網(wǎng)絡(luò)尋路階段的合作激勵(lì)機(jī)制探討(doc 11頁(yè)).doc

Ad hoc網(wǎng)絡(luò)尋路階段的合作激勵(lì)機(jī)制研究黃蕾，劉立祥（中國(guó)科學(xué)院軟件研究所綜合信息系統(tǒng)技術(shù)國(guó)家級(jí)重點(diǎn)實(shí)驗(yàn)室，北京，100080）摘要：如何激勵(lì)屬于不同利益最大化實(shí)體的自私節(jié)點(diǎn)合作是當(dāng)前Ad hoc網(wǎng)絡(luò)研究中的一個(gè)熱點(diǎn)問(wèn)題?，F(xiàn)有的自私節(jié)點(diǎn)檢測(cè)和激勵(lì)機(jī)制主要針對(duì)數(shù)據(jù)傳輸階段，不能適應(yīng)尋路階段的特點(diǎn)。本文基于鄰居節(jié)點(diǎn)中繼和生成的路由請(qǐng)求包之間的統(tǒng)計(jì)關(guān)系，提出了一種適用于按需路由協(xié)議尋路階段的自私行為檢測(cè)和懲罰機(jī)制，并利用博弈論工具將其建模為噪聲環(huán)境下的重復(fù)囚徒困境博弈，對(duì)算法激勵(lì)合作的有效性進(jìn)行分析。理論分析和仿真結(jié)果顯示，本算法能夠有效地懲罰尋路中的自私行為，促進(jìn)節(jié)點(diǎn)合作。關(guān)鍵詞：Ad hoc網(wǎng)絡(luò)，路由，自私檢測(cè)，合作激勵(lì)，博弈論Study on cooperation stimulation mechanism in route discovery of ad hoc networksHuang Lei, Liu Lixiang(National Key Laboratory of Integrated Information System Technology, Institute of Software, Chinese Academy of Sciences, Beijing, 100080)Abstract: How to stimulate selfish nodes which belong to different utility-maximizing entities to cooperate is a hot topic in ad hoc network research community. Current mechanisms proposed so far focus mainly on detecting selfish behavior and stimulating cooperation in data forwarding stage. They are not applicable in route discovery stage. Based on statistics relationship of route request packets relayed and generated by a neighbor node, this paper proposed an algorithm to detect and punish the selfishness in route discovery stage for on-demand routing protocols. The algorithm was modeled with the tool of game theory as the repeated prisoner dilemma in noisy environment, and its effectiveness to stimulate cooperation was analyzed with the model. Theoretic analysis and simulation results showed that our scheme could punish the selfishness in route discovery effectively and thus stimulate nodes to cooperate.Keyword: Ad hoc network, routing, selfishness detection, cooperation stimulation, game theory1 引言Ad hoc網(wǎng)絡(luò)由一組移動(dòng)或固定的無(wú)線(xiàn)節(jié)點(diǎn)組成，信息交流等網(wǎng)絡(luò)關(guān)鍵任務(wù)的實(shí)現(xiàn)需要各節(jié)點(diǎn)之間的相互協(xié)作，這種合作性也是現(xiàn)有諸多路由協(xié)議設(shè)計(jì)的一個(gè)基本假設(shè)前提。但是當(dāng)節(jié)點(diǎn)屬于不同實(shí)體時(shí)，其合作性缺乏內(nèi)在的保證，理性節(jié)點(diǎn)更傾向于采取能夠使得自身利益最大化的行動(dòng)，而不是完全遵從協(xié)議。由于無(wú)線(xiàn)傳輸需要耗費(fèi)大量的能量，因此理性的自私節(jié)點(diǎn)會(huì)盡量避免為其他節(jié)點(diǎn)中繼數(shù)據(jù)，從而導(dǎo)致網(wǎng)絡(luò)性能下降，合作用戶(hù)利益受損。Ad hoc網(wǎng)絡(luò)中自私節(jié)點(diǎn)的激勵(lì)機(jī)制是當(dāng)前的一個(gè)研究熱點(diǎn)，提出的解決方案可分為三種類(lèi)型1：基于信用的方法（credit-based method），基于聲譽(yù)的方法（reputation-based method），和博弈論方法（game theory method）?；谛庞玫姆椒ㄒ话憬⒃谔摂M貨幣機(jī)制的基礎(chǔ)上，通過(guò)精心設(shè)計(jì)的支付方式，使得節(jié)點(diǎn)只有在合作的時(shí)候才能使自己的利益最大化2-4。這種方法的缺陷在于作為其基礎(chǔ)的虛擬貨幣管理系統(tǒng)，或者需要抗篡改硬件的支持2，或者需要集中的支付服務(wù)4，尚未有令人滿(mǎn)意的解決方案；基于聲譽(yù)的方法記錄節(jié)點(diǎn)的過(guò)往行為，綜合直接觀察結(jié)果和第三方信息形成對(duì)節(jié)點(diǎn)合作性的判斷，對(duì)不合作的自私節(jié)點(diǎn)以拒絕服務(wù)的方式進(jìn)行懲罰，從而達(dá)到促進(jìn)合作的目的5-8。目前聲譽(yù)系統(tǒng)采用基于Watchdog8的隱式響應(yīng)或基于ACK的顯式響應(yīng)作為監(jiān)測(cè)的主要方式，19-10等文獻(xiàn)指出現(xiàn)有監(jiān)測(cè)機(jī)制的不準(zhǔn)確性是聲譽(yù)系統(tǒng)應(yīng)用的主要障礙；博弈激勵(lì)機(jī)制大多建立在 “針?shù)h相對(duì)（TFT）”策略及其變種的基礎(chǔ)上，目前提出的方案多是各節(jié)點(diǎn)根據(jù)自己數(shù)據(jù)傳輸?shù)某晒β蕘?lái)調(diào)整為網(wǎng)絡(luò)中其它節(jié)點(diǎn)中繼分組的概率11-13。這類(lèi)文獻(xiàn)重在納什均衡的證明，使用了較強(qiáng)的假設(shè)條件，距離實(shí)際應(yīng)用尚有一段距離。上述文獻(xiàn)提出的激勵(lì)機(jī)制大多是針對(duì)數(shù)據(jù)傳輸階段節(jié)點(diǎn)的自私行為而設(shè)計(jì)的，一個(gè)基本假設(shè)是節(jié)點(diǎn)在路由發(fā)現(xiàn)階段采取合作策略，而只在數(shù)據(jù)傳輸階段自私丟包581113，顯然這個(gè)假設(shè)不盡合理。對(duì)于Ad hoc網(wǎng)絡(luò)中通常采用的按需路由來(lái)說(shuō)，節(jié)點(diǎn)在尋路階段的自私行為可以使它免于后續(xù)的數(shù)據(jù)中繼任務(wù)，“合法”的節(jié)省更多的能量，因此節(jié)點(diǎn)傾向于在尋路階段采用自私策略，我們必須考慮相應(yīng)的檢測(cè)和合作激勵(lì)機(jī)制。尋路階段的自私行為可以分為兩大類(lèi)型：l 主動(dòng)篡改路由控制包。當(dāng)自私節(jié)點(diǎn)接收到RREQ（路由請(qǐng)求）、RREP（路由響應(yīng)）等控制包時(shí)，它改變其中一些關(guān)鍵域如AODV中的跳數(shù)、DSR中的中間節(jié)點(diǎn)列表，從而使自己避免出現(xiàn)在源和目的均為其他節(jié)點(diǎn)的路徑上，逃避中繼任務(wù)。這類(lèi)自私行為的應(yīng)對(duì)方式已經(jīng)被廣泛研究714。l 被動(dòng)丟棄。自私節(jié)點(diǎn)丟棄所接收到路由控制包，避免成為中繼節(jié)點(diǎn)。兩種類(lèi)型的路由控制包中，RREP的性質(zhì)與數(shù)據(jù)包類(lèi)似，可采用Watchdog機(jī)制檢測(cè)自私丟棄行為。但是RREQ包為廣播包，而且它的傳輸是有條件的，存在大量合法丟包，因此Watchdog機(jī)制不能有效檢測(cè)被動(dòng)丟棄RREQ包的自私行為。目前尚未有應(yīng)對(duì)這類(lèi)自私行為的有效方式。本文主要研究RREQ丟棄的檢測(cè)、懲罰和激勵(lì)機(jī)制，因此后續(xù)章節(jié)所提及的自私行為將主要指RREQ的被動(dòng)丟棄。雖然RREQ的有條件傳輸和鄰居集的不確定性使得基于單個(gè)包檢測(cè)的Watchdog機(jī)制失效，但是，由于每一個(gè)RREQ都會(huì)被接收到的節(jié)點(diǎn)再次廣播直到該節(jié)點(diǎn)擁有到目的節(jié)點(diǎn)的路徑或者TTL超時(shí)，因此從統(tǒng)計(jì)角度來(lái)看，合作節(jié)點(diǎn)中繼的RREQ與返回的RREP之和應(yīng)該遠(yuǎn)大于自身所生成的RREQ數(shù)。這一點(diǎn)可作為檢測(cè)被動(dòng)丟棄的基礎(chǔ)。本文提出一種被動(dòng)丟棄行為的檢測(cè)和激勵(lì)機(jī)制，基本思想是節(jié)點(diǎn)監(jiān)測(cè)過(guò)去一段時(shí)間內(nèi)的鄰居中繼和生成的RREQ數(shù)量，如果兩者比率超過(guò)一定門(mén)限，則認(rèn)為鄰居是合作節(jié)點(diǎn)，否則認(rèn)為鄰居是自私節(jié)點(diǎn)。節(jié)點(diǎn)以一定的概率丟棄來(lái)自自私節(jié)點(diǎn)的包，作為對(duì)自私行為的懲罰，從而激勵(lì)合作。由于Ad hoc網(wǎng)絡(luò)中節(jié)點(diǎn)移動(dòng)模型、業(yè)務(wù)模型、通信模型等均不相同，包括Watchdog在內(nèi)的各種檢測(cè)算法都不可避免的存在一定的誤判率，我們的算法也不能例外。我們建立簡(jiǎn)化的博弈模型對(duì)算法進(jìn)行分析，研究誤判率對(duì)合作激勵(lì)的有效范圍的影響。分析結(jié)果表明，即使存在一定的誤判率，本文算法也能夠激勵(lì)節(jié)點(diǎn)達(dá)成合作。最后我們通過(guò)仿真對(duì)算法進(jìn)行驗(yàn)證，仿真結(jié)果表明本文算法能夠?qū)ψ运焦?jié)點(diǎn)進(jìn)行有效的懲罰，從而激勵(lì)合作。 2 節(jié)點(diǎn)尋路階段自私行為的檢測(cè)和懲罰算法2.1 基本思想本算法的出發(fā)點(diǎn)來(lái)自于這樣一個(gè)觀察：由于RREQ的廣播本質(zhì)，對(duì)于業(yè)務(wù)量較均勻的網(wǎng)絡(luò)來(lái)說(shuō)，從統(tǒng)計(jì)上來(lái)看，合作節(jié)點(diǎn)自身所生成RREQ數(shù)應(yīng)小于其中繼的RREQ數(shù)和響應(yīng)的RREP數(shù)之和。在Ad hoc按需路由中，節(jié)點(diǎn)接收到RREQ后是否繼續(xù)廣播與RREQ的內(nèi)容以及本地路由表有關(guān)。例如，如果節(jié)點(diǎn)曾經(jīng)接收過(guò)該RREQ，那么這個(gè)包將被丟棄；如果節(jié)點(diǎn)具有到目的地的路徑，這個(gè)包也不再前傳，而是生成RREP返回源節(jié)點(diǎn)。因此，一個(gè)節(jié)點(diǎn)自私與否無(wú)法逐包來(lái)判斷。但是，對(duì)按需路由協(xié)議來(lái)說(shuō)，當(dāng)節(jié)點(diǎn)有數(shù)據(jù)要發(fā)送且沒(méi)有可用路由的時(shí)候，必須首先通過(guò)RREQ/RREP來(lái)建立數(shù)據(jù)傳輸路徑。這里的RREQ既可以是節(jié)點(diǎn)自己生成的，也可以是中繼其他節(jié)點(diǎn)的。由于Ad hoc按需路由協(xié)議中的尋路都是通過(guò)廣播實(shí)現(xiàn)的，因此節(jié)點(diǎn)中繼的RREQ數(shù)與響應(yīng)的RREP數(shù)之和應(yīng)大于它自身生成的RREQ數(shù)。后續(xù)章節(jié)中我們將只考慮相應(yīng)的RREQ數(shù)量，這是因?yàn)槌斯?jié)點(diǎn)數(shù)極少的網(wǎng)絡(luò)外，RREQ的數(shù)量將遠(yuǎn)大于RREP。我們通過(guò)仿真來(lái)驗(yàn)證這個(gè)觀察。仿真建立在NS2的平臺(tái)上。在1000m*1000m的區(qū)域內(nèi)分別隨機(jī)拋灑30和10 個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)位置服從均勻分布。每個(gè)節(jié)點(diǎn)從剩余節(jié)點(diǎn)中隨機(jī)選擇其目的地，每一源-目的對(duì)建立一個(gè)CBR流，包長(zhǎng)度為512字節(jié)，兩包之間間隔為1s。采用Random Way Point的隨機(jī)移動(dòng)模型。這種模型中，節(jié)點(diǎn)隨機(jī)移動(dòng)到某一位置后停頓一段時(shí)間再開(kāi)始新的移動(dòng)。設(shè)節(jié)點(diǎn)的移動(dòng)速度在1m/s到10m/s之間均勻分布，停頓時(shí)間在10s和50s之間均勻分布。傳輸模型為T(mén)woRayGround，節(jié)點(diǎn)通信半徑約為250m。采用DSR作為路由協(xié)議。仿真持續(xù)1000秒。在每個(gè)節(jié)點(diǎn)的路由agent中設(shè)置一張表，記錄過(guò)去200秒內(nèi)收到的鄰居自己生成的RREQ（REQs）和中繼的RREQ（REQr）的數(shù)量以及兩者的比值=REQr/REQs。為了排除初始階段不穩(wěn)定性的影響，我們的統(tǒng)計(jì)范圍為REQs1的那些記錄。30和10節(jié)點(diǎn)場(chǎng)景下的分布如圖1所示。可以看出，兩個(gè)場(chǎng)景中Th_i) ratio= RSrc.REQ_r/ RSrc.REQ_s if(ratioTh_a& Random:uniform(0,1) Th_i) ratio= DSrc.REQ_r/ DSrc.REQ_s if(ratio Th_s& Random:uniform(0,1) Tha，該包得到正常處理，如果Tha，以概率Thp丟包。當(dāng)節(jié)點(diǎn)收到數(shù)據(jù)包DATA的時(shí)候，判斷其源節(jié)點(diǎn)的，如果Ths，以概率Thp丟棄。為了避免被檢測(cè)出來(lái)，自私節(jié)點(diǎn)可能采取兩種規(guī)避措施：1， 更改尋路包的源地址選項(xiàng)，使得該RREQ看起來(lái)是由該鄰居節(jié)點(diǎn)中繼的，從而欺騙檢測(cè)機(jī)制。2，變更自己的身份，如采用sybil 攻擊15。這時(shí)，由于鄰居身份是虛假的，檢測(cè)機(jī)制不能有效發(fā)揮作用。第一個(gè)問(wèn)題在可采用7中應(yīng)對(duì)主動(dòng)篡改攻擊的方式來(lái)解決。在公鑰管理系統(tǒng)的支持下，當(dāng)節(jié)點(diǎn)發(fā)送RREQ時(shí)，必須利用自己的私鑰對(duì)其進(jìn)行簽名。鄰居以及中間節(jié)點(diǎn)可以對(duì)RREQ包的發(fā)起方身份進(jìn)行驗(yàn)證。如果驗(yàn)證失敗的話(huà)，丟棄該包。這樣自私節(jié)點(diǎn)不能改動(dòng)尋路包的源地址項(xiàng)，從而解決了第一個(gè)問(wèn)題。Sybil攻擊是基于聲譽(yù)的系統(tǒng)共同面對(duì)的一個(gè)問(wèn)題。15對(duì)此進(jìn)行了深入的研究，并提出了多種解決方案，如無(wú)線(xiàn)資源檢測(cè)，密鑰驗(yàn)證等等。這些方法的思路可用來(lái)解決第二個(gè)問(wèn)題。例如，可采用基于密鑰預(yù)分配15或者基于公鑰的身份認(rèn)證體系16來(lái)保證節(jié)點(diǎn)身份的真實(shí)性。這些方法在文獻(xiàn)中都已經(jīng)進(jìn)行了深入的研究，本文不再進(jìn)行詳細(xì)討論。3 算法分析算法的表現(xiàn)與Thi、Tha、Ths和Thp四個(gè)參數(shù)密切相關(guān)，其中Thi、Tha、Ths確定了檢測(cè)的誤判率， Thp決定了算法的懲罰力度。這里所說(shuō)的誤判率不僅是指把合作節(jié)點(diǎn)誤判為自私節(jié)點(diǎn)的概率，也包括把自私節(jié)點(diǎn)誤判為合作節(jié)點(diǎn)的概率，即通常意義上的敏感度。由于網(wǎng)絡(luò)情況千變?nèi)f化，不論Thi、Tha、Ths取什么值，靜態(tài)設(shè)定或者動(dòng)態(tài)變化，都可能存在誤判。本節(jié)利用博弈論的工具對(duì)算法在一定誤判率情況下合作激勵(lì)的有效性進(jìn)行分析。3.1 系統(tǒng)建模我們用隨機(jī)配對(duì)重復(fù)博弈來(lái)對(duì)網(wǎng)絡(luò)的尋路過(guò)程進(jìn)行抽象。所謂隨機(jī)配對(duì)博弈，即隨機(jī)選擇相互作用的兩個(gè)節(jié)點(diǎn)，它們均需要對(duì)方作為中繼才能到達(dá)各自的目的地。為了分析的方便，我們把時(shí)間軸劃分為離散的時(shí)槽。假設(shè)一個(gè)時(shí)槽內(nèi)網(wǎng)絡(luò)拓?fù)浔３植蛔?，時(shí)槽之間拓?fù)潆S機(jī)變化。每時(shí)槽內(nèi)兩節(jié)點(diǎn)均進(jìn)行一次尋路和數(shù)據(jù)傳輸過(guò)程。節(jié)點(diǎn)可以選擇自私丟包或者合作中繼的策略。如果對(duì)方選擇中繼，則源節(jié)點(diǎn)可獲得單位的收益。兩節(jié)點(diǎn)數(shù)據(jù)傳輸?shù)拈_(kāi)銷(xiāo)均為單位。一般來(lái)說(shuō)，應(yīng)遠(yuǎn)大于 。每時(shí)槽內(nèi)兩個(gè)節(jié)點(diǎn)的交互可建模為一次階段博弈。用Ai=合作（C），自私（D）來(lái)表示i節(jié)點(diǎn)的可選行動(dòng)。a來(lái)表示博弈的兩個(gè)節(jié)點(diǎn)的行動(dòng)組合，其中 ai是i節(jié)點(diǎn)的行動(dòng)，a-i是除i節(jié)點(diǎn)外其他節(jié)點(diǎn)的行動(dòng)。ui來(lái)表示節(jié)點(diǎn)i在階段博弈中獲得的支付，則階段博弈的支付矩陣為：表1：階段博弈的支付矩陣合作（C）自私（D）合作（C）（-2，-2）（- 2，-）自私（D）（-，-2）（-，-）可以看出階段博弈的局勢(shì)是一個(gè)典型的囚徒困境，其納什均衡是（自私，自私），也就是說(shuō)靜態(tài)策略是無(wú)法促成合作的。把本文的算法建模為下述動(dòng)態(tài)策略：其中為對(duì)手行為的誤判率，為檢測(cè)到的對(duì)手的行為，a為對(duì)手真正的行為。盡管在實(shí)際應(yīng)用中，這兩個(gè)概率是不同的，并且隨時(shí)間變化，但為了分析的方便，我們假設(shè)兩者相同且不隨時(shí)間變化，均為，粗略的反應(yīng)了本文算法中Thi、Tha、Ths的影響。f函數(shù)對(duì)應(yīng)著節(jié)點(diǎn)根據(jù)過(guò)往信息決定當(dāng)前行為的方式：如果檢測(cè)出對(duì)方自私的話(huà)，本節(jié)點(diǎn)以概率p丟棄對(duì)方的包，p反應(yīng)了本文算法中Thp的影響。行為策略的整體收益通過(guò)貼現(xiàn)平均準(zhǔn)則來(lái)計(jì)算：其中貼現(xiàn)因子0 Ui（D，*）(3)*為C或者D。我們對(duì)，p等參數(shù)取不同的值，以觀察策略促成合作的有效范圍。*與各參數(shù)之間的關(guān)系如圖2所示。圖2 合作范圍與，p的關(guān)系從圖2中我們可以觀察不同參數(shù)對(duì)合作范圍的影響：l *隨著，的比率的增大而降低，其原因是數(shù)據(jù)成功傳輸所獲得的收益越大，節(jié)點(diǎn)就越傾向于合作。l *隨著p的增加而降低，其原因可解釋為懲罰越嚴(yán)厲，節(jié)點(diǎn)偏離既有策略所獲得的收益越小，節(jié)點(diǎn)越傾向于合作l *隨著的增加而增加，當(dāng)=0.5時(shí)，不論其他參數(shù)為何值，節(jié)點(diǎn)均不能達(dá)成相互合作。其原因是，誤判率越大，節(jié)點(diǎn)所獲得的對(duì)手的信息越少，就越傾向于采用安全的自私策略以保證自身利益的最大化。可以看出，當(dāng)較小，p較大時(shí)，不等式（3）對(duì)于大部分值均成立，系統(tǒng)達(dá)到合作的均衡狀態(tài)。這說(shuō)明本算法可有效實(shí)現(xiàn)合作激勵(lì)的功能。4 仿真驗(yàn)證 我們?nèi)圆捎?節(jié)中的30節(jié)點(diǎn)仿真場(chǎng)景對(duì)算法進(jìn)行仿真驗(yàn)證。算法參數(shù)選擇為T(mén)hi=1，Tha=4，Ths=1和Thp=1。節(jié)點(diǎn)的初始能量為5，發(fā)送和接收能量配置分別為0.1和0.025，仿真時(shí)間設(shè)為2000秒。首先我們考察不同自私節(jié)點(diǎn)數(shù)時(shí)算法的表現(xiàn)。設(shè)置三種場(chǎng)景，基線(xiàn)場(chǎng)景：所有節(jié)點(diǎn)均合作；場(chǎng)景1：自私節(jié)點(diǎn)丟棄RREQ包，但是沒(méi)有啟用本文算法；場(chǎng)景2：自私節(jié)點(diǎn)丟棄RREQ，但是合作節(jié)點(diǎn)啟用了本文算法。各場(chǎng)景分別設(shè)3、6、9、12、15個(gè)節(jié)點(diǎn)為自私節(jié)點(diǎn)。對(duì)比自私節(jié)點(diǎn)和合作節(jié)點(diǎn)在不同場(chǎng)景下的吞吐量，如下圖所示：圖3 不同場(chǎng)景下吞吐量與自私節(jié)點(diǎn)數(shù)目關(guān)系首先觀察自私節(jié)點(diǎn)吞吐量的變化規(guī)律。對(duì)比基線(xiàn)場(chǎng)景和場(chǎng)景1的吞吐量變化，可以看出，節(jié)點(diǎn)自私丟棄RREQ，逃避中繼任務(wù)，節(jié)省了能量，從而使得自己的吞吐量上升。場(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ì)。合作節(jié)點(diǎn)的吞吐量變化規(guī)律與此相反。自私節(jié)點(diǎn)丟棄RREQ包使得合作節(jié)點(diǎn)需要花費(fèi)更多的能量中繼包，導(dǎo)致自己的吞吐量下降。算法啟用后，合作節(jié)點(diǎn)不再中繼自私節(jié)點(diǎn)的包，從而可以節(jié)省能量用于中繼合法包。自私節(jié)點(diǎn)數(shù)目越多，節(jié)省的能量越多，吞吐量提高的幅度就越明顯。下面我們考慮本文算法對(duì)選擇性丟包的應(yīng)對(duì)能力。設(shè)自私節(jié)點(diǎn)數(shù)目為6，即20% 的節(jié)點(diǎn)自私丟包，丟包概率分別為50%、60%直到100%。兩種類(lèi)型的節(jié)點(diǎn)在不同場(chǎng)景下的平均吞吐量如表2所示：表2：不同場(chǎng)景下不同類(lèi)型節(jié)點(diǎn)的平均吞吐量自私節(jié)點(diǎn)丟包概率場(chǎng)景1：不采用本文算法場(chǎng)景2：采用本文算法合作節(jié)點(diǎn)平均吞吐量(包)自私節(jié)點(diǎn)平均吞吐量(包)合作節(jié)點(diǎn)平均吞吐量(包)自私節(jié)點(diǎn)平均吞吐量(包)100%342.625388.833383.708257.590%350.917330.833374.125294.66780%344.5321.833362.16731870%343.75314.667362.333333.16760%348.167325360.042339.550%344.375315.333363.25348.50（合作狀態(tài)）354.708316.667360348.833從上表可以看出，在合作狀態(tài)，本文算法并不會(huì)給網(wǎng)絡(luò)性能帶來(lái)負(fù)面影響。在場(chǎng)景1本文算法沒(méi)有啟用的時(shí)候，自私節(jié)點(diǎn)只有在丟包率較高（80%）時(shí)，吞吐量才能得到顯著的增加。場(chǎng)景2中合作節(jié)點(diǎn)啟用本文算法之后，丟包率越大，遭受的懲罰力度越大，自私節(jié)點(diǎn)的吞吐量越小。當(dāng)丟包率大于80%時(shí)，其吞吐量遠(yuǎn)小于合作狀態(tài)的348.833，因此本文算法激活后，理性節(jié)點(diǎn)將選擇合作而不是自私丟包，從而實(shí)現(xiàn)對(duì)自私節(jié)點(diǎn)的激勵(lì)。5 相關(guān)工作 8是Ad hoc網(wǎng)絡(luò)自私行為檢測(cè)和激勵(lì)領(lǐng)域的開(kāi)創(chuàng)性文獻(xiàn)。8關(guān)注的是數(shù)據(jù)傳輸階段的自私丟包問(wèn)題，并提出了后續(xù)文獻(xiàn)中廣泛應(yīng)用的Watchdog檢測(cè)方案。 Watchdog建立在DSR的基礎(chǔ)上，并設(shè)定節(jié)點(diǎn)工作在混雜偵聽(tīng)模式下。節(jié)點(diǎn)發(fā)包之后，偵聽(tīng)下一跳節(jié)點(diǎn)的通信。如果在設(shè)定時(shí)間內(nèi)，沒(méi)有聽(tīng)到該包被繼續(xù)傳送到路徑上的下一節(jié)點(diǎn)，那么認(rèn)為下一跳節(jié)點(diǎn)自私丟包。當(dāng)節(jié)點(diǎn)檢測(cè)到其下一跳自私丟包的比率超過(guò)一定門(mén)限時(shí)，它將通知源節(jié)點(diǎn)。源節(jié)點(diǎn)中的Pathrater部件在選擇路徑時(shí)，避開(kāi)丟包的自私節(jié)點(diǎn)。從Watchdog的機(jī)理中可以看出它并不適合于尋路階段RREQ的丟包檢測(cè)；首先，RREQ是廣播包，鏈路層不提供應(yīng)答，因此節(jié)點(diǎn)不能確定此時(shí)鄰居域內(nèi)哪些節(jié)點(diǎn)接收到RREQ，哪些沒(méi)有。不能確定需要監(jiān)測(cè)的節(jié)點(diǎn)，也就無(wú)法對(duì)節(jié)點(diǎn)是否中繼RREQ包做出判斷。其次，由于一個(gè)RREQ可能被多個(gè)節(jié)點(diǎn)廣播，因此為了降低尋路開(kāi)銷(xiāo)，節(jié)點(diǎn)對(duì)同一個(gè)RREQ只作一次響應(yīng)，后續(xù)收到的重復(fù)RREQ將被丟棄，因此存在大量合法丟包。這兩個(gè)方面使得Watchdog無(wú)法用于尋路階段自私丟包的檢測(cè)。19提出了一種基于ACK的自私丟包檢測(cè)方式2ACK，其核心思想是傳輸路徑上的節(jié)點(diǎn)接收到數(shù)據(jù)包后返回ACK給兩跳前的節(jié)點(diǎn)，從而可以對(duì)中間節(jié)點(diǎn)的傳輸行為進(jìn)行判定。2ACK方法也建立在DSR的基礎(chǔ)上。尋路過(guò)程忠節(jié)點(diǎn)鄰居集未知、存在合法丟包的特點(diǎn)同樣使得2ACK不能正常發(fā)揮作用：盡管節(jié)點(diǎn)收到下兩跳的ACK時(shí)能夠確定下一跳節(jié)點(diǎn)是合作的；但是沒(méi)有收到ACK時(shí)，卻不能判定下一跳自私丟包。因此這種方式也不能用于尋路過(guò)程中。20提出一種基于虛擬支付的緊湊激勵(lì)機(jī)制來(lái)促使節(jié)點(diǎn)在尋路階段合作。收到RREQ后再次廣播的節(jié)點(diǎn)可以得到小額的支付，對(duì)最終構(gòu)成源目的路徑的節(jié)點(diǎn)則可以獲得大額支付。參與路由越多的節(jié)點(diǎn)獲得的支付越多，從而使節(jié)點(diǎn)愿意合作。但是20中只是簡(jiǎn)單的描述了這種思想，對(duì)于支付如何實(shí)現(xiàn)、支付的數(shù)量等細(xì)節(jié)問(wèn)題均缺乏進(jìn)一步的說(shuō)明。6 結(jié)論對(duì)于采用按需路由的Ad hoc網(wǎng)絡(luò)來(lái)說(shuō)，自私節(jié)點(diǎn)丟棄尋路包從而合法逃避為其他節(jié)點(diǎn)中繼數(shù)據(jù)的責(zé)任是節(jié)約自己能量的最好方式。由于路由控制包的有條件中繼模式和鄰居的不確定性，這類(lèi)自私方式很難通過(guò)傳統(tǒng)的Watchdog或基于ACK的方式來(lái)檢測(cè)。本文基于尋路包的統(tǒng)計(jì)特性，提出了一種被動(dòng)丟棄尋路包的行為檢測(cè)和懲罰算法，使得自私節(jié)點(diǎn)的收益大幅度下降。本文建立博弈模型對(duì)算法的有效性進(jìn)行分析，結(jié)果表明即使存在一定的誤判率，我們的算法仍能夠促使節(jié)點(diǎn)達(dá)成合作。仿真結(jié)果同樣也證明了我們的算法能夠有效懲罰自私節(jié)點(diǎn)，從而激勵(lì)節(jié)點(diǎn)合作。參考文獻(xiàn)1. Yoo Y., Agrawal D. P., Why does it pay to be selfish in a MANET? IEEE Wireless Communications, 2006, 13(6): 87-972. Buttyan L., Hubaux J.-P., Stimulating cooperation in self-organizing mobile ad hoc networks, Mobile Networks and Applications, 2003, 8(5): 579-5923. Wang W., EideNBenz S., Wang Y., Li X.-Y., OURS: Optimal unicast routing systems in non-cooperative wireless networks, Proceeding of the Annual International Conference on Mobile Computing and Networking(MOBICOM),Los Angeles: ACM Press,2006, 402-4134. Zhong S., Chen J., Yang R., Sprite: A simple, cheat-proof, credit-based system for mobile ad-hoc networks, Proceedings of INFOCOM, San Francisco: IEEE Press, 2003, 1987-19975. Buchegger S., Boudec J.-Y. L., Performance analysis of the CONFIDANT protocol cooperation of nodes fairness in dynamic ad hoc networks, Source: Proceedings of the International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), Lausanne: ACM Press, 2002, 226-2366. Buchegger S., Boudec J.-Y. L., Self-policing mobile ad hoc networks by reputation systems, IEEE Communications Magazine，2005, 43(7):101-1077. He Q., Wu D., Khosl P., A secure incentive architecture for ad-hoc networks, Wireless Communications and Mobile Computing, 2006, 6(3):333-3468. Marti S., Giuli T.J., Lai K. Baker M., Mitigating routing misbehavior in mobile ad hoc networks, Proceedings of the Annual International Conference on Mobile Computing and Networking(MOBICOM), Boston: ACM Press, 2000,255-2659. Huang E., Crowcroft J., Wassell I., Rethinking incentives for mobile ad hoc networks, Proceedings of the ACM SIGCOMM 2004 Workshops, Portland: ACM Press, 2004, 191-196 10. Carruthers R., Nikolaidis I., Certain limitations of reputationbased schemes in mobile environments, Proceedings of the Eighth ACM Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems, Montreal: ACM Press, 2005, 2-1111. Srinivasan V., Nuggehalli P., Chiasserini C. F., Rao R. R., Cooperation in wireless ad hoc networks, Proceedings of INFOCOM, San Francisco: IEEE Press, 2003, 808-81712. Milan F., Jaramillo J. J., Srikant R., Achieving cooperation in multihop wireless networks of selfish nodes, Proceedings of ACM workshop on Game theory for communications and networks, Pisa: ACM Press, 2006 13. Felegyhazi M., Buttyan L., Nash equilibrium of packet forwarding strategies in wireless ad hoc networks, IEEE Transactions on Mobile Computing, 2006, 5(5):463-47514. Zapata M.-G., Asokan N. , Securing ad hoc routing protocols, Proceedings of the 3rd Workshop on Wireless Security, New York: ACM Press, 2002, 1-1015. Newsome J., Shi E., Song D., Perrig A., The Sybil attack in sensor networks: analysis and defenses, Proceedings of International Symposium on Information Processing in Sensor Networks(IPSN), New York: ACM Press, 2004, 259-26816. Li R.-D., Li J., Liu P., Chen H.-H., On-demand public-key management for mobile Ad hoc networks, Wireless Communications and Mobile Computing, 2006, 6(3): 295-30617. Urpi A., Bonuccelli M., Giordano S., Modeling cooperation in mobile ad hoc networks: a formal description of selfishness, Proceedings of Modeling and Optimization in Mobile, Ad hoc and Wireless Networks, Sophia-Antipolis: IEEE Press, 200318. Myerson R. B., Game Theory, Analysis of Conflict, Chinese Economy Press, 200119. Liu K., Deng J., Varshney P. K., Balakrishnan K., An acknowledgment-based approach for the detection of routing misbehavior in MANETs, IEEE Transactions on Mobile Computing, 2007, 6(5): 488-50120. Zhu H.-F, Bao F., Li T.-Y., Compact stimulation mechanism for routing discovery protocols in civilian ad hoc networks, Proceeding of IFIP International Federation for Information Processing, 2005, LNCS 3677: 200-209 黃蕾，女，1972年生，博士研究生，高工，研究方向包括ad hoc網(wǎng)絡(luò)合作激勵(lì)，衛(wèi)星網(wǎng)絡(luò)擁塞控制等Huang Lei, born in 1972, Ph.D. candidate，senior engineer. Her research interests include cooperation stimulation in ad hoc networks, congestion control in satellite network, etc.劉立祥，男，1973年生，博士，副研究員，研究方向包括ad hoc網(wǎng)絡(luò)、衛(wèi)星網(wǎng)絡(luò)路由協(xié)議、新型網(wǎng)絡(luò)體系結(jié)構(gòu)、網(wǎng)絡(luò)控制等Liu Lixiang, born in 1973, Ph.D.，associate researcher. His research interests include ad hoc network, routing protocol in satellite network,