城市环境车联网中基于近似算法的RSU部署方案

朱钧宇; 黄传河; 范茜莹; 覃匡宇; 付斌

doi:10.11959/j.issn.1000-436x.2018008

您当前的位置：

首页 >

文章列表页 >

城市环境车联网中基于近似算法的RSU部署方案

学术论文 | 更新时间：2024-06-05

- 城市环境车联网中基于近似算法的RSU部署方案
- RSU deployment planning based on approximation algorithm in urban VANET
- 通信学报 2018年39卷第1期页码：78-89
- 作者机构：
  
  1. 武汉大学计算机学院，湖北武汉 430072
  2. 美国得克萨斯里奥格兰德河谷大学，得克萨斯爱丁堡 78539
- 作者简介：
  
  [ "朱钧宇（1987-），男，河南周口人，武汉大学博士生，主要研究方向为物联网、无线网络、车载自组织网络等。" ]
  [ "黄传河（1963-），男，湖北随州人，武汉大学教授、博士生导师，主要研究方向为计算机网络（移动互联网、移动ad hoc网络、无线传感器网络、未来互联网）、物联网、网络安全、高性能计算等。" ]
  [ "范茜莹（1990-），女，河南驻马店人，武汉大学博士生，主要研究方向为无线网络、算法设计与分析、车载自组织网络等。" ]
  [ "覃匡宇（1974-），男，壮族，广西马山人，武汉大学博士生，主要研究方向为软件定义网络（SDN）、网络管理。" ]
  [ "付斌（1964-），男，美国得克萨斯州人，美国得克萨斯里奥格兰德河谷大学终身教授，主要研究方向为算法设计与分析、生物信息、计算复杂性理论、无线网络等。" ]
- 基金信息：
  
  国家自然科学基金资助项目(61772385);国家自然科学基金资助项目(61373040);国家自然科学基金资助项目(61572370);美国国家科学基金会基金资助项目(0845376)
- DOI：10.11959/j.issn.1000-436x.2018008
  中图分类号： TP393
- 网络出版日期：2018-01，
  
  纸质出版日期：2018-01-25
- 稿件说明：
移动端阅览
朱钧宇, 黄传河, 范茜莹, 等. 城市环境车联网中基于近似算法的RSU部署方案[J]. 通信学报, 2018,39(1):78-89.

Junyu ZHU, Chuanhe HUANG, Xiying FAN, et al. RSU deployment planning based on approximation algorithm in urban VANET[J]. Journal on communications, 2018, 39(1): 78-89.
朱钧宇, 黄传河, 范茜莹, 等. 城市环境车联网中基于近似算法的RSU部署方案[J]. 通信学报, 2018,39(1):78-89. DOI： 10.11959/j.issn.1000-436x.2018008.

Junyu ZHU, Chuanhe HUANG, Xiying FAN, et al. RSU deployment planning based on approximation algorithm in urban VANET[J]. Journal on communications, 2018, 39(1): 78-89. DOI： 10.11959/j.issn.1000-436x.2018008.

摘要

为了使用尽可能少的 RSU 实现对目标区域的有效覆盖，设计 c 街道模型，将对区域的覆盖转化为对区域内街道的覆盖，然后，在该模型下提出基于贪心策略的多项式（GBP

greedy-based polynomial）时间近似算法，得到RSU的部署方案以解决覆盖问题。针对城市中一些地形复杂的区域，设计Cue模型（complex urban environment model），将目标区域划分为子区域，然后提出基于 shifting 策略的多项式时间近似算法，并对算法的近似比率和时间复杂度进行了理论分析与证明。仿真结果表明，算法 GBP 能够有效地解决城市环境车联网中的区域覆盖问题。

Abstract

To minimize the number of RSU deployed to cover a specific area

a c street model transforming the area covering problem to streets covering problem was designed

and a greedy-based polynomial (GBP) time approximation algorithm was developed to obtain the optimal RSU deployment for area coverage.For complex urban environments

a Cue model (complex urban environments model) was proposed.In this model

the target area was divided into different partitions.Then

based on shifting strategy

a polynomial time approximation scheme was designed.Theoretical analysis that include the approximation ratio and time complexity of the proposed algorithm were also presented.Simulation results show that GBP can efficiently solve the coverage problem in urban VANET.

关键词

Keywords

references

常促宇 , 向勇 , 史美林 . 车载自组网的现状与发展 [J ] . 通信学报 , 2007 , 28 ( 11 ): 116 - 126 .

