一种基于多维标度和区域细化的无线室内定位方法-肖亚龙.pdf

《一种基于多维标度和区域细化的无线室内定位方法-肖亚龙.pdf》由会员分享，可在线阅读，更多相关《一种基于多维标度和区域细化的无线室内定位方法-肖亚龙.pdf（15页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第40卷第8期 计 算 机 学 报 v0140 No82017年8月 CHINESE JOURNAL OF COMPUTERS Aug2017一种基于多维标度和区域细化的无线室内定位方法肖亚龙 张士庚 王(中南大学信息科学与工程学院长沙建新410083)摘 要移动用户的位置信息成为许多基于位置应用的内在驱动力基于指纹的wLAN定位方法因在定位精度、定位复杂性以及定位成本等方面的优势，近年来成为室内定位研究领域的热点然而，由于需要在训练阶段采集大量的参考点指纹信息，这类方法在大规模环境下的应用受到了很大的限制该文提出一种基于多维标度(Multidimensional scaling，MDS)技术

2、的室内定位算法，能够有效减少训练阶段指纹采集的开销该方法利用不同位置之间的信号强度差异来表征对应的物理空间距离，并以此为基础利用多维标度技术计算目标对象的位置提出一种区域细化的方法来进一步提高定位精度，在获取目标对象的近似位置后，通过缩小目标对象所在的可能区域并利用离其最近的参考点来对其位置进行迭代计算，有效提高了定位精度在多个实际场景中的测试结果表明，相比于已有工作，该文所提出的算法有效降低了所需的参考点个数，并达到了与已有算法类似甚至更高的定位精度关键词室内定位；指纹定位；接收信号强度；多维标度；区域细化；物联网；信息物理融合系统中图法分类号TP393 DOI号1011897SPJ1016

3、201701918An Indoor Localization Algorithm Based on Multidimensional Scalingand Region RefinementXIAO YaLong ZHANG ShiGeng WANG JianXin(School of Intormation Science and Engineering，Central South University，Changsha 410083)Abstract The position information 0f mobile users becomes the internal motivat

4、ion to manylocations based applications，such as indoor navigation，travel application and mobile advertisingserviceFingerprintingbased indoor localization has been a hot topic in localization research inrecent years due to its high accuracy，low complexity and low costThis method，however，requires coll

5、ecting a large number of reference point information in the offline training phase，which greatly limits its application in large environmentsThis paper proposes a new indoorlocalization algorithm based on multidimensional scaling(MDS)，which utilizes the distancebetween two pointsreceived signal stre

6、ngth vectors to approximately measure their distance inphysical environment，and then calculates the target obj eetS location with the distanceconstraints with MDSWe further propose a region refinement method to improve the localizationaccuracy，in which only reference points contained in a small rect

7、angle that contains the estimatedposition of the target obj ect are used to calculate the targetS locationExperiment results in tworeal environments and large scale simulations demonstrate the usefulness of our approachTheresults show that，compared with the Horus algorithm，the proposed algorithm can

8、 achievesimilar or even higher accuracy and reduce the number of required reference points by almost oneorder of magnitudeThe effectiveness of the proposed algorithm is validated via largescalesimU】ati on收稿El期：20151230；在线出版El期：20160518本课题得到国家自然科学基金面上项目(61173169)、国家自然科学基金青年项目(61402056)、湖南省研究生科研创新项目(1

9、50140006)资助肖亚龙，男，1985年生，讲师，主要研究方向为室内定位、无线感知E-mail：xiaoyalon92006163corn张士庚(通信作者)，男，1981年生，博士，副教授，中国计算机学会(CCF)会员，主要研究方向为物联网、无线感知、无线定位、RFID系统Email：sgzhangesueduca王建新，男，1969年生，博士，教授，中国计算机学会(CCF)高级会员，主要研究领域为网络协议、网络优化、算法分析、生物信息学万方数据8期 肖亚龙等：一种基于多维标度和区域细化的无线室内定位方法Keywords indoor localization；fingerprinting

