宋子彧，袁道華，成文龍

1.四川大學(xué)計算機(jī)學(xué)院，四川成都 610065

2.軍事經(jīng)濟(jì)學(xué)院襄樊分院基層財務(wù)系，湖北襄樊 441118

一種基于ABR協(xié)議的Ad hoc網(wǎng)絡(luò)路由方案

宋子彧1，2，袁道華1，成文龍1

1.四川大學(xué)計算機(jī)學(xué)院，四川成都 610065

2.軍事經(jīng)濟(jì)學(xué)院襄樊分院基層財務(wù)系，湖北襄樊 441118

ABR協(xié)議是移動自組網(wǎng)中的一種按需路由協(xié)議，采用路徑有效時間長短作為選路標(biāo)準(zhǔn)。本文介紹了ABR協(xié)議，在其基礎(chǔ)上提出了一種保存路由路徑的方案，該方案以耗費(fèi)較小開銷為代價，在一定程度上減小數(shù)據(jù)傳輸時延。最后，對所提出的方案進(jìn)行了簡要的性能分析。

ABR協(xié)議；Ad hoc 網(wǎng)絡(luò)；路由；穩(wěn)定性；按需路由

0 引言

近年來，Ad hoc網(wǎng)絡(luò)一直是國內(nèi)外研究的熱點領(lǐng)域。特別是隨著網(wǎng)絡(luò)時代的發(fā)展，由于人們更樂于享受沒有拘束的無線網(wǎng)絡(luò)環(huán)境，因此，進(jìn)一步研究無線移動自組網(wǎng)絡(luò)從而開發(fā)相應(yīng)的產(chǎn)品，極具現(xiàn)實意義。什么是Ad hoc網(wǎng)絡(luò)呢？Ad hoc網(wǎng)絡(luò)是一種分布式無線多跳網(wǎng)絡(luò)，它是由一組具有路由功能的節(jié)點組成且不依靠任何預(yù)設(shè)的基礎(chǔ)設(shè)施的網(wǎng)絡(luò)。該網(wǎng)絡(luò)中的節(jié)點既為路由器又為主機(jī)，節(jié)點之間相互協(xié)作，通過無線鏈路進(jìn)行通信、交換信息。然而，自組網(wǎng)中節(jié)點的移動性、節(jié)點傳輸范圍的有限性等原因，使得節(jié)點之間的數(shù)據(jù)傳輸不可能簡單依靠固定的路由協(xié)議，必須設(shè)計新的路由協(xié)議，所以，路由協(xié)議成了自組網(wǎng)研究的一個熱點。

1 ABR協(xié)議

目前，支持Ad hoc網(wǎng)絡(luò)的路由協(xié)議有很多。其中，ABR（Associativity Based Routing，基于穩(wěn)定性的協(xié)議）協(xié)議[1]是一種源點發(fā)起的按需路由協(xié)議。它的一個重要特點是打破了以“最短路徑”作為路由選擇的準(zhǔn)則，從路由的有效時間來考慮選路，采用路徑的穩(wěn)定性(路徑有效時間長短)作為選路的標(biāo)準(zhǔn)。當(dāng)源節(jié)點請求路由時，引起路由發(fā)現(xiàn)過程；當(dāng)已經(jīng)確定好的路由因源節(jié)點、目的節(jié)點、中間節(jié)點或subnet-bridging MHs[2]（因自身在兩個虛擬移動子網(wǎng)間移動而將子網(wǎng)分成更小子網(wǎng)的主機(jī)）的移動而改變時，促發(fā)路由重建階段。這就是ABR協(xié)議的兩個主要的組成階段。具體過程如下：

1）路由的建立

源節(jié)點采用洪泛的方式廣播路徑查詢（BQ）分組，收到BQ分組的節(jié)點建立一條到源節(jié)點的路由，并在BQ分組中添加自己的ID和“穩(wěn)定性信息”，然后繼續(xù)廣播BQ分組。中間節(jié)點不允許回復(fù)路由應(yīng)答分組。當(dāng)目的節(jié)點收到第一個BQ分組后，等待一段時間，以收到通過其他路徑到達(dá)的BQ分組的副本，然后選擇一個穩(wěn)定性（associativity[3]）最高的路由，若兩條路由的穩(wěn)定性相同，則選擇跳數(shù)較少的那條。一旦選定某條路由，目的節(jié)點將沿選定的這條路徑發(fā)送一個路由應(yīng)答分組。

2）路由重建

當(dāng)路徑的穩(wěn)定性發(fā)生變化，則啟動路由重建，首先節(jié)點試圖從局部進(jìn)行路由的修復(fù)，若不能成功修復(fù)，則向上游節(jié)點發(fā)送RN（route notification）消息。最壞的情況是源節(jié)點收到RN消息后，啟動一個新的路由建立過程。此外，ABR協(xié)議提到，當(dāng)源節(jié)點不再需要路由時，則通過洪泛RD（Route Deletion）分組的方式刪除路由，或是超時自動完成路由的刪除。

2 提出的方案

