基于苯环结构的WSNs 单向链路故障检测算法*

刘静娜，邵 清

(上海理工大学 光电信息与计算机工程学院，上海200093)

0 引 言

无线传感器网络(wireless sensor networks，WSNs)在军事、工业、智能交通、空间探索等领域有着广阔的应用前景，被认为是全球未来四大高技术产业之一［1，2］。尤其非常适合无法快速搭建基础设施的情况，如战场上部队快速展开和推进、自然灾害后的搜索和营救、临时会议等［3，4］。WSNs节点由自带电池供给电能，因此，节省能源是设计任何协议的前提条件［5～7］，加上通信环境非常恶劣，终端规格各异，网络性能易受天气和地形的影响，导致网络中单向链路普遍存在，使得网络的无线通信性能也会经常变化，甚至通信有可能中断。因此，如何设计可靠的通信机制以满足网络通信的节能可靠性需求是WSNs 所面临的一个重要问题［8，9］。

目前很多机构和学者致力于解决单向链路故障问题，Marina M K，Das S R 等人在按需距离矢量(Ad Hoc on－demand distance vector，AODV)协议［10］的基础上，提出了剔除单向链路故障的路由协议——AODV－LSA(AODV link－stateaware)［11］，该协议通过邻居节点间的信息交互来发现单向链路故障并重新寻路。但这种方法会报文数据巨大，导致资源的不必要开销。Sari R F，Syarif A 等人［12］在AODV 协议基础上，提出了检测单向链路故障的路由协议AODV－UU，这是一种按需距离矢量路由协议对单向链路状态更新的方法来标记单向链路并避免使用，尽管它有高的交付率，但该方法降低网络的连通性，若拓扑结构变化快，该协议的效率非常低。

针对传统算法存在的能耗瓶颈问题，本文提出了一种基于Hello 报文结合苯环网络模型的故障检测(ALFD－H)算法。该算法巧妙地利用苯环网络模型来完成故障检测，尽量避免节点重新寻路，避免了洪范性发送Hello 报文，从而减少网络开销和负载。

1 网络模型

ALFD－H 算法的网络模型是将WSNs 分成若干个苯环结构，以苯环为单位进行故障检测，苯环中心节点负责对苯环内成员节点之间的单向链路进行检测并与其它中心节点共享故障信息。该思想是受到化学中的苯环结构的启发［13］。化学中，在一个苯环结构上面可以衍生出很多种物质，苯环结构同样可以很好地应用于网络中，提高网络的可扩展性。

苯环的化学结构中，如图1 所示，每个C 原子上都含有一个双键，C 原子的另外两个共价键分别链接另一个C 原子和H 原子，构成了一个稳定的化学结构。针对ALFD－H的网络模型，一个苯环结构内的各节点之间构成一个邻居网络，同时节点也可与其他苯环进行通信，多个这样的苯环结构定能组成一个较大规模的网络。根据苯环的特性，节点之间的通信应置为两条，一条为单向链路故障的心跳检测通道;另一条通道是正常数据信道。本文通过对苯环结构进行改进，实现苯环中心节点管理苯环子节点从而减少了邻居节点的数目和广播通信次数从而降低了通信能耗。苯环中间加一个特别节点，即中心节点，数据处理能力和通信能力较强。图1 所示，C，H 分别表示不同的元素，可表示具有不同能力的节点。C 原子的四个共价键可如图2 进行分配:心跳检测、正常通信、邻居节点、中心节点或者其他网络中的节点，这样就可以构成较大的网络规模，保证了网络的可扩展性。

在这种网络模型中单向链路故障可以概括为三方面的原因:1)如图3 所示，当节点A 和节点B 相互覆盖对方时，此时两个节点的连通状态是双向的，即A↔B;当节点A 或者是节点B 背向对方移动，dAB大于了节点B(A)的最大传输半径dmax时，就成了单向链路A→B。2)如图4 所示，节点B 随着自身能量的消耗不能覆盖节点A，节点A 仍能覆盖节点B 时，节点A，B 之间的链路就成了单向链路。3)如图5所示，外界环境的干扰导致节点A 仍然能够覆盖节点B，但节点B 却不可以覆盖节点A，产生单向链路故障。

