基于馬爾可夫決策的P2P激勵(lì)機(jī)制研究

王春枝 周 可 陳宏偉 陳 莉

（武漢理工大學(xué)計(jì)算機(jī)學(xué)院1） 武漢 430070） （湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院2） 武漢 430068）

近年來，P2P網(wǎng)絡(luò)因其所具有的開放性，自治性［1］等，但也因?yàn)樗倪@些特性使得在其應(yīng)用中逐漸暴露出一系列的問題，安全問題尤為突出.馬爾可夫預(yù)測(cè)法［2－3］它是一種只要知道現(xiàn)在的情況，就能確定未來狀態(tài)，并不需要再對(duì)它過去的歷史進(jìn)行認(rèn)識(shí)了解的預(yù)測(cè)方法.本文對(duì)P2P網(wǎng)絡(luò)構(gòu)建一個(gè)預(yù)測(cè)機(jī)制，對(duì)節(jié)點(diǎn)進(jìn)行同步通告、監(jiān)督，并對(duì)節(jié)點(diǎn)隨機(jī)行為進(jìn)行警示、約束、淘汰，促使對(duì)等網(wǎng)絡(luò)中節(jié)點(diǎn)成功通信的概率增長(zhǎng)，直至保持穩(wěn)定.

1 馬爾可夫預(yù)測(cè)法

1.1 Markov鏈

定義1 隨機(jī)過程｛Xn，n＝0，1，2，…｝稱為Markov鏈，若它只取有限個(gè)值，并且對(duì)于任意的n≥0，及任意狀態(tài)i，j，i0，i1，…，in－1，有

式中：Xn＝i為過程在時(shí)刻n處于狀態(tài)i，稱｛0，1，2，…｝為該過程的狀態(tài)空間，記為E；P為系統(tǒng)從狀態(tài)i經(jīng)過一步轉(zhuǎn)移到狀態(tài)j的概率，其中Pij＝P｛Xn＋1＝j(luò)｜Xn＝i｝只與狀態(tài)i，j有關(guān).式（1）刻畫了 Markov鏈的特性，即無后效性［4－5］.

1.2 轉(zhuǎn)移概率

通過式（1），可以得知當(dāng)系統(tǒng)從狀態(tài)i通過一次轉(zhuǎn)移到狀態(tài)j的這一概率稱為一步轉(zhuǎn)移概率.通常，可以把一步轉(zhuǎn)移概率拓展為矩陣的形式，令

由于概率是非負(fù)的，且隨機(jī)過程必須轉(zhuǎn)移到某一狀態(tài)，可以看出pij（i，j∈I）有以下性質(zhì).

定義2 根據(jù)Markov隨機(jī)過程，可根據(jù)一步轉(zhuǎn)移概率矩陣，求出k步轉(zhuǎn)移矩陣，稱這一概率為Markov鏈的k步轉(zhuǎn)移概率矩陣.

定義3 C－K方程［6］，對(duì)一切c，d≥0，i，j∈I有：

1.3 穩(wěn)態(tài)分布

定義4 若 Markov鏈｛En：n≥0｝的狀態(tài)空間I為有限集，且其轉(zhuǎn)移概率矩陣Pij滿足Pij＞0，?i，j∈I，則存在I上惟一的概率分布D＝（D1，D2，D3，…，Dn），使 得 對(duì) 所 有i，j∈I 及min（Pij：ij∈I）≤1／n，都有：（1）D＝DP；（2）Pn＝.

2 基于Markov的預(yù)測(cè)機(jī)制

2.1 節(jié)點(diǎn)狀態(tài)分類

