一种基于分簇的优化定向扩散路由协议

梁小宇，刘 泉，刘新华

(武汉理工大学信息工程学院，湖北武汉430070)

随着微电子技术、传感器技术及通信技术的发展，无线传感器网络技术发展迅猛。但由于无线传感器网络具有硬件资源和电源容量有限、以数据为中心、自组织、多跳路由、动态拓扑、节点数量众多且分布密集等特点，许多现有的路由协议都不适用于它，特别是大规模无线传感器网络。在现有的路由协议中，以数据为中心、具有良好扩展性的定向扩散算法较适合于大规模无线传感器网络［1］，但由于定向扩散算法主要依赖耗能大的平面泛洪来建立路由，导致其在大规模无线传感器网络中消耗能量更为严重，基于此，笔者在定向扩散算法的基础上提出了一种改进的基于分簇的定向扩散路由协议。该协议是一种利用分簇来简化网络拓扑、抑制泛洪传播产生的冗余消息，从而节约能量，实现能源有效性的定向扩散路由协议。

1 定向扩散路由协议

定向扩散路由(directed diffusion routing，DDR)是一种经典的以数据为中心的路由机制［2］。定向扩散(directed diffusion，DD)是一种以数据为中心的路由协议。汇节点向所有传感器节点发送其嗜好(通过分配不同属性值来表示不同任务的描述符)，每个传感器节点在收到嗜好后保存在各自的缓存中。每个嗜好项包含一个时间标签域和若干个梯度域，按成本最小化和能量自适应原则引导数据扩散的方向。当一个嗜好传遍整个网络后，从源节点即嗜好所在区域的传感器节点，到汇节点之间的梯度就建立起来了。一旦源节点采集到嗜好所需的数据，便将其沿着该嗜好的梯度路径传输数据到汇节点或基站。其中，源节点采集的数据首先在本地采用数据融合技术进行整合，然后在网上传输。

显然，定向扩散路由建立时需要一个嗜好扩散的泛洪传播［3］，以及一个探测消息的泛洪传播来加强路径，形成梯度。泛洪产生的过剩消息会增加链路层的开销，增加冲突概率，同时也会造成网络拥塞。在大规模无线传感器网络中，这种额外的开销会严重影响网络的性能。因此，如何改进定向扩散算法中这些固有的缺陷使其能适用于大规模传感器网络是笔者研究的重点。

2 CBODD原理

CBODD是利用分簇［4］思想提高定向扩散的能源有效性的无线传感器网络路由协议。通过分簇来简化网络拓扑及减少泛洪中的冗余消息来达到提高网络能源有效性的目的，使之能适用于大规模无线传感网络［5］。

2.1 分簇算法

笔者采用一种基于被动分簇算法［6］的分簇机制，通过定向扩散协议本身的泛洪传播来建立网络拓扑。因此不需要额外的控制信息(通过泛洪传播)来建立或维护网络拓扑，仅需在原有的包结构中加入一个与簇相关的信息结构来实现路由的建立与维护［7－8］。

该被动分簇算法的思想是仅当网络中有数据通信要求时才在网络中建立分簇网络拓扑，且网络拓扑的建立与维护都在本地完成，不需要单独的控制命令以节省能量开销。分簇策略中最重要的是簇头选举机制和网关节点的选择机制，簇头选举采用“先声明者胜”的选举机制，网关节点的选择则是根据网络健壮性和能源有效性之间平衡的原则来确定选择机制。

2.2 路由的建立与维护

CBODD路由的建立由网络中Sink节点发起，当节点分布完成后，网络处于初始状态，如果之后没有数据传输要求，则网络保持初始状态，由于形成分簇的网络拓扑由Sink节点发起，分簇的网络拓扑形成以后只有当网络拓扑受到损害或无法维持下去时，网络才会重新回到初始状态，等待Sink节点的下一次传输要求来重新建立网络拓扑并形成由源节点到Sink节点的路由。

整个CBODD路由协议的建立基于分簇的基础，主要分为3个阶段:扩散阶段、建立阶段和路径加强阶段。图1描述了CBODD路由建立的完整过程。

(1)扩散阶段。当Sink节点广播嗜好时，若网络处于初始状态(图1(a))，则网络拓扑随嗜好在网络中泛洪传播而建立起来(图1(b))，同时建立起从源节点到Sink节点的网络梯度(图1(d));当网络已经处于成簇状态时，则嗜好仅沿簇首扩散(图1(c))，建立从源节点到Sink节点的网络梯度(图1(d))。

