基于重復博弈的Ad hoc網絡合作轉發模型

張華鵬 張宏斌

(蘇州大學計算機科學與技術學院 蘇州 215006)

1 引言

Ad hoc網絡是一種無需基礎設施支持的自組織網絡，網絡的功能通過節點間合作實現。在實際的網絡中，由于節點存在自私性使得它們為了保存能量而不愿參加與己無關的數據轉發活動。經研究發現，節點的自私行為不僅嚴重降低網絡整體性能，而且威脅網絡安全[1]。因此，在一些領域的Ad hoc網絡應用中，設計促進網絡中節點合作的策略機制變得十分關鍵。

Ad hoc網絡中的合作激勵機制分為兩類：基于信用的機制和基于信譽的機制。基于信用的機制[26]-將經濟學中的激勵手段應用到 Ad hoc網絡中，但該類機制需要使用防更改硬件或第3方信任機構，這影響了該類機制的推廣應用。在基于信譽的機制中[1,713]-，節點觀察其它節點的行為，并根據信譽推斷網絡中的自私節點。

對于基于信譽的機制，可以使用博弈模型分析節點間的交互并給出相應的均衡策略[7,8,14,15]。文獻[7]運用合作博弈模型對節點間交互進行建模，但節點在選擇策略時需進行復雜的信息交換，消耗的能量較多。針對該問題，文獻[8]采用非合作博弈模型分析節點間的交互。非合作博弈模型不僅不需要節點間交換信息，而且能夠很好地反應Ad hoc網絡節點的困境：是為了增加自身的信譽值選擇合作還是為了節省能量選擇不合作。文獻[8]使用完美信息重復博弈模型分析節點間的交互，并給出滿足子博弈完美均衡的策略組合。然而在Ad hoc網絡中，由于無線信道容易受到干擾等特點，大多數情況下節點掌握的信息是不完美信息。針對該問題，文獻[15]采用不完美信息重復博弈模型分析節點間的交互，并給出對應的序貫均衡策略。但該文獻使用簡單的觸發機制構造序貫均衡策略，當觀測誤差較大時，網絡的合作率較低。

本文在文獻[15]的基礎上，給出了不完美信息下另一種滿足序貫均衡的策略組合。與文獻[15]中的機制相比，本文使用貝爾曼方程構造策略，避免使用對觀測誤差非常敏感的觸發機制，提高了不完美信息環境下網絡的合作率。

2 不完美信息重復博弈

2.1 博弈模型

假定Ad hoc網絡中的節點可以使用watchdog[1]等機制觀察其它節點的行為。由于無線信道的特點，節點的觀察存在誤差，故節點掌握的信息是不完美信息。將一段時間內網絡中任意一對節點之間的交互看作一輪兩人靜態博弈 G。因此可以使用不完美信息重復博弈模型(,,)GΓδ λ分析Ad hoc網絡中任意一對節點間的交互，其中δ為貼現因子，說明了該對節點繼續博弈的概率，λ為觀測誤差。

對于重復博弈Γ，博弈雙方為網絡中的任意一對節點，記為i和j。在單輪博弈G中，博弈雙方同時從行為空間A={F,D}選擇行為，F為轉發對方數據包，D為丟棄對方數據包；并觀察對方的行為，f為觀察到對方的轉發行為，d為觀察到對方的丟包行為，令Ω={f, d}。由watchdog等機制的原理可知：對于對方的轉發行為F，博弈者依概率1-λ觀察到f，依概率λ觀察到d；對于對方的丟包行為D，博弈者僅能觀察到d。博弈者的轉發行為F消耗節點資源，對方轉發自身數據包時節點會獲得利益，假定數據包的價值大于轉發行為的成本，歸一化后的收益矩陣如圖1所示。圖中。假定表示在第t輪博弈中節點i的收益，那么節點i在重復博弈Γ中的收益為

圖1 博弈G中的收益矩陣

2.2 序貫均衡

對于不完美信息重復博弈，序貫均衡[16]不僅滿足一致性，而且滿足序貫理性，即對于博弈雙方的信念以及所有可能到達的信息集[17]，每個博弈方的策略都是針對其他博弈方策略的最佳對策。因此滿足序貫均衡的激勵機制比滿足納什均衡的機制有更好的穩定性和適用性。

定義 1 稱s=(si,sj)為無顯著偏離(no observable deviation[18])的策略組合。若對于每一個博弈者i，其任何一個沒有到達的信息集可以且僅可以通過博弈者i本身偏離策略si到達。

定理 1 對于不完美信息無限次重復博弈Γ，若納什均衡策略 s為無顯著偏離的策略組合，且 s在博弈Γ中沒有到達的信息集上也構成納什均衡策略，那么s是博弈Γ的序貫均衡策略。證明見文獻[18]。

2.3 已有模型分析

文獻[15]使用不完美信息重復博弈分析節點間交互，并提出滿足序貫均衡的策略機制。文獻[15]在構造策略時使用兩種連續策略：觸發策略Fσ和背叛策略Dσ。

