移動(dòng)Ad hoc網(wǎng)絡(luò)路由協(xié)議FSR研究摘要 隨著無線通信技術(shù)的發(fā)展和移動(dòng)終端性能的提高，Ad hoc的應(yīng)用越來越廣泛。無線Ad hoc 是一種不依賴于任何基礎(chǔ)設(shè)施，無中心自組織的多跳無線網(wǎng)絡(luò)。本文從Ad hoc 網(wǎng)絡(luò)的特點(diǎn)出發(fā)，在分析當(dāng)前路由協(xié)議設(shè)計(jì)思想的基礎(chǔ)上，對(duì)Ad hoc 的路由協(xié)議FSR進(jìn)行了研究。

　　關(guān)鍵詞 Ad hoc 多跳無線網(wǎng) 網(wǎng)絡(luò)拓?fù)?路由更新 魚眼域 FSR

1 前言

　　Ad hoc 網(wǎng)絡(luò)是一種無中心自組織的多跳無線網(wǎng)絡(luò)，它不以任何已有的固定設(shè)施為基礎(chǔ)而能隨時(shí)隨地組建臨時(shí)性的網(wǎng)絡(luò)。由于這種方便性，并且隨著無線通信技術(shù)的發(fā)展和移動(dòng)終端性能的提高，特別是人們對(duì)個(gè)人通信日益增長的需求，使得移動(dòng)ad hoc網(wǎng)絡(luò)的應(yīng)用范圍正逐步擴(kuò)大。在軍用領(lǐng)域，它可以支持野外偵察聯(lián)絡(luò)、獨(dú)立戰(zhàn)斗群通信和艦隊(duì)?wèi)?zhàn)斗群通信、無人偵察與情報(bào)傳輸?shù)�；在民用領(lǐng)域，它支持諸如移動(dòng)會(huì)議、移動(dòng)網(wǎng)絡(luò)、個(gè)人局域網(wǎng)、災(zāi)難營救過程中的信息交換以及臨時(shí)交互式通信組等。我們可以預(yù)測(cè)，這種技術(shù)在未來移動(dòng)通信的領(lǐng)域中將起到非常重要的作用。

2 Ad hoc 網(wǎng)絡(luò)的特點(diǎn)

　　Ad hoc 網(wǎng)絡(luò)是一群終端為了完成一項(xiàng)任務(wù)而臨時(shí)組建的一種網(wǎng)絡(luò)。它不需任何已有的固定設(shè)施作為基礎(chǔ)，隨時(shí)隨地進(jìn)行組建，因而網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都是平等的，沒有中心。從技術(shù)上講，Ad hoc 網(wǎng)絡(luò)是一種移動(dòng)通信技術(shù)和計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)相結(jié)合的網(wǎng)絡(luò)。一方面，它采用無線信道進(jìn)行通信，而且用戶終端都可以隨意移動(dòng)；另一方面，各節(jié)點(diǎn)的信息交換采用了計(jì)算機(jī)網(wǎng)絡(luò)中的分組交換機(jī)制，因此Ad hoc中的各節(jié)點(diǎn)兼有主機(jī)和路由器兩種功能。

　　 Ad hoc除了是無中心、自組織平等式的網(wǎng)絡(luò)外，它還有如下的特點(diǎn)：

　�。�1）網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)變化頻繁。 Ad hoc 網(wǎng)絡(luò)中，用戶終端的移動(dòng)性具有很大的隨機(jī)性，它們可以隨時(shí)移動(dòng)，也可以隨時(shí)開機(jī)和關(guān)機(jī)。再加上無線發(fā)射裝置發(fā)送功率的變化、無線信道間的相互干擾以及地形等因素的影響，網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)可能隨時(shí)發(fā)生變化，而且這種變化無法預(yù)先知曉。

　　 （2）多跳的無線網(wǎng)。 網(wǎng)絡(luò)中節(jié)點(diǎn)如果在相互輻射覆蓋范圍內(nèi)，則它們可以通過無線信道直接進(jìn)行通信；否則，它們必須借助中間節(jié)點(diǎn)的轉(zhuǎn)發(fā)才能通信。在Ad hoc網(wǎng)絡(luò)中，這種轉(zhuǎn)發(fā)不是由專門的路由器完成的，而是由平等的普通節(jié)點(diǎn)完成的。

