基于近鄰算法的無人機采集森林數(shù)據(jù)航跡路線的規(guī)劃

王曉東，楊昆

(1.河南九域騰龍信息工程有限公司， 鄭州 450000；2.鄭州科技學院 信息工程學院， 鄭州 450064)

0 引言

隨著低功耗[1]、微型傳感器的迅速發(fā)展，無線傳感網(wǎng)絡(luò)(Wireless Sensor Networks, WSNs)已在軍事和民用等領(lǐng)域廣泛應(yīng)用[2]。在這些應(yīng)用中，傳感節(jié)點收集檢測區(qū)域內(nèi)的數(shù)據(jù)信息，再經(jīng)數(shù)據(jù)樣本采集、處理和傳輸，使控制中心能夠掌握區(qū)域環(huán)境的實況。這類應(yīng)用特別適宜于無人值守或者惡劣環(huán)境的監(jiān)測[3]，如森林防火、煤礦檢測。有效地收集數(shù)據(jù)是基于WSNs應(yīng)用的關(guān)鍵，傳統(tǒng)的收集數(shù)據(jù)方法是由WSNs內(nèi)節(jié)點自行組網(wǎng)，并通過單跳或者多跳方式將數(shù)據(jù)傳輸至控制中心。由于多數(shù)傳感節(jié)點是由干電池供電，節(jié)點的能量有限。傳統(tǒng)的收集數(shù)據(jù)方法消耗了節(jié)點的大部分能量，易出現(xiàn)能量空洞[4]。據(jù)此，研究人員在WSNs中采用移動節(jié)點收集網(wǎng)絡(luò)內(nèi)節(jié)點數(shù)據(jù)，如移動機器人、小車和無人機(Unmanned Aerial Vehicles, UAV)。因機動性好，部署靈活，基于UAVs的WSN數(shù)據(jù)收集機制受到廣泛關(guān)注[5-9]。例如，Chen等[5]研究基于UAV協(xié)助的數(shù)據(jù)收集算法。該算法采用非正交多址接入(Non-orthogonal multiple access, NOMA)策略，并將節(jié)點組建成NOMA群，并在UAV位置、功率控制約束條件下，最大化網(wǎng)絡(luò)吞吐量。數(shù)據(jù)收集軌跡規(guī)劃是基于UAV輔助WSN數(shù)據(jù)采集的關(guān)鍵。Zhan等[10]研究證實：最優(yōu)的數(shù)據(jù)收集軌跡是由連通線段組成。先建立數(shù)據(jù)收集軌跡優(yōu)化模型，再利用凸優(yōu)化求解獲取次優(yōu)解。此外，Hu等[11]研究表明，UAV性能由UAV的數(shù)據(jù)收集和傳輸過程共同決定，而這2個過程又受到UAV路徑影響。然而，上述研究工作只關(guān)注到UAV路徑規(guī)劃問題，沒有考慮到傳感節(jié)點的能量問題。Yang等[12]考慮了傳感節(jié)點充電時間問題，并利用遺傳算法UAV的最優(yōu)錨點和停留時間。盡管上述研究工作充分利用了UAV在空中收集數(shù)據(jù)的速度快、無線信號覆蓋范圍大等優(yōu)勢，但是其沒有考慮無線能量傳輸(Wireless Power Transfer, WPT)策略。由于傳感節(jié)點是由干電池供電，并且即使電池能量消耗盡，也不便更換電池，節(jié)點的工作壽命有限。部署UAVs也只是降低節(jié)點能耗速度，并不能從根本上解決節(jié)點儲能的有限問題。利用WPT策略，使無人機向節(jié)點傳輸電能，可有效地補充節(jié)點能量，延長節(jié)點的工作時間。UAVs的機動性好，其返航充電站充電。一方面，延長UAV的續(xù)航時間，另一方面，補充能量后可繼續(xù)為監(jiān)測區(qū)域內(nèi)的節(jié)點補給能量。

