余成波，鄧順華，方　軍，余玉潔

(重慶理工大學(xué) 遠(yuǎn)程測(cè)試與控制研究所，重慶 400054)

基于節(jié)點(diǎn)位置與剩余能量的LEACH協(xié)議優(yōu)化*

余成波，鄧順華，方軍，余玉潔

(重慶理工大學(xué) 遠(yuǎn)程測(cè)試與控制研究所，重慶 400054)

摘要:LEACH協(xié)議在簇頭選舉產(chǎn)生、能耗控制還存在許多問題，為此，對(duì)其產(chǎn)生方式提出改進(jìn)。在原LEACH協(xié)議中加入網(wǎng)絡(luò)中節(jié)點(diǎn)的具體位置信息和網(wǎng)絡(luò)節(jié)點(diǎn)當(dāng)前的剩余能量信息，在簇頭選定階段引入了備選簇頭節(jié)點(diǎn)間距和模擬退火算法。在NS2上的仿真結(jié)果表明:改進(jìn)的LEACH協(xié)議使簇頭節(jié)點(diǎn)的選擇更為合理，整個(gè)網(wǎng)絡(luò)的壽命延長(zhǎng)了50 %，網(wǎng)絡(luò)基站的接收數(shù)據(jù)量提高了175 %。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；LEACH協(xié)議；位置信息；剩余能量；模擬退火算法；NS2

0引言

LEACH[1,2]協(xié)議與其它平面路由協(xié)議相比，在整個(gè)網(wǎng)絡(luò)的生存時(shí)間上有了很大的提升。但LEACH協(xié)議本身還存在很多不足，比如:LEACH協(xié)議在簇頭產(chǎn)生的時(shí)候采用的是隨機(jī)數(shù)原則，沒有結(jié)合節(jié)點(diǎn)本身的位置和剩余能量，這會(huì)導(dǎo)致部分節(jié)點(diǎn)過早死亡，對(duì)延長(zhǎng)網(wǎng)絡(luò)的生存時(shí)間有不利影響。

針對(duì)LEACH協(xié)議的不足,文獻(xiàn)[3,4]中在協(xié)議中考慮了能量因素，在簇頭選擇的時(shí)候選擇能量較多的節(jié)點(diǎn)成為簇頭。文獻(xiàn)[5]中提出先將網(wǎng)絡(luò)區(qū)域進(jìn)行分區(qū)，保證網(wǎng)絡(luò)中各節(jié)點(diǎn)的數(shù)量一致，然后再選擇能量最高的作為簇頭節(jié)點(diǎn)。文獻(xiàn)[6]中采用分級(jí)的方式實(shí)現(xiàn)數(shù)據(jù)逐級(jí)短距離傳輸實(shí)現(xiàn)節(jié)能。文獻(xiàn)[7]中提出的A-LEACH算法是根據(jù)節(jié)點(diǎn)的能量和當(dāng)前幾點(diǎn)的疏密程度選出簇頭節(jié)點(diǎn)。文獻(xiàn)[8]中提出讓冗余節(jié)點(diǎn)進(jìn)行休眠的方式實(shí)現(xiàn)節(jié)能。其他還有許多相應(yīng)的改進(jìn)算法如LEACH-LC[9]，BPSO-LEACH[10]等。

本文在協(xié)議中加入了節(jié)點(diǎn)的剩余能量和位置信息，在選擇備選簇頭時(shí)考慮了備選簇頭的距離因素，最后簇頭節(jié)點(diǎn)的選擇時(shí)引入模擬退火算法，使協(xié)議在簇頭節(jié)點(diǎn)的選擇和延長(zhǎng)網(wǎng)絡(luò)壽命上都有很大提高。

1LEACH 協(xié)議簇頭選舉存在的問題分析

1.1LEACH 協(xié)議的工作流程

LEACH協(xié)議的執(zhí)行過程大體可以分成以下三個(gè)階段：

