基于上下文的VANET服务推荐中间件

杨 倩 罗 娟 刘 畅

(湖南大学信息科学与工程学院 长沙 410082)

基于上下文的VANET服务推荐中间件

杨 倩 罗 娟 刘 畅

(湖南大学信息科学与工程学院 长沙 410082)

(1398654033@qq.com)

车载自组织网络(vehicle ad hoc network, VANET)作为智慧城市的重要组成部分，它需要为车辆安全、便捷交通及舒适驾驶提供众多的服务.目前针对车联网中服务发现的研究主要集中在服务发现质量和服务发现延时，但是随着VANET中服务数量和种类的增加，车联网中的信息激增问题变得越来越严重，因此如何按照个性化需求为用户推荐合适的服务成为目前车联网中亟需解决的问题.针对现有车联网中服务选择策略的不足，提出一种基于上下文的车联网服务推荐中间件体系结构，该中间件可以利用车辆丰富的上下文信息和用户的历史服务记录为用户推荐服务.利用离线分析方法，提出一种基于上下文的服务推荐方法，将既符合车辆上下文约束且满足用户偏好的服务推荐给用户.仿真结果表明，中间件推荐的服务合理且符合用户偏好，同时可以降低服务导致的绕路概率.

车载自组织网络;中间件;上下文;用户偏好;服务推荐

车载自组织网络(vehicle ad hoc network, VANET)是由车辆或车辆和路边单元(road side units， RSU)构成的一种自组织网络，它们之间通过无线局域网络进行通信[1].随着经济和科技的进步，现有的智能汽车搭载了各种传感器装置，如位置和速度传感器、ABS传感器、安全气囊传感器等，同时还具有较强的计算能力和可观的存储能力.由于不同车辆的底层设备存在异构性，因此可以使用中间件来提供统一通用的接口.中间件是一种位于应用程序与操作系统之间的软件，各种传感器可以将采集的上下文信息发送给中间件，由中间件对这些数据进行处理供上层应用使用.

现有车联网中服务发现的研究主要是针对车间资源的调度和共享[2-4]，而对实体服务的选择则主要依靠移动客户端(如手机、平板电脑等)进行查询.当用户处于驾驶状态，使用移动客户端进行服务查询存在安全隐患，同时如果用户请求与车辆本身相关的服务(如加油、车辆维修、查询车辆行驶路线上的餐厅等)，移动客户端不能获取到车辆特有的上下文信息，因此无法提供和上下文信息匹配的服务.随着智能交通的高速发展，用户对车联网信息服务的需求也在不断提高.车联网中的服务选择策略一般为随机获取服务提供者或者考虑服务质量(quality of service， QoS)等客观因素，用户缺乏个性选择能力，可能导致服务不合理或用户服务满意度较低.

目前对上下文感知中间件的研究较多[5]，Saravanaguru等人[6]提出一种基于上下文的车辆中间件结构，用于支持实时的分布式应用.Silva等人[7]提出一种车联网智能上下文配置中间件，该中间件可以为应用程序提供上下文信息，同时能够进行上下文逻辑推理并处理冲突.Thangavelu等人[8]提出一种基于车辆安全考虑的上下文感知中间件.Luo等人[9]提出一种基于开放服务网关协议(open service gateway initiative， OSGi)平台的服务共享中间件，选取车辆作为服务目录和网关节点，实现服务的发布和订阅.

服务推荐不同于常见的服务选择方法，用户具有明确的服务需求，只是在面对大量同种功能服务时很难选择出符合自身偏好的服务.近年来，大量研究工作围绕服务的QoS展开[10-11]，但这些研究并未过多地考虑用户的个性化需求.

推荐系统是个性化信息服务的主要技术之一，作为一种信息过滤的重要手段，目前推荐系统在电子商务、 信息检索以及移动应用、电子旅游、互联网广告等众多应用领域有较广泛的应用.推荐算法是推荐系统中的核心部分，常用的推荐方法包括：基于内容推荐、协同过滤推荐、基于知识推荐和组合推荐等.

