李 華，陳 超，盧 令

(1.解放軍第四五二醫(yī)院信息科，成都 610036;2.四川理工學(xué)院自動化與電子信息學(xué)院，四川 自貢 643000)

引 言

近年來，無線傳感器網(wǎng)絡(luò)［1］作為一種全新類型的智能網(wǎng)絡(luò)信息系統(tǒng)，在信息領(lǐng)域迅速發(fā)展。相比于其他短距離無線通信技術(shù)，無線傳感器網(wǎng)絡(luò)具有易部署、成本低、規(guī)模大、自組織等許多優(yōu)點，使得無線傳感器網(wǎng)絡(luò)的研究與應(yīng)用得到了越來越多的重視。但是無線傳感器網(wǎng)絡(luò)中，節(jié)點通常使用電池供電，而其應(yīng)用環(huán)境又使得電池的更換非常困難。所以，想要充分利用節(jié)點有限的計算和存儲能力，就必須有一個好的拓撲控制機制來優(yōu)化網(wǎng)絡(luò)的拓撲結(jié)構(gòu)，以達到節(jié)能和延長網(wǎng)絡(luò)生命周期的目的。

根據(jù)目前國內(nèi)外的研究成果，可將無線傳感器網(wǎng)絡(luò)的拓撲控制分為功率控制和層次控制兩種。功率控制中，要求節(jié)點必須具有較強的存儲和計算能力來維護路由信息，因而只適用于規(guī)模較小的無線傳感器網(wǎng)絡(luò)。而層次控制可有效解決這個問題，網(wǎng)絡(luò)結(jié)構(gòu)具有較好的可擴展性，可用于大規(guī)模部署的傳感器網(wǎng)絡(luò)。LEACH算法(Low Energy Adaptive Clustering Hierarchy)［2］是最早被提出來的較成熟且具有典型性的層次控制算法，該算法通過選舉簇頭來構(gòu)成骨干網(wǎng)［3］，但是簇頭的選擇具有隨機性，會導(dǎo)致簇頭的分布不均勻，不能有效均衡能耗和延長網(wǎng)絡(luò)生命周期，對于此，本文將在簇頭選舉和更新方面對LEACH算法進行改進。

1 經(jīng)典的LEACH算法

LEACH算法通過等概率隨機選擇簇頭，算法的運行過程是周期性的，因此定義了“輪(round)”這個概念，每一次輪循環(huán)包括建簇和數(shù)據(jù)傳輸兩個階段［4］，每一次輪循環(huán)結(jié)束后要重新選舉簇頭節(jié)點，執(zhí)行建簇和數(shù)據(jù)傳輸以保持網(wǎng)絡(luò)節(jié)點的能耗均衡。

1.1 建簇階段

LEACH算法中各節(jié)點輪流擔(dān)任簇頭，每一輪選舉簇頭時，各節(jié)點在0～1之間隨機產(chǎn)生一個數(shù)Ti，同時設(shè)定閾值Tn，若Ti＜Tn，則簇頭由節(jié)點i擔(dān)任［5］。對于已經(jīng)擔(dān)任過簇頭的節(jié)點，設(shè)置Tn=0，于是該節(jié)點在以后各輪中都作為普通節(jié)點。隨著輪數(shù)增加，節(jié)點的閾值Tn將隨著已擔(dān)任過簇頭的節(jié)點數(shù)目的增大而增大，則未擔(dān)任過簇頭的節(jié)點被選為簇頭的概率也就會增大。如果只有一個節(jié)點未擔(dān)任過簇頭，其Tn=1，意味著該節(jié)點一定當(dāng)選。閾值Tn由以下公式確定:

式中，p0是簇頭數(shù)占總節(jié)點數(shù)的百分比，r是當(dāng)前輪數(shù)，rmod(1/p0)是目前為止節(jié)點集合中已當(dāng)選過簇頭的節(jié)點個數(shù)，G是目前為止節(jié)點集合中沒有當(dāng)選過簇頭的節(jié)點的集合。

