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

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协议中获得,使用文献中链路代价模型.因为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路由机制中的相关问题.

3 路由机制应用

同构和异构网络的启动方式不尽相同,基本的启动过程为:节点定时启动,处于test状态;ND协议;根据DJM确定节点状态(组长节点和普通节点);组划分与组间路由;组内路由;事件驱动拓扑控制.

组内路由初始时使用直接传送协议收集网络拓扑信息.CHSN收集完组内拓扑后,运行本文提出的考虑RT约束的节能路由算法.事件驱动机制为:仅当组长变化或者组内拓扑变化时,组长重新计算路由.组长变化有2种情况:CHSN主动退休和CHSN突然出现故障.组内局部拓扑变化有增加和去除节点2种情况.

协议中使用多入单出式路由表,使得每个SN向路由表中唯一后继节点传送信息(采集信息和中继信息).节点决策路由中,每个节点需保存自己到CHSN路径中每一跳节点信息.而组长决策路由表要为每个RT级别存储一个下一跳节点信息(只有数据采集信息具有响应时间约束,其他信息如路由信息等无此约束).消息每中继一次,对应的RT字段便更新并根据当前节点的路由表发送.

4 模型验证

4.1模型分析

路由机制的复杂度包括:CHSN时间、空间复杂度、SN时间、空间复杂度和全局的通信复杂度.首先对组内信息做以下设定:

①组内节点数为n;

②组半径为r,即组内节点与组长传送消息所需的最大跳步数;

③响应时间划分为g个级别.

首先分析未考虑响应时间约束的节能算法复杂度.211节所述组内路由算法每次迭代的平均和最坏时间复杂度都是O(n2)(最坏复杂度为n2,平均复杂度为n2/2),而经过模拟测试知迭代次数是有限的(随机分布的500个节点的情况迭代次数不超过20次).下面分别分析节点决策和组长决策机制.

4.1.1节点决策复杂度

首先分析通信复杂度.因为路由确定过程的数据包主要是路由信息包,1个路由数据包带来的复杂度等于包长与包传送次数的乘积.该包中数据信息为发送路径的标志集合,1个需要m跳的路由信息的通信复杂度为

Comm(m)=mLhead+Lidm(m-1)/2 (2)

其中,通信复杂度Comm为跳数m的函数;Lhead为数据包首部长度;Lid为节点标志占用比特数.更新1个节点路由信息的最坏复杂度为Comm(r)即O(r2);更新所有节点路由信息(所有节点的路由信息都需要更新)的最坏复杂度为O(rn).现有的更新方式为flooding方式,更新1个路由信息的通信复杂度为O(nr).

组长时间复杂度即为组内路由算法复杂度,空间复杂度为路由表的存储和路由路径的存储.路由表最小为Lid,最大为(n-1)Lid.节点路由的平均和最坏时间复杂度都为O(n),路由表多入单出,边缘节点(处于网络拓扑边缘,不做中继的节点)的路由表为Lid,其他普通节点最小空间复杂度为2Lid,最大空间复杂度为nLid.路由路径的最坏空间复杂度为rLid.因此,边缘节点的空间复杂度为(r+1)×Lid,其他普通节点的最小空间复杂度为(r+2)Lid,最大为(r+n-1)Lid.

4.1.2组长决策复杂度

通信复杂度是节点决策通信复杂度的g倍;组长时间复杂度为2.1节所述组内路由算法的复杂度和路径处理的复杂度(复杂度为O(nCgr)),组长空间复杂度和第3节所述节点决策复杂度相同;节点路由的时间复杂度为O(1),边缘节点的空间复杂度为gLid,其他普通节点的最小空间复杂度为(g+1)×Lid,最大为(g+n)Lid.

4.2系统模拟

本节讨论引入RT约束引起的能量消耗.为了满足硬性时间约束,WSN能量损耗会有所增加,由于鲜有相关的工作,只讨论本文提出的2种机制的能量损耗表现.通过比较RT约束下SN的平均功耗与不考虑RT约束的对应值,机制的可用性可以得到检验.在不影响结果有效性的前提下,对WSN做如下假设:

①节点随机分布且所有节点是同构的(节点具有相同的通信模型和能量模型);

②所有节点同组,即网络仅有1个组长节点.

③MAC层、ND层和DJM层具有良好实现,只讨论活动节点.SN参数根据伯克利大学的Mica2设定,应用以森林防火为例,对一个边为50m的方形区域(组长位于左上角)的系统模拟.

图2中的曲线表示节点决策下SN平均功耗和无RT约束节能算法下SN平均功耗的比值.可以看出,在RT较小即跳步数较少的情况下,网络耗能会有较大变化.曲线下的方框代表RT级别为1时,组长决策的SN平均功耗和无RT约束的节能算法下SN平均功耗的比值.可以看出,组长决策优于节点决策路由(图中前者为9.5倍,后者为8.5倍).



图2节能路由算法和考虑响应时间约束的节能路由比较

总之,考虑RT约束必须更改路由,节点决策机制复杂度较低,但对应的功耗较大;组长决策功耗较小,但在组半径较大且响应级别数与组半径比值接近1/2时,时间复杂度较大.

5 结束语

本文细化了网络层架构,提出了考虑响应时间约束情况下的2种路由机制及其实现.通过分析可以得出,节点决策机制具有良好的时空复杂度和通信复杂度;在组半径较小或RT级别合理的前提下,组长决策路由时间复杂度比较理想.经过模拟可以看到,在RT约束下路由路径需要比较大的变化,这2种路由机制的能量消耗在RT合理的情况下都有较理想的效果.