MEC系統(tǒng)中基于無線供能的多用戶任務(wù)調(diào)度算法

朱科宇，朱 琦

(1.南京郵電大學(xué)江蘇省無線通信重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210003 2.南京郵電大學(xué)寬帶無線通信與傳感網(wǎng)技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210003)

隨著移動(dòng)網(wǎng)絡(luò)的快速發(fā)展，計(jì)算、存儲(chǔ)和電池資源有限的移動(dòng)設(shè)備已經(jīng)無法滿足高復(fù)雜度和高能耗服 務(wù) 的 需 求［1］。 移 動(dòng) 云 計(jì) 算 （Mobile Cloud Computing，MCC）可以利用云中可用的大量資源來提供彈性計(jì)算和存儲(chǔ)能力，以支持資源受限的終端設(shè)備。然而，計(jì)算負(fù)載向中心云的遷移將導(dǎo)致大量的數(shù)據(jù)傳輸和傳輸延遲，這將影響應(yīng)用的服務(wù)質(zhì)量，尤其是一些延遲敏感的工業(yè)控制應(yīng)用［2］，因此，移動(dòng)邊緣計(jì)算（Mobile Edge Computing，MEC）技術(shù)獲得了學(xué)術(shù)和工業(yè)界的廣泛關(guān)注［3］。MEC通過將計(jì)算、存儲(chǔ)和服務(wù)功能遷移到網(wǎng)絡(luò)邊緣，使得應(yīng)用程序、服務(wù)和內(nèi)容可以部署在離用戶更近的地方，同時(shí)得益于無線能量傳輸技術(shù)（Wireless Power Transmission，WPT）的發(fā)展，無線供能的MEC網(wǎng)絡(luò)受到越來越多的關(guān)注［4－5］。

邊緣計(jì)算網(wǎng)絡(luò)是在用戶附近部署計(jì)算能力強(qiáng)大的邊緣服務(wù)器，使得移動(dòng)用戶能以更低的時(shí)延與能耗完成相應(yīng)任務(wù)，卸載決策以及通信與計(jì)算資源的分配算法對(duì)性能會(huì)有很大影響［6］，針對(duì)MEC的任務(wù)卸載問題，許多學(xué)者做了相關(guān)研究。文獻(xiàn)［7］從任務(wù)的計(jì)算和通信兩個(gè)方面對(duì)卸載過程的能耗進(jìn)行建模，采用了一種基于人工魚群算法的能量優(yōu)化方案來進(jìn)行求解。文獻(xiàn)［8］研究了任務(wù)卸載到MEC過程中延遲和可靠性之間的權(quán)衡問題，提出了一種框架，其中用戶設(shè)備將任務(wù)劃分為子任務(wù)，并將它們依次卸載到多個(gè)鄰近的邊緣節(jié)點(diǎn)，在此框架下，本文提出了一個(gè)使延遲和卸載失敗概率共同最小的優(yōu)化問題。文獻(xiàn)［9］提出了一種用于多用戶MEC系統(tǒng)的在線聯(lián)合無線電和計(jì)算資源管理算法，目標(biāo)是在任務(wù)緩沖區(qū)穩(wěn)定性約束下，最小化移動(dòng)設(shè)備和MEC服務(wù)器的長期平均加權(quán)總和功耗。文獻(xiàn)［10］研究了基于時(shí)分多址（Time Division Multiple Access，TDMA）和正交頻分多址（Orthogonal Frequency Division Multiple Access，OFDMA）的多用戶移動(dòng)邊緣計(jì)算卸載系統(tǒng)的資源分配，同時(shí)考慮了無限和有限云計(jì)算能力的情況。文獻(xiàn)［11］提出了一種基于移動(dòng)邊緣計(jì)算的異構(gòu)網(wǎng)絡(luò)分布式聯(lián)合計(jì)算卸載與資源分配優(yōu)化方案，為了實(shí)現(xiàn)移動(dòng)終端卸載的上行子信道、上行傳輸功率和計(jì)算資源的聯(lián)合分配，設(shè)計(jì)了云與無線資源分配算法。文獻(xiàn)［12］考慮了應(yīng)用劃分和協(xié)同計(jì)算卸載的聯(lián)合問題，使得移動(dòng)設(shè)備可以在作業(yè)執(zhí)行上相互幫助，以滿足應(yīng)用的完成期限，同時(shí)最小化整體能量消耗。文獻(xiàn)［13］研究了多用戶時(shí)分多址MEC系統(tǒng)中以延遲最小為目標(biāo)的聯(lián)合通信和計(jì)算資源分配問題。但上述文獻(xiàn)并沒有采用無線供能技術(shù)來解決用戶的能耗問題，都沒有同時(shí)解決邊緣用戶的能量受限和計(jì)算能力受限這兩個(gè)問題。為此，文獻(xiàn)［14］將上述兩種技術(shù)結(jié)合，提出無線供能邊緣計(jì)算網(wǎng)絡(luò)來解決以上兩大難點(diǎn)。