本研究以檢測森林異常數(shù)據(jù)為應(yīng)用場景，通過UAV收集已部署森林區(qū)域內(nèi)的節(jié)點數(shù)據(jù), 研究單個UAV的航跡規(guī)劃問題，即UAV的移動軌跡。UAV在收集節(jié)點數(shù)據(jù)時，需移動至節(jié)點上空，并以懸停方式收集節(jié)點數(shù)據(jù)。因此，如何規(guī)劃UAV的航跡是提高數(shù)據(jù)收集效率的關(guān)鍵因素之一。

在規(guī)劃UAV航跡時考慮2項約束條件：①每個節(jié)點都需被遍歷，即在單條航跡路徑中，UAV需遍歷每個節(jié)點；②確保UAV能夠返航到充電站，一旦UAV的剩余能量小于閾值，就返充電站充電。其中閾值等于UAV返航到充電站所消耗的能量。規(guī)劃UAV航跡的目標：基于上述2項約束條件，最小化UAV航跡路徑，降低數(shù)據(jù)收集時間。為此，本研究提出基于近鄰算法的無人機數(shù)據(jù)采集航跡規(guī)劃算法(NNDC)。先基于節(jié)點被遍歷、UAV有能量返航能量的約束條件下，建立路徑最小化路徑的模型，再利用近鄰算法求解，獲取最小化UAV航跡路徑。性能分析表明，NNDC算法縮短了路徑，降低了數(shù)據(jù)收集時間。

1 網(wǎng)絡(luò)模型

考慮森林異常數(shù)據(jù)檢測場景。在森林區(qū)域內(nèi)部署多個傳感節(jié)點，這些傳感節(jié)點收集區(qū)域數(shù)據(jù)，如溫度數(shù)據(jù)、非法生物入侵等異常事件[13]，網(wǎng)絡(luò)模型如圖1所示。

圖1 網(wǎng)絡(luò)模型Fig.1 Network model

網(wǎng)絡(luò)由N個傳感節(jié)點和一個無人機構(gòu)成。采用確定性方式在目標區(qū)域內(nèi)(e×e)部署N個傳感節(jié)點，其中e為邊長。假定N個傳感節(jié)點位置為已知信息。由集合N={s1,s2,…,sN}表示。i∈N表示節(jié)點索引號。傳感節(jié)點以固定周期感知環(huán)境數(shù)據(jù)，再將數(shù)據(jù)傳輸至UAV。用G=(N,T,A)表示網(wǎng)絡(luò)模型，其中N表示頂點，其對應(yīng)網(wǎng)絡(luò)中的節(jié)點數(shù)；T=[Tij]為權(quán)重矩陣，其中Tij表示頂點i與頂點j連線的權(quán)重；A={(i,j)|i,j∈N,i≠j}表示2頂點間的連線(邊)集。

此外，在網(wǎng)絡(luò)區(qū)域部署一個UAV的充電站。當UAV的電量不足，其將返到該充電站充電。為簡化表述，用S0表示充電站。

2 問題表述

NNDC算法旨在滿足能量約束條件和UAV遍歷所有節(jié)點的條件下，最小化UAV完成任務(wù)的時間。為此，先闡述節(jié)點和UAV的能耗模型。

2.1 UAV向節(jié)點的無線輸電

(1)

式中，ti表示si需要從UAV采集能量的時間。

2.2 UAV的能耗

UAV的能耗主要由2部分組成[15]。

(2)

(3)

Ep的定義見公式(4)

(4)

(5)

因此，UAV的能耗(EUAV)可表述為

(6)

2.3 目標問題的構(gòu)建

NNDC算法通過優(yōu)化UAV的航跡路徑，減少收集所有傳感節(jié)點所需的時間。因此，可構(gòu)建如公式(7)所示的目標問題

(7)

式中，dij表示節(jié)點si與節(jié)點sj間距離。

為了保證UAV在任意一條路徑r∈R需遍歷每個節(jié)點，且只遍歷一次，構(gòu)建公式(8)的約束條件

(8)

同時，確保UAV在每條r∈R中航跡中，只遍歷一次從頂點i與頂點j連線，需構(gòu)建公式(9) 的約束條件

(9)

最后，對UAV在每條路徑所消耗的能量進行限制，使其不超過其可儲存的最高能量Emax。

(10)

