banner.jpg)
相關(guān)專題：
華北計算技術(shù)研究所通信工程研究室
摘要 隨著無線通信技術(shù)的發(fā)展和移動終端性能的提高，Ad hoc的應(yīng)用越來越廣泛。無線Ad hoc 是一種不依賴于任何基礎(chǔ)設(shè)施，無中心自組織的多跳無線網(wǎng)絡(luò)。本文從Ad hoc 網(wǎng)絡(luò)的特點出發(fā)，在分析當(dāng)前路由協(xié)議設(shè)計思想的基礎(chǔ)上，對Ad hoc 的路由協(xié)議FSR進行了研究。
關(guān)鍵詞 Ad hoc 多跳無線網(wǎng) 網(wǎng)絡(luò)拓撲 路由更新 魚眼域 FSR
1 前言
Ad hoc 網(wǎng)絡(luò)是一種無中心自組織的多跳無線網(wǎng)絡(luò)，它不以任何已有的固定設(shè)施為基礎(chǔ)而能隨時隨地組建臨時性的網(wǎng)絡(luò)。由于這種方便性，并且隨著無線通信技術(shù)的發(fā)展和移動終端性能的提高，特別是人們對個人通信日益增長的需求，使得移動ad hoc網(wǎng)絡(luò)的應(yīng)用范圍正逐步擴大。在軍用領(lǐng)域，它可以支持野外偵察聯(lián)絡(luò)、獨立戰(zhàn)斗群通信和艦隊?wèi)?zhàn)斗群通信、無人偵察與情報傳輸?shù)龋辉诿裼妙I(lǐng)域，它支持諸如移動會議、移動網(wǎng)絡(luò)、個人局域網(wǎng)、災(zāi)難營救過程中的信息交換以及臨時交互式通信組等。我們可以預(yù)測，這種技術(shù)在未來移動通信的領(lǐng)域中將起到非常重要的作用。
2 Ad hoc 網(wǎng)絡(luò)的特點
Ad hoc 網(wǎng)絡(luò)是一群終端為了完成一項任務(wù)而臨時組建的一種網(wǎng)絡(luò)。它不需任何已有的固定設(shè)施作為基礎(chǔ)，隨時隨地進行組建，因而網(wǎng)絡(luò)中的每個節(jié)點都是平等的，沒有中心。從技術(shù)上講，Ad hoc 網(wǎng)絡(luò)是一種移動通信技術(shù)和計算機網(wǎng)絡(luò)技術(shù)相結(jié)合的網(wǎng)絡(luò)。一方面，它采用無線信道進行通信，而且用戶終端都可以隨意移動；另一方面，各節(jié)點的信息交換采用了計算機網(wǎng)絡(luò)中的分組交換機制，因此Ad hoc中的各節(jié)點兼有主機和路由器兩種功能。
Ad hoc除了是無中心、自組織平等式的網(wǎng)絡(luò)外，它還有如下的特點：
�。�1）網(wǎng)絡(luò)拓撲動態(tài)變化頻繁。 Ad hoc 網(wǎng)絡(luò)中，用戶終端的移動性具有很大的隨機性，它們可以隨時移動，也可以隨時開機和關(guān)機。再加上無線發(fā)射裝置發(fā)送功率的變化、無線信道間的相互干擾以及地形等因素的影響，網(wǎng)絡(luò)的拓撲結(jié)構(gòu)可能隨時發(fā)生變化，而且這種變化無法預(yù)先知曉。
（2）多跳的無線網(wǎng)。 網(wǎng)絡(luò)中節(jié)點如果在相互輻射覆蓋范圍內(nèi)，則它們可以通過無線信道直接進行通信；否則，它們必須借助中間節(jié)點的轉(zhuǎn)發(fā)才能通信。在Ad hoc網(wǎng)絡(luò)中，這種轉(zhuǎn)發(fā)不是由專門的路由器完成的，而是由平等的普通節(jié)點完成的。
�。�3）傳輸帶寬有限。Ad hoc 網(wǎng)絡(luò)的通信手段是無線傳輸技術(shù)，而無線信道本身的帶寬相對有限網(wǎng)絡(luò)非常之有線，再加上無線信道中的信號的沖突、干擾、衰減等因素使得無線帶寬非常寶貴。
�。�4）存在單向鏈路。在無線通信中，由于通信設(shè)備頻率的強弱和地形環(huán)境因素的影響，使得單向鏈路常常存在。比如，車載臺終端發(fā)送功率比手持終端大很多，所以有時手持終端可以收到來自車載臺的信號而車載臺卻無法接受到手持終端的信號，即存在一條從車載終端到手持終端的單向信道。
Ad hoc 網(wǎng)絡(luò)的多跳性使得借鑒固定網(wǎng)絡(luò)的路由協(xié)議成為可能，但其網(wǎng)絡(luò)拓撲動態(tài)變化、傳輸帶寬有限、單向鏈路的存在使得固定網(wǎng)絡(luò)的路由協(xié)議不能直接應(yīng)用到無線Ad hoc 網(wǎng)絡(luò)中。節(jié)點的移動使得網(wǎng)絡(luò)拓撲不斷變化，這樣傳統(tǒng)的固定網(wǎng)絡(luò)路由協(xié)議很難及時地準確地反映網(wǎng)絡(luò)的拓撲結(jié)構(gòu)，而且為了維護網(wǎng)絡(luò)拓撲所使用的控制信息不斷地分發(fā)到網(wǎng)絡(luò)中去，要占用大量的無線帶寬。另外，傳統(tǒng)網(wǎng)絡(luò)協(xié)議在設(shè)計時沒考慮或者要求不存在單向鏈路，但在無線Ad hoc 網(wǎng)絡(luò)中，單向鏈路往往是存在的，因此Ad hoc 路由協(xié)議必須支持單向鏈路。
3 當(dāng)前使用的路由思想
不管是無線網(wǎng)絡(luò)還是有線網(wǎng)絡(luò)，大部分路由協(xié)議是基于DBF（Di- stributed Bellman Ford）和LS（Link State）設(shè)計的。由于DBF具有分布式的特點，因此它簡單而且計算效率較高，這是它的優(yōu)勢。但其路由收斂較慢，而且有形成環(huán)形路由的可能，因此不適合拓撲高度變化的Ad hoc 網(wǎng)絡(luò)。雖然有些方案已解決了環(huán)形路由問題，但到目前為止還沒有較好的方案能解決DBF收斂較慢這一問題。
正是由于DBF的這些問題，人們才找到一種全新的方案LS。在LS路由協(xié)議中，每個節(jié)點都維護著一個全局拓撲結(jié)構(gòu)表，因而很容易避免環(huán)形路由。而且鏈路的任何變化都會立即觸發(fā)鏈路更新，這樣收斂到新的拓撲結(jié)構(gòu)所需要的時間遠遠小于DBF。但是LS依靠泛洪去分發(fā)路由更新信息，可能會帶來過多的帶寬開銷，特別是在鏈路變化頻繁的無線Ad hoc 網(wǎng)絡(luò)中，大量的更新信息會占用相當(dāng)多的寶貴帶寬。
第三種方案是最近提出的按需路由思想，該方法只有在需要路由時才去發(fā)現(xiàn)路由。按需路由都使用了query/reponse的方法去發(fā)現(xiàn)和維護路由，由于query使用的也是洪泛技術(shù)，因此在移動性較高的無線網(wǎng)絡(luò)中這種方案的效率不高，而且路由發(fā)現(xiàn)延時較長根本不能滿足適時應(yīng)用的需要。
4 魚眼狀態(tài)路由協(xié)議FSR
“魚眼”技術(shù)是Kleinrock和Stevens提出來的，這種技術(shù)可以用來減少表示圖形圖像的數(shù)據(jù)。魚眼能清晰地捕捉焦點附近的像素，但清晰度隨著離焦點的距離增大而降低。"魚眼"技術(shù)在路由中用來維護精確的距離和路由質(zhì)量信息，但也會隨著距離的變大而逐漸不精確。
FSR（Fisheye State Routing）是一個先驗式（表驅(qū)動的）的路由協(xié)議。它使用了魚眼技術(shù)，在不同魚眼域中的節(jié)點以不同的頻率（這個頻率是由節(jié)點距離決定的）只向鄰居節(jié)點廣播鏈路更新信息，這能夠大大減少鏈路狀態(tài)更新信息，從而降低了泛洪的開銷。通過節(jié)點之間相互交換鏈路狀態(tài)消息，每個FSR路由器都能獲知網(wǎng)絡(luò)全局的拓撲信息。根據(jù)這些最新的拓撲信息， FSR為每個目的節(jié)點計算最短路徑。由于鏈路更新頻率由距離決定，因此對于域內(nèi)的節(jié)點路由都是精確的，而對于域外的節(jié)點，離目的節(jié)點越遠，路由的精確度便越低，這是因為距離較近的更新較快，較遠的更新較慢。但不會像按需路由那樣需要花時間去尋找路由，因此能維持較低的延時。而且隨著離目的節(jié)點越來越近，路由信息越來越精確，正好彌補了路由的不精確性。在移動網(wǎng)絡(luò)中，逐漸精確的路由減小了節(jié)點移動對路由精確度的影響。
當(dāng)鏈路崩潰時，F(xiàn)SR不會發(fā)出任何控制信息，而且也不包含在下一個更新信息中，而是簡單地刪除鄰居列表和拓撲結(jié)構(gòu)表中的信息，因此適合于拓撲高度變化的網(wǎng)絡(luò)環(huán)境。目的序列號的使用不僅使得FSR能使用最新的鏈路狀態(tài)信息去維護拓撲結(jié)構(gòu)，而且還避免了環(huán)形路由的形成，因此較適合高移動性的無線網(wǎng)絡(luò)。
4.1 魚眼域
魚眼域就是在一定跳數(shù)范圍內(nèi)的節(jié)點的集合。
4.2 FSR路由交換方案
FSR在功能上與鏈路狀態(tài)路由相似，因為它們都要在每個節(jié)點處維護一個全局拓撲結(jié)構(gòu)圖。主要的區(qū)別是路由信息分發(fā)的方法。鏈路狀態(tài)路由的更新消息要占用相當(dāng)多的帶寬，如果更新周期小的話可能要占用更多的帶寬。為了減少更新信息的數(shù)量而不嚴重影響路由的精確度，F(xiàn)SR使用了魚眼技術(shù)。拓撲結(jié)構(gòu)表中距離最小的節(jié)點的記錄，將被高頻率地分發(fā)給鄰居節(jié)點，而其他記錄則用低頻率分發(fā)出去。因此，相當(dāng)多的鏈路信息在一個特殊的更新周期內(nèi)不會分發(fā)出去，這樣便減少了更新消息的數(shù)量。總之，通過對路由表中的不同記錄使用不同的交換周期，路由更新開銷將大大地減少。這種策略對于較近的節(jié)點能及時更新信息，但對于較遠的節(jié)點會帶來較大的反應(yīng)時間。不過，隨著數(shù)據(jù)包離目的節(jié)點越來越近，路由也變得越來越精確，這一事實正好是對較遠節(jié)點路由不精確的彌補。隨著網(wǎng)絡(luò)規(guī)模的變大，為了保證低的控制開銷，可將網(wǎng)路劃分為多個域，并使用不同的更新頻率來分發(fā)更新信息。
在鏈路狀態(tài)協(xié)議中，當(dāng)一個節(jié)點檢測到拓撲發(fā)生變化時（或周期性地），便會產(chǎn)生鏈路狀態(tài)包并洪泛到網(wǎng)絡(luò)中。而在魚眼狀態(tài)路由中，鏈路狀態(tài)包不會被洪泛，相反只會周期性地與本地的鄰居進行交換。這種信息交換方案也被用于鄰居發(fā)現(xiàn)，每一個節(jié)點在監(jiān)聽到鄰居的廣播消息后都會增加鄰居或更新它的鄰居列表，同時也會更新拓撲表。各節(jié)點是從鄰居那里得到更新信息的，而信息的最新性是由目的序列號來維護的。這有點像目的序列距離矢量路由協(xié)議（DSDV，Destination-Sequenced Distance-Vector Routing）中的矢量交換，在目的序列距離矢量路由協(xié)議中，距離的更新是根據(jù)節(jié)點的時間戳或序列號來進行的。不過，在FSR中，被傳播的是鏈路狀態(tài)而不是距離矢量。更何況，在鏈路狀態(tài)路由中，每個節(jié)點都保存著全局的拓撲結(jié)構(gòu)表，并且最短路徑也是根據(jù)這個表來計算的。
在無線環(huán)境中，兩個節(jié)點間的無線鏈路可能會不斷地斷開連接。在這種情況下，鏈路狀態(tài)路由協(xié)議也會不斷地發(fā)布鏈路狀態(tài)更新信息，這些信息會被洪泛到網(wǎng)絡(luò)中從而導(dǎo)致過多的開銷。魚眼狀態(tài)路由避免了這一問題，它是周期性地交換拓撲信息，而不是由事件來驅(qū)動的，這樣大大地減少了控制信息的開銷。在FSR中不是任何信息都會被分發(fā)出去的，它根據(jù)消息的分發(fā)能使鄰居節(jié)點的拓撲表更新這一原則，來選擇廣播的消息中所包含的記錄（注：不產(chǎn)生影響的記錄不會被廣播出去）。在節(jié)點密集的網(wǎng)絡(luò)里，一個節(jié)點可能發(fā)現(xiàn)它所有的鄰居對于另一節(jié)點有同樣的更新信息，這時使用這一原則會減少很多不必要的信息分發(fā)。通過去掉這樣的記錄，使得只有有效的記錄包含在鏈路狀態(tài)更新消息中，可以減少更新消息的數(shù)量。
4.3 FSR協(xié)議的操作
4.3.1 信息的分發(fā)
每個節(jié)點都向它們的鄰居廣播最近的鏈路狀態(tài)信息。FSR根據(jù)拓撲表中各記錄中離節(jié)點的跳數(shù)來用不同的時間間隔分發(fā)信息。為了精確，較近節(jié)點對應(yīng)的記錄分發(fā)的頻率比較遠節(jié)點對應(yīng)的的頻率高。魚眼域i的更新時間間隔是UpdateInterval_i。當(dāng)更新魚眼域i的拓撲信息時，F(xiàn)SR瀏覽拓撲表從而獲得相應(yīng)的節(jié)點。如果更新消息有效，而且這些節(jié)點與當(dāng)前節(jié)點的距離在域i內(nèi)，那么它們將被包含在更新消息中。如果當(dāng)前節(jié)點包含在鏈路狀態(tài)消息中，那么它的序號將加1。怎樣獲得域i鏈路狀態(tài)消息的有效部分呢？如果對應(yīng)于域i的一個記錄的NeedToSend標記為真，那么它將被選擇。這個消息發(fā)送之后，域i內(nèi)所有記錄的標記都被重新設(shè)置為假，而且先前的序列號都將被當(dāng)前的序列號所代替。
4.3.2 信息的接收
當(dāng)節(jié)點接收到鏈路狀態(tài)更新信息后，它首先檢查鄰居列表。如果發(fā)送者是一個新的節(jié)點，那么將它插入到列表中，否則它會更新列表中發(fā)送者的時間戳。對于鏈路狀態(tài)更新信息中的每條記錄，應(yīng)考慮以下幾種情況：
（1）如果信息發(fā)送者是一個新的目的節(jié)點，便會產(chǎn)生一個新的拓撲記錄，同時填充相應(yīng)的信息。標志“NeedToSend”為真；
�。�2）否則，用最新的拓撲信息更新拓撲表。如果接受的信息的序列號比表中相應(yīng)節(jié)點記錄的序列號大，那么用接受的信息代替表中的記錄。標志“NeedToSend”為真。
�。�3）對于不滿足上述兩點的目的來說，如果信息較當(dāng)前節(jié)點的舊，即接受信息的序列號比本地記錄的序列號小，那么接受的信息將被丟棄，節(jié)點拓撲表中的相應(yīng)的記錄將在下一個更新周期內(nèi)被送出。標志“NeedToSend”為真。
不管怎樣，一旦拓撲表有變化，路由表將被重新計算。
4.3.3 鏈路崩潰
在移動ad hoc 網(wǎng)絡(luò)中，鏈路崩潰是經(jīng)常發(fā)生的事情。每個節(jié)點都用軟狀態(tài)方法去探測鏈路是否崩潰，即如果在時間間隔NEIGHBOR_TIMEOUT之內(nèi)，節(jié)點還沒有從鄰居那里接收到鏈路狀態(tài)消息，那么它就認為該鏈路崩潰了。節(jié)點就會從鄰居列表中刪除這個鄰居，同時也從拓撲表中刪除它的鏈路狀態(tài)記錄。
FSR不依賴MAC的反饋，如果MAC能在鏈路崩潰時提供反饋，F(xiàn)SR將利用這些反饋去更新鄰居表，同時提供更新的路由信息。這一操作和上面的相同。鏈路崩潰發(fā)現(xiàn)得越早越好。
4.3.4 路由表的計算
拓撲結(jié)構(gòu)表的任何變化都會觸發(fā)路由表的重新計算。路由計算是基于最新的拓撲表進行的，因此在計算之前要檢查拓撲表以去掉舊的記錄。為了在計算最短路徑時同時生成下一跳表（NEXTi( )）和距離表（Di( )），F(xiàn)SR將締杰斯特拉算法進行了一定的修改。
以節(jié)點i為例。FindSP（i）將集合P初始化為（i）,其中集合p表示已找到最短路徑的終點集，距離集Di（i）初始化為{0}，對于其他節(jié)點x初始化相應(yīng)的值Di（x）=weight（i，x）。然后進行迭代，直到P與所有的節(jié)點集相等為止。在每一次迭代中，算法都會從集合V-P中尋找一個節(jié)點j，使得Di（k）+ weight（k,j）的值最小，其中k是集合P中的一個節(jié)點。一旦找到節(jié)點j，那么j就被合并到集合P中，Di（j）的值被賦為Di（k）+ weight（k,j）,NEXTi（j）的值被賦為NEXTi（k），從中可知，從節(jié)點i到j(luò)的最短路徑不得不經(jīng)過節(jié)點k，因此從節(jié)點i到j(luò)和從節(jié)點i到k的最短路徑的后繼者相同，即從節(jié)點i到目的節(jié)點k或j的路由中，對節(jié)點i來說有相同的下一跳。
權(quán)值函數(shù)weight( )被用作計算鏈路的距離。在FSR中由于用跳數(shù)來度量距離，因此，當(dāng)兩節(jié)點直接相連時就簡單返回值1，當(dāng)不相連時就返回0。由于度量值不一樣，函數(shù)weight( )可能返回不同的值。
4.4 路由精確度的考慮
對于較遠的節(jié)點，F(xiàn)SR了解的路由信息不太精確，這種不精確是受路由的更新間隔影響的。更新時間越長路由信息越不精確。然而，F(xiàn)SR的特點減小了這種不精確。在FSR中，路由錯誤用距離進行了加權(quán)，因此它對網(wǎng)絡(luò)規(guī)模的敏感性大大地減少了。這樣一來，收到的遠處節(jié)點以低頻率發(fā)出的更新信息不會在很大程度上影響路由的精確度。而且，隨著離目的節(jié)點越來越近，路由信息越來越精確。在移動網(wǎng)絡(luò)中，逐漸精確的路由減小了節(jié)點移動對路由精確度的影響。
增加域半徑會提高路由的精確度，但是較大的半徑會增加路由更新包，會帶來更多的控制開銷。
5 結(jié)束語
Ad hoc 網(wǎng)絡(luò)具有不依賴任何固定設(shè)施、無中心、自組織、多跳性等特點，使得它的應(yīng)用越來越廣泛。也正是這些特點使得Ad hoc 網(wǎng)絡(luò)技術(shù)，特別是路由技術(shù)面臨著許多困難。FSR路由技術(shù)使用了魚眼技術(shù)，以不同的周期分發(fā)不同魚眼域的信息，使得鏈路更新信息大大地減少，節(jié)約了寶貴的無線帶寬。另外，路由的不精確度用距離進行了加權(quán)，因此，對網(wǎng)絡(luò)規(guī)模的敏感程度大大降低了，較適用于較大規(guī)模的網(wǎng)絡(luò)。同時，逐漸精確的路由減少了移動性的影響，因此FSR技術(shù)也較適用于移動網(wǎng)絡(luò)。
使用
參 考 文 獻
[1] Robertazzi T G,Sarachik.Self-organizing communication network[j].IEEE Communmag,1986,24(1):28-33
[2] G. Pei, M. Gerla, and T.-W. Chen, "Fisheye State Routing:
A Routing Scheme for Ad Hoc Wireless Networks", Proceedings of ICC 2000, New Orleans, LA, Jun. 2000
[3] G. Pei, M. Gerla, and T.-W. Chen, "Fisheye State Routing in Mobile Ad Hoc Networks", Proceedings of Workshop on Wireless
Networks and Mobile Computing, Taipei, Taiwan, Apr. 2000.
[4] 趙志峰，鄭少仁.ad hoc網(wǎng)絡(luò).中國數(shù)據(jù)通信，2002,4(9)：1-5
[5] 楊盤隆,鄭少仁.Ad Hoc網(wǎng)絡(luò)中的路由算法.軍用通信技術(shù)，2001，22（3）：49-53
----《中國數(shù)據(jù)通信》
