一種基于加權(quán)K?means的邊緣服務(wù)器部署方案

劉乃安，張澍文，李曉輝，呂思婷

（1.西安電子科技大學(xué)通信工程學(xué)院，陜西 西安 710071；2.西安電子科技大學(xué)廣州研究院，廣東 廣州 510555）

0 引 言

近年來(lái)，移動(dòng)互聯(lián)網(wǎng)產(chǎn)業(yè)飛速發(fā)展，文獻(xiàn)[1]引用全球移動(dòng)數(shù)據(jù)流量預(yù)測(cè)：更新在聯(lián)網(wǎng)設(shè)備的數(shù)量將超過(guò)全球的總?cè)丝跀?shù)。如今聯(lián)網(wǎng)設(shè)備的數(shù)量早已呈爆炸式的增長(zhǎng)，為了滿足5G 時(shí)代海量計(jì)算、海量數(shù)據(jù)、時(shí)延敏感和海量連接等需求，歐洲電信標(biāo)準(zhǔn)協(xié)會(huì)在2014年啟動(dòng)移動(dòng)邊緣計(jì)算（Mobile Edge Computing，MEC）標(biāo)準(zhǔn)項(xiàng)目。隨著軟件定義網(wǎng)絡(luò)（SDN）和網(wǎng)絡(luò)功能虛擬化（NFV）的提出，文獻(xiàn)[2?4]指出移動(dòng)網(wǎng)絡(luò)運(yùn)營(yíng)商（MNOs）將內(nèi)容分發(fā)網(wǎng)絡(luò)（CDN）功能集成到移動(dòng)網(wǎng)絡(luò)。5G 通信網(wǎng)絡(luò)架構(gòu)不同于4G 通信網(wǎng)絡(luò)架構(gòu)，它將核心網(wǎng)的應(yīng)用下沉至網(wǎng)絡(luò)邊緣側(cè)。邊緣服務(wù)器的部署將直接影響智能終端的接入速率、網(wǎng)絡(luò)時(shí)延、連接的可靠性以及智能終端的體驗(yàn)質(zhì)量。文獻(xiàn)[5]通過(guò)在網(wǎng)絡(luò)邊緣部署移動(dòng)邊緣服務(wù)器，智能終端的部分請(qǐng)求不用再去訪問(wèn)核心網(wǎng)，而是通過(guò)訪問(wèn)建立在基站側(cè)的邊緣服務(wù)器，使得傳輸距離變短從而降低了時(shí)延。未來(lái)MEC 業(yè)務(wù)的實(shí)現(xiàn)，會(huì)使網(wǎng)絡(luò)傳輸壓力下降，邊緣服務(wù)器的合理部署可有效避免網(wǎng)絡(luò)擁塞和負(fù)載均衡。

