姜 波 张荣福
摘 要：路由协议是无线传感器网络的重要组成部分,节能是无线传感器网络路由协议设计所要解决的首要问题。重点深入分析了低功耗路由协议LEACH和PEGASIS,总结了它们各自的优缺点,同时简单介绍了其他几种典型的路由协议,并对所述路由协议进行了综合对比,最后,总结了路由协议能量优化的方法。
关键词：无线传感器网络；路由协议；节能；LEACH协议；PEGASIS协议
中图分类号：TN915 文献标识码：A
文章编号：1004-373X(2009)01-026-04
Research on Energy-saving Routing Protocol for Wireless Sensor Network
JIANG Bo,ZHANG Rongfu
(University of Shanghai for Science and Technology,Shanghai,200093,China)
Abstract：Routing protocol is a very important part of wireless sensor network,saving energy is the first problem in routing protocol design for wireless sensor network.This paper focuses on in-depth analysis of the low-power routing protocols LEACH and PEGASIS,then their respective advantages and disadvantages are summarized,and several other typical routing protocols are introduced briefly,and routing protocol described in the text are compared together.Finally,the routing protocol energy optimization approach is indicated.
Keywords：wireless sensor network;routing protocol;energy-saving;LEACH protocol;PEGASIS protocol
0 引 言
传感器技术、微机电系统、现代网络和无线通信等技术的进步,推动了具有现代意义的无线传感器网络的产生和发展。无线传感器网络扩展了人们的信息获取能力,将客观世界的物理信息同传输网络连接在一起,在下一代互联网中将为人们提供最直接、最有效、最真实的信息。无线传感器网络具有十分广阔的应用前景,能应用于军事国防、工农业控制、城市管理、生物医疗、环境监测、抢险救灾、防恐反恐、危险区域远程控制等诸多领域。
无线传感器网络设计的基本原则就是要以节能为前提。传统无线通信网络的首要设计目标是提高服务质量和高效带宽利用,其次再考虑节约能源；而传感器的首要设计目标是能源的高效利用,这是传感器网络和传统网络的最重要的区别之一,能量问题是无线传感器网络的核心问题。传感器节点由电池供电,而目前的技术水平下电池容量难以有大幅度提高,而且在许多应用中,更换电池是不现实的(如军事应用),因此这就要求WSN路由协议必须以节约能源为主要目标,最大限度地延长网络生存时间。
1 低功耗路由协议
1.1 LEACH协议
LEACH(Low-Energy Adaptive Clustering Hierarchy)是MIT的Chandrakasan等人为无线传感器网络设计的低功耗自适应分层路由算法［1］。它的基本思想是以循环的方式随机选择簇头节点,将整个网络的能量负载平均分配到每个传感器节点中,从而达到降低网络能源消耗,提高网络整体生存时间的目的。LEACH在运行过程中不断地循环执行簇的重构过程。每个簇重构过程可以用“轮”的概念来描述。每个轮可以分成两个阶段：初始化和稳定工作两个阶段。为了避免额外的处理开销,稳定阶段一般持续较长时间。
初始化阶段即簇的形成阶段。在每一轮的初始化阶段,每个传感器节点都要决定自己是否充当簇头节点。这个决定主要取决于网络中所需要的簇头节点数(在初始化的时候设置)和迄今为止该节点已成为簇头节点的次数。簇头节点必须从那些没有当过簇头节点的节点中选择,直到网络中的所有节点都当过簇头节点,然后再进行重新选举,所有节点获得再次成为簇头的机会。簇头节点的选择办法是：每个传感器节点随机选择0～1之间的一个值,如果选定的值小于某一个阈值T(n),那么这个节点成为簇头节点。T(n)值的计算方法如下：
T(n)=p1-prmod1p, n∈G
0,其他(1)
其中,p是网络中簇头节点所占节点数目的百分比,r为当前的轮数,G是一个集合,集合中的节点是前1/p轮中没有充当过簇头节点的节点。使用这个门限,每个节点会在1/p轮操作内充当一次簇头节点,符号mod是求模运算符号。
在第0轮的时候(r=0),每个节点充当簇头节点的概率为p,在第0轮充当簇头节点的节点在后面1/p轮中不能再次充当簇头节点。这样,剩下的节点的数目变少了,所以能够充当簇头节点的概率必须增加才能保证每一轮中的簇的个数保持均衡。在经过1/p-1轮以后,T=1,此时对于任何一个在过去的1/p中还没有做过簇头节点的节点,都可以成为簇头节点,因为所有节点的标志值都在0~1之间。经过1/p轮之后,所有节点又可以重新充当簇头节点了。
一旦簇头节点被选定,它们就使用相同的能量向网络中的其他节点广播一个广告包。在这个过程中,其他非簇头节点的接收机一直处于工作状态,以便接收来自不同簇头的广告包,它们根据最小通信能量原则,选取信号最强的广告包的发送源节点作为自己的簇头节点,并发送消息给其簇头节点,告诉簇头节点自己已经加入该簇。
当簇头节点收到了来自成员节点的“报道”消息后,根据成员节点的数目,产生一个TDMA的时隙表,告诉成员在什么时刻可以发送数据。这个表会通过广播到达成员节点,由于形成了簇的结构,成员节点只与自己的簇头节点通信,如果收到来自其他节点的消息,会自动屏蔽掉。因此不用担心簇头节点的时隙表被其他簇的成员错误接收。当网络中的簇已经形成,而且TDMA时隙表也确定下来,就开始了数据传送。成员节点只能在TDMA时隙表为其分配的时隙内与簇头节点进行通信。假设传感器节点总是有数据要发送,在属于自己的时隙里,成员节点会把数据发送给自己的簇头节点。在发送阶段,在自己的时隙没有到来的时候成员节点可以关闭自己的收发机以节省能量。而簇头节点必须一直使自己的接收机处于开启状态,用于接收来自不同成员节点的数据。当一轮的数据传输完毕后,簇头节点会进行必要的数据融合处理,将多个数据融合成一个数据,然后发送给基站。持续一段时间以后,网络开始进入下一轮的工作周期。
LEACH协议运用了数据压缩技术和分层动态路由技术,通过本地的联合工作来提高网络的可扩展性和鲁棒性,通过数据融合来减少发送的数据量,通过随机选择簇头节点来达到网络内部负载均衡的目的,进而大大节约了能量。
尽管LEACH协议具备以上优点,但也存在一些不足之处。
(1) 由于LEACH算法假定所有节点能够与汇聚节点直接通信,并且每个节点都具备支持不同MAC协议的计算能力,因此该协议不适合在大规模的无线传感器网络中应用。
(2) LEACH算法是让网络中自组织的形成簇,由于簇头节点是随机产生的,这样无法保证簇头节点的合理分布。因此,很有可能出现被选择的簇头节点集中在网络中某一区域的现象,这样就会使得一些节点的周围没有任何簇。
(3) LEACH算法忽略了被选簇头在网络内的分布状态和节点间不同的通信距离而导致的节点能量损耗的不平衡。
1.2 PEGASIS协议
PEGASIS(Power-Efficient Gathering in Sensor Information Systems)协议是在LEACH基础上改进设计的［2］。PEGASIS算法的主要思想是在传感器网络中形成一条覆盖所有节点的“链”,节点从它的一边的邻居节点接收数据,然后将接收到的数据和自身的数据进行融合处理之后形成一个与原来数据包同样大小的新数据包,再将得到的新数据包发送给它的另外一边的邻居节点,以此类推,数据最终被传到一个“领导”节点,由这个“领导”节点把数据发送给基站。节点充当“领导”节点与基站通信是轮流的,当网络中的所有节点都充当过“领导”节点后,节点再进行新一回合的轮流通信。
在PEGASIS算法中,“链”的形成过程是整个通信的关键。“链”的形成采用的方法是：节点发送能量递减的测试信号通过监测应答来确定离自己最近的相邻节点。通过这种方式,网络中的所有节点能够了解彼此的位置关系,找到自己的邻居节点,每一轮通信中节点只需要与自己的邻居节点进行通信。为确保每个节点都有其相邻节点,从离基站最远的节点开始构建,链中邻居节点的距离会逐渐增大,因为已经在链中的节点不能被再次访问。依次下去,最终形成一条包含网络中所有节点的链。
当节点链形成并且选举出领导节点后,就开始了数据传输过程。PEGASIS中的数据传输使用Token(令牌)机制,如图1所示。Token很小,故能耗较少。在一轮通信中,领导节点用Token控制数据从链尾开始传输。图中,C2为领导节点,将Token沿着链传给C0,CO传数据给C1,C1将C0数据和自身数据进行融合后形成一个相同长度的数据包,再传给C2。然后,C2将Token传给C4,C2以相同的方式接收来自C3,C4的数据。这些数据在C2处进行融合后,发给基站。
图1 链式结构示意图
PEGASIS是在LEACH基础上建立的路由协议,PEGASIS比LEACH节省能量主要体现在以下几个方面：
(1) 在本地数据聚合阶段,PEGASIS算法中每个节点只与离自己最近的邻居节点进行通信,而不是像LEACH算法一样需要与簇头节点进行通信,PEGASIS算法大大减小了每轮通信中每个节点的通信距离,从而降低了每个节点在每一轮通信中所消耗的能量。
(2) LEACH算法中,一个簇头要接收多个簇成员节点发送过来的数据,而PEGASIS算法中,一个领导节点最多只需要接收2个节点发送过来的数据包。
(3) 在每一轮通信中,PEGASIS算法只有1个领导节点与基站通信,而LEACH中则有多个簇头节点与基站通信。PEGASIS也存在一些不足之处：节点维护位置信息(相当于传统网络的拓扑信息)需要额外的资源,在网络全局信息比较难以获得的情况下就不合适了,而且领导节点的惟一性使得其成为整个通信过程的瓶颈。
2 其他典型路由协议
2.1 SPIN协议
SPIN(Sensor Protocols for Information via Negotiation)协议［3］的设计思想是：每个节点在发送数据前通过协商来确定其他节点是否需要该数据；同时,节点通过“元数据”确定接收数据中是否有重复信息存在。节点通过3种消息进行通信：ADV(数据描述),REQ(数据请求)和DATA(数据)。源节点在传送DATA信息之前,首先向相邻节点广播包含DATA数据描述机制的ADV信息,需要该DATA信息的邻节点向信息源发送REQ请求信息,源节点在收到REQ信息后,有选择地将DATA信息发送给相应的邻节点。收到DATA后,该邻节点可以作为信息源,按照前述过程将DATA信息继续传播到网络中的其他节点。该协议的优点是：ADV消息减轻了内爆问题；通过数据命名解决了交叠问题；节点根据自身资源和应用信息决定是否进行ADV通告,避免了资源利用盲目的问题,进而有效地节约了能量。其缺陷是：当产生或收到数据的节点的所有邻节点均不需要该数据时,将导致数据不能继续转发,会使较远节点无法得到数据。
2.2 DD协议
DD(Directed Diffusion)是Estrin等人专为无线传感器网络设计的路由协议［4］。汇聚节点将查询任务封装成兴趣消息(interest)的形式,采用洪泛方式传播兴趣消息到其他节点,兴趣消息用来表达用户对监测区域内感兴趣的信息。在兴趣消息的传播过程中,协议逐跳地在每个节点上建立反向的从数据源到汇聚节点的数据传输梯度。节点将采集到的数据沿着梯度方向传送到汇聚节点。定向扩散的最大特点是引入网络梯度的概念,其优势在于扩散过程能够将按照经验选取的较优路径缓存以实现节能,并且提高节点间的有效性、鲁棒性和协作的可扩展性。
2.3 GEAR协议
GEAR(Geographical and Energy Aware Routing)是一种典型的地理位置路由协议［5］。该算法的提出基于以下思想：在传感器网络中向适当区域发送查询时,此查询数据中包含了位置属性信息,因此,可以利用这一信息将在整个网络中扩散的信息传送到适当的位置区域中。该算法引入了预估费用(estimated cost)和学习费用(learning cost),通过比较两者值的大小来选取更接近汇聚节点的传感器节点作为下一跳。GEAR利用能量和地理信息作为启发式选择路径向目标区域传送数据,它是在DD的基础上提出的,但由于GEAR只考虑向某个特定区域发送兴趣,而不是像DD那样发布到整个网络,因此,GEAR相对DD更加节省能量。
2.4 SAR协议
SAR(Sequential Assignment Routing)协议是一个典型的具有QoS意识的路由协议［6］。该协议通过构建以汇聚节点的单跳邻节点为根节点的多播树来实现传感器节点到汇聚节点的多跳路径,即汇聚节点的所有下一跳邻节点都以自己为根创建生成树,在创建生成树过程中考虑节点的时延,丢包率等QoS参数以及最大数据传输能力,这样就反向建立了到汇聚节点的具有不同QoS参数的多条路径。SAR的一个突出优点是综合考虑了能效和QoS,仿真结果表明,与只考虑路径能量消耗的最小能量度量协议相比,SAR的能量消耗较少。
3 路由协议对比分析
节能是无线传感器网络最重要的特征,因而高效地利用能量是无限传感器网络路由协议设计的根本出发点。LEACH和PEGASIS具备很好的节能策略,SPIN,DD,GEAR,SAR 也分别具备相应的节能策略。但是,无线传感器网络与应用高度相关,所以路由协议在节能的前提下还要满足以下方面的性能要求：以数据为中心、支持数据融合、基于节点定位、具有可扩展性、鲁棒性、提供QoS支持等。依据上述性能指标,对描述的路由协议特点进行对比的结果如表1所示。
4 结 语
深入分析了低功耗路由协议LEACH及PEGASIS,希望能对以后LEACH及PEGASIS协议的改进起到一定的推动作用。在综合所述的路由协议基础之上,总结出以下几种无线传感器网络路由协议能量优化方法：
(1) 数据融合。节点通过对数据进行融合,降低网络开销,节省能量。
(2) 数据命名。数据命名机制能高度搜索用户所需数据,避免数据在网络中的重复发送,降低了网络开销。
(3)局部协商技术。协商技术能够有效地避免由于
节点间重复地收发大量冗余信息所造成的能量浪费。
(4) 随机路由选择。路由协议支持到目的地的低开销多种路由会使网络负载趋于平衡,延长网络寿命。除了能量高效,无线传感器网络路由协议还存在一些挑战,如QoS和带宽的高效利用,在能量有效性的前提下提供对节点移动的支持,网络安全问题等。这些问题将在以后的工作中继续深入研究。
参考文献
［1］Heinzelman W,Chandrakasan A,Balakrishnan H.Energy-efficient Communication Protocols for Wireless Sensor Networks［A］.IEEE Proceedings of the Hawaii International Conference System Sciences′00.2000:3 005-3 014.
［2］Lindsey S,RaghavendraC.PEGASIS:Power-Efficient Gathering in Sensor Information Systems［A］.Proceeding of the IEEE Aerospace Conference′02.2002:1 125-1 130.
［3］Kulik J,Heinzelman W,Balakrishnan H.Negotiation-based Protocols for Disseminating Information in Wireless Sensor Networks［J］.Wireless Networks,2002,8(3):169-185.
［4］Intanagonwiwat C,Govindan R,Estrin D.Directed Diffusion for Wireless Sensor Networking［J］.Transactions on Networking,2003,11(1):2-16.
［5］Yu Y,Govindan R,Estrin D.Geographical and Energy Aware Routing:A Recursive Data Dissemination Protocol for Wireless Sensor Networks［R］.UCLA Computer Science Department Technical Report UCLA/CSD-TR-01-0023,2001.
［6］Sohrabi K,Gao J,Ailawadhi V,et al.Protocols for Self- organization of a Wireless Sensor Network［J］.IEEE Personal Communications,2000,7(5):16-27.
作者简介
姜 波 男,1983年出生,安徽颍上人,硕士研究生。研究方向为短距离无线通信与计算机网络。
张荣福 男,1971年出生,安徽庐江人,副教授,博士。研究方向为信息处理技术。
