0 引言

无线传感网络(Wireless Sensor Network, WSN)是由大量的廉价微型传感器节点以无线通信方式组成的一个多跳自组织网络^[1]。环境信息的采集和管理是无线传感器网络的主要功能，在工业、农业、军事、安全、医疗等很多领域都有广泛应用。随着无线传感器网络的应用越来越广泛，WSN中能量的高效利用成为需要解决的关键问题。大量散布的无线传感器节点一般由有限能量的电池供电，而节点电池更换困难，节点寿命有限。为了延长网络生命周期，需要能量高效、能耗均衡的无线传感器网络路由协议，否则会产生能量空洞现象^[2]。在WSN中传感器节点采用多跳的方式将采集的数据发送给基站。一般情况下，传感器节点在检测区域内的分布是随机的，它们可以自组织网络。当一个节点因为能量消耗殆尽或者其他原因导致不能工作，称之为节点死亡，节点死亡就可能导致出现能量空洞现象。

能量空洞现象的避免是延长网络生命周期的重要方面，而要避免部分节点过早死亡就要很好地均衡整个网络的节点能耗^[3]。在无线传感器网络中分簇路由算法相比平面路由算法具有更好的节能性，因此分簇的路由协议是研究重点。低功耗自适应集簇分层型(Low Energy Adaptive Clustering Hierarchy, LEACH)算法^[4]是最早的分簇路由协议，之后很多文献对分簇协议进行了大量研究，文献[5]中提出的混合能量高效分布式不等分簇算法(Unequal Hybrid Energy Efficient Distributed algorithm, UHEED)在一种混合能量高效分布式自组织网分簇(Hybrid, Energy-Efficient, Distributed clustering approach for ad-hoc sensor network, HEED)方法^[6]的基础上采用基于非均匀分簇的无线传感器网络路由(Energy-Efficient Uneven Clustering, EEUC)协议^[7]的竞争半径计算方法，通过综合考虑节点到基站的距离因素进行非均匀的分簇以解决HEED算法在能量空洞问题上的不足。文献[8]中轮转的混合能量高效分布式不等分簇算法(Rotated Unequal Hybrid Energy Efficient Distributed algorithm, RUHEED)对UHEED作了进一步的改进，通过成簇后簇首轮转的方式减少簇首选举与成簇过程中的能量开销达到延长网络生命周期的目的；但是算法在簇首轮转阶段仅考虑了节点剩余能量，直到出现节点死亡才进行重新分簇，不能很好地均衡能耗，这导致节点一旦出现死亡整个网络的节点迅速死亡。

除了通过分簇路由协议提高网络的生命周期，克服能量空洞现象，也有文献提出采用同心环模型对能量空洞现象进行分析。文献[9]提出了在节点均匀分布的WSN中采用同心环模型分析能量空洞现象，验证了圆环宽度相等的情况下，路由上的能量消耗最小。文献[10]为了均衡节点能量，在同心环模型上提出部署算法，使每一环上的节点数目相等，这造成了靠近基站环的节点密度过大，浪费了能量和成本。文献[11]提出了基于同心环的分簇路由协议，对簇头位置初始化、簇头轮转选择、簇间路由协议进行了优化，没有对每环的簇首数进行优化处理；文献[12]提出了一种基于分环的能量高效无线传感器网络分簇路由(sub-Ring-based Energy-efficient Clustering Routing for WSN, RECR)算法，算法对各环的簇首数进行了优化，采用了主次簇首轮换的方式降低节点能耗。以上基于分环的算法研究仍然在均匀分布的WSN网络模型下，或者对网络节点采用部署策略，只能应用到小部分的实际环境。