车联网中的服务推荐属于移动推荐系统范畴，移动推荐系统受其移动特点和设备类型影响，其服务需求受上下文影响较大，同时对实时性和精确性要求也较高，因此不能将传统互联网的推荐方法直接应用到移动推荐系统中[12].目前对于车联网的服务推荐研究较少，Woerndl等人[13]提出一种协同的基于上下文感知的加油站推荐应用，该应用在油量行驶范围内寻找加油站，结合附近车辆用户的建议采用协同过滤方法进行服务推荐.采用协同过滤推荐方法涉及车辆间的用户历史数据交互，可能存在恶意用户获取其他车辆用户的个人隐私，同时该文只证实了服务推荐的合理性，并没有对算法的推荐性能做出分析和验证.

本文的主要工作如下：

1) 针对车联网中服务推荐的不足，提出一种基于上下文的车联网服务推荐中间件体系结构(VANET service recommendation OSGi， VSROSGi).

2) 利用离线分析方法，设计基于上下文的服务推荐(context based service recommendation， CBSR)策略，该策略属于基于内容推荐方法范畴.离线阶段通过对用户近期历史数据中满分服务的属性特征进行加权处理，获得用户偏好模型.在线阶段依据车辆上下文对可选服务进行上下文过滤，再通过欧几里得相似度计算公式计算服务与用户偏好模型的相似度，结合用户与服务的距离，最终为用户推荐合理且具个性化的服务.

1 系统模型

1.1 应用情境及网络组成

如图1所示，研究车辆正在按照箭头方向行驶，由于车辆油量过低，用户请求寻找加油站服务.加油站可分为几种类型，分别提供不同类型的加油服务(如汽油、天然气、充电等)，车辆行驶途中有多个加油站可以提供服务.用户需要在多个服务中选取符合自己偏好同时满足上下文约束条件(在油量允许范围内且不偏离行驶轨迹太远)的服务.

本文的VANET由车辆、RSU及服务站构成.车辆集合表示为V={V1,V2，…,VN}，每辆车可以通过GPS获取自身的二维地理位置坐标，车辆Vk的位置可以表示为(xk，yk)，(k=1,2,…,N).每辆车都配备车载通信装备、多个传感器及存储设备，通过传感器可以获得车辆速度、油量等上下文信息.存储设备可以存储用户的历史服务记录.车辆可以发出服务请求，服务请求定义为Req(V_id，V_type，V_location)，其中V_id为车辆在网内唯一id标识，V_type为车辆请求服务类型，V_location为车辆位置上下文.网络中的通信模式包括V2V(vehicle-to-vehicle),V2R(vehicle-to-RSU),R2R(RSU-to-RSU).服务提供者可以将其服务信息通过互联网注册到本地RSU上(RSU的服务注册和服务查询算法见2.4节)，服务注册定义为Ser(S_id，S_type，S_property)，其中S_id为服务在网内唯一id标识，S_type表示服务类型(如加油站应用场景中包括天然气能源、电能、燃油等)，S_property=location,factor1,factor2,…,factori,…是服务的属性信息，location为服务的位置，factori为服务关键的属性信息，如价格、预期等待时长等.

Fig. 1 Gas and service station scenario图1 加油服务站情景图

1.2 中间件框架

基于OSGi的VANET服务推荐中间件VSROSGi的整体设计框架如图2所示.中间件主要由4个模块组成，服务发现分为在线服务请求和离线2个阶段.

1) 设备模块.车载嵌入式感知模块包括摄像头、速度位置传感器等，它们将可提供的基础服务分别封装在设备模块中，在线服务阶段，中间件平台通过设备模块获取设备提供的上下文信息，同时可以实现设备控制.

2) 通信模块.在线服务阶段，车辆可以通过通信模块与其他车辆或RSU实现信息交互.车辆的服务请求基于GPSR协议向RSU发送，以附近车辆为中继节点将服务请求发送给RSU，车辆间使用DssOSGi[14]实现无线连接，车辆与RSU通过WLAN进行通信，RSU进行服务查询后，将符合请求的服务数据集serviceprovider通过通信模块返回给车辆.

