基于分類優(yōu)化的物聯(lián)網(wǎng)節(jié)點(diǎn)負(fù)載均衡策略

趙 東，韓曉艷，趙宏偉，于繁華

(1.吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，長(zhǎng)春130022;2.長(zhǎng)春師范大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，長(zhǎng)春130032;3.吉林農(nóng)業(yè)大學(xué) 信息技術(shù)學(xué)院，長(zhǎng)春130118)

0 引 言

負(fù)載均衡算法優(yōu)化技術(shù)相對(duì)來(lái)說(shuō)已比較成熟。毛譽(yù)熹等［1］利用IA－DSR(基于干擾感知的負(fù)載均衡路由協(xié)議)改進(jìn)了網(wǎng)絡(luò)的整體吞吐量。鄭相全［2］通過(guò)跨層優(yōu)化路徑的方法提高網(wǎng)絡(luò)的吞吐量來(lái)優(yōu)化負(fù)載節(jié)點(diǎn)。文獻(xiàn)［3］利用于多信道技術(shù)改善無(wú)線網(wǎng)絡(luò)的通信，以優(yōu)化傳輸速率，提高網(wǎng)絡(luò)負(fù)載。王敏等［4］采用最大路徑的方法進(jìn)行負(fù)載均衡處理，其方法的主要缺點(diǎn)是沒(méi)有考慮所選信道的擁塞情況。其中文獻(xiàn)［5-6］還提及利用無(wú)線傳感器網(wǎng)絡(luò)，在不考慮節(jié)點(diǎn)密度分布的情況下對(duì)節(jié)點(diǎn)進(jìn)行處理，能夠有效地改善其負(fù)載性能。文獻(xiàn)［7］對(duì)異構(gòu)無(wú)線網(wǎng)絡(luò)節(jié)點(diǎn)性能與代價(jià)進(jìn)行處理和評(píng)估，從而優(yōu)化部署實(shí)施策略。朱永嬌等［8］使用遺傳聚類方法對(duì)路由算法進(jìn)行改進(jìn)，實(shí)現(xiàn)無(wú)線傳感網(wǎng)負(fù)載均衡。

本文運(yùn)用Hadoop 技術(shù)原理將Slave 節(jié)點(diǎn)的數(shù)據(jù)匯集成數(shù)據(jù)節(jié)點(diǎn)，根據(jù)其Slave 節(jié)點(diǎn)的數(shù)據(jù)特點(diǎn)進(jìn)行分類處理，使特征相似的Slave 節(jié)點(diǎn)歸為一類。同一類別Slave 節(jié)點(diǎn)，其處理能力及目前狀態(tài)可能非常相近，類別的不同決定其處理能力及當(dāng)前狀態(tài)的顯著不同，因此根據(jù)其類別特點(diǎn)按照其資源空閑狀況進(jìn)行有效排序，再通過(guò)Master節(jié)點(diǎn)進(jìn)行協(xié)調(diào)和分配Slave 節(jié)點(diǎn)任務(wù)，進(jìn)而達(dá)到節(jié)點(diǎn)優(yōu)化和提高資源效率的目的。本文結(jié)合MapReduce 模型、動(dòng)態(tài)多因素組合及KNN 分類方法對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行分類及資源配置，以實(shí)現(xiàn)優(yōu)化網(wǎng)絡(luò)負(fù)載均衡的目的。

1 K 近鄰模型

