0 引言

　　為了滿足低功耗、低成本的需求，短距離通信ZigBee技術應運而生，它是一種基于802.15.4的技術提案[1][2]。ZigBee網絡的不同節(jié)點通過網絡協調器來完成各個節(jié)點的協同工作[3]。ZigBee中的分布式地址分配機制(Distributed Address Assignment Mechanism，DAAM)算法具有簡單以及包含“地址-位置”關系等優(yōu)點。但是隨著網絡節(jié)點的增加，DAAM算法就會顯示出它的弱點，這時有些節(jié)點因為分配不到地址無法加入網絡而成為孤立節(jié)點[4]。

　　為了減少網絡中的孤立節(jié)點，目前已開展很多該方面的研究。由于節(jié)點密度以及網絡深度等原因將會造成網絡地址的不足，但是此時有些路由節(jié)點仍有未使用的地址，這時可以向這些有剩余地址的路由節(jié)點借用地址來達到減少孤立節(jié)點數量的目的，這一思想在文獻[5-6]有具體體現。文獻[7-9]提出了進行地址擴展的思想。文獻[10]提出了一種基于最小跳數的按需分配的地址分配算法。該方法首先由sink節(jié)點以洪泛方式向全網廣播最小跳數的構建消息，從而使每一個網絡節(jié)點都有到sink節(jié)點的最小跳數，然后根據已構建的最小跳數樹獲取地址。另外文獻[11]提出了一種動態(tài)參數的分配算法，該方法可以減少孤立節(jié)點數量，但是增加了網絡開銷，并且擴展性不強，當網絡節(jié)點很多時，增加了組網時間。

　　本文提出了一種基于動態(tài)參數的按需可擴展地址分配算法(AP-SAAM)，同時給出了改進的路由算法，使其兼容cluster-tree路由協議。

　　本文的貢獻主要如下：

　　(1)提出了一種基于動態(tài)參數的按需可擴展地址分配算法，可以根據已知網絡參數來決定擴展的地址大小，同時兼容原DAAM算法。

　　(2)可以根據網絡狀態(tài)進行參數調整以及擴展次數，具有很強的擴展性。

　　(3)給出了改進的路由算法，且與cluster-tree路由協議兼容。

1 系統模型

　　本文對地址的擴展思想為：首先計算出DAAM定義的地址空間，然后得出可以表示這些地址空間的最小比特位數a0，然后把剩余的地址分成Rm段，如果不進行地址擴展，就使用第一段地址空間；如果進行一次擴展，則使用第二段地址空間；以此類推，直到網絡地址擴展完，每一段地址所占的比特位數如圖1所示。

　　其中，ai表示各個地址塊所占用的比特位數。

　　具體地址段的分配方式如下：

　　根據已知條件可以得出DAAM分配的最大空間Am，可用式(1)計算：

　　Am=Cskip(0)×Rm+Cm-Rm(1)

　　又因為

　　為了考慮一般性，我們只考慮Rm>1的情況，此時有：

　　整理得：

　　所以得出可表示Am的最小比特位數a：

　　a=min{a|2a≥Am}(5)

　　進而得出每一塊地址段所占的比特位數為：

　　其中i表示地址塊數，即擴展的次數。

　　假設O、R分別代表普通設備和路由設備，N1，N2分別表示沒有獲得網絡地址的普通節(jié)點以及路由節(jié)點的個數，Li表示第i個網絡設備的深度，Oam表示地址為a的普通節(jié)點的深為m，Rbm表示地址為b的路由節(jié)點的深度為n，則新的網絡參數為：

　　然后進行第一次地址擴展，這時協調器只會給個路由節(jié)點分配擴展后的地址塊，如果第一次擴展后仍有孤立節(jié)點，然后再進行第二次地址擴展，以此推論，直至整個地址空間用完，分配方法如式（8）：

　　且Nd≤，其中Achildren為擴展地址，i表示進行地址擴展的次數，Nd表示第i次擴展時路由節(jié)點數。

　　得到地址塊的路由節(jié)點可以再次進行地址分配，分配方式仍按照原DAAM算法，參數為：。其可分配的地址大小為，其中i表示擴展次數，且1≤i≤Rm。

2 基于動態(tài)參數的按需可擴展地址分配算法

　　2.1 AP-SAAM算法步驟

　　(1)DAAM算法：

　　初始化：網絡協調器把自己的地址設置為0，網絡參數為Lm、Rm和Cm。

　　地址請求：節(jié)點向其鄰居表中未被標記的潛在父節(jié)點發(fā)出入網請求(當有多個時隨機選擇)；如果未收到答復，則依次向其他未標記的節(jié)點發(fā)出入網請求，如果仍未得到回復，則向協調器發(fā)送第一次地址擴展請求，同時轉向步驟(3)，如果仍沒有獲得地址，發(fā)送第二次地址擴展請求，以此類推。

　　地址分配：地址為Aparent的路由節(jié)點收到入網請求時，首先查詢自己的地址空間，如果有地址，則按照原DAAM算法進行分配。

　　(2)地址擴展：

　　網絡協調器收到借用地址請求后，根據式(6)對網絡進行地址塊的劃分；然后按照式(7)計算。