3) 服务推荐模块.服务推荐模块是中间件设计的核心部分.离线阶段，根据用户历史服务记录为不同类型的服务计算相应的用户偏好模型；在线服务请求阶段，获取到通信模块传回的服务数据集后，对数据集进行上下文过滤生成推荐数据集recommended_dataset，推荐数据集与用户偏好模型进行相似度相关运算，再结合距离因素确定服务的推荐系数(recommended level)k，最后根据推荐系数的大小为用户推荐服务.

4) 服务应用模块.在线服务阶段，用户根据推荐服务列表，选择最符合自己偏好的服务，实现服务绑定，导航地图可以为用户指引服务位置及行驶路线.在服务完成后的离线阶段，用户可以对服务进行评价，服务及其对应评价将被存入到历史记录数据库中.

VSROSGi中间件充分利用OSGi面向服务的设计模型，将车载嵌入设备与车联网应用解耦.本中间件作为底层异构设备和应用程序之间的纽带，充分利用车辆独有的上下文信息和丰富的车载存储、计算资源进行服务选择，过滤掉不符合车辆上下文约束的服务，并根据用户特有的偏好进行服务推荐.同时，VSROSGi中间件在线阶段可以直接获取离线阶段计算的用户服务偏好模型，减少在线服务请求的响应时间，提高用户的服务满意度.

Fig. 2 Architecture of middleware图2 中间件体系结构

2 算法设计

本节首先介绍如何对服务数据集进行上下文过滤，然后详细介绍用户偏好模型生成方法及相似度计算方法，最后描述了服务推荐的算法步骤.

2.1 上下文过滤

上下文是系统实现服务推荐的信息来源，Dey[15]给出的上下文定义得到广泛引用：“上下文是用于描述实体状态的任何信息，其中实体可以是人、地点或者与用户和应用程序之间交互相关的客体(包括用户与应用程序自身)”.

针对该应用情境，选择位置、油量及行驶速度(矢量)作为最重要的上下文影响因素.服务请求车辆收到RSU发送的服务数据集后，计算请求车辆到各个服务的距离为

(1)

其中,(xp,yp)为服务提供者的位置坐标，(xv,yv)为车辆当前位置坐标.同时，车辆可以根据油量上下文通过油耗公式[16]计算油量允许的最大行驶距离(Max_distance)(假设车辆保持匀速行驶)为

(2)

其中,E为车辆的剩余能量，α和β为车辆常数参量，ν为车辆速度大小，R为车辆牵引力.由于距离超过车辆最大行驶距离的服务不符合车辆上下文，因此将其滤除后生成推荐数据集.

2.2 用户偏好模型生成

用户的历史服务记录表示为HisRecordtype,property,rate.其中，type为服务类型；property为服务的属性信息，来自服务注册时提供的服务属性；rate为用户对该次服务的历史评分(最高评分5分，最低评分1分).

假定用户对于同一服务的不同评价是由用户个性化差异导致.以请求加油服务站场景为例，有的用户更关注油价，而有的用户则对等待时间或付款方式要求较高.如图3所示，理想情况下满分服务为所有服务属性都是最优的，而实际情况下的服务并不能达到理想预期，用户将根据自己的服务偏好进行服务评价.因此将用户历史记录中所有满分服务的属性特征值进行平均质心运算生成centroidsfactor1,factor2,…,factori(用户偏好模型生成算法见2.4节)，可以理解为获取到用户服务偏好的平均值，即提出的用户偏好模型.如图3中所示，factor1和factor2为影响用户1服务选择的主要因素，而用户2则更关注factor3，factor4，factor5.

Fig. 3 User preference model图3 用户偏好模型示意图

2.3 相似度计算

使用欧几里得方法计算2个服务属性特征值的相似度.基于多维空间考虑，点x和点y计算欧几里得距离如式(3)所示.

(3)

其中,xi和yi为点x和点y在i维的坐标，n表示维度.就欧几里得距离意义而言，欧几里得距离越小，反映出2个信息点越接近，相似度越大；反之，欧几里得距离越大，相似度越小.一般将相似度与1类比，在数值上相似度的取值空间为[0,1].越接近1，相似度越高.相似度为1表示2个信息点重合，特征完全一致；相似度为0则表示2个信息点之间的欧几里得距离为无穷远，不具有任何相似性.欧几里得距离计算点x和点y的相似度sim(x,y)为

