基于UAV动态特性限制的WSN分簇路由方法研究

张珊珊 孟庆奎 王玲

摘 要： 本文针对目前的WSN分簇算法研究中没有考虑到UAV动态特性，导致UAV采集信息过程中飞行距离过长、采集难度大的问题，提出了基于UAV动态特性限制的WSN分簇路由方法（CR）。CR算法首先考虑到UAV飞行中与簇头通信时间较短的情况，控制了成簇的大小，能够保证UAV访问过簇头节点后可以完全采集该簇信息；第二，簇头选择阶段在兼顾簇内节点能量消耗一致的同时，对簇头进行调整，使得簇头选择方案更利于UAV采集，减少UAV绕行距离；第三，考虑到了UAV可供飞行能量的局限性，在分簇的同时加入总飞行能量的限制，使得规划方案在可行的前提下执行。实验表明，CR算法能够有效地减少节点能量消耗差异，使得网络节点剩余能量趋于一致，延长了网络生存时间。

关键词： UAV-WSN；分簇路由；动态特性限制；网络生存时间

Abstract：Since the existing researches of clustering routing method in UAV-WSN system has not considered the UAV kinetic constraints when it collects information from WSN UAV is required to take longer flight distance and overcome more difficulties in information collection. In this paper a WSN clustering routing method （CR） is proposed to solve the above problem based on UAV kinetic constraints. Firstly CR algorithm controls the size of the clusters to ensure the full information collection due to the short time period for UAV to communicate with CHs during its flight；secondly CR adjusts CH selection to make it favorable for UAV to collect information taking into account the energy consumption uniformity of each cluster；thirdly CR is practicable as considering the limited energy for UAV flight. Experimental results show that CR can effectively reduce residual energy consumption level difference of nodes so as to prolong the lifetime of WSN.

Key words： UAV-WSN；clustering routing；UAV kinetic constraints；lifetime of WSN

引言

UAV-WSN系统因为具有抗毁性强、安全易布设、成本低廉等特点，目前受到各界广泛关注[1-3]。文献[4-11]分别根据UAV移动速度较快等特点设计了平面结构的UAV-WSN系统的通信协议。然而分簇结构的WSN在节约网络能量、拓扑管理、网络可扩展性、大规模网络等方面均优于平面结构[12]。因此，越来越多的研究已着重围绕着分簇结构的WSN而探讨展开，且取得了一定的技术成果。

Sujit等人[13]提出了以节点通信距离为基础对各节点进行分簇，通过TSP问题连接各簇，根据各簇的数据量，结合UAV的动态特性对UAV的飞行路线进行调整，使得在实际运用时能够采集到信息并确保信息采集完全。但面临问题是：分簇时采取了通用的分簇方案，导致UAV的采集过程中将在信息量大的簇上方停留时间过长，延长了UAV飞行时间。

Ho等人用粒子算法 （Particle Swarm Optimization PSO）优化了簇头产生方法，提出通过利用Bellman-Ford 算法确定中继点，设定UAV只有飞过簇头正上方时才能与其通信，以确保最好的信道质量[14]。继而在后续的研究中分析得到可基于确定的优化路径，设计决定节点与UAV直接通信或通过中继节点通信[15]。该方案有效地减少了UAV飛行时间，同时也因为启用了尽可能多的节点与UAV直接通信，减轻了中继节点的通信负担，提高了网络能量消耗的均衡性。

已有的分簇算法没有考虑到UAV的动态特性限制，因此容易出现UAV偏离预设位置，或者按照规划的访问顺序需要长距离绕行的情况；而对UAV路径规划的研究中，只是关注在已有的网络拓扑中进行规划，则并未呈现最佳的优化程度。

为此，本文将提出一种基于UAV的动态特性限制的WSN分簇路由算法（CR），根据节点信息量和UAV通信能力确定簇的大小，同时使得簇头选举能够符合UAV飞行特点，达到提高网络能量消耗一致性，延长网络生存时间的目标。实验表明，CR算法在满足UAV动态特性限制和UAV最大飞行能量限制的前提下，能够使得网络能量消耗趋于一致，延长了网络生存时间。

