基于ZigBee的集群機(jī)器人網(wǎng)絡(luò)路由算法

李躍　黃希玲　賈海瑞

摘要：集群機(jī)器人系統(tǒng)中使用ZigBee網(wǎng)絡(luò)技術(shù)可實(shí)現(xiàn)有效的通信，但樹(shù)形組網(wǎng)可能使部分節(jié)點(diǎn)過(guò)早耗盡電池能量，所以使用ZigBee技術(shù)的機(jī)器人系統(tǒng)中，ZigBee網(wǎng)絡(luò)的路由算法是研究的關(guān)鍵問(wèn)題。在重點(diǎn)研究了ZigBee協(xié)議網(wǎng)絡(luò)層樹(shù)型路由算法的基礎(chǔ)上，提出了一種適用于機(jī)器人通信系統(tǒng)的路由算法（RACRS），改進(jìn)算法中通過(guò)引入鄰居表，考慮網(wǎng)絡(luò)中的電池供電節(jié)點(diǎn)和持續(xù)供電節(jié)點(diǎn)，路由選擇網(wǎng)絡(luò)中的關(guān)鍵路徑而盡量避開(kāi)電池供電節(jié)點(diǎn)。仿真結(jié)果表明改進(jìn)算法能有效節(jié)省網(wǎng)絡(luò)中電池供電機(jī)器人網(wǎng)絡(luò)節(jié)點(diǎn)的能量消耗，增強(qiáng)集群機(jī)器人系統(tǒng)中ZigBee網(wǎng)絡(luò)的穩(wěn)定性，最大化系統(tǒng)網(wǎng)絡(luò)的生存時(shí)間。

關(guān)鍵詞：集群機(jī)器人；無(wú)線傳感器；ZigBee網(wǎng)絡(luò)；通信協(xié)議

Abstract： Cluster robotic system using ZigBee network technology can achieve an effective communication， but some nodes may use up all the energy because of heavy transmissions. So in robot system using ZigBee technology， the key issue of the research on its network layer is routing algorithm. This paper focuses on the research into such an issue an analyzes the tree. Based on the above analysis， an improved routing algorithm which suitable the robot communication system is proposed（Routing Algorithm of Cluster Robotic System，RACRS）. The algorithm introduce the neighbor table and consider the battery-powered nodes and continuous power node， selecting the critical path in the network routing try to avoid the battery-powered node. The simulation results show that the improved algorithm can effectively save the battery-powered robot node energy consumption and the lifetime of the whole network was maximized in this improved algorithm.

Keywords： groups of robots； wireless sensor； ZigBee network； communications

0 引言

機(jī)器人技術(shù)作為信息技術(shù)和先進(jìn)制造的典型代表和主要技術(shù)手段，已成為世界各國(guó)競(jìng)相發(fā)展的技術(shù)。隨著社會(huì)生產(chǎn)技術(shù)的飛速發(fā)展，機(jī)器人的應(yīng)用領(lǐng)域也不斷擴(kuò)展，從工業(yè)自動(dòng)化到海洋資源的探索，乃至太空作業(yè)等領(lǐng)域。同時(shí)由多個(gè)機(jī)器人組成的集群系統(tǒng)通過(guò)協(xié)調(diào)、協(xié)作來(lái)完成單機(jī)器人無(wú)法或難以完成的工作是機(jī)器人發(fā)展的一個(gè)趨勢(shì)，如流水線生產(chǎn)、編隊(duì)巡邏、倉(cāng)儲(chǔ)運(yùn)輸、交通規(guī)劃等應(yīng)用領(lǐng)域[1]。分布式集群機(jī)器人系統(tǒng)具有高度的自規(guī)劃、自組織特性，機(jī)器人的定位、協(xié)調(diào)與分析控制是應(yīng)用研究的重點(diǎn)，實(shí)現(xiàn)這些功能，機(jī)器人之間和控制系統(tǒng)需要可靠地進(jìn)行通信。無(wú)線通信技術(shù)能夠增加機(jī)器人的活動(dòng)范圍和靈活性，使用ZigBee無(wú)線傳感器網(wǎng)絡(luò)技術(shù)組建無(wú)線網(wǎng)絡(luò)，可在機(jī)器人系統(tǒng)中實(shí)現(xiàn)可靠的通信，顯著提高機(jī)器人的工作效率[1]。

