【正文】 仿真結(jié)果同樣也證明了我們的算法能夠有效懲罰自私節(jié)點(diǎn)，從而激勵(lì)節(jié)點(diǎn)合作。本文基于尋路包的統(tǒng)計(jì)特性，提出了一種被動(dòng)丟棄尋路包的行為檢測(cè)和懲罰算法，使得自私節(jié)點(diǎn)的收益大幅度下降。6 結(jié)論對(duì)于采用按需路由的Ad hoc網(wǎng)絡(luò)來說，自私節(jié)點(diǎn)丟棄尋路包從而合法逃避為其他節(jié)點(diǎn)中繼數(shù)據(jù)的責(zé)任是節(jié)約自己能量的最好方式。參與路由越多的節(jié)點(diǎn)獲得的支付越多，從而使節(jié)點(diǎn)愿意合作。[20]提出一種基于虛擬支付的緊湊激勵(lì)機(jī)制來促使節(jié)點(diǎn)在尋路階段合作。尋路過程忠節(jié)點(diǎn)鄰居集未知、存在合法丟包的特點(diǎn)同樣使得2ACK不能正常發(fā)揮作用：盡管節(jié)點(diǎn)收到下兩跳的ACK時(shí)能夠確定下一跳節(jié)點(diǎn)是合作的；但是沒有收到ACK時(shí)，卻不能判定下一跳自私丟包。[19]提出了一種基于ACK的自私丟包檢測(cè)方式2ACK，其核心思想是傳輸路徑上的節(jié)點(diǎn)接收到數(shù)據(jù)包后返回ACK給兩跳前的節(jié)點(diǎn)，從而可以對(duì)中間節(jié)點(diǎn)的傳輸行為進(jìn)行判定。其次，由于一個(gè)RREQ可能被多個(gè)節(jié)點(diǎn)廣播，因此為了降低尋路開銷，節(jié)點(diǎn)對(duì)同一個(gè)RREQ只作一次響應(yīng)，后續(xù)收到的重復(fù)RREQ將被丟棄，因此存在大量合法丟包。從Watchdog的機(jī)理中可以看出它并不適合于尋路階段RREQ的丟包檢測(cè)；首先，RREQ是廣播包，鏈路層不提供應(yīng)答，因此節(jié)點(diǎn)不能確定此時(shí)鄰居域內(nèi)哪些節(jié)點(diǎn)接收到RREQ，哪些沒有。當(dāng)節(jié)點(diǎn)檢測(cè)到其下一跳自私丟包的比率超過一定門限時(shí)，它將通知源節(jié)點(diǎn)。節(jié)點(diǎn)發(fā)包之后，偵聽下一跳節(jié)點(diǎn)的通信。[8]關(guān)注的是數(shù)據(jù)傳輸階段的自私丟包問題，并提出了后續(xù)文獻(xiàn)中廣泛應(yīng)用的Watchdog檢測(cè)方案。當(dāng)丟包率大于80%時(shí)，因此本文算法激活后，理性節(jié)點(diǎn)將選擇合作而不是自私丟包，從而實(shí)現(xiàn)對(duì)自私節(jié)點(diǎn)的激勵(lì)。在場(chǎng)景1本文算法沒有啟用的時(shí)候，自私節(jié)點(diǎn)只有在丟包率較高（80%）時(shí)，吞吐量才能得到顯著的增加。設(shè)自私節(jié)點(diǎn)數(shù)目為6，即20% 的節(jié)點(diǎn)自私丟包，丟包概率分別為50%、60%直到100%。自私節(jié)點(diǎn)數(shù)目越多，節(jié)省的能量越多，吞吐量提高的幅度就越明顯。自私節(jié)點(diǎn)丟棄RREQ包使得合作節(jié)點(diǎn)需要花費(fèi)更多的能量中繼包，導(dǎo)致自己的吞吐量下降。場(chǎng)景2本文算法啟用之后，對(duì)自私節(jié)點(diǎn)進(jìn)行有效檢測(cè)和懲罰，使得自私節(jié)點(diǎn)吞吐量大幅度下降，低于其合作狀態(tài)，因此理性的自私節(jié)點(diǎn)將傾向采用合作策略，從而實(shí)現(xiàn)對(duì)自私節(jié)點(diǎn)的激勵(lì)。對(duì)比自私節(jié)點(diǎn)和合作節(jié)點(diǎn)在不同場(chǎng)景下的吞吐量，如下圖所示：圖3 不同場(chǎng)景下吞吐量與自私節(jié)點(diǎn)數(shù)目關(guān)系首先觀察自私節(jié)點(diǎn)吞吐量的變化規(guī)律。設(shè)置三種場(chǎng)景，基線場(chǎng)景：所有節(jié)點(diǎn)均合作；場(chǎng)景1：自私節(jié)點(diǎn)丟棄RREQ包，但是沒有啟用本文算法；場(chǎng)景2：自私節(jié)點(diǎn)丟棄RREQ，但是合作節(jié)點(diǎn)啟用了本文算法。節(jié)點(diǎn)的初始能量為5，仿真時(shí)間設(shè)為2000秒。4 仿真驗(yàn)證 我們?nèi)圆捎?節(jié)中的30節(jié)點(diǎn)仿真場(chǎng)景對(duì)算法進(jìn)行仿真驗(yàn)證?？梢钥闯觯?dāng)ε較小，p較大時(shí)，不等式（3）對(duì)于大部分δ值均成立，系統(tǒng)達(dá)到合作的均衡狀態(tài)。l δ*隨著p的增加而降低，其原因可解釋為懲罰越嚴(yán)厲，節(jié)點(diǎn)偏離既有策略所獲得的收益越小，節(jié)點(diǎn)越傾向于合作l δ*隨著ε的增加而增加，當(dāng)ε=，不論其他參數(shù)為何值，節(jié)點(diǎn)均不能達(dá)成相互合作。δ*與各參數(shù)之間的關(guān)系如圖2所示。具體來說，就是在策略要求節(jié)點(diǎn)合作時(shí)，節(jié)點(diǎn)采用合作行動(dòng)的收益應(yīng)大于采取自私行動(dòng)的收益，即：Ui（C，*） Ui（D，*） (3)*為C或者D。動(dòng)態(tài)行為策略σ是一個(gè)均衡的充要條件是對(duì)每個(gè)局中人i和每個(gè)行為策略，使用σ所獲得的貼現(xiàn)收益要大于等于使用所獲得的貼現(xiàn)收益[18]： (1)其中 表示若每個(gè)局中人i在每個(gè)回合都使用行為策略σi并存在ε的誤判率時(shí)，t時(shí)槽局中人所采用的行動(dòng)組合為a的概率。δ*越大，有效范圍越小。能夠促成合作的δ值的下界用δ*來表示。 除了上述兩個(gè)因素外，本文用δ來反應(yīng)節(jié)點(diǎn)能量限制的影響。行為策略的整體收益通過貼現(xiàn)平均準(zhǔn)則來計(jì)算：其中貼現(xiàn)因子0≤δ1代表了對(duì)節(jié)點(diǎn)耐心和遠(yuǎn)見的一種度量，或者是博弈在下一回合仍然繼續(xù)的概率。盡管在實(shí)際應(yīng)用中，這兩個(gè)概率是不同的，并且隨時(shí)間變化，但為了分析的方便，我們假設(shè)兩者相同且不隨時(shí)間變化，均為ε，粗略的反應(yīng)了本文算法中Thi、Tha、Ths的影響。ui來表示節(jié)點(diǎn)i在階段博弈中獲得的支付，則階段博弈的支付矩陣為：表1：階段博弈的支付矩陣合作（C）自私（D）合作（C）（α2β，α2β）（ 2β，αβ）自私（D）（αβ，2β）（β，β）可以看出階段博弈的局勢(shì)是一個(gè)典型的囚徒困境，其納什均衡是（自私，自私），也就是說靜態(tài)策略是無法促成合作的。用Ai={合作（C），自私（D）}來表示i節(jié)點(diǎn)的可選行動(dòng)。一般來說，α應(yīng)遠(yuǎn)大于 β。如果對(duì)方選擇中繼，則源節(jié)點(diǎn)可獲得α單位的收益。每時(shí)槽內(nèi)兩節(jié)點(diǎn)均進(jìn)行一次尋路和數(shù)據(jù)傳輸過程。為了分析的方便，我們把時(shí)間軸劃分為離散的時(shí)槽。 系統(tǒng)建模我們用隨機(jī)配對(duì)重復(fù)博弈來對(duì)網(wǎng)絡(luò)的尋路過程進(jìn)行抽象。由于網(wǎng)絡(luò)情況千變?nèi)f化，不論Thi、Tha、Ths取什么值，靜態(tài)設(shè)定或者動(dòng)態(tài)變化，都可能存在誤判。3 算法分析算法的表現(xiàn)與Thi、Tha、Ths和Thp四個(gè)參數(shù)密切相關(guān)，其中Thi、Tha、Ths確定了檢測(cè)的誤判率， Thp決定了算法的懲罰力度。例如，可采用基于密鑰預(yù)分配[15]或者基于公鑰的身份認(rèn)證體系[16]來保證節(jié)點(diǎn)身份的真實(shí)性。[15]對(duì)此進(jìn)行了深入的研究，并提出了多種解決方案，如無線資源檢測(cè)，密鑰驗(yàn)證等等。這樣自私節(jié)點(diǎn)不能改動(dòng)尋路包的源地址項(xiàng)，從而解決了第一個(gè)問題。鄰居以及中間節(jié)點(diǎn)可以對(duì)RREQ包的發(fā)起方身份進(jìn)行驗(yàn)證。第一個(gè)問題在可采用[7]中應(yīng)對(duì)主動(dòng)篡改攻擊的方式來解決。2，變更自己的身份，如采用sybil 攻擊[15]。當(dāng)節(jié)點(diǎn)收到數(shù)據(jù)包DATA的時(shí)候，判斷其源節(jié)點(diǎn)的ξ，如果ξThs，以概率Thp丟棄。需要注意的是這兩個(gè)值均是過去一段時(shí)間內(nèi)的統(tǒng)計(jì)值，時(shí)間段外的情況不在考慮范圍內(nèi)，時(shí)間段的推移在add函數(shù)中實(shí)現(xiàn)。如果兩者相同，認(rèn)為該包是鄰居節(jié)點(diǎn)生成的，若兩者不同，則認(rèn)為是鄰居節(jié)點(diǎn)中繼的。 return。amp。/* Handling and Relaying of RREQ*/ ....../*Punishment for Selfish Node*/DSrc=RouteSOURCEof(DATA)。 Random::uniform(0,1) Th_p) drop(RREQ)。/*Punishment for Selfish Node*/if(Th_i) ratio= if(ratioTh_aamp。if(Nb==RSrc) Nb. REQ_s_add(now)。Nb=Lasthopof(RREQ)。這兩個(gè)門限值的選擇與網(wǎng)絡(luò)拓?fù)洹I(yè)務(wù)模型等密切相關(guān)，其關(guān)系留待下一步工作討論。當(dāng)ξ值小于Tha時(shí)，認(rèn)為節(jié)點(diǎn)是自私的，按照概率Thp丟棄來自該節(jié)點(diǎn)的路由包作為懲罰?！躎hi時(shí)，我們認(rèn)為該鄰居處于初始化階段，不對(duì)它進(jìn)行懲罰。考慮一個(gè)剛剛加入網(wǎng)絡(luò)的鄰居，==0，不能判定該鄰居是否自私，這時(shí)它的尋路包應(yīng)該得到中繼。為了減少誤判，同時(shí)提高算法的靈敏度，我們?cè)O(shè)置兩類門限：Thi和Tha、Ths。小概率的誤判對(duì)合作激勵(lì)機(jī)制的影響我們將在第3節(jié)討論。例如某一高速移動(dòng)的節(jié)點(diǎn)有大量的數(shù)據(jù)要發(fā)送，在此期間其他所有節(jié)點(diǎn)不需要尋路，這時(shí)，該節(jié)點(diǎn)的ξ將小于1。圖1 30節(jié)點(diǎn)和10節(jié)點(diǎn)場(chǎng)景中ξ的分布情況上述仿真結(jié)果證明了我們的觀察在均勻業(yè)務(wù)下是成立的?？梢钥闯?，兩個(gè)場(chǎng)景中ξ1的記錄所占百分比都非常小，10節(jié)點(diǎn)場(chǎng)景中約為6%，30節(jié)點(diǎn)場(chǎng)景中約為1%。為了排除初始階段不穩(wěn)定性的影響，我們