徐小玲 刘美

（广东石油化工学院计算机与电子信息学院）

矿井下无线传感器网络分簇算法研究

徐小玲 刘美

（广东石油化工学院计算机与电子信息学院）

矿井下采用分簇解决信息冲突问题，为了同时满足人员节点定位精度和能耗要求，提出了一种基于人员节点与簇首的位置误差和通信能量消耗综合考虑的粒子群分簇算法。仿真结果表明：在能耗上，基于通信能耗和位置误差考虑的分簇算法比基于能耗考虑的分簇算法提高了2.22%，但位置误差却降低了8.11%。算法在实现分簇、增加系统可靠性的同时，最大限度地降低了对资源的使用，满足了定位精度的要求。在人员密集的煤矿井下，该算法可将位置误差进一步降低。

分簇；位置误差；能耗；粒子群

1引言

利用无线传感器网络组建的井下安全监测系统通过使用功能不同的节点，随时掌握井下人员的动态分布。系统中，人员节点借助信标节点将井下人员的位置信息传送到控制台从而了解矿井下的情况。由于在煤矿主巷道、人车、采掘工作面等区域人员较为密集，当多个人员节点同时与信标节点通信会造成信号冲突，甚至导致网络处于瘫痪，通信无法进行。为了避免通信冲突，可采用不让每个人员节点都向信标节点发送信息，而只从中选出一个代表向信标节点发送信息，即采用成簇来解决这一问题。

2 相关工作

近年来，研究人员提出了多种传感器网络的分簇算法，其中W. Heinzelma等人提出的低功耗自适应分簇算法LEACH[1]。LEACH有效的节省了能量消耗，但它没有考虑到节点分布的拓扑结构和节点的能量问题，这种情况下簇内的能量消耗并不是最优值。文献[2]应用粒子群算法解决网络分簇问题，提出均匀分簇的思想以最小化节点能耗。但对于节点分布不均匀的网络，这种分簇方法可能造成各簇数量规模相等。而几何规模差异较大的情况，会造成簇间消耗能量不均。文献[3]提出一种具有能量感知能力的分簇策略，采用PSO算法优化选择分簇方式，既最小化簇内距离，又最优化网络能耗，有效延长网络生存周期。但它没有考虑簇头节点传输信息至基站时的能耗不均，易导致距离基站较远的节点成块死亡，网络能量消耗不均衡。如Thanongsak H.提出通过中继传输来延长网络的生存期，也有少量的文献研究分簇路由中的簇内通信方式，如孙勇等[4]提出了时分混合通信方案，张志东等[5]提出楔形多跳方案减小网络能耗。

本文根据井下分簇的要求，把节点与簇首的位置误差和通信能耗作为优化目标函数的主要指标建立传感器节点成簇的数学模型，通过采用最近邻进行初始成簇并采用粒子群优化算法实现节点重新组簇，尽可能快地得到最优成簇结果。

3 节点成簇目标函数设计

3.1 节点成簇能耗考虑

节点的能量消耗一般由感应、数据处理、节点间的通信三方面构成。而占能量消耗主体的就是节点之间的通信能耗，因此在算法评估时只考虑通信能耗，忽略其他能耗；本文运用无线电通信模型，通信能耗表示为式(1)：

节点接收lbit长度数据所消耗能量为：

其中Eelec表示发射电路损耗的能量。若传输距离小于阈值r，则功率放大损耗采用自由空间模型；若传输距离大于等于阈值r，采用多路径衰减模型。εmp、εfs分别为两种模型中功率放大所需的能量。由此可见总能量E主要取决于d，通信能量消耗最小化可以等效为d之和最小化。

而距离的测量，由于受传播环境的影响，电磁波在井下的传播不能用自由空间传播模型来描述，从文献[6]可知，一种对数正态分布模型可对电磁波井下传播与式(3)近似。

