偏好感知的边云协同群智感知参与者选择策略

王汝言，刘 佳，何 鹏，崔亚平

(1.重庆邮电大学 通信与信息工程学院，重庆 400065；2.重庆高校市级光通信与网络重点实验室，重庆 400065；3.泛在感知与互联重庆市重点实验室，重庆 400065)

近年来，随着移动智能设备的普及和嵌入式传感器的发展，移动群智感知(Mobile Crowd Sensing，MCS)[1-3]已经成为一种有效的物联网数据收集范式。另外，无线通信技术的快速发展[4-5](比如未来B5G和6G移动通信网络等)使得网络容量和传输速率进一步突破，这将显著地提高群智感知数据收集的效率。传统的移动群智感知系统依赖集中式服务器处理来自大量参与者提供的感知数据，在大规模移动群智感知部署情况下，这种体系结构消耗大量计算资源。若集中式服务器远离感知区域，用户和服务器间通信则会增加数据和信息传输的延迟，这会阻碍移动群智感知下实时数据收集[6]。近年来，随着移动边缘计算(Mobile Edge Computing，MEC)技术的发展，结合边缘计算的移动群智感知架构已经被提出[7]。在移动群智感知中，边缘节点用于处理移动设备和云服务器之间的数据，用户实时状态更新发生在移动设备附近，用户收集的感知数据由最近的边缘节点处理，因此可以减少信息传播和通信时延，有效支持实时的移动群智感知场景[8]。

在大量的用户群体中，如何选择最有效的用户子集作为参与者执行感知任务是移动群智感知面临的关键问题[9-11]。现有工作[12-13]通常从平台的角度出发选择参与者完成任务，满足其不同的优化目标，包括最小化感知成本和用户移动距离、最大化任务覆盖等。这种策略没有考虑用户感知能力差异。还有部分文献[14-15]考虑了用户的社会属性去选择参与者，但忽视了用户对不同任务的偏好这一关键因素。在现实中，由于任务的位置、时间、类型等差异，用户更想要执行自己偏好的任务。不恰当的任务分配使用户和平台双方都不满意，这在很大程度上影响用户执行任务的态度和积极性，降低了群智感知系统的性能。这些问题在结合移动边缘计算的移动群智感知架构下变得更为复杂，参与者选择过程应该由云平台和边缘节点共同执行以发挥各自的优势。

关于群智感知中的参与者选择问题，国内外的学者和研究机构已经做了大量研究。文献[16]考虑多个参与者方面的因素和任务的多维异构性而选择参与者最大化系统效用，又考虑了任务覆盖质量和参与者任务完成可能性，但并没有关注任务预算和感知成本。文献[17]提出一种多任务分配框架，考虑参与者意向移动和非意向移动，分别为时间敏感型任务和延迟容忍型任务而选择合适的参与者，最小化移动距离和参与者的数量。文献[18]提出一种数据质量指导下的激励机制设计，采用扩展期望最大化算法、最大似然估计和贝叶斯推理评估数据质量，并进一步应用信息论衡量有效数据贡献，基于数据贡献奖励参与者。文献[19]提出一种服务效益感知的多任务分配策略，首先根据任务困难度、任务历史、感知能力和感知积极性计算参与者的服务效益，然后通过改进的模糊聚类方法聚类用户，最后设计了一种梯度下降算法为任务匹配用户。现有参与者选择策略往往只能满足其单一优化目标，而忽视用户偏好和任务偏好等因素，这些因素对群智感知系统的发展至关重要。

针对上述研究问题，笔者首先在传统群智感知系统架构下引入移动边缘计算，提出一种边云协同的群智感知系统架构，整个感知过程由云平台和边缘节点协作执行。然后在此基础上，针对群智感知过程中的参与者选择阶段提出偏好感知的参与者选择策略，为任务选择合适的参与者。云平台根据任务位置向边缘节点分发任务，边缘节点在区域内进行参与者选择，并将收集的数据上传到云平台。考虑用户和任务双方的不同偏好，根据任务的时间、位置、类型和奖励评估用户对任务的偏好；根据用户的声誉和感知成本，评估任务对用户的偏好。把群智感知中的参与者选择问题建模为用户与任务间的稳定匹配问题，通过求解稳定匹配最大化用户偏好。

1 系统模型

