一种基于人工鱼群算法的K覆盖WiFi热点安置方案

李钟翔， 陈 蕾

（华东师范大学计算机科学与技术系，上海 200241）

一种基于人工鱼群算法的K覆盖WiFi热点安置方案

李钟翔， 陈 蕾

（华东师范大学计算机科学与技术系，上海 200241）

针对室内定位导航、多路由选择等热门应用中对多次无线信号覆盖的需求，提出了一种基于改进的人工鱼群优化算法的K覆盖安置策略.其中特别设计出一种简单的障碍物干扰描述模型，以期更真实地刻画应用场景.仿真结果表明，我们的方法可在保证覆盖的前提下，明显节省A P数量同时改善节点的聚集.

K覆盖； 人工鱼群； WiFi

0 引 言

随着无线通信技术的进步和推广，通过无线信号进行定位已经成为重要的热门应用.全球定位系统（G PS）能够在户外提供较准确的实时定位方案，但某些特殊环境（如车库、商场、写字楼）中，其信号覆盖和定位精度却很难满足用户需求.室内定位有其特殊性：精度要求通常较高，墙壁等障碍物对信号强度影响较大；此外车库、电梯等环境无法使用卫星信号和蜂窝信号.在室内场景下，基于WiFi技术的定位方案，逐渐引起人们的重视.为实现无线定位，研究者们提出了不同算法.这些算法无一不以无线信号的足够覆盖为前提，因此确保无线覆盖就成为了定位系统中关键的一环.此外，覆盖问题还可以被应用到如多路径的路由选择等问题中去.一个高效的覆盖方案，不仅为我们提供较好的信号传输质量，还能在一定程度上节省资源降低，系统成本.在无线覆盖问题中，最基本的要求被称为“一次覆盖”，即对于所涉范围的任意位置，都要求至少有一个A P装置能够对其进行覆盖以保证通信，我们注意到一些固定的设计模式被用于解决覆盖问题［1］.然而由于实际应用中覆盖区域不规则，以及因为信号强度不稳定造成的单节点覆盖范围不稳定等原因，给这类设计思路带来了挑战.随机部署节点后通过移动节点达到优化区域覆盖成为不少学者关注的重点.在随机部署节点的前提下，对于如何移动节点以高效地实现一次覆盖，前人提出了不少算法，如Virtual Forces（V F）算法［2-3］，这是一种模仿力之间的相互作用来实现较好覆盖的方案.遗传算法、群智能优化算法等也被广泛用于对这个问题的研究和讨论［4-7］.本文的算法设计在此前提下基于群智能算法中的鱼群算法.

在很多情况下，一次覆盖并不能满足用户的全部需求.例如几类有代表性的定位算法：N N、K N N、三点定位法，都是以区域内任何一位置获取多个A P装置的信号强度和位置信息为前提，这就需要实现多次覆盖，即K覆盖.在K覆盖的要求下，前人提出了一些理想状态下的全覆盖的算法和一些设计模式.Jung-Eun Kim等人提出了一种在理想状态下2次和3次覆盖的高度优化算法，实现了区域内的全覆盖［9］，但这类算法要求在无障碍物干扰的场景下实施，且无法推广解决更高次数的覆盖问题.L A A C A D算法在场景受限的情况下，针对无线传感网设计的一种K覆盖算法，即通过执行K次一次覆盖叠加，从而实现K覆盖［9］；该算法会产生传感器节点的聚集.而H e等人提出，A P点的聚集通常会使相邻A P节点所提供的位置特征信息近似，造成资源的浪费；而且由于A P节点的信号波动，A P节点的聚集可能导致对待定位点位置的错误判断［6］.故而A P节点的分布应当尽可能均匀.

对于如何解决障碍物对覆盖造成的影响，Chang等人提出将区域围绕障碍物将空间分成几块区域分别进行覆盖［11］.W u等人提出在障碍物周围按适当距离围成一圈以解决覆盖［12］.这些算法选择忽略节点信号穿越障碍物后依然能覆盖到的部分来避免对障碍物带来的信号衰减进行量化.

针对上述问题，本文的工作主要围绕以下两方面展开：①对基本的人工鱼群算法进行了相应改进，同时加入一些启发式算法来实现有障碍物情况下的K覆盖.在保证覆盖的前提下尽可能节省A P节点的数量，并改善A P节点分布的聚集状况；②提出了一种简单易用的估计模型，对障碍物带来的影响进行了量化.

1 相关的说明

1.1 人工鱼群算法

