基于K-means聚類的WSN能耗均衡路由算法

張海燕，劉 虹

(北京林業大學信息學院，北京100083)

無線傳感器網絡(Wireless Sensor Network，WSN)是由眾多具有通信和計算能力的傳感器節點，以多跳通信、自組織方式形成的網絡［1］。節點間協同工作，實時監測、感知和采集網絡分布區域內監測對象的信息，并通過一跳或多跳的方式將這些感興趣的數據路由至匯聚節點。

目前無線傳感器網絡已經成為研究熱點之一，隨著對無線傳感器網絡的深入研究和廣泛應用，它將深入到人類生活的各個領域(如軍事、工業生產、環境監測、醫療監護等)。由于傳感器節點的電源能量、計算能力和通信能力都非常有限，所以節能路由協議的設計，對無線傳感器網絡來說非常重要［2］。如何高效使用節點的能量，均衡整個網絡的能耗，延長整個網絡的生命周期是無線傳感器網絡研究的重點。研究表明，與平面路由協議相比，分層路由協議能有效將整個網絡的能量負載平均分配到每個傳感器節點中，從而達到降低網絡能源消耗、提高網絡整體生存時間的目的，其中 LEACH［3］(Low Energy Adaptive Clustering Hierarchy)是經典的分層路由協議。

LEACH協議雖然有很多優點，但其自身還存在一些問題，因此對LEACH協議的改進已成為一個研究的重點與熱點。文獻［4］中提出一種能量均衡自適應分簇算法，在簇頭的選舉過程中考慮到了節點的剩余能量，然而，該算法還存在簇頭分布不均勻、所有簇頭直接與基站通信、遠離基站的簇頭能量損耗快的問題。文獻［5］提出一種基于PSO的無線傳感器網絡雙簇頭分簇算法，該算法利用主簇頭完成數據的收集與融合，用副簇頭進行數據傳輸，達到了平衡能量負載的目的，但該算法也存在簇頭分布不均勻的問題。本文根據K-means算法及無線傳感器網絡分簇路由算法的特點，提出了一種新的基于K-means聚類的WSN能耗均衡路由算法(KBECRA)，將K-means算法應用于WSN分簇路由中，在簇內則根據不同的適應值選擇主簇頭和副簇頭。KBECRA算法使得簇結構更加均勻，同時避免了簇頭分布過于集中，或分散在邊緣地區，從而避免簇頭節點能量消耗過快加速簇的死亡。在簇內選擇主副簇頭分工合作，可將能耗分散開，從而延緩簇的死亡時間。KBECRA算法較好地平衡了網絡的能量負載，達到了延長網絡生存周期的目的。

1 LEACH協議研究

1.1 LEACH協議概述

LEACH協議是無線傳感器網絡最早提出的分簇路由協議。LEACH協議的基本思想是通過隨機循環的選舉過程生成簇頭節點，并基于接收信號的強度來形成簇，以簇頭節點作為路由器負責將簇內節點采集到的信息傳輸到基站節點;定期輪換簇頭節點以保證每個節點公平負擔網絡能耗、提高網絡整體生存時間［6］。

LEACH協議的工作過程是周期性的，它采用了“輪”的概念，每輪分為簇的建立階段和穩定數據傳輸階段。

在簇的建立階段，每個節點生成一個0－1之間的隨機數，并計算閾值，如果所生成的隨機數小于閾值，則這個節點被選為簇頭。簇頭節點選定后，向網絡中廣播自己是簇頭的消息，收到簇頭廣播的非簇頭節點根據信號的強度，選擇信號最大的簇頭節點加入，并發送請求加入的數據包。簇形成后，簇頭創造TDMA時序并通知簇內成員節點。

LEACH算法中閾值的計算公式為:

其中，p表示期望的簇頭節點占網絡節點總數的百分比;r表示當前輪數;G表示網絡中最近1/p輪未當選簇頭的節點集合。

在穩定數據傳輸階段，簇內的成員節點按照TDMA時序，在自己的時間槽內，將采集的數據發送給簇頭。簇頭節點將收到的數據進行融合處理，然后將融合后的數據直接發送給基站。

1.2 能量模型

在LEACH協議中，使用的能量模型是第一順序無線電能量模型(First Order Radio Model)［7］。傳感器節點發送k-bit字節所消耗的能量為:

傳感器節點接收k-bit字節所消耗的能量為:

其中，Emp是傳輸功效，Eelec是發送電路和接收電路消耗的能量，由于實際相差很小，將二者簡化為相等。β是由無線電信道決定的常量，d是信號傳輸距離。當傳輸距離小于預先定義的一個閾值時，采用自由空間信道模型，令β=2;當傳輸距離大于這個預先定義的閾值時，使用多路衰減信道模型，令β=4。

1.3 LEACH協議分析

LEACH協議擁有很多優良的性質，其中最主要的優點有:①LEACH協議采用層次結構，路徑的選擇和路由信息的存儲都變得非常簡單，節點不需要存儲大量的路由信息，大大減少了路由控制信息的數量;②簇頭的選擇采用自適應隨機選取機制，使各個節點成為簇頭的機會均等，進一步使得整個網絡的負載相對比較均衡;③LEACH協議中簇的自組織形成使得整個網絡具有良好的擴展性。

雖然LEACH協議擁有很多優點，但其本身還存在一些問題，如:①LEACH協議在簇頭的選擇時沒有考慮到節點的能量，每次選出的簇頭節點不一定是最合適的節點;②LEACH協議中簇頭節點既負責接收簇內成員節點的數據，又負責數據的融合，以及將數據傳輸給基站，所以簇頭節點的開銷較大;③LEACH協議無法保證簇頭節點在空間上均勻分布，簇頭節點可能集中在某一個小區域內或者分布在邊緣，造成成員節點與簇頭節點進行數據傳輸時消耗過多能量;④簇頭與基站之間采用單跳通信，根據能量消耗模型，當距離較大時則能量消耗很大;⑤LEACH協議假設所有節點都能與基站進行直接通信，這使得LEACH協議不能應用于較大區域。

2 基于K-means聚類的WSN能耗均衡路由算法

本文針對LEACH協議存在的在簇頭的選擇時沒有考慮到節點的能量、簇頭節點的能耗較大、簇頭節點可能集中在某一個小區域內或者分布在邊緣、造成成員節點與簇頭節點進行數據傳輸時消耗過多能量等缺點，對其進行改進，從而提出KBECRA算法。新算法在LEACH算法的基礎上，將K-means聚類算法利用到分簇中，在簇內則根據不同的適應值選擇主簇頭和副簇頭。其中，主簇頭負責收集并融合簇內節點的數據，然后將融合后的數據發送給副簇頭，副簇頭將從主簇頭接收到的數據發送給基站。這樣可以在一定程度上將簇頭的能耗分散開，做到能耗均衡從而延長網絡的生命周期。

2.1 網絡模型

本文采用文獻［3］和［8，10］的傳感器網絡模型，此模型具有以下特點:①基站位置固定，在傳感器網絡區域之外;基站的計算資源和能量不受限制，能覆蓋整個網絡;②節點能量有限，初始能量水平相同;節點位置固定或移動范圍和速度很小;③節點能控制傳輸功率，具有全局唯一的表示ID;④節點以固定速率監測環境，定期上報監測數據。

2.2 能量模型

新算法采用與經典LEACH協議一樣的能量模型，即第一順序無線電能量模型。

2.3 算法思想

基于K-means［11］聚類的WSN能耗均衡路由算法是在LEACH協議的基礎上提出的，同樣存在周期性輪，每輪分為兩部分:簇的建立階段和穩定數據傳輸階段。

2.3.1 簇建立階段

在簇的建立階段，節點首先將自己的位置信息和能量信息發送給基站，之后基站利用K-means算法，將區域內所有節點進行聚類分析。利用 K-means算法進行聚類分析的工作過程如下:①首先從m個節點中任選k個節點作為初始聚類中心;②對于其他非聚類中心，則根據與這些聚類中心的相似度，分別將它們分配給與其最相似的聚類中心;③計算每個聚類中所有節點的均值;④不斷重復①至③步驟直到標準測度函數開始收斂為止，最終每個聚類代表一個簇。

分簇工作的流程圖如圖1所示。

由于經典LEACH協議中簇首節點是根據隨機數產生的，沒有考慮節點的剩余能量和位置信息，存在一定的局限性，而且簇首節點的能效開銷較大，可能造成網絡的過早死亡。KBECRA算法針對上述缺陷進行了改進，提出在簇內首先根據閾值選擇出輔助簇頭，再根據不同的適應值選擇主簇頭和副簇頭。輔助簇頭負責告知簇內節點主、副簇頭的id號，主簇頭將接收到的數據進行融合處理，并傳輸給副簇頭，副簇頭負責與基站進行數據傳輸。其中選擇主簇頭的適應值一方面考慮了節點與簇內其他節點之間的距離，因為傳輸距離與能量的消耗密切相關，另一方面考慮了節點的剩余能量，因為主簇頭在接收其他節點發送的數據時要消耗能量。在選擇副簇頭時則考慮的是節點的能量和節點與基站之間的距離。

