閆海云+吳韶波

摘 要：無線傳感器網(wǎng)絡(luò)（WSN）是由能量有限的傳感器節(jié)點組成，因此，高效節(jié)能和延長網(wǎng)絡(luò)生命周期顯得尤其重要。 LEACH 路由算法是能量有效、基于層次結(jié)構(gòu)的經(jīng)典路由算法，但它存在簇頭選擇不合理和能耗不均衡等缺點。針對以上缺點，提出路由改進(jìn)算法 —CN-LEACH。根據(jù)節(jié)點的位置信息對節(jié)點進(jìn)行分簇，在簇內(nèi)運用新的閾值來選擇簇首，最后采用單跳和多跳相結(jié)合的方式進(jìn)行數(shù)據(jù)傳輸。通過Matlab仿真比較說明，與LEACH相比，CN-LEACH算法能夠有效地延長網(wǎng)絡(luò)的生命周期。

關(guān)鍵詞：WSN；LEACH；分簇；剩余能量；節(jié)點密集度；生命周期

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A 文章編號：2095-1302（2015）07-00-04

0 引 言

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）是由大量分布在目標(biāo)區(qū)域內(nèi)的低成本、低功耗的、具備特定功能的傳感器節(jié)點，通過無線通信方式組成分布式自組織網(wǎng)絡(luò)[1]。目前， WSN 已應(yīng)用于很多領(lǐng)域，比如環(huán)境監(jiān)測、醫(yī)療應(yīng)用、軍事等[2]。通常 WSN 中傳感器節(jié)點的數(shù)量非常大，并且投放到惡劣環(huán)境，人員很難到達(dá)，這些傳感器節(jié)點都是由電池供電的。因此無線傳感器網(wǎng)絡(luò)設(shè)計時，應(yīng)充分考慮各個節(jié)點的能量利用率，從而達(dá)到節(jié)能和延長網(wǎng)絡(luò)生命周期的目的，這也是無線傳感網(wǎng)絡(luò)與傳統(tǒng)的無線網(wǎng)絡(luò)的主要不同之處。

路由算法是WSN的核心技術(shù)之一，是無線傳感器網(wǎng)絡(luò)的重要組成部分。目前，針對無線傳感器網(wǎng)絡(luò)的路由協(xié)議大致分為兩類，一類是平面路由協(xié)議，另一類是分層路由協(xié)議。LEACH 是典型的分層路由協(xié)議[3]，由于簇頭的主要功能是負(fù)責(zé)收集各個普通節(jié)點感應(yīng)到的數(shù)據(jù)信息并傳輸至基站，故簇頭消耗的能量大，因此簇頭進(jìn)行輪轉(zhuǎn)性選舉，可確保無線傳感器網(wǎng)絡(luò)中各個節(jié)點能量均勻的消耗。LEACH 算法與一般的平面路由算法相比，網(wǎng)絡(luò)的生存時間可延長15%左右。

盡管LEACH算法在延長網(wǎng)絡(luò)生命周期方面有了很大的進(jìn)步，但是，該算法還存在很多不足。例如：簇頭的選舉是隨機的，簇頭選舉時未考慮能量因素等[4]。本研究針對 LEACH 算法存在的不足，提出了一種基于能量和節(jié)點密集度的路由選擇算法。即根據(jù)網(wǎng)絡(luò)所有節(jié)點所處的位置，對節(jié)點進(jìn)行分簇，在劃分的簇內(nèi)進(jìn)行簇頭選舉，簇頭選舉時，充分考慮節(jié)點的剩余能量和節(jié)點的密集程度。信息傳輸時，簇內(nèi)采用單跳，簇間采用單跳與多跳相結(jié)合的方式傳輸。實驗結(jié)果表明，與經(jīng)典的LEACH路由算法相比，改進(jìn)的算法有效的均衡了網(wǎng)絡(luò)中各節(jié)點的能量消耗，提高了各節(jié)點的利用率，推遲了第一個節(jié)點的死亡時間，進(jìn)而延長了網(wǎng)絡(luò)的生命周期。

1 LEACH算法

LEACH （Low Energy Adaptive Clustering Hierarchy）算法是由Wendi B . Heinzelman等人提出的第一個分層的拓?fù)淇刂频穆酚伤惴?。LEACH算法的工作過程如圖1所示。

圖1 LEACH算法的工作過程

