一种无线传感器网络低能耗覆盖优化算法

摘要

本发明公开了一种无线传感器网络低能耗覆盖优化算法，其在保证轮次簇能耗最低的前提下，能够获取满足覆盖能力的骨干节点最优值，同时通过PSO动态调整节点的飞行方向以及飞行速度，逐步迭代获取最优覆盖的骨干节点部署方案，既能有效地采集感知区域的数据信息，又能够充分管理传感器网络资源，有效地解决了无线传感器网络应用中的骨干节点分布不均、骨干节点数目无法达到最优、网络能耗不均衡、网络覆盖能力偏低等问题，为无线传感器网络在保证低能耗的前提下合理有效部署骨干节点以达到较高的网络覆盖均匀性和网络覆盖率提供技术支撑，为在网络低能耗的前提下提高网络的区域覆盖能力提供了一种全新的解决方案。

说明书

技术领域

本发明涉及一种无线传感器网络低能耗覆盖优化算法，属于无线传感器网络技术领域。

背景技术

无线传感器网络是由大量微型无线传感器节点组成的无线、多跳、自组织网络，其作用 是协同地感知、处理监测区域内感知对象的信息，并将感知数据发送至汇聚节点，被广泛应 用于国防、工业、农业、环境、医疗、物流、反恐、危险区域远程监控、重点区域防护等诸 多领域。

供电问题是目前制约无线传感器网络技术发展的一个主要瓶颈。其系统设计必须遵循节 能原则，以提高能量使用效率，延长网络的使用寿命。在保证网络低能耗的前提下，同时要 满足网络内节点对物理世界的感知能力，即达到网络节点覆盖的有效性。因此将低能耗和网 络覆盖结合考虑将更加有效地提高网络感知质量，对促进无线传感器网络的广泛应用具有重 要的现实意义。

在大规模危险环境的应用中，无线传感器网络的节点都是随机部署的。在传感器随机部 署的情况下，为保证感知数据能顺利传递，一般采用层次路由协议，即分簇路由协议。分簇 路由协议最基本的问题就是骨干节点的选择及分布问题。经典的层次路由协议主要有LEACH 协议、HEED协议、SEP协议、MARQ协议等等。LEACH协议采用分布式自举成簇算法和骨干节 点轮换机制，解决骨干节点能耗过分集中的问题。但是依然存在一些问题：骨干节点选举的 随机性可能会导致骨干节点在同一区域过于密集或太靠近网络边缘，骨干节点个数很难达到 最优值，网络覆盖能力无法得到有效保证等等。HEED协议通过对节点剩余能量和簇内通信能 耗的评估迭代成簇。但是在异构网络环境下难以充分利用能量异构特点，且某变量的取值对 收敛速度及簇分布的均衡性有直接影响。SEP协议是针对两级能量异构的传感器网络设计的， 采用能量因子加权的方法，对网络中两类节点的骨干节点自举门限进行了优化，使高级节点 有更大的成为骨干节点的概率，延长了网络的稳定期。但缺点是该协议仅适用于两级能量异 构的网络。MARQ协议则采用松散的耦合体系，引入了联络节点的概念，在发起查询信息的源 节点和提供信息的目的节点之间建立一条优化路径。

虽然上述这些协议能一定程度上改善层次路由协议，但是这些协议都面临一个相同的核 心问题，就是骨干节点选取的问题。骨干节点选取的合理性直接影响到网络能耗的均衡性和 网络覆盖能力，进而影响到网络的生命周期和网络感知质量的可靠性，因此，这是一个急待 解决的现实技术难题。

发明内容

本发明的目的是克服现有技术中无线传感器网络簇首选举算法中的网络能耗以及网络覆 盖等方面的不足之处，针对在保证网络低能耗的前提下提高网络覆盖能力的网络应用，提出 一种无线传感器网络低能耗覆盖优化算法。本发明的核心是在轮次簇低能耗的前提下结合节 点覆盖最优模型获得最优骨干节点数目以及邻居节点选取原则，根据PSO改进算法迭代运算， 获得骨干节点最优部署方案。

本发明提出一种无线传感器网络低能耗覆盖优化算法，包括以下步骤：

1)基于保证轮次簇能耗及覆盖能力的骨干节点数目优化算法：

11)普通节点的能耗来自于感知数据的发送能量，骨干节点的能耗主要来自于接收感知 数据、数据融合处理、数据转发至汇聚节点的能耗，因此普通节点的能耗为：骨干节点的能耗为：$E_{\mathrm{CH}}={\mathrm{lE}}_{\mathrm{elec}}(N/k-1)+{\mathrm{lE}}_{\mathrm{DA}}N/k+{\mathrm{lE}}_{\mathrm{elec}}+{\mathrm{lϵd}}_{\mathrm{toSink}}^{\alpha },$则某轮簇内的能耗为：

