基于博弈论的网格资源管理+源代码(3)
时间:2017-06-24 22:08 来源:毕业论文 作者:毕业论文 点击:次
图2 网格资源分配模型 2. 网格资源分配中博弈模型建立 2.1 博弈的定义 定义1： 一个非合作完全信息静态博弈定义如下： 博弈的参与者对于博弈的整体结构有着充分了解，唯一需要考虑的就是策略选择问题，同时博弈中的每个参与者的策略选择仅进行一次，在选择时不知道其他人的策略选择。 博弈参与者：M个Guser的集合（多个网格资源的请求者）。 博弈策略：记每个参与者i的策略为ai (每个Guser对Ggian的出价),ai ∈ Ai ,其中Ai 为局中人i可选择的策略组成的策略集合。 策略组合：n个参与者各选择一个策略形成的向量a=（a1，a2，...，an）被称为策略组合。 收益：指每个参与者从各种策略组合中获得的收益，记参与者i的收益函数为ui（ai），表示为参与者i选择策略ai时的收益。 定理1 ：在n人策略型博弈中，如果每个参与者的纯策略空间Ai 是欧式空间上的非空有界闭凸集，支付函数ui（ai）连续且对ai是拟凹的，那么这一博弈中存在一个纯策略纳什均衡。 当存在纳什均衡时说明，参与者i选择策略ai时的收益都是相对于其他参与者选择策略a-i时的最大收益（a-i表示a中除去参与者i的策略选择），其中每个局中人均不能因为单方面改变自己的策略而获利，则： u(ai,a-i)>u(A-i,a-i) 其中A-i表示参与者i除去选择策略ai的其他策略选择。 2.2 模型假设 1、 资源分配遵循基于权重的比例共享原则。 2、 Guser的任务是并行的，同时各Guser之间的任务类型一致。 3、 Ggian中所包含的单个资源的任务执行效率为一秒执行一个用户任务。 4、 当Guser获得请求的资源后，拥有该资源的占有权，使用完毕后释放。 5、 单位资源的费用是相同的，因此对于各个Guser来说资源的费用都是一致的。 6、 Guser是理性的，能够分析当下的资源分配情况，从而得出自身的最佳分配方案，同时Guser之间，以及Guser和Ggian之间的信息是已知的，但是Guser之间不能进行沟通，以确保资源的合理分配。 模型中有N个网格用户（Guser）同时向同一个资源巨头（Ggian（单类型））发起资源请求，而且用户出价相对越高，所得到的资源比例相对越多。每个用户需向资源提交一个出价ai∈R，则a=（a1，a2，...，an）表示所有请求用户的出价。则分配给第i个参与出价用户的资源份额比为p（ai）∈[0，1]和出价ai的关系为： 2.3 博弈参与者的效用函数 效用函数是每个博弈参与者在进行策略选择后得到利益的函数表达式，在博弈模型中进行分析用户策略的起着关键的作用，寻找纳什均衡点就是通过分析用户不同策略选择下的效用函数得到的。 在基于博弈论的网格资源分配模型中每个参与者都有一个与之对应的效用函数，设si表示第i个参与者的总任务量，cj表示类型为j的Ggian中所包含的资源总数，hi表示第i个参与者所分到的资源数量，由于在博弈模型中是多个Guser向同一个Ggian发起请求，所以假设j=1,即向同一个Ggian发起请求，则并且资源总量hi=c1* p（ai），ti为Guser完成任务的执行时间，为了简化问题假设所获得的资源总量hi和资源的分配份额比p（ai）一致，则ti=si/p（ai），bi为第i个参与者的出价预算。 在预算允许的情况下，用户以最短的执行任务时间为最优目标，因此效用函数应满足下列要求为： 以用户获得的资源越多相应的收益越高同时也就是相应的任务执行时间越低为原则建立用户的效用函数为： 2.4 最优策略求解 博弈模型中的均衡点也就是所有用户最优出价策略的结合点，则用户的最优出价策略ai*是使得自身效用达到最大时的策略选择，令效用函数的一次微分等于零，得出参与者的最优出价函数为： (责任编辑：qin) |