無線傳感器網(wǎng)絡(luò)的路由算法

1、AODV議定書1.概觀由諾基亞研究中心開發(fā)的自組織網(wǎng)絡(luò)路由協(xié)議RFc標準是DSR和DSDV的綜合。它借鑒了DSR路由發(fā)現(xiàn)和維護的基本程序，以及DSDV逐跳路由、目的節(jié)點序列號和路由維護階段的定期更新機制。它以DSDV為基礎(chǔ)，結(jié)合了DSR的按需路由思想，并對其進行了改進。它應(yīng)用于無線自組織網(wǎng)絡(luò)中的路由協(xié)議，可以實現(xiàn)單播和組播路由。該協(xié)議是自組織網(wǎng)絡(luò)中按需生成路由模式的典型協(xié)議。用于特定網(wǎng)絡(luò)中的移動節(jié)點。它可以在動態(tài)變化的點對點網(wǎng)絡(luò)中確定到達目的地的路由，具有訪問速度快、計算量小、占用內(nèi)存少、網(wǎng)絡(luò)負載輕的特點。它使用目的地序列號來確保在任何時候都不會出現(xiàn)環(huán)路，從而避免了傳統(tǒng)距離矢量協(xié)議中的許多問題

2、。AODV最初提出建立一個純按需路由系統(tǒng)。網(wǎng)絡(luò)中的節(jié)點根本不依賴于活動路徑，既不維護任何路由信息，也不參與任何常規(guī)的路由表交換。節(jié)點不需要發(fā)現(xiàn)和維護到其他節(jié)點的路由，除非兩個節(jié)點需要通信或者節(jié)點提供特定服務(wù)作為中間轉(zhuǎn)發(fā)節(jié)點來維護其他兩個節(jié)點的連通性。當需要新路由時，我們以最小化廣播和傳輸延遲為目標，設(shè)計了一個協(xié)議來提高DSDV在創(chuàng)建和維護自組織網(wǎng)絡(luò)方面的性能特征。2.特征優(yōu)點：(1)基本的路由算法是距離矢量算法，但它有所改進，其思想簡單易懂。(2)按需路由協(xié)議，節(jié)點只存儲所需的路由，減少了內(nèi)存需求和不必要的復(fù)制。(3) UDP封裝，屬于應(yīng)用層協(xié)議。(4)支持中間節(jié)點的回復(fù)可以使源節(jié)點快速獲得路

3、由，有效減少廣播次數(shù)，但存在過時的路由問題。(5)通過使用目的序列號來避免路由環(huán)路，解決了傳統(tǒng)的基于距離矢量的路由協(xié)議的無限計數(shù)問題。(6)具有網(wǎng)絡(luò)可擴展性。(7)對活動路徑上斷開的鏈接做出快速響應(yīng)。缺點：在無線個人局域網(wǎng)中，拓撲結(jié)構(gòu)相對簡單，網(wǎng)絡(luò)規(guī)模相對較小，節(jié)點位置不固定。設(shè)計時首先要考慮的因素是簡單、節(jié)能等。3.路線發(fā)現(xiàn)(a)廣播RREQ路由請求幀(b)中間節(jié)點向源節(jié)點更新它們的路由表(c)如果接收到RREQ的節(jié)點不是目的地節(jié)點并且沒有到目的地節(jié)點的更新的有效路由，則轉(zhuǎn)發(fā)RREQ(d)中間節(jié)點維護指向路由發(fā)起節(jié)點(源節(jié)點)的反向路由(e)目的節(jié)點或具有到目的節(jié)點的有效路由的中間節(jié)點生成R

4、REP路由響應(yīng)幀(f)通過先前建立的反向節(jié)點向源節(jié)點單播RREP(g)當源節(jié)點接收到RREP響應(yīng)幀時，源節(jié)點可以向目的節(jié)點發(fā)送數(shù)據(jù)包。4.路由維護你好消息當TTL=1時，問候信息幀實際上是RREP幀。生存時間是一個數(shù)據(jù)包字段，它指示幀的傳播跳數(shù)。Hello消息幀用于監(jiān)控活動路徑上相鄰節(jié)點的鏈路狀態(tài)。例如，當活動路徑上的節(jié)點在允許的_ hello _ loss * hello _ interval的毫秒內(nèi)沒有接收到Hello消息幀或路徑上的相鄰節(jié)點發(fā)送的任何其他幀時，該節(jié)點認為其與相鄰節(jié)點的鏈路已斷開。只有當一個節(jié)點在活動路徑上時，它才能發(fā)送Hello消息幀。5.判斷新舊路由信息AODV依靠網(wǎng)絡(luò)

