车辆雾计算中基于反向拍卖的停车辅助方案

朱兰婷,孙丽珺,闫 杨

(青岛科技大学 信息科学技术学院,山东 青岛 266061)

0 概述

随着智能连接设备数量的增加,智慧城市、5G网络、车联网以及无线传感器网络中的数据呈现爆炸式增长[1-2]。雾计算将云计算的弹性资源从云数据中心扩展至网络边缘,缓解了网络拥塞现象并缩短了服务响应时间[3-4]。车辆雾计算(Vehicle Fog Computing,VFC)作为雾计算的一种扩展模式,将雾计算与传统的车载网络相结合,设置车辆作为通信和计算的基础设施,利用靠近用户的边缘设备提供实时响应服务,从而大幅提高了服务质量[5]。

传统的车载网络部署路侧单元(Road Side Units,RSU)为移动终端提供服务。随着服务请求的增加,RSU的数据处理压力不断提高[5]。此外,人口数量的增加和城市空间资源的限制,导致了严重的城市停车问题。许多城市的交通堵塞是由于车辆寻找停车位所造成,智能停车辅助可以节省用户搜索车位的时间,如自动泊车系统可以为驾驶员提供实时停车导航服务[6-7],从而缓解交通拥堵现象。将VFC与智能停车辅助相结合,选择一些具有雾计算能力的智能车辆作为基础设施,与移动的车辆用户进行信息交换和共享,可以改善交通状况。

在VFC中,充当雾节点的智能车辆等设备具有资源有限性、分布性等特点,为VFC的发展带来挑战[8]。在一个地理区域内的各雾节点构成一个车辆雾网络,各节点分布广泛,实现雾计算资源的合理分配存在一定难度。如何利用雾节点为用户提供服务,使节点资源得到充分利用,成为亟待解决的问题[9-10]。此外,虽然雾节点可以独立地为用户提供低延迟服务,但其与云数据中心相比能力有限[11]。VFC需要不同的雾节点提供服务,雾节点在贡献资源的同时会花费一定的成本。因此,需要建立激励机制,激励雾节点持续稳定地贡献资源,进一步提高服务质量[12-13]。

本文提出一种基于反向拍卖的VFC停车辅助分配策略RAFC,以帮助用户获取停车信息资源。由于反向拍卖可以使市场更具竞争力,有助于买方以最优惠的价格得到服务[14],因此在智能车辆雾计算能力相对有限的条件下,本文将VFC智能停车辅助与反向拍卖相结合,激励雾节点贡献资源,使更多的用户以更低的价格获得服务,从而缓解交通压力。

1 相关工作

拍卖机制以投标方式来分配商品,建立相应的价格体系以实现资源的有效配置。传统拍卖由卖方提供待售商品,买方进行竞价,价高者得。而反向拍卖由买方提出购买需求,卖方进行报价,出价最低且满足买方需求的卖方竞标成功。在VFC停车辅助系统模型中,买方是欲获得停车信息资源的车辆用户,卖方是提供待售资源的智能车辆,拍卖代理是第三方平台。由拍卖代理决定拍卖分配并宣布拍卖结果。

为充分调动参与者的积极性以实现资源合理分配,将经济分析和定价模型与网络资源分配相结合,可以更好地在社会效用、用户满意度、匹配成功率等方面发挥作用。因此,基于拍卖的分配策略得到越来越多的关注。文献[15]提出一种基于反拍卖模型的激励方法,针对反拍卖可解决用户退出和预算平衡问题的优点,对模型中涉及的任务覆盖、反拍卖选择和奖励实施等关键技术进行深入分析与研究。文献[16]研究群智感知中单任务场景下的激励机制,采用反向拍卖方式,提出一种基于区域覆盖的群智感知激励机制,以提高区域覆盖率和用户参与度。文献[17]针对边缘网络的资源有限性问题,提出基于拍卖的资源分配方法。在雾计算的资源分配问题中,文献[13]针对支持VFC的智慧城市,提出一种通过资源定价影响车辆路径选择的激励方案,以减轻资源需求的地理不平衡性,但其没有考虑提高用户的匹配成功率。文献[18]建立一种Stackelberg博弈模型,解决服务运营商的定价以及用户的资源购买问题。文献[19]将区块链与云/雾计算服务相结合,建立基于拍卖的市场模型,以提高资源分配率和区块链网络的社会福利,但其未研究应用的时延性问题。

