【深度】多智能体优化技术+WLAN=？
【厚度】学术plus年终巨献：2017年 你不可以错过的重磅报告们！（全文阅读链接）
今日荐文的作者为武汉理工大学信息工程学院，奥克斯集团专家方丹丹，武汉理工大学信息工程学院宁波工程学院电子与信息工程学院专家郑悠，宁波工程学院 电子与信息工程学院专家徐小活，安鹏，袁红星。本篇节选自论文《多智能体优化技术在室内WLAN规划中的应用》，发表于《中国电子科学研究院学报》第13卷第4期。
摘 要：由于人们对无线通信的需求的增加以及通信质量的不断提升，无线局域网(Wireless Local Area Networks，WLAN)的接入点(Access Point，AP)部署问题在优化领域受到了越来越多的关注。目前，大量的文献都在研究WLAN规划问题，并提出了一系列优化技术。然而，这些技术的寻优能力在面对复杂的AP部署场景时就会下降。为了解决复杂的WLAN规划问题，本文在前人工作的基础上，提出了一种改进型多智能体优化算法。该算法基于分布式人工智能，从AP角度和全局角度来优化AP的布局。
关键词: 无线局域网规划；AP部署；多智能体优化算法；WLAN
引言
目前WLAN的应用已经变得越来越普遍。许多携带无线设备终端的用户在学校,酒店等公共场合通过AP接入Internet网络。为满足这些用户的通信需求，WLAN需要进行合理地规划。在WLAN规划中，AP部署的合理性将直接影响整个网络的通信质量。
一方面，AP的部署需要考虑到整个网络的覆盖，尽可能让每个位置的用户都能被AP的通信信号覆盖并接入网络；
另一方面，AP之间需要进行频率的分配以减少它们之间的相互干扰。但根据先前的研究发现，这两方面的目标是相互冲突的。例如，增加AP密度虽然在一定程度上能增加整个网络的覆盖量, 但这也会引入额外的频率干扰，导致通信服务质量的下降。
此外，AP数量的增加会提高设备的安装及维护成本。从最优化的观点来看，WLAN室内规划问题包括站点的布置和频率的分配两个子问题，它们分别可以抽象为集合覆盖问题和图着色问题。
先前已有不少文献研究WLAN部署的优化。在这些文献中，常规的优化技术有整数线性规划和二次规划，但是这些技术在WLAN部署问题的规模较大时，性能会严重下降。另外，部分文献采用了遗传算法(GA),变邻域搜索算法(VNS)等启发式方法去寻找WLAN的最优配置。启发式算法往往利用过去搜索过程中的信息，以明确算法接下来的搜索方向。在蜂窝网中，启发式方法的运用比较成功。但相比于室外，室内的障碍物干扰比较严重，这使得问题的解空间变的极度复杂，导致启发式算法在室内WLAN部署方案设计中难以有效的把握搜索的方向。
从算法角度分析，变邻域搜索算法作为单体搜索算法的代表，过于注重单体自身指标的提高，而轻视了不同个体之间的交互与协作。这往往会带来较低的搜索效率。遗传算法等单纯的群体算法有时也无法顾及单体搜索的需要。当提高单体搜索能力与提升整体性能相冲突时，由于群体学习侧重整个系统的工作效率,学习的结果就可能以牺牲单体搜索的性能为代价去保证整体的搜索效率。为了克服单体搜索与群体搜索各自的不足，本文设计了一种基于多智能体的优化工具来完成WLAN的热点部署。
近年来，基于多智能体优化的技术开始广泛应用于各类优化问题中，并取得了不错的效果。多智能体的学习算法利用了智能体之间的交互关系及其变化，因而是一种动态协作模型。在此模型中，个体最优化概念失去其意义，因为每个智能体的回报不仅取决于自身，还取决于其它智能体的动作决策。系统的目标是寻找一种策略，最大化系统将来要获得的总回报。
Alan Mc Gibney提出了基于多智能体的技术来优化WLAN的热点部署。他的论文从AP的角度出发，将所有AP看成一个多智能体系统，并采用博弈论工具让通信区域中的所有智能体进行游戏。每次游戏只有一个智能体能进行动作的执行，且每次只能做一种动作，即做移动，分裂以及调频中的一种。移动的主要目的是找到最适合自己的候选站点位置，分裂的目的是为了减少连接自己却得不到正常通信服务的用户数量。调频的目的是为了减少自己与其它智能体之间的频率干扰。
然而，在移动到其它候选站点来提高自身效用时，智能体未考虑到对该位置附近造成的频率干扰。在候选站点密度比较小且优化解空间比较复杂的情况下，智能体通常在博弈游戏中难以移动。智能体在进行移动的时候，不仅原来整个网络中智能体之间的场强关系会改变，它们之间的频率关系也会跟着变化。过分强调位置关系会使得算法忽略掉频率关系比较好的解空间。虽然Alan Mc Gibney采用了growing neural-gas network的方法生成了大量的比较密集的候选站点（在文献中，候选站点数量达到了2000多个）来减少问题解空间的复杂度和算法运行时间，但是在实际WLAN规划工程中，候选站点往往会遇到由公司，企业自己预先规定的情况。除此以外，有时候在实际项目中，候选站点密度比较小的情况会不可避免的遇到。在处理这类规划问题时，Alan Mc Gibney的多智能体优化算法的性能就会下降，并且会提早陷入局部最优。
在本文中，针对实际WLAN室内规划项目中存在候选站点密度小，优化解空间复杂的情况，本文对Alan Mc Gibney中的算法进行了改进，并提出了改进型多智能体优化算法。相比于Alan Mc Gibney的算法，本文的算法改进的地方主要有三方面：
第一，在动作执行阶段加入了随机扰动过程，增加了算法搜索的多样性；
第二，引入局部贪婪寻优过程，增强了算法局部寻优和跳出局部最优的能力，使得搜索能往更深入的解空间搜索；
第三，将博弈论，局域贪婪以及全局优化的思想相互结合起来，提高了算法的搜索效率。
根据如上所述的研究内容，本文在结构上将如下安排：接下来的一章将简要给出WLAN室内规划问题的数学模型。第2章将呈现多智能体优化算法的设计。实验的结果和分析将在第3章给出。最后一章将给出本文的总结，并对未来算法的改进提出建设性的展望。
1 WLAN室内规划问题
在使用多智能优化算法之前，本文需要对现实生活中的真实WLAN室内系统进行数学建模。通过WLAN室内系统数学模型的建立，一些比较复杂的现实问题可以被抽象化，符号化，并建立一定的数量关系。WLAN系统的建模过程是基于服务质量（Quality of Service，QoS）的数学描述。一些关于WLAN规划模型可以从相关的文献中借鉴。在WLAN模型中，为了方便计算机仿真模拟，计算区域将被划分为像素网格。像素网格的中心被定义为标记点（Marking Point，MP）。在这些标记点（除了被AP占据的点）中，被有通信需求的用户所占据的点叫做测试点（Test Point，TP）。
在本文中，为了方便问题的处理，无线网络优化模型将被分解为若干子模型：AP模型，信号传播模型以及吞吐量模型。这些子模型的目的是为了定义WLAN优化问题中的变量，进而得到问题的决策变量和优化目标。这些子模型之间的内在联系如图1所示。
图1 WLAN子模型联系图
AP模型、信号传播模型、吞吐量模型、WLAN问题的评价指标 略。
2 多智能体算法的设计
在这一节中我们将介绍多智能体优化算法的设计。（由于在多功率多天线角度的情况下，问题的解空间极度复杂，并且文献所使用的多智能体算法仅考虑单功率单天线角度的情况，文本为重点突出与该算法在单功率单天线角度的条件下的性能的比较，在设计算法时，也同样只考虑单功率单天线角度的情况。）在这里，我们将区域内的AP看成一个智能体，并把所有AP看成是一个分布式多智能体系统。这些智能体能够感知到被自己覆盖到的用户以及他们的通信满足程度。同时，这些智能体能够按共同的规则去做自己的动作。
（关于：智能体感知、执行动作次序随机扰动、合作博弈阶段、系统全局优化阶段、多智能体算法主框架等详细内容与算法，请移步中国知网下载全文。）
3 实验分析
3.1 实验场景
图2 建筑物拓扑图
图2展示了我们的实验场景。这是一幢拥有3层楼房的建筑物。每一层的面积为46米×46米。在空间离散化的时候，我们每隔1米取一个标记点MP，那么在3层建筑物中一共有6348个MP，每一层有2116个MP。通信区域为3层建筑物内部的所有区域。在建筑物内部除了被AP占据的以外的所有标记点MP都将被作为测试点TP。在图中，绿色的点是候选站点。其中，第一层分布了88个候选站点，第二层一共有77个候选站点，第三层有87个候选站点。对于每一层服务区域，有100个用户有通信需求，每个用户需要的速率为500kb/s。这些用户都均匀分布在每一楼层。那么，在整个建筑物中，所有用户的总需求量150000kb/s。在802.11b标准下，AP的可选信道有13个。
3.2 系统全局优化阶段
为了验证我们算法的可行性,我们将与Alan Mc Gibney提出的算法的进行比较。算法的结果将从在不超过规定的AP数量下去得到最小的obj的角度去比较。在实验中，本文提出的多智能体算法的调节参数K1和K2的取值分别为8和20。两个算法的比较的结果如表1所示。
表1：在AP数量不超过k的情况下得到的最小obj及得到该obj所需的AP数量
从表1中可以看到，我们的算法在中后期的运行的结果要明显优于Alan Mc Gibney提出的算法。在前期,由于智能体数量比较少，导致它们之间的频率和位置关系相对比较孤立。Alan Mc Gibney的算法侧重点为频率关系好或位置关系好的解空间，这使得它的算法性能在智能体数量较少时的条件下优于本文算法。到了中后期，智能体的数量超过了20(本文的多智能体算法的调节参数K2为20)。
此时，由于智能体之间的频率和位置关系非常紧密，Alan Mc Gibney的算法在这个阶段开始陷入局部最优的状态，无法有大量机会去往其它性质的解空间去搜索。而本文的多智能体算法首先考虑频率关系好或位置关系好的解空间。当陷入局部最优状态时，贪婪寻优机制将会被触发。这使得算法的搜索能在原来局部最优解的基础上往更深入的具有其它位置和频率关系且解的评价度更高的解空间展开。当两个算法收敛时，Alan Mc Gibney的算法的obj达到了9885.4 kb/s且需要44个AP，而本文的算法obj达到了277.4 kb/s且仅需要39个AP。
其次，在Alan Mc Gibney的算法得到的解中，AP数量要超过40个以上才有可能做到obj在10000kb/s以下。而本文的算法能找到AP数量不超过30且使得obj在10000kb/s以下的解。在40个以上AP数量的条件下，本文的算法甚至能找到obj在1000kb/s以下的解。综上所示，本文提出的改进型多智能体算法在候选站点密度比较小且解空间比较复杂的WLAN规划项目中的性能要优于Alan Mc Gibney的算法。
4 总结与展望
4.1 总结
本文一开始分析总结了前人所用的算法，并在之后对目前的多智能体算法进行了改进。改进的目的是为了增强多智能体算法在面对候选密度较小的WLAN规划问题的情况下的寻优能力。随机扰动过程的加入，局部贪婪寻优策略的引入分别提升了智能体优化算法寻优的多样性和集中性。在整个算法中，博弈论，局域贪婪以及全局优化三者思想相互渗透与结合进一步提升了寻优的效率。最终的实验进一步证明了本文提出的算法的可行性。
4.2 展望
本文仅考虑了AP配置为单功率单天线角度的WLAN规划问题。多功率多天线角度的配置的情况比较复杂， 此时，AP功率参数和天线角度参数的变化影响着该AP局部周围的场强，并会削弱或增强它对周围的邻居AP的频率干扰。AP位置参数不仅影响着原来位置的覆盖与场强，还对新位置处的周围的其它邻居AP造成了新的频率干扰。因而，本文未来的工作将集中于综合考虑AP功率，AP天线角度，AP位置和AP频率之间的相互关系，研究它们如何分别影响解空间的特性，挖掘新的动作策略并合理嵌入到多智能体算法中。
（参考文献略）
声明：版权归《中国电子科学研究院学报》所有。转载请务必注明出处，违者必究。文章观点不代表本机构立场。
《中国电子科学研究院学报》欢迎各位专家、学者赐稿！投稿链接 http://kjpl.cbpt.cnki.net
电话：010-68893411
邮箱：dkyxuebao@vip.126.com