周文晨,方維維,李陽(yáng)陽(yáng),薛峰,王子岳

(1.北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院,100044,北京;2.中國(guó)電子科學(xué)研究院創(chuàng)新中心,100041,北京)

近年來(lái),移動(dòng)互聯(lián)網(wǎng)快速發(fā)展,移動(dòng)用戶設(shè)備數(shù)量呈指數(shù)爆炸式增長(zhǎng)[1],移動(dòng)計(jì)算需求不斷升級(jí)。根據(jù)思科公司最新預(yù)測(cè)報(bào)告顯示,2021年全球移動(dòng)數(shù)據(jù)流量將比2016年增長(zhǎng)7倍,全球移動(dòng)設(shè)備數(shù)量將增加到116億[2],但目前以長(zhǎng)距離數(shù)據(jù)傳輸和集中式大數(shù)據(jù)處理為特點(diǎn)的移動(dòng)云計(jì)算不僅占用大量網(wǎng)絡(luò)帶寬,而且傳輸時(shí)延較大,已無(wú)法滿足時(shí)延敏感型業(yè)務(wù),例如無(wú)人駕駛汽車、醫(yī)療大數(shù)據(jù)和智慧城市等的需求[3]。

歐洲電信標(biāo)準(zhǔn)化研究所(ETSI)在2014年首次提出移動(dòng)邊緣計(jì)算(MEC),移動(dòng)設(shè)備可將高復(fù)雜度、高能耗計(jì)算任務(wù)卸載到MEC系統(tǒng)的接入網(wǎng)邊緣節(jié)點(diǎn),例如基站、無(wú)線接入點(diǎn)等,從而獲得低時(shí)延、近距離的本地化云服務(wù)[4]。MEC系統(tǒng)結(jié)合了移動(dòng)通信[5]和云計(jì)算[6]兩種技術(shù),通過(guò)協(xié)同優(yōu)化通信和計(jì)算資源實(shí)現(xiàn)低能耗、低時(shí)延的計(jì)算卸載服務(wù)。目前,最新的MEC系統(tǒng)研究將關(guān)注點(diǎn)放在單服務(wù)器多用戶條件下的通信、計(jì)算資源分配控制,以實(shí)現(xiàn)總體能耗最優(yōu)。Mao等基于隨機(jī)優(yōu)化模型的優(yōu)化方法,聯(lián)合本地計(jì)算功率、最優(yōu)發(fā)射功率和無(wú)線帶寬資源等約束對(duì)移動(dòng)設(shè)備能耗進(jìn)行優(yōu)化,但是卻無(wú)法有效約束時(shí)延,且計(jì)算復(fù)雜度較大,沒有考慮某個(gè)區(qū)域內(nèi)MEC系統(tǒng)的整體部署優(yōu)化[7];Liu等通過(guò)采用馬爾可夫決策過(guò)程理論對(duì)任務(wù)隊(duì)列的排隊(duì)屬性進(jìn)行分析,提出了發(fā)射功率約束條件下的最小化處理時(shí)延的問(wèn)題,但忽略了設(shè)備的能耗[8];You等針對(duì)TDMA、OFDMA兩種網(wǎng)絡(luò)工作模式,通過(guò)確定卸載量和時(shí)間槽,解決卸載通信和本地計(jì)算總體能耗最小化的凸優(yōu)化問(wèn)題,但是所提算法需要依賴于本機(jī)計(jì)算能量和信道增益的先驗(yàn)知識(shí)做出資源分配策略,降低了實(shí)際場(chǎng)景的可用性[9]。

綜上所述,本文以MEC系統(tǒng)的多服務(wù)器、多用戶的大規(guī)模場(chǎng)景下的計(jì)算卸載的時(shí)延和能耗的平衡為研究目標(biāo),基于邊緣計(jì)算的通信和計(jì)算資源的耦合約束,設(shè)計(jì)一種基于馬爾可夫近似的分布式發(fā)射功率優(yōu)化算法(TPO)。該算法基于馬爾可夫狀態(tài)概率跳轉(zhuǎn)規(guī)則設(shè)計(jì),移動(dòng)用戶設(shè)備自主決策計(jì)算卸載的服務(wù)器對(duì)象,從而有效降低系統(tǒng)級(jí)用戶功耗。理論證明,分布式TPO算法具有穩(wěn)態(tài)概率分布的馬爾可夫鏈,所設(shè)計(jì)的轉(zhuǎn)移速率滿足馬爾可夫鏈的狀態(tài)相互轉(zhuǎn)換條件;實(shí)驗(yàn)仿真結(jié)果表明,所提算法顯著優(yōu)于基準(zhǔn)算法,并在有效時(shí)間內(nèi)逼近最優(yōu)解決方案。