1 问题描述

1.1 UAV-WSN系统模型

如图1所示，在分簇结构的WSN中 WSN网络被分为若干个相邻的簇，通信分为2个层次。其中，低层通信是指节点与簇头之间的通信，主要包括节点间发送控制信息，簇内节点（Cluster Member，CM）向簇头（Cluster Head，CH）节点发送数据等；高层通信是指簇头与UAV之间的通信，主要包括簇头与UAV之间发送控制信息和簇头节点向UAV发送本簇的感知数据。本文假设UAV在同一水平面匀速飞行，同时为减少簇头节点的通信能量消耗，仅在UAV飞行至簇头正上方时对簇头信息进行采集。

1.2 概念定义

由于在飞行过程中受到飞机最大法向过载、飞行速度、升致阻力等影响，UAV在曲线飞行时生成的路线曲率不能超过一个定值，UAV飞行限制的设计定义如下。

定义1 最小转弯半径 当飞机以一定速度在同一水平面匀速飞行时，方向舵旋转到极限位置，飞机重心点在该飞行水平面上走过的轨迹圆的半径。分析可知，这与飞机飞行速度有关，表征了飞机通过狭窄弯曲地带或绕过障碍物的能力。相同速度时，最小转弯半径越小的飞机性能越好。

定义2 飞行角度 UAV在同一水平面上飞行，在该水平面以其飞行起点为圆心，正东为x轴正方向建立飞行坐标系，其飞行方向与x轴正方向顺时针方向的夹角为UAV当前飞行方向。

定义3 可达区域 指UAV在当前位置，以一定角度在同一水平面，匀速飞行时，不需要绕行而可以直接到达的区域。如图2所示，当飞机在i点以箭头方向匀速飞行时，就会在i点形成2个与飞行方向相切的以最小转弯半径为半径的虚拟的圆形区域，在这2个圆形区域以内为不可达区域，以外的区域称为可达区域。

1.3 限制条件

（1）UAV动态特性： 当UAV需要采集的下一个传感器节点在当前位置的不可达区域内，则UAV无法按照路径规划中的优化路径采集信息，需要绕行。

（2）UAV搭载飞行能量： 由于UAV搭载的可供飞行能量有限，当飞行任务消耗能量大于其搭载的可供飞行最大能量时，这种情况下飞机将无法飞抵终点，从而导致任务失败。即UAV飞行能量消耗应满足式（1），具体如下：

该方法在保证UAV能够完成采集任务飞回终点的同时，尽可能多地采集信息，同时可以提高能量消耗的一致性，延长网络生存时间。

3 仿真分析

3.1 场景和参数设置

为了验证本文提出的CR算法的性能，研究中将200个无线传感器节点随机放置在200 m×200 m的正方形区域中，并利用Matlab仿真工具进行了仿真实验并与LEACH算法在能量和网络生存时间方面进行了比较和分析。仿真参数的选取设置可详见表1。

3.2 仿真结果与分析

3.2.1 路径优化情况

LEACH Path 为 UAV 按照 LEACH 算法分簇方案进行信息采集需要飞行的路径长度；Original Path of CR、 Final Path of CR 分别代表UAV 对本文提出的 CR 算法生成的簇进行信息采集需要飞行的最初路径长度以及经过第四阶段簇头调整后产生的路径长度。Dlimit指每次测试中UAV能够飞行的最大路径长度。这里，研究给出了10 次仿真实验得到的计算结果平均值可见表2。

在生成簇头和簇结构后，CR算法经过簇头调整阶段与最初生成的路径相比，3种参数条件下分别优化了21.3%、25.9%、16.7%。与LEACH算法相比，路径平均长度分别减少了23.1%、24.6%、13.4%。这是因为CR簇头调整阶段使得簇头分布更符合UAV的动态特性限制，确保可以完成预定任务。

3.2.2 网络节点能量差别

为验证CR算法与LEACH算法在能量消耗方面的过程效果，本文通过每次轮循过后得到网络节点最低能量和网络节点能量差异来进行研究分析，内容探讨展示如下。

3.2.2.1 网络节点最低能量