(2)建立阶段。当源节点采集到与嗜好匹配的数据时，源节点把数据发送给自己的簇首节点，簇首节点通过网关节点向多个相邻的簇首节点发送数据，Sink节点可能收到多个路径的相同数据(图1(d))。中间的簇首节点收到其他簇首节点转发的数据后，首先查询嗜好列表的表项。如果没有匹配的嗜好表项就丢弃数据;如果存在响应的嗜好表项，则检查与该嗜好对应的保存最近转发数据的数据缓冲池。若其中有与接收到的数据匹配的副本，说明已转发过该数据，可避免出现传输环路而丢弃这个数据;否则，检查该嗜好表项中的邻居节点信息。对于转发的数据，数据缓冲池保留一个副本，并记录转发时间。

图1 CBODD路由建立过程

(3)路径加强阶段。节点在收到从源Sink节点发来的数据后，启动建立到源节点的加强路径，后续数据将沿着加强路径以较高的速率进行传输(图1(e))。

3 协议的实现

3.1 CBODD的实现机制

利用NS2所提供的网络路由应用编程接口［9］来实现基于定向扩散协议的CBODD协议。网络应用编程接口提供了一种过滤器API，利用API可以将设计的模块与定向扩散内核连接起来［10］。在CBODD协议的实现过程中，对NS2中的定向扩散协议作如下修改:

(1)原定向扩散协议包结构中增加与簇相关信息;

(2)增加一个优先级比梯度过滤器高的分簇过滤器，分簇过滤器的主要功能是实现网络拓扑的建立与维护。实现CBODD路由协议实际上主要是设计分簇过滤器。

3.2 CBODD的实现过程

在NS2中利用网络应用编程接口设计实现一个过滤器分为两步:第一步是初始化操作;第二步是返回处理。初始化操作包括创建定向扩散路由类;建立分簇过滤器，用来过滤进入定向扩散路由中的数据包。

返回处理是对接收到的嗜好包进行处理，这是设计分簇过滤器的关键。其详细算法如下:

Void ClusterFilter::recv(Message*msg，handle h)

