張珊珊 孟慶奎 王玲

摘 要： 本文針對目前的WSN分簇算法研究中沒有考慮到UAV動態(tài)特性，導致UAV采集信息過程中飛行距離過長、采集難度大的問題，提出了基于UAV動態(tài)特性限制的WSN分簇路由方法（CR）。CR算法首先考慮到UAV飛行中與簇頭通信時間較短的情況，控制了成簇的大小，能夠保證UAV訪問過簇頭節(jié)點后可以完全采集該簇信息；第二，簇頭選擇階段在兼顧簇內(nèi)節(jié)點能量消耗一致的同時，對簇頭進行調(diào)整，使得簇頭選擇方案更利于UAV采集，減少UAV繞行距離；第三，考慮到了UAV可供飛行能量的局限性，在分簇的同時加入總飛行能量的限制，使得規(guī)劃方案在可行的前提下執(zhí)行。實驗表明，CR算法能夠有效地減少節(jié)點能量消耗差異，使得網(wǎng)絡(luò)節(jié)點剩余能量趨于一致，延長了網(wǎng)絡(luò)生存時間。

關(guān)鍵詞： UAV-WSN；分簇路由；動態(tài)特性限制；網(wǎng)絡(luò)生存時間

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系統(tǒng)因為具有抗毀性強、安全易布設(shè)、成本低廉等特點，目前受到各界廣泛關(guān)注[1-3]。文獻[4-11]分別根據(jù)UAV移動速度較快等特點設(shè)計了平面結(jié)構(gòu)的UAV-WSN系統(tǒng)的通信協(xié)議。然而分簇結(jié)構(gòu)的WSN在節(jié)約網(wǎng)絡(luò)能量、拓撲管理、網(wǎng)絡(luò)可擴展性、大規(guī)模網(wǎng)絡(luò)等方面均優(yōu)于平面結(jié)構(gòu)[12]。因此，越來越多的研究已著重圍繞著分簇結(jié)構(gòu)的WSN而探討展開，且取得了一定的技術(shù)成果。

Sujit等人[13]提出了以節(jié)點通信距離為基礎(chǔ)對各節(jié)點進行分簇，通過TSP問題連接各簇，根據(jù)各簇的數(shù)據(jù)量，結(jié)合UAV的動態(tài)特性對UAV的飛行路線進行調(diào)整，使得在實際運用時能夠采集到信息并確保信息采集完全。但面臨問題是：分簇時采取了通用的分簇方案，導致UAV的采集過程中將在信息量大的簇上方停留時間過長，延長了UAV飛行時間。

Ho等人用粒子算法 （Particle Swarm Optimization PSO）優(yōu)化了簇頭產(chǎn)生方法，提出通過利用Bellman-Ford 算法確定中繼點，設(shè)定UAV只有飛過簇頭正上方時才能與其通信，以確保最好的信道質(zhì)量[14]。繼而在后續(xù)的研究中分析得到可基于確定的優(yōu)化路徑，設(shè)計決定節(jié)點與UAV直接通信或通過中繼節(jié)點通信[15]。該方案有效地減少了UAV飛行時間，同時也因為啟用了盡可能多的節(jié)點與UAV直接通信，減輕了中繼節(jié)點的通信負擔，提高了網(wǎng)絡(luò)能量消耗的均衡性。

已有的分簇算法沒有考慮到UAV的動態(tài)特性限制，因此容易出現(xiàn)UAV偏離預(yù)設(shè)位置，或者按照規(guī)劃的訪問順序需要長距離繞行的情況；而對UAV路徑規(guī)劃的研究中，只是關(guān)注在已有的網(wǎng)絡(luò)拓撲中進行規(guī)劃，則并未呈現(xiàn)最佳的優(yōu)化程度。

為此，本文將提出一種基于UAV的動態(tài)特性限制的WSN分簇路由算法（CR），根據(jù)節(jié)點信息量和UAV通信能力確定簇的大小，同時使得簇頭選舉能夠符合UAV飛行特點，達到提高網(wǎng)絡(luò)能量消耗一致性，延長網(wǎng)絡(luò)生存時間的目標。實驗表明，CR算法在滿足UAV動態(tài)特性限制和UAV最大飛行能量限制的前提下，能夠使得網(wǎng)絡(luò)能量消耗趨于一致，延長了網(wǎng)絡(luò)生存時間。

1 問題描述

1.1 UAV-WSN系統(tǒng)模型

