LEACH算法最優(yōu)數(shù)據(jù)采集方案

鄧夏陽 黃 杰

(東南大學(xué)信息科學(xué)與工程學(xué)院，南京 210096)

隨著物聯(lián)網(wǎng)應(yīng)用的興起，無線傳感器網(wǎng)絡(luò)(WSN)的研究越來越受到重視.與傳統(tǒng)無線網(wǎng)絡(luò)不同，由于WSN的成本低，其帶寬、內(nèi)存以及能量等物理資源受到很大的限制，而且WSN一般部署在無人區(qū)或敵占區(qū)，補(bǔ)充節(jié)點(diǎn)的能量將受到制約，因此延長網(wǎng)絡(luò)的運(yùn)行時(shí)間，提高網(wǎng)絡(luò)傳輸效率是WSN的重要研究內(nèi)容之一，而路由協(xié)議設(shè)計(jì)是該項(xiàng)研究的關(guān)鍵所在.

WSN路由協(xié)議按照網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可以分為平面型路由協(xié)議和層次型路由協(xié)議.在平面型路由協(xié)議中要求網(wǎng)絡(luò)各節(jié)點(diǎn)的功能和物理性能完全一樣，每個(gè)節(jié)點(diǎn)都需要具有一定的計(jì)算能力、數(shù)據(jù)采集能力和路由功能.平面型網(wǎng)絡(luò)的優(yōu)點(diǎn)是網(wǎng)絡(luò)中沒有特殊的節(jié)點(diǎn)，網(wǎng)絡(luò)流量均勻地分散在網(wǎng)絡(luò)中，路由算法容易實(shí)現(xiàn);缺點(diǎn)是各個(gè)相鄰節(jié)點(diǎn)間需要進(jìn)行頻繁的路由交換，極大地降低了網(wǎng)絡(luò)的性能，當(dāng)網(wǎng)絡(luò)規(guī)模增大到一定程度后，僅路由交換就會(huì)耗盡網(wǎng)絡(luò)帶寬，因此不適用于大規(guī)模網(wǎng)絡(luò).而層次型路由協(xié)議要求網(wǎng)絡(luò)中各節(jié)點(diǎn)在物理性能上相同，但功能上有所不同.網(wǎng)絡(luò)被分割成若干個(gè)簇，每個(gè)簇包含一個(gè)簇首節(jié)點(diǎn)(sink)和若干個(gè)簇節(jié)點(diǎn)(sensor)，簇節(jié)點(diǎn)將采集的信息發(fā)往簇首節(jié)點(diǎn)，簇首節(jié)點(diǎn)進(jìn)行數(shù)據(jù)融合，然后路由至基站.層次型網(wǎng)絡(luò)的優(yōu)點(diǎn)是:分簇減小了傳輸距離，數(shù)據(jù)融合技術(shù)減小了通信量，從而可以極大地降低網(wǎng)絡(luò)中能量的損耗，延長網(wǎng)絡(luò)的壽命;缺點(diǎn)是不適用于節(jié)點(diǎn)移動(dòng)較快的網(wǎng)絡(luò)［1］.由此可見，層次型網(wǎng)絡(luò)更適合于無線傳感器網(wǎng)絡(luò)的應(yīng)用.

