譚冕 戴昊峰 張暉 宋波

摘要：在ad hoc網(wǎng)絡(luò)中，節(jié)點(diǎn)間的合作是一個重要的問題，不相鄰節(jié)點(diǎn)的信息傳遞只能依靠中間節(jié)點(diǎn)的轉(zhuǎn)發(fā)來完成，若中間節(jié)點(diǎn)存在自私行為則會較大地影響網(wǎng)絡(luò)的性能。節(jié)點(diǎn)自私類型有不同，對網(wǎng)絡(luò)功能造成的影響也各不一樣，有些自私節(jié)點(diǎn)在一定數(shù)量上對網(wǎng)絡(luò)整體性能影響不大，可以容忍；而有些自私節(jié)點(diǎn)則必須得采取強(qiáng)硬的懲戒措施，將其驅(qū)逐出網(wǎng)絡(luò)或降低它的信譽(yù)值并公布。該文采用基于信譽(yù)值的算法檢測出ad hoc網(wǎng)絡(luò)中的問題節(jié)點(diǎn)，并對其進(jìn)行類型定義，仿真查看其對網(wǎng)絡(luò)性能的影響，方便下一步根據(jù)不同自私節(jié)點(diǎn)進(jìn)行機(jī)制設(shè)計。

關(guān)鍵詞： ad hoc網(wǎng)絡(luò)；信譽(yù)值；節(jié)點(diǎn)自私類型

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2014）28-6622-05

隨著軍事技術(shù)的不斷發(fā)展，新型武器、作戰(zhàn)手段和作戰(zhàn)理論等不斷涌現(xiàn)。如何將眾多武器設(shè)備之間相連和與指揮機(jī)構(gòu)相連，以及對戰(zhàn)場信息是否能夠準(zhǔn)確、有效地進(jìn)行交流，是未來戰(zhàn)爭輸贏的關(guān)鍵因素。因此，戰(zhàn)場情景下的組網(wǎng)技術(shù)研究成為各國軍隊研究與發(fā)展的重點(diǎn)。無線ad hoc網(wǎng)絡(luò)正是在這種趨勢下產(chǎn)生的。Ad hoc網(wǎng)絡(luò)是分布式的，沒有中心控制節(jié)點(diǎn)，因此節(jié)點(diǎn)與它覆蓋范圍外的節(jié)點(diǎn)想要完成通信，就必須通過中繼節(jié)點(diǎn)的轉(zhuǎn)發(fā)來實(shí)現(xiàn)[1]。節(jié)點(diǎn)在網(wǎng)絡(luò)有可能充當(dāng)三種身份：源節(jié)點(diǎn)、中繼節(jié)點(diǎn)和目的節(jié)點(diǎn)。在ad hoc網(wǎng)絡(luò)中每個正常節(jié)點(diǎn)的能量、存儲空間、處理能力、傳輸帶寬都是有限的，假設(shè)它們都是理性的，在考慮轉(zhuǎn)發(fā)任務(wù)的時候，尤其是當(dāng)有單個節(jié)點(diǎn)的損耗和整個網(wǎng)絡(luò)能耗的沖突時，就會產(chǎn)生一定的自私性，所以參與路由服務(wù)，同時會根據(jù)自己能量的損耗來決定是否參加中繼轉(zhuǎn)發(fā)任務(wù)[2]。人們還發(fā)現(xiàn)在ad hoc網(wǎng)絡(luò)中還有惡意節(jié)點(diǎn)的存在，和其它善于偽裝成正常節(jié)點(diǎn)來參與路由的節(jié)點(diǎn)，這些都對ad hoc網(wǎng)絡(luò)造成一定威脅，因?yàn)樗鼈儠档途W(wǎng)絡(luò)吞吐量，增加丟包率等，嚴(yán)重的時候甚至?xí)?dǎo)致整個ad hoc網(wǎng)絡(luò)的崩潰[3]。

1 Ad hoc網(wǎng)絡(luò)節(jié)點(diǎn)自私行為研究