1)簇頭的選取與簇的形成

各節(jié)點(diǎn)隨機(jī)產(chǎn)生一個(gè)[0,1]的隨機(jī)數(shù)，再將隨機(jī)數(shù)與設(shè)定閾值T(n)進(jìn)行比較，若產(chǎn)生的隨機(jī)數(shù)小于閾值T(n)，則該節(jié)點(diǎn)為本輪的一個(gè)簇頭;否則,為普通節(jié)點(diǎn)。T(n)的值由式(1)確定

(1)

式中p為需要產(chǎn)生簇頭數(shù)量的百分比；n為傳感器節(jié)點(diǎn)的總個(gè)數(shù)；r為當(dāng)前已經(jīng)完成的輪數(shù)；G為最近輪不是簇頭的節(jié)點(diǎn)集合。

節(jié)點(diǎn)被選為簇頭后，利用廣播消息通知周圍的節(jié)點(diǎn)。非簇頭節(jié)點(diǎn)在收到廣播消息后都將簇頭消息存在備選簇頭消息列表中，最后比較各廣播消息的信號(hào)強(qiáng)度，選擇信號(hào)最強(qiáng)的簇頭節(jié)點(diǎn)發(fā)送加入簇請(qǐng)求消息。簇頭節(jié)點(diǎn)根據(jù)請(qǐng)求消息將節(jié)點(diǎn)加入并記錄相應(yīng)的ID信息。

2)時(shí)隙表建立

當(dāng)網(wǎng)絡(luò)完成簇的建立后，各簇頭節(jié)點(diǎn)根據(jù)加入簇的成員節(jié)點(diǎn)個(gè)數(shù)建立TDMA時(shí)隙表，并通過廣播發(fā)送給簇內(nèi)各成員節(jié)點(diǎn)。這樣簇內(nèi)成員只有在自己時(shí)隙時(shí)才給簇頭節(jié)點(diǎn)發(fā)送消息，其他節(jié)點(diǎn)則關(guān)閉天線等待自己的時(shí)隙到來。

3)穩(wěn)定運(yùn)行

完成了時(shí)隙的分配后網(wǎng)絡(luò)就處于一個(gè)穩(wěn)定的狀態(tài)。各網(wǎng)絡(luò)節(jié)點(diǎn)根據(jù)自己的時(shí)隙對(duì)簇頭節(jié)點(diǎn)進(jìn)行數(shù)據(jù)傳輸，簇頭節(jié)點(diǎn)將接收的數(shù)據(jù)進(jìn)行簡(jiǎn)單的融合后傳輸給基站。如此反復(fù)運(yùn)行，達(dá)到一段時(shí)間后，又從新回到簇頭的選取和簇形成階段。

1.2LEACH 協(xié)議簇頭產(chǎn)生存在的問題

LEACH協(xié)議中簇頭的產(chǎn)生依靠隨機(jī)數(shù)的方式，這樣使得所有節(jié)點(diǎn)都有相同的機(jī)會(huì)成為簇頭，這就導(dǎo)致了以下的幾個(gè)問題：

1)被選為簇頭的節(jié)點(diǎn)可能是能量比較少的節(jié)點(diǎn)。若能量比較少的節(jié)點(diǎn)當(dāng)選簇頭節(jié)點(diǎn)這會(huì)加劇節(jié)點(diǎn)的能量消耗，使得節(jié)點(diǎn)過早死亡；同時(shí)在能量比較少的節(jié)點(diǎn)在與基站進(jìn)行通信時(shí)候也會(huì)影響通信的質(zhì)量，導(dǎo)致數(shù)據(jù)的傳輸有誤。

