基于完全圖網(wǎng)絡(luò)的鏡像激勵機制研究

張琦琮，朱立谷

(中國傳媒大學(xué) 理工學(xué)部計算機學(xué)院，北京)

1 引言

對等網(wǎng)絡(luò)具有節(jié)點自治性較高，擴展靈活，負(fù)載均衡等特點，因而得以在流媒體技術(shù)、文件分發(fā)、存儲共享、傳感器通訊等領(lǐng)域應(yīng)用廣泛。但由于網(wǎng)絡(luò)中自私節(jié)點的存在，不可避免地出現(xiàn)“搭便車”現(xiàn)象。還有如文獻[1]研究無線傳感器網(wǎng)絡(luò)發(fā)現(xiàn)，若傳感器節(jié)點不積極獲取數(shù)據(jù)并及時傳輸，會導(dǎo)致系統(tǒng)參與者數(shù)量不足，節(jié)點間合作程度不高，進而無法提供高質(zhì)量數(shù)據(jù)，最終難以保證網(wǎng)絡(luò)系統(tǒng)有效性。為減少和避免這類現(xiàn)象，采用激勵機制以促進節(jié)點之間合作和互相提供服務(wù)[2]。激勵機制如何在提升網(wǎng)絡(luò)節(jié)點合作方面有效發(fā)揮作用，國內(nèi)外學(xué)者已經(jīng)在不同領(lǐng)域進行了廣泛的研究。激勵機制在群智感知、機會網(wǎng)絡(luò)和延遲容忍網(wǎng)絡(luò)等研究方向取得進展，并在計算機與信息共享、帶寬與頻譜資源分配等應(yīng)用中得以實現(xiàn)[3，4]。在社交網(wǎng)絡(luò)、無線傳感器網(wǎng)絡(luò)等開放環(huán)境中，激勵機制用于評估信譽信任管理的效果[5，6]。如何構(gòu)建和評價激勵機制，事關(guān)激勵作用能否實現(xiàn)。有學(xué)者指出，關(guān)于社會網(wǎng)絡(luò)以及多智能體系統(tǒng)，對網(wǎng)絡(luò)群體行為實行合理建模分析是研究激勵機制的有效手段[7]。文獻[8]提出，演化博弈適合作為解決網(wǎng)絡(luò)環(huán)境中動態(tài)博弈問題的建?；A(chǔ)。還有學(xué)者進一步指出，將數(shù)學(xué)理論與計算機技術(shù)相結(jié)合，建立模型研究個體間協(xié)同演化與相互作用，進而分析群體演化的動力學(xué)機制[9]。這些成果都為深入研究提供了較好的基礎(chǔ)。

鏡像激勵機制是一種廣泛采用的激勵機制[10]。但對于鏡像激勵機制，不同學(xué)者有不同的認(rèn)識，如有學(xué)者認(rèn)為只有滿足一定的條件，初始狀態(tài)下無私節(jié)點和互惠節(jié)點數(shù)量比例較高，并擁有較高的激勵系數(shù)，該機制才能夠?qū)崿F(xiàn)有效激勵，系統(tǒng)可以保持合作狀態(tài)；如果初始時自私節(jié)點比例較高，即使激勵系數(shù)較高的情況下，系統(tǒng)也終將走向崩潰[11]。但有的學(xué)者認(rèn)為該機制根本無法實施有效的激勵[12]。因而，對鏡像激勵機制是否能夠有效激勵的研究分析就具有了重要意義。本文即基于完全圖網(wǎng)絡(luò)圍繞鏡像激勵機制進行建模和實驗仿真研究，探討不同類型節(jié)點初始比例、激勵系數(shù)與系統(tǒng)節(jié)點提供服務(wù)程度之間的關(guān)系。

2 框架設(shè)計與策略描述

一般網(wǎng)絡(luò)系統(tǒng)中，節(jié)點類型分為無私者和自私者兩種類型。無私者類型節(jié)點，采取無條件提供服務(wù)的策略，不論請求服務(wù)的節(jié)點是何種類型。自私者類型節(jié)點，采取不提供任何服務(wù)的策略，同樣不考慮請求服務(wù)的節(jié)點是何種類型。所謂鏡像激勵機制，是指在系統(tǒng)原有兩種類型節(jié)點的基礎(chǔ)上引入第三種類型節(jié)點，該類型節(jié)點不是無條件采用提供服務(wù)或拒絕服務(wù)的策略，而是采用一種新的有條件為對方提供服務(wù)的策略，稱為互惠策略，該類型節(jié)點稱為互惠者?；セ菡叩淖龇ㄈ缤幻骁R子，“你對別人怎么樣，我就對你怎么樣”。因此該激勵機制稱之為鏡像激勵機制。