由于ad hoc網(wǎng)絡(luò)的合作需要通過節(jié)點(diǎn)來完成，故而網(wǎng)絡(luò)性能的好壞很大程度取決于節(jié)點(diǎn)的行為，而通常節(jié)點(diǎn)可分為兩種，一種是正常節(jié)點(diǎn)：具有較好的合作性，愿意無私地轉(zhuǎn)發(fā)數(shù)據(jù)；另一種是存在問題的不正常節(jié)點(diǎn)，它往往會對網(wǎng)絡(luò)性能造成一定的負(fù)面影響。

在本文中，存在問題的節(jié)點(diǎn)由于其具體自私行為不同，為方便表述，所以將問題節(jié)點(diǎn)分為惡意節(jié)點(diǎn)和兩種自私節(jié)點(diǎn)。惡意節(jié)點(diǎn)：通過路由，傳遞虛假的信息給目的節(jié)點(diǎn)。自私節(jié)點(diǎn)：第一類為只參加路由服務(wù)，但是卻從來不參加數(shù)據(jù)的轉(zhuǎn)發(fā)，以此盡可能的提高節(jié)點(diǎn)生存時間。第二類為受到自身的能量限制，所以會根據(jù)具體的能量消耗情況考慮是否參加網(wǎng)絡(luò)活動。

文獻(xiàn)[4]提出一種基于退避窗口問題的解決方法。在此種方法中，接受節(jié)點(diǎn)用CTS或ACK幀通過界定退避值，發(fā)送給源節(jié)點(diǎn)。同時，這種方法具有可擴(kuò)展性，可以用于ad hoc網(wǎng)絡(luò)檢測節(jié)點(diǎn)是否存在自私行為，并進(jìn)行數(shù)據(jù)分析。這種方法主要是將實(shí)際退避值、連續(xù)退避值等數(shù)據(jù)與某個門限值比較，以判斷節(jié)點(diǎn)是否更改退避窗口大小而取得高效益。

文獻(xiàn)[5]提出一種通過診斷機(jī)制和懲罰機(jī)制，并且以更改MAC協(xié)議，且在幀內(nèi)增加BOV數(shù)據(jù)，以此來判斷節(jié)點(diǎn)是否存在自私行為，并解決移動自組網(wǎng)中MAC層存在的節(jié)點(diǎn)自私行為問題。

在基于信譽(yù)的機(jī)制中，當(dāng)節(jié)點(diǎn)能夠正確地轉(zhuǎn)發(fā)數(shù)據(jù)包的時候，信譽(yù)值增加，如果節(jié)點(diǎn)信譽(yù)值比設(shè)定的門限值低時，就認(rèn)為該節(jié)點(diǎn)為自私節(jié)點(diǎn)。文獻(xiàn)[3]就提出了Watchdog和Pathrater模型，Watchdog的作用主要用于檢測節(jié)點(diǎn)是否存在不良行為。Watchdog通過偵聽下一條節(jié)點(diǎn)是否將數(shù)據(jù)包轉(zhuǎn)發(fā)出去，以此確定行為異常的節(jié)點(diǎn)，并提供給Pathrater。而Pathrater則在選擇路徑的時候盡可能地規(guī)避那些異常節(jié)點(diǎn)，從而找到較好的路徑。雖然它并沒有懲戒異常節(jié)點(diǎn)，但在一定程度也減輕了網(wǎng)絡(luò)負(fù)擔(dān)。在之后的信譽(yù)機(jī)制設(shè)計中，普遍采用了該算法的思路。

文獻(xiàn)[6]提出一種估算網(wǎng)絡(luò)發(fā)生碰撞的平均概率的檢測方法，并計算出幀經(jīng)過幾次重傳到最后的發(fā)送成功，此算法較上述算法更加復(fù)雜；而且在具體的ad hoc網(wǎng)絡(luò)中的捕獲效應(yīng)普遍存在，故它的實(shí)際應(yīng)用性并不高。

