 Electromagn etic Analysis and Applications 电磁分析与应用, 2013, 2, 25-30 http://dx.doi.org/10.12677/eaa.2013.22004 Published Online April 2013 (http://www.hanspub.org/journal/eaa.html) Localization Analysis Based on Maximum Scatter Difference in Indoor WLAN Environments 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: Jan. 7th, 2013; revised: Jan. 23rd, 2013; accepted: Feb. 3rd, 2013 Copyright © 2013 Jia-Han Jan, Kun-Chou Lee. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Abstract: In this paper, we utilize Maximum Scatter Difference (MSD) for indoor localization over Wireless Local Area Network (WLAN) received signal data. Maximum Scatter Difference can solve the singular matrix problems by linear discriminant analysis calculates the inverse matrix of within-class scatter matrix. The objective functions of Maximum Scatter Difference are to maximize the inter-class scatter matrix and minimize the within-class scatter matrix. Therefore, Maximum Scatter Difference cannot need to construct the inverse matrix of within-class scatter matrix. It can avoid the singular matrix problems. We utilize location fingerprinting approaches for indoor localization. The ap- proaches are divided into two parts including off-line and on-line stages. In the off-line stage, we collected received signal data are projected onto the feature space of Maximum Scatter Difference. In the on-line stage, we receive real-time signal data compared with the off-line stage that was collected data using Maximum Likelihood (ML) to esti- mate current location. Maximum Scatter Difference applied to indoor WLAN localization that not only avoids the sin- gular matrix but also reduces the localization computation. From Simulation results show that this algorithm can be implemented. Keywords: Maximum Scatter Difference; WLAN; Indoor Localization 利用最大散度差于室内无线网络 定位分析 詹佳翰，李坤洲 国立成功大学系统及船舶机电工程学系，台南 Email: jch615@hotmail.com, kclee@mail.ncku.edu.tw 收稿日期：2013 年1月7日；修回日期：2013年1月23 日；录用日期：2013年2月3日 摘 要：在本研究中将最大散度差应用在无线网络室内定位上，最大散度差主要是可以解决线性鉴别分析在计 算类内散度矩阵时所遭遇的奇异性矩阵问题，它是利用类间散度矩阵与类内散度矩阵之差作为目标函数，由于 不需要构造类内散度矩阵的反矩阵，故可以避免掉奇异性矩阵的问题。本研究中其定位的方式是透过指纹特征 比对法的概念来进行定位，共分为两个阶段：在离线阶段，利用最大散度差将原始讯号数据库作前置处理；在 在线阶段，将接收到的实时讯号数据利用最大似然法计算出目前接收讯号的所在位置。将最大散度差应用于室 内无线网络进行定位，不仅可以避免奇异性矩阵的问题并且还可以降低定位时的计算量，从实验结果得知此应 用是可以实行的。 关键词：最大散度差；无线网络；室内定位 Copyright © 2013 Hanspub 25  利用最大散度差于室内无线网络定位分析 Copyright © 2013 Hanspub 26 1. 引言 在图样辨识领域当中，线性鉴别分析(Linear Dis- criminant Analysis, LDA)[1-3]一直是大家公认非常重要 的算法之一，其被广泛应用在人脸图像辨识领域上， LDA 其主要的目的是目标是寻找一个最优的投影方 向，样本数据在该方向上的投影能够让不同类别的类 间散度距离拉大，并且能使相同类别内的类内散度距 离缩小，如此一来便能增加类别数据的分群能力。但 是LDA 算法在应用时遇到计算类内散度矩阵的反矩 阵时，容易遇到奇异性矩阵的问题而造成无法求解。 为了避免此奇异性矩阵的问题，本文中引用的最大散 度差(Maximum Scatter Difference, MSD)算法[4-6] 与 LDA 算法很相似，但是 MSD和LDA 算法的不同之 处在于可以解决奇异性矩阵的问题，它是利用类间散 度矩阵与类内散度矩阵之差作为目标函数，由于不需 要构造类内散度矩阵的反矩阵，故可以避免计算类内 散度矩阵遭遇到奇异性矩阵的问题。 在此研究中，其定位方式是引用指纹特征比对法 的概念[7,8]来进行室内定位，其中流程就跟在比对人类 指纹时相同，共分为两个阶段，分别是训练(即离线阶 段)和测试(即在线阶段)，离线阶段是在选定的参考位 置上收集来自各个讯号来源(Access Point, AP)的强度 值(dBm)储存至数据库，在训练(即离线阶段)透过最大 散度差法此算法将数据库内数据作前置处理，将其特 征提取出来投影至特征空间，藉此降低原始数据库的 维度，减少定位时的计算量；接着测试(即在线阶段) 将接收到的实时讯号同样投影至特征空间，然后透过 最大似然法(Maximum Likelihood, ML)[9,10]与原始数 据投影至特征空间内数据做比对，来估算出目前接收 讯号者的所在位置。此种定位方式的优点不仅能避免 掉多重路径反射对于定位的影响，并且只需要由现在 广泛存在的无线网络和可以接收讯号的接收机器(本 研究是利用笔记型计算机)即可实现，故并不需要额外 的专用设备，可以节省硬件之成本。透过实验结果得 知，将最大散度差此算法应用在室内无线网络定位 上，可以准确的计算出接收讯号者的所在位置，证明 本研究的可行性及高效性。 2. 最大散度差(Maximum Scatter Difference, MSD) 假设我们在其中某个地点接收到的原始讯号来 源(Access Point, AP)维度大小为 D，我们将此讯号定 义为向量 T 12 ,,, D X xx x，接着我们总共收集了L 个地点(Receive position)，所 以有L个类别，而每个类 别中有 Ml笔数据，故所有数据笔数为 1 L l l M M ，我 们将这些M笔数据定义为 ,1,, i X iM，将这些数据 储存至数据库，排序方式如图 1所示。定位主要分为 训练(即离线阶段)和测试(即在线阶段)两个阶段。 在训练(离线阶段)，我们要寻找一个转换矩阵 A ， 投影到特征空间是利用此线性变换即为 T ii YAX，将 原始资料 X 转 为换 1 YyT 2 ,,, d y y，其中 dD， 大散度差的所构造出来的特征空间。 首 转换成最 先计算出每个类别内的数据平均值 1 1l M ,1 ,, li i l mXlL M (1) 接着计算出全部数据的平均值 11 1l M L i li mX M (2) 计算不同类别之间的特征参数散布情况，类间散度矩 阵定义为 T 1 L Bll l l S Mmmmm (3) 而计算同一类别内的特征参数散布情况，类内散度矩 阵为 T 11 l M L Wili li SXmXm l (4) 最大散度差判别准则其目标是寻找一个最优的 投影方向，经过转换矩阵 A 投影至特征空间时，使得 Figure 1. The structure of the database 图1. 数据库之构造图  利用最大散度差于室内无线网络定位分析 不同类别的类间散度最大且同一类别的类内散度最 小，所以最大散度差的目标函数为 T arg maxBW A A SSA (5) 其目标函数最大化可转换为下式(6)广义特征值求解 问题 BW SSA A (6) 在求解目标函数与LDA 在求解时类似，但是 LDA 在 求解时必须计算 1 W S，而从式(6)可以看出MSD 不需 要运算 1 W S，因此 以避免掉奇异性矩阵的问题。接 着我们求特征值方程式的解，算出特征值 i 可 出 和所对 应的特征向量 i A ，其中 1, ,iD ，透过选取前 dd D个最大 正数特征 20 d 的特征向量，经过转换矩 特征空间，投影完后之特征空间如图 2所示，其中选 取的特征值数目对应的特征向量即是主成份的个数。 3. 最大似然法(Maximum Likelihood, ML) 的 所相对应 阵将其投影到MSD 考地 值1 接着在测试(在线阶段)中，我们同样收集各个参 点(即12 ,, , L rr r)的D个讯号来源。将收集到的讯 号投影至MSD 征空间后，可以得到 的特 12 ,,, d Yyy y的矩阵维度，接着使用最 的接收位置坐标。透过贝氏定理 (Bayes’ rule)，我们可以得到事后机率 T大似然法 来估算出目前讯号 i PrY，如下 式(7) ii PrYPYr Pr i (7) 其中 i PYr为似然函数(likelihood fun 示在已 ction)，此机率 函数表知位置 i r中，会发生Y的机率。在本实 Figure 2. The structure of the MSD feature space 图2. MSD特征空间之构造图 验中，我们所取的参考地点都是在一个有限的范围 内，故事前机率 i Pr 可以假设为均匀分布，从式(7) 中可以得知，事后机率 i PrY是取决于似然函数 i PYr 。为了使估算似然函数 i Yr更加容易，通 似然函数 P 常都把 i PYr 假设为 分布(Gaussian distribution) 。意思 个参考地点 高斯 是在各 i r中，Y的每个 主成份都为高斯随机变数。所以第 d个投影特征成份 d y发生在参考地点 i r的机率为： 2 , 2 2, , exp2 2π did iid id PYr (8) 因为讯号 1y Y的每个主成份为统计独立(statistically )，independent 所以可以借由乘上Y的每个不同主成份 的高斯机率来计算出似然函数 i PYr 2 , 2 2 1, , 1 Dd exp ,1, , 2 2π di idid id y PYri L (9) 其中 和2 ,id 是在第 i个参考位置 i r ,id 中，预先测量 Ml个数本投影到 MSD 特征空间算出的平均 值和标准差，如图 3所示。可以将投影至特征空间的 讯号 据样 Y向量，经由式(8)和式(9) ，计算出全部参考位置的 然函数似 i P Yr 并由最大的似然函数值来决定出定 位结果。 为了使 Y 定位结果更准确，我们进一步计算向量 的接收位置坐标，在全部的参考位置中，实际接收位 置坐标可以看作是全部参考位置的加权平均，我们可 以对似然函数 i PYr正规化来算出权重值 1 iL i i wPYr (10) i PYr Figure 3. The mean and standard deviation of each reference in the MSD feature space 图3. MSD特征空间内每个参考地点的平均值与标准差 Copyright © 2013 Hanspub 27  利用最大散度差于室内无线网络定位分析 其中 数 后 i w表示在第i化后的似然函个参考位置，正规 值。最 结果位置的坐标可以由正规化之后的似然函 数值估算出来。 1 L ii i rw r (11) 其中 ,r'x y 即为最后计算出来的位置坐标。 定位的实验位置是位于国 立成 向量所集合 而成 较大，拥有较 高的 4. 仿真结果与分析 本文中室内无线网络 功大学机械工程学系系馆，我们选定了10 个(L = 10)参考地点，位置与位置之间间隔为 10 公尺，然后 我们利用笔记型计算机来接收讯号，在每个参考地点 接收 10个(D = 10)讯号来源(即无线网络接收到的讯 号数目)，并且在每个参考地点收集 150 笔讯号强度 值，每一笔的时间间格为 1秒，我们将它们分成两组 数据，前 100 笔讯号强度值当成训练(即离线阶段)时 所需的训练笔数，而参考地点有10 个，故训练向量 笔数为 1000 笔，并将这些数据放置于数据库，其数 据维度为10 × 1000。而后 50 笔讯号强度值当成测试 (即在线阶段)，测试向量笔数为 500 笔，将其当成测 试定位结果是否正确所需的测试向量。 在本文实验中，我们将收集到的训练 的数据库，利用最大散度差投影至特征空间后便 完成训练步骤，并计算出训练完的平均值及标准差， 以便测试定位结果时所需，接着进行测试步骤，将测 试向量利用最大似然法算出定位的结果，其中整个室 内定位算法的流程图，如图4所示。 本研究中，由于原始数据库数据量 维度，故将原始数据库利用最大散度差算法投影 至特征空间，透过选择不同的主成份个数藉此降低原 Figure 4. The flow chart of indoor positioning for MSD 图4. 最大散度差室内定位算法之流程图 始数 的 皆以训练向量为 100 笔进行训 练， 据库的维 ，当中我们选取前几个较具有特征度 主成份，使得在定位计算时可以减少计算量，执行速 度加快，同时达到高准确率。由如图 5所示，主成份 个数选择 3个(d = 3)和4个(d = 4)主成份时，定位准 确率分别为 94.4%和96.6%，所以我们只需要选择 3 个(d = 3)主成份即可达到九成(94.4%)以上的定位准 确率，相较于原本接收到的原始数据库(D = 10)，减 少了七成的计算量，达到在降低数据库维度的同时还 拥有高定位准确率。 上述的定位结果， 在本研究中，其定位方式是引用指纹特征比对法 的概念，必须在每个参考地点事先收集训练向量，在 离线阶段时需要耗费大量的收集时间，因此若能减少 收集训练向量笔数及时间，可提升定位的整体效率， 故减少训练向量的笔数对照其定位准确率，如图 6所 示。当中分别取 10笔、20 笔…到100 笔训练笔数做 训练，主成份个数我们取 3个(d = 3)的情况下，其不 同的训练笔数定位准确率，训练笔数取 20 笔、30 笔、 40 笔时准确率分别为89.20%，91.20%及92.60%，只 需取 30笔的训练向量，其定位准确率即可达到 90% 以上，大幅节省离线阶段事先收集数据的时间，从结 果来看，使用较少的训练向量依然可达到高定位准确 率。 123456 number of dimensions 60 70 80 90 100 63.6 88.6 94.4 96.6 98.2 97.8 accuracy(%) Figure 5. The positioning accuracy versus number of the principa components l 图5. 选择不同主成份个数的定位准确率 Copyright © 2013 Hanspub 28  利用最大散度差于室内无线网络定位分析 0 20406080 number of thetraining samples100 80 84 88 92 96 100 accuracy(%) 83 89.2 91.2 92.6 96.4 96.2 95.6 95.4 95.2 94.4 Figure 6. The positioning accuracy versus number of the training samples, as the number of selected components is d = 3 选取的讯号接收位置彼此之间的距 离为 图6. 选择 3个主成份个数情况下，不同训练笔数的定位准确率 在本文中所 10 公尺，当中我们将实际坐标 , x y和式(10)及 式(11) 所计算得知的估算 坐标 , x y 间的距离 来当作定位误差，此距离 是用欧氏距离来计算。 两者之 22 x xyy (12) 本文中相邻两个讯号接收位置的 意即 所应用的MSD 与LDA 很相似，两种算法 不同 间距为 10 公尺， 当定位误差小于 5公尺内即视为成功辨识，当定 位误差越小时，成功辨识的条件便更不易达到，在主 成份个数依然选取 3个(d = 3)的情况下，定位误差在 5公尺范围内，计算出不同定位误差所对应到的定位 准确率，如图 7所示。选择定位误差为 2.5 公尺、3 公尺、3.5公尺时定位准确率分别为 90.8%，91.6%， 91.8%，其中定位误差取的距离越小时，代表所预估 出来的位置与真正的实际位置必须更加接近才可以 成功辨识，从结果可得知，我们将定位误差仅取 2.5 公尺，表示每次所预估出来的估算位置与真正的实际 位置之间的距离都在 2.5公尺以内时，其成功辨识的 正确率为 90.8%，依然可以达到九成以上的高定位准 确率。 5. 结论 本研究 之处在于 MSD 可以解决奇异性矩阵的问题，它 2345 error distance(m) 89 90 91 92 93 accu r ac y (%) 89.8 90.8 91.6 91.8 91.8 92.4 92.6 Figure 7. The positioning accuracy versus different error distanc 利用类间散度矩阵与类内散度矩阵之差作为目标 国家科学委员会补助专题研究计划 NSC 参考文献 (References) ha and D. J. Kriegman. Eigen- tions Pattern Analysis and Ma- e 图7. 选取不同的定位误差的定位准确率 是 函数，由于不需要构造类内散度矩阵的反矩阵，故可 以避免计算类内散度矩阵遭遇到奇异性矩阵的问题。 本研究中应用 MSD 到室内无线网络定位上，实验结 果证明，只需选取3个主成份个数便可以达到94.4% 的定位准确率，大量减少定位时的计算量，并且只需 取30 笔训练向量一样可以达到九成以上的高准确率， 减少事先收集数据库的时间，并且透过不同的定位误 差距离来看出其定位的准确率，从以上实验结果得知 将最大散度差应用于室内无线网络定位是可以实行 的。 6. 致谢 感谢行政院 99-2221-E-006-244-MY3 经费补助支持。并感谢 我的导师李坤洲教授以及实验室学长，在本研究过程 中，适时给予我研究上的建议，使本论文内容能够更 加完整与严谨，在此致上最诚挚的谢意。 [1] P. N. Belhumeour, J. P. Hespan faces vs. Fisherfaces recognition using class specific linear pro- jection. IEEE Transactions Pattern Analysis and Machine Intel- ligence, 1997, 19(7): 711-720. [2] D. L. Swets, J. J. Weng. Using discriminant eigenfeatures for image retrieval. IEEE Transac Copyright © 2013 Hanspub 29  利用最大散度差于室内无线网络定位分析 Copyright © 2013 Hanspub 30 algorithm on angular- n. IEEE Transactions on Neu ure extraction and its applica- margin linear projection and support vector eived marungsi, P. Krishnamurthy. Modeling of indoor posi- athematical methods and algo- iemer, W. H. Tranter. Principles of communications: Sys- chine Intelligence, 1996, 18(8): 831-836. [3] K. C. Lee, L. T. Wang, J. S. Ou and C. W. Huang. Radar target recognition by using linear discriminant diversity RCS. Journal of Electromagnetic Waves and Applica- tions, 2007, 21(14): 2033-2048. [4] H. Li, T. Jiang and K. Zhang. Efficient and robust feature extrac- tion by maximum margin criterioral tioning systems based on location fingerprinting. 23rd Annual Joint Conference of the IEEE Computer and Communications Societies, 2004, 2: 1012-1022. [9] T. K. Moon, W. C. Stirling. M Networks, 2006, 17(1): 157-165. [5] J. G. Wang, Y. U. Lin, W. K. Yang and J. Y. Yang. Kernel maxi- mum scatter difference based feat tion to face recognition. Pattern Recognition Letters, 2008, 29 (13): 1832-1835. [6] F. X. Song, C. Ke, Y. J. Yu and L. S. Hai. Maximum scatter difference, large tems machines. Acta Automatica Sinica, 2004, 30(6): 890-896. [7] K. Kaemarungsi, P. Krishnamurthy. Properties of indoor rec signal strength for WLAN location fingerprinting. Proceedings of the First Annual International Conference on Mobile and Ubiquitous System: Networking and Services, Boston, August 2004. [8] K. Kae rithms for signal processing. Upper Saddle River: Prentice Hall, 2000. [10] R. E. Z , modulation, and noise. Wiley, 2010. |