石 閃，施偉斌，朱 蓓

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093)

一種針對(duì)無(wú)線傳感器網(wǎng)絡(luò)LEACH協(xié)議的改進(jìn)算法

石 閃，施偉斌，朱 蓓

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093)

針對(duì)傳統(tǒng)LEACH協(xié)議在簇首選取的隨意性，以及簇首節(jié)點(diǎn)將數(shù)據(jù)以單跳形式傳輸給匯聚節(jié)點(diǎn)造成能耗大的缺點(diǎn)。文中提出了改進(jìn)協(xié)議,該算法在對(duì)簇頭節(jié)點(diǎn)的選擇時(shí)會(huì)將節(jié)點(diǎn)的剩余能量考慮進(jìn)去，會(huì)在選擇剩余能量最多，同時(shí)以其到匯聚節(jié)點(diǎn)距離小的節(jié)點(diǎn)作為下一跳來(lái)傳輸數(shù)據(jù)，以實(shí)現(xiàn)多個(gè)簇之間的路由數(shù)據(jù)傳輸。通過(guò)Matlab仿真可以知道，改進(jìn)后的協(xié)議使整個(gè)傳感器網(wǎng)絡(luò)的能量消耗變得更加均衡，同時(shí)使整個(gè)網(wǎng)絡(luò)的生存時(shí)間得到了15%的延長(zhǎng)。

無(wú)線傳感器網(wǎng)絡(luò)；路由協(xié)議；LEACH；閾值

無(wú)線傳感器網(wǎng)絡(luò)是由眾多被放置在無(wú)人監(jiān)管區(qū)的微型傳感器組成，這些微型傳感器的節(jié)點(diǎn)是通過(guò)無(wú)線通信方式組成無(wú)線自組織網(wǎng)絡(luò)[1]。每個(gè)傳感器節(jié)點(diǎn)由傳感器單元、計(jì)算單元、通信單元和存儲(chǔ)單元構(gòu)成。其可以實(shí)時(shí)地監(jiān)測(cè)和感知環(huán)境，通過(guò)收集、處理，然后將控制信息發(fā)送給用戶。由于傳感器網(wǎng)絡(luò)具有成本較低、能耗不高的特點(diǎn)，被廣泛應(yīng)用于軍事和商業(yè)領(lǐng)域。

無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議是當(dāng)今主要的研究對(duì)象。無(wú)線傳感網(wǎng)絡(luò)局限性就在于電池供電，當(dāng)電池電量消耗完全后，由于傳感器節(jié)點(diǎn)分布的環(huán)境狀況一般較惡劣，此時(shí)電池的能量難以得到補(bǔ)充。因此，現(xiàn)在分簇路由協(xié)議研究的主要方向是如何降低能量的消耗。LEACH協(xié)議是一種低功耗的自適應(yīng)分簇路由協(xié)議，它將整個(gè)無(wú)線傳感器網(wǎng)絡(luò)分為若干領(lǐng)域，簇就是這樣的一個(gè)領(lǐng)域。傳感器網(wǎng)絡(luò)中的普通節(jié)點(diǎn)以及簇頭節(jié)點(diǎn)組成了這樣的一個(gè)簇，這兩類節(jié)點(diǎn)分工也是不同，普通節(jié)點(diǎn)則是將自己監(jiān)測(cè)到數(shù)據(jù)發(fā)送給簇頭節(jié)點(diǎn)，簇頭節(jié)點(diǎn)則是對(duì)它收到的這些信息進(jìn)行融合處理然后再以單跳的方式傳輸給匯聚節(jié)點(diǎn)[2]。

圖1 分簇路由協(xié)議的拓?fù)浣Y(jié)構(gòu)

針對(duì)無(wú)線傳感器的研究已經(jīng)提出了多種路由協(xié)議，LEACH是最先被提出的，后續(xù)還有LEACH-C，Teen和Heed等新的路由協(xié)議被提出來(lái)[3]。

