基于两层结构的无线传感器网络Mesh路由协议

王宏飞，李大霖，牟荣增，阎跃鹏

(中国科学院微电子研究所昆山分所，江苏昆山215347)

无线传感器网络(wireless sensor network，WSN)是一种低速率、低功耗、短距离传输的无线网络.与有线网络相比，无线网络传输的无线信号易于受到干扰，因此在环境复杂的户外以及室内等环境中，无线传输的链路质量频繁变化;此外，WSN还具有节点能量、计算和存储资源有限的特点［1］.无线传感器网络中节点可以按照3种拓扑结构形成多跳的低速率网络，分别为星型(star)拓扑、树型(tree)拓扑和网状(mesh)拓扑.相比于星型和树型拓扑，网状拓扑结构具有较广的网络覆盖范围，较大的网络吞吐量以及较高的数据传输可靠性［2-3］，因此无线传感器网络越来越多地使用网状拓扑结构.路由算法是无线mesh传感器网络的核心技术，目前的路由算法大多来自于成熟的Ad hoc网络.AODV(Ad hoc on demand distance vector)是最常用的一种［4］，已经在无线mesh网络标准IEEE 802.11s中得到了成功的应用［5］.在无线传感器网络中，通用标准 ZigBee也使用了AODVjr路由算法，对AODV算法进行了改进，保持其原始功能，但考虑到节能、应用方便性等因素，简化了AODV的一些特点［6］.但AODVjr算法存在两个根本性的问题:一方面依赖于路径对称性，在链路质量变化频繁的无线传感器网络中，非对称路径的大量存在会导致路由建立以及数据转发的失败［7-9］;另一方面AODVjr算法仅依靠一次路由管理帧的洪泛建立路由，因此路由管理帧的丢失会影响节点的路由选择.DSR(dynamic source routing protocol)是另外一种常用于移动Ad hoc网络的路由协议［10-11］，该协议中源节点发送的数据包需要包含转发路径上经过的所有节点，不适用于节点存储资源有限的无线传感器网络.IEEE标准组于2009年提出了适用于低速mesh结构网络的标准IEEE 802.15.5，在MAC(media access control)层实现了路由功能［12］，但其中单播路由仍然依靠邻居关系和父子关系进行数据转发，并未完全实现节点之间的mesh路由.

文中提出一种基于统计学的mesh路由算法，节点周期性洪泛一种管理帧，通过单向传递，便可以根据这种管理帧在其他节点的投递成功率来确定最优路径，消除了路由管理帧丢失以及非对称路径对于路由建立的影响.为了降低网络中节点的资源消耗，还在mesh网络下增加星型结构的子网.在星型子网下，簇头外的其他节点只能与簇头进行通信，不需要参加mesh路由，并且由簇头代替自己完成路由功能.

1 网络拓扑

网络中存在2种节点:路由节点和终端节点.它们按照图1所示组成网状和星型上下两层拓扑结构.

图1 两层结构网络拓扑图

下层网络包含若干子网，每个子网均为星型网络，由一个路由节点和若干终端节点组成:路由节点作为子网的管理者，称为簇头，负责子网的维护以及与本子网内节点相关数据帧的转发;终端节点均为簇头的子节点，只能与簇头进行通信，对于计算能力及存储等资源的要求较低.路由节点在上层形成一个mesh网络，此网络通过路由节点之间建立的路由路径将各子网内的数据转发至目的节点所在子网的簇头.

网络中每个节点均拥有一个16 bit的物理地址，作为节点间相互区分的唯一标识;每个子网将本子网的簇头节点的物理地址作为子网地址，是子网间相互区分的标识.另外每个节点同时被分配一个32 bit的扩展地址，用来指示应用数据传输过程中的最初源节点(srcAddr)以及最终目的节点(dstAddr);扩展地址的高16 bit为节点所在子网的地址(subAddr)，低16 bit为节点的物理地址(leftAddr).

2 星型子网

星型子网的建立、管理与维护均由簇头负责.一个路由节点启动后便建立一个子网，并作为子网的簇头周期性广播一种包含子网信息的信标帧.终端节点启动后在一段时间内监听周围簇头节点广播的子网信息，从中选择合适的子网并通过与相应簇头节点的信息交互加入网络，与簇头节点形成父子关系.

子网内父子关系的维护采用基于生存周期的被动维护机制:当节点收到来自于父节点或子节点的帧时便更新相应的生存周期;如果在生存周期内无法收到相应节点的帧，便断掉相应的父子关系.

簇头节点还负责发送与接收本子网所有数据帧.终端节点将需要发送的数据帧交给簇头，由其代为寻找到目的节点的路由路径并进行转发;另外簇头还会接收发送给本子网内终端节点的数据帧，并进一步转发给目的终端节点.

