基于“能量均衡”的集群无线传感器网络非均匀分簇方法

摘要

一种基于能量均衡的集群无线传感器网络非均匀分簇方法，涉及无线通信技术。该方法将节点均匀分布的无线传感器网络监测区域划分为非均匀的环带，根据等效距离的方法确定簇头节点的位置，保证簇头节点与汇聚节点端到端通信的可靠性链接指数δp，建立簇头节点的能量消耗求解方程。在基于“能量均衡”的思想下采用最速梯度下降算法优化簇头节点的能消耗求解方程的参数，得到最优环半径向量。根据最优环半径向量调整簇头节点的位置和发射功率，最终确定簇的大小，从而平衡簇头节点之间的能量消耗，延长网络的生存周期。本发明显著延长了网络的生存周期，提高路由协议和媒体控制协议的效率，同时为时间同步、数据融合及目标定位技术提供支撑基础。

说明书

技术领域

本发明涉及无线通信技术领域，是一种解决大规模无线传感器网络“能量空洞”问题，并延长网络生存周期的非均匀分簇方法。

背景技术

无线传感器网络是由部署在监测环境内的大量微型传感器节点通过无线通信方式组成的一种自组织无线网络。构成传感器网络的节点通常包括汇聚节点和传感器节点。无线传感器网络在国防军事、环境监测、智能家居、建筑物状态监控、空间探索、医疗卫生、城市交通等领域的广泛应用使得无线传感器网络成为当前无线网络领域的一个热门研究方向。它的出现被视为信息感知和采集领域的一场革命。传感器节点是一个微型嵌入式系统，其处理能力、存储能力和通信能力相对较弱，通过携带能量有限的电池供电，并且在部署后难以再次补充能量。因此如何高效地使用传感器节点的能量，最大地延长网络的生存周期是传感器网络设计中所要考虑的首要问题。由于无线传感器网络中数据流以多对一(many-to-one)的模式进行传递，离汇聚节点较近的传感器节点需要承担更多的通信负载，因此这些节点能耗速度过快，导致在汇聚节点周围出现能量空洞。能量空洞的出现使网络原有覆盖区域缺失数据无法传递到汇聚节点，网络的生存周期提前结束，网络中大量的能量资源被浪费。

针对集群无线传感器网络中的能量空洞问题已经有一些应对机制提出。在多跳的网络中，能量空洞往往会在离汇聚节点近的区域形成。Lian J和NaikK教授提出在离汇聚节点较近的地方放置更多的传感器节点是一种能够缓解能量空洞问题的措施，这就是所谓的节点数量非均匀分布方法，但是这种方法网络中节点数目由外环到内环以等比增长，导致网络中的节点总数呈指数级增长。因此，只有当传感器节点能够以低成本大规模生产时，这种节点数量非均匀方法才有可行性。Mihail L.Sichitiu教授提出根据传感器节点距离基站的远近设置不同初始能量的能量非均匀分布的方法。能量非均匀分布方法从调整网络能量密度来解决能量空洞的问题，在基站附近能量密度较高从而能够承受大量的通信开销。存在的问题是在随机布置的环境中，节点的实际分布很难达到预先设定的分布。Luo J和Hubaux J P教授将动态性引入无线传感器网络中来解决能量空洞的问题。如果网络中汇聚节点的位置可以按照一定的方法移动的话，汇聚节点周围的节点随着时间不断变化，这样可以避免在汇聚节点周围形成能量空洞，消除节点能耗不平衡的状况。但是频繁移动汇聚节点会造成网络拓扑的频繁变化，使得路径发现的代价增加，提高了整个网络的功耗。同时改变汇聚节点位置受到实际条件的制约，在应用中存在着困难。

基于集群无线传感器网络的自组织、无线信道、节点功率可控等特点，使得对于其拓扑结构的优化控制得以施行。研究证明在无线传感器网络中通过分簇(clustering)拓扑控制建立网络层次结构，可以节省系统的能量，延长系统的生命周期，提高系统的性能，适用于大规模无线传感器网络。但存在的问题是基于分簇技术的无线传感器网络中，簇头节点(cluster head)不仅管理簇内数据同时也要融合并转发来自其他簇头节点的数据，簇头节点与汇聚节点之间多跳的通信方式导致距离汇聚节点较近的簇头节点能量消耗过快而失效，导致该簇的节点与网络中其他节点通信终端。簇头节点之间的能耗不均衡大大降低了传感器网络的生存周期。Heinzelman W教授提出的LEACH(low energy adaptive clustering hierarchy)算法通过等概率地随机循环选择簇头节点，将能量负载平均地分配到网络每个节点上。Younis O教授提出的HEED(hybrid energy-eficient distributed clustering)算法首先根据节点的剩余能量来概率性地选取一些候选簇头节点，然后以簇内部通信代价的高低来竞争产生最终簇头节点。LEACH和HEED都需要周期性的更新簇头节点形成新的簇，以使整个网络的能量达到平衡，存在成簇开销大、网络部署面积受限、扩展性较差等诸多不足。传统的分簇算法中簇头节点多采用单跳通信方式直接与汇聚节点通信，研究重点主要集中于均衡簇内成员节点之间的能量消耗，没有考虑到簇头节点之间的能量消耗均衡问题。

