基于分段的ZigBee網(wǎng)絡(luò)按需可擴(kuò)展地址分配算法

任智，李鵬翔，姚玉坤，黃勇

（重慶郵電大學(xué) 通信與信息工程學(xué)院 移動(dòng)通信技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室，重慶 400065）

1 引言

采用 ZigBee標(biāo)準(zhǔn)[1]的無(wú)線傳感器網(wǎng)絡(luò)[2,3]（簡(jiǎn)稱“ZigBee網(wǎng)絡(luò)”）近來(lái)得到較多關(guān)注。ZigBee網(wǎng)絡(luò)在組網(wǎng)過(guò)程中會(huì)為每個(gè)節(jié)點(diǎn)分配一個(gè) 16bit的網(wǎng)絡(luò)地址，以用于之后的通信。分布式地址分配機(jī)制（DAAM, distributed address assignment mechanism）[1]是ZigBee網(wǎng)絡(luò)中一種重要的節(jié)點(diǎn)地址分配機(jī)制，它使用網(wǎng)絡(luò)協(xié)調(diào)器和路由節(jié)點(diǎn)的最大子節(jié)點(diǎn)數(shù)Cm、最大子路由節(jié)點(diǎn)數(shù)Rm和網(wǎng)絡(luò)最大深度Lm這3個(gè)參數(shù)計(jì)算并分配節(jié)點(diǎn)地址，通過(guò)在分配與被分配地址的節(jié)點(diǎn)之間建立“父-子”關(guān)系，使地址與位置相關(guān)聯(lián)，從而為樹(shù)路由（tree routing）協(xié)議[1,4]的運(yùn)行提供條件。因?yàn)閷?shí)現(xiàn)簡(jiǎn)便且能使地址與位置關(guān)聯(lián)，DAAM目前得到較廣泛的研究和應(yīng)用。

由于DAAM預(yù)設(shè)了參數(shù)Cm和Rm，因此當(dāng)向某個(gè)路由節(jié)點(diǎn)申請(qǐng)地址的路由節(jié)點(diǎn)數(shù)大于Rm，或終端節(jié)點(diǎn)數(shù)大于Cm-Rm時(shí)，節(jié)點(diǎn)分配不到地址，稱之為“寬度不足”（insufficient breadth）問(wèn)題，得不到地址的節(jié)點(diǎn)因無(wú)法入網(wǎng)而成為孤節(jié)點(diǎn)（orphan node）[5]，如圖1中的節(jié)點(diǎn)A。由于網(wǎng)絡(luò)部署通常難以直接固定所有節(jié)點(diǎn)位置，因此寬度不足問(wèn)題發(fā)生的可能性不能忽略。

圖1 寬度不足問(wèn)題（Cm=5,Rm=3,Lm=2）

對(duì)于寬度不足問(wèn)題，目前已有一些研究。文獻(xiàn)[5]探討了節(jié)點(diǎn)因預(yù)設(shè)參數(shù)限制而成為孤節(jié)點(diǎn)的成因，提出了改變孤節(jié)點(diǎn)潛在父節(jié)點(diǎn)、重構(gòu)局部網(wǎng)絡(luò)拓?fù)涞慕鉀Q方法，能夠減少因?qū)挾炔蛔惝a(chǎn)生的孤節(jié)點(diǎn)，但在通信和運(yùn)行時(shí)間等方面會(huì)產(chǎn)生明顯的額外開(kāi)銷(xiāo)。文獻(xiàn)[6]對(duì)寬度不足問(wèn)題提出的解決方法是無(wú)地址的節(jié)點(diǎn)以有地址的相鄰路由節(jié)點(diǎn)為代理，向協(xié)調(diào)器申請(qǐng)地址，協(xié)調(diào)器將 DAAM 定義的地址空間之外的地址分配給該節(jié)點(diǎn)，這種方法的主要問(wèn)題是會(huì)產(chǎn)生額外通信開(kāi)銷(xiāo)及部分節(jié)點(diǎn)無(wú)法使用樹(shù)路由。文獻(xiàn)[7]和文獻(xiàn)[8]提出了借地址的思路，子地址空間不足的路由節(jié)點(diǎn)向有剩余地址的路由節(jié)點(diǎn)借地址進(jìn)行分配，這種方式同樣存在額外通信開(kāi)銷(xiāo)和破壞樹(shù)路由的問(wèn)題。文獻(xiàn)[9]介紹了一種通過(guò)地址重配置來(lái)減少孤節(jié)點(diǎn)的方法，在重配置過(guò)程中使用了DAAM未用到的地址，但重配置使控制開(kāi)銷(xiāo)增加且其擴(kuò)展操作是一次性的。文獻(xiàn)[10]針對(duì)寬度不足問(wèn)題提出了一種通過(guò)增大深度參數(shù)減小地址偏移量，從而使路由節(jié)點(diǎn)的子節(jié)點(diǎn)地址空間增大的方案 SLAR（single level address reorganization）；當(dāng)深度為d的路由節(jié)點(diǎn)子地址不夠時(shí)，啟動(dòng)地址重配置過(guò)程，使用Cskip(d+1)取代Cskip(d)作為地址偏移量分配地址給子節(jié)點(diǎn)，Cskip(d)由式(1)計(jì)算：

