基于惯性权重蛙跳算法的WSN布局优化

滕志军，张晓旭

(东北电力大学 信息工程学院，吉林 吉林 132012)

基于惯性权重蛙跳算法的WSN布局优化

滕志军，张晓旭

(东北电力大学 信息工程学院，吉林 吉林 132012)

摘要：针对传统混合蛙跳算法(Shuffled Frog Leaping Algorithm，SFLA)易陷入局部极值的问题，在青蛙最差个体的更新策略中引入反正切惯性权重加以修正，从而使该算法具有更强的全局搜索能力及局部搜索能力。将提出的改进型蛙跳算法应用到WSN(Wireless Sensor Network，WSN)覆盖优化问题中，通过理论数据分析及仿真结果证明，改进的蛙跳算法较传统的SFLA、PS0、WIS-SFLA对网络覆盖率有较大的提升，是一种较优的覆盖优化方法。

关键词：混合蛙跳算法；覆盖优化；无线传感器网络；布局

无线传感器网络节点的合理部署能够有效提升网络覆盖率，降低网络能耗，延长网络生存周期，是实现无线传感器网络优化的核心问题[1-3]。混合蛙跳算法(Shuffled Frog Leaping Algorithm，SFLA)是由Lansey及Eusuff于2003年提出的一种基于全局协同搜索的群智能优化算法[4]。本文提出了一种基于混合蛙跳算法的无线传感器网络覆盖策略，并通过在青蛙个体的状态更新过程中引入反正切函数惯性权重来解决传统混合蛙跳算法的“早熟收敛”问题，改进后的蛙跳算法能够实现无线传感器网络的合理化布局，有效提高无线传感器网络的覆盖率。

1改进的蛙跳算法

1.1　基本蛙跳算法

混合蛙跳算法[5-7]是结合了基于遗传行为的模因算法及基于社会行为的粒子群算法的优点，通过模拟青蛙觅食过程而提出的一种新型仿生智能算法。其基本原理为：在D维搜索空间下，随机初始化M只具有相同特性结构的青蛙，将每只青蛙的位置视为优化空间中的一个可行解。第i只青蛙在t时刻下的位置为：Xi(t)=(xi1(t)，xi2(t)，…，xiD(t))，计算出每只青蛙的适应度函数值F(Xi)，并依据适应度函数值的好坏将M只青蛙降序排列，将其划分为Q个子群，子群规模为S，其中M，Q，S满足关系式M=Q×S。分组规则为：第1只分配到第1个子群，第2只分配到第2个子群，直到第Q只分配到第Q个子群，然后将第S+1只分配到第1个种群，依次类推，直到将全部青蛙分配完毕为止。在t时刻下，对于每个子群，具有最优适应度的青蛙个体记为Pb(t)=[pb1(t)，pb2(t)，…，pbD(t)]T，具有最差适应度的青蛙个体记为Pw(t)=[pw1(t)，pw2(t)，…，pwD(t)]T，具有全局最优适应度的青蛙个体记为Pg(t)=[pg1(t)，pg2(t)，…，pgD(t)]T。然后在每个子群中进行局部深度搜索，对每个子群中的Pw(t)在(t+1)时刻的位置通过如下更新策略获得：

Disi(t+1)=rand()·(Pb(t)-Pw(t))，

(1)

每次进行更新后，若Pw(t+1)较Pw(t)更优，则用Pw(t+1)替换原子群中的最差解。否则，用Pg(t)替换Pb(t)按下式进行移动步长计算：

Disi(t+1)=rand()·(Pg(t)-Pw(t))，

(2)

重新按对Pw(t)行更新。若仍未改进，则需在定义域内随机产生一个新解替换原子群内的Pw(t)。重复执行以上更新操作直到满足预设的迭代次数即完成一轮各子群的局部深度搜索。然后对各子群的全部青蛙重新进行混合、排序及划分子群，继续执行局部深度搜索，如此反复至达到预设的结束条件为止。

1.2　蛙跳算法的改进

为解决传统的混合蛙跳算法在寻优过程中存在的“早熟收敛”问题，借鉴粒子群算法的更新策略[8]，将反正切函数惯性权重w引入混合蛙跳算法步长更新策略中以实现蛙跳算法在寻优过程中局部深度搜索与全局信息交换的平衡，提高算法“跳出局部极值”的能力。

改进后具体的更新策略如下：

newDisi(t+1)=w·rand()·(Pb(t)-Pw(t))，

(3)

Pw(t+1)=Pw(t)+newDisi(t+1)，

(4)

(5)

其中：ws，we取值是0.9和0.4，分别为惯性权重因子的初始值及结束值。ts为子群内当前迭代次数，tm为当前混合迭代次数。tmmax为子群内迭代次数的最大值，tsmax为混合迭代次数最大值。λ是控制因子，取值区间为[0.4，0.7]，适当调整λ有利于加快算法的收敛速度。

2WSN节点部署方案

2.1　模型描述

假定在一个大小为A×B的二维平面监测区域T内，随机部署M个传感器节点，所有传感器节点均为同构节点。通过传感器节点位置的移动，扩大无线传感器网络覆盖面积以实现无线传感器网络覆盖率的最大化。Ni表示无线传感器网络中的第i个节点，将该网络的传感器节点集表示为N={N1，N2，…，NM}，每个传感器节点的位置记作ci=(xi，yi)，节点的感知半径及通信半径分别为R和2R。将区域T离散化为a×b个像素点，像素点pj位置记为pj=(aj，bj)其中j=1，2，…，a×b。

