（河海大學(xué)計(jì)算機(jī)與信息學(xué)院，南京 211100）

0 引言

以虛擬現(xiàn)實(shí)、現(xiàn)實(shí)增強(qiáng)、網(wǎng)絡(luò)游戲、圖像識(shí)別等為代表的一批新應(yīng)用不斷涌現(xiàn)，其產(chǎn)生的移動(dòng)數(shù)據(jù)流量與日俱增，思科預(yù)計(jì)，從2016—2021 年，虛擬現(xiàn)實(shí)和現(xiàn)實(shí)增強(qiáng)產(chǎn)生的流量將增長為原來的20倍［1］。這些應(yīng)用的任務(wù)通常是計(jì)算密集型和時(shí)延敏感型的任務(wù)，計(jì)算量相對(duì)較大，同時(shí)對(duì)時(shí)延的要求較高。然而當(dāng)前移動(dòng)設(shè)備的計(jì)算能力非常有限，在移動(dòng)設(shè)備本地執(zhí)行這些任務(wù)根本無法滿足時(shí)延的要求；同時(shí)，移動(dòng)設(shè)備的電力存儲(chǔ)也非常有限，當(dāng)自身完成這些計(jì)算量較大的任務(wù)時(shí)，會(huì)帶來高額的能源消耗，不利于移動(dòng)設(shè)備的長久工作。因此，這些應(yīng)用任務(wù)給移動(dòng)設(shè)備帶來了極大的挑戰(zhàn)。

移動(dòng)云計(jì)算（Mobile Cloud Computing，MCC）［2］曾經(jīng)被認(rèn)為是一種很有前途的減輕計(jì)算任務(wù)負(fù)擔(dān)的方法，遠(yuǎn)程云擁有強(qiáng)大的計(jì)算能力和充足的計(jì)算資源，可以為用戶提供充足的資源，還可以節(jié)約任務(wù)在本地計(jì)算的能耗。然而，通常情況下移動(dòng)設(shè)備與遠(yuǎn)程云在空間上距離較遠(yuǎn)，將任務(wù)卸載到云服務(wù)器會(huì)導(dǎo)致高額的通信開銷。對(duì)于時(shí)延敏感性的任務(wù)，會(huì)給用戶造成糟糕的體驗(yàn)，無法滿足用戶需求。

為了彌補(bǔ)MCC 在時(shí)延問題上的不足，提出了移動(dòng)邊緣計(jì)算（Mobile Edge Computing，MEC）［3］。移動(dòng)邊緣計(jì)算的核心思想是將服務(wù)器的計(jì)算和存儲(chǔ)等資源下沉到網(wǎng)絡(luò)邊緣以及用戶附近，通過邊緣服務(wù)器為用戶提供計(jì)算、存儲(chǔ)等服務(wù)，解決移動(dòng)云計(jì)算中高額通信時(shí)延的問題。移動(dòng)邊緣計(jì)算通過計(jì)算卸載技術(shù)將任務(wù)卸載到MEC 服務(wù)器上，解決由移動(dòng)設(shè)備計(jì)算能力不足帶來的一些問題。

如圖1 所示，當(dāng)有用戶設(shè)備（User Equipment，UE）請(qǐng)求任務(wù)卸載時(shí)，通過無線網(wǎng)絡(luò)直接將相關(guān)數(shù)據(jù)發(fā)送到部署在基站附近的MEC 服務(wù)器。MEC 服務(wù)器根據(jù)當(dāng)前資源情況與用戶任務(wù)需求，決定將用戶任務(wù)卸載到MEC 服務(wù)器上來計(jì)算完成。用戶任務(wù)不再需要經(jīng)核心網(wǎng)絡(luò)發(fā)送給遠(yuǎn)程云，極大了減少了傳輸時(shí)延。但是，MEC 服務(wù)器的資源相較于遠(yuǎn)程云來說是極為有限的，很難在所有時(shí)間段為用戶提供滿意的服務(wù)，因此如何有效地分配MEC 服務(wù)器中的計(jì)算資源，提出滿足用戶需求的任務(wù)卸載決策，成為了一個(gè)新的挑戰(zhàn)。

圖1 用戶任務(wù)卸載示例Fig.1 Example of user task unloading

本文考慮以最小化時(shí)延為單一目標(biāo)的卸載策略難以滿足用戶需求，針對(duì)獨(dú)立任務(wù)場景下多用戶任務(wù)卸載問題，使用博弈論中穩(wěn)定匹配的理論，把任務(wù)卸載過程比作是相互匹配的一個(gè)過程。針對(duì)以最小化時(shí)延為單一目標(biāo)的卸載策略難以滿足用戶需求的問題，在綜合考慮時(shí)延與能耗基礎(chǔ)上通過對(duì)問題進(jìn)行建模分析，提出了基于穩(wěn)定匹配的多用戶任務(wù)卸載策略（Multi-User Task Offloading strategy based on Stable Allocations，MUTOSA），在保證用戶時(shí)延的要求下達(dá)到能耗最小化，保證更多用戶的需求。

