劉 浩，陳志剛，張連明

1.湖南人文科技學(xué)院 信息學(xué)院，湖南 婁底 417000

2.中南大學(xué) 信息科學(xué)與工程學(xué)院，長沙 410083

3.湖南師范大學(xué) 物理與信息科學(xué)學(xué)院，長沙 410081

移動對等網(wǎng)絡(luò)中討價還價動態(tài)博弈的激勵策略*

劉 浩1+，陳志剛2，張連明3

1.湖南人文科技學(xué)院 信息學(xué)院，湖南 婁底 417000

2.中南大學(xué) 信息科學(xué)與工程學(xué)院，長沙 410083

3.湖南師范大學(xué) 物理與信息科學(xué)學(xué)院，長沙 410081

摘要內(nèi)容由于移動對等網(wǎng)絡(luò)的自組織、開放性以及節(jié)點資源受限等特點，一些節(jié)點表現(xiàn)出其自私性或惡意性。針對該問題，給出了一種基于討價還價動態(tài)博弈的節(jié)點激勵策略DGBIS（incentive strategy based on dynamic game of bargaining in mobile P2P network）。該激勵策略采用虛擬貨幣的支付方式，節(jié)點先根據(jù)其擁有的虛擬貨幣量、自身資源狀態(tài)和消息屬性對每次消息轉(zhuǎn)發(fā)進(jìn)行估價，然后交易雙方基于估價通過三次討價還價動態(tài)博弈以合理的報價進(jìn)行交易。通過博弈分析給出了DGBIS策略的納什均衡解，使理性的自私節(jié)點為最大化其自身利益而積極參與消息轉(zhuǎn)發(fā)合作，同時能抑制惡意節(jié)點的虛假報價。分析與實驗結(jié)果表明，該激勵策略能提高整個系統(tǒng)的消息轉(zhuǎn)發(fā)成功率，降低系統(tǒng)的能量消耗，達(dá)到了預(yù)期的設(shè)計目標(biāo)。

移動對等網(wǎng)絡(luò)；自私性；惡意性；討價還價；虛擬貨幣；動態(tài)博弈；激勵策略

1 引言

近年來，隨著無線通信技術(shù)的快速發(fā)展和移動用戶資源共享、協(xié)同工作需求的日益增長，移動對等（peer-to-peer，P2P）網(wǎng)絡(luò)得到了廣泛應(yīng)用。目前，移動對等網(wǎng)絡(luò)已成為網(wǎng)絡(luò)通信產(chǎn)業(yè)界與學(xué)術(shù)界普遍關(guān)注的重點領(lǐng)域之一[1]。一方面，由于移動對等網(wǎng)絡(luò)的自組織與開放性等特點，其用戶節(jié)點逐年大幅增加；另一方面，由于資源受限等原因部分移動節(jié)點表現(xiàn)出自私性與惡意性[2]。相關(guān)研究[2-5]表明，在Gnutella等網(wǎng)絡(luò)系統(tǒng)中，存在著2/3以上的freerider節(jié)點，這些自私節(jié)點只消費網(wǎng)絡(luò)系統(tǒng)中的資源而不愿意共享自身資源。并且移動對等網(wǎng)絡(luò)中存在著大量不可信的服務(wù)和欺詐行為[2]。顯然，這與對等網(wǎng)絡(luò)實現(xiàn)的基本理念“人人為我，我為人人”是相違背的[2]。移動用戶節(jié)點的自私行為與惡意行為嚴(yán)重影響了移動對等網(wǎng)絡(luò)服務(wù)的可用性，降低了網(wǎng)絡(luò)系統(tǒng)的整體效用。因此，在移動網(wǎng)絡(luò)中，研究與設(shè)計有效的節(jié)點激勵策略，約束節(jié)點的自私行為與惡意行為，激勵節(jié)點間的相互合作，對提高網(wǎng)絡(luò)系統(tǒng)的可用性和整體效用具有重要的意義[2-3]。

當(dāng)前，對等網(wǎng)絡(luò)中常見的節(jié)點激勵策略主要有兩類：區(qū)分服務(wù)與虛擬支付[3,6]。

區(qū)分服務(wù)類型激勵策略的基本思想是，給予積極參與資源共享和協(xié)同合作的節(jié)點更高級別的服務(wù)（如享受優(yōu)先服務(wù)等）。針對P2P網(wǎng)絡(luò)中節(jié)點的搭便車行為，樂光學(xué)等人在P2P可信流媒體網(wǎng)絡(luò)環(huán)境下給出了一種以節(jié)點的貢獻(xiàn)度、信譽(yù)度及其收益為評價指標(biāo)的抑制機(jī)制[6]。針對P2P文件共享系統(tǒng)中用戶節(jié)點的搭便車行為，若僅僅使用獎勵等區(qū)分服務(wù)激勵策略是不夠的，文獻(xiàn)[7]對相應(yīng)激勵策略的公平性進(jìn)行了評估與改進(jìn)。為了抑制P2P多媒體共享網(wǎng)絡(luò)中節(jié)點的自私行為，崔光海等人給出了一種基于演化博弈論的P2P多媒體共享網(wǎng)絡(luò)自組織激勵策略，激勵節(jié)點為最大化自己的收益而積極參與多媒體共享合作[8]?；谥貜?fù)博弈相關(guān)理論，文獻(xiàn)[9]在P2P網(wǎng)絡(luò)中建立了對自私節(jié)點的懲罰機(jī)制，并通過制定相關(guān)的行為規(guī)則，激勵理性節(jié)點為使其自身收益最大化而向網(wǎng)絡(luò)系統(tǒng)貢獻(xiàn)相關(guān)資源?；赟tackelberg博弈方法，文獻(xiàn)[10]給出了一個基于信用的異構(gòu)對等網(wǎng)絡(luò)中節(jié)點的激勵策略，該策略通過偏袒的資源配置機(jī)制，根據(jù)節(jié)點的不同信用值為其提供不同的服務(wù)，以激勵節(jié)點間的相互合作。盡管基于區(qū)分服務(wù)思想的激勵策略容易實現(xiàn)，然而在該類型激勵策略作用下，網(wǎng)絡(luò)系統(tǒng)的整體效用與每個節(jié)點的自身利益很難同時達(dá)到最優(yōu)，因此理性的自私節(jié)點仍然存在違背協(xié)議的動機(jī)[3,6]；同時，若評價機(jī)制不夠完善，節(jié)點間還可能存在共謀等惡意行為。

