一种基于能量感知无线传感器网络多路径路由机制

摘要:目前,无线传感器网络在智能环境检测,灾难控制,战场侦察,安全监视方面取得了日益广泛的应用,引起人们日益关注,在分析无线传感器网络能量消耗特征的基础上,基于Markov模型提出了无线传感器网络节点能量消耗模型,改进了无线传感器网络多路径路由协议。仿真结果表明,与传统的多路径路由机制相比,能够有效地降低无线传感器网络节点能量消耗,提高网络生存时间。

关键词:无线传感器网络; Markov; Wavelet;能量消耗

中图分类号:TP393文献标识码:A文章编号:1009-3044(2010)21-5743-05

A Energy-aware Multipath Routing in Wireless Sensor Networks

WANG Lin1, DUAN Xiao-yang2

(1.College of Software Engineering, Tongji University, Shanghai 201804, China; 2.School of Computer and Information Engineering Henu University, Kaifeng 475004, China)

Abstract: Recently, there has been a growing interest in the potential use of Wireless Sensor Networks (WSNs) in many applications such as smart environments, disaster management, combat field reconnaissance, and security surveillance. Therefore, to realize their potential, there is a need of an simulation platform that facilities the research of wireless sensor network .This paper focuses on developing node energy consumption in WSN.Therefore, we proposed a energy consumption model based on Markov chain, Furthermore, using the proposed algorithm to improve the multi-paths route scheme can extend the lifetime of the whole WSN by remaining load evenly distributed among several paths. According to performance comparison betweenthe traditional algorithmand the new method, numerical results have been proved feasible.

Key words: WSN; markov; multipath route; energy consumption

无线传感器网络(wireless sensor network,简称WSN )的相关研究已经成为现阶段国内外研究的热点[1-4],这不仅因为WSN相关领域技术的迅速发展,如微机电系统(Micro-Electro-Mechanism System)、无线通信和数字电子技术的发展,另外也是由于WSN在国防军事、环境监测、交通管理、医疗卫生、防恐抗灾等众多领域的广阔应用前景。WSN相关协议需要考虑的主要因素有传感器网络节点的有限计算能力和存储空间、传感器节点有限的能量资源等。由于传感器网络有限的计算能力和存储空间,为尽可能减小节点的运算开销,所设计的路由协议必须简单有效。另外,传感器节点通常由电池供电,因此如何高效率地利用有效的电池资源,从而尽可能地延长节点的生命周期也是WSN相关协议要考虑的重点因素。WSN的网络管理与传统网络管理相比,不仅包括QoS支持、故障管理等功能域,还包括能量管理[2]。而WSN能量管理的核心是能量消耗模型,因此不管在理论意义上还是在现实价值中,建立WSN能量消耗模型都显得十分重要。

WSN路由协议的任务是通过建立路由,使传感器节点和汇聚节点之间可靠地传递数据。能量多路径路由[5]在源节点和目的节点之间建立多条路径,首先基于能量因素给每条路径赋予被选择使用的概率,在发送数据时,根据赋予的概率随机选择其中的一条路径发送,这样就没有一条路径一直传送数据的现象,从而防止一条路径上节点能量消耗过快。就是在源节点和目的节点之间建立多条路径,根据路径上节点的通信量消耗以及节点的均衡消耗节点能量延长网络的生存期。但是由于其是在节点发生故障之后进行路径切换的,因此耗费了大量节点的能量资源。

本文针对现有网络传感器网络节点能量消耗的特点,在分析WSN节点能量消耗特征的基础上,通过对无线传感器网络节点的运行状态利用Markov来进行模拟,建立了无线传感器与网络的节点能量消耗模型,并基于能量消耗模型改进了无线传感器网络多路径路由机制,通过在J-sim [6]无线传感器网络仿真平台进行仿真对比,结果验证了Markov节点能量消耗模型的性能,通过分析改进前后的无线传感器网络多路径机制,结果表明基于能量感知的多路径路由机制能够有效降低节点能量消耗,提高网络生存时间。

下文组织如下,第二节在分析WSN节点能量消耗的基础上提出了一个WSN节点能量消耗模型;第三节基于能量消耗模型,改进了传统的WSN多路径路由机制;第四节在Jsim仿真平台分别对WSN能量消耗模型和改进前后的多路径路由机制进行了分析;最后在第五节总结全文。

1 无线传感器网络节点能量消耗模型

1.1 无线传感器网络节点能量消耗分析

