基于國(guó)網(wǎng)規(guī)范的無線自組網(wǎng)路由算法改進(jìn)

邵立芳,孫濮東,樓珊珊

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

0 引言

我國(guó)最具發(fā)展?jié)摿Φ默F(xiàn)代應(yīng)用技術(shù)之一是無線自動(dòng)抄表系統(tǒng)，智能抄表領(lǐng)域的熱門研究課題則成為通信技術(shù)的設(shè)計(jì)方法。主要涉及三個(gè)核心問題的是無線自動(dòng)抄表通信技術(shù)的研究：低成本是首要問題，無線自動(dòng)抄表系統(tǒng)成本直接影響用戶的接受程度其本身是由于涉及到千家萬戶；其次是低功耗問題，協(xié)議的設(shè)計(jì)和網(wǎng)絡(luò)通信技術(shù)協(xié)議的設(shè)計(jì)都必須要以節(jié)能為前提；最后是自組網(wǎng)問題，保證控制中心命令和表計(jì)用量數(shù)據(jù)及時(shí)準(zhǔn)確的傳輸，自愈能力和可靠性也是無線自動(dòng)抄表網(wǎng)絡(luò)的重要要求。研究對(duì)象是國(guó)網(wǎng)的無線自動(dòng)抄表系統(tǒng)體系結(jié)構(gòu)，針對(duì)第三個(gè)核心問題自組網(wǎng)問題進(jìn)行詳細(xì)的分析研究。

1 國(guó)網(wǎng)規(guī)范的自組網(wǎng)路由設(shè)計(jì)及缺陷

國(guó)網(wǎng)規(guī)范中微功率無線自動(dòng)抄表系統(tǒng)的組成是散布在一定地理區(qū)域的大量靜態(tài)通信節(jié)點(diǎn)，整個(gè)系統(tǒng)釆用從上至下的主從模式，層次性非常明顯。本地通信網(wǎng)絡(luò)中通常包括采集器集中器和表計(jì)三類通信節(jié)點(diǎn)，集中器中的微功率無線模塊指定為中心節(jié)點(diǎn)，采集器和表計(jì)中的微功率無線模塊為子節(jié)點(diǎn)，中心節(jié)點(diǎn)管理所有子節(jié)點(diǎn)，并收集、計(jì)算和處理節(jié)點(diǎn)的一些關(guān)鍵信息。

圖1 國(guó)網(wǎng)規(guī)范中中心節(jié)點(diǎn)直接管理所有子節(jié)點(diǎn)

國(guó)網(wǎng)規(guī)范中路由表的建立是在組網(wǎng)過程的場(chǎng)強(qiáng)收集階段完成，由中心節(jié)點(diǎn)發(fā)出場(chǎng)強(qiáng)收集命令，逐層收取每一層節(jié)點(diǎn)的鄰居節(jié)點(diǎn) 信息，信息收取完成后，中心節(jié)點(diǎn)根據(jù)收集到的節(jié)點(diǎn)信息，結(jié)合自身的路由算法，計(jì)算出符合一定QOS 的單條或多條路徑。

源節(jié)點(diǎn)和目的節(jié)點(diǎn)間存在多條路徑是平面式結(jié)構(gòu)的路由算法最大的優(yōu)點(diǎn)之一，因此可以通過多條路徑減少擁塞，傳輸業(yè)務(wù)流，消除可能的“瓶頸”問題，但是由于微功率無線自組網(wǎng)具有動(dòng)態(tài)的拓?fù)洌ü?jié)點(diǎn)可能會(huì)進(jìn)入或退出網(wǎng)絡(luò)）、有限的帶寬等問題，這種平面式結(jié)構(gòu)在節(jié)點(diǎn)數(shù)目增多時(shí)的路由開銷很大，可擴(kuò)展性較差。