無線供能通信網(wǎng)絡(luò)指在用戶設(shè)備附近部署專門的能量供應(yīng)站，為附近的用戶進(jìn)行無線能量傳輸，關(guān)鍵點(diǎn)在于無線供能的時(shí)隙分配，使得邊緣用戶能最大化利用采集到的能量進(jìn)行任務(wù)的執(zhí)行。文獻(xiàn)［14］針對(duì)單個(gè)傳感節(jié)點(diǎn)，將移動(dòng)云計(jì)算和微波功率傳輸（Microwave Power Transmission，MPT）兩種技術(shù)無縫地結(jié)合在一起，設(shè)計(jì)了最優(yōu)的二進(jìn)制計(jì)算卸載方案來最大化成功計(jì)算概率。隨后文獻(xiàn)［15－20］將文獻(xiàn)［14］考慮的單節(jié)點(diǎn)場景拓展到存在多個(gè)傳感節(jié)點(diǎn)的無線供能邊緣計(jì)算網(wǎng)絡(luò)，文獻(xiàn)［15］考慮一個(gè)由無線功率傳輸?shù)亩嘤脩鬗EC網(wǎng)絡(luò)，其中每個(gè)能量收集的用戶遵循一個(gè)二進(jìn)制計(jì)算卸載策略，即一個(gè)任務(wù)的數(shù)據(jù)集必須作為一個(gè)整體通過任務(wù)卸載到MEC服務(wù)器或遠(yuǎn)程執(zhí)行，通過聯(lián)合優(yōu)化單個(gè)計(jì)算模式選擇（即本地計(jì)算或卸載）和系統(tǒng)傳輸時(shí)間分配，最大化網(wǎng)絡(luò)中所有用戶的計(jì)算速率。文獻(xiàn)［16］提出了一個(gè)基于深度強(qiáng)化學(xué)習(xí)的在線卸載框架對(duì)文獻(xiàn)［15］中的場景進(jìn)行求解，該框架實(shí)現(xiàn)了一個(gè)深度神經(jīng)網(wǎng)絡(luò)作為一個(gè)可擴(kuò)展的解決方案，從經(jīng)驗(yàn)中學(xué)習(xí)二進(jìn)制卸載決策。文獻(xiàn)［17］采用非正交多址（Non?Orthgonal Multiple Access， NOMA）進(jìn)行信息傳輸，考慮速率自適應(yīng)的計(jì)算任務(wù)，旨在通過共同優(yōu)化各個(gè)計(jì)算模式選擇（本地計(jì)算或卸載）、能量傳輸和信息傳輸?shù)臅r(shí)間分配以及本地計(jì)算速率，來最大化所有用戶的總計(jì)算速率或發(fā)射功率水平。文獻(xiàn)［18］研究了混合接入點(diǎn)在全雙工模式下操作，以在同一頻段內(nèi)同時(shí)向移動(dòng)設(shè)備廣播能量并接收計(jì)算任務(wù)，每個(gè)移動(dòng)設(shè)備都依賴于將收集的能量通過本地執(zhí)行或部分卸載到混合接入點(diǎn)來完成計(jì)算任務(wù)。文獻(xiàn)［19］研究了一種邊緣用戶間最小計(jì)算能效最大化，以確保用戶間的公平性。文獻(xiàn)［20］考慮到多個(gè)子任務(wù)卸載相互之間的關(guān)系，提出了一種基于強(qiáng)化學(xué)習(xí)的無模型方法，根據(jù)網(wǎng)絡(luò)環(huán)境的變化自適應(yīng)地學(xué)習(xí)以優(yōu)化卸載決策和能耗。

上述研究中無線供能的時(shí)間是固定的，同時(shí)均假設(shè)邊緣服務(wù)器的計(jì)算能力是無限的，忽略了MEC服務(wù)器的計(jì)算時(shí)延。因此，為了更好地貼合實(shí)際應(yīng)用場景，本文針對(duì)考慮MEC服務(wù)器的計(jì)算能力是有限的，邊緣用戶通過無線供能設(shè)備獲取能量，用于任務(wù)本地執(zhí)行或者將任務(wù)卸載到MEC服務(wù)器執(zhí)行，通過聯(lián)合優(yōu)化無線供能時(shí)間、邊緣用戶的卸載決策及MEC的任務(wù)調(diào)度來最小化系統(tǒng)執(zhí)行的最長時(shí)延。本文的主要貢獻(xiàn)如下：

（1）針對(duì)無線供能的邊緣計(jì)算網(wǎng)絡(luò)，在多用戶二進(jìn)制計(jì)算卸載模式下，通過聯(lián)合優(yōu)化無線供能時(shí)間、邊緣用戶的卸載決策及任務(wù)調(diào)度，建立了系統(tǒng)執(zhí)行最大時(shí)延最小化的優(yōu)化問題，并證明了本地計(jì)算時(shí)間是關(guān)于任務(wù)執(zhí)行能耗的單調(diào)遞減且下凸函數(shù)，任務(wù)無線傳輸時(shí)間是關(guān)于能耗的單調(diào)遞減且下凸函數(shù)。

（2）該優(yōu)化問題是一個(gè)混合整數(shù)的非凸優(yōu)化問題難以求解，本文設(shè)計(jì)了一種兩層交替迭代的求解方案，第一層為用戶卸載決策和任務(wù)調(diào)度的優(yōu)化，首先采用貪婪算法進(jìn)行求解，但是這種方案未考慮到用戶的信道增益情況，因此進(jìn)一步提出了基于改進(jìn)的約翰遜算法進(jìn)行求解；第二層為無線供能時(shí)間的優(yōu)化，采用黃金分割法進(jìn)行求解。