10、 localization；received signal strength indicator；multidimensional scaling；region refinement；Internet of Things；CyberPhysical System引 言随着无线网络、移动智能终端的广泛普及和迅猛发展，移动用户对信息的即时性和就地性提出了越来越高的需求越来越多的智能应用需要获取移动终端的实时位置信息然而，相比于室外环境，室内环境中的精确定位技术仍然是一个具有挑战性的问题在开阔的室外环境中，全球定位系统(GlobalPositioning System，GPS)1、网络辅助全球卫星定

11、位系统(Assisted Global Positioning System，AGPS)23和蜂窝网定位系统等可以满足绝大部分应用的定位需求但是，在室内环境中，由于建筑物的遮挡以及无线信号的多路径传播等问题，使得GPS等已有室外定位系统不再适用研究并实现基于移动终端的室内定位系统，使之能在复杂的室内环境中(如机场候机楼、大型商场、地下停车场、矿井等)对目标对象提供高精度的实时定位服务，是当前一个很重要的研究课题目前，基于无线局域网(Wireless Local AreaNetworks，wLAN)的室内定位由于只利用现有的网络基础设施和移动终端，且能实时地提供较精确的室内位置信息，得到了广泛关

12、注按照定位原理划分，WLAN室内定位技术可以分成两大类：基于传播模型的定位和基于指纹的定位基于传播模型的定位方法31的思想是根据无线电信号的传播模型，将用户测得的接收信号强度值(Received SignalStrength Indicator，RSSI)映射成到对应的无线接入点(Access Point，AP)的距离若在二维平面中可以获取到3个以上已知位置的AP的距离，即可通过三边定位原理估算出用户位置但在室内环境中，由于无线传播的多径现象，RSSI有可能不再随传播距离增加而单调递减，利用传播模型估算距离时，极易产生误差，所以基于传播模型的定位方法的定位精度有限基于指纹的定位方法4主要分为两

13、个阶段，离线阶段和在线阶段其思想是在离线阶段采集各个参考点位置的RSSI样本，连同对应的参考点位置构建指纹数据库；在在线阶段，将移动终端(待测用户)实时测量得到的RSSI与离线阶段建立的指纹数据库匹配并计算定位结果。由于指纹数据库的RSSI样本是在实际环境中获得的，指纹定位法的定位精度明显高于传播模型法5然而，指纹数据库的构建需要在大量的参考位置上进行信号强度采样，较大的工作量限制了这类方法在大范围室内环境下的使用因此，如何在维持较高的定位精度的同时，能够大幅减少参考点样本采集工作量，是指纹定位技术的研究重点我们发现，当室内环境中每个位置能够收到足够数目(比如，4个以上)的AP信号时，任意两个

14、位置之间的物理距离与在这两个位置上获取的信号强度向量之间的差异存在着很强的相关性也就是说，对两个位置对(P，P。)和(P。，P。)来说，如果P，P：之间的信号强度向量差异大于P。P；之间的信号强度向量差异，那么P，P。之间的物理距离也极有可能大于P3Pa之间的物理距离；反之亦然基于这个现象，我们可以利用待测点与参考点的信号强度向量差异来表征其到不同参考点的距离远近在此基础上，我们就可以利用到给定参考点的距离远近关系来较为准确地计算待测点的位置根据上述思想，本文提出一种基于多维标度(Multidimensional Scaling，MDS)60分析技术的新颖室内定位算法，该算法能够利用比传统指纹

15、定位算法少较多的参考点信息来有效计算待测点位置首先通过计算待测点与各个参考点之间的信号强度差异来获取其到各个参考点的距离远近信息，然后利用MDS算法计算待测点与各个参考点的相对位置，最后利用参考点位置信息计算待测点的绝对位置信息为了进一步提高定位精度，本文在上述算法的基础上提出了分层次缩小区域的定位策略其基本思想是根据参考点的位置对区域进行划分，首先利用所有参考点估算出待测点所属的区域，然后根据估算出的位置所属区域内的参考点对待测点位置进行优化，最后实现更精确的定位实际环境实验结果和仿真结果均表明，本文所提出的算法能够达到与已有算法类似或更高的定位精度，但所需要的参考点数目比已有算法要少较多本

