李志堅,趙文棟,劉存濤

(陸軍工程大學,江蘇 南京 210007)

1 引言

1.1 傳感器網(wǎng)絡數(shù)據(jù)采集

目前,物聯(lián)網(wǎng)技術的不斷發(fā)展促使無線傳感器網(wǎng)絡的部署逐步成為現(xiàn)實。其中,小型低功耗傳感器設備通常由其自身攜帶的電池進行供電,可用能量有限。當其部署在室外環(huán)境中執(zhí)行諸如環(huán)境監(jiān)測、信息感知等任務時,一旦電量耗盡，很難得到及時有效的能源補充。在對傳感器數(shù)據(jù)進行采集時,實現(xiàn)傳感器設備的節(jié)能數(shù)據(jù)傳輸是延長傳感器網(wǎng)絡工作壽命的有效手段之一。

近年來,小型無人機憑借其成本低，機動性強及操作靈活等優(yōu)點,在無線傳感網(wǎng)絡數(shù)據(jù)采集方面得到了廣泛應用。 數(shù)據(jù)采集過程中,傳感器可采用休眠-喚醒機制,由無人機按需移動至傳感器附近將其喚醒。然后，利用良好的視距通信鏈路與傳感器進行通信,使得傳感器設備能夠以較小的發(fā)射功率獲得較高的通信速率,從而達到節(jié)能數(shù)據(jù)傳輸?shù)哪康摹榇?無人機輔助數(shù)據(jù)采集時通常需要考慮無人機與傳感器之間的喚醒調(diào)度問題。此外,考慮小型無人機通常由機載電池供電,可用能量也是受限的,對無人機軌跡進行優(yōu)化以節(jié)省飛行能耗,進而提高無人機的能耗效率,也是無人機輔助數(shù)據(jù)采集時通常需要考慮的問題。

針對數(shù)據(jù)采集過程中的無人機-傳感器喚醒調(diào)度及無人機軌跡優(yōu)化問題,已有研究從不同的目標出發(fā)開展了相關研究。靜態(tài)無人機輔助傳感器數(shù)據(jù)采集將無人機作為空中準靜態(tài)基站,從一定高度輔助給定區(qū)域內(nèi)傳感器的數(shù)據(jù)傳輸,主要研究無人機的部署/布局優(yōu)化方法,沒有考慮如何更好地發(fā)揮無人機的機動性優(yōu)勢。文獻[9]對物聯(lián)網(wǎng)常用的圓形軌跡下無人機數(shù)據(jù)采集系統(tǒng)的性能進行了分析,找出了兩者之間實現(xiàn)不同Pareto最優(yōu)的傳感器節(jié)點發(fā)射功率。文獻[10]對無人機能耗進行了精確建模和優(yōu)化。文獻[11]在滿足每個傳感器的通信吞吐量需求的條件下，使無人機總能耗最小化,但沒有考慮任務時間的影響以及傳感器的能耗約束。文獻[12]以傳感器網(wǎng)絡吞吐量最大化為優(yōu)化目標,對無人機-傳感器的喚醒調(diào)度和無人機軌跡進行了聯(lián)合優(yōu)化。文獻[13]以最小化傳感器向無人機傳輸數(shù)據(jù)的能耗為優(yōu)化目標,提出了無人機軌跡和無人機-傳感器的喚醒調(diào)度的聯(lián)合設計方案。其中,傳感器的節(jié)能傳輸是通過讓無人機在采集數(shù)據(jù)時盡可能靠近傳感器飛行以充分利用視距信道來實現(xiàn)的。文獻[14]以無人機作為數(shù)據(jù)采集器,設計了一種高效節(jié)能和快速數(shù)據(jù)采集(EFDC)方案,用于丘陵地區(qū)的無人機輔助傳感器網(wǎng)絡的數(shù)據(jù)采集。然后,應用改進的禁忌搜索算法優(yōu)化無人機的位置,利用導出的數(shù)據(jù)采集位置開發(fā)了旅行商問題,并采用改進的遺傳算法對其進行求解。文獻[15]在一對多數(shù)據(jù)采集方案下,聯(lián)合優(yōu)化了無人機軌跡和通信資源分配,提高了傳感器網(wǎng)絡的數(shù)據(jù)采集效率。文獻[16]研究了一種固定翼無人機在林火監(jiān)測中的數(shù)據(jù)采集任務規(guī)劃，將問題建模為一個帶鄰域的Dubins旅行商問題(DTSPN)。

