劉永超，張月霞，繆 旻

(1.北京信息科技大學 信息與通信工程學院，北京100101;2.北京信息科技大學 北京高動態(tài)導航技術(shù)重點實驗室，北京100101)

0 引 言

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

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

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

1 LEACH 算法原理

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

圖1 LEACH 算法的運作過程Fig 1 Operation process of LEACH algorithm

1.1 建立階段

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

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

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

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

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

1.3 LEACH 算法的不足

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

2 A-LEACH 算法

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

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

2.1 分區(qū)域階段

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

1)首先確定所有存活節(jié)點到基站距離。基站可以將消息傳遞給最遠的節(jié)點，將自己的位置等信息傳遞給所有節(jié)點，從而計算出節(jié)點到簇首節(jié)點的距離，然后再將信息傳遞給簇首節(jié)點。

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

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

2.2 簇的建立階段

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

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

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

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

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

2.3 信息傳輸階段

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 論

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

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

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

［3］ 陳曉娟，王 卓，吳 潔.一種基于LEACH 的改進WSNs 路由算法［J］.傳感技術(shù)學報，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］ 王 進，邵玉斌，龍 華，等.基于能量和距離加權(quán)的WSNs 簇頭選擇算法［J］.傳感器與微系統(tǒng)，2014，33(5):132－134.

［7］ 路成杰，蔣海峰.一種基于節(jié)點密度的無線傳感器網(wǎng)絡路由協(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］.電子學報，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.