无线传感器网络中的分布式动态路径规划算法*

贾思强，高 翔，陆起涌，2*

(1.复旦大学电子工程系，上海，200433;2.复旦大学无锡研究院，江苏无锡，214131)

将无线传感器网络技术与移动机器人技术相结合，既增强移动机器人的感知能力，也提高了传感器网络对环境的控制力［1］。WSN通过无线通信及协作处理，为移动主体提供当前环境下的优化路径，实现快速安全的导航，对于灾害逃生，及时救援和未知环境探测等具有重要意义。无线传感器节点通常受限于自身电量，因而需降低消息收发的频率，另一方面，被监控环境会随时间不断变化，计算最优路径需要大部分无线传感器节点的协同处理，因此如何平衡通信代价和最优路径，使算法能够具有良好的动态性能，是学者们研究的焦点。

基于无线传感器网络的动态路径规划算法可分为集中式和分布式。集中式算法［2－4］通过无线传感器网络将数据汇集到处理中心，算法利用全局信息(一般包括地图信息)计算得到全局最优路径。集中式算法由于其较高的系统要求和网络信息汇集延时，其适用场景受到限制，一般在紧急情况［2－3］和高复杂度环境［4］中采用。利用分布式算法进行路径规划在系统代价和扩展性方面具有优势。目前分布式算法主要集中在梯度势场算法［5－12］和路标算法［13－16］。梯度势场算法［5－9］通常以危险区域到各节点的跳数来构造梯度势场，对如何适应环境的动态变化考虑较少。文献［5］以各危险节点跳数平方的倒数和作为当前节点的势场值，通过最小生成树算法计算出优化路径，文献［8］进一步改进了梯度公式并对复杂场景做了分析，但其对危险事件变化和局部最小值的处理会耗费大量通信代价。为了增强动态性，文献［9］提出对于已计算出的优化路径主干进行较频繁的监测，相对降低其他区域的监测频率，从而减少网络消息收发数量。文献［10］提出了以跳数为单位预测危险区域的变化范围，文献［11］从最小暴露概率的角度建立梯度势场，两者在适用性方面均有不足。文献［12］通过引入射频接收信号强度RSS(Received Signal Strength)构造伪梯度函数，但未考虑环境因素。路标算法［13－16］借助环境地图信息以不同机制在网络中选取路标节点，网络消息在这些路标节点通路间传播。基本的路径规划和动态调整算法被限制在路标网络上或被查询区域内，从而以路径长度的增加为代价降低了消息数量。文献［17］和［18］结合地理位置和环境信息规划路径。文献［18］改进分布式的有向无环图DAG(Directed Acyclic Graph)算法，使节点利用局部信息进行动态调整和路径规划，在降低消息数量方面取得了较好的效果，但对于状态恢复节点没有针对性的路径修复。

本文受文献［12］和［18］的思想启发，在不借助WSN位置信息的前提下，针对梯度势场算法在动态调整方面的不足，综合考虑规划路径长度和安全性，以及动态调整时的通信开销，结合环境因素构造梯度势场函数，提出了一种分布式动态路径规划算法，并对该算法进行了分析，扩展和仿真比较。

1 问题描述

1.1 问题前提

WSN被随机散布在监控区域内，系统不借助任何地理位置信息。移动主体可能在该区域的任何位置请求被引导到任意目标节点。当一个危险事件发生时，其附近的无线传感器节点能够感知到该危险事件的发生和周围环境的变化。每个节点读取传感器数据，与已设定的阈值比较，将自身标记为安全或危险。系统可以设定多个阈值，以分级标定节点的当前状态。一个危险事件可能发生扩散，移动或者消减。在危险区域变化的过程中，原来受到影响的危险节点可能重新改变状态，恢复为安全节点。一条安全路径的定义，对于安全节点来说是该路径沿途不经过危险节点;对于危险节点来说是该路径可以尽快逃离危险区域并到达目标节点。本文定义一条路径的长度是其相连的每个节点间距离的总和。移动主体可以无线通信方式逐个经过路径节点，最终被引导到目标节点。