如圖1所示，在分簇結(jié)構(gòu)的WSN中 WSN網(wǎng)絡(luò)被分為若干個相鄰的簇，通信分為2個層次。其中，低層通信是指節(jié)點與簇頭之間的通信，主要包括節(jié)點間發(fā)送控制信息，簇內(nèi)節(jié)點（Cluster Member，CM）向簇頭（Cluster Head，CH）節(jié)點發(fā)送數(shù)據(jù)等；高層通信是指簇頭與UAV之間的通信，主要包括簇頭與UAV之間發(fā)送控制信息和簇頭節(jié)點向UAV發(fā)送本簇的感知數(shù)據(jù)。本文假設(shè)UAV在同一水平面勻速飛行，同時為減少簇頭節(jié)點的通信能量消耗，僅在UAV飛行至簇頭正上方時對簇頭信息進行采集。

1.2 概念定義

由于在飛行過程中受到飛機最大法向過載、飛行速度、升致阻力等影響，UAV在曲線飛行時生成的路線曲率不能超過一個定值，UAV飛行限制的設(shè)計定義如下。

定義1 最小轉(zhuǎn)彎半徑 當飛機以一定速度在同一水平面勻速飛行時，方向舵旋轉(zhuǎn)到極限位置，飛機重心點在該飛行水平面上走過的軌跡圓的半徑。分析可知，這與飛機飛行速度有關(guān)，表征了飛機通過狹窄彎曲地帶或繞過障礙物的能力。相同速度時，最小轉(zhuǎn)彎半徑越小的飛機性能越好。

定義2 飛行角度 UAV在同一水平面上飛行，在該水平面以其飛行起點為圓心，正東為x軸正方向建立飛行坐標系，其飛行方向與x軸正方向順時針方向的夾角為UAV當前飛行方向。

定義3 可達區(qū)域 指UAV在當前位置，以一定角度在同一水平面，勻速飛行時，不需要繞行而可以直接到達的區(qū)域。如圖2所示，當飛機在i點以箭頭方向勻速飛行時，就會在i點形成2個與飛行方向相切的以最小轉(zhuǎn)彎半徑為半徑的虛擬的圓形區(qū)域，在這2個圓形區(qū)域以內(nèi)為不可達區(qū)域，以外的區(qū)域稱為可達區(qū)域。

1.3 限制條件

（1）UAV動態(tài)特性： 當UAV需要采集的下一個傳感器節(jié)點在當前位置的不可達區(qū)域內(nèi)，則UAV無法按照路徑規(guī)劃中的優(yōu)化路徑采集信息，需要繞行。

（2）UAV搭載飛行能量： 由于UAV搭載的可供飛行能量有限，當飛行任務(wù)消耗能量大于其搭載的可供飛行最大能量時，這種情況下飛機將無法飛抵終點，從而導致任務(wù)失敗。即UAV飛行能量消耗應(yīng)滿足式（1），具體如下：

該方法在保證UAV能夠完成采集任務(wù)飛回終點的同時，盡可能多地采集信息，同時可以提高能量消耗的一致性，延長網(wǎng)絡(luò)生存時間。

3 仿真分析

3.1 場景和參數(shù)設(shè)置

為了驗證本文提出的CR算法的性能，研究中將200個無線傳感器節(jié)點隨機放置在200 m×200 m的正方形區(qū)域中，并利用Matlab仿真工具進行了仿真實驗并與LEACH算法在能量和網(wǎng)絡(luò)生存時間方面進行了比較和分析。仿真參數(shù)的選取設(shè)置可詳見表1。

3.2 仿真結(jié)果與分析

3.2.1 路徑優(yōu)化情況

LEACH Path 為 UAV 按照 LEACH 算法分簇方案進行信息采集需要飛行的路徑長度；Original Path of CR、 Final Path of CR 分別代表UAV 對本文提出的 CR 算法生成的簇進行信息采集需要飛行的最初路徑長度以及經(jīng)過第四階段簇頭調(diào)整后產(chǎn)生的路徑長度。Dlimit指每次測試中UAV能夠飛行的最大路徑長度。這里，研究給出了10 次仿真實驗得到的計算結(jié)果平均值可見表2。

在生成簇頭和簇結(jié)構(gòu)后，CR算法經(jīng)過簇頭調(diào)整階段與最初生成的路徑相比，3種參數(shù)條件下分別優(yōu)化了21.3%、25.9%、16.7%。與LEACH算法相比，路徑平均長度分別減少了23.1%、24.6%、13.4%。這是因為CR簇頭調(diào)整階段使得簇頭分布更符合UAV的動態(tài)特性限制，確?？梢酝瓿深A(yù)定任務(wù)。

3.2.2 網(wǎng)絡(luò)節(jié)點能量差別

為驗證CR算法與LEACH算法在能量消耗方面的過程效果，本文通過每次輪循過后得到網(wǎng)絡(luò)節(jié)點最低能量和網(wǎng)絡(luò)節(jié)點能量差異來進行研究分析，內(nèi)容探討展示如下。

3.2.2.1 網(wǎng)絡(luò)節(jié)點最低能量

