D2D網絡中基于多目標優化的計算卸載策略

陳 琦，李晶晶

（華南師范大學計算機學院，廣東 廣州 510620）

0 引言

隨著移動通信技術的發展和智能終端的普及，用戶對網絡服務質量、請求時延等網絡性能的要求越來越高。盡管移動設備的處理能力越來越強大，但依然無法在短時間內處理計算密集型或時延敏感型計算任務。為此，研究者們提出了移動邊緣計算（Mobile Edge Computing）［1］，并應用在不同的場景中（如5G網絡［2］、物聯網［3］等）。作為移動邊緣計算的關鍵技術之一，計算卸載［4］是指移動設備將部分或全部計算任務交給云計算［5］處理的技術，用于解決移動設備在資源存儲、計算性能以及能效等方面存在不足的問題。

傳統的移動邊緣計算卸載通過網絡接入點（Network Access Point，NAP）將任務卸載到基站、邊緣服務器或者其他設備，這種卸載模式依賴于網絡基礎設施和云服務器等設施［6］，可能會帶來一些問題：首先，隨著對云服務需求的不斷增加，這些設施需要頻繁更新擴容和定期維護；其次，將計算工作負載卸載到云服務器會給移動用戶帶來數據通信和租用云服務的高昂成本［7］；最后，移動設備的互聯網訪問可能在某些區域不可用［8］，例如基站無法覆蓋的森林、地下礦場等，這導致設備無法卸載計算任務。對于上述問題，一種解決方案是避免使用這些額外的設施，通過短距離無線網絡接口將工作負載卸載到附近的移動設備，即D2D計算卸載［9］。

1 相關工作

在D2D 網絡的計算卸載中，計算時延、計算能耗和任務成功率是重點關注的問題，已有許多國內外學者在這些方面進行了深度研究。

一個密集型應用可以拆分成若干的程序塊并分配給不同的設備并行執行，以此縮短應用的執行時間。文獻［10］提出了一種博弈論框架來減少無線D2D 網絡中的任務執行時間。文獻［7］將壓縮視頻文件的任務拆分并分配給附近的手機終端，減少視頻壓縮時間。文獻［11］提出了一種啟發式算法來最小化任務執行中的延遲。文獻［12］提出了多維拍賣將任務分發到附近的設備，因此可以最大限度地減少延遲。

大量數據的處理會消耗過多能量，通過計算卸載可以有效減少能耗。為了最小化能耗，文獻［13］提出一種基于穩定匹配的多用戶計算卸載資源優化決策算法；文獻［14］提出了圖匹配；文獻［15］提出了一個混合整數非線性規劃問題；文獻［16］提出了一種隨機搜索算法；文獻［17］提出了單維搜索。

任務成功率受設備移動性影響，為了提高成功率，文獻［18］通過基于最佳響應動態算法獲得多策略約束的納什均衡；文獻［19］采用多階段隨機規劃方法來補償不準確的移動性預測；文獻［20］中通過考慮節點之間的社會關系并發現其聯系模式中隱藏的規律。

上述文獻關注的問題中存在時間和能量等多種量綱且相互制約的變量，這些變量大多通過權值進行分配，也有學者采用多目標優化進行處理。文獻［21］將任務卸載至云服務器，提出了多目標優化問題，通過找到最優卸載概率和最優傳輸功率，以最小化能耗、執行延遲和價格成本。文獻［22］提出了一種全局最優多目標任務卸載優化算法并基于Kuhn-Munkres算法進行求解。這些文獻將任務卸載到云服務器，且很少考慮任務負載的劃分。文獻［23］基于粒子群優化的計算卸載算法，優化車輛邊緣計算的延遲與成本多目標優化問題。文獻［24］結合遺傳算法和帕累托最優概念，提出了快速非支配遺傳算法（NSGA-II），為處理多目標優化問題提供啟發式的智能求解算法，許多學者將此算法應用于邊緣計算的研究中。文獻［25］改進NSGA-II 用于處理無線多熱點網絡的負載均衡，平衡網絡吞吐量與設備選擇接入AP的關系，但沒有考慮最短時間與最小能耗的問題。文獻［26］將NSGA-II應用于工作流應用程序的計算卸載，考慮將應用卸載到cloudlet和云。文獻［27］提出基于NSGAII的卸載算法，節省了云機器人的能耗和程序執行時間。這2 篇文獻都對時間、能耗進行了優化，但仍然依賴于遠程云，存在遠程服務設備不可用的風險，并且沒有考慮設備移動性對任務成功率的影響。上述的文獻將NSGA-II 應用在遠程云服務的計算卸載研究中，但少有人考慮到網絡設施不可用的情況，此時將任務卸載到附近的設備是更好的選擇，因此，將NSGA-II 應用于D2D 網絡計算卸載決策問題具有現實意義。

