霧計算網(wǎng)絡(luò)中計算節(jié)點的最優(yōu)布局*

李炫鋒，羅喜良

(1 上?？萍即髮W(xué)信息科學(xué)與技術(shù)學(xué)院，上海 201210；2 中國科學(xué)院上海微系統(tǒng)與信息技術(shù)研究所，上海 200050；3 中國科學(xué)院大學(xué)，北京 100049)(2020年3月26日收稿；2020年5月5日收修改稿)

近年來，物聯(lián)網(wǎng)(internet of things，IoT)的廣泛應(yīng)用和快速發(fā)展促進了霧計算(fog computing)網(wǎng)絡(luò)的技術(shù)研究[1]。通常認為物聯(lián)網(wǎng)中的用戶設(shè)備資源(如計算能力、能量等)有限，難以完成對處理時延要求較高的任務(wù)，而霧計算賦能網(wǎng)絡(luò)是克服這一難題的一種非常具有前景的方法。在啟用霧計算能力的物聯(lián)網(wǎng)網(wǎng)絡(luò)中，任務(wù)節(jié)點(task node，TN)可以選擇將到達的任務(wù)卸載到附近的計算節(jié)點(computing node，CN)進行協(xié)同計算。通過共享霧賦能網(wǎng)絡(luò)中的計算資源，可以大大減少網(wǎng)絡(luò)的任務(wù)處理整體的時延。

目前針對霧計算網(wǎng)絡(luò)中任務(wù)卸載問題的研究已有很多方面的工作[2-4]。假設(shè)任務(wù)卸載場景中的系統(tǒng)參數(shù)(如CPU頻率和數(shù)據(jù)傳輸速率)全部已知的情況下，任務(wù)卸載問題可以通過轉(zhuǎn)化為一個確定性的優(yōu)化問題，并進行求解?？紤]更加復(fù)雜的任務(wù)卸載場景，為了應(yīng)對節(jié)點或用戶端配有實時狀態(tài)任務(wù)隊列池的情況，任務(wù)卸載問題可以轉(zhuǎn)化為隨機優(yōu)化問題，繼而利用李雅普諾夫(Lyapunov)優(yōu)化方法來解決[5-7]。而當(dāng)系統(tǒng)參數(shù)(如任務(wù)達到率或節(jié)點移動路徑等)部分未知的時候，原始問題可以轉(zhuǎn)化為多臂老虎機問題，在這種情況下，系統(tǒng)算法需在每一步迭代更新中，在嘗試探索學(xué)習(xí)新的系統(tǒng)參數(shù)還是直接利用已知的經(jīng)驗得出的最優(yōu)卸載策略這兩種選擇之間進行權(quán)衡[8-9]。

以上提到的這些工作都基于一個前提，即協(xié)助任務(wù)處理的計算節(jié)點的位置是固定的。在實際應(yīng)用中，只有當(dāng)任務(wù)節(jié)點處于計算節(jié)點的通信覆蓋范圍內(nèi)時，計算節(jié)點才能夠向任務(wù)節(jié)點提供計算服務(wù)。而每一個計算節(jié)點當(dāng)前時刻可用的計算資源的總量也限制了它所能夠提供服務(wù)的任務(wù)節(jié)點的數(shù)量。因此，計算節(jié)點在目標區(qū)域內(nèi)的位置布局直接影響該區(qū)域霧賦能網(wǎng)絡(luò)的任務(wù)卸載性能，其中包括無線通信覆蓋范圍和總?cè)蝿?wù)處理時延。而針對具有多個任務(wù)節(jié)點的某片區(qū)域中的計算節(jié)點布局問題的研究文獻目前很少。相似的工作包括如何對通信基站進行布局[10-12]，然而這些工作僅考慮了通信網(wǎng)絡(luò)中的無線通信覆蓋問題，并沒有考慮任務(wù)卸載的場景。為了減少系統(tǒng)總的任務(wù)處理等待時延，Maiti等[13]設(shè)計了一種改進的K均值聚類算法，得到計算節(jié)點的位置選擇。但是在該工作設(shè)置的場景中，由于計算節(jié)點需要設(shè)立在已有的網(wǎng)關(guān)之上，即為一部分網(wǎng)關(guān)增加任務(wù)處理的功能，因此計算節(jié)點放置的候選位置受到限制。同時，文中選擇任意2個網(wǎng)關(guān)之間的距離作為聚類度量，當(dāng)不同的任務(wù)節(jié)點具有不同數(shù)量的計算任務(wù)需求時，該方法找到計算節(jié)點的位置布局并不是最優(yōu)的[13]。

