無線傳感器網(wǎng)絡(luò)LEACH協(xié)議的節(jié)能改進(jìn)算法

1、無線傳感器網(wǎng)絡(luò)LEACH協(xié)議的節(jié)能改進(jìn)算法 摘要：通過分析LEACH協(xié)議簇頭選舉算法的運(yùn)行機(jī)制，針對無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)能量有限的問題，提出改進(jìn)的簇頭選舉算法LEACH-I。該算法在簇頭選舉階段將節(jié)點(diǎn)的剩余能量和節(jié)點(diǎn)到簇頭的距離作為簇頭選舉的考慮因素，在數(shù)據(jù)傳輸階段結(jié)合多跳傳輸計算所有節(jié)點(diǎn)在一輪的總能耗，最終推出最佳的簇頭范圍，通過控制簇頭數(shù)量達(dá)到優(yōu)化網(wǎng)絡(luò)性能的目的。仿真結(jié)果表明，改進(jìn)算法均衡了節(jié)點(diǎn)能量的消耗，有效地延長了整個網(wǎng)絡(luò)的生命周期。 關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；LEACH路由協(xié)議；最佳簇頭數(shù);能量消耗 中圖分類號：TP393 An improved energy-saving algori

2、thm based on LEACH in wireless sensor network Abstract: By analyzing the running mechanism of LEACH protocol cluster head election algorithm, aiming at the problem of wireless sensor network node energy limited, to improve the cluster head election algorithm is used to LEACH I. The algorithm in the

3、cluster head election phase of the node residual energy and the distance of the node to the cluster head as the cluster head election consideration, in data transmission phase combined with multiple hops transmission calculation of total energy consumption, all nodes in the round, finally introduced

4、 the best cluster head range, by controlling the number of cluster heads to achieve the purpose of optimizing the network performance. Simulation results show that the improved algorithm balance the node energy consumption and prolong the life cycle of the entire network efficiently.Key words:Wirele

5、ss Sensor Network;LEACH protocol; optimal number of cluster heads;energy consumption0 引言 無線傳感器網(wǎng)絡(luò)（WSN）是由大量傳感器節(jié)點(diǎn)以自組織的方式構(gòu)成的無線網(wǎng)絡(luò)。傳感器節(jié)點(diǎn)通常采用電池供電，其計算和存儲能力十分有限，因此節(jié)能是無線傳感器網(wǎng)絡(luò)的一個重要研究方向3。無線傳感器網(wǎng)絡(luò)的路由協(xié)議主要功能是尋找源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間的優(yōu)化路徑，實(shí)現(xiàn)數(shù)據(jù)分組沿著優(yōu)化路徑正確轉(zhuǎn)發(fā)。其中LEACH （Low Energy Adaptive Clustering Hierarchy，LEACH)路由協(xié)議是最早提出的一個能量利用率

6、較高的分層路由協(xié)議，協(xié)議根據(jù)產(chǎn)生的隨機(jī)數(shù)來選取簇頭，采用分簇的方式，由節(jié)點(diǎn)輪流擔(dān)當(dāng)簇頭，實(shí)現(xiàn)了網(wǎng)絡(luò)能量消耗的均衡45。本文針對LEACH協(xié)議的一些不足，提出一種改進(jìn)算，仿真結(jié)果表明，改進(jìn)后的算法減少了網(wǎng)絡(luò)能量消耗，有效的延長了網(wǎng)絡(luò)壽命。1 LEACH 算法概述LEACH算法是無線傳感器網(wǎng)絡(luò)最早提出的分簇路由協(xié)議，它的執(zhí)行過程是周期性的，LEACH定義了輪的概念，每輪分為簇的建立階段和穩(wěn)定狀態(tài)階段。在簇的建立階段，每個節(jié)點(diǎn)產(chǎn)生一個（0,1）之間的隨機(jī)數(shù)，并把它和閥值T(n)進(jìn)行比較，如果這個數(shù)小于閥值，則該節(jié)點(diǎn)成為簇頭節(jié)點(diǎn)。T(n)的計算公式為： 其中，是簇頭在所有傳感器節(jié)點(diǎn)中所占的百分比，,為

