面向WSNs節點數據采集的無人機Voronoi圖路徑規劃

王正才, 彭 紅

(貴州輕工職業技術學院, 貴陽 550025)

0 引言

利用移動數據收集設備可提高無線傳感網絡 (Wireless Sensor Networks，WSNs)[1-2]的能效及數據傳輸效率。通過移動，收集設備靠近每個節點，提高數據收集效率，再將所收集的數據傳輸至控制中心。通過收集設備的移動，避免了節點與控制中心通信，節省了因傳輸數據所消耗的能量。

最近，基于無人機(Unmanned Aerial Vehicle, UAV)的飛行數據收集器受到廣泛關注[3-5]。相比于地面數據收集器(例如，移動機器人)，UAV移動更方便。地面上的數據收集器移動容易受到障礙物影響。此外，利用UAV通信，增加了信號傳輸的可靠性[6]。

然而，由于UAV的車載能量有限，它的移動總體距離受限[7-8]。因此，UAV應當在收集所有節點數據后，能夠有能量返程，這就涉及到UAV路由設計問題。因此，如何設計低能耗的UAV路由成為UAV領域的研究熱點。

除了能耗，設計UAV路由還需考慮UAV的類型。按飛行平臺構型，可將UAV分為固定翼和多旋翼無人機。相比于固定翼，多旋翼UAV可以在任意方向上移動，并且能在特定位置上盤旋。此外，通過優化UAV盤旋的位置，可以控制傳感節點傳輸數據時的能耗和UAV遍歷的距離。

研究人員針對UAV盤旋位置進行了深入研究[9-11]。文獻[9]提出了“節點視覺”方法，讓UAV遍布每個傳感節點，使UAV與節點間的通信距離最小，但是該方法增長了UAV所遍歷的路程。

為了縮短移動路程，文獻[10-11]選用了部分節點作為簇頭，UAV只遍歷簇頭。但是該方法增加了簇頭節點的能耗。此外，該方法要求節點能夠向簇頭傳輸數據，若節點間不能直接通信的話，該方法就無法使用。

文獻[12-17]利用傳感節點的通信范圍決策UAV盤旋位置。先優化UAV的盤旋位置，致使在每個盤旋的位置，UAV能夠與多個鄰居節點通信。為了避免通信沖突，節點間采用基于時分多址接入(Time-Division Multiple Access, TDMA)策略。然而，由于所有UAV盤旋的位置并非是完全獨立，決策UAV的盤旋位置是一項挑戰的工作。

文獻[12]利用Welzl的算法[18]構建能夠共享一個盤旋位置的節點集。而文獻[13-15]利用Voronoi圖產生UAV盤旋位置。而文獻[19-20]分別利用遺傳算法、k-最短路徑搜索最優的UAV盤旋位置。然而，這些方法產生的UAV盤旋位置并不是最優的。

為此，提出基于Voronoi圖的無人機路徑規劃算法VDO-UAV。VDO-UAV算法依據Voronoi圖產生參考路徑，再在參考路徑的基礎上優化UAV盤旋的各位位置，最終由這些位置點構成UAV遍歷路徑。仿真結果表明，提出的VDO-UAV算法在不增加復雜度的前提下，縮短了遍歷路徑。

1 系統模型

引用多旋翼UAV機，其在高空H處收集節點數據。節點間不能直接通信。假定在區域Ω內有N個節點。用xi表示節點si的位置，i=1,2,…,N。

令PLπ={0,1,…,K,0}表示UAV的移動位置點。K表示UAV的第k次盤旋的位置 。由于K≤N,UAV在單個盤旋位置上能夠收集多個鄰居節點的數據。

令DLπ表示UAV所遍歷的路程，其定義如式(1)所示：

(1)

式中，d表示i與i+1間的距離；Lπ={1,2,…,K}。

假定節點si向位于π(i)的UAV機傳輸數據，且π(i)∈{1,…,K}。表1給出一個示例，其中N=6、K=3。UAV移動位置點PLπ={0,1,2,3,0}。例如，π(2)=1表示節點2向位于1的UAV傳輸數據。類似地，π(5)=2表示節點5向位于2的UAV傳輸數據。

