论文部分内容阅读
摘要：该文对现有室内定位中的AP（Access Points）选择算法进行了研究。首先，从时间、地点、方向等方面对AP信号造成的影响进行了实验分析，得出AP选择的重要性。其次，从国内外的研究现状出发，对基于WiFi的室内定位中AP选择算法进行了分类和对比分析，讨论算法的优缺点，分析显示室内定位算法的研究注重定位精度和能源消耗之间的平衡，最终得出结论。
关键词：室内定位；AP选择；WiFi；定位精度；能源消耗
中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2016）21-0242-03
Abstract： The paper examines the AP selection algorithms in existing indoor location schemes. Firstly， it looks into the impacts such aspects as time， location and orientation have on AP signal through experiments， showing the importance of AP selection. Secondly， based on the research both at home and abroad， this paper categorizes and compares the AP selection algorithms in Wi-Fi-based indoor location and discusses their strengths and weaknesses. The analysis shows that research on indoor location algorithms place a great emphasis on the balance between location accuracy and energy consumption. Lastly the paper arrives at conclusions.
Key words： indoor localization； Access Points select； Wireless Fidelity； location accuracy ； energy consumption
1 引言
根据无线信号与不同的地理位置进行匹配映射的关联特点，基于WiFi指纹的室内定位技术通过建立WiFi信号强度（RSS）和地理位置的映射关系來实现位置的定位，即不同地理位置上接收到的WiFi信号强度是不同的。在复杂的室内环境中，受多种因素的影响，AP信号的传播变得非常复杂和多变，比如有气候的变化、人体走动、多径效应、墙壁门窗的遮挡、其他信号干扰等因素；而实时定位的精度以及稳定性也会受AP的性能、AP的数目、采样点的方向、时间等多种因素的影响。这样会导致AP信号指纹与地理位置的映射关系发生变化，造成定位精度大幅度的降低。因此，为了提高基于WiFi指纹的室内定位精度和稳定性，本文首先对影响室内定位精度和稳定性的因素进行了实时的分析，然后从国内外研究现状出发，总结定位精度与多种因素的关系和其他方法[1-2]。
2 室内定位的影响因素分析
基于WiFi的室内定位由于受室内环境的多种因素影响，室内中人群的走动和气候的变化影响AP的信号强度变化；受墙壁和橱窗等障碍物的遮挡和阻隔造成AP的信号传输发生折射和衍射；AP信号随着时间的推移也会发生变化[3]。为了更加深入的了解影响室内定位的因素，本文对场景中室内因素进行的实验分析。实验场景为山东科技大学J13办公楼，包括走廊、办公室、机房等。
2.1 AP信号强度变化情况
如图1所示，在固定采样点对多个AP进行采样，然后对每个AP的信号强度进行统计分析，得出每个AP的信号强度变化近似成高斯分布。这对指纹库中数据的处理与存储有很大的帮助。
2.2 同一采样点不同时间采集到的AP数目
如图2所示，由于周围环境的变化比如人员走动等因素，同一位置的不同时间接收到的AP个数也会变化。所以，构件指纹库和在线定位时接收的AP信号数据，应该选择适当的AP进行数据过滤。
2.3 同一时间不同采样点采集到的AP数目
在复杂的室内环境下，受到房间环境的干扰，一些AP信号干扰比较大，有时候不仅会出现波动，还可能接收不到。所以，不同位置接收到的AP数目不一样。从图3可以看出，不同位置接收到的AP数目在变化的，而且相邻位置采样感测到的AP数目也有很大不同。
2.4 AP数目对误差的影响
图4是对实验环境内定位精度的一个分析，本分析是使用简单的确定性的KNN定位算法，在20个参考点的情况下，对指纹库中，RSS信号强度向量的一个维度的分析。由于不同AP对定位精度的贡献值不同，从来表现出定位精度的大幅变化。可以看出从维度为11到20时定位精度在3m左右。
总之，在复杂的室内环境中，由于空间小，房间结构复杂，比如墙壁、门窗的遮挡，人员的走动等，导致无线信号传播呈现多径传播效应，使得AP信号不稳定，变化多样。这就给室内定位精度的提高和定位精度的稳定性带来了挑战，以上分析的因素就是几个因素。所以AP选择至关重要，AP选择既可以大幅度的克服以上问题，又减小计算开销。
3 AP选择算法研究
随着基于指纹的WLAN室内定位技术的发展，许多学者也提出了相应的AP选择算法。最简单的AP选择算法是将所有能接收到信号的APs都作为采样对象，这样可以增加指纹库的存储并且加大在线定位的计算量。下面总结了几种AP选择算法。
3.1 MaxMean方法 2003年Youssef等人提出了MaxMean方法[4]。该方法是在每个采样位置，按照接收到的RSS平均值将APs进行排序，然后从中选择前k个RSS平均值最大的APs作为采样目标，最后将它们的RSS值当作样本指纹建立指纹库。通常在采样点位置接收到的AP数目是不断发生变化的，因此会经常选取在接收AP集合中出现频率最高的那些APs。例如Youssef团队提出的联合聚类技术（Joint Clustering Technique），主要是利用不用AP的信号强度的联合概率分布根据观察的信号强度样本找出最可能的用户位置，除此之外，使用聚类可以减小计算开销。
联合聚类技术分两个阶段：离线训练阶段（Offline training phase）和在线定位阶段 （Location determination phase）。离线阶 段首先是计算联合概率分布，涉及三个方面：联合概率的维度k的确定、选择哪k个AP和计算联合概率分布。公式如1。
在线阶段的总体思路，首先在未知位置获得来自周围AP的一个样本，选择其中q个最强的AP来决定属于哪个群集；然后根据观察样本利用贝叶斯理论求出每个位置的概率，根据指纹库中的概率求出可能性最大的位置。
通过该方法定位的精度90%的情况在2.1m左右，而用所有的AP定位精度为2.1m的情况下只有38%。定位精度得到了显著提高。该方法的缺点是，并没有考虑AP的RSS的变化情况，第一，对于变化较大的AP，实时定位的数据和指纹库中的采样数据有可能都不相同，从而加大了定位的误差。第二，对于该方法中设定的k和q可能实际测量时AP的数目小于k或者q。
3.2 基于信息增益的AP选择算法
2008年陈益强等人提出了基于信息增益的AP选择算法（CADET）[5]，利用数据挖掘技术来定内定位同时集中解决减少能耗问题，主要是二点：一是应用特征选择来选择AP；二是应用基于多元决策树处理无线数据。由于无线信号的多变，在CADET方法中，用基于信息理论的特征选择方法，它可能优化定位计算精度并且在高精度的计算下减少所需的样本数量。
CADET算法同样分两个阶段。离线阶段进行AP选择，应用特征选择算法找出APs集合S。根据集合S和离线阶段采集的数据，应用后续聚类分析，把网格空间分区为集群，每个集群提供一个后续位置模型，然后基于S中的APs，对每个群集构件一个决策树。在线阶段将将实时采集的数据作为输入，进行位置估计根据从S中选择APs的信号强度向量，来用于决定当前客户端属于哪个群集。然后根据决定群集的决策树来决定客户端属于哪个网格。
该方法中重要一环的AP选择就是应用信息增益（InfoGain）方法，InfoGain算法是以信息论中的信息增益为基础而设计的AP选择方法。在基于WiFI的网格定位系统中，每个接入点当成是一个指纹，且其中每个网格都可由周围m个接入点进行表示。在某个网格中，离线采集的第i个AP的信号指纹作为该网格的第i个特征，其中未接收到的AP对应的特征值设置为-95。InfoGain方法中使用信息增益的目的是评判每个特征的重要性，基于此选择信息增益最高的k个接入点作为定位AP。每个特征的重要性判断由信息增益来计算，就是通过信息熵来计算已知网格和未知网格之间信息熵的差值，公式如下。
该方法以提高精度的同时降低计算功耗为主要目的，运用了数据挖掘技术、信息论等技术，相比于选取RSS平均值最高的AP的MaxMean算法，InfoGain算法通过AP区分网格的能力来选择APs，因此相对于传统的方法该定位算法具有较好的定位效果且降低了计算功耗。但是通过实验证明，信号最强的AP也不一定最适合选作采样AP。
3.3 联合AP选择法
哈尔滨工业大学的邓志安博士曾提出的联合AP选择方法[6]，该方法主要是考虑AP之间的相关性，既未知较近的AP信号强度值之间的相关性信息，然后根据最大化信息准则来对接收到AP特征进行选择。该方法的基本原理与InfoGain算法累死，是根据MMI准则来度量特征指纹之间的信息增益，基于此，选择信息增益最高的某些AP作为定位AP。
3.4 基于APs信号关联性的选择方法
Kushki等人提出的AP选择方法是利用AP信号值之间的关联特性[7]，该算法的使用说明了所选择的接入点之间的相关性的最小化原则问题。在此基础上，提出了AP选择方法，该算法主要是利用NI过滤器来对定位区域中含有信息叫多的AP作为选择的接入点，其中位置的分辨能力是通过聚类之间的方差和聚类内部的散失率进行衡量。
上述3.2和3.3都是对MaxMean方法的衍变，都是选择最大（信号强度、信息增益、别的AP特征）的前m个AP作为采样对象，从而进行定位。所述的AP选择算法主要是通过APs的RSS数据在样本中出现的概率以及对位置的分辨能力作为衡量标准，虽然减小了定位计算量，但由于AP的多变化性都没有考虑APs的RSS样本数据的稳定性，无疑增加了误差，定位结果不准确。
4 结论
本文对现有室内定位中的AP选择算法进行了综述研究。首先，从时间、地点、方向等方面对AP信号造成的影响进行了实验分析，得出AP选择的重要性。其次，从国内外的研究现状出发，对基于WiFi的室内定位中AP选择算法进行了分类和对比分析，讨论算法的优缺点，分析显示室内定位算法的研究注重定位精度和能源消耗之间的平衡。为下一步室内定位方法的研究奠定基础。
参考文献：
[1] 姜莉.基于WiFi室内定位关键技术的研究[D].大连理工大学，2010.
[2] He S，Chan S H G. Wi-Fi Fingerprint-based Indoor Positioning： Recent Advances and Comparisons[J].IEEE Communications Surveys
关键词：室内定位；AP选择；WiFi；定位精度；能源消耗
中图分类号：TP301 文献标识码：A 文章编号：1009-3044（2016）21-0242-03
Abstract： The paper examines the AP selection algorithms in existing indoor location schemes. Firstly， it looks into the impacts such aspects as time， location and orientation have on AP signal through experiments， showing the importance of AP selection. Secondly， based on the research both at home and abroad， this paper categorizes and compares the AP selection algorithms in Wi-Fi-based indoor location and discusses their strengths and weaknesses. The analysis shows that research on indoor location algorithms place a great emphasis on the balance between location accuracy and energy consumption. Lastly the paper arrives at conclusions.
Key words： indoor localization； Access Points select； Wireless Fidelity； location accuracy ； energy consumption
1 引言
根据无线信号与不同的地理位置进行匹配映射的关联特点，基于WiFi指纹的室内定位技术通过建立WiFi信号强度（RSS）和地理位置的映射关系來实现位置的定位，即不同地理位置上接收到的WiFi信号强度是不同的。在复杂的室内环境中，受多种因素的影响，AP信号的传播变得非常复杂和多变，比如有气候的变化、人体走动、多径效应、墙壁门窗的遮挡、其他信号干扰等因素；而实时定位的精度以及稳定性也会受AP的性能、AP的数目、采样点的方向、时间等多种因素的影响。这样会导致AP信号指纹与地理位置的映射关系发生变化，造成定位精度大幅度的降低。因此，为了提高基于WiFi指纹的室内定位精度和稳定性，本文首先对影响室内定位精度和稳定性的因素进行了实时的分析，然后从国内外研究现状出发，总结定位精度与多种因素的关系和其他方法[1-2]。
2 室内定位的影响因素分析
基于WiFi的室内定位由于受室内环境的多种因素影响，室内中人群的走动和气候的变化影响AP的信号强度变化；受墙壁和橱窗等障碍物的遮挡和阻隔造成AP的信号传输发生折射和衍射；AP信号随着时间的推移也会发生变化[3]。为了更加深入的了解影响室内定位的因素，本文对场景中室内因素进行的实验分析。实验场景为山东科技大学J13办公楼，包括走廊、办公室、机房等。
2.1 AP信号强度变化情况
如图1所示，在固定采样点对多个AP进行采样，然后对每个AP的信号强度进行统计分析，得出每个AP的信号强度变化近似成高斯分布。这对指纹库中数据的处理与存储有很大的帮助。
2.2 同一采样点不同时间采集到的AP数目
如图2所示，由于周围环境的变化比如人员走动等因素，同一位置的不同时间接收到的AP个数也会变化。所以，构件指纹库和在线定位时接收的AP信号数据，应该选择适当的AP进行数据过滤。
2.3 同一时间不同采样点采集到的AP数目
在复杂的室内环境下，受到房间环境的干扰，一些AP信号干扰比较大，有时候不仅会出现波动，还可能接收不到。所以，不同位置接收到的AP数目不一样。从图3可以看出，不同位置接收到的AP数目在变化的，而且相邻位置采样感测到的AP数目也有很大不同。
2.4 AP数目对误差的影响
图4是对实验环境内定位精度的一个分析，本分析是使用简单的确定性的KNN定位算法，在20个参考点的情况下，对指纹库中，RSS信号强度向量的一个维度的分析。由于不同AP对定位精度的贡献值不同，从来表现出定位精度的大幅变化。可以看出从维度为11到20时定位精度在3m左右。
总之，在复杂的室内环境中，由于空间小，房间结构复杂，比如墙壁、门窗的遮挡，人员的走动等，导致无线信号传播呈现多径传播效应，使得AP信号不稳定，变化多样。这就给室内定位精度的提高和定位精度的稳定性带来了挑战，以上分析的因素就是几个因素。所以AP选择至关重要，AP选择既可以大幅度的克服以上问题，又减小计算开销。
3 AP选择算法研究
随着基于指纹的WLAN室内定位技术的发展，许多学者也提出了相应的AP选择算法。最简单的AP选择算法是将所有能接收到信号的APs都作为采样对象，这样可以增加指纹库的存储并且加大在线定位的计算量。下面总结了几种AP选择算法。
3.1 MaxMean方法 2003年Youssef等人提出了MaxMean方法[4]。该方法是在每个采样位置，按照接收到的RSS平均值将APs进行排序，然后从中选择前k个RSS平均值最大的APs作为采样目标，最后将它们的RSS值当作样本指纹建立指纹库。通常在采样点位置接收到的AP数目是不断发生变化的，因此会经常选取在接收AP集合中出现频率最高的那些APs。例如Youssef团队提出的联合聚类技术（Joint Clustering Technique），主要是利用不用AP的信号强度的联合概率分布根据观察的信号强度样本找出最可能的用户位置，除此之外，使用聚类可以减小计算开销。
联合聚类技术分两个阶段：离线训练阶段（Offline training phase）和在线定位阶段 （Location determination phase）。离线阶 段首先是计算联合概率分布，涉及三个方面：联合概率的维度k的确定、选择哪k个AP和计算联合概率分布。公式如1。
在线阶段的总体思路，首先在未知位置获得来自周围AP的一个样本，选择其中q个最强的AP来决定属于哪个群集；然后根据观察样本利用贝叶斯理论求出每个位置的概率，根据指纹库中的概率求出可能性最大的位置。
通过该方法定位的精度90%的情况在2.1m左右，而用所有的AP定位精度为2.1m的情况下只有38%。定位精度得到了显著提高。该方法的缺点是，并没有考虑AP的RSS的变化情况，第一，对于变化较大的AP，实时定位的数据和指纹库中的采样数据有可能都不相同，从而加大了定位的误差。第二，对于该方法中设定的k和q可能实际测量时AP的数目小于k或者q。
3.2 基于信息增益的AP选择算法
2008年陈益强等人提出了基于信息增益的AP选择算法（CADET）[5]，利用数据挖掘技术来定内定位同时集中解决减少能耗问题，主要是二点：一是应用特征选择来选择AP；二是应用基于多元决策树处理无线数据。由于无线信号的多变，在CADET方法中，用基于信息理论的特征选择方法，它可能优化定位计算精度并且在高精度的计算下减少所需的样本数量。
CADET算法同样分两个阶段。离线阶段进行AP选择，应用特征选择算法找出APs集合S。根据集合S和离线阶段采集的数据，应用后续聚类分析，把网格空间分区为集群，每个集群提供一个后续位置模型，然后基于S中的APs，对每个群集构件一个决策树。在线阶段将将实时采集的数据作为输入，进行位置估计根据从S中选择APs的信号强度向量，来用于决定当前客户端属于哪个群集。然后根据决定群集的决策树来决定客户端属于哪个网格。
该方法中重要一环的AP选择就是应用信息增益（InfoGain）方法，InfoGain算法是以信息论中的信息增益为基础而设计的AP选择方法。在基于WiFI的网格定位系统中，每个接入点当成是一个指纹，且其中每个网格都可由周围m个接入点进行表示。在某个网格中，离线采集的第i个AP的信号指纹作为该网格的第i个特征，其中未接收到的AP对应的特征值设置为-95。InfoGain方法中使用信息增益的目的是评判每个特征的重要性，基于此选择信息增益最高的k个接入点作为定位AP。每个特征的重要性判断由信息增益来计算，就是通过信息熵来计算已知网格和未知网格之间信息熵的差值，公式如下。
该方法以提高精度的同时降低计算功耗为主要目的，运用了数据挖掘技术、信息论等技术，相比于选取RSS平均值最高的AP的MaxMean算法，InfoGain算法通过AP区分网格的能力来选择APs，因此相对于传统的方法该定位算法具有较好的定位效果且降低了计算功耗。但是通过实验证明，信号最强的AP也不一定最适合选作采样AP。
3.3 联合AP选择法
哈尔滨工业大学的邓志安博士曾提出的联合AP选择方法[6]，该方法主要是考虑AP之间的相关性，既未知较近的AP信号强度值之间的相关性信息，然后根据最大化信息准则来对接收到AP特征进行选择。该方法的基本原理与InfoGain算法累死，是根据MMI准则来度量特征指纹之间的信息增益，基于此，选择信息增益最高的某些AP作为定位AP。
3.4 基于APs信号关联性的选择方法
Kushki等人提出的AP选择方法是利用AP信号值之间的关联特性[7]，该算法的使用说明了所选择的接入点之间的相关性的最小化原则问题。在此基础上，提出了AP选择方法，该算法主要是利用NI过滤器来对定位区域中含有信息叫多的AP作为选择的接入点，其中位置的分辨能力是通过聚类之间的方差和聚类内部的散失率进行衡量。
上述3.2和3.3都是对MaxMean方法的衍变，都是选择最大（信号强度、信息增益、别的AP特征）的前m个AP作为采样对象，从而进行定位。所述的AP选择算法主要是通过APs的RSS数据在样本中出现的概率以及对位置的分辨能力作为衡量标准，虽然减小了定位计算量，但由于AP的多变化性都没有考虑APs的RSS样本数据的稳定性，无疑增加了误差，定位结果不准确。
4 结论
本文对现有室内定位中的AP选择算法进行了综述研究。首先，从时间、地点、方向等方面对AP信号造成的影响进行了实验分析，得出AP选择的重要性。其次，从国内外的研究现状出发，对基于WiFi的室内定位中AP选择算法进行了分类和对比分析，讨论算法的优缺点，分析显示室内定位算法的研究注重定位精度和能源消耗之间的平衡。为下一步室内定位方法的研究奠定基础。
参考文献：
[1] 姜莉.基于WiFi室内定位关键技术的研究[D].大连理工大学，2010.
[2] He S，Chan S H G. Wi-Fi Fingerprint-based Indoor Positioning： Recent Advances and Comparisons[J].IEEE Communications Surveys