多徑路由算法簡介

多徑路由算法簡介

——2017.6.20內(nèi)容1、背景2、多徑路由算法概述3、多徑路由算法原理4、總結(jié)1、背景無線網(wǎng)絡(luò)：無線多跳網(wǎng)絡(luò)傳感器網(wǎng)絡(luò)AdHoc自組織網(wǎng)絡(luò)無線Mesh網(wǎng)絡(luò)ZigBee1、背景特征：1）無中心和自組織性2）動態(tài)變化的網(wǎng)絡(luò)拓撲3）多跳路由4）受限的無線傳輸帶寬5）節(jié)點能源有限6）安全性較差7）移動終端的局限性1、背景分類先應(yīng)式路由：DSDV（目的序號距離矢量算法）、WRP（無線路由協(xié)議）反映式路由：AODV（按需距離矢量路由算法）、DSR（動態(tài)源路由算法）混合式路由：ZRP（區(qū)域路由算法）2、多徑路由算法概述単徑路由算法：優(yōu)點：簡單缺點：負載不均，性能較低（沒有考慮到路徑的公平性，過多的依賴最短路徑或者最優(yōu)路徑；無法很好的獲取網(wǎng)絡(luò)的拓撲信息，導(dǎo)致無法有效的利用網(wǎng)絡(luò)的整體信息，進而增加了路由開銷；數(shù)據(jù)發(fā)送一般只利用一條路徑，無法實現(xiàn)并行或并發(fā)的發(fā)送數(shù)據(jù)）2、多徑路由算法概述多徑路由策略是指通過一定的約束規(guī)則，在網(wǎng)絡(luò)中找出到達目的節(jié)點的多條路徑，要求更多的節(jié)點來承擔(dān)數(shù)據(jù)包的轉(zhuǎn)發(fā)任務(wù)，然后在這多條路徑間合理的分配負載。優(yōu)點：可以較好的利用網(wǎng)絡(luò)拓撲信息；可以為不同的服務(wù)質(zhì)量要求提供不同的路徑；可以為同一類型的服務(wù)提供多條路徑，利用多條路徑來并行\(zhòng)并發(fā)發(fā)送數(shù)據(jù)，實現(xiàn)更高的服務(wù)質(zhì)量；提供網(wǎng)絡(luò)的利用效率；實現(xiàn)負載均衡，延長網(wǎng)絡(luò)生命周期挑戰(zhàn)：延時、丟包、開銷、吞吐量。。。多徑下鏈路關(guān)系：鏈路不相關(guān)、節(jié)點不相關(guān)、相關(guān)多路徑。路徑間的獨立性越高，所有路徑同時失效的可能性越低；不同路徑共享鏈路或者節(jié)點會導(dǎo)致路徑集內(nèi)部爭用信道。節(jié)點不相關(guān)的要求會導(dǎo)致路徑數(shù)量的減小，路徑之間的相關(guān)性定量指標(biāo)為“相關(guān)度（多條路徑間的共同的鏈路數(shù)）”和“交合度（因為其它路徑正在傳輸而導(dǎo)致的阻塞的平均節(jié)點數(shù)）”。2、多徑路由算法概述3、多徑路由原理1）路由發(fā)現(xiàn)2）路由維護3）路由選擇3、AODV——>AOMDV路由幀格式主要包括:RREQ–

路由請求幀RREP–

路由應(yīng)答幀RERR–

路由錯誤幀HELLO–