局限是每個(gè)常用的優(yōu)秀路由協(xié)議都具有的，系統(tǒng)開銷的有效降低是由于DSR 充分使用源路由發(fā)現(xiàn)和路由緩存機(jī)制。源路由的開銷是每個(gè)數(shù)據(jù)包都包含的，當(dāng)數(shù)據(jù)包經(jīng)過眾多的中間節(jié)點(diǎn)時(shí)，也會(huì)導(dǎo)致開銷的增加。該算法具有明顯的局限性的原因是CBRP首先提出用分簇算法來提高路由的可擴(kuò)展性，但是基于單路徑路由技術(shù)，頻繁的進(jìn)行路由重啟和路徑修補(bǔ)，開銷是巨大。

1.1 改進(jìn)的簇的選擇與建立方式

采用適當(dāng)?shù)姆执囟嗦窂剿惴?，?gòu)造分層的拓?fù)浣Y(jié)構(gòu)是解決國(guó)網(wǎng)規(guī)范路由問題最有效的方法之一。能夠優(yōu)化網(wǎng)絡(luò)帶寬的應(yīng)用，提高共享信道的利用率；有效地減少交換路由控制信息的開銷，強(qiáng)化節(jié)點(diǎn)的管理；容易實(shí)現(xiàn)局部網(wǎng)絡(luò)同步；支持大規(guī)模的無線網(wǎng)絡(luò)，可擴(kuò)展性好。

基于簇的多路徑動(dòng)態(tài)路由算法的主要思想是在分簇算法中將網(wǎng)絡(luò)分成單元簇和中心簇，這種分層可以實(shí)現(xiàn)路由開銷最小化，同時(shí)提高網(wǎng)絡(luò)的可擴(kuò)展性，有效適應(yīng)節(jié)點(diǎn)數(shù)目多和節(jié)點(diǎn)密度大的網(wǎng)絡(luò)。

該算法主要有三部分組成：簇的選擇和建立、可靠路由的建立、動(dòng)態(tài)路徑維護(hù)。

1.1.1 簇的結(jié)構(gòu)

CMDSR 的簇結(jié)構(gòu)，將網(wǎng)絡(luò)分為三級(jí)層次，第一級(jí)是節(jié)點(diǎn)層，每個(gè)節(jié)點(diǎn)相距簇首一跳，第二級(jí)為單元簇，負(fù)責(zé)管理多個(gè)節(jié)點(diǎn)按一定的算法和規(guī)則集結(jié)生成簇，同時(shí)受中心簇的管理和控制，第三層為中心簇層，中心簇為一組單元簇的集合，管理控制所有單元簇。

圖2 簇的結(jié)構(gòu)圖

1.1.2 簇的初始化及更新

自組網(wǎng)中的每個(gè)節(jié)點(diǎn)進(jìn)行標(biāo)識(shí)及令牌賦值首先是對(duì)簇的初始化。利用規(guī)定的簇首選舉算法選舉簇首，構(gòu)建各自的鄰居集合，相鄰節(jié)點(diǎn)間交互信息，實(shí)現(xiàn)簇的初始化。成為簇首的節(jié)點(diǎn)向所有鄰居節(jié)點(diǎn)廣播，未加入其它簇的節(jié)點(diǎn)獲取通告以后，立即應(yīng)答，宣布加入該簇。一個(gè)節(jié)點(diǎn)只屬于一個(gè)簇。

簇成員保留它能偵聽到的簇首節(jié)點(diǎn)的ID 是所有節(jié)點(diǎn)采用分布式方法交換信息。導(dǎo)致簇及簇成員改變的主要原因是網(wǎng)絡(luò)節(jié)點(diǎn)的加入或退出，網(wǎng)絡(luò)的拓?fù)湟搽S之改變。

1.1.3 中心簇首的選擇

圖3 簇的更新方式示意圖

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

1.2 可靠路由建立

1.2.1 路徑查找