S.Nunna 等人描述了大量的移動(dòng)邊緣計(jì)算應(yīng)用場(chǎng)景，如今汽車行業(yè)的自動(dòng)駕駛和電子醫(yī)療領(lǐng)域的機(jī)器人遠(yuǎn)程手術(shù)等業(yè)務(wù)都迫切需要通過(guò)MEC 來(lái)實(shí)現(xiàn)低延遲、近距離通信服務(wù)和全局感知等功能[1]。在每個(gè)基站配備一臺(tái)邊緣服務(wù)器會(huì)消耗過(guò)多的資源，因此合理的部署方案十分關(guān)鍵。文獻(xiàn)[6]中提出了一種基于傳統(tǒng)K?means算法的方案來(lái)解決邊緣服務(wù)器的部署問(wèn)題。該方法可以簡(jiǎn)單快速地獲取單一時(shí)刻的簇心，但并沒有考慮到當(dāng)移動(dòng)終端的位置產(chǎn)生變化后的結(jié)果對(duì)邊緣服務(wù)器部署的影響。近年來(lái)，有大量的研究人員通過(guò)改進(jìn)K?means算法獲得更好的分類效果。文獻(xiàn)[7]中描述了不同聚類算法之間的差異，并根據(jù)文獻(xiàn)[8]提出了一種基于距離和權(quán)重改進(jìn)的K?means 算法，有效地避免孤立點(diǎn)和噪點(diǎn)對(duì)結(jié)果的影響。對(duì)于實(shí)際的應(yīng)用場(chǎng)景，需要盡可能地在邊緣服務(wù)器業(yè)務(wù)范圍內(nèi)覆蓋更多的終端設(shè)備，為每一個(gè)用戶提供服務(wù)。針對(duì)上述研究，本文從實(shí)際情況出發(fā)，通過(guò)KNN 算法將模擬的移動(dòng)設(shè)備根據(jù)與基站的距離進(jìn)行分類，并獲取每個(gè)基站側(cè)的流量統(tǒng)計(jì)值，采集每一個(gè)移動(dòng)終端的位置坐標(biāo)進(jìn)行加權(quán)K?means 算法處理，尋找聚類中心。另外，建立一個(gè)模擬場(chǎng)景來(lái)測(cè)試不同方法得到的邊緣服務(wù)器部署位置，針對(duì)不同邊緣服務(wù)器個(gè)數(shù)和不同時(shí)間段下的傳輸時(shí)延進(jìn)行評(píng)估。實(shí)驗(yàn)結(jié)果表明，所提方案顯著地降低了傳輸時(shí)延，緩解了網(wǎng)絡(luò)擁塞，從而提高了用戶的體驗(yàn)質(zhì)量。

1 背景與問(wèn)題描述

1.1 移動(dòng)邊緣計(jì)算的背景

現(xiàn)如今，海量的移動(dòng)設(shè)備對(duì)于數(shù)據(jù)處理的要求越來(lái)越高，為了提高用戶上網(wǎng)的舒適感，文獻(xiàn)[9?10]中提出了云計(jì)算的解決方案，即將數(shù)據(jù)傳輸?shù)竭h(yuǎn)程云端進(jìn)行計(jì)算存儲(chǔ)。但是云端在地理位置上與智能終端距離較遠(yuǎn)，并不能滿足低時(shí)延的要求，因此移動(dòng)邊緣計(jì)算被提出。MEC 通過(guò)NFV 以及SDN 兩大技術(shù)將網(wǎng)絡(luò)功能、內(nèi)容和資源部署在邊緣服務(wù)器，縮短與智能終端的距離，從而降低時(shí)延。相較于云計(jì)算這種集中式結(jié)構(gòu)，移動(dòng)邊緣計(jì)算則屬于分布式結(jié)構(gòu)，雖然單個(gè)的邊緣服務(wù)器的處理能力有限，但是服務(wù)節(jié)點(diǎn)的數(shù)目多，相鄰的邊緣服務(wù)器之間也可以進(jìn)行數(shù)據(jù)的交互。移動(dòng)網(wǎng)絡(luò)邊界計(jì)算平臺(tái)可以放置在基站側(cè)，縮短數(shù)據(jù)傳輸?shù)木嚯x，滿足低時(shí)延的要求。

1.2 邊緣服務(wù)器部署問(wèn)題

