復雜環境下UAV-WSN 動態協作數據收集

鳳繼鋒，周金強

（四川大學電子信息學院，成都610065）

0 引言

在無線傳感器網絡中，由于傳感器節點能量有限且充電困難，節點能量效率是傳感器網絡數據收集最主要的問題。最近幾年，針對這個問題，利用UAV 去收集節點數據已經引起了廣泛的研究[1]。

無人機具有機動性和可控性，以及更大的信號覆蓋范圍。所以，對于UAV 飛行距離、通信質量等參數的優化可以提高數據收集效率，減少節能能耗。在文獻[2]中，UAV 順序移動到每個節點附近收集數據，以減少了鏈路距離。同時，作者提出了node-UAV 鏈路通用衰落信道模型，并優化節點的喚醒時間和UAV 飛行路徑，來最大程度的實現節點能耗最小化。HoD T等人[3]提出了一個啟發式算法優化節點能耗，具體地，當無人機飛抵傳感器工作區域后，不斷調整自身的飛行路徑去靠近每一個節點收集數據，從而更好的平衡各個節點間的能耗。

上述提出的方法中，UAV 和WSN 在數據收集過程中沒有信息交互，兩者是獨立工作的，UAV 不得不去訪問每一個節點來獲取數據，這大大消耗了無人機的能量，降低了數據采集效率。針對這個問題，由普通節點、簇頭節點、UAV 構成的分層網絡被提出。如圖1 所示，在分層網絡中，WSN 被分成多個簇，每個節點加入到一個簇中，并將數據發送給簇頭，UAV 根據簇頭位置規劃飛行路徑來直接從簇頭收集整個簇的數據，大大縮短了UAV 的飛行路徑和時間，減少了普通節點的能量消耗[4]。然而，由于簇頭需要將自己的位置信息發送給基站以便于UAV 路徑規劃，在分層網絡中，簇頭節點需要消耗更多的能量，導致簇頭節點過早死亡，影響網絡的整體連通性。

圖1 基于集群的無人機數據收集

針對這個問題，本文設計了一種UAV-WSN 動態協作方案：①提出節點密集區概念，UAV 根據節點密集區規劃初始飛行路徑；②簇頭的選舉參考了UAV 初始軌跡；③UAV 根據簇頭位置和輪替情況不斷調整、更新飛行路徑。特別地，在UAV 初始路徑規劃過程中，簇頭不需要將位置信息發給基站，減少了簇頭初始階段的能量消耗。具體的UAV-WSN 動態協作過程如圖2所示。

圖2 UAV-WSN動態協作框架

1 UAV-WSN動態協作

1.1 節點密集區域和無人機初始路徑規劃

在無線傳感器網絡中，傳感器節點一般被密集地部署在工作區域，該區域也就是無人機需要訪問的區域。因此，我們提出節點密集區域概念，并根據所有節點的已知位置將整個網絡劃分為多個密集區域，同時參考最小圓覆蓋問題獲取該區域的中心位置和半徑[5]。通過最小圓覆蓋算法，在節點密集的區域，尋找到一個覆蓋平面上所有節點的最小圓。確定最小覆蓋圓后，求出這個圓的半徑和圓心作為節點密集區域位置[6]。

UAV 初始路徑規劃的目的就是遍歷這些區域，基站根據這些區域的位置來設計出一條最短路徑，從基站出發，遍歷所有區域，然后返回基站，這是一個典型的旅行商問題（TSP）[7]。本文中，我們提出一種改進的蟻群算法來解決這個問題。

首先，我們通過K 最鄰近算法構造了一條初始路徑，并計算信息素增強因子的值。具體地，隨機選擇一個節點位置Vk，這個節點將根據以下的公式選擇下一個節點：

式中，P 是路徑選擇概率，r 是0 到1 均勻分布的隨機數，r0是0 到1 間的恒定值。根據概率P，從隨機節點出發，依次遍歷所有的節點，生成路徑：V1，V2…Vk…Vn。

令L 表示路徑的長度，τij(t)是路徑（i，j）之間的信息素；在t 時刻，ρ 是信息素揮發因子。因此，信息素更新機制如下：

If L

式中，?τij(t)是一輪迭代中路徑（i，j）上的信息素增量，是一輪迭代中第K 只螞蟻留在路徑上（i，j）上的信息素增量，m 表示螞蟻數量，Q 是信息素增強因子，Lk第K 只螞蟻所走過的路徑長度。

在普通的蟻群算法中，初始路徑搜索階段，螞蟻總是選擇信息素高路徑，這樣容易陷入局部最優解[8]。因此，本文提出的算法對路徑選擇策略做了以下調整：

式中，ps是路徑選擇策略，ηij是啟發函數，表示螞蟻從當前位置i 到任意位置的可能性，是t 時刻螞蟻從位置i 移動到j 的概率，α和β是信息素啟發因子（權重參數），q 是0 到1 間均勻分布的隨機數，q0是0到1 間的恒定常數。

根據以上方法，本文提出的改進的蟻群算法流程如圖3 所示。

1.2 簇頭選舉及數據收集

UAV 初始路徑規劃好后，基站將路徑廣播給所有節點，每個節點基于UAV 的飛行路徑和節點自身電量來計算一個權衡值用于簇頭選舉。節點i 的權衡值利用以下公式求得：

假設節點i 的位置是（X0,Y0），AX+BY+C=0 表示離節點i 最近的2 個節點密集區間的飛行航線方程。

其中，Ei是節點i 現存的電量，di是節點i 到航線的距離，α（0≤α≤1）是一個權重值。

