基于事件與能量感知的WMSNs 節(jié)點(diǎn)不相交多路徑算法*

趙作鵬，康清華，許新征，李曉波

(中國礦業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 徐州221116)

0 引 言

隨著科技的迅速發(fā)展，無線多媒體傳感器網(wǎng)絡(luò)(wireless multimedia sensor networks，WMSNs)成為智能地球中不可或缺的一部分。WMSNs 與傳統(tǒng)的無線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSNs)不同，WSNs 多用于傳輸溫度、壓力、濕度、噪聲等較小的數(shù)據(jù)流，傳輸?shù)臄?shù)據(jù)量有限;而WMSNs 主要是用于傳輸視頻、音頻數(shù)據(jù)流等數(shù)據(jù)量大的方面，解決了傳統(tǒng)WSNs 所面臨的問題;但由于WMSNs 中節(jié)點(diǎn)能量的限制和傳輸數(shù)據(jù)消耗能量相對(duì)較多，所以，平衡整個(gè)網(wǎng)絡(luò)的能量消耗以延長整個(gè)網(wǎng)絡(luò)的生命周期具有非常重要的意義。

許多學(xué)者已經(jīng)提出了各種有關(guān)建立節(jié)點(diǎn)不相交路徑的方案。文獻(xiàn)［1］中提出了一種建立基于地理與能量感知、不沖突的節(jié)點(diǎn)不相交多路徑的方案，該方案加快了傳輸速率并減小傳輸跳數(shù)，但是沒有對(duì)各個(gè)路徑進(jìn)行分類，對(duì)于異常事件的數(shù)據(jù)處理無法做出最快的響應(yīng);文獻(xiàn)［2］中利用了一種類似管道的概念對(duì)各個(gè)傳輸路徑進(jìn)行“隔離”，以此解決多路徑之間相互沖突的問題。文獻(xiàn)［3］提出了一種基于能量感知的多路徑?jīng)Q策算法，充分獲取各路徑上節(jié)點(diǎn)的能量信息來選取能量較富裕的路徑作為傳輸路徑，以達(dá)到了平衡網(wǎng)絡(luò)能量的目的，但并未對(duì)理論進(jìn)行相關(guān)實(shí)驗(yàn)分析。文獻(xiàn)［4］提出了一種在多條網(wǎng)絡(luò)中完全的不相交路徑算法，利用地理位置的感知，為鏈路之間的相對(duì)獨(dú)立提供保證。上述文獻(xiàn)中針對(duì)事件感知的涉及較少，基于對(duì)當(dāng)前各路徑節(jié)點(diǎn)能量狀態(tài)的感知為不同事件類型的數(shù)據(jù)采用不同的策略，以提供高效的數(shù)據(jù)傳輸服務(wù)和最大化網(wǎng)絡(luò)的生命周期。

本文綜合考慮了路徑中節(jié)點(diǎn)剩余能量狀態(tài)與當(dāng)前傳輸數(shù)據(jù)流的緊急程度，提出了一種基于事件與能量感知的節(jié)點(diǎn)不相交多路徑算法(event and energy aware node－disjoint multipath routing algorithm，EEDMA)。該算法為路徑?jīng)Q策提供了可靠的信息，為不同事件類型的數(shù)據(jù)提供高效、可靠的傳輸。

1 路徑?jīng)Q策模型

雖然事件類型和能量大小是兩個(gè)不相關(guān)的變量，但是它們對(duì)路徑?jīng)Q策來說都是關(guān)鍵的因素。

定義1 重要能量SE:SE 表示一條路徑上最小的剩余能量，用SE(i，t)表示在時(shí)間t 時(shí)，路徑i 上剩余最少的能量值。用SES(i，t)表示所有路徑中剩余能量最少的集合

式中 S(i)為路徑i 上所有節(jié)點(diǎn)集合，k 為從源節(jié)點(diǎn)到目的節(jié)點(diǎn)不相交路徑數(shù)，E(i，j，t)為在時(shí)間t 時(shí)節(jié)點(diǎn)i 在路徑j(luò)上的剩余能量。

定義2 重要能量概率SER:SER 表示路徑上節(jié)點(diǎn)的能量狀態(tài)在路徑選擇中概率的大小，SER(i，t)用來表示在時(shí)間t 時(shí)，選擇路徑i 作為傳輸路徑相對(duì)概率的大小

