武汉职业技术学院 蔡 静

1.介绍

一个最简单的无线传感网络被定义为一个由用节点来表示的设备构成的网络(可能是小规模和低复杂度的)，这些节点能够感知环境并通过无线链路传达从被监测领域获取的信息；数据可能通过多跳中继转发给本地的或者通过网关与其他网络连接的基站(汇聚)节点来传递[1,2]。每一个节点有五个部分，如图1所示：

(1)通信单元。

(2)控制单元。

(3)执行单元。

(4)存储单元。

(5)电源。

图1 传感器节点

节点从环境感知数据，然后将其处理并发送到基站。

这些节点既可以将数据发送给基站，又可以发送给其他传感器节点，这样数据最终到达基站，如图2所示。在大部分应用中，这些传感器节点只有有限的能源供应和通信带宽。这些节点由一些不可替代的电池供电，因此网络寿命取决于电池损耗。创新技术已用于有效的限制能源和带宽资源，以最大化网络寿命。这些技术依赖于网络协议中所有层级的精准的设计和管理。例如，在网络层非常需要找到一个发现节能路由的方法，并从传感器节点中继转发数据给基站。

图2 无线传感网络图

每一条消息被指定到达基站的路径对于网络的生命周期非常重要。换句话说，影响网络生命周期的因素有很多，比如网络的拓扑结构、传输速率、传输范围以及路由协议。

最简单的转发规则是溢出[3]网络：将收到的包发送给相邻节点，只要源节点和目标节点在同一网络相互连接的组件中，数据包就一定会到达目的地。为避免数据包无限循环，一个节点只能转发尚未见过的数据包(例如，迫使单独的源节点识别和排列数据包的序号)。同时，数据包通常携带某种形式的失效日期数据(生存时间和最大跳数)以避免不必要的数据包的传播(比如，如果目的节点根本不可到达)。由于这些传输协议很简单，他们的性能取决于发送的包和延迟的数量。路由算法以及路由协议决定路由表。在有线网络中，这些协议通常基于链接状态或距离向量算法[4,5,6]。而在无线网络中，常常需要移动、多跳网络和不同的路径。这里的路由协议应该是分布式的，开销低，自动配置，并且能够应付频繁的网络拓扑的变换。自组织路由的这个问题已经在研究文献和大量成熟的自组织路由协议中受到了重视。

一个通用的分类方法是将这些协议分为表控制式或先应式(主动式)协议，该协议试图在它们的路由表中保持精确的信息的保守协议；而另一个是请求式协议，它们不需要全程都保持路由表，只有当一个数据包被发送到一个没有可供使用的路由信息的目的地时，它们才去构建一个路由表。除了能量效率之外，弹性也是WSN的一个重要的考虑因素。例如，在运行中当节点依赖于能量挖掘时，他们有可能在不可预见的瞬间必须得停电，直到再次获得足够的能源。[7,8]

因此，在发送端和接收端路径单一时以及在多路径探索中，它都是令人满意的。这种多跳不仅在路径选择中提供冗余度，而且还可以在负载平衡中使用，例如，在均衡分布中需要用于转发的能量损耗。

2.激励

在WSN中，每一个消息的路径由基站决定这在网络的生命周期中真的很重要。如果我们总是选择到基站最短的路径，那将导致中间节点更快的衰竭从而缩短网络生命周期。我们需要尽可能地延长WSN的生命周期。

3.相关工作

在这一部分，我们将研究一些路由协议，它们对于得到无限传感网络中关于路由的概观很重要。我们来讨论AODV，SPIN，能量提醒路由协议，以及MRPC。

3.l AODV

AODV被广泛用于有线和无线网络的算法中。自组网按需距离向量路由协议。由于使用最短路径和最低能耗而被认为是最有效的路由协议之一。AODV是一个反应式协议，它仅在有请求时(即需要的时候)才在节点间建立路由。网络中给其他节点的消息不依赖于网络中全网周期性的发给其他节点的识别消息的广告。[9,10]

