车联网中时延约束的路侧单元部署方案研究

贾宗璞,杨焕焕,谢果君

(河南理工大学计算机科学与技术学院,454000,河南焦作)

车辆自组织网络(VANET)存在着功能不一的交通安全类应用、交通协调管理类应用和娱乐类应用,它们对智能交通系统(ITS)的实现起着重要作用。车辆感知数据的收集和分发是这些应用的核心内容,但由于车联网中车辆移动性高、拓扑变化频繁,单独地车对车(V2V)通信往往效率较低,严重影响了车辆感知数据的获取[1-3]。作为车联网中必不可少的道路基础设施单元,路侧单元(RSU)可以利用车对基础设施(V2I)通信降低智能车辆间的数据传输时延。然而,大量部署RSU不仅费用较高[4],而且会受到候选部署点集合、交通特征、道路特征等诸多因素的影响[5]。现有的关于RSU部署工作的研究主要是优化数据传输时延、RSU覆盖率和RSU部署费用等,以提高网络的性能。

关于数据传输时延的研究主要是降低RSU-RSU传输时延和车辆-RSU传输时延[6-7]。关于RSU部署费用的研究则是降低RSU的安装成本和维护成本[8-9]。就RSU覆盖率的研究而言,Trullols等研究了基础设施节点部署问题,目标是最大化区域内与基础设施连接的车辆数和连通时间,提出的贪婪算法和分区算法在大规模场景下有很好的适用性,但计算车辆覆盖时需要获取车辆的详细行驶信息[10]。Li等解决了车联网中预算和时延约束的RSU部署问题,其中有线RSU(c-RSU)和无线RSU(w-RSU)两种类型RSU的时延约束覆盖范围和部署代价完全不同,该问题的目标是在给定的预算和时延下确定RSU的最佳部署位置,最大化区域内接收c-RSU广播消息的车辆数[11]。Zhu等设计了c街道模型并提出基于贪心策略的近似算法,实现了RSU对目标区域的最优覆盖,然后针对城市中地形复杂的区域,设计了Cue模型,提出基于shifting策略的近似算法,进而有效地解决了城市场景下RSU的部署问题[12]。Chi等提出了十字路口优先级的RSU部署方案,根据车辆密度、十字路口普遍度计算路口权重值,并结合贪婪、动态规划和混合法确定RSU的部署数和部署位置,在确保最大连通性的同时降低RSU的部署成本[13]。

以上大多数的研究主要将传输时延、部署费用等作为RSU部署的优化目标,以覆盖率为目标的部署主要考虑对车辆的覆盖,部署算法需要车辆的详细移动信息,这些信息不仅涉及用户的隐私[14],而且较难获取。因此,本文将RSU对车辆的覆盖转化为对区域内划分子路段的覆盖,通过各路段上车辆的密度和平均速度求解路段上的数据传输时延,设计基于Dijkstra的0-1覆盖矩阵求解算法,将时延约束的RSU部署问题(DBRD)转化为集合覆盖问题。提出改进遗传算法的RSU部署方案(IGARD),在限定RSU部署数的前提下从候选位置集中选出最佳部署位置以最大化时延内覆盖路段数。与传统的遗传算法相比,IGARD方案基于贪心算法的思想产生初始种群,新解产生时根据设计的交叉算子和变异算子执行交叉和变异操作,且在执行过程中对不满足约束条件的潜在解进行修复。这样不仅可以将带约束条件的研究问题转化为无约束条件问题,避免了确定罚函数的困难,而且平衡了算法的集中搜索和多样性搜索能力。仿真结果进一步证实了算法的有效性。

1 系统模型

1.1 问题模型

城市道路模型图可表示为无向图G=(V,E),V是十字路口集合,V={I1,I2,…,In}且满足|V|=n,E是相邻十字路口间的路段,E={E1,E2,…,Es}。设车辆和RSU的通信半径为R,相邻十字路口间的距离D={D1,D2,…,Ds}。对于Di∈D且Di>R的路段Ei,将其按照R的间距划分为若干个子路段。图1给出了n=9时的城市道路模型图。