（3）仿真結(jié)果表明，本文提出的迭代算法收斂速度較快，與文獻(xiàn)［16］算法相比，本文算法有效地降低了系統(tǒng)任務(wù)執(zhí)行時(shí)延，當(dāng)用戶數(shù)為16時(shí)，時(shí)延降低了12%，并且當(dāng)用戶數(shù)變多時(shí)，兩種算法之間的性能差距在逐漸增加。同時(shí)MEC服務(wù)器的計(jì)算能力越強(qiáng)、無線供能的能量轉(zhuǎn)換效率越高，系統(tǒng)任務(wù)執(zhí)行時(shí)延就越短。

1 系統(tǒng)模型及問題描述

1.1 系統(tǒng)模型

本文的系統(tǒng)模型如圖1所示，由一個(gè)提供能量服務(wù)的專用能量站、多個(gè)具有無線充電功能的用戶終端以及一個(gè)配置了MEC服務(wù)器的基站組成。假設(shè)所有的設(shè)備都配備了單根天線且每個(gè)邊緣用戶都配備了一個(gè)容量有限的可充電電池，每個(gè)設(shè)備都有一個(gè)需要計(jì)算的任務(wù)。邊緣服務(wù)器和專用能量站為邊緣用戶終端提供計(jì)算服務(wù)與能量服務(wù)，邊緣用戶則利用收集到的能量將需要計(jì)算的任務(wù)進(jìn)行本地執(zhí)行或者卸載到邊緣服務(wù)器執(zhí)行。假設(shè)每個(gè)用戶需要先進(jìn)行能量采集，然后進(jìn)行任務(wù)處理，在持續(xù)時(shí)間為τ的能量收集階段，專用能量站通過無線能量傳輸?shù)姆绞綖樗械倪吘売脩暨M(jìn)行供能，在任務(wù)卸載階段，卸載用戶利用收集的能量采用時(shí)分復(fù)用的方式進(jìn)行上行任務(wù)卸載。如果用戶的任務(wù)在本地執(zhí)行，則時(shí)延就是任務(wù)計(jì)算的時(shí)間；如果用戶選擇卸載到邊緣服務(wù)器執(zhí)行，則時(shí)延包括任務(wù)卸載時(shí)間、任務(wù)計(jì)算時(shí)間和任務(wù)回傳時(shí)間。由于下行回傳數(shù)據(jù)量一般較小，本文忽略了下行傳輸階段的傳輸時(shí)間［20］。

圖1 無線供能用戶計(jì)算卸載的系統(tǒng)模型

假設(shè)一共有N個(gè)用戶設(shè)備，每個(gè)用戶設(shè)備都有一個(gè)需要計(jì)算的任務(wù)，定義用戶的卸載決策為X＝｛xi｝，xi＝ ｛0，1｝ 表示用戶是否將任務(wù)卸載到 MEC服務(wù)器執(zhí)行，如果用戶i將任務(wù)卸載到MEC服務(wù)器執(zhí)行，那么 xi＝1， 否則 xi＝0。 定義 C ＝ ［C1，C2，…，CNc］表示卸載到MEC服務(wù)器的用戶集合，Ci表示第 i個(gè)卸載的用戶； L ＝ ［L1，L2，…，LNl］ 表示在本地執(zhí)行用戶的集合，Li表示第i個(gè)在本地執(zhí)行的用戶。上述滿足N＝C∪L，C∩L＝?，并且N＝Nc＋Nl，Nc和Nl分別表示卸載到MEC服務(wù)器的用戶數(shù)和在本地執(zhí)行的用戶數(shù)。MEC服務(wù)器有一個(gè)單核的CPU處理器，并且每次按照先到先執(zhí)行的順序進(jìn)行處理，另外，為了能讓用戶任務(wù)的執(zhí)行滿足C的執(zhí)行順序，假設(shè)MEC服務(wù)器有一個(gè)足夠大的任務(wù)緩存單元來緩存沒有執(zhí)行的已卸載任務(wù)。

本文的目標(biāo)是降低整個(gè)系統(tǒng)的用戶任務(wù)執(zhí)行的時(shí)延，時(shí)延包括本地用戶的計(jì)算時(shí)延、卸載用戶的通信時(shí)延和計(jì)算時(shí)延以及無線供能的充能時(shí)延。本地用戶的計(jì)算時(shí)延與用戶的CPU工作效率有關(guān)，也與用戶可使用的能量有關(guān)；卸載用戶的通信時(shí)延則與用戶的發(fā)射功率有關(guān)，計(jì)算時(shí)延與MEC的計(jì)算能力以及任務(wù)的復(fù)雜度有關(guān)；無線供能的充能時(shí)間與用戶可以獲得的能量有關(guān)，它會(huì)影響任務(wù)的執(zhí)行與傳輸速率。

1.2 通信與無線供能模型