基于虛擬支付激勵策略的基本思想是，節(jié)點采用虛擬貨幣來支付所獲得的各種網(wǎng)絡(luò)服務(wù)，當(dāng)為其他節(jié)點提供各種網(wǎng)絡(luò)服務(wù)時則能夠獲得以虛擬貨幣形式的報酬[11]?；谔摂M支付的激勵策略在機(jī)會網(wǎng)絡(luò)、無線網(wǎng)絡(luò)、P2P網(wǎng)絡(luò)等領(lǐng)域應(yīng)用廣泛，尤其是與博弈論相結(jié)合，將成熟的博弈論思想應(yīng)用于虛擬支付的激勵策略中，能夠有效地解決網(wǎng)絡(luò)系統(tǒng)中節(jié)點的自私性問題，提高系統(tǒng)的整體效用。趙廣松等人針對節(jié)點在自私性機(jī)會網(wǎng)絡(luò)中內(nèi)容分發(fā)方面的自私行為，提出了一種網(wǎng)絡(luò)服務(wù)商A類節(jié)點與B類節(jié)點可以達(dá)到共贏互惠的激勵策略，基于虛擬支付的方式，使每個節(jié)點在試圖最大化自己收益的同時，達(dá)到提高整個機(jī)會網(wǎng)絡(luò)中內(nèi)容分發(fā)性能的目標(biāo)[12]?；谔摂M支付和演化博弈理論，文獻(xiàn)[13]提出了一種自組織網(wǎng)絡(luò)中節(jié)點間的協(xié)同合作激勵策略。文獻(xiàn)[14]針對機(jī)會網(wǎng)絡(luò)中邊緣注入和邊緣隱藏攻擊等問題，提出了一種MobiCent機(jī)制，該機(jī)制使用倍減算法來計算報酬，能激勵網(wǎng)絡(luò)系統(tǒng)中節(jié)點間的相互合作。為提高移動對等網(wǎng)絡(luò)數(shù)據(jù)的可用性，文獻(xiàn)[3]提出了一種基于經(jīng)濟(jì)激勵的經(jīng)紀(jì)方案，激勵中繼節(jié)點作為路由和消息轉(zhuǎn)發(fā)的經(jīng)紀(jì)人，以提高對等網(wǎng)絡(luò)的路由與消息轉(zhuǎn)發(fā)效率。為了約束移動P2P網(wǎng)絡(luò)中節(jié)點“搭便車”的行為，提高網(wǎng)絡(luò)的搜索效率，基于資源拍賣文獻(xiàn)[15]給出了一種節(jié)點激勵策略，系統(tǒng)通過拍賣經(jīng)濟(jì)模式激勵節(jié)點為獲得收益而貢獻(xiàn)相應(yīng)的資源，該激勵策略能夠有效地提高系統(tǒng)的整體效用，達(dá)到優(yōu)化系統(tǒng)性能的目標(biāo)。針對機(jī)會網(wǎng)絡(luò)中節(jié)點的自私性問題，并結(jié)合機(jī)會網(wǎng)絡(luò)中節(jié)點資源受限等特點，李云等人提出了一種基于買賣模型的節(jié)點消息轉(zhuǎn)發(fā)激勵策略，有效地解決了節(jié)點盲目合作帶來的網(wǎng)絡(luò)性能退化問題[16]。

這些激勵策略大多數(shù)是通過各種規(guī)則、策略來激勵自私節(jié)點進(jìn)行合作，并沒有考慮節(jié)點自身資源受限等因素對節(jié)點行為的影響，因此不適用于節(jié)點資源受限的移動對等網(wǎng)絡(luò)。同時，它們在追求系統(tǒng)整體效用最優(yōu)時，既沒有充分考慮理性節(jié)點的自私性，即最大化其自身收益，也沒有考慮惡意節(jié)點虛假報價的影響。

為了描述方便，本文的分析場景為移動對等網(wǎng)絡(luò)中節(jié)點間的消息轉(zhuǎn)發(fā)合作過程。由于移動對等網(wǎng)絡(luò)中節(jié)點的資源是有限的，假如其節(jié)點激勵策略不考慮資源的使用情況，就會造成節(jié)點因能源耗盡而直接退出網(wǎng)絡(luò)，從而導(dǎo)致整個網(wǎng)絡(luò)系統(tǒng)性能退化，造成更大的損失。因此，綜合考慮移動網(wǎng)絡(luò)中節(jié)點的自身狀態(tài)和消息屬性等因素，給出了一種基于討價還價動態(tài)博弈的節(jié)點激勵策略DGBIS（incentive strategy based on dynamic game of bargaining in mobile P2P network），同時該激勵策略將充分考慮節(jié)點自私性與惡意性的影響。

2 網(wǎng)絡(luò)概述

移動對等網(wǎng)絡(luò)本質(zhì)上是各種移動終端以自組織的方式疊加在網(wǎng)絡(luò)層之上的分布式覆蓋網(wǎng)絡(luò)，通過利用移動終端的空閑資源進(jìn)行協(xié)同工作與資源共享[1]。比如，移動自組網(wǎng)上的覆蓋網(wǎng)絡(luò)就屬于移動對等網(wǎng)絡(luò)。顯然，這些移動節(jié)點所擁有的能量、緩存等資源都是有限的，并且能量是不可再生的。一方面，移動節(jié)點加入網(wǎng)絡(luò)系統(tǒng)，是以資源共享與協(xié)同工作為目的，這就會消耗其自身的資源。另一方面，移動節(jié)點為了保證較長時間的正常工作，就會盡可能地節(jié)約其所擁有的資源，那么就會表現(xiàn)出其自私性或惡意性。

2.1 基本假設(shè)

