移動邊緣計算中基于貢獻度激勵的端池化解決方案

陽 柳,章立群,林曉勇

(南京郵電大學 通信與信息工程學院,江蘇 南京 210003)

0 引 言

目前基于云計算(Cloud Computing,CC)[1]的研究日益成熟。云計算通過分布式計算技術,即將多臺計算機的處理能力組合在一起,形成一個虛擬的計算機,獲取超高計算力[2],此過程又稱為公共算力池[3-4](Public Computing Pool,PCP)。移動邊緣計算(Mobile Edge Computing,MEC)通過將服務器下沉至數據源一側為用戶提供計算和網絡等資源,具有更低的時延和能耗,以完成用戶的各種業務請求[5-7]。邊緣計算通過基站接收各用戶的計算任務,通過邊緣側服務器進行處理,以完成用戶的請求。

隨著技術的發展,終端節點上行鏈接接入基站,通過云計算和邊緣計算完成計算需求。當基站由于外界因素導致基站覆蓋范圍縮小,基站計算服務器受損,原本處在基站覆蓋范圍內的節點無法接入,計算任務無法滿足。終端設備都存在一定的計算能力,基于算力共享[4]和公共算力池化的理念,通過移動自組織網絡(Mobile Ad hoc Network,MANET)進行連接,利用自身可用計算力實現算力共享,此過程即為端池化(Terminal Pooling)。將端池化后的系統計算合力定義為算力池,端池化以算力池作為評判端池化優劣的標準,在基站無法應付大量計算任務的請求時參與計算。

終端節點的數量影響著系統算力池的大小,目前對MANET網絡的研究默認節點全都同意接入網絡參與通信[8-9],其忽略了節點的自私性。文中通過對節點采取激勵策略,提升節點的接入率,增強端計算網絡的算力池。由于終端節點自主通信范圍受限,通過分簇方式對終端節點進行管理[9-11],并選舉簇首節點作為中間節點與基站進行連接,得到算力池最大的分簇方法,不同簇的算力池大小不一,基站可根據算力池下發計算任務。簇首的選舉對簇中算力池也存在一定的影響,不同節點具有不同的連接度,作為簇首時組建的簇的特性也不一樣。

針對聚簇算法,目前大多數研究都是通過考慮多種因素,通過加權分簇算法選舉簇首[11-14]。文獻[14]提出一種考慮節點度、節點移動性、節點剩余能量和節點與鄰居節點距離和進行加權的方法,并通過帶寬確定簇中節點個數,以此提高網絡資源效率。該方法雖然考慮了各因素的影響,但忽略了每個因素影響的差異化,即使通過加權因子來平衡各因素的影響,沒有從根本上得到最佳的簇首節點。文獻[15]通過建立節點剩余能量和位置閾值模型選取簇頭及分簇,考慮了節點剩余能量和位置,能夠提高能耗效率和對網絡生命周期進行分簇,但該方案沒有考慮節點計算力對分簇的重要性。文獻[16]通過修改K-means算法,根據點與計算的質心的距離進行迭代聚類,直到得到一個穩定的質心,并選取最接近質心的D2D用戶作為該組的D2D的簇首,僅以距離作為簇首選舉因素,雖然能保證簇的穩定性,卻無法保證簇的計算能力。文獻[17]通過等角度分簇算法,通過基站到簇首節點的通信半徑,得到系統時延最低時的最佳簇首位置,以此選定簇首節點。該文獻并沒有考慮終端節點直接的通信距離,默認所有節點皆能接入簇中。

綜上所述,在已有的分簇方案中,大多都未考慮終端節點通信能力和終端的計算力對簇性能的影響?；诖?該文提出一種基于貢獻度激勵的端池化(Contribution Emulated Terminal Pooling,CETP)解決方案,重點研究如何提升終端節點的接入率和算力池最大化要求下的簇首選舉方式,聚成最佳的簇,通過端池化協助基站快速完成計算任務。

1 系統模型

處于基站覆蓋范圍內的節點定義為內部節點(Internal Nodes,INs),隨著基站覆蓋范圍縮小,基站覆蓋范圍外的內部節點定義為外圍節點(Peripheral Nodes,PNs),外圍節點通過MANET網絡與內部節點建立通信連接。設定所有PNs主動加入MANET網絡與INs建立通信關系,INs中存在自私節點,不愿與PNs通信。端池化過程中下發的計算任務分為兩個階段：第一階段為基站通過蜂窩網絡將計算任務傳遞給簇首;第二階段為簇首通過MANET網絡將計算任務傳遞給簇內節點,通過利用節點的剩余計算力進行端池化,實現計算力共享。

設定小區用戶隨機分布,外圍節點的數量為N,內部節點的數量為M,分別用集合A={1,2,…,n,…,N}和G={1,2,…,m,…,M}表示,INs的通信意愿定義為willingness,用集合W表示。系統模型如圖1所示。

圖1 CETP模型

2 端池化

