經典路由算法

1、經典路由算法一、先驗式路由協(xié)議(DSDV)先驗式路由協(xié)議是一種基于表格的路由協(xié)議。在這種協(xié)議中，每個節(jié)點維護一張或多張表格，這些表格包含到達網絡中其它所有節(jié)點的路由信息。當檢測到網絡拓撲結構發(fā)生變化時，節(jié)點在網絡中發(fā)送路由更新信息。收到更新信息的節(jié)點更新自己的表格，以維護一致的、及時的、準確的路由信息。不同的先驗式路由協(xié)議的區(qū)別在于拓撲更新信息在網絡中傳輸的方式和需要存儲的表的類型。先驗式路由協(xié)議不斷的檢測網絡拓撲和鏈路質量的變化，根據變化更新路由表，所以路由表可以準確地反映網絡的拓撲結構。源節(jié)點一旦需要發(fā)送報文，可以立即得到到達目的節(jié)點的路由。(DSDV、OLSR路由協(xié)議等很多普通的因特網路

2、由協(xié)議)它們查找路由是不依賴于路徑上的節(jié)點是否要發(fā)包，而是每個節(jié)點維護一張包含到達其它節(jié)點的路由信息的路由表。節(jié)點間通過周期性的交換路由信息來不斷更新自身的路由表，以便能夠及時的反映網絡拓撲結構和變化，以維護一致的、及時的、準確的路由信息。DSDV:目的節(jié)點序列距離矢量協(xié)議（待補充）可以解決路由成環(huán)問題，每一個節(jié)點維持一個到其它節(jié)點的路由表，表的內容為路由的“下一跳”節(jié)點。1）給每條路徑增加了一個序列號碼2）每個目的節(jié)點會定期廣播一個單調遞增的偶數序列號號碼3）當一個節(jié)點發(fā)現它到某個目的節(jié)點的路徑斷開時，它把到這個節(jié)點的距離設為無窮大。并且將這條路徑的序列號加1（此時為奇數），然后向網絡中廣播

3、這個更新包。當這條路徑修復時，它又將序列號加1然后廣播出去。換另一種方式來說，每個節(jié)點都保持著一張路由表，路由表中的每一項記錄了它到目的節(jié)點的距離和序列號，也就是（s,d）我們假設有一目的節(jié)點為D,當以下任何一情況發(fā)生時，都會發(fā)送更新：1）D定期將自己的序列號加2并廣播出去，即（S,0）2）如果節(jié)點X要通過Y到達節(jié)點D,當X和Y之間的連接斷開后，X將到D的路徑的序列號加1,同時將路徑值設為卩然后將信息發(fā)送給鄰居。參考資料： HYPERLINK /candycatl992/article/details/8100146 /candycatl992/article/details/8100146C

4、SDN博客DSDV協(xié)議DSDV創(chuàng)新之處是為每一條路由設置一個序列號，序列號大的路由為優(yōu)選路由序列號相同時，跳數少的路由為優(yōu)選路由。正常情況下，節(jié)點廣播的序列號是單調遞增的偶數，當節(jié)點B發(fā)現到節(jié)點D的路由（路由序列號為s）中斷后，節(jié)點B就廣播一個路由信息，告知該路由的序列號變?yōu)閟+l,并把跳數設置為無窮大，這樣,任何一個通過B發(fā)送信息的節(jié)點A的路由表中就包括一個無窮大的距離，這一過程直到A收到一個到達D的有效路由（路由序列號為s+1-1）為止。在此方案中，網絡內所有的移動終端都建立一個路由表，包括所有的目的節(jié)點到達各個目標節(jié)點的跳躍次數（或標識距離矢量的路徑矩陣）。每個路由記錄都有一個由目標節(jié)點

5、設定的序列號。序列號使移動終端可以區(qū)分當前有效路由路徑和已過時的路由路徑。路由表周期性地做全網更新以維護全網的通信有效性。通常，為了減少由于路由表更新而產生的大量路由信息傳遞，減少網絡路由開銷，可以采用兩種路由更新方式。1）第一種是全清除方式：即通過多個網絡協(xié)議數據單元將路由更新信息在全網中傳輸。如果網絡內終端出現移動，則產生的新路由分組信息不定期的傳達至網絡內所有終端。2）第二種是部分更新方式：或稱為增量更新方式，即在最后一次全清除傳輸后，只傳遞那些涉及變化了的路由信息進行傳輸，這些信息通常被放置在一個標準的NPDU里，從而減少路由信息的傳遞量。在增量更新方式中移動終端可以增加另外一個附加的

6、表來存儲路由更新信息。新路由信息的廣播信息包含目標節(jié)點的地址，到每個目標節(jié)點的跳數、接收信息的序列號，以及獨有的廣播序列號。新路由信息適用最新的序列號。如果兩次更新具有相同的序列號，則具有較小的距離矢量陣的路由具有優(yōu)先權。因為它代表路徑最短（或跳數最少）。在通常情況下，從源節(jié)點到目的節(jié)點可能存在多條路徑，在最佳路由路徑的確定過程中，移動終端跟蹤不同路由路徑的時間，最佳路由路徑就是時間最短的路徑。在找到最佳路徑之前，該時間呈收斂性漲落。一旦路徑確定，這些信息就存放到每一個終端的路由表中，直到節(jié)點收到新的路由信息。二、反應式路由協(xié)議(AODV)反應式路由選擇協(xié)議是一種當需要一條從源節(jié)點到目的節(jié)點的