本文先給出一些在網(wǎng)絡(luò)模型方面的基本假設(shè)。

（1）節(jié)點間消息轉(zhuǎn)發(fā)被抽象為兩人交易模型，沒有第三方參與，消息轉(zhuǎn)發(fā)服務(wù)節(jié)點為賣方，賣出消息轉(zhuǎn)發(fā)服務(wù)，消息轉(zhuǎn)發(fā)請求節(jié)點為買方，購買相應(yīng)的服務(wù)。

（2）假設(shè)相鄰節(jié)點之間可通過監(jiān)控機(jī)制知曉對方的狀態(tài)信息，也就是說鄰居節(jié)點之間的狀態(tài)信息是透明的。

（3）由于鄰居節(jié)點之間的狀態(tài)信息是透明的，可以認(rèn)為所有節(jié)點都會根據(jù)自身狀態(tài)和消息屬性真實地對每次消息轉(zhuǎn)發(fā)交易進(jìn)行估價。

（4）在估價的基礎(chǔ)上，買賣雙方輪番出價，由于移動節(jié)點資源受限，本文采用三次討價還價交易模型，即必須在3輪之后終止，雙方必須接受第三次出價。

（5）每個移動節(jié)點的能量都不能得到補(bǔ)充，并在運行過程中知曉其能量狀態(tài)，當(dāng)能量耗盡時會自動退出網(wǎng)絡(luò)。

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

2.2 設(shè)計目標(biāo)

本文所設(shè)計的激勵策略要達(dá)到以下3個目標(biāo)：

（1）有效性。設(shè)計的激勵策略將通過虛擬支付的交易模式來激勵理性的自私節(jié)點為最大化其自身利益而積極參與消息轉(zhuǎn)發(fā)合作，以提高系統(tǒng)的消息轉(zhuǎn)發(fā)成功率。

（2）實用性。由于移動節(jié)點的資源受限，設(shè)計的激勵策略要能降低系統(tǒng)的能量消耗，能有效地提高網(wǎng)絡(luò)系統(tǒng)的整體效用。

（3）公平性。該激勵策略通過三次討價還價交易模型給出一個相對合理的交易價格，以抑制惡意節(jié)點的虛假報價。

3 基于討價還價動態(tài)博弈的節(jié)點激勵策略

討價還價是有共同利益的相關(guān)方面臨沖突時試圖達(dá)成一致協(xié)議的一種博弈過程，它是一種典型的談判活動；利益相關(guān)雙方通過對方的報價來判斷對方意圖，并給予再報價等反應(yīng)，使交易朝著己方有利又能讓對方接受的方向發(fā)展，最終達(dá)成利益分配的一致協(xié)議[17]。本文將節(jié)點間消息轉(zhuǎn)發(fā)過程抽象為一種雙方交易模型，提出了一種基于討價還價動態(tài)博弈的節(jié)點激勵策略DGBIS，它是一種基于虛擬貨幣支付的激勵策略。與目前相關(guān)研究不同的是，DGBIS策略綜合考慮了移動節(jié)點的自身狀態(tài)與消息屬性等因素對節(jié)點估價的影響；同時，該策略將充分考慮節(jié)點自私性與惡意性的影響。DGBIS策略不需要信任第三方來管理交易過程，每個移動節(jié)點各自管理自身的虛擬貨幣、緩存、能量等資源，每次消息轉(zhuǎn)發(fā)交易完成后，消息轉(zhuǎn)發(fā)請求節(jié)點支付給消息轉(zhuǎn)發(fā)服務(wù)節(jié)點一定的虛擬貨幣作為報酬。因此，DGBIS策略適用于移動對等網(wǎng)絡(luò)這樣的完全分布式系統(tǒng)。

3.1 博弈方與交易規(guī)則

在此，消息轉(zhuǎn)發(fā)動態(tài)博弈包括兩個博弈方：賣方即消息轉(zhuǎn)發(fā)服務(wù)節(jié)點j，買方即消息轉(zhuǎn)發(fā)請求節(jié)點i。每次消息轉(zhuǎn)發(fā)交易必須滿足以下規(guī)則：

（1）每次交易開始時，買賣雙方各自根據(jù)下面的估價函數(shù)對本次消息轉(zhuǎn)發(fā)交易進(jìn)行估價。設(shè)賣方對本次消息轉(zhuǎn)發(fā)交易的（成本）估價為cs，買方對本次消息轉(zhuǎn)發(fā)交易的（價值）估價為cb。

（2）若cb?cs，則本次交易失敗。

（3）若cb≥cs，則將Π=cb-cs作為一個雙方在本次交易中的共同受益，以供賣方節(jié)點j與買方節(jié)點i進(jìn)行利益分割。

（4）若經(jīng)過3次討價還價博弈后最終定價為cs+pbest，則賣方的收益為pbest，買方的收益為Π-pbest。

3.2 基本定義

在移動對等網(wǎng)絡(luò)中，影響節(jié)點進(jìn)行消息轉(zhuǎn)發(fā)合作意愿的因素較多。在此，DGBIS策略主要考慮節(jié)點的能量、緩存與虛擬貨幣量以及所需轉(zhuǎn)發(fā)消息的屬性等一些重要的因素。

定義1設(shè)Ei為節(jié)點i的剩余能量百分比，可表示為：

其中，Et_i表示節(jié)點i當(dāng)前t時刻的剩余能量值；Emax_i表示節(jié)點i的初始能量值。節(jié)點i的剩余能量百分比越大，此時節(jié)點i合作的意愿越強(qiáng)烈，越愿意參與消息轉(zhuǎn)發(fā)。

定義2設(shè)Hi為節(jié)點i的剩余緩存百分比，可表示為：

其中，Ht_i表示節(jié)點i當(dāng)前t時刻的剩余緩存值；Hmax_i表示節(jié)點i的最大緩存值。節(jié)點i的剩余緩存百分比越大，說明節(jié)點i存儲消息的能力越大。

定義3設(shè)節(jié)點的初始虛擬貨幣量為V0。

定義4設(shè)節(jié)點i當(dāng)前t時刻的虛擬貨幣量為Vi(t)。

