桂勁松，陳志剛

(中南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長沙，410083)

在無線接入網(wǎng)環(huán)境下，無線接入點的接入能力是有限的，尤其在面臨無線網(wǎng)絡(luò)多媒體應(yīng)用的海量數(shù)據(jù)流時。在1個無線接入點的服務(wù)范圍內(nèi)，若在線游戲、視頻會議、移動電視、P2P流媒體、交通監(jiān)控與執(zhí)法、電子醫(yī)療保健服務(wù)等應(yīng)用的用戶數(shù)量過多，則接入請求負載將很可能超出無線接入點的接入能力。在高接入負載下，無線接入點需要優(yōu)先保證一些移動節(jié)點的接入服務(wù)請求，而推遲甚至拒絕另一些移動節(jié)點的接入服務(wù)請求。能夠得到優(yōu)先接入服務(wù)保證的移動節(jié)點應(yīng)該是為無線接入網(wǎng)做出貢獻者，例如，為遠離無線接入點的移動節(jié)點中繼了數(shù)據(jù)；將接入負載較重的無線接入點區(qū)域的接入請求分流到鄰近負載較小的區(qū)域。行為表現(xiàn)惡意或極度自私的移動節(jié)點應(yīng)該被列為拒絕服務(wù)范圍。其他情況的移動節(jié)點在無線接入點處于重負載時，其接入服務(wù)請求將被推遲。為了實現(xiàn)這樣的區(qū)分服務(wù)，首先需要檢測到移動節(jié)點的行為，然后，依據(jù)系統(tǒng)服務(wù)策略實施?，F(xiàn)有移動節(jié)點行為檢測的相關(guān)工作[1?6]大多是針對無線自組網(wǎng)環(huán)境進行研究的，典型的有：Watchdog檢測方案[1]建立在 DSR路由協(xié)議的基礎(chǔ)上，并設(shè)定移動節(jié)點工作在混雜偵聽模式下。移動節(jié)點發(fā)包之后，偵聽下一跳節(jié)點的通信。如果在設(shè)定時間內(nèi)，沒有聽到該包被繼續(xù)傳送到路徑上的下一移動節(jié)點，那么認為下一跳節(jié)點自私丟包。但在不確定性沖突、接收方?jīng)_突、限制發(fā)送功率等情況下，監(jiān)視節(jié)點是不能確定下一跳節(jié)點是否成功發(fā)送了數(shù)據(jù)[1]。文獻[5]提出了一種基于 ACK 的自私丟包檢測方法 2ACK，其核心思想是傳輸路徑上的節(jié)點接收到數(shù)據(jù)包后返回ACK給2跳前的節(jié)點，從而可以對中間節(jié)點的傳輸行為進行判定。2ACK方法也建立在DSR路由協(xié)議的基礎(chǔ)上。盡管節(jié)點收到2ACK時能夠確定下一跳節(jié)點是合作的，但是，沒有收到2ACK時，不能判定下一跳節(jié)點自私丟包。另外，這種方法記錄的是行為不良的邊，但隨著節(jié)點的移動，這樣的邊可能隨之消失。文獻[6]提出了一種路由發(fā)現(xiàn)階段的行為檢測方法。其基本思想是基于鄰居的轉(zhuǎn)發(fā)包的數(shù)量與其自身產(chǎn)生包數(shù)量的統(tǒng)計關(guān)系。在通常情況下，自身產(chǎn)生包數(shù)量會遠遠小于需要其轉(zhuǎn)發(fā)包的數(shù)量。節(jié)點分別監(jiān)測過去一段時間內(nèi)的鄰居轉(zhuǎn)發(fā)和生成的路由請求包數(shù)量，如果兩者比率超過一定門限，則認為鄰居是合作節(jié)點，否則認為鄰居是自私節(jié)點。上述思想在均勻業(yè)務(wù)條件下是成立，但是，在業(yè)務(wù)不均勻的情況下可能不成立。針對無線接入網(wǎng)環(huán)境，文獻[7]提出了一種網(wǎng)絡(luò)基礎(chǔ)設(shè)施上節(jié)點參與的移動節(jié)點行為檢測方法，不需要移動節(jié)點增加新功能，而檢測工作主要由基礎(chǔ)設(shè)施上的節(jié)點來完成。這些基礎(chǔ)設(shè)施上的檢測節(jié)點通過從無線接入點提供的路由請求包和數(shù)據(jù)包中提取的源路由信息作為檢測依據(jù)，因此，此方法是建立在DSR路由協(xié)議基礎(chǔ)之上的。DSR路由協(xié)議不需要路徑的中間節(jié)點維護路由表，但增加了數(shù)據(jù)包的包頭長度，相應(yīng)地增加了網(wǎng)絡(luò)流量。而AODV路由協(xié)議則恰好相反。在局限于幾跳范圍內(nèi)拓撲變化較頻繁的無線網(wǎng)絡(luò)中，DSR和AODV路由協(xié)議都較為常用。隨著無線多跳網(wǎng)絡(luò)中多媒體應(yīng)用數(shù)據(jù)日益增長，包頭過長導(dǎo)致的額外開銷變得不可忽視，AODV路由協(xié)議相對短的包頭長度具有優(yōu)勢，因此，研究基于AODV路由協(xié)議的無線接入網(wǎng)環(huán)境下的移動節(jié)點行為檢測方法很有必要，而獲得類似于DSR源路由列表的中繼路徑是需要首先解決的問題。本文探討一種用于無線接入網(wǎng)移動節(jié)點行為檢測的基于 PPM(Probabilistic packet marking)的中繼路徑構(gòu)造方法。在基于一種特定無線接入網(wǎng)背景，概述一種使用基于PPM構(gòu)造的中繼路徑輔助移動節(jié)點行為檢測的方案后，闡述此中繼路徑的構(gòu)造方法并進行仿真分析。

