嵌套细菌觅食优化算法在无线传感器网络中的研究*

邹汪平

(池州职业技术学院 安徽 池州 247100)



嵌套细菌觅食优化算法在无线传感器网络中的研究*

邹汪平

(池州职业技术学院 安徽 池州 247100)

为优化无线传感器网络节点配置，探索了基于细菌觅食优化算法的传感器节点配置方法.以二维目标监测区域内既定数目的传感器节点总覆盖率作为评价函数，以三种操作相嵌套的细菌觅食优化算法对实际问题进行优化.通过计算机仿真实验评价了该方法的可行性，同其他方法进行了比较，分析了原始参数对优化结果的影响.结果显示：嵌套细菌觅食优化算法有效提高了无线传感器网络的总覆盖率.

细菌觅食优化算法；传感器网络；覆盖率

引言

得益于科技的迅猛发展，生产生活中对信息化要求的不断提高，无线传感器网络得到了越来越多的应用.无线传感器网络依托智能传感器信息控制模块，通过现场总线将传感器节点并入控制器构成局域网络，通过无线网络实现复杂的总体分析和远程操控[1].覆盖率是评价无线传感器网络的一个重要指标，理想中的无线传感器节点部署应尽可能实现对整个监测区域物理空间的覆盖，同时保证节点不过分冗余.实际应用中，由于监测面积大，传感器节点分布具有随机性，有效覆盖率不能满足高要求.为了优化无线传感器网的实际覆盖率，传感器节点部署策略得到了广泛研究.燕山大学邓成玉等人提出了一种基于跳段校正的定位算法，在不同网络规模、不同网络连通度条件下均可以显著提高传感器网络节点的定位精度.黄亮等人提出了改进的蚁群算法对离散网监测局域的覆盖率进行优化[2].郑磊等人研究了微粒群改进算法，对监测区域的覆盖率进行优化并取得了一定的效果[3].

细菌觅食优化算法(BFOA)是Passino等人模仿大肠杆菌在动物肠道内摄取食物的行为而提出的一种计算方法，该计算方法的核心思想是模仿人类肠道中的大肠杆菌在觅食过程中表现出的智能特征，具有群体算法并行搜索、易跳出局部极小值等优点，是计算研究领域的新热点[4,5].

为提高无线传感器网络覆盖率，研究了基于细菌觅食优化算法的无线传感器网络部署策略，并以仿真实验验证了算法的可行性，分析了算法的初始参数对优化结果的影响.

1　细菌觅食优化算法与无线传感器网络的数学模型

1.1无线传感器网络节点的数学模型

为便于分析，选取二维平面作为目标监测区域，目标监测区域内暴露于网络节点监测范围内的区域为监测区，否则为盲区.以g(j)标识位于目标监测区域内的一个无线传感器节点，该节点的具体位置由坐标(xj,yj)确定，监测半径为r，节点间互联半径为R，实际应用中R≥2r.目标监测区域内某点q(i)的二维坐标为(xi,yi).二维平面内传感器节点g(j)到某点q(i)的距离为

(1)

目标检测区域内某点q(i)被某传感器节点g(j)监测到的概率为

(2)

进一步将目标监测区域设定为长宽分别为m和n的矩形区域，将目标监测区域平均分割成m×n个面积为1 m2的正方形网格，则整个目标监测区域将出现(m+1)×(n+1)个网格节点.设目标监测区域内传感器为a，在a个传感器共同监测下，某点q(i)暴露于监测区的概率为

(3)

a个传感器对整个目标监测区域的总覆盖率为

(4)

f客观反映了统计学角度下无线传感器网络对目标监测区域的覆盖率，因此选用f作为评价函数，对算法进行量化评价，f值越大部署策略越好.

1.2细菌觅食优化算法的数学模型

细菌觅食优化算法的实现过程主要依据三种机制：趋化、复制和驱散[6,7].

1)趋化：大肠杆菌的运动以翻转和游动为主.大肠杆菌时刻处于翻转运动状态，即等概率向不确定的方向移动一定距离.当翻转后所处位置的生存环境不变或者更差，细菌将继续进行翻转.当所处位置的生存环境得到改良，细菌不会立即终止运动.细菌终止运动的条件是连续运动后生存环境不发生改变，或者游动达到了既定的最大步长.细菌的趋化可表示为

(5)

式(5)中，θi(j+1,k,l)为第i个大肠杆菌的位置函数，θi(j+1,k,l)在是该细菌前一时刻的位置函数.细菌移动次数用k表示，复制次数用l表示，趋化次数用j表示；c(i)为细菌i的趋化步长；Δ是标识细菌下一步运动方向的单位向量.