2)因?yàn)榇仡^選擇是隨機(jī)的，當(dāng)選的簇頭節(jié)點(diǎn)有可能出現(xiàn)不均勻或者相對(duì)集中的情況。簇頭節(jié)點(diǎn)不均勻會(huì)使得簇頭節(jié)點(diǎn)所分配的節(jié)點(diǎn)數(shù)不均勻，導(dǎo)致部分簇頭能量消耗很快。這樣也就失去了分層路由協(xié)議本來的意義。如果簇頭節(jié)點(diǎn)相對(duì)集中了，也會(huì)導(dǎo)致其他節(jié)點(diǎn)要完成數(shù)據(jù)傳輸都必須進(jìn)行遠(yuǎn)距離傳輸，這樣不但加大了簇頭節(jié)點(diǎn)的能量消耗，同時(shí)使得整個(gè)網(wǎng)絡(luò)的能量消耗也大大增加了，縮短了整個(gè)網(wǎng)絡(luò)的生存時(shí)間。

3)LEACH協(xié)議在設(shè)計(jì)時(shí)，其理想運(yùn)用狀態(tài)為所有節(jié)點(diǎn)的初始能量和平均消耗均量都相同。但在實(shí)際運(yùn)用中，各節(jié)點(diǎn)因?yàn)榫嚯x的原因和選擇的儲(chǔ)備電源均不可能完全一樣，而且因?yàn)楦鞴?jié)點(diǎn)的數(shù)據(jù)量的差異也會(huì)導(dǎo)致節(jié)點(diǎn)能量消耗的不一樣。所以，LEACH協(xié)議要直接運(yùn)用在實(shí)際傳感器網(wǎng)絡(luò)中還是比較困難的。

2LEACH協(xié)議的改進(jìn)

2.1改變簇頭產(chǎn)生方式

1)當(dāng)前剩余能量高于平均能量節(jié)點(diǎn)才能夠參加簇頭的競(jìng)選。考慮到網(wǎng)絡(luò)節(jié)點(diǎn)的能量不一致和簇頭的能量消耗更多，將節(jié)點(diǎn)的當(dāng)前剩余能量作為簇頭節(jié)點(diǎn)產(chǎn)生的一個(gè)重要標(biāo)準(zhǔn)，這樣能保證整個(gè)網(wǎng)絡(luò)能耗的平均，可有效提高全網(wǎng)節(jié)點(diǎn)的生存時(shí)間。

2)節(jié)點(diǎn)與備選簇頭之間必須大于閾值M才能當(dāng)選備選簇頭?？紤]到簇頭的分布必須平均才有利于全網(wǎng)絡(luò)的節(jié)能，文中引入了備選簇頭節(jié)點(diǎn)距離閾值M，這樣保證了在備選簇頭節(jié)點(diǎn)周邊M的范圍內(nèi)不會(huì)再出現(xiàn)其他的備選簇頭，這樣既可以保證簇頭不會(huì)相對(duì)集中也可以使后面的退火算法的迭代次數(shù)大大減少，加快最優(yōu)解搜索的速度。

3)在備選簇頭產(chǎn)生最后簇頭時(shí)引入模擬退火算法，選出最優(yōu)的備選簇頭作為最后網(wǎng)絡(luò)的簇頭。

2.2改進(jìn)協(xié)議的具體實(shí)現(xiàn)

