近年来，随着5G/6G通信技术和传感器技术的快速发展，智慧城市已进入智能万物互联时代^[1-3]. 目前，移动群智感知（mobile crowdsensing，MCS）已经应用于智慧城市建设^[4-5]. 相较于传统传感器网络，MCS具有数据采集成本低、设备维护方便、系统架构可扩展等优点^[6]. 此外，泛在移动的车辆在智慧城市中发挥了重要作用. 随着网络化、智能化的发展，智能车辆已从一种便捷的交通工具转变为强大的移动感知、计算和存储平台^[7]. 因此，车辆群智感知（vehicular crowdsensing，VCS）为智慧城市的发展带来了更多可能性. 具体来说，车辆作为VCS中的基本感知单元，通过支持车联网服务，可实现城市道路交通场景中人、车、环境的协同^[8-9]. 同时，由于车辆具有移动性、操作灵活等特点，可支持智慧城市中大规模的自然和社会感知需求，这对于智慧城市的运作与发展都至关重要^[10-11].

在VCS中，根据车辆参与感知任务的方式，可将车辆分为机会型车辆和参与型车辆^[12]. 其中，机会型车辆依赖其日常的行驶路径执行感知任务，因此无法改变其行驶路线；相反，参与型车辆可按需改变行驶路线，从而可主动前往指定地点执行感知任务^[13]. 图1显示了2种类型车辆的示意图. 其中，机会型车辆不会改变其原始轨迹，仅完成处于其途经既定行驶轨迹上分配的感知任务. 例如，公交车等公共车辆可被视为城市场景中的机会型车辆. 一般来说，公共车辆因具有既定行程路线，其路线不可更改. 然而，由于机会型车辆的固定路线的范围有限，可能导致任务覆盖率不足. 因此，参与型车辆的出现弥补了机会型车辆的部分不足. 这里，作为感知实体的参与型车辆，一般可视为是处于空闲状态的出租车或私家车. 由于此类车辆没有既定行驶轨迹，因此可根据感知任务的位置，主动改变其轨迹来完成任务. 与机会型车辆相比，除通过完成感知任务获得报酬奖励外，参与型车辆也可获得因完成该任务产生的相应绕行报酬奖励. 值得注意的是，参与型车辆可能会因被分配到较远距离的感知任务，从而要求高额报酬奖励，或将不可避免地增加平台运营开销.

图  1  机会型车辆和参与型车辆感知示意图

Figure  1.  Illustration of opportunistic and participatory vehicles sensing

下载: 全尺寸图片 幻灯片

通常，执行感知任务需要花费额外的时间或经济成本^[14]. 由于大多数车辆具备自私和理性特征，在缺乏奖励报酬的情况下，驱动其执行感知任务往往不可行^[15]. 因此，需设计适当的奖励机制，以激励车辆参与感知任务. 这里，激励机制主要从经济学角度引入，并逐渐应用于群智感知^[16]. 目前，常用的方法包括拍卖理论、博弈论、契约论等. 此外，由于参与型车辆没有既定行驶轨迹，其需平台统一决策以确定其轨迹，而深度强化学习方法（deep reinforcement learning，DRL）可通过与环境交互，为参与型车辆提供最优决策，并且可适应大规模复杂场景^[17-19].

本文将以挖掘2种类型感知车辆的不同移动特性为出发点，分别研究这2种类型车辆面向城市感知场景中的实际问题，即机会型车辆选择问题和参与型车辆调度问题. 具体来说，群智感知平台（crowd sensing platform，CSP）管理1组机会型车辆和1组参与型车辆，通过选择最优的机会型车辆、调度参与型车辆的行驶轨迹，分别完成感知任务.

本文通过选定矩形目标区域，并将其划分为大小相同的子区域网格，车辆经过该区域网格，即代表完成1次感知任务. 此外，本文通过引入感知公平性指数，以保证感知区域均衡性，即不同子区域网格内感知任务完成次数的均衡性. 为解决所提问题，针对机会型感知车辆，本文应用基于反向拍卖的激励方法，通过选择最优的获胜机会型车辆集合完成感知任务，并设计了相应的报酬支付算法；针对参与型感知车辆，则应用基于深度确定性策略梯度(deep deterministic policy gradient，DDPG )的方法指导CSP决策，以确定参与型车辆行驶轨迹，同时完成相应的感知任务. 本文所提2种方法分别应用于2种类型车辆的感知场景，并可与2种类型车辆的移动特性相匹配，其目的都是在完成感知任务的同时最小化CSP开销.

本文的主要贡献包括3个方面：

1）针对车辆群智感知场景，本文引入CSP对机会型车辆和参与型车辆进行统一管理. 根据机会型车辆和参与型车辆的移动特性，本文分别考虑了机会型车辆选择问题和参与型车辆调度问题.

2）为了解决上述问题，本文分别提出基于反向拍卖的机会型车辆选择方法和基于DDPG的参与型车辆调度方法. 这2种方法可与2种类型车辆的移动特性相匹配，并有效完成感知任务.

3）此外，本文考虑感知公平性，以确保不同感知子区域内感知任务完成的均衡性，并在CSP的开销中引入公平性指数. 本文的目标是在2种车辆感知的场景下，都能最小化CSP的开销.

1.   相关工作

本节回顾了与车辆群智感知相关的现有工作.

1.1   车辆群智感知

近年来，众多研究已考虑车辆群智感知中的车辆招募和选择问题. Hu等人^[20]提出了一项基于可变持续时间的车辆招募方法. 在预算有限的情况下，通过考虑车辆不确定性轨迹确定所选车辆和提供服务时长，后续设计了2阶段招募算法以最大限度利用感知资源. 文献 [21]通过考虑声誉和车辆轨迹，提出了一项基于贪心的启发式实时车辆选择算法，通过声誉评估和服务定价设计车辆招募计划，在降低成本的同时最大化感知覆盖范围.

此外，部分研究聚焦车辆路径规划和选择问题. Lai 等人^[11]研究了包括车辆招募、候选路径分析和路径选择在内的问题. 根据历史车辆轨迹信息分析车辆偏好和兴趣，用于选择最优车辆. 然后，利用最小干扰感知策略提出最大加权路径检测问题，以选择车辆行程中断最少且效益最大的路径. Wang等人^[22]通过向车辆推荐多条候选路线（每条路线涵盖不同的感知任务），以驱动车辆最低成本路线的选择. 由于所有车辆共享平台的任务奖励，每辆车的选择策略不可避免地会产生竞争. 因此，将群体选择策略问题建模为多车辆感知博弈模型，通过分析车辆之间的交互，提出了一项分布式路径选择方法以解决此问题.

1.2   基于反向拍卖的激励机制

鉴于车辆的个体合理性和自私性，在没有奖励的情况下，很难主动完成感知任务. 因此，需引入激励机制以促使车辆完成感知任务，例如博弈论、拍卖理论、契约理论等，而反向拍卖则是其中一种可行的方法.