(4)

由式(4)可以看出，2个同类服务的属性值越接近，相似度越大，即服务与用户偏好模型特征值越接近，那么服务就越符合用户偏好.

一般来说，希望推荐的服务尽可能不影响车辆的既定行驶路线，因此服务距离也是影响服务选择的关键因素.我们在计算服务与偏好模型的相似度后，加入距离影响因子，通过加权计算推荐系数k来为用户推荐距离较近的偏好服务.

(5)

其中ω1和ω2分别为服务相似度和距离因素的影响因子，ω1+ω2=1.如果ω1较高，推送给用户的服务将更加注重用户的服务偏好，然而过分地追求服务偏好可能会带来绕路行为进而增大平均行驶距离.用户可以根据实际情况动态地调整ω1和ω2.如用户当前油量很充足，只是单纯地想寻找符合自身偏好的服务站进行补给，可以增加ω1的权重大小.3.2节的大量仿真实验证明，随着ω1的不断增大，平均服务推荐成功率的增长率降低，因此一般情况下，相对平衡地对ω1和ω2进行取值.

最后根据k值进行从大到小排序，选取前3个服务作为推荐集合recommended_collection，以列表形式提供给用户选择，具体算法见2.4节.

2.4 算法伪代码

算法1. 基于上下文的服务推荐算法.

输入：历史服务数据集合HisRecord、服务提供商Providerp、服务请求车辆Vehiclev；

输出：推荐集合recommended_collection.

① for each historys∈HisRecorddo

② if (s.rate=Optimal score) then

③ addstohr;

④ end if

⑤ end for

⑦ if (phas published a serviceser) then

⑧ addp.sertop.ser.typeserviceprovider;

⑨ end if

⑩ if (vhas submitted a servicereq) then

Fig. 4 Map for simulation图4 仿真区域

3 实验仿真与分析

本节以加油站服务场景为例，通过一组仿真实验比较4种服务选择策略的效果，并对结果进行分析和比较.4种服务选择策略分别为最短距离选择策略、综合评分选择策略、随机服务选择策略和提出的基于上下文的服务推荐策略.

1) 最短距离选择策略(shortest distance selection, SDS).用户选取离自己距离最近的服务.

2) 综合评分选择策略(average rating selection, ARS).用户依据点评网站上的综合评分高低选择服务.

3) 随机服务选择策略(random service selection, RSS).用户随意选取服务集中的服务作为选择.

4) 基于上下文的服务推荐策略(CBSR).该策略为本文提出的服务选择策略，根据车辆上下文对服务列表中的服务进行上下文过滤，通过计算服务与用户偏好模型的相似度获得符合用户偏好的服务集合，再结合距离因素为用户提出服务建议.

3.1 实验准备

实验使用MySQL作为用户历史数据的存储数据库，真实实验数据来自Yelp点评网站的50名用户，这些用户都曾访问过仿真区域内的服务站.

实验在4 000 m×4 000 m区域范围内仿真，仿真范围为美国加州San Francisco地区，如图4所示.仿真参数设置如表1所示.

Table 1 Simulation Parameter Settings

在加油站服务场景中对服务站的服务属性设置如下：

S_property=location,price,waiting_time,

auxiliary_service_num,pay_method,ave_rating，

其中,location为服务站的位置，price为服务报价，waiting_time为预期等待时间，auxiliary_service_num为服务站附属服务数目(如餐饮、车辆维修、购物等)，pay_method为可选支付方式(如现金、银行卡、电子支付等)，ave_rating为来自点评网站的服务站平均评分.

仿真实验采用服务合理性、服务推荐成功率以及服务平均行驶距离作为评价指标.服务合理性指服务是否在油量允许的访问范围内；服务推荐成功率p表示提供的服务为用户满意服务的比例，其计算函数为

服务平均行驶距离s为按照策略选择服务用户到达服务地点所需行驶的平均距离，这里只考虑距离的相对大小，距离的绝对大小受到仿真区域的服务分布影响.计算公式为

3.2 实验结构和分析

