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={u₁, u₂, …, u_m}、充当雾节点的智能车辆F={f₁, f₂, …, f_n}以及第三方平台物联网提供商三部分组成^[20]。其中, 用户作为买方, 提交时延要求、资源需求, 雾节点作为卖方, 提供资源服务, 第三方平台担任拍卖代理, 负责接收信息和协调分配。本文假设各用户相互独立, 一个用户请求最多只能迁移至一个雾节点完成, 但一个雾节点可以接收处理多个请求。

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

2.2 问题建模

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

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

RAFC策略的目标包括:

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

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

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

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

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

2.3 效用函数 2.3.1 用户的效用函数

用户u_i的效用函数T_i^U由资源收益U_i(q_i)和开销成本P_i(q_i)构成:

$ T_i^U = {U_i}({q_i}) - {P_i}({q_i}) $

(1)

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

$ {U_i}({q_i}) = a{\kern 1pt} {\kern 1pt} {\rm{lb}} (1 + {q_i}) $

(2)

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

$ a = 1 + \frac{1}{{{\rm{exp}}( - d_i^j/{D_i})}} $

(3)

其中, D_i表示u_i的时延要求, 即最大允许时延阈值。d_i^j表示u_i到雾节点f_j的实际时延值。

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

$ {P_i}({q_i}) = p_i^d \cdot {q_i} + {L_{ij}} \cdot R_j^f + G_i^u $

(4)

其中, p_i^d表示u_i支付的实际资源成交单价, L_ij表示由u_i到f_j经过的节点数, R_j^f表示u_i支付给途经雾节点f_j的转发费用, G_i^u表示u_i需支付的代理费。

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

2.3.2 雾节点的效用函数

雾节点f_j的效用函数T_j^F由可获得的收益与支出成本组成:

$ T_j^F({q_i}) = p_i^d \cdot {q_i} + R_j^f - {c_j} \cdot {q_i} - S_j^f - G_j^f $

(5)

其中, p_i^d·q_i表示f_j为u_i提供资源服务的资源收益, R_j^f表示f_j提供转发服务的报酬, c_j表示f_j单位资源的成本价格, S_j^f表示f_j提供转发服务的成本, G_j^f表示f_j支付给第三方平台的代理费。

为激励雾节点积极参与分配并提供转发和资源服务, f_j提供转发服务的收益应满足R_j^f>S_j^f, f_j的资源收益应满足p_i^d·q_i>c_j·q_i+G_j^f。

2.3.3 第三方平台的效用函数

第三方平台为用户u_i和雾节点f_j提供分配服务的效用函数T^I, 由平台可获得的代理费G_i^u+G_j^f和提供分配服务的支出成本S_I组成:

$ {T^I} = G_i^u + G_j^f - {S_I} $

(6)

3 RAFC策略 3.1 目标函数

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

$ {\rm{max}}\left( {\sum\limits_{i = 1}^m {\sum\limits_{j = 1}^n {{x_{ij}}} } } \right) $

(7)

$ {\rm{min}}\sum\limits_{i = 1}^m {{P_i}} ({q_i}) $

(8)

$ \begin{array}{*{20}{l}} {{\rm{s}}{\rm{.}}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\rm{t}}{\rm{. }}}\\ {{x_{ij}} \in \{ 0,1\} } \end{array} $

(9)

$ \sum\limits_{i = 1}^m {\sum\limits_{j = 1}^n {{x_{ij}}} } \cdot {q_i} \le \sum\limits_{j = 1}^n {{d_j}} $

(10)

$ \sum\limits_{i = 1}^m {\sum\limits_{j = 1}^n {{x_{ij}}} } \le \sum\limits_{i = 1}^m | {Q_i}| $

(11)

$ {{U_i}({q_i}) > {P_i}({q_i})} $

(12)

$ {R_j^f > S_j^f} $

(13)

$ {p_i^d \cdot {q_i} > {c_j} \cdot {q_i} + G_j^f({f_j} \in F{\kern 1pt} {\kern 1pt} {\rm{且}}{\kern 1pt} {\kern 1pt} {x_{ij}} = 1)} $

(14)

$ {G_i^u + G_j^f > {S_I}} $

(15)

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

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

$ {\rm{min}}\left\{ {\alpha \left( {\sum\limits_{i = 1}^m {\sum\limits_{ij = 1}^n {(1 - {x_{ij}})} } } \right) + \beta \sum\limits_{i = 1}^m {\frac{{{P_i}({q_i})}}{{\overline {{P^d}} }}} } \right\} $

