分区域的树型多链的无线传感器网络路由算法

方旺盛，彭美平，胡中栋

（江西理工大学 信息工程学院，江西 赣州 341000）

无线传感器网络（Wireless Sensor Network，WSN）广泛应用于智慧农业、环境监控、战场监控和动物跟踪等方面，其由传感模块、存储模块、计算模块、电源模块组成。由于传感器节点体积小，自身的计算、通信能力及存储能量有限，WSN监测的区域广，部署的传感器节点众多，无法为大量传感器节点更换电池等缺陷，使得有效节省全网节点能耗成为需要解决的重要问题。路由协议是影响传感器节点能耗的主要因素之一，也是提高无线传感器网络寿命的一个关键因素，其中分簇路由协议是路由协议的一类，因其节省能耗而被广泛应用。基于此，本文提出一种分区域的树型多链的无线传感器网络路由算法。

1 经典分簇路由算法分析

1.1 LEACH算法

LEACH算法将全网节点分成几个簇，簇内能进行数据融合，可节省能耗，但簇头节点需进行数据计算，直接与sink节点通信等需消耗较多能量，会造成全网节点能量不均衡。因此LEACH算法会不断进行簇重构、簇头的重新选举，这将会增加额外的能耗。

1.2 PEGASIS算法

PEGASIS（Power-Efficient GAthering in Sensor Information Systems）算法将全网节点形成一条长链，链中相邻两节点间的距离相对较短，且数据传输时节点轮流当选链头与sink节点通信，不用簇的重构、簇头的重新选举等，节省了开销。但PEGASIS算法仍然存在以下不足：第一，若无线传感器网络中节点数目较多，连接过程中形成一条长链，会存在链的交叉、数据逆传等问题，节点能量利用率不高；第二，在所构建的链中，远距离的节点会引起过多的数据延时；第三，该协议所成链中只有一个链头节点，使得链头节点成为整个网络的瓶颈。

1.3 COSEN算法

COSEN（A Chain Oriented Sensor Network）算法将整个全网所有节点形成的一条长链拆成几条短链，减少了链路长度，每条分链同时收集数据进行处理、融合，大大降低了网络时延。当网络中某个节点死亡时，只对当前分链和链头节点形成的主链进行维护，维护成本相对较低。但依然存在如下不足：第一，链内存在交叉，易造成数据的回传；第二，链间存在交叉，易造成算法的局部最优。

2 本文算法

针对COSEN算法存在的缺陷，文献[11]提出一种多级分层链路算法。该算法按照节点与基站的距离对全网节点分层，每层节点之间采用贪婪式的方法形成一条链。该算法虽然大幅降低了全网总能耗，但仍然存在缺陷：第一，若纵向的不在同层的2个节点相距较近，则无法连接到一条链，容易造成节点间跨度较大，增加能耗；第二，节点容易形成横向跨度较大的长链，从而造成节点的检测数据差别较大，不利于数据融合；第三，若sink节点在网络区域内部，将形成半圆环的链或圆环的链，内链长度短，外链长度长，易造成节点能量消耗不均衡。鉴于以上讨论，首先，本文算法将全网节点根据数据的相关性分为若干个长条状的区域，克服文献[11]算法中纵向的不同层次的2个节点相距较近，而无法连接到一条链的情况；其次，本文算法区域中的节点根据它们之间的距离和角度形成树型结构的链，克服文献[11]算法中横向成链使整条链较长，从而节点的检测数据差别较大，不利于数据融合的问题；最后，本文算法将sink节点部署在网络区域，弥补文献[11]算法中sink节点部署在网络区域内能量消耗不均衡的情况。

2.1 算法设计思路

本文算法根据数据的相关性，将全网区域分成若干个长条状的区域，在每个区域中根据节点之间的距离和角度连接成一条链。成链过程中若产生交叉链，删除两交叉链中链较长的那个，这样会产生孤立节点，各个分区域内的孤立节点找本区域中已经成链的节点连接；区域外的孤立节点也找到已经成链的节点连接，这样就形成了分区域的树型多链结构。各分链链头根据它们之间的距离和角度连接形成树型主链，主链链头与sink节点通信，或者各分链链头直接与sink节点通信，即各分链链头采用单跳和多跳相结合的方式与sink节点通信。