文獻(xiàn)[7]CONFIDANT機(jī)制是按需路由協(xié)議的擴(kuò)展，其目的是為了檢測并孤立那些有不良行為的問題節(jié)點(diǎn)，通過這樣來達(dá)到節(jié)點(diǎn)間的合作。此機(jī)制下每個節(jié)點(diǎn)都擁有四個模塊：檢測器、信任管理、聲譽(yù)系統(tǒng)及路徑管理。這四個模塊共同完成路由信息的提供和處理。

本文參考了Watchdog模型，采用AODV路由協(xié)議，通過偵聽鄰居節(jié)點(diǎn)的行為，并基于信譽(yù)值來檢測出問題節(jié)點(diǎn)，用“自私節(jié)點(diǎn)發(fā)送率”與信譽(yù)值共同判斷出其類型。最后仿真并查看各種類型的問題節(jié)點(diǎn)在“丟包率”、“網(wǎng)絡(luò)吞吐量”的數(shù)據(jù)上的表現(xiàn)，得出一些適用的結(jié)論。

2 系統(tǒng)模型

圖1為檢測并分類當(dāng)前ad hoc網(wǎng)絡(luò)存在的各種問題節(jié)點(diǎn)時生成的場景圖既模型圖。假設(shè)一個ad hoc網(wǎng)絡(luò)中，共存在100個節(jié)點(diǎn)，這100個節(jié)點(diǎn)隨機(jī)生成正常節(jié)點(diǎn)，自私節(jié)點(diǎn)類型一，自私節(jié)點(diǎn)類型二，惡意節(jié)點(diǎn)若干，記錄下各類節(jié)點(diǎn)的數(shù)目。圖2、圖3、圖4是在當(dāng)前網(wǎng)絡(luò)共存在100個節(jié)點(diǎn)，分別為惡意節(jié)點(diǎn)數(shù)為4、第一類自私節(jié)點(diǎn)數(shù)為6、第二類自私節(jié)點(diǎn)數(shù)為10的系統(tǒng)模型圖，也就是在實(shí)驗(yàn)過程中，隨著各種類型的問題節(jié)點(diǎn)數(shù)目的變化，系統(tǒng)都會生成相應(yīng)的模型既場景圖，可以看出這些問題節(jié)點(diǎn)是隨機(jī)生成并分布在當(dāng)前ad hoc網(wǎng)絡(luò)。在當(dāng)前圖1的場景圖中，隨機(jī)選定一個節(jié)點(diǎn)作為源節(jié)點(diǎn)，當(dāng)中繼節(jié)點(diǎn)為正常節(jié)點(diǎn)的時候，它會無條件的轉(zhuǎn)發(fā)該數(shù)據(jù)包；當(dāng)中繼節(jié)點(diǎn)是惡意節(jié)點(diǎn)的時候，它會接受這個數(shù)據(jù)包，但是會篡改其目的節(jié)點(diǎn)的位置，再將其發(fā)送出去；當(dāng)中繼節(jié)點(diǎn)是自私節(jié)點(diǎn)類型一的時候，它會接受這個數(shù)據(jù)包，但是會直接將其丟棄，以此來節(jié)約有限的能量，盡可能地提高自己的生存時間；當(dāng)中繼節(jié)點(diǎn)是自私類型二的時候，它會根據(jù)當(dāng)前剩余的能量來判斷是否轉(zhuǎn)發(fā)數(shù)據(jù)，如果當(dāng)前的能量大于門閥值，就會轉(zhuǎn)發(fā)該數(shù)據(jù)包，如果當(dāng)前的能量小于門閥值，它就會丟棄這個數(shù)據(jù)包。根據(jù)上面各種節(jié)點(diǎn)不同的表現(xiàn)，每當(dāng)該節(jié)點(diǎn)沒有轉(zhuǎn)發(fā)這個數(shù)據(jù)包，其信譽(yù)值就會在基礎(chǔ)值上面遞減，一旦信譽(yù)值在0值以下，就可以判斷其為問題節(jié)點(diǎn)。然后再根據(jù)各自類型的問題節(jié)點(diǎn)在具體行為上的不同，可以得到它們的自私節(jié)點(diǎn)發(fā)送率，再判斷出是哪種類型的問題節(jié)點(diǎn)。

