基于能量和距離的分區(qū)域選擇簇首WSNs 路由算法*

劉永超，張?jiān)孪?，?旻

(1.北京信息科技大學(xué) 信息與通信工程學(xué)院，北京100101;2.北京信息科技大學(xué) 北京高動(dòng)態(tài)導(dǎo)航技術(shù)重點(diǎn)實(shí)驗(yàn)室，北京100101)

0 引 言

無線傳感器網(wǎng)絡(luò)(WSNs)是由很多傳感器節(jié)點(diǎn)組成，這些節(jié)點(diǎn)包含傳感器單元、處理器和無線收發(fā)器，可以形成一個(gè)自組織網(wǎng)絡(luò)系統(tǒng)。目前WSNs 已應(yīng)用于很多領(lǐng)域，比如:環(huán)境監(jiān)測、醫(yī)療應(yīng)用、軍事等。通常WSNs 中傳感器的數(shù)量非常大，又由于惡劣環(huán)境條件的限制，這些傳感器節(jié)點(diǎn)都是由電池供電的［1］。因此，WSNs 的設(shè)計(jì)主要考慮到能量有效和延長網(wǎng)絡(luò)的生命周期，這也是WSNs 不同于傳統(tǒng)的無線網(wǎng)絡(luò)的主要部分。

根據(jù)網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)的地位和功能的不同，路由算法可以分成平面路由算法和分層次路由算法。分層路由算法是通過將網(wǎng)絡(luò)分成不同的簇，在簇內(nèi)有一個(gè)簇首負(fù)責(zé)融合簇內(nèi)節(jié)點(diǎn)的信息，然后將融合信息發(fā)送給基站(BS)。相比平面路由算法，它能夠更好地節(jié)省網(wǎng)絡(luò)的能量和延長網(wǎng)絡(luò)的生命周期。LEACH(low-energy adaptive clustering hierarchy)是最早提出的經(jīng)典的分層路由算法，它采用動(dòng)態(tài)分簇，讓節(jié)點(diǎn)循環(huán)去充當(dāng)簇頭，負(fù)責(zé)收集簇內(nèi)其他節(jié)點(diǎn)的信息，進(jìn)行數(shù)據(jù)融合，然后再將信息發(fā)送到基站，從而均衡網(wǎng)絡(luò)節(jié)點(diǎn)的能量消耗［2］。與一般的平面路由算法相比之，LEACH 算法可以將網(wǎng)絡(luò)生存壽命延長15%左右。但是，LEACH 路由算法本身存在不足之處，如簇首分布不均勻，簇首節(jié)點(diǎn)選擇的盲目性，遠(yuǎn)距離傳輸過多消耗能量等［3］。

針對LEACH 算法存在的不足，本文提出一種基于能量和距離的分區(qū)域選擇簇首路由算法。根據(jù)網(wǎng)絡(luò)所有節(jié)點(diǎn)所處的位置和到基站的距離，將節(jié)點(diǎn)進(jìn)行分區(qū)域，然后再在各個(gè)區(qū)域內(nèi)進(jìn)行簇首節(jié)點(diǎn)選擇;將節(jié)點(diǎn)的剩余能量和節(jié)點(diǎn)的密集程度引入到簇首節(jié)點(diǎn)選擇;同時(shí)，采用多跳傳輸模型。實(shí)驗(yàn)結(jié)果表明:該算法能夠平衡網(wǎng)絡(luò)負(fù)載和延長網(wǎng)絡(luò)生命周期。

1 LEACH 算法原理

LEACH 算法是2000 年麻省理工學(xué)院電子工程和計(jì)算機(jī)科學(xué)系的Heinzelman W 等人為WSNs 設(shè)計(jì)的第一個(gè)分層次拓?fù)渎酚伤惴ǎ?］。LEACH 算法引入“輪”的概念，執(zhí)行過程是周期性的，每輪分為簇的建立階段和穩(wěn)定的數(shù)據(jù)傳輸階段，為了減少分簇帶來的額外能耗，簇的穩(wěn)定階段要遠(yuǎn)遠(yuǎn)長于簇的建立階段。從圖1 可以清楚地看出LEACH 算法的運(yùn)作過程。

