智能导航系统的研究与设计 .docx

《智能导航系统的研究与设计 .docx》由会员分享，可在线阅读，更多相关《智能导航系统的研究与设计 .docx（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、智能导航系统的研究与设计摘要 如今，随着我国社会的不断发展，国内旅游业的发展以及交通工具的增加。智能导航成为了解决交通困难的急切需求。目前室外导航技术已经相当成熟，通过GPS导航可以规划出一条最优的路线到达目的地。但随着楼盘的不断增加，人们在室内寻路的困难逐渐上升。室内的错综复杂的地形使得GPS并不能精准的导航定位，所以室内定位导航系统的应用前景十分的广泛。本文主要是对于智能导航系统研究与设计。首先对于现有的多种无线技术与几种定位导航算法的研究与比较，然后对于最优路径选择算法的研究，主要选取常规的导航系统所用到的两种经典算法，并对于A*算法、Dijkstra算法这两种算法进行阐述。通过MATL

2、AB平台进行算法的实现，最后对于已有的算法进行比较、改进。关键词 导航 最佳路径选择算法 算法优化 MATLAB平台实现ResearchandDesignofIntelligentNavigationSystemAbstract Nowadays, with the continuous development of our society, the development of domestic tourism and the increase of means of transportation. Intelligent navigation becomes an urgent need

3、to solve the traffic problems. At present, outdoor navigation technology has been quite mature, through GPS navigation can plan an optimal route to the destination. But with the continuous increase of the real estate, peoples difficulties in finding their way indoors are gradually increasing. Becaus

4、e of the complex indoor terrain, GPS can not accurately navigate and locate, so the application prospect of indoor positioning and navigation system is very wide.This paper is mainly about the research and design of intelligent navigation system. First of all, the research and comparison of the exis

5、ting wireless technology and several positioning and navigation algorithms, and then for the research of the optimal path selection algorithm, mainly select the two classical algorithms used in the conventional navigation system, and elaborate the A* algorithm and Dijkstra algorithm. Through the MAT

6、LAB platform to achieve the algorithm, finally, the existing algorithm is compared and improved.Key word Navigation Optimal Path Selection Algorithm Algorithm Optimization Matlab Platform Implementation目 录引 言11 系统设计与分析11.1 需求分析11.2 国内外技术分析11.3 系统设计分析21.3.1 平台简介21.3.2 系统的总体设计分析22 定位技术介绍22.1 相关定位技术概述3

7、2.1.1 WIFI技术32.1.2 GPS技术32.1.3 RFID技术32.1.4 基站技术42.2 无线通信的对比43 定位导航算法43.1 定位算法43.2 Dijkstra算法53.2.1 算法概述53.2.2 算法基本思想53.2.3 算法的具体步骤63.3 A*算法73.3.1 算法概述73.3.2 算法基本思想73.3.3 算法的具体步骤74 路径算法实现84.1 算法实现对比94.1.1 Dijkstra算法94.1.2 A*算法104.2 改进后的A*算法114.3 对于算法比较分析及优化12结 论13参考文献14致 谢15引 言信息化时代的快速发展，快节奏的生活，使得人们

8、对于时间的管理要求更加的严苛，任何的事情都讲究效率。所以，无论是外出工作中的还是休闲中放松身心的人们，也无论在室内还是室外，总是希望自己能够在路上能够少些耽误时间，让自己拥有更多的精力与时间投入到最终的事情当中。而智能导航系统恰好能帮助人们节省大量的时间。针对智能导航系统中的路径规划的问题，本文主要研究的是用户导航时对于路径的优劣选择的算法对比。首先对于无线通信以及室内的定位技术进行阐述，以及通过MATLAB平台对于路径算法的实现，对比数据结果分析优缺点并选取一种算法对其进行优化，使其能在日后的导航系统中实现出最优性能。1 系统设计与分析1.1 需求分析近年来，我国社会经济步入高速发展阶段，人