　　（3）傳輸帶寬有限。Ad hoc 網(wǎng)絡(luò)的通信手段是無線傳輸技術(shù)，而無線信道本身的帶寬相對(duì)有限網(wǎng)絡(luò)非常之有線，再加上無線信道中的信號(hào)的沖突、干擾、衰減等因素使得無線帶寬非常寶貴。

　�。�4）存在單向鏈路。在無線通信中，由于通信設(shè)備頻率的強(qiáng)弱和地形環(huán)境因素的影響，使得單向鏈路常常存在。比如，車載臺(tái)終端發(fā)送功率比手持終端大很多，所以有時(shí)手持終端可以收到來自車載臺(tái)的信號(hào)而車載臺(tái)卻無法接受到手持終端的信號(hào)，即存在一條從車載終端到手持終端的單向信道。

　　Ad hoc 網(wǎng)絡(luò)的多跳性使得借鑒固定網(wǎng)絡(luò)的路由協(xié)議成為可能，但其網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)變化、傳輸帶寬有限、單向鏈路的存在使得固定網(wǎng)絡(luò)的路由協(xié)議不能直接應(yīng)用到無線Ad hoc 網(wǎng)絡(luò)中。節(jié)點(diǎn)的移動(dòng)使得網(wǎng)絡(luò)拓?fù)洳粩嘧兓�，這樣傳統(tǒng)的固定網(wǎng)絡(luò)路由協(xié)議很難及時(shí)地準(zhǔn)確地反映網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，而且為了維護(hù)網(wǎng)絡(luò)拓?fù)渌�使用的控制信息不斷地分發(fā)到網(wǎng)絡(luò)中去，要占用大量的無線帶寬。另外，傳統(tǒng)網(wǎng)絡(luò)協(xié)議在設(shè)計(jì)時(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è)計(jì)的。由于DBF具有分布式的特點(diǎn)，因此它簡單而且計(jì)算效率較高，這是它的優(yōu)勢(shì)。但其路由收斂較慢，而且有形成環(huán)形路由的可能，因此不適合拓?fù)涓叨茸兓�的Ad hoc 網(wǎng)絡(luò)。雖然有些方案已解決了環(huán)形路由問題，但到目前為止還沒有較好的方案能解決DBF收斂較慢這一問題。

　　正是由于DBF的這些問題，人們才找到一種全新的方案LS。在LS路由協(xié)議中，每個(gè)節(jié)點(diǎn)都維護(hù)著一個(gè)全局拓?fù)浣Y(jié)構(gòu)表，因而很容易避免環(huán)形路由。而且鏈路的任何變化都會(huì)立即觸發(fā)鏈路更新，這樣收斂到新的拓?fù)浣Y(jié)構(gòu)所需要的時(shí)間遠(yuǎn)遠(yuǎn)小于DBF。但是LS依靠泛洪去分發(fā)路由更新信息，可能會(huì)帶來過多的帶寬開銷，特別是在鏈路變化頻繁的無線Ad hoc 網(wǎng)絡(luò)中，大量的更新信息會(huì)占用相當(dāng)多的寶貴帶寬。

　　第三種方案是最近提出的按需路由思想，該方法只有在需要路由時(shí)才去發(fā)現(xiàn)路由。按需路由都使用了query/reponse的方法去發(fā)現(xiàn)和維護(hù)路由，由于query使用的也是洪泛技術(shù)，因此在移動(dòng)性較高的無線網(wǎng)絡(luò)中這種方案的效率不高，而且路由發(fā)現(xiàn)延時(shí)較長根本不能滿足適時(shí)應(yīng)用的需要。

4 魚眼狀態(tài)路由協(xié)議FSR

