譚冕，何世彪，宋波，朱國慶，張暉

（重慶通信學院，重慶400035）

基于重復博弈的Ad Hoc網(wǎng)絡(luò)節(jié)點轉(zhuǎn)發(fā)策略分析

譚冕，何世彪，宋波，朱國慶，張暉

（重慶通信學院，重慶400035）

在無線Ad Hoc網(wǎng)絡(luò)中，源節(jié)點和目的節(jié)點互相通信需要中繼節(jié)點的支持，但節(jié)點是理性的，所以可能會拒絕轉(zhuǎn)發(fā)請求。這里就節(jié)點之間存在的合作問題，對針鋒相對策略、冷酷策略、完全合作策略、寬恕的針鋒相對策略、嚴厲針鋒相對策略進行了納什均衡分析。理論分析可知，針鋒相對策略相對于其他策略更具優(yōu)勢，因為它的閾值較低。

無線Ad Hoc網(wǎng)絡(luò)；重復博弈；納什均衡；轉(zhuǎn)發(fā)策略

0 引言

具有無中心、自組織、動態(tài)、多跳等特點的無線Ad Hoc網(wǎng)絡(luò)，由于節(jié)點傳輸距離的有限性，無線Ad Hoc網(wǎng)絡(luò)需要節(jié)點間的合作才能確保數(shù)據(jù)包得到成功傳遞[1]。在很多情況下，理性的參與者受到自身存儲資源和能量資源等的限制，為了增加存活時間，將采取損害網(wǎng)絡(luò)性能的行為[2]。顯然，即便只存在一些自私節(jié)點的無線自組網(wǎng)的系統(tǒng)，也會極大地降低網(wǎng)絡(luò)的整體性能。

本文首先對系統(tǒng)模型進行了分析，具體包括網(wǎng)絡(luò)的基本假設(shè)、博弈模型假設(shè)，再對多種轉(zhuǎn)發(fā)策略的納什均衡和節(jié)點收益進行了分析，最后得到了滿足納什均衡的條件。

1 系統(tǒng)模型

1.1 網(wǎng)絡(luò)基本假設(shè)

本文建立的Ad Hoc網(wǎng)絡(luò)存在如下假設(shè)：

（1）網(wǎng)絡(luò)中存在n個具有理性的節(jié)點，網(wǎng)絡(luò)模型如圖1所示。

（2）系統(tǒng)時間是由一系列的協(xié)作時隙t構(gòu)成，在每個時隙，各節(jié)點都有數(shù)據(jù)包發(fā)送。

（3）為分析方便起見，特假設(shè)任意源節(jié)點和目的節(jié)點之間都不能直接通信，必須經(jīng)過中間節(jié)點，且到目的節(jié)點的跳數(shù)基本相同。

（4）所有的數(shù)據(jù)包大小相等，各節(jié)點接收數(shù)據(jù)包消耗的能量相同，轉(zhuǎn)發(fā)數(shù)據(jù)包消耗同等大小的能量。

圖1 網(wǎng)絡(luò)模型

1.2 博弈模型假設(shè)

1.2.1 博弈要素的定義

博弈的三要素是：參與者、策略空間、效用函數(shù)。

參與者：分布在當前Ad Hoc網(wǎng)絡(luò)中理性的節(jié)點，都是博弈的參與者，那么它們的集合可以表示為N=(1,2,…,n)。

策略空間：博弈模型中的所有參與者都有一組可供選擇的策略集合。在本文中有兩種具體策略：合作，轉(zhuǎn)發(fā)其他節(jié)點的數(shù)據(jù)包；不合作，不轉(zhuǎn)發(fā)其他節(jié)點的數(shù)據(jù)包。

效用函數(shù)：即參與者采取某一策略所獲得的收益，下述將定義博弈相關(guān)參數(shù)，并滿足囚徒困境博弈的設(shè)定。

1.2.2 階段博弈假設(shè)

如圖2所示，源節(jié)點A和目的節(jié)點C無法直接通信，故節(jié)點A需要通過中間節(jié)點B的轉(zhuǎn)發(fā)。

圖2 節(jié)點轉(zhuǎn)發(fā)模型

