大規模MANET路由協議SPDSR的仿真研究

郭一辰，陳 靖，羅 樵，陳桂茸

（空軍工程大學 電訊工程學院，陜西 西安710077）

0 引 言

移動 Ad hoc網絡（mobile Ad hoc network，MANET）由一組無線移動節點組成，是一種沒有任何基礎設施、自組織、自愈的網絡［2］。及至目前，人們已經提出了多達10～20種Ad hoc網絡路由協議，經典的路由協議有DSDV（destination－sequenced distance－vector routing）， AODV（Ad hoc on demand distance vector），DSR（dynamic source routing）等［3－4］。通過前期對這3種協議進行的大量仿真實驗及對結果進行的觀察分析可以看到，在小規模網絡中，DSR的綜合性能要優于另外兩種協議，但當網絡規模擴大即網絡中的節點個數增加時，3種協議的性能均有明顯下降，其中以AODV和DSDV性能變化最為明顯。因此需要一種對大規模網絡具有良好支持的新型Ad Hoc路由協議。

本文所討論的一種新協議——SPDSR，是在 MANET路由協議領域，選擇主流反應式路由協議之一的DSR作為研究對象建立起來的。這種新的路由模型在MANET物理拓撲基礎上構建一層結構化P2P覆蓋層網絡，將運行在邏輯命名空間的P2P覆蓋層網絡協議功能與運行在物理命名空間的MANET路由協議無縫地結合起來，其目的是利用P2P計算模式對大規模網絡具有良好支持這一優點，將其有效地應用到無限自組織網絡路由技術中，從而實現了網絡資源的充分利用。本文設計實現了這一算法，并通過仿真實驗驗證了該算法在大規模網絡中的優越性能。

1 DSR協議和P2P技術

1.1 DSR協議

DSR協議是最早采用按需路由思想的路由協議［5］。其實現方式是中間節點不用維護去往全網所有節點的路由信息。當有分組需要發送并且本地路由表中沒有到目的節點的路由時，協議將啟動路由發現和路由維護算法，從而實現源節點和目的節點之間路徑的發現和維護。

DSR的優點是中間節點不用維護去往全網所有節點的路由信息，而且可以避免出現路由環路。它的缺點是每個數據分組都攜帶了路徑信息，造成協議開銷較大。而且也不適合網絡直徑大的自組網，網絡可擴展性不強［6］。

1.2 P2P技術和Chord算法

目前三代主流P2P路由模型為集中目錄式P2P網絡路由模型（第一代P2P路由模型），非結構化P2P網絡路由模型（第二代P2P路由模型）以及結構化P2P網絡路由模型（第三代P2P路由模型），其中研究最多應用最廣的是結構化P2P網絡路由模型［7］。其模型中的每個節點通過存儲少量路由信息，實現源節點到目的節點間的消息路由功能。該模型取締了泛洪算法，有效減少節點消息發送數量，使P2P網絡的可擴展性得到了增強。

Chord是最為典型的非結構化P2P網絡路由模型［8］。在Chord模型中，系統通過哈希算法給網絡中每個節點和資源分別賦予一個標識符，這些標識符按照一定的規則排列形成一個環（如圖1所示），環中每個節點具有其自己的路由表（在Chord中被稱為Finger table），并通過查詢該路由表進行消息的路由和轉發。

圖1 Chord路由表結構及消息轉發過程

1.3 結構化P2P網絡路由技術和 MANET路由技術的交叉研究

結構化P2P網絡與無線移動自組織網絡具有相似之處，見表1。

通過觀察研究兩種網絡的相似性特征可以預測，根據P2P技術與MANET技術的切合點從而產生新的MANET路由協議是可行的研究方向。因此在兩個技術領域分別選擇Chord模型和DSR協議作為研究對象，為下文對新算法的研究實現提供了技術基礎。

表1 結構化P2P網絡與無線移動自組織網絡相似性比較

2 基于P2P計算模式的MANET路由協議：SPDSR