基于以上研究，本文的主要工作如下：

1）結合實際應用場景對問題建模，充分考慮設備和任務的異構性，設備的異構包括不同的計算能力、電池容量和隨機移動性，任務的異構包括不同發布時間和不同的輸入數據規模。

2）提出過度卸載的概念，分析過度卸載對執行時間、執行效率和錯誤處理的影響，并提出減少遠程卸載數據量的方法。

3）基于NSGA-II算法，提出計算卸載算法，求出帕累托最優解集，對執行延遲目標和能耗目標進行優化。

4）提出數據路由算法（DRA），優化數據路由路線，平衡數據路由對路由節點的能耗。

2 系統模型

2.1 網絡模型

圖1展示了一個D2D 網絡的場景，每個設備只能通過無線局域網進行交互，例如WiFi-Direct。在一個由N個移動設備組成的網絡中，記I={ }1，2，…，N，每個移動設備都有有限的計算能力和電池能量，分別用RN和PN表示。設備以速度VN移動。如果設備j在距離dmax內，假設設備i可以直接與設備j連接，稱設備j是設備i的鄰居，鄰居節點之間采用D2D 連接實現無線交互。網絡中的設備分為2 類，當一個移動設備需要執行一項計算密集型任務時，稱為任務設備（Task Device，TD），當一個設備處于空閑狀態時，它可以與其他設備共享資源，稱為資源設備（Resource Device，RD）。在不同時間點，每個設備都可以作為TD或者RD。

圖1 D2D網絡場景

2.2 任務模型

時間線可以切分為多個時隙，每一個時隙定義為t。在一個時隙內，每個設備都可能在不同的時間點產生一個任務，用二元組Ki={ }Di，Ci表示，其中i表示設備i，Di為任務數據大?。▎挝粸閎it），Di取自[Dmin，Dmax]，Ci為處理單位數據所需的CPU 周期。一個時隙內所有設備產生的任務的總數量m遵循泊松分布，m不會超過設備總量N。假設λ為任務的泊松分布到達率，定義為λ=kN，其中0≤k≤1。

2.3 移動模型

設備以速度VN隨機移動，這可能導致RD 與TD斷開連接，因此需要注意TD 與RD 的連接時間，確保數據傳輸和計算結果回傳正常。假設每個設備都會記錄一段時間內的位置，由此可以求出這段時間設備的平均速度VAvg。RD 的VAvg在卸載請求時已被TD 收集。TD 計算各個RD 的任務完成時間T，并根據VAvg求出T時刻各設備的位置，從而判斷連接的可靠性。

2.4 時延模型

2.4.1 本地計算時延

TDi對Ki進行任務切分，Ki，i表示保留在TDi執行的部分，Ki，j(i≠j)表示傳輸到RDj執行部分，Ki，i的執行時間稱為本地計算時延。每個設備維護一個任務隊列，在同一時刻只執行一個任務。設τi，i為任務等待時間，為本地執行時延，則有：

其中，Di，i是分配給設備i的數據大小，Ri是設備i的計算能力。

2.4.2 數據發送時延

數據發送時延是指TD 發送數據塊的時長。設為RDj接收TDi的數據塊的結束時間，則有：

其中，為前一個設備接收數據塊的結束時間，ρTx為傳輸速率；Hi，j為TDi到RDj的跳數，數據從一個設備發送到鄰居設備稱為一跳。

