?

　　自組網的路由技術主要是設計能自適應網絡拓撲動態變化的分布式路由協議，并避免產生路由環路，盡可能減小路由開銷，具有一定的可擴展性，使網絡節點能根據網絡情況的變化，具各分布式管理的路由功能。自組織網絡是一個多跳的臨時性的自治系統，在這種環境中，由于結點的無線通信覆蓋范圍的有限性，兩個無法直接通信的移動結點可以借助其他結點進行分組轉發來進行數據通信。自組網結點之間是通過多跳數據轉發機制進行數據交換，需要按路由協議進行分組轉發決策。

　　自組織網絡路由協議按驅動模式的分類

　　迄今為止，已提出的主動式協議主要有WRP、DSDV等。下面簡單介紹這兩種協議。

　　(1)WRP協議

　　無線路由協議(wireless routmg protocol，WRP)是一個基于距離矢量的協議，其路由算法是對路徑發現算法PFA的改進。它利用去往目標結點的路徑長度和相應路徑到倒數第二跳結點信息加速路由協議收斂速度，改善路由環路問題。WRP對PFAD的改進之處在于當結點i監測到與鄰居結點j的鏈路發生變化時，i會檢查所有鄰居結點關于倒數第二跳信息的一致性，而PFA只會檢查結點j關于倒數第二跳結點信息的一致性。這種改進可以進一步地減少出現路由環路的次數，加快算法的收斂速度。WRP協議的主要思想如下：

　　每個結點維護四張表，即距離表、路由表、鏈路費用表和消息重發表，并通過UPDATE消息通告給鄰居結點。

　　設結點為i，信宿結點為j，結點i的鄰居結點為k。

　　①距離表。距離表包括k的通告的相關內容有經過k到j的路由的距離Dijk的前趨結點Piik。

　　②路由表。每個表項包括信宿結點地址、到信宿的距離Dij、到j的最短路由j的前趨結點Pij、i的下一跳(后繼)Sij等。

　　③鏈路費用表。通過結點乃的鏈路費用和從上一次收到無誤消息后所經過

　　的時間。

　　④消息重發表。可包括多個重發表項，每個表項包括更新消息的序號、重發計數、ACK標志(是否發過相應的ACK)、更新消息列表。

　　WRP通過發送ACK實現可靠傳輸，結點通過接收ACK和其他消息來測試其鄰居結點的存在性。如果結點沒有發現數據分組，則周期性地發HELLO消息來得到與鄰居結點的連通性消息。如果在一定的時間內收不到某鄰居結點的任何消息，則認為與鄰居結點的鏈路出現了故障;當有新的鄰居結點時，把自己的路由表通告給新的結點。當結點收到一個更新消息后，采用路由發現算法進行路由表的更新，并克服“計數到無窮”問題。WRP對路由發現算法進行了改進，其獨特性表現如下。

　　①距離表更新。對每一個更新消息(如k的通告)，結點i檢測其所有鄰居結點{B∈Ni|b≠k}，凡是經過b結點到j且包括有花結點的路由，距離值需要重新計算為Dibj=Dikj+Dij，路由前趨更新為Pijb=Pkj。

　　②路由表更新。當鄰居P→J路由不包括i，且是鄰居結點中到j的最短路由，則結點i選擇鄰居p作為其到j的下一跳結點，即更新Sij=p。

