林 蔚， 陳勖之

(哈爾濱工程大學理學院，黑龍江 哈爾濱 150001)

0 引言

近年來，無線傳感器網(wǎng)絡技術得到迅猛地發(fā)展，并且受到了普遍重視，作為一種新型網(wǎng)絡技術，它的產生和發(fā)展對現(xiàn)代網(wǎng)絡技術造成了極其深遠的影響[1].本文中，無線傳感器網(wǎng)絡的研究主要是針對以下幾個特性進行的:能源有效性;生命周期;容錯性[2].由于在無線傳感器網(wǎng)絡中傳感器節(jié)點是能源有限的，所以讓有限的能源得到高效的利用，延長的網(wǎng)絡生存時間有積極意義[3].無線傳感器網(wǎng)絡的容錯機制，能達到延長網(wǎng)絡生命這一目的.改善其容錯能力，對無線傳感器網(wǎng)絡發(fā)展和應用都具有十分重要的意義[2].

Leach算法是無線傳感器網(wǎng)絡的一種傳統(tǒng)經典的分簇算法，有極強的代表性.Leach在循環(huán)的分簇機制下，不斷地執(zhí)行簇的重構過程.但是，Leach算法在一些突發(fā)情況發(fā)生時，缺乏有效的容錯能力，因此本文針對Leach算法在出現(xiàn)部分節(jié)點突然死亡的情況，使用一種靜態(tài)容錯模型[4]，本文提出了一種改進的Leach算法(τ－Leach算法).通過平衡突發(fā)事件發(fā)生前后節(jié)點的能量，根據(jù)死亡節(jié)點數(shù)，給出一個系數(shù)τ，改變準入節(jié)點成為簇頭的閾值，來實現(xiàn)延長突發(fā)情況下網(wǎng)絡存在時間.

1 Leach算法及存在問題

1.1 Leach算法

Heinzelman等人在[5]中提出了 Leach算法.Leach定義了“輪”的概念，工作“輪”由初始化和穩(wěn)定工作階段組成.算法中閾值T(n)的計算公式十分重要，按等式(1)計算:

在上式(1)中，p=k/N，n為網(wǎng)絡中傳感器節(jié)點數(shù)，p為一輪中需要的簇頭節(jié)點的百分數(shù)，k為一輪中網(wǎng)絡中的簇數(shù)，r為當前的輪數(shù)，G為之后1/p輪中沒有成為簇頭的傳感器節(jié)點組成的集合.各個節(jié)點依照閾值T(n)進行分簇.簇構建完成，數(shù)據(jù)通信便開始，網(wǎng)絡進入穩(wěn)定階段.節(jié)點采集監(jiān)測數(shù)據(jù)，并將采集數(shù)據(jù)發(fā)送給簇頭.當一輪的數(shù)據(jù)傳輸完畢后，簇頭節(jié)點會對數(shù)據(jù)進行處理，然后發(fā)送到sink節(jié)點，一段時間后，進入下一工作輪.

1.2 存在問題

因為無線傳感器網(wǎng)絡應用廣泛，特別是在軍事國防、環(huán)境監(jiān)測、交通管理等方面有重要作用.在實際應用中會出現(xiàn)如下情況:當網(wǎng)絡工作到某一輪rx時，在網(wǎng)絡分布區(qū)域內，因為某些原因導致部分區(qū)域內的節(jié)點死亡.死亡節(jié)點帶有的能量被無端損耗，在網(wǎng)絡中其能量應視為0.這時，按照原有的閾值設計原理，不可避免的在(1/p－1)輪中出現(xiàn)下述情形:在這些節(jié)點中，必然存在在原各自周期內從未成為簇頭的節(jié)點.然而按照原有的閾值設計原理，這些節(jié)點的損耗占總損耗節(jié)點的比例勢必影響剩余節(jié)點選舉簇頭的周期性規(guī)律.但若原有閾值仍維持不變將導致錯誤的簇頭選舉規(guī)律，從而導致之后的周期性簇頭產生所占比例過多或過少，不能均衡承擔網(wǎng)絡工作負擔，不能適應改變后的節(jié)點和簇頭的比例，進而導致節(jié)點能量消耗加快.

2 τ－Leach協(xié)議分簇算法

2.1 τ－Leach算法的設計思路

τ－Leach算法，是針對上述問題而提出對Leach算法的一種改進，是在Leach算法在工作到某一輪rx時，突然出現(xiàn)一個區(qū)域內全部節(jié)點突然死亡的情況下，通過引入一個系數(shù)τ，調整Leach算法的閾值T(n)為τ*T(n)，使得節(jié)點成為簇頭的概率發(fā)生改變，調整每輪產生的簇頭的個數(shù)，優(yōu)化簇的個數(shù)和剩余節(jié)點的比例，以使網(wǎng)絡在新狀態(tài)下的生存時間達到最優(yōu)化.

2.2 τ的確定

τ－Leach算法，也是基于各節(jié)點能量的消耗前后保持均衡為前提考慮的，不可避免的，我們要根據(jù)在Leach算法中，節(jié)點能量的消耗作出調整.假設在一確定區(qū)域內均勻分布著N個節(jié)點，如果每輪生成k個簇，每個簇內約有N/k個節(jié)點.首先，考察每個簇頭節(jié)點能量消耗.因為簇頭離基站較遠，所以采用能量損耗適用多徑衰落信道模型(d4功率損耗)[6].每個簇頭節(jié)點的能量損耗為:

然后，再考察每個非簇頭節(jié)點能量消耗.通信消耗采用 Friss自由空間衰落模型(d2功率損耗)[6－7].每個非簇頭節(jié)點消耗的能量為:

其中，l是每個數(shù)據(jù)流的bits數(shù)，dtoBS是簇頭節(jié)點到sink的距離，dtoCH是非簇頭節(jié)點與簇頭之間的距離，EDA是簇頭數(shù)據(jù)處理能量消耗，εmp，εfs是信號放大倍數(shù).

通過以上兩式不難看出，當rx輪有節(jié)點突然死亡的情況發(fā)生，即N，k發(fā)生變化時，對非簇頭節(jié)點能量消耗并無影響，只需要保證輪rx前后

其中，k'和N'是變化后的簇頭數(shù)和節(jié)點數(shù)，k'=(k/N)(N－ΔN)，ΔN為rx輪中損耗的節(jié)點數(shù)，就可以保證每個節(jié)點能量消耗大致平衡.

Leach算法中，平均N/k輪中每個節(jié)點都可以成為一次簇頭.這樣，某一個節(jié)點i，在第r輪被選為簇頭節(jié)點的概率為:

由上式可知，在前r輪中，沒有擔任過簇頭的節(jié)點數(shù)期望為N－k*[r mod(N/k)].在N/k輪后，所有節(jié)點均已經當選過一次簇頭，在接下來的工作輪中，它們又可以繼續(xù)當選簇頭.由式(2)得.

其中Δn為rx輪時，損耗的前中從未成為簇頭的節(jié)點.

2.3 τ－Leach算法工作機制

工作開始，基站的位置，網(wǎng)絡節(jié)點的部署，每個節(jié)點所帶有的能量確定.開始初始化，能量的消耗情況等均滿足Leach算法的設定，并且按照Leach算法的工作機制工作.

當?shù)竭_某一輪rx時，發(fā)生某一區(qū)域內節(jié)點死亡的情況，各簇統(tǒng)計損失的節(jié)點數(shù) N以及 rxmod(N/k)輪中從未成為簇頭的節(jié)點數(shù)n，并計算閾值T'(n)=τ*T(n).之后的輪中，網(wǎng)絡的工作機制不發(fā)生改變，依舊按照Leach算法進行分簇，但是要采用新的閾值來篩選簇頭節(jié)點.

圖1 網(wǎng)絡節(jié)點存活個數(shù)與工作輪數(shù)關系(b為a的局部放大圖)

3 τ－Leach算法仿真實驗

3.1 仿真環(huán)境

節(jié)點為100個且隨機的分布在100m*100m范圍內，每個節(jié)點的初始能量相同，每個節(jié)點在每一輪向自己的簇頭節(jié)點傳輸?shù)臄?shù)據(jù)為4000b，基站位置為(50，150).本文對Leach和τ－Leach算法進行了仿真實驗并比較.仿真參數(shù)如下表所示，實驗在Matlab實驗平臺進行.并有如下表格中的假設.

表1 各仿真參數(shù)值假設

0.1 E elec 50 n J/b i t ε fs 10 p J/(b i t m 2)ε mp 0.0013 p J/(b i t m 4)E DA 5 n J/b i t數(shù)據(jù)包規(guī)格 500 b y t e s每輪時間p 8 s

3.2 存活節(jié)點數(shù)與工作輪數(shù)關系

圖1是網(wǎng)絡節(jié)點存活個數(shù)與工作輪數(shù)關系.因為在第rx輪時出現(xiàn)了節(jié)點損失，所以出現(xiàn)了明顯的圖像反映.rx=123輪后，Leach算法第一個節(jié)點死亡大約在第438輪，τ－Leach算法一個節(jié)點死亡大約是在464輪，τ－Leach算法比Leach算法提高網(wǎng)絡壽命大約8.3%.

4 結論

本文根據(jù)無線傳感器網(wǎng)絡Leach算法容錯能力的缺陷，基于能量提出一種改進算法——τ－Leach算法，并且在Matlab實驗平臺進行測試.根據(jù)測試實驗結果的顯示，新算法雖然簡單，但在一定區(qū)域內發(fā)生節(jié)點突然死亡的突發(fā)事件時，新算法效果明顯.采用τ－Leach算法能夠更加均勻地將能量消耗分配到所有節(jié)點上，網(wǎng)絡的節(jié)能和延長網(wǎng)絡生存時間更具優(yōu)勢.

[1]Holger K，Andreas W.Protocols and Architectures for Wireless Sensor Networks[M].John Wiley＆ Sons，2006:94－128.

[2]馬闖.無線傳感器網(wǎng)絡容錯關鍵技術研究[D].黑龍江哈爾濱:哈爾濱工業(yè)大學，2011.

[3]Akyildiz I，Kasimoglu I.Wireless Sensor and Actor Networks Research Challenges[J].Ad Hoc Networks，2004，2(4):351－367.

[4]馬建偉，李銀伢.滿意PID控制設計理論與方法[M].北京科學出版社，2007:1－3.

[5]Heizelman W，Chandrakasan A，Balakrishnan H.An Application Specific Protocol Architecture for Wireless Microsensor Networks[J].IEEE Transactions on Wireless Networking，2002，1(4):660－670.

[6]Mischa D，Yonghui L.孫卓，趙慧，彭岳星(譯).協(xié)同通信:物理層、信道模型和系統(tǒng)實現(xiàn)[M].機械工業(yè)出版社，2011:38－55.

[7]陳友榮，俞立，董齊芬，洪榛.基于近鄰算法的無線傳感器網(wǎng)絡功率控制[J].浙江大學學報(工學版)，2010，44(7):1321－1326.