牛涵琨,朱 江

(重慶郵電大學 通信與信息工程學院,重慶 400065)

0 引 言

隨著物聯(lián)網(wǎng)的不斷發(fā)展,無線傳感器網(wǎng)絡(wireless sensor network,WSN)得到了更廣泛應用。WSN通常由許多電池供電的傳感節(jié)點 (sensor node,SN)組成。在某種特定地理區(qū)域,用SN來傳感和傳輸傳感信息。由于傳感節(jié)點具有靈活部署和協(xié)同工作的優(yōu)點,無線傳感器網(wǎng)絡已經(jīng)應用于許多場景,例如災害檢測[1]、分布式估計[2]和環(huán)境監(jiān)測[3]等。在傳統(tǒng)無線傳感器網(wǎng)絡中,傳感節(jié)點感知的數(shù)據(jù)以一跳或者多跳的方式傳遞給Sink節(jié)點,這種方式在傳輸數(shù)據(jù)時容易造成能量空洞問題,即靠近Sink節(jié)點的SN通常需要更頻繁地傳輸數(shù)據(jù),導致該節(jié)點的能耗過早耗盡,造成網(wǎng)絡斷鏈。因此,引入無人機來解決這個問題[4-5]。與傳統(tǒng)的無線傳感器網(wǎng)絡相比,無人機可以更快地收集數(shù)據(jù)[6],并且縮短數(shù)據(jù)收集的時延。此外,無人機與地面上的SN可以建立視距(line of sight,LOS)連接,飛得更接近傳感節(jié)點,從而建立更穩(wěn)定的通信鏈路。因此,與傳統(tǒng)無線傳感器網(wǎng)絡相比,無人機對無線傳感節(jié)點數(shù)據(jù)收集更加節(jié)能和穩(wěn)定[7],并且延長了無線傳感器網(wǎng)絡壽命[8]。

在無人機數(shù)據(jù)收集的研究中,針對特定的應用場景和不同的優(yōu)化目標,一些文獻提出了基于時間窗的數(shù)據(jù)收集方案。文獻[9]基于收集數(shù)據(jù)的及時性,提出了時間窗的概念——物聯(lián)網(wǎng)設備需要及時上傳收集到的數(shù)據(jù),否則數(shù)據(jù)將喪失了時效性,但沒有優(yōu)化無人機和傳感節(jié)點的能耗,導致總系統(tǒng)能耗過高。文獻[10]基于內(nèi)存有限的無線傳感節(jié)點,提出了時間窗的概念——傳感節(jié)點需要及時上傳數(shù)據(jù),否則數(shù)據(jù)被會新數(shù)據(jù)覆蓋,造成數(shù)據(jù)丟失。但文獻[10]中無人機采用的懸停收集方式未優(yōu)化無人機的速度,造成過多能耗損失。由此可見,目前基于時間窗的數(shù)據(jù)收集方案研究大多沒有專門考慮無人機和無線傳感節(jié)點的能耗問題。然而在系統(tǒng)中,能耗是決定系統(tǒng)正常運行的關鍵因素:無人機飛行能耗決定了無人機的續(xù)航時間[11];傳感節(jié)點能耗決定了傳感節(jié)點的使用壽命[7,12]。所以,降低系統(tǒng)能耗是相關研究的重點。

為此,本文貢獻在于根據(jù)無線傳感節(jié)點MAC層的休眠-活躍調(diào)度機制,定義時間窗,并基于此提出了一種無人機軌跡和傳輸調(diào)度的聯(lián)合優(yōu)化方案,以降低無人機和無線傳感節(jié)點的總能耗。聯(lián)合優(yōu)化方案是整數(shù)非凸問題,為此,首先將傳輸調(diào)度連續(xù)化,將混合整數(shù)非凸問題轉化為連續(xù)非凸問題;然后通過引入2個松弛變量,將問題轉化為易于求解的凸問題,并利用連續(xù)凸逼近法求解。