根據(jù)節(jié)點(diǎn)在網(wǎng)絡(luò)中合作概率大小，以及合作態(tài)度將其狀態(tài)分別為4類：（1）積極合作（E1）是網(wǎng)絡(luò)中合作概率最優(yōu)的節(jié)點(diǎn)狀態(tài)，該類狀態(tài)節(jié)點(diǎn)會(huì)積極地將其資源傳送給其他節(jié)點(diǎn)，很少出現(xiàn)背叛，或是失誤，但若網(wǎng)絡(luò)大部分節(jié)點(diǎn)出現(xiàn)群體僥幸心理時(shí)，該類狀態(tài)不排除有轉(zhuǎn)移的可能性；（2）常規(guī)合作（E2）是網(wǎng)絡(luò)中合作概率較良好的狀態(tài)，該類狀態(tài)的節(jié)點(diǎn)有選擇性的將資源傳給需要它的節(jié)點(diǎn)，當(dāng)節(jié)點(diǎn)碰到其交互對(duì)象所需的資源不是它所擁有的，將拒絕與其通信.處于這一群體的節(jié)點(diǎn)，往往為求得最大收益，向其他狀態(tài)轉(zhuǎn)移的概率較大；（3）消極合作（E3）是網(wǎng)絡(luò)中合作概率相對(duì)一般或是較低的狀態(tài)，該狀態(tài)節(jié)點(diǎn)在網(wǎng)絡(luò)中一直從其他節(jié)點(diǎn)搜索，下載資源，起初未對(duì)網(wǎng)絡(luò)進(jìn)行資源貢獻(xiàn)，直至系統(tǒng)機(jī)制對(duì)網(wǎng)絡(luò)中自私節(jié)點(diǎn)進(jìn)行警告時(shí)，這一態(tài)度的節(jié)點(diǎn)會(huì)為防止下一次被機(jī)制淘汰，而被迫進(jìn)行資源共享.這一類型狀態(tài)與常規(guī)狀態(tài)一樣，由于自私性原因，是最易向其他狀態(tài)轉(zhuǎn)移的狀態(tài)；（4）自私（E4）是網(wǎng)絡(luò)中合作概率最低的狀態(tài)，這一態(tài)度的節(jié)點(diǎn)，在網(wǎng)絡(luò)中一直從其他節(jié)點(diǎn)索取資源，從不對(duì)網(wǎng)絡(luò)進(jìn)行資源貢獻(xiàn).但也有極少數(shù)這類狀態(tài)的節(jié)點(diǎn)會(huì)因網(wǎng)絡(luò)機(jī)制的約束，被迫向其他狀態(tài)轉(zhuǎn)移.

根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)合作行為的選擇概率分布，對(duì)節(jié)點(diǎn)的這四類狀態(tài)進(jìn)行概率區(qū)間劃分，設(shè)定節(jié)點(diǎn)狀態(tài)概率區(qū)間為

例如，t時(shí)刻，根據(jù)本文設(shè)定的節(jié)點(diǎn)狀態(tài)概率區(qū)間，自私狀態(tài)P1∈（0，x1］，消極狀態(tài) P∈（x1，x1＋x2］，常規(guī)狀態(tài)P3∈（x1＋x2，x1＋x2＋x3］，積極狀態(tài)P4∈（x1＋x2＋x3，x1＋x2＋x3＋x4］.

2.2 預(yù)測(cè)機(jī)制規(guī)則

本文通過博弈論經(jīng)典的囚徒困境模型對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)進(jìn)行心理分析.可將這一節(jié)點(diǎn)交互的過程看成是一種博弈，從表1中，能很明顯地看出，節(jié)點(diǎn)往往表現(xiàn)出更多的理性，它會(huì)為了使得自身利益最大化，而選擇去欺騙，只要網(wǎng)絡(luò)未對(duì)節(jié)點(diǎn)群體采取約束管理措施，節(jié)點(diǎn)很容易產(chǎn)生僥幸心理，從而一直去選擇欺騙其他節(jié)點(diǎn)，這也是產(chǎn)生P2P網(wǎng)絡(luò)安全問題的原因所在.

表1 囚徒困境模型

2.2.1 預(yù)測(cè)機(jī)制設(shè)置 根據(jù)這一博弈中節(jié)點(diǎn)行為選擇心理，以及針對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)的4種狀態(tài)，在P2P網(wǎng)絡(luò)中設(shè)置一種預(yù)測(cè)系統(tǒng)機(jī)制，并將機(jī)制對(duì)節(jié)點(diǎn)的行為約束規(guī)則統(tǒng)計(jì)如下.

1）對(duì)于進(jìn)入對(duì)等網(wǎng)絡(luò)的各狀態(tài)節(jié)點(diǎn)，機(jī)制允許初始狀態(tài)為自私的節(jié)點(diǎn)存在.

2）每間隔t（t＞0）時(shí)刻，機(jī)制對(duì)當(dāng)前節(jié)點(diǎn)狀態(tài)分布進(jìn)行統(tǒng)計(jì)，并運(yùn)用馬爾可夫鏈對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)未來狀態(tài)進(jìn)行預(yù)測(cè).

