基于國網規范的無線自組網路由算法改進

邵立芳,孫濮東,樓珊珊

（北京南瑞智芯微電子科技有限公司,浙江杭州,310013)

0 引言

我國最具發展潛力的現代應用技術之一是無線自動抄表系統，智能抄表領域的熱門研究課題則成為通信技術的設計方法。主要涉及三個核心問題的是無線自動抄表通信技術的研究：低成本是首要問題，無線自動抄表系統成本直接影響用戶的接受程度其本身是由于涉及到千家萬戶；其次是低功耗問題，協議的設計和網絡通信技術協議的設計都必須要以節能為前提；最后是自組網問題，保證控制中心命令和表計用量數據及時準確的傳輸，自愈能力和可靠性也是無線自動抄表網絡的重要要求。研究對象是國網的無線自動抄表系統體系結構，針對第三個核心問題自組網問題進行詳細的分析研究。

1 國網規范的自組網路由設計及缺陷

國網規范中微功率無線自動抄表系統的組成是散布在一定地理區域的大量靜態通信節點，整個系統釆用從上至下的主從模式，層次性非常明顯。本地通信網絡中通常包括采集器集中器和表計三類通信節點，集中器中的微功率無線模塊指定為中心節點，采集器和表計中的微功率無線模塊為子節點，中心節點管理所有子節點，并收集、計算和處理節點的一些關鍵信息。

圖1 國網規范中中心節點直接管理所有子節點

國網規范中路由表的建立是在組網過程的場強收集階段完成，由中心節點發出場強收集命令，逐層收取每一層節點的鄰居節點 信息，信息收取完成后，中心節點根據收集到的節點信息，結合自身的路由算法，計算出符合一定QOS 的單條或多條路徑。

源節點和目的節點間存在多條路徑是平面式結構的路由算法最大的優點之一，因此可以通過多條路徑減少擁塞，傳輸業務流，消除可能的“瓶頸”問題，但是由于微功率無線自組網具有動態的拓撲（節點可能會進入或退出網絡）、有限的帶寬等問題，這種平面式結構在節點數目增多時的路由開銷很大，可擴展性較差。

局限是每個常用的優秀路由協議都具有的，系統開銷的有效降低是由于DSR 充分使用源路由發現和路由緩存機制。源路由的開銷是每個數據包都包含的，當數據包經過眾多的中間節點時，也會導致開銷的增加。該算法具有明顯的局限性的原因是CBRP首先提出用分簇算法來提高路由的可擴展性，但是基于單路徑路由技術，頻繁的進行路由重啟和路徑修補，開銷是巨大。

1.1 改進的簇的選擇與建立方式

采用適當的分簇多路徑算法，構造分層的拓撲結構是解決國網規范路由問題最有效的方法之一。能夠優化網絡帶寬的應用，提高共享信道的利用率；有效地減少交換路由控制信息的開銷，強化節點的管理；容易實現局部網絡同步；支持大規模的無線網絡，可擴展性好。

基于簇的多路徑動態路由算法的主要思想是在分簇算法中將網絡分成單元簇和中心簇，這種分層可以實現路由開銷最小化，同時提高網絡的可擴展性，有效適應節點數目多和節點密度大的網絡。

該算法主要有三部分組成：簇的選擇和建立、可靠路由的建立、動態路徑維護。

1.1.1 簇的結構

CMDSR 的簇結構，將網絡分為三級層次，第一級是節點層，每個節點相距簇首一跳，第二級為單元簇，負責管理多個節點按一定的算法和規則集結生成簇，同時受中心簇的管理和控制，第三層為中心簇層，中心簇為一組單元簇的集合，管理控制所有單元簇。

圖2 簇的結構圖

1.1.2 簇的初始化及更新

自組網中的每個節點進行標識及令牌賦值首先是對簇的初始化。利用規定的簇首選舉算法選舉簇首，構建各自的鄰居集合，相鄰節點間交互信息，實現簇的初始化。成為簇首的節點向所有鄰居節點廣播，未加入其它簇的節點獲取通告以后，立即應答，宣布加入該簇。一個節點只屬于一個簇。