2.4.3 遠程計算時延

在執行任務之前，RDj必須從TDi接收所有數據，在數據接收期間可以處理其他任務。若RDj數據接收完成時正在執行其他任務，則Ki，j加入任務隊列并等待當前任務完成。令τi，j表示Ki，j服務等待時間，則Ki，j完成的時間記為：

2.4.4 結果回傳時延

RDj在接收數據塊后向TDi返回Ki，j的預計完成時間，TD根據這個時間的先后順序向RD發送計算結果回傳請求。RD 開始發送結果的時間有2 種情況：1）任務執行結束立即發送，RD 在任務執行結束之前收到結果返回請求，完成了任務的執行且無其他數據正在發送，此時可以立即回傳計算結果；2）任務執行結束延遲發送，RD 在任務執行結束之后收到結果返回請求，無其他數據正在發送時返回計算結果。如果TDi收到RDj的計算結果，記為任務執行結束。令表示任務Ki，j執行結束時間，可由等式（4）得出：

其中，表示前一個設備的任務完成時間，ρRx是結果返回時的傳輸速度。

2.5 能量模型

2.5.1 任務執行能耗

任務執行能耗是設備執行任務產生的能耗。任務Ki，j的執行能耗由設備j的執行能量功率αj和計算時間決定。假設為任務Ki，j的執行能耗，表示為：

2.5.2 任務數據傳輸能耗

任務數據傳輸能耗是任務Ki，j進行數據發送和接收結果時產生的能耗。設和分別為設備n發送和接收1 bit 數據所需要的能耗。對于任務Ki，i，由于是在TDi本地執行，它的任務數據傳輸能耗為0。對于任務Ki，j(i≠j)，它的數據傳輸可能為一跳或者多跳。令＜a，b＞( )a，b∈I表示設備a到設備b的單跳傳輸過程，e＜a，b＞為傳輸能耗系數，表示為：

當Ki，j從TDi經過一跳到達RDj時，任務數據傳輸能耗可表示為：

當Ki，j經過多跳到達RDj時，假設k={k1，k2，…，kl}(k1，…，kl∈I)表示從TDi到達RDj的中繼設備集合，此時，Ki，j從設備i經過設備集合k到設備j的傳輸過程表示為＜i，k，j＞。由于多跳傳輸過程可以視為多個一跳傳輸過程之和，傳輸過程＜i，k，j＞可以拆分為＜i，k1＞，＜k1，k2＞，…，＜kl-1，kl＞，＜kl，j＞。因此，多跳任務數據傳輸能耗可表示為：

3 過度卸載

根據卸載到遠程設備的數據量，計算卸載可以分為完全卸載和部分卸載。對于完全卸載，一個任務的結束時間取決于所有遠程執行任務的計算結果返回時間。而對于部分卸載，除了遠程執行的任務之外，還需要注意本地執行的任務。通常，當TD 產生計算密集型任務時，它傾向于將盡可能多的數據卸載到RD，這可能會卸載過多的數據，稱為過度卸載（定義1）。過度卸載在資源浪費和卸載超時2 個方面影響計算卸載的效率，本文將通過圖2 和圖3 進行詳細分析，其中節點1為TD，其他結點為RD。

圖2 過度卸載

圖3 無過度卸載

定義1過度卸載。假設進行計算卸載的設備為TDi，最后一個返回計算結果的設備為RDn，(i，n∈I，i≠n)，當時，稱TDi存在過度卸載。

3.1 資源浪費

TD 過度卸載會導致資源浪費，主要表現在3 個方面：

1）TD 計算資源的浪費。由于遠小于，TD 過快進入空閑狀態，導致其計算資源無法有效利用。如圖2 所示，t0是TD 上本地執行任務的完成時間，而t2是最后一個RD 結果回傳的結束時間，可見TD在t0到t2時間內處于空閑狀態。

2）卸載大量數據會占據網絡資源。當數據量較大時，傳輸時間較長，這可能導致網絡堵塞。

