英语原文共 6 页，剩余内容已隐藏，支付完成后下载完整资料
基于概率的群集及其在无线局域网中位置估计的应用
张明华，张申生，曹健
（计算机科学与工程系，上海交通大学，上海200240，中国）
摘要：基于接收信号强度的无线局域网(WLAN)定位成为基于位置服务的一个重要的推动者。效率和精度的限制是确定性的位置估算技术缺点。基于概率技术的定位精度好，但是会花费更高的计算开销。本文提出了基于集群技术的高斯混合模式，提高位置确定的效率。所提出的聚类算法减少了从整个区域到集群的候选位置的数目。在一个集群中，利用更多的访问点的信号强度,使用一种改进的近邻法来估计用户的位置。实验表明，位置估算时间大大减少，并且仍然可以实现高准确性。
关键词：基于概率的群集;高斯混合模型;无线局域网（WLAN）的位置估计;接收的信号强度。
中图分类号：TP 391 文献标识码：A
介绍
随着无线网络和移动设备的发展，基于位置的服务（LBS）的需求不断增长。LBS在很大程度上依赖于底层的位置估计技术。尽管全球定位系统（GPS）是一个著名的定位系统，但是它不能很好地在室内环境工作。随着无线局域网的扩大，，仅利用现有的无线局域网数据（提供了无线局域网中的接收信号强度（RSS））的定位技术已经引起了广泛的兴趣。
无线局域网的定位技术可以大致分为两类：确定性和概率技术。确定性技术使用确定性推理算法来选择最可能的位置，一连串的RSS抽样最好地适合实时RSS测量值。例如，雷达采用了近邻的信号空间（NNSS）技术来推断用户的位置。当定位区域延伸，定位时间会相应增加。此外,NNSS方法只使用RSS从三个固定接入点(AP)，因此位置确定面积是有限的。虽然概率技术更准确,但是我们提出了计算开销和准确性之间的权衡。
一些提高定位的效率方法已经被提出了。优素福等人提出了共同群集技术，但是他们没有提供确定控制参数的方法。在环境中通常会检测出大量的连接点，并且，通过实验来决定的参数是一项艰巨的工作。凯迪特使用K-means群集技术构建了RSS的样本集群。但k均值算法的性能易受噪声数据的影响，这是无线信道的特性。
在本文中，提出了用基于群集技术高斯混合模型建立RSS的样本群。从参考文献的8和9中，从AP中RSS的概率分布可以进行高斯分布的拟合。每个AP覆盖区域的一个位置子集。它是根据检测到的连接点来规划位置的一种自然的方式。因此，在同一群集内的位置，连接点的信号强度遵循相同的概率分布。从检测到的连接点设置的RSS的整个数据可以由几个高斯分布的混合来建模。从数学上来说，每个分布被用来代表一种特定的集群。RSS抽样值的相似度的测量依据它们自身的概率分布。集群定义不仅考虑RSS中的值的差别的方面，如参考文献[7]所示，也反映了RSS的概率分布以便于与无线数据有力执行。在集群中，位置估计使用的是一个改进的近邻算法。所提出的方法的主要特征是将基于概率的群集和确定性位置估计技术的优点整合，目的是提高定位效率。
1.无线信号传播特性
IEEE 802.11b标准在工作中可以自由使用的2.4 GHz频段的无线电频率。虽然许可证自由使得使用同一频带的WLAN宽，许多设备的扩散成为干扰源。受到反射，折射，衍射和吸收结构，甚至人体，信号传播从严重的多径衰落效应[11]的影响。
图1（a）给出了在一个固定的位置接收到AP的信号强度的归一化直方图。图2表示在固定位置二十分钟内检测到的AP数量。它们表明，从AP处接收到的型号强度以及能检测到的AP 数目都会随时间变化。图 1（b）中，另一个标准化直方图是使用在按一定的AP覆盖多个地点采集到的信号强度的。它表明，作为第一近似值，用高斯分布来表示簇是可行的。
2.基于概率的聚类和位置估计方法
WLAN定位估计技术有两个阶段工作。在第一阶段，RSS和采样位置之间的映射被设置，并显示在无线电地图。然后，用户位置的估计是使用经由某些位置确定技术从检测的AP接收到的无线电地图和实时信号强度测量计算出来的。
2.1基于高斯混合模型的聚类和EM算法
假设无线电地图上的记录被表示为矢量
该矢量由检测点接收到各个AP的信号强度以及检测点的位置，其中k为AP的数量，位置是一个元素组（X，Y，方向）。
在第一阶段中，聚类的目的是根据RSS对位置进行分类。检测大量的AP信号。一些AP是在区域内部署;一些部署在其他楼层或相邻建筑物。在实验测试平台，总共有69个AP被检测到。然而，大量AP被认为偶尔让使用所有检测的AP做集群是棘手的和微不足道。因此，重要的第一步就是确定多少AP以及哪些AP被用于聚类。本文提出了一种AP的选择方法，其思路如下：几个最强的AP用来覆盖大部分地区作为环境特征，用来进行聚类。实验结果已经说明，从AP接收到的RSS越强，标准差的越大。因此，AP的强弱由两个参数来评价：信号强度的标准差以及AP覆盖的范围。在本文中，选择前三个AP。
那么，对于3D RSS变量的概率密度函数由下面的概率给出
（1）
其中的参数，使得，并且每个的高斯密度函数是由决定的。换句话说，假定三组分的密度可以与三个系数混合在一起。对于RSS变量高斯密度函数表示为
（2）
其中mu;是均值矢量，Sigma;是协方差矩阵。mu;和Sigma;是高斯分布的参数，即。
接下来的工作是估算公式（1）的参数，并通过无线电地图提供的RSS信息进行聚类。在本文中，EM算法[12]被用于估算参数。当数据不完整或有缺失值的情况下，这是从给定数据集的潜在分布参数中寻找最大似然估计的一般方法。对这个问题，缺少的值是每个RSS变量的类值。
EM算法是通过两个步骤进行的迭代过程：一个是期望步骤（E步骤），一个是最大化步骤（M步骤）。在迭代过程中，模型参数的一个序列产生了，其中，是初始参数，是迭代终止时所获得的融合参数。特别地，它从三个初始高斯模型开始，其特征在于该组参数。的初始先验概率被设定为。在期望步骤中，属于类的每个RSS数据点的概率被用于计算
（3）
该步骤等效于具有一组的连续隐变量，取值在区间[0，1]，给予一个通过告知属于类 的何种程度的RSS数据点的一个数据标记。这代表了一个软分类。在最大化步骤中，所有的数据点参与所有的模型的更新。该平均数用如下公式校正
（4）
其中N是RSS数据的数量
变量们用如下公式修正
（5）
该先验用如下公式校正
(6)
直到总可能性不能连续迭代变化，则迭代停止。在目前的情况下，全球标准是相对于所有的模型中的所有数据的联合可能性：
(7)
聚类之后，每个群集的概率模型被构建。在无线电地图记录可以用分类标o=(，位置，簇标记)来更新。
2.2 定位算法
对于给定的实时RSS测量结果，在聚类中使用的三个应用程序的信号强度首先被选择确定该当前用户最有可能被定位。接着，一种改进的最临近法被用来在更精细的水准上确定的用户位置。
代表实时接收信号向量，其中其中k是检测到的AP在未知的地点的数量，然而代表来自三个选定的AP的信号矢量。然后给定属于各个集群的的信号向量的后验概率用于计算
(8)
其中参数已在第一个阶段被验证，还有。与信号矢量相关联的估计集群的是其获得的后验概率的最大值中的一个
(9)
在一个集群中，一种改进的最临近算法用于定位更高分辨率的用户。参考 [2]该NNSS方法只使用三个固定的应用程序。涉及三个AP的信息是非常有限的，特别是该区域的尺寸是大的。另外，某些位置可能不被一个确定的AP覆盖。改进后的最临近算法从更多的AP使用信号强度来提高精确度。由于聚类技术已经被用来在一个集群中定位用户，通过使用更多APs的计算成本是可以接受的。相同Aps 的数量出现在无线电地图中的每个记录，并且在由用户接收的实时RSS测量结果被计算。然后，这两个信号强度矢量之间的相似性由Euclidean距离测量：
(10)
在式（10）中，iisin;{1,2，...，|簇|}，其中|簇|表示簇的大小。具有最大和最小的定位是因为估计的位置。改进的最临近法的详情可参见参考文献[10]。
3.实验和结果
3.1 实验测试平台
该实验测试平台位于第三SEIEE建筑的二楼，是一个五层建筑包括5个子建筑。该建筑已经配备了IEEE 802.11b无线网络。在楼层的布局示于图3。
用于构建无线电地图，150采样位置沿走廊被选择，每个代表一个1.2times;1.2米网格。随着被修改的网络版WRAP[13]的功能和抽样方案，一个华硕掌上电脑被用来收集RSS数据，面向东边。30个样品是在每个位置每秒被收集一个样本。在楼层检测有69个接入点，其中用于执行群集的三个用混凝土圆来标记。，示于图3。
3.2 集群结果
实验是第一个进行了基于概率的聚类高斯混合模型的影响的研究。150个采样位置是沿着走廊获得的，每个水平迹线各有75人。聚类后，每个位置都有一个类标签。结果示于图4。为了比较，k-均值聚类算法也被实现，其结果示于图5。
直观地，这三个簇可以是三个AP周围，其中每个AP都有自己的覆盖区域。簇的大小主要由AP的功率来确定。图4表明这种想法，在三组簇的位置是非常紧凑的，除了第二簇中的一些定位。第二簇是最大的，因为中间的AP是由外部天线加强，但是其他两个APs被嵌入到天花板。k-均值算法计算了两个位置中的RSS向量之间的欧几里得距离的相似性。在图5，聚类结果并不与图4清楚。它不用一起考虑联合来自不同AP的信号强度之间的关系，就像三维高斯混合模型一样。例如，在东边采样位置收集的RSS矢量，与东边AP关联的元素是最大的，并与西方的AP相关联的一个是最小的。然而，K-均值算法无法区分他们。基于概率的聚类技术更适合嘈杂的RSS数据，并具有更好的性能。
3.3 定位法
另一组实验被执行以检查提出的位置估计方法的效果。让M1代表所提出的方法。与M1不同，M2采用了K-均值聚类算法。最后两个方法也没有采用任何聚类技术。让M3定位用户与改进临近算法。M4与NNSS[5]非常类似，但仅使用三个接入点。为了显示无线信道的噪声特性，所使用的信号样本的数量是从一到五连接。图6示出了结果
从图6看出，增加的信号样本的数量可以提高位置估计的精度，当时数从一个变成二个这是比较显著。使用两个实时RSS抽样值的平均值，嘈杂无线信道的效果可大大减少。然而，存在位置估计精度和定位时间之间的权衡。这取决于具体应用。对于许多普适计算应用，例如病人监护仪，使用两个采样信号的均值来定位是可行的。改进的最近邻居算法M3有比M4一个更好的性能。即使只使用一个信号样本来实现也有41%（70.6%-29%）得劲定位精度。这表明，使用的RSS来自更多的AP可提高精度，特别是当区域较大时。更重要的是，准确的使用不同数目的AP为M1的改进示于图7。 AP根据到定位区域的距离增加。在图6中，我们还发现，高斯混合模型聚类技术比K-均值聚类技术更好。其原因是，高斯混合模型能够准确地描述的信号强度在无线室内环境的分布。
虽然M1没有M3这么好，但是M1可以显著地降低成本。图8是四种方法定位所需的时间。
定位时间在一台IBM T40笔记本上的matlab平台上测量，它的配置是奔腾M1.5 GHz处理器，512M内存和Windows XP操作系统。如该图8所示，M3花费的时间差不多是M1的两倍左右（1.19/0.61=1.95）。然而，M3的定位精度比M1的仅高出2.6％ （70.6％-68％）。其结果，将定位精度和定位时间都考虑在内，所提出的方法是最好的。同时也可以发现，M4仍然花费比M1更多的时间，虽然M4只使 用三个AP。这表明，减少候选位置的数目增加了位置估算效率的最重要因素。总之，集群技术是一种有效的方式，而且使用的RSS来自更多的AP是合理的。
- 总结
本文实证研究基于概率的聚类技术的对推定精度和时间的影响。一种改进的近邻算法来估计一个集群，它采用由多个AP的RSS信息内用户的位置。实验表明，基于 聚类高斯混合模型可以用来减少候选位置的数量。其结果，定位时间大大缩短，但是仍可以实现高准确性。在未来，我们计划结合半监督学习算法，进一步提高定位方法的有效性。
参考文献
[1] Enge P, Misra P. Special issue on GPS: The global positioning system [J]. Proceedings of the IEEE, 1999,87(1): 3–172.
[2] Bahl P, Padmanabhan V N. RADAR: an in-bui
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[29235]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