圖1 分簇階段的流程圖

基于以上描述，參考參考文獻［5］和［12］，提出在選擇主、副簇頭時的適應函數f1和f2如下:

其中，g1表示節點ni的能量;g2表示簇內節點到主簇頭節點平均距離的倒數;m表示簇內節點的個數;CH表示主簇頭;d(ni，CH)表示節點ni到主簇頭節點的距離;g3表示副簇頭節點到基站距離的倒數;BS表示基站;d(ni，BS)表示節點ni到基站節點的距離。g1的定義是為了選擇的主副簇頭具有較多的能量，g2的定義是為了使主簇頭到簇內節點之間的平均距離最小，g3的定義則是為了使副簇頭到基站節點的距離最小。通過α和β可以調節g1和g2兩個因素在適應值函數f1中所占的比重，通過ε和δ可以調節g1和g3兩個因素在適應值函數f2中所占的比重。

輔助簇頭將主簇頭和副簇頭節點的信息發布給簇內所有節點，并為所有節點分配TDMA時隙。

2.3.2 穩定數據傳輸階段

在穩定數據傳輸階段，簇內的成員節點按照TDMA時序，在自己的時間槽內，將數據發送給主簇頭。主簇頭將收到的數據進行融合處理，然后將融合后的數據發送給副簇頭。副簇頭主要負責將數據轉發給基站。

3 仿真與結果分析

本文采用MATLAB對LEACH協議，以及對KBECRA算法進行仿真。根據網絡以及能量模型，設定仿真參數如下:200個傳感器節點隨機分布在200 m×200 m的網絡中，基站位于(200，250)。傳感器節點的初始能量為0.5 J，Eelec=50 nJ/bit，Efs=10 pJ/bit/m2，Emp=0.001 3 pJ/bit/m4，EDA=5 nJ/bit，數據包的長度為 4 000 bit，控制包長度為100 bit。α=0.4，β=0.6，ε=0.4，δ=0.6。仿真結果分別如圖2～圖4所示。

圖2為兩種算法在某一輪的成簇結構圖。其中圖2(a)為KBECRA算法的簇結構圖和主副簇頭分布圖，圖2(b)為LEACH算法的簇結構圖和簇頭分布圖，使用不同的顏色和形狀表示不同的簇，(a)中*代表主簇頭，向右三角形代表副簇頭，(b)中*代表簇頭。由圖2可得，LEACH協議分簇不均勻，有的簇節點過多，這會加劇該簇內簇頭節點的死亡;同時LEACH協議中簇頭可能集中于某一區域或邊緣地區。而KBECRA算法比LEACH協議分簇均勻，簇頭分布也更加均勻，避免了簇頭集中在某一區域或邊緣地區的情況。

圖2 兩種算法的簇結構圖

圖3所示是存活節點圖，反映了隨著時間關系網絡中存活節點的個數。由圖3可以看出，LEACH協議在第271輪開始出現節點死亡，KBECRA在第513輪出現節點死亡;LEACH協議在第650輪有50%的節點死亡，KBECRA算法在第807輪有50%的節點死亡;LEACH協議在第820輪有90%的節點死亡，KBECRA算法在第1100輪有90%的節點死亡。

圖3 網絡中剩余的存活節點數

表1對兩種算法的第1個節點死亡時間，一半節點死亡時間，以及90%節點死亡時間進行了統計。從表1中可以看出，KBECRA算法第1個節點的死亡時間是LEACH算法的1.89倍，一半節點死亡時間是LEACH算法的1.24倍，90%節點的死亡時間是LEACH協議的1.34倍。這表明KBECRA算法使能量消耗更加均勻地分布在所有節點中，避免了單個節點因能量消耗過大而過早死亡，可延長網絡的生命周期。

表1 兩種算法的節點生存時間統計

