自組織基本路由協議及混合型路由協議技術

（2）DSDV協議

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

　　①路由表結構。每個結點維護一個路由表，每個路由表項包括：信宿地址、到達信宿的度量值（如跳數）、信宿相關的序列號（由信宿發出）。

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

　　②信息通告。各結點周期性地向鄰居結點通告其當前的路由表，而不是才用洪泛法向網絡中的所有結點進行通告。這相當于各結點對收到的其他結點的信息進行處理后再進行廣播通告，從而可大大減少通告的信息量。

　　為了進一步減少路由信息的傳輸開銷，DSDV中使用了兩類更新報文。

　　（a）完全轉存（full damp）。該報文包括了結點當前路由表的所有表項，可能需要多個NPDU進行傳輸，占用的傳輸容量大。這種報文僅僅在結點頻繁移動的情況下使用。

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

　　③鏈路斷。如果在相當長的一段時間內不能收到鄰居結點的廣播消息，可推斷出鏈路斷；同時，MAC層實體也可檢測到。

　　（a）在DSDV中，斷的鏈路度量值＝∞。

　　（b）結點檢測路由表，下一跳經過該鏈路的路由表項的度量值標記為∞，并分配一個新的序列號。這種情況下的序列號為奇數，以區別于信宿發出的更新報文。

　　（c）度量值為∞的表項的變化程度足以觸發“遞增更新”報文的立即發送。

　　經過上述過程，在較短的時間內，該鏈路的變化將通告到網絡的各個結點。

　　④路由選擇準則與波動抑制。

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

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

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

　　表1 主動路曲協議的比較

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

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

　　（1）DSR協議

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

　　該協議的路由發現過程如下：

　　①RREQ分組。結點有分組要發時，動態地廣播“路由請求分組”RREQ。RREQ分組應包括信宿、請求分組發送結點地址、本分組ID、路由記錄。{請求分組發送結點地址＋本分組ID}用于唯一地識別RREQ，以便于RREQ的接收處理，這里稱為RREQ標識。路由記錄將積累地記下RREQ分組逐跳傳播時所順序經過的結點地址，從而完成路由發現的功能。