幾種邊緣服務器部署算法的對比分析*

湖南人文科技學院數學與金融學院 易婷 申佳靈 聶勤 李軍成

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

邊緣計算是指在靠近數據源頭的一側，采用網絡、計算、存儲、應用核心能力為一體的開放平臺，就近提供最近端服務，產生更快的網絡服務響應，同時滿足行業在實時業務、應用智能、安全與隱私保護等方面的基本需求[1]。邊緣服務器（Edge Server，ES）是邊緣計算的重要組成部分，因此邊緣服務器的部署問題具有重要的研究意義。

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

在部署邊緣服務器時，往往需要選取合適的算法。本文的目的是將K-Means算法與二分K-Means算法、K-Medoids算法及免疫優化算法分別應用于邊緣服務器部署中，通過仿真實驗進行對比分析，為邊緣服務器部署算法的選擇提供了一定的參考。

1 四種邊緣服務器部署算法簡介

1.1 K-Means算法

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

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

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

1.2 二分K-Means算法

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

1.3 K-Medoids算法

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

1.4 免疫優化算法

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

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

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

在基站數據集中隨機產生n1個中心基站，即視為初始邊緣服務器種群。對n1個中心基站進行親和值評價并以此進行升序排序，如式（5）所示：

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

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

2 仿真結果與對比分析

首先將區域劃分結果與部署后所得的邊緣服務器具體位置作為評價指標，對K-Means算法、二分K-Means算法、K-Medoids算法、免疫優化算法的性能進行對比分析。當邊緣服務器數量取9時，分別利用四種算法進行邊緣服務器部署，結果如圖1所示。

當邊緣服務器數量取15時，分別利用四種算法進行邊緣服務器部署，結果如圖2所示。

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

另外，當基站與邊緣服務器之間的距離越短時，兩者之間的訪問延遲會越短，故這里將基站與邊緣服務器之間的平均訪問延遲值作為另一個衡量不同算法性能的指標。在實驗中，將基站與邊緣服務器之間的平均距離表示平均訪問延遲，其計算式如式（6）所示[10]：

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

當邊緣服務器數量取9與15時，分別利用四種算法進行邊緣服務器部署，平均訪問延遲結果對比如表1所示。

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

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

綜合兩個性能指標的對比分析可知，相較于K-Means算法、K-Medoids算法和免疫優化算法，二分K-Means算法在邊緣服務器部署中具有更好的效果。

3 結語

本文首先介紹了K-Means算法、二分K-Means算法、K-Medoids算法及免疫優化算法分別應用于邊緣服務器部署的基本原理，然后通過仿真實驗對四種算法的區域部署結果、平均訪問延遲兩個性能指標進行了比較，為邊緣服務器部署算法的選擇提供了一定的依據。