2.1 模型系統(tǒng)的設(shè)計

為便于研究，我們構(gòu)建的網(wǎng)絡(luò)框架系統(tǒng)基于以下假設(shè)條件：(1)該網(wǎng)絡(luò)系統(tǒng)是具有一定規(guī)模的完全圖網(wǎng)絡(luò)，網(wǎng)絡(luò)中任意兩個節(jié)點之間直接相連，彼此可以直接實現(xiàn)數(shù)據(jù)傳輸存儲等相關(guān)服務(wù)。(2)該網(wǎng)絡(luò)是一個封閉的系統(tǒng)，當(dāng)模型運行開始后不允許系統(tǒng)內(nèi)節(jié)點退出，也不允許系統(tǒng)外節(jié)點進入，保證網(wǎng)絡(luò)規(guī)模固定不變。(3)該系統(tǒng)基于設(shè)定的離散時間時長演化，任務(wù)開始與完成都以時間步為基本單位。

根據(jù)以上假設(shè)，我們來構(gòu)建本文的模型系統(tǒng)。設(shè)網(wǎng)絡(luò)中有n個節(jié)點，共有3種類型，xi表示i類型節(jié)點數(shù)量占網(wǎng)絡(luò)中節(jié)點總數(shù)的比例，gi(j)為i類型節(jié)點為j類型節(jié)點提供服務(wù)的概率，i，j=1，2，3，分別代表無私、互惠、自私節(jié)點類型。各種類型節(jié)點數(shù)量初始比例為x1：x2：x3。歸一后有：

網(wǎng)絡(luò)中三種類型節(jié)點數(shù)目分別為n×x1，n×x2，n×x3。按照博弈理論，三種類型的節(jié)點可以認(rèn)為是三方博弈的參與者，構(gòu)成參與者集合：{無私者，互惠者，自私者}。參與策略集合：{按照一定比例gi(j)提供服務(wù)}。三方博弈關(guān)系：無私者對任何類型節(jié)點都采取提供服務(wù)的策略，因此，g1(j)=1，無私者對無私者、互惠者、自私者構(gòu)成的策略選擇矩陣為(1 1 1)。自私者對任何類型節(jié)點都采取拒絕服務(wù)的策略，因此，g3(j)=0，自私者對無私者、互惠者、自私者構(gòu)成的策略選擇矩陣為(0 0 0)?；セ菡卟扇』セ莶呗?，下文進行詳細分析。

2.2 策略描述

鏡像激勵機制下的互惠節(jié)點收到另一個節(jié)點請求時，是否為其服務(wù)的概率等于該請求節(jié)點是否為其他節(jié)點提供服務(wù)的概率。因此易知，互惠節(jié)點對無私節(jié)點提供服務(wù)概率為g2(1)=1，對自私節(jié)點提供服務(wù)概率為g2(3)=0。互惠節(jié)點之間服務(wù)概率滿足如下等式：

代入g2(1)=1，g2(3)=0，整理后求得，

綜合以上三種類型節(jié)點策略，構(gòu)建模型系統(tǒng)策略選擇矩陣如下：

(1)

其中，行列參與者順序依次表示無私者、互惠者、自私者類型節(jié)點，Gi，j表示i類型節(jié)點向j類型節(jié)點提供服務(wù)的概率，Gi，j=gi(j)。

顯然，為其他節(jié)點提供服務(wù)得出的消耗矩陣等于策略選擇矩陣式(1)，如下：

(2)

而獲得其他節(jié)點服務(wù)的收益矩陣為激勵系數(shù)與消耗矩陣的轉(zhuǎn)置的乘積，如下：

(3)

由式(2)(3)可以得到單個節(jié)點的凈收益矩陣，如下：

(4)

根據(jù)式(4)，可得兩兩凈收益矩陣，如下：

(5)

對式(5)采用劃線法分析可以得到：

由以上分析得到，(0，0)是唯一的納什均衡解。采用經(jīng)典博弈理論分析得出，只有節(jié)點拒絕提供服務(wù)才是最優(yōu)策略，而且與激勵系數(shù)α無關(guān)。但該結(jié)論與實際仿真實驗結(jié)果不同。