1 相關(guān)工作

MEC 是一種將服務(wù)下沉到網(wǎng)絡(luò)邊緣的一種計(jì)算模型［4-5］。通過任務(wù)卸載技術(shù)將任務(wù)卸載到合適的服務(wù)器上計(jì)算，解決移動(dòng)設(shè)備因其計(jì)算能力有限帶來的高能耗、高時(shí)延等問題。

任務(wù)卸載過程中不同的場景會(huì)有不同的卸載策略。

1）按照用戶設(shè)備數(shù)量劃分，卸載策略可以分為單用戶卸載和多用戶卸載。Mao 等［6］研究在單用戶設(shè)備場景下卸載決策問題。以執(zhí)行時(shí)延和任務(wù)失敗的執(zhí)行成本為性能指標(biāo)，提出了一種基于低復(fù)雜度在線Lyapunov 優(yōu)化的動(dòng)態(tài)計(jì)算卸載算法。Li等［7］致力用無人機(jī)作為移動(dòng)邊緣節(jié)點(diǎn)為多個(gè)用戶提供計(jì)算任務(wù)卸載服務(wù)。該策略的目標(biāo)是在無人機(jī)上以有限的能量最大化用戶任務(wù)的遷移吞吐量。Zhang 等［8］針對(duì)5G 異構(gòu)網(wǎng)絡(luò)中的多個(gè)移動(dòng)設(shè)備，提出了一個(gè)在滿足時(shí)延約束的同時(shí)系統(tǒng)能耗最小化的節(jié)能優(yōu)化問題，設(shè)計(jì)了一個(gè)三階段的計(jì)算卸載方案。在實(shí)際應(yīng)用場景中，基本都是多用戶的情況，因此在本文中，考慮的是多個(gè)用戶的任務(wù)卸載問題。

2）按照卸載目標(biāo)劃分，任務(wù)卸載可以分為面向時(shí)延的任務(wù)卸載、面向能耗的任務(wù)卸載、權(quán)衡時(shí)延和能耗的任務(wù)卸載。Guo 等［9］提出了一種混合整數(shù)規(guī)劃的卸載策略，研究如何將移動(dòng)應(yīng)用的計(jì)算密集型任務(wù)從資源稀缺的移動(dòng)設(shè)備動(dòng)態(tài)地轉(zhuǎn)移到位于邊緣網(wǎng)絡(luò)的服務(wù)器上，以最小化平均任務(wù)完成時(shí)延為目標(biāo)。Alameddine 等［10］關(guān)注對(duì)延遲敏感的計(jì)算任務(wù)卸載，提出了一種基于邏輯的曲向分解方法。Huang 等［11］研究的是多個(gè)無線設(shè)備選擇將計(jì)算任務(wù)卸載到邊緣服務(wù)器的場景。綜合考慮能耗和響應(yīng)時(shí)延，提出了一種適用于MEC 網(wǎng)絡(luò)分布式的基于深度學(xué)習(xí)的卸載算法。Zhang 等［12］考慮邊緣人工智能場景中能耗和時(shí)延的加權(quán)優(yōu)化問題，提出了一種退潮算法來求解該模型。在實(shí)際場景中，時(shí)延直接影響的用戶體驗(yàn)，終端能耗決定了用戶設(shè)備的工作時(shí)長。現(xiàn)有卸載策略多以最小化時(shí)延為單一目標(biāo)，難以滿足用戶需求的問題。

本文綜合考慮時(shí)延和能耗，對(duì)多用戶場景下的獨(dú)立任務(wù)卸載問題進(jìn)行建模，提出了基于穩(wěn)定匹配的多用戶任務(wù)卸載策略，卸載目標(biāo)是在滿足用戶時(shí)延情況下最小化能耗，不僅給用戶帶來良好的體驗(yàn)，還可以保證用戶設(shè)備的長久工作。

2 系統(tǒng)模型

2.1 網(wǎng)絡(luò)模型

圖2 展示了網(wǎng)絡(luò)模型。用戶設(shè)備將卸載請(qǐng)求發(fā)送到基站，基站將任務(wù)卸載到MEC 服務(wù)器或遠(yuǎn)程云服務(wù)器。終端UE 通過無線網(wǎng)絡(luò)直接連接的邊緣服務(wù)器計(jì)算節(jié)點(diǎn)稱為服務(wù)節(jié)點(diǎn)，本文假設(shè)服務(wù)節(jié)點(diǎn)為一個(gè)。每個(gè)UE有一個(gè)或者多個(gè)獨(dú)立任務(wù)，該任務(wù)不可分割。任意兩個(gè)MEC 服務(wù)器可以進(jìn)行通信，來相互幫助完成超額的任務(wù)。若所有MEC 服務(wù)器仍不能滿足用戶任務(wù)需求，MEC 服務(wù)器可以將任務(wù)提交到遠(yuǎn)程云計(jì)算。

圖2 多任務(wù)卸載場景Fig.2 Multi-task unloading scenario

