移動邊緣計算中一種貪心策略的內容卸載方案

袁培燕 蔡云云

摘 要：基于移動邊緣計算的內容卸載技術可以有效降低骨干網絡的流量壓力，提升終端用戶體驗。針對終端用戶與小基站之間的異質接觸率，設計了一種貪心策略的內容卸載方案。首先，將內容最優卸載問題轉化為內容最大投遞率問題;其次，證明最大投遞率問題滿足子模性，在此基礎上，采用貪心算法部署內容，該算法可以以概率（1-1/e）保證其最優性;最后，詳細分析了內容流行度指數以及緩存大小對不同卸載方案的影響。實驗結果表明，所提方案提高了內容投遞率同時降低了內容傳輸時延。

關鍵詞：移動邊緣計算;投遞率;內容卸載;子模性;貪心算法

中圖分類號：TP393.01

文獻標志碼：A

Content offloading scheme of greedy strategy in mobile edge computing system

YUAN Peiyan*， CAI Yunyun

College of Computer and Information Engineering， Henan Normal University， Xinxiang Henan 453007， China

Abstract：

Content offloading technology based on mobile edge computing can effectively reduce the traffic pressure on the backbone network and improve the end users experience. A content offloading scheme of greedy strategy was designed for the heterogeneous contact rate between end users and small base stations. Firstly， the content optimal offloading problem was transformed into the content maximum delivery rate problem. Secondly， the maximum delivery rate problem was proved to satisfy the submodularity. On this basis， the greedy algorithm was used to deploy the content. The algorithm was able to guarantee its optimality with the probability （1-1/e）. Finally， the impacts of content popularity index and cache size on different offloading schemes were analyzed in detail. The experimental results show that the proposed scheme improves the content delivery rate and reduces the content transmission delay at the same time.

Key words：

mobile edge computing; delivery rate; content offloading; submodularity; greedy algorithm

0 引言

近年來，隨著無線通信技術的快速發展和便攜式設備的大規模普及，逐漸形成了人、機物互聯互通的泛在網絡環境。與此同時，大規模的終端設備進行數據傳輸，消耗了大量的帶寬、能量和時間，終端用戶的服務質量（Quality of Service， QoS）急劇下降。移動邊緣計算（Mobile Edge Computing， MEC）技術通過將存儲、計算和通信集成到宏基站（Base Station， BS）或微基站（Small Base Station， SBS）等更加貼近用戶的地方，在一定程度上降低了時延、提高了網絡運營效率[1-3]，同時實現資源在終端、邊緣和云中心的3層級優化利用，更好滿足用戶體驗質量需求[4-5]。

內容卸載作為移動邊緣計算的一項典型應用，吸引了學術界和工業界的廣泛關注。文獻[6]提出利用住宅WiFi接入點（Access Point， AP）來卸載數據。文獻[7]將蜂窩網絡中的車輛通信業務卸載到車輛到車輛（Vehicle-to-Vehicle， V2V）的行進路徑中?；谛遁d控制方案移動邊緣計算內的軟件定義網絡（Software-Defined Network inside the Mobile Edge Computing， SDNi-MEC）服務架構的分析表明，當車輛密度處于中間值時，它在蜂窩網絡鏈路和V2V路徑中具有更大的吞吐量。內容卸載之所以能夠提升網絡性能，是因為它將緩存的內容從距離用戶較遠的地方（云中心）卸載到距離用戶終端較近的地方（宏基站或微基站），可以利用短距離通信技術提升系統容量。文獻[8]基于單個節點的緩存大小、內容數量和網絡節點數量，研究了網絡容量的擴展律。證明即使網絡中節點數量增加，具有緩存的無線自組織網絡的容量也可以保持一個常量。

本文主要考慮將網絡中的部分內容預先卸載到SBS上，進而更好地服務用戶。由于每一個微基站緩存大小及覆蓋范圍有限，于是一個性能良好的卸載方案就變得至關重要。與相關工作不同的是，本文在將網絡中的內容卸載到SBS的過程中，利用用戶終端與SBS之間的異質接觸率，通過貪心算法對內容進行卸載。具體貢獻如下：

