煤矿物联网一般是指大量物联网节点以自组织方式形成的一种无线感知网络．在煤矿突发灾害事故后，部分节点发生故障，导致原有拓扑失效，无法正常通信，因此利用残存节点实现灾后物联网网络重构具有重要现实意义[1-2]．由于灾后残存节点能量有限且无法补充，因此如何有效降低残存节点的能耗成为煤矿物联网灾后重构的首要问题．分簇技术按照一定的规则将节点划分为不同的簇结构实现网络重构，不仅可以减少通信能耗，还能提高网络的可扩展性．目前，节能分簇算法以LEACH[3]算法为代表，其通过簇头轮换机制实现簇头节点的能量均衡，簇头以单跳通信的方式将数据传输到基站．然而该算法未考虑到远离基站的簇头具有更大的能耗．文献[4]提出一种非均匀分簇EEUC算法来解决此问题，其根据节点与基站的距离远近构造大小不等的簇，距离基站越近的簇头选择的成员节点越少．但是，该算法基于节点当前的剩余能量竞选簇头，只适用于能量异构程度较低的网络．文献[5]提出了一种适用于多能量级别的分簇DEEC路由算法，其基于节点当前剩余能量和网络平均能量的比值选举簇头，但是算法在选举簇头时没有考虑节点的位置分布和簇间路由问题．文献[6]针对煤矿灾后残存节点能量难以补充的情况，提出一种基于两阶段簇头选举的节能分簇SEC协议，降低了重构网络的整体能耗，但是该算法并没有考虑簇头远离基站时的簇间能耗问题．在现有关于煤矿物联网灾后重构网络分簇问题的研究[6-7]中，均考虑的是均匀分簇和单跳路由的网络结构．一方面，若所有簇头均采用单跳路由传输，则会造成远离基站的簇头因能耗增加过早死亡；另一方面，若对所有残存节点采用均匀分簇，则重构网络中选取的簇头可能会由于剩余能量较低及簇内成员节点过多导致簇间能耗分布不均，从而降低重构网络的生存时间．因此，为适应煤矿巷道特殊的空间结构，均衡重构网络的能耗分布，延长重构网络的生存时间，本研究提出了一种能耗均衡的自适应非均匀分簇(energy-balanced adaptive uneven clustering，EAUC)算法．1 系统模型与问题描述1.1　系统模型煤矿物联网灾后重构网络分簇结构如图1所示，假设在长宽分别为aW(a≥1)和W的矩形巷道中心存在一个能量无限的基站，在基站覆盖范围内随机分布N个残存节点Si(1≤i≤N)，H(i)表示Si当选为簇头节点，H(j)表示H(i)选择的下一跳簇间路由节点．假设事故后的残存节点均为静态．本研究采用与文献[2]相同的一阶无线电能耗模型．为了便于计算，在节点通信过程中仅考虑数据转发能耗，忽略其融合能耗．假设事故后残存节点Si的初始剩余能量为(1+αi)E0，其中：E0为残存节点Si的最小初始剩余能量，当E0=0 J时，表示该残存节点的剩余能量耗尽，节点死亡；αi为残存节点Si的当前剩余能量超出最小初始剩余能量E0时的能量倍数．这样，可将煤矿灾后残存节点Si的初始剩余能量表示为在[E0,(1+αmax)E0]内随机分布[10]，其中αmax=max{αi}．由此得煤矿灾后重构网络总的初始剩余能量为En=∑i=1N(1+αi)E0=(N+∑i=1Nαi)E0,式中En为灾后N个残存节点总的剩余能量．10.13245/j.hust.210421.F001图1煤矿物联网灾后重构网络分簇结构1.2　问题描述假设在图1所示当前的灾后重构网络中形成了K个簇，表示为C1,C2,⋯,CK，簇内数据传输采用单跳路由，簇间数据传输采用多跳路由．簇C2的簇头不仅须要对自身所在簇的数据进行收集和转发，还须要转发来自簇C1的数据．因此，在灾后数据传输过程中，C1的簇头要比C2的簇头消耗更多的能量，导致簇间能耗分布不均，C2的簇头因承担过多的能耗而过早能量耗尽死亡．此外，由于灾后残存节点的剩余能量有限且差异性较大，当对煤矿灾后物联网进行非均匀分簇重构和簇间多跳路由建立时，应首要考虑残存节点的剩余能量因素，以尽量延长煤矿物联网灾后重构网络的生存时间．2 算法描述本研究结合非均匀分簇和多跳路由的思想[8]，提出一种适用于煤矿物联网灾后重构的能耗均衡自适应非均匀分簇算法．2.1　候选簇头选举机制为了避免所有残存节点参与簇头竞选过程，减少残存节点的能量消耗，灾后网络中引入候选簇头选举机制，即每个残存节点Si在本地生成一个随机数Siμ∈[0,1]，若Siμ小于簇头选举阈值函数T(Si)，则该残存节点Si被列入候选簇头集合C中；否则，该残存节点Si被直接标记为成员节点，进入休眠状态．2.1.1　簇头选举阈值函数为了避免灾后剩余能量不足、地理位置不佳和邻节点密度稀疏的残存节点当选簇头，影响重构网络的性能，所提EAUC算法在文献[5]的基础上设计了残存节点的剩余能量、地理位置和邻居密度三个簇头选举影响因子．a. 剩余能量因子．将煤矿灾后残存节点Si的剩余能量因子e(i)表示为在运行轮数为r时残存节点Si当前剩余能量Ei(r)与灾后重构网络平均剩余能量E¯(r)的比值，即e(i)=Ei(r)/E¯(r)．通过定义剩余能量因子，可以充分考虑残存节点的剩余能量在灾后重构网络中的相对水平，确保剩余能量高的残存节点具有更大的概率当选簇头，从而延长簇头的生存时间．由于残存节点自身很难得知灾后网络中其余节点的具体能量信息，因此当求解E¯(r)时，为了避免残存节点因额外的控制消息开销而过早能量耗尽死亡，可对E¯(r)进行估算，估算的公式为E¯(r)=En(1-r/R)/N,式中R为灾后重构网络理想的生存时间，用重构网络运行总轮数表示．由于残存节点之间的剩余能量差异较大，因此为均衡灾后重构网络的通信能耗，所有残存节点应在相同时间内耗尽能量．为此，假设灾后重构网络中所有残存节点在每轮所消耗的能量之和Er均相同．此时，有R=En/Er．重构网络中每个簇的簇头节点和成员节点所消耗的能量分别可表示为ECH和ECM，有ECH=(N/K-1)lεele+lεele+lεmpdBS4;ECM=lεele+lεfsdCH2,式中：εele为发送电路或接收电路的能耗系数；εfs和εmp均为功率放大电路能耗系数；K为灾后分簇重构网络在当前运行轮次形成的分簇数，即当前重构网络中当选的簇头节点数目；dBS和dCH分别为簇头到基站的距离和成员节点到簇头的距离.由此可以得到Er=KECH+(N/K-1)ECM≈l(2Nεele+NεfsdCH2+KεmpdBS4).此外，为了使灾后重构网络每轮的能量消耗最低，令K为最优簇头数．最优簇头比例popt为预先设定的固定参数，此时有K=Npopt．b. 距离因子．在煤矿灾后残存节点剩余能量接近的情况下，距离基站更近的残存节点的通信能耗显然要低于距离基站远的残存节点，因此定义煤矿灾后残存节点Si的距离因子为d(i)=1-di/dmax,式中：di为残存节点Si与基站的距离；dmax为残存节点与基站的最大距离，满足dmax=max{di}．通过定义距离因子，可以充分考虑煤矿灾后残存节点的地理位置，避免距离基站较远的残存节点因当选簇头节点而增大其通信能耗，从而使选举出的簇头节点分布更加合理．c. 密度因子．考虑到巷道狭长的结构特点，在节点密集区域应增加残存节点当选簇头的概率，减小簇规模，从而降低簇内能耗；反之，在节点稀疏区域应降低残存节点成为簇头的概率，以均衡网络能耗．故将煤矿灾后残存节点Si的密度因子定义为n(i)=(|N(i)|-1)/|N(i)|,式中|N(i)|为残存节点Si当前的邻居节点数．通过定义密度因子，可以确保邻居节点密度大的残存节点更容易当选簇头，从而能更好地均衡重构网络中簇的大小和簇头的分布．综合考虑煤矿灾后残存节点的剩余能量因子、距离因子及密度因子，EAUC算法的簇头选举阈值函数为T(Si)=      pi[λ1e(i)+λ2d(i)+λ3n(i)]/{1-pi[rmod(1/pi)]}    (Si∈G);0    (Si∉G), (1)式中：pi为节点Si当选为簇头的概率；λ1，λ2和λ3为权重系数，满足0λ1,λ2,λ31且λ1+λ2+λ3=1；G为还未当选过簇头的残存节点集合．由式(1)可知：当灾后重构网络中残存节点Si的当前剩余能量越高、与基站的距离越近并且邻居节点数越多时，簇头选举阈值函数T(Si)越大．此时，残存节点Si在本地生成的随机数Siμ就越有可能小于簇头选举阈值函数T(Si)，则残存节点Si当选为簇头的概率也会变大．因此，通过定义式(1)可有效避免剩余能量不足和地理位置不佳的残存节点当选簇头节点．2.1.2　权重系数计算为了评估灾后残存节点在簇头选举时的综合性能，根据式(1)，本研究采用层次分析法[9]从剩余能量因子、距离因子和密度因子三个方面提出灾后重构网络簇头选举层次分析结构模型，确定各个指标的影响权重，以避免权重系数随机取值对灾后重构网络簇头选举的不确定性影响．通过对簇头选举中残存节点不同影响因素的分析，建立如图2所示的灾后重构网络簇头选举的层次分析模型．10.13245/j.hust.210421.F002图2簇头选举层次分析模型根据图2，按照相对重要性将残存节点的剩余能量因子、距离因子和密度因子相对于簇头选举的重要度进行两两比较．结合文献[9]中相对重要性判断的九级标度定义，本研究簇头选举中三个影响因素的成对比较矩阵M构造为M=1571/5121/71/21．(2)按照下述步骤计算矩阵M的一致性指标和检验系数：首先，对式(2)的每一个列向量进行归一化处理，并对每一行进行求和，得到矩阵M的特征向量L．给出归一化处理公式Luv=muv/∑u=1kmuv, (3)式中：Luv和muv分别为特征向量L和矩阵M中第u行、第v列元素值，u=v=3；k=3表示准则层中的三个因素．结合式(2)和(3)，矩阵M的特征向量L可表示为L=0.7450.7690.70.1490.1540.20.1060.0770.1=2.2140.5030.283．(4)对式(4)进行归一化处理可以得到关于剩余能量因子、距离因子和密度因子的权重向量λ，即λ=λ1λ2λ3=0.7380.1680.094, (5)式中λ1,λ2,λ3为权值向量λ的三个权值．根据矩阵M最大特征值ξmax的近似计算公式，并结合式(2)和(5)，有ξmax=1k∑u=1k(Mλ)uλu=132.2360.738+0.5040.168+0.2830.094≈3.014,式中λu为权值向量λ的第u个权值．则一致性指标βCI=(ξmax-k)/(k-1)=0.007．(17)最后，通过查表可知：当k=3时，平均随机一致性指标γRI为0.58．则一致性比例ρCR满足ρCR=βCI/γRI≈0.0120.1，因此M满足一致性要求．综合以上分析，灾后重构网络簇头选举阈值函数中的剩余能量因子、距离因子和密度因子权重系数的取值分别为0.738，0.168，0.094．2.2　候选簇头竞争半径一般而言，剩余能量较低和更靠近基站的候选簇头须承担更多的数据转发过程．为了均衡灾后重构网络中不同位置处残存节点的能量消耗，此类簇头应具有更小的竞争半径，以形成更小规模的簇结构，减少重构网络的簇内通信能耗．故煤矿灾后重构网络候选簇头的竞争半径可表示为Ri=1-θ1dmax-d1dmax-dmin1-θ2E¯i'Ei'R0, (6)式中：Ri为灾后网络候选簇头集合C中第i个候选簇头节点的竞争半径；d1为候选簇头H(i)到基站BS的距离；Ei'为候选簇头H(i)在第r轮时的剩余能量；E¯i'为候选簇头集合C在第r轮时的平均剩余能量；θ1和θ2为权重系数，满足0θ1,θ21，分别表示距离因素和能量因素对候选簇头竞争半径的影响程度；R0为候选簇头预先设定的最大竞争半径．由式(6)可知：当候选簇头的剩余能量相近时，候选簇头的竞争半径随残存节点与基站距离的增大而增大；当候选簇头与基站距离相近时，候选簇头节点的竞争半径随残存节点剩余能量的增大而增大．因此，通过定义式(6)可在一定程度上避免煤矿灾后能量异构的带状分簇多跳重构网络出现热区问题，有效均衡重构网络的整体能耗．2.3　簇间多跳路由当建立簇间多跳路由时，簇头首先以相同功率在全网范围内广播一条包含自身ID、剩余能量、成员节点数和到基站距离的ROUTER_MSG消息进行中继转发节点的发现．一般而言，簇头H(i)选择比自身到基站距离更近的簇头ck作为中继节点，故定义灾后重构网络中簇头H(i)的备选中继节点集合R(i)={ck|d22+d32d12,1≤k≤K}, (7)式中：ck为H(i)的备选中继簇头；d2为H(i)与ck的距离；d3为候选簇头ck到基站BS的距离．在式(7)中，若R(i)为空集，即H(i)没有中继节点，则H(i)与BS之间建立单跳路由；否则，H(i)将在集合R(i)中选择一个最优中继簇头与基站之间建立多跳路由．本研究通过定义ck的权值Wrel来进行路由发现，其中，Wrel值最大的ck将成为H(i)的最优中继节点，即图1中的H(j)．由文献[10-12]分析可知，簇间通信能耗主要与中继节点所在的地理位置有关．此外，由于ck还须转发自身簇内的数据信息，若参与过多的中继传输，则会显著增加ck的通信能耗，导致簇间能耗分布不均．为了均衡灾后重构网络的簇间通信能耗，H(i)在选择中继簇头时须综合考虑备选中继簇头的地理位置、剩余能量及成员节点数，有Wrel=ω1Eck(r)E¯R(i)(r)+ω2N¯R(i)Nck+ω3d12d22+d32，(8)式中：N¯R(i)为H(i)的备选中继簇头集合R(i)包含的平均成员节点数；Nck为备选中继簇头ck的成员节点数；ω1，ω2和ω3为权重系数，满足ω1+ω2+ω3=1．由式(8)可知：若备选中继簇头的当前剩余能量越高、包含的成员节点数越少且簇间通信能耗越低，则该备选中继簇头的权值越大，即具有较大概率成为H(i)的中继节点．因此，通过定义备选中继簇头的权值，可以降低灾后重构网络中性能不佳的簇头当选为中继节点的概率，从而均衡灾后重构网络的簇间能耗．2.4　算法运行流程所提EAUC路由算法的消息开销主要由N个残存节点在簇头选举和簇间路由过程产生，重构网络消息总开销可计算为O(N)，即表明所提EACU算法并未使重构网络产生额外的能耗．EAUC算法主要运行步骤描述如下．a. 残存节点Si根据网络初始参数配置信息计算自身剩余能量因子、距离因子和密度因子；同时残存节点Si在本地生成一个随机数Siμ∈[0,1]，若SiμT(Si)，则残存节点Si当选为候选簇头节点；反之，则被系统直接标记为成员节点．b. 所有残存节点完成候选簇头选举后，候选簇头节点根据式(6)计算自身非均匀分簇竞争半径大小，并在此范围内与邻居候选簇头竞选正式簇头．c. 正式簇头节点以自身竞争半径在灾后重构网络内广播包含自身ID和剩余能量信息的CH_ADV_MSG消息宣布自身的存在，成员节点选择距离最近的一个簇头加入，并向其发送包含自身ID的JOIN_MSG消息，簇头向成员节点返回ACK消息后，形成非均匀分簇结构，簇头节点向簇内成员节点分配TDMA时隙进行簇内数据传输．d. 在簇间多跳路由阶段，簇头首先根据式(7)判断重构网络中是否存在下一跳中继簇头，然后根据式(8)计算备选中继簇头的权值大小，并选择权值最大的簇头作为下一跳中继转发节点．簇间形成了以基站为根节点的路由树．3 仿真结果与性能分析3.1　仿真场景与参数设置在Matlab中对所提EAUC算法网络性能进行了测试；同时，将其与LEACH[2]，DEEC[5]和SEC[6]三种算法进行了对比．假设在200 m×5 m的带状巷道内随机散布了200个残存节点，基站位于中心位置．为了测试残存节点多级能量异构性对灾后重构网络性能的影响，对不同能量倍数1≤αmax≤6下的灾后重构网络生存时间和数据包传输量分别进行了20次独立仿真实验，实验结果取平均值．部分仿真参数参考了文献[2]，中继簇头的权重系数ω1，ω2和ω3分别设置为0.3，0.3和0.4，仿真中使用的其他参数设置为：E0=0.5 J，l=4 000 bit，dth=87.7 m，popt=0.05，R0=30 m，εfs=10 nJ/(bit·m2)，εmp=1.3 fJ/(bit·m4)，Eelec=50 nJ/bit．3.2　参数选取通过在[0,0.5]之间选取几组不同的参数组合，以灾后重构网络残存节点存活数来判断θ1和θ2最优取值．图3为候选簇头竞争半径的权重系数θ1和θ2的不同取值对煤矿灾后重构网络存活节点数的影响曲线，图中s为残存节点个数．由图3可知：在煤矿物联网灾后重构网络相同运行时间下，(θ1,θ2)=(0.5,0)和(θ1,θ2)=(0,0.5)所对应的存活节点数目相对其他取值来说较少，(θ1,θ2)=(0.3,0.2)所对应的存活节点数目最多，这表明该组权重系数合理量化了残存节点与基站的距离及当前剩余能量对候选簇头竞争半径的影响程度．因此，在接下来的所有仿真实验中，θ1和θ2的取值均设置为0.3和0.2．10.13245/j.hust.210421.F003图3θ1和θ2的不同取值对存活节点数的影响曲线 1—(θ1,θ2)=(0,0.5)；2－(θ1,θ2)=(0.5,0)；3－(θ1,θ2)=(0.2,0.3)；4－(θ1,θ2)=(0.3,0.2)． 3.3　簇头节点能量消耗灾后重构网络簇头节点平均能耗随运行时间的变化曲线如图4所示，图中E为以每轮运行后重构网络中所有簇头节点的平均能耗大小．从图中可以看出采用EAUC算法的簇头平均能耗明显低于LEACH，DEEC和SEC这三种算法，相同运行时间下最低可分别达到88.8%，81.1%和52.8%．这是由于EAUC算法在重构网络簇头选举中综合考虑了残存节点的剩余能量、邻节点数及与基站的距离多个因素，使选举的簇头节点性能最佳．此外，采用层次分析法客观确定指标权重，避免了随机选取导致能耗过大的现象，采用非均匀分簇结构缓解了远离基站处簇头节点能耗较大的问题，更进一步降低了簇头节点的能耗．10.13245/j.hust.210421.F004图4灾后重构网络簇头节点平均能耗1－LEACH；2－DEEC；3－SEC；4－EAUC(下同)．3.4　灾后重构网络数据传输量灾后重构网络数据传输量是指煤矿灾后重构网络中基站接收到残存节点发送的有效数据包的总和．图5给出在四种分簇算法下，基站接收数据量随着轮数时间变化的对比，图中p为基站接收的数据包总量．可以看出：随着灾后重构网络运行时间的增大，四种算法下基站接收的总数据量都在逐渐增加．当网络运行至600轮以上时，明显看出LEACH和DEEC算法的数据传输量固定且基本无提升．在相同运行时间下，与SEC算法相比，EAUC算法数据传输量增加得更多，这是由于采用了簇间多跳路由策略，综合考虑了中继簇头节点当前的剩余能量、地理位置及包含的成员节点数，所选取的中继节点具有更优传输性能，使得灾后重构网络中基站接收到的灾后数据量最多．10.13245/j.hust.210421.F005图5灾后重构网络数据传输量3.5　灾后重构网络生存时间本研究将煤矿灾后重构网络生存时间定义为从灾后重构网络开始运行到第一个残存节点能量耗尽死亡所经历的时间范围，这段时间也表示煤矿灾后重构网络的稳定周期，用运行轮数表示．四种算法在网络生存时间方面的对比如图6所示，可知：四种算法下出现首个死亡节点的时间分别为338轮、508轮、605轮和707轮，因此采用EAUC算法的灾后重构网络稳定周期最长．相较于采用LEACH，DEEC和SEC算法，EAUC算法下重构网络残存节点全部死亡时间分别提高了31.5%，18.8%和10.3%．这是由于EAUC算法在灾后重构网络簇头节点选举过程避免了剩余能量不足和地理位置不佳的残存节点当选簇头节点，因而大大降低了灾后重构网络的能量消耗，延长了灾后重构网络的生存时间．同时，在簇间路由阶段，当前簇头在下一跳备选簇头集合中选取性能最佳的中继簇头用以数据传输，均衡了重构网络簇间能量消耗，从而进一步延长了重构网络的生存时间．10.13245/j.hust.210421.F006图6灾后重构网络残存节点数随运行轮数的变化4 结论煤矿物联网灾后重构网络中残存节点初始能量较低且差异性较大，为降低灾后重构网络的能耗和延长重构网络的生存时间，提出了一种能耗均衡的自适应非均匀分簇EAUC算法．EAUC算法根据簇头选举阈值函数进行候选簇节点选举，避免剩余能量不足和地理位置不佳的残存节点因参与簇头节点竞选而过早能量耗尽死亡；簇头节点形成不同大小的竞争半径以形成非均匀簇结构，从而均衡重构网络的能耗分布．在簇间路由阶段，通过定义中继簇头权值函数在备选中继簇头中选取性能最优的残存节点用以数据传输，旨在降低簇内通信能耗的同时均衡灾后重构网络的整体能耗．仿真结果表明EAUC算法在均衡簇头节点能耗、提升重构网络的数据传输量及生存时间等方面均具有良好的表现．