人工鱼群算法是群智能优化算法中的一种，通过设计单个人工鱼实体的感知和行动机制来与环境交互，以解决优化问题，寻求近似最优解.人工鱼群算法的应用范围很广，W ang等人将其用于区域的一次覆盖，取得了不错效果［8］.

人工鱼群由大量人工鱼组成.人工鱼是一种真实鱼的虚拟实体，它一般包括以下几个基本属性：人工鱼的当前状态X，人工鱼的视距dvisual，人工鱼的步长dstep.针对覆盖问题，本文假设每个人工鱼代表一个A P节点，并根据A P节点的特性加入了人工鱼探测距离属性dcover，用于描述A P节点信号强度的覆盖范围.人工鱼的状态为其所在位置信息X（x，y）.得到人工鱼模型如图1所示：以dvisual为半径的圆描述了人工鱼的视野，描述觅食行为中，搜索食物的范围；以dcover为半径的圆描述了人工鱼的信号的覆盖面积；以dstep为半径的圆描述了人工鱼一次移动的范围.

对于某一条人工鱼，其所在的环境是指问题的解空间和其他人工鱼的状态.人工鱼对其所处的环境作出反应，进而改变环境，影响其他人工鱼.它对于环境的反应方式主要依靠以下几种基本行为：觅食、聚群、追尾、随机.在覆盖问题中，聚群行为的作用并不明显，故而在本模型中，我们将聚群行为并入到追尾行为.

1.1.1 觅食行为

记区域内某一点的食物量为Y，某一条人工鱼i在由dvisual构成的圆中搜寻状态优于自身所在点的位置food，并以dstep为界向其运动.对于food所在位置的查找可表示为

如果备选点的食物量Yfood＞Yi，则向其移动：

若备选点的食物量Yfood≤Yi，则执行随机行为.

1.1.2 追尾行为

在人工鱼群算法中，某一人工鱼与其他人工鱼不应相隔过远，以防止远离最优解；同时也不宜过于接近，以防止聚集在局部最优解处，而无法找到全局最优解.在覆盖问题中，相邻两个A P节点之间同样要保持合适的距离.如图2所示，对于一次覆盖问题，理想状态下两条鱼之间的距离为，此时场景内不存在3次覆盖的区域，是全覆盖情况下的最优解［3］.

现实场景中，由于地形和障碍物的影响无法达到上述理想情况.本模型的追尾行为，即是保持某一条人工鱼与相邻人工鱼之间的距离，以保证重复覆盖区域尽可能小的过程.

综上，人工鱼i对另一条人工鱼j进行追尾行为是

1.1.3 随机行为

该行为用于作为觅食行为和追尾行为的补充.即在没有找到更优良的食物点也不需要进行追尾行为时，人工鱼将选择一个随机的方向游动.随机行为看似随机，其实增加了它寻觅其他人工鱼和食物的范围.

对于人工鱼i有

1.2 覆盖率

本文假设信号感知模型是概率感知的：某一点A（xA，yA）和某条人工鱼Xi（xi，yi）间的距离为d，有A点被某条人工鱼Xi覆盖的概率为

其中Rp用于描述信号强度的不稳定造成的A P节点覆盖范围的波动系数，∂用于表述覆盖对距离的敏感度.当距离d＞（dcover-Rp）时，Xi对A点覆盖的概率为Pi，以描述信号不稳定带来的覆盖区域变化.A被覆盖的概率P为

本文将需要覆盖的区域用多个很小的网格进行划分.若一个网格的4个顶点都被同一个A P节点覆盖则认为该网格被覆盖.计算某一个顶点A被覆盖的概率P.设定一个阈值Pth，当P＞Pth时，认为A点被覆盖.记覆盖的网格数为c1，总网格数为c，保证覆盖率在f以上，即

2 K覆盖算法

2.1 改进的人工鱼群算法

本文先用少量的A P节点实现1次覆盖，然后重复K次，以实现K覆盖.在已覆盖N次的情况下，进行第N+1次覆盖（其中0≤N＜K）称为一次逻辑覆盖.

用人工鱼群算法实现一次逻辑覆盖时，本模型对基本的人工鱼群加以改进，以适应已存在N次覆盖时的环境：

首先，之前的N次覆盖中有一定区域达到了N+1次覆盖甚至更高次的覆盖，本模型对觅食行为进行修改，在找到的食物点A后先行判定其是否已达到N+1次覆盖，如果达到则中止行为，只有A点被少于N+1个A P节点覆盖，才进行原本的觅食行为.即在公式（1）找到食物点之后，除了判断是否满足条件Yfood＞Yi，还应该判断食物点覆盖层数是否小于N+1.只有满足这两个条件才执行公式（2）.

