一種基于K-shell影響力最大化的路徑擇優(yōu)計(jì)算遷移算法

樂光學(xué) 陳光魯 盧 敏 楊曉慧 劉建華 黃淳嵐 楊忠明

1(嘉興學(xué)院信息科學(xué)與工程學(xué)院 浙江嘉興 314001) 2(國網(wǎng)冀北電力有限公司大城縣供電分公司 河北廊坊 065000) 3(江西理工大學(xué)理學(xué)院 江西贛州 341000)

隨著通信技術(shù)與智能終端設(shè)備的快速發(fā)展和應(yīng)用普及，流式服務(wù)已成為移動(dòng)網(wǎng)絡(luò)承載的重要業(yè)務(wù)之一，對(duì)智能終端設(shè)備性能提出了更高的要求.受計(jì)算能力、存儲(chǔ)容量、電池能耗、設(shè)計(jì)美觀等限制，移動(dòng)智能設(shè)備(mobile smart device,MSD)無法完成資源需求大、計(jì)算任務(wù)重的密集型任務(wù).為解決該問題，資源豐富的云計(jì)算模型作為有效方案之一應(yīng)運(yùn)而生，并由此已演化出霧計(jì)算、邊緣計(jì)算等先進(jìn)的計(jì)算模式.5G技術(shù)的日漸成熟和應(yīng)用推廣，使得無線移動(dòng)網(wǎng)絡(luò)承載數(shù)據(jù)和業(yè)務(wù)量將以線性增長(zhǎng)，流式多元化網(wǎng)絡(luò)業(yè)務(wù)和服務(wù)的快速增長(zhǎng)必將導(dǎo)致網(wǎng)絡(luò)擁塞、數(shù)據(jù)丟失等問題，傳統(tǒng)的云計(jì)算已無法滿足終端對(duì)高帶寬、低時(shí)延和實(shí)時(shí)性的需求[1].

為了解決云計(jì)算的不足，新出現(xiàn)的網(wǎng)絡(luò)計(jì)算模式在終端用戶附近提供計(jì)算資源，并根據(jù)應(yīng)用需求將數(shù)據(jù)就近處理[2]，如透明計(jì)算、cloudlet[3]、邊緣計(jì)算、霧計(jì)算[4]和移動(dòng)邊緣計(jì)算等.cloudlet和霧計(jì)算的計(jì)算能力未集成到移動(dòng)網(wǎng)絡(luò)中，導(dǎo)致服務(wù)質(zhì)量降低.移動(dòng)邊緣計(jì)算較其他計(jì)算模式更側(cè)重于無線接入網(wǎng)絡(luò)[5]，具有低時(shí)延、低能耗等優(yōu)點(diǎn).為了降低傳輸延遲，2014年歐洲電信標(biāo)準(zhǔn)協(xié)會(huì)提出移動(dòng)邊緣計(jì)算(mobile edge computing,MEC)，將延遲敏感的應(yīng)用程序遷移到距離較近的邊緣服務(wù)器(edge server,ES)進(jìn)行計(jì)算與存儲(chǔ)，并在2016年把MEC的概念擴(kuò)展為“多接入邊緣計(jì)算”(multi-access edge computing,MEC)，將MEC從電信蜂窩網(wǎng)絡(luò)進(jìn)一步延伸至其他無線接入網(wǎng)絡(luò)(如WiFi).計(jì)算遷移是MEC研究的關(guān)鍵問題之一.終端根據(jù)實(shí)際應(yīng)用場(chǎng)景指定不同的卸載策略時(shí)需考慮何時(shí)遷移、在何處遷移、如何遷移、遷移哪部分等，最終達(dá)到能耗與系統(tǒng)性能的平衡，提升用戶的服務(wù)質(zhì)量和體驗(yàn)質(zhì)量.

目前，計(jì)算遷移算法性能優(yōu)化目標(biāo)主要集中在能耗、時(shí)延以及兩者的聯(lián)合優(yōu)化.

