金 勇，徐仁發(fā)，舒 紅

(1.重慶郵電大學(xué) 移動通信技術(shù)重點實驗室，重慶 400065；2.重慶郵電大學(xué) 通信工程應(yīng)用研究所，重慶 400065)

?

基于灰色關(guān)聯(lián)的ZigBee網(wǎng)絡(luò)混合路由算法

金 勇1，2，徐仁發(fā)1，舒 紅1

(1.重慶郵電大學(xué) 移動通信技術(shù)重點實驗室，重慶 400065；2.重慶郵電大學(xué) 通信工程應(yīng)用研究所，重慶 400065)

ZigBee網(wǎng)絡(luò)混合路由算法(ZigBee Routing，ZBR)中將源節(jié)點和目的節(jié)點之間的最小跳數(shù)作為唯一的路由度量因素。但隨著節(jié)點能量消耗以及節(jié)點的頻繁移動，ZBR算法的這一特性會造成網(wǎng)絡(luò)間歇性連接，從而導(dǎo)致網(wǎng)絡(luò)性能下降。提出一種選擇最優(yōu)分組轉(zhuǎn)發(fā)路徑的ZigBee網(wǎng)絡(luò)混合路由算法(Grey Relational Algorithm based ZBR，GRA-ZBR)。GRA-ZBR算法在目的節(jié)點選擇路徑時引入灰色關(guān)聯(lián)算法，綜合考慮節(jié)點剩余能量、鏈路質(zhì)量、節(jié)點剩余隊列長度以及路徑長度等因素。仿真結(jié)果表明，GRA-ZBR算法可以有效提高網(wǎng)絡(luò)分組投遞率，降低平均端到端時延。

ZigBee網(wǎng)絡(luò)；路由算法；灰色關(guān)聯(lián)；路徑選擇

ZigBee網(wǎng)絡(luò)是一種采用ZigBee技術(shù)的無線傳感網(wǎng)絡(luò)，隨著“物聯(lián)網(wǎng)+”理論的提出，ZigBee網(wǎng)絡(luò)受到越來越多的關(guān)注[1]。ZigBee網(wǎng)絡(luò)由于具有低成本、低功耗、低復(fù)雜度、高容量等特點而被廣泛應(yīng)用于智能家居、工業(yè)監(jiān)測、智能交通等領(lǐng)域[2]。

不可避免地，ZigBee網(wǎng)絡(luò)也會受到某些因素限制，如節(jié)點能量、同頻段其他無線通信技術(shù)干擾、網(wǎng)絡(luò)擁塞等，如何提供較為可靠的數(shù)據(jù)分組傳輸成為了ZigBee網(wǎng)絡(luò)近期亟待解決的問題[3]。許多學(xué)者針對這一問題做出了廣泛研究。文獻[4]從節(jié)點能量優(yōu)化角度出發(fā)，在分簇機制基礎(chǔ)上，提出一種ZigBee網(wǎng)絡(luò)能量優(yōu)化算法(Cluster Label based ZBR，CLZBR)，通過簇內(nèi)節(jié)點路由信息共享的方式有效減少節(jié)點能量消耗，從而效提高了網(wǎng)絡(luò)分組投遞率。文獻[5]提出一種能量有效跨層網(wǎng)絡(luò)操作模型，該模型根據(jù)節(jié)點間相對位置關(guān)系調(diào)整節(jié)點的發(fā)送功率，從而控制節(jié)點能量消耗水平，避免網(wǎng)絡(luò)因為節(jié)點能量消耗過快導(dǎo)致網(wǎng)絡(luò)可靠性低的問題。文獻[6]提出一種鏈路狀態(tài)感知的ZigBee路由算法(Link State Aware-AOMDV Junior，S-AOMDVjr)。該算法選擇鏈路狀態(tài)最好的路徑進行數(shù)據(jù)轉(zhuǎn)發(fā)，可保證算法在惡劣環(huán)境下的可靠性。文獻[7]證明了網(wǎng)絡(luò)中鏈路質(zhì)量好壞與節(jié)點間距離大小呈正相關(guān)性，可通過節(jié)點間距離大小粗略估計鏈路質(zhì)量。文獻[8]從網(wǎng)絡(luò)擁塞程度出發(fā)，根據(jù)鏈路的連通率和擁塞程度選擇最合適的路徑轉(zhuǎn)發(fā)數(shù)據(jù)分組，可以有效減少網(wǎng)絡(luò)時延。

