随着集成电路、微电子技术、无线通信、嵌入式和传感器技术的高速发展，传感器网络已经由20世纪70年代的第一代发展到了第四代，即无线传感器网络（WSN）^[1]。尤其是进入21世纪后，无线传感器网络技术作为物联网的组成要素，已经被广泛应用于军事、环境监测、自然灾害预报、医疗健康、智能家居等众多领域^[2]。无线传感器网络的部署可以通过飞行器散播、人工规划埋置等方式完成，部署完成后，各节点以自组织的形式构成网络。无线传感器网络系统通常由传感器节点（sensor node）、基站（base station, BS）和管理节点组成，其中，传感器节点由能量有限的不可充电电池提高电力^[3]。无线传感器网络高度依赖于具体应用场景，受能源、存储容量和功率的限制，所以对于每个路由协议，减少能耗是延长网络寿命的重要考虑因素^[4]。

自Heinzelman等^[5]第一次提出了分层聚类的低功耗自适应集簇分层型协议(low energy adaptive clustering hierarchy，LEACH)协议后，由于其在延长无线传感器网络寿命方面具有优良的性能，此后，聚类协议开始受到研究学者的广泛关注。LEACH通过簇头轮换机制较好地平衡各节点的能耗，其在同构WSN中表现良好，但是在异构环境中的性能有所下降。文献[2]针对此问题进行优化，提出了在异构环境中适应性更强的DEEC协议。

在分层聚类协议中，WSN运作以轮为单位。由于LEACH类协议在每轮的簇头选举中通过预先计算一个阈值 $T\left( i \right)$ ，然后产生一个0~1之间的随机数，如果该数小于此阈值 $T\left( i \right)$ ，则此节点成为簇头^[6]。这种随机选举簇头的策略存在不确定性，并没有兼顾到不同节点个体特性，并且每轮选举出的簇头数量也存在较大差异，并不能保证产生稳定的最佳数量簇头，甚至在WSN后期会经常出现没有簇头的情况。如果在某轮中没有簇头产生，那么次轮就没有数据传输到汇聚节点。随着无线传感器网络的运行，宏观上将整个网络运作分成3个阶段：稳定周期（stable period，SP）^[7]，半数死亡节点期（half surviving nodes，HSN）^[8]和弱感知周期（weak perception cycle，WPC）。稳定期是未发生节点死亡，所有节点均平稳运行的轮次，在稳定期间网络具有最强的感知能力。半数死亡节点周期从网络运行开始到出现一半数量节点死亡或者还剩余一半数量节点存活时运行的轮数，在一半数量节点死亡时期内，无线传感器网络的感知能力下降到一个平庸的水平。随着传感器节点死亡数量的增加，从剩余半数存活节点到WSN运行结束，整个网络的感知能力持续减弱，网络滑入弱感知周期，在弱感知期间的后期，由于盲区的蔓延，感知能力急剧恶化，整个WSN基本上进入不可用状态。所以SP和HSN持续的时间越长，则WSN的网络性能也就越好。

大多数分层聚类协议为努力延长网络整体寿命而忽略了出现零簇头情况和WSN有效运行的阶段，不能避免出现零簇头的情况，也没能够有效地延长半数存活节点运作轮数，特别是稳定周期。因此，本文提出了基于簇头选举和节点位置优化的分层聚类协议（based on cluster election and position optimization clustering hierarchy, BCEPOCH）意在解决以上问题。BCEPOCH并不盲目追求WSN整体寿命，而是争取最长的稳定期和半数存活节点周期。同时，BCEPOCH可以保证每轮稳定地选举出最佳的簇头数量，避免零簇头轮的出现。

1 无线传感器网络模型 1.1 无线传感器结构