1 MEC系統(tǒng)建模

本文研究的MEC系統(tǒng)場(chǎng)景示例如圖1所示。根據(jù)已有的相關(guān)研究,本文基于以下5種假設(shè):①每個(gè)邊緣服務(wù)器時(shí)間和頻率完全同步;②每個(gè)邊緣服務(wù)器上的每個(gè)載波的信道增益在特定時(shí)間內(nèi)保持恒定;③由于每個(gè)邊緣服務(wù)器的載波頻率不同,假設(shè)MEC系統(tǒng)中邊緣服務(wù)器間不存在信號(hào)干擾;④設(shè)備同一時(shí)刻只能與一個(gè)邊緣服務(wù)器進(jìn)行連通;⑤卸載所需要執(zhí)行的指令都可以利用邊緣服務(wù)器進(jìn)行處理[10-13]。

圖1 多MEC服務(wù)器多用戶設(shè)備場(chǎng)景示例

假設(shè)當(dāng)前區(qū)域內(nèi)有M個(gè)邊緣服務(wù)器X={1,2,…,M}和N個(gè)移動(dòng)用戶設(shè)備Y={1,2,…,N}。每個(gè)移動(dòng)用戶設(shè)備n的計(jì)算任務(wù)卸載到邊緣服務(wù)器m,設(shè)備n必須傳送所有信息到服務(wù)器m。設(shè)定執(zhí)行程序的參數(shù):①每秒輸入比特?cái)?shù);②需要被MEC服務(wù)器執(zhí)行計(jì)算的指令集;③每秒輸出比特?cái)?shù)。對(duì)于移動(dòng)用戶設(shè)備n所需要卸載到服務(wù)器m的計(jì)算任務(wù)的輸入數(shù)據(jù)大小為Cmn,執(zhí)行的指令數(shù)為Dmn=Dmn(Cmn)。設(shè)備n是否卸載計(jì)算任務(wù)到服務(wù)器m主要取決于如下因素:需要被處理的指令數(shù)、設(shè)備n與對(duì)應(yīng)服務(wù)器m之間的無(wú)線信道狀況和服務(wù)器m的并行多個(gè)進(jìn)程的能力大小,同時(shí)每個(gè)進(jìn)程為了用戶的滿意體驗(yàn)都規(guī)定了不應(yīng)超過(guò)的最大時(shí)延[14],因此移動(dòng)用戶設(shè)備n決定卸載計(jì)算任務(wù)到服務(wù)器m之前必須考慮時(shí)延約束。在沒有解碼錯(cuò)誤的前提下,用戶設(shè)備n的時(shí)延應(yīng)該包含將輸入信息傳輸?shù)綄?duì)應(yīng)服務(wù)器m的時(shí)間、服務(wù)器m執(zhí)行指令所需的時(shí)間和將結(jié)果返回給設(shè)備n的時(shí)間。

根據(jù)香農(nóng)定理,在加性白高斯噪聲(AWGN)、信道帶寬為B的信道上傳送Cmn數(shù)據(jù)所需的最小時(shí)間為

(1)

式中:Pn是設(shè)備n計(jì)算任務(wù)卸載的發(fā)射功率;|Hmn|2是信道衰落系數(shù)(歸一化距離);Gmn是信噪比裕度;dmn是設(shè)備n和相連MEC服務(wù)器m的物理距離;γ是路徑損耗指數(shù);N0是噪聲功率。Pn是可調(diào)功率,Pn∈S,S是有限離散集合。

(2)

服務(wù)器m執(zhí)行指令所需的時(shí)間與其資源分配方式有直接關(guān)聯(lián)。系統(tǒng)內(nèi)用戶設(shè)備與服務(wù)器的連接方式表示為

(3)

(4)