節(jié)點i當(dāng)前t時刻的財富（虛擬貨幣）狀態(tài)可表示為：

（1）富裕狀態(tài)，Vi(t)≥αV0；

（2）一般狀態(tài)，αV0?Vi(t)?βV0；

（3）貧困狀態(tài)，Vi(t)≤βV0。

其中，α、β為系統(tǒng)自設(shè)參數(shù)，且有α?β?0。

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

定義5設(shè)消息M的大小為Ms，并約定Ms∈[0,1]。

定義6設(shè)消息M的剩余生存時間為Tres。

定義7設(shè)Murg為消息M需要轉(zhuǎn)發(fā)的緊急程度，當(dāng)Tres≥Tmin時，可表示為：

其中，TTTL為消息M的生存周期時間長度；Tmin為一次消息轉(zhuǎn)發(fā)所需要的最小時間。當(dāng)Tres?Tmin時，該消息應(yīng)該被丟棄，不再進(jìn)行轉(zhuǎn)發(fā)。

3.3 估價函數(shù)

3.3.1 買方估價函數(shù)

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

其中，Hi為買方i的剩余緩存百分比；Murg為消息需要轉(zhuǎn)發(fā)的緊急程度；ε和ω為兩者的權(quán)重值，表示買方節(jié)點i對緩存空間與消息轉(zhuǎn)發(fā)緊急程度的偏好，且有ε+ω=1；Ms為本次需要轉(zhuǎn)發(fā)的消息大小。

Wb和買方i的財富（虛擬貨幣）狀態(tài)相關(guān)，可表示為：

3.3.2 賣方估價函數(shù)

作為賣方，消息轉(zhuǎn)發(fā)服務(wù)節(jié)點j在對本次消息轉(zhuǎn)發(fā)（成本）進(jìn)行估價時，主要考慮自身的狀態(tài)與消息屬性。作為理性節(jié)點，如果賣方j(luò)的剩余能量百分比越小，則為了節(jié)省能量資源，它對本次消息轉(zhuǎn)發(fā)的估價會越高；若賣方j(luò)的剩余緩存百分比越小，它提供消息轉(zhuǎn)發(fā)服務(wù)的要價也會越高。與買方不同的是，若賣方j(luò)越貧窮，即其擁有的虛擬貨幣量越小，則它進(jìn)行本次消息轉(zhuǎn)發(fā)交易的意愿更為強(qiáng)烈。因此，賣方的估價函數(shù)可以表示為：

其中，Ms與式（4）的含義相同；Ej、Hi分別為賣方j(luò)的剩余能量百分比與剩余緩存百分比；λ和η為兩個權(quán)重值，且有λ+η=1。Ws和賣方j(luò)的財富（虛擬貨幣）狀態(tài)相關(guān)，可表示為：

由于節(jié)點剩余緩存的變化是可逆的，而能量是隨時間嚴(yán)格遞減的，并且只要兩者之一變小，賣方提供消息轉(zhuǎn)發(fā)服務(wù)的要價就會越高，因此可采用自適應(yīng)加權(quán)。當(dāng)剩余帶寬百分比小于剩余能量百分比時，前者對賣方估價的影響更大，反之亦然。則有：

3.4 博弈策略與收益

在討價還價動態(tài)博弈模型中，交易的物品（服務(wù)）是有時間價值的，即每次討價還價之后，雙方的共同收益都會有一個衰減，也稱貼現(xiàn)率σ，0≤σ≤1。三次討價還價博弈的具體過程如下：

（1）第一輪，賣方節(jié)點j出價cs+p1，則賣方節(jié)點j的收益為p1，買方節(jié)點i的收益為Π-p1；若買方節(jié)點i接受這一報價，那么雙方進(jìn)行消息轉(zhuǎn)發(fā)交易，否則進(jìn)入下一輪。

（2）第二輪，即買方節(jié)點i出價cs+p2，則賣方節(jié)點j的收益為σp2，買方節(jié)點i的收益為σ(Π-p2)；若賣方節(jié)點j接受這一報價，那么雙方進(jìn)行消息轉(zhuǎn)發(fā)交易，否則進(jìn)入下一輪。

（3）第三輪，賣方節(jié)點j進(jìn)行第三輪報價cs+pe，買方節(jié)點i必須接受，則賣方節(jié)點j的收益為σ2pe，買方節(jié)點i的收益為σ2(Π-pe)，交易完成。

三次討價還價動態(tài)博弈過程中，買賣雙方的收益如表1所示。

Table1 Dynamic game of tri-stages bargaining表1 三次討價還價動態(tài)博弈過程

3.5 博弈均衡分析

在三次討價還價動態(tài)博弈中，下面兩點是博弈雙方的公共知識：

（1）在第三輪中，賣方節(jié)點j提出的報價，買方節(jié)點i必須接受。

（2）隨著時間的推移，雙方的共同收益會有所衰減。

[17-18]，采用逆向歸納法來進(jìn)行博弈均衡分析。

（1）在第三輪，買方節(jié)點i必須接受賣方節(jié)點j提出的報價cs+pe，此時買方節(jié)點i的收益為σ2(Π-pe)，賣方節(jié)點j的收益為σ2pe。因此，賣方節(jié)點j一定會報價cs+pe=cb，那么賣方節(jié)點j獲得全部收益，買方節(jié)點i的收益為0。

（2）在第二輪中，買方節(jié)點i知曉一旦博弈進(jìn)行到第三輪，賣方節(jié)點j一定會報價cs+pe=cb。事實上，因為共同收益的衰減，雙方都不愿意進(jìn)入第三輪報價，所以只要買方節(jié)點i在第二輪的報價使得賣方節(jié)點j的收益不小于其第三輪的收益，賣方節(jié)點j將接受買方節(jié)點i的報價。那么博弈也不會進(jìn)行到第三輪。因此，應(yīng)有下不等式成立：

由式（10）可知，p2取最小值為 σpe。

那么，賣方節(jié)點j的收益為σ2pe，其收益與第三輪完全相同。買方節(jié)點i的收益為σ(Π-σpe)，其收益大于第三輪的收益。