目前,部分研究人员将反向拍卖与网络资源分配相结合,但未将反向拍卖与VFC停车辅助问题进行联系,也未考虑用户的时延和成本问题。本文提出一种RAFC策略,考虑车辆用户的时延和成本需求,将提高用户匹配成功率和降低用户开销成本作为优化目标,激励用户和雾节点积极参与分配。

2 VFC停车分配问题建模

2.1 问题描述

如图1所示,在一个地理区域内,一个VFC停车辅助系统由需要获得停车信息资源的车辆用户U={u1,u2,…,um}、充当雾节点的智能车辆F={f1,f2,…,fn}以及第三方平台物联网提供商三部分组成[20]。其中,用户作为买方,提交时延要求、资源需求,雾节点作为卖方,提供资源服务,第三方平台担任拍卖代理,负责接收信息和协调分配。本文假设各用户相互独立,一个用户请求最多只能迁移至一个雾节点完成,但一个雾节点可以接收处理多个请求。

图1 VFC停车辅助系统模型

在物联网中,通常将一个较大区域划分成若干独立子区域,一个子区域内的雾节点构成一个雾网络。本文考虑在一个车辆雾网络内,由第三方平台搜集信息,将雾节点资源提供给需求用户。本文符号说明如表1所示。

表1 符号说明

2.2 问题建模

本文RAFC策略在满足用户时延要求的基础上,最小化用户的开销成本并提高匹配成功率。用户、雾节点和第三方平台的三方交互关系如图2所示。

图2 三方交互关系示意图

在图2中,①表示用户ui∈U将请求Qi=(qi,Di)提交给第三方平台,雾节点fj∈F将资源量和资源单价信息Lj=(dj,Aj)提交给第三方平台;②表示第三方平台根据提交的信息确定分配方案,将结果通知双方;③表示拍卖成功的用户支付费用给雾节点和第三方平台,雾节点支付代理费给第三方平台。

RAFC策略的目标包括:

1)实现个人理性和预算平衡。

2)激励三方积极参与分配。

3)满足用户的时延要求和资源需求。

4)提高用户的匹配成功率。

5)降低用户的开销成本。

2.3 效用函数

2.3.1 用户的效用函数

(1)

收益函数Ui(qi)表示ui的请求响应后可获得的收益,qi表示ui的资源需求量,Ui(qi)可表示为:

Ui(qi)=alb(1+qi)

(2)

参数a计算如式(3)所示,a∈[1,2],其取值与用户需求有关,a值越大,表示资源需求越紧急。

(3)

开销成本函数Pi(qi)表示ui获得资源后应支付的费用,包括ui向提供资源的雾节点支付的费用、转发费用以及支付给第三方平台的代理费。Pi(qi)表示为:

(4)

为激励用户积极参与分配并支付费用获取服务,应满足用户可获得的资源收益大于成本支出,即Ui(qi)>Pi(qi)。

2.3.2 雾节点的效用函数

(5)

2.3.3 第三方平台的效用函数

(6)

3 RAFC策略

3.1 目标函数

RAFC策略将VFC停车辅助与反向拍卖相结合,制定分配方案,以最大化用户匹配成功率同时最小化其开销成本。RAFC策略的目标函数定义为:

(7)

(8)

s.t.

xij∈{0,1}

(9)

(10)

(11)

Ui(qi)>Pi(qi)

(12)

(13)

(14)

(15)

式(7)表示满足用户请求,实现匹配成功率最大化。式(8)表示最小化用户开销成本。约束条件式(9)的xij表示雾节点fj的资源分配给用户ui是否成功,xij=0表示未分配成功,xij=1表示分配成功。约束条件式(10)表示ui成功分配的资源量小于或等于参与分配的fj提供的资源量。约束条件式(11)表示分配成功的ui数目小于或等于提出请求的ui数目,约束条件式(12)表示ui获得收益大于支出成本。约束条件式(13)表示fj的转发收益大于转发成本。约束条件式(14)表示fj的资源服务收益大于资源成本与代理费之和。约束条件式(15)表示第三方平台获得的代理费大于支出成本。