本節介紹一種基于P2P計算模式的新型MANET路由模型，在主流反應式MANET路由協議DSR的基礎上，通過引入基于DHT的分布式命名機制、新型路由表以及一系列優化策略，有效地建立起一個基于MANET架構的完全分布式自組網路由協議——SPDSR。新路由模型實現了DSR和Chord算法的結合，并繼承了DSR所有動態特征和優點。

2.1 SPDSR模型基本設計

與DSR一樣，SPDSR也是一個基于MANET的網絡層路由算法，消息的源節點及目的節點采用IP地址。不同的是，SPDSR為每個節點分配了唯一的節點身份標識（Node Identifier，NID），這些NID都屬于同一個連續的哈希環域空間，通過在這個空間上運行P2P網絡路由算法，SPDSR有效實現了移動節點間的信息共享和消息通信。圖2描述了SPDSR的節點命名機制，其中圖2（a）描述了無線自組織網絡的結構，圖2（b）顯示了圖2（a）中無線自組織網絡所對應邏輯命名空間的哈希環域空間結構。

2.2 SPDSR路由算法

2.2.1 SPDSR路由發現算法

SPDSR路由發現算法通過按需機制查找通往指定目標節點的源路由，路由發現過程一般均由移動節點啟動的路由更新過程調用。不同于DSR的是［9］，SPDSR路由發現算法僅查詢每個移動節點指定路由表項對應下一跳節點的源路由，并采用多跳路由的方式將路由消息經過多個節點轉發至目的節點。SPDSR路由表（PRT，SPDSR Routing Table）的結構如表2所示。

圖2 SPDSR節點命名機制

表2 SPDSR路由表結構

在SPDSR路由算法中，每個路由表項負責所有NID屬于該路由表項對應環域空間范圍（NRI）內目標節點的路由，無需像DSR一樣針對每個不同目標節點的路由查詢消息進行路由發現，因此SPDSR下廣播機制造成的網絡流量負擔將大大減少。

2.2.2 SPDSR路由表查詢算法

SPDSR的路由表查詢算法是基于P2P計算模式的結構化覆蓋層網絡路由查詢算法，其采用的路由表查詢機制與Chord算法的路由發現機制原理類似。在SPDSR中，每個節點的IP地址通過哈希雜湊運算獲得對應的NID和KID，這兩個識別碼具有嚴格的一一對應關系，因此只要目標節點存在于網絡中，SPDSR就能通過消息在節點間的多跳轉發定位目標節點。而這一多跳過程是通過每個節點的無線收發機在其信號傳輸范圍內，與其它節點建立連接完成的。

2.2.3 SPDSR路由維護算法

（1）移動節點的加入（mobile node join）

在移動節點加入網絡時，SPDSR不對移動節點的路由表進行初始化，而僅當有某種消息路由需求時，才按需啟動路由表項發現機制，實時構建相應路由表項。

（2）移動節點的退出（mobile node departure）

在SPDSR中，節點的退出可分為正常退出和異常退出。對于移動節點異常退出，系統將不采取任何動作；對于移動節點正常退出，系統將進行以下動作：移動節點B首先向其后繼節點C和前繼節點A發送一個退出請求消息（QREQ），C和A接收到該消息后，將分別更新自己的前繼和后繼節點，從而使哈希環的完整性得到了保證。

2.3 SPDSR路由算法優化策略

2.3.1 偵聽技術

DSR中一個重要的優化策略是偵聽技術，即偵聽通過本節點轉發的數據分組和路由響應分組，從而獲取通往網絡中其他節點的路由信息。SPDSR繼承了這一優化策略，但不同于DSR的是，SPDSR中的節點僅偵聽并提取通往本節點路由表項所對應的下一跳節點的源路由信息，有效降低了路由更新和維護開銷［10］。

2.3.2 源路由檢測機制與phello協議