2)复制：细菌总数保持不变，在任何一步趋化发生后，累计适应值较小的一半细菌将死亡，累计适应值较大的一半细菌将存活，并进行分裂，使细菌总数不发生变化.第i个大肠杆菌适应值累加和的计算公式为

(6)

式(6)中，J(i,j,k,l)为细菌i在第l次驱散、第k次复制、第j次趋化中的适应值.

3)若干次趋化复制后，细菌个体将随机分布在目标监测区域内，并呈现出统计学规律.为避免细菌过早收敛，迁徙范围设定为可行解的范围[8].

1.3基于细菌觅食优化算法的无线传感器网络部署策略

为将细菌觅食优化算法应用于无线传感器网络，研究过程均基于以下假设：

1)目标监测区域的网格划分不变，网格节点总覆盖率f为唯一评价函数；

2)每个细菌代表一个传感器节点，细菌在二维目标监测区域移动，细菌搜索半径为传感器节点监测半径；

3)细菌觅食算法参数及传感器节点参数在一次优化过程中不发生改变，传感器节点具有平等地位，传感器节点间双向通信，细菌适应值为携带传感器参数的细菌在当前位置所产生的覆盖率；

4)严格依照适应值的排序确定细菌的存亡，每个存活的细菌必须且只能进行一分为二的繁殖；

5)经过多次迭代后，新的细菌将按统计学规律分布.

为尽可能避免传感器节点监测范围出现重合，细菌趋向操作过程中引入回避机制，设细菌两两之间有排斥力和引力，距离超过一定值的两个细菌将互相吸引，距离小于一定值的两个细菌将彼此远离，细菌间的排斥和吸引作用可表示为：

2016年以来，谷城县资金使用管理逐步规范，建立健全了覆盖资金分配、拨付、使用、监管和绩效评价全过程的扶贫统筹资金管理制度体系。

sij=e-λDij

(7)

式(7)中sij表示两细菌反向移动距离，λ为敏感系数，即细菌对彼此之间距离的敏感程度，Dij为细菌i和细菌j之间的距离，λ和Dij共同决定了细菌反向移动距离.

当所有菌落的细菌的趋向运动结束时，细菌以菌落为单位进行复制操作，单个菌落适应值为

(8)

式(8)中，w为菌落内的细菌总数.

2　基于细菌觅食优化算法的无线传感器网络优化部署实验

2.1细菌觅食优化算法的实验结果及分析

实验选用Matlab软件，实验选取面积为900 m2的正方形平面作为目标监测区域.目标监测区域被划分为900个面积为1 m2的正方形网格，并形成961个网格节点.设传感器的监测区域半径r=3 m，通信距离R=6 m，在目标监测区域内随机分布40个传感器节点.

设置细菌觅食优化算法的细菌步长c为0.5 m，细菌“复制”操作次数Nre为5，迁徙操作概率为0.25，一次趋化操作中每只细菌移动距离上限Ned为2，一次迭代中，趋化操作次数Nc为50，敏感系数λ为0.05，单方向翻滚最大次数为15，覆盖率收敛时终止运算.实验重复操作10 次，以结果的平均值作为总覆盖率.选取部分实验结果如表1所示.

表1　基于细菌觅食优化算法的传感器节点部署实验结果

表1中，Dd表示每次操作的迭代次数，Cz表示实验组别.实验结果显示：设置合理的初始值，运算结果收敛，细菌觅食优化算法可以用于无线传感器网络的节点部署设计；所选取的五组实验结果中，当迭代次数为500时，总覆盖率值趋于稳定，算法有较好的收敛性；每组实验的细菌初始位置不同，优化结果会有微小差异，五组实验结果中，覆盖率最大值为0.941 2，覆盖率最小值为0.939 0，两者相差约0.13%，可以忽略不计.

无线传感器节点在若干次随机分配中所产生的最大覆盖率情形，如图1所示；基于细菌觅食优化算法的覆盖率情形，如图2所示.

图1　无线传感器网络初始覆盖示意图

图2　基于细菌觅食优化算法的无线传感器网络覆盖示意图

图中离散的点代表传感器位置.对比图1和图2，图2的节点分布更加分散，传感器监测重合的面积较少.其中图1中节点分布更加密集，传感器监测重合的面积较多.初始的传感器节点最优覆盖率约为0.7，通过细菌觅食优化算法得到的传感器覆盖率约为0.94.比较两种传感器节点部署方式，细菌觅食优化算法使覆盖率提高了约34%，有效实现了优化部署，基于细菌觅食优化算法的无线传感器网络部署策略是可行的.

2.3细菌觅食优化算法与两种常见算法的比较

为验证细菌觅食优化算法在无线传感器网络节点部署优化上的优势，设计了细菌觅食优化算法和遗传算法以及微粒群算法的对比实验.验证实验中三种算法的初始参数如下：

