JIANG Zidong，F(xiàn)ENG Hui，YANG Tao，HU Bo

(Department of Electronic Engineering，F(xiàn)udan University，Shanghai 200433，China)

Joint Optimization of Battery Allocation and Routing for Maximum Lifetime in Wireless Sensor Networks*

JIANG Zidong，F(xiàn)ENG Hui，YANG Tao，HU Bo*

(Department of Electronic Engineering，F(xiàn)udan University，Shanghai 200433，China)

In order to prolong the lifetime of wireless sensor networks(WSN)，we jointly optimize the routing and battery allocation policy.The joint optimization problem is modeled with continuous and discrete battery levels respectively.In the case of continuous battery allocation，a linear programming problem is established，which obtains the optimal routing and battery allocation simultaneously.In the case of discrete battery allocation，a suboptimal but efficient method is proposed，which slacks a combinational optimization problem to a continuous form，and discretizes the battery levels in an optimal way.The simulation results show that our methods can substantially prolong the network lifetime and perform better than others.

wireless sensor networks;network lifetime;battery allocation;routing;linear programming

無線傳感器網(wǎng)絡(luò)(WSN)通常會(huì)在目標(biāo)區(qū)域中放置大量的廉價(jià)傳感器節(jié)點(diǎn)來完成數(shù)據(jù)的采集，傳輸與處理。由于其成本低，覆蓋率高的特性，在很多領(lǐng)域都引起了廣泛關(guān)注［1－2］，比如環(huán)境數(shù)據(jù)監(jiān)測(cè)，災(zāi)難預(yù)警，目標(biāo)跟蹤等。在大多數(shù)的場(chǎng)景中，節(jié)點(diǎn)由電池供能，且更換電池所需要的成本很高，例如當(dāng)網(wǎng)絡(luò)布置在偏遠(yuǎn)區(qū)域中時(shí)。因此，在無線傳感器網(wǎng)絡(luò)的應(yīng)用中，如何在有限的電量下延長(zhǎng)網(wǎng)絡(luò)的工作時(shí)間，是一項(xiàng)重要的工作和挑戰(zhàn)。

無線傳感器網(wǎng)絡(luò)的壽命主要取決于節(jié)點(diǎn)的能耗能否平衡。在有數(shù)據(jù)匯聚節(jié)點(diǎn)(通常稱為Sink節(jié)點(diǎn))的多跳WSN中，Sink節(jié)點(diǎn)周圍的節(jié)點(diǎn)由于需要轉(zhuǎn)發(fā)大量數(shù)據(jù)而容易出現(xiàn)電量耗盡的情況，導(dǎo)致外部節(jié)點(diǎn)雖然有剩余電量，整個(gè)網(wǎng)絡(luò)卻無法繼續(xù)工作。這種現(xiàn)象被稱為能量空洞(Energy Hole)［3－5］。一些方法可以減輕這種現(xiàn)象，比如合理規(guī)劃節(jié)點(diǎn)的放置策略和放置密度［6－7］，或者引入可移動(dòng)的Sink節(jié)點(diǎn)［8－10］來平衡全網(wǎng)能耗。但是很多應(yīng)用場(chǎng)景中，節(jié)點(diǎn)的位置是預(yù)先確定不可更改的。比如在氣象數(shù)據(jù)監(jiān)測(cè)網(wǎng)絡(luò)中，節(jié)點(diǎn)的放置有嚴(yán)格的規(guī)定，這關(guān)系到測(cè)量數(shù)據(jù)的準(zhǔn)確性。在這些場(chǎng)景中，節(jié)點(diǎn)電池電量分配［11－13］就是一個(gè)緩解能量空洞現(xiàn)象的有效方式。文獻(xiàn)［11］首先提出了對(duì)節(jié)點(diǎn)分配不同電量的電池可以有效的延長(zhǎng)網(wǎng)絡(luò)壽命的觀點(diǎn)。其多層分配方法MTA(Multiple Tiers Allocation Method)根據(jù)節(jié)點(diǎn)到Sink節(jié)點(diǎn)的跳數(shù)，將節(jié)點(diǎn)劃分到不同的層級(jí)，同一層級(jí)采用同一種電量的電池。但是MTA的方法需要假設(shè)WSN有均勻的節(jié)點(diǎn)分布密度，有一定局限性，而且它的推導(dǎo)和分析都是基于最小跳數(shù)路由策略。文獻(xiàn)［12－13］提出的CLPS(Cost Limited Pack Selection)沒有采用“層”的結(jié)構(gòu)以及均勻密度和最小跳數(shù)路由的假設(shè)，而是假設(shè)已知節(jié)點(diǎn)能耗分布。CLPS通過將不同電池打包為電池組，根據(jù)節(jié)點(diǎn)能耗分布提出了電池組分配的啟發(fā)式算法。本質(zhì)上，CLPS的性能還是依賴于路由，因?yàn)槁酚墒菦Q定節(jié)點(diǎn)能耗的主要因素之一，但CLPS沒有對(duì)路由進(jìn)行優(yōu)化。