1 中繼路徑的移動節(jié)點行為檢測概述

本文研究問題的背景為一個自治的管理域內(nèi)的無線接入網(wǎng)環(huán)境，移動節(jié)點移動速度局限于步行速度，能夠確保一定的端到端連接持續(xù)時間，如機場候機區(qū)、校園區(qū)域、會展場所等無線網(wǎng)絡(luò)環(huán)境中存在這類情況。圖1所示為1個簡單示例。在這樣的環(huán)境下，移動節(jié)點自己生成公私鑰對，并將公鑰與其身份一起向管理域注冊。注冊成功后，移動節(jié)點在此管理域擁有了唯一身份標識，并具備了對需要保密數(shù)據(jù)的加密以及對發(fā)送數(shù)據(jù)的數(shù)字簽名等功能。

由于數(shù)據(jù)業(yè)務(wù)通信量在時間和空間上都是不均勻的，而無線網(wǎng)絡(luò)基礎(chǔ)設(shè)施的建設(shè)不太可能都按峰值來考慮，因此，一些無線接入點區(qū)域的接入請求負載可能超出其能力，而另一些則相對空閑的情況較為常見。處于擁塞無線接入點區(qū)域的用戶通過移動到非擁塞區(qū)域可以獲得更多的接入帶寬。此思想自首次被Satyanarayanan[8]描述后，一直受到研究人員的關(guān)注，并提出了各具特色的解決方案[9?11]。但這些方案的共同點是持有移動設(shè)備的用戶需要以獲得更多的接入帶寬為目標進行移動。在實際中，這可能與因其他目的而進行的移動存在方向上的沖突，或約束了用戶移動的自由。這時，移動節(jié)點間合作進行數(shù)據(jù)中繼，是均衡接入負載的一種有效方法。若圖1中無線接入點II處負載較重，而移動節(jié)點B和G愿意將部分接入請求分別中繼到無線接入點I和III處，則整個接入網(wǎng)的負載會相對均衡。移動節(jié)點的內(nèi)存容量、處理器計算能力、電源等資源都十分有限，其行為常常表現(xiàn)出自私傾向，因此，系統(tǒng)無法確定自愿的中繼數(shù)據(jù)行為是否會發(fā)生，采用激勵機制是一種有效的解決方法。