1)细菌觅食优化算法.细菌步长c为0.5 m，复制操作Nre为5，迁徙操作概率为0.25，步长Ned为2，Nc为50，敏感系数λ为0.05，单方向翻滚最大次数为15，覆盖率收敛时终止运算.

2)遗传算法.传感器的初始值为40，为保证遗传算法的高效性，Pc值和Pm值分别设为0.5和0.01，覆盖率收敛时终止运算.

3)微粒群算法.微粒个数为40，微粒的飞行速度为-3～3 m/s，参数C1= 0.9，C2=0.9，覆盖率收敛时终止运算.

每种算法迭代次数均为600，计算10次，对10次计算结果的覆盖率平均值进行比较.实验结果见表2.

表2　三种优化方法的对比实验结果

实验结果显示：初始状态相同，经过600次迭代运算，细菌觅食优化算法下的总覆盖率收敛于0.940 1，遗传算法下的总覆盖率收敛于0.861 2，微粒群算法下的总覆盖率收敛于0.821 1.通过细菌觅食优化算法得到的覆盖率分别比其他两种算法提高了9%和14%.在无线传感器网络节点优化部署问题上，细菌觅食优化算法更有优势.

2.4细菌觅食优化算法的初始参数对优化结果的影响

细菌觅食优化算法的无线传感器网络部署策略是基于数学模型实现的，通过对数学模型进行分析，算法实现过程中的参数设置会对优化结果有以下几点影响：

1)趋化次数的改变可以影响平均覆盖率和最高覆盖率.趋化次数越少，覆盖率平均值越高.趋化次数过多，将使运算速度减慢，同时会导致覆盖率平均值降低.

2)适当的迭代次数可以提高运算速度且不影响覆盖率值.迭代次数超过一定值，平均覆盖率几乎不变，但运算速度将大幅下降.

3)对目标检测区域进行网格划分时，采用了1m2作为最小网格，当缩小网格，即增加网格节点数量时，优化结果将进一步提高，但计算速度将减慢.优化过程中应针对不同参数传感器适当进行网格划分.

3　结论

细菌觅食优化算法可以有效应用于无线传感器网络节点部署，相比于传统的传感器网络节点部署策略，细菌觅食优化算法有更好的优化效果.适当选取目标检测区域的网格划分，可以有效改善细菌觅食优化算法的收敛速度.

[1]王晟. 无线传感网络节点定位与覆盖控制理论及技术研究[D]. 武汉：武汉理工大学， 2006.

[2]庞娜,程德福．基于Zig Bee无线传感器网络的温室监测系统设计[J]．吉林大学学报信息科学版，2010(1) : 55-60．

[3]黄亮. 基于改进蚁群算法的无线传感器节点部署[J]．计算机测量与控制，2010，18(9):2210-2221．

[4]郑磊,朱正礼,候迎坤．基于改进的微粒群算法的WSNs节点部署[J]．广西师范大学学报自然科学版，2011，29(4) :56-61．

[5]黄守志,赵学增等.基于网格划分的无线传感器网络节点冗余分析[J]. 东北石油大学学报,2013,37(3):113-122.

[6]Mishra S.A hybrid least square-fuzzy bacterial foraging strategy for harmonic estimation[J].I-EEE Trans On Evolutionary Computation,2005,9(1):61-73.

[7]刘丽萍,王智,孙优贤.无线传感器网络部署及其覆盖问题研究[J].电子与信息学,2006,28(9):1752-1757.

[8]戴秋萍,马良,郗莹.连续优化问题的细菌觅食改进算法[J]. 上海理工大学学报, 2013,35(2),103-107.

Research on Nested Bacterial Foraging Optimization Algorithm in Wireless Sensor Networks

ZOU Wang-ping

(Chizhou Vocational Technical College, Chizhou Anhui 247100, China)

In order to optimize the configuration of wireless sensor networks, the paper explores a sensor node configuration method based on bacterial foraging optimization algorithm. Taking the total coverage of determined number of sensor node rate in two-dimensional target monitoring area as evaluation function, actual problems are optimized by nested bacterial foraging optimization algorithm. The feasibility of this method was compared with others in experimental evaluation by computer simulation and the influence of the original parameters on the optimization results was researched. The results show that the nested bacterial foraging optimization algorithm can effectively improve the overall coverage of wireless sensor networks.

bacterial foraging optimization algorithm; wireless sensor networks; coverage rate

1673-2103(2016)02-0018-05

2016-02-24

安徽省2016年高校优秀青年人才支持计划重点项目(gxyqZD2016531)；安徽省2015年度省级质量工程项目(2015gxk113)；安徽省2014年度省级质量工程项目(2014jyxm524)

邹汪平(1982-)，男，安徽池州人，副教授，硕士，研究方向：智能算法应用.

TP18

A