假設(shè)在一個(gè)時(shí)隙內(nèi)有N個(gè)用戶任務(wù)請(qǐng)求。所有UE 在通信過程中，不存在用戶間的干擾?？値払被分成H個(gè)信道。用戶通過正交頻分多址將請(qǐng)求和數(shù)據(jù)上傳到基站，其中同一信道中的每個(gè)用戶與其他用戶正交，并且每個(gè)信道只能分配給一個(gè)用戶。每個(gè)用戶任務(wù)Ui由三元組{datai，cyclesi，delayi}表示，其中datai表示任務(wù)i的輸入數(shù)據(jù)規(guī)模，cyclesi表示完成計(jì)算任務(wù)所需的CPU 周期數(shù)，delayi表示完成任務(wù)i的最大容忍時(shí)延。

2.2 時(shí)延和能耗模型

2.2.1 時(shí)延模型

完成任務(wù)i的響應(yīng)時(shí)延ti由兩部分組成，分別為計(jì)算時(shí)延和通信時(shí)延。即：

1）計(jì)算時(shí)延。假設(shè)有M個(gè)MEC 服務(wù)器，設(shè)任務(wù)i所在的UE 本地計(jì)算能力為LCi(1 ≤i≤N)，MEC 服務(wù)器k的計(jì)算能力為ECk(1 ≤k≤M)，遠(yuǎn)程云的計(jì)算能力為RC。由此可以得到任務(wù)在每個(gè)計(jì)算節(jié)點(diǎn)的計(jì)算時(shí)延。

當(dāng)任務(wù)i在本地計(jì)算，計(jì)算時(shí)延為：

當(dāng)任務(wù)卸載到第MEC服務(wù)器k中，計(jì)算時(shí)延為：

每個(gè)用戶任務(wù)Ui為一個(gè)三元組，且是不可分割的一個(gè)原子任務(wù)，因此用戶任務(wù)只能由本地設(shè)備、MEC 服務(wù)器和遠(yuǎn)程云三者中其中一個(gè)節(jié)點(diǎn)來完成計(jì)算。αi、βi、γi表示每個(gè)任務(wù)都有可能在本地、MEC 服務(wù)器或者遠(yuǎn)程云服務(wù)器上計(jì)算。αi+βi+γi=1，αi，βi，γi∈{0，1}保證每個(gè)任務(wù)只能由三者中的一個(gè)來處理。

2）通信時(shí)延?；就ǔＮ挥诒镜貐^(qū)域的MEC 服務(wù)器附近，因此忽略基站到MEC 服務(wù)器的通信時(shí)延。此外，由于計(jì)算結(jié)果的輸出數(shù)據(jù)規(guī)模遠(yuǎn)小于從UE 發(fā)送到遠(yuǎn)程服務(wù)器的輸入數(shù)據(jù)規(guī)模，所以忽略反向鏈路的通信開銷。

本文主要關(guān)注從UE到基站、基站到基站和基站到遠(yuǎn)程云的上行鏈路通信開銷。用戶任務(wù)i到MEC 服務(wù)器k的傳輸速率ri，k可以用式（6）［13］表示：

其中：ω表示帶寬，因?yàn)榭値払被分成H個(gè)信道，所以ω=表示用戶任務(wù)i的UE 傳輸功率。采用陰影衰落系數(shù)為σc和噪聲功率為N0的瑞利信道模型。信道模型中的參數(shù)Γ表示保證最小誤碼率的信噪比。假設(shè)信道系數(shù)hi是完美估計(jì)，并且在整個(gè)傳輸周期中信道衰落是恒定的。λ是路徑損耗指數(shù)。d表示用戶任務(wù)i與服務(wù)節(jié)點(diǎn)k的距離。

當(dāng)需要卸載到非服務(wù)節(jié)點(diǎn)的MEC 服務(wù)器時(shí)，需要服務(wù)節(jié)點(diǎn)做轉(zhuǎn)發(fā)工作。多個(gè)MEC 服務(wù)器的拓?fù)浣Y(jié)構(gòu)為全連接［14］，即兩兩相連，如圖3 所示。每個(gè)邊緣服務(wù)器節(jié)點(diǎn)可以直接和其他所有的節(jié)點(diǎn)進(jìn)行通信。兩者的通信速率可以表示為：

其中：j，k表示不相同的兩個(gè)MEC 服務(wù)器；為MEC 服務(wù)器k的傳輸功率；dk，j表示服務(wù)節(jié)點(diǎn)k與其他MEC 服務(wù)器j的距離；hk為信道系數(shù)，假設(shè)其為完美估計(jì)，并且在整個(gè)傳輸周期中信道衰落是恒定的。

圖3 服務(wù)器的拓?fù)浣Y(jié)構(gòu)Fig.3 Topology of servers

如果卸載決策將任務(wù)卸載到遠(yuǎn)程云中時(shí)，服務(wù)節(jié)點(diǎn)也需要做轉(zhuǎn)發(fā)工作，假設(shè)πk為MEC 服務(wù)器k將計(jì)算數(shù)據(jù)發(fā)送到遠(yuǎn)程云的傳輸速率。綜合式（6）和式（7）可以得到通信時(shí)延為：