這種“以深度換寬度”的方法雖能增大路由節(jié)點(diǎn)的子節(jié)點(diǎn)地址空間，但減小了網(wǎng)絡(luò)深度，且地址重配置操作使控制開(kāi)銷(xiāo)和耗時(shí)增加。

為解決現(xiàn)有方案存在的上述增加額外通信開(kāi)銷(xiāo)、破壞樹(shù)路由的問(wèn)題，本文提出一種基于分段的按需可擴(kuò)展地址分配算法，對(duì)路由節(jié)點(diǎn)的子節(jié)點(diǎn)地址空間進(jìn)行分段式按需擴(kuò)展，為更多節(jié)點(diǎn)分配地址，既保持“地址-位置”關(guān)系又無(wú)需任何額外的通信開(kāi)銷(xiāo)，并且通過(guò)改進(jìn)樹(shù)路由協(xié)議使其適應(yīng)所有地址。

本文的主要貢獻(xiàn)如下。

1) 提出一種基于分段的按需可擴(kuò)展地址分配新算法，在需要時(shí)逐段擴(kuò)展可用地址空間，增加路由節(jié)點(diǎn)能夠連接的子節(jié)點(diǎn)數(shù)。

2) 改進(jìn)DAAM中的節(jié)點(diǎn)地址計(jì)算公式，引入段地址和段偏移量，使其適用于新算法，并保持原有的“地址-位置”關(guān)系。

3) 改進(jìn)現(xiàn)有的ZigBee網(wǎng)絡(luò)樹(shù)路由協(xié)議，使其與新算法分配的節(jié)點(diǎn)地址兼容。

本文后面部分組織如下：第2節(jié)介紹網(wǎng)絡(luò)模型，第3節(jié)詳述提出的地址分配新算法和樹(shù)路由協(xié)議的改進(jìn)方法，第4節(jié)對(duì)新算法的性能進(jìn)行理論和仿真分析，第5節(jié)總結(jié)全文。

2 網(wǎng)絡(luò)模型

2.1 模型與定義

ZigBee網(wǎng)絡(luò)的數(shù)學(xué)模型為：G=(V，E)，其中，V表示所有節(jié)點(diǎn)的集合，V={t}∪Vr∪Ve，t表示網(wǎng)絡(luò)協(xié)調(diào)器，Vr表示所有路由節(jié)點(diǎn)的集合，Ve表示所有終端節(jié)點(diǎn)的集合；E表示所有對(duì)稱無(wú)線通信鏈路的集合。

為便于研究，在本文中做如下定義。

定義1 地址空間（address space）：指具有一定位數(shù)的地址集合。

定義2 分段（segmentation）：指將一個(gè)地址空間分為多個(gè)容量更小的地址空間。

2.2 剩余地址空間

本文在研究中發(fā)現(xiàn)，DAAM定義的地址空間上限很少達(dá)到65 535(216-1)，這意味著絕大多數(shù)情況下有剩余地址空間可供利用。下面推導(dǎo) DAAM 用完16bit地址空間的概率。

根據(jù)DAAM的原理，有SDAAM={1,Am}，其中，SDAAM和Am分別表示DAAM定義的地址空間和分配的最大地址。Am可用式(2)計(jì)算：