選舉完簇頭后，簇頭節(jié)點便向全網(wǎng)廣播簇頭消息，消息包含簇頭節(jié)點ID和消息類型的頭部。網(wǎng)內(nèi)其他節(jié)點接收到簇頭消息后，根據(jù)消息強弱來選擇要加入的簇。若節(jié)點i接收到來自某個簇頭節(jié)點消息的信號越強，說明節(jié)點i離該簇頭節(jié)點越近，通信代價也就越小。如果接收到的消息信號強度相當(dāng)，則節(jié)點可以隨機選擇要加入的簇。

若節(jié)點i決定要加入簇j后，需通知簇頭j，即向簇頭j發(fā)送自身ID和簇頭j的ID。

當(dāng)簇頭節(jié)點接收到每個節(jié)點的入簇請求消息后，會建立一個TDMA調(diào)度時間表并將其發(fā)送給每一個簇成員節(jié)點。當(dāng)所有非簇頭節(jié)點都收到時間表后，簇的建立就完成了，隨后便是數(shù)據(jù)傳輸階段。

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

該階段主要是簇內(nèi)節(jié)點按TDMA調(diào)度時間表完成數(shù)據(jù)傳輸任務(wù)。該階段被劃分成為若干個時間長度相等的幀，每個幀又包含若干個時間長度相等的時隙。

所有非簇頭節(jié)點都只在自己所在時隙內(nèi)發(fā)送數(shù)據(jù)，其余時間關(guān)閉自己的無線通信模塊以減少能耗。簇頭節(jié)點要隨時準(zhǔn)備接收成員節(jié)點發(fā)來的數(shù)據(jù)，因此要時刻保持活躍狀態(tài)，簇頭節(jié)點收集所有簇內(nèi)節(jié)點發(fā)來的信息后，對相似信號和噪音信號進行處理和融合，并發(fā)送給匯聚節(jié)點。網(wǎng)絡(luò)持續(xù)工作一個固定的時間段后，將會重新進行簇建立階段和穩(wěn)定的數(shù)據(jù)傳輸階段［6］。

1.3 LEACH算法的缺點

LEACH算法通過構(gòu)建骨干網(wǎng)的方式來進行數(shù)據(jù)多跳傳輸，網(wǎng)絡(luò)的性能得到了很大的提升，但是在某些方面算法還存在一定的局限性。

首先，LEACH算法是基于初始能量相同且均勻分布的網(wǎng)絡(luò)模型研究的。而實際情況很難達到這樣的理想狀態(tài)，節(jié)點的能量和地理位置都將會存在差異，因此LEACH算法無法保證簇頭的均勻分布，從而不能有效地提高網(wǎng)絡(luò)整體性能和生命周期，簇頭節(jié)點負載也不均衡。其次，LEACH算法中，簇頭是隨機選擇的，并未考慮到剩余能量和其他問題，而對于剩余能量不同的節(jié)點，成為簇頭的代價也不同。另外，LEACH算法中，簇頭節(jié)點承擔(dān)任務(wù)重，能耗相對較大，因此簇頭節(jié)點容易失效并造成簇頭頻繁更新，而全網(wǎng)的簇頭選舉會帶來較高的額外頭開銷，這樣的頭開銷將會降低節(jié)點的能量利用率。

2 基于組合加權(quán)的改進算法

2.1 改進算法(M－LEACH)的設(shè)計思想

借鑒Ad Hoc網(wǎng)絡(luò)中的按需加權(quán)分簇算法(AOW)的思想［7-8］，對無線傳感器網(wǎng)絡(luò)的LEACH算法進行改進。在LEACH分簇算法中，簇頭的合理選擇對網(wǎng)絡(luò)的拓撲結(jié)構(gòu)至關(guān)重要，簇頭的選擇是否合理決定了整個無線傳感器網(wǎng)絡(luò)性能的好壞。傳統(tǒng)的LEACH算法通過隨機的方式選擇簇頭，M-LEACH算法主要對簇頭的選舉和簇的更新方式進行改進。

