高 潔,吳憲海,文瓊瑤

(1.西昌學(xué)院預(yù)科教育學(xué)院,四川 西昌 615000;2.63798部隊,四川 西昌 615000)

無線傳感器網(wǎng)絡(luò)多應(yīng)用在環(huán)境危險,面積空曠的野外作業(yè)。用電池供電的節(jié)點一旦部署組成網(wǎng)絡(luò)開始工作,將無法在部署環(huán)境中更換電池[1-2]。節(jié)點的主要作用是完成信息的傳輸,通過多跳傳輸方式最終將信息傳輸?shù)交?。大量研究表?節(jié)點無線通信模塊的能量消耗水平直接決定了節(jié)點的使用壽命[3-4]。大量學(xué)者致力于如何均衡整個網(wǎng)絡(luò)的能源消耗研究,優(yōu)化無線傳感器網(wǎng)絡(luò)結(jié)構(gòu),延長整個網(wǎng)絡(luò)的生命周期[2-3,5-6]。Jiang[5]基于構(gòu)造節(jié)點的最大獨立集提出冗余節(jié)點休眠的思想。利用最少數(shù)量的節(jié)點達到網(wǎng)絡(luò)的全覆蓋。作者提出利用構(gòu)造最小生成樹尋找節(jié)點最大獨立集的多項式時間近似算法。當(dāng)刪除最大獨立集中的節(jié)點后,網(wǎng)絡(luò)中剩余節(jié)點可以保證整個網(wǎng)絡(luò)的全覆蓋。Yang[6]將網(wǎng)絡(luò)中節(jié)點的剩余能量作為點的權(quán)值。利用改進的貪婪算法尋找最小加權(quán)獨立集。保證最小加權(quán)獨立集中的冗余節(jié)點首先休眠,而網(wǎng)絡(luò)中工作的節(jié)點剩余能量水平相對較高,并且滿足整個網(wǎng)絡(luò)的全覆蓋。在延長網(wǎng)絡(luò)生命周期的前提下,同時使得網(wǎng)絡(luò)中每個節(jié)點的能量消耗得到均衡。有向傳感器網(wǎng)絡(luò)由于在節(jié)點屬性上增設(shè)了有向?qū)傩远蛊鋼碛懈鼮閺V闊的實用意義。針對重點區(qū)域覆蓋不足的問題,Tan等提出了一種改進的非均勻有向傳感器網(wǎng)絡(luò)節(jié)點部署方法,引入部署中心和矢量引力的概念,增加斥力的非均勻部署屬性,從而加強區(qū)域內(nèi)的覆蓋質(zhì)量[7]。文獻[8]對網(wǎng)絡(luò)節(jié)點均衡性進行準(zhǔn)確合理的控制,可保障網(wǎng)絡(luò)在入侵后還能保持良好的運行狀態(tài)。利用局部最小生成樹理論控制網(wǎng)絡(luò)結(jié)構(gòu),將選擇鏈路節(jié)點的權(quán)值視為新的加權(quán)函數(shù),在組建網(wǎng)絡(luò)拓撲模型時考慮了節(jié)點間的通信消耗和節(jié)點剩余能量,依據(jù)節(jié)點能量的變化對網(wǎng)絡(luò)拓撲結(jié)構(gòu)進行動態(tài)調(diào)節(jié),利用通信損耗鏈路作為衡量標(biāo)準(zhǔn),同時考慮中繼節(jié)點的剩余能量情況,避免了網(wǎng)絡(luò)入侵后部分節(jié)點能量過早耗盡。Tian等[9]提出了自發(fā)的檢測節(jié)點休眠算法。當(dāng)節(jié)點的探測范圍可以由其鄰居節(jié)點的探測范圍所覆蓋,這個節(jié)點可以認為是冗余的,就自動進入休眠狀態(tài)。在一個時間周期內(nèi),節(jié)點自發(fā)的醒來檢測是否有鄰居節(jié)點覆蓋其探測區(qū)域,從而決定是否休眠。但是這種算法中,鄰居節(jié)點由于自發(fā)地醒來檢測導(dǎo)致能量的浪費。針對無線傳感器網(wǎng)絡(luò)節(jié)點覆蓋不均勻?qū)е赂采w率低下的問題,Wu[10]提出了一種基于改進自適應(yīng)粒子群優(yōu)化算法的覆蓋優(yōu)化方法。建立WSN 覆蓋優(yōu)化的數(shù)學(xué)模型;然后將進化因子和聚合因子引入粒子群優(yōu)化(PSO)算法中的慣性權(quán)重系數(shù),接著在算法迭代過程中引入碰撞回彈策略保證粒子群的多樣性,克服改進粒子群優(yōu)化算法在優(yōu)化后期容易陷入局部最優(yōu)的弱點。文獻[11]提出了一種工作量加權(quán)路由模型以提高無線自組織網(wǎng)絡(luò)的生存時間。在網(wǎng)絡(luò)信息傳輸?shù)倪^程中,綜合每條鏈路的業(yè)務(wù)工作量對網(wǎng)絡(luò)鏈路進行加權(quán),建立最小代價傳輸數(shù)學(xué)模型。該模型通過降低工作較為繁忙節(jié)點的信息轉(zhuǎn)發(fā)概率,從而到達均衡節(jié)點能耗、延長網(wǎng)絡(luò)生存時間的目的。文獻[12]引入覆蓋率均衡思想,將各傳感器節(jié)點對目標(biāo)區(qū)域覆蓋率的均衡性與節(jié)點剩余能量的均衡性作為篩選因子,且通過調(diào)節(jié)傳感器節(jié)點的剩余能量與其平均覆蓋率的比例關(guān)系,篩選出最大不相關(guān)且代價最小的網(wǎng)絡(luò)覆蓋子集,以盡可能少的節(jié)點實現(xiàn)對區(qū)域的覆蓋。文獻[13]針對多冗余通路設(shè)計的無線傳感器網(wǎng)絡(luò)故障預(yù)防方法存在工作狀態(tài)冗余節(jié)點過多、能量大量浪費的問題,提出一種基于節(jié)點健康度的冗余通路控制方法。該方法利用匯聚節(jié)點收集網(wǎng)絡(luò)內(nèi)所有節(jié)點能量狀態(tài),計算節(jié)點健康度等相關(guān)參數(shù),使用A-Star算法選擇最優(yōu)工作通路,控制其余冗余通路分批輪流休眠,從而達到減少和均衡網(wǎng)絡(luò)工作過程能量消耗、預(yù)防某些節(jié)點能量提前耗盡導(dǎo)致網(wǎng)絡(luò)能量故障發(fā)生的目的。文獻[14]提出位于基站周圍的節(jié)點由于負責(zé)所有探測數(shù)據(jù)的轉(zhuǎn)發(fā)任務(wù)而能量消耗水平較高。為了均衡基站周圍節(jié)點的能量消耗,提出一種合理有效的節(jié)點輪換休眠機制。使得網(wǎng)絡(luò)中大量冗余節(jié)點處于休眠狀態(tài),從而減少基站周圍重要節(jié)點的負載。