研究可得，网络节点最低能量的数值对比可如图3所示。分析图3结果可知，CR算法在设计时考虑了簇的规模，使得每个簇的节点数不超过20个，这样能确保UAV充分采集各簇信息，同时簇头的负载不会过大；而LEACH算法的成簇却是由节点选择距离自身最近的簇头加入该簇，使得簇的大小并不平均。因此，在均衡簇頭能量负荷方面，CR算法将优于LEACH算法。

3.2.2.2 网络节点能量差别

图4提供了在10次轮循中节点能量差别（△E=max∣Ei-Eaverage∣）的变化曲线。

从图4中可以看出，CR算法得到的△E一直低于LEACH算法。这是由于CR算法是根据提高网络能量消耗一致性来选择和调整簇头，如此即使较高能量的簇头承担了更多负载来缩小节点能量差别。

3.2.3 信息采集率

如图5所示，CR算法和LEACH算法的信息采集率分别为70%和28%。分析其原因机理可知：在CR算法中，为了能够实现UAV对节点信息的完全采集，对簇的大小了进行了限制。因此当规划的UAV飞行路径长度小于UAV最大航程时，UAV能够完成信息采集任务。而在第3、5、8次测试中，UAV采集的信息量却较低，这是因为采集全部信息所需路程超出了UAV的最大航程，为了满足UAV航行能量限制，就需要放弃采集过程中的一些簇头信息。

LEACH算法中，在成簇时各节点会选择与自己最近的簇头节点并加入该簇，而未能考虑到簇的规模，这就致使UAV飞过簇内成员较多的簇头时，对其信息无法达到完全采集，从而降低了信息采集率。图5中2、5、6、7、9、10次测试中，LEACH采集信息为0，这是因为LEACH产生的簇头使得UAV实际飞行距离过长，而算法又并未针对这种情况设计处理策略，则使得UAV访问途中即已耗尽飞行能量而无法飞回终点，导致任务失败。而在1、3、4、8次测试中，即使LEACH算法在生成簇头基础上的路径长度均处在UAV的可达范围内，但却由于个别簇的规模过大，导致UAV仍然无法对其做到完全采集，从而最终影响了信息采集率。

综上分析可以得知，相较于LEACH算法，CR算法能够优化簇头的选取，使得UAV的采集路径长度一直保持在其最大直飞距离之内，从而确保任务的高效完成；而在两种方法都可行的情况下，CR算法也仍能获得更高的信息采集率。

3.2.4 网络生存时间

进一步研究得到，网络生存时间的数值曲线对比如图6所示。从图6中可以看出，CR算法的网络生存时间比LEACH算法高出了37%。LEACH算法与CR算法相比，第一个死亡节点出现较早，且CR算法在出现第一个死亡节点后曲线即急速下降。这是由于CR算法中节点的剩余能量分配均衡，第一个死亡节点出现时，其它节点的剩余能量也很低。而LEACH算法中，节点的剩余能量并不平均，因此在出现第一个死亡节点后，网络中仍存在剩余能量较高的节点。

4 結束语

为了使得WSN分簇符合UAV动态特性限制的特点，本文设计提出了基于UAV动态特性限制的WSN分簇路由方法—CR算法。本次研究取得的重要成果可表述如下：

首先，CR算法在簇的划分阶段，考虑到UAV飞行时对簇头采集数据的通信时间较短的情况，控制了成簇的大小，能够保证UAV访问过该簇头节点后可以完全采集到该簇的信息；

其次，簇头选择阶段在兼顾簇内能量消耗一致的同时，对簇头进行调整，使得簇头选择方案更利于UAV采集，减少UAV绕行距离；

最后，考虑到了UAV可供飞行能量的局限性，在分簇的同时加入总飞行能量的限制，使得规划方案具备了客观可行性。

实验表明，CR算法能量能够使得WSN节点能量消耗趋于一致，延长了网络生存时间。

参考文献

[1] COBANO J MARTNEZ-DE DIOS J R CONDE R et al. Data retrieving from heterogeneous wireless sensor network nodes using UAVs[J]. Journal of Intelligent & Robotic Systems 2010 60（1）：133-151.

