基于最佳簇半径的无线传感器网络分簇路由算法

武 一，李家兴，范书瑞，岳雨豪

（河北工业大学 电子信息工程学院，天津300401）

0 引 言

无线传感器网络（Wireless Sensor Network，WSN）是由若干个分布在被监控范围内的传感器节点构成的网络，这些节点以随机或者确定位置分布的形式布置在被监测范围内，可以收集温度、湿度、光照条件、地震活动等方面的数据，在军事和民用环境中有着非常广泛的应用。由于传感器节点数量较多，计算能力、内存和传感器的电源功率有限，能量问题就成了无线传感网络需要解决的关键技术之一[1]。为了解决上述问题，无线传感器网络中的路由算法的设计极为重要。

无线传感器网络中，路由协议技术主要有两种：平面型路由协议以及分层型路由协议[2]。在第一种平面型路由技术中，所有节点都被平等对待，比较有利于相互协作。在网络中，一些协议要求部分节点不仅仅只是要收集、存储周围的数据，还需要作为中继节点转发来自其他节点的数据，使得这类传感器节点的能量消耗过快而提前失去工作能力，从而致使网络的瘫痪失效[3]。在第二种分层型路由算法中，通过分层的形式将整个大网络分成多个互不相关的集群，将这个集群称为簇[4]。每个簇由簇内成员节点和簇头组成，其中，簇头承担数据转发的功能，负责收集节点收集的信息，并将其传送给基站，而且可以缩短传输距离，进而降低能耗。

本文提出一种基于最佳簇半径的分簇路由算法LEACH-OR（Low Energy Adaptive Clustering Hierarchy based on Optimal cluster Radius）算法。该算法主要思想是根据网络范围大小和簇头数目初步划分网络，首先计算出每个小网络的最优半径，按照该半径对网络进行划分，使簇的分布更加均匀。其次在进行簇头选取时，加入节点当前剩余能量和距离的控制因子。优化簇头的选举阈值公式，使簇头选举更加均衡合理，簇与基站之间的数据传输采用多跳的方式，以减小通信间的能耗。对比仿真验证了该路由算法的优越性，其可以有效地平衡网络的能量损耗，提高能量利用效率，最终实现增加网络寿命的目标。

1 相关研究

文 献[5]提 出 的LEACH（Low Energy Adaptive Clustering Hierarchy）算法是一种最具代表性的分层型路由算法。通过设计好的分层算法和节点轮流当选簇头的工作方式来平衡网络的能量损耗，但是在LEACH算法中簇头的选取和分布具有随机性，当能量小或者位置较为偏远的节点被选择为簇头时会加快节点的失效。韩广辉等人提出了一种节能路由协议LEACH-improved算法[6]。LEACH-improved算法通过增加间距算子、剩余能量算子和节点密度算子对阈值公式进行优化，解决了随机选择簇头造成网络能耗过快的问题。黄利晓等人提出了LEACH-E（LEACH based on Energy）算法[7]。该算法在簇头选择的阈值公式里引入了节点的剩余能量和网络当前平均能量，使得节点能量比平均能量多的成员节点具有更大概率被选作簇头。普通节点的数据包中含有节点的能量数据，将其转发给基站以获取当前整个网络的能量平均值，使基站也可当作簇头以降低网络的能耗。LEACH-improved与LEACH-E两种算法通过改进阈值的计算公式，一定程度上可以减小能耗，但其没有解决簇头分布不均匀以及单跳传送能耗过大的问题。

2 系统模型

2.1 网络模型

假设在一个设定范围大小的监测范围内，随机布置多个传感器节点，并且这些节点持续对该区域进行监测。这些传感器节点具有以下性质[8]：

1）监测范围大小已知，传感器节点在监测范围内随机布置。

2）传感器节点的电量是有限的，放置后每个节点的ID固定不变，且坐标公开。

3）网络中传感器和基站的位置确定后均不会产生变动。

4）每个节点拥有的功能一样，具有同样的计算和数据融合能力。

5）节点布置完成后将不能修复，即传感器不能进行二次充电。

6）所有节点的传输功率可以依据传输的距离自动调整。

2.2 能耗模型

本文采用一阶无线电模型作为能量消耗模型。节点在发送数据时，采用发送电路发送数据，并且使用放大电路对信号进行放大；接收端接收数据时，采用接收电路解析数据[9]。节点与节点间产生数据通信时，节点的能量消耗与发送端和接收端的距离大小有关。当发送端节点向间距为d的接收端节点传送数据时，发送端消耗的能量大小为：

式中：k为数据量的大小，单位为bit；Etx为传输数据能耗；Eelec为传输1 bit数据所需的能量；εfs和εmp为不同信道传播模型下的功率放大电路能量损耗系数，其中，信道方式的选择受传输距离大小的影响是传输距离阈值。当发送的间距小于或等于该值时，使用自由空间信道模型，放大电路能量消耗系数为εfs；若发送的间距大于该值，使用多路径衰减信道模型，放大电路能耗系数[10]为εmp。

3 基于最佳簇半径的分簇路由算法

3.1 分簇优化

