李添澤武穆清李沛哲廖文星馬 偉（北京郵電大學信息與通信工程學院 北京 100876）（網(wǎng)絡與體系架構與融合北京市重點實驗室 北京 100876）（中國科學院信息工程研究所 北京 100093）

基于博弈理論的無線自組織網(wǎng)增強協(xié)作模型研究

李添澤①②武穆清①②李沛哲①②廖文星①②馬 偉*③
①（北京郵電大學信息與通信工程學院 北京 100876）②（網(wǎng)絡與體系架構與融合北京市重點實驗室 北京 100876）③（中國科學院信息工程研究所 北京 100093）

為了解決無線自組織網(wǎng)絡中轉發(fā)節(jié)點因自身能量與存儲空間限制而拒絕協(xié)作的自私性問題，該文從分析數(shù)據(jù)包源節(jié)點與轉發(fā)節(jié)點的收益與開銷特性出發(fā)，基于虛擬貨幣的獎勵機制，結合博弈理論提出無線自組織網(wǎng)絡增強協(xié)作模型。該模型將網(wǎng)絡協(xié)作問題轉化為數(shù)據(jù)包轉發(fā)路徑中多轉發(fā)節(jié)點與源節(jié)點收益的博弈均衡問題，在保障雙方利益的基礎上提出最優(yōu)的激勵方式，促進通信協(xié)作的進行。另外，為最大化網(wǎng)絡生存時間與避免擁塞，該模型對轉發(fā)節(jié)點的電量與存儲空間狀態(tài)做了相應的約束。

無線自組織網(wǎng)；自私性；增強協(xié)作；博弈；虛擬貨幣

1 引言

無線自組織網(wǎng)絡是一種采用無線通信方式、動態(tài)組網(wǎng)的移動性對等網(wǎng)絡，具有快速部署、動態(tài)組網(wǎng)、高抗毀性等優(yōu)點，在軍事通信、抗震救災、工業(yè)控制等方面具有廣闊的應用前景。無線自組織網(wǎng)絡的各種網(wǎng)絡協(xié)議都是以各節(jié)點積極參與通信協(xié)作為前提的，然而在實際應用中由于網(wǎng)絡節(jié)點能量限制、內(nèi)存限制或其他資源的限制等因素而拒絕協(xié)作的現(xiàn)象大有存在，如果網(wǎng)絡中有 10%～40%的節(jié)點不參與協(xié)作，那么網(wǎng)絡的平均吞吐量將降低16%～40%［1，2］。因此加強節(jié)點間的協(xié)作一直是無線自組織網(wǎng)絡中研究的熱點，目前主要有基于懲罰的機制和基于博弈的激勵機制兩種方法［3］。前者的基本思想是通過觀察和監(jiān)控節(jié)點的合作行為并對不合作的節(jié)點進行懲罰，從而保證所有節(jié)點都能積極合作。Watchdog方法［1］，CONFIDANT算法［4］，CORE機制［5］和Pathrater機制［6］均屬于此類方法?；诓┺牡募顧C制主要是應用博弈論的相關知識，增強節(jié)點之間的合作轉發(fā)。隨著博弈論被應用于無線網(wǎng)絡［711］-該方案得到了廣泛的關注。Ad hoc VCG［12］是通過激勵中間節(jié)點給出它們轉發(fā)所需的真實成本，從而實現(xiàn)轉發(fā)策略。文獻［13］提出錢包與改進的購買方式，文獻［14］提出Sprite方案，即建立可信的結算中心來計算各個節(jié)點發(fā)送數(shù)據(jù)包時留下的收據(jù)。文獻［15］將經(jīng)濟學上的委托代理引入無線自組織網(wǎng)絡，提出了基于虛擬貨幣的激勵模型。文獻［16～19］分析了博弈理論對增強節(jié)點協(xié)作的作用，文獻［20］研究了基于演化博弈機制的物理層安全協(xié)作方法，文獻［21～24］研究了基于聲譽的增強節(jié)點協(xié)作的作用，文獻［25，26］研究了競價理論在促進節(jié)點協(xié)作中的應用。

