王 鈺，田 杰 ，徐 磊

（武警工程學院 西安 710086）

1 引言

移動無線自組網(wǎng)[1](mobile Ad Hoc network，MANET)是由具有無線通信能力的移動節(jié)點組成的，是一種能夠迅速展開使用的網(wǎng)絡體系。它不需要依靠現(xiàn)有固定的通信網(wǎng)絡基礎設施，是沒有任何中心節(jié)點的自組織、自愈合網(wǎng)絡。在MANET中，每一個節(jié)點既充當了主機的角色，又充當了路由器的角色。由于節(jié)點的傳輸距離有限，當通信的源節(jié)點和目的節(jié)點間的距離超出傳輸范圍時，它們之間的通信就必須通過中間節(jié)點轉(zhuǎn)發(fā)。由于移動節(jié)點的傳輸能力和能量有限，所以處在網(wǎng)絡拓撲結(jié)構(gòu)中心的若干個節(jié)點，將會收到更多的路由請求，成為更多路徑的中間節(jié)點。它們在負載壓力和能耗方面都將遠遠大于其他節(jié)點，容易超出負載及耗盡能量，進而造成網(wǎng)絡擁塞。如何控制網(wǎng)絡負載和提高網(wǎng)絡生存時間成為了Ad Hoc網(wǎng)絡所面臨的一個重要問題。

2 路由協(xié)議描述

Ad Hoc路由協(xié)議可分為先驗式(proactive)路由協(xié)議和反應式 (reactive)路由協(xié)議兩類，也可稱為表驅(qū)動(table-driven)路由協(xié)議和按需驅(qū)動(on-demand)路由協(xié)議。表驅(qū)動路由協(xié)議的主要特點是要求每個節(jié)點維護一個或多個路由信息，并在網(wǎng)絡拓撲結(jié)構(gòu)發(fā)生改變時及時更新。按需驅(qū)動路由協(xié)議[2]的主要特點是它只有在源節(jié)點需要時才進行路由發(fā)現(xiàn)，路由一經(jīng)建立，就會對其進行維護，直至目的節(jié)點無法到達或該路徑不再被需要為止。相關研究[3]表明，與先驗式路由協(xié)議相比，反應式路由協(xié)議雖然傳送時延較大，但路由開銷小、分組投遞率高，更適合移動自組網(wǎng)絡。本文將要改進的AODV[4]路由協(xié)議就是一種按需驅(qū)動的路由協(xié)議。

AODV路由協(xié)議采用逐跳 （hop-by-hop）方式轉(zhuǎn)發(fā)分組，路由表中記錄了到目的節(jié)點的下一跳信息。它不需要在報文中攜帶完整的路由信息，當源節(jié)點中沒有到達目的節(jié)點的路由時，廣播一個RREQ。每個接收到RREQ的中間節(jié)點記錄下到源節(jié)點的逆向路徑（以便為之后的RREP提供路由），然后查詢路由表中是否有到達目的節(jié)點的路由，若有則利用記錄在報文中的逆向路徑回復RREP，否則重新廣播RREQ。當RREQ到達目的節(jié)點時，目的節(jié)點利用記錄在報文中的逆向路徑發(fā)送RREP。每個接收到RREP的節(jié)點記錄了本節(jié)點到目的節(jié)點的路徑，用以傳送后續(xù)報文。另外，每個節(jié)點都維護有一個目的序列號，當節(jié)點需要建立到目的節(jié)點的路徑和接收到以自己為目的節(jié)點的RREQ時，其值自動加1。該序列號附帶在其發(fā)出的RREQ、RREP中，網(wǎng)絡中其他節(jié)點在收到包含節(jié)點路徑信息的控制報文（RREQ、RREP）時，對比此序列號和本地路由緩存中該節(jié)點路由的序列號，來判別路由的新舊程度，避免環(huán)路的產(chǎn)生。路由請求信息中包含了TTL（time to live），避免了路由請求帶來的全網(wǎng)廣播。AODV協(xié)議通過節(jié)點周期廣播hello消息提供與相鄰節(jié)點的連接信息，檢測鏈路狀態(tài)。

3 改進后的AODV協(xié)議

在移動Ad Hoc網(wǎng)絡中，包含擁塞節(jié)點的一條路由，即使是通往目的節(jié)點的最短路由也未必是最佳路由。因此，在路由選擇的時候應盡力避開擁塞節(jié)點。采用負載相對較輕的路由，不但有利于保證傳輸時延，也均衡了全網(wǎng)的負載，有助于提升網(wǎng)絡整體性能。AODV的開銷主要來自于建立路由的泛洪廣播的路由請求報文RREQ。對其進行改進,提出PS-AODV協(xié)議。節(jié)點收到RREQ分組后先檢查其負載值，若節(jié)點負載過大，則拒絕轉(zhuǎn)發(fā)RREQ分組，直到負載降低以后，再重新轉(zhuǎn)發(fā)RREQ分組。在此引入一種MAC層和路由層之間交換信息的跨層機制，網(wǎng)絡中每個節(jié)點監(jiān)視自己的MAC層接口隊列，加入metric值來對網(wǎng)絡中節(jié)點的能量和負載進行度量。網(wǎng)絡中從源節(jié)點到目的節(jié)點的鏈路負載狀況，取決于鏈路中負載大的節(jié)點。即該鏈路的metric(m)值為 m=max(m1,m2,m3,…，mn)。設該鏈路中第 i個節(jié)點的metric值為mi=li/bi。其中bi為該節(jié)點的可用能量百分比，li為該節(jié)點MAC層接口隊列的當前占用率li=qi/ci，其中qi為節(jié)點i的MAC層接口隊列緩存的分組數(shù)量，ci為節(jié)點i的MAC層接口隊列能容納的最大長度。假設所有節(jié)點的規(guī)格都是一樣的，則ci=c。所以到達目的節(jié)點的為了簡化計算，可將c去掉，則

