一种去中心化群智感知系统中的分布式最优拍卖方法

技术领域

本发明涉及一种针对去中心化群智感知系统的分布式最优拍卖方法，特别涉及一种基于不可信参与者构建的群智感知系统中的高效的任务分配和分布式激励方法。

背景技术

作为一种典型的共享经济应用，移动群智感知系统(mobile crowd sensingsystems)提供了一种绝佳的高效利用群体智慧的实践方式。移动群智感知系统将广阔的城市区域内闲置的各种各样的传感器有机结合，统一的调度和分配，以极低的部署成本构建智慧城市应用。这些传感器可以来自人携带的智能手机、平板电脑等各种移动设备，也可以嵌入在各种智能车辆、智能道路基础设施中。传感器的种类非常丰富，常见的传感器包括定位装置、麦克风、摄像头、相机、加速计、陀螺仪、温度计、湿度计等，因此各类传感器可以提供非常丰富的环境感知数据。由于移动群智感知系统的各种参与方来自不同的组织或个人，收集和传输感知数据会耗费资源，各种参与方缺乏为系统提供有效的感知数据的动机。为此，现有的各种群智感知系统引入激励，鼓励尽可能多的参与方参与进来。但现有方法忽略了中心化群智感知系统带来的各种风险，比如隐私泄露、索要过高的交易费、恶意操作市场价格等。

本发明考虑针对去中心化群智感知系统的一种分布式最优拍卖方法。移动群智感知系统中有通常有两大类参与方，各种移动智能设备被认为是提供感知服务的劳动者，发布感知需求的个人或组织被认为是消费感知服务的需求方。需求方可以雇佣劳动者执行感知任务，并且给劳动者提供适当的报酬作为补偿或奖励。完成一个感知任务被带来一定的社会效益，其数量与参与的劳动者的成本和需求方对感知任务的估值有关，而需求方支付给劳动者的报酬决定了社会效益在二者之间的分割方案。在去中心化场景下如何高效的匹配需求方和劳动者的需求、优化群智感知的社会效益，需要解决分配问题、激励问题和组织问题这三大关键问题。分配问题指的是有效的匹配需求方的感知任务和劳动者，使总体的社会效益最大化。激励问题指的是给需求方和劳动者恰当的激励，也就是设计合理的报酬，保证参与的各方都满意并且愿意积极参与到群智感知系统中。组织问题指的是在一种完全分布式的环境下组织需求方和劳动者之间的交易过程。本发明基于区块链技术搭建去中心化场景下的群智感知系统，并在此基础上设计了一种分布式最优拍卖方法解决了上述三个关键问题。

针对去中心化群智感知系统设计分布式最优拍卖方法面临着许多挑战。首先，所有的参与方都是自私的，即每个参与方总是期望获得尽可能多的收益。其次，劳动者的成本和需求方的估值都是参与方的私有信息，他们并不愿意向外披露这些信息。最后，各个参与方是不可信的，信任风险也会降低的劳动者和需求方的参与意愿，不利于系统的整体效率和稳定性。参与方的不可信行为可能包括一些为了提升自身收益的恶意行为，比如需求方故意拒绝为正常执行的感知任务支付报酬。

发明内容

本发明的目的是：提供了一种针对去中心化和不可信参与方场景下的群智感知系统的分布式最优拍卖方法。

为了达到上述目的，本发明的技术方案是提供了一种去中心化群智感知系统中的分布式最优拍卖方法，适用于在城市区域中利用大量的、广泛分布的、来源广泛的各类智能设备上的传感器资源构建大规模智能应用的问题，所述分布式最优拍卖方法针对去中心化群智感知系统进行设计，所述分布式最优拍卖方法在基于区块链系统和智能合约技术构建的公开的和可信的去中心化交易平台上以完全分布式的形式解决任务分配和报酬计算及兑付问题，达到最优化的社会效益，其特征在于，所述分布式最优拍卖方法包括以下步骤：

步骤1、初始时，各参与方在去中心化交易平台上注册；

步骤2、分布式拍卖过程重复进行多轮，每一轮包含以下步骤：

步骤201、初始化拍卖过程，每轮开始时更新参与方的注册信息；

步骤202、需求方发布感知任务需求；

步骤203、劳动者不断提交竞拍标书，降低感知任务的竞拍价格，平台根据竞拍标书确定当前的分配方案和当前各个感知任务的交易价格，交易过程不断迭代直到满足一定停止条件时得到最终的分配方案和交易价格；

步骤204、相关的劳动者根据最终的分配方案执行分配的感知任务并上传感知数据，需求方确认数据后根据最终的交易价格兑付报酬；

步骤205、去中心化交易平台更新每个参与方的可信度评分。

优选地，步骤201中，更新参与方的注册信息包括增加新参与方、移除注销的或因为可信度低被拒绝的参与方。

优选地，步骤202中，需求方发布的感知任务需求包含任务描述、初始交易价格，同时支付一笔数额等于两倍初始交易价格的押金。

