宋蔓蔓，張振宇，楊文忠，張珍

新疆大學(xué)信息科學(xué)與工程學(xué)院，烏魯木齊 830046

一種機會網(wǎng)絡(luò)節(jié)點重復(fù)博弈模型

宋蔓蔓，張振宇，楊文忠，張珍

新疆大學(xué)信息科學(xué)與工程學(xué)院，烏魯木齊 830046

在資源受限的機會網(wǎng)絡(luò)中，節(jié)點在轉(zhuǎn)發(fā)過程中所表現(xiàn)出的自私行為將嚴重影響網(wǎng)絡(luò)性能。針對這一問題，建立基于認錯機制的“禮尚往來”策略的節(jié)點重復(fù)博弈模型。節(jié)點考慮到將來的利益，迫于對懲罰的恐懼而參與轉(zhuǎn)發(fā)。通過該策略，節(jié)點協(xié)作可以使網(wǎng)絡(luò)性能達到最優(yōu)。仿真結(jié)果表明，節(jié)點間的相互協(xié)作增強，在自私節(jié)點較多時也能保證較好的網(wǎng)絡(luò)性能。

機會網(wǎng)絡(luò)；節(jié)點協(xié)作；認錯機制；重復(fù)博弈

1 概述

機會網(wǎng)絡(luò)[1]是一種不需要源節(jié)點和目的節(jié)點之間存在完整鏈路，利用節(jié)點移動帶來的相遇機會實現(xiàn)通信的自組織網(wǎng)絡(luò)。由于節(jié)點的移動性，在機會網(wǎng)絡(luò)中很難維持端到端的連通，消息從源節(jié)點傳遞到目的節(jié)點，通常需要中間節(jié)點的存儲、攜帶和轉(zhuǎn)發(fā)才能完成消息的傳送。

由于轉(zhuǎn)發(fā)消息會消耗節(jié)點有限的資源，如緩存、能量等，節(jié)點為了維護自己的資源拒絕與其他節(jié)點協(xié)作。文獻[2]把機會網(wǎng)絡(luò)中只享受信息資源服務(wù)而不為系統(tǒng)做貢獻的節(jié)點稱為自私節(jié)點。節(jié)點的自私行為將導(dǎo)致網(wǎng)絡(luò)性能嚴重下降[2-4]。因此促進節(jié)點間的協(xié)作成為機會網(wǎng)絡(luò)的一個關(guān)鍵問題。

目前，促進節(jié)點協(xié)作的方法主要分為基于信譽、基于聲譽和博弈論三類方法?；谛抛u的方法[5]基本思想是：節(jié)點為另一個節(jié)點轉(zhuǎn)發(fā)消息將獲取一定的信譽，這些信譽是從發(fā)送方（或目的地）扣除。這個方法實現(xiàn)時需要在每個節(jié)點上添加防篡改硬件，從而可以正確地增加或扣除一個節(jié)點的信譽。基于聲譽的方法[6]記錄節(jié)點過去的行為，幫助節(jié)點區(qū)分和選擇有較高聲譽的、從而愿意幫助其他節(jié)點轉(zhuǎn)發(fā)的節(jié)點，這樣可以得到較好的網(wǎng)絡(luò)性能?，F(xiàn)有檢測機制的不準確性是聲譽系統(tǒng)應(yīng)用的主要障礙。

本文在機會網(wǎng)絡(luò)中存在自私節(jié)點的情況下，建立了基于認錯機制的“禮尚往來”策略（Adm it-Tit-for-Tat，ATFT）的重復(fù)博弈模型，節(jié)點會相互協(xié)作，可以使網(wǎng)絡(luò)性能達到最優(yōu)。

2 基于ATFT策略的重復(fù)博弈模型

重復(fù)博弈是指階段博弈重復(fù)進行（有限次或無限次）構(gòu)成的博弈過程，是一種特殊的博弈[7]。由于其他參與人過去行動的歷史是可以觀測的，因此在重復(fù)博弈中，每個參與人可以使自己在每個階段的策略選擇依賴于其他參與人過去的行為。