发明内容

本发明所要解决的技术问题是：针对现有技术中存在的上述缺陷，设计一种基于能量均衡(power-balancing)的非均匀分簇方法来解决大规模基于分簇技术的集群无线传感器网络中簇头节点之间由于多跳(hop-to-hop)的通信方式导致的靠近汇聚节点的簇头节点能量消耗速度过快耗尽而失效所产生的能量空洞问题，平衡簇头节点间的能量消耗，延长网络的生存周期。在本发明中无线传感器网络的生存周期被定义为网络中最早因电池能量耗尽而失效的节点的生存时间。

本发明解决上述问题的技术方案是：通过分簇拓扑控制将无线传感器网络建立成层次结构型网络，将节点均匀分布的无线传感器网络监测区域划分为非均匀的环带，根据等效距离的方法初始确定簇头节点的位置。综合考虑大规模集群无线传感器网络中簇内通信与簇间通信的相互作用，以保证簇头节点与汇聚节点端到端(end-to-end)通信的可靠性链接，建立簇头节点的能量消耗求解方程。通过数学分析将无线传感器网络中簇头节点能量消耗平衡，使簇头节点消耗最大功耗值最小并最大化网络生存周期的问题归纳为标准的符号优化问题。在基于“能量均衡”的思想下采用数值分析中的最速梯度下降算法优化簇头节点的能量消耗方程中的参数，得到环带的最优环半径向量。根据环半径向量解调整簇头节点的位置和发射功率，最终确定簇的大小。簇内节点以单跳的方式与簇头节点通信，簇头节点以多跳的方式与汇聚节点通信，环带内的簇头节点只能选择相邻上一环带内距离自己最近的簇头节点转发数据。

本发明具有如下优点：

(1)与传统的基于负载均衡(load-balancing)的启发式(heuristics)分簇方法不同，本发明通过数学分析给出了解决基于分簇技术的无线传感器网络中的簇头节点能量消耗不均衡问题的方法，将最大化网络生存周期问题归纳为标准的符号优化问题，为该问题的解决提供了很好的理论基础和求解方案。最速梯度下降算法对于求解最大化网络生存周期问题模型参数的优化具有很好的收敛性。

(2)本发明提出的基于能量均衡的非均匀分簇方法不仅有效地平衡了簇头节点间的能量消耗，而且保证了簇头节点与汇聚节点之间通信链路的可靠性连接。解决了传统的基于负载(load-balancing)均衡的分簇方法中距离汇聚节点较近的簇头节点能量消耗过快提前失效的问题，显著延长了网络的生存周期。

(3)本发明基于分簇技术的分层式拓扑结构不仅能提高路由协议和媒体控制协议的效率，而且与优化网络整体性能的存在着密切的联系，同时为时间同步、数据融合及目标定位技术提供支撑基础。

附图说明

图1为本发明的实现过程流程图

图2是采用本发明的基于能量均衡的无线传感器网络非均匀分簇拓扑结构图

图3是n＝2不同分簇方法无线传感器网络簇头节点剩余能量比仿真曲线图

图4是n＝4不同分簇方法无线传感器网络簇头节点剩余能量比仿真曲线图

图5是n＝2不同分簇方法无线传感器网络归一化生存周期仿真曲线图

图6是n＝4不同分簇方法无线传感器网络归一化生存周期仿真曲线图

具体实施方式

本发明通过分簇拓扑控制将无线传感器网络建立成层次结构型网络，将节点均匀分布的无线传感器网络监测区域划分为非均匀的环带，根据等效距离的方法初始确定簇头节点的位置。综合考虑大规模集群无线传感器网络中簇内通信与簇间通信的相互作用，保证簇头节点与汇聚节点端到端(end-to-end)通信的可靠性链接，建立簇头节点的能量消耗模型。通过数学分析将无线传感器网络中簇头节点能量消耗平衡，使簇头节点消耗最大功耗值最小并最大化网络生存周期的问题归纳为标准的符号优化问题。在基于“能量均衡”的思想下采用数值分析中的最速梯度下降算法优化簇头节点的能量消耗模型的参数，得到最优环半径向量。根据环半径向量调整簇头节点的位置和发射功率，最终确定簇的大小。本发明通过调整簇的大小和簇头节点位置平衡簇头节点之间的能量消耗，延长网络的生存周期。