9、类社会的基本面貌已经发生了天翻地覆的变化，高楼大厦也充分印证了每座美丽城市的生存和发展。汽车业、旅游业、建筑业的蓬勃发展。城市的交通压力随着车辆的增加而增加，人们对于GPS导航等系统的研究日渐改善这一压力，即使在拥堵的早晚高峰，智能导航能够为用户迅速规划出一条安全地路线供其行驶。当人们到了陌生的城市，只需通过智能导航系统中的高德地图、百度地图等等0p11，即可到达自己所需的目的地。室外的导航也极大的方便了人们的出行。室外卫星定位信号技术给人们日常生活中所带来的诸多好处也是有目共睹的，然而室外卫星定位信号技术的应用在面对传统一样封闭复杂的室内的环境的时候，效果并不显著。所以室内导航定位一旦得到运

10、用，将一定会在当今人们的生活中能够发挥举足轻重的关键性作用。1.2 国内外技术分析国外方面，欧美、俄罗斯及中国的卫星定位系统具有良好的应用前景0p2，例如北斗卫星定位系统、Gagps、Galileo以及Gaglonass0p2。GNSS卫星定位技术0p13主要具有定位可靠性好、精确度高、覆盖范围等诸多优点。国外谷歌推出了室内导航应用软件，即Google Maps Floor Marker0p50，提倡用户根据其要求跟步骤来增加室内定位导航的准确性。国内方面，我国目前北京、上海、广州等地方开始对于GPS的大力推广与应用，对于日常中的车辆倡导应用GPS，通过车辆的导航系统可以为其提供无线通信、车辆

11、定位等服务。当然室外的应用逐渐成为了主流，但是并不代表着室内的导航技术的成熟。从“十二五”起，我国制定并实施了“羲和”计划0p2，旨在构建科学高效的室内定位对地观测服务的系统，设计的室内与室外，尺寸分别等于1米，3米；国内多家大型企业、高校科研院所也陆续的开展了室内无线网络定位接入点技术的开发和研究。1.3 系统设计分析1.3.1 平台简介本文研究的两种经典的路径选择算法，为了方便直观的对其进行比较分析，选取了MATLAB软件平台对其进行实现对比。MATLAB是一款以数学计算为主的编程软件，有MathWorks公司研发应用，在交互式环境中可运用MATLAB，应用过程中可使用高级技术计算语言。进

12、行数据可视化、深入全面的数据分析，科学合理的算法开发数值求解均可使用MATLAB应用软件，组成以MATLAB与Simulink为主；前者的基本数据单位为矩阵，数学或工程中常用的形式与其指定表达式非常接近。因此运用MATLAB软件进行计算更加便捷高效，此外此应用具有和Maple等相同的优势。由此可见此软件的功能非常强大，在数学领域具有十分广阔的应用前景。并将C，C+,JAVA融入了最新版的MATLAB软件中。1.3.2 系统的总体设计分析对于导航系统的设计分析，通过已有的资料查阅，最终将系统整体拆分为三个部分进行研究与分析。第一部分是对于室内定位技术的介绍，通过了解查阅国内外相关的室内定位技术，

13、对于现有的几种无线通信技术的分析以及比较。第二部分是通过现有的几种定位算法的研究，对比各室内定位技术的优劣0p3与分析，第三部分则是对于其中的关键路径选择算法，深入全面的对比常用的A*算法与Dijkstra算法的准确度及运算效率，归纳各自的优点与不足。由于A*算法的启发函数仅包括距离这一启发信息，科学合理的优化与改进了此函数及其搜索区域，促使算法更加便捷高效。2 定位技术介绍对比于传统的的有线定位技术，无线通信技术则具有着很多的优势，一是低廉的成本，构建科学合理的无线数据传输方式，可缩减费用。二是整个工程的周期较短，相比之下无线通信所需要的通信链路可迅速建起。三是良好的适应性和扩展性，对于地理

14、环境影响较小，通过无线数传电台连接新增设备即可实现系统扩展了。而常见的无线通信技术主要由WIFI技术、GPS技术、RFID技术、基站技术0p25等。虽然在无线通信方面都能发挥作用，但是利用这些不同的技术所具有的特点和使用领域也不尽相同。2.1 相关定位技术概述相比较于室外的环境，在室内的电磁波传输要远比外界更加繁杂，室内到处都是墙壁、布置好的家具以及随时走动的人们以及物体都会影响到无线信号的的传输，从而接受的数据将会出现延迟。使得接收端的信号出现不稳定。因此，国内外的很多研究机构通过现有的无线通信技术的研究，发不了许多解决的方案，如下是对一些常见的定位技术的概述：2.1.1 WIFI技术WIF