圖1 LEACH 算法的運(yùn)作過程Fig 1 Operation process of LEACH algorithm

1.1 建立階段

在選舉簇首時(shí)，各個(gè)節(jié)點(diǎn)產(chǎn)生一個(gè)0～1 之間的隨機(jī)數(shù)，將它與它所對應(yīng)的閾值T(i)進(jìn)行比較，如果這個(gè)隨機(jī)數(shù)小于其閾值，則這個(gè)節(jié)點(diǎn)將被選為簇首。其中，T(i)可表示為

其中，p 為簇首在所有節(jié)點(diǎn)中所占的比例，r 為當(dāng)前運(yùn)行的輪數(shù)，mod 為求模運(yùn)算，G 為這一周期中未當(dāng)選為簇首的節(jié)點(diǎn)集合。

一輪簇首選舉結(jié)束后，某些節(jié)點(diǎn)會(huì)當(dāng)選為簇首。簇首節(jié)點(diǎn)就向外發(fā)送廣播信息，其他節(jié)點(diǎn)接收到廣播消息后，依據(jù)接收到廣播消息的信號強(qiáng)度確定要加入的簇，同時(shí)向該簇發(fā)送加入請求。簇首收到請求后將節(jié)點(diǎn)加入自己的路由表，并為每個(gè)節(jié)點(diǎn)設(shè)定一個(gè)TDMA 時(shí)間表，再將該時(shí)間表發(fā)送給所有簇內(nèi)節(jié)點(diǎn)。普通節(jié)點(diǎn)接收到信息后，整個(gè)簇的建立完成。

1.2 穩(wěn)定的傳輸階段

在每輪的穩(wěn)定傳輸階段，普通的傳感器節(jié)點(diǎn)按照TDMA 表在屬于自己的時(shí)隙內(nèi)將采集的數(shù)據(jù)發(fā)送給簇首節(jié)點(diǎn)。簇首節(jié)點(diǎn)再將收集到的數(shù)據(jù)進(jìn)行數(shù)據(jù)融合，然后將融合后的信息發(fā)送給基站。簇首工作任務(wù)比較繁重，需要收集普通節(jié)點(diǎn)的信息，然后完成數(shù)據(jù)融合，最后與基站通信，能量消耗較大。因此，每一輪結(jié)束后要按照上述方法重新選擇簇首和簇的劃分，以使網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)的負(fù)載保持均衡。

1.3 LEACH 算法的不足

LEACH 路由算法本身存在簇首的選舉是隨機(jī)選擇的，經(jīng)常會(huì)導(dǎo)致簇首分布不均勻，會(huì)增加整個(gè)網(wǎng)路的能量消耗;在簇首節(jié)點(diǎn)選擇時(shí)沒有考慮節(jié)點(diǎn)當(dāng)前的能量情況，如果能量很低的節(jié)點(diǎn)當(dāng)選為簇頭節(jié)點(diǎn)，則將會(huì)加速該節(jié)點(diǎn)的死亡，影響整個(gè)網(wǎng)絡(luò)的生命周期;簇首節(jié)點(diǎn)到基站的通信采用單跳通信，WSNs 中很多節(jié)點(diǎn)距離基站較遠(yuǎn)，根據(jù)多徑衰減模型，簇首節(jié)點(diǎn)發(fā)送數(shù)據(jù)到基站所消耗的通信能量會(huì)隨著距離的增大而急劇增長，從而增加整個(gè)網(wǎng)絡(luò)的能量消耗。

2 A-LEACH 算法