[2] SONG Wenzhan HUANG Renjie XU M et al. Design and deployment of sensor network for real-Time high-delity volcano monitoring[J]. IEEE Transactions on Parallel and Distributed Systems 2010 21（11）：1658-1674.

[3] CORKE P HRABAR S PETERSON R et al. Autonomous deployment and repair of a sensor network using an unmanned aerial vehicle[C]//Proc. of the IEEE International Conference on Robotics and Automation. New Orleans LA USA：IEEE 2004：3602-3608.

[4] DE FREITAS E P HEIMFARTH T NETTO I F et al. UAV relay network to support WSN connectivity[C]// 2010 International Congress on the Ultra Modern Telecommunications and Control Systems and Workshops （ICUMT）. Moscow Russia： IEEE，2010：309-314.

[5] OLIVEIRA H A BARRETO R S FONTO A L et al. A novel greedy forward algorithm for routing data toward a high speed sink in wireless sensor networks [C]//proceedings of the Computer Communications and Networks （ICCCN） 2010 Proceedings of 19th International Conference on.Zurich Switzerland： IEEE，2010：1-7.

[6] HO T D PARK J SHIMAMOTO S. QoS constraint with prioritized frame selection CDMA MAC protocol for WSN employing UAV[C]// IEEE Globecom 2010 Workshops on Wireless Networking for Unmanned Aerial Vehicles （GC Wkshps）. Miami FL：IEEE 2010：1826-1830.

[7] HO T D PARK J SHIMAMOTO S. Novel multiple access scheme for wireless sensor network employing unmanned aerial vehicle[C]//2010 IEEE/AIAA 29th the Digital Avionics Systems Conference （DASC） . Salt Lake City UT USA： IEEE，2010：5.C.5（1）-5.C.5（8）.

[8] HO D T SHIMAMOTO S. Highly reliable communication protocol for WSN-UAV system employing TDMA and PFS scheme[C]//2011 IEEE Globecom Workshops （GC Wkshps）. Houston TX：IEEE 2011：1320-1324.

[9] HO D T PARK J SHIMAMOTO S. Performance evaluation of the PFSC based mac protocol for WSN employing UAV in rician fading[C]// 2011 IEEE Wireless Communications and Networking Conference （WCNC）. Cancun Quintana Roo Mexico：IEEE，2011：55-60.

[10]SOTHEARA S AOMI N ANDO T et al. Effective data gathering protocol in WSN-UAV employing priority-based contention window adjustment scheme [C]//proceedings of the Globecom Workshops （GC Wkshps）. Austin TX USA：IEEE，2014：1475-1480.

[11]LI Hanshang WANG Ling PANG Shuo et al. A cross-layer design for data collecting of the UAV-wireless sensor network system[C]//2014 12th IEEE International Conference on Embedded and Ubiquitous Computing （EUC） . Milano Italy：IEEE，2014：242-249.

[12]EMAMZADE A N HEIDARI M NAJI H R. A study on the effect of applying clustering on sink movement for data gathering in wireless sensor networks[C]//2012 2nd International Conference on Computer and Knowledge Engineering （ICCKE）. Mashhad Iran：IEEE 2012：266-271.

[13]SUJIT P B LUCANI D E SOUSA J B. Joint route planning for UAV and sensor network for data retrieval[C]// proceedings of the Systems Conference （SysCon） 2013 IEEE International. Orlando FL：IEEE，2013：688-692.

[14]HO D T GRTLI E I SUJIT P B et al. Cluster-based communication topology selection and UAV path planning in wireless sensor networks [C]//2013 International Conference on the Unmanned Aircraft Systems （ICUAS）. Atlanta GA：IEEE，2013：59-68.

[15]HO DT GRTLI E I SUJIT P B et al. Performance evaluation of cooperative relay and particle swarm optimization path planning for UAV and wireless sensor network [C]//2013 IEEE Globecom Workshops （GC Wkshps）. Atlanta GA USA： IEEE，2013：1403-1408.

[16]DUBINS L E. On plane curves with curvature [J]. Pacific Journal of Mathematics，1961，11（2）： 471-481.