邊緣服務(wù)器部署在基站一側(cè)，相較于云計(jì)算有著地理位置上的優(yōu)勢(shì)，但如何選取邊緣服務(wù)器的部署位置就成了MEC 技術(shù)最關(guān)鍵的一步。合理的部署位置可以實(shí)現(xiàn)移動(dòng)用戶的覆蓋率最大化，減少孤立用戶偏離邊緣服務(wù)器的覆蓋范圍，從而使移動(dòng)用戶得到良好的體驗(yàn)質(zhì)量。本文算法是基于流量統(tǒng)計(jì)所提出，根據(jù)CNNIC（中信證券研究部）提供的數(shù)據(jù)，自1997年至今，中國(guó)手機(jī)網(wǎng)民規(guī)模達(dá)到80%以上，其中手機(jī)網(wǎng)民占整體網(wǎng)民比例接近100%，網(wǎng)民每周上網(wǎng)時(shí)間也在逐步增多，其中短視頻時(shí)長(zhǎng)占比持續(xù)提升。MEC 的提出不僅能提高用戶的體驗(yàn)質(zhì)量，還能夠降低基站對(duì)于網(wǎng)絡(luò)資源提供的壓力。根據(jù)上述研究，可實(shí)現(xiàn)的功能有：邊緣服務(wù)器的部署將進(jìn)一步促使移動(dòng)運(yùn)營(yíng)商與各種包含短視頻業(yè)務(wù)和車聯(lián)網(wǎng)業(yè)務(wù)的公司合作；移動(dòng)運(yùn)營(yíng)商通過(guò)為有需求的公司提供MEC 服務(wù)，使移動(dòng)用戶獲得更加舒適的用戶體驗(yàn)。

2 系統(tǒng)模型

本文系統(tǒng)模型的符號(hào)概述如表1所示，根據(jù)實(shí)際的系統(tǒng)模型可確定目標(biāo)函數(shù)及約束方程。本文將文獻(xiàn)[11]中提出的負(fù)載均衡問(wèn)題中所應(yīng)滿足的帶寬占用比和利用負(fù)載平衡因子判斷當(dāng)前接入網(wǎng)絡(luò)的負(fù)載情況作為判斷平衡負(fù)載情況的參考。

表1 符號(hào)概述

2.1 系統(tǒng)架構(gòu)

移動(dòng)邊緣計(jì)算的系統(tǒng)框架如圖1所示，作為一種三級(jí)網(wǎng)絡(luò)架構(gòu)，它包括數(shù)據(jù)中心層、邊緣服務(wù)器層和移動(dòng)終端設(shè)備層。移動(dòng)終端設(shè)備層中包含種類繁雜的移動(dòng)設(shè)備，如手機(jī)、便攜式計(jì)算機(jī)和車聯(lián)網(wǎng)設(shè)備等。在之前關(guān)于邊緣服務(wù)器部署的研究[6]中，并沒有提出當(dāng)移動(dòng)終端發(fā)生位置變化時(shí)是否會(huì)對(duì)邊緣服務(wù)器的部署產(chǎn)生影響。由于移動(dòng)終端的數(shù)量過(guò)于龐大，所以通過(guò)研究設(shè)備移動(dòng)的方式選擇邊緣服務(wù)器部署位置是難以實(shí)現(xiàn)的。本文通過(guò)模擬流量峰值時(shí)移動(dòng)終端的分布位置得到坐標(biāo)，并根據(jù)基站側(cè)采集到的流量對(duì)移動(dòng)設(shè)備進(jìn)行加權(quán)，有效地弱化終端設(shè)備的移動(dòng)性。因?yàn)槿祟惿盍?xí)慣和活動(dòng)場(chǎng)所范圍的局限性，當(dāng)用戶基數(shù)不斷擴(kuò)大時(shí)，個(gè)別用戶大范圍的轉(zhuǎn)移不會(huì)對(duì)邊緣服務(wù)器的部署問(wèn)題產(chǎn)生本質(zhì)的影響。相較于任意時(shí)刻下選擇邊緣服務(wù)器位置部署的模型，本文所提方法更具有實(shí)用性和真實(shí)性，所部署的邊緣服務(wù)器可以進(jìn)一步提高用戶的QoE。

圖1 MEC 系統(tǒng)框架

解決邊緣服務(wù)器的部署問(wèn)題主要取決于邊緣服務(wù)器層以及移動(dòng)終端設(shè)備層。邊緣服務(wù)器層由基站B 和邊緣服務(wù)器S 構(gòu)成，在基站與基站、邊緣服務(wù)器與邊緣服務(wù)器之間都可以進(jìn)行數(shù)據(jù)交換。為了解決邊緣服務(wù)器的部署問(wèn)題，需要盡可能地使邊緣服務(wù)器所覆蓋的移動(dòng)終端數(shù)目最大化，減少網(wǎng)絡(luò)各層之間數(shù)據(jù)傳輸?shù)木嚯x和時(shí)延，減少開發(fā)商的建造成本以及提高用戶的體驗(yàn)質(zhì)量。移動(dòng)終端設(shè)備層由不同種類的可與邊緣服務(wù)器層進(jìn)行數(shù)據(jù)交換的設(shè)備U構(gòu)成。