1）在移動邊緣計算系統中將內容最優卸載問題轉化為最大投遞率問題，確保SBS所存放的內容可以滿足大部分用戶的需求;

2）證明了最大投遞率問題滿足子模性，在此基礎上，設計了一種貪婪算法求解最優SBS選擇問題;

3）分析了緩存大小和流行度指數對于投遞率以及傳輸時延的影響，仿真結果表明基于貪心算法的緩存策略與經典

的緩存策略相比，投遞率與傳輸時延均有明顯改善。

1 相關工作

內容卸載是移動網絡的一個重要應用。內容卸載問題與緩存問題緊密相關，增加緩存以及進行內容卸載都可以使網絡性能得到提升。即使每一個內容只緩存一個備份，也可以使網絡性能得到提升。然而在現實中，不同的文件有不同的流行度，流行度高的文件在網絡中有更高的概率被用戶終端請求，流行度低的文件可能被較少的用戶請求，甚至有些文件在網絡中不被請求。在流量使用高峰期，請求流行度高的內容的用戶終端可能會出現排隊現象，造成網絡延遲。流行度較低的內容可能沒有被用戶終端請求，造成資源浪費。文獻[9]按照內容的流行度對內容進行存儲。有較高流行度的內容在網絡中有較多的備份，較低流行度的內容在網絡中有較少的備份。仿真結果表明，按照流行度緩存計算出的容量高于所有內容均勻緩存的容量。這是因為流行度高的內容在網絡中的備份數多，用戶終端會相對容易找到自己請求的文件，傳輸距離減小，容量增大。

依照流行度進行緩存固然重要，緩存策略也很重要。當一個BS將內容卸載到SBS時，無法確認將內容緩存在哪些SBS中更容易滿足用戶需求。最優卸載問題可以被理解為預緩存問題。近年來已近有一些關于預緩存問題的研究。Liu等[10]研究了最佳內容放置，基于概率緩存框架，采用隨機幾何理論推導出閉形的成功卸載概率，并制定了緩存概率優化問題。文獻[11]利用設備到設備的通信技術，將公共內容分發給在下載過程期間協作的一組移動設備?；緦热莸牟煌M塊單播到選定的移動設備，移動設備使用多跳協作，同時保持對移動設備的能量消耗的公平性約束。通過將最優蜂窩卸載問題表述為混合整數線性規劃問題，分析其算法復雜性。實驗結果表明，即使只有很少一部分移動設備用于合作，也可以顯著的增益系統性能。Han等[12]設計了一種有偏好的學習算法來跟蹤用戶不斷變化的興趣，然后通過預測WiFi網絡連接的持續時間，優化了何時預取以最大化用戶體驗問題，同時降低預取成本。文獻[13]提出基于推理的社交網絡內容預取器EarlyBird，使用社交數據特定信號，以便在用戶使用之前檢索新聞提要以及相關鏈接和多媒體。提出的基于回歸的內容預測模型能夠在55%的時間內估計用戶感興趣的內容。文獻[14]提出了一種基于動作的預取解決方案Precog，用于時移WiFi卸載。與需要并發蜂窩和WiFi連接的先前卸載解決方案不同，Precog通過時移WiFi卸載內容。文獻[15]通過帶寬有限的兩層異構網絡中的帶寬分配和緩存放置來最小化平均文件傳輸延遲。對于聯合帶寬分配和高速緩存放置問題，首先給出最佳帶寬分配策略。 然后，通過替換最佳帶寬分配，將原始問題轉換成關于高速緩存策略的等效問題。最后為了解決等效非凸問題，提出了一種低復雜度的迭代算法來獲得次優解。文獻[16]將延遲最小化作為優化目標并將其表示為整數規劃問題，通過動態規劃有效地分配資源。結合以上工作不難發現，無論是卸載問題還是緩存問題，其目的都是將內容和資源合理分配，從而提升網絡性能。

2 系統架構