1.1 工作過程

LEACH算法每輪包括兩個階段：簇的建立階段和穩(wěn)定的傳輸階段。為了使能耗最小化，簇在建立階段的時間要遠(yuǎn)小于穩(wěn)定的傳輸時間。

（1）建立簇階段：它的基本思想是在每一輪以隨機等概率的方式選擇簇頭。在選舉簇頭時，每一個節(jié)點產(chǎn)生一個0～1之間的隨機數(shù)值，如果這個數(shù)值小于設(shè)定的閾值T（n），則這個節(jié)點在當(dāng)前輪中被選為簇頭。T（n）的計算式為：

（1）

，其他

其中：P為無線傳感器網(wǎng)絡(luò)中簇頭節(jié)點數(shù)在總節(jié)點數(shù)中所占的比例，r為當(dāng)前運行的輪數(shù)，mod為求模運算，G為在最近的周期內(nèi)未當(dāng)選過簇頭的節(jié)點集合。

LEACH協(xié)議是根據(jù)簇頭節(jié)點來劃分簇，每輪結(jié)束后，簇頭節(jié)點向外廣播信息告知其他節(jié)點，其他節(jié)點接收到廣播數(shù)據(jù)包信息后，根據(jù)接收到信息的信號強度決定加入哪一個簇頭，并發(fā)送加入請求給相應(yīng)的簇頭，簇頭收到加入請求后，為每一個簇內(nèi)普通節(jié)點分配信息發(fā)送和接受的TDMA時間表，每個節(jié)點在分配的特定時間內(nèi)發(fā)送和接受信息（TDMA 時間表是根據(jù)每一個簇內(nèi)節(jié)點的個數(shù)來決定的）。此時完成了簇的建立。

（2）穩(wěn)定的傳輸階段：穩(wěn)定的傳輸階段的目的是進(jìn)行數(shù)據(jù)傳輸。無線傳感器網(wǎng)絡(luò)中簇內(nèi)成員將感應(yīng)到的數(shù)據(jù)信息在相應(yīng)的TDMA時間表內(nèi)傳遞給簇頭，簇頭節(jié)點收集到數(shù)據(jù)信息后，進(jìn)行適當(dāng)?shù)臄?shù)據(jù)融合，最終發(fā)送給基站。因此簇頭消耗的能量較多，穩(wěn)定傳輸階段進(jìn)行一段時間后，重新選舉簇頭，達(dá)到均衡網(wǎng)絡(luò)能量的目的。

1.2 LEACH 算法的不足

LEACH 路由協(xié)議算法是采用周期性、隨機選擇簇頭節(jié)點的方法來均衡傳感器的節(jié)點能耗，提高網(wǎng)絡(luò)中各節(jié)點的能量利用率，在性能上有了很大提升，但是該算法本身在以下方面仍存在不足之處：

（1）LEACH算法隨機產(chǎn)生簇頭[5]，每輪產(chǎn)生的簇頭數(shù)目不定。如果簇頭個數(shù)過少，普通節(jié)點與簇頭間距離較遠(yuǎn)，大大增加了節(jié)點信息的傳遞能耗；如果簇頭個數(shù)過多，會增加信道的競爭，產(chǎn)生過多的重復(fù)信息，增加數(shù)據(jù)融合和數(shù)據(jù)傳輸?shù)哪芰肯摹?/p>

（2）隨機產(chǎn)生的簇頭節(jié)點分布不均[5，6]，可能會導(dǎo)致被選成簇頭的節(jié)點集中分布在一個局部區(qū)域內(nèi)，而其它局部區(qū)域內(nèi)沒有簇頭節(jié)點，即網(wǎng)絡(luò)能耗不均衡，網(wǎng)絡(luò)生命周期降低。

（3）公式中設(shè)定簇頭選舉的閾值[7]過于簡單，未考慮節(jié)點的剩余能量和鄰近節(jié)點值。

這里提出了 LEACH 路由協(xié)議的特征以及不足。盡管LEACH算法較之于平面路由算法，在性能上有了很大的提升，但是，LEACH算法未考慮以上所提出的三點，如果將以上三點因素考慮到算法當(dāng)中，將會更好地提升網(wǎng)絡(luò)的性能，使網(wǎng)絡(luò)具有更高的實用價值。

2 CN-LEACH算法

