通信学报 ›› 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

[1] 刘伯涛. 移动回传的融合之路[J]. 电信科学, 2009, 25(11): 91 -93 .
[2] 鲜永菊,董灿,张祖凡,吴东伟. LTE-A载波聚合下的载波切换分析[J]. 电信科学, 2009, 25(12): 46 -50 .
[3] 桑俊俊,石胜飞,李建中,熊蜀光. 无线传感器网络分布式单向链路检测算法[J]. 通信学报, 2008, 29(11): 22 -172 .
[4] 曾 益,胡 波,冯 辉. 用于传感器网络的高效分时洪泛时钟同步协议[J]. 通信学报, 2007, 28(5): 2 -14 .
[5] 王俊波,陈 明. 单业务TDD-CDMA系统上行用户容量分析[J]. 通信学报, 2007, 28(6): 8 -53 .
[6] 张 静,胡华平,刘 波,肖枫涛. 基于ASPQ的LDoS攻击检测方法[J]. 通信学报, 2012, 33(5): 10 -84 .
[7] 牛德华,马建峰,马卓,李辰楠,王蕾. 基于属性的安全增强云存储访问控制方案[J]. 通信学报, 2013, 34(Z1): 37 -284 .
[8] 刘 龙,宋琦军,赵太飞,元向辉. 基于运动矢量时-空特性的快速运动估计算法研究[J]. 通信学报, 2013, 34(1): 14 -127 .
[9] 王亚石,闵丽娟,周严. OSS/BSS一体化及其与ITSM的融合[J]. 电信科学, 2014, 30(6): 17 -23 .
[10] 彭俊宇,蔡孙增,朱正航,徐景,周婷. 基于MIMO-OFDM的高频段Gbit/s通信系统设计和实现[J]. 电信科学, 2014, 30(6): 95 -101 .