基于Lyapunov優(yōu)化的時(shí)變無(wú)線(xiàn)傳感網(wǎng)路由研究*

董齊芬,張其前

(浙江警察學(xué)院計(jì)算機(jī)與信息技術(shù)系,杭州 310053)

?

基于Lyapunov優(yōu)化的時(shí)變無(wú)線(xiàn)傳感網(wǎng)路由研究*

董齊芬*,張其前

(浙江警察學(xué)院計(jì)算機(jī)與信息技術(shù)系,杭州 310053)

針對(duì)無(wú)線(xiàn)傳感網(wǎng)應(yīng)用中監(jiān)測(cè)環(huán)境具有隨機(jī)性和不可預(yù)測(cè)性等因素使得節(jié)點(diǎn)感知速率通常是時(shí)變的且某些時(shí)刻會(huì)超出鏈路容量的實(shí)際問(wèn)題,設(shè)計(jì)了一種時(shí)變路由算法。在該算法中,將時(shí)變感知速率下的路由問(wèn)題建立成以時(shí)均的網(wǎng)絡(luò)能耗與丟棄感知數(shù)據(jù)代價(jià)的加權(quán)和最小為目標(biāo)的隨機(jī)優(yōu)化模型,并利用Lyapunov優(yōu)化技術(shù)求解該模型,進(jìn)而得到一種路由策略來(lái)實(shí)時(shí)決策每條鏈路上的數(shù)據(jù)流量以及由于節(jié)點(diǎn)感知速率持續(xù)超出鏈路容量而不得不丟棄的數(shù)據(jù)量。進(jìn)一步,討論感知數(shù)據(jù)不被丟棄的條件,建立目標(biāo)函數(shù)與感知信息最大傳輸時(shí)延之間的權(quán)衡關(guān)系。最后,通過(guò)仿真實(shí)驗(yàn),驗(yàn)證了本文算法在能耗、感知數(shù)據(jù)的丟棄量及傳輸時(shí)延之間的均衡關(guān)系。還在不同的最大數(shù)據(jù)感知速率下,比較了本文算法與AVE算法的性能。

無(wú)線(xiàn)傳感器網(wǎng)絡(luò);時(shí)變路由;Lyapunov優(yōu)化

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)WSNs(Wireless Sensor Networks)作為物聯(lián)網(wǎng)的“末梢神經(jīng)”,是一種綜合信息采集、處理和傳輸功能于一體的新型網(wǎng)絡(luò)信息系統(tǒng),在環(huán)境監(jiān)測(cè)、智慧城市、公共安全等領(lǐng)域有著廣泛應(yīng)用前景。但通常地,WSNs節(jié)點(diǎn)的能量、通信距離和鏈路容量等資源均是受限的。在滿(mǎn)足鏈路容量等有限資源約束的前提下,如何設(shè)計(jì)能量有效的路由機(jī)制一直以來(lái)都是WSNs研究熱點(diǎn)之一[1]。

目前,基于能量有效的路由研究已取得一定成果。其中,將最大化WSNs生存周期的路由問(wèn)題直接建模或轉(zhuǎn)換成線(xiàn)性規(guī)劃模型并采用經(jīng)典的最優(yōu)化法或最短路徑樹(shù)、人工智能等方法求解的研究思路受到了學(xué)者們的青睞。文獻(xiàn)[2]是較早用線(xiàn)性規(guī)劃模型表示網(wǎng)絡(luò)生存周期最優(yōu)路由問(wèn)題的典型代表作。該模型考慮了流量平衡約束和能耗約束,并采用次梯度算法實(shí)現(xiàn)分布式求解。在此基礎(chǔ)上,不少學(xué)者進(jìn)一步考慮實(shí)際條件,對(duì)這類(lèi)問(wèn)題深入研究[3-7]。如文獻(xiàn)[3]考慮WSNs中有多個(gè)Sink節(jié)點(diǎn)的情況,并將多個(gè)Sink節(jié)點(diǎn)的數(shù)據(jù)收集路由問(wèn)題分解成若干個(gè)單個(gè)Sink節(jié)點(diǎn)的路由問(wèn)題,從而建立優(yōu)化網(wǎng)絡(luò)生存時(shí)間的路由模型;文獻(xiàn)[4]在文獻(xiàn)[2]模型的基礎(chǔ)上增加了鏈路的帶寬資源約束;針對(duì)節(jié)點(diǎn)的位置不平等造成節(jié)點(diǎn)能耗不均衡從而在一定程度上減低了網(wǎng)絡(luò)生存時(shí)間的問(wèn)題,文獻(xiàn)[5-7]采用Sink節(jié)點(diǎn)移動(dòng)的方法解決。他們?cè)谇蠼庾顑?yōu)路由的同時(shí)優(yōu)化Sink節(jié)點(diǎn)的移動(dòng)路徑或移動(dòng)Sink節(jié)點(diǎn)在每個(gè)位置的停留時(shí)間。最近,還有學(xué)者研究如何根據(jù)節(jié)點(diǎn)剩余能量、節(jié)點(diǎn)度及鄰居節(jié)點(diǎn)狀態(tài)等參數(shù)來(lái)自適應(yīng)調(diào)節(jié)路由以均衡節(jié)點(diǎn)能耗[8-9]。