1 LEACH協(xié)議

MIT的Heinzelman等人[4]提出了LEACH協(xié)議。該協(xié)議是通過(guò)簇頭輪換的機(jī)制來(lái)選舉簇頭的。LEACH協(xié)議定義“輪”這樣的一個(gè)概念，簇的形成以及簇內(nèi)數(shù)據(jù)穩(wěn)定傳輸這兩個(gè)階段組成了這樣的一個(gè)輪，在簇形成階段，各節(jié)點(diǎn)隨機(jī)產(chǎn)生的數(shù)字決定的決定其能否成為簇首，這個(gè)隨機(jī)數(shù)是介于0和1之間，如果節(jié)點(diǎn)產(chǎn)生這個(gè)隨機(jī)數(shù)的值比T(n)小，這個(gè)節(jié)點(diǎn)成為簇首節(jié)點(diǎn)。T(n)的運(yùn)算公式如下[5]

(1)

式(1)中，p是節(jié)點(diǎn)期望成為簇首節(jié)點(diǎn)的概率；r表示當(dāng)前的輪數(shù)，此時(shí)G表示在之前(rmod 1/p)輪中沒(méi)有成為簇首的普通節(jié)點(diǎn)的集合。

當(dāng)簇內(nèi)的普通節(jié)點(diǎn)被選舉為簇首節(jié)點(diǎn)時(shí)，它就會(huì)以廣播的形式把消息發(fā)送給傳感器網(wǎng)絡(luò)中的其它節(jié)點(diǎn)，這些節(jié)點(diǎn)會(huì)對(duì)其收到信號(hào)的強(qiáng)弱進(jìn)行判斷，然后選擇收到信號(hào)最強(qiáng)發(fā)送反饋消息也就是期望加入，然后簇首收到消息用發(fā)送允許加入這樣的消息給節(jié)點(diǎn)[6]。簇建立之后簇首會(huì)給簇內(nèi)各個(gè)普通節(jié)點(diǎn)發(fā)送時(shí)間表。簇內(nèi)的普通的節(jié)點(diǎn)是按時(shí)間表給簇頭節(jié)點(diǎn)發(fā)送數(shù)據(jù)，在其它普通節(jié)點(diǎn)向簇頭節(jié)點(diǎn)發(fā)送數(shù)據(jù)式，剩下的普通節(jié)點(diǎn)會(huì)進(jìn)入休眠狀態(tài)，這樣則可以是整個(gè)簇內(nèi)的能量消耗得到降低，但簇首節(jié)點(diǎn)需要持續(xù)地工作，不斷接收來(lái)自普通節(jié)點(diǎn)發(fā)送的數(shù)據(jù)并進(jìn)行融合[7-10]。

圖2 LEACH協(xié)議算法流程圖

LEACH存在如下缺點(diǎn)：(1)簇頭的隨機(jī)選擇會(huì)導(dǎo)致簇頭分布不均勻，能耗不平衡和網(wǎng)絡(luò)穩(wěn)定時(shí)間短；(2)簇頭的數(shù)量是不穩(wěn)定的，因此很難達(dá)到理論上的最佳值；(3)數(shù)據(jù)的簇頭節(jié)點(diǎn)和匯聚節(jié)點(diǎn)之間傳輸使用的是單跳傳輸模式，使靠近匯聚節(jié)點(diǎn)周圍的節(jié)點(diǎn)既要完成數(shù)據(jù)的融合又要完成在各個(gè)簇首之間的數(shù)據(jù)轉(zhuǎn)移，能量消耗較大。

2 傳感器網(wǎng)絡(luò)和簇的搭建