以下针对附图和具体实例，对本发明的实施作具体说明。

图1所示为本发明的实现过程流程图：

1.网络结构初始化

通过分簇拓扑控制将无线传感器网络建立成层次结构型网络，将节点均匀分布的无线传感器网络监测区域划分为非均匀的环带并根据等效距离的原则初始确定簇头节点的位置。

初始化网络节点以密度ρ均匀地分布在半径为R的圆形监测区域S中，汇聚节点被置于圆心处；将圆形区域S划分为K+1个环带，沿监测区域中心至外围所有环带的半径分别记为R₀，R₁，R₂，...，R_k，环半径向量为r＝(r₁，r₂，L，r_K)^T；基于监测区域的对称性和节点分布的均匀性，位置落在R_i＝{(ρ，θ)|r_i-1<ρ≤r_i}环带内的节点被归类为i型簇；位于R₀＝{(ρ，θ)|0<ρ≤r₀}环带内的节点直接与汇聚节点进行通信，其中r₀<R；环带R_i内的簇头节点只能与内邻环带R_i-1内距离最近的簇头节点以单跳的方式进行通信；R₁，R₂，...，R_k-1环带内的簇头节点不仅要管理簇内节点，融合各节点数据并传输至下一跳节点，还要承担其他环带的数据中继任务，R_k环带内的节点则不需负担数据中继的责任。

2.簇头节点位置初始化

由于节点是均匀分布在对称的圆形监测区域内，因此簇头节点均匀地分布在C_i＝{(ρ，θ)|ρ＝d_i}的圆上，其中r_i-1<d_i≤r_i，1≤i≤K。

本发明通过等效距离的方法初始确定簇头节点的位置。将某个环带R_i内节点发送每比特数据至环带R_i-1内簇头节点所消耗的能量的平均值等效为位于簇头节点均匀分布的C_i＝{(ρ，θ)|ρ＝d_i}圆环上节点发送每比特数据至内邻环带R_i-1内簇头节点所消耗的能量，由此确定等效距离d_i的值。令x_i为R_i环内的簇头节点将数据传递到R_i-1环内簇头节点所需的平均距离：

$x_i=d_i-d_{i-1}=\frac{2{\int }_{r_{i-1}}^{r_i}(\rho -r_{i-1})\mathrm{\rho d\rho }}{r_i^2-r_{i-1}^2}=\frac{2(r_i^2+r_i{r}_{i-1}+r_{i-1}^2)}{3(r_i+r_{i-1})}-d_{i-1}---\left(1\right)$

$d_i=\frac{2(r_i^2+r_i{r}_{i-1}+r_{i-1}^2)}{3(r_i+r_{i-1})}---\left(2\right)$

3.建立信道模型以及簇头节点能量消耗求解方程

本发明综合考虑大规模集群无线传感器网络中簇内通信与簇间通信的相互作用，保证簇头节点与汇聚节点端到端(end-to-end)通信的可靠性链接，建立簇头节点的能量消耗模型。设置节点接收每比特数据所需的能量不小于预定的能量门限值τ，保证簇头节点与汇聚节点端到端(end-to-end)通信达到可靠性链接指数δp。

采用瑞利衰减模型描述簇头节点之间，簇头节点与汇聚节点之间的通信的信道模型，信道增益为$h\left(x\right)=L\left(d_0\right){\left(\frac{x}{d_0}\right)}^{-n}\zeta .$其中$L\left(d_0\right)=\frac{G_t{G}_r{l}^2}{16{\pi }^2{d}_0^2},$L(d₀)为路径损耗，G_t为发射天线增益，G_t接收天线增益，x为发射终端与接收终端之间的距离，n路径损耗指数，ζ为归一化的随机变量代表衰减功率增益，呈指数分布，P_r(ζ≤t)＝1-e^-t。

在集群无线传感器网络中，簇内节点以速率λbit/s产生数据并以单跳的方式将数据发送给簇头节点。簇头节点以速率μbit/s产生数据以多跳的方式通过其他簇头节点转发数据至汇聚节点。根据接收每比特数据电路所消耗的能量e_rx、发送每比特数据电路所消耗能量e_tx、发射功率函数E_Ti(λ_i+μ_i，Γ)确定环带R_i内簇头节点的能量消耗E_i：

