智能合同網協議的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 投標的次數,降低了整個系統的運行時間,降低了通信量.比傳統合同網協議具有明顯優勢.