16、文的主要贡献如下首先，我们定量验证了当部署区域内存在足够多个无线接入点时，不同位置所采集的信号强度向量之间的距离可以有效表征它们之间的物理距离远近，根据此结论说明可以采用多维标度分析技术的算法来计算待测点的位置然万方数据计 算 机 学 报后，验证基于多维标度分析技术的定位算法存在着两个性质：一是定位误差的大小与使用的参考点集合有关；二是待测点定位误差与其相对于区域的位置有关基于这两个性质，我们提出一个基于分层次缩小区域的定位算法，在使用较少参考点的前提下进一步提高了定位精度，从而解决指纹定位法在大规模环境中由于指纹采集工作量大而无法应用的问题本文第2节对相关工作进行介绍；第3节是本文的预备知识

17、；第4节对本文提出的定位算法给出具体描述和分析；实际实验和仿真实验的结果在第5节给出；最后在第6节进行总结2 相关工作一般来说，无线室内定位模式首先获得无线信号的物理测量值，然后通过基于传播模型的方法或者基于指纹的方法来计算待测点的位置所利用的物理测量值包括时间口_8、角度9-u3和功率121 8I其中基于时问的物理测量值通常包括到达时间(Timeof Arrival，TOA)和到达时间差(Time Differenceof Arrival，TDOA)，基于功率的物理测量值包括接收信号强度和信道状态信息(Channel State Information，CSI)口列的定位方法基于时间和角度的

18、测量值大都需要使用专用的硬件测量设备由于RSSI可以通过无线网络适配器直接测量，无需额外的专用硬件设施，能够较好地适用于大范围的室内环境，因此基于RSSI的室内定位技术近年来引起了人们广泛的关注按照定位原理划分，WLAN室内定位技术可以大致分成两类：传播模型法口0。223和指纹定位法n2。132争2引由于室内无线信号通常采用高频信号(24 GHz或5 GHz)进行传输，容易受到人员走动的干扰，使得基于传播模型的室内定位方法的精度通常不是很高针对室内无线信号传播模型难以估计的问题，Mazuelas等人口o提出了一种将传播模型的参数随着接收到的信号强度特征的变化进行自适应更新的方法Chang等人2

19、u提出了一种使用同一位置不同AP的信号强度差值来消除环境的干扰从而提高定位精度的方法Narzullaev等人心幻提出了一种考虑室内环境布局等因素的无线传播模型，提高了室内定位系统的准确度Xiao等人口71考虑到室内环境中RSSI具有不确定性，提出了一种基于CSI的传播模型，相比于基于RSSI的传播模型，达到了更高的定位精度，但目前CSI的获取需要特定的网卡设备使用传播模型法需要知道无线接入点的位置，而无线接入点的位置在很多情况下是较难获取的，因为不同的无线接入点可能是由不同的人或组织部署的，基于指纹的定位方法不需要知道无线接入点的位置另外，由于指纹数据库中的RSSI样本是在实际参考点上采集获得

20、的，指纹定位法的定位精度明显高于传播模型法针对基于WLAN的指纹定位技术，研究人员已从各个不同方面进行了研究2000年，美国微软研究院首先提出了命名为RADAR121的WLAN室内定位系统该系统事先在建筑物内部固定3个位置已知的基站移动点通过两个步骤获取自身位置：第1步进行离线指纹数据收集，在选定的参考点测量对应基站的信号强度，并存入指纹数据库中第2步进行在线实时定位在移动过程中测量基站的信号强度信息，并与指纹数据库中存储的指纹进行比较，根据接收信号的强度找出最为接近的K个参考点，将它们的平均位置作为节点当前的位置在指纹数据库中节点间隔至少25m且不规则分布的情况下，RADAR系统的定位精度在

21、2 m3 m之间美国马里兰大学计算机系的Youssef等人13提出了Horus系统与RADAR系统类似，Horus系统也是在离线阶段在选定的参考点上采集并记录各AP的信号强度值Horus系统与RADAR系统的不同之处在于，其并不对全部采样值进行平均处理，而是生成各个AP的RSSI在参考点上的分布直方图在离线阶段提出聚类分块的概念，将具有相似RSSI信号特征的参考点划分为一簇，即一个定位子区域在在线定位阶段，先通过聚类分块将用户粗略定位至某个定位子区域，再进行精确定位文献13中报告的Horus的平均定位精度可以达到08m，但是在其它环境中z8Horus的定位精度有可能显著降低文献E29提出了一种