3）由于RD 需要接收所有數據后才能進行計算，當過大的數據傳輸會導致RD 長時間處于接收狀態而無法提供有效的卸載服務。

3.2 卸載超時

卸載過程中可能出現設備掉線、任務執行錯誤等情況，TD 需要及時做出處理，否則可能出現卸載方案比本地執行方案使用更長的執行時間的情況。如圖2 所示，考慮最壞情況，TD 在發送所有數據之后（t1時刻）無法接收所有RD 的執行結果，并需要在本地執行未完成的子任務。由于TD 在t0到t1之間處于空閑狀態，它需要在t2之后繼續執行t1-t0時長，可見進行卸載時的總執行時間比不進行卸載時的總執行時間長，即卸載超時。

3.3 問題解決

對于處理過度卸載，最有效的辦法是限制卸載數據的大小，保證TD 在整個卸載過程中不處于空閑狀態。此時，TD的本地計算時延大于最后一個RD的任務執行結束時間。假設最后一個返回計算結果的設備為RDn，則有

如圖3 所示，在無過度卸載場景下，TD 保留更多的數據在本地執行，從而減少了網絡傳輸以及RD 執行任務的時間。計算卸載的結束時間從RD 結果回傳的結束時間t2縮短到TD上執行任務的結束時間t'0，因此無過度卸載要比過度卸載有更高的計算卸載效率和資源利用率。另外，TD 作為最后一個完成子任務的設備，可以及時發現存在的卸載失敗并進行處理。TD 可以在t'0之前檢測到卸載失敗，并將失敗的子任務加在當前執行任務之后，實現子任務無縫切換（任務的切換時間忽略不計），在最差的情況下，所有子任務都在TD 上執行，總執行時間等于本地執行方案的總執行時間，這有效防止了卸載超時的發生。

4 問題形式化與算法

TD（ii∈I）在一個時間周期t內隨機產生一個任務，記為Ki={Di，Ci}，該任務需要消耗大量的執行時間和能量。TDi的附近存在空閑的RD（ji∈I，j≠i），它們可以為TDi提供計算資源。TDi產生一個任務后廣播其卸載請求，RDj收到請求后，回復自己的設備狀態。TDi在收集到RDj的響應之后將Ki劃分為子任務Ki，j={Di，j，Ci}，其中Di，j≤Di，并做出卸載的決定，稱為卸載決策問題。本文將卸載決策問題轉化為求解多目標最優解問題，該問題包括任務執行時間最小化問題以及卸載能耗最小化問題。設卸載決策問題的最優決策為X，它可以表示為下列的決策向量：

其中，X的每一列表示TD的對RDj的卸載決策，表示形式為百分比，xi，n表示最后一個設備n的卸載決策。因此，Ki，j也可以表示為Ki，j={xi，jDi，Ci}。

4.1 多目標函數

由第2節、第3節的分析可知，卸載的完成時間是TD對計算結果接收完成的時間，包括接收RD遠程計算結果的時間以及本地處理數據的時間，定義為：

總能耗等于任務執行能耗和任務數據傳輸能耗之和，定義為：

則多目標函數F（x）表示為：

卸載決策問題轉化為求解多目標最優解問題，可由下式給出：

其中，式（15）解決過度卸載問題；式（16）表示任務Ki，j消耗的能量不能高于RDj的剩余能量；式（17）表示RDj分配的數據量應大于最小執行數據量；式（18）表示各個設備數據分配的權重之和為1；式（19）表示RDj在(xi，j)時刻與TDi斷開連接的概率應小于。如圖4所示，令為TDi在時刻的位置，為RDj響應卸載請求時的位置，則RDj在之前的移動范圍為以為圓心半徑為rj的圓形區域，其中rj為平均移動距離。當RDj移動出TDi的通信范圍外，即S區域時，將其視為RDj掉線，此時無法進行數據傳輸。因此，RDj的掉線概率為：

圖4 RDj掉線區域