文獻(xiàn)［14］首次提出了在已知初始電量下的最大壽命路由MLR(Maximum Lifetime Routing)，將WSN的壽命最大化問題建模成一個(gè)線性規(guī)劃問題。之后，很多基于MLR的擴(kuò)展和改進(jìn)被提出［15－16］，但是都沒有考慮到對(duì)于電量分配進(jìn)行優(yōu)化?？梢灶A(yù)見到，如果電量分配和路由一起優(yōu)化，網(wǎng)絡(luò)壽命可以更長(zhǎng)。

本文的主要貢獻(xiàn)是將網(wǎng)絡(luò)路由和電池電量分配進(jìn)行聯(lián)合優(yōu)化，在連續(xù)和離散兩種電池電量分配場(chǎng)景中分別建立優(yōu)化模型并求解。仿真顯示，本文的方法都可以顯著地延長(zhǎng)網(wǎng)絡(luò)壽命，比已有方法性能更優(yōu)。

1 系統(tǒng)模型與網(wǎng)絡(luò)壽命

本文考慮的WSN由N個(gè)靜態(tài)傳感器節(jié)點(diǎn)和一個(gè)Sink節(jié)點(diǎn)組成。每個(gè)傳感器節(jié)點(diǎn)i以固定速率采集數(shù)據(jù)，單位時(shí)間產(chǎn)生Si個(gè)數(shù)據(jù)。如果Si=0，節(jié)點(diǎn)i就只是轉(zhuǎn)發(fā)數(shù)據(jù)的路由節(jié)點(diǎn)，否則它就是源節(jié)點(diǎn)，可以完成數(shù)據(jù)采集和轉(zhuǎn)發(fā)的功能。如果兩個(gè)節(jié)點(diǎn)i和j之間的距離不大于最大傳輸半徑dmax，則它們可以直接通信，稱彼此為鄰居。與節(jié)點(diǎn)i相連的鄰居集合為Ni。我們假設(shè)在所有傳感器節(jié)點(diǎn)和Sink節(jié)點(diǎn)之間總存在通路，那么所有采集的數(shù)據(jù)都要通過多跳路由傳輸?shù)絊ink節(jié)點(diǎn)。數(shù)據(jù)的傳輸可以看成是一種網(wǎng)絡(luò)流r∈RN×N，rij代表了節(jié)點(diǎn)i到j(luò)的流速率。節(jié)點(diǎn)i的初始電量記為Bi，并假設(shè)只有數(shù)據(jù)的發(fā)送是消耗能量的，發(fā)送單位數(shù)據(jù)到節(jié)點(diǎn)j消耗電量Eij。

上面提到的系統(tǒng)模型可以很方便的擴(kuò)展到其他復(fù)雜形式［16］，包括多Sink節(jié)點(diǎn)網(wǎng)絡(luò)，無Sink節(jié)點(diǎn)的ad-hoc網(wǎng)絡(luò)以及考慮接收能量等，我們之后的分析和方法都將適用于這些擴(kuò)展模型。

1.1 最大壽命路由

在給定網(wǎng)絡(luò)拓?fù)?，初始電量{Bi}和鏈路能耗{Eij}的情況下，MLR的目的就是設(shè)計(jì)出最優(yōu)的網(wǎng)絡(luò)流r來最大化網(wǎng)絡(luò)壽命。文獻(xiàn)［17］描述了不同種類的WSN壽命的定義。本文采用一種最常見的定義方式:第1個(gè)死亡節(jié)點(diǎn)的壽命。節(jié)點(diǎn)死亡等價(jià)于節(jié)點(diǎn)電量耗盡，所以單個(gè)節(jié)點(diǎn)i的壽命是

而網(wǎng)絡(luò)壽命的定義是

基于這種壽命定義(2)，MLR可以通過求解以下的優(yōu)化問題得到，

其中，q=1/Tnet。第1個(gè)約束是流約束，表示單位時(shí)間每個(gè)節(jié)點(diǎn)發(fā)送的數(shù)據(jù)量等于接收加采集的數(shù)據(jù)量。第3個(gè)約束確保了在Tnet時(shí)間內(nèi)，沒有節(jié)點(diǎn)耗盡電池。

(P1)是一個(gè)典型的線性規(guī)劃問題［18］，它可以通過很多現(xiàn)有的工具包求解，比如MATLAB的CVX［19］。

2 連續(xù)電量分配場(chǎng)景