觸發機制對觀察誤差比較敏感，若節點的觀察結果在t輪之前不全為f，那么在t輪之后的博弈中始終選擇背叛行為 D。因此，在觀察誤差較大的環境中，該類機制的合作率較低。本文采用基于貝爾曼方程的序貫均衡策略所采取方法并不是“觸發機制”而是針對背叛策略，采取一定程度忍耐方式，從而抵消文獻[15]中由于觀測誤差導致合作率不高的結果出現。第5節進一步分析該類機制，并通過仿真比較兩種序貫均衡策略的性能。

3 序貫均衡策略

3.1 構造策略

圖2 節點策略構造流程圖

圖2描述節點策略的構造。初始化階段，節點根據網絡確定收益矩陣中的參數g, l，初始化參數t,k, t=0, k=0，并計算出數列。在第t輪博弈中，節點首先確定自身的行為：以概率mk選擇合作行為F；以概率1-mk選擇不合作行為D。在每一輪博弈結束時，節點觀察對方的行為：若觀察到對方選擇合作行為(即)，將觀察到對方連續不合作次數歸零(k = 0)；若觀察到對方選擇不合作行為(即)，則k = k +1。構造策略s的關鍵是如何確定，使得對方在任何博弈點選擇F行為和D行為獲得的總收益相等。

節點策略構造算法如表1所示。

表1 節點策略構造算法

在首輪博弈中(t = 0, k = 0)，節點“友好”地選擇轉發行為；節點觀察到對方的轉發行為時，同樣選擇轉發行為。根據對方選擇轉發行為F和丟包行為D時(對方)所得收益，可得貝爾曼方程：

解該方程得

更一般的情況，當節點連續k (k ＆gt; 0)次觀察到對方的丟包行為時，根據對方選擇轉發行為和丟包行為時(對方)所得收益，可得貝爾曼方程：

解該方程可得

3.2 策略分析

由s可知，在首輪博弈中，節點j選擇轉發行為F，因此i可以通過偏離si到達所有信息集。假定在第t(t ＆gt; 0)輪博弈中，節點j選擇轉發行為的概率是mk。若mk= 0，那么節點i可以通過在第t -1輪博弈中選擇F行為使得mk＆gt; 0，因此在第t輪博弈中i可以通過偏離策略 si到達所有的信息集。綜上所述，節點i可以通過偏離策略si到達任何信息集。j與i采用相同策略，因此j也可以通過偏離sj到達任何信息集，s無顯著偏離。 證畢

證明 對于策略s*，任何一個節點i(j)單獨偏離策略其總收益不會增加，因此*s是博弈Γ的納什均衡策略。因為在博弈的任何階段，任意一個博弈者i(j)偏離策略其總收益不會增加，因此*s在沒有到達的信息集上也是納什均衡策略。由引理1及定理1可知，*s是無限次重復博弈Γ的序貫均衡策略。

證畢

圖3是mk隨k的變化趨勢，參數l = 3, g = 2,δ=0.99, λ=0.03。從圖3中可以看出，隨著連續觀察到對方丟包次數的增加(k的增加)，節點選擇轉發行為的概率(mk)逐漸降低，最終趨于穩定值 m。從式(8)可以看出，博弈者i的對手收益也是隨著自身丟包行為次數增加而減少。博弈者 i也以較低的概率m選擇轉發行為F。由于博弈對稱特性，博弈者i丟包行為次數將隨之增加，也會導致博弈者i的收益減少。最后雙方將會在一個較低的轉發行為概率值mk=m范圍內達到平衡。但不會出現mk=0的情形。若對方始終選擇丟包行為，博弈者 i以較低的概率m選擇轉發行為F，降低了節點的損失。若對方為正常節點，由于信息的不完美性導致節點(連續)觀察到丟包行為，博弈者i以較大概率mk試圖與對方恢復合作，提高了網絡的合作率。

4 仿真

圖3 mk 與 k 的關系

在仿真中，本文給出基于貝爾曼方程的序貫均衡策略，與文獻[15]中的序貫均衡策略進行比較。對于文獻[15]中的模型，為了獲得更好的收益，文獻[15]將重復博弈Γ分割為N個重復博弈NGΓ。

從合作率、平均收益和對不同網絡環境的適應性3個方面考察兩種序貫均衡策略的性能。仿真模擬了 4種類型的策略，S*為本文給出的序貫均衡策略；S'為文獻[15]中的策略；Sc為合作策略，節點始終選擇轉發行為F; Sd為背叛策略，節點始終選擇丟包行為D。

圖4為分別使用策略S*和S'時，網絡的合作率、平均收益隨觀察誤差的變化曲線。實驗參數為：g =2,l = 2, δ=0.99。對于策略S'，作者使用簡單的觸發機制構造該策略，觸發機制對觀察誤差非常敏感。因此，隨著觀察誤差的增加，網絡的合作率、節點的平均收益迅速降低。對于策略S*，當觀察出現誤差時，節點以一定的概率恢復合作，提高了網絡的合作率和節點的平均收益。仿真結果表明，網絡采用策略S*時，合作率、平均收益與觀察誤差呈現出近似的線性關系。隨著觀察誤差的增加，合作率、平均收益沒有顯著下降。