由于多目標優化中存在多個目標函數，并且它們的量綱不一致，對于可行解集的解，無法用傳統的等于、大于或小于等數量關系進行優劣關系的比較和排序，需要用另外一種關系來定義2 個可行解的優劣關系，稱為帕累托支配（Pareto Domination），又稱帕累托占優。設xA，xB∈X是公式（14）的2 個可行解，則稱與xB相比，xA是帕累托占優的，當且僅當：?i=1，2，…，F（ixA）≤F（xB）且至少存在一個j∈{1 ，2，…，m}，使得Fj（xA）＜F（xB），則稱xA支配xB，記為xA?xB。帕累托最優解（或非支配解）可以表述為可行解xA∈X，當且僅當：?x∈X，使得x?xA。

因此公式（14）的解以帕累托最優解的集合構成，稱為帕累托最優解集，定義如下：

4.2 計算卸載決策算法

基于NSGA-II，本文提出計算卸載決策算法。首先，算法根據RD 的計算能力和任務隊列信息求得任務Ki，j的服務等待時間τi，j并將RD 進行排序得到發送隊列順序，這可以有效減少任務Ki，j的執行時間；其次，算法根據設備的位置、平均速度、計算能力、能耗系數和任務隊列等設備信息求得目標函數值；最后，算法提出適用于計算卸載的基因編碼、交叉和變異方法。

4.2.1 編碼

傳統的遺傳算法的基因編碼包括二進制編碼、符號編碼和實數編碼等，在本文中，計算卸載問題的解表示為各個設備分配數據量的百分比，因此基因值應該為［0，1］區間的浮點數，且所有基因值之和等于1，這可以由一組隨機數除以它們的均值得到。假設多目標問題的解為n維向量Xf=[x1，…，xn]，n維隨機數組U=[u1，…，un]，則基因編碼可由下式得到：

4.2.2 交叉

在卸載決策場景中，每個基因表示分配數據的比例，2 個個體基因的簡單交換會改變其他基因所占有的比重，無法保持父代的性狀。因此基因的交換并不是交換基因編碼，而是交換多個隨機位置上所占基因的比例。如圖5 所示，設父代1 和父代2 為進行基因交叉的個體，總共有8 個基因位點，其中假設父代2 的4 和6 位點被父代1 替換，且a4+a6≠b4+b6，則子代的基因編碼之和不等于1，并且子代無法保留父代2的性狀。令A和B分別為父代1和父代2替換位點基因值組成的集合，A=［a1，…，an］，b=［b1，…，bn］，則子代交叉生成的基因值由下式給出：

圖5 交叉

4.2.3 變異

如圖6 所示，個體在4 和6 號位點發生變異，需要滿足b'4+b'6=b4+b6。假設n維變異位點集合B=[b1，…，bn]，n維隨機數組V=[v1，…，vn]，滿足變異后的位點集合為B'=[b'1，…，b'n]，則b'i可表示為：

圖6 變異

4.3 數據路由算法

得到卸載決策后，TD通過D2D無線鏈路向RD發送數據，為此，本文提出了數據路由算法（Data Routing Algorithms，DRA）。首先，數據傳輸需要確定路由表。如果RD 在TD 的通信范圍內，則可以直接傳輸，記這些節點為RDin，如圖7（a）中的節點1、2 和3。對于TD的通信范圍之外的RD，數據傳輸需要路由節點，這些節點記為RDout，如節點4、5、6和7。令Aj表示RDin的集合，其中RDin表示RDout和TD 的共同鄰居，數據可以通過Aj進行路由。任何一個RDin都應該盡可能地協助完成數據路由，單一節點不能實現數據塊的并行傳輸，并且可能會過快消耗路由節點的能量。記RCi為RDin轉發數據塊的計數，RDoutj選擇RCi最小的RDini作為下一跳路由節點，然后RCj加1，直到存在TD 與RDoutj的路徑Pj。之后，數據塊的發送需要確定順序，以減少數據傳輸碰撞?；诼酚杀?，可以得到圖7（b）所示的路徑有向圖，它最終轉化為一個傳輸隊列Sq。首先，對節點0 上的3 棵子樹分別進行前序遍歷，得到隊列1、2 和3（Sq1、Sq2和Sq3）；之后，取Sq1的隊首壓入Sq；然后，依次取Sq1、Sq2和Sq3的隊首壓入Sq，直到所有隊列為空。DRA如算法1所示。