本文結合博弈論的相關理論與虛擬貨幣的機制，建立基于節(jié)點收益最大化的增強合作模型。首先分析了在數(shù)據(jù)包轉發(fā)過程中源節(jié)點與轉發(fā)節(jié)點的收益情況，轉發(fā)節(jié)點消耗自身資源為源節(jié)點提供滿足一定性能要求的數(shù)據(jù)轉發(fā)服務，同時獲得源節(jié)點支付的虛擬貨幣，源節(jié)點獲得服務并支付相應的虛擬貨幣。該模型對轉發(fā)節(jié)點剩余能量、剩余存儲空間做了合理約束以最大化網(wǎng)絡生存時間并減少擁塞的發(fā)生，轉發(fā)節(jié)點的服務能力因素以保證源節(jié)點對服務質(zhì)量的需求。

2 博弈論模型

2.1 收益分析

本模型基于虛擬貨幣機制，源節(jié)點發(fā)送數(shù)據(jù)時需要向轉發(fā)節(jié)點支付一定量的虛擬貨幣作為報酬。假設節(jié)點具有趨利性，對事件做出反應前會對收益與付出的代價進行權衡。數(shù)據(jù)發(fā)送過程中，源節(jié)點的收益是數(shù)據(jù)得以傳送，代價是為轉發(fā)節(jié)點提供一定的虛擬貨幣。轉發(fā)節(jié)點的收益是轉發(fā)數(shù)據(jù)獲得的虛擬貨幣，代價是消耗自身能量與存儲空間。目的節(jié)點是信息的接收方，其只需要接收到達的信息即可，不需要為信息接收支付貨幣，在本模型中不對目的節(jié)點進行討論。

為了定量分析轉發(fā)節(jié)點的自私特性，本文提出努力程度的概念，其反映節(jié)點對轉發(fā)數(shù)據(jù)的積極程度。假設轉發(fā)節(jié)點的努力程度主要影響其所能提供的帶寬與轉發(fā)效率等因素，而轉發(fā)時延等因素與節(jié)點努力程度無關。數(shù)據(jù)在傳送的過程中，一般要經(jīng)過多次轉發(fā)才能成功到達目的節(jié)點，對于轉發(fā)路徑中的某個節(jié)點i，假設其轉發(fā)時延為 ti，節(jié)點其努力程度為 ai，其產(chǎn)出函數(shù)為

f（ai，ti）表示轉發(fā)節(jié)點i在努力程度 ai轉發(fā)時延為 ti時帶來的產(chǎn)出；θi～ N（0，σ）表示由不確定性因素帶來的產(chǎn)出。

在數(shù)據(jù)包轉發(fā)路徑中，轉發(fā)節(jié)點i的電量狀態(tài)用ei表示，已用存儲空間狀態(tài)用 mi表示，初始電量狀態(tài)用表示，初始存儲空間狀態(tài)用 m表示，則轉發(fā)節(jié)點i自身狀態(tài)可表示為 （ei， mi，e，m。節(jié)點i參與轉發(fā)行為時自身的消耗為

g（ai）表示節(jié)點i努力程度為 ai時所產(chǎn)生的消耗； h（ei，m）是節(jié)點的機會消耗。

假設該過程中源節(jié)點為該轉發(fā)節(jié)點i支付的報酬為

α為轉發(fā)節(jié)點的固定性收入，β為對轉發(fā)節(jié)點提供服務的激勵強度。在整個轉發(fā)的過程中轉發(fā)節(jié)點獲得的凈收益為

本模型中轉發(fā)節(jié)點的努力程度ia越高收益iG越大，同時付出的代價iS也越高，轉發(fā)節(jié)點的協(xié)作過程中有收益也有付出，其凈收益取決于收益與付出的大小，即該轉發(fā)過程有一定的風險。本模型利用節(jié)點的風險偏好情況來表示其參與協(xié)作的熱情。在轉發(fā)的過程中假設節(jié)點都是風險規(guī)避的，為了描述節(jié)點對風險的偏好程度，本模型引入效用函數(shù)的概念［13］，即