E_C＝L_CH+(N/k-1)E_M，网络总能耗为$E_{\mathrm{total}}=l({2\mathrm{NE}}_{\mathrm{elec}}+{\mathrm{NE}}_{\mathrm{DA}}+{\mathrm{kϵd}}_{\mathrm{toSink}}^{\alpha }+{\mathrm{Nϵ}}_{\mathrm{fs}}{d}_{\mathrm{toCH}}^2).$式中，E_elec为收发 电路单位bit数据能耗；ε_fs、ε_mp分别为近距离和远距离的功率衰减系数；d_toCH为各普通节点 到骨干节点距离的均值；E_DA为融合单位bit数据消耗的能量；d_toSink为各骨干节点到汇聚节点 距离的均值；d₀为参考距离，一般为

12)假设监测区域边长为M，簇所占区域为圆形，骨干节点位于簇中心，根据节点覆盖 最优模型，即相邻任意三个骨干节点成等边三角形，由此可得到每个簇所占区域的面积近似 为节点的分布律为则普通节点到骨干节点距离平方的数学期望值为：

$E\left[d_{\mathrm{toCH}}^2\right]=\int \int (x^2+y^2)k/M^2{d}_x{d}_y=\sqrt{27}{M}^2/{\left(2\pi \right)}^{2}k.$

13)根据轮次内网络总能耗及普通节点到骨干节点距离平方的数学期望值，可获得能耗 最小时骨干节点k的最优值为

$k_{\mathrm{opt}}=\left(\begin{array}{c}\frac{\sqrt[4]{27}\sqrt{N}M}{2\pi d_{\mathrm{toSink}}^2}\sqrt{\frac{{ϵ}_{\mathrm{fs}}}{{ϵ}_{\mathrm{mp}}}},d_{\mathrm{toSink}}\ge d_0\\ \frac{\sqrt[4]{27}}{2\pi d_{\mathrm{toSink}}^2},d_{\mathrm{toSink}}<d_0\end{array}\right),$

ε_fs、ε_mp分别为近距离和远距离的功率衰减系数；d₀为参考距离，一般为

2)用于保证网络覆盖均匀性的改进分簇部署算法：

21)覆盖均匀性反映了传感器节点在被监测区域的分布情况，根据覆盖均匀性与节点之 间距离的关系，采用改进分簇部署算法来获取覆盖均匀性指标，距离标准差值越小，则覆盖 均匀性越高，同时网络中节点的能量消耗越低，具体如下：

$U=\frac{1}{k_{\mathrm{opt}}}\underset{i=1}{\overset{k_{\mathrm{opt}}}{\Sigma }}{U}_i$

$U_i={\left(\frac{1}{k_i}\underset{j=1}{\overset{k_i}{\Sigma }}{(D_{i,j}-M_i)}^2\right)}^{\frac{1}{2}}$

式中U为覆盖均匀性指标，即距离标准差值指标，k_opt为骨干节点总数目，k_i为第i个骨 干节点的邻居节点个数，D_i，j为第i个骨干节点与第j个骨干节点之间的距离，M_i表示第i个 骨干节点与邻居骨干节点距离的平均值。

22)邻居节点的选取，根据节点覆盖最优模型以及最优骨干节点数量可得到骨干节点之 间的最佳距离为为了保证网络覆盖率，选取距离第i个骨干节点为 (0，Ropt±2(Rs-Ropt/2)]的节点为该骨干节点的邻居节点，R_s为骨干节点的感知距离。

3)用于解决骨干节点分布不均，平衡网络覆盖率和覆盖均匀性的改进PSO覆盖能效优化 算法：

31)优化目标是满足网络覆盖率最大化及覆盖均匀性最大化，即网络覆盖率最大化、距 离标准差值最小化，由此可得到最小化目标函数为：f(X)＝C^-(1-α)U^α，式中C和U分别为节点 集N所对应网络部署状态的网络覆盖率和网络覆盖均匀性指标，α为权重系数，用于调节优 化中两项指标的权重，以适应无线传感器网络不同的约束条件。

32)初始化微粒群，根据各个微粒的位置信息，在节点集N中搜索距离各个微粒中骨干 节点最近的节点，并作为初始微粒群集X。

33)根据节点覆盖最优模型，获得监测区域内理想骨干节点部署信息L，根据下式将骨 干节点进行迭代进化

$v_{\mathrm{ij}}^{k+1}={\mathrm{\omega v}}_{\mathrm{ij}}^k+c_1{r}_1(p_{\mathrm{ij}}^k-x_{\mathrm{ij}}^k)+c_2{r}_2(p_{\mathrm{gj}}^k-x_{\mathrm{ij}}^k)$

