基于網絡模體的空閑計算資源捕獲算法

李麗庭， 朱 蓉， 林基明， 王俊義

(1.桂林電子科技大學 信息與通信學院,廣西 桂林 541004；2.桂林電子科技大學 廣西無線寬帶通信與信號處理重點實驗室,廣西 桂林 541004)

隨著無線通信技術和微處理器技術的發展，智能手機、平板電腦等移動設備急劇增加[1]，思科預測到2022年全球移動設備將超過120億臺[2]。然而，受物理尺寸以及電池技術限制，移動設備計算能力和電池容量有限，難以滿足像虛擬現實(VR)等新型應用的快響應、高能耗執行需求[3-4]。高可靠和低時延通信問題是近年來無線通信研究的難點和熱點[5]。設備到設備(device to device，簡稱D2D)技術的出現，使得設備可以直接在設備與設備間進行數據傳輸[6-7]，可減輕基站負載，有助于緩解網絡擁塞[8-9]，受到學術界和工業界的廣泛關注。然而，如何捕獲系統可用計算資源(即空閑終端)，減少云端負載至關重要。

目前，已經有很多學術工作致力于復雜網絡中信息的捕獲。為揭示復雜系統的結構屬性，文獻[10]提出網絡模體(network motif)的概念，即復雜網絡的互聯基元(網絡子圖)，其在網絡中出現的次數遠高于其他隨機網絡子圖，即網絡模體具有統計占優特性。目前，網絡模體的檢測、分析、統計等，已成為熱門研究[11-13]。

已有的網絡屬性研究主要針對網絡節點、鏈接關系或整個網絡的基本信息，如平均度[14]、聚類系數[15]、平均最短距離[16]、間度[17]等，缺乏對網絡模體結構測度量的分析。不同的網絡，節點的連接關系不同，其網絡模體結構也有顯著差異[18]。近年來，有少部分研究將復雜網絡與網絡模體結合，對復雜網絡的網絡模體結構測度量進行分析。文獻[19-21]主要針對生物網絡，研究DNA中網絡模體特點、方法、優缺點，并對網絡模體的檢測進行歸納。然而，上述文獻未考慮普通復雜網絡及網絡中不同節點的結構屬性。鑒于此，基于移動邊緣計算(mobile edge computing，簡稱MEC)網絡，考慮通信網絡的資源利用率低下問題[22]，將計算卸載與網絡模體結合，通過查找復雜網絡中模體，同時計算模體的Z得分，判斷模體在原網絡中的重要性，并結合KM算法，提出一種基于網絡模體的設備匹配資源搜索算法，以充分捕獲系統空閑計算資源，提高系統資源利用率，減少邊緣云端負載。最后，仿真結果表明，該算法能有效捕獲空閑計算資源，提高空閑資源利用率。

1 網絡模體概述

將網絡模體簡稱為模體，并對其定義、網絡架構特征進行描述。

1.1 模體定義及特征

1)模體定義。復雜網絡的互聯基元(網絡子圖)在網絡中出現的次數遠高于對應隨機網絡子圖[10]。給定一個網絡G={V,E}，節點個數|V|=N，則模體定義為一個二元組(B,A)，B為k×k模體鄰接矩陣，A?{1,2,…,k}為錨定節點。k-模體可表示為

(1)

其中：v為節點向量；χA(v)為選擇函數，表示從向量中取出錨定節點A；(v,χA(v))∈M(B,A)為模體實例。

2)模體特性。節點數量特征：模體是小型、緊湊的連接子圖結構，其大小介于網絡個體和社團之間，一般由少數幾個節點連接構成[23]。結構特征：模體可以用來描述社團內部成員之間的基本連接模式，能夠揭示大多數網絡的基礎信息結構和基本構成，對于一些特殊網絡而言，甚至可以認為該網絡是多種“模體”的擴展。統計特征：模體在實際網絡中出現的次數一般大于在隨機網絡中出現的次數，一般要求(nM-nrand)>0.1nrand。

1.2 基于模體的測度量

模體網絡的常用測度量包括模體頻率、模體Z分數及模體導率。