{//嗜好消息过滤后转发;否则丢弃该包

bool bForward=true;

static int iHeaderCount=0;//簇首计数器

if(!msg－＞new_message){丢弃这个消息;

return;}

if(msg－ ＞last_hop==LOCALHOST_ADDR)

{获取本节点当前状态;

将与簇相关的信息填入嗜好消息中;}

else//否则嗜好消息来自其他节点

{提取嗜好包中与簇相关的信息;

获取本节点当前状态;

switch(本节点当前状态)

{case NS_INITIAL://节点为初始态

if(嗜好来自簇首预备态的节点)

{置本节点当前态为普通节点状态;

bForward=false;}

else{if(嗜好来自簇首节点)

{保存该簇首信息;iHeaderCount++;

bForward=false;}

else{置本节点当前态为簇首预备态;

将与簇相关信息填入嗜好消息;

启动该节点簇首选取机制;}}break;

case NS_HEADER_READY:

if(嗜好来自簇首预备态的节点)

{if(该嗜好比本节点发的嗜好早)

{中断该节点簇首选取机制;

置本节点当前态为普通节点态;}}

else{if(嗜好来自簇首节点)

{中断该节点簇首选取机制;

置本节点当前态为普通节点态;}}

bForward=false;//丢弃该包break;

case NS_GATEWAY_READY:

if(嗜好来自网关预备态的节点)

{保存预备网关信息至预备网关表;

据网关机制决定本节点是否成为网关节点;

if(选定本节点为网关节点)

{置本节点当前态为网关节点态;

将与簇相关信息填入嗜好消息;}

else{置本节点当前态为普通节点态;

bForward=false;//丢弃该包}}

else{if(嗜好来自网关节点)

{保存网关信息至网关列表;

据网关机制决定本节点是否为网关节点;

if(选定本节点为网关节点)

{置本节点当前态为网关节点态;

将与簇相关信息填入嗜好消息中;}

else{置本节点为普通节点状态;

bForward=false;}}

else{bForward=false;}}break;

case NS_HEADER:

if(嗜好来自网关节点)

{将与簇相关的信息填入嗜好消息中;}

else{bForward=false;//丢弃该包}break;

case NS_GATEWAY:

if(嗜好来自网关节点)

{将与簇相关的信息填入嗜好消息中;}

Else{bForward=false;//丢弃该包}break;case NS_ORDINARY:

if(嗜好来自簇首节点)

{if(簇首不属于现存的簇首)

{保存该簇首信息;iHeaderCount++;}

if(iHeaderCount＞=2)

{置本节点当前状态为网关预备状态;

将与簇相关信息填入嗜好消息中;}

else{bForward=false;//丢弃该包}}

else{bForward=false;//丢弃该包}break;}}

if(bForward)//将嗜好消息往下转发

((DiffusionRouting*)dr)－＞

sendMessageToNext(msg，h);}

3.3 CBODD协议性能分析

在一个节点随机分布、无限大的无线传感器网络区域中取一小块区域(X×Y m2)为例来分析，在该区域内随机分布了N个节点。

首先考虑最坏即节点密度最大情况下，簇首节点的覆盖半径为R，两簇首间距为R，则转发节点的个数为:

因分簇而减小的消息比率为:

因分簇而减小的消息比率为:

假设该区域为1 000 m×1 000 m，R=250 m，则转发节点在密度最大情况下共有56个，而在平均密度情况下共有21个，因此如果在该区域内有1 000个节点的话，则可以抑制超过94.4%的转发消息数。

4 仿真试验结果及分析

在NS－2.27中通过改变仿真参数实现实际无线传感器网络的模拟。分别对每种情境下传统的定向扩散路由协议和基于分簇的定向扩散路由协议进行仿真，并对所获得的仿真数据进行统计。设定节点的发送功率为0.660 W，节点的接收功率为0.395W，同时假设节点侦听与休眠状态的能量消耗功率均为0。

能量有效性试验结果如图2所示。在图2中可以看到，随着网络规模扩大(网络中节点数增加)，DD与CBODD的平均消耗能量均呈上升趋势，然而，CBODD的平均消耗能量要比DD低得多。结果表明，CBODD利用分簇来抑制泛洪传播的冗余消息提高能量有效性效果显著。网络平均延迟比较结果如图3所示。随着网络规模扩大，DD协议与CBODD协议的平均延迟均有所上升，但DD协议增长很快，即在节点数增加的情况下，由于泛洪传播冗余消息的影响，平均延迟显著增大，这表明，CBODD协议采用分簇机制来简化网络拓扑，不仅不会增加网络平均延迟，相反会使网络延迟性更好。

图2 DD与CBODD能量有效性比较

图3 DD与CBODD网络平均延迟比较

［1］A l－ KARAKI JN，KAMAL A E.Routing techniques in wireless sensor networks:a survey［J］.IEEEWireless Comm，2004(11):6 －28.

［2］INTANAGONWIWAT C，GOVINDAN R，ESTRIN D.Directed diffusion:a scalable and robust communication paradigm for sensor networks［C］//Proceedings of ACM MobiCom.Boston:MA，2000:56 －67.

［3］Y IY，GERLA M，KWON T J.Efficient flooding in ad hoc networks using on－demand(passive)cluster formation［C］//Proc of the 3rd ACM MobiHoc.Lausanne:［s.n.］，2002:217 －225.

［4］L IANG X Y，LIU Q .A new model and route protocol of cluster－ b ased wireless sensor network［J］.Computational Intelligence and Industrial Application，2004(12):28－30.

［5］S HELTMAI T，MOUFTAH H.A comparative study of on－demand and cluster－based routing prototols in MANETs［C］//Proceedings of IEEE IPCCCWorkshop on EWCN.Arizona:［s.n.］，2003:291 －295.

［6］刘 泉，梁小宇.一种基于被动分簇算法的能源有效无线传感器网络模型［J］.计算机工程与应用，2007，43(16):142 －145.

［7］MANJESSHWAR A，GRAWAL D P.TEEN:a protocol for enhanced efficiency in wireless sensor networks［C］//Proc of the 15th Parallel and Distributed Processing Symp.San Francisco:IEEE Computer Society，2001:2009－2015.

［8］Q IAN Y，ZHOU J F，CHEN K S.Prolonging the lifetime of wireless sensor network viamultihop clustering［C］//NEW2AN.［S.l.］:［s.n.］，2006:118 －129.

［9］S ILVA F，HEIDEMANN J，GOVINDAN R.Network routing application programmer's interface(API)and walk through 9.0.1 ［R］.LOS Angeles:Information Sciences Institute，USC，2002.

［10 周琴，李腊元.基于双簇头的无线传感器网络多跳路由协议［J］.武汉理工大学学报:信息与管理工程版，2010，32(2):202－205.