無線傳感器網(wǎng)絡的路徑優(yōu)化節(jié)能算法?

王曙光 張蕓蕓

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

1 引言

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

2 研究背景

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

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

3 算法設計

3.1 網(wǎng)絡模型

本文所采用的網(wǎng)絡模型基于如下假設：

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

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

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

4）每個節(jié)點都具有功率調節(jié)功能，可以調節(jié)自身發(fā)射功率。

本文采用的網(wǎng)絡模型圖，如圖1所示。

圖1 網(wǎng)絡模型圖

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

3.2 能量消耗模型

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

節(jié)點接收k bit數(shù)據(jù)所需要的能量ERx為

節(jié)點處理k bit數(shù)據(jù)所需的能量Eda-fus為

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

3.3 算法步驟

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

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

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

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

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

其中，R（B）是節(jié)點B的剩余能量系數(shù)，D（A）是節(jié)點A所發(fā)送數(shù)據(jù)量的系數(shù)。對R和D有如下定義［3］：

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

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

如果newdist＜dist［j］；

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

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

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

綜上所述，整個網(wǎng)絡的運作過程如下：

1）簇頭選舉，并將網(wǎng)絡分成幾個均勻的簇；

2）簇成員申請加入簇；

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

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

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

6）各節(jié)點沿著最優(yōu)路徑發(fā)送收集的信息給SINK。

4 算法分析及實驗仿真

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

4.1 實驗參數(shù)設定

仿真的實驗參數(shù)設置如表1所示。

表1 參數(shù)設置

4.2 算法的有效性

圖2 網(wǎng)絡能量消耗

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

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

圖3 存活節(jié)點數(shù)

4.3 算法的復雜性

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

5 結語

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