基于節(jié)點信任度和博弈論的Ad hoc網(wǎng)絡(luò)路由算法

劉　欣，李校林,3，夏小霞

(1.重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 400065；2.重慶郵電大學(xué) 通信新技術(shù)應(yīng)用研究中心，重慶 400065；3.重慶信科設(shè)計有限公司，重慶 400065)

?

基于節(jié)點信任度和博弈論的Ad hoc網(wǎng)絡(luò)路由算法

劉欣1,2，李校林1,2,3，夏小霞1

(1.重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 400065；2.重慶郵電大學(xué) 通信新技術(shù)應(yīng)用研究中心，重慶 400065；3.重慶信科設(shè)計有限公司，重慶 400065)

摘要：節(jié)點能耗和路徑可靠性是移動自組織網(wǎng)絡(luò)路由需要考慮的關(guān)鍵因素。為了提高能量利用率以及實現(xiàn)網(wǎng)絡(luò)收益的最大化，在節(jié)點理性、自私的前提下，運用博弈論方法建立了轉(zhuǎn)發(fā)節(jié)點選擇的重復(fù)博弈模型，設(shè)計了節(jié)點信任度評價函數(shù)，并采用懲戒機(jī)制來威懾自私節(jié)點，迫使其自愿采取協(xié)同合作的策略。仿真結(jié)果表明，提出的路由算法能夠均衡網(wǎng)絡(luò)的能量消耗，提高分組投遞率，延長網(wǎng)絡(luò)的生存時間。

關(guān)鍵詞：Ad hoc網(wǎng)絡(luò)；重復(fù)博弈；信任度評價；懲戒機(jī)制；路由

0引言

移動自組織網(wǎng)絡(luò)(mobile ad hoc networks, MANET)[1]是一種由無固定基礎(chǔ)設(shè)施支持的移動節(jié)點組成的無線網(wǎng)絡(luò)，具有開展迅速、無控制中心、靈活組網(wǎng)等優(yōu)點。由于網(wǎng)絡(luò)的高度動態(tài)性、時變性以及丟失性容易導(dǎo)致鏈路質(zhì)量較差，這對Ad hoc網(wǎng)絡(luò)的傳輸可靠性造成了影響。另外，節(jié)點能量受限以及移動性也為新的路由算法的設(shè)計與優(yōu)化帶來了難度。

傳統(tǒng)的Ad hoc網(wǎng)絡(luò)路由協(xié)議大致分為2類：一類為按表驅(qū)動路由協(xié)議，如目的序列距離矢量路由(destination sequenced distance vector routing, DSDV)算法[2]；另一類為按需驅(qū)動路由協(xié)議，如動態(tài)源路由(dynamic source routing, DSR) 算法[3]和按需距離矢量路由(Ad hoc on-demand distance vector, AODV)算法[4]等，這些協(xié)議并未考慮節(jié)點能量、鏈路可靠等因素，多采用最小跳數(shù)優(yōu)先策略。但是，基于最小跳數(shù)原則設(shè)計的路由算法在傳輸數(shù)據(jù)時，容易使得部分節(jié)點過多地被選為轉(zhuǎn)發(fā)節(jié)點，造成這些節(jié)點能量過快消耗，致使網(wǎng)絡(luò)生存時間嚴(yán)重縮短。另外，由于節(jié)點能量、帶寬等資源受限，節(jié)點不可避免地會產(chǎn)生自私性?；诶硇云玫目紤]，自私節(jié)點都希望從其他節(jié)點獲取收益而不消耗資源。所以，在這種利己性的驅(qū)使下，節(jié)點的自私性行為對網(wǎng)絡(luò)性能造成了嚴(yán)重的影響：網(wǎng)絡(luò)吞吐量下降以及資源浪費。