15、I是由无线接入点以及站点组成的无线网络，其覆盖范围广阔，能够在复杂环境实现应用。其在实际的生活中应用十分方便，只需要装备日常的WIFI设施，即可实现定位，其成本较低，传输的范围较为广。接收信号、到达时间差定位法、到达时间法为常用的传统WiFi定位算法。当然WIFI定位如果不是参照的周边的信号强度图，则很容易发生定位误差。国外最典型的应用则是微软公司RADAR系统的运用0p1，通过指纹的定位方法，录入用户的指纹放入数据库，通过精密的计算将会变得十分准去从而提供准确的定位。另外，WIFI的安全性以及数据的保密程度也不如有线接入的方式。2.1.2 GPS技术GPS定位实际上就是卫星定位，其实GNSS

16、当中的一种定位。28颗卫星共同构成了GPS定位系统，其中备用卫星与工作卫星的数量分别为4颗，24颗。卫星可向地面发射导航信息等等内容，而GPS终端也将接受其发送的各项数据来计算出当前位置。并且能够安全、无误的通过特定的规定路线，到达最终的目的地，也可应用于移动终端上面更加方便人们。所以目前GPS是最为广泛的应用，但是其到室内工作是，会受到地形以及建筑的影响，准确度将大幅度下降，其成本也高昂。2.1.3 RFID技术自动识别技术中的RFID定位技术非常灵敏便捷，在物联网领域发挥着举足轻重的作用，可通过无线射频来完成非接触的双向数据通信7p23。应用范围及其广泛，包括与车辆定位、建筑等多个领域。该

17、技术可以在几毫秒内得到厘米级定位精度的信息，具有低成本、适应性好等优点，能够无视复杂的环境中进行连接。但是目前来说，RFID的技术还不够成熟，应用起来仍有些困难。2.1.4 基站技术基站定位的技术主要适用于手机中，通常也会被称为移动位置服务。移动设备的通讯过程需要借助GSM网络，即GSM网络与某蜂窝基站相连接，及时的传送数据。基站定位主要其定位迅速、成本也低，但是其准确率却不高。2.2 无线通信的对比目前而言，WIFI的技术还是广泛的运用于室内定位系统，收到了大量研究者们的欢迎。主要是会因为相比于其他的无线通信技术，WIFI技术所具备的许多的优势，能够应用于多个场景，而且所以消耗的人力物力较少

18、等。表1表示的是各无线通信对比的结果，清晰直观的列出了不同定位技术的定位精度，可靠性及所需成本。表1 各无线通信对比定位技术定位精度可靠性成本WIFI2-10m低低GPS3-10m高高RFID1-10m中低基站150-200m低高3 定位导航算法3.1 定位算法通过对比可知，不同定位方法的数据传输方式存在一定差异。例如Gps定位，WIFI定位，基站定位以及RFID定位各不相同。系统前端使得其具有丰富多样的数据传输方式，后台的定位算法决定了系统的定位效果。表2清晰直观的说明了不同定位算法的不同之处。根据下表可知常用的定位方法包括邻近探测法，极点法以及航位推算法等。表2 各定位算法对比定位原理描述

19、特点邻近探测法通过一些有范围限制的物理信号的接受，从而推测发射点附近。提供大概信息，成本低，易于搭建质心定位法根据可接收信标位置来计算质心坐标易懂，计算量小，精度取决信标密度多边定位法测量已知参考点之间距离，确定目标精度高，应用广三角定位法获取相对2个参考目标集合距离确定唯一三角形，即可确定待测目标位置精度高，应用广极点法测量相对某一参考距离和角度确定位置仅需知道一个参考点位置，因此使用非常方便，已经大地测量广泛应用指纹定位法在定位空间中建立指纹数据库，通过实际信息于数据库中参考进行对比实现定位指纹定位优势不需要参考测量点，定位精度相对较高，但是缺点是前期离线创建指纹库的工作量巨大航位推算法通

