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

《无线传感器网络的WiME系统路由设计.docx》由会员分享，可在线阅读，更多相关《无线传感器网络的WiME系统路由设计.docx（13页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、无线传感器网络的WiME系统路由设计zhangting导语：随着微机电技术、低功耗嵌入式技术和通讯技术的飞速开展，具有感悟才能、计算才能和无线通讯才能的微型传感器得到了广泛的应用。随着微机电技术、低功耗嵌入式技术和通讯技术的飞速开展，具有感悟才能、计算才能和无线通讯才能的微型传感器得到了广泛的应用。这些由无线微型传感器组成的传感器网络可以协作地实时监测、感悟和收集网络分布区域内的各种环境或者检测对象的信息，并对这些信息进展处理，传送到需要这些信息的用户。这便是被美国贸易周刊认定的21世纪最具影响力的21项技术之一无线传感器网络WirelessSensorNetwork，WSN。在一个20层楼高

2、、有着上千个房间的庞大医院中，一位刚进入大楼的坐在智能车中的老年人或者残障病人，怎样可以轻松地到达自己要去的房间?我们正在尝试为这样的需求提供一种不需要外界干预的“室内自动导航系统称为“无线复眼系统WirelessMosaicEyes，WiME。概括地讲，它是一个基于生物行为启发的无线传感器网络，通过空中大量分布的无线节点对智能车提供行为控制，因此是一个采用无线传感器网络实现的机器人导航系统。WiME涉及两个路由问题：一个是在地理空间的机器人途径规划，另一个是在分散的通讯节点之间的信息通讯路由。复眼可以作为机器人导航经过中的电子灯塔；无线复眼网络可以被以为是描绘地理空间的一个拓扑图、地理途径规

3、划，也可以被简化为一个网络拓扑图中的途径规划。因此在WiME中，空间途径规划和信息通讯路由可以以完全一样的方式工作，而途径规划将根据各分散节点的语义定义为根底。为了在WiME这样一个采用无线传感器网络技术的系统的节点上实现完好地图的机器人导航，本设计使用一种单步方向查询的途径存储和查询系统。为了进一步减小资源有限的无线传感器节点中的途径信息的数据量，在WiME的设计中对每一个分组使用BloomFilter来压缩存储。另外，由于途径信息可能是动态建立的，为了知足频繁修改的要求，将每个子表设计为计数型BloomFilter。2、WiME系统2.1WiME的生物启发自主机器人通常都装备有传感器，可以

4、感悟环境并自主挪动，其装备的传感器可以以为是机器人的器官，它们所感悟到的信息由机载电脑集中处理。这种集中构架面临如下三大问题：传感器处理经过在真实环境中不鲁棒；在动态环境中，处理算法的计算量大；在非构造化的环境中理解场景特别困难。然而，与脊椎动物的眼睛相比，更低级的昆虫的眼睛是极具创造性和多样性的。生物学研究发现，一些昆虫可以用很小的神经系统来处理上万只小眼的信息。狼蛛复眼中的单眼功能不尽一样，一些用以提供前向视觉，而其他的那么用来探测和提供周边的视觉信息，这些视觉信号传递到大脑后可以交融并完成挪动检测、间隔估计、运动控制等。因此，通过分布式功能划分和适当的传感器路由，复眼的信息处理机制的效率

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

6、线通讯的分布式复眼以无线传感器网络为连接机制，将具有高运算量和大数据量特征的部分视觉信息以具有明确语义概念的形式实现通讯连接，完成低通讯带宽的视觉协同。2基于语义和信息全息的路由算法该算法是一个针对用户询问的最优途径搜索算法。路由算法应充分考虑查询语义，采用信息全息编码方式压缩可能查询和全局路由表，最终实现快速寻优。这也是昆虫复眼信息流分布的详细表达。3生物启发的分布式行为协调由于本研究将诸多运动行为分布在整个复眼系统中，机器人导航控制将面临怎样和谐地组织与激发行为。本研究将由生物神经网络为启发，探究脉冲spike鼓励的动作组织方式，以实现具有目的驱动和及时响应特性的行为控制网络。2.3无线复

7、眼系统中的单视神经元的设计根底运动检测器EMD。以生物视觉所特有的根底运动检测器EMD为蓝图，将低分辨率并可随机读取的CMOS视觉传感器作为视网膜，与无线模块连接构成系统单眼。低分辨率图像的语义提取。实时图像语义提取的内容包括：低分辨率的特征提取，包括颜色、纹理和区域外形；交融纹理、颜色和外形特征并给出解释；区域分割和空间分析。这局部将采用降分辨率技术，通过并行运算与FPGA实现相结合，减少计算代价并把算法应用到分布式视觉交融中。对象跟踪和形式识别。无线传感器节点。节点一方面通过外围电路与EMD相连，另一方面通过IEEE802.15.4协议的接收器与其他复眼及机器人进展通讯，进而提供复眼神经系

