基于均匀分区的无线传感器网络路由算法

刘玉红，陈满银，李翠然

(兰州交通大学 电子与信息工程学院，兰州 730070)

无线传感器网络(wireless sensor networks，WSN)由数百甚至数千个传感器节点组成，收集监测数据供终端用户分析，被广泛应用于医疗保健、智能家居、农业工程和目标跟踪等各个领域[1-4].WSN有很多优势，包括自配置、组网灵活、经济有效、体积小等，而由于传感器节点的能量由电池供应，电池的能量是有限的，并且传感器网络经常部署在条件恶劣和无人坚守的环境，如救灾行动、矿产开采[5-6]，存在节点能量一旦耗尽便很难及时补充或更换的问题；因此延长网络寿命，提高能量利用率，实现高效能网络是WSN研究的主要目标之一.分层路由算法是解决这一问题的重要方法，它在网络中首先选举出若干个簇头，传感器节点根据簇头选择加入簇，然后将收集到的数据发送到簇头节点，簇头再将数据进行融合后转发到基站(base station,BS)，通过优化网络通信量达到节省网络能耗的目的[7].由于分层路由算法的实际应用效果优于平面路由算法，所以分层路由算法已经成为WSN节能路由算法研究的热点之一[8].

文献[9]提出了最具经典意义的LEACH算法，该算法提出了“轮循环”的思想，每轮根据阈值和赋给各节点的随机值来确定簇头，将网络能耗分摊到各个节点上，但因为在选择簇头时，没有考虑簇头的剩余能量和位置，导致能量较低的节点担任簇头而过早死亡以及分簇不均带来的簇头负载不均衡等问题.文献[10]在K-means算法的基础上，提出了EECPK-means算法，根据与基站之间的距离确定初始簇头，迭代计算得到最终簇头，在一定程度上使簇头的分布更加均匀；但存在节点连续多次充当簇头而过早死亡的问题.文献[11]提出了一种基于能量质心的路由算法，在选举簇头时，根据节点的剩余能量与位置信息计算出能量质心，将距离能量质心最近的节点作为簇头，减小网络的能量消耗；但存在簇头负载不平衡而影响网络寿命的问题.

本文在对上述文献进行分析研究后，提出一种基于均匀分区的无线传感器网络节能路由算法，首先通过改进的多叉树遍历算法选择随机且分布均匀的初始簇头，避免出现节点连续多次被选为簇头的问题；其次，节点根据自身与初始簇头之间的距离以及成员节点的数量来加入分区，均衡各分区内节点的个数，进而均衡各簇头的负载；接下来，再在各分区内优先选择剩余能量较多以及与其他节点之间的距离和最小的节点担任簇头，有效地减小网络能耗；最后进行数据收集和上传，其中，距离BS较远的簇头采用多跳通信的方式将数据转发到BS.

1 WSN能耗模型及参数设置

1.1 无线通信能耗模型

因为节点的能量消耗主要集中在数据的接收和发送上[12]，所以本文对节点的能耗分析主要考虑节点的无线通信能耗.节点发送l/bit数据到与其距离为d/m的节点，其消耗的能量ETX(l,d)为：

(1)

其中：Eelec是发送和接收数据时电路消耗的能量;εfs与εmp分别表示自由空间和多径衰落模型下的放大器系数;距离阈值[13]Dthreshold为

(2)

节点接收l/bit数据所消耗的能量ERX(l)为

ERX(l)=lEelec.

(3)

节点对m个数据包进行数据融合所消耗的能量Efuse为

Efuse(m)=m×lEDA,

(4)

其中，EDA是融合单位比特数据所消耗的能量.

1.2 仿真场景参数设置

本文在进行能耗分析和仿真实验过程中，仿真场景参数设置见表1.

表1 仿真场景参数设置

2 WSN能耗分析

2.1 簇头节点能耗分析

在无线传感器网络分层路由算法中，簇头节点主要负责接收该簇成员节点收集到的传感数据，并将融合后的数据转发到基站.所以，簇头节点的能耗主要包括接收数据的能耗、融合数据的能耗和向下一簇头发送数据的能耗.根据公式(1)、(3)、(4)，如果簇内成员节点的个数为n，簇头的发送距离为d，则该簇头节点在一轮中消耗的能量[14]ECH(n,d)为

ECH(n,d)=ETX+ERX+Efuse=(n+1)×lEelec+nlEDA+lεfsd2.

(5)

由式(5)可以得到，簇头能耗与簇内节点的数量n和簇头的发送距离d的关系分别为：

(6)

其中：1≤n≤100；0≤d≤Dthreshold.则ECH(n)和ECH(d)的取值范围分别为：