首先提出群智感知系统的工作流程。如图1所示，移动群智感知系统模型由4部分组成：数据请求者、MCS云平台、边缘节点和移动用户(用户区域)。数据请求者向MCS云平台请求数据，MCS云平台根据请求信息生成一组任务集，根据任务的位置将任务子集发送至区域对应的边缘节点。边缘节点向当前区域用户发布任务消息，区域内想要参与任务的用户会向边缘节点发送任务请求。边缘节点在区域内进行参与者选择过程，完成用户与任务间的匹配。最后，边缘节点接收用户提交的数据并最终上传到云平台。其中，任意两个节点之间进行的通信和数据流的传输需要移动通信技术[20]的支持，保障群智感知系统各个阶段的效率。主要研究群智感知中的参与者选择阶段，假设任意节点间可以正常通信，提出合适的参与者选择策略。

图1 移动群智感知系统模型

考虑用户和平台不同的偏好，如何设计一种参与者选择策略在保证数据质量的同时使用户方的偏好最大化，是研究的主要问题。群智感知中的参与者选择可以看作用户与任务间的匹配问题，稳定匹配理论在具有双方偏好的匹配问题中应用广泛，适用于学生择校、婚姻匹配等各种场景[21]。在移动群智感知中应用稳定匹配可以充分整合影响用户和任务偏好的各种因素，并且实现匹配后双方都能达到稳定状态。考虑到用户感知能力受限，假定每个用户只能完成一个任务；而每个任务需要多个用户共同完成以确保感知质量。因此，笔者把用户和任务之间的参与者选择建模为多对一匹配模型，为每个任务选择合适的参与者，以用户偏好最大化为目标求解双方完全匹配下的稳定匹配。

首先给出用户ui偏好任务集，记为ι(ui)：

ι(ui)={wj|∀j∈[1，2，…，n]} ，

(1)

该集合为一个有序集，集合中的任务按照用户对任务的偏好γi，j降序排列，集合中的任务数量为n。使用wj≻uiwj′表示ui相对于wj′更喜欢wj。

相似地，得到任务wj偏好用户集，记为ι(wj)：

ι(wj)={ui|∀i∈[1，2，…，m]} ，

(2)

该集合为一个有序集，集合中的用户按照任务对用户的偏好εj，i降序排列，集合中的用户数量为m。使用ui≻wjui′表示wj相对于ui′更喜欢ui。

下面给出多对一稳定匹配相关定义。

定义1(匹配S)匹配S是用户-任务对(ui，wj)的集合，S(ui)表示用户ui在S中的匹配对象，S(wj)表示任务wj在S中的匹配对象。

定义3(不稳定对)给定一个匹配S，在双方完全匹配中一个用户ui和一个任务wj组成一个不稳定对(ui，wj)，满足wj≻uiS(ui)并且存在一个子集U′⊆S(wj)，{ui}≻wjU′。

定义4(稳定匹配)如果匹配S中不包含任何不稳定对，那么匹配S为稳定匹配。

所提参与者选择问题可以描述为：对于边缘节点管理的区域，首先评估任务所需用户总数k，然后从用户集U中选择k个用户作为候选用户Uk，与n个任务构造稳定匹配S，使得稳定匹配S中每个用户分配任务的用户偏好最大化。

(3)

其中，S*为所有稳定匹配构成的集合。

2 用户和任务偏好评估

主要评估用户偏好和任务偏好的影响因素，边缘节点根据这些因素量化用户和任务的偏好。

2.1 用户偏好

2.1.1 时间因素

时间因素对用户偏好具有重要影响。群智感知中的任务是有时间约束的，用户在任务规定的持续时间内任意时刻到达任务地点才能执行任务。如果用户到达时间超过了任务结束时间，则用户无法完成感知任务。不同用户空余时间是不同的，用户更偏好那些在空余时间内能够完成的任务。根据任务的持续时间和用户空余时间，边缘节点首先计算用户的有效时间，然后通过用户执行任务的有效时间与任务持续时间的比例评估用户ui与任务wj的时间匹配度。分3种情况进行讨论：第1种是用户结束时间为任务持续时间内的某个时刻，此时用户有效时间为用户的空余时间；第2种是用户结束时间小于任务开始时间或用户开始时间大于任务结束时间，此时用户有效时间为0；第3种是用户开始时间小于任务结束时间，但用户结束时间大于任务结束时间，此时用户有效时间为任务结束时间与用户开始时间的差值。用户ui与任务wj的时间匹配度，记为Ξi，j：