改進(jìn)LEACH協(xié)議執(zhí)行每一輪流程圖如圖1所示，在協(xié)議開始時(shí)，首先要進(jìn)行的是簇頭的產(chǎn)生，簇頭產(chǎn)生程序流程如圖2所示。協(xié)議開始時(shí)各節(jié)點(diǎn)首先將自己的位置信息和當(dāng)前剩余能量信息發(fā)送給基站，節(jié)奏在接收到各節(jié)點(diǎn)的能量信息后計(jì)算出全網(wǎng)的平均能量并告知各節(jié)點(diǎn)。各節(jié)點(diǎn)根據(jù)自己的情況若大于全網(wǎng)平均能量并且周邊距離M范圍內(nèi)沒有備選簇頭節(jié)點(diǎn),則在[0,1]之間產(chǎn)生一個(gè)隨機(jī)數(shù);若小于設(shè)定閾值T(n),則節(jié)點(diǎn)為備選簇頭節(jié)點(diǎn)。節(jié)點(diǎn)在被選為被選簇頭后將信息發(fā)送給基站和周邊節(jié)點(diǎn)。周邊節(jié)點(diǎn)在得知自己周邊距離M范圍內(nèi)存在備選簇頭節(jié)點(diǎn)時(shí),不在參數(shù)隨機(jī)數(shù)去競(jìng)爭(zhēng)備選簇頭節(jié)點(diǎn)。M的設(shè)定不能太小或太大，太小會(huì)導(dǎo)致最后產(chǎn)生的備選簇頭較多不利于退火算法最后求最優(yōu)解，太大則會(huì)使得部分被選簇頭分布不合理導(dǎo)致最后簇頭的分布不合理。多次實(shí)驗(yàn)表明,M的選取為傳感器區(qū)域的1/15～1/20的時(shí)候得到的效果最佳。

圖1　改進(jìn)LEACH協(xié)議每輪執(zhí)行流程圖Fig 1　Each round execution flow chart of improved LEACH protocol

圖2　改進(jìn)LEACH協(xié)議簇頭產(chǎn)生程序流程圖Fig 2　Flow chart of cluster head generation program of improved LEACH protocol

在確定備選簇頭后，基站利用模擬退火算法計(jì)算選出最優(yōu)簇頭節(jié)點(diǎn)。基站在備選簇頭中選出一組備選簇頭作為最初解，然后對(duì)解中每個(gè)節(jié)點(diǎn)坐標(biāo)產(chǎn)生一個(gè)新的坐標(biāo)。設(shè)原來最初解的坐標(biāo)為(Xi，Yi)，則新解的坐標(biāo)如式(2)所示

(2)

式中rand(-10,10)為在-10～10之間產(chǎn)生一個(gè)隨機(jī)數(shù)，然后在解周邊的隨機(jī)數(shù)范圍內(nèi)尋找新的解，即尋找備選簇頭節(jié)點(diǎn)。如果新產(chǎn)生的備選簇頭坐標(biāo)與之前的均不同，則新產(chǎn)生的備選簇頭坐標(biāo)成為新解。同時(shí)算法會(huì)產(chǎn)生一個(gè)隨機(jī)數(shù)，如果小于指定接收新解概率，則接收新解。新解中的備選簇頭成為最終簇頭。

選定簇頭后，簇頭向外廣播，周邊節(jié)點(diǎn)在收到廣播后根據(jù)自己接收到的不同簇頭發(fā)來廣播的信號(hào)強(qiáng)加入信號(hào)最強(qiáng)的簇頭。簇頭接收到節(jié)點(diǎn)的申請(qǐng)后對(duì)簇內(nèi)的成員進(jìn)行TDMA時(shí)隙分配發(fā)送給簇內(nèi)各成員節(jié)點(diǎn)。完成時(shí)隙分配后網(wǎng)絡(luò)將進(jìn)入穩(wěn)定階段，各成員節(jié)點(diǎn)根據(jù)自己的時(shí)隙分配進(jìn)行數(shù)據(jù)傳輸。簇頭節(jié)點(diǎn)在對(duì)收集的信息進(jìn)行數(shù)據(jù)融合之后發(fā)送給基站。穩(wěn)定時(shí)間完成后又從復(fù)之前的操作進(jìn)入新一輪簇頭節(jié)點(diǎn)的選擇。

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

3.1仿真試驗(yàn)場(chǎng)景與參數(shù)設(shè)定

