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

《基于不完全信息博弈网格资源分配方法探究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基于不完全信息博弈网格资源分配方法探究　　摘要：针对网格环境下用户难以获得资源竞价所需的信息而导致的决策风险，将不完全信息资源竞价转化成完全信息下的重复博弈问题。分析了该博弈均衡解的存在性及求解过程，给出了相应的竞价算法，讨论了对用户低价联盟的抑制方法。仿真实验表明用户通过各阶段资源预配置的信息调整竞价策略，资源配置可逐步逼近均衡解，实现网格资源的优化配置。关键词：不完全信息；重复博弈；网格计算；资源配置中图分类号：TP393文献标识码：A文章编号：2095-2163（2014）01-0006-040引言经济网络[1-3

2、]将资源提供者和网格用户的需求使用一定的价值表述，通过成本和收益等经济约束描述网格环境[4]下用户与资源之间的交互行为，有助于建立高可扩展性的网格系统。早期经济网格的研究普遍采用商品市场[5-7]7机制或拍卖[8]机制，但商品市场机制忽略了单个用户的个体行为对资源价格的影响作用，与实际情况有较大偏差，而拍卖机制则依赖于第三方（如拍卖师）的公正性。此外，另有一些研究[9-11]将用户之间对资源的竞争使用看作一个博弈过程，在完全信息前提下通过分析均衡价格策略组合来求解网格资源优化配置方法，但基于完全信息的前提要求用户掌握其他

3、用户的详细信息，这在动态、自治的网格环境中是难以实现的。本文分析了不完全信息情况下的网格环境中用户对资源竞价的情况，通过“虚拟用户”的方式将不完全信息情况下的资源博弈转化成完全信息下的重复博弈。给出用户竞价算法及近似均衡解，克服用户对竞价信息的依赖，避免了用户盲目竞价决策的风险，实现资源的优化配置。1不完全信息资源竞价模型设N个用户竞争使用一个有M+1个中间节点的通信链路，节点k和k+1之间的通信带宽为Rk，用户使用资源并付费，系统按用户的出价比例分配资源，用户的目标是在预算范围内使用资源，且使得数据传输时间最短。模型各

4、参数设定如下：7{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的保留底价，保留底价是资源所有

5、者对资源使用成本的评估。只有当用户出价和不低于ck时，资源提供者才有意愿向用户提供资源。2竞价问题分析2.1多用户不完全信息博弈问题的转换虽然用户i难以获得所有其他用户的相关信息，但每个用户对自己的出价cki信息是可知的，而相应可获得的资源数rki则由系统返回。由于资源总量Rk是已知的，对于按竞价比例配置资源的方式，用户即可通过Rk和rki获得其他所有用户的竞价ck-i和资源数rk-i。由此推知，理性用户在拥有私有信息rki、cki基础之上，再获得可用资源总数Rk一个公共信息就可以测算出所有其他用户竞价的信息。在此，可将

6、除用户i外所有其他用户的集合虚拟为用户-i。其中，用户i的竞价信息为（cki，rki），用户类型-i的竞价信息为（ck-i，rk-i），则多用户不完全信息的资源博弈可转变成两个用户集合i和-i在完全信息下的资源博弈，并据此而得到资源配置的均衡解{c*i}。第1期林晓鹏：基于不完全信息博弈的网格资源分配方法研究智能计算机与应用第4卷72.2竞价策略的求解3.3用户低价联盟的抑制因重复竞价博弈中用户在博弈的后续阶段可对前期的竞价策略进行调整，理性用户可能会在竞价初期隐藏自己的真实目的，在前期阶段以低价进行竞价而导致延长资源配

7、置过程。或者用户之间也可能达成某种默契形成竞价联盟，联合以低价获得资源的使用权，导致资源提供者的收益可能低于资源的使用成本。为了防止这种情况发生，设定每个资源的使用者也都参与到资源竞价中，竞价过程中资源所有者设定为虚拟用户ξ，利用预先设定的保留价格ckξ参与资源竞价。通过虚拟用户的竞价，使得当资源价格低于保留价格ckξ时降低可供应的资源数量，促使用户通过提高竞价来获得更好的资源，以保障资源方的利益。4仿真结果和分析4.1仿真环境文中运用Gridsim仿真软件包来构建网格用户、网格资源、GIS等各个网格实体。各实体之间由消

8、息机制进行竞价过程的消息传递。仿真中资源数为M=10，各用户总预算为100～400GCU（GridCurrencyUnit）之间的随机数，各资源能力、用户数据包长度分别在范围1000～5000（Mbps）和0～57000（Mb）内正态分布。不考虑消息传递代价，竞价博弈的初始阶段用户按相同的单位任务费用分配预算。4.2