與本地計(jì)算相比，將計(jì)算任務(wù)卸載到MEC服務(wù)器進(jìn)行處理可以降低時(shí)延與能耗，但傳輸任務(wù)數(shù)據(jù)會(huì)消耗額外的時(shí)延與能耗（即通信時(shí)延與能耗）。如圖2所示，本文考慮無線能量傳輸與用戶任務(wù)傳輸占用相同的頻段，因此不能同時(shí)進(jìn)行，并且用戶的任務(wù)卸載采用時(shí)分復(fù)用的形式。根據(jù)Shann?Hartley定理，用戶到基站之間的通信模型可以定義為

圖2 用戶計(jì)算卸載的無線通信模型

式中，W表示信道帶寬，hi表示用戶i與基站之間的信道增益，表示用戶i的發(fā)射功率，σ2表示高斯白噪聲。

在無線能量傳輸?shù)臅r(shí)隙τ內(nèi)，對(duì)所有邊緣用戶進(jìn)行無線能量傳輸，那么第i個(gè)用戶采集到的能量ei可以表示為

式中，μ∈（0，1）表示能量轉(zhuǎn)化效率，P表示能量專用站在能量收集階段的發(fā)射功率，gi表示專用能量站與第i個(gè)邊緣用戶之間的信道增益。

1.3 計(jì)算模型

將用戶終端 i的計(jì)算任務(wù)定義為數(shù)組Wi＝，其中表示任務(wù)計(jì)算輸入數(shù)據(jù)的大小，Di表示單任務(wù)執(zhí)行所需的CPU周期數(shù)，表示任務(wù)計(jì)算后響應(yīng)數(shù)據(jù)大小，時(shí)延計(jì)算分兩種情況進(jìn)行討論。

（1）當(dāng)用戶i選擇本地執(zhí)行時(shí)，那么用戶選擇本地執(zhí)行所需要的計(jì)算時(shí)延可以表示為

將式（3）代入式（4）中可以得到

式中，fi為用戶終端i的計(jì)算能力，即單位時(shí)間運(yùn)行CPU周期數(shù)，而且用戶CPU周期滿足，c表示每個(gè)CPU周期消耗能量的系數(shù)，Ei表示可以用于任務(wù)執(zhí)行的能耗。

定理1 式（5）的本地計(jì)算時(shí)間是關(guān)于任務(wù)執(zhí)行的能耗Ei的單調(diào)遞減且下凸函數(shù)。

證明：對(duì)式（5）求一階導(dǎo)可得

因此可以得到式（5）是一個(gè)單調(diào)遞減的函數(shù)，再對(duì)其求二階導(dǎo)可得

可以得到式（5）是一個(gè)凸函數(shù)，故定理1得證。

根據(jù)定理1可知，為了最小化用戶本地的執(zhí)行時(shí)延，在滿足本地計(jì)算能力的前提下，用戶將采集到的能量全部用完可以獲得最短的本地執(zhí)行時(shí)延，即滿足時(shí)可以獲得最短的執(zhí)行時(shí)間。

（2）當(dāng)用戶i選擇將任務(wù)卸載到MEC執(zhí)行時(shí)，根據(jù)通信模型可以得到卸載數(shù)據(jù)從用戶終端到邊緣節(jié)點(diǎn)的傳輸時(shí)間為

因此可以得到t是關(guān)于Ei的單調(diào)遞增函數(shù)，即是關(guān)于Ei的單調(diào)遞減函數(shù)，于是可以得到能耗Ei是關(guān)于無線傳輸時(shí)延的單調(diào)遞減函數(shù)。

接下來證明能耗Ei是關(guān)于無線傳輸時(shí)延的下凸函數(shù)，因?yàn)槟芎腅i是關(guān)于無線傳輸時(shí)延的單調(diào)遞減函數(shù)，因此能耗Ei與無線傳輸時(shí)延是一一映射關(guān)系，那么就有的凹凸性相同，其中是 f（Ei） 的反函數(shù)。 不妨將a，b歸一化為1（不影響函數(shù)的凹凸性），可以得到，對(duì)其進(jìn)行求導(dǎo)可以得到

根據(jù)定理2可知，為了最小化任務(wù)無線傳輸?shù)臅r(shí)延，隨著用戶能量的增加，在滿足最大發(fā)射功率的前提下，用戶的發(fā)射功率會(huì)不斷增加，從而無線傳輸?shù)臅r(shí)延下降，當(dāng)用戶將獲得的能量全部用于任務(wù)的傳輸，即，可以獲得最小的無線傳輸時(shí)延。

假設(shè)M E C服務(wù)器的處理能力為fedge，則任務(wù)在M E C服務(wù)器執(zhí)行的計(jì)算時(shí)延可以表示為

1.4 問題描述

本文研究的目標(biāo)是用戶利用無線供能獲得的能量來進(jìn)行任務(wù)的處理，通過聯(lián)合本地計(jì)算和MEC服務(wù)器計(jì)算，以最小化任務(wù)的執(zhí)行時(shí)延為目的，獲得最優(yōu)的卸載決策和任務(wù)調(diào)度。

如果任務(wù)選擇在本地執(zhí)行，那么本地執(zhí)行的任務(wù)在不同的用戶設(shè)備上可以同時(shí)執(zhí)行，前i個(gè)用戶中本地執(zhí)行用戶任務(wù)的完成時(shí)間可以表示為