1) 當(dāng)Rm=1時(shí)，有：

欲使Am=65 535，須CmLm=65 535；通過(guò)因式分解可知65 535為4個(gè)素?cái)?shù)的乘積：65 535=3×5×17×257；因此，滿足條件的CmLm組合個(gè)數(shù)為：

2) 當(dāng)Rm＞1時(shí)，有：

結(jié)合條件Rm＞1、Cm≥Rm和Lm≥1進(jìn)行遍歷搜索，得到滿足條件的CmRmLm組合個(gè)數(shù)為3，即（4 369, 2,4）、（13 107, 4, 2）、（21 845, 2, 2）。

綜上，DAAM 用完 16bit地址空間的方式有16+3=19種；由于Lm∈{1, 65 535}，Cm∈{1, 65 535}，因此總的地址分配方式數(shù)大于65 5352，則DAAM用完地址空間的概率P＜19/65 5352(≈4.42×10-9)，近似地，P≈0。

3 基于分段的按需可擴(kuò)展地址分配算法

根據(jù)按需利用剩余地址空間的思路，提出一種基于分段的按需可擴(kuò)展地址分配 (SOSAA, segmentation-based on-demand scalable address assignment)算法，用DAAM定義的地址空間作為單位，對(duì) 16bit地址空間進(jìn)行按需的分段式擴(kuò)展（如圖 2所示），改善寬度不足問(wèn)題。

圖2 地址空間分段式擴(kuò)展

3.1 SOSAA算法操作

SOSAA算法操作包括初始化、地址請(qǐng)求和地址分配3個(gè)階段，具體如下。

1) 初始化

網(wǎng)絡(luò)協(xié)調(diào)器將自己的地址設(shè)為 0，并確定參數(shù)Cm、Rm和Lm；然后，向鄰居節(jié)點(diǎn)廣播組網(wǎng)消息。

2) 地址請(qǐng)求

如果一個(gè)無(wú)地址的節(jié)點(diǎn)收到鄰居廣播的組網(wǎng)消息，它將鄰居地址存入鄰居表；然后，從鄰居表中選擇一個(gè)信號(hào)最強(qiáng)的節(jié)點(diǎn)，向其發(fā)送地址請(qǐng)求消息；如果收到無(wú)地址分配的消息，則依次向鄰居表中的其他節(jié)點(diǎn)發(fā)送地址請(qǐng)求，直至發(fā)往所有鄰居。

3) 地址分配

如果地址為Ap的路由節(jié)點(diǎn)收到其他節(jié)點(diǎn)的地址請(qǐng)求，用式(6)為該申請(qǐng)節(jié)點(diǎn)分配地址Ar。

其中，AS為段地址，等于進(jìn)行地址擴(kuò)展操作的次數(shù)，初始值為 0；n為同一段地址空間內(nèi)已分配的同類節(jié)點(diǎn)數(shù)。如果無(wú)剩余地址，該路由節(jié)點(diǎn)將AS加1，重新計(jì)算Ar；若Ar小于65 536，則將其分配給申請(qǐng)節(jié)點(diǎn)，否則，因地址位數(shù)大于16，向申請(qǐng)節(jié)點(diǎn)發(fā)送無(wú)地址分配消息。

SOSAA算法進(jìn)行地址分配的效果可從圖1中看出，該圖中的節(jié)點(diǎn)A使用DAAM無(wú)法獲得地址，但運(yùn)行 SOSAA 算法則能獲得地址 28(1×20+7+1×0+1=28)。

3.2 計(jì)算復(fù)雜度

關(guān)于SOSAA算法的計(jì)算復(fù)雜度，有如下引理。

引理1 SOSAA算法具有與DAAM相同的計(jì)算復(fù)雜度。

證明 考慮時(shí)間、存儲(chǔ)和通信3個(gè)方面的復(fù)雜度。

