基于K-means的動(dòng)態(tài)資源分配策略

朱新峰，吳名位，王國海

(1.揚(yáng)州大學(xué) 信息工程學(xué)院，江蘇 揚(yáng)州 225100；2.中電科航空電子有限公司 航空電子事業(yè)部，四川 成都 610000)

0 引 言

移動(dòng)邊緣計(jì)算(MEC)是5G時(shí)代的一項(xiàng)新興技術(shù)，該技術(shù)將云計(jì)算中心的部分功能遷移至基站，使基站具備相應(yīng)的計(jì)算、存儲(chǔ)、處理等功能。MEC可以近距離為移動(dòng)用戶提供云計(jì)算和IT服務(wù)，允許用戶在基站內(nèi)或一定范圍內(nèi)使用邊緣云服務(wù)，使得移動(dòng)用戶感知到的端到端延遲減少。近期，如何對基站內(nèi)的資源進(jìn)行科學(xué)合理分配、如何實(shí)現(xiàn)資源分配的低時(shí)延和高帶寬成為近期研究熱點(diǎn)，尤其是在一些對時(shí)延敏感、數(shù)據(jù)量大的應(yīng)用中，如：車聯(lián)網(wǎng)、遠(yuǎn)程醫(yī)療、公共安全和CloudMES[1]等應(yīng)用場景。但MEC因其屬性和用戶的移動(dòng)性為資源的合理分配和充分利用帶來諸多挑戰(zhàn)[2]，考慮到MEC的計(jì)算壓力和用戶密集度成正比，本文結(jié)合MEC的頻譜資源分配，綜合不同場景、不同用戶量、不同用戶和用戶的不同任務(wù)等多種因素，采用K-means算法對用戶進(jìn)行聚類，利用拍賣算法對資源進(jìn)行分配，不僅使得資源得到較好利用、用戶獲得較好體驗(yàn)，且在有效提高吞吐量、降低傳輸時(shí)延方面獲得較好效果。

1 相關(guān)工作

本章介紹在MEC環(huán)境下，邊緣服務(wù)器的計(jì)算資源分配、頻譜資源分配、基于k-means算法的用戶分類和拍賣算法的相關(guān)研究。文獻(xiàn)[3]提出的MEC平臺(tái)的體系結(jié)構(gòu)描述以及支持上述特性的關(guān)鍵功能，說明了應(yīng)用程序開發(fā)人員可以利用來自MEC的實(shí)時(shí)無線接入網(wǎng)信息提供上下文感知服務(wù)，支持使用涉及云服務(wù)器的協(xié)作計(jì)算在資源約束設(shè)備中執(zhí)行計(jì)算密集型應(yīng)用程序。文獻(xiàn)[4]利用局域網(wǎng)絡(luò)收集用戶數(shù)據(jù)，使能源互聯(lián)網(wǎng)的數(shù)據(jù)壓縮成為可能，在不增加額外能耗開銷的情況下，可大幅度提高隨機(jī)訪問的可能性，降低傳輸延遲。文獻(xiàn)[5]提出MEC環(huán)境下如何保證q(quality of service)，把計(jì)算遷移到邊緣和基礎(chǔ)設(shè)施去中心化，能夠支持新興的應(yīng)用程序，實(shí)現(xiàn)了可接受的服務(wù)質(zhì)量。文獻(xiàn)[6]在WLAN中，將多種類型的網(wǎng)絡(luò)資源共同分配給用戶以實(shí)現(xiàn)q的公平性，將用戶q需求轉(zhuǎn)化為多資源需求，并應(yīng)用優(yōu)勢資源公平方案為每個(gè)用戶分配網(wǎng)絡(luò)資源。文獻(xiàn)[7]使用了一種根據(jù)總功率和誤碼率約束系統(tǒng)參數(shù)進(jìn)行參數(shù)化的聯(lián)合方法，根據(jù)每個(gè)用戶的實(shí)際需要來調(diào)整每個(gè)服務(wù)的平均吞吐量，通過最大數(shù)量的子載波進(jìn)行傳輸保證了q的子載波共享調(diào)度。文獻(xiàn)[8]將移動(dòng)應(yīng)用程序的計(jì)算密集型任務(wù)從資源稀缺的移動(dòng)設(shè)備轉(zhuǎn)移到位于邊緣網(wǎng)絡(luò)的服務(wù)器上，結(jié)合通信通道和邊緣服務(wù)器的容量限制，實(shí)現(xiàn)最小化應(yīng)用程序的平均完成時(shí)間。文獻(xiàn)[9]采用分布式資源分配的容錯(cuò)算法——時(shí)隙算法，以可執(zhí)行協(xié)議，使用簡單的啟發(fā)式和捐贈(zèng)方法合理的在成員之間分配資源。文獻(xiàn)[10]提出了一種基于Nim博弈獲勝策略的云資源分配機(jī)制為所有客戶端提供了有效數(shù)量的運(yùn)行云服務(wù)器，并通過使用預(yù)配對方法快速有效地分配云資源，不需要搜索正在運(yùn)行的云服務(wù)器的剩余資源，減少了調(diào)度資源所花費(fèi)的時(shí)間。文獻(xiàn)[11]利用流量規(guī)范參數(shù)化每個(gè)無線體域網(wǎng)絡(luò)的流量源，得到每個(gè)無線體域網(wǎng)絡(luò)所需的服務(wù)速率，采用優(yōu)先資源分配算法，根據(jù)無線體域網(wǎng)絡(luò)的服務(wù)優(yōu)先級(jí)分配信道資源。文獻(xiàn)[12]以器件特性的數(shù)據(jù)傳輸方案，采用k-均值聚類算法，根據(jù)流量特征對設(shè)備進(jìn)行分類。每組分類設(shè)備具有不同的優(yōu)先級(jí)，無線信道訪問時(shí)間由該優(yōu)先級(jí)決定，根據(jù)優(yōu)先級(jí)使用不同的信道訪問時(shí)間可以避免終端設(shè)備的沖突，提高傳輸效率，并對隨機(jī)組合拍賣機(jī)制[13]、多市場動(dòng)態(tài)雙向拍賣機(jī)制MobiAuc[14]、云環(huán)境下虛擬機(jī)資源分配與定價(jià)機(jī)制[15]等問題進(jìn)行了研究。本文提出KDSAA策略，采用“流體”模型[16]，有效提高了計(jì)算資源和頻譜資源的利用率。

