煤矿井下无线传感网络路由协议研究

郑欢欢，白鱼秀

（榆林学院信息工程学院，陕西榆林，719000）

0 引言

近年来矿井安全事故频发，因此建立较为完善的煤矿井下安全监测系统尤为重要。由于井下环境复杂、恶劣，如果采用有线设备建设安全监测系统，不仅费时费力、成本较高，而且一旦有线设备受损也容易造成系统的功能受限[1]。

无线传感器网络由于强大的移动性和自组织性更适合应用于煤矿井下的特殊环境。将无线传感器网络应用于煤矿井下环境还有两个问题要解决：传感器节点受限于能量有限，无线传感器网络中节点能耗不均会导致节点过快死亡，影响网络的生存时间和整体性能；煤矿井下长距离带状环境，容易造成“热区”问题，导致节点能耗不均[2]。因此需要为WSN建立合理的网络拓扑结构，以降低网络的整体能耗、延长网络的生存周期、提高网络性能和扩展性等。

本文采用k-medoids聚类算法对无线传感器网络的拓扑结构进行簇类划分，并在初始化簇头节点时舍弃传统算法中的随机选择，采用领域自适应半径的方法进行簇头节点选择，综合考虑了簇头节点的剩余能量因子和用邻居节点数计算出的近似密度因子；替换新簇头节点时考虑节点剩余能量，较好的均衡了无线传感器网络节点的能量，延长了网络的生存周期。

1 传统k-medoids算法

k-medoids算法是一种优化的划分式聚类方法，对包含异常点的数据集能够实现较好的聚类划分，具有较好的健壮性和鲁棒性[3]。

k-medoids算法常用的划分方法是选取实际节点作为簇头节点，普通节点根据与簇头节点的相似性度量加入相应的簇中。其算法的核心思想是：从n个节点中随机选择k个节点作为簇头节点，其余节点按照就近原则分配到k个簇中；通过反复迭代使用非簇头节点代替簇头节点，从而得到最佳分簇效果。

虽然k-medoids算法比起其他聚类算法能够得到较均匀的分簇结构，有效改善孤立点的簇类划分，一定程度上改善了节点之间的能耗问题。但也存在不少缺点：（1）在初始化簇头节点时采用随机选择的方法，导致不同环境中分簇效果不稳定；（2）更新簇头节点为参考当前能量值等其他标准，导致迭代计算工作量较大。因此本文分析研究传统k-medoids算法的基础上，提出了基于能耗均衡的k-medoids算法。

2 基于能耗均衡的k-medoids算法

■2.1 网络模型

假设本文采用的网络模型如下：

（1）在一个大小为L×W的实验区域内有n个传感器节点和1个汇聚节点，其中汇聚节点位于网络的一端。

（2）网络中的汇聚节点能量不受限制，其余传感器节点有唯一的标识ID，具有相同的功能属性。

（3）节点可以根据接收信号强度计算节点间距离，并根据环境调节自身发射功率。

■2.2 能耗模型

传感器节点绝大部分能量都消耗在节点间的数据接收和转发，所以能量的消耗模型采用传统的无线通信模型，网络节点发送l bit数据传输d m距离消耗的能量Etx为：

网络节点接收l bit数据传输d m距离消耗的能量Erx为：

上式中，Eelec、εfs和εamp都是常数，分别表示信号处理时的能量消耗、自由空间模型下放大器功耗和多径衰减模型下放大器功耗。

■2.3 算法描述

本算法主要分为3个步骤，首先是在无线传感器网络内选择初始化簇头节点；然后剩余节点根据就近原则选择加入相似度最高的簇中；为了最大程度的优化分簇结果，因此要按照替换准则选择其余节点优化分簇结果，如果分簇结果改变就需要重新回到第二步继续迭代优化，直到分簇结果不发生改变，则说明分簇结果已达到最优。以下详细描述初始化簇头节点和更新簇头节点算法详情。

（1）初始化簇头节点

由于传统k-medoids算法随机选取k个节点作为簇头节点，再通过不断地迭代优化聚类，不仅浪费大量迭代时间，而且由于簇头节点选择的随机性，容易是聚类陷入局部最优。因此本算法采用领域自适应半径的方法[4]选取初始簇头节点，综合考虑了簇头节点的剩余能量因子和用邻居节点数计算出的近似密度因子，可以缩短选择初始化簇头节点的时间[5]。