1.2 軌跡優(yōu)化算法

當前路徑優(yōu)化算法可分為以生物和自然規(guī)律為啟發(fā)的智能算法和以(非)凸優(yōu)化范疇為主的傳統(tǒng)算法。

文獻[17]中基于凸優(yōu)化理論,提出了一種有人/無人機協(xié)作系統(tǒng)的軌跡優(yōu)化算法，分別以系統(tǒng)能耗最小化和無人機到達預定位置的時間最短為優(yōu)化目標,對優(yōu)化模型進行了逼近和凸化,最后，利用凸優(yōu)化算法對該問題進行求解。文獻[18]研究了U2U(UAV-to-UAV)的通信系統(tǒng),通過優(yōu)化無人機路徑使信息傳輸時間最小化，提出了一種基于精確懲罰法和逐次凸逼近的路徑規(guī)劃算法。文獻[19]提出了用于無人機航跡規(guī)劃的改進人工蜂群算法。該算法參數(shù)少,收斂速度快,能夠使無人機避免實時環(huán)境下的動態(tài)威脅。文獻[20]提出了改進的遺傳算法(IGA)和基于蟻群優(yōu)化算法的粒子群算法(PSO-ACO)來解決無人機TSP問題。文獻[21]研究無人機輔助的蜂窩網(wǎng)絡,由無人機充當飛行中繼將信息在蜂窩之間進行傳遞,隨后針對接入點選擇子問題具有NP難的特點,提出了一種基于博弈論的分布式算法。同時為了實現(xiàn)最優(yōu)信道狀態(tài),采用基于深度強化學習(DRL)的方法求解無人機路徑優(yōu)化子問題。

上述研究很少考慮偏僻節(jié)點的存在對無人機能耗效率以及傳感器網(wǎng)絡整體壽命的影響。其中,本文中的偏僻節(jié)點主要指具有以下特征的節(jié)點:一是距離傳感器網(wǎng)絡中心較遠,處于相對孤立的邊緣位置,與無人機起點和終點之間連線的距離較遠,如圖1中的偏僻節(jié)點Ⅰ;二是處于障礙物較多的環(huán)境中,與無人機之間的通信信道較差,無法完成數(shù)據(jù)采集,如圖1中的偏僻節(jié)點Ⅱ。需要注意的是,當傳感器距離傳感器網(wǎng)絡中心較遠,但與無人機起點和終點之間連線的距離較近時,通常不認為是偏僻節(jié)點。在本文中考慮第一種情況的偏僻節(jié)點。相比于訪問其他節(jié)點而言,無人機對偏僻節(jié)點進行抵近訪問時需要飛行更多的路程,從而導致能耗效率的降低和任務完成時間的增加。此外,當無人機可用能量受限或數(shù)據(jù)采集任務的時間比較緊急時,可能出現(xiàn)無法對偏僻節(jié)點進行抵近訪問的情況,此時偏僻節(jié)點需要以較大的發(fā)射功率發(fā)送數(shù)據(jù)，才能確保數(shù)據(jù)的有效傳輸,從而會消耗更多的能量，導致傳感器網(wǎng)絡的使用壽命降低。

圖1 兩類偏僻節(jié)點