式中，RSSI(d)表示节点接收的信号强度，单位为dBm；PT为传送信号的强度，PT取－45dBm；d0是相对于人员节点的参考距离，d0取1m；Pr(d0)是该参考点处的信号功率。α则通常是由场地测量得来的经验值。而XdB服从均值为0，方差为σdB的正态分布，但是在确定环境中的传播路径，则与确定的XdB相对应。在实验环境中，用两块CC2430模块多次测量不同距离下RSSI值，通过估计得到相应的α与XdB。

表1 RSSI与距离的关系

实验中设定d0为1m，测得Pr(d0)=－56dBm。根据多元回归分析可得α=2.8305，XdB=40.9388。再通过式(3)可实现RSSI到d的转换。

在矿井人员跟踪过程中，在初始时刻，为保证所有人员节点不丢失，根据实际要求，将接收到相同信标且信号强度最强的节点组成一簇，此时该信标节点相当于一个临时簇首，保证所有人员节点都可以与信标节点进行通信；当然，还要在人员节点中选择一个真正簇首节点。当每个簇选出一个真正簇首时，可以用式(4)描述成簇关系矩阵：

在矩阵A中，行数表示人员节点个数；列数表示簇首节点个数。amn为0-1变量，amn=1表示第n（n= 1，2，…，N）个节点加入第m个簇中，即加入簇首节点m（m=1，2，…，M）所在的簇里，否则amn=0。这里能耗数学模型可以描述为式(5)：

其中，要求一个人员节点只能参加一个簇。即

式中，dmn表示第m个簇首节点与第n个人员节点之间的距离，为使得能耗指标最小化，保证簇内所有人员节点至所选簇首节点之间距离之和最小。

3.2 节点位置误差考虑

对于k个固定信标节点B1(x1,y1)，B2(x2,y2)，…，Bk(xk,yk)，人员节点M (x,y)至信标节点的距离分别为d1，d2，…，dk。这里若只考虑两个信标节点B1，B2，假设两节点的质心在B12，位置为(x12,y12)，B12到B1和B2的距离分别为d1，d2。显然可知存在(x12-x1)/d1= (x12-x2)/d2和(y12-y1)/d1=(y12-y2)/d2。得x12=(x1/d1+x2/d2) /(1/d1+ 1/ d2)，y12=(y1/d1+ y2/d2)/(1/d1+ 1/d2)。其中，1/di为权值，体现出距离人员节点距离近的信标节点的权重大，其误差比较小；而距离人员节点距离远的信标节点的权重小，其误差比较大，选择加权因子能体现各个信标节点对于人员节点位置的决定权的大小，其约束力符合加权质心算法的要求。若把人员节点接收到RSSI值的范围在－56dBm～－98dBm之间的信标节点加入考虑，则得：

在井下信息化管理系统中，为了实时监控井下人员，在大多数情况下，只要求人员节点每隔一个不长时间就与信标节点传递一次确认信息。保证人员节点在一段时间内不丢失，而不需要知道确切位置，簇首在信标节点传输信息时，把簇首节点的位置信息作为全簇节点的位置信息。也就是说，簇首只向信标节点发送簇首的位置信息及全簇成员的ID号即可。但在一些需要知道某个簇成员相对确切位置时，节点相对于簇首的选择就非常重要。

对于簇首的选择，在得到节点位置后，根据文献[7]对通信模型(1)、(2)的研究，单个簇与信标节点通信总能量消耗最小的满足条件，即信标节点、簇首、簇的质心在同一直线上。假设信标节点位置为(0，0)，理想簇首位置为(xCH，yCH)，簇内节点的位置为(xi，yi)，簇内节点总数为n(包括簇首)，则有下列等式：

其中，ρ满足下面关系

由式(8)、式(9)可以计算出理想簇首节点的位置(xCH，yCH)，那么，距离该点最近的节点应该被选为簇首(xchm，ychm)(m=1,2, …,M)，m为第m个簇。

则人员节点位置误差可以表示为：