為了驗(yàn)證文中改進(jìn)協(xié)議的合理性和有效性，文中采用NS2仿真軟件作為仿真平臺(tái)，對(duì)改后的LEACH協(xié)議和原LEACH協(xié)議作了相應(yīng)的對(duì)比。實(shí)驗(yàn)中對(duì)協(xié)議的能量消耗、網(wǎng)絡(luò)的生存時(shí)間以及網(wǎng)絡(luò)數(shù)據(jù)的吞吐量進(jìn)行了比較。表1為實(shí)驗(yàn)的仿真參數(shù)。

表1　仿真參數(shù)

3.2對(duì)比實(shí)驗(yàn)結(jié)果與分析

圖3為協(xié)議改進(jìn)后某一輪的分簇圖，圖中同一顏色代表為一個(gè)分簇。由圖中可以看出實(shí)驗(yàn)中分簇?cái)?shù)量為5，標(biāo)示有CH字樣的為當(dāng)前簇頭或是已經(jīng)當(dāng)選過簇頭，左下角有用字母BS標(biāo)注的節(jié)點(diǎn)為基站。

圖3　改進(jìn)后某一輪分簇圖Fig 3　A round of clustering picture after improvement

圖4為網(wǎng)絡(luò)存活節(jié)點(diǎn)數(shù)隨時(shí)間的變化圖，由圖中看到LEACH協(xié)議中節(jié)點(diǎn)在230～280 s之間節(jié)點(diǎn)的死亡速度非?？欤⒃?80 s附近節(jié)點(diǎn)全部死亡。而改進(jìn)后的協(xié)議50～100 s時(shí)死亡速度比LEACH協(xié)議快，這是由于網(wǎng)絡(luò)前期的計(jì)算量大于LEACH協(xié)議，相對(duì)應(yīng)的能量消耗也大于LEACH協(xié)議，所以前期的死亡速度要快于LEACH協(xié)議。在100 s附近節(jié)點(diǎn)開始緩慢死亡，而且全網(wǎng)的生存時(shí)間由之前的280 s延長(zhǎng)到420 s，提升了50 %的時(shí)間。

圖4　網(wǎng)絡(luò)節(jié)點(diǎn)存活數(shù)目Fig 4　Number of alive node of network

圖5為協(xié)議改進(jìn)前后全網(wǎng)能量消耗的對(duì)比圖，圖中看到240 s附近兩種協(xié)議能量消耗線相交，前期改進(jìn)的協(xié)議能量消耗大于原LEACH協(xié)議。但改進(jìn)后的協(xié)議讓整個(gè)網(wǎng)絡(luò)的生存時(shí)間由之前的280 s延長(zhǎng)到了420 s，大大的延長(zhǎng)了網(wǎng)絡(luò)的壽命。

圖6為基站接收數(shù)據(jù)包對(duì)比圖，由圖中可以看出，改進(jìn)后協(xié)議接收的數(shù)據(jù)包比原協(xié)議接收的數(shù)據(jù)包多接收了700 000個(gè)，效率提升了175 %。

圖5　全網(wǎng)能量消耗Fig 5　Energy consumption of the whole network

圖6　基站接收數(shù)據(jù)包的數(shù)量Fig 6　Amount of data packets received by base station

4結(jié)束語

本文首先分析了LEACH協(xié)議，針對(duì)LEACH協(xié)議的不足，在簇頭的選取時(shí)加入了節(jié)點(diǎn)的位置信息和當(dāng)前剩余能量信息。同時(shí)在備選簇頭的產(chǎn)生時(shí)引入距離因素M，并在備選簇頭產(chǎn)生簇頭時(shí)引入退火算法提出新的改進(jìn)LEACH協(xié)議。NS2的仿真結(jié)果表明:新的改進(jìn)LEACH協(xié)議使協(xié)議的分簇更為合理，同時(shí)有效延長(zhǎng)網(wǎng)絡(luò)壽命并能夠提高網(wǎng)絡(luò)的接收數(shù)據(jù)量。

參考文獻(xiàn):

