蔣紫東， 馮 輝， 楊 濤， 胡 波

(復(fù)旦大學(xué) 電子工程系，上海 200433)

WSNs中路由與能量收集速率的聯(lián)合優(yōu)化*

蔣紫東， 馮 輝， 楊 濤， 胡 波

(復(fù)旦大學(xué) 電子工程系，上海 200433)

針對(duì)帶有能量收集裝置的無線傳感器網(wǎng)絡(luò)(WSNs)，提出了一種路由與能量收集速率聯(lián)合優(yōu)化的算法。通過規(guī)劃節(jié)點(diǎn)能量收集裝置的規(guī)格和網(wǎng)絡(luò)路由，使WSNs在滿足預(yù)算約束下達(dá)到最大的數(shù)據(jù)采集速率。算法將問題建模為一個(gè)組合優(yōu)化問題，并通過凸松弛和變量離散化算法，得到一組次優(yōu)結(jié)果，避免了高復(fù)雜度的窮舉遍歷。仿真結(jié)果表明:在不同的網(wǎng)絡(luò)規(guī)模下，該算法性能均優(yōu)于對(duì)比算法。

無線傳感器網(wǎng)絡(luò)； 能量收集； 網(wǎng)絡(luò)路由； 聯(lián)合優(yōu)化； 采集速率

0 引 言

無線傳感器網(wǎng)絡(luò)(WSNs)通常會(huì)在目標(biāo)區(qū)域中放置大量節(jié)點(diǎn)來完成數(shù)據(jù)的采集，傳輸與處理等工作。在傳統(tǒng)場景中，節(jié)點(diǎn)由電池供能，而更換電池可能需要很大的開銷，所以,在有限的電量下最大化網(wǎng)絡(luò)壽命是一項(xiàng)重要的工作。盡管文獻(xiàn)[1]總結(jié)了很多延長網(wǎng)絡(luò)壽命的方法，但是節(jié)點(diǎn)最終還是會(huì)電量耗盡。近年來提出的能量收集技術(shù)[2～4]使節(jié)點(diǎn)可以將外界環(huán)境中的太陽能、風(fēng)能、動(dòng)能等轉(zhuǎn)換為電能。理論上，如果各節(jié)點(diǎn)的能量收集速率大于消耗速率就可以實(shí)現(xiàn)能量可持續(xù)性，使網(wǎng)絡(luò)達(dá)到無限的壽命。這時(shí)主要目標(biāo)將由最大化網(wǎng)絡(luò)壽命轉(zhuǎn)變?yōu)樵谀芰靠沙掷m(xù)性下最大化工作量[5,6]。在周期采樣的WSNs中，工作量可以由傳感器節(jié)點(diǎn)采集速率來表示，即單位時(shí)間產(chǎn)生的數(shù)據(jù)量。

在有Sink節(jié)點(diǎn)的多跳網(wǎng)絡(luò)中，路由策略決定了節(jié)點(diǎn)間的能耗分布。一些針對(duì)能量收集場景的路由策略被提出以最大化工作量[7～9]。文獻(xiàn)[8,9]提出的R-MF算法實(shí)現(xiàn)了路由的離線計(jì)算，它將WSNs建模為流網(wǎng)絡(luò)，并用擴(kuò)展的Ford-Fulkerson算法來計(jì)算最大流。實(shí)際工作中，選擇一條邊上發(fā)送數(shù)據(jù)的概率正比于該邊上的最大流。R-MPRT[9]以節(jié)點(diǎn)因發(fā)送數(shù)據(jù)而消耗的能量的恢復(fù)時(shí)間作為權(quán)重，從而得到最短路徑路由。

上述算法均是在節(jié)點(diǎn)的能量收集速率已知的情況下進(jìn)行的。在很多應(yīng)用中，設(shè)計(jì)WSNs時(shí)可以規(guī)劃不同節(jié)點(diǎn)的能量收集設(shè)備[10]，不同規(guī)格的能量收集設(shè)備會(huì)導(dǎo)致不同的能量收集速率。以太陽能電池板為例，在相同光照條件下，面積和轉(zhuǎn)換效率都會(huì)影響最終的收集速率。由于預(yù)算有限，給所有節(jié)點(diǎn)配置最高規(guī)格的設(shè)備是不可能的，這就需要給節(jié)點(diǎn)分配不同規(guī)格的設(shè)備。因此,可以在設(shè)計(jì)WSNs時(shí)同時(shí)規(guī)劃節(jié)點(diǎn)能量收集設(shè)備的規(guī)格和路由，使網(wǎng)絡(luò)在它們的共同作用下達(dá)到更高的采集速率。

