基于進化算法的無線傳感器網絡任播路由算法*

顧云麗,徐 昕,張嫣娟

(1.南京信息工程大學江蘇省網絡監控中心,南京 210044;2.南京信息工程大學計算機與軟件學院,南京 210044)

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

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

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

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

1 網絡模型及問題描述

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

WSN往往用來監控其覆蓋范圍內若干指定目標,該目標附近節點往往需定期匯報監測數據至任一基站。這些發送節點集合標記為S,L為S中節點數目。

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

Ps={Ps1,Ps2,…,PsM}

(1)

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

P={P1,P2,…,PL}

(2)

P的路由權重集合W表示如下:

W={W1,W2,…,WN}

(3)

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

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

(4)

因此,節點v單位時間內處于發送狀態的時間tvs為:

tvs=Dv/τ

(5)

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

Ev=tvsEdelivery+(1-tvs)Eidle

(6)

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

學者在設計WSN路由算法時往往以網絡生存期最大化為優化目標。如圖1中,S1和S2為發送節點,各需匯報u大小數據分組至基站;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是最短路徑。但為最大化網絡生存期,發送節點不能只采用一條任播路徑(最短路徑或無交叉路徑)。而是根據WRS策略,將數據流分散到各條任播路徑上。圖1中,為最大化網絡生存期,顯然應設置P1路由權重W1={w11w12}={0.666 0.333};而P2的W2=(w23w21)=(0.666 0.333)。即S1將0.666u分組通過路徑P12匯報至A2,將0.333u分組通過路徑P11匯報至A1,S2也依此處理。

圖1 網絡示意圖

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

設fi為鏈路ei出現故障的概率,本文設定鏈路的故障彼此之間是完全獨立的事件。本文還設定,中間節點不保存其轉發的數據分組,即若傳輸任務失敗需路徑源節點重新發送丟失的分組。

設路徑Psj∈P,Psj單位時間內路徑出現故障的概率rsj計算如下:

(7)

(8)

(9)

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

(10)

節點v壽命Lv計算如下:

(11)

式中:Einit是節點的初始能量。

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

(12)

經過簡化,Fe為:

(13)

可得,使用鏈路e∈E,導致任播路徑數據分組丟失率如下:

(14)

我們設計的任播路由算法,其算法設計目標之一是最大化網絡生存期。即

(15)

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

(16)

該優化問題記為

(17)

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

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

(18)

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

(19)

3 多目標進化算法優化

由上文可知,我們的優化目標不僅是網絡生存期,還要包括路由健壯性。即我們優化的目標如下:

(20)

(21)

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

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

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

針對這一點,我們設網絡生存期單目標優化最優值:

(22)

又設路由健壯性單目標優化最優值:

(23)

我們可以將原多目標優化問題改為如下單目標問題:

(24)

因此,可將原多目標問題轉成3個單目標問題,而且無需人為給定權值。

進化算法具體流程如下:

4 實驗與仿真

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

圖2 迭代次數與優化值

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

圖3(a) 數據分組丟失數與網絡生存期(N=30)

設網絡節點數N=30,以傳統任播路由協議(即發送節點將其監測的全部數據匯報至最優基站,本文標記為Anycast)為對照算法,分析AR-EA的路由健壯性和網絡生存期,結果如圖3(a)所示。

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

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

圖3(b) 數據分組丟失數與網絡生存期(N=90)

圖3(c) 數據分組丟失數與網絡生存期(N=150)

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

5 結語

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

[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] 劉文博,王濤. 基于水壓的水下傳感網絡的選播路由協議[J]. 傳感器學報,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.