(4)

2.1.2 距离因素

群智感知中的任务是基于位置的。不同任务需要在不同的地点执行，并且不同用户所处位置也具有很大差异。用户位置与任务位置间距离越大，用户需要花费越多的时间到达任务位置执行任务。平台发布任务时，对每个任务都有一个有效覆盖半径Rj，处于任务有效覆盖半径的用户更有可能完成任务。当用户与任务的位置距离超过有效覆盖半径，用户与任务的距离匹配度随两者距离的增大而减小。假设任务存在最大距离Rmax，当两者间的距离超过最大距离时，认为用户无法完成任务。边缘节点根据用户提交的位置信息以及任务位置计算用户ui和任务wj的距离匹配度，记为Ψi，j：

(5)

其中，Di，j为用户位置与任务所处位置间的欧式距离。

2.1.3 任务类型因素

在群智感知系统中，平台发布任务具有不同的类型。任务大致可以划分为3大类：环境现象类、基础设施现象类、社交应用类[1]。不同用户对不同类型任务具有不同的偏好，用户往往更想要或者有能力完成其中某一类任务。根据用户一段时间内完成任务的列表Lui计算用户对任务wj的类别偏好，其中，Lui中任务wj所属类型的任务个数越多，用户ui对该任务wj的偏好越大，记为Ζi，j：

(6)

当wi与wj类型相同时，M(wi，wj)为1，否则为0。

2.1.4 奖励因素

平台发布任务时，往往会给出任务的预算。该预算用来弥补用户感知过程的成本消耗，并激励用户积极参与感知任务。在用户选择自己偏好任务时，任务奖励是需要考虑的。不同任务的预算不同，往往任务价值越大，执行感知任务越困难，任务所需用户数越多，任务预算越大。同时用户感知成本也会影响用户的奖励偏好，在相同的任务奖励下，感知成本越低，用户需要付出的代价越小，用户的奖励偏好越大。因此，首先通过任务的预算和所需用户数计算参与者平均奖励，结合感知成本计算用户ui对任务wj的奖励偏好，记为Ωi，j：

(7)

其中，ci，j为用户感知成本，在节2.2.2介绍。

综上所述，用户与任务间的时间匹配度、距离匹配度、任务类型以及任务奖励都会影响用户对任务的偏好，且用户偏好与上述因素成正相关关系。用户与任务的时间、距离越匹配以及用户对任务的类型和奖励偏好越高，用户对任务的偏好越大。参考文献[10，22]中对用户相关属性的量化方式，计算用户ui对任务wj的偏好，记为γi，j：

γi，j=Ξi，jΨi，jΖi，jΩi，j。

(8)

2.2 任务偏好

2.2.1 用户声誉

参与者提交数据质量对群智感知服务性能具有重要影响。高质量的数据不仅可以提高数据请求者的满意度，也能维持平台高效运行；反之，低质量的数据降低了群智感知服务的可用性。声誉指标可以很好地反映用户执行感知任务的能力，通过考虑用户历史任务记录来评估用户的声誉。在用户历史任务记录中，用户提交数据的准确性是主要因素。

假设用户ui在执行历史任务wj时提交了一组数据{d1，d2，…，dn}，感知平台计算的数据真值为d*，则通过均方根误差来衡量一组感知数据的观测值同真值之间的偏差αui(wj)，对其进行归一化，得到参与者感知数据的准确度，记为βui(wj)：

(9)

(10)

其中，αmin(wj)和αmax(wj)分别为执行感知任务wj的所有用户感知数据的最小偏差和最大偏差。

(11)

2.2.2 用户感知成本

边缘节点通过考虑移动成本、资源消耗成本和流量消耗成本实时评估用户感知成本ci，j。其中，移动成本表明用户从当前位置走到任务位置所产生的距离开销，与用户和任务间的距离有关。距离越大，移动成本越大并且用户每移动单位距离会产生一个固定的开销，ρdis为单位距离成本，与系统类型有关。资源消耗成本和流量消耗成本表明用户执行感知任务过程消耗的设备内存、电量和流量。用户执行感知任务所需时间越长，资源消耗越多，ρres为单位时间资源消耗系数，根据用户自身设备可知；用户感知数据量越大，上传数据花费的流量越多，其中ρdata为单位数据流量消耗系数，由用户提交的配置文件可得。因此，边缘节点评估用户ui完成任务wj的感知成本，记为ci，j：