5、中的每個節(jié)點來維護自己的序列號。在廣播路由請求幀RREQ之前，源節(jié)點應(yīng)該更新它自己的序列號，也就是說，將序列號加1。在生成RREP響應(yīng)幀之前，目的節(jié)點還應(yīng)該在自己的序列號中添加1。當每個節(jié)點在自己的序列號上加1時，它被認為是一個無符號數(shù)。通過將來自目的節(jié)點的路由控制幀中的序列號SN1與該節(jié)點維護的目的節(jié)點的序列號SN2進行比較，可以確定該鏈路的新舊程度，然后可以進行相應(yīng)的處理。如果SN2-SN10(減去有符號數(shù))表示路由表中維護的信息已過期，則路由信息應(yīng)更新為路由控制幀中的最新路由信息。6.擁塞控制當源節(jié)點在發(fā)送RREQ后的指定時間內(nèi)沒有從目的節(jié)點接收到RREP時，它可以選擇再次發(fā)送RREQ路

6、由請求幀。如果在嘗試RREQ_RETRIES后仍未收到RREP，請在路由表中標記目標節(jié)點不可達，并通知應(yīng)用層。每次重傳RREQ請求幀時，等待RREP響應(yīng)幀的時間應(yīng)根據(jù)原始時間乘以2，以避免擁塞。DSR議定書1.概觀動態(tài)源路由是一種按需路由協(xié)議，它允許節(jié)點動態(tài)發(fā)現(xiàn)到目的節(jié)點的多跳路由。源路由是指每個數(shù)據(jù)包的報頭攜帶一個節(jié)點列表，所有數(shù)據(jù)包在到達目的節(jié)點之前都必須經(jīng)過該列表，也就是說，數(shù)據(jù)包包含一條到目的節(jié)點的完整路由。在自組織網(wǎng)絡(luò)中，移動節(jié)點需要其他節(jié)點的幫助才能將數(shù)據(jù)包傳輸?shù)侥康墓?jié)點，目的節(jié)點能夠快速適應(yīng)節(jié)點移動時路徑的變化，并且能耗較低2.特征優(yōu)點：(1)采用源路由機制，避免路由環(huán)路。(2)

7、采用路由緩存技術(shù)，避免了每次路由中斷時都需要進行路由發(fā)現(xiàn)，減少了路由請求信息對信道的占用(3)中間節(jié)點不需要存儲轉(zhuǎn)發(fā)數(shù)據(jù)包所需的路由信息，網(wǎng)絡(luò)開銷較小缺點：(1)隨著跳數(shù)的增加，包頭長度線性增加，開銷較大(2)路由請求包RREQ通過洪泛擴散到整個網(wǎng)絡(luò)，導(dǎo)致網(wǎng)絡(luò)負載過重(3)來自相鄰節(jié)點的RREQ分組可能在某個節(jié)點上沖突。解決方案是在發(fā)送RREQ數(shù)據(jù)包時引入隨機延遲(4)當源節(jié)點發(fā)送路由請求包RREQ時，可能會收到多個節(jié)點緩存的路由信息到達目的節(jié)點，導(dǎo)致競爭。解決方案：如果一個節(jié)點聽說其他節(jié)點發(fā)送的RREQ數(shù)據(jù)包中的路由信息包含較少的跳數(shù)，該節(jié)點將停止發(fā)送。(5)源節(jié)點發(fā)送路由請求包RREQ時，

8、可能會接收到多個節(jié)點緩存的路由信息到達目的節(jié)點，但有些路由信息可能已經(jīng)過時。解決方案：當引入定時器并且鏈路斷開時，整個網(wǎng)絡(luò)應(yīng)該被淹沒。3.路線發(fā)現(xiàn)(洪水路線)當一個節(jié)點要發(fā)送數(shù)據(jù)包時，源節(jié)點首先檢查緩存中是否有到目的地的路由信息，如果有未過期的路由，它可以直接采用，否則，它將廣播并發(fā)送一個路由請求包。(1)初始廣播路由請求(2)中間節(jié)點接收后，進行如下處理：如果之前已經(jīng)收到請求，則放棄該請求；如果該節(jié)點的地址在請求中，則放棄該請求；如果到達目的節(jié)點，它將返回路由回復(fù)。否則，將您自己的地址添加到數(shù)據(jù)包的路由記錄中，并將其轉(zhuǎn)發(fā)給相鄰節(jié)點(3)如果是目的節(jié)點，返回路由應(yīng)答包，當源節(jié)點收到路由應(yīng)答時，