如果用戶選擇將任務(wù)卸載到MEC服務(wù)器上去執(zhí)行，那么必須滿足以下兩個(gè)條件：首先，所有的先前和當(dāng)前的任務(wù)數(shù)據(jù)都已經(jīng)傳輸完成；其次，MEC的處理器有空閑的時(shí)間可以用于執(zhí)行新的任務(wù)。因此，本文可以將前i個(gè)用戶中卸載的用戶執(zhí)行時(shí)延表示為

因此，本文聯(lián)合計(jì)算卸載、任務(wù)調(diào)度和無線供能的優(yōu)化問題可以表示為

2 基于無線供能的兩層迭代優(yōu)化算法

由于問題P1是一個(gè)混合整數(shù)非凸問題，為了求解這個(gè)問題，本文將該問題分解成一個(gè)兩層的交替優(yōu)化的問題，上層在給定供電時(shí)間的情況下，采用貪婪算法或改進(jìn)的約翰遜算法求解出用戶的卸載決策和任務(wù)調(diào)度，下層則在給定的卸載決策和任務(wù)調(diào)度下采用黃金分割法求解出最優(yōu)的無線供能時(shí)間。通過采用貪婪算法或改進(jìn)的約翰遜算法與黃金分割法進(jìn)行交替迭代優(yōu)化，最終收斂得到問題P1的解。

2.1 基于貪婪算法的卸載決策及任務(wù)調(diào)度算法

在給定的無線供能時(shí)延下，本文采用貪婪算法和流水線調(diào)度算法確定用戶的卸載決策和任務(wù)調(diào)度順序。對(duì)于本地執(zhí)行的用戶，不需要考慮任務(wù)執(zhí)行的順序，只需要關(guān)注最長的完成時(shí)間；對(duì)于卸載執(zhí)行的用戶則是一個(gè)標(biāo)準(zhǔn)的雙機(jī)流水調(diào)度問題，需要考慮任務(wù)的調(diào)度順序。本文提出的貪婪算法的核心思想是同時(shí)最大化MEC服務(wù)器和本地用戶服務(wù)器的CPU利用率，所有的用戶根據(jù)它們執(zhí)行任務(wù)的CPU周期數(shù)分配到本地和MEC服務(wù)器執(zhí)行，并且通過流水線調(diào)度算法來確定卸載用戶的調(diào)度順序，最小化本地執(zhí)行時(shí)間與MEC執(zhí)行的時(shí)間之差。

卸載決策及任務(wù)調(diào)度如算法1所示，具體步驟如下：第1行表示根據(jù)初始的無線供能時(shí)間τ分別計(jì)算出每個(gè)用戶采集到的能量，第2行將用戶集合根據(jù)需要執(zhí)行的任務(wù)所需的CPU周期數(shù)進(jìn)行降序排列得到集合M，第4行表示根據(jù)式（17）和式（19）分別計(jì)算表示集合L?中的第一個(gè)用戶終端，表示集合C?中的第一個(gè)用戶。第5～15行表示將集合M中的用戶進(jìn)行分配，首先將第t個(gè)用戶分別添加到集合C?與集合L?中，然后根據(jù)式（17）計(jì)算集合L?中的， 根據(jù)流水線調(diào)度算法，將集合C?中的用戶分為兩個(gè)不相交的子集A和B，滿足C?＝A∪B，A∩B＝?，其中A和B的定義分別為

得到一個(gè)重新排列的卸載用戶集合C?，然后根據(jù)式（19）計(jì)算獲得， 直到所有的用戶全部被分配完。最后可以獲得本地的用戶集合L?，將其中的用戶設(shè)置為xi＝0，卸載的用戶集合C?，將其中的用戶設(shè)置為xi＝1。

算法1 基于所需CPU周期數(shù)的完全卸載決策和調(diào)度算法（FSC）

2.2 基于改進(jìn)約翰遜算法的卸載決策及任務(wù)調(diào)度算法

由于2.1節(jié)中的基于貪婪算法的策略依靠任務(wù)執(zhí)行所需要的CPU周期數(shù)來進(jìn)行任務(wù)的劃分，沒有考慮到不同用戶信道增益的差別導(dǎo)致計(jì)算時(shí)延的差別，這會(huì)影響到最終的系統(tǒng)任務(wù)完成時(shí)間。在本節(jié)中，將利用約翰遜算法的思想，提出一種改進(jìn)的約翰遜算法來求解多用戶的完全卸載決策及任務(wù)調(diào)度。約翰遜算法作為流水車間調(diào)度的常用算法，對(duì)于選擇卸載的用戶任務(wù)調(diào)度非常適合，但是本文存在本地執(zhí)行的用戶，直接采用約翰遜算法難以求解，因此本文對(duì)原有的約翰遜算法進(jìn)行了改進(jìn)。根據(jù)用戶任務(wù)的傳輸時(shí)間和在MEC執(zhí)行的時(shí)間可以將用戶分為兩個(gè)不相交的子集D和子集E，分別表示如下

集合D中的用戶在集合E之前執(zhí)行，這個(gè)算法的核心思想就是最大化MEC的CPU利用率。具體的過程見算法2，根據(jù)這個(gè)改進(jìn)的約翰遜算法，基于用戶任務(wù)的卸載時(shí)延與執(zhí)行時(shí)延可以將所有的用戶分配到本地執(zhí)行和MEC服務(wù)器執(zhí)行。

