基于分類優化的物聯網節點負載均衡策略

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

(1.吉林大學 計算機科學與技術學院，長春130022;2.長春師范大學 計算機科學與技術學院，長春130032;3.吉林農業大學 信息技術學院，長春130118)

0 引 言

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

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

1 K 近鄰模型

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

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

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

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

如構造一組數據:x=matrix(c(0，4，5，3，0，7，6，3)，ncol=2)

其曼哈頓距離為:

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

上例數據的歐式距離為:

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

結果如下:

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

當r 比較小時，對比較小的差異較敏感，適合于相似度很大而差異較小的數據分類。

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

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

上例數據的切比雪夫距離為:

(5)Canberra 距離:

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

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

其中s 為樣本協方差矩陣。

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

R 語言程序源碼如下:

產生的圖形如圖1 所示。

圖1 兩點關系圖Fig.1 Two point diagram

圖示結果顯示通過KNN 預測，其類別為2。

2 算法設計與實現

節點分類流程如圖2 所示。

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

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

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

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

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

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

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

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

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

3 實驗仿真與分析

本文根據終端設備Slave 節點及網絡的特點，對某公司大型數據處理系統進行監控，產生設備內存、空間、CPU 情況等狀態數據。并根據狀態數據的特點，對其進行標準化處理、字段刪減、類型定義、分箱處理，在此基礎上構建模型。最后將該模型運用到該數據集上，產生相關分類。其數據處理過程如圖3 所示。

圖3 數據處理過程Fig.3 Data processing

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

圖4 分類統計數據結果Fig.4 Classification statistics results

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

表1 算法預測表Table 1 Algorithm predicting table

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

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

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

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

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

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

表3 的數據信息表明，通過KNN 分析方法構造的分類器準確率及召回率優于決策樹分類器、貝葉斯分類器、神經網分類器及SVM 分類器。

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

4 結束語

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

［1］毛譽熹，盧漢成，盧昊.WMN 中一種基于干擾感知的負載均衡路由協議［J］.通信技術，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］鄭相全.一種基于跨層設計和蟻群優化的自組網負載均衡路由協議［J］.電子學報，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］尹安，汪秉文，胡曉婭，等.無線傳感器網絡負載均衡路由協議［J］.華中科技大學學報:自然科學版，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］阮楊楊，徐恪.異構無線網絡節點性能與代價優化部署策略［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］.電子設計工程，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，Falchi F.KNN based image classification relying on local feature similarity［J］.SISAP，2010:101-108.