忽略服務(wù)器m把計(jì)算結(jié)果返回給設(shè)備n的極短時(shí)間[11],則設(shè)備n的平均計(jì)算卸載的時(shí)延為

(5)

(6)

Pn∈S,n∈Y

xmn∈{0,1},m∈X,n∈Y

基于香農(nóng)定理和鏈路傳輸特性將用戶功率最小化策略建模成問(wèn)題(6),作為典型的組合網(wǎng)絡(luò)優(yōu)化問(wèn)題,其求解復(fù)雜度是NP難的,一般只能通過(guò)集中式的窮舉搜索獲得最優(yōu)解[15],可行解空間隨著網(wǎng)絡(luò)規(guī)模的增大而呈指數(shù)級(jí)增加,而隨機(jī)法又不能獲得穩(wěn)定而較優(yōu)的解,因此有必要尋求一種有效和穩(wěn)定的求解方法。

2 TPO算法設(shè)計(jì)

針對(duì)問(wèn)題(6),設(shè)計(jì)了一種分布式并發(fā)的優(yōu)化算法,利用Log-Sum-Exp函數(shù)[15]將問(wèn)題轉(zhuǎn)化為最小權(quán)重配置的近似問(wèn)題,然后使用馬爾可夫近似[15]求解問(wèn)題,即通過(guò)求解轉(zhuǎn)化后的問(wèn)題從而趨近問(wèn)題(6)的最優(yōu)解,并證明算法可進(jìn)行有效求解。

2.1 Log-Sum-Exp原則

設(shè)定配置f={xmn,m∈X,n∈Y},即問(wèn)題(6)所表示的系統(tǒng)中移動(dòng)用戶設(shè)備n和邊緣服務(wù)器m相連的可行配置狀態(tài),所有可行的狀態(tài)f組成F,即f∈F,則問(wèn)題(6)的等效問(wèn)題模型是

(7)

問(wèn)題(7)是NP難的網(wǎng)絡(luò)組合優(yōu)化問(wèn)題,對(duì)實(shí)際系統(tǒng)來(lái)說(shuō)可行集合F非常大,因此通過(guò)Log-Sum-Exp函數(shù),將問(wèn)題(7)近似轉(zhuǎn)化為

(8)

式中β是正的常數(shù)。因?yàn)閱?wèn)題(8)的目標(biāo)函數(shù)對(duì)于所有的ρf是二次可微、單調(diào)遞增和嚴(yán)格的凹函數(shù),其所有的約束都是線性的,所以Karush-Kuhn-Tucker(KKT)條件對(duì)于最優(yōu)解是必要和充分的,故問(wèn)題(8)的最優(yōu)解是

(9)

與原問(wèn)題(6)相比,近似問(wèn)題(8)存在一個(gè)額外的熵項(xiàng),即為優(yōu)化差距,通過(guò)對(duì)比兩問(wèn)題的表達(dá)式可知優(yōu)化差距的上限是

(10)

從式(10)可知,優(yōu)化差距上限的大小取決于β,當(dāng)β增加時(shí),優(yōu)化差距上限會(huì)減小,這意味著近似求解結(jié)果更加準(zhǔn)確,優(yōu)化差距上限r(nóng)*=lb|F|/β,此時(shí)ρf=1/|F|,f∈F,同時(shí)由文獻(xiàn)[16]可知,當(dāng)β增加時(shí),收斂時(shí)間將增加。

綜上可知,當(dāng)β增加時(shí),近似求解獲得的系統(tǒng)移動(dòng)用戶設(shè)備發(fā)射總功率更加準(zhǔn)確,因此選擇相對(duì)較大的β來(lái)獲得穩(wěn)態(tài)分布。通過(guò)馬爾可夫近似獲得的近似系統(tǒng)功率可表示為

(11)

2.2 TPO算法設(shè)計(jì)

根據(jù)文獻(xiàn)[15]可知,狀態(tài)轉(zhuǎn)移速率有很多設(shè)計(jì)選擇,將其設(shè)計(jì)為

(12)

