劉 青，李蘭蘭，宮 強(qiáng)

（1.滁州職業(yè)技術(shù)學(xué)院 信息工程學(xué)院，安徽 滁州 239000；2.南京航空航天大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 210016）

ZigBee 技術(shù)作為物聯(lián)網(wǎng)關(guān)鍵技術(shù)之一，已經(jīng)被廣泛應(yīng)用在農(nóng)業(yè)、醫(yī)療、家居、環(huán)境監(jiān)測等多個領(lǐng)域。它具有低功耗、短距離、自組網(wǎng)和低成本等優(yōu)勢，適合多種環(huán)境下大規(guī)模快速組網(wǎng)。由于使用場景的限制，Zig?Bee節(jié)點大多使用電池供電，如何限制能耗，均衡網(wǎng)絡(luò)性能，延長網(wǎng)絡(luò)生存周期，是當(dāng)前ZigBee技術(shù)研究的熱點之一。雖然ZigBee技術(shù)也采用了一些措施，如節(jié)點定時休眠、周期喚醒、簡化協(xié)議、規(guī)避沖突等，但網(wǎng)絡(luò)通信能耗大、節(jié)點失效快等問題仍然存在。

ZigBee技術(shù)的能耗控制問題主要涉及PHY層、MAC層和網(wǎng)絡(luò)層的研究[1]，網(wǎng)絡(luò)層主要是路由算法優(yōu)化研究，可分為網(wǎng)狀路由、混合路由和分簇路由等?，F(xiàn)有的分簇與能量控制路由算法，如閾值敏感分簇能量控制算法、低能量自適應(yīng)分簇算法、能量優(yōu)化分簇路由算法等，都是根據(jù)能量閾值、響應(yīng)時間、網(wǎng)絡(luò)深度等條件將網(wǎng)絡(luò)劃分成若干邏輯簇，由簇首管理簇內(nèi)節(jié)點，簇首轉(zhuǎn)發(fā)簇間通信，并按一定算法調(diào)整網(wǎng)絡(luò)結(jié)構(gòu)，優(yōu)化網(wǎng)絡(luò)負(fù)載[2-4]。本文設(shè)計一種能量預(yù)警和分簇的ZigBee路由算法，依據(jù)簇樹路由算法，引入簇首等節(jié)點能量監(jiān)測機(jī)制，實現(xiàn)動態(tài)預(yù)警，適時啟動備用節(jié)點，均衡節(jié)點能耗，延長網(wǎng)絡(luò)生命周期。

1 ZigBee路由協(xié)議

ZigBee 網(wǎng)絡(luò)使用的是靜態(tài)路由協(xié)議，節(jié)點組成樹形結(jié)構(gòu)。網(wǎng)絡(luò)依據(jù)IEEE802.15.4 標(biāo)準(zhǔn)定義了協(xié)調(diào)器（Coordinator）、路由器（Router）和終端節(jié)點（End Device）三類設(shè)備，分為精簡功能型（RFD）和完全功能型（FFD）[5-6]。ZigBee網(wǎng)絡(luò)中的每個節(jié)點都擁有一個64位的IEEE地址和一個16位網(wǎng)絡(luò)地址，采用DAAM地址分配機(jī)制，協(xié)調(diào)器分配給父節(jié)點一定長度的地址段，父節(jié)點為新加入的子節(jié)點分配一個唯一網(wǎng)絡(luò)地址，形成邏輯的父子關(guān)系[7]。其地址分配算法基于式（1）～（3）。

公式（1）中Cskip(d)是地址偏移量，Lm是網(wǎng)絡(luò)最大深度，Rm是父節(jié)點可連接的最多路由數(shù)，Cm是父節(jié)點可連接最多子節(jié)點數(shù)，d是父節(jié)點深度[8]。終端節(jié)點i加入f網(wǎng)絡(luò)，父節(jié)點f依據(jù)公式（2）為其分配地址。路由節(jié)點j加入f網(wǎng)絡(luò)，依據(jù)公式（3）為其分配地址。

1.1 Cluster-Tree 路由算法

Cluster-Tree 即簇樹路由算法，協(xié)議中無路由表，依據(jù)父子關(guān)系的鄰接表轉(zhuǎn)發(fā)數(shù)據(jù)，無路由維護(hù)開銷[9]。使用式（4）來判斷目標(biāo)節(jié)點是否為源節(jié)點的后代節(jié)點，按照式（5）來計算下一跳地址。Cluster-Tree適用于簡單網(wǎng)絡(luò)拓?fù)?，具有通信效率高，網(wǎng)絡(luò)開銷小等特點。Cluster-Tree 不足之處，一是相鄰節(jié)點間無邏輯父子關(guān)系，數(shù)據(jù)轉(zhuǎn)發(fā)需多跳完成，通信效率低，節(jié)點能耗高；二是傳輸路徑不一定最優(yōu)，臨近根的節(jié)點容易因能耗高而過早脫離網(wǎng)絡(luò)，形成網(wǎng)絡(luò)孤島。