1)以能耗為優(yōu)化目標(biāo).文獻(xiàn)[6]研究了基于非正交多址(non-orthogonal multiple access,NOMA)的節(jié)能多任務(wù)多址MEC，對(duì)任務(wù)計(jì)算卸載、本地計(jì)算資源分配和NOMA傳輸持續(xù)時(shí)間進(jìn)行聯(lián)合優(yōu)化，以最小化終端完成所有任務(wù)的總能耗為目標(biāo).文獻(xiàn)[7]研究了移動(dòng)邊緣計(jì)算遷移面臨的可擴(kuò)展性問題，提出一個(gè)輕量級(jí)的請(qǐng)求和準(zhǔn)入框架解決可伸縮性問題，設(shè)計(jì)選擇性遷移方案，最小化設(shè)備能耗.此外，文獻(xiàn)[8-11]考慮不同的應(yīng)用場(chǎng)景和約束，構(gòu)建相應(yīng)的優(yōu)化模型，實(shí)現(xiàn)最小化能耗.

2)以時(shí)延為優(yōu)化目標(biāo).文獻(xiàn)[12]基于無人機(jī)群的三維分布構(gòu)建了一個(gè)聯(lián)合通信與計(jì)算優(yōu)化模型，利用隨機(jī)幾何和排隊(duì)論，實(shí)現(xiàn)了最優(yōu)響應(yīng)時(shí)延.文獻(xiàn)[13]提出了一種低延遲的安全移動(dòng)邊緣計(jì)算系統(tǒng)，該系統(tǒng)優(yōu)化用戶的傳輸功率、計(jì)算容量分配和用戶關(guān)聯(lián)，在保證安全的資源約束條件下最小化用戶計(jì)算和傳輸延遲.

3)以聯(lián)合優(yōu)化能耗和延遲為目標(biāo).文獻(xiàn)[14]研究了物聯(lián)網(wǎng)邊緣云計(jì)算系統(tǒng)中的工作負(fù)載分配問題，基于時(shí)延和能耗約束設(shè)計(jì)智能算法，實(shí)現(xiàn)本地、邊緣和云計(jì)算服務(wù)器的負(fù)載均衡.文獻(xiàn)[15]定義能耗和時(shí)延之間折中的代價(jià)函數(shù)，提出了一種MEC輔助的計(jì)算和中繼方案，獲得移動(dòng)設(shè)備和中繼節(jié)點(diǎn)的最佳傳輸和壓縮策略.另外，文獻(xiàn)[16-20]針對(duì)不同場(chǎng)景下任務(wù)遷移的能耗與時(shí)延構(gòu)建系統(tǒng)模型，平衡兩者間關(guān)系，提升用戶體驗(yàn)質(zhì)量(quality of experience,QoE).文獻(xiàn)[21]利用低秩矩陣?yán)碚撆c邊緣計(jì)算去中心化的計(jì)算能力來處理大量交通數(shù)據(jù)，以實(shí)現(xiàn)精確和實(shí)時(shí)的恢復(fù).

若將密集型任務(wù)遷移到一個(gè)ES時(shí)，當(dāng)前ES由于達(dá)到負(fù)載閾值而無法完成，產(chǎn)生新的等待時(shí)延.根據(jù)分布式計(jì)算模式的特點(diǎn)，可將無法完成的任務(wù)遷移到相鄰空閑的ES上進(jìn)行計(jì)算，通過多個(gè)ES協(xié)作完成.因此，選擇ES路徑問題是關(guān)鍵.由于該問題為非凸優(yōu)化問題，即NP難問題，與影響力最大化問題本質(zhì)為同一問題.因此，可將ES路徑擇優(yōu)問題轉(zhuǎn)化為社會(huì)網(wǎng)絡(luò)中影響力最大化問題.

