基于CGSR的改进型AdHoc路由协议.pdf

《基于CGSR的改进型AdHoc路由协议.pdf》由会员分享，可在线阅读，更多相关《基于CGSR的改进型AdHoc路由协议.pdf（3页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、?收稿日期:2008-07-28;修回日期:2008-09-28。?基金项目:国家自然科学基金资助项目(NSFC90718032)。?作者简介:陈维华(1981-),男,江苏宜兴人,硕士研究生,主要研究方向:嵌入式系统、无线网络;?贾智平(1964-),男,山东济南人,教授,主要研究方向:嵌入式系统。文章编号:1001-9081(2009)01-0032-02基于 CGSR的改进型 AdHoc路由协议陈维华,贾智平(山东大学 计算机科学与技术学院,济南 250101)(redaroma mai.l )摘?要:通过对 AdHoc网络分群路由协议的研究,从平衡节点能量消耗和增加网络生命周期角度出发

2、,提出了CGSR的改进型路由协议 CBSR。CBSR通过减少信息转发次数,有效地减少了能量消耗。使用群首能量限制降低了因群首能量消耗过快对网络整体寿命的影响。通过 NS?2仿真实验,论证了改进后的协议具有更长的生命周期。关键词:AdHoc网络;能量均衡;生命周期;CGSR中图分类号:TP393.17?文献标志码:ANew Ad Hoc routing protocol based on CGSRCHENW ei?hua,JI A Zhi?ping(School of Computer Science and T echnology,Shandong University,Jinan Shand

3、ong 250101,China)Abstract:Based on the research on the clustered Ad Hoc routing protocols,this paper proposed to i mprove CGSRprotocolunder the conditions of balanced energy consumption and prolonged lifeti me.Energy consumption was reduced bycutting down themessage transm ition.Energy restriction o

4、fClusterhead reduced the i mpact of excessive energy consumption onthe network life.NS?2 si mulation results indicate the lifeti me of network increaseswhen ne w protocolCBSR is used.Keywords:AdHoc network;energy balance;lifeti me;Clusterhead Gateway Sw itch Routing(CGSR)?移动 AdHoc网络是一种特殊的无线网络,它不需要基础

5、网络设施的支持,网络中的节点兼有主机和路由器的功能,它是一种具有高度动态拓扑结构、节点可自由移动的自组织网络。AdHoc网络通常以电池供电,能量非常有限,如果网络中的某些节点能量消耗过快,则会使节点在短时间内失效,从而导致有效传感区域变小,影响传输效果。因此在 AdHoc网络中,能量比带宽等其他性能指标更重要。如何有效减少并平衡网络中各个节点的能量消耗,从而使得网络生命周期最大化,是 AdHoc路由协议尤其是大规模无线传感网络路由协议设计的关键之一。本文是基于无线网络分群路由协议栈的特点,提出了 CGSR 1-2的改进路由协议。在新协议中采用边界节点思想,优化了路由策略,使得网络能耗负载更加均

6、衡,从而达到延长网络生存期的目的。1?分群路由协议按照网络结构分类,传统 AdHoc可以分为平面结构和分级结构 2-3。平面结构只适用于小规模网络,大型网络使用分级结构。目前比较广泛使用的分级路由协议主要有 CGSR(Clusterhead Gateway SwitchRouting)、ZRP2,4和 LEACH 5协议。CGSR是以 DSDV 1-2,6为基础 的先应式路由协议,在CGSR网络模型中,网络被划分为重叠的群,每个群通过群首选择 算法选 出一 个群首。每个 节点 保存 一个群 成员 表(clustermember table)和路由选择表(routing table),前者记录网

7、络中每个节点的群首并周期广播更新;后者为每个群保存一条表项,记录通往该群首的下一条节点。处于两个以上群首通信范围内的节点为网关节点,群首必须通过网关实现通信。图 1给出了 CGSR的一个路由实例。ZRP协议使用分群思想,但不产生群首,群内使用先应式路由协议,群间使用按需路由方式。LEACH 协议也使用群首和网关来交互信息,并且使用动态方式来选举群首。以上三种协议各自有本身的优缺点,CGSR 协议响应速度快,但先应式路由协议开销大。ZRP结合了先应式和按需路由的优点,但群间路由建立速度慢,并且建立路由使用泛洪方式,能耗大。LEACH 协议通过轮换随机选举群首,均衡中继通信的业务量,但协议中节点以

8、相同概率竞争群首,缺乏对能量等因素考虑,并且必须保证所有节点都能够与网关节点直接通信。另外 CGSR和 LEACH群间信息必须使用群首和网关传送,加大了群首和网关负载,同时产生的路由不一定是最优。图 1?CGSR 路由实例针对上面目前分群路由协议的问题,本文结合 CGSR 特点,综合考虑群首和网关负载以及节点能耗情况,提出了改进的路由协议 CBSR(Clusterhead Border Switch Routing)。2?CBSR2.1?节点类型在 CGSR中,由于消息必须经过网关转发,使得在相互通信范围之内的相邻但不相交的群之间消息必须经过其他群转发,增加了路由的能耗。为了减少网关节点负载,