馬爾可夫鏈通常具有分布式的結(jié)構(gòu),因此可以設(shè)計(jì)分布式算法以實(shí)現(xiàn)符合馬爾可夫鏈的移動(dòng)用戶設(shè)備的決策算法[17]。算法設(shè)計(jì)的關(guān)鍵是建立不同配置f之間的鏈接,實(shí)現(xiàn)最小化轉(zhuǎn)換配置的系統(tǒng)級(jí)功率,通過(guò)每次只執(zhí)行一個(gè)用戶設(shè)備切換服務(wù)器的選擇來(lái)連接系統(tǒng)兩個(gè)配置的鏈接。本文將算法命名為發(fā)射功率優(yōu)化(TPO)算法,TPO算法分為以下4個(gè)步驟。

步驟1每個(gè)移動(dòng)用戶設(shè)備隨機(jī)選擇MEC服務(wù)器,初始化計(jì)算資源和設(shè)備時(shí)延約束等信息。

步驟2當(dāng)前狀態(tài)定義為配置f,每個(gè)用戶設(shè)備計(jì)算自己的發(fā)射功率并廣播,同時(shí)生成均值為ζ的指數(shù)分布隨機(jī)數(shù),根據(jù)隨機(jī)數(shù)進(jìn)行倒計(jì)時(shí),最先到期的用戶設(shè)備n將隨機(jī)切換到新MEC服務(wù)器,并通知其他所有用戶設(shè)備終止倒計(jì)時(shí)。

步驟3進(jìn)入新配置f′,每個(gè)用戶設(shè)備重新計(jì)算自己的發(fā)射功率并廣播。用戶設(shè)備n根據(jù)配置f和f′的系統(tǒng)移動(dòng)用戶設(shè)備發(fā)射總功率的改變做出決策,以概率ρf,f′停留在新的MEC服務(wù)器或者以概率(1-ρf,f′)切換到原先的MEC服務(wù)器,其中

(13)

步驟4重復(fù)步驟2～步驟4,直至收斂。

2.3 TPO算法可行性證明

定理1TPO算法實(shí)現(xiàn)了一個(gè)時(shí)間可逆的馬爾可夫鏈,其穩(wěn)態(tài)分布如式(9)所示。

證明通過(guò)算法步驟2的移動(dòng)用戶設(shè)備的轉(zhuǎn)換條件可知,所有配置可以在有限轉(zhuǎn)換次數(shù)內(nèi)相互可達(dá),因此構(gòu)造的馬爾可夫鏈?zhǔn)遣豢杉s的。此外,它是具有唯一穩(wěn)態(tài)分布的有限狀態(tài)遍歷馬爾可夫鏈?，F(xiàn)在證明穩(wěn)態(tài)分布表達(dá)式是式(9)。

基于式(12)設(shè)定的系統(tǒng)狀態(tài)轉(zhuǎn)移速率可得

(14)

它滿足細(xì)致平衡等式,證畢。

定理2通過(guò)上述完備的馬爾可夫鏈設(shè)計(jì),對(duì)于任意兩個(gè)滿足相互轉(zhuǎn)換條件的配置f,f′∈F,轉(zhuǎn)移速率是式(12)。

證明從系統(tǒng)的角度來(lái)看,狀態(tài)f轉(zhuǎn)移到狀態(tài)f′是由于配置f下的設(shè)備n切換服務(wù)器所致,設(shè)備n從已連接的MEC服務(wù)器斷開,隨機(jī)切換到新的服務(wù)器,可切換的服務(wù)器有M-1個(gè)。故對(duì)于設(shè)備n離開狀態(tài)f轉(zhuǎn)移概率為

其中配置f∈F是馬爾可夫鏈的狀態(tài)之一,因?yàn)樵O(shè)備根據(jù)均值為ζ的指數(shù)分布隨機(jī)數(shù)進(jìn)行倒計(jì)時(shí),倒計(jì)時(shí)結(jié)束后進(jìn)行服務(wù)器切換,因此狀態(tài)f轉(zhuǎn)移到狀態(tài)f′的轉(zhuǎn)移速率為

因此,轉(zhuǎn)移速率與式(12)相等,證畢。

本文算法滿足近似最優(yōu)解,是可行設(shè)計(jì)。

3 仿真與結(jié)果分析

3.1 實(shí)驗(yàn)設(shè)置

