李海翠,刁憲邦,張校晨,尚志會,楊蓮新
(1.中國人民解放軍陸軍工程大學 通信工程學院,南京 211100;2.國防科技大學 電子科學學院,長沙 410003)
物聯(lián)網(wǎng)(Internet of Things,IoT)是未來移動通信網(wǎng)絡(luò)的重要組成部分,它可以連接來自不同環(huán)境的大量設(shè)備,支持許多新穎的應(yīng)用。然而,IoT設(shè)備的大規(guī)?;ミB所產(chǎn)生的大量數(shù)據(jù)、IoT設(shè)備體積偏小、電池能量較為有限以及計算能力較弱等缺陷對IoT的發(fā)展帶來了嚴峻的挑戰(zhàn)。為解決這些問題,多址邊緣計算(Multi-access Edge Computing,MEC)和非正交多址接入(Non-orthogonal Multiple Access,NOMA)技術(shù)所結(jié)合的系統(tǒng)應(yīng)運而生。
近年來,研究者們開始研究基于NOMA的MEC系統(tǒng),目的是最大化 NOMA在 MEC 系統(tǒng)中的潛在增益。大多數(shù)的作者均是通過優(yōu)化終端設(shè)備分簇、計算資源、通信信道分配策略或終端設(shè)備傳輸功率來最小化所有終端設(shè)備的總能耗、總時延以及總開銷,少數(shù)作者則通過設(shè)計遷移架構(gòu)達到滿足設(shè)備計算需求的目的。然而,對于偏遠山區(qū)和受災(zāi)地區(qū),由于沒有基站或基站被破壞,IoT設(shè)備靠自身的計算能力無法完成計算任務(wù)。此時,無人機(Unmanned Aerial Vehicle,UAV)的部署靈活、響應(yīng)迅速等優(yōu)勢為應(yīng)對此問題提供了解決思路。UAV可以在懸停模式下按需部署,更適合IoT的無線傳輸。由于其空中優(yōu)勢,可以獲得更好的視距鏈路,若將MEC服務(wù)器部署至UAV上,IoT設(shè)備便能夠在離服務(wù)器足夠近的地方發(fā)送信息[1-4]。文獻[5-8]研究的均是無人機輔助下基于NOMA的MEC系統(tǒng),文獻[5-7]中均是單無人場景,文獻[8]研究的多無人機場景;文獻[5-7]在優(yōu)化UAV軌跡時對每個時隙IoT設(shè)備的排序都是固定的,而文獻[8]優(yōu)化UAV軌跡時用的是上一時隙的IoT設(shè)備的排序。
綜上所述,關(guān)于NOMA-IoT中多UAV輔助MEC系統(tǒng)的研究還處于初級階段,研究此系統(tǒng)是非常有意義的。為了最小化系統(tǒng)總能耗,設(shè)計合理的計算資源分配和功率分配策略為重中之重。然而NOMA的引入必然導致同信道干擾,可以通過優(yōu)化卸載策略得到對每個設(shè)備來說同信道干擾小的設(shè)備組,而且可以使固定的MEC服務(wù)器針對特定設(shè)備組進行服務(wù),從而設(shè)備分配到更多的計算資源,最終減少系統(tǒng)總能耗。此外,若UAV的軌跡未知,則下一時隙連續(xù)干擾消除的排序變未知,從而傳輸數(shù)據(jù)量便無法獲得,最終優(yōu)化問題便無法獲得。因此,受上述文獻啟發(fā),本文對NOMA-IoT場景中多UAV輔助的MEC系統(tǒng)進行研究,具體是固定UAV的軌跡,對每個時隙的IoT卸載策略、計算資源和發(fā)射功率進行聯(lián)合優(yōu)化,以最小化所有設(shè)備的本地計算和卸載過程能耗以及MEC服務(wù)器計算能耗的加權(quán)和。
考慮IoT中一個區(qū)域突發(fā)地震,附近的基站均被破壞,地面多個IoT設(shè)備都有一個高復雜度的計算任務(wù)需要在時間間隔T內(nèi)完成。由于IoT設(shè)備計算能力及能量有限,MEC服務(wù)器具有更強大的計算能力,IoT設(shè)備可以將計算任務(wù)卸載到MEC服務(wù)器。采用多個配備MEC服務(wù)器的UAV來協(xié)助IoT設(shè)備完成計算任務(wù),UAV按照固定軌跡飛行,多個IoT設(shè)備采用上行NOMA方式將計算任務(wù)卸載至多UAV配備的MEC服務(wù)器上。具體系統(tǒng)模型圖如圖1所示。
圖1 系統(tǒng)模型圖
在UAV飛行過程中,周圍可能會有其他物體充當散射體或障礙物,導致UAV和IoT設(shè)備之間的通信中斷。因此在對信道進行建模時,必須同時考慮視距鏈路(Line of Sight,LoS)和非視距鏈路(Non-Line of Sight,NLoS),根據(jù)兩者出現(xiàn)的概率進行平均以求得信道增益。LoS/NLoS概率取決于環(huán)境、設(shè)備和UAV的位置以及仰角。在第n個時隙時,假設(shè)IoT設(shè)備i將計算任務(wù)卸載至UAVm上,則兩者之間的仰角和直線距離可寫為
(1)
根據(jù)文獻[8],LoS /NLoS的概率可寫為
(2)
式中:a和b是取決于載波頻率和環(huán)境類型的參數(shù)。
因此,設(shè)備i和UAVm之間LoS和NLoS的路徑損耗為
(3)
式中:fc是載波頻率,ζ是路徑損耗系數(shù),η1和η2分別代表LoS和NLoS的大尺度路徑損耗系數(shù),c代表光速。
(4)
(5)
假設(shè)IoT設(shè)備i要完成的計算任務(wù)比特數(shù)是Ii。采用部分卸載方式,即每個用戶進行本地計算的同時也可以將部分任務(wù)卸載到UAV上配備的MEC服務(wù)器,本地計算和遠程卸載計算的比特數(shù)不得超過任務(wù)總比特數(shù)[1]。因此,在第n個時隙時IoT設(shè)備i本地計算完成的比特數(shù)為
(6)
對于卸載而言,定義αi,m為二進制變量。由于一個設(shè)備至多只能將計算任務(wù)卸載至一個UAV上,所以αi,m必須滿足
(7)
此外,由于該過程是離散化的,并且時隙是最小的動作單位,所以MEC服務(wù)器只能計算在前一時隙中卸載的計算任務(wù)。因此,當沒有任務(wù)被卸載時,第一個時隙不應(yīng)該分配資源。另一方面,在第N個時隙時將任務(wù)卸載到UAV也是不合理的,因為在該周期結(jié)束后不再對卸載的計算任務(wù)進行計算。
(8)
(9)
(10)
根據(jù)前面的分析,可以得到系統(tǒng)的效用函數(shù)為
(11)
式中:非負參數(shù)ωuser和ωuav代表IoT設(shè)備和UAV的權(quán)重,滿足ωuser+ωuav=1。本文的目標是通過聯(lián)合優(yōu)化卸載策略和資源分配(本地計算的CPU頻率、UAV計算的CPU頻率以及IoT設(shè)備的發(fā)射功率)最小化系統(tǒng)中IoT設(shè)備和UAV的加權(quán)總能耗,以提升系統(tǒng)性能,因此優(yōu)化問題可寫為
(12a)
s.t.
C1:αi,n,m={0,1},
(12b)
(12c)
(12d)
(12e)
(12f)
(12g)
(12h)
顯然,問題P0是一個混合整數(shù)非線性規(guī)劃問題,它由二進制、整數(shù)和實數(shù)變量組成,目標函數(shù)是非凸函數(shù),因此無法利用凸優(yōu)化直接解決該問題。從式(11)中可以發(fā)現(xiàn),卸載策略α獨立于發(fā)射功率p、CPU頻率fuser和服務(wù)器的CPU頻率fuav,因此可以將每個時隙的卸載策略、聯(lián)合計算資源和功率分配分開優(yōu)化,將其分為卸載策略和聯(lián)合計算資源和功率分配子問題。本文針對卸載策略子問題將其建模為聯(lián)盟形成博弈,針對計算資源和發(fā)射功率優(yōu)化問題采用連續(xù)凸逼近將其轉(zhuǎn)化為可解的凸問題,并提出一種高效的優(yōu)化算法對聯(lián)合計算資源和功率分配子問題進行求解,通過交替求解這兩個子問題來找到原問題的收斂次優(yōu)解。
首先將IoT設(shè)備根據(jù)與UAV的距離遠近對聯(lián)盟進行初始化,獲得卸載策略,給定UAV的軌跡,假設(shè)IoT設(shè)備i將計算任務(wù)卸載至UAVm,此時優(yōu)化計算資源和通信資源的子問題P1可以寫為
(13a)
s.t.
(13b)
(13c)
(13d)
(13e)
(13f)
式中,雖然目標函數(shù)是凸函數(shù),但由于約束C7的存在仍使得問題難以求解,為了要解決P1,可以將其變換為目標函數(shù)為凸的等價形式,并對約束條件進行變換。
根據(jù)公式(10),通過換底公式可以得到
(14)
令
(15)
然后,利用遞推公式可以得到
(16)
因此,可以得到
(17)
(18)
由于兩個指數(shù)函數(shù)的差一般不是凸函數(shù),因此優(yōu)化問題P1仍是非凸函數(shù)。此外,每個IoT設(shè)備的發(fā)射功率之和具有一些遞歸特性。接下來我們試圖利用這些特性來證明每個UAV對應(yīng)的IoT設(shè)備的功率之和是一個凸函數(shù)。所有UAVm服務(wù)的所有IoT設(shè)備的發(fā)射功率之和為
(19)
式中:Um為將計算任務(wù)卸載至UAVm的IoT設(shè)備總數(shù)。
此外,有g(shù)l1,m[n]≤gl2,m[n]≤…≤glUm,m[n]成立,可以得到每個指數(shù)函數(shù)的系數(shù)都是非負的。令βk,m[n]=1/glk,m[n],有βUm+1,m[n]=0和β0.m[n]=0兩種特殊情況,因而式(19)可以重寫為
(20)
上式是優(yōu)化問題P1中自變量的凸函數(shù),因此目標函數(shù)仍然一個凸函數(shù)。
另外,定義一個ψ(i,n,m)代表在時隙n時設(shè)備i在UAVm上的排序,此時數(shù)據(jù)傳輸量為
Ri,m[n]=xψ(i,n,m),m[n]-xψ(i,n,m)-1,m[n]。
(21)
因此,優(yōu)化問題P1可以重寫為
(22a)
s.t.C3,C4,C6,
eJx0+JeJx0(x-x0)。
(23)
s.t.C3,C4,C6,C7′,
(24a)
[y(xψ(i,n,m),m[n])-
(24b)
算法1的偽代碼如下:
Input:卸載決策α,IoT設(shè)備坐標ruser,UAV軌跡ruav
Output:傳輸功率p,設(shè)備的CPU頻率fuser,服務(wù)器的CPU頻率fuav
1 計算每個時隙每個聯(lián)盟的信道增益并按升序方式排序
2 令x0=0,初始效用函數(shù)ρ0=0及迭代次數(shù)λ=1
3 直到 |ρλ-ρλ-1|≥εdo
5λ=λ+1,返回步驟3
6 Output:p,fuser,fuav
當初始化卸載策略得到資源分配策略后,卸載策略子問題可以表示為
s.t.C1~C2 。
(25)
(26)
(27)
基于以上定義,我們提出了一種分布式算法來獲得博弈的納什穩(wěn)定解,稱為算法2(聯(lián)盟形成博弈算法)。通過有限次迭代,可以獲得在當前計算資源和功率分配前提下的卸載策略,最終得到穩(wěn)定的納什穩(wěn)定分區(qū)如定義3。
算法2的偽代碼如下:
2 while num≤10×Udo
3 重復:iter=iter+1,調(diào)用算法1,求得p,fuser,fuav
6 else num=num+1
7 end if
8 end while
2.3.1 收斂性分析
問題P0由兩層迭代解決:內(nèi)層(算法1)是在當前卸載策略的前提下通過迭代求解P1″來尋找計算資源和發(fā)射功率的最優(yōu)分配,外層(算法2)通過迭代求解P2求得每一時隙物聯(lián)網(wǎng)設(shè)備的卸載策略,而后內(nèi)外層迭代求解P0,并尋找到其次優(yōu)解,即每一時隙每個物聯(lián)網(wǎng)設(shè)備的卸載策略、計算資源和功率分配策略。首先討論內(nèi)層的收斂性。根據(jù)迭代過程,更新過程可以表示為
(28)
式中:ρ(λ+1)是目標函數(shù)的第λ+1次迭代。可以發(fā)現(xiàn),由于問題P1″是嚴格凸函數(shù),對所有的λ都有ρλ+1<ρλ成立,因此ρλ是λ的單調(diào)非增序列,ρλ是該序列的下界。由于具有下界的單調(diào)非遞增序列總是收斂的,因此本文提出的連續(xù)凸逼近算法(算法1)是收斂的。接下來對外層聯(lián)盟形成博弈的收斂性進行分析。
引理2算法2保證在有限的迭代次數(shù)內(nèi)收斂。
2.3.2 計算復雜度分析
(a)兩個無人機的軌跡
圖3給出了本文所提算法的收斂曲線,其中M=2。從圖3(a)可以看出,當閾值ε=1時,IoT設(shè)備數(shù)目越多,系統(tǒng)加權(quán)能耗越大,而且曲線最終都會趨于一個定值,這驗證了該算法的收斂性。而且設(shè)備數(shù)目越多,進行切換操作可供選擇的設(shè)備也就越多,從而切換次數(shù)也會隨之增加,該圖也可以驗證這一點。圖3(b)中U=10,從該圖可以看出,縱使算法1中的閾值為不同值,本文所提算法最終也是收斂的。此外,當ε=2時,雖然切換次數(shù)最少,但能耗最大;當ε=0.5時,雖然能耗最小,但切換次數(shù)最多;當ε=1時,能耗和切換次數(shù)都較為適中,因此本文進行其他仿真結(jié)果驗證時均取ε=1。
(a)設(shè)備數(shù)目對收斂性的影響
圖4為包含卸載策略和不包含卸載策略在NOMA和OMA兩種接入方式下的對比圖。在不考慮干擾的情況下,OMA系統(tǒng)中每個設(shè)備的帶寬減小到NOMA情況下的1/U。因此,最大卸載任務(wù)量與發(fā)射功率之間的關(guān)系如下:
(29)
(30)
與地面的NOMA系統(tǒng)相比,UAV在每一時隙位置不一樣,設(shè)備傾向于在信道條件較好的時隙卸載較多的計算任務(wù),因此具有更大的靈活性。從圖4(a)中可以看出,無論采用哪種接入方式,比起本地計算,設(shè)備均傾向于將計算任務(wù)卸載至MEC服務(wù)器。這是因為MEC服務(wù)器的計算能力要比本地計算大得多,可以進一步降低本地計算能耗,相較于OMA接入方式,NOMA接入方式在減少本地計算能耗、卸載能耗和計算能耗方面約為20%。從圖4(b)可以看出,本文所提出的包含卸載策略的算法要比文獻[8]中固定無人機軌跡時的算法在降低能耗方面更為有效。該文獻中的每個設(shè)備會將計算任務(wù)卸載至全部無人機,而本文中每個聯(lián)盟中的設(shè)備只將計算任務(wù)卸載至相應(yīng)的MEC上,因此會減少一部分的卸載能耗。而且,相比前者而言,后者的設(shè)備分配到的計算資源會更多,計算能耗也會更小。此外,比起OMA接入方式,NOMA接入方式在降低能耗方面較為有效。這是因為NOMA系統(tǒng)中有更多的設(shè)備重復使用相同的頻率,這使得設(shè)備占用更大的帶寬來傳輸數(shù)據(jù),此時設(shè)備可以使用較低的發(fā)射功率將其任務(wù)卸載至服務(wù)器從而降低卸載能耗。
(a)不同接入方式在降低能耗方面的對比圖
圖5為IoT設(shè)備數(shù)目U=14,采用不同算法在不同無人機數(shù)目的情況下降低IoT設(shè)備能耗的對比圖。首先,相比于不考慮卸載策略,優(yōu)化卸載策略能進一步降低設(shè)備能耗,這體現(xiàn)了算法的有效性。其次,無人機數(shù)目越多,每個無人機服務(wù)的設(shè)備數(shù)目越少,設(shè)備分配到的計算能力越強。此外,設(shè)備更傾向于將計算任務(wù)卸載至離自己更近的MEC服務(wù)器,因此設(shè)備的能耗會隨著無人機數(shù)目的增大而減小。最后,當無人機數(shù)目越多時,聯(lián)盟數(shù)量也就越多,設(shè)備更傾向于進入干擾較小的聯(lián)盟,雖然可能切換次數(shù)增加,但會進一步減小同信道干擾,從而減小設(shè)備能耗。
圖5 不同算法在無人機數(shù)目不一致時降低設(shè)備能耗的對比圖
為了提升采用NOMA的IoT中MEC系統(tǒng)性能,本文對卸載策略、計算資源分配、功率分配進行聯(lián)合優(yōu)化以最小化系統(tǒng)加權(quán)總能耗。仿真結(jié)果表明,本文提出的方法能夠明顯降低系統(tǒng)加權(quán)總能耗。未來將針對不同種類型的計算任務(wù)開展工作。此外,無人機軌跡優(yōu)化與連續(xù)干擾消除排序之間的矛盾也是目前亟待解決的問題。