王文博,鄭文艷,趙麗敏

(德州學(xué)院 信息管理學(xué)院,德州 253014)

1 引言

合同網(wǎng)協(xié)議[1]是由Smith RG 提出的經(jīng)典協(xié)調(diào)協(xié)議.針對(duì)通信量大,協(xié)商效率低等問(wèn)題,許多學(xué)者提出了改進(jìn)方案.比如,文獻(xiàn)[2]將拍賣機(jī)制引入合同網(wǎng).文獻(xiàn)[3]提出一種既考慮信任度也考慮代價(jià)的動(dòng)態(tài)合同網(wǎng)協(xié)議.文獻(xiàn)[4]改進(jìn)了評(píng)標(biāo)策略.文獻(xiàn)[5]引入了匹配度和信譽(yù)度,并結(jié)合歷史數(shù)據(jù),提高了匹配效率.文獻(xiàn)[6]提出一種基于心智的合同網(wǎng)模型.文獻(xiàn)[7]在傳統(tǒng)合同網(wǎng)中引入信任度,友好度等參數(shù)來(lái)提高通信質(zhì)量.文獻(xiàn)[8]將貝葉斯平均算法引入合同網(wǎng)協(xié)議,考慮投標(biāo)者的歷史投標(biāo)情況.文獻(xiàn)[9]對(duì)傳統(tǒng)合同網(wǎng)中參與者的投標(biāo)數(shù)量進(jìn)行了限制,并將參與者能力與任務(wù)完成質(zhì)量相結(jié)合.文獻(xiàn)[10]結(jié)合群體智能提出了一種動(dòng)態(tài)合同網(wǎng)協(xié)議,在系統(tǒng)規(guī)模較大時(shí),該算法比傳統(tǒng)合同網(wǎng)協(xié)議算法具有明顯優(yōu)勢(shì).文獻(xiàn)[11]總結(jié)了對(duì)合同網(wǎng)協(xié)議進(jìn)行改進(jìn)的措施及局限性.文獻(xiàn)[12]提高了匹配效率,文獻(xiàn)[13]把時(shí)間機(jī)制引入基于顏色Petri 網(wǎng)建立的合同網(wǎng)模型.文獻(xiàn)[14]建立了合同網(wǎng)的顏色Petri 網(wǎng)模型,證明了Bidder的數(shù)量與終止?fàn)顟B(tài)的關(guān)系,并把結(jié)果擴(kuò)展到24 個(gè)Bidder.

借鑒以上各種改進(jìn)算法的特點(diǎn),本文基于顏色Petri 網(wǎng)[15]提出了智能動(dòng)態(tài)時(shí)間合同網(wǎng)協(xié)議(ICP).該協(xié)議對(duì)雙方都添加了因子,從第一步就大幅度降低了通信次數(shù);其次,該協(xié)議限定了投標(biāo)次數(shù),并不是對(duì)所有符合條件的亂投標(biāo),按照投標(biāo)者的喜好參數(shù)進(jìn)行小范圍的投標(biāo);再者,改進(jìn)了任務(wù)要么被流拍一次就徹底退出,要么無(wú)限次的流拍,該協(xié)議設(shè)定了任務(wù)可以被流拍的閾值,符合實(shí)際情況;最后,該協(xié)議根據(jù)任務(wù)流拍產(chǎn)生的原因,智能實(shí)時(shí)調(diào)整各項(xiàng)參數(shù).

2 ICP的顏色Petri 網(wǎng)模型

利用顏色Petri 網(wǎng)構(gòu)造其CPN 模型.如圖1所示,模型分兩層,top 層描述了整個(gè)模型的框架,具體功能在子頁(yè)實(shí)現(xiàn).其具體描述如下:

第1 步.產(chǎn)生任務(wù)的基本信息(GenerateTask 變遷)

該基本信息以六元組形式表示:(任務(wù)號(hào),發(fā)布任務(wù)的Auctioneer,可以參與投標(biāo)的Bidder 列表,該任務(wù)發(fā)布的時(shí)間,該任務(wù)的基本約束條件,該任務(wù)的有效期).

第2 步.Auctioneer 選擇滿足條件的Bidder,并對(duì)其發(fā)布任務(wù)信息(AUCSendTasktoSuitableBidder 變遷).

Auctioneer 根據(jù)任務(wù)基本信息中的約束條件(Bidder的初始信任度),Bidder 對(duì)Auctioneer 友好度的要求,以及Bidder 投標(biāo)總數(shù)的要求,從所有Bidder 中選擇滿足條件的Bidder;如果滿足條件的Bidder 列表為空,并且該任務(wù)被發(fā)布的次數(shù)滿足條件,那么該任務(wù)重新進(jìn)入待發(fā)布的任務(wù)列表中,否則,丟掉該任務(wù).如果有滿足條件的Bidder,那么保留滿足條件的Bidder列表.