KNN 最近鄰模型［9］是一種比較傳統(tǒng)的分類模型，具有穩(wěn)定、成熟、思路簡(jiǎn)單、易實(shí)現(xiàn)、無(wú)需訓(xùn)練過(guò)程、適合稀疏事件分析處理的機(jī)器學(xué)習(xí)方法之一。KNN 分類模型的原理如下:對(duì)于某一給定的Slave 節(jié)點(diǎn)，在樣本特征空間有K 個(gè)最相似的集合，而這K 個(gè)相似的集合大多屬于同一類別，通過(guò)該算法對(duì)Slave 節(jié)點(diǎn)進(jìn)行聚類。K 近鄰算法在分類上有比較成熟的經(jīng)驗(yàn)，同時(shí)也可以進(jìn)行回歸預(yù)測(cè)。其優(yōu)點(diǎn)為:簡(jiǎn)單、適合多分類問(wèn)題、應(yīng)用范圍廣，因而對(duì)類域的交叉或重疊較多的聚類問(wèn)題，K 近鄰模型更為合適，同時(shí)由于其模型不需要預(yù)先構(gòu)建，故此可以用SQL 語(yǔ)句實(shí)施，操作方便、快捷。同樣，K 近鄰模型由于其自身的特點(diǎn)，也具有一些不足之處，如:最近鄰算法是懶惰的學(xué)習(xí)算法，其計(jì)算都是在線進(jìn)行的，這無(wú)疑增大了算法的時(shí)間復(fù)雜度，并消耗大量的存儲(chǔ)空間。當(dāng)兩類樣本容量相差懸殊時(shí)，通過(guò)K 近鄰模型預(yù)測(cè)可能會(huì)造成誤判，從而降低其準(zhǔn)確率。為了保證算法的準(zhǔn)確性，實(shí)驗(yàn)時(shí)需要大量訓(xùn)練數(shù)據(jù)，由于訓(xùn)練數(shù)據(jù)增多，搜索空間加大，給搜索帶來(lái)難度，同時(shí)也會(huì)消耗大量?jī)?nèi)存。距離權(quán)重的計(jì)算方法產(chǎn)生的函數(shù)難以確定，同時(shí)其結(jié)果與K 值數(shù)量存在緊密關(guān)系。KNN 方法基于這樣的前提條件，即預(yù)測(cè)的樣本與其鄰居樣本具有相似的屬性值。

針對(duì)這種情況，我們可以通過(guò)篩選掉分類作用不大的樣本或者采用重新抽樣法使之按某一方向抽取樣本。也可以根據(jù)與該樣本的距離動(dòng)態(tài)匹配權(quán)值。采用這種方式，對(duì)每一個(gè)待分類的樣本都要進(jìn)行權(quán)值計(jì)算，而這些工作都要推遲到分類階段來(lái)完成，因此增加了算法的時(shí)間復(fù)雜度。還可以動(dòng)態(tài)調(diào)整K 值，使其達(dá)到最優(yōu)狀態(tài)。由于KNN 算法需要進(jìn)行點(diǎn)與點(diǎn)之間的距離計(jì)算。為了使算法更加清晰，我們假設(shè)x = (x1，x2，…，xn)，y=(y1，y2，…，yn)，n 為輸入特征的維數(shù)，則兩點(diǎn)之間距離系數(shù)dXY具有如下性質(zhì):

此外，由于對(duì)兩點(diǎn)間距離運(yùn)算方式的不同，動(dòng)態(tài)因素的選擇有如下情況:

(1)絕對(duì)距離(曼哈頓距離，absolute distance):

如構(gòu)造一組數(shù)據(jù):x=matrix(c(0，4，5，3，0，7，6，3)，ncol=2)

其曼哈頓距離為:

(2)歐氏距離(Euclidean distance):

上例數(shù)據(jù)的歐式距離為:

dist(x，method=“euclidean”，diag=T，upper=FALSE)

結(jié)果如下:

(3)明氏距離(Minkowski distance):

當(dāng)r 比較小時(shí)，對(duì)比較小的差異較敏感，適合于相似度很大而差異較小的數(shù)據(jù)分類。

上例數(shù)據(jù)的明式距離為:dist(x，diag=T，method=“minkowski”，p=3)

(4)切比雪夫距離(Chebyshev Distance):

上例數(shù)據(jù)的切比雪夫距離為:

(5)Canberra 距離:

上例數(shù)據(jù)的Canberra 距離為:dist(x，diag=T，method=“canberra”)

(6)馬氏距離(Mahalanobis Distance):

其中s 為樣本協(xié)方差矩陣。

為了保證實(shí)驗(yàn)的準(zhǔn)確性，在實(shí)驗(yàn)中采用馬氏距離實(shí)驗(yàn)法進(jìn)行實(shí)驗(yàn)。根據(jù)具體訓(xùn)練樣本和新數(shù)據(jù)的屬性特點(diǎn)進(jìn)行分類，在K 個(gè)樣本中找到屬于某類最多的樣本，并把這些樣本歸為此類。例如根據(jù)兩個(gè)主要特征權(quán)重為24 個(gè)節(jié)點(diǎn)進(jìn)行分類。

