基于博弈理論的無線自組織網增強協作模型研究

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

基于博弈理論的無線自組織網增強協作模型研究

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

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

無線自組織網；自私性；增強協作；博弈；虛擬貨幣

1 引言

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

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

2 博弈論模型

2.1 收益分析

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

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

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

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

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

假設該過程中源節點為該轉發節點i支付的報酬為

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

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

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

中等值效用

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

轉發節點實際收益的方差為

轉發節點中等值效用為

其中 （1/2）rβ2σ為轉發節點風險成本。

假設數據包從源節點傳送到目的節點的過程中有n個轉發節點，對于源節點s其獲得的收益為

數據包傳輸過程中源節點s所需支付的虛擬貨幣總量的期望為

源節點的凈收益的期望為

2.2模型建立

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

（2）服務質量約束：根據不同業務的要求，數據轉發路徑中的節點需要提供滿足一定質量要求的服務，假設源節點對轉發節點努力程度要求為 A0，路徑時延要求為 T0，則

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

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

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

綜合以上分析，無線自組織網絡中數據包傳送的最優激勵模型如式（20）所示。

圖1 機會消耗圖

圖2 機會消耗等高線圖

圖3 機會消耗約束下節點可行狀態區間

3 模型求解與分析

在源節點傳送數據包的過程中，假設轉發路徑中共有n各個節點，對于傳輸路徑中任選的某個轉發節點i，設定：

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

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

對式（23）求導并令其導數為零，即

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

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

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

轉發節點i的期望產出為

轉發節點i的期望收益為

源節點s的期望收益為

源節點s的期望支出為

轉發節點i的確定性等值效用為

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

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

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

4 結束語

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

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

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

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

圖6 節點固定性收入與其 風險偏好程度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］ 汪洋， 林闖， 李學林， 等. 基于非合作博弈的無線網絡路由機制研究［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網絡合作轉發模型［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］ 黃開枝， 洪穎， 羅文宇. 基于演化博弈機制的物理層安全協作方法［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］ 蔣小杰， 芮蘭蘭， 郭少勇， 等. 一種基于信譽的移動自組網區分服務激勵機制［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年生，博士生，研究方向為無線自組織網絡網絡協議及通信網理論.

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

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

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；網絡出版：2015-11-01

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

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