适合无线传感器网络的路由算法MSAODV

2011-06-09 14:13:02来源: 互联网

引言
   随着通信技术、嵌入式计算技术和传感器技术的飞速发展和日益成熟,具有感知能力、计算能力和通信能力的微型传感器开始在世界范围内出现。由这些微型传感器构成的传感器网络引起了人们的极大关注。这种传感器网络综合了传感器技术、嵌入式计算技术、分布式信息处理技术和通信技术,能够协作地实时监测、感知和采集网络分布区域内的各种环境或监测对象的信息,并对这些信息进行处理,获得详尽而准确的信息,传送到需要这些信息的用户。本文在AODV路由协议的基础上,提出了一种全新的路由协议—MSAODV协议,这种路由算法适合在微型无线传感器网络上使用。
2 MSAODV路由算法的基本思想与算法原理
  2.1 路由算法的基本思想
在研究了AODV路由协议之后,本文提出了一种全新的路由算法,这种路由算法适合在微型无线传感器网络上使用,又由于是基于AODV路由协议之上,故称之为MSAODV(Micro- Sensor Ad-hoc On-     Demand Distance Vector Algorithm)路由协议。
无线传感器网络与传统无线移动网络有区别,无线传感器网络最关心的是整个网络的成存周期,而传统无线移动网主要关心的是网络拓扑变化情况下可靠传输质量。微型无线传感器网络中的节点具有体积小,功耗小,通信距离短等特点,他们应用的场合非常广泛,像战场敌方信息采集,森林火灾监控等,这些场合往往是一些无人区,传感器节点抛撒到这些地方再回收的可能性非常小,所以节点的功耗决定了他的使用时间。针对这些特点,MSAODV路由算法采用了按需查询方式,他简单实用,易于扩充,协议开销小,应用了这种路由算法传感器节点大部分时间都可以处在睡眠状态,这样就延长了节点的使用时间,适合无线传感器网络的使用环境。
2.2 MSAODV路由算法原理
MSAODV路由协议算法是在AODV路由协议的基础上改进演化而来的,他继承了AODV路由算法的许多特点,但是又与AODV路由协议算法有所不同。无线传感器网络的体系结构将有助于设计MSAODV路由协议算法,图1显示了无线传感器网络的体系结构。
MSAODV路由算法同样假设网络中的所有链路都是双向对称的,即某个源节点通过一条路由可以到达无线网络中的某个目的节点时,该目的节点同样也可以通过这条路由的反向路由回到源节点。MSAODV路由协议同样是一种按需的距离向量路由协议,具有按需路由协议的特点,网络中的每个节点在需要进行通信时才发送路由分组,而不会周期性地交互路由信息以得到所有其它主机的路由:同时具有距离向量路由协议的一些特点,即各节点路由表只维护本节点到其他节点的路由,而无须掌握全网拓扑结构


 
图1 无线传感器网络体系结构
MSAODV路由协议中只有两种类型的消息控制帧:路由请求RREQ和路由应答RREP。和AODV路由协议一样,当源节点需要发送数据而又没有到目的节点的有效路由时,启动一个路由发现过程:向网络广播一个路由请求包RREQ,中间节点转发该路由请求,收到请求的目的节点以单播的方式向源节点返回一个RREP包,RREP沿着刚建立的逆向路径传输回源节点,源节点收到该RREP包后则开始向对应目的节点发送数据。在路由请求包的正向传播过程中,网络中能收到该路由请求的节点都建立起了到源节点的反向路由,当目的节点收到路由请求而回送路由应答时,逆向路径上的节点又建立了前向路由。整个MSAODV路由发现过程如图2所示,a图表示的是反向路由的建立过程,节点S需要和节点D通信,但是他没有节点D的路由,所以节点S发起到节点D的路由请求,节点S广播一个路由请求包,收到路由请求包的节点转发节点S的请求,最终节点D收到了节点S的路由请求包,这个过程建立了节点S到节点D的反向路由;b图表示的是由节点S到节点D前向路由的建立过程,当节点D收到节点S的路由请求包后,他要给节点S回送一个路由应答包,顺着刚才建立的反向路由,应答包最终被节点S成功接收,在此过程中节点S又建立了到节点D的前向路由。


 
图2 MSAODV路由建立过程