R 語(yǔ)言程序源碼如下:

產(chǎn)生的圖形如圖1 所示。

圖1 兩點(diǎn)關(guān)系圖Fig.1 Two point diagram

圖示結(jié)果顯示通過(guò)KNN 預(yù)測(cè)，其類別為2。

2 算法設(shè)計(jì)與實(shí)現(xiàn)

節(jié)點(diǎn)分類流程如圖2 所示。

圖2 節(jié)點(diǎn)分類流程圖Fig.2 The flow chart of node classification

最小描述模型建立過(guò)程分為以下步驟:

(1)特征集的建立:將Slave 節(jié)點(diǎn)劃分成數(shù)據(jù)屬性，形成屬性向量。

(2)最小化特征集:根據(jù)特征集中節(jié)點(diǎn)屬性的特征向量運(yùn)算，運(yùn)用數(shù)據(jù)挖掘的聚類算法。

(3)對(duì)節(jié)點(diǎn)進(jìn)行分類處理:對(duì)每一對(duì)數(shù)據(jù)(pa，pb)，計(jì)算其屬性相似度，然后取其中的最大值作為該最終相似度，將相似度大于某一閾值的所有節(jié)點(diǎn)分類到一起，形成小世界集合。

(4)規(guī)則模式提煉:根據(jù)文中定義的規(guī)則進(jìn)行小世界集合提煉，從而得到對(duì)應(yīng)的候選描述模式，并記錄下模式出現(xiàn)的次數(shù);選取其中模式出現(xiàn)次數(shù)大于某一閾值的模式加入到描述模式集合。為提高節(jié)點(diǎn)運(yùn)行的效率，必須最小化模式，得到一最小的描述集合，作為節(jié)點(diǎn)的描述模式集合。

(5)模式集成:初始化模式集S，將候選模式集S'中當(dāng)前模式PScurrent與模式集S 中的現(xiàn)有模式匹配，若匹配成功，定義其狀態(tài)為1，否則為0。當(dāng)狀態(tài)為0 時(shí)，表示模式集S 中沒(méi)有此模式，將當(dāng)前模式PScurrent初始化為新的模式PSnew，加入到模式集S 中。若模式狀態(tài)為1，則將模式進(jìn)行歸并處理。

(6)策略優(yōu)化:根據(jù)上述模式，對(duì)特征數(shù)據(jù)進(jìn)行有計(jì)劃的分類處理，使機(jī)器任務(wù)由繁忙節(jié)點(diǎn)向空閑節(jié)點(diǎn)過(guò)渡。

(7)屬性優(yōu)化:由于在進(jìn)行節(jié)點(diǎn)優(yōu)化的過(guò)程中要考慮多種因素，而因素過(guò)多對(duì)分類會(huì)造成一定的影響。在實(shí)驗(yàn)過(guò)程中充分考慮到多因素的相互過(guò)程，以使節(jié)點(diǎn)分類結(jié)果達(dá)到最優(yōu)。

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

本文根據(jù)終端設(shè)備Slave 節(jié)點(diǎn)及網(wǎng)絡(luò)的特點(diǎn)，對(duì)某公司大型數(shù)據(jù)處理系統(tǒng)進(jìn)行監(jiān)控，產(chǎn)生設(shè)備內(nèi)存、空間、CPU 情況等狀態(tài)數(shù)據(jù)。并根據(jù)狀態(tài)數(shù)據(jù)的特點(diǎn)，對(duì)其進(jìn)行標(biāo)準(zhǔn)化處理、字段刪減、類型定義、分箱處理，在此基礎(chǔ)上構(gòu)建模型。最后將該模型運(yùn)用到該數(shù)據(jù)集上，產(chǎn)生相關(guān)分類。其數(shù)據(jù)處理過(guò)程如圖3 所示。

圖3 數(shù)據(jù)處理過(guò)程Fig.3 Data processing

