长距离带状无线传感器网络路由协议设计

王 伟



长距离带状无线传感器网络路由协议设计

王 伟

(中煤科工集团沈阳研究院有限公司，辽宁 抚顺 113122)

带状网络的长带状特性会影响无线传感器网络路由协议的性能，导致网络出现“热区”。针对该问题，提出一种能量均衡的多跳路由协议CRLDB。该协议主要采用非均匀分簇的思想，引入备选簇首竞争半径的概念和相应的竞争策略，并加入最优簇首个数、节点剩余能量和周围邻居节点个数的簇首选择机制，使节点的剩余能量和传输能量达到平衡。NS2仿真实验结果证明，与LEACH和LEACH-C协议相比，CRLDB在网络的生存时间、整体能耗和基站收到的数据量这3个性能指标上有较大程度的提高，能更好地均衡网络的能量消耗，提高网络的生命周期。

无线传感器网络；分簇；长距离带状网络；路由协议；CRLDB协议；簇首

1 概述

无线传感器网络(Wireless Sensor Network, WSN)[1]由大量的传感器节点组成，节点通过本身的各种传感器采集数据，通过无线通信的方式，传递信息到目的地，共同完成某一目标的智能型无线网络。无线传感器网络是计算机科学技术的一个重要研究领域，受到学术界和工业界的高度重视，对人类的社会生活和工业变革造成巨大的影响[2]。

WSN节点具有能量有限的特点，因此，WSN路由协议一直是研究的热点，如何提高网络的生命周期成为其主要目标[3]。在以往的研究中，已经有很多种路由协议，如定向扩散协议DD(Directed Diffusion)[4]、自适应路由协议SPIN (Sensor Protocol for Information via Negotiation)[5]、低功耗自适应聚类路由协议LEACH(Low Energy Adaptive Clustering Hierarchy)[6]、能量高效的路由协议TEEN(Threshold sensitiveEnergy Efficient sensor Network protocol)[7]、PEGASIS(Power- efficient Gathering in Sensor Information Systems)[8]等协议。文献[9]提出了一种能量高效均衡的分布式分簇路由协议DEBUC(Distributed Energy-balanced Unequal Clustering routing protocol)，采用贪婪算法在邻居簇头集合中选择其中继节点，达到延长网络生存周期的目的。文献[10]提出了一种基于双簇头交替和压缩感知的WSN路由协议DCHACS (Double Cluster Head Alternation and Compressed Sensing)，采用双簇头交替机制分担簇头的负担，簇头节点利用压缩感知理论进行数据融合。文献[11]提出了以非均匀分簇的思想来均衡簇头节点能耗，簇间采用多跳方式，簇内通信能耗和成员节点数量成比例关系，使得所有簇头的能耗接近，网络能量消耗均衡。

但在特定环境中，如长距离的街道、带状的峡谷、长带状河流、跨江大桥、高速公路、井下巷道等环境，无线传感器网络需要布置成狭长的带状结构。对于这种特殊的长带状网络，传统的WSN路由协议在此场景下存在局限性，因此，本文设计长带状网络条件下能量均衡的路由协议，协议中采用分簇的结构，通过大小不等的簇的结构提高网络的性能。

2 一种能量均衡的多跳路由协议

本文研究的网络拓扑结构为长距离带状，主要应用在河流、跨江大桥、煤矿巷道等特殊环境。因此，本文设计一种长距离带状网络环境下的分簇路由协议(Cluster- based Routing in Long Distance Band-type network, CRLDB)。CRLDB协议也是基于分簇的路由协议，但不同于LEACH，由于网络呈长带状分布，若采用单跳路由形式，距离汇聚节点远的节点能量很容易耗尽。一般来说，通过动态分簇的形式可以大大地减小网络的负载，把能量的消耗平均在整个网络的所有节点上，这样就可以提高网络的有效性，尽可能减少节点死亡的概率，提高网络的生命周期。CRLDB协议采用多跳的形式，以动态的方式进行簇首的簇首选举，簇首一旦确定，网络内的簇结构便建立起来。当网络呈长带状分布时，信息流一般向一侧流向汇聚节点，假设数据融合量很小，这样数据流就会呈“棒槌”状，越靠近汇聚节点数据量越大，造成的“热区”问题更为严重。故本文的核心思想是利用非均匀分簇，越靠近汇聚节点簇的规模越小，来解决“热区”问题，平衡整个网络的负载，提高网络的生存时间达到增加网络寿命的目的。