22、基于支持向量回归的80211无线室内定位方法，文献30提出了一种抗多径和阴影的视距指纹定位算法但是这些方法没有考虑如何减少指纹采集工作量上述方法均需要在训练阶段采集大量的参考点信号强度信息，不适用于大范围的室内环境定位指纹采集工作量主要取决于参考点的密度以及每个参考点所需的采样时长通过加大参考点采集间隔和减少采样时长，可以有效降低采样开销，但是同时也可能无法保证RSSI信号对物理位置空间刻画的精细度文献26在已经获得的少数指纹信息的基础万方数据8期 肖亚龙等：一种基于多维标度和区域细化的无线室内定位方法 1921上采用插值法来重建指纹数据库，从而达到减少指纹采集工作量的目的但是这种人为的对数据

23、库进行插值，可能会带来不可靠的信息，本文所使用的指纹数据均是实地采集为了减少离线阶段指纹收集的工作量，研究人员还提出了基于“众包(Crowdsourcing)”的指纹收集方式wu等人心铂和Yang等人心明指出在创建指纹库时不需要大量的现场勘测，只需人员持有移动设备在室内随机走动即可完成指纹库的数据采集通过对采集到的数据和室内结构进行匹配，他们所提出的方法分别达到了86的平均房问级别准确率和588 m的平均定位误差但是这种方式需要激励用户参与指纹数据库的创建，并且可能会产生大量的冗余数据还有研究人员提出有效利用移动设备中各种传感器的数据来取代指纹的收集Chintalapudi等人2朝提出了一种利

24、用地标点(包括种子地标点和有机地标点)的位置信息和采集到的各种传感器信息，通过Deadreckoning来推算当前位置信息的方法该方法在不需要地图信息以及对室内环境进行标注的情况下完成定位，主要利用了很多传感器获得的信息实验得出在实时定位情况下，中值定位精度为169rrt但是这种方式的定位精度取决于室内地标点的个数，并且无线AP覆盖的范围不能太大最近有研究人员利用相邻位置的RSSI固有的空间相关性，提出一种基于流形对齐的定位方法3“此方法首先获取一个具有RSSI空间相关性的数据集，再根据一部分参考点信息，通过半监督学习算法得出待测点的位置但是这种方式的定位方法需要对异常值进行过滤，且计算较复杂

25、3 预备知识在室内环境中，无线信号的强度会受到多径传播和阴影效应的影响而变得难以预测，通常使用对数距离模型3胡来表示信号传播的损耗设接收节点和发射节点之间的距离为d，则信号在传播过程中导致的损耗可以表示为PL(d)一PJ(d。)+lOnlog(dd。)+X。 (1)其中d为发射节点与接收节点之间的距离m；咒为路径损耗指数，表示路径损失随距离增加而增长的快慢，与周围环境有关；X。是以分贝为单位的零均值，标准差为d的高斯分布随机变量；d。为参考距离，通常取1 m(本文以下内容也取此值)，Pc(磊)表示参考距离为d。时的路径损耗接收端接收到的信号强度为RSSIP。一PL(d) (2)其中P，表示信号

26、的发射功率；P。(d)为经过距离d后的路径损耗根据上述理论模型，对单个AP而言，接收端读取到的RSSI值的大小和距离该AP的远近密切相关然而，如图1所示，对单个AP而言，不同位置对之间的信号强度差值并不能有效表征它们之间距离的远近比如，图1中A、C的距离远大于A、B之间的距离然而，根据前述信号传播理论，A、C两点接收到的信号强度差值要小于A、B两点接收到的信号强度差值当AP数目较少时，该问题仍然存在I，25AP3俐1 仿其实验I刳列i当系统中的AP数目增加时，不同位置对之间获取到的信号强度向量的差异与其对应的实际物理距离之间的一致程度会增强，也就是说，两个位置相距越远，在这两个位置上获取到的信

