基于能量和節(jié)點(diǎn)密集度的WSN路由算法

閆海云+吳韶波

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

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

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

0 引 言

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

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

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

1 LEACH算法

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

圖1 LEACH算法的工作過程

1.1 工作過程

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

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

（1）

，其他

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

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

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

1.2 LEACH 算法的不足

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

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

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

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

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

2 CN-LEACH算法

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

2.1 分簇階段

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

（1）隨機(jī)給定K個(gè)簇中心；

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

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

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

圖2 K-mean 算法聚類

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

2.2 建立簇階段

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

（2）

，其他

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

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

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

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

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

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

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

（3）

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

ERx（k）=k*Eelec （4）

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

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

3 仿真結(jié)果分析

3.1 仿真環(huán)境

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

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

表1 仿真參數(shù)

參數(shù)名稱 符號(hào) 值

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

節(jié)點(diǎn)數(shù)

簇頭概率

初始能量

短距離能耗系數(shù)

長距離能耗系數(shù)

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

控制包的長度

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

N

P

E0

εfs

εamp

k

Lctrl

EDA 100×100 m2

100個(gè)

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é)果

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

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

圖4 節(jié)點(diǎn)死亡時(shí)間對(duì)比

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

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

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

4 結(jié) 語

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

參考文獻(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é)報(bào)2011，24（5） ：64-70.

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

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

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

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

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

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

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