其次，要与前N次已安置好的A P节点保持一定距离以防止多个A P点聚集在某一个较小范围.本模型要求新加入A P点在尽可能远离前N次覆盖布置的A P点的前提下，与本层的A P点实施追尾行为，这样的过程称为“规避行为”.当然，随着迭代次数的增加，A P节点也将越来越密集，新安置A P点与前N次布置的A P点间的距离可能与N有关，故将这个距离定为.得到公式如下：若人工鱼i到前N次覆盖产生的人工鱼j之间的距离小于则有

迭代终止条件为第N+1次覆盖率达到V1，则判定完成了第N+1次覆盖.

此外，部分区域由于A P节点覆盖范围的重合，其覆盖次数也会高于N次.且随着覆盖次数N的增加，我们发现在进行第N次A P节点的布置之后，覆盖达到N+1次的区域也在逐渐增大，这时对人工鱼群的初始状态进行一些条件限制能够加快算法收敛.图3是进行了5次覆盖之后各点被覆盖的次数情况：白色区域被覆盖次数小于6次，是执行第6次覆盖时需要覆盖的区域；黑色区域被覆盖次数大于或等于6次，应当尽量避免再去覆盖以节省资源.从图中可以发现，白色区域分布比较分散，且大部分临近区域能被一个A P覆盖.因此在这种情况下，寻找当前情况下可覆盖白色区域面积最大的一个点作为人工鱼初始化的位置.在接下来的规避行为中，由于初始化阶段本模型选择的初始点已经是当前最优，故不再进行觅食行为.对大多数较靠近的白色区域，都可以通过一条人工鱼进行覆盖，所以同一层中，鱼与鱼之间的吸引和排斥关系都不再重要，故不再执行追尾行为，只执行规避行为.当第N次覆盖以后达到N+1次覆盖率为V2时，本模型采用上述方案实现第N+1次覆盖.

综上所述，有设计流程如图4所示.

在取得场景中某一点与某一人工鱼间的信号距离后，将其代入公式（5），来判断该点是否被该人工鱼覆盖.

3 实验仿真与实测用例

3.1 实验仿真

本次实验的仿真环境为Matlab7.1，计算机处理器是Intel（R）Core（T M）2 Duo C P U E P4400 2.00 G H z.取100×100大小，有一个障碍物的空间进行仿真.在程序的开始阶段每实现一次逻辑覆盖时，都将对30个人工鱼进行随机状态的初始化来进行计算.当层数增加到一定数量时，采用指定区域的方式初始化人工鱼的位置，即覆盖率已经超过阈值V2时，点数不固定，根据实际仿真的情况来看，每次增加的人工鱼将少于30个.我们使用的设置参数表如表1所示.（仿真中计drisual、dcover、dstep、Rp、r1、r2变量单位为1单位长）

本次仿真，记V1为99%作为接近100%迭代终止的阈值，该阈值可以根据实际应用的需求进行调整，文献3、文献5和文献8也采用了类似的方法［3，6，8］.对3次、5次、7次、8次、9次覆盖分别进行3次仿真实验之后取中间值，要使覆盖率超过99%至少需要的点数如表2所示.

以5次覆盖为例得到的效果图如图6所示，其中·代表的是障碍物.

图7显示了由基本鱼群算法实现5次覆盖的A P节点位置分布，图8示意了由本文中提出的改进算法得到的布局情况.

对比图7、图8，可以看出改进后的人工鱼群算法有相对均匀的部署结果，对A P点分布有显著的优化.

另外，优化后K次覆盖率达到99%使用的A P节点数也少于基本鱼群算法.两者的对比图如图9所示.

3.2 实测用例

针对一个小型地下车库场景进行了实验，过程是先用模拟手段进行安置规划，再通过实际设备测试进行验证.仿真实验使用了7个A P节点对区域实现了3次覆盖.主要参数如表3所示.场景中的节点安置方案如图10所示.

选取的A P节点为T P-LIN K的T L-M R10 U便携式3 G路由器，-75db m阈值时该设备的覆盖半径约20 m.采用手机软件WiFi分析仪进行信号强度测试.

实测结果显示：可以保证区域内位置有3个以上的A P节点的信号强度高于-75db m［13］，即在上述场景下，实测结果与仿真结果吻合，用例说明在上述场景下算法是正确的.

4 结 语

