通信学报 ›› 2014, Vol. 35 ›› Issue (12): 116-123.doi: 10.3969/j.issn.1000-436x.2014.12.014

• 学术论文 • 上一篇    下一篇

基于动态路网的分布式邻近目标查询算法

叶晨1,2,杨振宇1,2,喻剑2,龙其1,2   

  1. 1 同济大学 计算机科学与技术系,上海 201804
    2 同济大学 嵌入式系统与服务计算教育部重点实验室,上海201804
  • 出版日期:2014-12-25 发布日期:2017-06-17
  • 基金资助:
    国家国际科技合作专项基金资助项目

Distributed nearneighbor search algorithm based on real-time traffic information in dynamic road network

Chen YE1,2,Zhen-yu YANG1,2,Jian YU2,Qi LONG1,2   

  1. 1 Computer Science and Technology Department,Tongji University,Shanghai 201804,China
    2 Key Laboratory of Embedded System and Services Computing,Ministry of Education,Tongji University,Shanghai 201804,China
  • Online:2014-12-25 Published:2017-06-17
  • Supported by:
    The International S&T Cooperation Program of China

摘要:

提出了一种基于实时路况信息的分布式邻近目标查询算法,采用基于Voronoi图的划分将地理信息存储在离它最近路口的智能摄像头上,实时路况信息由智能摄像头采集,通过对路口的畅通程度进行建模,估算出路口间通行所需要的时间。当有车辆查询邻近目标时,网络中的智能摄像头根据所在路口的畅通程度和到邻近路口的距离,在分布式查询过程中加入延时转发机制,广播目标路径询问的数据分组,使数据分组的发送能模拟当前的路况进行传输,从而获得到达邻近目标的路径。基于真实数据的实验结果表明算法是有效的,处理大量并发查询时的性能优于现有方法。

关键词: 动态路网, 最邻近查询, k邻近查询, 分布式查询, 延迟路由

Abstract:

A novel distributed near neighbor search algorithm that makes use of real-time traffic information is presented.The geographic information are stored in the nearest smart camera using Voronoi partition,and cameras are located in the intersection.The intersection unimpeded degree is modeled and the time which vehicle travel between adjacent intersec-tions is estimated.When a vehicle search for some near neighbors,smart cameras set a delay to broadcast the near neighbor search packet based on the traffic parameters collected by smart camera networks.In this way,the near neighbor search packet can be transmitted according to current road conditions.Thus get the path to near targets quickly and effec-tively.Extensive experiments are londucted on real data sets,and the results show that proposed algorithm is efficient and scalable to large number of concurrent query,significantly outperforming state-of-the-art methods.

Key words: dynamic road network, nearest neighbor search, k-nearest neighbor search, distributed search, delay routing