20、过计算已知运动速度和时间计算得到当前的位置数据稳定，无依赖，但是该方法存在累积误差，定位精度随时间增加而变化3.2 Dijkstra算法3.2.1 算法概述著名的迪杰斯特拉算法形成于1959年，其英文缩写为Dijkstra，这种基于贪心算法模式的算法，能够科学合理的规划单源最短路径，具有非常广阔的应用前景。迪杰斯特拉算法的工作原理是准确求解各节点至其余各顶点之间的最短路径，其中心是起始点，基于此层层拓展，在迭代过程中确定后续迭代过程的相关顶点，直至到达扩展路径的终点。此过程中不需标记顶点与原点相距最近的点。3.2.2 算法基本思想对某带权的有向图而言，迪杰斯特拉算法对应的有向图可分两组存放全部

21、顶点集合，分别为组S和组U。前者内存储了求得的所有最短路径顶点集合，源点按照一定次序陆续通过其余最短路径各顶点，并依次将各点纳入此集合中，直至组S中包括全部顶点。即算法执行完毕。后者中包括了全部不确定最短路径各顶点，将所有最短路径按照从小到大的次序排序，并将其纳入组S中。执行算法时，源点至组S中所有顶点的最短路径距离不超过源点至组U中所有顶点的最短路径距离。有向图中顶点集合到组S顶点的长度等于中间顶点的最短路径距离，也就是组U对应的顶点距离。3.2.3 算法的具体步骤算法搜索最优路径的流程图如图1所示：图1 Dijkstra算法流程图（1）初始时，可将有向图内全部顶点分别划分为S和U两个集合里

22、；S集合当中只包含起始源点s，绝大部分顶点存储于U集合，不包括起始源点s。若U集合内的各节点u与s直接相连接的顶点，则两个顶点之间有已知的边权值，距离为(s,v)，如果节点u不是节点s的直接相连接的顶点，则两个顶点直接有着无穷大的边权值；（2）依次从集合U当中找出一个顶点，设顶点至集合u的最短距离为k并将其纳入集合S；将集合U内的顶点k剔除。（3）更新起始点s与集合U各节点之间的距离，根据上文所得的k值更新剩余的顶点距离；（4）多次进行步骤2与步骤4，直至集合U内不包含顶点，此时算法执行完毕，即可求出有向图全部顶点与源点之间的最短路径。3.3 A*算法3.3.1 算法概述现阶段应用最为广泛的启

23、发式搜索算法是A*算法，其英文名称为是Heuristic Search。进行搜索时，运用此算法能够促使已知迭代步数利用率最大，还可获知算法初始状态至现阶段完成相应目标所需的相关信息。为了科学合理的引用所有信息，进而合理的评估目前节点与终点之间的距离，可运用此算法来选取相应的被检查节点，进而为用户规划此节点对应的最优路线，此节点通常具有最大搜索可能性，促使算法的运行效率最高。3.3.2 算法基本思想将当前节点n的估价函数f成功的引入到系统中的算法即为A*算法，可将其定义如下：fn=gn+hn (1) g(n)表示该点到达起始的点所需代价， h(n)表示该点到终点的曼哈顿距离， f(n)表示是g(

24、n)和h(n)的总和，从而得出最小的f(n)的值即求出的最优路径。其A*算法的核心是对于函数的估价部分，对于设计估价函数h(n)，则采用当前的节点s(p,q)到达终点v(pend,qend)距离进行评估，则有下面几种：（1） 若图形当中只有四个方向可以移动，则可以使用曼哈顿距离，则启发式函数如下：hn=x-xend+y-yend (2) （2） 若图形的任意方向均可移动，基于欧几里得距离得出启发式函数如下：hn=x-xend2+y-yend2 (3) 3.3.3 算法的具体步骤（1）初始化路网，设起始节点为s，终止节点为t；（2）初始化所有的节点并且作为没标志的节点；（3）从起始节点s开始，把

25、起始点当做节点k，选取跟起始点连接的节点为备用节点j，通过估价函数来计算得出结果；（4）从备选节点中筛选最小估值的点当做节点，通过该节点来计算其到起始点的距离；（5）重复（3）、（4），当最终的节点到达终点时，算法结束。算法搜索最优路径的流程图如图2所示：图2 A*算法流程图搜索过程当中，在估计目前节点到达目标节点的代价的同时，所计算的估计代价不能高于实际代价，只有估计代价小于实际代价，算法在运行的时候才能确保寻找出一条最优的行驶路径。4 路径算法实现4.1 算法实现对比4.1.1 Dijkstra算法（1）算法路径实现结果，如图3： 图3 Dijkstra算法路径图（2）改变地图以及实验规划

