基于貪婪算法的樹形WSN 低功耗路由算法

肖 劍，何志成，胡 欣，張 贊，袁 曄

（1.長安大學 電子與控制工程學院，陜西 西安 710064；2.長安大學 能源與電氣工程學院，陜西 西安 710064；3.寧夏回族自治區(qū)無線電監(jiān)測站，寧夏 銀川 750001）

0 引 言

無線傳感器網(wǎng)絡主要由大量具備無線通信能力的傳感器節(jié)點和少量基站組成，傳感器節(jié)點對相關監(jiān)測數(shù)據(jù)進行采集，然后將數(shù)據(jù)無線傳輸給基站以便數(shù)據(jù)的后續(xù)處理和分析，從而使無線傳感器網(wǎng)絡實現(xiàn)對某一片區(qū)域的實時監(jiān)測。然而傳感器節(jié)點大多被安裝在人難以觸及的地方，使得傳感器節(jié)點難以維護，所以傳感器節(jié)點大都由電池進行供電，而一旦電能耗盡，該傳感器節(jié)點會立即失效。因此，如何在能量有限的情況下使盡可能多的傳感器節(jié)點有盡可能長的生命周期已成為無線傳感器網(wǎng)絡技術領域的重要研究方向。

針對無線傳感器網(wǎng)絡存在的能耗問題，Heinzelman 等[1]提出了基于分簇路由協(xié)議的LEACH 算法，通過等概率隨機選取簇首的方式使整個網(wǎng)絡中各個節(jié)點的能耗盡可能均衡，進而使更多的節(jié)點有更長的生命周期。但是LEACH 算法在選取簇首時，沒有考慮到節(jié)點的剩余能量、節(jié)點所處的位置以及節(jié)點密度，這就有可能使某些節(jié)點過快凋亡。Lindsey等[2]提出了PEGASIS 算法，該算法將網(wǎng)絡中的節(jié)點逐個連接起來形成長鏈，然后沿著長鏈進行數(shù)據(jù)傳輸，最后再將數(shù)據(jù)傳輸給基站。劉偉強等[3]針對無線傳感器網(wǎng)絡中的PEGASIS協(xié)議進行了研究與改進，該算法以基站為圓心將無線傳感器網(wǎng)絡的監(jiān)測區(qū)域分成若干個幅度相等的扇形區(qū)域，然后分別在每個扇區(qū)內形成通信樹，數(shù)據(jù)先由通信樹的樹葉傳輸?shù)綐涓?，然后樹根再傳輸給基站。該算法通過通信樹的傳輸方式有效降低了節(jié)點的傳輸能耗，但是均勻劃分扇區(qū)的策略可能導致某些扇區(qū)的節(jié)點都距離基站較遠，使得這些扇區(qū)中節(jié)點的能量消耗過快。王海浪等[4]提出一種基于PEGASIS 的剩余能量距離分區(qū)（PEGASIS-REDP）協(xié)議，該算法在建立網(wǎng)絡連接時對網(wǎng)絡進行均勻分區(qū)并分別在每個分區(qū)中單獨成鏈以降低傳輸鏈中差鏈的數(shù)量。該算法通過降低差鏈數(shù)量有效降低網(wǎng)絡的能耗，但是仍然無法避免傳輸鏈上出現(xiàn)差鏈而導致部分節(jié)點能量消耗過快。胡中棟等[5]提出一種雙層樹型高能效多鏈路由算法，該算法在成鏈時使基站附近的節(jié)點不入鏈以降低分鏈和鏈頭鏈的能耗，用啟發(fā)式算法優(yōu)化鏈的傳輸路徑；選取主鏈頭時綜合考慮節(jié)點的剩余能量和節(jié)點與基站的距離，在選取分鏈頭時綜合考慮了節(jié)點的剩余能量和節(jié)點與相鄰分鏈頭的距離。但是分鏈之間的傳輸距離過長導致鏈頭能量消耗過快。安葳鵬等[6]提出基于改進灰狼優(yōu)化算法的無線傳感器網(wǎng)絡路由協(xié)議，該算法將無線傳感器網(wǎng)絡的監(jiān)測區(qū)域進行分區(qū)，先以基站為圓心將區(qū)域劃分為多個環(huán)帶，然后在環(huán)帶的基礎上進行扇形劃分以降低節(jié)點的遠距離傳輸能耗，再分別在每個分區(qū)中單獨成鏈，最后利用改進的灰狼優(yōu)化算法選取簇首。然而該算法的分區(qū)方式可能導致部分扇區(qū)中節(jié)點過于分散，使得這些節(jié)點的能量消耗過快。