ermn表示第n个人员节点与第m个簇首之间的位置误差。由于一个人员节点只能参加一个簇。因此，基于人员节点位置误差的数学模型设计为：

在完成簇首选择后，根据粒子群算法综合考虑通信能耗和节点位置误差重新成簇。成簇目标函数可以设计为式(11)，以保证节点通信能耗与位置误差最小。

4 基于粒子群的分簇算法

粒子群优化是通过个体之间的协作寻找最优解的计算技术。算法数学描述为：假设在一个D维的目标空间中，有N个代表潜在问题解的粒子组成一个群，其中第i个粒子表示为一个D维的向量，Xi= [xi1，xi2，…，xiD]，i=1，2，…，N；第i个粒子在D维搜索空间中的位置是Xi，飞行速度是Vi=[vi1，vi2，…，viD]；记Pi为第i个粒子迄今为止搜索到的个体最优位置，Pi=[pi1，pi2，…，piD]；记Pg为粒子群迄今为止搜索到的全局最优值，Pg=[pg1，pg2，…，pgD]；每次迭代中粒子按照式(12)、(13)更新速度与位置，则：

式中，i=1，2，…N；t为迭代次数；w为加权因子，取值在0.1～0.9之间，c1，c2为学习因子，分别调节向个体最好粒子和全局最好粒子方向飞行的最大步长；r1，r2是[0，1]之间的随机数。粒子通过不断学习更新，最后找的Pg就是全局最优解。

然而无线传感器网络成簇问题是一个离散型问题，基本的PSO算法是针对连续问题设计的，要解决成簇问题，需要设计一个求解离散问题的PSO算法。具体算法设计如下。

4.1 粒子群初始化

4.1.1 位置的定义

粒子的位置X代表分簇方案，可以表示为X= (X1,X2,…,Xj,…,XM)，1≤j≤M；Xj=(xj1，xj2，…，xji，…，xjN)，1≤i≤N。在对粒子的位置进行更新时，粒子的位置X为一个用元素为0或1的位置矩阵。

其中，M表示簇首个数；N表示人员节点个数；xji=1表示第i个人员节点加入第j个簇中；xji=0表示第i个人员节点个数不加入第j个簇中。

4.1.2 速度的定义

离散空间的速度不再是连续空间所说的速度，而是用来计算粒子的位置变化的概率值，粒子的速度用一个矩阵来表示：

式中，vji∈[-vmax，vmax]，j∈{1，2，…，m}，i∈{1，2，…，n}。由于速度是一个表示粒子的位置变化的概率值，它被限制在[0，1]之间。

4.2确定适应值函数、个体极值和全局极值

在粒子群算法中，适应值函数作为评价标准必须要能够反映所要求解问题的目标要求以及约束限制。这里将适应值函数取为目标函数。同时，根据无线传感器网络分簇的具体问题，进行条件限制。其次，计算粒子所经历的最好位置pbi(t)，也就是粒子所经历过的具有最好适应度的位置，由式(14)确定：

并计算群体中所有粒子经历过最好位置，即全局最好位置，由式(15)确定：

最后，依据粒子群公式对粒子的速度和位置进行进化。算法流程如图1所示：

图1 基于粒子群的分簇算法流程图

4.3 算法仿真

仿真过程中，在120m×120m监测区域内，实验中将120个传感器随机分布于监测区域内模拟120个井下人员，另外在监测区域上下两侧各安放4个信标节点。设节点的探测半径R=60m。实验中采用一组参数如下：εmp=0.0013pJ、εfs=10 pJ，根据计算可得簇首节点位置。采样间隔为1秒；粒子群参数w=1，c1=c2=2，循环次数n=100；仿真结果如下图所示：图中各种相同形状节点表示簇节点，簇首节点用五角星型表示，图2为根据与信标节点的位置，采用最近邻的初始化分簇，从而形成8个簇。图3为基于能耗和位置误差考虑重新成簇的结果。

