基于能量有效的分层协作覆盖模型的节点部署方法

摘要

本发明公开了一种基于能量有效的分层协作覆盖模型的节点部署方法，属于无线传感器网络技术领域。具体方法是：(1)建立目标区域的覆盖模型，通过对目标区域进行分层来达到节省能耗的目的；(2)求解启发式因子，使得在用蚁群算法求解该模型时，收敛速度大大加快；(3)求解节点数量上下限，使得在用蚁群算法求解该模型时迭代次数减少；(4)选取节点的位置部署策略；(5)利用蚁群算法求解分层协作覆盖模型的最优解。有益效果是本发明能满足具有特定区域形状的区域的节点部署。

说明书

技术领域

本发明涉及一种基于能量有效的分层协作覆盖模型的节点部署方法；属于无 线传感器网络技术领域。

背景技术

无线传感器网络是一种智能无线传感节点构成的计算机系统，它的出现扩展 了人类移动感知自然界的能力，改变了人们管理家庭、工厂和环境的方式。无线 传感器网络以其部署灵活，成本低廉的特点在军事侦察、交通监管、智能工业控 制等领域得到了广泛的应用。

无线传感节点的特点包括：资源有限，网络覆盖范围大，节点密集，动态拓 扑。一般而言，对于某项测量任务，传感节点的布置数量都要超过其需要量。这 样做一方面可以弥补传感节点定位精度不高所导致的测量精度降低的问题；另一 方面也可以进一步提高系统容错性。但无线传感节点在尺寸、重量、能量和带宽 上都受到严格约束，这些将影响网络资源的可用性。因此，如何在消耗最小能量 的情况下同时保证网络覆盖范围是目前研究的热点。

网络覆盖是无线传感器网络对其目标监控区域探测性的一种度量，是无线传 感器网络研究内容中的一个重要问题。覆盖模型按照配置方式可分为确定性覆盖 和随机性覆盖。确定性覆盖的研究内容是目标区域的状态相对固定，根据预先配 置的节点位置确定网络拓扑结构或者根据需要设定子区域的节点密度。随机节点 覆盖的研究内容是在节点随机分布且节点位置未知的情况完成对目标区域的覆 盖。评价覆盖模型优劣的主要标准有网络对目标区域的覆盖程度、能量有效性、 算法的精确性和网络拓扑的健壮性。在无线传感器网络中，由于节点能量受限， 实际应用环境复杂而且多数情况下不允许对节点电池进行更换，因此最大限度延 长节点的使用寿命和网络生存时间成为无线传感器网络中重要的研究内容。

常用的传统覆盖模型有布尔模型、一般覆盖模型、协作覆盖模型和概率覆盖 模型等。布尔模型较为简单，但不能表达传感器的探测能力随距离增加而减小的 特点；而一般覆盖模型则仅仅考虑了单个传感器的覆盖能力；协作覆盖模型和概 率覆盖模型虽然考虑到了多个传感器对覆盖的贡献，但是未从节点能耗的角度进 行研究。

在保证传感网络对目标区域具有一定覆盖能力的情况下，减少节点能量消耗 的主要手段有在节点数目确定的情况下优化网络拓扑，在节点冗余部署的情况下 进行休眠调度，优化节点数目和节点位置，优化sink节点的位置等。目前针对 无线传感网络中能量有效的覆盖研究多集中在前两个领域。K.Shashi Prab等人 提出了一种分布式六边形覆盖算法，该算法通过选择最优化的邻居节点来实现能 量有效的网络覆盖。Paul Sounak等人提出了同构节点网络环境下的动态能量均 衡休眠调度策略，该算法通过节点剩余能量等三个因子来确定节点的休眠来达到 节省能量的目的，但是该算法不支持多跳网络。Costa等人提出了拓扑感知节点 拒绝的多路径选择算法，该算法通过考察节点和覆盖能力并通过多路径选择来平 衡节点能耗，通过这种选择算法可以延长网络的生存时间。Martins等人则提出 了解决有节点失效的情况下，区域覆盖的动态恢复，提出了能量有效的动态覆盖 算法MGoDA。基于贪婪法的最小覆盖集近似算法可以在线性时间计算出最小覆 盖集，即用最少的节点覆盖目标区域，从而让更多的节点进入休眠调度，达到节 省节点能耗的目的。以上算法都是从前两个角度来分析和优化网络结点能耗。在 多跳网络中，多数节点需要通过中继节点进行路由转发才能将数据发送到sink 节点，中继节点除了要发送自身监测数据还需转发其它节点的监测数据，节点能 量损耗较快。因此，在网络中处于不同位置的节点能量的损耗速度不尽相同。如 果中继节点死亡过快，普通节点的监控数据无法通过中继节点进行转发，网络就 无法提供正常的服务，而普通节点的能量未能得到充分利用。而在很多应用中， 许多位置重要的节点因为部署难度较大，应首先保证这些节点的能量得到充分利 用，如在战场数据监测中的前线节点，煤矿信息监测中的矿井底部节点等等。因 此仅仅考虑覆盖率而忽视因节点位置不同而造成能量损耗模型会使某些位置的 节点较快的死亡，从而降低整个网络的生存时间。因此在节点部署时需要在不同 位置，不同区域布设不同密度的节点，以达到能量均衡，延长网络生存时间的目 的。

