一種改進型DSR-I路由協議的設計與仿真

吳 磊，皮 智

(北方工業大學 計算機學院，北京 100144)

一種改進型DSR-I路由協議的設計與仿真

吳 磊，皮 智

(北方工業大學 計算機學院，北京 100144)

動態源路由協議(DSR)是為移動自組織網絡設計的路由協議，性能較優，但是DSR協議中存在路由不穩定、時延大以及能量不平衡等問題。針對DSR的這些不足，通過對DSR協議的研究分析，提出了一種基于權重、鏈路反饋和均衡能量的DSR改進型路由協議(DSR-I)。在滿足權重的路徑查找中選擇能量高的節點充當中繼，在數據包發送的過程中低能量的節點反饋能量狀態，源端主動斷開舊鏈路，從而變更路徑，并采用NS2平臺對DSR和DSR-I進行了仿真實驗和性能分析。實驗結果表明，改進后的DSR-I路由協議比較明顯地改進了原DSR路由協議的性能。

動態源路由協議；移動自組織網絡；權重；均衡能量；NS2；仿真

0 引 言

移動自組織網絡(Ad hoc Network)是指多個無線收發裝置的移動終端節點組成的，不需要依靠通信網絡基礎設施的自組織和自管理網絡[1]。因此，網絡中的節點可以通過路由發現機制轉發分組，并進行路由維護。近年來，Ad hoc網絡以其低成本、低功耗、分布式和自組織的優點，在國內被很多高校、科研單位廣泛應用；在國外也受到關注，同時涉及多個學科交叉和相關知識高度集成的熱點研究方向。但是網絡中的節點通常由電池供電，節點部署的位置往往具有隨機性，能量難以再次添加，有些節點可能因自然原因損壞或者被人為破壞。而路由技術是無線自組網的核心技術之一，維護網絡的穩健性和均衡網絡中能量的消耗是設計一個好的路由協議應該要考慮的首要問題。

DSR協議對延遲、帶寬、丟包率和能量等都沒有加以限制，即無QoS限制。這會導致網絡的節點擁塞、時延大等問題。同時也會導致其中某些節點的能量或者網絡的能量被迅速耗盡，造成網絡很快分裂，影響整個數據的傳輸效率，縮短了該網絡的生存時間。所以提出了基于權重、鏈路反饋和均衡能量的DSR改進路由協議DSR-I(DSR-Improve)。

1 DSR協議簡介

DSR(Dynamic Source Routing)是為移動Ad hoc設計的，同時是一種簡單高效、無線多跳的路由協議。它是一種基于源端的路由協議，給每一個傳輸分組的頭部插入完整的源路由信息，保證傳輸過程中按完整的路徑傳輸。該方法可以避免環路的產生，并在網絡變化和節點移動的情形下，也可以將分組正確地傳送，提高了移動通信節點對于網絡拓撲動態變化的適應能力[2]。

DSR路由協議包括兩個主要機制：第一是路由發現，當源節點需要發送數據時才啟動，實現源節點獲取到達目的節點的路由信息；第二是路由維護，源節點發送數據到達目的節點時監測此時路由的可用狀況，當出現網絡拓撲變化導致路由故障時自動尋找另一條路由或者重新發起路由發現過程[3-10]。

2 DSR-I的設計

2.1 基于權重的策略

在分析QoS問題時，為了方便研究，可以把Ad hoc場景下的Ad hoc網絡表示成一個加權圖G(V,E)。其中，V為Adhoc移動節點的集合;E為代表Adhoc移動節點間形成的鏈路的集合，且每個Adhoc節點的傳輸半徑相同。假設在給定的源節點與目的節點之間存在路徑K(s→i→…→j→d)，該路由需滿足以下約束條件:

Bank(k)=min{Bank(s,i),…,Bank(j,d)}

(1)

Delay(k)=Delay(s,d)

(2)

則該Adhoc路由協議可以抽象為在加權圖G(V,E)中，在給定的源節點與目的節點之間尋找滿足QoS約束要求的可行路由(B≤Band(K),D≥Delay (K))，然后通過計算各條可行路由的權重值Weight，選取Weight值最大的可行路由進行數據傳輸。針對DSR協議沒有考慮的QoS保障，對DSR協議從權重策略方面進行了研究分析。將其DSR路由轉發的優先級設計轉發的權重公式如下:權重與鏈路的延時、跳數、能量以及帶寬成正比。

Weight=a1×T1+a2×H2+a3×E3+a4×W4

(3)

其中，T1表示延時；H2表示跳數；E3表示能量；W4表示帶寬。