其中：βE表示任務(wù)是卸載到服務(wù)節(jié)點(diǎn)還是其他MEC 服務(wù)器，當(dāng)卸載在服務(wù)節(jié)點(diǎn)時(shí)為1，卸載到其他MEC服務(wù)器時(shí)為0。若在本地執(zhí)行，通信時(shí)延為0。

2.2.2 能耗模型

在本文中，能耗僅考慮UE端。因?yàn)閁E能量有限，為保持長久工作，提高用戶體驗(yàn)，能耗是不可忽略的重要因素。UE端能耗主要有兩個(gè)方面：計(jì)算能耗與通信能耗。當(dāng)用戶任務(wù)在本地計(jì)算時(shí)，只存在計(jì)算能耗；當(dāng)用戶任務(wù)卸載服務(wù)器上計(jì)算時(shí)，則只有通信能耗。因此能耗ei可以表示為：

當(dāng)任務(wù)不在本地計(jì)算時(shí)，傳輸能耗僅僅由用戶i到MEC服務(wù)器k的傳輸時(shí)間決定，與其他的因素?zé)o關(guān)。

2.3 目標(biāo)函數(shù)

本文的目標(biāo)函數(shù)是滿足用戶延時(shí)的前提下，使得用戶終端能耗最小，最大化所有用戶的滿意度（Degree of Satisfaction，DoS）。單個(gè)用戶滿意度定義為：

其中：DoSi表示用戶滿意度，任務(wù)響應(yīng)時(shí)延小于等于最大容忍時(shí)延為1，否則為0。對(duì)于滿足時(shí)延的用戶，最小化用戶終端能耗。對(duì)于無法滿足時(shí)延的用戶，優(yōu)先選擇時(shí)延最小的節(jié)點(diǎn)來計(jì)算任務(wù)，不考慮能耗問題。綜上，最大化所有用戶滿意度的目標(biāo)函數(shù)可以表示為：

3 基于穩(wěn)定匹配的多任務(wù)卸載策略

3.1 穩(wěn)定匹配

本文運(yùn)用博弈論中雙邊匹配的知識(shí)來解決上述問題。所謂雙邊匹配就是一個(gè)集合中的元素與另一個(gè)集合中的元素進(jìn)行一對(duì)一、多對(duì)一或者多對(duì)多的匹配。把所有用戶任務(wù)看作是一個(gè)集合，所有計(jì)算節(jié)點(diǎn)看作是另一個(gè)集合。任務(wù)卸載過程可以看作是一個(gè)或者多個(gè)用戶任務(wù)匹配一個(gè)計(jì)算節(jié)點(diǎn)的雙邊匹配。穩(wěn)定匹配是雙邊匹配中達(dá)到納什均衡的一種狀態(tài)以及博弈理論［15］。當(dāng)雙方達(dá)到穩(wěn)定匹配的狀態(tài)時(shí)，總體的收益最高。

定義1偏序關(guān)系。令X是一個(gè)集合，X上的偏好關(guān)系是一個(gè)雙向關(guān)系，滿足：

1）對(duì)每個(gè)x≠y，有x?y或者y?x，關(guān)系是完備的。

2）x?x不成立，關(guān)系是非自反的，即x不會(huì)優(yōu)于自身。

3）如果x?y且y?z，那么x?z，關(guān)系是傳遞的。

定義2匹配問題。一個(gè)匹配問題可描述為：存在兩個(gè)集合，任務(wù)集合T和服務(wù)器集合M。自然數(shù)n表示兩個(gè)集合中元素的數(shù)量（假設(shè)任務(wù)和服務(wù)器的數(shù)量一樣多）。

每個(gè)服務(wù)器在任務(wù)的集合上有一個(gè)偏好關(guān)系。一個(gè)任務(wù)t認(rèn)為服務(wù)器m1優(yōu)于服務(wù)器m2，這個(gè)關(guān)系表示為：

定義3雙邊匹配。就是以雙邊匹配為研究對(duì)象，研究具有穩(wěn)定偏好的不相交的雙方的匹配過程。本文中的匹配是一個(gè)從任務(wù)集到服務(wù)器集的雙射。

等價(jià)的匹配n個(gè)配對(duì){(t1，m1)，(t2，m2)，…，(tn，mn)}，使得{m1，m2，…，mn}=M和{t1，t2，…，tn}=T成立。對(duì)于一個(gè)配對(duì)(t1，m1)被包含在了一個(gè)匹配中，就說任務(wù)t1匹配給了服務(wù)器m1。后面用大寫字母A、B或C等表示一個(gè)匹配。

定義4匹配反對(duì)。一個(gè)服務(wù)器和一個(gè)任務(wù)反對(duì)一個(gè)匹配，條件是：它們認(rèn)為對(duì)方存在一個(gè)個(gè)體優(yōu)于自己在當(dāng)前匹配下被匹配給的個(gè)體。一個(gè)匹配是穩(wěn)定的條件是：不存在這樣的反對(duì)。

