無線傳感器網絡中的能效優化路由算法

摘 要:根據無線傳感器網絡節點能量消耗和網絡生存周期的特點，通過建立動態規劃能量優化模型，在路由總能耗滿足能量閾值約束條件下，均衡消耗網絡中各節點能量，在此基礎上提出一種適合無線傳感器網絡的動態規劃路由算法。仿真結果表明，提出的路由算法能充分地利用有限的能量資源，較大地延長網絡生存周期并降低節點的平均能耗。

關鍵詞:無線傳感器網絡; 動態規劃; 路由; 網絡生存周期

中圖分類號:TP393文獻標志碼:A

文章編號:1001-3695(2010)06-2198-03

doi:10.3969/j.issn.1001-3695.2010.06.057

Energyefficient routing algorithm for wireless sensor networks

PENG Limin1，2， LIU Hao2

(1.Computer Application Teaching Department， Guangzhou Sport University， Guangzhou 510500， China; 2.School of Computer Science Engineering， South China University of Technology， Guangzhou 510641， China)

Abstract:According to the characteristic of nodes’ energy consuming and network lifetime in the wireless sensor networks， the paper proposed a dynamic programming model for energyoptimizing. Under the constraint of the total energyconsuming， which was less than the energy threshold value， presented a routing algorithm based on dynamic programming model， which made the network nodes’ energy consuming uniformly during routing from source to destination. Simulation results show that the proposed routing algorithm can utilize the limited energy resources rationally， and prolong the network lifetime and decrease the average energy consumption effectively.

Key words:wireless sensor networks (WSN); dynamic programming; routing; network lifetime

0 引言

無線傳感器網絡通常運行在人無法接近的惡劣或危險的遠程環境中，電源能量通常由于無法補充或替代而受到限制，因此，怎樣高效地利用無線傳感器網絡的能量資源，以提高網絡生存周期已成為無線傳感器網絡領域中一個十分重要的研究課題[1]。文獻[2]假定各節點可以在自適應調節發射功率的基礎上，基于線性規劃方法，提出一種最大化網絡生存周期的路由算法;文獻[3]通過建立無線傳感器網絡生存周期的理論模型，利用集中式迭代算法，提出了一種能量Pareto路由算法;文獻[4]提出根據網絡中各節點能量水平，選擇合適的中繼節點分發數據，均衡整個網絡的能量消耗，避免個別節點過早失效，從而延長網絡生存時間;文獻[5]通過設置節點能量水平閾值γ，應用剪枝方法裁掉網絡中節點能量水平低于閾值γ的相關邊，在此基礎上利用Dijkstra算法求解最小能耗路由;文獻[6]綜合考慮在傳感器網絡中節點鏈路接入、數據包傳輸能耗及節點剩余能量的基礎上，提出了一種自適應能耗均衡路由策略;文獻[7]綜合考慮網絡中節點的剩余能量與節點間傳輸數據的能耗，基于最短路徑樹算法，通過構造兩種不同的權值函數，提出了權值路由算法;文獻[8]在滿足能量三角不等式的前提下，應用動態規劃的思想，提出了一種最小跳步路由算法。

在無線傳感器網絡中，由于發送單位數據所消耗的能量通常與傳送距離的冪次方成正比[8]，路由能耗通常不滿足所謂的三角不等式，即數據從vi經vk傳到vj所消耗的總能量大于數據從vi直接到vj所消耗的能量通常不成立，也就是說，有時增加路由跳數反而能降低傳送數據的能耗，因此，文獻[8]中最小跳數路由不一定就是最小能耗路由;另一方面，由于無線傳感器網絡中流量分布不均勻性，即使采用最小能耗路由算法，也容易使網絡中個別關鍵節點能量過早耗盡而失效，造成網絡分割和連通性無法保持，直接導致網絡生存時間縮短。因此，在設計路由算法時，不僅要考慮路由的總能耗，還要從整個網絡系統的角度出發，根據具體的應用背景，考慮網絡中各個節點的能量水平。本文根據無線傳感器網絡的節點能量消耗和網絡生存周期特點，通過借鑒動態規劃思想，提出一個適合無線傳感器網絡的能效優化路由算法，達到既減少路由能耗，又使網絡中各節點的能量均衡配置，從而延長整個網絡的生存周期。