CHANG C Y , XIANG Y , SHI M L . Development and status of vehicular ad hoc networks [J ] . Journal on Communications , 2007 , 28 ( 11 ): 116 - 126 .

李丽君 , 刘鸿飞 , 杨祖元 , 等 . 车用自组网信息广播 [J ] . 软件学报 , 2010 , 21 ( 7 ): 1620 - 1634 .

LI L J , LIU H F , YANG Z Y , et al . Broadcasting methods in vehicular ad hoc networks [J ] . Journal of Software , 2010 , 21 ( 7 ): 1620 - 1634 .

ENGLUND C , CHEN L , VINEL A , et al . Future applications of VANETs [M ] // Vehicular Ad Hoc Networks . Switzerland:Springer , 2015 : 524 - 544 .

XING M , HE J , CAI L . Utility maximization for multimedia data dissemination in large-scale VANETs [J ] . IEEE Transactions on Mobile Computing , 2017 , 16 ( 4 ): 1188 - 1198 .

陈立家 , 江昊 , 吴静 , 等 . 车用自组织网络传输控制研究 [J ] . 软件学报 , 2007 , 18 ( 6 ): 1477 - 1490 .

CHEN L J , JIANG H , WU J , et al . Research on transmission control on vehicle ad-hoc network [J ] . Journal of Software , 2007 , 18 ( 6 ): 1477 - 1490 .

姜海涛 , 张宏 , 李千目 . 车载时延容忍网络路由协议研究 [J ] . 通信学报 , 2013 , 34 ( 3 ): 76 - 84 .

JIANG H T , ZHANG H , LI Q M . Research on routing protocol of vehicular delay-tolerant networks [J ] . Journal on Communications , 2013 , 34 ( 3 ): 76 - 84 .

HOCHBAUM D S , MAASS W . Approximation schemes for covering and packing problems in image processing and VLSI [J ] . Journal of ACM , 1985 , 32 ( 1 ): 130 - 136 .

LUO Z , GAN X , WANG X , et al . Optimal throughput-delay trade-off in manets with supportive infrastructure using random linear coding [J ] . IEEE Transactions on Vehicular Technology , 2016 , 65 ( 9 ): 7543 - 7558 .

LU N , ZHANG N , CHENG N , et al . Vehicles meet infrastructure:towards capacity-cost tradeoffs for vehicular access networks [J ] . IEEE Transaction on Intelligent Transportation System , 2013 , 14 ( 3 ): 1266 - 1277 .

HAJLAOUI R , GUYENNET H , MOULAHI T . A survey on heuristic-based routing methods in vehicular ad hoc network:technical challenges and future trends [J ] . IEEE Sensors Journal , 2016 , 16 ( 17 ): 6782 - 6792 .

OMAR H , ZHUANG W , LI L . Gateway placement and packet routing for multihop in-vehicle Internet access [J ] . IEEE Transactions on Emerging Topics in Computing , 2015 , 3 ( 3 ): 335 - 351 .

TRULLOLS O , FIORE M , CASETTI C , et al . Planning roadside infrastructure for information dissemination in intelligent transportation systems [J ] . Computer Communications , 2010 , 33 ( 4 ): 432 - 442 .

CAVALCANTE E , AQUINO A , PAPPA G , et al . Roadside unit deployment for information dissemination in a VANET:an evolutionary approach [C ] // The 14th Annual Conference Companion on Genetic and Evolutionary Computation . 2012 : 27 - 34 .

LIN Y Y , RUBIN I . Throughput maximization under guaranteed dissemination coverage for VANET systems [C ] // Information Theory and Applications Workshop . 2015 : 313 - 318 .

RIZK R , DAHER R , MAKKAWI A . RSUs placement using overlap based greedy method for urban and rural roads [C ] // International Workshop on Communication Technologies for Vehicles . 2015 : 12 - 18 .

YAN T , ZHANG W S , WANG G L , et al . Access points planning in urban area for data dissemination to drivers [J ] . IEEE Transactions on Vehicular Technology , 2014 , 63 ( 1 ): 390 - 402 .

ZHU Y M , BAO Y C , LI B . On maximizing delay-constrained coverage of urban vehicular networks [J ] . IEEE Journal on Selected Areas in Communications , 2012 , 30 ( 4 ): 804 - 817 .

CHENG H , FEI X , ALMULLA M , et al . A knapsack constrained steiner tree model for continuous coverage over urban VANETs [C ] // IEEE International Conference on Communications . 2014 : 130 - 135 .