ci，j=ρdisDi，j+ρresΔt(wj)+ρdataowj，

(12)

其中，Di，j为用户所需移动距离，Δt(wj)为任务所需感知时间，owj为任务所需数据量。

在评估任务对用户的偏好时，平台更喜欢为任务选择完成质量较大的用户。高质量的用户往往能够提供高质量的感知数据，用户声誉代表用户完成任务的质量。另外，对于不同的任务，用户完成任务的感知成本不同，在用户提供数据质量相同的情况下，平台更想要那些感知成本低的用户。因此，通过用户声誉和感知成本来量化平台中任务wj对用户ui的偏好，记为εj，i：

(13)

3 参与者选择策略

笔者基于延迟接受机制[21]的思想实现多对一匹配条件下的稳定匹配。算法从候选用户集Uk中的每个用户ui出发，向用户偏好列表l(ui)中的第一个任务wj发出匹配。任务集中的每个任务wj根据收到的用户请求和所需用户数rj限制最优地选择用户子集。未被选择的用户开始下一轮的匹配，向偏好列表中的下一个未被选择的任务发出匹配，然后相应的任务根据当前用户集和新到达用户最优地更新当前用户集合，直到所有用户找到自己匹配的任务。

所提的参与者选择算法如下。

算法1基于稳定匹配的参与者选择算法(PSSM)。

输入：任务集W，用户集U，l(ui)，l(wj)。

输出：匹配S。

初始化：S(ui)←φ，S(wj)←φ。

① 对用户集U按照声誉值降序排序

② 候选用户集Uk←声誉前k个用户

③ whileUk不为φ

④ for∀ui∈Uk

⑤ 选择l(ui)中还未被选过的第一个任务