26、路线，如图4： 图4 改变地图后的Dijkstra算法路径图（3）Dijkstra算法求解通过直观的实验结果显示出来，Dijkstra算法在求解的时候，先是加载了搜索范围当中的所有的节点。并且通过路网中的信息，通过用户给定的起始点来进行遍历，并且搜索同时将道路的长度来做为选择的根据，然后使用该算法来求出的最优路径如表3所示：表3 Dijkstra算法求解的最优路径所需时间遍历节点数路径距离0.047538s30922.89950.042766s0.126426s29131021.313722.48534.1.2 A*算法（1）算法路径实现结果，如图5： 图5 A*算法路径图（2）改变地图以及实

27、验规划路线，如图6： 图6 改变地图以及实验规划路线后的A*算法路径图（3）A*算法求解同样适用A*算法求解路径，该系统会同处理Dijkstra算法时一样，但是其核心估价函数却是会根据用户给定的起始点而去进行启发式的搜索。该算法求解的最优路径如表4所示：表4 A*算法求解的最优路径所需时间遍历节点数路径距离0.028589s17422.89950.041722s0.052351s10913421.313722.48534.2 改进后的A*算法（1）改进后的算法路径实现结果，如图7： 图7 改进A*算法路径图（2）改变地图以及实验规划路线，如图8： 图8 改变地图以及实验规划路线图（3）A*算法

28、的改进根据全局环境信息，常用于科学合理的求解起始点与目标位置之间的最优路径的算法是A*算法，而此算法仍存在不足之处0p1，即已确定全局变量且已知没有动态障碍物时，才可执行此算法获得最优路径，此算法的运行效率受到动态障碍物的显著影响。编写的这种算法，并未充分考量行动物体宽度，障碍物通常会与行动物体在拐点处发生碰撞，甚至出现危险情况。基于传统A*算法，增加转弯半径，求解物体在拐点处的转动角度及方向，直角转弯可用曲线转向替换。对于此过程而言，增大转弯半径具有举足轻重的意义。在搜索环境下，可运用A*算法规划最佳路径，然而环境条件变化时，已知的最佳路径不再适用。对于传统的A*算法而言，若环境条件不确定，

29、可适当更改搜索所得路径的结点序列及部分障碍物节点，促使障碍物对路径的影响最小，进而获得最佳搜索路径。如表5所示：表5 改进后的A*算法求解的最优路径所需时间遍历节点数路径距离0.214013s18123.54650.187992s0.122643s11614121.848123.49484.3 对于算法比较分析及优化通过上面所展示的图片以及表中的内容，我们可以清晰直观的比较两种算法的优劣，并且对其进行分析比较。相比较两种路径我们不难发现，Dijkstra算法相比于A*算法，该算法搜索的范围很大，效率却很低。而A*算法相比较之下搜索的范围不大，但效率却极其的高。其中A*算法当中最为核心的部分就是

30、会在下一次选择搜索的节点之前，先将周围所有已知的但是还未搜索的节点当中，搜索时，首先要选取最小f值结点。按照f值从大到小的顺序一次排列全部已探知却并未搜索过点。进行搜索时，可基于与广度优先算法框架类似的框架，及时获知队首元素，通常f值为第1个元素，求解可能子结点的f值，g值与h值，优先队列无解或搜索到终点时，整个搜索过程结束。运用迪杰斯特拉算法可求解某路网中的最优路径。值得关注的是，动态导航系统通常需要进行安全便捷且准确高效的数据处理，但路网中包括海量数据时，此算法的运行速率较慢。由此可见，在设计这种导航系统时不宜运用此算法。深入全面的剖析迪杰斯特拉算法可知，其不足之处是进行全局搜索，因此速率

