李炫鋒，羅喜良

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

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

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

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

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

1 系統(tǒng)模型

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

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

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

1.2 問題建模

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

(1)

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

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

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

(2)

證明對(duì)于第1個(gè)不等號(hào)，在最壞的情況下，每個(gè)計(jì)算節(jié)點(diǎn)只能服務(wù)到一個(gè)任務(wù)節(jié)點(diǎn)，因此有N≤K。

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

(3)

將N個(gè)不等式加和，得

(4)

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

(5)

證畢。

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

2 計(jì)算節(jié)點(diǎn)布局算法

2.1 二分K均值聚類算法

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

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

(6)

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

(7)

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

(8)

給出。

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

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

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

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

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

2.2 螺旋計(jì)算節(jié)點(diǎn)布局算法

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

(9)

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

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

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

圖2 SCNP算法示例

2.3 復(fù)雜度分析

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

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

3 仿真實(shí)驗(yàn)分析

本節(jié)將提供數(shù)值仿真實(shí)驗(yàn)結(jié)果測(cè)試本文所提出的計(jì)算節(jié)點(diǎn)布局算法的性能。

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

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

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

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

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

4 結(jié)論

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