綜合以上LEACH 算法的不足，本文提出了以下的改進(jìn)方案:首先根據(jù)節(jié)點(diǎn)到基站的距離將簇首節(jié)點(diǎn)分為由近到遠(yuǎn)的三個(gè)區(qū)域［5］，然后在三個(gè)區(qū)域進(jìn)行簇首選擇。簇首選擇時(shí)綜合考慮到節(jié)點(diǎn)的剩余能量［6］和周圍的鄰居節(jié)點(diǎn)［7］，選擇剩余能量高且周圍鄰居節(jié)點(diǎn)較多的節(jié)點(diǎn)為簇首。在簇首節(jié)點(diǎn)收集完信息后進(jìn)行由遠(yuǎn)區(qū)域到近區(qū)域的逐次多跳傳輸，從而減少過遠(yuǎn)傳輸帶來的巨大能量的消耗。圖2 為ALEACH 路由算法的網(wǎng)絡(luò)結(jié)構(gòu)圖。

圖2 A-LEACH 算法的網(wǎng)絡(luò)結(jié)構(gòu)圖Fig 2 Network structure of A-LEACH algorithm

2.1 分區(qū)域階段

節(jié)點(diǎn)隨機(jī)地分布在固定的檢測區(qū)域，節(jié)點(diǎn)一旦部署，其位置不可變動(dòng)。

1)首先確定所有存活節(jié)點(diǎn)到基站距離?；究梢詫⑾鬟f給最遠(yuǎn)的節(jié)點(diǎn)，將自己的位置等信息傳遞給所有節(jié)點(diǎn)，從而計(jì)算出節(jié)點(diǎn)到簇首節(jié)點(diǎn)的距離，然后再將信息傳遞給簇首節(jié)點(diǎn)。

2)所有節(jié)點(diǎn)確定到基站的距離，并將距離保存下來。通過所有節(jié)點(diǎn)到簇首之間的距離，將所有節(jié)點(diǎn)分為A，B，C三個(gè)區(qū)域［8］。將所有節(jié)點(diǎn)到基站的距離由近到遠(yuǎn)進(jìn)行排序，距離最近的前20%的節(jié)點(diǎn)劃分為A 區(qū)域，排序中到基站的距離在20%～60%的節(jié)點(diǎn)為B 區(qū)域，而60%以上節(jié)點(diǎn)劃分為C 區(qū)域，A，B，C 區(qū)域的節(jié)點(diǎn)個(gè)數(shù)由Num-A，Num-B，Num-C 表示。

3)在分區(qū)之后，在各個(gè)區(qū)域中，計(jì)算出每個(gè)節(jié)點(diǎn)的密集程度，也就是節(jié)點(diǎn)附近節(jié)點(diǎn)的個(gè)數(shù)，取節(jié)點(diǎn)周圍D 距離范圍內(nèi)的節(jié)點(diǎn)個(gè)數(shù)Nneigh(i)，D 為網(wǎng)絡(luò)區(qū)域范圍長度x 的20%。

2.2 簇的建立階段

1)首先是簇首選擇:在分區(qū)域階段，已經(jīng)獲知了節(jié)點(diǎn)的密集程度，通過節(jié)點(diǎn)的剩余能量和節(jié)點(diǎn)的密集程度來計(jì)算各個(gè)節(jié)點(diǎn)當(dāng)選簇首的概率值，該概率值為

其中，c1，c2為比例系數(shù)，E(i)為當(dāng)前節(jié)點(diǎn)的能量值，Eave為所有節(jié)點(diǎn)能量的平均值，Nneigh(i)為當(dāng)期節(jié)點(diǎn)的密集程度，nalive為當(dāng)前網(wǎng)絡(luò)的存活節(jié)點(diǎn)個(gè)數(shù)。通過概率值來選擇簇首，讓優(yōu)秀的節(jié)點(diǎn)成為簇首節(jié)點(diǎn)［9］。

2)在得到了所有節(jié)點(diǎn)的概率值之后，然后分別在A，B，C 區(qū)域選擇簇首節(jié)點(diǎn)。在前人研究的基礎(chǔ)上，得知將簇首個(gè)數(shù)控制在整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)的5%時(shí)，可使網(wǎng)絡(luò)的能量消耗最低［2，10］。所以在選擇簇首時(shí)，A，B 和C 區(qū)域選出Num-A×5%，Num-B×5%，Num-C×5%個(gè)簇首節(jié)點(diǎn)。同時(shí)在選擇簇首時(shí)，為避免兩個(gè)簇首節(jié)點(diǎn)離得太近而增加簇首的能耗，要求兩個(gè)簇首節(jié)點(diǎn)的距離不能小于網(wǎng)絡(luò)區(qū)域范圍長度x的20%。