在層次型路由協(xié)議中提出了以低功耗自適應(yīng)聚類路由(low energy adaptive clustering hierarchy，LEACH)算法［2］、閾值敏感節(jié)能傳感器網(wǎng)絡(luò)協(xié)議(threshold sensitive energy efficient sensor networks protocol，TEEN)、順序分配路由(sequential assignment routing，SAR)等為代表的路由算法.其中LEACH算法作為各種層次型協(xié)議的基礎(chǔ)，在2001年一經(jīng)提出，就受到了大家的關(guān)注.該算法把網(wǎng)絡(luò)分割成若干個(gè)簇，周期性地選擇簇首，并引入了“輪”的概念，每輪分為2個(gè)階段:簇建立階段和穩(wěn)定的數(shù)據(jù)傳輸階段.在簇首選擇問題上采用隨機(jī)數(shù)選舉，并且在一輪循環(huán)中簇首節(jié)點(diǎn)是固定的.TEEN協(xié)議是在LEACH算法的基礎(chǔ)上改進(jìn)而來，它是基于減小網(wǎng)絡(luò)通信量，從而降低節(jié)點(diǎn)能耗這一目標(biāo)而提出的，該協(xié)議通過引入軟門限和硬門限來實(shí)現(xiàn)對(duì)數(shù)據(jù)的過濾，減少了網(wǎng)絡(luò)的通信量，使得網(wǎng)絡(luò)壽命大大增加.SAR協(xié)議是第一個(gè)在WSN路由協(xié)議中保證QoS的主動(dòng)路由協(xié)議，sink節(jié)點(diǎn)的所有一跳鄰居節(jié)點(diǎn)都以自己為根創(chuàng)建生成樹，SAR協(xié)議的優(yōu)點(diǎn)是保證了QoS，缺點(diǎn)是需要大量的存儲(chǔ)空間來存儲(chǔ)路由表，且路由維護(hù)會(huì)造成很大的開銷［3］.這些路由協(xié)議都在一定程度上改善了無線傳感器網(wǎng)絡(luò)的路由性能，并且降低了能量消耗，但都并未對(duì)穩(wěn)定的數(shù)據(jù)傳輸階段的數(shù)據(jù)采集次數(shù)做出明確的規(guī)定.本文通過對(duì)經(jīng)典LEACH算法的分析和研究，從能量使用效率的角度出發(fā)，提出了最優(yōu)化的數(shù)據(jù)采集方案，從而使得節(jié)點(diǎn)的能量使用效率達(dá)到最大化.

1 LEACH算法及其能量消耗模型

1.1 LEACH算法

LEACH算法每輪分為2個(gè)階段［4-7］:簇建立階段和穩(wěn)定的數(shù)據(jù)傳輸階段.

1)簇建立階段

① 簇首選擇在［0，1］中隨機(jī)選擇一個(gè)數(shù)，將該數(shù)與每個(gè)節(jié)點(diǎn)計(jì)算出T(n)進(jìn)行比較，若T(n)大于該隨機(jī)數(shù)，則該節(jié)點(diǎn)當(dāng)選為本輪簇首，否則該節(jié)點(diǎn)為簇節(jié)點(diǎn)，即

②簇形成當(dāng)選為簇首的節(jié)點(diǎn)廣播ADV消息，包括本節(jié)點(diǎn)ID和標(biāo)志符.簇節(jié)點(diǎn)接收到一個(gè)ADV消息后等待一段時(shí)間以便接收到多個(gè)簇首發(fā)來的ADV消息，并根據(jù)RSSI選擇能量信號(hào)較強(qiáng)的節(jié)點(diǎn)作為自己的簇首，回復(fù)Join-REQ，包括本節(jié)點(diǎn)ID、簇首ID和消息位的標(biāo)識(shí)符.簇首節(jié)點(diǎn)向自己簇內(nèi)節(jié)點(diǎn)發(fā)送消息，包括本節(jié)點(diǎn)ID、簇節(jié)點(diǎn)ID、擴(kuò)頻碼、時(shí)間戳以及時(shí)隙表.

2)穩(wěn)定的數(shù)據(jù)傳輸階段

①簇節(jié)點(diǎn)采集數(shù)據(jù)，并在自己的時(shí)隙內(nèi)向簇首節(jié)點(diǎn)發(fā)送采集的信息.

②簇節(jié)點(diǎn)接收到采集來的消息，進(jìn)行數(shù)據(jù)融合后發(fā)往基站.