大量研究表明：數(shù)據(jù)分組轉(zhuǎn)發(fā)路徑的優(yōu)劣在很大程度上決定了路由算法的好壞[3]。所以，本文主要從選擇最優(yōu)路徑方向做出研究。

1 ZBR路由算法

ZBR路由算法根據(jù)節(jié)點是否具有路由能力而將節(jié)點劃分為RN+和RN-兩種[9]。該算法的基本思路如下：路由過程中，RN+節(jié)點可以使用AODVjr路由算法發(fā)起路由發(fā)現(xiàn)過程，RN-節(jié)點只能使用Cluster-Tree路由算法[10]。ZBR路由算法的工作流程如圖1所示。

圖1 ZBR路由算法流程圖

一方面，AODVjr算法可以通過全網(wǎng)廣播路由請求消息(RouteREQuest，RREQ)來尋找源節(jié)點和目的節(jié)點之間的最短路徑；但另一方面，轉(zhuǎn)發(fā)大量冗余RREQ消息會導(dǎo)致網(wǎng)絡(luò)能量消耗過快、分組投遞率下降等問題。而Cluster-Tree算法盡管復(fù)雜度較低，極易實現(xiàn)，存儲空間需求小，路由開銷和能量消耗均被控制在一定程度內(nèi)。但隨著網(wǎng)絡(luò)節(jié)點數(shù)量和節(jié)點密度的增加，Cluster-Tree算法中節(jié)點能量消耗極度不均衡，協(xié)調(diào)器附近節(jié)點能量消耗程度遠遠大于其他節(jié)點。另外，由于Cluster-Tree算法中采用的路徑并非源節(jié)點和目的節(jié)點之間的最短路徑，所以數(shù)據(jù)分組的傳輸時延較大。相較AODVjr算法和Cluster-Tree算法而言，ZBR路由算法在一定程度上緩解了AODVjr算法和Cluster-Tree算法存在的問題，所以，本文在ZBR算法基礎(chǔ)上做出改進。

2 GRA-ZBR路由算法

2.1 灰色關(guān)聯(lián)理論

灰色系統(tǒng)是由鄧聚龍教授在20世紀(jì)80年代提出的科學(xué)理論[11]，其中，灰色關(guān)聯(lián)分析算法根據(jù)各影響因子在發(fā)展過程中出現(xiàn)的相似或差異情況來描述它們之間的關(guān)聯(lián)程度。本文采用灰色關(guān)聯(lián)分析算法來分析目的節(jié)點接收到的各RREQ消息中攜帶的影響因子。目的節(jié)點選擇灰色關(guān)聯(lián)度最大的RREQ消息回復(fù)RREP消息，并將該RREQ消息轉(zhuǎn)發(fā)路徑作為數(shù)據(jù)分組轉(zhuǎn)發(fā)路徑。灰色關(guān)聯(lián)分析算法主要步驟如下：

1)選擇影響因子

ZBR路由算法將路徑長度作為路徑選擇的唯一度量因素，這將導(dǎo)致網(wǎng)絡(luò)性能隨著時間推移而快速下降。本文在考慮路徑長度因素的基礎(chǔ)上，進一步將節(jié)點剩余能量、鏈路質(zhì)量、節(jié)點剩余隊列長度等作為影響評估因子。其中，鏈路質(zhì)量反映出節(jié)點間距離大小，節(jié)點剩余隊列長度反映出鏈路的擁塞程度。

2)RREQ消息處理