SOSAA算法的運(yùn)行時(shí)間主要受網(wǎng)絡(luò)深度Lm和節(jié)點(diǎn)的最大鄰居節(jié)點(diǎn)數(shù)Nm影響，為O(Lm+Nm)；而DAAM的時(shí)間復(fù)雜度同樣如此，也為O(Lm+Nm)。DAAM 占用節(jié)點(diǎn)存儲(chǔ)空間最多的部分是鄰居節(jié)點(diǎn)的信息，因此它的存儲(chǔ)復(fù)雜度由最大鄰居節(jié)點(diǎn)數(shù)決定，為O(Nm)；SOSAA算法只比DAAM多存儲(chǔ)了一個(gè)長(zhǎng)度固定的段地址值，此值占用空間相對(duì)很小，對(duì)存儲(chǔ)復(fù)雜度沒(méi)有影響，因此它的存儲(chǔ)復(fù)雜度同樣為O(Nm)。DAAM算法的通信操作主要包括網(wǎng)絡(luò)協(xié)調(diào)器和路由節(jié)點(diǎn)的組網(wǎng)消息廣播和節(jié)點(diǎn)的地址申請(qǐng)與回復(fù)，因此它的通信復(fù)雜度由路由節(jié)點(diǎn)的數(shù)量和度決定，為O(NRmLm-1)，其中，N為路由節(jié)點(diǎn)的度；而SOSAA算法沒(méi)有增加任何通信操作，因此其通信復(fù)雜度同樣為O(NRmLm-1)。由上述內(nèi)容可得：SOSAA算法與DAAM具有相同的計(jì)算復(fù)雜度。證畢。

3.3 SOSAA算法的適用范圍與不足

SOSAA算法可用于任何使用DAAM的ZigBee網(wǎng)絡(luò)。當(dāng)子節(jié)點(diǎn)數(shù)量適用于DAAM時(shí)，DAAM和SOSAA算法均可應(yīng)用且地址分配的效果相同；而通常情況下子節(jié)點(diǎn)數(shù)有可能超出 DAAM 的限制，此時(shí) SOSAA算法能夠分配更多地址，效果優(yōu)于DAAM。在任何規(guī)模的 ZigBee網(wǎng)絡(luò)中，都可以用SOSAA算法代替DAAM，為更多節(jié)點(diǎn)分配地址并且保持“地址－位置”關(guān)系。SOSAA算法的不足之處在于：16bit地址總空間的限制對(duì)分段后留給子節(jié)點(diǎn)擴(kuò)充用的地址空間有一定程度的制約，當(dāng)DAAM定義的地址空間較大時(shí)，地址空間分段式擴(kuò)展的次數(shù)會(huì)降低，能夠多分配的地址數(shù)也會(huì)相應(yīng)減少；但只要16bit地址空間沒(méi)被DAAM用完，就能多分配地址，前文已推導(dǎo)出用完的概率約等于0。

另一方面，由于受到 ZigBee標(biāo)準(zhǔn)的限制，節(jié)點(diǎn)根本地址的最大值為65 535；當(dāng)節(jié)點(diǎn)數(shù)小于該值時(shí)，SOSAA算法能夠有效擴(kuò)充節(jié)點(diǎn)所用地址空間；而當(dāng)節(jié)點(diǎn)數(shù)大于該值時(shí)，由于根本地址數(shù)量已不能滿足要求，因此需要在根本地址的擴(kuò)充上再想辦法，比如為節(jié)點(diǎn)地址擴(kuò)充附加比特?cái)?shù)等，這涉及到改變 ZigBee標(biāo)準(zhǔn)對(duì)節(jié)點(diǎn)地址比特?cái)?shù)的定義，將在下一步工作中深入研究此問(wèn)題。

3.4 樹(shù)路由協(xié)議的改進(jìn)

為消除SOSAA算法對(duì)樹(shù)路由的影響，本文改進(jìn)了樹(shù)路由協(xié)議中判斷數(shù)據(jù)傳遞方向和計(jì)算下一跳節(jié)點(diǎn)的機(jī)制。改進(jìn)后的樹(shù)路由協(xié)議主要步驟如下。

1) 地址為A深度為d的路由節(jié)點(diǎn)收到目的地址為D的數(shù)據(jù)分組時(shí)，先計(jì)算基準(zhǔn)地址D'：

2) 用式(7)判斷D是否是子孫節(jié)點(diǎn)：

若式(8)成立，則執(zhí)行步驟3）；否則，將數(shù)據(jù)分組發(fā)給本節(jié)點(diǎn)的父節(jié)點(diǎn)，結(jié)束。

