周　林，朱馬鋒，劉子辰

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

基于動(dòng)態(tài)參數(shù)的按需可擴(kuò)展地址分配算法*

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

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

提出了一種基于動(dòng)態(tài)參數(shù)的按需可擴(kuò)展地址分配算法，根據(jù)分布式地址分配機(jī)制(DAAM)對16 bit地址空間進(jìn)行分塊，根據(jù)網(wǎng)絡(luò)狀況來動(dòng)態(tài)調(diào)整參數(shù)以及進(jìn)行地址一次或者多次擴(kuò)展；同時(shí)改進(jìn)路由算法，使其與Cluster-Tree協(xié)議兼容。仿真表明改進(jìn)算法在地址分配成功率、平均分配耗時(shí)等方面優(yōu)于DAAM以及它的改進(jìn)方案EDAA-BA和RBAC。

地址分配；動(dòng)態(tài)參數(shù)；地址擴(kuò)展；路由算法

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)算法具有簡單以及包含“地址-位置”關(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)模型

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

圖1　分段的16 bit空間大小

其中，ai表示各個(gè)地址塊所占用的比特位數(shù)。

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

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

又因?yàn)?/p>

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

整理得：

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

進(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ù)為：

且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.1AP-SAAM算法步驟

(1)DAAM算法：

初始化：網(wǎng)絡(luò)協(xié)調(diào)器把自己的地址設(shè)置為0，網(wǎng)絡(luò)參數(shù)為Lm、Rm和Cm。

地址請求：節(jié)點(diǎn)向其鄰居表中未被標(biāo)記的潛在父節(jié)點(diǎn)發(fā)出入網(wǎng)請求(當(dāng)有多個(gè)時(shí)隨機(jī)選擇)；如果未收到答復(fù)，則依次向其他未標(biāo)記的節(jié)點(diǎn)發(fā)出入網(wǎng)請求，如果仍未得到回復(fù)，則向協(xié)調(diào)器發(fā)送第一次地址擴(kuò)展請求，同時(shí)轉(zhuǎn)向步驟(3)，如果仍沒有獲得地址，發(fā)送第二次地址擴(kuò)展請求，以此類推。

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

(2)地址擴(kuò)展：

網(wǎng)絡(luò)協(xié)調(diào)器收到借用地址請求后，根據(jù)式(6)對網(wǎng)絡(luò)進(jìn)行地址塊的劃分；然后按照式(7)計(jì)算。

(3)擴(kuò)展地址分配：

其中，Aparent為父節(jié)點(diǎn)地址，Li為申請加入的節(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ū)域。對此，源節(jié)點(diǎn)以及目的節(jié)點(diǎn)的地址類型就會(huì)有四種情況，如表1所示。

圖2　網(wǎng)絡(luò)拓?fù)?/p>

表1　源節(jié)點(diǎn)與目的節(jié)點(diǎn)類型

假設(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ù)為 Lm、Rm、Cm。

如果不成立，則交給A的父節(jié)點(diǎn)；如果成立，且D是A的一跳鄰居節(jié)點(diǎn)，則修改下一跳地址Ne=D，若不是一跳鄰居節(jié)點(diǎn)，則通過式(13)計(jì)算下一跳地址，其中參數(shù)為 Lm、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。

如果不成立，則交給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]作為比較對象，通過OPNET仿真來觀察它們在性能方面的差異。其中網(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)的概率。

圖3　平均地址分配成功率與節(jié)點(diǎn)個(gè)數(shù)關(guān)系圖

圖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)。

圖4　平均分配耗時(shí)與節(jié)點(diǎn)個(gè)數(shù)關(guān)系圖

圖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í)專門考慮了迂回問題。

圖5　平均路由跳數(shù)與網(wǎng)絡(luò)節(jié)點(diǎn)關(guān)系圖

4　結(jié)束語

本文提出了一種基于動(dòng)態(tài)參數(shù)的按需可擴(kuò)展地址分配算法，當(dāng)?shù)刂烦渥銜r(shí)，使用 DAAM算法；當(dāng)出現(xiàn)地址不足時(shí)，對剩余地址空間進(jìn)行擴(kuò)展，根據(jù)已知參數(shù)對剩余地址塊靈活的分配，同時(shí)根據(jù)網(wǎng)絡(luò)狀況進(jìn)行一次或者多次擴(kuò)展，從而很好地解決了孤立節(jié)點(diǎn)問題。

[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網(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.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網(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.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網(wǎng)絡(luò)按需可擴(kuò)展地址分配算法[J].通信學(xué)報(bào)，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]胡義，文建國，羅娟.時(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 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

國家自然科學(xué)基金（61171190）

2014-06-14)

周林（1963-），男，副教授，主要研究方向：數(shù)據(jù)通信、計(jì)算機(jī)網(wǎng)絡(luò)、物聯(lián)網(wǎng)等。

朱馬鋒（1989-）男，在讀研究生，主要研究方向：無線傳感器網(wǎng)絡(luò)。

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