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

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这两种“规则引擎”。