上述成果為能量有效的路由機(jī)制提供有力的理論支撐,但大部分認(rèn)為節(jié)點(diǎn)感知速率是常量。然而在實(shí)際應(yīng)用中,由于監(jiān)測(cè)環(huán)境具有隨機(jī)性,節(jié)點(diǎn)感知速率通常是時(shí)變的。文獻(xiàn)[10-12]雖然對(duì)時(shí)變感知速率問(wèn)題進(jìn)行了研究,但其前提是節(jié)點(diǎn)的平均感知速率是已知的。在具有隨機(jī)性和不可預(yù)測(cè)性的監(jiān)測(cè)環(huán)境中,節(jié)點(diǎn)的平均感知速率也是很難獲取的。本文對(duì)此問(wèn)題進(jìn)一步深入研究,設(shè)計(jì)一種時(shí)變路由算法。該算法還考慮了節(jié)點(diǎn)感知速率超出WSNs鏈路容量時(shí)的特殊情況。主要貢獻(xiàn)歸納為:①考慮WSNs應(yīng)用中監(jiān)測(cè)環(huán)境具有隨機(jī)性和不可預(yù)測(cè)性等實(shí)際因素,將時(shí)變感知速率下的路由問(wèn)題建立成以時(shí)均的網(wǎng)絡(luò)能耗與丟棄感知數(shù)據(jù)代價(jià)的加權(quán)和最小為目標(biāo)的隨機(jī)優(yōu)化模型;②利用解決無(wú)線(xiàn)網(wǎng)絡(luò)中的隊(duì)列系統(tǒng)動(dòng)態(tài)控制問(wèn)題的Lyapunov優(yōu)化技術(shù)[13],設(shè)計(jì)一種時(shí)變路由算法;③討論感知數(shù)據(jù)不被丟棄的條件,建立網(wǎng)絡(luò)能耗與感知信息的最大傳輸時(shí)延之間的權(quán)衡關(guān)系;④通過(guò)仿真實(shí)驗(yàn)來(lái)驗(yàn)證本文提出的時(shí)變路由算法的可行性和有效性,并與基于平均感知速率的路由算法進(jìn)行比較。

1 問(wèn)題描述與建模

用G(V,L)表示一個(gè)無(wú)向連通的無(wú)線(xiàn)傳感器網(wǎng)絡(luò),其中,V是所有節(jié)點(diǎn)的集合,包含N個(gè)傳感節(jié)點(diǎn)和1個(gè)Sink節(jié)點(diǎn),L是所有無(wú)線(xiàn)鏈路的集合。設(shè)Pmax為允許的節(jié)點(diǎn)最大發(fā)射功率,如果節(jié)點(diǎn)i和節(jié)點(diǎn)j之間進(jìn)行無(wú)線(xiàn)通信所需的發(fā)射功率小于Pmax,那么稱(chēng)節(jié)點(diǎn)i流向節(jié)點(diǎn)j的無(wú)線(xiàn)鏈路lij∈V存在,且無(wú)線(xiàn)鏈路是雙向存在的(但Sink節(jié)點(diǎn)沒(méi)有出鏈路),節(jié)點(diǎn)i和節(jié)點(diǎn)j相互稱(chēng)為鄰居節(jié)點(diǎn)。令Ni表示節(jié)點(diǎn)i的所有鄰居節(jié)點(diǎn)的集合。為方便敘述與分析,再作如下定義與假設(shè):

①傳感節(jié)點(diǎn)同時(shí)承擔(dān)數(shù)據(jù)采集和中繼任務(wù)。

②傳感節(jié)點(diǎn)的能耗主要用于收發(fā)數(shù)據(jù),忽略數(shù)據(jù)感知、計(jì)算等能耗。

式中:dij表示節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的距離,Eelec代表收發(fā)單位比特?cái)?shù)據(jù)時(shí)的電路電子能耗,εfs是放大單位比特?cái)?shù)據(jù)時(shí)所需要的電子能耗。

④無(wú)線(xiàn)鏈路的帶寬資源是有限的,設(shè)單位時(shí)間內(nèi)每條鏈路上的最大數(shù)據(jù)傳輸量為Rmax。

⑤由于WSNs應(yīng)用中的監(jiān)測(cè)環(huán)境具有隨機(jī)性和不可預(yù)測(cè)性,故不同節(jié)點(diǎn)在單位時(shí)間內(nèi)的數(shù)據(jù)感知量均不同且是隨機(jī)的。令節(jié)點(diǎn)i在時(shí)間t的數(shù)據(jù)感知量為ai(t),且有amin≤ai(t)≤amax,其中的amin和amax分別表示節(jié)點(diǎn)在單位時(shí)間內(nèi)的最小和最大數(shù)據(jù)感知量。

