顧云麗,徐 昕,張嫣娟

(1.南京信息工程大學(xué)江蘇省網(wǎng)絡(luò)監(jiān)控中心,南京 210044;2.南京信息工程大學(xué)計算機與軟件學(xué)院,南京 210044)

無線傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Networks)常用于軍事、海洋、氣象環(huán)境、森林火警監(jiān)測,其網(wǎng)絡(luò)范圍往往大于一般無線網(wǎng)絡(luò)。由于網(wǎng)絡(luò)規(guī)模較大,為改善性能(如網(wǎng)絡(luò)生存期和流量分布等),需在WSN中部署多個基站,并采用多源多基站任播模式MMAP(Multi-source Multi-Sink Anycast Pattern)。即從傳感器節(jié)點產(chǎn)生的監(jiān)測數(shù)據(jù)分組可以傳輸給任一基站。

任播(anycast)是IPv6中定義的一種新型通信服務(wù),其服務(wù)是將數(shù)據(jù)分組傳送到具有任播地址標(biāo)識的任意一個或多個接口處。傳統(tǒng)任播路由協(xié)議是將數(shù)據(jù)分組發(fā)送至最優(yōu)基站。而在WSN中,有學(xué)者采用的是基于路由權(quán)重隨機選擇策略[1]WRS(Weighted Random Selection)的任播路由技術(shù),即監(jiān)控節(jié)點根據(jù)至各基站的任播路徑的路由權(quán)重,將監(jiān)控數(shù)據(jù)分組分散傳輸?shù)礁鱾€基站處。該策略可以緩解單條路徑承載過多傳輸任務(wù),導(dǎo)致部分節(jié)點過早耗盡能量的問題。

任播路由領(lǐng)域相對比較新穎,關(guān)于WSN任播路由協(xié)議的重要研究成果目前還不是太多,主要如下:Lenders[2]等人根據(jù)勢場理論提出一種基于密度的無線網(wǎng)絡(luò)任播路由協(xié)議;Flury[3]等學(xué)者證明在WSN中指定任播組和源節(jié)點所生成的信息樹中尋找最小傳輸總能耗是一個NP完全問題,作者在文中給出一個分布式的近似算法來解決該難題;Ashraf[4]提出Any-MAC協(xié)議,通過改善路由級冗余,減少傳輸延遲;Kim等[5]學(xué)者將睡眠-喚醒機制引入MAC任播路由;Hadi等[6]學(xué)者研究編碼轉(zhuǎn)發(fā)策略和固定比率合并機制,設(shè)計了一個最小能量路由協(xié)議的聯(lián)合優(yōu)化算法;Kostin等[7]學(xué)者研究移動傳感器和移動多Sink路由方案,方案基于擴展環(huán)搜索、傳感器節(jié)點維護反應(yīng)模式和路由狀態(tài)信息等算法思想;Gao[8]等學(xué)者為解決森林環(huán)境監(jiān)測數(shù)據(jù)分組的傳輸延遲問題,提出一種可充電WSN的任播路由協(xié)議,其算法主要思想是通過禁忌搜索算法建立至每一個基站的端到端時延最小的任播路徑;Yerra[9]搭建三維馬爾可夫模型,從而能夠更準(zhǔn)確地觀察中繼節(jié)點的傳輸效率、傳輸時延等關(guān)鍵性能指標(biāo);劉文博[10]將任播路由應(yīng)用于水下傳感網(wǎng)絡(luò)。也有學(xué)者將k-任播應(yīng)用到WSN中以達到均衡能耗提高網(wǎng)絡(luò)生存期的目的。Wang[11]提出一種分布式地理WSN的k-任播路由協(xié)議(GKAR);Gao[12]借用WSN的廣播特點以節(jié)省傳輸能耗(即k條路徑盡量共用相同鏈路的算法思想)。