(7)

由式(7)可知，簇内节点的数量对簇头能耗的影响要远大于发送距离对其的影响.所以均衡簇内节点的数量对均衡簇头的能量消耗起着主导性的作用.

2.2 簇头位置对网络能耗的影响分析

假设一个簇中10个节点随机分布在10 m×10 m的监测区域内，如图1所示，计算这10个节点分别充当簇头时，簇头节点与其他节点之间的距离之和与网络能耗，如图2所示.

图1 节点分布位置图

图2 簇头位置和网络能耗关系对比图

从图2中可以看出，网络能耗与距离和(簇头节点与其他簇内节点之间的距离之和)成正比关系.其中，节点10与其他节点之间的距离和最小，当簇头位置在节点10上时，网络能耗也是最小的.所以，在簇头选举时，选择距离和越小的节点作为簇头越能降低网络的能耗.

3 基于均匀分区的WSN路由算法

3.1 均匀分区

根据2.1节中关于簇头节点能耗的分析可知，簇内节点的数量是影响簇头能耗的主要因素.由此，本文提出均匀分区的方法，通过均衡各分区内节点的数量，同时在各分区中选取能使网络能耗最小的节点充当簇头，从而均衡簇头负载能耗，有效减小网络能耗.

3.1.1 最优簇头数的确定

根据监测区域的大小和节点的数量计算出所需的簇头数，设有N个节点随机分布在M×N的区域中，得到最优簇头数[15]kopt为

(8)

其中，dtoBS是节点到基站之间的平均距离.

3.1.2 初始簇头的选择

假设在M×M的监测区域中，随机分布N个节点，需要从其中随机选取kopt个节点作为簇头，要求这kopt个节点两两之间距离大于间隔值Dmin.

本文采用改进的多叉树遍历算法来求解初始簇头的位置，该算法的具体求解思路是：先随机选择一个根节点，根据节点间的距离信息，将与该节点(父节点)距离大于约束距离Dmin的节点均设为该节点的子节点；再根据同样的距离约束条件，设定每个子节点(此时为父节点)的下一级子节点；以此类推，完成节点多叉树的构建，如图3(a)所示.接下来，要找到一条满足所有子节点与父节点的距离大于Dmin约束条件且层数为kopt的路径，判断该条路径中kopt个节点是否满足两两之间距离均大于Dmin的总条件，若满足，则记录节点信息，停止循环；否则，选择下一条路径并判断其中的节点是否满足以上条件.

如图3(b)所示，先随机选出一个节点a1，根据子节点与父节点之间的距离大于Dmin的约束条件，找到第一条路径a1→a2→a4，其中a1和a2、a2和a4满足距离大于Dmin的约束条件.下一步判断a1、a2、a4这三个节点是否满足两两之间距离均大于Dmin的总条件.从图3(a)中可看出，与a1节点距离大于间隔值Dmin的节点有a2、a3、a5，其中没有a4，所以，节点a1与a4之间的距离不符合条件.检查下一条路径a1→a2→a5，其中a1和a2、a2和a5满足距离大于Dmin的约束条件，同时a5又是a1节点的子节点，所以a1和a5之间的距离也符合距离大于Dmin的约束条件.所以，节点a1、a2与a5之间符合两两之间距离大于Dmin的约束条件，选为初始簇头，示于图3(b)中的阴影节点，记录节点信息，并停止循环.可见，改进后的多叉树遍历算法在被选取节点的随机性前提下，可以使选出的节点分布更加均匀.

图3 多叉树示例图

根据以上多叉树遍历算法求解初始簇头的位置.其中，根据监测区域的面积以及最优簇头数计算出的间隔值Dmin为

(9)

3.1.3 节点选择分区

计算节点与各初始簇头之间的距离权值，节点根据最小的距离权值选择加入的分区.本文定义的距离权值函数W(nodei,aj)为：

(10)

其中：dis(nodei,aj)是节点nodei与初始簇头之间的距离；ni是初始簇头aj所在区域当前拥有的节点个数；uj为该分区节点数量的上限，如式(11)所示.

(11)

其中，Nalive是当前轮网络中存活节点的个数.

由式(10)和式(11)可知，当各区域节点个数未达到上限值时，节点根据距离最近原则加入分区；当该区域节点个数达到上限值时，则不再接收新的节点加入,这样就可以有效地控制各区域节点的数量.

3.2 簇头竞选

根据均匀分区可得到kopt个节点数量均匀的区域，在每个区域中选择一个能耗权值最小的节点充当簇头节点.由2.2节知，簇头节点与其成员节点之间的距离和越小，网络的能量消耗就越小，同时考虑到簇头节点的剩余能量，可得到竞选簇头时节点的能耗权值WCH(nodei)为