27、号强度向量之间的距离也会较远，反之亦然接下来我们分析在多个AP的情况下，不同位置对之间的信号强度距离与实际物理距离之间的关系假设区域中的每个点都能接收到N个AP的信号，那么A位置获取到的信号强度值向量可表示为昭_sJA一RSSIAl，RSSIAz，RSSIAN(3)其中RSSIA，一P。一PL：(d。)一10nlog(dA：d。)一x。：，1iN，d。：为A位置到第i个AP的距离，P。P。：(威)分别为第i个AP的发射功率和近地参考点功率由于每个AP的发射功率和近地参考点功率不变，可将式(3)表述为RN$IA一APl一10nlog(dAl)+X，t，AP 2一lOnlog(dA2)+X。2，

28、L4 J-APN一10nlog(dN)+X。N其中AP。一P，：一P。(d。)，1iN类似的，我们可以写出在B，C两位置上读取到的信号强度向量万方数据计 算 机 学 报由式(4)可得A，B两点读取到的信号强度向量之间的欧几里得距离为RSSIAB一善(10咒log瓦dBi艄)。 (5)其中dAi和d。：分别为A，B位置到第i个AP的距离，liN为了验证前述推论，我们用两个指标来表征不同位置对之间的信号强度差异与实际物理距离之间的一致程度第一个指标是皮尔逊相关系数，即计算不同点对之间的信号强度向量之间的距离和物理距离之间的相关性皮尔逊相关系数表示了两组数据之间的线性相关程度其次，我们定义两组数据之

29、间的一致性系数指标如下定义1(一致性系数) 给定区域中的九个点，定义在这7个点上的信号强度向量距离和物理距离的一致性系数用如下公式计算sign(RSSI。一RSSIz)*(d。，一d“)一1_一其中sign cz，一：三兰：,RSSI。可通过式c 5，获得，d，为i，歹两位置的欧几里得距离从定义中可以看出，一致性系数表现为所有可以进行比较的点对之间物理距离和信号强度向量距离一致的点对数占点对总数的比例，其中分子是所有可以进行比较的点对之间物理距离和信号强度向量距离一致的点对数，分母是点对总数，所以它的取值在0和1之间这里“一致”的含义为若点对(A，B)之间的物理距离大于(或小于)点对(C，D)

30、之间1OO8趟06籁04O2OAP数目(规则部署)(a)一致性随AP数目变化曲线的物理距离时，其对应的信号强度向量距离也同时大于(或小于)点对(C，D)之间的信号强度向量距离与皮尔逊相关系数不同，一致性系数并不能表示两组数据之间的线性相关性，仅能够表示对应的数据是否满足顺序性设计这样一个指标的原因是因为有些算法并不要求数据之间存在线性相关性，仅要求顺序一致，如非度量多维标度方法6我们利用仿真实验和实际环境中所得的数据来探讨当系统中部署有多少AP时不同位置之间的信号强度差异才能有效表征它们之间的物理距离在仿真实验中，我们将不同数目的AP部署在一个20ITI20m的区域中在部署区域中随机产生100

31、个点对任意两个点，我们通过式(5)计算它们之间的信号强度向量距离，并且利用它们的坐标计算它们之间的物理距离由于共有100个点，我们可以得到MC；。一4950个不同的点对，即我们可以得到两组数据，每组含有4950个数据第1组数据中包含的是点对之间的物理距离，第2组包含的是在对应的位置上获取到的信号强度向量的距离通过计算这两组数据之间的皮尔逊系数和一致性系数(见定义1)，我们可以判断出当系统中部署多少个AP时可以利用信号强度差异来表征物理距离我们对不同的衰减因子，考虑了AP在规则部署和不规则部署(AP随机部署在区域中)两种情况下，对一致性系数和相关性系数随AP数目变化进行了仿真实验仿真实验的结果如

