基于细菌觅食优化算法的WSNs节点部署策略*

朱瑞金， 王联国

(1.甘肃农业大学 工学院，甘肃 兰州 730070；2.甘肃农业大学 信息科学技术学院，甘肃 兰州 730070)

0 引 言

利用无线传感器网络(WSNs)对草地进行监控是近些年农业生态领域对草地生态环境进行管理的一种手段，具有易部署、成本低、信息收集全面持续等特点。传感器节点的布置策略是监控网络的基础，只有合理的节点部署，才能得出准确的原数据。但是，通过随机抛撒等手段得出的数据具有很大的不确定性[1]，因此，很多学者利用智能优化算法对WSNs节点的部署策略进行了优化。例如:文献[2]利用改进的蚁群算法对离散成网监测局域的覆盖率进行优化，文献[3]提出一种改进的微粒群算法，以覆盖面积比为标准对监测区域的覆盖率进行优化，都取得了一定的效果。对具有普遍性的监测区域，通常以提高覆盖面积比例或覆盖的网格比例(网格比例指将监测区域离散成网格形式)为目标进行部署优化，从而尽可能减少盲区和重复覆盖面积[4,5]。

细菌觅食优化 (bacterial foraging optimization,BFO) 算法是由Passino K M在2002年基于大肠杆菌在在人体的觅食行为提出的一种全局启发算法[6]。该算法求解的过程中能够在区间内并行搜索并通过群体之间的信息互换实现群体智能性，在公交调度[7]、背包问题[8]、BP神经网络[9]等问题上的应用都取得良好的效果。

本文提出一种基于BFO算法，对草地的WSNs部署策略进行了应用性研究，仿真结果验证了该算法的可行性和有效性。

1 传感器节点的优化模型

本文传感器采用0/1的监测模型，将传感器的监测区域离散为[10]：监测区和盲区。例：假定传感器节点u(j)的二维坐标是(xj,yj),监测区半径为r，通信半径为R，通常假定R≥2r。监测目标点k(i)的二维坐标为(xi,yi)，那么两点之间的距离

(1)

对于监测点k(i)被此传感器u(j)监测到的概率为P(k(i),u(j))

(2)

假定监控草地区域是面积为m×n的区域A[11]，则区域A离散成m×n像素点，传感器只数为v，传感器的集合集为U，则对于像素点k(i)被传感器集合集U监控的概率为

(3)

从而对于整个监控区域的总覆盖率P为

(4)

这样得出的结果可以反映出监视草地区域具有普遍性的状况下的近似覆盖率。

2 BFO算法

BFO算法有[12～14]趋向行为、复制行为、迁徙行为等三种主要操作。

1)趋向操作：大肠细菌在觅食过程中同时通过旋转和游动来寻找附近食物较为丰富的区域，避开有毒区域。上述统称趋向行为，对于细菌i在趋向运动中的数学模型表示为

θi(j+1,k)=θi(j,k)+C(i)φ(i).

(5)

其中,j为趋向行为次数，k为迁徙行为次数，C(i)为步长，φ(i)为细菌i的随机方向的单位向量，且

(6)

2)复制操作：当整体细菌的趋向运动结束后，细菌进行优胜劣汰，健康值更好的细菌个数为Sr(Sr=S/2,其中,S为种群中细菌的个数)分裂为成2个细菌，健康值较差的 50 %细菌死亡，保持种群个数的不变，细菌i的健壮函数值为

(7)

式中Nc为最大趋向次数，k为第k复制次数，l为第l次迁徙，函数值越大细菌的健康程度越差。

3)在复制操作完成后，由于外部环境原因，细菌有一定的概率迁徙的其他随机的空间，迁徙范围设定为可行解的范围，从而避免细菌过早收敛。

3 基于BFO算法的WSNs节点部署优化

3.1 编码方案

菌落为监测区域的传感器集合，每个菌落由z个细菌组成，每个细菌代表一只传感器，细菌的搜索维度为2，分别为二维平面的x轴和y轴的值。菌落的适应度值代表监测区域内传感器集合的有效覆盖率。

菌落的细菌表示为P(z,b,i,j,k,l),其中，z为菌落里面细菌的编号，b为菌落里面单个细菌的维度，i为菌落的编号，j为趋向运动的次数，k为复制操作的次数，l为迁徙操作的次数。

3.2 BFO算法的三种操作的改动