　　“魚眼”技術(shù)是Kleinrock和Stevens提出來的，這種技術(shù)可以用來減少表示圖形圖像的數(shù)據(jù)。魚眼能清晰地捕捉焦點(diǎn)附近的像素，但清晰度隨著離焦點(diǎn)的距離增大而降低。"魚眼"技術(shù)在路由中用來維護(hù)精確的距離和路由質(zhì)量信息，但也會(huì)隨著距離的變大而逐漸不精確。

　　 FSR（Fisheye State Routing）是一個(gè)先驗(yàn)式（表驅(qū)動(dòng)的）的路由協(xié)議。它使用了魚眼技術(shù)，在不同魚眼域中的節(jié)點(diǎn)以不同的頻率（這個(gè)頻率是由節(jié)點(diǎn)距離決定的）只向鄰居節(jié)點(diǎn)廣播鏈路更新信息，這能夠大大減少鏈路狀態(tài)更新信息，從而降低了泛洪的開銷。通過節(jié)點(diǎn)之間相互交換鏈路狀態(tài)消息，每個(gè)FSR路由器都能獲知網(wǎng)絡(luò)全局的拓?fù)湫畔�。根�?jù)這些最新的拓?fù)湫畔ⅲ?FSR為每個(gè)目的節(jié)點(diǎn)計(jì)算最短路徑。由于鏈路更新頻率由距離決定，因此對(duì)于域內(nèi)的節(jié)點(diǎn)路由都是精確的，而對(duì)于域外的節(jié)點(diǎn)，離目的節(jié)點(diǎn)越遠(yuǎn)，路由的精確度便越低，這是因?yàn)榫嚯x較近的更新較快，較遠(yuǎn)的更新較慢。但不會(huì)像按需路由那樣需要花時(shí)間去尋找路由，因此能維持較低的延時(shí)。而且隨著離目的節(jié)點(diǎn)越來越近，路由信息越來越精確，正好彌補(bǔ)了路由的不精確性。在移動(dòng)網(wǎng)絡(luò)中，逐漸精確的路由減小了節(jié)點(diǎn)移動(dòng)對(duì)路由精確度的影響。

　　當(dāng)鏈路崩潰時(shí)，F(xiàn)SR不會(huì)發(fā)出任何控制信息，而且也不包含在下一個(gè)更新信息中，而是簡單地刪除鄰居列表和拓?fù)浣Y(jié)構(gòu)表中的信息，因此適合于拓?fù)涓叨茸兓�的網(wǎng)絡(luò)環(huán)境。目的序列號(hào)的使用不僅使得FSR能使用最新的鏈路狀態(tài)信息去維護(hù)拓?fù)浣Y(jié)構(gòu)，而且還避免了環(huán)形路由的形成，因此較適合高移動(dòng)性的無線網(wǎng)絡(luò)。

4.1 魚眼域

　　魚眼域就是在一定跳數(shù)范圍內(nèi)的節(jié)點(diǎn)的集合。

4.2 FSR路由交換方案

　　FSR在功能上與鏈路狀態(tài)路由相似，因?yàn)樗鼈兌家�在每個(gè)節(jié)點(diǎn)處維護(hù)一個(gè)全局拓?fù)浣Y(jié)構(gòu)圖。主要的區(qū)別是路由信息分發(fā)的方法。鏈路狀態(tài)路由的更新消息要占用相當(dāng)多的帶寬，如果更新周期小的話可能要占用更多的帶寬。為了減少更新信息的數(shù)量而不嚴(yán)重影響路由的精確度，F(xiàn)SR使用了魚眼技術(shù)。拓?fù)浣Y(jié)構(gòu)表中距離最小的節(jié)點(diǎn)的記錄，將被高頻率地分發(fā)給鄰居節(jié)點(diǎn)，而其他記錄則用低頻率分發(fā)出去。因此，相當(dāng)多的鏈路信息在一個(gè)特殊的更新周期內(nèi)不會(huì)分發(fā)出去，這樣便減少了更新消息的數(shù)量。總之，通過對(duì)路由表中的不同記錄使用不同的交換周期，路由更新開銷將大大地減少。這種策略對(duì)于較近的節(jié)點(diǎn)能及時(shí)更新信息，但對(duì)于較遠(yuǎn)的節(jié)點(diǎn)會(huì)帶來較大的反應(yīng)時(shí)間。不過，隨著數(shù)據(jù)包離目的節(jié)點(diǎn)越來越近，路由也變得越來越精確，這一事實(shí)正好是對(duì)較遠(yuǎn)節(jié)點(diǎn)路由不精確的彌補(bǔ)。隨著網(wǎng)絡(luò)規(guī)模的變大，為了保證低的控制開銷，可將網(wǎng)路劃分為多個(gè)域，并使用不同的更新頻率來分發(fā)更新信息。