由于網(wǎng)絡(luò)節(jié)點當前消息轉(zhuǎn)發(fā)策略行為選擇會影響其他節(jié)點的策略選擇，在重復(fù)博弈理論的基礎(chǔ)上，通過將網(wǎng)絡(luò)節(jié)點之間交互抽象成重復(fù)的多階段動態(tài)博弈，并且使用納什均衡這一概念對利益沖突環(huán)境中節(jié)點理性行為所導(dǎo)致的穩(wěn)定局勢進行預(yù)測。當節(jié)點根據(jù)其他節(jié)點行為始終選擇對自己最有利的協(xié)作策略時，便構(gòu)成了網(wǎng)絡(luò)中的一個納什均衡。這一整體網(wǎng)絡(luò)狀態(tài)的意義在于激勵一致性：此時，任何節(jié)點均不會產(chǎn)生自私企圖，因為這將降低節(jié)點的整體收益。重復(fù)博弈的分析視角為我們從節(jié)點自身角度來引入相應(yīng)的協(xié)作促進機制，同時考察耐心因素對其理性響應(yīng)的影響提供了便利。

ATFT策略的基本思想是節(jié)點第一次總是協(xié)作，之后節(jié)點i根據(jù)對方的上次策略進行決策。即如果對方選擇不協(xié)作，節(jié)點i也選擇不協(xié)作來進行懲罰。在經(jīng)過若干次懲罰之后，對方意識到必須主動轉(zhuǎn)發(fā)來向i認錯，否則懲罰將無限執(zhí)行下去，對方一旦認錯，i必須原諒。

2.1 階段博弈

為分析方便，本文做出如下假設(shè)：

（1）網(wǎng)絡(luò)中存在N個節(jié)點，N={1，2，…，n}。

（2）所有消息的大小相同，發(fā)送、轉(zhuǎn)發(fā)單個消息時每個中繼節(jié)點的花費相同。

（3）整個機會網(wǎng)絡(luò)運行時間由一系列離散的時隙t構(gòu)成(t1，t2，…，tn)，并且單一時隙長度足以保證每個消息均能抵達目的節(jié)點。

（4）由于本文研究的是消息轉(zhuǎn)發(fā)時節(jié)點之間的相互協(xié)作，假設(shè)消息丟失的主要原因是網(wǎng)絡(luò)中節(jié)點的不合作行為。

（5）每次博弈都遵循相同的規(guī)則和過程。

假設(shè)節(jié)點i加入到消息傳輸中，節(jié)點的一個消息被成功轉(zhuǎn)發(fā)的收益為Bi，轉(zhuǎn)發(fā)一個消息的花費為Coi。根據(jù)ATFT策略，綜合考慮對手上一次的策略以及網(wǎng)絡(luò)花費，決定節(jié)點i下一階段的策略，得出節(jié)點i的效用函數(shù)為：

其中-i表示節(jié)點i的對手；S-i={C-i，NC-i}表示節(jié)點-i的策略空間，其中C表示合作，NC表示拒絕合作。節(jié)點i的策略選擇可表示為f(S-i)；b-i表示節(jié)點i接收到傳輸請求的概率；ai表示節(jié)點i轉(zhuǎn)發(fā)消息的概率。

由于資源有限，節(jié)點為了減少資源消耗會拒絕轉(zhuǎn)發(fā)消息。如果網(wǎng)絡(luò)中所有的節(jié)點均選擇這樣的策略，網(wǎng)絡(luò)中消息的傳輸成功率將會是0，由式（1）可知此時節(jié)點效用值最大，所有的節(jié)點達到納什均衡狀態(tài)，但是網(wǎng)絡(luò)中不存在任何協(xié)作轉(zhuǎn)發(fā)。這一穩(wěn)定狀態(tài)顯然并不符合預(yù)期。