端池化過程計算任務傳輸的第一階段,基站將計算任務傳遞給簇首,所需傳輸時延定義為tbs,ch,計算過程如公式1所示：

(1)

其中,C為計算任務的大小,Rbs,CH為基站到簇首的傳輸速率,可用香農公式表示,計算公式如公式2所示：

(2)

其中,B為基站總帶寬,K為簇的個數;Pbs為基站的發射功率,dCH為簇首到基站的物理距離;l為路徑損耗因子;n0為噪聲功率譜密度。

在端池化過程計算任務傳輸的第二階段,定義簇首(CH)與簇內節點之間的連接關系為v,當通信條件時,v=1,反之v=0。通信條件表示如公式3所示：

(3)

通信條件(a)表示簇內中IN節點m的通信意愿,當willingness大于通信意愿閾值wthreshold,表示節點愿意加入與簇首建立通信連接;通信條件(b)表示雙方節點的物理通信條件,當簇首與簇內節點之間的物理距離小于最大通信范圍r時,雙方能進行通信。

第二階段完成計算任務的傳輸和計算需要的時延為t2,如公式4所示：

(4)

其中,Numk為第k個簇中可通信的簇內節點;fi為簇內節點i的剩余計算力;φ為處理1 bit任務所需的CPU周期;RCH,i為簇首與簇內節點的傳輸速率,計算過程如公式5所示：

(5)

其中,Bk為第k個簇內節點可用帶寬;Pt為簇首的發射功率;dCH,i為簇內節點i與簇首的距離;vCH,i為簇內節點(CH)與簇首的連接關系。

端池化過程完成計算任務C所需花費的總時延包括計算時延和傳輸時延,計算時延受限于最小節點計算力,傳輸時延受限于最差節點信道質量,因此總時延為傳輸時延和計算時延和的最大值。定義總時延為T,計算過程如公式6所示：

(6)

算力池為一個簇的可用計算力的合力大小,即一個簇綜合處理單位計算任務的能力。第k個簇的算力池Fk為所需完成的計算任務大小與所花費時延的比值,計算過程如公式7所示：

(7)

基站與簇首之間的傳輸時延忽略不計,系統總合力(FF)定義為各簇算力池之和,計算過程如公式8所示：

(8)

基于上述分析,可以得到以系統整體算力池最大為優化目標,對端池化過程的用戶進行分簇,得到時延優化下分簇的個數以及簇首接入的節點數。以系統整體算力池最大為優化目標可以化作求以系統時延最小為優化目標,計算過程如公式9所示：

(9)

其中,C1是對簇內接入節點的約束,接入節點不能超過簇中節點個數Sm;C2是對整個系統的簇內接入節點的約束,接入節點不能超過系統內節點個數;C3是簇內節點帶寬約束,信道帶寬不能超過最大可接入帶寬Bmax;C4是簇內的總帶寬約束,簇內帶寬和不能超過簇中總帶寬BCH;C5是系統帶寬約束,各簇帶寬和不能超過系統總帶寬B。

3 激勵策略

由公式6可知,接入的Numk影響算力池大小。為了提升INs的連接意愿,提出將貢獻度激勵INs與外圍節點進行連接,以此增加通信的PNs數,從而增加Numk。PNs根據以往作為INs時,成功連接的次數Ks與被申請連接的次數S的比定義為節點的貢獻度,表示為Con,如公式10所示：

(10)

系統平均貢獻度如公式11所示：

(11)

當PN節點n所申請連接的IN節點m滿足通信條件(b)時,不滿足條件(a)時,判斷該PN節點的貢獻度與系統平均貢獻度的關系,若大于等于系統平均貢獻度,則將該意愿連接節點m的連接意愿進行提升,再判雙方是否滿足通信條件(a),最后得到INs的連接數以及PNs的接入數。意愿激勵公式如下：

(12)

配對策略流程如圖2所示。

圖2 激勵策略流程

4 聚簇算法

文中聚簇算法基于k-means算法將系統節點分割為K個簇,簇中包括內部節點和外圍節點,內部節點可以根據意愿選擇是否加入該簇,通過對比入簇的內部節點作為簇首時簇的算力池大小,選出算力池最大時具體簇的分布。根據公式6和公式7可知,在信道帶寬和計算任務相同的情況下,算力池的大小受限于簇中接入數,簇的個數和信道質量,信道質量主要受兩點之間的距離影響。

具體算法步驟如下：

輸入：B,Bk,Pbs,Pt,C,l,n0,N,M,r,R,Kmax

輸出：vij,Numk,K,FF

步驟1：初始化相關參數,得到系統所有節點橫坐標X,縱坐標Y;內部節點橫坐標X_n和縱坐標Y_n,內部節點意愿willingness;外圍節點橫坐標X_p和縱坐標Y_p;

步驟2：fork←K_min toK_max do

步驟3： 通過K-means分簇得到初始簇Cluster1;

步驟4：Fori←1 to Numkdo

步驟5：Forj←1 to Numkdo

步驟6：Ifi～=j