1.2 算法目标

基于以上前提，本文算法的目标是为每一个节点提供一条到达目标节点的优化路径，该路径是确保安全和尽可能快速的。同时，随着危险事件的变化，网络能够通过较低的通信代价来实现动态路径规划。

2 路径规划算法

2.1 梯度势场函数构造

考虑到RSS在一定程度上能够反映两节点间距离的远近和链路质量［19］，本文如文献［12］在梯度势场函数中引入RSS，以进一步优化路径长度。本文构建的梯度势场是从目标节点扩散至末端节点，因此该梯度势场函数与RSS成正比，而与跳数成反比。同时，梯度势场函数应与环境的危险程度成反比，使安全节点不会选取危险节点作为父节点而引导移动主体进入危险区域。基于以上考虑，可构造梯度势场函数如式(1)。式中，pseu_和RSS分别代表当前节点i收到的上一跳节点发送的梯度势场值和接收信号强度，RSS需进行归一化处理，Hop-Count为上一跳节点的跳数加与当前节点传感器的数值相关，当节点安全时其值为1，当节点处于危险状态时取小于1大于0的数值。

目标节点梯度势场值为最大值pseu_gMAX。由于对跳数的不同处理，本文梯度势场随跳数的下降速度比文献［12］中的慢，更有利于远距离节点梯度势场值的区分。对于的处理事实上可以多样化，在后文中将继续讨论，这里暂且将所有危险状态节点的定为同一值。

2.2 算法描述

2.2.1 梯度势场建立

梯度势场算法通常以CSMA(Carrier Sense Multiple Access)的方式进行定向泛洪，传播效率低。本文结合式(1)对该过程做相应改进，当父节点广播梯度消息后，其临近的子节点中RSS强的应较先广播。因此，本文设计每个节点在初次收到上一跳节点消息后，做如式(2)计算的延时，在延时结束后进入CSMA模式广播。式中，d为网络节点的平均邻居节点数，Δdelay为一个梯度消息的发送时间。

网络梯度势场的建立过程如下:

步骤1 目标节点自身跳数为0，梯度势场为最大值，其他节点跳数设为无穷，梯度势场值为0;

步骤2 节点监听来自邻居节点的路由消息，包括跳数，接收信号强度，梯度势场值和传感器数据;

步骤3 节点接收到邻居节点的梯度消息后，设定延时时间，判断邻居节点当前状态;

步骤4 如邻居处于安全状态，则通过式(1)计算出相应的势场值，如该值大于自身当前势场值，则将邻居节点记录为父节点，将自身更新的梯度信息打包发送;特别地，对于当前状态为危险的节点，且自身从未收到过来自安全节点的梯度消息，则将邻居节点记录为父节点，并将自身更新打包发送梯度消息;

步骤5 如邻居处于危险状态，则只有在从未接收到来自安全节点的梯度消息且计算得势场值大于当前势场值时，记录父节点并打包发送梯度消息，否则抛弃来自危险节点的梯度消息;

步骤6 该过程结束后，各节点建立起各自的邻居信息表，最终确定的父节点为使自身梯度势场值最高或最安全的邻居节点。

2.2.2 动态调整

当监控环境出现变化时，为实现算法目标，网络需要维持其自身的梯度趋势，即每个节点的父节点梯度势场值必须大于自身节点。为了有效降低通信代价，算法仅在危险区域造成网络梯度无法维持时进行必要的通信。网络的动态调整算法如下:

步骤1 各节点读取自身传感器数值，确定当前状态，如与之前相比发生状态变化，则根据当前的邻居信息表通过式(1)计算出当前最高梯度势场值，记录父节点并打包梯度信息进行广播;

步骤2 邻居节点接收到梯度消息后更新自身邻居信息表，根据邻居信息通过式(1)计算出更新的最高梯度势场值P;