在無線接入網(wǎng)環(huán)境下，移動節(jié)點訪問 Internet服務(wù)都要經(jīng)過無線接入點中轉(zhuǎn)，因此，在基礎(chǔ)設(shè)施上設(shè)置專門的服務(wù)器 S，移動節(jié)點只要參與了中繼上行數(shù)據(jù)包(從移動節(jié)點到Internet)的工作，其貢獻由無線接入點匯報服務(wù)器S進行處理并記錄其貢獻。移動節(jié)點注冊后，服務(wù)器S初始化其貢獻值為0。貢獻值不低于0的移動節(jié)點原則上都能得到接入服務(wù)，前提是無線接入點的接入服務(wù)能力不低于接入服務(wù)請求負載。當某無線接入點負載重時，無線接入點向服務(wù)器S咨詢接入服務(wù)請求者(即移動節(jié)點)的貢獻值，依據(jù)貢獻值確定處理優(yōu)先級。以此激勵移動節(jié)點在自己能力所及范圍內(nèi)自愿為其他移動節(jié)點中繼數(shù)據(jù)來提升貢獻值，以增加自己請求接入服務(wù)的成功概率。這里的關(guān)鍵是如何獲得移動節(jié)點中繼數(shù)據(jù)的貢獻。

圖1 一種無線接入網(wǎng)環(huán)境Fig.1 A wireless access network environment

當采用DSR路由協(xié)議時，無線接入點收到的所有包中都含有源路由信息，其中包含路徑上的中間節(jié)點列表，無線接入點只要將中間節(jié)點列表以及此包的長度信息提交服務(wù)器S處理即可。然而，在采用AODV路由協(xié)議時，無法獲得中繼數(shù)據(jù)的中間節(jié)點列表，因此，本文通過借鑒 IP路由追蹤技術(shù)中概率包標記算法[12?14]的思想，移動節(jié)點在轉(zhuǎn)發(fā)數(shù)據(jù)包前，以一定概率將與自己 IP地址相關(guān)的信息填入數(shù)據(jù)包頭指定區(qū)域，無線接入點將收集到的數(shù)據(jù)包的包頭提交服務(wù)器S，由其根據(jù)一定數(shù)量的包頭中所含信息，依據(jù)一定算法構(gòu)造出一條從數(shù)據(jù)包的發(fā)送源到無線接入點為目的地的路徑，從而獲得中繼節(jié)點列表。此方法只要求移動節(jié)點根據(jù)自身處理能力在經(jīng)過它且需要它轉(zhuǎn)發(fā)的上行數(shù)據(jù)包的相關(guān)域中添加上與自己 IP地址相關(guān)的信息即可，不增加任何新包。

移動節(jié)點根據(jù)自身能力，若決定參與中繼數(shù)據(jù)的工作，則只有參與尋路過程，才有機會出現(xiàn)在數(shù)據(jù)中繼路徑上。若移動節(jié)點在數(shù)據(jù)中繼路徑上，則除中繼上行數(shù)據(jù)流外，還要中繼下行數(shù)據(jù)流(從Internet到移動節(jié)點)。因為根據(jù)本文研究問題的背景(存在一定的端到端連接持續(xù)時間)，無需為下行數(shù)據(jù)流重新尋路，除非下行數(shù)據(jù)流傳輸時間超過端到端連接持續(xù)時間(這時通過無線接入點間協(xié)作，由離目標移動節(jié)點最近的無線接入點轉(zhuǎn)發(fā)，也許目標移動節(jié)點在此無線接入點直接通信范圍內(nèi)或只需1個中間移動節(jié)點的中繼。若屬于這種情況，中繼路徑是確定的，無需另行求解)。對中繼下行數(shù)據(jù)流行為的檢測沒有上行數(shù)據(jù)流那樣便利，而且通常數(shù)據(jù)量也較上行數(shù)據(jù)量大，因此，中間節(jié)點為了節(jié)省能量，被丟棄的可能性很大。

