室内离散格网空间Dijkstra最短路径算法优化
|
摘要
针对接收信号强度指示指纹库室内定位中的离散格网空间场景,将次区域间与区域内最短路径分开处理,在起终点次区域内寻找其与最短路径的交点;然后以此交点代替次区域内的网络节点,优化原生Dijkstra室内最短路径算法;通过室内格网空间的区域划分、网络节点设置及区域与节点之间的关系界定、优化后的Dijkstra算法,结合PostGIS/pgRouting数据库工具,最终得到一条综合最优的最短路径。实验数据显示,优化后的方法不仅可以得出正确的结果,而且在数据存储和计算复杂度方面提升了约90%。
This paper put forward an optimization method for Dijkstra shortest path algorithm for discrete grid space for indoor positioning based on RSSI(Received Signal Strength Indicator)fingerprint database.In the method,the shortest paths were calculated separately among different sub-zones and within sub-zone,and the intersection between the shortest path and the sub-zone including the starting or end node obtained to replace the node in sub-zone.Furthermore,with the indoor discrete grid spatial partitioned,network vertexesset,relationship between zones and vertexes confirmed,and the Dijkstra algorithmoptimized,abest shortest path was achieved using PostGIS/pgRouting database.The experiment shows that the optimized method not only gets the correct results,but also improves the efficiency on data storage and computing complexity by about 90%.
This paper put forward an optimization method for Dijkstra shortest path algorithm for discrete grid space for indoor positioning based on RSSI(Received Signal Strength Indicator)fingerprint database.In the method,the shortest paths were calculated separately among different sub-zones and within sub-zone,and the intersection between the shortest path and the sub-zone including the starting or end node obtained to replace the node in sub-zone.Furthermore,with the indoor discrete grid spatial partitioned,network vertexesset,relationship between zones and vertexes confirmed,and the Dijkstra algorithmoptimized,abest shortest path was achieved using PostGIS/pgRouting database.The experiment shows that the optimized method not only gets the correct results,but also improves the efficiency on data storage and computing complexity by about 90%.
引文
[1]陈锐志,陈亮.基于智能手机的室内定位技术的发展现状和挑战[J].测绘学报,2017,46(10):1 316-1 326.
[2]ZHAO Z,WANG J,ZHAO X,et al.Navi light:indoor localization and navigation under arbitrary lights[C].IEEE Conference on Computer Communications.Atlanta:IEEE,2017.
[3]ZHANG A,YUAN Y, WU Q,et al.Wireless localization based on RSSI fingerprint feature vector[J].International Journal of Distributed Sensor Networks,2015(9):8.
[4]吴文坛,田挚,付晨.室内定位多传感器空间的配准算法[J].测绘科学,2016,41(10):40-43.
[5]LOW C G,LEE Y L.A better user experience in mobile indoor navigation system using augmented reality[J].Advanced Science and Technology Letters,2015(9):137-140.
[6]FADZLI S A,ABDULKADIR S I,MAKHTAR M.Robotic indoor path planning using Dijkstras algorithm with multilayer dictionaries[C].International Conference on Information Science and Security.Seoul:IEEE,2015:1-4.
[7]ZHANG D Z.Towards an open global Wi-Fi indoor positioning system via implicit crowdsourcing[D].Bedford:University of Nottingham,2017.
[8]SABRI N A M,BASARI A S H,HUSIN B.The utilization of Dijkstras algorithm to assist evacuation route in higher and close building[J].Journal of Computer Science,2015,11(2):330-336.
[9]孙凯,吴红星,王浩,等.蚁群与粒子群混合算法求解TSP问题[J].计算机工程与应用,2012,48(34):60-63.
[10]刘东林,陈银银.基于花香浓度的人工蜂群算法在机器人路径规划中的应用[J].华东理工大学学报(自然科学版),2016,42(3):375-381.
[11]梅海涛,王毅,华继学.直觉模糊小生境的自适应遗传算法求解旅行商问题[J].计算机科学,2016,43(12):46-49.
[12]SAMAHKA F A,HUSSIN B,BASARIA S H.Modification of Dijkstras algorithm for safest and shortest path during emergency evacuation[J].Applied Mathematical Sciences,2015,9(31):1 531-1 541.
[13]王树西,李安渝.Dijkstra算法中的多邻接点与多条最短路径问题[J].计算机科学,2014,41(6):217-224.
[14]张少平,江辉仙,张明锋.基于移动终端的楼宇应急疏散导航系统设计[J].福建师范大学学报(自然科学版),2017,33(1):22-27.
[15]王华.改进Dijkstra算法的城市道路最短路径仿真研究[J].测绘科学,2013,38(4):149-151.
[16]孙文彬,谭正龙,王江.基于多粒度通讯的Dijkstra并行算法优化[J].中国矿业大学学报(自然科学版),2014,43(5):938-943.
[17]黄艺坤.Dijkstra算法在室内移动导航最短路径寻址的改进[J].福建师范大学学报(自然科学版),2017,33(3):13-18.
[18]邓中亮,肖占蒙,贾步云.城市空间无线定位信号传播模型校正方法研究[J].导航定位与授时,2017,4(3):11-16.
[19]霍欢,杨沪沪,郑德原.一种改进的RSSI指纹库定位算法[J].计算机应用研究,2017,34(9):1-8.
[20]贲进,童晓冲,周成虎.正八面体的六边形离散格网系统生成算法[J].地球信息科学学报,2015,17(7):789-797.
[21]赵学胜,贲进,孙文彬.地球剖分格网研究进展综述[J].测绘学报,2016(S1):1-14.
[2]ZHAO Z,WANG J,ZHAO X,et al.Navi light:indoor localization and navigation under arbitrary lights[C].IEEE Conference on Computer Communications.Atlanta:IEEE,2017.
[3]ZHANG A,YUAN Y, WU Q,et al.Wireless localization based on RSSI fingerprint feature vector[J].International Journal of Distributed Sensor Networks,2015(9):8.
[4]吴文坛,田挚,付晨.室内定位多传感器空间的配准算法[J].测绘科学,2016,41(10):40-43.
[5]LOW C G,LEE Y L.A better user experience in mobile indoor navigation system using augmented reality[J].Advanced Science and Technology Letters,2015(9):137-140.
[6]FADZLI S A,ABDULKADIR S I,MAKHTAR M.Robotic indoor path planning using Dijkstras algorithm with multilayer dictionaries[C].International Conference on Information Science and Security.Seoul:IEEE,2015:1-4.
[7]ZHANG D Z.Towards an open global Wi-Fi indoor positioning system via implicit crowdsourcing[D].Bedford:University of Nottingham,2017.
[8]SABRI N A M,BASARI A S H,HUSIN B.The utilization of Dijkstras algorithm to assist evacuation route in higher and close building[J].Journal of Computer Science,2015,11(2):330-336.
[9]孙凯,吴红星,王浩,等.蚁群与粒子群混合算法求解TSP问题[J].计算机工程与应用,2012,48(34):60-63.
[10]刘东林,陈银银.基于花香浓度的人工蜂群算法在机器人路径规划中的应用[J].华东理工大学学报(自然科学版),2016,42(3):375-381.
[11]梅海涛,王毅,华继学.直觉模糊小生境的自适应遗传算法求解旅行商问题[J].计算机科学,2016,43(12):46-49.
[12]SAMAHKA F A,HUSSIN B,BASARIA S H.Modification of Dijkstras algorithm for safest and shortest path during emergency evacuation[J].Applied Mathematical Sciences,2015,9(31):1 531-1 541.
[13]王树西,李安渝.Dijkstra算法中的多邻接点与多条最短路径问题[J].计算机科学,2014,41(6):217-224.
[14]张少平,江辉仙,张明锋.基于移动终端的楼宇应急疏散导航系统设计[J].福建师范大学学报(自然科学版),2017,33(1):22-27.
[15]王华.改进Dijkstra算法的城市道路最短路径仿真研究[J].测绘科学,2013,38(4):149-151.
[16]孙文彬,谭正龙,王江.基于多粒度通讯的Dijkstra并行算法优化[J].中国矿业大学学报(自然科学版),2014,43(5):938-943.
[17]黄艺坤.Dijkstra算法在室内移动导航最短路径寻址的改进[J].福建师范大学学报(自然科学版),2017,33(3):13-18.
[18]邓中亮,肖占蒙,贾步云.城市空间无线定位信号传播模型校正方法研究[J].导航定位与授时,2017,4(3):11-16.
[19]霍欢,杨沪沪,郑德原.一种改进的RSSI指纹库定位算法[J].计算机应用研究,2017,34(9):1-8.
[20]贲进,童晓冲,周成虎.正八面体的六边形离散格网系统生成算法[J].地球信息科学学报,2015,17(7):789-797.
[21]赵学胜,贲进,孙文彬.地球剖分格网研究进展综述[J].测绘学报,2016(S1):1-14.