　　(3)擴展地址分配：

　　此時網絡協調器進行第一次地址擴展，根據式(8)對申請的個路由節(jié)點進行地址的分配（如有剩余，留作下次使用）。網絡協調器需要維護這些路由節(jié)點的路由表，得到地址塊的路由節(jié)點向其潛在父節(jié)點發(fā)出作為其子節(jié)點的請求，并上報自己的網絡地址，同時標記自己的網絡深度為其父節(jié)點深度加1，用Lj表示，當此路由節(jié)點再次收到節(jié)點的入網請求時，則按照式(9)進行地址的分配：

　　其中，Aparent為父節(jié)點地址，Li為申請加入的節(jié)點深度，且滿足Li-Lj≤。

　　2.2 路由算法改進

　　經過擴展地址分配后，可能的網絡地址結構如圖2所示，其中A、B為獲得擴展地址的節(jié)點區(qū)域，C為按照原DAAM算法得到地址的節(jié)點區(qū)域。對此，源節(jié)點以及目的節(jié)點的地址類型就會有四種情況，如表1所示。

　　假設源節(jié)點網絡地址為A，深度為d；目的節(jié)點網絡地址為D。首先判斷式(10)、(11)是否成立

　　如果式(10)和式(11)都成立，則執(zhí)行步驟1；如果式(10)成立，式(11)不成立，則執(zhí)行步驟2；如果式(10)不成立，式(11)成立，則執(zhí)行步驟3；如果式(10)不成立，式(11)不成立，則執(zhí)行步驟4。

　　步驟1：首先判斷邏輯表達式(12)是否成立，其中參數為Lm、Rm、Cm。

　　A<D<A+Cskip(d-1)(12)

　　如果不成立，則交給A的父節(jié)點；如果成立，且D是A的一跳鄰居節(jié)點，則修改下一跳地址Ne=D，若不是一跳鄰居節(jié)點，則通過式(13)計算下一跳地址，其中參數為Lm、Rm、Cm。

　　其中0≤d≤Lm。

　　步驟2：首先判斷邏輯表達式(14)是否成立：

　　其中Achildren為節(jié)點A的子節(jié)點。

　　如果成立，則表示目的節(jié)點屬于節(jié)點A的子節(jié)點的擴展地址域，然后修改下一跳地址Ne=Achildren；如果不成立，則修改下一跳地址為A的父節(jié)點即：Ne=Aparpent。

　　步驟3：修改下一跳地址為A的父節(jié)點即：Ne=Aparpent。

　　步驟4：首先判斷邏輯表達式(12)是否成立，其中參數為。

　　如果不成立，則交給A的父節(jié)點；如果成立，若D是A的一跳鄰居節(jié)點，則修改下一跳地址Ne=D，若不是一跳鄰居節(jié)點，則通過式(13)計算下一跳地址，其中參數為，且0≤d≤。

　　綜上所述，修改的路由協議能夠滿足地址分配算法。

3 算法仿真

　　把DAAM、EDAA-BA[5]、RBAC[9]作為比較對象，通過OPNET仿真來觀察它們在性能方面的差異。其中網絡參數分別設為Cm=4，Rm=2，Lm=15。

　　圖3表示的是平均地址分配成功率與網絡節(jié)點個數之間的關系。從圖中可以看出，EDAA-BA、RBAC以及AP-SAAM的分配成功率要高于DAAM，且AP-SAAM最高，特別是隨著節(jié)點數的增加，AP-SAAM的性能更優(yōu)，這是因為AP-SAAM能夠根據網絡狀況實施地址擴展，從而能夠分配更多的地址，進而提高節(jié)點入網的概率。

　　圖4表示的是平均分配耗時與網絡節(jié)點個數之間的關系，有圖可知，EDAA-BA、RBAC以及AP-SAAM都比DAAM平均耗時大，其中EDAA-BA耗時最大，這是因為其不斷進行借用地址花費了大量的時間，這一現象隨著節(jié)點的增加、網絡結構的復雜變得更加明顯，RBAC和AP-SAAM的平均耗時相當。

　　圖5表示的是平均路由跳數與網絡節(jié)點個數之間的關系，其中路由跳數表示節(jié)點到其潛在鄰居節(jié)點的跳數。從圖中可以看出RBAC算法和AP-SAAM算法相當，而EDAA-BA要優(yōu)于其它三種算法，這是因為EDAA-BA算法在進行借用地址時專門考慮了迂回問題。

4 結束語

　　本文提出了一種基于動態(tài)參數的按需可擴展地址分配算法，當地址充足時，使用DAAM算法；當出現地址不足時，對剩余地址空間進行擴展，根據已知參數對剩余地址塊靈活的分配，同時根據網絡狀況進行一次或者多次擴展，從而很好地解決了孤立節(jié)點問題。

參考文獻

　　[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網絡節(jié)點設計[J].電子技術應用，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網絡中基于借地址的高效分布式地址分配算法[J].重慶大學學報，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網絡按需可擴展地址分配算法[J].通信學報，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] 胡義，文建國，羅娟.時間驅動型傳感器網絡地址分配算法研究[J].計算機工程與應用，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.