自私性移動P2P網絡中節點激勵策略研究

劉 浩 陳志剛 張連明

?

自私性移動P2P網絡中節點激勵策略研究

劉 浩*①陳志剛②張連明③

①(湖南人文科技學院信息學院 婁底 417000)②(中南大學信息科學與工程學院 長沙 410083)③(湖南師范大學物理與信息科學學院 長沙 410081)

該文針對移動P2P網絡中節點表現出來的自私性，并結合移動P2P網絡的資源受限、自組織以及開放性等特點，提出一種基于不完全信息的雙方叫價拍賣模型的節點激勵策略—DAIP。該激勵策略采用虛擬貨幣的支付方式，節點根據其擁有的虛擬貨幣量、自身資源狀態和消息屬性對每次消息轉發進行估價，然后根據估價與博弈策略給出相應報價。通過博弈分析給出了DAIP策略的線性策略貝葉斯納什均衡解，使各節點為最大化其自身利益而積極參與消息轉發合作，從而促進網絡系統中消息轉發合作的成功。分析與實驗結果表明該激勵策略能夠降低系統的能量消耗，提高整個網絡系統的消息轉發成功率，提高系統的整體效用。

移動P2P網絡；自私性；拍賣模型；虛擬貨幣；激勵策略

1 引言

近年來，無線通信技術得到了快速發展，移動用戶的資源共享與協同工作需求日益增長，從而促進了移動P2P網絡的廣泛應用。當前，移動P2P網絡已經得到了網絡通信領域產業界和學術界的普遍關注[1]。然而，移動P2P網絡的自組織與動態性等特點，一方面使大量的移動用戶節點加入到移動P2P網絡中，另一方面也使網絡中自私性節點普遍存在[2]。自私節點總是盡可能地利用網絡系統中的各種資源，如存儲資源、計算資源以及文件資源等，卻不愿意貢獻出自身的資源，這就導致整個網絡系統的可用資源存在很大的變數。顯然，這與P2P網絡實現的基本理念“人人為我，我為人人”是相違背的[3]。相關研究表明，在Gnutella等P2P網絡中，存在著60%以上只消費網絡資源而不愿意共享自身資源的freerider節點。并且，移動P2P網絡中存在著大量不可靠的服務質量和欺詐行為[2]。用戶節點的自私行為嚴重影響了移動P2P網絡服務的可用性，降低了系統的整體效用。顯然，如何構建有效的激勵策略，約束節點的自私行為，激勵節點間的相互合作，是移動P2P網絡需要解決的關鍵問題之一[2,3]。