$x_{\mathrm{ij}}^{k+1}=x_{\mathrm{ij}}^k+v_{\mathrm{ij}}^{k+i},(V\max ⋐[\mathrm{Ropt}-2(\mathrm{Rs}-\mathrm{Ropt}/2),\mathrm{Ropt}+2(\mathrm{Rs}-\mathrm{Ropt}/2)\left]\right),$

每代进化完毕后获得具有最小适应度值的骨干节点集位置信息S，在S±2(Rs-Ropt/2)范围内 搜索是否满足节点集N，若满足则更新相应骨干节点位置信息，否则设置λ(S±L)为该节点下 次迭代的飞行方向。

本发明基于保证轮次簇能耗及覆盖能力的骨干节点数目优化算法；本发明在保证轮次簇 能耗最低的前提下，能够获取满足覆盖能力的骨干节点最优值，同时通过PSO动态调整节点 的飞行方向以及飞行速度，逐步迭代获取最优覆盖的骨干节点部署方案，既能有效地采集感 知区域的数据信息，又能够充分管理传感器网络资源，本发明有效地解决了无线传感器网络 应用中的骨干节点分布不均、骨干节点数目无法达到最优、网络能耗不均衡、网络覆盖能力 偏低等问题，为无线传感器网络在保证低能耗的前提下合理有效部署骨干节点以达到较高的 网络覆盖均匀性和网络覆盖率提供技术支撑，为在网络低能耗的前提下提高网络的区域覆盖 能力提供了一种全新的解决方案。

附图说明

图1是本发明所述的一种无线传感器网络低能耗覆盖优化算法的主流程图；

图2是本发明所述的一种无线传感器网络低能耗覆盖优化算法的详细流程图。

具体实施方式

下面结合附图和实施例对本发明进行详细描述。如图1、图2所示，本发明包括以下步 骤：

(1)节点采用随机密集部署方式；

(2)各个节点周期性上报能量信息、位置信息、节点ID等至汇聚节点。汇聚节点根据 步骤1)中本轮内的能耗及普通节点到骨干节点距离平方的数学期望值，能获得本轮内骨干 节点数目的最优值，即

$k_{\mathrm{opt}}=\left(\begin{array}{c}\frac{\sqrt[4]{27}\sqrt{N}M}{2\pi d_{\mathrm{toSink}}^2}\sqrt{\frac{{ϵ}_{\mathrm{fs}}}{{ϵ}_{\mathrm{mp}}}},d_{\mathrm{toSink}}\ge d_0\\ \frac{\sqrt[4]{27}}{2\pi d_{\mathrm{toSink}}^2},d_{\mathrm{toSink}}<d_0\end{array}\right);$

(3)初始化微粒群，根据各个微粒的位置信息，在节点集N中搜索距离各个微粒中骨干 节点最近的节点，并作为初始微粒群集X；

(4)汇聚节点根据网络覆盖模型以及微粒群信息，获得各个微粒的网络覆盖率，即

$C=\frac{{\int }_0^M{\int }_0^{M}p(x,y,X)\mathrm{dxdy}}{M\times M};$

(5)根据步骤2)获得各个微粒的网络覆盖均匀性指标；

(6)选取适应度值最小的微粒作为最优值，根据步骤33)中的PSO迭代公式将各个微粒 进行进化，

$v_{\mathrm{ij}}^{k+1}={\mathrm{\omega v}}_{\mathrm{ij}}^k+c_1{r}_1(p_{\mathrm{ij}}^k-x_{\mathrm{ij}}^k)+c_2{r}_2(p_{\mathrm{gj}}^k-x_{\mathrm{ij}}^k)$

$x_{\mathrm{ij}}^{k+1}=x_{\mathrm{ij}}^k+v_{\mathrm{ij}}^{k+1}$

其中c₁和c₂通常等于2；Vmax＝[Ropt-2(Rs-Ropt/2),Ropt+2(Rs-Ropt/2)]；r₁和r₂为[0，1]区间内 均匀分布的随机数；

(7)每代进化完毕后获得具有最小适应度值的骨干节点集位置信息S，在S±2(Rs-Ropt/2) 范围内搜索是否满足节点集N，若满足则更新相应骨干节点位置信息，否则设置λ(S±L)为该 节点下次迭代的飞行方向；

(8)满足最大迭代次数后，获取具有最优适应度值的微粒，并得到骨干节点的最优部署 方案；

(9)汇聚节点广播骨干节点的信息，则相应的骨干节点声明为簇首，并发出广播信息至 可交互数据的普通节点，至此网络拓扑结构形成。

以上所述，仅为本发明的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本 技术领域的技术人员在本发明公开的范围内，能够轻易想到的变化或替换，都应涵盖在本发 明权利要求的保护范围内。