定義3 最終概率LR:LR 表示針對(duì)當(dāng)前路徑上節(jié)點(diǎn)能量狀態(tài)和當(dāng)前事件緊急程度，各路徑作為傳輸路徑的概率。LR(i，e，t)用例表示在時(shí)間為t 時(shí)，對(duì)事件緊急程度為e 的數(shù)據(jù)流把路徑i 作為傳輸路徑的概率

式中 maxEnergy，minEnergy 分別為當(dāng)前路徑中最大的最小的剩余能量值，U(e)為緊急事件集合，M(e)為中等程度事件集合，C(e)為普近事件集合，minH(i)為從源節(jié)點(diǎn)到目的節(jié)點(diǎn)所需跳數(shù)最少的路徑的集合，maxH(i)為從源節(jié)點(diǎn)到目的節(jié)點(diǎn)所需跳數(shù)最大的路徑的集合;結(jié)合源節(jié)點(diǎn)在當(dāng)前事件緊急程度及其可用路徑中節(jié)點(diǎn)的能量狀態(tài)，利用最終概率判斷哪一條路徑作為最終的傳輸路徑。

2 EEDMA

2.1 多路徑路由建立策略

1)源節(jié)點(diǎn)首先在自己的路由表中查詢是否存在到達(dá)目標(biāo)節(jié)點(diǎn)的路由，如果存在，則根據(jù)EEDMA 路徑?jīng)Q策算法從中選擇一條合適的路徑進(jìn)行傳輸;否則，進(jìn)入下一步。

2)源節(jié)點(diǎn)向其鄰居節(jié)點(diǎn)廣播一個(gè)RREQt 請(qǐng)求報(bào)文，RREQt 報(bào)文包括了數(shù)據(jù)包類型、RREQt 報(bào)文ID、路由目標(biāo)地址、路由源地址、時(shí)間戳等信息。

3)自身就是目標(biāo)節(jié)點(diǎn)，則向路徑中回復(fù)RREPt 消息報(bào)文;否則，首先判斷自身是否已轉(zhuǎn)發(fā)過該報(bào)文與該報(bào)文是否已過期，如果未轉(zhuǎn)發(fā)過該報(bào)文且報(bào)文未過期，則向其鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)RREQt 報(bào)文。

4)源節(jié)點(diǎn)收到RREPt 回復(fù)消息，判斷自身路由表中是否存在下一跳與目標(biāo)地址相同的路由，如果不存在，則把下一跳與目標(biāo)地址插入到路由表中。

2.2 中間節(jié)點(diǎn)轉(zhuǎn)發(fā)RREQt 報(bào)文算法

1)解析接收的RREQt 報(bào)文，如果源節(jié)點(diǎn)收到其他節(jié)點(diǎn)發(fā)送的RREQt 報(bào)文消息，丟包不作處理。

2)判斷自身是否為RREQt 的目標(biāo)節(jié)點(diǎn)，如果是目標(biāo)節(jié)點(diǎn)且未向相同的下一跳發(fā)送RREPt 報(bào)文，則指定下一跳地址沿著反向路徑向源節(jié)點(diǎn)發(fā)送RREPt 報(bào)文，并釋放RREQt消息報(bào)文;否則，進(jìn)入下一步。

3)如果曾經(jīng)接收過該報(bào)文，則丟棄不作處理;否則，如果在自身鄰居路由表中不存在到達(dá)目標(biāo)節(jié)點(diǎn)的路由，則向鄰居節(jié)點(diǎn)廣播這一RREQt 報(bào)文，并在反向路徑中加入上一跳的節(jié)點(diǎn)地址，作為RREPt 回復(fù)報(bào)文的傳輸路徑。

2.3 中間節(jié)點(diǎn)轉(zhuǎn)發(fā)RREPt 報(bào)文算法

1)如果是源節(jié)點(diǎn)且存在到達(dá)該目標(biāo)節(jié)點(diǎn)的路由表項(xiàng)，則比較兩個(gè)路由跳數(shù)是否相同，如果不相同，則保留路由跳數(shù)更小的那一個(gè)路由表;否則，將該路由插入到路由表項(xiàng)中。