1 網(wǎng)絡(luò)能量優(yōu)化策略研究

考慮網(wǎng)絡(luò)中存在高密度的靜態(tài)傳感器節(jié)點集V={vi|i=1,2,…,N}和唯一的基站BS。位于基站周圍且直接與基站通信的節(jié)點由于向基站轉(zhuǎn)發(fā)全部數(shù)據(jù)的任務(wù),能量消耗比其他節(jié)點快,這樣的節(jié)點被稱作瓶頸節(jié)點。本文中采取M. Bhardwaj[15]對網(wǎng)絡(luò)生命周期的定義,認為網(wǎng)絡(luò)的生命周期為網(wǎng)絡(luò)中出現(xiàn)第1個覆蓋漏洞的時間。

為了便于研究并簡化模型,提出以下假設(shè):①節(jié)點以密度為ρ的泊松分布隨機布撒在一個圓心為O半徑為R的圓形網(wǎng)絡(luò)區(qū)域G中,基站位于圓心O上。②傳感器節(jié)點的最大通信半徑為Rc,最大探測半徑為Rs,且有Rc,Rs?R。那么,節(jié)點vi的探測范圍可表示為Pi={p∈R2|d(p,vi)≤Rs},其中d(p,vi)表示點p到vi的歐氏距離。③節(jié)點可以通過一定的方法(如GPS全球定位系統(tǒng))知曉基站及自身地理位置。

