无线传感器网络的WiME系统路由设计

引 言

随着微机电技术、低功耗嵌入式技术和通信技术的飞速发展，具有感知能力、计算能力和无线通信能力的微型传感器得到了广泛的应用。这些由无线微型传感器组成的传感器网络能够协作地实时监测、感知和采集网络分布区域内的各种环境或检测对象的信息，并对这些信息进行处理，传送到需要这些信息的用户。这便是被美国商业周刊认定的21世纪最具影响力的21项技术之一——无线传感器网络(Wireless Sensor Network，WSN)。

在一个20层楼高、有着上千个房间的庞大医院中，一位刚进入大楼的坐在智能车中的老年人或残障病人，如何可以轻松地到达自己要去的房间?我们正在尝试为这样的需求提供一种不需要外界干预的“室内自动导航系统”——称为“无线复眼系统(Wireless MOSaic Eyes，WiME)”。概括地讲，它是一个基于生物行为启发的无线传感器网络，通过空中大量分布的无线节点对智能车提供行为控制，因此是一个采用无线传感器网络实现的机器人导航系统。

WiME涉及两个路由问题：一个是在地理空间的机器人路径规划，另一个是在分散的通信节点之间的信息通信路由。复眼可以作为机器人导航过程中的电子灯塔；无线复眼网络可以被认为是上海卫星电视描述地理空间的一个拓扑图、地理路径规划，也可以被简化为一个网络拓扑图中的路径规划。因此在WiME中，空间路径规划和信息通信路由可以以完全相同的方式工作，而路径规划将根据各分散节点的语义定义为基础。

为了在WiME这样一个采用无线传感器网络技术的系统的节点上实现完整地图的机器人导航，本设计使用一种单步方向查询的路径存储和查询系统。为了进一步减小资源有限的无线传感器节点中的路径信息的数据量，在WiME的设计中对每一个分组使用Bloom Filter来压缩存储。另外，由于路径信息可能是动态建立的，为了满足频繁修改的要求，将每个子表设计为计数型Bloom Filter。

2 WiME系统

2.1 WiME的生物启发

自主机器人通常都配备有传感器，能够感知环境并自主移动，其配备的传感器可以认为是机器人的器官，它们所感知到的信息由机载电脑集中处理。这种集中构架面临如下三大问题：传感器处理过程在真实环境中不鲁棒；在动态环境中，处理算法的计算量大；在非结构化的环境中理解场景十分困难。

然而，与脊椎动物的眼睛相比，更低级的昆虫的眼睛是极具创造性和多样性的。生物学研究发现，一些昆虫可以用很小的神经系统来处理上万只小眼的信息。狼蛛复眼中的单眼功能不尽相同，一些用以提供前向视觉，而其他的则用来探测和提供周边的视觉信息，这些视觉信号传递到大脑后可以融合并完成移动检测、距离估计、运动控制等。因此，通过分布式功能划分和适当的传感器路由，复眼的信息处理机制的效率可以很高。

受此启发，建立WiME这样一个基于无线复眼网络的智能环境。其中，各单眼将由低分辨率的视觉传感器节点构成，通过IEEE 802.15.4协议通信并组织形成环境神经系统；通过探索仿生技术和算法，以支持无线复眼系统的智能信息处理(包括路径规划、行为协调、传感器融合和路由等)以及视觉伺服。在WiME中，每个单眼都提供有明确的语义(定位信息和行为集)，而它们的拓扑连接将采用行为网络来隐式建立；行为将通过能量累积所产生的事件进行激发。节点之间的连接包含了信息融合和路由的条件概率信息；机器人的导航将建立在具有明确语义的传感器拓扑图的基础之上，而不是建立在非结构的地理环境之上。

2.2 WiME的设计目标

(1)基于无线通信的分布式复眼

以无线传感器网络为连接机制，将具有高运算量和大数据量特征的局部视觉信息以具有明确语义概念的形式实现通信连接，完成低通信带宽的视觉协同。

(2)基于语义和信息全息的路由算法

该算法是一个针对用户询问的最优路径搜索算法。路由算法应充分考虑查询语义，采用信息全息编码方式压缩可能查询和全局路由表，最终实现快速寻优。这也是昆虫复眼信息流分布的具体体现。

(3)生物启发的分布式行为协调

由于本研究将众多运动行为分布在整个复眼系统中，机器人导航控制将面临如何和谐地组织与激发行为。本研究将由生物神经网络为启发，探索脉冲(spike)激励的动作组织方式，以实现具有目标驱动和及时响应特性的行为控制网络。

2.3 无线复眼系统中的单视神经元的设计

①基础运动检测器(EMD)。以生物视觉所特有的基础运动检测器(EMD)为蓝图，将低分辨率并可随机读取的CMOS视觉传感器作为视网膜，与无线模块连接构成系统单眼。

②低分辨率图像的语义提取。实时图像语义提取的内容包括：低分辨率的特征提取，包括颜色、纹理和区域形状；融合纹理、颜色和形状特征并给出解释；区域分割和空间分析。这部分将采用降分辨率技术，通过并行运算与FPGA实现相结合，减少计算代价并把算法应用到分布式视觉融合中。