表1 節點與UAV盤旋位置示例

1.1 信道模型

將UAV與節點間鏈路視為視線鏈路(Line-of-Sight, LoS)。當節點si向位于π(i)位置點的UAV傳輸數據時，在UAV處所獲取的信號功率：

(2)

圖1 通信距離與水平距離示意圖

1.2 傳輸能耗

采用文獻[21]的能耗模型。節點si通過控制它的傳輸功率Gi，保證UAV接收信號的功率達到預設的值。因此，節點si向UAV傳輸bi比特數據所消耗的能量：

(3)

2 問題描述

(4)

因此，可利用式(5)表述VDO-UAV算法需解決的問題：

(5)

約束條件：

(6)

(7)

(8)

π(i)∈{1,2…,K},si∈S

(9)

3 VDO-UAV算法

3.1 Voronoi圖的修正

{p|dp,xi=dp,xm,m∈A(i),i∈A(m),m∈S,p∈Ω}

(10)

式中：dp,xm表示點p離節點si的距離；A(i)表示節點si的鄰居節點集；Ω表示監測區域。

(a) 修正前 (b) 修正后圖2 構建示例

3.2 最短路由決策

通過最小化UAV盤旋位置數，縮短UAV遍歷的距離。換而言之，每個UAV盤旋位置應盡可能覆蓋多個節點，進而收集更多節點數據。據此，每條Voronoi邊或中心均存在兩個或兩上以上的鄰居Voronoi中心(節點)。因此，可用L(h)搜索最短路由，其中h=1,2,…,hmax。然而，如果直接搜索，計算量較大。

為了降低計算量，采用基于參考路徑。所謂參考路徑是指由各Voronoi中心連線組成的路徑，如圖3所示。參考路徑是基于旅行商問題(Traveling Salesman Problem,TSP)[9]求解的路徑。

而浙江省氣象臺此前使用的省級海洋業務平臺因為開發應用多年,且主要功能以多種產品顯示為主,不具有GIS縮放、格點訂正等功能,無法很好展示近年來發展的海洋氣象客觀預報產品的精細化程度,已不能滿足現代化海洋預報業務的需求。為此,省氣象臺及時組織力量開發新一代省級海洋預報業務平臺。新一代海洋預報業務平臺是立足于為全省氣象預報員服務,基于海洋業務扁平化的理念,提供集數據采集、精細分析、格點訂正、預報制作、快速發布、產品展示、工作記錄等功能于一體,基于Silverlight和SQL數據庫技術進行開發的專業業務平臺,并將在使用中不斷發展來更好滿足臺風和海洋氣象預報業務需求。

算法1 The shortest route determination on mVDdmaxn Input:Reference path,a starting point,route direction,Lhmax,Lhmax-1,…,L(1).Output:The set of UAV hovering locations L.Initialize:??1,…,N ,L=?.Step 1:Assign numbers to mVDdmaxn 1:Assign numbers to Voronoi regions in an ascending order along the reference path an the route direction,from the starting point.Step 2:Determine UAV hovering location,sequentially2:h←hmax3:if h≥4 then4:if L(h)≠? then5:L←L∪l(h)|?l(h)L(h) .For all l(h)L(h),numbers as-signed to Voronoi regions adjacent to l(h)are removed from the set Λ.6:end if7:h←h-1 and go to line 3.8:end if9:Let l(3)L(3)be the Voronoi vertex surrounded by three Voronoi regions with consecutive numbers.10:if l(3)exists for numbers i,i+1,i+2 Λ then11:L←L∪l(3) ,Λ←Λi,i+1,i+2 ,Go to line 9.12:end if13:For two adjacent Voronoi regions with consecutive numbers,let l(2)L(2)be the intersection of Voronoi edge and the reference path.14:if l(2)exists for numbers i,i+1 Λ then15:L←L∪l(2) ,Λ←Λi,i+1 ,Go to line 13.16:end if17:Let l(1)L(1)be the Voronoi center with number i Λ.L←L∪l(1)|?i Λ Step 3:Find the shortest UAV route18:All lL are connected along the order of the reference path to make a closed route.19:For each l(1)L,replace l(1)with the intersection of the closed route and the MHCR of the corresponding sensor.