定義5穩(wěn)定匹配。匹配A是穩(wěn)定的條件是，當(dāng)一個(gè)服務(wù)器認(rèn)為另一個(gè)任務(wù)優(yōu)于在A匹配下的他的伴侶，而這個(gè)任務(wù)認(rèn)為在A匹配下，自己所匹配的服務(wù)器優(yōu)于其他服務(wù)器。

定理1穩(wěn)定匹配永遠(yuǎn)存在［16］。

證明 當(dāng)沒有任務(wù)被服務(wù)器拒絕時(shí)，算法終止。假設(shè)本地和遠(yuǎn)程云中心沒有資源限制，因此最終所有任務(wù)都會(huì)被匹配到。假設(shè)此時(shí)得到的匹配是不穩(wěn)定，那么至少存在一個(gè)任務(wù)和一個(gè)服務(wù)器，稱為T0和M0，它們認(rèn)為對(duì)方優(yōu)于在算法下配給自己的伴侶。假設(shè)算法把T0匹配給了M1，把M0匹配給了T1，因?yàn)門0認(rèn)為M0優(yōu)于M1，那么T0在向M1匹配前，一定向M0匹配過，M0匹配T1，M0認(rèn)為T1優(yōu)于T0。這就跟T0和M0反對(duì)這個(gè)匹配的假定矛盾，所以此時(shí)的匹配是穩(wěn)定匹配。因此穩(wěn)定匹配永遠(yuǎn)存在。

定義6形式化的穩(wěn)定匹配。如果按照偏好賦予一定的權(quán)值，那么一個(gè)穩(wěn)定的匹配一定是權(quán)值最大的匹配（默認(rèn)權(quán)值按照偏好依次從大到小賦值）。

定理2對(duì)于穩(wěn)定匹配，存在兩個(gè)集合M和T，如果由M方發(fā)起匹配，則最后形成的匹配，對(duì)于集合M中所有元素來說是利益最大的匹配結(jié)果；反之，對(duì)于T集合亦然。

證明 設(shè)一個(gè)穩(wěn)定的匹配C是由M和T兩個(gè)集合中M發(fā)起匹配形成的，因?yàn)槊恳淮蜯中的元素都是選擇偏好最優(yōu)的，如果被拒絕，再選擇偏好順序中的下一個(gè)，所以最后形成的匹配，對(duì)于M中的每一個(gè)元素來說，一定是當(dāng)前可選擇情況下最好的選擇，那么相對(duì)應(yīng)的M集合所有元素得到的總權(quán)值一定是所有穩(wěn)定匹配中最大的。

3.2 列表生成

在進(jìn)行雙邊匹配時(shí)，雙邊的各個(gè)元素都會(huì)有對(duì)邊所有元素的一個(gè)偏好排序，首先要制定這個(gè)排序規(guī)則。本文最終目標(biāo)是在用戶時(shí)延允許內(nèi)的能耗最小，因此分為兩種情況：滿足時(shí)延要求和不滿足時(shí)延要求。

1）滿足時(shí)延要求。如果三者中存在可以滿足用戶要求的計(jì)算節(jié)點(diǎn)，那么可能會(huì)出現(xiàn)多種情況。這里假設(shè)用戶為0，邊緣節(jié)點(diǎn)為1，遠(yuǎn)程云為2，滿足時(shí)延的情況會(huì)有23-1種，這里去掉了空集的情況（即不滿足的情況）。最終的7 種情況如表1所示。

表1 滿足時(shí)延情況下的能耗對(duì)比Tab.1 Comparison of energy consumption in case of satisfying delay

2）不滿足時(shí)延要求。如果出現(xiàn)了三者都不能滿足要求的情況，那么選擇三方中時(shí)延最低的，按照延時(shí)升序排序。這種情況不考慮能耗。

3.3 多用戶任務(wù)卸載算法

在本文中假設(shè)遠(yuǎn)程云的最大計(jì)算資源限制是無限大的。計(jì)算節(jié)點(diǎn)對(duì)任務(wù)的偏序規(guī)則是按照任務(wù)的時(shí)延要求升序排序，時(shí)延要求越小，則優(yōu)先級(jí)越高。假設(shè)邊緣節(jié)點(diǎn)會(huì)有最大計(jì)算資源限制，允許幾個(gè)任務(wù)在當(dāng)前節(jié)點(diǎn)同時(shí)運(yùn)算但會(huì)限制任務(wù)計(jì)算量，遠(yuǎn)程云的這個(gè)最大計(jì)算資源限制設(shè)為∞。多用戶任務(wù)卸載算法是迭代進(jìn)行的。

本文提出的基于聯(lián)盟博弈的服務(wù)器聯(lián)盟形成策略如算法1所示。

算法1 基于穩(wěn)定匹配的多用戶任務(wù)卸載策略（MUTOSA）。

輸入：Ui，LCi，ECk，RC，D，ω，σc，N0，λ，Γ，PTi，PTk；

輸出：用戶滿意度。

算法主要步驟如下所示：

