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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

(2)

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

(3)

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

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

(4)

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

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

(5)

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

(6)

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

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

(7)

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

(8)

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

(9)

(10)

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

Tcount,dk=Ttran+Tmec,

(11)

Ecount,dk=Etran+Emec.

(12)

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

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

(13)

綜上所述，任務(wù)遷移需要的總時延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 計算遷移路徑選擇優(yōu)化策略

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

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

K-shell算法是通過層層剝離的方式對網(wǎng)絡(luò)中節(jié)點進行分類.本文將網(wǎng)絡(luò)中ES類比為節(jié)點，采用K-shell算法進行等級劃分，通過網(wǎng)絡(luò)拓撲結(jié)構(gòu)區(qū)分ES在網(wǎng)絡(luò)中的不同位置.假設(shè)網(wǎng)絡(luò)內(nèi)包含節(jié)點為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é)點，即a，b，c，e，q，r標記ks=1；剩余的節(jié)點又會組成新的網(wǎng)絡(luò)，此時度數(shù)最少的節(jié)點為d,o,p,n，m，l，k，j，這些節(jié)點的ks=2；以此類推，直到網(wǎng)絡(luò)中所有的節(jié)點都具有ks值.

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

算法1.路徑重疊算法.

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

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

① for 每個ES

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

③ end for

④ for 每個Lall

⑤ 搜索重疊路徑；

⑥ end for

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

(17)

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

2.2 ES路徑影響力選擇模型

考慮到ES的計算、傳輸能力的差異性，構(gòu)建ES路徑對計算任務(wù)的評判標準：ES路徑影響力.

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

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

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

(18)

(19)

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

(20)

σ∈(0,20],

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

綜上，ES路徑影響力計算表示為

(21)

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

(22)

證明.

由式(17)可得：

由式(22)可得：

證畢.

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

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

步驟3.計算ES的ks；

步驟6.運行PO算法，對路徑重疊部分選擇其影響力最大路徑進行計算遷移；

步驟7.得到最終計算遷移路徑.

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

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

① for 每個ES

④ 計算pi(ks)；

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

⑥ end for

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

⑧ ifδk=0

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

⑩ else ifδk=1

Eloc,dk；

與能耗Ecount,dk；

3 仿真實驗與分析

3.1 仿真實驗設(shè)計

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

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

3.2 算法仿真與性能分析

實驗1.本地計算與Ks-IMCO算法遷移計算能耗對比分析.

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

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

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

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

實驗2.不同算法能耗與時延對比分析.

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

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

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

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

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

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

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

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

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

圖片文件實驗結(jié)果如圖11～14所示.

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

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

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

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

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

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

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

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

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

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

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

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

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

4 討論問題與未來工作

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

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

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

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

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

5 總 結(jié)

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