现有研究主要集中在网络节点均匀分布情况或者通过采用节点部署策略来解决网络能耗不均产生的能量空洞问题。本文针对同构网络中，节点非均匀分布前提下的能量空洞问题，提出了非均匀分布的同心环传感器网络模型分簇路由算法——基于环的节点非均匀分布分簇算法(Ring-based Clustering Algorithm for Nodes Non-uniform Deployment, RCANND)。该算法在同心环网络模型基础上，针对节点非均匀分布的传感器网络研究能量均衡的分簇路由协议。在网络初始化阶段根据网络总能耗最低的原则以及每一环的节点数目对簇首数优化，得到最优簇首数后再计算每一环各自的簇首竞争半径。在簇首选举阶段，通过竞争获得最佳簇首，同时对簇内的各个成员节点计算簇首选择度，通过簇首轮转来均衡各节点能耗，减少了每轮进行簇首选举的网络能耗。最后通过簇间多跳路由实现数据传输到基站，完成通信。

1 无线传感器网络采用的模型 1.1 网络模型

在本文，对无线传感器网络模型作如下假设：1) 节点同构，基站外的所有节点具有相同的特性，如初始能量、通信半径等。2) 监测区域内的同构传感器节点具有唯一ID，规定以j为下标的参数均表示第j个传感器节点的参数。3) 所有节点和基站部署之后都是静止的，都能根据距离调节它们的发射功率。4) 同构传感器网络节点随机分布在半径为R的区域内，圆形区域内分为M个宽度相等的环形带，并且每个环形带内的传感器节点的密度是随机的；对环形带进行编号，规定用i表示第i(i=1, 2, …，M)个环形带，文中下标为i的均表示第i个环形带中的参数。5) 这些环形带之间节点的分布是非均匀的，每个环形带中都有着不同的节点密度参数ρ_i，ρ_i的值可以随不同的部署模型而改变。在一个环形带中，节点的个数N_i=ρ_i×S_i，S_i为该环形面积。网络节点分布模型如图 1所示。

1.2 能量消耗模型

本文采用与LEACH算法相同的无线电模型。发送l b的信息量到距离d处需要消耗的能量如下：

$E{T_x}\left( {l,d} \right) = \left\{ {\begin{array}{*{20}{c}} {l \times {E_{{\rm{elec}}}} + l \times {\varepsilon _{{\rm{fs}}}} \times {d^2},} & {d \le {d_0}}\\ {l \times {E_{{\rm{elec}}}} + l \times {\varepsilon _{{\rm{amp}}}} \times {d^4},} & {d > {d_0}} \end{array}} \right.$

(1)

式中：ε_fs表示自由空间模型的能耗系数；ε_amp表示多路径放大电路的能耗系数；d₀是节点可以直接与基站通信的距离。为了接收l b的信息量，消耗的能量为：

$E{R_x}\left( l \right) = l \times {E_{{\rm{elec}}}}$

(2)

此外，对网络中的其他能量消耗作如下假设：1) 节点感知环境信息的能量消耗为E_s；2) 簇首消耗E_DA用于数据融合。

2 RCANND设计

本文提出的WSN分簇路由算法以轮为周期运行，每一轮由优化分簇和数据传输两部分组成。优化分簇部分由三个阶段组成：第一阶段，初始化网络，对网络中每环簇首数进行优化；第二阶段，由簇首选举和簇建立组成的分簇过程阶段；第三阶段，每完成一次数据采集过程进行簇首轮转以均衡节点能耗，轮转一定次数后重新循环第二阶段到第三阶段。数据传输部分，通过簇间多跳的路由方式将数据传输到基站。

2.1 簇首数优化

在传感器网络区域内，获得最优簇首数是有效均衡网络能耗、延长网络生命周期的重要因素。在基于环的分簇路由算法中，都有对簇首数优化，但是这些算法主要是在均匀分布的网络模型基础之上。现在用k来表示期望的最优簇首数目，根据文献[13]中每簇平均面积的计算方法以及本文中的网络模型，网络监测区域内每簇的平均面积为πR²/k，那么每簇节点平均密度ρ=1/(πR²/k)，那么可以得到节点到簇首距离的平方期望是：

