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

（2）DSDV協(xié)議

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

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

　　該序列號(hào)用以識(shí)別路由的新舊，作為路由更新和分組轉(zhuǎn)發(fā)的依據(jù)。

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

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

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

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

　?、坻溌窋唷Ｈ绻谙喈?dāng)長的一段時(shí)間內(nèi)不能收到鄰居結(jié)點(diǎn)的廣播消息，可推斷出鏈路斷；同時(shí)，MAC層實(shí)體也可檢測(cè)到。

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

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

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

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

　　④路由選擇準(zhǔn)則與波動(dòng)抑制。

　　DSDV中路由選擇的準(zhǔn)則為：序列號(hào)新或度量值小。

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

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

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

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

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

　?。?）DSR協(xié)議

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

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

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