3) 判斷：

若式(8)成立，下一跳節(jié)點(diǎn)地址N=D；否則：

然后，將數(shù)據(jù)分組轉(zhuǎn)發(fā)給下一跳節(jié)點(diǎn)。

如上所述，改進(jìn)后的樹(shù)路由協(xié)議能夠適用于SOSAA算法分配的所有地址。

4 性能分析

4.1 理論分析

1) 地址分配成功率

地址分配成功率用于評(píng)價(jià)地址分配算法的有效性。定義地址分配成功率S為

其中，N為節(jié)點(diǎn)總數(shù)，NS表示獲得地址的節(jié)點(diǎn)數(shù)。因?yàn)镾OSAA算法能夠通過(guò)按需的地址擴(kuò)展為原來(lái)得不到地址的節(jié)點(diǎn)分配地址，所以會(huì)使NS增大，則S隨之增大。

2) 控制開(kāi)銷(xiāo)

控制開(kāi)銷(xiāo)指地址分配算法在運(yùn)行過(guò)程中用于傳送控制分組的開(kāi)銷(xiāo)，與算法效率負(fù)相關(guān)。為消除控制分組長(zhǎng)度不同的影響，在本文中用地址分配算法運(yùn)行結(jié)束時(shí)節(jié)點(diǎn)發(fā)出的所有控制分組的比特?cái)?shù)BC來(lái)表示控制開(kāi)銷(xiāo)。

其中，i為大于0的整數(shù)，Li表示第i個(gè)控制分組的長(zhǎng)度。由于SOSAA算法能夠?yàn)樵瓉?lái)得不到地址的節(jié)點(diǎn)分配地址，這部分節(jié)點(diǎn)獲得地址后不再觸發(fā)地址請(qǐng)求分組及其答復(fù)分組，因此與DAAM相比，i減小，相應(yīng)地BC減小。

3) 地址分配平均耗時(shí)

地址分配平均耗時(shí)表征算法分配地址的快慢程度。定義地址分配平均耗時(shí)ta為其中，ts表示分配地址消耗的全部時(shí)間，Na表示獲得地址的節(jié)點(diǎn)總數(shù)。與DAAM相比，SOSAA算法能夠?yàn)楦嗟墓?jié)點(diǎn)分配地址，Na增大；減少了節(jié)點(diǎn)因得不到地址而多次申請(qǐng)的操作，使ts減小，所以ta減小。

4.2 仿真分析

取 DAAM 和 SLAR[10]作為比較對(duì)象，通過(guò)仿真比較分析它們和SOSAA算法在地址分配方面的性能。選擇SLAR的原因在于它能夠增大路由節(jié)點(diǎn)的地址空間且未破壞樹(shù)路由。

4.2.1 仿真設(shè)置

使用Windows XP平臺(tái)上的OPNET仿真軟件[11]對(duì)上述地址分配算法進(jìn)行仿真。在半徑為200m的圓形區(qū)域設(shè)置具有不同節(jié)點(diǎn)密度的5個(gè)仿真場(chǎng)景，N個(gè)靜止節(jié)點(diǎn)在該區(qū)域中隨機(jī)均勻分布，N∈{100，200，300，400，500}；每個(gè)場(chǎng)景的中心位置有 1個(gè)協(xié)調(diào)器，路由節(jié)點(diǎn)和終端節(jié)點(diǎn)的數(shù)量比例為6：4；節(jié)點(diǎn)的MAC層和物理層采用IEEE802.15.4a標(biāo)準(zhǔn)[12]，節(jié)點(diǎn)通信范圍統(tǒng)一設(shè)為35m；考慮節(jié)點(diǎn)總數(shù)和路由、終端節(jié)點(diǎn)比例，Cm、Rm和Lm的缺省值分別設(shè)為5、3和8。每個(gè)仿真實(shí)驗(yàn)做4次，結(jié)果取平均值。隨機(jī)種子值分別取128、130、132和134。

4.2.2 仿真結(jié)果及分析

1) 地址分配成功率