7、網(wǎng)絡(luò)中的簇頭個數(shù)，為網(wǎng)絡(luò)中的節(jié)點(diǎn)總數(shù)，是當(dāng)前的輪數(shù)，是前輪中未當(dāng)選過簇頭節(jié)點(diǎn)的集合。因此，在輪時，。這樣可以確保在每輪，每個節(jié)點(diǎn)有且只能成為一次簇頭。節(jié)點(diǎn)一旦選為簇頭，立即向外廣播自己成為簇頭的消息，其他節(jié)點(diǎn)根據(jù)收到的廣播消息的信號強(qiáng)度決定要加入的簇，最后簇頭為簇內(nèi)節(jié)點(diǎn)創(chuàng)建TDMA時隙表，并將該表發(fā)送給簇內(nèi)節(jié)點(diǎn)。穩(wěn)定階段中，簇內(nèi)節(jié)點(diǎn)按照TDMA表在規(guī)定的時間將采集的數(shù)據(jù)傳送至簇頭。簇頭節(jié)點(diǎn)對所有數(shù)據(jù)進(jìn)行融合并發(fā)送至基站，之后網(wǎng)絡(luò)進(jìn)入下一輪，不斷循環(huán)，每個簇采用不同的CDMA代碼進(jìn)行通信來減少其他簇內(nèi)節(jié)點(diǎn)的干擾6。2. 簇頭選擇的改進(jìn)Leach協(xié)議中所有節(jié)點(diǎn)被選為簇頭的概率是相等的，即使經(jīng)過許多

8、輪之后，不同的節(jié)點(diǎn)能量相差很大，但是他們當(dāng)選為簇頭的概率依然是相等的。在這種情況下會出現(xiàn)一些剩余能量很少的節(jié)點(diǎn)依然被選為簇頭節(jié)點(diǎn)，由于簇頭節(jié)點(diǎn)承擔(dān)的任務(wù)較多，消耗的能量較大，這樣導(dǎo)致此節(jié)點(diǎn)的能量會很快耗盡，出現(xiàn)網(wǎng)絡(luò)“洞點(diǎn)”使得整個網(wǎng)絡(luò)的生存時間變短7。因此，應(yīng)當(dāng)把節(jié)點(diǎn)的剩余能量這個因素作為簇頭選擇的考慮因素。方案一： 結(jié)合Leach的閥值公式再將節(jié)點(diǎn)的剩余能量考慮進(jìn)去，提出改進(jìn)的閥值8為： (2)其中為表示節(jié)點(diǎn)的初始能量，表示節(jié)點(diǎn)的當(dāng)前能量值。這種方法通過節(jié)點(diǎn)的剩余能量來調(diào)節(jié)閥值的大小，可以使剩余能量多的節(jié)點(diǎn)計算的閥值較大，從而使其成為簇頭的機(jī)會更大。但該方法存在的缺陷是：隨著網(wǎng)路的運(yùn)行，節(jié)點(diǎn)

9、的剩余能量都在逐漸減少，閥值也會隨之減小，因此節(jié)點(diǎn)成為簇頭的機(jī)會變得很小，簇頭數(shù)目隨之減少，縮短網(wǎng)絡(luò)的生存時間。方案二：對方案一的不足之處提出了第二種改進(jìn)方案，該改進(jìn)算法是將原Leach節(jié)點(diǎn)隨機(jī)數(shù)的生成區(qū)間（0，1）改為隨網(wǎng)絡(luò)的運(yùn)行而動態(tài)變化的（0，），是未被選為簇頭的節(jié)點(diǎn)的平均剩余能量，是節(jié)點(diǎn)的初始能量。 建立隨能量動態(tài)變化的隨機(jī)數(shù)可調(diào)節(jié)節(jié)點(diǎn)當(dāng)選為簇頭的概率，即使節(jié)點(diǎn)的剩余能量偏低時，也不會影響其成為簇頭的概率，因?yàn)榇藭r節(jié)點(diǎn)產(chǎn)生的隨機(jī)數(shù)也減小，該算法能夠確保每一輪的簇頭數(shù)目總是保持在最佳簇頭個數(shù)范圍之內(nèi)，優(yōu)化了網(wǎng)絡(luò)性能，但該方法節(jié)點(diǎn)需要發(fā)送剩余能量信息，且該值需要不斷更新，會帶來較大的額外開

