新闻动态
无线传感器网络路由协议(上)
无线传感器网络路由协议(上)  


     此外,针对不同传感器网络应用,研究人员也提出了许多不同的路由协议,大体可分为基于多径和能量感知的路由、基于可靠的路由、基于查询的路由、基于协商的路由、基于QoS的路由和基于位置的路由等。除了上面分类外,像传统的无线Ad hoc网络和无线Mesh网络,无线传感器网络的路由协议还可分为主动的、按需的和混合的路由协议。还有一类特殊的路由协议叫协作路由(有的也叫基于相干的路由协议),即节点发送数据到某个中心节点,在那儿进行数据汇聚和融合,因而可降低路由在能耗上面的代价。还有很多其他路由协议是依赖于时间和位置信息的。下面重点讲述几类传感器网络典型应用的路由协议。

2  基于多径的能量感知路由

能量感知就是根据节点的可用能量(即节点的当前剩余能量)或传输路径上的能量需求,选择数据转发的路径。能量感知路由策略主要有以下几种。

① 最大剩余节点能量路由。从数据源节点到汇聚节点的所有路径中选取节点剩余能量之和最大的路径。

② 最小能耗路由。从数据源节点到汇聚节点的所有路径中选取节点能耗之和最小的路径。

③ 最少跳数路由。从数据源节点到汇聚节点的所有路径中选取跳数最少的路径。

④ 最大最小剩余节点能量路由。每条路径上有多个节点,且节点的可用剩余能量不同,从中选取每条路径中可用能量最小的节点来表示这条路径的可用能量。

    上述能量感知路由算法策略需要节点掌握整个网络的全局信息,然而多数传感器网络节点只能获取局部信息,因此这些方法只能在理想情况下讨论。

传统网路的路由机制通常选择源节点到目的节点的最小跳数单径路由传输数据,但在无线传感器网络中,频繁使用同一条路径传输数据容易导致该路径上节点能耗过快而提前失效,从而整个网络分割成互不连接的孤立网络,造成网络寿命缩短。C.Rahul等人提出了基于多径的能量感知路由算法。该算法在源节点和目的节点建立了多条路径,根据路径上节点通信能耗和剩余能量状况给每条路径赋予一定选择概率,由于该概率与能量相关,可将通信能耗分散到多条路径上,从而使得数据传输可以均衡消耗整个网络的能量,最大限度延长网络的使用寿命。该多径能量感知路由协议包括三个阶段:路由建立阶段、数据通信或数据传播阶段和路由维护阶段。每个节点都知道到达目的节点的所有下一跳节点,需要计算选择每个下一跳节点传输数据的概率,该概率与节点能量通信代价的倒数成正比。概率的计算是通过节点到目的节点的通信代价来估算的。由于存在多径,所以该代价值应当是

各个路径的加权平均值,用符号Cost(Ni)来表示节点i到目的节点的通信代价。该协议过程如下:  

① 目的节点广播路径请求消息,启动路径建立过程。其中,路径请求消息包含一个代价域,初值设为0,即Cost(ND)=0,表示发出该消息的节点到目的节点的路径上的能量消息。

② 当节点收到邻居节点发送的路径请求消息时,和该邻居节点相比,仅当自己距离源节点更近,且距目的节点更远情况下才需转发该请求,如式(3-3),否则丢弃该请求消息。


③ 当节点准备转发路径请求消息时,需计算新的代价值以更新旧的值。如路由请求消息从节点Ni到Nj时,路径的通信代价为原节点Ni的代价加上两节点间的通信能耗,即式中,CNi,Nj表示发送的数据经由节点Ni到目的节点的通信代价;Econsumed(Ni,Nj)表示节点Ni和Nj之间的能耗,其计算公式为式中,eijα表示节点Ni到Nj之间的直接通信能耗,包括发送部分Etx和接收部分Erx,即eijα=Etx+Erx;Riβ表示节点Ni的剩余能量所占比例,即。该度量准则同时考虑了邻居缓存数据的信息、节点的能量再生率和数据的相关性。

④节点丢弃通信代价高的路径,仅当邻居节点Ni更低代价的路径才会加入到节点Nj的转发路由表中FTj的条件是:

⑤ 节点Nj会为转发路由表中每个邻居Ni指定一个概率,该概率与通信代价成反比:

⑥ 每个节点Nj都由大量邻居数路由分组到目的地,Nj然后通过转发路由表中的邻居计算到达目的节点的平均通信代价,并更新原有消息中的代价值,然后向邻居节点广播该路由建立请求消息:


⑦平均代价Cost(Nj)在路由请求分组的代价域里设置,正如步骤②,并随着请求分组一路沿着向着源节点处的路径转发。该协议在数据通信阶段,对于每个收到的分组,节点根据概率选择一个下一跳节点,并将分组转发给该节点。路由维护阶段是通过节点周期性从目的节点到源节点实施泛洪查询来维持所有路径的有效性。

3  基于查询路由

    基于查询的路由通常是指目的节点通过网络传播一个来自某个节点数据查询消息(感应任务),收到该查询数据消息的节点又将匹配该查询消息的数据发回给原来的节点。一般这些查询是以自然语言或者高级语言来描述的。定向扩散(Directed Diffusion)就是一种基于查询的路由协议。基站节点或者汇聚节点发送兴趣消息(Interest Message)执行查询任务,通过泛洪方式传播消息给所有传感器节点。随着兴趣消息在整个网络传播,协议逐跳地在每个传感器节点上建立反向的从数据源节点到基站或汇聚节点的传输梯度。当源节点有感兴趣的数据时,就沿着兴趣消息梯度方向发送数据到基站或汇聚节点。定向扩散协议分为三个阶段:周期性的兴趣消息扩散阶段、传输梯度建立阶段和发送数据和路径加强阶段。

1.兴趣消息扩散阶段

    基站或汇聚节点周期性地向周围邻居广播兴趣消息。消息中含有一些重要参数,如数据发送速率、任务类型、目标区域以及时戳等。每个节点都在本地保存一个兴趣列表,其中专门存在一个表项用来记录发送该兴趣消息的邻居节点、数据发送速率和时戳等相关信息,以建立该节点向汇聚或基站节点传输数据的梯度关系。每个兴趣消息可能对应多个邻居节点,每个邻居节点对应一个梯度信息。另外,该表项还存在一个字段用来表示该表项的有效时间,超过该时间,节点就删除该表项。当收到邻居节点发送的兴趣消息时,首先检查兴趣列表中是否存在参数类型与收到兴趣相同的表项,如果有,就更新表项有效时间值;如果仅仅是参数类型相同,但不包含发送该消息的邻居节点,就在对应表项中添加该邻居节点;对于其他情况,都需建立一个新表项来记录这个新的兴趣,如收到的兴趣消息和刚刚转发的一样,则丢弃该信息,以免消息循环,否则,就转发收到的兴趣消息。

2.传输梯度建立阶段

    当源节点采集到的数据与执行查询任务的兴趣消息匹配时,就将其发送到梯度方向上的邻居节点,并按梯度上的数据传输速率设定相应的数据采集速率。由于传播兴趣消息是采用的广播机制,故基站或者汇聚节点可能会收到经过多个路径的相同数据。对于中间节点,如收到转发的数据时,首先检查兴趣列表的表项,如没有匹配项就丢弃该数据。如果有,则检查与该兴趣消息对应的数据缓存(Data Cache)。如缓存里面存在与接收数据相匹配的,表明已经转发过该数据,并将其丢弃;否则,再检查表项中的邻居信息。如记录的邻居节点发送速率超过接收的数据速率,就全部转发接收的数据;否则,按照比例转发。转发的数据都会在缓存中保留一个备份,且记录转发时间。

