張珊珊 孟慶奎 王玲

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

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

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

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

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

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

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

1 問題描述

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

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

1.2 概念定義

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

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

定義2 飛行角度 UAV在同一水平面上飛行，在該水平面以其飛行起點(diǎn)為圓心，正東為x軸正方向建立飛行坐標(biāo)系，其飛行方向與x軸正方向順時(shí)針方向的夾角為UAV當(dāng)前飛行方向。

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

1.3 限制條件

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

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

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

3 仿真分析

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

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

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

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

LEACH Path 為 UAV 按照 LEACH 算法分簇方案進(jìn)行信息采集需要飛行的路徑長度；Original Path of CR、 Final Path of CR 分別代表UAV 對本文提出的 CR 算法生成的簇進(jìn)行信息采集需要飛行的最初路徑長度以及經(jīng)過第四階段簇頭調(diào)整后產(chǎn)生的路徑長度。Dlimit指每次測試中UAV能夠飛行的最大路徑長度。這里，研究給出了10 次仿真實(shí)驗(yàn)得到的計(jì)算結(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%。這是因?yàn)镃R簇頭調(diào)整階段使得簇頭分布更符合UAV的動態(tài)特性限制，確保可以完成預(yù)定任務(wù)。

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

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

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

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

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

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

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

3.2.3 信息采集率

如圖5所示，CR算法和LEACH算法的信息采集率分別為70%和28%。分析其原因機(jī)理可知：在CR算法中，為了能夠?qū)崿F(xiàn)UAV對節(jié)點(diǎn)信息的完全采集，對簇的大小了進(jìn)行了限制。因此當(dāng)規(guī)劃的UAV飛行路徑長度小于UAV最大航程時(shí)，UAV能夠完成信息采集任務(wù)。而在第3、5、8次測試中，UAV采集的信息量卻較低，這是因?yàn)椴杉啃畔⑺杪烦坛隽薝AV的最大航程，為了滿足UAV航行能量限制，就需要放棄采集過程中的一些簇頭信息。

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

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

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

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

4 結(jié)束語

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

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

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

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

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

參考文獻(xiàn)

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