算法2的具體步驟如下：第1行表示根據(jù)初始的無線供能時(shí)間τ分別計(jì)算出每個(gè)用戶采集到的能量，第2～4行根據(jù)式（23）與式（24）獲得兩個(gè)不相交的集合D和E，并且將集合D中的用戶按照任務(wù)的傳輸時(shí)間進(jìn)行升序排列，將集合E中的用戶按照任務(wù)的執(zhí)行時(shí)間進(jìn)行降序排列。第6行表示分別將集合D中的第一個(gè)用戶添加到C?中，將集合E中的最后一個(gè)用戶添加到L?中，然后根據(jù)式（17）與（19）計(jì)算，第 7～12行根據(jù)本地和卸載計(jì)算的時(shí)間將集合D和E中的用戶進(jìn)行分配，直到其中的一個(gè)集合的用戶被分配完成。第13～17行表示將剩下未分配的用戶添加到集合M中，第18～24行則根據(jù)本地和卸載計(jì)算的時(shí)間將集合M中的用戶全部分配完成。最后可以獲得本地的用戶集合L?，將其中的用戶設(shè)置為xi＝0，卸載的用戶集合C?，將其中的用戶設(shè)置為xi＝1。

算法2 基于改進(jìn)約翰遜的完全卸載決策和調(diào)度算法（FSJ）

2.3 無線供能時(shí)間優(yōu)化算法

在本節(jié)中，已經(jīng)通過算法1或算法2獲得了用戶的卸載決策和調(diào)度順序。接下來將通過給定的卸載決策和任務(wù)調(diào)度順序求解出最佳的無線供能時(shí)間。對(duì)于不同的用戶來說，在相同時(shí)間內(nèi)通過無線供能設(shè)備獲得的能量是不一樣的，因此對(duì)應(yīng)的發(fā)射功率和本地CPU工作頻率也不一樣，從而導(dǎo)致任務(wù)的完成時(shí)間也不相同。如果用戶的無線供能時(shí)間確定了，就可以通過算法1或算法2獲得任務(wù)的卸載決策和調(diào)度順序，同理，如果用戶的卸載決策和調(diào)度順序確定了，同樣可以求解出最佳的無線供能時(shí)間。對(duì)于問題P1，在給定用戶的卸載決策和調(diào)度順序下，可以重寫為

然而，問題P2雖然是一個(gè)一維函數(shù)的最值問題，但是該問題是不可導(dǎo)的，難以求解出顯式表達(dá)式。

定理3 問題P2是一個(gè)關(guān)于時(shí)間τ的下凸函數(shù)。

證明：問題P2包含兩項(xiàng)，后一項(xiàng)τ是一個(gè)線性遞增函數(shù)，同時(shí)也是特殊的下凸函數(shù)，下面來證前一項(xiàng)是一個(gè)下凸函數(shù)，其中是選擇本地執(zhí)行用戶的一個(gè)最大時(shí)延，由定理1可知它是關(guān)于能耗的單調(diào)遞減且下凸的函數(shù)，而根據(jù)式（2）可知能耗與無線供能時(shí)間是線性關(guān)系，所以是一個(gè)關(guān)于無線供能時(shí)間τ的單調(diào)遞減且下凸的函數(shù)。對(duì)于則是一個(gè)流水車間調(diào)度的完成時(shí)間，其中MEC服務(wù)器的任務(wù)執(zhí)行時(shí)間是一個(gè)定值，只有無線傳輸?shù)臅r(shí)延與無線供能的能耗有關(guān)，由定理2可知單次的無線傳輸時(shí)延與能耗之間是一個(gè)單調(diào)遞減且下凸的函數(shù)，因此可知整個(gè)卸載過程的完成時(shí)間是一個(gè)關(guān)于無線供能時(shí)間τ的單調(diào)遞減且下凸的函數(shù)。不妨令前一項(xiàng)為 f（x）＝max｛f1（x）、f2（x）｝， 有 f1（x）、f2（x） 是下凸函數(shù)，其定義域?yàn)?domf（x） ＝ dom f1（x） ∩ domf2（x）， 任取0≤ θ≤1以及 x，y∈ domf（x），有

由定理3可知，問題P2是一個(gè)關(guān)于時(shí)間τ的下凸函數(shù)，可以采用常見的一維搜索算法進(jìn)行求解。因此本文將采用黃金分割法進(jìn)行求解，該算法常用于不可導(dǎo)的一維搜索問題，求解效率較高，具體的步驟見算法3。通過在給定的卸載決策和任務(wù)調(diào)度下，求解出最優(yōu)的無線供能時(shí)間，然后利用算法1或算法2求解出卸載決策，多次交替迭代來降低系統(tǒng)的執(zhí)行時(shí)延。

算法3 無線供能時(shí)間分配算法（WPTA）

2.4 聯(lián)合無線供能時(shí)間分配和卸載決策及任務(wù)調(diào)度分配算法

