余 意 李 松 王艳芬
(*中国矿业大学信息与控制工程学院 徐州 221116)
(**徐州市智能安全与应急协同工程研究中心 徐州 221008)
车联网(Internet of vehicle,IoV)使用无线通信、传感探测等技术将服务器、路边单元(road side unit,RSU)和车载单元等设备连接,采集车辆、道路、环境等信息,通过车与车、车与路、车与人之间的信息交互和共享,使车与基础设施之间智能协同与配合,最终实现车辆智能化控制、智能交通管控和智能动态信息服务的一体化网络[1-2]。
随着智能网联汽车数量的快速增长[3],交通信息的不及时传输会导致更高频次的交通拥堵和交通事故,从而降低人们的出行效率[4]。作为5G 通信中的关键技术,V2V(vehicle-to-vehicle)通信使得道路上的邻近车辆可直接建立连接[5],实现车辆在道路上的信息共享,如车辆自身状态信息、道路预警和事故调查的信息等。通过在车辆网中引入缓存,车辆将交通状态等信息缓存到本地,并经由V2V 通信与其他邻近车辆共享,既可以实现安全高效的行驶,也能够有效降低车辆网基础设施的通信数据量[6]。
文献[7]将V2V 通信与缓存结合,来有效控制车联网多跳中的数据流量,减少车辆出行和数据通信的成本;为缓解车联网下多媒体业务广泛应用而给系统带来的流量负担和能源消耗,文献[8]针对V2V、V2R(vehicle-to-RSU)的混合通信模式,提出一种用于信息娱乐服务的能量感知缓存方案,实现了更高的节能效果和更低的平均访问延迟。文献[9]通过评估车辆的社区相似性和隐私等级设计了一种动态概率缓存方案并提出了基于内容流行度的缓存部署车辆选择方案,有效减少平均时延并增加缓存命中率。
随着智能物联网设备数量的急剧增长,设备间的社交关系的挖掘与利用逐渐成为无线通信研究中的热点[10-12]。社交网络将网络信息空间与现实信息空间相连接,并产生包含了传播信息和社交行为等维度的数据,这些数据可用于辅助IoT 设备间的通信。文献[13]将车联网与在线社交网络相结合提出一种用于社交车联网的信任感知通信架构以保证车辆提供信息的准确度。文献[14]则基于社交关系提出一种物联网场景下的安全内容共享方案,避免共享内容被不受信任的用户拦截,实现内容分发安全性和用户体验的折中。文献[15]将社交关系应用于车联网中来预测车辆移动轨迹,从而有效减少了交通堵塞。
车联网中内容缓存可有效减小RSU 的服务压力以及节省车辆的通信资源,但却增大了车辆的存储资源消耗;利用社交关系和缓存联合优化车联网中通信资源和存储资源消耗的研究相对较少。
受以上研究启发,本文构建了车联网场景下的基于社交关系的内容共享模型以权衡车辆的通信资源和存储资源消耗,在满足车辆内容获取请求下,最小化系统的内容获取代价。将内容获取代价最小化问题构建成车辆的内容获取的策略选择问题,并将策略选择转化成一个局部合作博弈,通过分析该博弈的纳什均衡,进而提出基于社交关系的局部协作缓存算法(social-based local cooperative caching algorithm,SLCCA)求得系统的内容获取代价最小下的博弈策略。
本文构建了车联网场景下的基于社交关系的内容共享模型,本节从物理域和社交域2 个维度描述该模型。
如图1 所示的车联网系统中,该区域部署有单个RSU,区域中有N辆车,车辆集合可记为N={1,2,3,…,N},编号0 表示RSU。车辆i∈N 的最大存储空间记为Ki,系统中的车辆都具备V2V 通信能力。车辆请求获取的内容包括其他车辆的状态信息、路况信息等,这些信息既可以通过V2R 通信链路获取,也可以通过V2V 通信链路获取。为避免V2V 链路和V2R 链路之间产生同频干扰,车联网系统中的V2V 通信使用专有频谱。
图1 物理域系统模型图
车辆可请求的内容集合记为F={1,2,3,…,L},内容f∈F大小为Zf,RSU 有集合F中的所有内容的缓存。在包含τ个时隙的时间段T={t1,t2,…,tk,…,tτ} 内,集合N 中车辆会针对不同内容发起请求,并且一辆车最多只对一则内容发起请求。车辆的内容请求状态矩阵记为,其中=0 表示在时隙tk车辆i没有对内容f发起请求,反之则表示车辆i对内容f发起了请求。根据历史记录,车辆本地缓存有集合F中的一部分,车辆在时隙tk的内容缓存状态矩阵记为,其中=0表示车辆i在时隙tk未缓存内容f,反之则表示车辆i缓存有内容f。
假设车辆在时间段T内不会出现大幅度位置变化,时隙tk内车辆i的地理位置坐标记为,车辆i和车辆j间地理距离由式(1)计算。
V2V 的最大通信距离记为dth,若≤dth,称车辆i和车辆j互为邻居车辆,则车辆i可与车辆j建立V2V 连接。时隙tk下车辆i的邻居车辆中缓存有内容f的车辆集合记为,一个时隙里一辆车至多只能与一辆车建立V2V 连接。
如果车辆i缓存有内容f,则车辆无需向其他车辆或RSU 请求该内容;如果车辆i未缓存内容f,车辆i可从缓存有该内容的邻居车辆或RSU 处获取该内容。
车辆获取到请求内容需要付出一定的代价,包括通信资源和存储资源消耗。由于自身资源的有限性,车辆的使用者具有理性和自私的特点,并不会主动贡献自己的通信资源或存储资源。将社交关系引入到车联网中可激励具有紧密社交关系的车辆间建立连接并进行内容共享,还能通过分析车辆间的社交行为实现信任管理,以保证内容共享过程的可靠性。本文系统模型中的车辆社交属性包括内容偏好程度、亲密度、路径相似度和信誉度。
车辆获取到请求内容付出的代价与车辆对内容的偏好程度有关,若车辆i对内容f感兴趣,则车辆i认为获取到内容f更有价值。车辆i在时隙tk内对内容f的偏好程度服从齐夫分布,即式(2),车辆对内容的偏好程度记为矩阵。
亲密度描述了车辆间的联系强度,根据历史记录,在过去δ个时间段里,车辆i和车辆j之间的连接次数记为CTij,δ,第q次连接所持续的时长记为CDij,δ,q,q≤CTij,δ。时隙tk内,车辆i和车辆j间的亲密度由式(3)计算[16]。
路径相似度可用于表示车辆感兴趣内容之间的相似性。车辆的路径由一系列按时间排序的位置组成,δ个时间段里车辆i的路径记为Tri,δ={(Li,1,t1),(Li,2,t2),…,(Li,h,th),…,(Li,δ,tδ)},(Li,h,th) 表示车辆i在时刻th时的位置Li,h。时隙tk内,车辆i和车辆j间的路径相似度由式(5)计算[17]。
其中,‖·‖为两点坐标的欧氏距离。
信誉度描述了车辆之间可信任程度,为提高获取内容的安全性以及内容共享成功率,车辆通常选择与信誉度高的车辆建立V2V 连接。时隙tk内,车辆i对车辆j的信誉度通过式(6)计算[16]。
其中,SRij,δ表示过去δ个时间段内车辆j向车辆i传输内容的成功率,可用式(7)描述。
其中,CSij,δ表示车辆j成功将车辆i请求的内容发送给车辆i的次数。
综合考虑上述3 个维度的社交属性,车辆i和车辆j之间的社交强度sij由式(8)定义。
其中,ω1、ω2和ω3分别是3 个维度社交属性的权重,且ω1+ω2+ω3=1。
在上述车联网内容共享模型中,由于在内容获取时需要占用相应通信资源和存储资源,每辆汽车在获得内容时需要付出一定的代价,系统中车辆的内容获取总代价取决于车辆社交属性、车辆的内容缓存状态以及获取内容方式。在上述模型中,车辆i有3 种内容请求方式。
(1)车辆i本地缓存有内容f,其无需建立通信链路请求该内容,内容获取代价=0。
(2)车辆i与RSU 建立V2R 连接,车辆i需要付出从RSU 获取内容的通信代价,若车辆i选择将内容缓存在本地,则还需要付出内容存储代价。
车辆与RSU 间的地理距离越小,意味着车辆获取内容的通信代价越低。为了简单起见,本节中的通信代价可认为是由于路径损耗带来的代价,记通信距离d带来的路径损耗为F(d),单位路径损耗下的通信成本记为BL,那么通信距离d带来的通信代价可记为F(d)·BL。在该方式下,车辆i从RSU获取内容的通信代价可以建模为·BL。
车辆i对内容f的缓存选择记为∈{0,1},=0 表示车辆i选择不缓存内容f到本地,反之表示缓存到本地。记单位容量大小内容的缓存放置成本为α,车辆i将内容f缓存至本地的存储代价表示为Zfα。
考虑到上述车辆对不同内容有不同的偏好,车辆i的内容获取代价可用式(9)计算。
(3)车辆i与车辆j∈建立V2V 通信,车辆i需要付出与车辆j进行V2V 通信的代价,若车辆i选择将内容缓存在本地,则还需要付出存储代价。在该方式下,车辆i的V2V 通信代价与车辆之间的地理距离和社交强度相关。根据式(1)和式(8),结合车辆地理距离和社交关系,车辆i和车辆j之间的社交加权距离可由式(10)计算。
由式(10)可知,当车辆间的地理距离越小或社交关系越紧密时,越小,意味着车辆获取内容的通信代价越小。根据前面分析,车辆i从RSU 获取内容的通信代价建模为·BL。
考虑到车辆对不同内容有不同的偏好,车辆i的内容获取代价可用式(11)计算。
依据式(9)、(11),车辆i获取到内容f的内容获取代价可用式(12)计算。
本文的优化问题定义为最小化时间T内系统的总内容获取代价,用式(13)表示。
其中限制条件式(13.3)表示所有内容占用的存储空间不得超过车辆自身的存储空间大小。如果自身的存储空间不足以容纳请求的新内容,则通过最近最少使用(least recently used,LRU)算法进行内容更新[18]。
由式(12)可知,邻居车辆的缓存状态会影响车辆i在时隙tk的选择。若有较多的邻居车辆有内容f的缓存,车辆i可以选择与更多不同的车辆建立V2V 通信,相应可减少系统的内容获取代价;反之车辆i在tk时的策略也会影响其他车辆的选择,从而影响系统的内容获取代价。为最小化车辆在时间段T内的内容获取代价之和,车辆之间需要进行协作缓存,部分车辆贡献自身的存储资源将请求的内容缓存在本地,使得其他车辆可经由V2V 通信获取到请求的内容,以权衡系统下车辆的通信资源消耗和存储资源消耗。
优化问题式(13)是一个NP-hard 问题[19]。本文将上述基于社交属性的车辆间协作缓存问题建模成基于社交属性的协作缓存博弈问题,并将时间段T分为博弈过程、内容获取与共享过程,车辆作为博弈的参与者决定获取请求内容的途径以及是否将请求的内容保存到本地,在时间段T的前若干个时隙里通过多轮博弈得到优化问题式(13)的最优策略集。
由上述分析可知,车辆i获取内容f时的决策既包含从何处获取,也包含是否将内容缓存到本地。记该博弈为G={N,S,u},其中N是参与博弈的所有车辆的集合;S是所有参与博弈的车辆的策略集合,车辆i获取内容f的策略记为si,f=(Ci,f,Gi,f),S={si|i∈N},si={si,f|f∈F};u是参与博弈车辆的效用函数。
由式(12)可知,在决策si下,车辆i的内容获取代价之和costi可用式(14)表示。
考虑到车辆间的协作,对于车辆i、策略为si下的效用函数ui定义为自身的内容请求代价和其邻居车辆的内容请求代价之和。
式(15)中等号右侧第2 部分表示车辆i的邻居车辆的内容请求代价之和。
优化问题式(13)可转化为在博弈阶段求得一个策略集合,使得所有车辆的效用函数之和最小,即优化如下问题:
在上述博弈G中,对于任意车辆i∈N,优化问题式(16)下整体最优策略中车辆i的策略记为,如果车辆i单方面将自己的策略由改为而无法提升自己的效用,即式(17)无法成立,则博弈G的策略是一个纯策略的纳什均衡。
满足式(18)的博弈称为严格势力场博弈,其中Φ(·) 是博弈的势函数,文献[20]表明严格势力场博弈至少存在一个纯策略的纳什均衡点。
对于上述博弈G,构造势函数Φ(·),用式(19)表示。
车辆i将其策略由改为,且,那么势函数的变化量可用式(20)表示。
由式(18)可知,上述博弈G是一个严格势力场博弈,因此该博弈至少存在一个纳什均衡点,且在有限策略集合下,势函数最小值点就是纯策略纳什均衡。
根据上述讨论与分析,针对建模的基于社交属性的协作缓存博弈,受文献[21]启发,本文提出基于社交关系的局部协作缓存算法。在初始化阶段,所有的车辆先默认自己的策略为从RSU 获取到请求内容并且不缓存请求内容,且将t1时隙的相关参数作为初始化参数,具体为。决策迭代过程分为3 个阶段:第1 阶段为车辆选择,在这一阶段中车辆i都是按照1/N的概率随机选择,选择车辆后计算车辆i在第l次博弈中的代价costi(l) 和效用函数值ui(l);第2 阶段为策略探索阶段,车辆i主动随机产生新策略,其他车辆被动更改策略,若车辆i在新策略下不缓存内容到本地,那么其他从车辆i获取内容的车辆将策略更改为从RSU 获取且不缓存到本地,根据式(12)和式(15),车辆i确定新策略下的效用函数值;第3 阶段为策略更新阶段,在这一阶段中,车辆i按照式(21)、式(22) 和式(23)对其策略进行更新,式中β为调节因子,并更新本次迭代时的缓存状态矩阵Cl。
上述算法描述如算法1 所示。
本文SLCCA 算法的复杂度取决于单个车辆的邻居车辆数量。最差的情况下,所有的车辆都互相为邻居车辆,且对于任意车辆i,ci,f=0,ri,f=1,∀f∈F,在最多有N辆汽车和L个请求内容的情况下,车辆i请求的内容最多有2N种策略,上述算法的最差时间复杂度为O(LN2);最好的情况下,对于任意车辆i,其邻居车辆集合为空,即没有邻居车辆,那么上述算法的最好时间复杂度为O(LN);平均情况下,对于任意车辆i,有辆车是其邻居车辆,在有L个请求内容情况下,车辆i请求的内容最多有2N种策略,那么上述算法的平均时间复杂度也为O(LN2)。
本节对上述提出的SLCCA 算法进行了仿真实验和性能分析。仿真实验中,路径损耗模型简化为F(d)=d-α,α为路径损耗指数并设置为4,RSU 的覆盖半径为300 m,车辆总数量为20~50 辆,车辆存储空间均为100 MB,单个请求内容大小均为5 MB,最大V2V 通信距离为90~150 m,3 个维度社交属性的权重均为1/3,单位路径损耗的通信成本为0.1,内容缓存放置成本为0.5。仿真过程中将本文策略与RSU 策略、随机缓存和贪婪缓存等方案进行对比。
RSU 策略:若车辆的本地没有请求内容的缓存,则与RSU 建立V2R 连接获取请求内容,并且获取的内容不缓存到本地。
随机策略:所有车辆等概率随机选择获取请求内容的策略,可以选择V2V 通信获取到请求的内容,也可以从RSU 获取到请求的内容,车辆是否将请求内容缓存到本地也是等概率随机的。
贪婪策略:所有车辆只考虑最小化自身的请求代价而不考虑系统整体的请求代价。
图2 描述了不同策略下车辆的平均内容获取代价与不同车辆数量之间的变化关系,其中V2V 最大通信距离dth=120 m。在RSU 策略下,车辆只能与RSU 建立V2R 连接获取到请求内容并且不缓存到本地,随着车辆数量的增加,车辆的平均内容获取代价也会增加。在随机策略下,车辆对获取内容途径和内容缓存的选择都是随机的,但车辆选择到整体最优策略概率较小,车辆平均内容获取代价整体随着车辆数量的增加而增加。在贪婪策略下,每辆车仅针对自身的内容获取代价做出最优选择,部分车辆选择从RSU 获取,部分车辆从邻居车辆经由V2V获取,且获取的内容不缓存到本地。随着车辆数量的增加,本地有请求内容缓存的车辆数量会增加,车辆平均请求代价整体以较缓趋势增加。在本文策略下,车辆不仅会考虑自身的内容获取代价,也会考虑整体内容获取代价而选择性地将内容缓存到本地,其他车辆可经由V2V 通信获取到请求内容。随着车辆的增加,选择缓存请求内容到本地的车辆会增加,因此车辆平均内容获取代价随着车辆数量的增加而增加。仿真结果表明,在相同车辆数量下,相较于其他3 种策略,本文策略的性能有优势。
图2 车辆平均内容获取代价-车辆数量
图3 描述了不同策略下车辆的平均内容获取代价与不同的V2V 通信距离之间的变化关系,其中车辆数量N=50。在RSU 策略下,车辆只与RSU 建立V2R 连接获取请求内容,在车辆数量固定下,车辆的平均内容获取代价不随V2V 通信距离变化而变化。在随机策略下,车辆的请求内容获取途径和请求内容的缓存都是随机的,车辆平均请求代价本没有明显变化规律,但随着V2V 通信距离的增加,向其他车辆请求建立连接时有更高几率获取到请求内容,车辆的平均内容获取代价随之减少。在贪婪策略下,车辆仅针对自身内容获取代价做出最优选择,随着V2V 通信距离的增加,可与其他车辆共享本地缓存内容的车辆的数量也会增加,车辆的平均内容获取代价随之减少。在本文策略下,车辆的策略选择同时考虑自身内容获取代价和整体内容获取代价,部分车辆通过选择缓存请求内容到本地,随着V2V 通信距离增加,可共享给其他车辆,车辆的平均内容获取代价随着V2V 通信距离增加而减小。仿真结果表明,在相同V2V 通信距离限制下,相较于其他3 种策略,本文策略的性能有优势。
图3 车辆平均内容获取代价-最大V2V 通信距离
图4 描述了本文策略下车辆的平均内容获取代价与博弈次数之间的变化关系,其中车辆数量N=50,V2V 最大通信距离dth=120 m。随着博弈次数的增加,车辆逐步做出更有利于减小车辆平均内容获取代价的策略,一定次数博弈后,车辆的平均内容获取代价不会随着博弈次数的增加而改变。理论分析和仿真结果表明本文策略有较好的收敛性。
图4 车辆平均内容获取代价-博弈次数
表1 描述了不同策略的平均时间耗费,其中测试环境为AMD Ryzen 7 4800U Windows10,软件版本为Matlab 2021a,V2V 最大通信距离dth=120 m,车辆数量N=20,测试次数为50 次。在RSU 策略下,车辆只与RSU 建立V2R 连接获取请求内容,因此得到结果只需要耗费极少的时间。在随机策略下,车辆的请求内容获取途径和请求内容的缓存都是随机的,因此得到结果只需要耗费较少的时间。在贪婪策略下,车辆仅针对自身内容获取代价做出最优选择,因此得到结果也只需要耗费较少的时间。在本文策略下,车辆的策略选择需要同时考虑自身内容获取代价和整体内容获取代价,得到结果需要耗费较多的时间。但由图2 和图3 仿真结果可知,本文策略是在时间耗费和性能上的折中。
表1 不同策略的平均时间耗费
为应对智能网联汽车场景下的大数据量和海量连接等特点,实现安全高效的行驶以及降低核心网的数据流量,本文构建了车联网场景下的内容共享模型。建模了基于车辆社交关系的内容获取代价最小化问题,通过优化车辆选择获取请求内容的途径以及是否将请求内容缓存到本地来减小车辆的平均内容获取代价。将建模的优化问题转化为车辆间的局部协作缓存博弈问题,通过分析博弈的纳什均衡,提出基于社交关系的局部协作缓存算法求得优化问题的最优解。仿真结果表明,本文提出的基于社交关系的局部协作缓存算法可有效降低系统的平均内容获取代价。