針對以上提出的LEACH算法的不足，本研究提出了改進(jìn)的LEACH算法：即CN—LEACH算法。它的主要思想是：仍以輪為工作單位，每輪工作仍分為兩個階段：建立簇階段和穩(wěn)定傳輸階段。建立簇階段包括劃分簇和選舉簇頭兩部分。穩(wěn)定工作階段即為數(shù)據(jù)傳輸。具體為根據(jù)前人的研究得出簇頭個數(shù)控制在整個網(wǎng)絡(luò)節(jié)點數(shù)的5%時[8]，可使網(wǎng)絡(luò)的能耗最低。為了使節(jié)點分布均勻，每輪開始時，采用經(jīng)典的聚類算法（K-means）算法[9]對所有節(jié)點進(jìn)行聚類劃分。在劃分的簇內(nèi)進(jìn)行簇頭的選舉，簇頭選舉時，充分考慮節(jié)點的剩余能量和臨近節(jié)點數(shù)。選擇剩余能量高和臨近節(jié)點數(shù)多的節(jié)點作為簇頭節(jié)點。簇頭節(jié)點和基站（BS）之間通信時，采用簇內(nèi)單跳，簇間單跳和多跳[7]相結(jié)合的傳輸。

2.1 分簇階段

將N個節(jié)點隨機分布在固定的檢測區(qū)域內(nèi)?；竟?jié)點固定在一個確定位置后，依據(jù)K-means算法對節(jié)點進(jìn)行聚類劃分簇。K-means算法是基于距離的典型聚類算法。采用距離作為相似性評價指標(biāo)，即認(rèn)為兩個節(jié)點的距離越近，其相似度就越大。其基本步驟為：

（1）隨機給定K個簇中心；

（2）計算每個點到K個簇中心的距離，根據(jù)其與各個簇中心的距離，將該點歸到相距最近的簇；

（3）計算新得到的每個簇的質(zhì)心，并將這個質(zhì)心值作為新的聚類中心，反復(fù)執(zhí)行（2）、（3），直到聚類中心不再進(jìn)行大范圍的移動或者聚類條件達(dá)到要求為止。

在CN—LEACH算法中，將K-means算法運用到聚類劃分過程中，并將區(qū)域均勻劃分，每個節(jié)點屬于一個簇，簇頭個數(shù)就是要劃分的簇個數(shù)，即K的值為簇頭個數(shù)值。本研究對100個節(jié)點在100×100的固定區(qū)域內(nèi)使用K-means算法進(jìn)行聚類，其劃分后如圖2所示。

圖2 K-mean 算法聚類

由圖2可以看出：100個隨機分布的節(jié)點根據(jù)位置信息被均勻的劃分成五類，每個顏色代表一類，節(jié)點分成了五個簇。避免了由于簇頭分布不均而導(dǎo)致的個別節(jié)點能量消耗過多提前死亡。

2.2 建立簇階段

簇建立完成后，每個簇開始為自己挑選合適的簇頭。此時K個簇內(nèi)的每一個節(jié)點隨機產(chǎn)生一個0～1之間的隨機數(shù)，并且與新的閾值T（n）相比，如果小于新的閾值，則該節(jié)點成功被選為簇頭。新閾值T（n）的公式如式（2）所示：

（2）

，其他

式（2）中：Eave是同一簇內(nèi)節(jié)點的平均能量值。E（i）是當(dāng)前節(jié)點的能量值，Nneigh是當(dāng)前節(jié)點的鄰近節(jié)點數(shù)，nalive是本輪節(jié)點的存活節(jié)點數(shù)。

由新的閾值公式可以看出，簇頭的選舉引進(jìn)了節(jié)點的剩余能量和鄰近節(jié)點數(shù)[9]。高臨近節(jié)點數(shù)使簇頭成為簇的質(zhì)心的概率提高，簇頭處于質(zhì)心，可以節(jié)省簇內(nèi)普通節(jié)點向簇頭傳輸數(shù)據(jù)時的能量，即提高了簇內(nèi)節(jié)點的能量利用率。

2.3 數(shù)據(jù)傳輸階段

簇頭選舉完成后，當(dāng)選為簇頭的節(jié)點將自己成為簇頭的消息發(fā)給簇內(nèi)其它節(jié)點，而不是發(fā)往全部節(jié)點。簇頭節(jié)點將收集到的數(shù)據(jù)信息進(jìn)行必要的計算、融合后以單跳或多跳的方式[8]將其發(fā)送給sink節(jié)點。數(shù)據(jù)傳輸持續(xù)一段時間后，進(jìn)入下一輪。