在ABR協(xié)議中不使用緩存，對已經(jīng)建立起來的穩(wěn)定值高的路由采取超時或無用即刪除的策略。但是，如果某條穩(wěn)定值高的路由在一定的時間段內(nèi)再次或多次被利用，那么重建這條路由也必將產(chǎn)生不小的開銷。有沒有一種較好的方法能夠既降低開銷又達(dá)到路由重用的目的呢？是否可以考慮通過“犧牲”節(jié)點的少許緩存，不將已建立好的穩(wěn)定值高的路由在使用完后立即刪除，而是通過“監(jiān)視”這條既定路由的穩(wěn)定指數(shù)FOA（figure of associativity），當(dāng)FOA處于某個數(shù)值范圍，則保留這條路由；當(dāng)FOA不在此范圍再刪除之？基于這樣的考慮，提出如下實現(xiàn)步驟：

1）既定路由FOA參量的選定

Ad hoc網(wǎng)絡(luò)中，鏈路是由移動節(jié)點進(jìn)行相互通信形成的。判斷某條鏈路是否穩(wěn)定，歸根到底就是判斷這條鏈路上的各個相鄰節(jié)點之間是否穩(wěn)定。因此，這里先給出節(jié)點間FOA參量的定義。定義FOAx-y表示鄰節(jié)點y對移動主機(jī)x的穩(wěn)定程度。該數(shù)值通過下列方式得到：當(dāng)移動的節(jié)點y剛進(jìn)入x的范圍內(nèi)，x就為該節(jié)點設(shè)一個FOAx-y，初始值可以設(shè)定為0，該FOA隨時間線性增加（如圖1）。移動主機(jī)x周期性的產(chǎn)生一個hello信息，告知其鄰節(jié)點自己的存在。當(dāng)鄰節(jié)點y收到hello信息并回復(fù)后，x就將其為節(jié)點y設(shè)置的FOAx-y減小，且FOAx-y值減小的數(shù)值等于FOAx-y在節(jié)點x周期性發(fā)送hello信息的周期時間間隔中所增加的數(shù)值。也就是說，只要鄰節(jié)點y還在x的范圍內(nèi)，x為節(jié)點y設(shè)置的FOAx-y值就會保持在一定數(shù)值以內(nèi)。鄰節(jié)點y在一段時間內(nèi)沒有回復(fù)移動主機(jī)x的hello信息，則FOAx-y將逐漸增大。如果鄰節(jié)點y只是因為阻塞沒有及時回復(fù)hello信息，則x就在超時較短的時間內(nèi)再次發(fā)送hello信息，收到節(jié)點y的回復(fù)后，x將FOAx-y設(shè)置到警戒值以下。如果y長時間沒有回復(fù)hello信息，則FOAx-y最終將超過禁用值。接下來，定義既定路由的FOA。設(shè)ABCDE為一條已經(jīng)通過ABR協(xié)議選定的路由（如圖2），A為源節(jié)點，E為目的節(jié)點。設(shè)定FOAa-b表示B節(jié)點對A節(jié)點的穩(wěn)定指數(shù)，F(xiàn)OAb-c表示C節(jié)點對B節(jié)點的穩(wěn)定指數(shù)，依次可得到FOAc-d，F(xiàn)OAd-e，則該路由的FOAa-e取 FOAa-b、FOAb-c、FOAc-d、FOAd-e這4個值中的最大值，即鏈路采用凸性加權(quán)得到既定路由的FOA。

2）獲取既定路由FOA的初始值

節(jié)點值之間的穩(wěn)定指數(shù)FOA按照上述方式獲取后，與ABR協(xié)議中的“associativity ticks[2]”一并存儲到節(jié)點緩存中。路由的發(fā)起過程仍然按照ABR協(xié)議所述，源節(jié)點首先廣播BQ分組，尋找一條到目的節(jié)點的路徑。目的節(jié)點DEST在收到第一個BQ分組之后的一個適當(dāng)?shù)臅r間內(nèi)，就知道所有可能的路由和它們的穩(wěn)定程度。DEST選擇穩(wěn)定性最高且跳數(shù)少的路由發(fā)送RREP。此時，由于DEST的這個REPLY分組的長度可變，所以，可以在其中附加一幀記錄鏈路的FOA信息。DEST的沿著選定的路由發(fā)送RREP，其下一個節(jié)點收到RREP后，將其存儲的DEST對它的穩(wěn)定指數(shù)FOA記錄在RREP的附加幀中，然后轉(zhuǎn)發(fā)該RREP。而接下來的節(jié)點收到RREP后，都比較前一發(fā)送節(jié)點對于自己的FOA值與RREP中的FOA值，將FOA值較大的記錄到RREP中。依此類推，直到源節(jié)點。這樣，當(dāng)源節(jié)點收到目的節(jié)點的RREP后，就獲取了該路由的FOA初始值。當(dāng)然，這個數(shù)值肯定是小于前面提到過的警戒值的。

3）既定路由的刪除