在 $M \times M$ 大小的分层聚类无线传感器网络中，整个WSN被分为若干个簇，每个簇由一个簇头和一定数量的传感器节点组成。假设在整个无线传感器网络内部署N个传感器节点，将传感器节点定义为 $S = \left\{ {{s_1},{s_2}, \cdots ,{s_N}} \right\}$ 。传感器节点监测到的数据通过直接或者间接多跳的方式传输到其所在簇的簇头，簇头收集其成员节点的数据进行分析融合，同样通过直接或者间接多跳的方式将数据传输到汇聚节点。用户可以通过汇聚节点对传感器网络进行配置和管理，发布监测任务以及收集监测数据。典型的WSN结构示意图如图1所示。

1.2 异构网络模型

本文采用文献[9]两级异构传感器，即普通传感器节点和高级传感器节点2种传感器。假设普通传感器节点的初始能量为 ${E_0}$ ，高级节点的初始能量为 ${E_0}(1 + a)$ ，a为高级节点的附加能量因子。在总共含有N个传感器节的网络内，设m为高级节点所占比例，则共用普通节点个 $N(1 - m)$ 个，高级节点 $Nm$ 个。网络的初始总能量为

$\begin{array}{l}{E_{{\rm{total}}}} = N\left( {1 - m} \right){E_0} + Nm\left( {1 + a} \right){E_0} = \\\;\;\;\;\;\;\;\;\;N{E_0}(1 + am)\end{array}$

(1)

从式（1）可以看出，在两级异构网络中，整个网络初始能量附加了am倍的能量，或者认为附加了am倍个传感器节点。

1.3 能量消耗模型

分层无线传感器网络的能量消耗主要发生在数据传输阶段和簇头对数据的处理分析融合部分。由于无线电传输中的能量消耗通常远大于一般传感器操作和存储器访问的能耗，所以本文只考虑数据无线传输和数据融合部分的能量消耗，忽略数据存储和其他操作的能量消耗。发生数据传输的主要有3个部分：1）普通传感器节点采集数据发送到簇头部分；2）簇头接收传感器节点数据；3）簇头发送数据到Sink节点部分。所以，加上簇头处理数据所消耗的能量，本文计算WSN网络的能耗共计以上4个部分，采用文献[5, 10]的能量消耗模型，传感器节点发送和接收k-bit消息的能量消耗分别定义为

