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

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

通信学报 ›› 2018, Vol. 39 ›› Issue (1): 78-89.doi: 10.11959/j.issn.1000-436x.2018008

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

朱钧宇¹,黄传河¹(),范茜莹¹,覃匡宇¹,付斌²

¹ 武汉大学计算机学院，湖北武汉 430072
² 美国得克萨斯里奥格兰德河谷大学，得克萨斯爱丁堡 78539

修回日期:2017-12-25 出版日期:2018-01-01 发布日期:2018-02-07
作者简介:朱钧宇（1987-），男，河南周口人，武汉大学博士生，主要研究方向为物联网、无线网络、车载自组织网络等。|黄传河（1963-），男，湖北随州人，武汉大学教授、博士生导师，主要研究方向为计算机网络（移动互联网、移动ad hoc网络、无线传感器网络、未来互联网）、物联网、网络安全、高性能计算等。|范茜莹（1990-），女，河南驻马店人，武汉大学博士生，主要研究方向为无线网络、算法设计与分析、车载自组织网络等。|覃匡宇（1974-），男，壮族，广西马山人，武汉大学博士生，主要研究方向为软件定义网络（SDN）、网络管理。|付斌（1964-），男，美国得克萨斯州人，美国得克萨斯里奥格兰德河谷大学终身教授，主要研究方向为算法设计与分析、生物信息、计算复杂性理论、无线网络等。
基金资助:
国家自然科学基金资助项目(61772385);国家自然科学基金资助项目(61373040);国家自然科学基金资助项目(61572370);美国国家科学基金会基金资助项目(0845376)

RSU deployment planning based on approximation algorithm in urban VANET

Junyu ZHU¹,Chuanhe HUANG¹(),Xiying FAN¹,Kuangyu QIN¹,Bin FU²

¹ Computer School,Wuhan University,Wuhan 430072,China
² The University of Texas Rio Grande Valley,Edinburg 78539,USA

Revised:2017-12-25 Online:2018-01-01 Published:2018-02-07
Supported by:
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)

摘要/Abstract

摘要：

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

关键词: 车联网, RSU部署, 区域覆盖, 近似算法

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.

Key words: VANET, RSU deployment, covering problem, approximation algorithm

中图分类号:

TP393

朱钧宇,黄传河,范茜莹,覃匡宇,付斌. 城市环境车联网中基于近似算法的RSU部署方案[J]. 通信学报, 2018, 39(1): 78-89.

Junyu ZHU,Chuanhe HUANG,Xiying FAN,Kuangyu QIN,Bin FU. RSU deployment planning based on approximation algorithm in urban VANET[J]. Journal on Communications, 2018, 39(1): 78-89.

图/表 10

图1

表1

图2

图3

图4

图5

图6

图7

图8

图9

参考文献 34

