移動(dòng)邊緣計(jì)算中基于貢獻(xiàn)度激勵(lì)的端池化解決方案

陽 柳,章立群,林曉勇

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

0 引 言

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

隨著技術(shù)的發(fā)展,終端節(jié)點(diǎn)上行鏈接接入基站,通過云計(jì)算和邊緣計(jì)算完成計(jì)算需求。當(dāng)基站由于外界因素導(dǎo)致基站覆蓋范圍縮小,基站計(jì)算服務(wù)器受損,原本處在基站覆蓋范圍內(nèi)的節(jié)點(diǎn)無法接入,計(jì)算任務(wù)無法滿足。終端設(shè)備都存在一定的計(jì)算能力,基于算力共享[4]和公共算力池化的理念,通過移動(dòng)自組織網(wǎng)絡(luò)(Mobile Ad hoc Network,MANET)進(jìn)行連接,利用自身可用計(jì)算力實(shí)現(xiàn)算力共享,此過程即為端池化(Terminal Pooling)。將端池化后的系統(tǒng)計(jì)算合力定義為算力池,端池化以算力池作為評(píng)判端池化優(yōu)劣的標(biāo)準(zhǔn),在基站無法應(yīng)付大量計(jì)算任務(wù)的請(qǐng)求時(shí)參與計(jì)算。

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

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

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

1 系統(tǒng)模型

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

設(shè)定小區(qū)用戶隨機(jī)分布,外圍節(jié)點(diǎn)的數(shù)量為N,內(nèi)部節(jié)點(diǎn)的數(shù)量為M,分別用集合A={1,2,…,n,…,N}和G={1,2,…,m,…,M}表示,INs的通信意愿定義為willingness,用集合W表示。系統(tǒng)模型如圖1所示。

圖1 CETP模型

2 端池化

端池化過程計(jì)算任務(wù)傳輸?shù)牡谝浑A段,基站將計(jì)算任務(wù)傳遞給簇首,所需傳輸時(shí)延定義為tbs,ch,計(jì)算過程如公式1所示：

(1)

其中,C為計(jì)算任務(wù)的大小,Rbs,CH為基站到簇首的傳輸速率,可用香農(nóng)公式表示,計(jì)算公式如公式2所示：

(2)

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

在端池化過程計(jì)算任務(wù)傳輸?shù)牡诙A段,定義簇首(CH)與簇內(nèi)節(jié)點(diǎn)之間的連接關(guān)系為v,當(dāng)通信條件時(shí),v=1,反之v=0。通信條件表示如公式3所示：

(3)

通信條件(a)表示簇內(nèi)中IN節(jié)點(diǎn)m的通信意愿,當(dāng)willingness大于通信意愿閾值wthreshold,表示節(jié)點(diǎn)愿意加入與簇首建立通信連接;通信條件(b)表示雙方節(jié)點(diǎn)的物理通信條件,當(dāng)簇首與簇內(nèi)節(jié)點(diǎn)之間的物理距離小于最大通信范圍r時(shí),雙方能進(jìn)行通信。

第二階段完成計(jì)算任務(wù)的傳輸和計(jì)算需要的時(shí)延為t2,如公式4所示：

(4)

其中,Numk為第k個(gè)簇中可通信的簇內(nèi)節(jié)點(diǎn);fi為簇內(nèi)節(jié)點(diǎn)i的剩余計(jì)算力;φ為處理1 bit任務(wù)所需的CPU周期;RCH,i為簇首與簇內(nèi)節(jié)點(diǎn)的傳輸速率,計(jì)算過程如公式5所示：

(5)

其中,Bk為第k個(gè)簇內(nèi)節(jié)點(diǎn)可用帶寬;Pt為簇首的發(fā)射功率;dCH,i為簇內(nèi)節(jié)點(diǎn)i與簇首的距離;vCH,i為簇內(nèi)節(jié)點(diǎn)(CH)與簇首的連接關(guān)系。

端池化過程完成計(jì)算任務(wù)C所需花費(fèi)的總時(shí)延包括計(jì)算時(shí)延和傳輸時(shí)延,計(jì)算時(shí)延受限于最小節(jié)點(diǎn)計(jì)算力,傳輸時(shí)延受限于最差節(jié)點(diǎn)信道質(zhì)量,因此總時(shí)延為傳輸時(shí)延和計(jì)算時(shí)延和的最大值。定義總時(shí)延為T,計(jì)算過程如公式6所示：

(6)

算力池為一個(gè)簇的可用計(jì)算力的合力大小,即一個(gè)簇綜合處理單位計(jì)算任務(wù)的能力。第k個(gè)簇的算力池Fk為所需完成的計(jì)算任務(wù)大小與所花費(fèi)時(shí)延的比值,計(jì)算過程如公式7所示：

(7)

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

(8)

基于上述分析,可以得到以系統(tǒng)整體算力池最大為優(yōu)化目標(biāo),對(duì)端池化過程的用戶進(jìn)行分簇,得到時(shí)延優(yōu)化下分簇的個(gè)數(shù)以及簇首接入的節(jié)點(diǎn)數(shù)。以系統(tǒng)整體算力池最大為優(yōu)化目標(biāo)可以化作求以系統(tǒng)時(shí)延最小為優(yōu)化目標(biāo),計(jì)算過程如公式9所示：

(9)