為此,本文研究了考慮偏僻節(jié)點影響的高效數(shù)據(jù)采集問題,提出了地面移動基站與無人機協(xié)同的數(shù)據(jù)采集方法。其中,地面移動基站指的是可按需臨時部署的小型基站。在考慮無人機可用能量、任務完成時間以及傳感器可用能量等多種約束條件的基礎上,以最小化傳感器的最大能耗為優(yōu)化目標,對無人機-傳感器的喚醒調(diào)度、無人機的軌跡以及地面移動基站的部署位置進行了聯(lián)合優(yōu)化。為了解決該問題,提出了基于迭代優(yōu)化的問題求解框架,用塊坐標下降(BCD)技術以迭代的方式交替優(yōu)化子問題。最后,仿真結(jié)果表明，與基準方案相比,本文算法所提出的方案實現(xiàn)了顯著的性能提升。

2 系統(tǒng)模型及問題形式化

2.1 系統(tǒng)模型

如圖2所示,本文考慮了一個基于可部署基站和無人機的協(xié)同數(shù)據(jù)采集場景。其中,一架無人機作為可移動數(shù)據(jù)收集設備負責在給定的任務執(zhí)行時間內(nèi)收集位于地面的傳感器U={1,2,…,|U|}的數(shù)據(jù)。其中，偏僻節(jié)點M={1,2,…,|M|}通過可部署基站將數(shù)據(jù)間接發(fā)送給無人機。將數(shù)據(jù)直接傳輸給無人機的傳感器集合表示為K={1,2,…,|K|},U=K∪M,K∪M=?。傳感器的坐標表示為=[,]?？刹渴鸹镜淖鴺吮硎緸?span id="j5i0abt0b" class="emphasis_italic">=[,]。假設所有傳感器位置信息以及需要上傳的數(shù)據(jù)量都是已知的,并且無人機的飛行高度是固定的。

圖2 空地協(xié)同數(shù)據(jù)采集

假設從傳感器和可部署基站到UAV的信道是視距(LoS)信道。在任意時隙中，傳感器和可部署基站到UAV的信道增益為：

(1)

(2)

其中,表示距離為1 m時的參考信道功率增益,≥2為路徑損耗指數(shù)。傳感器在其被喚醒的傳輸時隙中以恒定的功率向無人機傳輸數(shù)據(jù),在未被喚醒傳輸時為了節(jié)能而保持靜默狀態(tài)。用[]表示在時隙時地面設備被無人機喚醒的二進制變量,如果[]=1,則表示傳感器在第個時隙進行數(shù)據(jù)傳輸，否則保持靜默。從而，可以得到無人機-傳感器喚醒調(diào)度約束為:

(3)

[]∈{0,1},?,∈K∪BS

(4)

在任意時隙n,如果傳感器k被無人機喚醒,則傳感器k對應的傳輸速率[](bps/Hz)為

(5)

其中，σ表示噪聲功率。同理，可部署基站與無人機之間的傳輸速率為

(6)

偏僻節(jié)點與可部署基站之間的傳輸速率為

(7)

傳感器節(jié)點的能耗為:

(8)

(9)

2.2 問題形式化

本文的目標是在完成數(shù)據(jù)采集任務的約束條件下聯(lián)合優(yōu)化無人機軌跡、無人機-傳感器的喚醒調(diào)度和可部署基站的部署位置,最小化所有傳感器的最大能耗。令={[],?},=,={[],?,∈K∪BS}。那么，優(yōu)化問題可表示為：

(P1):min,,,

s.t≤, ?∈K

(10)

E≤η, ?m∈M

(10b)

(10)

(10d)

[]∈{0,1}, ?∈K∪BS,n

(10)

‖[]-[-1]‖≤, ?≥2

(10f)

[1]=

(10g)

[]=

(10h)

約束(10a)、(10b)確保每個傳感器的能耗不超過,為松弛變量，表示所有傳感器能耗中的最大能耗。約束(10c)確?？煽康厥占矫總€傳感器的目標數(shù)據(jù)量。約束(10f)、(10g)、(10h)分別對應無人機的機動性約束和初始/最終位置約束。

3 算法設計

3.1 偏僻節(jié)點篩選算法