以往學(xué)者往往將網(wǎng)絡(luò)生存期作為路由選擇的重要判據(jù),但卻較少有學(xué)者將路由健壯性也作為路由選擇的參考因素之一。在WSN中,無線鏈路經(jīng)常臨時性失效,監(jiān)測數(shù)據(jù)分組有可能不能正常到達目的地,從而導(dǎo)致能耗(重傳能耗)和端對端時延增加,這使得以往有些學(xué)者所提出的路由算法的實際性能可能達不到其所述性能指標(biāo)。因此,本文將路由健壯性及網(wǎng)絡(luò)生存期兩方面因素都作為路由判據(jù),并實驗分析該算法的性能。

1 網(wǎng)絡(luò)模型及問題描述

本文,WSN抽象視為連通圖G(V,E)。其中,V為傳感器節(jié)點集合,E為節(jié)點間通信鏈路集合。本文標(biāo)記:A為任播地址;G(A)為共享A的任播通信組成員集合(即基站集合),G(A)?V;N為集合V的節(jié)點數(shù)目;M為集合G(A)組員數(shù)目,T為集合E的鏈路數(shù)目。

WSN往往用來監(jiān)控其覆蓋范圍內(nèi)若干指定目標(biāo),該目標(biāo)附近節(jié)點往往需定期匯報監(jiān)測數(shù)據(jù)至任一基站。這些發(fā)送節(jié)點集合標(biāo)記為S,L為S中節(jié)點數(shù)目。

由于WSN節(jié)點能量受限且往往難于更換電池,一旦有節(jié)點耗盡能量,可能會導(dǎo)致網(wǎng)絡(luò)分割,即某些區(qū)域無節(jié)點負(fù)責(zé)監(jiān)測和轉(zhuǎn)發(fā)分組,從而被認(rèn)定為網(wǎng)絡(luò)失效。本文定義網(wǎng)絡(luò)生存期為第1個節(jié)點耗盡能量。因此,我們設(shè)計的路由算法不僅要節(jié)能,還要保證各節(jié)點能耗要均衡,從而最大化網(wǎng)絡(luò)生存期。所以,發(fā)送節(jié)點將監(jiān)測數(shù)據(jù)分組不能僅發(fā)送至最優(yōu)基站,還需根據(jù)各個基站的路由權(quán)重,將數(shù)據(jù)隨機發(fā)送給相應(yīng)基站(WRS策略[1])。設(shè)發(fā)送節(jié)點s∈S至M個基站(G(A))都有一條任播路徑,即節(jié)點s共有M條任播路徑,表示如下:

Ps={Ps1,Ps2,…,PsM}

(1)

Ps中的M條任播路徑路由權(quán)重Ws表示為{ws1,ws2,…,wsM}。S中各發(fā)送節(jié)點的任播路徑集合P表示如下:

P={P1,P2,…,PL}

(2)

P的路由權(quán)重集合W表示如下:

W={W1,W2,…,WN}

(3)

設(shè)節(jié)點s∈S為某一源節(jié)點,單位時間需匯報至基站的次數(shù)是ns;每次匯報至基站的數(shù)據(jù)分組大小為us。由于采用WRS策略,即s根據(jù)路由權(quán)重從M條至各基站的任播路徑中隨機選擇一條作為傳輸路徑。設(shè)任播路徑Psj∈P,Psj是指源節(jié)點s至基站j的路徑,路徑權(quán)重設(shè)為wsj,則路徑Psj單位時間將為源節(jié)點s承擔(dān)wsjnsus大小的數(shù)據(jù)傳輸任務(wù)。設(shè)節(jié)點傳輸速率為τ,wsjnsus大小的數(shù)據(jù)所需傳輸時間tv為wsjnsus/τ(不考慮分組在節(jié)點內(nèi)排隊等待時間等)。

節(jié)點的狀態(tài)可分為正在發(fā)送分組,或正在接收分組(包括串聽),或空閑等待狀態(tài)。設(shè)節(jié)點v∈Psj,則節(jié)點v需為任播路徑Psj發(fā)送數(shù)據(jù)量為Nsuswsj。節(jié)點v還可能屬于同一源節(jié)點其他任播路徑,或者其他發(fā)送節(jié)點為源節(jié)點的任播路徑,因此節(jié)點v單位時間發(fā)送數(shù)據(jù)量Dv計算如下:

(4)

因此,節(jié)點v單位時間內(nèi)處于發(fā)送狀態(tài)的時間tvs為:

tvs=Dv/τ

(5)

由此可得,節(jié)點v單位時間能耗Ev為:

Ev=tvsEdelivery+(1-tvs)Eidle

(6)

式中:Edelivery為節(jié)點處于傳輸狀態(tài)時單位時間能耗;Eidle為節(jié)點處于空閑等待或接收狀態(tài)時單位時間能耗。接收能耗與空閑等待能耗往往相差不大,本文簡化為視為相同。

學(xué)者在設(shè)計WSN路由算法時往往以網(wǎng)絡(luò)生存期最大化為優(yōu)化目標(biāo)。如圖1中,S1和S2為發(fā)送節(jié)點,各需匯報u大小數(shù)據(jù)分組至基站;A1、A2和A3為基站。S1的任播路徑集合P1=(P11P12)。P11=S1-n1-A1;P12=S1-n2-n3-A2。S2的任播路徑集合P2=(P23P21)。P23=S2-n4-n5-A3;P21=S2-n1-A1。由圖1可以看出,S1的P12與S2的P23是無交叉路徑,而P11和P21是最短路徑。但為最大化網(wǎng)絡(luò)生存期,發(fā)送節(jié)點不能只采用一條任播路徑(最短路徑或無交叉路徑)。而是根據(jù)WRS策略,將數(shù)據(jù)流分散到各條任播路徑上。圖1中,為最大化網(wǎng)絡(luò)生存期,顯然應(yīng)設(shè)置P1路由權(quán)重W1={w11w12}={0.666 0.333};而P2的W2=(w23w21)=(0.666 0.333)。即S1將0.666u分組通過路徑P12匯報至A2,將0.333u分組通過路徑P11匯報至A1,S2也依此處理。

圖1 網(wǎng)絡(luò)示意圖

但WSN還會因環(huán)境等因素常常出現(xiàn)無線鏈路臨時性失效現(xiàn)象。失效會導(dǎo)致節(jié)點有額外的重傳能耗,路徑有額外的重傳時延。因此,這些學(xué)者所提出的路由算法的實際傳輸時延和傳輸能耗可能達不到其設(shè)計性能(后文將以圖1數(shù)據(jù)說明)。

設(shè)fi為鏈路ei出現(xiàn)故障的概率,本文設(shè)定鏈路的故障彼此之間是完全獨立的事件。本文還設(shè)定,中間節(jié)點不保存其轉(zhuǎn)發(fā)的數(shù)據(jù)分組,即若傳輸任務(wù)失敗需路徑源節(jié)點重新發(fā)送丟失的分組。

設(shè)路徑Psj∈P,Psj單位時間內(nèi)路徑出現(xiàn)故障的概率rsj計算如下:

(7)

(8)

(9)

由此,我們可得,節(jié)點v的單位時間實際能耗如下:

(10)

節(jié)點v壽命Lv計算如下:

(11)

式中:Einit是節(jié)點的初始能量。

由于鏈路e∈E,可能在P中多條任播路徑中出現(xiàn),即,鏈路e的失效會造成P中多條任播路徑數(shù)據(jù)分組的丟失,計算如下:

(12)

經(jīng)過簡化,Fe為:

(13)

可得,使用鏈路e∈E,導(dǎo)致任播路徑數(shù)據(jù)分組丟失率如下:

(14)

我們設(shè)計的任播路由算法,其算法設(shè)計目標(biāo)之一是最大化網(wǎng)絡(luò)生存期。即

(15)

式中:式中變量是P和W,即任播路徑集合及其路由權(quán)重向量。

(16)

該優(yōu)化問題記為

(17)