1.2 AODVjr 路由算法

AODVjr 路由算法是AODV（Ad hoc On-Demand Distance Vector routing）按需距離矢量路由算法的簡化版[10]。AODVjr取消了AODV協(xié)議中的目標(biāo)節(jié)點序號，只允許目標(biāo)節(jié)點RREP響應(yīng)；刪除了AODV路由協(xié)議中RREQ、RREP、RERR 中的跳數(shù)、序列號等信息；舍棄了前驅(qū)列表和HELLO 信息，使用周期性發(fā)送KEEP_ALIVE給源節(jié)點來維護(hù)路由表，如RREP分組報文，格式如表1所示。它彌補(bǔ)了Cluster-Tree算法路由發(fā)現(xiàn)的不足，具有收斂速度快、拓?fù)鋵W(xué)習(xí)能力強(qiáng)、有效節(jié)省能耗等特點。AODVjr的不足之處，一是周期性發(fā)送路由維護(hù)信息，堵塞網(wǎng)絡(luò)；二是新路由發(fā)現(xiàn)過程能耗大，增加開銷。

表1 RREP分組報文格式Table 1 RREP packet message format

2 分簇路由算法

分簇路由算法可將一個ZigBee網(wǎng)絡(luò)分成若干個邏輯簇，簇中節(jié)點一般分為簇首（Cluster Head Node）、網(wǎng)關(guān)（Gateway Node）、簇內(nèi)節(jié)點（Within The Cluster Node）等[11]。根據(jù)網(wǎng)絡(luò)拓?fù)鋸?fù)雜性，有單層和多層分簇路由算法；依據(jù)轉(zhuǎn)發(fā)跳數(shù)情況，又分為簇內(nèi)單跳、簇內(nèi)多跳、簇首多跳、簇內(nèi)簇首多跳幾種算法。單層分簇路由算法具有結(jié)構(gòu)簡單、收斂速度快、容易實現(xiàn)等特點，是本文研究的基礎(chǔ)。與平面路由等算法相比，分簇路由算法在能量控制、網(wǎng)絡(luò)擴(kuò)展、負(fù)載均衡等方面具有優(yōu)越性。

ZiCL（Cluster Laber-based ZigBee Routing Protocol）是一種依據(jù)網(wǎng)絡(luò)深度分簇路由算法[12]。協(xié)調(diào)器是第一個簇頭，網(wǎng)絡(luò)深度是偶數(shù)的FFD節(jié)點為簇首，RFD節(jié)點和奇數(shù)FFD節(jié)點為其父節(jié)點的簇員。依據(jù)簇標(biāo)簽算法分配簇的唯一標(biāo)識，簇首廣播更新路由，簇內(nèi)共享路由信息。源節(jié)點A與目標(biāo)節(jié)點D通信時，首先計算目標(biāo)節(jié)點所在簇的標(biāo)簽，根據(jù)簇標(biāo)簽選擇路由，同簇使用簇內(nèi)路由轉(zhuǎn)發(fā)，簇間使用外部路由轉(zhuǎn)發(fā)，具體流程如圖1所示。ZB-CESRP是一種靜態(tài)分簇路由算法[13]，要求所有節(jié)點均勻分布，節(jié)點類型只能是FFD設(shè)備。與協(xié)調(diào)器直接連接的節(jié)點定為簇首，并分配簇ID，簇首依據(jù)算法為子節(jié)點分配節(jié)點ID。節(jié)點加入網(wǎng)絡(luò)后，簇首進(jìn)行簇內(nèi)廣播，通過設(shè)置TTL值避免泛洪，簇內(nèi)節(jié)點記錄鄰節(jié)點報文，優(yōu)化節(jié)點路由，節(jié)省能耗，ZB-CESRP算法的建簇流程如圖2所示。ME-AODV（Multipath Energy Aware AODV）分簇路由算法[14]有效融合了AOM?DV和MBCR算法的思想，網(wǎng)絡(luò)通信分創(chuàng)建簇和數(shù)據(jù)轉(zhuǎn)發(fā)兩個階段，建簇的同時建立Mesh鏈路，每個簇有唯一ID，分協(xié)調(diào)器、簇首、網(wǎng)關(guān)、簇內(nèi)節(jié)點等角色，簇間與簇內(nèi)均單跳通信，簇內(nèi)路由信息共享[15]。