每個(gè)基站bi和其覆蓋范圍下與其進(jìn)行數(shù)據(jù)傳輸?shù)慕K端用戶uij(i=1,2,…,m;j=1,2,…,n)之間的傳輸時(shí)延可用歐幾里得距離d(bi,uij)表示，基站與邊緣服務(wù)器si之間的傳輸損耗用d(bi,sj)表示，公式如下：

由于d(bi,uij)?d(bi,sj)，所以基站與邊緣服務(wù)器之間的傳輸損耗可以忽略不計(jì)。本文需要解決的是如何部署邊緣服務(wù)器在實(shí)時(shí)條件下對(duì)于移動(dòng)終端的時(shí)延最小化的問(wèn)題，即解決平均傳輸距離問(wèn)題，使平均傳輸時(shí)延降低到最小，公式為：

2.2 目標(biāo)方程與約束

邊緣服務(wù)器部署中的普遍約束問(wèn)題包括邊緣服務(wù)器si是否部署在基站bj上、智能設(shè)備uj是否分配給邊緣服務(wù)器si，以及對(duì)用戶服務(wù)質(zhì)量的約束。

邊緣服務(wù)器與基站的連通性表示為：

智能終端與邊緣服務(wù)器的連通性表示為：

用戶服務(wù)質(zhì)量的約束表示為：

式中σ表示智能設(shè)備uj與邊緣服務(wù)器si之間的網(wǎng)絡(luò)延遲。

現(xiàn)在的邊緣服務(wù)器部署問(wèn)題沒有考慮不同時(shí)段智能終端訪問(wèn)的實(shí)際情況，即用戶高峰時(shí)段或用戶集中區(qū)域，智能設(shè)備的高密度訪問(wèn)會(huì)導(dǎo)致網(wǎng)絡(luò)出現(xiàn)擁堵的情況。為了克服這一問(wèn)題，在邊緣服務(wù)器的部署問(wèn)題中加入用戶的訪問(wèn)數(shù)據(jù)量這一約束，以便更合理地分配網(wǎng)絡(luò)資源，更快速地進(jìn)行網(wǎng)絡(luò)數(shù)據(jù)傳輸。這一約束問(wèn)題可表示為：

本文以系統(tǒng)平均完成時(shí)間最小化為目標(biāo)函數(shù)，公式如下：

3 部署算法

文獻(xiàn)[12]中分析了近幾年聚類算法的算法思想、關(guān)鍵技術(shù)以及優(yōu)缺點(diǎn)。其中針對(duì)數(shù)值類型數(shù)據(jù)的實(shí)驗(yàn)，K?means 算法的運(yùn)行效率遠(yuǎn)高于傳統(tǒng)層次聚類算法。傳統(tǒng)K?means 算法是一種簡(jiǎn)單、高效的聚類算法，但是傳統(tǒng)K?means 算法隨機(jī)選擇簇心的機(jī)制可能導(dǎo)致結(jié)果陷入局部最優(yōu)。因此需要對(duì)傳統(tǒng)的K?means 算法進(jìn)行改進(jìn)，讓它更加適合在MEC 場(chǎng)景下對(duì)邊緣服務(wù)器進(jìn)行尋址。文獻(xiàn)[13]提出一種基于距離和樣本權(quán)重改進(jìn)的K?means 算法，以密度峰值作為加權(quán)的參考依據(jù)并且有效地選擇初始聚類中心，提升了算法的性能。但是對(duì)于邊緣服務(wù)器部署的實(shí)際問(wèn)題，智能終端的密度會(huì)隨著用戶位置的變化而發(fā)生變化。因此本文依據(jù)基站側(cè)的流量統(tǒng)計(jì)提出一種改進(jìn)的K?means 算法，主要內(nèi)容如下：

