|
三、文献综述（或调研报告）
现代社会正在逐渐从海量数据时代向智能时代迈进，刺激和促进了大量新兴技术的迅猛发展[1]。位置服务作为一种基础服务，在国家战略新兴产业中占据了举足轻重的地位，在物联网、智慧地球、城市交通和医疗卫生等领域发挥着重要的基础性支撑作用[2]。目前，室外定位系统，诸如美国的 GPS（Global Positioning System）和中国的北斗定位系统技术上已经十分成熟[3]，定位精度达到米级，为全球广大用户提供定位、导航、授时与通信等服务。但是受到室内复杂的电磁环境和非视距误差等影响，室外定位技术无法直接迁移至室内为人们提供位置服务[4]。
室内导航与定位系统是指在各种室内空间中采用不同技术来实现人员室内导航以及对人员、物体的定位与跟踪。随着物联网技术的发展，人员、物体在经济行为、个人活动、军事等应用领域的定位需求越来越多。在室外有全球卫星导航系统(global navigation satellite system，GNSS)，是一种普适且成熟的方案可以让人们在室外实现导航与定位;但是在室内空间越来越庞大的今天，各个工厂车间、大型购物商城、办公楼、地铁站的不断建设，以及5G 技术的日趋成熟更是让人们看到了室内定位技术广阔的应用前景，由此催生了诸如室内导航等位置增值服务的涌现与发展[5]。目前室内导航定位系统大都基于临近探测、三角、多边定位、指纹定位法来实现，或者为了提高精度采取组合定位的方法。但是由于多路径效应影响，室内环境易变、复杂，尚未有一种普适的解决方案;所以如何提升精度、实时性、安全性，提高可扩展能力，降低成本仍然是研究的热点，使得人们无论在生活还是工作环境中可以随时随地获取位置信息，享受基于位置服务带来的便捷。
针对室内导航市场这一需求，国内外都对此进行了大量研究。
国外，1992年，英国剑桥ORL的Active Badge系统就是最早期的室内定位系统之一。它是一种使用红外线收发器，无需测距的定位系统。不过该系统的缺点十分明显，就是难以部署大规模网络，且红外线受光线干扰影响严重。之后Microsoft公司在1998年开发了基于RSSI技术的室内无线射频定位系统，利用信号传播模型和经验测试相结合的场景法进行定位，Microsoft公司将其命名为RADAR定位系统。不过该系统同样没有解决受外界环境影响这一问题，使其只能满足一些区域定位的要求。
为了实现小范围的精准定位，1999年Bat System作为Active Badge系统的后继发展，它使用超声波和射频信号接收器，利用TOA技术进行定位实现了最高达3cm的精准定位。取得了一定突破后，2000年麻省理工大学研制了Cricket系统，这是基于TDOA技术的定位系统，它从硬件的尺寸和价格上取得了一定的成就，是目前仍然在使用的室内定位形同之一。随后2002年，加利福尼亚大学研发出基于TOA和RSSI两种技术进行定位的Calamari系统。
相较于国外，国内无线定位系统发展起步较晚，但发展速度非常快。很多大中小型公司都相继推出了自己的定位解决方案。其中比较典型的有：中兴的CDMA移动通信系统定位业务解决方案、康柏电脑公司的移动定位服务解决方案、中软安人的3G车载无线定位系统等。
以上是比较典型的室内定位系统，除此以外，近年来国内外很多公司、高校、研究所也根据具体的应用设计出了很多无线定位系统。其中使用的主流定位技术主要是以下几种：基于传感器的室内定位技术、基于射频信号的室内定位技术、融合定位技术。其中基于传感器的室内定位技术又可以分为红外线定位、超声波定位、惯性导航定位、视觉定位。基于射频信号的室内定位技术分为WiFi定位、蓝牙和紫峰定位、蜂窝网络定位、射频识别定位、超宽带定位。
在这些技术中，应用比较广泛的是WiFi定位技术，蓝牙定位技术。
首先是WiFi定位技术，利用WiFi 信号实现室内定位有2 种方法，测距交汇法和指纹匹配法。测距交汇法是指利用信号强度衰减模型将WiFi 信号从接入点到接收机的信号衰减强度转化为2 者之间距离，采用三角定位法，根据3 个以上接入点到接收机之间的距离约束对接收机的位置进行估算。该方法优点在于无需建立维护数据指纹库，且定位精度比指纹匹配法精度高；缺点在于信号强度衰减模型与室内环境强相关，由于室内环境复杂多变且非视距现象严重，很难获取准确的信号强度衰减模型。指纹匹配法是将难以直接测量的位置信息和容易获取的信号特征（如无线信号强度）建立映射关系，即对应每个室内场景的位置坐标建立专属的信号特征指纹，从而匹配估算出待测目标的空间位置。指纹匹配法分训练和定位2 步进行：训练是将定位环境划分网格，并在网格点采集信号指纹，如WiFi 强度，建立指纹库；定位是将接收到的信号特征测量值与指纹库中的值进行比对，通过相似性分析得到室内位置估计。与测距交汇法相比，该方法的优点在于不需要求解信道衰减模型，缺点在于指纹库的构建需要耗费大量人力。目前，国内有多家单位致力于研究WiFi 定位技术，在传统WiFi 室内定位的多个方面逐步取得技术突破和进步，主要包括指纹库采集成本降低、指纹库精度提升和匹配方法的优化等等。
其次是蓝牙定位技术，与WiFi 定位原理相同，蓝牙定位分为测距交汇法和指纹匹配法。由于绝大多数智能手机终端都自带蓝牙模块，方便大范围地普及和场地设备的部署；但是基于蓝牙的定位技术容易受到外部噪声信号的干扰，信号稳定性较差，通信范围较小。最常用的蓝牙定位技术是基于蓝牙4.0 的低功耗蓝牙技术，即iBeacon 技术，该技术具有低功耗、连接速度更快、传输速率高、信号传输稳定安全无干扰等特点。iBeacon 技术尚未大规模工程应用，其原因在于需要高密度部署蓝牙信标，加之软件费用较高，使得该系统成本偏高。蓝牙设备同样可作为无线接入点，与WiFi 定位技术类似；因此指纹匹配算法同样应用广泛，针对信号范围小、稳定性差等特点，经常与WiFi 组合应用来实现室内定位的小范围区域增强。国内有几家企业开发了iBeacon 的产品，包括SENSORO、四月兄弟、智石科技和Drop Beacon；但针对蓝牙定位技术的理论研究较少，主要集中于定位算法层面。
不过一个优秀的室内停车导航系统除了需要室内定位技术外，还需要合适的路径规划算法的辅助。路径规划是智能车辆环境感知和运动控制的桥梁，也是智能驾驶的基础[6]。国内外关于路径规划算法的研究有许多，如菌群算法和遗传算法。《一种基于Dijkstra算法[J]的机器人避障路径规划方法》作者提出了使用Dijkstra算法来解决机器人路径规划问题[7]。在路径搜索的过程中，可以得到最短的路径，但所有的节点信息都需要提前得到。当节点较多时，节点网络变大，导致响应时间长，算法效率低。《机器人路径规划的光栅模型构建与蚁群算法解决方案》的作者提出利用蚁群算法建立路径规划的栅格模型[8]。该方法虽然能有效地解决路径规划问题，但它容易陷入局部最优的陷阱，收敛速度较慢。目前比较常用的便是启发式算法，启发式算法(heuristic algorithm)就是对通过算法对起点到终点的一个移动代价和估算代价进行整合，判断出哪条路线的代价最小，求解出最优化的路径，该思想就是，从起点开始对其周围的结点进行代价评估选取最优结点然后重复评估选取，代价不是最优的就不进行遍历。
在启发式算法中A*算法便是一种很优秀的算法，也是路径规划中常被使用的一种算法。
A*算法是于1968在P. E. Hart, N. J. Nilsson and B. Raphael三人发表的一片论文中提到的[9]。该论文首次向人们展示了A*算法。A*算法是基于Dijkstra算法的并在该算法上进行了扩展。A*算法相对Dijkstra算法来说，效率更好、操作简单、快速响应和准确性高。
A*算法就是启发式算法当中比较经典的，A*算法是以Dijksra为基础的启发式搜索算法[10]并且结合深度和广度算法的特点，在能够得到最优解的同时还能减少搜索的范围从而减少内存和时间的消耗。
A*算法，A*（A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是解决许多搜索问题的有效算法。算法中的距离估算值与实际值越接近，最终搜索速度越快。
但A*算法也有着他的局限性，虽然该方法在优化最短路径方面比其他方法更有效，但当面对大量节点时，该方法的搜索时间仍然相对较长，需要进一步改进。目前关于这一方面的研究有许多，其中一种便是BB-Astar算法[11]，其旨在通过利用双向搜索策略和二叉树改进Astar算法，提出了约束路径规划问题的解决方案。
【参考文献】
[1]Safaltin S, Gencer O, Morgul M C, et al. Realization of four-terminal switching lattices:
Technology development and circuit modeling[C]//2019 Design, Automation & Test in Europe Conference & Exhibition (DATE). IEEE, 2019: 504-509.
[2] Rajalakshmi K, Goyal M. Location-Based Services: Current State of The Art and Future
Prospects[M]//Optical and Wireless Technologies. Springer, Singapore, 2018: 625-632.
[3] Ding W, Tan B, Chen Y, et al. Evaluation of a regional real-time precise positioning system based on GPS/BeiDou observations in Australia[J]. Advances in Space Research, 2018, 61(3): 951-961.
[4] Stocker M, Großwindhager B, Boano C A, et al. SnapLoc: an ultra-fast UWB-based indoor localization system for an unlimited number of tags: demo abstract[C]//Proceedings of the 18th International Conference on Information Processing
in Sensor Networks. ACM, 2019: 348-349.
[5] 梁森.面向室内导航的路径规划方法研究[D]. 哈尔滨工程大学,2020.
[6] 陈志，自动驾驶汽车简介。北京：北京科技大学出版社，2014.
[7] 邹益民、杨高、高碧岳。一种基于Dijkstra算法[J]的机器人避障路径规划方法。数学实践与理解，2013,43（10）：111-118.
[8] 尹柴、唐秋华、邓星星等。机器人路径规划的光栅模型构建与蚁群算法解决方案。机械设计与制造，2016（4）：178-181.
[9]Zhu Yunhong, Yuan Yi. Optimal path search based on improved A* algorithm[J]. Computer Technology and Development, 2018, v.28; No.252(04):55-59.
[10] P. E. Hart, N. J. Nilsson and B. Raphael, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths," in IEEE Transactions on Systems Science and Cybernetics, vol. 4, no. 2, pp. 100-107, July 1968, doi: 10.1109/TSSC.1968.300136.
[11]Zhe Xu,Xin Liu,Qianglong Chen．Application of Improved Astar Algorithm in Global Path Planning of Unmanned Vehicles[C]//Chinese Automation Congress.2019
|