為了驗(yàn)證TPO算法的有效性和穩(wěn)定性,采用C++編程進(jìn)行仿真實(shí)驗(yàn),與隨機(jī)法和窮舉法的實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比,得到關(guān)鍵參數(shù)對(duì)系統(tǒng)的影響。參數(shù)設(shè)置見表1[11,18]。移動(dòng)用戶設(shè)備n的輸入數(shù)據(jù)大小Cmn設(shè)定為(0.2+0.02n)MB,為簡(jiǎn)化起見,設(shè)定MEC服務(wù)器執(zhí)行的指令數(shù)Dmn與輸入數(shù)據(jù)大小Cmn成線性相關(guān),即Dmn=σCmn。集合S={0w,10-2w,2×10-2w,…,10w}。

表1 TPO算法仿真參數(shù)

3.2 實(shí)驗(yàn)結(jié)果分析

因采用窮舉搜索獲得系統(tǒng)N個(gè)移動(dòng)用戶設(shè)備與M個(gè)MEC服務(wù)器的連接方式的最優(yōu)解共需計(jì)算MN次,復(fù)雜度過(guò)高,因此我們將TPO算法與隨機(jī)法實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比。圖2分別給出了TPO算法與隨機(jī)法得到的系統(tǒng)用戶設(shè)備發(fā)射總功率。從圖2可知,雖然TPO算法實(shí)現(xiàn)的系統(tǒng)用戶設(shè)備發(fā)射總功率平均值在算法執(zhí)行初期比隨機(jī)法平均值大,但是在50次迭代后小于隨機(jī)法平均值。TPO算法實(shí)現(xiàn)的總功率均值隨著算法迭代次數(shù)逐步下降,可收斂至4.6 W,而多次隨機(jī)法的均值為21.4 W,由此可推算出TPO算法性能比隨機(jī)法的效果提升了78.5%,因此TPO算法不僅可行,并且得到的收斂解比隨機(jī)法結(jié)果更趨近最優(yōu)解,更加有效。

圖2 TPO算法與隨機(jī)法對(duì)比

為了進(jìn)一步驗(yàn)證TPO算法的準(zhǔn)確性,建立4個(gè)MEC服務(wù)器服務(wù)10個(gè)用戶設(shè)備的小型MEC系統(tǒng)場(chǎng)景,在此場(chǎng)景下對(duì)比分析TPO算法多次實(shí)驗(yàn)平均值和窮舉搜索最優(yōu)結(jié)果。圖3給出了TPO算法與窮舉搜索實(shí)現(xiàn)的系統(tǒng)用戶設(shè)備發(fā)射總功率。實(shí)驗(yàn)數(shù)據(jù)顯示,TPO算法實(shí)現(xiàn)的系統(tǒng)用戶設(shè)備發(fā)射總功率均值僅在第130次迭代后逼近最優(yōu)解,遠(yuǎn)小于理論優(yōu)化差距,與窮舉法的410計(jì)算次數(shù)相比,TPO算法復(fù)雜度大大降低,更具有實(shí)際應(yīng)用價(jià)值。

圖3 TPO算法與窮舉搜索結(jié)果對(duì)比

以上實(shí)驗(yàn)結(jié)果驗(yàn)證了TPO算法的有效性和實(shí)用性,下面將分析系統(tǒng)關(guān)鍵參數(shù)對(duì)TPO算法結(jié)果的影響。圖4顯示了TPO算法的參數(shù)β對(duì)算法收斂時(shí)間和系統(tǒng)用戶設(shè)備發(fā)射總功率的影響。從圖4中可知,當(dāng)β=20時(shí),系統(tǒng)總功率接近最優(yōu)解,收斂時(shí)間較長(zhǎng);當(dāng)β=5時(shí),系統(tǒng)總功率遠(yuǎn)離最優(yōu)解,收斂時(shí)間較短。因此伴隨β的增加,TPO算法獲得的近似系統(tǒng)總功率越接近最優(yōu)值,同時(shí)收斂時(shí)間增加,符合式(10)理論結(jié)果。

圖4 系統(tǒng)用戶設(shè)備發(fā)射總功率與β的關(guān)系

