無線傳感器網絡的路徑優化節能算法?

王曙光 張蕓蕓

（西安郵電大學自動化學院 西安 710000）

1 引言

對于無線傳感器網絡的應用而言，人們很自然地希望其部署之后能夠工作盡可能長的時間，或者在給定的時間內完成盡可能多的工作，這就要提高網絡的生存時間。生存時間通常是指無線傳感器網絡自開始工作到網絡無法完成數據傳輸的時間長短。由于無線傳感器網絡節點部署的隨機性，導致了不同的監測區域具有不同的節點部署密度，加之節點通信半徑的局限性，傳感器節點在工作時刻，網絡中的一部分節點即需要發送自身的感知數據，還要作為媒介幫鄰居節點轉發數據，這樣的工作量使得節點的能量消耗加速，網絡的生存時間快速減少。

2 研究背景

LEACH 協 議［1］（Low-Energy Adaptive Clusteriing Hierarchy）是由麻省理工學院的Wendi Rabiner-Heinzelman等提出的，它是一種低功耗的自適應路由協議。LEACH算法是基于“輪”的概念進行的，每一輪都包括簇的建立和穩定的數據傳輸階段。傳統的LEACH算法由于簇頭選擇的隨機性，會造成網絡中簇頭分布不均勻，進而產生網絡中的盲點。文獻［2］提出了LEACH-KED算法，它是針對LEACH協議的不足，在成簇方法、簇頭選擇、數據傳輸三個方面做了改進。此算法在選擇簇頭時綜合考慮了簇頭間的距離和簇頭的剩余能量因素，數據傳輸則采用多跳與單跳相結合的方法。但此算法仍存在不足之處，在簇頭與基站進行通信的過程中未考慮到最優路徑的選取。

針對這個問題，本文提出了基于LEACH的無線傳感器網絡的節能算法。算法的思想：在只考慮簇頭與基站間距離的情況下，可能出現同時存在多條相同跳數的最小路徑，此時，就需要考慮路徑所涉及到的相關節點的剩余能量，選擇剩余能量較多的節點路徑，從而延長網絡的生存時間。

3 算法設計

3.1 網絡模型

本文所采用的網絡模型基于如下假設：

1）假設將N個傳感器節點隨機拋灑在一個大小為L×W的區域內，所有傳感器節點隨機部署之后不再移動，且每個節點有唯一的ID號；

2）每個傳感器節點的都有相同的初始配置，且每個傳感器節點的能量是有限的，sink節點的能量是不受限；

3）借助定位技術，每個節點都可以獲取自身的位置信息和能量；

4）每個節點都具有功率調節功能，可以調節自身發射功率。

本文采用的網絡模型圖，如圖1所示。

圖1 網絡模型圖

本文將傳感器節點視為圖中的點，簇成員與簇首形成一個個完整的簇，簇頭與簇頭間的通信視為如圖1所示的實線邊，通信所要消耗的能量視為邊上的權值，這樣就形成了一個加權圖，從而將路徑的優化問題轉化為圖的極值問題來求解。

3.2 能量消耗模型

在無線傳感器網絡中，節點的能量優化問題一直是一個網絡生存時間長短的重要因素之一。節點能量的消耗多來自于節點間的數據接收，轉發和信息的處理，其他能耗微不足道，故本文只考慮數據接收，轉發和信息的處理能耗。本文采用傳統的無線通信模型，網絡節點發送k bit數據傳輸d m距離消耗的能量ETx為

節點接收k bit數據所需要的能量ERx為

節點處理k bit數據所需的能量Eda-fus為

其中，Eelec是節點發送與接收單位比特數據的能耗，Eda是節點處理單位比特數據的能耗，d0是決定衰減模型選取的重要因子，即傳輸距離門限，εfs=10pJ/(bit/m2)是自由空間模型中功率放大器的能耗，εmp=0.0013pJ/(bit/m4)是多徑衰減模型中功率放大器的能耗。

3.3 算法步驟

1）使用LEACH算法［2］對所有節點進行簇頭的選舉；

2）選出簇頭后，簇成員根據自己的距離選取距離自己最近的簇頭發送Join-Cluster消息（包含自己的位置信息和剩余能量信息），申請加入該簇；

3）在2）的基礎上，按照如下方法計算出各鄰居簇頭間的邊權值：

（1）在每一輪的簇頭競選過程中，每個節點都會與鄰居節點進行通信，因此各簇頭間的距離可視為已經距離。通過上述能量模型可計算得邊上的權值 wi，j，例如：假設A與B之間的距離為dA，B＜d0，則能量消耗為

（2）在選取最優路徑的時候，還需要考慮參加該路徑的節點的剩余能量情況，因此需引入剩余能量系數R和數據量系數D，這樣可以避免多次選擇同一條最短路徑而忽略該路徑節點的能量情況，從而導致節點過早死亡。故此時A到B的邊權計算方式為