目前，P2P網絡中節點的激勵策略大致可分為區分服務與虛擬支付兩類[3,6]。區分服務類型激勵策略的基本思想是，給予積極參與資源共享和協同合作的節點更高級別的服務(如享受優先服務等)。針對P2P網絡中節點的搭便車行為，樂光學等人[6]在P2P可信流媒體網絡環境下給出了一種以節點的貢獻度、信譽度及其收益為評價指標的抑制機制。針對P2P文件共享系統中用戶節點的搭便車行為，若僅僅使用獎勵等區分服務激勵策略是不夠的，文獻[7]對相應激勵策略的公平性進行了評估與改進。基于重復博弈相關理論，文獻[8]在P2P網絡中建立了對自私節點的懲罰機制，并通過制定相關的行為規則，激勵理性節點為使其自身收益最大化而向網絡系統貢獻相關資源。基于Stackelberg博弈方法，文獻[9]給出了一個基于信用的異構對等網絡中節點的激勵策略，該策略通過偏袒的資源配置機制，根據節點的不同信用值為其提供不同的服務，以激勵節點間的相互合作。牛新征等人[10]針對移動P2P網絡中移動節點的資源有限和網絡拓撲的動態性，基于依據排隊理論與可靠性理論，構建了一種移動節點間層次型資源調度模型與資源協作共享方案，通過動態調整節點的隊列優先權激勵節點參與資源共享。盡管基于區分服務思想的激勵策略容易實現，然而在該類型激勵策略作用下，網絡系統的整體效用與每個節點的自身利益很難同時達到最優，因此，理性的自私節點仍然存在違背協議的動機[3,6]；同時，若評價機制不夠完善，節點間還可能存在共謀現象。基于虛擬支付激勵策略的基本思想是：節點采用虛擬貨幣來支付所獲得的各種網絡服務，當為其他節點提供各種網絡服務時則能夠獲得以虛擬貨幣形式的報酬[11]。基于虛擬支付的激勵策略在機會網絡、無線網絡、P2P網絡等領域應用廣泛，尤其是與博弈論相結合，將成熟的博弈論思想應用于虛擬支付的激勵策略中，能夠有效地解決網絡系統中節點的自私性問題，提高系統的整體效用。基于虛擬支付和演化博弈理論，文獻[12]提出了一種自組織網絡中節點間的協同合作激勵策略。文獻[13]針對機會網絡中邊緣注入和邊緣隱藏攻擊等問題，提出了一種MobiCent機制，該機制使用倍減算法來計算報酬，以激勵網絡系統中節點間的相互合作。為提高移動對等網絡數據的可用性，文獻[14]提出了一種基于經濟激勵的經紀方案，激勵中繼節點作為路由和消息轉發的經紀人，以提高對等網絡的路由與消息轉發效率。為了約束移動P2P網絡中節點“搭便車”的行為，提高網絡的搜索效率，基于資源拍賣文獻[15]給出了一種節點激勵策略，系統通過拍賣經濟模式激勵節點為獲得收益而貢獻相應的資源，該激勵策略能夠有效地提高系統的整體效用，達到優化系統性能的目標。針對機會網絡中節點的自私性問題，并結合機會網絡中節點資源受限等特點，李云等人[16]提出了一種基于買賣模型的節點消息轉發激勵策略，有效地解決節點盲目合作帶來的網絡性能退化問題。文獻[17]給出了一種基于進化博弈的資源配置模型，將資源配置問題抽象為一種進化博弈,通過策略與收益函數來分析資源配置過程中節點對資源副本的選擇行為及其對查詢性能的影響；以約束有限理性節點在配置過程中的自私行為,從而提高系統的查詢性能。這些激勵策略大多數是通過各種規則、策略來激勵自私節點進行合作，并沒有考慮節點自身資源受限等因素對節點行為的影響。因此，它們并不適用于節點資源受限的移動P2P網絡。同時，它們在追求網絡系統整體效用最優時，也沒有充分考慮理性節點的自私性，即最大化其自身收益。

為了描述方便，本文的分析場景為移動P2P網絡中節點間的消息轉發合作過程。由于移動P2P網絡中節點資源是有限的，假如節點激勵策略不考慮資源的使用情況，就會造成節點因能源耗盡而直接退出網絡，從而導致整個網絡系統性能退化，會造成更大的損失。因此，在綜合考慮移動網絡中節點的自身狀態和消息屬性等因素，給出了一種基于不完全信息的雙方叫價拍賣模型的節點激勵策略—DAIP(Double Auction basedIncentive Protocol)。

2 網絡模型

本質上，移動P2P網絡是各種移動終端以自組織方式建立在網絡層之上的分布式覆蓋網絡，通過利用移動終端的空閑資源進行資源共享和協作工作[1]。比如，當遇到自然災害(如地震等)時，現有的基礎設施遭到破壞，一般可利用移動設備快速建立移動自組網，這里的移動自組網上覆蓋網絡就屬于移動P2P網絡。由于這些移動節點所擁有的能量、緩存等資源都是有限的，并且能量是不可再生的。一方面，移動節點加入網絡系統，是以資源共享與協同工作為目的，這就會消耗其自身的資源。另外一方面，移動節點為了保證較長時間的正常工作，就會盡可能地節約其所擁有的資源，那么就會表現出其自私性。并且，對于移動P2P網絡中節點的惡意行為，一般來說激勵策略沒有抑制作用，通常是采用信任機制來達到抑制惡意節點的目標。因此，在網絡模型方面，這里先給出一些相關的理論假設。

(1)每個移動節點都是理性的自私節點，若在某次消息轉發交易中無法收益時，就不會參與本次消息轉發交易。

(2)自私節點都是有限理性的，在自身狀態允許的情況下，節點在消息轉發交易中都會考慮自身利益的最大化。

(3)理性的自私節點并不是惡意節點，都會根據自身狀態和消息屬性對每次消息轉發交易進行估價。