圖7 節點位置和路徑有向圖

算法1數據路由算法

輸入：TD，RD

輸出：Sq

1 RDin←{v|v∈RD，v在TD范圍內}；

2 RDout←{v|v∈RD，v不在TD范圍內}；

3Aj←{v|v∈RDin，v為TD和的共同鄰居節點}；

5 whilePj=Φ

6 在Aj中取最小RCi的節點RDini作為下一跳節點；

7 RCi加1；

8 end

9 end

10 創建路徑有向圖T0，設T1，…，Tk為T0的k棵子樹；

11 foreachTkdo

12 Sqk←對Tk進行前序遍歷；

13 end

14 將Sq1隊首壓入Sq；

15 while Sq1，…，Sqk≠Φ do

16 foreach Sqkdo

17 將Sqk隊首壓入Sq；

18 end

19 end

5 性能評估

本文在NS-3 上模擬無線通信網絡的傳輸，實驗場景由10 個移動節點組成，它們隨機分布在一個50 m×50 m 的平面空間中，以［1，3］m/s 的速度在不同方向上進行均勻的移動，并且可以在某個點改變方向。在通信范圍R=40 m 的范圍內，2 個移動設備通過WiFi-Direct 連接。在一個任務產生周期t=120 s 內，所有設備都隨機產生任務，任務總數量遵循泊松分布（λ=0.25）。每個設備都有計算能力，為了更加直觀地表示數據量與計算能力的關系，本文將計算能力的單位轉化為kbit/s，設備的計算能力的大小遵循高斯分布，其中μ=1024×1.0，σ2=（1024×0.4）2。通過計算卸載算法求得時間最優分配（Time Optimal Allocation，TOA）以 及 能 量 最 優（Energy Optimal Allocation，EOA），并與以下基線方案進行比較，分析數值結果評估所提出算法的性能：

1）本地計算（Local Computing，LC）：TD 生成的數據僅在本地執行，不進行計算卸載。

2）平均分配（Equal Allocation，EA）：TD 根據可卸載設備數量平均劃分數據。

3）計算能力分配（Computing Power Allocation，CPA）：TD 根據可卸載設備的計算能力作為權重進行數據劃分。

5.1 平均執行時間

圖8 顯示了任務數據大小對平均執行時間的影響。當數據量小于10 MB 時，所有卸載方案都會選擇本地執行。當數據量在［10，40］MB之間時，所有卸載方案的平均執行時間都以平穩的趨勢上升，其中CPA、TOA 和EOA 的平均執行時間都要比EA 少。當數據量大于40 MB 時，TOA 偏向于執行時間的最小化，所以平均執行時間比其他的卸載方案更少；而EA的平均執行時間最長；相對于其他3 種方案，CPA 是最不穩定的，因為當TD計算能力較弱時，CPA會選擇卸載更多的數據，而卸載數據量較大時，會產生網絡擁堵，增加傳輸時間。綜上所述，在數據量較少時，所有卸載方案的平均執行時間基本一致；當數據量較大時，TOA相對其他卸載方案能得到最小的平均執行時間。在穩定性方面，TOA、EOA和EA平均執行時間變化較為穩定，而CPA受網絡影響較大。

圖8 平均執行時間

5.2 平均提升效率

提升效率是一個任務節省的時間與本地執行時間的比值，而平均提升效率是所有任務的提升效率的平均值。圖9 是任務數據大小對平均提升效率的影響。當數據量在［20，40］MB 時，TOA、EOA 和CPA 都在20 MB 時迅速達到較高的水平，之后緩慢提升。CPA 的平均提升效率要比EOA 高，這說明在數據量較少的時候，根據計算能力進行數據劃分能得到較好的提升效果。EA 則是穩定緩慢提升，可見根據設備的不同狀態進行數據劃分更能有效提升計算效率。在40 MB 時，所有的卸載方案的平均提升效率都達到峰值，其中TOA 為41.7%，EOA 為37.2%，高于其他方案。當數據量大于40 MB 時，所有卸載方案的平均提升效率開始下降。TOA 和EOA 在80 MB 之后趨于平衡，TOA 收斂于31.8%，EOA 收斂于26.8%。EA和CPA 下降非常迅速，收斂值均在21%左右。因此，TOA 和EOA 進行計算卸載的平均提升效率明顯比EA和CPA穩定，且TOA能取得較好的提升效率。