1 問題描述

在本文中，假定無線傳感器網絡中的傳感器節點位置是固定的，每個傳感器節點能量是有限的，每個傳感器節點能感知通信范圍內的節點距離，且可根據距離自動調整節點信號發射功率，以減少不必要的能量消耗。

1.1 符號和公式

采用G=G(V，A，c)表示給定的無線傳感器網絡。其中:V是節點集，節點個數為n;A是邊的集合;c:A|→R+為A中的每條邊賦一個權值，表示從節點i到節點j發送一個數據包所消耗的能量，即使用c(i，j)表示節點i發送一個數據包的能量消耗，ei，j表示節點i到節點j的邊，i，j∈V。

EIi是節點初始能量水平，ECi是節點當前能量水平;

Pj(s，t)表示從源節點s到目的節點t的第j條路徑;

Pall表示從源節點s到目的節點t的路徑集合;

Rj=minECii∈Pj(s，t)表示源節點s到目的節點t第j條路徑上節點當前能量水平最小值;

Ri=max{Rj|Pj(s，t)∈Pall}表示源節點s到目的節點t所有路徑中節點能量水平Rj中的最大值;

E(s，t)表示從源節點s到目的節點t的路由能耗;

E(k，t)表示從節點k到目的節點t的路由能耗，其中k∈V;

Emin表示從源節點s到目的節點t的最小能耗(采用Dijkstra最短路徑路由，以c(i，j)作為邊的權重);

z是能耗調節因子，zEmin表示從源節點s到目的節點t的能耗閾值;

P(v0，vk)=v0，v1…，vk，表示從節點v0到目的節點vk的路徑;

e(P(v0，vk)=∑k-1i=0c(vi，vi+1)，表示從節點v0到目的節點vk的路由能耗。

1.2 優化模型

為了求解在能耗約束條件下能量均衡路由問題，本文建立了以下能耗優化路由優化模型。

1)優化目標

max Ri(1)

式(1)使從源節點s到目的節點t路徑中Ri值最大，即網絡采用能量均衡路由，避免個別節點過早耗盡能量。

2)約束條件

xi，j=1if ei，j∈P(s，t)

0otherwise(2)

∑ei，j∈Ac(i，j)*xi，j

式(2)中的變量xi，j是二元變量，即如果邊ei，j是從源節點s到目的節點t路徑上的邊，則xi，j=1，否則為0;式(3)表示從s到t路由的總能量小于zEmin。

ECie(i，j)∈P(s，t)-c(i，j)>0(4)

式(4)表示從源節點s到目的節點t的路徑上節點發送一個數據包后剩余能量水平應該大于0。

2 分級動態規劃路由模型

無線傳感器網絡能效優化路由問題就是尋找無線傳感器網絡中從源節點s到目的節點t的能效最優路徑。動態規劃是把一個多階段過程問題轉換為一系列單階段問題，用不變嵌入原理求解原問題的最優策略，因此，動態規劃的這種處理問題方法非常適合用來解決無線傳感器網絡中的路由問題。為了將無線傳感器網絡的路由問題轉換為動態規劃問題，本文參考文獻[9]最短路徑問題的動態規劃求解方法，建立一個如圖1所示的n級多目標動態規劃模型。

如圖1所示，s表示源節點，t表示目的節點，每級有n個節點，分別標志為v0，v1，…，vn-1，為了區分每個節點在各級中的位置，使用vli表示第l級的第i個節點。使用cl(i，j)表示節點vli發送一個數據包到節點vl+1j的能耗，如果節點vl+1j不在節點vli的通信范圍內，那么vli和vl+1j在G=G(V，E，w)中無邊相連，則該邊的權重cl(i，j)=∞，且假定在相鄰兩級間連接自身節點邊的權重為0，即cl(i，i)=0。使用E(k，t)表示從節點k到目的節點t的路由能耗，其中k∈V，則vli到t路由的總能耗記為E(vli，t)。當l級中有n個節點的時候，那么向量El表示l級中各節點到t的路由能耗，即El=[E(vl0，t)，E(vl1，t)，…，E(vln-1，t)]。由于第0級僅有節點s，E0=[E(s，t)]。