步骤3 对于当前状态为安全的节点，如果该势场值P较当前势场值下降，则查找邻居表中梯度势场值最大的安全邻居，如其势场值大于自身当前势场值，则不进行广播，维持当前势场值，否则记录父节点并打包梯度信息进行广播;

步骤4 对于当前状态为危险的节点，如果该势场值P较当前势场值下降，则判断该势场值是否小于原邻居势场值中比当前势场值低的最大梯度势场值，如大于则不进行广播，维持当前势场值，否则记录父节点并打包梯度信息进行广播;

步骤5 对于所有节点，如果该势场值P较当前势场值上升，则判断相应邻居节点是否为当前父节点，如不一致，则记录父节点并打包梯度信息进行广播。

2.3 算法分析

在梯度势场建立的过程中，每个节点选取最高梯度势场值并确定父节点，由式(1)的性质，其父节点势场值必高于子节点，因而每条路径的最高势场值最终都将收敛于pseu_gMAX处，即目标节点处。不妨反证假设存在局部梯度势场最高区域，如该区域收敛到一个最大梯度势场节点，则该节点没有父节点，与算法的问题前提相悖，而根据本文算法，该局部区域节点将相互进行多次梯度传播和更新，直至该区域节点势场值降到满足条件选取区域外节点为路径父节点。

算法对于危险区域节点的处理方式较为严格，主要目的是使危险区域内的移动主体能够尽快脱离危险区域，同时兼顾到达目标节点的路径长度，这之间的权衡关系通过来调节。在动态调整过程中，最宽松的要求是每个节点存在一个比自身梯度势场高的父节点，此限制条件如前文的分析思路一样可得出其最终收敛于pseu_gMAX的结论。

每个节点对于梯度势场的分布式计算和调整需要根据各邻居梯度消息进行如式(1)的计算，其运算复杂度为O(Δ)，Δ为邻居节点数，然后进行排序运算，其复杂度一般为 O(Δ2)或O(Δlog2Δ)。

2.4 算法扩展

对于该算法的扩展可以有两个方面。一方面，前文中将所有危险区域内节点的环境因子设定为同一值，即所有超过阈值的无线传感器节点采用相同的权值。事实上，环境因子可以根据节点的传感数值进行细化，从而根据实际情况进一步设计出合理的路径规划策略。另一方面，本文算法可适用于前文所述的路标算法上，在无线传感器网络选取了合适路标节点子集后，可通过本文算法在路标节点与目标节点之间规划路径，算法的动态调整策略同样适用于路标节点受到危险事件影响的情况。

3 仿真与结果分析

3.1 仿真搭建

本文利用CC2430无线模块模型在OMNET++4.1平台进行仿真。实验设计在500 m×500 m的平面空间里随机散布若干节点，设定节点的稳定通信距离为50 m，目标节点坐标为(450 m，450 m)，最大梯度势场值为50 000，环境因子设定为 0.4。实验模拟危险事件最初以坐标(175 m，325 m)为圆心，50 m为半径存在于此空间内，而后扩散为半径75 m的圆形区域，最后以此形状转移至以坐标(200 m，300 m)为圆心。这里首先给出示例图1，呈现一个WSN在3种情况下的网络拓扑变化，其中处于危险状态的节点选择尽快逃离危险区域的路径，同时兼顾选择离目标节点较近的邻居为父节点。在环境变化先后，安全状态节点动态调整各自的路径避开危险区域，从三幅图的对比可发现，这种路径的变化仅发生在危险事件附近局部区域。

图1 模拟环境变化先后WSN拓扑仿真示例图

尽管文献［18］算法(下文简称“DAG算法”)借助了位置信息，但考虑到本文算法与其在目标和策略上的相近性，这里将其纳为参考对象进行比较。

3.2 路径长度