2 數(shù)據(jù)表示

在移動(dòng)邊緣計(jì)算中，評判算法性能的主要指標(biāo)為：吞吐量和時(shí)延。本文實(shí)驗(yàn)以邊緣云的吞吐量和傳輸時(shí)延為主要評判標(biāo)準(zhǔn)，結(jié)合算法在不同條件下的表現(xiàn)，綜合評判算法性能。本文K-means算法以用戶的實(shí)際資源請求量和用戶的優(yōu)先級(jí)為主要屬性，模擬邊緣云部署在基站上，對用戶進(jìn)行聚類，再根據(jù)用戶坐標(biāo)，使用類歐式距離公式計(jì)算用戶到基站的距離，篩除超出基站范圍用戶，使用拍賣算法將資源按照對應(yīng)比例拍賣給用戶，結(jié)合動(dòng)態(tài)頻譜資源分配降低傳輸時(shí)延。為獲得較好實(shí)驗(yàn)效果，該實(shí)驗(yàn)只考慮了單時(shí)隙下的單基站資源分配。以下為數(shù)據(jù)表示的主要部分：

3 動(dòng)態(tài)的計(jì)算資源和頻譜分配策略

本文中動(dòng)態(tài)計(jì)算資源和頻譜分配主要有兩個(gè)策略。一是根據(jù)用戶的資源請求量和用戶優(yōu)先級(jí)兩個(gè)基本屬性，采用K-means算法把用戶聚類成n個(gè)不同類型用戶簇，二是針對不同類型用戶簇的資源請求量，采用荷蘭式拍賣算法，把基站中的計(jì)算資源和帶寬按照不同類型用戶簇的競價(jià)比例進(jìn)行分配，將基站資源進(jìn)行“流體”化，從而基本達(dá)到根據(jù)不同用戶的實(shí)際資源需求量進(jìn)行分配的要求，即“用多少分多少”，以此來實(shí)現(xiàn)基站較大的吞吐量和較低的傳輸時(shí)延。

實(shí)驗(yàn)主要分為5個(gè)步驟：