從圖3可看出，SOSAA算法在5個(gè)場(chǎng)景中的地址分配成功率均明顯大于DAAM和SLAR，它們的均值分別為88%、65%和30%，最小的差距也有 20%（300節(jié)點(diǎn)場(chǎng)景），分析其原因主要在于 SOSAA算法通過(guò)擴(kuò)展地址使更多的節(jié)點(diǎn)得到地址，而且不影響節(jié)點(diǎn)原有的地址分配機(jī)會(huì)。SLAR由于縮小了網(wǎng)絡(luò)深度，對(duì)地址分配成功率造成了明顯影響。

圖3 地址分配成功率比較

2) 控制開(kāi)銷(xiāo)

圖4顯示了SOSAA算法的控制開(kāi)銷(xiāo)(均值為552 700.8bit)在各場(chǎng)景中均不大于另外2種算法，這驗(yàn)證了前面的理論分析。此外，由于深度減小而丟失地址的節(jié)點(diǎn)會(huì)再次發(fā)送地址請(qǐng)求消息，也使開(kāi)銷(xiāo)上升。隨著節(jié)點(diǎn)數(shù)的增加，SOSAA算法的優(yōu)勢(shì)從0（100節(jié)點(diǎn)）上升到28.6%（500節(jié)點(diǎn)），也從側(cè)面說(shuō)明了無(wú)地址節(jié)點(diǎn)的增加使 DAAM 和SLAR的開(kāi)銷(xiāo)增加較明顯，尤其是SLAR，上升速率最大，說(shuō)明重配置過(guò)程在節(jié)點(diǎn)多時(shí)會(huì)明顯增加開(kāi)銷(xiāo)。

圖4 控制開(kāi)銷(xiāo)比較

3) 地址分配平均耗時(shí)

圖5表明SOSAA算法的地址分配平均耗時(shí)（均值為0.12s）在總體上少于DAAM（均值為0.14s）和SLAR（均值為0.60s）。分析其原因在于DAAM中無(wú)地址的節(jié)點(diǎn)會(huì)向相鄰的所有路由節(jié)點(diǎn)申請(qǐng)地址，引起耗時(shí)增加；SLAR在第一次分配地址之后會(huì)再次運(yùn)行地址分配過(guò)程，使分配耗時(shí)增加；從圖中數(shù)據(jù)來(lái)看，SLAR地址重配置過(guò)程加上之后的無(wú)地址節(jié)點(diǎn)的地址請(qǐng)求過(guò)程，使地址分配平均耗時(shí)成倍增加。100個(gè)節(jié)點(diǎn)的場(chǎng)景中由于節(jié)點(diǎn)總數(shù)和無(wú)地址的節(jié)點(diǎn)數(shù)都較少，因此SOSAA算法的優(yōu)越性尚未充分體現(xiàn)，平均耗時(shí)比 DAAM 稍高，但仍比SLAR低約60%。

圖5 地址分配平均耗時(shí)比較

4) 路由節(jié)點(diǎn)比例的影響

選擇500個(gè)節(jié)點(diǎn)的場(chǎng)景，改變路由節(jié)點(diǎn)比例，得到如圖6所示的結(jié)果。從圖中可看出，隨著路由節(jié)點(diǎn)比例的增加，SOSAA算法的地址分配成功率從4.2%開(kāi)始上升，在比例為0.8時(shí)獲得最大值91%，地址分配平均耗時(shí)從0.393開(kāi)始下降，在比例為 0.6時(shí)取得最小值 0.042s，說(shuō)明路由節(jié)點(diǎn)比例的增加總體上對(duì) SOSAA的節(jié)點(diǎn)地址分配性能有利，這為網(wǎng)絡(luò)部署時(shí)路由節(jié)點(diǎn)比例的選取提供了一個(gè)參考。

圖6 路由節(jié)點(diǎn)比例對(duì)SOSAA性能的影響

5) 網(wǎng)絡(luò)深度的影響

選擇 500個(gè)節(jié)點(diǎn)的場(chǎng)景，取Cm=5，Rm=3，Lm∈{2，3，4，5，6，7，8，9}，考察 SOSAA算法的性能得到如圖7所示結(jié)果。由圖7可知，SOSAA算法的地址分配成功率和平均耗時(shí)在Lm=8時(shí)取得最優(yōu)值，說(shuō)明網(wǎng)絡(luò)最大深度和地址分配性能不是正相關(guān)關(guān)系。分析其原因在于：在寬度一定的情況下，深度小時(shí)因深度不足而無(wú)法得到地址的節(jié)點(diǎn)會(huì)增多；而深度大時(shí)，在地址總量65 535的限制下，因DAAM占用的地址空間增大而會(huì)導(dǎo)致可擴(kuò)展的地址空間減少，這也驗(yàn)證了3.3節(jié)的分析。

