基于終端直通通信的多用戶計算卸載資源優(yōu)化決策

李余，何希平，唐亮貴

（1.重慶工商大學 計算機科學與信息工程學院，重慶 400067； 2.重慶市檢測控制集成系統(tǒng)工程實驗室（重慶工商大學），重慶 400067）（?通信作者電子郵箱liyu@ctbu.edu.cn）

基于終端直通通信的多用戶計算卸載資源優(yōu)化決策

李余1，2*，何希平1，2，唐亮貴1，2

（1.重慶工商大學 計算機科學與信息工程學院，重慶 400067； 2.重慶市檢測控制集成系統(tǒng)工程實驗室（重慶工商大學），重慶 400067）（?通信作者電子郵箱liyu@ctbu.edu.cn）

隨著計算密集和時延敏感類應用的激增，移動邊緣計算（MEC）被提出應用在網(wǎng)絡邊緣為用戶提供計算服務。針對基站（BS）端邊緣服務器計算資源有限以及網(wǎng)絡邊緣用戶遠距離計算卸載的時延較長等問題，提出了基于終端直通（D2D）通信的多用戶計算卸載資源優(yōu)化決策，將D2D融入MEC網(wǎng)絡使用戶以D2D方式直接卸載任務到相鄰用戶處執(zhí)行，從而能夠進一步降低卸載時延和能耗。首先，以最小化包括時延和能耗的系統(tǒng)計算總開銷為優(yōu)化目標，建模多用戶計算卸載和多用戶計算資源分配的聯(lián)合優(yōu)化問題；然后，將求解該問題看作是一個D2D配對過程，并提出基于穩(wěn)定匹配的低復雜度的多用戶計算卸載資源優(yōu)化決策算法；最后，迭代求解D2D卸載的優(yōu)化分配決策。通過理論證明分析了所提算法的穩(wěn)定性、最優(yōu)性和復雜度等特性。仿真結果表明，所提算法相較于隨機匹配算法能夠有效降低10%～33%的系統(tǒng)計算總開銷，并且其性能非常接近最優(yōu)的窮舉搜索算法?？梢?，所提基于D2D卸載的決策有利于改善時延和能耗開銷性能。

移動邊緣計算；終端直通通信；計算卸載；資源分配；穩(wěn)定匹配

0 引言

隨著第五代移動通信（Fifth Generation， 5G）的發(fā)展和商用，越來越多的移動應用，如物聯(lián)網(wǎng)、增強現(xiàn)實、視頻流處理等，不僅需要高速數(shù)據(jù)傳輸并且要求強大計算資源的時延敏感的新應用正在迅速被普及［1］。為了能夠支持這些對計算資源和時延有特殊需求的應用，移動邊緣計算（Mobile Edge Computing， MEC）應運而生。MEC是一種相當有潛力的新興5G服務方案，主要利用用戶鄰近的無線網(wǎng)絡邊緣設施或者大量的用戶端設備協(xié)作，代替遠端云計算來執(zhí)行大量的通信和計算服務［2］。與云計算相比，MEC能夠在網(wǎng)絡邊緣，即無線接入網(wǎng)端提供與云計算相當?shù)哪芰?，從而使用戶能夠以較近的距離卸載其計算任務，實現(xiàn)低時延且靈活的計算和通信擴展服務［1-2］。

針對用戶計算任務的卸載問題，大多數(shù)研究都集中于基于邊緣服務器的MEC網(wǎng)絡資源管理，即在考慮無線通信和移動計算準則下，用戶可將計算任務卸載至網(wǎng)絡邊緣高速的計算服務器［3］。該方式下的計算卸載模型可劃分為二元卸載和部分卸載兩大類。在二元卸載方案中，用戶的計算任務要么全部在本地執(zhí)行要么全部卸載到邊緣服務器執(zhí)行。Wang等［4］利用圖著色算法設計了一種聯(lián)合二元計算卸載和通信資源分配的卸載決策。而在部分卸載方案中，用戶的計算任務可分割開來，一部分留在本地執(zhí)行，一部分卸載到邊緣服務器執(zhí)行。Ren等［5］建立了部分卸載模型分段的最優(yōu)化問題，并基于最優(yōu)數(shù)據(jù)分割策略中分段的結構提出了聯(lián)合通信和計算資源分配的最優(yōu)化算法。MEC網(wǎng)絡中僅利用邊緣服務器的計算卸載，不管是采用哪種卸載模型，雖然能夠使移動網(wǎng)絡的計算性能在一定程度上得到提升，但基站（Base Station， BS）端邊緣服務器有限的計算資源并不能保持一直足以支持其覆蓋范圍內的所有移動設備；而且由于用戶在網(wǎng)絡中分布的隨機性，尤其是對于分布在小區(qū)邊緣的用戶而言，基站端的邊緣服務器與用戶之間的距離可能會較遠，從而導致較長的卸載時延［6］。為了彌補MEC網(wǎng)絡中的這些不足，將允許終端之間無需經(jīng)過基站而直接進行通信的終端直通（Device-to-Device， D2D）融入MEC網(wǎng)絡，利用D2D通信輔助用戶計算任務卸載是一個值得關注的解決方案。