假設(shè)每個(gè)節(jié)點(diǎn)分配相同電量的電池，路由選擇(P1)計(jì)算出來的MLR，那么當(dāng)網(wǎng)絡(luò)死亡時(shí)，一部分節(jié)點(diǎn)的電池還有剩余電量，這些電量就被浪費(fèi)了。直觀的理解，如果節(jié)點(diǎn)的初始電量被合理地分配，原本浪費(fèi)的電量就能被利用，從而延長(zhǎng)網(wǎng)絡(luò)壽命。所以我們需要路由和電量分配的聯(lián)合優(yōu)化，來最大化網(wǎng)絡(luò)壽命。接下來，我們提出了兩種聯(lián)合優(yōu)化方法，分別針對(duì)連續(xù)電量分配場(chǎng)景和離散電量分配場(chǎng)景。本節(jié)只考慮連續(xù)電量分配場(chǎng)景。

連續(xù)電量分配意味著節(jié)點(diǎn)的初始電量可以是任意連續(xù)值。這適合于電池訂做的場(chǎng)景，或者電池規(guī)格很多，容量間隔很小，以至于可以近似認(rèn)為是連續(xù)值?？紤]到制作工藝和重量的限制，最大可能的電池容量為Bmax，

假設(shè)電池價(jià)格和容量是近似線性的，那么對(duì)于價(jià)格預(yù)算約束就轉(zhuǎn)化為了對(duì)于能量預(yù)算約束∑i∈NBi≤Btotal。給定網(wǎng)絡(luò)拓?fù)洌溌纺芎牡那闆r下，網(wǎng)絡(luò)壽命取決于路由和節(jié)點(diǎn)初始電量。所以我們提出如下的聯(lián)合優(yōu)化問題

(P1)和(P2)的主要區(qū)別在于(P2)中，初始電量{Bi}是優(yōu)化變量而不是已知值。因?yàn)榇嬖诩s束的可行域不是凸集，所以它是一個(gè)非凸的優(yōu)化問題。一般非凸問題的算法不能保證得到全局最優(yōu)解，它的效果和初始點(diǎn)的選取以及迭代步長(zhǎng)等參數(shù)有關(guān)。而接下來提出的算法要得到(P2)的最優(yōu)解。

將式(4)代入(P2)，得到以下優(yōu)化問題。

這里(P3)是一個(gè)凸問題(線性規(guī)劃問題)，可以方便的求解。

定義(P2)的可行域?yàn)棣?，最優(yōu)值為q*。而Φ3為(P3)的可行域與對(duì)應(yīng)的電量B的集合，對(duì)應(yīng)關(guān)系由式(4)給出。設(shè)(P3)最優(yōu)值為qc，其中一組最優(yōu)解是{rc，qc}，對(duì)應(yīng)的電量分配為Bc，Bc可以通過式(4)由{rc，qc}解出。這里上標(biāo)c表示這些變量屬于連續(xù)(continuous)電量分配的場(chǎng)景。

定理1{rc，qc，Bc}是(P2)的一組最優(yōu)解。

證明因?yàn)槭?4)是∑j∈NiEijrij≤Biq的一種特例，所以有Φ3?Φ2，{rc，qc，Bc}∈Φ2。為了證明定理1，只需要證明qc=q*即可。

已知{r*，q*，B*}是(P2)的一組最優(yōu)解?？梢缘玫皆诰W(wǎng)絡(luò)停止工作后，節(jié)點(diǎn)i的剩余電量為ΔBi。接下來，根據(jù)剩余電量的不同，將{r*，q*，B*}分為3種情況。

情況1:ΔBi=0，?i∈N

這里，式(4)對(duì)每一個(gè)節(jié)點(diǎn)都成立，所以{r*，q*，B*}∈Φ3。因?yàn)閝c是(P3)的最優(yōu)值，有q*≥qc。然而，因?yàn)棣??Φ2，必然有q*≤qc。所以只能是qc=q*。

情況2:?j∈N，ΔBj＞0以及?i∈N，Bi=Bmax

如果在B*中去除將被剩余的部分，將得到新的分配方案Bnewi=B*i－ΔBi，?i∈N。這樣的改變不會(huì)違背(P2)的約束以及改變最優(yōu)值q*。修改后的解是{r*，q*，Bnew}，它將被劃分到情況1。根據(jù)之前的分析，得到qc=q*。

情況3:?j∈N，ΔBj＞0以及?i∈N，Bi＜Bmax

在這種情況下，總可以對(duì)電量分配做出以下調(diào)整:從浪費(fèi)的電量中取出一小部分，將它平均分配到所有節(jié)點(diǎn)，而依舊保持?i∈N，Bi≤Bmax。這樣原來最先死亡的節(jié)點(diǎn)有更多的電量，在保持路由不變的情況下，網(wǎng)絡(luò)的壽命會(huì)延長(zhǎng)。這與q*是(P2)最優(yōu)解的定義矛盾。所以這種情況是不可能出現(xiàn)的。