2)如果不是源節(jié)點(diǎn)，則比較自身剩余的能量與RREPt報(bào)文中的能量信息，如果小于RREPt 消息中最小能量，則用自身剩余能量去更新RREPt 報(bào)文消息中的能量值，然后在反向路徑中查找到達(dá)源節(jié)點(diǎn)的下一跳地址，更新RREPt報(bào)文的下一跳，轉(zhuǎn)發(fā)該報(bào)文。

2.4 多路徑?jīng)Q策

源節(jié)點(diǎn)需要向目的節(jié)點(diǎn)發(fā)送不同事件類型數(shù)據(jù)時(shí)，為了緊急事件數(shù)據(jù)流能以最小的時(shí)延發(fā)送到目的節(jié)點(diǎn)并盡量延長整個(gè)網(wǎng)絡(luò)的生命周期，必須針對(duì)當(dāng)前網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)能量不同的狀態(tài)，選擇最佳的路徑進(jìn)行數(shù)據(jù)傳輸?；趯?duì)事件和能量的感知，以事件能量模型作為決策工具，以式(3)中LR 值最大的路徑i 作為傳輸路徑。

2.5 路由維護(hù)

1)每個(gè)節(jié)點(diǎn)都會(huì)定期在網(wǎng)絡(luò)相對(duì)較空閑時(shí)向網(wǎng)絡(luò)中發(fā)送NHello 報(bào)文以獲取最新的鄰居節(jié)點(diǎn)信息，并更新鄰居路由表。

2)源節(jié)點(diǎn)定期通過路由表中所有的路徑向目標(biāo)節(jié)點(diǎn)發(fā)送EHello 報(bào)文消息，目標(biāo)節(jié)點(diǎn)接收到EHello 報(bào)文消息之后沿著反向路徑向源節(jié)點(diǎn)發(fā)送ReplyEHello 回復(fù)消息，并把報(bào)文中的能量值設(shè)為無窮大。中間節(jié)點(diǎn)轉(zhuǎn)發(fā)ReplyEHello 消息時(shí)，如果自身剩余能量小于ReplyEHello 中的路徑最小能量值，則用自身能量值去更新ReplyEHello 的能量值。

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

3.1 仿真環(huán)境與參數(shù)

為了驗(yàn)證EEDMA 的可靠性，本文利用NS2 網(wǎng)絡(luò)仿真工具進(jìn)行實(shí)驗(yàn)分析。提供了三種不同事件類型的數(shù)據(jù)仿真。在250 m×250 m 區(qū)域中隨機(jī)分布若干節(jié)點(diǎn)，從中選取了三條節(jié)點(diǎn)不相交的路徑作，仿真場景參數(shù)如下:區(qū)域大小為250 m×250 m，區(qū)域節(jié)點(diǎn)密度為4096/km2，MAC 層協(xié)議為IEEE 802.11，節(jié)點(diǎn)發(fā)射半徑為25 m，節(jié)點(diǎn)初始能量為50 J，發(fā)射功率為0.3 W，接收功率為0.2 W，空閑時(shí)功率為0.03 W，睡眠時(shí)功率為0.01 W，MAC 層協(xié)議為IEEE 802.11。

3.2 仿真結(jié)果分析

在上述條件下，將本文的EEDMA 與文獻(xiàn)［10］中節(jié)點(diǎn)不相交路徑算法(SMP－DSR)進(jìn)行比較分析，本文主要分析了WMSNs 中的路徑生命周期、節(jié)點(diǎn)能量平衡程度、緊急事件數(shù)據(jù)的傳輸延遲。

各路徑節(jié)點(diǎn)剩余能量的方差是一個(gè)評(píng)價(jià)網(wǎng)絡(luò)中節(jié)點(diǎn)能量平衡很好的指標(biāo)，方差越小，則反映出各路徑中節(jié)點(diǎn)的能量消耗較平均。圖1 反映了EEDMA 通過對(duì)節(jié)點(diǎn)能量的感知可以明顯地減小節(jié)點(diǎn)剩余能量方差，特別是當(dāng)隨著網(wǎng)絡(luò)存在時(shí)間越長時(shí)，能量感知對(duì)平衡網(wǎng)絡(luò)節(jié)點(diǎn)能量的意義越突出。