上述目标函数属于多目标优化问题,可以将多目标优化转换为单目标优化问题来解决。最大化ui的匹配成功率可转换为最小化ui的匹配失败率。将目标函数式(7)、式(8)转换为单目标函数,可表示如下:

(16)

3.2 RAFC策略设计

整数规划可以将3.1节的目标函数问题简化为0-1规划问题,但0-1规划问题已经被证明是一个NP问题。本文提出RAFC策略来近似求解NP问题,该策略分为节点筛选阶段和资源匹配阶段。

3.2.1 节点筛选阶段

本文在Dijkstra算法[21]的基础上进行改进,提出一种节点筛选算法,将最短路径问题与用户的时延和成本需求相结合,目的是找到满足用户时延要求和最低成本需求的候选雾节点集合Fc。首先,计算各雾节点之间的最短路径,寻找满足用户时延要求的雾节点集合,不满足条件的雾节点不再参与下一阶段。然后,计算用户的开销成本,将成本最低的雾节点作为候选雾节点。节点筛选算法具体流程如算法1所示。

算法1节点筛选算法

输入U,F,W

输出Fc,Pi

1.Initialize: Fc←∅;Pi←∅;int i.j;

//Find the feasible shortest path that can meet the latency //requirement

2.for each ui∈U

3.for each fj∈F

6.Fc←Fc∪{fj};

7.end

8.end

9.for each ui∈U

10.calculate Pi(qi) for each fj∈Fcby formula(4) to find the lowest fj

11.Pi←Pi(qi)

12.end

13.return Fc, Pi

//Output the candidate fog node set,and minimum cost

3.2.2 资源匹配阶段

算法1为用户找出候选雾节点集合Fc,反之,每一个雾节点都存在候选用户集合。本文在贪心算法[22]的基础上进行改进,提出一种资源匹配算法。将候选用户集合的资源需求按升序排列,每次完成分配后更新雾节点信息。若节点资源不能满足剩余候选用户的需求,停止分配该节点,再分配下一个节点,直到雾节点和用户全都分配完成,得到成功分配的用户集合Uw和雾节点集合Fw,算法结束。资源匹配算法具体流程如算法2所示。

算法2资源匹配算法

输入Fc

输出Uw,Fw

1.for each fj∈Fc

//User resource requirements are sorted in ascending order

2.sort qifor all ui∈U in the ascending order and the list is denoted Fc

3.if dj≥qi

4.Uw=[Uw,m]

//Update the set of users that have been assigned

5.dj=dj-qi;

//Update the amount of resources of the fog node fj

6.Else

7.break

//Processing the next fog node if the user resource //requirement is not met

8.End

9.return Uw, Fw

4 理论分析

本节首先从拍卖机制的经济属性角度进行分析,证明RAFC策略的算法是个人理性、预算平衡的,可以持续地激励三方积极参与拍卖。然后,分析算法的时间复杂度,证明该算法具有可执行性并且可以在有限步骤内实现。

4.1 个人理性分析

定理1本文RAFC策略是个人理性的。

4.2 预算平衡分析

定理2本文RAFC策略是预算平衡的。

4.3 算法的时间复杂度分析

定理3RAFC策略的时间复杂度为多项式时间。

证明RAFC策略分为节点筛选阶段和资源匹配阶段两部分。对于节点筛选阶段,算法1中第2行～第8行的时间复杂度为O(mn),第9行～第11行的循环时间复杂度为O(m)。因此,算法1的时间复杂度为O(mn)+O(m),即算法1的时间复杂度为多项式时间。对于资源匹配阶段,算法2中第1行～第8行的时间复杂度为O(|Fc|),第2行排序算法的时间复杂度为O(mlogam)。因此,算法2的时间复杂度为O(m|Fc|logam),即算法2的时间复杂度为多项式时间。综上,本文RAFC策略的时间复杂度为多项式时间。

5 数值结果分析

5.1 参数设定

本文采用MATLAB仿真平台验证RAFC策略的可行性,将CRB数量定义为VFC网络资源的单位。首先,定义所需的基本仿真参数。假设雾节点有5个～40个,用户数目有10个～150个。用户的资源需求量在2～12之间随机选取,雾节点的资源量根据用户资源需求量和用户数目在10～200之间随机选取。雾节点单位资源报价在1～10之间随机选取,用户的最大允许时延在0.1 s～0.3 s之间随机选取。