其中r為轉發(fā)節(jié)點的風險規(guī)避量，r ＞ 0，r =0，r ＜0分別代表節(jié)點是風險厭惡者，風險中性者與風險偏好者。x為轉發(fā)節(jié)點的實際收入，其服從均值為w，方差為 σ的正態(tài)分布，即 x ～N（w，σ）。

中等值效用

在本模型中 x= PGi= Gi- Si，則轉發(fā)節(jié)點實際收益的期望為

轉發(fā)節(jié)點實際收益的方差為

轉發(fā)節(jié)點中等值效用為

其中 （1/2）rβ2σ為轉發(fā)節(jié)點風險成本。

假設數(shù)據(jù)包從源節(jié)點傳送到目的節(jié)點的過程中有n個轉發(fā)節(jié)點，對于源節(jié)點s其獲得的收益為

數(shù)據(jù)包傳輸過程中源節(jié)點s所需支付的虛擬貨幣總量的期望為

源節(jié)點的凈收益的期望為

2.2模型建立

節(jié)點機會消耗隨剩余電量情況及存儲空間使用情況的變化如圖1所示，圖中為剩余電量占初始電量的比例，為已用存儲空間占初始存儲空間的比例，由圖可見剩余電量越少、已用存儲空間越大節(jié)點機會消耗便越大。節(jié)點機會消耗的等高線如圖2所示，規(guī)定，在實際中設定0=20h ，則轉發(fā)節(jié)點可行的狀態(tài)區(qū)間如圖 3所示，即節(jié)點i可作為轉發(fā)節(jié)點的條件為其狀態(tài)處在可行的狀態(tài)區(qū)間中。

（2）服務質(zhì)量約束：根據(jù)不同業(yè)務的要求，數(shù)據(jù)轉發(fā)路徑中的節(jié)點需要提供滿足一定質(zhì)量要求的服務，假設源節(jié)點對轉發(fā)節(jié)點努力程度要求為 A0，路徑時延要求為 T0，則

（3）轉發(fā)節(jié)點參與約束：為使節(jié)點i參與所設計的激勵機制，則節(jié)點i獲得效用的期望必須不小于其不參與該激勵機制的機會效用，即

（4）轉發(fā)節(jié)點激勵相容約束：該約束指節(jié)點i參與激勵機制的條件下，所選擇行動的效用不小于選擇其他行動的效用，即

（5）最大效用約束：發(fā)報方在滿足以上約束條件的可行機制中，選擇最大化自己效用的函數(shù)，即

綜合以上分析，無線自組織網(wǎng)絡中數(shù)據(jù)包傳送的最優(yōu)激勵模型如式（20）所示。

圖1 機會消耗圖

圖2 機會消耗等高線圖

圖3 機會消耗約束下節(jié)點可行狀態(tài)區(qū)間

3 模型求解與分析

在源節(jié)點傳送數(shù)據(jù)包的過程中，假設轉發(fā)路徑中共有n各個節(jié)點，對于傳輸路徑中任選的某個轉發(fā)節(jié)點i，設定：

努力程度為ia時的消耗設定為：

將式（14）、式（21）、式（22）代入式（20）可得：

對式（23）求導并令其導數(shù)為零，即

假設節(jié)點i為努力程度最小的節(jié)點，即 amin=min（a1，a2，…， an）=ai，對于節(jié)點 j（j ≠ i）有

當aj≥ ai時節(jié)點j的收益隨 aj的增大而減小，故 aj合理的取值為 aj= ai，有

將式（26）代入式（20）并求解，可得：

轉發(fā)節(jié)點i的期望產(chǎn)出為

轉發(fā)節(jié)點i的期望收益為

源節(jié)點s的期望收益為

源節(jié)點s的期望支出為

轉發(fā)節(jié)點i的確定性等值效用為