圖5反映了在不同的網絡環境中，使用策略S*,S'和Sc時節點的平均收益。實驗參數為：g = 2, l =2, δ= 0.99, λ= 0.03。對于策略Sc，節點始終選擇轉發行為 F，隨著網絡中自私節點比例的增加，節點的收益快速下降。策略S*在面對自私節點時，以概率m選擇轉發行為F，一定程度上減少了損失。策略S'使用了觸發機制，如果觀察到自私節點的丟包行為 d，那么節點在之后的博弈中始終選擇不合作行為D。因此策略S'收到的影響最低。

5 結論

一種有效的合作激勵機制可以防止節點自私行為的發生。本文應用不完美信息重復博弈模型分析Ad hoc網絡中節點的交互，使用貝爾曼方程構造滿足序貫均衡的合作激勵機制。與已有的序貫均衡相比，本文給出的序貫均衡策略避免使用觸發機制，提高在不完美信息環境下的性能。仿真結果表明，本文給出的序貫均衡策略不僅提高了網絡的合作率和節點的平均收益，而且提高了機制的適應性。

圖4 合作率和平均收益與參數λ的關系

圖5 節點的平均收益隨自私節點所占比例的變化

[1] Marti S, Giuli T J, Lai K, et al.. Mitigating routing misbehavior in mobile ad hoc networks[C]. Proceedings of the Sixth Annual International Conference on Mobile Computing and Networking (MobiCom’00), Boston, MA, 2000: 255-265.[2] Mahmoud M M E A and Shen X. FESCIM: fair, efficient, and secure cooperation incentive mechanism for multihop cellular networks[J]. IEEE Transactions on Mobile Computing, 2012,11(5): 753-766.

[3] Zhong S, Chen J, and Yang Y R. Sprite: a simple, cheat-proof,credit based system for mobile ad-hoc networks[C].Proceedings of the IEEE INFOCOM,03, San Francisco, CA,2003: 1987-1997.

[4] Cutillo L A, Molva R, and ?nen M. PRICE: privacy preserving incentives for cooperation enforcement[C]. World of Wireless, Mobile and Multimedia Networks (WoWMoM),San Francisco, California, USA, 2012: 1-9.

[5] Kaushik R and Singhai J. Modspirite: a credit based solution to enforce node cooperation in an ad-hoc network[J].International Journal of Computer Science Issues, 2011,8(2/3): 295-302.

[6] Mahmoud M E and Shen X M. Credit-based mechanism protecting multi-hop wireless networks from rational and irrational packet drop[C]. Global Telecommunications Conference, Waterloo, Canada, 2010: 1-5.

[7] Saad W, Han Z, Debbah M, et al.. A distributed coalition formation framework for fair user cooperation in wireless networks[J]. IEEE Transactions on Wireless Communications,2009, 8(9): 4580-4593.

[8] Milan F, Jaramillo J J, and Srikant R. Achieving cooperation in multihop wireless networks of selfish nodes[C]. Workshop on Game Theory for Networks (GameNets 2006), Pisa, Italy,2006: 3-3

[9] Michiardi P and Molva R. Core: a collaborative reputation mechanism to enforce node cooperation in mobile ad hoc networks[C]. Proceedings of the Communications and Multimedia Security Conference (CMS’02), Portoroz,Slovenia, 2002: 107-121.

[10] Buchegger S and Le Boundec J Y. Performance analysis of the CONFIDANT protocol (cooperation of nodes: fairness in dynamic ad-hoc networks)[C]. Proceedings of the International Symposium on Mobile Ad Hoc Networking ＆amp;Computing (MobiHoc‘02), Lausanne, Switzerland, 2002:226-236.

[11] 許智君, 胡琪, 張玉軍, 等. MANET 網絡激勵節點協作的信任評估路由協議[J]. 通信學報, 2012, 33(7): 27-35.

[12] Charilas D E, Georgilakis K D, and Panagopoulos A D.ICARUS: hybrid incentive mechanism for cooperation stimulation in ad hoc networks[J]. Ad Hoc Networks, 2012,10(6): 976-989.

[13] Yu K and Chen X B. Analysis of reputation-based incentive mechanisms in Ad hoc networks[C]. Internet Conference on Software Engineering and Service Science (ICSESS). Beijing,China, 2012: 333-336.

[14] Jaramillo J J and Srikant R. A game theory based reputation mechanism to incentivize cooperation in wireless Ad hoc networks[J]. Ad Hoc Networks, 2010, 8: 416-429.

[15] Ji Z, Yu W, and Liu K J R. A belief evaluation framework in autonomous MANETs under noisy and imperfect observation:vulnerability analysis and cooperation enforcement[J]. IEEE Transactions on Mobile Computing, 2010, 9(9): 1242-1254.

[16] Kreps D M and Wilson R. Sequential equilibria[J].Econometrica: Journal of the Econometric Society, 1982,50(4): 863-894.

[17] Osborne M J. A course in game theory[M]. Cambridge, Mass.:MIT Press, 1994: 1-353.

[18] Kandori M and Matsushima H. Private observation,communication and collusion[J]. Econometrica, 1998, 66(3):627-652.