由能量消耗公式可以得出，传输消耗的能量大小和信号传输距离有关。节点之间的间距越大，传输所需的能量就越大；间距小，所需能量就较小。在网络工作时，基站首先在监测范围内广播信号。然后，所有节点根据收到信号的强度，计算出自身位置与基站的间距，并将本身的坐标ID和当前能量信息发送至基站。这样基站就知道网络内所有节点的当前能量与距离，即节点能否当选簇头的重要参数。为减少簇内通信的能耗，簇头应尽量均匀散布在监测范围内，以保证各个簇均匀分布。若监测区域范围大小为M×M，其中，簇头节点的数量为n，则每个簇的平均面积S以及最优簇半径R为：

当一个簇头选定好之后，那么在该节点最优簇半径R范围内的其他节点就不再进行簇头的选举，从而使簇头平均分布，如图1所示。

图1 簇半径分簇模型

与LEACH算法相似，LEACH-OR算法也是通过阈值公式进行簇头的选取。每一轮次中，每个节点首先生成一个0～1之间的未知数μ，然后与阈值T(n)比较，若小于阈值T(n)，则该节点被选作簇头。其中，阈值T(n)的计算公式为：

式中：p为簇头占网络节点总数的比值；r为当前轮次；G为在上次1p轮节点没有被选中过作簇头的集合。为减小能量低的节点和位置较远的节点被选择为簇头的概率，设置一个控制参数Q，目的是使当前轮次能量更多，位置距离更近的节点更容易被选择为簇头。其中，Q的计算公式为：

式中：α，β为权重因子，它们之间的关系为α+β=1，可通过改变两个因子的值来控制节点能量和节点位置的比重；Ei(r)为第r轮该节点的自身能量；Eavg(r)为第r轮当前网络的平均能量。

第r轮节点的当前自身能量越大，阈值T(n)也会变大，节点变成簇头的可能性也会变大。如此加大了能量高的这一类节点被选作簇头的概率。Davg(r)为第r轮整个网络中剩余节点与基站间的平均距离：

Di(r)为当前节点距基站的距离：

相同条件下，Di(r)越大，该节点至基站位置的间距也更大，则该节点对应的阈值就会相应的变小，当选簇头的概率也会减小。减小位置远的节点被选作簇头的概率，增加位置近的节点被选作簇头的概率，从而达到减小因距离过大产生的能耗。

3.2 簇间通信

全部簇头节点都确定后，簇头节点广播消息到网络中，非簇头的普通节点选取一个信号强度最高的簇头加入构成簇，簇内所有节点收集数据。之后通过单跳通信方式数据发送给簇头。若两个间隔为d的节点发送数据大小为kbit时，发送间距d＜d0时，发送端消耗的能量大小满足：

发送间距d＞d0时，消耗的能量大小满足：

接收端消耗的能量为：

式中kEelec指信号处理消耗的能量。如果簇内成员节点的数量为L，则簇头损耗的能量为：

若簇头与基站间距较近，则簇头把数据单跳发送至基站，而间距基站远的簇头则通过多跳的方法进行数据传送，选择路径上其他簇头当作中继节点。先将数据发送至该中继节点，再通过中继节点发送至基站。若有A，B两个簇头节点，基站为BS，距离之间关系如下：

则由距离计算其能耗，能耗之间的关系为：

由式（14）可以看出，多跳传送的能耗方式要小于单跳。因此在数据传输时，若簇头节点间满足式（13），则簇头通过满足条件的另一簇头作为中继节点传输数据至基站。

4 仿真实验

实验采用Matlab仿真软件分别对上述提到4种算法做对比仿真，主要观察各种算法的网络生命周期，网络能量消耗对比。表1给出了该对比实验的基本参数。

实验仿真设置200个节点分布在200×200大小监测范围内的分布图。基站坐标设置在图中原点（0，0）位置。该对比仿真实验一共为2 000轮次。图2显示了网络有效工作时间内各算法每一轮存活节点的曲线。

图2 呈现了各个算法在每一轮工作周期后，网络中还仍然生存的节点数目的对比。由图2中曲线得出，LEACH算法存活节点数量最先开始降低，第一个失效节点出现在第159轮次。LEACH-improved算法在287轮出现第一个失效节点，在该轮次LEACH算法大约失效了10%的节点。LEACH-E算法在492轮出现首个失效节点。LEACH-OR算法在970轮才出现首个失效节点，此时其他三种算法的失效节点数均已经超过总数的50%。1 300轮后各种算法的失效节点均超过80%。

表1 仿真参数设置

图2 网络生命周期曲线

图3 呈现了网络工作过程中每一轮次各个算法的网络总剩余能量，展示了LEACH-OR算法及其他三种算法的能量消耗速度对比。由图3中能看出，LEACH算法的能量损耗最快，LEACH-OR算法相对于其他三种算法的能耗速度都要缓慢，能量损耗更加平均；且在相同工作内，LEACH-OR算法的节点剩余存活数量要高于其他算法，能有效地加长网络的工作时间。

5 结 语

LEACH-OR算法是以LEACH算法原理为基础，针对其缺陷改进的一种算法，综合研究了剩余能量和节点坐标与基站距离等条件对网络工作时长的影响。在簇头选择的阈值公式中加入控制因子，分析节点能量及位置等因素对网络影响程度，设置合适的权重，并且依据最优簇半径划分簇，优化簇头节点的分布，使用多跳发送的方式减少节点消耗。由LEACH-OR算法与LEACH、LEACH-improved、LEACH-E等算法的性能对比仿真结果可以看出，LEACH-OR算法经历的工作轮数更长，能量消耗更加平均，各项性能均有提升。

图3 网络能耗曲线