无线传感器网络的能量有效性网络层路由算法

1、无线传感器网络的能量有效性网络层路由算法         摘  要  本文提出了一个能量有效性的适用于无线传感器网络的网络层路由算法最小跳数路由算法(MHRA )。MHRA算法分为两个阶段；在感知任务交付阶段，节点通过洪泛感知任务建立路由；在感知数据交付阶段将感知数据沿该路由返回收发器。实验结果表明MHRA路由算法通过采用多跳通信工作方式、按需驱动的路由策略、使用传感器节点到Sink节点的最佳路径和次最佳路径、数据融合等方案，减少了路由的建立和维持开销，有

2、效地实现了能量节省，实现了算法的简单性、正确性、能量有效性和健壮性。    关键词  无线传感器网络、路由协议、能量有效性、能量管理策略 1  算法概述    MHRA路由算法采用按需求驱动的路由策略，采用多跳路由通信模式，网络应用者通过Sink节点洪泛查询，激活一个工作节点子集，并在洪泛过程中建立路由。算法可分为两个阶段：感知任务交付和感知数据交付阶段。    在感知任务交付阶段，Sink节点向与其相邻的传感器节点发送感知任

3、务查询包，传感器节点收到查询包后，确定自己是否有Sink节点需要的感知数据，如果没有就继续向其相邻节点洪泛查询包，在洪泛查询过程中，收到查询包的各个传感器节点根据查询包的信息确定其距离Sink最近的上一跳节点，完成路由建立。在感知任务交付阶段，由于查询包是通过洪泛传播到网络中去的，所以要解决洪泛的信息“爆炸”和“重叠”问题，以减少不必要的能量损失。路由的建立是通过每次洪泛查询的过程中完成的，因此，MHRA路由算法属于反应路由策略。当收到查询包的传感器节点有Sink节点需要的感知数据时，进入感知数据交付阶段，这时传感器节点不再洪泛查询包，并利用感知任务交付阶段建立的路由信息，将感知数据返回给其距

4、离Sink的上一跳节点，使感知数据沿着一条最佳路由返回Sink。为了解决洪泛的信息爆炸问题，Sink节点发送的查询包中，包含跳点计数器(即最大跳点数*，根据网络尺寸、节点密度等因素确定最大跳点数)，每个收到查询包的节点将跳点计数器的值减1，如果为0则不再洪泛该查询包，同时拥有匹配感知数据的传感器节点也不再继续洪泛查询包，因此，查询包不是洪泛到整个网络，MHRA路由算法只激活了一个工作节点的子集，能量消耗只集中在这个节点子集上，有效地降低了整个网络的能量损耗。另外，在感知数据交付阶段，通过采用数据融合技术，消除冗余的感知数据，虽然产生一定的数据处理的能量开销和网络延迟，但可以有效地降低通信量，降

5、低了无线通信的能量损耗。    能量有效性的主要目的是延长网络生命期，MHRA路由算法可以通过激活一个有限的节点子集、建立传感器节点到Sink节点的最佳路径、采用多跳通信模式和数据融合技术，有效地实现能量节省。2  MHRA路由算法的工作原理与描述    MHRA路由算法是基于多跳路由通信模式的以数据为中心的路由选择算法。MHRA算法通过在查询洪泛中建立数据源节点到Sink节点间的最佳路径，并在感知数据沿着路径返回Sink节点时利用了简单的数据融合技术，有效地实现能量节省。2.1 路由

6、算法工作过程的两个阶段    如前文所述，MHRA路由算法的工作过程可以分为两个阶段：感知任务交付阶段和感知数据交付阶段。在感知任务交付阶段，应用者通过Sink节点向网络洪泛一个查询包，收到查询包的传感器节点利用查询包中的内容建立到Sink节点的反向路径；在感知数据交付阶段，拥有匹配数据的传感器节点通过在感知任务交付阶段建立的路径，向Sink节点返回感知数据。    感知任务交付阶段的主要任务是向洪泛查询包，并在洪泛查询包的过程中建立数据源节点到Sink节点的最佳路由。为了实现能量有效性，在感知任务交付阶段MHRA