網(wǎng)絡(luò)中的數(shù)據(jù)流均來自于區(qū)域S1和S2并必須經(jīng)過S2才能傳輸?shù)交?。因?瓶頸節(jié)點大多位于中心,如圖1所示。為了平衡整個網(wǎng)絡(luò)的能量消耗,關(guān)鍵是平衡瓶頸節(jié)點的能量消耗。

R=10,r=1,ρ=4/π,λ=1,ε=1,p=0.5圖1 位于基站周圍節(jié)點的能量消耗

假設(shè)S1區(qū)域的節(jié)點均采取多跳傳輸?shù)姆绞?。由于S2區(qū)域中的同時存在多跳傳輸節(jié)點和一跳傳輸?shù)墓?jié)點,為了清楚地計算區(qū)域S2中采用一跳傳輸方式的節(jié)點的數(shù)量和其他多跳傳輸?shù)墓?jié)點數(shù)量,本文定義網(wǎng)絡(luò)中的直接傳輸概率p(0

接下來,將對節(jié)點的平均能量消耗進行數(shù)學(xué)描述,首先提出以下假設(shè):

ε(D):位于距離基站D的節(jié)點將每單位數(shù)據(jù)傳遞到基站所需的能量。

λ:節(jié)點向基站發(fā)射信號的頻率。在本文中,認為節(jié)點發(fā)射數(shù)據(jù)的頻率為常數(shù)。

由于越靠近基站的節(jié)點將承擔(dān)更多的轉(zhuǎn)發(fā)任務(wù),其能量消耗越快。對于S2中的瓶頸節(jié)點,取距離基站最遠的瓶頸節(jié)點的距離計算節(jié)點平均能量消耗才能得到S2中可休眠的冗余節(jié)點的下界。

在Luo J[16]幾何模型的基礎(chǔ)上,節(jié)點ni的平均能量消耗與區(qū)域S1和S2的面積有關(guān),如圖2所示,S1和S2的面積可表示為:

(1)

S1=π[R2-r(D)2]

S2=πr(D)2D

(2)

所以,S2區(qū)域中的節(jié)點在一段時間內(nèi)的平均能量消耗可以表達為:

(3)

式中:β(D)=2arcsin(r/D)。在本文中,假設(shè)網(wǎng)絡(luò)中所有節(jié)點的通信半徑都相同Rc=r。

D表示節(jié)點n到圓心O的距離,r為探測半徑圖2 網(wǎng)絡(luò)模型

從圖1中所示,位于基站周圍的瓶頸節(jié)點大量死亡后,通過瓶頸節(jié)點傳輸?shù)臄?shù)據(jù)將無法傳遞到基站,將使網(wǎng)絡(luò)中出現(xiàn)覆蓋空洞。因此瓶頸節(jié)點的使用壽命直接影響整個網(wǎng)絡(luò)的生命周期。如圖3所示,由于網(wǎng)絡(luò)中的節(jié)點密度高,多個節(jié)點同時探測到相同的數(shù)據(jù)信息并以頻率λ傳輸給S2區(qū)域內(nèi)中的瓶頸節(jié)點,這些節(jié)點休眠后并不影響網(wǎng)絡(luò)的連通性。大量冗余節(jié)點加重S2區(qū)域中瓶頸節(jié)點的負載,不利于網(wǎng)絡(luò)的生存。

圖3 瓶頸節(jié)點數(shù)據(jù)轉(zhuǎn)發(fā)模型

最優(yōu)的能量均衡模式是在網(wǎng)絡(luò)運行狀態(tài)下,目標(biāo)區(qū)域的任意位置當(dāng)且僅當(dāng)被一個節(jié)點的探測區(qū)域覆蓋。網(wǎng)絡(luò)中大部分節(jié)點相繼失效時,網(wǎng)絡(luò)中同時出現(xiàn)大面積的覆蓋空洞,網(wǎng)絡(luò)壽命宣告結(jié)束。而在實際情況下,總是存在部分節(jié)點由于能量消耗水平高而先行死亡,網(wǎng)絡(luò)中同一區(qū)域被多個節(jié)點的探測范圍同時覆蓋。