近年來，不少研究者將博弈理論(game theory)引入路由協(xié)議。博弈理論描述了參與者在游戲中的行為，參與者根據(jù)所處環(huán)境選擇對應(yīng)的策略來獲取自身最大收益。在網(wǎng)絡(luò)中，路由路徑的選擇過程與博弈類似，數(shù)據(jù)轉(zhuǎn)發(fā)節(jié)點同樣是根據(jù)所處的網(wǎng)絡(luò)環(huán)境來選擇相應(yīng)策略，并實現(xiàn)最大化收益。文獻(xiàn)[5]為了解決網(wǎng)絡(luò)能耗不均衡的問題，引入馬爾可夫博弈理論，在能量均衡路由分析的基礎(chǔ)上提出了一種馬爾科夫博弈的能量均衡路由算法，該算法實現(xiàn)了節(jié)點能量的均衡消耗，延長了網(wǎng)絡(luò)的生命周期。針對節(jié)點的自私性與理性偏好，文獻(xiàn)[6]采用博弈理論建立了一個基于節(jié)點理性偏好的路由博弈模型，并對網(wǎng)絡(luò)均衡問題進(jìn)行了分析。但以上算法沒有考慮節(jié)點間鏈路可靠性對數(shù)據(jù)轉(zhuǎn)發(fā)造成的影響，也沒有對節(jié)點存在的自私性問題進(jìn)行解決。

針對網(wǎng)絡(luò)中節(jié)點的自私性行為，一些激勵節(jié)點協(xié)同合作的方法被提出，如虛擬貨幣機(jī)制、獎勵機(jī)制、懲戒機(jī)制等。文獻(xiàn)[7]提出了一種不完全信息的數(shù)據(jù)包合作機(jī)制，利用集中仲裁方式，對節(jié)點進(jìn)行“懲罰”和“獎勵”，采用自信概率來影響節(jié)點的決策行為。但是此算法依賴于集中控制，不適合分布式自治下的環(huán)境。文獻(xiàn)[8]將博弈理論運用于無線自組網(wǎng)，提出一種采用虛擬流通方法或者協(xié)作信譽(yù)制度激勵節(jié)點間合作的機(jī)制。另外，一些研究學(xué)者也提出了其他的博弈算法來增強(qiáng)節(jié)點間的合作，如文獻(xiàn)[9]采用支付價格的方式來補(bǔ)償節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)所消耗能量和時延，并建立了一種基于價格機(jī)制的博弈模型來促進(jìn)節(jié)點之間的合作，文獻(xiàn)[10]以博弈理論中的循環(huán)囚徒困境模型為基礎(chǔ)，提出節(jié)點間親密度的概念，并以此為因子激勵節(jié)點的合作，有效地改善網(wǎng)絡(luò)性能。以上算法很好地解決了節(jié)點自私行為對網(wǎng)絡(luò)造成的影響，但未考慮到節(jié)點的能量受限性，因此，所提出來的博弈模型并不適合Ad hoc網(wǎng)絡(luò)能量有限的特點。

在路由選擇過程中，節(jié)點之間數(shù)據(jù)的多次傳遞是重復(fù)進(jìn)行的，并且可以看作是發(fā)送方節(jié)點與潛在接收節(jié)點之間的博弈過程，所以本文在重復(fù)博弈模型的基礎(chǔ)上綜合考慮節(jié)點的能量有限性與鏈路可靠性，提出了一種基于節(jié)點信任度和重復(fù)博弈的路由選擇算法。將路由問題建模為節(jié)點之間的博弈問題，由每個節(jié)點根據(jù)相鄰節(jié)點的信任度來選擇合適的下一跳，逐跳之后形成一條通向目的節(jié)點的路徑。另外，為了降低自私節(jié)點背叛的可能性，算法采用懲戒機(jī)制來促使自私節(jié)點傾向于選擇協(xié)同合作策略。通過仿真實驗證明，本文提出來的算法能夠均衡網(wǎng)絡(luò)能量消耗，提高網(wǎng)絡(luò)分組投遞率，以及延長網(wǎng)絡(luò)的生存時間。