由上可以看出，簇建立階段會(huì)消耗節(jié)點(diǎn)能量.最初的LEACH算法僅對(duì)2個(gè)階段有粗略的要求，即穩(wěn)定的數(shù)據(jù)采集階段的時(shí)間應(yīng)大于簇建立階段［2］，并沒有明確說明采集的次數(shù).一方面如果在每輪中僅進(jìn)行一次數(shù)據(jù)采集，那么就需要不斷地更新簇首，頻繁的簇首更新會(huì)讓能量過多無意義的損失;另一方面一輪中數(shù)據(jù)采集次數(shù)也不能無限制地增大，從而使簇首節(jié)點(diǎn)的能耗負(fù)擔(dān)過重，可能導(dǎo)致某些節(jié)點(diǎn)過早地退出網(wǎng)絡(luò)，影響網(wǎng)絡(luò)壽命.這就需要找到一個(gè)合適的采集次數(shù)來使得LEACH算法的能量使用達(dá)到最優(yōu)化［8-9］.

1.2 能量消耗模型

假設(shè)在發(fā)射信息時(shí)會(huì)產(chǎn)生電子能量消耗和功率放大器能量消耗，而在接收數(shù)據(jù)時(shí)僅產(chǎn)生電子能量消耗.如圖1所示，接收l bit消息所消耗的能量為SR=lSelec，Selec為發(fā)送/接收單位 bit數(shù)據(jù)的能耗.發(fā)射l bit消息所消耗的能量:根據(jù)發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)之間的距離d，功率放大消耗分別采用自由空間模型(d2功率衰減)和多路徑衰減模型(d4功率衰減).當(dāng)2個(gè)節(jié)點(diǎn)之間的距離d小于門限值d0時(shí)，使用自由空間(FS)模型;當(dāng)2個(gè)節(jié)點(diǎn)的距離大于門限值d0而小于最大通信距離d′時(shí)，使用多路徑衰減(MP)模型.因此，節(jié)點(diǎn)發(fā)送l bit消息所消耗的能量為［2，10］

其中，電子能量消耗Selec取決于數(shù)字編碼、調(diào)制方式以及濾波器等因素.而放大器能量消耗εfsd2和εmpd4取決于收發(fā)2個(gè)節(jié)點(diǎn)間的距離及誤比特率.

圖1 無線通信模型

設(shè)網(wǎng)絡(luò)中有N個(gè)節(jié)點(diǎn)，形成了k個(gè)簇，基站距離節(jié)點(diǎn)部署區(qū)域的距離為dto-BS(d0＜dto-BS≤d′)，簇節(jié)點(diǎn)距離本簇的簇首節(jié)點(diǎn)的距離是dto-clus(0＜dto-clus≤d0)，建立階段所消耗的能量為S0，則S0的期望為

式中，S1，S2分別為簇首節(jié)點(diǎn)和簇節(jié)點(diǎn)在簇建立階段所消耗的能量.

在穩(wěn)定的數(shù)據(jù)傳輸階段，每個(gè)簇的簇首節(jié)點(diǎn)接收簇節(jié)點(diǎn)發(fā)送的信息所消耗的能量為

簇首節(jié)點(diǎn)和基站通信所消耗的能量為

簇節(jié)點(diǎn)發(fā)送消息至簇首節(jié)點(diǎn)消耗的能量為

2 最優(yōu)化數(shù)據(jù)采集方案的實(shí)現(xiàn)

傳感器網(wǎng)絡(luò)的主要任務(wù)就是獲取周圍物理世界的信息并將其傳輸至指定的地方.因此在相同初始能量的條件下，獲取的信息量越多則能量的利用效率就越高.

在LEACH協(xié)議中有2個(gè)階段:簇建立階段和穩(wěn)定的數(shù)據(jù)傳輸階段.只有發(fā)送到BS的數(shù)據(jù)才是可獲取的信息.從這個(gè)角度來看，簇建立階段消耗的能量對(duì)基站獲取的信息是沒有貢獻(xiàn)的，但是它又是不可缺少的網(wǎng)絡(luò)建立過程.那么在網(wǎng)絡(luò)建立完成后，每輪需要采集多少次數(shù)據(jù)才能使節(jié)點(diǎn)的能量利用效率達(dá)到最優(yōu)化.根據(jù)節(jié)點(diǎn)每輪采集數(shù)據(jù)次數(shù)的不同，討論2種不同情況下的LEACH算法:(1)每輪僅采集一次數(shù)據(jù)，采集完畢后即進(jìn)入下一輪;(2)每輪采集多次數(shù)據(jù).

