鳳繼鋒，周金強(qiáng)

（四川大學(xué)電子信息學(xué)院，成都610065）

0 引言

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

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

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

圖1 基于集群的無人機(jī)數(shù)據(jù)收集

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

圖2 UAV-WSN動態(tài)協(xié)作框架

1 UAV-WSN動態(tài)協(xié)作

1.1 節(jié)點密集區(qū)域和無人機(jī)初始路徑規(guī)劃

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

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

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

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

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

If L

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

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

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

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

1.2 簇頭選舉及數(shù)據(jù)收集

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

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

其中，Ei是節(jié)點i 現(xiàn)存的電量，di是節(jié)點i 到航線的距離，α（0≤α≤1）是一個權(quán)重值。

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

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

圖3 算法流程圖

1.3 簇頭輪替和無人機(jī)路徑更新

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

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

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

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

2 能量消耗模型

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

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

每接收L 位數(shù)據(jù)所消耗的能量為：

圖4 一階RF能耗模型

3 結(jié)果

3.1 仿真結(jié)果

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

圖5 仿真環(huán)境

圖6 節(jié)點密集區(qū)域

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

3.2 能耗分析

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

圖7 UAV初始路徑

圖8 第一輪簇頭

圖9 不斷調(diào)整后的UAV飛行路徑

表1 仿真參數(shù)

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

圖10 200輪后節(jié)點剩余能量

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

圖11 數(shù)據(jù)收集總量

最后，比較傳感器網(wǎng)絡(luò)整體壽命。如圖13 所示，方法1 在經(jīng)過500 輪后，存活的節(jié)點數(shù)逐漸減少，所有節(jié)點在2600 輪左右全部死亡。在方法2 中，節(jié)點的能量在2000 輪后才逐漸減少，所有節(jié)點在3400 輪后死亡。對比發(fā)現(xiàn)，方法2 中節(jié)點能耗比較平均，不存在大量節(jié)點過早死亡的現(xiàn)象，減少了對網(wǎng)絡(luò)整體性能的影響。

圖12 網(wǎng)絡(luò)整體壽命

4 結(jié)語

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