随着城市现代化的脚步越来越快,在城市中,高楼大厦一栋接着一栋的竖立在地面,并且,这些建筑物的结构和设计也越来越复杂。不光如此,随着现代生活的节奏越来越快,城市人口在室内呆的时间也越来越多。这样,人们对室内环境的了解的热情就会变高。室外导航现在早已经发展的成熟,可以基本满足绝大多数的导航请求,但是,室内导航却是一个很新的领域。虽然现在已经有不少公司在发展室内导航技术,但是,毕竟这是个刚发展不久的领域,室内导航技术仍然有很多不足之处。3圆定位和质心定位算法是比较常使用的室内定位算法,但是,由于无线信号在室内传播的过程中会有一定的衰减,所以,这些定位算法都会存在一定的误差。本文首先通过过滤掉那些误差较大的设备信息来减少定位误差,然后在3圆定位的基础上提出改进的多圆定位算法,同时,将加权质心算法加入到改进后的定位算法中,这样可以有效的提高定位精确度。相比于传统的定位算法,改进后的定位算法可以将定位误差限制在4米之内。相比于传统的定位算法,这种算法更加稳定。室内定位最终还是为室内导航做准备的。在室内导航中,使用最多的算法就数Dijkstra算法和A*算法啦。相比于Dijkstra算法,A*算法增加了评估函数f(A)=g(A)+h(A),评估函数使得A*算法不会像Dijkstra算法那样将周围的节点全都扩展一遍而是先评估周围的节点,然后找到评估值最小的那个节点进行扩展。这就使得扩展的节点数大大减少,从而提高效率。但是,分析一下A*算法的思想以后发现,浪费在A*算法的时间主要是用于查找出评估值最小的点和处理非常庞大的网格地图。基于此,论文首先提出在A*算法的基础上增加方向控制的策略,这样算法将减少了访问周围节点的次数,从而提高算法的效率。另外,论文将普遍使用在网格地图中的A*算法应用到无向图中,通过使用无向图将地图中特定的位置抽象为无向图中的节点从而可以大大减少地图的复杂性。另外,又考虑到室内路径一般都是区域性的(即区域块中的节点和道路比较稠密但是区域与区域之间就比较稀疏。),所以论文又提出地图分层的策略。如果起始节点和终止节点在不同的区域块中,那么利用地图分层和硬编码的策略可以大大加快寻路过程。最后,论文给出了关于改进后的算法的实验仿真。系统借助微信摇周边功能和Ibeacon设备获取当前位置到Ibeacon锚点之间的距离。通过仿真实验,增加了方向控制的改进算法在区域块之内表现良好,在区域块之间表现一般。这是因为如果起始节点和目标节点是在同一个区域块之内的话,它们之间不需要借助其他的区域块,这样就不会受其他区域块的位置的影响。在寻路过程中增加方向控制可以让目标朝着目标节点前进。实验证明,在同一区域块中,增加方向使得算法的效率提高18.2%。另一方面,由实验可知,增加了分层寻路策略的改进算法在区域块之内表现一般,在区域块之间表现良好。这是因为如果起始节点和目标节点不在同一个区域块之内的话,它们之间的导航就需要借助其他的区域块,这时候导航过程就会受其他区域块的位置的影响。如果这个中转区域块在起始节点和目标节点的连线上的话,那么按方向寻路的过程就不会受中转区域块的影响。如果中转区域块不在起始节点和目标节点的连线上的话,假如继续按照方向寻路的话就会发现无路可走然后还要再返回来继续寻找;假如按照分层思想寻路的话就会先找到起始节点到中转区域块的道路,然后再找中转区域块到目标节点的道路。实验证明,在不同区域块中,增加分层寻路的思想使得算法的效率提高14.1%。