在博弈中，用c代表節(jié)點轉(zhuǎn)發(fā)時的能量消耗，用b代表一個節(jié)點的數(shù)據(jù)包被其他節(jié)點轉(zhuǎn)發(fā)時獲得的利益[3]。當博弈雙方的策略選擇都是合作的時候，效益為（b-c）。如果一個節(jié)點在轉(zhuǎn)發(fā)數(shù)據(jù)上采取不合作，而其他節(jié)點是合作的話，那么自私節(jié)點能夠得到b的效益而合作節(jié)點的效益為-c。這是因為自私節(jié)點的數(shù)據(jù)包被其他合作節(jié)點轉(zhuǎn)發(fā)，但是自私節(jié)點并沒有轉(zhuǎn)發(fā)合作節(jié)點的數(shù)據(jù)包。如果雙方節(jié)點在轉(zhuǎn)發(fā)數(shù)據(jù)上都采取不合作的態(tài)度，那么他們的策略收益為（0,0），這是因為節(jié)點都沒有收益和消耗能量。

基于上述的收益和消耗，建立如表1所示的囚徒困境收益矩陣[4]。

表1 博弈策略收益

無論節(jié)點j選擇什么策略，對于節(jié)點i而言，選擇不合作策略是最好的，所以階段博弈的納什均衡點是雙方節(jié)點同時選擇不合作策略。然而雙方都采取合作策略的收益是最高的，所以在這個收益矩陣中，納什均衡點并不帕累托占優(yōu)。原因就在于網(wǎng)絡(luò)中的節(jié)點都是獨立和自私的，博弈的雙方不知道對方的策略，如果節(jié)點i選擇了合作，而節(jié)點j選擇了不合作，那么節(jié)點i將會獲得最差的收益。所以，自私的節(jié)點通常會選擇獲得最好結(jié)果的策略而不冒險獲得最差收益[5]。

在囚徒困境的內(nèi)容設(shè)定上，必須滿足以下兩個條件：

該囚徒困境的收益矩陣如表1所示。

2 重復博弈的納什均衡和節(jié)點收益

由于節(jié)點當前行為會對后續(xù)的博弈階段造成影響，所以與鄰居節(jié)點間的多次交互將不是相互獨立的階段博弈，而形成重復策略博弈[6]。下面研究重復博弈中的重要概念——納什均衡。

定義1納什均衡（Nash Equilibrium，NE）[7]策略向量為一個納什均衡向量，假如對于所有的參與者都有以下式子成立：

意味著在一個已達到納什均衡的策略中，沒有任何一個理性的參與者能夠通過單方面的策略改變而獲得收益。如表1的囚徒困境所示，在單次的階段博弈中，對于參與者M，N而言，雙方都選擇了不合作策略，盡管是納什均衡解，但并不是全局最優(yōu)點，為了讓理性的參與者合作，通常有兩種辦法：博弈的次數(shù)為無限次；博弈雙方都相信對方不會背叛自己。

其中，P為某節(jié)點階段博弈采取的策略概率；i和j為博弈的節(jié)點；表示的是節(jié)點i在第tn個時隙的效用值。

假設(shè)重復博弈的時隙總長度為T，節(jié)點在各自時隙內(nèi)的策略都會被觀察到。根據(jù)重復博弈的原理，節(jié)點的收益會在每一個階段有δ（0＜δ＜1）的折扣率，它代表節(jié)點的歷史行為對未來利益的影響，若其值越大則表示節(jié)點更加重視一個長期的利益，根據(jù)重復博弈論中基于貼現(xiàn)準則的收益評估方式，假設(shè)T=∞，用Ui代表節(jié)點的平均收益[8]，則有：

在博弈中，節(jié)點存在的時間有限，若當合作節(jié)點都知道其死亡時間，最后一次的博弈必定會選擇不合作。當節(jié)點都無法預(yù)知博弈何時終止時，網(wǎng)絡(luò)中的節(jié)點就必須以無限重復的方式來評估當前策略及其對后來情形的影響。

3 節(jié)點轉(zhuǎn)發(fā)策略的納什均衡分析

3.1 針鋒相對策略的納什均衡分析

針鋒相對策略[9]（Tit-for-Tat，TFT）會根據(jù)博弈對手方的策略來制定自己下一步的策略，策略仿佛“回聲”般出現(xiàn)。

博弈初始時，所有節(jié)點都具有合作意圖，能積極轉(zhuǎn)發(fā)其他節(jié)點的信息，即，其中j為博弈中對方的節(jié)點，i為做出行為決策的節(jié)點。

TFT策略的概率模型如下：