1網(wǎng)絡(luò)系統(tǒng)架構(gòu)

1.1網(wǎng)絡(luò)模型及假定

在分析路由問題時將網(wǎng)絡(luò)拓?fù)淠Ｐ筒捎脽o向圖G=(V,E)表示，V表示拓?fù)銰中的移動節(jié)點集合，E表示節(jié)點間可雙向通信的鏈路集，其中vi∈V為網(wǎng)絡(luò)中的一個節(jié)點，eij=(vi,vj)∈E為節(jié)點vi與vj之間的連接邊。s∈V為源節(jié)點，d∈{V-{s} }為目的節(jié)點。

本文假設(shè)網(wǎng)絡(luò)模型如下。

1) 網(wǎng)絡(luò)是對稱的，且節(jié)點隨機(jī)分布。

2) 網(wǎng)絡(luò)中的節(jié)點具有相同有限的能量，并定義初始能量為Einitial。

3) 網(wǎng)絡(luò)中的節(jié)點具有理性自私性。

4) 網(wǎng)絡(luò)采用離散的時間模型，每個時隙節(jié)點均有一個數(shù)據(jù)包發(fā)送。

5) 網(wǎng)絡(luò)中節(jié)點的最大通信距離為R。

1.2包轉(zhuǎn)發(fā)概率模型

由于Ad hoc網(wǎng)絡(luò)的動態(tài)拓?fù)湟约皞鬏敹嗵院托诺赖牟豢煽啃?，往往存在?shù)據(jù)包因轉(zhuǎn)發(fā)失敗而重新轉(zhuǎn)發(fā)的現(xiàn)象，這會影響網(wǎng)絡(luò)的分組投遞率。定義節(jié)點i轉(zhuǎn)發(fā)包的數(shù)量為Pis(t)，接收包的數(shù)量為Pir(t)，則該節(jié)點在t時刻的包成功轉(zhuǎn)發(fā)概率為

Pi(t)=Pis(t)/Pir(t)

(1)

1.3能耗模型

假設(shè)網(wǎng)絡(luò)中，接收節(jié)點收到信號所需能量為Emin，則發(fā)射節(jié)點發(fā)出信號所消耗的能量為

Et(d)=kdnEmin

(2)

(2)式中：k為常系數(shù)；d為發(fā)射節(jié)點與接收節(jié)點之間的距離(d≤R)；n為2-4之間的整數(shù)值。本文中取n=2，k=1。Et(d)為發(fā)射節(jié)點傳輸單位數(shù)據(jù)需要消耗的能量，如果需要發(fā)送m個數(shù)據(jù)包，則消耗的總能量Etx(m,d)如(3)式所示，接收m個數(shù)據(jù)包所需消耗的能量如式(4)所示。

Etx(m,d)=m(Eelec+Emind2)

(3)

Erx(m,d)=mEelec

(4)

(3)式中，Eelec為節(jié)點在發(fā)送與接收數(shù)據(jù)過程中內(nèi)部電路所消耗的能量。

所以，對于中繼節(jié)點而言，傳輸m個數(shù)據(jù)包所需消耗的能量為

Ecost(m,d)=Etx(m,d)+Erx(m,d)=

2mEelec+md2Emin

(5)

對于單個節(jié)點，在接收與轉(zhuǎn)發(fā)數(shù)據(jù)過程中，其剩余能量為

Eremain(m,d)=Einitial-Ecost(m,d)

(6)

(6)式中：Einitial為節(jié)點的初始能量；Ecost(m,d)為轉(zhuǎn)發(fā)m個數(shù)據(jù)包所需消耗的能量，可通過(5)式得到。

2基于信任度的重復(fù)轉(zhuǎn)發(fā)博弈

2.1一次博弈模型