(4)在約定的觀測時間周期內，所有移動節點的能量都不能得到補充，且在運行過程中知曉其能量狀態，當能量耗盡時則自動退出網絡。

(5)每個移動節點都不會最終接收其他節點的消息，除非它是消息的目的節點。

3 基于不完全信息的雙方叫價拍賣模型的節點激勵策略

本文給出的基于不完全信息雙方叫價拍賣模型的節點激勵策略DAIP是一種基于虛擬貨幣支付的激勵策略。與已有工作不同，該激勵策略DAIP綜合考慮了移動節點的自身狀態與消息屬性等因素對節點估價的影響。DAIP策略不需要信任第三方來管理交易過程，每個移動節點各自管理自身的虛擬貨幣、緩存、能量等資源，每次消息轉發交易完成后，消息轉發請求節點向消息轉發服務節點支付虛擬貨幣作為報酬。因此，DAIP策略適用于移動P2P網絡這樣的完全分布式系統。

3.1 基本概念與定義

在移動P2P網絡中，影響節點進行消息轉發合作意愿的因素較多。在此，DAIP策略主要考慮節點的能量、緩存與虛擬貨幣量以及所需轉發消息的屬性等一些重要的因素。

消息屬性包括消息的大小與消息的剩余生存時間。在其他條件相同的情況下，消息越大，轉發信息的時間越長，所消耗的能量越大。消息的剩余生存時間是指從當前時刻到消息過期(生存周期結束)這段時間，消息的剩余生存時間越短，說明該消息越應盡快轉發到達目的節點。

定義8 設消息傳輸的能量消耗與消息大小成正比，其中比例系數為。即每傳輸1 MB的消息，服務節點將消耗J能量。

3.2 不完全信息的雙方叫價拍賣模型

在此，將移動節點間消息轉發過程抽象成不完全信息的雙方叫價拍賣交易過程。在交易過程中，雙方都只知曉自身的狀態與消息屬性，但并不了解對方的狀態等其他情況，也就是說雙方在對本次消息轉發交易估價時，信息是不完全的。其中，交易的賣方是提供消息轉發服務的節點，買方是需要轉發消息的請求節點。在交易過程中，買方通過支付虛擬貨幣來購買賣方的消息轉發服務。

3.2.1拍賣交易規則 每次消息轉發交易必須滿足以下規則：

(1)每次交易開始時，買賣雙方各自根據下面的估價函數對本次消息轉發交易進行估價。設賣方對本次消息轉發交易的(成本)估價為，其中；設買方對本次消息轉發交易的(價值)估價為，其中。

3.2.2買方估價函數 在發送消息時，作為買方，消息發送節點需要對本次消息轉發進行(價值)估價。買方在估價時，主要會考慮自身的財富狀態、緩存與消息的屬性。作為理性節點，買方的剩余緩存百分比越小，為了減小緩存壓力，節點發送出消息的意愿越強烈；消息需要轉發的緊急程度越高，購買消息轉發服務的意愿越強烈。并且，若買方越富裕，即其擁有的虛擬貨幣量越大，則它更愿意出一個相對高的價格來支付本次消息轉發服務。那么，買方的估價函數可以表示為

(7)

由于節點剩余緩存的變化是可逆的，而能量是隨時間嚴格遞減的，并且，只要兩者之一變小，賣方提供消息轉發服務的要價就會越高，因此，可采用自適應加權。當剩余帶寬百分比小于剩余能量百分比時，前者對賣方出價的影響則大，反之亦然。則有

(9)

3.3消息轉發過程

圖1 消息轉發過程

具體描述如下：

4 博弈分析

不完全信息雙方叫價拍賣的動態博弈是有共同利益的兩個交易者面臨沖突(就某一商品進行談判報價)時試圖達成一致協議的一種博弈過程；利益相關雙方都認定自己對該商品的估價(價值或成本)是私人信息，對方是不知曉的，即在不完全信息條件下博弈；并且利益相關雙方都希望在本次交易過程中最大化其自身利益。在前面的拍賣交易模型中，約定了規則：當時，本次消息轉發交易成功，交易的最終價格為。但是如何才能夠保證消息轉發服務節點按約定的規則提供轉發服務，同時，消息轉發請求節點按約定的規則接收轉發服務。為解決該問題，這里將節點間的消息轉發過程抽象為一個不完全信息雙方叫價拍賣的動態博弈，激勵理性的博弈雙方(節點與節點)為最大化自身利益而積極參與消息轉發合作，從而促進消息轉發合作的成功。

