基于改进的反向Vickrey拍卖的社交云资源分配模型

删除或更新信息，请邮件至freekaoyan#163.com(#换成@)

本站小编 Free考研考试/2020-03-23

王学毅^1,2, 王兴伟^1,2, 黄敏³, 王尊¹
1. 东北大学软件学院，辽宁沈阳 110169;
2. 东北大学计算机科学与工程学院，辽宁沈阳 110169;
3. 东北大学信息科学与工程学院，辽宁沈阳 110819
收稿日期：2015-11-10
基金项目：国家杰出青年科学基金资助项目 (61225012, 71325002)；国家自然科学基金资助项目 (61572123)；高等学校博士学科点专项科研基金优先发展领域资助项目 (20120042130003)。
作者简介：王学毅 (1979-), 男, 辽宁辽阳人, 东北大学讲师, 博士研究生;
王兴伟 (1968-), 男, 辽宁盖州人, 东北大学教授, 博士生导师;
黄敏 (1968-), 女, 福建长乐人, 东北大学教授, 博士生导师。

摘要：由于经济学涉及人类社会中持有不同目的个体间的资源分配与定价，提出了一种基于改进的反向Vickrey拍卖的社交云资源分配模型.首先，给出了标的描述和动态的信任计算方法，提出了候选资源提供者选择方法，并将其整合到反向Vickrey拍卖中，使参与拍卖的资源提供者不仅可以是资源消费者的好友，又可以是具有较高信誉的非好友.其次，为了提高资源提供者的资源利用率，将超额预订机制引入到反向Vickrey拍卖中，并提出了资源的分配和定价方法.仿真结果表明该模型可行且有效.
关键词：社交云社交搜索反向Vickrey拍卖超额预订信任
Social Cloud Resource Allocation Model Based on Improved Reverse Vickrey Auction
WANG Xue-yi^1,2, WANG Xing-wei^1,2, HUANG Min³, WANG Zun¹
1. School of Software, Northeastern University, Shenyang 110169, China;
2. School of Computer Science & Engineering, Northeastern University, Shenyang 110169, China;
3. School of Information Science & Engineering, Northeastern University, Shenyang 110169, China
Corresponding author: WANG Xue-yi, E-mail: xywang@mail.neu.edu.cn
Abstract: Since economics is concerned with resource allocation among individuals with different objectives in human societies, a social cloud resource allocation model was proposed based on improved reverse Vickrey auction. First, the tender description and the dynamic trust calculation method were given. Then, a candidate resource provider selection method was proposed, and it was integrated into reverse Vickrey auctions to make the resource providers participating in the auction be not only friends of resource consumers, but also non-friends with high reputation. Finally, the overbooking mechanism was introduced into reverse Vickrey auction to improve the utilization of resource providers, and the allocation and pricing method was presented. The simulation results showed that the proposed model was feasible and effective.
Key Words: social cloudsocial searchreverse vickrey auctionoverbookingtrust
社交云^[1]是基于P2P结构构建的，每个用户单独拥有并管理自己的资源.通过聚集每个用户的资源，社交云可以提供比传统的中心式自治的云计算系统更弹性、性价比更高的资源分配方案.社交用户与其社交好友之间是通过一定的现实世界关系关联在一起的^[2]，因此他们之间会相互提供高质量的服务以便维系现实世界中的信誉.但是，由于在社交云中资源的分散性、异构性及不确定性^[3]，使资源分配与定价成为一项具有挑战性的工作.
许多学者提出通过市场机制来解决社交云资源有效分配问题.文献[4]将激励机制引入到社交云中以便设计一个可持续的、公平的资源共享机制.文献[5]提出了一种基于社交网络的云资源交换模型, 共享用户的计算资源.文献[6]提出了一个面向社交平台的新颖的协作模型，提供基础设施资源.文献[7]在现有的社交云资源分配方案的基础上引入了基于信誉定价和合作惩罚的激励机制，以便用户间可以公平、诚实地交易.文献[8]利用社交网络中已存在的社交关系，在好友间基于反向Vickrey拍卖 (RVA) 进行资源分配.但是，在文献[8]的RVA模型中资源分配仅限于好友之间，这样可能导致某些资源消费者找不到合适的资源提供者.另外，在一次反向Vickrey拍卖中，多个资源提供者参与拍卖并且在等待拍卖结果时资源提供者需要资源预留，但最后仅有一个胜标者，这样将导致失败者资源利用率较低.针对文献[8]中的RVA模型所存在的问题，提出了社交云环境下的一种基于改进的反向Vickrey拍卖 (IRVA) 的资源分配模型，主要贡献在于本文将超额预订机制^[9]引入到反向Vickrey拍卖中，以便提高资源提供者的资源利用率；同时提出一种候选资源提供者选择算法，并将其整合到改进的反向Vickrey拍卖中，使资源提供者不仅局限于资源消费者的好友，而且可以是信誉较高的非好友.
1 系统框架如图 1所示，本文所提出的基于改进的反向Vickrey拍卖的资源分配模型主要包含两个部分：社区云用户 (social cloud user, SCU) 和拍卖仲裁 (auction intermediary, AI).当一个SCU请求资源时，此时它是一个社交云资源消费者，记作SCRC；当一个SCU想要出售多余的资源时，此时它是一个社交云资源提供者，记作SCRP.
图 1(Fig. 1)