它把“HELLO”这个消息广播给邻近节点，然后它在路由选择中使用这些邻近的节点。无论何时、任何(源)节点要发送消息给另一个非邻近的(目的)节点，这个源节点就会启动一个路径探索，源节点将会发送一个路由请求(RREQ)消息给它的邻居。收到路由请求的这些节点就能更新他们关于发送节点的信息。该RREQ应该包含源节点的IP地址。换句话说，这个RREQ包含识别该RREQ所必须的广播ID。这个RREQ必须有一个当前序列号，这决定了这个信息是否过时。最终，该RREQ将跟踪这个通过跳数变量的路径探索而被访问的节点的序列号。当一个节点收到一个RREQ，它将检查自己是否在早些时候收到了同样的RREQ(通过检查IP，ID以及序列号)，如果不是，它将丢弃。换句话说，假如该RREQ的接受者是一个没有任何有关于路径和最终目的地信息的中间节点，那么这个节点不仅增加了跳数而且还重播了该RREQ给它的邻居。如果收到该RREQ的节点是最终的目的地节点，或者是一个知道路径和最终目的地信息的中间节点，它就会发送路由回复(RREP)回去。该RREP应记录该RREQ从源节点到目的节点的遍历路径。如图3所示，当源节点收到该RREP时，它应该开始发送数据。我们应该考虑到另一个控制信息，即，如果一个节点探测到活性路由上到下一跳的链路断开了，或者假如它收到一个数据包，而这个数据包注定要发送给一个不可修复的没有活性路由的节点时，那么我们将用到路由错误(RERR)。最终假如一个节点从相邻节点收到一个或多个活性路由的RERR时，它将发送一个RERR消息。

图3 Hello数据包图

3.2 SPIN协议

Wendi Rabiner Heinzelman et al.[11]提出一个被称为SPIN的一组自适应协议，假定网络中的所有节点是一个潜在的基站，它的每个节点可以传送网络中的所有信息。在这种算法中使用者可以查询任何节点，并且能立即得到请求信息或者数据。这种算法假定相近的节点具有相似的数据，因此只需要分发其他节点没有的数据。协议中的SPIN组使用数据协商和资源自适应算法。使用SPIN的节点分配一个高级别的名称来完整地描述他们收集的数据(被称为元数据或元内容)。元数据最简单的定义是描述数据的数据。这就是说，元数据应该提供原始数据的一个或多个方面的数据。例如，元数据可能是创建这个数据的意义，这个数据的目的、时间和创建数据，创建者或作者的数据，创建这个数据的计算机网络的位置信息，然后在所有数据(我们这里指的是原始数据)被传输前执行元数据的协议。由于我们过去常常确认有没有冗余数据在网络中发送，这样做可以减少网络上的开销和节省电力，元数据格式的语义具有特殊用途但在SPIN中不是特殊的。例如，当传感器因某一特定区域的重要事件想要发送元数据，它将用到它的ID。换句话说，SPIN算法能访问节点的能级，并根据某一节点剩余的能量多少来监控协议的执行。我们知道，这些协议是时间驱动式的，他们在无线传感器网络的各个角落广播信息，尽管事实是用户在有些时刻并没有请求任何数据。SPIN的元数据协商办法解决了溢出这个传统问题，从而通过发送元数据实现了多能效，而并非和以前的溢出一样发送所有数据。在SPIN中有三个阶段，传感器节点在这三种阶段中采用三种不同类型的信息：ADV(元数据的广播)，REQ(请求发送)与其他节点通信的数据，DATA是传感器采集的实际的数据包。当一个节点得到新数据，协议开始，它愿意与别的节点分享，然后他广播包含元数据的ADV消息。如果任意接收了ADV的节点对那个数据有兴趣，它会为此发送一个REQ消息，然后这个数据被发送至这个相邻的节点。相邻的传感器节点会在它的相邻节点之间重复这个过程。最终，全部的传感器区域将会收到备份数据。

3.3 动力感知路由