图2 采用最近邻的初始化分簇

图3 基于能耗和位置 误差考虑成簇

表2 不同分簇算法能量消耗与位置误差结果比较

根据表2可知，在不同分簇算法的能量消耗中，采用最近邻方式进行初始化分簇时总能量消耗用距离表示为2082m，而基于能耗和位置误差考虑的分簇的总能量消耗用距离表示为2128.2m；此能耗与采用最近邻的初始化分簇相比，提高了2.22%。而各个簇的位置误差如表2所示，其中，采用最近邻方式进行初始化分簇，此时总位置误差为495.5887m，而基于能耗和位置误差考虑的成簇的总位置误差为458.3910m；在位置误差上与采用最近邻的初始化分簇相比，提高了8.11%。在煤矿井下非常密集的区域，尤其在上下班的高峰时段，基于能耗和位置误差考虑的分簇算法，在定位精度上更占优势，更有利于煤矿井下人员跟踪定位的要求。

5 结论

本文在无线传感器网络节点能量、存储、带宽资源受限的条件下，重点从通信能耗和位置误差的角度，通过建立无线传感器网络分簇的综合性能指标，利用离散粒子群优化算法，在实现有效的分簇同时，保证定位精度，达到煤矿井下通过传感器节点之间的高效协同实现人员跟踪的目的。

[1] Heinzelman W, Chandrakasan A, Balakrishnan H. An application-specific protocol architecture for wireless microsensor networks[J]. IEEE Transactions on Wireless Communications， 2002，1(4) :660-670.

[2] Tillett J, Rao R,Sahin F. Cluster-head Identification in Ad hoc Sensor Networks Using Particle Swarm Optimization[C]//Proc. Of IEEE International Conf. on Personal Wireless Communications. New Delhi， India: [s. n.]，2002.

[3] Latiff N M A, Tsimenidis C C, Sharif B S. Energy- aware Clustering for Wireless Sensor Networks Using Particle Swarm Optimization [C]//Proc. of the 18th International Symposium on Personal, Indoor and Mobile Radio Communications. Athens,Greece: [s. n.],2007.

[4] 孙勇,景博.分簇路由的无线传感器网络通信模式与能量有效性研究[J].电子与信息学报,2007,29(9): 2262-2264.

[5] 张志东,孙雨耕.无线传感器网络能量模型[J].天津大学学报(自然科学版),2007,40(9):1029- 1034.

[6] Chahe Nerguizian, Charles L.Despins. “Radio- Channel Characterization of an Underground Mine at 2.4GHz”.IEEE Transactionsons on wireless communications,Vol4,No.5，SEPTEMBER 2005：2441-2453.

[7] Gurpreet Singh,GaoXi Xiao. Algorithms for energy-efficient clustering in wireless sensor networks[A]. Communication systems,2006 10th IEEE Singapore International Conference[C], Oct. 2006. 1-5.

徐小玲，女，1981年生，助教，硕士，主要从事无线传感器网络的研究。

刘美，女，1967年生，副教授，主要从事无线传感器网络的研究。

Study on Wireless Sensor Networks Clustering Algorithm for Coal Mine

Xu Xiaoling Liu Mei
(Computer and Electronic Information College, Guangdong University of Petrochemical Technology)

Adopting clustering to solve information conflict and meeting personnel node location accuracy and energy requirement in coal mine, this paper puts forward a kind of clustering method based on the comprehensive consideration of position error between nodes and cluster head and communication energy consumption using particle swarm optimization. Simulation results show that energy consumption of the clustering algorithm mentioned in this paper is increased by 2.22%, location error is reduced by 8.11% comparing with clustering algorithm. The algorithm achieves clustering, increases the system reliability and reduces the use of resources, meets the location accuracy requirement. In a crowded colliery, position error will be further improved.

Clustering; Position Error; Energy Consumption; Particle Swarm Optimization (PSO)