3)在選擇出簇首節(jié)點(diǎn)以后，簇首向自己所在的區(qū)域進(jìn)行廣播，普通節(jié)點(diǎn)接收到此區(qū)域的簇首廣播信息以后選擇合適的簇首加入，向簇首發(fā)送加入信息，同時(shí)簇首接收普通節(jié)點(diǎn)發(fā)過來的加入信息。

4)在分簇完成以后，簇首為其簇內(nèi)的普通節(jié)點(diǎn)制定TDMA 時(shí)間表，普通節(jié)點(diǎn)在自己所在時(shí)隙里將數(shù)據(jù)傳遞給簇首。簇的建立階段完成。

2.3 信息傳輸階段

在信息傳輸過程中，節(jié)點(diǎn)傳輸k bit 數(shù)據(jù)到距離為d 時(shí)所消耗的能量為

其中，ETx－elec為節(jié)點(diǎn)信號發(fā)送數(shù)據(jù)消耗的能量，ETx－amp為發(fā)送電路所消耗的能量，εfs和εamp為放大器的系數(shù)，d0為臨界距離接收端接收k bit 數(shù)據(jù)消耗的能量為

通過以上公式可知，節(jié)點(diǎn)傳輸距離大于臨界距離d0時(shí)，所消耗的能量會(huì)急劇增加。所以，本文提出采用多跳的傳遞模式。每個(gè)簇接收簇內(nèi)普通節(jié)點(diǎn)的信息后，將信息融合，然后C 區(qū)域的簇首將信息傳遞給B 區(qū)域距離近的簇首節(jié)點(diǎn)，然后B 區(qū)域的簇首節(jié)點(diǎn)再將信息傳遞給A 區(qū)域的簇首節(jié)點(diǎn)，最后再傳遞給基站。

3 仿真與結(jié)果分析

為了分析改進(jìn)算法有效性，本文對改進(jìn)算法A-LEACH和LEACH 進(jìn)行了仿真和分析。WSNs 面積分別為100 m×100 m 基站位置分別為(125，50)m 場景。假定信息感知、空閑和休眠三種功耗均為0，仿真環(huán)境的各個(gè)參數(shù)如表1 所示。

表1 仿真參數(shù)Tab 1 Simulation parameters

本文中從網(wǎng)絡(luò)的生存時(shí)間、存活節(jié)點(diǎn)數(shù)和網(wǎng)絡(luò)總體剩余能量方面評估改進(jìn)后的性能。A-LEACH 路由算法首先是對網(wǎng)絡(luò)進(jìn)行分區(qū)域。圖3 為節(jié)點(diǎn)的劃分區(qū)域分布圖，根據(jù)節(jié)點(diǎn)到基站距離的遠(yuǎn)近將其分為三個(gè)部分。

圖3 節(jié)點(diǎn)的分布圖Fig 3 Distribution of nodes

圖4 表示仿真中每一輪的簇首個(gè)數(shù)。通過圖4 可知，LEACH 路由算法中的每一輪的簇首節(jié)點(diǎn)個(gè)數(shù)的變化范圍很大。簇首個(gè)數(shù)過多或者過小都會(huì)增加網(wǎng)絡(luò)能量的開銷。而A-LEACH 路由算法嚴(yán)格地將簇首節(jié)點(diǎn)的個(gè)數(shù)控制在存活節(jié)點(diǎn)個(gè)數(shù)的5%。同時(shí)A-LEACH 采用的是分區(qū)選擇簇首，簇首節(jié)點(diǎn)的分布比較均勻。

