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

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

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

0 引 言

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

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

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

1 網絡模型

1.1 系統模型

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

（1）無線傳感器網絡由多個傳感器節點和一個基站組成；

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

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

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

（5）任意節點都能進行數據融合。

1.2 能耗模型

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

發送L比特數據所消耗的能量計算公式為：

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

接收L比特數據所消耗的能量計算公式為：

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

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

2.1 貪婪算法

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

2.2 數據傳輸階段

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

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

圖1 數據傳輸過程

2.3 本文算法中的定義

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

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

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

2.4 基于貪婪算法形成樹

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

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

2.5 樹的融合

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

當第二類樹的個數降為零時，則表示網絡的數據傳輸路徑確定下來，然后就可以進行數據傳輸了。進行數據傳輸時，只能沿集合S中的路徑進行數據傳輸，并且總是朝著基站的方向進行數據傳輸。

2.6 能耗平衡

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

式中：N表示網絡中存活節點個數；Ej表示第j個存活節點Aj的剩余能量。

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

為了避免某些節點能量消耗過快從而導致無線傳感器網絡的監測區域出現覆蓋空洞，在形成樹和融合樹時做如下處理：

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

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

2.7 本文算法流程

本文算法的流程如下：

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

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

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

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

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

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

（7）本輪數據傳輸完成，并統計死亡節點ID 號，若節點未全部死亡，轉向步驟（1）。

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

3.1 仿真參數及性能指標

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

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

表1 仿真參數

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

3.2 樹的形成和融合過程

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

圖2 樹的形成和樹的融合

3.3 網絡存活節點個數對比

不同算法下存活節點數隨輪數的變化情況如圖3 所示。

圖3 存活節點數隨輪數的變化情況

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

3.4 網絡剩余總能量對比

不同算法下網絡的剩余總能量隨輪數的變化情況如圖4所示。

圖4 剩余總能量隨輪數的變化情況

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

4 結 語

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