集群機(jī)器人系統(tǒng)控制方式分為集中式和分布式。集中式是有中心化的協(xié)調(diào)機(jī)構(gòu)，控制效率比較高，但由于選擇集中控制來(lái)解決所有機(jī)器人產(chǎn)生的沖突，需要增加一個(gè)主控制器，主控制器的工作負(fù)荷很大。而分布式控制不存在有任何中心控制器，由局部范圍內(nèi)的機(jī)器人實(shí)現(xiàn)協(xié)同控制。本文的研究基于混合式結(jié)構(gòu)，混合式結(jié)構(gòu)本質(zhì)上是一種層次結(jié)構(gòu)，上層的主控制器或領(lǐng)導(dǎo)機(jī)器人對(duì)下層的機(jī)器人只有部分控制能力。該方式可實(shí)現(xiàn)集中和分布式結(jié)構(gòu)的互補(bǔ)，提高系統(tǒng)靈活性和協(xié)調(diào)效率[2]。本文針對(duì)混合式結(jié)構(gòu)的集群機(jī)器人系統(tǒng)，提出了一種適用于集群機(jī)器人系統(tǒng)的ZigBee網(wǎng)絡(luò)路由新算法（Routing Algorithm of Cluster Robotic System，RACRS）。該算法考慮了集群機(jī)器人系統(tǒng)的應(yīng)用場(chǎng)所及其特點(diǎn)，提高了路由算法的效率，降低了網(wǎng)絡(luò)中電池供電節(jié)點(diǎn)的能量消耗，延長(zhǎng)了網(wǎng)絡(luò)的生存時(shí)間和自適應(yīng)能力，對(duì)集群機(jī)器人系統(tǒng)網(wǎng)絡(luò)的組建具有指導(dǎo)意義。

1.ZigBee簇樹(shù)組網(wǎng)及其路由算法

ZigBee技術(shù)是一種新興的近距離、低復(fù)雜度、低功耗、低數(shù)據(jù)率、低成本的短距離無(wú)線通信標(biāo)準(zhǔn)。ZigBee技術(shù)以IEEE802.15.4協(xié)議作為其物理層和介質(zhì)訪問(wèn)層（Medium Access Layer， MAC）的標(biāo)準(zhǔn)協(xié)議，網(wǎng)絡(luò)層和應(yīng)用接口層由ZigBee聯(lián)盟定制[1]。ZigBee技術(shù)主要用于近距離無(wú)線連接，相對(duì)于現(xiàn)有的各種無(wú)線通信技術(shù)，ZigBee技術(shù)是具有最低功耗和最低成本的技術(shù)。ZigBee技術(shù)數(shù)據(jù)率的特點(diǎn)適合于承載數(shù)據(jù)流量較小的業(yè)務(wù)，被廣泛的應(yīng)用于工業(yè)控制、自動(dòng)化等領(lǐng)域[3]。

1.1 ZigBee簇樹(shù)型結(jié)構(gòu)

IEEE802.15.4定義了兩種物理設(shè)備，全功能設(shè)備（FFD）和精簡(jiǎn)功能設(shè)備（RFD）。FFD可以擔(dān)任網(wǎng)絡(luò)協(xié)調(diào)器，也能作為終端設(shè)備，可以與RFD或其他FFD通訊。RFD只能與FFD通訊，在網(wǎng)絡(luò)中通常用作終端設(shè)備，實(shí)現(xiàn)非常簡(jiǎn)單，通常以電池供電，只需較少的資源和存儲(chǔ)空間，成本比FFD低很多。ZigBee網(wǎng)絡(luò)中，定義了三種邏輯設(shè)備類型：ZigBee協(xié)調(diào)器、ZigBee路由器和ZigBee終端設(shè)備。FFD可以實(shí)現(xiàn)ZigBee全部邏輯設(shè)備功能，RFD只能作為ZigBee終端設(shè)備[4]。

