0 引言

无线传感器网络(Wireless Sensor Network, WSN)是由部署在监测区域内大量的传感器节点组成，通过无线通信方式，监测和收集区域内对象信息的多跳自组织网络系统。随着信息技术的发展，WSN在生物医疗、国防军事、环境检测、抢险救灾、城市管理、智能家居、工农业控制等领域有着广泛的应用前景。无线传感器网络最突出的特点是传感器节点能量有限且不可再生，所以在无线传感器网络中，降低网络能量消耗、延长网络生存周期是面临的重要挑战^[1]。

层次路由协议通过分簇在一定程度上延长了无线传感器网路的生存周期。其中低功耗自适应集簇分层(Low Energy Adaptive Clustering Hierarchy, LEACH)^[2]协议通过随机选择一小部分节点作为簇头节点并采用周期轮换机制，但由于随机选择簇头节点导致簇头节点分布不合理。此外，在数据传输阶段，簇头节点与汇聚节点直接通信，导致簇头节点的能量消耗过快。吕涛等^[3]通过引入簇成员数门限和合并极小簇的方法，避免存在极大簇和极小簇。文献[4]针对LEACH协议频繁地选择簇头节点消耗过多的能量提出了一种基于LEACH的簇头连任协议(cluster head Reappointment protocol based on LEACH，LEACH-R)，有效地延长了网络的生存周期。

针对均匀分簇存在簇间能耗不均衡的问题，李成法等^[5]提出了一个能量高效的非均匀分簇(Energy-Efficient Uneven Clustering, EEUC)算法。EEUC通过使用非均匀的竞争范围来构造大小不等的簇，使得靠近汇聚点的簇的规模小于远离汇聚点的簇，均衡了簇头节点的能量消耗。尚凤军等^[6]提出了分布式能量有效非均匀成簇(Distributed Energy Efficient Unequal Clustering, DEEUC)算法，在选择簇头时，加入了平均能量因子平衡全网节点的剩余能量，并通过调节簇头竞争半径调节簇的大小，在一定程序上缓解了能耗不均衡的问题，但离基站比较近的簇头频繁转发其他簇头发送的数据包，因此消耗更多的能量，使得离基站近的簇头容易死亡，产生“热点”问题。蒋畅江等^[7]提出了能量均衡的无线传感器网络非均匀分簇路由(Distributed Energy-Balanced Unequal Clustering routing, DEBUC)协议。DEBUC在选择簇头时，参考候选簇头的剩余能量和邻居节点的剩余能量，采用基于时间的簇头竞争算法，通过控制候选簇头的竞争范围, 使得距离基站较近的簇规模较小。数据传输时，簇头节点根据节点剩余能量、簇内通信代价和簇间通信代价, 在邻居簇头中选择中继节点作为下一跳; 但存在离基站较远的簇规模过大，节点能量消耗过多的问题。文献[8]中提出了能量有效的LEACH改进协议(Energy Efficient Extended LEACH, EEE LEACH)。EEE LEACH采取分层的思想，在簇头节点之间选取一些主簇头节点。簇内节点将数据发送给簇头节点，簇头节点将融合后的数据发送给距离最小的主簇头节点，主簇头节点将接收的数据包发送给汇聚节点。但是EEE LEACH存在主簇头节点选择不合理以及主簇头节点能量消耗过大的问题，影响网络的生存周期。黄廷辉等^[9]提出了基于非均匀分簇的无线传感器网络分层路由协议(Hierarchical Routing Protocol based on Non-uniform Clustering, HRPNC)。HRPNC在分层的基础上改进了DEBUC协议的竞争半径，控制了节点竞争半径的范围，避免了大规模网络中离基站远的节点竞争半径过大的问题。在簇头选择时，HRPNC随机选择一些节点作为候选簇头节点，再依据节点竞争半径选择簇头节点，而节点的基准竞争半径取决于每层的面积和节点数目。由于HRPNC没有考虑节点的能量以及密集程度，存在簇头节点选择不合理的问题。

针对以上一些协议的不足，为了解决簇头节点选取不合理以及能量消耗不均的“热点”问题，本文提出了一个非均等分区的非均匀分簇路由协议(Unequal partition Area Uneven Clustering routing protocol, UAUC)。UAUC通过结合非均等分区以及综合考虑能量因子、距离因子以及密集程度因子选择簇头节点，使簇头节点分布更加合理。在数据传输时，通过构建合理的路径树，均衡节点之间的能量消耗，提高网络的生存周期。