源路由檢測機制和phello協議是為了解決SPDSR中的繞路問題而引入的兩種優化機制。源路由檢測機制的基本思想就是每個移動節點在發起一次路由查詢請求或轉發某個路由查詢消息時，應首先通過判斷目標節點是否存在于路由表項中某條源路由的中間節點之中，如果是，則從該源路由中提取通往目的節點的路由信息，并直接返回給路由查詢發起節點。

phello協議采用按需發送機制，僅當某節點需要發起一次路由查詢請求或者轉發某個路由查詢消息時，才向其無線信號范圍內的相鄰節點發送hello消息以獲得相鄰節點的列表信息，其目的是降低phello協議對網絡造成的路由開銷。

總之，通過一系列算法優化策略的引入，進一步提高了模型的路由性能，有效地建立起一個基于MANET架構的完全分布式自組網路由協議。

3 基于NS－2的SPDSR的仿真

3.1 SPDSR協議的設計和實現

SPDSR協議是在DSR協議的基礎上，結合P2P計算模式建立起來的。其目的是通過Chord算法與DSR的結合，將P2P網絡路由算法的優點有效移植到新型MANET路由協議之中。因此SPDSR在DSR中已有類的基礎上，添加了新的類，如圖3所示。

（1）用于存放運行時用到的常量的MyConst類；

（2）用于連續hash函數構造的哈希構造類Hash；

（3）用于維護全局Chord環節點的Chord環類Chord－Cycle；

（4）用于存放節點類信息的Chord環節點類Chord－Node；

圖3 SPDSR中添加的類及類之間的關系

（5）用于節點路由表維護和管理的節點管理類NIDManager；

（6）算法路由表PRTTable；

（7）存儲路由信息的路由表項類PRTEntry。

哈希構造類Hash將節點的地址通過哈希運算映射成一個哈希環域空間結構，有效實現了移動節點間的信息共享和消息通信；類ChordNode用于存儲節點Id值和下一節點指針的信息，通過Chord環類ChordCycle對其信息的調用，實現了在Chord環中節點查詢，插入，刪除的功能，維護了全環節點的秩序；類NIDManager的功能是標識節點NID和定位目標節點NID，從而實現對節點路由表的維護和管理。

路由表項類PRTEntry包含NHID，路由表路徑的實際長度等信息，用于查看NHSR中是否包含到destId的節點路徑。一個節點的所有路由表項構成這個節點的算法路由表PRTTable，加入這個類可以實現初始化PRTEntry，更新PRTEntry中的路由表路徑等功能。

3.2 NS－2分裂對象模型擴展［11－12］

NS－2支持有線和無線網絡中的有關TCP、路由、多播等協議的模擬，且只支持4種主要自組網路由協議（DSDV、DSR、TORA和 AODV）。為了在NS－2中添加新協議，需要擴展NS－2分裂對象模型，其步驟為：添加tcl的新協議類；添加新協議支持；新協議初始化。

對新協議做仿真實驗時，需要在仿真程序中添加對新協議支持。即在仿真程序中添加以下代碼：

3.2.1 添加tcl的新協議類

針對新算法SPDSR，需要添加tcl類SPDSRNode，并初始化參數。在類SPDSRNode中主要是對SPDSRAgent類功能的tcl封裝，具體包括：配置模擬環境參數、新算法的初始化方法、添加接口參數的設置、參數重置方法和初始化參數等過程。

3.2.2 ns－lib.tcl中添加新協議支持

ns－lib.tcl中定義的模擬器類Simulator在創建無線節點時調用了函數create－wireless－node，為了增加對新路由協議SPDSR的支持，需要增加SPDSR啟動入口（MYMself at 0.0"MYMnode start－spdsr"）、對SPDSR節點參數進行設置和綁定SPDSR節點代理類。

3.2.3 新協議初始化

在tcl/lib/ns－default.tcl中 添 加 對 SPDSR 初 始 值 的 設置，代碼如下：

4 實驗結果及分析

本實驗模擬在1000＊1000m，節點移動速度1m/s，數據流類型為cbr的單兵場景中，節點規模變化（節點個數分別為50，70，100，200，300，400，500個）對分組投遞率，平均端到端延時，路由開銷，吞吐量這4個性能指標的影響。通過對DSR和SPDSR這兩種路由協議性能的比較，論證SPDSR在大規模無線網絡中的優勢。

