基于不完全信息博弈的网格资源分配方法研究

摘要：针对网格环境下用户难以获得资源竞价所需的信息而导致的决策风险，将不完全信息资源竞价转化成完全信息下的重复博弈问题。分析了该博弈均衡解的存在性及求解过程，给出了相应的竞价算法，讨论了对用户低价联盟的抑制方法。仿真实验表明用户通过各阶段资源预配置的信息调整竞价策略，资源配置可逐步逼近均衡解，实现网格资源的优化配置。

关键词：不完全信息； 重复博弈； 网格计算； 资源配置

中图分类号：TP393 文献标识码：A文章编号：2095-2163（2014）01-0006-04

0引言

经济网络[1-3]将资源提供者和网格用户的需求使用一定的价值表述，通过成本和收益等经济约束描述网格环境[4]下用户与资源之间的交互行为，有助于建立高可扩展性的网格系统。

早期经济网格的研究普遍采用商品市场[5-7] 机制或拍卖[8]机制，但商品市场机制忽略了单个用户的个体行为对资源价格的影响作用，与实际情况有较大偏差，而拍卖机制则依赖于第三方（如拍卖师）的公正性。此外，另有一些研究[9-11]将用户之间对资源的竞争使用看作一个博弈过程，在完全信息前提下通过分析均衡价格策略组合来求解网格资源优化配置方法，但基于完全信息的前提要求用户掌握其他用户的详细信息，这在动态、自治的网格环境中是难以实现的。

本文分析了不完全信息情况下的网格环境中用户对资源竞价的情况，通过“虚拟用户”的方式将不完全信息情况下的资源博弈转化成完全信息下的重复博弈。给出用户竞价算法及近似均衡解，克服用户对竞价信息的依赖，避免了用户盲目竞价决策的风险，实现资源的优化配置。

1不完全信息资源竞价模型

设N个用户竞争使用一个有M+1个中间节点的通信链路，节点k和k+1之间的通信带宽为Rk，用户使用资源并付费，系统按用户的出价比例分配资源，用户的目标是在预算范围内使用资源，且使得数据传输时间最短。模型各参数设定如下：

{Rk}为各通信链路的传输带宽。{qki}表示经过中间节点k后经通信资源Rk传输的来自用户i的数据包长度。Ci为用户的总预算。{Cki}表示用户i对资源k的出价，且∑Mk=1cki≤Ci。aik为用户i在资源Rk上的出价比例。Ck为第k个资源上所有用户的竞价和。tkip、tkic分别表示任务qkr在资源k上的传输时间和任务qki到达新节点后的处理时间。为了简化分析，设数据处理时间与数据包长度成正比例关系。tki表示任务qki完成时间，tki=tkip+tkic。ck为资源Rk的保留底价，保留底价是资源所有者对资源使用成本的评估。只有当用户出价和不低于ck时，资源提供者才有意愿向用户提供资源。

2竞价问题分析

2.1多用户不完全信息博弈问题的转换

虽然用户i难以获得所有其他用户的相关信息，但每个用户对自己的出价cki信息是可知的，而相应可获得的资源数rki则由系统返回。由于资源总量Rk是已知的，对于按竞价比例配置资源的方式，用户即可通过Rk和rki获得其他所有用户的竞价ck-i和资源数rk-i。由此推知，理性用户在拥有私有信息rki、cki基础之上，再获得可用资源总数Rk一个公共信息就可以测算出所有其他用户竞价的信息。

在此，可将除用户i外所有其他用户的集合虚拟为用户-i。其中，用户i的竞价信息为（cki，rki），用户类型-i的竞价信息为（ck-i，rk-i），则多用户不完全信息的资源博弈可转变成两个用户集合i和-i在完全信息下的资源博弈，并据此而得到资源配置的均衡解{c*i}。第1期林晓鹏：基于不完全信息博弈的网格资源分配方法研究智能计算机与应用第4卷

2.2竞价策略的求解

3.3用户低价联盟的抑制

因重复竞价博弈中用户在博弈的后续阶段可对前期的竞价策略进行调整，理性用户可能会在竞价初期隐藏自己的真实目的，在前期阶段以低价进行竞价而导致延长资源配置过程。或者用户之间也可能达成某种默契形成竞价联盟，联合以低价获得资源的使用权，导致资源提供者的收益可能低于资源的使用成本。

