基于動態參數的按需可擴展地址分配算法*

周　林，朱馬鋒，劉子辰

（1.重慶郵電大學 通信與信息工程學院，重慶400065；（2.中國科學院計算技術研究所，北京100083）

基于動態參數的按需可擴展地址分配算法*

周林1，朱馬鋒1，劉子辰2

（1.重慶郵電大學 通信與信息工程學院，重慶400065；（2.中國科學院計算技術研究所，北京100083）

提出了一種基于動態參數的按需可擴展地址分配算法，根據分布式地址分配機制(DAAM)對16 bit地址空間進行分塊，根據網絡狀況來動態調整參數以及進行地址一次或者多次擴展；同時改進路由算法，使其與Cluster-Tree協議兼容。仿真表明改進算法在地址分配成功率、平均分配耗時等方面優于DAAM以及它的改進方案EDAA-BA和RBAC。

地址分配；動態參數；地址擴展；路由算法

0　引言

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

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

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

本文的貢獻主要如下：

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

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

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

1　系統模型

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

圖1　分段的16 bit空間大小

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

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

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

又因為

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

整理得：

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

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

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

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

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

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

2　基于動態參數的按需可擴展地址分配算法

2.1AP-SAAM算法步驟

(1)DAAM算法：

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

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

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

(2)地址擴展：

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

(3)擴展地址分配：

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

2.2路由算法改進

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

圖2　網絡拓撲

表1　源節點與目的節點類型

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

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

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

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

其中0≤d≤Lm。

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

其中 Achildren為節點 A的子節點。

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

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

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

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

3　算法仿真

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

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

圖3　平均地址分配成功率與節點個數關系圖

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

圖4　平均分配耗時與節點個數關系圖

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

圖5　平均路由跳數與網絡節點關系圖

4　結束語

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

[1]Huang Yu-Kai，Pang，Ai-Chun，Hsiu，Pi-Cheng，et al. Distubuted throughput optimization for ZigBee cluster-tree Networks[J].IEEE Computer Society，2012(5)，23(3)：513-520.

[2]寧炳武，劉軍民.基于CC2430的Zigbee網絡節點設計[J].電子技術應用，2008(3)：95-99.

[3]Natalia C Fer，Marcelo D D Mor，Otto C M B Dua.An Efficient and Robust Addressing Protocol for Node Autoconfiguration in Ad Hoc Networks[J].IEEE/ACM Transactions on Networking，2013(4)，3(21)：845-856.

[5]KARAPISTROLI E，PAVLIDOU F N，GRAGOPOULOS I，et al.An overview of the IEEE 802.15.4a standard[J].IEEE Communications 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.An Efficient and Robust Addressing Protocol for Node Auto configuration in Ad Hoc Networks[J].IEEE/ACM Transactions 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 problem of 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 distributed address assignment mechanism[C].2013 IEEE 24th International Symposium on Personal,Indoor and Mobile Radio Communications:Mobile and Wireless Networks,8-11 Sept 2013,London,United Kingdom，2013：2062-2066.

Automatic parameters selection based on-demand scalable address assignment algorithm

Zhou Lin1，Zhu Mafeng1，Liu Zhichen2
(1.Institute of Communication Software,Chongqing University of Posts and Telecommunications，Chongqing 400065，China；2.Institute of Computing Technology，Chinese Academy of Sciences，Beijing 100083，China)

An automatic parameters selection based on-demand scalable address assignment algorithm was proposed in this paper.The 16 bit address space is divided into some blocks according to the values defined by DAAM.Different parameters are used and the address space is extend once or more according the network condition.Meanwhile,the improved routing protocol was compatible with the cluster-tree protocol.In the end,it is proved that the proposed algorithm performs better than DAAM,EDAA-BA and RBAC in the aspects of the success rate of address assignment,the average hop count and etc.

address assignment；automatic parameters；address extension；routing protocol

TN925.9

A

0258-7998(2015)01-0078-04

10.16157/j.cnki.0258-7998.2014061402147

國家自然科學基金（61171190）

2014-06-14)

周林（1963-），男，副教授，主要研究方向：數據通信、計算機網絡、物聯網等。

朱馬鋒（1989-）男，在讀研究生，主要研究方向：無線傳感器網絡。

劉子辰(1984-)，男，在讀博士生，主要研究方向：無線網絡、綠色無線電。