D2D通信利用蜂窩資源能夠支持網(wǎng)絡中用戶間直接的數(shù)據(jù)傳輸［7］，基于此網(wǎng)絡的大量移動設備在網(wǎng)絡中心的輔助控制下不僅可實現(xiàn)數(shù)據(jù)轉發(fā)和共享，還能夠實現(xiàn)資源共享和計算卸載。網(wǎng)絡中大量不同種類的設備，如物聯(lián)網(wǎng)設備、智能手機、平板電腦等，它們多樣化的計算能力以及復用增益可以被用來支持多種服務的協(xié)作計算任務執(zhí)行［8］。事實上，通過用戶間協(xié)作進行計算卸載時，卸載距離的明顯減少是通常被忽視的一個關鍵。從無線通信角度考慮，發(fā)送距離短就能以較低的功率消耗獲得較高的數(shù)據(jù)傳輸速率，從而當用戶間短距離進行任務卸載時能夠減少卸載時延和能量消耗［6］?？紤]到D2D卸載的優(yōu)勢，研究者們逐漸對基于D2D通信輔助的卸載決策展開了研究。Hu等［9］在考慮D2D卸載方式的情況下，設計了一種基于序貫決策博弈的多用戶計算卸載方法。Xing等［10］利用D2D將鄰近用戶當作協(xié)作計算的幫助者，通過聯(lián)合最優(yōu)化任務卸載、任務執(zhí)行和結果下載時間來最小化計算卸載時延。Feng等［11］在考慮計算資源均衡的基礎上，以最小化移動設備任務卸載開銷為目標，提出利用凸函數(shù)差分的迭代算法來解決計算卸載和資源分配的優(yōu)化問題。上述研究以及大多數(shù)D2D輔助的計算卸載決策，其算法的計算復雜度都非常高，并且優(yōu)化目標以最小化時延為單一目標居多，但D2D設備的能耗也是需要考慮的重點，還有一些研究僅僅利用了D2D卸載的概念，設備間通信仍然采用蜂窩通信。考慮到以上問題，本文利用匹配理論設計了一種低復雜度的D2D通信輔助的多用戶計算卸載資源優(yōu)化決策。

本文將D2D通信與D2D卸載融入MEC網(wǎng)絡形成D2D-MEC網(wǎng)絡架構，在最小化系統(tǒng)計算總開銷的基礎上進一步降低用戶的卸載時延和能耗。考慮多用戶計算任務卸載場景，這些用戶各自有一個獨立的計算任務需要被執(zhí)行，但由于其自身大量的中央處理器（Central Processing Unit， CPU）資源被計算任務的一部分或者其他應用所占用，需要卸載全部或已分割的部分計算任務到鄰近的擁有閑置CPU資源的設備處執(zhí)行。通過對計算任務在D2D傳輸和執(zhí)行階段的時延和能耗開銷建模，以最小化包括時延和能耗的系統(tǒng)計算總開銷為優(yōu)化目標，將多用戶計算任務卸載和多用戶計算資源分配問題，建模為最小化系統(tǒng)計算總開銷的整數(shù)規(guī)劃問題。針對該問題，本文將多個用戶的計算任務卸載和多個用戶的計算資源分配看作是他們之間的相互匹配，利用穩(wěn)定匹配給出了基于D2D通信的多用戶計算卸載資源優(yōu)化決策，以較低的復雜度實現(xiàn)了系統(tǒng)計算總開銷最小化，提升用戶體驗。

1 系統(tǒng)模型

1.1 網(wǎng)絡模型

本文考慮一個由宏蜂窩基站（BS）和多個移動用戶（User Equipment， UE）組成的D2D-MEC系統(tǒng)，如圖1所示。每個移動用戶不僅能夠與基站建立蜂窩通信鏈路，也能夠與其他鄰近的移動用戶以D2D通信的方式建立D2D鏈路。基站配備了一個MEC服務器為較大的計算任務卸載提供相應的計算卸載服務，而某些移動用戶較小的計算任務或者已分割的部分計算任務則可直接以D2D卸載的方式由鄰近的移動用戶提供計算卸載服務。為了降低計算卸載時延和能耗，避免因MEC服務器計算資源緊缺導致計算卸載擁堵，將鄰近用戶閑置的計算資源利用起來，可采用向鄰近移動用戶請求D2D卸載的方式執(zhí)行計算任務卸載。事實上，可將提供閑置計算資源的D2D用戶設備看作臨時的多個分布式小型移動MEC站，以近距離的方式為用戶提供卸載服務。當然這些D2D用戶設備除了能夠提供計算卸載服務以外，還能夠提供傳統(tǒng)的D2D協(xié)作通信及數(shù)據(jù)內容轉發(fā)和共享等服務，只是針對本文所考慮的問題，文中僅分析了D2D用戶設備的計算卸載能力。假設系統(tǒng)中有個需要請求D2D計算卸載的移動用戶，用集合表示。這個移動用戶均有一個獨立的并且時延較為敏感的計算任務需要向鄰近移動用戶請求計算卸載服務。相應地，系統(tǒng)中有個相鄰的有閑置計算資源能夠提供D2D計算卸載服務的移動用戶，用集合表示。為了避免復雜的信令交互并考慮到任務量較小，本文設定用戶的計算任務只能卸載到一個相鄰的用戶，提供計算服務的用戶也只會將其計算資源分配給一個請求卸載的用戶為其提供服務。雖然此設定在請求用戶多于服務用戶時可能會使少數(shù)請求用戶不能被立即分配服務用戶，但相較于一對多、多對一或多對多D2D卸載而言，此設定下請求用戶的任務不需要執(zhí)行復雜的算法再進行分割，系統(tǒng)處理復雜度較低，并且還能避免多個任務在一個服務用戶處排隊等候使服務用戶過載而造成卸載時延和能耗增加的情況。不失一般性，參考大多數(shù)移動邊緣計算［12］和移動網(wǎng)絡［13］的研究場景，為了分析的可行性并取得實用的結果，本文也采用半靜態(tài)的計算卸載場景，即在通常的一個計算卸載時間周期（百毫秒級）內，移動用戶集合和保持不變，而在兩個或多個周期內可能會有所變化。