圖7 網(wǎng)絡(luò)深度對(duì)SOSAA性能的影響

5 結(jié)束語(yǔ)

本文提出了一種基于分段的按需可擴(kuò)展地址分配算法——SOSAA算法，當(dāng)路由節(jié)點(diǎn)的子節(jié)點(diǎn)地址空間不足時(shí)對(duì)其進(jìn)行分段式擴(kuò)展，從而為更多的節(jié)點(diǎn)分配地址，并且避免了額外通信開(kāi)銷(xiāo)和對(duì)樹(shù)路由的影響。理論分析和仿真結(jié)果顯示，與DAAM和它的一種改進(jìn)方案(SLAR)相比，SOSAA算法在地址分配成功率、控制開(kāi)銷(xiāo)和地址分配平均耗時(shí)等方面的性能表現(xiàn)整體更優(yōu)。在未來(lái)工作中，將深入研究根本地址的擴(kuò)充問(wèn)題和寬、深度不足問(wèn)題的合成解決方案。

[1] ZigBee Alliance, ZigBee Specification Document 053474r17[S].2007.

[2] AKYILDIZ I F, SU W L, SANKARASUBRAMANIAM Y,et al. A survey on sensor networks[J]. IEEE Communications Magazine, 2002,40(8): 102-114.

[3] 黃瓊, 張宏科, 郜帥等. 基于 IPv6的無(wú)線傳感器網(wǎng)絡(luò)應(yīng)用設(shè)計(jì)[J].重慶郵電學(xué)院學(xué)報(bào)(自然科學(xué)版), 2006, 18(5): 621-624.HUANG Q, ZHANG H K, GAO S,et al. Application design of wireless sensor network based on IPv6[J]. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition), 2006,18(5): 621-624.

[4] HARBAWI M A, RASID M F A, NOORDIN N K. Improved tree routing (ImpTR) protocol for ZigBee network[J]. International Journal of Computer Science and Network Security, 2009, 9(10):146-152.

[5] PAN M S, TSAI C H, TSENG Y C. The orphan problem in ZigBee wireless networks[J]. IEEE Transactions on Mobile Computing, 2009,8(11):1573-1584.

[6] YEN L H, TSAI W T. The room shortage problem of tree-based Zig-Bee/IEEE 802.15.4 wireless networks[J]. Computer Communications,2010, 33(4):454-462.

[7] GIRI D, ROY U K. Address borrowing in wireless personal area network[A]. 2009 IEEE International Advance Computing Conference(IACC 2009)[C]. Patiala, India, 2009.181-186.

[8] FANG M Q, WAN J, XU X H. A preemptive distributed address assignment mechanism for wireless sensor networks[A]. Proceedings of the 4th International Conference on Wireless Communications,Networking and Mobile Computing (WICOM’ 08)[C]. Dalian, China,2008.1-5.

[9] LI Y R, SHI H B, TANG B Y. Address assignment and routing protocol for large-scale uneven wireless sensor networks[A]. 2009 International Symposium on Computer Network and Multimedia Technology[C]. Wuhan, China, 2009.1-4.

[10] GIRI D, ROY U K. Single level address reorganization in wireless personal area network[A]. 2009 International Conference on Com-

[14] ZigBee Alliance. ZigBee Specification[S]. 2008.

[15] 張潔穎.基于ZigBee網(wǎng)絡(luò)的定位跟蹤研究與實(shí)現(xiàn)[D]. 上海：同濟(jì)大學(xué), 2007.ZHANG J Y. The Research and Implementation of Localization and Tracking in the ZigBee Network[D]. Shanghai: Tongji University,2007.

[16] GON?ALO G, HELENA S. Indoor location system using ZigBee technology[A]. Third International Conference on Sensor Technologies and Applications[C]. 2009. 152-157.