基于文化蚁群算法的无线传感器网络节点部署设计方法

摘要

本发明涉及一种基于文化蚁群算法的无线传感器网络节点部署设计方法,该算法将蚁群优化算法纳入文化算法的框架，采用基于蚁群优化算法的种群空间和信念空间的双层进化结构进行寻优，在群体空间中加入信息素更新策略、禁忌表以及针对节点稀疏情况加入贪婪策略等，从整体上加快算法的寻优速度、提高解的质量。本发明旨在讨论在保证覆盖率与连通性的条件下优化网络中节点的数目。

说明书

 

技术领域

本发明涉及一种无线传感器网络节点部署的方法，特别地，涉及一种基于文化蚁群算法的无线传感器网络节点部署的设计算法。

背景技术

无线传感器网络逐渐在条件恶劣和无人坚守的环境监测和事件跟踪中显示了很大的应用价值。一方面，制造成本低廉的传感器在技术和经济上已经成为可行；另一方面，无线传感器网络技术如能量功耗、节点定位以及路由协议等技术变得越来越成熟。因此，部署由成千上万个传感器节点组成的大规模、自组织无线传感器网络已成为现实。节点部署问题最早可追溯到O’Rourke提出的艺术走廊和Williams提出的圆周覆盖这两个经典的计算几何问题。这两个几何问题对于无线传感器网络节点部署问题有着重要的参考意义。

无线传感器网络节点部署问题的即在一定的区域内，通过适当的策略布置传感器节点以满足某种特定的需求。通常在部署传感器节点时需要满足无线传感器网络的覆盖度和连通性约束。本文中提出的文化—蚂蚁系统算法同时考虑了这两种约束条件,并且在不同环境和不同参数条件下算法都表现出了较强的稳定性和良好的性能。另外，在设计部署策略时优化节点数目和节点分布形式，高效利用有限的传感器网络资源，最大程度的降低网络能耗均是节点部署时应注意的问题，本发明旨在讨论在保证覆盖率与连通性的条件下优化网络中节点的数目。

发明内容

本发明要解决的技术问题是：利用基本蚁群算法设计的节点部署算法，由于基本蚁群算法本身的缺点：收敛速度慢、搜索时间较长、易于陷入停滞出现早熟等现象，导致节点部署算法寻优时间长、易于陷入局部最优、部署结果不稳定等不足。因此针对这些不足之处，提出一种基于文化蚁群算法的无线传感器网络节点部署设计算法。在借鉴了现有的对蚁群算法的研究成果的基础上，用文化框架和蚁群算法对无线传感器节点部署问题进行更好的解决。

本发明公开的基于文化蚁群算法的无线传感器网络节点部署算法，主要是针对基本蚁群算法的不足添加了文化算法以及对基本蚁群算法提出相应的改进措施，从而提高蚁群算法的寻优速率与效率。与基于蚁群算法的无线传感器网络节点部署算法相比，主要由以下几个方面的差别：

（1）文化算法的引入。文化算法中包含两个独立又相互影响的进化空间：信念空间和群体空间，其中文化算法的整体进化机制是群体空间采用一定的进化策略将得到的精英个体传递给信念空间，而信念空间中进化的精英个体又会影响群体空间的进化，这种反馈式的进化机制在一定程度上大大加快进化速度，并且算法寻优效果会明显变好。这一点恰好解决了现有算法中寻优速度慢、寻优结果差等问题。

（2）贪婪策略。这一改进策略主要针对的是无线传感器网络中目标点放置较为稀疏的情况。在这种情况下，现有的节点部署算法的部署结果较差，并且随着目标点的增加呈现出不规则的变化。加入此贪婪策略使得算法部署结果整体上呈现出有规律的变化趋势，且在目标点稀疏情况下具有较优的结果。

（3）收敛判定策略。此策略重点解决现有算法的不稳定性等问题，一方面实现了算法快速收敛保证算法每次寻优的稳定性相同，另一方面使得算法避免误判而较快的得到最优解。 

为实现上述目的，本发明公开了如下的技术方案：

一种基于文化蚁群算法的无线传感器网络节点部署设计方法，其特征在于，包括以下步骤：

（1）种群空间设计；

（2）信念空间维护；

（3）收敛判定算法。

其中所述的步骤（1）包括以下步骤：

（2.A），启发式信息的计算，在蚂蚁个体的转移概率公式中，除蚂蚁系统中的信息素浓度                                                外，还有表示先验效应的启发式信息；