　　(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分組逐跳傳播時所順序經過的結點地址，從而完成路由發現的功能。

　　②結點對RREQ分組的處理。

　　(a)如果在最近收到的f歷史RREQ列表”中已存在，則丟棄該RREQ分組，不作進一步的處理;

　　(b)如果“路由記錄”中包括本結點，則丟棄該RREQ分組，不作進一步的處理;

　　(c)如果本結點就是RREQ指定的信宿，發送“路由回答分組”RREP，否則將本結點的地點添加到“路由記錄”的后面，重新廣播更新后的RREQ分組。

　　③信宿的路由回答RREP。RREP包含有由信宿接收到RREQ分組的路由記錄。RREP的目的是如何把這個路由記錄告訴給信源。先假設網絡中所有的鏈路是雙向的。如果信宿到信源的“反向路由”存在，則RREP分組沿“反向路由”點到點傳輸到信源;如果信宿到信源的“反向路由”不存在，則按RREQ中的“路由記錄”(前向路由)進行反向傳送。

　　④存在單向鏈路。信宿執行與信源相同的反向路由發現過程，所不同的是信宿RREQ分組稍帶傳送RREP分組。

　　按需路由協議中，沒有周期性的網絡測試過程，各結點需要執行路由維護進程，動態地監視活動路由的運行情況。該協議的路由維護過程如下：

　　①“逐跳MAC確認”的網絡。這種網絡中，鏈路的故障或變化由MAC層通告，結點將發送“路由錯誤分組”RRER到信源;信源結點將刪除該路由，重新進行路由發現。

　　②“逐跳MAC不確認”的網絡。這種情況下，可利用無線傳輸的空間廣播性，實現等效的“被動ACK”。當結點A轉發分組到下一跳B時，B到C的分組轉發可被A監聽到。

　　③利用“端到端確認”的路由維護。端到端的確認(如TCP層的確認機制)也可以實現路由維護，信源端將檢測到并發起新的路由請求。

　　(2)AODV協議

　　AODV協議是在DSDV協議基礎上，結合類似DSR中的按需路由機制進行改進后提出的。不同之處在于AODV采用了逐跳轉發分組方式，而DSR是源路由方式。因此，AODV在每個中間結點隱式保存了路由請求和回答的結果，而DSR將結果顯示保存在路由請求和路由回答分組中。此外，AODV的另一個顯著特點是它加人了組播路由協議擴展，并支持QoS。它的缺點是不支持單向信道，原因是AODV協議基于雙向信道的假設工作，路由回答分組直接沿著路由請求的反方向回到源結點。AODV與DSR的路由發現有所不同，該協議的路由發現過程如下：

　　①RREQ分組。結點在需要(沒有到信宿的活動路由)時，向其鄰居廣播RREQ分組用于路由發現。RREQ分組包括信源地址、信源序列號、廣播ID、信宿地址、信宿序列號、跳計數。

　　(a)(信源地址+廣播ID)唯一地標識了一個RREQ分組;

　　(b)信源序列號由信源結點維護，用于表示“到信源的反向路由”的新舊;

　　(c)信宿序列號表示信源可接受的“到信宿的前向路由”的新舊，等于過去接收到的有關信宿的最大序列號。可見，結點需要為每一個信宿維護一個信宿序列號;

　　(d)RREQ的跳計數=0。

　　②對RREQ的處理。接收到RREQ的結點的處理方法為：創建一個表項，先不分配有效的序列號，用于記錄反向路徑。如果在“路由發現定時”內已收到一個具有相同標識的RREQ分組，則拋棄該分組，不作任何的處理，否則對該表項進行更新如下：

　　(a)信源序列號=RREQ分組的信源序列號;

　　(b)下一跳結點=廣播RREQ的鄰居;

　　(c)跳數=RREQ分組的“跳計數”字段值;

　　(d)設置表項的“過時定時器”。

　　如果該結點是信宿，結點的路由表中有到信宿的活動表項，且表項的信宿的序列號大于RREQ中的信宿序列號(新)，則該結點將產生“路由回答分組”RREP，并發送到信源，否則更新RREQ分組，并廣播更新后的RREQ分組。

　　(a)信宿序列號=本結點收到的該信宿相關的最大序列號;

　　(b)跳計數加1。

　　③RREP的產生。產生RREP的條件如上所述。RREP分組各字段設置如下。

　　信宿結點產生的RREP：

　　(a)如果收到的相應RREQ的信宿序列號與信宿維護的當前序列號相等，則信宿將自己維護的序列號加1，否則不變;

　　(b)信宿序列號=信宿維護的序列號;

　　(c)跳計數=0;

　　(d)定時器值。

　　中間結點產生的RREP：

　　(a)本結點所獲得的該信宿的最大序列號;

　　(b)跳計數=本結點到信宿的跳數;

　　(c)更新本結點維護的“前向路由表項”的下一跳和“反向路由表項”的前一跳。

　　④對RREP的處理。結點對接收到的RREP的處理方法為：如果沒有與RREP分組中的信宿相匹配的表項，則先創建一個“前向路表”的空表項，否則滿足如下條件對已有表項進行更新：

　　(a)現有表項的信宿序列號小于RREP分組中的信宿序列號;

　　(b)現有的表項沒有激活;

　　(c)信宿序列號相同，但RREP分組的“跳計數”值小于表項相對應的值;通過更新或創建，產生一個新的前向路徑;

　　(d)下一跳=廣播RREP的鄰居結點;

　　(e)信宿序列號=RREP中的信宿序列號;

　　(f)跳計數加1。

　　按照上述的過程，任何轉發RREP的結點，都記錄了到信宿的下一跳，當RREP到達信源時，結點地址匹配，不再轉發RREP，信源到信宿的前向路徑已建立起來了。信源可以沿這條前向路徑進行分組傳輸。

　　該協議的路由維護過程如下：

　　①與活動路由無關的結點移動，并不影響信源到信宿的尋徑。

　　②如果信源結點移動導致路由不可用，則由信源重新發起路由發現的過程。

　　③當信宿結點或活動路由的中間結點移動，導致鏈路中斷，則鏈路的“上游結點”主動發送一個RREP，該RREP的信宿序列號大于其所獲取的信宿序列號，跳計數的值設為∞，并傳播到所有的活動鄰居。該過程重復，直至所有的相關信源結點被通告到。信源結點如果需要，可重發起路由發現過程。

　　AODV與DSR的比較：

　　①DSR使用源路由技術進行路由發現，AODV通過“路由請求分組”洪泛進行路由發現，DSR在一次路由發現過程中結點獲取的路由信息遠遠多于AODV。從這個角度看，AODV進行“路由發現”可能更頻繁，所帶來的開銷比較大。

　　②DSR在一次路由發現過程中或獲取到多個替代的路由，而AODV只響應一個路由，后續的在定時內的申請被丟棄。

　　上述的表驅動路由協議和按需路由協議統稱為平面型路由協議，還有一類路由協議混合了二者優點，稱為層次性路由協議或混合型路由協議。在平面型路由協議中，所有節點功能都是對等的;在層次型路由協議中，各層次由若干個節點組成，在層次內的節點之間采用表驅動路由算法，在各層次間采用按需路由算法，代表性的協議有區域路由協議(zone routing protocol，ZRP)。ZRP協議是第一個利用分級結構混合使用按需和主動路由策略的自組網路由協議。ZRP中，分級被稱作域(zone)。域形成算法較為簡單，它是通過一個重要的協議參數-區域半徑，指定每個結點維護的區域大小，即所有距離不超過區域半徑的結點都屬于該區域。一個結點可能同時屬于多個區域。為了綜合利用按需路由和主動路由的各自優點，ZRP規定每個結點采用DVA主動路由協議維護去往區域內結點的路由，采用類似DSR協議中的按需路由機制尋找去往區域外結點的路由。ZRP協議的性能很大程度上由區域半徑參數決定。通常，小的區域半徑適合在移動速度較快的結點組成的密集網絡中使用;大的區域半徑適合在移動速度慢的結點組成的稀疏網絡中使用。