綜上所述，我們得到qc=q*，從而證明了定理1。

連續(xù)電量分配與路由聯(lián)合優(yōu)化方法(CBAR)如下所示。由定理2可知，CBAR得到的{rc，qc，Bc}是網(wǎng)絡(luò)壽命最大化的最優(yōu)解。

算法1連續(xù)電量分配與路由聯(lián)合優(yōu)化方法(CBAR)

步驟1:計(jì)算路由:解線性規(guī)劃問題(P3)，得到最優(yōu)路由rc和對(duì)應(yīng)的最大網(wǎng)絡(luò)壽命Tnet=1/qc。

步驟2:電量分配:根據(jù)式(4)，分配各節(jié)點(diǎn)電量Bc。

CBAR中不存在任何的電量浪費(fèi)。將式(4)代入式(1)，得到所有節(jié)點(diǎn)的壽命是一致的，T1=T2=…=TN=Tnet，它們將同時(shí)耗盡電量。在(P2)的多組最優(yōu)解中，CBAR給出了最“節(jié)省電量”的解。

3 離散電量分配場(chǎng)景

在很多實(shí)際應(yīng)用中，節(jié)點(diǎn)電池只有幾種合適的規(guī)格可以選擇，也就是說，節(jié)點(diǎn)初始電量是在一個(gè)有限集合中選擇。本節(jié)考慮這種離散電量分配下的網(wǎng)絡(luò)壽命最大化問題。

假設(shè)有K種規(guī)格的電池可供選擇，按電量大小排序有bK＞…＞b1=0。所以節(jié)點(diǎn)的初始電量Bi滿足Bi∈{b1，b2，…，bK}，?i∈N。與(P2)類似，在給定網(wǎng)絡(luò)拓?fù)浜玩溌纺芎牡那疤嵯拢?lián)合優(yōu)化路由與電量分配的問題如下，

(P4)是一個(gè)組合優(yōu)化問題，一般需要窮舉遍歷來得到最優(yōu)解。如果在實(shí)際應(yīng)用中，N或者K很大，采用窮舉法需要很大的計(jì)算量。所以本節(jié)提出一個(gè)次優(yōu)但是高效的算法。

首先，通過將離散的約束Bi∈{b1，b2，…，bK}放松為連續(xù)的線性約束Bi≤bK，得到

令Bmax=bK，利用上一節(jié)的CBAR求解(P5)，得到路由rc，連續(xù)電量分配方案Bc以及對(duì)應(yīng)的最大壽命。

為了得到離散電量分配，Bc需要做離散化。定義節(jié)點(diǎn)i的電池序號(hào)是mi，mi∈{1，2，…，K}。由上節(jié)可知T1c=T2c=…=TcN=Tcnet。如果最終節(jié)點(diǎn)i的初始電池電量bmi小于連續(xù)分配的電量Bci，在路由rc不變的情況下，節(jié)點(diǎn)的壽命可以由式(1)推導(dǎo)出，

基于上式，本文提出了最優(yōu)電池離散化算法(ODA)，將Bc離散化為Bd。這里上標(biāo)d表示該變量屬于離散(discrete)電量分配的場(chǎng)景。圖1顯示了ODA的算法流程圖。圖中主要過程的解釋如下:

預(yù)先計(jì)算節(jié)點(diǎn)退化后壽命:計(jì)算當(dāng)節(jié)點(diǎn)電池“退化”到下一個(gè)更小電量的電池時(shí)，節(jié)點(diǎn)的壽命，即退化后壽命

停止:得到離散電量分配方案Bd={bmi}。

圖1 最優(yōu)電池離散化算法(ODA)流程圖

定理2經(jīng)過ODA離散化后的Bd是在路由rc下最優(yōu)的離散電量分配方案。

證明由ODA選擇退化節(jié)點(diǎn)的方法，說明了節(jié)點(diǎn)經(jīng)過退化后的壽命就是當(dāng)時(shí)的網(wǎng)絡(luò)壽命，并保證在所有可能的電池退化中，網(wǎng)絡(luò)壽命最小限度地下降。

構(gòu)造一張列表，按照網(wǎng)絡(luò)壽命的降序，對(duì)所有可能的KN種電量分配方案進(jìn)行排序。顯然，最優(yōu)的分配方案是第1個(gè)恰好滿足能量預(yù)算約束的分配方案。由于初始松弛，初始的電量分配在列表中位于最優(yōu)分配之前。步驟4導(dǎo)致最小的壽命減少，也就是說ODA每一次循環(huán)后，新的電量分配方案就是原來表中的下一個(gè)方案。所以O(shè)DA在循環(huán)中一定會(huì)到達(dá)最優(yōu)分配并停止。得證。