7、路徑進行數據發(fā)送時才查找路由的路由選擇方式。節(jié)點并不保存整個網絡的及時準確的路由信息。當源節(jié)點要向目的節(jié)點發(fā)送報文時，源節(jié)點在網絡中發(fā)起路由查找過程，找到相應的路由后，才開始發(fā)送報文。為了提高效率，節(jié)點可以將找到的路由保存在緩存中供后續(xù)發(fā)送使用。反應式路由協(xié)議按需路由的特點可以較好地適應節(jié)點移動較為頻繁的無線網絡環(huán)境，節(jié)點發(fā)生移動后，只需要更新需要發(fā)送數據的相關路徑的路由信息即可。AODV:adhocon-demanddistancevetorroutin無線自組網按需平面距離矢量路由協(xié)議0S2REEQ廣播丘運kRREQ當一個節(jié)點需要給網絡中的其他節(jié)點傳送信息時，如果沒有到達目標節(jié)點的路由，則

8、必須先以多播的形式發(fā)出路由請求消息RREQ(routerequestpacket)。RREQ報文中記錄著發(fā)起節(jié)點和目標節(jié)點的網絡層地址。S3RREP單播,I.Fjg.3RREfosjii鄰近節(jié)點收到RREQ，首先判斷目標節(jié)點是否為自己。如果是，則向發(fā)起節(jié)點發(fā)送路由應答消息RREP(routereplypacket)；如果不是，則首先在路由表中查找是否有到達目標節(jié)點的路由，如果有，則向源節(jié)點單播RREP，否則繼續(xù)轉發(fā)RREQ進行查找。直至發(fā)現目的節(jié)點。在網絡資源充分的情況下，AODV協(xié)議可以通過定期廣播hello報文來維護路由，一旦發(fā)現某一個鏈路斷開，節(jié)點就發(fā)送ERROR報文通知那些因鏈路斷開而

9、不可達的節(jié)點刪除相應的記錄或者對已存在的路由進行修復。在AODV中，整個網絡都是靜止的除非有連接建立的需求。這就是說一個網絡節(jié)點要建立連接時才廣播一個連接建立的請求。其他的AODV節(jié)點轉發(fā)這個請求消息，并記錄源節(jié)點，和回到源節(jié)點的臨時路由。當接收連接請求的節(jié)點知道到達目的節(jié)點的路由時，就把這個路由信息按照先前記錄的回到源節(jié)點的臨時路由發(fā)回源節(jié)點。于是源節(jié)點就開始使用這個經由其他節(jié)點并且有最短跳數的路由。當鏈路斷掉，路由錯誤就被回送給源節(jié)點，于是源節(jié)點就重新發(fā)起路由查找的過程。參考資料：/item/AODV/7811971?fr=aladdin百度百科AODV三、基于位置的路由協(xié)議(GPSR)G

10、PSR路由協(xié)議：greedyperimeterstatelessroutingGPSR路由算法是使用地理位置信息實現路由(非輔助作用)的一種算法，它使用貪婪算法來建立路由。當節(jié)點S需要向節(jié)點D轉發(fā)數據分組的時候，它首先在自己的所有鄰居節(jié)點中選擇一個距節(jié)點D最近的節(jié)點作為數據分組的下一跳，然后將數據傳送給它。該過程一直重復，直到數據分組到達目的節(jié)點D或某個最佳主機。貪心算法：在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，只做出在某種意義上的局部最優(yōu)解。貪心算法不是對所有問題都能得到整體最優(yōu)解，關鍵是貪心策略的選擇，選擇的貪心策略必須具備無后效性，即某個狀態(tài)以前

11、的過程不會影響以后的狀態(tài)，只與當前狀態(tài)有關。一般步驟是：建立數學模型來描述問題；把求解的問題分成若干個子問題；對每一子問題求解，得到子問題的局部最優(yōu)解；把子問題的局部最優(yōu)解合成原來問題的一個解。參考資料： HYPERLINK /qq_32400847/article/details/51336300 /qq_32400847/article/details/51336300從零開始學貪心算法空洞問題：產生或收到數據的節(jié)點向以歐氏距離計算出的最靠近目的節(jié)點的鄰節(jié)點并向其轉發(fā)數據,但由于數據可能會到達沒有比現節(jié)點更接近目的點的區(qū)域(稱為空洞),導致數據無法傳輸。解決方法：當出現這種情況時,空洞周圍的節(jié)點能夠探測到,并利用右手法則沿空洞周圍傳輸來解決此問題。優(yōu)點：該協(xié)議避免了在節(jié)點中建立、維護、存儲路由表,只依賴直接鄰