1)模體頻率。在統計上，模體具有統計占優特性，即模體在實際網絡中出現的頻率大于模體在對應隨機網絡中的頻率。給定子圖類型M，其在網絡出現的頻率為

(2)

其中，nM、nsub分別為子圖類型M和同節點數子圖在D2D通信網絡中出現的次數。若M為網絡的模體，則fM為模體頻率。

2)模體P值。對于模體M，為保證其統計占優特性，其在實際網絡中出現的次數應大于它在隨機網絡中出現的次數。文獻[24]給出模體存在的條件，即模體在隨機網絡中出現的次數大于在實際網絡中出現的次數的概率應小于一個閾值，定義此概率值為模體的P值。P值越小，說明該模體在網絡中越重要。P值用來證明子圖聯通類型是否可作為網絡模體。

3)模體Z分數。Z分數(Z-score)，也叫標準分數，其數學表達式為

(3)

考慮衡量模體在初始通信網絡中的地位，將Z分數引入模體網絡，分析模體類型在通信網絡中的重要性。模體的Z分數表示為

(4)

1.3 相關工作

根據模體測度量性質，當前與模體有關的研究主要從模體的查找、統計特性和結構特性上進行分析。

在模體的查找研究方面，文獻[25]總結了復雜網絡中的主題查找算法，并概述各策略的區別和優勢。文獻[26]基于網絡檢測并行性，提出一種分布式控制策略，在整個計算過程中提供動態負載平衡以實現模體檢測的近線性加速。在模體統計特征研究方面，模體的頻率或次數常作為衡量標準。文獻[27]計算了所有3節點模體的絕對頻率，并以此對網絡進行分類。文獻[28]基于模體在實際網絡和隨機網絡的出現頻率，采用Z-SCORE模型，提出一種快速、高效、并行的算法，加快模體的統計速度。文獻[24]驗證了復雜網絡中模體的存在性，并基于模體頂點度，通過引入模體邊度，分析模體在網絡中的重要性。在模體應用上，文獻[29]基于模體，提出了一種新的D2D網絡分析框架，研究了星形和鏈形2種模體對D2D網絡性能的影響，并確定有效的內容傳播策略，導出了模體的統計顯著性、中斷概率和設備平均吞吐量的封閉解析表達式。

基于上述文獻，通過對模體頻率、P值及Z分數進行分析，證明D2D網絡中模體的存在性，并結合KM算法對網絡空閑計算資源進行捕獲。

2 模體網絡構造及分析

2.1 D2D通信模型

支持D2D通信的單蜂窩網絡架構如圖1所示，主要包含基站、MEC服務器和設備集N。設備有2種狀態，分別為空閑狀態和工作狀態，工作設備可將計算任務卸載到空閑移動設備和MEC。

將通信網絡圖示化G={V,E}，其中，V={v}表示系統的所有設備和基站，E={e}為工作設備所有卸載鏈路，|V|表示設備和基站個數。

圖1將通信網映射到上方，其中綠色表示處于空閑狀態的移動設備，定義為Nidle(Nidle?N)，紅色為處于工作狀態的移動設備，定義為Nact(Nact?N)。工作設備允許在D2D最大傳輸范圍內向周邊空閑設備卸載計算任務。圖G是一個有向圖，邊的方向即數據卸載方向，如圖2所示。

圖1 支持D2D通信的蜂窩網絡

圖2 D2D通信網絡連接圖

針對D2D通信網絡，移動設備可通過D2D鏈路將計算或存儲需占用大量資源的應用卸載到鄰近設備，D2D傳輸速率為

Rij=Blog2(1+pitγij)。

(5)

實際上，設備距離越遠，D2D通信越不穩定，為了體現設備距離對用戶卸載質量的影響，以連接質量表示用戶進行D2D通信的好壞程度，鏈路傳輸質量定義為

(6)

其中：pij為鏈路中斷概率；dmax為D2D通信的最大距離，滿足dji=dij。

2.2 模體網絡構造

本質上，模體為網絡的局部連接模式。在D2D通信網絡中，局部移動設備之間的相互通信構成整個網絡的基本單元，使用模體作為新網絡的節點，一方面，模體內部的信號流動可以直觀映射整個網絡；另一方面，模體內部聚合度高，模體網絡能更直觀地表現出區域設備的聚合度。

