王春枝 周 可 陳宏偉 陳 莉

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

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

1 馬爾可夫預測法

1.1 Markov鏈

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

式中：Xn＝i為過程在時刻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｜Xn＝i｝只與狀態(tài)i，j有關(guān).式（1）刻畫了 Markov鏈的特性，即無后效性［4－5］.

1.2 轉(zhuǎn)移概率

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

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

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

定義3 C－K方程［6］，對一切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），使 得 對 所 有i，j∈I 及min（Pij：ij∈I）≤1／n，都有：（1）D＝DP；（2）Pn＝.

2 基于Markov的預測機制

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

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

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

例如，t時刻，根據(jù)本文設定的節(jié)點狀態(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 預測機制規(guī)則

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

表1 囚徒困境模型

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

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

2）每間隔t（t＞0）時刻，機制對當前節(jié)點狀態(tài)分布進行統(tǒng)計，并運用馬爾可夫鏈對網(wǎng)絡節(jié)點未來狀態(tài)進行預測.

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

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

2.2.2 預測機制的運行 通過對網(wǎng)絡節(jié)點狀態(tài)統(tǒng)計，本文總結(jié)四種節(jié)點狀態(tài)的轉(zhuǎn)換趨勢，見圖1.

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

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

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

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

3 仿真分析

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

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

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

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

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

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

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

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

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

圖2 未加入預測機制后的網(wǎng)絡節(jié)點狀態(tài)分布

圖3 加入預測機制后的網(wǎng)絡節(jié)點狀態(tài)分布

4 結(jié)束語

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

［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.