實質(zhì)上，公式(7)的目標問題是規(guī)劃UAV的航跡問題。為了消除子環(huán)路徑，采用Miller-Tucker-Zemlin(MTZ)約束進行子環(huán)消除。作為有效的子環(huán)消除約束條件，MTZ被廣泛應(yīng)用于車輛路徑規(guī)劃問題。為此，對約束條件進行修改。

i≠j,?r∈R。

(11)

(12)

此外，UAV的每條路徑r∈R必須包含S0(充電站)。因此，先生成K個S0的復(fù)制點，并將其加入節(jié)點集，即形成新的節(jié)點集N′=N∪K,其中K表示K個S0的復(fù)制點所形成的集合，即K={N+1,…,N+K}。相應(yīng)地，邊集A也被擴展，即A′={(i,j)|i,j∈N′,i≠j}。

為了保證每條航跡路徑均遍歷一個S0點，形成公式(13)的約束條件

(13)

最后，形成見公式(14)的目標函數(shù)P1(包括公式(8)、公式(12)、公式(13)，下面不再列出)

(14)

3 基于近鄰算法的UAV軌跡規(guī)劃

P1問題是典型的行商問題(Travel Salesman Problem, TSP)。而TSP問題為NP-complete問題[16]。因此，P1問題也是NP-hard問題。為此，采用近鄰算法，規(guī)劃UAV的航跡。

(15)

對于任意一條路徑r∈R，UAV從S0開始，先尋找離其最近的節(jié)點作為下一個遍歷點。假定sk∈N是離S0最近的節(jié)點。因此，將sk∈N加入路徑r，即Tr←{s0}∪{sk}，其中Tr表示路徑r的節(jié)點集。UAV移動至節(jié)點sk后，就開始向其傳輸能量，隨后，收集該節(jié)點數(shù)據(jù)。UAV再更新自己的能量

(16)

下面給出基于近鄰算法的UAV軌跡規(guī)劃過程的算法。

該算法的輸入為：

(1)充電站S0離網(wǎng)絡(luò)內(nèi)所有節(jié)點的距離，即{d0i}i∈N。

(2)各節(jié)點間距離，即{dij}i∈A2。

初始階段，令d←0;EUAV←Emax;r←1;Tr←{S0};Nr←φ;N′←N。

4 性能分析

4.1 仿真環(huán)境

利用MATLAB軟件建立仿真平臺，分析NNDC算法的性能。在200 m×200 m區(qū)域內(nèi)以確定性方式部署N個傳感節(jié)點。充電站S0位于200 m×200 m區(qū)域中心。部分仿真參數(shù)見表1。

表1 仿真參數(shù)Tab.1 Simulation parameters

選擇3個同類的算法作為參照。

(1)基于距離排序的UAV航跡規(guī)劃(Distance-Sorting Trajectory Planning of UAV, DSTP)。在DSTP算法中，先依據(jù)節(jié)點離充電站距離的大小，從近至遠排序。其中充電站就是監(jiān)測區(qū)域的中心位置，且是UAV的初始位置。然后，UAV再依據(jù)各節(jié)點序值，依次遍歷。

(2)隨機服務(wù)(Radom Service, RS)算法。在RS算法中，UAV以隨機方式收集節(jié)點的數(shù)據(jù)，即隨機移動。

(3)利用分支定界法直接求解目標函數(shù),記為BABS。該方法能夠獲取最優(yōu)的航跡，但是該算法的復(fù)雜度很高。

4.2 性能分析

將UAV收集所有節(jié)點的數(shù)據(jù)稱為一項任務(wù)。UAV完成單項任務(wù)的時間越短，表示路徑越優(yōu)。分析節(jié)點數(shù)隨任務(wù)的執(zhí)行時間變化。圖2給出UAV執(zhí)行50次任務(wù)時完成任務(wù)的平均時間，以下簡稱任務(wù)平均時間。由圖2可知，任務(wù)平均時間隨節(jié)點數(shù)的增加而呈線性增加。原因在于節(jié)點數(shù)越多，UAV在執(zhí)行每次任務(wù)需要收集的節(jié)點數(shù)據(jù)越多。因此，執(zhí)行任務(wù)時間就越多。此外，相比于RS算法和DSTP算法，提出的NNDC算法降低了執(zhí)行任務(wù)時間。原因在于NNDC算法利用近鄰算法，優(yōu)化了UAV收集數(shù)據(jù)的路徑。BABS算法執(zhí)行任務(wù)時間最短。這主要因為BABS算法采用窮搜索法建立了遍歷所有節(jié)點的最優(yōu)路徑。然而，由于復(fù)雜度高，BABS算法只能執(zhí)行14個節(jié)點的任務(wù)。