首先將對無人機飛行時間影響最大的傳感器節(jié)點篩選出來作為偏僻節(jié)點處理。篩選步驟如算法1所示:首先,記傳感器到無人機起點和終點所連直線的距離為0,=‖-‖,將滿足0,≥threshold的節(jié)點篩選出來放入集合中;然后，通過比較算法,再次篩選出對整個任務執(zhí)行時間的影響超過閾值的傳感器節(jié)點。在該場景下，選擇導致無人機飛行總時間波動較大的傳感器節(jié)點。假設傳感器的數(shù)據(jù)量相同,傳輸功率相同。無人機飛行至傳感器附近懸停，然后進行數(shù)據(jù)采集。將無人機開始對傳感器進行數(shù)據(jù)采集的時刻表示為,為了保證傳感器能耗均衡可以得到約束:‖()-‖≤，給定無人機最大飛行速度,且無人機勻速飛行時,飛行時間最小化問題可以轉(zhuǎn)化為無人機飛行距離最小化問題：

(11)

顯然約束和目標函數(shù)關于都是凸的,因此該問題可以用標準的凸優(yōu)化技術來解決。最后，將不考慮預篩選的偏僻節(jié)點而得到的最短飛行路徑,與全部傳感器的最短飛行路徑進行對比,篩選出影響超出閾值的傳感器,這些傳感器即為偏僻節(jié)點。

算法1 偏僻節(jié)點篩選算法 1: 初始化系統(tǒng)參數(shù),設置篩選閾值為threshold1;2: 求解TSP問題,得到訪問順序;3: 預篩選‖Q0-wu‖≥threshold1,u→G;4: G→g,-g→G;5: 代入集合G,求解(P);6: 比較無人機飛行距離,得到偏僻節(jié)點集合。

3.2 聯(lián)合優(yōu)化算法

在(P1)中,由于存在式(10a)(10c)中的非凸約束和(10e)中的整數(shù)約束,問題(P1)是一個混合整數(shù)非凸優(yōu)化問題,一般情況下很難得到最優(yōu)解。因此,首先將(P1)中的整數(shù)變量放松為連續(xù)變量。由于松弛問題相對于、、不是聯(lián)合凸的,采用塊坐標下降技術交替求解、、。

1)優(yōu)化喚醒調(diào)度

首先,對于任意給定的軌跡和基站部署位置、,可以通過求解以下標準線性規(guī)劃(LP)問題得到整數(shù)松弛無人機-傳感器的喚醒調(diào)度的解。

(12)

目標函數(shù)和約束都為線性函數(shù),(2)是標準凸優(yōu)化問題。

2)優(yōu)化無人機軌跡

另一方面,對于任何給定的基站部署位置和無人機-傳感器的喚醒調(diào)度、,無人機軌跡優(yōu)化原則是最大化所有傳感器的通信吞吐量的加權(quán)最小值,其中，權(quán)重與成反比。此時,傳感器的能耗是一定的,比值越大,表明能量利用率越高。反之,能量利用率越高,表明傳感器可以利用更小的能耗完成數(shù)據(jù)傳輸,從而達到降低傳感器能耗的目的。該問題可以表述為

(13)

由于式(13)中的非凸約束,(P3)是一個非凸優(yōu)化問題。然而,基于凸逼近算法可以得到一個有效的近似解,并保證至少收斂到一個局部最優(yōu)解。其主要思想是在每次迭代時，不斷地最大化(P3)的下界。設={[]?}表示給定的第次迭代的無人機飛行軌跡。通過應用一階泰勒展開,得到式(5)中[]下界為

(14)

其中

(15)

(16)

然后，可以通過求解以下問題來優(yōu)化無人機的軌跡:

(17)

3)優(yōu)化可部署基站部署位置

給定無人機軌跡、無人機-傳感器的喚醒調(diào)度、以及通過優(yōu)化得到的傳感器能耗,在保證偏僻節(jié)點的能耗小于等于其他傳感器能耗的前提下,優(yōu)化臨時基站的部署位置,使無人機和基站之間的吞吐量最大化：

