论文总字数：30060字

目 录

1.绪论 5

1.1 研究背景 5

1.2 研究意义 5

1.3 研究的重要性和必要性 5

2.LBS方法研究现状 6

2.1最短路径算法国内外研究现状 6

2.2查找兴趣点算法研究现状 7

3.LBS基本原理 7

3.1 LBS特点 7

3.2 LBS分类 8

4.LBS算法概述 9

4.1现有算法概述 9

4.1.1 启发式搜索算法 9

4.1.2 Dijkstra算法 10

4.1.3 弗洛伊德算法 11

4.1.4 双向搜索算法 12

4.1.5 限制区域搜索算法 12

4.2 最短路径算法分析比较 13

4.3 对Dijkstra算法和Floyd算法的验证与分析 15

4.3.1单源节点问题 15

4.3.2多源节点问题 16

5.LBS查找兴趣点算法 18

5.1 基于球面距离 18

5.1.1 Great-circle 球面距离公式 18

5.1.2 Haversine formula球面距离公式 18

5.2 Geohash算法 20

5.2.1 Geohash算法介绍 20

5.2.2 Geohash算法实现周边查询原理 21

6.LBS查找兴趣点算法的验证与分析 22

6.1对基于球面距离算法的分析 23

6.1.1 Great-circle公式及其变形 23

6.1.2 对球面距离公式的验证分析 23

6.2对Geohash算法的分析 25

6.2.1 Geohash算法编码实例 26

6.2.2 Geohash算法策略 26

6.3 对两种算法的验证分析 26

6.4 小结 28

7.结束语 .......28

参考文献 29

致谢 31

基于位置服务LBS方法综述与分析

满富康

,China

Abstract：Location-based services have deepened people's lives more and more,it provides a lot of convenience for our lives.In this paper, we mainly study and analyze the characteristics of different shortest path algorithms, such as heuristic search algorithm, Dijkstra algorithm, Floyd algorithm, bidirectional search algorithm and restricted region search algorithm,and make a summary and description of the shortest path algorithm for different situations. In the CodeBlocks platform,we validate and analyze the Dijkstra algorithm and the Floyd algorithm.The analysis of the algorithm for finding nearby points of interest mainly focuses on the spherical distance algorithm and Geohash algorithm,in the Eclipse (integrated development environment),we use Java language and PHP（Hypertext Preprocessor）language to analyze and validate these two algorithms. The results show that the implementation efficiency of Geohash algorithm is better than spherical distance algorithm.

Key words：Location-based services;shortest path algorithm;spherical distance;Geohash algorithm

绪论

研究背景

当今社会，人们对于位置信息的获取已经成为生活中的常态。基于位置服务LBS（Location-based services）因为其集通信、定位、查询、分析于一体的独特优势，在日常生活中变得极为常见，成为当下的研究热点。

基于位置服务作为一种新型服务，将移动通讯与导航相结合是其标志性的特点。服务器根据用户的位置信息，由地理信息系统GIS(Geographic Information System)提供支持，为用户提供与位置信息有关的服务。用户通过自己的手机等设备进行定位，得到当前的位置信息（如经纬度数据），返回给服务器，进而服务器通过一系列方法满足用户的要求，实现基于位置服务。例如，用户通过手机获取当前所在的位置，根据用户个人的要求，将用户周围一定范围内的电影院、餐厅等一系列公共服务设施推荐给用户，这其实是一种较为广泛的与用户位置信息有关的新型服务。随着大数据时代的到来，信息社会的高速发展和智能移动设备的普及，LBS正在成为社会各方面研究的重点与热点，它的应用越来越广泛^[1]。

基于位置服务起源于美国，美国联邦通信委员会规定，当用户处于紧急情况下，移动通信营业商必须为用户提供求助服务。当用户处于危险情况时，用户可以使用自己的设备进行求救服务，而营业商可以根据用户设备发出的无线电信号对用户的位置进行定位，进而得到用户的所在位置进行救援，基于位置服务从此而来^[2]。

随着信息时代的发展，智能移动设备的普及，基于位置服务的各种方法得到了更多的改进与发展，本文主要对最短路径算法和查找兴趣点算法作了研究与分析。

研究意义

基于位置服务作为一种在信息时代发展必不可少的服务，存在着巨大的发展前景。随着社会经济的发展，人们所在的位置会经常发生变化，用户需要适应新的环境，这就产生了大量的数据。面对大量数据，对基于位置服务LBS的方法进行研究与分析，为今后的基于位置服务的应用提供坚实的基础，具有一定的应用价值^[3]。

对基于位置服务的方法进行研究与分析，实际上不仅仅局限于基于位置服务，方法的改进在涉及数据处理的学科都具有一定的学术价值。对基于位置服务的方法进行研究与分析，优化改进方法，可以不断完善理论，为相关学科的研究提供新的思路与方法。

研究的重要性和必要性