假設(shè)網(wǎng)絡(luò)中有N個(gè)節(jié)點(diǎn)，形成了k個(gè)簇，每個(gè)簇含有相同數(shù)目的節(jié)點(diǎn)，每個(gè)簇每次采集的信息量是相等的，都是單位信息量1.在傳感器網(wǎng)絡(luò)中，網(wǎng)絡(luò)節(jié)點(diǎn)死亡后是無法及時(shí)補(bǔ)充的，當(dāng)出現(xiàn)節(jié)點(diǎn)死亡時(shí)，網(wǎng)絡(luò)的性能就會(huì)降低，并且對(duì)于LEACH算法而言，其核心就是把網(wǎng)絡(luò)能耗均等地分配到每個(gè)節(jié)點(diǎn)上，若有一個(gè)節(jié)點(diǎn)因能量耗盡而退出網(wǎng)絡(luò)，則剩余節(jié)點(diǎn)都會(huì)在很短的時(shí)間內(nèi)耗盡能量，因此可以認(rèn)為當(dāng)網(wǎng)絡(luò)中只要有一個(gè)節(jié)點(diǎn)死亡，則整個(gè)網(wǎng)絡(luò)生命結(jié)束，下面分析每種情況下WSN的壽命.

1)首個(gè)死亡節(jié)點(diǎn)的初始能量Ss有

由于 r?q，則

式中，r為節(jié)點(diǎn)經(jīng)歷的總輪數(shù);q為節(jié)點(diǎn)當(dāng)選簇首的次數(shù);SAg為簇首結(jié)點(diǎn)壓縮一條信息所消耗的能量，令

則基站接收到的總消息幀為

2)假設(shè)節(jié)點(diǎn)在網(wǎng)絡(luò)中經(jīng)歷了r輪，每輪采集p次數(shù)據(jù)，共有q次當(dāng)選為簇首，其中，，則首個(gè)死亡節(jié)點(diǎn)初始能量Ss有

由于 r?q，則

因此基站獲得的總消息幀為

比較這2種不同的情況發(fā)現(xiàn):第2種要優(yōu)于第1種情況.

證明 比較式(13)和(10)得

由于

由于 1?Sfr-clus，則對(duì)式(15)有

由于 1?S0，因此 kprmax－kr＞0.

由此可以看出:當(dāng)在初始能量一定的情況下，

3 仿真實(shí)驗(yàn)

通過以上分析，采用OMNet++軟件仿真來評(píng)估該算法的性能.

如圖2所示，在100×100的正方形區(qū)域內(nèi)均勻分布100個(gè)節(jié)點(diǎn)，每輪選取5個(gè)節(jié)點(diǎn)作為簇首.參照文獻(xiàn)［2］中的參數(shù)賦值，即 N=100，k=5，εfs=10 pJ/(bit·m2)，εelact=5 nJ/bit，εmp=1.3 fJ/(bit·m4)，l=4 kbit，SAg=5 nJ/bit，S0=32.7 nJ，S=5 J.

當(dāng)?shù)?個(gè)節(jié)點(diǎn)能量耗盡時(shí)，網(wǎng)絡(luò)生命就已經(jīng)結(jié)束了.圖3顯示了在每輪不同采集次數(shù)下，基站接收到的信息幀的總數(shù).從圖中可以明顯看出，在初始能量相同的情況下(5 J)，第1個(gè)節(jié)點(diǎn)死亡時(shí)，若每輪只采集一次，則基站獲得的信息幀為1.838 4×104，隨著每輪采集次數(shù)的增大，基站獲得的信息量也隨著增大;當(dāng)每輪采集3次數(shù)據(jù)，基站獲得的信息幀最大為2.453 4×104，比只采集一次提高了33%.這是因?yàn)樵龃罅嗣枯喌牟杉螖?shù)，減小了簇首更新的頻率，節(jié)點(diǎn)的能量更多地用在了傳輸數(shù)據(jù)上，因此在能量的利用效率上也比只采集一次提高了33%;當(dāng)每輪的采集次數(shù)大于3，基站收到的信息量迅速減小，這是由于每輪的采集次數(shù)增大后，過多地消耗簇首節(jié)點(diǎn)的能量，使得節(jié)點(diǎn)過早地因能量耗盡而退出網(wǎng)絡(luò).