3.发送数据和路径加强阶段

    当通过前面的兴趣扩散阶段,源节点到基站或汇聚节点的数据传输基本路径建立起来。然后,源节点以较低速率采集和发送数据以建立梯度,不过此时建立的梯度称为探测梯度(Probe Gradient)。当基站或汇聚节点收到源节点发来的数据后,立刻启动建立到源节点的加强路径,随后数据沿着加强路径以较高速率传输数据。加强后的梯度称为数据梯度(Data Gradient)或数据传播梯度。

    路径加强优化的原理就是,当邻居节点收到路径加强消息(包含新设定的较高发送数据速率)时,如判断该消息是一个已有的兴趣,仅仅是增加了数据发送速率的话,就确定这是一跳路径加强消息,从而更新相应兴趣表项到邻居节点的数据发送速率。依次类推,采用同样方法选择加强路径的下一跳邻居节点。为了达到更低的能耗,在加强路径上面有必要采用数据汇聚方法进一步处理数据(如加倍压缩等)。值得注意的是路径加强标准有很多,如数据传输延迟、数据转发的业务流量以及数据传输的稳定性等。如果标准选得不同,可能对该协议性能带来显著的影响。

    定向扩散路由协议是一种典型的以数据为中心的查询路由。为了适应拓扑和节点失效等网络状态变化,定向扩散路由协议采用了周期性的兴趣消息扩散、建立数据传输梯度和发送数据及加强路径三个阶段的策略。然而不足的是,路径建立时的兴趣消息扩散要执行一个泛洪广播操作,时间和能量开销较大,特别是当底层的MAC协议采用睡眠机制时可能造成兴趣消息建立的不一致。

    另外一种基于查询的路由协议叫谣传路由(Rumor Routing),是D.Braginsky等人提出的适用于数据传输量较小的无线传感器网络高效路由协议。在某些特定的应用场合,传感器节点采集或传输的数据量很少或者并不知道事件发生的区域,如果采用定向扩散路由机制,并不能实现高效路由的目的。而谣传路由由于采用了查询消息的单播随机转发机制,克服了泛洪广播消息建立转发路径带来大量路由开销的问题。该协议基本思想就是事件监测区域的感应节点产生代理消息(Agent),代理消息沿着随机路径向邻居节点扩散传播,如图3-12所示。与此同时,基站或汇聚节点发送的查询消息也沿随机路径在网络中传播。当查询消息和代理消息的传播路径交叉在一起时,就会形成一条基站或汇聚节点到事件监测区域的完整路径。实质上谣传协议就是通过使用一系列生存期较长的代理(Long-lived Agents)来产生直接到达事件监测区域的路由路径。

下面详细介绍一下谣传路由协议的基本过程。

① 每个节点维护两个列表:邻居列表和事件列表。其中事件列表中每项都记录着事件相关的信息,包括事件名称、到事件区域的跳数和到事件区域的下一跳邻居等信息。当传感器节点在本地监测到一个事件发生时,就在事件列表中添加一个表项,并设置相应的事件名称和跳数等信息,同时根据一定的概率产生一个代理消息。

② 代理是指包含生存期等事件相关信息的分组,用来将携带的本地事件信息传播给它经过的每一个传感器节点,另外还有执行汇聚事件的功能。对于收到代理的节点,首先检查事件列表中是否有相关事件的表项。如存在相关表项就比较代理和表项中的跳数值,当代理中跳数小时,就更新表项中的跳数值,否则就更新代理中的跳数值。如事件列表中不存在该事件相关表项,就增加一个表项来记录代理消息携带的事件信息。然后,节点将代理中的生存期值减1,并在网络中随机选择邻居节点转发该代理,直到其生存期值减小为零。通过代理在其生存期传播过程,逐渐形成一段到达事件发生区域的路径。网络中任何节点都可产生一个对特定事件的查询消息。如果节点事件列表中存有该事件相关表项,表明节点处于到达事件区域的路径上,查询消息就可沿着该路径转发,否则节点随机选择邻居节点转发查询消息。与此类似原理,中间节点继续转发查询消息,并记录查询消息中的相关消息,从而形成了查询消息的路径。同样,查询消息也具有生存期,以避免环路问题。

③ 当代理与查询消息交叉时,交叉节点会沿着查询消息的反向路径将事件消息传送到查询节点。如查询节点在一段时期内没有收到事件消息,就认为查询消息没有到达事件区域,可选择重传或泛洪查询及放弃等方法,泛洪方法代价较高,一般不要轻易采用。

    相比定向扩散路由,谣传路由协议最大的贡献就是减少了路由建立的开销。但由于采用随机方式产生的路由路径不一定是数据传输的最优路由,其中最优参数严重依赖于拓扑,并且可能产生环路路由问题。下面给出了谣传路由算法的主要伪代码。

相关新闻文章