吳 磊，皮 智

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

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

吳 磊，皮 智

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

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

動態(tài)源路由協(xié)議；移動自組織網(wǎng)絡；權重；均衡能量；NS2；仿真

0 引 言

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

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

1 DSR協(xié)議簡介

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

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

2 DSR-I的設計

2.1 基于權重的策略

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

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

(1)

Delay(k)=Delay(s,d)

(2)

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

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

(3)

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

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

2.2 基于鏈路反饋的策略

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

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

(4)

圖1 節(jié)點i和j之間鏈路的ECPC值

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

flag=Pf×Ps

其中，Pf代表前向傳輸?shù)母怕?；Ps為后向傳輸?shù)母怕?。flag越高，代表鏈路的狀態(tài)越好。

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

2.3 基于均衡能量的策略

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

3 仿 真

3.1 仿真工具和仿真參數(shù)的設置

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

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

表1 仿真參數(shù)

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

3.2 性能評價指標

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

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

(5)

其中，Rni為節(jié)點i成功接收的報文數(shù)；Sni為節(jié)點i成功發(fā)送的報文數(shù)。

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

(6)

其中，Dni為節(jié)點i的路由發(fā)現(xiàn)次數(shù)；Time為協(xié)議的仿真時間。

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

Normalized Rooting Load = (SCn+ FCn)/RDn

(7)

其中，SCn為發(fā)送的路由報文數(shù)；FCn為轉發(fā)的路由報文數(shù)；RDn為接收到的數(shù)據(jù)報文數(shù)。

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

(8)

其中，N為成功傳輸?shù)臄?shù)據(jù)報文的總數(shù)；Rti為第i個報文接收的時間；Sti為第i個報文發(fā)送的時間。

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

3.3 仿真結果對比與分析

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

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

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

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

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

圖3 DSR和DSR-I路由發(fā)起頻率對比

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

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

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

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

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

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

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

圖6 DSR和DSR-I節(jié)點剩余能量對比

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

4 結束語

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

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

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

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

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

[3] 趙菊敏，張子辰，李燈熬，等.基于LEACH路由協(xié)議的多跳節(jié)能路由算法[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路由協(xié)議改進[J].計算機應用研究，2011,28(1)：256-258.

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

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

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

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

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

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

[12] 李向麗，李超超.基于小世界理論和QoS支持的DSR協(xié)議[J].傳感器與微系統(tǒng)，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].工業(yè)控制計算機，2013,26(1)：77-79.

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

[16] 王 英，黃 群，李 云，等.一種新的協(xié)作的路由協(xié)議: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)；北京市屬高等學校創(chuàng)新團隊建設與教師職業(yè)發(fā)展計劃項目(IDHT20130502)作者簡介：吳 磊(1963-)，男，副教授，碩士研究生導師，研究方向為嵌入式系統(tǒng)和無線通信技術；皮 智(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