4.1博弈方及其策略

(1)信息是不完全的，即：賣方只知道本次消息轉發交易的(成本)估價，買方只知道本次消息轉發交易的(價值)估價為；

4.2博弈均衡分析

本文假設每個移動節點都是理性的自私節點，那么在消息轉發博弈過程中，每個移動節點都會考慮自身利益的最大化。下面來分析博弈雙方(節點與節點)如何來選擇報價策略(,)，使其各自的利益最大化，同時達到納什均衡。

滿足式(10)，式(11)后，分別有

參考文獻[18,19]，最優化一階條件有

解兩個一階條件得到線性策略均衡解為

給出線性策略均衡分析圖如圖2所示。

從圖2可以看出，在線性策略均衡下，

由線性策略均衡解式(12)和拍賣交易規則(3) 可以推出：

圖2 線性策略均衡分析圖

通過以上對消息轉發博弈過程的均衡分析可知，本文將消息轉發過程抽象為一個不完全信息雙方叫價拍賣的動態博弈，能夠激勵博弈雙方(節點與節點)在追求自身利益最大化的同時積極參與消息轉發合作，從而促進消息轉發合作的成功。

5 仿真試驗與結果分析

為了評價激勵策略DAIP的網絡性能，我們采用JXTA開發平臺來實現網絡模型中的相關機制與協議，其中以按需路由協議AODV作為仿真實驗中的路由協議。

實驗場景參數設置：500個移動節點(無線終端)隨機分布在4000 m×3000 m的區域內，每個節點使用IEEE802.11無線網絡接口，節點移動速度為0~20 m/s，節點通信半徑為100 m，移動方式遵循Random Waypoint 移動模型。每個節點的初始能量為1000 J，發射功率為1 W，緩存空間初始值為30 MB，并假設節點只有在參與消息轉發合作時才會消耗能量，其中每次消息轉發請求與響應等過程消耗能量1 J，消息傳輸的能量消耗比例系數為，即1 MB的消息傳輸消耗2 J能量。模擬時間為4 h，其中最初的5 min為熱身時間，網絡系統每1 min隨機地產生500個大小服從[0.5,1] MB均勻分布的消息。設,,,,。

實驗 1 設文獻[16]給出的基于買賣模型節點激勵策略簡稱為BIP，該激勵策略借鑒了雙向叫價的拍賣交易模型，并通過單一價格策略均衡來激勵機會網絡中自私性節點的合作。分別在網絡系統中采用DAIP策略、BIP策略和不采用任何激勵策略Nature狀態的3種情況下，當網絡系統中自私節點的比例增大時，考察整個網絡系統中消息轉發的平均成功率，其實驗結果如圖3所示。

從圖3可知，當網絡系統中自私節點的比例增大時，在不采用任何激勵策略的Nature狀態下，系統的消息轉發平均成功率快速下降，極端情況網絡系統性能嚴重退化；采用BIP激勵策略，系統的消息轉發平均成功率緩慢下降；采用DAIP激勵策略，系統的消息轉發平均成功率基本保持不變。原因是在不采用任何激勵策略的Nature狀態下，理性的自私節點可能不會參與消息轉發合作，這就會降低消息轉發的成功率。并且，DAIP激勵策略比BIP激勵策略更能夠提高系統的消息轉發成功率。

實驗2 設網絡系統中的移動節點都是理性的自私節點，分別在網絡系統中采用DAIP策略、BIP策略和不采用任何激勵策略Nature狀態的3種情況下，當網絡系統中消息轉發成功的次數增加時，考察所有節點的平均剩余能量，其實驗結果如圖4所示。

從圖4可以看出，當網絡系統中消息轉發成功的次數增加時，在不采用任何激勵策略的Nature狀態下，網絡系統中所有節點的平均剩余能量減少的較快；若采用BIP激勵策略，網絡系統中所有節點的平均剩余能量減少得較慢；采用DAIP激勵策略，則平均剩余能量減少得最慢。原因是不采用任何激勵策略，由于節點的自私性，可能不會參與消息轉發合作，那么在達到相同消息成功轉發的次數時，會增大消息轉發請求與響應等過程的次數，從而加大了能量消耗。并且，相對于BIP激勵策略，采用DAIP激勵策略的系統整體效用更高。