那么,如果可以尋找到網(wǎng)絡(luò)中最大數(shù)量的冗余節(jié)點并使其休眠,將極大的降低瓶頸節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)的負載,進而降低其能量消耗。同時整個網(wǎng)絡(luò)的能量達到最大程度的均衡。

因此,基于式(3),將可休眠的冗余節(jié)點數(shù)量作為變量,建立本文研究的優(yōu)化模型,通過優(yōu)化算法即可找到可休眠的節(jié)點集。

為了可以尋找到休眠節(jié)點集,將位于S2區(qū)域中的節(jié)點進行編號,Vneck={ni}(i=1,…,n)。

Dni=d(ni,BS):表示節(jié)點ni與基站之間的距離。

xni={0,1}:節(jié)點ni的狀態(tài)變量。xni=1表示ni處于休眠狀態(tài);xni=0表示ni此時處于喚醒狀態(tài)。

fni(x):表示距離基站Dni的節(jié)點ni的平均能量消耗。

Etotal(ni):節(jié)點的工作初始的總能量。

Eremnant(ni):持續(xù)工作t時間后,節(jié)點的剩余能量。

位于S2區(qū)域中的瓶頸節(jié)點的實際平均能量消耗可以表示為:

(4)

除了考慮均衡整個網(wǎng)絡(luò)的能量消耗,在本文中還考慮延長單一節(jié)點的使用壽命。所以在尋找可休眠的冗余節(jié)點時,選擇剩余能量較少的節(jié)點首先休眠,可以有效地延長單個節(jié)點的使用壽命。

令ω=(ω1,ω2,…,ωn)T為節(jié)點剩余能量權(quán)值。在初始狀態(tài)時ω=(ω1,ω2,…,ωn)T=(1,1,…,1)T。

對于節(jié)點ni的剩余能量權(quán)值wi可以表示為:

建立同時優(yōu)化整個網(wǎng)絡(luò)壽命和單一節(jié)點壽命的多目標(biāo)優(yōu)化模型為:

(5)

s.t.

Coverage(G)≥C

(6)

xj={0,1}

(7)

xj≠N(xj)

(8)

j∈S1

(9)

式中:x(Dni)=(x1,x2,…,xn)T表示節(jié)點狀態(tài)的0-1矩陣,winf為所有節(jié)點剩余能量指標(biāo)的最小值。

式(6)表示網(wǎng)絡(luò)的覆蓋集coverage(G)滿足不小于決策者所需的最小覆蓋常數(shù)指標(biāo)C(0

研究多目標(biāo)優(yōu)化問題的一個基本途徑是將多目標(biāo)優(yōu)化問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題,利用已成熟的單目標(biāo)優(yōu)化問題求解方法解決問題。這種處理方法稱為多目標(biāo)規(guī)劃問題的標(biāo)量化處理[17]。

引入權(quán)向量α=(α1,α2)T,且滿足α1,α2≥0,α1+α2=1。記極小化問題為:

定理1[14]設(shè)X?Rn,f:X→Rn,α=(α1,α2)T是常數(shù)向量。

式中:E(f,X)為全體Pareto有效點構(gòu)成的集合,Ew(f,X)為全體Pareto弱有效點構(gòu)成的集合。

②與①證明過程類似。

由定理1可知,求解極小化問題(Pw)和原問題是等價的。

首先,將優(yōu)化問題(5)進行標(biāo)量化處理,對多目標(biāo)優(yōu)化問題(5)進行線性加權(quán)。

模型中將網(wǎng)絡(luò)的平均能量消耗和單一節(jié)點壽命作為優(yōu)化目標(biāo)。在問題中,希望降低網(wǎng)絡(luò)的平均能量,也需要降低單一節(jié)點的壽命。在優(yōu)化問題中,自然可以認為兩個目標(biāo)的重要度相同。由于可以認為多目標(biāo)規(guī)劃問題的兩個方面權(quán)重是相同的,設(shè)α=(α1,α2)T=(0.5,0.5)T。

(10)

(11)

(12)

s.t. (winf-w)Txnj≤ε

(13)

Coverage(G)≥πR2

(14)

xnj∈{0,1}

(15)

nj∈S1

(16)

2 節(jié)點輪換休眠能量優(yōu)化策略算法

提出的能量優(yōu)化策略算法用以求解以上NP-難問題,使得大量可休眠節(jié)點進入休眠狀態(tài),也就是求解以上優(yōu)化模型的方法,如圖4所示。

圖4 冗余節(jié)點休眠的能量優(yōu)化策略算法流程圖

3 算法復(fù)雜度分析

定理2算法的復(fù)雜度為O(nk)。

證明標(biāo)記節(jié)點和剩余能量的復(fù)雜度是多項式的O(n),判別節(jié)點度的復(fù)雜度是O(n),在最小節(jié)點度的節(jié)點集中判別能量為最小的復(fù)雜度為O(n),即找到最小節(jié)點度最小能量的節(jié)點復(fù)雜度為O(n3)。重復(fù)調(diào)用算法復(fù)雜度為O(nk)。

值得說明的是,當(dāng)節(jié)點密度越大時,算法收斂的速度反而越快。也就是說k值是可控的。算法依然可以在多項式時間內(nèi)完成。

4 仿真分析

為了試驗?zāi)Ｐ蛻?yīng)用節(jié)點輪換策略是否對于網(wǎng)絡(luò)延長生命周期起到一定的作用,本文采用MATLAB 7.0作為仿真工具,運行環(huán)境為內(nèi)存512 Mbyte,操作系統(tǒng)為win7的PC機。