首先由ZigBee協(xié)調(diào)器構(gòu)建整個(gè)網(wǎng)絡(luò)，協(xié)調(diào)器進(jìn)行信道掃描，選擇一個(gè)未探測(cè)到的網(wǎng)絡(luò)空閑信道，然后確定自己的16位網(wǎng)絡(luò)地址、地址的PAN ID及網(wǎng)絡(luò)的拓?fù)鋮?shù)等，當(dāng)各項(xiàng)參數(shù)設(shè)定好后，協(xié)調(diào)器便可以接受其他節(jié)點(diǎn)加入網(wǎng)絡(luò)。加入ZigBee網(wǎng)絡(luò)的節(jié)點(diǎn)通過(guò)MAC層提供的關(guān)聯(lián)過(guò)程組成一棵邏輯樹(shù)，當(dāng)網(wǎng)絡(luò)中的節(jié)點(diǎn)允許一個(gè)新節(jié)點(diǎn)通過(guò)它加入網(wǎng)絡(luò)時(shí)，他們便形成了父子關(guān)系，父節(jié)點(diǎn)為子節(jié)點(diǎn)分配網(wǎng)絡(luò)中唯一的16位網(wǎng)絡(luò)地址。假設(shè)父節(jié)點(diǎn)最多可連接的子節(jié)點(diǎn)數(shù)為Cm，子節(jié)點(diǎn)中的最大路由器數(shù)為Rm，網(wǎng)絡(luò)的最大深度為L(zhǎng)m，可以根據(jù)（1）式得到網(wǎng)絡(luò)深度為d的父節(jié)點(diǎn)為其子節(jié)點(diǎn)分配的地址之間的偏移量Cskip（d），即：

當(dāng)一個(gè)新的RFD子節(jié)點(diǎn)A通過(guò)Ap加入到網(wǎng)絡(luò)中，Ap節(jié)點(diǎn)成為這個(gè)新節(jié)點(diǎn)的父節(jié)點(diǎn)，Ap使用（2）式為子節(jié)點(diǎn)A分配地址，即：

如果是新的FFD節(jié)點(diǎn)加入，它具有路由能力，所以父節(jié)點(diǎn)Ap使用（3）式為子節(jié)點(diǎn)A分配網(wǎng)絡(luò)地址，即：

1.2簇樹(shù)型路由算法

樹(shù)型網(wǎng)絡(luò)拓?fù)洌═ree）路由算法中，節(jié)點(diǎn)根據(jù)目的節(jié)點(diǎn)的網(wǎng)絡(luò)地址計(jì)算分組的下一跳，假設(shè)地址為A，深度為d的ZigBee路由節(jié)點(diǎn)收到目的節(jié)點(diǎn)地址為D的數(shù)據(jù)幀，路由節(jié)點(diǎn)首先通過(guò)（4）式判斷該目的節(jié)點(diǎn)是否是它的后代節(jié)點(diǎn)，

如果目的節(jié)點(diǎn)是接收節(jié)點(diǎn)的后代節(jié)點(diǎn)，該數(shù)據(jù)幀將被轉(zhuǎn)發(fā)給它的子節(jié)點(diǎn)N，依據(jù)（5）式可以確定將數(shù)據(jù)幀轉(zhuǎn)發(fā)給其終端子節(jié)點(diǎn)或路由子節(jié)點(diǎn)

如果目的節(jié)點(diǎn)不是它的后代節(jié)點(diǎn)，則將數(shù)據(jù)幀沿著樹(shù)型結(jié)構(gòu)轉(zhuǎn)發(fā)到父節(jié)點(diǎn)。

2.集群機(jī)器人系統(tǒng)

2.1 系統(tǒng)框架模型

對(duì)于固定通信節(jié)點(diǎn)和位置固定機(jī)器人，可以將固定通信節(jié)點(diǎn)環(huán)境模型預(yù)先標(biāo)定為不變模型，而對(duì)于移動(dòng)機(jī)器人，其通信環(huán)境模型是變化的。對(duì)于整個(gè)通信網(wǎng)絡(luò)模型則是不變模型和可變模型的結(jié)合，屬于動(dòng)態(tài)模型（Dynamic Model，DM）[5]。對(duì)于固定通信節(jié)點(diǎn)或者具有通信能力的固定機(jī)器人設(shè)備模型，可以預(yù)先標(biāo)定，采用持續(xù)電源為通信節(jié)點(diǎn)供電。而對(duì)于移動(dòng)機(jī)器人，為了增強(qiáng)機(jī)器人的靈活性和活動(dòng)范圍，機(jī)器人ZigBee通信節(jié)點(diǎn)采用電池供電方式。由于ZigBee組網(wǎng)技術(shù)具有自適應(yīng)能力，網(wǎng)絡(luò)環(huán)境發(fā)生變化后，被斷開(kāi)連接的通信節(jié)點(diǎn)能夠再次自動(dòng)發(fā)起網(wǎng)絡(luò)連接請(qǐng)求，再次和網(wǎng)絡(luò)建立連接，該網(wǎng)絡(luò)模型適用于混合分布式集群機(jī)器人系統(tǒng)的網(wǎng)絡(luò)通信。