無線傳感器網(wǎng)絡(luò)的數(shù)據(jù)傳輸模型采用一階無線電模型，如圖3所示。

圖3 數(shù)據(jù)傳輸模型

在傳輸長為k的信息經(jīng)過距離d的過程中，發(fā)送端的能量消耗為：

（3）

其中由圖3可知，Eelec表示發(fā)射電路發(fā)送信號時消耗的能量，k*ε*dn為發(fā)射放大器發(fā)送信號時消耗的能量，由公式（3）可知，若傳輸距離小于臨界值d0，功率放大消耗采用自由空間模型；反之，當(dāng)傳輸距離大于等于臨界值d0時，采用多路徑衰減模型。 εfs，εamp分別為這兩種模型中放大器的系數(shù)。這里。其節(jié)點接收端能量消耗如公式4所示：

ERx（k）=k*Eelec （4）

由以上公式可以看出，發(fā)送信息消耗的能量與距離密切相關(guān)，當(dāng)傳輸距離超過臨界值時，能量消耗會急劇增加，簇頭節(jié)點的死亡時間將會提前。簇頭節(jié)點一旦死亡，簇內(nèi)信息將不能傳遞給基站，從而造成信息丟失。

本研究在數(shù)據(jù)傳輸階段，簇內(nèi)信息單跳傳送至簇頭節(jié)點，簇間采用單跳和多跳相結(jié)合的模式[10]，在此模式中，若簇頭離sink節(jié)點較近，即在d0范圍內(nèi)，則采用單跳；較遠(yuǎn)（即超出d0）則簇頭節(jié)點選擇距離最近的簇頭進(jìn)行路由中轉(zhuǎn)。采用這種單多跳結(jié)合的通信模式，可以提高網(wǎng)絡(luò)的負(fù)載均衡，改進(jìn)的算法避免了距離基站較遠(yuǎn)的簇頭節(jié)點由于能耗過大提早死亡，從而延長了生命周期。

3 仿真結(jié)果分析

3.1 仿真環(huán)境

為了評價改進(jìn)后路由算法的性能，本文采用仿真工具M(jìn)ATLAB進(jìn)行仿真，并將改進(jìn)后的算法CN-LEACH與原算法LEACH進(jìn)行仿真比較。然后分析實驗結(jié)果。

我們假定無線傳感器網(wǎng)絡(luò)的區(qū)域是一個正方形，節(jié)點隨機分布，每個節(jié)點的電池能量有限，基站部署位置唯一。最優(yōu)簇頭是5%，無線傳感器網(wǎng)絡(luò)的仿真是在理想環(huán)境中進(jìn)行的，不存在丟包現(xiàn)象，則其實驗參數(shù)如表1所列。

表1 仿真參數(shù)

參數(shù)名稱 符號 值

網(wǎng)絡(luò)區(qū)域

節(jié)點數(shù)

簇頭概率

初始能量

短距離能耗系數(shù)

長距離能耗系數(shù)

數(shù)據(jù)包的大小

控制包的長度

數(shù)據(jù)融合能量 M×M

N

P

E0

εfs

εamp

k

Lctrl

EDA 100×100 m2

100個

0.05%

0.5 J

10 pJ/b/m2

0.001 3 pJ/b/m4

4 000 b

100 b

5 pJ/b/report

3.2 仿真結(jié)果

本研究從第一個死亡節(jié)點出現(xiàn)的時間和整個網(wǎng)絡(luò)剩余能量兩方面來評價網(wǎng)絡(luò)的性能。

圖4所示是死亡節(jié)點數(shù)與時間（輪數(shù)）的關(guān)系圖，由圖4可以看出，隨著輪數(shù)的增加，改進(jìn)后算法的性能明顯優(yōu)于LEACH算法。在該監(jiān)測區(qū)域中，LEACH的第一個死亡節(jié)點的時間在763輪，而CN-LEACH算法中的第一個死亡節(jié)點在1 123輪，改進(jìn)后的算法生命周期延長了近30%。LEACH算法網(wǎng)絡(luò)能量未得到均衡，節(jié)點能量未得到充分應(yīng)用。仿真結(jié)果表明，CN-LEACH死亡節(jié)點的時間明顯向后推遲，也就是延長了網(wǎng)絡(luò)的生存時間。