（2.B），维护蚂蚁的禁忌表与工作空间信息更新，蚂蚁个体在搜索的过程中维护一个禁忌表，用以避免重复地转移到同位置；禁忌表初始为空，蚂蚁做出转移选择后，在向指定位置将传感器加入传感器网络的同时，需要更新禁忌表，即将新增传感器节点的位置加入禁忌表，随后更新覆盖点集与有效待选点集；

（2.C），蚁群算法中蚂蚁个体在其经过的地方释放信息素，但是信息素会随着时间和环境的变化而蒸发，则工作空间中点j上的信息素更新公式为： 其中，ρ 表示信息素的蒸发系数，而 表示蚂蚁经过某网格点后在该点上留下的信息素的增量；而 起到一个引导的作用，其定义如下：

  ，其中，Q是一个常数,它表示蚂蚁所留轨迹数量，变量senserUsed用来表示蚂蚁k本次迭代使用传感器的数量。

所述的步骤（2）包括以下步骤：

（3.A），信念空间的初始化，当一代种群生成后，文化算法会按照规则对其执行接受函数或影响函数：执行接受函数时，种群中的优秀个体会进入文化算法的信念空间；执行影响函数时，信念空间中的若干优秀个体会替换掉当前种群中的较差个体。

（3.B），接收函数，接受函数主要用来传递群体空间中比较得到的精英蚂蚁个体到信念空间。本发明采取定期更新的策略，即在群体空间的演化过程中，规定每当蚁群优化算法运行AcceptStep的倍数代时，选取种群空间中全局最优的个体替换信念空间中最差个体。这里AcceptStep取值为2。

（3.C），影响函数，影响函数是指上层信念空间在完成精英解集的迭代更新后，反馈给下层群体空间以指导其后续的进化方向，对影响种群的时机采用动态策略，通过设定一个动态变化的变量InfluenceStep，信念空间中种群每运行InfluenceStep的倍数代时，将信念空间中适应值较好的一定数目个体，替换群体空间中适应值较劣的同样数目个体，InfluenceStep由下面的公式表示：

 ，其中，N₁、N₂为常数，iter_max表示算法的最大迭代次数；CurrentStep为当前群体空间进化代数。这里N1、N2取值分别为2和5。

所述的步骤（3）包括以下步骤：

（4.A），计算信念空间中的各个蚂蚁个体适应度值的方差σ，即计算信念空间中每个个体对应的无线传感器网络中所需传感器节点数量的方差，若该σ小于一标准值，则进行计数，执行步骤2；

（4.B），若在后面接受函数执行过程中仍然有σ<则计数器i累加1，执行步骤3；否则结束计数过程计数器清零，返回步骤1；

（4.C），若计数器i大于一个设定好的常数值I，表示算法收敛，一个适当的I值可以在算法早期有效规避误判使用一种新型的基于文化蚁群算法的无线传感器网络节点部署设计算法， 对无线传感器节点部署问题进行更好的解决。

本发明更加详细的方法如下：

（1）蚂蚁个体的转移规则

蚂蚁系统中的蚂蚁个体在一步步构建解时，会对下一步的转移规则按一定概率进行选择。蚂蚁对转移规则的选择如下表示。

位于节点i的蚂蚁k，根据以下规则选择节点j：

     ，其中r～U(0,1)，∈[0,1]，由用户制定具体参数值；J∈(t)是根据以下概率随机选择的节点：

      ，其中，(t)是可选节点集合。上式中，代表从节点i移动到节点j的后验效应，在节点部署问题中，表示当前候选点集合中候选点上的信息素浓度；代表从节点i移动到节点j的先验效应，通过启发式信息计算得出，节点部署问题中代表某一候选点附近监测点的个数。

    与 表示“信息素”影响和启发式信息两者的相对系数。按照蚁群算法的理论，与表示了以往经验数据和本次独立搜索之间的相对重要程度。

（2）启发式信息的计算

在蚂蚁个体的转移概率公式中，除蚂蚁系统中的信息素浓度外，还有表示先验效应的启发式信息，该启发式信息的计算方式如下:

     蚂蚁个体在选择下一步转移节点时判断工作空间中的有效点集合(W->E)是否为空，若为空，则在覆盖点集合中搜索转移目标，计算时置为“1”，若不为空，则在有效点集合中搜索转移目标，置为该节点所覆盖到的监测点的个数。

