基于事件与能量感知的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.