2.2 重復(fù)博弈模型

由2.1可知，如果節(jié)點間的交互只進行一次，博弈的結(jié)局與囚徒困境相似，所有節(jié)點選擇不協(xié)作策略形成了單階段博弈唯一的納什均衡。但是在節(jié)點的生命周期中很少只有一次博弈過程，它可以在不同的時刻與不同的對手加入不同的博弈過程。在網(wǎng)絡(luò)中一個節(jié)點在一次博弈中作為消息攜帶者，但是下一刻就可能在另一個博弈中充當消息接收者。因此加強節(jié)點間的相互協(xié)作需要建立一個重復(fù)博弈模型[8]。

假設(shè)重復(fù)博弈過程已經(jīng)執(zhí)行了T次，節(jié)點知道過去T-1次對手的行為。通過用貼現(xiàn)因子δ∈（0，1）來描述效用函數(shù)的話，節(jié)點的總效用值可表示為：

Ui（t）表示節(jié)點i在時刻t的效用值。δ表示節(jié)點對未來利益的重視程度，δ越大，節(jié)點越注重長遠利益，δ越小，節(jié)點越注重眼前利益。當T=∞時，以上博弈過程可視為無限次重復(fù)博弈過程[9]，記作G(∞)，則節(jié)點i的平均效用值為：

2.3 ATFT策略

假設(shè)自私節(jié)點的自私周期是y，則懲罰周期也為y，每個節(jié)點維護一個集合，保存相互交互過的節(jié)點i及交互節(jié)點拒絕與此節(jié)點協(xié)作的次數(shù)Nui。基本思想是：如果節(jié)點-i拒絕幫助節(jié)點i轉(zhuǎn)發(fā)消息，節(jié)點i將(-i，Nu-i)中Nu-i的值加1；一旦節(jié)點-i幫助i轉(zhuǎn)發(fā)，i將(-i，Nu-i)中Nu-i的值清零。以節(jié)點i向-i請求轉(zhuǎn)發(fā)為例，ATFT策略的具體步驟：

（1）如果節(jié)點-i是自私節(jié)點，轉(zhuǎn)向步驟（2），若不是，轉(zhuǎn)向步驟（6）。

（2）節(jié)點-i查看自己是否在集合中存儲了(i，Nui)，若未存儲（說明兩個節(jié)點首次交互），由于節(jié)點首次總是協(xié)作，-i幫助i轉(zhuǎn)發(fā)，并在集合中添加(i，0)，節(jié)點i在集合中添加(-i，0)，轉(zhuǎn)向（8），否則轉(zhuǎn)向（3）。

（3）-i查看集合中的Nui是否小于y，若小于轉(zhuǎn)向（5）。

（4）-i意識到由于自身的自私行為，節(jié)點i已經(jīng)對自己做出y次懲罰，因此主動幫助轉(zhuǎn)發(fā)來認錯。節(jié)點i在收到-i的認錯之后，必須原諒，因此將(-i，Nu-i)中Nu-i清零。

（5）節(jié)點-i為了自身利益的最大化，仍拒絕轉(zhuǎn)發(fā)，i將(-i，Nu-i)中Nu-i值增加1。

（6）若節(jié)點-i不是自私節(jié)點，查看是否存儲了(i，Nui)，若未存儲，-i幫助i轉(zhuǎn)發(fā)，節(jié)點i在集合中添加(-i，0)，否則轉(zhuǎn)向（7）。

（7）-i查看集合中保存的Nui是否為零，若為零，幫節(jié)點i轉(zhuǎn)發(fā)，i(-i，Nu-i)中Nu-i清零；若不為零，則拒絕為節(jié)點i提供轉(zhuǎn)發(fā)服務(wù)，i將(-i，Nu-i)中Nu-i加1。

圖1 節(jié)點對未來利益重視程度對網(wǎng)絡(luò)性能的影響(y=2)