分組丟失會導(dǎo)致節(jié)點傳輸能耗增加,從而影響網(wǎng)絡(luò)生存期。如圖1,若忽略數(shù)據(jù)分組丟失問題,如前文所述,為最大化網(wǎng)絡(luò)生存期,P1路由權(quán)重W1={w11w12}={0.666 0.333};而P2的W2={w23w21}={0.666 0.333}。 但實際由于重傳能耗問題的引入(設(shè)各鏈路故障概率為0.1),根據(jù)式(15)可得:W1=W2={0.643 0.357}。分析如下:由式(12),可知S1-A2路徑的數(shù)據(jù)丟失率為0.271,0.643u的數(shù)據(jù)分組在S1-A2路徑實際上需要傳遞0.882u;同理,可得S2-A3路徑,S1加上S2至A1路徑的實際數(shù)據(jù)流為0.882u,即各任播路徑上各節(jié)點能耗均衡(相等),網(wǎng)絡(luò)生存期最大。由此可知,忽略對路由健壯性問題的討論,導(dǎo)致有些學(xué)者所提出的路由算法的網(wǎng)絡(luò)生存期性能可能達不到其所述性能指標(biāo)。

上文只是描述鏈路失效造成的重傳能耗后果,除此以外,還會造成傳遞時延額外增加、節(jié)點計算和路由資源浪費等。因此,我們所設(shè)計的任播路由算法也要盡可能減少鏈路的數(shù)據(jù)分組丟失概率。該優(yōu)化問題描述如下:

(18)

為方便討論,式(17)記為:

(19)

3 多目標(biāo)進化算法優(yōu)化

由上文可知,我們的優(yōu)化目標(biāo)不僅是網(wǎng)絡(luò)生存期,還要包括路由健壯性。即我們優(yōu)化的目標(biāo)如下:

(20)

(21)

顯然,這兩個目標(biāo)往往存在沖突,常常無法同時取得最優(yōu)值。設(shè)圖1中鏈路S1-n1和S2-n1的故障率為0.1,而其余鏈路故障率為0,顯然S1(S2)將其所有監(jiān)測數(shù)分組傳送至A2(A3),此時鏈路故障率最低。但為了最大化網(wǎng)絡(luò)生存期,S1(S2)還需將部分?jǐn)?shù)據(jù)分組傳送至A1。該多目標(biāo)優(yōu)化問題是一個NP完全問題[5],即該問題無法給出一個有限多項式解。對于這種多目標(biāo)路由優(yōu)化問題,以往學(xué)者有采用多目標(biāo)進化算法解決類似問題[13-14],因此本文采用多目標(biāo)進化算法解決該問題。

如前文所述,單個節(jié)點的能耗計算和單條鏈路導(dǎo)致任播路徑分組丟失率的計算的算法復(fù)雜度分別為O(N)和O(N3/2),對節(jié)點的計算能力要求不是太高。但是式(20)和式(21)的多目標(biāo)優(yōu)化問題是NP完全問題,為了節(jié)省節(jié)點能耗、降低對節(jié)點計算能力的要求,本文將優(yōu)化計算問題遷移到基站。即網(wǎng)絡(luò)初始化時,由基站完成優(yōu)化計算并返回結(jié)果給各節(jié)點。當(dāng)有拓?fù)浣Y(jié)構(gòu)等信息發(fā)生改變時,由基站重新計算并返回給各節(jié)點?；谏鲜霾呗?可以緩解節(jié)點能耗等問題。

解決多目標(biāo)優(yōu)化問題常見的方法有加權(quán)和方法和Pareto解方法等。加權(quán)和方法需要人為給各目標(biāo)設(shè)定權(quán)值,難于掌握;目前比較流行的Pareto 最優(yōu)概念的進化算法,得出的結(jié)果往往是一組(而不是一個)均勻分布的在Pareto前沿的Pareto占優(yōu)解。

針對這一點,我們設(shè)網(wǎng)絡(luò)生存期單目標(biāo)優(yōu)化最優(yōu)值:

(22)

又設(shè)路由健壯性單目標(biāo)優(yōu)化最優(yōu)值:

(23)

我們可以將原多目標(biāo)優(yōu)化問題改為如下單目標(biāo)問題:

(24)

因此,可將原多目標(biāo)問題轉(zhuǎn)成3個單目標(biāo)問題,而且無需人為給定權(quán)值。

進化算法具體流程如下:

4 實驗與仿真