(18)

[][]≥,

(19)

同理對式(19)應用一階泰勒展開得到傳輸速率的下界。因此(P5)也可以轉(zhuǎn)化為一個凸優(yōu)化問題。

4)塊坐標下降算法

采用塊坐標下降法(也稱交替優(yōu)化法)對(P1)進行求解。算法的詳細內(nèi)容在算法2中進行了總結(jié)。

算法2 求解(P1)的塊坐標下降算法 1: 初始化系統(tǒng)參數(shù),篩選偏僻節(jié)點,設置迭代精度為tol;2: 初始化W0,計算初始無人機軌跡Q0, r←0;3: 更新迭代次數(shù)r=r+1;4: 將Wr、Qr代入(P2)得到Ar+1;5: 將Ar+1、Qr和Wr代入式(P4),獲得Qr+1;6: 將Ar+1、Qr+1和Wr代入式(P5),得到Wr+1;7: 直到滿足收斂條件。

3.3 收斂性分析

值得指出的是,在經(jīng)典的塊坐標下降法中,為了保證收斂性,需要在每次迭代中精確地以最優(yōu)的方式求解更新子問題。而在本例中,對于軌跡優(yōu)化問題(P3)只最優(yōu)地求解它的近似問題(P4)。因此,不能直接應用經(jīng)典坐標下降法的收斂性分析,需要證明算法2的收斂性。

首先,在算法2的步驟4中,由給定的和得到(P2)的最優(yōu)解,因此，得到下面的不等式：

(,,)≥(+1,,)

(20)

其中，(,,)在(P1)前定義。

然后給定+1,,經(jīng)過算法2的步驟5處理得到以下結(jié)果:

(21)

其中，(a)成立,因為式(13)的一階泰勒展開式在給定的局部點處是緊密的,這意味著(P4)在處與(P3)的目標值相同;(b)成立,因為在給定、+1的算法1的步驟5中,+1為(P4)的最優(yōu)解;(c)成立,因為問題(P4)的目標值是原問題(P3)在+1的目標值的下界。由式(20)中的不等式可知,雖然只解決了一個近似優(yōu)化問題(P4)來獲得無人機軌跡,但(P3)的目標值在每次迭代后仍然不增加，并且(P1)的目標值為一個有限值的下界。

最后,對于給定的+1、+1代入算法2的步驟6中，得

(,,)≥(+1,+1,+1)≥

(22)

因此，關于,,的函數(shù)(,,)是收斂的。

4 仿真分析

在本節(jié)中,為了驗證本文提出方案和算法的有效性,提供數(shù)值例子來證明所提算法的有效性。除非另有說明,表1中列出的參數(shù)將被用于后續(xù)的數(shù)值結(jié)果。其他相關參數(shù)將單獨描述。假設所有傳感器分布在1.6 km×1.6 km的矩形區(qū)域內(nèi),設置無人機出發(fā)點為=[-800,0],目的點為=[800,0],單位為m。初始軌跡設置為直線飛行軌跡。

表1 仿真參數(shù)

為驗證本文所提出算法的性能,與以下四種算法進行對比：1)靜態(tài)數(shù)據(jù)采集方案,其中，無人機部署在所有傳感器和可部署基站的幾何中心；2)最短飛行距離基準方案,該算法中無人機在最短的飛行路徑勻速移動；3)最小懸停時間基準方案,該算法中無人機只有在懸停時進行數(shù)據(jù)采集,采集完當前傳感器數(shù)據(jù)后，以最大速度向下一傳感器或可部署基站移動；4)無基站輔助方案,該算法中只對無人機軌跡和喚醒調(diào)度進行聯(lián)合優(yōu)化,沒有考慮基站輔助。