在霧計算網(wǎng)絡(luò)中任務(wù)卸載問題的研究中，先前很少有工作研究如何實現(xiàn)計算節(jié)點的最優(yōu)布局，本文將詳細探討這個問題。本文貢獻總結(jié)如下。首先，假設(shè)任務(wù)節(jié)點的位置和任務(wù)到達率是已知的，而計算節(jié)點是邊緣計算節(jié)點[14]，并且可以在目標區(qū)域中任意布局。基于該假設(shè)，將該問題建模為計算節(jié)點的p中心問題。接著，對傳統(tǒng)K均值在該情境下的應(yīng)用進行探究。由于K均值算法對初始值敏感，進一步提出一種基于凸包的啟發(fā)式算法，找到可支持任務(wù)節(jié)點通信和計算要求的最少計算節(jié)點數(shù)量和相應(yīng)布局位置。

1 系統(tǒng)模型

1.1 網(wǎng)絡(luò)模型

圖1 具有多個任務(wù)節(jié)點的霧計算網(wǎng)絡(luò)

考慮到當(dāng)需要大量的算力且通信量相對較小時，選擇將任務(wù)進行卸載處理可以有效提升系統(tǒng)性能[17]。因此，假設(shè)任務(wù)節(jié)點生成的任務(wù)需要很大的算力，必須卸載到計算節(jié)點進行計算，并且數(shù)據(jù)傳輸造成的延時與計算節(jié)點處的任務(wù)處理延時相比可以忽略不計。本文只關(guān)注任務(wù)在計算節(jié)點上的任務(wù)處理時延。

1.2 問題建模

在本文中，考慮盡可能降低計算節(jié)點布局成本，因此優(yōu)化目標是令布局的計算節(jié)點數(shù)量N最小。為了確保任務(wù)處理的服務(wù)質(zhì)量(quality of service，QoS)，每個計算節(jié)點的任務(wù)處理時延應(yīng)小于τmax。同時每個任務(wù)節(jié)點至少處于一個計算節(jié)點的無線覆蓋范圍內(nèi)。因此，計算節(jié)點的最優(yōu)布局可以建模為以下的優(yōu)化問題：

(1)

式中：μ為計算節(jié)點的服務(wù)速率，表示單位時間內(nèi)計算節(jié)點能夠處理的平均任務(wù)數(shù)量；λk是第k個任務(wù)節(jié)點的到達率，表示單位時間內(nèi)需要卸載處理的平均任務(wù)數(shù)量。約束1以及約束2確保已布局的計算節(jié)點覆蓋所有任務(wù)節(jié)點。約束3表示的是任務(wù)處理延遲，它保證了任務(wù)卸載的QoS。

解決上述問題有2個困難。首先，這是一個p中心問題，而這是NP難的[11]。同時傳統(tǒng)的求解算法在此并不適用，這是因為某些計算節(jié)點可能會不滿足平均任務(wù)處理時延的約束條件。另外，考慮到在實際應(yīng)用場景中任務(wù)節(jié)點的數(shù)量較多，因此需要一個低復(fù)雜度的高效算法。

在介紹算法前，首先在命題1中給出在我們的問題當(dāng)中需要布局的計算節(jié)點數(shù)量的一個下界。

(2)

證明對于第1個不等號，在最壞的情況下，每個計算節(jié)點只能服務(wù)到一個任務(wù)節(jié)點，因此有N≤K。

對于第2個不等號，我們考慮所有任務(wù)節(jié)點都集中分布在一個計算節(jié)點的通信覆蓋范圍內(nèi)的情況。由于需要N個計算節(jié)點來滿足任務(wù)卸載的QoS，由問題(1)中的第3個約束可得

(3)

將N個不等式加和，得

(4)

又因1/(μ-λmax)≤τmax，進一步有

(5)

證畢。

接下來，首先對傳統(tǒng)K均值如何應(yīng)用在該場景作了探究，給出改進的二分K均值聚類算法。進一步地，將致力于找到一種高效的螺旋計算節(jié)點布局算法來解決問題(1)。

