RSU deployment planning based on approximation algorithm in urban VANET

Junyu ZHU; Chuanhe HUANG; Xiying FAN; Kuangyu QIN; Bin FU

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

您当前的位置：

首页 >

文章列表页 >

RSU deployment planning based on approximation algorithm in urban VANET

Papers | 更新时间：2024-06-05

- RSU deployment planning based on approximation algorithm in urban VANET
- Journal on Communications Vol. 39, Issue 1, Pages: 78-89(2018)
- 作者机构：
  
  1. 武汉大学计算机学院，湖北武汉 430072
  2. 美国得克萨斯里奥格兰德河谷大学，得克萨斯爱丁堡 78539
- 作者简介：
- 基金信息：
  
  The National Natural Science Foundation of China(61772385);The National Natural Science Foundation of China(61373040);The National Natural Science Foundation of China(61572370);The National Science Foundation Early Career Award of USA(0845376)
- DOI：10.11959/j.issn.1000-436x.2018008
  CLC： TP393
- Online First：2018-01，
  
  Published：25 January 2018
- 稿件说明：
移动端阅览
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：

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 .

Views

1836

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Dynamic SDN controller placement based on latency in LEO satellite network

Interference-aware node access scheme in UAV-aided VANET

Distributed congestion control strategy using network utility maximization theory in VANET

Data dissemination of VANET based on lower bound of road delay

Efficient and secure message authentication scheme for VANET

Related Author

Yangyang ZHOU

Wentao ZHOU

Chuan XU

Guofeng ZHAO

Zhenzhen HAN

Shaojie WEN

Junyu ZHU

Chuanhe HUANG

Related Institution

School of Communication and Information Engineering, Chongqing University of Posts and Telecommunications

Research Center for Computer and Microelectronics Industry Development,MIIT(China Software Testing Center)

School of Computer Science, Wuhan University

College of Information Engineering,Dalian Ocean University

College of Computer Science and Engineering,Shandong University of Science and Technology

AI问答

⁰