4.1 分組投遞率（packet delieve ratio，PDR）

如圖4所示，兩種協議的分組投遞率在中小規模網絡中性能差別不大；當節點個數增加即網絡規模擴大時，性能均有所下降。其中DSR在節點個數超過200個之后，其分組投遞率下降速度陡然加快，而SPDSR雖然也有下降趨勢，但下降速度比較緩慢。在200個節點以后隨著節點個數的繼續增加，SPDSR對DSR的優勢更加明顯。因此在大規模網絡中，SPDSR在分組投遞率方面具有更為良好的表現。

圖4 分組投遞率性能比較

4.2 平均端到端延時（average end－to－end delay，AED）

圖5顯示隨著節點個數的增加，端到端延時整體呈上升趨勢。其中在中小規模網絡環境里，兩種協議的端到端延時較低且差別不大。當網絡規模變大時，DSR的端到端延時陡然增加，而SPDSR的這一性能未發生很大波動，并且有下降的趨勢。這是由于新算法引入了源路由檢測機制、PHello協議以及鄰居節點表，解決了結構化P2P覆蓋層網絡路由技術應用到無線移動自組織網絡過程中帶來的繞路問題，消息轉發次數大大減少，從而降低了端到端延時［13］。

圖5 端到端延時性能比較

4.3 路由開銷（routload）

圖6顯示的是協議在路由開銷方面的表現。從圖中可以觀察到，當網絡規模變大時，SPDSR的路由開銷明顯低于DSR，這是由于新協議將每個移動節點必須保存和維護的路由表項數控制為O（log（N））（N為網絡中節點總數），使它的路由存儲開銷，路由發現和維護開銷大大低于其他協議［14］。

圖6 路由開銷性能比較

4.4 吞吐量（thoughout）

從圖7中我們可以看到和前幾幅圖類似的情況，即在中小規模網絡中，SPDSR的吞吐量與DSR協議差別不大，而隨著節點個數增加，DSR的吞吐量明顯低于SPDSR，這充分體現了SPDSR在大規模網絡中良好的通信性能。

5 結束語

圖7 吞吐量性能比較

本文介紹了一種基于P2P計算模式的新型MANET路由協議——SPDSR，并實現了其在NS2上的設計與仿真。通過觀察DSDV，AODV，DSR這3種協議在分組投遞率，端到端延時，第一個封包到達時間，路由開銷，吞吐量這5個指標的表現，發現DSR的整體性能要優于另外兩種協議［15］，這充分說明選擇DSR作為研究對象并建立新的協議是具有實驗依據的，是在考慮了多種因素的前提下作出的正確選擇。通過大量實驗我們可以得出結論，即SPDSR在大規模無線網絡中的幾個主要性能指標要明顯優于另外3種協議，這與SPDSR的原理相一致。新協議的這一特點增強了網絡的可擴展性，提升了網絡的實用性能?？傊?，SPDSR是一種極具開發潛力的新的路由協議，相信在今后不斷深入研究和實際應用中將得到更好的發展和完善。

［1］LI Zupeng.Study in MANET routing protocol base on P2P computing model ［D］.Beijing：Institute of Computing Technology，Chinese Academy of Science，2007：38－50（in Chinese）.［李祖鵬.基于P2P計算模式的MANTE路由協議研究［D］.北京：中國科學院計算機研究所，2007：38－50.］

［2］PAN Lili.Performance simulation for ZRP route protocols in Ad hoc network ［J］.Computer Engineering and Design，2010，30（12）：2948－2950（in Chinese）.［盤莉 莉.Ad hoc網絡ZRP路由協議的性能仿真 ［J］.計算機工程與設計，2010，30（12）：2948－2950.］