在工業(yè)生產(chǎn)和大型公共場(chǎng)所中，使用集群機(jī)器人系統(tǒng)可有效的提高生產(chǎn)效率，或更加便利的服務(wù)生活。在這樣的應(yīng)用環(huán)境中，部分機(jī)器人或通信節(jié)點(diǎn)位置固定，而其它機(jī)器人可以移動(dòng)，它們和位置固定的機(jī)器人協(xié)同完成復(fù)雜的任務(wù)。該系統(tǒng)中機(jī)器人個(gè)體存在結(jié)構(gòu)和功能上的差異，為有意識(shí)協(xié)作的異構(gòu)集群機(jī)器人系統(tǒng)[6-9] [12]，如在商場(chǎng)中發(fā)生突發(fā)事故，需要有事故檢測(cè)機(jī)器人，事故處理機(jī)器人等協(xié)同工作。該模型即是本文中研究的集群機(jī)器人系統(tǒng)的網(wǎng)絡(luò)模型。

2.2 集群機(jī)器人系統(tǒng)中樹(shù)型路由的問(wèn)題

樹(shù)型路由適用于節(jié)點(diǎn)靜止或者移動(dòng)較少的場(chǎng)合，屬于靜態(tài)路由，不需要路由表，節(jié)省存儲(chǔ)資源，對(duì)于傳輸數(shù)據(jù)包的響應(yīng)較快，在集群機(jī)器人系統(tǒng)中使用樹(shù)型路由對(duì)機(jī)器人的定位非常不靈活，浪費(fèi)大量的地址空間，并且路由效率低。如圖1所示，圖中C是網(wǎng)絡(luò)的協(xié)調(diào)器節(jié)點(diǎn)，標(biāo)號(hào)R1～R20的節(jié)點(diǎn)是FFD節(jié)點(diǎn)，RFD節(jié)點(diǎn)略去，持續(xù)電源供電的路由節(jié)點(diǎn)用粗實(shí)線表示，電池供電的路由節(jié)點(diǎn)用虛線表示。當(dāng)路由節(jié)點(diǎn)R9與路由節(jié)點(diǎn)R16通信時(shí)，其路由是R9-R1-C-R4-R3-R10-R16，使用樹(shù)路由轉(zhuǎn)發(fā)數(shù)據(jù)需要6跳，但由圖可知，節(jié)點(diǎn)R16在節(jié)點(diǎn)R9的直接通信范圍內(nèi)，因此R9可直接將數(shù)據(jù)發(fā)送發(fā)R16而無(wú)需其他節(jié)點(diǎn)轉(zhuǎn)發(fā)，這樣可提高路由效率。

集群機(jī)器人系統(tǒng)模型中，存在一定比例物理位置固定傳感器節(jié)點(diǎn)，樹(shù)型路由中沒(méi)有考慮網(wǎng)絡(luò)中的持續(xù)電源節(jié)點(diǎn)和電池供電節(jié)點(diǎn)的特點(diǎn)，將兩類傳感器節(jié)點(diǎn)同樣處理，這樣浪費(fèi)了持續(xù)電源節(jié)點(diǎn)這一資源，同時(shí)頻繁地使用電池供電的父節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)時(shí)，會(huì)大量消耗節(jié)點(diǎn)的能量，降低網(wǎng)絡(luò)的穩(wěn)定性[10] [11]。如圖1所示，網(wǎng)絡(luò)中頻繁地使用電池供電路由節(jié)點(diǎn)R4轉(zhuǎn)發(fā)數(shù)據(jù)，容易使R4節(jié)點(diǎn)過(guò)早的消耗完電池能量。如果能夠?qū)⒒ハ嘣谝惶秶鷥?nèi)的持續(xù)電源節(jié)點(diǎn)間建立虛路由[13]，如圖中虛直線所示，轉(zhuǎn)發(fā)數(shù)據(jù)時(shí)就可盡可能的使用持續(xù)電源節(jié)點(diǎn)，避開(kāi)電池供電節(jié)點(diǎn)，這樣就減少了電池供電路由節(jié)點(diǎn)的數(shù)據(jù)轉(zhuǎn)發(fā)量，節(jié)省了電池供電路由節(jié)點(diǎn)的能量，延長(zhǎng)了系統(tǒng)網(wǎng)絡(luò)的生存時(shí)間。