移動邊緣計算通常由邊緣設備（如智能手機、物聯網設備、智能車等），邊緣云和遠端云（或大型云計算中心、大云）組成。邊緣云是部署在移動基站上的小規模云計算中心，更加專注于局部，將計算任務在接近數據源的地方執行，可以有效減小計算系統的延遲， 減小內容傳輸帶寬， 緩解云計算中心壓力并能夠保護數據安全和隱私[17]。當邊緣設備的處理能力無法滿足自身需求時，可以通過無線網絡將密集型任務和海量數據遷移到邊緣云處理;當邊緣云不能滿足邊緣設備的要求時，任務和數據可以遷移到遠端云處理。在本文中，邊緣設備為了更好地滿足用戶終端的需求并降低自身壓力，將內容卸載在SBS上。然后，為了最大化增益，用貪心算法求解內容最佳卸載問題。

假設一個邊緣網絡包括一個BS，n個SBS。所有SBS的集合可以表示為V={v1，v2，…，vn}。整個邊緣網絡中有m個獨立的內容，記作F={F1，F2，…，Fm}。為了方便計算，假設每一個內容的大小是1b。每一個SBS空間大小是sb，即每一個SBS可以緩存s個內容，其中s≤m。為了減少等待時間并且將SBS中的緩存空間充分利用，每個內容在每一個SBS中僅具有一個緩存。另外，假設每個內容都有一個生命周期T，剩余時間越長表示該內容被移動終端收到的概率越大。

用戶終端到SBS的傳輸距離小于用戶終端到BS之間的傳輸距離，如果用戶終端盡可能多地在SBS請求內容，而不是向BS請求內容，該內容請求將會更快得到響應。由于用戶終端是移動的并且每一個SBS有不同的位置和覆蓋范圍，因此用戶終端跟每一個SBS的接觸率不同。同樣的內容在不同的SBS中有不同的投遞率（投遞率是用于評估算法性能的最重要標準之一，其可以直觀地反映網絡傳輸的可靠性。當源節點發送的內容數量不變時，目的節點成功接收的內容越多，內容的投遞率就越高）。另外，每一個SBS的緩存空間有限，只能緩存部分內容。這就使得對每一個內容進行合理分配尤為重要。為了使傳輸更加可靠、傳輸時延更小，應該將內容卸載到使投遞率盡可能大的SBS中。因為不同的內容有不同的流行度，所以將優化問題表示為：

max（∑mi=1pidi）（1）

s.t.

Ai≤n

∑mi=1Ai≤ns（2）

其中：pi指第i個內容的流行度，di指第i個內容的投遞率。第一個限制條件表示每一個內容的數量不能超過SBS的數量;第二個限制條件表示緩存的所有內容的數量不能超過所有SBS的緩存大小。

在解決優化問題之前，需要計算第i個內容的流行度。假設內容的流行度遵循Zipf分布，并且第i個內容的流行度與 1/iγ成正比。于是可以將第i個內容的流行度表示為：

pi=1irHm，γ=1/（ir∑mj=11jr）（3）

滿足0≤pi<1，∑mi=1pi=1，其中，Hm，γ是廣義諧波數。至此，可以通過解決最大投遞率問題來解決內容的最佳卸載問題。

3 問題解決

本章中主要通過最大投遞率問題解決內容的最佳卸載問題。首先研究用公式表示最大投遞率，其次證明最大投遞率問題滿足子模性，最后用貪心策略解決內容最佳卸載問題。

3.1 子模性

假設βj表示用戶終端與第j個SBS之間接觸概率，存放在第j個SBS中的內容在時間T內沒有被目的用戶終端接收到的概率為e-βjT，則目的用戶終端接收到的概率可以表示為1-e-βjT。令集合Ai表示當前存儲第i個內容的SBS的集合。A=‖Ai‖表示緩存第i個內容的SBS的數量。假設存在一個集合Bi，滿足AiBi，B=‖Bi‖。由于第i個內容的投遞率di可以表示為1-e-∑j∈AiβjT，結合式（3），則式（1）可以表示為：

∑mi=1pi（1-e-∑j∈AiβjT）（4）

s.t.

Ai≤n∑mi=1Ai≤ns（5）

定理1 最大投遞率問題滿足子模性。

證明 當有一個新的SBS加入時，即基站想要將第i個文件放置在一個SBS，存放第i個內容的SBS的集合可以表示為Ai′=Ai∪{v}，Bi′=Bi∪{v}。