3 MSAODV路由中的路由表与协议帧的格式
3.1 MSAODV路由协议路由表
网络中的每一个节点都有这样的一个路由表,该表保存了对应节点的路由信息,由于各个节点在网络中的位置不同,因而他们的路由表项也不相同,例如在图2(b)中,a节点的路由表有两项,c节点的路由表也有两项,如表1所示。
表1 相关路由表

由于MSAODV路由协议是AODV路由协议的改进演化,所以与AODV路由协议帧类似,MSAODV路由协议也包括RR卫Q协议帧和RREP协议帧,但不包含RERR协议帧。不包含RERR协议帧会导致MSAODV协议在路由维护和错误处理上功能欠缺,但可以通过其他方法来弥补这个缺陷。
1 RREQ协议帧格式

 
 
2 RREP协议帧格式

 
4 MSAODV路由协议的操作
    由于MSAODV路由协议是对AODV协议的改进演化,所以MSAODV路由协议的操作与AODV路由协议的操作大同小异,为了清晰起见,对MSAODV协议的操作做一详细的介绍还是有必要的。
4.1产生路由请求
无线网络中某个节点需要和网络中的另一个节点通信时,他首先会查找自己的路由表,以确定是否有通往该目的节点的有效路由,如果有的话,从对应的目的节点路由表项中取出下一跳节点地址,然后构造数据包并把该数据包发往下一节点,如果不存在通往目的节点的路由,那么该节点就要发起一次路由请求。
4.2处理和转发路由请求
处理和转发路由请求是针对源节点和目的节点之间的中间节点而言。这些中间节点可能不止一个,在他们收到源节点广播的RREQ路由请求帧之后,必需处理和转发该路由请求帧。
在某个中间节点接收到源节点广播或者由其他节点转发的RREQ请求帧后,他首先会判定该RREQ请求帧是否己经被成功接收过,判断的依据就是源节点的IP地址和广播ID号,如果发现由源节点和广播ID唯一标志的RREQ请求帧是新的,也就是没收到过,就会根据此RREQ请求帧更新自己路由表中对应的项。很显然,该路由表项的目的节点IP字段就是是源节点IP地址,下一跳IP地址就是发送此RREQ请求帧的节点IP地址,有可能是源节点也有可能是另一个中间节点。接下来此中间节点判断该RREQ请求帧的目的IP是不是就是自己,如果是就回送一个RREP回应帧,不是就转发该RREQ请求帧。