在不完全信息的雙方叫價拍賣動態博弈中，主要有單一價格策略均衡和線性策略均衡。相關研究結果[18,19]表明，從最大化交易比例來說，線性策略均衡優于單一價格策略均衡，或者說線性策略均衡的效率是最高的。因此，理論分析與仿真實驗結果一致表明DAIP激勵策略要優于BIP激勵策略。

綜上所述，采用DAIP激勵策略能夠有效地提高整個網絡系統的消息轉發成功率，降低系統的能量消耗，提高系統的整體效用，達到了預期的設計目標。

6 結束語

通過借鑒雙方叫價拍賣模型、博弈論的基本原理，本文給出了一種自私性移動P2P網絡環境下節點間消息轉發過程中的激勵策略DAIP。該策略通過虛擬貨幣支付方式，有效地激勵自私節點進行合作，給自私性移動P2P網絡中節點激勵策略等相關研究提供了一種新的研究思路。盡管DAIP策略不失為一種有效的節點激勵策略，但是并沒有考慮如何保證節點進行真實報價或者說如何約束節點進行虛假報價的行為，也沒有研究如何約束節點因自身的富裕性出現的偏好自私性問題。因此，我們未來將重點圍繞這些相關工作進行研究。

圖3 3種情況下平均交互成功率的比較圖

圖4 3種情況下平均剩余能量的比較圖

[1] 張國印, 李軍. 移動對等網絡覆蓋網[J]. 軟件學報, 2013, 24(1): 139-152. doi: 10.3724/SP.J.1001.2013.04332.

ZHANG G Y and Li J. Overlays in mobile P2P networks[J]., 2013, 24(1): 139-152. doi: 10.3724/SP.J. 1001.2013.04332.

[2] COURCOUBETIS C and WEBER R. Incentives for large peer-to-peer systems[J]., 2006, 24(5): 1034-1050.

[3] 曲大鵬, 王興偉, 黃敏. 移動對等網絡中自私節點的檢測和激勵策略[J]. 軟件學報, 2013, 24(4): 887-899. doi: 10.3724/SP. J.1001.2013.04290.

QU D P, WAND X W, and HUANG M. Selfish node detection and incentive mechanism in mobile P2P networks [J]., 2013, 24(4): 887-899.doi: 10.3724/ SP.J.1001.2013.04290.

[4] SAFIRIYU E and DAUDA A. A novel decurity protocol for P2P incentive schemes[J]., 2015, 5(2): 1046-1051.

[5] FELDMAN M, PAPADIMITRIOU C, and CHUANG J. Free-riding and whitewashing in peer-to-peer systems[J]., 2006, 24(5): 1010-1019.

[6] 樂光學, 李仁發, 陳志, 等. P2P網絡中搭便車行為分析與抑制機制建模[J]. 計算機研究與發展, 2011, 48(3): 382-397.

LE X G, LI R F, CHEN Z,. Analysis of Free-riding behaviors and modeling restrain mechanisms for peer-to-peer networks[J]., 2011, 48(3): 382-397.

[7] LI Y Z, GRUENBACHER D, andSCOGLIO C. Reward only is not enough: Evaluating and improving the fairness policy of the P2P file sharing network eMule/eDonkey[J].--, 2012, 5(1): 40-57.

[8] CHEN H W, XU H, and CHEN L. Incentive mechanisms for P2P network nodes based on repeated game[J]., 2012, 7(2): 385-392.

[9] KANG X and WU Y D. Incentive mechanism design for heterogeneous peer-to-peer networks: A stackelberg game approach[J]., 2015, 14(5): 1-13.

[10] 牛新征, 周明天, 佘堃. 一種應用于移動P2P網絡的資源協作共享策略[J]. 電子學報, 2010, 38(1): 18-24.

NIU X Z, ZHOU M T, and SHE K. A cooperative sharing scheme for resources in mobile P2P networks[J]., 2010, 38(1): 18-24.

[11] TAN G and JARVIS S A. A payment-based incentive and service differentiation scheme for peer-to-peer streaming broadcast[J]., 2008, 19(7): 940-954.