網(wǎng)絡(luò)仿真設(shè)置在一個矩形區(qū)域內(nèi);N個節(jié)點隨機均勻分布,每個節(jié)點至少有3條鏈路;基站數(shù)目M=3;發(fā)送能耗是接收(空閑等待)能耗的3倍;各條鏈路的故障率都設(shè)為0.01;發(fā)送節(jié)點數(shù)目T為網(wǎng)絡(luò)節(jié)點數(shù)(N)的50%,各發(fā)送節(jié)點單位時間內(nèi)需發(fā)送數(shù)據(jù)分組大小相同,次數(shù)相同(us=256b,Ns=1)。

圖2 迭代次數(shù)與優(yōu)化值

由圖2可以看出,當(dāng)設(shè)置迭代次數(shù)為25時,EA-NL以及AR-EA的種群還沒有完全收斂,適應(yīng)度值仍然有較大的波動。當(dāng)?shù)螖?shù)為95時,EA-NL與AR-EA已經(jīng)收斂,即已計算出最優(yōu)路徑和權(quán)值,說明AR-EA算法有效。從圖2中可以看出,AR-EA在迭代次數(shù)為80時基本保持平穩(wěn),種群平均適應(yīng)值為0.873;而對于EA-NL,由于其實驗優(yōu)化目標(biāo)僅僅是網(wǎng)絡(luò)生存期,而參與比較的卻是網(wǎng)絡(luò)生存期與數(shù)據(jù)分組丟失率的綜合值,因此其優(yōu)化結(jié)果并不理想。而且,由后文實驗可知,網(wǎng)絡(luò)生存期與路由健壯性兩者性能優(yōu)化往往沖突,隨著迭代次數(shù)增加,EA-NL的性能反而有一些降低。

圖3(a) 數(shù)據(jù)分組丟失數(shù)與網(wǎng)絡(luò)生存期(N=30)

設(shè)網(wǎng)絡(luò)節(jié)點數(shù)N=30,以傳統(tǒng)任播路由協(xié)議(即發(fā)送節(jié)點將其監(jiān)測的全部數(shù)據(jù)匯報至最優(yōu)基站,本文標(biāo)記為Anycast)為對照算法,分析AR-EA的路由健壯性和網(wǎng)絡(luò)生存期,結(jié)果如圖3(a)所示。

由圖3(a)可知,AR-EA在網(wǎng)絡(luò)生存期和路由健壯性兩個性能上都明顯優(yōu)于Anycast。這是由于AR-EA在路由策略安排上,采用了WRS策略;而Anycast只采用最優(yōu)路徑這一個單一路徑,其選擇范圍只是WRS策略的一個子集,而AR-EA的路由權(quán)重設(shè)置可以更好地在網(wǎng)絡(luò)生存期和網(wǎng)絡(luò)健壯性上做出權(quán)衡。在圖3(a)中,還可以看出,網(wǎng)絡(luò)生存期和路由健壯性這兩個性能在較大區(qū)間內(nèi)是優(yōu)化沖突的。

再觀察AR-EA算法的可擴展性。在上一個實驗基礎(chǔ)上,設(shè)置不同網(wǎng)絡(luò)規(guī)模(區(qū)域不變,基站數(shù)M不變,節(jié)點數(shù)N=30,90,150),觀察各算法路由健壯性和網(wǎng)絡(luò)生存期,結(jié)果如圖3(a)、圖3(b)、圖3(c)所示。

圖3(b) 數(shù)據(jù)分組丟失數(shù)與網(wǎng)絡(luò)生存期(N=90)

圖3(c) 數(shù)據(jù)分組丟失數(shù)與網(wǎng)絡(luò)生存期(N=150)

由圖3(a)、圖3(b)、圖3(c),可以看出,隨著網(wǎng)絡(luò)規(guī)模增大,在基站數(shù)量不變的情況下,發(fā)送節(jié)點數(shù)增加,任播路徑平均長度增加,從而導(dǎo)致Anycast與AR-EA的數(shù)據(jù)分組丟失率相應(yīng)增加、網(wǎng)絡(luò)壽命相應(yīng)減少。但AR-EA由于采用了WRS策略,網(wǎng)絡(luò)生存期和路由健壯性這兩個性能仍然優(yōu)于Anycast,而且隨著網(wǎng)絡(luò)規(guī)模的增大,這種優(yōu)勢將更加明顯(可供選擇的任播路徑數(shù)的增加)。