在這節(jié)中，將聯(lián)合算法1、算法2和算法3對(duì)問題P1進(jìn)行求解，求解出最優(yōu)的卸載決策、任務(wù)調(diào)度和無線供能時(shí)間。算法4中主要分為兩層，上一層用來求解卸載決策和任務(wù)調(diào)度，下一層用來獲得最佳的無線供能時(shí)間。用戶的卸載決策不僅取決于任務(wù)的執(zhí)行時(shí)延，而且與無線供能獲得的能耗有關(guān)。算法4是一個(gè)兩層的迭代式算法，為了獲得問題P1的次優(yōu)解，本文采用了算法1或算法2這兩種方法來更新卸載決策和任務(wù)調(diào)度，定義采用算法1和算法2進(jìn)行迭代求解的算法分別記為 JFWA?C和JFWA?J，采用算法3來更新無線供能時(shí)間。算法4中第4行計(jì)算出初始的效用函數(shù)Fold，第5行記錄更新后的效用函數(shù)值，通過多次迭代，每次迭代后系統(tǒng)的效用函數(shù)下降，直到收斂，求解出最優(yōu)的卸載決策、任務(wù)調(diào)度和無線供能時(shí)間。從仿真圖3中能看出具有良好的收斂特性。

圖3 JFWA?C與JFWA?J算法的迭代收斂圖

算法4 兩層迭代優(yōu)化算法

3 仿真結(jié)果與分析

在本節(jié)中，基于移動(dòng)邊緣計(jì)算網(wǎng)絡(luò)，同時(shí)考慮無線功率傳輸與邊緣用戶任務(wù)的計(jì)算卸載，通過計(jì)算機(jī)仿真來驗(yàn)證本文所提方案的優(yōu)越性與有效性。假設(shè)用戶隨機(jī)分布在半徑為10 m的圓中，專用能量站位于圓心處，邊緣服務(wù)器距離圓心80 m，專用能量站與用戶i的信道增益gi以及邊緣服務(wù)器與用戶i的信道增益hi分別為

式中，g′i表示第i個(gè)邊緣用戶與專用能量站之間的小尺度信道衰落，d0，i表示第 i個(gè)邊緣用戶與專用能量站之間的距離，路徑損耗指數(shù)α取2.8，Ad＝ 4.11 表示天線增益， fc＝ 2.4 GHz表示載波頻率，d1，i表示用戶與邊緣服務(wù)器之間的距離，de≥2表示路徑損耗指數(shù)，本文取de＝ 2.8， 每個(gè)CPU周期的能量消耗系數(shù) c＝ 10－22，其余仿真參數(shù)見表1。

表1 仿真參數(shù)

接下來將本文提出的兩層迭代式的次優(yōu)算法與以下算法進(jìn)行對(duì)比分析，通過仿真來驗(yàn)證本文所提算法的性能。

（1）JFWA?C：本文提出的第一種算法，上層采用貪婪算法求解卸載決策和任務(wù)調(diào)度，下層采用黃金分割法求解最佳無線供能時(shí)間。

（2） JFWA?J：本文提出的第二種算法，上層采用改進(jìn)的約翰遜算法求解用戶的卸載決策和任務(wù)調(diào)度，下層采用黃金分割法求解最佳無線供能時(shí)間。

（3）所有用戶全部在本地執(zhí)行。

（4）采用文獻(xiàn)［16］的卸載決策和無線供能時(shí)間分配方案。

（5）采用文獻(xiàn)［21］的完全卸載任務(wù)調(diào)度方案。

圖3給出了JFWA?C與JFWA?J算法的迭代收斂圖，從圖中可以發(fā)現(xiàn)JFWA?J算法比JFWA?C算法能夠獲得更低的系統(tǒng)執(zhí)行時(shí)延，這是因?yàn)榕cJFWA?C算法相比，JFWA?J算法有更多的用戶將任務(wù)卸載到MEC執(zhí)行，兩種算法的收斂值不同主要取決于卸載決策和任務(wù)調(diào)度的改變。從圖中也表明本文所提的兩種算法收斂速度都比較塊，在14次的時(shí)候基本區(qū)域平穩(wěn)。

圖4對(duì)比分析了5種不同策略下的用戶執(zhí)行時(shí)延，從圖中可以發(fā)現(xiàn)本文所提的JFWA?J算法具有最低的系統(tǒng)執(zhí)行時(shí)延，并且JFWA?J算法比JFWA?C算法具有更好的性能，這是因?yàn)镴FWA?J算法在計(jì)算任務(wù)卸載決策時(shí)，同時(shí)考慮了用戶任務(wù)的計(jì)算量大小與信道增益情況。當(dāng)用戶完全在本地執(zhí)行時(shí)，那么系統(tǒng)的整體執(zhí)行時(shí)延將取決于最后完成計(jì)算任務(wù)的用戶，多次實(shí)驗(yàn)可以得到一條較為平穩(wěn)的曲線。與文獻(xiàn)［16］的算法對(duì)比可以發(fā)現(xiàn)，當(dāng)用戶數(shù)較少的時(shí)候，性能差異并不大，隨著用戶數(shù)的增加，文獻(xiàn)［16］的算法與本文所提的JFWA?J算法性能差距逐漸增大，這是因?yàn)槲墨I(xiàn)［16］卸載決策與本文相比，性能的差距主要體現(xiàn)在卸載過程，本文采用的是流水線調(diào)度策略，減少了一定的重疊時(shí)延，隨著用戶數(shù)的增加，這種時(shí)延也越來越明顯。對(duì)比文獻(xiàn)［21］可以發(fā)現(xiàn)，在用戶數(shù)較少的情況下性能相近，這是因?yàn)榇藭r(shí)將任務(wù)卸載是最優(yōu)的決策。隨著用戶數(shù)的增加，卸載到MEC服務(wù)器的時(shí)延越來越大，直到超過選擇在本地執(zhí)行的時(shí)延，本文選擇將部分用戶的任務(wù)在本地執(zhí)行，因此性能會(huì)優(yōu)于文獻(xiàn)［21］的完全卸載任務(wù)調(diào)度算法。綜上所述，對(duì)比5種算法可以發(fā)現(xiàn)，本文所提的JFWA?J算法與JFWA?C算法均有著不錯(cuò)的性能。