1 系統(tǒng)模型

系統(tǒng)模型如圖1所示,其中無人機在各個傳感節(jié)點活躍期內(nèi)收集其數(shù)據(jù)。此模型可從網(wǎng)絡模型、信道模型和能耗模型三個主要方面進行描述。

圖1 系統(tǒng)模型圖Fig.1 System model diagram

1.1 網(wǎng)絡模型

地面共有K個傳感節(jié)點,其集合表示為{1,2,…,K}。無人機總飛行時間為T,本文采用時分多址(time division multiple access,TDMA)方案收集數(shù)據(jù)。將時間[0,T]離散化為N個相等的時隙,即T=Nδt,其中,δt表示時隙長度,并取值足夠小。

利用三維歐幾里得坐標表示的方法,可以分別表示出無人機和無線傳感節(jié)點的具體位置。傳感節(jié)點分布在地面上,第k個傳感節(jié)點的位置表示為

wk=(xk,yk,0),k∈{1,2,…,K}

(1)

由于時隙δt足夠小,假設與所有傳感節(jié)點到無人機的距離相比,無人機在δt內(nèi)的位置變化可以忽略不計,并以固定高度H在空中飛行,連續(xù)的無人機軌跡可以離散為N個時隙,在第n個時隙無人機位置表示為

q[n]=(x[n],y[n],H),1≤n≤N

(2)

無人機從起點出發(fā)最后回到起點,無人機起始和終止的位置滿足q(0)=q(T)。無人機在飛行過程中的最大速度為Vmax,其速度約束可表示為

(3)

假設無線傳感器網(wǎng)絡在MAC層具有“休眠-活躍”調(diào)度機制,每個傳感節(jié)點有自己的周期性休眠和活躍時間表,傳感節(jié)點只有在活躍期內(nèi)才能上傳數(shù)據(jù),并將其定義為時間窗,如圖2所示。如果在時隙n內(nèi),節(jié)點k始終處于活躍狀態(tài),那么該時隙就是節(jié)點k的時間窗。圖2中,給出3個傳感節(jié)點的時間窗,傳感節(jié)點SN1在第3個時隙到第5個時隙處于活躍狀態(tài),則該時隙內(nèi)為傳感節(jié)點SN1的時間窗,傳感節(jié)點SN2的時間窗為第5個時隙到第8個時隙,傳感節(jié)點SN3的時間窗為第9個時隙到第12個時隙。只有在這個時間窗內(nèi)傳感節(jié)點才能傳輸數(shù)據(jù),每個傳感節(jié)點需要傳輸?shù)臄?shù)據(jù)量為Sk。第k個無線傳感節(jié)點的時間窗定義為

圖2 傳感節(jié)點的時間窗Fig.2 Time window of sensor nodes

Wk[n]∈{0,1}?k,n

(4)

(4)式中:Wk[n]=1表示SNk在第n個時隙處于活躍狀態(tài);Wk[n]=0表示SNk處于休眠狀態(tài),該狀態(tài)下無法傳輸數(shù)據(jù)。

在傳感節(jié)點活躍狀態(tài)下,無人機向傳感節(jié)點發(fā)出信號,傳感節(jié)點接受到信號并開始向無人機傳輸數(shù)據(jù)。第n個時隙無線傳感節(jié)點的傳輸調(diào)度xk[n]為

xk[n]={0,1}?k,n

(5)

(5)式中,xk[n]=1表示uk在第n個時隙以恒定的發(fā)射功率Pk傳輸數(shù)據(jù),否則為xk[n]=0。

無線傳感節(jié)點只有在活躍狀態(tài)下才能上傳數(shù)據(jù),則有

xk[n]≤Wk[n],?k,n

(6)

由于無人機采用時分多址方案收集數(shù)據(jù),在每個時隙內(nèi),無人機最多只能收集一個無線傳感節(jié)點的數(shù)據(jù)。

(7)

