王一然

（華北電力大學(xué)，北京 102200）

泛在電力物聯(lián)網(wǎng)就是圍繞電力系統(tǒng)各環(huán)節(jié)，充分應(yīng)用現(xiàn)代信息技術(shù)，實(shí)現(xiàn)電力系統(tǒng)各環(huán)節(jié)的智能化。隨著泛在電力物聯(lián)網(wǎng)的建設(shè)，上傳數(shù)據(jù)量爆炸式增加，集中式的處理不再能夠滿足需求[1]。移動邊緣計(jì)算（Mobile Edge Computing，MEC）被認(rèn)為是解決此問題的有效方式，它將具有空閑資源的MEC服務(wù)器等各種設(shè)施當(dāng)作分布式邊緣，將計(jì)算任務(wù)加載到物理上靠近數(shù)據(jù)源的移動邊緣，以顯著減少傳輸延遲[2]。

1 介紹

文章考慮移動設(shè)備和MEC服務(wù)器的計(jì)算能力、無線信道條件和時延約束，將MEC系統(tǒng)中的任務(wù)分配問題歸結(jié)為一對一的匹配問題。該任務(wù)分配機(jī)制的主要目標(biāo)是在滿足設(shè)備延遲需求以及良好可擴(kuò)展性的同時，降低總體能耗[3]。

文章主要進(jìn)行了以下研究：（1）MEC系統(tǒng)中的任務(wù)分配問題。提出了分布式執(zhí)行的任務(wù)分配機(jī)制[4]。（2）理論上證明了該任務(wù)分配機(jī)制能夠使設(shè)備和MEC服務(wù)器之間保持最穩(wěn)定的匹配。（3）該任務(wù)分配機(jī)制可以顯著降低總體能耗，并能夠良好地平衡計(jì)算的復(fù)雜性和能耗。

2 系統(tǒng)模型

文章假設(shè)所有移動設(shè)備都能生成任務(wù)，但僅具有過多計(jì)算能力的設(shè)備和MEC服務(wù)器[以下統(tǒng)稱為邊緣節(jié)點(diǎn)（Edge Nodes，ENs）]才能進(jìn)行計(jì)算任務(wù)。文章假設(shè)大多數(shù)任務(wù)可以在一個時隙內(nèi)完成，而大型任務(wù)被分成若干子任務(wù)，子任務(wù)可以在一個時隙內(nèi)完成。下文中的“任務(wù)（Tasks，Ts）”將用于指在一個時隙中作為一個整體計(jì)算的任務(wù)[5]。

文章模擬了一個MEC場景。該場景中有M個Ts，Ts集為T={T1，……，Tm}，有N個ENs，ENs集為E={E1，……，Em}。ENs可以將資源平均劃分為多個虛擬資源單元（Virtual Resource Units，VRU），從而實(shí)現(xiàn)任務(wù)的并行計(jì)算。Ej處的VRU數(shù)量稱為Ej的配額，用Qj表示。假設(shè)VRU在不同ENs下的計(jì)算能力不同，用CPU頻率（Hz）來描述ENs的計(jì)算能力，即Ej處的每個VRU的CPU頻率用Fj表示。

3 問題描述

匹配理論是描述隨著時間的推移形成互惠關(guān)系的數(shù)學(xué)框架。匹配時，雙方會形成對彼此的偏好列表。因此，基于匹配理論的協(xié)議一般無需集中式協(xié)調(diào)器，且具有良好的可擴(kuò)展性。文章將MEC系統(tǒng)中的任務(wù)分配問題轉(zhuǎn)化為匹配博弈。Ts和ENs是要互相匹配的不相連代理集。假設(shè)一個Ts只能分配給一個ENs，一個ENs只能接受一個Ts。Sij表示Ti與Ej是否匹配。Sij=1表示匹配，而Sij=0表示不匹配。

3.1 時延問題

時延是任務(wù)分配中需要解決的主要問題，不同的設(shè)備對時間的敏感度不同。延遲容限定義為從計(jì)算請求發(fā)出到任務(wù)完成的時間，表示設(shè)備的時間敏感性。Ti的延遲容限用表示。加載Ts會產(chǎn)生額外的傳輸能耗和傳輸延遲，因此每個Ts必須仔細(xì)決定任務(wù)加載到哪個相鄰的ENs?？傮w延遲通常由3個部分組成：（1）傳輸延遲。（2）排隊(duì)延遲。（3）計(jì)算延遲。

傳輸延遲是指通過無線連接將Ts傳輸?shù)紼Ns的時間。隊(duì)列延遲是任務(wù)在隊(duì)列中等待直到可以執(zhí)行的時間。文章假設(shè)每個Ts均使用EN或VRU的全部資源執(zhí)行Ts（即可以省略排隊(duì)延遲）。計(jì)算延遲取決于EN的計(jì)算能力，是執(zhí)行Ts所需的時間。Ti與Ej匹配時的總延遲Lij表示如下：

其中，Ci表示成功執(zhí)行Ti所需的CPU周期數(shù)。