2 計算節(jié)點布局算法

2.1 二分K均值聚類算法

作為對K均值聚類算法的一種改進版本，二分K均值聚類可看作是一種層次聚類方法[18]。二分K均值聚類首先將所有未被聚類的點視為一個大類，然后使用傳統(tǒng)K均值將不滿足度量值要求的類進一步分為2個較小的類，重復(fù)上述步驟直到計算節(jié)點的數(shù)量等于給定數(shù)量N。

具體到我們的問題中，首先使用傳統(tǒng)K均值反復(fù)進行二分操作，采用“是否滿足約束條件”作為對當(dāng)前類的度量，即當(dāng)滿足約束條件時，當(dāng)前類不需要進一步劃分，反之則需要繼續(xù)使用傳統(tǒng)K均值進行二分類。由于傳統(tǒng)K均值計算得到的聚類中心并不一定滿足要求，同時也為了確保傳統(tǒng)K均值聚類中的任務(wù)節(jié)點能夠盡可能多地被部署的計算節(jié)點覆蓋，需要對聚類中心進一步調(diào)整，即求解聚類n形成的最小覆蓋圓問題[19]，并更新計算節(jié)點n的部署位置。最小覆蓋圓問題可以轉(zhuǎn)化為以下形式：

(6)

定義一個變量sn作為指示變量，來確定當(dāng)前劃分得到的聚類n是否滿足約束條件，為

(7)

如果sn=0，聚類n滿足約束。若sn=1，即當(dāng)?shù)玫降木垲恘不滿足約束條件時，表示需要繼續(xù)對其進行二分操作。將會被進一步劃分的所選簇由

(8)

給出。

與傳統(tǒng)K均值算法相比，二分K均值聚類算法針對該場景進行了優(yōu)化，無需預(yù)設(shè)最小數(shù)量的聚類即可確保其收斂性。二分K均值聚類算法具體流程見算法1。

算法1MBKC(modified bisectingK-means clustering)布局算法

步驟2求解問題(6)，并計算第1個計算節(jié)點的位置和最小覆蓋圓半徑；

步驟6根據(jù)式(6)和式(7)更新參數(shù)fi,fn和si,sn；

由于二分K均值算法中的傳統(tǒng)K均值聚類對初始值敏感，為克服這個缺點，在下一節(jié)提供一種螺旋式布局的方法。

2.2 螺旋計算節(jié)點布局算法

受文獻[11]的啟發(fā)，我們以螺旋部署方式解決計算節(jié)點的布局問題。該算法遵循2個原則：第一，保證優(yōu)先覆蓋目標區(qū)域邊界的任務(wù)節(jié)點；第二，以螺旋推進的方式沿著邊界進行部署。

(9)

算法2SCNP(spiral computing node placement)算法

步驟10沿逆時針方向更新k0，n=n+1；

如圖2所示，算法從計算節(jié)點CN-1到CN-19由外向內(nèi)依次逆時針連續(xù)螺旋部署，計算節(jié)點布局的軌跡構(gòu)成一個螺旋曲線。

圖2 SCNP算法示例

2.3 復(fù)雜度分析

接下來，給出兩種算法對應(yīng)的時間復(fù)雜度。

MBKC算法對于二維歐幾里德空間中的K均值聚類算法[20]，其時間復(fù)雜度為O(KNI)，其中K,N,I分別表示任務(wù)節(jié)點數(shù)量、計算節(jié)點數(shù)量和算法收斂迭代次數(shù)。解最小覆蓋圓問題時間復(fù)雜度為O(K′)[19]，其中K′是被覆蓋的任務(wù)節(jié)點數(shù)量，且有K′≤K。因此算法總時間復(fù)雜度為O(K2NI)，上界為O(K3I)。

3 仿真實驗分析

本節(jié)將提供數(shù)值仿真實驗結(jié)果測試本文所提出的計算節(jié)點布局算法的性能。