（3）监测点稀疏情况下的贪婪策略

工作空间

基于网格的网络模型构建的用于运行算法的空间区域（即网格）。

监测点

工作空间中需要被传感器节点覆盖到的、位于网格线相交位置的节点。监测点集合用一个二元组C(M,H)表示,其中M表示所有监测点的集合，H表示M中已被覆盖的监测点的集合，即覆盖监测点集。

若在散布在工作空间中的监测点较为稀疏，在蚂蚁个体转移时可能出现有效待选点集合E为空的情况，此时无法计算启发式信息，本文采用了贪心策略使得算法能尽快找到新的有效点。

点到网络的距离

工作空间中的一点到传感其网络中各传感器距离的最小值称为点到网络的距离。

主要算法步骤如下：

首先，计算工作空间的覆盖点集A中各个点到当前网络的距离；

第二步，找到与当前网络距离最大的覆盖点集A；

第三步，选取信息素浓度最大的点作为下一步转移的目标点。

（4）维护蚂蚁的禁忌表与工作空间信息更新

有效点

该点是在工作空间已形成的网络通讯范围内的点，若在其上放置一个传感器后该传感器至少覆盖到一个之前未被覆盖到的监测点，则该点为有效待选点。

蚂蚁个体在搜索的过程中维护一个禁忌表，用以避免重复地转移到同位置。禁忌表初始为空，蚂蚁做出转移选择后，在向指定位置将传感器加入传感器网络的同时，需要更新禁忌表。首先，蚂蚁将新增传感器节点的位置加入禁忌表，随后蚂蚁更新工作空间中的覆盖点集合与有效点集合。随着新节点的加入，覆盖点集合不断增加，而有效点集合变化较复杂，新节点可能会导致旧的有效点失效，同时可能带来若干新的有效点。

（5）蚂蚁系统的信息素更新策略

蚁群算法中蚂蚁个体在其经过的地方释放信息素，但是信息素会随着时间和环境的变化而蒸发，则工作空间中点j上的信息素更新公式为：

 ，其中，ρ 表示信息素的蒸发系数， 表示蚂蚁经过某网格点后在该点上留下的信息素的增量。从而可以看出好的网格点上的信息素会慢慢增加，相反不好的网格点上信息素会减少至消失，因此会吸引后来的蚂蚁沿着好的网格点继续搜索更优的解，因此 起到一个引导的作用。  ，其中，Q是一个常数,它表示蚂蚁所留轨迹数量。变量senserUsed用来表示蚂蚁k本次迭代使用传感器的数量。

     为了避免在信息素更新过程中信息素浓度值无限制的累加，本算法中加入了对信息素浓度的限制，以避免过早收敛。这样做既可以限制高信息素浓度点对蚂蚁个体的吸引能力，又可以保证信息素浓度低的点对蚂蚁的吸引不会过小。信息素更新限制如下式所示：

 ，其中，使用变量表示网格点的信息素浓度，pher_MIN和pher_MAX表示信息素的最小值和最大值。

（6）信念空间的初始化

信念空间中的个体是通过接受群体空间中较优的个体得到的，信念空间将这些个体与原有的个体根据一定的规则进行比较优化，并更新信念空间的经验知识，从而引导群体空间蚂蚁个体的进化方向，以提高群体空间的进化效率。

当一代种群生成后，文化算法会按照规则对其执行接受函数或影响函数。执行接受函数时，种群中的优秀个体会进入文化算法的信念空间；执行影响函数时，信念空间中的若干优秀个体会替换掉当前种群中的较差个体。

经过若干代，通常是种群中的优良个体趋于相似即算法收敛，或算法到达最大代数，则停止继续产生新一代种群，并输出得到的最优解。

本文算法中，用一个List列表作为文化算法的信念空间，将列表实体化即完成了对信念空间的初始化工作。信念空间与群体空间相对独立存在，然而信念空间要比群体空间生命周期长，因为本文算法的输出是从信念空间中取最优解得到的。

（7）接收函数

     接受函数主要用来传递群体空间中比较得到的精英蚂蚁个体到信念空间。这里我们采取定期更新的策略，即在群体空间的演化过程中，规定每当蚁群优化算法运行AcceptStep的倍数代时，选取种群空间中全局最优的个体替换信念空间中最差个体。这里AcceptStep取值为2。