划分完成后形成另一无向图G1=(V1,E1),V1={V,M},E1={e(i,j),∀i,j,i∈V1,j∈V1},M是E∈G(V,E)划分时形成的顶点,M={m1,m2,…,mk}且|V1|=N,|E1|=m。对eij∈E1有e(i,j)={lij,ρij,vij},lij、ρij、vij分别为路段e(i,j)的欧氏距离、车辆密度和平均速度。

图1 城市道路模型图

1.2 通信模型

本文的场景是多个RSU和多个车辆组成的网络,网络通信场景如图2所示。图2中,虚线覆盖的区域为RSU的部署区域,RSU设施表示可供选择的RSU部署候选位置,含有通信链路的RSU设施表示在该处部署了RSU。本文的通信模型为圆盘通信模型,任意两个节点可以通信,当且仅当它们之间的欧氏距离小于或等于其通信半径R。以i和j为端点的路段e(i,j)为例,根据文献[15],其上的数据传输时延t(i,j)可以表示为

图2 网络通信场景图

(1)

式中:thop为数据的一跳传输时延,thop=psize/s,psize为数据包大小,s为数据传输带宽。式(1)表明,道路e(i,j)上有(1-e-Rρij)的车辆车间距离小于等于R,它们使用转发方式传输数据,其余的e-Rρij的车辆车间距离大于R,它们使用携带方式传输数据。另外,当lij>R时,需将e(i,j)划分为若干子路段,此时子路段上的数据传输时延仍旧由式(1)计算。

1.3 DBRD问题

RSU部署时选择十字路口为候选位置[10]。本文目标是在n个候选位置中部署r个RSU,使时延τ内将数据传输至RSU的子路段总数最多。设e(i,j)上车辆将数据传输至RSU的最小时延为tj(1≤j≤m)。对任一eij∈E1,定义0-1变量xi、yj,当tj≤τ时,yj=1,否则yj=0;在Ii处部署RSU时,xi=1,否则xi=0。那么,DBRD问题可形式化为

(2)

定理1DBRD问题是NP-hard问题。

证明首先引入集合覆盖问题(SCP)[16-17]。SCP问题表述如下:给定n个元素集合E={e1,e2,…,en},E的子集集合S={s1,s2,…,sm},求E的一个覆盖C,使C在E的所有覆盖中所含元素个数最少且C中元素并集为E。因为SCP问题是NP-hard问题,将DBRD问题转化为SCP问题后,即可证明DBRD问题是NP-hard问题。设在Ii处部署RSU时各子路段在τ内将数据传输至RSU的集合为Si,则问题转化为τ限制的集合覆盖问题(τ-LSCP)

(3)

问题的目标为最大化RSU覆盖的子路段数量,即最大化Si的并集,约束条件为RSU的部署数等于r。因此,DBRD问题是NP-hard问题。

1.4 数据传输延迟计算方法

将DBRD问题转化为τ-LSCP问题后,获取Si(1≤i≤n)是求解τ-LSCP问题的前提。设计0-1覆盖矩阵Tmn,当路段e(i,j)上的车辆将数据传输至i处RSU的最小时延tji≤τ时,Tji=1,否则Tji=0。那么,Si可表示为

(4)

因此,问题转化为求路段e(i,j)上车辆将数据传输至i处RSU时最小时延tji的值。设路段e(i,j)距离i处RSU的距离为dji,则tji为

(5)

式中:Pik∈P为路段e(i,j)上车辆将数据传输至i处RSU时的所有路径;t(j,k)为数据在e(j,k)的传输时延。经1.2节中式(1)求解t(j,k)后,为无向图G1=(V1,E1)的各条边附上相应的权值t(j,k),G1即为无向带权图。此时无向带权图表示的道路模型如图3所示,n=9。

图3 无向带权图表示的道路模型