1)趋向操作：趋向操作是以细菌为单位进行的，在细菌趋向操作开始时，引入碰壁策略，设定菌落内部细菌互相影响，当细菌i和细菌j距离接近一定范围，细菌i就会针对细菌j反方向，sij表示菌落内细菌i相对细菌j的反向运动距离

(8)

式中α为细菌对食物的敏感系数，(此问题中，α为单只传感器覆盖面积和整体覆盖面积决定的)。

随后菌落内的细菌做各自的趋向运动，运动步长一致，运动的单位向量各自独立随机产生

(9)

2)复制操作：当所有菌落的细菌的趋向运动结束时候，细菌以菌落为单位进行复制操作，其中菌落健壮函数值为

(10)

3)迁徙操作：迁徙操作同样以菌落为单位进行。

3.3 目标函数

目标函数为总体覆盖面积与整体面积的比例大小，覆盖面积越大越优越，故细菌觅食算法的适应度函数应该为

(11)

3.4 BFO算法流程

BFO算法流程如图1。

图1 BFO算法流程

4 仿真实验

本文在Matlab 7.6环境下进行仿真实验。假定需要检测的草地区域范围是20 m×20 m的矩形区域，草地的监测区域为二维平面。监测区域离散成m×n像素点，传感器的监测区域半径r=2.5 m,通信距离R=5 m,在区域随机分布25个传感器节点。

4.1 趋化操作对算法性能的影响

设置BFO的菌落个数为30，菌落内细菌个数为25，细菌的搜索维度p为2，细菌的步长c为0.1，碰壁系数α为0.05，复制操作Nre为10，迁徙操作Ned为2,在趋化操作为1，5，10,25,50情况下独立计算50次(BFO的迭代计算可以换算为Ned×Nre×Nc)得到的实验结果如表1所示。

表1 趋化操作的实验结果

由表1可以得出:适当增加趋化操作次数可以提高WSNs覆盖率的平均值，但是当趋化次数增大到一定的数值时，WSNs的覆盖率最高值趋于收敛，同时WSNs覆盖率的平均值有所下降。

4.2 复制操作对算法性能的影响

设置BFO的菌落个数为30，菌落内的细菌个数为25，搜索维度p为2，步长c为0.05，碰壁系数α为0.05，在Ned∶Nre∶Nc=2∶250∶1，Ned∶Nre∶Nc=2∶50∶5，Ned∶Nre∶Nc=2∶25∶10，Ned∶Nre∶Nc=2∶10∶25，Ned∶Nre∶Nc=2∶5∶50的比例下分别迭代计算，迭代次数为500次(BFO的迭代计算可以换算为Ned×Nre×Nc，3个嵌套的循环,总的迁徙次数为Ned,总的复制次数是Ned×Nre)计算50次得到实验结果如表2所示。

由表2可以得出:在迭代次数确定的情况下，适当增加复制次数，WSNs覆盖率的平均值、最高值都得到了提高，同时算法的收敛速度也得到提升。但是当复制次数过高的时，种群失去多样性，收敛速反而变慢。

表2 复制操作的实验结果

4.3 迁徙操作对算法性能的影响

设置BFO的菌落个数为30，菌落内细菌个数为25，搜索维度p为2，步长c为0.05，碰壁系数α为0.05，在Ned∶Nre∶Nc=2∶50∶5，Ned∶Nre∶Nc=4∶25∶5，Ned∶Nre∶Nc=10∶10∶5，Ned∶Nre∶Nc=20∶5∶5，Ned∶Nre∶Nc=25∶4∶5的比例下分别迭代计算，迭代次数为500次，计算50次得到实验结果如表3所示。

表3 迁徙操作的实验结果

由表3可以得出:在迭代次数相同的情况下，随着迁徙次数的提高，WSNs的平均覆盖率小幅度的增加,同时算法的收敛速度变慢。

4.4 仿真结果

为了验证BFO算法的有效性，将BFO部署结果与初始部署结果相比较。设置BFO算法的菌落个数为30，菌落内细菌个数为25，步长c为0.5，Nre∶Nc∶Ned=5∶50∶2,碰壁系数α为0.05，迁徙概率为0.25，单方向翻滚最大次数为10，计算次数约500次，运行50次，选取接近平均值的覆盖率。与初始的无线传感器覆盖率中最优值相比较，图2(a)为基于初始WSNs覆盖率最优值的节点部署情况，图2(b)为用BFO优化得到的WSNs节点部署情况，点代表传感器位置，圆形代表传感器覆盖区域。

