董友俊

關(guān)鍵詞：ZigBee;隨機(jī)地址分配;地址沖突;NS2

1引言

ZigBee技術(shù)是在IEEE802.15.4無線通信協(xié)議標(biāo)準(zhǔn)上建立的近距離無線組網(wǎng)通信技術(shù)，具有近距離、自組織、低功耗、低復(fù)雜度等特點(diǎn)[1]，主要用于近距離低速率電子設(shè)備之間的數(shù)據(jù)傳輸以及典型的有周期性數(shù)據(jù)、間歇性數(shù)據(jù)傳輸需求的場景，包括汽車工業(yè)、家庭自動化、遙控遙測、定位系統(tǒng)等領(lǐng)域。

ZigBee技術(shù)的地址分配有兩種機(jī)制，分別是分布式地址分配機(jī)制（Distributed Address AssignmentMechanism，簡稱DAAM）和隨機(jī)地址分配機(jī)制（Stochastic Address Assignment Mechanism，簡稱SAAM）。DAAM強(qiáng)調(diào)“地址——位置”的對應(yīng)關(guān)系，更確切地說是“子節(jié)點(diǎn)地址——父節(jié)點(diǎn)地址”的對應(yīng)關(guān)系，該對應(yīng)關(guān)系是樹狀路由的基礎(chǔ)。而SAAM采用邏輯上更簡單的隨機(jī)方式分配地址，該機(jī)制對應(yīng)的是網(wǎng)狀路由[2]。

現(xiàn)有的隨機(jī)地址分配算法（簡稱SAAM算法）雖能完成節(jié)點(diǎn)的入網(wǎng)地址分配工作，但時間消耗和通信開銷較大，對于采用電池供電的ZigBee設(shè)備而言，顯然是技術(shù)弊端。因此，本文在深入研究SSAM算法的基礎(chǔ)上，提出了新型的基于鄰居確認(rèn)的隨機(jī)地址分配算法（Stochastic Address Assignment Mechanism basedon the Confirm of the Neighbors，簡稱SAAMCN），以減少時間和通信開銷，同時對重復(fù)地址進(jìn)行有效清理。

本文的主要工作包括如下四個方面：（1）研究ZigBee現(xiàn)有的隨機(jī)地址分配算法SAAM并分析其優(yōu)缺點(diǎn);（2）針對SAAM的缺陷提出新型掃描算法SAAMCN;（3）將SAAM和SAAMCN在NS2網(wǎng)絡(luò)仿真平臺上實(shí)現(xiàn);（4）對SAAM和SAAMCN進(jìn)行多指標(biāo)多場景的測試，驗(yàn)證SAAMCN算法的有效性。

2SAAM算法分析

SAAM算法的邏輯是：從協(xié)調(diào)器開始，每個父節(jié)點(diǎn)都隨機(jī)從65533個地址中為子節(jié)點(diǎn)分配地址，而不考慮子節(jié)點(diǎn)的類型。因?yàn)槎痰刂房偣?5536個，其中有3個（分別是Ox0000，OxFFFE，OxFFFF）不參與地址分配，故地址池大小為65533。父節(jié)點(diǎn)每隨機(jī)出一個地址，都要去自己的子地址列表中查詢，以確認(rèn)該地址是否已經(jīng)分配過。若是，則重新隨機(jī)，否則將該網(wǎng)絡(luò)地址通過入網(wǎng)應(yīng)答命令傳遞給子節(jié)點(diǎn)。子節(jié)點(diǎn)在收到入網(wǎng)應(yīng)答命令之后，需要向全網(wǎng)廣播“設(shè)備聲明”（Device Announce），其中包含剛獲得的網(wǎng)絡(luò)地址和64位長地址。其他設(shè)備收到該聲明之后，首先判斷自己的網(wǎng)絡(luò)地址與該聲明中的網(wǎng)絡(luò)地址是否一致，若是，則以廣播方式發(fā)送“地址沖突”（Address Conflict），并且自行重新隨機(jī)選擇網(wǎng)絡(luò)地址，同樣需要發(fā)送“設(shè)備聲明”，否則繼續(xù)轉(zhuǎn)廣播“設(shè)備聲明”。節(jié)點(diǎn)收到“地址沖突”的通告之后，自行重新隨機(jī)選擇網(wǎng)絡(luò)地址，繼續(xù)重復(fù)上述流程。節(jié)點(diǎn)在收到設(shè)備聲明之后，首先要判斷此前是否接收過，若已接收，則直接忽略。還需要注意若節(jié)點(diǎn)發(fā)現(xiàn)網(wǎng)絡(luò)地址沖突，即既要發(fā)送地址沖突通告，還要通過自行隨機(jī)的方式重新給自己分配網(wǎng)絡(luò)地址，最后還需廣播設(shè)備聲明將新獲得的網(wǎng)絡(luò)地址通知全網(wǎng)。