对tji(1≤j≤m,1≤i≤n),使用Dijkstra算法求出e(i,j)两侧端点到源点Ii的最短路径(最小传输延迟)后记录在disk[]数组中,取两者中的较小值加上t(i,j)即可,计算方法如下式

tji=min{disk[i],disk[j]}+t(i,j)

(6)

0-1覆盖矩阵Tmn的求解算法如下。

算法10-1覆盖矩阵Tmn求解算法。

输入RSU候选位置集合V={I1,I2,…,In},无向带权图G1=(V1,E1),传输延迟τ

输出矩阵Tmn

1double dist [N];∥记录图中各顶点到源点Ii的最小传输延迟的数组

2for inti=1 ton∥遍历RSU候选位置集合V={I1,I2,…,In}

3 Dijkstra(G1,dist,Ii);∥Dijkstra算法求出图中各顶点到源点Ii的最小传输延迟

4 for intj=1 tom∥遍历图中所有的边eij∈E1

5tji=min{disk[i],disk[j]}+t(i,j);∥计算所有路段到Ii处RSU的最小传输延迟

6 if(tji≤τ)Tji=1;

7 else if(tji>τ)Tji=0;

8 end for

9end for

定理20-1覆盖矩阵Tmn求解算法的时间复杂度为O[n(N2+m)]。

证明RSU部署候选位置集合|V|=n,为获取每个位置Ii对应的Si,需要进行n次运算。每次运算使用Dijkstra算法计算图中顶点到源点Ii的最小传输延迟,时间复杂度为O(N2)。获得dist [N]数组后,需要计算eij∈E1上车辆将数据传输至i处RSU时的最小时延tji,时间复杂度为O(m),即每次运算时间复杂度为O(N2+m),故0-1覆盖矩阵求解算法时间复杂度为O[n(N2+m)]。

2 改进遗传算法的RSU部署方案

在1.4节中,通过算法1求得0-1覆盖矩阵后,τ-LSCP问题可表述为:给定0-1矩阵Tmn,Tji=1表示第j行被第i列覆盖,Tji=0则表示第j行未被第i列覆盖。τ-LSCP问题需要寻找包含r个列的集合D,使D中元素覆盖的总行数最多。引入n维0-1向量X={x1,x2,…,xn},若第i列选入集合D,则xi=1,否则xi=0,因此X是τ-LSCP问题的解。图4给出了τ-LSCP问题实例图。

图4 τ -LSCP问题实例图

基于此,提出了改进遗传算法的RSU部署方案IGARD,流程图如图5所示,其基本步骤如下。

步骤1使用贪心算法产生初始种群P={x1,x2,…,xM},设计适应度函数f(x),计算个体的适应度,记P中最优解为x*,B=f(x*)。

步骤2通过以下方式产生新解:①从P中任选2个解xi、xj,交叉产生解xs,变异得新解xz;②从P中任选一个解xi变异得新解xz。

步骤3将x*与xs比较,若找到比x*适应度更优的解,则更新解x*和B=f(x*)。

步骤4重复步骤2～步骤3至最大迭代次数结束。

2.1 编码

改进的遗传算法中个体使用n维0-1向量进行编码,当个体某一维位置取值为1时,表示该维度对应的列加入选中列集合。例如{0,1,1,0}表示将第2列和第3列加入选中列集合。

2.2 产生初始种群

初始种群的产生通过贪心算法完成,这样可以避免过多无效解的出现。假设τ-LSCP问题的解向量为xj={xj(1),xj(2),…,xj(n)},选中列集合为D,未选中列集合为M,选中列已覆盖行集合为U,则初始种群产生的步骤如下。

步骤1初始化D=φ,M={1,2,…,n},xj={xj(i)}={0,…,0},1≤i≤n,U=E1。

步骤2记Si表示第i列加入D后新覆盖的行,可用性价比Q(i)=|Si∩U|表示。

