[發明專利]一種物聯網表面自適應定向路由算法

無效

• 申請號: 201310605276.8
• 申請日: 2013-11-26
• 公開（公告）號: CN103701698A
• 公開（公告）日: 2014-04-02
• 發明（設計）人: 王江濤
• 申請（專利權）人: 中國十七冶集團有限公司
• 主分類號: H04L12/721
• 分類號: H04L12/721
• 代理公司: 馬鞍山市金橋專利代理有限公司 34111
• 代理人: 魯延生

技術領域

本發明是一種用于信息網絡，特別是適用于物聯網發現路徑的基于位置的路由新算法，屬于物聯網路由應用技術領域。

背景技術

近年來，無線通信和定位技術有著突飛猛進的發展，GPS和Galileo等全球定位系統的成本越來越低，在物聯網中的應用也越來越廣泛。利用這些定位系統提供的定位服務，物聯網中的節點均能獲悉自身位置。根據這些位置信息，基于位置的物聯網路由算法僅依據當前節點所緩存的鄰居節點位置以及消息報文中的控制信息便做出轉發決策，無須建立和維護全局的路由狀態表，大大縮減了節點的存儲、通信和計算開銷，已成為物聯網研究的熱點。

另一方面，目前物聯網正朝著大規模方向發展，網絡中的節點個數可能增加到幾百甚至上千。為了處理這么大規模的網絡，目前提出的諸多適用于小規模網絡的路由協議，包括基于表驅動方式的、基于按需方式的、采用平面結構的、采用分層結構的等等，都不能很好地適應大規模的網絡環境。

最早能確保到達目標的位置物聯網路由算法是第二代指南針路由算法，但它的時間復雜度為O（n）（n是網絡節點數目），這可通過泛洪獲得同樣的復雜度且操作更為簡單。隨后出現AFR是一種純表面路由選擇，但它缺少貪婪轉發，在現代的大型密集網絡中缺乏實用價值。B.?Karp和H.?Kung提出了一種結合了貪婪和表面路由轉發的GPSR算法，其花費很小且在平均情況下有著很好的性能，但它由于過早地切換回貪婪路由算法，失去了在最壞情況下的最優性。F.?Kunth等在AFR的基礎上引入GOAFR保證了路由的最壞情況的最優性，不足的地方是每輪轉發失敗后都要重新調用算法回到源點并且下一輪開始時又要全部重新搜索，多次的重復計算增加了物聯網節點通信和計算的開銷。

發明內容

本發明的目的就是針對物聯網中基于位置的路由算法中存在的重復搜索和冗余計算問題，提出了一種適用于發現路徑的基于位置的物聯網表面自適應定向路由算法DAFR?（Directed?Adaptive?Face-Based?Routing），該算法充分發揮表面路由轉發和定向選路的優勢，依據局部區域節點的狀態信息進行整個網絡的路由選擇。DAFR是局部狀態路由算法，它在節點的存儲容量和計算通信量之間獲取折中，通過在每個節點緩存中加入一些字段避免了重復搜索，只需局部節點的狀態信息便可進行全局的路由，因此其開銷相比于傳統路由大為降低，同時保證了算法在最壞情況下的最優性。

本發明的技術方案是這樣實現的：一種物聯網表面自適應定向路由算法，其特點是：發揮表面路由轉發和定向選路的優勢，依據局部區域節點的狀態信息進行整個網絡的路由選擇；

a)????????????????????????????算法通過在節點緩存中加入上一跳節點標識（L），下一跳節點標識（N）和算法重搜索（R）字段使得節點“記憶”了有效搜索的狀態；

b)????????????????????????????算法發揮表面路由轉發和定向選路的優勢，依據局部區域節點的狀態信息進行整個網絡的路由選擇，算法具備漸近最優性；

c)????????????????????????????算法通過在每個節點緩存中加入一些字段避免了重復搜索，只需局部節點的狀態信息便可進行全局的路由；

d)????????????????????????????當在一輪遍歷失敗后，它避免了重復的反向查找，直接定向回到源點，且在下一輪遍歷時繼續利用這些有效字段來簡化搜索，大大降低了路由通信量和計算量，獲得平均情況下的高性能；

e)????????????????????????????算法在最壞情況下的路由代價僅需O（c2（p*）），滿足了最壞情況下的最優性條件。

本發明設定物聯網節點具有相同的傳輸半徑，并支持多跳路由；節點通過已有的定位服務獲得自身位置；節點通過交換hello報文獲悉其所有鄰居節點的標識和位置；消息源節點知道目標節點的位置；消息報文所包含的控制字段在O（1）階數內，除本身和鄰居節點相關信息以及臨時存儲報文消息外，節點不存儲任何其他信息。本發明的算法完全本地化，節點無須維護全局的拓撲信息和鏈路狀態，大大降低了對節點存儲量和計算能力的要求，同時也增強了對網絡拓撲變化的適應能力。

附圖說明

圖1是HELLO報文格式。

圖2是節點存儲內容。

圖3是DAFR消息報文格式。

圖4是DAFR算法頂層結構圖。

圖5是DAFR算法結構圖。

圖6是模塊b結構圖。