盡管{Bd，rc}并不是(P4)的最優(yōu)解，但是ODA給出了路由rc下的最優(yōu)離散電量分配。之后通過在固定Bd下優(yōu)化路由，來進(jìn)一步延長(zhǎng)網(wǎng)絡(luò)壽命。最終，我們提出了離散電量分配與路由的聯(lián)合優(yōu)化方法(DBAR)，避免了窮舉法的極大的計(jì)算復(fù)雜度，得到(P4)的次優(yōu)解。

算法2離散電量分配與路由的聯(lián)合優(yōu)化方法(DBAR)

步驟1:解松弛形式:放松(P4)的離散約束，得到(P5)。利用CBAR解出Bc，rc和。

步驟2:電池離散化:在路由rc下，利用ODA將Bc離散化為Bd。

步驟3:路由改善:將Bd代入(P1)中的B，得到壽命最大路由rd以及對(duì)應(yīng)的網(wǎng)路壽命=1/qd。

4 仿真分析

本節(jié)給出一些仿真結(jié)果，來顯示聯(lián)合優(yōu)化的效果以及CBAR與DBAR的性能。首先利用一個(gè)水環(huán)境監(jiān)測(cè)系統(tǒng)的例子來說明本文算法的適用場(chǎng)景和實(shí)際意義，之后是本文算法與已有其他算法的性能仿真與對(duì)比。

在接下來的仿真中，我們統(tǒng)一采用文獻(xiàn)［20］的能耗模型來計(jì)算鏈路能耗，Eij=c1+c2dαij，其中設(shè)c1=1 mJ/kbit，c2=10－5mJ/kbit/m4，α=4。

4.1 水環(huán)境檢測(cè)系統(tǒng)

考慮在水環(huán)境，比如湖泊或河流中，布置用于監(jiān)測(cè)水質(zhì)參數(shù)的WSN。網(wǎng)絡(luò)中存在三類節(jié)點(diǎn)，源節(jié)點(diǎn)，路由節(jié)點(diǎn)和Sink節(jié)點(diǎn)，源節(jié)點(diǎn)以固定的頻率采集水質(zhì)數(shù)據(jù)，并借助路由節(jié)點(diǎn)的中繼轉(zhuǎn)發(fā)將此數(shù)據(jù)傳遞給Sink節(jié)點(diǎn)。在水環(huán)境中，更換節(jié)點(diǎn)電池是很不方便的。我們需要在有限的能量預(yù)算下盡可能延長(zhǎng)人工維護(hù)的間隔，即網(wǎng)絡(luò)壽命。由于存在漁業(yè)管理和航道管理，并不是水域中的任何位置都可以安放節(jié)點(diǎn)，節(jié)點(diǎn)只能存在于一些可行的位置中。此外，為了考慮監(jiān)測(cè)的覆蓋率和對(duì)重點(diǎn)區(qū)域的關(guān)注，源節(jié)點(diǎn)的位置可以認(rèn)為是預(yù)先確定的。Sink節(jié)點(diǎn)的能耗不考慮，它一般與工作站相連，所以位置也是固定的。這樣，在最大化網(wǎng)絡(luò)壽命的問題中，有3種變量可以優(yōu)化:路由節(jié)點(diǎn)的數(shù)量和位置，路由以及電量分配方案。事實(shí)上，可以忽略第1個(gè)變量，而在每一個(gè)可行的位置上都放上路由節(jié)點(diǎn)。在電量分配后，如果某一個(gè)路由節(jié)點(diǎn)分配到的電池電量是零，那就不必安置節(jié)點(diǎn)。這樣，原問題就變成了本文之前討論的路由和電量分配的聯(lián)合優(yōu)化問題。

圖2顯示了一種可能的網(wǎng)絡(luò)拓?fù)?。在邊長(zhǎng)為90 m的正方形區(qū)域中，51個(gè)節(jié)點(diǎn)構(gòu)成了傳感器網(wǎng)絡(luò)。其中方點(diǎn)表示源節(jié)點(diǎn)，圓點(diǎn)表示路由節(jié)點(diǎn)，五角星表示Sink節(jié)點(diǎn)，網(wǎng)絡(luò)中最大傳輸半徑是20 m，源節(jié)點(diǎn)采集數(shù)據(jù)速率為2 kbit/s。

首先，先顯示在沒有電量分配的情況下，只優(yōu)化路由的效果。每個(gè)節(jié)點(diǎn)分配相同電量的電池Bi= 100 kJ，求解(P1)得到MLR。圖3(a)顯示了在相同電量分配UBA(Uniform Battery Allocation)的情況下MLR的網(wǎng)絡(luò)流。圖中，邊的線寬與該流的大小成正比，被標(biāo)記為三角形的節(jié)點(diǎn)為第1批死亡的節(jié)點(diǎn)。當(dāng)網(wǎng)絡(luò)死亡時(shí)，除了三角形節(jié)點(diǎn)電量耗盡以外，其他節(jié)點(diǎn)都有剩余電量。圖3(b)顯示了這些被浪費(fèi)的剩余電量，并將他們排序輸出，高達(dá)總能量預(yù)算48.54%的電量被浪費(fèi)了。由圖3可知，雖然傳統(tǒng)的MLR方法在確定電量分配的情況下，通過優(yōu)化路由而盡可能的最大化網(wǎng)絡(luò)壽命，但由于初始電池分配的不合理，仍然會(huì)導(dǎo)致當(dāng)部分節(jié)點(diǎn)耗盡時(shí)，其他節(jié)點(diǎn)可能有大量剩余電量未被利用。