作为路径规划的首要目标，实验在路径长度方面将本文算法与DAG算法和文献［8］算法(下文简称“Tseng算法”)对比。在初始状态下，比较所有节点的路径平均长度，图2表明了本文算法在路径长度上的优势。在危险区域扩散和转移的情况下，为了突出算法的动态性能，本文选取在环境变化先后路径受到影响的节点在平均长度上做比较，同样可以看到本文算法的优势。相比于DAG算法这种优势在危险区域转移时稍有增加，原因是本文算法在路径恢复处理方面对规划路径长度的要求更高。

3.3 路径安全性

本文以WSN中所有节点路径途经危险区域的总次数作为路径安全性指标来进行比较。经仿真验证，三种算法都使安全区节点路径有效避开危险区域，该指标实际考察了各算法对于危险区域内节点脱离危险的路径规划能力。从图3中可看出，本文算法与DAG算法在途经次数上几乎一样，仅在节点较少时差距相对明显。分析认为，DAG算法借助位置信息仅考虑节点如何最快脱离危险区域，而不兼顾其脱离后到达目标节点的路径长度。图4是在网络含300个节点时将不同的情况做比较，事实上通过减小环境因子，本文算法将达到与DAG算法一致的处理策略和效果。

图2 模拟环境变化先后WSN内节点路径长度对比

3.4 动态调整通信代价

本文以动态调整过程中节点间消息收发的总数作为通信代价的衡量标准。对比仿真中不再与泛洪形式的梯度势场算法相比较，而是与一般的以广度优先遍历(BFS)泛洪WSN并在泛洪结束后即可规划路径的算法相对比。模拟实验中放置400个节点，图5(a)模拟危险区域从半径30 m依次扩散至50 m到80 m，图5(b)模拟半径75 m的危险区域向东南方向以每周期依次移动20 m到50 m。从图5中可看出，本文算法相较于BFS泛洪方法优势明显，而与泛洪形式的梯度势场算法对比则将效果更优。与DAG算法相比，两者的消息数量在危险区域扩散和移动实验中分别最大相差16和33，从绝对值来看并不大。经分析，这样的差距主要由于本文算法中的动态调整并不仅限于状态发生变化的节点，对其附近及后续节点做出更好的路径规划亦有作用，因而相对增加了通信开销。

图3 模拟环境变化先后WSN内节点途经危险区域次数对比

图4 对路径安全性的影响

综上，本文算法在规划路径长度和安全性方面具有一定优势;相比Tseng算法，本文算法可显著降低动态调整时的通信开销;相比DAG算法，本文算法可在不借助位置信息条件下，以相近的通信开销动态处理路径规划，且路径自恢复效果更好。

图5 WSN动态调整路径规划的通信代价对比

4 结论

本文针对梯度势场算法在动态调整方面的不足，综合考虑规划路径长度，路径安全性和通信代价，结合环境因素构造梯度势场函数，提出了一种分布式动态路径规划算法，在环境变化时各节点依据局部信息动态调整网络梯度势场，为每个节点提供优化路径。仿真结果显示了本文算法在WSN受到危险区域变化影响的情况下，能够规划出较短路径，有效降低通信代价并可灵活处理路径安全性。算法不借助WSN地理位置信息，相对简捷易实现，可进一步研究将其与路标算法相结合，利于大规模WSN中路径规划性能的提升。

［1］ 薛晗，李迅，马宏绪.基于无线传感器网络的移动机器人智能导航算法［J］.传感技术学报，2008，21(5):834－840.

［2］ Li S，Zhan A，Wu X，et al.ERN:Emergence Rescue Navigation with Wireless Sensor Networks［C］//15th International Conference on Parallel and Distributed Systems(ICPADS).Shenzhen，China，2009:361－368.

［3］ Chen L W，Cheng J H，Tseng Y C，et al.LEGS:A Load-balancing Emergency Guiding System based on Wireless Sensor Networks［C］//2012 IEEE International Conference on Pervasive Computing and Communications Workshops(PERCOM Workshops).Lugano，2012:486－488.