針對(duì)社會(huì)網(wǎng)絡(luò)影響力最大化問題，Kempe等人[22]首次提出運(yùn)用貪心算法求解.隨后，基于貪心策略改進(jìn)的算法被大量提出.例如，利用影響力函數(shù)子模性的CELF(cost-effective lazy-forward)算法[23]、優(yōu)化CELF算法后的CELF++算法[24]、將社會(huì)網(wǎng)絡(luò)圖縮小化后的NewGreedy算法[25]等.但貪心算法時(shí)間復(fù)雜度較高，無法適應(yīng)于大型網(wǎng)絡(luò).因此，大量啟發(fā)式算法被提出，最早的啟發(fā)式算法是依據(jù)節(jié)點(diǎn)中心度來判斷節(jié)點(diǎn)影響力大小[26].隨后，基于度中心方法優(yōu)化的DegreeDiscount算法[25]、利用K-shell算法的核覆蓋算法(core covering algorithm,CCA)[27]、考慮鄰居節(jié)點(diǎn)距離遠(yuǎn)近損耗的PageRank算法[28]、利用反向排名信息和鄰居節(jié)點(diǎn)影響的逆向節(jié)點(diǎn)排名(reversed node ranking,RNR)算法[29]等相繼被提出，有效解決了貪心算法時(shí)間開銷較大等問題.其中，文獻(xiàn)[27]提出的CCA算法充分考慮選取種子節(jié)點(diǎn)影響范圍的重疊情況，基于K-shell分解求解出每個(gè)節(jié)點(diǎn)的核數(shù)，然后根據(jù)核數(shù)分布的層次性，引入節(jié)點(diǎn)的影響半徑參數(shù)，最后綜合核數(shù)和度數(shù)2個(gè)屬性找出影響力節(jié)點(diǎn)集合.但啟發(fā)式算法精準(zhǔn)度較低，故有些研究者將2類算法相結(jié)合進(jìn)行求解.例如，Chen等人[30]用最大影響力路徑來估算影響力的傳播，并提出了最大化影響力樹狀(maximum influence arborescence,MIA)算法進(jìn)行求解該問題；Kim等人[31]結(jié)合貪心算法的精確度和啟發(fā)式算法的高效率提出了獨(dú)立路徑算法(independent path algorithm,IPA)，通過設(shè)置閾值，將傳播路徑的概率近似為影響函數(shù)，縮短了運(yùn)行時(shí)間.

本文將MEC計(jì)算遷移路徑最優(yōu)化轉(zhuǎn)化為社會(huì)網(wǎng)絡(luò)影響力最大化問題，充分考慮網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中ES的位置及屬性，構(gòu)建計(jì)算遷移路徑優(yōu)化選擇算法，對(duì)不同ES通過K-shell算法進(jìn)行分等級(jí)處理，有效減少ES路徑搜索消耗成本.其核心思想是將ES類比為社會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)，通過K-shell算法定義ES路徑影響力，提出K-shell影響力最大化計(jì)算遷移(K-shell influence maximization computation off-loading,Ks-IMCO)算法，有效降低能耗與時(shí)延，提高用戶體驗(yàn)質(zhì)量.

1 計(jì)算遷移系統(tǒng)建模與策略研究

假設(shè)由1個(gè)基站、n個(gè)邊緣服務(wù)器和m個(gè)智能終端組成的移動(dòng)邊緣計(jì)算場(chǎng)景.n個(gè)ES共同構(gòu)成網(wǎng)絡(luò)G(P,E)，其中，P為邊緣服務(wù)器構(gòu)成的集合，P={pi|i=1,2,…,n}，E為邊緣服務(wù)器連接矩陣.m個(gè)終端集合形式表示為D={dk|k=1,2,…,m}.終端dk的計(jì)算任務(wù)Rdk包括本地計(jì)算任務(wù)Rloc,dk和遷移計(jì)算任務(wù)Rtran,dk.如圖1所示，終端與基站關(guān)聯(lián)的ES通過正交頻分復(fù)用(OFDMA)進(jìn)行通信.

Fig.1 Multi-user mobile edge computing scenario圖1 多用戶移動(dòng)邊緣計(jì)算應(yīng)用場(chǎng)景

考慮到終端計(jì)算能力受限，根據(jù)計(jì)算復(fù)雜度δk分割任務(wù)，dk在本地執(zhí)行復(fù)雜度較低的任務(wù)，將復(fù)雜度高的任務(wù)遷移到ES執(zhí)行.因此，使用二元變量δk∈{0,1}表示終端的決策，δk=0表示本地執(zhí)行；δk=1表示遷移到ES執(zhí)行，并將結(jié)果返回終端.計(jì)算遷移決策流程圖如圖2所示.

Fig.2 Computation offloading process[32]圖2 計(jì)算遷移流程圖[32]

1.1 任務(wù)本地計(jì)算建模與分析