圖2 水環(huán)境監(jiān)測(cè)網(wǎng)絡(luò)拓?fù)鋱D

之后是對(duì)本文兩種聯(lián)合優(yōu)化策略的仿真。與UBA的情況一致，能量預(yù)算為Btotal=100×50=5 ×103kJ。對(duì)于CBAR的仿真，設(shè)最大的可分配電池容量Bmax=300 kJ。圖4(a)顯示了CBAR的路由，圖4(b)顯示了對(duì)應(yīng)編號(hào)節(jié)點(diǎn)所分配的電量。網(wǎng)絡(luò)壽命為2.68×107s，約為310天，是UBA下壽命的兩倍多。由圖4可知，通過將電池分配作為優(yōu)化變量，可以大幅提高最終的網(wǎng)絡(luò)壽命，因?yàn)镃BAR通過合理分配電池電量，避免了剩余電量的浪費(fèi)，充分利用了能量預(yù)算，所以可以有更長(zhǎng)的網(wǎng)絡(luò)壽命。注意到CBAR還可以選擇最終安放的路由節(jié)點(diǎn)的數(shù)量，比如21號(hào)節(jié)點(diǎn)，它在圖4(a)中是孤立節(jié)點(diǎn)，在圖4(b)中分配電池電量為零，這就表示不需要被安放。

對(duì)于離散電量分配場(chǎng)景的仿真，我們假設(shè)可供選擇的電池電量為{0，50，100，200，300}kJ。圖5 (a)顯示了DBAR得到的路由和電量分配方案，節(jié)點(diǎn)形狀代表不同電量的電池，得到的網(wǎng)絡(luò)壽命是2.0×107s，約232 d。圖中米字形的孤立節(jié)點(diǎn)在實(shí)際系統(tǒng)中不需要被放置。圖5(b)顯示了排序后的各節(jié)點(diǎn)浪費(fèi)的電量。因?yàn)殡x散分配是連續(xù)分配的一個(gè)特例，且DBAR只是離散優(yōu)化的次優(yōu)算法，所以最終網(wǎng)絡(luò)壽命比CBAR的小，且存在一定數(shù)量的能量浪費(fèi)。但是與沒有電量分配的UBA相比，網(wǎng)絡(luò)壽命明顯增加且能量浪費(fèi)明顯減少。

圖3UBA仿真結(jié)果

圖5DBAR仿真結(jié)果

4.2 算法對(duì)比

本節(jié)將CBAR，DBAR與UBA，CLPS和MTA(文獻(xiàn)［14］的Problem 2)進(jìn)行性能對(duì)比。為了得到更加公平和通用的結(jié)果，在每一組參數(shù)進(jìn)行100個(gè)不同的隨機(jī)拓?fù)涞姆抡娌?duì)結(jié)果求均值。

首先是不同的網(wǎng)絡(luò)規(guī)模下的性能比較。五組測(cè)試場(chǎng)景，節(jié)點(diǎn)數(shù)分別是20、50、100、150和200，每組一半的節(jié)點(diǎn)是采集速率為2 kbit/s的源節(jié)點(diǎn)。能量約束隨著網(wǎng)絡(luò)規(guī)模而改變，以保證平均每個(gè)節(jié)點(diǎn)的電量預(yù)算是100 kJ。除此之外，區(qū)域面積也會(huì)變化，以保證5組場(chǎng)景下節(jié)點(diǎn)密度是定值0.008個(gè)/m2。我們?cè)O(shè)最大傳輸半徑是30 m，可選擇的電池電量是{0，50， 100，200，300}kJ，圖5顯示了不同算法的對(duì)比。注意所有的結(jié)果都與CBAR進(jìn)行了歸一化，因?yàn)槎ɡ?已經(jīng)證明CBAR給出了最優(yōu)解。CLPS的仿真選擇了CBAR的路由來計(jì)算能耗分布，并且將每一種電池認(rèn)為是電池組。

圖6給出了以下5點(diǎn)事實(shí)。