${E_{{\rm{Tx}}}}\left( {k,d} \right) = \left\{ {\begin{array}{*{20}{c}} {k{E_{{\rm{elec}}}} + k{E_{{\rm{fs}}}}{d^2},d < {d_0}} \\ {k{E_{{\rm{elec}}}} + k{E_{{\rm{amp}}}}{d^4},d \geqslant {d_0}} \end{array}} \right.$

${E_{{\rm{Rx}}}}\left( k \right) = k{E_{{\rm{elec}}}}$

${d_0} = \sqrt {\frac{{{E_{{\rm{fs}}}}}}{{{E_{{\rm{amp}}}}}}} $

${E_{{\rm{CH}}}} = \left\{ {\begin{array}{*{20}{c}} {k({E_{{\rm{elec}}}} + {E_{{\rm{DA}}}}) + k{E_{{\rm{fs}}}}{d^2},d < {d_0}} \\ {k({E_{{\rm{elec}}}} + {E_{{\rm{DA}}}}) + k{E_{{\rm{amp}}}}{d^4},d \geqslant {d_0}} \end{array}} \right.$

式中： ${E_{{\rm{Tx}}}}\left( {k,d} \right)$ 和 ${E_{{\rm{Rx}}}}\left( k \right)$ 分别表示传感器节点发送和接收k-bit数据包总能量消耗； ${E_{{\rm{CH}}}}$ 和 ${E_{{\rm{DA}}}}$ 分别表示簇头节点发送和融合数据消耗的能量； ${E_{{\rm{elec}}}}$ 表示发射电路或接收电路每bit数据的消耗能量，是一个固定值；d表示传输距离， $d < {d_0}$ 为自由空间传输模型， $d \geqslant {d_0}$ 为多路径传输模型。汇聚节点接收和发送数据的能量不在我们考虑的范围内，它不涉及这种能源消耗模型。

2 基于节点位置优化的分层聚类协议（BCEPOCH）描述 2.1 阈值计算

在文献[9-10]中都采用了由节点初始能量和当前节点剩余能量来确定簇头选举概率。设节点i在r轮中成为簇头的概率为 ${p_i}\left( r \right)$ ，可求得：

${p_i}\left( r \right) = \left\{ {\begin{aligned}& {\displaystyle\frac{{{P_{{\rm{opt}}}}{E_i}(r)}}{{(1 + a \times m)\overline {E} (r)}}{\rm{ }}, \;\; i{\text{是普通节点}}}\\& {\displaystyle\frac{{{P_{{\rm{opt}}}}(1 + a){E_i}(r)}}{{(1 + am)\overline {E}(r) }}{\rm{ }}, \;\; i{\text{是高级节点}}}\end{aligned}} \right.$

${P_{{\rm{opt}}}} = \sqrt {\frac{1}{{2N{\rm{\pi }}}}} \sqrt {\frac{{{E_{{\rm{fs}}}}}}{{{E_{{\rm{amp}}}}}}} \frac{M}{{d_{{\rm{toSink}}}^2}}$

式中： ${P_{{\rm{opt}}}}$ 是最佳簇头所占比例， ${d_{{\rm{toSink}}}}$ 是节点i在第r轮中剩余的能量， $\overline {E}(r)$ 是在第r轮中所有剩余存活节点的平均能量，其理论计算公式为 $\overline {E}(r) = \displaystyle\sum\nolimits_{i = 1}^N {{E_i}(r)} ({1 / N})$ 。此公式每一轮都要计算每个节点的剩余能量，要实现这种方案非常繁琐，文献[9-10]中采用了估计值的方式估计 $\overline {E}(r)$ ，估值计算公式为

$\overline {E}(r) = \frac{{{E_{{\rm{total}}}}(1 - \displaystyle\frac{r}{R})}}{N}$

式中：R为网络寿命的总轮数，它也是通过预估得到，预估公式为 $R = {{{E_{{\rm{total}}}}} / {{E_{{\rm{round}}}}}}$ ， ${E_{{\rm{round}}}}$ 为每轮所有节点消耗的能量，

${E_{{\rm{round}}}} = l(2N{E_{{\rm{elec}}}} + N{E_{{\rm{DA}}}} + k{E_{{\rm{amp}}}}d_{{\rm{toSink}}}^4 + N{E_{{\rm{fs}}}}d_{{\rm{toCH}}}^2)$

式中：l是簇头数量， ${d_{{\rm{toSink}}}}$ 是所有簇头节点到汇聚节点的平均距离， ${d_{{\rm{toCH}}}}$ 是簇成员到簇头的平均距离。

Heinzelman等^[5]定义了节点i的簇头阈值，本文遵循该阈值模型。节点i的阈值计算公式为

$T\left( i \right) = \left\{ {\begin{split}&{\displaystyle\frac{{{p_i}\left( r \right)}}{{1 - {p_i}\left( r \right)(od (r,1/{p_i}\left( r \right)))}},i{\text{是候选簇头}}}\\&{0,{\text{其他}}}\end{split}} \right.$

2.2 改进簇头选举策略，优化簇头数量

在分层聚类算法中，每一个节点都用属性G_node来标记该节点是否属于候选簇头集合G，当某一个节点在最近 ${1 / {{P_{{\rm{opt}}}}}}$ 轮中内未做过簇头时G_node=1，此节点可以作为簇头的候选节点；反之G_node=0，此节点不能作为簇头候选节点。然后每 ${1 / {{P_{{\rm{opt}}}}}}$ 轮重置节点G_node值为1，LEACH类的同构无线传感器网络都是采用这种更新规则。在本文两级异构网络中，普通节点每 $({{1 + am)} / {{P_{{\rm{opt}}}}}}$ 轮做一次簇头，高级节点每 $({{1 + am)} / {{P_{{\rm{opt}}}}}}(1 + a)$ 轮做一次簇头。TSEP^[11]、EDDEEC^[12]等异构无线传感器网络同样采用这种规则。

我们假设在某轮中可以作为候选簇头节点（candidate cluster head，CCH）的数量为n_cch，最佳簇头（optimal cluster head，OCH）数量为n_och。在理想的情况下，每一轮的运行中都应该选出n_och个簇头，在WSN网络运行前期未出现死亡节点时，可作为簇头的候选节点数量n_cchcCH远大于最佳簇头数量为n_och，这时可以通过节点阈值选举出n_ochoCH个簇头。随着节点死亡，候选簇头节点减少，当n_cch=n_ochcCH=n_oCH时，为了保合理的簇头数量，跳过阈值选举将n_cch个候选节点全部选举为簇头。随着节点死亡数量进一步增加，当n_cch<n_ochcCH<n_oCH时，则无法选出最佳数量的簇头。出现这种情况时，更新未被选为簇头存活节点的G_node值，不需要等待 ${1 / {{P_{{\rm{opt}}}}}}$ 轮结束再更新，这样从更新后的节点中选出n_och−n_cchoCH-cCH个簇头。如果第一次更新选举出的簇头个数小于n_och−n_cch，则继续上一次操作，直到累计选举n_och个簇头或者没有可用节点为止，从而保障每轮都尽可能地选择出合理稳定的簇头数量。更改后的分簇选举流程如图2所示。本文提出的选举流程在打破LEACH选举局限性的同时又保留了其轮换机制的优越性。

2.3 节点阈值修正

根据式（1），我们得到了距离与无线电能耗的关系，如图3所示。显然，当节点距离越远时，无线传输所消耗的能量就越大，并且随着距离d的增加呈现指数级增长的趋势。所以，当节点到基站的距离大于 ${d_0}$ 时，尽可能地选择距离基站较近的节点作为簇头，可以较好地节省无线电传输的能量消耗。本文根据节点与基站的距离和节点与簇头的距离对节点的阈值进行修正，使得距离基站更近的节点成为簇头的概率更大以缩短通信距离，距离簇头较近的节点再当选为簇头的概率更小，避免分簇间隔太小，从而达到节省无线电传输能耗的目的。

选举簇头时本文同时兼顾节点与基站的距离和节点与簇头距离，当选举第一个簇头时只考虑节点与基站距离的影响，定义了修正因子 $\varphi \left( {i,j} \right)$ 为

$\varphi \left( {i,j} \right) = {\left( {\frac{{{s_{{\rm{avg\_to\_Sink}}}}}}{{{s_{{\rm{i\_to\_Sink}}}}(i)}}} \right)^\alpha }i \in \left[ {1,N} \right],j = 1$

$T\left( i \right) = T\left( i \right)\varphi \left( {i,j} \right) = T\left( i \right){\left( {\frac{{{s_{{\rm{avg\_to\_Sink}}}}}}{{{s_{{\rm{i\_to\_Sink}}}}(i)}}} \right)^\alpha }$

式中：节点 $i \in [1,N]$ ，簇头 $j \in [1,oCH]$ ， ${s_{{\rm{avg\_to\_Sink}}}}$ 表示节点到汇聚节点的平均距离，当节点部署完成后其为固定值， ${s_{{\rm{i\_to\_Sink}}}}(i)$ 表示节点i到汇聚节点的距离， $\alpha $ 为调节参数 显然，距离汇聚节点越远的节点其阈值越小，被选为簇头的概率就越低，式（2）为抑制较远节点被选为簇头的概率。

根据式（2）选择出第一个簇头后，在第二个簇头选举前，根据节点与簇头1的距离和节点与基站的距离对阈值进行修正。计算如下：

$\begin{array}{l}\varphi \left( {i,j} \right) = {\left( {\displaystyle\frac{{{s_{{\rm{i\_min\_to\_CH}}}}(j)}}{{{s_{{\rm{avg\_min\_to\_CH}}}}}}} \right)^\beta }{\left( {\displaystyle\frac{{{s_{{\rm{avg\_to\_Sink}}}}}}{{{s_{{\rm{i\_to\_Sink}}}}(i)}}} \right)^\alpha }\end{array}$

式中： ${s_{{\rm{i\_min\_to\_CH}}}}(j)$ 表示节点i到最近簇头j的最小距离， ${s_{{\rm{avg\_min\_to\_CH}}}}$ 表示所有节点到自己最近簇头的平均距离， $\beta $ 为调节参数， $ i \in \left[ {1,N} \right],j \in [2,{n_{\rm och}}]$ 。当节点i距离最近簇头j越远时，阈值修正因子 $\varphi \left( {i,j} \right)$ 值越大，此节点i被选为簇头的可能性越高，反之则越小。

3 仿真结果及分析

本文仿真环境使用MATLAB 8.1平台，在大小为100 m×100 m场地中随机部署100个传感器节点，其他具体实验参数如表1所示。与LEACH^[5]，TSEP^[11]，MODLEACH^[13]协议作比较，分析BCEPOCH的性能。图4为BCEPOCH运行示意图。

3.1 簇头选举优化

本文算法针对LEACH、TSEP等算法在簇头选举时出现不稳定和零簇头的情况进行簇头选举优化，优化后保障WSN在稳定期内的簇头数量始终为 $pn$ 个。我们取p=0.5, n=100，在理想情况下每一轮选举出簇头的数量都应该为 $pn$ 个，稳定期内没有节点死亡时，簇头个数应为5个。在表2中，我们统计分析了每种协议在稳定期、半数存活节点期间、网络寿命期间簇头数量的均值与方差。同时，为了更加明显地表明各算法在簇头选举的稳定性，绘制了簇头稳定性柱状图如图5所示。

由表2和图5可以得出，在稳定期、半数存活节点期和整个网络生命周期本文提出的BCEPOCH算法在簇头选举的稳定性上明显高于其他算法。尤其在稳定期内没有节点死亡时，BCEPOCH每轮网络运行都能选举出5个最佳数量的簇头，并且在稳定期均值为5，方差为零，性能表现与理想情况相同，LEACH与MODLEACH表现几乎相同，TSEP表现最差。

3.2 网络有效生命周期和网络寿命

本文算法在优化簇头选举的同时通过节点与基站的距离和节与簇头距离实时修正节点阈值，延长WSN网络的稳定期和半数存活节点时期。通过MATLAB仿真，得到各协议的在不同阶段的运作轮数，结果汇总如表3所示。

分析表3数据可以得出，在网络的稳定期和半数存活节点时期内，本文提出的BCEPOCH算法网络运作轮数明显高于其他3种算法。在稳定期内运行轮数表现相比于LEACH、TSEP、MODLEACH分别提高了35.55%、22.85%、22.22%，在半数存活点时期分别提高了40.19%、14.30%、40.07%，在整个网络寿命周期内，BCEPOCH算法运作轮数少于其他3种算法。但是由于BCEPOCH稳定的簇头选举策略使得每一轮都可以选举出簇头，不会出零簇头情况，所以在整个网络寿命的有效轮数中BCEPOCH算法仍然优于其他3种算法，较其他3种算法分别提高了66.84%、47.53、136.91%。在图6中可以明显得出，BCEPOCH算法在有效地延长了WSN网络的稳定期和半数存活节点期的同时又延长了整体网络运行的有效轮数。

4 结论

针对无线传感器网络中簇头选举的不稳定性和稳定期较短的问题进行研究，通过仿实验分析本文主要做出以下改进和展望：

1）提出的修改簇头选举流程可以有效地保障每轮网络都能选举出合理数量的簇头，避免零簇头的产生，提高簇头选举的稳定性。

2）根据节点与簇头的距离和节点与基站的距离实时修改节点阈值，延长网络的稳定期。

3）本文中仍然存在可以优化的空间，可以看出本文算法在稳定期与生命周期的占比上并不占优势，下一步的研究应当重点关注与提高稳定期的占比上。