綜合考慮各指標的重要程度以及收支的平衡關系，模型中的各個變量設定為并假設路徑中有5個轉發(fā)節(jié)點，將以上數(shù)值代入式（20），求解便可得到最優(yōu)的激勵方式以及源節(jié)點與轉發(fā)節(jié)點的期望收益。圖4，圖5，圖 6分別為激勵強度β，節(jié)點努力程度a，轉發(fā)節(jié)點的固定性收入α隨節(jié)點對風險偏好程度r的變化關系。

由圖4可知，源節(jié)點的激勵強度β隨轉發(fā)節(jié)點對風險偏好程度的增強（r由大到小）而變大，由圖6可知固定支付貨幣量α隨轉發(fā)節(jié)點對風險偏好程度的增強而減弱，故對于風險愛好者可以減少固定支付而增大激勵強度。同時結合圖4，圖 5可知轉發(fā)節(jié)點努力程度與源節(jié)點激勵強度有相同的遞增趨勢。

表1為r取-0.2，-0.1，0，0.1，0.2等不同值時模型的應用結果。分析可知，源節(jié)點的激勵強度β隨轉發(fā)節(jié)點的不合作程度而依次上升，0.14→0.16→0.20→0.25→0.33，在此激勵條件下轉發(fā)節(jié)點的努力程度也隨之上升0.71→0.83→1.00→1.25→1.67，相應的轉發(fā)節(jié)點的期望收益減少了一半，31.22→14.44，這會使轉發(fā)節(jié)點從風險偏好者轉變?yōu)轱L險厭惡者，即在確保收益的情況下節(jié)點更積極地參與通信協(xié)作。

4 結束語

本文基于博弈理論提出了一種促進無線自組織網(wǎng)絡中自私節(jié)點參與通信協(xié)作的激勵模型，探討了在滿足源節(jié)點業(yè)務質(zhì)量需求的情況下如何以最小代價促使網(wǎng)絡中的節(jié)點參與協(xié)作。一方面源節(jié)點需要得到滿足業(yè)務質(zhì)量要求的服務，而其擁有的虛擬貨幣數(shù)量有限，不能支付過高的報酬，另一方面轉發(fā)節(jié)點能量、存儲空間、帶寬等資源有限，其提供服務的條件是獲得足夠的報酬。本模型基于博弈理論對數(shù)據(jù)傳輸過程中源節(jié)點與轉發(fā)節(jié)點的收益情況進行分析，綜合考慮兩者的凈收益情況提出最優(yōu)激勵方案。

本文首次提出基于數(shù)據(jù)傳輸全路徑多轉發(fā)節(jié)點的激勵模型，符合無線自組織網(wǎng)絡中數(shù)據(jù)包轉發(fā)的實際狀況。另外考慮轉發(fā)節(jié)點能量與存儲空間有限等特點，本模型設定了合理的約束機制，在一定程度上延長網(wǎng)絡壽命并避免網(wǎng)絡擁塞的發(fā)生。

圖4 節(jié)點激勵強度與風險偏好程度的關系

圖5 節(jié)點努力程度與 風險偏好程度的關系

圖6 節(jié)點固定性收入與其 風險偏好程度r的關系

表1 模型應用結果

［1］ Marti S and Giuli T J. Mitigating routing misbehavior in mobile Ad hoc networks［C］. MibiCOM 2000， USA， Boston，2000: 255-265.

［2］ Michiardi P and Molva R. Simulation-based analysis of security exposures in mobile Ad hoc networks［C］. Proceedings of European Wireless Conference， Firenze， Italy，2002: 275-281.

［3］ Malnar M Z and Neskovic N J. An analysis of performances of multi-channel routing protocol based on different link quality metrics［C］. International Conference on Telecommunications in Modern Satellite， Cable and Broadcasting Services， Nis，Serbia， 2011: 737-740.

［4］ Buchegger S and Boudec J Y L. Performance analysis of the Confidant protocol: cooperation of nodes-fairness in dynamic Ad-hoc networks［C］. MobiHOC， Lausanne， Switzerland， 2002: 226-236.