实验的推荐选择基于式(5)推荐系数的计算结果，不同的ω1和ω2设定(ω2=1-ω1)对最终的推荐结果有直接影响.图5表示ω1取0～1之间不同值时的平均推荐成功率和平均行驶距离.由图5中可以看出，当ω1较大时，即相似度所占权重较大时，服务的平均推荐成功率较高，但是此时距离因素ω2的权重较小，导致平均行驶距离较长；随着ω1的不断增大，平均推荐成功率的增长率降低，而平均行驶距离的增长率在ω1趋近于1时有显著提高.因此为了保证平均推荐成功率，同时尽量降低平均行驶距离，选择ω1=0.8，ω2=0.2.

Fig. 5 Average recommendation precision and averagedistance with different ω1图5 不同ω1下平均推荐成功率和平均行驶距离

Fig. 6 Service recommendation precision comparisonwith different selection methods图6 不同选择策略的服务推荐成功率比较

通过图6可以看出，随着历史数据集数据量的增加，CBSR的推荐成功率逐渐变大；在历史数据量较小的情况下，依据大量用户的综合评分结果进行服务选择的ARS和CBSR在性能上十分接近，但是当历史数据量变大，CBSR在性能上有明显提高，而ARS则表现不是很稳定，这是因为ARS只能反映大量用户对服务的一种普遍反映，而未对用户的个性化特征做出考量；SDS和RSS都未考虑用户的个性化需求，所以在性能上较差.

表2为对4种算法性能的综合比较.服务平均推荐成功率和服务平均行驶距离为经过多次实验求得的平均结果.从表2中可以看出，CBSR和SDS考虑了服务的合理性，即服务是否在用户可以到达的范围内；在服务推荐成功率上，CBSR可以达到70%以上，较其他3种算法表现良好；CBSR考虑了距离影响因素，比ARS和RSS的平均行驶距离更短，但是稍差于SDS.

Table 2 Algorithm Performance Comparison in Three

4 结束语

本文提出一种基于上下文的车联网服务推荐中间件体系结构VSROSGi，并设计基于上下文的服务推荐策略CBSR，该方法依赖用户历史数据建立的用户偏好模型，通过车辆自身的上下文感知特性对服务数据集进行过滤，考量服务与用户偏好模型的相似度和服务与用户距离，为用户推荐个性化的服务.通过实验分析，该方法较普遍的综合评分策略、随机服务选择策略和最短距离服务选择策略具有更高的推荐成功率，同时考虑了服务的合理性以及服务距离等影响因素.

进一步工作包括：针对车联网的特性，加入主动服务推荐策略，在保证用户历史数据安全的前提下，将服务主动推送给具有相似服务偏好的用户；加入用户轨迹分析策略，将服务的选择与用户行驶轨迹相结合，进一步提高用户满意度.

[1]Hartenstein H, Laberteaux K P. A tutorial survey on vehicular ad hoc networks[J]. IEEE Communications Magazine, 2008, 46(6): 164-171

[2]Mishra T, Garg D, Gore M M. A publishsubscribe communication infrastructure for VANET applications[C]Proc of the 2011 IEEE Workshops of Int Conf on Advanced Information Networking and Applications. Piscataway, NJ: IEEE, 2011: 442-446

[3]Ma Chunmei, Liu Nianbo, Wang Xiaomin, et al. Towards efficient multimedia publishsubscribe in urban VANETs[C]Proc of the 2014 IEEE Int Conf on Smart Computing. Piscataway, NJ: IEEE, 2014: 156-163

[4]Eichhorn M, Pfannenstein M, Muhra D, et al. A SOA-based middleware concept for in-vehicle service discovery and device integration[C]Proc of the 2010 IEEE Intelligent Vehicles Symp(IV). Piscataway, NJ: IEEE, 2010: 663-669

[5]Li Xin, Eckert M, Martinez J F, et al. Context aware middleware architectures: Survey and challenges[J]. Sensors, 2015, 15(8): 20570-20607

[6]Saravanaguru R K, Thangavelu A. CoMiTe: Context aware middleware architecture for time-dependent systems: A case study on vehicular safety[J]. Arabian Journal Forence and Engineering, 2014, 39(4): 2895-2908