當不滿足B≤Band(K),D≥Delay(K)中的任意一項，則不進行轉發，從而刪除不滿足延時、帶寬條件下的路徑；權重大的節點獲得轉發路徑的優先級，從而更容易被選中成為網絡中的中繼節點。

2.2 基于鏈路反饋的策略

在路徑維護的過程中，對鏈路的生存狀態進行預測。由于傳統的DSR路由協議是以最小跳數作為度量參數來建立路由，而忽略了路由上鏈路的傳輸質量，導致路由整體性能不佳。因此提出選用期望控制報文次數(Expected Control Packet Count，ECPC)作為評估鏈路質量的度量參數。

如圖1所示，假設節點i和j之間可以建立有效的通信傳輸數據，則ECPC表示在無線網絡中節點i和j之間進行一次成功的數據報文傳遞時，需要的傳輸次數預期值。ECPC的取值需要通過計算節點之間的前向傳輸率Pf和反向傳輸率Ps來獲取。假設在一定的滑動窗口時間內，節點i會向節點j發送數據，則節點j成功接收數據的成功率為Pf，當節點j收到數據后會反向給節點i發送應答報文，則節點i接收到應答報文的成功率為Ps，因此此條鏈路間的ECPC可以通過式(4)計算得到：

(4)

圖1 節點i和j之間鏈路的ECPC值

由于一條路由的ECPC值由該路由上鏈路之間的ECPC累加值決定。若ECPC累加值越小，則鏈路間的分組傳遞率就越高，路由性能就越高效可靠。若鏈路的狀態計算公式為：

flag=Pf×Ps

其中，Pf代表前向傳輸的概率；Ps為后向傳輸的概率。flag越高，代表鏈路的狀態越好。

在DSR選出的多向路徑中，若Pf×Ps值穩定，則代表鏈路越穩定。源端收到數據包時，通過比較收到反饋的包，如果源端收到更穩定的路徑返回，則源端更新自己的路由表及下一跳。

2.3 基于均衡能量的策略

當能量低于某一值時或者發生鏈路的中斷時，標記鏈路的狀態，置flag為0。在數據包的轉發過程中，攜帶節點的能量信息。當節點的能量低于閾值時，認為節點的能量將消耗完。其他轉發節點攜帶收到的低能量的信息并轉發直至數據包的源節點。當源節點接收此數據包時，從路由中表中刪除低能量節點的鏈路。再重新發起路徑請求，尋找更優的路徑充當中繼。能量閾值的反饋作用對網絡的鏈路狀態起到了預警作用，從而讓源節點主動變更路徑。

3 仿 真

3.1 仿真工具和仿真參數的設置

目前國內外大部分研究機構均采用NS2對無線自組網的路由協議進行仿真。移植算法在NS2框架下，設置的場景如下：數據流為創建了一個具有50個移動節點、10對通信連接和每秒鐘發送2個分組的，以CBR為業務源的通信場景文件。移動場景設置為一個具有50個節點、節點在每個地點停留0 s(即不停留)、最大移動速度20 m/s、仿真時間300 s、長1 000 m和寬300 m的移動場景文件。其中暫停的時間可變，用于比較DSR路由協議改進前向的參數性能。

為了模擬節點能量的差異性，該測試環境下設置了兩種不同概率的能量:一種為普通能量的，設置節點的比率為80%，初始的能量結合TCL腳本設置為80 J；另一種為高能量的，設置的比率為20%，初始的能量結合TCL腳本設置為80 J。仿真參數見表1。

表1 仿真參數

在實驗仿真過程中，setdest用來設定節點運動場景文件，cbrgen用來生成傳輸負載，awk用于從TCL腳本生成的trace文件中提取數據，最后使用Matlab工具繪制成圖。

3.2 性能評價指標

節點的分組投遞率、路由發起頻率、歸一化路由開銷、平均延時和節點的剩余能量等參數是衡量路由協議性能及網絡的重要指標[11-14]。所以對DSR路由協議和DSR-I路由協議也是從這五個方面進行仿真實驗和結果分析。

分組投遞率(Packet Delivery Ratio)的計算公式為：

(5)

其中，Rni為節點i成功接收的報文數；Sni為節點i成功發送的報文數。

路由發起頻率(RouteDiscoveryFrequency)的計算公式為：

(6)

其中，Dni為節點i的路由發現次數；Time為協議的仿真時間。

歸一化路由開銷(NormalizedRootingLoad)的計算公式為：

Normalized Rooting Load = (SCn+ FCn)/RDn

(7)

其中，SCn為發送的路由報文數；FCn為轉發的路由報文數；RDn為接收到的數據報文數。