圖1 D2D-MEC系統(tǒng)模型Fig. 1 D2D-MEC system model

以上假設是合理的，因為有些用戶自身可能不具備計算能力或者只具備較弱的計算能力，而計算任務通常又是時延敏感的，所以這些用戶自身不能按時完成全部任務時，就會發(fā)起全部或者部分任務的計算卸載請求，而請求卸載的計算任務量可能是較小的。鄰近的用戶他們可能擁有較強的計算能力，在有多余閑置計算資源的情況下，以D2D方式幫助相鄰的用戶完成較小的計算任務量卸載是能夠實現(xiàn)的。因為即使會消耗一些用戶的計算和能量等資源，但可通過一些互惠或補償手段使這些用戶愿意分享自身的資源提供服務，例如：請求卸載的用戶可向為他服務的用戶分享他較強的存儲資源或者以D2D方式分享他擁有的各種社會內容資源等。

1.2 通信模型

用戶間的D2D卸載需利用D2D鏈路傳輸計算任務和計算結果，D2D通信在蜂窩網(wǎng)控制下采用正交頻分多址接入方式接入無線信道［8］。因為信道狀態(tài)估計等內容不是本文的研究重點，所以假設通過信令反饋，基站能夠獲取信道狀態(tài)信息以及所有設備需要卸載的計算任務大小?；谧杂煽臻g傳播路徑損耗和瑞利衰落，請求計算卸載的用戶和提供計算卸載服務的用戶之間D2D鏈路的接收功率可表示為：

進一步地，用戶i和用戶j之間D2D鏈路可實現(xiàn)的數(shù)據(jù)速率表示為：

其中：W表示帶寬；表示信道的加性高斯白噪聲。

1.3 計算模型

1.3.1 任務傳輸階段計算開銷模型

1）時間開銷模型。

用戶i將計算任務的輸入數(shù)據(jù)通過D2D通信傳輸?shù)接脩鬸，基于1.2節(jié)通信模型中用戶i和用戶j之間D2D鏈路可實現(xiàn)的數(shù)據(jù)速率，傳輸輸入數(shù)據(jù)所消耗的傳輸時間可由式（3）計算：

2）能量開銷模型。

除傳輸時間開銷以外，由于用戶通常是能量受限的，為了盡可能延長工作時間提升用戶體驗，用戶所消耗的能量也需要被考慮。用戶i以功率將輸入數(shù)據(jù)通過D2D通信傳輸?shù)接脩鬸所消耗的能量取決于數(shù)據(jù)傳輸?shù)臅r間，所以傳輸輸入數(shù)據(jù)所消耗的傳輸能量可由式（4）計算：

綜合式（3）～（4），任務傳輸階段，用戶i計算任務包括時間開銷和能量開銷的計算總開銷為：

1.3.2 任務執(zhí)行階段計算開銷模型

1）時間開銷。

當用戶i的計算任務成功傳輸?shù)接脩鬸后，用戶j就會代替用戶i執(zhí)行相關的計算任務，不同用戶擁有的計算能力可能是不同的，設用戶j的計算能力，也即是CPU計算頻率為，那么用戶j計算接收到的計算任務所消耗的計算時間可由式（6）計算：

2）能量開銷。

用戶j計算接收到的計算任務會消耗自身能量，設是用戶j執(zhí)行計算任務時所需消耗的功率，其中是有效開關電容，根據(jù)文獻［15］的實測結果，可設置為，是一個正常數(shù)［16］。那么用戶j計算接收到的計算任務所消耗的計算能量可由式（7）計算：

綜合式（6）～（7），任務執(zhí)行階段，用戶i計算任務包括時間開銷和能量開銷的計算總開銷為：

1.4 問題建模