其中,C1是對(duì)簇內(nèi)接入節(jié)點(diǎn)的約束,接入節(jié)點(diǎn)不能超過簇中節(jié)點(diǎn)個(gè)數(shù)Sm;C2是對(duì)整個(gè)系統(tǒng)的簇內(nèi)接入節(jié)點(diǎn)的約束,接入節(jié)點(diǎn)不能超過系統(tǒng)內(nèi)節(jié)點(diǎn)個(gè)數(shù);C3是簇內(nèi)節(jié)點(diǎn)帶寬約束,信道帶寬不能超過最大可接入帶寬Bmax;C4是簇內(nèi)的總帶寬約束,簇內(nèi)帶寬和不能超過簇中總帶寬BCH;C5是系統(tǒng)帶寬約束,各簇帶寬和不能超過系統(tǒng)總帶寬B。

3 激勵(lì)策略

由公式6可知,接入的Numk影響算力池大小。為了提升INs的連接意愿,提出將貢獻(xiàn)度激勵(lì)I(lǐng)Ns與外圍節(jié)點(diǎn)進(jìn)行連接,以此增加通信的PNs數(shù),從而增加Numk。PNs根據(jù)以往作為INs時(shí),成功連接的次數(shù)Ks與被申請(qǐng)連接的次數(shù)S的比定義為節(jié)點(diǎn)的貢獻(xiàn)度,表示為Con,如公式10所示：

(10)

系統(tǒng)平均貢獻(xiàn)度如公式11所示：

(11)

當(dāng)PN節(jié)點(diǎn)n所申請(qǐng)連接的IN節(jié)點(diǎn)m滿足通信條件(b)時(shí),不滿足條件(a)時(shí),判斷該P(yáng)N節(jié)點(diǎn)的貢獻(xiàn)度與系統(tǒng)平均貢獻(xiàn)度的關(guān)系,若大于等于系統(tǒng)平均貢獻(xiàn)度,則將該意愿連接節(jié)點(diǎn)m的連接意愿進(jìn)行提升,再判雙方是否滿足通信條件(a),最后得到INs的連接數(shù)以及PNs的接入數(shù)。意愿激勵(lì)公式如下：

(12)

配對(duì)策略流程如圖2所示。

圖2 激勵(lì)策略流程

4 聚簇算法

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

具體算法步驟如下：

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

輸出：vij,Numk,K,FF

步驟1：初始化相關(guān)參數(shù),得到系統(tǒng)所有節(jié)點(diǎn)橫坐標(biāo)X,縱坐標(biāo)Y;內(nèi)部節(jié)點(diǎn)橫坐標(biāo)X_n和縱坐標(biāo)Y_n,內(nèi)部節(jié)點(diǎn)意愿willingness;外圍節(jié)點(diǎn)橫坐標(biāo)X_p和縱坐標(biāo)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：計(jì)算各簇中的節(jié)點(diǎn)距離;

步驟8：保存各點(diǎn)滿足通信的節(jié)點(diǎn)坐標(biāo);

步驟9：Endif

步驟10：Endfor

步驟11：Endfor

步驟12：W_k←滿足通信條件(a)的簇中內(nèi)部節(jié)點(diǎn)集合,個(gè)數(shù)為Numk_1;

步驟13：保存與簇中內(nèi)部節(jié)點(diǎn)滿足簇中通信條件的節(jié)點(diǎn),連接關(guān)系為vij;

步驟14：Fori←1 to Numk_1 do

步驟15：根據(jù)公式7計(jì)算得到每個(gè)內(nèi)部節(jié)點(diǎn)作為簇首的算力池F(i);

步驟16：選舉各簇中算力池最大的簇中內(nèi)部節(jié)點(diǎn)作為簇首,保存其F值作為Fk,并保存該情況下的簇內(nèi)個(gè)數(shù)Numk;

步驟17：根據(jù)公式8得到系統(tǒng)中總算力池;

步驟18：Endfor

步驟19：得到系統(tǒng)合力最大的分簇個(gè)數(shù)K,系統(tǒng)合力為FF

5 仿真結(jié)果及分析

本節(jié)詳細(xì)分析了激勵(lì)策略下,研究在不同計(jì)算任務(wù)和小區(qū)內(nèi)節(jié)點(diǎn)數(shù)的情況下,不同簇首選舉算法對(duì)系統(tǒng)總時(shí)延的影響。為了評(píng)估文中算法的性能,將文獻(xiàn)[17]的等角度分簇算法作為對(duì)比算法1,加權(quán)分簇算法作為對(duì)比算法2,對(duì)比算法2中影響因素為節(jié)點(diǎn)計(jì)算力、節(jié)點(diǎn)連接度以及節(jié)點(diǎn)與簇首的距離和。

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

該文所采用的仿真參數(shù)如表1所示。

表1 系統(tǒng)仿真參數(shù)設(shè)置

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

圖3 接入率與計(jì)算任務(wù)的關(guān)系

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

圖4 系統(tǒng)總時(shí)延與計(jì)算任務(wù)的關(guān)系

當(dāng)計(jì)算任務(wù)為103bit時(shí),不同算法下的用戶接入率隨用戶數(shù)的變化情況如圖5所示。小區(qū)覆蓋范圍不變的情況下,當(dāng)用戶數(shù)增加時(shí),單位范圍內(nèi)的用戶密度會(huì)增加,各算法中的簇首所能接入的用戶數(shù)也會(huì)增加,接入端計(jì)算網(wǎng)絡(luò)的節(jié)點(diǎn)越多,用戶數(shù)的增加并不影響接入率的變化,但數(shù)量越多,接入率越穩(wěn)定。

圖5 接入率與用戶數(shù)的關(guān)系

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

圖6 系統(tǒng)總時(shí)延與用戶數(shù)的關(guān)系

6 結(jié)束語

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