［3］MENG Hao，ZHONG Zhangdui，AI Bo.Performance comparison and evaluation of the routing protocols in Ad Hoc Network ［J］.Information and Electronic Engineering，2009，7（2）：151－155（in Chinese）.［孟昊，鐘章隊，艾渤.Ad hoc網絡路由協議研究及其性能比較 ［J］.信息與電子工程，2009，7（2）：151－155.］

［4］KE Zhiheng，CHENG Rongxiang，DENG Dejuan.NS2simulation experiment－multimedia and wireless network communication ［M］.Beijing：Electronics Industry Press，2009：15－17（in Chinese）.［柯志亨，程榮祥，鄧德雋.NS2仿真實驗－多媒體和無線網絡通信 ［M］.北京：電子工業出版社，2009：15－17.］

［5］LUO Qiao，CHEN Jing，HUANG Chonghui，et al.Study of MANET routing evaluation model Based on Best－First ［C］.IEEE Internationan Conference on Wireless Communications，Networking and Information Security，2010：329－332.

［6］CHEN Jing，LUO Qiao，HUANG Conghui.The research on clustering algorithm of position forecast based on DSR ［J］.Journal of Air Force Engineering University，2011，12（1）：55－58（in Chinese）.［陳靖，羅樵，黃聰會，等.基于DSR的位置預測分簇算法研究 ［J］.空軍工程大學學報（自然科學），2011，12（1）：55－58.］

［7］ZHANG Zhen，WANG Xiaoming.Research on Chord lookup algorithm for peer－to－peer network ［J］.Computer Engineering and Application，2006，42（11）：147－152（in Chinese）. ［張震，王曉明.對等網中Chord資源查找算法研究 ［J］.計算機工程與應用，2006，42（11）：147－152.］

［8］LUO Qiao，CHEN Jing，GUO Yichen，et al.The study of structured P2Prouting protocol based on DHT ［J］.China Science and Technology Information，2011，8（77）：127－128（in Chinese）.［羅樵，陳靖，郭一辰，等.基于DHT的結構化P2P路由協議研究 ［J］.中國科技信息，2011，8（77）：127－128.］

［9］ZHOU Jingxiang，LI Layuan.Optimized in DSR routing protocol of Ad hoc networks ［J］.Computer Application Research，2006，23（12）：292－294（in Chinese）.［周敬祥，李臘元.Ad hoc網絡DSR路由協議的優化 ［J］.計算機應用研究，2006，23（12）：292－294.］

［10］Mohammad Shahidul Hasan，Christopher Harding，Hongnian Yu.Modeling delay and packet drop in network control system using network simulator NS2 ［J］.International Journal of Automation and Computing，2005：187－194.

［11］SONG Ling，LIU Bolan.Study and implementation of adding routing protocols in NS2 ［J］.Journal of Communication and Computer，2006，3（10）：33－37（in Chinese）. ［宋玲，劉勃蘭.NS2中添加路由協議的研究與實現 ［J］.通信和計算機，2006，3（10）：33－37.］

［12］CHEN Yajun，XIAO Jianhua.Network simulation and protocol extension based on NS－2 ［J］.Computer Syetem Application，2005，14（5）：84－87（in Chinese）.［陳亞軍，肖建華.基于NS－2的網絡仿真與擴展 ［J］.計算機系統應用，2005，14（5）：84－87.］

［13］TAN Feng，FU Xuezheng，ZHANG Yanqing，et al.A genetic algorithm－based method for feature subset selection ［J］.Soft Computing，2007，12（2）：111－120.

［14］BAI Rujiang，WANG Xiaoyue，LIAO Junhua.Combination of rough sets and genetic algorithms for text classification ［C］.Proceedings of the 2nd International Conference on Autonomous Intelligent Systems：Agents and Data Mining，2007：256－268.

［15］CHEN Fujiang.Ad Hoc network routing protocol compare study and DSR optimizing ［D］.Nanjing University of Science，2008：50－55（in Chinese）.［陳復將.Ad Hoc網絡路由協議的比較研究與DSR協議的優化 ［D］.南京：南京理工大學，2008：50－55.］