路由發(fā)現(xiàn)過程中，目的節(jié)點會接收到來自多個中間節(jié)點轉(zhuǎn)發(fā)的RREQ分組。假設(shè)目的節(jié)點d接收到m條RREQ分組，則由這些RREQ分組組成的序列如

X=[x1,x2,x3,...,xm]

(1)

3)影響因子序列

RREQ分組由代表不同含義的字段組成，將代表特定影響因子的n個字段讀取出來。由此生成影響因子序列，如

X=[xi(1),xi(2),xi(3),…,xi(n)],i=1,2,…,m

(2)

此外，X還可以寫成矩陣形式，如

(3)

4)無量綱化處理

根據(jù)各影響因子對路徑好壞的正相關(guān)性和負相關(guān)性，將影響因子分成效益型因子(剩余能量、鏈路質(zhì)量、剩余隊列長度)和成本型因子(路徑長度)。效益型因子和成本型因子的處理方式[12]為

k=1,2,3,…,n

(4)

k=1,2,3,…,n

(5)

5)參考序列

為了更準(zhǔn)確地反映出各RREQ消息的優(yōu)劣程度，本文根據(jù)實時網(wǎng)絡(luò)狀況設(shè)定最優(yōu)、最差兩個參考序列，分別如

2,…,m

(6)

2,…,m

(7)

6)灰色關(guān)聯(lián)系數(shù)

影響評估因子的最優(yōu)、最差灰色關(guān)聯(lián)系數(shù)[12]的計算式如

(8)

(9)

式中：ξ為分辨系數(shù)，且有ξ=0.5。

7)灰色關(guān)聯(lián)度

各條RREQ消息的最優(yōu)、最差灰色關(guān)聯(lián)度的計算式為

(10)

(11)

8)RREQ消息灰色關(guān)聯(lián)度

各條RREQ消息的灰色關(guān)聯(lián)度[12]的計算式為

(12)

GRA-ZBR算法實際上是將各條RREQ消息中的影響評估因子字段分別與最優(yōu)、最差參考序列相比較，最終計算最優(yōu)灰色關(guān)聯(lián)度占灰色關(guān)聯(lián)度總和的比重。所占比重越大，表明該條RREQ消息中影響評估因子與最優(yōu)參考序列關(guān)聯(lián)越大，該條RREQ消息的轉(zhuǎn)發(fā)路徑質(zhì)量越好。

2.2 GRA-ZBR路由算法實現(xiàn)過程

與經(jīng)典ZBR算法相比，GRA-ZBR算法主要對路由發(fā)現(xiàn)過程做出改進，如圖2所示。

圖2 GRA-ZBR算法流程圖

GRA-ZBR路由算法主要步驟如下：

步驟1，有數(shù)據(jù)傳輸需求的節(jié)點首先查詢自身路由表，若具有目的節(jié)點相關(guān)表項，則根據(jù)該目的路由表進行數(shù)據(jù)分組轉(zhuǎn)發(fā)；否則，判斷自身節(jié)點類型。

步驟2，若源節(jié)點為RN-節(jié)點，則使用Cluster-Tree路由算法轉(zhuǎn)發(fā)數(shù)據(jù)分組；若源節(jié)點為RN+節(jié)點，則進入路由發(fā)現(xiàn)過程。

步驟3，將源節(jié)點的剩余能量、剩余隊列長度、鏈路質(zhì)量、路徑跳數(shù)等信息添加到RREQ消息對應(yīng)字段。

步驟4，中間節(jié)點接收到RREQ消息后，判斷自身是否為目的節(jié)點：若當(dāng)前節(jié)點為中間節(jié)點，則更新RREQ消息中對應(yīng)字段，將新的RREQ消息向周圍節(jié)點轉(zhuǎn)發(fā)出去。根據(jù)木桶原理可知，通信鏈路性能取決于最差的因素，所以，剩余能量、剩余隊列長度以及鏈路質(zhì)量字段更新方式如下：將當(dāng)前節(jié)點對應(yīng)影響因子數(shù)值與RREQ消息中對應(yīng)字段數(shù)值作比較，它們中的較小值成為新的RREQ消息中對應(yīng)的字段數(shù)值。另外，每經(jīng)過一個中間節(jié)點，路徑跳數(shù)字段的數(shù)值加1。