31、较慢，所需时间较长；若系统具有非常庞大的路网，需要占据较大空间存放相应的中间结果。便捷高效的A*算法可以有效的管控搜索规模。这种启发搜索算法运用了估价函数，促使其具有良好的搜索效果，因此在设计灵活安全且便捷高效的动态导航系统时可运用此算法。估价函数可表示为h(n)，对于此算法具有至关重要的作用，若结点n与目标结点之间的实际距离比h(n)估价小，此时相应的算法节点数较少，但算法运行速率较快，所得结果不一定是最优解。若二者相等，则可快速求得与实际值非常接近的最优解。若h(n)为0，则表明算法启发过程中并未应用现有信息，即为Dijkstra算法。结 论随着人们在室内的活动时间越来越久，室内定位导航越

32、来越受到大众的欢迎。而当人进入到新的环境时，无法获取当前位置的射频信号和位置，组合导航定位精度也会大大折扣。因此，未来的研究焦点是开发便捷高效的室内导航系统，科学合理的应用最优路径算法具有举足轻重的意义。便捷的导航系统能够大大提高人们在室内复杂建筑物中快速寻找到自己所要的目的地。比这所学知识有限，所得的研究结论具有一定局限性，需要在今后的研究过程中不断完善。研究内容如下：（1）分析研究国内外智能导航系统的研究与发展趋势，本文通过各种数据的对比，对于室内定位技术的无线通信技术的分析对比。定位算法的介绍分析。（2）对路导航算法中的关键路径选择算法的选择，已经对于现有的几种经典的路径选择算法的分析与

33、比较，选择出适合算法应用于合适的场景。（3）对于已有的算法有可能的进行优化，使其在运用过程当中能够对于Array数组的优化，并且打开关闭标记，换掉不用重置。本文主要对于智能导航系统的研究与设计，并对其进行了实验验证，实验结果表明，本文中所分析对比的三种算法能够充分应用到现实的导航定位当中，而就整体效果而言，目前的算法仍然有较大的提升空间，更深入的研究有待进一步的展开，后续的工作内容将继续对于路径选择算法的深度学习，对于用户在使用定位导航的时候能够更加快速的贴切的为用户规划出一条路线。对于自己的一些不足，将会多加学习多加思考，对于此类进行更加深层次的研究。参考文献1莫愁. 附有轨道信息约束的动态

34、GNSS周跳探测与修复方法D.西南交通大学,2015.2李冰. 超声波室内定位导航的设计与实现D.哈尔滨理工大学大学,2017.3梁焰松. 室内导航路径规划算法的实现研究D.华中科技大学,2015.4关惠平. 全球卫星导航定位系统及其定位原理，兰州铁道学院报自然科学版.2003,8,4(22):66-71.5毛勤. 基于 WIFI 位置指纹的室内定位算法的研究与优化D.广东工业大学,2016.6Bahl P,Padmanabhan V N.RADAR:An In-Building RF-based User Location and Tracking SystemJ.Proc.IEEE INF

35、OCOM 2000,2:775-784.7丁晔. 基于RFID信号特征的室内定位技术研究与实现D.南京邮电大学.2018.8刘建业. 基于 WLAN 的室内 WiFi 的室内定位技术的研究与实现D.云南财经大学,2013.9徐定杰,刘明凯,沈峰等. 基于MBOC调制的北斗导航信号的多径误差分析J.哈尔滨工业大学学报.2013,45(8):122-128. 10Ning Y,Zhong-Qin W,Malekian R,etal.Design of Accurate Vehicle Location System Using RFIDJ.Elekstronika Ir Elektrotechni

36、ka.2013,19(8):1105-110.11徐静. 室内移动导航系统的路径规划方法研究：D.长春：长春理工大学,2009.12陈锐志,陈亮. 基于智能手机的室内定位技术的发展现状和挑战J. 测绘学报，2017，46(10)：1316-1326. DOI: 10.11947/j.AGCS.2017.20170383.13宗传苓,李相勇,王英涛. 出行前路径选择的多目标规划模型J. 交通运输系统工程与信息,2005,15(16):58-61.14李志健,郑新奇,王淑晴等. 改进A*算法及其GIS路径搜索中的应用J.系统仿真学报,2009,21(10):3116-3119.15徐伟. 基于 Android 手机的室内定位技术研究与实现D. 华中师范大学,2014.第 15 页