10、銷。 方案三：針對以上兩個方案存在的弊端，再結(jié)合節(jié)點(diǎn)到基站的距離，提出第三種改進(jìn)方案。Leach協(xié)議中節(jié)點(diǎn)競選簇頭，是通過將節(jié)點(diǎn)產(chǎn)生的隨機(jī)數(shù)和閥值進(jìn)行比較，如果隨機(jī)數(shù)小于閥值，則節(jié)點(diǎn)當(dāng)選為簇頭。所以對簇頭選擇算法進(jìn)行改進(jìn)時，調(diào)節(jié)節(jié)點(diǎn)的隨機(jī)數(shù)或者閥值都可以達(dá)到優(yōu)化簇頭的目的。以下通過對節(jié)點(diǎn)產(chǎn)生的隨機(jī)數(shù)進(jìn)行調(diào)整，均衡節(jié)點(diǎn)成為簇頭的概率，調(diào)節(jié)公式如下： (3) 這種改進(jìn)算法的簇頭選擇與Leach相同，傳感器節(jié)點(diǎn)首先產(chǎn)生一個（0,1）之間的隨機(jī)數(shù)，然后使用節(jié)點(diǎn)的剩余能量、節(jié)點(diǎn)與基站的距離作為參數(shù)對隨機(jī)數(shù)進(jìn)行調(diào)節(jié)。其中表示節(jié)點(diǎn)當(dāng)前的剩余能量；表示節(jié)點(diǎn)的初始能量；、，分別表示節(jié)點(diǎn)到基站的距離、最近和最遠(yuǎn)距

11、離；為是一個預(yù)設(shè)的定值，本文設(shè)定為0.5。根據(jù)的單調(diào)性來調(diào)節(jié)隨機(jī)數(shù)，隨著節(jié)點(diǎn)的剩余能量和節(jié)點(diǎn)到基站的距離的改變而改變。如果節(jié)點(diǎn)剩余能量多且到基站的距離近，那么節(jié)點(diǎn)產(chǎn)生的隨機(jī)數(shù)會相對較小，則小于當(dāng)前閥值的概率會更大，從而此節(jié)點(diǎn)當(dāng)選為簇頭的概率就更大，反之亦然。該算法能夠很好地均衡整個網(wǎng)絡(luò)的能量消耗。3.最佳簇頭數(shù)目的改進(jìn)算法 LEACH 路由協(xié)議最優(yōu)簇頭數(shù)的推導(dǎo)，只考慮了穩(wěn)定傳輸階段的能量損耗，而忽略了建立階段的能量損耗，從而導(dǎo)致節(jié)點(diǎn)加快死亡、網(wǎng)絡(luò)能量利用率低的問題，本文提出了一種改進(jìn)的最優(yōu)簇頭數(shù)計算方法。 該方法根據(jù)所有節(jié)點(diǎn)在一輪消耗的總能量， 推算出了最佳的簇頭數(shù)范圍，通過控制簇頭的數(shù)量來改

12、善網(wǎng)絡(luò)的性能.3.1 Leach協(xié)議節(jié)點(diǎn)的能耗模型 Leach協(xié)議采用一階無線電模型，在無線電的傳輸過程中，信號能量的衰減與發(fā)送端和接收端的距離有關(guān)，定義閾值，表達(dá)式為：。如果距離，則采用自語空間（）模型，如果距離，則采用多徑衰落（）模型9。因此，在距離發(fā)送一條長度比特消息的電臺耗能為： (4) 接收這條消息的耗能為： (5)其中表示電臺電子元器件耗能；、表示信號放大器的放大倍數(shù)。3.2 建立階段的總能耗 假設(shè)節(jié)點(diǎn)總數(shù)為N,隨機(jī)分布在的區(qū)域內(nèi)，簇頭個數(shù)為K。簇頭節(jié)點(diǎn)選定后，會向非簇頭節(jié)點(diǎn)廣播自己成為簇頭的消息，假設(shè)廣播的距離為,為保證簇頭的廣播消息能夠覆蓋網(wǎng)絡(luò)中的大部分節(jié)點(diǎn)，這里采用多徑衰落模

