鄧夏陽 黃 杰

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

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

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

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

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

1.1 LEACH算法

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

1)簇建立階段

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

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

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

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

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

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

1.2 能量消耗模型

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

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

圖1 無線通信模型

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

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

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

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

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

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

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

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

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

1)首個死亡節(jié)點的初始能量Ss有

由于 r?q，則

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

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

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

由于 r?q，則

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

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

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

由于

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

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

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

3 仿真實驗

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

如圖2所示，在100×100的正方形區(qū)域內(nèi)均勻分布100個節(jié)點，每輪選取5個節(jié)點作為簇首.參照文獻［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.

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

圖2 網(wǎng)絡拓撲圖

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

4 結(jié)語

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

由于在每一輪中進行了多次的數(shù)據(jù)采集，所以本方案適用于移動性不強的傳感器網(wǎng)絡.但對于移動性強的網(wǎng)絡，需要適當?shù)販p小每輪的采集次數(shù)，以適應網(wǎng)絡拓撲的頻繁變化，這也是下一步要研究的工作.

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.