1）數(shù)據(jù)采集。在300×300的地圖中模擬真實(shí)場(chǎng)景放置4 個(gè)坐標(biāo)已知的基站bm，模擬人口分布特點(diǎn)隨機(jī)生成800個(gè)終端設(shè)備樣本點(diǎn)，并獲取每個(gè)設(shè)備的位置坐標(biāo)un。

2）數(shù)據(jù)分類。本文暫不考慮終端設(shè)備在不同基站覆蓋范圍下的數(shù)據(jù)切換問(wèn)題，只根據(jù)設(shè)備距離基站的真實(shí)距離對(duì)100 個(gè)樣本點(diǎn)進(jìn)行分類。使用k=1 的KNN 算法，根據(jù)每個(gè)樣本點(diǎn)到不同基站的歐氏距離，選擇距離最小的基站作為一個(gè)子集，如圖2所示。其中nA，nB，nC，nD表示A、B、C 和D 基站下對(duì)應(yīng)的智能設(shè)備數(shù)目。

圖2 終端設(shè)備分類效果圖

3）權(quán)值分配。根據(jù)基站上統(tǒng)計(jì)到的日流量，通過(guò)式（8）計(jì)算不同組數(shù)據(jù)集樣本的權(quán)重，得到不同基站下對(duì)應(yīng)智能終端所屬權(quán)重ωA，ωB，ωC，ωD。

4）算法實(shí)現(xiàn)。將隨機(jī)選取的l個(gè)對(duì)象作為原始聚類中心，通過(guò)100 次迭代，將加權(quán)后的終端地理位置按照距離聚類中心最近的原則重新分配到每個(gè)聚類中，最終得到聚類中心的坐標(biāo)sl。由于隨機(jī)挑選原始聚類中心會(huì)對(duì)算法的結(jié)果產(chǎn)生影響，所以本文將多次產(chǎn)生的結(jié)果再次進(jìn)行聚類劃分，得到誤差最小的結(jié)果。圖3為選擇4 個(gè)邊緣服務(wù)器分布結(jié)果圖。

圖3 加權(quán)K?means 算法邊緣服務(wù)器的部署位置

4 實(shí)驗(yàn)與分析

對(duì)所提算法結(jié)果進(jìn)行分析，在智能終端和基站數(shù)量分布相同的情況下，分別比較所提加權(quán)K?means 算法、傳統(tǒng)K?means 算法和隨機(jī)方法在模擬環(huán)境中的終端的響應(yīng)時(shí)延。

4.1 不同數(shù)量邊緣服務(wù)器下的效果對(duì)比

如圖4所示，當(dāng)邊緣服務(wù)器部署的數(shù)量越多時(shí)，智能終端的響應(yīng)時(shí)間逐漸降低，當(dāng)邊緣服務(wù)器的數(shù)量增多，智能終端總是可以訪問(wèn)距離最近的邊緣服務(wù)器。由于邊緣服務(wù)器的部署問(wèn)題需要考慮實(shí)際成本，為了避免資源浪費(fèi)，移動(dòng)運(yùn)營(yíng)商希望在滿足用戶體驗(yàn)質(zhì)量的同時(shí)，可以使部署策略產(chǎn)生成本最小化。

圖4 邊緣服務(wù)器不同數(shù)量下的響應(yīng)時(shí)延