目的節(jié)點或者擁有到達目的節(jié)點路由信息的中間節(jié)點，在回復RREP分組的時候，若存在多條路徑，可憑借metric值進行最優(yōu)選擇。PS-AODV在路由請求RREQ中添加一個字段metric(m)，來記錄所經(jīng)過節(jié)點的最大負載，當源節(jié)點發(fā)起路由請求時，它計算m值，并把m值寫入RREQ分組中，然后進行廣播。同時在節(jié)點路由表中添加一個字段mt，記錄從源節(jié)點到該節(jié)點的m值。中間節(jié)點收到RREQ后，計算m值來確定當前節(jié)點的負載狀況和可用能量。根據(jù)節(jié)點的m值以及是否有目的節(jié)點的路由信息，決定該節(jié)點是否可以作為中間節(jié)點。節(jié)點有3種狀態(tài)。癱瘓:m≥a；擁塞:b≤m≤a；正常:m

網(wǎng)絡中每個節(jié)點可根據(jù)其負載狀況和可用能量決定轉(zhuǎn)發(fā)或丟棄收到的RREQ分組。當一個中間節(jié)點處于“癱瘓”狀態(tài)時，除非它是該鏈路的目的節(jié)點，否則將不處理任何路由請求，丟棄所有收到的RREQ，使其不能再成為中間節(jié)點。當節(jié)點處于“擁塞”狀態(tài)時，只有其路由表中已經(jīng)存在了此路由請求目的節(jié)點的路由信息或它是該鏈路的目的節(jié)點，它才會回復其路由請求，否則將丟棄該路由請求，以此來減少由于RREQ廣播造成的網(wǎng)絡負載和降低路由發(fā)現(xiàn)的端到端時延。當節(jié)點處于“正?！睜顟B(tài)時，如果首次收到新的RREQ，則把路由表中的相應路由值設為該RREQ中的m值。然后比較m和該節(jié)點的metric值，將大的m值記錄在RREQ的mt中，最后轉(zhuǎn)發(fā)RREQ。如果節(jié)點已經(jīng)收到過來自同一源節(jié)點的相同廣播ID的RREQ，則比較m和mt。如果m值較小，則丟棄RREQ。否則，更新路由表的mt值，并將指向前一跳節(jié)點的指針指向發(fā)送該RREQ的節(jié)點，并且不再轉(zhuǎn)發(fā)該RREQ。收到第一個RREQ后，目的節(jié)點等待一段時間來獲得可能的更多路由，然后從中選擇擁有最小m值的路由回復RREP。

4 仿真和分析

下面在NS2[5]上進行仿真。以下描述仿真環(huán)境、性能參數(shù)和試驗結(jié)果。物理信道的帶寬為2 Mbit/s。鏈路層采用IEEE 802.11MAC層協(xié)議的分布式協(xié)調(diào)功能(distributed coordination function，DCF)。PS-AODV 的 b 值取 0.5，a值取0.7。將50個節(jié)點隨機地分布在1 200 m×800 m的范圍內(nèi)，節(jié)點的通信范圍是250 m，最大移動速度為 5 m/s，節(jié)點初始能量為200 J，暫停時間為50 s，仿真運行500 s。信源采用固定比特率(constant bit rate，CBR)，每個分組長度為512 byte，一共啟動40個CBR流。仿真通過改變信源發(fā)送分組的頻率來改變網(wǎng)絡負荷。

4.1 仿真參數(shù)

以下是本文選取的協(xié)議性能比較參數(shù)：

平均端到端時延=路由發(fā)現(xiàn)過程所需時間+分組在緩存中的排隊時間+鏈路層重傳時間+傳播時間；

4.2 仿真結(jié)果

圖1反映了隨著網(wǎng)絡負載增加，AODV和PS-AODV分組傳送率的變化曲線。結(jié)果顯示隨著網(wǎng)絡負載的增加，兩者的分組傳送率都在下降，當負載為0～480 kbit/s時，AODV和PS-AODV的分組傳送率下降不明顯，差距不大，但隨著負載增加，兩者的分組傳送率都急劇下降，但PS-AODV的下降幅度比AODV小，當負載達到1 440 kbit/s時，PS-AODV的分組傳送率比AODV高7%。由此可見，PS-AODV在分組傳送率上比AODV擁有更大的優(yōu)勢，尤其是在高負載情況下優(yōu)勢更加明顯。這是因為AODV沒有考慮負載均衡問題，在高負載環(huán)境下，處于網(wǎng)絡中心的若干節(jié)點負荷急劇增加，當流量超出節(jié)點傳輸極限時，其分組丟失率迅速提高，導致分組傳送率急劇下降。而PS-AODV根據(jù)metric值選擇傳輸路徑，并且高負載的節(jié)點能有選擇地回復RREQ分組，有效地對數(shù)據(jù)流量進行了分流，均衡了負載，間接提高了分組傳送率。

