道路网上连续最近邻查询的研究.pdfVIP

道路网上连续最近邻查询研究 王琰 1 河海大学计算机及信息工程学院，江苏南京210098 E-mail：wangyan0724@163.com 摘 要： 在智能交通系统（ITS ）中，最近邻查询是经常遇到的一类查询，尤其是查询对象 在路网上移动的情况。本文采用基于 RBF 神经网络的行程时间预测模型，拟根据已有的历 史数据对未来时段的行程时间进行预测，从而改变路段的权值，使它能真实地反映当前的交 通状况。并在此基础上提出了一种改进的连续最近邻查询算法。 关键词：智能交通系统，交通路网，连续最近邻查询，RBF ，神经网络 中图分类号：TP311 1. 引 言 [1] 地理信息系统（GIS ） 中，最近邻查询是经常遇到的一类查询，由于无线通讯和地理 位置的广泛使用，跟踪并记录移动对象的位置成为可能，移动对象的最近邻查询算法也成为 [2]是用来找出空间中距离指定 研究的重点和难点。最近邻（the Nearest Neighbor, NN ）查询 点最近的对象，即最近邻居，最近邻的数目可以是一个，也可以是k(k≥1)个，若k1 则称k 近邻。例如，在地理信息系统中，对一个特定的位置或目标，要求系统查找并返回五个离它 最近的对象，当目标对象和查询对象均移动时，我们则称之为移动对象的持续最近邻查询。 本文主要是对于道路网上移动对象的持续最近邻查询方法的研究，针对具体的道路网， 考虑道路网的特殊性和复杂性，给出相对快速准确的查询算法减少复杂的计算和网络负担。 2. 最近邻查询及行程时间模型预测 路网的移动对象连续最近邻查询按照移动对象的运动轨迹分为两类：移动对象运动轨 迹预知的连续最近邻查询和运动轨迹未知的连续最近邻查询。本文侧重研究运动轨迹未知的 连续最近邻查询。下面介绍轨迹未知的连续最近邻查询的传统算法： 2.1 路网连续最近邻查询的传统算法 [3] M.Kolahdouzan等在 中提出的Voronoi方法同样也可用于查询对象移动轨迹不定的查 询，因为目标对象固定，且已经过预处理，一旦知道查询对象目前在哪个区域内即可确定其 最近邻。 J.Zhang等则在[4] 中提出当查询对象q仍在初始位置周围的一定区域（有效区域）内，则 最近邻结果不变。而这个有效区域可以通过Voronoi方法来获得这种方法通过减少更新次数 来提高效率，然而道路网发生改变时，则需要对路网重新进行预处理。 Kyriakos等在[5] 中给出了道路网上连续最近邻查询的IMA算法，并对路网上的对象进行 实时追踪，并考虑了路网中边的更新处理问题。 然而道路网上随着交通状况发生变化，每条路段上的行程时间也随之改变，这时仅仅将 路段的长度作为权值是不合理的。路段的行程时间是描述城市交通网络状态的重要参数,它 能直观反映道路的拥挤情况,是进行动态路线诱导的前提和基础, 同时也是有哪些信誉好的足球投注网站最短路径的依 据。本文将行程时间作为路段的权值，则更接近于实际交通路网特性。同时，由于路网交通 状况实时发生变化，交通信息中心进行数据转换并发布信息也需要一定的时间，想要准确地 给出最近邻查询结果，这就需要对路段上未来行程时间进行预测。下面介绍路网行程时间预 - 1 - 测模型的研究现状。 2.2 路网行程时间预测模型 [6] 现有的行程时间预测模型有历史趋势方法 、非参数回归模型、时间序列、卡尔曼滤 波模型[7] 、神经网络等。神经网络模型是通过对历史数据的学习，可以找到输入