3 結(jié)合數(shù)學(xué)模型的實驗分析方法

經(jīng)典博弈理論以博弈參與者具有完全理性為基礎(chǔ)，完全理性意味著博弈參與者一開始就能夠找到最優(yōu)策略。但這與大部分現(xiàn)實狀況不符，現(xiàn)實中由于信息不對稱等各種因素限制，大部分參與者表現(xiàn)出的是有限理性，因此導(dǎo)致經(jīng)典博弈理論分析難以逼真地模擬現(xiàn)實。仿真實驗允許博弈參與者在博弈過程中，不斷試錯，不斷學(xué)習(xí)，來尋求更優(yōu)的策略。因而，在有限理性的前提下模擬現(xiàn)實情形，博弈分析的重點是關(guān)注博弈者學(xué)習(xí)和策略調(diào)整過程，以及趨勢和穩(wěn)定性。這里穩(wěn)定性是指系統(tǒng)中博弈參與者采用特定策略的比例不變，而不是某個博弈方的策略不變。本模型節(jié)點數(shù)量較多，任意兩個節(jié)點滿足完全圖網(wǎng)絡(luò)性質(zhì)，可以兩兩直接相連，相互之間隨機提出服務(wù)請求。因此采用在上文的數(shù)學(xué)框架基礎(chǔ)上開展演化博弈實驗方法分析。

3.1 實驗基本流程

(1)系統(tǒng)初始化階段

首先確定系統(tǒng)規(guī)模，生成數(shù)量充足、數(shù)目固定的節(jié)點，并建立兩兩相連的完全圖網(wǎng)絡(luò)。對網(wǎng)絡(luò)中每個節(jié)點按照初始策略比例賦予相應(yīng)個體策略屬性初值。并假定所有節(jié)點都可以滿足提供服務(wù)的條件和具備學(xué)習(xí)能力。最后，系統(tǒng)設(shè)置完畢相關(guān)參數(shù)，如演化步數(shù)，學(xué)習(xí)系數(shù)，激勵系數(shù)等。

(2)演化學(xué)習(xí)階段

為便于實現(xiàn)并較為真實地反映實際演化過程，該階段使用當(dāng)前最大收益學(xué)習(xí)模型。該模型的核心思想是每個時間步系統(tǒng)得到平均收益最大的策略，采用其他策略的節(jié)點按照一定概率改變?yōu)樵摬呗?。后文作詳細介紹。

(3)數(shù)據(jù)處理階段

系統(tǒng)運行時記錄每次時間步各種策略比值，對趨于穩(wěn)定的后半部分時間步的策略比值集進行數(shù)學(xué)處理，以最小二乘法將這部分實驗數(shù)據(jù)擬合為直線。截取該直線在時間步區(qū)間上的線段求其函數(shù)均值作為策略比例解。全部過程結(jié)束。

3.2 最大收益學(xué)習(xí)模型

當(dāng)前最大收益學(xué)習(xí)模型包括3部分內(nèi)容：

(1)某時刻(即當(dāng)前時間步)的i類型節(jié)點的平均收益，公式如下：

(6)

(7)

(2)策略改變概率，公式如下：

(8)

(3)一個時間步內(nèi)完整的流程。流程如下：

(a)每個節(jié)點(i)從自己相連的節(jié)點集合中隨機選取一個節(jié)點(j)，向其提出請求服務(wù)，并提供自身節(jié)點類型；

(b)收到服務(wù)請求的節(jié)點(j)根據(jù)節(jié)點類型和自身當(dāng)前策略，做出決定；

(c)每個節(jié)點計算本輪自己的收益，將收益值告訴系統(tǒng)；

(d)系統(tǒng)對每類節(jié)點的收益值分類求總和，計算平均收益(式6)，得到本輪平均收益最高的策略(式7)，并將該策略類型，與收益值告訴系統(tǒng)中每一個節(jié)點；

(e)每個節(jié)點將自己策略類型與最高策略比較，相同則保持策略不變，不同則轉(zhuǎn)向6；

(f)節(jié)點將自己收益與平均最高收益值比較，自己的高或相同則不變，低則轉(zhuǎn)向7；

(j)根據(jù)式(8)，計算概率值，節(jié)點按照概率轉(zhuǎn)變策略。

4 實驗結(jié)果與分析

4.1 實驗設(shè)定

