一種基于K-shell影響力最大化的路徑擇優計算遷移算法

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

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

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

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

目前，計算遷移算法性能優化目標主要集中在能耗、時延以及兩者的聯合優化.

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

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

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

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

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

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

1 計算遷移系統建模與策略研究

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

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

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

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

1.1 任務本地計算建模與分析

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

(1)

(2)

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

(3)

1.2 基于路徑擇優的計算遷移策略建模

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

(4)

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

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

(5)

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

(6)

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

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

(7)

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

(8)

任務計算時，分別構建任務計算時延Tmec與計算能耗Emec模型[15]：

(9)

(10)

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

Tcount,dk=Ttran+Tmec,

(11)

Ecount,dk=Etran+Emec.

(12)

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

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

(13)

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

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

(14)

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

(15)

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

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

(16)

2 計算遷移路徑選擇優化策略

2.1 基于K-shell算法邊緣服務器劃分與計算遷移優化策略

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

K-shell算法是通過層層剝離的方式對網絡中節點進行分類.本文將網絡中ES類比為節點，采用K-shell算法進行等級劃分，通過網絡拓撲結構區分ES在網絡中的不同位置.假設網絡內包含節點為a，b，…，q，r，如圖3所示.具體分類過程為：

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

首先去除網絡內度數最低(度數為1)的節點，即a，b，c，e，q，r標記ks=1；剩余的節點又會組成新的網絡，此時度數最少的節點為d,o,p,n，m，l，k，j，這些節點的ks=2；以此類推，直到網絡中所有的節點都具有ks值.

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

算法1.路徑重疊算法.

輸入:ES網絡G(P,E);

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

① for 每個ES

② 根據路徑生成規則，查找所有遷移路徑Lall；

③ end for

④ for 每個Lall

⑤ 搜索重疊路徑；

⑥ end for

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

(17)

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

2.2 ES路徑影響力選擇模型

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

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

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

綜合考慮ES在網絡拓撲結構所在位置，利用度中心方法度量ES重要性[26]：

(18)

(19)

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

(20)

σ∈(0,20],

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

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

(21)

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

(22)

證明.

由式(17)可得：

由式(22)可得：

證畢.

2.3 Ks-IMCO路徑尋優算法

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

步驟3.計算ES的ks；

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

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

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

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

① for 每個ES

④ 計算pi(ks)；

⑤ 根據路徑生成規則，查找所有遷移路徑

⑥ end for

⑦ for 每個MSD任務Rdk

⑧ ifδk=0

⑨Rloc,dk執行本地計算；

⑩ else ifδk=1

Eloc,dk；

與能耗Ecount,dk；

3 仿真實驗與分析

3.1 仿真實驗設計

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

Table 1 Simulation Parameter表1 仿真參數

3.2 算法仿真與性能分析

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

本地計算遷移策略與Ks-IMCO算法遷移計算進行對比分析，實驗過程中，將每個MSD任務隨機設為10～100 GB，在500個ES組成的數據集進行仿真，觀察MSD數目由0～500過程中能耗所發生的變化.Ks-IMCO算法遷移計算能耗僅計算MSD分割后任務的本地計算能耗與上傳能耗，實驗結果如圖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節能百分比

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

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

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

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

Table 2 Task Volume Division表2 任務量劃分

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

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

Fig.7 A network of 500 ES terminals for text files task圖7 500個ES終端組成的網絡完成純文本任務

Fig.8 A network of 1 000 ES terminals for text files task圖8 1 000個ES終端組成的網絡完成純文本任務

Fig.9 A network of 2 000 ES terminals for text files task圖9 2 000個ES終端組成的網絡完成純文本任務

Fig.10 A network of 5 000 ES terminals for text files task圖10 5 000個ES終端組成的網絡完成純文本任務

圖片文件實驗結果如圖11～14所示.

Fig.11 A network of 500 ES terminals for picture files task圖11 500個ES終端組成的網絡完成圖片文件任務

Fig.12 A network of 1 000 ES terminals for picture files task圖12 1 000個ES終端組成的網絡完成圖片文件任務

Fig.13 A network of 2 000 ES terminals for picture files task圖13 2 000個ES終端組成的網絡完成圖片文件任務

Fig.14 A network of 5 000 ES terminals for picture files task圖14 5 000個ES終端組成的網絡完成圖片文件任務

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

Fig.15 A network of 500 ES terminals for streaming files task圖15 500個ES終端組成的網絡完成流式文件任務

Fig.16 A network of 1 000 ES terminals for streaming files task圖16 1 000個ES終端組成的網絡完成流式文件任務

Fig.17 A network of 2 000 ES terminals for streaming files task圖17 2 000個ES終端組成的網絡完成流式文件任務

Fig.18 A network of 5 000 ES terminals for streaming files task圖18 5 000個ES終端組成的網絡完成流式文件任務

大規模數據流式文件實驗如圖19～22所示.

Fig.19 A network of 500 ES terminals for large-scale data streaming files task圖19 500個ES終端組成的網絡完成大規模數據流式文件任務

Fig.20 A network of 1 000 ES terminals for large-scale data streaming files task圖20 1 000個ES終端組成的網絡完成大規模數據流式文件任務

Fig.21 A network of 2 000 ES terminals for large-scale data streaming files task圖21 2 000個ES終端組成的網絡完成大規模數據流式文件任務

Fig.22 A network of 5 000 ES terminals for large-scale data streaming files task圖22 5 000個ES終端組成的網絡完成大規模數據流式文件任務

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

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

4 討論問題與未來工作

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

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

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

2)ES路徑分布重疊稀疏度對路徑選擇以及能耗和時延的影響.通過選取不同稀疏的ES路徑分布進行實驗結果如圖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 總 結

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