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

1、無(wú)線傳感器網(wǎng)絡(luò)LEACH協(xié)議的節(jié)能改進(jìn)算法 摘要：通過(guò)分析LEACH協(xié)議簇頭選舉算法的運(yùn)行機(jī)制，針對(duì)無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)能量有限的問(wèn)題，提出改進(jìn)的簇頭選舉算法LEACH-I。該算法在簇頭選舉階段將節(jié)點(diǎn)的剩余能量和節(jié)點(diǎn)到簇頭的距離作為簇頭選舉的考慮因素，在數(shù)據(jù)傳輸階段結(jié)合多跳傳輸計(jì)算所有節(jié)點(diǎn)在一輪的總能耗，最終推出最佳的簇頭范圍，通過(guò)控制簇頭數(shù)量達(dá)到優(yōu)化網(wǎng)絡(luò)性能的目的。仿真結(jié)果表明，改進(jìn)算法均衡了節(jié)點(diǎn)能量的消耗，有效地延長(zhǎng)了整個(gè)網(wǎng)絡(luò)的生命周期。 關(guān)鍵詞：無(wú)線傳感器網(wǎng)絡(luò)；LEACH路由協(xié)議；最佳簇頭數(shù);能量消耗 中圖分類號(hào)：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ú)線傳感器網(wǎng)絡(luò)（WSN）是由大量傳感器節(jié)點(diǎn)以自組織的方式構(gòu)成的無(wú)線網(wǎng)絡(luò)。傳感器節(jié)點(diǎn)通常采用電池供電，其計(jì)算和存儲(chǔ)能力十分有限，因此節(jié)能是無(wú)線傳感器網(wǎng)絡(luò)的一個(gè)重要研究方向3。無(wú)線傳感器網(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é)議是最早提出的一個(gè)能量利用率

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

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

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

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

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

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

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

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

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

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

16、。4 仿真與分析 本文使用MATLAB對(duì)LECH、LEACH-I和LEACH-II進(jìn)行仿真分析，仿真網(wǎng)絡(luò)含有100個(gè)節(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個(gè)傳感器節(jié)點(diǎn)隨機(jī)分布如圖1 圖1-100個(gè)傳感器節(jié)點(diǎn)的分布 仿真場(chǎng)景為：在100m×100m的區(qū)域內(nèi)分布了100個(gè)傳感器節(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ǔ)上對(duì)閥值進(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輪開(kāi)始出現(xiàn)第一個(gè)死亡節(jié)點(diǎn)，而LEACH-II在第1590輪才出現(xiàn)第一個(gè)死亡節(jié)點(diǎn)，且整個(gè)生存時(shí)間遠(yuǎn)遠(yuǎn)大于LEACH和LEACH-I。從而可知，新算法LEACH-II不但延長(zhǎng)了網(wǎng)絡(luò)的穩(wěn)定期，而且延長(zhǎng)了網(wǎng)絡(luò)的生存時(shí)間。5 結(jié)語(yǔ) 本文針對(duì)LEACH存在的缺陷提出了一種新的改進(jìn)算法，首先在簇頭選擇階段提出改進(jìn)的閥值和隨機(jī)數(shù)公式，在數(shù)據(jù)傳輸階段，計(jì)算一輪所有節(jié)點(diǎn)的總耗能推算出最佳簇頭數(shù)目，通過(guò)控制

18、最佳簇頭數(shù)目達(dá)到優(yōu)化網(wǎng)絡(luò)性能的目的，仿真實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的算法均衡了網(wǎng)絡(luò)能耗，有效地延長(zhǎng)網(wǎng)絡(luò)的生存周期。6 參考文獻(xiàn)1 陳林星.無(wú)線傳感器網(wǎng)絡(luò)技術(shù)與應(yīng)用M.北京：電子工業(yè)出版社，2009.2 蔣陽(yáng)，孫柳林.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ú)線傳感器網(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