(1)所有算法的性能都不如CBAR(歸一化壽命均小于1)，因?yàn)樵谥挥新酚珊碗姵胤峙洳呗钥梢哉{(diào)整的場(chǎng)景中，CBAR已經(jīng)證明是最優(yōu)策略。而仿真再一次印證了定理1的結(jié)論。

(2)盡管DBAR是一個(gè)次優(yōu)方法，由于它具有最優(yōu)電池離散算法，以及最后根據(jù)電池改善路由的步驟，使其效果優(yōu)于已有其他方法。在所有網(wǎng)絡(luò)規(guī)模下，DBAR均可達(dá)到CBAR的80%的性能。而CLPS的啟發(fā)式電池選擇方法過于保守，影響性能。

(3)在所有的網(wǎng)絡(luò)規(guī)模下，DBAR和CLPS都比UBA的效果好，這意味著合適的電量分配對(duì)于網(wǎng)絡(luò)壽命的延長(zhǎng)起到重要作用。

(4)N越大，電量分配的作用(DBAR/CLPS與UBA的差距)就越明顯。因?yàn)榫W(wǎng)絡(luò)規(guī)模越大，UBA的能量空洞就越嚴(yán)重。電量分配可以很好的減輕這個(gè)現(xiàn)象。

(5)MTA的性能比UBA還要差。這是因?yàn)镸TA的電量分配方法是基于最小跳數(shù)路由，其他算法均對(duì)路由進(jìn)行了優(yōu)化。此外，MTA假設(shè)節(jié)點(diǎn)在區(qū)域中均勻分布且有相同的采樣速率，這些假設(shè)與仿真環(huán)境沖突。

之后，固定網(wǎng)絡(luò)規(guī)模為N=50，觀察電量預(yù)算約束從Btotal=2 500 kJ到Btotal=12 500 kJ變化時(shí)，各算法的性能。其他參數(shù)與之前仿真相同。圖7顯示了不同算法下，網(wǎng)絡(luò)壽命與能量預(yù)算約束的關(guān)系。所有算法下，隨著電量預(yù)算的增加，可以利用的總能量變多，所以網(wǎng)絡(luò)壽命也都隨之增加。各算法的性能與圖6中的表現(xiàn)相似，在各種電量預(yù)算約束下，DBAR都優(yōu)于其他離散電量分配的方法，很接近最優(yōu)的CBAR。而CLPS在高預(yù)算下反而不如UBA，這顯示了它啟發(fā)性算法的不穩(wěn)定性。

圖6 不同網(wǎng)絡(luò)規(guī)模下的性能比較

圖7 不同電量預(yù)算下的性能比較

5 結(jié)論

本文通過提出在設(shè)計(jì)路由的同時(shí)，合理分配各節(jié)點(diǎn)電池電量，通過聯(lián)合優(yōu)化路由和電池電量分配，最終實(shí)現(xiàn)網(wǎng)絡(luò)壽命的最大化。針對(duì)電池電量取連續(xù)值和離散值兩個(gè)場(chǎng)景，本文分別提出了CBAR和DBAR兩種聯(lián)合優(yōu)化算法，并有數(shù)學(xué)分析和證明。仿真結(jié)果顯示，與單一優(yōu)化路由或者電量分配的算法相比，本文的聯(lián)合優(yōu)化算法能更充分的利用能量，減小浪費(fèi)，使WSN達(dá)到更長(zhǎng)的網(wǎng)絡(luò)壽命。

［1］Akyildiz I F，Su W，Sankarasubramaniam Y，et al.Wireless Sensor Networks:A Survey［J］.Computer Networks，2002，38(4):393－422.

［2］Chong C Y，Kumar S P.Sensor Networks:Evolution，Opportunities，and Challenges［J］.Proceedings of the IEEE，2003，91(8):1247－1256.

［3］Ahmed N，Kanhere S S，Jha S.The Holes Problem in Wireless Sensor Networks:A Survey［J］.ACM Sigmobile Mobile Computing and Communications Review，2005，9(2):4－18.

［4］劉安豐，任炬，徐娟，等.異構(gòu)傳感器網(wǎng)絡(luò)能量空洞分析與避免研究［J］.軟件學(xué)報(bào)，2012，23(9):2438－2448.

［5］陸海明，劉學(xué)軍，錢江波.異構(gòu)傳感器網(wǎng)絡(luò)的能量空洞［J］.傳感技術(shù)學(xué)報(bào)，2010，23(10):1480－1485.

［6］Das D，Rehena Z，Roy S，et al.Multiple-Sink Placement Strategies in Wireless Sensor Networks［C］//Proceedings of International Conference on Communication Systems and Networks(COMSNETS)，IEEE，2013:1－7.

［7］Wang Z，Zhao X，Qian X.A Energy Balanced Deployment for Linear Wireless Sensor Networks［C］//Proceedings of International Conference on Computer Science and Network Technology(ICCSNT)，IEEE，2011，4:2345－2349.