仿真試驗1 設(shè)置節(jié)點的探測半徑為1,節(jié)點數(shù)為n=1 225個,網(wǎng)絡(luò)區(qū)域為半徑R=50的圓形區(qū)域。

表1中,選取位于節(jié)點不同位置的節(jié)點,對應(yīng)的可休眠冗余節(jié)點數(shù)量不同。而且遵循以下規(guī)律:隨著節(jié)點與基站的距離D越大,其對應(yīng)的冗余節(jié)點的數(shù)量會越少。瓶頸節(jié)點位于基站周圍,距離基站較近的可休眠的冗余節(jié)點的數(shù)量較多,當(dāng)這些冗余節(jié)點休眠后,瓶頸節(jié)點的負載明顯減少。當(dāng)整個網(wǎng)絡(luò)的可休眠節(jié)點周期性的處于休眠狀態(tài),網(wǎng)絡(luò)的生命周期將會明顯延長。

表1 距離基站不同距離節(jié)點對應(yīng)可休眠冗余節(jié)點個數(shù)

仿真試驗2 設(shè)置節(jié)點探測半徑為1,節(jié)點與基站的距離越遠,節(jié)點的能量節(jié)約率越高,因為節(jié)點與基站距離越近,雖然大量節(jié)點休眠,但喚醒的次數(shù)也增加,而距離基站較遠的節(jié)點,休眠的節(jié)點數(shù)量較少,休眠后喚醒次數(shù)降低,能量節(jié)約較多。但距離基站較近的節(jié)點也有20%以上的能量得到節(jié)約。

圖5 相同探測半徑節(jié)點對應(yīng)可休眠節(jié)點數(shù)與能量節(jié)約率

仿真實驗3 如圖6所示,運行節(jié)點休眠策略前后的網(wǎng)絡(luò)平均能量消耗情況比較。虛線條表示網(wǎng)絡(luò)中原本節(jié)點的能量消耗情況。實線條表示網(wǎng)絡(luò)中節(jié)點休眠后的平均能量消耗情況。那么,網(wǎng)絡(luò)的平均能量消耗明顯降低。

圖6 節(jié)點能量消耗比較

仿真實驗4 對瓶頸節(jié)點的能量進行衡量,從圖7可以發(fā)現(xiàn),瓶頸節(jié)點的能量在網(wǎng)絡(luò)相同運行時間,有節(jié)點休眠策略的網(wǎng)絡(luò)瓶頸節(jié)點的能量消耗更慢。

圖7 兩種情況下瓶頸節(jié)點能量變化圖

4 結(jié)束語