根據(jù)數(shù)據(jù)處理結(jié)果產(chǎn)生分類統(tǒng)計(jì)數(shù)據(jù)，如圖4 所示。根據(jù)其數(shù)據(jù)特點(diǎn)不同該模式被分為十類。其中類一主要反映CPU、I/O、數(shù)據(jù)承載量等使用情況，類二反映內(nèi)存和承載量情況。從圖4中可以看出由于各機(jī)器設(shè)備運(yùn)行的數(shù)據(jù)不同，其執(zhí)行的內(nèi)容也不盡相同。根據(jù)分類情況的描述，Master 能夠較快調(diào)整各節(jié)點(diǎn)設(shè)備，使其能夠進(jìn)行均衡運(yùn)轉(zhuǎn)。

圖4 分類統(tǒng)計(jì)數(shù)據(jù)結(jié)果Fig.4 Classification statistics results

為使研究具有實(shí)用意義，本文所采用的數(shù)據(jù)集為某集團(tuán)公司辦公網(wǎng)絡(luò)，根據(jù)Map-Reduce 模型，將節(jié)點(diǎn)分成Master 和Slave 兩部分，其中Master 節(jié)點(diǎn)主要負(fù)責(zé)監(jiān)控及計(jì)算資源，Slave 負(fù)責(zé)節(jié)點(diǎn)運(yùn)行。根據(jù)Slave 節(jié)點(diǎn)特點(diǎn)，將該數(shù)據(jù)集按照其網(wǎng)絡(luò)使用程度分類為辦公、研發(fā)、運(yùn)維、軟件、硬件、市場(chǎng)、工程、維護(hù)、管理、人事10 個(gè)類別，分為訓(xùn)練集和測(cè)試集兩部分。其中，辦公為25 臺(tái)，研發(fā)為85 臺(tái)，運(yùn)維為44 臺(tái)，軟件為21 臺(tái)，硬件為43 臺(tái)，市場(chǎng)為49 臺(tái)，工程為150 臺(tái)，維護(hù)為28 臺(tái)，管理為22 臺(tái)，人事為20 臺(tái)，總計(jì)為487 臺(tái)。為使算法具有簡(jiǎn)捷性，本文從以上10 類數(shù)據(jù)中選取5類進(jìn)行歸類分析，即研發(fā)、運(yùn)維、硬件、工程、管理。采用決策樹(shù)分類算法、貝葉斯分類算法、神經(jīng)網(wǎng)分類算法、SVM 分類算法與KNN 算法進(jìn)行有效比較，通過(guò)對(duì)比實(shí)驗(yàn)對(duì)各類算法進(jìn)行優(yōu)化性對(duì)比。上述方法構(gòu)造的分類器均在SPSS CLEMENTINE環(huán)境下開(kāi)發(fā)。根據(jù)各機(jī)器設(shè)備屬性信息，結(jié)合分類算法可以構(gòu)造如表1 所示預(yù)測(cè)矩陣。

表1 算法預(yù)測(cè)表Table 1 Algorithm predicting table

在表1 中，1 代表研發(fā)，2 代表運(yùn)維，3 代表硬件，4 代表工程，5 代表管理。

由于考慮到各因素的作用可能影響到機(jī)器節(jié)點(diǎn)的分類，因此需要對(duì)各因素相互作用進(jìn)行分析，其分析結(jié)果如表2 所示。

表2 多因素綜合測(cè)試表Table 2 Multi-factor comprehensive test table

圖5 多模型組合準(zhǔn)確率Fig.5 The combined model accuracy

圖5 為多模型組合準(zhǔn)確率，其中因素A 代表CPU 使用情況、因素B 代表內(nèi)存使用情況、因素C代表進(jìn)程使用情況、因素D 代表I/O 狀況。

為了客觀評(píng)價(jià)此分類系統(tǒng)的性能，實(shí)驗(yàn)時(shí)需要對(duì)評(píng)價(jià)指標(biāo)進(jìn)行評(píng)定，其中最常用的是準(zhǔn)確率和召回率的方法統(tǒng)計(jì)。對(duì)每個(gè)分類的準(zhǔn)確率precision、召回率recall 以及F1 的計(jì)算方式分別如公式(7)(8)(9)所示。

表3 的數(shù)據(jù)信息表明，通過(guò)KNN 分析方法構(gòu)造的分類器準(zhǔn)確率及召回率優(yōu)于決策樹(shù)分類器、貝葉斯分類器、神經(jīng)網(wǎng)分類器及SVM 分類器。