圖4中，橫坐標(biāo)是邊緣服務(wù)器的個(gè)數(shù)，縱坐標(biāo)是所有終端的平均響應(yīng)時(shí)間。當(dāng)邊緣服務(wù)器部署的數(shù)量大于6 個(gè)時(shí)，響應(yīng)時(shí)間的變化率也逐漸減小，部署過(guò)多的邊緣服務(wù)器將會(huì)造成資源以及成本的浪費(fèi)。綜合考慮部署成本、響應(yīng)時(shí)延以及用戶體驗(yàn)質(zhì)量等因素，發(fā)現(xiàn)選擇6 個(gè)邊緣服務(wù)器的部署策略是最合理的。對(duì)比分析發(fā)現(xiàn)，本文提出的方案相較于隨機(jī)部署方法和傳統(tǒng)K?means 算法選擇的部署位置，對(duì)于移動(dòng)終端用戶的響應(yīng)時(shí)延總是最小的。

4.2 不同時(shí)段下邊緣服務(wù)器部署效果對(duì)比

為了使邊緣服務(wù)器可以滿足各種場(chǎng)景下移動(dòng)用戶的體驗(yàn)質(zhì)量，本實(shí)驗(yàn)根據(jù)用戶的實(shí)際需求在不同時(shí)段場(chǎng)景下進(jìn)行分析。當(dāng)移動(dòng)用戶的響應(yīng)軌跡發(fā)生變化時(shí)，邊緣服務(wù)器的部署位置是否還能支持低時(shí)延的傳輸以及盡可能多的連接請(qǐng)求是本文探究的關(guān)鍵問(wèn)題。本文分別模擬早晨、中午和傍晚三個(gè)時(shí)間段終端設(shè)備的分布位置和分布密度，如圖5所示。由圖5可知，在早晨和傍晚階段，人口分布較為均勻并且網(wǎng)絡(luò)傳輸壓力較低，加權(quán)K?means 算法和傳統(tǒng)K?means 算法相較于隨機(jī)部署方法有著不錯(cuò)的表現(xiàn)。到中午時(shí)，人口多聚集于公司、學(xué)校等場(chǎng)所，分布稀疏度明顯，部分區(qū)域的網(wǎng)絡(luò)傳輸壓力增大，這種場(chǎng)景對(duì)于邊緣服務(wù)器的部署是一種考驗(yàn)。實(shí)驗(yàn)結(jié)果可以得出，傳統(tǒng)K?means 算法相較于隨機(jī)部署方法有著不錯(cuò)的優(yōu)勢(shì)，而本文提出的加權(quán)K?means 算法對(duì)于邊緣服務(wù)器部署問(wèn)題更加具有優(yōu)勢(shì)。

圖5 不同時(shí)段下的響應(yīng)時(shí)延

綜上所述，本文提出的加權(quán)K?means 算法相較于傳統(tǒng)K?means 算法和隨機(jī)部署的方法對(duì)于邊緣服務(wù)器部署位置的選擇更加合理；并且本文算法隨著場(chǎng)景的不斷切換和智能終端用戶對(duì)于邊緣服務(wù)器請(qǐng)求的不確定性，表現(xiàn)出更加優(yōu)秀的適應(yīng)性。

5 結(jié) 語(yǔ)

邊緣服務(wù)器的部署問(wèn)題是獲取服務(wù)于用戶效率最大化的尋址問(wèn)題。在實(shí)際處理這個(gè)問(wèn)題時(shí)，不僅要滿足對(duì)于設(shè)備的低時(shí)延要求，還應(yīng)該考慮對(duì)于運(yùn)營(yíng)商成本最小的問(wèn)題。在設(shè)計(jì)算法上，由于模擬的數(shù)據(jù)量遠(yuǎn)沒有實(shí)際的設(shè)備數(shù)據(jù)那么龐大，因此需進(jìn)一步優(yōu)化本文算法，在規(guī)模更大、數(shù)據(jù)更密集的場(chǎng)景下實(shí)現(xiàn)精確的數(shù)據(jù)結(jié)果。邊緣服務(wù)器處理尋址問(wèn)題有待解決，在得到部署位置之后，還應(yīng)該根據(jù)各個(gè)服務(wù)器之間的協(xié)同工作，找到更加優(yōu)化、便捷地處理數(shù)據(jù)的卸載方案。