由于傳感節(jié)點(diǎn)的數(shù)據(jù)感知速率隨機(jī)可變,且無(wú)線(xiàn)鏈路的帶寬資源受限,故無(wú)法保證當(dāng)前時(shí)間內(nèi)的所有感知數(shù)據(jù)都能發(fā)送到Sink節(jié)點(diǎn)。為了利用帶寬資源受限的無(wú)線(xiàn)鏈路將感知信息在允許的收集時(shí)延要求內(nèi)傳輸?shù)絊ink節(jié)點(diǎn),本文首先將每個(gè)節(jié)點(diǎn)的感知數(shù)據(jù)存儲(chǔ)在相應(yīng)隊(duì)列中,然后通過(guò)一定的策略進(jìn)行處理。具體地,令Qi(t)為節(jié)點(diǎn)i的感知數(shù)據(jù)存儲(chǔ)隊(duì)列在時(shí)間t的存儲(chǔ)量,且根據(jù)下式更新:

Qi(t+1)=max{Qi(t)-ρi(t)-bi(t),0}+ai(t), ?i,t

(1)

式中:Qi(0)=0;ρi(t)≥0和bi(t)≥0是需要決策的變量,其中:ρi(t)表示在時(shí)間t發(fā)送出去的關(guān)于節(jié)點(diǎn)i的感知數(shù)據(jù)量。為使得當(dāng)前發(fā)送出去的數(shù)據(jù)能被Sink節(jié)點(diǎn)接收到,每個(gè)傳感節(jié)點(diǎn)應(yīng)滿(mǎn)足數(shù)據(jù)流量平衡約束:

(2)

式中:γij(t)≥0表示在時(shí)間t節(jié)點(diǎn)i發(fā)送給其鄰居節(jié)點(diǎn)j的數(shù)據(jù)量。因?yàn)閱挝粫r(shí)間內(nèi)每條鏈路上的最大數(shù)據(jù)傳輸量是有限的,所以γij(t)應(yīng)滿(mǎn)足如下約束:

γij(t)+γji(t)≤Rmax,?lij∈L且j≠Sinkk節(jié)點(diǎn)

γij(t)≤Rmax,j=Sink節(jié)點(diǎn)

(3)

bi(t)表示當(dāng)出現(xiàn)傳感節(jié)點(diǎn)的感知速率持續(xù)超出鏈路容量的特殊情況時(shí)不得不丟棄的數(shù)據(jù)量。用單調(diào)遞增的凸函數(shù)c(x)=α(x2+x)來(lái)表征丟棄感知數(shù)據(jù)的代價(jià),其中α是可調(diào)系數(shù)。該代價(jià)函數(shù)表明當(dāng)α給定時(shí),丟棄的感知數(shù)據(jù)越多,對(duì)整個(gè)應(yīng)用系統(tǒng)的影響越大,且隨著丟棄數(shù)據(jù)量的增加,其影響更是急劇增大的。為防止丟棄過(guò)多數(shù)據(jù)量從而破壞系統(tǒng)性能,令單位時(shí)間內(nèi)允許節(jié)點(diǎn)丟棄的最大數(shù)據(jù)量為bmax。

根據(jù)Lyapunov優(yōu)化技術(shù),為確保感知信息的收集時(shí)延是有限的,每個(gè)隊(duì)列應(yīng)是可穩(wěn)定的,即:

(4)

式中:E{·}表示數(shù)學(xué)期望。

隨著無(wú)線(xiàn)充電技術(shù)和智能移動(dòng)節(jié)點(diǎn)的發(fā)展,可在WSNs中部署移動(dòng)充電站為傳感節(jié)點(diǎn)提供高效及時(shí)的充電服務(wù),以保證傳感節(jié)點(diǎn)持久正常地工作[14-15]。但是,這并不代表可以任意浪費(fèi)節(jié)點(diǎn)能量,因此減少網(wǎng)絡(luò)能耗從而降低充電代價(jià)仍是WSNs研究中的重要指標(biāo)。故本文目標(biāo)是在滿(mǎn)足上述各項(xiàng)約束的前提下,合理決策ρi(t)、γij(t)及bi(t),使時(shí)均的網(wǎng)絡(luò)能耗與丟棄感知數(shù)據(jù)代價(jià)的加權(quán)和最小,即建立如下的隨機(jī)優(yōu)化模型:

(5)

2 算法設(shè)計(jì)