无线传感网络中有许多许多对路由的算法研究，这当中的许多算法和协议是基于能量的算法。在这些算法中我们收集网络图表，指定给每个链路一定的成本值，这个值能够反映出这个链路上的能量损耗，然后按照这些算法的估算选择图表中所需成本最少的路径。早期的关于这个的论文是参考文献[12]，它改进了Dijkstra的最短路径算法，以获得最低传输总功率的路径。

其中一个重要的算法以每一数据包或者每一比特的能量最低而闻名。最直接的构想是考虑在多跳路径上从源节点到目的地节点运送一个数据包所需的总能量(包括所有开销)，最终目的对于每一个包来说是通过选择一个好的路径来最小化所需的总能量。最小化跳数的办法显然不能达到这个目的，因为跳数少的办法中有可能某些跳的路程远、传输功率大。尽管如此，这些成本的衡量标准可以很容易的被考虑到标准路由算法中。这将导致不同的节点有完全不同的能量损耗[13]。

有些报告研究路由可能有电池的能量，在有限的能量供应中节点电池在网络寿命中是限制因素，在路由决策中有理由使用电池状态信息。有些方案通过选择有效的电池容量最大的路由来得到最大化电池容量，而省去那些不必要的绕道。最小化电池损耗，而不是着眼于一个给定路径上总的有效的电池容量；MBCR最小电池耗费路由，不是着眼于一个节点路由流量的“磁阻”[13,15]。随着电池的耗尽，这个磁阻会越来越大；。例如，磁阻和路由损耗可以测量，它们是电池容量的倒数。于是，一个路径上的损耗是这个倒数的和，这种规则是选择成本最低的路径。由于这种互导函数将低电池容量、高成本分配给节点，这样当节点能量将要耗尽时会自动把流量从路径上转移走。MMBCR(最小-最大电池开销路由算法)，这个计划[13,15]有一个类似的目的，就是以低能量电池资源保护节点。简单的将路径上所有节点的最大互导电平作为这条路径的成本，取代了使用互导电池电平。于是，最小成本的路径又被用上了。从这个意义上说，最佳路径是通过超过最大限度地最小化来选择最佳路径。通过沿一个路径使用最小电池电平然后在这个路径上最大化，可以达到同样的效果[14]。这就是一个最小/最大化构想。最小化电池电平的方差以保证一个较长的网络生命周期，一个策略是同时用尽所有的电池以避免某些节点过早耗尽能量和网络中断。因此，应该选择使得不同路径之间的方差降低的路径。

MTPR(最小总传输功率路由)事实上不考虑路由的情况下，如Bambos[16]考虑多个节点直接传送给他们的目的地的情况下，相互之间引起干扰。如果他的信噪比超过一个临界值，那么一个给定的传输就是成功的。我们的目的是为每一个发送机(考虑到通道衰减指标)发现一种功率值的分配方式，以使得所有的传输都是成功的，同时所有功率值之和是最小的。MTPR(最小总传输功率路由)当然对多跳网络也是适用的。

3.4 MRPC

Archan Misra,Suman Banerjee[17]过去一直致力于使无线环境中可靠路由的网络寿命最大化(MRPC)，他们靠挑选最可靠通信以及最少传输能耗的路径的方法不可能总是最大化adhoc网络的寿命。换句话说，由于节点电池能量的实际消耗将取决于该节点已转发的数据包，很难预测最优路由路径，除非数据包流的总大小在路径设置中已知。MRPC是这样选择路径的，已知组成节点的当前蓄电池电源的电平，假设共享该路径的所有其他流量不进一步进行任何传输，那么最大化的数据包总数可能在路径上进行理想地传输。

4.标准的高效路由算法

MRPC算法有个问题，它所使用的路径损耗太多功率。仿真结果[17]显示每个数据包的传输功率比最低能量算法的要高。下图4[18]显示MRPC算法将选择路径P1(A—C—F—H)，因为从A到H它将发送3个包，而通过路径P2只需发送两个数据包，尽管通过路径P1(6单元)发送一个数据包消耗的功率比P2(只有三个单元)要多。我们提出一个新的算法叫做标准的高效路由算法。