[7]Silva F A, Silva T R M B, Ruiz L B, et al. ConProVA: A smart context provisioning middleware for VANET applications[C]Proc of the 77th Vehicular Technology Conf (VTC Spring). Piscataway, NJ: IEEE, 2013: 1-5

[8]Thangavelu A, Saravanaguru R A K. Context aware middleware model for handling vehicular safety issues[J]. Journal of Computer Science, 2012, 8(8): 1244-1252

[9]Luo Juan, Pan Qiu, He Zanyi. VANET middleware for service sharing based on OSGI[J]. Computer Science and Information Systems, 2015, 12(2): 729-742

[10]Garai M, Boudriga N. A novel architecture for QoS provision on VANET[C]Proc of the 10th Int Conf on High Capacity Optical Networks and Enabling Technologies.Piscataway, NJ: IEEE, 2013: 25-31

[11]Rehan M, Hasbullah H, Chughtai O, et al. ZLS: A next-door lightweight QoS aware location service technique for VANET on highways[C]Proc of the 2014 Int Conf on Computer and Information Sciences. Piscataway, NJ: IEEE, 2014: 1-6

[12]Meng Xiangwu, Hu Xun, Wang Licai, et al. Mobile recommender systems and their applications[J]. Journal of Software, 2013, 24(1): 91-108 (in Chinese)(孟祥武, 胡勋, 王立才, 等. 移动推荐系统及其应用[J]. 软件学报, 2013, 24(1): 91-108)

[13]Woerndl W, Eigner R. Collaborative, context-aware appli-cations for inter-networked cars[C]Proc of the 16th IEEE Int Workshops on Enabling Technologies: Infrastructure for Collaborative Enterprises. Piscataway, NJ: IEEE, 2007: 180-185

[14]Xie Kun, Wang Xin, Wen Jigang , et al. Cooperative routing with relay assignment in multi-radio multihop wireless networks[J]. IEEEACM Trans on Networking, 2016, 24(2): 859-872

[15]Dey A K. Understanding and using context[J]. Personal and Ubiquitous Computing, 2001, 5(1): 4-7

[16]Younes M B, Boukerche A, Rom’an-Alonso G. An intelligent path recommendation protocol (ICOD) for VANETs[J]. Computer Networks, 2014, 64(9): 225-242

Yang Qian, born in 1992. MSc. Her main research interests include VANET and recommender system.

Luo Juan, born in 1974. PhD, professor, PhD supervisor. Her main research interests include Internet of things, cloud computing and middleware.

Liu Chang, born in 1987. PhD candidate. Her main research interests include Internet of things and network security.

Context Based Service Recommendation Middleware in VANET

Yang Qian, Luo Juan, and Liu Chang

(CollegeofComputerScienceandElectronicEngineering,HunanUniversity,Changsha410082)

VANET (vehicle ad hoc network) is a very important part of smart city which is required to implement a myriad services related to vehicles safety, traffic efficiency and comfortable driving experience. The current researches on service discovery in VANET are mainly focused on quality and latency of service. But with the development of service number and service type in VANET, the information explosion in VANET is increasing seriously, so there is an urgent need for VANET to provide services considering users’ individual requirements. This paper presents a context based service recommendation middleware architecture for VANET which can recommend services for users based on vehicles’ rich context information and users’ service history. With offline theory, a context-based approach of service recommendation is provided. Only when services meet the vehicle’s context constraints and the users’ preference model, they could be recommended to the user. Experimental results show that the recommended services are reasonable and meet users’ preference, additionally, the detours probability caused by services can be reduced.

vehicle ad hoc network (VANET); middleware; context; user preference; service recommendation

2016-08-22；

2016-12-20

国家自然科学基金项目(61672220,61370094,61300219)；湖南省自然科学基金杰出青年基金项目(13JJ1014) This work was supported by the National Natural Science Foundation of China (61672220, 61370094, 61300219) and the Natural Science Foundation for Distinguished Young Scholars of Hunan Province (13JJ1014).

罗娟(juanluo@hnu.edu.cn)

TP393