當某個時隙t1，節(jié)點i將它的合作概率改為其中0＜m＜1，則在下一個時隙t2，節(jié)點j的合作概率，節(jié)點i在t2時隙的合作概率又會變成1，此時兩個節(jié)點的概率序列如下所示：

在之后的每個博弈階段，節(jié)點i和j都會模仿對方在上一階段的行為。若節(jié)點i采取合作策略，那么節(jié)點j也是合作的，如果節(jié)點i選擇了不合作，那么節(jié)點j的策略也是不合作。

將式（6）代入到式（3）和式（4）中可得節(jié)點i采取TFT策略的收益為：

又因為節(jié)點都是理性的，僅當Ui≥0時才會選擇該策略。將其代入式（7）中有：

式（8）即是節(jié)點選擇TFT策略的納什均衡條件。

3.2 冷酷策略的納什均衡分析

冷酷策略[10]（Grim Strategy，GS）是一種在博弈中常用的觸發(fā)策略。初始節(jié)點之間都具有合作性，當與節(jié)點i博弈的節(jié)點j在某個時隙選擇了不合作，那么節(jié)點i在這個時隙之后的所有策略都將會選擇不合作。GS策略將會孤立網(wǎng)絡(luò)中的自私節(jié)點，并且極大地打擊存在的自私行為。其概率模型如下：

其中q是節(jié)點i的一個觸發(fā)閾值，當Pi≥q時，這個背叛會被對方節(jié)點忽略；當Pi＜q，就會令博弈的節(jié)點選擇永久的不合作策略作為懲戒。如果對方知道你的策略為觸發(fā)策略，那么對方將不敢采取觸發(fā)策略，那么博弈雙方就可以一直合作下去，即使存在無意的錯誤，也會被判定為不合作且永遠不再合作。本文為方便分析起見，只考慮最差的情況，即Pi＜q，故概率序列如下：

將式（10）代入到式（3）和式（4）中可得節(jié)點i采取GS策略的收益為：

又因為節(jié)點都是理性的，僅當Ui≥0時才會選擇該策略。將其代入式（11）中有：

式（12）即是節(jié)點選擇GS策略的納什均衡條件。

3.3 完全合作策略的納什均衡分析

完全合作策略（Full Cooperation Strategy，F(xiàn)CS）基于理想的情況之下，所有節(jié)點在博弈的任意階段都會選擇合作策略，在本文中作為一種對比策略引入。其概率序列如下：

將式（13）代入到式（3）和式（4）中可得節(jié)點i采取完全合作策略的收益為：

又因為節(jié)點都是理性的，僅當Ui≥0時才會選擇該策略。將其代入式（14）中有：

式（15）即是節(jié)點選擇FCS策略的納什均衡條件。

3.4 寬恕的針鋒相對策略的納什均衡分析

寬恕的針鋒相對策略（Tit-for-Tat with Forgiveness，TFTF）是在經(jīng)歷對方的一個不合作行為后，節(jié)點以一個小概率m()

0＜m＜1去選擇合作，并如同TFT策略一般交替出現(xiàn)。

為方便討論起見，假設(shè)其概率序列如下：

將式（16）代入到式（3）和式（4）中可得節(jié)點i采取完全合作策略的收益為：

又因為節(jié)點都是理性的，僅當Ui≥0時才會選擇該策略。將其代入式（17）中有：

3.5 嚴厲針鋒相對策略的納什均衡分析

嚴厲針鋒相對策略（Stern Tit-for-Tat，STFT）[11]是指當節(jié)點出現(xiàn)不合作行為時，其所有鄰居節(jié)點對它執(zhí)行若干時隙的拒絕合作的懲罰，且其本身策略為合作。懲罰期間結(jié)束后鄰居節(jié)點選擇遺忘對方的不合作行為，重新開始合作。

為方便分析起見，令懲罰期為3個時隙，且重新合作后又出現(xiàn)不合作行為，設(shè)定其概率序列如下：

將式（20）代入到式（3）和式（4）中可得節(jié)點i采取完全合作策略的收益為：

又因為節(jié)點都是理性的，僅當Ui≥0時才會選擇該策略。將其代入式（21）中有：

4 結(jié)語