图4 图G以及它的组成

我们的算法可以概括为如下叙述：

D代表传感网络图；

w,y代表节点；

Edge(w,y)是w到y的链路；

e(w)：节点w剩余的电池；

c(w,y)：是edge(w,y)的加权成本；

N(w,y)是可以从w发送到y的数据包总数，这个值被称为e(w)/c(w,y)。

步骤1：初始化

当e(w)

对于每一个剩余的edge(w,y)使得：

令S为N(w,y)的值的集合。

步骤2：二分法

对S进行二分法以找到最大值，使得某一路径P从源节点到目的节点都没用边缘路径：

为此，当测试S中的一个值v时，我们从源节点开始执行一种深入或宽度优先的搜索。

这种搜索不允许使用边缘路径：

令P为寿命最长的源节点到目的节点的路径。同时，我们应通过Dijkstra算法找到最低能量路径，则：

步骤3：总结

如果在第二步中找不到路径，那么这种路由是不可能的。否则，用P来作为路径。

当然，我们也发现：min(x)，∀x∈P

我们需要获得一种兼具两者优势的混合算法。这里我们采用以下步骤：

我们必须增加一个条件，即阈值T，我们用它来衡量每个节点的电池电平，如果其中一个值小于阈值，则标准的高效路由算法将切换到使用MRPC的模式。除此之外，标准的高效路由算法将继续执行AODV协议。

在这种情况下我们考虑两个因素，经过该路径消耗的总功率，以及该路径上所有节点的剩余电量。但是我们必须注意，我们在新算法中使用权重，最低能量因素占较大的权重。这样，我们能保证尽可能长时间的使用最低能量算法而不至于使这些节点断电。

在图5中，我们首先可以用函数概括标准的高效路由算法。我们将一直 执行AODV协议知道第一个节点的能量变为初始能量的五分之一。在这种情况下，标准的高效路由算法将转换为路由算法。将执行MRPC算法。标准的高效路由将测试有没有节点。

图5 标准的高效路由流程图

我们也要注意到，如果我们使第一种条件下的阈值为(0)，那么标准的高效路由将执行AODV协议。而当我们选择阈值为(1)时标准的高效路由协议将完全执行MRPC。

5.分析

这里是仿真中用到的一些参数。

表1 仿真参数

我们通过MRPC与Min-Energy协议在三个领域的比较来研究标准的高效路由算法的行为。第一个因素是坏死节点随着时间变化的总数。在这个因素中节点在刚开始执行标准的高效路由算法时慢慢坏死，并将在执行结束时突然死掉，因为它同时具有MRPC和Min-Energy的特征。标准的高效路由算法的行为显示在图6中。

如果我们想要根据网络节点总发包数比较这些算法，那么我们的算法必须发送比Min-Energy多但是比MRPC少的数据包，如图7所示。

图6 有效期序列图

图7 发送的数据包的数量

最后我们将研究每个数据包的能量，这里我们同样假设每个数据包的能量将介于MRPC和Min-Energy之间，高于Min-Energy，低于MRPC。图8阐述了这一理念。

图8 每个数据包的能量

6.结论

这篇文章中我们试图介绍一种新型混合算法，它能通过采用最低能量和剩余电池的概念尽可能地延长网络寿命。我们的算法主要是依赖于用于WSN当中的能耗算法。这种算法是给予大部分能量在数据传输期间而非计算时消耗掉了。这种算法实际上兼具两种重要协议的优势。换句话说，MRPC协议的存在将最大限度的延长网络寿命。通过这种方法，标准的高效路由算法将使用最低能量协议直到剩余能量超过已知的阈值。

[1]Guillermo Rodriguez-Navas,Miquel A.Ribot,Bartomeu Alorda,Understanding the Role of Transmission Power in Component-Based Architectures for Adaptive WSN,2012 IEEE 36th IEEE Annual Computer Software and Applications Conference Workshops(COMPS ACW).