活躍路由鏈路監(jiān)測幀RREQ路請求由幀在兩個節(jié)點之間的路由有效、通信正常的情況下，路由協(xié)議不起任何作用只有當(dāng)源節(jié)點S需要向目的節(jié)點D發(fā)送數(shù)據(jù)包，但又沒有D節(jié)點的路由入口時才會發(fā)起路由請求，即發(fā)送路由廣播幀RREQRREQ請求幀的傳播B?B?B?B?B?B?B?BARREP應(yīng)答幀當(dāng)RREQ最終到達目的節(jié)點時，目的節(jié)點通過向該反向路由（即該RREQ傳播路線）發(fā)送RREP應(yīng)答幀，從而在該條路徑的各個節(jié)點建立通向目的節(jié)點的前向路由只有在以下情況下節(jié)點才會產(chǎn)生RREP:該節(jié)點本身就是目的節(jié)點該節(jié)點為中間節(jié)點，但是它有通向目的節(jié)點的活躍路徑當(dāng)RREP傳播到源節(jié)點時，中間節(jié)點根據(jù)該RREP更新它們各自指向目的節(jié)點的路由信息RREP路由應(yīng)答幀的傳播BAAAAAAA1）路由發(fā)現(xiàn)（AODV）當(dāng)源節(jié)點需發(fā)送數(shù)據(jù)包到目的，且源沒有到達目的的路徑時，才發(fā)起路由發(fā)現(xiàn)過程。1）路由發(fā)現(xiàn)（AOMDV）2）路由維護Hello消息Hello消息幀用于監(jiān)測活躍路徑上相鄰節(jié)點的鏈接狀況。例如：當(dāng)活躍路徑上某節(jié)點多長時間內(nèi)沒有收到該路徑上的鄰居節(jié)點發(fā)送來的Hello消息幀或其他任何幀時，該節(jié)點就認為與它與鄰居節(jié)點的鏈路已斷只有當(dāng)某節(jié)點位于某活躍路徑之上時，它才能發(fā)送Hello消息幀中間節(jié)點發(fā)起一次指向該鄰居節(jié)點的局部修復(fù)RERR傳播過程中，各中間節(jié)點刪除該失效路徑上相應(yīng)的路由信息RERR路由錯誤幀以下情況發(fā)生時，則廣播RERR路由錯誤幀：一個節(jié)點檢測到與一個鄰居節(jié)點的鏈路斷裂（即該鄰居節(jié)點不可達）節(jié)點收到一個數(shù)據(jù)包，而該節(jié)點路由表中沒有指向數(shù)據(jù)包制定的目的地址的有效路由，并且該路由并非處于修復(fù)狀態(tài)節(jié)點收到來自鄰居節(jié)點的RERR路由錯誤信息幀，該幀可能指示多個目的節(jié)點不可達2)路由維護若某一路徑上節(jié)點故障或鏈路故障，可能會引起路徑不可用。這種情況下，節(jié)點會定期廣播HELLO包給鄰居節(jié)點以監(jiān)測鏈路狀況程。RERR信息的發(fā)送方式單播將RERR信息單播發(fā)送給一個接收者重復(fù)單播將RERR信息分別的單播發(fā)送給多個接收者廣播將RERR信息同時發(fā)送給多個接收者使用IP地址255.255.255.255進行廣播2)路由維護多徑路由與單徑路由維護過程區(qū)別在于：

單徑路由協(xié)議在唯一的路徑不可用之后發(fā)起維護過程，而多徑路由協(xié)議在多條路徑都不可用之后，或者經(jīng)裁定某些路徑不可以用之后才發(fā)起路由維護過程。這將大大減少路由發(fā)現(xiàn)的次數(shù)，有利于降低路由發(fā)現(xiàn)的成本，而且路由發(fā)現(xiàn)過程中全網(wǎng)范圍內(nèi)的RREQ包泛洪會引起網(wǎng)絡(luò)擁塞，泛洪次數(shù)的減少也有利于網(wǎng)絡(luò)性能的提高。3）、路由選擇路徑數(shù)量和質(zhì)量對路徑的質(zhì)量進行估計，選擇質(zhì)量較優(yōu)的路徑，可以使用跳數(shù)、時延、負載、路徑獨立性等作為估計路徑質(zhì)量的判據(jù)。3）路由選擇流量分配策略：1）貪婪策略：當(dāng)一個數(shù)據(jù)包到達且等待轉(zhuǎn)發(fā)時，節(jié)點計算并比較每一條路徑的評價值，從中選擇最優(yōu)的一條路徑轉(zhuǎn)發(fā)改數(shù)據(jù)包。2）輪轉(zhuǎn)策略：當(dāng)一個數(shù)據(jù)包到達且等待轉(zhuǎn)發(fā)時，節(jié)點計算并比較每條路徑的轉(zhuǎn)發(fā)計數(shù)器，從中選擇轉(zhuǎn)發(fā)數(shù)據(jù)包較少的路徑轉(zhuǎn)發(fā)改數(shù)據(jù)包。3）隨機概率策略：當(dāng)一