本文考慮用戶間以D2D方式進行計算任務卸載，為了使整個任務卸載過程中時延最小化的同時用戶的能耗也最小，提升用戶體驗，以最小化整個系統(tǒng)中所有用戶任務卸載過程中的計算總開銷，即包含任務傳輸和任務執(zhí)行階段總的時間開銷和能量開銷為目標函數(shù)，建立以下線性的全局優(yōu)化問題：

2 基于穩(wěn)定匹配的計算卸載資源優(yōu)化決策

2.1 匹配基礎

定義2不存在阻塞對的匹配是穩(wěn)定匹配。

本文中參與匹配的兩個有限不相交的集合分別是卸載請求的用戶集合和卸載服務的用戶集合。在匹配過程中，請求用戶和服務用戶都需要依據(jù)效用函數(shù)建立對另一邊集合的偏好序列。為匹配最佳的服務用戶，中的請求用戶會向其偏好序列中最高偏好的服務用戶發(fā)起匹配請求，因服務用戶對所有請求用戶有它自己的一個偏好，所以接收到請求的服務用戶會依據(jù)自己的偏好序列選擇接收或拒絕該請求用戶的請求。以此循環(huán)迭代進行匹配，在最終匹配結束時，請求用戶和服務用戶不可能同時存在比現(xiàn)在偏好更佳的其他對象，即不存在未匹配的請求用戶和服務用戶相較于當前的匹配對象，它們更愿意去打破當前的匹配使對方成為自己的匹配對象。

2.2 偏好序列的建立

要進行雙邊匹配，首先應根據(jù)用戶的不同偏好建立雙邊用戶的偏好序列，合理的排序規(guī)則是建立偏好序列的基礎。當請求用戶與不同服務用戶進行配對時，由于他與不同服務用戶之間通信距離不同且不同服務用戶的計算能力也不同，那么不同配對會得到不同的計算總開銷。同理，當服務用戶與不同請求用戶進行配對時，不同配對也會得到不同的計算總開銷。本文的優(yōu)化目標是最小化系統(tǒng)計算總開銷，因此請求用戶對服務用戶的偏好，以及服務用戶對請求用戶的偏好，都以式（5）和式（8）之和的計算總開銷為效用函數(shù)來衡量，也即是請求用戶和服務用戶以計算總開銷的大小為排序依據(jù)來建立偏好序列：總開銷越小，用戶的偏好就越高，排序就越靠前。

2.3 多用戶D2D計算卸載資源優(yōu)化決策算法

當偏好序列建立完成以后，請求用戶就會根據(jù)偏好序列向排在第一位的最高偏好的服務用戶發(fā)起匹配請求，相對應的服務用戶會根據(jù)自己的偏好序列作出選擇。參考文獻［18］中的穩(wěn)定結婚問題，本文給出了基于穩(wěn)定匹配的多用戶D2D計算卸載資源優(yōu)化決策，如算法1所示。

算法1 基于穩(wěn)定匹配的多用戶D2D計算卸載資源優(yōu)化決策算法。

1）初始化：設置相關參數(shù)，建立所有未匹配的請求用戶的列表集合，定義為

4） end for

7） end for

15） else

18） end if

19） else

20） 跳轉至第9）步

21） end if

22） end for

23） end while

算法1的具體步驟如下：

a）初始化系統(tǒng)和用戶各參數(shù)，建立所有未匹配的請求計算卸載的用戶集合列表。

d）收到任務卸載請求的服務用戶根據(jù)其偏好序列將發(fā)起請求的請求用戶與當前匹配對象進行比較，如果服務用戶更偏好發(fā)起請求的請求用戶，則接受發(fā)起請求的請求用戶拒絕當前匹配對象，該發(fā)起請求的請求用戶從未匹配列表中移除，而被拒絕的匹配對象則會被加入未匹配列表中；反之如果服務用戶更偏好當前匹配對象，則會維持當前匹配，拒絕發(fā)起請求的請求用戶，而被拒絕的發(fā)起請求的請求用戶會從自己的偏好序列中移除該服務用戶，更新其偏好序列，如步驟12）～18）所示。

e）算法迭代進行，未被匹配的請求用戶又會繼續(xù)向當前偏好序列中最高偏好的服務用戶提出新的任務卸載/匹配請求，直到與服務用戶匹配成功或者其偏好序列中再無可發(fā)起請求的服務用戶，如步驟8）～23）所示。

2.4 算法分析

下面對本文穩(wěn)定匹配算法的穩(wěn)定性、最優(yōu)性和復雜度等特性進行詳細分析。對于算法的收斂性，從算法1可知，當每一個請求用戶已經(jīng)成功匹配了合適的服務用戶，或者已經(jīng)被所有服務用戶拒絕時，本文算法經(jīng)過有限次迭代最終都會收斂形成穩(wěn)定匹配。

2.4.1 匹配算法的穩(wěn)定性

定理1匹配算法經(jīng)過有限次迭代收斂時，得到的匹配是穩(wěn)定的。