13、型。簇頭廣播一條消息耗能為： (6)未被選為簇頭的節(jié)點(diǎn)根據(jù)收到廣播消息的信號強(qiáng)度決定加入哪個簇，簇頭會收到節(jié)點(diǎn)的加入請求信息。每個簇頭的平均耗能為： (7)簇頭節(jié)點(diǎn)創(chuàng)建TDMA時隙表并發(fā)送給簇成員，簇頭到費(fèi)簇頭的距離用表示，則簇頭消耗的能量為： (8)所以，簇建立階段每個簇頭節(jié)點(diǎn)消耗的能量為： (9)1) 每個非簇頭節(jié)點(diǎn)接收簇頭廣播消息消耗的能量為： (10)2) 向簇頭節(jié)點(diǎn)發(fā)送加入請求消息的耗能為： (11)3) 接收簇頭節(jié)點(diǎn)的TDMA時隙表消耗的能量為: (12）因此簇建立階段每個非簇頭節(jié)點(diǎn)耗能為： （13） 綜上所述，簇建立階段的總能耗為：(14)3.3 穩(wěn)定階段的能量消耗穩(wěn)定階段主要是

14、進(jìn)行數(shù)據(jù)的傳輸，簇內(nèi)成員節(jié)點(diǎn)和簇頭的距離較近，而簇頭和基站的距離相對較遠(yuǎn)，所以本文采用簇內(nèi)單跳簇間多跳的數(shù)據(jù)傳輸策略。假設(shè)在簇頭和基站之間距離較遠(yuǎn)，簇頭節(jié)點(diǎn)要經(jīng)過跳才能到達(dá)基站，設(shè)每跳距離相等，都等于，那么簇頭節(jié)點(diǎn)的三部分耗能分別為：1） 接收簇內(nèi)成員節(jié)點(diǎn)的耗能： (15)2） 若每條數(shù)據(jù)消息的比特數(shù)為,假定數(shù)據(jù)完全累積，故累計融合數(shù)據(jù)的耗能為： (16)3） 簇頭到基站之間采用多跳傳輸，假設(shè)簇頭到中繼節(jié)點(diǎn)的距離為，則，將數(shù)據(jù)發(fā)送給中繼節(jié)點(diǎn)的耗能為: (17)所以,數(shù)據(jù)傳輸階段一個簇頭節(jié)點(diǎn)的總耗能為： (18)同理，中繼節(jié)點(diǎn)將數(shù)據(jù)傳給基站的耗能為： (19) 每個非簇頭節(jié)點(diǎn)的耗能為： (20)

15、所以穩(wěn)定階段的總耗能為： (21) 3.4 最優(yōu)簇頭數(shù)的優(yōu)化算法 一輪運(yùn)行過程中，所有節(jié)點(diǎn)消耗的總能量為建立階段和穩(wěn)定階段的耗能之和，即 (22) 由于的值是不確定的，以下用數(shù)學(xué)期望的方法求簇內(nèi)節(jié)點(diǎn)到簇頭的距離，假設(shè)N個節(jié)點(diǎn)分布在的區(qū)域內(nèi)，則每個簇平均占的面積為,每個簇構(gòu)成的圓形區(qū)域的半徑為,節(jié)點(diǎn)密度設(shè)為，則節(jié)點(diǎn)到簇頭的距離的平方的期望值為： (23)將該值帶入總能量式子中，再對式子對K進(jìn)行求導(dǎo)，令式子等于零，即可得到最佳簇頭數(shù)目k： (24)上式中、均是仿真實(shí)驗(yàn)室中固定的參數(shù)值，所以最佳簇頭個數(shù)由網(wǎng)絡(luò)區(qū)域、傳感器節(jié)點(diǎn)總數(shù)、簇頭節(jié)點(diǎn)發(fā)布廣播消息的距離以及采用多跳傳輸?shù)钠骄鶈翁嚯x和跳數(shù)共同決定