步驟5，目的節(jié)點接收到RREQ消息后不會直接回復(fù)RREQ消息，而是啟動定時器。通過灰色關(guān)聯(lián)分析算法計算在定時器時間段內(nèi)接收到的各條RREQ消息的灰色關(guān)聯(lián)度，其中，不同的影響因素對路徑好壞影響程度不同。由于節(jié)點剩余能量因素不僅反映了路徑的穩(wěn)定性，還與路徑長度因素一起影響著網(wǎng)絡(luò)整體生存時間。因此，為節(jié)點能量分配的權(quán)值最重，ρk為0.4。針對節(jié)點頻繁移動的場景，若在路徑選擇時考慮LQI因素，則可以有效延長路由有效時間。所以，LQI因素的權(quán)重設(shè)置為0.3。其余兩個影響因素的權(quán)值均設(shè)為0.15。為了簡化算法復(fù)雜度，在網(wǎng)絡(luò)運行期間，上述影響因子權(quán)重固定不變。

步驟6，目的節(jié)點選擇灰色關(guān)聯(lián)度最大的RREQ消息回復(fù)RREP消息。

步驟7，源節(jié)點接收到RREP消息后，建立源節(jié)點和目的節(jié)點之間數(shù)據(jù)分組轉(zhuǎn)發(fā)路徑。

3 仿真分析

為了驗證GRA-ZBR算法的性能，本文采用NS2.35+Cygwin軟件平臺，在IEEE 802.15.4PHY層和MAC基礎(chǔ)上來實現(xiàn)網(wǎng)絡(luò)層的仿真。本文將GRA-ZBR算法與ZigBee網(wǎng)絡(luò)經(jīng)典路由算法AODVjr和ZBR在不同節(jié)點數(shù)量、不同移動速率等場景下進行仿真實驗，性能指標(biāo)包括分組投遞率和平均端到端時延。所有仿真結(jié)果都是網(wǎng)絡(luò)獨立運行50次后取得的算術(shù)平均值。實驗過程中所有節(jié)點隨機分布，數(shù)據(jù)分組最大聯(lián)機數(shù)為10個，平均發(fā)包率為1 packet/s，其余參數(shù)設(shè)置如表1所示。

表1 仿真參數(shù)設(shè)置

3.1 分組投遞率

圖3為最大移動速率設(shè)置為6 m/s時，3種算法在不同節(jié)點數(shù)量場景下的分組投遞率比較，可以發(fā)現(xiàn)，隨著網(wǎng)絡(luò)規(guī)模逐漸加大，網(wǎng)絡(luò)中的冗余RREQ消息增多，網(wǎng)絡(luò)擁堵現(xiàn)象越來越頻繁，所以3種算法的分組投遞率都有所降低。但由于GRA-ZBR算法在選擇路徑時考慮到節(jié)點剩余隊列長度這一因素，有效避免選擇堵塞節(jié)點作為數(shù)據(jù)分組轉(zhuǎn)發(fā)的中間節(jié)點，在一定程度上緩解了網(wǎng)絡(luò)擁堵問題，所以性能優(yōu)于AODVjr算法和ZBR算法。

圖3 不同節(jié)點數(shù)量下的分組投遞率

圖4為節(jié)點數(shù)量固定在80時，3種算法在不同節(jié)點最大移動速率場景下的分組投遞率比較情況。隨著節(jié)點移動速率加快，通信鏈路質(zhì)量變差，網(wǎng)絡(luò)逐漸出現(xiàn)間歇性連接，3種算法的分組投遞率曲線均呈下降趨勢。對于只考慮路徑跳數(shù)的AODVjr算法和ZBR算法而言，分組投遞率下降速率隨著節(jié)點移動速率而增加。但由于GRA-ZBR算法在路徑選擇時添加了路徑質(zhì)量這一度量因素，轉(zhuǎn)發(fā)數(shù)據(jù)分組使用的鏈路不易斷裂，所以，分組投遞率下降趨勢較為平緩。