3.集群機(jī)器人系統(tǒng)的ZigBee網(wǎng)絡(luò)路由算法

3.1 鄰居表定義

ZigBee網(wǎng)絡(luò)中，具有路由能力的節(jié)點(diǎn)都有一個(gè)鄰居表，并對(duì)其動(dòng)態(tài)維護(hù)，每個(gè)節(jié)點(diǎn)在接收到信息包時(shí)，都要更新維護(hù)鄰居表，鄰居表中存儲(chǔ)的是該節(jié)點(diǎn)的鄰接節(jié)點(diǎn)的信息，鄰接節(jié)點(diǎn)是指在直接通信范圍內(nèi)的節(jié)點(diǎn)。鄰居表的結(jié)構(gòu)如圖2所示。鄰居表的記錄中有三個(gè)字段：ADDR是鄰居節(jié)點(diǎn)地址；NodeType是鄰居節(jié)點(diǎn)設(shè)備類型，區(qū)分節(jié)點(diǎn)是具有路由功能的FFD設(shè)備，還是不具有路由功能的RFD設(shè)備；PowerType是鄰居節(jié)點(diǎn)的電源類型；DeadTime是鄰居節(jié)點(diǎn)的確認(rèn)時(shí)間。

3.2 構(gòu)建關(guān)鍵路徑

混合式異構(gòu)集群機(jī)器人系統(tǒng)中，部分機(jī)器人或通信節(jié)點(diǎn)位置固定，這些路由節(jié)點(diǎn)使用持續(xù)電源供電。簇樹(shù)型ZigBee網(wǎng)絡(luò)組建完成后，由前文的分析可知，網(wǎng)絡(luò)的穩(wěn)定性較弱，路由選擇有限，同時(shí)電池供電節(jié)點(diǎn)頻繁的轉(zhuǎn)發(fā)數(shù)據(jù)，會(huì)縮短網(wǎng)絡(luò)時(shí)間。通過(guò)在簇樹(shù)型網(wǎng)絡(luò)中構(gòu)建多條只包含電源供電節(jié)點(diǎn)的虛路由，如圖2中的路由C-R1-R2-R3-R5、C-R7-R6、C-R1-R9-R16。其中R2與R3、R5與R6等互為鄰居節(jié)點(diǎn)，兩節(jié)點(diǎn)間可使用鄰居表建立虛路由。簇樹(shù)型網(wǎng)絡(luò)組建過(guò)程中，路由節(jié)點(diǎn)可識(shí)別出自己的電源類型，當(dāng)其加入網(wǎng)絡(luò)時(shí)，發(fā)送節(jié)點(diǎn)信息到協(xié)調(diào)器節(jié)點(diǎn)，協(xié)調(diào)器記錄該節(jié)點(diǎn)的信息，包括節(jié)點(diǎn)的電源類型，該節(jié)點(diǎn)鄰居節(jié)點(diǎn)中的持續(xù)電源路由節(jié)點(diǎn)和電池供電路由節(jié)點(diǎn)。協(xié)調(diào)器構(gòu)建帶權(quán)有向圖的鄰接矩陣，并依據(jù)接收到的信息修改相應(yīng)的鄰接矩陣。當(dāng)兩個(gè)路由節(jié)點(diǎn)互為鄰居節(jié)點(diǎn)時(shí)，設(shè)置其間的通信代價(jià)為0值或1值，其中0值表示起點(diǎn)為持續(xù)電源路由節(jié)點(diǎn)，即由持續(xù)電源路由節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)；而值1表示起點(diǎn)為電池供電路由節(jié)點(diǎn)，即由電池供電路由節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)。當(dāng)兩節(jié)點(diǎn)不是鄰居節(jié)點(diǎn)時(shí)，設(shè)置通信代價(jià)為無(wú)窮大。此處的關(guān)鍵路徑即為帶權(quán)有向圖中兩頂點(diǎn)間的最短路徑，由dijkstra算法可求得[10]。協(xié)調(diào)器將求得的每個(gè)持續(xù)電源路由節(jié)點(diǎn)到其它電源路由節(jié)點(diǎn)的最短路徑發(fā)送給對(duì)應(yīng)的持續(xù)電源節(jié)點(diǎn)記錄。

