大型商场室内定位与导航设计

夏晨航 龚俊

摘 要：本文以商场作为模型的设置室内导航，借助于云子实现位置定位。从实物定位，到路径规划实施室内导航技术。

关键词：空间定位；室内导航；移动设备；云子

定位导航给生活带来了诸多便利，大家对GPS比较了解，其在室外非常好用，但在室内却不精确，甚至无法使用。为了方便人们在室内商场快捷找到目的地，本文提出了一个可行的适用于室内定位与导航的方法。

1 室内导航的实物定位

室内的货架按照一定距离铺设释放信号的云子，并记录好每个云子的坐标及其编号，当客户进入室内后，其携带的蓝牙设备会接收到多颗云子发出的RSSI值并得到对应云子的信号强度，并根据其中最强的三个云子得到客户的位置。分两种情况陈述。

1.1 位置指纹识别算法

如客户所在位置附近阻挡物体较多，云子的RSSI值波动幅度较大会导致定位不精确，为了使定位精确，使用位置指纹识别算法：首先，根据合理的测算设定参考点，测出每个参考点上的信号强度存入位置指纹数据库，格式为RSSI[R1，R2，R3]。然后，用户会在相应位置得到RSSI信号大小，系统会把此用户测得的数据与数据库中的信息进行 s2=（RR1-R1）2+（RR2-R2）2+（RR3-R3）2的遍历计算得到方差值。如果小于一定值（根据参考点密度而定），则认为此地点与位置指纹数据库中的地点匹配，得到相应参考点的位置坐标。

1.2 圆形定位算法

如没有符合的参考点，说明用户此时位置不是事先确定的阻挡物较多的位置，可以使用圆形算法：通过判断 iBeacon 的 RSSI 值，如果某个 iBeacon 信号覆盖范围为30米，在它1米处检测到的信号是-50，3米时是-70…因此，能够得到用户离的最近的三个云子的坐标及用户分别与三个云子的距离。云子a圆心坐标[x1，y1]，覆盖范围d1。云子b圆心坐标[x2，y2]，覆盖范围d2。云子c圆心坐标[x3，y3]，覆盖范围d3。同时覆盖到的那个点就是用户的坐标。

2 室内导航的路径盘查

2.1 获取用户搜索物品的位置和用户的位置

把每个云子的位置，绑定到该云子所在位置正对面的转角坐标连上线。用户搜索物品地点和用户所在地点连入的云子，都对应一个位置。这时，就能知道用户搜索物品和用户所在地离哪个转角坐标最近，然后，用室内最近路线算法，算出这兩个转角坐标的最短路线，最后把首位转角坐标点和搜索物品，用户坐标连接起来，就得到用户到搜索物品最近的路线。

2.2 室内最近路线算法

2.2.1算法思路

设商场路线是个连通图（v，e）（v顶点，e连线），把顶点集合V分成两个组，第一组为已求出最短路径的顶点集合（用a表示，初始时a中只有用户转角坐标一个顶点，以后得到一条最短路径 ， 就将加入到a中，直到b中剩余转角坐标全部加入到a中），第二组为剩余的转角坐标顶点集合（用b表示），每次求出与a中最后一个顶点坐标直连的最短路径，把他加入到b中。在加入的过程中，如果加入路径短于原先就存在的路径，那么就替换它，如果长于原先的路径，就不加入。最后，就能得到起点开始，到除他以外的所有点的最短路径。

2.2.2算法过程

如果用户和搜索物品最近转角坐标同为一个，则跳过室内最近路线算法，直接画物品坐标—转角坐标—用户坐标的连线。

如果用户和搜索物品的最近转角坐标点能直接相连，则也跳过室内最近路线算法， 直接画物品坐标—转角坐标—转角坐标—用户坐标 的连线。

如果不是前两种情况，则用室内最近路线算法算出用户和搜索物品最近的转角坐标点的相连最短路线，然后画出物品坐标—转角坐标—（最短路径）—用户坐标的连线。

2.3 算法示例

设某商场的位置由12个点组成的无向图（a-g：9，a-b：20，b-f：5，g-f：20，g-p：5，p-q：7，q-t：5，t-e：5，f-e：5，p-o：5，q-r：5，t-s：5，o-r：7，r-s：5，s-u：5）

下面就是算法的具体实现：首先，会得到用户坐标，并得到离用户最近的转角坐标点（假设a），然后，会得到牛奶的坐标，并得到离牛奶最近的转角坐标点（假设t）。求a到t最近的路线：（只说明关键的步骤和特殊的情况步骤，其他的步骤同理）

（1）a-g：5，a-b：20。a-g=5 存入a集合中，b返回b集合中。

（2）a-g-p：10，a-g-f：25。a-g-p：10存入a集合中，f返回b集合中。

（3）a-g-p-o：15，a-g-p-q：17。a-g-p-o：15存入a集合中，q存入b集合中。

（4）a-g-p-o-r：2。由于该行为是只有一个路径，直接存入。

（5）比如a-g-p-o-r-q：27和a-g-p-o-r-s：27的路径都是27，但是由于之前a集合中有a-g-p-q：17的路径且小于这条路径，那么当前这俩个路径删除。

（6）如果有俩条路径相等，比如a-g-p-q-t-s：27，a-g-p-q-t-e：27，且在a集合中没有找到相等的结束位置，那么就随机存入。a-g-p-q-t-s：27存入a集合。……

一共有12个顶点，经过11次的重要运算，这时b集合为空，则完成了室内最近路线算法操作。此时，a集合中有11条记录：这些记录就是从a坐标到除他外任意坐标的最短路径，从中找到我们需要的a-t路径即可。最后，把a-g-p-q-t路径连接起来，并把a和用户坐标，t和物品坐标连接，得出的连线，就是用户到物品的最佳路径。

3 总结

本文是基于“sensoro 云子”传感器实现商场室内定位与导航设计，实现过程是首先通过云子的获得用户和商品的位置，然后在通过算法来找到用户相对于该商品的最短路径，最后只要在用户的界面上通过直线描绘直观的表示出这条路径即可，关键点是对商场中地点信息的采集。随着物联网的普及和发展，基于传感器的定位系统也会逐步的占据市场。

参考文献：

[1] 方震，赵湛，郭鹏，等.基于RSSI测距分析[J].传感器技术学报，2011，20（11）：2526-2530.

[2] 王小辉.基于FRID的室内定位技术评论[J].传感器与微系统，2009，28（2）：1-3.