因此，當(dāng)p2=σpe時，交易在第二輪完成。

（3）在第一輪中，賣方節(jié)點j知曉自己在第二輪和第三輪的收益為σ2pe，并能推斷買方節(jié)點i在第二輪的報價為p2=σpe。由于收益衰減的原因，從共同收益角度考慮，最佳的成交方案應(yīng)該是在第一輪。為了達(dá)到這一目標(biāo)，賣方節(jié)點j在第一輪的報價必須使得買方節(jié)點i的收益不小于其第二輪的收益，即下面不等式成立：

由式（11）可知，p1取最大值為 Π-σ(Π-σpe)。

那么，賣方節(jié)點j的收益為 Π-σ(Π-σpe)，其收益大于第二輪與第三輪的收益σ2pe。買方節(jié)點i的收益為σ(Π-σpe)，其收益與第二輪收益相同。

因此，當(dāng)p1=Π-σ(Π-σpe)時，交易在第一輪完成。

綜上所述，該動態(tài)博弈的子博弈納什均衡解是：賣方節(jié)點j給出報價cs+p1，其中p1=Π-σ(Π-σpe)。同時，賣方節(jié)點j的收益為Π-σ(Π-σpe)，買方節(jié)點i的收益為 σ(Π-σpe)。

在最后一輪，買方節(jié)點i必須接受賣方節(jié)點j的報價，因此賣方節(jié)點j一定會選擇報價cs+pe=cb，即pe=cb-cs=Π。那么，子博弈的納什均衡解為：

顯然，pbest由1-σ+σ2決定，且有0?(1-σ+σ2)?1，即pbest?Π，雙方都達(dá)到收益的最大化，交易成功。

4 消息轉(zhuǎn)發(fā)過程

若消息轉(zhuǎn)發(fā)請求節(jié)點i預(yù)測其某一鄰居節(jié)點j更可能與消息M的目的節(jié)點相遇或者更可能將消息M轉(zhuǎn)發(fā)到其目的節(jié)點，則向節(jié)點j發(fā)起消息轉(zhuǎn)發(fā)服務(wù)請求。消息轉(zhuǎn)發(fā)的具體過程如圖1所示。

具體描述如下：

（1）服務(wù)請求。若節(jié)點i向節(jié)點j發(fā)起對消息M的轉(zhuǎn)發(fā)服務(wù)請求，則請求信息包括消息M的ID（身份識別碼）、買方估價cb與大小Ms、目的節(jié)點。

（2）請求響應(yīng)。節(jié)點j收到節(jié)點i發(fā)來消息轉(zhuǎn)發(fā)服務(wù)請求信息后，若節(jié)點j愿意接受本次消息轉(zhuǎn)發(fā)，則根據(jù)式（6）計算出估價cs。然后，反饋給節(jié)點i一條請求響應(yīng)信息，該請求響應(yīng)信息包含賣方節(jié)點j估價cs。

（3）若cb?cs，則本次交易失敗。否則，根據(jù)3.5節(jié)的博弈分析，得出使博弈雙方（節(jié)點i與節(jié)點j）利益最大化的最終報價cs+pbest。

（4）消息轉(zhuǎn)發(fā)交易。若cb≥cs，交易的最終價格為cs+pbest。賣方節(jié)點j向買方節(jié)點i提供消息M的轉(zhuǎn)發(fā)服務(wù)，本次交易成功。

（5）更新。消息轉(zhuǎn)發(fā)交易完成后，節(jié)點i扣除cs+pbest單位的虛擬貨幣，同時節(jié)點j增加cs+pbest單位的虛擬貨幣。

Fig.1 Procedure of message forwarding圖1 消息轉(zhuǎn)發(fā)過程

5 仿真實驗與結(jié)果分析

為了評價激勵策略DGBIS的網(wǎng)絡(luò)性能，本文采用NS2作為系統(tǒng)模擬軟件來實現(xiàn)網(wǎng)絡(luò)模型中的相關(guān)機(jī)制與協(xié)議，其中以按需路由協(xié)議AODV（Ad hoc on-demand distance vector routing）作為仿真實驗中的路由協(xié)議，仿真實驗由離散事件（消息轉(zhuǎn)發(fā)）進(jìn)行驅(qū)動。先對NS2中的節(jié)點、鏈路、代理以及包等基本功能模塊進(jìn)行初始化。網(wǎng)絡(luò)中的路由配置通過對節(jié)點附加路由協(xié)議AODV來實現(xiàn)。在節(jié)點上，通過配置不同的代理（發(fā)送代理與接收代理）以實現(xiàn)相應(yīng)的協(xié)議，并接收一些實驗用的通信量等數(shù)據(jù)。通過NS2仿真系統(tǒng)中的Trace文件來保存整個模擬過程，并對Trace文件中的相關(guān)數(shù)據(jù)進(jìn)行統(tǒng)計分析。

實驗場景參數(shù)設(shè)置：500個移動節(jié)點（無線終端）隨機(jī)分布在4 000m×3 000m的區(qū)域內(nèi)，每個節(jié)點使用IEEE802.11無線網(wǎng)絡(luò)接口，節(jié)點移動速度為0～20m/s，節(jié)點通信半徑為100m，移動方式遵循Random Waypoint移動模型。每個節(jié)點的初始能量為1 000 J，發(fā)射功率為1 W，緩存空間初始值為30 MB，并假設(shè)節(jié)點只有在消息轉(zhuǎn)發(fā)時才會消耗能量，其中每次消息轉(zhuǎn)發(fā)請求與響應(yīng)以及討價還價博弈等過程消耗能量1 J,消息傳輸?shù)哪芰肯呐c消息大小成正比，即1 MB的消息傳輸消耗2 J能量。模擬時間為4h，其中最初的5min為熱身時間，網(wǎng)絡(luò)系統(tǒng)每分鐘隨機(jī)地產(chǎn)生500個大小服從[0.5,1.0]MB均勻分布的消息。設(shè)α=2/3，β=1/3，ε=ω=0.5，V0=6，TTTL=30s，σ=0.85。