（8）交互結(jié)束。

在博弈過程中可以發(fā)現(xiàn)，一旦節(jié)點-i選擇自私，那么它將采取持續(xù)自私的策略。這是因為如果一次自私能夠讓節(jié)點-i額外獲益，那么在懲罰結(jié)束之后，節(jié)點-i會面臨相同的策略選擇。采用ATFT策略時，網(wǎng)絡(luò)中節(jié)點的效用函數(shù)為：

若博弈過程中節(jié)點i協(xié)作的效用大于自私行為的效用，它將毫不猶豫地選擇協(xié)作，并在下一次博弈時采取持續(xù)協(xié)作的策略。也就是說，為了打消節(jié)點i采取自私行為的念頭，必須保證其持續(xù)協(xié)作時的收益不小于重復(fù)自私行為的收益，這一條件可用式（5）表示：

由于節(jié)點都是理性的，只有式（5）不成立時才會自私。存在δ滿足上式，使節(jié)點避免自私行為，協(xié)作是節(jié)點的最優(yōu)策略，而且節(jié)點沒有足夠的動機偏離這一決策。因此式（5）即為節(jié)點采取ATFT策略時最佳納什均衡的條件。

3 仿真及分析

本文采用仿真工具The ONE 1.4.0[10]分析本文所建立模型的有效性。采用真實城市街區(qū)圖，200個節(jié)點隨機分布在4 500 m×3 400 m的區(qū)域內(nèi)，移動速度為1～3 m/s；節(jié)點間的通信范圍半徑為10 m；節(jié)點緩存大小均為10 MB；消息的大小為500 KB。

首先通過實驗分析了節(jié)點對未來利益重視程度對協(xié)作效果的影響。然后分析了懲罰周期y對協(xié)作性的影響。最后與已有的博弈模型對比，并給出了仿真結(jié)果。

3.1 節(jié)點對未來利益重視程度對協(xié)作性的影響

圖1給出了當懲罰周期y=2時，在機會網(wǎng)絡(luò)中存在不同比例的自私節(jié)點時在不同貼現(xiàn)因子取值下，對Epidem ic算法傳輸成功率和平均延遲的影響。圖1（a）中傳輸成功率隨δ增加而明顯提高，圖1（b）中網(wǎng)絡(luò)平均延遲隨δ增加而降低。隨著節(jié)點對未來利益重視程度的增長，自私節(jié)點會主動選擇認錯，因此整個網(wǎng)絡(luò)的協(xié)作性隨自私節(jié)點對未來利益的重視而得到了改善，進而傳輸成功率會隨之增加，網(wǎng)絡(luò)平均延遲相應(yīng)減少。

3.2 懲罰周期對協(xié)作性的影響

圖2表示在貼現(xiàn)因子σ=1時，在機會網(wǎng)絡(luò)中存在不同比例的自私節(jié)點時在不同懲罰周期取值下，對Epidem ic算法傳輸成功率的影響。在一定范圍內(nèi)，增加y將有助于提高網(wǎng)絡(luò)協(xié)作程度。但是如果y過大，即懲罰周期過長，超過了本實驗仿真過程中節(jié)點的最大相遇次數(shù)，在懲罰周期內(nèi)自私節(jié)點拒不認錯，致使網(wǎng)絡(luò)性能下降。所以y值的選取需要根據(jù)網(wǎng)絡(luò)特定情況而定。

圖2 參數(shù)y對傳輸成功率的影響

3.3 自私節(jié)點比例對協(xié)作性的影響

分別模擬Epidem ic[11]、PROPHET[12]和Spray and Wait[13]三種算法在使用ATFT策略前后自私節(jié)點占節(jié)點總數(shù)的10%，20%，…，80%時對網(wǎng)絡(luò)中傳輸成功率的影響，并且與這三種算法使用冷酷策略（Grim Strategy，GS）[14]和GTFT[15]時的傳輸成功率進行對比。仿真結(jié)果如圖3所示。