[1]Heinzelman W,Chandrakasan A,Balakrishnan H.Energy-effi-cient communication protocol for wireless microsensor network-s[C]∥Proc of the 33rd Annual Hawaii Int'l Conf on System Sciences,Maui:IEEE Computer Society,2000:3005-3014.

[2]Lindsey S,Raghavendra C,Sivalingam K.Data gathering in sensor networks using the energy delay metric[C]∥Proc of the IPDPS Workshop on Issues in Wireless Networks and Mobile Computing，2001.

[3]Heinzelman W B.An application-specific protocol architecture for wireless microsensor networks[J].IEEE Transactions on Wireless Communications，2002，10:660-670.

[4]Yang Yang，Bai Enjian，Hu Jia，et al.MRBCH:A multi-path routing protocol based on credible cluster heads for wireless sensor networks[J].J Communications，Network and System Sciences，2010，3:689-696.

[5]Gou Haosong，Yoo Younghwan.An energy balancing LEACH algorithm for wireless sensor networks[C]∥2010 The Seventh International Conference on Information Technology，2010：822-827.

[6]趙菊敏，張子辰，李燈熬.一種無線傳感器網(wǎng)絡(luò)鏈?zhǔn)絺鬏敺执芈酚蓞f(xié)議[J]．傳感器與微系統(tǒng)，2014，33(3):135-138．

[7]劉永超，張?jiān)孪?，繆旻.基于能量和距離的分區(qū)域選擇簇首WSNs 路由算法[J].傳感器與微系統(tǒng)，2015，34(1)：124-127.

[8]魏玉宏，田杰，孔韋韋.一種基于LEACH 協(xié)議高效節(jié)能的數(shù)據(jù)融合算法[J]．傳感器與微系統(tǒng)，2015，34(6):148-151．

[9]馬建樂，楊軍.基于位置和剩余能量的局部集中式LEACH算法研究[J].傳感技術(shù)學(xué)報(bào)，2013,26(8):1147-1158.

[10] 曹欲曉，徐金寶，徐夢(mèng)溪,等.無線傳感器網(wǎng)絡(luò)LEACH協(xié)議的二進(jìn)制粒子群改進(jìn)算法[J].電子技術(shù)應(yīng)用，2015，41(4):91-93.

Optimization of LEACH protocol based on node position and residual energy*

YU Cheng-bo,DENG Shun-hua,FANG Jun,YU Yu-jie

(Institute of Remote Test and Control,Chongqing University of Technology,Chongqing 400054,China)

Abstract:LEACH has many problems in election of cluster head and energy consumption control,aiming at these problems,propose improvement for generation mode of LEACH protocol cluster head.The improved LEACH protocol is to add specific location information of network nodes and current remaining energy information of network node in original LEACH protocol,alternative cluster head node spacing and simulated annealing algorithm are introduced in cluster head selection stage.The simulation results on NS2 show that the improved LEACH protocol makes selection of cluster head more reasonable,and the whole network lifetime is extended 50 %,and amount of receiving data of base station is increased by 175 %.

Key words:wireless sensor networks(WSNs);LEACH protocol;location information;residual energy;simulated annealing algorithm;NS2

DOI:10.13873/J.1000—9787(2016)05—0139—03

收稿日期：2015—10—19

*基金項(xiàng)目：重慶市高校優(yōu)秀成果轉(zhuǎn)化資助項(xiàng)目(KJZH14213)；重慶市科技人才培養(yǎng)計(jì)劃(新產(chǎn)品研發(fā)團(tuán)隊(duì))資助項(xiàng)目(CSJC2013KJRC—TDJS40012)

中圖分類號(hào)：TP 393

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1000—9787(2016)05—0139—03

作者簡(jiǎn)介:

余成波(1965-)，男，江西鄱陽人，博士，教授，博士生導(dǎo)師，主要從事信號(hào)與信息處理、遠(yuǎn)程測(cè)試與控制技術(shù)的研究。