与路由节点相比，终端节点只能与簇头进行通信，不需要参与路由建立、数据转发以及子网管理等功能，结构简单，有效地降低了资源消耗.

3 Mesh路由

簇头路由节点之间通过多跳通信形成一个网状网络，作为骨干通信网络.每个路由节点均建立并维护到其他路由节点的路由路径，并将数据帧转发至相应子网的簇头路由节点.路由节点之间路由路径的建立与维护通过信标帧在全网中的洪泛来完成.

3.1 信标帧

路由节点周期性广播的信标帧(beaconFrame)在网络中具有两个功能:一方面在星型网络中帮助簇头节点管理并维护子网;另一方面可以作为路由管理帧，在mesh网络中通过洪泛过程协助路由节点形成并维护有效的路由路径.信标帧包含如下有效管理信息:接收地址(recAddr)和发送地址(sendAddr)是信标帧洪泛过程中单跳通信的物理地址信息;序列号(frameSeq)代表信标帧的新旧程度，由产生信标帧的路由节点封装并在洪泛过程中保持不变，可以避免重复和过时处理;已加入终端节点个数表示该路由节点所在子网内的终端节点个数，用于星型子网的管理，可以限制子网规模;源子网地址(originAddr)为生成信标帧的路由节点的子网地址;上次发送子网地址(lastAddr)存储了信标帧在洪泛过程中上一跳路由节点的子网地址;TTL(time to lives)表征信标帧在洪泛过程中的生存时间;Tq(transmit quality)为信标帧在某条路径上的投递成功率，为表征路由路径质量的量值，用作路由判据.

3.2 路由判据

本文协议将信标帧在某条路径上的投递成功率(Tq)作为路由判据:较大的路由判据代表较优的路由路径.信标帧中洪泛过程中不断地被中间节点更新Tq域.当其通过某条路径到达某一节点时，接收节点便可以计算出通过该路径到达信标帧源节点的Tq值，并从多条路径中选择最优路径.

3.2.1 单跳Tq

单跳Tq指本节点到一跳内可通信的邻居节点(neighborNode)的信标帧投递成功率，是路径Tq值的计算基础.本文协议通过统计两类信标帧的投递成功率计算单跳Tq:当帧中发送地址(sendAddr)与源子网地址(originAddr)相同时，此帧来自邻居节点，其接收成功率为反向投递概率Rq;当帧中上次发送地址(lastAddr)以及源子网地址(originAddr)均与本地子网地址(localSubAddr)相同时，此帧由本节点产生并被邻居节点转发回来的信标帧，其接收成功率为回路投递概率Eq;则本节点到邻居节点的信标帧投递概率Tq=Eq/Rq，即为单跳Tq.

3.2.2 窗口机制

本文协议采用滑动窗口机制更准确地估算信标帧的投递成功率.滑动窗口在每次接收到最新的信标帧后进行更新;长度为N，记录了最新的N个序列号对应的信标帧的接收情况，如图2所示:1表示该帧已被成功接收，0表示未被成功接收，窗口中1的数量除以窗口长度即可计算出信标帧的投递成功率.

图2 Tq计算窗口机制

3.2.3 路径Tq

一条完整的路径由若干条单跳链路组成，文中网络通过比较路径总Tq来决定最优路由路径.路径Tq反映了从该路径的一端到另一端的信标帧投递成功率，为各单跳Tq的乘积.图3为路径Tq的计算图.

图3 路径Tq的计算

如图3所示，源节点A1在产生信标帧时初始化Tq1为255，Tqi(i＞1)为单跳链路Ai- ＞Ai-1的Tq，Tqi1为在Ai处计算所得的路径AiA1的总Tq，则路径AnA1的总Tq为

当路由节点收到某一源节点的信标帧后，将帧中的Tq值与到发送节点的Tq值相乘，计算出通过此次传播路径本节点到源节点的Tq值，进而与路由表中已经存在的Tq值进行比较得出最优路径.

3.3 路由建立

路由节点之间路由路径的建立通过信标帧的洪泛来完成，建立过程仅依靠信标帧的单向传输.路由节点会周期性生成并广播信标帧，当某个路由节点收到一个信标帧(beaconFrame)后，会进行如下步骤处理:

1)如果发送地址(sendAddr)为广播地址(broadAddr)或本地物理地址(localAddr)，则丢弃该帧，否则转入步骤2).

2)如果源子网地址(originAddr)为广播地址，则丢弃该帧，否则转入步骤3).

3)如果此帧源自本节点并由邻居节点发送，则更新回路投递概率Eq，然后丢弃该帧.

4)如果此帧源自邻居节点并由邻居节点发送，则更新反向投递概率Rq，然后转入步骤5).