首先根据能量消耗模型计算网络传输一次数据的能耗得出最优簇头节点数目[6]为：

根据煤矿井下巷道的长距离带状环境，设置传感器的领域半径Rch计算方法见式（4）。

为了更好地均衡能耗，本文采用领域自适应半径，因此在计算中综合考虑了传感器节点的剩余能量和邻居节点数。故根据下式计算得出：

其中，Ec是传感器节点的当前剩余能量，Eavg表示当前网络的平均能量。Nbrn是本节点在网络中相邻节点的数目。α和β为控制权重参数，且相加之和为1。

最后，设置假设所有节点的中心位置为O，将以O为中心，以Rc为半径确定中心圆。k-medoids选取的初始化簇头节点是实际节点，因此在中心园上均匀的选择k个节点作为初始簇头节点。

通过式（5）计算得到的自适应半径，用节点的剩余能量和初始能量比例作为能量因子可以计算出节点消耗能量的速率，而通过本节点的邻居节点和所有节点的比例可以近似得到本节点周围的节点密度因子，因此可知如果节点耗能越少、节点密度越稀疏会得到较大的领域半径。这样在自适应半径圆上选取的初始化簇头节点大大降低了算法的迭代时间，更加高效。

（2）更新簇头节点

分簇完成后，需要通过迭代优化分簇，更新簇头节点实现普通节点和簇头节点之间的距离最小化。更新簇头节点的替换准则应满足[7]下式：

其中x是簇Ci中的普通节点，mi表示Ci中的簇头节点。

假设S={S1, S2,…,Sj,…Sk-1,Sk},S表示无线传感器网络中所有簇头节点的集合。从网络中随机选择一个普通节点Sr作为备用簇头节点准备替换原簇头节点Sj,。根据式（6）给出的替换准则计算备用簇头节点的替换准则，如果该值小于原簇头节点的替换准则值且备用簇头节点的剩余能量大于此时网络中所有节点的平均剩余能量值时，那么就用该备用簇头节点替换原簇头节点，即簇头节点集合变为S={S1, S2,…,Sr,…Sk-1,Sk}。

替换流程如下：

a.随机选择一个普通节点作为备用簇头节点准备替换原簇头节点。

b.计算该备用簇头节点的替换准则，如果该节点的替换准则小于原簇头节点的替换准则，且备用簇头节点剩余能量小于网络中所有节点的平均剩余能量，那么就用备用簇头节点替换原簇头节点，否则就释放掉备用簇头节点。

c.如果原簇头节点都没有替换，则表示已得到最优化分簇；否则根据替换的新簇头节点重新划分簇，返回a迭代寻找最佳划分簇。

3 实验仿真及分析

■3.1 实验环境

根据理论分析，通过matlab搭建实验仿真环境，对本文协议进行仿真，并参照LEACH、EEUC协议进行对比。实验参数设置如表1所示。

表1 实验参数

■3.2 实验结果对比

图1表示三种算法在节点死亡数目的对比，LEACH在500轮后开始出现死亡节点，EEUC和本文算法在1100轮后开始出现死亡节点，而之后EEUC死亡节点数目剧增，本文算法死亡节点数目变化缓慢，直到2000轮左右，本文算法的死亡节点数目都是最少。说明改进的协议能够有效的均衡网络节点的能量消耗，最大程度保障网络性能，延长网络生命周期。

图1 节点死亡数目对比

图2从节点平均剩余能量方面做对比，节点平均剩余能量是循环工作一定轮次后取节点的剩余能量平均值，可以看出本文改进协议的节点平均剩余能量高于其他对比协议，说明该协议能较好的均衡节点能耗。

图2 节点平均剩余能量对比

4 结束语

本文提出了基于k-medoids算法应用于矿井巷道环境下的能够均衡网络能耗的路由协议。改进协议在初始化簇头节点时采用领域自适应半径的方法，综合考虑了簇头节点的剩余能量因子和用邻居节点数计算出的近似密度因子，可以缩短选择初始化簇头节点的时间；更新簇头节点时把剩余能量也作为更新条件，从而达到均衡网络节点能耗的目的。实验仿真结果表明，改进协议在应用于长距离带状环境下，在节点死亡个数和平均剩余能量方面的性能优于LEACH和EEUC协议，有效均衡了网络能量消耗，延长了网络生命周期。