（8）影响函数

     影响函数是指上层信念空间在完成精英解集的迭代更新后，反馈给下层群体空间以指导其后续的进化方向。本发明采取动态选择影响时机的策略，使得信念空间对群体空间的影响随着演化代数的增加而增大。动态选择影响时机的策略具体实现：通过设定一个动态变化的变量，信念空间中种群每运行代时，将信念空间群体中适应值较好的一定数目个体，替换群体空间中适应值较劣的同样数目个体。InfluenceStep的值通过下式计算得到： ，其中，N1、N2为常数，为预先设定的算法最大演化代数；CurrentStep为当前群体空间进化代数。这里N1、N2取值分别为2和5。

（9）收敛判定算法

信念空间中的个体周期性的更新，使得这一列表代表了群体空间中最近出现的最优个体，本文算法就是对信念空间进行分析，来判定算法收敛。算法每次在接收函数执行完毕后，紧跟着执行该判定算法。算法描述如下：

首先，计算信念空间中的各个体评价值的方差σ，即计算信念空间中无线网络所用节点数量的方差。若该σ小于一标准值，则开始计数过程，执行第二步。

第二步，若在后面接受函数执行过程中仍然有σ<则计数器i累加1，执行第三步；否则结束计数过程计数器清零，返回第一步。

第三步，若计数器i大于一个设定好的常数值I，则置flag为false，表示算法收敛。

（10）构建传感器网络的树形拓扑

     本文要解决的问题是对无线传感器网络的初始化部署，算法的输出是一个网络，网络本身由节点集和边集组成，故在蚂蚁个体组织解时，采用相应的路由选择机制，建立起一个树状的网络。路由选择算法在蚂蚁个体执行过转移操作后执行，算法描述如下：

首先，扫描以新增结点为圆心，以节点通信半径为半径的区域，若该区域存在其他节点，记这些节点的集合为V执行步骤2，若该区域无其他节点，则算法出错；

第二步，在V中寻找距离新增结点最近的结点，若有唯一最近节点，则在新增节点与最近结点间建立一条边，否则执行步骤3；

第三步，在最近结点集中寻找树状网络中的非叶子节点，若找到，则在新增节点与最近结点间建立一条边，否则随机与最近节点集中的一个结点间建立一条边。

基于文化蚁群算法的无线传感器网络节点部署算法与现有技术相比所具有的积极效果在于：

（1）算法部署的传感器数量随着监测点数量的增加稳步递增，且解的质量优于现有算法的部署结果。在目标点稀疏的情况下部署效果更明显。

（2）现有算法搜索得到最优解所需的平均迭代次数均明显高于此算法，所以此算法在给定的条件下能够更快速的搜索得到最优解。

（3）此算法中蚁群算法可以更快速的搜索到全局最优解，同时进一步提高了算法的稳定性。

 

附图说明

图1 是本发明文化蚁群算法基本框架图；

图2 是本发明工作空间图；

图3是有效待选点集E图；

图4是R=48实验效果图；

图5是R=72实验效果图；

图6 是R=96实验效果图。

具体实施方式

下面结合实施例进一步描述本发明。本发明的范围不受这些实施例的限制，本发明的范围在权利要求书中提出。

实施例1

基于文化蚁群算法的无线传感器网络节点部署设计系统，包括：

（1）种群空间设计；

（2）信念空间维护；

（3）收敛判定算法。

所述的步骤（1）包括以下步骤：

（2.A），启发式信息的计算，在蚂蚁个体的转移概率公式中，除蚂蚁系统中的信息素浓度外，还有表示先验效应的启发式信息；

（2.B），维护蚂蚁的禁忌表与工作空间信息更新，蚂蚁个体在搜索的过程中维护一个禁忌表，用以避免重复地转移到同位置；禁忌表初始为空，蚂蚁做出转移选择后，在向指定位置将传感器加入传感器网络的同时，需要更新禁忌表，即将新增传感器节点的位置加入禁忌表，随后更新覆盖点集与有效待选点集；

（2.C），蚁群算法中蚂蚁个体在其经过的地方释放信息素，但是信息素会随着时间和环境的变化而蒸发，则工作空间中点j上的信息素更新公式为： ，其中，ρ 表示信息素的蒸发系数，而 表示蚂蚁经过某网格点后在该点上留下的信息素的增量；而 起到一个引导的作用，其定义如下：

  ，其中，Q是一个常数,它表示蚂蚁所留轨迹数量，变量senserUsed用来表示蚂蚁k本次迭代使用传感器的数量。

所述的步骤（2）包括以下步骤：