為了檢驗所設(shè)計激勵策略DGBIS的有效性、公平性與實用性，假設(shè)網(wǎng)絡(luò)系統(tǒng)可能存在3類節(jié)點：

（1）合作節(jié)點（cooperative node），該類節(jié)點會無條件地幫助其鄰居節(jié)點轉(zhuǎn)發(fā)消息。

（2）理性的自私節(jié)點（rational selfish node），該類節(jié)點會真實地對每次消息轉(zhuǎn)發(fā)進(jìn)行估價，在利益驅(qū)使下才會積極參與消息轉(zhuǎn)發(fā)，并且會盡可能地最大化其自身利益。

（3）惡意節(jié)點（malicious node），該類節(jié)點會對每次消息轉(zhuǎn)發(fā)進(jìn)行真實的估價，即買方節(jié)點會按式（4）進(jìn)行真實估價，賣方會按式（6）進(jìn)行真實估價。但是可能會虛擬報價，即不會按3.5節(jié)進(jìn)行真實的報價。

為了準(zhǔn)確地分析相關(guān)網(wǎng)絡(luò)性能，本文使用包投遞率和平均剩余能量作為網(wǎng)絡(luò)性能的評價指標(biāo)。包投遞率（即消息轉(zhuǎn)發(fā)的平均成功率）是指目的節(jié)點正確接收到的數(shù)據(jù)包個數(shù)與源節(jié)點發(fā)送的數(shù)據(jù)包個數(shù)之比值。平均剩余能量是指成功轉(zhuǎn)發(fā)相同數(shù)量的消息時，所有節(jié)點的平均剩余能量，它是消息轉(zhuǎn)發(fā)過程中能量消耗的評價指標(biāo)。為了驗證所設(shè)計的激勵策略DGBIS在3個設(shè)計目標(biāo)（有效性、公平性與實用性）上的達(dá)成度，進(jìn)行了3個實驗。

實驗1檢驗DGBIS策略的有效性，即能否有效地激勵理性的自私節(jié)點積極參與消息轉(zhuǎn)發(fā)合作。將文獻(xiàn)[16]給出的基于買賣模型節(jié)點激勵策略簡稱為BIP，文獻(xiàn)[19]給出的節(jié)點激勵策略簡稱為RF20。分別在網(wǎng)絡(luò)系統(tǒng)中采用DGBIS策略、BIP策略、RF20策略和不采用任何激勵策略Nature狀態(tài)的4種情況下，假設(shè)系統(tǒng)中只有合作節(jié)點與理性的自私節(jié)點兩類節(jié)點，當(dāng)系統(tǒng)中自私節(jié)點的比例增大時，考察整個網(wǎng)絡(luò)系統(tǒng)中消息轉(zhuǎn)發(fā)的平均成功率，其實驗結(jié)果如圖2所示。

Fig.2 Varying of average success rate of message forwarding with proportion of selfish nodes圖2 消息轉(zhuǎn)發(fā)成功率隨自私節(jié)點比例的變化圖

從圖2可知，當(dāng)網(wǎng)絡(luò)系統(tǒng)中自私節(jié)點的比例增大時，在不采用任何激勵策略的Nature狀態(tài)下，系統(tǒng)的消息轉(zhuǎn)發(fā)平均成功率快速下降，極端情況網(wǎng)絡(luò)系統(tǒng)性能嚴(yán)重退化，成功率在12％左右；采用BIP激勵策略和RF20策略，系統(tǒng)的消息轉(zhuǎn)發(fā)平均成功率緩慢下降；采用DGBIS激勵策略，系統(tǒng)的消息轉(zhuǎn)發(fā)平均成功率基本保持不變。原因是在不采用任何激勵策略的Nature狀態(tài)下，理性的自私節(jié)點不會參與消息轉(zhuǎn)發(fā)合作，這就會降低消息轉(zhuǎn)發(fā)的成功率。并且DGBIS激勵策略比BIP和RF20策略更能夠有效提高系統(tǒng)的消息轉(zhuǎn)發(fā)成功率。

實驗2檢驗DGBIS策略的公平性，即能否抑制惡意節(jié)點虛假報價對系統(tǒng)性能的影響。在網(wǎng)絡(luò)系統(tǒng)中分別采用DGBIS策略、BIP策略、RF20策略和不采用任何激勵策略Nature狀態(tài)的4種情況下，假設(shè)系統(tǒng)中只有合作節(jié)點與惡意節(jié)點兩類節(jié)點，當(dāng)系統(tǒng)中惡意節(jié)點的比例增大時，考察整個網(wǎng)絡(luò)系統(tǒng)中消息轉(zhuǎn)發(fā)的平均成功率，其實驗結(jié)果如圖3所示。

Fig.3 Varying of average success rate of message forwarding with proportion of malicious nodes圖3 消息轉(zhuǎn)發(fā)成功率隨惡意節(jié)點比例的變化圖

從圖3可知，當(dāng)系統(tǒng)中惡意節(jié)點的比例增大時，在Nature狀態(tài)下，采用RF20策略和BIP激勵策略，系統(tǒng)的消息轉(zhuǎn)發(fā)平均成功率都快速下降，極端情況下系統(tǒng)性能嚴(yán)重退化；采用DGBIS激勵策略，系統(tǒng)的消息轉(zhuǎn)發(fā)平均成功率緩慢下降。原因是在Nature狀態(tài)下采用RF20策略和BIP激勵策略，都不能有效地抑制惡意節(jié)點的虛假報價，導(dǎo)致了許多消息轉(zhuǎn)發(fā)交易失敗，這會降低消息轉(zhuǎn)發(fā)的成功率。然而，在DGBIS激勵策略中，通過討價還價交易模型來抑制惡意節(jié)點的虛假報價，因此降低了惡意節(jié)點對消息轉(zhuǎn)發(fā)合作的影響。

