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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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