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

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

0 引 言

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

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

1 K 近鄰模型

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

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

此外，由于對兩點間距離運算方式的不同，動態(tài)因素的選擇有如下情況:

(1)絕對距離(曼哈頓距離，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):

當r 比較小時，對比較小的差異較敏感，適合于相似度很大而差異較小的數(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é)方差矩陣。

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

R 語言程序源碼如下:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實驗仿真與分析

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

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

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

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

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

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

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

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

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

圖5 多模型組合準確率Fig.5 The combined model accuracy

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

為了客觀評價此分類系統(tǒng)的性能，實驗時需要對評價指標進行評定，其中最常用的是準確率和召回率的方法統(tǒng)計。對每個分類的準確率precision、召回率recall 以及F1 的計算方式分別如公式(7)(8)(9)所示。

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

表3 各算法評估表Table 3 The algorithm evaluation table

4 結(jié)束語

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

［1］毛譽熹，盧漢成，盧昊.WMN 中一種基于干擾感知的負載均衡路由協(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è)計和蟻群優(yōu)化的自組網(wǎng)負載均衡路由協(xié)議［J］.電子學(xué)報，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 多路徑負載均衡路由［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ǎng)絡(luò)負載均衡路由協(xié)議［J］.華中科技大學(xué)學(xué)報:自然科學(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ǎng)絡(luò)節(jié)點性能與代價優(yōu)化部署策略［J］.中國科技論文，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］朱永嬌，閻巍，左偉明.基于遺傳聚類的無線傳感器負載均衡路由算法［J］.電子設(shè)計工程，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.