2020, Vol. 29
合同网协议[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投标, 产生报价信息以及完成该动作消耗的时间(BidderRebackTaskCosttoAuctioner变迁).
符合条件的所有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 实验数据对比分析 |
可以看出, 在任务数量一定的情况下, 文献[1]中合同网协议的Auctioneer发送消息数量与任务数量相同, Bidder投标次数成倍增加, 而ICP中Auctioneer发送消息数量比文献1中稍多, 但大大减少了Bidder的投标次数, 最终达成协议的成功率均为100%, 但总的消耗时间有所增加.
3.2 Bidder信任度图2展示了任务被拒绝或接受时, Bidder信任度的分布情况. 从图中看出, Bidder信任度与被接受还是拒绝并不成正比关系, 还要参考其他因素, 比如Cost等.
|
图 2 Bidder信任度关系图 |
4 结论
本文在深入分析传统合同网协议以及其扩展及改进协议后, 提出了ICP, 不仅考虑了以信任度为代表的有益因素以及以成本为代表的不利因素的归一问题, 并根据双方的历史动作情况实时更新两个因素, 而且把时间以及造成任务流拍的两个因素做了智能调整, 增大了任务达成一致的机率, 从而减少了Auctioneer公布任务的次数, Bidder投标的次数, 降低了整个系统的运行时间, 降低了通信量. 比传统合同网协议具有明显优势.
| [1] |
Smith RG. The contract net protocol: High-level communication and control in a distributed problem solver. IEEE Transactions on Computers, 1980, C–29(12): 1104-1113. |
| [2] |
刘俊, 曹斌, 谭丹丹. 基于拍卖机制的改进合同网协商策略. 计算机应用, 2007, 27(2): 494-496. |
| [3] |
韦兆文, 区云鹏, 闫俊燕. 一种改进的动态合同网协议. 计算机工程与应用, 2007, 43(36): 208-210, 216. DOI:10.3321/j.issn:1002-8331.2007.36.064 |
| [4] |
杨唯一, 刘晓路. 基于动态合同网的多星自主协同与任务规划. 第六届高分辨率对地观测学术年会论文集(上). 成都. 2019. 231–258.
|
| [5] |
付光远, 李源, 付文宇, 等. 改进合同网在多机器人围捕任务分配中的应用. 兵器装备工程学报, 2019, 40(3): 98-102, 216. DOI:10.11809/bqzbgcxb2019.03.022 |
| [6] |
陈明, 简玉梅. 基于心智系数的多Agent合同网协作模型研究. 计算机应用与软件, 2013, 30(6): 46-51, 56. DOI:10.3969/j.issn.1000-386x.2013.06.014 |
| [7] |
潘刚, 苏厚勤. 一种关于合同网协作改进模型的研究与实践. 计算机应用与软件, 2012, 29(3): 212-215. DOI:10.3969/j.issn.1000-386X.2012.03.057 |
| [8] |
曹佳. 基于贝叶斯平均算法的合同网协议改进方案研究. 苏州大学学报(工科版), 2012, 32(5): 76-80. |
| [9] |
杨件, 李文立, 洪春宇. 基于阈值和可用度的合同网协议改进方案研究. 计算机集成制造系统, 2009, 15(5): 1016-1022. |
| [10] |
张海俊, 史忠植. 动态合同网协议. 计算机工程, 2004, 30(21): 44-46, 57. DOI:10.3969/j.issn.1000-3428.2004.21.019 |
| [11] |
郭超, 熊伟, 刘呈祥. 合同网协议改进研究现状与展望. 装备学院学报, 2016, 27(6): 82-89. DOI:10.3783/j.issn.2095-3828.2016.06.016 |
| [12] |
陈波, 朱坤博, 杜秀丽, 等. 基于扩展合同网的协同故障诊断任务分配研究. 计算机应用与软件, 2017, 34(2): 280-284, 294. DOI:10.3969/j.issn.1000-386x.2017.02.050 |
| [13] |
Boukredera D, Maamri R, Aknine S. Modeling and analysis of reliable contract net protocol using timed colored petri nets. Proceedings of 2013 IEEE/WIC/ACM International Joint Conferences on Web Intelligence (WI) and Intelligent Agent Technologies (IAT). Atlanta, GA, USA. 2013. 17–24.
|
| [14] |
Gupta AK, Gallasch GE. Equivalence class verification of the contract net protocol-extension. International Journal on Software Tools for Technology Transfer, 2016, 18(6): 685-706. DOI:10.1007/s10009-015-0376-z |
| [15] |
Jensen K. Coloured petri Nets. Brauer W, Reisig W, Rozenberg G. Petri Nets: Central Models and their Properties. Heidelberg: Springer, 1986. 248–299.
|