7、路由算法要解决的主要问题是：查询包在洪泛过程中的信息爆炸和重叠；如何通过查询包洪泛建立最佳路由。        在网络的初始阶段，所有的传感器节点处于休眠状态，网络应用者通过Sink节点向网络发送一个查询，这里的“查询”在MBA路由算法中被理解为一次数据请求，查询是对一个物理目标的物理属性进行的数据采集请求，如某个目标或对象的位置、温度等。    Sink节点首先根据应用者的数据请求内容建立查询包，设置QueryID(查询编号)；设置QueryData(数据请求内容)字段；将

8、HopCount(跳点计数器)字段设置为MHRA路由算法要求的最大跳点数(即允许的最大路径长度)：将SourceNodeID(发送节点ID)设置为Sink：将MinHopToSink(距离Sink节点最小跳数)字段设置为O。Sink节点向网络中与其相邻的传感器节点发出查询包后，进入感知任务交付阶段。         (1)查询包洪泛    传感器节点收到查询包后，如果满足以下条件则向其相邻节点转发查询包：查询包HopCount(跳点计数器)字段的值大于0；根据节点的

9、Que行Buffer(查询缓冲一)确认该查询包没有收到或转发过：根据查询包的QueryData(数据请求内容)字段的内容确认没有匹配数据。洪泛查询包的传感器节点修改查询包中的SourceNodeID(发送节点标识)和MnHopToSink(距离Sink最小跳数)字段，然后将查询包发送到它的相邻节点。    在查询洪泛过程中，算法需要解决洪泛的信息爆炸问题，解决的办法是每一个收到查询包的传感器节点，将查询包中的HopCount(跳点计数器)字段中的值减1，当其值为0时，传感器节点丢弃该包。在查询洪泛时，还要解决信息重叠问题，即当节点收到重复的查询包时，应丢

10、弃该包，解决的办法是在节点中维持一个QueryBuffer(查询缓冲)，每个查询包中都包含有该次查询的编号，利用这两个数据结构可以确定该查询是否己经接收、响应或转发过。    (2)路由建立    建立数据源节点到Sink节点的最佳路由，是MHRA路由算法的核心问题。最佳路由的建立是通过洪泛查询包的过程中完成的。在特定的网络拓朴和节点密度环境下，一个数据源节点到Sink节点会有存在很多可以交付数据的路径。    为了建立最佳路由，传感器节点维护一个MinHopBuffer(最

11、小跳数相邻节点缓冲)，初始时，该缓冲中的最小跳数字段为一个极大值或无穷大，上一跳节点字段为空。每一个收到查询包的节点，如果满足洪泛该查询包的条件，则修改查询包中的SourceNodeID和MinHopToSink字段，然后向相邻节点发送该查询包。它的相邻节点在接收到这个查询包后，会检查MinHopToSink字段，并与MinHopBuffer中的Minhop(最小跳数)字段进行比较，如果查询包中的MinHopToSink字段的值小于MinHopBuffer中MitiHop字段的值，则将查询包中的SourceNodeID和MinHopToSink两个字段内容记录在MinHopBuffer的Pre

12、pNodeID和MinHop字段，并修改查询包中的SourceNodeID为自己的网络标识，修改查询包中的MinHopTo$ink字段为最小跳数相邻节点缓冲中的MinHop字段值加1。    根据上面的描述，MHRA路由算法确定最佳路径的标准是跳点数最短的路径，显然，可能在数据源节点到Sink节点之间存在着多条跳点数相同且最短的路径，这些路径可能交叉也可能互不交叉。如果只选择其中一条路径作为感知数据交付路径，由于传感器网络动态性强，因为传感器节点的不断移动和节点的能量损耗，路径可能在感知数据返回前成为失败路径。为了保证路由算法的健壮性，可能考虑在增加传感