為了使實驗仿真更加接近真實情況，因而必須保證網(wǎng)絡(luò)系統(tǒng)具有一定規(guī)模，以減少誤差。本文參考文獻[11]中的節(jié)點數(shù)目，設(shè)定網(wǎng)絡(luò)規(guī)模為節(jié)點數(shù)500。演化步數(shù)設(shè)定為20000時間步，大于一般文獻設(shè)定的不高于3000時間步。策略比值集數(shù)據(jù)截取最后10000時間步。其他相關(guān)初始參數(shù)參照文獻[11]，所有實驗都在同一平臺上進行仿真實驗。具體實驗參數(shù)設(shè)定如下。

實驗參數(shù)參數(shù)值節(jié)點數(shù)500演化步數(shù)20000截取步數(shù)10000

續(xù)表

設(shè)定6組具有代表性的各種初始節(jié)點比例，來分析初始節(jié)點比例對演化過程和演化結(jié)果的影響。比例如下：

組次初始x1x2x3比例第1組(0.05,0.05,0.9)第2組(0.05,0.9,0.05)第3組(0.2,0.55,0.25)第4組(0.35,0.1,0.55)第5組(0.5,0.05,0.45)第6組(0.05,0.05,0.9)

4.2 固定α值實驗過程分析

首先固定α值進行6組實驗。圖1(a)-(f)給出在激勵系數(shù)α=4條件下，完全圖對等網(wǎng)絡(luò)不同初始類型節(jié)點密度條件下，三種類型節(jié)點演化20000步的比例變化過程。每個子圖中不同曲線分別對應(yīng)無私者、互惠者和自私者即時比例。

(a)

(b)

(c)

(d)

(e)

(f)圖1

由圖1可見：(1)不管節(jié)點初始比例怎樣不同，經(jīng)過20000步演化后，各組節(jié)點比例都趨向穩(wěn)定。結(jié)果都趨向于相同的比例值，且遵循x1>x2>x3。

(2)各組演化至穩(wěn)定狀態(tài)所花費的時間不一樣。從圖1大致看出，節(jié)點初始比例與演化穩(wěn)定比例較為接近的組趨于穩(wěn)定花費的時間較短，反之較長。

(3)一些組節(jié)點比例經(jīng)歷了較大幅度的反復(fù)變化，如圖1(d)(e)(f)前期都經(jīng)歷過自私者數(shù)量快速增長的階段。如果設(shè)定的演化時間較短，實驗結(jié)果與演化時間較長的結(jié)果偏差較大，就容易得出不一樣的結(jié)論。

(4)圖1(a)(b)(f)是特意取值較為極端的3種情形，分別對應(yīng)初始時自私者、互惠者、無私者幾乎獨占的狀態(tài)。但從演化變化情況發(fā)現(xiàn)，過程雖然經(jīng)過較大幅度振蕩，結(jié)果仍趨向穩(wěn)定和一致。

圖2

進一步對實驗數(shù)據(jù)進行處理，精確求得節(jié)點所占比例值，見圖2。進而求得數(shù)據(jù)的算術(shù)平均值，并計算三種節(jié)點類型的標(biāo)準(zhǔn)差和離散系數(shù)。見表1。

節(jié)點類型算術(shù)平均值標(biāo)準(zhǔn)差離散系數(shù)無私者(x1)0.550980.003580.006497互惠者(x2)0.3692580.009880.026755自私者(x3)0.0803520.0065840.081945

觀察圖2和分析表1可知，各個評價維度顯示，6組實驗結(jié)果非常接近。因而得出，當(dāng)激勵系數(shù)α=4時，經(jīng)過較長時間演化學(xué)習(xí)后，節(jié)點比例趨向于一個穩(wěn)定值，與初始比例無關(guān)。

4.3 不同α值實驗結(jié)果分析

下面對激勵系數(shù)α為一般值時的情形進一步進行實驗仿真。分別取α=1，2，3，4，5，6，7，8，9，其他參數(shù)同前文設(shè)置，系統(tǒng)仍然按照6組初始比例運行20000步。圖3(a)-(f)為運行后各種節(jié)點類型的所占比例。

觀察圖3(a)-(f)可知：(1)當(dāng)α=1時，事實上等于沒有激勵，無私者在演化過程中消失，不同組互惠者與自私者比例雖然有所不同，但其實效果一樣。沒有了無私者，所謂的互惠者按照鏡像激勵機制的互惠策略，不再給任何節(jié)點提供服務(wù)，本質(zhì)等同于自私者。此時系統(tǒng)已經(jīng)崩潰，節(jié)點彼此之間已不提供服務(wù)。