(2)使用類歐氏距離計(jì)算每個(gè)用戶與基站的距離D=(D1,D2,…,Dm)，為了保證實(shí)驗(yàn)效果，目前只考慮單個(gè)基站范圍內(nèi)的用戶，并設(shè)置基站覆蓋閾值d(Di

接下來我們把基站資源(BSresource)和帶寬(BSband)對應(yīng)不同類型用戶簇按照比例分成n份，同樣使用“用多少分多少”的方法，即每份中均包含相應(yīng)數(shù)量的“資源塊”，表示為Rn(分配資源量)和Bn(分配帶寬)，如式(1)和式(2)所示

(1)

(2)

考慮到基站計(jì)算資源量和帶寬有限，所有用戶簇分配的計(jì)算資源量總和、帶寬總和均不能超過邊緣云的資源總量，應(yīng)滿足式(3)

(3)

(4)參照(3)分配方法將基站頻譜資源進(jìn)行“流體”化分配，即“用多少分多少”，不同用戶簇把簇內(nèi)資源按照每個(gè)用戶的競價(jià)分配子載波帶寬，子載波帶寬b如式(4)所示

(4)

為保證實(shí)驗(yàn)效果，用戶分配到的子載波帶寬總和不超過基站子載波帶寬總量，子載波最大分配個(gè)數(shù)不超過Num，如式(5)所示

(5)

(5)線性求出基站吞吐量最大值和傳輸時(shí)延的最小值：基站吞吐量和傳輸時(shí)延在式(1)和式(5)約束下，求得目標(biāo)函數(shù)Rc(邊緣云吞吐量)的最大值和Rt(傳輸時(shí)延)的最小值。

1)求出邊緣云的最大吞吐量Rc

2)求出所有用戶的最小傳輸時(shí)延Rt

算法步驟和流程如下：

步驟1 初始化參數(shù)m、n、k、d、e、N0、h0，用戶和基站的基本屬性。

步驟2 初始化n個(gè)質(zhì)心，運(yùn)行K-means算法，將用戶聚成n個(gè)用戶簇。

步驟3 將不同用戶簇存入不同矩陣，計(jì)算用戶競價(jià)、計(jì)算用戶到基站距離，篩除大于閾值d的用戶，計(jì)算每類用戶簇競價(jià)總和。

步驟4 參照不同用戶簇的計(jì)算資源總和，基站按式(1)和式(2)把“流體”化的資源進(jìn)行按比例分配，確保每個(gè)用戶簇均可獲得合適資源量。

步驟5 用戶簇結(jié)合簇內(nèi)最大競價(jià)將資源進(jìn)行內(nèi)部拍賣，直到所有用戶均獲得合理計(jì)算資源或該基站資源耗盡時(shí)終止。

步驟6 計(jì)算子載波帶寬和用戶競價(jià)，按式(4)進(jìn)行分配。

步驟7 計(jì)算基站吞吐量最大值和傳輸時(shí)延最小值。

步驟8 結(jié)束算法。

在實(shí)際環(huán)境中邊緣云的資源分配由多個(gè)基站協(xié)調(diào)配合，動(dòng)態(tài)完成對用戶需求資源的分配任務(wù)，但本文實(shí)驗(yàn)只考慮了單基站、單時(shí)隙，因此在KDSAA算法整體實(shí)現(xiàn)流程示意圖中判斷框后的鄰居基站和下一時(shí)隙在本文實(shí)驗(yàn)中不體現(xiàn)。KDSAA算法整體實(shí)現(xiàn)流程如圖1所示。

圖1 KDSAA算法整體實(shí)現(xiàn)流程

4 仿真實(shí)驗(yàn)

為驗(yàn)證本算法在動(dòng)態(tài)資源和頻譜分配策略中的性能，本文使用MATLAB2016a為實(shí)驗(yàn)平臺(tái)，PC配置為聯(lián)想啟天T5000，16 G內(nèi)存，酷睿i7CPU，Windows10操作系統(tǒng)。本實(shí)驗(yàn)使用數(shù)值計(jì)算，將KDSAA、DRAA和傳統(tǒng)的虛擬機(jī)分配算法(VMAA)進(jìn)行比較，分別計(jì)算吞吐量和傳輸時(shí)延，觀察3種算法隨著用戶量變化時(shí)的性能狀況。

實(shí)驗(yàn)參數(shù)設(shè)置如下：用戶基本屬性資源請求量r和用戶優(yōu)先級(jí)p設(shè)置：均值為10，相關(guān)系數(shù)為1的高斯數(shù)據(jù)，坐標(biāo)x，y為50以內(nèi)的隨機(jī)值。邊緣云基站基本屬性值見表2，程序運(yùn)行次數(shù)所用時(shí)間總和為該算法計(jì)算結(jié)果所用時(shí)間，算法復(fù)雜度為O(n2)。為采集較好的實(shí)驗(yàn)效果，本次實(shí)驗(yàn)以循環(huán)100次求均值為結(jié)果，并將所得結(jié)果單位化處理。