當(dāng)源節(jié)點(diǎn)s 試圖建立到目的節(jié)點(diǎn)d 的連接時(shí)，向它的簇首發(fā)起一次路徑請(qǐng)求消息（RREQ），簇首收到RREQ 消息后，判斷目標(biāo)節(jié)點(diǎn)是否與源節(jié)點(diǎn)在同一簇中，如果相同，則通知節(jié)點(diǎn)啟動(dòng)路由查找程序；不在同一簇中，則向中心簇首報(bào)告路徑請(qǐng)求消息，中心簇首根據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)建立起源到目標(biāo)的路由查找導(dǎo)向隊(duì)列{S，C2，…，Cm-1，D}，并把隊(duì)列信息發(fā)送到源節(jié)點(diǎn)。

源節(jié)點(diǎn)s 向其鄰居節(jié)點(diǎn)發(fā)送RREQ 消息，RREQ 包含最低可靠性需求Plower和已經(jīng)路過的鏈路及相應(yīng)路徑的可靠性Pacc等信息，每個(gè)RREQ 消息都有唯一的請(qǐng)求ID，每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)可以唯一確定一個(gè)RREQ，Pacc域初始設(shè)置為1。

當(dāng)中間節(jié)點(diǎn)更新完RREQ 消息后，將會(huì)把這些信息復(fù)制多個(gè)轉(zhuǎn)發(fā)給它的鄰居節(jié)點(diǎn)。中間節(jié)點(diǎn)拒絕向已經(jīng)出現(xiàn)VR 域中的鄰居節(jié)點(diǎn)發(fā)送消息，確保RREQ 消息不會(huì)在網(wǎng)絡(luò)中循環(huán)。

表1 RREQ 消息

1.2.2 路徑選擇

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

當(dāng)目的節(jié)點(diǎn)完成了路徑選擇后，將會(huì)向每一條非交差路徑發(fā)送一組RREP 消息到源節(jié)點(diǎn)，格式如表2 所示。

表2 RREP 消息

1.3 動(dòng)態(tài)路徑維護(hù)與修補(bǔ)

由于網(wǎng)絡(luò)的動(dòng)態(tài)特性，路徑可能在任意時(shí)刻被中斷，為了保證可靠的的網(wǎng)絡(luò)連接，必須進(jìn)行路由維護(hù)以保證端到端的可靠性。

路由維護(hù)分為以下三種情況：

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

b) 第二種情況是在傳輸路徑中的某一中間節(jié)點(diǎn)NODEi移動(dòng)后，網(wǎng)絡(luò)拓?fù)浒l(fā)生變化，造成路徑可靠性變差或路徑中斷，該節(jié)點(diǎn)的簇首判斷變化路徑的前一節(jié)點(diǎn)NODEi-1和后一節(jié)點(diǎn)NODEi+1是否屬于本簇成員。如果是則將該NODEi的信息直接遷至簇首，并通知前一節(jié)點(diǎn)NODEi-1設(shè)置一個(gè)暫停時(shí)間，根據(jù)路徑查找算法，來形成很多NODEi-1到NODEi+1新鏈路，用這些鏈路代替原來中斷的路徑。如果NODEi-1，NODEi，NODEi+1不屬于同一簇，則向中心簇首報(bào)告變化情況，并將有關(guān)信息遷至中心簇首，由中心簇首來實(shí)現(xiàn)路徑維護(hù)。

c) 第三種是當(dāng)路徑中的某個(gè)簇消失或者幾乎所有路徑都破壞的情況下，要立即初始化一次新的路由發(fā)現(xiàn)但是源節(jié)點(diǎn)不做任何檢查。

2 實(shí)驗(yàn)仿真與性能分析

2.1 實(shí)驗(yàn)設(shè)計(jì)

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

設(shè)置節(jié)點(diǎn)在1500 m X 500 m 內(nèi)的區(qū)域移動(dòng)，為了發(fā)現(xiàn)單路徑和多路徑的區(qū)別矩形區(qū)域一定要擴(kuò)大平均路徑長(zhǎng)度，；節(jié)點(diǎn)采用隨機(jī)分布；暫停時(shí)間設(shè)置為0～900 s 顯示不同的移動(dòng)性對(duì)性能的影響。節(jié)點(diǎn)數(shù)目為50～500 個(gè)，用來觀察節(jié)點(diǎn)數(shù)目的增長(zhǎng)對(duì)性能的影響。。

