2017, Vol. 38
2. 东北大学 计算机科学与工程学院，辽宁 沈阳 110169;
3. 东北大学 信息科学与工程学院，辽宁 沈阳 110819
2. School of Computer Science & Engineering, Northeastern University, Shenyang 110169, China;
3. School of Information Science & Engineering, Northeastern University, Shenyang 110169, China
社交云[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 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所需求的各种类型资源的数量，其中DRQVk表示SCRC所需求的Rk(k=1, 2, …, n) 类型资源的数量；BUD (budget) 表示SCRC对所需求资源的预算.SToDR (start time of demanding resource) 表示SCRC资源需求的开始时间；EToDR (end time of demanding resource) 表示SCRC资源需求的结束时间.Repmin表示SCRC对SCRP信誉值的最低要求.
SCRPj标的描述：PID表示SCRPj的标识符；SRQVj(supplying resource quantity vector) 是一个长度为n的向量，表示SCRPj所提供的各种类型资源的数量，其中SRQVjk表示SCRPj所提供的Rk(k=1, 2, …, n) 类型资源的数量；COSj(cost) 是一个长度为n的向量，其表示SCRPj所提供的各种类型资源的单位时间单位资源的成本，其中COSjk表示SCRPj所提供的Rk(k=1, 2, …, n) 类型资源的单位时间单位资源的成本；SToSRj (start time of supplying resource) 表示SCRPj提供资源的开始时间；EToSRj (end time of supplying resource) 表示SCRPj提供资源的结束时间.
利用SCRC标的信息和SCRPj标的信息，根据式 (1) 可以得到SCRPj总的要价TAPj:
|
(1) |
在本文中，信任关系仅存在于社交云中相邻的SCU之间，每个SCUp记录着它和每个邻居SCUq的信任值TSCUp, SCUq∈[0,1]，信任值初始为0.5.如果某个SCUo通过SCUp，SCUq间接与SCUr相连，即SCUo与SCUp，SCUp与SCUq及SCUq与SCUr为邻居，则从SCUo到SCUr沿着路径path (SCUo, SCUr)={(SCUo, SCUp), (SCUp, SCUq), (SCUq, SCUr)}的信任值TSCUo, SCUr为该路径上各个邻居间信任值的乘积：
|
(2) |
在交易完成后，如果SCUo使用了SCUp推荐的资源并且做出了评价E，则SCUo对SCUp的信任值更新为
|
(3) |
式中：
由于
|
(4) |
本文首先设计了一种利用已有的社交关系来进行信息搜索的方法，称为社交搜索.搜索信息类型主要分为两类：资源信息RES和信誉信息REP.资源查询消息QRES的格式为 (SCRC, RES, DRQV, SToDR, EToDR)，表示SCRC查询能够在[SToDR, EToDR]内提供DRQV资源的SCRP；资源应答消息RRES的格式为 (SCRPj, SCRC)，表示SCRPj能够提供SCRC所需要的资源.信誉查询消息QREP的格式为 (SCU, REP, PATH, SCUl)，表示当前的SCU查询能够提供SCUl信誉信息的SCU，其中PATH为推荐路径，在每次转发之前将当前的SCU加入到PATH中；信誉应答消息RREP的格式为 (SCUr, SCUg, SCUl, PATH, TSCUr, …, SCUg, Egl)，表示SCUg可以提供关于SCUl的信誉信息为Egl，其中SCUr为此消息的发送者，PATH为推荐路径，TSCUr, …, SCUg为SCUr对SCUg的信任值.另外，在推荐路径PATH上的每个SCU仅计算TPATH的一部分，例如，对于路径PATH (SCU1, SCU2, SCU3, SCU4), SCU3将传递TSCU3, SCU4给SCU2，然后SCU2将计算TSCU2, SCU3, SCU4=TSCU2, SCU3×TSCU3, SCU4, 并将其传递给SCU1，最后SCU1计算TSCU1, SCU2, SCU3, SCU4=TSCU1, SCU2× TSCU2, SCU3, SCU4.社交搜索方法的具体过程如下所示.
1) SCRC根据搜索条件来初始化查询消息Q，并将Q转发给它的所有邻居.
2) 每个邻居收到查询消息Q后，如果有相关的信息，则返回应答消息R；否则，将Q转发给它的所有邻居.
当某个SCRC请求资源来完成任务时，可以通过候选SCRP选择算法来确定候选的SCRP集合，其具体过程描述如下.
|
本文将反向Vickrey拍卖分为两个阶段.在第一阶段，如果胜标的SCRP违约，那么在不包括违约者的情况下重新计算胜标者.这种技术可以增加系统的资源利用率.然而这种方法可能会增加SCRC的成本，因为替代价格会高于以前的胜标价格.同时，由于反向Vickrey拍卖自身所具有的特点，即可以使每个参与拍卖SCRP以真实的成本报价[10]，因此，违约不会造成购买成本大幅度增加.在本文中，为了使SCRC的购买成本保持不变，购买成本增加部分由违约的SCRP共同平均承担.而在第二阶段，如果胜标的SCRP违约，其将收到严厉的惩罚.具体资源分配与定价算法描述如下.
|
在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 SCU数目对总购买成本的影响 Fig.2 Effect of SCU number on total purchase cost |
如图 3所示，随着SCU数量的不断增加，总成功完成任务数也不断增加，RVA和IRVA的差距也在不断缩小.因为随着SCU数量的不断增加，可以提供的资源也越来越充足.IRVA在总成功完成任务数方面的性能上总是优于RVA，因为在RVA中，由于一些SCU已经参与了某些拍卖，在拍卖结果没有公布之前就不能参与其他的拍卖，其相应资源只能暂时预留.
|
图 3 SCU数目对总成功执行任务数的影响 Fig.3 Effect of SCU number on number of total successful tasks |
如图 4所示，当SCU的个数分别为30，60，100和200时，IRVA在平均资源利用率上总是明显优于RVA，其原因是在IRVA中引入的超额预订机制.
|
图 4 SCU数目对平均资源利用率的影响 Fig.4 Effect of SCU number on average utilization |
如图 5所示，在IRVA中每个请求的平均处理时间要高于在RVA中每个请求的平均处理时间.随着SCU数量的增加，在IRVA中每个请求的平均处理时间明显增加，但IRVA也有很多优点，例如降低购买成本、提高成功完成任务数和资源利用率.
|
图 5 SCU数目对平均请求处理时间的影响 Fig.5 Effect of SCU number on average request handling time |
为了增加资源提供者的数量，本文提出了候选资源提供者的选择算法，并将其整合到反向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. |