本文首先提出了路由和能量收集速率的聯(lián)合優(yōu)化，使WSNs在滿足一定的預(yù)算約束下采集速率最大。由于節(jié)點(diǎn)可選的能量收集設(shè)備規(guī)格有限，本文將該問題建模為一個(gè)組合優(yōu)化問題，并提出了聯(lián)合最大化采集速率(joint maximum sampling rate,JMS)算法來求解。仿真表明：JMS算法的性能優(yōu)于現(xiàn)有算法。

1 系統(tǒng)模型

本文考慮的WSNs由N個(gè)靜態(tài)節(jié)點(diǎn)和一個(gè)Sink節(jié)點(diǎn)組成。靜態(tài)節(jié)點(diǎn)包括傳感器節(jié)點(diǎn)和路由節(jié)點(diǎn)，它們的集合分別表示為Ns和Nr。2種節(jié)點(diǎn)都能接收數(shù)據(jù)并轉(zhuǎn)發(fā)，傳感器節(jié)點(diǎn)還以固定周期采樣并產(chǎn)生數(shù)據(jù)，采集速率為Skbit/s。距離小于最大傳輸半徑dmax的節(jié)點(diǎn)互為鄰居，記節(jié)點(diǎn)i的鄰居集合為Ni。假設(shè)在所有傳感器節(jié)點(diǎn)和Sink節(jié)點(diǎn)之間總存在通路，那么所有采集的數(shù)據(jù)最終通過多跳路由傳輸?shù)絊ink節(jié)點(diǎn)。路由可以看成是一種網(wǎng)絡(luò)流r∈RN×(N+1)， 其中,rij代表了節(jié)點(diǎn)i到j(luò)的流速率，單位是k bit/s。

節(jié)點(diǎn)配備了能量收集裝置，可以將外界環(huán)境中的能量轉(zhuǎn)換為電量。實(shí)際上能量收集速率會(huì)隨著環(huán)境變化而變化，系統(tǒng)會(huì)為每個(gè)節(jié)點(diǎn)配置合適容量的可充電電池作為緩沖來補(bǔ)償這種變化[11]。本文只考慮平均能量收集速率，單位是mJ/s。共有M種能量收集裝置供節(jié)點(diǎn)選擇，按平均能量收集速率排序λM>…>λ1=0，即節(jié)點(diǎn)單位時(shí)間從環(huán)境中收集的平均能量為Λi∈{λ1,λ2…,λM},?i∈N。

假設(shè)節(jié)點(diǎn)僅當(dāng)發(fā)送數(shù)據(jù)時(shí)消耗能量。定義節(jié)點(diǎn)i發(fā)送數(shù)據(jù)到節(jié)點(diǎn)j消耗的能量為EijmJ/kbit。為了滿足WSNs可持續(xù)工作的要求，每個(gè)節(jié)點(diǎn)都需要滿足能量可持續(xù)性的條件，即

(1)

這樣在給定網(wǎng)絡(luò)拓?fù)涞那闆r下，對(duì)r，S和Λ進(jìn)行聯(lián)合優(yōu)化，優(yōu)化問題如下

Λi∈{λ1,λ2,…,λM},?i∈N,

rij≥0,?i∈N,?j∈Ni,

S≥0.

(2)

由于Λ取離散值，問題(2)是組合優(yōu)化問題，一般需要窮舉遍歷來得到最優(yōu)解，需要很大的計(jì)算量。所以，之后本文提出一個(gè)次優(yōu)但是高效的JMS算法來求解問題(2)。

2 聯(lián)合最大化采集速率算法

2.1 凸松弛

首先將離散約束Λi∈{λ1,λ2,…，λM}松弛為連續(xù)約束0≤Λi≤λM,同時(shí)將能量持續(xù)性約束式(1)改為等式約束

(3)

這個(gè)改變不影響連續(xù)約束下的最優(yōu)值，但是可以保證對(duì)收集能量的完全利用，便于之后離散化算法的提出。所以,問題(2)變?yōu)?/p>

0≤Λi≤λM,?i∈N,

rij≥0,?i∈N,?j∈Ni,

S≥0.

(4)

這是一個(gè)線性規(guī)劃，可以用現(xiàn)有的工具包高效求解，比如:Matlab的CVX。規(guī)化(4)的最優(yōu)解為{Sc,rc,，Λc},上標(biāo)c表示這屬于變量松弛后的連續(xù)優(yōu)化問題。

2.2 能量收集速率離散化算法

