智能合同网协议的CPN实现①

王文博,郑文艳,赵丽敏

(德州学院 信息管理学院,德州 253014)

1 引言

合同网协议[1]是由Smith RG 提出的经典协调协议.针对通信量大,协商效率低等问题,许多学者提出了改进方案.比如,文献[2]将拍卖机制引入合同网.文献[3]提出一种既考虑信任度也考虑代价的动态合同网协议.文献[4]改进了评标策略.文献[5]引入了匹配度和信誉度,并结合历史数据,提高了匹配效率.文献[6]提出一种基于心智的合同网模型.文献[7]在传统合同网中引入信任度,友好度等参数来提高通信质量.文献[8]将贝叶斯平均算法引入合同网协议,考虑投标者的历史投标情况.文献[9]对传统合同网中参与者的投标数量进行了限制,并将参与者能力与任务完成质量相结合.文献[10]结合群体智能提出了一种动态合同网协议,在系统规模较大时,该算法比传统合同网协议算法具有明显优势.文献[11]总结了对合同网协议进行改进的措施及局限性.文献[12]提高了匹配效率,文献[13]把时间机制引入基于颜色Petri 网建立的合同网模型.文献[14]建立了合同网的颜色Petri 网模型,证明了Bidder的数量与终止状态的关系,并把结果扩展到24 个Bidder.

借鉴以上各种改进算法的特点,本文基于颜色Petri 网[15]提出了智能动态时间合同网协议(ICP).该协议对双方都添加了因子,从第一步就大幅度降低了通信次数;其次,该协议限定了投标次数,并不是对所有符合条件的乱投标,按照投标者的喜好参数进行小范围的投标;再者,改进了任务要么被流拍一次就彻底退出,要么无限次的流拍,该协议设定了任务可以被流拍的阈值,符合实际情况;最后,该协议根据任务流拍产生的原因,智能实时调整各项参数.

2 ICP的颜色Petri 网模型

利用颜色Petri 网构造其CPN 模型.如图1所示,模型分两层,top 层描述了整个模型的框架,具体功能在子页实现.其具体描述如下:

第1 步.产生任务的基本信息(GenerateTask 变迁)

该基本信息以六元组形式表示:(任务号,发布任务的Auctioneer,可以参与投标的Bidder 列表,该任务发布的时间,该任务的基本约束条件,该任务的有效期).

第2 步.Auctioneer 选择满足条件的Bidder,并对其发布任务信息(AUCSendTasktoSuitableBidder 变迁).

Auctioneer 根据任务基本信息中的约束条件(Bidder的初始信任度),Bidder 对Auctioneer 友好度的要求,以及Bidder 投标总数的要求,从所有Bidder 中选择满足条件的Bidder;如果满足条件的Bidder 列表为空,并且该任务被发布的次数满足条件,那么该任务重新进入待发布的任务列表中,否则,丢掉该任务.如果有满足条件的Bidder,那么保留满足条件的Bidder列表.

第3 步.符合条件的Bidder 投标,产生报价信息以及完成该动作消耗的时间(BidderRebackTask CosttoAuctioner 变迁).

符合条件的所有Bidder 对任务进行投标,主要是产生每个Bidder的报价Cost 信息以及每个Bidder 完成该项任务所消耗的时间,更新Bidder 已经投标的次数.此处的时间信息作为下一个模块用以判断回应任务是否超时.

图1 ICP的CPN 模型top 层

第4 步.Auctioneer 根据Bidder的报价以及Bidder的信任度综合评价选择最合适的Bidder 来完成任务(AUCReceiveBidandSelectBidder 变迁).

Auctioneer 根据Bidder 提供的报价信息以及时间信息,首先判断是否超时,如果所有的Bidder 回应的时间信息都超时,那么该任务根据任务被发布的次数判断是否需要返回待发布任务列表;并且给所有超时的Bidder 反馈TimeOut 信息.如果存在Bidder 不超时,那么根据设定的规则选择合适的Bidder,对该Bidder 发出Grant 信息,其余Bidder 发送Reject 信息.

第5 步.对选中的Bidder 发送Grant 信息,对于没有选中的发送Reject 信息,而对于超时的发送TimeOut信息 (SendGrantReject2Bidder 变迁).

第6 步.根据接收及发送的信息,更新Auctioneer的友好度以及Bidder的信任度,便于下次投标.根据收到的信息更新Bidder的信任度和Auctioneer的友好度以及Bidder 投标的次数 (UpdateCredit 变迁).

3 实验分析

3.1 ICP与合同网协议[1]的对比分析

为证明ICP的有效性,假定Auctioneer,Bidder 数量一定,任务数量不同时从通信次数、消耗时间、达成协议的任务数量3 方面进行分析.

初始假定Auctioneer的个数为3 个,采用文献[1]的合同网协议,Bidder的个数为5,任务数分别为10 个,50 个和100 个,得到的实验数据如表1所示.

可以看出,在任务数量一定的情况下,文献[1]中合同网协议的Auctioneer 发送消息数量与任务数量相同,Bidder 投标次数成倍增加,而ICP 中Auctioneer 发送消息数量比文献1 中稍多,但大大减少了Bidder的投标次数,最终达成协议的成功率均为100%,但总的消耗时间有所增加.

3.2 Bidder 信任度

图2展示了任务被拒绝或接受时,Bidder 信任度的分布情况.从图中看出,Bidder 信任度与被接受还是拒绝并不成正比关系,还要参考其他因素,比如Cost 等.

图2 Bidder 信任度关系图

4 结论

本文在深入分析传统合同网协议以及其扩展及改进协议后,提出了ICP,不仅考虑了以信任度为代表的有益因素以及以成本为代表的不利因素的归一问题,并根据双方的历史动作情况实时更新两个因素,而且把时间以及造成任务流拍的两个因素做了智能调整,增大了任务达成一致的机率,从而减少了Auctioneer公布任务的次数,Bidder 投标的次数,降低了整个系统的运行时间,降低了通信量.比传统合同网协议具有明显优势.