無線傳感器網(wǎng)絡(luò)中的能效優(yōu)化路由算法

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

關(guān)鍵詞:無線傳感器網(wǎng)絡(luò); 動態(tài)規(guī)劃; 路由; 網(wǎng)絡(luò)生存周期

中圖分類號: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 引言

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

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

1 問題描述

在本文中，假定無線傳感器網(wǎng)絡(luò)中的傳感器節(jié)點位置是固定的，每個傳感器節(jié)點能量是有限的，每個傳感器節(jié)點能感知通信范圍內(nèi)的節(jié)點距離，且可根據(jù)距離自動調(diào)整節(jié)點信號發(fā)射功率，以減少不必要的能量消耗。

1.1 符號和公式

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

EIi是節(jié)點初始能量水平，ECi是節(jié)點當前能量水平;

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

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

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

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

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

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

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

z是能耗調(diào)節(jié)因子，zEmin表示從源節(jié)點s到目的節(jié)點t的能耗閾值;

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

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

1.2 優(yōu)化模型

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

1)優(yōu)化目標

max Ri(1)

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

2)約束條件

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

0otherwise(2)

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

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

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

式(4)表示從源節(jié)點s到目的節(jié)點t的路徑上節(jié)點發(fā)送一個數(shù)據(jù)包后剩余能量水平應(yīng)該大于0。

2 分級動態(tài)規(guī)劃路由模型

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

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

3 基于動態(tài)規(guī)劃的路由算法

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

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級中只有目的節(jié)點t，節(jié)點到節(jié)點自身路由的能耗為0，所以E(t，t)=0;當0≤k

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

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

4 仿真及結(jié)果

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

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

5 結(jié)束語

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

參考文獻:

[1]孫利民，李建中，陳渝.無線傳感器網(wǎng)絡(luò)[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]趙彤，郭田德，楊文國.無線傳感器網(wǎng)絡(luò)能耗均衡路由模型及算法[J].軟件學報，2009，20(11):3023-3033.

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

[8]楊文國，郭田德，趙彤.基于動態(tài)規(guī)劃的無線傳感器網(wǎng)絡(luò)的路由算法[J].計算機研究與發(fā)展，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.