　　在鏈路狀態(tài)協(xié)議中，當(dāng)一個(gè)節(jié)點(diǎn)檢測(cè)到拓?fù)浒l(fā)生變化時(shí)（或周期性地），便會(huì)產(chǎn)生鏈路狀態(tài)包并洪泛到網(wǎng)絡(luò)中。而在魚眼狀態(tài)路由中，鏈路狀態(tài)包不會(huì)被洪泛，相反只會(huì)周期性地與本地的鄰居進(jìn)行交換。這種信息交換方案也被用于鄰居發(fā)現(xiàn)，每一個(gè)節(jié)點(diǎn)在監(jiān)聽到鄰居的廣播消息后都會(huì)增加鄰居或更新它的鄰居列表，同時(shí)也會(huì)更新拓?fù)浔怼８鞴?jié)點(diǎn)是從鄰居那里得到更新信息的，而信息的最新性是由目的序列號(hào)來維護(hù)的。這有點(diǎn)像目的序列距離矢量路由協(xié)議（DSDV，Destination-Sequenced Distance-Vector Routing）中的矢量交換，在目的序列距離矢量路由協(xié)議中，距離的更新是根據(jù)節(jié)點(diǎn)的時(shí)間戳或序列號(hào)來進(jìn)行的。不過，在FSR中，被傳播的是鏈路狀態(tài)而不是距離矢量。更何況，在鏈路狀態(tài)路由中，每個(gè)節(jié)點(diǎn)都保存著全局的拓?fù)浣Y(jié)構(gòu)表，并且最短路徑也是根據(jù)這個(gè)表來計(jì)算的。

　　在無線環(huán)境中，兩個(gè)節(jié)點(diǎn)間的無線鏈路可能會(huì)不斷地?cái)嚅_連接。在這種情況下，鏈路狀態(tài)路由協(xié)議也會(huì)不斷地發(fā)布鏈路狀態(tài)更新信息，這些信息會(huì)被洪泛到網(wǎng)絡(luò)中從而導(dǎo)致過多的開銷。魚眼狀態(tài)路由避免了這一問題，它是周期性地交換拓?fù)湫畔ⅲ�而不是由事件來�?qū)動(dòng)的，這樣大大地減少了控制信息的開銷。在FSR中不是任何信息都會(huì)被分發(fā)出去的，它根據(jù)消息的分發(fā)能使鄰居節(jié)點(diǎn)的拓?fù)浔砀�新這一原則，來選擇廣播的消息中所包含的記錄（注：不產(chǎn)生影響的記錄不會(huì)被廣播出去）。在節(jié)點(diǎn)密集的網(wǎng)絡(luò)里，一個(gè)節(jié)點(diǎn)可能發(fā)現(xiàn)它所有的鄰居對(duì)于另一節(jié)點(diǎn)有同樣的更新信息，這時(shí)使用這一原則會(huì)減少很多不必要的信息分發(fā)。通過去掉這樣的記錄，使得只有有效的記錄包含在鏈路狀態(tài)更新消息中，可以減少更新消息的數(shù)量。

4.3 FSR協(xié)議的操作

4.3.1 信息的分發(fā)