假設(shè)需要進行布局的物聯(lián)網(wǎng)區(qū)域為半徑5 km的圓形，在沒有特殊指出的情況下，根據(jù)文獻[15]，仿真參數(shù)設(shè)定為，任務(wù)節(jié)點在目標區(qū)域內(nèi)隨機均勻分布，其任務(wù)到達率λk是均值為100 s-1的隨機數(shù)，計算節(jié)點的服務(wù)速率μ為1 000 s-1，計算節(jié)點服務(wù)的最大任務(wù)處理時延τmax為0.02 s。根據(jù)文獻[11]，設(shè)計算節(jié)點的通信覆蓋半徑r與目標區(qū)域比值為1∶5，即1 km。

為測試本文提出的 SCNP 算法和 MBKC 算法的性能，圖3比較了不同算法下平均任務(wù)處理等待時間的累積分布函數(shù)(cumulative distribution function，CDF)，該曲線通過計算小于多個不同時延值的計算節(jié)點數(shù)量與布局的總數(shù)量的比值而得到。同時，在霧計算網(wǎng)絡(luò)中對計算節(jié)點進行布局時，將任務(wù)處理時延納入限制條件中的必要性得到了證明。在圖3(a)中，以任務(wù)節(jié)點數(shù)量200為例。當(dāng)考慮計算QoS時，SCNP算法得到的計算節(jié)點數(shù)量為NSCNP=27，MBKC算法為NMBKC=35。當(dāng)不考慮計算QoS時，分別為N′SCNP=21和N′MBKC=31。雖然部署的計算節(jié)點數(shù)量減少，但從CDF曲線可以看出，分別只有42.9% 和 83.9% 的計算節(jié)點時延滿足QoS要求，即τ≤τmax。這說明在考慮服務(wù)QoS時，算法需要通過增加少量的計算節(jié)點，來保證所有計算節(jié)點的任務(wù)處理時延小于τmax。同時還可以注意到，在圖3(b)中，以任務(wù)節(jié)點數(shù)400為例，MBKC算法中有93.4%的計算節(jié)點時延小于0.01 s，數(shù)量為56。而在SCNP算法中這個數(shù)字為71.8%，數(shù)量為33。這說明與SCNP算法相比，MBKC算法的平均卸載任務(wù)處理等待時間更短，但代價是需要布局更多的計算節(jié)點。

圖3 平均任務(wù)處理延遲的累積分布函數(shù)對比

圖4 不同算法下計算節(jié)點隨任務(wù)節(jié)點數(shù)量變化對比

在Maiti等[13]的工作中，霧計算節(jié)點需要部署在已有的任務(wù)節(jié)點上。在這種情況下，計算節(jié)點的部署是“受限”的。圖4的仿真結(jié)果表明，無論是MBKC算法還是SCNP算法，“任意布局”的性能都要好于“受限布局”。當(dāng)在區(qū)域內(nèi)自由部署時，算法能對計算節(jié)點的位置進一步優(yōu)化，而不受限于固定的位置。值得注意的是，雖然在部署受限且任務(wù)節(jié)點數(shù)量較少(K≤150)的情況下，基于K均值的MBKC算法能夠得到更少的計算節(jié)點部署方案，但總的來說，SCNP算法更能勝任未來大規(guī)模霧計算網(wǎng)絡(luò)的實際應(yīng)用。這進一步凸顯了我們工作的優(yōu)勢。

4 結(jié)論

本文研究霧計算網(wǎng)絡(luò)中計算節(jié)點的最優(yōu)布局問題?？紤]到任務(wù)處理的時延影響部署節(jié)點的服務(wù)QoS，希望找到可以同時滿足任務(wù)節(jié)點通信覆蓋和計算要求的最小數(shù)量的計算節(jié)點及其對應(yīng)的布局位置。該問題是NP難的，目前沒有理論上的最優(yōu)解。為解決這個問題，給出該場景問題下所需計算節(jié)點數(shù)量的下界，并且提出低復(fù)雜度的啟發(fā)式算法實現(xiàn)計算節(jié)點的布局。首先，基于二分K均值思路提出MBKC算法。接著，考慮到MBKC算法較為依賴于初始值的選取這一事實，基于螺旋布局策略進一步設(shè)計高效低復(fù)雜度的SCNP算法。此外，也提供了兩種思路的布局算法的復(fù)雜度分析。數(shù)值結(jié)果證明了SCNP算法的優(yōu)越性，并且該算法能夠在任務(wù)節(jié)點較多的環(huán)境中以低復(fù)雜度得到趨向于下界的解。