湖南人文科技學(xué)院數(shù)學(xué)與金融學(xué)院 易婷 申佳靈 聶勤 李軍成

在邊緣計(jì)算中，邊緣服務(wù)器的部署是任務(wù)卸載的核心，因此選取合適的邊緣服務(wù)器部署算法顯得尤為重要。本文以K-Means算法、二分K-Means算法、K-Medoids算法及免疫優(yōu)化算法等邊緣服務(wù)器部署算法為對(duì)象，通過(guò)仿真實(shí)驗(yàn)對(duì)四種算法的性能進(jìn)行了對(duì)比分析，為邊緣服務(wù)器部署算法的選擇提供了一定的依據(jù)。

邊緣計(jì)算是指在靠近數(shù)據(jù)源頭的一側(cè)，采用網(wǎng)絡(luò)、計(jì)算、存儲(chǔ)、應(yīng)用核心能力為一體的開(kāi)放平臺(tái)，就近提供最近端服務(wù)，產(chǎn)生更快的網(wǎng)絡(luò)服務(wù)響應(yīng)，同時(shí)滿足行業(yè)在實(shí)時(shí)業(yè)務(wù)、應(yīng)用智能、安全與隱私保護(hù)等方面的基本需求[1]。邊緣服務(wù)器（Edge Server，ES）是邊緣計(jì)算的重要組成部分，因此邊緣服務(wù)器的部署問(wèn)題具有重要的研究意義。

目前，已有許多文獻(xiàn)對(duì)邊緣服務(wù)器的部署問(wèn)題進(jìn)行了研究，例如引用[2]以時(shí)延與能耗為目標(biāo)，對(duì)邊緣服務(wù)器放置進(jìn)行研究，提出了一種基于混沌麻雀搜索算法的邊緣服務(wù)器放置方法，但其并不適用于多跳的時(shí)延模型；引用[3]以最小化訪問(wèn)延遲和最小化負(fù)載差異為優(yōu)化目標(biāo)，建立了邊緣服務(wù)器放置優(yōu)化模型并提出了一種基于改進(jìn)啟發(fā)式算法的移動(dòng)邊緣服務(wù)器放置方法，但其在負(fù)載平衡方面沒(méi)有達(dá)到最優(yōu)；引用[4]將智能城市中k個(gè)邊緣服務(wù)器放置問(wèn)題描述為一個(gè)多目標(biāo)優(yōu)化問(wèn)題，提出了一種改進(jìn)的帶有精英策略的多目標(biāo)非支配排序遺傳算法對(duì)該問(wèn)題進(jìn)行優(yōu)化解決；引用[5]為克服參數(shù)調(diào)整困難等，提出了一種基于深度Q網(wǎng)絡(luò)和強(qiáng)化學(xué)習(xí)的新型邊緣服務(wù)器放置算法等。

在部署邊緣服務(wù)器時(shí)，往往需要選取合適的算法。本文的目的是將K-Means算法與二分K-Means算法、K-Medoids算法及免疫優(yōu)化算法分別應(yīng)用于邊緣服務(wù)器部署中，通過(guò)仿真實(shí)驗(yàn)進(jìn)行對(duì)比分析，為邊緣服務(wù)器部署算法的選擇提供了一定的參考。

1 四種邊緣服務(wù)器部署算法簡(jiǎn)介

1.1 K-Means算法

在利用K-Means算法[6]部署邊緣服務(wù)器時(shí)，首先基站數(shù)據(jù)集中隨機(jī)取k個(gè)基站分別作為k個(gè)簇的中心基站，計(jì)算剩下的所有基站到k個(gè)中心基站的歐氏距離，如式（1）所示：

其中，ai表示第i個(gè)基站，bj表示第j個(gè)中心基站；然后將與中心基站的歐式距離和最小的基站劃分為一簇，并根據(jù)聚類(lèi)劃分結(jié)果重新得到k個(gè)中心基站，按照新中心基站重新聚類(lèi)；最后不斷重復(fù)選取新中心基站并劃分簇，直至目標(biāo)函數(shù)SEE收斂，此時(shí)所得到的k個(gè)中心基站即為邊緣服務(wù)器位置，如式（2）所示：

