在室内定位中，用于向外广播信号的接入点（Access Point，AP）因其有着扩网灵活、覆盖面积广、易于管理等优势普遍用于无线信号覆盖。接入网络的用户终端通过扫描不同AP发射的信号，获得网络的基本状态信息，并接收来自不同AP的信号特点，通过一定的匹配算法在预先建立的离线指纹数据库中找到最适合的参考点坐标作为用户终端的定位结果。一旦改变AP位置，指纹数据库将发生巨大变化，定位精度随之变化，因此在建立指纹数据库之前，找到AP部署的最佳位置显得尤为重要。
二、 AP部署研究进展
研究AP部署的目标是确定AP放置的位置，并使用数量尽可能少的AP为服务区域的用户提供尽可能好的覆盖，通常有两种研究方案：采用现场调研的方法和利用计算机辅助设计方法[2]。前者在进行系统的设计和建设之前，先对目标环境进行调查测量以获得必要的参数，由于环境随时间变化，因此每次新环境组网都需要重复大量工作，可见该方法需要花费大量的人力、财力以及时间，成本较高。为了解决现场调研的不足，节约成本，计算机辅助设计方法凸显出其优势，该方法通过预先设定一些约束条件或限制因素，通过数学方法建立工程模型，计算出AP的最佳数目和部署位置。
计算机辅助设计常用的方法主要有：基于信号覆盖的方法、注水算法（Water-Filing）、模拟退火算法（Simulated Annealing,SA）、禁忌搜索算法（Tabu Search,TS）和遗传算法（Genetic Algorithm,GA）等。
1 基于信号覆盖的方法
在过去，室内无线接入系统主要是从无线网络覆盖的角度设计的，根据室内区域总面积和单个AP默认发射功率时的覆盖范围即可确定出实现室内无线网络全覆盖所需的AP数量。很长一段时间，研究的优化目标集中在如何放置最少数量的AP，以确保室内覆盖率大于预先设定的阈值，使用户从不小于预设阈值的AP接收到信号强度RSS用于定位。早期的研究体现出的定位精度往往不高。
2 注水算法
注水算法是多信道无线通信系统中求解容量最大化问题中的一种经典算法。注水优化模型主要用于正交频分多路复用（Orthogonal Frequency division multiplexing,OFDM）信道中的功率分配。在多用户OFDM系统，将注水优化模型应用在AP优化部署的问题中，在总功率一定的条件下，根据信道状况对发送功率进行自适应分配，通常情况下，在信道状况好的时刻，多分配功率，相反，则少分配功率，从而实现系统吞吐量的最大化。[3]应用注水优化模型进行AP部署，并验证了该方法在位置指纹定位精度及时间开销方面的性能。
3 模拟退火算法
模拟退火算法最早的思想是由N.Metropolis等人于1953年提出的。1983年,S.Kirkpatrick等成功地将退火思想引入到组合优化领域。它是基于Monte-Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法从某一较高初温出发，伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解。
期刊文章分类查询,尽在期刊图书馆H.R.Anderson等人使用模拟退火算法应用在AP部署问题中，通过借鉴移动蜂窝网络，区域范围、成本、交通、干扰、容量等因素被考虑和配置，通过使用模拟退火技术，找到最佳的AP位置规划，使以上各方面因素达到最小化成本。
4 禁忌搜索算法
禁忌搜索算法是由H.G.Kang等人提出的，是一种亚启发式(meta-heuristic)随机搜索算法，它从一个初始可行解出发，选择一系列的特定搜索方向（移动）作为试探，选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向。把该算法应用在AP的部署问题中，通过探索所有可能的空间单元，计划找到一个或多个合适的解决方案，但这种方法对于初始解具有较强的依赖性。
5 遗传算法
遗传算法是在20世纪六七十年代由美国密歇根大学的 Holland教授创立。遗传算法是一种基于“适者生存”的高度并行、随机和自适应的优化算法,通过复制、交叉、变异将问题解编码表示的“染色体”群一代代不断进化,最终收敛到最适应的群体,从而求得问题的最优解或满意解。L.Nagy等人利用Motley-Keenan的室内信号传播模型，分析建筑物内无线AP放置技术的最优信号覆盖，设定成本函数为二维平面上路径损耗与某个特定阈值的比率，使用遗传算法使该目标函数达到最小化，从而确定AP数量及合适的部署位置。[4]利用两次遗传算法分别得到部署AP的数目和最优位置。[5]提出了一个基于基因定位的遗传算法框架，在每个信号测试点找到一个具有独特指纹的AP设置，同时最大限度地增加这些指纹之间的多样性，提高了定位精度。
三、应用场景展望及存在的挑战
1 应用场景展望
室内位置服务已经在大型商场、电影院、展馆、机场等室内环境中得到了应用。另外，接入点部署良好的室内定位对行政执法、应急救援与消防、室内停车场的寻车服务、人员和物品位置跟踪等方面具有重要的作用。
2 存在的挑战
由于室内定位环境的特殊性，优化接入点部署还存在很多技术难点，这些难点为在复杂环境下实现AP最佳部署带来了巨大挑战，主要的挑战有:
（1）障碍物多。建筑物内通常会有各种障碍物，包括家具、房间和行人等。障碍物位置各异，房间布局不同，行人时刻存在，大量的不确定性使室内环境异常复杂。
（2）干扰源多。由于室内环境相对封闭，声音、光线、温度等干扰源都会对定位造成一定的影响，增加了AP部署的难度。
（3）多层建筑。室内定位AP部署不仅要考虑二维平面的位置，在多层建筑中还要考虑楼层的位置，包括地上和地下部分。
综上所述，在室内定位系统中快速准确部署接入点对提高定位精度起着重要作用，这正好满足人们对位置服务的需要。但要实现接入点最优部署，仍需要针对不同的应用场景采用适当的技术做进一步研究。因此，室内定位接入点部署将会成为研究的重点和热点。
参考文献
[1]徐小龙。物联网室内定位技术。2017。 电子工业出版社
[2]尤云龙. WLAN室内定位系统中AP自动布放模型的设计与实现. 2017
[3]周牧，蒲巧林，田增山. 室内WLAN定位中位值指纹优化的接入点部署方法. 通信学报. 36(s1): 30-41.2015.
[4]何颖. 基于 WLAN 室内定位系统的 AP快速部署算法研究. 2011
[5]H. Eldeeb, M. Arafa and M. T. F. Saidahmed, "Optimal placement of access points for indoor positioning using a genetic algorithm,"?2017 12th International Conference on Computer Engineering and Systems (ICCES), Cairo, pp. 306-313.2017.
论文作者:王娜
论文发表刊物:《科学与技术》2019年第14期
论文发表时间:2019/12/16
标签：算法论文; 室内论文; 位置论文; 信号论文; 方法论文; 指纹论文; 最优论文; 《科学与技术》2019年第14期论文;