圖3 傳輸成功率

Epidem ic算法復(fù)制消息并轉(zhuǎn)交給所遇到的所有節(jié)點，中間節(jié)點若不存在自私節(jié)點，負責(zé)轉(zhuǎn)發(fā)的中繼節(jié)點能及時把消息轉(zhuǎn)交給下一個中繼節(jié)點，最大程度上傳遞消息，所以消息遞交率比較高。自私節(jié)點比例增加時，中繼節(jié)點丟棄消息而不是盡最大努力轉(zhuǎn)發(fā)，因此成功率隨之降低。PROPHET算法是基于概率策略的，由于自私節(jié)點聲稱自己不會遇到其他節(jié)點，即傳輸概率為0，節(jié)點轉(zhuǎn)發(fā)消息時根本不會選擇此類節(jié)點，因此隨著網(wǎng)絡(luò)中自私節(jié)點數(shù)目的增多，可用節(jié)點的數(shù)目隨之減少，消息傳輸成功率隨之降低。網(wǎng)絡(luò)中自私節(jié)點數(shù)目較少時，Spray and Wait算法傳輸成功率最高，但隨著自私節(jié)點數(shù)目的增加，成功率明顯降低。這是由于Spray階段，源節(jié)點中的部分消息被擴散到鄰居節(jié)點，若Wait階段并未發(fā)現(xiàn)目的節(jié)點，那么中繼節(jié)點通過直接傳輸?shù)姆绞桨严魉偷侥康墓?jié)點，因此隨著自私節(jié)點數(shù)目的增多，Spray階段消息被拋棄的幾率也隨之增加，成功率隨之降低。

使用GS策略之后，由于自私節(jié)點首次是合作的，因此當自私節(jié)點較少時，傳輸成功率要高于上述情況；但是由于網(wǎng)絡(luò)中任何一個節(jié)點的一次不協(xié)作將會導(dǎo)致永遠的不協(xié)作，在自私節(jié)點比例增加時，傳輸成功率明顯下降。

使用ATFT策略之后，由于引入了認錯機制，自私節(jié)點出于對懲罰的恐懼，每次收到傳輸請求時都會考慮自私行為帶來的后果，因此在自私節(jié)點逐漸增多的情況下Epidem ic、PROPHET和Spray and Wait三個算法均能保持平穩(wěn)的傳輸成功率，優(yōu)于未使用ATFT策略的情況。GTFT僅考慮了歷史收益對節(jié)點決策的影響，沒有考慮其將來獲利的期望。但是使用ATFT策略節(jié)點考慮了未來利益，導(dǎo)致節(jié)點在博弈過程中進行自我約束，并且提高了傳輸成功率。

4 結(jié)束語

本文建立基于認錯機制的“禮尚往來”策略的節(jié)點重復(fù)博弈模型。利用節(jié)點對將來利益的重視來脅迫它參與轉(zhuǎn)發(fā)協(xié)作。仿真結(jié)果表明，該模型使節(jié)點間的相互協(xié)作大大增強，網(wǎng)絡(luò)性能隨之提高。

[1]Pelusi L，Passarella A，Conti M.Opportunistic networking：data forwarding in disconnected mobile ad hoc networks[J]. Communications Magazine，2006，44（11）：134-141.

[2]Chiou C，Chen L.Poster abstract：an evaluation study of routing reliability in opportunistic networks[C]//Proceedings of the 9th ACM International Symposium on Mobile Ad hoc Networking and Computing.Hong Kong：ACM，2008：455-456.

[3]Panagakis A，Vaiosand A，Stavrakakis L.On the effects of cooperation in DTNs[C]//Proceedings of COMSWARE，2007：1-6.

[4]Marti S，Giuli T，Lai K.Mitigating routing misbehavior in mobile Ad hoc networks[C]//Proceedings of ACM MOBICOM’00.New York，USA：ACM Press，2000.