要求無線接入點在轉(zhuǎn)發(fā)下行數(shù)據(jù)給目標移動節(jié)點時，必須將分組數(shù)據(jù)域進行數(shù)字簽名并附在其后面，并稱此數(shù)字簽名為分組印章，將它的一個副本同時提交給服務(wù)器 S。目標移動節(jié)點成功收到數(shù)據(jù)后，將分組印章發(fā)送給服務(wù)器S以示確認，于是，中繼路徑上的所有中間節(jié)點都獲得貢獻分。若服務(wù)器S在規(guī)定時間內(nèi)未收到分組印章，則依次詢問中繼路徑上的中間節(jié)點以確定問題所在。服務(wù)器S首先詢問目標移動節(jié)點在中繼路徑上的鄰居，若此鄰居能提供其發(fā)送的數(shù)據(jù)幀的幀頭(為防篡改，可加上數(shù)字簽名)和分組印章做證明，然后，服務(wù)器S詢問此鄰居的鄰居是否也能提供同樣的幀頭，若能，則說明此幀被發(fā)送，而且也被發(fā)送者的鄰居監(jiān)聽到，于是，認為發(fā)送者既然愿意消耗能量發(fā)送數(shù)據(jù)，而故意造成目標節(jié)點接收不成功的可能性較小，詢問就此結(jié)束，服務(wù)器S為中繼路徑上的所有中間節(jié)點增加貢獻分。否則，應(yīng)按同樣的方法繼續(xù)沿中繼路徑朝無線接入點方向詢問下去，直至確定問題所在為止。對被認定為惡意行為可能性較大的中間節(jié)點給予懲罰，即扣除一定貢獻值。若移動節(jié)點的貢獻值低于0，則被列入拒絕服務(wù)名單。

由上可見，中繼路徑的獲得對服務(wù)器S的工作至關(guān)重要。下面重點研究如何在基于AODV路由協(xié)議的無線接入網(wǎng)環(huán)境下，根據(jù)上行請求數(shù)據(jù)包提供的信息，構(gòu)造出參與數(shù)據(jù)中繼工作的中間節(jié)點列表，即中繼路徑。

2 基于PPM的中繼路徑構(gòu)造

概率包標記技術(shù)標記的對象是經(jīng)過它的所有 IP包， IP首部可供包標記使用的空間十分有限。為了顯著減少路徑上邊和距離等信息所占用的空間量，將標記的信息分成多個塊，分別由不同IP包頭攜帶，由路徑構(gòu)造者收集大量的包后再構(gòu)造出 IP包所經(jīng)過的路徑。以收斂包數(shù)和收斂時間的相應(yīng)增加來減少標記信息占用的空間。用于追蹤攻擊源的概率包標記技術(shù)所運用的環(huán)境是：(1)攻擊者發(fā)送包的數(shù)量大；(2)攻擊者和受害者之間的路徑十分穩(wěn)定。本文研究問題的背景與概率包標記技術(shù)應(yīng)用于追蹤攻擊源的背景不同，其特點是：(1)本文只使用請求包數(shù)據(jù)構(gòu)成的 IP分組序列來重構(gòu)路徑，這樣的分組數(shù)量相對較少；(2)由于本文的目的是通過構(gòu)造路徑來得到中繼節(jié)點列表，以方便為中繼節(jié)點記錄貢獻值，所以，在移動節(jié)點請求 Internet服務(wù)之初，要求能很快地構(gòu)造出路徑并獲得中繼節(jié)點列表；(3)由于發(fā)起服務(wù)請求的移動節(jié)點和無線接入點之間的路徑不穩(wěn)定，一條路徑維持的時間有限，所以，需要周期性啟動路徑構(gòu)造算法，以驗證中繼節(jié)點列表是否改變，若已改變，則要及時作出更新。因此，需要的路徑構(gòu)造算法注重更加少的收斂包和更短的收斂時間。

依據(jù)文獻[12]，構(gòu)造路徑長度為d 的路徑所需要的包數(shù)X滿足如下關(guān)系：

其中：p為對包進行標記的概率；d為路徑長度；E(X)為所需要包數(shù)的期望值。為了滿足所研究問題的需要，可以加大一個 IP包攜帶的標記信息量。因此，提出n(n＞1)次包標記方案，從概率上相當于每次都取n次，期望的包數(shù)X滿足如下關(guān)系：

對上式求p的一階導(dǎo)數(shù)(把d和n看為常數(shù))并令其等于0，得到：在p=1/d 時，X有最小值；當d=5時，有p=0.2，同時，取n=4，可知X大約為5；當d為2，3和4時，取p=0.2和n=4，可得X大約為1.00，2.00和3.40，非常接近各自的最小值(即0.69，1.85和3.28)。