图 1 系统框架Fig.1 System framework

SCRP作为资源提供者主要负责确定要价和初始化卖方标的等；SCRC作为资源消费者主要负责资源发现、信誉计算、初始化买方标的和QoS评价等；AI主要负责收集标的、胜标确定、违约处理等.本文所提出的基于改进的反向Vickrey拍卖的社交云资源分配模型的基本流程描述如下：
1)? SCRC利用候选SCRP选择算法来确定能够为其提供所需资源的候选SCRP集合，详见2.3节.
2)? SCRC将其买方标的和候选SCRP集合提交给AI.
3)? AI发送拍卖邀请给所有的候选SCRP.
4)?收到邀请且愿意参加拍卖的候选SCRP提交卖方标的给AI.
5)? AI利用资源分配和定价算法来确定胜标的SCRP及收益，并将拍卖结果通知给胜标的SCRP，详见2.4节.
6)? SCRC付费给胜标的SCRP，并根据其QoS来进行评价.
2 反向Vickrey拍卖协议2.1 标的描述SCRC标的描述：CID表示SCRC的标识符；DRQV (demanding resource quantity vector) 是一个长度为n的向量，其表示SCRC所需求的各种类型资源的数量，其中DRQV_k表示SCRC所需求的R_k(k=1, 2, …, n) 类型资源的数量；BUD (budget) 表示SCRC对所需求资源的预算.SToDR (start time of demanding resource) 表示SCRC资源需求的开始时间；EToDR (end time of demanding resource) 表示SCRC资源需求的结束时间.Rep_min表示SCRC对SCRP信誉值的最低要求.
SCRP_j标的描述：PID表示SCRP_j的标识符；SRQV_j(supplying resource quantity vector) 是一个长度为n的向量，表示SCRP_j所提供的各种类型资源的数量，其中SRQV_j^k表示SCRP_j所提供的R_k(k=1, 2, …, n) 类型资源的数量；COS_j(cost) 是一个长度为n的向量，其表示SCRP_j所提供的各种类型资源的单位时间单位资源的成本，其中COS_j^k表示SCRP_j所提供的R_k(k=1, 2, …, n) 类型资源的单位时间单位资源的成本；SToSR_j (start time of supplying resource) 表示SCRP_j提供资源的开始时间；EToSR_j (end time of supplying resource) 表示SCRP_j提供资源的结束时间.
利用SCRC标的信息和SCRP_j标的信息，根据式 (1) 可以得到SCRP_j总的要价TAP_j:

(1)

2.2 动态的信任计算方法在本文中，信任关系仅存在于社交云中相邻的SCU之间，每个SCU_p记录着它和每个邻居SCU_q的信任值T_{SCU_p, SCU_q}∈[0,1]，信任值初始为0.5.如果某个SCU_o通过SCU_p，SCU_q间接与SCU_r相连，即SCU_o与SCU_p，SCU_p与SCU_q及SCU_q与SCU_r为邻居，则从SCU_o到SCU_r沿着路径path (SCU_o, SCU_r)={(SCU_o, SCU_p), (SCU_p, SCU_q), (SCU_q, SCU_r)}的信任值T_SCU_o, SCU_r为该路径上各个邻居间信任值的乘积：

(2)