3 基于動態規劃的路由算法

根據圖1，本文將無線傳感器網絡G表示為n級，且每級中最多有n個節點的網絡結構(第0級中只有源節點s，第n-1級中只有目的節點t，其他級中都有n個節點)，使用P(vik，t)表示第k級中節點i到目的節點t的路徑，使用R(vki，t)=minECjj∈P(vki，t)表示第k級中節點i到目的節點t路徑上節點的當前能量水平最小值，使用E(vik，t)表示第k級中節點i到目的節點t的路由總能耗。因此，根據無線傳感器網絡的路由問題描述，可以采用以下基于動態規劃的遞歸方法描述能耗路由問題:

E(vik，t)=maxECi{c(vik，vjk+1)+E(k+1，t)}

E(t，t)=0if k=n-1(5)

式(5)中，當k=n-1時，因為n-1級中只有目的節點t，節點到節點自身路由的能耗為0，所以E(t，t)=0;當0≤k

如果使用n×n的表格保存網絡各級中節點到目的節點t的能耗E(vik，t)以及各級中節點到目的節點t路徑上節點當前能量水平的最小值R(vik，t)，那么，根據G=G(V，A，c)可以得到n-2級中每個節點到目的節點t的E(vin-2，t)和R(vjn-2，t)，然后利用式(5)和第n-2級的結果，則可以得到第n-3級各節點的E(vin-3，t)和R(vin-3，t)，依此往前推，進而可以得第0級中源節點s的E(s，t)和R(s，t)，因此，只要E(s，t)

由于分級路由模型中，每級最多有n個節點，計算每級中節點的E(vik，t)和R(vik，t)的時間復雜度為Θ(n2)，同時，動態規劃模型分為n級，所以該算法總的時間復雜度為Θ(n3)。

4 仿真及結果

本文采用NS2來模擬驗證提出的路由算法，在25×25區域內隨機分布50個傳感器節點，檢測控制中心節點(即sink節點)位于右上方區域中心，且該節點初始能量無限大，其他傳感器節點初始能量均設置為30 J，各個傳感器節點均處于靜止狀態且各節點射頻半徑相互獨立，節點之間是否連接取決于它們之間的距離，節點剩余能量隨發送數據包而減少，當節點剩余能量低于發送能耗時，即認為該節點由于能量太低而失效。假定節點可以自動調節發送功率，且將數據包發送到下一跳節點消耗能量為0.001×d3(d表示節點間距離)，因此，節點間發送數據消耗的能量取決于節點間距離。在本文實驗中，筆者在網絡中隨機地選擇源節點和目的節點(sink節點)進行數據包通信，各個數據包大小均設置為512 Byte。在隨機生成的網絡拓撲選取10個進行網絡模擬，對每個隨機網絡拓撲使用第一個數據包發送失敗前，網絡發送數據包個數表示網絡生存周期。本文實驗中，不考慮節點競爭信道、數據分組出錯、超時重發、信令傳遞、計算數據融合等傳感器網絡事件。由于本文中z是能耗調節因子，當z為1時，本文提出的基于動態規劃路由算法(DRP)即為最小能耗路由算法，當z為無窮大時，DPR路由算法即為能耗均衡路由算法。由于本文實驗中網絡節點個數較小，當z為10的時候，DPR路由算法也可以認為是能耗均衡路由算法。為了考察DRP路由算法在調節因子z取不同值時對網絡性能的影響，對DPR路由算法進行實驗模擬，實驗結果分別如圖2~4所示。為了便于圖中表示，當z=1時，DPR路由算法表示為MER，當z=10時，DPR路由算法表示為BER。

