移動邊緣計算中利用BPSO的任務卸載策略

汪小威，林 寧+，胡玉平

(1.南寧學院 信息工程學院，廣西 南寧 530200；2.廣東財經大學 信息學院，廣東 廣州 510320)

0 引 言

隨著智能設備的劇增以及通信技術的突飛猛進，促使邊緣計算突破技術瓶頸，并極大地提高了物聯網(Internet of thing，IoT)的計算效率[1]。面對著越來越多的數據，各類終端設備不斷研發出來并且功能愈發豐富，甚至逐漸承擔了云服務的作用，實現了更高的計算效率。移動邊緣計算(moving edge computing，MEC)技術作為云計算相關領域最為關鍵的方向之一，已在物聯網和嵌入式系統等眾多新技術中廣泛應用并投入實際運行[2]。然而，各種終端設備在不斷競爭與腳逐的過程中計算成為了關鍵環節，大量的計算開銷對計算能力和網絡承載能力也提出了新的要求[3]。

一般情況下云計算速度的快慢以及其性能的高低依賴于物理服務器，終端設備利用云計算時首先要將相應的數據傳送給物理服務器，這樣可以有效解決中斷設備自身能力不足的弊病[4]。但是不可否認的是隨著終端設備越來越多，大量數據不斷匯集到服務器將會對其造成巨大壓力。與云服務器相反，邊緣節點有限的計算和存儲資源要求其將部分計算或存儲任務卸載到其它邊緣節點，以提高系統資源利用率，便于靈活高效地進行任務卸載，以實現對所需處理任務的合理規劃[5]。

對于任務卸載策略最優化問題，從最優化動機的角度來看，移動邊緣設備必須克服數據量大、帶寬低、設備電池容量受限等不利因素[6]。因此，在保證數據處理速率的前提下，降低能量消耗是保證設備連續運行的關鍵[7]。傳統的任務卸載優化方法除了需要對數據隱私性進行強化以外，還需要在保證低數據延遲的同時，降低任務處理能耗，提高系統計算效率。所提出的任務卸載策略基于由移動設備、邊緣節點和云服務器組成的三層網絡架構提出了任務卸載方案，用以實現移動設備在所有任務持續時間內的能耗的最小化。

1 相關工作

目前已經有許多關于計算卸載優化問題的研究成果，其中包括由移動設備和邊緣節點組成的移動邊緣計算網絡場景研究，以及由移動設備和云服務器組成的移動云計算(mobile cloud computing，MCC)網絡場景研究等[9]。

在移動邊緣計算網絡的基礎上，為盡可能延長中斷設備使用時間，提升能源使用效率，要尋找出最優的資源分配方案。文獻[10]考慮了MEC網絡中分布式能量收集設備通過射頻實現功率傳輸的能量感知架構，充分利用乘子交替方向法有效提升計算能力降低其延遲時間，但該方法不能在各種網絡設置下有效地實現最佳性能，具有一定的局限性[11]。文獻[12]為了最大限度地降低移動設備的能耗，將約束條件設成所有任務的持續時間，針對邊緣計算中能量消耗的最優化問題展開研究，分別從協同任務卸載和計算資源配置兩方面進行了問題優化，在最短的時間內實現能耗最低的需求，雖然兼顧了能耗和延遲最小化，但在實際應用中還不具有一定的可行性。文獻[13]為了解決MEC任務卸載中兼顧效率與數據隱私性的問題，提出了一種包含實用感知卸載程序和用于隱私權衡的兩階段聯合卸載優化策略，用于MEC系統任務卸載策略優化和隱私保護，實驗結果表明了該方法的高效性和可靠性。由于任務卸載過程中對隱私保護的權衡，導致算法在處理延遲和綜合能耗方面表現較差。