圖4是網絡的總能耗圖，它反映了在兩種不同算法下，網絡的總能量消耗隨時間的變化關系。由圖4可得，網絡中200個節點的總能量為100 J，LEACH在第271輪開始出現節點死亡，消耗的總能量是 47.42 J，KBECRA 算法消耗的是 36.15 J;LEACH在第650輪時出現50%節點死亡，消耗的總能量是 92.61 J，KBECRA算法消耗的是 78 J;LEACH在第768輪時出現80%節點死亡，消耗的總能量是98.47 J，KBECRA 算法消耗的是87.5 J。

圖4 網絡的總能量消耗

表2是兩種算法的能耗統計表。由表2可以看出，在第271輪KBECRA算法的能耗比LEACH算法的能耗減少了11.27 J，減少的百分比是23.8%;在第650輪KBECRA算法的能耗比LEACH算法的能耗減少了14.6 J，減少的百分比是 15.8%;在第 768 輪 KBECRA算法的能耗比LEACH算法的能耗減少了10.97 J，減少的百分比是11.2%。通過以上數據表明，與經典LEACH協議相比，本文采用的算法有效減少了網絡的總體能量消耗，網絡性能得到了很大的提高。

表2 兩種算法的能耗統計

與LEACH協議相比，KBECRA可以延長網絡生命周期，減少網絡總能耗，是因為該算法將K-means聚類算法利用到分簇中，使得分簇更加均勻，避免了簇頭分布不均勻或集中分布在某一區域的情況，進而減少了簇內節點與簇頭進行數據傳輸時的能耗，同時避免了簇頭節點的能耗過高。在簇內則采用了主、副簇頭的通信方式，這種方式在一定程度上將簇頭的能耗分散開，可以做到能耗均衡，從而延長網絡的生命周期。

4 結論

本文提出基于K-means聚類的WSN能耗均衡路由算法KBECRA，算法通過K-means聚類算法進行分簇，在簇內則根據不同的適應值選擇主副簇頭，較好地平衡了網絡的能量負載，從而達到了延長網絡生命周期的效果。通過仿真實驗證明它具有較好的性能，但是本文主要著眼于能耗均衡和延長網絡生命周期，今后工作的重點是研究算法的延遲以及安全方面，設計具有安全性的能量均衡路由協議。

［1］ 王殊，閻毓杰，胡富平，等.無線傳感器網絡的理論及應用［M］.北京:北京航空航天大學出版社，2007.

［2］ 何延杰，李臘元，邢明彥.WSN中一種能量均衡的分簇路由協議的設計［J］.傳感技術學報，2009，22(10):1513－1514.

［3］ Heinzelman W R.Energy-Efficient Communication Protocol for Wireless Microsensor Networks［C］//Proceedings of the 33rd Hawaii International Conference On System Sciences.［S.1.］:IEEE Computer Society，2000.

［4］ 杜玉紅，張曉敏，蔡成聞.無線傳感器網絡能耗均衡自適應分簇算法［J］.傳感技術學報，2007，20(7):1616－1619.

［5］ 韓冬雪，張瑞華，劉丹華.基于PSO的無線傳感器網絡雙簇頭分簇算法［J］.計算機工程，2010，36(10):100－102.

［6］ 樂世成，王培康.無線傳感器網絡中的節能路由算法［J］.計算機工程，2008，34(7):113－114，117.

［7］ 祝華君.基于LEACH的無線傳感器網絡路由協議研究［D］.武漢:武漢理工大學，2009.

［8］ KuIik J，Heinzelman W R，Balakrishnan H.Negotiation-Based Protocols for Disseminating Information in Wireless Sensor Networks［J］.Wireless Net-works，2002，8:169－85.

［9］ Intanagonwiwat C，Govindan R，Estrin D.Directed Diffusion.A Scalable and Robust Communication Paradigm for Sensor Networks［C］//Proc.6th Annual Int’I.Conf.Mobile Com.and Net，Aug.2000，56－67.

［10］ Lindsey S，Raghavendra C，Sivalingam K M.Data Gathering Algorithms in Sensor Networks using Energy Metrics［J］.IEEE Trans.Parallel and Distribute.Sys，Sept.2002，13(9):924－35.

［11］ Wei Peng，David J Edwards.K-Means Like Minimum Mean Distance Algorithm for Wireless Sensor Networks［C］//2010 2nd International Conference on Computer Engineering and Technology.2010 IEEE:120－124.

［12］ Abdul Latiff N M，Tsimenidis C C，Sharif B S.Energy-Aware Clustering for Wireless Sensor Networks Using Particle Swarm Optimization［C］//The 18th Annual IEEE International Symposium on Personal，Indoor and Mobile Radio Communications.2007.