步骤3构造候选列集合RCL={i∈M,ξQmax≤Q(i)≤Qmax}。ξ为(0,1)内的数,设置目的是平衡初始种群产生的随机性和贪婪性。

步骤4从RCL中任选一列i加入D,令M=M-{i},xj(i)=1,U=U-Si。

步骤5若|D|=r,结束并输出xj,否则转至步骤2。

步骤6重复运行步骤1～步骤5,直至初始种群的数量达到M,并输出P={x1,x2,…,xM}。

图5 IGARD方案流程图

2.3 适应度函数

本文适应度函数如下

(7)

式中:Si为第i列覆盖的行,f(x)为适应度,表示Si并集元素数。因种群初始化时已剔除无效个体,故求解问题已转化为无约束问题,适应度函数即为本文目标函数。

2.4 选择、交叉和变异算子

本文使用轮盘赌选择法选择个体,基本思想是根据个体适应度大小进行选择操作。首先依据种群中个体的适应度计算其被遗传到下一代种群中的概率为

(8)

然后根据P(xi)计算个体的累计概率

(9)

最后在[0,1]内产生一个均匀分布的伪随机数k。若k

选择算子执行完毕后,交叉算子从下一代种群中随机选择2个解xi,xj,交叉产生解xs。首先初始化解xs={xs(i)}={0,…,0},1≤i≤n。然后比较xi和xj,若xi(i)=xj(i)=1,令xs(i)=1,否则xs(i)=0。因为交叉产生的解xs中选中列数小于r,因此需要使用贪心算法进行修复。依据Q(i)=Si∩U计算出解xs中所有未选列的性价比值,重复执行2.2节中步骤3和步骤4,直至解xs满足|xs(i)=1|=r。

3 性能分析

本文通过仿真实验对IGARD方案的相关性能(路段覆盖率和RSU平均扩展通信范围)与其他部署方案进行了对比。仿真平台为Visual Studio 2015,仿真语言为C++,仿真环境为城市场景。实验默认参数见表1,表中c×c表示RSU部署区域包含c2个十字路口,相邻十字路口间的路段被划分为3个子路段,每个子路段长度为R,则部署区域为3R(c-1)×3R(c-1)。

表1 实验默认参数

为了更准确地模拟真实的城市环境,假设部署区域内各子路段上的车辆密度和车辆平均速度是不均匀分布的。靠近十字路口处的子路段上车辆密度相对较高,车辆平均速度相对较低。远离十字路口处的子路段上车辆密度相对较低,车辆平均速度相对较高。当部署区域为8×8时,区域内包含336个子路段,此时,车辆密度和平均速度的具体分布情况分别如图6、图7所示。

图6 部署区域内各子路段上车辆密度的分布图

图7 部署区域内各子路段上车辆平均速度的分布图

路段覆盖率是衡量部署方案有效性的指标,是部署方案性能的直接体现,表示为

(10)

式中:Rvalid是RSU的有效覆盖路段,它等于总路段Rall减去被多个RSU重复覆盖的路段。

RSU的平均扩展通信范围与路段上车辆的密度和平均速度相关,通过多跳转发RSU的直接通信范围得到扩大。该参数是单个RSU部署位置最优性的体现,可以间接反应出RSU覆盖区域的重复度

(11)

式中:Rvalid可由式(10)获得;Rdirect是RSU直接覆盖路段的总和;a是RSU部署数。

在此与RSU的热点部署方案和均匀部署方案[6]、MCP-g部署方案[13]对比了路段覆盖率和RSU的平均扩展通信范围。热点部署方案在覆盖路段最多的位置处部署RSU,直至部署数为r。均匀部署方案将n个RSU候选位置分为r个区域,取各区域中点处为RSU部署位置。MCP-g部署方案使用贪婪的启发式算法在各候选位置处选出r个使未覆盖路段覆盖最多的位置。将道路模型图转换为无向带权图后计算0-1覆盖矩阵,在其上运行RSU部署方案进而得到实验结果。

3.1 RSU部署数对性能的影响