粒子群優化算法作為一種經典的智能算法，目前已有一些文獻將其廣泛應用于優化決策過程中[14]。文獻[15]針對預測任務之間的全局時空相關性，時空異質性與模型的全局預測能力之間的平衡以及預測模型的參數優化等挑戰，結合基于粒子群優化的時空多任務和多視圖特征學習模型提高模型的訓練速度，對MEC中任務卸載進行優化。但傳統的粒子群優化算法容易陷入局部最優，難以獲得全局最優解，因此文獻[16]提出了計算分流模型，將任務卸載表述為一個混合整數非線性規劃問題。在該文獻中引入了兩種算法，一種是數學中經典的遺傳算法，另外一種是粒子群優化算法，通過這兩種算法的結合有效提升了計算速度。仿真研究表明該算法的收斂性和可靠性，但由于算法迭代耗時，導致任務卸載整體延遲較其它算法較高，還有可提升的空間。文獻[17]在考慮完成時間和能效的基礎上，把計算分流進行了轉化，利用能效成本進行代替。同時在該文獻中還對時鐘頻率以及其發射功率等再次進行了優化從而建立了一種有效的分布式算法，這種方法對本地任務執行的時鐘頻率和邊緣云執行的傳輸功率進行了聯合優化，在保證卸載效率的同時降低了能耗。文獻[18]提出了一個包含對卸載策略制定、負載平衡、計算資源分配的多維優化問題，以最小化多MEC服務器多智能移動終端(smart mobile devices，SMD)網絡中所有SMD的總延遲和能耗的加權總和，并進行功率控制。通過一種低復雜度的啟發式算法來獲得卸載策略，同時保證多個MEC服務器之間的負載平衡；并使用拉格朗日對偶分解法解決計算資源分配子問題。

雖然該方法在任務卸載策略的能耗優化方面取得了一定的成績，但是無法兼顧能耗與傳輸延遲，系統整體負載均衡方面仍存在一定的提升空間。為此，提出了一種移動邊緣計算中利用BPSO的任務卸載策略。其主要的創新點總結如下：

(1)由于核心計算網絡負擔較大，所提策略構建了三層移動邊緣計算(moving edge computing，MEC)網絡架構，移動設備中的計算任務可以在本地進行，也可卸載至邊緣計算節點與云服務器中執行，有利于任務卸載策略的高效實施。

(2)為了提高任務卸載方案的性能，所提策略根據MEC網絡中的計算模型、通信模型設計了計算卸載目標，并利用二進制粒子群(binary particle swarm optimization，BPSO)算法對其進行求解，以得到最優卸載策略，實現能量消耗最小且時延最短，系統整體負載最為均衡。

2 系統模型

2.1 網絡模型

為了任務卸載策略的高效實施，提出了一個分布式的三層邊緣計算網絡模型，其架構如圖1所示。其中包括了M個移動設備(mobile devices，MD)、N個基站(base stations，BS)和一個遠程云服務器。每個基站都配備了一個邊緣計算節點。此外，移動設備的電池容量是有限的，將移動設備的集合表示為m={1,2,…,M}，邊緣節點的集合為n={1,2,…,N}。當每個基站通過有線鏈路連接到云端時，可以通過無線鏈路與多個移動設備進行通信，并且移動設備與基站之間的距離遠小于基站與云之間的距離[19]。

圖1 移動邊緣計算網絡模型的架構

(1)

上式表示一個計算任務要么由移動設備在本地執行，要么由設備卸載到基站或云再進行處理，且總數據量大小為Dm。

其次，介紹了服務緩存的概念。緩存將數據副本存儲在靠近請求的位置，并預期會收到相同的請求，這樣的方式可以減少計算延遲和網絡負擔。在所提策略中，將服務的集合表示為s={1,2,…,S}，用cs來表示服務S所需的存儲空間大小，用Cn來表示基站n的存儲空間。更具體地說，所提策略中假設計算任務以vs,n的速率到達，并服從泊松過程。需要注意的是，服務緩存將在每次基于短期預測而做出決策之前進行更改。

2.2 通信模型

提出的網絡模型中，每個移動設備都需要為其任務選擇最佳的策略。將Bn(Hz)表示為邊緣節點n的無線信道帶寬；以ηm,n表示移動設備m和邊緣節點n之間的上行傳輸效率。根據香濃公式，可以近似得到

(2)

式中：pm,n代表的是使用的終端設備m的傳輸功率，δm,n代表的是使用的終端設備m和相應基站n之間的信道增益，τ2代表的是背景噪聲的功率值，即加性高斯白噪聲。pm,nδm,n/τ2可以表示移動設備m與基站n之間的上行鏈路信噪比。根據ηm,n的定義，進一步地定義移動設備m與基站n之間傳輸數據的上行速率為

(3)