實驗3檢驗DGBIS策略的實用性，即能否降低系統(tǒng)的能量消耗，提高系統(tǒng)的整體效用。不失一般性，不妨設(shè)合作節(jié)點在網(wǎng)絡(luò)系統(tǒng)所占比重為40％，自私節(jié)點所占比重為30％，惡意節(jié)點所占比重為30％。在網(wǎng)絡(luò)系統(tǒng)中分別采用DGBIS策略、BIP策略、RF20策略和不采用任何激勵策略Nature狀態(tài)的4種情況下，當(dāng)系統(tǒng)中消息轉(zhuǎn)發(fā)成功的次數(shù)增加時，考察所有節(jié)點的平均剩余能量，其實驗結(jié)果如圖4所示。

Fig.4 Comparison of average residual energy in 4 kinds of situations圖4 4種情況下平均剩余能量的比較圖

從圖4中可以看出，當(dāng)系統(tǒng)中消息轉(zhuǎn)發(fā)成功的次數(shù)增加時，在不采用任何激勵策略的Nature狀態(tài)下，系統(tǒng)中所有節(jié)點的平均剩余能量減少得最快；采用BIP激勵策略和RF20策略，系統(tǒng)中所有節(jié)點的平均剩余能量減少得較快；采用DGBIS激勵策略，則平均剩余能量減少得最慢。原因是不采用任何激勵策略，由于節(jié)點的自私性與惡意性，會導(dǎo)致許多消息轉(zhuǎn)發(fā)合作交易的失敗，那么在達(dá)到相同消息成功轉(zhuǎn)發(fā)的次數(shù)時，會增大消息轉(zhuǎn)發(fā)請求與響應(yīng)以及討價還價博弈等過程的次數(shù)，從而加大了能量消耗。同時，若系統(tǒng)采用BIP激勵策略和RF20策略，由于該策略不能抑制惡意節(jié)點的虛假報價，也會導(dǎo)致一些消息轉(zhuǎn)發(fā)合作交易的失敗，同理會加大系統(tǒng)的能量消耗。因此，可以認(rèn)為采用DGBIS激勵策略能降低系統(tǒng)的能量消耗，提高系統(tǒng)的整體效用。

綜上所述，DGBIS激勵策略達(dá)到了預(yù)期的設(shè)計目標(biāo)（有效性、公平性與實用性）。

6 結(jié)束語

通過借鑒討價還價動態(tài)博弈的基本原理，本文給出了一種移動對等網(wǎng)絡(luò)中節(jié)點間消息轉(zhuǎn)發(fā)的激勵策略DGBIS。該策略通過虛擬貨幣支付方式有效地激勵理性的自私節(jié)點進(jìn)行合作；通過討價還價交易模式來抑制惡意節(jié)點的虛假報價，給移動對等網(wǎng)絡(luò)中節(jié)點激勵策略等相關(guān)研究提供了一種新的研究思路。盡管DGBIS策略不失為一種有效的節(jié)點激勵策略，但是尚未考慮如何約束節(jié)點因自身的富裕性出現(xiàn)的偏好自私性等問題。因此，這些將是未來的研究重點之一。

References:

[1]Zhang Guoyin,Li Jun.Overlays in mobile P2P networks[J].Journal of Software,2013,24(1):139-152.

[2]Qu Dapeng,Wang Xingwei,Huang Min.Selfish node detection and incentive mechanism in mobile P2P networks[J].Journal of Software,2013,24(4):887-899.

[3]Padhariya N,MondalA,Madria S K,et al.Economic incentivebased brokerage schemes for improving data availability in mobile-P2P networks[J].Computer Communications,2013,36(2):861-874.

[4]Safiriyu E I,DaudaA.Anovel security protocol for P2Pincentive schemes[J].Journal of Multidisciplinary Engineering Science and Technology,2015,5(2):1046-1051.

[5]Feldman M,Papadimitriou C,Chuang J.Free-riding and whitewashing in peer-to-peer systems[J].IEEE Journal on SelectedAreas in Communications,2006,24(5):1010-1019.

[6]Yue Guangxue,Li Renfa,Chen Zhi,et al.Analysis of freeriding behaviors and modeling restrain mechanisms for peerto-peer networks[J].Journal of Computer Research and Development,2011,48(3):382-397.

[7]Li Yunzhao,Gruenbacher D,Scoglio C.Reward only is not enough:evaluating and improving the fairness policy of the P2P file sharing network eMule/eDonkey[J].Journal of Peerto-Peer Networking andApplications,2012,5(1):40-57.

[8]Cui Guanghai,Li Mingchu,Jin Xing,et al.Evolution of cooperation in P2P media sharing networks based on selforganized incentive[J].Journal of Chinese Computer Systems,2016,37(2):202-206.

[9]Chen Hongwei,Xu Hui,Chen Li.Incentive mechanisms for P2P network nodes based on repeated game[J].Journal of Networks,2012,7(2):385-392.

[10]Kang Xin,Wu Yongdong.Incentive mechanism design for heterogeneous peer-to-peer networks:a Stackelberg game approach[J].IEEE Transactions on Mobile Computing,2015,14(5):1018-1030.

[11]Tan Guang,Jarvis SA.Apayment-based incentive and service differentiation scheme for peer-to-peer streaming broadcast[J].IEEE Transactions on Parallel and Distributed Systems,2008,19(7):940-953.

[12]Zhao Guangsong,Chen Ming.Research of incentive-aware data dissemination in selfish opportunistic networks[J].Journal on Communications,2013,34(2):73-84.

[13]Yang Yanbing,Liu Bin,Shi Yan,et al.Design and simulation of the cooperation incentive mechanism in ad hoc network based on evolutionary game[J].ICIC Express Letters,2015,9(10):2827-2834.

[14]Cheng Gang,Song Mei,Zhang Yong,et al.Routing protocol based on social characteristics for opportunistic networks[J].The Journal of China Universities of Posts and Telecommunications,2014,21(1):67-73.

[15]Ding Hui,Pei Jinming.The research of resource auction incentive mechanism in mobile P2P[C]//Proceedings of the5th International Conference on Wireless Communications,Networking and Mobile Computing,Beijing,Sep 24-26,2009.Piscataway,USA:IEEE,2010:5520-5522.

[16]Li Yun,Yu Jihong,You Xiaohu.An incentive protocol for opportunistic networks with resources constraint[J].Chinese Journal of Computers,2013,35(5):947-956.