圖2顯示了隨著網(wǎng)絡負載的增加，AODV和PS-AODV的平均端到端時延變化情況。隨著網(wǎng)絡負載增加，兩者的平均端到端時延開始上升，PS-AODV的平均端到端時延總體低于AODV,當負載達到1 440 kbit/s時，PS-AODV比AODV的平均端到端時延低240 ms，該圖反映出PS-AODV比AODV擁有更低的平均端到端時延。這是因為PS-AODV根據(jù)metric值選擇路徑，而metric值的決定性因子是MAC層接口隊列緩存的分組數(shù)量，而端到端時延主要由排隊時間產(chǎn)生，所以PS-AODV會選擇排隊時間較小的路由，從而減小了網(wǎng)絡時延。

圖3顯示了PS-AODV和AODV的路由開銷隨網(wǎng)絡負載變化時的變化情況。隨著網(wǎng)絡負載增加，數(shù)據(jù)分組所占比例不斷提高，兩者的路由開銷降低。PS-AODV的路由開銷總體低于AODV，當負載為1 120 kbit/s時兩者差距達到最高的0.9。由于AODV的路由開銷主要來自于建立路由時泛洪廣播的路由請求報文RREQ。在PS-AODV中，處于“癱瘓”和“擁塞”狀態(tài)中的節(jié)點會有選擇性地丟棄RREQ分組。且PS-AODV提高了分組傳送率，減少了路由重傳的次數(shù)，從而減少了初始化路由發(fā)現(xiàn)的次數(shù)，有效地降低了RREQ分組的產(chǎn)生。在路由發(fā)現(xiàn)過程中，收到同一源節(jié)點相同廣播ID的中間節(jié)點，會通過比較metric值后刪除m值大的路徑，減少了RREQ的轉(zhuǎn)發(fā)，從而減少了網(wǎng)絡路由開銷，所以PS-AODV的路由開銷要低于AODV。

圖4顯示了網(wǎng)絡生存時間隨網(wǎng)絡負載變化情況，在此項分析中，選用了第一個節(jié)點與第n/2個節(jié)點死亡時間的中值作為網(wǎng)絡生存時間，這是因為當網(wǎng)絡中第n/2個節(jié)點死亡以后，整個網(wǎng)絡將會急劇惡化，失去其使用價值。當網(wǎng)絡負載增加時，PS-AODV和AODV的網(wǎng)絡生存時間都降低，PS-AODV的網(wǎng)絡生存時間要長于AODV,這主要由于PS-AODV會根據(jù)節(jié)點負載情況選擇負載更小的節(jié)點，使整個網(wǎng)絡的能量消耗更加均衡，避免了網(wǎng)絡中心的節(jié)點過早耗盡的能量，從而延長了網(wǎng)絡的生存時間。

5 結(jié)束語

本文在AODV基礎上提出了一個基于路徑選擇和應答拒絕算法的改進MANET路由協(xié)議PS-AODV。它根據(jù)本地節(jié)點的負載情況和可用能量來決定是否應答，并根據(jù)RREQ分組和節(jié)點中的metric值進行路徑選擇，從而實現(xiàn)負載均衡的目的。PS-AODV降低了因為網(wǎng)絡中心的節(jié)點能耗過快、負載過重而造成的網(wǎng)絡擁塞概率。仿真顯示PS-AODV在分組傳送率、平均端到端時延、路由開銷和網(wǎng)絡生存時間等性能指標上較AODV有一定提高。今后的工作主要是將PS-AODV協(xié)議與其他負載平衡協(xié)議[6]對比，并對協(xié)議進行進一步改進，提高其性能。

1 陳林星,曾曦,曹毅.移動Ad Hoc網(wǎng)絡.北京:電子工業(yè)出版社,2006

2 Best P,Gundeti S,Pendse R.Self-learning Ad Hoc routing protocol.In:Proc of the 58th Vehicular Technology Conference,Orlando,Florida,USA,2003

3 Eshghi F,Elhakeem A K.Performance analysis of Ad Hoc wireless LANs for real-time traffic.IEEE Journal on Selected Areas in Communications,2003,21(2):204～215

4 IETF RFC 3561.Ad Hoc on-demand distance vector(AODV)routing,2003

5 于斌，孫斌，溫暖等，NS-2與網(wǎng)絡模擬.北京：人民郵電出版社，2007

6 Lee S J,Gerla M.Dynamic load-aware routing in Ad Hoc networks.In:IEEE International Conference on Communications(ICC),Helsinki,Finland,2001