论文研究-一种基于非完全信息博弈的网格资源分配新模型 .pdf

所需积分/C币:10 2019-08-15 14:37:53 336KB .PDF
34
收藏 收藏
举报

一种基于非完全信息博弈的网格资源分配新模型,许雷,李明楚,针对网格环境动态,异构以及分布的特性,结合微观经济学理论,本文建立一种“多赢家”式的网格资源拍卖模型(MWAM)。首次将隐马尔�
国科技论文在线 竞拍者的预测估价,并且了最大化拍卖收益,最终提交的对所需资源的受买价格,用 衣示。 本文建立一和种隐马尔可夫模型来预测竞拍者单位资源的实际估价,该预测模型通过已知 的资源请求序列来计算时刻任一竞拍者对单位资源的最大可能竞拍价( 以及其概率。隐马尔科夫链的状态是不可观测或不确定的,只有通过观测序列的随机状态才 能表现出来,则该模型可以用如下的五元组来表示: 其中: }为竞拍者的单位资源竞拍价的集合, 衣示用 在时刻对所需求的单位资源竞拍价为= ,这里 为市场网格 中资源交易的最小货币单位,并且对于用户米说,都有自己能够承受的单价上限 因此 ≤}(在后续计算推导中,简写为 形式)。 为竞标者可观测到的其他任何一个竞标者在个时刻以 内个需求资源数量的信号集合,与不存在一一对应的关系,但可以以一定的 概率显示为 (在后续计算推导中简写为=形式) 为对于某个竞拍者 来说,其的种状态之间相互转 移的概率矩阵。其中 () ,其中 ()z为初始状态的概率分有,其中x={z},丌 )(≤≤ 通过上文定义可以看出,本文所建立的隐马尔科夫模型上要由两大部分组成。如图 所示,第一部分为所有资源请求者的单位竞拍价的集合,即马尔科夫链。其中每个请求者有 个单价状态(=….),各自以的概率相转换;第二部分为一组可观测的随机 状态,由第一部分的经过一定的概率( 显示为 状态序列 随机过稈 观察值序列 马尔科夫链 (丌) 图 构成原理 本节后半部分主要任务是计算并推导出对资源请求者的预测单价状态。主要推导流 程是,首先计算条件概率=( )的值,之后从个值中选 取使 =)最人的作为最终结果。条件概率为 国科技论文在线 },带入贝叶斯公式1)中得 )=∑{-= ∑=∑ )∑ 对于 ,推导出递推公式之后,由 元 接下来本文将推导在给定 的条件下,隐马尔科夫链在t时刻的最佳预测状态。 计算目标是能够正确预测的状态概率最人。每轮拍卖,竞拍者所请求的资源数量都作为其价值评佔函数的 参数之一,任何一个竞标者一组资源请求的历史记录 与其出价状态并非呈一一对 应关系,但每个出价状态总会以一定的概率形式显示为。那么,对丁每一个≤,取使 得最大值的为条件下的预测。由上文假设可 因此,使得 )的使是此时刻的最佳预测状态。通过依次计算 (),(),…即可求解。因此,对于每一位竞拍者来说,设 。这便计算出了时刻对竞拍者做出的预测的单位资 源竞拍价为 已知了竞拍者单位出价的概率,那么通过下一节的“多赢家”拍卖规则,既可以推导出 对于某一竞拍者来说,以出价赢得所需资源的概率的表达式 从 而可计算期望收益,得到非完全信息博弈中的稔定均衡竞拍价。该表达式以及推导过程在 国科技论文在线 节实验参数设置中给予了详细描述。 的结构及算法 基于市场中的供求关系,从资源的角度提出一种网格环境下的新型拍卖模型——“多嬴 家”式拍卖,即最终获得所需资源的用户数量为多个而不是以往竞拍机制中的一个。整个过 程可以看作为一和非完仝信息博弈,竞拍者在彼此独立的条件下,通过一轮竞拍以不同价柊 争夺网格资源,最终资源代理依据特定的拍卖方式选择胜岀者。它需要的信息量较少且具有 很强的操作性,可以使系统在形成稳定的均衡价,并在系统收益与资源利用率等方面体现岀 以往资源分軋算法所不具备的优势。 的结构 依托于市场网格环境下的非完全信息博弈理论与“虚拟化”方法,本文提出一种“多赢 家”的拍卖模型,其构成如图所示 图多赢家式拍卖模型结构 由图可见,“多赢家”式拍卖模型按流程划分主要由四部分构成。竞拍开始后,初始集 合(0 riginal group)中的每一位竞拍者向资源代理( Resource agent)提交本轮拍卖的竞拍价 与请求资源量,资源代理依照“多嬴家”式算法 将资源按 比例虚拟化,分配给结果集 中的竞拍者,本轮资源拍卖结束。各部分主要功 能如下 (1) Resource agent:资源代理,负责发布资源属性,虚拟化分配资源。并且设定单位 资源价格底线 ,将单位竞拍价 的竞拍者不纳入竞拍中 (2) riginal group:每一轮拍卖初始阶段,所有参加竞拍的竞拍人集合。在拍卖开始 之后,各自依据上文所推导的隐马尔科夫公式,计算可以赢得所需资源的概率,从 而通过博弈确定竞拍价。接下米,向资源代理 Resource agent提父竞标价与 实际需求量,即 取国科技论文在线 (3) Multi- winners algorith皿:核心分配算法模块:对」资源代理来说,收益最大化是 其在分配过稈中考虑的最主要因素。设≤≤,表示分予竞拍者的资源量占其提 交的需求量的百分比,则资源代理可以分配给竞拍者的资源量为。因此对用广 提交的 ,>,对于任意的≤,在 且 ≤的前 提下,资源代珥确定使得∑最大的集合,即{…}为竞拍中的 资源分配比例集合。该模型可以表示为 (4) Result group:拍卖结束后,每个竞拍者按比例获得资源数量的集合,即: 的核心算法 由模型假设可知,从最优分配结果中除去分配给用户的资源量,剩下的必须是 可从 中取出,分酉给一个用户的且使得总收益最大的资源分量,因此它满足贪 心算法的最优子结构;考虑到减慢中剩余资源的消耗以及提高资源代理的收益增加速率, 采用单位资源量的出价 作为贪心选择标准,按照 的降序依次将资源分配给 竞拍者。假设有: 设变量与表示已经分配的资源量和资源代理的最大收益,数组 分别表示每个竞拍者的资源需求量和竞拍价。算法如图所示: 山国科技论文在线 资源总量 分配结束 资源总量 资源总量 剩余需求量 余需求量 竞标价 剩余需求量 图多赢家资源分配算法 使用单位资源价格 作为贪心选择的标准分配资源,一方面能够减慢了分配过程 中,中剩余资源的减少速度,充分利用了资源;另一方面,按照单位资源出价的降序来分 配资源,能够最优化资源代理的最终收益。 的效用分析 作为市场网格中以经济学理论为依托的模型,本文将从激励相容性,个人 理性,系统收益这几方面分析证明其效用 ()激励相容性即:在竞标者个人理性出价,且个人利益不受到损失的同时,使得 其它人的收益也有所增加,或者说使得各自标价能够达到一种均衡出价状态 即:对 于任何一位竞拍者的任何一种出价类型有, 。由」只有当在每组的竞拍中胜出,竞拍者的收益 才会体现,否则收益为,因此本文定义竞拍者的期望收益函数为 其中 表示用户以出价赢得所 需资源的概率,山一阶导数为得, 化简得 对等式两侧积分得: 由分部积分法得均衡出价值: ,即纳什均衡解。因 此,在每个分组中都达到了贝叶斯纳什均衡状态,由定义知其满足激励相容策略约束 取国科技论文在线 )个人理性每个竞拍者的出价行为也要符合个人理性约束,也就是每个竞拍参与 者的效用都为非负,即 对于获得资源量为的竞拍者来说,其收益可看作 是,对于按匕例获得所分配资源的竞拍者来说,由上文推导可知 >。因此,所有竞拍者的个人效用都为非负, “多赢家”拍卖模型是符合个人理性的 ()最大收益最后需要考虑的是系统收益。理想状态卜,成交后资源提供者的收益 与网格用户的收益总和需要达到最大。上文已求出当用户期望收益在竞标价为纳什均衡解 时出现最大值,因此该时刻所有“赢家”的收益总和也最大。设模型(2)的解为 (…),是使得≠的最小下标;为评明其为最优解的正确性,假设不 是最优解,有另可行解=( 使得 是使得 的最小下标,则: (1)当<时,由=且≠,有< (2)当=时,若>,则对于<<,=,∑。>,故 (3)当>时,有 ∑ 与模型(2)限制条件矛盾。综上可知 假改+B=,则为保证∑ ,需要从( )中减去尸,这样 来,对于∑ 且 有 +≤≤ =∑+( ∑ (y∈且∈[+] 此结果与 矛盾,所以∑ 不 ≤ 成立, ∑ ,是该问题的最优解。系统总收益为赢得资源的竞标者 总收益与资源代理收益之和,二者均为最大,因此系统收益为最大。 由上述推导证明可见,本模型能够形成较稳定的纳什均衡解,即最终竞拍价,使竞 拍者出价满足激劢相容性与个人理性,且最优化了收益;从系统收益上来看,使用本文的分 配算法,能够为其带来最优收益。 实验模拟 本节先对“多赢家”资源分配算法中 预测的可行性,以及“多嬴家”模型在市场 取国科技论文在线 网格中的适用性做了纵向的实验分析;之后分别选取序贯博弈资源分配算法,双向拍卖 分配算法,基于的资源分配算法,以及经济学中常见的“第价格”拍卖算法, ¨第二价格”拍卖算法同本文的“多赢家”算法进行比较,主要比较的指标有:资源利用率, 系统总收益和算法执行时间 参数设置 节中模型建立之后,需要给定初始化参数,通过已推导的状态预测算法对该 智能模型进行反复训练,使其快速学习,得到参数的收敛值。在本文的实验模拟中,假设网 格资源货币单位为 则选取台札,经过存储虚拟化,将其整合为 个容量为的存储资源,另选·台机作为资源代理,设发布的资源属性如衣所 小: 表资源属性 资源名称容量()类型传输标准实际频率()等效频率传输率最低价格 内存 本文中设定竞标者个数为,实验分为组。每组中对于仁一竞拍者来说,所能承 受的单价上限为 且 则状态数为 ,假设 。设定每组模拟仿真轮拍卖。其中,设任 竞标者的需求量为一集合 ,其中为区间[]上的一个随机整 数 且 亦为一随机整数 针对竞拍者需求的异构性,这里采用效用函数描述竞拍者对资源属性的偏好,从而直接 体现为其自身对资源价值的实际评估。在网格环境下的资源供求关系中,用户对资源的需求 量越人,最终的竞标价往往越高:同时,用户渴望占用资源完成仟务的执行时间越长,资源 相对开销会越高,最终标价便相应升高。本文中主要考虑参数资源需求量对函数的影响。因 此,在本文的拍卖模型中,实际估价值是用户期望资源提供的服务执行时间与用户自身 对资源需求量的函数,实际价值评估函数为: +a 其中,是期望使用资源的时间;为资源的需求量;c是竞标者对上述两种属性的 各自偏好程度a∈();7为单位效用所带来的收益。这里设定7,a。每位竞拍 者已知对资源的需求量,带入式(3)即可计算所需资源会为自身带来的实际价值。 设竞标者在已预测其他估价的基础上,能赢得所需资源量的概率为 由 节可知,单位价格 相对越大,得到所需资源量的概率越大,因此,本文中 的值为竞拍者单位竞拍价格 与其它竞拍者的预测而得的单位拍价之 和的比值。设除竞拍者之外,计算得剩余个竟拍者的预测单位价格之和为 则 取国科技论文在线 将式(4带入 衣达式中即可计算的值,从而求得最终的均衡竞拍价,由竞 拍者提交予资源代理,进行下步资源分配 模拟结果及分析 自行编写仿真程序模拟上述拍卖过程。经过样本训练后,对于其中任意一位竞标者 设 需求量依次取[]上的随机值,其中竞拍价等于预测 单价与需求量的积。经过轮模拟拍卖后所得的预测佔价与实际估价的对比如图 所示。由对比结果可以看出,使用模型预测的竞拍价曲线与竞拍者实际竞拍价曲线有 较大相似度,因此,本文建立的可以较准确地反映实际的竞拍价。 HMM预测估价 实际估价 800 400 100 仟一用户c对资源的需求量(GB) 图 预测竞拍价与实际竞拍价的对比 接下来考虑当竞标者总数与资源总量逐步增加时,算法的执行时间与资源代理总体 收益的变化情况。分别取竞拍者数目等于 ,,则变化情况如图所示, 当资源总量増加时,资源代理的收益呈现增加的趋势:冋时,当竞标者数目増多时,资源代 理的收益亦有较快增长,即瓷源代理方收益与资源总量和竞拍者数量基本上都成正比例关 系,由此可见,该算法能够较好地适应市场经济网格的特点。 ●● 资源总 图竞拍者数目变化对收益的影响

...展开详情
试读 13P 论文研究-一种基于非完全信息博弈的网格资源分配新模型 .pdf
立即下载
限时抽奖 低至0.43元/次
身份认证后 购VIP低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • 至尊王者

关注 私信
上传资源赚钱or赚积分
最新推荐
论文研究-一种基于非完全信息博弈的网格资源分配新模型 .pdf 10积分/C币 立即下载
1/13
论文研究-一种基于非完全信息博弈的网格资源分配新模型 .pdf第1页
论文研究-一种基于非完全信息博弈的网格资源分配新模型 .pdf第2页
论文研究-一种基于非完全信息博弈的网格资源分配新模型 .pdf第3页

试读结束, 可继续读1页

10积分/C币 立即下载