本文就如何实现高效的K覆盖对基于人工鱼群算法的改进和补充，建立了一个改进的K次覆盖人工鱼群算法的模型.保证了覆盖区域内99%的K覆盖率，降低了使用A P点的个数，同时也较好的解决了多层情况下A P点聚集的问题.仿真结果表明随着覆盖层数的增加，改进算法带来的节省A P节点的优势也越明显.

本文设计一种障碍物对A P节点覆盖范围影响的模型.该障碍物模型的设计还比较简单.实际应用中，可以通过获取大量的实测数据，并对其进行多项式拟合，以取得更好的效果.

［1］ BAI X，XUAN D，YUN Z，et al.Complete optimal deployment patterns for full-coverage and k-connectivity（k≤6）wireless sensor networks［C］//Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing.A C M，2008：401-410.

［2］ ZOU Y，CHAKRABARTY K.Sensor deployment and target localization based on virtual forces［C］//IN F O C O M 2003.Twenty-Second Annual Joint Conference of the IE E E Computer and Communications.IE E E Societies. IE E E，2003，2：1293-1303

［3］ YU X，HUANG W，LAN J，et al.A novel virtual force approach for node deployment in wireless sensor network［C］//Distributed Computing in Sensor Systems（D C O SS），2012 IE E E 8th International Conference on.IE E E，2012：359-363.

［4］ REDA S M，ABDELHAMID M，LATIFA O，et al.Efficient uncertainty-aware deployment algorithms for wireless sensor networks［C］//Wireless Communications and Networking Conference（W C N C），2012 IE E E.IE E E，2012：2163-2167.

［5］ NAVARRO M，DAVIS T W，LIANG Y，et al.A S W P：a long-term W S N deployment for environ mental monitoring［C］//Proceedings of the 12th international conference on Information processing in sensor networks.A C M，2013：351-352.

［6］ HE Y，MENG W X，MA L，et al.Rapid deployment of APs in W L A N indoor positioning system［C］//Proceedings of the 2011 6th International ICS T Conference on Communications and Networking in China.IE E E Computer Society，2011：268-273.

［7］ WANG G，GUO L，DUAN H，et al.Dynamic deployment of wireless sensor networks by biogeography based optimization algorithm［J］.Journal of Sensor and Actuator Networks，2012，1（2）：86-96.

［8］ WANG Y Y，LIAO H M，H U H Y.Wireless sensor network deployment using an optimized artificial fish swarm algorithm［C］//Computer Science and Electronics Engineering（ICCSEE），2012 International Conference on. IE E E，2012，2：90-94.

［9］ KIM J E，HAN J，LEEC G.Optimal 3-coverage with minimum separation requirements for ubiquitous computing environments［J］.Mobile Networks and Applications，2009，14（5）：556-570.

［10］ LI F，LUO J，XIN S Q，et al.L A A C A D：Load balancing k-area coverage through autonomous deployment in wireless sensor networks［C］//Distributed Computing Systems（ICDCS），2012 IE E E 32nd International Conference on.IE E E，2012：566-575.

［11］ CHANG C Y，CHEN Y C，CHANG H R.Obstacle-resistant deployment algorithms for wireless sensor networks［J］.Vehicular Technology，IEEE Transactions on，2009，58（6）：2925-2941.

［12］ WU C H，LEE K C，CHUANG Y C.A Delaunay triangulation based method for wireless sensor network deployment［J］.Computer Communications，2007，30（14）：2744-2752.

［13］ PATRO A，GOVINDAN S，BANERJEE S.Observing ho me wireless experience through WiFi APs［C］//Proceedings of the 19th annual international conference on Mobile computing&networking.A C M，2013：339-350.

（责任编辑 李 艺）

K-coverage of WiFi signal node deployment based on AFSA

LI Zhong-xiang， C H E N Lei
（Department of Computer Science and Technology，East China Normal University，Shanghai 200241，China）

O n the requirement of multiple wireless coverage in so me hot applications like indoor positioning and navigation，multipath routing etc.，this paper presented aK-coverage placement scheme based on an improved Artificial Fish-S warm Algorithm（A FS A）.A simple obstacle interference describing model was also designed to make our simulation scenario closer to a real one.The simulative results showed that our method could obviously reduce the number of signal nodes and their aggregation on the premise of coverage.

K-coverage； A FS A； WiFi

T P393.17

A D OI：10.3969/j.issn.1000-5641.2015.01.019

1000-5641（2015）01-0151-10

2014-05

李钟翔，男，硕士研究生，研究方向为计算机网络.E-mail：51131201054@ecnu.cn.

陈蕾，女，副教授，研究生导师，研究方向为计算机网络.E-mail：lchen@cs.ecnu.edu.cn.