面向WSNs節(jié)點(diǎn)數(shù)據(jù)采集的無人機(jī)Voronoi圖路徑規(guī)劃

王正才, 彭 紅

(貴州輕工職業(yè)技術(shù)學(xué)院, 貴陽 550025)

0 引言

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

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

然而，由于UAV的車載能量有限，它的移動總體距離受限[7-8]。因此，UAV應(yīng)當(dāng)在收集所有節(jié)點(diǎn)數(shù)據(jù)后，能夠有能量返程，這就涉及到UAV路由設(shè)計(jì)問題。因此，如何設(shè)計(jì)低能耗的UAV路由成為UAV領(lǐng)域的研究熱點(diǎn)。

除了能耗，設(shè)計(jì)UAV路由還需考慮UAV的類型。按飛行平臺構(gòu)型，可將UAV分為固定翼和多旋翼無人機(jī)。相比于固定翼，多旋翼UAV可以在任意方向上移動，并且能在特定位置上盤旋。此外，通過優(yōu)化UAV盤旋的位置，可以控制傳感節(jié)點(diǎn)傳輸數(shù)據(jù)時(shí)的能耗和UAV遍歷的距離。

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

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

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

文獻(xiàn)[12]利用Welzl的算法[18]構(gòu)建能夠共享一個(gè)盤旋位置的節(jié)點(diǎn)集。而文獻(xiàn)[13-15]利用Voronoi圖產(chǎn)生UAV盤旋位置。而文獻(xiàn)[19-20]分別利用遺傳算法、k-最短路徑搜索最優(yōu)的UAV盤旋位置。然而，這些方法產(chǎn)生的UAV盤旋位置并不是最優(yōu)的。

為此，提出基于Voronoi圖的無人機(jī)路徑規(guī)劃算法VDO-UAV。VDO-UAV算法依據(jù)Voronoi圖產(chǎn)生參考路徑，再在參考路徑的基礎(chǔ)上優(yōu)化UAV盤旋的各位位置，最終由這些位置點(diǎn)構(gòu)成UAV遍歷路徑。仿真結(jié)果表明，提出的VDO-UAV算法在不增加復(fù)雜度的前提下，縮短了遍歷路徑。

1 系統(tǒng)模型

引用多旋翼UAV機(jī)，其在高空H處收集節(jié)點(diǎn)數(shù)據(jù)。節(jié)點(diǎn)間不能直接通信。假定在區(qū)域Ω內(nèi)有N個(gè)節(jié)點(diǎn)。用xi表示節(jié)點(diǎn)si的位置，i=1,2,…,N。

令PLπ={0,1,…,K,0}表示UAV的移動位置點(diǎn)。K表示UAV的第k次盤旋的位置 。由于K≤N,UAV在單個(gè)盤旋位置上能夠收集多個(gè)鄰居節(jié)點(diǎn)的數(shù)據(jù)。

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

(1)

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

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

表1 節(jié)點(diǎn)與UAV盤旋位置示例

1.1 信道模型

將UAV與節(jié)點(diǎn)間鏈路視為視線鏈路(Line-of-Sight, LoS)。當(dāng)節(jié)點(diǎn)si向位于π(i)位置點(diǎn)的UAV傳輸數(shù)據(jù)時(shí)，在UAV處所獲取的信號功率：

(2)

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

1.2 傳輸能耗

采用文獻(xiàn)[21]的能耗模型。節(jié)點(diǎn)si通過控制它的傳輸功率Gi，保證UAV接收信號的功率達(dá)到預(yù)設(shè)的值。因此，節(jié)點(diǎn)si向UAV傳輸bi比特?cái)?shù)據(jù)所消耗的能量：

(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表示點(diǎn)p離節(jié)點(diǎn)si的距離；A(i)表示節(jié)點(diǎn)si的鄰居節(jié)點(diǎn)集；Ω表示監(jiān)測區(qū)域。

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

3.2 最短路由決策

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

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

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

算法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)首先沿參考路徑，從始點(diǎn)對Voronoi區(qū)進(jìn)行編號，如圖3所示，沿著參考路徑，對15個(gè)Voronoi區(qū)進(jìn)行編號。

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

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

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

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

圖3 路由決策示例

4 性能仿真

4.1 仿真環(huán)境

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

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

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

4.2 UAV遍歷距離

圖4 UAV的遍歷距離

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

4.3 算法復(fù)雜度

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

表2 算法復(fù)雜度

5 總結(jié)

針對WSNs的數(shù)據(jù)收集問題，提出基于Voronoi圖的無人機(jī)路徑規(guī)劃VDO-UAV算法。VDO-UAV算法充分利用了無人機(jī)收集數(shù)據(jù)的靈活性。為了縮短UAV遍歷路徑，VDO-UAV算法利用先依據(jù)TSP的參考路徑對Voronoi區(qū)進(jìn)行編號，再優(yōu)先將多個(gè)Voronoi區(qū)相交的頂點(diǎn)作為UAV盤旋的位置。仿真結(jié)果表明，提出的VDO-UAV算法縮短了遍歷路徑。