本组实验主要研究RSU部署数对实验结果的影响。设置部署区域为8×8,数据传输最大时延τ=6 s。图8和图9分别给出了4种方案关于路段覆盖率和RSU平均扩展通信范围的对比图。

图8 a对路段覆盖率的影响

图9 a对RSU平均扩展通信范围的影响

由图8、图9可知,RSU部署数增加时,4种方案的路段覆盖率都逐渐增加,RSU平均扩展通信范围都逐渐下降,但本文方案优于其他3种方案。这是因为RSU部署数的增加使更多的路段被覆盖,提高了路段覆盖率,但重复覆盖路段也逐渐增加,进而降低了RSU平均扩展通信范围。同时由于V2V通信的存在,RSU的平均扩展通信范围一定大于其直接通信范围。MCP-g部署方案虽然考虑到了重复覆盖的路段,但在部署过程中只考虑单个位置的覆盖路段数会导致部署方案具有很大的局限性。热点部署方案基于贪心算法的思想部署RSU,但未考虑重复覆盖的路段。均匀部署方案基于分治的思想部署RSU,容易忽略部署的热点位置。因此,这两种方案的性能低于本文算法。

3.2 限定传输最大时延对性能的影响

本组实验主要研究限定传输最大时延对实验结果的影响。设置部署区域为8×8,a为15。图10和图11分别给出了4种方案关于路段覆盖率和RSU平均扩展通信范围的对比图。

图10 限定传输最大时延对路段覆盖率的影响

图11 限定传输最大时延对RSU平均扩展通信范围的影响

由图10、图11可知,限定传输最大时延增加时,路段覆盖率和RSU平均扩展通信范围均逐渐增大,且表现出几乎相同的增长趋势,但本文方案优于其他3种方案。这是因为在部署区域和RSU部署数一定时,路段覆盖率和RSU平均扩展通信范围只取决于RSU有效覆盖的路段。限定传输最大时延的增加使更多路段的车辆可以在时延内将数据传输至RSU,提高了路段覆盖率和RSU平均扩展通信范围。本文使用贪心算法产生初始种群,经过了选择、交叉、变异、染色体修复等一系列循环迭代,从全局考虑总覆盖路段部署RSU,而不局限于考虑单个位置的新覆盖路段数,因而与其他3种部署方案相比,获得了更优的部署位置。

3.3 部署区域对性能的影响

本组实验主要研究部署区域大小对实验结果的影响。设置a为15,数据限定传输最大时延τ=6 s。图12和图13分别给出了4种方案关于路段覆盖率和RSU平均扩展通信范围的对比图。

图12 部署区域对路段覆盖率的影响

图13 部署区域对RSU平均扩展通信范围的影响

由图12、图13可知,部署区域面积增大时,路段覆盖率逐渐下降,RSU平均扩展通信范围逐渐增加,且本文方案的性能优于其他3种方案。这是因为部署区域增大时,RSU有效覆盖的路段增加,提高了RSU的平均扩展通信范围,但其增加低于区域内子路段的增加,使得路段覆盖率逐渐降低。MCP-g部署方案与热点部署方案只考虑单个RSU部署后覆盖的路段,容易产生局部最优解。均匀部署方案虽从全局考虑部署位置,但缺少贪婪性。因此,这3种方案的性能均低于本文算法。

4 结 论

本文研究了RSU的部署问题,证明了该问题是NP-hard问题且可以转化为集合覆盖问题求解。为获取候选位置集中各元素覆盖的子路段数,设计了0-1覆盖矩阵和基于Dijkstra的求解算法。针对转化后的τ-LSCP问题,提出基于改进遗传算法的RSU部署方案，以最大化时延内将数据传输至RSU的子路段数。使用贪心算法产生初始种群,按照设定的交叉算子、变异算子执行交叉和变异操作并修复染色体,循环迭代求得RSU的部署位置。仿真结果表明,利用本文方案部署RSU可以提高路段覆盖率,进而提高网络的性能。