地址沖突通告中包含網(wǎng)絡(luò)地址、64位長地址、廣播序列號。這些信息在最初節(jié)點(diǎn)發(fā)送設(shè)備聲明時設(shè)置，此后的轉(zhuǎn)發(fā)節(jié)點(diǎn)只會讀取其中的信息并記錄在本地的聲明發(fā)送列表（或沖突發(fā)送列表），不會修改其中的值。只有最初發(fā)送設(shè)備聲明的節(jié)點(diǎn)收到地址沖突通告，才會在重新選擇網(wǎng)絡(luò)地址之后將廣播序列號加一，重復(fù)此前廣播。廣播序列號的作用除了避免無窮廣播之外，還可以便于節(jié)點(diǎn)識別這是來自某個節(jié)點(diǎn)的第幾個廣播包。

通過以上分析可知SAAM算法具有以下優(yōu)點(diǎn)：（1）降低了欲入網(wǎng)節(jié)點(diǎn)選擇潛在父節(jié)點(diǎn)的邏輯復(fù)雜度，因此減輕了掃描階段的壓力。而且，潛在父節(jié)點(diǎn)采用隨機(jī)方式獲得網(wǎng)絡(luò)地址，操作方便;（2）由于不存在地址池枯竭的問題，節(jié)點(diǎn)的入網(wǎng)也就沒有靜態(tài)和動態(tài)之分，所以也就不用考慮借地址等問題，欲入網(wǎng)節(jié)點(diǎn)都能分到地址;（3）潛在父節(jié)點(diǎn)得出網(wǎng)絡(luò)地址不需要計(jì)算，因此不需要R。等參數(shù)。這就意味著在DAAM機(jī)制中，與這些參數(shù)對應(yīng)的限制在SAAM機(jī)制中都不存在。在一些不能提供等參數(shù)值的場合下，SAAM算法非常合適。

SAAM算法把壓力集中到了獲得網(wǎng)絡(luò)地址之后，因?yàn)樽庸?jié)點(diǎn)要進(jìn)行全網(wǎng)廣播來避免地址沖突，并對沖突的地址進(jìn)行處理。從上述對設(shè)備聲明和地址沖突通告的處理邏輯上，我們不難發(fā)現(xiàn)，SAAM算法以下明顯的缺點(diǎn)：（1）子節(jié)點(diǎn)獲得網(wǎng)絡(luò)地址后都需要進(jìn)行全網(wǎng)廣播設(shè)備聲明，即已入網(wǎng)節(jié)點(diǎn)都要為剛?cè)刖W(wǎng)節(jié)點(diǎn)轉(zhuǎn)發(fā)一次設(shè)備聲明，除非該節(jié)點(diǎn)的網(wǎng)絡(luò)地址與剛?cè)刖W(wǎng)的節(jié)點(diǎn)沖突，但沖突的情況更糟糕，因?yàn)闆_突就需要廣播地址沖突通告，節(jié)點(diǎn)重新選擇網(wǎng)絡(luò)地址之后還需要廣播，又加重了整個網(wǎng)絡(luò)的負(fù)擔(dān)。而且，這種廣播是每個節(jié)點(diǎn)剛?cè)刖W(wǎng)是都會促發(fā)的，顯然通信開銷很大，耗時很長;（2）在出現(xiàn)地址沖突時，SAAM算法要求重復(fù)的地址都要重新選擇，但并未考慮原網(wǎng)絡(luò)地址在網(wǎng)絡(luò)中存在過，在部分節(jié)點(diǎn)的路由表、鄰居表等屬性表中都有記錄，SAAM算法并未對這些記錄進(jìn)行有效的處理。

3SAAMCN算法

針對SAAM算法存在的問題，本文提出基于鄰居確認(rèn)的隨機(jī)地址分配算法-SAAMCN，可以看作是對SAAM算法的優(yōu)化或者補(bǔ)充。

首先，對于廣播成本高的問題，SAAMCN算法采用將廣播限制在兩跳范圍內(nèi)的方法來解決。這就從根本上解決了成本問題，能夠明顯減少廣播的通信開銷，節(jié)省時間。但必須指出的是，該算法在網(wǎng)絡(luò)規(guī)模很大的情況下效果不太理想，因?yàn)殡S著網(wǎng)絡(luò)規(guī)模的擴(kuò)大，兩跳廣播覆蓋的范圍占全網(wǎng)的比率比較小，雖然通信開銷和時間消耗控制在低位，但是避免地址沖突的功能就受限制，因此該算法的適用范圍是中等及以下規(guī)模的網(wǎng)絡(luò)[3]。

SAAMCN算法在節(jié)點(diǎn)接到設(shè)備聲明之后，不僅要跟本節(jié)點(diǎn)的網(wǎng)絡(luò)地址比較，還要跟本地的路由表、鄰居表等屬性表中記錄的節(jié)點(diǎn)網(wǎng)絡(luò)地址比較，只要查到有設(shè)備聲明中網(wǎng)絡(luò)地址的記錄，就可確定該網(wǎng)絡(luò)地址是重復(fù)的，直接發(fā)送地址沖突通告即可，因?yàn)樵撏ǜ娌⒎且欢ㄒW(wǎng)絡(luò)地址重復(fù)的節(jié)點(diǎn)才能發(fā)送。