实验性能指标包括运行时间、匹配成功率、开销成本、社会效用4个方面,通过50次实验比较得到平均结果。同时,为验证RAFC策略的性能,将该策略与随机匹配法进行比较,随机匹配法随机分配用户,若满足用户需求即完成匹配。

5.2 仿真结果分析

当雾节点数目和空闲资源一定时,用户请求越多,方案的运行时间越长,开销成本越高,匹配成功率越低。当请求数目一定时,雾节点的个数越多,匹配成功率越高。

图3所示为雾节点数目等于10时2种方法的运行时间随用户数目的变化曲线。从图3可以看出,随着用户数目的增加,2种方法的运行时间逐渐上升。当用户数目相同时,由于RAFC策略需要对用户的资源需求进行重新排序,更新雾节点信息,因此其运行时间高于随机匹配法,但2种方法的运行时间相差不大,且RAFC策略的运行时间结果表明其可以快速实现。

图3 2种方法的运行时间对比

图4所示为用户数目等于60时匹配成功率随雾节点数目的变化曲线。从图4可以看出,随着雾节点数目的增加,匹配成功率逐渐升高。当雾节点数目少于15个时,RAFC策略的匹配成功率明显高于随机匹配法。但当雾节点个数多于15个时,随着雾节点个数的增加,2种方法的匹配成功率相差不大,且都可以稳定在较高的值。当用户数目恒定时,与随机匹配法相比,RAFC策略可以提高匹配成功率。

图4 匹配成功率1

图5所示为雾节点数目等于10时匹配成功率随用户数目的变化曲线。从图5可以看出,随着用户数目的增加,匹配成功率逐渐降低。当用户数目相同时,RAFC策略的匹配成功率高于随机匹配方法。当用户数目少于70个时,2种方法的匹配成功率相差不大,但用户数目大于70个时,匹配成功率出现较大变化,且当用户数目为80个时,两者差距最大,其后差距逐渐趋于稳定。由于RAFC策略的资源匹配阶段采用了贪心策略,可以更快速地找到用户匹配的局部最优解。当雾节点数目恒定时,与随机匹配法相比,RAFC策略可以提高匹配成功率。

图5 匹配成功率2

图6所示为雾节点数目等于10时用户的开销成本随用户数目的变化曲线。从图6可以看出,随着用户数目的增加,开销成本逐渐增加。当用户数目相同时,随机匹配法产生的开销成本高于RAFC策略,原因是RAFC策略考虑了用户的最低成本需求且使用了贪心策略。当雾节点数目恒定时,与随机匹配法相比,RAFC策略可以降低开销成本。

图6 2种方法的开销成本对比

社会效用是指成功分配的用户、雾节点及第三方平台的三方收益总和。图7所示为雾节点数目等于10时社会效用随用户数目的变化曲线。从图7可以看出,随着用户数目的增加,社会效用逐渐增加。当用户数目相同时,RAFC策略的社会效用高于随机匹配法。RAFC策略结合了反向拍卖原理,激励三方积极参与分配,且不损害三方的收益。当雾节点数目恒定时,与随机匹配法相比,RAFC策略可以提高社会效用。

图7 社会效用1

图8所示为用户数目等于60时社会效用随雾节点数目的变化曲线。从图8可以看出,随着雾节点数目的增加,社会效用逐渐降低。当雾节点数目相同时,RAFC策略的社会效用高于随机匹配法。当用户数目恒定时,与随机匹配法相比,RAFC策略可以提高社会效用。

图8 社会效用2

6 结束语

本文研究VFC停车分配问题,提出一种基于反向拍卖的VFC停车辅助分配策略RAFC。该策略根据用户需求和智能车辆的资源量来制定分配方案,激励用户、雾节点和第三方平台积极参与拍卖。理论分析和实验结果表明,RAFC策略在保证个人理性和预算平衡的基础上,可以提高用户匹配成功率,降低用户开销成本,提高社会效用。雾计算的网络资源分配可广泛应用于智能交通、智慧医疗、智能电网等新兴领域,本文仅考虑车辆雾计算环境下的智能停车辅助问题,在实际应用中,需求具有多样性,因此,下一步将研究当用户有多种资源需求和时延要求时,如何利用车辆雾节点的计算、存储等资源来制定更加高效的分配策略。