節(jié)點數(shù)據(jù)包的一次轉(zhuǎn)發(fā)可以看作一次博弈過程。假設(shè)T取值為1表示節(jié)點i發(fā)送自己的數(shù)據(jù)包，取值為0表示放棄發(fā)送自己的數(shù)據(jù)包；Z取值為1表示節(jié)點i的鄰居節(jié)點轉(zhuǎn)發(fā)其數(shù)據(jù)包，取值為0表示其鄰居節(jié)點放棄為其轉(zhuǎn)發(fā)數(shù)據(jù)包；F取值為1表示節(jié)點i愿意轉(zhuǎn)發(fā)其他節(jié)點的數(shù)據(jù)包，取值為0表示放棄轉(zhuǎn)發(fā)其他節(jié)點的數(shù)據(jù)包；R取值為1表示節(jié)點i成功發(fā)送自己的數(shù)據(jù)包，取值為0表示自己的數(shù)據(jù)包發(fā)送失敗，且存在如下關(guān)系式

(7)

由(7)式可以看出，只有當(dāng)節(jié)點發(fā)送數(shù)據(jù)，且其數(shù)據(jù)被鄰居節(jié)點轉(zhuǎn)發(fā)時，該節(jié)點才算成功發(fā)送自身數(shù)據(jù)(R=1)。

不妨假設(shè)當(dāng)鄰居節(jié)點合作時，節(jié)點成功發(fā)送一個包的收益為b，接收一個包的收益為0，則節(jié)點i在時隙tj中的收益模型為

ui(R,T,F)=R·b-T·c-F·c·mi

(8)

其中mi為節(jié)點i在時隙tj中轉(zhuǎn)發(fā)數(shù)據(jù)包的數(shù)目，c為發(fā)送一個包的所需消耗的能量。

定義節(jié)點i的策略S為(R,T,F) 三元組的取值形式，并規(guī)定所有節(jié)點都是同時決策。由(9)式可以看出，當(dāng)節(jié)點拒絕轉(zhuǎn)發(fā)數(shù)據(jù)包時，即當(dāng)F=0，T=1時，無論其鄰居節(jié)點是否為其轉(zhuǎn)發(fā)數(shù)據(jù)，節(jié)點獲得的收益總要大于其為別的節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)包獲得的收益。因此策略(*, 1 ,0)為整個博弈的優(yōu)超策略，當(dāng)全部節(jié)點采用該策略時，博弈G將達(dá)到納什均衡[11]，且當(dāng)策略為(1, 1, 0)時，博弈G達(dá)到帕累托最優(yōu)策略，但該狀態(tài)下所有節(jié)點不轉(zhuǎn)發(fā)其他節(jié)點數(shù)據(jù)會導(dǎo)致整個網(wǎng)絡(luò)的性能下降，顯然不是我們期望的。

2.2信任度函數(shù)

在數(shù)據(jù)包轉(zhuǎn)發(fā)的過程中，自私節(jié)點的決策具有如下特點：①自私節(jié)點更加傾向于選擇剩余能量較高、包轉(zhuǎn)發(fā)成功率較高的相鄰節(jié)點作為轉(zhuǎn)發(fā)節(jié)點。②鄰居節(jié)點在做轉(zhuǎn)發(fā)決策時，若其獲得的收益越大，其轉(zhuǎn)發(fā)的可能性也就越大。因此，為了合理地選擇下一跳節(jié)點，本文依據(jù)節(jié)點的包轉(zhuǎn)發(fā)概率模型、能耗模型以及收益模型來設(shè)計節(jié)點信任度評估函數(shù)，如(9)式所示。

(9)

(9)式中：Eremain為節(jié)點t時刻的剩余能量；Einitial為節(jié)點的初始能量；ui為本輪博弈中轉(zhuǎn)發(fā)數(shù)據(jù)包所能獲得的收益；Pi(t)為節(jié)點在t時刻的包成功轉(zhuǎn)發(fā)概率。設(shè)計可信度函數(shù)是從節(jié)點自身角度出發(fā)，用于評價鄰居節(jié)點轉(zhuǎn)發(fā)自己數(shù)據(jù)包的一種度量標(biāo)準(zhǔn)。