9、在 CBSR 协第 29卷第 1期2009年 1月?计算机应用Journal of ComputerApplications?Vo.l 29 No.1Jan.2009议中提出了使用边界节点代替网关。定义 1?对于一个群 A,它的边界节点指那些至少有一个不在群 A 的邻居节点的节点。由定义可知网关节点一定是边界节点,但边界节点不一定是网关节点。新协议中可以通过边界节点直接通信来减少信息转发次数,节省能量。CBSR 协议中,群首保存的路由选择表不再是保存到其他群首路由的下一跳节点,而是保存去目的节点的下一相邻群首节点和到达相邻群首的边界节点,边界节点仅保存到自己所在群内所有节点的路由以及相邻群邻居

10、节点对应的群首,普通节点保存本群节点信息和群内路由。2.2?路由选择2.2.1?群内路由可以根据本地路由表直接发送,群内节点的路由应尽量避免经过群首和边界节点,而减少群首和边界节点的负担。具体做法:群内路由使用 D ijkstra算法,以节点跳数作为路径长度(因为节点接受发射功率是恒定的)。在路由经过群首或边界节点时额外增加 4跳,由于分群算法中群内节点距离最长不超过 5跳,这样经过群首或边界的路径一定是最长路径,仅当没有其他路径时才被选用。2.2.2?群间路由一个普通节点发送消息到其他群节点的步骤:第 1步?节点向群首发送一个带源节点和目的节点地址的请求包 REQ。第 2步?如果目的节点在本

11、群中,则直接通过本地路由把 REQ发送给目的节点。否则群首在群成员表中找到目的节点所在群,并在路由表中找到通往目的节点的下一相邻群首,以及通往相邻群首的边界节点。然后把这一相邻群首和目的节点加入 REQ发往该边界节点。第 3步?若边界节点已经在相邻群中,去掉 REQ 中群首,把自己加入 REQ 中,并发送到这一群首,群首重复第 2步。否则边界节点在自己路由表中找到通往相邻群首的边界节点,把自己添加到 REQ 并发送到相邻群的边界节点。然后重复第 3步。第 4步?目的节点根据收到的 REQ消息(REQ 中仅包含源节点、目的节点和经过的边界节点)后,根据 REQ 发送应答消息 REPLY。每个边界

12、节点可以根据 REQ通过本地路由表直接发送。第 5步?源节点收到 REPLY后,将沿着 REPLY 发送信息。在图 2中,节点 a发送消息到 y,REQ 实际经过的路径是adbfgjxrsy。目的节点 y收到的 REQ 信息为 afjxy。然后 y可以根据本地路由表将 REPLY 发送给 x,同样 x发送给 j,j发送给f,f发到源节点 a建立实际信息发送路由 adfikjxsy,消息实际只经过一个群转发。消息经过的节点比图 1中少,且群首节点参与消息转发次数也减少。2.3?群首选择CGSR协 议使 用 最少 分 群改 变 算法 7(Least ClusterChange,LCC),该算法并没

13、有考虑群首节点能量情况对整个网络生命周期的影响。在 CBSR中,设置群首能量底限来防止群首能量过度使用而失效。群首自身能量到达能量底限时,自动发送群首选择消息,重新选择群首。在 CBSR 中,将群首能量底限设为该节点被选为群首时能量的三分之一。用式(1)计算出群首平均能量消耗速度:Eavg=2Es3(Ts-Te)(1)其中:Es,Te表示当前群首被选为群首时能量和时间,Ts表示当前时间。群内节点根据自身平均能量消耗和群首能量消耗情况估算出自己可担任群首的时间,并把结果返回给群首。假设 i节点的邻节点集合为Ni,eij为发送单位数据到起邻节点耗费的能量。kij为节点 i到 j的数据流。那么节点

14、i发送数据总能耗 Ei可用式(2)计算:Ei=?j Nieijkij(2)那么节点 i可以担任群首的时间 Ti如下:Ti=23Eic-EiEavg=2Eic-3Ei3Eavg(3)其中 Eic表示节点当前能量。群首根据返回的消息选择 Ti值最大的节点作为下一个群首,广播消息并将群成员表和路由表发给新群首。图 2?CBSR 路由实例3?仿真实验本文基于 NS?2网络模拟器对改进协议进行仿真分析。具体实验条件为:群半径 r=4,节点传输范围为 250m,节点运动模型采用 Random W ay Point模型。MAC 层采用 IEEE802.11 MAC协议。节点以常速(CBR)发送数据,产生 U

15、DP数据包速率是 10 packet/s,每个数据包有 512 B。对相同的场景模式分别运行改进前后协议,在两次模拟实验中,信息发送起始时刻,源节点和目的节点以及数据包数量都相同,这样保证了两次试验在网络断裂之前同一时刻吞吐量一致。实验运行到数据发送失败停止。实验结果如图 3 5所示。图 3给出了 50个节点随机分布在 1000m!1000m的区域内,节点以 10m/s速度移动,新旧两种协议节点能耗和网络生命周期情况。图中可以看出改进的协议并没有表现出明显的优势,那是因为节点少的情况下,群数量较少,群首节点传输的信息相对较少,所以两种协议群首耗能情况相差不大。图 3?50节点生命周期比较图 4