近年来，车辆群智感知研究已应用了反向拍卖方法. Fan等人^[23]提出了一项称为Hector的方法，用于车辆感知网络的联合轨迹调度和激励机制. 其中，车辆轨迹被映射到时空约束集合中，以降低问题解决的复杂性. 同时，设计了基于反向拍卖的激励机制，以激励车辆通过绕行实现更广的任务覆盖范围. Gao等人^[24]研究了基于车辆非确定性的激励机制，通过建立关联平台和车辆间的反向拍卖模型以激励车辆参与感知任务. 此外，还考虑了车辆的感知数据质量，提出了相应的获胜者选择方法和支付确定方法. Chen等人^[25]提出了一项基于时效性的激励机制，建立了服务请求者和车辆间的反向拍卖模型，通过将拍卖问题转化为非单调子模块最大化问题，实现预算约束下的请求者的效用提升.

1.3   深度强化学习

随着车辆群智感知系统的不断发展，需采用新的技术和方法以解决系统规模和复杂性不断增长带来的挑战. 由于DRL方法通过将优化问题建模为马尔可夫决策过程（Markov decision processes，MDP），并基于智能体与环境交互的不断迭代获得最优决策，因此在解决复杂和动态问题方面展现了独特优势. Zhao等人^[26]研究了非合作车辆感知方法，以动态确定感知任务的单位完成成本，通过车辆社交属性激励相关车辆参与感知任务. 为了保障决策的长期最优性，Xu等人^[27]结合生成对抗网络和DRL以解决感知任务分配问题，并根据环境灵活自适应调整动作. 这里，该文作者集成生成对抗网络到DRL训练过程，并在训练阶段应用双深度Q学习方法，以确保感知决策阶段的最优策略.

随着车辆的智能化发展，近期研究还考虑了分布式感知场景，车辆也可充当决策智能体. Ding等人^[28]提出一项基于图卷积协作的多智能体强化学习方法GCC-MARL，辅助出租车进行分布式决策和全局目标的协同优化. 其中，每辆车充当代理，通过引入信任分配方式以促进车辆间合作，同时结合图卷积网络收集复杂道路网络的空间特征指导车辆的决策动作. Liu等人^[29]提出一项分布式多智能体DRL方法，用于节能和分布式无人车辆调度. 该方法将卷积神经网络提取的特征作为演员-评论家网络的输入，生成实时动作并引导无人车辆的轨迹. 此外，使用长短期记忆网络和分布式优先经验回放以实现更优探索策略，通过该方式降低了无人车辆执行感知任务能耗.

1.4   动　机

当前工作主要从单一车辆类型方面进行考虑，未根据机会型车辆和参与型车辆的移动特性进行比较. 因此，本文则以2种类型感知车辆的不同移动特性为出发点，分别研究2种类型车辆在城市感知场景中的实际问题，即机会型车辆选择问题和参与型车辆调度问题. 然后针对这2种问题，根据车辆的移动特性匹配相应的解决方法. 具体来说，本文首先提出了基于反向拍卖的激励机制解决机会型车辆选择问题；然后提出基于DDPG的方法解决参与型车辆调度问题. 此外，根据本文模型特性，首次在车辆群智感知场景引入感知公平性指数以保证不同子区域感知任务完成的均衡性. 本文的目标则是在2种类型车辆的感知场景下都能最小化CSP的开销.

2.   系统模型

本节主要介绍2种类型车辆的基本定义，然后给出相应的问题表述，并提出本文的优化目标.

2.1   模型定义

本文考虑1组机会型车辆、1组参与型车辆和CSP共同存在的场景. 其中，CSP负责发布1组感知任务，并管理和调度以上2种类型的车辆分别完成感知任务. 本文根据2种类型车辆的移动特性，分别提出了不同的问题，并选择不同的方法以匹配所提问题. 具体来说，针对机会型车辆，由于其轨迹无法更改，本文提出机会型车辆选择问题，并设计基于反向拍卖的激励机制解决此问题. 针对参与型车辆，由于其轨迹可以更改，本文提出参与型车辆调度问题，并设计基于DRL的方法调度车辆轨迹解决此问题.

假设在矩形目标区域内，存在M辆机会型车辆，表示为$U=\left\{{u}_{1},{u}_{2},… ,{u}_{M}\right\}$；存在N辆参与型车辆，表示为$V=\left\{{v}_{1},{v}_{2},… ,{v}_{N}\right\}$，2种类型的车辆都需通过CSP进行调度与决策. 此外，本文将矩形目标区域划分为一组大小相同的子区域网格，用$\mathcal{L}=\left\{\mathrm{1,2},… ,L\right\}$表示子区域网格的序号.

本文中，感知任务被定义为特定时间段内，于目标区域中收集的特定数据，如图像或视频. 为简化表述，每个子区域内都存在1个感知任务，当任一车辆经过当前子区域，则视为完成1次感知任务. 对于每个子区域内的感知任务，规定车辆收集不超过$\eta$次数据，即每个子区域的感知次数不能超过$\eta$次. 此外，设CSP执行感知任务的总预算为B，即需确保车辆执行感知任务的开销小于B.

定义整个感知窗口为时间$D$，每个感知任务在时间$D$内均有效，车辆只有在时间范围内到达才能完成感知任务. 本文假设时间窗口为$\left[0,D\right]$，同时时间也可离散化为$T$个时隙，表示为$\left\{\mathrm{1,2},… ,t,… ,T\right\}$. 在机会型感知场景中，平台以离线方式决策，机会型车辆执行任务，因此不考虑时隙划分；在参与型感知场景中，则需划分时隙为每个参与型车辆进行实时决策.

2.2   机会型车辆模型

对于机会型车辆${u}_{m}\in U$，其候选轨迹表示为${r}_{m}$. 为简单起见，假设车辆只要到达该子区域网格，即可完成1次感知任务. 本文定义候选轨迹${r}_{m}$经过的网格数为$s_m^h$，表示车辆${u}_{m}$的候选轨迹${r}_{m}$可完成的任务数. 本文将车辆${u}_{m}$执行1次感知任务的成本定义为${c}_{m}^{l}$，这包括了电池、存储、CPU等各种开销. 对于机会型车辆${u}_{m}$，其被选中执行感知任务而产生的成本可表示为

同时，我们定义二元变量${x}_{m}=\left\{\mathrm{0,1}\right\}$表示机会型车辆${u}_{m}$是否被CSP选中执行感知任务，其中${x}_{m}=1$表示机会型车辆${u}_{m}$被选中执行感知任务，反之${x}_{m}=0$则表示未被选中.

2.3   反向拍卖模型

由于机会型车辆具备自私和理性特征，在没有激励情况下难以主动完成感知任务，因此本文引入基于反向拍卖的激励机制. 如图2所示，在机会型车辆选择过程中，CSP基于反向拍卖的激励机制以选择获胜车辆，并支付相应的报酬.

图  2  基于反向拍卖的机会型车辆选择图