3.3 RACRS算法

ZigBee簇樹(shù)型網(wǎng)絡(luò)使用鄰居表引入虛連接，這樣既保持了網(wǎng)絡(luò)樹(shù)型結(jié)構(gòu)中的“地址-位置關(guān)系”，又可減少網(wǎng)絡(luò)中電池供電節(jié)點(diǎn)的能量消耗。FFD節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)時(shí)，如果下一跳節(jié)點(diǎn)不是目的結(jié)點(diǎn)，則轉(zhuǎn)發(fā)數(shù)據(jù)節(jié)點(diǎn)采用新路由算法查找下一跳路由節(jié)點(diǎn)。路由算法具體如下：

（1）查找路由節(jié)點(diǎn)S鄰居表。

（2）若鄰居表中有目的節(jié)點(diǎn)D，則直接轉(zhuǎn)發(fā)數(shù)據(jù)到目的節(jié)點(diǎn)D。

（3）若目的結(jié)點(diǎn)D是某個(gè)鄰居節(jié)點(diǎn)N的后代節(jié)點(diǎn)，則轉(zhuǎn)發(fā)數(shù)據(jù)到該鄰居節(jié)點(diǎn)N。

（4）查找節(jié)點(diǎn)的關(guān)鍵路徑，若目的節(jié)點(diǎn)是某條關(guān)鍵路徑的節(jié)點(diǎn)，則使用該關(guān)鍵路徑轉(zhuǎn)發(fā)數(shù)據(jù)。

（5）若查找失敗，則查找目的節(jié)點(diǎn)是否是關(guān)鍵路徑中節(jié)點(diǎn)的后代節(jié)點(diǎn)，若是則使用該關(guān)鍵路徑轉(zhuǎn)發(fā)數(shù)據(jù)。

（6）鄰居表中無(wú)合適的下一跳路由鄰居節(jié)點(diǎn)，則使用DAAM樹(shù)路由算法轉(zhuǎn)發(fā)數(shù)據(jù)[3]。

3.4算法的使用范圍與不足

RACRS算法用于持續(xù)電源路由節(jié)點(diǎn)占一定比例的ZigBee網(wǎng)絡(luò)，當(dāng)網(wǎng)絡(luò)中持續(xù)電源節(jié)點(diǎn)比例增加時(shí)，網(wǎng)絡(luò)中電池供電節(jié)點(diǎn)的路由節(jié)點(diǎn)負(fù)載相應(yīng)的減少，當(dāng)ZigBee網(wǎng)絡(luò)中存在由持續(xù)電源節(jié)點(diǎn)組成的關(guān)鍵路由路徑時(shí)，RACRS算法相比DAAM算法有明顯的電池節(jié)點(diǎn)耗能減少。

改進(jìn)的RACRS算法為了在網(wǎng)絡(luò)中通過(guò)由持續(xù)電源節(jié)點(diǎn)組成的路徑轉(zhuǎn)發(fā)數(shù)據(jù)，可能會(huì)增加到目的結(jié)點(diǎn)的路由跳數(shù)，同時(shí)使得網(wǎng)絡(luò)的局部流量增加。此外，如果ZigBee網(wǎng)絡(luò)中無(wú)恰當(dāng)?shù)挠沙掷m(xù)電源組成的關(guān)鍵路徑，則會(huì)使網(wǎng)絡(luò)中個(gè)別電池供電節(jié)點(diǎn)的轉(zhuǎn)發(fā)數(shù)據(jù)量增加，反而降低了網(wǎng)絡(luò)的生存時(shí)間。針對(duì)以上問(wèn)題將在下一步工作中深入研究。

4.算法分析與仿真

4.1 算法分析