在K-means算法中，設(shè)定合理的聚類個(gè)數(shù)n值是NP問題。n值的確定需要相關(guān)的專業(yè)知識(shí)來猜測和預(yù)判，而預(yù)判的結(jié)果往往是不準(zhǔn)確的，得到的結(jié)果也不理想，本實(shí)驗(yàn)根據(jù)相關(guān)先驗(yàn)知識(shí)，采用啟發(fā)式算法，對不同n值進(jìn)行適當(dāng)?shù)拿杜e實(shí)驗(yàn)驗(yàn)證，最終確定n值設(shè)為4時(shí)聚類效果最好，這里例舉n值為3、5時(shí)的聚類效果：n=3，聚類如圖2所示。n=5，聚類結(jié)果如圖3所示。

圖2 當(dāng)n=3時(shí)聚類結(jié)果

圖3 當(dāng)n=5時(shí)聚類結(jié)果

通過實(shí)驗(yàn)發(fā)現(xiàn)，將質(zhì)心個(gè)數(shù)n設(shè)置為4時(shí)聚類結(jié)果達(dá)到最優(yōu)。此時(shí)，考慮到基站性能和實(shí)際生活環(huán)境，將邊緣云覆蓋用戶上限設(shè)為m=500。仿真參數(shù)見表1。

表1 仿真參數(shù)

本實(shí)驗(yàn)設(shè)置聚類質(zhì)心個(gè)數(shù)n=4，分別定義為：n=1為普通用戶簇，n=2為重要用戶簇，n=3為一般重要用戶簇、n=4為較重要用戶簇。用戶的資源請求量不同，對應(yīng)的優(yōu)先級(jí)也不同，因此使用mvnrnd函數(shù)產(chǎn)生均值為10，相關(guān)系數(shù)為1的高斯數(shù)據(jù)。我們選取4個(gè)初始質(zhì)心，從序號(hào)為1的用戶開始，每隔m/n個(gè)選取一個(gè)，直到選夠4個(gè)。然后運(yùn)行K-means算法對用戶進(jìn)行聚類，通過不斷更新質(zhì)心位置，直到4個(gè)質(zhì)心參數(shù)值基本不再變化或迭代次數(shù)超過用戶量m時(shí)結(jié)束聚類。聚類結(jié)果如圖4所示。

圖4 用戶聚類結(jié)果

聚類結(jié)束后，我們用4個(gè)聚類出的質(zhì)心作為不同類型用戶簇的表征，分別對應(yīng)1、2、3、4，質(zhì)心參數(shù)和不同用戶簇對應(yīng)結(jié)果見表2。

表2 不同類型用戶簇對應(yīng)

由表2中結(jié)果分析可知，聚類出的4類用戶簇和我們預(yù)測的基本吻合，分析入下：

(1)當(dāng)用戶資源請求量較小，用戶優(yōu)先級(jí)也較低時(shí)，被劃分到普通用戶簇中;

(2)當(dāng)用戶資源請求量較大，用戶優(yōu)先級(jí)也較高時(shí)，被劃分到較重要用戶簇中;

(3)當(dāng)用戶請求量或用戶優(yōu)先級(jí)其中一個(gè)較低時(shí)，就被劃分到重要用戶簇或一般重要用戶簇中。

根據(jù)用戶實(shí)際需求將用戶分類，不僅可以有效提高用戶體驗(yàn)，也可以使基站資源得到合理的分配和充分使用。接下來，考慮單個(gè)基站的覆蓋范圍有限，且用戶到基站的距離對信道質(zhì)量會(huì)產(chǎn)生影響，我們對超過基站覆蓋范圍的用戶進(jìn)行篩選，通過改變實(shí)驗(yàn)中基站覆蓋范圍閾值d分別來測試對比3個(gè)算法的性能，這里列舉d=45和d=50時(shí)的實(shí)驗(yàn)對比結(jié)果，如圖5～圖8所示。

圖5 用戶數(shù)量和邊緣服務(wù)器吞吐量的關(guān)系(d=45)

(1)不同閾值d，吞吐量對比；