端到端平均延時(AverageDelay)的計算公式為：

(8)

其中，N為成功傳輸的數據報文的總數；Rti為第i個報文接收的時間；Sti為第i個報文發送的時間。

能量模型是采用NS2.34版本自帶的，NS2中實現的能量模型是一個節點屬性，能量模型也表示了一個移動主機的能量水平[15-18]。在開始仿真時，所有節點的能量模型對應一個能量初始值，模擬過程中還會產生每個包發射和接收的能耗。

3.3 仿真結果對比與分析

分組投遞率的仿真實驗結果對比如圖2所示。

圖2 DSR和DSR-I分組投遞率對比

從圖2可以看出，當暫停時間越大，表明節點移動性越慢，當節點的移動暫停時間為300 s，而仿真的總時間為300 s，表明節點不移動，此時分組投遞率的成功率越高。當節點的移動暫停時間為0 s時，節點一直在移動，此時分組投遞率的成功率較低，丟包率比較明顯。DSR-I由于考慮基于鏈路的反饋作用，相對于DSR選出的路徑更加穩定，表現為接收的分組投遞率高。

路由發起頻率的仿真實驗結果對比如圖3所示。

從圖3可以看出，當暫停時間越大，表明節點移動的越緩慢，路徑變更不明顯，由此帶來的路由發起頻率越低。DSR-I由于考慮到網絡中節點的能量以及鏈路的質量通信情況，相比DSR進行了預警信息，并且主動變更了即將斷開的鏈路與通信質量不佳的鏈路，因此路徑變更的概率減小，表現為DSR-I路由協議發起的頻率較低。

圖3 DSR和DSR-I路由發起頻率對比

歸一化路由開銷的仿真實驗結果對比如圖4所示。

圖4 DSR和DSR-I歸一化路由開銷對比

從圖4可以看出，當暫停時間越大，表明節點移動性越慢，路由越穩定，路由開銷越小。DSR-I由于考慮到網絡中節點的能量以及鏈路的質量通信情況，由于網絡中節點的能量消耗完或者節點的移動，更易于對鏈路的變化進行快速響應。因而選出的路徑更加穩定，需要用于控制包來變更路徑的變化指令更少，表現為DSR-I路由協議開銷降低。

端到端平均延時的仿真實驗結果對比如圖5所示。

圖5 DSR和DSR-I平均延時對比

從圖5可以看出，當暫停時間越大，表明節點移動性越慢，路由越穩定，端到端的平均延時越小。當節點的移動暫停時間為0 s時，節點一直在移動，由于路徑的不斷變更，端到端的平均延時越大。DSR-I考慮到刪除帶寬較小、延時較大、跳數較大等的路徑，剔除了一些不滿足最佳QoS的次要路徑，從而選出的路徑為優化后的結果，表現為DSR-I端到端的延時更短。

節點的剩余能量仿真實驗結果對比如圖6所示。

圖6 DSR和DSR-I節點剩余能量對比

從圖6可以看出，DSR-I選擇出來的路徑更加穩定，用于路由發起的控制包減少，網絡中的能量避免了因偵聽到過多的控制廣播而產生大量的能量消耗。使得DSR-I相比DSR，網絡中的節點剩余能量得到更好的節省，進一步延長了網絡的生存時間。

4 結束語

DSR是為無線Ad hoc網絡設計的路由協議，但是沒有QoS保障。當節點的能量有差異化時，容易選中能量低的節點充當中繼，從而影響網絡的生存時間。其次，能量低的節點在能量將耗盡時，也無法感知網絡的鏈路即將變更信息。

在分析總結國內外針對DSR協議所做相關工作的優缺點的基礎上，文中提出一種基于權重、鏈路反饋和均衡能量的DSR-I改進協議。

DSR-I路由協議在查找路徑、正向發送路由請求的過程中，選擇帶寬、時延、跳數、能量四個方面的因素，滿足時延和帶寬要求并且剩余能量大的節點充當中繼節點的權重較高，延時較低，從而獲得比較高的優先級。在數據包發送的過程中，低能量的節點反饋能量狀態，并且剩余能量大，獲取鏈路質量好的反向路徑。當能量較低或者通信質量不好時，主動報告源端，源端主動斷開舊鏈路，從而變更路徑。仿真結果表明，改進后的DSR-I協議有效地改進了DSR路由不穩定、時延大和能量不平衡等缺點，有效地提升了DSR的性能。

[1] 柯志亨，程榮祥，鄧德雋.NS2仿真實驗-多媒體和無線網絡通信[M].北京：電子工業出版社，2009.

