自組織基本路由協(xié)議及混合型路由協(xié)議技術(shù)

（2）DSDV協(xié)議

　　目的序列距離矢量協(xié)議DSDV（destinatiON sequenced distance vector，DSDV）是一種基于Bellman_ord算法的主動(dòng)路由協(xié)議。它被認為是最早的自組網(wǎng)路由協(xié)議。它的主要特點(diǎn)是采用了序列號機制來(lái)區分路由的新舊程度，防止可能產(chǎn)生的路由環(huán)路。它的缺點(diǎn)是不適應變化速度快的自組網(wǎng)，不支持單向信道。DSDV的主要設計思想如下：

　?、俾酚杀斫Y構。每個(gè)結點(diǎn)維護一個(gè)路由表，每個(gè)路由表項包括：信宿地址、到達信宿的度量值（如跳數）、信宿相關(guān)的序列號（由信宿發(fā)出）。

　　該序列號用以識別路由的新舊，作為路由更新和分組轉發(fā)的依據。

　?、谛畔⑼ǜ?。各結點(diǎn)周期性地向鄰居結點(diǎn)通告其當前的路由表，而不是才用洪泛法向網(wǎng)絡(luò )中的所有結點(diǎn)進(jìn)行通告。這相當于各結點(diǎn)對收到的其他結點(diǎn)的信息進(jìn)行處理后再進(jìn)行廣播通告，從而可大大減少通告的信息量。

　　為了進(jìn)一步減少路由信息的傳輸開(kāi)銷(xiāo)，DSDV中使用了兩類(lèi)更新報文。

　?。╝）完全轉存（full damp）。該報文包括了結點(diǎn)當前路由表的所有表項，可能需要多個(gè)NPDU進(jìn)行傳輸，占用的傳輸容量大。這種報文僅僅在結點(diǎn)頻繁移動(dòng)的情況下使用。

　?。╞）遞增更新（incremental update）。該報文包括上一次“完全轉存”報文傳輸以后發(fā)生了變化的表項。結點(diǎn)根據每個(gè)路由表項變化的程度決定是否進(jìn)行“遞增更新”報文的發(fā)送。例如，當到達信宿的度量值變化時(shí)，可認為需要對相應的表項進(jìn)行“遞增更新”了。

　?、坻溌窋?。如果在相當長(cháng)的一段時(shí)間內不能收到鄰居結點(diǎn)的廣播消息，可推斷出鏈路斷；同時(shí)，MAC層實(shí)體也可檢測到。

　?。╝）在DSDV中，斷的鏈路度量值＝∞。

　?。╞）結點(diǎn)檢測路由表，下一跳經(jīng)過(guò)該鏈路的路由表項的度量值標記為∞，并分配一個(gè)新的序列號。這種情況下的序列號為奇數，以區別于信宿發(fā)出的更新報文。

　?。╟）度量值為∞的表項的變化程度足以觸發(fā)“遞增更新”報文的立即發(fā)送。

　　經(jīng)過(guò)上述過(guò)程，在較短的時(shí)間內，該鏈路的變化將通告到網(wǎng)絡(luò )的各個(gè)結點(diǎn)。

　?、苈酚蛇x擇準則與波動(dòng)抑制。

　　DSDV中路由選擇的準則為：序列號新或度量值小。

　　DSDV中路由的選擇考慮到下述事實(shí)：結點(diǎn)的路由信息通告是異步事件，結點(diǎn)可能先接收到度量值大的路由信息，更新路由的下一跳；當收到新的度量值小的路由信息時(shí)，即使信宿結點(diǎn)沒(méi)有移動(dòng)，通過(guò)路由選擇算法也會(huì )改變路由的下一跳結點(diǎn)。這種現象導致需要通告的路由表項的頻繁波動(dòng)。

　　DSDV采取的辦法是維護兩張表：一是轉發(fā)表；二是廣播表。兩張表的操作規則有所區分。廣播表以信宿地址為關(guān)鍵字，表項中設置一個(gè)“平均通告時(shí)間間隔”字段，該字段是對該表項過(guò)去通告時(shí)間間隔的加權平均，最近通告的時(shí)間加杈大。當收到一個(gè)新的網(wǎng)絡(luò )變化通告時(shí)，查詢(xún)廣播表的相應表項的“平均通告時(shí)間間隔”字段，決定是否進(jìn)行通告廣播。需要注意的是，當接收到度量為∞的通告時(shí)，不延遲，立即進(jìn)行廣播。WRP和DSDV的比較如表1所示。

　　表1 主動(dòng)路曲協(xié)議的比較

　　目前，提交到IETF MANET組的路由協(xié)議及其他研究人員提出的路由協(xié)議，大都是基于信源按需建立的特征。這種特征成為自組織網(wǎng)絡(luò )路由協(xié)議設計的一種趨勢。

　　迄今為止，已提出的按需路由協(xié)議（on demand）主要有源動(dòng)態(tài)路由協(xié)議（dynamlc source routmg，DSR）、按需距離矢量協(xié)議（Ad Hoc on demand distancevector，AODV）等。下面簡(jiǎn)要介紹這兩種協(xié)議。

　?。?）DSR協(xié)議

　　DSR協(xié)議是最早采用按需路由思想的路由協(xié)議。它包括路由發(fā)現和路由維護兩個(gè)過(guò)程。它的主要特點(diǎn)是使用了源路由機制進(jìn)行分組轉發(fā)。這種機制最初是IEEE 802.5協(xié)議用于在網(wǎng)橋互聯(lián)的多個(gè)令牌環(huán)網(wǎng)中的結點(diǎn)尋找路由。DSR協(xié)議借鑒了這種機制，并加人了按需思想而形成。它的優(yōu)點(diǎn)在于中間結點(diǎn)不用維護去往全網(wǎng)所有結點(diǎn)的路由信息，而且可以避免出現路由環(huán)路。它的缺點(diǎn)是每個(gè)數據分組都攜帶了路徑信息，造成協(xié)議開(kāi)銷(xiāo)較大，而且也不適合網(wǎng)絡(luò )直徑大的自組網(wǎng)，網(wǎng)絡(luò )可擴展性不強。

　　該協(xié)議的路由發(fā)現過(guò)程如下：

　?、賀REQ分組。結點(diǎn)有分組要發(fā)時(shí)，動(dòng)態(tài)地廣播“路由請求分組”RREQ。RREQ分組應包括信宿、請求分組發(fā)送結點(diǎn)地址、本分組ID、路由記錄。{請求分組發(fā)送結點(diǎn)地址＋本分組ID}用于唯一地識別RREQ，以便于RREQ的接收處理，這里稱(chēng)為RREQ標識。路由記錄將積累地記下RREQ分組逐跳傳播時(shí)所順序經(jīng)過(guò)的結點(diǎn)地址，從而完成路由發(fā)現的功能。