移動節(jié)點訪問 Internet服務(wù)的顯著特點是請求包小，響應(yīng)包大。盡管響應(yīng)包能夠提供更多的IP分組，對構(gòu)造較長的中繼路徑有利，但這只能由能量受限的移動節(jié)點(即發(fā)起訪問Internet服務(wù)的移動節(jié)點)來做。為了盡量減輕移動節(jié)點負擔，只能將構(gòu)造工作放在無能量約束的基礎(chǔ)設(shè)施節(jié)點上，但它只能利用由請求包構(gòu)成的IP分組序列。應(yīng)用層的一次服務(wù)請求的數(shù)據(jù)量也許在網(wǎng)絡(luò)層使用一個IP分組就能承載，由上述分析可知，無法滿足構(gòu)造數(shù)據(jù)包傳輸路徑的IP分組數(shù)量要求，因此，需要同一個發(fā)送源的后續(xù)請求包來湊足一定數(shù)量。

通常，訪問 Internet服務(wù)時發(fā)送多個請求的情況是很普遍的，例如，當訪問基于web的電子郵件系統(tǒng)時，首先發(fā)一個請求以得到交互頁面，然后通過此頁面提交用戶名和密碼，得以進入個人郵箱頁面，這時，可以點擊收件箱來得到收信頁面，然后，點擊需要收看的信，若是帶附件的信，則要點擊下載附件的鏈接。由此例可見，在這個會話中，依次發(fā)送了5個請求，得到了4個相對短的響應(yīng)和1個相對長的響應(yīng)。因此，利用同一用戶多次請求所形成 IP包序列中的標記信息，構(gòu)造出較長的中繼路徑是可行的。對能維持一定的端到端連接持續(xù)時間的無線網(wǎng)絡(luò)應(yīng)用場景，同一移動節(jié)點多個會話的數(shù)據(jù)流在網(wǎng)絡(luò)層走的是同一路由，上行分組流量也能確保中繼路徑在首次構(gòu)造后，周期性重構(gòu)以滿足驗證之需。例如，在網(wǎng)頁瀏覽或在線游戲中，用戶頻繁地點擊超鏈接會形成持續(xù)的上行流量。

圖2所示為 IP首部可以為人們所用的域。TOS(Type of service)域是用來表示服務(wù)類型或用作QoS服務(wù)，共8 bit。但在廣域網(wǎng)中通常被忽略，因此，此域可作他用。在本方案中，使用該域中的3 bit標記距離，1 bit標記數(shù)據(jù)包類型(例如，0為請求包，1為響應(yīng)包)。IP首部的identification，flags和offset 3個域為IP包分片后方便重組而設(shè)置的，但現(xiàn)在的網(wǎng)絡(luò)應(yīng)用一般都有自動MTU (Maximum transmission unit)協(xié)商的功能以防分片發(fā)生，因此，這3個域很少被使用，可作他用。在本文方案中，使用這32 bit記錄1個邊界 ID(edge ID)。IP首部有1個選項域，用來支持排錯、測量以及安全等措施，長度是可變的，從1個字節(jié)到 40個字節(jié)不等，其具體長度取決于所選擇的項目。若采用4次包標記，則需要采取長度為12個字節(jié)的選項域來記錄另3個邊界ID。由上述可見：對單個IP地址不再分片，利用了IP首部選項域的空間來加大單個IP分組的地址標記信息承載量，目的是為了加快構(gòu)造路徑的速度。

圖2 用部分的IP包頭域作為標記域Fig.2 Using gray fields as marking fields in IP header

以4次包標記方案為例，若第2至第4次標記仍然以相同的概率進行標記，那么，實際概率將顯著變小。例如，當標記概率p為0.2時，第4次標記概率實際為 0.24=0.001 6，起不到實質(zhì)的作用。所以，將策略調(diào)整為：如果數(shù)據(jù)包被標記，那么在接下來的至多連續(xù)3跳以p=1進行包標記?？梢酝ㄟ^檢測距離域的值來確定是第幾次標記。在本方案中，沒有標記的包的距離域被置為NIL。如果檢測到距離域的值為0，說明此包已被標記了1次，就進行第2次標記，其余以此類推。若距離域為NIL，則按照概率p進行第1次標記。

