 Hans Journal of Wireless Communications 无线通信, 2012, 2, 34-38 http://dx.doi.org/10.12677/hjwc.2012.22007 Published Online May 2012 (http://www.hanspub.org/journal/hjwc) Wireless Local Area Network Indoor Positioning Using Locality Preserving Projects Jia-Han Jan, Kun-Chou Lee Department of Systems and Naval Mechatronic Engineering, National Cheng Kung University, Tainan Email: jch615@hotmail.com, kclee@mail.ncku.edu.tw Received: Apr. 4th, 2012; revised: Apr. 19th, 2012; accepted: Apr. 29th, 2012 Abstract: In this study, we utilize location fingerprinting approaches for indoor positioning by Wireless Local Area Network (WLAN) received signal strength. The approaches are divided into two parts including off-line and on-line stages. In the off-line stage, we collected received signal strength are projected onto the feature space of Locality Preserving Projects (LPP). In the on-line stage, we receive real-time signal strength compared with the off-line stage was collected data using Maximum Likelihood (ML) to estimate current location. Simulation results show that application of LPP not only reduce original dimension of the signal strength database but also reduce the computation. In addition, it can does not affect the positioning accuracy and reduce the off-line stage required prior to collection of signal samples at the same time. From simulation results show that this algorithm is used in indoor location is feasible. Keywords: Wireless Local Area Network; Locality Preserving Projects; Indoor Positioning 应用局部保持投影法于无线网络室内定位 詹佳翰，李坤洲 国立成功大学，系统及船舶机电工程学系，台南 Email: jch615@hotmail.com, kclee@mail.ncku.edu.tw 收稿日期：2012 年4月4日；修回日期：2012 年4月19 日；录用日期：2012 年4月29 日 摘 要：本研究利用无线网络接收到的讯号强度值进行室内定位，定位的算法我们引用了指纹特征比对法的概 念，共分为离线阶段和在线阶段，在离线阶段我们应用局部保持投影法将接收到的讯号强度值投影到特征空间。 在在线阶段，将接收到的实时讯号强度值利用最大似然法与离线阶段的资料作比对，估算出目前所在位置。实 验结果显示，应用局部保持投影法可以将接收到的讯号强度值做前置处理，降低原始接收到的讯号维度，减少 定位时的计算量，且在不影响定位准确率的同时，可以减少离线阶段所需事先收集讯号样本的时间，大幅节省 事先收集讯号样本的工作量，从实验结果可知此算法应用于室内定位是可行的。 关键词：无线网络；局部保持投影法；室内定位 1. 引言 近年来，室内无线网络在目前有越来越普遍的情 形，传统的无线网络定位有几个位置估计的方法像是 收讯时间法(Time of Arrival，TOA)或是到达方向估算 法(Direction of Arrival，DOA)[1-3]来定位，此种方法在 定位时需量测反射讯号的到达时间差或方向，但如果 接收的反射讯号遇到多重路径反射时，容易造成定位 结果的不准确。故在本研究中我们将接收到的讯号 值，引用指纹特征比对法的概念，并利用图形比对的 方式，应用于室内无线网络定位，可以避免掉多重路 径反射对于定位的影响。这种定位方式只需要由现在 广泛存在的无线网络和可接收讯号的接收机器(本研 Copyright © 2012 Hanspub 34  应用局部保持投影法于无线网络室内定位 究是利用笔记型计算机)即可实现，故并不需要额外的 专用设备，藉此可以节省硬件成本并且同时拥有较高 的定位准确率。其中指纹特征比对法[4,5]的概念，其流 程就跟在比对人类指纹时相同，共分为两个阶段，分 别是训练(即离线阶段)和测试(即在线阶段)，离线阶段 是在选定的参考位置上收集来自各个讯号来源的强 度值(dBm)储存 至数据库；在 线阶段我们将 接收到的 即时讯号利用最大似然法(Maximum Likelihood，ML) [6,7]与收集到的数据库做比对，来估算出目前所在位 置。 在实际的室内定位环境中，参考地点上接收到的 各个讯号来源的讯号强度值通常都有复杂的时变性， 容易影响定位的准确率，且一般收集到的数据库经常 是高维度的，故我们加入局部保持投影法将原始数据 库做前置处理，希望可以降低数据库维度并且保持数 据特性。实验结果显示，应用局部保持投影法可以将 原始接收讯号强度值做前置处理，降低原始接收到的 讯号维度，减少定位时的计算量，且在不影响定位准 确率的同时，可以减少每个地点的收集量，大幅节省 事先收集的工作量。 2. 局部保持投影(Locality Preserving Projects, LPP) 局部保持投影法(Locality Preserving Projects，LPP) 是Xiaofei He和Partha Niyogi提出的一种非常有效的 降维方法[8]，此算法是优化线性算法近似于由拉普拉 斯特征映像(Laplacian Eigenmap，LE)[9]导出的流形 Laplace-Beltrami 算子的特征函数，其目标是保持数据 之间的相似关系，即可以保持高维数据的邻域结构特 性，使得高维空间邻近的数据点在低维空间里也能保 持邻近，实质在运算时是非线性投影算法的一个线性 近似。 首先，假设我们接收到的原始讯号来源(Access Point, AP)维度大小为 D，我们将此讯号定义为向量 12 ,,, T D x xxX，在数据库中我们总共收集了 L个 地点(Receive position)，每个地点有 N笔数据，故所 有数据笔数为 1 L l M N ，我们将这些 M笔数据定义 为,1,, i X i Figure 1. The structure of the database 图1. 数据库之构造图 首先，在训练(离线阶段)，我们要寻找一个转换 矩阵 A，将原始资料 X 转换为 12 ,,, T d Yyy y，其 中( )，希望高维原始数据透过转换矩阵投影到 低维特征空间后，让同类相近邻向量尽可能靠近，而 不同类近邻向量则尽可能远离。 dD 首先，构造近邻图 G:G为M笔数据所构成的图， 我们使用 k近邻方法来构建，此方法即是当原始讯号 i X 与 j X 为距离 k笔资料以内时，代表 i X 与 j X 是属 于同类，则在相邻的各笔数据之间都有一条边连接。 接着是利用上面近邻图 G来定义权值矩阵W， 此矩阵的計算方法是使用热核方法(Heat Kernel)，其 中热核方法即是当原始讯号 i X 与 j X 是属于比较近 邻，即是有边连接时，此时权值矩阵为 2 exp ij ij X XtW，如果 i X 与 j X 不是近邻， 则0 ij W，公式如下，其中 t为热核参数。 2 , is nearest neighbors of 0 ,otherwise ij XX tij ij eX WX (1) 局部保留投影的目标，是经过转换矩阵 A投影到 特征空间，在高维中邻近的向量投影到低维后一样还 是邻近。因此为了保持低维投影完后一样保持邻近， 故求下面目标函数的最小化： 2 ,1 min M ij ij ij YY W (2) 投影到特征空间是利用此线性变换 T ii YAX并 将它代入式(2)，经运算后如下式 2 2 ,1 ,1 11 22 MM TT ij iiij ij ij ij ij TT TT YYAX AX AXX AAXLX A WW DW (3) M ，将这些数据储存至数据库，排序方 式如图 1所示。定位主要分为训练(即离线阶段)和测 试(即在线阶段)两个阶段。 Copyright © 2012 Hanspub 35  应用局部保持投影法于无线网络室内定位 其中 D 为对角矩阵，它的对角元素为对应于W每一 行的和，即是 1 M ii ij j D W， L DW为拉氏矩阵。 经过上面推导后可得知式(2)可简化表示为 1 argmin T T T T AXDX A A XLXA (4) 其中 1 T T A XDXA为约束条件，故目标函数最小化 可转换为下式(5)广义特征值求解问题 TT X LX AXDX A (5) 求出特征值方程式的解，算出特征值 i 和对应的特征 向量 i A，其中 ，接着我们选取前个 最小的正数特征值 1,i 0 D dd D d12 所相对应的特 征向量，经过转换矩阵将其投影到LPP 特征空间，投 影完后之特征空间如图 2所示，其中选取的特征值数 目对应的特征向量即是主成份的个数。 3. 仿真结果与分析 在本研究中通讯定位的实验地点是在国立成功 大学机械工程学系系馆，我们选定了 10 个(L = 10)参 考地点，然后我们利用笔记型计算机来接收讯号，在 每个参考地点接收 10 个(D = 10)讯号来源(即无线网 络接收到的讯号数目)，并且在每个参考地点收集 150 笔讯号强度值，每一笔的时间间格为 1秒，我们将它 们分成两组数据，前 100笔讯号强度值当成训练(即离 线阶段)时所需的训练笔数，而参考地点有 10个，故 训练向量笔数为 1000笔，并将这些数据放至数据库， 其数据维度为 10 × 1000。而后 50笔讯号强度值，测 试向量笔数为500 笔，将其当成测试(即在线阶段)时 测试定位结果是否正确所需的测试向量。当中室内定 位算法之流程图，如图 3所示。 Figure 2. The structure of the LPP feature space 图2. LPP特征空间之构造图 Figure 3. The flow chart of indoor positioning for LPP 图3. 局部保持投影法室内定位算法之流程图 在本实验中，我们将收集到的训练向量所集合而 成的数据库，利用局部保持投影法投影到特征空间完 成训练步骤，并计算出训练完的平均值及标准差，以 便测试定位结果时所需，接着进行测试步骤，将测试 向量利用最大似然法算出定位的结果。当中局部保持 影法的第一步构造近邻图 G，其中的近邻参数 k之设 定[10]，我们是假设同一个参考地点内训练数据皆为近 邻，故近邻参数 k = N – 1 = 99，其中N为每一个参考 地点的训练笔数。接着我们计算定位结果的部份，在 选择不同主成份个数的定位准确率，如图 4所示。从 图中我们可发现主成份个数取3个(d = 3)和取 4个(d = 4)的定位准确率分别为 96.80%及98.20%，主成份个 数只需取 3个(d = 3)即可达到 90%的高准确率， 02468 nu 10 m b e r of di m ensions 50 60 70 80 90 100 accu r acy (%) 54.2 79.4 96.8 98.2 98.8 98.6 98.6 98.6 98.6 Figure 4. The positioning accuracy versus number of the principal components 图4. 选择不同主成份个数的定位准确率 Copyright © 2012 Hanspub 36  应用局部保持投影法于无线网络室内定位 大量的减少了原始训练向量维度(D = 10)，可以大幅 节省计算量。 当中在定义权值矩阵W时所使用的热核方法，在 计算定位准确率时参数 t的选取大小亦会影响，在此 方法中我们将参数 t称为热核参数，当中热核参数 t 并没有一个固定值，故本研究选择一个较广泛的范围 10–1 到来试验，结果如图 5所示，从图中我们可以 发现热核参数 t在1000之后的对于定位的准确率变化 幅度不大，准确率趋近于固定(93%上下)，而在热核 参数 t在1000以前，我们发现 t = 10拥有较佳的准确 率为 96.8%，故我们在本研究中热核参数皆取t = 10 来进行定位估算。 5 10 上述的定位结果都是以训练向量为100笔来训 练，而在本文中的定位方式是以指纹特征比对法的概 念，故离线阶段需要事先收集每个参考地点的讯号数 据当作训练向量，会耗费大量的收集时间，因此我们 希望可以减少训练(离线阶段)事先收集训练向量的时 间，故我们将训练(离线阶段)的笔数减少，分别取10 笔、20 笔……到100笔训练笔数做训练，主成份个数 我们取 3个(d = 3)的情况下，其不同的训练笔数定位 的结果，如图 6所示。 从图 6中我们可以发现训练笔数 40 笔、50笔、60 笔时准确率分别为 85.40%，90.80%及92.20%，我 们 仅 需50 笔的训练向量定位准确率即可达到 90%以上， 0.1110100100010000 100000 heat ke r nel p a r a m ete r 80 84 88 92 96 100 accu r acy (%) 83.8 92.2 96.8 93.4 93.4 93.8 93.4 Figure 5. The positioning accuracy versus different heat kernel parameter t 图5. 不同热核参数 t下的定位准确率 0 20406080 nu 100 m b e r of trainin g sa m p les 76 80 84 88 92 96 100 accu r acy (% ) 79.8 83.4 81 85.6 90.8 92.2 93 93.6 97.6 96.8 Figure 6. The positioning accuracy versus number of the training samples, as the number of s e l e cted comp o n ents is d = 3 图6. 选择 3个主成份个数情况下，不同训练笔数的定位准确率 故可以利用较少的训练向量也能达到较高的定位准 确率，大幅节省事先收集数据的所需的时间。 4. 结论 利用局部保持投影法将无线网络接收到之讯号 强度值做前置处理，降低原始接收到的讯号维度，藉 此减少定位时的计算量。其中本研究的定位算法必须 事先收集训练向量来建立原始数据库，若我们能够减 少训练讯号的样本数并维持定位准确率，将能够节省 我们事先收集训练向量的时间，实验结果显示，应用 LPP 可以大幅减少定位计算量，且仅需要大约 50 笔 的训练向量即可达到 90.80%的准确率，大幅减少每个 地点的收集量，节省事先收集的工作量，从实验结果 可知此算法应用于室内定位是可行的。 5. 致谢 感谢我的导师李坤洲教授，在我遇到有疑问时， 适时给予我论文上的建议，并在教授的细心指导与帮 助之下，使本论文内容能够更加完整与严谨，在此致 上最诚挚的谢意。 参考文献 (References) [1] G. G. Raleigh, T. Boros. Joint space-time parameter estimation Copyright © 2012 Hanspub 37  应用局部保持投影法于无线网络室内定位 Copyright © 2012 Hanspub 38 for wireless communication channels. IEEE Transactions on Signal Processing, 1998, 46(5): 1333-1343. [2] A. L. Swindlehurst. Time delay and spatial signature estimation using known asynchronous signals. IEEE Transactions on Signal Processing, 1998, 46(2): 449-462. [3] M. Wa x, A. Leshem. Joint estimation of time delays and directions of arrival of multiple reflections. IEEE Transactions on Signal Processing, 1997, 45(10): 2477-2484. [4] K. Kaemarungsi, P. Krishnamurthy. Properties of indoor received signal strength for WLAN location fingerprinting. Proceedings of the First Annual International Conference on Mobile and Ubiquitous System: Networking and Services, 2004. [5] K. Kaemarungsi, P. Krishnamurthy. Modeling of indoor positioning systems based on location fingerprinting. Proceedings of the IEEE INFOCOM, 2004, 2: 1012-1022. [6] T. K. Moon, W. C. Stirling. Mathematical methods and algo r i t hms for signal processing. Upper Saddle River: Prentice Hall, 2000. [7] R. E. Ziemer, W. H. Tranter. Principles of communications: Systems, modulation, and noise. New York: John Wiley & Sons, 2002. [8] X. F. He, P. Niyogi. Locality preserving projections. Advances in Neural Information Processing Systems, Vol. 16, Cambridge: MIT Press, 2003. [9] M. Belkin, P. Niyogi. Laplcian eigenmaps for dimensionality reduction and data representation. Neural Computation, 2003, 15(6): 1373-1396. [10] J. Yang, D. Zhang, J. Y. Yang, et al. Globally maximizing, locally minimizing: Unsupervised discriminant projection with applications to face and palm biometrics. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007, 29(4): 650- 664. |