可以采用動(dòng)態(tài)規(guī)劃或馬爾科夫決策求解上述隨機(jī)優(yōu)化模型,但前提是節(jié)點(diǎn)感知數(shù)據(jù)量的先驗(yàn)統(tǒng)計(jì)信息是完全可知的。然而,對(duì)事件發(fā)生具有不可預(yù)測(cè)性的WSNs應(yīng)用來(lái)說(shuō),這很難滿(mǎn)足。為此,本節(jié)引入解決無(wú)線(xiàn)網(wǎng)絡(luò)中的隊(duì)列系統(tǒng)動(dòng)態(tài)控制問(wèn)題的Lyapunov優(yōu)化技術(shù),設(shè)計(jì)一種可行有效的算法求解上述隨機(jī)優(yōu)化模型,使得在任意時(shí)間t,只要根據(jù)當(dāng)前觀(guān)測(cè)值,即可計(jì)算出ρi(t)、γij(t)及bi(t)。

2.1 預(yù)備知識(shí)

定義虛擬隊(duì)列:

Zi(t+1)=

max[Zi(t)-bi(t)-ρi(t)+δ1{Qi(t)>0},0], ?i,t

(6)

式中:Zi(0)=0;δ是可調(diào)參數(shù),其取值影響感知數(shù)據(jù)的收集時(shí)延和隨機(jī)優(yōu)化問(wèn)題(5)的目標(biāo)函數(shù)值;1{Qi(t)>0}是符號(hào)函數(shù),當(dāng)Qi(t)>0時(shí),它為1,否則為0。首先,給出與感知信息傳輸時(shí)延有關(guān)的引理[13]。

(7)

再記Θ(t)=[{Qi},{Zi}]為當(dāng)前感知數(shù)據(jù)存儲(chǔ)隊(duì)列和相應(yīng)虛擬隊(duì)列的向量,并定義二次型Lyapunov函數(shù):

(8)

根據(jù)感知數(shù)據(jù)存儲(chǔ)隊(duì)列和相應(yīng)虛擬隊(duì)列的更新式(1)和(6),有:

(9)

最后一個(gè)不等式由0≤bi(t)≤bmax得到。然后,定義一階Lyapunov平移函數(shù)Δ(Θ(t)):

Δ(Θ(t))=E{L(Θ(t+1))-L(Θ(t))|Θ(t)}

(10)

進(jìn)一步,將隨機(jī)優(yōu)化問(wèn)題(5)的目標(biāo)函數(shù)以懲罰項(xiàng)的形式與Lyapunov平移函數(shù)相加,得到以下的Lyapunov平移函數(shù)-加-懲罰函數(shù):

(11)

式中:V是可調(diào)參數(shù),其取值也會(huì)影響數(shù)據(jù)收集時(shí)延和隨機(jī)優(yōu)化問(wèn)題(5)的目標(biāo)函數(shù)值。由式(9)可得:

(12)

2.2 算法實(shí)現(xiàn)

給出基于Lyapunov優(yōu)化的WSNs時(shí)變路由算法,如表1所示。算法的實(shí)現(xiàn)遵循Lyapunov優(yōu)化技術(shù)的基本思路,即選擇一種策略ρi(t)、γij(t)及bi(t),使得式(12)不等號(hào)右邊的表達(dá)式最小。

表1 基于Lyapunov優(yōu)化的WSNs時(shí)變路由流程

2.3 算法性能分析

分析當(dāng)感知數(shù)據(jù)量ai(t),?i服從獨(dú)立同分布時(shí)本文算法的性能。

定理1 若參數(shù)δ滿(mǎn)足0<δ≤E{ai(t)},?i,且bmax≥amax,那么,提出的算法具有以下特性:

①在任意時(shí)間t內(nèi),節(jié)點(diǎn)i的感知數(shù)據(jù)存儲(chǔ)隊(duì)列及相應(yīng)的虛擬隊(duì)列均滿(mǎn)足:

Qi(t)+Zi(t)≤Ωmax, ?i

(15)

式中:Ωmax=Vα+2bmax(Vα+1)+amax。

②感知數(shù)據(jù)的最大收集延時(shí)為:

(16)

③對(duì)?t,若節(jié)點(diǎn)i均有Qi(t)+Zi(t)≤Vα-δ時(shí),則節(jié)點(diǎn)i的感知數(shù)據(jù)不會(huì)被丟棄。

④令ρi(t)、γij(t)及bi(t)是根據(jù)算法1計(jì)算的值,φ是相應(yīng)的時(shí)均網(wǎng)絡(luò)能耗和丟棄感知數(shù)據(jù)代價(jià)的加權(quán)和。那么,φ與隨機(jī)優(yōu)化問(wèn)題(5)的最優(yōu)目標(biāo)函數(shù)值φopt之間滿(mǎn)足:

(17)

證明 ①用數(shù)學(xué)歸納法證明。顯然Qi(0)+Zi(0)=0<Ωmax。假設(shè)當(dāng)t=s時(shí),命題成立,即Qi(s)+Zi(s)≤Ωmax。下面證明當(dāng)t=s+1時(shí),命題仍成立。

首先,分析Qi(s)+Zi(s)≤Vα+2bmax(Vα+1)-δ的情況。根據(jù)式(1)和式(6)可知,更新Qi(s)和Zi(s)時(shí),它們的增加量分別不會(huì)超過(guò)amax和δ,故有Qi(s+1)+Zi(s+1)≤Qi(s)+Zi(s)+amax+δ≤Ωmax。