在本地計(jì)算時(shí)，設(shè)終端dk分配的任務(wù)Rloc,dk運(yùn)行功率為Ploc,dk，CPU頻率為floc,dk，則本地計(jì)算所需時(shí)延Tloc,dk與能耗Eloc,dk可采用文獻(xiàn)[33]中系統(tǒng)模型的構(gòu)建思想表示為

(1)

(2)

由式(1)(2)得到本地服務(wù)質(zhì)量公式Qloc,dk：

(3)

1.2 基于路徑擇優(yōu)的計(jì)算遷移策略建模

為解決ES資源受限引起的多用戶并發(fā)訪問，導(dǎo)致網(wǎng)絡(luò)堵塞.密集型任務(wù)模擬選擇ES進(jìn)行遷移，獲得最佳遷移路線，即ES路徑L′={p1,p2,…,pl}，其中l(wèi)≤n.

(4)

當(dāng)前ES因資源受限無法完成終端dk遷移到邊緣的任務(wù)Rtran,dk時(shí)，綜合考慮計(jì)算任務(wù)在傳輸、計(jì)算過程中的時(shí)延與能耗，將部分任務(wù)遷移到相鄰ES.其中計(jì)算任務(wù)的傳輸包括上行傳輸、邊緣網(wǎng)絡(luò)內(nèi)傳輸和下行傳輸3部分.

遷移請(qǐng)求發(fā)起后，上行傳輸時(shí)延Tloc,mec、ES路徑內(nèi)傳輸時(shí)延Tmec,mec、下行傳輸時(shí)延Tmec,loc可分別表示為[13]：

(5)

上行傳輸能耗Eloc,mec、ES路徑內(nèi)能耗Emec,mec、下行傳輸能耗Emec,loc分別為[15]：

(6)

根據(jù)式(5)(6)得到傳輸時(shí)延Ttran、傳輸能耗Etran分別為

Ttran=Tloc,mec+Tmec,mec+Tmec,loc，

(7)

Etran=Eloc,mec+Emec,mec+Emec,loc.

(8)

任務(wù)計(jì)算時(shí)，分別構(gòu)建任務(wù)計(jì)算時(shí)延Tmec與計(jì)算能耗Emec模型[15]：

(9)

(10)

根據(jù)任務(wù)傳輸和計(jì)算開銷，得到任務(wù)遷移計(jì)算所需要的時(shí)延Tcount,dk與能耗Ecount,dk分別為

Tcount,dk=Ttran+Tmec,

(11)

Ecount,dk=Etran+Emec.

(12)

由式(11)(12)得到遷移計(jì)算服務(wù)質(zhì)量公式Qcount,dk：

Qcount,dk=αTcount,dk+βEcount,dk,

(13)

綜上所述，任務(wù)遷移需要的總時(shí)延Ttotal,dk與總能耗Etotal,dk分別表示為

Ttotal,dk=Tloc,dk+Tcount,dk,

(14)

Etotal,dk=Eloc,dk+Ecount,dk.

(15)

由式(14)(15)得到任務(wù)遷移服務(wù)質(zhì)量公式Qtotal,dk：

Qtotal,dk=αTtotal,dk+βEtotal,dk,

(16)

2 計(jì)算遷移路徑選擇優(yōu)化策略

2.1 基于K-shell算法邊緣服務(wù)器劃分與計(jì)算遷移優(yōu)化策略

在研究網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中，節(jié)點(diǎn)重要性度量方法常用指標(biāo)有度中心性[34]、介數(shù)中心性[35]、緊密中心性[36]等.度中心性只關(guān)注了節(jié)點(diǎn)周圍鄰居數(shù)量，而介數(shù)中心性與緊密中心性需計(jì)算最短入境從而導(dǎo)致時(shí)間復(fù)雜度較高.文獻(xiàn)[37]提出了節(jié)點(diǎn)重要程度依賴于所處網(wǎng)絡(luò)中位置的思想，圖論中經(jīng)典的K-shell算法[38]充分利用了這一思想，能夠準(zhǔn)確有效地識(shí)別節(jié)點(diǎn)在網(wǎng)絡(luò)中的影響力.

K-shell算法是通過層層剝離的方式對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)進(jìn)行分類.本文將網(wǎng)絡(luò)中ES類比為節(jié)點(diǎn)，采用K-shell算法進(jìn)行等級(jí)劃分，通過網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)區(qū)分ES在網(wǎng)絡(luò)中的不同位置.假設(shè)網(wǎng)絡(luò)內(nèi)包含節(jié)點(diǎn)為a，b，…，q，r，如圖3所示.具體分類過程為：

