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

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

?

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

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

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

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

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

0引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

1.3能耗模型

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

Et(d)=kdnEmin

(2)

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

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

(3)

Erx(m,d)=mEelec

(4)

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

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

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

2mEelec+md2Emin

(5)

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

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

(6)

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

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

2.1一次博弈模型

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

(7)

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

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

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

(8)

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

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

2.2信任度函數(shù)

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

(9)

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

2.3懲戒機(jī)制

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

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

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

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

(10)

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

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

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

表1　路由博弈收益矩陣

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

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

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

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

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

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

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

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

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

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

3性能評(píng)估

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

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

圖1給出了2種算法的網(wǎng)絡(luò)生命周期。從圖1中可以看出，隨著博弈輪數(shù)的增加，本文提出的路由算法的節(jié)點(diǎn)死亡數(shù)要低于循環(huán)囚徒困境算法，這是因?yàn)檠h(huán)囚徒困境算法并沒(méi)有考慮節(jié)點(diǎn)能量有限問(wèn)題，在路由通信中，能量消耗不均衡縮短了網(wǎng)絡(luò)的生命周期。而本文算法考慮了節(jié)點(diǎn)的剩余能量，將其作為下一跳節(jié)點(diǎn)選擇的評(píng)價(jià)指標(biāo)之一，剩余能量較大的節(jié)點(diǎn)更有可能被選為轉(zhuǎn)發(fā)節(jié)點(diǎn)，這樣較低剩余能量的節(jié)點(diǎn)被保護(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ò)整體能耗要低。因?yàn)樵诼酚蛇x擇時(shí)，發(fā)送數(shù)據(jù)方節(jié)點(diǎn)傾向于選擇更節(jié)能的通信方式，有效地降低和均衡了網(wǎng)絡(luò)的能量消耗。此外，本文算法考慮了節(jié)點(diǎn)的包轉(zhuǎn)發(fā)概率，成功率較高的節(jié)點(diǎn)在路由過(guò)程中傾向于被選擇，這在一定程度上避免了因數(shù)據(jù)轉(zhuǎn)發(fā)失敗而重傳造成的能量浪費(fèi)?？偠灾疚乃惴ㄔ谀芎木夥矫姹憩F(xiàn)出較好的效果。

圖3給出了節(jié)點(diǎn)在不同移動(dòng)速度下的分組投遞率，隨著節(jié)點(diǎn)平均移動(dòng)速度增加，本文算法的分組投遞率下降趨勢(shì)要比循環(huán)囚徒困境算法緩慢。循環(huán)囚徒困境算法根據(jù)節(jié)點(diǎn)間的親密度以及自身收益來(lái)決定采取合作或背叛策略，在一定程度上激勵(lì)了節(jié)點(diǎn)間的合作，但該算法沒(méi)有對(duì)選擇背叛的自私節(jié)點(diǎn)進(jìn)行懲戒，也沒(méi)有考慮鏈路的可靠性，分組仍然存在重傳、丟失現(xiàn)象。而本文算法不僅考慮了節(jié)點(diǎn)的包轉(zhuǎn)發(fā)成功率，同時(shí)也針對(duì)節(jié)點(diǎn)背叛行為建立懲戒機(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ò)性能的一個(gè)重要指標(biāo)，為了考察2種算法對(duì)網(wǎng)絡(luò)吞吐率的影響，本文進(jìn)行了實(shí)驗(yàn)對(duì)比，如圖4所示。由于網(wǎng)絡(luò)存在自私節(jié)點(diǎn)，循環(huán)囚徒算法并沒(méi)有對(duì)節(jié)點(diǎn)的自私行為進(jìn)行威懾，且該算法沒(méi)有考慮能量均衡消耗，部分節(jié)點(diǎn)消耗過(guò)快，吞吐率在生存后期迅速下降。而本文算法采用懲戒機(jī)制，允許自私節(jié)點(diǎn)在受到懲罰后重新恢復(fù)合作，同時(shí)，算法保持了能耗均衡狀態(tài)，所以吞吐率保持較長(zhǎng)時(shí)間的高位。

4總結(jié)

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

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

參考文獻(xiàn)：

[1]王博，陳訓(xùn)遜. ad hoc網(wǎng)絡(luò)中一種基于信任模型的機(jī)會(huì)路由算法[J]. 通信學(xué)報(bào)，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]董榮勝，馬爭(zhēng)先，郭云川，等.一種基于馬爾科夫博弈的能量均衡路由算發(fā)[J]. 計(jì)算機(jī)學(xué)報(bào)，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]李慧芳，姜?jiǎng)倜鳎f崗.無(wú)線傳感器網(wǎng)絡(luò)中基于博弈論的路由建模[J].傳感技術(shù)學(xué)報(bào).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] 何濤，王鎖萍. 無(wú)線Mesh 網(wǎng)絡(luò)中基于循環(huán)囚徒困境的路由算法[J]. 南京大學(xué)學(xué)報(bào)：自然科學(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ú)線自組織網(wǎng)絡(luò)協(xié)作增強(qiáng)模型[J].軟件學(xué)報(bào)，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

中圖分類號(hào)：TP393

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

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

作者簡(jiǎn)介：

劉欣(1990-)，男，湖南衡陽(yáng)，碩士生，主要研究方向?yàn)橥ㄐ判录夹g(shù)、數(shù)字圖像處理。E-mail：1063657058@qq.com。

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

工程師，主要研究方向?yàn)樾乱淮苿?dòng)通信技術(shù)、物聯(lián)網(wǎng)與視頻監(jiān)控技術(shù)、天線與電波傳播。

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

(編輯：張誠(chéng))