9、路由發(fā)現(xiàn)過程結(jié)束。如果RREQ分組存在于最近接收的“歷史RREQ列表”中，或者路由記錄包括該節(jié)點，則該節(jié)點將刪除“路由請求”分組，以防止循環(huán)處理和路由循環(huán)。4.路由維護路由建立后，源節(jié)點將傳輸數(shù)據(jù)，在此過程中需要維護已建立的路由。源節(jié)點可以通過路由維護機制檢測網(wǎng)絡(luò)拓撲的變化，從而知道到目的節(jié)點的路由是否可用。當路由維護檢測到正在使用的路由有問題時，它將向源節(jié)點發(fā)送RERR(路由錯誤消息)。收到RERR后，源節(jié)點將從其路由緩存中刪除包含故障鏈路的所有路由，并重新啟動路由發(fā)現(xiàn)過程。DSR與ADOV之比較1基本算法類型：AODV采用逐跳路由算法，每個節(jié)點只記得下一跳；DSR使用源路由算法，每個節(jié)點都

10、記住整個路由。2 .路徑支持：AODV單一路徑；DSR多路支持。如果一條路徑損壞，可以使用路由緩存中的其他路徑。3定期廣播：AODV也定期發(fā)送Hello數(shù)據(jù)包，以維護路由；DSR不要求定期廣播。4邏輯結(jié)構(gòu)：兩者都是平面路由，協(xié)議中的所有節(jié)點都具有同等的地位。5單向鏈路支持：AODV依賴于對稱鏈路；DSR可以處理不對稱鏈接的網(wǎng)絡(luò)。6 .路由獲取機會：DSR首先檢查緩存中是否有到目的節(jié)點的未到期路由，如果有，則直接使用可用路由，否則，啟動路由發(fā)現(xiàn)過程；每當AODV需要到新節(jié)點的路徑時，它就會啟動路由發(fā)現(xiàn)過程。注水(注水方法)1.概觀泛洪意味著從任何節(jié)點通過路由器發(fā)送的數(shù)據(jù)包將被發(fā)送到連接到路由器的

11、所有其他節(jié)點(發(fā)送數(shù)據(jù)包的節(jié)點除外)。首先，源節(jié)點通過網(wǎng)絡(luò)向其每個鄰居節(jié)點發(fā)送數(shù)據(jù)的副本，然后每個鄰居節(jié)點相互發(fā)送數(shù)據(jù)，發(fā)送數(shù)據(jù)的節(jié)點除外。這一直持續(xù)到數(shù)據(jù)傳輸目標節(jié)點或數(shù)據(jù)集壽命(TTL)為0。2.特征優(yōu)點：它易于實現(xiàn)，容錯性強，不需要消耗計算資源來維護網(wǎng)絡(luò)拓撲信息和實現(xiàn)復(fù)雜的路由發(fā)現(xiàn)算法，適用于魯棒性要求高的場合。缺點：(1)存在信息爆炸問題，即一個節(jié)點可能獲得一個數(shù)據(jù)的多個副本。(2)會有部分重疊。如果同一觀測環(huán)境中同類傳感器的兩個同事對一個事件做出反應(yīng)，并且他們收集的數(shù)據(jù)具有相同的屬性和相似的值，那么這兩個節(jié)點周圍的相鄰節(jié)點將接收到數(shù)據(jù)的兩個副本。(3)盲目使用資源，即擴散方法沒有考慮

12、每個節(jié)點的能量可用性，因此無法做出相應(yīng)的自適應(yīng)路由。3.算法模型接收消息的任何節(jié)點ni的動作可以用下面的偽代碼來描述。每條消息都包含TTL(消息壽命)、DATA等。(1)信宿和其他節(jié)點廣播它們自己的位置信息和序列號；(2)源節(jié)點廣播消息；(3)如果接收消息的節(jié)點是信宿，則消息已經(jīng)被發(fā)送到目的地；否則轉(zhuǎn)到(4)；(4)如果消息的TTL-1等于0或者節(jié)點已經(jīng)接收到消息，則轉(zhuǎn)到(5)，否則轉(zhuǎn)到(6)；(5)節(jié)點丟棄消息；(6)該節(jié)點將消息轉(zhuǎn)發(fā)給其所有相鄰節(jié)點。閑聊協(xié)議1.概觀流言協(xié)議是對洪泛協(xié)議的改進，在洪泛協(xié)議中，節(jié)點將生成或接收的數(shù)據(jù)隨機轉(zhuǎn)發(fā)給一個或多個相鄰節(jié)點，從而避免了以廣播形式傳輸信息的能