32、图2(AP规则部署)和图3(AP不规则部署)所示从实验结果可以看出，在两种部署情况下，物理距离和信号强度向量距离之间的一致性和相关性都随着AP个数的增加而增高，并且随着衰减因子的变大而变小我们还发现当AP在区域中规则部署时，对应的两个指标值1008蛆06涮罂O402O图2仿真实验结果(AP规则部署)AP数目(规则部署)(b)相关性随AP数目变化曲线100万方数据8期 肖亚龙等：一种基于多维标度和区域细化的无线室内定位方法趟豁1 4 16 49AP数目(非规则部署)(a)一致性随AP数目变化曲线l 4 16 49 100AP数目(非规则部署)(b)相关性随AP数目变化曲线图3仿真实验结果(AP非

33、规则部署)均高于AP非规则部署时的指标值从图中结果我们可以看出，当系统中的AP数目高于4时，信号强度向量之间的距离就能够很好地表征不同位置之间的物理距离(皮尔逊系数大于08意味着两组数据之间存在着极强线性相关)在仿真中我们将阴影效应的标准偏差设为4AP的个数为了验证在实际环境中该结论是否也成立，我们利用在两个不同实际场景下(图10所示)收集的数据也统计了不同点对之间的物理距离和信号强度向量距离之间的一致性系数和相关性系数，具体结果如图4和图5所示图4所示的数据结果对应图10(a)中的实验场景，图5的数据结果对应的是图AP的个数(a)一致性随AP数目变化曲线 (b)相关性随AP数目变化曲线图4实