源節(jié)點到目的節(jié)點的路由傳送完數(shù)據(jù)后，路由上的節(jié)點并不將該路由刪除，而是將這條路由緩存起來備用。當(dāng)該路由上兩個相鄰節(jié)點不在各自的范圍內(nèi)一段時間后，上游節(jié)點（靠近源節(jié)點端的節(jié)點）對其相鄰的下游節(jié)點的FOA會超過禁用值。此時，上游節(jié)點將這個FOA通過廣播BQ分組發(fā)送出去，而源節(jié)點收到該BQ分組后，發(fā)現(xiàn)路由的FOA超過了禁用值，于是廣播一個路由刪除（RD）分組，通知這條路由上的所有節(jié)點刪除這個路由。

3 方案性能的定性分析

在ABR協(xié)議中加入既定路由穩(wěn)定指數(shù)FOA的判定，能較為有效保存穩(wěn)定性高的路由。下面對方案的性能進(jìn)行定性分析：

1）端到端的平均時延

端到端的平均時延定義為單位數(shù)據(jù)包從源節(jié)點發(fā)出到目的節(jié)點接收的時間差值[4]。時延越小，說明響應(yīng)速度越快。在本方案與原ABR協(xié)議比較，當(dāng)移動節(jié)點的移動速度較快時，由于節(jié)點之間穩(wěn)定值不高，既定路由維持時間短，端到端的平均時延與原ABR協(xié)議基本相同。當(dāng)移動節(jié)點移動速度較慢時，由于對既定路由的保存，本方案中數(shù)據(jù)包傳遞的時延要小于原ABR協(xié)議的數(shù)據(jù)包傳遞時延。

2）路由開銷

路由開銷是指發(fā)送的路由分組的總的個數(shù)。對于在多跳路徑上發(fā)送的分組，每發(fā)送一次計算為一次發(fā)送[5]。該統(tǒng)計量反映路由協(xié)議的效率。與原協(xié)議相比，本方案多出的開銷主要在節(jié)點之間穩(wěn)定指數(shù)的獲取以及既定路由的各節(jié)點對路由的臨時保存上。當(dāng)移動節(jié)點分布較密集且移動速度較慢時，由于各節(jié)點維持其鄰節(jié)點的穩(wěn)定指數(shù)個數(shù)較多，開銷較大，但是，考慮到移動節(jié)點移動緩慢時，本方案減少了路由重建的開銷，實際開銷多少仍需要通過仿真實驗后得出結(jié)論。而當(dāng)移動節(jié)點分布較為疏散時，本方案造成的開銷與原協(xié)議大致相等。

4 結(jié)論

本文通過研究Ad hoc網(wǎng)絡(luò)的ABR協(xié)議，分析該協(xié)議如何采用路徑有效時間長短作為選路標(biāo)準(zhǔn)，提出了一種合理保存穩(wěn)定指數(shù)較高路由路徑的方案。此方案的提出，是考慮到處于Ad hoc網(wǎng)絡(luò)的移動節(jié)點在實際的網(wǎng)絡(luò)環(huán)境中，并不一定時刻都在遷移。在某些地域范圍內(nèi)，例如小區(qū)、辦公樓等，移動節(jié)點是有可能在一段較長的時間內(nèi)保持位置穩(wěn)定的。因此，對于基于ABR協(xié)議建立起來的路由路徑，可以反復(fù)利用。采取本文設(shè)計的方案，雖然會增加穩(wěn)定節(jié)點用于緩存路由的控制開銷，但是可以減小穩(wěn)定節(jié)點本身和其他節(jié)點用于路由重建的開銷。另外，讓穩(wěn)定性強(qiáng)的移動節(jié)點存儲路由，必然會增加這些節(jié)點的負(fù)載。對于這些節(jié)點來說是不公平的。所以，下一步研究的重點是對此方案加入對路由負(fù)載的考慮，并采用網(wǎng)絡(luò)仿真器NS2做相關(guān)的仿真試驗，希望通過這些工作進(jìn)一步優(yōu)化ABR協(xié)議，為在現(xiàn)實的Ad hoc網(wǎng)絡(luò)環(huán)境中有效的應(yīng)用ABR協(xié)議做準(zhǔn)備。

[1] 于宏毅. 無線移動自組織網(wǎng)[M].北京：人民郵電出版社，2005.

[2] Chai-Keong Toh. Associativtity-Based Routing For Ad-Hoc Mobile Networks[J]. Wireless Personal Communications Journal，1997，4（2）：103-139.

[3] Chai-Keong Toh. Associativtity Based Long-Lived Routing. Special Issue on Mobile Networking & Computing Systems， 1997，4（1）.

[4] 段云飛，周麗瓊，楊磊.幾種典型Ad hoc路由協(xié)議的仿真分析[J].電力系統(tǒng)通信， 2009，30(200)：59-63.

[5] 陳林星，曾曦，曹毅.移動Ad hoc網(wǎng)絡(luò)[M].北京：電子工業(yè)出版社，2006.

TP393

A

1674-6708（2010）18-0138-02

宋子彧，碩士研究生，主要研究方向：計算機(jī)網(wǎng)絡(luò)、分布式并行計算

袁道華，教授，主要研究方向：分布式并行計算、計算機(jī)網(wǎng)絡(luò)、移動計算

成文龍，碩士研究生，主要研究方向：多媒體技術(shù)