一種基于負(fù)載均衡的移動(dòng)Ad Hoc網(wǎng)絡(luò)AODV協(xié)議改進(jìn)

王 鈺，田 杰 ，徐 磊

（武警工程學(xué)院 西安 710086）

1 引言

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

2 路由協(xié)議描述

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

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

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

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

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

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

4 仿真和分析

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

4.1 仿真參數(shù)

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

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

4.2 仿真結(jié)果

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

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

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

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

5 結(jié)束語(yǔ)

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

1 陳林星,曾曦,曹毅.移動(dòng)Ad Hoc網(wǎng)絡(luò).北京:電子工業(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)絡(luò)模擬.北京：人民郵電出版社，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