在服務緩存的情況下必須要強調的是，基站n的有限存儲空間Cn迫使基站必須做出選擇，即基站需要選擇哪些服務進行緩存[21]。具體地說，基站n需要在服務S中選擇若干個服務進行緩存。為此，引入一個二進制變量φs,n∈{1,0}，用來表示服務s是否被緩存在基站n中。因此，服務緩存的約束條件服從下式

(4)

進一步地，將φs,n?N表示緩存服務S的基站集合，所以這些基站可以向移動設備提供相應的服務。

2.3 計算模型

(1)本地計算

(5)

(2)邊緣計算

(6)

(7)

由于被基站n處理后的數據量大小與原先相比將變得非常小，所以忽略將處理后的數據發送回移動設備m的下行鏈路傳輸延遲。綜上所述，將從移動設備m中數據卸載到基站n的傳輸能量成本定義為

(8)

(3)云計算

(9)

與邊緣計算類似，忽略基站與移動設備之間的下行傳輸延遲。值得注意的是，計算過程的總能耗是十分復雜的，它還包括基站和云的計算成本。然而，由于考慮的問題是關于移動設備的電池續航能力，這意味著需要進行最優化的問題僅需關注到移動設備的能源成本。

根據以上所述，可以總結得出每個移動設備的所有任務持續時間Tt和能量消耗Em分別如下

(10)

(11)

2.4 計算卸載目標

計算機卸載的主要作用就是將原有的計算工作轉至云計算或者其它邊緣計算中，然后再利用各種終端設備發送需求指令，待計算完成結束，最終的結果利用終端顯示出來。計算卸載應用場景越來越多并且也逐漸引起了人們的重視。其具體的架構如圖2所示。

圖2 計算卸載框架

從具體過程來看，計算卸載正式開始前，終端設備必須對其要開展的計算工作做出合理、科學的分配，一部分歸為本地進行，另外一部分可以歸為節點進行。其中前者就是指在設備中即可進行操作。而后者則需要依賴于邊緣計算節點。另外，計算節點一旦接受相應指令就要對資源進行詳細的規劃，具體的工作任務會根據規劃進行分配，假如節點不能實現，那么就需要將其轉至云服務中心。計算節點根據規劃完成任務后還要將結果再次傳送至終端設備。

對卸載目標進行準確的確定目的就是要快速的將計算任務進行科學、合理的分配，具體來講卸載目標涵蓋了如下3個部分。

(1)任務最優分配。最優分配通俗來講就是確定一個最為合理同時效率又最高的一種方法，使得整個計算過程的延時能夠達到最小，從而提升用戶的體驗感。

(2)節點負載均衡。邊緣計算平臺一般包括很多個計算節點，而這些節點必須利用足夠數量的計算機，當其數量達到一定程度后，每個節點的負載如何保證最佳也是卸載目標要實現的，這樣才能夠將有效的資源充分調動起來。

(3)經濟利益最大化。計算卸載任務同樣要考慮到所需要的成本以及能夠實現的經濟效益，尤其是在數據爆炸的今天，對于設備數量需求只會越來越高，所以卸載目標必須考慮經濟效益的問題，平衡使用者與運營公司二者之間的利益。

3 基于二進制粒子群的調度策略

這里假定本地執行的與卸載至邊緣計算平臺進行的任務都已經明確，通常情況下用Qm表示總任務，那么卸載后的任務就能夠通過?i進行表示，這里需要注意的是?i屬于二進制，其中?i∈{0,1}。當?i=0時，表示計算任務Qm在本地執行計算；當?i=1時，表示計算任務Qm需要卸載到邊緣計算或云計算服務器去執行。如此，就能夠知道任何一個Q都將會對應著一個?,并且?屬于通過(0,1)形成的二進制向量，這個向量維數可以用N表示。

利用蠻力搜索就能夠進一步求出?的最優值所在的時間復雜度為O(2N)，基于此就能夠再利用BPSO算法進一步求出最終的解。

為了判斷粒子是否是最優的，需要通過目標函數進行計算，其中目標函數為系統整體負載φ

φ=γ1Tt+γ2Em

(12)

式中：γ1,γ2分別表示在卸載決策時計算任務延遲和能耗的權重。

(13)

(14)