2.1.1 无线传感器网络分区

在无线传感器网络中，当传感器节点在网络区域随机部署完毕后，节点将检测数据发给邻居节点，邻居节点根据收到的数据将从离sink节点近的节点开始依次向外将全网区域分成若干区域。在分区域过程中判断该区域是否为长条状区域，即区域的长宽是否在上下阈值之间。若区域的长宽低于上下阈值，则区域中加入新的节点；若区域的长宽超过上下阈值，则区域中去掉加入的节点或者更换节点加入，直到整个分区域在上下阈值之间。从离sink节点近的节点开始依次向外划分，直到所有区域划分为长条状区域。对于网络边缘的区域，节点往往比较稀疏，网络区域可以不满足设定阈值，只要节点能量消耗小即可。分区域流程如图1所示。

图1 分区域流程图

分区过程的伪代码如下：

2.1.2 区域内的节点连接成链

将整个网络区域分成几个长条状的区域后，在每个子区域中根据节点之间的距离和角度将节点连接成一条链，具体成链过程如下：

如图2所示，在一个分区域中，节点为该区域的终节点，节点为将要成链的节点，以节点为例来说明具体成链的过程。节点的下一跳节点从它的相邻节点中选取，有，，，，，共6个节点。选择哪个节点作为节点的下一跳节点，取决于下式：

式中：d 为节点到节点的下一跳节点的距离；为节点到节点连线与节点到下一跳节点连线的夹角。将，，，，，共6个节点代入式（1），显然，W ＜W ＜W ＜W ＜W =W =，选择使W 值最小的节点为下一跳节点。然后依据式（1），用节点和它下一跳节点之间的距离和角度两个因素相结合的方式将节点连接起来形成一条链，若成链过程中产生交叉链，删除两交叉链中链较长的那个，这样可形成分区域的主干链。

区域中的节点形成主干链的过程中，会产生如图2中，，，，这样的孤立节点。这些孤立节点按照式（1）找到本区域中使它们的值最小的下一跳节点连接。

图2 区域内节点连接成链

图3中节点、节点、节点分别与已成链节点、节点、节点建立连接。

若根据式（1），使孤立节点最小值的下一跳节点不在主干链上，那么离已成链节点近的孤立节点先根据式（1）找到使孤立节点最小值的下一跳节点，并计算值；然后找到孤立节点的下一跳在主干链上的节点，计算它们的值。最小的值记为；最小的值记为；最后比较和的值，找到值最小的下一跳节点连接。值计算公式如下：

式中：d 为节点到节点的下一跳节点的距离；为节点到节点连线与节点到下一跳节点连线的夹角；为节点要连的下一跳节点所在分支链中的节点个数。若孤立节点，使它的值最小的下一跳节点为节点，节点的最小值的下一跳节点为节点，节点和节点都不在主干链中，节点离已成链节点较近，为分支链中的第一个节点，且已连接到链中；接着节点离已成链节点较近，根据式（2）找到使节点最小值的下一跳节点为节点，并计算F 的值；然后在节点的邻居节点中找到下一跳在主干链上的节点，节点是节点下一跳在主干链上的节点中值最小节点，并计算W 的值。因为节点F ＜W ，所以节点的下一跳节点为节点。同理，因为W ＜F ，所以节点的下一跳节点为节点。区域中的孤立节点的链接如图3所示。

图3 区域内孤立节点连接成链

2.1.3 区域外的节点连接成链

分区域外的孤立节点分别找使它们的值最小的下一跳已成链节点连接成链，如图4中的节点、节点分别与已成链节点、节点连接。

图4 区域外的节点连接成链

2.1.4 链头节点的选举及通信

在形成的各条分链中，链中节点轮流当链头，轮流的原则遵循相邻链的链头之间的距离尽可能小。