(16)

其中, $\overline {{P^d}} = \sum\limits_{i = 1}^m {\sum\limits_{j = 1}^n {\left( {{x_{ij}} \cdot P_i^d} \right)} } /\sum\limits_{i = 1}^m {\sum\limits_{j = 1}^n {{x_{ij}}} } $表示成功分配的用户的成交价格均值, 参数α, β∈(0, 1), 约束条件为式(9)~式(15)。

3.2 RAFC策略设计

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

3.2.1 节点筛选阶段

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

算法1  节点筛选算法

输入  U, F, W

输出  F_c, P_i

1.Initialize: F_c>←Ø;P_i←Ø;int i.j;

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

//requirement

2.for each u_i∈U

3.for each f_j∈F

4.calculate d_i^j for W;

5.if d_i^j≤D_i then

6.F_c←F_c∪{f_j};

7.end

8.end

9.for each u_i∈U

10.calculate P_i(q_i) for each f_j∈F_c by formula(4) to find the lowest f_j

11.P_i←P_i(q_i)

12.end

13.return F_c, P_i

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

3.2.2 资源匹配阶段

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

算法2  资源匹配算法

输入  F_c

输出  U_w, F_w

1.for each f_j∈F_c

//User resource requirements are sorted in ascending order

2.sort q_i for all u_i∈U in the ascending order and the list is denoted F_c

3.if d_j≥q_i

4.U_w=[U_w, m]

//Update the set of users that have been assigned

5.d_j=d_j-q_i;

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

6.Else

7.break

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

8.End

9.return U_w, F_w

4 理论分析

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

4.1 个人理性分析

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

证明  个人理性即所有买方都不愿支付高于成交的价格, 而所有卖方也都不愿以低于报价的回报来提供服务。为激励用户、雾节点积极参与分配, 本文策略应满足个人理性。RAFC策略从算法设计上保证了双方都是理性的。在算法1中, 当用户u_i分配给雾节点f_j时, 由于用户u_i的最低成本需求限制, 用户u_i不愿意支付比雾节点f_j的报价A_j更高的成交价格, 否则会增加用户u_i的开销成本, 导致分配失败。同时, 雾节点f_j也不愿意以低于报价A_j的价格提供服务, 这样会降低雾节点的资源收益, 进而降低雾节点效用, 导致分配失败, 故最终成交价格满足p_i^d=A_j。同时, 由3.1节可得RAFC策略保证了用户效用T_i^U>0, 雾节点效用T_j^F>0。综上, 对于u_i和f_j而言, 本文RAFC策略是个人理性的。同理可证, 对任意u_i∈U_w, f_j∈F_w, 本文RAFC策略是个人理性的。

4.2 预算平衡分析

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

证明  拍卖代理需要维护服务, 因此, 要保证从买方收取的金额不能小于支付给卖方的金额, 故第三方平台提供分配服务时向用户和雾节点收取一定的代理费用。对于任意u_i∈U_w, f_j∈F_w, 第三方平台从用户u_i收取的金额为p_i^j·q_i+L_ij·R_j^f+G_i^u, 其中, p_i^j·q_i支付给提供资源服务的雾节点, L_ij·R_j^f支付给提供转发服务的雾节点, G_i^u是用户支付给第三方平台的代理费, 故满足从买方收取金额大于支付给卖方的金额, 即p_i^j·q_i+L_ij·R_j^f+G_i^u>p_i^j·q_i+L_ij·R_j^f。同时, 第三方平台向雾节点f_j收取代理费G_j^f。由式(6)、式(15)可得, RAFC策略保证了第三方平台的效用T^I>0。因此, 本文RAFC策略是预算平衡的。

4.3 算法的时间复杂度分析

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

证明  RAFC策略分为节点筛选阶段和资源匹配阶段两部分。对于节点筛选阶段, 算法1中第2行~第8行的时间复杂度为O(mn), 第9行~第11行的循环时间复杂度为O(m)。因此, 算法1的时间复杂度为O(mn)+O(m), 即算法1的时间复杂度为多项式时间。对于资源匹配阶段, 算法2中第1行~第8行的时间复杂度为O(|F_c|), 第2行排序算法的时间复杂度为O(mlog_am)。因此, 算法2的时间复杂度为O(m|F_c|log_am), 即算法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策略的运行时间结果表明其可以快速实现。

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

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

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

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

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

6 结束语

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