圖2 任務(wù)平均時間隨節(jié)點數(shù)變化情況Fig.2 Average mission time varies with number of nodes

分析UAV可存儲的最大能量Emax對任務(wù)平均時間的影響，如圖3所示。其中節(jié)點數(shù)為14。由圖3可知，任務(wù)平均時間隨Emax的增加而下降。原因在于：Emax越大，UAV存儲的能量越足，其返往充電站充電的次數(shù)越少，這利于縮短節(jié)點遍布節(jié)點路徑。此外， BABS算法具有最低的任務(wù)平均時間，并且當Emax大于600 J，其保持常數(shù)。這意味著，當Emax足夠大時，BABS算法只需一條路徑就能遍布網(wǎng)絡(luò)中所有節(jié)點，無須中途返回充電站充電。相比于RS算法和DSTP算法, NNDC算法的任務(wù)平均時間仍保持顯明的優(yōu)勢。

圖3 任務(wù)平均時間隨Emax變化情況Fig.3 Average mission time varies with Emax

再分析NNDC算法在每輪節(jié)點數(shù)據(jù)收集所產(chǎn)生的路徑數(shù)。路徑數(shù)越少，說明UAV往返充電站的次數(shù)越少，能夠以低能耗方式收集節(jié)點數(shù)據(jù)。圖4給出節(jié)點數(shù)為14個時的路徑數(shù)隨Emax的變化情況。由圖4可知，Emax越大，每輪收集節(jié)點數(shù)據(jù)所需的路徑數(shù)越少。這意味著UAV在收集節(jié)點數(shù)據(jù)時，充電次數(shù)越少。當Emax達到650 J時，NNDC算法所需的路徑數(shù)逼近于BABS算法所需路徑數(shù)。

圖4 路徑數(shù)隨Emax變化情況Fig.4 Average number of tours varies with Emax

最后，分析30輪數(shù)據(jù)收集中，UAV在每輪中所消耗的能量，如圖5所示，Emax=600 J,N=20。一輪是指UAV收集遍歷所有節(jié)點，并收集所有節(jié)點的數(shù)據(jù)。由圖5可知，隨著輪數(shù)增加，UAV的能耗在增加，原因在于最初節(jié)點可利用儲能工作，但隨著輪數(shù)增加，節(jié)點需要從UAV采集更多能量，換而言之，UAV需要向節(jié)點補給更多能量，這就增加了UAV的能耗。相比于RS和DSTP算法，NNDC算法降低了能耗。這歸功于NNDC算法優(yōu)化了收集數(shù)據(jù)的路徑，減少飛行時間。

圖5 UAV平均每輪所消耗的能量Fig.5 Average energy consumed of UAV in each round

5 總結(jié)

針對無線傳感網(wǎng)絡(luò)的數(shù)據(jù)收集問題，提出基于近鄰算法的無人機數(shù)據(jù)采集航跡規(guī)劃算法(NNDC)。NNDC算法利用無人機的機動性、高空特性，收集節(jié)點數(shù)據(jù)。同時，考慮到節(jié)點能量有限問題，NNDC算法通過無人機向節(jié)點補給能量。本研究針對森林數(shù)據(jù)異常數(shù)據(jù)收集的應(yīng)用前景，利用無人機收集節(jié)點數(shù)據(jù);建立數(shù)據(jù)收集時間最小化的目標函數(shù)，再利用鄰近算法規(guī)劃UAV遍歷節(jié)點數(shù)據(jù)的次序；考慮到節(jié)點的能量有限問題，允許UAV利用WPT向節(jié)點傳輸能量。性能分析表明，相比于RS和DSTP算法，NNDC算法縮短了數(shù)據(jù)收集時間。