文獻(xiàn)標(biāo)識(shí)碼: A
文章編號(hào): 0258-7998(2015)01-0078-04
0 引言
為了滿足低功耗,、低成本的需求,短距離通信ZigBee技術(shù)應(yīng)運(yùn)而生,,它是一種基于802.15.4的技術(shù)提案[1][2],。ZigBee網(wǎng)絡(luò)的不同節(jié)點(diǎn)通過網(wǎng)絡(luò)協(xié)調(diào)器來完成各個(gè)節(jié)點(diǎn)的協(xié)同工作[3]。ZigBee中的分布式地址分配機(jī)制(Distributed Address Assignment Mechanism,,DAAM)算法具有簡(jiǎn)單以及包含“地址-位置”關(guān)系等優(yōu)點(diǎn),。但是隨著網(wǎng)絡(luò)節(jié)點(diǎn)的增加,DAAM算法就會(huì)顯示出它的弱點(diǎn),,這時(shí)有些節(jié)點(diǎn)因?yàn)榉峙洳坏降刂窡o法加入網(wǎng)絡(luò)而成為孤立節(jié)點(diǎn)[4],。
為了減少網(wǎng)絡(luò)中的孤立節(jié)點(diǎn),目前已開展很多該方面的研究,。由于節(jié)點(diǎn)密度以及網(wǎng)絡(luò)深度等原因?qū)?huì)造成網(wǎng)絡(luò)地址的不足,,但是此時(shí)有些路由節(jié)點(diǎn)仍有未使用的地址,這時(shí)可以向這些有剩余地址的路由節(jié)點(diǎn)借用地址來達(dá)到減少孤立節(jié)點(diǎn)數(shù)量的目的,,這一思想在文獻(xiàn)[5-6]有具體體現(xiàn),。文獻(xiàn)[7-9]提出了進(jìn)行地址擴(kuò)展的思想。文獻(xiàn)[10]提出了一種基于最小跳數(shù)的按需分配的地址分配算法。該方法首先由sink節(jié)點(diǎn)以洪泛方式向全網(wǎng)廣播最小跳數(shù)的構(gòu)建消息,,從而使每一個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)都有到sink節(jié)點(diǎn)的最小跳數(shù),,然后根據(jù)已構(gòu)建的最小跳數(shù)樹獲取地址。另外文獻(xiàn)[11]提出了一種動(dòng)態(tài)參數(shù)的分配算法,,該方法可以減少孤立節(jié)點(diǎn)數(shù)量,,但是增加了網(wǎng)絡(luò)開銷,并且擴(kuò)展性不強(qiáng),,當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)很多時(shí),,增加了組網(wǎng)時(shí)間。
本文提出了一種基于動(dòng)態(tài)參數(shù)的按需可擴(kuò)展地址分配算法(AP-SAAM),,同時(shí)給出了改進(jìn)的路由算法,,使其兼容cluster-tree路由協(xié)議。
本文的貢獻(xiàn)主要如下:
(1)提出了一種基于動(dòng)態(tài)參數(shù)的按需可擴(kuò)展地址分配算法,,可以根據(jù)已知網(wǎng)絡(luò)參數(shù)來決定擴(kuò)展的地址大小,,同時(shí)兼容原DAAM算法。
(2)可以根據(jù)網(wǎng)絡(luò)狀態(tài)進(jìn)行參數(shù)調(diào)整以及擴(kuò)展次數(shù),,具有很強(qiáng)的擴(kuò)展性,。
(3)給出了改進(jìn)的路由算法,且與cluster-tree路由協(xié)議兼容,。
1 系統(tǒng)模型
本文對(duì)地址的擴(kuò)展思想為:首先計(jì)算出DAAM定義的地址空間,,然后得出可以表示這些地址空間的最小比特位數(shù)a0,然后把剩余的地址分成Rm段,,如果不進(jìn)行地址擴(kuò)展,,就使用第一段地址空間;如果進(jìn)行一次擴(kuò)展,,則使用第二段地址空間,;以此類推,直到網(wǎng)絡(luò)地址擴(kuò)展完,,每一段地址所占的比特位數(shù)如圖1所示,。
其中,ai表示各個(gè)地址塊所占用的比特位數(shù),。
具體地址段的分配方式如下:
根據(jù)已知條件可以得出DAAM分配的最大空間Am,,可用式(1)計(jì)算:
Am=Cskip(0)×Rm+Cm-Rm(1)
又因?yàn)?/p>
為了考慮一般性,我們只考慮Rm>1的情況,,此時(shí)有:
整理得:
所以得出可表示Am的最小比特位數(shù)a:
a=min{a|2a≥Am}(5)
進(jìn)而得出每一塊地址段所占的比特位數(shù)為:
其中i表示地址塊數(shù),,即擴(kuò)展的次數(shù)。
假設(shè)O,、R分別代表普通設(shè)備和路由設(shè)備,,N1,,N2分別表示沒有獲得網(wǎng)絡(luò)地址的普通節(jié)點(diǎn)以及路由節(jié)點(diǎn)的個(gè)數(shù),Li表示第i個(gè)網(wǎng)絡(luò)設(shè)備的深度,,Oam表示地址為a的普通節(jié)點(diǎn)的深為m,,Rbm表示地址為b的路由節(jié)點(diǎn)的深度為n,,則新的網(wǎng)絡(luò)參數(shù)為:
然后進(jìn)行第一次地址擴(kuò)展,,這時(shí)協(xié)調(diào)器只會(huì)給個(gè)路由節(jié)點(diǎn)分配擴(kuò)展后的地址塊,如果第一次擴(kuò)展后仍有孤立節(jié)點(diǎn),,然后再進(jìn)行第二次地址擴(kuò)展,,以此推論,直至整個(gè)地址空間用完,,分配方法如式(8):
且Nd≤,,其中Achildren為擴(kuò)展地址,i表示進(jìn)行地址擴(kuò)展的次數(shù),,Nd表示第i次擴(kuò)展時(shí)路由節(jié)點(diǎn)數(shù),。
得到地址塊的路由節(jié)點(diǎn)可以再次進(jìn)行地址分配,分配方式仍按照原DAAM算法,,參數(shù)為:,。其可分配的地址大小為,其中i表示擴(kuò)展次數(shù),,且1≤i≤Rm,。
2 基于動(dòng)態(tài)參數(shù)的按需可擴(kuò)展地址分配算法
2.1 AP-SAAM算法步驟
(1)DAAM算法:
初始化:網(wǎng)絡(luò)協(xié)調(diào)器把自己的地址設(shè)置為0,網(wǎng)絡(luò)參數(shù)為L(zhǎng)m,、Rm和Cm,。
地址請(qǐng)求:節(jié)點(diǎn)向其鄰居表中未被標(biāo)記的潛在父節(jié)點(diǎn)發(fā)出入網(wǎng)請(qǐng)求(當(dāng)有多個(gè)時(shí)隨機(jī)選擇);如果未收到答復(fù),,則依次向其他未標(biāo)記的節(jié)點(diǎn)發(fā)出入網(wǎng)請(qǐng)求,,如果仍未得到回復(fù),則向協(xié)調(diào)器發(fā)送第一次地址擴(kuò)展請(qǐng)求,,同時(shí)轉(zhuǎn)向步驟(3),,如果仍沒有獲得地址,發(fā)送第二次地址擴(kuò)展請(qǐng)求,,以此類推,。
地址分配:地址為Aparent的路由節(jié)點(diǎn)收到入網(wǎng)請(qǐng)求時(shí),首先查詢自己的地址空間,,如果有地址,,則按照原DAAM算法進(jìn)行分配。
(2)地址擴(kuò)展:
網(wǎng)絡(luò)協(xié)調(diào)器收到借用地址請(qǐng)求后,,根據(jù)式(6)對(duì)網(wǎng)絡(luò)進(jìn)行地址塊的劃分,;然后按照式(7)計(jì)算,。
(3)擴(kuò)展地址分配:
此時(shí)網(wǎng)絡(luò)協(xié)調(diào)器進(jìn)行第一次地址擴(kuò)展,根據(jù)式(8)對(duì)申請(qǐng)的個(gè)路由節(jié)點(diǎn)進(jìn)行地址的分配(如有剩余,,留作下次使用),。網(wǎng)絡(luò)協(xié)調(diào)器需要維護(hù)這些路由節(jié)點(diǎn)的路由表,得到地址塊的路由節(jié)點(diǎn)向其潛在父節(jié)點(diǎn)發(fā)出作為其子節(jié)點(diǎn)的請(qǐng)求,,并上報(bào)自己的網(wǎng)絡(luò)地址,,同時(shí)標(biāo)記自己的網(wǎng)絡(luò)深度為其父節(jié)點(diǎn)深度加1,用Lj表示,,當(dāng)此路由節(jié)點(diǎn)再次收到節(jié)點(diǎn)的入網(wǎng)請(qǐng)求時(shí),,則按照式(9)進(jìn)行地址的分配:
其中,Aparent為父節(jié)點(diǎn)地址,,Li為申請(qǐng)加入的節(jié)點(diǎn)深度,,且滿足Li-Lj≤。
2.2 路由算法改進(jìn)
經(jīng)過擴(kuò)展地址分配后,,可能的網(wǎng)絡(luò)地址結(jié)構(gòu)如圖2所示,,其中A、B為獲得擴(kuò)展地址的節(jié)點(diǎn)區(qū)域,,C為按照原DAAM算法得到地址的節(jié)點(diǎn)區(qū)域,。對(duì)此,源節(jié)點(diǎn)以及目的節(jié)點(diǎn)的地址類型就會(huì)有四種情況,,如表1所示,。
假設(shè)源節(jié)點(diǎn)網(wǎng)絡(luò)地址為A,深度為d,;目的節(jié)點(diǎn)網(wǎng)絡(luò)地址為D,。首先判斷式(10)、(11)是否成立
如果式(10)和式(11)都成立,,則執(zhí)行步驟1,;如果式(10)成立,式(11)不成立,,則執(zhí)行步驟2,;如果式(10)不成立,式(11)成立,,則執(zhí)行步驟3,;如果式(10)不成立,式(11)不成立,,則執(zhí)行步驟4,。
步驟1:首先判斷邏輯表達(dá)式(12)是否成立,其中參數(shù)為L(zhǎng)m,、Rm,、Cm,。
A<D<A+Cskip(d-1)(12)
如果不成立,則交給A的父節(jié)點(diǎn),;如果成立,,且D是A的一跳鄰居節(jié)點(diǎn),則修改下一跳地址Ne=D,,若不是一跳鄰居節(jié)點(diǎn),,則通過式(13)計(jì)算下一跳地址,其中參數(shù)為L(zhǎng)m,、Rm,、Cm,。
其中0≤d≤Lm,。
步驟2:首先判斷邏輯表達(dá)式(14)是否成立:
其中Achildren為節(jié)點(diǎn)A的子節(jié)點(diǎn)。
如果成立,,則表示目的節(jié)點(diǎn)屬于節(jié)點(diǎn)A的子節(jié)點(diǎn)的擴(kuò)展地址域,,然后修改下一跳地址Ne=Achildren;如果不成立,,則修改下一跳地址為A的父節(jié)點(diǎn)即:Ne=Aparpent,。
步驟3:修改下一跳地址為A的父節(jié)點(diǎn)即:Ne=Aparpent。
步驟4:首先判斷邏輯表達(dá)式(12)是否成立,,其中參數(shù)為,。
如果不成立,則交給A的父節(jié)點(diǎn),;如果成立,,若D是A的一跳鄰居節(jié)點(diǎn),則修改下一跳地址Ne=D,,若不是一跳鄰居節(jié)點(diǎn),,則通過式(13)計(jì)算下一跳地址,其中參數(shù)為,,且0≤d≤,。
綜上所述,修改的路由協(xié)議能夠滿足地址分配算法,。
3 算法仿真
把DAAM,、EDAA-BA[5]、RBAC[9]作為比較對(duì)象,,通過OPNET仿真來觀察它們?cè)谛阅芊矫娴牟町?。其中網(wǎng)絡(luò)參數(shù)分別設(shè)為Cm=4,Rm=2,,Lm=15,。
圖3表示的是平均地址分配成功率與網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)之間的關(guān)系,。從圖中可以看出,EDAA-BA,、RBAC以及AP-SAAM的分配成功率要高于DAAM,,且AP-SAAM最高,特別是隨著節(jié)點(diǎn)數(shù)的增加,,AP-SAAM的性能更優(yōu),,這是因?yàn)锳P-SAAM能夠根據(jù)網(wǎng)絡(luò)狀況實(shí)施地址擴(kuò)展,從而能夠分配更多的地址,,進(jìn)而提高節(jié)點(diǎn)入網(wǎng)的概率,。
圖4表示的是平均分配耗時(shí)與網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)之間的關(guān)系,有圖可知,,EDAA-BA,、RBAC以及AP-SAAM都比DAAM平均耗時(shí)大,其中EDAA-BA耗時(shí)最大,,這是因?yàn)槠洳粩噙M(jìn)行借用地址花費(fèi)了大量的時(shí)間,,這一現(xiàn)象隨著節(jié)點(diǎn)的增加、網(wǎng)絡(luò)結(jié)構(gòu)的復(fù)雜變得更加明顯,,RBAC和AP-SAAM的平均耗時(shí)相當(dāng),。
圖5表示的是平均路由跳數(shù)與網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)之間的關(guān)系,其中路由跳數(shù)表示節(jié)點(diǎn)到其潛在鄰居節(jié)點(diǎn)的跳數(shù),。從圖中可以看出RBAC算法和AP-SAAM算法相當(dāng),,而EDAA-BA要優(yōu)于其它三種算法,這是因?yàn)镋DAA-BA算法在進(jìn)行借用地址時(shí)專門考慮了迂回問題,。
4 結(jié)束語
本文提出了一種基于動(dòng)態(tài)參數(shù)的按需可擴(kuò)展地址分配算法,,當(dāng)?shù)刂烦渥銜r(shí),使用DAAM算法,;當(dāng)出現(xiàn)地址不足時(shí),,對(duì)剩余地址空間進(jìn)行擴(kuò)展,根據(jù)已知參數(shù)對(duì)剩余地址塊靈活的分配,,同時(shí)根據(jù)網(wǎng)絡(luò)狀況進(jìn)行一次或者多次擴(kuò)展,,從而很好地解決了孤立節(jié)點(diǎn)問題。
參考文獻(xiàn)
[1] Huang Yu-Kai,,Pang,,Ai-Chun,Hsiu,,Pi-Cheng,,et al.Distubuted throughput optimization for ZigBee cluster-treeNetworks[J].IEEE Computer Society,2012(5),,23(3):513-520.
[2] 寧炳武,,劉軍民.基于CC2430的Zigbee網(wǎng)絡(luò)節(jié)點(diǎn)設(shè)計(jì)[J].電子技術(shù)應(yīng)用,,2008(3):95-99.
[3] Natalia C Fer,Marcelo D D Mor,,Otto C M B Dua.AnEfficient and Robust Addressing Protocol for Node Auto-configuration in Ad Hoc Networks[J].IEEE/ACM Transac-tions on Networking,,2013(4),3(21):845-856.
[5] KARAPISTROLI E,,PAVLIDOU F N,,GRAGOPOULOS I,etal.An overview of the IEEE 802.15.4a standard[J].IEEECommunications Magazine,,2010,,48(1):47-53.
[6] 姚玉坤,陳永超,,李鵬翔,,等.ZigBee網(wǎng)絡(luò)中基于借地址的高效分布式地址分配算法[J].重慶大學(xué)學(xué)報(bào),2012(8),,35(8):151-158.
[7] Natalia C F,,Marcelo D D M,,Otto Carlos M B D.AnEfficient and Robust Addressing Protocol for Node Autoconfiguration in Ad Hoc Networks[J].IEEE/ACM Transac-tions on Networking, Jun.2013,,vol.21:845-856.
[8] 任智,李鵬翔,,姚玉坤,,等.基于分段的ZigBee網(wǎng)絡(luò)按需可擴(kuò)展地址分配算法[J].通信學(xué)報(bào),2012,,33(5):131-137.
[9] Li-Hsing Yen,,Wei-Ting Tsai.The room shortage problemof three-based Zigbee/IEEE 802.15.4 wireless networks[J].Computer Communication,2010(33):454-462.
[10] 胡義,,文建國(guó),,羅娟.時(shí)間驅(qū)動(dòng)型傳感器網(wǎng)絡(luò)地址分配算法研究[J].計(jì)算機(jī)工程與應(yīng)用,2009,,45(33):83-85.
[11] Shu-Chiung Hu,,Cheng-Kuan Lin,Yu-Chee Tseng.Automatic parameter selection for the ZigBee distributedaddress assignment mechanism[C].2013 IEEE 24th Inter-national Symposium on Personal, Indoor and Mobile RadioCommunications: Mobile and Wireless Networks, 8-11Sept 2013, London, United Kingdom,,2013:2062-2066.