改進算法的主要設(shè)計思想是:在簇頭的選舉階段，把節(jié)點的剩余能量、節(jié)點度數(shù)、節(jié)點的移動性以及節(jié)點與其鄰居節(jié)點之間的平均距離作為簇頭選舉所考慮的因素;簇頭的更新只在簇內(nèi)進行，并不在全網(wǎng)范圍內(nèi)進行更新，局部調(diào)整簇頭可以減少全網(wǎng)選舉簇頭帶來的頭開銷;簇頭的更新使用按需更新簇頭策略，即當(dāng)簇頭節(jié)點的剩余能量小于某個閾值時進行簇頭的重新選舉。

2.2 改進算法描述

在簇頭選舉初始階段，為每一個節(jié)點分配一個權(quán)值W，該權(quán)值衡量了節(jié)點適合充當(dāng)簇頭的程度，權(quán)值W越小的節(jié)點越適合充當(dāng)簇頭。節(jié)點i的權(quán)值W(i)由以下公式計算可得:

其中，E(i)表示節(jié)點i到目前為止已消耗掉的能量，D(i)表示節(jié)點i當(dāng)前的節(jié)點度與網(wǎng)絡(luò)理想節(jié)點度差值的絕對值，M(i)是衡量節(jié)點i移動性的參數(shù)，P(i)表示節(jié)點i到所有鄰居節(jié)點的平均距離，a1、a2、a3、a4分別為四個參數(shù)的權(quán)重。算法的執(zhí)行過程可描述如下:

(1)建簇階段

①首先，根據(jù)網(wǎng)絡(luò)具體情況確定簇頭概率p，所有節(jié)點通過周期性地交換“Hello”消息，可統(tǒng)計出鄰居節(jié)點數(shù)目以及與所有鄰居節(jié)點的距離。

②每個節(jié)點i計算自己已耗能量E(i)。假設(shè)所有節(jié)點擁有相同的初始能量，由于節(jié)點接收和發(fā)送數(shù)據(jù)所消耗能量遠比感知數(shù)據(jù)時所消耗能量大，所以各節(jié)點的已消耗能量由節(jié)點收發(fā)數(shù)據(jù)時消耗能量來計算。

③每個節(jié)點i計算自己的節(jié)點度Di與網(wǎng)絡(luò)理想節(jié)點度D0之差，即

④用每個節(jié)點i的平均移動速度代表節(jié)點的移動性M(i)。

⑤每個節(jié)點i統(tǒng)計其到自己所有鄰居節(jié)點的距離總和Pi(總)，并除以鄰居節(jié)點個數(shù)，得到節(jié)點i到所有鄰居節(jié)點之間的平均距離P(i)。

⑥對每個節(jié)點i計算它的組合權(quán)重W(i)，其中權(quán)重因子 a1、a2、a3、a4滿足a1+a2+a3+a4=1，當(dāng)某個參數(shù)越重要，其權(quán)重因子的值越大。每個節(jié)點依據(jù)自己的權(quán)值W(i)大小設(shè)置一個門限時間，門限時間的大小和W(i)的大小成正比，權(quán)值越小的節(jié)點，為其設(shè)置越短的門限時間。

⑦門限時間到的節(jié)點自動升為簇頭，這意味著權(quán)值越小的節(jié)點就優(yōu)先成為了簇頭，即節(jié)點綜合性能越好，就越容易成為簇頭。若存在節(jié)點權(quán)值相等的情況，即門限時間相同，則選擇ID號較小的那個節(jié)點作為簇頭。

⑧當(dāng)選為簇頭的節(jié)點在全網(wǎng)范圍內(nèi)廣播簇頭消息，若在各自的門限時間內(nèi)，節(jié)點收到了簇頭廣播消息，則根據(jù)廣播消息的信號強弱選擇要加入的簇并向所選簇的簇頭發(fā)送入簇消息，同時取消門限時間。簇頭節(jié)點收到所有入簇消息后，建立一個TDMA調(diào)度時間表，并發(fā)送給簇內(nèi)每個節(jié)點。當(dāng)所有節(jié)點都收到TDMA時間表后，進入穩(wěn)定的數(shù)據(jù)傳輸階段。

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