在出現(xiàn)地址沖突后，擁有該網(wǎng)絡(luò)地址的節(jié)點(diǎn)都將會修改地址，則網(wǎng)絡(luò)中其他節(jié)點(diǎn)關(guān)于該網(wǎng)絡(luò)地址的記錄就無效了，因此SAAMCN算法在節(jié)點(diǎn)收到地址沖突通告之后，如果本節(jié)點(diǎn)的短地址跟正在進(jìn)行設(shè)備聲明的短地址不相同（此類節(jié)點(diǎn)稱為第三方節(jié)點(diǎn)），則查詢本地的各種屬性表，若發(fā)現(xiàn)通告中的短地址記錄，則刪除相應(yīng)的信息，以解決地址變更時節(jié)點(diǎn)信息未清理的問題。

通過對SAAM算法的一系列改進(jìn)，不難發(fā)現(xiàn)SAAMCN算法的已具有如下優(yōu)勢：（1）同樣具有邏輯復(fù)雜度低、地址池不枯竭、不受參數(shù)限制等優(yōu)勢，即SAAMCN算法完全保留了SAAM算法的優(yōu)勢;（2）采用兩跳廣播代替SAAM算法的全網(wǎng)廣播，有效地控制了通信開銷和時間消耗;（3）查詢屬性表確認(rèn)地址沖突的策略擴(kuò)大了設(shè)備通告的實(shí)際范圍，因此彌補(bǔ)了兩跳廣播造成搜索范圍有限的劣勢;（4）特有的沖突地址信息清理機(jī)制保證了已失效的地址信息不會繼續(xù)存在于網(wǎng)絡(luò)中，保障了網(wǎng)絡(luò)的正常運(yùn)行。

4模擬仿真及數(shù)據(jù)分析

為了驗(yàn)證SAAMCN算法的有效性，本文將其在NS2上進(jìn)行仿真實(shí)現(xiàn)并做相應(yīng)的測試。本文模擬仿真所采用的NS2是開源免費(fèi)的仿真軟件，其具有較高的執(zhí)行效率、豐富的構(gòu)件庫、靈活的配置，良好的可擴(kuò)展性和開放性等優(yōu)點(diǎn)[4]。同時，將SAAM算法也在NS2上模擬實(shí)現(xiàn)并測試，將兩組算法的測試數(shù)據(jù)進(jìn)行對比，以增強(qiáng)說服力。

本文設(shè)置了7套模擬仿真場景，具體如表1所列。在200個節(jié)點(diǎn)以下的場景中，SAAMCN能保證0.050-/0以下的重復(fù)率，特別是150個及以下節(jié)點(diǎn)的場景，重復(fù)的情況基本上統(tǒng)計(jì)不到，所以SAAMCN算法的非常適用于200個節(jié)點(diǎn)以下的場景。在現(xiàn)實(shí)生活中，小規(guī)模ZigBee網(wǎng)絡(luò)大約是十幾個節(jié)點(diǎn)，中等規(guī)模網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)約幾十或者上百個，因此SAAMCN算法在中小規(guī)模網(wǎng)絡(luò)中表現(xiàn)優(yōu)異。

圖2和圖3顯示，SAAMCN算法時間消耗和通信開銷都遠(yuǎn)低于SAAM算法。

綜合比較三組數(shù)據(jù)，發(fā)現(xiàn)在網(wǎng)絡(luò)規(guī)模低于200個節(jié)點(diǎn)時，SAAMCN的重復(fù)率和SAAM很接近，但通信開銷和時間消耗遠(yuǎn)遠(yuǎn)低于SAAM，因此SAAMCN算法具有明顯優(yōu)勢。在網(wǎng)絡(luò)規(guī)模大于200個節(jié)點(diǎn)時，SAAMCN的時間消耗和通信開銷遠(yuǎn)低于SAAM.重復(fù)率高于SAAM。因此，得出結(jié)論：在網(wǎng)絡(luò)規(guī)模不是很大時，SAAMCN算法在總體指標(biāo)上優(yōu)于SAAMCN算法。

5結(jié)束語

本文在對ZigBee網(wǎng)絡(luò)隨機(jī)地址分配機(jī)制進(jìn)行深入研究的基礎(chǔ)上，分析出現(xiàn)有隨機(jī)地址分配算法SAAM會造成較大的通信開銷和時間消耗，且未能有效清理重復(fù)地址信息的問題，并提出了新型隨機(jī)地址分配算法SAAMCN。該算法對廣播的跳數(shù)做出限制，并充分利用屬性表來清理重復(fù)地址信息，以解決上述問題。最后，通過在NS2仿真平臺上的模擬測試，證明SAAMCN在其適用范圍內(nèi)的優(yōu)越性。