图2 覆盖面积的对比

初始的WSNs节点最优覆盖率为71.75 %，通过BFO优化得到的传感器的收敛覆盖率为92.45 %。相比初始节点部署，通过BFO得到节点部署的覆盖率提高20.70 %，达到了优化的效果。从图2可以得知，比较图2(a)，(b)的节点分布的更均匀，重复覆盖的区域更少。其中图2(a)中出现了孤立的传感器节点或节点群(相互距离大于R)。通过上述分析得知，与初始的WSNs部署相比较，由BFO得到的WSNs部署具有较高覆盖率和较好的部署合理性，由此对比表明，基于BFO算法的WSNs部署策略是可行的。

为了进一步的验证BFO算法在WSNs节点部署的优化问题上的可行性，将遗传算法，微粒群算法和本文的算法(菌落个数为30，菌落内细菌个数为25，步长c为0.1，Nc数值为5，Nre数值为50,Ned数值为2，Nc×Ned×Nre的计算值为500，碰壁系数α为0.05，迁徙概率Ped为0.25，单个方向细菌翻滚的最大次数为10)进行对比，遗传算法采用文献[15]方法(种群规模的初始值为50,交叉概率Pc的初始值为0.05,变异概率Pm的初始值为0.01)，微粒群算法采用文献[3]方法(微粒个数为30，微粒的飞行速度为-3～3 m/s之间，参数C1=0.9,C2=0.9 )。三种方法迭代次数均为500，计算50次得到实验结果如表4所示。

表4 三种算法的优化结果

由表4可以得出,比较遗传算法和微粒群算法，BFO算法得到的传感器节点平均覆盖率分别提高了13.85 %和5.65 %，最优覆盖率分别提高了14.80 %和6.85 %，收敛速度也比遗传算法和微粒群算法快。可以看出:在解决WSNs覆盖率问题上，比之两种算法，BFO算法具有明显优势。

5 结 论

本文针对大规模草地区域监测中的传感器节点优化部署问题，提出一种基于BFO算法的节点部署策略，对仿真实验的数据和理论分析表明:这种策略是可行的。在实地草地监测中，等同于像素的监测点的密度并不是均匀分布的，在这种情况下求得WSNs的最优覆盖率分布，是下一步研究工作的重点。

参考文献:

[1] Yick J,Mukherjee B,Ghosal D.Wirless sensor networks sur-vey[J].Computer Network,2008,52(12):2292-2330.

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

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

[4] 曾映兰,陈 静,郑金华.基于遗传算法的WSNs覆盖优化方法[J].计算机工程与应用,2009,45(11):89-91.

[5] 龙 腾,孙 辉,赵 嘉.基于改进蛙跳算法的WSNs、移动节点的部署研究[J].计算机工程,2012,38(5):96-116.

[6] Kevin M P.Biomimicry of bacterial foraging for distributed optimization and control[J].IEEE Control Systems Magazine,2002,22(3):52-67.

[7] 刘 芹.差分进化细菌觅食算法求解公交车调度问题[J].交通运输系统与信息,2012,12(2):155-161.

[8] 戴秋萍,马 良,都 莹.求解0-1背包问题的细菌觅食算法[J].数学的实践与认识,2013,43(3):178-183.

[9] 麦雄发,李 玲,胡宝清.优化BP神经网络的快速细菌觅食算法[J].广西科学院学报,2011,27(3):221-223.

[10] 袁 浩.基于改进蜂群算法无线传感器感知节点部署优化[J].计算机应用研究,2010,27(7):2704-2708.

[11] 张云亚,纪志成.虚拟力导向多粒子群算法的WSNs部署策略[J].江南大学学报:自然科学版,2012,11(4):428-431.

[12] 周雅兰.细菌觅食优化算法的研究与应用[J].计算机工程与应用,2010,46(20):16-21.

[13] 梁艳春,吴春国,时小虎,著.群智能优化算法理论与应用[M].北京:科学出版社,2009．

[14] Das S,Dasgupta S,Biswas A,et al.Onstability of the chemotactic dynamicsin bacterial foraging optimization algorithm[J].IEEE Transactions on Systems,Man,and Cybernetics—Part A: Systems and Humans,2009,29(3):670-679.

[15] 殷卫莉,陈 巍.遗传算法在无线传感器网络覆盖中的仿真研究[J].计算机仿真,2010,27(10):120-123.