图1 苯环结构Fig 1 Benzene ring structure

图2 苯环网络模型Fig 2 Network model of benzene ring

图3 节点移动导致单向链路Fig 3 Unidirectional link caused by node moving

图4 能量消耗引起单向链路Fig 4 Unidirectional link caused by energy consumption

图5 环境干扰导致单向链路Fig 5 Unidirectional link caused by environmental interference

2 ALFD－H 算法

2.1 ALFD－H 算法检测过程分析

ALFD－H 算法充分利用苯环区域自治的特点进行故障检测。苯环中心节点周期性地广播Hello 报文，该苯环的子节点接收到Hello 报文后会检测与邻居节点的链路是否故障，如果没有收到反馈消息就认为邻居节点与自己可能发生了单向链路故障，子节点就会把可能发生链路故障的消息发送到苯环中心节点。苯环中心节点接收到子节点发送来的故障消息，这说明两个子节点之间的链路一定存在问题，要么是链路不存在了，要么是错误地判断了链路之间的状态，要么是存在单向链路(这里假设无线传感器网络节点是完好的)。这里假设故障链路的两节点是A，B。苯环中心节点接收到故障消息后发送Hello 报文给A 并携带这样一条路经指示A→B→苯环中心节点，若苯环中心节点收到了来自B 发送的Hello 报文，则说明这条链路是单向链路，苯环中心节点将标记该链路并在通信质量要求不高时加以使用，若苯环中心节点收不到来自B 的Hello 报文，则以同样的方式检测BA 之间的链路，发送Hello 报文给B 并携带这样一条路经指示B→A→苯环中心节点，若苯环中心节点收到了来自A 发送的Hello 报文，则标记该链路为单向链路并加以利用;若同样没有收到Hello 报文，则表示A，B 间已经没有了链路，此时苯环中心节点检测A，B 两节点与苯环中心节点的链路关系，若可以构成通路，则建立连接继续使用，避免重新寻路浪费资源;若不存在链路关系，则丢弃该节点并通知其他节点以便及时组合到新的苯环中去。

2.2 ALFD-H 检测算法

定义 B:一个苯环结构;C［i］:苯环中心节点;S［i］:与苯环相连的子节点;S［j］:苯环子节点。

1)节点初始化

2)苯环故障检测

3 ALFD－H 算法性能测试和分析

本文采用NS2 平台作为仿真工具。为了构造单向链路，对拓扑结构中的节点的发射功率和接收门限做了调整。仿真实验的拓扑结构为1 000 m×1 000 m 范围，节点覆盖范围50 ～150 m，由于ALFD－H 算法主要工作是在路由建立阶段，故仿真时间设定较短，为30s。实验中每种网络规模均仿真60 次，然后求平均值。将该算法与传统算法做对比分析，从单向链路通告成功率、控制报文数和能量损耗三个方面进行比较。

1)单向链路通告成功率

单向链路通告成功率是指单向链路故障被恢复为双向链路的数目占全部被发现的单向链路数目的比例。在AODV 协议中，单向链路节点的修复是靠各方面能力都比较强的源节点实现的，故而单向链路通告成功率会较高;在ALFD－H 算法中，单向链路的修复是靠苯环中心节点实现的，苯环中心节点配置需求就是通信能力和处理能力较强故而单向链路通告成功率次之;在AODV－UU 中不涉及到Hello 报文，故单向链路通告成功率较低。如图6 所示，该图表明各种算法的单向链路通告成功率随网络节点变化情况。

2)控制报文数

控制报文数指的是节点链路状态通告报文和路由建立的消息报文的总数。AODV－UU 算法的控制报文数相对较少，主要是采用泛洪来解决单向链路;ALFD－H 算法在链路通告期间对控制报文的TTL 做了限制(TTL 最大为3)。而传统的AODV 中的Hello 报文数目相对较多。图7 显示了各个算法在不同网络节点的情况下，控制报文的数量的变化。

图6 单向链路通告成功率Fig 6 Notice success rate of unidirectional links