${\rm{E}}\left[ {d_{{\rm{nodetoCH}}}^2} \right] = \rho \int_{\theta = 0}^{2{\rm{ \mathsf{ π} }}} {\int_{r = 0}^{R/\sqrt k } {{r^3}{\rm{d}}} } r{\rm{d}}\theta = \frac{1}{2} \cdot \frac{{{R^2}}}{k}$

(3)

根据本文的能量消耗模型，当基站距离节点很近时，通信损耗认为是自由空间损耗。当传感器节点距离基站较远时认为是多路径损耗。现在总的能量损耗由文献[14]可得：

$\begin{array}{l} {E_{{\rm{Total}}}} = L \cdot \left( {2 \cdot N \cdot {E_{{\rm{elec}}}} + N \cdot {E_{{\rm{DA}}}} + k \cdot {\varepsilon _{{\rm{f}}s}} \cdot d_{{\rm{CHtoBS}}}^2 + } \right.\\ \quad \left. {N \cdot {\varepsilon _{{\rm{fs}}}} \cdot {R^2}/\left( {2k} \right)} \right) \end{array}$

(4)

令$\frac{{\partial {E_{{\rm{Total}}}}}}{{\partial k}} = 0$，可以得到k的最优值，如式(5) :

${k_{{\rm{opt}}}} = \sqrt {N/2} \cdot R/{d_{{\rm{CHtoBS}}}}$

(5)

簇首到基站的平均距离估算公式为：

${d_{{\rm{CHtoB}}{{\rm{S}}_{{\rm{ave}}}}}} = \sum\limits_{i = 1}^M {{N_i}{R_i}} /N = \sum\limits_{i = 1}^M {{\rho _i}{S_i}{R_i}} /N$

(6)

式中：R_i表示每一环到基站的最大半径。由此，k_opt可以求得：

${k_{{\rm{opt}}}} = N \cdot \sqrt N \cdot R/\left( {\sqrt 2 \cdot \sum\limits_{i = 1}^M {{\rho _i}{S_i}{R_i}} } \right)$

(7)

现在让每个环里的簇的数目是k_i, k_i-1, …, k₁，那么：

$\begin{array}{l} {k_{{\rm{opt}}}} = \sum\limits_{i = 1}^M {{k_i}} = {k_i} + {k_{i - 1}} \cdots + {k_1} = \\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \sqrt {\frac{{{N_i} + {N_{i - 1}} \cdots + {N_1}}}{2}} \cdot \frac{{{R_i}}}{{{d_{{\rm{CHtoB}}{{\rm{S}}_i}}}}} \end{array}$

(8)

式中：

${d_{{\rm{CHtoB}}{{\rm{S}}_i}}} = \sum\limits_{i = 1}^M {{N_i}{R_i}} /\sum\limits_{i = 1}^M {{N_i}} $

计算得到网络每环的最优簇首数k_i，簇首的竞争面积近似为每环的面积与每环簇首数k_i的比，那么每环簇首各自的平均竞争半径R_i^c为：

${R_i}^c = \sqrt {{R_i}^2 - {R_{i - 1}}^2/{k_i}} $

(9)

2.2 分簇过程

分簇过程由簇首选举、簇建立两个阶段组成。簇首选举阶段，获取最优簇首数后得到节点的竞争半径R_i^c，各个节点在竞争半径内广播自己的ID、位置信息；在获得竞争半径R_i^c以及竞争半径内节点的位置信息后，每个节点计算存储自身的簇首选择度P_j，并在竞争半径内广播。在邻居节点中进行簇首竞争，簇首选择度P_j为：

${P_j} = {c_1}{E_r}/{E_{{\rm{init}}}} + {c_2}{d_i}/{d_{j - {\rm{toBS}}}} + {c_3}/{d_{j - {\rm{avg}}}}$

(10)