1.2 信道模型

假設無人機與地面?zhèn)鞲泄?jié)點之間的通信信道為準靜態(tài)衰落信道,其中無人機與無線傳感節(jié)點之間的信道系數(shù)在每個時隙內(nèi)保持不變,在不同時隙內(nèi)發(fā)生變化。無人機移動性而產(chǎn)生的多普勒效應可以由接收機端補償,在第n個時隙無人機與第k個無線傳感節(jié)點的大尺度信道功率增益表示為

(8)

(8)式中,ρk[n]是小尺度衰落的復值隨機變量,βk[n]是大尺度衰落系數(shù)。其中,大尺度為LoS鏈路,取決于無人機和無線傳感節(jié)點的距離,表示為

(9)

(9)式中:β0表示距離為1 m時的信道功率增益,α≥2為路徑損耗指數(shù);dk[n]為無人機和第k個無線傳感節(jié)點的距離;‖·‖表示歐式范數(shù)。

小尺度衰落為Rician衰落模型[13]。|ρk[n]|2的累積分布函數(shù)表示為

F(z)?P(|ρk[n]|2

(10)

(10)式中,Q1(·)表示0階修正貝塞爾函數(shù)I0的Marcum-Q函數(shù),Rician因子Kc為LoS信號分量與散射分量之間的功率比。

在第n個時隙內(nèi),第k個無線傳感節(jié)點與無人機進行通信,其傳輸速率(bit/s)為

(11)

pk[n]=P(Ck[n]

(12)

(13)

1.3 能耗模型

模型中采用旋翼無人機,無人機能量消耗包括推進能耗和通信能耗,由于是上行數(shù)據(jù)采集,無人機的通信能耗可以忽略。通過將無人機飛行時間離散化,由文獻[14]推導,無人機飛行能耗模型可表示為

(14)

(14)式中:P0和Pi是無人機懸停狀態(tài)下型阻功率和誘導功率;Utip是葉尖角速度(m/s);v0是懸停時平均旋翼誘導速度(m/s);d0是機身阻力比;s是總葉片面積和葉片掃過面積的比;A是無人機葉片掃過的面積(m2);ρ是空氣密度(kg/m3)。

由于無線傳感節(jié)點的電路功率較傳輸功率較小,本文不予考慮[15]。因此,第k個無線傳感節(jié)點SNk的能量消耗可以表示為

(15)

2 問題描述

(16)

(16)式中,0≤θ≤1為權衡無人機能耗和傳感節(jié)點能耗的權重因子。

在滿足每個無線傳感節(jié)點的數(shù)據(jù)收集要求的前提下,通過聯(lián)合優(yōu)化無人機軌跡Q?{q[n]}和傳感節(jié)點傳輸調(diào)度X?{xk[n]} ,最小化無人機飛行能耗與所有傳感節(jié)點總能耗的加權和Dθ。根據(jù)上述模型,這個優(yōu)化問題可表示為

C3:xk[n]∈{0,1},?k,n

C4:Wk[n]∈{0,1}?k,n

C5:xk[n]≤Wk[n],?k,n

C6:‖v[n]‖≤Vmax,1≤n≤N-1

C7:q[1]=q[N]

(17)

(17)式中:約束C1表示每個傳感節(jié)點需要傳輸完數(shù)據(jù);約束C2表示在一個時隙內(nèi)無人機只能收集一個傳感節(jié)點的數(shù)據(jù);約束C3表示無線傳感節(jié)點的數(shù)據(jù)傳輸調(diào)度;約束C4表示傳感節(jié)點休眠-活躍狀態(tài);約束C5表示無人機必須在傳感節(jié)點活躍狀態(tài)下才能收集數(shù)據(jù);約束C6表示無人機飛行的最大速度;約束C7表示無人機完成任務后必須飛回起始點。

由于存在二進制變量xk[n]和非凸約束C1,且目標函數(shù)中飛行能耗也是非凸的,問題P1是混合整數(shù)非凸問題,難以求解。為此,提出了一種基于(successive convex approximation,SCA)的求解方法。

3 解決方案

針對P1是混合整數(shù)非凸問題,提出一種基于SCA的迭代算法來求解原問題的次優(yōu)解。為了將問題P1轉化為一個凸問題,首先將二進制變量松弛為連續(xù)變量將原問題轉化為連續(xù)非凸問題,然后引入2個松弛變量并進行變換,將連續(xù)非凸問題轉化為凸問題,最后對凸問題求解。

3.1 傳輸調(diào)度參數(shù)連續(xù)化

首先要處理問題P1中的混合整數(shù)約束,將C3中的二進制變量松弛為連續(xù)變量,得到

s.t. C1,C2,C4-C7

(18)

C8:0≤xk[n]≤1,?k,n

混合整數(shù)非凸問題P1轉化為連續(xù)非凸優(yōu)化問題P2,依然很難求解。

3.2 連續(xù)非凸問題轉化為凸問題

對于問題P2連續(xù)非凸優(yōu)化問題,其中飛行能耗和約束條件C1是非凸的。為了將P2轉變?yōu)橥箚栴},首先引入松弛變量Y={y[n]≥0},其中