(a)

(b)

(c)

(d)

(e)

(f)圖3

(2)當(dāng)α>1時，可以大體看出，無論節(jié)點初值比例如何設(shè)定，在α值相同的條件下，演化后的不同組的比例值大體相近。也就意味著一般意義上，不同的初始比例對經(jīng)過長期演化的節(jié)點類型比例值不構(gòu)成影響。

(3)當(dāng)α=2時，無私者數(shù)量稍有增加，雖然對系統(tǒng)性能改善有一定作用，但效果不明顯。自私者比例仍然在70%左右，占據(jù)絕對多數(shù)，而互惠者比例雖有所提高，但按照鏡像激勵機制的互惠策略，大部分互惠節(jié)點為其他節(jié)點提供服務(wù)概率很低，整個系統(tǒng)不具有良好的性能。

(4)當(dāng)α=3時，自私節(jié)點已經(jīng)降到了系統(tǒng)總節(jié)點數(shù)的1/3以下，無私節(jié)點和互惠節(jié)點占據(jù)了大多數(shù)，具有一定優(yōu)勢，但沒有形成壓倒性態(tài)勢。

(5)當(dāng)α=4時，自私節(jié)點降到了10%以下，無私節(jié)點和互惠節(jié)點占據(jù)了絕對優(yōu)勢地位，系統(tǒng)形成了穩(wěn)定的態(tài)勢。

(6)α>4之后，系統(tǒng)保持優(yōu)良的穩(wěn)定性能，但激勵系數(shù)增加的帶來系統(tǒng)的整體效果改善不再像之前明顯，自私節(jié)點整體上呈現(xiàn)平穩(wěn)態(tài)勢下略有下降。

綜上分析，可以得到：(1)鏡像激勵機制并非是一種不成功的激勵機制，而是在較高激勵系數(shù)的條件下，隨著長時間演化，可以實現(xiàn)促進系統(tǒng)節(jié)點間提供服務(wù)的目的。(2)演化穩(wěn)定狀態(tài)與激勵系數(shù)相關(guān)，與初始比例無關(guān)。(3)即使存在激勵機制，但沒有提供實質(zhì)性的激勵(當(dāng)α=1時相當(dāng)于沒有激勵)，系統(tǒng)仍然會走向崩潰。(4)既有激勵機制，又保證實質(zhì)性激勵(α>1)，激勵的效果可以顯現(xiàn)。在較小的激勵系數(shù)變化區(qū)間(2≤α≤4)，激勵系數(shù)增加，能夠明顯有利于無私者和互惠者數(shù)量的增加，自私節(jié)點的減少，有效引導(dǎo)系統(tǒng)趨向合作。但并非隨著激勵系數(shù)的增大，性能改善持續(xù)保持明顯提高。實驗結(jié)果顯示，到達一定值(α=4)后，效果改善不再顯著，而是趨于平緩。由此我們可以得到啟示：系統(tǒng)需要激勵機制，但沒有必要無限制地增加激勵成本。

5 結(jié)論

本文基于完全圖網(wǎng)絡(luò)，構(gòu)建了旨在提高節(jié)點之間服務(wù)概率的鏡像激勵機制框架系統(tǒng)，采用結(jié)合數(shù)學(xué)模型的實驗仿真方法求得了系統(tǒng)穩(wěn)定后各種節(jié)點類型所占總節(jié)點數(shù)的比例。進而發(fā)現(xiàn)，在較短的演化時間內(nèi)，各種節(jié)點的初始比例對演化情形影響較大，但隨著演化時間的增加，演化比例趨于穩(wěn)定。本質(zhì)而言，演化穩(wěn)定時的節(jié)點比例只受激勵系數(shù)影響，而與初始比例無關(guān)。一般而言，激勵系數(shù)的增大，能夠減少自私者在系統(tǒng)中所占的比例，在激勵系數(shù)較小的區(qū)間內(nèi)這種變化較為明顯。隨著激勵系數(shù)增大，這種變化逐漸趨向平緩。本文的局限性在于假設(shè)條件較為嚴(yán)格以及采用了結(jié)合數(shù)學(xué)的實驗方法，探究其背后的數(shù)學(xué)機理以及放寬假設(shè)條件使之更接近真實系統(tǒng)是下一步的研究方向。