③对象跟踪和模式识别。

④无线传感器节点。节点一方面通过外围电路与EMD相连，另一方面通过IEEE 802.15.4协议的接收器与其他复眼及机器人进行通信，从而提供复眼神经系统的信道；同时，复眼信息的融合与行为序列的产生这样的运算也要在节点上完成。

3 路由方式的选择

所有的机器人导航都需要解决这样的一个问题：机器人如何获知通往目的地的道路。在无线传感器网络中，无线节点之间的信息通信路由也是一个首先要解决的问题。如前所述，由于地理信息固定，在WiME中空间路径规划和信息通信路由完全可以以相同的方式工作。因此下面以路径规划来说明这样一个路由存储和查询方式的选择问题。

在无线传感器网络中，无线节点由于能量受限，采用的是低功耗嵌入式处理器，其计算能力和存储空间都有限。WiME也不例外，一般无法直接存储路径信息或者将地图信息存储在节点上从而在需要时计算出最优路径。为此，首先考虑下面的4种方法。

方法1：作为一种常用的方法，可以查询整个地图的路径信息。由于房间数n众多(认为n不小于1000)，路径数据巨大(存在n(n-1)／2条路径)，这样的地图可以由1台或多台主服务器提供。任何一个无线节点或邻近的有限多个节点都满足不了这样的存储量。一个自然的方法是将全局地图存储到服务器上，机器人终端在必要时从服务器上下载路径信息。这类似于GPS设备的工作方式。

方法2：根据使用的广播式无线路由通信协议，建立一条到目标点的无线通信链路，并利用建立的这条通信线路作为地理导航线路。

方法3：利用动态路径规划的思想，每个节点存储与自身相关的一定范围内的地理信息，并生成最优路径信息。

方法4：每个节点存储全局节点分布的地理信息和连接关系，在需要时与临近的节点协同计算出最优路径。这是借鉴了计算机网络中分布式计算的概念。

每种方法各有其优劣。第1种方法修改容易，增加或删除节点只需要在主服务器端更新。第2种方法不需要事先知道节点的地理位置信息，整个路径信息是动态建立和修改的。第3种方法可以随着道路情况动态调整最优路径。由于节点能够实时观察到道路信息，可以引入参数来反映当前周边道路状况，比如道路的堵塞程度，并由此动态维护这样一个包含自身及临近区域的最优路径表。但是这3种方法都是在多跳通信的情况下完成的，返回完整的路径信息需要较多的通信带宽和较长的通信延时，这对通信协议的鲁棒性提出了挑战。第4种方法的存储量相对要小，与节点个数同数量级，但是多节点协同的最优路径的实时分布式计算对于无线传感器节点无疑是一个困难的问题。毕竟当前的分布式计算仍然局限在计算机网络领域。如何将分布式计算和最新的网格计算的思想运用到无线传感器网络上，可能会成为嵌入式系统领域的下一个方向。

在本设计的WiME中并没有主机这个概念，每个无线移动节点同时充当了主机和路由器——这是一个Ad-Hoc网络。Ad-Hoc网络的路由方式可以分为两大类：基于路由表的路由和基于按需建立路由的路由。由于庞大的路径数据量和极为有限的存储空间，上面的方法2、方法3和方法4都采用了基于按需建立路由的路由方式；而方法1虽然是通过服务器的方式提供了基于路由表的路由，但是有限的服务器的数量并不适合这样一个庞大的无线传感器网络。难道真的不能在每个无线节点上存储这样一个全局路由表，实现真正的基于路由表的路由方式吗？

综合考虑，本文提出了下面的方法——查询目标方向。这类似于人们在大街上问路，对方会告知该往哪个方向走；走到下一岔口时，又只好重新问路；最终可以成功到达目的地，而被询问者并不能提供这条路线的完整路径，所能提供的只是一个大概方向。

相比而言，这种方法利用到了室内相对固定的地理信息的先验知识；每个节点只需要存储自身到目标点的方向信息，其存储量只是O(n)；查询时也避免了多跳通信的发生，而且没有增加额外的通信负担，显然更适合无线传感器网络的特点。因此，WiME系统中的路径查询采用了这种方法，通信路由也基于这种方式建立。

4 Bloom Filter

4.1 路由信息的存储和查询

在参考文献[3]中，作者提出了在无线传感器网络中实现带有语义的路由，其具体方法是在每个节点存储了一个语义检索表，检索表的每一点对应一个区域分类。每个节点只存在有限的几个区域分类或称为“路由可能”。这样，当发生包含足够属性的语义信息的路由查询输入时，节点调用自己的规则引擎，通过计算匹配到检索表中的某一点，并从其对应的区域信息获取通往该区域的下一跳的信息。这与本没计中的这种单步路径查询的方法有相似之处。本设计中也有这样的一种规则引擎，即下文所要介绍的Bloom Filter。所不同的是，在本设计中，检索表不是一个，而是多个；检索表中的元素不再指示区域或路由的类别，而是指示输入是否在当前路由表中；而且查询输人不是抽象的语义信息，而是人名、房间号或单位名称等这样的含有明确语义的地理空间标识。