为了防止这种情况发生，设定每个资源的使用者也都参与到资源竞价中，竞价过程中资源所有者设定为虚拟用户ξ，利用预先设定的保留价格ckξ参与资源竞价。通过虚拟用户的竞价，使得当资源价格低于保留价格ckξ时降低可供应的资源数量，促使用户通过提高竞价来获得更好的资源，以保障资源方的利益。

4仿真结果和分析

4.1仿真环境

文中运用Gridsim仿真软件包来构建网格用户、网格资源、GIS等各个网格实体。各实体之间由消息机制进行竞价过程的消息传递。仿真中资源数为M=10，各用户总预算为100～400GCU（Grid Currency Unit）之间的随机数，各资源能力、用户数据包长度分别在范围1 000～5 000（Mbps）和0～5 000（Mb）内正态分布。不考虑消息传递代价，竞价博弈的初始阶段用户按相同的单位任务费用分配预算。

4.2结果分析

当所有用户竞价价格∑Ni=1 cki

5结束语

在用户对资源进行竞价过程中，需要掌握其他用户的资源使用策略，或者依赖于公正的第三方才能做出正确的策略图3 博弈过程用户的总执行时间变化选择。在实际网格环境中，现竞价有关的其他用户信息则难以获得。本文提出了基于重复博弈按出价比例分配网格计算资源的模型、求解方法和算法实现，将不完全信息下多用户竞价博弈转化为完全信息下两个用户竞价博弈，降低了用户竞价的复杂性。

用户在重复博弈的每个阶段通过对所获资源比例等信息来分析其他用户的资源使用策略，按照优化目标对下一阶段的出价进行调整，可在掌握少量信息情况下，达到趋近于均衡的竞价策略，实现用户优化目标下的资源分配。通过资源保留价格，可防止用户合谋低价使用资源，保障资源提供者的利益，进一步促使用户理性使用资源。

参考文献：

[1]MACKIE J K， VARIAN H R. Pricing the internet[EB/01]. http：//ideas.repec.org/p/wpa/wuwpco/9401002.html.

[2]CHRISTOS H P. Algorithms， Game， and Internet[EB/01]. http：//eecs.harvard.edu/～parkes/cs286r/spring02/papers/stoc01.pdf.

[3]BUYYA R， ABRAMSON D， VENUGOPAL S. The grid economy[J]. Proceedings of the IEEE， 93（3）：698-714.

[4]FOSTER I， KESSELMAN C， TUECKE S. The anatomy of the grid： Enabling scalable virtual organizations. Intl Journal of Supercomputer Applications， 2001，15（3）：200-222. [doi： 10.1177/109434200101500302].

[5]FERGUSON D， YEMINI Y， NICKOLAOU C. Microeconomic algorithms for load balancing in distributed computer systems[C]//Proceedings of the 8th International Conference on Distributed Computer System（ICDCS88），1988：491-499.

[6]FERGUSON D， NIKOLAOU C， YEMINI Y. An economy for managing replicated data in autonomous decentralized systems[C]//Proceedings of the International Symposium on Autonomous Decentralized Systems（ISADS93），1993：367-375.

[7]MACKIE J K， VARIAN H R. Pricing the internet[EB/01]. http：//ideas.repec.org/p/wpa/wuwpco/9401002.html.

[8]翁楚良， 陆鑫达. 一种基于双向拍卖机制的计算网格资源分析方法[J]. 计算机学报， 2007，29（6）：1004-1009.

[9]SUBRATA R， ZOMAYA A Y， LANDFELDT B. Game-theoretic approach for load balancing in computational grids[J]. IEEE Transactions on Parallel and Distributed System， 2008， 19（1）：66-76.

[10]KWOK Y K， HWANG K， SONG S. Selfish Girds： Game-theoretic modeling and NAS benchmark evaluation[J]. IEEE Transactions on Parallel and Distributed System， 2007， 18（5）：621-636.

[11]BUSCEMI M G， MONTANARI U， TANEJA S. Towards a game-theoretic model of grid systems[J]. Lecture Notes in Computer Science， 2010， 6084/2010：57-72.