典型的传感器网络体系结构通常由分布的传感器节点、接收发送器、互联网和用户界面等构成。其中,传感器节点作为网络中的独立工作实体,其基本的功能子系统包括供电子系统、计算子系统、传感子系统和通信子系统等,如图1所示,其能量消耗分别说明如下。

供电子系统:主要任务是为其他各个子系统供给能源,它主要由电池和DCDC转换器等模块构成。电池是节点最主要的能量来源,因此它的性能与容量就显得至关重要。为实现延长供电子系统的能量供给时间,从而给其他子系统提供持续性的能量供应,可以采用增加电池容量的方法,但采用有效的再充电技术或是太阳能等再生性能源则更利于保证供电子系统的能量来源,。

计算子系统:主要任务是负责控制传感器、执行通信协议和处理传感数据等软件算法,是节点的控制和计算核心。它主要包括存储器和I/O接口电路、微处理器/微控制器、存储器等硬件。作为节点的数据计算中心和功能控制中心,计算子系统与其他各个子系统联系十分紧密,功能也很复杂。因此,其性能高低、功能强弱、在不同工作状态(活动、空闲和休眠等)的持续时长以及不同状态间的相互切换等,都会对整个节点的能量消耗产生严重影响。硬件上减少计算子系统能量消耗的常用技术包括低功耗器件、适时休眠和空闲时的降频技术等。而要从网络的整体来实现网络节点的能量消耗相对均衡,则采用的主要是节点间的功能轮换。

传感子系统:主要任务是将采样/收集被测控对象的敏感信息转换成相应的数字信息,它主要由一组传感器和ADC、控制器等构成。理想情况下,传感子系统自动检测周期性和非周期性两类事件时[7],它的能量消耗总量可以简单描述为单次采样消耗的能量与采样次数的乘积。因此,该子系统的能量消耗可以从以下两个方面进行控制:一是控制单次数据采样所消耗的能量, 可通过采用低功耗器件,从元器件本身有效控制单次数据采样的能量消耗。二是控制采样频率,有选择性地减少单个节点的采样频率,由于传感器网络众多分布节点中往往是成组节点去监测相同的对象或敏感数据,因此它不会对被测数据有效性和完整性造成破坏,只要依据应用需求合理设置节点采样任务的激活原则,就能在保证数据准确性的前提下,较好地控制该子系统的能量消耗。

通信子系统:主要任务是负责节点的通信,由无线收发部件(radio)构成。影响通信子系统能量消耗的关键因素[8-9]包括无线收发部件采用的调制模式、数据率、发射功率和操作周期等。另外,在没有通信任务时,通信子系统应尽可能地处于休眠期,而不是处于空闲期[9]。这是因为通信子系统即使处于空闲期,也有着与接收期几乎相近的能量消耗。

根据以上分析,以分簇方式组织的无线传感器网络,节点能量消耗主要是数据发送和数据处理模块,节点运行时共分为6个状态,如表1所示。其中状态3和状态4消耗能量最多。

1.2 基于Markov的无线传感器网络节点能量预测模型

无线传感器网络节点的状态转换是建立节点能量消耗仿真模型的基础,采用Markov进行节点能量消耗的预测,其中关键点是转移矩阵的生成。

1.2.1 状态转移概率矩阵生成模型

生成WSN状态转移矩阵有两种可行的办法,一种是WSN节点根据自身过去的历史采集状态值构造自己的状态转移矩阵。另一种方法是混合在同一个区域中节点之间的概率,在这种情况下,迁移矩阵将代表一个网络的特定区域中所有节点的行为。最终生成的状态转移阵如式(1)所示:

(1)

其中

2.2.2 Markov能量消耗预测模型分析

通过建立Markov仿真模型来模拟传感器网络节点能量消耗情况,其模型如下所示:

每个节点中用一个随机变量序列表示该节点在这段时间的状态,假设该随机变量为X0,X1,X2……。那么每个节点在同一时间可以处在不同的模式下。Xn=i表示传感器节点在时间段n处于操作模式i下。假定所有的状态迁移发生在任何时间段的开始阶段,如果状态j是节点在状态i后的下一个状态,用Pij来表示节点由状态i迁移到状态j的概率,则这个概率可用下式来表示:

(1)

定义2阶的迁移概率Pij(2)表示一个节点当前在状态i,经历两次状态迁移后到状态j的概率,则该概率可表示为:

(2)

Pij(2)的计算如下式,可以由Pij得出:

(3)

由上可以得出,若Pij(n)为n阶的迁移概率,则由Chapman-Kolmogorov方程式定义如下:

(4)

对于任意0

(5)

Pij(2)的值就是矩阵P和它自身的乘积矩阵P2(P*P)中第i行第j列的元素。类似的,Pij(n)就是矩阵P的n次方的第i行第j列的元素。又Pm+n=Pm*Pn,所以有:

(6)

在上面的模型中,传感器节点的行为由迁移概率矩阵表示,每个节点的初态由X0表示,这样我们就可以建立整个无线传感器网络能量消耗序列。

假定现在节点在初态i,即X0=i,节点在经过T个时间段后到达状态s,Pis(t)表示节点当前处在初态I,经历t个时间段迁移到达状态S的概率。则节点停留在任意的一个状态s的时间段数可用下式计算:

(7)

假设BS表示节点在状态S停留一个时间段所传输的数据量,BT表示节点当前处在状态i,经过T个时间段后到达状态s所传输的数据总量。而节点经过T个时间段到达状态s 的期望时间段数可由计算出来,于是可以得出BT:

(8)

由计算可以得出每个节点在时间T的数据,总的节点数由下式来计算:

(9)

其中BS表示一个节点在状态s 停留一个时间段所传输的数据量,Ck-i表示它是属于簇Ck 的第i个传感器节点,Pis表示从状态i迁移到状态s的概率。

综合上述可知,根据无线传感器网络的状态转移矩阵和建立Markov模型可以预测节点在T时刻的能量消耗。

2 改进多路径路由协议

2.1 改进思想

在传感器网络中,为了实现网络负载平衡和提高数据传输的可靠性,于是引入了多路径路由。文献提出一种多路径路由机制,通过预先建立和维护一组数据,从而不需要周期性洪泛就能够得到从数据源节点到汇聚节点的传输路径。其基本思想是:在从数据源节点到汇聚节点之间除了建立一条主路径之外,还建立多条备份路径,首先通过主路径传送数据来维护数据的有效性,但当主路径失败时,就从建立的备用路径中选择次优路径进行数据传送。但是,这种思想并不适用于WSN的需求,因为由主路由失败触发的切换机制所引起的负载不均衡会导致传感器节点资源消耗的不均衡,从而降低WSN全网的生存期。改进该思想,可以引入能量消耗预测机制,这样主路径在预测其将要传输失败前就切换至次优路径,从而实现WSN多路径之间的负载均衡。

2.2 实例分析

如在图2所示的WSN节点拓扑中,节点A为传感器源节点,汇聚节点sink node是目的节点,在基于预测的多路径路由机制中,假定路径A-B-C-D-sink node 为主路径,其他两条路径为次优路径。其基本步骤为:

1) 在主路径A-B-C-D-sink node中,每个关键节点中都建立了Markov能量消耗预测模型。

2) 主路径中的关键节点从本地检测网络流量,建立阈值,如果检测到即将发生拥塞,或者本节点能量即将耗尽,或者流量超过本节点负载,则给源节点A发送一个消息。

3) 源节点A接收到关键节点发送的消息后,就会立即进行路径切换,选择一条次优路径进行数据传输。

3 仿真比较分析

3.1 Markov能耗预测模型仿真说明

仿真的主要目的是比较Markov能量消耗感知模型和真实WSN能量消耗的性能,共分为训练时间比较和预测效果比较两个方面,采用了J-sim平台进行比较仿真验证。J-Sim是一种基于Java的、开放源代码的、实时进程驱动的网络仿真平台。该项目由美国DARPA、NSF、Cisco公司及美国高校项目资助开发。除了支持IP网络之外,J-Sim还支持多种有线(MPLS、区分服务、综合服务)和无线网络(Ad hoc网络、无线传感器网络),能够对不同网络层次、不同网络结构、不同网络组件进行实时仿真。

具体仿真步骤如下所示:

1) 在真实环境中中进行WSN节点能量消耗采集,采样流量数据的采集是每隔1秒采集一个数据,采集了88组数据。

2) 在J-Sim中,扩展实现Markov能量消耗模型。

3) 把步骤1)中所采集得到的WSN节点能量消耗数据序列化为矩阵。

4) 利用Markov能量消耗模型模拟WSN节点能量消耗过程。

5) 将仿真结果利用Jsim绘图工具绘制成图。

真实无线传感器网络节点采用了Medusa II Nodes.其能量消耗参数如表2所示。