[5]Zhu Haojin，Lin Xiaodong，Lu Rongxing，et al.SMART：A secure multilayer credit-based incentive scheme for delay-tolerant networks[J].IEEE Trans on Vehicular Technology，2009，58（8）：4628-4639.

[6]Zhang Sihai，Qiu Hongyang，Liu Yuan，et al.Evolutionary reputation model for node selfishness resistance in opportunistic networks[C]//Concurrency and Computation：Practice and Experience，F(xiàn)orthcoming，2011.

[7]Osborne M J，Rubinstein A.A course in game theory[M]. Cambridge：M IT Press，1994.

[8]陸音，石進，謝立.基于重復(fù)博弈的無線自組網(wǎng)絡(luò)協(xié)作增強模型[J].軟件學(xué)報，2008，19（3）：755-776.

[9]Ratliff J.Sampler F T.Great introductory notes to the Folk Theorem[N/OL]（1996）.http：//www.virtualperfeetion. com/gametheory5.3.FolkTheorem Sampler.1.0.pdf.

[10]TKK/COMNET.Project page of the ONE simulator[EB/OL]. http：//www.netlab.tkk.fi/tutkimus/dtn/theone，2008.

[11]Apoorva J，Konstantinos P.Performance analysis of epidemic routing under contention[C]//Proc of the 2006 International Conference on Wireless Communications and Mobile Computing.[S.l.]：ACM Press，2006.

[12]Lindgren A，Doria A，Schelen O.Probabilistic routing in intermittently connected networks[J].Lecture Notes in Computer Science，2004，3126：239-254.

[13]Spyropoulos P K，Raghavendra C S.Spray and wait：al efficient routing scheme for intermittently connected mobile networks[C]//Proceedings of ACM SIGCOMM Workshop on Delay-tolerant Networking，Philadelphia，New York，2005：252-259.

[14]張維迎.博弈論與信息經(jīng)濟學(xué)[M].上海：上海人民出版社，1996：31-81.

[15]Srinivasan V，Nuggehalli P.Cooperation in wireless ad hoc networks[C]//Proc of the IEEE INFOCOM 2003. Washington：IEEE Computer Society，2003：808-817.

SONG Manman,ZHANG Zhenyu,YANG Wenzhong,ZHANG Zhen

College of Information Science and Engineering,Xinjiang University,Urumqi 830046,China

In opportunistic networks with limited resources,the performance of network is seriously affected by selfish behavior of the nodes during the packet forwarding.To solve this problem,the paper establishes a repeated-game model of node cooperation based on a admit mechanism of“Tit-For-Tat”strategy.The nodes consider the long-term interests and participate in forwarding forced by the fear of punishment.By using the strategy,cooperation of nodes in the network can make the network performance to achieve optimal.The simulation results show that the mutual cooperation of nodes is enhanced and the performance of the network can be guaranteed when more selfish nodes exist in network.

opportunistic networks;node cooperation;admit mechanism;repeated game

A

TP393

10.3778/j.issn.1002-8331.1209-0185

SONG Manman,ZHANG Zhenyu,YANG Wenzhong,et al.Repeated-gam e model of node cooperation in opportunistic networks.Computer Engineering and Applications,2014,50（16）：86-89.

國家自然科學(xué)基金（No.61262089）；新疆大學(xué)博士科研啟動基金資助項目（No.BS110127）。

宋蔓蔓（1987—），女，主研方向：機會網(wǎng)絡(luò)；張振宇（1964—），男，副教授，主研方向：對等網(wǎng)絡(luò)，機會網(wǎng)絡(luò)；楊文忠（1971—），男，副教授，主研方向：無線網(wǎng)絡(luò)組播路由；張珍（1988—），女，主研方向：機會網(wǎng)絡(luò)。E-mail：songman0534@126.com

2012-09-18

2012-11-14

1002-8331（2014）16-0086-04