本節(jié)提出能量收集速率離散化算法(energy harvesting rate discretization algorithm,ERDA)，使連續(xù)的Λc離散化為Λd，并分析其性能。上標(biāo)d為該變量取離散值。已知節(jié)點(diǎn)共有M種能量收集裝備可選擇，設(shè)節(jié)點(diǎn)i選擇的編號(hào)為wi，wi∈{1,…,M}，對(duì)應(yīng)的充電速率λwi。

引理1：在{Sc,rc,Λc}的基礎(chǔ)上保持路由不變，節(jié)點(diǎn)分配了能量收集裝備后，最大采集速率為

(5)

(6)

3)預(yù)先計(jì)算節(jié)點(diǎn)能量收集裝置“退化”到下一個(gè)更小收集速率后，網(wǎng)絡(luò)的最大采集速率

(7)

5)停止。

引理2：ERDA中步驟(3)的結(jié)果就是節(jié)點(diǎn)退化后WSNs的最大采集速率。

證明：由引理1知，證明引理2只需證明式(8)成立

(8)

通過引理2，可以得到下面的定理1來說明ERDA的特性。

定理1:經(jīng)過ERDA離散化后的Λd是在路由確定下最優(yōu)的能量收集裝置分配方案。

證明:構(gòu)建一張列表，將所有可能的MN種能量收集裝置分配方案下的采集速率按降序排列。步驟(1)的初始松弛保證了初始的采集速率高于最優(yōu)值，而引理2和步驟(4)保證了一次退化后，采集速率會(huì)下降為列表中的下一個(gè)或者保持不變(不同的分配對(duì)應(yīng)相同的采集速率)。所以,ERDA使采集速率以最小跨度單調(diào)下降，總能從初始狀態(tài)到達(dá)最優(yōu)分配下的采集速率，得證。

2.3 算法流程

ERDA得到離散的Λd。最后在能量收集速率確定的情況下，對(duì)路由進(jìn)行優(yōu)化。完整的JMS流程如下:

1)松弛問題(2)為線性規(guī)劃式(4)，求解得到{Sc,rc,Λc}；

2)在rc確定的路由下，利用ERDA將Λc離散化為Λd；

3) 取ΛJMS=Λd，代入問題(2)，重新優(yōu)化路由，得到rJMS和對(duì)應(yīng)的網(wǎng)路壽命SJMS。

{SJMS,rJMS,ΛJMS}就是JMS對(duì)問題(2)的最終結(jié)果。注意到ERDA只是在給定路由下的最優(yōu)離散化算法，得到的Λd與路由并不是聯(lián)合最優(yōu)的。JMS避免了對(duì)于能量收集裝置的窮舉遍歷，步驟(1)與步驟(3)都是求解線性規(guī)劃問題，ERDA只需要簡單的代數(shù)運(yùn)算，所以,JMS是高效的次優(yōu)算法。

3 仿真分析

圖1是一個(gè)JMS的示例。在邊長為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。有5種能量收集速率供節(jié)點(diǎn)選擇，為{0，5,10,20,30}mJ/s，能量收集裝置預(yù)算約束Λtotal=500 mJ/s。經(jīng)過JMS規(guī)劃后，圖1的邊的線寬與流大小呈正比，數(shù)字表示節(jié)點(diǎn)的能量收集速率。注意到能量收集速率為0的點(diǎn)也是孤立的點(diǎn)，表示這些節(jié)點(diǎn)沒有數(shù)據(jù)收發(fā)的任務(wù)，無需安放。

圖1 JMS下的WSNs示例Fig 1 WSNs example of JMS

JMS使圖1的WSNs達(dá)到最大采集速率為13.6 kbit/s。對(duì)同樣的拓?fù)?，如果不采用?lián)合優(yōu)化，而是給節(jié)點(diǎn)分配相同的能量收集裝置，Λi=10 mJ/s，R-MF，R-MPRT和最小跳數(shù)路由(minimum hop routing,MH)能達(dá)到的最大工作量分別為8.4，3.4,2.3 kbit/s，性能對(duì)于JMS下降了38 %，75 %,83 %。

為了得到更普遍的結(jié)果，本文之后測試不同的網(wǎng)絡(luò)規(guī)模下算法的性能。節(jié)點(diǎn)數(shù)N為10～100，50 %節(jié)點(diǎn)為傳感器節(jié)點(diǎn)，預(yù)算約束與區(qū)域面積隨節(jié)點(diǎn)變化，保持Λtotal=10N mJ/s和節(jié)點(diǎn)密度為0.008個(gè)/m2，最大傳輸半徑為3 m。其他條件與之前相同。每組參數(shù)進(jìn)行100次隨機(jī)拓?fù)涞姆抡?，并?duì)結(jié)果求平均。