图7 报文控制数Fig 7 Number of packets control

3)能量消耗

AODV 邻居单向链路检测通过向邻居广播消息来查询是否存在单向链路，广播消息耗费能量较大;而ALFD－H 算法中是通过一组邻居节点和中心节点协作完成的，故消耗的能量较小;在AODV－UU 中，没有涉及到Hello 报文的广播故而能量消耗是这三种算法中最少的。图8 表明了各个算法随着时间的延长，各自能量剩余的百分比变化情况。

图8 能量消耗随时间的变化Fig 8 Energy consumption vs time change

仿真结果表明:本文提出的ALFD－H 算法极大程度地降低了通信过程电能和资源的消耗。

4 结束语

本文基于苯环的对称结构与Hello 报文检测机制，设计出了一种ALFD－H 算法。该算法具有能耗小、可扩展性高等优点，能够有效地在WSNs 中检测单向链路。当有单向链路存在时，ALFD－H 算法能够尽量避免节点重新寻路，从而降低能量消耗，并提高了单向链路通告成功率。下一步的重点倾向于该实际应用是否仍具有较低的能耗和探测准确度，在实现故障有效检测的基础上，对于单向链路利用的研究也是需要进一步考虑的。

［1］ Valera A，Tan H P.Analysis of Hello－based link failure detection in wireless Ad Hoc networks［C］∥2012 IEEE 23rd International Symposium on Personal Indoor and Mobile Radio Communications(PIMRC)，IEEE，2012:669－674.

［2］ Jun T，Roy N，Julien C.Modeling delivery delay for flooding in mobile Ad Hoc networks［C］∥2010 IEEE International Conference on Communications(ICC)，2010.

［3］ Yamada K，Umebayashi K，Kamiya Y，et al.A study on routing protocol suitable for directional links［C］∥2010 IEEE Radio and Wireless Symposium(RWS)，IEEE，2010:328－331.

［4］ 龙昭华，陈丹丹，蒋贵全.无线传感器网络分簇拓扑控制算法［J］.传感器与微系统，2014，33(3):143－145.

［5］ Tang Y，Li X，Yang M.Improvement of multicast routing supporting mobile Ad Hoc networks with unidirectional links［C］∥2011 6th International Conference on Pervasive Computing and Applications(ICPCA)，IEEE，2011:502－508.

［6］ Su Bo，Pei Changxing，Tang Jun.Improved capacity scaling of wireless Ad Hoc networks［J］.China Communications，2010，7(5):183－188.

［7］ Cambruzzi E，Farines J，Macedo R J，et al.An adaptive failure detection system for vehicular Ad Hoc networks［C］∥2010 IEEE Intelligent Vehicles(IV)Symposium，IEEE，2010:603－608.

［8］ Zuhairi M，Zafar H，Harle D.On－demand routing with unidirectional link using path loss estimation technique［C］∥2012 Wireless Telecommunications Symposium(WTS)，IEEE，2012:1－7.

［9］ Chaturvedi A，Tiwari D，Bhadoria R S，et al.Route discovery protocol for optimizing the power consumption in wireless Ad Hoc network［C］∥2013 International Conference on Communication Systems and Network Technologies(CSNT)，IEEE，2013:290－294.

［10］Ayash M，Mikki M，Yim K.Improved AODV routing protocol to cope with high overhead in high mobility MANETs［C］∥2012 Sixth International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing(IMIS)，IEEE，2012:244－251.

［11］Yu X H，Ouyang Y U.A link－state－aware Ad Hoc on－demand distance vector(AODV)routing protocol for mobile Ad Hoc networks［C］∥2006 International Conference on Communication Technology，ICCT’06，IEEE，2006:1－4.

［12］Sari R F，Syarif A，Ramli K，et al.Performance evaluation AODV routing protocol on Ad Hoc hybrid network testbed using PDAs［C］∥2005 13th IEEE International Conference on Networks，2005 Jointly held with the 2005 IEEE 7th Malaysia International Conference on Communication:256－261.

［13］马甲林，邵 清.一种基于苯环结构的WSNs 故障检测算法［J］.传感器与微系统，2013，32(11):125－127.