2001年Seapahn等人建立了协作覆盖模型(CCM)，通过定义某一点的覆盖 指标来反映网络在该点的覆盖情况。覆盖指标定义为：

$I(p,K)=\underset{k=1}{\overset{K}{\Sigma }}S(p,s_k)---\left(1\right)$

其中

2007年杨等人在协作覆盖模型的基础上指出，在保证区域被完全覆盖的条 件下，最优的节点分布是：任意三点构成一个等边三角形，三角形的边长为(R 为节点的最大通讯半径)，所有节点成蜂窝状覆盖目标区域。如图1所示，区域 S被14个节点成蜂窝状覆盖。

协作覆盖模型仅仅从覆盖区域的角度考察节点对目标区域的覆盖度，而没有 加入对节点的能量损耗的分析。在多跳网络中，离sink节点相对较近的节点除 了要发送自身监控数据外还需要转发离sink节点较远的节点的数据，在发送数 据量相同的情况下，能量损耗相对较快。在单跳网络中，离sink节点较远的节 点发送数据损失的能量相对较多。因此，网络的覆盖不应当仅仅考虑覆盖面积， 还要考虑不同位置，不同层次的节点的能量损耗。

发明内容

本发明的目的在于提供一种基于能量有效的分层协作覆盖模型的节点部署 方法，实现在满足覆盖要求的情况下使得节点的能量消耗最少。

本发明采取以下技术方案实现：一种基于能量有效的分层协作覆盖模型的节 点部署方法，包括以下步骤：

1)建立目标区域的覆盖模型，该模型通过对目标区域进行分层来达到节省 能耗的目的。

2)求解启发式因子，使得在用蚁群算法求解该模型时，收敛速度大大加快。

3)求解节点数量上下限，使得在用蚁群算法求解该模型时，迭代次数减少。

4)选取节点的位置部署策略。

5)利用蚁群算法求解分层协作覆盖模型的最优解。

所述步骤1具体包括以下步骤：

11.绘制出目标区域的图纸，并计算目标区域的面积。

12.根据覆盖度要求和目标区域的大小，选取层次划分粒度。

13.建立目标区域的分层协作覆盖模型。

所述步骤3具体为：首先建立模型的目标函数，该目标函数是使得分层后的 生存时间最小的层的生存时间最大。其次要建立该模型的约束条件：一、每层节 点数量之和等于总的节点数量。二、每层节点的覆盖率要大于要求的覆盖率。

所述步骤5具体包括以下步骤：

51.初始化算法中使用的参数，包括总结点的数目N，节点的初始能量，节 点的最大通信半径.在蚁群算法中，蚂蚁的数目，边ij上的信息素量τ_ij初始为0， 信息素的相对重要程度α，启发式因子的相对重要程度β，启发式因子η_ij中的常 数M＝1，W＝1，蚁环常数Q＝10。

52.开始最外层迭代，对于每只蚂蚁，将当前节点加入禁忌表。

53.计算启发式因子。

54.通过信息素和启发式因子计算每条边上的转移概率，并选取下一节点。

55.选取节点位置部署策略。

56.执行多跳路由算法，计算网络生存时间。

57.进行信息素更新。

所述步骤55具体为：根据覆盖区域的面积除以节点个数得到每个正六边形的 面积大小，从而得到边长和中心位置。每个传感器节点就放置在正六边形的中心， 这个边长小于等于一般覆盖模型的正六边形的边长。

本发明提供的基于能量有效的分层协作覆盖模型，它充分考虑的节点位置的 分布对于网络生存时间的影响，通过对目标区域进行分层优化实现了在满足覆盖 要求的情况下，网络的生存时间最大化。通过蚁群算法来求解该模型可以达到快 速收敛，避免全局最优的情况。本发明能满足具有特定区域形状的区域的节点部 署。

以下结合附图及实施例进一步说明本发明。

附图说明

图1是本发明采用的分层协作覆盖模型的示意图。

图2是本发明采用的蚁群算法的转换方法。