文章假設(shè)Ts使用正交信道進(jìn)行輸入數(shù)據(jù)傳輸（即用戶間干擾可以忽略）。每個設(shè)備傳輸數(shù)據(jù)是獨(dú)立的，不受其他設(shè)備及ENs的干擾。則傳輸延遲如下：

其中，Mi表示Ti的輸入數(shù)據(jù)大小；γij(t)是Ti在第t個時隙中到Ej的信道功率增益；是傳輸功率；B是系統(tǒng)帶寬；N0是接收器處的噪聲功率譜密度。

3.2 效用函數(shù)和優(yōu)化問題

在匹配算法中，效用函數(shù)用于衡量Ts或ENs從任務(wù)分配中獲得的凈收益。根據(jù)Ej計(jì)算的Ti的效用定義如下：

其中，ri是Ti的滿意度，即Ti在指定的延遲容限內(nèi)的完成度；a是能源成本系數(shù)；λ表示ENs計(jì)算Ti時，Ti為每個CPU周期支付的單價(jià)。（總付款λCi與任務(wù)的大小Ci成比例）。

Ej完成Ti獲得的效用如下：

資源有限的設(shè)備在考慮設(shè)備和MEC服務(wù)器的計(jì)算能力、無線信道條件和延遲限制的同時，將Ts加載到附近的ENs。此時，問題被轉(zhuǎn)化為效用最大化問題，任務(wù)分配受延遲的約束。所有Ts和ENs在Sij上的總效用如下：

整體效用最大化問題即整體能耗最小化問題：

延遲約束能耗優(yōu)化問題定義如下：（1）保證每個Ts只分配給一個EN；（2）保證每個Ts按時完成；（3）保證每個Ts和EN的效用為正；（4）信噪比應(yīng)高于閾值，以保證成功傳輸（可靠傳輸約束）。

4 基于匹配理論的解決方法及性能分析

文章的任務(wù)分配算法是分布式的問題優(yōu)化算法，該算法由初始化階段和多次迭代組成。

4.1 初始化部分

為所有任務(wù)建立偏好列表。偏好是根據(jù)本地信息進(jìn)行評估的，本地信息被定義為一個效用函數(shù)，表示通過特定任務(wù)匹配所獲得的收益。效用函數(shù)如下：

公式（10）表示能夠?qū)i的輸入數(shù)據(jù)傳輸?shù)降腅Ns的一組可靠連接。

4.2 迭代部分

文章定義已匹配的任務(wù)集為Mmatch，未匹配的任務(wù)集為Munmatch。屬于Munmatch的Ti向在其偏好列表中排名第一的Ej發(fā)送請求且Ti宣布其計(jì)算要求。如果Ej未匹配并且滿足Ti的計(jì)算要求，則接受Ti的匹配請求，并將Ti從Munmatch中刪除，添加到Mmatch中。否則，Ti的請求將被拒絕。

如果Ek已與Ti匹配，但Ej能更好地滿足Ti的計(jì)算要求，則接受Ej，并將Ek從Mmatch中移除，添加到Munmatch，將Ej從Munmatch中移除，添加到Mmatch。否則，Ej的請求將被拒絕。

如果Ti不與任何ENs匹配，表示沒有ENs能夠滿足Ti的計(jì)算要求，則將Ti從Munmatch中刪除，直至Munmatch為空集。

4.3 穩(wěn)定性分析

匹配的關(guān)鍵在于結(jié)果是否穩(wěn)定。在任務(wù)分配系統(tǒng)中，匹配的穩(wěn)定性偏差是固定的，這使得任何一個匹配對都不會偏好先前的匹配結(jié)果。

引理：當(dāng)算法結(jié)束時，任務(wù)和邊緣節(jié)點(diǎn)的匹配是穩(wěn)定的。

證明：如果Ti和Ej都完成匹配（但并非Ti和Ej進(jìn)行了匹配）。算法完成后，Ti和Ej不能繼續(xù)匹配，如果Ti偏好Ej而非當(dāng)前匹配對象Ek，則Ti必定在與Ek完成匹配之前向Ej發(fā)出過匹配請求。如果Ej接受其匹配請求，但在算法結(jié)束時并未與Ti配對，則說明Ti因Ek更好而放棄與Ej匹配。

5 結(jié)語

文章提出了基于匹配理論的MEC系統(tǒng)任務(wù)分配機(jī)制，該任務(wù)分配機(jī)制是優(yōu)化驅(qū)動的，可以分布式執(zhí)行。文章在考慮到移動設(shè)備和MEC服務(wù)器的計(jì)算能力、無線信道條件和延遲約束的條件下，以最小化能耗為目標(biāo)，建立了任務(wù)分配問題，并提出了一種基于一對一匹配的算法，從理論上證明了該任務(wù)分配機(jī)制能夠使設(shè)備和MEC服務(wù)器之間保持穩(wěn)定的匹配，并且良好地平衡了計(jì)算復(fù)雜性和能耗。