2.3懲戒機(jī)制

造成節(jié)點之間的協(xié)作困境是由于節(jié)點不會考慮自私行為對將來收益造成影響。若不采用懲罰手段，自私節(jié)點不會自愿消耗能量去轉(zhuǎn)發(fā)其他節(jié)點的數(shù)據(jù)。因此，本文提出了對于不合作的節(jié)點采取懲戒的策略，當(dāng)節(jié)點在上一輪發(fā)送數(shù)據(jù)過程中存在作弊行為，整個網(wǎng)絡(luò)會立馬得知，那么在下一輪博弈的時候，該節(jié)點在發(fā)送自身數(shù)據(jù)時會被鄰居節(jié)點拒絕轉(zhuǎn)發(fā)，且節(jié)點自身在轉(zhuǎn)發(fā)其他節(jié)點的數(shù)據(jù)時得不到任何收益。當(dāng)后繼懲罰損害了其利益，并超過作弊時的短期利益，將會對自私節(jié)點產(chǎn)生威懾，迫使該節(jié)點采取協(xié)同合作的態(tài)度。節(jié)點在懲罰結(jié)束后將繼續(xù)參與下一輪的路由博弈，其作弊歷史會被遺忘。

2.4基于信任度的重復(fù)博弈

在Ad hoc網(wǎng)絡(luò)中，節(jié)點的能量是有限的，當(dāng)節(jié)點的剩余能量不足以發(fā)送或者轉(zhuǎn)發(fā)一個數(shù)據(jù)包時，我們認(rèn)為該節(jié)點死亡。本文定義上述的重復(fù)博弈過程為有限次數(shù)的博弈，當(dāng)網(wǎng)絡(luò)中死亡節(jié)點數(shù)目的百分比超過90%時，博弈結(jié)束。

根據(jù)重復(fù)博弈論中的收益評估方式，節(jié)點i在時隙tj中k次博弈的總收益Ui是各階段收益總和的一個折現(xiàn)值，用式(10)表述為

(10)

(10)式中，0<δ<1，該系數(shù)越大，節(jié)點將來的行為對收益的影響也就越大。

根據(jù)ui的定義，可以得出節(jié)點在博弈選擇的策略以及相應(yīng)收益，如表1所示。

從表1可以看出，策略DF沒有被采用，因為對于理性且自私的節(jié)點而言，不發(fā)送自身數(shù)據(jù)而轉(zhuǎn)發(fā)其他節(jié)點的數(shù)據(jù)，不僅得不到收益而且還要消耗自身的能量，這種行為顯然是不會被采用的。所以本文網(wǎng)絡(luò)中的節(jié)點只有3種可選策略，即S=(FF,FD,DD)。

表1　路由博弈收益矩陣

2.5基于信任度的博弈路由選擇算法

本文路由算法通過數(shù)據(jù)發(fā)送節(jié)點與潛在接收方節(jié)點之間的兩兩博弈，自組織地建立路由路徑。其算法的基本流程描述如下。

步驟1初始化網(wǎng)絡(luò)參數(shù)。

步驟2數(shù)據(jù)發(fā)送方節(jié)點向周圍的鄰居節(jié)點發(fā)起路由請求，并按式(9)評估所有鄰居節(jié)點的可信任度。

步驟3比較所有鄰居節(jié)點的可信任度，選擇可信任度值最大的節(jié)點作為下一跳為其轉(zhuǎn)發(fā)數(shù)據(jù)。

步驟4如果該節(jié)點決定為其轉(zhuǎn)發(fā)數(shù)據(jù)，就會回復(fù)路由確定消息并跳到步驟7。若該節(jié)點放棄為其轉(zhuǎn)發(fā)數(shù)據(jù)，轉(zhuǎn)入步驟5。

步驟5判斷該節(jié)點是否為存在自私行為。如果存在，則根據(jù)本文設(shè)定的懲戒機(jī)制對其采取懲罰。否則轉(zhuǎn)入步驟6。

