基于事件與能量感知的WMSNs 節點不相交多路徑算法*

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

(中國礦業大學 計算機科學與技術學院，江蘇 徐州221116)

0 引 言

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

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

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

1 路徑決策模型

雖然事件類型和能量大小是兩個不相關的變量，但是它們對路徑決策來說都是關鍵的因素。

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

式中 S(i)為路徑i 上所有節點集合，k 為從源節點到目的節點不相交路徑數，E(i，j，t)為在時間t 時節點i 在路徑j上的剩余能量。

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

定義3 最終概率LR:LR 表示針對當前路徑上節點能量狀態和當前事件緊急程度，各路徑作為傳輸路徑的概率。LR(i，e，t)用例表示在時間為t 時，對事件緊急程度為e 的數據流把路徑i 作為傳輸路徑的概率

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

2 EEDMA

2.1 多路徑路由建立策略

1)源節點首先在自己的路由表中查詢是否存在到達目標節點的路由，如果存在，則根據EEDMA 路徑決策算法從中選擇一條合適的路徑進行傳輸;否則，進入下一步。

2)源節點向其鄰居節點廣播一個RREQt 請求報文，RREQt 報文包括了數據包類型、RREQt 報文ID、路由目標地址、路由源地址、時間戳等信息。

3)自身就是目標節點，則向路徑中回復RREPt 消息報文;否則，首先判斷自身是否已轉發過該報文與該報文是否已過期，如果未轉發過該報文且報文未過期，則向其鄰居節點轉發RREQt 報文。

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

2.2 中間節點轉發RREQt 報文算法

1)解析接收的RREQt 報文，如果源節點收到其他節點發送的RREQt 報文消息，丟包不作處理。

2)判斷自身是否為RREQt 的目標節點，如果是目標節點且未向相同的下一跳發送RREPt 報文，則指定下一跳地址沿著反向路徑向源節點發送RREPt 報文，并釋放RREQt消息報文;否則，進入下一步。

3)如果曾經接收過該報文，則丟棄不作處理;否則，如果在自身鄰居路由表中不存在到達目標節點的路由，則向鄰居節點廣播這一RREQt 報文，并在反向路徑中加入上一跳的節點地址，作為RREPt 回復報文的傳輸路徑。

2.3 中間節點轉發RREPt 報文算法

1)如果是源節點且存在到達該目標節點的路由表項，則比較兩個路由跳數是否相同，如果不相同，則保留路由跳數更小的那一個路由表;否則，將該路由插入到路由表項中。

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

2.4 多路徑決策

源節點需要向目的節點發送不同事件類型數據時，為了緊急事件數據流能以最小的時延發送到目的節點并盡量延長整個網絡的生命周期，必須針對當前網絡中各個節點能量不同的狀態，選擇最佳的路徑進行數據傳輸。基于對事件和能量的感知，以事件能量模型作為決策工具，以式(3)中LR 值最大的路徑i 作為傳輸路徑。

2.5 路由維護

1)每個節點都會定期在網絡相對較空閑時向網絡中發送NHello 報文以獲取最新的鄰居節點信息，并更新鄰居路由表。

2)源節點定期通過路由表中所有的路徑向目標節點發送EHello 報文消息，目標節點接收到EHello 報文消息之后沿著反向路徑向源節點發送ReplyEHello 回復消息，并把報文中的能量值設為無窮大。中間節點轉發ReplyEHello 消息時，如果自身剩余能量小于ReplyEHello 中的路徑最小能量值，則用自身能量值去更新ReplyEHello 的能量值。

3 仿真實驗

3.1 仿真環境與參數

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

3.2 仿真結果分析

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

各路徑節點剩余能量的方差是一個評價網絡中節點能量平衡很好的指標，方差越小，則反映出各路徑中節點的能量消耗較平均。圖1 反映了EEDMA 通過對節點能量的感知可以明顯地減小節點剩余能量方差，特別是當隨著網絡存在時間越長時，能量感知對平衡網絡節點能量的意義越突出。

圖1 各路徑節點剩余能量方差Fig 1 Variance of remained energy of each path node

由圖2 中可以看出:EEDMA 算法比SMP—DSR 算法在減小緊急事件延遲上體現了更好的優越性，增加了網絡對緊急事件的響應速度。為了該事件的數據流能在最短的延遲傳送至目標節點，在保證路徑可用性的基礎上，選擇當前所有可用路徑中時間延遲最短的路徑作為傳輸路徑，因此，在一定程度上減小了該事件數據流的延遲。

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

4 結 論

本文提出了一種EEDMA，介紹了多路徑算法建立的過程，包括多路徑路由發現、中間節點轉發策略、多路徑路維護，利用事件能量決策模型選擇多路徑中的一條作為數據傳遞路徑。該算法充分考慮了不同事件類型對時延的要求和路徑中各個節點能量狀態，為緊急事件等對網絡延遲要求較高的數據流提供了高速的傳輸通道，平衡了網絡中各節點的能量消耗，對延長網絡的生命周期具有重要的意義。

［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，Fukuoka－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.