3 自私類型檢測算法

算法共分兩個部分：一部分是要驗(yàn)證類型檢測是否正確，一部分是要知道丟包率、網(wǎng)絡(luò)吞吐量與各類問題在節(jié)點(diǎn)數(shù)目上的關(guān)系。

算法的檢測部分：隨機(jī)選定一個源節(jié)點(diǎn)a，探測并得到它的鄰居節(jié)點(diǎn)數(shù)目（節(jié)點(diǎn)的初始信譽(yù)值都為1） 。然后，源節(jié)點(diǎn)傳遞RREQ（路由請求）數(shù)據(jù)。若源節(jié)點(diǎn)的某一相鄰節(jié)點(diǎn)c無轉(zhuǎn)發(fā)，則c的信譽(yù)值相對于源節(jié)點(diǎn)a（-1） 。一個周期后，a再次發(fā)送RREQ數(shù)據(jù)，c仍無轉(zhuǎn)發(fā)，則認(rèn)為c的信譽(yù)值過低，判定c為問題節(jié)點(diǎn)。遍歷所有節(jié)點(diǎn)后，但凡是信譽(yù)值小于0的，都為問題節(jié)點(diǎn)。此時，以問題節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)，進(jìn)行“自私節(jié)點(diǎn)發(fā)送率”的檢測，結(jié)合信譽(yù)值進(jìn)行比較，就能得出問題節(jié)點(diǎn)的具體類型，并對其計數(shù)。最后，得到各種類型節(jié)點(diǎn)的數(shù)值，與之前記錄的節(jié)點(diǎn)數(shù)值對比，是否相同，若相同則算法的檢測部分得證。算法的另一部分是通過仿真查看各種不同數(shù)目的問題節(jié)點(diǎn)在檢測數(shù)據(jù)上的表現(xiàn)，并不斷變換各個類型問題節(jié)點(diǎn)的實(shí)際存在數(shù)目，并生成當(dāng)前的場景圖。

以下是本文中關(guān)于“丟包率”，“網(wǎng)絡(luò)吞吐量”和“自私節(jié)點(diǎn)發(fā)送率”的定義。

節(jié)點(diǎn)通過對相鄰節(jié)點(diǎn)的信譽(yù)值的評定，可以得知是否存在問題節(jié)點(diǎn)。而當(dāng)節(jié)點(diǎn)存在自私行為的時候，會對網(wǎng)絡(luò)造成不良影響，而惡意節(jié)點(diǎn)則相對于其它節(jié)點(diǎn)，表現(xiàn)的只為降低網(wǎng)絡(luò)性能的相關(guān)數(shù)據(jù)，比如降低周圍節(jié)點(diǎn)的吞吐量，提升丟包率等行為。算法中的多次檢測，也讓算法具有一定的容錯率[8]。

圖5為算法檢測部分的流程圖，對所有節(jié)點(diǎn)而言，其判決如下：當(dāng)信譽(yù)值不小于0的時候，為正常節(jié)點(diǎn)；當(dāng)信譽(yù)值小于0且自私節(jié)點(diǎn)發(fā)送率等于1的時候，為惡意節(jié)點(diǎn)；當(dāng)信譽(yù)值小于0且自私節(jié)點(diǎn)發(fā)送率等于0，為第一類自私節(jié)點(diǎn)；當(dāng)信譽(yù)值小于0且自私節(jié)點(diǎn)發(fā)送率大于0小于1，為第二類自私節(jié)點(diǎn)，最后統(tǒng)計各類問題節(jié)點(diǎn)的數(shù)量。