其中，k代表的是具體的迭代次數，ω、g1以及g2代表的是不同的參數，通常情況下它們都為常數；rand()命令用來獲得隨機數，具體的范圍是[0,1]。利用上面的這個計算公式能夠對全部粒子的具體位置以及其相應的速度進行不斷的迭代更新，然后對得到的數值取最優。

但是因為BPSO算法本身就決定了所有粒子得出的位置值都會在{0,1}范圍內，所以還需要通過Sigmoid函數將其對應的速度重新進行映射至迭代更新之后的位置。具體如下

(15)

式中：wij∈[0,1]表示在[0,1]區間內均勻分布的隨機數。

根據以上分析，利用BPSO的任務卸載具體過程如圖3所示。

圖3 基于BPSO的任務卸載流程

利用不同粒子的具體位置就能夠進一步獲取本地執行以及通過邊緣計算執行兩部分的具體的任務，這里用T1與T2分別表示。這樣就可以得到相應的調度策略并從中擇取最佳的一種方案。基于該方案可以計算出延遲時間以及相應的能耗，同時能夠計算出粒子的具體位置。通過不斷迭代就可以最終獲得最優解。

4 仿真實驗及分析

通過MATLAB仿真平臺對所提任務卸載策略性能進行評估。在移動邊緣計算網絡模型中，移動設備數量為200個，基站數量為50個，云計算服務器為1個。相關的實驗參數設置見表1。需要強調的是，在仿真實驗中，邊緣節點的設置相對更靠近于設備，而云服務器則遠得多。

表1 仿真實驗參數設置

4.1 參數討論

為了分析BPSO算法中參數wij對任務卸載策略能量消耗的影響，通過改變參數值比較能量的消耗情況，具體結果如圖4所示。這里做理想假設所有終端設備計算任務基本一致，且外部環境一致，僅僅改變wij的數值，實驗中選取了3個不同的wij值對能量消耗曲線收斂的影響進行分析。

圖4 參數wij對收斂性的影響

從圖4中可以看出，當wij的值較小時，能量消耗曲線的收斂速度最快。因此，應當在合理的范圍內選擇相對較小的wij，以獲得更好的收斂性能。

4.2 基站數量對所提策略能耗的影響分析

在所提任務卸載策略中，系統參數都會影響其性能和收斂性，例如基站總帶寬、計算速率和傳輸速率的變化、移動設備和基站的數目等。為了對實驗結果進行分析，篩選了若干個具有代表性的參數，其中基站數量對所提策略能耗的影響如圖5所示。

圖5 基站數量對所提策略能耗的影響

從圖5中可以看出，在迭代開始之時的能量消耗遠遠高于在最終取得最優結果時的能耗。隨著迭代的不斷進行，在迭代次數為20左右之前，能量消耗一直急劇下降，而超過20次迭代之后，其能量消耗變化并不明顯。經過大約40次迭代后，曲線實現近似的收斂，此時如果算法不要求更高的精度，那么收斂值就可作為卸載選擇的最優解。需要注意的是，曲線上方的n=0直線表示計算任務只能在本地處理，在一定范圍內，能量消耗隨著基站數量的增加而減少。基站越多，完成計算任務卸載的能力越強，因此能量消耗隨之減少。

此外，當結果接近收斂時，基站的數量對平均迭代次數的影響如圖6所示。

圖6 基站數量對平均迭代次數的影響

從圖6中可以看出，當基站的數量越大時，卸載策略需要花費更多的時間和進行更多次迭代才能實現收斂。另外，將所提策略與文獻[10]進行對比，由于文獻[10]采用具有差分隱私的交替方向乘子算法，其收斂需要更多次迭代，且迭代過程受到高斯噪聲的影響。而所提策略基于BPSO算法，尋優能力更強，因此能夠以最少的迭代次數實現收斂。

信道帶寬的變化對所提策略能量損耗的影響如圖7所示。

圖7 信道帶寬變化對能量消耗的影響

從圖7中可以看出，總帶寬越大，能量消耗越低，并且隨著帶寬的增加，當帶寬還處于一個較低水平時(如6 MHz)，能量消耗迅速降低；當帶寬已經到達一個很高的水平時(如15 MHz)，能量消耗會緩慢降低。即較高的帶寬會導致較低的傳輸延遲，而這就意味著處理每一位數據時的能量消耗較小。此外，邊緣節點和移動設備之間的傳輸延遲遠小于邊緣節點和云服務器之間的傳輸延遲，因為基站建造時十分接近移動設備，而云服務器卻離移動設備更遠。因此，與卸載到云服務器相比，帶寬的變化對卸載到基站這種方式的影響更小。