改進(jìn)算法中，只需要在網(wǎng)絡(luò)結(jié)構(gòu)發(fā)生變化時(shí)，相應(yīng)的修改鄰居表中節(jié)點(diǎn)信息，此時(shí)網(wǎng)絡(luò)需要廣播結(jié)構(gòu)改變的信息，供其它節(jié)點(diǎn)記錄該變化，同時(shí)需要發(fā)送加入節(jié)點(diǎn)的信息到協(xié)調(diào)器，需要少量控制分組的開(kāi)銷。分析網(wǎng)絡(luò)結(jié)構(gòu)的圖1可知，在電源供電節(jié)點(diǎn)占有一定比例的網(wǎng)絡(luò)中，可在網(wǎng)絡(luò)中構(gòu)建多條關(guān)鍵路徑，通過(guò)改進(jìn)后的算法使用關(guān)鍵路徑轉(zhuǎn)發(fā)數(shù)據(jù)，使得數(shù)據(jù)包到達(dá)目的節(jié)點(diǎn)的路由中包含的電池供電節(jié)點(diǎn)的數(shù)目小于或等于傳統(tǒng)的樹(shù)路由算法，降低了網(wǎng)絡(luò)中電池供電節(jié)點(diǎn)的能量消耗。轉(zhuǎn)發(fā)數(shù)據(jù)包時(shí)經(jīng)過(guò)位置固定的持續(xù)電源傳感器節(jié)點(diǎn)，避免了移動(dòng)機(jī)器人在網(wǎng)絡(luò)中地址變化帶來(lái)的影響，可減少網(wǎng)絡(luò)中數(shù)據(jù)包的丟失，增強(qiáng)了網(wǎng)絡(luò)的穩(wěn)定性。

由于RACRS算法選擇一條包含電池供電節(jié)點(diǎn)最少的路由來(lái)轉(zhuǎn)發(fā)數(shù)據(jù)，部分路由可能會(huì)增加跳數(shù)，或使個(gè)別持續(xù)電源節(jié)點(diǎn)的數(shù)據(jù)流量增大，但在整個(gè)網(wǎng)絡(luò)中，采用含有鄰居表的RACRS算法，到達(dá)目的節(jié)點(diǎn)的平均路由跳數(shù)不超過(guò)傳統(tǒng)的樹(shù)路由算法[12]。

4.2 仿真結(jié)果分析

改進(jìn)算法通過(guò)仿真實(shí)驗(yàn)和傳統(tǒng)樹(shù)路由算法進(jìn)行了比較，重點(diǎn)是比較傳輸時(shí)網(wǎng)絡(luò)中電池供電節(jié)點(diǎn)的總能耗以及網(wǎng)絡(luò)的轉(zhuǎn)發(fā)數(shù)據(jù)丟包率。仿真結(jié)果證明了改進(jìn)算法的有效性。

仿真工具采用Omnett++4.2.2。網(wǎng)絡(luò)覆蓋面積為300×500，網(wǎng)絡(luò)中路由節(jié)點(diǎn)數(shù)為100，網(wǎng)絡(luò)協(xié)調(diào)器初始化Cm=6，Rm=4，Lm=5。仿真結(jié)果如圖3所示。在圖3中，分別列出了PSAR算法[2]和本文改進(jìn)的RACRS算法相對(duì)應(yīng)傳統(tǒng)的樹(shù)路由算法，網(wǎng)絡(luò)中電池供電節(jié)點(diǎn)的總耗能減少率。由圖可知改進(jìn)的算法在引入鄰居表記錄，在路由的過(guò)程中考慮了持續(xù)電源節(jié)點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn)，同時(shí)選擇局部最小路由跳數(shù)的路徑進(jìn)行數(shù)據(jù)傳輸時(shí)，減少了網(wǎng)絡(luò)中電池供電節(jié)點(diǎn)的能量消耗，能夠最大化網(wǎng)絡(luò)的生存時(shí)間。

如3.2中所述，網(wǎng)絡(luò)中有新的持續(xù)電源供電節(jié)點(diǎn)加入時(shí)，節(jié)點(diǎn)發(fā)送信息到協(xié)調(diào)器，協(xié)調(diào)器將計(jì)算后的關(guān)鍵路徑再發(fā)送給相應(yīng)節(jié)點(diǎn)。在關(guān)鍵路徑和移動(dòng)機(jī)器人網(wǎng)絡(luò)地址改變的時(shí)間段內(nèi)，轉(zhuǎn)發(fā)到原目的地址的數(shù)據(jù)包會(huì)丟失。圖4說(shuō)明了使用新算法后對(duì)網(wǎng)絡(luò)丟包率的影響，實(shí)驗(yàn)結(jié)果表明使用新算法的網(wǎng)絡(luò)丟包率在0.1%上下，小于網(wǎng)絡(luò)丟包率的平均值。