⑥ if (|S(wj)|

⑦S(ui)←wj

⑧S(wj)←S(wj)∪ui

⑨Uk←Ukui

结论1PSSM算法是有穷的。

证明 while循环中每个用户最多向n个任务发出请求，所以最多在nk个请求后算法停止。

结论2PSSM算法可以得到稳定匹配。

证明 假设匹配S中不包含匹配对(ui，wj)。第1种情况：ui从未向wj发出请求，得到ui比起wj更喜欢当前匹配对象，因此(ui，wj)是稳定对；第2种情况：ui向wj发出了请求，但是wj拒绝或抛弃了ui，得到wj比起ui更喜欢当前的匹配对象，(ui，wj)是稳定对。因此，匹配S中不包含的对一定是稳定对，匹配S不包含不稳定对，所以，PSSM算法是稳定的。

结论3PSSM算法可以产生双方完全匹配。

证明 假设存在用户ui在算法结束后未匹配到任务。由此可知，一定有一个任务wj的匹配对象没有达到任务所需用户数rj。根据算法，这种情况下任务wj一定会接收用户ui发出的请求，所以用户ui没有向任务wj发出请求。根据算法，用户ui向所有任务发出请求后才会终止，因此用户ui向任务wj发出了请求。前后矛盾，假设不成立。所有用户完全匹配，因此产生双方完全匹配。

结论4PSSM算法产生用户最优分配。

证明 对于用户ui，如果最后该用户的匹配任务是在其偏好列表的第i位，那么在i位之前的那些任务，他是匹配不到的。假设ui匹配到前面的任务wj(即wj一时糊涂答应)，那么任务wj必然会有比用户ui更加偏好的对象uj(在当时情况下，uj已经向wj发出匹配)。uj在当时向wj发出匹配，表明在偏好列表中wj之前的任务都拒绝了uj，如果wj也拒绝了uj，那么uj最后匹配到的任务必定排在wj后面。所以，uj和wj必然会构成不稳定对。假设不成立，因此PSSM算法产生用户最佳分配。

4 数值结果分析

为了更好地体现参与者选择策略PSSM的性能，与文献[14]提出的TRIM机制和文献[23]提出的IMRAL机制进行对比。TRIM机制首先根据任务向量和用户向量计算两者的相似度并获得候选用户集，然后根据报酬和相似度比值确定最终用户集。IMRAL机制针对每个任务选择投标与任务价值之比最小的用户作为获胜者，并根据临界价格给出报酬。仿真性能指标包括偏好程度、用户满意度、数据质量和任务平均完成时间。具体仿真参数如表1所示。

表1 仿真参数设置

4.1 用户偏好分析

图2 用户和任务偏好程度分析

图2展示的是在单任务需求数为2时，100个用户与50个任务进行稳定匹配，得到的每个匹配对中用户和任务各自的偏好程度。其中偏好程度表示每个匹配对中用户匹配到的任务或任务匹配到的用户在各自偏好列表中的排名，偏好程度越小，用户或任务对匹配对象的偏好越高。从图2中可以看到，在100个任务用户匹配对中，大多数的小点处在小圆的下方，表明在得到的稳定匹配中，用户对各自匹配任务的偏好明显优于任务对用户的偏好。这是因为笔者提出的PSSM算法中对于每个用户来说，匹配到的任务都是稳定匹配条件下能够匹配到的偏好最大的任务，因此该算法可以实现用户偏好最优分配。

图3研究了在任务数量为10和单任务所需用户数为3时，任务总预算对用户满意度的影响。其中用户满意度表示为稳定匹配对中用户对任务的平均偏好值。随着任务预算的增加，三种算法的用户满意度都会增加。其中，IMRAL算法的主要目的是提高用户效用和任务覆盖，任务预算的增加使所选用户的效用提高，但由于没有考虑用户的偏好，用户的满意度比较低。相比于TRIM算法，PSSM算法以用户偏好最大化为目标，因此PSSM算法中用户满意度最大。

4.2 平台效用分析

图4展示了在单任务需求用户数为3时任务数量对整体数据质量的影响。整体数据质量定义为所有用户提交数据质量的均值，在这里用声誉代表用户提交数据的质量。随着任务数量的增加，整体数据质量有所降低。这是由于在用户资源有限的情况下，任务数量越多，任务所需的用户数越多，提交低质量数据的用户会增多，导致数据质量降低。其中，IMRAL算法的目的是提高用户效用和任务覆盖，但是没有考虑用户具体感知数据质量，因此整体数据质量较低。相比于TRIM算法，PSSM算法量化了用户的声誉，并且从用户集中优选声誉值高的用户构造候选用户集，保证感知数据的质量。

图3 任务总预算对用户满意度的影响

图4 任务数量对整体数据质量的影响

图5展示了在任务数量为20和单任务需求用户数为3时，不同用户数量对整体数据质量的影响。随着用户数量的增加，整体数据质量有所提高。由于在任务数量固定的情况下，任务所需的用户数是固定的，随着用户数量的提高，用户资源变得充足，平台可以选择更优的用户去执行任务，数据质量有所提高。IMRAL机制主要优化用户效用，假定所有用户提交数据质量是一样的，因此整体数据质量较低。TRIM机制考虑用户和任务间的相似度，并根据阈值优化候选用户集，数据质量有所提高。而笔者提出的PSSM机制量化了用户的声誉，并根据声誉对匹配用户进行优化，数据质量较高。

图6展示了在任务数量为10和单任务需求用户数为3时，用户数量对任务平均完成时间的影响。任务平均完成时间定义为用户执行感知任务所需的时间均值。随着用户数量的增多，任务平均完成时间有所下降。这是由于用户数量的增多，导致用户方的资源充足，有效降低任务完成时间。IMRAL机制主要优化用户效用，没有考虑用户的具体位置，任务完成时间最高。相比于TRIM，笔者提出的PSSM考虑了用户可用时间和所处位置，并量化用户的偏好，为用户分配最优偏好任务，因此任务完成时间最低。

图5 用户数量对整体数据质量的影响

图6 用户数量对任务平均完成时间的影响

5 结束语

笔者在结合移动边缘计算的移动群智感知架构下提出了一个偏好感知的参与者选择策略，参与者选择过程由云平台和边缘节点协作执行。考虑用户和任务不同的偏好，边缘节点从任务时间、位置、类型和奖励方面对用户偏好进行量化，从用户声誉和感知成本方面对任务偏好进行量化。基于双方的偏好，在用户与任务间构造一个多对一稳定匹配，使匹配后的每个用户得到最优分配任务。在未来的工作中，打算研究在用户或任务动态到达的情况下如何立即做出选择，如何更好地实现边云协同发挥移动群智感知的优势等。