圖1所示的所有移動節(jié)點(A～L)都運行一種包標記算法。當1個IP地址為MN的移動節(jié)點收到1個上行IP包(IP首部type域為0指示其為請求包數(shù)據(jù)，即上行IP包，見圖2)，而且從未標注過(IP首部dist域為NIL指示未曾被任何移動節(jié)點標注，見圖2)，則按照概率p進行第1次標記進行決策。若決策結(jié)果是標記，則將地址MN填入IP首部的FE域(見圖2)。若此移動節(jié)點發(fā)現(xiàn)dist域為0，則表明給它發(fā)送此IP包的鄰居已將自己的地址填入了 FE域，此時，它需要將自身 IP地址與鄰居的進行異或運算，并將結(jié)果(此結(jié)果表示自身與鄰居之間的邊)填入FE域，同時，自身IP地址被填入SE域以作為下一條邊的起點。dist域的值也需要加1，它表示此節(jié)點與首次標記此IP包的節(jié)點之間增加了1條邊的距離。類似過程持續(xù)至此IP包的最大標記次數(shù)或已到達無線接入點為止。若收到的IP包中dist域的值達到或超過最大標記次數(shù)，則以概率p進行標記決策。若決策結(jié)果是標記，則前面節(jié)點的標記信息被覆蓋，否則，只是將dist域的值增1。若此IP包被發(fā)送節(jié)點的鄰居標記后，未被后面節(jié)點覆蓋掉而順利到達目的節(jié)點，則dist域的值增1就是從發(fā)送節(jié)點到目的節(jié)點需要經(jīng)過的邊數(shù)。無線接入點將其收到的被標記的IP包提交服務(wù)器S進行路徑構(gòu)造，其中單個IP包最多可標記4次的包標記算法偽代碼如圖3所示。

圖3 包標記算法偽代碼Fig.3 Pseudo code of packet marking algorithm

圖1所示的服務(wù)器S上運行一種中繼路徑構(gòu)造算法。S以提交標記分組的無線接入點為基準點b，根據(jù)其提交的標記分組(具有相同的源IP地址)所含信息構(gòu)造中繼節(jié)點列表L。這里的關(guān)鍵是將用于中繼路徑構(gòu)造的所有標記分組根據(jù)其IP首部dist域的值排序，按從小到大的順序處理。在上面的包標記算法中，本文作者使用了1條邊的2個端點值的異或運算結(jié)果表示此邊的值。若知道了1條邊的值為x⊕y, 其中1個端點的值為x，則通過x⊕y⊕x可得到另一個端點的值y。圖4中與4次包標記算法配套的中繼路徑構(gòu)造算法偽代碼中用到了這一點。

圖4 中繼路徑構(gòu)造算法偽代碼Fig.4 Pseudo code of relay path construction algorithm

3 仿真結(jié)果與分析

在VC++6.0編程環(huán)境下，實現(xiàn)圖1中所示的服務(wù)器S、無線接入點、移動節(jié)點共3種模塊。其中：無線接入點位于圖1中IV處，與服務(wù)器S可直接通信，而與移動節(jié)點J，I，G，E，D，B和A形成線形拓撲結(jié)構(gòu)，即無線接入點IV與J可直接通信，而與I通信則需要通過J中繼，其余以此類推。圖1中其他節(jié)點在本仿真中不存在。

首先，針對式(2)中標記概率p取不同值而n=4時，仿真收斂包數(shù)X隨路徑長度d的變化情況如圖5所示。然后，保持p=0.2而n取不同值時，仿真收斂包數(shù)X隨路徑長度d的變化情況如圖6所示。使用移動節(jié)點I向無線接入點IV發(fā)送IP包，可獲得d=2時的收斂包數(shù)X，而使用A向IV發(fā)送IP包，則可得到d=7時的收斂包數(shù)。從圖5可知：標記概率p越小，收斂包數(shù)隨路徑長度的變化越平緩，因此，取p=0.2能較好地適應(yīng)路徑長度d的變化，而當路徑長度變化不大且不大于3時，適當增加標記概率有利于減少收斂包數(shù)。從圖6可知：標記次數(shù)n越大，所需收斂包數(shù)越少，但移動節(jié)點的平均標記工作量越大；當n取4時，與n取2或3時相比收斂包數(shù)減少幅度較大，而n取5時，盡管進一步減少了收斂包數(shù)，但減少幅度已不大。