3.2 WSN能量消耗仿真结果分析

仿真结果如图3所示,在时间段(0,12)WSN节点状态为休眠状态,能量消耗比较少,在时间段(21,42)WSN节点采集传感数据,在时刻31秒是能量消耗很大,然后节点在时间段(47,60)进行传感数据处理,节点能量消耗相对较低,最后在(70,88)节点把传感数据通过路由协议发送给其他节点,整体能量消耗达到最大点,与真实WSN节点能量消耗过程相比,Markov能量消耗模型能够准确的预测出节点运行状态变换,而且在每一个状态中模拟曲线对实际WSN节点能量消耗具有良好的逼近性能,整体误差范围较小,说明基于Markov的WSN能量消耗仿真模型能够有效的预测现有真实WSN节点的能量消耗过程。

3.3 WSN多路径仿真

利用J-sim对改进前后的多路径路由协议进行了性能比较。实验参数如表3所示。

感知节点每次采样生成的数据量为4096byte,分别用改进前后的多路径路由协议机制对数据进行传送。试验中对生存节点个数和全网的能耗在每个采样周期都进行了统计。统计结果如图4所示。

图4(a)为改进前后的存活节点的采样值的统计图。在前400s内,存活节点的数量均未减少,而在400s之后,改进前的多路径路由协议的存活节点数迅速下降,在600s内即减少为0,而在改进后的多路径路由协议机制中,节点的减少速度相对较小,特别在400s-500s之间,与改进前的相比节点的存活数减少趋势较为平缓,最终在700s处才减少为0。因此改进后的协议可有效地减小WSN存活节点的减少速度。

图4(b)为改进前后的全网能耗的统计图。全网的初始功率为200J。基于能量预测的多路径路由协议在同采样时刻中的能耗和全网的生存期中,都表现出较改进前的更好的性能。这是因为在改进前的多路径路由协议中,路径切换至次优路径中是在主路径失败之后,而在改进后的多路径路由协议中,路径的切换是在主路径即将失败时实现的,这样就使得全网的负载在各个路径中的分配得以有效地平衡。这种机制与固定网中常见的重路由机制相类似,区分WSN中切换的是整条路径,而在固定网中只是在路由的某一结点处调整网络流量的物理路径。

4 结论

综上分析,本文通过采用Markov过程来模拟WSN节点的运行状态,从而建立了WSN的节点能量消耗模型,并通过在J-sim网络仿真平台将其与一个真实的WSN节点能量消耗进行了对比分析,仿真结果表明本文提出的WSN能量消耗模型能够有效的表示WSN能量消耗过程,并将能量预测模型引入到WSN多路径路由机制中,结果表明该机制能够有效减少WSN能量消耗,提高WSN中的节点存活数量。

参考文献:

[1] 孙利民,李建中.无线传感器网络[M].北京:清华大学出版社,2005,5.

[2] 崔莉,鞠海玲.无线传感器网络研究进展[J].计算机研究与发展,2005.42(1):163-174.

[3] Wireless Integrated Network Sensors, University of California, Los Angeles.Available: www.janet.ucla.edu/WINS.

[4] J.M. Kahn, R.H. Katz,,K.S.J. Pister.Next century challenges: Mobile for smart dust,in Proc. Mobicom,1999:483-492.

[5] Ganesan D., Govindan R.etc Highly-resilient, energy-efficient multipath routing in wireless sensor networks. Mobile Computing Review,2002.1(2):11-25.

[6] Jsim.www.cs.uga.edu/~jam/jsim/.

[7] Rhee S,Seetharam D,Liu S,et al. I Beans: An Ultra low Power Wireless Sensor Network.Interactive Poster in the Fifth International Conference on Ubiquitous Computing (UBICOMP),October,2003.

[8] A. Wang, S-H. Cho, C.G. Sodini, and A.P. Chandrakasan.Energy-efficient modulation and MAC for asymmetric microsensor systems, in Proc.ISLPED, 2001:106-111.

[9] C. Schurgers,O. Aberthorne, and M. Srivastava,Modulation scaling for energy aware communication systems, in Proc. ISLPED, 2001:96-99.

[10] Dhanaraj M,Manoj B S,et al.A New Energy Efficient Protocol for Minimizing Multihop Latency in Wireless Sensor Networks.Proc of the 3rd IEEE Int'l Conf.on Pervasive Computing and Communications,2005.

注:本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文