簇成員節(jié)點按照TDMA時間表將采集數(shù)據(jù)發(fā)送給簇頭節(jié)點，簇頭節(jié)點收集所有成員節(jié)點發(fā)來的信息，對其進行融合處理并轉(zhuǎn)發(fā)給匯聚節(jié)點。簇內(nèi)節(jié)點在TDMA時間表分配給自己的時隙之外關(guān)閉其通信模塊。

(3)簇的更新

①當(dāng)簇頭節(jié)點的能量小于某個閾值Em時，接收簇內(nèi)節(jié)點最后一幀數(shù)據(jù)，簇成員節(jié)點會將自己當(dāng)前的權(quán)值信息和ID號聯(lián)合最后一幀數(shù)據(jù)發(fā)送給簇頭節(jié)點。簇頭節(jié)點比較每個成員節(jié)點的權(quán)值，權(quán)值最小的節(jié)點將當(dāng)選為下一輪的簇頭，簇頭節(jié)點將在簇內(nèi)廣播下一輪簇頭的信息，并把自己設(shè)置為非簇頭節(jié)點。

②簇內(nèi)節(jié)點收到新簇頭節(jié)點信息后，把自己的ID號與新簇頭的ID號進行對比，如果相等則將自己設(shè)置為簇頭。

值得注意的是，第一輪簇頭選舉時，由于所有節(jié)點有著相同的初始能量，所以計算權(quán)值時不考慮已消耗能量。

3 仿真分析

3.1 仿真環(huán)境參數(shù)設(shè)置

仿真區(qū)域為一矩形區(qū)域:500×100 m，隨機放置100個節(jié)點，基站坐標(biāo)為(50 m，50 m)。節(jié)點的通信距離范圍為:1～100 m。其余參數(shù)設(shè)置如下:

(1)整個網(wǎng)絡(luò)是連通的，即不存在獨立部分或者是孤立的節(jié)點。

(2)所有節(jié)點隨機分布且每個節(jié)點都有一個唯一的ID號。

(3)部分節(jié)點具有移動性，即部分節(jié)點在一定時間以后會改變自身坐標(biāo)。

(4)節(jié)點通過廣播“hello”消息來計算鄰節(jié)點數(shù)及其與鄰節(jié)點的距離。

(5)節(jié)點的天線采用全向天線且所有節(jié)點都能接收到來自鄰節(jié)點的消息。

(6)節(jié)點初始能量為 0.5 J，簇頭概率為 0.05，控制包長度為100字節(jié)，數(shù)據(jù)包長度為4000字節(jié)。節(jié)點能量等于0時，標(biāo)記為死亡，并不再進行數(shù)據(jù)的傳輸。

(7)節(jié)點的權(quán)重因子a1、a2、a3、a4滿足a1+a2+a3+a4=1，且考慮到每個影響因素在簇頭選舉過程中的作用程度不同，分別取值為:0.5、0.2、0.2、0.1。同時，只有當(dāng)簇頭的能量下降至充當(dāng)簇頭時能量的百分之七十時，才重新選舉簇頭。

3.2 仿真結(jié)果分析

使用MATLAB對M-LEACH算法進行仿真，并與LEACH算法進行比較分析。

(1)生命周期。也就是網(wǎng)絡(luò)維持正常工作所持續(xù)的時間，本文中將其定義為網(wǎng)絡(luò)從開始工作到節(jié)點存活個數(shù)降至初始節(jié)點數(shù)的50%時所持續(xù)的時間。算法的生命周期仿真結(jié)果如圖1所示。

圖1 網(wǎng)絡(luò)生命周期