1）任務(wù)選擇自己偏好中優(yōu)先級(jí)最高的計(jì)算節(jié)點(diǎn)（14）～16）行代碼）。

2）每個(gè)計(jì)算節(jié)點(diǎn)從選擇它的任務(wù)中，按照每個(gè)自身對(duì)任務(wù)的偏好選擇最大計(jì)算資源限制允許范圍內(nèi)的多個(gè)任務(wù)留在該節(jié)點(diǎn)，拒絕余下的超過最大計(jì)算資源限制的任務(wù)（17）～20）行代碼），然后通過3）、4）不斷地迭代。

3）在前面階段被計(jì)算節(jié)點(diǎn)拒絕的每個(gè)任務(wù)，從沒有拒絕它的計(jì)算節(jié)點(diǎn)中選擇偏好最優(yōu)的一個(gè)節(jié)點(diǎn)（22）～25）行代碼）。

4）每個(gè)計(jì)算節(jié)點(diǎn)從選擇它的任務(wù)中，按照偏好關(guān)系，選擇最大計(jì)算資源限制允許范圍內(nèi)的多個(gè)任務(wù)留下，拒絕余下的超過最大計(jì)算資源限制的任務(wù)（26）～29）行代碼）。

5）沒有任務(wù)被節(jié)點(diǎn)拒絕時(shí)，算法終止。

在算法終止時(shí)，所達(dá)到的就是一個(gè)穩(wěn)定的匹配，一個(gè)穩(wěn)定的匹配就是雙邊中的元素對(duì)這個(gè)匹配都沒有異議，可以在用戶允許時(shí)延要求下實(shí)現(xiàn)能耗最小，達(dá)到最大的用戶滿意度。

4 實(shí)驗(yàn)驗(yàn)證與結(jié)果分析

4.1 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)集

通過計(jì)算機(jī)仿真實(shí)驗(yàn)評(píng)估基于穩(wěn)定匹配的多用戶任務(wù)卸載策略的有效性，實(shí)驗(yàn)平臺(tái)為IDEA。實(shí)驗(yàn)仿真參數(shù)［13，17-20］如表2所示。

評(píng)估的指標(biāo)分別為用戶滿意度、策略執(zhí)行時(shí)間和用戶總能耗3 個(gè)主要方面。用戶滿意度表示的是能夠在容忍時(shí)延內(nèi)完成的任務(wù)數(shù)量與總?cè)蝿?wù)數(shù)量的比值；策略執(zhí)行時(shí)間是每種卸載策略對(duì)各種信息綜合處理，得出卸載決策計(jì)算所用的時(shí)間；用戶總能耗表示的是執(zhí)行卸載決策所有用戶所消耗的能量總和。

為了評(píng)估基于博弈論穩(wěn)定匹配任務(wù)卸載策略的有效性，實(shí)驗(yàn)比較了以下卸載策略的用戶滿意度。

1）本地運(yùn)行策略（Local Computing，LC）：所有任務(wù)都在移動(dòng)設(shè)備運(yùn)行。

2）遠(yuǎn)程云卸載策略（Remote Cloud，RC）：任務(wù)全部卸載到遠(yuǎn)程云中心運(yùn)行。

3）基于Lyapunov 優(yōu)化的在線算法（Online Algorithm based on Lyapunov Optimization，OALO）。

4）基于遺傳算法的啟發(fā)式卸載策略（Heuristic Offloading Strategy Based on Genetic Algorithm，HOSBGA）：運(yùn)用啟發(fā)式算法（本文采用遺傳算法）來求得較優(yōu)解。HOSBGA 實(shí)驗(yàn)參數(shù)：種群規(guī)模60，交叉概率0.5，變異概率0.1。

5）基于穩(wěn)定匹配的多用戶任務(wù)卸載策略（MUTOSA）：通過結(jié)合博弈論中的穩(wěn)定匹配來對(duì)任務(wù)進(jìn)行卸載判斷，選擇合適的計(jì)算節(jié)點(diǎn)。

表2 主要參數(shù)設(shè)置Tab.2 Main parameter setting

4.2 結(jié)果分析

4.2.1 用戶滿意度

用戶滿意度是本文中最重要的評(píng)估指標(biāo)，是能夠在容忍時(shí)延內(nèi)完成的任務(wù)數(shù)量與總?cè)蝿?wù)數(shù)量的比值。圖4 顯示了在五種策略下任務(wù)數(shù)量對(duì)用戶滿意度的影響情況。由圖4 可以看出，在不進(jìn)行任務(wù)卸載時(shí)，即在本地運(yùn)行，LC 策略的用戶滿意度一直維持在45%左右，此時(shí)影響用戶滿意度的主要因素為UE 本地設(shè)備的計(jì)算能力。而相較于LC 策略，RC 策略是把所有的任務(wù)全都卸載到遠(yuǎn)程云，通信時(shí)延比較大。相較于LC和RC 策略，OALA、HOSBGA 和MUTOSA 都有著比較高的用戶滿意度。隨著用戶任務(wù)數(shù)量的增多，OALA、HOSBGA 和MUTOSA 的滿意度都呈現(xiàn)下降趨勢；但是MUTOSA 的下降趨勢比較緩慢，當(dāng)任務(wù)數(shù)量達(dá)到140 的時(shí)候，仍能保持用戶滿意度90%以上。具體而言，相較于OALA 和HOSBGA，當(dāng)用戶任務(wù)數(shù)量增多時(shí)，MUTOSA 分別可以最高提高15個(gè)百分點(diǎn)和10個(gè)百分點(diǎn)的用戶滿意度。