圖1 ZiCL算法的路由流程圖Figure 1 Routing flow chart of ZiCL algorithm

圖2 ZB-CESRP算法的建簇過程圖Figure 2 Cluster building process of ZB-CESRP algorithm

3 基于能量預(yù)警和分簇的ZigBee網(wǎng)絡(luò)路由算法

本文提出的改進(jìn)路由算法是融合了Cluster-Tree 和AODVjr算法的優(yōu)點，結(jié)合ME-AODV 算法的建簇思想，提出的一種基于能量預(yù)警機(jī)制的ZigBee 網(wǎng)絡(luò)單層分簇路由算法。改進(jìn)算法將網(wǎng)絡(luò)劃分為若干邏輯簇，簇首有唯一ID。FFD設(shè)備可以成為簇首，RFD設(shè)備只能成為簇員。建簇過程如圖3所示。①ZigBee協(xié)調(diào)器通過廣播方式，在其通信范圍內(nèi)建立第一個簇，并與非子節(jié)點建立通信鏈路，例如節(jié)點A與節(jié)點K。②以簇0所有子節(jié)點為當(dāng)前節(jié)點，繼續(xù)廣播發(fā)現(xiàn)新節(jié)點，如發(fā)現(xiàn)的節(jié)點是簇0簇內(nèi)節(jié)點則建立兄弟鏈路關(guān)系，如果新發(fā)現(xiàn)節(jié)點已經(jīng)是簇首，以父節(jié)點為簇首；如果發(fā)現(xiàn)節(jié)點與當(dāng)前節(jié)點無父子關(guān)系，連通度較大、網(wǎng)絡(luò)地址較小者為簇首，如D節(jié)點的連通性高于J節(jié)點，D點為簇首。重復(fù)步驟①和②，直到建簇完成，形成以A、E、D、R節(jié)點為簇首，J、N、L節(jié)點為網(wǎng)關(guān)的分簇網(wǎng)絡(luò)。

圖3 改進(jìn)路由算法的建簇過程Figure 3 Cluster building process of improved routing algorithm

3.1 能量監(jiān)測與預(yù)警

ZigBee網(wǎng)絡(luò)中除協(xié)調(diào)器外均使用電池供電，對各節(jié)點實施能量分級預(yù)警監(jiān)測。節(jié)點剩余能量達(dá)到初始能量一半時，進(jìn)入“偏低”狀態(tài)；剩余能量是初始能量的四分之一時，進(jìn)入“預(yù)警”狀態(tài)。網(wǎng)關(guān)和簇首節(jié)點位置特殊，耗電較快，簇首能量“偏低”時，開啟簇首延長響應(yīng)功能。簇首或網(wǎng)關(guān)能量“預(yù)警”時，簇首丟棄非路由表中的信息，啟動備用網(wǎng)關(guān)遴選機(jī)制，如節(jié)點F因可收到簇首A和D的信息，可成為網(wǎng)關(guān)L的備用網(wǎng)關(guān)，同時廣播修改路由表。使用公式（6）計算節(jié)點剩余能量，實現(xiàn)實時動態(tài)監(jiān)測。Ei是節(jié)點的最初能量；di表示節(jié)點所在網(wǎng)絡(luò)深度，di≤4；ε是固定系數(shù)，0 ＜ε ＜1；α是網(wǎng)絡(luò)深度的冪，取值為1到4的整數(shù)；N初始值為1，隨著預(yù)警節(jié)點的增加而加大。使用公式（7）計算節(jié)點網(wǎng)絡(luò)節(jié)點平均剩余能量，n是節(jié)點數(shù)，Er(i) 是第i節(jié)點剩余能量。使用公式（8）計算節(jié)點延遲響應(yīng)時間。Er是簇首節(jié)點的剩余能量，β是延遲因子，根據(jù)節(jié)點的角色，將協(xié)調(diào)器、簇首、網(wǎng)關(guān)和簇內(nèi)節(jié)點的β值分別設(shè)置為8、4、2、1。

3.2 路由維護(hù)過程

當(dāng)簇首能量充足時，簇內(nèi)節(jié)點使用虛擬鏈路通信，簇間使用AODVjr 算法路由發(fā)現(xiàn)目的節(jié)點，并廣播剩余能量值。當(dāng)簇首能量偏低時，簇內(nèi)節(jié)點使用Cluster-Tree 算法，使用公式（4）、（5）計算目標(biāo)節(jié)點與源節(jié)點之間是否為父子關(guān)系并轉(zhuǎn)發(fā)。簇間采用AODVjr算法，具體路由流程如圖4所示。當(dāng)簇首能量預(yù)警時，只轉(zhuǎn)發(fā)現(xiàn)存路由條目的目的地址，發(fā)送預(yù)警信號給協(xié)調(diào)器，開始網(wǎng)絡(luò)初始化。當(dāng)節(jié)點能量枯竭時，鏈路斷開，將源數(shù)據(jù)報緩存并開啟路由修護(hù)。