［5］ Michiardi P and Molva R. A collaborative reputation mechanism to enforce node cooperation in mobile ad hoc networks［C］. Conference on Communications and MultimediaSecurity， Portoroz， 2002: 107-121.

［6］ 汪洋， 林闖， 李學林， 等. 基于非合作博弈的無線網(wǎng)絡路由機制研究［J］. 計算機學報， 2009， 32（1）: 54-68. Wang Yang， Lin Chuang， Li Xue-lin， et al.. Non-cooperation game based research on routing schemes for wireless networks［J］. Chinese Journal of Computers， 2009， 32（1）: 54-68.

［7］ Akkarajitsakul K. Game theoretic approaches for multiple access in wireless networks: a survey［J］. IEEE Communications Surveys and Tutorials， 2012， 13（3）: 372-395.［8］ Brown D R and Fazel F. A game theoretic study of energy efficient cooperative wireless networks［J］. Journal of Communications and Networks， 2011， 13（3）: 266-276.

［9］ Alizadeh Y， Sabaei M， and Tavallaie O. Game theoretic modeling of joint topology control and forwarding in MANET based on local information［C］. Computational Intelligence and Communication Networks （CICN）， Mathura， India， 2013: 510-515.

［10］ Sarkar S and Datta R. A game theoretic model for stochastic routing in self-organized MANETs［C］. Wireless Communications and Networking Conference （WCNC），Shanghai， China， 2013: 1962-1967.

［11］ Rong C. Cooperative game based relay vehicle selection algorithm for VANETs［C］. Communications and Information Technologies （ISCIT）， Seoul， Korea， 2014: 30-34.

［12］ Anderegg L and Eidenbenz S. Ad hoc-VCG: a truthful and cost-efficient routing protocol for mobile ad hoc networks with selfish agents［C］. International Conference on Mobile Computing and Networking， California， USA， 2003: 245-259.

［13］ Buttyan L and Hubaux J P. Enforcing service availability in mobile Ad hoc WANs［C］. MobiHOC， Boston， USA， 2000: 87-96.

［14］ Zhong S， Chen J， and Yang Y R. Sprite: a simple cheat proof credit-base system for mobile ad hoc networks［C］. INFOCOM，San Francisco， USA， 2003: 1987-1997.

［15］ 鄭慧芳， 蔣挺， 周正. MANET增強合作模型的理論研究［J］.北京郵電大學學報， 2008， 31（10）: 21-24. Zheng Hui-fang， Jiang Ting， and Zhou Zheng. Theoretical study with the model for MANET cooperation enforcement［J］. Journal of Beijing University of Posts and Telecommunications， 2008， 31（10）: 21-14.

［16］ Akkarajitsakul K， Hossain E， and Niyato D. Coalition-based cooperative packet delivery under uncertainty: a dynamic Bayesian coalitional game［J］. IEEE Transactions on Mobile Computing， 2013， 12（2）: 371-385.

［17］ Li Z and Shen H. Game-theoretic analysis of cooperation incentive strategies in mobile Ad hoc networks［J］. IEEE Transactions on Mobile Computing， 2012， 11（8）: 1287-1303.

［18］ Naserian M and Tepe K. Dynamic probabilistic forwarding in wireless Ad hoc networks based on game theory［C］. Vehicular Technology Conference （VTC Spring）， Seoul， Korea， 2014: 1-5.

［19］ 張華鵬， 張宏斌. 基于重復博弈的Ad hoc網(wǎng)絡合作轉發(fā)模型［J］. 電子與信息學報， 2014， 36（3）: 703-707. Zhang Hua-peng and Zhang Hong-bin. Cooperative forwarding model based on repeated game in Ad hoc networks［J］. Jourenal of Electronics & Information Technology， 2014， 36（3）: 703-707.