3）每隔t時(shí)刻后，機(jī)制根據(jù)統(tǒng)計(jì)的數(shù)據(jù)對(duì)節(jié)點(diǎn)進(jìn)行通告，并根據(jù)預(yù)測(cè)的節(jié)點(diǎn)狀態(tài)轉(zhuǎn)移矩陣，針對(duì)節(jié)點(diǎn)的每種狀態(tài)采取對(duì)應(yīng)的措施，相應(yīng)措施如下：（1）對(duì)于積極狀態(tài)，機(jī)制不會(huì)對(duì)其采取約束措施；（2）對(duì)于常規(guī)狀態(tài)，以博弈收益矩陣為前提，當(dāng)該類狀態(tài)節(jié)點(diǎn)對(duì)其交互對(duì)象采取背叛行為，得到更大的收益時(shí)，為防止其一直保持僥幸心理，機(jī)制將在每隔t時(shí)間后對(duì)該類狀態(tài)進(jìn)行觀測(cè)，若該狀態(tài)以轉(zhuǎn)移向消極，更或是自私，機(jī)制將會(huì)對(duì)其進(jìn)行約束，甚至淘汰；（3）對(duì)于消極狀態(tài)，為防止該狀態(tài)節(jié)點(diǎn)一直保持不貢獻(xiàn)的狀態(tài)，機(jī)制會(huì)在t時(shí)刻后對(duì)該類節(jié)點(diǎn)進(jìn)行激勵(lì)，若節(jié)點(diǎn)有積極趨勢(shì)，則將其保留，若繼續(xù)消極，則將其淘汰；（4）對(duì)于自私狀態(tài)，根據(jù)這一狀態(tài)的特性，每隔t時(shí)刻機(jī)制直接將這類節(jié)點(diǎn)淘汰出網(wǎng)絡(luò).

4）經(jīng)過機(jī)制多次反復(fù)約束，若在某時(shí)刻節(jié)點(diǎn)狀態(tài)處于較為積極的趨勢(shì)，機(jī)制為保持網(wǎng)絡(luò)的穩(wěn)定性，將不再對(duì)網(wǎng)絡(luò)進(jìn)行預(yù)測(cè)，而是直接維護(hù)，淘汰自私節(jié)點(diǎn)，保留其余節(jié)點(diǎn).

2.2.2 預(yù)測(cè)機(jī)制的運(yùn)行 通過對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)狀態(tài)統(tǒng)計(jì)，本文總結(jié)四種節(jié)點(diǎn)狀態(tài)的轉(zhuǎn)換趨勢(shì)，見圖1.

圖1 網(wǎng)絡(luò)整體節(jié)點(diǎn)狀態(tài)轉(zhuǎn)移圖

圖1 顯示，每種狀態(tài)只能由自身或向相鄰的狀態(tài)進(jìn)行轉(zhuǎn)移，不能進(jìn)行跨越轉(zhuǎn)移，例如積極狀態(tài)不能直接轉(zhuǎn)移到自私狀態(tài).這一狀態(tài)轉(zhuǎn)移趨勢(shì)遵循節(jié)點(diǎn)在網(wǎng)絡(luò)中行為規(guī)律，若節(jié)點(diǎn)抱有僥幸心理，通過逐漸背叛，合作概率逐漸減少，進(jìn)而由積極→常規(guī)→消極→自私［6］.

基于馬爾可夫鏈的預(yù)測(cè)方法，機(jī)制會(huì)對(duì)每隔t時(shí)刻的節(jié)點(diǎn)狀態(tài)進(jìn)行統(tǒng)計(jì)，設(shè)在t時(shí)刻，網(wǎng)絡(luò)中四類節(jié)點(diǎn)狀態(tài)為E，E∈（En，n＝1，2，3，4），節(jié)點(diǎn)狀態(tài)的初始分布為 Pt（0）＝（Pt1（0），Pt2（0），Pt3（0），Pt4（0））.根據(jù)圖1節(jié)點(diǎn)的狀態(tài)轉(zhuǎn)移情況，構(gòu)建一個(gè)節(jié)點(diǎn)狀態(tài)概率轉(zhuǎn)移矩陣.假設(shè)處于Ei狀態(tài)的節(jié)點(diǎn)個(gè)數(shù)為mi，由Ei轉(zhuǎn)移到狀態(tài)Ej的個(gè)數(shù)為mij，則可以得到網(wǎng)絡(luò)中節(jié)點(diǎn)由Ei轉(zhuǎn)移到狀態(tài)Ej的狀態(tài)轉(zhuǎn)移概率Pij，且Pij＝mij／mi.由此可得，網(wǎng)絡(luò)節(jié)點(diǎn)的4種狀態(tài)轉(zhuǎn)移矩陣P