第3 步.符合條件的Bidder 投標(biāo),產(chǎn)生報(bào)價(jià)信息以及完成該動(dòng)作消耗的時(shí)間(BidderRebackTask CosttoAuctioner 變遷).

符合條件的所有Bidder 對(duì)任務(wù)進(jìn)行投標(biāo),主要是產(chǎn)生每個(gè)Bidder的報(bào)價(jià)Cost 信息以及每個(gè)Bidder 完成該項(xiàng)任務(wù)所消耗的時(shí)間,更新Bidder 已經(jīng)投標(biāo)的次數(shù).此處的時(shí)間信息作為下一個(gè)模塊用以判斷回應(yīng)任務(wù)是否超時(shí).

圖1 ICP的CPN 模型top 層

第4 步.Auctioneer 根據(jù)Bidder的報(bào)價(jià)以及Bidder的信任度綜合評(píng)價(jià)選擇最合適的Bidder 來(lái)完成任務(wù)(AUCReceiveBidandSelectBidder 變遷).

Auctioneer 根據(jù)Bidder 提供的報(bào)價(jià)信息以及時(shí)間信息,首先判斷是否超時(shí),如果所有的Bidder 回應(yīng)的時(shí)間信息都超時(shí),那么該任務(wù)根據(jù)任務(wù)被發(fā)布的次數(shù)判斷是否需要返回待發(fā)布任務(wù)列表;并且給所有超時(shí)的Bidder 反饋TimeOut 信息.如果存在Bidder 不超時(shí),那么根據(jù)設(shè)定的規(guī)則選擇合適的Bidder,對(duì)該Bidder 發(fā)出Grant 信息,其余Bidder 發(fā)送Reject 信息.

第5 步.對(duì)選中的Bidder 發(fā)送Grant 信息,對(duì)于沒(méi)有選中的發(fā)送Reject 信息,而對(duì)于超時(shí)的發(fā)送TimeOut信息 (SendGrantReject2Bidder 變遷).

第6 步.根據(jù)接收及發(fā)送的信息,更新Auctioneer的友好度以及Bidder的信任度,便于下次投標(biāo).根據(jù)收到的信息更新Bidder的信任度和Auctioneer的友好度以及Bidder 投標(biāo)的次數(shù) (UpdateCredit 變遷).

3 實(shí)驗(yàn)分析

3.1 ICP與合同網(wǎng)協(xié)議[1]的對(duì)比分析

為證明ICP的有效性,假定Auctioneer,Bidder 數(shù)量一定,任務(wù)數(shù)量不同時(shí)從通信次數(shù)、消耗時(shí)間、達(dá)成協(xié)議的任務(wù)數(shù)量3 方面進(jìn)行分析.

初始假定Auctioneer的個(gè)數(shù)為3 個(gè),采用文獻(xiàn)[1]的合同網(wǎng)協(xié)議,Bidder的個(gè)數(shù)為5,任務(wù)數(shù)分別為10 個(gè),50 個(gè)和100 個(gè),得到的實(shí)驗(yàn)數(shù)據(jù)如表1所示.

可以看出,在任務(wù)數(shù)量一定的情況下,文獻(xiàn)[1]中合同網(wǎng)協(xié)議的Auctioneer 發(fā)送消息數(shù)量與任務(wù)數(shù)量相同,Bidder 投標(biāo)次數(shù)成倍增加,而ICP 中Auctioneer 發(fā)送消息數(shù)量比文獻(xiàn)1 中稍多,但大大減少了Bidder的投標(biāo)次數(shù),最終達(dá)成協(xié)議的成功率均為100%,但總的消耗時(shí)間有所增加.

3.2 Bidder 信任度

圖2展示了任務(wù)被拒絕或接受時(shí),Bidder 信任度的分布情況.從圖中看出,Bidder 信任度與被接受還是拒絕并不成正比關(guān)系,還要參考其他因素,比如Cost 等.

圖2 Bidder 信任度關(guān)系圖

4 結(jié)論

本文在深入分析傳統(tǒng)合同網(wǎng)協(xié)議以及其擴(kuò)展及改進(jìn)協(xié)議后,提出了ICP,不僅考慮了以信任度為代表的有益因素以及以成本為代表的不利因素的歸一問(wèn)題,并根據(jù)雙方的歷史動(dòng)作情況實(shí)時(shí)更新兩個(gè)因素,而且把時(shí)間以及造成任務(wù)流拍的兩個(gè)因素做了智能調(diào)整,增大了任務(wù)達(dá)成一致的機(jī)率,從而減少了Auctioneer公布任務(wù)的次數(shù),Bidder 投標(biāo)的次數(shù),降低了整個(gè)系統(tǒng)的運(yùn)行時(shí)間,降低了通信量.比傳統(tǒng)合同網(wǎng)協(xié)議具有明顯優(yōu)勢(shì).