2.1 基本网络模型

为了更有利于协议的研究，本文给出如下假定：

(1)传感器网络由个普通传感器节点和1个汇聚节点(由Sink表示，也可以叫基站)组成，其中普通节点具有相同的计算、通信能力和初始能量水平，而汇聚节点的能量和计算能力是没有限制的。

(2)汇聚节点位于带状网络的一端，网络部署完毕后，所有节点(包括Sink节点)都是静止不动的。

(3)传感器节点具有全网唯一的ID，同时链路是对称的，若已知对方发射功率，节点可以根据接收信号的强度计算出发送者到自己的近似距离。

(4)节点可调整自己的无线电发射功率，也就是节点可根据通信距离长短来调整发射功率的大小。

2.2 能量传输模型

本文采用与文献[12]相同的无线能量模型，发送节点和接收节点之间的距离小于0时，采用自由空间模型，发射功率呈2衰减；否则采用多路径衰减模型，发射功率呈4衰减，能量消耗定义如下：

2.3 簇首选取策略

2.4 非均匀簇的建立

在网络部署阶段，基站节点以一个固定的发送功率向全网内广播一个Hello信号。每个传感器节点在接收到这个信号后，根据接收信号的强度来计算它到基站的近似距离n。这个距离n在本文非均匀分簇中用来计算簇的半径的必要参数。一旦某个节点通过上面的簇首选择公式计算成为备选簇首节点，就可以根据下面的计算公式来算出备选簇首的覆盖半径半径e的大小。

备选簇首半径e的计算公式如下：

其中，1、2是普通参数，0<1、2<1，且有1+2=1，max是网络中所有节点与Sink节点距离的最大值，min是网络中的所有节点到Sink节点的最小值，0为簇的最大半径。

当簇首节点距离基站最远时，且当前节点剩余能量等于初始能量时，=max、cur=int，有e=0，此时簇的范围最大。随着节点与基站距离的减小，簇首的剩余能量的降低，簇的覆盖范围随之也变小，当簇首距离基站最近时，=min，e=20cur/int，式中只有cur为变量，因此，此时簇的覆盖范围随着节点的剩余能量的减少而逐渐降低。 同时也考虑节点剩余能量的状况，节点的剩余能量越高，它的覆盖半径越大；反之，节点的剩余能量越低，它的覆盖半径越小，这样它传输的距离就相对较小，更能节约能量。备用簇首的覆盖半径如图1所示。

图1 备选簇首非均匀分簇效果

定义1(竞争半径) 本文定义备选簇首的参数e的大小为竞争半径。

定义2(簇首的竞争规则) 在竞选过程中，若某个备选簇首成功当选，则在它的竞争半径范围内的所有其他备选簇首都退出，从而转变成普通节点。

图2给出了一张由4个备选簇首组成的拓扑结构图，其中1、2、3、4为备选簇首节点。由上面的规则得出，3和4可以同时成为最终簇首，而1和2则不能同时成为最终簇首，因为2位于1的竞争区域内部，因此，只有1、3、4成为最终簇首，而2转变为普通节点。

图2 备选簇首的竞争过程

2.5 簇间数据传输策略

算法的主要步骤如下：

当一个簇首节点(假设为簇首节点)想要发送数据包给基站时：

(1)选择能量参数()，()包含2个部分：

2)中间节点本身的剩余能量，参数()计算式如下：

其中，AX是节点到未知节点的距离；X−BS是未知节点到基站(BS)的距离，resX是未知节点的剩余能量。集合S为簇首节点下一跳路由的所有可能的簇首节点。集合S的定义如下：节点N经过多跳路由传送数据包到基站时，下一条路由节点N的集合S为：

(2)从上式中可以得知，当cur=int且d=min时，簇首e的半径为最大值，即emax=0。所以簇首A以半径为20向集合S中的簇首发送自己的ID路由信息，接收簇首在本地计算()，反馈给簇首。