[2]Fuu-Cheng Jiang,Der-Chen Huang,Chao-Tung Yang,Fang-Yi Leu.Lifetime elongation for wireless sensor network using queue-based approaches.Springer Science+Business Media,LLC 2011.

[3]24.A.Qayyum,L.Viennot and A.Laouiti,“Multipoint Relaying:An Efficient Technique for Flooding in Mobile Wireless Networks,”Research Report RR-3898,INRIA,Mar.2000.Also available at www.inria.fr/RRRT/RR-3898.html.

[4]X.Chen,J.Wu,The Handbook of Ad Hoc Wireless Networks,CRC Press Inc(2002年12月26日)http://yuedu.baidu.com/ebook/7b5278563c1ec5da50e2705d.html.

[5]Jeffrey E.Wiesel their,Gam D.Nguyen and Anthony Ephremides,On the Construction of Energy-Efficient Broadcast and Multicast Trees in Wireless Networks,Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies.Proceedings.IEEE,Volume:2.

[6]K.Makki,N.Pissinou,and O.Frieder,“Efficient solutions to multicast routing in communication networks,”Mobile Networks and Applications (MONET),1,pp.221-232,1996.

[7]E.M.Royer and C.K.Toh,”A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks,”IEEE Personal Comm.,pp.46-55,Apr.1999.

[8]3.P.Bose,P.Morin,I.Stojmenovic and J.Urrutia,”Routing with Guaranteed Delivery in Ad Hoc Wireless Networks,”Proc.Third Int’,l Workshop Discrete Algorithms and Methods for Mobile Computing and Comm.,pp.48-55,Aug.1999.

[9]Wendi Rabiner Heinzelman,Anantha Chandrakasan and Hari Balakrishnan,Energy-Ef fi cient Communication Protocol forWireless Microsensor Networks,Proceedings of the 33rd Hawaii International Conference on System Sciences-2000.

[10]Charles E.Perkins,Elizabeth M.Belding-Royer,Samir R.Das,Ad hoc网络中基于距离数组的按需(AODV)路由协议,2003.7.http://wenku.baidu.com/link?url=wdahusmqcYoq MAGq81MdZYTuDwMcPbeYLf8iiejzW51OPHC_mphWpn S7Sg0oGwnWCBC0EodzmTQhIEa2m7SUnIe8BQZzH1ujR CCYEYvGJr3.

[11]Wendi Rabiner Heinzelman,Joanna Kulik,Hari Balakrishnan,Adaptive Protocols for Information Dissemination in Wireless Sensor Networks,in:Proceedings of the 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking(MobiCom99),Seattle,WA,Aug.15-19,1999.

[12]K.Scott,N.Bambos,Routing and channel assignment for low power transmission in PCS,California Univ.,Los Angeles,CA In proceeding of:Universal Personal Communications,1996.Record.,1996 5th IEEE International Conference on.

[13]Toh,C.K.,Maximum battery life routing to support ubiquitous mobile computing in wireless ad hoc networks,Communications Magazine,IEEE (Volume:39,Issue:6)2001.

[14]I.F.Akyildiz,W.Su,Y.Sankasubramaniam,E.Cayirci,Wireless sensor networks:A survey,Computer Networks 38(2002) 393-422.

[15]Suesh Singh and Mke Woo,Power-Aware Routing in Mobile Ad Hoc Networks,12/2001,Source:CiteSeer,http://www.researchgate.net/publication/2379876_Power-Aware_Routing_in_Mobile_Ad_Hoc_Networks.

[16]Bambos,N.Stanford Univ.,CA,USA,Toward powersensitive network architectures in wireless communications:con cepts,issues,and design aspectshttp://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=683739.

[17]Archan Misra,Suman Banerjee,MRPC:Maximizing Network Lifetime for Reliable Routing inWireless Environments,http://ieeexplore.ieee.org/xpl/articleDetails.jsp?reload=true&tp=&arnumber=993371&contentTyp e=Conference%20Publications&sortType%3Dasc_p_Sequence%26 fi lter%3DAND(p_IS_Number%3A21424).