圖3為有向圖的所有三節點模體類型，也就是說，在有向網絡拓撲中，3個節點之間可以形成13種不同的連通關系。模體節點越多，包含的信息量越大，其組成聯通關系也越復雜，四節點模體的聯通關系可達199種。

圖3 三節點模體類型

考慮移動設備的計算能力受限，為保證計算任務的正常執行，假設單個空閑移動設備只能處理設備卸載任務的一半，即Fidle=0.5Ftask。滿足要求的模體類型有M6、M8、M10、M12，如圖4所示。

圖4 D2D通信適用模體類型

M10類型模體適用于工作設備多于空閑設備且移動設備任務量較少，空閑設備計算資源足夠支持多個設備進行應用卸載的場景。M12模體類型對D2D通信鏈路要求較高，容易因AB鏈路中斷而卸載失敗。在M6、M8模體類型下，針對網絡突發情況，M6可通過空閑中繼將應用卸載到中斷設備?；诖?，考慮本移動設備計算資源受限及系統穩定性，選取M6對網絡進行分析。

不失一般性，采用全錨定節點，即對k-模體有A={1,2,…,k}。原網絡圖可轉化為一個有權無向的模體網絡圖Gm=(Vm,Em)。其中，|Vm|=N為圖Gm的節點集，Em為圖Gm的邊，從而定義模體鄰接矩陣WM，

(7)

其中，M表示模體類型，即每個矩陣元素表示同時包含節點i和節點j的模體個數，此時WM為雙向圖。

3 基于模體的空閑計算資源捕獲

基于D2D通信的計算卸載可以不經過基站直接進行數據交互，一方面降低了通信鏈路的堵塞，另一方面減少了云端計算資源的使用量。

考慮空閑移動設備的計算資源受限，空閑設備處理的任務量為0.5Ftask，其中Ftask為移動設備任務的計算量。結合通信鏈路的穩定性，假定在D2D通信鏈路中，設備i、j之間卸載中斷概率為pij，不失一般性，假設所有鏈路的中斷概率一致，中斷概率重寫為pout，此時，通信鏈路正常的概率為plink=1-pout。

基于M6模體類型對D2D網絡的空閑計算資源進行配置。令設備i為工作設備，j、k為空閑設備，且3個設備之間的距離滿足最大D2D通信距離，設備i向設備j、k卸載計算任務，若通信鏈路eij中斷，則設備i可以通過鏈路eik、ekj將任務卸載到設備j。因此，考慮鏈路的中斷概率，M6對應網絡結構中空閑移動設備處理的任務量可分為以下3種情況：

1)網絡鏈路均正常通信時，任務處理量為

(8)

2)只有2條鏈路正常通信，有一條D2D通信鏈路斷開時，處理任務量為

(9)

3)2條D2D通信鏈路斷開時，處理的任務量為

(10)

由式(8)～(10)可得到模體處理工作設備的卸載任務量

Fmoff=FTlink+FBlink+FSlink。

(11)

對于一對一連接的D2D設備對(一個空閑設備與一個工作設備連接)，其處理的任務量為

(12)

否則，空閑設備更愿意選擇最大的偏好鏈路進數據處理，即

(13)

(14)

通過衡量模體鏈路質量以及用戶的偏好，將模體與KM算法結合。當模體不存在時，考慮工作設備與空閑設備之間的通信，此時，采用KM算法對2種類型設備進行配對，工作設備與具體算法如下：

算法1基于模體的設備匹配資源搜索

輸入：D2D網絡鄰接矩陣和模體的鄰接矩陣B

輸出：計算資源捕獲S

1. 初始化捕獲計算資源S=0，去掉空閑設備對；

2. 利用式(6)計算鏈路質量矩陣LW；

3. 找到空閑設備與工作設備的一對一聯通對集合P，利用式(12)求出任務量S1，S=S+S1；

5. if |Cm≥1|

6. fori=1:|Cm|

8. if (Dout)v1(Dout)v2(Dout)v3