決策UAV路由的過程如算法1所示。具體步驟如下：

(1)首先沿參考路徑，從始點對Voronoi區進行編號，如圖3所示，沿著參考路徑，對15個Voronoi區進行編號。

(2) 利用L(hmax)，L(hmax-1)，…，L(1)決策UAV盤旋的位置。具體而言，當h≥4時，所有區中心位置(h)∈L(h)都作為UAV盤旋的位置；當h≤3時，就尋找3個Voronoi區所包圍的Voronoi頂點，并將這些頂點作為UAV盤旋的位置，如圖3所示的紅色圓點。第5、6、7個Voronoi區包圍一個頂點，如算法1的9～12行所示。

(3)除了由3個Voronoi區能夠包圍的頂點外，即剩余的就是2個Voronoi區相鄰或者孤立的一個Voronoi區。對于2個Voronoi區相鄰情況(h=2)，就取Voronoi邊與參考路徑的交點作為盤旋位置，如圖3所示，Voronoi區2與Voronoi區3。圖中黑色的正方形就是參考路徑與邊的交點，將其作為UAV盤旋位置，如算法1的13～16行。

(4)只剩余孤立的Voronoi區(h=1)，在這種情況下，就將該孤立的Voronoi區的中心位置作為UAV盤旋位置，如圖3所示的Voronoi區 4。如算法1的17行所示。

最后，為了形成閉合的路由，將所有UAV盤旋位置沿著參考路徑連接成閉合線路，進而形成閉合路徑，如圖3所示。

圖3 路由決策示例

4 性能仿真

4.1 仿真環境

選擇UAV遍歷距離和平均目標值作為性能指標。在滿足UAV遍歷距離限制下，若不能找到UAV的可行路徑，目標值就為零。

同時，選擇TSP算法[9]、文獻[12]提出的跳躍-替換的融合算法(Combine-Skip-Substitute, CSS)、基于Voronoi邊的算法(Voronoi Edge based Method, VEM)[13]和窮搜索法作為參照，并與VDO-UAV算法進行性能對比。

選擇TSP算法、CSS算法、VEM算法和窮搜索法作為參照的原因分別如下：①本文提出VDO-UAV算法求解的UAV路徑是以基于TSP求解的參考路徑為基礎，并對其進行修改的；選擇TSP算法作為參照，能夠反映VDO-UAV算法對參考路徑修改后的所得到路徑的性能；②文獻[12]提出的CSS算法也是將路徑規劃問題看成TSP問題，并采用CSS求解該TSP問題的解，其與TSP算法和VDO-UAV算法在TSP問題上存在共性；③VEM算法立足于多無人機路徑規劃問題，并采用遺傳算法求解最優的路徑。這與VDO-UAV算法的目的一致；④窮搜索法是簡單粗暴的搜索法。VDO-UAV算法目的是搜索最優的路徑。因此，選擇窮搜索法作為基準參照。

4.2 UAV遍歷距離

圖4 UAV的遍歷距離

相比于TSP和VEM算法，提出的VDO-UAV算法在UAV遍歷距離上的性能得到提高。VDO-UAV算法中UAV遍歷距離與CSS算法相似。CSS算法是通過傳感節點的通信距離決策UAV路由。 窮搜索法使UAU遍歷距離最小。但是其算法復雜度最高。

4.3 算法復雜度

表2給出TSP、VEM、CSS和VDO-UAV算法的時間復雜度。其中N表示節點數。從表2可知，窮搜索法的復雜度最高，其隨N呈指數增長。盡管CSS算法控制了UAV遍歷距離，但是它的復雜度高于VDO-UAV算法。

表2 算法復雜度

5 總結

針對WSNs的數據收集問題，提出基于Voronoi圖的無人機路徑規劃VDO-UAV算法。VDO-UAV算法充分利用了無人機收集數據的靈活性。為了縮短UAV遍歷路徑，VDO-UAV算法利用先依據TSP的參考路徑對Voronoi區進行編號，再優先將多個Voronoi區相交的頂點作為UAV盤旋的位置。仿真結果表明，提出的VDO-UAV算法縮短了遍歷路徑。