本文采用文献[1，8]中布尔感知模型来计算无线传感器网络的覆盖率。在无线传感器网络中任意像素点pj被传感器节点ci检测到的概率可通过下式进行计算：

(6)

(7)

无线传感器网络的覆盖率可表示为被覆盖的像素点之和与像素点总数之比，如下式：

(8)

公式(8)即为本文中无线传感器网络节点部署优化方案中的优化对象。

2.2　基于改进SLFA的部署策略描述

在无线传感器网络中应用改进后的SFLA，公式(8)将作为该算法的适应度函数。算法具体实现过程如表1所示。

表1　基于改进SFLA的部署策略描述

3实验结果分析

本文无线传感器网络的监测区域设置为100 m×100 m的正方形区域，将其划分为大小相等、面积为1 m2的100×100个像素点。在监测区域内布置25个感知半径R=10 m，通信半径为2R=20 m的传感器节点且全部传感器节点均为同构节点。为了验证本文中WSN节点部署策略的有效性，在相同实验条件下，将分别与采用SFLA算法、基于线性惯性权重的蛙跳算法对无线传感器网络覆盖优化方案求解的结果进行比较。其中，图1为传感器节点均匀分布时所达到的理论最优值，此时节点所覆盖的面积为监测区域的78.5%。图2为使用SFLA算法对覆盖优化方案进行求解的效果图。其覆盖率为60.7%，是理论最优值的77.4%。

图1 最优方案节点覆盖图图2 基于SFLA的节点覆盖图

图3为使用权重改进的蛙跳算法[9](Weight Improved Shuffled frog Algorithm，WIS-SLFA)算法对覆盖优化方案进行求解的效果图，其覆盖率为66.2%是理论最优值的84.3%。图4为本文中改进的蛙跳算法(Arctangent Function Weight Shuffled Frog Leaping Algorithm，ASFLA)求解无线传感器网络覆盖优化方案的效果图，其覆盖率为70.3%，是理论最优值的89.5 %。

通过对比发现，本文所提出的ASFLA算法具有更强的寻优能力，寻优结果明显优于采用SFLA算法及WIS-SLFA算法的覆盖优化方案，具有更高的覆盖率，节点的分布更均匀，覆盖率可达89.5%。

图3 基于WIS-SFLA的节点覆盖图图4 基于ASFLA的节点覆盖图

4结论

无线传感器的优化覆盖是无线传感器网络的关键问题之一。本文提出了一种基于改进的混合蛙跳算法的无线传感器网络覆盖优化方案。在传统蛙跳算法中引入反正切函数惯性权重，使其克服了在寻优过程中的“早熟收敛”等问题。实验结果表明，相同实验条件下，本文中的节点部署方案可以获得更为理想的网络覆盖率，但该方案并没有将无线传感器网络的能耗考虑进去，能耗问题将成为下一步的研究方向。

参考文献

[1]Kimberley W.Lighter weight leads to fuel savings[J].Automotive engineer，2004，29(9)：30-31.

[2]Chang J H，Tassiulas L.Energy conserving routing in wireless ad-hoc networks[J].Proceedings of IEEE INFOCOM，2000,1：22-24.

[3]王震宇.基于WSN会聚点部署及捆塞控制策略[J].东北电力大学学报，2009,29(1)：81-83.

[4]Eusuff MM，Lansey KE.Optimization of water distribution network design using the shuffled frog leaping algorithm[J].Journal of Water Resources Planning and Management.2003，129(3)：210-25.

[5]Niknam T，Azad Farsani E.A hybrid self-adaptive particle swarm optimization and modified shuffled frog leaping algorithm for distribution feeder reconfiguration[J].Engineering Applications of Artificial Intelligence,2010,23(8)：1340-1349.

[6]Amiri B，Fathian M，Maroosi A.Application of shuffled frog-leaping algorithm on clustering[J]..The International Journal of Advanced Manufacturing Technology，2009，45(1/2)：199-209.

[7]刘洪涛，肖广明，刘俊涛.基于粒子群优化灰色模型的电力系统负荷预测[J].东北电力大学学报，2009,29(2)：69-72.

[8]李莉，牛奔.粒子群优化算法[M].北京：冶金工业出版社，2010：52-55.

[9]刘悦婷.权重改进的蛙跳算法优化PID参数[J].工业仪表与自动化装置，2014，(2)：7-10.

The Layout Optimization of WSN Based on Inertia Weight Shuffled Frog Leaping Algorithm

TENG Zhi-jun，ZHANG Xiao-xu

(Department of Information Engineering，Northeast Dianli University，Jilin Jilin 132012)

Abstract：To solve basic shuffled frog leaping algorithm(SFLA)’s easiness of trapping into local optional solution，an improved shuffled frog leaping algorithm based on arc tangent function was proposed.The local search capability and the global search capability of the advanced algorithm is enhanced efficiently.The advanced algorithm is applied to optimal coverage problem of wireless sensor network(WSN) to find a better solution.The theoretical analysis and simulation result show this algorithom can improve network coverage effectively compared with PSO、SFLA、and WIS-SFLA.

Key words：SFLA；Coverage optimization；WSN；Layout

中图分类号：TN99

文献标识码：A

文章编号：1005-2992(2015)06-0066-04

作者简介：滕志军(1973-)，男，吉林省吉林市人，东北电力大学信息工程学院教授，博士，主要研究方向：无线通信技术.

收稿日期：2015-09-12