[1]	常促宇, 向勇, 史美林 . 车载自组网的现状与发展[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.
[2]	李丽君, 刘鸿飞, 杨祖元 ,等. 车用自组网信息广播[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.
[3]	ENGLUND C , CHEN L , VINEL A ,et al. Future applications of VANETs[M]// Vehicular Ad Hoc Networks. Switzerland:Springer, 2015: 524-544.
[4]	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.
[5]	陈立家, 江昊, 吴静 ,等. 车用自组织网络传输控制研究[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.
[6]	姜海涛, 张宏, 李千目 . 车载时延容忍网络路由协议研究[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.
[7]	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.
[8]	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.
[9]	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.
[10]	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.
[11]	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.
[12]	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.
[13]	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.
[14]	LIN Y Y , RUBIN I . Throughput maximization under guaranteed dissemination coverage for VANET systems[C]// Information Theory and Applications Workshop. 2015: 313-318.
[15]	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.
[16]	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.
[17]	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.
[18]	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.
[19]	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.
[20]	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.
[21]	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.
[22]	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.
[23]	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.
[24]	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.
[25]	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.
[26]	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.
[27]	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.
[28]	奎晓燕, 杜华坤, 肖雪峰 ,等. 基于真实车载移动数据的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.
[29]	刘明, 曹建农, 郑源 ,等. 无线传感器网络多重覆盖问题分析[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.
[30]	黄晓, 程宏兵, 杨庚 . 无线传感器网络覆盖连通性研究[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.
[31]	谢永, 吴黎兵, 何炎祥 ,等. 无间隙的车联网协助下载方法[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.
[32]	KARP R M , . Reducibility among combinatorial problems[M]// New York:Springer, 1972: 85-103.
[33]	HAKLAY M , WEBER P . OpenStreetMap:user-generated street maps[J]. IEEE Pervasive Computing, 2008,7(4): 12-18.
[34]	KRAJZEWICZ D , . Traffic simulation with SUMO-simulation of urban mobility[M]// New York:Springer, 2010: 269-293.

变量	含义
r	RSU通信范围
i、j、m、s、t	整数参数
R	待选RSU部署点集合
S	目标覆盖街道集合
S_i	所需覆盖的街道
c	整数参数，用于c街道模型
I_i,j	RSU的R_i覆盖的街道区间
C_i	S_i的最优覆盖集合
f(·)	十字路口的数量
g(·,·)	2 rl×2rl区域内可供选择的RSU个数
n	目标区域内可供选择的RSU个数
C^*	最优覆盖方案
B	目标覆盖区域
SA	shifting策略
A	用于求解宽度为2rl的区域部署方案的局部算法
l	近似精度控制参数
L_i	由多个宽为2rl区域组成的区域
P_i	若干L_i组成的区域
I_i	街道区间

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

RSU deployment planning based on approximation algorithm in urban VANET

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 34

相关文章 15

Metrics

推荐阅读 0

[1]	张海波, 兰凯, 陈舟, 王汝言, 邹灿, 王明月. 车联网中基于环的匿名高效批量认证与组密钥协商协议[J]. 通信学报, 2023, 44(6): 103-116.
[2]	张海波, 曹钰坤, 刘开健, 王汝言. 车联网中基于区块链的分布式信任管理方案[J]. 通信学报, 2023, 44(5): 148-157.
[3]	刘雪娇, 钟强, 夏莹杰. 基于双层分片区块链的车联网跨信任域高效认证方案[J]. 通信学报, 2023, 44(5): 213-223.
[4]	刘雪娇, 曹天聪, 夏莹杰. 区块链架构下高效的车联网跨域数据安全共享研究[J]. 通信学报, 2023, 44(3): 186-197.
[5]	张雷, 王玉, 田建杰, 张琳, 章天骄. 基于IRS辅助的MIMO车联网系统联合波束成形设计[J]. 通信学报, 2023, 44(2): 59-69.
[6]	曾嵘, 杭潇. 车联网环境下可重构智能反射面辅助无线信道估计算法[J]. 通信学报, 2022, 43(8): 142-150.
[7]	程翔, 张浩天, 杨宗辉, 黄子蔚, 李思江, 余安澜. 车联网通信感知一体化研究：现状与发展趋势[J]. 通信学报, 2022, 43(8): 188-202.
[8]	秦鹏, 和昊婷, 赵雄文, 伏阳, 张钰, 王淼, 王硕, 武雪. 基于停放车辆路边单元环境感知的车联网资源高效分配[J]. 通信学报, 2022, 43(7): 113-125.
[9]	孙雁飞, 尹嘉峥, 亓晋, 胡筱旋, 陈梦婷, 董振江. 基于动态图嵌入的车联网拓扑控制[J]. 通信学报, 2022, 43(6): 133-142.
[10]	朱思峰, 蔡江昊, 柴争义, 孙恩林. 车联网云边协同计算场景下的多目标优化卸载决策[J]. 通信学报, 2022, 43(6): 223-234.
[11]	亓伟敬, 宋清洋, 郭磊. 面向软件定义多模态车联网的双时间尺度RAN切片资源分配[J]. 通信学报, 2022, 43(4): 60-70.
[12]	莫梓嘉, 高志鹏, 杨杨, 林怡静, 孙山, 赵晨. 面向车联网数据隐私保护的高效分布式模型共享策略[J]. 通信学报, 2022, 43(4): 83-94.
[13]	丛玉良, 孙闻晞, 薛科, 钱志鸿, 陈绵书. 基于改进的混合遗传算法的车联网任务卸载策略研究[J]. 通信学报, 2022, 43(10): 77-85.
[14]	陈九九, 冯春燕, 郭彩丽, 杨洋, 孙启政, 朱美逸. 车联网中视频语义驱动的资源分配算法[J]. 通信学报, 2021, 42(7): 1-11.
[15]	崔杰, 陈学峰, 张静, 魏璐, 仲红. 基于公交车缓存的车联网位置隐私保护方案[J]. 通信学报, 2021, 42(7): 150-161.