(3)簇首A得到反馈数据后比较()，选择使()值最小的节点X，即min()。若通过计算发现未知节点X是节点的话，那么就直接把数据传给基站。否则，选择未知节点(这里假设节点)作为传输到基站的一个中间节点。

(4)如果节点被选作中间节点并从簇首节点A收到数据包的话，接下来簇首节点按式(5)继续寻找一个跳的簇首节点。

(5)重复步骤(1)~步骤(4)，直到数据传输给基站为止。

2.6 CRLDB路由协议的具体过程

CRLDB路由协议的具体过程如下：

阶段1网络部署

在开始阶段，让基站以一定的功率向整个网络广播一个消息Information_MSG。传感器节点根据接收信号的强弱估算出自己到基站的近似距离d，在与基站通信时，依据这个距离选择适当的发射功率。在成簇阶段，还将利用这个信息来均衡簇首的负载。

阶段2簇头选举

根据预先一个设定好的0~1之间的阈值new()，用来控制参加簇首竞选的节点比例。每一个节点生成一个0~1之间的随机数，记为。若new()，则该节点成为簇头备选节点，然后每个备选节点延迟时间后，在竞争半径内广播一个竞选消息COMPETE_HEAD，内容为自身标识符。只有在半径覆盖范围内的备选节点才能接收到此消息。若有备选节点N接收到备选节点N广播的消息后，则N立即放弃竞选，变成普通节点。一定时间后，竞选消息在网络内传播结束，表明该阶段完成。剩余的备选节点则成为此轮选举产生的簇首。

阶段3簇类形成

簇首在竞争半径内广播自己成为簇首的消息HEAD_AD，普通节点接收到此消息后，加入这个簇首所在的簇，最终形成一个个簇类。

阶段4 数据传输

簇首头向所有成员节点广播TDMA通信时隙调度信息TDMA_SCHEDULE。成员节点按分配好的TDMA时隙在某个时刻将自己检测到的数据发送给簇首。簇首在接收聚类成员发送数据的过程中进行数据融合后，寻找下一跳路由的路径，规则是在集合S中寻找一个使()最小的簇首节点作为下一跳路由。以此类推，最后形成从簇首到基站的一条或条近似链状的路。

图3给出了CRLDB路由协议每一轮算法的流程。

图3 CRLDB路由协议算法流程

3 实验及结果分析

3.1 最优簇首个数Kopt的确定

在上文中提及最优簇首opt的计算公式为：

可见最优簇首Kopt和节点的个数、节点到基站的距离等参数有关。场景1和场景2节点与基站的距离分别为：75

图5 簇首个数与网络运行时间关系(场景2)

3.2 网络的生命周期

图6和图7是场景1和场景2中网络运行时间与存活节点个数的关系。可以看出，LEACH、LEACH-C、CRLDB 3种路由协议随着网络的运行时间的增加，在开始一段时间之后，网络的节点开始逐渐死亡，直到所有的节点全部死亡为止。同时可以看出，LEACH、LEACH-C的性能相互相近，但LEACH-C的性能比LEACH更好。

图6 3种路由协议网络运行时间与存活节点个数的关系(场景1)

图7 3种路由协议网络运行时间与存活节点个数的关系(场景2)

3.3 网络的总体能耗

图8与图9分别给出了在2种场景下，随着网络运行时间的变化网络所消耗的能量的变化关系。从图中可以看出，在场景1中，LEACH、LEACH-C协议约在网络运行570 s左右时网络的能量被耗尽，而CRLDB协议在整体能量被耗尽时网络运行了超过800 s，性能提高了约40%。在场景2中，当网络中能量被耗尽时，CRLDB协议运行时间分别比LEACH、LEACH-C提高了61%和41%。从而看出，当网络规模变大时，CRLDB的性能更加显著。

图8 3种协议网络运行时间与网络消耗总能量的关系(场景1)

图9 3种协议网络运行时间与网络消耗总能量的关系(场景2)

4 结束语

本文通过对长距离带状网络的分析，提出一种基于非均匀分簇的路由协议CRLDB，并介绍相关算法。通过仿真证明，CRLDB协议能改善由“热区”效应带来的能量消耗不均衡的问题。今后的主要研究方向是在特殊网络或者特定环境下对WSN路由协议进行改进，延长网络生命周期。