針對以上算法存在的問題，本文提出基于貪婪算法的樹形WSN 低功耗路由算法，該算法引入樹的概念，并通過貪婪算法形成樹，然后基于傳輸距離最近原則進行樹的融合，最后使所有樹的根延伸到基站。

1 網(wǎng)絡模型

1.1 系統(tǒng)模型

本文假定所有傳感器節(jié)點隨機分布在正方形區(qū)域內，并有以下設定：

（1）無線傳感器網(wǎng)絡由多個傳感器節(jié)點和一個基站組成；

（2）基站的能量無限制；

（3）傳感器節(jié)點和基站都是靜止的，且它們的坐標都是已知的；

（4）每個節(jié)點都有唯一固定的ID 號；

（5）任意節(jié)點都能進行數(shù)據(jù)融合。

1.2 能耗模型

本文中網(wǎng)絡的能耗模型采用與文獻[4]相同的一階無線電能耗模型。

發(fā)送L比特數(shù)據(jù)所消耗的能量計算公式為：

式中：Eelec為發(fā)射電路和接收電路的功耗；εfs為自由空間信道模型下放大器功率的放大倍數(shù)；εamp為多路徑衰減模型下放大器功率的放大倍數(shù)；d為發(fā)送節(jié)點與接收節(jié)點之間的歐氏距離；為劃分空間模型的閾值。

接收L比特數(shù)據(jù)所消耗的能量計算公式為：

對長度為L比特的數(shù)據(jù)包進行融合時消耗的能量Eda的計算公式為：

2 基于貪婪算法的樹形WSN 低功耗路由算法

2.1 貪婪算法

貪婪算法（Greedy Algorithm）又稱貪心算法，具有實現(xiàn)簡單和時間復雜度低的特點[7-10]。它的基本思想是基于當前最優(yōu)解做出選擇，也就是在每一步選擇時只考慮最有利的選擇，而不會綜合考慮多次選擇對結果的影響，即只考慮眼前的最優(yōu)選擇[11-13]。

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

樹上的節(jié)點分為三類，分別是樹根節(jié)點、樹干節(jié)點和葉節(jié)點。一棵樹只有一個樹根節(jié)點，樹上所有節(jié)點的數(shù)據(jù)全都朝著樹根節(jié)點的方向傳輸，樹根節(jié)點負責接收數(shù)據(jù)、融合數(shù)據(jù)和發(fā)送數(shù)據(jù)；樹上的葉節(jié)點是樹的端點，只負責發(fā)送數(shù)據(jù)；除了樹根節(jié)點和葉節(jié)點，樹上其余的節(jié)點全都是樹干節(jié)點，樹干節(jié)點負責接收數(shù)據(jù)、融合數(shù)據(jù)和發(fā)送數(shù)據(jù)。因此，樹根節(jié)點和樹干節(jié)點的能耗相對較高，葉節(jié)點的能耗相對較低。