不同任務數據量大小對能量消耗的影響如圖8所示。

圖8 任務數據量大小與能耗的關系

從圖8中可以看出，隨著任務數據量的增加，能量消耗也隨之增加，但是并不是線性變化。這是因為計算延遲或能量消耗遠小于傳播時的延遲與能量消耗，而且任務數據量的大小對傳播時的能量消耗的影響也相對較小。在這種情況下，隨著任務數據量的增加，總體的能量消耗會在一定范圍內以逐漸減小的速度上升。

4.3 不同策略的對比分析

為了論證所提任務卸載策略的性能，將其與文獻[10]、文獻[13]、文獻[17]中策略的能量開銷進行對比分析，結果如圖9所示。

圖9 不同任務卸載策略的能量消耗情況

從圖9中可以看出，隨著移動用戶數量的增加，文獻[17]策略的能量開銷略微高于所提任務卸載策略的能量開銷，導致這一現象的原因在于該最優解的獲取與迭代次數有著直接關系，如果迭代次數有限那么最終的結果僅僅就是一個局部最優的結果。利用BPSO則很好地解決了這一問題。因此相比于其它3種策略，其能耗最低。同時，文獻[13]中通過深入分析發現本地計算所需要的能量遠遠超過了卸載方案，同時當終端設備數量不斷上升時本地計算所需能量的增加也不是非線性的。在該文獻中所選擇的卸載方案對能量優化效果遠遠低于文中所提到的其它方案，導致這一問題的根源在于隨機選擇接入的條件下，如果同時接入基站的終端設備數量陡然增加，那么必然會造成同一個信道被多個設備使用，這樣就使得前向以及后向鏈路都受到一定的作用從而降低了傳輸速度，這樣能量損耗自然會有所上升。

此外，在不同移動設備數量的情況下，所提任務卸載策略與文獻[10]、文獻[13]、文獻[17]中策略的系統整體負載對比情況如圖10所示。

圖10 不同任務卸載策略的系統平均整體負載情況

從圖10中可以看出，文獻[10]中采用本地執行方案，其具有最大的系統整體負載，在其余各個卸載策略中，其它方案都有效減少了系統的載荷，這也就意味著當任務卸載至邊緣計算中后，用戶可以得到更好的服務體驗。所提策略的系統整體負載最低，比文獻[10]策略相比，平均降低67.5%的系統負載，性能提升效果很明顯。文獻[13]采用隨機卸載方案，其系統整體負載也較大，由于其隨機地將任務卸載到邊緣計算或者云計算服務器上，忽略了不同用戶之間會有一定的干擾，所以有時卸載并未顯著提高性能。與這兩個文獻不同的是文獻[17]策略的系統整體負載明顯降低，但仍高于所提策略，由于其忽略了在 MEC 服務器中的等待延遲。

5 結束語

隨著移動互聯網的快速崛起，各種終端設備被研發出來并且走入了人們的生活，但終端自身資源有限，無法滿足部分應用對計算性能的需求，為此，充分挖掘邊緣計算的潛力，尤其是對于技術上已經相對比較成熟的云計算如果能夠將其運用至接入網絡邊緣，將會更大提升用戶的體驗感，本文提出了一種移動邊緣計算中利用BPSO的任務卸載策略。基于構建的三層移動邊緣計算(MEC)網絡架構，并根據網絡的計算模型、通信模型設計計算卸載優化目標，利用BPSO算法進行求解，以得到最優卸載策略，滿足能量消耗小、時延低且整體負載均衡的需求。此外，基于MATLAB仿真平臺對所提任務卸載策略的性能進行實驗論證，結果表明，所提策略能夠實現能量消耗曲線的快速收斂，基站數量越多、信道帶寬越大，系統能量損耗越小，但移動設備越多，能耗越大。

本文提出的方案對于MEC節點計算具有顯著效果，但是該方案首先要假定所有的CPU能耗均屬于線性，也就意味著當占用率提高時該值并不會明顯提升，這與現實情況有一定的差異。為了解決這一問題還要對CPU能耗開展深入研究并建立相應的數學模型，這將是下一步的研究重點。