面向大型建筑物的室内导航系统开发

李 盟，杨 静，邵薪儒

(天津城建大学 控制与机械工程学院，天津300384)

信息科学与技术

面向大型建筑物的室内导航系统开发

李 盟，杨 静，邵薪儒

(天津城建大学 控制与机械工程学院，天津300384)

为提高大型建筑物内资源利用效率，针对建筑物内环境复杂、无法利用卫星导航信号等因素导致的导航精度差的问题，利用建筑物内已覆盖的无线网络信号，开发一套基于无线网络定位技术的室内导航系统．为满足大型公共建筑物内导航精度的要求，提出一种加入信号传播模型修正的加权K近邻算法，以提高传统位置指纹定位方法的定位精度；为提高路径规划与导航的效率，采用一种改进的实时A*算法，将时间较优指标引入到评价指标中，节省软件开销．基于ARM-Linux嵌入式系统开发了导航服务器，并在智能移动设备上进行客户端的开发，使用户可利用智能设备查询自己在建筑物内的位置、目的地信息，并自动规划路线．该系统可广泛应用于商场、博物馆、图书馆、交通枢纽等大型公共建筑物内．

大型建筑物；室内导航；无线网络；综合信息系统

随着建筑技术的发展和人们生活水平的提高，公共建筑物的规模不断扩大、功能日趋复杂，因此在公交枢纽、商场、图书馆等大型公共建筑物内进行导航逐渐成为必要．然而，由于室内环境限制，无法利用GPS等信号进行定位．随着无线局域网(wireless local area networks，简称WLAN)在室内环境的广泛部署，IEEE802.11系列协议的成熟完善，以及手机等移动智能设备的普及应用，基于WLAN室内定位技术迅速发展起来．近年来，国内外很多高校和科研院所都开展了室内定位技术研究：如英国剑桥ORL实验室的Active Badge系统[1]，美国Microsoft公司的RADAR定位系统、麻省理工大学的Cricket系统[2]、加利福尼亚大学的Calamari系统[3]等．基于WLAN的室内定位技术，充分利用现有的WLAN设备而无须增加额外的硬件设备，具有部署成本低、易于实现等优势，成为目前室内定位技术研究的主流方向[4]．

针对大型建筑物内导航的特点，利用无线网络定位技术，在智能设备上实现室内定位、导航、信息查询等功能，可广泛运用于商场、博物馆、图书馆、交通枢纽等大型公共建筑物内．

1 系统结构

系统硬件组成包括导航信息服务器、无线网络热点、智能移动设备等部分．其中无线网络热点利用建筑物中已有的无线路由器，无须增加硬件设备；智能移动设备可选用智能手机、平板电脑、智能穿戴设备等．系统结构如图1所示．

智能设备同时接收到几个热点发出的信号，利用基于Wifi的信号强度的定位算法，可以对当前位置进行估计，并根据地图信息进行路径规划．采用基于ARM9的Linux嵌入式系统开发导航信息服务器，包含地图信息数据库，实现信息采集、分析、管理和发布的功能．服务器可获取智能设备的位置信息，接收其发来的请求指令，并对智能设备的信息进行分析、存储，同时发送广播信息．

图1 系统结构

2 导航信息服务器开发

2.1 导航信息服务器硬件结构

导航信息服务器采用基于ARM9的嵌入式系统，其硬件基本组成如图2所示．服务器的核心为一片AT91RM9200处理器．采用一片同步动态存储器SDRAM作为内存、一片FLASH存储器用于存储系统文件，通过USB接口连接外部存储设备，Jtag接口用于系统的维护和调试．外部设备包括一个LCD屏，用于显示系统状态；一个Wifi模块，用于通讯．另外还有电源管理电路保障电源供应，复位电路用于特殊情况下的复位．

导航信息服务器硬件原理图和实物分别如图3-4所示．4个USB接口分别用于连接无线网卡和其他外设；以太网口用于连接有线局域网络；HDMI接口用于连接显示设备，可以进行系统调试．

图2 导航信息服务器硬件结构

图3 导航服务器硬件原理图

图4 导航服务器硬件

2.2 导航信息服务器软件结构

导航信息服务器软件采用嵌入式Linux操作系统．它充分满足硬件设备的实时性要求，具有高可靠性、适应性和成熟的开发工具．另外，小巧的内核可以满足存储空间的容量[5]．

应用程序主要用于处理和储存信息，软件结构如图5所示．管理模块是应用程序的核心，它用于对其他模块进行监视和管理；通讯模块用于收发数据，并将收到的数据发送给数据库管理模块，同时通过数据库管理模块读取数据库数据，并发送给客户端．数据库管理模块用于对数据库信息进行管理和操作．数据库分为两部分：一个是固定数据库，其中储存所在场所的地图和局部的基本信息，其数据维护需要特定的权限，一般用户只能请求其数据，但不能对数据内容进行修改；另一个是动态数据库，随时记录用户使用偏好等信息，用于后续的分析工作．服务器端界面如图6所示．