13、器节点最小跳数节点缓冲的缓冲深度，形成健壮的多路径交付。       感知数据交付阶段的主要任务是将匹配数据请求的感知数据沿着感知任务交付阶段建立的路由交付给Sink节点，如果是多路径交付，在感知数据交付阶段还要通过数据融合消除冗余的匹配感知数据，以减少通信量，降低通信能量消耗。    当收到查询包的传感器节点有Sink节点需要的感知数据时，进入感知数据交付阶段，这时传感器节点不再洪泛查询包，并利用感知任务交付阶段建立的路由信息，即数据源节点的最小跳数缓冲中记录的MinHop和Prep

14、NodeID，将感知数据返回给其返回Sink节点路径的上一跳节点，使感知数据沿着该路径返回Sink节点。    如果在感知任务交付阶段建立的是一个多路径交付的路由，如果这是一个交叉多路径，在路径交叉的节点完成数据融合，消除冗余数据。根据前面的假设，对于同一个查询来说，可能存在多个数据源节点拥有匹配的感知数据，该感知数据是完全冗余的，因此，在路径交叉的节点，在接收到感知数据包时，根据数据包中的查询编号，检查自己的查询缓冲，在对应的查询编号记录中的相应字段，可以确定这个查询的匹配感知数据包是否己经转发过，如果己经转发，则丢弃后来的数据包，以减少网络中的冗余数

15、据，减少通信量。因此带来的通信能量的节省是远远大于数据融合的数据处理能量开销。 2.2 最佳路由建立过程    在MHRA算法中，最佳路由即是最小跳数路由。最佳路由的建立是在感知任务交付阶段，通过在洪泛查询包过程中，由传感器节点根据查询包中包含的洪泛信息建立的。    为了描述最佳路由建立过程，考虑这样一个例子，在这个例子中，有S个节点，分别标识为1，2，3，4，5。节点、Sink节点和目标(Object)之间的位置关系如图1所示。图中虚线圆表示节点的通信半径，带箭头的直线表示查询包的洪泛方向，

16、带箭头的弧线表示感知数据包的返回方向。在这个例子中，根据节点通信范围，查询包将沿着“ Sink-> 1->2->3->4”和“Sink-> 1->2->3->5->4”这两条路径传播到节点4，感知目标或事件(Object)在节点4的感知范围内，节点4将放弃转发查询包，进入感知数据状态，并将感知数据沿着其中的一条路径返回。对于节点4来说，存在两条可以返回Sink的路径，MHRA算法将选择其中跳点数最小的节点返回，即“4->3->2-> 1->Sink”返回感知数据。下面利用这个例

17、子描述一下最佳路径的建立过程。图1  单路径最佳路由的建立过程    (1)网络应用者通过Sink节点提出查询或数据请求。    (2)Sink节点根据应用者的数据请求形成查询包，填写查询包的QueryID和QueryData字段。设置HopCount(跳点计数器)字段为算法要求的最大跳点数，设置SourceNodeID(发送节点标识)字段为“Sink”，设置MinHopToSink(距离Sink节点的最小跳数)字段为O。    (3)Sink节点将查询包

18、发送到与它相邻的传感器节点。    (4)节点1收到查询包。    将查询包中的HopCount(跳点计数器)的值减1，结果大于0；    根据QueryBuffer(查询缓冲)和查询包中的QueryID字段，确定该查询包没有收到或转发过；    根据查询包中的QueryData(数据请求内容)字段，确认没有匹配数据：    检查查询包的SourceNodeID(发送节点标识)字段的值为Sink，