13、耗，避免了內(nèi)爆，但增加了延遲，避免了重疊問題。每次選擇下一跳節(jié)點時，都沒有采用相關(guān)的路徑優(yōu)化算法，因此選擇的路由往往不理想，這將導(dǎo)致端到端時延增加或數(shù)據(jù)包到達目的節(jié)點前的生命周期結(jié)束。2.算法節(jié)點n通過向隨機選擇的b鄰居發(fā)送消息m來完成該消息傳播：當(節(jié)點p從節(jié)點q接收到消息m)時如果(p收到的m不超過Ftimes)p將m統(tǒng)一發(fā)送給B，隨機發(fā)送給該p的鄰居知道還沒有見過米b表示在一次傳播中可以轉(zhuǎn)發(fā)消息的鄰居節(jié)點的最大數(shù)量；參數(shù)f決定了一個節(jié)點向其鄰居轉(zhuǎn)發(fā)相同消息的次數(shù)。例如，如果f為1，節(jié)點只將第一個接收到的消息M轉(zhuǎn)發(fā)給它的B鄰居，稍后到達的消息M將被忽略。通過調(diào)整B和F，我們可以在效率和成本

14、之間找到平衡，以滿足不同的需求。當f為1時，b是網(wǎng)絡(luò)中節(jié)點的最大數(shù)量，這就是泛洪協(xié)議。自旋協(xié)議1.概觀傳感器信息協(xié)商協(xié)議(spin)是一種以數(shù)據(jù)為中心的自適應(yīng)通信路由協(xié)議。它利用節(jié)點間的協(xié)商機制和資源自適應(yīng)機制，解決了傳統(tǒng)協(xié)議中資源內(nèi)爆、重疊和盲目使用的問題。SPIN協(xié)議有三種數(shù)據(jù)包類型，即ADV、請求和數(shù)據(jù)。ADV用于廣播元數(shù)據(jù)(元數(shù)據(jù)指數(shù)據(jù)的屬性)，REQ用于請求發(fā)送數(shù)據(jù)，數(shù)據(jù)是傳感器收集的數(shù)據(jù)包。洪水得到了改善?？紤]到WSN數(shù)據(jù)的冗余性，相鄰節(jié)點感知到的數(shù)據(jù)是相似的，通過節(jié)點間的協(xié)商減少了數(shù)據(jù)傳輸，只廣播其他節(jié)點沒有的數(shù)據(jù)。2.路由過程傳感器節(jié)點與自旋協(xié)議交互的基本過程；(1)節(jié)點a收集

15、數(shù)據(jù)m.帶有m個元數(shù)據(jù)(元數(shù)據(jù)是指數(shù)據(jù)的屬性)的Adv包被向外廣播。(2)鄰居節(jié)點B接收到A的adv數(shù)據(jù)包，并根據(jù)其攜帶的元數(shù)據(jù)判斷是否需要數(shù)據(jù)M。如果不需要，銷毀adv數(shù)據(jù)包。如果需要，生成相應(yīng)的請求數(shù)據(jù)包并向外部廣播。(3)節(jié)點甲接收來自節(jié)點乙的請求數(shù)據(jù)包請求，并生成相應(yīng)的異相廣播數(shù)據(jù)包。(4)節(jié)點B接收到節(jié)點A的數(shù)據(jù)包，并存儲該數(shù)據(jù)包(5)節(jié)點B繼續(xù)廣播具有M個元數(shù)據(jù)的adv數(shù)據(jù)包，以便在網(wǎng)絡(luò)中傳輸數(shù)據(jù)M。3.特征優(yōu)點：(1)簡單，一個節(jié)點只需要知道它的鄰居節(jié)點，不需要其他拓撲信息(2)節(jié)點只廣播數(shù)據(jù)，其他節(jié)點不必減少冗余數(shù)據(jù)，從而有效降低能耗。(3)利用三步握手機制解決內(nèi)爆(4)利用數(shù)據(jù)融合部分解決重疊問題(5)不需要路線維護(6)對網(wǎng)絡(luò)拓撲數(shù)不敏感缺點：(1)本質(zhì)上，它仍在向整個網(wǎng)絡(luò)傳播新消息，開銷相對較大(2)當多個節(jié)點同時向同一個節(jié)點發(fā)送請求消息時，需要一種退避算法定向擴散協(xié)議1.概觀定向擴散路由協(xié)議是一種重要的基于數(shù)據(jù)和查詢驅(qū)動的路由機制。匯聚節(jié)點通過興趣消息發(fā)送查詢?nèi)蝿?wù)，并將興趣消息泛洪到整個區(qū)域或部分區(qū)域的所有傳感器節(jié)點。興趣信息用于表示查詢?nèi)蝿?wù)，表達網(wǎng)絡(luò)用戶對檢測區(qū)域感興趣的信息，如檢測區(qū)域的溫度、濕度