圖4 節(jié)點死亡時間對比

圖5所示是剩余能量與時間的關(guān)系圖，由圖5可以看出，隨著時間的遞增，CN-LEACH算法每一輪網(wǎng)絡(luò)的能量消耗都有所降低，改進(jìn)后算法總的剩余能量要高于LEACH算法，改進(jìn)后的算法能夠更好的使節(jié)點均勻的分擔(dān)能耗，使能耗均衡，更好的節(jié)省了整個網(wǎng)絡(luò)的能量，延長了網(wǎng)絡(luò)的生命周期。

綜上分析可知，改進(jìn)后的算法明顯優(yōu)于LEACH算法。該算法改善了LEACH算法中簇頭能耗過大等問題，有效的提高了網(wǎng)絡(luò)中各節(jié)點的能量利用率，均衡了能量負(fù)載，從而降低了整個網(wǎng)絡(luò)的能耗，更好的延長了網(wǎng)絡(luò)生存周期。

圖5 網(wǎng)絡(luò)剩余能量對比

4 結(jié) 語

無線傳感器網(wǎng)絡(luò)是物聯(lián)網(wǎng)技術(shù)接入層面的重要組成部分，它的研究和應(yīng)用已經(jīng)成為一個熱點，然而其網(wǎng)絡(luò)節(jié)點體積小，電池儲能少，這是無線傳感器網(wǎng)絡(luò)發(fā)展的瓶頸，本文通過分析無線傳感器網(wǎng)絡(luò)經(jīng)典的層次路由算法 LEACH 。提出了一種路由改進(jìn)算法 CN-LEACH。此算法在簇的分布、簇頭選舉和通信方式方面做了相應(yīng)的改進(jìn)。改進(jìn)后的算法降低了選舉的復(fù)雜度，優(yōu)化了簇頭節(jié)點在簇內(nèi)的位置，降低了簇成員間的通信成本。通過從網(wǎng)絡(luò)中節(jié)點的死亡時間、網(wǎng)絡(luò)的剩余能量方面的仿真比較可知，改進(jìn)的CN-LEACH 算法能夠有效地均衡能耗，延長網(wǎng)絡(luò)的生存時間。

參考文獻(xiàn)

[1] Adamu Murtala Zungeru， Li-Minn Ang， Kah Phooi Seng. Classical and swarm intelligence based routing protocols for wireless sensor networks： A survey and comparison[J]. Journal of Network and Computer Applications，2012，35 （5）： 1508-1536.

[2] Muhammad Saleem， Gianni A. Di Caro， Muddassar Farooq. Swarm intelligence based routing protocol for wireless sensor networks： Survey and future directions[J]. Information Sciences . 2010 （20）.

[3]劉鐵流，巫詠群.基于能量優(yōu)化的無線傳感器網(wǎng)絡(luò)分簇路由算法研究[J].傳感技術(shù)學(xué)報2011，24（5） ：64-70.

[4]陳曉娟，王卓，吳潔. 一種基于LEACH的改進(jìn)WSN路由算法[J].傳感技術(shù)學(xué)報，2013，26（1）：116-121.

[5]呂濤，朱清新，張路橋.一種基LEACH協(xié)議的改進(jìn)算法[J]. 電 子學(xué)報，2011，39（6）：1405-1409.

[6]路成杰，蔣海峰.一種基于節(jié)點密度的無線傳感器網(wǎng)絡(luò)路由協(xié)議[J].傳感器與微系統(tǒng)，2014，33（9）：114-116.

[7]李浩.無線傳感器網(wǎng)絡(luò)路由協(xié)議簇頭選舉機制研究[D].重慶：重慶大學(xué)，2014.

[8]李芳芳，王靖.一種基于LEACH協(xié)議的無線傳感器網(wǎng)絡(luò)路由算法[J].傳感技術(shù)學(xué)報，2012，25（10）：1445-1451.

[9]賈云杰. 基于LEACH的無線傳感器網(wǎng)絡(luò)分簇路由算法[D].武漢：華中師范大學(xué)，2013.

[10]王東東.基于能量感知的無線傳感器網(wǎng)絡(luò)分簇協(xié)議研究[D]. 無錫：江南大學(xué)，2014.