步驟6發(fā)送方節(jié)點根據(jù)信任度值向次優(yōu)的鄰居節(jié)點發(fā)送路由請求，并轉(zhuǎn)到步驟4。

步驟7重復(fù)步驟2-6，直到所有數(shù)據(jù)發(fā)送至目的節(jié)點，算法結(jié)束。

這種路由方式不僅可以保證數(shù)據(jù)在轉(zhuǎn)發(fā)出去的情況下，盡可能地會去選擇剩余能量較高、轉(zhuǎn)發(fā)成功率較高的節(jié)點作為跳轉(zhuǎn)節(jié)點，而且符合節(jié)點的理性偏好特性。

3性能評估

本文采用NS2進(jìn)行仿真實驗，將基于IEEE802.11協(xié)議中分布式協(xié)調(diào)機(jī)制作為MAC層協(xié)議，數(shù)據(jù)傳輸率為2 Mbit/s。網(wǎng)絡(luò)中節(jié)點均勻隨機(jī)分布，且以Random Waypoint Model 方式隨機(jī)移動，每個節(jié)點的通信范圍為250 m，節(jié)點速度在0-30 m/s之間均勻變化。規(guī)定當(dāng)網(wǎng)絡(luò)中90%節(jié)點死亡時，網(wǎng)絡(luò)失效。其他仿真參數(shù)如表2所示。

為了驗證算法性能，將本文算法與文獻(xiàn)[10]提出的循環(huán)囚徒困境博弈算法進(jìn)行實驗對比。將網(wǎng)絡(luò)的生命周期、網(wǎng)絡(luò)能量總耗、分組投遞率及網(wǎng)絡(luò)吞吐量作為評價標(biāo)準(zhǔn)。

圖1給出了2種算法的網(wǎng)絡(luò)生命周期。從圖1中可以看出，隨著博弈輪數(shù)的增加，本文提出的路由算法的節(jié)點死亡數(shù)要低于循環(huán)囚徒困境算法，這是因為循環(huán)囚徒困境算法并沒有考慮節(jié)點能量有限問題，在路由通信中，能量消耗不均衡縮短了網(wǎng)絡(luò)的生命周期。而本文算法考慮了節(jié)點的剩余能量，將其作為下一跳節(jié)點選擇的評價指標(biāo)之一，剩余能量較大的節(jié)點更有可能被選為轉(zhuǎn)發(fā)節(jié)點，這樣較低剩余能量的節(jié)點被保護(hù)。因此，網(wǎng)絡(luò)的生命周期要優(yōu)于循環(huán)囚徒困境算法。

表2　仿真參數(shù)

圖1　網(wǎng)絡(luò)生命周期圖Fig.1　Network lifecycle diagram

圖2描述了網(wǎng)絡(luò)的總體能耗?？梢钥吹?，本文算法的網(wǎng)絡(luò)整體能耗增加比較平緩，與循環(huán)囚徒困境算法相比，網(wǎng)絡(luò)整體能耗要低。因為在路由選擇時，發(fā)送數(shù)據(jù)方節(jié)點傾向于選擇更節(jié)能的通信方式，有效地降低和均衡了網(wǎng)絡(luò)的能量消耗。此外，本文算法考慮了節(jié)點的包轉(zhuǎn)發(fā)概率，成功率較高的節(jié)點在路由過程中傾向于被選擇，這在一定程度上避免了因數(shù)據(jù)轉(zhuǎn)發(fā)失敗而重傳造成的能量浪費?？偠灾疚乃惴ㄔ谀芎木夥矫姹憩F(xiàn)出較好的效果。

