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

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

作　　者：叶晨[1,2] 杨振宇[1,2] 喻剑[2] 龙其 

机构地区：[1]同济大学计算机科学与技术系,上海201804 [2]同济大学嵌入式系统与服务计算教育部重点实验室,上海201804

出　　处：《通信学报》2014年第12期116-123,135,共9页Journal on Communications

基　　金：国家国际科技合作专项基金资助项目(2012DFG11580)~~

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

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

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术]