Figure  2.  Illustration of reverse auction-based for opportunistic vehicles selection

下载: 全尺寸图片 幻灯片

具体工作流程为

1）CSP向机会型车辆候选集合$U$宣布拍卖开始.

2）CSP和机会型车辆进入拍卖阶段. 在拍卖阶段，CSP扮演拍卖人角色，机会型车辆扮演竞拍人角色. 每个机会型车辆${u}_{m}$报告其投标价格${b}_{m}$至CSP，声称其执行感知任务的单位开销（注意${b}_{m}\ge {c}_{m}^{l}$，这意味着机会型车辆${u}_{m}$的投标价格${b}_{m}$不低于其执行感知任务的实际单位成本${c}_{m}^{l}$）.

3）根据机会型车辆的出价集合，CSP将决定获胜车辆集合${U'}\in U$，并依据获胜车辆轨迹完成相应的感知任务.

4）当机会型车辆完成感知任务后，CSP对所有获胜车辆执行付款，表示为${q}_{m}$. 如车辆未完成任何感知任务，则无法获得任何报酬.

根据上述工作流程，CSP通过反向拍卖选择获胜机会型车辆集合，向其支付相应的报酬. 同时，CSP需将支付的报酬控制在合理预算范围内，以保证系统长期激励的有效性. 此外，本文所提基于反向拍卖的方法还需具备2个属性：

1）个体合理性. 每个获胜车辆都存在非负效用，即机会型车辆完成感知任务获得的报酬不低于其执行任务的实际成本${c}_{m}^{l}$.

2）真实性. 对于每个获胜车辆，其真实性表示为只有按真实成本出价才可获得最大利润，不能通过恶意提高出价以增加自身利润. 因此，机会型车辆需将其投标价格设置为其执行任务的真实成本. 后文将证明此定理.

2.4   参与型车辆模型

由于参与型车辆没有既定行驶轨迹，因此可通过CSP调度前往目标子区域完成感知任务，本文将采用基于DDPG的方法确定参与型车辆的行驶路线. 如图3所示，参与型车辆位于不同子区域网格，每个时隙内CSP将决定参与型车辆${v}_{n}$的动作，即下一时隙应处于的子网格区域. 这里，本文定义参与型车辆${v}_{n}$在时隙$t$的动作为${a}_{n}^{t}=\left\{\mathrm{0,1},\mathrm{2,3},4\right\}$，表明CSP在时隙$t$控制参与型车辆${v}_{n}$从当前子区域水平移动到相邻子区域（1=“前进”，2=“后退”，3=“左转”，4=“右转”)，或“停滞”$\left({a}_{n}^{t}=0\right)$在当前子区域内.

图  3  基于 DRL 的参与型车辆调度示意图

Figure  3.  Illustration of DRL-based for participatory vehicles scheduling

下载: 全尺寸图片 幻灯片

对于参与型车辆${v}_{n}$，除考虑其固定的执行感知任务的单位成本${c}_{n}^{l}$，还需考虑其绕行所产生的额外距离成本. 给定单位绕行成本为$c\mathrm{_d}$，则参与型车辆所生的距离成本可表示为$c\mathrm{_d}\left(Dis_n-D_n^{\mathrm{m}\mathrm{a}\mathrm{x}}\right)$，其中$Di{s}_{n}$为车辆${v}_{n}$实际行驶距离，用曼哈顿距离计算. ${D}_{n}^{\mathrm{m}\mathrm{a}\mathrm{x}}$表示车辆${v}_{n}$的计划行驶轨迹距离，如在计划行驶距离内，则CSP不需支付距离成本，超过计划距离，CSP则需支付给参与型车辆${v}_{n}$相应的距离成本. 此外，本文规定参与型车辆${v}_{n}$执行的感知任务数量$count\left({v}_{n}\right)$不能超过${g}_{n}$.

针对参与型车辆${v}_{n}$，其执行感知任务的总成本可表示为

其中等号右边第1项为参与型车辆执行感知任务的成本，${c}_{n}^{l}$为执行任务的单位成本，${h}_{n}$为车辆当前感知的次数. 第2项为执行感知任务所支付的距离成本，${c}_{{\mathrm{d}}}$为单位距离成本.

2.5   问题表述

CSP分别选择1组机会型车辆和调度1组参与型车辆执行感知任务，目标是最小化CSP开销.

首先，定义CSP支付给机会型车辆${u}_{m}$的报酬为

式（3）中$P_m$表示机会型车辆${u}_{m}$执行1次感知任务的出价乘以完成感知任务的次数.

由于机会型车辆需参与反向拍卖过程，CSP向所有机会型车辆支付的报酬为

其中${x}_{m}$判断该车辆是否被CSP选中为获胜车辆，CSP仅向被选中的获胜车辆支付相应的报酬.

参与型车辆由CSP进行调度，以完成目标子区域的感知任务. 根据式（2），可得CSP向所有参与型车辆支付的报酬为

此外，本文通过引入感知公平性定义，以确保不同子区域的感知公平性. 由于目标区域被划分为多个子区域网格，且每个子区域网格内可执行多次感知任务，因此需考虑感知子区域的公平性. 这里，CSP需保证各子区域网格之间的感知任务完成次数的平等性，避免出现部分子区域感知密度不均问题. 因此，本文提出感知公平指数$Fair\_Index\left(U_L\right)$以反映感知公平性.

基于Jain公平指数^[30-31]，根据机会型车辆完成感知任务后的状态，本文定义$coun{t}_{l}^{u}$为所有机会型车辆在子区域网格$l$内的感知总次数. 因此，针对机会型车辆，定义感知公平指数为

可知$Fair\_Index\left({U}_{L}\right)\in \left[\mathrm{0,1}\right]$，当$Fair\_Index\left({U}_{L}\right)$越接近于1时，代表公平性越好.

同样，针对参与型车辆，定义$coun{t}_{l}^{v}$为所有参与型车辆在子区域网格$l$内的感知总次数. 因此，可定义参与型车辆的感知公平指数为

综上，结合感知公平指数，本文重新定义CSP的开销. 因此，针对机会型车辆，CSP的开销定义为

针对参与型车辆，CSP的开销定义为

为降低自身的开销，CSP会选择成本低的机会型车辆参与感知任务，同时尽可能保证感知覆盖的公平性.

2.6   优化问题定义

本文优化目标是在保证感知公平性的前提下，提升感知覆盖范围以最小化CSP开销. 因此，针对机会型车辆选择问题，给定优化目标为

其中式（10-2）表示机会型车辆是否被选中的二元变量，式（10-3）表示每个子区域网格的感知次数限制，式（10-4）表示机会型车辆的成本限制，即不能超过CSP的预算$B$.

针对参与型车辆调度问题，给定优化目标为

其中式（11-2）表示参与型车辆${v}_{n}$执行的感知任务数量不能超过${g}_{n}$，式（11-3）表示每个子区域网格的感知次数限制，式（11-4）表示支付给参与型车辆的报酬限制，即不能超过CSP的预算$B$.