Fig.3 K-shell algorithm schematic[39]圖3 K-shell算法示意圖[39]

首先去除網(wǎng)絡(luò)內(nèi)度數(shù)最低(度數(shù)為1)的節(jié)點(diǎn)，即a，b，c，e，q，r標(biāo)記ks=1；剩余的節(jié)點(diǎn)又會(huì)組成新的網(wǎng)絡(luò)，此時(shí)度數(shù)最少的節(jié)點(diǎn)為d,o,p,n，m，l，k，j，這些節(jié)點(diǎn)的ks=2；以此類推，直到網(wǎng)絡(luò)中所有的節(jié)點(diǎn)都具有ks值.

針對(duì)CCA算法[27]中所考慮種子節(jié)點(diǎn)間的覆蓋范圍重合的問題，結(jié)合本文研究問題，考慮任務(wù)傳輸過程中的路徑重疊問題.由于該問題會(huì)導(dǎo)致邊緣服務(wù)器負(fù)載過重，故構(gòu)建路徑重疊(path overlap,PO)算法.

算法1.路徑重疊算法.

輸入:ES網(wǎng)絡(luò)G(P,E);

輸出:路徑集合S(L).

① for 每個(gè)ES

② 根據(jù)路徑生成規(guī)則，查找所有遷移路徑Lall；

③ end for

④ for 每個(gè)Lall

⑤ 搜索重疊路徑；

⑥ end for

考慮ES計(jì)算能力、基站帶寬資源、任務(wù)遷移時(shí)延與能耗因素，以用戶體驗(yàn)質(zhì)量(QoE)作為多終端遷移策略聯(lián)合優(yōu)化目標(biāo)，構(gòu)建近于實(shí)際應(yīng)用環(huán)境的密集型任務(wù)系統(tǒng)模型minQ[11]：

(17)

式(17)為非凸優(yōu)化問題，是一個(gè)NP難問題.針對(duì)NP難問題，以通信質(zhì)量、ES交互頻度等為約束，將其轉(zhuǎn)化為影響力最大化問題用Ks-IMCO算法進(jìn)行求解.

2.2 ES路徑影響力選擇模型

考慮到ES的計(jì)算、傳輸能力的差異性，構(gòu)建ES路徑對(duì)計(jì)算任務(wù)的評(píng)判標(biāo)準(zhǔn)：ES路徑影響力.

ES路徑影響力由其自身影響力與潛在影響力所構(gòu)成.其中，ES自身影響力受ES在網(wǎng)絡(luò)中所處位置與自身屬性影響；潛在影響力主要考慮任務(wù)遷移時(shí)延、能耗和傳輸通信質(zhì)量等.ES路徑影響力選擇模型過程如圖4所示.

Fig.4 ES path influence selection model圖4 ES路徑影響力選擇模型

綜合考慮ES在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)所在位置，利用度中心方法度量ES重要性[26]：

(18)

(19)

潛在影響力表示ES路徑具有的潛在計(jì)算能力，由K-shell方法計(jì)算；σ,Cqua分別表示ES之間的交互頻度和通信質(zhì)量；Ttotal,dk，Etotal,dk分別表示任務(wù)遷移延遲和能耗.則潛在影響力表達(dá)式為

(20)

σ∈(0,20],

其中，D(pi)為鄰居節(jié)點(diǎn)pj的集合，ks為ES所處等級(jí)值，θ為隨機(jī)分布變量，N0為噪聲功率.

綜上，ES路徑影響力計(jì)算表示為

(21)

為了描述一致，將用戶體驗(yàn)質(zhì)量作為計(jì)算遷移策略優(yōu)化目標(biāo)轉(zhuǎn)化為ES路徑影響力最大化問題求解.則有：

(22)

證明.

由式(17)可得：

由式(22)可得：

證畢.

2.3 Ks-IMCO路徑尋優(yōu)算法

根據(jù)ES所處ks等級(jí)，將備選遷移路徑進(jìn)行排隊(duì)，遷移路徑選擇約束條件初始ES只能向同級(jí)或低級(jí)延伸.算法描述為：