19、即自己是Sink节点的相邻节点，修改MinHopBuffer(最小跳数缓冲)中的MinHop(最小跳数)字段值为1，修改PrepNodeID(上一跳节点标识)为Sink；    修改查询包内容，设置SourceNodeID(发送节点标识)字段为节点1的标识，将MinHopToSink(距离Sink节点的最小跳数)字段值加1。    转发查询包给相邻节点。    (5)节点2收到查询包。    步骤同节点1。  

20、60; 检查查询包的SourceNodeID(发送节点标识)字段的值不是Sink修改MinHopBuffer(最小跳数缓冲)中的MinHop(最小跳数)字段值为查询包中MinHopToSink(距离Sink节点的最小跳数)字段和MinHop字段中的最小的值，修改PrepNodeID(上一跳节点标识)为查询包SourceNodeID(发送节点标识)字段的值。    修改查询包内容，设置SourceNodeID(发送节点标识)字段为节点2的标识，其余操作同节点1。    转发查询包给相邻节点。 &#

21、160;  (6)节点1和节点3收到查询包。        节点1通过检查查询包中的QueryID确认已经转发过该查询，然后将MinHopBuffer中的MinHop字段和收到的查询包的MinHopToSink字段比较后，维持自己的最小跳数相邻节点缓冲的内容，并将收到的查询包丢弃。    节点3操作与节点2类似，修改自己的数据结构和查询包后，将查询包转发给相邻节点。    (7)节点2、节点4和节点5收到查询包。&#

22、160;   节点2通过检查查询包中的QueryID确认己经转发过该查询，然后将MinHopBuffer中的MinHop字段和收到的查询包的MinHopToSink字段比较后，维持自己的最小跳数相邻节点缓冲的内容，并将收到的查询包丢弃。    节点5操作与节点2， 3类似，修改自己的数据结构和查询包后，将查询包转发给相邻节点。节点3和节点4会收到节点5转发来的查询包，节点3通过检查查询包中的QueryID确认己经转发过该查询，然后将MinHopBuffer中的MinHop字段和收到的查询包的MinHopToSink

23、字段比较后，维持自己的最小跳数相邻节点缓冲的内容，并将收到的查询包丢弃。    (8)节点4将分别收到节点3和节点5发来的两个查询包。    节点4收到由节点3或节点5发来的第一个查询包后，利用查询包中的内容，填写最小跳数相邻节点缓冲中的相应字段的内容。    节点4收到由节点3或节点5发来的第二个查询包后，根据查询包中的路由建立信息，确定是否修改最小跳数相邻节点缓冲中相应字段的内容，并将在查询包丢弃。显然，处理完第二个查询包后，节点4的最小跳数相邻节点缓冲中的PrepNod

24、eID字段的值是节点3的标识，Minhop(最小跳数)字段的值为3，即节点4将选择节点3作为路由的上一跳节点。    根据查询包中QueryID(查询标识)字段，确认自己拥有匹配数据，进入感知数据状态，并将感知数据通过路径“4->3->2->1->Sink”返回给Sink节点。在这个例子里面，通过查询包的洪泛，建立了一条最小跳数路由，即MHRA算法的最佳路由。显然，这个例子建立的是一个单路径数据交付的路由。这种单路径路由对于固定节点的无线传感器网络，是具有很高的应用价值的。3  小结    本文提出了一个能量有效性的适用于无线传感器网络的网络层路由算法最小跳数路由算法(MHRA)。MHRA路由算法将一个传感任务的完成过程分为两个阶段：感知任务交付阶段和感知数据交付阶段。在感知任务交付阶段，Sink节点发送查询，收到查询包的传感器节点根据查询包中的信息建立自己到Sink节点的最佳路径和次最佳路径：在感知数据交付阶段，拥有匹配查询的感知数据的传感器节点沿着在上一阶段建立的路由，将感知数据返回给Sink节点。MHRA路由算法通过采用多跳通信工作方式、按需驱动的路由策略、使用传感器节点到Sink节点的最佳路径和次最佳路径、数据融合等方案，减少了