證明 根據(jù)定義2可知，沒有阻塞對的匹配是穩(wěn)定匹配。在匹配過程中，請求用戶和服務用戶均根據(jù)式（5）和式（8）之和計算偏好值，由于通信距離、任務大小和計算能力的不同，，；，，因此在建立偏好序列的過程中不存在阻塞個體，不同用戶將偏好值按照從小到大排序所建立的偏好序列是完全序。假設在匹配中存在請求用戶和服務用戶，他們相互沒有匹配但期望與對方匹配，表示為：。根據(jù)匹配原則，從算法1步驟11）可知，請求用戶i曾經(jīng)向服務用戶j提出過匹配請求，但最終表明在算法結束時服務用戶j拒絕了請求用戶i當時的請求。并且從算法步驟12）～18）可知，服務用戶j選擇了另一個他更偏好的請求用戶i，即，滿足。上述分析表明匹配中不存在阻塞對，與假設矛盾，所以算法1的匹配算法結果是穩(wěn)定的。

2.4.2 匹配算法的最優(yōu)性

定義3一個多目標函數(shù)的效用如果能在某種設定發(fā)生變化時得到提升，并且參與者也都同意這種變化，就是帕累托改進。如果在博弈匹配的過程中沒有帕累托改進，那么當前的匹配結果就是弱帕累托最優(yōu)［17］。

定理2所得匹配對于多用戶D2D計算卸載資源優(yōu)化是弱帕累托最優(yōu)的。

證明在本文匹配算法中，下一個選擇能夠得到更好的效用時個體偏好序列的指針才會移動，但不論是什么匹配結果，個體都不能為了獲取更好的效用而往回移動。假設存在匹配的帕累托改進：請求用戶i與服務用戶j匹配可以提高目標效用，即。如果在匹配中服務用戶j未匹配，那么，也即是請求用戶i與服務用戶j愿意互相匹配形成阻塞對，但這與定理1證明的匹配是穩(wěn)定的相矛盾。如果在匹配中服務用戶j已經(jīng)匹配了請求用戶i，i使得服務用戶j不能和i匹配。根據(jù)匹配原則可知，這表明i和i相比，i會讓j得到的效用更差，那么j不會選擇i進行匹配，則無法實現(xiàn)。綜合以上分析可知，匹配沒有帕累托改進，匹配是弱帕累托最優(yōu)。

2.4.3 匹配算法的復雜度

建立偏好序列時，雙邊集合中的每一個用戶都要計算另一邊集合中每個用戶的偏好值（計算總開銷），因此建立偏好序列的計算復雜度為。升序排列偏好值得到偏好序列的計算復雜度為。進行匹配的過程中，每個請求用戶最多向個服務用戶發(fā)起匹配請求，那么個請求用戶最多發(fā)起次請求，計算復雜度為。如果采用窮舉（枚舉）搜索法求解建立的優(yōu)化問題，則需要枚舉所有可能的配對，因此會出現(xiàn)的匹配結果總數(shù)（枚舉次數(shù)）為dt！×dt！，計算復雜度為（dt！×dt?。蝗绻捎秒[枚舉法這種特殊的分支定界法求解建立的優(yōu)化問題，相較于窮舉搜索法，該方法通過分支定界能夠減少枚舉的次數(shù)，計算復雜度為；如果采用隨機匹配法求解建立的優(yōu)化問題，算法復雜度隨服務用戶數(shù)的增加線性增加，計算復雜度為。通過對以上不同方法的復雜度進行分析對比可知，本文穩(wěn)定匹配算法的計算復雜度雖然略高于隨機匹配法，但相較于窮舉搜索法和隱枚舉法明顯更低，并且當參與個體越多時該優(yōu)勢越明顯。

3 仿真結果與性能分析

通過仿真對基于穩(wěn)定匹配的多用戶D2D計算卸載資源優(yōu)化決策算法的性能進行分析驗證?？紤]一個半徑為100 m的區(qū)域，個具有獨立計算任務的請求用戶和個具有閑置計算資源的服務用戶均勻分布在圓內。采用正交的信道資源，根據(jù)匹配的決策結果，一個請求用戶的任務可以D2D通信的方式卸載到相應服務用戶處執(zhí)行。具體設置的關鍵仿真參數(shù)如表1［4，8，10］所示。

表1 仿真參數(shù)Tab. 1 Simulation parameters

本文以最小化系統(tǒng)計算總開銷為優(yōu)化目標來制定多用戶D2D計算卸載資源優(yōu)化決策，因此通過仿真不同情況下的系統(tǒng)計算總開銷性能對本文算法進行分析。為了更加便于評估本文算法的有效性，選擇以下兩種算法分別作為上界和下界基準與本文算法進行比較：1）最優(yōu)的窮舉搜索算法，即通過枚舉搜索所有可能的配對來選擇最佳的進行匹配；2）隨機匹配算法，顧名思義即隨機選擇兩個用戶進行匹配。另外還將本文算法與把所有任務都卸載到遠端MEC服務器執(zhí)行的MEC卸載決策進行了比較。考慮到仿真的隨機性，所有仿真結果都是基于至少1 000次不同位置分布、不同任務大小和不同計算能力等條件的蒙特卡羅（Monte Carlo）隨機實驗平均值。