(19)

(19)式可等價為

(20)

給定第r次迭代的局部點vr[n]和yr[n],由于‖v[n]‖2和y[n]2分別關于v[n]和y[n]的凸函數(shù),因此,(20)式右端可以通過一階泰勒展開表示下界,令φ[n]表示其下界函數(shù),則有

(21)

因此,無人機飛行能耗可重寫為

(22)

gk[n]≤Rk[n]

(23)

(xk[n]+gk[n])2≥

(24)

由(23)式,以下不等式成立

(25)

(25)式將約束C1轉化為凸約束。此時,(23)式為非凸的,同理對(23)式中的Rk[n]一階泰勒展開,則有

wk‖2+Ik,r[n]‖qr[n]-wk‖2

(26)

(26)式中:

(27)

(28)

Jk,r[n]=H2+‖qr[n]-wk‖2

(29)

引入松弛變量后,通過對松弛變量y[n],gk[n]的變換將非凸問題P2轉化為凸問題P3。

s.t. C2,C4-C8

C9:y[n]≥0,?n

C10:gk[n]≥0,?n,k

(30)

算法1基于SCA的求解算法

1.初始化無人機軌跡Q0,傳輸調(diào)度X0,設置算法收斂閾值ε1,迭代次數(shù)r=0。

3.forr=0,1,2K

5.更新xr+1[n]=x*[n],Rr+1[n]=R*[n],vr+1[n]=v*[n],yr+1[n]=y*[n],gr+1[n]=g*[n],qr+1[n]=q*[n]

6.判斷|Dθ(xr+1,Rr+1,vr+1,yr+1,gr+1,qr+1)-Dθ(xr,Rr,vr,yr,gr,qr)|≤ε1,成立進入步驟8,否則返回步驟3

7.更新r=r+1

8.end for

9.得到結果。

在算法1中,每次迭代都會求解標準凸優(yōu)化問題P3,優(yōu)化變量Q和X僅與傳感節(jié)點個數(shù)K和無人機飛行的總時隙數(shù)N有關,算法1執(zhí)行了L次迭代,因此其復雜度是O{LK3.5N3.5log(1/ε1)},其中,ε1是算法精度。由于所提方案嵌入了SCA的算法,此算法本身是收斂的[16],所以,所提方案是收斂的,且可以收斂到滿足P1的Karush-Kuhn-Tucker(KKT)條件的KKT解[17]。所提方案的計算過程不需要在無人機上運行,可以在地面工作站離線實施。然后,將運行結果Q和X從地面工作站上傳到無人機,無人機就可以按照這些結果開始數(shù)據(jù)收集任務。

4 仿真結果與分析

4.1 參數(shù)設置