圖6 用戶數(shù)量和邊緣服務(wù)器吞吐量的關(guān)系(d=50)

圖7 用戶數(shù)量和邊緣服務(wù)器傳輸時(shí)延的關(guān)系(d=45)

圖8 用戶數(shù)量和邊緣服務(wù)器傳輸時(shí)延的關(guān)系(d=50)

(2)不同閾值d，傳輸時(shí)延對比；

由以上實(shí)驗(yàn)結(jié)果我們看出，KDSAA算法在吞吐量和傳輸時(shí)延上要優(yōu)于DRAA和VMAA。因考慮到單個(gè)基站所能承受的用戶量有限，所以本實(shí)驗(yàn)中用戶數(shù)量m值上限設(shè)置為500。在實(shí)驗(yàn)中，當(dāng)基站覆蓋范圍閾值d不同時(shí)，基站所覆蓋用戶數(shù)量也不同，因此該實(shí)驗(yàn)結(jié)果也間接驗(yàn)證了當(dāng)用戶數(shù)量遞增時(shí)，KDSAA算法在吞吐量和傳輸時(shí)延上的表現(xiàn)也優(yōu)于DRAA和VMAA。傳統(tǒng)的虛擬機(jī)分配方式是將資源分塊，再拍賣給用戶，用戶的資源請求量的變化不會(huì)對基站的分配產(chǎn)生較大影響，這使得資源利用率較低。DRAA將計(jì)算資源“流體化”，是根據(jù)用戶的實(shí)際需求量進(jìn)行分配，所以DRAA的吞吐量和傳輸時(shí)延的指標(biāo)均優(yōu)于VMAA。KDSAA根據(jù)用戶的資源需求量和相應(yīng)優(yōu)先級(jí)進(jìn)一步細(xì)分用戶，為用戶提供了更精準(zhǔn)、更高效的服務(wù)，同時(shí)也大幅度提高了基站資源利用率。其次，KDSAA將頻譜進(jìn)一步分配，根據(jù)用戶實(shí)際資源請求量計(jì)算競價(jià)大小，使每個(gè)子載波都會(huì)獲得合理的帶寬，讓頻譜資源也得到了充分利用，尤其是在基站覆蓋范圍閾值d值變大時(shí)，即使距離基站較遠(yuǎn)的用戶依然可以獲得較好的資源分配。綜上所述，在基站覆蓋范圍一定時(shí)，KDSAA在吞吐量和傳輸時(shí)延指標(biāo)上的表現(xiàn)更好。

實(shí)驗(yàn)將程序運(yùn)行時(shí)間模擬為基站處理器運(yùn)行時(shí)間，在改變基站覆蓋范圍d(用戶數(shù)量同步變化)的情況下，對比3種算法的運(yùn)行時(shí)間。3種算法執(zhí)行100次的時(shí)間對比如圖9和表3所示。

圖9 算法執(zhí)行時(shí)間

表3 算法執(zhí)行時(shí)間數(shù)據(jù)

由以上實(shí)驗(yàn)結(jié)果我們可以看出3種算法的執(zhí)行時(shí)間無明顯差距，隨著基站覆蓋范圍和用戶數(shù)量變化時(shí)，KDSAA的執(zhí)行時(shí)間略低于VMAA的執(zhí)行時(shí)間，與DRAA執(zhí)行時(shí)間基本一致。雖然計(jì)算時(shí)間上無明顯優(yōu)勢，但足以提高對時(shí)效要求較高的用戶體驗(yàn)，且KDSAA相較于DRAA和VMAA有著較高吞吐量和較低傳輸時(shí)延，綜合各項(xiàng)實(shí)驗(yàn)指標(biāo)，KDSAA 更適用于在MEC環(huán)境下的動(dòng)態(tài)資源分配。

5 結(jié)束語

隨著5G通訊技術(shù)的到來，在MEC環(huán)境下，用戶對服務(wù)質(zhì)量和應(yīng)用體驗(yàn)要求越來越高，需根據(jù)用戶的實(shí)際場景和需求對資源進(jìn)行合理分配，才能達(dá)到較好的資源分配效果。文中我們對用戶進(jìn)行合理的聚類后，結(jié)合計(jì)算資源和頻譜資源分配策略，獲得了較好的分配效果。下一步工作將進(jìn)一步研究MEC環(huán)境下動(dòng)態(tài)時(shí)隙中多基站博弈的資源分配問題。