圖5 為LEACH 和A-LEACH 算法的存活節(jié)點(diǎn)個(gè)數(shù)與輪數(shù)的關(guān)系。從圖中可知，LEACH 出現(xiàn)第一個(gè)死亡節(jié)點(diǎn)在763 輪，而A-LEACH 算法第一個(gè)死亡節(jié)點(diǎn)出現(xiàn)在1023 輪。從整體網(wǎng)絡(luò)的生命周期看，A-LEACH 算法將網(wǎng)絡(luò)的生命周期延長了近20%。同時(shí)通過節(jié)點(diǎn)死亡的趨勢可以看出，LEACH 算法中，網(wǎng)絡(luò)節(jié)點(diǎn)的能量分布不均勻，能量相差的比例較大，所以，出現(xiàn)了有些節(jié)點(diǎn)過早死亡而有些節(jié)點(diǎn)存活很長時(shí)間的情況。而在A-LEACH 路由算法中，網(wǎng)絡(luò)中的節(jié)點(diǎn)幾乎在同一時(shí)間能量耗盡，表明此算法能夠很好地均衡網(wǎng)絡(luò)的能量分布。

圖4 每一輪的簇首個(gè)數(shù)Fig 4 Number of cluster heads in each round

圖5 存活節(jié)點(diǎn)數(shù)的比較Fig 5 Comparison of number of nodes alive

圖6 為整個(gè)網(wǎng)絡(luò)的剩余能量總和，通過仿真結(jié)果可以看出:A-LEACH 算法每輪消耗的能量要比LEACH 少，節(jié)省整個(gè)網(wǎng)絡(luò)的能量，這也是延長網(wǎng)絡(luò)生命周期的一個(gè)原因。

圖6 整個(gè)網(wǎng)絡(luò)的剩余能量Fig 6 Residual energy of entire network

4 結(jié) 論

WSNs 是物聯(lián)網(wǎng)工程的重要組成部分，而路由算法是WSNs 的核心技術(shù)之一。本文通過對WSNs 的經(jīng)典路由算法LEACH 進(jìn)行分析研究，提出了一種分區(qū)域分簇的路由改進(jìn)算法A-LEACH。改進(jìn)算法首先根據(jù)節(jié)點(diǎn)到基站的距離對節(jié)點(diǎn)進(jìn)行區(qū)域劃分，然后在特定區(qū)域用新的閾值來選擇優(yōu)秀的節(jié)點(diǎn)作為簇首，最后采用多跳的方式進(jìn)行信息傳輸。通過仿真證明:A-LEACH 改進(jìn)算法能夠更有效延長網(wǎng)絡(luò)的生命周期，均衡網(wǎng)絡(luò)能量的分布和減少網(wǎng)絡(luò)的能耗。

［1］ 李桂香.基于傳感器網(wǎng)絡(luò)能量均衡分簇算法仿真研究［J］.計(jì)算機(jī)仿真，2012，29(4):161－164.

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

［3］ 陳曉娟，王 卓，吳 潔.一種基于LEACH 的改進(jìn)WSNs 路由算法［J］.傳感技術(shù)學(xué)報(bào)，2013，26(1):116－121.

［4］ Heinzelman W，Chandrakasan A，Balakrishnan H.Energy-efficient communication protocol for wireless sensor networks［C］∥Proceedings of 33th IEEE Annual Hawaii International Conference on System Sciences，2000:10.

［5］ Gautam Navin，Pyun Jae-Young.Distance aware intelligent clustering protocol for wireless sensor networks［J］.Journal of Communications and Networks，2010，12(2):122－129.

［6］ 王 進(jìn)，邵玉斌，龍 華，等.基于能量和距離加權(quán)的WSNs 簇頭選擇算法［J］.傳感器與微系統(tǒng)，2014，33(5):132－134.

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

［8］ Liu Y，Xiong N，Zhao Y，et al.Multi-layer clustering routing algorithm for wireless vehicular sensor networks［J］.IET Trans on Communications，2010，4(7):810－816.

［9］ 呂 濤，朱清新，張路橋.一種基于LEACH 協(xié)議的改進(jìn)算法［J］.電子學(xué)報(bào)，2011，39(6):1405－1409.

［10］Heinzelman W B，Chandrakasan A，Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks［J］.IEEE Transactions on Wireless Communication，2002，1(4):600－670.