圖2給出了通過本文算法得到的計算總開銷隨請求卸載用戶數(shù)和服務用戶數(shù)變化的情況。由圖2明顯可知，系統(tǒng)計算總開銷隨著請求卸載用戶數(shù)（即任務數(shù)）和服務用戶數(shù)的增加而增加。當請求卸載用戶數(shù)一定即任務數(shù)一定時，增加服務用戶數(shù)能夠使相應數(shù)量的請求用戶的任務得到執(zhí)行，系統(tǒng)計算總開銷增加。特別地，當服務用戶數(shù)超過請求卸載用戶數(shù)時，系統(tǒng)計算總開銷逐漸降低。這是因為當有更多的服務用戶出現(xiàn)時，意味著有更多的計算資源能夠提供給請求用戶進行選擇，通過本文穩(wěn)定匹配算法，可使雙方選擇到更好的匹配對象。當服務用戶數(shù)一定時，同理分析可得。

圖2 請求卸載和服務用戶數(shù)對計算總開銷的影響Fig. 2 Impact of number of request offloading user and number of service users on total computing overhead

對比了本文算法與兩種基準算法的計算總開銷隨請求卸載和服務用戶數(shù)的變化情況，如圖3所示。

圖3 三種算法的計算總開銷對比Fig. 3 Comparison of total cost of three algorithms

從圖3（a）、3（b）中均可以看出，本文基于穩(wěn)定匹配的算法所得計算總開銷非常接近最優(yōu)的窮舉搜索算法，并且遠低于隨機匹配算法。窮舉搜索雖然能獲得最優(yōu)的性能，但其計算復雜度非常高，而本文算法能以較低的復雜度獲得與之相近的性能。特別地，圖3（a）中設置網(wǎng)絡中存在4個服務用戶（= 4），而請求卸載用戶數(shù)是變化的；圖3（b）中設置網(wǎng)絡中存在4個請求卸載用戶（），而服務用戶數(shù)是變化的。很明顯初始階段不同算法隨著用戶數(shù)的增加計算總開銷均會增加；當用戶數(shù)超過4時，本文算法與窮舉搜索算法的計算總開銷均有所減小，這與圖2所示結果一致，原因就不再贅述。而隨機匹配算法由于隨機選擇匹配對象，所以即使有更多的可供選擇的用戶出現(xiàn)，其計算總開銷也不會在超過4用戶數(shù)時有所減小而是趨于平穩(wěn)。

圖4（a）、4（b）、4（c）分別給出了三種算法的計算總開銷隨卸載任務數(shù)據(jù)量、任務所需CPU周期數(shù)和服務用戶CPU計算頻率（計算能力）變化的情況。

圖4 不同條件下三種算法的計算總開銷Fig. 4 Total cost of three algorithms under different conditions

其中，網(wǎng)絡設置有3個請求任務卸載的用戶和4個服務用戶，圖4（a）中請求用戶擁有相同的任務數(shù)據(jù)量，圖4（b）中請求用戶擁有相同的任務所需CPU周期數(shù)，圖4（c）中服務用戶擁有相同的CPU計算頻率?？梢钥闯?，本文算法仍明顯優(yōu)于隨機匹配算法，特別是任務量和計算能力不斷增加時差距更大，且仍非常接近窮舉搜索算法。另外明顯可以看出，任務數(shù)據(jù)量或所需CPU周期數(shù)的增加，會使任務傳輸或執(zhí)行階段的時延和能耗增加，所以計算總開銷隨之增加；但服務用戶CPU計算頻率的增加能夠縮短計算時延并減小計算能耗，因此計算總開銷隨之減小。

圖5比較了D2D卸載和MEC卸載兩種決策的各種開銷隨請求卸載用戶數(shù)的變化情況。設置網(wǎng)絡中請求卸載用戶數(shù)與服務用戶數(shù)相等，其中D2D卸載是指采用本文所述場景和卸載算法；MEC卸載是指將所有請求用戶的任務都卸載到相距200 m～700 m較遠的MEC服務器處執(zhí)行，MEC服務器CPU計算頻率為5 GHz。因為MEC服務器通常具備交流供電條件，所以MEC卸載決策執(zhí)行計算任務時的能耗開銷沒有考慮，其他開銷與D2D卸載同理計算可得。特別需要說明的是，在計算這兩種決策的時延開銷時，都是將每個用戶的時延開銷累加起來，沒有考慮任務被同時處理的情況。

圖5 不同卸載決策的開銷Fig. 5 Costs of different offloading policies

