基于近鄰算法的無人機采集森林數據航跡路線的規劃

王曉東，楊昆

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

0 引言

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

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

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

1 網絡模型

考慮森林異常數據檢測場景。在森林區域內部署多個傳感節點，這些傳感節點收集區域數據，如溫度數據、非法生物入侵等異常事件[13]，網絡模型如圖1所示。

圖1 網絡模型Fig.1 Network model

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

此外，在網絡區域部署一個UAV的充電站。當UAV的電量不足，其將返到該充電站充電。為簡化表述，用S0表示充電站。

2 問題表述

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

2.1 UAV向節點的無線輸電

(1)

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

2.2 UAV的能耗

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

(2)

(3)

Ep的定義見公式(4)

(4)

(5)

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

(6)

2.3 目標問題的構建

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

(7)

式中，dij表示節點si與節點sj間距離。

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

(8)

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

(9)

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

(10)

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

i≠j,?r∈R。

(11)

(12)

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

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

(13)

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

(14)

3 基于近鄰算法的UAV軌跡規劃

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

(15)

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

(16)

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

該算法的輸入為：

(1)充電站S0離網絡內所有節點的距離，即{d0i}i∈N。

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

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

4 性能分析

4.1 仿真環境

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

表1 仿真參數Tab.1 Simulation parameters

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

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

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

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

4.2 性能分析

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

圖2 任務平均時間隨節點數變化情況Fig.2 Average mission time varies with number of nodes

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

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

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

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

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

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

5 總結

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