預(yù)測(cè)機(jī)制根據(jù)這一節(jié)點(diǎn)狀態(tài)轉(zhuǎn)移矩陣，可以得到未來任意時(shí)刻網(wǎng)絡(luò)節(jié)點(diǎn)狀態(tài)的轉(zhuǎn)移情況，即，假設(shè)在n時(shí)刻，網(wǎng)絡(luò)節(jié)點(diǎn)狀態(tài)轉(zhuǎn)移矩陣P［n］＝P（0）·Pn，并由D＝D·P，得到網(wǎng)絡(luò)節(jié)點(diǎn)狀態(tài)的穩(wěn)態(tài)分布向量，進(jìn)而得到未來網(wǎng)絡(luò)節(jié)點(diǎn)狀態(tài)的穩(wěn)態(tài)轉(zhuǎn)移概率矩陣.

3 仿真分析

在Ti時(shí)刻，統(tǒng)計(jì)前t段時(shí)間內(nèi)的節(jié)點(diǎn)狀態(tài)分布數(shù)據(jù)，得到表2.

表2 t時(shí)間段內(nèi)節(jié)點(diǎn)狀態(tài)轉(zhuǎn)移分布

根據(jù)表2數(shù)據(jù)統(tǒng)計(jì)，可建立節(jié)點(diǎn)狀態(tài)轉(zhuǎn)移矩陣P為

式（7）中，在未加入系統(tǒng)機(jī)制的情況下，積極狀態(tài)與自私狀態(tài)大部分是向自身轉(zhuǎn)移，只有極少數(shù)向其他狀態(tài)轉(zhuǎn)移，而在大多數(shù)節(jié)點(diǎn)存在的常規(guī)狀態(tài)和消極狀態(tài)逐步兩極分化，并更多地轉(zhuǎn)移向自私狀態(tài)，由于節(jié)點(diǎn)進(jìn)行博弈行為選擇過后發(fā)現(xiàn)自私獲取資源遠(yuǎn)遠(yuǎn)比貢獻(xiàn)資源要輕松的多，于是更多地采取背叛行為，形成僥幸心理，導(dǎo)致網(wǎng)絡(luò)資源利用不均，節(jié)點(diǎn)誠(chéng)信問題的嚴(yán)重.

由Ti時(shí)刻網(wǎng)絡(luò)的4種節(jié)點(diǎn)狀態(tài)分布，以及其狀態(tài)轉(zhuǎn)移概率矩陣，可計(jì)算得到未來節(jié)點(diǎn)狀態(tài)的穩(wěn)態(tài)分布向量D＝［0.080 0 0.051 0 0.140 2

0.728 8］.分析這一穩(wěn)態(tài)向量，可預(yù)測(cè)到若網(wǎng)絡(luò)節(jié)點(diǎn)狀態(tài)繼續(xù)由這一概率矩陣進(jìn)行轉(zhuǎn)移，網(wǎng)絡(luò)總體狀態(tài)必然趨向于自私，也就是由于節(jié)點(diǎn)僥幸心理群體化，改變節(jié)點(diǎn)博弈行為選擇，最終影響網(wǎng)絡(luò)的穩(wěn)定性.

由于提前預(yù)知到網(wǎng)絡(luò)節(jié)點(diǎn)博弈行為的這一惡化，節(jié)點(diǎn)狀態(tài)未來的改變趨勢(shì)，本文在這一時(shí)刻對(duì)網(wǎng)絡(luò)中設(shè)置預(yù)測(cè)機(jī)制，從細(xì)節(jié)入手，對(duì)節(jié)點(diǎn)博弈行為選擇進(jìn)行約束，從而對(duì)節(jié)點(diǎn)4種狀態(tài)轉(zhuǎn)移進(jìn)行控制，并實(shí)時(shí)對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)狀態(tài)進(jìn)行統(tǒng)計(jì)，淘汰頑固自私節(jié)點(diǎn).