圖4 不同最大移動速率下的分組投遞率

3.2 平均端到端時延

圖5為最大移動速率設(shè)置為6 m/s時，3種算法在不同節(jié)點數(shù)量場景下的平均端到端時延比較，可見，隨著網(wǎng)絡(luò)節(jié)點數(shù)量的增加，網(wǎng)絡(luò)擁塞情況日益嚴(yán)重，數(shù)據(jù)分組在排隊等待階段花費的時間越多，3種算法的平均端到端時延均呈上升趨勢。盡管AODVjr算法可以選擇源節(jié)點與目的節(jié)點之間的最短路徑轉(zhuǎn)發(fā)數(shù)據(jù)分組，但AODVjr算法在網(wǎng)絡(luò)擁塞情況較為嚴(yán)重。而GRA-ZBR算法在考慮路徑長度基礎(chǔ)上，避免選擇擁塞情況較為嚴(yán)重的節(jié)點作為中間節(jié)點，所以性能優(yōu)于其他算法。

圖5 不同節(jié)點數(shù)量下的端到端時延

圖6為節(jié)點數(shù)量固定在80時，3種算法在不同節(jié)點最大移動速率場景下的平均端到端時延比較結(jié)果，隨著網(wǎng)絡(luò)中節(jié)點移動性增強，轉(zhuǎn)發(fā)路徑上的通信鏈路逐漸開始斷裂，越來越多的數(shù)據(jù)分組需要重新尋找轉(zhuǎn)發(fā)路徑，所以3種算法的平均端到端時延越來越大。但是由于GRA-ZBR算法在路徑選擇時選擇鏈路質(zhì)量作為路由度量因素，有效降低了中間鏈路發(fā)生斷裂的可能性，所以GRA-ZBR算法的性能優(yōu)于AODVjr算法和ZBR算法。

圖6 不同最大移動速率下的端到端時延

4 小結(jié)

節(jié)點移動特性逐漸成為ZigBee網(wǎng)絡(luò)路由算法設(shè)計的一大挑戰(zhàn)，而經(jīng)典ZigBee網(wǎng)絡(luò)ZBR路由算法僅以路徑長度作為路徑選擇依據(jù)，未考慮實時網(wǎng)絡(luò)鏈路狀態(tài)，從而導(dǎo)致網(wǎng)絡(luò)性能下降。本文針對這一問題，提出一種基于灰色關(guān)聯(lián)的ZigBee網(wǎng)絡(luò)混合路由算法GRA-ZBR，該算法根據(jù)鏈路實時能量水平、擁塞程度、鏈路質(zhì)量以及路徑長度作為路由度量依據(jù)，選擇最佳路徑進行數(shù)據(jù)傳輸。仿真結(jié)果證明，GRA-ZBR算法在較大網(wǎng)絡(luò)規(guī)模和移動速率的復(fù)雜場景下，仍然能將分組投遞率和端到端時延等性能指標(biāo)控制在可接受范圍內(nèi)，驗證了GRA-ZBR算法的有效性。但由于GRA-ZBR算法在RREQ消息中增加了3個字段，所以，系統(tǒng)控制開銷會稍高于原ZBR算法。

[1]任智，李鵬翔.基于分段的ZigBee網(wǎng)絡(luò)按需可擴展地址分配算法[J].通信學(xué)報，2012，33(5)：131-137.

[2]白樂強，王玉濤，孫晶晶.基于鄰居表的能量均衡ZigBee樹路由改進算法[J].計算機工程與設(shè)計，2015，36(12)：3204-3208.

[3]韓挺.基于信任理論的路由協(xié)議安全技術(shù)研究[D].北京：北京郵電大學(xué)，2015.

[4]錢志鴻，朱爽，王雪.基于分簇機制的ZigBee混合路由能量優(yōu)化算法[J].計算機學(xué)報，2013，36(3)：485-493.