在傳感器網(wǎng)絡(luò)搭建階段，匯聚節(jié)點(diǎn)會(huì)使用一定的功率向整個(gè)網(wǎng)絡(luò)廣播信號(hào)，在傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)收到匯聚節(jié)點(diǎn)發(fā)送的信號(hào)，其會(huì)根據(jù)收到信號(hào)的強(qiáng)度就可以估算他到匯聚節(jié)點(diǎn)的距離[11-15]。整個(gè)網(wǎng)絡(luò)將被劃分為一系列不同半徑的圓形區(qū)域，遠(yuǎn)離匯聚節(jié)點(diǎn)的節(jié)點(diǎn)具有更大的半徑，改進(jìn)的協(xié)議中，會(huì)將節(jié)點(diǎn)的剩余能量考慮進(jìn)去以提高閾值方程的方程，改進(jìn)后的閾值公式如式(2)所示

(2)

式(2)較好地利用了節(jié)點(diǎn)剩余能量，提高了那些剩余能量比較高的節(jié)點(diǎn)成為簇首概率。

改進(jìn)閾值公式成簇過(guò)程如下：候選簇首是由各節(jié)點(diǎn)隨機(jī)產(chǎn)生的數(shù)字決定的。在傳感器網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)都會(huì)隨機(jī)產(chǎn)生一個(gè)數(shù)字，把該數(shù)字和預(yù)先設(shè)定好的閾值作比較，當(dāng)數(shù)字比閾值小的時(shí)候，對(duì)應(yīng)的節(jié)點(diǎn)集合就是候選簇首集合。這個(gè)集合里面的每個(gè)節(jié)點(diǎn)都是候選簇頭節(jié)點(diǎn)。然后根據(jù)之前該算法提出節(jié)點(diǎn)收到匯聚節(jié)點(diǎn)發(fā)送的信號(hào)強(qiáng)度就可以測(cè)出這些候選簇頭節(jié)點(diǎn)與匯聚節(jié)點(diǎn)的距離，由式(3)可以確定競(jìng)爭(zhēng)半徑，當(dāng)候選簇首節(jié)點(diǎn)與匯聚節(jié)點(diǎn)的距離較近時(shí)，就會(huì)使Rc變得更小。這樣簇首可以將更多剩下的能量用來(lái)轉(zhuǎn)發(fā)其它簇首發(fā)來(lái)的消息，這樣就更好地使各個(gè)簇首的能耗變得更加均衡

(3)

簇首節(jié)點(diǎn)的選取取決于本節(jié)點(diǎn)與接受到競(jìng)爭(zhēng)信號(hào)節(jié)點(diǎn)做比較來(lái)確定的，在競(jìng)爭(zhēng)半徑內(nèi)，如果沒(méi)有收到競(jìng)爭(zhēng)信號(hào)，則該節(jié)點(diǎn)直接成為簇首；如果接收到競(jìng)爭(zhēng)信息，則與發(fā)出競(jìng)爭(zhēng)信息的節(jié)點(diǎn)做對(duì)比，如果一個(gè)節(jié)點(diǎn)剩余的能量更多的話，這個(gè)節(jié)點(diǎn)就成為簇首，另外的將變?yōu)槠胀ü?jié)點(diǎn)。如果兩個(gè)節(jié)點(diǎn)能量也是一樣的，就比較它們到匯聚節(jié)點(diǎn)的距離，距離小的成為簇首，剩下變?yōu)槠胀ü?jié)點(diǎn)，接下來(lái)簇首節(jié)點(diǎn)向整個(gè)網(wǎng)絡(luò)發(fā)送其成為簇首的消息。

3 簇間數(shù)據(jù)傳輸協(xié)議

為克服傳統(tǒng)的LEACH協(xié)議的不足，接下來(lái)該算法提出了距離閾值dist。如果想達(dá)到直接對(duì)簇頭節(jié)點(diǎn)和匯聚節(jié)點(diǎn)的通信，那么兩者之間的距離小于閾值dist。每個(gè)節(jié)點(diǎn)會(huì)將包括自己的剩余能量以及距離匯聚節(jié)點(diǎn)距離的消息以廣播的形式發(fā)送給匯聚節(jié)點(diǎn)。簇頭節(jié)點(diǎn)ni接受到來(lái)自簇頭節(jié)點(diǎn)nj發(fā)送的消息，就能夠?qū)⒈舜酥g的距離算出來(lái)。