其中，ai表示第k個(gè)簇的中第i個(gè)基站，bk表示第k個(gè)簇的中心基站。

1.2 二分K-Means算法

將二分K-Means算法[7]應(yīng)有于邊緣服務(wù)器部署時(shí)，將整個(gè)基站數(shù)據(jù)集視為一個(gè)簇A1，對(duì)簇A1進(jìn)行K-Means聚類(lèi)(k=2)得到兩個(gè)基站分簇A2、A3；分別根據(jù)式(2)計(jì)算簇A2、A3的SSE，選擇較小SEE的基站簇繼續(xù)進(jìn)行K-Means聚類(lèi)(k=2)得到基站簇A4、A5并計(jì)算各簇的SSE，重復(fù)以上步驟直至得到k個(gè)基站簇?cái)?shù)，在進(jìn)行基站簇劃分過(guò)程中各簇中心基站已明確得到，即邊緣服務(wù)器部署完成。

1.3 K-Medoids算法

將K-Medoids算法[8]應(yīng)有于邊緣服務(wù)器部署時(shí)，首先在基站數(shù)據(jù)集中隨機(jī)選取k個(gè)初始中心基站，依據(jù)就近原則將所有基站劃分至k個(gè)初始中心基站內(nèi)，此時(shí)基站數(shù)據(jù)集分為k類(lèi)；在每一類(lèi)中計(jì)算任意基站與其他基站的距離和，選擇該類(lèi)中與該類(lèi)其他基站距離和最小的基站為該類(lèi)新中心基站；再依據(jù)新中心基站重新將整個(gè)基站數(shù)據(jù)集劃分k類(lèi)，直至k個(gè)中心基站不再發(fā)生變化，最后所得到的k個(gè)中心基站即為所部署的k個(gè)邊緣服務(wù)器位置，邊緣服務(wù)器部署完成。

1.4 免疫優(yōu)化算法

在利用免疫算法[9]部署邊緣服務(wù)器時(shí)，從有限個(gè)位置(N個(gè))中選擇一定數(shù)量的位置(K個(gè))，以邊緣服務(wù)器為抗體、基站為抗原建立一個(gè)選址模型，將邊緣服務(wù)器與基站之間的最小距離和為目標(biāo)函數(shù)F，如式（3）所示：

約束條件如式（4）所示：

其中，d(Aa,Bb)表示在同一類(lèi)中位置Aa的邊緣服務(wù)器和位置Bb的基站之間的距離，K為邊緣服務(wù)器數(shù)量，N為基站數(shù)量，Sa表示邊緣曲線所包含的不規(guī)則區(qū)域。

在基站數(shù)據(jù)集中隨機(jī)產(chǎn)生n1個(gè)中心基站，即視為初始邊緣服務(wù)器種群。對(duì)n1個(gè)中心基站進(jìn)行親和值評(píng)價(jià)并以此進(jìn)行升序排序，如式（5）所示：

其中，aff(Ai,Cj)表示中心基站Ai與其他基站Cj的距離和，值越小代表基站Ai與Cj越親和。

在排序后的n1個(gè)中心基站中取前n2個(gè)基站作為父代邊緣服務(wù)器群體，前m1個(gè)基站放入邊緣服務(wù)器記憶庫(kù)；若記憶庫(kù)中的m1個(gè)基站滿足約束條件則結(jié)束，若不滿足則將父代邊緣服務(wù)器群體中n2個(gè)基站進(jìn)行選擇、交叉、變異等操作，與記憶庫(kù)中的m1個(gè)基站構(gòu)成一個(gè)新群體；重新進(jìn)行基站評(píng)價(jià)并以親和值排序，從新群體中選取前m2個(gè)基站替換記憶庫(kù)中已有的部分基站；若此時(shí)記憶庫(kù)中的基站滿足約束條件則結(jié)束，若不滿足則繼續(xù)重復(fù)以上步驟直至滿足；滿足條件后輸出記憶庫(kù)中排序最高的k個(gè)基站，即為k個(gè)邊緣服務(wù)器位置。