本文算法的數(shù)據(jù)傳輸階段參考經(jīng)典PEGASIS 算法[2]的方式，如圖1 所示，在一棵樹上有5 個節(jié)點，分別是A1、A2、A3、A4和A5。其中A5為樹根節(jié)點，A2和A4為樹干節(jié)點，A1和A3為葉節(jié)點。該樹的數(shù)據(jù)傳輸方向是其他節(jié)點朝著節(jié)點A5的方向傳輸數(shù)據(jù)。在數(shù)據(jù)傳輸階段，節(jié)點A1先將數(shù)據(jù)傳輸給節(jié)點A2，節(jié)點A2將接收到的數(shù)據(jù)與自身采集到的數(shù)據(jù)進行融合并得到一個相同長度的數(shù)據(jù)包；然后節(jié)點A2和節(jié)點A3將數(shù)據(jù)傳輸給節(jié)點A4，節(jié)點A4將接收到的數(shù)據(jù)與自身采集到的數(shù)據(jù)進行融合并得到一個相同長度的數(shù)據(jù)包；最后節(jié)點A4將數(shù)據(jù)傳輸給節(jié)點A5，節(jié)點A5將接收到的數(shù)據(jù)與自身采集到的數(shù)據(jù)進行融合并得到一個相同長度的數(shù)據(jù)包。

圖1 數(shù)據(jù)傳輸過程

2.3 本文算法中的定義

定義1：若在路由協(xié)議下無線傳感器網(wǎng)絡中某兩點（包括節(jié)點和基站）之間可直接傳輸數(shù)據(jù)，則將這兩點之間直接傳輸數(shù)據(jù)的路徑稱為“可用路徑”，網(wǎng)絡中全部“可用路徑”構成的集合稱為“可用路徑集合”，并用S表示。

定義2：任意點Ai（包括節(jié)點和基站）以及從點Ai出發(fā)沿集合S中的路徑可以到達的全部點構成一棵樹的全部點，一棵樹的全部點和集合S中連接這些點的全部路徑構成一棵樹。

定義3：設樹Vi中與樹Vi外某一點Ai之間距離最近的點是Bi，則樹Vi與Ai之間的距離等于Bi與Ai之間的距離。

2.4 基于貪婪算法形成樹

基于貪婪算法，每個節(jié)點只能將數(shù)據(jù)傳輸給距離自身最近的點（包括節(jié)點和基站），此時集合S包含且僅包含每個節(jié)點到距離其自身最近的點（包括節(jié)點和基站）之間的路徑，將數(shù)據(jù)傳輸給距離最近的點能夠有效降低每個節(jié)點傳輸數(shù)據(jù)的能耗，通過這種方法使多個節(jié)點形成數(shù)據(jù)傳輸鏈，這種數(shù)據(jù)傳輸鏈就是樹[14-15]。

在本文中，將樹分為第一類樹和第二類樹，包含基站的樹為第一類樹，不包含基站的樹為第二類樹。在基于貪婪算法形成樹后，如果在樹中不存在兩個節(jié)點使得這兩個節(jié)點互為距離彼此最近的節(jié)點，那么理論上該樹可以無限長并且能夠延伸到基站，這類樹就是第一類樹，第一類樹的樹根為基站。如果在樹中存在兩個節(jié)點使得這兩個節(jié)點互為距離彼此最近的節(jié)點，則該樹上的其他節(jié)點都會朝著這兩個節(jié)點的方向傳輸數(shù)據(jù)，因此該樹有限長且不與基站相連，這類樹就是第二類樹。

2.5 樹的融合

由于第二類樹不與基站相連，第二類樹上的節(jié)點無法沿集合S中的路徑將數(shù)據(jù)傳輸給基站，因此需要將第二類樹轉化為第一類樹。為了將第二類樹轉化為第一類樹，需要對樹進行融合。對樹進行融合的步驟是重復執(zhí)行如下步驟，直到第二類樹的個數(shù)為零：找出與第二類樹距離最近的點（包括節(jié)點和基站），若距離最近的點是基站，則將基站與該樹中距離基站最近的節(jié)點之間直接傳輸數(shù)據(jù)的路徑添加到集合S中，此時該樹轉化為第一類樹；若距離最近的點是節(jié)點，則將該節(jié)點與該樹中距離該節(jié)點最近的節(jié)點之間直接傳輸數(shù)據(jù)的路徑添加到集合S中，此時兩棵樹融合成一棵樹。