表3 各算法評(píng)估表Table 3 The algorithm evaluation table

4 結(jié)束語(yǔ)

本文使用KNN 算法對(duì)Slave 節(jié)點(diǎn)進(jìn)行分類處理，根據(jù)其分類結(jié)果，與其他方法相比能最先識(shí)別出資源空閑較大的一類機(jī)器，并根據(jù)這類機(jī)器的運(yùn)行狀況，對(duì)Slave 節(jié)點(diǎn)進(jìn)行有效調(diào)控，進(jìn)而優(yōu)化資源負(fù)載均衡，最終提高機(jī)器設(shè)備的最大可用率。實(shí)踐證明，運(yùn)用KNN 算法結(jié)合多因素有機(jī)組合能有效地對(duì)各服務(wù)器節(jié)點(diǎn)進(jìn)行分類，其效果要優(yōu)于其他算法。

［1］毛譽(yù)熹，盧漢成，盧昊.WMN 中一種基于干擾感知的負(fù)載均衡路由協(xié)議［J］.通信技術(shù)，2014(04):401-405.Mao Yu-xi，Lu Han-cheng，Lu Hao.An interfere-nce-aware load balancing routing protocol for wireless Mesh networks［J］.Communications Technology，2014(04):401-405.

［2］鄭相全.一種基于跨層設(shè)計(jì)和蟻群優(yōu)化的自組網(wǎng)負(fù)載均衡路由協(xié)議［J］.電子學(xué)報(bào)，2006，34(7):1199-1208.Zheng Xiang-quan.A cross-layer design and a-nt-colony optimization based load-balancing routing protocol for Ad Hoc networks(CALR-A)［J］.Acta Electronica Sinica，2006，34(7):1199-1208.

［3］Lin Kai，Rodrigues，Joel J P C，et al.Energy efficiency QoS assurance routing in wireless multimedia sensor networks［J］.Systems Journal，IEEE，2011，5(4):495-505.

［4］王敏，李士寧，李志剛.基于蟻群算法的WSN 多路徑負(fù)載均衡路由［J］.計(jì)算機(jī)工程，2011，14:1-4.Wang Min，Li Shi-ning，Li Zhi-gang.Multipath R-outing with load balancing based on ant col-ony algorithm in WSN［J］.Computer Enginee-ring，2011，14:1-4.

［5］尹安，汪秉文，胡曉婭，等.無(wú)線傳感器網(wǎng)絡(luò)負(fù)載均衡路由協(xié)議［J］.華中科技大學(xué)學(xué)報(bào):自然科學(xué)版，2010，38(1):88-91.Yin An，Wang Bing-wen，Hu Xiao-ya，et al.Load balancing routing protocol in wireless sensor network［J］.Journal of Huazhong University of Science and Technology(Natural Science Edition)，2010，38(1):88-91.

［6］Wu Dan，Cai Yue-ming.A cooperative commu-nication scheme based on dynamic coalition formation game in clustered wireless sensor net-works［J］.IEEE Conference on Global Telecommunications(GLOBECOM 2011)，2011:1-6.

［7］阮楊楊，徐恪.異構(gòu)無(wú)線網(wǎng)絡(luò)節(jié)點(diǎn)性能與代價(jià)優(yōu)化部署策略［J］.中國(guó)科技論文，2012，7(7):518-522.Ruan Yang-yang，Xu Ke.Station and relay node deployment strategy for optimizing performance and costs in heterogeneous wireless networks［J］.China Sciencepaper，2012，7(7):518-522.

［8］朱永嬌，閻巍，左偉明.基于遺傳聚類的無(wú)線傳感器負(fù)載均衡路由算法［J］.電子設(shè)計(jì)工程，2011，19(11):4-7.Zhu Yong-jiao，Yan Wei，Zuo Wei-ming.A load balanced wireless sensor network routing algorithm based on genetic clustering algorithm［J］.Electronic Design Engineering，2011，19(11):4-7.

［9］Giuseppe A，F(xiàn)alchi F.KNN based image classification relying on local feature similarity［J］.SISAP，2010:101-108.