圖4 任務(wù)數(shù)量對(duì)用戶滿意度的影響Fig.4 Effect of task number on user satisfaction

圖5顯示了MEC服務(wù)器最大資源限制在五種策略下對(duì)用戶滿意度的影響。由圖5 可以看出，LC 與RC 兩種策略與MEC 最大資源限制是不相關(guān)的。OALA、HOSBGA 和MUTOSA 三種策略滿意度都會(huì)隨著MEC 服務(wù)資源增加而提高。

圖5 MEC容量對(duì)用戶滿意度的影響Fig.5 Effect of MEC capacity on user satisfaction

同時(shí)，當(dāng)最大資源限制在12 之前時(shí)，滿意度的提升明顯；當(dāng)超過12 時(shí)，滿意度的提升減緩。三者相比較，MUTOSA 的上升趨勢較小，這是由于MUTOSA 策略達(dá)到當(dāng)前場景下最大的用戶滿意度，未能滿足的用戶任務(wù)數(shù)量相較于總數(shù)較小，因此提升幅度較小。相較于OALA 和HOSBGA 策略，MUTOSA策略分別提高了約8%和10%的用戶滿意度。

4.2.2 策略執(zhí)行時(shí)間

圖6 顯示了任務(wù)數(shù)量對(duì)于策略執(zhí)行時(shí)間的影響。策略執(zhí)行時(shí)間指的是從獲得任務(wù)、服務(wù)器信息開始，計(jì)算出任務(wù)卸載結(jié)果的時(shí)間。由圖6 可以看出，因?yàn)長C 卸載策略和RC 卸載策略自身策略性質(zhì)，所以它們的執(zhí)行時(shí)間都是0，不予考慮。OALA 策略、HOSBGA 策略和MUTOSA 策略隨著任務(wù)數(shù)量的增多，兩者的執(zhí)行時(shí)間也隨之變長。相較于HOSBGA，當(dāng)任務(wù)數(shù)量較少時(shí)，MUTOSA 可以節(jié)省約60 ms 的執(zhí)行時(shí)間，隨著任務(wù)數(shù)量的增多，可以達(dá)到節(jié)省約100 ms 的效果。這是因?yàn)镠OSBGA 算法需要從全局去搜索較優(yōu)解，收斂速度較慢。MUTOSA 中任務(wù)總是選擇當(dāng)前條件下在最優(yōu)選擇，被拒絕后選擇次優(yōu)選擇，時(shí)間復(fù)雜度是線性相關(guān)的。相較于OALA 策略，MUTOSA 可以節(jié)省約30 ms 的執(zhí)行時(shí)間。在執(zhí)行時(shí)間上，MUTOSA 優(yōu)勢明顯，因此對(duì)于時(shí)延敏感應(yīng)用可以有效提高用戶體驗(yàn)。

圖6 任務(wù)數(shù)量對(duì)卸載策略執(zhí)行時(shí)間影響Fig.6 Effect of task number on execution time of offloading strategy

4.2.3 能耗消耗

基于穩(wěn)定匹配的多用戶任務(wù)卸載策略可以分為兩種：一種為考慮能耗的計(jì)算卸載策略MUTOSA-C（Multi-User Task Offloading based on Stable Allocations-Considering energy consumption）；一種為不考慮能耗的計(jì)算卸載策略MUTOSA-N（Multi-User Task Offloading based on Stable Allocations-Not considering energy consumption）。在能耗方面，指標(biāo)為所有用戶的總能耗。

圖7顯示了傳輸數(shù)據(jù)規(guī)模對(duì)總能耗的影響。由圖7（a）可以看出，LC、OALA、HOSBGA、MUTOSA-N 以及MUTOSA-C 都隨著傳輸數(shù)據(jù)的增大總能耗也隨著增大。LC 策略任務(wù)只在本地運(yùn)算，傳輸數(shù)據(jù)量的大小與其能耗無關(guān)。RC策略總能耗雖然一直處于最小的情況，但是RC策略所能達(dá)到的用戶滿意度比較低。因此在圖7（b）去除LC與RC策略。

圖7 傳輸數(shù)據(jù)規(guī)模與總能耗關(guān)系Fig.7 Relationship between transmission data scale and total energy consumption

