基于一种优化的KNN算法在室内定位中的应用研究

第２１卷　第７期　Ｖｏ１．２１　Ｎｏ．７　电子设计工程　Ｅｌｅｃｔｒｏｎｉｃ　Ｄｅｓｉｇｎ　Ｅｎｇｉｎｅｅｒｉｎｇ　２０１３年４月　Ａｐｒ．２０１３　基于一种优化的ＫＮＮ算法在室内定位中的应用研究　张晓亮，赵平，徐冠青，林日明　（西北工业大学电子信息学院，陕西西安７１００７２）　摘要：根据位置指纹室内定位算法的理念，提出了一种旨在减小计算量的定位方法，并将此方法应用于ＫＮＮ算法　中。以ＫＮＮ算法为例，理论上分析了其计算量优化的情况，并在此优化算法的基础上，通过仿真比较了Ｋ的取值、ＡＰ　节点的位置及数量对定位精度的影响。结果表明该算法不但能够保证位置指纹室内定位的精度，而且还能有效的减　小定位过程中的计算量。该方法同样可以推广到其他位置指纹定位算法中，能在理论上解决位置指纹定位算法的计　算量问题。　关键词：室内定位；位置指纹；计算量；ＫＮＮ　中图分类号：ＴＮ９２　文献标识码：Ａ　文章编号：１６７４—６２３６（２０１３）０７—００４４—０３　Ｒｅｓｅａｒｃｈ　ｏｆ　ｉｎｄｏｏｒ　ｐｏｓｉｔｉｏｎｉｎｇ　ｂａｓｅｄ　ｏｎ　ａ　ｏｐｔｉｍｉｚａｔｉｏｎ　ＫＮＮ　ａｌｇｏｒｉｔｈｍ　ＺＨＡＮＧ　Ｘｉａｏ—ｌｉａｎｇ，ＺＨＡＯ　Ｐｉｎｇ，ＸＵ　Ｇｕａｎ—ｑｉｎｇ，ＬＩＮ　Ｒｉ—ｍｉｎｇ　（Ｓｃｈｏｏｌ　ｏｆＥｌｅｃｔｒｏｎｉｃｓ　ａｎｄ　Ｉｎｆｏｒｍａｔｉｏｎ，Ｎｏｒｔｈｗｅｓｔｅｒｎ　Ｐｏｌｙｔｅｃｈｎｉｃａｌ　Ｕｎｉｖｅｒｓｉｔｙ，Ｘｉ’帆７１００７２，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ａｃｃｏｒｄｉｎｇ　ｔｏ　ｔｈｅ　ｃｏｎｃｅｐｔ　ｏｆ　ｌｏｃａｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｆｉｎｇｅｒｐｒｉｎｔ－ｂａｓｅｄ　ｉｎｄｏｏｒ　ｐｏｓｉｔｉｏｎ．Ａ　ｎｏｖｅｌ　ｃｏｍｐｕｔｉｎｇ　ｍｅ￣ｏｄ　ｉｓ　ａｐｐｌｉｅｄ　ｔｏ　ｋ－ｎｅａｒｅｓｔ　ｎｅｉｇｈｂｏｒｓ（ＫＮＮ）ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｒｅｄｕｃｉｎｇ　ｔｈｅ　ｃｏｍｐｕｔａｔｉｏｎａｌ　ｃｏｍｐｌｅｘｉｔｙ．Ｔａｋｅ　ｔｈｅ　ＫＮＮ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｅｘａｍｐｌｅ，ａｎａｌｙｚｅｄ　ｔｈｅ　ｃｏｍｐｕｔａｔｉｏｎａｌ　ｃｏｍｐｌｅｘｉｔｙ　ｔｈｅｏｒｅｔｉｃａｌｌｙ，ａｎｄ　ｃｏｍｐａｒｅｄ　ｔｈｅ　ｄｉｆｆｅｒｅｎｔ　ｖａｌｕｅ　ｏｆ　Ｋ，ｔｈｅ　ｐｏｓｉｔｉｏｎ　ａｎｄ　ｎｕｍｂｅｒ　ｏｆ　ＡＰ　ｏｎ　ｔｈｅ　ｉｎｆｌｕｅｎｃｅ　ｔｏ　ｔｈｅ　ｐｒｅｃｉｓｉｏｎ　ｏｆ　ｐｏｓｉｔｉｏｎｉｎｇ　ｂｙ　ｓｉｍｕｌａｔｉｎｇ　ｏｎ　ｔｈｅ　ｂａｓｉｃ　ｏｆ　ｔｈｉｓ　ａｌｇｏｒｉｔｈｍ．Ｓｉｍｕｌａｔｉｏｎ　ｒｅｓｕｌｔｓ　ｉｎｄｉｃａｔｅ　ｔｈａｔ　ｔｈｅ　ｂｅｔｔｅｒ　ｌｏｃａｔｉｏｎ　ｐｅｒｆｏｒｍａｎｃｅ　ｃａｎ　ｂｅ　ａｃｈｉｅｖｅｄ　ａｎｄ　ｔｈｅ　ｃｏｍｐｕｔａｔｉｏｎａｌ　ｃｏｍｐｌｅｘｉｔｙ　ｉｓ　ｒｅｄｕｃｅｄ　ｂｙ　ｐｒｏｐｏｓｅｄ　ＫＮＮ　ａｌｇｏｒｉｔｈｍ，ａｎｄ　ｔｈｉｓ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ａｌｓｏ　ｓｕｉｔａｂｌｅ　ｏｒ　ｆｏｔｈｅｒ　ｌｏｃａｔｉｏｎ　ｓｙｓｔｅｍｓ　ｔｏ　ｒｅｄｕｃｅ　ｔｈｅ　ｃｏｍｐｕｔａｔｉｏｎａｌ　ｃｏｍｐｌｅｘｉｔｙ．　Ｋｅｙ　ｗｏｒｄｓ：ｉｎｄｏｏｒ　ｌｏｃａｔｉｏｎ；ｌｏｃａｔｉｏｎ　ｆｉｎｇｅｒｐｒｉｎｔ；ｃｏｍｐｕｔａｔｉｏｎａｌ；ＫＮＮ　当前室内定位技术主要有光跟踪定位ｌｌｌ、Ａ—ＧＰＳ［２Ｊ定位、　（ＲＳＳ）采样值和位置指纹数据库中采样值之间的距离。假设参　考点（ＲＰ）和接入点（ＡＰ）的数量分别为ｍ和　，距离定义如下：　ｌ　ｒ　＼无线电波与超声波组合定位以及基于接收信号强度的定位［３１　等。近年来，随着无线局域网的发展，与之相关的定位技术和　应用不断出现．其中．基于接收信号强度的位置指纹室内定　位得到了广泛的关注。　｛￡　：＝（∑Ｉ　ｓ，—．ｓ　Ｉ　｝ｉ＝１，２，…，ｍ　、ｊ＝ｌ　（１）　这里ｓ　是位置指纹数据库中第　个ＡＰ在第ｉ个ＲＰ上　的ＲＳＳ采样值，ｓ　是在线定位阶段第　个ＡＰ的实时ＲＳＳ采　样值　。　基于接收信号强度的位置指纹定位算法主要有ＮＮ算　法、ＫＮＮ算法等。定位过程首先是离线阶段的采样和建立数　据库，然后进行在线阶段的位置匹配，需要存储的数据量和　根据ＫＮＮ算法原理，计算得到具有最小距离的Ｋ个　ＲＰ，其位置坐标分别为（　Ｙ　），（ｉ＝１，２，…，ｋ），那么，测试点　（ＴＰ）的位置坐标估计值为这　个ＲＰ的质心。如式（２）所示。　ｋ　运算量极大。使得两种算法的应用受到了一定程度的限制。　文中基于指纹室内定位算法的理念，设计了一种旨在减　小位置指纹匹配计算过程中冗余计算的精简算法，并应用于　ＫＮＮ算法中。从理论上分析了该算法相较以往算法节约的计　算量，在ＫＮＮ算法的基础上，通过仿真比较了Ｋ的取值、ＡＰ　节点的位置及数量对定位精度的影响。　（　，　）＝＿＿１∑（ｘｌ，ｙｉ）　ｉ＝１　（２）　在ＮＮ算法中，取距离最近的ＲＰ作为ＴＰ　的位置估计　值，即将式（２）中Ｋ取为１，即可得到ＮＮ算法的计算结果。　１优化的ＫＮＮ算法　１）ＫＮＮ算法　２）位置指纹匹配计算精简算法　在位置指纹室内定位过程中，由于电磁波的传播损耗，　ＲＳＳ随着距离的增加呈现指数衰减。当传输距离较近时，衰减　较快．而传输距离越远，衰减越慢，当传输距离接近８　ｍ［６１左右　时，信号功率对传输距离的变化表现不明显。根据上述特性，　在ＫＮＮ算法中，首先计算在线阶段的接受信号强度　收稿臼期：２０１２—１１—１５　稿件编号：２０１２１１１２６　基金项目：国家自然科学基金资助项目（６１２７１２７９，６１２０１１５７）　作者简介：张晓亮（１９８７一），男，河南漯河人，硕士研究生。研究方向：通信与信息系统。　－４４－　张晓亮。等　基于一种优化的ＫＮＮ算法在室内定位中的应用研究　在某定位区域内，ＴＰ接收的距离８　ｍ以外的ＡＰ的ＲＳＳ趋于　稳定，在一定值附近波动，因此这部分数据对匹配定位并无贡　献，这表明，在位置指纹匹配计算过程中，存在大量的冗余计　算。该算法拟在匹配计算过程中忽略距ＴＰ８　ｍ以外ＡＰ的　ＲＳＳ，减小位置指纹匹配过程中的计算量。具体算法如下：　假设在某定位区域内有ｎ个ＡＰ，设定当１１Ｐ距离ＡＰ　８　Ｉｎ　时的ＲＳＳ为临界值ａ，某ＴＰ实时接收到的来自不同ＡＰ的　ＲＳＳ为　＝（　。，　２，…，　），将向量　中的元素逐一与临界值Ⅱ　参考点处信号Ｊ强度　ｌ待测点处信号Ｉ　测量Ｉ　ｌ强度测量Ｉ　建立位置指纹ｌ　Ｊ　数据库　Ｊ　离线阶段　行匹配定位　一Ｉ＝ｌ二＝＝：＝ｌ　觋』　图１优化的ＫＮＮ算法流程　Ｆｉｇ．１　Ｐｒｏｃｅｓｓ　ｏｆ　ｏｐｔｉｍｉｚａｔｉｏｎ　ＫＮＮ　ａｌｇｏｒｉｔｈｍ　输损耗模型根据各测量点距相应的ＡＰ的距离确定。本文选　进行减法运算，如式（３）所示。　１一ｎ　７２２－ａ　：　（３）　对上式计算结果进行判断，当ｘｌ－ａ＞Ｏ时保留　当ｘｌ－ａ＜￣　０时弃掉麓，由保留下来的施组成新的向量　＝（　，…，　），ｍ≤ｎ）。　在匹配计算过程中，假设某ＲＰ处位置指纹数据库数据　为ｙ＝（ｙ。，Ｙ２，…，　），根据该算法的规则，取出与　对应项组成　新的向量，，　＝（　。，Ｙａ，…，　），然后计算向量　与Ｙ　之间的距　离，如式（４）所示。　ｄ＝、／（　ｎ－ｙ　１）　＋（　也—，　）２＋…＋（　－ｙ　）　（４）　以此取代传统计算的向量　与Ｙ之间的距离。其他ＲＰ　处也进行相同的计算，最后根据所采用的位置指纹定位算法　进行定位计算。　在每个参考点处进行匹配计算过程中．该算法相较传统　算法节约计算量为：加法：３（ｎ－ｍ）次，乘法：（ｎ—ｍ）次，由于在　每个ＲＰ处要对数据库进行筛选，实际节约计算量为：加法：　（２ｎ＇３ｍ）次，乘法：（ｎ—ｍ）次。在整个定位过程中，由于ＡＰ布　置的不规则性和ＴＰ位置选取的随意性．每次距离ＴＰ在８ｍ　以外的ＡＰ个数会有所不同，假设上述节约的计算量为平均　值，对在共有Ｐ个ＲＰ的定位区域，每次定位过程中共节约计　算量为：加法：Ｐ（２ｎ一３ｍ）次，乘法：Ｐ（ｎ—ｍ）次。　３）优化的ＫＮＮ算法　文中提出的优化ＫＮＮ算法。将位置指纹匹配计算精简算　法应用于ＫＮＮ算法中，将在线阶段实时定位任务分配给服务　器进行处理。最后对算法定位信息进行处理，得到最终的定位　结果。　完整的优化ＫＮＮ算法定位过程如图１所示。　首先，离线阶段，在各个ＲＰ处测量自各ＡＰ的ＲＳＳ，并根　据所测得的ＲＳＳ建立位置指纹数据库。　第二步，在线阶段，首先测量ＴＰ处自各ＡＰ的ＲＳＳ，然后　根据该ＲＳＳ和位置指纹数据库，利用本文提出的上述优化的　ＫＮＮ算法进行位置指纹匹配定位。　第三步，对数据进行处理，得到最终ＴＰ位置估计值。　２仿真实验　仿真实验中，位置指纹数据库及ＴＰ处的ＲＳＳ由室内传　用的室内传输损耗模型为ＭＫ模型［７１，它属于统计模型，该模　型综合考虑了墙壁等对信号的衰减，能比较精确地反应无线　信号在室内环境下的传输损耗，如式（５）所示。　Ｌ　＝￡０＋１０・ｎ・ｌｏｇ（ｘ）＋Ｎｗ・Ｌ　（５）　在该公式中，　表示信号接收强度，　表示距离发射端　１　ｍ处的传播损耗，ｎ是路径损耗系数。　表示发射端到接收　端的距离，　表示射线从发射机到接收机穿过的墙的个数，　代表墙壁损耗系数。根据文中的仿真实验环境，选取　３７　ｄＢ，ｎ＝２，Ｌｗ＝３　ｄＢ，得出本文仿真实验所用的路径损耗计算公　式为：　三一＝３７＋２０・ｌｏｇ（ｘ）＋３・　（６）　接下来的仿真均选取公式（６）作为信号传输损耗模型，并　加入１Ｏ　ｄＢ信噪比的高斯白噪声。　在公式（２）中，ＫＮＮ算法中Ｋ的取值对定位精度有较大　影响，因此首先对算法中　的取值不同对定位精度的影响进　行了仿真研究。在定位区域随机选取１００个点作为待测点。在　式（１）中，本文按照室内位置指纹定位一般准则选取ｑ取值为　２，即选取欧几里得距离作为匹配定位时的距离模式。本文研　究了Ｋ的取值在１～１Ｏ之间变化时，相应的优化ＫＮＮ算法的　定位精度的变化．仿真结果如图２所示。　图２　Ｋ取不同值时对定位精度的影响　Ｆｉｇ．２　Ｉｎｆｌｕｅｎｃｅ　ｏｆ　ｌｏｃａｔｉｏｎ　ｐｒｏｂａｂｉｌｉｔｙ　ｗｉｔｈ　ｄｉｆｆｅｒｅｎｔ　ｋ　接下来仿真分析了ＡＰ节点的位置及数量对定位精度的　影响，为了方便，在定位区域内．ＡＰ节点个数分别取２个３个　和４个，ＡＰ节点的位置分别取为定位区域的４个顶点、对角　线上平均分布的４个点和区域内部随机的一个４方形的４个　顶点对其进行了研究，结果如图３、图４所示。　－４５－　《电子设计工程￣２０１３年第７期　减小计算量的位置指纹定位算法，并将此算法应用于ＫＮＮ算　法中。基于该算法，文中综合分析了　的取值、ＡＰ节点的位　置及数量的不同对定位精度的影响，结果证明文中所提出的　算法在保证了定位精度的前提下．还能够有效的减小系统定　位过程中的计算量。在以后的工作中，将会进行该算法在其　它环境下的性能分析，以及设计一个根据环境自适应的云计　算加权分配算法　。　参考文献：　【１］Ｓｍｉｔｈ　Ａ，Ｂａｌａｋｒｉｓｈｎａｎ　Ｈ，Ｇｏｒａｃｚｋｏ　Ｍ，ｅｔ　ａ１．Ｔｒａｃｋｉｎｇ　ｍｏｖｉｎｇ　ｄｅｖｉｃｅｓ　ｗｉｔｈ　ｔｈｅ　ｃｒｉｃｋｅｔ　ｌｏｃａｔｉｏｎ　ｓｙｓｔｅｍ［ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２ｎｄ　ＡＣＭ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｍｏｂｉｌｅ　Ｓｙｓｔｅｍｓ，　ＬｏｃａｔｉＯＦｔ￣ｒｆｏｒ／ｍ　Ａｐｐｌｉｃａｔｉｏｎｓ，ａｎｄ　Ｓｅｒｖｉｃｅｓ．ＵＳＡ：［ｓ．ｎ．】，２００４：１　９０—２０２．　网３　ＡＰ位置的不同对定位精度的影响　［２】ＳＵＮ　Ｇｕｏ－ｌｉｎ，ＣＨＥＮ　Ｊｉｅ，ＧＵＯ　Ｗｅｉ，ｅｔ　ａ１．Ｓｉｇｎａｌ　ｐｒｏｃｅｓｓｉｎｇ　ｔｅｃｈｎｉｑｕｅｓ　ｉｎ　ｎｅｔｗｏｒｋ－－ａｉｄｅｄ　ｐｏｓｉｔｉｏｎｉｎｇ：ａ　ｓｕｒｖｅｙ　ｏｆ　ｓｔａｔｅ．－ｏｆ－　ｔｈｅ－ａｒｔ　ｐｏｓｉｔｉｏｎｉｎｇ　ｄｅｓｉｇｎｓ［Ｊ］．ＩＥＥＥ　Ｓｉｇｎａｌ　Ｐｒｏｃｅｓｓｉｎｇ　Ｍａｇａｚｉｎｅ，　２００５，２２（４）：１２—２３．　［３】Ｍａｒｋｏ　Ｈ，Ｊｕｈａ　Ｌ，Ｈａｎｎｕ　Ｉ，ｅｔ　ａ１．Ｕｓｉｎｇ　ｃａｌｉｂｒａｔｉｏｎ　ｉｎ　ＲＳＳＩ—　ｂａｓｅｄ　ｌｏｃａｔｉｏｎ　ｔｒａｃｋｉｎｇ　Ｓｙｓｔｅｍ【Ｃ］，／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　５ｔｈ　Ｗｏｒｌｄ　Ｍｕｌｔｉｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｃｉｒｃｕｉｔｓ，Ｓｙｓｔｅｍｓ，Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ　ａｎｄ　Ｃｏｍｐｕｔｅｍ．【Ｓ．Ｉ．］：ＩＥＥＥ　Ｐｒｅｓｓ，２００１：４６１—４６５．　【４】Ｈａｔａｍｉ　Ａ，Ｐａｈｌａｖａｎ　Ｋ．Ｃｏｍｐａｒａｔｉｖｅ　ｓｔａｔｉｓｔｉｃａｌ　ａｎａｌｙｓｉｓ　ｏｆ　ｉｎｄｏｏｒ　ｐｏｓｉｔｉｏｎｉｎｇ　ｕｓｉｎｇ　ｅｍｐｉｒｉｃａｌ　ｄａｔａ　ａｎｄ　ｉｎｄｏｏｒ　ｒａｄｉｏ　ｃｈａｎｎｅｌ　ｍｏｄｅｌｓ【Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ＩＥＥＥ　ＣＣＮＣ　２００６．Ｌａｓ　Ｖｅｇａｓ：Ｉｓ．ｎ．］，２００６：１０１８—１０２２．　Ｌｏｃａｔ　ｌＯｉｌ　ｅｒｒｏｒ／ｆｌｌ　【５］ＳＵＮ　Ｙｏｎｇ－ｌｉａｎｇ，ＸＵ　Ｙｕ—ｂｉｎ，ＭＡ　Ｌｉｎ，ｅｔ　ａ１．ＫＮＮ—ＦＣＭ　ｈｙｂｒｉｄ　ｌａｇｏｒｉｔｈｍ　ｆｏｒ　ｉｎｄｏｏｒ　ｌｏｃａｔｉｏｎ　ｉｎ　ＷＬＡＮ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２ｎｄ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｐｏｗｅｒ　Ｅｌｅｃｔｒｏｎｉｃｓ　ａｎｄ　图４　ＡＰ个数的不同对定位精度的影响　Ｆｉｇ．４　Ｉｎｆｌｕｅｎｃｅ　ｏｆ　ｌｏｃａｔｉｏｎ　ｐｒｏｂａｂｉｌｉｔｙ　ｗｉｔｈ　ｄｉｆｆｅｒｅｎｔ　ｎｕｍｂｅｒ　ｏｆ　ＡＰ　以上仿真结果表明，优化的ＫＮＮ算法的定位精度随着Ｋ　的取值不同呈现不规则的变化，由于位置指纹法最关注的定　位精度在３￣４　ｍ之间，可得出当Ｋ＝２时定位精度达到最高。　ＡＰ节点的位置及个数都对定位精度有着明显的影响．当节点　位置分布均匀且相对扩散时，定位精度能够得到较大的提高。　ＡＰ节点的个数增加时，也能够显著的提高定位精度．但随着　Ｉｎｔｅｌｌｉｇｅｎｔ　Ｔｒａｎｓｐｏｒｔａｔｉｏｎ　Ｓｙｓｔｅｍ．Ｓｈｅｎｚｈｅｎ：［ｓ．ｎ．］，２００９：２５　１－　２５４．　【６】孙佩刚，赵海，罗玎玎，等．智能空间中ＲＳＳＩ定位问题研究叨．　电子学报，２００７，３５（７）：１２４０—１２４５．　ＳＵＮ　Ｐｅｉ—ｇａｎｇ，ＺＨＡＯ　Ｈａｉ，ＬＵＯ　Ｄｉｎｇ—ｄｉｎｇ，ｅｔ　ａ１．Ｒｅｓｅａｒｃｈ　ｏｎ　ＲＳＳＩ－ｂａｓｅｄ　ｌｏｃａｔｉｏｎ　ｉｎ　ｓｍａｒｔ　ｓｐａｃｅ【Ｊ１．Ａｃｔａ　Ｅｌｅｃｔｒｏｎｉｃａ　Ｓｉｎｉｃａ，２００７，３５（７）：１２４０—１２４５．　ＡＰ节点个数的增加，系统所承担的计算量将成指数形式增　加，所以在实际应用中应综合考虑以上各种因素选择合适的　ＡＰ数量及节点位置。　［７】姜莉．基－ｔ－ＷｉＦｉ室内定位关键技术的研究［Ｄ］．大连：大连　理工大学。２０１０：１５—１６．　３结束语　文中基于位置指纹室内定位算法的理念．提出一种旨在　［８］ＺＨＡＮＧ　Ｙｕ—ｄｏｎｇ，ｗｕ　ＩＪｅ—ｎａｎ．Ａｒｔｉｉｆｃｉａｌ　ｂｅｅ　ｃｏｌｏｎｙ　ｆｏｒ　ｔｗｏ　ｄｉｍｅｎｓｉｏｎａｌ　ｐｒｏｔｅｉｎ　ｆｏｌｄｉｎｇ［ＪＪ．Ａｄｖａｎｃｅｓ　ｉｎ　Ｅｌｅｃｔｉｒｃａｌ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｓｙｓｔｅｍｓ，２０１２，ｌ（１）：１９－２３．　－４６－