對于集合Ai，加入v后，投遞率的增量為：

pi（1-e-∑j∈Ai′βjT）-pi（1-e-∑j∈AiβjT）=

pi（e-∑j∈AiβjT-e-∑j∈Ai′βjT）=pie-∑j∈AiβjT（1-e-βiT）（6）

同理，對于集合Bi，投遞率的增量為：

pi（1-e-∑j∈Bi′βjT）-pi（1-e-∑j∈BiβjT）=pie-∑j∈BiβjT（1-e-βiT）（7）

因為AiBi，可以得出：

pie-∑j∈AiβjT（1-e-βiT）≥pie-∑j∈BiβjT（1-e-βiT）（8）

所以，內容的投遞率滿足子模性，證畢。

3.2 貪婪算法

算法1 基于貪婪算法的內容卸載流程。

輸入：所有的SBS的集合V;

輸出：能夠使第i內容的投遞率最大的SBS的集合C。

有序號的程序——————————Shift+Alt+Y

程序前

1）

計算出將第i內容放入每一個SBS的投遞率并排序

2）

D={i}

3）

V0=V

4）

V=V-{i}

5）

while ∑mi=1ai≤ns，ai≤n do

6）

for each node r∈V＼C do

7）

r ← arg maxr∈V＼C（f（C∪{r}）-f（C））

8）

end for

9）

C=C∪{r}

10）

V=V-{r}

11）

end while

12）

return C

程序后

由于投遞率滿足子模性，因此存在一個貪心算法以 （1-1/e）的概率保證式（4）的最優性。貪心算法是一種改進了的分級處理的方法，其核心是根據問題選取一種量度標準。然后將多個輸入排成這種量度標準所要求的順序，按這種順序一次輸入一個量。如果這個輸入和當前已構成在這種量度標準下的部分最佳解合并在一起不能產生一個可行解，則此輸入不能加入到該部分解中。這種能夠得到某種量度意義下最優解的分級處理方法稱為貪婪算法。

本文貪心算法的核心是將投遞率作為一種度量標準。按照將第i個內容放置到SBS的投遞率等級進行排序?；景凑者@個順序將內容依次放入SBS。如果新加入的內容放置的SBS和當前已經放入第i內容的SBS的集合一起可以使投遞率最高，則第i內容放入該SBS，并將該SBS加入存放第i個內容的SBS的集合C內。當有一個內容需要加入SBS時重復上述過程，直到所有SBS沒有空閑緩存空間或所有內容均被緩存。

4 實驗仿真

本章分析流行度指數以及緩存的大小對于投遞率和傳輸時延的影響，并將基于貪婪算法（Greedy algorithm）進行緩存的投遞率和傳輸時延與經典方案進行比較：隨機緩存（Random）[18]、根據流行度緩存（Popular）[7]和根據閾值緩存（Pop-unpop）[19]。隨機緩存表示每個節點對每個內容按照一定的概率隨機緩存，不考慮內容的流行度。根據流行度緩存的方案是指每一個內容在節點中的備份數由內容的流行度決定，若內容流行度較高，則該內容在節點中有較多的備份數;若內容的流行度較低，則緩存該內容較少。根據閾值緩存方案指流行度最高的前k個內容在每一個SBS中都有一個備份，第k+1個內容至最后一個內容在所有SBS組成的網絡中最多僅有一個備份。

圖1（a）與圖1（b）中分析了流行度指數以及緩存大小對投遞率的影響。在圖1（a）中，緩存大小設置為10。從圖中可以看出隨著流行度指數的不斷增大，根據貪婪算法進行緩存的投遞率在不斷增大。在流行度指數接近于2.0時，投遞率接近1?；陂撝档木彺娣桨负突诹餍卸冗M行緩存方案的投遞率也會隨著流行度指數的增大而增大，但是投遞率的值在流行度指數增長期間，始終沒有超過基于貪婪算法進行緩存的投遞率的值。隨機緩存有很多不確定性，其投遞率也存在很多不確定性。為了能夠較好地反映基于隨機緩存的投遞率隨著流行度指數的變化情況，進行了4次仿真實驗，并取均值。從圖1（a）中可以看出，隨機緩存的投遞率平均值很小。在流行度指數變化期間，投遞率一直處于低于0.1的狀態。在圖1（b）中，流行度指數設置為1.0。幾種方案隨著緩存大小的變大，變化不是太明顯。但是基于貪婪算法進行緩存的方案，投遞率仍然是單調上升的趨勢，并且其值大于其他方案下的投遞率的值。結合圖1中的兩個圖可以發現，基于貪婪算法進行緩存的方案跟其他方案相比顯示出一定的優越性。