（3.A），信念空间的初始化，当一代种群生成后，文化算法会按照规则对其执行接受函数或影响函数：执行接受函数时，种群中的优秀个体会进入文化算法的信念空间；执行影响函数时，信念空间中的若干优秀个体会替换掉当前种群中的较差个体。

（3.B），接收函数，接受函数主要用来传递群体空间中比较得到的精英蚂蚁个体到信念空间。本发明采取定期更新的策略，即在群体空间的演化过程中，规定每当蚁群优化算法运行AcceptStep的倍数代时，选取种群空间中全局最优的个体替换信念空间中最差个体。这里AcceptStep取值为2。

（3.C），影响函数，影响函数是指上层信念空间在完成精英解集的迭代更新后，反馈给下层群体空间以指导其后续的进化方向，对影响种群的时机采用动态策略，通过设定一个动态变化的变量InfluenceStep，信念空间中种群每运行InfluenceStep的倍数代时，将信念空间中适应值较好的一定数目个体，替换群体空间中适应值较劣的同样数目个体，InfluenceStep由下面的公式表示：

，其中，N₁、N₂为常数，iter_max表示算法的最大迭代次数；CurrentStep为当前群体空间进化代数。这里N1、N2取值分别为2和5。

所述的步骤（3）包括以下步骤：

（4.A），计算信念空间中的各个蚂蚁个体适应度值的方差σ，即计算信念空间中每个个体对应的无线传感器网络中所需传感器节点数量的方差，若该σ小于一标准值，则进行计数，执行步骤2；

（4.B），若在后面接受函数执行过程中仍然有σ<则计数器i累加1，执行步骤3；否则结束计数过程计数器清零，返回步骤1；

（4.C），若计数器i大于一个设定好的常数值I，表示算法收敛，一个适当的I值可以在算法早期有效规避误判。

实施例2

（1）关键参数设置

为了验证CA-ACA算法的可行性和有效性，选择已有的典型的基于蚁群算法求解无线传感器节点部署问题的Easidesign算法和ACO-TCAT进行对比。本算法采用Java进行仿真，设定网格大小为24，网格规模20*20，采用伪随机的方式产生监测点。

（2）基于文化蚁群算法的无线传感器网络节点部署设计算法

设计节点部署算法的一个重要目标就是针对合理的网络需求得到符合条件的最优部署方案，并且算法要有较强的寻优能力。这里设定传感器通信半径分别为R=48,72,96。将这三种算法（CA-ACA，Easidesign，ACO_TCAT）对应不同通信半径R各自运行20次后，得到的平均数据统计结果。

实验结果中图4、图5、图6分别展示了在传感器感知半径=传感器通信半径=48、72、96的情况下，传感器部署数量与工作空间中监测点数量的关系。横轴表示监测点的数目，纵轴为相应算法搜索到的节点部署所需的平均传感器节点数目。可以看到在三种情况下，CA-ACA部署的传感器数量都随着监测点数量的增加稳步递增，且解的质量优于ACO-TCAT，更优于Easidesign。在监测点稀疏（如监测点数量小于等于80）情况下，Easidesign因没有较适应的机制导致了在监测点稀疏环境下无法得到有价值的解，图5中ACO-TCAT的解与CA-ACA也有明显的差距。而CA-ACA中针对稀疏情况加入了贪婪策略，使得其解要优于其他两种算法。而对于监测点稠密情况，随着监测点数目的增加，三种算法之间差距较小但CA-ACA相对较优。综上所述，在监测点稀疏和稠密的情况下，CA-ACA能够很好地进行传感器节点数目的寻优。

实施例3

在本发明的一个应用实例，如城市中对某些易燃区域的监测中，与常规方法对比其应用效果为：

常规方法：基于基本蚁群算法的无线传感器网络节点部署算法

本发明的方法：基于文化蚁群算法的无线传感器网络节点部署算法

表1

目标点文化蚁群基本蚁群405497806376120667216069702007373

表2

结论：

（1）如表1和表2所示，在不同环境和不同参数条件下算法都表现出了较强的稳定性和良好的性能。

（2）在设计部署策略时优化了节点数目和节点分布形式，高效的利用了有限的传感器网络资源，最大程度的降低了部署代价，如表1所示，本发明方法比常规方法所需的部署代价要小很多，且数据呈现稳定性增长。

（3）本发明实现了在保证覆盖率与连通性的条件下优化了网络中节点的数目。