面向路网的移动对象间的连续状态查询算法的研究与实现

《面向路网的移动对象间的连续状态查询算法的研究与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据分类号UDC密级学位论文面向路网的移动对象间的连续状态查询算法的研究与实现作者姓名：乔伟指导教师：王波涛教授东北大学信息科学与工程学院申请学位级别：硕士学科类别：工学学科专业名称：计算机软件与理论论文提交日期：2014年6月论文答辩日期：2014年6月21日学位授予日期：2014年7月答辩委员会主席：乔建忠教授评阅人：吴刚副教授张大波教授东北大学2014年6月万方数据AThesisinComputerSoftwareandTheoryResearchandImplementationofContinuousStateQueryAlgor

2、ithmsbetweenMovingObjectsinRoadNetworksByQiaoWeiSupervisor：ProfessorWangBotaoNortheasternUniversityJune2014万方数据独创性l声明本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者签名：名诂日期：多．五铲学位论文版权使用授权书本

3、学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。作者和导师同意网上交流的时间为作者获得学位后：半年口一年口一年半口学位论文作者签名：云铂签字日期：∥．砂≯两年囤／导师签名：7-．认纪哥签字日期：2p／争，石，2争万方数据查I垦盘堂塑±鲎焦迨塞揎璺面向路网的移动对象间的连续状态查询算法的研究与实现摘要随着基于用户位置的服务(Location．BasedService，LB

4、S)研究的日益深入，用户对LBS的需求日趋丰富。例如在智能交通领域，自动驾驶技术不仅需要解决普通的位置定位技术，更重要的是要持续监测车与周围车辆以及道路上其他物体之间的距离远近关系，保证安全行驶。现有的查询处理技术，如范围查询、最近邻查询和连续范围查询等，仅仅关注某一时刻查询点与被查询点之间的位置关系，无法满足用户对移动对象之间的连续状态查询服务的需求。移动对象间状态查询是指移动对象查询自身与周围其他移动对象之间越来越远或者越来越近的位置关系。已有的移动对象间状态查询算法主要包括朴素的状态查询算法与移动对象间的连续状态查询算法，均是基于欧氏空间

5、，难以直接应用于路网环境。本文提出了面向路网的移动对象间连续状态查询中的关键算法。针对大规模的移动对象的应用场景，移动对象间的连续状态查询算法面临着两大挑战：一方面如何快速地对海量移动对象定位；另一方面如何在路网环境下高性能地计算海量移动对象间的距离。针对上述问题，本文做了以下两方面工作：针对快速定位移动对象位置的问题，本文提出了三种移动对象定位算法。基于路段划分的移动对象定位算法通过对较长路段进行划分，对子路段构造MBRs，建立R树索引，有效地减少了MBRs之间的重叠区域和MBRs对无效区域的覆盖。基于网格R树的移动对象定位算法将网格定位的高

6、效性与R树搜索的高效性结合起来。基于路网拓扑的移动对象定位算法，利用了路网拓扑结构与基于网格R树的移动对象定位算法相结合。实验对比表明：三种定位算法的性能均优于基于R树的移动对象定位算法。路网环境下，大规模移动对象间的距离计算成为制约移动对象间的连续状态查询的瓶颈。因此，本文从工程角度提出基于距离查询表的移动对象间距离序列计算算法(calculatingdistancesequencebasedonDistanceQueryTable，DQT)，满足了移动对象间的连续状态查询处理的实时性要求。针对距离查询表需要内存空间较大的问题，对距离查询表进

7、行了空间优化，提出了基于空间受限距离查询表的移动对象间距离序列计算算法(calculatingdistancesequencebasedonLimitedSpaceDistanceQueryTable，LSDQT)。实验对比表明：两种算法时间性能均优于基于最短路径算法移动对象间距离序列计算算法。算法LSDQT虽然在计算速度上比DQT算法慢了一个数量级，但空间受．II．万方数据壅j垦盘堂亟±鲎焦逾塞抽垩限距离查询表所需的内存空间仅为距离查询表的1％，LSDQT算法对移动对象间的状态计算精确度接近DQT算法，趋近于100％。关键词：移动对象间状态查

8、询；连续查询；路网；移动对象定位；最短路径．．III．．万方数据盘I垦盘芏塑±鲎焦逾塞△垒§!!垒丛ResearchandImplementation