1 网络与能耗模型 1.1 网络模型

本文假设无线传感器网络中所有节点随机分布在一个矩形区域内，网络模型具有以下性质：

1)节点随机均匀地分布在监测区域中。

2)基站位于监测区域底边中点处，且位置固定。

3)基站具有较强的计算能力、存储能力，且能量不受限制。

4)所有节点都具有唯一的标识(ID)，能量受限。

5)节点可以通过计算得出当前的剩余能量。

6)节点不具有位置感知能力。

7)节点具有相同的通信能力。

1.2 能耗模型

本文采用与文献[2]中相同的无线通信能耗模型。如图 1所示，该模型考虑了无线传输中发射电路发射信号的能耗，功率放大器的能耗以及接收电路中接收信号的能耗。功率放大器的能耗与传输距离d有关：当d < d₀时，采用自由空间模型; 当d≥d₀时，采用多径衰减模型(d₀是距离阈值，公式为d₀=$\sqrt{{{\varepsilon }_{\text{ts}}}/{{\varepsilon }_{\text{mp}}}}$)。

因此当发送Lb数据且传输距离为d时，所消耗的能量为：

$ {{E}_{TX}}(L, d)=\left\{ \begin{align} &L{{E}_{\text{elec}}}+L{{\varepsilon }_{\text{fs}}}{{d}^{2}}, d<{{d}_{0}} \\ &L{{E}_{\text{elec}}}+L{{\varepsilon }_{\text{mp}}}{{d}^{4}}, d\ge {{d}_{0}} \\ \end{align} \right. $

(1)

其中：E_elec表示发射电路损耗的能量，ε_fs表示自由空间模型中功率放大所需的能量，ε_mp表示多径衰减模型中功率放大所需的能量。

节点接收Lb数据所消耗的能量为：

$ {{E}_{\text{RX}}}(L)={{E}_{\text{RX-elec}}}(L)=L{{E}_{\text{elec}}} $

(2)

分簇算法中采用数据融合算法可以减少数据的发送量，缓解数据冗余的问题。数据融合也需要消耗能量，本文用E_u表示融合Lb数据所消耗的能量。

$ {{E}_{u}}=L\cdot {{E}_{\text{DA}}} $

(3)

其中E_DA表示融合一个1b数据所消耗的能量。

2 基于非均等分区的路由协议UAUC

本文提出的基于非均等分区的路由协议UAUC分成三个阶段：第一阶段，非均等分区阶段；第二阶段，选择簇头节点以及簇的形成阶段；第三阶段，数据传输阶段。

2.1 非均等分区阶段

UAUC协议首先对网络进行非均等分区。初始化建立一个矩形网络，基站位于矩形网络底边的中点处。基站与其对边中点的连线将矩形网络均分成大小相等的两部分。以基站为圆心，半径为R_i(i=1, 2, …)生成一系列圆O_i(i=1, 2, …)，其中R_i满足条件：R_i=i·R₁(i=1, 2, …)。圆O_i将矩形网络分成了k个区域，对每个区域标记区域号，用A_k表示。分区后的模型如图 2所示。

设初始矩形网络边长为a，圆O₁的半径R₁=r，则以基站所在位置点为圆心，R_i为半径的圆O_i有$\left\lceil a/r \right\rceil $个。那么区域数目k满足以下条件：

$ k=2\left\lceil a/r \right\rceil+2 $

(4)

设总节点数目为n，每个区域的节点数目为N_i(i=1, 2, …, k)，则满足以下公式：

$ \sum\limits_{i=1}^{k}{{{N}_{i}}}=n $

(5)

设簇头节点数目为m个，其中区域i中簇头节点数目为M_i，则满足以下公式：

$ {{M}_{i}}=\left\lceil p\cdot {{N}_{i}} \right\rceil $

(6)

其中:p为区域中节点成为簇头节点的概率，经大量实验考证，本文取p=0.04时，效果最优。

$ \sum\limits_{i=1}^{k}{{{M}_{i}}}=m $

(7)

对于簇头节点数目m的最优取值，参考文献[10]，总能量消耗函数如下：

$ \begin{align} &{{E}_{\text{Total}}}=L\cdot \left(2n\cdot {{E}_{\text{elec}}}+n\cdot {{E}_{\text{DA}}}+\right.\\ &\ \ \ \ \ \ \ \ \ \ \ \left.m\cdot {{\varepsilon }_{\text{amp}}}\cdot d_{\text{to-BS}}^{4}+n\cdot {{\varepsilon }_{\text{fs}}}\cdot d_{\text{to-CH}}^{\text{2}} \right)\\ \end{align} $

(8)

其中$d_{\text{to-CH}}^{\text{2}}=\frac{{{a}^{2}}}{2m\cdot \text{ }\!\!\pi\!\!\text{ }}$。

通过使E_Total对m求导等于0，得到最优簇头数目m的公式如下：

$ m=\frac{\sqrt{n}}{\sqrt{2\text{ }\!\!\pi\!\!\text{ }}}\cdot \sqrt{\frac{{{\varepsilon }_{\text{fs}}}}{{{\varepsilon }_{\text{mp}}}}}\cdot \frac{a}{d_{\text{to-BS}}^{\text{2}}} $

(9)

其中：a是矩形网络的边长，ε_fs表示自由空间模型中功率放大所需的能量，ε_mp表示多径衰减模型中功率放大所需的能量。

根据式(4)~(9)，可确定参数r的最优取值。

2.2 簇头选择及簇形成阶段

经过非均等分区阶段后，整个网络被分成了k个区域，每个区域中的簇头节点数目由式(6)给出。在每个区域中，综合考虑能量、距离以及密集程度，合理地选择簇头节点。

定义1     能量因子${{E}_{i}}=\frac{{{E}_{i-\text{current}}}}{{{E}_{i-\text{initial}}}-{{E}_{i-\text{current}}}}$, 其中：E_i-current表示节点i的当前剩余能量，E_i-initial表示节点i的初始能量。

能量因子E_i表示节点i当前剩余能量与消耗能量的比值。节点i的能量因子E_i越大，则该节点当前剩余能量比较大且消耗能量比较少，更适合作簇头节点。

定义2    距离因子${{D}_{i}}=\frac{Ma{{x}_{\text{to-BS}}}-{{d}_{i-\text{BS}}}}{Ma{{x}_{\text{to-BS}}}-Mi{{n}_{\text{to-BS}}}}$，其中：d_i-BS表示节点i到基站BS的距离，Max_to-BS代表网络中节点到基站的最大距离，Min_to-BS代表网络中节点到基站的最小距离。

节点距离因子D_i越大，则该节点距离基站相对比较近，更适合作簇头节点。

定义3    密度因子S_i=s_i/s_avg，其中：s_i表示节点i的邻居节点数目，s_avg代表了邻居节点数目的平均值。

密度因子S_i代表了节点i的密集程度。

定义节点的权值公式如下：

$ valu{{e}_{i}}=\alpha \cdot {{E}_{i}}+\beta \cdot {{D}_{i}}+\gamma \cdot {{S}_{i}} $

(10)

其中：α、β、γ代表调节能量因子、距离因子和密度因子在选取簇头时的权重参数，且满足α+β+γ=1。α、β、γ的取值根据具体的网络可作调整。针对规模不是很大的网络，优先考虑节点的能量因子，本文在实验中取值为：α=0.5，β=0.3，γ=0.2。

根据式(6)和(10)，每个区域中的节点计算自己的value值，在区域范围中广播数据包宣布自己的value值以及节点ID，权值value大的节点最终宣布成为簇头节点。UAUC算法在簇头选择时，综合考虑了节点的剩余能量、能量消耗速率、离基站的距离以及密度等因素，使得簇头选择更加合理，有利于延长网络的生命周期。簇头选择完成后，簇头节点广播数据包，宣布成为簇头节点。其他节点不考虑区域，直接根据接收信号的强度，选择离自己最近的簇头加入，实现跨区域成簇。

2.3 数据传输阶段

本文采用簇内单跳和簇间多跳的数据传输方式。簇内节点通过单跳的方式将数据发送给簇头节点，再由簇头节点将融合后的数据包多跳发送给基站。簇头节点和基站之间互发hello包，构建一个简单连通无向图G=(V, E)描述簇头节点和基站之间的关系图模型。其中图G的顶点集合G_v表示簇头节点和基站，边集合G_E表示节点对称链路。根据图G，构建一棵路径树。

定义4    负载均衡度。根据图G=(V, E)生成的树T=(V, E′), E′⊆E，深度为N。树T的负载均衡度定义为${{W}_{T}}=\sum\limits_{i=1}^{N}{{{W}_{L}}(i)}$，其中${{W}_{L}}\left(i \right)=\underset{j=1}{\overset{{{n}_{i}}}{\mathop{\prod }}}\, {{t}_{ij}}/n$。t_ij表示第i层中以第j个节点为根的子树中的节点个数，n表示网络中所有节点的数目。当$\underset{j=1}{\overset{{{n}_{i}}}{\mathop{\prod }}}\, {{\mathbf{t}}_{ij}}$越大时，t_ij相差越小，负载越均衡。所以，在节点通信范围内，选择合适的节点作为父节点，构建一棵负载均衡度大的路径树，对解决数据传输时的“热点”问题有着重要的意义。

路径树的构建流程如下：

步骤1   开始，节点初始化。

步骤2   簇头节点广播数据包，找到邻居节点，构造出关系图G。

步骤3   根据关系图G，对节点进行分级。与基站可直接通信即图G中与基站Sink直接有边相连的节点定义为一级节点，与一级节点有边相连的节点定义为二级节点，依次确定所有节点的等级。

步骤4   以基站Sink为根，一级节点作为树的第一层节点，二级节点以一级节点作为父节点。当二级节点只与一个一级节点有边相连，则直接选择此一级节点作为父节点；否则在一级节点中选择使W_L(i)最大的节点作为父节点，直到所有节点遍历完成。

步骤5  结束。

以图 3为例，图 3(a)表示一个基站与簇头节点之间的关系图G，0号节点表示基站，1号节点到16号节点表示簇头节点。根据关系图G，可得到节点的等级数。一级节点为：1号节点、2号节点、3号节点和4号节点；二级节点为：5号节点、6号节点、8号节点、9号节点和10号节点；三级节点为：7号节点、11号节点、12号节点、14号节点、15号节点和16号节点；四级节点为：13号节点。一级节点作为路径树的第一层，二级节点作为路径树的第二层，依此类推。根据路径树的构建流程构造出一棵以基站为根节点的路径树，如图 3(b)所示。簇头节点依照构建出的路径树，将数据包发送给自己的父节点。

2.4 算法分析

UAUC先将网络进行非均等分区，对每个区域选出合适的簇头节点，其他节点不考虑所在区域直接选择离自己最近的簇头加入成簇。数据传输时，簇内节点将数据包发送给簇头节点，簇头节点将接收到的数据包进行融合，然后按照构建的路径树将数据包发送给自己的父节点，直到将数据包发送给基站。

为了避免簇头节点能量消耗过快死亡，UAUC采用簇头轮换机制。与LEACH协议不同，UAUC协议用区平均能量表示该区域中所有节点的平均能量。当有簇头节点的能量小于所在区域的区平均能量时，对该区域的簇头节点进行重新选取，重新计算该区域中节点的value值，选择value值最大的节点替换原来的节点作为新的簇头节点。避免每轮全部选取新的簇头所消耗的能量和代价。

UAUC的伪代码如下所示，其中：n(i).AreaNum代表节点n(i)所在的区域号, EnergyAvg(j)代表区域A_j的区平均能量，N_j表示区域A_j的节点数目。

ClusterHead selection algorithm

For every area A_j

    For every node n(i)

      If(n(i).AreaNum==A_j)

        Calculate value(i)according Eq(10);

      Else

        Continue

      End

    End

    Sort value(i), get the ClusterHead for the A_j;

End

Forming Cluster algorithm

For every ClusterHead(k)

    Broadcast ClusterHead-MSG(ID);

End

For every node n(i)

    If n(i)∉ClusterHead(k)

      Receiving all ClusterHead-MSG;

      Calculate Distance To ClusterHead d(i, k);

      Select the ClusterHead with min d(i, k);

      Add n(i)to ClusterHead(k)and broadcast the

        Join-ClusterHead-MSG(ID);

    End

End

Forwarding Message algorithm

For every node n(i)

      If n(i)∉ClusterHead(k)

        Forwarding(msg)to it’s ClusterHead(k);

      Else

        Receiving the msg and Data fusion;

        And Forwarding(msg)to parentNode in T;

      End

End

Cluster head rotation algorithm

For every area A_j

        $EnergyAvg(j)=\sum\limits_{i=1}^{{{N}_{j}}}{n(i).energy}/{{N}_{j}}$;

End

For every ClusterHead(k)

    If ClusterHead(k).Energy < EnergyAvg(j)

      Calculate value(i)in A_j according Eq(10);

      Select max value(i);

      ClusterHead(k)=ClusterHead(i);

    End

End

性质  UAUC的消息复杂度是O(n)。

证明  基站广播一个数据包，让所有节点计算到基站的距离；假设网络中有n个节点，则广播n个数据包，让所有节点计算密度因子。其中有k个节点被选作为簇头节点，簇头节点广播ClusterHead-MSG消息，宣布自己成为簇头节点。其余n-k个非簇头节点广播Join-ClusterHead-MSG消息，成簇。数据传输阶段，簇头节点广播一个数据包，确定自己的邻居节点。因此UAUC的消息复杂度是：1+n+k+(n-k)+k=2n+k+1, 因此UAUC的消息复杂度是O(n)。

3 仿真与实验

为了验证UAUC的性能，本文使用Matlab作为仿真工具，与经典的LEACH协议、DEBUC协议和HRPNC协议进行性能比较，从簇头节点分布、网络生存周期、节点剩余平均能量、节点剩余能量方差和数据包接收量等方面评估本文提出的UAUC协议的性能。实验参数设置如表 1所示。

在100m×100m的监测区域上随机部署200个节点，根据式(4)~(9)，可得到参数r=20, 那么区域数目k=12。

图 4显示了LEACH协议、DEBUC协议、HRPNC协议和UAUC协议簇头节点分布对比情况，如图 4(a)所示，LEACH协议由于随机选择簇头节点，导致簇头节点分布不合理。如图 4(b)所示，DEBUC协议中竞争半径逐渐增大，使得离基站远的簇规模过大，尤其在规模比较大的网络中，容易出现极大簇，影响网络生存周期。如图 4(c)所示，HRPNC协议通过改进DEBUC协议的竞争半径，缓解了DEBUC协议中离基站远的簇规模过大的问题，但簇头节点的分布仍存在问题。图 4(d)显示了UAUC协议的簇头分布情况。UAUC协议通过对网络进行分区，在每个区域中选择合适的节点作为簇头节点，使得簇头节点分布更加合理。

图 5显示了4种算法存活节点数量的变化曲线。从图 5中可以看出，UAUC运行到约2 000轮时才出现第一个节点死亡，约4 200轮时，50%的节点死亡，直到4 700轮，节点完全死亡。UAUC算法的网络生存周期相对于LEACH算法、DEBUC算法与HRPNC算法分别提高了88%，12%与17.5%。DEBUC算法仅仅通过节点与基站之间的距离控制簇头节点的分布，而UAUC算法通过非均等分区以及综合考虑多个因素选择簇头节点，使得簇头节点比DEBUC簇头节点分布更加合理，因此提高了网络的生存周期。

图 6显示了4种算法节点平均剩余能量的对比曲线。从图 6中可以看出，与LEACH算法、DEBUC算法和HRPNC算法相比，UAUC算法的节点剩余能量明显较高。DEBUC算法选择代价函数值最小的邻居节点作为下一跳，但中继节点并不进行数据融合而直接发送数据包，造成数据冗余。UAUC算法通过构建负载均衡路径树实现多跳传输并且进行数据融合，有效地提高了网络的能量效率。

图 7显示了4种算法节点剩余能量方差随轮数变化的对比曲线。从图 7中可以看出，LEACH协议的节点剩余能量方差最大，DEBUC协议与HRPNC协议的节点剩余能量方差较小，UAUC协议的剩余能量方差最小，且变化不大。表明UAUC协议通过构建合理的路径树实现多跳传输，有效地均衡了网络中节点能量消耗。

图 8显示了4种算法数据包接收量的对比曲线。从图 8中可以看出，随着仿真轮数的增加，存活节点数量减少，数据包接收量也随之减少。UAUC算法在数据包接收量上较LEACH协议，DEBUC协议以及HRPNC协议分别提高了400%，87.5%与25%。表明UAUC算法通过构建路径树有效地提高了数据包接收量。

4 结语

针对簇头节点分布不合理和节点能量消耗不均衡的问题，本文提出了一个基于非均等分区的路由协议UAUC。通过非均等分区，综合考虑能量因子，距离因子和密集程度因子选择合适的簇头节点，并且基于负载均衡的路径树实现簇间多跳数据传输。通过仿真验证，UAUC算法使得簇头节点分布更加合理，提高能量效率和数据包接收量，均衡能量消耗，延长网络生存周期。但是UAUC协议假设网络中的节点一直不间断地向基站发送数据包，并且该算法在大规模无线传感器网络中性能有所下降。

在今后的工作中，考虑针对大规模无线传感器网络，加入节点睡眠机制，当节点不需要发送和接收数据包时，使节点进入睡眠状态，节约节点的能量消耗；当要发送和接收数据包时，结束睡眠状态，进入活跃状态。怎样制定合理的状态转换机制将是下一步工作。