由圖1可知，隨著節(jié)點的最大通信距離的增大，改進算法與LEACH算法的網(wǎng)絡(luò)生命周期都在減小，并且，在整個過程中，改進算法的生命周期都優(yōu)于原算法。其原因是:相比于LEACH算法，改進算法選出的簇頭節(jié)點的綜合性能更好，能始終讓剩余能量較多的、節(jié)點移動性較小的、節(jié)點度與理想節(jié)點度之差較小的、與鄰節(jié)點的平均距離較優(yōu)的節(jié)點來擔(dān)任簇頭，使得能量的有效性得到了提高，節(jié)點的負載也更均勻，延長了節(jié)點存活的時間，因此，網(wǎng)絡(luò)生命周期也更長。

(2)節(jié)點平均剩余能量。即網(wǎng)絡(luò)正常工作中，所有節(jié)點的平均剩余能量。節(jié)點平均剩余能量仿真結(jié)果如圖2所示。

圖2 節(jié)點平均剩余能量比較

從圖2可以看出，改進算法的剩余能量要高于LEACH算法，并且隨著輪數(shù)的增加，剩余能量最終都趨于0，即節(jié)點死亡。這是因為，改進算法采用了新的簇頭更新機制，減少了簇頭的更新次數(shù)，從而降低了選舉簇頭帶來的頭開銷，節(jié)約了一定的能耗，同時也有助于延長網(wǎng)絡(luò)的生命周期。

(3)節(jié)點充當(dāng)簇頭的公平性指數(shù)(HFI)。該性能指標(biāo)用來衡量節(jié)點充當(dāng)簇頭的公平性程度，也就是節(jié)點充當(dāng)簇頭的時間相比于所有節(jié)點充當(dāng)簇頭的平均時間的偏離程度。HFI由以下公式計算可得:

其中，ti為節(jié)點i充當(dāng)簇頭的時間，為節(jié)點作為簇頭的平均時間，N為全體節(jié)點數(shù)，V為網(wǎng)絡(luò)中的節(jié)點集合。因此，HFI值越小，節(jié)點在充當(dāng)簇頭方面就越公平。在最好的時候，ti=E(ti)，這時HFI=0。一般情況下，簇頭的能耗遠比普通節(jié)點大，HFI值越小，說明所有節(jié)點越能較均勻地分擔(dān)能耗，也就是所有節(jié)點可以較公平地充當(dāng)簇頭，從而可以有效地延長網(wǎng)絡(luò)生存時間。HFI值越小表示網(wǎng)絡(luò)工作越長的時間才會出現(xiàn)節(jié)點的分區(qū)，因此網(wǎng)絡(luò)的整體性能可以得到更好的維護。節(jié)點充當(dāng)簇頭的公平性指數(shù)的仿真結(jié)果如圖3所示。

圖3 節(jié)點充當(dāng)簇頭的公平性指數(shù)比較

從圖3可以看出，兩算法的HFI值都隨節(jié)點的最大通信距離do的增大而增大，而改進算法的HFI值在整個區(qū)間內(nèi)都比LEACH算法的HFI值要小，說明改進后的算法使得節(jié)點能夠更公平的充當(dāng)簇頭。隨著節(jié)點的最大通信距離增大，造成了節(jié)點之間的沖突域，數(shù)據(jù)傳輸?shù)呐鲎猜试龃?，能量損耗變大，節(jié)點充當(dāng)簇頭的時間變短，以至于頻繁的分簇，簇頭公平性降低，所以HFI值呈上升趨勢。而本算法對簇頭選舉進行了改進，簇頭分布更為合理，能耗也更均勻地分配到所有節(jié)點上，因此，節(jié)點充當(dāng)簇頭的公平性更好。

