一種基於AOMDV的能量感知節點不相交多路徑路由算法的製作方法
2023-05-15 10:00:57 1
本發明屬於無線傳感器網絡技術領域，涉及一種基於AOMDV的能量感知節點不相交多路徑路由算法。
背景技術：
近些年來，無線通信技術和無線網絡的應用越來越廣泛。移動自組織通信網絡是由無線移動節點構成，利用移動終端的路由轉發功能，具有組網速度快，抗毀能力強等特點。在無基礎設施的情況下進行通信，從而彌補了無網絡通信基礎設施可使用的缺陷。
在移動自組織網絡中，源節點通過無線傳輸的方式，將數據包經過相鄰節點、中間節點發送到目的節點，一旦中間某個節點出現問題，或者是因為節點的移動，就會造成網絡通信失效，從而影響到網絡數據傳輸的效果。在某些特殊的應用場景下，可靠性保證和容錯性保證是網絡運行的前提。目前，常用的按需路由協議AODV(Ad hoc On-demand Distance Vector Routing)、DSR(Dynamic Source Routing)等，都是單路徑路由，頻繁的全網泛洪，路由的開銷很大，數據報文傳送時延較大，不適合實時性的應用，而且無線網絡節點移動性高，帶寬資源有限，連接中斷率高。因而傳統的無線路由算法已漸漸不在適用了。
當前提出了很多多路徑路由的思想。多路徑路由提供了一些機制來分配通信量、平衡網絡負載，以及提供容錯能力，受到很多人的研究。多路徑路由可以分為3種：節點不相交多路徑(Node-Disjoint)、鏈路不相交多路徑(Link-Disjoint)和相交多路徑。多路徑可以提高路由的可靠性和容錯性，使用多路徑策略改善了通訊性能，避免了單路徑由於節點能量消耗殆盡導致的數據傳輸失敗。AOMDV(AdHoc on-Demand Multipath Distance Vector)路由協議是在AODV路由協議基礎上設計多徑路由協議，該協議經過一次路由發現過程，能夠找到多條從一個節點到另一個節點的路徑，這些路徑是節點不相交或鏈路不相交。當其中一條出錯時，直接選用其他可用路徑，而不用重新啟動路由發現過程，增加了容錯能力和穩定性，然而，它沒有考慮鏈路擁塞、鏈路丟包率、帶寬等其它參數，因此得到的多路徑不一定是最好的，其次，AOMDV協議從路由表中選擇路徑傳輸數據時，選擇的是最早發現的路徑，但最早的路逕往往不一定是最優的。
技術實現要素：
有鑑於此，本發明的目的在於提供一種基於AOMDV的能量感知節點不相交多路徑路由算法，該算法針對由於節點失效，節點移動等問題，綜合考慮了不相交多路徑、鏈路質量和節點能耗等因素，從而達到降低節點能耗、均衡網絡負載，提高能量的利用效率的目的。
為達到上述目的，本發明提供如下技術方案：
一種基於AOMDV的能量感知節點不相交多路徑路由算法，在該方法中，根據在路由發現階段、路由回復階段，通過泛洪，查找出所有可能的不相交多路徑；再根據在數據傳輸階段，對路由數據包設計，在路由表中增加節點能量欄位用來統計當前節點的能量，根據每條路徑節點的能量給每條路徑分配權重，篩選鏈路，獲取最優鏈路；具體包括以下步驟：
S1：在鄰居發現階段，首先網絡中每個節點通過廣播HELLO包，在規定時間間隔內交互報文發現他們的鄰居節點，確定鏈路，為在鄰居發現過程中交換各自的能量信息，丟棄節點能量較低的節點；在鄰居發現階段後，每個節點都有了其鄰居節點的信息；
S2：在多路徑路由階段，路由發現階段，以源節點為起點，首先通過泛洪RREQ包，通過不同的中間節點多次轉發到達目的節點，目的節點維持多條到達源節點的路由，發現從源節點到目的節點的所有不相交多路徑，存儲路徑信息在路由表中；
S3：在數據傳輸階段，源節點到目的節點的多條路徑被存儲在路由表中，路徑能量等級分有五種，這些能量等級用來分配鏈路權重，通過篩選出能量較好的路徑進行數據通信，在最小權重路徑發送數據包。
進一步，在步驟S1中，鄰居發現過程中，中間節點的能量水平有限，當有節點能量很低時，但又需要轉發路由請求包RREQ時，這種情況是很危險的，如果使用這種節點建立路徑會因節點能量過低而導致網絡分割的現象出現，所以要避免這類節點參與到多徑路由過程中；在本方法中，設置一個能量閾值來丟棄節點能量過低的節點，取能量閾值為Et，當鄰居節點自身的剩餘能量率，即目前節點能量與初始能量的比值低於這個閾值時，將丟棄該鏈路，不再繼續轉發，從而有效地保護了能量較低的節點。
進一步，所述步驟S2具體包括：
S21：當源節點需要發送數據包時，首先檢測源節點路由表中是否存在到達目的節點的路徑，若存在，將按著已用的路徑發送數據，不需要重新路由的過程；
S22：已有路徑失效，重新路徑發現過程，主要使用路由請求(RREQ)、路由回復(RREP)兩種類型的控制信息；源節點在整個網絡中泛洪RREQ信息，通過不同的中間節點多次轉發到目的節點；中間節點通過Routing_list檢測發來的RREQ是否是新的；Routing_list包含泛洪ID，在網絡中唯一標識RREQ包；中間節點收到的請求包已在Routing_list中，將認為是重複的RREQ包，將丟棄停止廣播；否則將中間將創建新的Routing_list並更新路由表，繼續泛洪RREQ信息包；
S23：在整個網絡中，只有目的節點可以在收到RREQ數據包時發送RREP數據包，這樣以便於得到節點不相交路徑；目的節點每收到一個RREQ數據包，響應一個RREP數據包，沿著RREQ數據包的反向路徑單播RREP數據包；
S24：在目的節點收到第一個路由請求包時，啟動定時器，在一定周期內收到的REEQ包，將進行響應，丟棄跳數太多或者時延太長的路徑，留下相對最優的節點不相交多路徑。
進一步，所述步驟S3具體包括：
S31：在RREQ數據包欄位中加入首跳節點能量和源節點能量；首跳節點能量和源節點能量顯示當前節點的能量；
S32：在RREP數據包欄位中加入目的節點能量和首跳節點能量；目的節點能量和首跳節點能量顯示當前節點的能量；
S33：在完成多路徑發現過程後，源節點到目的節點的可靠多路徑被存儲在路由表中，然後源節點根據節點能量分配路徑權重，發送數據包將選擇在最小權重路徑上；
S34：當前的數據包傳輸在指定的時間內完成，然後下一個數據包將繼續根據當前路徑權重，選擇權重最小的路徑進行傳輸數據包，避免了一直使用同一路徑造成的節點過度消耗死亡，均衡整個網絡負載目的；
S35：當權重最小的路徑傳輸數據包未在指定時間內完成，數據重傳三次沒有收到確認，將重新開始路由發現過程。
本發明的有益效果在於：在本發明提供的算法中，建立源節點到目的節點的多條節點不相交路徑，基於路徑上節點的能量等級分配權重，節點能量最大、權重最小的路徑傳輸數據包，每次發送數據包都是選擇的權重最低的路徑。當都失效時，將重新路由發現過程，這樣的傳輸方式將均勻的分布到多個路徑上，這樣可以確保沿著路徑的節點的能量被均勻地利用，還可以節點過度消耗，延長網絡的生存周期。
附圖說明
為了使本發明的目的、技術方案和有益效果更加清楚，本發明提供如下附圖進行說明：
圖1為本發明所述能量高效不相交多路徑路由算法的流程圖；
圖2為本發明所述RREQ包的報文格式；
圖3為本發明所述RREP包的報文格式；
圖4為本發明所述路由請求RREQ發送流程圖；
圖5為本發明所述路由回復RREP發送流程圖；
圖6為本發明所述路徑選擇示意圖；
圖7為本發明的說明框圖。
具體實施方式
下面將結合附圖，對本發明的優選實施例進行詳細的描述。
圖1是本發明提出的能量感知節點不相交多路徑路由算法流程圖。根據在路由發現階段、路由回復階段，通過泛洪，查找出所有可能的不相交多路徑；在根據在數據傳輸階段，對路由數據包設計，在路由表中增加節點能量欄位用來統計當前節點的能量，根據每條路徑節點的能量給每條路徑分配權重，篩選鏈路，獲取最優鏈路。路由算法包括以下步驟：
S1：在鄰居發現階段，首先網絡中每個節點通過廣播HELLO包，在規定時間間隔內交互報文發現他們的鄰居節點，確定鏈路，為在鄰居發現過程中交換各自的能量信息，丟棄節點能量較低的節點。在鄰居發現階段後，每個節點都有了其鄰居節點的信息。
節點通過鄰居發現過程找到相鄰節點，相鄰節點的剩餘能量率與該節點的能量閾值比較，當相鄰節點的剩餘能量率低於該閾值時，將丟棄該鏈路，不在繼續鄰居發現過程，只有當節點的剩餘能量率高於閾值的時候，才繼續路由建立過程。
S2：在多路徑路由階段，主要考慮形成節點不相交的情況。多路徑情況主要是考慮路徑的穩定性。節點不相交多路徑，就是各條路徑中除源節點和目的節點之外沒有其他任何共用節點。鏈路不相交多路徑是指各條路徑間沒有任何共用的鏈路，但有可能有共用的節點。相交多路徑是指各條路徑間既有共用的節點，又有共用的鏈路。當共享節點失效或者共享鏈路終端，就會導致多條使用共享節點的路徑失效，其容錯能力就差很多，因此，節點不相交路由容錯能力最強。
單路徑的穩定性：路徑上各條鏈路失效的概率為P，整條路徑失效率為PLF，路徑穩定概率為PLS，則路徑1失效率為PLF1，穩定概率為PLS1。
PLF1＝1-(1-P)n
PLS1＝1-PLF1＝(1-P)n
單一路徑時，路徑的穩定性與節點個數成指數關係，路徑上節點越多，穩定性越差。
多路徑的穩定性：當擁有兩條路徑組成是，每條路徑上同樣有n個節點，則其路徑2失效率為PLF2，穩定概率為PLS2。
PLF2＝[1-(1-P)n][1-(1-P)n]＝1-2(1-P)n+(1-P)2n
PLS2＝1-PLF2＝2(1-P)n-(1-P)2n
當兩條多路徑，每條路徑有n個節點，m條共同鏈路，則此時路徑3失效率PLF3，穩定概率為PLS3。
PLS3＝{1-[1-(1-P)n-m][1-(1-P)n-m]}(1-P)m＝2(1-P)n-(1-P)2n-m
PLF3＝1-PLS3＝1-2(1-P)n+(1-P)2n-m
綜上，多路徑類型的公共鏈路越多，路徑失效概率越大，節點不相交的穩定性最高。而且，在無線傳輸的過程中，網絡中有信號幹擾的問題，在共享節點處需要競爭信道，相交多路徑不僅存在共享節點還有共享鏈路，相交多路徑幹擾最大，節點不相交多路徑間幹擾最小。此外，在節點能量有限的情況下，可以將負載分配到不同的路徑上，減少端到端的時延。在節點不相交的情況下還能減少由公共節點導致的排隊時延。所以本發明的多路徑的策略選擇節點不相交多路徑。
路由發現階段，以源節點為起點，首先通過泛洪RREQ包，通過不同的中間節點多次轉發到達目的節點，目的節點維持多條到達源節點的路由，發現從源節點到目的節點的所有不相交多路徑，存儲路徑信息在路由表中。
圖2和圖3分別是基於本發明的路由算法改進的RREQ和RREP數據包報文格式。RREQ ID和RREP ID是個序列號，用它和發起節點的IP就可以唯一標識一個路由請求信息。在RREQ包中目的節點序列號表示到目的節點的最新序列號，首跳表示存在的多路徑，存儲第一跳信息節點。
圖4為本發明的能量感知節點不相交多路徑路由請求過程：
1、當節點要向另一節點發送數據時，源節點首先查詢路由表，看有沒有到目的節點的活躍路由，如果有則按照路由表中權重最小的路由將數據發送給目的節點；如果沒有，該節點將廣播RREQ信息包尋找目的節點；
2、鄰居節點收到RREQ包，先通過Routing_list檢測發來的RREQ是否是新的。Routing_list包含泛洪ID，在網絡中唯一標識RREQ包。中間節點收到的請求包已在Routing_list中，將認為是重複的RREQ包，將丟棄停止廣播。否則將中間將創建新的Routing_list並更新路由表，繼續泛洪RREQ信息包。這是為了防止出現同一節點出現在兩條或多條路徑中；
3、之後節點會判斷本節點是否是目的節點，如果不是的話，將繼續廣播RREQ信息包，如果該節點是目的節點的話，還要進行判斷，如果在規定的時間內接收到RREQ包，將產生路由回復RREP信息包，返回的路徑將按照RREQ包來的路徑單播回去，最後源節點收到RREP響應包，丟棄跳數太多或者時延太長的路徑，留下相對最優的節點不相交多路徑。
圖5為本發明的能量感知節點不相交多路徑路由響應過程：
目的節點收到RREQ信息包，創建RREP信息包，並以單播形式沿著RREQ包路徑返回RREP包。當源節點收到RREP包後，將會啟動定時器，在收到第一個RREP信息包後，T時間內，源節點將收到多個RREP包，將其路徑信息添加到路由表中，如果未在T時間內達到源節點的RREP包，將丟棄。這樣源節點就建立了到達目的節點的多條路徑，多路徑路由的過程完成。
S3：在數據傳輸階段，源節點到目的節點的多條路徑被存儲在路由表中，路徑能量等級分有五種，這些能量等級用來分配鏈路權重，通過篩選出能量較好的路徑進行數據通信，在最小權重路徑發送數據包。
在移動自組織網絡中，源節點能夠找到達到目的節點的多條路徑，這些路徑有些能保證數據包的端到端可靠傳輸，有些由於存在質量太差，有嚴重的丟包現象。所以本發明通過節點的能量作為衡量路徑質量的好壞，來選擇作為數據傳輸的多條路徑。
在圖2中，RREQ包的報文格式中First Hop node Energy和Source node Energy分別代表當前首跳的節點能量和存儲當前源節點能量信息。在圖3中，RREP包的報文格式中Destination node Energy和First Hop node Energy分別代表當前的目的節點的能量和存儲當前的首跳節點能量信息。
圖6為本發明的所述路徑選擇簡單示意圖：
節點S與節點D通信，最初通過泛洪RREQ包發現多路徑。節點S發現有三條路逕到達目的節點(S-A-B-C-E-D)，(S-G-H-I-J-D)和(S-K-L-P-M-D)路徑。在節點P收到L發來的RREQ包後，繼續收到節點O發來的RREQ，由於在Routing_list檢測到節點P發來的RREQ包，所以將捨棄節點O發來的RREQ包，形成節點不相交多路徑。
然而根據路由表中節點的信息，每條鏈路的能量等級為(100+70+60+70+80+90＝470)，(100+80+70+70+80+90＝490)和(100+70+70+50+60+90＝440)。源節點分別分配權重2,1和3分別代表這些路徑的能量等級。基於節點能量也就是路徑上節點平均能量分配路徑權重。
節點S將選擇最小權重路徑(S-G-H-I-J-D)發送數據包。在每次發送數據包之前計算當前路徑的能量等級，再分配路徑權重，節點S每次發送數據包都是選擇的權重最低的路徑，當路徑都失效時，將重新路由發現過程。在節點能量有限的情況下，這樣可以確保多路徑上節點的能量被均勻地利用，防止節點過度消耗，延長網絡的生存周期。圖7為本發明的說明框圖。
最後說明的是，以上優選實施例僅用以說明本發明的技術方案而非限制，儘管通過上述優選實施例已經對本發明進行了詳細的描述，但本領域技術人員應當理解，可以在形式上和細節上對其作出各種各樣的改變，而不偏離本發明權利要求書所限定的範圍。