圖2 網(wǎng)絡(luò)拓?fù)鋱D

圖3 LEACH協(xié)議不同采集次數(shù)的比較

4 結(jié)語

通過對(duì)經(jīng)典LEACH算法的分析和研究，針對(duì)LEACH算法未明確指出穩(wěn)定的數(shù)據(jù)傳輸階段的數(shù)據(jù)采集次數(shù)，從能量使用效率的角度出發(fā)，提出了最優(yōu)化的數(shù)據(jù)采集方案.經(jīng)過數(shù)學(xué)計(jì)算，推導(dǎo)出最優(yōu)化采集次數(shù)的公式，并對(duì)其進(jìn)行了仿真，從而獲得了最優(yōu)化的節(jié)點(diǎn)數(shù)據(jù)采集方案，解決了LEACH算法中未明確的簇建立階段和穩(wěn)定的數(shù)據(jù)傳輸階段在一輪中的所占用時(shí)間比例的問題.分析和仿真結(jié)果表明:最優(yōu)化的采集方案顯著提高了網(wǎng)絡(luò)的能量利用效率，在初始能量相同的條件下，能夠獲得更多的信息.

由于在每一輪中進(jìn)行了多次的數(shù)據(jù)采集，所以本方案適用于移動(dòng)性不強(qiáng)的傳感器網(wǎng)絡(luò).但對(duì)于移動(dòng)性強(qiáng)的網(wǎng)絡(luò)，需要適當(dāng)?shù)販p小每輪的采集次數(shù)，以適應(yīng)網(wǎng)絡(luò)拓?fù)涞念l繁變化，這也是下一步要研究的工作.

References)

［1］ Intanagonwiwat C，Govindan R，Estfin D.Directed diffusion for wireless sensor networking［J］.IEEE/ACM Transactions on Networking，2003，11(1):2-16.

［2］ Heinzelman W B，Chandrakasan A P，Balakrishnan H.Application-specific protocol architectures for wireless networks［J］.IEEE/ACM Transactions on Wireless Communications，2002，1(4):660-670.

［3］ Sohrabi K，Gao J，Ailawadhi V，et al.Protocols for selforganization of a wireless sensor network［J］.IEEE Personal Communications，2000，7(5):16-27.

［4］Wendi R H，Anantha C，Hari B.Energy-efficient communication protocol for wireless microsensor networks［C］//System Sciences.Hawaii，USA，2000:1-10.

［5］ Liu Yuhua，Luo Zhenrong.A reliable clustering algorithm base on LEACH protocol in wireless mobile sensor networks［C］//Mechanical and Electrical Technology.Wuhan，China，2010:692-696.

［6］ Jia Jianguang，He Zunwen，Jing Ming，et al.An energy consumption balanced clustering algorithm for wireless sensor network［C］//Wireless Communications Networking and Mobile Computing.Beijing，China，2010:1-4.

［7］ Li Xunbo，Li Na，Liang Chen，et al.An improved LEACH for clustering protocols in wireless sensor networks［C］//Measuring Technology and Mechatronics Automation.Changsha，China，2010:496-499.

［8］Melese D G，Xiong Huagang，Gao Qiang.Consumed energy as a factor for cluster head selection in wireless sensor networks［C］//Wireless Communications Networking and MobileComputing. Chengdu， China，2010:1-5.

［9］ Xu Longlong，Zhang Jianjun.Improved LEACH cluster head multi-hops algorithm in wireless sensor networks［C］//International Symposium on Distributed Computing and Applications to Business，Engineering and Science.Hong Kong，China，2010:263-267.

［10］ Yang Kun，Wu Yuanming，Zhou Haibo.Research of optimal energy consumption model in wireless sensor network computer engineering and technology［C］//Computer Engineering and Technology.Chengdu，China，2010:421-424.