圖6為算法統(tǒng)計部分的流程圖，它簡單的描述了算法，通過一個判決框比較數(shù)據(jù)量。假設(shè)當(dāng)前測試數(shù)據(jù)tt為0，算法隨機(jī)產(chǎn)生起始節(jié)點(diǎn)和目的節(jié)點(diǎn)，并記錄下成功傳輸?shù)臄?shù)據(jù)和丟失的數(shù)據(jù)，不斷更新。直到TT在數(shù)值上小于tt，這時再統(tǒng)計“丟包率”、“網(wǎng)絡(luò)吞吐量”，查看各種問題節(jié)點(diǎn)在不同數(shù)量下對網(wǎng)絡(luò)性能的影響。

4 仿真分析

基于信譽(yù)值的ad hoc網(wǎng)絡(luò)節(jié)點(diǎn)自私類型檢測算法是在ad hoc網(wǎng)絡(luò)中，以AODV路由協(xié)議[9]為基礎(chǔ)的matlab程序。在已知各種類型節(jié)點(diǎn)數(shù)目的前提下，再用信譽(yù)值和自私節(jié)點(diǎn)發(fā)送率這兩個數(shù)據(jù)來檢測出問題節(jié)點(diǎn)，并進(jìn)行具體分類。第二部分的仿真主要是從丟包率和網(wǎng)絡(luò)吞吐量這兩個數(shù)據(jù)來測試三種不同的問題節(jié)點(diǎn)對當(dāng)前ad hoc網(wǎng)絡(luò)性能的影響。

圖7為節(jié)點(diǎn)類型的檢測結(jié)果，它表明當(dāng)ad hoc網(wǎng)絡(luò)的惡意節(jié)點(diǎn)、第一類型自私節(jié)點(diǎn)、第二類自私節(jié)點(diǎn)數(shù)目都為10且如圖1所示分布，通過算法的檢測部分，成功得到了三種類型問題節(jié)點(diǎn)各自正確的數(shù)量。

從圖8可以看出，三大類型問題節(jié)點(diǎn)隨著各自節(jié)點(diǎn)數(shù)目的增加，丟包率也是隨之增加。第一類自私節(jié)點(diǎn)和第二類自私節(jié)點(diǎn)在丟包率上的整體變化趨勢是類似的，第一類自私節(jié)點(diǎn)略高于第二類自私節(jié)點(diǎn)。兩類節(jié)點(diǎn)在數(shù)量小于6的時候，它們的丟包率較小，說明網(wǎng)絡(luò)并未受到較大影響，可以包容這些問題節(jié)點(diǎn)。而惡意節(jié)點(diǎn)則在丟包率上表現(xiàn)的較為突出，普遍高于前兩者，說明存在直接丟棄數(shù)據(jù)包的可能性。圖9中的三大類型問題節(jié)點(diǎn)隨著各自節(jié)點(diǎn)數(shù)目的增加，網(wǎng)絡(luò)吞吐量也隨之遞減，尤其是惡意節(jié)點(diǎn)，幾乎不傳輸數(shù)據(jù)，此時問題節(jié)點(diǎn)存在比例較大，影響了當(dāng)前網(wǎng)絡(luò)的整體性能。在這三種問題節(jié)點(diǎn)中，惡意節(jié)點(diǎn)的吞吐量比其它自私節(jié)點(diǎn)小且丟包率也高，所以它是這三種類型節(jié)點(diǎn)中影響網(wǎng)絡(luò)最大的問題節(jié)點(diǎn)。

5 結(jié)束語