圖3給出了節(jié)點在不同移動速度下的分組投遞率，隨著節(jié)點平均移動速度增加，本文算法的分組投遞率下降趨勢要比循環(huán)囚徒困境算法緩慢。循環(huán)囚徒困境算法根據(jù)節(jié)點間的親密度以及自身收益來決定采取合作或背叛策略，在一定程度上激勵了節(jié)點間的合作，但該算法沒有對選擇背叛的自私節(jié)點進(jìn)行懲戒，也沒有考慮鏈路的可靠性，分組仍然存在重傳、丟失現(xiàn)象。而本文算法不僅考慮了節(jié)點的包轉(zhuǎn)發(fā)成功率，同時也針對節(jié)點背叛行為建立懲戒機(jī)制，有效地提高了分組的成功投遞率，保證了鏈路的可靠性。

圖2　網(wǎng)絡(luò)總能耗圖Fig.2　Network total energy diagram

圖3　分組投遞率圖Fig.3　Rate of delivering packet diagram

網(wǎng)絡(luò)吞吐率是網(wǎng)絡(luò)性能的一個重要指標(biāo)，為了考察2種算法對網(wǎng)絡(luò)吞吐率的影響，本文進(jìn)行了實驗對比，如圖4所示。由于網(wǎng)絡(luò)存在自私節(jié)點，循環(huán)囚徒算法并沒有對節(jié)點的自私行為進(jìn)行威懾，且該算法沒有考慮能量均衡消耗，部分節(jié)點消耗過快，吞吐率在生存后期迅速下降。而本文算法采用懲戒機(jī)制，允許自私節(jié)點在受到懲罰后重新恢復(fù)合作，同時，算法保持了能耗均衡狀態(tài)，所以吞吐率保持較長時間的高位。

4總結(jié)

本文提出了一種基于節(jié)點信任度和博弈理論的Ad hoc網(wǎng)絡(luò)路由選擇算法。在考慮節(jié)點的理性偏好條件下，設(shè)計了與節(jié)點剩余能量、包成功轉(zhuǎn)發(fā)率及路由博弈收益相關(guān)的可信任函數(shù)。發(fā)送數(shù)據(jù)方通過評估鄰居節(jié)點的可信任度來合理選擇下一跳。為了防止節(jié)點的自私性行為，又采用懲戒機(jī)制來迫使節(jié)點協(xié)同合作。實驗結(jié)果表明，該算法能夠均衡網(wǎng)絡(luò)的能量消耗，提高分組投遞率、網(wǎng)絡(luò)吞吐量，以及延長網(wǎng)絡(luò)的生存時間。

圖4　網(wǎng)絡(luò)吞吐率圖Fig.4　Network throughput rate diagram

參考文獻(xiàn)：

[1]王博，陳訓(xùn)遜. ad hoc網(wǎng)絡(luò)中一種基于信任模型的機(jī)會路由算法[J]. 通信學(xué)報，2013，34(9)：92-104.

WANG Bo, CHEN Xunxun. Opportunistic routing algorithm based on trust model for ad hoc network[J]. Journal on Communication，2013，34(9): 92-104.

[2]PERKINS C E, BHAGWAT P. Highly dynamic destination-sequenced distance-vector routing (DSDV) for Mobile Computer[C]// Proc ACM SIGCOMM’94. UK: Computer Communications Review, 1994: 234-244.

[3]JOHNSON D B, MALTZ D A, BROCH Josh. DSR: The dynamic source routing protocol for multihop wireless ad hoc networks[C]// ACM/IEEE. Ad Hoc Networking.USA:Addison Wesley Longman Publishing Co,2001:139-172.

[4]PERKINS C E, ROYER E M. Ad hoc on-demand distance vector routing[C]//IEEE WORKSHOP. Proc of the 2nd IEEE Workshop on Mobile Computer Systems and Applications. USA: IEEE Computer Society, 1990: 90.

[5]董榮勝，馬爭先，郭云川，等.一種基于馬爾科夫博弈的能量均衡路由算發(fā)[J]. 計算機(jī)學(xué)報，2013，36(7):1500-1508.

DONG Rongsheng，MA Zhengxian，GUO Yunchuan,et al. A Markov Game Theory-Based Energy Balance Routing Algorithm[J]. Chinese Journal of Computers，2013，36(7): 1500-1508.