首先，考察z值對網絡生存周期的影響。從圖2可以看出，在z=1時，即采用最小能耗路由時，網絡最大發送數據包較小，隨z增大到一定程度時，網絡生存周期最大，然后隨z值繼續增大，網絡生存周期緩慢減少。在網絡規模確定的情況下，不同的節點發送半徑(最大)影響網絡拓撲結構，因而也會影響網絡中能量消耗關系，因此，在不同的發送半徑下，考察z取三個不同值(即z=1、3和10)時網絡中節點剩余能量比率(即平均節點的剩余能量水平/平均節點的初始能量水平)。從圖3可以看出，當z=1時，即網絡采用最小能耗路由算法(MER)網絡中平均節點剩余能量最大;當z=10時，即網絡采用能量均衡路由算法(BER)網絡中平均節點剩余能量最小，說明路由算法在傳送數據包的時候，MER采用最小能耗進行路由，而BER則只考慮網絡中當前節點能量水平，沒有考慮路由總能耗，所以能量消耗最多;然而，當z=3時，DPR算法既要考慮每個節點的能量水平，也要考慮路由能耗，所以網絡中平均節點剩余能量居中。圖4給出了節點在不同的發送半徑下，z取三個不同值(即z=1、3和10)對網絡生存周期的影響。從圖4可看出，三種情況中，使用MER時，網絡發送數據包個數最小，說明此時網絡生存周期最短，當z=10時，網絡生存周期較大，當z=3時，網絡生存周期最大。其主要原因是MER只考慮了路由能耗，沒有考慮網絡中節點能量水平，使個別關鍵節點能量過早消耗而失效，導致網絡生存周期縮短，而BER卻只考慮了路由中節點能量水平，沒有考慮路由能耗，也使得網絡生存周期不夠理想。然而，當DPR算法中z=3時，該算法既考慮了路由能耗，也考慮了節點能量水平，所以網絡生存周期最大。綜合上述三個實驗結果，說明在設計無線傳感器網絡路由算法的時候，只有綜合考慮節點能量水平和節點傳輸數據的能耗，路由算法才能達到提高網絡生存周期的目的。

5 結束語

本文針對無線傳感器網絡中路由能量消耗問題，通過借鑒動態規劃思想，在滿足路由能耗約束的條件下，選擇網絡中能量水平較高的節點進行路由，提出了一個適合無線傳感器網絡的能效優化路由策略。仿真結果表明，本文提出的DPR路由算法，能充分考慮路由能耗和各節點的能量水平，達到既降低網絡中路由能耗，又使網絡中節點能量均衡分布，延長無線傳感器網絡生存周期的目的。

參考文獻:

[1]孫利民，李建中，陳渝.無線傳感器網絡[M].北京:清華大學出版社，2005.

[2]CHANG J H， TASSIULAS L. Maximum lifetime routing in wireless sensor networks[J]. IEEE/ACM Trans on Networking， 2004，12(4):609-619.

[3]DAGHER J C， MARCELLIN M W， NEIFELD M A. A theory for maximizing the lifetime of sensor networks[J]. IEEE Trans on Communication， 2007，55(2):323-331.

[4]MAINWARING A， POLASTRE J， SZEWCZYK R， et al. Wireless sensor networks for habitat monitoring[C]//Proc of the 1st ACM Workshop on Wireless Sensor Networks and Applications. Atlanta:ACM Press，2002:88-97.

[5]TOH C K. Maximum battery life routing to support ubiquitous mobile computing in wireless Ad hoc networks[J]. IEEE Communications Magazine， 2001，39(7):138-147.

[6]趙彤，郭田德，楊文國.無線傳感器網絡能耗均衡路由模型及算法[J].軟件學報，2009，20(11):3023-3033.

[7]朱藝華，沈丹丹，吳萬登，等.無線傳感器網絡優化生存時間的動態路由算法[J].電子學報，2009，37(5):1041-1045.

[8]楊文國，郭田德，趙彤.基于動態規劃的無線傳感器網絡的路由算法[J].計算機研究與發展，2007，44(5):890-897.

[9]GRAMA A， GUPTA A， KARYPIS G， et al. An introduction to parallel computing: design and analysis of algorithms[M]. 2nd ed. Redwood City， CA: Addison Wesley，2003.