图5 导航信息服务器软件结构

图6 服务器端界面

3 智能设备应用软件开发

3.1 基于无线局域网的导航算法

基于WLAN的导航是本系统的核心功能．考虑到大型建筑物内GPS信号不稳定，且基于GPS的定位方法在垂直方向上精度较低，难以在建筑物内部准确定位，因此需要在建筑物内部布设信号点，代替导航卫星进行定位．目前，无线局域网在公共建筑物内的部署日益广泛，采用基于WLAN的导航技术无须增加硬件，相对于基于蓝牙等其他设备的定位方法更加经济，且容易实现．同时，由于智能手机的飞速发展，智能移动设备本身的信息接口满足在其上开发导航软件的需要，因此本系统采用基于WLAN的导航方法．

基于无线局域网的导航方法，主要需要解决的问题包括：复杂环境下基于WLAN信号强度的定位精度问题和基于建筑物内布局与人流密度的时间最优路径规划算法问题．

3.1.1 定位算法

在大型公共建筑物内，由于建筑物结构复杂、电气设备多等特点，对WLAN信号造成一定的干扰．目前，基于WLAN的室内定位技术主要方法有：到达时间(time of arrival，简称TOA)法、到达角度(angle of arrival，简称AOA)法、到达时间差(time difference of arrival，简称TDOA)法、信号传播模型法、最近接入点(access point，简称AP)法以及位置指纹法等[6]．各种方法的特性如表1所示．采用传统的基于信号传播模型的算法鲁棒性较差，无法满足定位精度的需要；位置指纹法具有成本低廉、不需要添加外部硬件、定位精度较高等特点，适合在公共建筑物内使用．虽然文献[7]中的实验表明，位置指纹法依赖于建筑物的结构，但由于公共建筑物结构相对稳定，且在前期调试时易于修正，因此可采取基于WLAN信号强度的位置指纹法作为定位算法．

表1 基于WLAN的室内定位技术主要方法比较

位置指纹定位算法的基本原理：通过测量不同位置的无线网络信号强度向量，建立信号强度位置指纹数据库，并通过将设备实时采集的无线网络信号强度与数据库中的数据进行匹配，实现定位[8]．

常用的匹配算法有最近邻法(nearest neighborhood，简称NN)、K最近邻匹配算法(K-nearest neighborhood，简称KNN)、加权K近邻法(weight K-nearest neighborhood，简称WKNN)等．NN算法的实质是将待测点的信号强度和指纹数据库中各个指纹点处的信号强度进行匹配，求出待测点相对每个指纹点的偏移量，将其中偏移量最小的指纹点的坐标作为该待测点的坐标；KNN算法与NN算法类似，区别在于KNN算法进行信号强度匹配后，是将偏移量最小的k个指纹点坐标取平均值，得到待测点的实际坐标，其难点是确定k的值；WKNN算法是对KNN算法的改进，它将偏移量最小的k个指纹点的坐标取加权平均值，即

式中：Xi为按信号强度进行排序后的第i个指纹点的坐标Xi＝(xi，yi)；ˆX为当前待测点坐标的估计值；wi为指纹点坐标的权值，该权值由指纹点处的信号强度值定义：

式中：Pfi为第i个指纹点处的信号强度；Pr为待测点处的信号强度；n为指纹点个数．

WKNN算法与NN和KNN算法的对比实验结果如图7所示．显然，WKNN算法的精度明显高于NN和KNN算法．

图7 三种算法误差分布对比实验结果

3.1.2 路径规划

在路径规划问题上，已经有许多成熟的算法．传统上有模拟退火算法、人工势场法、模糊逻辑算法、禁忌搜索算法等．近年来，也出现了一些智能仿生学算法，如蚁群算法、神经网络算法、遗传算法、粒子群算法等[9]．

A*算法是导航路径计算中的标准算法．但考虑到系统所采用的嵌入式硬件，其性能和内存有一定的限制与要求，难以直接使用A*算法计算路径，所以需要对传统的A*算法进行改进．本系统采用一种改进的实时A*算法[10]．考虑建筑物内实际环境情况，将时间较优指标引入到评价指标中，提高导航的效率，同时节省软件开销．算法流程如下：

输入：起始点和目标点坐标

输出：继承点序列

(1)设置一个节点作为起始点；

(2)为节点建立继承点，如果任一继承点为目标点，则退出；

(3)通过从继承点开始进行固定深度搜索，计算每个继承点的值；

(4)将节点移到得分最低的继承点上，将上一节点与次优继承点的启发代价存储到一个表中；

