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

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合理的情况下都有较理想的效果.