在交易完成后，如果SCU_o使用了SCU_p推荐的资源并且做出了评价E，则SCU_o对SCU_p的信任值更新为

(3)

式中：

.
由于

，利用式 (4) 将其映射到[0,1]：

(4)

2.3 候选SCRP选择算法本文首先设计了一种利用已有的社交关系来进行信息搜索的方法，称为社交搜索.搜索信息类型主要分为两类：资源信息RES和信誉信息REP.资源查询消息Q_RES的格式为 (SCRC, RES, DRQV, SToDR, EToDR)，表示SCRC查询能够在[SToDR, EToDR]内提供DRQV资源的SCRP；资源应答消息R_RES的格式为 (SCRP_j, SCRC)，表示SCRP_j能够提供SCRC所需要的资源.信誉查询消息Q_REP的格式为 (SCU, REP, PATH, SCU_l)，表示当前的SCU查询能够提供SCU_l信誉信息的SCU，其中PATH为推荐路径，在每次转发之前将当前的SCU加入到PATH中；信誉应答消息R_REP的格式为 (SCU_r, SCU_g, SCU_l, PATH, T_{SCU_r, …, SCU_g}, E_gl)，表示SCU_g可以提供关于SCU_l的信誉信息为E_gl，其中SCU_r为此消息的发送者，PATH为推荐路径，T_{SCU_r, …, SCU_g}为SCU_r对SCU_g的信任值.另外，在推荐路径PATH上的每个SCU仅计算T_PATH的一部分，例如，对于路径PATH (SCU₁, SCU₂, SCU₃, SCU₄), SCU₃将传递T_{SCU₃, SCU₄}给SCU₂，然后SCU₂将计算T_{SCU₂, SCU₃, SCU₄}=T_{SCU₂, SCU₃}×T_{SCU₃, SCU₄}, 并将其传递给SCU₁，最后SCU₁计算T_{SCU₁, SCU₂, SCU₃, SCU₄}=T_{SCU₁, SCU₂}× T_SCU₂, _{SCU₃, SCU₄}.社交搜索方法的具体过程如下所示.
1)? SCRC根据搜索条件来初始化查询消息Q，并将Q转发给它的所有邻居.
2)?每个邻居收到查询消息Q后，如果有相关的信息，则返回应答消息R；否则，将Q转发给它的所有邻居.
当某个SCRC请求资源来完成任务时，可以通过候选SCRP选择算法来确定候选的SCRP集合，其具体过程描述如下.

2.4 资源分配与定价算法本文将反向Vickrey拍卖分为两个阶段.在第一阶段，如果胜标的SCRP违约，那么在不包括违约者的情况下重新计算胜标者.这种技术可以增加系统的资源利用率.然而这种方法可能会增加SCRC的成本，因为替代价格会高于以前的胜标价格.同时，由于反向Vickrey拍卖自身所具有的特点，即可以使每个参与拍卖SCRP以真实的成本报价^[10]，因此，违约不会造成购买成本大幅度增加.在本文中，为了使SCRC的购买成本保持不变，购买成本增加部分由违约的SCRP共同平均承担.而在第二阶段，如果胜标的SCRP违约，其将收到严厉的惩罚.具体资源分配与定价算法描述如下.

3 仿真与评价在CloudSim平台上实现了本文所提出的IRVA模型.SCU所需求的资源采用了谷歌集群数据^[11]，资源价格的设置参考了Amazon云的定价^[12].在CloudSim环境下利用事件驱动模型，每个SCU的资源需求按照泊松分布周期性地产生.另外，利用了LiveJournal^[13]的数据集来构建社交网络中的朋友关系.将其与文献[8]中的反向Vickrey拍卖模型 (RVA) 进行比较，主要比较指标有总购买成本、总成功完成任务数、平均资源利用率和平均请求处理时间.
如图 2所示，当SCU的个数分别为30，60，100和200时，IRVA在总购买成本上总是明显优于RVA.因为在IRVA中，SCRC不仅可以与朋友SCRP交易，也可以与满足信誉要求的非朋友SCRP交易，这样可以使SCRP间更加充分地竞争，进一步降低购买成本.
图 2(Fig. 2)

图 2 SCU数目对总购买成本的影响Fig.2 Effect of SCU number on total purchase cost