10. endif

11. endfor

12. else

13. 清除空閑設備之間的通信鏈路，構造二分圖；基于LW使用KM算法對設備進行配對，更新S；

14. 遍歷工作設備，將配置空閑設備大于1的工作設備鏈路清空，更新LW；

15. 計算網絡節點出度入度Din、Dout；

16. if max(Dout)>0

17. 轉到步驟2；

18. endif

19. endif

考慮D2D通信網絡中用戶卸載任務到空閑設備，同時單個空閑移動設備擁有的計算資源有限，無法滿足工作設備任務對計算資源的需求，同時考慮卸載中斷的可能性，選用M6模體類型構造模體網絡，2個空閑設備包含的計算資源較多，應充分考慮用戶的資源需求，以保證卸載的正常進行。

4 仿真結果及分析

為了驗證模體，對模體Z分數、模體個數及P值進行分析。將基于模體的設備匹配資源搜索算法與K-means聚類算法、隨機聚類算法及KM算法進行對比，凸顯本算法對系統空閑計算資源的捕獲能力，不失一般性，利用任務數衡量所捕獲的計算資源大小。

為了保證參數的合理性，將具體仿真參數設置如下：小區覆蓋半徑為500 m[30]；系統設備數量為100～500，且服從泊松點分布；D2D最大通信距離為50 m[30]；鏈路中斷概率pout=0.9[31]；模體P閾值取0.01[24]。

模體的P值通過對比模體在實際網絡和隨機網絡中的頻率，利用二者的概率對模體的存在性進行證明。表1為通信網絡和隨機網絡中M6、M8和M9模體類型出現的頻率及P值。從表1可看出，在D2D通信網絡中，M6和M8模體類型出現的頻率遠大于其在隨機網絡中出現的頻率。此外，2個類型模體的P值均為0，遠小于閾值0.01，M6和M8對應的聯通結構可作為D2D通信網絡的模體。然而，M9在隨機網絡中出現的頻率高于在通信網絡中的頻率，且P值為1，遠大于其閾值0.01，所以不能作為D2D通信網絡的模體。

表1 D2D通信網絡和隨機網絡中三角形模體類型出現的頻率和P值

不同模體類型在網絡中出現的次數及頻率均有所差異。圖5為隨機網絡和MEC網絡中模體個數與設備個數的關系變化曲線。從圖5可看出，M8和M6類型模體在實際MEC網絡出現次數均大于在隨機網絡中出現的次數，符合統計占優特性。

圖5 隨機網絡和通信網絡中模體次數

移動設備數量的增加使得模體數量也增加，但覆蓋區域內移動設備密集化程度的提高，也大大增加了設備信息交互的機會，使得對應同階子圖數量也增加，從而導致2個類型網絡模體的頻率下降，如圖6所示。

圖6 隨機網絡和通信網絡中模體次數

模體類型不同，其在網絡中的地位也不同，圖7為M8和M6類型模體的Z分數。從圖7可看出，M6的地位優于M8，且隨著設備數量的增加，模體的Z分數也增加，即大型網絡中的模體比小型網絡中的模體具有更高的Z分數。

利用D2D通信處理的任務大小衡量捕獲的計算資源?？臻e計算資源捕獲如圖8所示。從圖8可看出，基于模體的設備匹配資源捕獲算法優于其他3種算法。因為模體考慮了鏈路質量及中斷概率，在計算資源配置時，優先配置處理偏好系數高的設備，同時在完成模體配置后利用KM算法進行匹配，以提高捕獲資源量。

5 結束語

通過對當前關于模體研究文獻的介紹，匯總了支持D2D通信的蜂窩網絡中模體選取、檢測的一些技巧，包括在結構上和統計上進行測試。在結構上，對模體Z得分及導率等進行評價，以判斷選取的模體在原復雜網絡中的重要性，并證明模體具有統計占優特性。在計算資源發掘上，將KM算法與模體結合，在提高信息捕獲量的同時，抗干擾能力也優于傳統的配對方法。在接下來的研究中，將把模體與計算資源配置結合，研究模體網絡在多維云資源配置下的優越性。