优选地，所述步骤203包括以下步骤：

去中心化交易平台维护一个分配方案集合和一个未被分配感知任务的劳动者的集合；此时，分配方案集合为空集，未被分配感知任务的劳动者的集合包含所有的劳动者；之后未被分配感知任务的劳动者的集合中的所有劳动者互相竞争直到被分配某个感知任务，包括：

步骤2031、每个未被分配感知任务的劳动者查询当前所有感知任务的交易价格，如果某个劳动者发现选择任何感知任务都无法获取非负的收益，即任何一个感知任务的报酬都不高于他的成本，该劳动者退出本轮拍卖，通知去中心化交易平台将他从未被分配感知任务的劳动者的集合中移除；

步骤2032、每个未被分配感知任务的劳动者根据自己执行各个感知任务的成本，选择最优的感知任务，并针对这个感知任务提交一个竞拍标书，竞拍标书中包含感知任务序号、竞拍价格，其中，竞拍价格严格低于该感知任务的当前交易价格；

步骤2033、去中心化交易平台根据收到的竞拍标书更新各个感知任务的当前交易价格、分配方案和未被分配感知任务的劳动者的集合；如果存在针对某个任务的竞拍标书，那么选择竞拍价格最低的劳动者作为该感知任务的获胜者，将该感知任务和该劳动者构成的一个分配添加到分配方案替代原有的分配，若该任务此前并没有出现在分配方案中，则无需替代；该感知任务的交易价格更新成当前最低的竞拍价格，获胜的劳动者从未被分配感知任务的劳动者的集合中移除，若有被替代的劳动者，则该被替代的劳动者添加到未被分配感知任务的劳动者的集合；

步骤2034、重复步骤2031至步骤2033直至未被分配感知任务的劳动者的集合变成空集，按照最后的分配方案和交易价格执行交易。

优选地，步骤205中，去中心化交易平台更新每个参与方的可信度评分，如果参与方的可信度低于设定的阈值，将会被视为无效参与方，并且无法参加后续轮次的交易过程。

优选地，步骤202中，每个需求方的决策是确定初始交易价格，初始交易价格设定为需求方的估值减去一个很小的正数，需求方自行选择随机选取这个正数，这样的决策可以隐藏需求方的私有信息。

优选地，步骤2032中，每个未被分配感知任务的劳动者的决策是选择为哪个感知任务投标以及竞拍价格；选择收益最高的感知任务作为投标任务，劳动者的收益是该任务的报酬与该任务的成本之差；为了提交一个严格递减的竞拍价格，劳动者随机选取一个很小的正数作为最小降价幅度。

优选地，计算任务的竞拍价格的步骤如下：

(1)计算当前的最高收益；

(2)计算当前第二高的收益，如果第二高收益小于0，也就是除了最高收益的感知任务之外无法从其他任务获益，那么将第二高收益视为0；

(3)计算最高收益和第二高收益之差，再加上最小降价幅度作为本次竞拍的降价幅度，即本次竞拍价格等于该任务的当前交易价格减去降价幅度。

在本发明的在分布式拍卖过程中，拍卖中参与方只需要根据公开信息和自己的私有信息做简单的决策，拍卖过程经历多次迭代，感知任务的交易价格和参与者的决策在迭代过程中不断更新，直到得到一个稳定的交易价格，拍卖结束。

本发明引入了分布式拍卖过程来组织参与方的交易过程，从而最优化社会效益、提供合适的激励和保护隐私信息。在分布式拍卖过程中，拍卖中参与方只需要根据公开信息和自己的私有信息做简单的决策，拍卖过程经历多次迭代，感知任务的交易价格和参与者的决策在迭代过程中不断更新，直到得到一个稳定的交易价格拍卖结束。最后的分配方案及交易价格对应的报酬被证明能够达到最优的社会效益。此外，本发明基于区块链系统和智能合约技术构建了一个公开的和可信的去中心化交易平台(后文中简称“平台”)，设计并部署了相关的智能合约来支撑分布式拍卖过程以及其中设计的激励机制和参与方可信度管理问题。

本发明的优点在于：

(1)本发明考虑群智感知系统的参与方的不可信风险，涉及的平台为部署实际的群智感知系统提供了有益的指导。

(2)本发明所述的分布式拍卖方法可以在平台上以完全分布式的形式解决任务分配和报酬计算及兑付问题，达到最优化的社会效益，因而方法的可实施性较好。

(3)本发明所述的分布式拍卖方法不需要参与者进行复杂的决策，也无需暴露参与者的私有信息，因而参与方的参与负担较小，更容易鼓励更多的参与者参与到系统中来。

本发明适用于在城市区域中利用大量的、广泛分布的、来源广泛的各类智能设备上的传感器资源构建大规模智能应用的问题，在基于区块链和智能合约构建的去中心化的平台上实施的分布式拍卖方法的模拟实验实验结果证明了本发明的可行性。

附图说明

图1是去中心化群智感知系统的架构；

图2是分布式拍卖方法的完整过程。