簇成員保留它能偵聽到的簇首節點的ID 是所有節點采用分布式方法交換信息。導致簇及簇成員改變的主要原因是網絡節點的加入或退出，網絡的拓撲也隨之改變。

1.1.3 中心簇首的選擇

圖3 簇的更新方式示意圖

中心簇首管理所有成員簇，中心簇不遵循成員簇首的選舉方式，直接指定集中器中的微功率無線模塊即中心節點為中心簇首。

1.2 可靠路由建立

1.2.1 路徑查找

當源節點s 試圖建立到目的節點d 的連接時，向它的簇首發起一次路徑請求消息（RREQ），簇首收到RREQ 消息后，判斷目標節點是否與源節點在同一簇中，如果相同，則通知節點啟動路由查找程序；不在同一簇中，則向中心簇首報告路徑請求消息，中心簇首根據網絡拓撲結構建立起源到目標的路由查找導向隊列{S，C2，…，Cm-1，D}，并把隊列信息發送到源節點。

源節點s 向其鄰居節點發送RREQ 消息，RREQ 包含最低可靠性需求Plower和已經路過的鏈路及相應路徑的可靠性Pacc等信息，每個RREQ 消息都有唯一的請求ID，每個網絡節點可以唯一確定一個RREQ，Pacc域初始設置為1。

當中間節點更新完RREQ 消息后，將會把這些信息復制多個轉發給它的鄰居節點。中間節點拒絕向已經出現VR 域中的鄰居節點發送消息，確保RREQ 消息不會在網絡中循環。

表1 RREQ 消息

1.2.2 路徑選擇

算法分為兩步，第一步是路徑分類，按照路徑可靠性遞減的順序分類排列，這些已分類的路徑集稱為候選路徑集。第二步是非交差路徑選擇，從候選路徑集中選擇出一組非交差的路徑，這組路徑都滿足最低可靠性要求。通過以上兩步選擇出來的路徑稱之為真實路徑。

當目的節點完成了路徑選擇后，將會向每一條非交差路徑發送一組RREP 消息到源節點，格式如表2 所示。

表2 RREP 消息

1.3 動態路徑維護與修補

由于網絡的動態特性，路徑可能在任意時刻被中斷，為了保證可靠的的網絡連接，必須進行路由維護以保證端到端的可靠性。

路由維護分為以下三種情況：

a) 第一種是在傳輸過程中，源節點會向該路徑發送RCHK消息檢查路徑情況原因是端到端的可靠性低于Plower的要求時，并設置暫停以等待RCHK-RP，接收到RCHK-RP 后，源節點在目的節點路徑重新計算端到端可靠性。如果可靠性滿足，則源節點使用該路徑繼續進行傳輸數據。

b) 第二種情況是在傳輸路徑中的某一中間節點NODEi移動后，網絡拓撲發生變化，造成路徑可靠性變差或路徑中斷，該節點的簇首判斷變化路徑的前一節點NODEi-1和后一節點NODEi+1是否屬于本簇成員。如果是則將該NODEi的信息直接遷至簇首，并通知前一節點NODEi-1設置一個暫停時間，根據路徑查找算法，來形成很多NODEi-1到NODEi+1新鏈路，用這些鏈路代替原來中斷的路徑。如果NODEi-1，NODEi，NODEi+1不屬于同一簇，則向中心簇首報告變化情況，并將有關信息遷至中心簇首，由中心簇首來實現路徑維護。

c) 第三種是當路徑中的某個簇消失或者幾乎所有路徑都破壞的情況下，要立即初始化一次新的路由發現但是源節點不做任何檢查。

2 實驗仿真與性能分析

2.1 實驗設計

為集中比較不同的路由算法，假定物理層、鏈路層及其它層的參數都是固定不變的。

設置節點在1500 m X 500 m 內的區域移動，為了發現單路徑和多路徑的區別矩形區域一定要擴大平均路徑長度，；節點采用隨機分布；暫停時間設置為0～900 s 顯示不同的移動性對性能的影響。節點數目為50～500 個，用來觀察節點數目的增長對性能的影響。。

