• 四川郎酒股份有限公司获第十二届人民企业社会责任奖年度环保奖 2019-05-13
  • 银保监会新规剑指大企业多头融资和过度融资 2019-05-12
  • 韩国再提4国联合申办世界杯 中国网友无视:我们自己来 2019-05-11
  • 中国人为什么一定要买房? 2019-05-11
  • 十九大精神进校园:风正扬帆当有为 勇做时代弄潮儿 2019-05-10
  • 粽叶飘香幸福邻里——廊坊市举办“我们的节日·端午”主题活动 2019-05-09
  • 太原设禁鸣路段 设备在测试中 2019-05-09
  • 拜耳医药保健有限公司获第十二届人民企业社会责任奖年度企业奖 2019-05-08
  • “港独”没出路!“梁天琦们”该醒醒了 2019-05-07
  • 陈卫平:中国文化内涵包含三方面 文化复兴表现在其中 2019-05-06
  • 人民日报客户端辟谣:“合成军装照”产品请放心使用 2019-05-05
  • 【十九大·理论新视野】为什么要“建设现代化经济体系”?   2019-05-04
  • 聚焦2017年乌鲁木齐市老城区改造提升工程 2019-05-04
  • 【专家谈】上合组织——构建区域命运共同体的有力实践者 2019-05-03
  • 【华商侃车NO.192】 亲!楼市火爆,别忘了买车位啊! 2019-05-03
    • / 15
    • 下载费用:30 金币  

    重庆时时彩真的假的: 众包系统中兼顾用户异质性与用户偏好的任务分配方法.pdf

    摘要
    申请专利号:

    重庆时时彩单双窍门 www.4mum.com.cn CN201610966591.7

    申请日:

    2016.10.28

    公开号:

    CN106570639A

    公开日:

    2017.04.19

    当前法律状态:

    实审

    有效性:

    审中

    法律详情: 实质审查的生效IPC(主分类):G06Q 10/06申请日:20161028|||公开
    IPC分类号: G06Q10/06(2012.01)I 主分类号: G06Q10/06
    申请人: 西北大学
    发明人: 尹小燕; 贾茹昭; 胡潇; 王倩倩; 王薇; 陈晓江; 房鼎益
    地址: 710069 陕西省西安市太白北路229号
    优先权:
    专利代理机构: 西安恒泰知识产权代理事务所 61216 代理人: 李婷;张明
    PDF完整版下载: PDF下载
    法律状态
    申请(专利)号:

    CN201610966591.7

    授权公告号:

    |||

    法律状态公告日:

    2017.05.17|||2017.04.19

    法律状态类型:

    实质审查的生效|||公开

    摘要

    本发明公开了一种众包系统中兼顾用户异质性与用户偏好的任务分配方法,该方法权衡任务的预算、用户异质性以及用户偏好,基于多对一匹配机制,找到最佳的用户?任务匹配;该分配方案的核心在于,在算法运行的整个过程,每项任务的完成质量总和非减。本发明方法为众包系统提供了一种新的分配思路和具体方案,克服了当前的众包系统任务分配策略未考虑用户异质性和用户偏好的问题,由本发明算法得到的匹配结果具备个体理性、公平性且不浪费性等特点。

    权利要求书

    1.一种众包系统中兼顾用户异质性与用户偏好的任务分配方法,其特征在于,包括以
    下步骤:
    步骤1,将众包系统中所有任务和用户均初始化为自由者;
    步骤2,随机选择一名自由用户w,该用户w满足:
    用户w没有被自己偏好列表中的所有任务拒绝;
    若无自由用户可选,则方法结束;
    步骤3,选择用户w的偏好列表中尚未拒绝用户w且优先级别最高的任务t,若无t可选,
    则返回步骤2;否则执行以下步骤:
    步骤3.1,若任务t的余额足以支付用户w,则将用户w分配给任务t,并更新任务t的余
    额;
    步骤3.2,若任务t的余额不足以支付用户w,则找到用户集合B,该集合B中的每名用户
    w'满足以下两个条件:
    条件1:在配结果μ中,用户w'已被分配给任务t;
    条件2:在任务t的偏好列表中,用户w的优先级别高于w';
    步骤3.2.1,若集合B为空集,则用户w被任务t拒绝,返回步骤2;
    步骤3.2.2,若集合B非空集,则生成集合β,β由B的所有子集构成;
    若β中存在元素B'满足如下两个条件:
    条件3:任务t移除B'中所有用户后,任务t有足够余额可接纳w;
    条件4:用户w取代集合B'以后,任务t的完成质量不会降低;
    则找出B'中服务质量总和最小的子集Bmin,然后将Bmin移除,把任务t分配给w,更新t的
    余额,返回步骤2。
    2.如权利要求1所述的众包系统中兼顾用户异质性与用户偏好的任务分配方法,其特
    征在于,所述的步骤3.2中,用户用户集合B的形成方法为:
    对于分配给任务t的每位用户w',查看任务t的偏好列表,确定w'的排序是否在w之后,
    若w'在w之后,则该用户w'属于用户集合B。。

    说明书

    众包系统中兼顾用户异质性与用户偏好的任务分配方法

    技术领域

    本发明涉及众包技术领域,具体涉及一种众包系统中兼顾用户异质性与用户偏好
    的任务分配方法。

    背景技术

    随着全球化的推进,众多网络平台应运而生,网络的群体力量爆发出前所未有的
    影响力。群体中多元化的知识背景与协作理念为大型任务的顺利完成提供了力量源泉,“与
    用户共创价值”是众包系统的核心。众包能降低成本,提高效率,在众包系统中,跨专业的创
    新与合作蕴含巨大潜力,能实现任务发布者与任务参与者双方共赢。利用网络的群体力量,
    众包能完成依靠个人力量无法解决的难题,如涉及各阶层的社会调查,此类数据的收集困
    难重重,且需要多人参与。

    若采用传统方式,意见全面而分析透彻的调查报告耗时耗力;若借助于集众人智
    慧与力量而大成的众包系统,此类调查易如反掌且能获得满意的任务完成质量。目前,鉴于
    其低成本及高效性,Uber、Waze和亚马逊的Mechanical Turk等众包系统日益盛行。

    任务分配是众包系统需解决的首要问题。众包系统中的任务分配面临多重挑战:
    首先,用户对任务有不同偏好。例如,任务发布者计划收集地点A和地点B的交通信息,由于
    用户a的居住地靠近地点A,与地点B相比,用户a肯定更愿意选择与地点A相关的任务。一言
    以蔽之,若用户有机会选择自己更青睐的任务,他将毫不犹疑地放弃当前任务;其次,用户
    因经验、技能和能力等方面的差异而导致的任务完成质量不尽相同。因此,多名高质量用户
    对应高品质的任务完成质量。然而,虑及用户的有偿参与,任务发布者不可能为每项任务招
    募超出其支付能力的用户,因为每项任务具有相应的财务预算。

    目前的众包系统中已经有多种任务分配策略:

    (1)车联网众包系统中基于可预测运动性的参与者招募策略;(2)移动众包系统中
    基于机会网络模式的用户招募策略;(3)预算受限的在线学习众包系统BLISS;(4)众包系统
    中实时可靠的任务分配策略;(5)众包系统中位置相关的最优任务分配方案;

    在现有的这些分配策略中,策略(1)未考虑用户异质性与用户偏好;策略(2)主要
    考虑移动环境下的用户招募;策略(3)虽然关注用户提交的数据质量与预算,但未考虑用户
    偏好;策略(4)关注的是用户运动和任务完成的不确定性;策略(5)未考虑预算及用户偏好,
    因此现有技术中这些策略并不适应于前面提到的任务分配问题。

    发明内容

    针对上述现有技术中存在的问题,本发明的目的在于,提供一种众包系统中兼顾
    用户异质性与用户偏好的任务分配方法,该方法中将多对一匹配框架引入众包系统,用以
    解决众包系统中的任务分配问题;用户对任务的完成质量具有不同的贡献,且对任务有不
    同偏好;每名用户至多被分配给一项任务,每项任务可接纳多名用户,越多用户参与,任务
    的完成质量就愈高,且任务发布者将确保支付给所有参与用户的费用不超过任务预算。

    为了实现上述任务,本发明采用以下技术方案:

    一种众包系统中兼顾用户异质性与用户偏好的任务分配方法,包括以下步骤:

    步骤1,将众包系统中所有任务和用户均初始化为自由者;

    步骤2,随机选择一名自由用户w,该用户w满足:

    用户w没有被自己偏好列表中的所有任务拒绝;

    若无自由用户可选,则方法结束;

    步骤3,选择用户w的偏好列表中尚未拒绝用户w且优先级别最高的任务t,若无t可
    选,则返回步骤2;否则执行以下步骤:

    步骤3.1,若任务t的余额足以支付用户w,则将用户w分配给任务t,并更新任务t的
    余额;

    步骤3.2,若任务t的余额不足以支付用户w,则找到用户集合B,该集合B中的每名
    用户w'满足以下两个条件:

    条件1:在配结果μ中,用户w'已被分配给任务t;

    条件2:在任务t的偏好列表中,用户w的优先级别高于w';

    步骤3.2.1,若集合B为空集,则用户w被任务t拒绝,返回步骤2;

    步骤3.2.2,若集合B非空集,则生成集合β,β由B的所有子集构成;

    若β中存在元素B'满足如下两个条件:

    条件3:任务t移除B'中所有用户后,任务t有足够余额可接纳w;

    条件4:用户w取代集合B'以后,任务t的完成质量不会降低;

    则找出B'中服务质量总和最小的子集Bmin,然后将Bmin移除,把任务t分配给w,更新
    t的余额,返回步骤2。

    进一步地,所述的步骤3.2中,用户集合B的形成方法为:

    对于分配给任务t的每位用户w',查看任务t的偏好列表,确定w'的排序是否在w之
    后,若w'在w之后,则该用户w'属于用户集合B。

    本发明与现有技术相比具有以下技术特点:

    1.本发明提出了一种新颖的多对一匹配框架,实现了众包系统中的稳定任务分
    配;

    2.本发明针对用户异质性,提出了一个新的匹配算法,并证明了由所有算法产生
    的匹配结果具备个体理性、公平性和不浪费性;

    3.本发明对所提任务分配算法的性能进行了分析,并证明了所提算法能在短时间
    内获得高任务完成质量的稳定匹配。

    附图说明

    图1为本发明的方法流程图;

    图2至图7为本发明方法与现有的Anchor算法性能比较图,其中:

    图2为用户数量-用户幸福指数关系图(任务数量为10);

    图3为任务数量-用户幸福指数关系图(用户数量为40);

    图4为平均预算限制-用户幸福指数关系图(任务数量为12,用户数量为40);

    图5为用户数量-运行时间关系图(任务数量为10);

    图6为任务数量-运行时间关系图(用户数量为50);

    图7为平均预算限制-运行时间关系图(任务数量为4,用户数量为40)。

    具体实施方式

    众包系统中已有的任务分配策略均未解决前述挑战。多数解决方案的目的是最大
    化任务发布者的效用,而未虑及用户对不同任务的偏好。有些已提出算法以最小化任务发
    布者的总成本为优化目标,但可能会超出单项任务的预算限制。多对一匹配机制已被广泛
    应用于计算机科学,可用于云计算的资源管理、低功率无线接入节点或基站的用户联合以
    及D2D通信系统中的资源共享等问题。然而,众包系统中的任务分配问题不同于传统的匹配
    问题,即众所周知的高考报考与大学招生问题,每名学生只能被一所大学录取,每所大学可
    以招收多名学生,但招生数量受限。每名学生的规模相同,均占用大学的一个名额。

    然而,在众包系统中,每名用户的规模不尽相同?;谎灾?,由于用户对任务的完成
    质量具有不同贡献,对应不同的支付额度,从而花费相应比例的任务预算。虽然经典的延迟
    接收算法能解决学生报考与高校招生问题,产生学生与高校间的稳定匹配结果。但是,若考
    虑众包系统中的用户异质性与用户偏好,对于本方案针对的任务分配场景,传统的延迟接
    受算法不能产生稳定的匹配结果。因此,我们提出面向众包系统的基于多对一匹配机制的
    任务分配框架,该框架涉及用户对不同任务的偏好以及单项任务的预算限制。

    一、本发明的详细步骤介绍

    众包系统由多项任务和多名用户构成,每名用户至多参与一项任务,每项任务可
    由多名用户协同完成,用W和T分别表示用户集合与任务集合。由于个人经验,技能和知识面
    的差异,用户具有异质性。假定用户w为所有任务提供相同的完成质量,用rw表示。只要用户
    w参与任务,她将获得相应报酬f(rw)。支付函数f(*)为单调递增函数。简单起见,假设f(rw)
    =αrw,这样在后续分析过程中易于扩展到非线性支付函数的情况。由于越多用户参与同一
    项任务,该任务的完成质量就越高。因此,每项任务应招募尽可能多的用户。然而,每个任务
    t∈T均有相应预算,用qt表示,意味着任务t支付给所有参与用户的总额不能超出其预算。

    每名用户对各项任务有不同偏好,对应于各项工作在该用户的偏好列表中的次
    序。用户w的偏好(用>w表示)是具有全序、自反性和传递性的二元关系。t>w t'表示相对于
    任务t',用户w更倾向于参与任务t。

    在预算限制内,任务t更希望吸引高质量用户参与。对于所有用户,任务t的偏好
    (由>t表示)亦为具有全序、自反性和传递性的二元关系。本方案假定用户w对于所有任务
    完成质量的贡献相同。任务对用户的偏好取决于用户能提供的服务质量,因此,所有任务对
    用户的偏好一致,即>t=>T。若用户w能提供比w'更高的完成质量,即rw>rw',则w在所有任
    务的偏好列表中的次序先于w',由此可推断w>T w'。

    已有众包系统的任务分配解决方案中,将任务发布者的效用最大化置于首位???br />虑用户对不同任务的偏好,旨在获得稳定的任务分配方案,无论是用户还是任务均不愿偏
    离当前的任务分配结果。为了实现这一目标,将任务分配问题建模为多对一且预算受限的
    匹配问题。

    本发明提出可实现该分配目标的稳定的任务分配方案,该分配方案的主要思想在
    于:在算法运行的整个过程,每项任务的完成质量总和非减。算法的具体步骤如下:

    一种众包系统中兼顾用户异质性与用户偏好的任务分配方法,包括以下步骤:

    步骤1,将众包系统中所有任务和用户均初始化为自由者;

    算法开始的时候,任务和用户均为自由状态,即自由用户为没有匹配到任何任务
    的用户,而自由任务为配有匹配到任何用户的任务。

    步骤2,随机选择一名自由用户w,该用户w满足:用户w没有被自己偏好列表中的所
    有任务拒绝;

    在本方案中,用户的偏好列表已知。用户的偏好设置规则如下:

    对于两个任务A0与B0,分别收集任务A0与B0所在地点的交通状况信息,若用户a离
    任务A0所在地点更近,则比起任务B0,用户a更愿意参加任务A0,即A0>a B0)。

    若无自由用户可选,即所有用户均不满足步骤2的条件,则方法结束;

    步骤3,选择用户w的偏好列表中尚未拒绝用户w且优先级别最高的任务t,若无t可
    选,则返回步骤2;否则执行以下步骤:

    步骤3.1,若任务t的余额足以支付用户w,则将用户w分配给任务t,并更新任务t的
    预算余额;更新后的余额为qt=qt-rw;其中,qt为任务t的余额,rw为用户w参与任务t所得报
    酬;

    步骤3.2,若任务t的余额不足以支付用户w,则找到用户集合B,该集合B中的每名
    用户w'满足以下条件1和条件2:

    条件1:在配结果μ中,用户w'已被分配给任务t,即μ(w')=t;

    条件2:在任务t的偏好列表中,用户w的优先级别高于w',即w>t w';

    所有满足这两个条件的用户组成集合B,即基于任务t的偏好列表,匹配到t的所有
    用户中排序比w靠后的用户集合为B。

    用户集合B的形成具体方法为:

    对于分配给任务t的每位用户w',查看任务t的偏好列表,确定w'的排序是否在w之
    后,若w'在w之后,则该用户w'属于用户集合B。

    步骤3.2.1,若集合B为空集,则用户w被任务t拒绝,返回步骤2;

    步骤3.2.2,若集合B非空集,则生成集合β,β由B的所有子集构成;

    若β中存在元素B',即B的某一子集B'满足如下条件3和条件4:

    条件3:任务t移除B'中所有用户后,任务t有足够余额可接纳w,即|B'|r+qt>rw;其
    中,|B'|r为集合B'中的用户价值,也就是任务t需要向B'中的用户支付的费用;

    条件4:用户w取代集合B'以后,任务t的完成质量不会降低,即|B'|r≤rw;

    则找出B'中服务质量总和最小的子集Bmin,然后将Bmin移除,把任务t分配给w,更新
    t的余额为qt=qt+|B'|r-rw,返回步骤2;如若β中不存在元素B',则直接返回步骤2。

    二、本发明方法的实例以及相关分析

    简明起见,在本实施例中,任务分配系统由4个用户与2项任务组成。用户a、b、c、d
    的服务质量及其偏好列表,任务A、B的预算限制及其偏好列表如表1所示:

    表1偏好列表及参数设置I



    根据自由用户及其偏好列表中任务的不同选择方式,本任务分配方案对应两种不
    同的运行序列:(1)基于轮询的迭代;(2)基于遍历的迭代。经验证,虽然两种迭代方式产生
    的匹配结果不同,但是两种匹配结果均是稳定的。

    (1)基于轮询的迭代。如表2所示,算法依次检查每个自由用户。第一轮,用户a被选
    定,按照其偏好列表,用户a向第一偏爱的任务B提出申请,但因B的余额不足而被拒绝。然
    后,用户b和c向其第一偏爱的任务A提出申请,均被接受;用户d也因A的可用余额不足而被
    拒绝,与用户d相比,任务A更喜欢b和c。第二轮,用户a向第二偏爱的任务A提出申请,虽然对
    于任务A,用户a的优先级高于b与c,但由于a的服务质量小于b和c的服务质量之和而被拒
    绝。

    相应的运行序列为:

    a→B,b→A,c→A,d→A;

    a→A,d→B。

    表2基于轮询的迭代运行实例

    Iteration
    Action
    Result
    1
    User a applies to job B
    μ(A)=Φ,μ(B)=Φ
    2
    User bapplies to job A
    μ(A)=,μ(B)=Φ
    3
    User capplies to job A
    μ(A)={b,c},μ(B)=Φ
    4
    User dapplies to job A
    μ(A)={b,c},μ(B)=Φ
    5
    User aapplies to job A
    μ(A)={b,c},μ(B)=Φ
    6
    User dapplies to job B
    μ(A)={b,c},μ(B)={d}

    (2)基于遍历的迭代。如表3所示,算法依次检查每个自由用户,直到选中用户偏好
    列表中的所有任务均被处理过,再检查下一自由用户。用户a向第一偏爱的任务B提出申请,
    但因B的余额不足而被拒绝。用户a接着向第二偏爱的任务A提出申请,被任务A接纳。但是,
    因任务预算受限,用户b依次被任务A、B拒绝。此后,用户c依次向任务A、B提出申请,被任务B
    接受。用户d向第一偏爱的任务A提出申请,被A接受。相应的运行序列为:

    a→B,a→A;

    b→A,b→B;

    c→A,c→B;

    d→A。

    表3基于遍历的迭代运行实例

    Iteration
    Action
    Result
    1
    User a applies to job B
    μ(A)=Φ,μ(B)=Φ
    2
    User a applies to job A
    μ(A)={a},μ(B)=Φ
    3
    User b applies to job A
    μ(A)={a},μ(B)=Φ
    4
    User b applies to job B
    μ(A)={a},μ(B)=Φ
    5
    User c applies to job A
    μ(A)={a},μ(B)=Φ
    6
    User c applies to job B
    μ(A)={a},μ(B)={c}
    7
    User d applies to job A
    μ(A)={a,d},μ(B)={c}

    三、本发明方法的理论证明

    定义1:众包系统的任务分配给定任务集合T、用户集合W和任务匹配结果μ。μ将任
    务t,t∈T映射到用户子集满足以下条件:

    ·对于任务t,t∈T,μ(t)∈2W;

    ·对于用户w∈W,μ(w)∈T;

    ·对于任务t和用户w,t=μ(w)当且仅当w∈μ(t);

    ·预算约束。对于任务t,

    预算约束保证每项任务支付给所有参与用户的总额不超出预算。任何超出预算约
    束的任务分配不可行。若任务分配满足个体理性、公平性和不浪费性,该任务分配方案则是
    稳定的。

    定义2:个体理性任务分配μ具备个人理性,则μ满足:

    ·与成为自由用户相比,每名用户更愿意被分配到某项任务,即

    ·任务更愿意被匹配到当前分配的用户集合,而非该用户集合的任意子集。

    由于有偿提供服务,所有用户更愿意被匹配给某项任务而不是成为自由用户,因
    而满足个体理性的第一个条件。参与用户的数量越多,任务的完成质量越高。因此,任何可
    行的满足预算约束的任务分配方案满足个体理性的第二个条件。于是,个体理性定理如下:

    引理1:任何可行的任务分配方案具备个体理性。

    与个体理性相比,公平性和不浪费性难于实现。在定义公平性和不浪费性前,首先
    引入两类关于任务分配的不稳定用户-任务组合。

    定义3:机会的不稳定组合给定任务分配结果μ,若用户w有机会偏离当前匹配结
    果,并能与任务t形成新的组合,则称用户w与任务t能形成机会的不稳定组合,表述如下:

    ·与当前匹配结果相比,用户w更倾向于参与任务t,即t>wμ(w);

    ·任务t的可用余额足以接纳用户w,即rw+∑w'∈μ(t)rw'≤qt

    用|S|表示用户集合S的数量。用|S|r=∑w∈S rw表示支付给用户集合S的总额。

    定义4:可替换的不稳定组合给定匹配结果μ,若用户w可取代一名或多名已经分配
    给任务t的用户,则用户w和任务t能形成可替换的不稳定组合,表述如下:

    ·与当前匹配结果相比,用户w更倾向于参与任务t,即t>wμ(w);

    ·存在一个用户,w'该用户已被分配给任务t,但任务t更倾向于用w代替w',即
    w>T w',|μ(t)|r-rw'+rw≤qt。

    显而易见,任务t用w替代w'的条件为:(1)用户w提供的服务质量不小于集w'中所
    有用户的服务质量之和;(2)移除集合用户w'后,任务t的余额足以支付w。只要满足以上两
    个条件,任务t就能用w替换掉用户集合w'。

    这两类不稳定组合的主要区别如下:为了接纳用户w,任务t是否需要踢除当前匹
    配中的用户,从而为w腾出空间?;谡饬嚼嗖晃榷ㄗ楹?,公平性和不浪费性定义分别如下:

    定义5:不浪费性若匹配结果μ中不存在机会的任务-用户组合,则该匹配结果μ具
    有不浪费性。

    定义6:公平性若匹配结果μ中不存在可替换的任务-用户组合,则该匹配结果μ具
    有公平性。

    若匹配结果兼具公平性和不浪费性,则所有的用户和任务均满意他们当前被匹配
    的结果。

    命题1:本方法所提任务分配方案的迭代次数为O(|W||T|)。

    证明:每次迭代时,自由用户均可向一项任务提出申请,不管该用户是否被该任务
    接受,该用户将不会再次向该任务提出申请。系统中至多有|W|名自由用户,每名用户至多
    向|T|项任务提出申请。因此,该任务分配方案的最大迭代次数为|W||T|。

    引理2:对于任务t,t∈T,随着迭代的进行,任务t的完成质量非减?;谎灾?,随着迭
    代的进行,t的可用余额非增。

    证明:假定自由用户w在某次迭代被选中,且t为w可选任务中优先级别最高的任
    务,任务t的可用余额为bt。显而易见,除任务t外,其余任务的可用余额不变。让表示本次
    迭代后任务t的可用余额。仅需证明

    若用户w被t拒绝,则

    若用户w被分配给任务t,且未移除已分配给t的任意用户,则

    若用户w被分配给任务t,且移除了已分配给t的用户集合Bmin,则
    又因|Bmin|r≤rw,因此

    得证。

    命题2:本方法所提的任务分配方案具备不浪费性。

    证明:反证法。假定用户w和任务t能形成机会的不稳定组合。因为t>wμ(w),用户w
    肯定向任务t提出过申请,但被拒绝了。用表示当用户w被任务t拒绝时刻的匹配结果。于
    是,根据引理2,于是,|μ(t)|r+rw≥bt。这与机会不稳定组
    合的定义矛盾。因此,匹配结果中不会存在机会的不稳定组合,本专利所提任务分配方案具
    备不浪费性。

    命题3:本专利所提的任务分配方案具备公平性。

    证明:为了证明公平性,首先引入两个符号。假定最终的匹配结果是μ且w∈μ(t),
    用表示任务t为了接纳用户w而移除的用户集合,表示用户w向t提出申请时刻t
    的可用预算。如果用户w没有挤走任何用户,则假定w'为用户集合中的元
    素,且w'被任务t接纳的时间晚于集合中其余用户。定义并且
    即当用户w'向任务t提出申请时,t的可用余额。

    任务分配系统由5个用户与3项任务组成。用户a、b、c、d的服务质量及其偏好列表,
    任务A、B、C的预算限制及其偏好列表如表4所示:

    表4偏好列表及参数设置Ⅱ

    User
    Preference list
    Quality
    a
    C>a B>a A
    3.5
    b
    C>b A>b B
    2.2
    c
    A>c B>c C
    1.2
    d
    A>d B>d C
    1.1
    e
    A>e B>e C
    1
    Job
    Preference list
    Budget
    A
    a>T b>T c>T d>T e
    3.5
    B
    a>T b>T c>T d>T e
    2
    C
    a>T b>T c>T d>T e
    1

    如表5所示,用户a挤走b与c,从而被任务A接纳,于是同
    理,和任务A接纳b的时间晚于c,于是,
    易于证明
    对于任务t,用户w的优
    先级高于中所有用户。Δb是任务分配结束时,任务t的可用余额,即Δb=qt-|μ(t)|r。

    反证法。假定用户w和任务t能构成可替换的不稳定组合,即任务t想移除w',从而
    接纳w。意味着w>T w',并且。与已匹配的任务μ(w)相比,用户w更愿意参与任务t,因此她先
    前肯定向任务t提出过申请,但出于某种愿意而被拒绝。而且,用户w'肯定是在用户w申请失
    败后,才被分配给任务t的。若先于w申请,用户w'已被分配给任务t,于是,
    其中是用户w向任务t提出申请时任务t的可用余额。根据算法1,
    任务t将移除用户w',从而接纳用户w。由此可知,用户w'肯定是在用户w申请失败后,再向任
    务t提出申请并被接纳。当用户w向任务t提出申请时,存在中所有用户被匹
    配给任务t,但中所有用户的优先级均低于w,则而且
    于是,用户w应被分配给任务t,而不是被任务t拒绝,这与假设不相符。用
    户w和任务t不可能形成可替换的不稳定对。因此,本专利提出的任务分配算法是公平的。

    表5公平性感知的任务分配运行实例

    Iteration
    Action
    Result
    1
    a applies to job C
    μ(A)=Φ,μ(B)=Φ,μ(C)=Φ
    2
    bapplies to job C
    μ(A)=Φ,μ(B)=Φ,μ(C)=Φ
    3
    capplies to job A
    μ(A)={c},μ(B)=Φ,μ(C)=Φ
    4
    dapplies to job A
    μ(A)={c,d},μ(B)=Φ,μ(C)=Φ
    5
    eapplies to job A
    μ(A)={c,d,e},μ(B)=Φ,μ(C)=Φ
    6
    aapplies to job B
    μ(A)={c,d,e},μ(B)=Φ,μ(C)=Φ
    7
    bapplies to job A
    μ(A)={b,c},μ(B)=Φ,μ(C)=Φ
    8
    dapplies to job B
    μ(A)={b,c},μ(B)={d},μ(C)=Φ
    9
    eapplies to job B
    μ(A)={b,c},μ(B)={d},μ(C)=Φ
    10
    aapplies to job A
    μ(A)={a},μ(B)={d},μ(C)=Φ
    11
    bapplies to job B
    μ(A)={a},μ(B)={d},μ(C)=Φ
    12
    capplies to job B
    μ(A)={a},μ(B)={c},μ(C)=Φ
    13
    dapplies to job C
    μ(A)={a},μ(B)={c},μ(C)=Φ
    14
    e applies to job C
    μ(A)={a},μ(B)={c},μ(C)={e}

    综上所述,本方法提出的任务分配算法兼具非浪费性和公平性,因此该算法能产
    生匹配结果是稳定的。

    四、本发明方法的性能分析

    本发明方法(图例中的Proposed scheme)与已有工作Anchor算法进行比较,两者
    均基于多对一匹配算法,区别在于拒绝策略不相同。Anchor将多对一匹配算法用于云计算
    平台的代理间的匹配问题。在Anchor中,若用户s被拒绝,则所有优先级低于s的用户均被拒
    绝。而本发明方法尽可能地利用预算,接受尽可能多的用户,为每项任务提供最佳服务质
    量。

    用户数量、任务数量以及任务的平均预算限制与用户的幸福指数之间的关系见图
    2-图4。

    用户的幸福指数被定义为该用户被匹配的百分位。例如,给定5个任务,若用户被
    匹配到其偏好列表中排名第一的任务,则该用户的幸福指数为100%;若若用户被匹配到其
    偏好列表中排名第二的任务,则该用户的幸福指数为80%;若用户未被匹配到任何任务,则
    该用户的幸福指数为0%;

    如图2所示,随着用户数量增加,用户的幸福指数降低,本发明方法的用户幸福指
    数明显高于Anchor。原因在于用户数量越多,竞争越激烈,用户的幸福指数因而降低。

    如图3所示,随着任务数量的增加,用户的幸福指数增加,本发明方法的用户幸福
    指数明显高于Anchor。当任务数为6时,本发明方法的用户幸福指数是Anchor的2倍。原因在
    于随着任务的增多,用户的选择更多,用户的幸福指数因而增加。

    如图4所示,随着任务预算的增加,用户的幸福指数增加,本发明方法的用户幸福
    指数明显高于Anchor。原因在于每项任务有充足的预算可接纳更多的用户,用户的幸福指
    数因而增加。

    用户数量、任务数量以及任务平均预算限制与算法运行时间之间的关系见图5-图
    7。图5-图7证实本专利提出的算法能在短时间内收敛,并得到一个稳定的任务分配结果。

    如图5所示,随着用户数量的增加,算法的运行时间线性增加,本发明方法的运行
    时间大于Anchor。

    如图6所示,随着任务数量的增加,算法的运行时间线性增加,本发明方法的运行
    时间大于Anchor。

    如图7所示,随着任务预算的增加,算法的运行时间保持不变,本发明方法的运行
    时间大于Anchor。

    Anchor的运行时间小于本发明所提出的运行时间。但是Anchor未能充分利用任务
    的预算,且Anchor产生的匹配结果不满足非浪费性,匹配结果不稳定。本专利所提的方法以
    少量时间为代价,使得匹配结果的性能得到大大提升。

    关 键 词:
    系统 兼顾 用户 异质性 偏好 任务 分配 方法
      专利查询网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
    关于本文
    本文标题:众包系统中兼顾用户异质性与用户偏好的任务分配方法.pdf
    链接地址://www.4mum.com.cn/p-6092839.html
    关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服客服 - 联系我们

    [email protected] 2017-2018 www.4mum.com.cn网站版权所有
    经营许可证编号:粤ICP备17046363号-1 
     


    收起
    展开
  • 四川郎酒股份有限公司获第十二届人民企业社会责任奖年度环保奖 2019-05-13
  • 银保监会新规剑指大企业多头融资和过度融资 2019-05-12
  • 韩国再提4国联合申办世界杯 中国网友无视:我们自己来 2019-05-11
  • 中国人为什么一定要买房? 2019-05-11
  • 十九大精神进校园:风正扬帆当有为 勇做时代弄潮儿 2019-05-10
  • 粽叶飘香幸福邻里——廊坊市举办“我们的节日·端午”主题活动 2019-05-09
  • 太原设禁鸣路段 设备在测试中 2019-05-09
  • 拜耳医药保健有限公司获第十二届人民企业社会责任奖年度企业奖 2019-05-08
  • “港独”没出路!“梁天琦们”该醒醒了 2019-05-07
  • 陈卫平:中国文化内涵包含三方面 文化复兴表现在其中 2019-05-06
  • 人民日报客户端辟谣:“合成军装照”产品请放心使用 2019-05-05
  • 【十九大·理论新视野】为什么要“建设现代化经济体系”?   2019-05-04
  • 聚焦2017年乌鲁木齐市老城区改造提升工程 2019-05-04
  • 【专家谈】上合组织——构建区域命运共同体的有力实践者 2019-05-03
  • 【华商侃车NO.192】 亲!楼市火爆,别忘了买车位啊! 2019-05-03