2 仿真結(jié)果與對(duì)比分析

首先將區(qū)域劃分結(jié)果與部署后所得的邊緣服務(wù)器具體位置作為評(píng)價(jià)指標(biāo)，對(duì)K-Means算法、二分K-Means算法、K-Medoids算法、免疫優(yōu)化算法的性能進(jìn)行對(duì)比分析。當(dāng)邊緣服務(wù)器數(shù)量取9時(shí)，分別利用四種算法進(jìn)行邊緣服務(wù)器部署，結(jié)果如圖1所示。

當(dāng)邊緣服務(wù)器數(shù)量取15時(shí)，分別利用四種算法進(jìn)行邊緣服務(wù)器部署，結(jié)果如圖2所示。

由圖1與圖2可知，K-Means算法所得的邊緣服務(wù)器部署結(jié)果只能得到具體的邊緣服務(wù)器位置，并沒(méi)有進(jìn)行區(qū)域劃分且可能摒棄孤立點(diǎn)；二分K-Means算法所得的邊緣服務(wù)器部署結(jié)果既有明確的區(qū)域劃分，同時(shí)又直接給出邊緣服務(wù)器位置；K-Medoids算法、免疫優(yōu)化算法所得的邊緣服務(wù)器部署結(jié)果只有區(qū)域劃分結(jié)果而沒(méi)有直接給出邊緣服務(wù)器位置，還另需對(duì)各區(qū)域計(jì)算任意基站與其他基站的距離之和，取每簇中與該簇中其他基站距離之和最小的基站作為各區(qū)域待部署的邊緣服務(wù)器位置。

另外，當(dāng)基站與邊緣服務(wù)器之間的距離越短時(shí)，兩者之間的訪問(wèn)延遲會(huì)越短，故這里將基站與邊緣服務(wù)器之間的平均訪問(wèn)延遲值作為另一個(gè)衡量不同算法性能的指標(biāo)。在實(shí)驗(yàn)中，將基站與邊緣服務(wù)器之間的平均距離表示平均訪問(wèn)延遲，其計(jì)算式如式（6）所示[10]：

式中，其中d(Aa,Bb)表示分別在位置Aa的邊緣服務(wù)器和位置Bb的基站之間的距離，K為邊緣服務(wù)器數(shù)量，N為基站數(shù)量。顯然，在邊緣服務(wù)器數(shù)量K和基站數(shù)量N一定時(shí)，基站和邊緣服務(wù)器之間的距離越小，平均訪問(wèn)延遲T也越小，即越滿足部署目標(biāo)。

當(dāng)邊緣服務(wù)器數(shù)量取9與15時(shí)，分別利用四種算法進(jìn)行邊緣服務(wù)器部署，平均訪問(wèn)延遲結(jié)果對(duì)比如表1所示。

表1 四種算法的平均訪問(wèn)延遲結(jié)果對(duì)比（單位：s）Tab.1 Comparison of average access delay results of four algorithms (unit: s)

由表1可知，四種算法的平均訪問(wèn)延遲由小到大分別為二分K-Means算法、K-Medoids算法、免疫優(yōu)化算法、K-Means算法。

綜合兩個(gè)性能指標(biāo)的對(duì)比分析可知，相較于K-Means算法、K-Medoids算法和免疫優(yōu)化算法，二分K-Means算法在邊緣服務(wù)器部署中具有更好的效果。

3 結(jié)語(yǔ)

本文首先介紹了K-Means算法、二分K-Means算法、K-Medoids算法及免疫優(yōu)化算法分別應(yīng)用于邊緣服務(wù)器部署的基本原理，然后通過(guò)仿真實(shí)驗(yàn)對(duì)四種算法的區(qū)域部署結(jié)果、平均訪問(wèn)延遲兩個(gè)性能指標(biāo)進(jìn)行了比較，為邊緣服務(wù)器部署算法的選擇提供了一定的依據(jù)。