5 結(jié)語

以往學(xué)者在研究WSN任播路由算法時,往往較多關(guān)注節(jié)點能耗問題,對網(wǎng)絡(luò)路由健壯性問題關(guān)注較少。而WSN的無線鏈路往往比較脆弱,從而導(dǎo)致重傳能耗、傳輸延遲等問題。因此,本文提出一種基于進化算法的WSN任播路由算法。該算法的優(yōu)化目標(biāo)是網(wǎng)絡(luò)生存期和路由健壯性兩個目標(biāo),并通過多目標(biāo)進化算法尋找到兩者的最佳適應(yīng)值。實驗數(shù)據(jù)證明,相比較基于單目標(biāo)優(yōu)化(網(wǎng)絡(luò)生存期)的任播路由算法,所提算法的網(wǎng)絡(luò)生存期及路由健壯性兩個性能的綜合優(yōu)化值較優(yōu);相比較傳統(tǒng)單路徑任播路由算法,所提算法的網(wǎng)絡(luò)生存期、路由健壯性和可擴展性較優(yōu)。

[1] Xuan D,Jia W,Zhao W,et al. A Routing Protocol for Anycast Messages[J]. IEEE Transactions on Parallel and Distributed Systems,2000,11(6):571-588.

[2] Lenders V,May M,Plattner B. Density-Based Anycast:A Robust Routing Strategy for Wireless Ad Hoc Networks[J]. IEEE/ACM Transactions on Networking,2008,16(4):852-863.

[3] Flury R,Wattenhofer R. Anycast and Multicast Routing for Mesh and Sensor Networks[C]//Proc of INFOCOM’07. 2007:946-954.

[4] Ashraf F,Vaidya N H,Kravets R H. Any-MAC:Extending any Asynchronous MAC with Anycast to Improve Delay in WSN[C]//Proc of SECON 2011. 2011:19-27.

[5] Kim J,Lin X,Shroff N B. Optimal Anycast Technique for Delay-Sensitive Energy-Constrained Asynchronous Sensor Networks[J]. IEEE/ACM Transactions on Networking,2011,19(2):484-497.

[6] Hadi F,Ahmed S,Minhas A A. Wireless-Powered Cooperative Energy Aware Anycast Routing in Wireless Sensor Networks[J]. International Journal of Distributed Sensor Networks,2016,12(11).

[7] Kostin A E,Fanaeian Y,Al-Wattar H. Anycast Tree-Based Routing in Mobile Wireless Sensor Networks with Multiple Sinks[J]. Wireless Networks,2016,22(2):579-598.

[8] Gao D,Liu Y,Zhang F. Anycast Routing Protocol for Forest Monitoring in Rechargeable Wireless Sensor Networks[J]. International Journal of Distributed Sensor Networks,2013,6:1-14.

[9] Yerra R V P,Kiran M P R S,Pachamuthu R. Reliability and Delay Analysis of Slotted Anycast Multi-Hop Wireless Networks Targeting Dense Traffic IoT Applications[J]. IEEE Communications Letters,2015,19(5):727-730.

[10] 劉文博,王濤. 基于水壓的水下傳感網(wǎng)絡(luò)的選播路由協(xié)議[J]. 傳感器學(xué)報,2016,29(12):1899-1904.

[11] Wang X,Wang J,Lu K,et al. GKAR:A Novel Geographick-Anycast Routing for Wireless Sensor Networks[J]. IEEE Transactions on Parallel and Distributed Systems,2013,24(5):916-925.

[12] Gao D,Lin H,Liu X. Routing Protocol fork-Anycast Communication in Rechargeable Wireless Sensor Networks[J]. Computer Standards and Interfaces,2016,43:12-20.

[13] Su S,Yu H,Wu Z. An Efficient Multi-Objective Evolutionary Algorithm for Energy-Aware QoS Routing in Wireless Sensor Network[J]. International Journal of Sensor Networks,2013,13(4):208-218.

[14] Murugeswari R,Radhakrishnan S,Devaraj D. A Multi-Objective Evolutionary Algorithm Based QoS Routing in Wireless Mesh Networks[J]. Applied Soft Computing,2016,40:517-525.