各分链选出链头节点后，分链链头与sink节点的通信采用文献[13]中单跳和多跳相结合的通信方式。单跳时远处分链的链头节点耗能大，多跳时近处分链的链头节点耗能大。节点总的数据通信时间为，在·时间内，分链链头以单跳的方式与sink节点通信；在·( 1-)的时间内，分链链头以多跳的方式与sink节点通信。

分链链头的多跳传输需要成链，成链的规则和各分区域节点的成链规则一样，即根据链头节点之间的距离和角度形成树型主链。树型主链找到离sink节点最近的节点充当主链链头与sink节点通信。全网节点具体成链情况如图5所示。

图5 全网节点所成链路

2.2 算法伪代码

3 算法仿真与分析

本文设定的实验区域为100 m×100 m，区域中部署100个传感器节点。考虑到数据的相关性、链的长度、网络整体的时延及能耗，将整个传感器网络区域分为6个长条状的区域，长条状区域的长、宽的上阈值分别为100 m，20 m，下阈值为35 m，5 m。

本文采用Matlab仿真实验，并与在本区域中利用PEGASIS算法、COSEN算法、文献[11]的MSLR（Multistage Stratified Link Routing）算法进行仿真实验的结果进行对比，从节点的成链情况、节点死亡数目、网络能量消耗和时延四个方面进行分析评估。算法的仿真参数如表1所示。

表1 仿真参数

3.1 节点成链情况

图6中的4幅仿真图分别为PEGASIS算法、COSEN算法、MSLR算法和本文算法形成的仿真图。将四种算法成链情况做对比可以看出：前两种算法形成的链存在明显的交叉，整体较乱；而MSLR算法虽然比前两种算法有条理，但依然存在链间交叉和某些链较长的问题；本文算法形成的树型结构有明显的条理且无交叉，相比PEGASIS算法形成的链较短，相比COSEN算法和MSLR算法形成的链无交叉，可避免数据的回传。

图6 各算法链式图对比

3.2 能耗分析

本文以网络区域中全部节点到sink节点的一次数据传输为一个周期，对比四种算法在工作过程中节点的死亡数目和全网能量消耗情况，如图7、图8所示。从图7可以看出，本文算法比前三种算法的首个节点的死亡数量和全网所有节点的死亡数量都有所延长。本文算法的首个节点死亡的轮数大约在660轮，比PEGASIS算法、COSEN算法、MSLR算法的首个节点死亡的轮数分别延长了大约260轮、140轮、100轮。

图7 每轮死亡节点数对比

本文算法的全网全部节点死亡的轮数大约在920轮，比PEGASIS算法、COSEN算法、MSLR算法的全网全部节点死亡的轮数分别延长了大约180轮、90轮、70轮，本文算法生命周期有所延长。

从图8的全网节点能量消耗对比的仿真图可以看出，PEGASIS算法在740轮时全网能量基本消耗完毕，COSEN算法全网能量基本消耗完在830轮，MSLR算法在850轮时全网能量基本消耗完毕，本文的算法全网能量基本消耗完毕在920轮，在同一周期内比PEGASIS算法、COSEN算法和MSLR算法的全网节点能量消耗都小。

图8 全网节点能量消耗对比

3.3 时延分析

图9是四种算法从节点开始工作到第一个节点死亡时间内的时延情况对比仿真图。

图9 节点时延情况对比

从图9可以看出，本文算法时延最短，PEGASIS算法时延最长，并且比另外两种算法时延大得多。原因在于PEGASIS算法全网形成一条链，只有一个链头与sink节点通信，所以时延较大；COSEN算法和MSLR算法形成多条分链，分链节点同时传输数据，减少了时延。而本文算法将全网节点也分为几条短链，链中节点可同时传输数据，且短链是树型结构，相邻两节点相距较小，链中无交叉传递数据，所以比其他两种算法的时延都小。

4 结 语

本文通过将无线传感器网络分成长条状的区域，区域中的节点根据距离和角度连接成链，减少了节点之间的距离，使全网节点数据传输时延减小；并且区域中的节点之间无交叉，避免了数据的逆传递，减少了网络整体能耗。从整体上来看，节点传输数据时延缩短，节点的生命周期有所提升。

注：本文通讯作者为彭美平。