從圖5（a）中可以看出，D2D卸載決策的總開銷、總時延開銷和總能耗開銷均低于MEC卸載決策，特別是隨著請求卸載用戶數(shù)的增加，這種差距也隨之增大。從圖5（b）中可以看出，無論哪種決策，任務傳輸階段的總開銷均大于任務執(zhí)行階段的總開銷。此外，通過對比可以看出，由于MEC距離用戶較遠，所以任務傳輸階段所消耗的時延和能耗均遠遠大于D2D卸載決策。而任務執(zhí)行階段，由于MEC的計算能力比單個服務用戶高并且MEC決策未考慮能耗，所以任務執(zhí)行階段用戶累加起來的時延小于D2D卸載決策總的時延和能耗開銷。通過對比圖5可知，雖然MEC卸載決策任務執(zhí)行階段的總開銷性能優(yōu)于D2D卸載決策，但其任務執(zhí)行階段的優(yōu)勢也并不能彌補任務傳輸階段與D2D卸載決策之間產(chǎn)生的差距，所以出現(xiàn)了圖5（a）中的D2D卸載決策在總開銷、總時延開銷和總能耗開銷性能上均更優(yōu)的結果。這也驗證了D2D短距離通信的優(yōu)勢有利于減小用戶計算任務卸載時延和能耗，特別是當同時有較多用戶需要計算卸載服務時，可以在一定程度上減輕MEC擁堵，有效降低時延和能耗，提升用戶體驗。

4 結語

本文考慮D2D通信低時延、低能耗的優(yōu)勢，提出了一種基于D2D通信的多用戶計算卸載資源優(yōu)化決策算法。首先，通過任務傳輸和執(zhí)行階段建立的時延和能耗模型，將多個用戶的計算卸載和多個用戶的計算資源分配建模為最小化包括時延和能耗的計算總開銷的最優(yōu)化問題；然后，基于穩(wěn)定匹配理論采用低復雜度的決策算法求解D2D卸載的優(yōu)化分配。理論分析驗證了本文算法的穩(wěn)定性、最優(yōu)性和復雜度等特性。仿真結果表明，本文算法在不同情況下的計算總開銷都遠小于隨機匹配算法，有效降低了10%～33%，性能非常接近最優(yōu)的窮舉搜索算法，而且無論是總開銷還是總時延和總能耗開銷性能，均優(yōu)于MEC卸載決策，用戶間D2D卸載能夠實現(xiàn)低時延、低能耗的體驗。本文研究D2D卸載是基于提供計算資源的用戶會得到相應補償?shù)脑O定，其實在實際應用場景中，用戶在社會網(wǎng)絡中所表現(xiàn)出的某些特性，如社會關系、偏好特性等，應該是需要被考慮的重點之一。未來將探究社會網(wǎng)絡中用戶的相關特性對D2D卸載的影響，設計考慮更加全面、性能更優(yōu)的D2D卸載決策，提升用戶體驗。

[1] MAO Y Y， YOU C S， ZHANG J， et al. A survey on mobile edge computing： the communication perspective ［J］. IEEE Communications on Surveys and Tutorials， 2017， 19（4）： 2322-2358.

[2] HU Y C， PATEL M， SABELLA D， et al. Mobile edge computing： a key technology towards 5G： ETSI White Paper No. 11 ［R］. Sophia Antipolis： European Telecommunications Standards Institute， 2015： 1-15.

[3] YOU C S， HUANG K B， CHAE H， et al. Energy-efficient resource allocation for mobile-edge computation offloading ［J］. IEEE Transactions on Wireless Communications， 2017， 16（3）： 1397-1411.

[4] WANG C M， YU F R， LIANG C C， et al. Joint computation offloading and interference management in wireless cellular networks with mobile edge computing ［J］. IEEE Transactions on Vehicular Technology， 2017， 66（8）： 7432-7445.

[5] REN J K， YU G D， CAI Y L， et al. Latency optimization for resource allocation in mobile-edge computation offloading ［J］. IEEE Transactions on Wireless Communications， 2018， 17（8）： 5506-5519.

[6] KAI Y， WANG J Y， ZHU H L. Energy minimization for D2D-assisted mobile edge computing networks ［C］// Proceedings of the 2019 IEEE International Conference on Communications. Piscataway： IEEE， 2019： 1-6.

[7] MACH P， BECVAR Z， VANEK T. In-band device-to-device communication in OFDMA cellular networks： a survey and challenges ［J］. IEEE Communications Surveys and Tutorials， 2015， 17（4）： 1885-1922.

[8] HE Y H， REN J K， YU G D， et al. D2D communications meet mobile edge computing for enhanced computation capacity in cellular networks ［J］. IEEE Transactions on Wireless Communications， 2019， 18（3）： 1750-1763.

[9] HU G S， JIA Y J， CHEN Z C. Multi-user computation offloading with D2D for mobile edge computing ［C］// Proceedings of the 2018 IEEE Global Communications Conference. Piscataway： IEEE， 2018： 1-6.

[10] XING H， LIU L， XU J， et al. Joint task assignment and resource allocation for D2D-enabled mobile-edge computing ［J］. IEEE Transactions on Communications， 2019， 67（6）： 4193-4207.

[11] FENG J， ZHAO L Q， DU J B， et al. Computation offloading and resource allocation in D2D-enabled mobile edge computing ［C］// Proceedings of the 2018 IEEE International Conference on Communications. Piscataway：IEEE， 2018： 1-6.