[2] 張簡麗，許洪光.基于DSR的路由協議綜述[J].通信技術，2009,42(1)：137-139.

[3] 趙菊敏，張子辰，李燈熬，等.基于LEACH路由協議的多跳節能路由算法[J].計算機測量與控制，2014,22(5)：1506-1509.

[4] Zhang Dongli,Jiao Wencheng,Zheng Jianling.Research and improvement of DSR protocol in Ad hoc network[C]//Proc of 2010 2nd international conference on industrial and information systems.[s.l.]:[s.n.],2010:242-244.

[5] 李 梅，周繼鵬.基于負載均衡的DSR路由協議改進[J].計算機應用研究，2011,28(1)：256-258.

[6] 沙 毅，張 婷，陳 進，等.基于流量的Ad hoc網絡負載均衡路由協議[J].東北大學學報:自然科學版，2010,31(3)：350-353.

[7] 劉 榮，王 東，李曉鴻．移動Ad Hoc網絡中基于剩余生存時間的鏈路穩定性路由協議[J]．計算機工程與科學，2012, 34(12) 9-15．

[8] 楊東勇，陳曉倩，顧東袁．一種節能的無線傳感器網絡路由協議的設計與實現[J]．計算機工程與科學，2010, 32(4) 110-113．

[9] 鄧亞平,楊 佳,胡亞明.動態分簇的異構傳感器網絡安全路由協議[J].重慶郵電大學學報：自然科學版,2011,23(3):336-342.

[10] 田 敏,劉占軍,李 云,等.一種基于節點度數的Ad Hoc網絡穩定路由協議[J].重慶郵電大學學報：自然科學版,2007,19(5):558-561.

[11] 王魯光，賈智平，李 新.AODV和AOMDV路由協議性能分析與比較[J].計算機應用，2010,30(3)：740-744.

[12] 李向麗，李超超.基于小世界理論和QoS支持的DSR協議[J].傳感器與微系統，2014,33(2)：43-46.

[13] Ahmad S,Awand I.Performance analysis of DSR & extended DSR protocols[C]//Proceedings of IEEE military communications conference.[s.l.]:IEEE,2007.

[14] 葉海濱，張華熊，馬漢杰，等.基于NS2的能量模型的研究[J].工業控制計算機，2013,26(1)：77-79.

[15] 朱 睿，呂秋冬，張連芳.基于DSR協議的區域路由研究[J].微計算機信息，2007,23(3-3)：114-116.

[16] 王 英，黃 群，李 云，等.一種新的協作的路由協議:C-DSR[J].計算機應用研究，2013,30(7)：2148-2150.

[17] Tamilarasi M,Palanuivelu T G.A strategy to reduce the control packet load of MANETs with bidirectional links using DSR[J].International Journal of Network Management,2008,18(4):365-376.

[18] Gupta A.MIKBIT-Modifiled DSR for MANET[C]//Proc of IEEE 4th international conference on internet multimedia services architecture and application.[s.l.]:IEEE,2010.

Design and Simulation of an Improved DSR-I Routing Protocol

WU Lei，PI Zhi

(Computer Institution,North China University of Technology,Beijing 100144,China)

The DSR is a protocol designed for Ad hoc network,which possesses good performance.But it has problems including instable routing,long delay and unbalanced energy.Aimed at these shortages of DSR,through the research and analysis to DSR,an improved routing protocol is proposed based on weight,link feedback and equilibrium energy.The main idea is that nodes with higher energy are selected to act as a repeater in the path of meeting the weight and nodes with lower energy are used to feed back energy state in the process of data packets transmission.The source disconnects actively with the old link,thus changing the path.The NS2 platform is used to make a simulation experiments and performance analysis between DSR-I and DSR.These simulation results show that the improved DSR-I protocol promotes the performance obviously compared with the original DSR.

DSR;Ad hoc network;weight;equilibrium energy;NS2;simulation

2015-05-28

2015-08-31

時間：2016-01-26

北京市自然科學基金資助項目(4131001)；中央支持地方專項(PXM2014_014212_000097)；北京市屬高等學校創新團隊建設與教師職業發展計劃項目(IDHT20130502)作者簡介：吳 磊(1963-)，男，副教授，碩士研究生導師，研究方向為嵌入式系統和無線通信技術；皮 智(1990-)，男，碩士研究生，研究方向為嵌入式技術。

http://www.cnki.net/kcms/detail/61.1450.TP.20160126.1522.076.html

TP391.9

A

1673-629X(2016)02-0017-05

10.3969/j.issn.1673-629X.2016.02.004