${d_i} = 2\left( {R_i^2 + {R_i}{R_{i - 1}} + R_{i - 1}^2} \right)/\left[ {3\left( {{R_i} + {R_{i - 1}}} \right)} \right]$

(11)

式中：E_r为节点剩余能量；E_init为节点初始能量；d_i为该圆环到基站的平均期望距离；d_j-toBS为节点到基站的距离；d_j-avg为各节点与竞争半径内各节点的平均距离；c₁、c₂、c₃为权重系数且c₁+c₂+c₃=1。

选择度P_j考虑了节点的剩余能量、到基站的距离因素，以及与邻居节点间的距离。如果在竞争半径内，某个节点簇首选择度P_j最大，那么该节点被选为簇首。

簇建立阶段，成为簇首的节点在竞争半径R_i^c范围内广播自己成为簇首的消息，普通节点在竞争半径内选择P_j最大的簇首申请加入。加入簇时，分为两个阶段：第一阶段，每个簇首按照P_j大小接收不多于n_i个节点，这里n_i由式(12) 给出，当超出节点数时返回拒绝加入的消息。已经成簇的普通节点自动退出分簇过程，不再接收簇首竞争和其他簇首消息；未成簇的普通节点按照P_j的大小继续完成簇的建立。第二阶段，第一阶段中均被拒绝的普通节点选择最近的簇首加入簇，以防止产生孤立节点。由式(8) 和式(9) 可知，节点分布密度决定了簇首数目和竞争半径。当某区域节点分布密度过大时，那么产生的簇也会相应增加；节点分布密度过小时，产生的簇也会减少，同时簇的覆盖半径也会增大避免产生孤立节点。

2.3 簇头轮转策略

成簇过程完成后，簇首已经获得了各个簇成员的P_j，簇首按照P_j大小排序形成一个簇首选择序列表。簇首选择序列表作为下一轮的簇首选择依据。每一轮数据传输结束后，根据簇首选择序列中排在下一位次的节点成为簇首并在簇内广播消息，其他节点接收到消息后，下一轮将数据传送给新簇首。每经过n轮，重新进行分簇过程，产生新的簇首选择序列，以均衡网络能耗；这里n取各环中的最小值，n由式(13) 给出。虽然有些节点未在本次轮转担当簇首，但是在下次竞争簇首时具备更大优势，依然能够保证整个网络的能耗均衡。

${n_i} = {N_i}/{k_i}$

(12)

$n = {\rm{min}}\left\{ {{n_1},{n_2}, \cdots ,{n_i}} \right\}$

(13)

数据传输过程，簇首对簇内数据进行融合后，将数据传输到基站。当簇首到基站的距离小于等于直接传输距离d₀时，簇首直接与基站进行通信; 当距离大于d₀时，采用多跳的路由方式将数据传送到基站。仿真中的具体路由算法采用文献[11]中的簇间多跳路由算法。

3 算法仿真与分析

为了验证本文算法在能耗均衡以及延长网络生命周期方面的性能，通过Matlab仿真平台，对算法进行仿真和对比。仿真中使用的网络节点分布模型如1.1节所述，传感器网络部署在一个圆形监测区域内，基站位于监测区域的中心位置。本文主要的仿真参数均采自LEACH算法^[4]，主要的仿真参数如表 1所示。

3.1 能耗均衡性

将监测区域分成宽度相等的3环，针对不同的节点分布情况，作网络能耗变化的仿真。当节点分布模型不同时，簇首产生的数目必然不同，为了验证算法在节点分布密度变化时依然能有良好的能耗均衡性能，现在选取四种典型节点分布模型进行仿真对比。这四种分布模型分别是case1(ρ₁＞ρ₂＞ρ₃)、case2(ρ₂＞ρ₃=ρ₁)、case3(ρ₁＜ρ₂＜ρ₃)以及case4(ρ₁=ρ₂=ρ₃)，本次仿真的具体取值如表 2，仿真结果如图 2所示。