考慮一個二維區(qū)域,其中7個傳感節(jié)點隨機分布在區(qū)域內(nèi)且位置已知,單架無人機在恒定的高度H=100 m。無人機端的加性高斯白噪聲設置為σ2=-110 dB,在距離d0=1 m時的參考信道功率增益β0=-60 dB。無人機的最大飛行速度Vmax=50 m/s;飛行周期T=164 s。時隙長度δt=0.5 s;帶寬B=1 MHz;權重參數(shù)λ=1 000。對于傳感節(jié)點,假設每個傳感節(jié)點具有相同的發(fā)射功率Pk=0.1 W,每個傳感節(jié)點需上傳數(shù)據(jù)量Sk=50 MByte,其時間窗參數(shù)如表1所示。對于旋翼無人機的推進能耗參數(shù)[11]為d0=0.6;Utip=120;A=0.503;ρ=1.225;s=0.05;P0=79.86;Pi=88.63;v0=4.03 m/s。

表1 傳感節(jié)點的時間窗Tab.1 Time window of sensor nodes

4.2 仿真分析

本文考慮大多數(shù)場景下,傳感節(jié)點具有休眠-活躍周期,傳感節(jié)點需在活躍期內(nèi)上傳數(shù)據(jù),休眠狀態(tài)無人機無法收集其數(shù)據(jù)。無人機的飛行軌跡如圖3所示。圖3中,無人機根據(jù)每個傳感節(jié)點的時間窗制定了數(shù)據(jù)收集順序,可以看到,無人機途經(jīng)傳感節(jié)點SN4時,由于未在傳感節(jié)點SN4時間窗內(nèi),無人機并未收集其數(shù)據(jù),而是直接飛往時間窗較早的傳感節(jié)點SN1收集數(shù)據(jù)。此外,可以看到,不同加權因子θ值下的優(yōu)化軌跡,隨著θ的減小,SN的總能耗考慮的權重更大,無人機更靠近每個傳感節(jié)點進行數(shù)據(jù)收集以減少傳感節(jié)點的能耗。 相比之下,θ增加使得無人機的能量消耗更為重要,無人機軌跡的飛行距離減少,能耗降低。

圖3 無人機的飛行軌跡Fig.3 Flight path of UAV

當θ=0.2,0.4,0.8時,傳感節(jié)點的傳輸調(diào)度分別如圖4—圖6所示,隨著加權因子θ增大,加權下的無人機能耗在總能耗中占比隨之增大,導致無人機在距離傳感節(jié)點越遠的地方收集數(shù)據(jù)。由于傳感節(jié)點的發(fā)射功率恒定不變,且滿足問題P3中的約束C12,傳感節(jié)點的數(shù)據(jù)收集時間也相應增加。反之,當θ較小時,加權下的傳感節(jié)點能耗在總能耗中占比較少,由(15)式可知傳感節(jié)點能耗與時間有關,無人機在靠近傳感節(jié)點的位置收集數(shù)據(jù),此時,由于通信信道較好,無人機可以在更短的時間內(nèi)收集完傳感節(jié)點的數(shù)據(jù)。

圖4 θ=0.2時傳感節(jié)點的傳輸調(diào)度Fig.4 Transmission scheduling of sensor nodes when θ=0.2

圖5 θ=0.4時傳感節(jié)點的傳輸調(diào)度Fig.5 Transmission scheduling of sensor nodes when θ=0.4

圖6 θ=0.8時傳感節(jié)點的傳輸調(diào)度Fig.6 Transmission scheduling of sensor nodes when θ=0.8