[5]AL-JEMELI M，HUSSIN F A. An energy efficient cross-layer network operation model for IEEE 802.15.4-based mobile wireless sensor networks[J].IEEE sensors journal，2014，15(2)：

[6]謝忠明，何華冰，李云飛.一種基于鏈路狀態(tài)感知的Zigbee多徑路由算法[J].微電子學(xué)與計算機，2015，32(9)：65-75.

[7]GOMEZ C，BOIX A，PARADELLS J. Impact of LQI-based routing metrics on the performance of a one-to-one routing protocol for IEEE 802.15.4 multihop networks[J].Eurasip journal on wireless communications & networking，2010，4(2)：50-50.

[8]SECCI L，BURATTI C. Reducing traffic congestion in ZigBee networks：experimental results[C]//2013 9th International Wireless Communications and Mobile Computing Conference (IWCMC).Sardinia：IEEE，2013：627-632.

[9]ICHIHARA T，MITANI T，SHINOHARA N. Study and development of an intermittent microwave power transmission system for a ZigBee device[C]//2014 IEEE Wireless Power Transfer Conference (WPTC). Jeju：IEEE，2014：40-43.

[10]MURUGAN T S. Shortest energy based optimal route in zigbee mesh network[J]. International journal of applied engineering research，2015，10(15)：35258-35260.

[11]宋倩倩，王宏剛，盧光躍.基于灰色關(guān)聯(lián)度的Leach算法的改進[J].電視技術(shù)，2015，39(3)：144-147.

[12]鄧聚龍.灰色控制系統(tǒng)[M].武漢：華中理工大學(xué)出版社，1995.

金 勇(1974— )，碩士生導(dǎo)師，主要研究方向為移動通信網(wǎng)絡(luò)規(guī)劃與優(yōu)化等；

徐仁發(fā)(1989— )，碩士生，主研物聯(lián)網(wǎng)、無線傳感網(wǎng)絡(luò)等；

舒 紅(1991— )，女，碩士生，主研無線傳感網(wǎng)絡(luò)、移動通信技術(shù)等。

責(zé)任編輯：許 盈

Hybrid routing algorithm based on grey relational algorithm in ZigBee network

JIN Yong1,2,XU Renfa1,SHU Hong1

(1.ChongqingKeyLabofMobileCommunicationsTechnology,ChongqingUniversityofPostsandTelecommunications,Chongqing400065,China；2.CommunicationEngineeringApplicationResearchInstitute,ChongqingUniversityofPostsandTelecommunications,Chongqing400065,China)

The hop-count between the source node and the destination node is the only routing metric in ZigBee network hybrid routing algorithm (ZigBee Routing, ZBR). However, this property of the algorithm leads to the intermittent connectivity of the network, with the energy consumption of nodes and the frequent mobility of nodes. As a result, the performance of the ZigBee network degrades. In this paper, a grey relational algorithm is proposed based on ZigBee network hybrid routing algorithm (Grey Relational Algorithm based ZBR, GRA-ZBR), which can select the best path between the source node and the destination node. At first, GRA-ZBR takes various factors, including the residual energy, link quality, the remaining queue length and hop-count, into consideration. Then, the best path is selected via grey relational algorithm. Experimental results show that GRA-ZBR can improve the network packet delivery ratio and reduce the average end-to-end delay, effectively.

ZigBee network; routing algorithm; grey relational; path selection

金勇，徐仁發(fā)，舒紅.基于灰色關(guān)聯(lián)的ZigBee網(wǎng)絡(luò)混合路由算法[J].電視技術(shù)，2016，40(11)：70-74. JIN Y，XU R F，SHU H.Hybrid routing algorithm based on grey relational algorithm in ZigBee network[J].Video engineering，2016，40(11)：70-74.

TN949.6

A

10.16280/j.videoe.2016.11.015

長江學(xué)者和創(chuàng)新團隊發(fā)展計劃(1RT1299);重慶市科委項目(CSTC2012JJA40044;CSTC2013YYKFA40010)

2016-03-01