設(shè)定移動節(jié)點發(fā)送請求包的間隔為10 s，仿真收斂時間隨路徑長度d的變化情況。標記概率p取不同值而標記次數(shù)n=4的情況如圖7所示。由圖7可見：p=0.2時的收斂時間變化很平緩，能適應(yīng)較大的路徑長度變化，但在小于4跳的情況下，增大標記概率到p=0.5明顯減少了收斂時間；同時，在大于4跳的情況下，則又顯著增加了收斂時間。這可解釋為：當采用高標記概率且中繼路徑較短時，能更快地產(chǎn)生標記包，而被后面覆蓋的較少；但隨著路徑長度的增加，被覆蓋得更多，因此，需要更長時間來獲得足夠的被標記包。圖8所示顯示了保持p=0.2而n取不同值時的情況，其規(guī)律與圖6所示的規(guī)律相類似。

圖5 標記次數(shù)n=4而標記概率p取不同值時的收斂包數(shù)比較Fig.5 Convergence packets under n=4 and different marking probabilities

圖6 標記概率p=0.2而標記次數(shù)n取不同值時的收斂包數(shù)比較Fig.6 Convergence packets under p=0.2 and different marking frequencies

圖7 標記次數(shù)n=4而標記概率p取不同值時的收斂時間比較Fig.7 Convergence time under n=4 and different marking probabilities

圖8 標記概率p=0.2，標記次數(shù)n取不同值時的收斂時間比較Fig.8 Convergence time under p=0.2 and different marking frequencies

為了與利用DSR路由協(xié)議的源路由信息的方法進行IP包頭開銷的比較，實現(xiàn)基于AODV路由協(xié)議的中繼路徑構(gòu)造3種方案：方案A(n=3,p=0.2)，方案B(n=4,p=0.2)，方案C(n=5,p=0.2)。同時，實現(xiàn)方案D(DSR源路由，協(xié)議頭格式參見文獻[15])。同樣設(shè)定移動節(jié)點發(fā)送請求包的間隔為10 s，運行時間為180 s，仿真4種方案下的IP包頭開銷隨路徑長度d的變化情況如圖9所示。從圖9可以看到：這3種方案的開銷明顯低于方案D的開銷。從圖10可以看到這3種方案的差別：當路徑長度在5跳以下時，方案C占優(yōu)；在5跳以上時，方案A占優(yōu)。這可解釋為：標記次數(shù)大的方案減少了前面標記的包被后面覆蓋的概率，因為一旦前面標記了，后面將以概率1添加而不是以概率 0.2覆蓋，這有利于減少收斂包數(shù)。當路徑路徑長度不超過某個值例如5時，標記次數(shù)大的方案因收斂包數(shù)少，而節(jié)省的包頭開銷優(yōu)勢大于其標記次數(shù)大帶來的包頭開銷大的劣勢，因而，總的開銷比標記次數(shù)小的方案的開銷少。當路徑路徑長度超過某個值時，效果則適得其反。

圖9 各種方案的IP包頭開銷比較Fig.9 Comparison of IP header costs in various schemes

圖10 本文方案放大后的情況Fig.10 IP header costs of our schemes after magnification for viewing

綜上所述，在本文方案中，當標記概率 p取 0.2時，收斂包數(shù)量和收斂時間隨路徑長度變化較平緩且平均性能較優(yōu)；當標記次數(shù)n取4時，收斂包數(shù)較少，收斂時間更短，同時移動節(jié)點標記工作量增加不多，能取得較好的折中。與基于DSR的方案相比，本文方案明顯節(jié)省IP包頭開銷，能夠較好地適應(yīng)無線網(wǎng)絡(luò)多媒體應(yīng)用環(huán)境。

4 結(jié)論