[12] KO S W， HAN K F， HUANG K B. Wireless networks for mobile edge computing： spatial modeling and latency analysis ［J］. IEEE Transactions on Wireless Communications， 2018， 17（8）： 5225-5240.

[13] 張文柱，曹琲琲，余靜華.移動邊緣計算中一種多用戶計算卸載方法［J］.西安電子科技大學學報，2020，47（6）：131-138.（ZHANG W Z， CAO B B，YU J H. Multi-user computation offloading approach for mobile edge computing ［J］. Journal of Xidian University， 2020， 47（6）： 131-138.）

[14] CHEN X. Decentralized computation offloading game for mobile cloud computing ［J］. IEEE Transactions on Parallel and Distributed Systems， 2015， 26（4）： 974-983.

[15] WEN Y G， ZHANG W W， LUO H Y. Energy-optimal mobile application execution： taming resource-poor mobile devices with cloud clones ［C］// Proceedings of the 2012 IEEE International Conference on Computer Communications. Piscataway： IEEE， 2012：2716-2720.

[16] TANG J H， TAY W P， WEN Y G. Dynamic request redirection and elastic service scaling in cloud-centric media networks ［J］. IEEE Transactions on Multimedia， 2014， 16（5）： 1434-1445.

[17] XU C， GAO C X， ZHOU Z Y， et al. Social network-based content delivery in device-to-device underlay cellular networks using matching theory ［J］. IEEE Access， 2017， 5： 924-937.

[18] GALE D， SHAPLEY L S. College admissions and the stability of marriage ［J］. The American Mathematical Monthly， 1962， 69（1）： 9-15.

Multi-user computation offloading and resource optimization policy based on device-to-device communication

LI Yu1，2*， HE Xiping1，2， TANG Lianggui1，2

（1.School of Computer Science and Information Engineering，Chongqing Technology and Business University，Chongqing400067，China；2.Chongqing Engineering Laboratory for Detection，Control and Integrated System（Chongqing Technology and Business University），Chongqing400067，China）

With the significant increase of computation-intensive and latency-intensive applications， Mobile-Edge Computing （MEC） was proposed to provide computing services for users at the network edge. In view of the limited computing resources of edge servers at the Base Stations （BSs） and the long latency of long-distance computation offloading of users at the network edge， a multi-user computation offloading and resource optimization policy based on Device-to-Device （D2D） communication was proposed. The D2D was integrated into MEC network to directly offload tasks to neighbor users for executing in D2D mode， which was able to further reduce offloading latency and energy consumption. Firstly， the joint optimization problem of multi-user computation offloading and multi-user computing resource allocation was modelled with the optimization objective of minimizing the total system computing cost including latency and energy consumption. Then， the solution of this problem was considered as a D2D pairing process， and the multi-user computation offloading and resource optimization policy algorithm was proposed based on stable matching. Finally， the optimization allocation policy of D2D offloading was solved iteratively. The characteristics such as stability， optimality and complexity of the proposed algorithm were analyzed by theoretical proof. Simulation results show that， the proposed algorithm can effectively reduce the total system computing cost by 10%-30% compared with the random matching algorithm，and the performance of the proposed algorithm is very close to the optimal exhaustive search algorithm， indicating that the proposed policy based on D2D offloading is helpful to improve latency and energy consumption performance.

Mobile Edge Computing (MEC); Device-to-Device (D2D) communication; computation offloading; resource allocation; stable matching

TP389.1

A

1001-9081（2022）05-1538-09

10.11772/j.issn.1001-9081.2021030458

2021?03?25；

2021?06?30；

2021?07?01。

國家自然科學基金資助項目（61901067）；重慶市自然科學基金資助項目（cstc2020jcyj?msxmX0339）；重慶市教育委員會科學技術研究項目（KJQN201900824）；重慶工商大學科研項目（1952002，1956011）。

李余（1989—），女，重慶人，副教授，博士，主要研究方向：終端直通通信、移動邊緣計算、資源優(yōu)化； 何希平（1968—），男，四川射洪人，教授，博士，主要研究方向：機器學習、數(shù)據(jù)分析處理、計算機視覺； 唐亮貴（1973—），男，重慶人，副教授，博士，CCF會員，主要研究方向：分布式智能計算、網(wǎng)絡計算。

This work is partially supported by National Natural Science Foundation of China （61901067），Natural Science Foundation of Chongqing （cstc2020jcyj-msxmX0339）， Science and Technology Research Program of Chongqing Municipal Education Commission （KJQN201900824）， Science Research Program of Chongqing Technology and Business University （1952002， 1956011）.

LI Yu， born in 1989， Ph. D.， associate professor. Her research interests include device-to-device communication， mobile edge computing， resource optimization.

HE Xiping， born in 1968， Ph. D.， professor. His research interests include machine learning， data analysis and processing， computer vision.

TANG Lianggui， born in 1973， Ph. D.， associate professor. His research interests include distributed intelligent computing， network computing.