下面可以看到，采用Bloom Filter不仅可以解决路由的分类和查询问题，而且可以进一步降低资源有限的无线传感器节点中的路径信息的数据量。进而在WiME的设计中，对每一个分组使用计数型Bloom Filter实现了路由信息的动态修改。下面介绍基本的Bloom Filter和计数型Bloom Filter这两种“规则引擎”。

4.2 BIoom Filter概念

Bloom Filter的概念最早是由B.H.Bloom于1970年提山的。已知一个集合S含有n个元素，每个元素可以是人名、网址或者某个编号之类的能被计算机识别的独有的一个或一组符号。我们定义一个含有m个元素的向量表v，v中的每个元素只使用1位表示，即每个元素只能表示为0或1。初始化v的每个元素为0。假设有k个独立的hash函数H1，…，Hk，映射范围为m。对S中的每个元素，将其进行hash变换后在v中对应的位置上置1。

如果要知道一个元素a是否在集合S中，可以参照图1对其进行k个hash变换，并查询v中对应的元素是否为1。如果k个对应元素均为1，就断定a在集合S中。

举例来说，如果S表示的是一个URL查找表，每个元素平均包含50个ASCII码，则直接存储需要400n位；而采用Bloom Filter存储，需要m位(m和kn同数量级)。由于hash函数的计算需要花费一定的时间，限制k的个数不会很大，使得存储空间大大缩小，所以这是一种用时间换取空间的办法。

edatop.com

4.3 最优情况下Bloom Filter的正向误检概率

从上面可以看到，集合元素个数n、hash函数个数k和向量表长度m是Bloom Filter的3个关键参数。BloomFilter中存在着这样一种情况，即虽然一个元素不属于集合S，由于hash函数的随机性，有可能k个hash变换在v中的对应元素均为1，从而该元素被误认为属于集合S。这种情况称为“正向误检(false positive)”。从概率上看，正向误检总是不可避免的。

将n个元素插入Bloom Filter表中后，每一位元素仍然为0的概率是(如无声明，下面均认为hash函数是均匀映射的)：

4.4 计数型Bloom Filter

在生成Bloom Filter表的过程中，不可避免地会出现映射到v的同一位置的情况，这在存在增删的情况下就会出现问题。如果一个元素从集合中删除，则其对应的Bloom Filter表中的元素都要从1变为0。那么，其他映射到该位置的元素在查询自身是否属于集合时，就不会得到正确结果，这称为“反向误检(false negative)”。计数型Bloom Filter可以解决这个问题，它将向量表中每个位置从1位表示改为多位表示。这样，添加操作中每映射到某一位置1次，该位置就计数加1；删除操作中时，该位置减1。计数位数决定了所能计数的最大值。

4.5 Bloom Filter的其他改进

除了计数型Bloom Filter，还有许多在尝试提出改进的Bloom Filter数据结构。参考文献[6]提出的压缩型Bloom Filter探讨了非最优情况下m、n和k之间的相互关系；参考文献[7]提出的域衰减Bloom Filter，针对无线传感器网络中洪泛查询的特点提出了随空间域衰减的方式，其Bloom Filter向量表中置1的位会随着空间域的变化以一定概率清0，则Bloom Filer解码时就变成了统计k个hash函数对应位置上1的个数(个数越大可能性越大)；参考文献[8]提出的拆分型Bloom Filter，针对反复增删最终导致最初设计的Bloom Filter表不可用的情况，提出将总表分割成多个子表来设计。

综合考虑，笔者仍然认为计数型Bloom Filter是简单、易用的，而且具有较好的性能。尽管参考文献[5]建议使用4位计数，但经过对计数位数的理论分析和实验验证，笔者最终采用了2位计数。这已经可以将进行反复增删可能造成的反向误检的概率降低到1.85×10-4。反复增删5396次，才会出现1次反向误检，对1000个节点这样的规模已经是够用的了。不过，对于这一问题的讨论已经超出了本文的范围，这里不再赘述。

5 结 论

WiME是一个基于生物行为启发的、使用无线传感器网络实现的智能复眼系统。它尝试着从仿生的角度来有效地降低智能实现的复杂性，提高机器人的移动能力；同时拓宽机器人的应用范围，使廉价移动机器人也可以表现出卓越的移动智能。这是从另一个视角解决集中式人工智能所面临的应用难点的一种新的理论尝试。

WiME中的机器人导航技术采用单步的方向查询方式，完成了一跳情况下的路由查询任务；而且使用了Bloom Filter来压缩存储，空间进行了高度优化。这使在无线传感器网络这样一个计算能力弱、资源严重受限的环境下完成路径和通信路由查询系统这样一个包含大数据最的工作变成了现实。希望本设计的思路，对于其他的机器人导航应用有很好的启发作用。