無線Ad Hoc網(wǎng)絡(luò)起源于軍事運用，時至今日已得到廣泛的關(guān)注，由于其分布式的特點，導致每個節(jié)點都會對網(wǎng)絡(luò)造成影響，故促進節(jié)點之間的合作是有必要的。本文對TFT策略、GS策略、FCS策略、TFTF策略、STFT策略進行了滿足納什均衡的條件比較[12-13]，通過對比可以得知TFT策略更易滿足該條件。

[1]KHALILI A，BAZZI W M，RASTEGARNIA A.Cooperation gain in incremental LMS adaptive networks with noisy links [C]//Proceedings of 2012 SPIT Second International Conference.Dubai：SPIT，2012：107-114.

[2]RAMACHANDRAN S，SHANMUGAM V.Performance comparison of routing attacks in manet and WSN[J].International Journal of Ad Hoc，Sensor&Ubiquitous Computing，2012，3（4）：361-369.

[3]BADE S，KUMAR M，KAMAT P.A reactive energy-alert algorithm for MANET and its impact on node energy consumption [J].International Journal of Computer Applications，2013，71（18）：267-272.

[4]JIN Q，WANG Z，WANG Y L.Strategy changing penalty promotes cooperation in spatial prisoner′s dilemma game[J].Chaos，Solitons&Fractals，2012，45（4）：395-401.

[5]ROCA C P，SANCHEZ A，CUESTA J A.Individual strategy update and emergence of cooperation in social networks[J]. The Journal of Mathematical Sociology，2012，36（1）：1-21.

[6]LEI T，XIANG M S.Research of avoid the selfish behavior in mobile Ad Hoc networks based on repeated game[C]//Proceedings of 2012 the Fourth IEEE International Conference on Multimedia Information Networking and Security.Nanjing，China：IEEE，2012：835-838.

[7]WANG Y，XU Q，LIU Z.Fair computation with tit-for-tat strategy[C]//Proceedings of 2013 the 5th IEEE International Conference on Intelligent Networking and Collaborative Systems.[S. l.]：IEEE，2013：309-314.

[8]SRIVASTAVA V，DASILVA L A.Equilibria for node participation in Ad Hoc networks-an imperfect monitoring approach [C]//Proceedings of 2006 IEEE International Conference on Communications.Istanbul：IEEE，2006，8：3850-3855.

[9]BOYER S，ROBERT J M，ROUSSEAU C，et al.A novel reputation-based tit-for-tat strategy for IEEE 802.11 CSMA/CA protocol[C]//Proceedings of 2012 IEEE Consumer Communications and Networking Conference.Las Vegas：IEEE，2012：143-148.

[10]WANG J，CAI Y Q.A rational secret sharing scheme based on repeated game[C]//Proceedings of 2011 the 7th IEEE International Conference on Computational Intelligence and Security.Hainan，China：IEEE，2011：615-619.

[11]聞英友，趙博，趙宏.基于博弈理論的移動自組網(wǎng)激勵機制研究[J].通信學報，2014，35（4）：44-52.

[12]徐許亮，董榮勝，劉亮龍.無線自組網(wǎng)中節(jié)點協(xié)作的納什均衡研究[J].計算機工程，2010，36（4）：107-109.

[13]孫玉星，趙燕飛，李婭，等.基于概率博弈的無線自組網(wǎng)信任推薦激勵策略的研究[J].計算機科學，2011，38（4）：65-71.

Analysis for forwarding strategy of Ad Hoc network node based on repeated game

TAN Mian，HE Shibiao，SONG Bo，ZHU Guoqing，ZHANG Hui
（Chongqing Communication Institute，Chongqing 400035，China）

In wireless Ad Hoc network，the intercommunication between the source and destination nodes needs the support of relay node.Since the node is rational，it may refuse the forwarding requests.For the cooperation problem among the nodes，the tit-for-tat strategy，grim strategy，full cooperation strategy，tolerant tit-for-tat strategy and severe tit-for-tat strategy are analyzed with Nash equilibrium.According to the theoretical analysis，the tit-for-tat strategy is more advantageous than other strategies because of its low threshold value.

wireless Ad Hoc network；repeated game；Nash equilibrium；forwarding strategy

TN92-34

A

1004-373X（2015）23-0020-04

10.16652/j.issn.1004-373x.2015.23.006

譚冕（1989—），男，重慶人，碩士研究生。主要研究方向為抗干擾通信、無線Ad Hoc網(wǎng)絡(luò)的節(jié)點合作研究。

2015-04-04

重慶市自然科學基金資助項目（cstc2014jcyjA40051）