當?shù)诙悩涞膫€數(shù)降為零時，則表示網(wǎng)絡的數(shù)據(jù)傳輸路徑確定下來，然后就可以進行數(shù)據(jù)傳輸了。進行數(shù)據(jù)傳輸時，只能沿集合S中的路徑進行數(shù)據(jù)傳輸，并且總是朝著基站的方向進行數(shù)據(jù)傳輸。

2.6 能耗平衡

首先引入能量差額因子概念，節(jié)點Ai的能量差額因子Sub(Ai)的表達式為：

式中：N表示網(wǎng)絡中存活節(jié)點個數(shù)；Ej表示第j個存活節(jié)點Aj的剩余能量。

將網(wǎng)絡中的存活節(jié)點分為兩類，能量差額因子大于閾值α的節(jié)點構成集合U1，其余節(jié)點構成集合U2。

為了避免某些節(jié)點能量消耗過快從而導致無線傳感器網(wǎng)絡的監(jiān)測區(qū)域出現(xiàn)覆蓋空洞，在形成樹和融合樹時做如下處理：

（1）在利用貪婪算法形成樹時，為了使集合U1中的節(jié)點不成為樹干節(jié)點以降低能耗，不考慮集合U1中的節(jié)點而只將集合U2中的節(jié)點連接形成樹。在利用貪婪算法形成樹之后，在集合U2中分別為集合U1中的每一個節(jié)點尋找一個距離最近的節(jié)點，并將集合U1中的節(jié)點和在集合U2中與它們距離最近的節(jié)點之間直接傳輸數(shù)據(jù)的路徑添加至集合S中，使得集合U1中的節(jié)點都形成樹的葉節(jié)點以降低這些節(jié)點的能耗，至此所有存活節(jié)點都形成樹。

（2）在對樹進行融合時，為了避免集合U1中的節(jié)點由葉節(jié)點變成樹干節(jié)點從而增大能耗，在計算樹與節(jié)點的距離時不考慮樹內屬于集合U1的節(jié)點（計算樹與節(jié)點的距離時，假定樹內屬于集合U1的節(jié)點不存在），在尋找距離第二類樹最近的節(jié)點時同樣不考慮集合U1中的節(jié)點。

2.7 本文算法流程

本文算法的流程如下：

（1）計算每個存活節(jié)點的能量差額因子，然后根據(jù)能量差額因子將全部存活節(jié)點分為U1和U2兩個集合；

（2）為每個存活節(jié)點尋找距離最近的存活節(jié)點；

（3）利用貪婪算法將集合U2中的節(jié)點連接形成樹；

（4）將集合U1中的節(jié)點作為葉節(jié)點接入樹；

（5）進行樹的融合，直到第二類樹的個數(shù)降為零；

（6）開始數(shù)據(jù)傳輸，首先是葉節(jié)點將數(shù)據(jù)傳輸給樹干節(jié)點，然后樹干節(jié)點沿著樹干向數(shù)根節(jié)點（即基站）傳輸數(shù)據(jù)；

（7）本輪數(shù)據(jù)傳輸完成，并統(tǒng)計死亡節(jié)點ID 號，若節(jié)點未全部死亡，轉向步驟（1）。

3 實驗仿真及算法性能分析

3.1 仿真參數(shù)及性能指標

為分析算法的性能，本文利用MATLAB 對算法進行仿真，并將本文提出的算法與LEACH 算法[1]、PEGASIS 算法[2]和PEGASIS-REDP 算法[4]進行對比。

