[發明專利]一種智能抄表系統無線網絡路由算法

在審

• 申請號: 201410258788.6
• 申請日: 2014-06-11
• 公開（公告）號: CN104065572A
• 公開（公告）日: 2014-09-24
• 發明（設計）人: 王宏;李世興;楊祖業;李勇;王進超
• 申請（專利權）人: 沈陽中科博微自動化技術有限公司
• 主分類號: H04L12/707
• 分類號: H04L12/707
• 代理公司: 沈陽優普達知識產權代理事務所(特殊普通合伙) 21234
• 代理人: 俞魯江

技術領域

本發明涉及無線傳輸技術、網絡技術、路由技術，具體地說是一種智能抄表系統無線網絡路由算法。

背景技術

隨著控制、計算機、通信、網絡等技術的發展，信息交換溝通的領域正在迅速覆蓋從現場設備到各個控制領域，而興起于本世紀初的工業無線技術引發了傳統工業測控模式的重大變革，工業無線網絡是從新興的無線傳感器網絡發展而來的、具有低成本、低能耗、高度靈活性等特點。工業無線網絡是一種面向設備間信息交互的無線通信技術，是對現有無線通信技術在工業應用方向上的功能擴展和提升，是降低工業測控系統成本、擴展應用范疇的革命性技術。工業無線網絡技術改變了現有系統控制信息傳遞的方式。路由作為數據的傳輸和分發機制，是無線網絡的一大核心任務，是不可或缺的。無線網絡路由是一個非常活躍的研究領域，在這方面國內外學者提出了很多的解決方案。

目前，AODV(反應式路由協議)、OLSR(先應式路由協議)等主流的路由算法，大部分是采用的分布式協議，路由的計算選擇過程由數據的發送或者轉發者來承擔，采用網絡各個成員來選擇路由和維護路由的策略。在一個無線智能抄表網絡中，網絡管理者負責節點路由和通信資源的分配管理，通過命令將路由信息發送到網絡設備，是一種集中式路由配置方案，而不需要網絡其他節點進行路由計算。此外，當前主要路由算法集中在單路徑路由的研究，當路由路徑上某個節點故障時，通信就要受到影響，也不符合無線抄表網絡的要求。在實際應用中，網絡節點之間無線通信往往受到周圍環境電磁干擾、信號衰減、信號反射等不利因素影響，對無線傳輸的性能帶來很大挑戰。

Dijkstra算法是由荷蘭計算機科學家Edsger Wybe Dijkstra提出的，在論領域有著廣泛的應用，是經典的最短路徑算法。Dijkstra算法的輸入為一個非負權重的有向圖G。在給定出某個發頂點的情況下，該算法能夠找出出發頂點到圖中其余頂點的最短距離。然而Dijkstra算法得出的結果是最短的距 離和路徑，只有單一路徑，不符合WirelessHART中圖路由機制的要求，因此提出了基于Dijkstra算法搜索的冗余路徑搜索算法R-Dijkstra算法。

因此，采用冗余路由，引入多路徑路由機制，增強了數據傳輸的路徑冗余，以確保數據可靠無誤的傳輸，具有重大的意義。

發明內容

為了使無線抄表網絡路由更可靠，本發明的目的是提供一種冗余的智能抄表系統無線網絡路由算法。

為實現本發明的目的所采用的技術方案是：

一種智能抄表系統無線網絡路由算法，采用吸收了Dijkstra算法思想的R-Dijkstra算法；

所述R-Dijkstra算法以Dijkstra算法為核心搜索算法，通過引入冗余度參數r，實現了路由路徑的冗余；

根據冗余度參數r，對待加入節點匯報的鄰居進行選擇，然后對將每個選出的鄰居作為出發頂點，分別采用Dijkstra算法進行對目的節點搜索，得出每條路徑后，最后將待加入節點分別添加到每條路徑的起點上，這樣就得出了冗余度r的路由路徑，這些路徑都是待加入節點到目的節點冗余的目標代價最小的路由。

冗余度參數r，表示每個節點在路由轉發數據時候可選擇的鄰居個數為r個；

網絡可以用一個有向圖模型G＝(V,E)來表達，其中V表示網絡中節點的集合，E為有向邊集合；網絡中每兩個節點之間的鏈接可以賦予權值w(i,j)，表示由節點i到節點j的鏈接權值；w(i,j)具體值的計算可以根據鏈路質量、帶寬多個指標計算獲得；將兩節點之間是否直接鏈接作為w(i,j)取值依據，有鏈接的鄰居之間的權值都為1，否則為無窮大；根據節點加入時匯報鄰居信息，然后采用R-Dijkstra算法，得出待加入節點的路由信息。

所述路徑都是待加入節點到目的節點冗余的目標代價最小的路由，目標代價可以考慮傳輸跳數、信號質量、節點能量以及負載等因素的共同作用；從路由實時性考慮，在本算法中采用跳數作為目標代價。

算法的復雜度結論如下；

Dijkstra算法的復雜度主要在兩個循環中，因此Dijkstra算法的復雜度為O(n²)；R-Dijkstra算法在Dijkstra算法基礎上引入了冗余度參數r，以 Dijkstra算法為基礎，進行了r次循環；因此，R-Dijkstra算法的復雜度為O(r×n²)；

由于通常情況下r≥2，但n相對較大，則有r＜＜n，冗余度參數對算法復雜度的影響不是很嚴重。