基于完全圖網絡的鏡像激勵機制研究

張琦琮，朱立谷

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

1 引言

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

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

2 框架設計與策略描述

一般網絡系統中，節點類型分為無私者和自私者兩種類型。無私者類型節點，采取無條件提供服務的策略，不論請求服務的節點是何種類型。自私者類型節點，采取不提供任何服務的策略，同樣不考慮請求服務的節點是何種類型。所謂鏡像激勵機制，是指在系統原有兩種類型節點的基礎上引入第三種類型節點，該類型節點不是無條件采用提供服務或拒絕服務的策略，而是采用一種新的有條件為對方提供服務的策略，稱為互惠策略，該類型節點稱為互惠者。互惠者的做法如同一面鏡子，“你對別人怎么樣，我就對你怎么樣”。因此該激勵機制稱之為鏡像激勵機制。

2.1 模型系統的設計

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

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

網絡中三種類型節點數目分別為n×x1，n×x2，n×x3。按照博弈理論，三種類型的節點可以認為是三方博弈的參與者，構成參與者集合：{無私者，互惠者，自私者}。參與策略集合：{按照一定比例gi(j)提供服務}。三方博弈關系：無私者對任何類型節點都采取提供服務的策略，因此，g1(j)=1，無私者對無私者、互惠者、自私者構成的策略選擇矩陣為(1 1 1)。自私者對任何類型節點都采取拒絕服務的策略，因此，g3(j)=0，自私者對無私者、互惠者、自私者構成的策略選擇矩陣為(0 0 0)。互惠者采取互惠策略，下文進行詳細分析。

2.2 策略描述

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

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

綜合以上三種類型節點策略，構建模型系統策略選擇矩陣如下：

(1)

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

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

(2)

而獲得其他節點服務的收益矩陣為激勵系數與消耗矩陣的轉置的乘積，如下：

(3)

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

(4)

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

(5)

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

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

3 結合數學模型的實驗分析方法

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

3.1 實驗基本流程

(1)系統初始化階段

首先確定系統規模，生成數量充足、數目固定的節點，并建立兩兩相連的完全圖網絡。對網絡中每個節點按照初始策略比例賦予相應個體策略屬性初值。并假定所有節點都可以滿足提供服務的條件和具備學習能力。最后，系統設置完畢相關參數，如演化步數，學習系數，激勵系數等。

(2)演化學習階段

為便于實現并較為真實地反映實際演化過程，該階段使用當前最大收益學習模型。該模型的核心思想是每個時間步系統得到平均收益最大的策略，采用其他策略的節點按照一定概率改變為該策略。后文作詳細介紹。

(3)數據處理階段

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

3.2 最大收益學習模型

當前最大收益學習模型包括3部分內容：

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

(6)

(7)

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

(8)

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

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

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

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

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

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

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

(j)根據式(8)，計算概率值，節點按照概率轉變策略。

4 實驗結果與分析

4.1 實驗設定

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

實驗參數參數值節點數500演化步數20000截取步數10000

續表

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

組次初始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)給出在激勵系數α=4條件下，完全圖對等網絡不同初始類型節點密度條件下，三種類型節點演化20000步的比例變化過程。每個子圖中不同曲線分別對應無私者、互惠者和自私者即時比例。

(a)

(b)

(c)

(d)

(e)

(f)圖1

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

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

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

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

圖2

進一步對實驗數據進行處理，精確求得節點所占比例值，見圖2。進而求得數據的算術平均值，并計算三種節點類型的標準差和離散系數。見表1。

節點類型算術平均值標準差離散系數無私者(x1)0.550980.003580.006497互惠者(x2)0.3692580.009880.026755自私者(x3)0.0803520.0065840.081945

觀察圖2和分析表1可知，各個評價維度顯示，6組實驗結果非常接近。因而得出，當激勵系數α=4時，經過較長時間演化學習后，節點比例趨向于一個穩定值，與初始比例無關。

4.3 不同α值實驗結果分析

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

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

(a)

(b)

(c)

(d)

(e)

(f)圖3

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

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

(4)當α=3時，自私節點已經降到了系統總節點數的1/3以下，無私節點和互惠節點占據了大多數，具有一定優勢，但沒有形成壓倒性態勢。

(5)當α=4時，自私節點降到了10%以下，無私節點和互惠節點占據了絕對優勢地位，系統形成了穩定的態勢。

(6)α>4之后，系統保持優良的穩定性能，但激勵系數增加的帶來系統的整體效果改善不再像之前明顯，自私節點整體上呈現平穩態勢下略有下降。

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

5 結論

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