無線傳感器網(wǎng)絡的仿真模型：設定在400 m×400 m 正方形區(qū)域內隨機分布100 個節(jié)點，在正方形區(qū)域的正中心有一個基站，本文算法中能量差額因子的閾值α取0.01 J。其他仿真參數(shù)見表1 所列。

表1 仿真參數(shù)

網(wǎng)絡剩余總能量的變化情況反映了網(wǎng)絡總體能量的消耗速度以及能量的利用率，而存活節(jié)點個數(shù)的變化情況反映了無線傳感器網(wǎng)絡的監(jiān)測區(qū)域覆蓋率和無線傳感器網(wǎng)絡的生命周期。因此本文用網(wǎng)絡的剩余總能量和存活節(jié)點個數(shù)這兩項指標來評估算法的性能。

3.2 樹的形成和融合過程

傳統(tǒng)PEGASIS 算法通過單鏈形式傳輸數(shù)據(jù)，導致傳輸鏈上差鏈較多從而使差鏈一端的節(jié)點能耗過高。本文算法首先利用貪婪算法形成樹，然后對樹進行融合直到第二類樹的數(shù)量降為0，以避免差鏈的出現(xiàn)；同時引入能量均衡機制，避免剩余能量過低的節(jié)點接收數(shù)據(jù)和融合數(shù)據(jù)。網(wǎng)絡中樹的形成以及樹的融合如圖2 所示。

圖2 樹的形成和樹的融合

3.3 網(wǎng)絡存活節(jié)點個數(shù)對比

不同算法下存活節(jié)點數(shù)隨輪數(shù)的變化情況如圖3 所示。

圖3 存活節(jié)點數(shù)隨輪數(shù)的變化情況

根據(jù)圖3 可知，本文算法下的網(wǎng)絡中首個節(jié)點死亡時間相較于LEACH、PEGASIS 和PEGASIS-REDP 算法分別延長了89.1%、81.8%和68.3%。當有節(jié)點死亡后，就可能造成無線傳感器網(wǎng)絡監(jiān)測區(qū)域的覆蓋空洞，數(shù)據(jù)表明本文算法能夠有效延長網(wǎng)絡在監(jiān)測區(qū)域無覆蓋空洞時的工作時長。本文算法下的網(wǎng)絡中全部節(jié)點死亡時間相較于LEACH、PEGASIS 和PEGASIS-REDP 分別延長了70.4%、27.1%和14.4%，表明本文算法能夠有效延長網(wǎng)絡的生命周期。

3.4 網(wǎng)絡剩余總能量對比

不同算法下網(wǎng)絡的剩余總能量隨輪數(shù)的變化情況如圖4所示。

圖4 剩余總能量隨輪數(shù)的變化情況

從圖4 可以看出，本文算法下網(wǎng)絡的剩余總能量始終高于LEACH、PEGASIS 和PEGASIS-REDP 算法，并且當網(wǎng)絡剩余總能量為50%時，LEACH、PEGASIS、PEGASIS-REDP和本文算法下的網(wǎng)絡分別運行了269 輪、446 輪、468 輪和549 輪。這表明相較于其他三種算法，本文算法的能量利用率更高。

4 結 語

本文針對PEGASIS 算法存在的問題，提出基于貪婪算法的樹形WSN 低功耗路由算法，該算法引入樹的概念，并利用貪婪算法將節(jié)點連接起來形成樹；并且為了降低剩余能量過低的節(jié)點的能耗，在形成樹時避開剩余能量過低的節(jié)點，形成樹之后再將這些節(jié)點連接到樹上，然后基于距離最近原則進行樹的融合，直到所有樹都以基站為樹根。通過算法的仿真結果對比，表明本文所提出的算法在延長網(wǎng)絡生命周期、平衡節(jié)點能耗和提高能量利用率方面都明顯優(yōu)于LEACH、PEGASIS 和PEGASIS-REDP 算法。