8、统的信道；同时，复眼信息的交融与行为序列的产生这样的运算也要在节点上完成。3、路由方式的选择所有的机器人导航都需要解决这样的一个问题：机器人怎样获知通往目的地的道路。在无线传感器网络中，无线节点之间的信息通讯路由也是一个首先要解决的问题。如前所述，由于地理信息固定，在WiME中空间途径规划和信息通讯路由完全可以以一样的方式工作。因此下面以途径规划来讲明这样一个路由存储和查询方式的选择问题。在无线传感器网络中，无线节点由于能量受限，采用的是低功耗嵌入式处理器，其计算才能和存储空间都有限。WiME也不例外，一般无法直接存储途径信息或将地图信息存储在节点上进而在需要时计算出最优途径。为此，首先考虑下

9、面的4种方法。方法1：作为一种常用的方法，可以查询整个地图的途径信息。由于房间数n诸多以为n不小于1000，途径数据宏大存在nn-12条途径，这样的地图可以由1台或者多台主效劳器提供。任何一个无线节点或者邻近的有限多个节点都知足不了这样的存储量。一个自然的方法是将全局地图存储到效劳器上，机器人终端在必要时从效劳器上下载途径信息。这类似于GPS设备的工作方式。方法2：根据使用的播送式无线路由通讯协议，建立一条到目的点的无线通讯链路，并利用建立的这条通讯线路作为地理导航线路。方法3：利用动态途径规划的思想，每个节点存储与自身相关的一定范围内的地理信息，并生成最优途径信息。方法4：每个节点存储全局节

10、点分布的地理信息和连接关系，在需要时与邻近的节点协同计算出最优途径。这是借鉴了计算机网络中分布式计算的概念。每种方法各有其优劣。第1种方法修改轻易，增加或者删除节点只需要在主效劳器端更新。第2种方法不需要事先知道节点的地理位置信息，整个途径信息是动态建立和修改的。第3种方法可以随着道路情况动态调整最优途径。由于节点可以实时观察到道路信息，可以引入参数来反映当前周边道路状况，比方道路的堵塞程度，并由此动态维护这样一个包含自身及邻近区域的最优途径表。但是这3种方法都是在多跳通讯的情况下完成的，返回完好的途径信息需要较多的通讯带宽和较长的通讯延时，这对通讯协议的鲁棒性提出了挑战。第4种方法的存储量相

11、对要小，与节点个数同数目级，但是多节点协同的最优途径的实时分布式计算对于无线传感器节点无疑是一个困难的问题。毕竟当前的分布式计算仍然局限在计算机网络领域。怎样将分布式计算和最新的网格计算的思想运用到无线传感器网络上，可能会成为嵌入式系统领域的下一个方向。在本设计的WiME中并没有主机这个概念，每个无线挪动节点同时充当了主机和路由器这是一个Ad-Hoc网络。Ad-Hoc网络的路由方式可以分为两大类：基于路由表的路由和基于按需建立路由的路由。由于庞大的途径数据量和极为有限的存储空间，上面的方法2、方法3和方法4都采用了基于按需建立路由的路由方式；而方法1固然是通过效劳器的方式提供了基于路由表的路由

12、，但是有限的效劳器的数目并不合适这样一个庞大的无线传感器网络。难道真的不能在每个无线节点上存储这样一个全局路由表，实现真正的基于路由表的路由方式吗？综合考虑，本文提出了下面的方法查询目的方向。这类似于人们在大街上问路，对方会告知该往哪个方向走；走到下一岔口时，又只好重新问路；最终可以成功到达目的地，而被询问者并不能提供这条道路的完好途径，所能提供的只是一个大概方向。相比而言，这种方法利用到了室内相对固定的地理信息的先验知识；每个节点只需要存储自身到目的点的方向信息，其存储量只是On；查询时也防止了多跳通讯的发生，而且没有增加额外的通讯负担，显然更合适无线传感器网络的特点。因此，WiME系统中的