34、验结果(部署4个AP的实验室场景(156m72m)AP的个数(a)一致性随AP数目变化曲线AP的个数(b)相关性随AP数目变化曲线图5实验结果(部署6个AP的整个楼层场景(336 rn144m)万方数据计 算 机 学 报10(b)中的实验场景在图10(a)中，由于我们在实际环境中部署了4个AP，所以AP数为1和3时对应有4个值，AP数为2时有6个值，AP数为4时有1个值，因此得到图4(a)和(b)中所示的带标准差的曲线图在图10(b)中，我们共部署了6个AP，因此得到图5(a)和(b)中所示的曲线图从图4和图5中可以看出，在实际数据中两点之问RSSI距离和其物理距离也有较高的一致性和相关性，并

35、且随着AP数目的增多，一致性系数和相关性系数都增大根据前述仿真实验和实际实验的统计结果，我们有如下结论：当区域内每个位置能够收到足够数目(比如，4个以上)的AP信号时，对任意两个点对来说，在对应的位置上观察到的信号强度向量之间的距离可以有效地用来表征它们之间物理距离的远近基于这个结论，我们就可以根据待测点与参考点的信号强度向量距离大小关系，来判断待测点与参考点在物理位置上的远近关系在下一节，基于上述结论，我们根据待测点与参考点的信号强度向量之间的欧几里得距离的大小关系得出它们在物理位置上的远近关系，并提出一种基于多维标度分析技术的定位方法来计算待测节点的位置我们还提出了一种分层次缩小区域的优化

36、方法来进一步提高定位精度，具体在下一节介绍算法1 基于MDS的定位算法输入：待测点的RSSI向量，参考点的坐标及RSSI向量输出：待测点的坐标1计算m个参考点的RSSI向量之间的欧几里得距离，记为P，并计算待测点与各个参考点的RSSI向量之间的欧几里得距离，得到参考点、待测点的RSSI距离矩阵，记为P(。+1)(。+1)；2将P作为MDS算法的输入，进行降维处理，得出参考点、待测点的相对位置坐标，记为X。+。；3根据m个参考点的相对坐标x和其绝对坐标，利用坐标转换算法，得出平移向量t、翻转矩阵R和缩放系数s；4根据t，R，S以及待测点的相对坐标，即可求出待测点的绝对坐标4算法描述根据前一节的结

37、果，通过计算待测点到参考点的接收信号强度向量之间的距离，我们可以有效表征待测点到各个参考点的物理距离远近那么基于所获取到待测点和参考点的信号强度向量之间的距离关系，我们可以利用多维标度分析MDS61技术来计算待测点与各个参考点之间的相对位置，然后再通过坐标转换，利用参考点的实际物理位置计算出待测点的绝对位置主要原理是利用MDS技术的特性，即若两个元素相似度越高，那么它们在较低维度空间上的表示点之间的距离也就更加靠近，保证在信息压缩的情况下，还能得到较准确的物理距离关系依据上节结论，我们既可以使用需要知道位置间距离尺度的度量多维标度技术(Metric MDS)，又可以使用仅需要知道距离远近关系的

38、非度量多维标度技术(Non-metric MDS)不失一般性，本文采用度量多维标度技术来计算待测点的位置41基于MDS的定位算法描述算法的基本思想如下首先，我们在选定的参考点处测量对应的信号强度向量连同参考点的坐标存储到数据库中然后，当移动目标需要定位时，采集移动目标的信号强度向量与之前基于指纹的定位算法不同，我们的算法并不直接将测量到的向量与数据库中存储的记录一一比对并查找最接近的参考点，而是通过计算移动目标与参考点之间的信号强度向量距离来近似估计其物理距离，并构建一个距离矩阵来表示移动目标与所有参考点之间的两两距离该距离矩阵表征了移动目标与所有参考点在信号强度空间的相对位置关系然后，我们利

39、用MDS技术来获取移动目标相对于参考点的相对位置关系，并通过坐标转换算法将计算得到的相对位置关系转换为在参考点所在坐标系内的绝对位置关系算法的输入、输出以及具体执行过程如算法1所示在步骤1中，计算参考点、待测点的RSSI向量距离矩阵时，对于不同的位置只需计算待测点与参考点之间的RSSI向量距离，不需计算参考点之间的RSSI向量距离，因为参考点之间的RSSI向量距离是不变的，计算一次即可步骤2中的MDS算法和步骤3中坐标转换算法的具体执行过程都可参看相关文献33为了验证当室内环境中每个位置能够收到足够数目(比如，4个以上)的AP信号时，两点之间RSSI向量距离和其物理距离有较高的一致性和相关性，

40、进而可以利用MDS技术通过点对之间RSSI向量距离得出的相对位置关系，求出待测点的位置我们做了如下仿真实验，将不同数目的AP部署在一个20m20m的区域中，在部署区域中随机产生500个点作为待测点，参考点的间距分别为20m、5m和1m，观察待测点的平均定位误差随AP数目和参考点个数变化的情况，结果如图6所示从图6中可以看出，基于MDS定位方法的定万方数据8期 肖亚龙等：一种基于多维标度和区域细化的无线室内定位方法 1925图6 MDS定位误差随AP数目及参考点个数变化情况位误差随着参考点间距的变小而降低，这是因为参考点间距越小，说明参考点个数越多，用较多的参考点计算待测点位置时，定位误差降低另

41、外，可以看出随着AP数目的增多，定位误差也在降低，并且当AP数目多于4个时，定位误差没有太大的变化根据第3节的结论，这是因为随着AP数目的增多，两点之间RSSI向量距离和其物理距离的一致性和相关性都变大，一致性、相关性越高，利用MDS计算出的待测点位置就越准确，但是当AP数目多于4个时，一致性和相关性系数增大的有限，定位误差也就没有太大的变化利用此方法定位时，我们发现了两个现象：一是定位误差的大小与使用的参考点集合有关；二是待测点定位误差与其相对于区域的位置有关基于这两个现象，我们提出了分层次缩小区域的定位策略，达到提高定位精度的目的我们在下一节对此做具体阐述算法2 基于MDS的分层次缩小区域

42、算法输入：待测点的RSSI向量，参考点的坐标及RSSI向量输出：待测点的坐标1将整个区域按照参考点坐标划分成若干个互不重叠的小区域步骤12将所有参考点的坐标和RSSI向量以及待测点的RSSI向量作为MDS算法的输入，估算出待测点位置，并判断此位置所属的小区域步骤23计算估算出的位置到其所属的小区域边界的距离|步骤34根据步骤3中的距离，对待测点最终的位置进行优化。步骤442基于MDS的分层次缩小区域定位法基于MDS的算法存在着如下两个性质一是定位误差的大小与使用的参考点集合有关：当使用的参考点更接近于待测点时，定位误差较小，也就是说使用待测点所处的较小区域内的参考点比使用较大区域内的参考点得到

43、的定位精度要更高二是待测点定位误差与其相对于区域的位置有关：当待测点靠近区域中心时，定位误差较小；反之，当待测点靠近区域边界时，定位误差较大本节首先对这两个现象给予了实验验证，之后提出了一种分层次缩小区域的定位方法我们利用下面的仿真实验做了相关验证实验环境设置是在一个20m20m的矩形区域中，4个角部署4个AP，25个参考点均匀分布在区域中，相邻参考点之问的间隔为5m25个参考点将区域分成4个10mXlom的区域和16个5m5 m的区域我们在整个区域内随机产生500个点作为待测点，每个待测点分别采用所在的5 m5 m、10 m10 m和20m20m区域中的参考点利用上述定位方法估算其位置3种情

44、况下，待测点的定位误差累积分布函数曲线如图7(a)所示从图中可以看出，在基于MDS的定位方法中，采用小区域中的参考点来计算定位误差m 定位误差m(a)待测点所属区域的大小对定位误差的影响 (b)待测点相对区域位置对定位误差的影响图7对定位误差的影响万方数据计 算 机 学 报待测点位置可以达到更高的定位精度针对第2个现象，我们统计了区域中心10 m10 131范围(称为中间区域)和此范围外(称为外围区域)的待测点定位误差，其累积分布函数曲线如图7(b)所示结果表明位于中间区域的待测点具有更高的定位精度基于这两个性质，我们提出一种分层次缩小区域的定位方法，称此定位方法为MDS(s)算法框架如算法2

45、所示算法3 划分小区域输入：参考点的坐标(墨，YJ)，横纵坐标个数为X，y输出：二级小区域集合、三级小区域集合1FOR i一1 to X-1 by 2，do2 FORj=1 toy-1 by 2，do3 IF i+2Xl lj+2Y，do6 依次获得6个参考点围成的二级小区域7 END8 记录各二级小区域包含的三级小区域集合9 END10END该算法分为4个步骤，每个步骤的具体执行过程如下步骤1：区域划分将整个区域按照参考点坐标划分成若干个互不重叠的二级小区域及三级小区域，并记录下每个三级小区域属于哪个二级小区域这里每个区域是指一个矩形区域，如矩形的4个顶点为(z。，Y。i。)，(z。，y。；

46、)，(z。，Y。i。)，(z。，Y。)，则此区域可以表示为如下形式：(z一，z。，)；(y晌，y。)每个三级小区域是指由4个参考点围成的区域，而每个二级小区域是指由4个或2个相邻的三级小区域组成的区域记所有三级小区域的集合为R3一r，r)，所有二级小区域的集合为R2一r；，r)，其中S，T分别为二级小区域和三级小区域的个数，r；，疗分别为第i，J(1iS，1歹T)个二级小区域和三级小区域区域划分的具体过程在算法3中给出步骤2：将所有参考点的坐标和RSSI向量以及待测点的RSSI向量作为MDS算法的输入，利用41节所述算法算出待测点位置，并判断此位置所属的小区域令估算出的待测点位置为(z。，Y。

47、)则该位置所属的三级小区域为满足如下条件的小区域：z吲。=ITIaXXi z!z。)，z。；一rainzi ziz，)，Y幽一maxY，lYJy。)，Ym*。一minY，lY，执)步骤3：计算估算出的位置(z。，孔)到其所属的三级小区域特定边的直线距离特定边是指三级小区域所属的二级小区域内部和三级小区域的边重合的边具体过程如算法4所示步骤4：根据步骤3中的距离，对待测点最终的位置进行优化比较d与阈值T。的大小，对待测点的最终位置进行优化，具体过程如算法5所示算法4 计算到特定边距离输入：估算出的位置(z。，Y。)及圮，砖输出：(z。，Y。)到r：特定边的距离d1IF疙有6个参考点，do2 可以

48、得到直线距离为d一X。一z。I或dIY。一y。f3END4IF戈有9个参考点，do5 可以得到直线距离有两个值，分别为d。一I z。一z。，dz一Y，一y。l6END则其所属的三级小区域可以记为如下形式圮一(z。z。)；(Y。i。，Y。)通过步骤1和R2可获得其所属的二级小区域吒算法5 优化待测点最终位置输入：参考点的坐标及RSSI向量，步骤3中得到的d，阈值t，龙，坨输出：待测点最终估计位置(z，Y，)1IF矗t(d1tfd：t)，do2 将圮中4个参考点坐标及RSSI向量、待测点的RSSI向量作为MDS的输人，再次估算待测点位置(z，M)3ELSE4 将r：中6个或9个参考点的坐标及RSSI向量、待测点的RSSI向量作为MDS的输入，再次估算待测点位置(z，Y，)5END由于利用小区域对待测点的位置进行了二次计算，上述算法可以得出更精确的待测点位置估计根据前述性质1可知，当第1次得到