其中，R（B）是節點B的剩余能量系數，D（A）是節點A所發送數據量的系數。對R和D有如下定義［3］：

（3）在計算出各邊權值之后，可以得到如圖1所示的加權圖G=（V，E），V=｛1，2，…，n｝，其中V為節點個數，E為邊數。

4）Sink節點廣播自身位置，簇頭依據如下算法求得與Sink節點通信的最優路徑，并將融合的數據信息通過選定的節點發送給Sink。本文在求最優路徑的時候，應用了Dijkstra［4］（迪杰斯特拉）算法，其基本思想是，設置頂點集合S并不斷地做貪心選擇來擴充這個集合。初始時，S中僅含有源。假設從集合G中取一任意的節點u，從源到u的最優路徑是由從源到u且中間經過的S中的節點組成的。將每個節點對應的最短路徑保存在數組dist內。使用Dijkstra算法從V-S中依次選出具有最短特殊路徑的節點u，把u增加到S中，且對數組dist做出相應的修改。直到集合V中的所有頂點都被包含在S內，此時，dist記錄的就是從源節點到所有其他節點的最短路徑［4］。設節點 v是源，二維數組 c［i］［j］表示的是邊（i，j）的權，dist［i］保存了當前時刻從源到節點i的最短路徑長度。

如果newdist＜dist［j］；

則dist［j］=newdist；prev［j］=u。

在算法中，用數組prev［i］來依次記錄從源到節點i的最短路徑上i的前一個頂點。在算法中更新最短路徑時，只要dist［u］+c［u］［j］＜dist［i］時，就置prev［i］=u。這樣在算法結束時，可以依據數組prev中保存的節點得到從源到i的最短路徑。

最終Ni到Sink的能量消耗可以表示為

綜上所述，整個網絡的運作過程如下：

1）簇頭選舉，并將網絡分成幾個均勻的簇；

2）簇成員申請加入簇；

3）計算各鄰居簇頭之間的邊權值；

4）使用本文改進的算法求出各簇頭與SINK通信的最優路徑；

5）簇頭向簇組員廣播計算的結果路徑和發送時間；

6）各節點沿著最優路徑發送收集的信息給SINK。

4 算法分析及實驗仿真

本文利用 Matlab對 LEACH、LEACH-KED、LEACH-DK算法進行仿真和比較，實驗中模擬了不同算法在相同條件下的網絡整體能量消耗和存活節點的，仿真環境如表1所示。

4.1 實驗參數設定

仿真的實驗參數設置如表1所示。

表1 參數設置

4.2 算法的有效性

圖2 網絡能量消耗

首 先 圖 2 將 LEACH、LEACH-KED、LEACH-DK三種算法進行模擬對比，可以看出隨時間的變化，網絡剩余能量都在減少，LEACH算法沒有采用隨機數和閾值的策略產生簇頭，導致簇頭的不均勻分布，使得網絡能耗不平衡，網絡生存時間減少。LEACH-KED在繼承了LEACH算法優點的情況下，還針對它的缺點進行了改進，將最優簇頭數和K-means聚類劃分算法結合起來，將區域均勻劃分，最后在選擇簇頭的時候充分考慮距離和剩余能量的因素，如圖2可見達到了較好的效果。本文在此基礎又加入了簇頭與基站通信時最優路徑的選擇的算法，使得在相同時間內網絡的剩余能量最多，從而延長網絡的生存時間。

如圖3所示，LEACH算法在50輪以前明顯出現節點死亡，LEACH-KED算法在將近100輪以后出現明顯的死亡；就整體而言，與LEACH算法相比較，LEACH-KED算法的節點存活率提高了15%，本文算法的節點存活率提高了30%。與LEACH-KED算法相比，本文算法的節點存活率提高了15%。綜上，LEACH-DK算法可以有效延長網絡工作時間。

圖3 存活節點數

4.3 算法的復雜性

LEACH-KED算法的時間復雜度是O（n2），空間復雜度為O（n），和LEACH算法保持一致。而LEACH-DK算法的主循環體需要的時間復雜度為O（n），這個循環體需要執行n-1次，所以完成循環需要O（n2）時間。算法的其余部分所需要的時間不超過O（n2）。因此，就復雜度而言，LEACH-DK更具有一定的優勢。

5 結語

本文基于無線傳感器網絡的能量消耗問題，提出了一種基于LEACH的最優路徑選擇的算法。該算法將參與路由通信的節點的剩余能量作為最優路徑選擇時的重要參數，使得各節點間的權值計算不僅限于距離參數。仿真結果表明，本文算法可以有效地降低網絡的能量消耗，延長網絡生存時間，該算法是可行的。