[1] 于海斌, 曾 鹏. 智能无线传感器网络系统[M]. 北京: 科学出版社, 2006.

[2] Karl H, Willim A. Protocols and Architectures for Wireless Sensor Networks[M]. 丘天爽, 译. 北京: 电子工业出版社, 2007.

[3] 路 纲, 周明天, 佘 堃, 等. 无线传感器网络路由协议的寿命分析[J]. 软件学报, 2009, 20(2): 375-393.

[4] Intanagonwiwat C, Govindan R, Estrin D, et al. Directed Diffusion for Wireless Sensor Networking[J]. IEEE/ACM Transactions on Networking, 2003, 11(1): 2-16.

[5] Kulik J, Heinzelman W, Balakrishnan H. Negotiation Based Protocols for Disseminating Information in Wireless Sensor Networks[J]. Wireless Networks, 2002, 8(2/3): 169-185.

[6] Heinzelman W, Chandrakasan A, Balakrishnan H. Energy- efficient Communication Protocol for Wireless Microsensor Networks[C]//Proc. of the 33rd Annual Hawii International Conference on System Sciences. Maui, USA: IEEE Computer Society, 2000: 1-10.

[7] Manjeshwar A, Agrawal D. TEEN: A Protocol for Enhanced Efficiency in Wireless Sensor Networks[C]//Proc. of the 15th IEEE International Parallel and Distributed Processing Sym- posium. Hawaii, USA: IEEE Computer Society, 2001: 23-27.

[8] Lindsey S, Raghavendra C S. PEGASIS: Power-efficient Gathering in Sensor Information Systems[C]//Proc. of IEEE Aerospace Conference. San Francisco, USA: IEEE Computer Society, 2002: 1-6.

[9] 蒋畅江, 石为人, 唐贤伦, 等. 能量均衡的无线传感器网络非均匀分簇路由协议[J]. 软件学报, 2012, 23(5): 1222-1232.

[10] 赵小川, 周 正, 秦智超. 基于双簇头交替和压缩感知的WSN路由协议[J]. 软件学报, 2012, 23(1): 17-24.

[11] Soro S, Heinzelman W B. Prolonging the Lifetime of Wireless Sensor Networks via Unequal Clustering[C]//Proc. of the 19th IEEE International Parallel and Distributed Processing Symposium. Denver, USA: IEEE Computer Society Press, 2005: 4-8.

[12] Shepard T. A Channel Access Scheme for Large Dense Packet Radio Networks[C]//Proc. of ACM SIGCOMM. Cambridge, USA: Association for Computing Machinery, 1996: 1-12.

编辑 金胡考

Design of Routing Protocol in Long Distance Band-type Wireless Sensor Network

WANG Wei

(CCTEG Shenyang Engineering Co., Ltd., Fushun 113122, China)

Aiming at the problem that characteristics of the long distance band-type network will constrain the effect of general Wireless Sensor Network(WSN) routing protocols, and causes a “hot spot” problem in long distance band-type network, this paper introduces the energy balanced consumption multi-hop routing protocol CRLDB. It takes the idea of non-uniform cluster, concept of competition radius and the corresponding competitive strategy, and joins the number of cluster head node selection mechanism with the optimal number of cluster head, node residual energy and the surrounding neighbors, to balance nodes residual energy and transmission energy. Simulation by NS2 shows CRLDB routing protocol, compared with existing routing protocols Low Energy Adaptive Clustering Hierarchy(LEACH), LEACH-C for the survival time in the network, the network’s overall energy consumption and the amount of data received by base stations, CRLDB protocol with several performances in the above has a large improvement, can balance the network’s energy consumption and increase the network’s lifetime.

Wireless Sensor Network(WSN); clustering; long distance band-type network; routing protocol; CRLDB protocol; cluster header

1000-3428(2014)03-0132-05

A

TP393

王 伟(1984－)，男，助理工程师、硕士，主研方向：无线传感器网络。

2012-12-14

2013-03-21 E-mail：forrestwang113@gamil.com

10.3969/j.issn.1000-3428.2014.03.027