權值對傳感節(jié)點能耗的影響如圖7所示。隨著θ的增大,無人機飛行能耗考慮的權重較大,無人機在距離傳感節(jié)點較遠的地方收集數(shù)據(jù),導致傳感節(jié)點總能耗增加。當θ=0.2時,無人機在距離傳感節(jié)點較近的位置收集數(shù)據(jù),傳感節(jié)點上傳數(shù)據(jù)的時間減少。由于傳感節(jié)點以恒定功率上傳數(shù)據(jù),因此,可降低傳感節(jié)點總能耗。當θ=0.8時,SN6由于距離較遠,無人機為了節(jié)省能耗,在較遠的地方收集數(shù)據(jù),傳感節(jié)點上傳數(shù)據(jù)的時間變長,導致傳感節(jié)點的能耗增大。

圖7 權值對傳感節(jié)點能耗的影響Fig.7 Influence of weights on the energy consumption of UAV and sensor nodes

權值對無人機速度的影響如圖8所示。無人機在靠近傳感節(jié)點時降低飛行速度,以較好的通信信道收集數(shù)據(jù)。此外,加權因子θ增大時,由(14)式可知,無人機降低飛行速度,以實現(xiàn)降低飛行能耗的效果。由于本文設置了時間窗的約束,無人機必須在每個傳感節(jié)點時間窗內(nèi)迅速飛到該節(jié)點收集數(shù)據(jù),因此,優(yōu)化后的無人機飛行速度變化較大。

圖8 權值對無人機速度的影響Fig.8 Effect of weights on the speed of UAV

圖9為不同加權因子θ對無人機能耗和所有無線傳感節(jié)點總能耗的影響,可以看到,隨著θ的增大,無人機飛行能耗減小,傳感節(jié)點總能耗增大。針對傳感節(jié)點能耗要求較高的場景,傳感節(jié)點能耗一旦耗盡就會造成能量空洞[18],且無法頻繁地充電或者更換電池(例如偏遠的山區(qū)或者沙漠地區(qū)),可以將θ調(diào)小適用于該場景。針對無人機飛行能耗要求高的情況下(例如搭載基站服務器的救災無人機),可以將調(diào)高加權因子θ增加無人機的續(xù)航時間。

圖9 無人機和傳感節(jié)點能耗的權衡Fig.9 Trade-off of UAV and sensor node energy consumption

為了進一步展示本文方案的性能增益,將5個不同的方案與本文方案對比,分別為最小化無人機飛行能耗、最小化傳感節(jié)點能耗[7]、TSP方案[19]、最小化數(shù)據(jù)收集時間方案[20]。圖10比較了不同方案下傳感節(jié)點和無人機的能耗。圖10中,最小化無人機飛行能耗為θ=1的極端情況;最小化傳感節(jié)點總能耗為θ=0的極端情況;TSP方案未對無人機飛行能耗進行優(yōu)化;最小化數(shù)據(jù)收集時間雖然可以減少數(shù)據(jù)收集任務完成的時間,但是造成較高的無人機飛行能耗和傳感節(jié)點能耗;最大化吞吐量方案導致了無人機飛行能耗和傳感節(jié)點能耗較高。

圖10 比較不同方案下傳感節(jié)點和無人機的能耗Fig.10 Comparing the energy consumption of sensor nodes and UAV under different schemes

5 結束語

本文在確保無人機在各個節(jié)點活躍期內(nèi)完成數(shù)據(jù)收集任務的前提下,通過優(yōu)化傳輸調(diào)度和無人機軌跡來最小化無人機飛行能耗與無線傳感節(jié)點總能耗的加權和,并進一步探索了無人機飛行能耗和傳感節(jié)點總能耗之間的基本權衡。由于該問題是混合整數(shù)非凸優(yōu)化問題,很難直接求解。本文先將整數(shù)變量松弛為連續(xù)變量,并引入2個松弛變量將原問題轉化為凸優(yōu)化問題,最后用CVX求解凸問題。并且,提出了一種基于SCA的高效迭代算法,保證收斂到KKT解。在實際應用中,可以根據(jù)系統(tǒng)需求,靈活調(diào)節(jié)加權因子,在無線傳感器網(wǎng)絡的壽命和無人機續(xù)航能力之間取得良好的平衡。