如图 3所示，随着SCU数量的不断增加，总成功完成任务数也不断增加，RVA和IRVA的差距也在不断缩小.因为随着SCU数量的不断增加，可以提供的资源也越来越充足.IRVA在总成功完成任务数方面的性能上总是优于RVA，因为在RVA中，由于一些SCU已经参与了某些拍卖，在拍卖结果没有公布之前就不能参与其他的拍卖，其相应资源只能暂时预留.
图 3(Fig. 3)

图 3 SCU数目对总成功执行任务数的影响Fig.3 Effect of SCU number on number of total successful tasks

如图 4所示，当SCU的个数分别为30，60，100和200时，IRVA在平均资源利用率上总是明显优于RVA，其原因是在IRVA中引入的超额预订机制.
图 4(Fig. 4)

图 4 SCU数目对平均资源利用率的影响Fig.4 Effect of SCU number on average utilization

如图 5所示，在IRVA中每个请求的平均处理时间要高于在RVA中每个请求的平均处理时间.随着SCU数量的增加，在IRVA中每个请求的平均处理时间明显增加，但IRVA也有很多优点，例如降低购买成本、提高成功完成任务数和资源利用率.
图 5(Fig. 5)

图 5 SCU数目对平均请求处理时间的影响Fig.5 Effect of SCU number on average request handling time

4 结论为了增加资源提供者的数量，本文提出了候选资源提供者的选择算法，并将其整合到反向Vickrey拍卖中.同时，本文将超额预订机制引入到反向Vickrey拍卖中，以便提高资源提供者的资源利用率.仿真结果表明本文所提出的基于改进反向Vickrey拍卖的资源分配模型在购买成本、总成功完成任务数和平均资源利用率方面的性能要优于RVA.
参考文献

[1]	Chard K, Bubendorfer K, Caton S, et al. Social cloud computing:a vision for socially motivated resource sharing[J].IEEE Transaction on Services Computing, 2012, 5(4): 551–563.DOI:10.1109/TSC.2011.39
[2]	Punceva M, Rodero I, Parashar M, et al.Incentivising resource sharing in social clouds[C]// International Workshop on Enabling Technologies.Newport Beach:IEEE, 2012:185-190.
[3]	Mathijs M, Zhang Y, Klos T. Multiagent task allocation in social networks[J].Autonomous Agents and Multi-Agent Systems, 2012, 25(1): 46–86.DOI:10.1007/s10458-011-9168-3
[4]	Haas C, Caton S, Weinhardt C.Engineering incentives in social clouds[C]// International Symposium on Cluster, Cloud and Grid Computing.Newport Beach:IEEE, 2011:572-575.
[5]	Ali Z, Rasool R U, Bloodsworth P.Social networking for sharing cloud resources[C]// International Conference on Cloud and Green Computing.Xiangtan:IEEE, 2012:160-166.
[6]	Haas C, Caton S, Chard K, et al.Co-operative infrastructures:an economic model for providing infrastructures for social cloud computing[C]// International Conference on System Sciences.Wailea Maui HI:IEEE, 2013:729-738.
[7]	Zhang Y, van der Schaar M. Incentive provision and job allocation in social cloud systems[J].IEEE Journal on Selected Areas in Communications, 2013, 31(9): 607–617.DOI:10.1109/JSAC.2013.SUP.0513053
[8]	Chard K, Caton S, Rana O, et al.Social cloud:cloud computing in social networks[C]// International Conference on Cloud Computing.Miami:IEEE, 2010:99-106.
[9]	Birkenheuer G, Brinkmann A, Karl H.The gain of overbooking[C]// International Workshop Job Scheduling Strategies for Parallel Processing.Berlin:Springer, 2009:80-100.
[10]	Krishna V. Auction theory[M]. New York: Academic Press, 2009: 185-202.
[11]	Liu Z, Cho S.Characterizing machines and workloads on a google cluster[C]// International Conference on Parallel Processing Workshops.Pittsburgh:IEEE, 2012:397-403.
[12]	Shang S, Jiang J, Wu Y, et al.A knowledge-based continuous double auction model for cloud market[C]// International Conference on Semantics Knowledge and Grid.Ningbo:IEEE, 2010:129-134.
[13]	Backstrom L, Huttenlocher D, Kleinberg J, et al.Group formation in large social networks:membership, growth, and evolution[C]// International Conference on Knowledge Discovery and Data Mining.Philadelphia:ACM, 2006:44-54.