圖9 平均提升效率

5.3 卸載數據量

圖10 對比了不同卸載方案向附近RD 卸載數據的數據大小的區別。EA卸載的數據量呈現線性上升趨勢，與響應卸載請求的RD 數量成正比。CPA 根據計算能力大小進行數據劃分，計算能力較強的設備將處理更多的數據，而計算能力較弱的設備將分配更少的數據。在數據量小于70 MB 時，CPA 方案卸載的數據量要多于EA 方案。對于TOA 和EOA，卸載的數據量要明顯低于其他方案，節約了能耗成本，同時也節約了網絡資源。當數據量在［20，40］MB 之間時，TOA 和EOA 卸載的數據量基本相同，在40 MB 之后，EOA 的卸載數據量要明顯低于TOA。這是因為計算卸載算法考慮了過度卸載問題，對卸載的數據量進行限制，節約了數據傳輸的時間。

圖10 卸載數據量

5.4 卸載對象選擇對能耗的影響

圖11對比了不同卸載方案的能量消耗情況。EA方案的能耗明顯高于其他方案。TOA、EOA 和CPA在40 MB 之前的能耗大體一致，而在40 MB 之后，EOA 要明顯低于其他方案，這主要包括2 方面原因。1）卸載數據量較少。如圖10 所示，EOA 卸載的數據量明顯少于其他方案，這減少了傳輸能耗。2）卸載對象的選擇。圖12 展現各個卸載方案生成的子任務數量，EOA 會選擇將任務卸載到計算能力較強的設備，淘汰計算能力較弱的設備，從而節省能量，TOA 則是盡可能利用空閑的RD 進行任務卸載，這樣可以獲得更多的時間效益，但也比EOA消耗更多的能量。CPA和EA 并不考慮時間效益和能耗效益，而是盡可能多地將數據發送到附近的RD 進行處理，導致消耗更多的數據傳輸時間和數據傳輸能量。

圖11 能耗

圖12 子任務總數量與重傳子任務數量

5.5 子任務重傳率

子任務重傳率是重傳子任務總量與子任務總量的比值，它代表了卸載方案的可靠性。如圖12 所示，EOA、TOA、CPA 和EA 的子任務重傳率分別為9.3%、7.8%、22.6%和17.3%，可見EOA 和TOA 要明顯優于CPA 和EA。這得益于2 個方面原因：1）對于過度卸載的處理，限制了卸載的數據量，有效防止了網絡堵塞；2）對設備掉線率的考慮，TOA 和EOA 在進行卸載對象的選擇時，考慮了設備連接性，這有效提高了任務卸載的成功率。

6 結束語

本文研究了移動邊緣計算中D2D 網絡的計算卸載問題，將該問題轉化為多目標優化問題，并提出了一種計算卸載算法求解時間最優解和能量最優解。另外，本文提出了過度卸載的概念，分析過度卸載對于部分卸載的不利影響并提出解決方案，限制TD 的卸載數據量，有效提高TD 的資源利用率并解決卸載超時問題。在模擬實驗中，本文將所提出算法與基準卸載方案進行比較，在不同的場景下評估算法的效率。實驗結果表明，在提升效率方面，各個卸載方案在數據量為40 MB 時可以達到最高的平均提升效率，其中TOA 遠高于其他方案，并且當數據量增大后，TOA 也能有較好的平均提升效率；在能耗方面，EOA 可以節省更多能耗；在數據傳輸量方面，TOA 和EOA 能有效減少數據傳輸量，有效減少網絡擁堵；在任務重傳率方面，TOA 和EOA 能夠有效減少數據傳輸錯誤的情況。