再分析Vα+2bmax(Vα+1)-δ

δ+Qi(s)+Zi(s)>Vα+2bmax(Vα+1)

(18)

令算法1的第2步中的子項(xiàng)為:

fi(bi(t))=Vc(bi(t))+bi(t)2-bi(t){Qi(t)+δ+Zi(t)}

則fi(bi(t))在0≤bi(t)≤bmax處的一階導(dǎo)數(shù)滿(mǎn)足:

Vα(2bi(t)+1)+2bi(t)-{Qi(t)+Zi(t)+δ}

(19)

上式表明當(dāng)Vα+2bmax(Vα+1)-δ

綜上,Qi(t)+Zi(t)≤Ωmax, ?i成立。

②將命題①的結(jié)果代入引理1即可。

③當(dāng)Qi(t)+Zi(t)≤Vα-δ時(shí),fi(bi(t))在0≤bi(t)≤bmax處的一階導(dǎo)數(shù)滿(mǎn)足:

Vα(2bi(t)+1)+2bi(t)-{Qi(t)+Zi(t)+δ}≥0

上式表明當(dāng)Qi(t)+Zi(t)≤Vα-δ時(shí),fi(bi(t))在區(qū)間[0,bmax]上是單調(diào)遞增的,故計(jì)算出bi(t)=0,即節(jié)點(diǎn)i的感知數(shù)據(jù)不會(huì)被丟棄。

(20)

(21)

然后,根據(jù)本文提出的算法原則,即選擇一種策略ρi(t)、γij(t)及bi(t)使得式(12)不等號(hào)右邊的表達(dá)式最小,可得:

(22)

式中:第3個(gè)不等式根據(jù)式(20)和式(21)、ε→0及0<δ≤E{ai(t)},?i得到;第4個(gè)不等式根據(jù)0≤bi(t)≤bmax、0≤ρi(t)≤Rmax和0≤ai(t)≤amax得到;最后一個(gè)等式是由bmax、Rmax和amax及δ均為常數(shù)得到。將Φ(t)的表示式(11)代入上式,然后在式的兩端取數(shù)學(xué)期望,則由迭代期望法則可得:

(23)

再將上式兩端除以TV,并從t=0到t=T-1依次相加,得:

(24)

因?yàn)镼i(t)和Zi(t)有界,所以L(fǎng)(Θ(t))有界。因此,令T→∞時(shí)可得:

(25)

綜上,4個(gè)命題全部得證。

可見(jiàn),當(dāng)感知數(shù)據(jù)量ai(t),?i服從獨(dú)立同分布時(shí),本文提出的算法使目標(biāo)函數(shù)值與感知信息的最大收集時(shí)延存在一定的均衡關(guān)系,即感知信息的最大收集時(shí)延與V和1/δ成正比,而目標(biāo)函數(shù)值與1/V和δ成正比。另外,由命題③可知,只要傳感節(jié)點(diǎn)的數(shù)據(jù)感知速率不持續(xù)超出WSNs鏈路容量,通過(guò)設(shè)置合理的代價(jià)函數(shù)c(·)就能保證感知數(shù)據(jù)不會(huì)被丟棄,且在能耗與最大收集時(shí)延之間達(dá)到均衡。

3 仿真實(shí)驗(yàn)

3.1 仿真設(shè)置

為了驗(yàn)證本文提出的時(shí)變路由算法的可行性和有效性,本部分對(duì)算法進(jìn)行仿真,仿真在MATLAB平臺(tái)上進(jìn)行。假設(shè)25個(gè)節(jié)點(diǎn)隨機(jī)部署于500 m×500 m的正方形區(qū)域內(nèi),仿真區(qū)域的中心位置布置一個(gè)Sink節(jié)點(diǎn),節(jié)點(diǎn)間的最大通信距離是140 m。本文產(chǎn)生的WSNs拓?fù)浣Y(jié)構(gòu)如圖1所示。仿真中用到的其他共同參數(shù):節(jié)點(diǎn)i在時(shí)間t的數(shù)據(jù)感知量ai(t)在區(qū)間[amin,amax]上隨機(jī)產(chǎn)生;發(fā)送單位比特?cái)?shù)據(jù)時(shí)電路電子能耗Eelec=50 nJ/bit;放大單位比特?cái)?shù)據(jù)時(shí)所需要的電子能耗εfs=100 pJ/(bit/m2);單位時(shí)間內(nèi)鏈路允許的最大傳輸量Rmax=1 000 bit;單位時(shí)間內(nèi)允許節(jié)點(diǎn)丟棄的最大數(shù)據(jù)量bmax=amax。

圖1 本文產(chǎn)生的WSNs拓?fù)浣Y(jié)構(gòu)

(26)

3.2 參數(shù)V與α對(duì)算法的影響