(4)網(wǎng)絡(luò)負載平衡因子(LBF)。網(wǎng)絡(luò)的負載表現(xiàn)為簇頭處理負載的能力，即簇頭能夠支持的簇的大小。分簇結(jié)構(gòu)中，簇頭將承擔(dān)較多的任務(wù)，能耗較大，因此拓撲控制算法應(yīng)使網(wǎng)絡(luò)的負載盡可能均勻地分配給選出的每個簇頭。某簇頭處理負載的能力可由該簇的大小近似衡量，因此，網(wǎng)絡(luò)負載平衡因子可由簇成員節(jié)點個數(shù)的方差的倒數(shù)來計算:

其中，nh為網(wǎng)絡(luò)中簇頭總數(shù)，xn為簇頭n所在簇的成員節(jié)點個數(shù)，u=(N-nh)/nh為網(wǎng)絡(luò)內(nèi)所有簇的成員節(jié)點的平均個數(shù)，N為網(wǎng)絡(luò)中總節(jié)點數(shù)。若LBF越大，說明網(wǎng)絡(luò)的負載越能均勻地分配給每個簇頭，在負載平衡程度最好時，xn=u，這時LBF趨于無窮大［9］。網(wǎng)絡(luò)負載平衡因子仿真結(jié)果如圖4所示。

圖4 負載平衡因子比較

由圖4可以看出，在整個循環(huán)過程中，改進算法的負載平衡因子明顯高于LEACH算法。在循環(huán)開始時，兩算法的負載平衡因子都較大，隨著輪數(shù)的增加，都呈遞減趨勢，在輪數(shù)r=600后LBF均趨于0。改進算法的LBF較好的原因在于:算法在簇頭選舉時綜合考慮了節(jié)點的多種影響因素，使選出來的簇頭不管在節(jié)點度方面，還是在簇頭與其鄰居節(jié)點的平均距離方面，都優(yōu)于LEACH算法，因此，簇頭分布更均勻，負載的分布也越平衡，從而避免了瓶頸節(jié)點的出現(xiàn)以及網(wǎng)絡(luò)擁塞的情況。

4 結(jié)束語

本文提出了一種基于組合加權(quán)的改進LEACH算法，并對其簇更新方式進行了改進。改進算法在生命周期、節(jié)點平均剩余能量、HFI、LBF上都優(yōu)于LEACH算法。另外，本文中僅對分簇算法進行了改進，后續(xù)研究可對分簇算法與功率控制相結(jié)合的拓撲控制機制做一定的嘗試和研究。

［1］ Estrin D，Govindan R，Heidemann J S，et al.Next century challenges:scalable coordination in sensor networks［C］//Proc of the 5thInternational Conference on Mobile Computing and Networking(MobiCom)，Seattle，Washington，August 15-20，1999:263-270.

［2］ Heinzelman W R，Chandrakasan A，Balakrishnan H.An application-special protocol architecture for wireless microsensor networks［J］.IEEE Transactionson wireless communications，2002，1(4):660-670.

［3］ Gerla M，Tsai J T C.Multicluster，mobile，multimedia radio network［J］.Wireless Networks，1995，1(3):255-265.

［4］劉曉文，閆靜杰，苗 錦，等.礦井無線傳感器網(wǎng)絡(luò)LEACH協(xié)議的改進［J］.煤炭科學(xué)技術(shù)，2009，37(4):46-49.

［5］陳曉娟，王卓，吳浩.一種基于LEACH的改進WSN路由算法［J］.傳感技術(shù)學(xué)報，2013，26(1):116-121.

［6］肖劉軍，鄧 平.一種基于位置和能量的WSN改進分簇協(xié)議［J］.通信技術(shù)，2010，43(8):43-45.

［7］杜國勇，束永安.基于鏈接率的Ad hoc自適應(yīng)按需加權(quán)分簇算法［J］.計算機技術(shù)與發(fā)展，2014，24(1):93-97.

［8］林要華，胡華平.基于軌道預(yù)測自適應(yīng)Ad Hoc分簇算法［J］.計算機工程與科學(xué)，2012，32(2):27-30.

［9］鄭少仁，王海濤，趙志峰，等.Ad hoc網(wǎng)絡(luò)技術(shù)［M］.北京:人民郵電出版社，2005.