从图 2中可以看出，相同半径下，在网络节点分布密度不同的情况下，网络的节点平均能耗的波动并不明显；算法最优簇首数的动态选择发挥了均衡整个网络能耗的作用，使得不同分布模型下的网络能耗未出现大幅变化；当半径不同时，由于半径越大，平均传输距离越大，较大半径平均能耗会略有提升。对比各个半径下、相同分布密度的网络节点平均能耗，依然波动不明显。从图 2中还可以看出：不同半径下，均在第三种节点分布模型(case3) 下的平均能耗最高，第三种分布模型的各环节点密度系数的关系是ρ₁＜ρ₂＜ρ₃，可见最外环的节点数目最多，而最内环的节点数目最少，这导致节点与基站的平均通信距离最大，能耗自然会略有提高。

3.2 分环数与网络生命周期

讨论网络半径变化时，网络的最佳分环数。针对本文的网络模型，在网络节点分布情况不变以及半径不变的情况下，改变同心环的数量。在100 m、180 m、320 m的半径下进行仿真，讨论不同的分环数与网络生命周期的关系，仿真结果如图 3所示。从图 3中可以看出，整体上，分环数过多会导致网络生命周期减少，但是同半径下使网络生命周期最长的最优分环数总是存在的。由于算法对于簇首数的优化，分环数开始增加时，网络生命周期的减少并不明显。随着同心环数量的增加，同心环的面积在减小，必然会产生更多的簇，节点的能量消耗增加，网络生命周期减少。

从3.1节中的仿真结果可知，本文算法的最优簇首数的动态选择，可以有效地均衡不同密度下的网络能耗以避免能量空洞、延长网络生命周期；但是当分环数变多导致的簇首数增加，路由的转发能量增加，仍然使网络总能耗增加，减少了网络生命周期。可见，本文算法仍然需要合理选择分环数量以有效延长网络生命周期。

3.3 网络生命周期对比

为了验证算法在延长网络生命周期方面的有效性，在非均匀分布的模型中，将本文算法与算法UHEED和RUHEED进行了对比；在均匀分布情况下，将本文算法与分环算法RECR进行对比，仿真结果如图 4所示。

从图 4(a)可以看出，本文算法解决了RUHEED在簇首轮转上导致的能耗不均衡、节点迅速死亡的问题；由于本文算法的不定周期分簇，部分轮转过程会产生较大能耗，死亡节点在后期会产生死亡速度增加现象。以50%节点存活作为网络的生命周期，在非均匀分布情况下，本文算法的网络生命周期比UHEED和RUHEED分别提高约18.1%和11.5%。由图 4(b)可以看出，RECR算法采用主次簇首轮换的方式减少分簇的能耗，本文算法采用的簇首轮换机制比RECR减少了更多的分簇能耗，因而网络生命周期上比RECR算法提高了约6.4%，可见在均匀分布的情况下，本文算法在网络生命周期上也略有提高。由此可得，所提算法相比传统的分环算法，主要优势在于能适应不同的节点分布情况，能够适应更多的实际应用环境。

4 结语

本文在已有的分环分簇算法基础上提出了一种节点非均匀分布情况下的算法。该算法主要解决在节点非均匀分布的网络模型下的能耗均衡问题，避免产生能量空洞现象，延长了网络的生命周期。在网络初始化阶段，根据每一环的节点数目进行簇首数优化；在簇首选举阶段，通过竞争获得最佳簇首，同时对簇内的各个成员节点计算簇首选择度P_j，通过簇首轮转来均衡各节点能耗，同时避免了每轮进行簇首选举，降低了网络能耗。仿真结果表明，本文算法在不同分布模型下有效地均衡了网络能耗，延长了网络生命周期。今后可考虑针对分环的大规模网络中多跳的簇间路由算法进行进一步的研究。