5)计算路径Tq值并更新路由表(routeTable)相关表项，然后转入步骤6).

6)如果帧中TTL值为0，则丢弃该帧，否则更新信标帧中相应域并继续广播.

以下为路由建立算法的伪码描述:

3.4 路由转发

当路由节点收到一个数据帧(dataFrame)时，会进行如下处理:

1)提取最终目的节点(dstAddr)扩展地址中的高16 bit子网地址(dstSubAddr)，然后转入步骤2);

2)如果目的子网地址为本地子网地址(local-SubAddr)，即本数据帧发给本子网，则转入步骤3)，否则转入步骤4);

3)提取最终目的节点扩展地址中的低16 bit地址(dstLeftAddr)，如果等于本地物理地址(local-Addr)，即本数据帧发给自己，则接收并做相应处理;否则将检查子节点表(childTable)，如果目的节点在子节点表中则将其转发给本子网内相应的终端节点，否则将其丢弃;

4)检查路由表，如果目的子网地址不在路由表中，则转入步骤5);否则将该数据帧转发给相应路由表项中的下一跳地址(nextHopAddr);

5)检查邻居表，如果目的子网地址不在邻居表中，则丢弃该帧;否则如果相应邻居表项中Tq值为0，则丢弃该帧，否则将该数据帧直接发送给邻居节点.

以下为路由转发算法的伪码描述:

4 性能分析

文中搭建了实际网络环境并通过测试对本文协议与ZigBee协议栈进行性能对比分析.测试网络的硬件平台为自主设计的基于Freescale无线传感器网络芯片MC13213的无线传输模块，其可调发射功率范围为-28.7 ～3.4 dBm，接收灵敏度为 -92 dBm［13］;软件部分本文协议基于ucos-Ⅱ实时操作系统实现，ZigBee采用Freescale提供的ZigBee协议栈代码.

测试地点为写字楼室内办公区域，大小为50 m×50 m，网络拓扑如图4所示:共有21个路由节点分布在测试环境中，传输不同类型应用数据的两种终端各4个，也平均分布在测试环境中.

图4 性能测试节点分布图

4.1 对于对称路径依赖性的对比

本部分测试比较两种协议在非对称路径上数据投递成功率.如图4所示，在测试过程中，网络中的路由节点随机动态地调整发射功率，以此模拟链路的非对称性.分别在两种协议下终端节点Ⅰ-4以1 kb·s-1的速率向路由节点T发送应用数据，其他节点不发送任何应用数据，测试时间为4 h，并在T点以10 min为单位统计丢包率，最终统计结果如图5示.

图5 对称路径依赖性

由图5可见，在存在非对称路径的环境中，文中提出的协议相比于ZigBee协议有着稳定且较低的丢包率.这是由于ZigBee协议路由的建立需要路由请求帧和路由回复帧两种路由管理帧在所选路径上的回路传输，非对称路径可能会导致路由回复帧在反向路径上的丢失，从而造成路由建立失败;本文协议路由建立的过程仅基于路由管理帧的单向传输，所以对于对称路径的依赖比ZigBee协议低.

4.2 对于路由管理帧投递效率依赖性的对比

在本部分测试中，网络中路由节点在接收到路由管理帧和数据帧时以0.1%的概率将帧丢弃不处理，以此测试两种路由协议对于路由管理帧投递失败的容忍程度.测试时终端节点Ⅰ-4向路由节点B以1 kb·s-1的速率发送应用数据，其他节点不发送任何应用数据，测试时间为4 h，并在B点以10 min为单位统计丢包率，最终统计结果如图6示.

图6 路由管理帧投递成功率依赖性对比

由图6可见相比ZigBee协议，本文协议对路由管理帧的丢失有更好的容忍度.这是因为ZigBee协议仅依靠一次路由管理帧的洪泛过程建立路由，因此路由管理帧的丢失会影响到可选路径的数量或造成路由建立的失败，也有可能将最优路径漏掉;而本文协议则统计了近期管理帧的投递成功率，并以此为判据选择最优路由，所以路由建立不会受到某次路由管理帧丢失的影响.

4.3 网络整体应用数据投递成功率对比

测试时在两种协议下所有Ⅰ类终端节点和所有Ⅱ类终端节点在相同的负载下分别向G点和L点发送应用数据，每组测试中负载不同，时间均为4 h，最后统计G点和L点的应用数据丢包率，统计结果如图7-8所示.

图7 Ⅰ类终端G点处丢包率对比

图8 Ⅱ类终端L点处丢包率对比