16、给出了 100个节点在 2000m!2000m区域内,节点以 10m/s速度移动,两种协议仿真结果。可以看出在同一时刻,新协议消耗完能量的节点数明显要少,而且网络生命周期也延长了 8.3 s。(下转第 53页)?33第 1期陈维华等:基于 CGSR的改进型 AdH oc路由协议?A,B,C三点为动态聚类后的代表点,但是 C点为中心的区域明显与人体目标模板不匹配,因此仅有 A、B两点为合理代表点。图 3?动态聚焦后代表点4?实验及结果分析实验选用了 PETS 2006数据库,该数据库是由英国公共安全部门提供的,设置于地铁的监控设备所录制的真实场景。实验选取了 PETS 2006的 Databas

17、e S1中的场景 3,每 10帧取一帧,共获取 224帧图像,对 224帧图像进行预处理,从中分离出运动区域,根据运动区域中的粘连人体数量进行人工分类,应用本文所提算法分别进行分割(如表 1所示)。根据实验结果可以看出,本文所提方法可以有效地分割粘连人体目标。特别是对于粘连人体数量较少的运动区域,分割效果更好。但是从实验过程也可以发现,本方法的最终结果依赖于图像预处理的效果,不太适合应用于光线变化较大的室外场所。而且当人体发生相互重叠时,分割效果不好。但是,该方法具有一定局限性。在下一阶段的工作中,将重点研究提高本方法的鲁棒性,以求使其更具实用价值。表 1?试验结果粘连人数样本数正确样本数正确

18、率/%2766788.23433479.04272074.04人以上13969.0总计15913081.7参考文献:1?DO Y.Region based detection of occluded people for the tracking invideo i mage sequencesC/ComputerAnalysis of I mages and Pat?terns.Rocquencourt,France:Springer Press,2005:829-836.2?CHEN THOU?HO,HSU CHE?WEI.An automatic bi?directionalpassin

19、g?people counting method based on color i mage processing C/International Carnahan Conference on Security Technology.T aipe,i T ai wan:Springer Press,2003:200-207.3?BATISTA J P.T racking pedestrians under occlusion using multiplecameras C/The International Conference on I mage Analysis andRecognitio

20、n.Porto,Portuga:l SpringerPress,2004:552-562.4?陈卓夷.基于非参数密度估计聚类的关键帧提取方法 J.计算机科学,2007,34(4):119-162.5?宋新,罗军,王鲁平,等.基于 M ean Shift聚类的边缘检测方法 J.弹箭与制导学报,2007,27(1):366-368.(上接第 33页)?图 5给出了 100个节点在 2 000 m!2000m 区域内以20m/s 随机运动时,两种协议运行结果,从图 5可以看出,新协议网络生命周期延长了 5.7 s。这表明在节点运动速度加快时,新协议仍然具有相当优势。表 1给出了几次仿真综合比较。可以

21、看出,使用 CBSR协议后,第一节点失效时间延后,网络生命周期也明显增加。4?结语AdHoc网络中单个节点能量消耗和网络生命周期是一对相互制约的因素。本文提出的 CBSR 协议,在保留了 CGSR协议建立路由速度快等优点基础上,较好地解决了目前分群协议中网关和群首能耗过快的问题。通过实验分析比较,该协议有效地延长网络寿命。表 1?协议运行结果比较节点数第一节点失效时间CGSRCBSR生命周期CGSRCBSR5033.125.278.980.0100(10m/s)18.526.166.374.6100(20m/s)16.820.559.465.1参考文献:1?ROYER E M,TOH C K.

22、A review of current routing protocols forAdHocmobile wireless networks J.IEEE Personal Communica?tions.1999,6(2):46-55.2?史美林,英春.自组网路由协议综述 J.通信学报.2001,22(11):93-103.3?BACHIR A,BARTHEL D.Localized max?m in remaining energyrouting forWSN using delay contro l C/I CC 2005:I EEE Interna?tional Conference

23、on Communications.S.l:I EEE Press,2005,5:3302-3306.4?HASS Z J,PEARLMAN M R.The perfor mance of query controlscheme for the zone routing protocolC /ACM SI GCOMM 98 C.Canada:AC M Press,1998:167-177.5?孙利民,李建中,陈渝,等.无线传感器网络 M.北京:清华大学出版社,2005.6?PERK I NS C E,B HAGWAT P.H ighly dynam ic destination?sequenc

24、ed distance?vector routing(DSDV)for mobile computersC/Proceedings of SI GCOMM?94.N ew York:ACM Press,1994:234-244.7?CHI ANG C C,WU H K,LI U W,et al.Routing in clusteredmulti?hopmobile wireless net works with fading channel C/ProceedingI EEE Sicon?97.Singapore:I EEE Press,1997:197-211.53第 1期郭森等:基于 M ean?shift的粘连人体目标分割算法?