论文部分内容阅读
摘 要 Ad hoc网络分级路由协议中，一般采用分簇思想，传统方式上没有考虑热门节点较其它节点能量耗费快，容易造成因簇头和网关寿命终结引起整个簇网络寿命终结的问题。本文在CGSR路由协议的基础上，从优化路由方式出发，通过路由优化实现了路由发现和路由传输的分离，减少了簇头和网关的能量消耗，ns2仿真实验表明，该方法有效的延长了网络寿命。
关键词 Ad hoc 边界路由 能量消耗
一、引言
在分级结构的Ad Hoc无线网络拓扑结构中[2]，整个网络是以簇为子网组成，每个簇由一个簇头和多个簇成员组成，其中簇头形成高一级网络。每一个簇中的簇头和簇成员是动态变化的，能够自动组网。目前比较广泛使用的分级路由协议是CGSR，但CGSR存在以下缺点[71]：
簇间通信必须经过簇头和网关，增加了簇头和网关的压力，造成能量消耗太快。
本文对在CGSR路由协议进行改进。在CGSR的基础上去除了传统方式只有一个网关的限制，采用所有边界节点做为网关参与通信的方式进行簇间路由，减少了网关的压力。
二、路由改进
（一）簇内路由
把路由上节点的开销与剩余电池能量相关的函数之和作为路由选择的量度，选择的路由是路径上各节点开销之和最小的路由。设节点的电池剩余能量为，定义为节点的电池开销函数。可以定义为：
（2.1）
随着电池能量的下降，节点的开销函数的值将增大。设有路由其中是源节点，是目的节点，定义路由的电池开销为：
（2.2）
那么，最小电池开销路由满足： （2.3）
式中，A是所有以為源节点，为目的节点的可能路由组成的集合。
选择一条节点电池费用之和最小的路由作为最佳路由，这样就可以使建立的路径中包含剩余能量较多的节点。最小电池开销路由直接用到电池电量量度，防止了节点的过度使用，延长了节点寿命，选择的路由尽量避开了低电节点，推迟了网络分割时间。
簇内节点间采用先验式路由方式，最短路径不再是依据最小跳数，是依据电池最小开销进行路由计算：每个节点保存一个簇成员表和路由选择表，簇成员表记录网络中每个节点的簇头并周期广播更新；路由选择表为每个簇保存一条表项并记录通往该簇头的下一条节点。由于采用了电池最小开销为依据，簇头和边界节点一般比较活跃且能耗大，导致剩余能量相对较少从而参与簇内路由的意愿减小，所以簇头和边界节点在一定程度上避免了参与簇内路由。
（二）簇间路由以及边界节点选取
簇间仍然采用最小电池耗费路由。簇内一个节点向另一簇内节点发送信息时：
第1步，节点向簇头发送一个带源节点和目的节点的IP地址请求包REQ，簇头在群成员表中找到目的节点所在群，并在路由表中找到通往目的节点的下一相邻簇头，以及通往相邻簇头的所有边界节点。比较得到的所有边界节点参与路由的意愿，选取意愿最大的节点做为下一跳，然后把这一相邻簇头和目的节点加入RREQ发往该边界节点。
第2步，若边界节点已经在相邻簇中，去掉REQ中簇头后把自己加入到REQ中，重复步骤1；否则，边界节点在自己的路由表中找到通往相邻簇头的所有边界节点，比较这些边界节点参与路由的意愿，选取意愿最大的节点做为下一跳，发送REQ到该节点，该节点接收并把自己添加到REQ中，重复步骤2直到目的节点。
第3步，目的节点收到REQ消息后，根据REQ发送应答消息REPLY。由于REQ中只包含源节点、目的节点、和经过的边界节点，所以应答消息REPLY返回路径不经过簇头节点，边界节点根据本地路由表直接发送。
假设c节点要与s节点和l节点进行通信，如图1所示。
如果采用传统的CGSR路由算法采用的路由：
在c与s通信路由为cbdefprs，c与l通信路由为cbdel。由图可以看出簇间通信都要经过簇头节点b、e、r和网关节点d、f、p，造成簇头和网关节点压力过大能量消耗过快。
如果采用改进的CGSR路由方式，依据上面的叙述：
节点c发送REQ请求的路径为cbdefprs但REQ内记录的节点只有d、f、p、s节点，d、f、p、s节点间采用簇内路由的方式路由，所以REPLY的返回路径为sqpftdac，与REQ相比我没有经过r、e、b节点，而r、e、b节点都是簇头节点，通过这种方式实现了簇间采用路由发现与实际路由相分离的方式，实现了簇头只用于路由发现，而不进行实际路由，减小了簇头和网关的压力，减小了能量消耗速度。同理，c与l通信的路由为cdl。解决了簇头和网关节点能量消耗过快的问题
三、仿真分析
本文基于NS2网络模拟器对改进协议进行仿真分析。具体实验条件为：群半径r=5，节点传输范围为250 m，节点运动模型采用Random Way Point模型。MAC层采用IEEE802.11MAC协议。实验结果如图所示。
在图2的上半部分，给出了50个节点随机分布在1000m×1000m的区域内，节点以10m/s速度移动，新旧两种协议节点能耗和网络生命周期情况。在图2的下半部分，给出了100个节点下两种协议的仿真结果。
从图中可以看出，节点数越多，新协议的能量消耗相对越少。
图2节点变化下的能量对比
四、结论
移动自组网的节能路由协议已成为目前的研究热点之一，本文提出的协议，在保留了CGSR协议建立路由速度快等优点基础上，通过均衡各节点能量，避免了因关键的几个耗能快节点耗完能量而造成的整个网络瘫痪，较好地解决了目前分群协议中网关和簇头能耗过快的问题。通过仿真分析比较， 该协议有效地延长网络寿命。
参考文献：
[1]陈维华，贾智平.基于CGSR的改进型AdHoc路由协议[J].计算机应用，2009，29（1）：32-33.
[2] Nithyanandan L，Sivarajesh G.Modified GPSR protocol for Wireless Sensor Networks[J].International Journal of Computer and Electrical Engineering，2010，2（2）：324-328.
[3]刘宇，赵志军，沈强，唐晖. 能量感知的GPSR动态路由负载均衡[J]. 计算机工程与应用，2011，47（6）：23-25.
作者简介：
方承志，男，汉族，1976.10—，湖南安化人，南京邮电大学电子科学与工程学院，博士，讲师，从事电路和信号处理研究。
关键词 Ad hoc 边界路由 能量消耗
一、引言
在分级结构的Ad Hoc无线网络拓扑结构中[2]，整个网络是以簇为子网组成，每个簇由一个簇头和多个簇成员组成，其中簇头形成高一级网络。每一个簇中的簇头和簇成员是动态变化的，能够自动组网。目前比较广泛使用的分级路由协议是CGSR，但CGSR存在以下缺点[71]：
簇间通信必须经过簇头和网关，增加了簇头和网关的压力，造成能量消耗太快。
本文对在CGSR路由协议进行改进。在CGSR的基础上去除了传统方式只有一个网关的限制，采用所有边界节点做为网关参与通信的方式进行簇间路由，减少了网关的压力。
二、路由改进
（一）簇内路由
把路由上节点的开销与剩余电池能量相关的函数之和作为路由选择的量度，选择的路由是路径上各节点开销之和最小的路由。设节点的电池剩余能量为，定义为节点的电池开销函数。可以定义为：
（2.1）
随着电池能量的下降，节点的开销函数的值将增大。设有路由其中是源节点，是目的节点，定义路由的电池开销为：
（2.2）
那么，最小电池开销路由满足： （2.3）
式中，A是所有以為源节点，为目的节点的可能路由组成的集合。
选择一条节点电池费用之和最小的路由作为最佳路由，这样就可以使建立的路径中包含剩余能量较多的节点。最小电池开销路由直接用到电池电量量度，防止了节点的过度使用，延长了节点寿命，选择的路由尽量避开了低电节点，推迟了网络分割时间。
簇内节点间采用先验式路由方式，最短路径不再是依据最小跳数，是依据电池最小开销进行路由计算：每个节点保存一个簇成员表和路由选择表，簇成员表记录网络中每个节点的簇头并周期广播更新；路由选择表为每个簇保存一条表项并记录通往该簇头的下一条节点。由于采用了电池最小开销为依据，簇头和边界节点一般比较活跃且能耗大，导致剩余能量相对较少从而参与簇内路由的意愿减小，所以簇头和边界节点在一定程度上避免了参与簇内路由。
（二）簇间路由以及边界节点选取
簇间仍然采用最小电池耗费路由。簇内一个节点向另一簇内节点发送信息时：
第1步，节点向簇头发送一个带源节点和目的节点的IP地址请求包REQ，簇头在群成员表中找到目的节点所在群，并在路由表中找到通往目的节点的下一相邻簇头，以及通往相邻簇头的所有边界节点。比较得到的所有边界节点参与路由的意愿，选取意愿最大的节点做为下一跳，然后把这一相邻簇头和目的节点加入RREQ发往该边界节点。
第2步，若边界节点已经在相邻簇中，去掉REQ中簇头后把自己加入到REQ中，重复步骤1；否则，边界节点在自己的路由表中找到通往相邻簇头的所有边界节点，比较这些边界节点参与路由的意愿，选取意愿最大的节点做为下一跳，发送REQ到该节点，该节点接收并把自己添加到REQ中，重复步骤2直到目的节点。
第3步，目的节点收到REQ消息后，根据REQ发送应答消息REPLY。由于REQ中只包含源节点、目的节点、和经过的边界节点，所以应答消息REPLY返回路径不经过簇头节点，边界节点根据本地路由表直接发送。
假设c节点要与s节点和l节点进行通信，如图1所示。
如果采用传统的CGSR路由算法采用的路由：
在c与s通信路由为cbdefprs，c与l通信路由为cbdel。由图可以看出簇间通信都要经过簇头节点b、e、r和网关节点d、f、p，造成簇头和网关节点压力过大能量消耗过快。
如果采用改进的CGSR路由方式，依据上面的叙述：
节点c发送REQ请求的路径为cbdefprs但REQ内记录的节点只有d、f、p、s节点，d、f、p、s节点间采用簇内路由的方式路由，所以REPLY的返回路径为sqpftdac，与REQ相比我没有经过r、e、b节点，而r、e、b节点都是簇头节点，通过这种方式实现了簇间采用路由发现与实际路由相分离的方式，实现了簇头只用于路由发现，而不进行实际路由，减小了簇头和网关的压力，减小了能量消耗速度。同理，c与l通信的路由为cdl。解决了簇头和网关节点能量消耗过快的问题
三、仿真分析
本文基于NS2网络模拟器对改进协议进行仿真分析。具体实验条件为：群半径r=5，节点传输范围为250 m，节点运动模型采用Random Way Point模型。MAC层采用IEEE802.11MAC协议。实验结果如图所示。
在图2的上半部分，给出了50个节点随机分布在1000m×1000m的区域内，节点以10m/s速度移动，新旧两种协议节点能耗和网络生命周期情况。在图2的下半部分，给出了100个节点下两种协议的仿真结果。
从图中可以看出，节点数越多，新协议的能量消耗相对越少。
图2节点变化下的能量对比
四、结论
移动自组网的节能路由协议已成为目前的研究热点之一，本文提出的协议，在保留了CGSR协议建立路由速度快等优点基础上，通过均衡各节点能量，避免了因关键的几个耗能快节点耗完能量而造成的整个网络瘫痪，较好地解决了目前分群协议中网关和簇头能耗过快的问题。通过仿真分析比较， 该协议有效地延长网络寿命。
参考文献：
[1]陈维华，贾智平.基于CGSR的改进型AdHoc路由协议[J].计算机应用，2009，29（1）：32-33.
[2] Nithyanandan L，Sivarajesh G.Modified GPSR protocol for Wireless Sensor Networks[J].International Journal of Computer and Electrical Engineering，2010，2（2）：324-328.
[3]刘宇，赵志军，沈强，唐晖. 能量感知的GPSR动态路由负载均衡[J]. 计算机工程与应用，2011，47（6）：23-25.
作者简介：
方承志，男，汉族，1976.10—，湖南安化人，南京邮电大学电子科学与工程学院，博士，讲师，从事电路和信号处理研究。