表3 實驗參數及其配置

2.2 性能計算結果

圖4 說明了CBRP、SMR、CMDSR 不同移動速度的報文成功傳輸率。移動速度在0 ～ 30 m/s 的任何值時，CMDSR 的傳輸成功率比CBRP 和SMR 都高。不管移動節點速度如何改變，CMDSR和SMR 能夠得到相對穩定的傳輸成功率，這是實驗模擬結果證明的。

圖5，圖6 說明了單路徑路由開銷低于多路由原因是多路徑路由搜索路徑花費的代價要比單路徑路由花費的代價要高。CMDSR 相對于SMR 代價要低，特別是節點數目增加時，CMDSR 的開銷要比SMR 小的多，這是因為利用簇的層次管理來進行路由搜索，比起在整個網絡進行搜索代價小的多，特別是網絡規模越大，基于簇的路由算法（CMDSR 和CBRP）相對于平面結構路由算法（SMR）的開銷越小。

3 結語

只有關注自組網的差異性才能設計出更高效的系統，利用分簇算法的優點，將網絡分成兩層簇結構，路由發現被遷移到中心簇層進行，控制路由發現階段泛洪開銷大的缺點，實現路由開銷最小化。為了進一步提高網絡的可擴展性必須要有效處理節點數量增多和節點密度增大的問題，；在現有的國網規范中，想要提高組網速度，增加網絡的可擴展性，那么基于簇的動態路由算法具有重要的參考使用價值。

圖4 不同移動速率報文成功傳輸率

圖5 不同的速度下的節點開銷控制

圖6 不同節點數目開銷控制實驗圖

[1] 劉樹剛.微功率無線自動抄表系統設計新方法及其應用研究[D].湖南：湖南大學，2011.

[2] 王陽，唐龍江.無線自組網通信技術在配電網監測中的應用[D]，安徽：黃山供電局.2008.

[3] 電力用戶用電信息采集系統通信協議第4 部分：基于微功率無線通信的數據傳輸協議[S]，國家電網公司 2013：36-118.

[4] 安耀輝，王新安，李輝，蘇金樹，等.移動自組網中的先進路由算法與路由協議[M].北京：科學出版社，2009：50-138.

[5] Johnson D，Maltz D.Dynamic source routing in Ad Hoc wireless networks.//Imielnski E,Korth H.Mobile Computing.Amsterdam：Kluwer Academic Publishers，1996.

[6] 安耀輝，盧錫城，彭偉等，MANET 中基于簇的動態多路徑路由.計算機研究與發展，2006，3(43).

[7] Ephremids A，WieselthierJ，Baker D J.A design concpt for reliable mobile radio networks with frequency hopping signaling.//Proceedings of the IEEE，1987，75(1).

[8] Gerla M ,Tsai T C.Multucluster,mobile multimedia radio networks.ACM-Baltzer Journal of Wireless Networks ,1995,1(3):255-265.

[9] Alwan A，Bagrodia R，Bambos N et al.Adaptive mobile multimedia networks.IEEE Personal Communication Magazine，1996，34-51.

[10] McDonald A B，ZNati T F,A mobility based frameworks for adaptive clustering in wireless Ad Hoc networks.IEEE Journal on Selected Areas in Communications，1999，17（8）：1466-1487.

[11] Lin C R，Gerla M.Adaptive clustering for mobile wireless networks.IEEE Journal on Selected Areas in Communications，1997，15（7）：1265-1275.

[12] Bhatnagar A，Robertazzi G.Layer net：a new selforganizing network protocols.//Proceedings of the IEEE MILCOM，1990：845-849.

[13] Chen W L，Jain N，Singh S，ANMP：Ad Hoc network management protocol.IEEE Journal on Selected Areas in Communications，1999，17（8）：1506-1531.

[14] 安耀輝，盧錫城，彭偉等，MANET 中一種基于簇的動態多路徑路由算法.軟件學報，2007，18(4)：987-995.

[15] Nasipuri A,Das S R.On-demand multi-path routing for mobile Ad Hoc networks,IEEE ICCCN,Boston,1999:64-70.