［8］Gu Y，Ji Y，Li J，et al.EMS:Efficient Mobile Sink Scheduling in Wireless Sensor Networks［J］.Ad Hoc Networks，2013，11(5): 1556－1570.

［9］郭劍，孫力娟，許文君，等.基于移動(dòng)Sink的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)采集方案［J］.通信學(xué)報(bào)，2012，33(9):176－184.

［10］孫彥景，田紅，王迎.多Sink協(xié)同移動(dòng)的最大化網(wǎng)絡(luò)生存期優(yōu)化算法［J］.傳感技術(shù)學(xué)報(bào)，2012，25(10):1433－1437.

［11］Sichitiu M L，Dutta R.Benefits of Multiple Battery Levels for the Lifetime of Large Wireless Sensor Networks［M］//Networking 2005.Networking Technologies，Services，and Protocols;Performance of Computer and Communication Networks;Mobile and Wireless Communications Systems.Springer Berlin Heidelberg，2005: 1440－1444.

［12］Long H，Liu Y，Wang Y，et al.Battery Allocation for Wireless Sensor Network Lifetime Maximization under Cost Constraints［C］// Proceedings of the International Conference on Computer-Aided Design.ACM，2009:705－712.

［13］Liu Y，Wang Y，Long H，et al.Lifetime-Aware Battery Allocation for Wireless Sensor Network under Cost Constraints［J］.IEICE Transactions on Communications，2012，95(5):1651－1660.

［14］Chang J H，Tassiulas L.Routing for Maximum System Lifetime inWireless Ad-Hoc Networks［C］//Proceedings of the Annual Allerton Conference on Communication Control and Computing.The U-niversity;1998，1999，37:1191－1200.

［15］Chang J H，Tassiulas L.Maximum Lifetime Routing in Wireless Sensor Networks［J］.IEEE/ACM Transactions on Networking (TON)，2004，12(4):609－619.

［16］Madan R，Lall S.Distributed Algorithms for Maximum Lifetime Routing in Wireless Sensor Networks［J］.IEEE Transactions on Wireless Communications，2006，5(8):2185－2193.

［17］Gandham S R，Dawande M，Prakash R，et al.Energy Efficient Schemes for Wireless Sensor Networks with Multiple Mobile Base Stations［C］//Globecom IEEE 2003，1:377－381.

［18］Boyd S P，Vandenberghe L.Convex Optimization［M］.Cambridge University Press，2004.

［19］Grant M，Boyd S，Ye Y.CVX:MATLAB Software for Disciplined Convex Programming［CP/OL］.http://cvxr.com/cvx，2009.

［20］Heinzelman W B，Chandrakasan A P，Balakrishnan H.An Application-Specific Protocol Architecture for Wireless Microsensor Networks［J］.IEEE Transactions on Wireless Communications，2002，1(4):660－670.

蔣紫東(1989－)，男，碩士研究生，研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)，11210720022@fudan.edu.cn;

馮輝(1980－)，男，講師，主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)、分布式信號(hào)處理理論及應(yīng)用;

楊濤(1970－)，男，副教授，主要研究方向?yàn)闊o線通信理論與信號(hào)處理;

胡波(1986－)，男，教授、博士生導(dǎo)師，主要研究方向?yàn)閿?shù)字信號(hào)處理、數(shù)字通信，bohu@fudan.edu.cn。

最大化WSN壽命的電量分配與路由聯(lián)合優(yōu)化策略*

蔣紫東，馮輝，楊濤，胡波*
(復(fù)旦大學(xué)電子工程系，上海200433)

為了盡量延長(zhǎng)無線傳感器網(wǎng)絡(luò)的工作壽命，提出了一種對(duì)網(wǎng)絡(luò)路由和電池電量分配方案進(jìn)行聯(lián)合優(yōu)化的策略，在連續(xù)和離散兩種電池電量分配場(chǎng)景中分別建立優(yōu)化問題模型，并給出求解算法。在連續(xù)電量分配情況下，通過轉(zhuǎn)換成線性規(guī)劃問題，可同時(shí)解出最優(yōu)的路由和電量分配方案。在離散電量分配場(chǎng)景中，通過將組合優(yōu)化問題松弛為連續(xù)優(yōu)化問題，并提出一種最優(yōu)的電池離散化算法，得到一組次優(yōu)的路由和相應(yīng)的離散電量分配方案。仿真顯示該聯(lián)合優(yōu)化策略可以顯著地延長(zhǎng)網(wǎng)絡(luò)壽命。

無線傳感器網(wǎng)絡(luò);網(wǎng)絡(luò)壽命;電池電量分配;路由;線性規(guī)劃

TP393

A

1004－1699(2014)04－0536－08

2013－11－29修改日期:2014－04－02

C:6150P

10.3969/j.issn.1004－1699.2014.04.021

項(xiàng)目來源:國家教育部博士點(diǎn)基金項(xiàng)目(20120071110028)