车联网中时延约束的路侧单元部署方案研究
|
摘要
针对车联网城市环境下限制数量的路侧单元(RSU)的最佳部署位置难以确定的问题,将RSU对车辆的覆盖转化为对区域内划分子路段的覆盖,通过各路段上车辆的密度和平均速度计算路段上的数据传输时延,设计基于Dijkstra的0-1覆盖矩阵求解算法,将时延约束的RSU部署问题(DBRD)转化为集合覆盖问题。提出改进遗传算法的RSU部署方案(IGARD),在限定RSU部署数的前提下从候选位置集中选出最佳部署位置以最大化时延内覆盖路段的数量。与传统的遗传算法相比,IGARD方案基于贪心算法的思想产生初始种群,新解产生时根据设计的交叉算子和变异算子执行交叉和变异操作,且在执行过程中对不满足约束条件的潜在解进行修复,这样不仅可以将带约束条件的研究问题转化为无约束条件问题,避免了确定罚函数的困难,而且平衡了算法的集中搜索和多样性搜索能力。仿真结果表明:在相同的时延约束下,利用IGARD方案部署RSU可以将路段覆盖率提高5%以上。IGARD方案能够在时延约束下确定RSU的最佳部署位置,提高网络的性能,并为相同应用场景下的RSU部署提供一定的参考。
A Dijkstra based 0-1 covering matrix computing algorithm is designed through the vehicles density and average speed on the roads to solve the problem that the deployment location of number-limited RSU(road side unit) in urban VANET is difficult to determine. The algorithm converts the coverage of vehicles into coverage of divided sub-roads in the deployment area and the delay-bounded RSU deployment problem(DBRD) is converted into a set-covering problem. Then an RSU deployment scheme based on an improved genetic algorithm(IGARD) is proposed. The best deployment location is selected from candidates under the premise of limiting the number of RSUs to maximize the number of covering roads in the bounded delay. A comparison with the traditional genetic algorithm shows that IGARD scheme utilizes the idea of greedy algorithm to generate initial population, and uses the designed crossover operator as well as the mutation operator to execute the crossover operation and the mutation operation. Moreover, the potential solution is also repaired in the execution process. This not only turns the constrained optimization problem into an unconstrained problem and avoids the difficulty of selecting penalty function, but also balances the algorithm's ability of focused search and diversified search. Experimental results show that using IGARD scheme for RSU deployment gains an over 5% increase in the road coverage ratio under the same bounded delay. Therefore, IGARD scheme can get the best location among candidates, promote network performance, and provide reference for RSU deployment under the same scene.
A Dijkstra based 0-1 covering matrix computing algorithm is designed through the vehicles density and average speed on the roads to solve the problem that the deployment location of number-limited RSU(road side unit) in urban VANET is difficult to determine. The algorithm converts the coverage of vehicles into coverage of divided sub-roads in the deployment area and the delay-bounded RSU deployment problem(DBRD) is converted into a set-covering problem. Then an RSU deployment scheme based on an improved genetic algorithm(IGARD) is proposed. The best deployment location is selected from candidates under the premise of limiting the number of RSUs to maximize the number of covering roads in the bounded delay. A comparison with the traditional genetic algorithm shows that IGARD scheme utilizes the idea of greedy algorithm to generate initial population, and uses the designed crossover operator as well as the mutation operator to execute the crossover operation and the mutation operation. Moreover, the potential solution is also repaired in the execution process. This not only turns the constrained optimization problem into an unconstrained problem and avoids the difficulty of selecting penalty function, but also balances the algorithm's ability of focused search and diversified search. Experimental results show that using IGARD scheme for RSU deployment gains an over 5% increase in the road coverage ratio under the same bounded delay. Therefore, IGARD scheme can get the best location among candidates, promote network performance, and provide reference for RSU deployment under the same scene.
引文
[1]刘冰艺,吴黎兵,贾东耀,等.基于移动云服务的车联网数据上传策略[J].计算机研究与发展,2016,53(4):811-823.LIU Bingyi,WU Libing,JIA Dongyao,el al.Data uplink strategy in mobile cloud service based vehicular ad hoc network[J].Computer Technology and Development,2016,53(4):811-823.
[2]陈丽,李治军,姜守旭,等.车载Ad Hoc网络中基于移动网关的数据传输[J].计算机学报,2012,35(3):454-463.CHEN Li,LI Zhijun,JIANG Shouxu,et al.MGF:mobile gateway based forwarding for infrastructure-tovehicle data delivery in vehicular ad hoc networks[J].Chinese Journal of Computers,2012,35(3):454-463.
[3]朱金奇,马春梅,刘明,等.车载自组织网络中基于停车骨干网络的数据传输[J].软件学报,2016,27(2):432-450.ZHU Jinqi,MA Chunmei,LIU Ming,el al.Data delivery for vehicular Ad Hoc networks based on parking backbone[J].Journal of Software,2016,27(2):432-450.
[4]DIETZEL S,PETIT J,KARGL F,et al.In-network aggregation for vehicular Ad Hoc networks[J].IEEECommunications Surveys&Tutorials,2014,16(4):1909-1932.
[5]姜海涛,张宏,李千目.车载时延容忍网络路由协议研究[J].通信学报,2013,34(3):76-84.JIANG Haitao,ZHANG Hong,LI Qianmu.Research on routing protocol of vehicular delay-tolerant networks[J].Journal on Communications,2013,34(3):76-84.
[6]PATRA M,MISHRA S,MURTHY C S R.An analytic hierarchy process based approach for optimal road side unit placement in vehicular ad hoc networks[C]∥Proceedings of the 2014 79th IEEE Vehicular Technology Conference.Piscataway,NJ,USA:IEEE,2014:1-5.
[7]ASLAM B,AMJAD F,ZOU C C.Optimal roadside units placement in urban areas for vehicular networks[C]∥Proceedings of the 2012IEEE Symposium on Computers and Communications.Piscataway,NJ,USA:IEEE,2012:423-429.
[8]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.
[9]NIKOOKARAN N,KARAKOSTAS G,TODD T.Combining capital and operating expenditure costs in vehicular roadside unit placement[J].IEEE Transactions on Vehicular Technology,2017,66(8):7317-7331.
[10]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.
[11]LI Peng,HUANG Chuanhe,LIU Qin.BCDP:budget constrained and delay-bounded placement for hybrid roadside units in vehicular ad hoc networks[J].Sensors,2014,14(12):22564-22594.
[12]朱钧宇,黄传河,范茜莹,等.城市环境车联网中基于近似算法的RSU部署方案[J].通信学报,2018,39(1):78-89.ZHU Junyu,HUANG Chuanhe,FAN Xiying,et al.RSU deployment planning based on approximation algorithm in urban VANET[J].Journal on Communications,2018,39(1):78-89.
[13]CHI J,JO Y,PARK H,et al.Intersection-priority based optimal RSU allocation for VANET[C]∥Proceedings of the 5th International Conference on Ubiquitous&Future Networks.Piscataway,NJ,USA:IEEE,2013:350-355.
[14]刘辉,李晖.采用群组密钥管理的分布式车联网信息认证方案[J].西安交通大学学报,2013,47(2):58-62.LIU Hui,LI Hui.A distributed authentication protocol for VANET[J].Journal of Xi’an Jiaotong University,2013,47(2):58-62.
[15]DING Yong,XIAO Li.SADV:static-node-assisted adaptive data dissemination in vehicular networks[J].IEEE Transactions on Vehicular Technology,2010,59(5):2445-2455.
[16]CAPRARA A,TOTH P,FISCHETTI M.Algorithms for the set covering problem[J].Annals of Operations Research,2000,98(1/2/3/4):353-371.
[17]OWAIS M,OSMAN M K,MOUSSA G.Multiobjective transit route network design as set covering problem[J].IEEE Transactions on Intelligent Transportation Systems,2016,17(3):670-679.
[2]陈丽,李治军,姜守旭,等.车载Ad Hoc网络中基于移动网关的数据传输[J].计算机学报,2012,35(3):454-463.CHEN Li,LI Zhijun,JIANG Shouxu,et al.MGF:mobile gateway based forwarding for infrastructure-tovehicle data delivery in vehicular ad hoc networks[J].Chinese Journal of Computers,2012,35(3):454-463.
[3]朱金奇,马春梅,刘明,等.车载自组织网络中基于停车骨干网络的数据传输[J].软件学报,2016,27(2):432-450.ZHU Jinqi,MA Chunmei,LIU Ming,el al.Data delivery for vehicular Ad Hoc networks based on parking backbone[J].Journal of Software,2016,27(2):432-450.
[4]DIETZEL S,PETIT J,KARGL F,et al.In-network aggregation for vehicular Ad Hoc networks[J].IEEECommunications Surveys&Tutorials,2014,16(4):1909-1932.
[5]姜海涛,张宏,李千目.车载时延容忍网络路由协议研究[J].通信学报,2013,34(3):76-84.JIANG Haitao,ZHANG Hong,LI Qianmu.Research on routing protocol of vehicular delay-tolerant networks[J].Journal on Communications,2013,34(3):76-84.
[6]PATRA M,MISHRA S,MURTHY C S R.An analytic hierarchy process based approach for optimal road side unit placement in vehicular ad hoc networks[C]∥Proceedings of the 2014 79th IEEE Vehicular Technology Conference.Piscataway,NJ,USA:IEEE,2014:1-5.
[7]ASLAM B,AMJAD F,ZOU C C.Optimal roadside units placement in urban areas for vehicular networks[C]∥Proceedings of the 2012IEEE Symposium on Computers and Communications.Piscataway,NJ,USA:IEEE,2012:423-429.
[8]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.
[9]NIKOOKARAN N,KARAKOSTAS G,TODD T.Combining capital and operating expenditure costs in vehicular roadside unit placement[J].IEEE Transactions on Vehicular Technology,2017,66(8):7317-7331.
[10]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.
[11]LI Peng,HUANG Chuanhe,LIU Qin.BCDP:budget constrained and delay-bounded placement for hybrid roadside units in vehicular ad hoc networks[J].Sensors,2014,14(12):22564-22594.
[12]朱钧宇,黄传河,范茜莹,等.城市环境车联网中基于近似算法的RSU部署方案[J].通信学报,2018,39(1):78-89.ZHU Junyu,HUANG Chuanhe,FAN Xiying,et al.RSU deployment planning based on approximation algorithm in urban VANET[J].Journal on Communications,2018,39(1):78-89.
[13]CHI J,JO Y,PARK H,et al.Intersection-priority based optimal RSU allocation for VANET[C]∥Proceedings of the 5th International Conference on Ubiquitous&Future Networks.Piscataway,NJ,USA:IEEE,2013:350-355.
[14]刘辉,李晖.采用群组密钥管理的分布式车联网信息认证方案[J].西安交通大学学报,2013,47(2):58-62.LIU Hui,LI Hui.A distributed authentication protocol for VANET[J].Journal of Xi’an Jiaotong University,2013,47(2):58-62.
[15]DING Yong,XIAO Li.SADV:static-node-assisted adaptive data dissemination in vehicular networks[J].IEEE Transactions on Vehicular Technology,2010,59(5):2445-2455.
[16]CAPRARA A,TOTH P,FISCHETTI M.Algorithms for the set covering problem[J].Annals of Operations Research,2000,98(1/2/3/4):353-371.
[17]OWAIS M,OSMAN M K,MOUSSA G.Multiobjective transit route network design as set covering problem[J].IEEE Transactions on Intelligent Transportation Systems,2016,17(3):670-679.