基于灰色關聯的ZigBee網絡混合路由算法

金 勇，徐仁發，舒 紅

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

?

基于灰色關聯的ZigBee網絡混合路由算法

金 勇1，2，徐仁發1，舒 紅1

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

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

ZigBee網絡；路由算法；灰色關聯；路徑選擇

ZigBee網絡是一種采用ZigBee技術的無線傳感網絡，隨著“物聯網+”理論的提出，ZigBee網絡受到越來越多的關注[1]。ZigBee網絡由于具有低成本、低功耗、低復雜度、高容量等特點而被廣泛應用于智能家居、工業監測、智能交通等領域[2]。

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

大量研究表明：數據分組轉發路徑的優劣在很大程度上決定了路由算法的好壞[3]。所以，本文主要從選擇最優路徑方向做出研究。

1 ZBR路由算法

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

圖1 ZBR路由算法流程圖

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

2 GRA-ZBR路由算法

2.1 灰色關聯理論

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

1)選擇影響因子

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

2)RREQ消息處理

路由發現過程中，目的節點會接收到來自多個中間節點轉發的RREQ分組。假設目的節點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)無量綱化處理

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

k=1,2,3,…,n

(4)

k=1,2,3,…,n

(5)

5)參考序列

為了更準確地反映出各RREQ消息的優劣程度，本文根據實時網絡狀況設定最優、最差兩個參考序列，分別如

2,…,m

(6)

2,…,m

(7)

6)灰色關聯系數

影響評估因子的最優、最差灰色關聯系數[12]的計算式如

(8)

(9)

式中：ξ為分辨系數，且有ξ=0.5。

7)灰色關聯度

各條RREQ消息的最優、最差灰色關聯度的計算式為

(10)

(11)

8)RREQ消息灰色關聯度

各條RREQ消息的灰色關聯度[12]的計算式為

(12)

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

2.2 GRA-ZBR路由算法實現過程

與經典ZBR算法相比，GRA-ZBR算法主要對路由發現過程做出改進，如圖2所示。

圖2 GRA-ZBR算法流程圖

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

步驟1，有數據傳輸需求的節點首先查詢自身路由表，若具有目的節點相關表項，則根據該目的路由表進行數據分組轉發；否則，判斷自身節點類型。

步驟2，若源節點為RN-節點，則使用Cluster-Tree路由算法轉發數據分組；若源節點為RN+節點，則進入路由發現過程。

步驟3，將源節點的剩余能量、剩余隊列長度、鏈路質量、路徑跳數等信息添加到RREQ消息對應字段。

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

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

步驟6，目的節點選擇灰色關聯度最大的RREQ消息回復RREP消息。

步驟7，源節點接收到RREP消息后，建立源節點和目的節點之間數據分組轉發路徑。

3 仿真分析

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

表1 仿真參數設置

3.1 分組投遞率

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

圖3 不同節點數量下的分組投遞率

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

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

3.2 平均端到端時延

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

圖5 不同節點數量下的端到端時延

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

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

4 小結

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

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

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

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

[4]錢志鴻，朱爽，王雪.基于分簇機制的ZigBee混合路由能量優化算法[J].計算機學報，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]謝忠明，何華冰，李云飛.一種基于鏈路狀態感知的Zigbee多徑路由算法[J].微電子學與計算機，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]宋倩倩，王宏剛，盧光躍.基于灰色關聯度的Leach算法的改進[J].電視技術，2015，39(3)：144-147.

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

金 勇(1974— )，碩士生導師，主要研究方向為移動通信網絡規劃與優化等；

徐仁發(1989— )，碩士生，主研物聯網、無線傳感網絡等；

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

責任編輯：許 盈

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

金勇，徐仁發，舒紅.基于灰色關聯的ZigBee網絡混合路由算法[J].電視技術，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

長江學者和創新團隊發展計劃(1RT1299);重慶市科委項目(CSTC2012JJA40044;CSTC2013YYKFA40010)

2016-03-01