16、。4 仿真與分析 本文使用MATLAB對LECH、LEACH-I和LEACH-II進(jìn)行仿真分析，仿真網(wǎng)絡(luò)含有100個節(jié)點(diǎn)隨機(jī)分布在100*100的區(qū)域，仿真參數(shù)如表1所示。 表1 仿真參數(shù)參數(shù) 數(shù)據(jù)值參數(shù) 數(shù)據(jù)值節(jié)點(diǎn)數(shù)量N 100基站位置 （50,175） d 90m節(jié)點(diǎn)初始能量 0.5J數(shù)據(jù)包大小 500bit 100個傳感器節(jié)點(diǎn)隨機(jī)分布如圖1 圖1-100個傳感器節(jié)點(diǎn)的分布 仿真場景為：在100m×100m的區(qū)域內(nèi)分布了100個傳感器節(jié)點(diǎn)，圖中紅點(diǎn)表示簇頭節(jié)點(diǎn)，黑點(diǎn)表示普通節(jié)點(diǎn)。圖2顯示了網(wǎng)絡(luò)中剩余節(jié)點(diǎn)數(shù)隨著輪數(shù)的變化圖。LEACH-I表示只在原LEACH的基礎(chǔ)上對閥值進(jìn)行改進(jìn)，

17、LEACH-II表示在LEACH-I基礎(chǔ)再將簇頭數(shù)量控制在最佳的范圍內(nèi)。圖2-剩余節(jié)點(diǎn)數(shù)與輪數(shù)的關(guān)系從圖中仿真結(jié)果可以看出，改進(jìn)后LEACH-II的生存曲線明顯優(yōu)于LEACH和LEACH-I。LEACH在第724輪開始出現(xiàn)第一個死亡節(jié)點(diǎn)，而LEACH-II在第1590輪才出現(xiàn)第一個死亡節(jié)點(diǎn)，且整個生存時間遠(yuǎn)遠(yuǎn)大于LEACH和LEACH-I。從而可知，新算法LEACH-II不但延長了網(wǎng)絡(luò)的穩(wěn)定期，而且延長了網(wǎng)絡(luò)的生存時間。5 結(jié)語 本文針對LEACH存在的缺陷提出了一種新的改進(jìn)算法，首先在簇頭選擇階段提出改進(jìn)的閥值和隨機(jī)數(shù)公式，在數(shù)據(jù)傳輸階段，計算一輪所有節(jié)點(diǎn)的總耗能推算出最佳簇頭數(shù)目，通過控制

18、最佳簇頭數(shù)目達(dá)到優(yōu)化網(wǎng)絡(luò)性能的目的，仿真實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的算法均衡了網(wǎng)絡(luò)能耗，有效地延長網(wǎng)絡(luò)的生存周期。6 參考文獻(xiàn)1 陳林星.無線傳感器網(wǎng)絡(luò)技術(shù)與應(yīng)用M.北京：電子工業(yè)出版社，2009.2 蔣陽，孫柳林.WSN中LEACH路由協(xié)議簇頭數(shù)優(yōu)化研究 J.2010911):4251-4254.3 Weber S,Andrews J G,Jindal N.An overview of the transmission capacity of wireless networkJ.IEEE Transactions on Communications,2010,58(12):3593-36004. 4 王郭燕基于分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議研究與改進(jìn)D成都：電子科技大學(xué)，20125 HANDY M J,HAASE M,TIMMERMANN D.Low energy adaptive clustering hierarchy with deterministic cluster-head selectionC/Proceedings of the4th IEEE Conference on Mobile and Wireless Communications Network.Washing,DC：IEEE Comput