圖4 簇首能量偏低時的路由流程圖Figure 4 Routing flow chart when cluster head energy is low

4 仿真結(jié)果與分析

為分析改進(jìn)路由算法的性能，使用NS2軟件進(jìn)行了仿真實驗。本文從網(wǎng)絡(luò)主要節(jié)點剩余能量、節(jié)點失效率和數(shù)據(jù)延遲時間3個方面與AODVjr算法做了對比。具體實驗場景如表2所示。

表2 仿真參數(shù)Table 2 Simulation parameters

4.1 節(jié)點剩余能量

節(jié)點剩余能量是指網(wǎng)絡(luò)主要節(jié)點的剩余能量。AODVjr算法選取協(xié)調(diào)器一跳的節(jié)點為主要節(jié)點，改進(jìn)的算法以簇首節(jié)點為主要節(jié)點。如圖5所示，隨著節(jié)點數(shù)和時間的增加，兩種算法的主要節(jié)點剩余能量都逐漸降低，特別是300 s以后，AODVjr 算法持續(xù)陡降，而改進(jìn)的算法采用預(yù)警機(jī)制，在主要節(jié)點剩余能量過半后開啟延遲轉(zhuǎn)發(fā)，選擇備用節(jié)點，使得剩余能量曲線趨于緩慢。

圖5 網(wǎng)絡(luò)主要節(jié)點剩余能量對比圖Figure 5 Comparison of residual energy of main nodes of the network

4.2 節(jié)點失效率

節(jié)點失效率是指節(jié)點“死亡”個數(shù)占總節(jié)點數(shù)的百分比。節(jié)點剩余能量到初始能量的5%時，認(rèn)為節(jié)點死亡。相同時間內(nèi)數(shù)值越低，說明節(jié)點存活得越多，網(wǎng)絡(luò)生命周期越長。如圖6所示，隨著運行時間的增加，兩種算法都開始有節(jié)點失效，但改進(jìn)的算法延遲到250 s，明顯優(yōu)于AODVjr 算法。特別在350 s 以后，兩種算法失效率差達(dá)到10個百分點，說明改進(jìn)的算法更能均衡網(wǎng)絡(luò)能耗。

圖6 網(wǎng)絡(luò)節(jié)點失效率對比圖Figure 6 Comparison of network node failure rate

4.3 數(shù)據(jù)延遲時間

數(shù)據(jù)延長時間是指數(shù)據(jù)從源節(jié)點發(fā)送至目標(biāo)節(jié)點的端到端時間的平均值，即數(shù)據(jù)的總發(fā)送和總接收的時間差與分組個數(shù)的比值。數(shù)值越低，說明網(wǎng)絡(luò)延遲越短，通信效率越高。如圖7所示，在網(wǎng)絡(luò)節(jié)點較少時，兩種算法的延遲都較低。隨著節(jié)點數(shù)的增加，數(shù)據(jù)分組加劇，兩種算法延長都有明顯增加。但改進(jìn)的算法優(yōu)化了分簇策略，簇間使用AODVjr 路由，簇內(nèi)采用Cluster-Tree 路由，且虛擬鏈路共享，有效減少了轉(zhuǎn)發(fā)跳數(shù)，降低了端到端的延遲。

圖7 網(wǎng)絡(luò)通信端到端延長對比圖Figure 7 Comparison diagram of end-to-end extension of network communication

5 結(jié)論

本文提出一種基于能量預(yù)警的分簇ZigBee 路由算法，針對現(xiàn)有算法的不足，融合了AODVjr 和Cluster-Tree算法的優(yōu)點，參考ME-AODV算法的建簇思想，設(shè)置節(jié)點能量動態(tài)監(jiān)測，依據(jù)簇首能量等級啟用備用節(jié)點，選擇合適路由轉(zhuǎn)發(fā)機(jī)制。使用NS2仿真軟件，從主要節(jié)點能量消耗、節(jié)點失效率和端到端平均時延三個方面與AODVjr算法做了對比，結(jié)果表明，本算法均衡了網(wǎng)絡(luò)能量，提高了網(wǎng)絡(luò)通信效率，降低了網(wǎng)絡(luò)延遲，延長了網(wǎng)絡(luò)生命周期。在智能家居、智慧農(nóng)業(yè)等領(lǐng)域中監(jiān)測節(jié)點相對固定，本算法將有一定應(yīng)用。