基于位置的服务：问题、模型及算法

　　本书共分八章，重点研究了几种典型的基于位置的服务（LBS），如道路网络的基于地理空间距离的邻近检测、时间感知道路网络中基于时间距离的临近检测、基于GPS轨迹推荐兴趣点（POI）、时间相关道路网络中的成本Z优路径查找、时间相关道路网络中带约束的节能路径查找等。对于每种典型的基于位置的服务，从研究者的角度，详细地介绍了其背景、研究动机、问题描述、算法模型、实验结果等;还补充了市场上对具体LBS位置服务问题的研究等内容。 本书所述的对具体LBS的研究方法及实验分析，对从事LBS相关研究的科技工作者及相关硕博研究生具有较大的启发与指导。

　　刘雅琼，博士，北京邮电大学讲师、硕士生导师，中国通信学会高级会员，2016年5月于新加坡南洋理工大学获得博士学位。讲授《Python编程与实践》《嵌入式操作系统》《无线物联网基础与应用》等课程。主要研究方向是基于位置的服务（LBS）、边缘计算、物联网。

目录
第1章绪论1
11基于位置的服务的背景1
12LBS的典型应用1
121道路网络中基于地理空间距离的邻近检测1
122时间感知道路网络中基于时间距离和移动边缘计算的临近检测3
123由GPS轨迹进行兴趣点推荐4
124时间相关道路网络中的成本最优路径查询6
125时间感知道路网络中带约束的节能路径规划7
13本书贡献总结8
14本书章节安排10
第2章相关研究11
21基于位置的服务11
211LBS相关内容11
212LBS的位置管理11
22连续空间查询处理12
23邻近（临近）检测13
231道路网络中的通信模型13
232欧几里得空间的邻近检测解决方案14
233道路网络空间的邻近检测解决方案15
234时间感知道路网络空间的临近检测解决方案15
24POI推荐16
241聚类算法16
242相似性度量16
243位置识别和推荐17
244利用时间信息的推荐18
245利用地理信息的推荐18
25时间相关道路网络中成本最优的路径查询18
251传统路线规划问题19
252静态道路网络中的路线规划19
253传统的时间相关的路径查找问题19
254节能路径规划19
255其他路径规划工作20
256与其他成本最优路径规划问题的比较20
26时间感知道路网络中带约束的节能路径查找20
261传统路线规划问题和静态道路网络中的路线查询20
262无旅行时间预算约束的时间感知路径查找21
263最低能耗路径规划21
264适用于WCSPP的方法21
265工作的新颖性21
27本章小结22
第3章道路网络中基于地理空间距离的邻近检测23
31邻近检测问题定义23
32固定半径移动检测方法24
321客户端服务器通信模型25
322安全移动区域25
323剪枝引理26
324服务器端和客户端算法28
325FRMD的通信成本分析29
33自动调整方法31
331RMDRN / CMDRN方法31
332基于半径的应激移动检测方法32
34服务器端计算成本优化33
341通知策略的优化33
342每对节点间网络距离的计算33
343触发时间技术34
35实验34
351实验设置34
352FRMD实验35
353自动调整方法性能实验36
354服务器端计算成本优化实验38
355现实世界中移动物体的实验39
36结论40
37本章小结40
第4章时间感知道路网络中基于移动边缘计算的临近检测41
41问题陈述41
411定义和符号41
412问题设定43
42基于MEC的临近检测体系架构43
43算法：基于时间的移动区域检测方法44
431时间感知网络中的移动区域45
432剪枝引理45
433客户端和服务器端算法47
44服务器端计算成本优化49
441线下点到点网络距离预计算49
442使用OpenMP进行并行计算49
45实验49
451实验设置49
452TMRBD实验50
453MEC对通信时延的减少实验52
454MEC影响通信成本的实验53
455服务器端计算成本优化技术的实验54
46结论55
47本章小结56
第5章基于GPS轨迹的兴趣点推荐57
51问题定义和框架概述57
52兴趣点推荐模型框架详述58
521数据预处理58
522提取语义POI59
523挖掘受欢迎度效应60
524挖掘时间效应61
525挖掘地理效应64
526统一推荐计分函数65
53实验66
531实验设置67
532预处理68
533DTBJCluster与DJCluster的比较69
534PTGRecommend框架的性能评估70

54结论74
55本章小结74
第6章时间相关道路网络中成本最优的路径查找75
61问题表述75
611问题设置和定义75
612油耗和行驶时间函数78
613通行费函数80
62算法80
621计算ns的每个后代节点的最早到达时间λi81
622计算候选节点的最新到达时间θi82
623对候选节点进行拓扑排序82
624计算最低成本83
625回溯成本最优路径85
626时间复杂度分析87
63实验88
631实验数据集89
632简化的通行费函数89
633实验目的和角度89
634参数的默认值和实验设置90
635实验结果91
64结论98
65本章小结98
第7章时间感知道路网络中带约束的节能路径规划99
71问题表述99
72算法101
721预处理102
722作为基准的蛮力求解法102
723通用动态规划解决方案：标签设置算法103
724近似算法ECScaling105
725贪心算法111
73实验112
731实验设置113
732算法评估114
74结论118
75本章小结118

第8章总结与展望119
8.1总结119
8.2展望120
8.2.1从某地到推荐POI的最佳路径查找121
8.2.2从GPS轨迹挖掘语义模式121
8.2.3动态道路网络中的多偏好路径查找122
8.2.4基于校园WiFi轨迹的学习成绩预测123
参考文献124