圖2（a）和與圖2（b）中分析了流行度指數以及緩存區的大小對傳輸時延的影響。在圖2（a）中，將緩存大小設置為10，傳輸時延的仿真圖與投遞率的變化趨勢幾乎是對稱的。在圖2（a）中，基于貪婪算法進行緩存的傳輸時延與其他方案的傳輸時延隨著流行度指數的增大而快速下降，但是基于貪婪算法進行緩存的傳輸時延的下降趨勢大于基于閾值的緩存和基于流行度緩存的下降趨勢。隨機緩存的傳輸時延并沒有隨著流行度指數的變化而下降，在整個流行度指數的變化期間一直保持接近10的狀態。圖2（b）中，流行度指數設置為1.0，并且隨著緩存變大，傳輸時延的變化趨勢都不是太大?；谪澬乃惴ň彺娴膫鬏敃r延最小。從傳輸時延的變化趨勢可以看出，傳輸時延在減小到一定的值的時候，變化不會太明顯。結合實際，用戶與SBS進內容行輸，總會有一定的傳輸時延。這是因為SBS與用戶終端之間會有一定的傳輸距離，且內容處理都需要時間。結合投遞率以及傳輸時延，跟其他經典的方案相比，基于貪心算法進行緩存的方案提升了投遞率，減小了傳輸時延。

圖3是4種緩存方案下的投遞率隨著時間比（BS到用戶終端與SBS到用戶終端傳輸的時間比）增大的變化情況。將k、流行度指數以及緩存大小分別設置為30、10和1.0。時間比變大表示用戶請求的內容由BS提供服務的比例大于由SBS提供服務的比例。因為BS到用戶終端的距離大于SBS到用戶終端的距離，所以用戶的請求由BS提供服務的傳輸時延比SBS提供服務的傳輸時延大。時間比對于傳輸時延的影響再一次證明在靠近用戶終端進行緩存的重要性，也證明了一個性能良好的卸載方案的重要性。

5 結語

本文針對移動邊緣計算中內容的最佳卸載問題，提出用貪婪算法解決。將內容卸載問題轉化為最大投遞率問題，并證明最大投遞率問題滿足子模性，因此用貪心算法可以概率（1-1/e）保證其最優性。仿真結果表明，與一些經典方案相比，提出的方案使內容投遞率與傳輸時延性能均得到了較大改善。

參考文獻

[1]BARBAROSSA S， CECI E， MERLUZZI M， et al. Enabling effective mobile edge computing using millimeterwave links [C]// Proceedings of 2017 IEEE International Conference on Communications Workshops. Piscataway， NJ： IEEE， 2017： 367-372.

[2]BELLI D， CHESSA S， FOSCHINI L， et al. A social-based approach to mobile edge computing [C]// Proceedings of the 2018 IEEE Symposium on Computers and Communications. Piscataway， NJ： IEEE， 2018： 292-297.

[3]ROMAN R， LOPEZ J， MAMBO M. Mobile edge computing， Fog et al.： a survey and analysis of security threats and challenges [J]. Future Generation Computer Systems， 2018， 78： 680-698.

[4]鄧曉衡， 關培源， 萬志文，等.基于綜合信任的邊緣計算資源協同研究[J]. 計算機研究與發展， 2018， 55（3）：449-477.（DENG X H， GUAN P Y， WAN Z W， et al. Integrated trust based resource cooperation in edge computing [J]. Journal of Computer Research and Development， 2018， 55（3）：449-477.）

[5]GUAN P， DENG X， LIU Y， et al. Analysis of multiple clients behaviors in edge computing environment [J]. IEEE Transactions on Vehicular Technology， 2018， 67（9）： 9052-9055.