具体实施方式

下面结合具体实施例，进一步阐述本发明。应理解，这些实施例仅用于说明本发明而不用于限制本发明的范围。此外应理解，在阅读了本发明讲授的内容之后，本领域技术人员可以对本发明作各种改动或修改，这些等价形式同样落于本申请所附权利要求书所限定的范围。

本发明提供的分布式最优拍卖方法针对去中心化群智感知系统进行设计，本实施例中，如图1所示为基于区块链系统的去中心化群智感知系统的架构。该去中心化群智感知系统分为三个层次，自底向上分别是分布式存储层、区块链层及平台层。

分布式存储层主要用于存储任务需求、感知数据、分配方案、交易价格等各类交易过程中的数据。区块链层基于点对点网络和共识机制构架，主要功能是支撑去中心化的服务模式和应对信任风险。平台层主要用于组织各个参与方之间的交易过程，实施的是一种公开的、可信的、去中心化的服务模式。平台层基于部署的两个智能合约完成了任务分配、激励设计和兑付、参与方管理等问题。由于较低的两层(分布式存储层及区块链层)已有相关解决方案，本发明中采用现在流行的解决方案构建较低两层。重点关注平台层，在平台层上设计和部署最优的分布式拍卖算法。

本发明提供的分布式拍卖方法中，假设每轮需求方只能发布一项感知需求，劳动者也只能执行一项感知任务。如图2所示，本提供的分布式拍卖方法具体包括以下步骤：

(1)各参与方在平台上注册；

(2)每轮开始时更新参与方的注册信息，包括增加新参与方、移除注销的或因为可信度低被拒绝的参与方，每轮的拍卖过程包含步骤(3)至(13)的所有步骤；

(3)需求方发布感知任务需求，包含任务描述、初始交易价格，同时支付一笔数额等于两倍初始交易价格的押金；

(4)平台维护一个分配方案集合和一个未被分配感知任务的劳动者的集合；此时，分配方案集合为空集，未被分配感知任务的劳动者的集合包含所有的劳动者；之后未被分配感知任务的劳动者的集合中的所有劳动者互相竞争直到被分配某个感知任务，包含步骤(5)至步骤(8)的所有步骤；

(5)每个未被分配感知任务的劳动者查询当前所有感知任务的交易价格，如果某个劳动者发现选择任何感知任务都无法获取非负的收益，即任何一个感知任务的报酬都不高于他的成本，该劳动者退出本轮拍卖，通知平台将他从未被分配感知任务的劳动者的集合中移除；

(6)每个未被分配感知任务的劳动者根据自己执行各个感知任务的成本，选择最优的感知任务，并针对这个感知任务提交一个竞拍标书，竞拍标书中包含感知任务序号、竞拍价格，其中，竞拍价格严格低于该感知任务的当前交易价格；

(7)平台根据收到的竞拍标书更新各个感知任务的当前交易价格、分配方案和未被分配感知任务的劳动者的集合；如果存在针对某个任务的竞拍标书，那么选择竞拍价格最低的劳动者作为该感知任务的获胜者，将该感知任务和该劳动者构成的一个分配添加到分配方案替代原有的分配(如果该任务此前并没有出现在分配方案中，无需替代)；该感知任务的交易价格更新成当前最低的竞拍价格，获胜的劳动者从未被分配感知任务的劳动者的集合中移除，被替代的劳动者(如有)添加到未被分配感知任务的劳动者的集合；

(8)重复步骤步骤(5)-步骤(7)直至未被分配感知任务的劳动者的集合变成空集，按照最后的分配方案和交易价格执行交易；

(9)劳动者执行被分配的任务，上传感知数据；

(10)需求方获取感知数据，确认任务完成；

(11)劳动者获得最终交易价格对应的报酬，需求方取回额外支付的押金；

(12)平台更新每个参与方的可信度评分，如果参与方的可信度低于设定的阈值，将会被视为无效参与方，并且无法参加后续轮次的交易过程，跳转到步骤(2)开始下一轮。

上述步骤(3)中，每个需求方的决策是确定初始交易价格。初始交易价格设定为需求方的估值减去一个很小的正数。需求方自行选择随机选取这个正数。这样的决策可以隐藏需求方的私有信息。

上述步骤(6)中，每个未被分配感知任务的劳动者的决策是选择为哪个感知任务投标以及竞拍价格。选择收益最高的感知任务作为投标任务，劳动者的收益是该任务的报酬与该任务的成本之差。为了提交一个严格递减的竞拍价格，劳动者随机选取一个很小的正数作为最小降价幅度。计算该任务的竞拍价格的步骤如下：

(1)计算当前的最高收益；

(2)计算当前第二高的收益，如果第二高收益小于0，也就是除了最高收益的感知任务之外无法从其他任务获益，那么将第二高收益视为0；

(3)计算最高收益和第二高收益之差，再加上最小降价幅度作为本次竞拍的降价幅度，即本次竞拍价格等于该任务的当前交易价格减去降价幅度。