13、途径查询采用了这种方法，通讯路由也基于这种方式建立。4、BloomFilter4.1路由信息的存储和查询在参考文献3中，作者提出了在无线传感器网络中实现带有语义的路由，其详细方法是在每个节点存储了一个语义检索表，检索表的每一点对应一个区域分类。每个节点只存在有限的几个区域分类或者称为“路由可能。这样，当发生包含足够属性的语义信息的路由查询输入时，节点调用自己的规那么引擎，通过计算匹配到检索表中的某一点，并从其对应的区域信息获取通往该区域的下一跳的信息。这与本没计中的这种单步途径查询的方法有相似之处。本设计中也有这样的一种规那么引擎，即下文所要介绍的BloomFilter。所不同的是，在本设计中

14、，检索表不是一个，而是多个；检索表中的元素不再指示区域或者路由的种别，而是指示输入是否在当前路由表中；而且查询输人不是抽象的语义信息，而是人名、房间号或者单位名称等这样的含有明确语义的地理空间标识。下面可以看到，采用BloomFilter不仅可以解决路由的分类和查询问题，而且可以进一步降低资源有限的无线传感器节点中的途径信息的数据量。进而在WiME的设计中，对每一个分组使用计数型BloomFilter实现了路由信息的动态修改。下面介绍根本的BloomFilter和计数型BloomFilter这两种“规那么引擎。4.2BIoomFilter概念BloomFilter的概念最早是由B.H.Bloo

15、m于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码，那么直

16、接存储需要400n位；而采用BloomFilter存储，需要m位m和kn同数目级。由于hash函数的计算需要花费一定的时间，限制k的个数不会很大，使得存储空间大大缩小，所以这是一种用时间换取空间的方法。4.3最优情况下BloomFilter的正向误检概率从上面可以看到，集合元素个数n、hash函数个数k和向量表长度m是BloomFilter的3个关键参数。BloomFilter中存在着这样一种情况，即固然一个元素不属于集合S，由于hash函数的随机性，有可能k个hash变换在v中的对应元素均为1，进而该元素被误以为属于集合S。这种情况称为“正向误检falsepositive。从概率上看，正向误

17、检总是不可防止的。将n个元素插入BloomFilter表中后，每一位元素仍然为0的概率是如无声明，下面均以为hash函数是均匀映射的：4.4计数型BloomFilter在生成BloomFilter表的经过中，不可防止地会出现映射到v的同一位置的情况，这在存在增删的情况下就会出现问题。假如一个元素从集合中删除，那么其对应的BloomFilter表中的元素都要从1变为0。那么，其他映射到该位置的元素在查询自身是否属于集合时，就不会得到正确结果，这称为“反向误检falsenegative。计数型BloomFilter可以解决这个问题，它将向量表中每个位置从1位表示改为多位表示。这样，添加操纵中每映射

18、到某一位置1次，该位置就计数加1；删除操纵中时，该位置减1。计数位数决定了所能计数的最大值。4.5BloomFilter的其他改良除了计数型BloomFilter，还有很多在尝试提出改良的BloomFilter数据构造。参考文献6提出的压缩型BloomFilter讨论了非最优情况下m、n和k之间的互相关系；参考文献7提出的域衰减BloomFilter，针对无线传感器网络中洪泛查询的特点提出了随空间域衰减的方式，其BloomFilter向量表中置1的位会随着空间域的变化以一定概率清0，那么BloomFiler解码时就变成了统计k个hash函数对应位置上1的个数个数越大可能性越大；参考文献8提出的

19、拆分型BloomFilter，针对反复增删最终导致最初设计的BloomFilter表不可用的情况，提出将总表分割成多个子表来设计。综合考虑，笔者仍然以为计数型BloomFilter是简单、易用的，而且具有较好的性能。尽管参考文献5建议使用4位计数，但经过对计数位数的理论分析和实验验证，笔者最终采用了2位计数。这已经可以将进展反复增删可能造成的反向误检的概率降低到1.8510-4。反复增删5396次，才会出现1次反向误检，对1000个节点这样的规模已经是够用的了。不过，对于这一问题的讨论已经超出了本文的范围，这里不再赘述。5、结论WiME是一个基于生物行为启发的、使用无线传感器网络实现的智能复眼系统。它尝试着从仿生的角度来有效地降低智能实现的复杂性，进步机器人的挪动才能；同时拓宽机器人的应用范围，使廉价挪动机器人也可以表现出卓越的挪动智能。这是从另一个视角解决集中式人工智能所面临的应用难点的一种新的理论尝试。WiME中的机器人导航技术采用单步的方向查询方式，完成了一跳情况下的路由查询任务；而且使用了BloomFilter来压缩存储，空间进展了高度优化。这使在无线传感器网络这样一个计算才能弱、资源严重受限的环境下完成途径和通讯路由查询系统这样一个包含大数据最的工作变成了现实。希望本设计的思路，对于其他的机器人导航应用有很好的启发作用。0