[6]POULARAKIS K， IOSIFIDIS G， PEFKIANAKIS I， et al. Mobile data offloading through caching in residential 802.11 wireless networks [J]. IEEE Transactions on Network and Service Management， 2016， 13（1）： 71-84.

[7]HUANG C， CHIANG M， DAO D， et al. V2V data offloading for cellular network based on the Software Defined Network （SDN） inside Mobile Edge Computing （MEC） architecture [J]. IEEE Access， 2018， 6： 17741-17755.

[8]QIU L， CAO G. Cache increases the capacity of wireless networks [C]// Proceedings of the 35th Annual IEEE International Conference on Computer Communications. Piscataway， NJ： IEEE， 2016： 1-9.

[9]QIU L， CAO G. Popularity-aware caching increases the capacity of wireless networks [C]// Proceedings of the 2017 IEEE Conference on Computer Communications. Washington， DC： IEEE Computer Society， 2019： 1-9.

[10]LIU D， YANG C. Optimal content placement for offloading in cache-enabled heterogeneous wireless networks [C]// Proceedings of the 2016 IEEE Global Communications Conference. Piscataway， NJ： IEEE， 2016： 1-6.

[11]AL-KANJ L， POOR H V， DAWY Z. Optimal cellular offloading via device-to-device communication networks with fairness constraints [J]. IEEE Transactions on Wireless Communications， 2014， 13（8）： 4628-4643.

[12]HAN J， LI X， JUN T， et al. Network agile preference-based prefetching for mobile devices [C]// Proceedings of the 2014 IEEE 33rd International Performance Computing and Communications Conference. Piscataway， NJ： IEEE， 2014： 1-8.

[13]WANG Y， LIU X， CHU D， et al. EarlyBird： mobile prefetching of social network feeds via content preference mining and usage pattern analysis [C]// Proceedings of the 16th ACM International Symposium on Mobile Ad Hoc Networking and Computing. New York： ACM， 2015： 67-76.

[14]SANADHYA S， MORAVAPALLE U P， KIM K-H， et al. Precog： action-based time-shifted prefetching for Web applications on mobile devices [C]// Proceedings of the fifth ACM/IEEE Workshop on Hot Topics in Web Systems and Technologies. New York： ACM， 2017.

SANADHYA S， MORAVAPALLE U P， KIM K-H， et al. Precog： action-based time-shifted prefetching for Web applications on mobile devices [EB/OL]. [2018-12-20]. http：//gnan.ece.gatech.edu/archive/precog_hotweb_17.pdf.

[15]YANG Z H， PAN C H， PAN Y J， et al. Cache placement in two-tier HetNets with limited storage capacity： cache or buffer？ [J]. IEEE Transactions on Communications， 2018， 66（11）： 5415-5429.

[16]LUO J， DENG X， ZHANG H， et al. Ultra-low latency service provision in edge computing [C]// Proceedings of the 2018 IEEE International Conference on Communications. Piscataway， NJ： IEEE， 2018： 1-6.

[17]施巍松，張星洲，王一帆，等.邊緣計算：現狀與展望[J].計算機研究與發展，2019，56（1）：69-89.（SHI W S， ZHANG X Z， WANG Y F， et al. Edge computing： state-of-the-art and future directions [J]. Journal of Computer Research and Development， 2019， 56（1）： 69-89.）

[18]WEN W， CUI Y， ZHENG F C， et al. Random caching based cooperative transmission in heterogeneous wireless networks [J]. IEEE Transactions on Communications， 2018， 66（7）： 2809-2825.

[19]AO W C， PSOUNIS K. Distributed caching and small cell cooperation for fast content delivery [C]// Proceedings of the 16th ACM International Symposium on Mobile Ad Hoc Networking and Computing. New York： ACM， 2015： 127-136.

This work is partially supported by the National Natural Science Foundation of China （U1804164， U1404602）， the Science and Technology Foundation of Henan Province （172102210341）.

YUAN Peiyan， born in 1978， Ph. D.， associate professor. His research interests include mobile network， wireless communication.

CAI Yunyun， born in 1994， M. S. candidate. Her research interests include mobile edge computing.