表3 實(shí)驗(yàn)參數(shù)及其配置

2.2 性能計(jì)算結(jié)果

圖4 說明了CBRP、SMR、CMDSR 不同移動(dòng)速度的報(bào)文成功傳輸率。移動(dòng)速度在0 ～ 30 m/s 的任何值時(shí)，CMDSR 的傳輸成功率比CBRP 和SMR 都高。不管移動(dòng)節(jié)點(diǎn)速度如何改變，CMDSR和SMR 能夠得到相對(duì)穩(wěn)定的傳輸成功率，這是實(shí)驗(yàn)?zāi)M結(jié)果證明的。

圖5，圖6 說明了單路徑路由開銷低于多路由原因是多路徑路由搜索路徑花費(fèi)的代價(jià)要比單路徑路由花費(fèi)的代價(jià)要高。CMDSR 相對(duì)于SMR 代價(jià)要低，特別是節(jié)點(diǎn)數(shù)目增加時(shí)，CMDSR 的開銷要比SMR 小的多，這是因?yàn)槔么氐膶哟喂芾韥磉M(jìn)行路由搜索，比起在整個(gè)網(wǎng)絡(luò)進(jìn)行搜索代價(jià)小的多，特別是網(wǎng)絡(luò)規(guī)模越大，基于簇的路由算法（CMDSR 和CBRP）相對(duì)于平面結(jié)構(gòu)路由算法（SMR）的開銷越小。

3 結(jié)語

只有關(guān)注自組網(wǎng)的差異性才能設(shè)計(jì)出更高效的系統(tǒng)，利用分簇算法的優(yōu)點(diǎn)，將網(wǎng)絡(luò)分成兩層簇結(jié)構(gòu)，路由發(fā)現(xiàn)被遷移到中心簇層進(jìn)行，控制路由發(fā)現(xiàn)階段泛洪開銷大的缺點(diǎn)，實(shí)現(xiàn)路由開銷最小化。為了進(jìn)一步提高網(wǎng)絡(luò)的可擴(kuò)展性必須要有效處理節(jié)點(diǎn)數(shù)量增多和節(jié)點(diǎn)密度增大的問題，；在現(xiàn)有的國(guó)網(wǎng)規(guī)范中，想要提高組網(wǎng)速度，增加網(wǎng)絡(luò)的可擴(kuò)展性，那么基于簇的動(dòng)態(tài)路由算法具有重要的參考使用價(jià)值。

圖4 不同移動(dòng)速率報(bào)文成功傳輸率

圖5 不同的速度下的節(jié)點(diǎn)開銷控制

圖6 不同節(jié)點(diǎn)數(shù)目開銷控制實(shí)驗(yàn)圖

[1] 劉樹剛.微功率無線自動(dòng)抄表系統(tǒng)設(shè)計(jì)新方法及其應(yīng)用研究[D].湖南：湖南大學(xué)，2011.

[2] 王陽，唐龍江.無線自組網(wǎng)通信技術(shù)在配電網(wǎng)監(jiān)測(cè)中的應(yīng)用[D]，安徽：黃山供電局.2008.

[3] 電力用戶用電信息采集系統(tǒng)通信協(xié)議第4 部分：基于微功率無線通信的數(shù)據(jù)傳輸協(xié)議[S]，國(guó)家電網(wǎng)公司 2013：36-118.

[4] 安耀輝，王新安，李輝，蘇金樹，等.移動(dòng)自組網(wǎng)中的先進(jìn)路由算法與路由協(xié)議[M].北京：科學(xué)出版社，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 中基于簇的動(dòng)態(tài)多路徑路由.計(jì)算機(jī)研究與發(fā)展，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 中一種基于簇的動(dòng)態(tài)多路徑路由算法.軟件學(xué)報(bào)，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.