移动社交网络中的动态轨迹推测算法

摘要

本文研究讨论了一种全新的位基服务算法，从数据挖掘的角度看待LBS问题。这样解决了原来依靠移动运营商基站或者GPS的方案在某些场景下低效或者完全无法工作的问题。所有应用这种定位服务的设备间通过短距离通信时别对方（Social Context），同时记录下来接触到对方的时间。经过一段时间后，将这种分布式的会面记录（Contact）汇总的中央服务器。通过本文的算法可以推测出所有人的历史移动轨迹。
　　本文提供了两种算法解决轨迹推测。一种是基于BFS的搜索算法，该算法假设系统内节点按照固定速度运动，在现实中较难应用。另一种是基于MMP模型的概率推测算法，该算法使用概率分布描述节点的运动模型，较为真实，且准确率也较高。

目录

封面

中文摘要

英文摘要

目录

第一章 绪论

1.1课题背景

1.2研究目的与意义

1.3本文研究内容与主要工作

1.4文章组织结构

第二章 MTIP问题定义以及数学模型

2.1 MTIP描述

2.2两种解决MTIP的思路

2.3本章小结

第三章 基于BFS搜索算法

3.1 基本概念

3.2算法描述

3.3算法分析

3.4仿真验证

3.5结果

3.6本章小结

第四章 基于MMP模型的算法

4.1概述

4.2节点运动模型

4.3 Markov Process/Chain

4.4算法实现

4.5算法复杂度分析

第五章 结论

参考文献

致谢

攻读硕士学位期间发表的学术论文

声明