在ad hoc網(wǎng)絡(luò)中，網(wǎng)絡(luò)的通信主要是依賴于節(jié)點(diǎn)之間的合作。由于各種資源的限制，節(jié)點(diǎn)往往是缺乏合作性的，為了盡可能地維護(hù)自己的利益，節(jié)點(diǎn)可能會采取各種各樣的行為，比如拒絕轉(zhuǎn)發(fā)數(shù)據(jù)、虛報節(jié)點(diǎn)信息等。在具體網(wǎng)絡(luò)環(huán)境中，有很多種情況能夠?qū)е戮W(wǎng)絡(luò)性能的降低，其威脅不僅來自于外部，更多的來自于內(nèi)部的自私節(jié)點(diǎn)、惡意節(jié)點(diǎn)、叛變節(jié)點(diǎn)。由于節(jié)點(diǎn)自私行為的多樣化，它們對網(wǎng)絡(luò)性能的影響是不同的，應(yīng)該區(qū)別對待，否則建立的懲戒機(jī)制就可能不是最有效的，因此對節(jié)點(diǎn)進(jìn)行自私類型檢測很有必要的。該文就是基于這種情況，參考了信譽(yù)值的算法，驗(yàn)證了三種自私類型節(jié)點(diǎn)的數(shù)目，并通過仿真查看其對網(wǎng)絡(luò)性能的影響。因?yàn)榫W(wǎng)絡(luò)中問題節(jié)點(diǎn)的多樣化，下一步，將會完善算法，并提出一種基于博弈論的算法來懲戒問題節(jié)點(diǎn)，構(gòu)建一個合理的機(jī)制，通過該機(jī)制讓網(wǎng)絡(luò)達(dá)到納什均衡[10]，甚至于帕累托最優(yōu)。

參考文獻(xiàn)：

[1] 譚長庚，羅文燕，陳松喬，王建新.移動Ad hoc網(wǎng)絡(luò)中節(jié)點(diǎn)合作性研究綜述[J].計算機(jī)科學(xué)，2007，4：24-27，6.

[2] 陳真勇， 唐龍，唐澤圣，熊璋.以魯棒性為目標(biāo)的數(shù)字多水印研究[J].計算機(jī)學(xué)報，2006，29（11）.

[3] 黃莉.基于博弈論的無線網(wǎng)絡(luò)節(jié)點(diǎn)行為研究[D].北京：北京交通大學(xué)，2011.

[4] Marti S， Giuli T， Lai K， and Baker M. Mitigating routing misbehavior in mobile Ad hoc networks[C].IEEE International Conference on Mobile Computing and Networking[M].NewYork：ACMPress，2000：255-265.

[5] Raya M， Aad I， Hubaux J， Fawal A. DOMINO： Detecting MAC Layer Greedy Behavior in IEEE 802.11 Hotspots[J]. IEEE TransactionsonMobileComputing，2006.5（12）：1-11.

[6] Gunasekaran R， Uthariaraj V， Yamini U， etc. A Distributed Mechanism for Handing of Adaptive/Intelligent Selfish Misbe- havior at MAC Layer in Mobile Ad Hoc Networks[J].Journal of Computer Science and Technology，2009，24（3）：1007-1017.

[7] Toledo A L， Wang X， Robust detection of selfish misbehavior in wireless networks [J]. IEEE J. Sel. Areas Commun， 2007， 6（25）： 1124-1134.

[8] Buchegger S，，Boudec J Y L.Performance analysis of the CONFIDANT protocol：Cooperation of nodes fairness in dynamic ad hoc networks. Proc of IEEE/ACM Workshop on Mobile Ad Hoc Networking and Computing（Mobi HOC），2002.

[9] LIU Chunfeng， SHU Yantai， LI Mingyuan， et al. Delay modeling and analysis of IEEE 802.11 DCF with selfish nodes[C]//Proceedings of the 4th International Conference on wireless Communications. Networking and Mobile Computing. Piscataway. NJ. USA：IEEE Press，2008：1-4.

[10] WANG Cui-rong， YANG Xiao-zong， GAO Yuan. Enhancement in Ad hoc on Demand Distance Vector （AODV） Routing Protocol Security[J]. Journal of DongHua University，2005，03：18-22.

[11] Srivastava V， Neel J O， MacKenzie A B， et al. Using game theory to analyze wireless ad hoc networks [J]. IEEE Communications Surveys and Tutorials， 2005， 7（1-4）： 46-56.