[6]李慧芳，姜勝明，韋崗.無線傳感器網(wǎng)絡(luò)中基于博弈論的路由建模[J].傳感技術(shù)學(xué)報.2007，20(9):2075-2079.

LI Huifang，HIANG Shengming，WEI Gang. Game-Theoretic Modeling on Routing in Wireless Sensor Networks[J]. Chinese Journal of Sensors and Actuators. 2007，20(9)：2075-2079.

[7]ZENG Jia，MU Chundi. Game theory-based energy balance routing with incomplete information in wireless sensor networks[J]. Acta Automatica Sinica，2008，34(3): 317-322.

[8]ZHONG S，CHEN J，YANG Y R. A Simple，Cheat-Proof, Credit-Based System for Mobile Ad hoc Networks[C]// Proceeding of IEEE IOFOCOM. San Francisco，CA，USA：IEEE Press，2003: 1987-1997.

[9]SHASTRY N, ADVE R S. Stimulating Cooperative diversity in wireless ad hoc networks through pricing[C]// In Proc. IEEE intl Conf Commun. Istanbul: IEEE, 2006: 3747-3752.

[10] 何濤，王鎖萍. 無線Mesh 網(wǎng)絡(luò)中基于循環(huán)囚徒困境的路由算法[J]. 南京大學(xué)學(xué)報：自然科學(xué)版， 2010，46(5):561-566.

HE Tao, WANG Suoping. A routing algorithm for wireless mesh network based on alternating prisoner’s dilemma[J]. Journal of Nanjing University：Natural Sciences Edition, 2010，46(5)：561-566.

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

LU Yin，SHI Jin，XIE Li. Repeated-Game Modeling of Cooperation Enforcement in Wireless Ad Hoc Network[J].Journal of Software，2008，19(3):755-768.

Trust and game theory based routing algorithm for Ad hoc networks

LIU Xin1,2, LI Xiaolin1,2,3, XIA Xiaoxia1

(1.School of Communication and Information Engineering,Chongqing University of Posts and Telecommunications,Chongqing 400065,P.R.China;2. Research Centre for Application of New Communication Technologies,Chongqing University of Posts and Telecommunications,Chongqing 400065,P.R.China;3.Chongqing Information Technology Designing CO.LTD，Chongqing 400065，P.R.China)

Abstract:Energy consumption and path reliability are the key issues in mobile Ad hoc networks. In order to improve energy efficiency and maximize networks payoff, a repeated-game theoretic model is proposed for selecting forwarding nodes under the conditions of selfish and rational nodes, a trust evaluation function is designed, and punishment mechanism is used to deter the selfish nodes and force them to take cooperation strategy. Simulation indicates that the proposed routing algorithm can keep the balance of energy consumption and improve the packet delivery ratio and prolong network lifetime.

Keywords：Ad hoc network；repeated game；trust evaluation；punishment mechanism；routing

DOI：10.3979/j.issn.1673-825X.2016.01.018

收稿日期：2014-04-16

修訂日期：2015-03-07通訊作者：劉欣1063657058@qq.com

中圖分類號：TP393

文獻(xiàn)標(biāo)志碼：A

文章編號：1673-825X(2016)01-0120-05

作者簡介：

劉欣(1990-)，男，湖南衡陽，碩士生，主要研究方向為通信新技術(shù)、數(shù)字圖像處理。E-mail：1063657058@qq.com。

李校林(1968-)，男，碩士生導(dǎo)師，正高級

工程師，主要研究方向為新一代移動通信技術(shù)、物聯(lián)網(wǎng)與視頻監(jiān)控技術(shù)、天線與電波傳播。

夏小霞(1990-)，女，湖南益陽人，碩士生，主要研究方向為移動通信、自組織網(wǎng)絡(luò)路由算法。E-mail：fighting_xxx@163.com。

(編輯：張誠)