圖4 5種算法性能比較圖

圖5和圖6則分析了不同能量轉(zhuǎn)換效率與不同MEC服務(wù)器計(jì)算能力對(duì) JFWA?J算法和JFWA?C算法的性能影響。在圖5中分別對(duì)比了能量轉(zhuǎn)換效率為0.3、0.5、0.7時(shí)的算法性能，從圖5中分析可以發(fā)現(xiàn)，當(dāng)能量轉(zhuǎn)換效率較高時(shí)，獲取一定能量所需要的無線供能時(shí)間也更短，因此當(dāng)能量轉(zhuǎn)換效率為0.3時(shí)，系統(tǒng)需要花費(fèi)大量的時(shí)間進(jìn)行無線能量的傳輸，導(dǎo)致系統(tǒng)的執(zhí)行時(shí)間最長。在圖6中分別對(duì)比了MEC服務(wù)器計(jì)算能力為 5 GHz、10 GHz、15 GHz時(shí)的算法性能，MEC服務(wù)器的計(jì)算能力越強(qiáng)，那么對(duì)于卸載用戶的任務(wù)計(jì)算時(shí)延也就越短，從圖6中可以發(fā)現(xiàn)，當(dāng)MEC服務(wù)器計(jì)算能力為5 GHz時(shí)，卸載任務(wù)執(zhí)行所需要的時(shí)間更長，這將導(dǎo)致更多的用戶選擇本地進(jìn)行執(zhí)行，使得卸載到MEC服務(wù)器執(zhí)行的用戶數(shù)更快的接近飽和。對(duì)比分析MEC服務(wù)器計(jì)算能力為15 GHz時(shí)，此時(shí)則有更多的用戶選擇卸載到MEC服務(wù)器進(jìn)行執(zhí)行，MEC服務(wù)器執(zhí)行的用戶數(shù)達(dá)到飽和的值也越大。

圖5 能量轉(zhuǎn)化效率對(duì)系統(tǒng)執(zhí)行時(shí)延的影響

圖6 MEC服務(wù)器計(jì)算能力對(duì)性能的影響

圖7和圖8分別分析了采用JFWA?C算法與JFWA?J算法用戶選擇本地執(zhí)行與卸載執(zhí)行的分布比例，從圖7與圖8中可以很明顯發(fā)現(xiàn)，當(dāng)用戶數(shù)較少的情況下，采用流水線調(diào)度對(duì)所有任務(wù)進(jìn)行卸載執(zhí)行所需要的時(shí)延比某個(gè)用戶在本地執(zhí)行的時(shí)間更短，此時(shí)所有的用戶會(huì)選擇卸載執(zhí)行任務(wù)，當(dāng)用戶數(shù)達(dá)到10左右時(shí)，用戶選擇卸載會(huì)比某個(gè)用戶在本地的執(zhí)行時(shí)延更長，因此就有部分用戶選擇在本地執(zhí)行，卸載到MEC服務(wù)的用戶數(shù)也就接近飽和。同時(shí)對(duì)比圖7與圖8可以發(fā)現(xiàn)，隨著用戶數(shù)的增加，采用JFWA?J算法比采用JFWA?C算法選擇卸載的用戶數(shù)更多，這也解釋了為什么JFWA?J算法比JFWA?C算法有著更小的執(zhí)行時(shí)延。

圖7 采用JFWA?C算法時(shí)不同用戶數(shù)下本地執(zhí)行與卸載執(zhí)行的分布比例

圖8 采用JFWA?J算法時(shí)不同用戶數(shù)下本地執(zhí)行與卸載執(zhí)行的分布比例

4 結(jié)束語

本文討論了基于無線供能邊緣計(jì)算網(wǎng)絡(luò)的用戶卸載決策及任務(wù)調(diào)度問題。聯(lián)合考慮無線供能時(shí)間與用戶卸載決策，提出了以最小化系統(tǒng)用戶執(zhí)行時(shí)延為目標(biāo)的優(yōu)化問題，然后提出了一種兩層迭代式的求解方案。上層用于解決用戶的卸載決策與任務(wù)調(diào)度問題，提出了FSC與FSJ次優(yōu)算法進(jìn)行求解，下層采用黃金分割法求解最佳的無線供能時(shí)間，兩層交替迭代求解優(yōu)化問題。實(shí)驗(yàn)結(jié)果表明，本文提出的算法在降低系統(tǒng)時(shí)延方面相較于其他策略有著明顯的提升，并且本文算法收斂速度較快。