建立了一個(gè)簇頭多跳路由表，如式(4)

ni.Route={nj|dist(nj,sink)

(4)

式(4)中，在路由選擇設(shè)置里節(jié)點(diǎn)ni是靠近匯聚節(jié)點(diǎn)且剩余能量最大的。傳感器網(wǎng)絡(luò)中的能量主要消耗在數(shù)據(jù)的融合以及數(shù)據(jù)多跳傳輸。對(duì)于前一部分消耗的能量，如果在簇里面的普通節(jié)點(diǎn)發(fā)送L字節(jié)的數(shù)據(jù)給簇頭節(jié)點(diǎn)，此時(shí)簇頭節(jié)點(diǎn)能量的消耗如式(5)

Einternal=LEelec+NLEDA

(5)

在式(5)中，Eelec代表接受一個(gè)字節(jié)數(shù)據(jù)所消耗的能量，Eda代表融合一個(gè)字節(jié)數(shù)據(jù)所消耗的能量，N代表簇里面的節(jié)點(diǎn)數(shù)目。對(duì)于下一部分的能量消耗，如果簇頭節(jié)點(diǎn)ni選擇簇頭節(jié)點(diǎn)nj作為下一跳的時(shí)候。簇頭節(jié)點(diǎn)ni需要傳輸L字節(jié)的數(shù)據(jù)給匯聚節(jié)點(diǎn)。此時(shí)節(jié)點(diǎn)nj就是會(huì)匯聚節(jié)點(diǎn)

Eni-external=LEelec+Lεfsdist(ni,nj)

(6)

Enj-external=2LEelec+Lεfsdist(nj,sink)

(7)

在式(6)和式(7)中，εfs代表放大信號(hào)的倍數(shù)dist(ni,nj)代表兩個(gè)節(jié)點(diǎn)之間的距離;dist(nj，sink)代表簇頭節(jié)點(diǎn)和匯聚節(jié)點(diǎn)的距離;2LEelec能量的消耗代表從簇頭節(jié)點(diǎn)接受LByte的數(shù)據(jù)以及將對(duì)應(yīng)的數(shù)據(jù)傳輸給匯聚節(jié)點(diǎn)。

4 仿真結(jié)果

表1 仿真參數(shù)

在Matlab中的仿真結(jié)果如圖3所示。

圖3 節(jié)點(diǎn)死亡率與實(shí)間的關(guān)系圖

由圖3可知，該算法的協(xié)議與LEACH相比，在生存時(shí)間上有了一定的提高。

5 結(jié)束語(yǔ)

通過(guò)對(duì)LEACH的研究，提出了非均勻、多跳路由、動(dòng)態(tài)的無(wú)線傳感器網(wǎng)絡(luò)協(xié)議，它大幅提高了無(wú)線傳感器網(wǎng)絡(luò)的生命周期。本文提出的簇路由協(xié)議考慮了簇頭的能量消耗和多跳路由的能耗。具有良好的節(jié)能效果。然而，無(wú)線傳感器網(wǎng)絡(luò)的如能量閾值和距離閾值通常依靠經(jīng)驗(yàn)設(shè)置初始參數(shù)，它需要更加精確的數(shù)值。

[1] 秦智超.無(wú)線傳感器網(wǎng)絡(luò)中節(jié)能關(guān)鍵技術(shù)的研究[D].北京:北京郵電大學(xué),2013.

[2] 白鳳娥,李環(huán).能量均衡的無(wú)線傳感器網(wǎng)絡(luò)非均勻分簇算法的研究[J].計(jì)算機(jī)與數(shù)字工程,2012,40(1):28-31.

[3] Akkaya K,Younis M.A survey on routing protocols for wireless sensor networks[J].Ad Hoc Network,2005,3(3):325-349.

[4] 朱蓓,施偉斌.基于LEACH的非均勻分簇改進(jìn)協(xié)議[J].數(shù)據(jù)通信,2015(4):38-42.

[5] 洪薇,胡健,龔代圣,等.一種基于層次的無(wú)線傳感器網(wǎng)絡(luò)非均勻分簇路由協(xié)議[J].計(jì)算機(jī)與現(xiàn)代化,2012,12(1):80-84.

[6] 李成法,陳貴海.一種基于非均勻分簇的無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議[J].計(jì)算機(jī)學(xué)報(bào),2007,30(1):27-36.

[7] 張倩.能量有效的無(wú)線傳感器網(wǎng)絡(luò)LEACH分簇路由協(xié)議的改進(jìn)與仿真[D].武漢:華中師范大學(xué),2007.

[8] 繆強(qiáng),鄭扣根.無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議設(shè)計(jì)研究[J].計(jì)算機(jī)應(yīng)用研究,2004,21(8):33-35.

[9] 任豐原,黃海寧,林闖.無(wú)線傳感器網(wǎng)絡(luò)[J].軟件學(xué)報(bào),2003,14(7):1282-1291.

[10] 陳曉娟,王卓,吳潔.一種基于LEACH的改進(jìn)WSN路由算法[J].傳感技術(shù)學(xué)報(bào),2013(1):116-121.

[11] 李成岳,申鉉京,陳海鵬,等.無(wú)線傳感器網(wǎng)絡(luò)中LEACH路由算法的研究與改進(jìn)[J].傳感技術(shù)學(xué)報(bào),2010(8):1163-1167.

[12] 張華忠,劉志杰,于鵬程.WSN中負(fù)載平衡的LEACH通信協(xié)議研究[J].計(jì)算機(jī)工程與設(shè)計(jì),2007(18):4403-4406.

[13] 胡峰松,肖球.一種基于LEACH的能耗均衡多跳路由算法[J].小型微型計(jì)算機(jī)系統(tǒng),2014(1):70-73.

[14] 馬玉剛,周群彪.基于LEACH的無(wú)線傳感器網(wǎng)絡(luò)節(jié)能算法[J].計(jì)算機(jī)應(yīng)用,2009(6):1514-1516.

[15] 盧先領(lǐng),王瑩瑩,王洪斌,等.無(wú)線傳感器網(wǎng)絡(luò)能量均衡的非均勻分簇算法[J].計(jì)算機(jī)科學(xué),2013(5):78-81.

An Improved Algorithm for LEACH Protocol in Wireless Sensor Networks

SHI Shan，SHI Weibin，ZHU Bei

(School of Optical-Electrical and Computer Engineering，University of Shanghai for Science and Technology，Shanghai 200093, China)

The routing protocols of WSNs are one of the most hottest issues in related researchs fields .In view of the randomness of the traditional LEACH protocol in cluster head selection, and the disadvantages of the cluster head nodes delivering some data to the sink node by single hop, the article puts up with an improved protocol ,this algorithm will think remaining energy over in the select of cluster head.The article will choose the node .Its capacity of remaining energy is the biggest and the distance between it and sink mode is not long.This algorithm chooses it as next jump to realize data transferring between the clusters. Finally,through Matlab simulation ,we know that improved algorithm can make the consumpation of the whole wireless sensor network become more equalized,meanwhile,the lifetime of the network has been extended in 15%.

WSNs; routing protocol; LEACH; threshold

2016- 05- 18

石閃(1990-)，男，碩士研究生。研究方向：無(wú)線傳感器網(wǎng)絡(luò)。施偉斌(1967-)，男，博士研究生。研究方向：無(wú)線傳感器網(wǎng)絡(luò)。朱蓓(1991-)，女，碩士研究生。研究方向：無(wú)線傳感器網(wǎng)絡(luò)。

10.16180/j.cnki.issn1007-7820.2017.04.024

TN926

A

1007-7820(2017)04-095-04