［20］ 黃開枝， 洪穎， 羅文宇. 基于演化博弈機制的物理層安全協(xié)作方法［J］. 電子與信息學報， 2015， 37（1）: 193-197. Huang Kai-zhi， Hong Ying， and Luo Wen-yu. A method for physical layer security cooperation based on evolutionary game［J］. Journal of Electronics & Information Technology，2015， 37（1）: 193-197.

［21］ Tang Chang-bing， Li Ang， and Li Xiang. When reputation enforces evolutionary cooperation in unreliable MANETs［J］. IEEE Transactions on Cybernetics， 2014， PP（99）: 1-1.

［22］ Safaei Z， Sabaei M， and Torgheh F. An efficient reputation-based mechanism to enforce cooperation in MANETs［C］. Application of Information and Communication Technologies， Venice， Italy， 2009: 1-6.

［23］ Sengathir J， Manoharan R， and Kumar R. Markovian process based reputation mechanisms for detecting selfish nodes in MANETs: A survey［C］. Advanced Computing （ICoAC），Madras， India， 2013: 217-222.

［24］ 蔣小杰， 芮蘭蘭， 郭少勇， 等. 一種基于信譽的移動自組網(wǎng)區(qū)分服務激勵機制［J］. 電子與信息學報， 2012， 29（7）: 1299-1303. Jiang Xiao-jie， Rui Lan-lan， Guo Shao-yong， et al.. A Reputation-based service differentiated incentive mechanism for MANETs［J］. Journal of Electronics & Information Technology， 2012， 29（7）: 1299-1303.

［25］ Liu L， Guo Y， and Yin L. Analyzing asking/bidding price in dynamic game for cooperative authentication［C］. Computer Communications Workshops （INFOCOM WKSHPS），Toronto， Canada， 2014: 165-166.

［26］ Liu Li-cai， Yin Li-hua， Guo Yun-chuan， et al.. Bargaining-based dynamic decision for cooperative authentication in MANETs［C］. Trust， Security and Privacy in Computing and Communications （TrustCom）， Beijing，China， 2014: 212-220.

李添澤： 男，1987年生，博士生，研究方向為無線自組織網(wǎng)絡網(wǎng)絡協(xié)議及通信網(wǎng)理論.

武穆清： 男，1964年生，教授，博士生導師，研究方向為寬帶網(wǎng)絡理論與信息處理.

李沛哲： 男，1990年生，博士生，研究方向為電網(wǎng)通信技術.

Ad hoc Network Cooperation Enforcement Model Based on Game Theory

Li Tian-ze①②Wu Mu-qing①②Li Pei-zhe①②Liao Wen-xing①②Ma Wei③
①（School of Information and Communication Engineering， Beijing University of Posts and Telecommunications， Beijing 100876， China）②（Beijing Key Laboratory of Network System Architecture and Convergence， Beijing 100876， China）③（Institute of Information Engineering， Chinese Academy of Sciences， Beijing 100093， China）

In order to solve the selfishness problem that forwarding nodes in the wireless ad hoc network refuse to cooperation due to the limit of energy and storage space， a wireless ad hoc network cooperation enhancement model combined with the game theory is proposed， which is based on the incentive mechanism of virtual currency，analysis the benefit and overhead characteristics of the source nodes and forwarding nodes. In this model， the network cooperation problem is transformed into a game equilibrium problem about the benefit of source node and forwarding nodes in the data forwarding path， promoting the cooperation of communication. Furthermore， in order to avoid the congestion and maximizing network lifetime， the model makes some certain constraint about the energy and storage space for the forwarding nodes.

Ad hoc network； Selfishness； Cooperation enforcement； Game theory； Virtual currency

The Director Funds of Laboratory of Network System Architecture and Convergence （2015BKL-NSAC-ZJ-06）

TP393.08

A

1009-5896（2015）12-2802-06

10.11999/JEIT150356

2015-03-25；改回日期：2015-08-28；網(wǎng)絡出版：2015-11-01

*通信作者：馬偉mawei@iie.ac.cn

網(wǎng)絡體系架構與融合北京市重點實驗室主任基金（2015BKL-NSAC-ZJ-06）