·166· 智能系统学报 第5卷 其中，Ag为协商参与者Agent i,j,它在协商中 表示生产者或消费者；A为协商双方可行行动组合； 8为协商对象类型组合；Te为协商双方的协商最终 期限；S为协商策略；Protocol为协商协议，协商时协 商参与者所遵循的协商规则 协商过程为在协商最终期限内任意Agent i在 时刻t出价，如果Agent j(i≠j)不接受则根据自身的 状态：S稳定)，B(竞价)，A(分析)事什 策略在t+1时刻还价，然后轮到i决定是否接受j 1)发布竞介信总：2)到达竞价周期：3)确定新的策略：4)记录 分析结果：5)收集竞价信息：6)分析网格状态 的还价，然后再到j决定，这样多次交替出价还价. 图1消费者状态变迁 如果j接受i的出价，则行动accept,协商结束，如果 Fig.1 Consumers state transition j选择退出协商，则行动qut,协商结束。 设消费者c向提供者p申请的资源量为R。个基本 在上述模式下的资源调度过程实际上是消费者 单位，预算费用为B。.设提供者p当前可用资源数量是 和提供者间的竞价博弈过程，目的是在为消费者确 P.个基本单位.在进行资源调度时，提供者首先将目前 定合适资源占用量的同时，也为提供者确定合适的 可用资源量与一预设阈值△比较如果P.≥A,则认为 售价，达到Nash均衡下的Pareto最优. 当前可用资源丰富，采用博弈模式分配资源；否则，认 2仿真分析 为当前可用资源短缺，采用竞价模式△值由提供者根 据其资源使用历史纪录确定， 为验证本文方法的有效性，将本文算法与文献 算法1消费者竞价算法。 [8]中针对日用品市场模型提出的费用优先算法进 输入：资源提供者给出的底价、消费者的最大支 行负载平衡比较，实验结果如表1.表1表明，本文 付能力、所需资源数量； 算法在负载平衡方面表现比定价算法要好，这是因 输出：最终成交价 为本文算法在每个作业协商完成后协商双方都对协 1)提供者通告消费者资源销售底价B。· 商策略进行调整.当资源利用不充分时，资源提供者 2)如果R。·B。≤B。,则消费者通告提供者“愿 调整策略在后面的协商中降低成交价格以竞争到作 接受该售价”；反之，通告提供者“不接受该售价”， 业.这样通过竞争使系统中的资源负载较平衡.而定 3)提供者在收到所有消费者响应后，计算愿意 价算法中，由于在一段时间内资源的价格是不变的， 接受当前售价的消费者数量N,如果N4>0,则提 资源代理都选择价格便宜的资源执行作业，这造成 高售价B,=B。+ε(E是提价步长)，并通告消费者 了一些资源负载过大，而另一些资源得不到利用。 资源最新售价，转2)；否则转4). 表1竞价算法和定价算法对比 4)提供者把所有已知的消费者愿接受的最高 Table 1 Comparison of loads balance between the bidding 售价B,B2,…按从高到低顺序排列为：B,B,… algorithms and the pricing algorithm 5)令i=1. 资源号12345678910 6)给接受售价B的消费者分配R。个基本单位 出价2202323141 资源(R。是该消费者申请的资源量). 定价0040505150 7)如果提供者仍有可用资源且还有待分配资 同时，还在P℃机模拟了本文算法和蛛网模型 源的已接受售价的消费者，则i=i+1,转6). 每个资源提供者可为多个用户服务，每个用户有不 8)对于刚性需求的消费者，若其需求未得到满 同的需求.用户总需求资源数量为32个标准任务， 足，则提供者与其协商；若协商失败，则其退出竞价， 图2比较了本文算法和蛛网算法的资源利用率.资 9)根据消费者资源占用量和其接受的最高售 源提供者资源数量小于32时，如果供不应求，资源 价计算其实际付费，结束， 提供者满足部分用户的需求，本文模型资源利用率 上述竞价协商模型定义如下： 高于蛛网模型；供大于求时，蛛网模型经过反复迭 M=<Ag,A,⊙，Te,S,Protocol> 代，达到平衡点，满足部分用户的需求，竞价模型此 时满足所有用户的需求，资源利用率高于蛛网模型