設(shè)置節(jié)點(diǎn)在單位時(shí)間內(nèi)的最小和最大數(shù)據(jù)感知量分別是amax=200 bit和amin=100 bit,參數(shù)δ=0.6×amax。隨著參數(shù)V和代價(jià)函數(shù)中的可調(diào)系數(shù)α的變化,感知數(shù)據(jù)存儲(chǔ)隊(duì)列、丟棄的總數(shù)據(jù)量、Sink節(jié)點(diǎn)接收到的總數(shù)據(jù)量及能耗等性能指標(biāo)的變化分別如圖2～圖5所示。

圖2 參數(shù)V和α對(duì)感知數(shù)據(jù)存儲(chǔ)隊(duì)列的影響

圖3 參數(shù)V和α對(duì)丟棄的總數(shù)據(jù)量的影響

圖4 參數(shù)V和α對(duì)Sink節(jié)點(diǎn)接收到的總數(shù)據(jù)量的影響

圖5 參數(shù)V和α對(duì)能耗的影響

分析可得:①通過(guò)選取合適的V和α的值,保證了感知數(shù)據(jù)的丟棄量為0,且當(dāng)α的值較大時(shí),即提高丟棄感知數(shù)據(jù)的代價(jià),較小的V值就能保證感知數(shù)據(jù)不被丟棄。如圖3所示,在此仿真環(huán)境下,當(dāng)α≥60時(shí),只要調(diào)節(jié)V的值使得Vα≥600,感知數(shù)據(jù)就不會(huì)被丟棄。②仔細(xì)觀(guān)察圖2、圖4和圖5,當(dāng)V值給定且調(diào)節(jié)α的值使得保證感知數(shù)據(jù)不被丟棄時(shí),再增加α的值對(duì)網(wǎng)絡(luò)的其他性能幾乎沒(méi)有影響。這表明在實(shí)際應(yīng)用中,可以選取較大的α值,從而為V值的選取提供更大的范圍。③根據(jù)圖3～圖5,當(dāng)丟棄的數(shù)據(jù)量越多,需要發(fā)送給Sink節(jié)點(diǎn)的數(shù)據(jù)量就越少,所以經(jīng)過(guò)能耗大的路徑發(fā)送的數(shù)據(jù)量減少,從而使得發(fā)送單位數(shù)據(jù)到達(dá)Sink節(jié)點(diǎn)的平均能耗就降低。④隨著V的增加,發(fā)送單位數(shù)據(jù)到達(dá)Sink節(jié)點(diǎn)的平均能耗就減少,但其代價(jià)是所有節(jié)點(diǎn)的感知數(shù)據(jù)存儲(chǔ)隊(duì)列平均值增加,即增大了數(shù)據(jù)到達(dá)Sink節(jié)點(diǎn)的平均時(shí)延。這和第2部分的理論分析結(jié)果是一致的。

圖6 參數(shù)δ對(duì)感知數(shù)據(jù)存儲(chǔ)隊(duì)列的影響

3.3 參數(shù)δ對(duì)算法的影響

設(shè)置節(jié)點(diǎn)在單位時(shí)間內(nèi)的最小和最大數(shù)據(jù)感知量分別是amax=200 bit和amin=100 bit,參數(shù)V=10及代價(jià)函數(shù)中的可調(diào)系數(shù)α=60。隨著參數(shù)δ從0.2amax增加到amax,得到:①感知數(shù)據(jù)的丟棄量均為0。這表明只要確定了合適的V值和α值,參數(shù)δ值的變化幾乎不會(huì)影響感知數(shù)據(jù)的丟棄情況;②如圖6所示,所有節(jié)點(diǎn)的感知數(shù)據(jù)存儲(chǔ)隊(duì)列平均值減少,即降低了數(shù)據(jù)到達(dá)Sink節(jié)點(diǎn)的平均時(shí)延。又由于數(shù)據(jù)丟棄量均為0,在500個(gè)單位時(shí)間處,Sink節(jié)點(diǎn)接收到的總數(shù)據(jù)量是不斷增多的,如表2中的第2行所示。特別地,當(dāng)δ值增加到0.8amax時(shí),穩(wěn)定狀態(tài)下的所有節(jié)點(diǎn)的感知數(shù)據(jù)存儲(chǔ)隊(duì)列平均值為0,即所有數(shù)據(jù)均被實(shí)時(shí)傳輸?shù)絊ink節(jié)點(diǎn)。當(dāng)然,其代價(jià)是相比于δ≤0.6amax時(shí)的情況,發(fā)送單位數(shù)據(jù)到達(dá)Sink節(jié)點(diǎn)的平均能耗增加了約0.001 μJ。

從上述分析可知,能耗、感知數(shù)據(jù)的丟棄量及傳輸時(shí)延之間存在一定的均衡關(guān)系。因此應(yīng)根據(jù)實(shí)際需求來(lái)確定參數(shù)V、δ及α的值。