本文利用matlab仿真軟件，對(duì)預(yù)測(cè)機(jī)制未加入前的網(wǎng)絡(luò)節(jié)點(diǎn)狀態(tài)分布進(jìn)行仿真，并對(duì)得到預(yù)測(cè)機(jī)制約束后的網(wǎng)絡(luò)節(jié)點(diǎn)狀態(tài)進(jìn)行了仿真對(duì)比，得到以下曲線圖.

通過圖2和圖3可看到，只要機(jī)制對(duì)節(jié)點(diǎn)進(jìn)行一定的行為約束，節(jié)點(diǎn)的狀態(tài)趨勢(shì)有稍微的轉(zhuǎn)變，整個(gè)網(wǎng)絡(luò)的節(jié)點(diǎn)狀態(tài)在未來的發(fā)展趨勢(shì)都會(huì)有很大的變化，證實(shí)了預(yù)測(cè)機(jī)制的存在對(duì)于P2P網(wǎng)絡(luò)是有積極作用的，其對(duì)于網(wǎng)絡(luò)的穩(wěn)定性，和節(jié)點(diǎn)間的信任都有了很大的輔助作用.也可以看到節(jié)點(diǎn)狀態(tài)的任意變化都會(huì)對(duì)整個(gè)網(wǎng)絡(luò)造成很大的影響，所以機(jī)制的存在是有必要的，而且需要預(yù)測(cè)機(jī)制同時(shí)在每時(shí)刻都對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)狀態(tài)進(jìn)行跟蹤、預(yù)測(cè)，以防止網(wǎng)絡(luò)出現(xiàn)癱瘓的可能.

圖2 未加入預(yù)測(cè)機(jī)制后的網(wǎng)絡(luò)節(jié)點(diǎn)狀態(tài)分布

圖3 加入預(yù)測(cè)機(jī)制后的網(wǎng)絡(luò)節(jié)點(diǎn)狀態(tài)分布

4 結(jié)束語(yǔ)

本文通過對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)歷史行為進(jìn)行統(tǒng)計(jì)，根據(jù)節(jié)點(diǎn)選擇合作行為概率將節(jié)點(diǎn)狀態(tài)進(jìn)行分類，并對(duì)節(jié)點(diǎn)這4種狀態(tài)進(jìn)行分析，研究節(jié)點(diǎn)行為選擇趨勢(shì).進(jìn)而在P2P網(wǎng)絡(luò)中設(shè)置一種預(yù)測(cè)機(jī)制，通過對(duì)節(jié)點(diǎn)狀態(tài)分布進(jìn)行統(tǒng)計(jì)，對(duì)未來網(wǎng)絡(luò)節(jié)點(diǎn)狀態(tài)發(fā)展趨勢(shì)進(jìn)行預(yù)測(cè)，通過預(yù)測(cè)結(jié)果及時(shí)選擇相應(yīng)地策略對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行約束.通過仿真，證實(shí)了該機(jī)制對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)自私行為具有約束性，有效性，進(jìn)而能夠維護(hù)網(wǎng)絡(luò)的穩(wěn)定性.今后將繼續(xù)對(duì)馬爾可夫隨機(jī)過程與P2P信任博弈模型的結(jié)合進(jìn)行更為細(xì)致的研究.

［1］Yu Yijiao，Jin Hai.A survey on overcoming free riding in peer－to－peer networks［J］.Chinese Journal of Computers，2008，3l（1）：1－15.

［2］Cao X R.Semi－markov decision problems and performance sensitivity analysis［J］.IEEE Trans on Automatic Control，2003，48（5）：758－769.

［3］BumPkin C，Agrawa1D.A game theoretic framework for incentives in P2Psystems［C］／／Proc.of the third International Conference on Peer－to－peer Computing，2003.

［4］Wang Y ，Vassileva J.Bayesian network based trust model［C］／／Proceedings of the IEEE／WIC International Conference on Web Intelligence（WI＇03），Halifax，Canada，2003：372－378.

［5］RabinerL R.A tutorial on hidden Markov models and selected applications in speech recognition［J］.Proceedings of the IEEE，1989，77（2）：257－286.

［6］Park H S，Lee S W.A truly 2－D hidden markov model for off－line handwritten character recognition［J］.Pattern Recognition，1998，31（2）：1 864－1 894.