由于本文所提出的2个优化问题都为NP-Hard问题，从而可将该优化问题的特殊情况转化为对应的最小加权集覆盖（MWSC）问题来证明，此处省略具体证明过程.

3.   机会型车辆选择问题求解

针对机会型车辆的选择问题，本节提出基于反向拍卖的激励机制，包括获胜车辆选择和报酬支付2个步骤. 此外，本节还证明了该方法保证了机会型车辆的个体合理性和真实性.

3.1   获胜车辆选择

在反向拍卖过程中，机会型车辆作为投标人，CSP作为竞拍人. 由于选择获胜车辆执行感知任务为NP-Hard，本文提出一种近似方法为CSP选择获胜车辆集合. 本文所提机会型车辆获胜选择算法(winner selection algorithm，WSA)主要依靠贪婪思想选取使CSP开销最低的$\left|{M'}\right|$辆车的集合${U'}$，具体过程如下所述.

首先，初始化机会型车辆获胜集合. 通过式（1）计算候选机会型车辆集合中所有车辆的任务完成成本${C}_{m}$，按递增顺序排序并将新候选车辆集合表示为${U}^{N}={\{u}_{1},{u}_{2},…, {u}_{m},… ,{u}_{{M'}},{u}_{{M'}+1},… ,{u}_{{m'}}$,…,${u}_{M}\}$. 然后，在新候选车辆集合${U}^{N}$中选择前$\left|{M'}\right|$辆为初始获胜车辆集合$U'_{0}={\{u}_{1},{u}_{2},… ,{u}_{m},… ,{u}_{{M'}}\}$，并计算初始的CSP开销${C}_{\mathrm{P}}\left({U}_{0}\right)$.

接下来，进入迭代更新过程，此处共包含2层循环过程. 在外层循环中，从车辆${u}_{{M'}+1}$开始至车辆${u}_{M}$，即针对$\{{u}_{{M'}+1},{u}_{{M'}},… ,{u}_{{m'}}$,…,${u}_{M}\}$中的每一辆车有如下内循环过程：依次从后向前替代集合$U'_{0}$中的每一辆车，即$\left\{{u}_{{M'}},{u}_{{M'}-1},… ,{u}_{m},… ,{u}_{1}\right\}$. 具体地，在内层循环中，以车辆${u}_{{M'}+1}$为例，用车辆${u}_{{M'}+1}$替代集合${U'}$中的每一辆车，并根据每辆车的出价，通过式（8）计算车辆${u}_{{M'}+1}$替换对应车辆${u}_{m}$后CSP相应的开销${C}_{\mathrm{P}}\left({U}_{{m'}}\right)$.

此时，我们定义

