王一然

（華北電力大學(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]。移動(dòng)邊緣計(jì)算（Mobile Edge Computing，MEC）被認(rèn)為是解決此問(wèn)題的有效方式，它將具有空閑資源的MEC服務(wù)器等各種設(shè)施當(dāng)作分布式邊緣，將計(jì)算任務(wù)加載到物理上靠近數(shù)據(jù)源的移動(dòng)邊緣，以顯著減少傳輸延遲[2]。

1 介紹

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

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

2 系統(tǒng)模型

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

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

3 問(wèn)題描述

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

3.1 時(shí)延問(wèn)題

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

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

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

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

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

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

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

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

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

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

整體效用最大化問(wèn)題即整體能耗最小化問(wèn)題：

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

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

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

4.1 初始化部分

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

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

4.2 迭代部分

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

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

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

4.3 穩(wěn)定性分析

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

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

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

5 結(jié)語(yǔ)

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