表2 參數(shù)δ對(duì)Sink節(jié)點(diǎn)接收到的總數(shù)據(jù)量和能耗的影響

圖7 不同的數(shù)據(jù)感知速率對(duì)感知數(shù)據(jù)存儲(chǔ)隊(duì)列的影響

3.4 本文算法與AVE算法的比較

設(shè)置節(jié)點(diǎn)在單位時(shí)間內(nèi)的最小數(shù)據(jù)感知量是amin=0 bit,參數(shù)V=10、δ=0.6×amax及代價(jià)函數(shù)中的可調(diào)系數(shù)α=60,節(jié)點(diǎn)在單位時(shí)間內(nèi)的最大數(shù)據(jù)感知量amax從100 bit逐步增加到500 bit。由圖7和表3可知,①當(dāng)amax≤200 bit時(shí),穩(wěn)定狀態(tài)下的所有節(jié)點(diǎn)的感知數(shù)據(jù)存儲(chǔ)隊(duì)列平均值均為0,本文算法發(fā)送單位數(shù)據(jù)到達(dá)Sink節(jié)點(diǎn)的平均能耗略高于AVE算法;②當(dāng)300 bit≤amax≤400 bit時(shí),穩(wěn)定狀態(tài)下的所有節(jié)點(diǎn)的感知數(shù)據(jù)存儲(chǔ)隊(duì)列平均值在大部分時(shí)間為0,但會(huì)出現(xiàn)小波動(dòng),如圖7中的黑色小圓圈所示。這是由于隨著數(shù)據(jù)感知速量的增加,能耗小的路徑上的鏈路承受力趨于飽和,本文算法試圖等待在感知數(shù)據(jù)量較少的時(shí)間里再將數(shù)據(jù)沿著能耗小的路徑傳輸?shù)絊ink節(jié)點(diǎn),這正是本文算法的出發(fā)點(diǎn)之一,如第1部分所述。另外,本文算法發(fā)送單位數(shù)據(jù)到達(dá)Sink節(jié)點(diǎn)的平均能耗明顯高于AVE算法,尤其當(dāng)amax=400 bit時(shí),本文算法發(fā)送單位數(shù)據(jù)到達(dá)Sink節(jié)點(diǎn)的平均能耗增加了達(dá)0.052 μJ;③當(dāng)amax增加到500 bit時(shí),節(jié)點(diǎn)的感知量超出了WSNs鏈路容量,故AVE算法無(wú)法得到可行解,而本文算法通過(guò)等待和丟棄少量數(shù)據(jù)量等策略,使得Sink節(jié)點(diǎn)接收到了95.44%的感知數(shù)據(jù)。

表3 不同的最大數(shù)據(jù)感知速率下,發(fā)送單位數(shù)據(jù)

可見(jiàn),本文算法在節(jié)點(diǎn)感知數(shù)據(jù)量較低的情況下,能得到接近于AVE算法的路由結(jié)果,同時(shí)也能處理節(jié)點(diǎn)感知數(shù)據(jù)量較高使得AVE算法無(wú)法計(jì)算的情況。但當(dāng)節(jié)點(diǎn)感知數(shù)據(jù)量較為均衡時(shí),本文算法的性能欠佳。不過(guò)再次說(shuō)明,實(shí)際中節(jié)點(diǎn)的平均感知速率是很難得到的。

4 結(jié)語(yǔ)

本文考慮WSNs應(yīng)用中監(jiān)測(cè)環(huán)境具有隨機(jī)性和不可預(yù)測(cè)性等因素,研究時(shí)變感知速率下的路由問(wèn)題,提出了一種基于Lyapunov優(yōu)化技術(shù)的時(shí)變路由算法來(lái)實(shí)時(shí)決策每條鏈路上的數(shù)據(jù)流量以及由于節(jié)點(diǎn)感知速率持續(xù)超出鏈路容量而不得不丟棄的感知數(shù)據(jù)量。理論分析與仿真實(shí)驗(yàn)均表明通過(guò)選取合適的參數(shù)V、δ及α值,可在能耗、感知數(shù)據(jù)丟棄量及傳輸時(shí)延之間達(dá)到一定的均衡。本文算法還能處理節(jié)點(diǎn)感知速率較高使得AVE算法無(wú)法計(jì)算的情況。下一步將結(jié)合Sink節(jié)點(diǎn)移動(dòng)的方法,進(jìn)一步研究?jī)?yōu)化算法在能耗、感知數(shù)據(jù)的丟棄量及傳輸時(shí)延等方面的性能。

[1] 何杏宇,周亦敏,楊桂松,等. 無(wú)線(xiàn)傳感器網(wǎng)絡(luò)能量感知增強(qiáng)樹(shù)型路由協(xié)議研究[J]. 傳感技術(shù)學(xué)報(bào),2015(4):551-556.

[2] Madan R,Lall S. Distributed Algorithms for Maximum Lifetime Routing in Wireless Sensor Networks[C]//Proceedings of the IEEE Global Telecommunications Conference,2004:748-753.