4.3产生路由应答
RREQ经过中间节点的转发到达目的节点或者是直接到达目的节点后,目的节点要进行相应的处理。
目的节点收到RREQ请求包,首先会判断是否已经收到过此请求包,如果没有收到过则更新自己相应的路由表项,目的节点把该路由表项的目的IP更新为源节点的IP地址,下一跳IP为发给他RR卫Q请求帧的节点IP,目的节点序列号填上源节点的序列号,该序列号在RREQ请求帧里,跳数直接从RREQ请求帧里拷贝。在确认请求的节点就是自己后,目的节点要给源节点发送一个RREP应答帧,接下来目的节点构造一个RREP应答帧并正确初始化该帧。类型字段为2,表示该帧是RREP应答帧。跳数字段为0,因为是目的节点发起的RREP应答帧。目的节点产生一个RREP应答包之前,必需更新自己的序列号,更新值为当前序列号与RREQ请求包中的目的序列号两者中的最大值,目的序列号字段被初始化为这个最大值。源IP地址指的是发起RREQ请求帧的源节点的IP地址,而不是指目的节点的IP地址,同样的,目的IP地址就是目的节点的IP地址,也就是发起RREP应答帧的节点IP地址。
在目的节点构造好RREP回应帧后,就要把该帧以单播的形式沿着反向路由传送,他的下一跳节点IP地址是发给他RREQ请求帧的节点地址,可能是某个中间节点,也可能是源节点。一切准备就绪,目的节点按照退避算法发送该帧。
4.4接收和转发路由应答
由于无线网络的特点,尽管目的节点是以单播的形式向源节点回送RREP回应帧,但是网络中的很多节点也能接收到该帧,当然,这些节点只是简单的丢弃该帧,只有反向路由上的节点才会接收该RREP回应帧。反向路由上的节点会沿着反向路由顺利的把RREP回应帧传给源节点,同时他们也根据此RREP回应帧建立了前向路由。该节点下面要完成的工作就是把该RREP回应帧转发出去。他要知道下一跳节点的IP地址,以RREP回应帧中的源节点IP地址为关键字查找路由表,得到下一跳节点的IP,这个表项是在建立反向路由时建立或更新的。该中间节点在完成上面的步骤后,以退避算法转发该RREP回应帧。与RREQ请求帧的转发不同,R.REP回应帧的转发是单播的,他不会像R.REQ请求帧那样可能被转发多次,所以R.REP回应帧的字段里不存在广播ID。
4.5新节点加入
无线传感器网络中的节点在开机或重启之后,会向网络广播一个RESET消息,网络中的其他节点收到此RESET消息后会转发该帧,最后主节点收到该帧。新节点在RESET消息帧里携带自己的IP地址,这样当主节点收到该帧后就可以知道是哪个节点重启。
收到RESET消息帧的其他节点首先查找自己的路由表看是否有主节点的IP地址,如果有就以单播的形式发送该帧,反之则继续广播此RESET消息帧。每个节点都要保存上一次他收到的RESET消息帧中的源节点IP地址,下次再收到RESET消息帧首先要比较源IP地址是否和保存值相同,相同就不再转发该帧,在经过一段时间后,将保存值清零,这样就避免了重复转发同一个RESET消息帧,又避免了不再转发下次的RESET消息帧。
4.6其他操作
除了前文描述的产生路由请求、处理和转发路由请求、产生路由应答、接收和转发路由应答、新节点加入等主要操作外,MSAODV路由算法余下的操作可以参考第二章介绍的AODV路由算法。
5 本文作者创新点
AODV路由算法应用在无线传感器网络中有一定的局限性,不能很好得适合无线传感器网络的体系结构。以无线传感器网络与传统移动无线网着重点不同为依据,本文提出了适合无线传感器网络的路由算法MSAODV,并详细叙述分析了MSAODV路由算法。

关键字:适合  无线  传感器网络

编辑:eeleader 引用地址:http://www.eeworld.com.cn/gykz/2011/0609/article_6503.html
本网站转载的所有的文章、图片、音频视频文件等资料的版权归版权所有人所有,本站采用的非本站原创文章及图片等内容无法一一联系确认版权者。如果本网所选内容的文章作者及编辑认为其作品不宜公开自由传播,或不应无偿使用,请及时通过电子邮件或电话通知我们,以迅速采取适当措施,避免给双方造成不必要的经济损失。
论坛活动 E手掌握
微信扫一扫加关注
论坛活动 E手掌握
芯片资讯 锐利解读
微信扫一扫加关注
芯片资讯 锐利解读
推荐阅读
全部
适合
无线
传感器网络

小广播

独家专题更多

富士通铁电随机存储器FRAM主题展馆
富士通铁电随机存储器FRAM主题展馆
馆内包含了 纵览FRAM、独立FRAM存储器专区、FRAM内置LSI专区三大部分内容。 
走,跟Molex一起去看《中国电子消费品趋势》!
走,跟Molex一起去看《中国电子消费品趋势》!
 
带你走进LED王国——Microchip LED应用专题
带你走进LED王国——Microchip LED应用专题
 
电子工程世界版权所有 京ICP证060456号 京ICP备10001474号 电信业务审批[2006]字第258号函 京公海网安备110108001534 Copyright © 2005-2016 EEWORLD.com.cn, Inc. All rights reserved