基于匹配理論的電力物聯網邊緣服務器選擇機制

王一然

（華北電力大學，北京 102200）

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

1 介紹

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

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

2 系統模型

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

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

3 問題描述

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

3.1 時延問題

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

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

其中，Ci表示成功執行Ti所需的CPU周期數。

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

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

3.2 效用函數和優化問題

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

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

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

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

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

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

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

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

4.1 初始化部分

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

公式（10）表示能夠將Ti的輸入數據傳輸到的ENs的一組可靠連接。

4.2 迭代部分

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

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

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

4.3 穩定性分析

匹配的關鍵在于結果是否穩定。在任務分配系統中，匹配的穩定性偏差是固定的，這使得任何一個匹配對都不會偏好先前的匹配結果。

引理：當算法結束時，任務和邊緣節點的匹配是穩定的。

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

5 結語

文章提出了基于匹配理論的MEC系統任務分配機制，該任務分配機制是優化驅動的，可以分布式執行。文章在考慮到移動設備和MEC服務器的計算能力、無線信道條件和延遲約束的條件下，以最小化能耗為目標，建立了任務分配問題，并提出了一種基于一對一匹配的算法，從理論上證明了該任務分配機制能夠使設備和MEC服務器之間保持穩定的匹配，并且良好地平衡了計算復雜性和能耗。