(12)

3.3 节点通信

在WSN分层路由算法中，节点通信可分为簇内通信和簇间通信.节点将收集到的数据发送到簇头节点的过程被称为簇内通信；簇头节点将数据转发到基站则称为簇间通信.本文采用的节点通信方式具体如下：

1) 簇内通信距离通常小于距离阈值.为了避免传输信号出现冲突，簇内通信采取单跳的方式进行通信.

2) 如果簇头节点与基站之间的距离大于距离阈值，采用单跳的方式会急速消耗网络能量，此时簇间通信采用多跳的方式将数据转发到基站；如果簇头节点与基站之间的距离小于距离阈值，则簇间通信采取直接与基站进行通信的方式.

4 仿真验证

为了验证本文提出的路由算法的有效性，采用Matlab对其进行了仿真实验测试，并与LEACH算法、EECPK-means算法和能量质心算法进行了对比分析，具体的实验仿真参数见表1.

4.1 簇结构对比分析

根据式(13),在100 m×100 m的区域随机生成100个节点的位置，第i个节点的横、纵坐标分别为S(i)·x和S(i)·y，rand()用来生成[0,1]之间均匀分布的随机数.根据3.1节中的均匀分区方法对监测区域进行分区，再使用能量质心算法和EECPK-means算法对监测区域进行分区，得到三种算法各分区节点数量对比图，如图4所示.由图4可见，本文算法中各区域节点数最为均衡.

图4 3种算法各分区节点数量对比

(13)

此外，分别对EECPK-means算法、能量质心算法和本文算法进行5轮观测，并记录下各簇头(C1,C2,C3,C4)的标识号，见表2.从表2可以看出:能量质心算法和EECPK-means算法都有一个共同的缺点，即同一个节点会连续多次被选为簇头节点，导致节点能量快速消耗；而本文算法的各区随着每轮初始簇头的变化而发生位置上变化，从而影响簇头位置的变化，能够在一定程度上将簇头能耗分摊给不同节点.

表2 3种算法5轮观测中簇头的标识号

4.2 网络寿命对比分析

分别对LEACH算法、EECPK-means算法、能量质心算法和本文算法进行仿真，得到4种算法网络寿命与时间的关系，如图5所示.从图5中可以看出:本文提出的算法有效地延长了第一个能量耗尽节点的寿命，其主要原因是本文提出的分区方式具有较大的优势，能够有效地均衡各区节点的数量，并且在一定程度上分摊簇头的能耗；并且，当算法运行到第800轮时，本文算法网络中还有74个节点存活，能量质心算法有48个节点存活，EECPK-means算法有35个节点存活，LEACH算法仅有6个节点存活.可见，本文算法能够有效地提高网络的生存周期.

图5 4种算法网络生存周期对比

4.3 网络能量利用率对比分析

WSN是一种以采集传感数据为目的且能量受限的网络，所以除了网络寿命，网络的能量利用率也是WSN另一重要的性能指标.网络能量利用率越高，说明算法越节能.网络的初始能量为50 J，图6给出了4种算法网络能耗与基站接收数据包数量之间的关系.从图6中可以看出，在接收数据包的数量为2 000个时，本文算法消耗8.884 J能量，能量质心算法消耗了12.09 J能量，EECPK-means算法消耗了16.2 J能量，LEACH算法消耗了48.77 J能量.可知，在接收数据包的数量相同时，本文算法消耗的能量最小，能量利用率最高.其主要原因是，本文算法在簇头的选举时优先选择与分区内其他节点之间的距离和最小的节点，从而使网络能耗最小，并且从图5中可以看出，在同一时间，本文算法网络中存活节点的数量也最多.

图6 4种算法网络能量利用率对比

5 结论

本文从均衡簇头负载和优化网络能耗两个方面出发，针对分层路由算法中出现的节点过早死亡、簇头负载不均衡等问题，提出了基于均匀分区的无线传感器网络路由算法.首先采用改进的多叉树遍历算法随机选取分布均匀的初始簇头，从而使每轮产生不同的簇头，避免了节点连续多次被选为簇头的现象，在一定程度上分摊了簇头能耗；然后基于距离权值函数进行分区，均衡了簇头的负载；最后，通过分析簇头位置和网络能耗的关系得到最优簇头位置，优化了网络能耗.仿真结果表明：本文提出的算法能有效均衡簇头负载，避免节点过早死亡，延长网络的生存周期，同时提高网络的能量利用率.