[17]Wang Kanliang,Wang Song.Dynamic game of asymmetry information bargaining with tri-stages bargaining as example[J].Systems Engineering,Theory&Practice,2010,30(9):1636-1642.

[18]Li Bangyi,Wang Yuyan.Game theory and information economics[M].Beijing:Science Press,2016.

[19]Huangfu Shenlong,Guo Bin,Yu Zhiwen,et al.Incentive mechanism for opportunistic social networks:the market model with intermediaries[J].Journal of Software,2014,25(S2):53-62.

附中文參考文獻(xiàn)：

[1]張國印,李軍.移動對等網(wǎng)絡(luò)覆蓋網(wǎng)[J].軟件學(xué)報,2013,24(1):139-152.

[2]曲大鵬,王興偉,黃敏.移動對等網(wǎng)絡(luò)中自私節(jié)點的檢測和激勵策略[J].軟件學(xué)報,2013,24(4):887-899.

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

[8]崔光海,李明楚,金星,等.基于自組織激勵的P2P多媒體共享網(wǎng)絡(luò)節(jié)點合作的演化[J].小型微型計算機(jī)系統(tǒng),2016,37(2):202-206.

[12]趙廣松,陳鳴.自私性機(jī)會網(wǎng)絡(luò)中激勵感知的內(nèi)容分發(fā)的研究[J].通信學(xué)報,2013,34(2):73-84.

[16]李云,于季弘,尤肖虎.資源受限的機(jī)會網(wǎng)絡(luò)節(jié)點激勵策略研究[J].計算機(jī)學(xué)報,2013,35(5):947-956.

[17]王刊良,王嵩.非對稱信息下討價還價的動態(tài)博弈:以三階段討價還價為例[J].系統(tǒng)工程理論與實踐,2010,30(9):1636-1642.

[18]李幫義,王玉燕.博弈論與信息經(jīng)濟(jì)學(xué)[M].北京:科學(xué)出版社,2016.

[19]皇甫深龍,郭斌,於志文,等.機(jī)會社交網(wǎng)絡(luò)下基于中介市場模型的激勵機(jī)制[J].軟件學(xué)報,2014,25(S2):53-62.

Incentive Strategy in Mobile P2PNetwork Based on Dynamic Game of Bargaining*

LIU Hao1+,CHEN Zhigang2,ZHANG Lianming3
1.Institute of Information,Hunan University of Humanities,Science and Technology,Loudi,Hunan 417000,China
2.School of Information Science and Engineering,Central South University,Changsha 410083,China
3.College of Physics and Information Science,Hunan Normal University,Changsha 410081,China
+Corresponding author:E-mail:lhkd0407@126.com

LIU Hao,CHEN Zhigang,ZHANG Lianming.Incentive strategy in mobile P2P network based on dynamic game of bargaining.Journal of Frontiers of Computer Science and Technology,2017,11(8)：1269-1278.

Owing to the self-organization and opening features of mobile P2P network and the resource-constraint of nodes in it,some nodes show their selfishness and malice.Aiming at this problem,this paper proposes a novel incentive strategy based on dynamic game of bargaining in mobile P2P network(DGBIS).The incentive strategy adopts virtual currency payment method.The node calculates the evaluation of a message forwarding based on the virtual currency,its resource state and the message property.Both sides of the transaction give the reasonable price according to the evaluation and based on the dynamic game of tri-stages bargaining.Through the game analysis,this paper gives the Nash equilibrium solution of DGBIS strategy,which encourages rational selfish node to cooperate with the message forwarding in order to maximize its own benefits,and holds back the deceptive price of the malicious nodes.Analysis and simulation show that this incentive mechanism is able to effectively improve the success rate of message forwarding,reduce the system's energy consumption in the whole network system,and reach the predetermined design target.

as born in 1977.He

the Ph.D.degree from South China University of Technology in 2010.Now he is an associate professor at Hunan University of Humanities,Science and Technology.His research interests include parallel computing and peer-to-peer network,etc. 劉浩（1977—），男，2010年于華南理工大學(xué)獲得博士學(xué)位，現(xiàn)為湖南人文科技學(xué)院副教授，主要研究領(lǐng)域為并行計算，對等網(wǎng)絡(luò)等。

CHEN Zhigang was born in 1964.He received the Ph.D.degree from Central South University in 1998.Now he is a professor and Ph.D.supervisor at Central South University.His research interests include computer network and distributed system,etc.陳志剛（1964—），男，1998年于中南大學(xué)獲得博士學(xué)位，現(xiàn)為中南大學(xué)教授、博士生導(dǎo)師，主要研究領(lǐng)域為計算機(jī)網(wǎng)絡(luò)，分布式系統(tǒng)等。

ZHANG Lianming was born in 1972.He received the Ph.D.degree from Central South University in 2009.Now he is a professor at Hunan Normal University.His research interests include complex network and network calculus,etc.張連明（1972—），男，2009年于中南大學(xué)獲得博士學(xué)位，現(xiàn)為湖南師范大學(xué)教授，主要研究領(lǐng)域為復(fù)雜網(wǎng)絡(luò)，網(wǎng)絡(luò)演算等。

A

：TP393

*The National Natural Science Foundation of China under Grant Nos.61572191,61571188(國家自然科學(xué)基金);the Natural Science Foundation of Hunan Province under Grant No.2017JJ2124(湖南省自然科學(xué)基金);the Key Construction Course of Computer Application Technology in Hunan Province(湖南省計算機(jī)應(yīng)用技術(shù)重點建設(shè)學(xué)科資助項目).

Received 2017-01,Accepted 2017-03.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2017-03-23,http://kns.cnki.net/kcms/detail/11.5602.TP.20170323.1322.004.html

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology 1673-9418/2017/11(08)-1269-10

10.3778/j.issn.1673-9418.1701040

E-mail:fcst@vip.163.com

http://www.ceaj.org

Tel:+86-10-89056056

Key words:mobile P2P network;selfishness;malice;bargaining;virtual currency;dynamic game;incentive strategy