WANG Y , ZHENG J , MITTON N . Delivery delay analysis for roadside unit deployment in vehicular ad hoc networks with intermittent connectivity [J ] . IEEE Transactions on Vehicular Technology , 2016 , 65 ( 10 ): 8591 - 8602 .

ZHANG B , JIA X , YANG K , et al . Design of analytical model and algorithm for optimal roadside AP placement in VANETs [J ] . IEEE Transactions on Vehicular Technology , 2016 , 65 ( 9 ): 7708 - 7718 .

KIM D , VELASCO Y , WANG W , et al . A new comprehensive RSU installation strategy for cost-efficient VANET deployment [J ] . IEEE Transactions on Vehicular Technology , 2017 , 66 ( 5 ): 4200 - 4211 .

LIU C , HUANG H , DU H . Optimal RSUs deployment with delay bound along highways in VANET [J ] . Journal of Combinatorial Optimization , 2017 , 33 ( 4 ): 1168 - 1182 .

JALOOLI A , SONG M , XU X . Delay efficient disconnected RSU placement algorithm for VANET safety applications [C ] // IEEE Wireless Communications and Networking Conference . 2017 : 1558 - 2612 .

MUKHERJEE J C , GUPTA A , SREENIVAS R C . Event notification in VANET with capacitated roadside units [J ] . IEEE Transactions on Intelligent Transportation Systems , 2016 , 17 ( 7 ): 1867 - 1879 .

LI Y , JIN D , HUI P . Contact-aware data replication in roadside unit aided vehicular delay tolerant networks [J ] . IEEE Transactions on Mobile Computing , 2016 , 15 ( 2 ): 306 - 321 .

LI P , ZHANG T , HUANG C , et al . RSU-assisted Geocast in vehicular ad hoc networks [J ] . IEEE Wireless Communications , 2017 , 24 ( 1 ): 53 - 59 .

SUN Y P , LIN X D , LU R X , et al . Roadside units deployment for efficient short-time certificate updating in VANETs [C ] // IEEE International Conference on Communications (ICC) . 2010 : 1 - 5 .

奎晓燕 , 杜华坤 , 肖雪峰 , 等 . 基于真实车载移动数据的RSU部署算法 [J ] . 北京邮电大学学报 , 2015 , 38 ( 1 ): 114 - 118 .

KUI X Y , DU H K , XIAO X F , et al . Realistic vehicular mobility trace driven RSU deployment scheme [J ] . Journal of Beijing University of Posts and Telecommunications , 2015 , 38 ( 1 ): 114 - 118 .

刘明 , 曹建农 , 郑源 , 等 . 无线传感器网络多重覆盖问题分析 [J ] . 软件学报 , 2007 , 18 ( 1 ): 127 - 136 .

LIU M , CAO J N , ZHENG Y , et al . Analysis for multi-coverage problem in wireless sensor networks [J ] . Journal of Software , 2007 , 18 ( 1 ): 127 - 136 .

黄晓 , 程宏兵 , 杨庚 . 无线传感器网络覆盖连通性研究 [J ] . 通信学报 , 2009 , 30 ( 2 ): 129 - 135 .

HUANG X , CHENG H B , YANG G . Research of connectivity for wireless sensor networks [J ] . Journal on Communications , 2009 , 30 ( 2 ): 129 - 135 .

谢永 , 吴黎兵 , 何炎祥 , 等 . 无间隙的车联网协助下载方法 [J ] . 通信学报 , 2016 , 37 ( 1 ): 180 - 190 .

XIE Y , WU L B , HE Y X , et al . Non-intermittent cooperative downloading approach for VANET [J ] . Journal on Communications , 2016 , 37 ( 1 ): 180 - 190 .

KARP R M , . Reducibility among combinatorial problems [M ] // New York:Springer , 1972 : 85 - 103 .

HAKLAY M , WEBER P . OpenStreetMap:user-generated street maps [J ] . IEEE Pervasive Computing , 2008 , 7 ( 4 ): 12 - 18 .

KRAJZEWICZ D , . Traffic simulation with SUMO-simulation of urban mobility [M ] // New York:Springer , 2010 : 269 - 293 .

浏览量

1644

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

基于时延的LEO卫星网络SDN控制器动态放置方法

无人机辅助车联网环境下干扰感知的节点接入机制

基于网络效用最大化理论的分布式车联网拥塞控制策略

基于路口时延下界的车联网数据分发方案

面向车联网高效安全的消息认证方案