從圖3可以看出,在沒有基站輔助的情況下，無人機需要飛到距離比較近的位置去收集信息。此時，由于無人機的飛行時間有限,無人機與其他傳感器的距離變大,因此，在傳感器傳輸功率一定的情況下,需要花費更多的時間來傳輸數(shù)據(jù),進而消耗更多的能量。而有可部署基站輔助時，無人機不需要飛行至距離很近的位置,此時，無人機與其他節(jié)點的距離就會變小,同理，此時傳感器的能耗就會降低。因此，在時間受限的條件下,有可部署基站輔助時，無人機與傳感器之間的平均距離比沒有可部署基站輔助時要小,即傳感器消耗的傳輸能耗小。

圖3 T=40 s時無人機的飛行軌跡對比

圖4顯示了傳感器在=40 s時的無人機-傳感器喚醒調(diào)度時間表,在這里我們可以觀察到，傳感器在大部分時間都處于未喚醒(睡眠)狀態(tài),只有當無人機飛行至足夠接近它們時，才會被喚醒(傳輸)，而且無人機對可部署基站的喚醒時間明顯大于其他傳感器,這是因為算法并沒有考慮可部署基站的能耗,因此，無人機不需要飛行至距離可部署基站附近進行數(shù)據(jù)采集,由于傳輸距離遠，所以傳輸相同數(shù)據(jù)量時花費的時間就多。

圖4 T=40 s時的無人機-傳感器(基站)的喚醒調(diào)度

圖5給出了不同任務執(zhí)行時間下，無人機的飛行軌跡以及基站的部署位置。從圖中可以看出,任務執(zhí)行時間越長，無人機就會飛到距離傳感器更近的位置去收集數(shù)據(jù)。因為算法是使傳感器的最大能耗最小化,所以，在無人機與其他傳感器傳輸距離越近時,可部署基站的部署位置同樣會距離偏僻節(jié)點越近。由于可部署基站不需要考慮能耗問題,無人機不需要飛行至可部署基站附近進行數(shù)據(jù)采集,因此節(jié)省了飛行時間，可飛往其他傳感器節(jié)點。

圖5 無人機飛行軌跡以及基站位置與T的關系

圖6比較了在不同任務周期時,傳感器節(jié)點的最大能耗。從圖中可以看出,本文所提出的方案優(yōu)于基準方案。采用可部署基站輔助無人機進行數(shù)據(jù)采集時,無人機不需要用較長的時間飛行到偏僻節(jié)點的周圍進行數(shù)據(jù)采集。此時,無人機有更多的時間飛行至距離傳感器節(jié)點更近的位置進行數(shù)據(jù)采集,從而以固定功率傳輸數(shù)據(jù)的傳感器所需要的通信時間減少,因此，傳感器的能耗降低。

圖6 Dk=10 m,不同T時傳感器節(jié)點最大能耗

圖7比較了不同數(shù)據(jù)量時傳感器的最小-最大能耗?？梢杂^察到,本文提出的設計優(yōu)于其他基準方案,并且隨著增加,性能增益更加明顯。這是因為通過本文提出的方案,無人機可以更接近甚至停留在傳感器的上方,因此，SN 可以用更短的傳輸時間、更高的速率傳輸數(shù)據(jù),從而節(jié)省能源消耗。

圖7 不同上傳數(shù)據(jù)量時的傳感器能耗(T=50 s)

圖8 不同T時無人機能量效率

5 結(jié)束語

本文研究了一個可部署基站輔助無人機對傳感器進行數(shù)據(jù)采集的場景，以傳感器能耗最小為目標,構(gòu)造了混合整數(shù)非線性規(guī)劃問題,該問題可解耦松弛為若干個凸優(yōu)化子問題。仿真結(jié)果表明,借助可部署基站可以極大地提高無人機的能效,降低傳感器的能耗。通過擴展本文的結(jié)果,在未來的工作中還有許多研究方向可以進行：1)空中和地面移動基站共存的網(wǎng)絡設計;2)基于高度和水平位置優(yōu)化的無人機三維軌跡設計;3)考慮多地面移動基站輔助,針對多無人機和多用戶場景進行節(jié)能聯(lián)合軌跡設計。