圖5是將所有移動(dòng)用戶設(shè)備的輸入數(shù)據(jù)大小Cmn設(shè)定為相同值并統(tǒng)一調(diào)整,觀察系統(tǒng)用戶設(shè)備總功率與設(shè)備所需計(jì)算卸載的輸入數(shù)據(jù)量大小Cmn的關(guān)系。從圖5可以看出,當(dāng)Cmn越大,TPO算法實(shí)現(xiàn)的系統(tǒng)用戶設(shè)備的總發(fā)射功率會(huì)增大,這是因?yàn)樵O(shè)備需要更多的能耗傳輸更多的數(shù)據(jù),但是總發(fā)射功率的收斂時(shí)間并沒有伴隨Cmn增加發(fā)生顯著變化,說(shuō)明當(dāng)設(shè)備的輸入比特量增加時(shí),TPO算法的收斂速度會(huì)更快,這對(duì)實(shí)際系統(tǒng)中用戶設(shè)備計(jì)算卸載高峰期的處理具有很大的優(yōu)勢(shì)。

圖5 系統(tǒng)用戶設(shè)備發(fā)射總功率與Cmn的關(guān)系

為了顯示TPO算法對(duì)用戶設(shè)備資源分配的調(diào)節(jié)效果,建立了用戶設(shè)備高度聚集的特殊場(chǎng)景,將TPO算法與其他常用算法的處理效果進(jìn)行對(duì)比。通過(guò)觀察可知,圖6b中傳統(tǒng)的依賴接收信號(hào)強(qiáng)度指示(RSSI)進(jìn)行連接的方式會(huì)導(dǎo)致MEC服務(wù)器資源分配不合理,進(jìn)而無(wú)法滿足用戶需求,圖6c中隨機(jī)法實(shí)現(xiàn)的系統(tǒng)設(shè)備發(fā)射總功率為48.3 W,圖6d中TPO算法實(shí)現(xiàn)的系統(tǒng)設(shè)備發(fā)射總功率僅為8.7 W,因此隨機(jī)法的實(shí)驗(yàn)結(jié)果不滿足最小化目標(biāo),而本文提出的TPO算法能夠合理有效地建立移動(dòng)用戶設(shè)備和MEC服務(wù)器的連接,達(dá)到系統(tǒng)設(shè)備發(fā)射總功率優(yōu)化的最優(yōu)效果。

(a)用戶與基站位置 (b)RSSI連接方式

(c)隨機(jī)法連接方式 (d)TPO算法連接方式

4 結(jié) 論

傳統(tǒng)的云計(jì)算模型已無(wú)法有效解決海量的邊緣數(shù)據(jù)計(jì)算卸載問(wèn)題,如何提升移動(dòng)邊緣計(jì)算的大規(guī)模網(wǎng)絡(luò)架構(gòu)的計(jì)算卸載的效率和用戶體驗(yàn)受到越來(lái)越多的關(guān)注。本文在傳輸帶寬和計(jì)算資源參數(shù)化的基礎(chǔ)上,使用馬爾可夫近似框架將系統(tǒng)用戶設(shè)備的發(fā)射功率最小化問(wèn)題轉(zhuǎn)化,設(shè)計(jì)分布式的發(fā)射功率優(yōu)化算法求得原目標(biāo)的近似最優(yōu)解。對(duì)比基準(zhǔn)算法測(cè)試結(jié)果,TPO算法的系統(tǒng)用戶設(shè)備發(fā)射總功率優(yōu)化效果比隨機(jī)法提升了78.5%,同時(shí)執(zhí)行效果更加穩(wěn)定;與窮舉搜索的指數(shù)階O(2n)計(jì)算復(fù)雜度相比,該算法的復(fù)雜度為線性階O(n),故該算法在有限迭代輪次后即可逼近窮舉搜索的最優(yōu)解;與傳統(tǒng)的RSSI連接方式相比,TPO算法能夠避免在用戶量小范圍高度集中時(shí)爭(zhēng)搶計(jì)算資源的現(xiàn)象,減少網(wǎng)絡(luò)擁塞和資源分配不均衡的情況發(fā)生,滿足用戶計(jì)算卸載需求。TPO算法能夠在保證用戶設(shè)備的時(shí)延約束下有效降低系統(tǒng)用戶功耗成本,確保時(shí)延敏感型業(yè)務(wù)的時(shí)延約束下的用戶體驗(yàn)。