(1)提出了一種應(yīng)用于無線接入網(wǎng)環(huán)境下移動節(jié)點行為檢測的中繼路徑構(gòu)造方法。該方法要求移動節(jié)點以一定概率標記它中繼的包，一個專門服務(wù)器根據(jù)所收集到的標記包頭所攜帶信息來構(gòu)造中繼路徑。后繼移動節(jié)點通過對已標記包添加自身信息來加大同一個包所攜帶的信息量，從而減少了中繼路徑構(gòu)造算法所需的收斂包數(shù)和收斂時間。

(2)分析了本方法中的標記概率和標記次數(shù)對收斂包數(shù)和收斂時間的影響，并指出標記概率 p取 0.2以及標記次數(shù)n取4時，可在收斂包數(shù)和收斂時間的節(jié)省上與移動節(jié)點標記工作量的增加上取得較好的折中。

(3)利用本文的中繼路徑構(gòu)造方法獲得中繼節(jié)點列表明顯比利用DSR的源路由信息的方法節(jié)省IP包頭開銷。

[1]Marti S, Giuli T, Lai K, et al.Mitigating routing misbehavior in mobile ad hoc networks[C]//Proceedings of the Sixth Annual International Conference on Mobile Computing and Networking(MobiCom).Boston: ACM Press, 2000: 255?265.

[2]Buchegger S, Le Boudec J Y.Performance analysis of the CONFIDANT protocol: Cooperation of nodes, fairness in dynamic ad-hoc networks[C]//Proceedings of MobiHoc’02.Lausanne, Switzerland: ACM Press, 2002: 226?236.

[3]Michiardi P, Molva R.Core: A collaborative reputation mechanism to enforce node cooperation in mobile ad hoc networks[C]//Proceedings of the IFIP TC6/TC11 6th Joint Working Conference on Communications and Multimedia Security.Deventer, Netherlands, 2002: 107?121.

[4]HU J Y.Cooperation in mobile ad hoc networks[R].Technical Report, CS-TR-050111, Florida State University[EB/OL].[2005].http://www.cs.fsu.edu/ research / reports/TR-050111.pdf

[5]LIU K, DENG J, Varshney P K, et al.An acknowledgment-based approach for the detection of routing misbehavior in MANETs[J].IEEE Transactions on Mobile Computing, 2007, 6(5): 488?501.

[6]黃蕾, 劉立祥.Ad hoc網(wǎng)絡(luò)尋路階段的合作激勵機制研究[J].計算機學(xué)報, 2008, 31(2): 262?269.HUANG Lei, LIU Li-Xiang.Study on cooperation stimulation mechanism in route discovery of ad hoc networks[J].Chinese Journal of Computers, 2008, 31(2): 262?269.

[7]Gui J S.A routing misbehavior detection and mitigating scheme based on reputation in hybrid wireless mesh networks[C]//Proceedings of the 8th International Conference on Dependable,Autonomic and Secure Computing (DASC-09).Chengdu, China:IEEE Computer Society, 2009: 545?550.

[8]Satyanarayanan M.Pervasive computing: visions and challenges[J].IEEE Personal Communications, 2001, 8(4):10?17.

[9]Balachandran A, Bahl P, Voelker G.Hot-spot congestion relief in public-area wireless networks[C]//Fourth IEEE Workshop on Mobile Computing Systems and Application.Callicoon, New York: IEEE Computer Society, 2002: 70?80.

[10]Sanzgiri K, Royer E B.Leveraging mobility to improve quality of service in mobile networks[C]//First Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services (MobiQuitous’04).Boston: IEEE Computer Society,2004: 128?137.

[11]Mittal K, Belding E M, Suri S.A game-theoretic analysis of wireless access point selection by mobile users[J].Computer Communications, 2008, 31(1): 2049?2062.

[12]Savage S, Wetherall D, Karlin A, et al.Network support for IP traceback[J].ACM/IEEE Transactions on Networking, 2001,9(3): 226?237.

[13]MA Miao.Tabu marking scheme to speedup IP traceback[J].Computer Networks, 2006, 50(18): 3536?3549.

[14]Liu J S, Lee Z J, Chun Y C.Dynamic probabilistic packet marking for efficient IP traceback[J].Computer Networks, 2007,51(3): 866?882.

[15]Johnson D, Maltz D, Hu Y C.The dynamic source routing protocol for mobile ad hoc networks[EB/OL].[2010?03?15].http://www.ietf.org/ietf/lid-abstracts.txt