圖2顯示仿真結(jié)果，從中可以看出網(wǎng)絡(luò)規(guī)模變大后，為了滿足Sink周圍節(jié)點(diǎn)的能量可持續(xù)條件，最大采集速率減小。但在各種網(wǎng)絡(luò)規(guī)模下，性能上均有JMS>R-MF>R-MPRT>MH成立。這是因?yàn)镴MS考慮了能量收集速率和路由的聯(lián)合優(yōu)化，而其他3種只考慮了路由策略。相較于啟發(fā)式算法R-MPRT，R-MF對(duì)路由進(jìn)行了優(yōu)化，故性能較好，而MH只考慮跳數(shù)，沒有考慮節(jié)點(diǎn)能耗，故性能不佳。

圖2 不同網(wǎng)絡(luò)規(guī)模下的算法性能比較Fig 2 Performance comparison of algorithm in different network scales

4 結(jié) 論

在配備能量收集裝置的WSNs中，為了在滿足預(yù)算約束和能量可持續(xù)性約束下最大化傳感器的采集速率，本文提出將路由與節(jié)點(diǎn)的能量收集速率進(jìn)行聯(lián)合優(yōu)化，并提出JMS算法求解。仿真顯示：在不同網(wǎng)絡(luò)規(guī)模下，JMS算法具有很好的性能，始終優(yōu)于現(xiàn)有算法。

[1] Anastasi G,Conti M,Di Francesco M,et al.Energy conservation in wireless sensor networks:A survey[J].Ad Hoc Networks,2009,7(3):537-568.

[2] Sudevalayam S,Kulkarni P.Energy harvesting sensor nodes:Survey and implications[J].IEEE Communications Surveys & Tutorials,2011,13(3):443-461.

[3] Roseveare N,Natarajan B.A structured approach to optimization of energy harvesting wireless sensor networks[C]∥Proceedings of Consumer Communications and Networking Conference (CCNC),IEEE,2013:420-425.

[4] 張華良,王 軍,于海斌,等.一個(gè)能量收集無線傳感器網(wǎng)絡(luò)路由協(xié)議[J].小型微型計(jì)算機(jī)系統(tǒng),2011,32(7):1277-1280.

[5] 馬 寧,李開宇,吳 寅,等.基于最大流的能量采集型無線傳感器網(wǎng)絡(luò)路由算法[J].傳感器與微系統(tǒng),2013,32(1):131-134.

[6] Peng S,Low C P.Energy neutral routing for energy harvesting wireless sensor networks[C]∥Proceedings of Wireless Communications and Networking Conference (WCNC),IEEE,2013:2063-2067.

[7] Hasenfratz D,Meier A,Moser C,et al.Analysis,comparison,and optimization of routing protocols for energy harvesting wireless sensor networks[C]∥Proceedings of Sensor Networks,Ubiquitous,and Trustworthy Computing(SUTC),IEEE,2010:19-26.

[8] Bogliolo A,Lattanzi E,Acquaviva A.Energetic sustainability of environmentally powered wireless sensor networks[C]∥Procee-dings of the International Workshop on Performance Evaluation of Wireless Ad-hoc,Sensor and Ubiquitous Networks,ACM,2006:149-152.

[9] Lattanzi E,Regini E,Acquaviva A,et al.Energetic sustainability of routing algorithms for energy-harvesting wireless sensor networks[J].Computer Communications,2007,30(14):2976-2986.

[10] Zhang S,Seyedi A.Analysis and design of energy harvesting wireless sensor networks with linear topology[C]∥Proceedings of the International Conference on Communications,IEEE,2011:1-5.

[11] Bogliolo A,Delpriori S,Lattanzi E,et al.Self-adapting maximum flow routing for autonomous wireless sensor networks[J].Cluster Computing,2011,14(1):1-14.

[12] 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.

Joint optimization of routing and energy harvesting rate in WSNs*

JIANG Zi-dong, FENG Hui, YANG Tao, HU Bo

(Department of Electronic Engineering,Fudan University,Shanghai 200433,China)

Propose an algorithm to jointly optimize routing and energy harvesting rate in wireless sensor networks(WSNs) with energy harvesting devices.By designing size and network routing of node energy harvesting devices,aiming at maximizing data sampling rate under the budget constraint.The algorithm models the problem as a combination optimization probles and by convex relaxation and variable discretization algorithm,and get a group of suboptimal solution avoid high complexity exhaustive search.The simulation results illustrate that performance of the algorithm is better than comparative algorithms in different network scales.

wireless sensor networks(WSNs); energy harvesting;network routing; joint optimization; sampling rate

2014—01—16

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

TP 393

A

1000—9787(2014)04—0017—04

蔣紫東(1989-)，男，浙江定海人，碩士研究生，研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)。