張海燕，劉 虹

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

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

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

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

1 LEACH協(xié)議研究

1.1 LEACH協(xié)議概述

LEACH協(xié)議是無線傳感器網(wǎng)絡(luò)最早提出的分簇路由協(xié)議。LEACH協(xié)議的基本思想是通過隨機循環(huán)的選舉過程生成簇頭節(jié)點，并基于接收信號的強度來形成簇，以簇頭節(jié)點作為路由器負責將簇內(nèi)節(jié)點采集到的信息傳輸?shù)交竟?jié)點;定期輪換簇頭節(jié)點以保證每個節(jié)點公平負擔網(wǎng)絡(luò)能耗、提高網(wǎng)絡(luò)整體生存時間［6］。

LEACH協(xié)議的工作過程是周期性的，它采用了“輪”的概念，每輪分為簇的建立階段和穩(wěn)定數(shù)據(jù)傳輸階段。

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

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

其中，p表示期望的簇頭節(jié)點占網(wǎng)絡(luò)節(jié)點總數(shù)的百分比;r表示當前輪數(shù);G表示網(wǎng)絡(luò)中最近1/p輪未當選簇頭的節(jié)點集合。

在穩(wěn)定數(shù)據(jù)傳輸階段，簇內(nèi)的成員節(jié)點按照TDMA時序，在自己的時間槽內(nèi)，將采集的數(shù)據(jù)發(fā)送給簇頭。簇頭節(jié)點將收到的數(shù)據(jù)進行融合處理，然后將融合后的數(shù)據(jù)直接發(fā)送給基站。

1.2 能量模型

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

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

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

1.3 LEACH協(xié)議分析

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

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

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

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

2.1 網(wǎng)絡(luò)模型

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

2.2 能量模型

新算法采用與經(jīng)典LEACH協(xié)議一樣的能量模型，即第一順序無線電能量模型。

2.3 算法思想

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

2.3.1 簇建立階段

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

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

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

圖1 分簇階段的流程圖

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

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

輔助簇頭將主簇頭和副簇頭節(jié)點的信息發(fā)布給簇內(nèi)所有節(jié)點，并為所有節(jié)點分配TDMA時隙。

2.3.2 穩(wěn)定數(shù)據(jù)傳輸階段

在穩(wěn)定數(shù)據(jù)傳輸階段，簇內(nèi)的成員節(jié)點按照TDMA時序，在自己的時間槽內(nèi)，將數(shù)據(jù)發(fā)送給主簇頭。主簇頭將收到的數(shù)據(jù)進行融合處理，然后將融合后的數(shù)據(jù)發(fā)送給副簇頭。副簇頭主要負責將數(shù)據(jù)轉(zhuǎn)發(fā)給基站。

3 仿真與結(jié)果分析

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

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

圖2 兩種算法的簇結(jié)構(gòu)圖

圖3所示是存活節(jié)點圖，反映了隨著時間關(guān)系網(wǎng)絡(luò)中存活節(jié)點的個數(shù)。由圖3可以看出，LEACH協(xié)議在第271輪開始出現(xiàn)節(jié)點死亡，KBECRA在第513輪出現(xiàn)節(jié)點死亡;LEACH協(xié)議在第650輪有50%的節(jié)點死亡，KBECRA算法在第807輪有50%的節(jié)點死亡;LEACH協(xié)議在第820輪有90%的節(jié)點死亡，KBECRA算法在第1100輪有90%的節(jié)點死亡。

圖3 網(wǎng)絡(luò)中剩余的存活節(jié)點數(shù)

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

表1 兩種算法的節(jié)點生存時間統(tǒng)計

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

圖4 網(wǎng)絡(luò)的總能量消耗

表2是兩種算法的能耗統(tǒng)計表。由表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%。通過以上數(shù)據(jù)表明，與經(jīng)典LEACH協(xié)議相比，本文采用的算法有效減少了網(wǎng)絡(luò)的總體能量消耗，網(wǎng)絡(luò)性能得到了很大的提高。

表2 兩種算法的能耗統(tǒng)計

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

4 結(jié)論

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

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

［2］ 何延杰，李臘元，邢明彥.WSN中一種能量均衡的分簇路由協(xié)議的設(shè)計［J］.傳感技術(shù)學報，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］ 杜玉紅，張曉敏，蔡成聞.無線傳感器網(wǎng)絡(luò)能耗均衡自適應(yīng)分簇算法［J］.傳感技術(shù)學報，2007，20(7):1616－1619.

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

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

［7］ 祝華君.基于LEACH的無線傳感器網(wǎng)絡(luò)路由協(xié)議研究［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.