圖1 各路徑節(jié)點(diǎn)剩余能量方差Fig 1 Variance of remained energy of each path node

由圖2 中可以看出:EEDMA 算法比SMP—DSR 算法在減小緊急事件延遲上體現(xiàn)了更好的優(yōu)越性，增加了網(wǎng)絡(luò)對(duì)緊急事件的響應(yīng)速度。為了該事件的數(shù)據(jù)流能在最短的延遲傳送至目標(biāo)節(jié)點(diǎn)，在保證路徑可用性的基礎(chǔ)上，選擇當(dāng)前所有可用路徑中時(shí)間延遲最短的路徑作為傳輸路徑，因此，在一定程度上減小了該事件數(shù)據(jù)流的延遲。

圖2 異常事件的時(shí)間延遲Fig 2 Time delay of abnormal event

4 結(jié) 論

本文提出了一種EEDMA，介紹了多路徑算法建立的過程，包括多路徑路由發(fā)現(xiàn)、中間節(jié)點(diǎn)轉(zhuǎn)發(fā)策略、多路徑路維護(hù)，利用事件能量決策模型選擇多路徑中的一條作為數(shù)據(jù)傳遞路徑。該算法充分考慮了不同事件類型對(duì)時(shí)延的要求和路徑中各個(gè)節(jié)點(diǎn)能量狀態(tài)，為緊急事件等對(duì)網(wǎng)絡(luò)延遲要求較高的數(shù)據(jù)流提供了高速的傳輸通道，平衡了網(wǎng)絡(luò)中各節(jié)點(diǎn)的能量消耗，對(duì)延長網(wǎng)絡(luò)的生命周期具有重要的意義。

［1］ Li Boyi，Chuang Po－Jen.Geographic energy－aware non－interfering multipath routing for multimedia transmission in wireless sensor networks［J］.Information Science，2013，249:24－37.

［2］ Lee Jeongcheol，Park Hosung.Radio－disjoint geographic multipath routing for reliable data transfer in lossy WSNs［C］∥IEEE 26th International Conference on Advanced Information Networking and Applications，F(xiàn)ukuoka－shi，Japan，2012:1－5.

［3］ Xie Mande，Gu Yanyan.Multipath routing algorithm for wireless multimedia sensor networks within expected network lifetime［C］∥International Conference on Communications and Mobile Computing，Los Alamitos，CA，2010:284－287.

［4］ Sonia Waharte，Raouf Boutaba.Totally disjoint multipath routing in multihop wireless networks［C］∥2006 IEEE International Conference on Communications，Istanbul，Turkey，2006:5576－5581.

［5］ Akyildiz I F，Melodia T，Chowdhury K R.A survey on wireless multimedia sensor networks［J］.Comput Networks，2007，51(4):921－960.

［6］ Shu L，Zhang Y，Yang L T，et al.Geographic routing in wireless multimedia sensor networks［C］∥2008 Second Int’l Conf on Future Generation Communication and Networking，Hainan Island，China，2008:68－73.

［7］ Galvez J J，Ruiz P M，Skarmeta A.Achieving spatial disjointness in multipath routing without location information［C］∥IEEE 2009 Wireless Communications and Networking Conference，Budapest，Hungry，2009:1－6.

［8］ Yan Guoqiang，Duan Weijun，Ma Chao，et al.Minimize interference while using multipath transportation in wireless multimedia sensor networks［J］.Recent Advances in Computer Science and Information Engineering，2012，4:239－244.

［9］ Perkins C E，Royer E M.Ad－Hoc on demand distance vector routing［C］∥Proceedings of IEEE WMCSA’99，New Orleans，LA，1999:90－100.

［10］Shabnam Vahedi，MaryamMohseni.Design a multi－path routing algorithm in Ad Hoc networks in order to improve fault tolerance［C］∥18th IEEE International Symposium on Personal，Indoor and Mobile Radio Communication，Athens，Greece，2007:2804－2808.

［11］Mahesh K Marina，Samir R Das.Ad Hoc on－demand multipath distance vector routing［J］.Wireless Communications and Mobile Computing，2006，6:969－988.