传感器网络中考虑响应时间的路由机制

0 引言

作为热点问题,无线传感器网络(WSN,wirelesssensornetwork)鲜有实际应用.究其原因,主要有以下2点:传感器节点(SN,sensornode)价格较高;没有考虑实际情况的路由协议.为详细说明第2点,首先介绍WSN的性质.在普遍意义上,它具有以下特性:

①SN能量有限;

②SN的放置采用飞机投撒等方式,不能精确控制;

③WSN是无线自主的,设定SN的初始状态之后的拓扑启动和网络运行是自组织的.

传统网络路由算法和普通Adhoc网络路由算法都不能很好地应用于WSN中,针对传感器网络路由算法的研究,前期比较典型的工作有LEACH,LEACH2,TEEN和PEGAGIS等.它们考虑使链路代价最低而没有考虑负载平衡.之后的工作以负载平衡和链路代价两者结合作为算法性能衡量标准,比较典型的有负载平衡组划分、最大化网络生命期等.二层路由协议较平面路由协议更加负载平衡.AlbertoCerpa等提出了一种实际可用的参与度模型,本文路由机制基于该模型.

本文将WSN分为邻域发现(ND,neighbor discovery)、动态参与度模型(DJM,dynamic joining model)、组内路由和组间路由.在假设前2层模型有较好实现的情况下研究了组内路由算法.为引入响应时间这一WSN应用的重要指标,提出2种方法对现有的路由算法进行改进:沿用节能性路由算法并在节点中根据响应时间(RT,response time)约束修订路由;组长(CHSN,cluster head sensor node)在计算路由时考虑RT因素,为节点消息的不同RT要求分别计算路由.

1WSN参考模型及基本假定

1.1层次介绍
无线传感器网络MAC层、网络层以及传输层都是WSN中研究的热点问题.为了明确研究内容和方法,提出以能量节省、响应时间和传送质量为标准将WSN中的课题划分为物理层、MAC层、网络层(该层包含ND协议、路由等,具体关系如图1所示)和应用层.



图1细化的网络层

1.2ND与DJM协议

ND协议为每个SN提供邻居信息,其中邻居定义为可以和该节点单跳传送的SN集合.考虑到WSN应用环境可能会有突发事件,如某SN被监控对象撞坏,使用定时查询方式实现ND协议,该协议采集数据的类型取决于DJM的设计.本文使用丢包率、剩余能量和邻居个数作为DJM的参考标准,因此,ND协议需要采集邻居的能量信息并统计丢包率.其中,邻居的判定依据为丢包率是否小于对应的丢包率门限.

在ND协议提供必要数据的基础上,本文采用了参与度模型,即在某一时刻只有部分节点参与组建网络.该模型中SN有4种状态(sleep、passive、test、active),只有处于test和active状态时参与网络传送消息.passive状态节点只接收邻居状态消息,监测网络通信质量,当丢包率和邻居数不符合要求时,按状态转换自动机转入test状态以改善网络连通性和通信质量,其余sleep节点休眠以节能.

2 路由机制描述

2.1问题与假定

本文研究满足响应时间的节能组内路由机制.首先,说明对WSN的描述和假定.

①SN能量有限,密集分布,采用飞机投撒等方式放置,不能精确控制;

②WSN是无线自组网,允许多跳(multi-hop)路由;

③WSN对响应时间的要求为硬约束,即数据必须在它对应的响应时间内传送到组长.

以响应时间为硬约束、能量消耗为标准采用集中式算法考虑组内路由策略.因为现有的分布式Bellman-Ford算法要求网络初始和拓扑变化时所有节点都必须已知全局拓扑,代价太高.对于节能路由,使用贪心算法多次迭代就可得到近似最优路径.不考虑RT约束的集中式组内节能路由算法基于以下假定:

①组内只有一个组长,它已知组内全局拓扑;

②SN具有初始标志,并具有一定的存储和判定能力;

③ND、DJM和链路代价都具有良好的实现.

链路代价表示一定量数据经过一段链路的消耗,等于其所含边对应数据传送的耗能总和.发送数据代价(使用RSSI测量)和节点能量都可以在ND协议中获得,使用文献[1]中链路代价模型.因为SN的路由路径是个Markov链,即链路中到第i个节点的路由仅由第i-1个节点确定.组内路由算法可以描述为第1步:针对每个SN,SN以最小化该节点与CHSN间的链路代价为标准选择下一跳中继SN;第2步:若拓扑内路由有变化,转向第1步,否则路由决策结束.下面提出节点决策和组长决策2种方式修正路由策略引入RT硬约束.

2.2节点决策

经过上述路由算法,组长为每个节点确定最佳节能路由并发送路由表.节点决策机制下,每个节点根据消息的RT约束对组长发来的路由路径进行调整.消息m的链路延时使用如式(1)表示,它由数据发送时间和节点延迟时间2部分构成.

其中,L为对应链路;S(m)为m的长度;C(e)为边e上m的延时,由e的起始节点的延迟R(e)和发送S(m)数据量的延迟(数据长度除以该边的传送速率c)2部分构成.由式(1)可见,链路包含节点数越少,延迟时间越短.节点决策路由表述为:对应于每个发送消息的RT约束,SN逐步去除链路中SN的直接中继节点(SN找其直接中继节点的直接中继做直接中继节点),直至满足该RT约束或者该SN无法直接传送到下一中继节点.

2.3组长决策

节点决策机制较简单,但是节能效果不是最优.可以利用组长进行决策,在原有的节能链路上为不同RT约束等级计算路由.不失一般性,假定SN具有相同的通信模型,此时RT约束可以转化为链路中继节点数的约束.组长决策路由为:对于某SN,设节能算法(如2.1节所述)计算出的路由链路为L,对应的中继节点集合为C,RT等级集合为R(RT等级已经转化为中继节点的个数).对应R中每个等级r(r=1,2,.)在C中选取构成链路能量消耗最小的r个节点.下面介绍节点决策和组长决策算法应用到WSN路由机制中的相关问题.