步驟3.計(jì)算ES的ks；

步驟6.運(yùn)行PO算法，對(duì)路徑重疊部分選擇其影響力最大路徑進(jìn)行計(jì)算遷移；

步驟7.得到最終計(jì)算遷移路徑.

算法2.K-shell影響力最大化計(jì)算遷移算法.

輸出:路徑集合S(L′).

① for 每個(gè)ES

④ 計(jì)算pi(ks)；

⑤ 根據(jù)路徑生成規(guī)則，查找所有遷移路徑

⑥ end for

⑦ for 每個(gè)MSD任務(wù)Rdk

⑧ ifδk=0

⑨Rloc,dk執(zhí)行本地計(jì)算；

⑩ else ifδk=1

Eloc,dk；

與能耗Ecount,dk；

3 仿真實(shí)驗(yàn)與分析

3.1 仿真實(shí)驗(yàn)設(shè)計(jì)

一個(gè)社區(qū)由多個(gè)MSD與ES構(gòu)成，每個(gè)MSD與ES通過正交頻分復(fù)用(OFDMA)信道相連，各個(gè)信道之間相互獨(dú)立.在同一時(shí)刻，每個(gè)MSD將計(jì)算不同大小的任務(wù)，按照計(jì)算復(fù)雜度策略將任務(wù)進(jìn)行分割，對(duì)于密集型任務(wù)通過信道進(jìn)行計(jì)算遷移，完成多用戶多服務(wù)器的邊緣計(jì)算.具體仿真參數(shù)如表1所示：

Table 1 Simulation Parameter表1 仿真參數(shù)

3.2 算法仿真與性能分析

實(shí)驗(yàn)1.本地計(jì)算與Ks-IMCO算法遷移計(jì)算能耗對(duì)比分析.

本地計(jì)算遷移策略與Ks-IMCO算法遷移計(jì)算進(jìn)行對(duì)比分析，實(shí)驗(yàn)過程中，將每個(gè)MSD任務(wù)隨機(jī)設(shè)為10～100 GB，在500個(gè)ES組成的數(shù)據(jù)集進(jìn)行仿真，觀察MSD數(shù)目由0～500過程中能耗所發(fā)生的變化.Ks-IMCO算法遷移計(jì)算能耗僅計(jì)算MSD分割后任務(wù)的本地計(jì)算能耗與上傳能耗，實(shí)驗(yàn)結(jié)果如圖5、圖6所示:

Fig.5 Comparison of energy consumption betweenKs-IMCO offloading calculation and local calculation圖5 Ks-IMCO遷移計(jì)算與本地計(jì)算的能耗對(duì)比

Fig.6 The percentage of MSD energy saving calculated by Ks-IMCO algorithm offloading圖6 Ks-IMCO算法遷移計(jì)算的MSD節(jié)能百分比

從圖5、圖6可以看出，當(dāng)系統(tǒng)MSD數(shù)目在100時(shí)，Ks-IMCO遷移計(jì)算能耗降低80%以上；系統(tǒng)MSD數(shù)目在100～450時(shí)，Ks-IMCO遷移計(jì)算能耗降低70%以上；當(dāng)系統(tǒng)MSD數(shù)目在350～450時(shí)，Ks-IMCO算法遷移計(jì)算節(jié)能效果趨于穩(wěn)定，維持在70%左右.Ks-IMCO算法遷移計(jì)算能耗明顯小于本地計(jì)算.

實(shí)驗(yàn)2.不同算法能耗與時(shí)延對(duì)比分析.

將Ks-IMCO算法分別與隨機(jī)分配(random allocation,RA)、路徑選擇切換(path selection with handovers,PSwH)算法[20]對(duì)比分析其有效性.

設(shè)Rdk為MSD計(jì)算任務(wù)量.不同數(shù)量級(jí)的任務(wù)量代表不同格式文件，具體劃分如表2所示：

Table 2 Task Volume Division表2 任務(wù)量劃分

針對(duì)Ks-IMCO算法與RA算法、PSwH算法分別在不同場(chǎng)景下進(jìn)行時(shí)延與能耗對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)過程中逐漸增加MSD數(shù)目觀察時(shí)延與能耗性能.為了提高實(shí)驗(yàn)的準(zhǔn)確性，針對(duì)ES網(wǎng)絡(luò)規(guī)模，分別以500，1 000，2 000，5 000的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn).