為了確保網(wǎng)絡(luò)具有更長的工作時間,本文同時考慮到單一節(jié)點的工作時間和整個網(wǎng)絡(luò)的生命周期,提出了多目標(biāo)決策網(wǎng)絡(luò)優(yōu)化模型,并將其單一目標(biāo)化。設(shè)計了一種最小能量節(jié)點輪換休眠策略,解決了多目標(biāo)決策網(wǎng)絡(luò)優(yōu)化的NP難問題,算法復(fù)雜度為多項式的,可以有效的延長網(wǎng)絡(luò)的生存時間和單一節(jié)點的壽命,通過試驗表明,本文算法可以使WSN的能量節(jié)約20%以上,距離基站更近的節(jié)點,大量的冗余節(jié)點通過算法輪換休眠,大大降低了瓶頸節(jié)點的通信次數(shù),使其能量消耗更加均衡。因此,本文設(shè)計的算法在一定程度砂鍋內(nèi)有效的提高了整個網(wǎng)絡(luò)的性能。

[1] Geoffrey Werner Allen,Jeff Johnson. Monitoring Volcanic with a Wireless Sensor Network[C]//Proceeedings of the Second European Workshop on. 2005,1:108-120.

[2] Ma C,Liu H W,Zuo D C,et al. Tsinghua Univ. In Chinese,2011,51:1418.

[3] Akyildiz I F,Su W,Sanakamaniam Y,et al. Wireless Sensor Networks:A Survey[J]. IEEE Computer Networks,2002,40(4):102-114.

[4] Hill J,Szewczyk R,Woo A,et al. System Architecture Directions for Networked Sensors[C]//International Conforence on Architectural Support for Programming Languages and Operating Systems. USA. 2000,9:93-104.

[5] 蔣杰,方力,張鶴穎,等. 無線傳感器網(wǎng)絡(luò)最小連通覆蓋集問題求解算法[J]. 軟件學(xué)報,2006,17(2):175-184.

[6] 陽娣蘭,謝政,陳摯,等. 無線傳感器網(wǎng)絡(luò)中能耗均衡的覆蓋控制算法[J]. 計算機工程與科學(xué),2008,30(12):15-18.

[7] 譚勵,楊朝玉,楊明華,等. 改進的非均勻有向傳感器網(wǎng)絡(luò)節(jié)點部署方法[J]. 傳感技術(shù)學(xué)報,2015,25(12):1835-1840.

[8] 徐力,車念. 網(wǎng)絡(luò)節(jié)點均衡性優(yōu)化控制模型仿真研究[J]. 計算機仿真,2017,34(4):271-275.

[9] Di T,Georganas N D. A Node Scheduling Scheme for Energy Conservation in Large Wireless Sensor Networks[J]. Wireless Communications and Mobile Computing,2003,3(2):271-290.

[10] 吳意樂,何慶,徐同偉. 改進自適應(yīng)粒子群算法在WSN覆蓋優(yōu)化中的應(yīng)用[J]. 傳感技術(shù)學(xué)報,2016,29(4):559-565.

[11] 劉半藤,周瑩,陳友榮. 基于加權(quán)路由思想的無線自組織網(wǎng)絡(luò)生存時間優(yōu)化算法研究[J]. 傳感技術(shù)學(xué)報,2017,30(3):463-466.

[12] 秦寧寧,陳家樂,丁志國. 覆蓋率均衡區(qū)域覆蓋算法[J]. 傳感技術(shù)學(xué)報,2015,28(4):578-584.

[13] 宋佳,羅清華,彭喜元. 基于節(jié)點健康度的無線傳感器網(wǎng)絡(luò)冗余通路控制方法[J]. 物理學(xué)報,2014,12(63):(128401)1-11.

[14] 高潔,吳延紅,白建俠,等. 無線傳感器網(wǎng)絡(luò)最小覆蓋能量優(yōu)化算法[J]. 傳感技術(shù)學(xué)報,2016,29(9):1435-1440.

[15] Bhardwaj M,Chandrakasan A P. Bounding the Lifetime of Sensor Networks via OPTIMAL ROLE ASSIGNments[C]//Proc of the 21st IEEE INFOCOM. 2002,3(3):1587-1596.

[16] Luo J,Hubaux J P. Joint Mobility and Routing for Lifetime Elongation in Wireless Sensor Networks[C]//Proceedings of IEEE INFOCOM,2005,3:1735-1746.

[17] 徐玖平,胡志能,中級運籌學(xué)[M]. 北京,科學(xué)出版社,2008.