基于位置服务LBS在信息社会迎来了巨大的发展前景，在导航、交通、工程与抢险救灾等领域具有广泛的应用。用户不断移动的地理位置是服务的基础，随着用户的增多，服务器需要处理大量的数据，这就需要服务商不断完善与改进自己的方法，选择效率更高的方法，在保证服务准确性的前提下不断提高效率。如在导航服务中，用户需要准确地到达自己的目的地并且是最优路径，这就需要导航服务在保证导航精度的前提下，充分考虑实际路况，为用户规划出最优路径。这对于基于位置服务来说是一个需要不断完善与发展的方面^[4]。

只有为用户提供更加准确、人性化的服务，基于位置服务才能够有更好的发展。这就需要不断研究与分析基于位置服务的各种方法，在完善理论的基础上进行实际应用，促进该服务的发展。

LBS方法研究现状

对于LBS来说，它在导航、交通、工程以及抢险救灾等方面具有广泛的应用。其中，最短路径算法与查找兴趣点算法是其主要的方法。

2.1最短路径算法国内外研究现状

对于最短路径问题，很早便有学者进行研究，该问题在计算机科学、地理信息科学等学科一直是研究的热点^[5]。国内外对最短路径问题做了大量的深入研究。最短路径算法的具体形式包括：

（1）起点确定的情况，即已知出发点，求最短路径。即在图中选择一个点作为源点，求该点到图中其它节点的最短路径。

（2）终点确定的情况，该情况与起点确定的情况相反。解决该问题，需要分成两种情况。一是在无向图中，即路径没有方向，这种情况下与起点确认时的情况相同；另一种情况是在有向图中，即路径是带有方向的，这时可以将所有路径反向，认为是确定起点的情况。

（3）已知起始点和终点，求出两点间的最短路径。

（4）全局最短路径，要求计算出任意一点到其余点的最短路径。

最短路径算法有很多，常用的算法有：Dijkstra算法、Floyd-Warshall算法、（A-Star）算法、Bellman-Ford算法、Johnson算法等。最短路径算法按照路径及其周围环境的属性是否变化可以分为静态路径最短路径算法和动态路径最短路径算法^[6]。静态最短路径指的是路径的权值及其周围环境不发生变化，在图中计算静态的最短路径，主要算法有Dijkstra的标号法^[7]、算法等。动态路径最短路径算法指的是路径的属性及周围情况不断变化，在无法预测的基础上计算最短路径，如在目标不断移动的情况下求导弹的最短路径，典型的算法有（D-Star）算法^[8]。

目前最短路径问题依旧是国内外研究的热点与重点，大多集中于对该算法的应用研究。Dijkstra最短路径算法是一种经典算法，继Dijkstra之后提出了大量求解最短路径的方法。Cherkassky，Goldberg和Radzik在1996年^[9]对Bellman-Ford-Moore算法、Dijkstra算法、Incremental Graph等17种最短路径算法进行理论分析和试验评估，通过不同特征下的网络数据的试验发现，没有哪种算法在任何情况下都保持优势。Zhan（1998）^[10-11]基于实际道路网络对Bellman-Ford-Moore、Dijkstra等多种算法进行了分析和评价，针对不同规模的道路网和寻优需求（one-to-one、one-to-all、all-to-all）的测试结果显示，可以根据道路网弧长的分布范围选择合适的算法。TWO_Q(Two Queue)比较适合计算单源节点到其余点的最短距离；对于单源、目标节点或单源节点至多目标节点的情况，如果1500（为网络最大弧长），DIKBA(Dijkstra's algorithm implemented with bucket)算法较为合适，如果1500，DIKBD(Dijkstra's algorithm implemented with double buckets)算法较为合适。

2.2查找兴趣点算法研究现状

对查找兴趣点的算法研究主要集中在基于球面距离算法和Geohash算法。对于球面距离，即求出球面上两个点的距离，目前主要有Great-circle distance（大圆距离）和Haversine formula公式^[12]。

对于Geohash算法，该算法是由Gustavo Niemeyer提出。它实际上是一种地理数据编码技术，它的基础是网格划分理论。Geohash算法将目标的经纬度坐标转化为类URL(外文名：Uniform Resource Locator，中文名：统一资源定位符)的字符串编码，能够保证精确定位的前提下，减少经纬度信息存储所产生的数据冗余。因此在地物周边查询、地理围栏技术中得到了广泛的应用，该算法是一种主要的查找兴趣点算法，用于向用户推荐周边兴趣点 ^[13]。

LBS基本原理

LBS特点

LBS的特点主要体现在两个方面：一方面是指LBS是一种智能服务，该服务不仅能够对用户进行精确定位，还能够提供用户周边事物的信息与服务。另一方面是指不管是普通用户还是专业人员，不管是在移动终端还是固定终端上，都能随时随地获取与位置信息有关的服务。因此，移动性、分布性、个体感知和大众化是LBS最基本的特点^[14]。

剩余内容已隐藏，请支付后下载全文，论文总字数：30060字