純文本文件實(shí)驗(yàn)結(jié)果如圖7～10所示:

Fig.7 A network of 500 ES terminals for text files task圖7 500個(gè)ES終端組成的網(wǎng)絡(luò)完成純文本任務(wù)

Fig.8 A network of 1 000 ES terminals for text files task圖8 1 000個(gè)ES終端組成的網(wǎng)絡(luò)完成純文本任務(wù)

Fig.9 A network of 2 000 ES terminals for text files task圖9 2 000個(gè)ES終端組成的網(wǎng)絡(luò)完成純文本任務(wù)

Fig.10 A network of 5 000 ES terminals for text files task圖10 5 000個(gè)ES終端組成的網(wǎng)絡(luò)完成純文本任務(wù)

圖片文件實(shí)驗(yàn)結(jié)果如圖11～14所示.

Fig.11 A network of 500 ES terminals for picture files task圖11 500個(gè)ES終端組成的網(wǎng)絡(luò)完成圖片文件任務(wù)

Fig.12 A network of 1 000 ES terminals for picture files task圖12 1 000個(gè)ES終端組成的網(wǎng)絡(luò)完成圖片文件任務(wù)

Fig.13 A network of 2 000 ES terminals for picture files task圖13 2 000個(gè)ES終端組成的網(wǎng)絡(luò)完成圖片文件任務(wù)

Fig.14 A network of 5 000 ES terminals for picture files task圖14 5 000個(gè)ES終端組成的網(wǎng)絡(luò)完成圖片文件任務(wù)

流式文件實(shí)驗(yàn)結(jié)果如圖15～18所示.

Fig.15 A network of 500 ES terminals for streaming files task圖15 500個(gè)ES終端組成的網(wǎng)絡(luò)完成流式文件任務(wù)

Fig.16 A network of 1 000 ES terminals for streaming files task圖16 1 000個(gè)ES終端組成的網(wǎng)絡(luò)完成流式文件任務(wù)

Fig.17 A network of 2 000 ES terminals for streaming files task圖17 2 000個(gè)ES終端組成的網(wǎng)絡(luò)完成流式文件任務(wù)

Fig.18 A network of 5 000 ES terminals for streaming files task圖18 5 000個(gè)ES終端組成的網(wǎng)絡(luò)完成流式文件任務(wù)

大規(guī)模數(shù)據(jù)流式文件實(shí)驗(yàn)如圖19～22所示.

Fig.19 A network of 500 ES terminals for large-scale data streaming files task圖19 500個(gè)ES終端組成的網(wǎng)絡(luò)完成大規(guī)模數(shù)據(jù)流式文件任務(wù)

Fig.20 A network of 1 000 ES terminals for large-scale data streaming files task圖20 1 000個(gè)ES終端組成的網(wǎng)絡(luò)完成大規(guī)模數(shù)據(jù)流式文件任務(wù)

Fig.21 A network of 2 000 ES terminals for large-scale data streaming files task圖21 2 000個(gè)ES終端組成的網(wǎng)絡(luò)完成大規(guī)模數(shù)據(jù)流式文件任務(wù)

Fig.22 A network of 5 000 ES terminals for large-scale data streaming files task圖22 5 000個(gè)ES終端組成的網(wǎng)絡(luò)完成大規(guī)模數(shù)據(jù)流式文件任務(wù)

從表3可以看出，對(duì)于不同形式的任務(wù)Rdk，當(dāng)ES規(guī)模為500且MSD數(shù)目為500時(shí)，Ks-IMCO算法較RA算法節(jié)能60%～70%，時(shí)延縮短41%～48%，較PSwH算法節(jié)能13%～15%，時(shí)延縮短12%～15%；當(dāng)ES規(guī)模為500且MSD數(shù)目為1 000時(shí)，Ks-IMCO算法較RA算法節(jié)能45%～55%，時(shí)延縮短35%～40%，較PSwH算法節(jié)能24%～26%，時(shí)延縮短30%～36%；當(dāng)ES規(guī)模為500且MSD數(shù)目為2 000時(shí)，Ks-IMCO算法較RA算法節(jié)能65%～70%，時(shí)延縮短43%～55%，較PSwH算法節(jié)能40%～55%，時(shí)延縮短38%～47%；當(dāng)ES規(guī)模為5 000，MSD數(shù)目為500時(shí)，Ks-IMCO算法較RA算法節(jié)能60%～65%，時(shí)延縮短45%～50%，較PSwH算法節(jié)能55%～57%，時(shí)延縮短24%～38%.隨著ES規(guī)模逐漸增大，Ks-IMCO算法對(duì)比RA算法節(jié)能總體維持在60%左右，對(duì)比PSwH算法節(jié)能逐漸增高；Ks-IMCO算法對(duì)比RA，PSwH算法具有較短時(shí)延.因此，從能耗與時(shí)延方面看，Ks-IMCO算法能有效提高用戶服務(wù)質(zhì)量.