由图7-8可以看出在各种负载情况下本文协议的数据投递成功率均比ZigBee协议有优势，而且优势会随着负载的提高而扩大.这是因为终端负载的提高会相应地增大网络中存在的数据量，从而增大没有传输可靠性的路由管理帧的丢失概率.本文协议对于管理帧丢失可以容忍的特性减轻了这方面的影响，而依赖于路由管理帧投递成功率的ZigBee协议会受到严重的影响.对比图7-8还可以看出本文协议相对于ZigBee协议在G点处比在L点处的整体优势大，这可能是由于G点附近环境较为复杂，会出现大量的非对称路径导致ZigBee协议整体丢包率增大.

5 结论

文中提出了一种基于两层网络结构的无线传感器网络mesh路由算法，从根本上解决了ZigBee中AODVjr路由算法对对称路径以及路由管理帧投递成功率依赖性强的问题，结论如下:

1)路由建立依靠管理帧的单向传输，不需要节点间管理帧的交互，降低了路由算法对路径对称性的依赖.

2)将一段时间内路由管理帧的丢包率作为路由判据，因此消除了某些管理帧丢失对路由建立的影响.

3)实际测试表明在链路质量频繁变化的无线传感器网络环境中，相比ZigBee协议本文协议有着更高的数据传输可靠性.未来可以重点研究此协议对于含有移动节点的网络环境的适应能力.

References)

［1］Sai Krishna T N，Garimella R M.Mesh multipath routing with leveling in route discovery:an efficient strategy in wireless sensor networks［C］∥Proceedings of2009 4th International Symposium on Wireless and Pervasive Computing.Melbourne，VIC，Australia:IEEE Computer Society，2009，doi:10.1109/ISWPC.2009.4800592.

［2］张荣标，陈 婷，沈 卓，等.工业控制WSN汇聚节点可靠性分析［J］.江苏大学学报:自然科学版，2011，32(3):320-324.Zhang Rongbiao，Chen Ting，Shen Zhuo，et al.Reliability analysis of sink node in industrial control WSN［J］.Journal of Jiangsu University:Natural Science Edition，2011，32(3):320-324.(in Chinese)

［3］Hassan M N，Stewart R，Brito E，et al.Deployment and performance issues of an integrated wireless sensor network and wireless mesh campus network［C］∥Proceedings of2010 7th International Symposium on Communication Systems，Networks and Digital Signal Processing.Newcastle upon Tyne，United Kingdom:IEEE Computer Society，2010:890-895.

［4］Yang Hua，Li Zhiyuan.Simulation and analysis of a stability reverse AODV routing protocol［C］∥Proceedings of2012 2nd International Conference on Consumer Electronics，Communications and Networks.Three Gorges，China:IEEE Computer Society，2012:560-563.

［5］Bahr M.Proposed routing for IEEE 802.11s WLAN mesh networks［C］∥Proceedings of the2nd Annual International Workshop on Wireless Internet.Boston，MA，United States:Association for Computing Machinery，2006，doi:10.1145/1234161.1234166.

［6］Dong Yuejun，Dong Zhiyong，Zhang Shuqin，et al.Zig-Bee based energy efficient reliable routing in wireless sensor network:study and application［C］∥Proceedings of2011IEEE3rd International Conference on Communication Software and Networks.Xi'an，China:IEEE Computer Society，2011:464-467.

［7］易 欢.基于AODV的自组网系统的设计与实现及单向链路问题分析［D］.北京:北京邮电大学信息与通信工程学院，2008.

［8］Jairath A，Khan W U.Modified AODV with Qos for asymmetric MANET［C］∥Proceedings of2010International Conference on Computational Intelligence and Communication Networks.Bhopal，India:IEEE Computer Society，2010:265-268.

［9］Xian Feng，Wang Jianzhi.An efficient ad hoc on-demand distance vector routing protocol［C］∥Proceedings of2010International Conference on Educational and Network Technology.Qinhuangdao，China:IEEE Computer Society，2010:453-458.

［10］Zhang Dongli，Jiao Wencheng，Zheng Jianling.Research and improvement of DSR protocol in Ad hoc network［C］∥Proceedings of2010 2nd International Conference on Industrial and Information Systems.Dalian，China:IEEE Computer Society，2010:242-244.

［11］Long Zhaohua，He Zheng.Optimization and implementation of DSR route protocol based on Ad hoc network［C］∥Proceedings of2007International Conference on Wireless Communications，Networking and Mobile Computing.Shanghai， China:IEEE Computer Society，2007:1508-1511.

［12］Lee Myung J，Zhang Rui，Zheng Jianliang，et al.IEEE 802.15.5 WPAN mesh standard-low rate part:meshing the wireless sensor networks［J］.IEEE Journal on Selected Areas in Communications，2010，28(7):973-983.

［13］Freescale.MC13211/212/213/214 Reference Manual 2006［EB/OL］.http:∥www.freescale.com，2012-09-17.