　　每個(gè)節(jié)點(diǎn)都向它們的鄰居廣播最近的鏈路狀態(tài)信息。FSR根據(jù)拓?fù)浔碇懈饔涗浿须x節(jié)點(diǎn)的跳數(shù)來用不同的時(shí)間間隔分發(fā)信息。為了精確，較近節(jié)點(diǎn)對(duì)應(yīng)的記錄分發(fā)的頻率比較遠(yuǎn)節(jié)點(diǎn)對(duì)應(yīng)的的頻率高。魚眼域i的更新時(shí)間間隔是UpdateInterval_i。當(dāng)更新魚眼域i的拓?fù)湫畔�時(shí)，F(xiàn)SR瀏覽拓?fù)浔韽亩�獲得相應(yīng)的節(jié)點(diǎn)。如果更新消息有效，而且這些節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)的距離在域i內(nèi)，那么它們將被包含在更新消息中。如果當(dāng)前節(jié)點(diǎn)包含在鏈路狀態(tài)消息中，那么它的序號(hào)將加1。怎樣獲得域i鏈路狀態(tài)消息的有效部分呢？如果對(duì)應(yīng)于域i的一個(gè)記錄的NeedToSend標(biāo)記為真，那么它將被選擇。這個(gè)消息發(fā)送之后，域i內(nèi)所有記錄的標(biāo)記都被重新設(shè)置為假，而且先前的序列號(hào)都將被當(dāng)前的序列號(hào)所代替。

4.3.2 信息的接收

　　當(dāng)節(jié)點(diǎn)接收到鏈路狀態(tài)更新信息后，它首先檢查鄰居列表。如果發(fā)送者是一個(gè)新的節(jié)點(diǎn)，那么將它插入到列表中，否則它會(huì)更新列表中發(fā)送者的時(shí)間戳。對(duì)于鏈路狀態(tài)更新信息中的每條記錄，應(yīng)考慮以下幾種情況：

　　 （1）如果信息發(fā)送者是一個(gè)新的目的節(jié)點(diǎn)，便會(huì)產(chǎn)生一個(gè)新的拓?fù)溆涗�，同時(shí)填充相應(yīng)的信息。標(biāo)志“NeedToSend”為真；

　�。�2）否則，用最新的拓?fù)湫畔⒏�新拓�(fù)浔�。如果接受的信息的序列�?hào)比表中相應(yīng)節(jié)點(diǎn)記錄的序列號(hào)大，那么用接受的信息代替表中的記錄。標(biāo)志“NeedToSend”為真。

　�。�3）對(duì)于不滿足上述兩點(diǎn)的目的來說，如果信息較當(dāng)前節(jié)點(diǎn)的舊，即接受信息的序列號(hào)比本地記錄的序列號(hào)小，那么接受的信息將被丟棄，節(jié)點(diǎn)拓?fù)浔碇械南鄳?yīng)的記錄將在下一個(gè)更新周期內(nèi)被送出。標(biāo)志“NeedToSend”為真。

　　不管怎樣，一旦拓?fù)浔碛凶兓�，路由表將被重新�?jì)算。

4.3.3 鏈路崩潰

　　在移動(dòng)ad hoc 網(wǎng)絡(luò)中，鏈路崩潰是經(jīng)常發(fā)生的事情。每個(gè)節(jié)點(diǎn)都用軟狀態(tài)方法去探測(cè)鏈路是否崩潰，即如果在時(shí)間間隔NEIGHBOR_TIMEOUT之內(nèi)，節(jié)點(diǎn)還沒有從鄰居那里接收到鏈路狀態(tài)消息，那么它就認(rèn)為該鏈路崩潰了。節(jié)點(diǎn)就會(huì)從鄰居列表中刪除這個(gè)鄰居，同時(shí)也從拓?fù)浔碇袆h除它的鏈路狀態(tài)記錄。

　　FSR不依賴MAC的反饋，如果MAC能在鏈路崩潰時(shí)提供反饋，F(xiàn)SR將利用這些反饋去更新鄰居表，同時(shí)提供更新的路由信息。這一操作和上面的相同。鏈路崩潰發(fā)現(xiàn)得越早越好。

4.3.4 路由表的計(jì)算

　　拓?fù)浣Y(jié)構(gòu)表的任何變化都會(huì)觸發(fā)路由表的重新計(jì)算。路由計(jì)算是基于最新的拓?fù)浔磉M(jìn)行的，因此在計(jì)算之前要檢查拓?fù)浔硪匀サ襞f的記錄。為了在計(jì)算最短路徑時(shí)同時(shí)生成下一跳表（NEXTi( )）和距離表（Di( )），F(xiàn)SR將締杰斯特拉算法進(jìn)行了一定的修改。