Table 3 Algorithm Comparison when Task is Streaming File and ES Number is 500表3 任務(wù)為流式文件、ES數(shù)目為500的算法對(duì)比

4 討論問題與未來工作

對(duì)于邊緣計(jì)算中能耗與時(shí)延優(yōu)化問題影響因素不僅在于路徑的選擇問題，其中也包含在路徑選擇前的任務(wù)分配、ES路徑分布重疊稀疏度問題.

1)任務(wù)分配對(duì)路徑選擇以及能耗和時(shí)延的影響.由于本文中對(duì)于任務(wù)分配進(jìn)行主動(dòng)劃分，故在進(jìn)行計(jì)算遷移時(shí)，任務(wù)進(jìn)行遷移或在本地計(jì)算時(shí)可能對(duì)路徑選擇以及能耗和時(shí)延產(chǎn)生影響.為此，我們進(jìn)行隨機(jī)實(shí)驗(yàn)對(duì)比分析，為使實(shí)驗(yàn)效果最為明顯，選取MSD任務(wù)為10～100 GB范圍內(nèi)進(jìn)行實(shí)驗(yàn).實(shí)驗(yàn)結(jié)果如圖23所示，從圖23(a)中可看出主動(dòng)劃分時(shí)延小于隨機(jī)劃分，圖23(b)中可看出主動(dòng)劃分能耗小于隨機(jī)劃分.在今后的工作中，將研究如何進(jìn)行任務(wù)智能劃分，對(duì)不同終端發(fā)布任務(wù)根據(jù)任務(wù)量以及可遷移路線進(jìn)行智能劃分，進(jìn)一步優(yōu)化遷移計(jì)算能耗與時(shí)延.

Fig.23 The influence of task assignment on energy consumption and delay圖23 任務(wù)分配對(duì)能耗和時(shí)延的影響

2)ES路徑分布重疊稀疏度對(duì)路徑選擇以及能耗和時(shí)延的影響.通過選取不同稀疏的ES路徑分布進(jìn)行實(shí)驗(yàn)結(jié)果如圖24所示.從圖24(a)中可以看出對(duì)于稀疏度高的ES路徑分布圖能耗與稀疏度低的ES路徑分布圖相差無幾,圖24(b)中可以看出對(duì)于稀疏度高的ES路徑分布圖時(shí)延小于稀疏度低的ES路徑分布圖.

Fig.24 The influence of ES path distribution overlap and sparsity on energy consumption and delay圖24 ES路徑分布重疊稀疏度對(duì)能耗和時(shí)延的影響

5 總 結(jié)

本文將邊緣計(jì)算中計(jì)算遷移路徑選擇問題轉(zhuǎn)化為社會(huì)網(wǎng)絡(luò)影響力最大化問題，為計(jì)算遷移路徑擇優(yōu)問題提供了新思路，將問題轉(zhuǎn)換可以有效利用網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行邊緣服務(wù)器分層，節(jié)約路徑搜尋時(shí)間，依據(jù)社會(huì)網(wǎng)絡(luò)影響力最大化問題中的K-shell算法進(jìn)行路徑影響力定義，提出了Ks-IMCO算法求解該問題.實(shí)驗(yàn)結(jié)果表明：Ks-IMCO算法遷移計(jì)算較本地計(jì)算能耗有效節(jié)能在70%左右；對(duì)于不同形式的任務(wù)，Ks-IMCO算法在能耗與時(shí)延方面都優(yōu)于RA，PSwH算法.