從圖7（b）中可以看出，策略HOSBGA 與MUTOSA-N 策略在能耗方面比較接近，OALA 比HOSBGA 和MUTOSA-N 要低一些，但是OALA 和HOSBGA 所能達(dá)到的用戶滿意度低于MUTOSA-N 策略。相較于前三種策略，MUTOSA-C 方法的能耗是最低的。在用戶滿意度方面，與MUTOSA-N 策略相同。相較于MUTOSA-N、OALA 和HOSBGA，MUTOSA-C 方法可以節(jié)省大約50%的能耗，最大限度地減少用戶端設(shè)備的能源消耗。

圖8 顯示了任務(wù)數(shù)量對(duì)總能耗的影響。由于從圖7 可以看出LC策略總能耗明顯比其他幾種策略能耗要高出很多，因此忽略LC 策略。此外，五種策略都隨著用戶任務(wù)數(shù)量增多，總能耗升高。五種策略中，RC 策略是能耗最小的，這是由于假設(shè)任務(wù)類型為計(jì)算密集型任務(wù)。但是由于RC 策略的低用戶滿意度，因此僅作為參考數(shù)據(jù)。OALA、HOSBGA 和MUTOSA-N 三種策略，在用戶任務(wù)數(shù)量達(dá)到60 之前，兩者的總能耗比較接近；當(dāng)用戶任務(wù)數(shù)量超過60 時(shí)，MUTOSA-N 總能耗超過HOSBGA 策略的總能耗，OALA 總能耗低于HOSBGA 和MUTOSA-N 策略。相較于前三者，MUTOSA-C 策略的總能耗一直處于最低的水平，而且增長趨勢比較緩慢。這表明MUTOSA-C 策略為用戶節(jié)省了大量的能耗，給用戶設(shè)備長久工作提供了有利條件。

圖8 任務(wù)數(shù)量與總能耗關(guān)系Fig.8 Relationship between task number and total energy consumption

圖9 顯示了任務(wù)數(shù)量對(duì)卸載比例的影響。L、E 和R 分別表示的是本地（Local，L）、邊緣MEC 服務(wù)器（Egde，E）和遠(yuǎn)程云（Remote，R）?？梢钥闯觯珽 所占比例總是最多的，這表明大多數(shù)的任務(wù)被卸載到了MEC服務(wù)器上。

圖9 卸載比例與任務(wù)數(shù)量關(guān)系Fig.9 Relationship between offloading proportion and task number

HOSBGA 與MUTOSA-N 兩者策略，E 所占比例比較接近，這說明兩者在利用MEC 服務(wù)器方面所達(dá)到的利用率相接近。MUTOSA-C 策略相較于前兩者，E 所占比例明顯要多了大約10%的比例，這表明MUTOSA-C 策略更能充分地利用MEC 服務(wù)器的能力。綜合來說，MUTOSA-C 策略能更大限度地利用MEC 服務(wù)器資源，并能根據(jù)任務(wù)性質(zhì)選擇最有利于用戶的卸載節(jié)點(diǎn)。

上述實(shí)驗(yàn)結(jié)果表明，本文提出的基于穩(wěn)定匹配的多用戶任務(wù)卸載策略能夠?qū)崿F(xiàn)高達(dá)約95%的用戶滿意度，滿足絕大多數(shù)的用戶時(shí)延要求，并能有效地減少終端能耗，解決多用戶任務(wù)卸載問題。

5 結(jié)語

本文針對(duì)單個(gè)MEC 服務(wù)器計(jì)算能力有限的問題，不僅聯(lián)合多個(gè)邊緣MEC 服務(wù)器，還聯(lián)合本地用戶設(shè)備與遠(yuǎn)程云，通過對(duì)三方面任務(wù)執(zhí)行過程進(jìn)行建模，提出了基于穩(wěn)定匹配的多用戶任務(wù)卸載策略，解決多用戶的計(jì)算任務(wù)卸載問題。仿真實(shí)驗(yàn)表明，與本地卸載策略、遠(yuǎn)程云卸載策略和啟發(fā)式卸載策略相比，基于穩(wěn)定匹配的多用戶任務(wù)卸載策略能夠?qū)崿F(xiàn)平均約93%的用戶需求，實(shí)現(xiàn)較高的用戶滿意度，而且執(zhí)行時(shí)間比啟發(fā)式算法大幅度減少，對(duì)于時(shí)延敏感型應(yīng)用任務(wù)可以有效地提高用戶體驗(yàn)。后續(xù)的研究將從以下方面展開。首先，在計(jì)算任務(wù)卸載決策和資源分配問題中，多個(gè)用戶進(jìn)行任務(wù)卸載時(shí)，對(duì)通信和計(jì)算資源都會(huì)產(chǎn)生競爭問題，這將是未來值得研究的工作之一。其次，用戶的移動(dòng)性是移動(dòng)邊緣計(jì)算的重要特點(diǎn)，這往往會(huì)導(dǎo)致用戶和邊緣服務(wù)器的網(wǎng)絡(luò)連接不穩(wěn)定，造成任務(wù)卸載失敗。在實(shí)際場景中，通過挖掘用戶的移動(dòng)規(guī)律制定高效的卸載決策對(duì)提高任務(wù)的執(zhí)行成功率具有重要意義。