时间:2022-10-21 11:11:48
导语:在路由协议的撰写旅程中,学习并吸收他人佳作的精髓是一条宝贵的路径,好期刊汇集了九篇优秀范文,愿这些内容能够启发您的创作灵感,引领您探索更多的创作可能。
关键词:物联网;无线传感器网络;路由协议;能源利用率
中图分类号:TP393 文献标识码:A 文章编号:2095-1302(2016)03-00-04
0 引 言
无线传感器网络(Wireless Sensor Networks, WSN)作为物联网的重要组成部分,具有广阔的应用前景[1]。传统网络主要应用于用户间的数据通信和资源共享, 相比之下,WSN应用范围更加广泛,例如环境监测、敌情侦查等。对于WSN路由协议,应用场景的不同会导致它们之间存在某些差异。本文主要从原理、特点以及优缺点三个方面对目前具有代表性的WSN路由协议进行分析,并对其特性进行归纳总结。
根据WSN中传感器节点的特性以及节点间数据传输的特征,可以将WSN路由协议分为以数据为中心的路由、层次路由、地理位置路由以及基于网络流量和服务质量的路由[2]。
1 以数据为中心的路由
传统网络中的路由协议通常是通过地址找到相对应的资源,即以地址为中心;而对于WSN,传感器节点的部署却无规律。在这种情况下,节点的具体编号对用户来说并不重要,用户只需要得到融合后的、有价值的数据即可,即WSN主要以数据为中心。以数据为中心的路由协议包括Flooding、Gossiping、SPIN、Directed Diffusion和Rumor。
1.1 Flooding路由协议
Flooding协议(洪泛路由协议)是一种传统的广播式路由协议[3]。当环境中的某一传感器节点监测或接收到数据时,无条件的将数据转发给自己的邻居节点。Flooding协议原理如图1所示。
Flooding协议最突出的特点在于节点对数据进行“无条件转发”,直到数据传遍整个网络或是达到规定的跳数上限为止。这一特点使得该协议容易实现,并且能较好地适应网络拓扑结构的改变。因此,它具有较强的鲁棒性,可以应用于军事领域或者恶劣环境。但该特点也给Flooding协议带来了一个致命的弱点,即信息爆炸问题。图1中同一个数据包被3次发送给E节点,这对于E节点来说,极大地浪费了能量。图2所示为其重叠问题示意图,其中深色部分为A、B节点所能感知到的区域的重叠部分,如果重叠区域有事件发生,那么该事件信息将被发送给C节点两次。重叠问题普遍存在而且很难避免,并且会随着节点分布密集程度的增大而变得愈发严重。
目前来讲,Flooding协议过于浪费网络资源和节点能量,因此很少被直接运用,一般将其作为衡量标准去评价其他路由算法。
1.2 Gossiping路由协议
Gossiping协议在Flooding协议的基础上演变而来。改进之处在于数据包被随机转发给某几个相邻节点,并非所有相邻节点,这可以在一定程度上控制信息内爆问题。但是由于节点转发数据包时随机选取的相邻节点可能并不是所有相邻节点里面距离该节点较近的几个点,很可能使得数据到达目的节点的时延增大,或是出现跳数已达最大但数据仍未传送到目的节点所导致的信息传送失败问题。
1.3 SPIN路由协议
SPIN(Sensor Protocol for Information via Negotiation)协议基于Flooding协议,改进之处在于节点之间通过协商(Negotiation)的方式缓解数据冗余问题。该协议包含以下三种数据包类型: 消息广播包(ADV)、 数据请求包(REQ)和数据包(DATA)。
图3所示为SPIN协议原理,其中S节点有新数据时则向其所有相邻节点ADV消息,假设A和C有该数据,则它们不回复给S任何消息;假设B没有该数据,则B需要回复REQ数据包,S收到REQ数据包后将原始数据DATA发送给B节点。B接收到DATA后与自己的数据进行融合并对B的相邻节点重复该过程。
该路由协议的核心基于元数据(Metadata)的协商(Negotiation)过程。协议中采用“三次握手”机制,即节点只对回复REQ信息的节点发送原始数据,这相比给所有相邻节点发送原始数据而言,大大减少了冗余数据的传输。
该协议仍然有一些不足之处。若某一个节点收到多个相邻节点的REQ消息,这时需采用“退避算法”,该方法可能会增加时延,也可能会有某些节点对许多消息都“感兴趣”,那么它将接收大量数据,这些节点的能量容易耗尽。
1.4 DD路由协议
DD协议(Directed Diffusion定向扩散路由协议)中路径的建立过程需要经历以下三个阶段:
(1)“兴趣扩散”阶段,汇聚节点(Sink)采用周期性洪泛方式广播自己的“兴趣”,即自己要接收何种类型的消息;
(2)“梯度建立”阶段,兴趣扩散路径即为数据传输路径,只是传输方向相反;
(3)“强化路径”阶段,即从“梯度建立”阶段所得到的路径中选取合适路径进行数据传输。
DD协议实现过程如图4所示。
当加强路径中的某一段出现故障时,原加强路径上的节点会启动新的加强过程,从而建立新的加强路径。“加强路径”的修复如图5所示。
DD协议中路径加强机制可以显著提高数据的传输速率,但加强路径上的节点会消耗大量能量,为了确保能量均衡消耗,需要周期性替换加强路径,这将增加网络维护的难度。当某一加强路径出现故障并且暂未更新加强路径时,多次失败的发送过程也会增大端到端时延并耗费部分节点的能量[4]。
1.5 Rumor路由协议
对于某些节点较少、需要传输的数据量较少或是已知事件发生区域的WSN来说,运用上面提及的几种路由协议将会带来一些不必要的开销。Rumor协议(谣传路由协议)能够在一定程度上缓解这种问题,减少网络中的冗余数据量。该协议中引入(Agent)消息概念,消息由感知到信息的传感器节点产生[5]。Sink节点产生查询消息、源节点产生消息,两者均在网络中随机传播,到两者传播路径出现交点为止,即构成一条完整的数据传输路径。Rumor路由协议原理如图6所示,实线为消息传播路径,虚线为查询消息传播路径,两条路径在B点处会合,从而形成一条完整的传输线路。
Rumor协议使用单播随机转发方式能够在一定程度上减少网络的开销,但由于每个传感器节点需要维护的列表数目增加了,维护的难度也就增大了。协议中采用的随机转发方式无法保证数据传输的路径是最短路径,因此无法保证数据传输的时效性,并且容易出现环路。
2 层次路由
层次路由也叫集群结构路由,它通过引入簇的概念实现网络内节点的分层管理。簇头和簇成员各司其职,共同完成数据的传输。
2.1 LEACH协议
LEACH协议(Low-energy Adaptive Clustering Hierarchy,低功耗自适应集簇分层型协议)通过特定的簇头选举算法确定哪些节点为某一个特定周期内的簇头,簇头通过广播方式告知其它节点自己是簇头。非簇头节点选择加入某个簇之后,会被分配固定的时间片用于发送消息,簇头负责对后续的消息发送过程进行管理。
该协议通过对传感器节点的分层管理,优化网络体系结构,并且利用簇头节点的信息融合能力减少网络中的冗余数据。不足之处在于,通过簇头选举算法选举产生的多个簇头并不一定能够遍及整个网络,因此可能导致某些节点无法接收和发送数据。
2.2 TTDD路由协议
TTDD协议(Two-Tier Data Dissemination)相比其他WSN路由协议而言可以很好地处理Sink节点移动问题。传输数据前先以源节点为中心建立网格,最接近网格交叉点的节点负责转发数据。Sink节点在其所处网格区间通过洪泛方式发起查询请求,距离Sink节点最近的转发节点作为直接转发节点并向其上游节点传送查询消息,直到查询消息传送到源节点为止。查询消息走过的路径即为数据传输路径,但两者传送方向相反。该协议中定义了初级(PA)和直接(IA),以便Sink节点在等待数据时可以继续移动。
TTDD适用于节点分布较为密集的网络,机制的存在使得Sink节点即使是在等待查询数据时仍然可以继续移动,这更贴近实际的网络环境。但网格尺寸的确定对整个算法的效率来讲影响较大,因此划分合适大小的网格对于该算法来讲较为重要。
3 地理位置路由
对于WSN网络来讲,短距离、少跳数的传输通常情况下能够缩短传播时延并节省能量[6]。节点可以利用一些地理位置信息选择合适的发送路径,从而提高网络性能。地理位置路由协议主要包括GPSR协议和GEAR协议。
3.1 GPSR路由协议
GPSR协议(Greedy Perimeter Stateless Routing)要求节点知道自己的地理位置,想要发送数据的节点利用贪婪算法选取转发节点。
贪婪算法的示意图如图7所示,B节点有数据需要发送,B的邻居节点C比B节点离目的节点A更近,因此B将数据转发给C。C再根据贪婪算法重复此过程,当数据包传送到目的节点A时此次传送过程才结束。由图7贪婪算法示意图不难发现, B-C-D-E-A的传送距离比实线标出的线路更短,但是由于F点相比E点距离D点更近,因此D点选择把数据发送给F点。贪婪算法所产生的“局部优化”问题,可能会增加数据的传播时延。
GPSR协议中不需要花费大量精力去维护网络拓扑结构,它既能支持静态WSN,又能支持动态WSN。但贪婪算法的使用可能导致协议实现过程中出现路由空洞问题,这时需要采用其他算法以达到整个路由算法收敛的目的,因而会在一定程度上增加传播时延[7]。
3.2 GEAR协议
GEAR协议(Geographic and Energy Aware Routing)与GPSR协议都需要将目标区域分割成若干个子区域,但GEAR协议中消息是向子区域的中心位置发送。GEAR协议与GPSR协议不同之处在于,节点需要知道自身剩余能量,并根据位置和剩余能量两个要素按照一定权重计算代价。代价计算见公式(1)所示:
估计:F(Ni,R)=α・D(Ni,R)+(1-α)・LE(Ni)
实际:F(Ni,R)=α・EC(Ni,R)+(1-α)・LE(Ni) (1)
说明:Ni为具有转发需求节点的邻居节点,R为目标区域的中心位置。若N不知道Ni的实际代价时使用估计代价。D(Ni, R)代表Ni和R的距离; LE(Ni)表示Ni的剩余能量;EC(Ni,R)表示Ni到R的能量损耗;α代表权重。
GEAR协议利用位置信息避免了查询消息的内爆问题,同时它在选择转发路径时考虑了节点到达指定区域的代价,这其中涉及消息传送过程消耗的能量以及节点剩余能量,以此达到均衡消息的目的。但由于使用了贪婪算法,该协议在实现过程中较容易出现路由空洞问题。
4 基于网络流量和服务质量的路由
对于WSN这个特殊的网络,传输路径的选择需要参考网络流量或是QoS性能指标,这时需要使用基于网络流量和服务质量的路由协议。例如基于QoS的SAR协议和SPEED协议。
4.1 SAR协议
SAR协议(Sequential Assignment Routing)是首个在WSN中做到保证网络服务质量的路由协议[8]。在该协议中,Sink节点的所有一跳邻居节点都以它为根创建生成树,见图8第一部分;其他节点重复此过程,多个生成树的叠加可以得到图8中第二部分。在路径汇总图中,有多条可达Sink节点且具有不同QoS参数的路径可供选择。节点发送数据时,按照QoS以及能量剩余情况选择合适路径进行传输。
SAR协议在保证QoS的基础上,通过维护传感器节点和Sink节点间的多条路径,使得某个节点或某条路径出现故障时,网络仍可以正常运行,从而增强网络的健壮性。不足之处在于节点需存储大量冗余路由信息,不仅浪费资源还导致路由信息维护的难度增大。
4.2 SPEED协议
SPEED协议是一种QoS协议,它通过设定一个速度门限对下一跳节点进行挑选,实现拥塞控制功能[8]。当节点准备发送数据包时,通过节点自身、邻居节点和目的节点三者的距离关系划分出一个转发结点候选集合,选取转发速度高于规定的门限值的节点构成转发节点集合。如果转发节点集合为空,可以通过调整门限值重新选取。
协议中对邻居节点的筛选过程,有利于保证传输的实时性,并使整个网络的传输负荷处于动态平衡状态,调节节点的能量消耗[9]。因SPEED协议同时也是与地理位置相关的路由协议并使用了贪婪算法,因此很难避免路由空洞问题[10]。
5 结 语
本文主要针对目前存在的典型WSN路由协议,从原理、特点和优缺点进行分析,以便为日后的WSN路由协议研究提供一些参考。
参考文献
[1]周雅琴,谭定忠.无线传感器网络应用及研究现状[J]. 传感器世界, 2009,5(5):35-40.
[2]毕俊蕾.基于分簇的WSN路由算法的研究与设计[D].开封:河南大学,2008.
[3]黄化吉,冯穗力,秦丽姣,等.NS网络模拟和协议仿真[M].北京:人民邮电出版社,2010.
[4]彭海英,唐伶俐,唐红.无线传感器网络中DD 路由协议的改进研究[J].计算机工程与应用,2007,43(14):127-130.
[5]夏静,庄雷,白雨.无线传感器网络谣传路由研究及改进[J].微计算机信息(测控自动化),2007,23(7-1):152-153.
[6]顾一中.无线传感器网络地理位置路由相关技术研究[D].南京:南京理工大学,2008.
[7]唐国明,谢羿,唐九阳,等.一种基于左、右手法则的GPSR分区边界转发路由协议[J].计算机应用研究, 2011,28(3):1099-1101.
[8]赵强利,蒋艳凰,徐明.无线传感器网络路由协议的分析与比较[J].计算机科学, 2009,36(2):35-41.
关键词: 动态路由;OSPF;自治系统配置命令;链路
中图分类号:TP3 文献标识码:A 文章编号:1009-3044(2013)34-7697-02
21世纪是网络的世界,我们每个人都在不知不觉中融入这个网络世界。而路由器在网络中发挥着越来越重要的作用,其主要负责在网络层间按传输数据分组的,并确定网络上数据传送的最佳路径。世界各地的个人和企业单位接入到Internet的自治系统有大有小,小型自治系统因其网络结构简单往往采用静态路由技术即可完成自治系统内的路由寻址,然而大、中型自治系统的网络拓扑结构往往更加复杂,采用依靠人工分配的静态路由技术存在很大的困难,因此根据合理的路由寻址算法设计的动态路由技术随之诞生,而OSPF动态路由技术因其功能强大、可拓展性强和网络性能优越在动态路由技术中格外优秀,被广泛应用于各大、中型自治系统中。
1 OSPF的基本概念
开放最短路径优先协议(Open Shortest Path First)简称OSPF,它是路由选择协议中非常重要的一种协议,这是一种典型的链路状态(Link-state)路由协议,是由Internet工程任务组开发的内部网关(IGP)路由协议,其主要用在一个路由域内。路由域是指一个网络自治系统(Autonomous System),所谓自治系统是指一组路由器都使用同一种路由协议交换路由信息,网络中每个路由器都有一个唯一的标识,用于在链路状态数据库(LSDB)中标识自己。LSDB描述的是整个网络的拓扑结构,包括网络内所有的路由器,作为一种链路状态的路由协议,OSPF将链路状态广播数据包LSA(Link State Advertisement)传送给在某一区域内的所有路由器,OSPF协议使用最短路径优先算法,利用LSA通告得来的信息计算每一个目标网络的最短路径,以自身为根生成一个树,包含了到达每个目的网络的完整路径。
OSPF的路由标示是一个32位的数字,它在自治系统中被用来唯一识别路由器。默认地使用最高回送地址,若回送地址没有被配置,则使用物理接口上最高的IP地址作为路由标示。OSPF在相邻路由器间建立邻接关系,使它们能利用HELLO包维护关系并交换信息。OSPF使用区域来为自治系统分段,区域0是一个主干区域,每一个OSPF网络必须具有,其他的区域通过区域0互连到一起。
2 OSPF的特点
OSPF路由协议主要用在大型自治系统内,这是一种链路状态的路由协议,,而距离矢量路由协议RIP(Routing Information Protocol)则主要用在小型自治系统内,两个路由协议都具有重要的作用,RIP作为静态路由协议,具有适于小型网络,管理员可手工配置,精确控制路由选择,改进网络性能等优点,但它特别不适合于大型网络自治系统。而OSPF路由协议与RIP相比,具有如下优点:1、RIP路由协议中用跳(HOP)来表示到达目的网络所要经过的路由器个数,RIP跳数最高为15,超过15跳的路由被认为不可达,而OSPF不受路由跳数的限制,它只受限于带宽和网络延迟,因而OSPF更适合应用于大型网络中。2、RIP在规划网络时是不支持可变长子网掩码(VLSM),这将导致IP地址分配的低效率,而OSPF路由协议支持VLSM,现在IPV4资源短缺,我们在划分大型网络的子网时,往往采用VLSM,这样划分子网效率更高,更节约IP资源,所以OSPF更适合大型网络。3、RIP必须每30秒就要周期性的广播整个路由表,才能使网络运行正常,如果RIP用在大型网络中,它会产生很多广播信息,而这些广播会占用较多的网络带宽资源,较频繁的更新有可能导致网络拥塞,其结果就是RIP用在大型网络中收敛速度较慢,甚至无法收敛。而OSPF使用组播发送链路状态更新,在链路状态变化时才进行更新,这样提高了带宽的利用率, 收敛速度也大幅提高,能够在最短的时间内将路由变化传递到整个自治系统。4、RIP没有网络延迟和链路开销的概念,拥有较少跳数的路由总是被选为最佳路由,即使较长的路径有低的延迟和开销,并且RIP没有区域的概念,不能在任意比特位进行路由汇总。而在OSPF路由协议中,往往把一个路由域划分为很多个区域area,每一个区域都通过OSPF边界路由器相连,区域间可以通过路由总结(Summary)来减少路由信息,从而减小路由表,提高路由器的运算速度。
OSPF路由协议拥有很多优点,特别适合用于大型网络,提高网络的运行速度,但它也有缺点:①使用OSPF路由协议,需要网络管理员事前先进行区域规划和路由器各端口IP属性的设置,所以配置相对于静态路由RIP来说显得较为复杂,对网络管理员的网络知识水平要求较高。②对路由器的CPU及内存要求较高。
3 OSPF配置命令及配置实例
在思科路由器中配置OSPF路由协议主要使用以下命令:①route ospf 进程号,其中进程号要求范围为1~65535,进程号只在路由器内部起作用,不同路由器的进程号可以不同。②network address 子网掩码的反码 area 区域号,区域号要求在0~4294967295内的十进制数,也可以是带有IP地址格式的X.X.X.X,当网络区域号为0时或0.0.0.0时为主干域,不同网络区域的路由器通过主干域学习路由信息。③show ip route,查看路由信息表,④show ip route ospf 查看OSPF协议路由信息。
某学校采用四台思科3550路由器把整个学校划分为3个区域,四台路由器通过使用OSPF协议实现互通。路由器R1的S0端口IP为192.200.10.5/30,E0端口IP为192.1.0.129/26;路由器R2的S0端口IP为192.200.10.6/30,E0端口IP为192.1.0.65/26;路由器R3的E0端口IP为192.1.0.130/26;路由器R4的E0端口IP为192.1.0.66/26。R1的S0端口和R2的S0端口划入区域0;R1的E0端口和R3的E0端口划入区域1;R2的E0端口和R4的E0端口划入区域2。各路由器配置如下:
R1:
interface Ethernet 0
ip address 192.1.0.129 255.255.255.192
interface serial 0
ip address 192.200.10.5 255.255.255.252
route ospf 500
network 192.200.10.4 0.0.0.3 area 0
network 192.1.0.128 0.0.0.63 area 1
R2:
interface Ethernet 0
ip address 192.1.0.65 255.255.255.192
interface serial 0
ip address 192.200.10.6 255.255.255.252
route ospf 600
network 192.200.10.4 0.0.0.3 area 0
network 192.1.0.64 0.0.0.63 area 2
R3:
interface Ethernet 0
ip address 192.1.0.130 255.255.255.192
route ospf 700
network 192.1.0.128 0.0.0.63 area 1
R4:
interface Ethernet 0
ip address 192.1.0.66 255.255.255.192
route ospf 800
network 192.1.0.64 0.0.0.63 area 2
在上述配置中首先对每台路由器接口进行配置,接口配置完后可以使用router ospf 100命令启动一个OSPF路由选择协议进程,期中“100”为进程号,每台路由器进程号可不同,最后使用network将相应的网段加入OSPF路由进程中,则此接口所对应的网段就加入到OSPF进程中。
综上所述,OSPF作为一种链路状态的路由协议,具有收敛快,支持变长网络掩码,支持CIDR,配置命令简单易学等。所以在大型或复杂网络中应用OSPF协议可以极大的提高网络的运行效率。
参考文献:
[1] 谢希仁.计算机网络[M].5版.北京:电子工业出版社,2008
[2] 思科网络技术学院.思科网络技术学院教程.
[3] 思科网络技术学院.思科网络技术学院教程(第三,四学期).
关键词:传感器节点
汇聚节点 能量 簇头 路由协议
中图分类号:TP316.4
文献标识码:
A
文章编号:1002-2422(2010)03-0002-03
1WSN路由协议介绍
1,1协议分类
划分路由协议种类有不同的标准。按是否需要外界辅助的地理信息准则,可划分为基于地理位置信息的协议和非基于地理位置信息的协议;按照网络中数据发送模式,路由机制可以相应地采用适合周期性地发送数据连续模式、事件驱动模式、请求驱动模式、事件驱动和请求驱动混合模式的协议;按照网络路由是否动态生成,可划分为表驱动路由协议和按需路由协议等。
下面介绍各个协议的工作方式。
SPIN采用广告、请求、数据三种消息类型。节点A在发送DATA数据包之前,会对外采用泛洪方式广播ADV包,若某个节点B希望接受要传来的数据,向A回复BEQ数据包。A将向B发送数据包。
GPsR对节点位置进行了统一编址。选择邻居节点中离数据包目的节点更近的点作为转发节点。当数据到达没有比当前节点更接近目的节点的区域(空洞),数据无法传输。可利用平面图解决空洞问题。
DIRECTED DIFFUSION路由过程分为请求、梯度建立和路径加强三阶段。请求含有目标区域、数据发送速率等参数。节点接收到请求后,若当前请求缓存中没有相同的请求记录,加入新记录。记录中包含了相邻节点数据发送率,称“梯度”。当请求扩散整个网络后,选择“梯度”最大的路径将反向把数据快速路由。模拟过程如图1所示。
GEAR发出请求后,数据扩散过程包括目标域传送和域内传送。若在目标区域传输遇到空洞现象,则根据开销函数选择开销最小的邻居作为下一跳节点。在域内传送阶段,主要是通过两种方式(泛洪、区域递归)使数据在域内扩散。
LEACH随机选择簇头,普通节点按接收到信号强弱加入簇层。簇层内节点单跳与簇头通讯,簇头与汇聚节点通讯。TEEN划分出多级簇层结构。子簇头单跳和父簇头通讯。PEGASIS在网络中节点中采用算法构造一个数据链,各个节点向靠近唯一网络簇头的邻居发送、接收其他节点传来的数据。
1,2路由协议决策要考虑的准则
设计协议要考虑多种因素,包括数据通讯量、带宽、网络负载情况、网络拓扑结构动态变化、网络节点增加、数据融合、可靠性等。图2中,数据从A传送到节点c。若要求传送及时,路由可采用A-B-C路径,减少了传送中继节点;若要求以负载平衡达到节能目的,路由应该根据实际负载情况采用负载相对较小的路径;若要求对不同节点的数据进行融合,可以选择A-E-F-G-H-C融合更多节点的数据;若要求可靠性,路由可以同时选择这两条路径。若被监测区域内的节点位置发生无规律变化。路由应该具备适应网络拓扑结构不断发生变化的能力;若要采集详尽数据而添加节点,协议还应具备支持更多节点协同工作的能力。
1,3路由协议的性能参数
(1)数据通讯量
把一块数据路由到观察者,不同算法会使得该数据的通讯量大小不一致。协议会在不同的程度上产生该数据块副本。通讯量越大,网络能耗越大。
(2)延迟
延迟指观察者对网络发出请求到接收到数据所历经的时间。
(3)可扩展性
在某些特殊的实际应用中,被监测区域需要大量节点。这样就要求路由协议能够协同大量节点同时工作。
2路由协议的路由通讯量分析
LEACH通过划分簇层和数据融合技术减少数据通讯量。TEEN采用相似的层次通讯方式,并使用软门阀值和硬门阀值控制数据传输的次数。PEGASIS通过有效的链式数据聚合和数据融合技术,减少了的数据收发次数和数据通讯量。图3是两者之间以及和FLOODING洪泛协议通讯量比较。
SPIN采用基于数据描述的协商机制进行数据的转发,从而避免了产生要转发数据的大量副本。
DIRECTED DIFFUSION采用请求驱动的数据传送模式和局部的数据聚集、融合,减少网络数据通讯量。图4是这两种协议间以及和FLOODING之间通讯量大小示意表示。
GPSR将数据发送给符合要求的下一跳邻居。针对某个特定节点A,在网络拓扑结构不发生变化的情况下,发送数据的路由比较固定。GEAR考虑到汇聚节点的地理位置信息,并将其添加到数据包的地理信息字段,数据传输到特定方向。
3路由协议的路由延迟分析
DIRECTED DIFFUSION在数据传输阶段采用一条“梯度”最大路径。数据传输时间短。LEACH采用划分簇层方式减少路由中间的传感器数量,也具备短延迟特性。TEEN协议延迟也比较小,和LEACH同属于层次式路由协议。GPSR只依赖直接相邻的节点进行路由。因为使用接近最短欧式距离的路由,因此数据传输延迟短。GEAR采用了域内和位置区域地理位置划分,这样减少了路由上的跳数,数据能及时到达汇聚节点。
PEGASIS数据延迟和簇头位置有很大的关系。普通节点距簇头的地理位置比较远,会明显增加数据传输的延迟。SPIN采用三种消息模型来信息扩散整个网络。解决了FLOODING中的“信息内爆”和“信息重叠”问题,但此消息模型导致延迟增加。
图5给出了层次性协议在相应延迟示意比较。表2作了路由延迟分析的总结。
4路由协议的可扩展性分析
某些协议,因节点大量增加导致网络数据通讯量过大、路由数据的延迟过长等等而不适用于网络。
TEEN不断加入节点形成新簇层。子簇头数据会向父簇头传送,不必像LEACH协议一样要求普通节点必须具备和汇聚节点直接通讯的能力。
DIRECTED DIFFUSION也具备良好可扩展。“梯度场”的建立确保了数据传输的及时性。备用路径保证了路由的畅通性、可靠性。
GPSR有可达路由只要求保持网络连通性。GEAR具备好的可扩展性,但需要GPS定位信息的支持。即使增加节点,在地理位置和“两个阶段”的支持下,不会影响协议。
PEGASIS可扩展性差。当大量节点涌入到网络中,要构造的数据链长度会急剧增加。将数据传送到簇头,不仅耗费大量能量还增加延时时间。
SPIN可扩展性差。当产生或收到数据的节点的所有相邻节点都不需要该数据时,将导致数据不能继续转发。可能导致相当部分网络不能接收到该数据。此外,汇聚节点对任何类型的数据都需要时,周围的节点会能量耗尽。表3给出了协议总结。
【关键词】ZigBee网络 路由协议 性能
随着信息技术和移动通信技术的快速发展,让无线通信技术在各行各业得到了广泛的应用。组网灵活、使用方便是无线传感器网络在实际应用中表现出来的主要特点。ZigBee协议的出现,可以让传统无线协议对无线传感器的适应问题得到有效解决。
1 ZigBee协议的概述
ZigBee技术不仅功耗、成本和速率均比较低,而且便于操作使用。而IEEE 802.15.4标准具有数据传输率低、成本少、功耗低等特性,其最终目标就是为家庭或个人范围内各种设备之间的低速互连提供一个统一的标准。为了保证所制定出的应用层与网络层的规范能够匹配IEEE802.15.4标准,ZigBee规范成为ZigBee联盟中不可缺少的因素。在与之有关的LR-WPAN网络中,IEEE802.15.4标准编制了以下两种要素:
(1)系统的媒体接入控制子层;
(2)系统的物理层协议规范。
ZigBee联盟在这一前提下,所构建的应用层与网络层协议相关的规范构成了ZigBee协议。简言之,ZigBee协议是为适应IEEE802.15.4标准而构建的网络层与应用层协议规范。其中,协议规范可以由以下几方面因素组成:
(1)应用支持子层;
(2)应用架构;
(3)ZigBee设备对象和厂商所定义的应用对象。
分层结构是这一协议所采用的主要结构。数据实体和管理实体这两种服务实体在这种结构的每一层都有所涉及。数据传输服务是数据实体所承担的主要形式。管理实体提供的服务中并没有涉及到数据传输服务。服务接入点是为上层提供接口的重要工具。服务原语命令是服务接入点实现自身功能的保障性因素。图1中的内容就是协议层之间的服务接口。
2 ZigBee网络拓扑
ZigBee网络拓扑结构主要由以下几种结构组成:
(1)星型结构;
(2)树形结构,
(3)网状结构。
如图2所示。
从图中所示的内容来看,中心协调器和终端节点是星型网络中的主要器件。这种中心协调器采用的是FFD节点,可以在整个网络的维护和建立过程中发挥出自身的功能。RFD和FFD是终端节点主要组成部分,一般的情况下,在中心协调器覆盖范围以内的区域是这两大节点的主要分布区域,@种便利性可以让这些节点与中心协调器进行有效通信的能力得到有效提升。两个不同设备之间进行通信的过程,也是两设备将各自所要传送的数据包向中心协调器进行传送的过程。可以说,中心协调器发挥的是一种中转作用。对中心协调器的中转功能进行发挥的网络系统又被称为主从网络。同步与控制的简单性特点是星型网的主要特点,这种网络体系目前仅能在一些拥有较少节点数量的场合中得到应用。网状网络是一种由多个FFD组合而成的骨干网络,各节点之间的通信完全对等,在整个通信范围内,各节点都可以与其它节点进行通信。如果其中一条路径发生故障,那么还可以选择其他一条或若干条路径。然而,正是因为两个节点之间的路径较多,所以显得冗余非常高。一般情况下,路由功能的实现,是网状网络构建过程中所遵循的一个重要原则,此种有助于网络层找到最佳的信息传递路径,事实上属于一种多信道通信。树状拓扑结构主要由以下三个部分组成:
(1)中心协调器;
(2)路由节点;
(3)终端节点。
在实际应用过程中,连接路由节点和终端节点的功能是该结构的主要功能。在路由节点成为中心协调器子节点的情况下,这一结构会借助一系列的终端节点与路由节点相连。终端节点不能涵盖自身的子节点,但路由节点与中心协调器可以涵盖自身的子节点。在树状拓扑结构中,各个节点只具备一种功能,就是实现子节点与父节点之间的通讯。在这样的情况下,如果要将一个节点中的数据传输到另一个节点,这种树状结构会让信息顺着树的路径进行输送。网络覆盖范围大是这一网络结构的主要特点。由于信息路由通道在该系统中存在单一性,随着网络覆盖范围增加,信息的传输时延也会有所增加,并且时间同步也会越来越繁琐。
3 ZigBee网络路由协议的性能
3.1 路由协议的基本思想
低成本、低功效和高可靠性是ZigBee网络路由协议的主要设计目标。树路由和按需距离矢量路由相结合的路由算法的构建,为上述目标的实现提供了帮助。在对ZigBee网络中使用的AODVjr与自组网中所应用的AODV协议进行对比分析以后,我们可以发现,AODVjr可以被看作是AODV的一种简化版本。在ZigBee网络中,节点之间存在一种类似于父子关系的从属关系。在依托路由算法进行路径选择的过程中,节点会在接收到分组信息以后对信息进行判断,如果发现其中的内容与自己无关,会把该信息传送给其父节点或其他子节点。为了对路由效率进行进一步的提升,AODVjr也会为一些具备路由功能的节点搜寻路由,也就是说,在传输信息的过程中,在不遵从父子从属关系的情况下,通过直接传递的方式将信息传送到其通信范围内的其他具备同样功能的节点的措施,是一些具备路由功能的节点进行信息传输的主要措施,而针对那些不具备路由功能的节点,则只能借助树路由来对控制分组与数据分组进行传输。
3.2 ZigBee的路由过程
在zigBee网络路由协议中,节点既具备路由表能力,又具有路由发现表能力,表1所示的内容为路由发现表的格式
从阶段网络层的数据帧获取情况来看,在网络层从更高层接受数据帧的情况下,广播发送是节点进行数据传送的主要方式。在接收节点为路由器或协调器的情况下,如果数据帧的目的节点是该节点的子节点,这一数据帧会被直接传送到目的地址之中。如果网络层接收的是来自低层的数据帧,数据帧的目的节点成为了系统对数据帧的发送方式进行确定的主要方式。在对一些具备路由功能的节点进行确定的过程中,系统会对目的地址在路由表中的地址加以核查,在节点目的地址的路由条目不确定的情况下,首先针对数据帧头系统需要对帧控制域中的路由发现标志进行核查,如果路由发现标志值为0,或者此节点缺少路由功能,则可采取树路由的方式传输数据帧;倘若该发现路由标志值为1,则该节点可根据路由发现的发起方式及条件来发起路由发现。针对目的地址的路由条目明确的节点,必须借助已有路由表条目进行路由传输。
如果网络层接收到来源于低层的数据帧,则是否需要转发该数据帧主要取决于该数据帧的目的节点是否是本地节点。在终端设备成为目的节点以后,设备在应用过程中出现的休眠问题会给信息的传输效率带来不利的影响。间接传递方式的应用,就成为了对休眠效应的不利影响进行规避的有效方式。数据帧头中的Discover Route字段决定着如何选取ZigBee网络层的具体路由方法。
3.3 路由选择
在节点的职能定义和工作状态存在一定差异性的情况下,路由策略选择就成为了zigBee网络路由协议性能的一种表现。路由选择策略主要由以下几种策略组成。
(1)抑制路由发现,这一性能是建立在已经存在的路由表基础之上的;
(2)使能路由的发现,即路由表中存在该路由地址,则按路由表执行,否则路由器进行初始化路由发现处理。如果路由表中的节点不具备初始路由的发现能力,系统会对树形路由进行运用;
(3)强制路由发现功能,在这一功能的作用下,不论相应的路由表是否存在,节点都会在对AODVjr路由算法进行强制应用的情况下进行初始化路由发现。可以说,数据驱动思想是与数据的传输种类和传输需要之间存在着一定的联系;
(4)树路由发现功能,即只应用树状路由方式发起路由发现,且不遵从现有的路由表。所谓的数据驱动思想就是指针对不同类型及需求的数据传递,可以采取多种路由方式。如果需要传递大量的数据,那么可以对使能路由发现功能加以选取,发现并构建最佳路径。如果需要传递控制数据或突发型数据,则可以对树路由发现功能与抑制路由发现功能加以选取,这两种路由发现功能能够实现快速响应,而且不需要构建路由表。如果需要更新路由表内的信息,那么可以对强制路由发现功能加以选取,以此来对路由表进行更新,对路由表加以重新构建。
4 结论
ZigBee结束对进场通信市场所表现出的低成本、低速率和低功耗的问题进行了有效解决。这一技术的应用,对低端无线传感器和控制网络设计的优化有着一定的促进作用。ZigBee通过结合ZigBee规范与IEEE802.15.4标准,可以有效的实现数以万计的微波传感器之间进行协同通信。在当下ZigBee快速发展、不断优化的新时代下,ZigBee技术势必会为无线接入技术领域注入全新的活力,必将使人们的生活模式及工作模式发生翻天覆地的改变,促进社会以及经济建设更快、更好地发展。
参考文献
[1]张习胜.ZigBee无线网络协议的路由算法分析与实现[J].电子元器件应用,2010(07):53-56.
[2]关学忠,张新城,孟伸伸.基于ZigBee技术的无线传感器网络路由算法的性能分析[J].自动化技术与应用,2017(03):36-39.
作者简介
李玉林(1981-),男,湖南省永兴县人。硕士学位。现为湖南机电职业技术学院讲师。主要研究方向为计算机网络管理。
Abstract: Ad hoc network is a MANET, mobile nodes must have the routing function, so the routing protocol selection is critical. This paper introduces the DSDV, DSR and AODV routing protocols. We obtain the throughput, packet loss and delay performance analysis chart by NS simulation. It gives the advantages and disadvantages of these types of routing protocols and the future direction of development of routing protocols.
关键词: Ad hoc网络;NS模拟;DSDV;DSR;AODV
Key words: Ad hoc network;NS simulation;DSDV;DSR;AODV
中图分类号:TP393文献标识码:A文章编号:1006-4311(2011)17-0146-02
0引言
移动Ad hoc网络是一种自组网,不需要固定的基础设施,能够快速地自动组网。与有中心网络相比,Ad hoc网络灵活、健壮、投资少,特别适合于作战指挥、抢险救灾以及应付突发事件和执行临时任务的场合。在Ad hoc网络中,因为自组网中节点的传输范围有限,源端向目的端发送数据时,通常需要其它节点的辅助,所以路由协议是自组网中不可缺少的一部分。路由协议的功能是根据路由策略和路由表进行数据分组转发和路由维护。Ad hoc网络在通信中,节点是移动的,而且传输能力有限,大多采用多跳转播通信,而多跳路由带宽受限,设备功率低,网络的拓扑结构动态变化,易受攻击等挑战。
1Ad hoc路由协议及典型的路由算法
目前,Ad hoc网络的路由协议大致可以分为主动路由协议、按需路由协议和混合路由协议。主动路由协议又称为表驱动路由协议,在这种路由协议中,即使没有传输需求,两节点之间的路由也预先建立。这种方法不适合大规模网络,许多不用的路由仍需维持,而且还有周期性的路由信息更新。而按需路由协议,是一种当需要发送数据时才建立路由。不需要时,释放路由。然而,当一个链路失效或节点断开,要重建路由而引起延时和开销更严重。下面介绍几种典型的路由算法。
1.1 主动路由协议――DSDV目的节点序列距离矢量路由协议(DSDV,Destination-Sequenced Distance-Vector Routing)是基于Bellman-Ford算法,在DSDV中,每个移动节点都需要维护一个路由表。路由表包括目的节点、跳数、下一跳节点和目的地序号,其中目的地序号由目的节点分配,主要用于判别路由是否过时,并可防止路由环路的产生。每个节点周期性必须与邻节点交换路由信息,当然也可以根据路由表的改变来触发路由更新。对路由表进行更新主要有以下两种方式:①全部更新:拓扑更新消息中将涵盖整个路由表。此种方式大多运用在有相对快的网络变化的状况下;②部分更新:在更新消息中只是涵盖了变化的路由部分。这种方式大多应用在有相对较慢的网络变化的状况。在DSDV中只要从源到目的的路由存在,这种路由协议的所需时延较小,缺点是路由协议的开销较大,因为动态的拓扑结构变化,使得路由信息更新复杂,不适合大规模的网络。
1.2 按需路由协议――DSR动态源路由协议(DSR,Dynamic Source Routing Protocol)是一种基于源路由的按需路由协议,它使用源路由算法而不是逐跳路由的方法。DSR主要包括两个过程:路由发现和路由维护。当节点S向节点D发送数据时,它首先检查缓存是否存在未过期的到目的节点的路由,如果存在,则直接使用可用的路由,否则启动路由发现过程。路由发现过程是:源端节点广播路由请求给其邻居节点,邻居节点收到路由请求分组后,轮流把自己的地址添加道路由请求分组,并转发补充了的路由请求分组,这个过程一直持续到有一个路由请求分组到达目的端节点。若发现自己的地址在记录中,就停止广播,每个节点都有一个路由缓存,存贮最近转发来的路由请求,同时查询接收的是否为统一个请求,这样可以保证每个节点之转发一次。当路由请求到达目的节点时,节点要返回一个路由应答分组,通知节点已收到该路由请求。目的节点通过反向路由来发送路有应答消息。那么源端与目的端有多条路由。DSR把这些路由缓存在路由缓存器中备用。
这样做DSR不需要周期性的发送路由发现报文,但发送每个报文都要携带完整的路由消息。降低带宽的利用率。DSR的优点:①节点仅需要维护与之通信的节点的路由,减少了协议开销;②使用路由缓存技术减少了路由发现的耗费;③一次路由发现过程可能会产生多条到目的点的路由。DSR的缺点:①每个数据报文的头部都需要携带路由信息,数据包的额外开销较大;②路由请求消息采用洪泛方式,相邻节点路由请求消息可能发生传播冲突并可能会产生重复广播;③由于缓存,过期路由会影响路由选择的准确性。
1.3 按需路由协议――AODV Ad hoc按需距离矢量路由协议(AODV, Ad hoc on Demand Distance Vector)是DSDV算法的改进,但它与DSDV的区别在于它是按需路由协议。为了找到通往目的节点的路由,源端将广播一个路由请求分组,邻居节点依次向周围节点广播此分组直到该分组被送到一个知道目的节点路由信息中间节点或目的节点本身。一个节点将丢弃重复收到的请求分组,路由请求分组中的序列号用来防止路由环路,并能判断中间节点是否响应了相应的路由请求。当节点转发路由请求分组时,它会将其上一个节点的标志ID记入路由表,从而能够构建一条从目的节点到源节点的反向路由。当源端移动时,它会重新发起路由发现算法;如果中间节点移动,那么与其相邻的节点会发现链路失效并向其上一个节点发送链路失效消息并一直传到源节点,而后源节点根据情况重新发起路由发现过程。
2Ad hoc网络中的路由协议的NS模拟
本模拟在windows XP环境下,采用Cygwin和ns-allinone-2.28搭建模拟平台。在此环境下,对Ad hoc网络中的路由协议DSDV、DSR和AODV进行模拟分析,并对其进行性能比较,并以图形形式显示。
2.1 搭建实验网络拓扑模拟工具采用NS2网络模拟器,无线模拟开始时,需要定义每个网络功能组件的类型,包括天线的类型、电磁波的传输模式和移动节点使用的Ad hoc路由选择协议等。网络初始拓扑结构见图1,该模型由6个无线移动节点构成,3个源节点(节点0,1和2)和3个目的节点(节点3,4和5)。节点0开始向节点3发送CBR数据包,使用的是DSDV路由协议;节点1开始向节点4发送CBR数据包,使用的是DSR路由协议;节点2开始向节点5发送CBR数据包,使用的是AODV路由协议;传输的分组大小均是512比特,传输速率是600 Kbps,开始传输时间为1.4s,传输距离是195米,模拟的时间是80s。
2.2 性能分析在相同的网络环境下,分别用3种Ad hoc路由协议进行模拟,而后对模拟产生的TR数据进行分析,用绘图工具Xgraph绘制,由于本模拟是从1.4s开始模拟,但是绘制的吞吐量、丢包和延时图却是从0s开始。吞吐量实时变化图如图2,丢包实时变化图如图3,端到端的延时的实时变化图如图4所示,黑色是DSR,深灰色是DSDV,浅灰色是AODV。下面进行具体的分析比较3种路由协议下CBR应用的性能。
2.2.1 吞吐量吞吐量能反映网络占用带宽的性能。从图2可知,从1.4s到20s时,AODV的吞吐量最大,DSDV和DSR差不多;20s后,3种路由协议的吞吐量都比刚开始模拟要小一些,呈现不断降低的趋势。吞吐量是AODV最好,次之是DSR,DSDV最差。
2.2.2 丢包率丢包率反映的是丢包数目与总发包数目的比值。从图3可知,从1.4s到20s时,3种路由协议都没有丢包,但20s后,丢包率都增加,呈现不断提高的趋势。其中,丢包最大的是DSDV,然后是DSR,最小的是AODV。
2.2.3 端到端的延时端到端的延时是反映包发送过程中,目的端与源端的时间差。从图4可知,从1.4s到20s时,3种路由协议端到端的延时一致,呈现不断提高的趋势。但20s后,端到端的延时都增加,其中,延时最大的是DSR,然后是AODV,最小的是DSDV。
综上所述,都是因为DSDV是主动路由协议,而DSR、AODV是需路由协议,DSDV为目的节点只维护一个路由,当此路由失效时将没有可以替换的路由。如果网络拓扑结构动态变化的太快,路由信息更新复杂,网络开销大,端到端的延时小一些。而按需路由是不用周期的广播信息,节省网络开销,但每次要进行路由发现,端到端的时延大。
3结论
本文详细分析了当前Ad hoc网络采用的3种路由协议,并且通过NS网络模拟器对其中的3种路由算法进行了模拟分析和性能比较。结果表明不同的路由协议都有各自的应用场合和优缺点,目前最为流行的就是将主动和按需路由协议优点的混合式路由协议是一种较好的折衷方案。应用在局部范围内使用主动路由协议,维护准确的路由信息,并可缩小路由控制消息传播的范围,当目标节点较远时,通过查找发现路由,这样既可以减少路由协议的开销,时延特性也得到了改善。这种路由算法吸取了2种路由算法的优点,具有较高的效率和较强的适应性。由于Ad hoc自身复杂多变的动态特性,路由协议的设计目前仍是一个人们关注的热点问题。
参考文献:
[1]李平均,谷宁静.一种基于AODV协议的改进协议Q-AODV[J].微电子学与计算机,2006,23(5):89-92.
[2]王金龙,王呈贵,吴启晖等.Ad hoc移动无线网络[M].北京:国防工业出版社,2004.
[3]葛文英,伟.Ad hoc网络的按需路由研究[J].软件技术.2006,(8):41-42.
[4]于斌,孙斌,温暖等.NS-2与网络模拟[M].北京:人民邮电出版社,2007.
关键词:无线传感网络;RPL;IP;能量路由
中图分类号:TP393 文献标志码:A 文章编号:2095-1302(2014)01-0057-03
0 引 言
低功耗有损网络路由协议 (RPL)是IETF的ROLL(Routing Over Low power and Lossy networks )工作组,专门针对低功耗有损网络LLN(Low power and Lossy network)新提出来的路由协议[1]。低功耗有损网络是由功率、存储空间、处理能力等资源受限的嵌入式设备所组成的网络。它们可以通过多种链路连接,比如IEEE 802.15.4、蓝牙、低功率Wi-Fi,甚至低功耗电力线通信(PLC)等等。ROLL将LLN网络的应用主要划分为四个领域[2]:城市网络(包括智能电网应用)、建筑自动化、工业自动化以及家庭自动化,并且分别制定了针对四个应用领域的路由需求[3-6]。由于LLN的独特性,传统的IP路由协议,比如OSPF、IS-IS、AODV、OLSR,无法满足其独特的路由需求,因此ROLL工作组制定了RPL协议,其协议标准RFC6550[1]于2012年3月。
本论文首先介绍了RPL的应用场景及基本原理,并在路径选择策略中加入了对节点剩余能量的考虑;最后通过仿真验证了改进后的路由协议的性能。
1 RPL协议工作原理
RPL是一个矢量路由协议,通过构建有向非循环图(DAG)来形成拓扑结构,加入DAG中的节点自动形成一条指向根节点的路径。RPL主要为数据汇聚型的场景设计,即数据流量由叶节点指向根节点。当然RPL也扩展支持多点对点(MP2P)和点对点(P2P)的应用场景。
图1所示为典型的DAG结构。其中的每一个节点至少有一条指向根节点的路径。
1.1 DODAG的形成
DODAG(Destination Oriented Directed Acyclic Graph)是面向目的地的有向非循环图的简称,可以视为物理网络上的逻辑路由拓扑。
RPL中定义了由多种ICMPv6消息来控制拓扑的形成。DIO消息用于通告有关DODAG的参数,例如DODAGID、目标函数(OF)、DODAG版本号等[1]。其中OF规定了拓扑建立及最优父节点的选择方式,规定了节点级别的计算方法,是路径选择的首要参考标准。级别决定了节点在DODAG中的相对位置,主要用于避免回路。DAO消息是用来建立从根节点到叶节点的“向下”的路径。根据节点的存储能力,RPL协议中将节点类型定义为可存储型和非存储型,两者的区别在于是否存储有路由表信息。在图1中,当D节点要和E节点通信时,如果B节点和C节点是非存储型,那么必须先追溯到根节点A,查找路由,即路径为D—C—B—A—B—C—E。若C为可存储型节点,则只需追溯到共同的祖先节点即可找到路由,即路径为D—C—E。DIS消息用于向邻居节点请求DODAG信息。当一个孤立的节点没有收到任何DIO消息的时候,可通过DIS向周围节点请求DODAG信息。收到DIS消息的节点会反馈DIO消息给DIS源节点。
如图1所示,首先A节点通过DIO消息广播自己创建的DODAG信息,收到DIO消息的节点根据OF来决定是否应该加入该DODAG;加入之后然后再向自己周围的节点继续广播DIO消息;这样一层一层地建立拓扑结构。当节点加入DODAG之后,就自动创建一条“向上”汇聚到根节点的路径。“向下”的路径则由DAO消息完成。
1.2 定时器管理
RPL中使用细流算法[7]来控制DIO消息的发送。细流算法是一个适应性的机制,用来限制控制协议的开销。与传统IP网络不同,LLN网络有着非常有限的资源,必须尽可能的减少控制协议消息所占的比例,但同时又必须要维护好网络结构。当网络改变时,节点会以较高的频率发送控制包;当网络趋于稳定时,则控制流的速率减少。算法中定义了控制消息发送间隔参数I,当网络很稳定时,则I成倍的增加;而网络有动荡时,则发送间隔迅速降为最小值,高频率的发送控制消息以修复网络。
本文借助Contiki系统中的Cooja模拟器,对RPL协议进行了仿真。图2所示为节点布局图,并在图3中以节点5为例展示了DIO消息的发送控制过程。从图3中可以看到,当网络刚形成逐步趋于稳定的时候,DIO消息发送间隔成倍增加;图3中23:00和01:20附近陡峭的转折点表明此时监测到节点5和网络存在不一致性,迅速将控制消息发送间隔调至最小值以迅速修复网络。
1.3 环路避免机制
RPL中规定,在沿着叶节点到根节点的路径上,节点级别必须是递减的[1],即父节点的级别必须小于子节点的级别。当节点在网络中位置发生改变时,必须根据父节点重新计算自己的级别。假设节点N的最优父节点为P,P的级别为R(P),那么N的级别R(N)计算公式为:
R(N)=R(P)+ rank_increase
rank_increase为子节点和父节点级别的差值,其算法在OF中有定义。
节点的级别在环路避免中有着重要的意义。RPL协议也通过在包头上设定标志位来附带路由控制数据,以避免数据包被循环转发。
2 考虑节点剩余能量的RPL协议
2.1 RPL协议原始路由方案
目标函数决定了RPL协议的路径选择方式。目前RPL的官方文件中,只明确定义了零目标函数(OF0)[8],即以跳数(HC)为最佳路径选择的唯一标准,而其他的目标函数则由开发者根据需求灵活定义。比如对链路可靠性要求较高的应用,可将链路质量作为路由选择的首要考虑标准;而对能量受限的环境则可以定义在路径中尽量避开电池供电节点。在文档RFC6551[9]中,提出了多种可供开发者参考的路由度量。
在选择路径时,若只考虑跳数因素,必然会导致Sink周边节点数据压力过大,从而使关键节点能量过早消耗而死亡。文献[10]将网络的生命长度定义为第一个节点死亡的时间。对于能量受限的低功耗有损网络,如何平衡能量消耗,延长网络整体寿命,是协议要考虑的重要因素。
2.2 优化之后的RPL路由方案
目前已有多种针对无线传感网络能量优化的路由协议,比如分级能量路由协议LEACH和TEEN,以数据为中心的能量有效路由协议DD和SPIN,还有基于地理位置的路由协议GPSR和GEAR等[11]。 但这些协议都很难实现和RPL协议的融合。RPL协议是通过在container metric中,定义路径选择时所考虑的参数,然后再以一定的方式将所需要考虑的参数相结合,从而确定一个合理的路径选择方案。
本篇论文中采取的是跳数(HC)和节点能量(EN)相结合的方式。结合方式有两种[12],一种是Lex,一种是Add。Lex是指优先考虑跳数,只有在跳数相同的情况下,才考虑节点能量;而Add则是采取两种参数综合考虑的方式,按照一定的比例相结合,即:
其中:
本文对这两种不同的结合方式做了仿真对比。
2.3 RPL协议改进前后的仿真对比
仿真工具采用的是美国UIUC大学开发的针对无线传感网络研究的J-Sim平台,该平台基于Java语言,和NS2相比具有内存消耗小、仿真速度快、有更好的可扩展性等优点。本文仿真了传感网络数据收集的场景。在100×100的区域里,规则的布置有100个节点,图4所示是网络节点布局图和OF0的拓扑结构,其中最左上侧的0号节点为数据汇聚节点,右下侧的49-99和94-98这11个节点为传感器数据采集节点。数据从右下侧的11个源节点发送到左上侧的0号节点。由于该网络具有对称性,1和10对称,2和20对称等,对称节点的能量消耗基本一致。本文中重点仿真了具有代表性的1、2、11、12、22这几个关键节点的能量消耗情况。
对于OF0,由于跳数是路径选择的唯一标准,节点位置固定的网络,其拓扑结构也相对保持不变。图4即为这种情况下的拓扑结构。由图4中可以看到,节点1和节点10承载了大部分的数据量,几乎任何从下侧或者右侧源节点发过来的数据都要经过这两个节点转发到Sink节点。而节点11,则只有来自源节点99的数据由它转发。
图5所示是系统节点能耗图。其中图5(a)为OF0方案下部分节点能量消耗图。从图中可以看出,最关键的节点1和节点10,能量很快就消耗殆尽。而节点11,则能耗相对较少。这对节点位置固定的网络是很不利的,会使数据量较大的节点在短期内能量迅速消耗完而死亡,而其他非位置关键节点,则一直被闲置。造成网络能耗分布极其不均匀,能量利用率不高。
接下来可以仿真跳数和节点剩余能量相结合的路径选择方式,图5(b)为跳数和能量按照2∶8的比例加权所得到的能耗结果。从图5(b)可以看出,节点1、10和11的能耗更为均衡,第一个节点死亡的时间大为延长。跳数和节点剩余能量相结合的路径选择方式,能一定程度上改善以跳数为唯一度量所造成了能量消耗不均的情况,从而延长关键节点的生命长度。仿真中也能看到,最佳路径的拓扑图一直处于动态变化,原先经过节点1和节点10到达汇聚节点的数据,有一部分从节点11分流,从而缓解节点1和节点10的压力。
(a) HC路径选择方案节点能耗 (b) HC+EN路径选择方案节点能耗
本文也仿真了跳数(HC)和节点能量(EN)按照Lex的结合方式,即优先考虑最小跳数,当跳数相同的时候再考虑节点能量,以及在Add结合方式下按0.8HC+0.2EN和0.2HC+0.8EN的不同比例相结合的情况对比。最后得出的结论是,两种不同的结合方式对网络能耗均衡都有一定程度的改善;而Add的结合方式能耗更为均衡,且剩余能量所占的比例越高,改善的效果越为显著。图6所示是在不同路由策略下,关键节点能耗的对比情况。
4 结 语
本文描述了RPL协议的基本原理,并且对原路由协议的路径选择策略进行了改进,在只考虑跳数的基础上,加入节点剩余能量的考虑,从而平衡了网络能耗,延长网络整体寿命。由于RPL是近几年新提出的协议,随着实践的不断深入,越来越多的新问题被提出,还有很大的研究空间。RPL协议在物联网领域有着广阔的应用前景,值得广大学者进一步深入研究。
5 致 谢
本论文的工作得到了实验室项目的大力支持。感谢国家自然科学基金(61271257),北京市自然科学基金(4122034)和教育部博士点基金(20120005110007)对本文研究工作的支持。
参 考 文 献
[1] WINTER T. RFC6550 RPL: routing protocol for low power and lossy networks [S]. USA: Internet Engineering Task Force, 2012.
[2] VASSEUR J P, DUNKELS A.基于IP的物联网架构、技术与应用[M]. ,田辉,徐贵保,译.北京:人民邮电出版社,2011.
[3] DOHLER M. RFC 5548 routing requirements for urban low-power and lossy networks [S]. Internet Engineering Task Force, 2009.
[4] PISTER K. RFC5673 industrial routing requirements in low-power and lossy networks [S]. Internet Engineering Task Force, 2009.
[5] BRANDT A. RFC5826 home automation routing requirements in low-power and lossy networks[S]. Internet Engineering Task Force, 2010.
[6] MARTOCCI J. RFC5867 building automation routing requirements in low-power and lossy networks [S]. Internet Engineering Task Force, 2010.6
[7] LEVIS P. The trickle algorithm draft-ietf-roll-trickle-08 [S]. Internet Engineering Task Force, 2011.
[8] THUBERT P. RFC6552 objective function zero for the routing protocol for low-power and lossy networks (RPL) [S]. Internet Engineering Task Force, 2012.
[9] VASSEUR JP. RFC6551 routing metrics used for path calculation in low-power and lossy networks [S]. Internet Engineering Task Force, 2012.
[10]廖梦泽.无线传感器网络生命期最优化[D].上海:上海交通大学,2010.
关键词:移动Ad Hoc;NS2;延时;多路径路由协议
中图分类号:TP393文献标识码:A文章编号:1009-3044(2007)03-10681-03
1 引言
移动Ad Hoc 网络又称移动自组网、多跳网络,它的特点是由结点移动引起的动态拓扑、信道带宽有限和结点有限的存储能力。面临的关键挑战是在动态环境下能在花费最小的情况下传送信息,另外,对QoS 的支持也是一个重要的研究课题。目前存在的多数协议也都是路由表驱动或是源结点发起的按需路由协议,而且这些协议都是基于尽力服务模型的,无法满足现近一些需要QoS路由的业务。在有线网的多路径协议中,已经对QoS路由有很广泛的研究,但是这些研究并不能适用于Ad Hoc网络的。其中文献[1,2,3]详细阐述了移动Ad Hoc网络QoS路由协议的发展现状,文献[4,5]对移动Ad Hoc网络中的QoS约束作出了深入解析,文献[6,7,8]提出一些新的支持QoS约束的移动Ad Hoc路由协议,在本文中,我们将给出一种多路径QoS路由协议MQDSR,该路由能够支持QoS约束并提供多路径路由以减少路由发现过程和路由维护。
2 DSR协议描述
DSR(Dynamic Source Routing)协议是一种基于源路由方式的按需路由协议。在DSR协议中,当发送者发送报文时,在数据报文头部携带到达目的节点的路由信息,该路由信息由网络中的若干节点地址组成,源节点的数据报文就通过这些节点的中继转发到达目的节点。与基于表驱动方式的路由协议不同的是,在DSR协议中,节点不需要实时维护网络的拓扑信息。
DSR路由协议主要由路由发现和路由维护两部分组成。路由发现过程主要用于帮助源节点获得到达目的节点的路由。当路由中的节点由于移动、关机等原因无法保证到达目的节点时,当前的路由就不再有效了。DSR协议通路由维护过程来监测当前路由的可用情况,当监测到路由故障时,将调用新的一轮路由发现过程。文献[3]中详细论述了DSR协议的路由发现及路由维护过程。
3 QoS参数的计算
随着移动通信的不断发展和多媒体业务的日益普及,在移动网络上提供QoS保障的研究逐渐成为一个热点。由于Ad Hoc网络中结点的移动性和无线传输特性,导致对QoS约束的支持远比有线网中困难。本文中,我们把带宽的计算和预留作为QoS参数计算的主要问题。在时隙的Ad Hoc网络中,计算带宽不仅需要得到路径上链路可用带宽信息,而且知道如何安排时隙,所以在Ad Hoc网络中计算带宽是一件很困难的事情,而且是一个NP-完全问题,在这种情况下,往往用启发式路由算法来解决这种问题。在我们将要提出的MQDSR中,使用文献[4]中的启发式路由算法来计算和预留带宽。
4 MQDSR协议描述
针对现在移动Ad Hoc网络中的大多数单路径协议,我们在DSR路由协议的基础,提出了一种多路径的QoS路由协议MQDSR。
4.1 路由的发现过程
当一个源结点需要建立一条路由,但是还没有目的地的路由信息时,它首先广播一个QRP(QoS Route Probe)包到它的邻接结点。当一个结点收到QRP包时,它将对带宽进行计算,为了使用逐跳的方法计算可用带宽,中间结点并不使用路由缓存去直接回复QRP包。下面给出了一个中间结点N处理QRP的算法的伪代码:
IFCheckRedundantPkt(QRP.Source,QPR.QRPSN)||IncludedNodeList(QRP.Node_List,N))
DropAndExit(QRP)
AvailableBandwidth=ComputeBandwidth(QRP,N)
IF AdmissionDecision(AvailableBandwidth, QRP.Bmin)=0)
DropAndExit(QRP)
ELSE
QRP.TTL = QRP.TTLC1
IF QRP.TTL = 0
DropAndExit(QRP)
LogSlotInfo(QRP.Slot_List_Array)
AppendToNodelist(QRP.Node_List, N)
IF N! = QRP.Destination
Forward(QRP)
对于目的结点,当收到第一个QRP包时,它会向源结点发送一个QRR(QoS Route Reply)包,同时保存第一个QRP包记录的路由,然后,目的结点将等待消息ROUTE_WAIT,同时收集其它的QRP控制包。目的地可能接收多个QRP,每一个都代表着一个从源结点到目的结点的可用的路由,我们采用了备份路由机制,因此可以用一个的选择算法,在众多路由当中选取一个最佳的作为首选路由,选取另一条作为备份,该算法如下:
NodeDisjointRoute=FindNodeDisjointRoute()
IF NodeDisjointRoute = 0
LinkMaxDisjointRoute=FindMaxLinkDisjointRoute()
IF LinkMaxDisjointRoute > 1
SelectRoutewithMinHop()
ELSE IF NodeDisjointRoute > 1
SelectRoutewithMinHop()
接着目的结点发送其它的QRR到源结点。因此,我们可以得到两条源结点到目的结点的路由。
中间结点通过QRR包来进行资源的预留。如果源结点能接收到QRR包,一个端到端的资源预留将完成,同时,它会使用第一条建立的路由立即发送数据包。当接收到第二个QRR包时,这时将有两条源结点到目的结点的路由,MQDSR协议中采用的简单的包分配机制,把数据流分配到两条路由上进行传送数据,这样可减少网络负载。
4.2 路由维护
当一个结点发现它到下游结点的链路失效后,它将发送一个MQRP_Route_Error包到源结点。从断开的结点到源结点之间的路由上的所有结点,当它们收到MQRP_Route_Error包时,将释放预留的资源,同时丢弃队列中所有的待发送的QoS请求包。当源结点收到MQRP_Route_Error包时,它将删所有使用断链的路由条目。如果两条路由中,仅仅只有一条路由失效,源结点将使用剩下的那条路由继续发送数据。如果两条路由都已失效,那么源结点将重新发起一次新的路由发现过程。
5 正确性验证及复杂性分析
定理1 由MQDSR选择的路径是无环的。
证明:假设p是一个以D为目的探测帧,而S(P, D)是路由算法选择的路由,若S(P, D)中存在一个环路,则说明在路径S(P, D)上存在一个节点i两次收到了探测帧p并转发p。这与DSR协议中规定的一个节点只能转发一个探测帧矛盾。由于MQDSR遵循了DSR的该机制,因此S(P, D)必定是无环的。证毕。
定理2 在MQDSR协议的路由算法中,时间复杂性为O(2h)式中:h为Ad Hoc网络中各条路径中链路数量的最大值。
证明:在MQDSR协议的路由算法中,需要发送探测帧来建立路由,成功建立一条路径需要花费的时间开销是一个来回的时间。假设消息每经过一条链路花费的时间开销是一个单位,而假设h是被选择的多路径中链路数量的最大值,则MQDSR协议算法路径建立的时间复杂性为O(2h),证毕。
定理3 在MQDSR协议的路由算法中,消息的复杂性为O(3h)。式中:h为Ad Hoc网络中各条路径中链路数量的最大值。
证明:在MQDSR协议算法中,主要使用两个报文Route Request和Route Reply来发现路由,由于本协议路径数目为2,则每次连接的成功建立会有最多3个报文。假设h为Ad Hoc网络中各条路径中链路数量的最大值,则每个报文最多会经历h跳的转发,所以报文消息复杂性为O(3h)。证毕。
6 访真实验与分析
以下仿真是在NS2中进行的,仿真环境及模型如下:
MAC层协议采用的是IEEE 802.11。无线电传播模型是Two-Ray Ground Reflection Model,载频是914MHz,带宽为2M,天线采用OmniAntenna。
运行场景:采用NS的setdest随机产生。50个节点在一个1000×1000的矩形区域按照random waypoint模型移动。每个节点随机的向一个目的地运动,到达后,停留一段时间,继续朝另一个方向移动,移动速度为3m/s到18m/s不等。
数据场景:信源用的是CBR(恒定比特率),包长512bytes。30个信源在仿真的过程中,在不同的时间开始发送数据包。
以下是实验中,不同结点移动速率下的DSR和MQDSR的对比图:
图1显示了,在不同的节点移动速度级别下,MQDSR与DSR的分组投递率的变化情况以及之间的差异。从中可以看出,当节点移动速率越高时,两个协议的性能总体上都有所下降,但另一方面,QMDSR比DSR有更好的分组投递率,这是因为在DSR中,有较多的路由重建过程,网络中产生了更多的数据包的冲突,而在MQDSR中,我们有两条路径可用,既使在其中一条无效的情况吧,还能用另外一条路径继续发送数据,所以在MQDSR协议的网络拥有更好的吞吐量性能。
图1 分组投递率随节点移动速率的变化情况
图2中显示了端到端的延时随节点移动速率的变化情况,相比之下,MQDSR比DSR拥有更少的延时,这是因为,在DSR中路由重建较频繁产生了大量的延时,而数据包的等待也会产生大量的延时,但是在MQDSR中,因为我们有两条路径可用,既使在其中一条无效的情况吧,还能用另外一条路径继续发送数据,所以延时相对较少。
图2 端到端的延时随节点移动速率的变化情况
图3显示了路由控制负载情况,我们可以看到在节点低速率情况下,MQDSR比DSR的负载要稍大,这是因为MQDSR在建立多路径路由过程中,需要较多的控制报文,但是,随着移动节点移动速率的增加,MQDSR的控制负载相对较少,这是因为DSR协议将比MQDSR产生更多的路由重建过程,而在MQDSR协议仅当两条由源结点到目的结点的路由同时失效后,才会重新发起路由发现过程。
图3 路由控制负载随节点移动速率的变化情况
7 结束语
移动Ad Hoc网络是一门新兴研究领域,具有很高的实用价值,并具有极其广泛的应用前景。其中路由协议是移动Ad Hoc网络的核心技术之一,同时也是热门研究的对象。本文针对Ad Hoc网络中DSR路由协议进行了分析,结合多路径路由算法思想,提出了多路径QoS路由协议MQDSR,并进行了仿真实验,仿真结果表明MQDSR路由协议在动态环境中拥有较好的性能。本论文中并没有讨论能量受限的问题,以及结点移动的预测问题,在今后的研究当中,能量,移动预测等也是路由协议中重要一环。
参考文献:
[1] 孙宝林, 李腊元. Ad Hoc网络QoS多播路由协议[J]. 计算机学报,2004,27(10):1402-1407.
[2] 李腊元,李春林. 计算机网络技术[M]. 北京:国防工业出版社,2004.
[3] 肖小玲,李腊元,张翔. 移动Ad Hoc网络QoS路由协议研究,计算机工程与应用,2006.01.
[4] C.R.Lin and J. S. Liu Bandwidth routing in ad hoc wireless networks. In IEEE Globecom, 1998.
[5] C.-R. Lin and J. S. Liu. "QoS Routing in Ad Hoc Wireless networks," IEEE Journal on Selected Areas in Communications, 1999,17(8):1426-1438.
[6] K.N.S.Chen.Distributed quality-of-service routing in ad hoc networks.IEEE Journal on Selected Area in Communications, 1999,17(8):1488-1505.
[7] R.Sivakumar, P.Sinha, and C.Bharghavan, V.a core-extraction distributed ad hoc routing algorithm.Selected Areas in Communications, IEEE Journal on, 1999,17(8):1454-1465.
关键词:传感器;无线传感器;网络路由协议;平面路由协议;层次路由协议
一、引言
近年来,随着现代化科技的蓬勃发展,无线传感器技术也越来越受到人们的关注和重视。无线传感器网络,主要由传感节点、终端节点和观察对象等三个部分组成。就目前来看,无线传感器网络在医疗监护、社区监控、矿井生产及军事侦探等多个领域的应用正日趋广泛。无线传感器网络路由协议,作为无线传感器网络中的关键技术,通过对其基本特征和设计要求,以及平面路由协议和层次路由协议等两大分类的认识和了解,对于无线传感器技术的发展和变革有着不容忽视的促进作用。
二、无线传感器网络路由协议
1.无线传感器网络路由协议的特点
无线传感器网络路由协议,主要是用来处理网络中的传输数据,在无线传感器网络中充当着极为重要的角色。通过对无线传感器网络路由协议的分析,认为其具有以下几点鲜明特点和局限性。
(1)终端节点的特点。传感器的节点数量相对较大,促使其能够作用于计算子系统、通信子系统、传感子系统和能量供应子系统等多个方面,不过同时也加大了建立全局地址的难度,而且各节点的传输能力、处理能力和存储能力也极为有限。
(2)传感器定位特点。在无线传感器中,由于终端节点的数量庞大,且通常是数据聚集的主要地方,因此,在进行传感器定位上,主要工作是由终端节点来完成的。
(3)传感器网络特点。根据不同的应用场景,传感器网络的作用类型也不同。呈现功能多样化的特点。
2.无线传感器网络路由协议的设计
(1)注重路由算法节能。在无线传感器网络路由协议的设计上,降低路由算法的耗能,在网络周期运行、通信功能等方面起着决定性的作用。通过降低算法能量消耗,能够有效延长网络的生命周期。
(2)注重路由算法扩展。随着无线传感器的应用日趋广泛,终端节点的数量也在不断增加,给网络造成了一定程度的繁冗。为此,在设计时注重路由算法扩展性的提高,能够有效地融合新节点,从而提高网络处理数据的能力,延长使用寿命。
(3)注重路由算法容错。注重路由算法容错能力的提高,能够保证在分层结构的终端节点失效时,最大限度减轻簇头的高负载,以免整个网络陷入瘫痪。
3.要求数据融合
通过强化数据的融合,能够减少无线传感器在采集和传递数据方面造成的大量冗余信息,确保网络系统的简洁和信息的精确。
4.无线传感器网络路由协议的类别及分析
根据不同的角度,无线传感器网络路由协议可以划分的类别也不同。通过路由发现策略,可以分为主动路由和被动路由,而从逻辑结构出发,则可以划分成平面路由协议和层次路由协议等两种。
(1)平面路由协议。
扩散法。即传统的网络路由协议,是通过源节点将网络数据副本传输给相邻节点,相邻节点又将其发送给下一相邻节点,以此来达到数据扩散并最终将数据传输给目标节点的方法。具有简单实现、降低网络拓扑信息以及路由算法消耗的能源,且能够适用于要求较高的场合等优势,但从另一个角度来看,这种扩散法很可能会造成信息爆炸、重叠发送信息及盲目使用资源等现象。
SPIN协议。是基于节点间的协商制度和资源自适应机制研发出来的通信路由协议,用于处理扩散法中的缺陷。通过在传输数据过程中,节点与节点之间的协商,能够保证传输的数据的可靠性和可用性。
定向扩散。是采用梯度的形式,对节点传输数据方向进行搜索,以此来获得匹配数据的新协议。运行的终端节点主要用命名机制来描述数据,并通过向所有节点发送被命名数据的任务描述符,从而实现数据的采集。相对来说,这种定向扩散协议,在节能和扩展方面具有更大的优势。
(2)层次路由协议。
LEACH协议。通过采用聚类的形式发展起来的LEACH路由协议,能够不断随机循环执行聚类首节点重构过程,以此来实现无线传感器网络中能量负载均衡分配。其重构过程主要分为类准备阶段和就绪阶段等两部分。通过延长就绪阶段的时间,同时缩短类准备阶段的用时,能够有效地节省资源,进而提高整个网络生存的时长到15%。
PEGAGIS协议。是基于LEACH协议设计的,并在假定终端节点的同构和静止的前提下,通过终端节点发送能量递减的测试信号来找出相邻最近节点。从而明确各节点之间的位置关系,并通过选择所属聚类来完成到sink的链路优化。不但促使整个网络的生存时间是LEACH的两倍左右,同时由于融合数据降低了收发次数,进而节省了系统能源。不过对于链中远距离的节点,则较为容易引起数据延迟。
TEEN协议。该协议的主要特点是实时性,是基于LEACH的聚类结构及其运行模式,采用硬、软阈值来发送检测数据的协议。新硬阈值是由监测数据首次超过设定硬阈值时确定的。当节点发送的硬阈值变化幅度大于软阈值界定范围,则节点重新采集数据设定硬阈值。同时,节点能够通过调节软阈值大小,有效平衡监测精度与系统能耗。TEEN协议的实时性,促使其能快速反应并处理突发事件,但受其自身限制,该协议并不适合持续采集数据的应用环境。
通过对无线传感器网络路由协议相关知识点的分析和思考,能够进一步加深人们对无线传感器网络的研究,推动该技术在国内相关领域的普及和发展。
参考文献:
【关键词】无线传感网络 分簇 多跳路由算法 移动性
1 引言
传感器在计算和无线通讯中广泛使用,如监测外部环境,把感知的数据转化为用户可以理解的信息。传感网络的应用是目前国际科学研究的热点。随着社会的发展,在很多的移动环境应用了无限传感器,如海洋的监测、移动车辆的监测、动物的监测等,因此研究移动环境下的无线传感器网络越来越重要[1-2]。
传感器网络的移动性带来了许多问题。如传感器节点在成功部署之后由于节点的移动随时变换位置,很容易造成拓扑的变化;通信链路建立之后,节点移动很容易偏离最初的位置,从而导致连接断裂、路由中断;节点移动造成数据延迟发送;节点的移动造成路由建立的频率增大,从而增大能量的消耗,缩短了网络生存时间。因此针对移动环境设计支持移动性的路由协议十分必要。
基于分簇的路由协议有很多。LEACH[3]的成簇思想贯穿于其后发展出的很多分簇路由协议中,如TEEN[4]、PEGASIS[5]、APTEEN[6]都基于分簇的路由协议,但在移动性的支持上存在不足,尤其当网络规模增大时,缺陷就更加明显。M-LEACH[7]是基于LEACH提出的支持簇头和成员节点的移动协议,簇头选取时考虑了节点剩余能量、位置及节点的移动速率,但没有在簇的建立阶段解决移动性问题。EMHR[8]算法是簇头在数据传输时可以通过多跳传输,根据权值确定下一跳簇头,这样EMHR协议在网络拓扑结构中平衡负载和降低簇头能量消耗,此协议主要是针对静态网络。
分簇技术可以避免感知节点之间的信息传输,通过簇头数据融合,减少数据冗余,减少发送数据量,降低能耗,更好地支持移动性。多跳传输技术是动态自组织,利用网络中的节点动态建立和维持网络连接。由于多跳技术的独特性,无线传感网络多跳技术得到了极大的关注,大量信息表明多跳路由协议的能耗远低于单跳路由协议。针对现有分簇路由中存在的缺陷,本文提出新的支持移动的簇头多跳路由算法,以降低能耗。
2 EM-CHMR算法
基于LEACH-M算法,在感知节点移动且基站(BS)不移动的环境下,根据节点的移动信息进行分簇,分簇成功之后建立高效的多跳路径,笔者提出能有效地支持移动性的簇头多跳路由策略(EM-CHMR,Energy-efficient Mobile Cluster Head Multi-hops Routing protocol)。此路由策略中,簇首向基站传输数据引入了多跳路由机制,让距基站较近的簇首适当承担一些数据中继转发任务,把直接长距离通信变成间接的多次短距离通信,在支持移动下保证转发簇首有充分的能量来进行数据转发。
2.1 分簇的模型
簇头多跳的简单模型如图1,模型中距离BS较远的簇头可以通过建立多跳路径与BS通信,这样可以降低自身的能量消耗。同时距离BS较近的簇头不需要再进行多跳,可以直接与BS进行通信。模型中感知节点和簇头都可以进行移动,但是BS是固定位置不移动;每个节点的移动速度大小都限制在一定范围内;节点同构,且初始能量相同;传感器节点得到的信息,可以使用GPS或其他位置检测方案;传感器节点的发射功率可以进行调节。
路由算法中利用文献[9]提出的能量消耗模型,节点发射kbit数据到距离为d的位置消耗的能量为:
其中,Eelec表示发端电路运算和处理每比特数据的能耗;εfs和εmp为放大器的系数;d0为临界距离。
2.2 簇头的选取
簇头选取算法是基于M-LEACH协议提出的,网络模型是一个均匀的网络,簇头的数量确定方式与M-LEACH相同。根据簇头数量把整个区域划分为子区域,然后为每个区域选取簇头。首先按照剩余能量利用阈值Eselect进行筛选,避免节点剩余能量不足造成早死现象。为了让簇头均匀分布并对整个传感网络实现完全覆盖,把整个区域分成M个子区域,在每一个子区域中选取一个簇头。假设第j子区域节点数Nj,每个节点坐标为(xi,yj),速度为vi。簇头的最佳位置S0计算方式如下:
移动方向用θi(0O≤θi≤180O)表示,意为节点i的移动方向和连接节点指向最佳位置的直线形成的夹角(速度和直线的最小夹角)。最佳选择则是节点移动方向是S0,即夹角越小越好。角度则是处理后的角度,其中θt是角度阈值。
如果簇头移动速度过快则容易造成簇的破坏,移动速度慢则适合整个网络的移动速度。式(4)表示节点i处理后的速度,其中vt是速度阈值,vi为节点i的速度。
节点i为簇头的代价函数为:
由式(5)看到,、和变小时值也变小,则是节点i的速度因子,因此最小的节点为簇头最理想的节,若存在多个节点,取最小值。
2.3 簇的形成
簇的形成阶段,就是在感知节点选择簇头键入,并在其中形成簇。簇头和感知节点的移动使得节点与簇头位置关系的变化很难计算。为了降低复杂性,把速度大小和速度方向一起分析,利用速度和角度得到速度因子。
其中,vi根据阈值计算,θi是感知节点移动方向与连接感知节点、簇头间直线所形成的夹角,θ0是簇头移动方向和连接簇头、感知节点的直线所形成的夹角。可以看出,移动因子不是两个速度的矢量和,而是要考虑到两个速度的移动方向变化,才能够简单高效地对节点移动性进行评估。
基于EECS[10]协议,本文提出新的通信代价函数:
其中E=En_init/En_current,w是具体环境决定的权值,CHi是区域i的簇头,BS为基站,d是距离,f是两者之间的通信代价,EX为期望。Si为感知节点。Cost(i,j)表示成员节点i到簇头j的通信代价,在簇的形成过程中,每个成员节点选取通信代价最小的簇头加入簇区域。
2.4 多跳路径建立
在数据传输中选择下一跳的簇头,对簇头能量消耗有重要的影响。如果BS在簇头传输的有效范围内,簇头将直接与BS进行通信,否则通过其他簇头进行多跳传输。
为了多跳能量消耗,计算通过簇头跳一次的情况,即从簇头i到j再到BS。设簇头i和j的距离为d(i,j),j和BS的距离为d(j,S)。根据无线通信能量消耗模型,总的能量消耗模型ET为:
可看出能量消耗的影响因素为d(i,j)和d(j,S),所以,簇头i发送消息经过n个簇头到BS的能量消耗为:
式(10)充分体现了距离对簇头能量的消耗的影响,因此可用距离的平方和作为权值函数的一个重要因素。
由于无线传感器网络中节点是移动状态,尤其在簇头多跳网络中,簇头的移动很容易对多跳路径造成破坏,因此在多跳路径建立过程中要选取一条比稳定且受速度影响较少的路径。在簇头多跳路径中簇头的移动可以缩短整个路径的距离,也有可能使得路径遭到破坏。
由图2看到簇头H0经过(H1, H2, H3)到达基站BS,(S1, S2, S3)分别为簇头到直线OS的距离,θ为H3移动方向与S3形成的角度。在多跳路径中最好的效果是三个簇头向OS移动,并且三个簇头和OS的距离波动不要太大,因为波动过大会造成传输距离加大。因此要(0, S1, S2, S3, 0)(前后两个0分为H0和BS到OS的距离)的方差来衡量节点的波动,它们的期望衡量严重偏离OS的大小。由于节点的移动造成簇头位置的不断变化,为了较好地反应簇头的移动,要充分考虑簇头节点的移动速度大小和方向。Si在OS左面值为正,右面值为负。角度则是指向OS的锐角,反向为钝角。当多跳经过簇头数为n时,计算(Si+vitcosθ)的期望:
计算对应方差:
其中t是根据轮到时间设定的值,设为半个轮时间。则新的权值函数如下:
Ei_residual是簇头i的剩余能量,Ei_init是初始化能量。为了控制σ和es值极端情况(只等于0),约束如下:
在簇头选取成功时,向周围广播信息通知普通节点,每一个簇头会接收到周围相邻的信息,信息包括ID、移动信息、剩余能量等。每个簇头把周围的信息进行存储,然后根据收集的邻居节点找出到BS的所有路径,利用权值函数(11)进行计算,权值最小的路径的第二个簇头作为下一跳节点。利用此算法,簇头都可以找到下一跳节点。如果某簇头能量不足作为多跳节点时,就向周围发送取消作为多跳节点的信息,周围簇头把该节点记录信息取消,从新选取下跳节点。
3 实验结果
实验无线传感器网络有100个感知节点组成,分布在100m*100m的区域中,基站BS随机放在此区域中。速度范围为(0, 2)m/s,速度阈值为0.3m/s,角度阈值为10o,方差和期望的阈值为1,相关参数如表1:
图3表示随着时间延长,感知节点逐渐出现了死亡现象,EM-CHMR协议的死亡节点出现较晚,两种节点死亡数量在300s之后大量出现。在600s之后新协议的存活节点数量明显高于M-LEACH协议的节点存活数量,表明簇头多跳网络较好地均衡了簇之间的能量,降低了感知节点的死亡数量。
图4展示了能量消耗,可以明显看出M-LEACH能量已经消耗远高于EM-CHMR,在900s时M-LEACH能量消耗完毕,而EM-CHMR还有能量剩余,从而有效地延长了网络生存时间。能量消耗和存活节点数量的变化充分体现了支持移动的簇头多跳路由协议能够较好支持移动,平衡节点能量,降低能耗,延长整个网络的存活时间。
4 结束语
本文针对无线传感器网络的移动性,基于LEACH提出了EM-CHMR路由算法,保持了按轮进行分簇,对簇头节点采用了多跳算法,提出了信息权值函数及建立多跳路径算法。仿真结果证明该方案支持移动的簇头多跳路由策略,使得能量消耗均衡地分布在各节点上,保证了数据尽快地传输到基站,弥补单跳的不足,从而使网络寿命得到延长。支持移动的簇头多跳路由协议的维护机制对簇和路径的生存时间有很大的影响,因此,为了使移动传感网络中更好地降低能耗,还需要在路由维护机制方面展开更深一步的研究。
参考文献:
[1] AKYILDIZ L F, SU WEILIAN, CIRCI E. A survey on Sensor networks[J]. IEEE Communications Magazine, 2002,40(8): 102-114.
[2] YICK J, MUKHERJEE B, GHOSAL D. Wireless sensor network survey[J]. Computer Networks, 2008,52(12): 2292-2330.
[3] HEINZELMAN W R , CHANDRAKASAN A, BALAKRISHNAN H. Energy-efficient communication protocol for wireless micro-sensor networks[C]. Proceedings of the 33rd Annual Hawaii International Conference on System Sciences(HICSS), Maui, HI, 2000: 1-10.
[4] MANJESHWAR A, AGRAWAL D P. TEEN: a routing protocol for enhanced efficiency in wireless sensor networks[C]. Parallel and Distributed Processing Symposium, Proceedings 15th International, 2001: 2009-2015.
[5] LINDSEY S, RAGHAVENDRA C S. PEGASIS: power efficient gathering in sensor information systems[C]. Aerospace Conference Proceedings, 2002: 1125-1130.
[6] MANJESHWAR A, AGRAWAL D P. APTEEN: a hybrid protocol for efficient routing and comprehensive information retrieval in wireless sensor networks. Parallel and Distributed Processing Symposium[C]. Proceedings of the International, 2002: 195-202.
[7] LAN TIEN NGUYEN, DEFAGO X, BEURAN R, et al. An Energy Efficient Routing Scheme for Mobile Wireless Sensor Networks[C]. Proceedings of the 2008 IEEE international symposium on wireless communication systems (ISWCS), 2008: 568-572.
[8] HUANG WEN WEN, PENG YA LI, WEN JIA, et al. Energy-Efficient Multi-hop Hierarchical Routing Protocol for Wireless Sensor Networks[C]. 2009 International Conference on Networks Security Wireless Communications and Trusted Computing, 2009: 469-472.