每個節點計算的權衡值后，將該值和自身信息（位置及ID）發送給自己所處密集區域的其他節點。每個節點將自己的權衡值與接收到的進行比較，權衡值最大的成為簇頭節點，其他節點作為普通節點與簇頭通信，這樣就實現了分簇。與傳統的分簇辦法相比，在簇頭選舉成功后，不需要將信息發送給基站，極大減少了簇頭的能耗。

分簇完畢后，每個非簇頭節點按照TDMA 時隙發送數據給簇頭，簇頭節點存儲數據并等待無人機的到來。當UAV 按照初始路徑飛近節點密集區后，將信標廣播到該區域以實現和簇頭節點的通信，簇頭先將自己的位置信息發送給UAV，以便無人機不斷調整飛行軌跡接近簇頭。當UAV 與簇頭間的距離達到最佳傳輸距離時，簇頭將數據包和該簇節點信息（能量、位置）發送給UAV。最后，數據傳輸完畢后，無人機回復確認信標，本輪該簇的數據收集結束。

圖3 算法流程圖

1.3 簇頭輪替和無人機路徑更新

簇頭的能耗比普通節點的大很多，當簇頭的能量低于閾值ET時，表示該節點已經不適合擔任簇頭，需要進行簇頭輪替，尋找新的簇頭。所有能量高于閾值的節點都是新簇頭的候選，根據以下公式進行簇頭輪替：

公式中，Ej代表節點j 的剩余能量，ET是簇頭節點能量閾值，E0是該節點初始能量，distj表示節點j 與原簇頭間的距離，distave表示節點j 與簇頭其他節點的平均距離，0≤β1，β2，β3≤1（β1+β2+β3=1）是三個權重值。

每個候選節點將以上公式求得的值發送給原簇頭，原簇頭選擇該值最大的成為新的簇頭節點，并將信息發送給每一個節點。接下來，每個節點與新簇頭通信，簇頭輪替結束。

簇頭輪替后，無人機的路徑也需要更新?；靖鶕恳惠喢總€簇頭的能耗和剩余電量，在某個簇頭能量即將低于閾值之時，根據上述公式來預測新的簇頭位置，并在下一輪數據收集中直接與新簇頭通信。

2 能量消耗模型

為了研究節點的能量消耗，本文提出了一種簡化的WSN 能耗模型[9]。首先，我們假設節點能耗主要是由發送和接收數據引起的，而節點在非工作模式時消耗能量非常少，可以忽略不計。

傳感器節點發送或接收1bit 數據的能耗為Eelec，每發送1bit 數據功率放大器需要消耗的能量為Emp（when d ≥d0）或Efs（when d＜d0）。如圖4 所示是一階RF 能耗模型，每發送L 位數據所消耗的能量為：

每接收L 位數據所消耗的能量為：

圖4 一階RF能耗模型

3 結果

3.1 仿真結果

通過模擬大型復雜環境，我們在500×500 米的網絡中部署了120 個節點，基站位于（0，0）點，用X 表示，如圖5 所示。在每一輪仿真中，我們假設每個普通節點將10000bit 的數據發送給簇頭存儲，UAV 從簇頭收集這些數據，這個過程將仿真多輪。

圖5 仿真環境

圖6 節點密集區域

首先，我們使用第1.1 小節中的方法劃分節點密集區域，劃分結果如圖6 所示。同時利用提出的算法規劃UAV 初始路徑，如圖7 所示。接著，應用第1.2 小節中的方法選舉簇頭（黑點表示簇頭），圖8 就是第一輪簇頭選舉結果。最后，如圖9 所示，無人機開始收集數據并不斷調整飛行路徑，第一輪飛行長度為1963 米。

3.2 能耗分析

利用第3 節所描述的能耗模型，模型中具體的參數如表1 所示。在實驗中，我們將本文提出的方法（approach 2）與[10]中提出的方法（approach 1）進行比較，通過仿真數據收集過程來檢驗網絡整體壽命。在文獻[10]中，簇頭的選舉是根據節點的ID，ID 值較低的成為簇頭的可能性越大，簇頭選好后，簇頭需要將數據發送給基站。

圖7 UAV初始路徑

圖8 第一輪簇頭

圖9 不斷調整后的UAV飛行路徑

表1 仿真參數

首先，比較節點間能耗。圖10 顯示了相同環境下使用方法1 和方法2 在200 輪數據收集后每個節點剩余的能量。由圖可以看出，方法1 的每個節點能量明顯低于方法2，這意味著方法1 每輪消耗更多的能量。

圖10 200輪后節點剩余能量

其次，比較相同輪數收集的數據量。圖11 顯示了在所有節點死亡之前，使用兩種方法所收集到的數據包數量。從圖中可以看出，兩種方法在1000 輪之前收集的數據量相差不大，但在1000 輪之后，差距逐漸變大，在所有節點死亡后，使用方法2 收集到的數據大約是方法1 的2 倍。

圖11 數據收集總量

最后，比較傳感器網絡整體壽命。如圖13 所示，方法1 在經過500 輪后，存活的節點數逐漸減少，所有節點在2600 輪左右全部死亡。在方法2 中，節點的能量在2000 輪后才逐漸減少，所有節點在3400 輪后死亡。對比發現，方法2 中節點能耗比較平均，不存在大量節點過早死亡的現象，減少了對網絡整體性能的影響。

圖12 網絡整體壽命

4 結語

本文中，我們重點討論了簇頭過早死亡造成的WSN 能耗問題，在傳感器能耗與無人機能耗兩難選擇中，根據UAV-WSN 動態協作，通過協同優化簇頭選舉，無人機路徑規劃和簇頭輪替，提出了更優的數據采集辦法。仿真結果表明，與其他UAV-WSN 數據收集方案相比，該方法減少了節點間能耗差異，極大延長了傳感網絡壽命。