[3] Hong Y,Xu J,Jiang C. Lifetime Maximization in Wireless Sensor Networks with Network Coding[C]//Proceedings of IEEE International Conference on Wireless Communications,Networking and Mobile Computing,Los Angeles:IEEE,2007:2527-2530.

[4] Cheng M,Gong X,Cai L. Joint Routing and Link Rate Allocation under Bandwidth and Energy Constraints in Sensor Networks[J]. IEEE Transactions on Wireless Communications,2009,8(7):3770-3779.

[5] 任條娟,楊海波,陳友榮. Sink 節(jié)點(diǎn)移動(dòng)的無(wú)線(xiàn)傳感網(wǎng)生存時(shí)間優(yōu)化算法[J]. 傳感技術(shù)學(xué)報(bào),2012,25(5):683-690.

[6] Yun Y S,Xia Y,Behdani B,et al. Distributed Algorithm for Lifetime Maximization in Delay-Tolerant Wireless Sensor Network with Mobile Sink[J]. IEEE Transactions on Mobile Computing,2012,12(10):370-375.

[7] Yun Y S,Xia Y. Maximizing the Lifetime of Wireless Sensor Networks with Mobile Sink in Delay-Tolerant Applications[J]. IEEE Transactions on Mobile Computing,2010,9(9):1308-1318.

[8] Wang Y,Tan H. Distributed Probabilistic Routing for Sensor Network Lifetime Optimization[J]. Wireless Networks,2016,22(3):975-989.

[9] Kumar V,Kumar S. Energy Balanced Position-Based Routing for Lifetime Maximization of Wireless Sensor Networks[J]. Ad Hoc Networks,2016,52:117-129.

[10] 薛亮,王燕龍,李志華,等. 無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中基于數(shù)據(jù)融合的時(shí)變速率路由算法[J]. 微電子學(xué)與計(jì)算機(jī),2015,32(12):130-135.

[11] Hou Y T,Shi Y Y. Variable Bit Rate Flow Routing in Wireless Sensor Networks[J]. IEEE Transactions on Wireless Communications,2007,6(6):2140-2148.

[12] Xue L,Yang B,Zhao J,et al. Joint Resource Reconfiguration and Robust Routing for Cognitive Radio Networks:A Robust Optimization Approach[J]. Wireless Communications and Mobile Computing,2015,15(5):848-867.

[13] Neely M J. Stochastic Network Optimization with Application to Communication and Queuing Systems[M]. Morgan & Claypool,2010.

[14] Yuanyuan Y,李亞寧. 無(wú)線(xiàn)可充電傳感器網(wǎng)絡(luò)[J]. 國(guó)外科技新書(shū)評(píng)介,2015(7):22-23.

[15] 胡誠(chéng),汪蕓,王輝. 無(wú)線(xiàn)可充電傳感器網(wǎng)絡(luò)中充電規(guī)劃研究進(jìn)展[J]. 軟件學(xué)報(bào),2016,27(1):72-95.

Variable Bit Rate Flow Routing in Wireless Sensor Networks Based on Lyapunov Optimization*

DONG Qifen*,ZHANG Qiqian

(Department of Computer and Information Technology,Zhejiang Police College,Hangzhou 310053,China)

Monitoring environment in the application of wireless sensor networks is always random and unpredictable,so the node sensing rate is usually time-varying and may exceed the link capacities at some time-slots. Pointing at this problem,a variable bit rate flow routing algorithm is designed in this paper. In the proposed algorithm,the routing problem with time variable sensing rate is described as a stochastic optimization model whose objective function is to minimize the weighted sum of time-average power consumption and the cost induced by discarding sensed data. The model is solved by Lyapunov optimization technique,and a routing method is proposed to determine the amount of data flowing through each link and to calculate the amount of data to be discarded when the node sensing rate continuously exceeds the link capacities in real time. Further,the condition under which the data will not be discarded is discussed and an explicit trade-off between the value of objective function and the worst-case delay of data transmission is obtained. Finally,simulation demonstrates the relationship among power consumption,the amount of discarded data and the data transmission delay. We also compare the performance of the proposed algorithm with AVE algorithm under different maximum node sensing rates.

wireless sensor networks;variable bit rate flow routing;lyapunov optimization

董齊芬(1985-),女,博士,講師,主要研究方向?yàn)闊o(wú)線(xiàn)傳感網(wǎng)、優(yōu)化算法,dongqifen@zjjcxy.cn;

張其前(1976-),男,博士,講師,主要研究方向?yàn)橛?jì)算機(jī)取證,控制理論、優(yōu)化理論等。

項(xiàng)目來(lái)源:NSFC-浙江兩化融合聯(lián)合基金項(xiàng)目(U1509219)

2016-11-03 修改日期:2016-12-29

TP393

A

1004-1699(2017)05-0758-08

C:7230

10.3969/j.issn.1004-1699.2017.05.021