(5)返回步骤(2)．

步骤(3)中，使用A*启发式函数f＝g＋h′评价所有叶节点，其中g为根节点到叶节点的距离，h′为叶节点到目标点的预测距离．每个中间节点的f值都被设定为其子节点的最小值，以此在搜索树上通过启发式估计．由于步骤(4)的做法，在同一点处不会两次采取相同的策略，而避免落入死循环．若该节点再次由步骤(2)生成，只需在步骤(3)中的表中查找，而无须重做固定深度搜索，减少算法的时间成本．

3.2 软件结构

针对智能移动设备开发客户端程序．客户端通过对上述定位和路径规划算法的实现，完成用户导航功能，同时与服务器端进行通讯，调用服务器端的信息，并将用户数据反馈服务器端．软件流程如图8所示．

图8 软件流程

移动客户端软件部分功能界面如图9所示．

图9 移动客户端界面

4 结 论

针对大型公共建筑物内导航及资源高效利用的问题，设计了大型公共建筑物室内导航系统．

(1)进行了服务器端的软、硬件设计，采用ARM-Linux嵌入式架构，通过应用层的开发，实现客户端与服务器之间的通讯，以及对服务器数据库的读写功能．

(2)进行了基于智能移动设备的客户端软件设计．首先研究了基于WLAN的定位方法，解决了大型建筑物内无法使用GPS信号进行导航的问题，通过对不同定位算法的研究，采用了改进的WKNN算法，保证定位的精度；再通过采用改进的实时A*算法进行路径规划，实现对路径的最优选择．

(3)根据算法进行基于智能移动设备的导航软件的设计，完成了基于智能移动设备的室内导航系统的开发．

［1］ WANT R，HOPPER A，FALCAO V，et al. The active badge location system[J]. Acm Transactions on Information Systems，1992，10(1)：91-102.

［2］ SHEN M，YANG X，JUN W U. A method of identifying beacons of cricket system based on phase superposition[J]. Chinese Journal of Sensors & Actuators， 2013，26(7)：981-985.

［3］ WHITEHOUSE C D. The design of calamari：an ad-hoc 788 localization system for sensor networks[D]. Berkeley：University of California at Berkeley，2002.

［4］ ZANDBERGEN P A. Accuracy of iPhone locations：a comparison of assisted GPS，WiFi and cellular positioning[J]. Transactions in Gis，2009，13(Suppl1)：5-25.

［5］ 沈 可. 使用嵌入式Linux操作系统进行软件开发的特点及优势[J]. 电脑开发与应用，2001，14(7)：13-15.

［6］ 刘建业. 基于WLAN的室内定位技术的研究与实现[D]. 昆明：云南财经大学，2013：11-17.

［7］ FARSHAD A，LI J，MARINA M K，et al. A microscopic look at WiFi fingerprinting for indoor mobile phone localization in diverse environments[C]// IPIN. 2013 International Conference on IEEE，Busan：[s.n.]，2013：1-10.

［8］ LUO Y，HOEBER O，CHEN Y. Enhancing Wi-Fi fingerprinting for indoor positioning using human-centric collaborative feedback[J]. Human-centric Computing and Information Sciences，2013，3(1)：1-23.

［9］ 张广林，胡小梅，柴剑飞，等. 路径规划算法及其应用综述[J]. 现代机械，2011(5)：85-90.

［10］ DAS P K，BEHERA H S，PRADHAN S K，et al. A modified real time A* algorithm and its performance analysis for improved path planning of mobile robot[J]. Smart Innovation，Systems and Technologies，2015，32：221-234.

Development of the Indoor Navigation System in Large Public Buildings

LI Meng，YANG Jing，SHAO Xinru
(School of Control and Mechanical Engineering，TCU，Tianjin 300384，China)

A navigation and integrated information system is designed and developed based on the wireless network signals，which can be used to improve the efficient use of resources and solve indoor navigation problem in large public buildings. A fingerprint positioning method based on WLAN signal along with modified weighting K nearest neighbor algorithm and signal propagation model is proposed to meet the requirement of indoor navigation. A modified real-time A* algorithm which introduces the time optimal index into the evaluation index is used to improve navigation efficiency. A navigation server is designed based on ARM-linux embedded system，and a client is developed on smart mobile devices. The users can easily inquire their location and the information of the destination on their smart mobile devices，which can also plan the route automatically. This system will be widely used in large public buildings such as market，museum，library and transport hubs.

large public buildings；indoor navigation；wireless network；integrated information system

TN966

A

2095-719X(2016)06-0460-05

2015-11-23；

2016-03-29

国家级大学生创新创业训练计划(201510792013)

李 盟（1985—），女，天津人，天津城建大学助教，硕士.