式（12）表示车辆${u}_{{M'}+1}$通过替代初始获胜车辆集合$U'_{0}$中车辆${u}_{m}$带来的CSP开销变化. 针对车辆${u}_{{M'}+1}$，当其将集合$\left\{{u}_{{M'}},{u}_{{M'}-1},… ,{u}_{m},… ,{u}_{1}\right\}$中的车辆替换1个轮次后，产生集合$\Delta U\left(M\right)=\left\{\Delta {U}_{1},\Delta {U}_{2},… ,\Delta {U}_{{M'}}\right\}$，若存在任意一个$\Delta U < 0$，则说明新加入的车辆与原车辆相比降低了CSP的开销，故此时用车辆${u}_{{M'}+1}$代替集合$\Delta U\left(M\right)$中对应数值最小的车辆. 上述过程即为一个轮次的内循环过程.

然后，对车辆${u}_{{M'}+2}$~${u}_{M}$，重复上述内循环过程. 待内循环结束，最终保留在集合${U'}$内的$\left|{M'}\right|$车辆集合即为使CSP开销最小的获胜车辆集合.

注意，在上述过程中，已知子区域网格感知次数和预算受限制，若超出限制，则停止迭代，并将当前车辆删除或终止流程. 具体算法步骤如算法1所示.

算法1. 机会型车辆获胜者选择算法（WSA）.

输入：机会型车辆候选集合${U}_{M}$，预算$B$，车辆${u}_{m}$的任务执行成本${c}_{l}$，车辆${u}_{m}$的候选轨迹可完成的感知任务数量${s}_{m}^{h}$；

输出：获胜者车辆集合${U'}$.

① for each ${u}_{m}\in {U}_{M}$ do

② 计算每辆车的完成感知任务的成本${C}_{m}$；

③ end for

④ 根据成本${C}_{m}$从小到大依次对候选车辆进行排 序，得到初始化候选车辆集合${U}^{N}={\{u}_{1},{u}_{2},… ,$ ${u}_{{M'}},{u}_{{M'}+1},… ,{u}_{M}\}$；

⑤ 在新候选集合中，选取前$\left|{M'}\right|$辆车作为初始获 胜者集合$U'_{0}$，并根据式（8）计算初始的CSP 开销${C}_{\mathrm{P}}\left({U}_{0}\right)$；

⑥ for each ${u}_{{m'}}\in \left\{{u}_{{M'}+1},{u}_{{M'}},… ,{u}_{M}\right\}\mathrm{d}\mathrm{o}$

⑦ for each ${u}_{m}\in \left\{{u}_{{M'}},{u}_{{M'}-1},… ,{u}_{1}\right\}$ do

⑧ 依次替代初始候选车辆集合${U}^{N}$中前$\left|{u}_{{M'}}\right|$ 辆车，即$\left\{{u}_{{M'}},{u}_{{M'}-1},… ,{u}_{1}\right\}$；

⑨ 计算${u}_{{m'}}$代替${u}_{m}$后对应的${C}_{\mathrm{P}}\left({U}_{{m'}}\right)$，并得到 $\Delta {U}_{{m'}}={C}_{\mathrm{P}}\left({U}_{{m'}}\right)-{C}_{\mathrm{P}}\left({U}_{0}\right)$；

⑩ 获取集合$\Delta U\left(M\right)=\left\{\Delta {U}_{1},\Delta {U}_{2},… ,\Delta {U}_{{m'}}\right\}$；

⑪ if min $\Delta U\left(M\right) < 0$

⑫ ${u}_{m}\leftarrow \mathop{{\mathrm{arg\;min}}}\limits_{{u}_{{m'}}}\Delta U\left(M\right)$；

⑬ end if

⑭ end for

⑮ end for

⑯ return ${U'}$.

3.2   报酬支付

经获胜车辆选择阶段后，CSP需为获胜的机会型车辆支付相应的报酬. 由于机会型车辆完成感知任务会消耗相应的成本，但CSP在选择机会型车辆时已知其期望报酬. 鉴于机会型车辆的自私和理性特征，一般假设其希望获得更高回报. 为此，必须制定统一的支付规则以保障支付合理性. 这里，参考标准VCG（Vickrey-Clarke-Groves）方案的支付规则，本文所提出的支付规则可鼓励机会型车辆参与感知任务，同时确保车辆的个体合理性和真实性.

标准VCG方案中，投标人提交报价并报告其对任务的估价，而不知其他投标人的出价，为此每个获胜者将支付给其他参与者产生的“机会成本”. 这里，定义投标人S的“机会成本”为在没有投标人S参与情况下的其他投标人的总出价，减去所有其他中标人的出价总和.

本文所提报酬支付算法（payment algorithm，PA）则基于上述方案的思想进行设计. 对于获胜车辆集合${U'}$，首先定义${C}_{\mathrm{P}}^{-m}\left(U\right)$表示在没有机会型车辆${u}_{m}$参与情况下CSP的最小开销. 这里，基于算法$1$可获得在没有机会型车辆${u}_{m}$参与情况下的最优获胜车辆集合，从而计算此时CSP的最优开销为

然后，本文可以得到

其中${p}_{m}$代表车辆${u}_{m}$参与拍卖过程中为CSP带来的开销降低的幅度.

根据机会型车辆${u}_{m}$的出价${b}_{m}$和对应的感知任务完成数量${s}_{m}^{h}$，可得出机会型车辆${u}_{m}$的效率因子${\rho }_{m}$，${\rho }_{m}$根据为CSP带来的开销降低幅度与其需要CSP支付报酬的比值

因此，可确定CSP向获胜车辆${u}_{m}$支付的报酬表示为

从式（16）可以看出，对于获胜车辆${u}_{m}$，CSP将支付大于其成本的报酬，从而提高了机会型车辆参与感知任务的积极性. 对于未被选中的车辆，则不向其支付任何报酬. 此外，本文还需要确保CSP的开销不能超过设置预算. 具体算法流程如算法2所示.

算法2. 机会型车辆报酬支付算法（PA）.

输入：机会型车辆候选集合${U}_{M}$，机会型车辆获胜者集合${U'}$，预算$B$，车辆${u}_{m}$的任务执行成本${c}_{l}$和报价${b}_{m}$，车辆${u}_{m}$轨迹可完成的感知任务数${s}_{m}^{h}$；

输出：向获胜者车辆支付的报酬集合$Q\left(m\right)$.

① for each ${u}_{m}\in {U'}$ do

② 根据算法$1$计算在没有获车辆${u}_{m}$参与的情 况下CSP的获胜车辆集合${U}^{-m}$；

③ 计算当前状态下CSP的最优开销${C}_{\mathrm{P}}^{-m}\left(U\right)$；

④ 计算${p}_{m}={C}_{\mathrm{P}}^{-m}\left(U\right)-{C}_{\mathrm{P}}\left(U\right)$；

⑤ 计算${\rho }_{m}=\dfrac{{p}_{m}}{{b}_{m}{s}_{h}^{m}}$；

⑥ 计算${q}_{m}=\left(1+{\rho }_{m}\right){b}_{m}{s}_{h}^{m}$；

⑦ ${B}^{*}\leftarrow B-{q}_{m}$；

⑧ if ${B}^{*} < 0$

⑨ break；

⑩ end if

⑪ end for

⑫ return $Q\left(m\right)=\left\{{q}_{1},{q}_{2},… ,{q}_{m}\right\}$.

3.3   理论分析

本节证明所提基于反向拍卖的机会型车辆选择方法需满足2个重要属性：个体合理性和真实性. 作为车辆帮助CSP完成感知任务的主要动机，个体合理性属性需保证每个机会型车辆都能获得非负奖励. 此外，真实性属性需保证每个机会型车辆无法从不真实的出价中获得更高的报酬.

定理1. 所提出基于反向拍卖的机会型车辆选择方法符合真实性，即每个机会型车辆需要将出价设置为其成本（${b}_{m}={c}_{m}^{l}$）.

证明. 首先，本文假设获胜车辆集合中的某机会型车辆${u}_{m}$报告不真实出价为$b'_{m}$ ($b'_{m} > {c}_{m}^{l}$). 然后，根据式（1）可得出当前不真实成本$C'_{n}$，由于存在$C'_{n} > {C}_{n}$，进而可根据式（4）得出$C'_{\mathrm{P}1} > {C}_{\mathrm{P}1}$. 通过计算当前CSP开销$C'_{\mathrm{P}}\left(U\right)$，当车辆${u}_{m}$报告不真实出价后，CSP的开销差值可表示为

由（17）可以看出，车辆${u}_{m}$的不真实出价会增加CSP开销.

然后，根据式（14），可得出车辆在不真实出价情况下有$p'_{m}-{p}_{m} < 0$，进而得到式（15）中有$\rho' _{m} < {\rho }_{m}$. 最后，根据式（16）可得出：

综上，可得知车辆${u}_{m}$通过不真实出价并不会为自身带来报酬提升. 因此，表明车辆${u}_{m}$无法通过不真实的投标价格提升自身收益，保证了真实性.证毕.

定理2. 式（16）中定义的支付规则符合个体合理性，即$\forall {u}_{m}\in {U'},{q}_{m}-{c}_{m}\ge 0$.

证明. 根据本文所提支付规则，对于获胜者集合中的任意车辆${u}_{m}$，式（14）恒成立，这意味着式（15）中的${\rho }_{m} > 0$恒成立. 因此，根据式（16）可得出${q}_{m} > {c}_{m}$同样恒成立，从而表明每个获胜车辆都将获得大于自身成本的报酬支付，因此个体合理性得到满足. 证毕.

4.   参与型车辆调度问题求解

本节针对参与型车辆的调度问题，提出基于DDPG的方法求解. 本节首先将优化问题近似为MDP，以最小化CSP开销；然后定义MDP中的状态、动作和奖励函数；最后提出一种基于DDPG的方法以解决该问题.

4.1   状态、动作和奖励函数定义

参与型车辆执行感知任务时，由于其行驶轨迹的不确定性，因此可由CSP作为智能体，对所有参与型车辆进行统一决策和控制. 在此过程中，由于需即时为车辆做出动作决策，因此本文将时间窗口$\left[0,D\right]$离散化为$T$个时隙，并表示为$\left\{\mathrm{1,2},… ,t,… ,T\right\}$. 这里，本文将介绍基于DDPG的参与型车辆调度问题的相关状态空间、动作空间和奖励函数.

1）状态空间（S）. 状态用于表示当前时隙面临的网络环境状况. 相应地，时隙$t$的状态由${s}_{t}$=$\left\{{S}_{1},{S}_{2},{B}_{\mathrm{r}}^{t}\right\}$表示. 其中，${S}_{1}=\left\{lo{c}_{{v}_{1}}^{t},lo{c}_{{v}_{2}}^{t},… ,lo{c}_{{v}_{n}}^{t}\right\}$表示每个参与型车辆${v}_{n}$在时隙$t$的位置索引（即所处子区域网格的位置索引），${S}_{2}=\left\{coun{t}_{1}^{t},coun{t}_{2}^{t},… ,coun{t}_{l}^{t}\right\}$表示在时隙$t$时每个子区域网格的感知次数，${B}_{\mathrm{r}}^{t}$则表示时隙$t$开始时CSP剩余的预算.

2）动作空间（A）. CSP负责确定每个参与型车辆${v}_{n}$的动作策略，即负责调度参与型车辆轨迹以分配相应的感知任务. 时隙$t$的动作由${a}_{t}$=$\{{a}_{1}^{t},{a}_{2}^{t},… ,{a}_{n}^{t},… , {a}_{N}^{t}\}$表示. 其中，${a}_{n}^{t}=\left\{\mathrm{0,1},\mathrm{2,3},4\right\}$，表明CSP在时隙$t$控制参与型车辆${v}_{n}$从当前子区域水平移动到相邻子区域（1=“前进”，2=“后退”，3=“左转”，4=“右转”)，或“停滞”$\left({a}_{n}^{t}=0\right)$在当前子区域内.

3）奖励函数（R）. 本文目标为最小化CSP开销，这与DRL最大累积折扣奖励的目标相反. 因此，需设置目标函数的值与奖励的值负相关. 为了最小化 CSP 的长期开销，即时奖励${r}_{t}$被定义为

4.2   从强化学习到深度强化学习

MDP可用于描述较多决策控制的问题，通常可使用动态规划或线性规划方法解决. 然而，当面对时变且未知的状态和决策时，基于强化学习的方法更适用. 这是因为在强化学习中，智能体在给定的环境中主动学习，并尝试获得更优动作以获得最大累积奖励^[32].

这里，$\mathrm{Q}$学习是一种典型的强化学习方法，可描述为在MDP中获取最优策略的学习行为，它使用$\mathrm{Q}$表进行值迭代. 其中，智能体需计算每个状态-动作对的$\mathrm{Q}$函数结果，并在每次与环境交互后更新和维护$\mathrm{Q}$ 表中的$\mathrm{Q}$值.

由于需要维护$\mathrm{Q}$表，$\mathrm{Q}$学习只能应用于小规模动作空间和状态空间的问题，相较于DRL方法可在不需先验信息的情况下通过神经网络自动提取高维数据特征，因此在解决大规模状态空间问题时具有优势. 综上，本文提出基于DDPG的方法可以解决参与型车辆调度问题.

4.3   基于DDPG的参与型车辆调度方法

该方法主要由2部分组成，即作为$\mathrm{A}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}$的策略网络和作为$\mathrm{C}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{c}$的价值网络. 如图4所示，首先通过给定初始状态，智能体基于初始动作产生新的状态和奖励，并更新$\mathrm{C}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{c}$网络；然后，智能体需根据$\mathrm{C}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{c}$的建议迭代更新$\mathrm{A}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}$网络，在训练出满意的$\mathrm{A}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}$网络前，该迭代会一直持续到最大迭代次数. 对于每次迭代中网络参数的更新，一方面，$\mathrm{C}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{c}$网络与环境交互，更新自身$\mathrm{Q}$网络奖励的参数$w$；另一方面，$\mathrm{C}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{c}$网络需估计当前状态和动作的$\mathrm{Q}$值以指导$\mathrm{A}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}$网络的更新^[33].

图  4  DDPG 结构图

Figure  4.  Illustration of DDPG framework

下载: 全尺寸图片 幻灯片

本文提出了一种基于DDPG的参与型车辆调度算法，以解决所提参与型车辆调度问题. 首先，CSP作为智能体从环境中收集信息以生成初始状态；然后，主$\mathrm{A}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}$网络根据当前状态${s}_{t}$、当前策略$\mu$以及随机噪声序列$N$选择动作${a}_{t}$：

当获得动作${a}_{t}$后，智能体可在每个时隙$t$将其样本传输元组 $\left({s}_{t},{a}_{t},{r}_{t},{s'}\right)$存储到经验回放池中. 同时，基于当前状态和动作，主$\mathrm{C}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{c}$网络可更新价值网络参数$w$并计算当前$\mathrm{Q}$值. 本文根据贝尔曼方程将$\mathrm{Q}$值表示为

然后，$\mathrm{C}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{c}$网络通过构造卷积神经网络以模拟贝尔曼方程求解递归$\mathrm{Q}$函数，并从经验回放池中随机选择一小批样本传输元组更新$\mathrm{C}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{c}$网络. 这里，目标$\mathrm{Q}$值由目标$\mathrm{C}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{c}$网络计算为

为使学习过程稳定并提高算法收敛速度，智能体从经验回放池中随机选择小批量样本传输元组$\left({s}_{t},{a}_{t},{r}_{t},{s'}\right)$以消除耦合时间序列训练数据. 在每次迭代中，本文通过计算${y}_{j}$并将其发送到主$\mathrm{C}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{c}$网络以 将目标$\mathrm{A}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}$网络与目标$\mathrm{C}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{c}$网络结合，并最小化损失函数$L\left(w\right)$，表示为

其中$m$表示样本传输元组的数量.

通过使用价值网络参数 $w$和来自经验回放池的样本元组，主$\mathrm{A}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}$网络使用策略梯度以更新当前策略，可表示为

此外，DDPG使用软更新方法来更新部分参数：

其中$\tau$表示更新参数.

基于 DDPG 算法的详细内容如算法3所示. 基于 DDPG 的算法将迭代运行，直至给定轮次设置（行②）. 在每一个episode中，模拟环境被初始化，初始状态则随机生成（行③④）. 首先，在每个时隙中，主$\mathrm{A}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}$网络会根据当前状态${s}_{t}$和策略$\mu$生成相应动作，并根据得到的动作生成新的状态和奖励；同时，CSP作为代理可将其样本传输元组$\left({s}_{t},{a}_{t},{r}_{t},{s'}\right)$存储到经验回放池中（行⑤~⑧）. 然后，基于当前的状态和动作，主$\mathrm{C}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{c}$网络可以更新价值网络参数$w$并计算当前的$\mathrm{Q}$值（行⑩）；目标$\mathrm{C}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{c}$网络将当前的$\mathrm{Q}$值发送到主$\mathrm{C}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{c}$网络，以最小化损失函数$L\left(w\right)$（行⑪）. 最后，根据价值网络参数$w$和来自经验回放池的样本传输元组，主$\mathrm{A}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}$网络使用策略梯度来更新当前策略（行⑫），并在当前时隙结束时，更新目标网络的参数（行⑬）.

算法3. 基于DDPG的参与型车辆调度算法.

输入：参与型车辆候选集合${U}_{M}$，预算$B$，初始状态${s}_{0}$，测试环境参数$\theta ,\theta ',w,{w'},\tau ,\gamma ,m,N$，最大迭代次数$T$；

输出：参与型车辆的轨迹策略.

① 随机初始化参数：$\theta ,w,{\theta '}=\theta ,{w'}=w$，初始化重 放存储器组$D$；

② for each steps of episode do

③ 初始化模拟环境设置；

④ 随机生成并接收一个初始状态；

⑤ for $t$ form $1$ to $T$ do

⑥ 在$\mathrm{A}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}$网络中，根据式（18）获取动作${a}_{t}$；

⑦ 在系统中执行动作${a}_{t}$，获得奖励${r}_{t}$和下一 个状态$s'_{t}$；

⑧ 将$\left({s}_{t},{a}_{t},{r}_{t},{s'}\right)$存入经验回放池$D$；

⑨ 从经验回放池$D$中随机选择一个小批量 的样本传输元组$\left({s}_{t},{a}_{t},{r}_{t},{s'}\right)$；

⑩ 根据式（22）计算当前目标$\mathrm{Q}$值；

⑪ 根据式（23）更新主$\mathrm{C}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{c}$网络参数$w$的权重；

⑫ 根据式（24）更新主$\mathrm{A}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}$网络参数$\theta$的权重；

⑬ 根据式（25）（26）更新目标$\mathrm{C}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{c}$网络和目标 $\mathrm{A}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}$网络参数；

⑭ end for

⑮ end for

5.   实验分析

本节针对所提的基于反向拍卖的机会型车辆选择方法和基于DDPG的参与型车辆调度方法进行性能分析，并通过真实数据集验证了所提方法的有效性，并优于基准方案.

5.1   实验设置

针对基于反向拍卖的机会型车辆选择问题，本文使用基于现实世界的Roma数据集^[34-35]以验证所提方法的有效性. 该数据集收集了意大利罗马市内 320辆出租车在30天内的轨迹数据. 其中，数据时间为2014年2月1日至2014年3月2日，车辆轨迹每隔约15 s通过经纬度更新1次，数据格式为〈出租车ID，日期，时间，纬度，经度〉.

由于该数据集的地理范围较大，本文使用了原始数据集的一部分，以确保准确发现车辆运动信息. 首先，本文选取数据集的GPS范围位于（41.87, 12.44）和（41.93, 12.50）之间的矩形区域内. 然后，将此矩形区域划分为大小相同的子区域网格，每个子区域网格存在1个感知任务. 根据划分精度不同，任务的稀疏性也不同，本文将网格的划分精度区间设置为$\left[\mathrm{0.001,0.01}\right]$. 当车辆经过1次某子区域网格，则代表完成1次感知任务. 最后，根据出租车的位置和时间生成车辆轨迹，并与子区域网格进行匹配，确定每辆车可完成的感知任务.

本文随机选取数据集中$\left[\mathrm{20,100}\right]$辆车的前1 000个轨迹点所形成的轨迹进行分析，并且设定获胜车辆数量为候选车辆数量的一半. 此外，每辆机会型车辆完成任务的单位成本在$\left[\mathrm{0.3,1.1}\right]$之间变化. 为了与所提基于反向拍卖的机会型车辆选择方法（WSA）进行比较，本文提出了4个基准方案：

1）随机（Random）. CSP 随机选择目标数量的机会型车辆完成感知任务.

2）基于成本的贪心方法（greedy cost，GC）. CSP仅选择完成感知任务单位成本最低的机会型车辆，而不考虑其他因素.

3）基于感知任务完成数量的贪心方法（greedy task，GT）. CSP仅选择可完成感知任务数量最多的机会型车辆.

4）不考虑感知公平性的反向拍卖方法^[24]（no-fair_index, NF）. CSP通过反向拍卖方法选择机会型车辆，但不考虑感知公平性的影响.

针对基于DDPG的参与型车辆调度问题，本文设置与机会型车辆相同的场景，即在同样GPS范围的矩形区域内进行分析. 然后对矩形目标区域以精度0.01进行划分，将目标区域设置为6×6大小的子区域网格，每个子区域网格最大感知次数设为10. 对于所提出的基于DDPG的参与型车辆调度方法，本文使用具有2个隐藏层的全连接神经网络分别作为$\mathrm{A}\mathrm{c}\mathrm{t}\mathrm{o}\mathrm{r}$网络和$\mathrm{C}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{c}$网络，每层隐藏单元的数量为128. 最后，针对网络训练过程，本文设置经验回放池大小为5 000，所选样本传输元组的小批量为64，学习率则设为0.001；针对网络学习过程，设置折扣因子$\gamma$为0.9，软参数$\tau$为0.005.

为了与所提基于DDPG的参与型车辆调度方法进行比较，本文使用3个基准方案：

1）AC（Actor-Critic）. AC构建了一个全方位的智能体，不仅可直接输出策略，还可通过价值函数实时评估当前策略的质量. 其中，Actor使用策略函数生成动作并和环境交互；Critic使用价值函数评估Actor表现，并指导Actor下一阶段动作.

2）随机（Random）. CSP 随机做出动作决策，确定参与型车辆的轨迹路线，并完成相应的感知任务.

3）贪心方法（Greedy）. 针对每辆参与型车辆，CSP选择相邻子区域网格中感知次数最少的子区域网格作为当前车辆的下一个动作.

5.2   机会型车辆实验结果分析

本节对本文所提出的WSA方法的性能进行分析. 图5比较了当候选车辆数量变化时的CSP开销变化，其中图5（a）的网格区域划分精度为0.005，图5（b）的网格区域划分精度为0.01. 此时，设置单位任务成本在$\left[0.1, 0.3\right]$之间. 可以看出，随着车辆数量的增加，CSP的开销逐渐增加，这是由于有更多机会型车辆参与感知任务，CSP必然需要支付更多报酬，所以导致开销增长. 此外，本文所提出的WSA方法具有最低开销，验证了该方法所选的获胜机会型车辆集合的最优性. Random效果最差，主要因为随机选择无法带来任何优化. NF结果接近于WSA，这是因为NF也通过获胜者选择方法选取最优车辆集合. 然而，由于NF为不考虑感知公平性下的最优解，这验证了WSA方法在感知公平性上的优越性.

图  5  CSP 开销随机会型车辆数量的变化

Figure  5.  CSP overhead changes with the number of opportunistic vehicles

下载: 全尺寸图片 幻灯片

图6比较了CSP的开销随机会型车辆执行感知任务的单位成本的变化情况，其中图6（a）的网格区域划分精度为0.005，图6（b）的网格区域划分精度为0.01. 此时，将候选车辆集合设定为60. 可以发现，WSA略优于NF和GT，并大幅优于Random和GC. 这是因为GC仅选取感知成本最低的机会型车辆，并没有考虑车辆可完成的任务数量，因而导致较低的公平性指数，产生更高开销. 此外，随着感知任务执行成本的增长，CSP的开销也随之逐渐增长.

图  6  CSP 开销随机会型车辆单位任务成本的变化

Figure  6.  CSP overhead changes with the unit task cost of opportunistic vehicles

下载: 全尺寸图片 幻灯片

图7和图8比较了WSA与NF在感知公平性方面的性能，此时候选车辆数量设为100辆. 其中，图7可视化了在精度0.01下WSA方法和NF方法中各网格感知次数的热力图，图8可视化了在精度0.005下WSA方法和NF方法中各网格感知次数的热力图. 这里，子网格颜色深浅代表了对应子区域网格感知任务的完成次数. 可以看出，与NF相比，WSA拥有更好的感知公平性. 此外，图7（a）中网格区域完成的最大感知任务次数为72，而图7（b）中网格区域完成的最大感知任务次数为102. 图8（a）中网格区域完成的最大感知任务次数为55，图8 （b）中网格区域完成的最大感知任务次数为59. 这里，尽管最大感知任务次数的数值接近，但是可看出感知公平性差异明显.

图  7  精度 0.01 时不同子区域网格感知任务完成次数可视化

Figure  7.  Visualization of the number of completed sensing tasks in different sub-region grids at 0.01 accuracy

下载: 全尺寸图片 幻灯片

图  8  精度 0.005 时不同子区域网格感知任务完成次数可视化

Figure  8.  Visualization of the number of completed sensing tasks in different sub-region grids at 0.005 accuracy

下载: 全尺寸图片 幻灯片

此外，本文对算法2的有效性进行验证，并选取其中$10$辆获胜机会型车辆的结果进行分析，如图9和表1所示. 在图9中，车辆数据点被表示为（单位成本，单位报酬），可看出车辆的数据都在图9中的左上方，这说明每辆获胜的机会型车辆的单位报酬都大于其单位成本，从而符合预期. 此外，根据表1可以看出，获胜车辆单位报酬的大小与其对CSP开销降低带来的贡献程度有关，贡献越大，获得的单位报酬就越高. 相反，感知任务完成的次数与单位报酬并无直接关系，这是因为尽管车辆完成较多感知任务，但对CSP公平性并没有带来明显改善，因此无法获得较高报酬.

图  9  PA 方法有效性验证

Figure  9.  Validation of PA method effectiveness

下载: 全尺寸图片 幻灯片

表  1  PA方法相关结果

Table  1.  Related Results of PA Method

获胜车辆ID	单位成本	单位付款	CSP开销降低的幅度	任务完成次数
370	0.140326	1.233298	26.23132	24
179	0.152087	1.648364	35.91063	24
174	0.208489	0.918434	14.90886	21
290	0.140510	0.641551	17.03537	34
14	0.152216	1.260109	37.66836	34
339	0.202298	0.412341	6.721365	32
19	0.114158	0.350992	11.36804	48
278	0.299363	1.869238	31.39749	20
349	0.212298	1.412341	16.72136	32
30	0.121529	0.394767	15.57460	57

下载: 导出CSV 

| 显示表格

5.3   参与型车辆实验结果分析

本节对本文所提出的基于DDPG的参与型车辆调度方法进行性能分析. 首先进行收敛性分析，本文选取$6$辆车在$6\times 6$的网格区域内进行实验，设置参与型车辆单位任务成本在$\left[0.1, 0.3\right]$之间. 图10总共绘制了1 600个episode的累积平均奖励的收敛曲线图. 正如预测的那样，与AC算法相比，基于DDPG的参与型车辆调度方法表现出更快的收敛速度和更好的性能. 可以看出，随着episode训练轮次的增加，平均奖励迅速增加，尽管在200~400轮次出现波动，但仍在1 000轮次后收敛到相对稳定的值. 此外，可看出AC收敛速度则更加缓慢，波动也较大，这是因为AC更新过程中没有经验回放池，导致收敛速度变慢. 而基于DDPG的参与型车辆调度方法利用经验回放池和双网络结构，使神经网络学习更加有效. 因此，基于DDPG的方法比AC具有更好的收敛性能. 此外，图10中还可看出，传统适用于离散动作的DQN方法效果表现较差，收敛速度非常缓慢，这是由于动作空间过大造成的. 因此本文通过离散动作连续化，应用DDPG方法可以更好地获取参与型车辆动作决策.

图  10  每 episode 平均奖励变化趋势

Figure  10.  The average reward trends for each episode

下载: 全尺寸图片 幻灯片

其次，图11比较了CSP的开销随参与型车辆数量的变化情况（参与型车辆数量设置为[2,10]），其中图11（a）的网格区域划分精度为0.01，图11（b）的网格区域划分精度为0.005. 可以看出，随着车辆数量的增加，CSP的开销逐渐增加，这是因为有更多参与型车辆参与感知任务，CSP必然需要支付更多的报酬，从而导致开销增长. 此外，本文所提出的基于DDPG的方法具有最低开销，从而验证了该方法的优越性. 相比较，Random效果最差，主要因为其无法在感知公平性方面带来任何优化. 尽管AC接近于本文所提基于DDPG的方法，但其收敛速度较慢. 此外，Greedy方法通过贪婪方式获取车辆动作，容易导致局部最优解，因此CSP开销也较大.

图  11  CSP 开销随参与型车辆数量的变化

Figure  11.  CSP overhead changes with the number of participatory vehicles

下载: 全尺寸图片 幻灯片

最后，图12比较了CSP开销随参与型车辆执行感知任务的单位成本的变化情况（参与型车辆数量设为6），其中图12（a）的网格区域划分精度为0.01，图12（b）的网格区域划分精度为0.005. 可以发现，本文所提基于DDPG的参与型车辆调度方法略优于AC，并大幅优于Random和Greedy，这种差距随着单位成本的增加而更加显著. 此外，随着感知任务执行成本的增长，CSP的开销也随之逐渐增长.

图  12  CSP 开销随参与型车辆单位任务成本的变化

Figure  12.  CSP overhead changes with the unit task cost of participatory vehicles

下载: 全尺寸图片 幻灯片

6.   总结与展望

本文以挖掘机会型车辆和参与型车辆的不同移动特性为出发点，分别研究了这2种类型的车辆面向城市感知场景中的实际问题. 针对机会型车辆，本文应用基于反向拍卖的激励方法，通过选择最优的获胜机会型车辆集合完成感知任务，并设计了相应的报酬支付算法. 针对参与型车辆，应用基于DDPG的方法指导CSP决策，以确定参与型车辆行驶轨迹，并完成相应的感知任务. 此外，本文引入感知公平性指数以保证不同子区域感知任务完成的均衡性，保证了在2种类型的车辆感知场景下都能最小化CSP的开销. 基于真实世界数据集的广泛评估表明，本文所提方法效果良好，并优于其他基准方案.

目前，根据2种类型车辆的不同移动特性，本文选择对应的解决方法以匹配所提问题，目的是突出2种类型车辆的不同移动特性在感知任务完成方面带来的影响. 在未来工作中，我们计划将这2种类型车辆相结合，并考虑不同类型车辆间在完成感知任务时的相互影响. 据此，可探索结合2种类型车辆的混合感知方法，以发挥2种类型车辆在移动特性方面的优势，共同完成感知任务.

作者贡献声明：王振宁提出了实验方案并撰写论文；曹越提出指导意见并修改论文；江恺对实验方案设计提出意见；林海和周欢参与论文修改.