具体实施方式

如图1所示，本发明在具体实施时，首先要建立目标区域的覆盖模型。能量 有效的分层协作覆盖模型Energy Efficient Hierarchical Collaboration Coverage Model(EEHCCM)，就是在一定约束条件下求解网络生存时间的最大值。该模型 的目标函数为：

${}^T\mathrm{Sur}=\underset{i=\mathrm{1,2}L}{\min }{}_l{}^T\mathrm{Sur}_i---\left(3\right)$

约束条件为：

$\underset{i=1}{\overset{n}{\Sigma }}{b}_i=N---\left(4\right)$

N＞N′                                            (5)

S_monitor≥S_area                                   (6)

公式4的含义是每层节点的数目之和等于总结点数目，公式5和公式6是要 求节点的部署覆盖整个目标监控区域，其中S_monitor是节点覆盖区域的面积，S_area是目标区域的面积。EEHCC所解决的问题是在某一监测区域，总结点数量已知 的情况下，通过优化不同位置的节点密度来实现节点能量均衡，延长网络生存时 间。

模型建立完以后，对模型进行蚁群算法求解，在求解前设定该算法中用到的 参数和启发式因子的选取规则。EEHCCM的蚁群优化算法的启发式因子的选取 规则是：

若i＞j

若i＜j

其中：η_ij(k)表示从层i选择第k条边到层j的启发式因子，表示层i的最 优节点数量估计，M和W是任意正常数。

在每次迭代过程中，每层节点数量由于受到覆盖率的限制，因此存在一个上 下限，每层节点数量的下限为：

第l_i层节点数量的上限为：

由于EEHCC模型的求解是NP难度的，因此不存在多项式时间的求解算法。 在应用蚁群算法求解EEHCCM时需要对该问题进行转换，使输入参数类型满足 蚁群算法的形式。如果将层次划分的集合L看成是TSP问题中的城市的集合C， 而每层的节点数集合N看成是TSP问题中城市之间的距离集合D，则该问题转 化为一个多路径的类TSP问题。图2所示，图中的圆代表区域划分中的某一层， 对应于TSP问题中的城市，圆之间的弧线代表每层节点的数量n_l，对应于TSP 问题中城市间的距离d_ci，cj，网络生存时间T_k对应于路径长度L_k，选择第k条边从 层i转移到层j概率定义为a_ij(k)，该条边上的信息素浓度为τ_ij(k，τ)，k代表层i 中的节点数量，层i和层j之间第k条边上的启发式因子为η_ij(k)。算法执行时， 蚂蚁在各个层之间进行随机游走，通过转移概率确定转移，并更新路径上的信息 素，最终达到收敛。因此EEHCCM转化为在遍历图中每个圆的路径集合中搜索 使得网络生存时间最长的节点数量组合方式。

EEHCCM的蚁群求解算法模型可以表示为：

$a_{\mathrm{ij}}\left(k\right)=\frac{{\left[{\tau }_{\mathrm{ij}}\left(k\right)\right]}^{\alpha }{\left[{\eta }_{\mathrm{ij}}\left(k\right)\right]}^{\beta }}{\underset{l=1}{\overset{N}{\Sigma }}{\left[{\tau }_{\mathrm{ij}}\left(l\right)\right]}^{\alpha }{\left[{\eta }_{\mathrm{ij}}\left(l\right)\right]}^{\beta }}\forall i\ne j\in L---\left(11\right)$

τ_ij(τ，k)＝ρτ_ij(τ-l，k)+Δτ_ij                             (12)

${\mathrm{\Delta \tau }}_{\mathrm{ij}}\left(k\right)=\underset{a=1}{\overset{m}{\Sigma }}{\mathrm{\Delta \tau }}_{\mathrm{ij}}^a\left(k\right)---\left(13\right)$

算法执行前需要初始化算法中使用的参数，包括总结点的数目N，节点的初 始能量，节点的最大通信半径.在蚁群算法中，蚂蚁的数目，边ij上的信息素量 τ_ij初始为0，信息素的相对重要程度α，启发式因子的相对重要程度β，启发式 因子η_ij中的常数M＝1，W＝1，蚁环常数Q＝10

利用蚁群算法求解能量有效的分层协作模型的算法步骤如下：

算法经过若干次迭代以后，会收敛于最优解，该最优解指明了每层节点的最 优数量比例，确定了每层的节点数量后，需要指定节点的位置或者分布。本发明 采取的方式是根据覆盖区域的面积除以节点个数得到每个正六边形的面积大小， 从而得到边长和中心位置。每个传感器节点就放置在正六边形的中心，这个边长 小于等于一般覆盖模型的正六边形的边长。