　　以節(jié)點(diǎn)i為例。FindSP（i）將集合P初始化為（i）,其中集合p表示已找到最短路徑的終點(diǎn)集，距離集Di（i）初始化為{0}，對(duì)于其他節(jié)點(diǎn)x初始化相應(yīng)的值Di（x）=weight（i，x）。然后進(jìn)行迭代，直到P與所有的節(jié)點(diǎn)集相等為止。在每一次迭代中，算法都會(huì)從集合V-P中尋找一個(gè)節(jié)點(diǎn)j，使得Di（k） weight（k,j）的值最小，其中k是集合P中的一個(gè)節(jié)點(diǎn)。一旦找到節(jié)點(diǎn)j，那么j就被合并到集合P中，Di（j）的值被賦為Di（k） weight（k,j）,NEXTi（j）的值被賦為NEXTi（k），從中可知，從節(jié)點(diǎn)i到j(luò)的最短路徑不得不經(jīng)過節(jié)點(diǎn)k，因此從節(jié)點(diǎn)i到j(luò)和從節(jié)點(diǎn)i到k的最短路徑的后繼者相同，即從節(jié)點(diǎn)i到目的節(jié)點(diǎn)k或j的路由中，對(duì)節(jié)點(diǎn)i來說有相同的下一跳。

　　權(quán)值函數(shù)weight( )被用作計(jì)算鏈路的距離。在FSR中由于用跳數(shù)來度量距離，因此，當(dāng)兩節(jié)點(diǎn)直接相連時(shí)就簡單返回值1，當(dāng)不相連時(shí)就返回0。由于度量值不一樣，函數(shù)weight( )可能返回不同的值。

4.4 路由精確度的考慮

　　對(duì)于較遠(yuǎn)的節(jié)點(diǎn)，F(xiàn)SR了解的路由信息不太精確，這種不精確是受路由的更新間隔影響的。更新時(shí)間越長路由信息越不精確。然而，F(xiàn)SR的特點(diǎn)減小了這種不精確。在FSR中，路由錯(cuò)誤用距離進(jìn)行了加權(quán)，因此它對(duì)網(wǎng)絡(luò)規(guī)模的敏感性大大地減少了。這樣一來，收到的遠(yuǎn)處節(jié)點(diǎn)以低頻率發(fā)出的更新信息不會(huì)在很大程度上影響路由的精確度。而且，隨著離目的節(jié)點(diǎn)越來越近，路由信息越來越精確。在移動(dòng)網(wǎng)絡(luò)中，逐漸精確的路由減小了節(jié)點(diǎn)移動(dòng)對(duì)路由精確度的影響。

　　增加域半徑會(huì)提高路由的精確度，但是較大的半徑會(huì)增加路由更新包，會(huì)帶來更多的控制開銷。

5 結(jié)束語

　　Ad hoc 網(wǎng)絡(luò)具有不依賴任何固定設(shè)施、無中心、自組織、多跳性等特點(diǎn)，使得它的應(yīng)用越來越廣泛。也正是這些特點(diǎn)使得Ad hoc 網(wǎng)絡(luò)技術(shù)，特別是路由技術(shù)面臨著許多困難。FSR路由技術(shù)使用了魚眼技術(shù)，以不同的周期分發(fā)不同魚眼域的信息，使得鏈路更新信息大大地減少，節(jié)約了寶貴的無線帶寬。另外，路由的不精確度用距離進(jìn)行了加權(quán)，因此，對(duì)網(wǎng)絡(luò)規(guī)模的敏感程度大大降低了，較適用于較大規(guī)模的網(wǎng)絡(luò)。同時(shí)，逐漸精確的路由減少了移動(dòng)性的影響，因此FSR技術(shù)也較適用于移動(dòng)網(wǎng)絡(luò)使用。(陳軍健　徐海川　鄢楚平 華北計(jì)算技術(shù)研究所通信工程研究室)