E_i＝e_rx(λ_i+μ_i)+e_tx(λ_i+μ_i)+E_Ti(λ_i+μ_i，Γ)   (3)

其中发射功率函数E_Ti(λ_i+μ_i，Γ)与发送数据比特流和簇头节点的路由机制相关。在本发明中，簇头节点通过最短路径路由来转发数据，即R_i环带内的簇头节点只能选择内邻R_i-1环带内距离自己最近的簇头节点来转发数据。

E_Ti＝e_ti(λ_i+μ_i)     (4)

将公式(4)带入公式(3)可得R_i，环内簇头节点通信能量消耗：

E_i＝(λ_i+μ_i)(e_rx+e_tx+e_ti)    (5)

其中e_ti为簇头节点发射每比特数据所消耗的能量，则接收每比特数据所要消耗的能量$e_{\mathrm{ri}}=e_{\mathrm{ti}}L\left(d_0\right){\left(\frac{x}{d_0}\right)}^{-n}\zeta .$在最短路径路由下，端到端路径中最大链路数为K，为满足端到端链路的可靠性指数δp，e_ri必须不小于预定的能量门限值τ，δ_l为最短链路可靠性指数。因此发射每比特数据所需的最低能量e_ti如下式所示：

${\delta }_l={\delta }_p^{\frac{1}{K}}=\mathrm{Pr}(e_{\mathrm{ri}}\ge \tau )=\mathrm{Pr}\{\zeta \ge \frac{\tau }{e_{\mathrm{ti}}L\left(d_0\right)}{\left(\frac{x_i}{d_0}\right)}^n\}=e^{-\frac{\iota x_i^n}{e_{\mathrm{ti}}L\left(d_0\right)d_0^n}}---\left(6\right)$

$e_{\mathrm{ti}}=-\frac{\mathrm{K\tau }{x}_i^n}{L\left(d_0\right)d_0^n\ln {\delta }_p}---\left(7\right)$

其中$\left(\begin{array}{c}{x}_1=d_1=\frac{2(r_1^2+r_1{r}_0+r_0^2)}{3(r_1+r_0)}\\ x_i=d_i-d_{i-1}=\frac{2(r_i^2+r_i{r}_{i-1}+r_{i-1}^2)}{3(r_i+r_{i-1})}-\frac{2(r_{i-1}^2+r_{i-1}{r}_{i-2}+r_{i-2}^2)}{3(r_{i-1}+r_{i-2})}\end{array}\right)---\left(8\right)$

R_i环带内的总的数据流量为${\lambda }_{\mathrm{totali}}=\pi (R^2-r_{i-1}^2)\mathrm{\rho \lambda },$为便于在实际应用中简单易行，本发明取角幅度为的环扇为一个簇，且每个环带的分簇方法一致，则R_i环带内的簇头节点数为R_i环带内每个簇的平均数据流量为$\lambda +\mu =\frac{{\lambda }_{\mathrm{totali}}}{N}=\frac{\pi (R^2-r_{i-1}^2)\mathrm{\rho \lambda }}{N}.$由此可建立R_i环带内簇头节点能量消耗求解方程：

得到所有环带内簇头节点能量消耗求解方程，，求解方程获得最优环带半径向量。

4.建立最大化网络生存周期问题求解方程

由于簇头节点的初始能量相等，为了最大化地延长网络的生命周期，我们需要解决的问题是平衡各个簇头节点的能量消耗，并使簇头节点的最大能量消耗降到最低。为此，建立原始方程：

Minimize max{E₁，E₂...E_k}        (10)

本发明通过优化环半径向量r＝(r₁，r₂，L，r_K)^T，来调整簇头节点的位置和发射功率，确定簇的大小，以此平衡各个簇头节点的能量消耗，并使簇头节点的最大能量消耗降到最低。即得带约束条件的最大化网络生存周期问题求解方程：

$\left(\begin{array}{c}{\min }_{\{r_i,...,r_K\}}\left\{\max (E_1\left(r\right),...,E_K\left(r\right)\}\right\}\\ s.t\\ r_0<r_1<...<r_K=R\end{array}\right)---\left(11\right)$

5.根据簇头节点能量消耗求解方程迭代求解最优环半径向量

本发明采用数值分析中的最速梯度下降算法计算最优环半径解向量，通过步长因子系数和簇头节点的能量消耗函数的负梯度向量的分量迭代调整环半径向量，使得簇头节点的能量消耗函数收敛，求得最优环半径向量。其具体步骤如下：

(1)引入辅助变量t≥E_i(r)，其中1≤i≤K，将最大化网络生存周期问题

归纳为标准的符号优化问题(signomial optimal problem)：