[12] YANG Y,LIU B, and SHI Y. Design and simulation of the cooperation incentive mechanism in ad hoc network based on evolutionary game[J]., 2015, 9(10): 2827-2834.

[13] CHENG G, SONG M, ZHANG Y,. Routing protocol based on social characteristics for opportunistic networks[J]., 2014, 21(1): 67-73.

[14] PADHARIYA N, MONDAL A, MADRIA S K,. Economic incentive-based brokerage schemes for improving data availability in mobile-P2P networks[J]., 2013, 36(2): 861-874.

[15] DING H and PEI J M. The research of resource auction incentive mechanism in mobile P2P[C]. International Conference on Wireless Communications, Networking & Mobile Computing, Beijing, China, 2010: 1-3.

[16] 李云, 于季弘, 尤肖虎. 資源受限的機會網絡節點激勵策略研究[J]. 計算機學報,2013, 35(5): 947-956. doi: 10.3724/SP.J. 1016.2013.00947.

LI Y, YU J H, and YOU X H. An incentive protocol for opportunistic networks with resources constraint[J].,2013, 35(5): 947-956.doi: 10.3724/ SP.J.1016.2013.00947.

[17] 周經亞, 宋愛波, 羅軍舟.P2P 網絡中一種基于進化博弈的資源配置模型[J]. 軟件學報,2013, 24(3): 526-539. doi:10.3724/ SP.J.1001.2013.04229.

ZHOU J Y, SONG A B, and LUO J Z. Evolutionary game theoretical resource deployment model for P2P networks[J]., 2013, 24(3): 526-539. doi:10.3724/SP.J. 1001.2013.04229.

[18] 李幫義, 王玉燕. 博弈論與信息經濟學[M]. 北京: 科學出版社, 2016: 253-260.

LI B Y and WANG Y Y. Game Theory and Information Economics[M]. Beijing: China, Science Press, 2016: 253-260.

[19] TADELIS S. Game Theory: An Introduction[M]. Princeton, US: Princeton University Press, 2012: 428-432.

Research on Node Incentive Protocol in Selfish Mobile Peer-to-peer Network

LIU Hao①CHEN Zhigang②ZHANG Lianming③

①(,,,417000,)②(,,410083,)③(,,410081,)

In view of the selfishness of nodes in mobile Peer-to-Peer (P2P) network, combined with its features of the resource-constrained, self-organization and opening, this paper proposes a novel Incentive Protocol DAIP of mobile P2P network based on Double Auction model of incomplete information on both sides. The incentive mechanism adopts virtual currency payment method. The node calculates the evaluation of a message forwarding based on the virtual currency, resource state of it and the property of message, then gives the corresponding price according to the evaluation and game strategy. Through the game analysis, the linear strategy Bayes Nash equilibrium solution of DAIP strategy is given, which makes each node to maximize its own benefits, encourages them to cooperate with the message forwarding, and then improves the success rate of message forwarding in the network system. Analysis and simulation show that this incentive mechanism is able to effectively reduce the system's energy consumption, improve the success rate of message forwarding in the whole network system, and improve the overall effectiveness of the system.

Mobile Peer-to-Peer (P2P) network; Selfishness; Auction model; Virtual currency; Incentive protocol

TP393

A

1009-5896(2017)08-1986-07

10.11999/JEIT161335

2016-12-08；

改回日期：2017-05-19；

2017-06-14

劉浩 lhkd0407@126.com

國家自然科學基金(61572191, 61571188 )，湖南省自然科學基金(2017JJ2124)，湖南省教育廳優秀青年科研項目 (15B125)，湖南省計算機應用技術重點建設學科資助項目

The National Natural Science Foundation of China (61572191, 61571188), The Natural Science Foundation of Hunan Province (2017JJ2124), The Outstanding Youth Scientific Research Foundation of Department of Education, Hunan Province (15B125),The Key Construction Course of Computer Application Technology in Hunan Province

劉 浩： 男，1977年生，副教授，研究方向為并行計算、P2P網絡.

陳志剛： 男，1964年生，教授，研究方向為計算機網絡與分布式系統.

張連明： 男，1972年生，教授，研究方向為復雜網絡與網絡演算.