无线传感器网络中一种高能效低延时的泛洪算法研究.doc

第8期李方敏等：无线传感器网络中一种高能效低延时的泛洪算法研究53无线传感器网络中一种高能效低延时的泛洪算法研究李方敏1，刘新华1，旷海兰2(1武汉理工大学 信息工程学院，湖北 武汉430070；2衡阳师范学院 计算机系，湖南 衡阳 421008 )摘 要：提出了一种新的应用于无线传感器网络的泛洪传播算法覆盖优先泛洪算法。算法采用覆盖优先策略为相邻节点分配不同的转发优先权，实现泛洪包快速覆盖整个网络；采用节点转发抑制策略和动态延时转发机制，尽可能抑制冗余包和减少冲突重传。仿真结果表明，该算法与同类算法相比，具有更高的能源有效性，更低的延时。关键词：无线传感器网络；泛洪；覆盖优先；动态延时中图分类号：TP393 文献标识码：A 文章编号：1000-436X(2007)08-0046-08Research on a very energy-efficient and low-delay flooding algorithm for wireless sensor networkLI Fang-min1，LIU Xin-hua1，KUANG Hai-lan2(1. School of Information Engineering, Wuhan University of Technology, Wuhan 430070, China;2. Computer Department of Hengyang Normal University, Hengyang 421008,China )Abstract: A novel flooding algorithm called priority covering algorithm was proposed for wireless sensor network. In the algorithm, a method of priority covering was used for assigning different forwarding priorities to vicinity nodes so as to make the flooding packet cover the whole network rapidly; a scheme of restrained forwarding and a scheme of dynamic delay for forwarding were used for restraining the redundant flooding packets and reducing the conflicting retransmission overhead. The result of simulation shows that the algorithm is more energy-efficient and low-delay than those similar flooding algorithms proposed.Key words: wireless sensor network; flooding; priority covering; dynamic delay1 引言收稿日期：2006-10-17；修回日期：2007-06-29基金项目：国家教育部博士点基金资助项目（20050497006）；新世纪优秀人才支持计划（NCET-05-0657）；湖北省青年杰出人才基金资助项目（2006ABB028）Foundation Items: The Ph.D. Programs Foundation of Ministry of Education of China(20050497006); The Program for New Century Excellent Talents in University of China(NCET-05-0657); The Foundation for Distinguished Young Scientists of Hubei Province(2006ABB028)泛洪（flooding）算法是无线网络中一种最基本的、最简单的路由算法。由于它具有实现简单、健壮性高的优点，成为实现网络服务和资源发现的主要手段，同时，在许多的无线网络路由协议中，泛洪算法还是这些路由协议的重要的组成部分和实现基础，例如ad hoc 网络的DSR、AODV、ZRP、LAR路由协议及无线传感器网络中比较经典的路由协议定向扩散（directed diffusion）协议。因此，良好的泛洪算法可以为这些路由协议提供更好的支持，进而提高整个路由协议的性能。传统的泛洪算法是指在泛洪传播过程中，一个节点发送一个消息给它所有的邻居节点，这些邻居节点分别将该消息转发给它们自己的邻居节点，直到该消息发布给整个网络，即网络中所有节点均收到这个消息，这种算法使得泛洪包在转发过程中带有很大的盲目性，因此称之为盲目泛洪（BF, blind flooding）算法。BF算法健壮性高、实现简单，但是由于算法未能有效抑制冗余泛洪包和有效减少信道冲突概率，这使得每次泛洪过程都要消耗很大的能量，而且随着网络规模扩大、节点密度增加，这种情况将更加严重。无线传感器网络是一种新型的、无基础设施的、自组织的无线网络1, 2。与其他无线网络相比，具有硬件资源有限、电源容量有限、以数据为中心、自组织、多跳路由、动态拓扑、节点数量众多且分布密集等特点3。因此，在路由算法的研究中，能量有效性和网络延时是路由设计中优先考虑的要素。由于BF算法所表现出来的固有缺陷，研究者们已经做了大量的研究工作，对BF算法提出了许多的改进方法412。这些方法的主要目标是在网络中找到一个节点的子集，只有处于这个子集中的节点才能转发泛洪包，以此来抑制网络中冗余数据。本文对其中具有代表性的方法进行了分析与研究，并将这些算法大致归为两类：一是利用节点的基本信息（位置，距离及邻居节点等）来影响节点的转发策略，以实现对冗余数据包的抑制。例如文献13提出的自我裁剪泛洪（SF, self-pruning flooding）算法及文献4提出的SBA（scalable broadcasting algorithm）就是基于邻居节点信息来抑制冗余泛洪包，前者是基于1跳邻居节点，后者是基于2跳邻居节点并通过随机分配转发延时来降低冲突概率；文献5 提出了基于计数（counter-based）、基于距离（distance-based）及基于定位（location-based）的算法思想，并在文献6中提出了几种自适应机制，以动态调整基于本地连接信息的阈值，来解决算法中的可达率与传输开销之间的平衡问题；文献7 提出了一种定位辅助的泛洪（location-aided flooding）算法；文献8,9则是节点通过在一定时间范围内对已经收到的冗余包进行跟踪，并在时间结束时，对它所收到的所有冗余包检查处理，以决定是否转发该包，这个时间值要么是在0和预先配置的值之间随机选取，要么是基于节点到发送这些包的节点的距离确定。二是利用网络的拓扑结构确定转发节点的子集。例如文献10提出的TBRPF（topology broadcast based on reverse-path forwarding）算法就利用了网络的拓扑信息，在这种机制下，泛洪包仅在源树（source-tree）的非叶子节点间传播，在源树中源节点是树的根节点；文献11,12,14利用分簇算法来形成分层的网络拓扑，确定转发节点子集（通常是簇头节点和网关节点）。这些主要适用于ad hoc网络的泛洪算法往往是提高了网络的能源有效性，却以牺牲传输延时为代价；或者能有效地抑制过多的冗余包，却增加了传输开销；或者算法比较复杂等。这对于主要利用泛洪传播来实现网络服务和资源发现以及构建其他路由算法的无线传感器网络来说，是不可取的。一种要求具有高能效、低延时而又实现简单的泛洪算法是提高无线传感器网络整体性能的基础。本文在深入分析和研究现有泛洪算法的基础上，提出了一种新的应用于无线传感器网络的泛洪传播算法覆盖优先泛洪（PCF, priority covering flooding）算法。PCF算法是一种高能效、低延时的泛洪算法，该算法采用覆盖优先策略为相邻节点分配不同的转发优先权，实现泛洪包快速覆盖整个网络；采用节点转发抑制策略和动态延时转发机制，尽可能抑制冗余包和减少冲突重传。算法能很好地解决高能效和低延时的一致性问题，且健壮性高、控制开销低、实现简单。论文后续部分安排如下：第2节给出PCF算法的基本理论；第3节和第4节给出PCF算法描述、算法的仿真实验及分析结果；最后是对全文的研究工作进行了总结。2 PCF算法的基本理论PCF算法主要从2个方面来解决泛洪过程中的能量消耗和网络泛洪延时问题：一是尽可能快地使泛洪包覆盖全网；二是尽可能多地抑制冗余泛洪包、减少信道冲突概率。前者主要采用覆盖优先策略来实现；后者通过节点转发抑制策略和动态延时转发机制来取得最佳效果。2.1 覆盖优先策略覆盖优先是指当一个节点收到泛洪包时，由该节点根据邻居节点覆盖新区域范围的大小指定它们的转发优先权。覆盖新区域范围越大，转发优先权就越高。因此，如何确定相邻节点覆盖新区域范围是覆盖优先策略的关键。从全局的角度看，按这种原则来分配转发优先权，节点就须要了解当前所有邻居节点覆盖新区域的范围，才能根据范围的大小来进行转发优先权的分配。在这种情形下，新区域是绝对意义上的，即未被该泛洪包覆盖过的区域，这就要求在泛洪过程中，每个节点都能动态地获知其所有邻居节点当前的覆盖新区域范围，而这显然是很难做到的，因为在泛洪过程中无论发布有关覆盖新区域范围的全局消息或者局部消息都是不适宜的，更重要的是会大大增加额外的控制开销。因此，本文提出相邻覆盖的思想来实现相对意义上的覆盖优先，即利用局部信息（指1跳邻居节点的基本信息）来确定邻居节点的潜在的覆盖新区域的范围，从而实现对相邻节点的转发优先权分配（本文中所说某节点的邻居节点均指该节点的1跳邻居节点）。相邻覆盖包括2个部分，一是利用转发节点的ID来确定本节点的邻居节点的覆盖状态，这需要在每个节点中维护一个邻居节点信息表，在这个表中包括相邻节点的ID、位置（坐标）等信息，而转发节点的ID则附加在它所转发的泛洪包中（在泛洪包增加一个4字节的ID字段）；二是确定邻居节点的转发优先权。1) 确定邻居节点的覆盖状态下面以一个平面泛洪的例子来说明节点如何利用收到的泛洪包中的发送节点的ID来确定本节点邻居节点中的覆盖状态，如图1所示。假设所有节点的通信距离为R，节点Sm坐标(xm，ym)为网络中任一发送节点，ID为m；节点Sn坐标 (xn，yn)是节点Sm的任意一个邻居节点，ID为n。图1 相邻覆盖当节点Sn接收到来自节点Sm的泛洪包时，根据泛洪包中节点Sm的ID，查询邻居信息表，就可以获得节点Sm的坐标(xm，ym)，因为Sm显然也是Sn的一个邻居。从图1可知，节点Sn中被Sm所覆盖的邻居节点是节点Sm与节点Sn的邻居节点的交集，即只要节点Sn中的任意邻居节点Si的坐标(xi,yi)满足：(1)则节点Sn的邻居节点Si处于相邻覆盖状态。2) 确定邻居节点的转发优先权在节点的邻居节点中确定优先转发机制，目的是尽可能使那些潜在的具有覆盖新区域范围大的邻居节点能优先转发。当一个节点收到一个泛洪包，那么这个节点的邻居节点就会分成两类，一类是处于相邻覆盖状态下的节点，用集合T表示；另一类就是未被相邻覆盖的节点，用集合表示。如图2所示，当节点S1收到来自节点S0的泛洪包时，节点S1的邻居节点分为两类：T1 = S0、S2、S3、S4 ，1= S5、S6、S7、S8 。根据泛洪算法扩散的方向性（由源节点向外围扩散），在与节点S1等距离的情况下，处于集合T1中的节点所具备的潜在的覆盖新区域能力的概率要比处于T1中的节点高。例如S2和S6（假设S2和S6等距于S1）相比，S6覆盖新区域的范围要比S2大（如图2阴影部分所示）。因此，获得最高优先转发权的节点是1中距离节点S1最远的节点。图2 节点转发覆盖图根据上述分析，本文对节点Sn( n是节点的ID)的邻居节点的转发优先权的分配是以集合n中具有最高优先转发权的节点为参考标准，根据邻居节点到节点Sn的距离以及是否被相邻覆盖来确定。具体描述如下：首先在集合n中找到优先权最高的节点Sk()，计算节点Sk到节点Sn的距离Dopt(2)其中，dist(Si, Sn)表示节点Si到节点Sn的距离，然后根据邻居节点Si到节点Sn的距离分配节点的优先转发权：(3)式（3）中W(Si)的值越小，表示转发优先权越高。若邻居节点处于n中，则距离越远，转发优先权就越高，其中距离最远的节点的优先权为0，即获得最高转发优先权，这意味着节点收到这个泛洪包后可以立即进行转发；若邻居节点处于Tn中，则对该节点的转发优先权进行调整，即在本次分配的转发优先权和它的其相邻节点已经分配给它的优先权W(Si)中取最大值，以得到当前该节点的转发优先权。2.2 节点转发抑制策略节点的转发抑制策略包括2个部分：一是设定节点的转发权，即节点对同一个泛洪包（指来自同一个源节点且具有同一标识的泛洪包）有且仅有一次转发权。一旦节点失去了对该泛洪包的转发权（例如已经转发了该泛洪包或转发权被抑制），则节点对此后收到的相同的泛洪包不再处理，而是直接丢弃。二是抑制节点的转发权，即节点在收到一个泛洪包时，如果这个节点的所有邻居节点已经被覆盖（即收到该泛洪包），则该节点对该种泛洪包的转发权被抑制（失去对该泛洪包的转发权）。因此，如果能尽可能多的抑制这类节点，必将大大提高网络的能量有效性。如图3所示，根据转发优先权，当节点S1转发泛洪包后，紧接着节点S2转发，这时节点S3就会发现自己所有的邻居节点都已经被覆盖了（即已经收到了泛洪包），在这种情况下节点S3再转发泛洪包已经没有意义，因此，节点S3的转发该种泛洪包的转发权被取消。图3 节点转发抑制2.3 动态延时机制动态延时机制是实现PCF算法的关键。该机制结合节点的转发优先权对转发节点进行动态延时转发，主要解决如下3个问题：1) 通过对相邻节点设置不同的转发延时，尽可能降低物理信道的冲突概率，减少消息重传机率。2) 通过延时转发，有利于节点在延时转发过程中能收集更多节点转发过来的泛洪包，通过相邻覆盖，确定节点的邻居节点的覆盖状态，再根据节点转发抑制策略，尽可能多的抑制节点的转发权，从而达到抑制冗余包的目的。3) 通过对节点动态配置转发延时，实现节点转发优先权的分配。下面以一个例子来说明在泛洪过程中节点根据其转发优先权来实现动态延时转发的过程。设节点Si坐标(xi，yi)是节点Sn坐标(xn，yn)的一个邻居节点，当节点Si收到来自节点Sn的泛洪后，节点首先根据转发抑制策略确定是否具有对该泛洪包进行转发的权限，若没有，则丢弃该包；否则，节点Si按下述方法计算转发该泛洪包的延时：若首次收到该泛洪包，则转发延时为(4)否则：(5)其中，；表示节点转发该泛洪包的最大延时；是节点Si的在收到节点Sn的泛洪包时当前还剩余的转发延时时间。式（4）表明节点首次收到该种泛洪包时的转发延时，这时节点Si处于n中，若节点Si的优先权最高（即W(Si)=0），则= 0，这意味着节点Si可以立即转发该泛洪包，从而保证泛洪包可以快速覆盖全网；而式（5）实际上表明节点Si处于Tn中，因而须要对延时转发进行动态调整，即在本次计算得到的转发延时和它当前的延时之间取最大值，以获得最终转发延时，而之所以取得大值，就是为了在许可的范围内尽可能延长节点的转发时间，以便收集更多的冗余泛洪包，从而尽可能将自身的对该泛洪包的转发权抑制掉，减少网络对能量的消耗，同时，这也保证了网络中的每个节点都将被覆盖到。此外，从上面分析可以看到，Dopt作为转发节点的一个信息也应加入到泛洪包中，即在泛洪包中要增加一个Dopt字段。3 PCF算法的描述及实现PCF算法是基于1跳邻居信息的泛洪算法，下面根据PCF算法的基本理论，给出了PCF算法的描述及实现过程。3.1 基本数据结构实现PCF算法需要在每个节点内部维护一张该节点的邻居信息表，邻居信息的获取通过节点周期性发送HELLO消息来实现。节点的邻居信息表结构如下：typdef struct _NeighborTableint nodeID; /邻居节点的地址double x; / 邻居节点的x坐标double y; / 邻居节点的y坐标double z; / 邻居节点的z坐标 NeighborTable;同时，根据覆盖优先方法可知，在每个泛洪包中要包括转发节点的ID（通过转发结点的ID查邻居信息表就可以得到转发节点的坐标）及Dopt值，因此，PCF的包头结构定义如下：typedef struct _PCF_HEADERint srcID; /PCF包源地址 int dstID; /PCF包目的地址int seqNo;/PCF包顺序号int fwdID;/转发PCF包的节点地址int Dopt;/T中节点到转发节点最远距离 PCF_HEADER;为了能同时处理不同的泛洪包（指来自不同的源节点或来自同一源节点但包的ID不同），在每个节点内部还要建立起泛洪包缓冲池，用以暂存不同的泛洪包，记录每个泛洪包所对应的邻居节点的相邻覆盖状态，并采用最近最久不使用策略来管理这个缓冲池。3.2 算法描述PCF算法主要分成3个组成部分：PCF包发送、PCF包接收及PCF包转发。算法具体描述如下：/PCF包发送算法void send( PCFPacket *p ) 计算节点的Dopt值；在PCF包中填入本节点的ID及Dopt值；发送PCF包；节点失去对该PCF包的转发权；/PCF包接收算法void recv( PCFPacket *p ) if( 对该PCF包没有转发权) 丢弃PCF包；return；if( PCF包的目的地址是本节点 ) 将PCF包交高层处理；节点失去对该PCF包的转发权；return；forward( p )；/PCF包转发处理算法void forward( PCFPacket *p ) /根据相邻覆盖与转发抑制策略判断对该PCF包的转发权是否被抑制if( 转发权被抑制)if( 存在延时转发过程 )终止延时转发过程；return；/根据式（3）和式（4）计算该PCF包的转发延时Tdelay；if(Tdelay = 0 ) if( 存在延时转发过程 )终止延时转发过程；/立即转发PCF包send(p)；elseif( 存在延时转发过程 )按Tdelay重启延时转发过程；else按Tdelay开启延时转发过程；3.3 算法分析PCF算法的主要特点表现在：1）高能效。PCF算法的高能效主要体现在2个方面，一是利用相邻覆盖可以使网络中大量节点的转发功能被抑制，从而能大幅度减少冗余泛洪包；二是采用动态转发延时机制，使得物理信道冲突概率大大降低，减少节点的重传机率。2）低延时。PCF算法中的覆盖优先策略保证尽可能让覆盖新区域范围大的节点获得转发优先权，从而能使泛洪包能快速地覆盖全网。3）高健壮性。相邻覆盖使得网络中每个节点都能确保其所有的邻居节点被覆盖（即收到泛洪包）。4）算法实现简单，控制开销低，与其他算法结合容易。PCF算法仅需要在每个节点内部维护一张邻居信息表以及在每个泛洪包中包含发送节点的ID及Dopt就可以实现，具有较低的控制开销，易于与其他路由协议结合。4 PCF算法的仿真及结果分析对PCF算法的性能评价主要从能源有效性及网络泛洪延时两方面来分析算法的性能。基于算法比较的公平性，除了与BF算法进行比较外，还选取了PCF算法的同类算法SF算法13和SBA算法 4来进行比较。在NS2中，各算法均采用IEEE 802.11MAC协议，并根据泛洪算法的特点，设计了2个仿真场景，来比较和分析同等条件下PCF算法与同类算法的性能： 随节点的密度变化。在平面区域100m100m上，节点随机分布，所有节点的传输半径固定为40m，节点数量以50个节点为增量在50,350范围内变化。 随节点的传输范围变化。在平面区域100m100m上，随机分布150个节点，每个节点的传输半径以5m的增量在20m，50m之间变化。并在、中随机选取一个节点作为源节点，源节点发出的每个泛洪包的大小为512Byte。4.1 能源有效性仿真分析1) 转发率（forward rate ）转发率是指在一次泛洪传播过程中转发节点数与总节点数（不包括源节点）的比率。用转发率来衡量泛洪算法在一次泛洪传播中的能量消耗，是为了检验算法抑制冗余泛洪包的能力及处理机制的有效性。根据仿真场景和，在NS中分别得到BF算法、SF算法、SBA算法及PCF算法的转发率随节点数量变化的曲线比较图（如图4(a)所示）及转发率随节点传输半径变化的曲线比较图（如图4(b)所示）。由图4可知，在节点数量增加（节点分布密度增大）和节点的传输半径增大的情况下,BF算法因为采用盲目转发机制，使得网络中所有节点都要转发一次泛洪包，因此，BF算法的转发率是100%；SF算法抑虽能抑制部分泛洪包，在效果不是很明显（只抑制不足20%）；SBA可抑制60%左右的；而PCF则能抑制率高达80%以上。2) 节点平均消耗能量（average dissipated energy）节点平均消耗能量是指在一次泛洪传播中网络所消耗的总能量与网络中节点总数比值。使用节图4 PCF与BF、SF、SBA的转发率比较图5 PCF与BF、SF、SBA的节点平均消耗能量比较点平均消耗能量主要是检验算法在综合情况（如节点消息冲突，信道竞争，控制开销等）下的能源有效性。为此在、两种仿真场景中增加节点能量模型并设定：节点的发送功率为0.660W，节点的接收功率为0.395W，并假设节点的节点侦听与休眠状态的能量消耗功率均为0。仿真得到BF算法、SF算法、SBA算法及PCF算法的节点平均消耗能量随节点数量变化的曲线比较图（如图5(a)所示）及节点平均消耗能量随节点传输半径变化的曲线比较图（如图5 (b)所示）。由图5可知，SF及SBA算法在节点平均能量消耗上比BF算法有所改善，但PCF算法表现更优越。4.2 网络延时仿真分析泛洪延时（flooding delay）是指在一次泛洪传播过程中，从源节点发送一个泛洪包开始，到网络中最后一个节点收到泛洪包的时间，即网络经历一次泛洪传播需要的时间。泛洪延时用来衡量泛洪算法的网络延时性能，根据仿真场景和，分别得到BF算法、SF算法、SBA算法及PCF算法的泛洪延时随节点数量变化的曲线比较图（如图6(a)所示）及泛洪延时随节点传输半径变化的曲线比较图（如图6(b)所示）。由图6可知，在节点密度增大（节点数增加）的情况下（如图6(a)所示），BF算法与SF算法的图6 PCF与BF、SF、SBA的传输延时比较泛洪延时随之增加，这是因为影响BF算法与SF算法延时主要因素是泛洪包冲突与竞争信道，因此在这种情况下，延时会随着增大；SBA算法由于采用随机分配延时而对网络泛洪延时不敏感；而PCF算法由于采用了覆盖优先策略，使得泛洪延时变低而且增加比较平缓。在节点传输半径增大的情况下（如图6(b)所示），虽然三者延时都有所下降，但PCF算法所表现出来的性能更好。5 结束语本文提出了一种新的应用于无线传感器网络的泛洪传播算法覆盖优先泛洪算法（PCF算法）。PCF算法是一种高能效、低延时的泛洪算法，该算法采用覆盖优先策略为相邻节点分配不同的转发优先权，实现泛洪包快速覆盖整个网络；采用节点转发抑制策略和动态延时转发机制，尽可能抑制冗余包和减少冲突重传。算法能很好地解决高能效和低延时的一致性问题，且健壮性高、控制开销低、实现简单。本文给出了覆盖优先方法的理论及PCF算法的实现，并在NS2上进行了仿真，仿真结果表明，与同类泛洪算法相比，PCF算法具有更高的能源有效性，更低的延时。同时，算法实现简单，控制开销低，容易与其他应用于无线传感器网络的算法结合。参考文献：1任丰原, 黄海宁, 林闯. 无线传感器网络J. 软件学报,2003,14(7): 1282-1291.REN F Y, HUANG H N, LIN C. Wireless sensor networksJ. Journal of Software, 2003,14(7):1282-1291.2崔莉, 鞠海玲, 苗勇等. 无线传感器网络研究进展J计算机研究与发展, 2005, 42(1): 163-174.CUI L, JU H L, MIAO Y, et al. Overview of wireless sensor networkJ. Journal of Computer Research and Development, 2005, 42(1): 163-174.3孙利民, 李建中, 陈渝等. 无线传感器网络M. 北京: 清华大学出版社, 2005.SUN J M, LI J Z, CHEN Y, et al. Wireless Sensor NetworkM. Beijing: Qinghua University Press, 2005.4PENG W, WU C X. On the reducation of broadcast redundancy in mobile ad hoc networksA. The Sixth Annual International Conference on Mobile Computing and Networking (MobiCom 2000)C. Boston, USA, 2000. 129-1305NI S Y, TSENG Y C, CHEN Y S, et al. The broadcast storm problem in a mobile ad hoc networkA. Intl Conf on Mobile Computing and Networking (MOBICOM) C. 1999. 151-162.6SABBINENI H,CHAKRABARTY K.Location-aided flooding: an energy-efficient data dissemination protocol for wireless-sensor networksJ. IEEE Transactions on Computers, 2005, 54(1):36-46.7TSENG Y C, NI S Y, SHIH E Y. Adaptive approaches to relieving broadcast storms in a wireless multihop mobile ad hoc networkA. Proc IEEE 21st International Conference on Distributed Computing SystemsC. 2001.481-488.8SUN M T, FENG W C, LAI T H. Location aided broadcast in wireless ad hoc networksA. Proceedings of the IEEE Conference on Global Telecommu