研究可得，網(wǎng)絡(luò)節(jié)點最低能量的數(shù)值對比可如圖3所示。分析圖3結(jié)果可知，CR算法在設(shè)計時考慮了簇的規(guī)模，使得每個簇的節(jié)點數(shù)不超過20個，這樣能確保UAV充分采集各簇信息，同時簇頭的負載不會過大；而LEACH算法的成簇卻是由節(jié)點選擇距離自身最近的簇頭加入該簇，使得簇的大小并不平均。因此，在均衡簇頭能量負荷方面，CR算法將優(yōu)于LEACH算法。

3.2.2.2 網(wǎng)絡(luò)節(jié)點能量差別

圖4提供了在10次輪循中節(jié)點能量差別（△E=max∣Ei-Eaverage∣）的變化曲線。

從圖4中可以看出，CR算法得到的△E一直低于LEACH算法。這是由于CR算法是根據(jù)提高網(wǎng)絡(luò)能量消耗一致性來選擇和調(diào)整簇頭，如此即使較高能量的簇頭承擔了更多負載來縮小節(jié)點能量差別。

3.2.3 信息采集率

如圖5所示，CR算法和LEACH算法的信息采集率分別為70%和28%。分析其原因機理可知：在CR算法中，為了能夠?qū)崿F(xiàn)UAV對節(jié)點信息的完全采集，對簇的大小了進行了限制。因此當規(guī)劃的UAV飛行路徑長度小于UAV最大航程時，UAV能夠完成信息采集任務(wù)。而在第3、5、8次測試中，UAV采集的信息量卻較低，這是因為采集全部信息所需路程超出了UAV的最大航程，為了滿足UAV航行能量限制，就需要放棄采集過程中的一些簇頭信息。

LEACH算法中，在成簇時各節(jié)點會選擇與自己最近的簇頭節(jié)點并加入該簇，而未能考慮到簇的規(guī)模，這就致使UAV飛過簇內(nèi)成員較多的簇頭時，對其信息無法達到完全采集，從而降低了信息采集率。圖5中2、5、6、7、9、10次測試中，LEACH采集信息為0，這是因為LEACH產(chǎn)生的簇頭使得UAV實際飛行距離過長，而算法又并未針對這種情況設(shè)計處理策略，則使得UAV訪問途中即已耗盡飛行能量而無法飛回終點，導致任務(wù)失敗。而在1、3、4、8次測試中，即使LEACH算法在生成簇頭基礎(chǔ)上的路徑長度均處在UAV的可達范圍內(nèi)，但卻由于個別簇的規(guī)模過大，導致UAV仍然無法對其做到完全采集，從而最終影響了信息采集率。

綜上分析可以得知，相較于LEACH算法，CR算法能夠優(yōu)化簇頭的選取，使得UAV的采集路徑長度一直保持在其最大直飛距離之內(nèi)，從而確保任務(wù)的高效完成；而在兩種方法都可行的情況下，CR算法也仍能獲得更高的信息采集率。

3.2.4 網(wǎng)絡(luò)生存時間

進一步研究得到，網(wǎng)絡(luò)生存時間的數(shù)值曲線對比如圖6所示。從圖6中可以看出，CR算法的網(wǎng)絡(luò)生存時間比LEACH算法高出了37%。LEACH算法與CR算法相比，第一個死亡節(jié)點出現(xiàn)較早，且CR算法在出現(xiàn)第一個死亡節(jié)點后曲線即急速下降。這是由于CR算法中節(jié)點的剩余能量分配均衡，第一個死亡節(jié)點出現(xiàn)時，其它節(jié)點的剩余能量也很低。而LEACH算法中，節(jié)點的剩余能量并不平均，因此在出現(xiàn)第一個死亡節(jié)點后，網(wǎng)絡(luò)中仍存在剩余能量較高的節(jié)點。

4 結(jié)束語

為了使得WSN分簇符合UAV動態(tài)特性限制的特點，本文設(shè)計提出了基于UAV動態(tài)特性限制的WSN分簇路由方法—CR算法。本次研究取得的重要成果可表述如下：

首先，CR算法在簇的劃分階段，考慮到UAV飛行時對簇頭采集數(shù)據(jù)的通信時間較短的情況，控制了成簇的大小，能夠保證UAV訪問過該簇頭節(jié)點后可以完全采集到該簇的信息；

其次，簇頭選擇階段在兼顧簇內(nèi)能量消耗一致的同時，對簇頭進行調(diào)整，使得簇頭選擇方案更利于UAV采集，減少UAV繞行距離；

最后，考慮到了UAV可供飛行能量的局限性，在分簇的同時加入總飛行能量的限制，使得規(guī)劃方案具備了客觀可行性。

實驗表明，CR算法能量能夠使得WSN節(jié)點能量消耗趨于一致，延長了網(wǎng)絡(luò)生存時間。

參考文獻

[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.