步驟7：計算各簇中的節點距離;

步驟8：保存各點滿足通信的節點坐標;

步驟9：Endif

步驟10：Endfor

步驟11：Endfor

步驟12：W_k←滿足通信條件(a)的簇中內部節點集合,個數為Numk_1;

步驟13：保存與簇中內部節點滿足簇中通信條件的節點,連接關系為vij;

步驟14：Fori←1 to Numk_1 do

步驟15：根據公式7計算得到每個內部節點作為簇首的算力池F(i);

步驟16：選舉各簇中算力池最大的簇中內部節點作為簇首,保存其F值作為Fk,并保存該情況下的簇內個數Numk;

步驟17：根據公式8得到系統中總算力池;

步驟18：Endfor

步驟19：得到系統合力最大的分簇個數K,系統合力為FF

5 仿真結果及分析

本節詳細分析了激勵策略下,研究在不同計算任務和小區內節點數的情況下,不同簇首選舉算法對系統總時延的影響。為了評估文中算法的性能,將文獻[17]的等角度分簇算法作為對比算法1,加權分簇算法作為對比算法2,對比算法2中影響因素為節點計算力、節點連接度以及節點與簇首的距離和。

對比算法1通過等角度分簇,限制了節點根據性能選擇簇的權利,不能保證簇中節點加入最佳簇;對比算法2通過考慮不同的影響因素進行加權,在一定程度上保證了所分簇的性能,但權值最佳的簇首所聚的簇不一定是最佳性能簇,因此所分簇的性能存在不穩定性。文中算法是確定所分簇的最佳性來反向選舉簇首,并通過端池化來確定系統的計算能力,以最短時延完成計算任務。

該文所采用的仿真參數如表1所示。

表1 系統仿真參數設置

當用戶數為300時,在節點接入的激勵策略對比下,不同算法下的用戶接入率隨計算任務的變化情況如圖3所示。由于組網過程存在自私節點,因此理論下的最大接入率無法到達100%。對比算法1是通過等角度的分簇方式,限制了簇首節點選擇簇中節點,無法最大限度接入滿足通信條件節點,因此接入率最低;對比算法2雖然在一定程度上考慮了簇首節點的接入率,但在加權的影響下,需要綜合考慮計算力與節點度的影響程度,無法確定能選出最大接入度的簇首,因此在接入率上低于文中算法;文中算法是基于算力池最大情況下進行聚簇,而簇中節點數影響著算力池的大小,因此文中算法充分考慮節點接入情況,但簇首節點的通信范圍受限,無法達到理論最大值。仿真結果表明,相比其他幾種算法,文中算法能夠得到最大節點接入率。

圖3 接入率與計算任務的關系

當用戶數為300時,在節點接入的激勵策略對比下,不同算法下的系統時延隨計算任務的變化趨勢如圖4所示。隨著計算任務的增大,各種算法時延都有明顯的增加。對比算法1通過等角度分簇,節點隨機分布,無法保證每次分簇的穩定性,總體計算力無法保證;對比算法2通過加權多個因素選舉簇首,在一定程度上保證了簇的性能,但簇首權值最大不代表整個簇的性能最強。由圖3可知,文中算法的節點接入率對比其他兩種算法更高,因此系統算力池更大,完成計算任務所花費的時延也更低。仿真結果表明,相比其他幾種算法,文中算法能夠獲得最低的時延。

圖4 系統總時延與計算任務的關系

當計算任務為103bit時,不同算法下的用戶接入率隨用戶數的變化情況如圖5所示。小區覆蓋范圍不變的情況下,當用戶數增加時,單位范圍內的用戶密度會增加,各算法中的簇首所能接入的用戶數也會增加,接入端計算網絡的節點越多,用戶數的增加并不影響接入率的變化,但數量越多,接入率越穩定。

圖5 接入率與用戶數的關系

當計算任務為103bit時,在節點接入的激勵策略對比下,不同算法下的系統時延隨用戶數的變化趨勢如圖6所示。小區用戶數越多,接入端計算網絡的節點數越大,因此各節點所分配的計算任務越小,但隨著用戶密度增加,算力池受到簇中最差信道和節點最小計算力的約束,最后在用戶數為8 000時趨于穩定。仿真結果表明,相比其他幾種算法,CETP方案能夠獲得最低的時延。

圖6 系統總時延與用戶數的關系

6 結束語

該文綜合了云計算和移動邊緣計算技術,在特定的場景下,提出了移動智能終端構建端池化過程的CETP解決方案,并對不同貢獻度大小的端節點進行分類,由MANET技術構建通信分簇,根據算力池最大化來選舉簇首,通過貢獻度激勵獲取更大的用戶接入,最終評估出CETP可獲得各種算力池方案結果。仿真結果表明,CETP方案可獲得90%以上的接入率,50%以上的參與率,較低的系統時延,以及不同用戶數變化下相對穩定的計算時延特性。CETP方案為運營商在霧計算領域中提供了新的算力池化解決思路。