［4］ Imen C，Anis K，Hachemi B，et al.Smart PATH:A Hybrid ACO-GA Algorithm for Robot Path Planning［C］//2012 IEEE Congress on Evolutionary Computation(CEC).Brisbane，Australia，2012:1－8.

［5］ Li Q，Rosa D M，Rus D.Distributed Algorithms for Guiding Navi-gation Across a Sensor Network［C］//Proceedings of the 9th annual International Conference on Mobile Computing and Networking.San Diego，CA，USA，2003:313－325.

［6］ Xiao Q，Xiao B，Luo J，et al.Reliable Navigation of Mobile Sensors in Wireless Sensor Networks Without Localization Service［C］//17th International Workshop on Quality of Service，IWQoS，2009.Charleston，SC，2009:1－9.

［7］ Verma A，Sawant H，Tan J.Selection and Navigation of Mobile Sensor Nodes Using a Sensor Network［C］//Proceedings of the 3rd IEEE International Conference on Pervasive Computing and Communications.Kauai Island，HI，2005:41－50.

［8］ Tseng Y C，Pan M S，Tsai Y Y.Wireless Sensor Networks for E-mergency Navigation［J］.Computer，2006，39(7):55－62.

［9］ Keith J O，Tucker R B.Distributed Path Planning for Robots in Dynamic Environments Using a Pervasive Embedded Network［C］//Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems，AAMAS 2004.New York，NY，USA，2004:1538－1539.

［10］ Wu X，Tan S，Chen T，et al.Distributed Dynamic Navigation for Sensor Networks［J］.Tsinghua Science and Technology，2011，16(6):648－656.

［11］ Ferrari S，Foderaro G.A Potential Field Approach to Finding Minimum-exposure Paths in Wireless Sensor Networks［C］//2010 IEEE International Conference on Robotics and Automation(ICRA).Anchorage，AK，USA，2010:335－341.

［12］ Deshpande N，Crant E，Henderson C.T.Experiments With a Pseudo-gradient Algorithm for Target Localization Using Wireless Sensor Networks［C］//2010 IEEE Conference on Multisensor Fusion and Integration for Intelligent Systems.Salt Lake City，UT，2010:74－79.

［13］ Alankus G，Atay N，Lu C，et al.Adaptive Embedded Roadmaps for Sensor Networks［C］//2007 IEEE International Conference on Robotics and Automation.Roma，2007:3645－3652.

［14］ Alankus G，Atay N，Lu C，et al.Spatiotemporal Query Strategies for Navigation in Dynamic Sensor Network Environments［C］//2005 IEEE/RSJ International Conference on Intelligent Robots and Systems，2005(IROS 2005).Edmonton，Alta，2005:3718－3725.

［15］ Bhattacharya S，Atay N Alankus G，et al.Roadmap Query for Sensor Network Assisted Navigation in Dynamic Environments［C］//Proceedings of the Second IEEE international conference on Distributed Computing in Sensor Systems.San Francisco，CA，2006:17－36.

［16］ Yao Z，Gupta K.Backbone-based Roadmaps for Robot Navigation in Sensor Networks［C］//2008 IEEE International Conference on Robotics and Automation，ICRA 2008.Pasadena，CA，USA，2008:1023－1029.

［17］梁华为，陈万明，李帅，等.基于无线传感器网络的移动目标导航方法［J］.传感技术学报，2007，20(7):1620－1624.

［18］ Buragohain C，Agrawal D，Suri S.Distributed in-network Path Planning for Sensor Network Navigation in Dynamic Hazardous Environments［J］.Wireless Communications and Mobile Computing，2012，12(8):739－754.

［19］ Maheshwari R，Jain S，Das S R.A Measurement Study of Interference Modeling and Scheduling in Low-power Wireless Networks［C］//Proceedings of the 6th ACM conference on Embedded network sensor systems.Raleigh，NC，USA，2008:141－154.