5.結(jié)束語(yǔ)

本文提出了一種適用于分布式異構(gòu)集群機(jī)器人系統(tǒng)的ZigBee網(wǎng)絡(luò)路由算法——RACRS算法，當(dāng)網(wǎng)絡(luò)中電池供電節(jié)點(diǎn)的鄰居節(jié)點(diǎn)在一條持續(xù)電源節(jié)點(diǎn)組成的關(guān)鍵路徑中時(shí)，F(xiàn)FD節(jié)點(diǎn)可通過(guò)該鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)，從而減少電池供電節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)的能耗，算法避免了動(dòng)態(tài)查找路由的額外通信開(kāi)銷和對(duì)樹(shù)路由的影響。理論分析和仿真結(jié)果顯示，與DAAM算法相比，在合適的ZigBee網(wǎng)絡(luò)中，RACRS算法在控制開(kāi)銷和減少網(wǎng)絡(luò)能耗，延長(zhǎng)網(wǎng)絡(luò)生存等方面的性能表現(xiàn)整體更優(yōu)。RACRS算法對(duì)未來(lái)的分布式異構(gòu)集群機(jī)器人系統(tǒng)的網(wǎng)絡(luò)構(gòu)建具有指導(dǎo)意義。

參考文獻(xiàn)：

[1]ZigBee Standards Organization. （2006）[S]. ZigBeespeci?-cation.

[2]Metin， T.， Ibrahim，K..PSAR：power-source-awarerouting in ZigBee Networks[J].Wireless Networks.（2012），18（6），635-651.

[3]Cho， D. H.， Song， J. H.，& Han， K. J. （2006）. An adaptive energysaving mechanism for the IEEE 802.15.4 lr-wpan[J]. Lecture Notesin Computer Science， 4138， 38–46

[4]Puccinelli， D.，Sifakis， E.，&Haenggi， M. （2006）. A cross-layerapproach to energy balancing in wireless sensor networks[J].Lecture Notes in Control and Information Sciences， 331， 309–324

[5]Boughanmi， N.，& Song， Y. （2008） A new routing metric forsatisfying both energy and delay constraints in wireless sensornetworks[J]. Journal of Signal Processing Systems， 51（2）， 137–143.

[6] P. Buck， T. Schmitt，and M. Beetz： Reliable multi-robot coordination using minimal communication and neural prediction[J].Springer-Verlag. Pages 36-51，2001.

[7] P. Iocchi， D. Nardi， M. Piaggio， and A. Sgorbissa： Distributed coordination in heterogeneous multi-robot systems[J]. Kluwer Academic. Pages 155-168，2003.

[8] I. Mas， S. Li， J. Acain， and C. Kitts： Entrapment/escorting and patrolling missions in multi-robot cluster space control[J].IEEE Press. Pp.5855-5861，2009.

[9] J. Mataric，S.Sukhatme， and H. Ostergaard： Multi-robot task allocation in uncertain environments[J].Kluwer Academic.pp. 255-263，2003.

[10]Yong Deng，Yuxin Chen，Yajuan Zhang， and S. Mahadevan. Short communication：FuzzyDijkstra algorithm for shortest path problem under uncertain environment[J].Elsevier Science. pp. 1231-1237，2012.

[11]李智軍，周曉，呂恬生.基于群體協(xié)作的分布式多機(jī)器人通信系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].機(jī)器人.2000，22（4）：300-304.

[12]吳軍，徐昕，連傳強(qiáng)，賀漢根.協(xié)作多機(jī)器人系統(tǒng)研究進(jìn)展綜述[J].智能系統(tǒng)學(xué)報(bào).2011，6（1）：13-27.

[13]戚劍超，魏臻.ZigBee樹(shù)型路由算法的改進(jìn)[J].合肥工業(yè)大學(xué)學(xué)報(bào).2010，33（4）：529-537.

基金項(xiàng)目：西南科技大學(xué)城市學(xué)院校級(jí)科研項(xiàng)目支助，編號(hào)：XCY14Z12。

作者簡(jiǎn)介：李躍，（1986.11-），男，漢，四川簡(jiǎn)陽(yáng)人，碩士，研究方向：節(jié)能技術(shù)、人工智能。