基于邏輯區(qū)域的Zig Bee網(wǎng)絡(luò)地址分配算法*

， ，

(西南科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，四川 綿陽(yáng) 621000)

0 引 言

Zig Bee協(xié)議[1]有2種地址分配機(jī)制：隨機(jī)地址分配機(jī)制和分布式地址分配機(jī)制(distributed address assignment mechanism，DAAM)。隨機(jī)地址分配機(jī)制是由父節(jié)點(diǎn)為子節(jié)點(diǎn)隨機(jī)的分配網(wǎng)絡(luò)地址；DAAM分配的地址呈規(guī)律性，包含了“地址—位置”的對(duì)應(yīng)關(guān)系，通過(guò)對(duì)地址的計(jì)算能獲得路由信息。DAAM實(shí)現(xiàn)簡(jiǎn)單，目前得到了廣泛的研究和應(yīng)用，但由于DAAM地址分配機(jī)制組網(wǎng)階段就設(shè)定了網(wǎng)絡(luò)參數(shù)Cm，Rm,Lm，造成了網(wǎng)絡(luò)中地址的嚴(yán)重浪費(fèi)，使得一些節(jié)點(diǎn)無(wú)法加入網(wǎng)絡(luò)，形成了孤立節(jié)點(diǎn)[2,3]。

針對(duì)這些問(wèn)題，目前已經(jīng)有一些研究，如文獻(xiàn)[4]針對(duì)網(wǎng)絡(luò)中存在大量頻繁移動(dòng)節(jié)點(diǎn)的問(wèn)題提出了相應(yīng)的地址分配算法，但并沒(méi)有充分解決出現(xiàn)孤立節(jié)點(diǎn)的問(wèn)題。文獻(xiàn)[5]分析了孤立節(jié)點(diǎn)形成的2種情況，提出了相應(yīng)的改進(jìn)算法，緩解了孤立節(jié)點(diǎn)問(wèn)題。文獻(xiàn)[6]提出了一種基于分段的按需可擴(kuò)展地址分配算法，對(duì)路由節(jié)點(diǎn)的子節(jié)點(diǎn)地址空間進(jìn)行分段式按需擴(kuò)展，為更多節(jié)點(diǎn)分配地址的同時(shí)保持了節(jié)點(diǎn)間的“地址—位置”關(guān)系。但仍基于DAAM地址分配機(jī)制，不適用于節(jié)點(diǎn)位置變化頻繁的網(wǎng)絡(luò)。文獻(xiàn)[7]和文獻(xiàn)[8]提出了借地址的思路，子地址空間不足的路由節(jié)點(diǎn)向有剩余地址的路由節(jié)點(diǎn)借地址進(jìn)行分配，這種方法的主要問(wèn)題是會(huì)產(chǎn)生額外通信開(kāi)銷和部分節(jié)點(diǎn)無(wú)法使用樹(shù)路由。

本文提出了一種基于邏輯區(qū)域按需地址分配機(jī)制，更加充分地利用了網(wǎng)絡(luò)的可用地址，增加路由節(jié)點(diǎn)能夠連接的子節(jié)點(diǎn)數(shù)。同時(shí),將16 bits短地址分段，引入了簇首段和區(qū)域段，使其適應(yīng)新算法，并保持了“地址—區(qū)域”的對(duì)應(yīng)關(guān)系。針對(duì)提出的地址分配機(jī)制，改進(jìn)了現(xiàn)有的Zig Bee網(wǎng)絡(luò)樹(shù)路由和AODVjr協(xié)議。

1 網(wǎng)絡(luò)模型構(gòu)建

1.1 模型定義

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

為便于研究，本文中定義了下列概念：

定義1 地址空間[6](address space)：指具有一定位數(shù)的地址集合，本文中指Zig Bee網(wǎng)絡(luò)的所有地址和各個(gè)區(qū)域段中的所有地址。

定義2 地址分段(address segmentation)：指將16 bits短地址按位數(shù)再分成前后2段，第一段稱為簇首段，第二段稱為區(qū)域段。

定義3 簇首段(cluster segmentation，CS)：Zig Bee網(wǎng)絡(luò)由多個(gè)邏輯區(qū)域組成，每個(gè)邏輯區(qū)域中有一個(gè)簇首，簇首節(jié)點(diǎn)地址就是該邏輯區(qū)域的簇首段地址。

定義4 區(qū)域段(regional segmentation，RS)：16 bits地址分段后，第二段中的位數(shù)構(gòu)成網(wǎng)絡(luò)的子地址空間，分配了該子地址空間中地址的節(jié)點(diǎn)在邏輯上處于同一個(gè)區(qū)域內(nèi)，擁有同一個(gè)簇首。

1.2 模型構(gòu)建

本文構(gòu)建的Zig Bee網(wǎng)絡(luò)結(jié)構(gòu)模型如圖1所示，圖中的每個(gè)六邊形區(qū)域表示一個(gè)區(qū)域段子地址空間，子地址空間的地址連續(xù)，每個(gè)區(qū)域段有一個(gè)簇首，分配一個(gè)簇首段地址，且每個(gè)區(qū)域子地址空間包含的地址數(shù)相同，所有的簇首節(jié)點(diǎn)組成了網(wǎng)絡(luò)的主框架結(jié)構(gòu)。如果簇首段分配了i位，則區(qū)域段占有16-i位，這時(shí)網(wǎng)絡(luò)中最多有2i個(gè)簇首，即有2i個(gè)區(qū)域段子地址空間，每個(gè)區(qū)域段子地址空間有216-i個(gè)連續(xù)的地址。表示網(wǎng)絡(luò)模型中最多可分布2i個(gè)六邊形，每個(gè)六邊形中有一個(gè)簇首節(jié)點(diǎn)Vc，簇首節(jié)點(diǎn)均具有路由能力。ZC協(xié)調(diào)器節(jié)點(diǎn)是特殊的簇首節(jié)點(diǎn)，用于開(kāi)始時(shí)組建網(wǎng)絡(luò)。網(wǎng)絡(luò)中的其它路由節(jié)點(diǎn)Vr和終端節(jié)點(diǎn)Ve分布在邏輯區(qū)域內(nèi)，與簇首節(jié)點(diǎn)構(gòu)成局部區(qū)域網(wǎng)絡(luò)。不同邏輯區(qū)域間的節(jié)點(diǎn)通信都要經(jīng)過(guò)簇首節(jié)點(diǎn)轉(zhuǎn)發(fā)，同一邏輯區(qū)域的節(jié)點(diǎn)通信，只在本邏輯區(qū)域內(nèi)建立路由。

圖1 邏輯區(qū)域分布的網(wǎng)絡(luò)模型示意圖

2 基于邏輯區(qū)域的地址分配算法

本文根據(jù)按需分配地址空間的思想，提出了基于邏輯區(qū)域的地址分配算法(logical regional address assignment，LRAA)。地址分配算法將16 bits地址位數(shù)分成2段，這樣就把整個(gè)地址空間分成了大小相同的連續(xù)區(qū)域片段。當(dāng)需要分配地址的時(shí)候，區(qū)域段的簇首節(jié)點(diǎn)分配地址給新加入的節(jié)點(diǎn)，或協(xié)調(diào)器分配一個(gè)區(qū)域段給新加入的具有路由能力的節(jié)點(diǎn)，并把其作為該區(qū)域段的簇首。

2.1 LRAA流程

LRAA流程包括初始化、地址請(qǐng)求、地址分配和區(qū)域段分配4個(gè)階段，具體流程如下:

1)初始化:網(wǎng)絡(luò)協(xié)調(diào)器將自己的地址設(shè)為0，并確定參數(shù)，簇首段CS、區(qū)域段RS和區(qū)域段中節(jié)點(diǎn)距簇首節(jié)點(diǎn)的最大跳數(shù)Lm，然后廣播組網(wǎng)消息。

2)地址請(qǐng)求:無(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ā)往所有鄰居節(jié)點(diǎn)。

3)地址分配:如果簇首節(jié)點(diǎn)收到其它節(jié)點(diǎn)的地址分配請(qǐng)求，首先查看自己的區(qū)域段中是否有可分配的地址，若有,則采用隨機(jī)地址分配機(jī)制分配地址；若無(wú),剩余地址則直接發(fā)送無(wú)地址分配的消息到分配地址請(qǐng)求節(jié)點(diǎn)。

4)如果節(jié)點(diǎn)無(wú)法獲得某個(gè)區(qū)域段的地址，則通過(guò)已知區(qū)域的簇首節(jié)點(diǎn)通知協(xié)調(diào)器為其分配一個(gè)新的區(qū)域段，當(dāng)然，只有具有路由能力的節(jié)點(diǎn)才能向協(xié)調(diào)器申請(qǐng)一個(gè)的區(qū)域段，因?yàn)樾枰?fù)責(zé)簇首的功能。

5)如果申請(qǐng)加入網(wǎng)絡(luò)的節(jié)點(diǎn)距最近簇首節(jié)點(diǎn)的跳數(shù)超過(guò)區(qū)域段設(shè)定的最大跳數(shù)Lm，但是能夠和已加入網(wǎng)絡(luò)中的節(jié)點(diǎn)通信，則該已加入網(wǎng)絡(luò)中的節(jié)點(diǎn)通過(guò)簇首節(jié)點(diǎn)向協(xié)調(diào)器申請(qǐng)一個(gè)新的區(qū)域段，并請(qǐng)求斷開(kāi)與源區(qū)域段中簇首節(jié)點(diǎn)的連接，成為新區(qū)域段中的簇首節(jié)點(diǎn)后接受申請(qǐng)加入網(wǎng)絡(luò)節(jié)點(diǎn)的連接。

2.2 LRAA路由

為了適應(yīng)新的網(wǎng)絡(luò)地址分配機(jī)制，本文改進(jìn)了AODVjr路由算法，將網(wǎng)絡(luò)中的AODVjr路由算法分成兩部分，分別是由簇首節(jié)點(diǎn)組成的主干網(wǎng)的路由和區(qū)域段中的路由。改進(jìn)后的路由協(xié)議主要步驟如下，為了便于分析，本文設(shè)定CS段的位數(shù)是8，RS段的位數(shù)也是8，則網(wǎng)絡(luò)中最多可以有256個(gè)區(qū)域段，每個(gè)區(qū)域段有256個(gè)地址。

1)在由簇首節(jié)點(diǎn)組成的主干網(wǎng)和邏輯區(qū)域段網(wǎng)絡(luò)中分別使用按需路由協(xié)議AODVjr建立路由，并動(dòng)態(tài)維護(hù)。主干網(wǎng)中建立路由時(shí)，收到路由請(qǐng)求RREQ包的非簇首節(jié)點(diǎn)不做處理；區(qū)域段中建立路由時(shí)，非該區(qū)域段中的節(jié)點(diǎn)收到RREQ包時(shí)不做處理。

2)地址為A的路由節(jié)點(diǎn)收到目的地址為D的數(shù)據(jù)分組時(shí)，計(jì)算地址A節(jié)點(diǎn)和目的節(jié)點(diǎn)是否屬于同一區(qū)域段。判斷的方法為

1111111100000000&A=1111111100000000&D.

(1)

3)如果式(1)成立，說(shuō)明節(jié)點(diǎn)A和節(jié)點(diǎn)D屬于同一個(gè)網(wǎng)絡(luò)，使用區(qū)域段中的AODVjr路由算法將分組發(fā)送到目的節(jié)點(diǎn)。目的節(jié)點(diǎn)不存在時(shí)，丟棄分組。非同一區(qū)域段的節(jié)點(diǎn)收到分組后，直接丟棄不予處理。

4)如果式(1)不成立，說(shuō)明目的節(jié)點(diǎn)D屬于其它的區(qū)域段，節(jié)點(diǎn)A通過(guò)區(qū)域段中的AODVjr路由算法先將分組轉(zhuǎn)發(fā)給自己所屬區(qū)域段的簇首節(jié)點(diǎn)Ac，簇首節(jié)點(diǎn)Ac通過(guò)主干網(wǎng)中的AODVjr路由算法將分組轉(zhuǎn)發(fā)到相應(yīng)的區(qū)域段，分組到達(dá)目的節(jié)點(diǎn)D所在區(qū)域段后，簇首節(jié)點(diǎn)再通過(guò)區(qū)域段中的AODVjr路由算法將分組轉(zhuǎn)發(fā)給目的節(jié)點(diǎn)D。如果目的節(jié)點(diǎn)不存在，則丟棄分組。

2.3 LRAA分析

LRAA具有隨機(jī)地址分配的靈活性，能夠充分地使用網(wǎng)絡(luò)地址，同時(shí)具有分布式地址分配的“地址—區(qū)域”關(guān)系，具有相同簇首段的節(jié)點(diǎn)分布在同一邏輯區(qū)域內(nèi)，由于協(xié)調(diào)器限定了區(qū)域中節(jié)點(diǎn)到簇首節(jié)點(diǎn)的最大跳數(shù)Lm，所以,在同一邏輯區(qū)域內(nèi)的節(jié)點(diǎn)在物理位置上也集中分布在小范圍區(qū)域內(nèi)。LRAA可有效控制網(wǎng)絡(luò)中路由查找包，處理位置頻繁變化的節(jié)點(diǎn)。LRAA更適用于節(jié)點(diǎn)分布均勻的網(wǎng)絡(luò)，當(dāng)網(wǎng)絡(luò)中某處的節(jié)點(diǎn)密度非常大時(shí)，可在此區(qū)域分配多個(gè)區(qū)域段，如圖1(a)中的S區(qū)域所示。由圖1可知,使用LRAA的網(wǎng)絡(luò)延展性好，能夠處理復(fù)雜的網(wǎng)絡(luò)。若出現(xiàn)極端的情況，例如:網(wǎng)絡(luò)節(jié)點(diǎn)處于一條線上，此時(shí)如果為每個(gè)節(jié)點(diǎn)分配一個(gè)區(qū)域段就會(huì)造成地址的浪費(fèi)，此時(shí)需要改變最大跳數(shù)Lm值，將這些節(jié)點(diǎn)可容納在一個(gè)區(qū)域段中。LRAA中簇首節(jié)點(diǎn)的維護(hù)開(kāi)銷大，易耗盡能量，可在區(qū)域段中指定其它合適路由節(jié)點(diǎn)為備用簇首節(jié)點(diǎn)，當(dāng)原簇首節(jié)點(diǎn)因?yàn)楸黄茐幕蚰芰亢谋M時(shí)，可與協(xié)調(diào)器協(xié)商啟用備用簇首節(jié)點(diǎn)，同時(shí),區(qū)域段中的路由由簇首節(jié)點(diǎn)的鄰居路由節(jié)點(diǎn)來(lái)維護(hù)，可降低對(duì)簇首節(jié)點(diǎn)存儲(chǔ)空間的需求。其次,16 bits地址中的CS段和RS段的具體分配對(duì)網(wǎng)絡(luò)性能的影響在算法中也沒(méi)有討論，這些問(wèn)題將在下一步工作中深入研究此問(wèn)題。

3 仿真實(shí)驗(yàn)

仿真實(shí)驗(yàn)中將DAAM算法和LRAA作為比較的參照，通過(guò)仿真實(shí)驗(yàn)比較二者之間在地址分配成功率、網(wǎng)絡(luò)穩(wěn)定性和算法效率等性能方面的差異。

3.1 仿真設(shè)置

仿真工具采用Omnet++，網(wǎng)絡(luò)覆蓋面積為400 m×400 m，網(wǎng)絡(luò)中路由節(jié)點(diǎn)數(shù)分別為500,1 000,2 000,4 000,8 000個(gè)，節(jié)點(diǎn)密度范圍為320 m～20 m2/個(gè)，節(jié)點(diǎn)在仿真區(qū)域中隨機(jī)均勻分布，協(xié)調(diào)器位于仿真區(qū)域的中心。節(jié)點(diǎn)的MAC層和物理層采用IEEE 802.15.4標(biāo)準(zhǔn)，節(jié)點(diǎn)通信距離設(shè)為35 m，網(wǎng)絡(luò)中具有路由能力的FFD節(jié)點(diǎn)與終端節(jié)點(diǎn)比例為1∶1，網(wǎng)絡(luò)協(xié)調(diào)器參數(shù)初始化CS=8,RS=8,Lm=5。每個(gè)仿真實(shí)驗(yàn)做50次，結(jié)果取平均值。

3.2 仿真結(jié)果

1)地址分配成功率

從圖2可看出，LRAA在五類網(wǎng)絡(luò)環(huán)境中的地址分配成功率均明顯高于DAAM算法，兩類算法的平均地址分配成功率最小差距也近20 %，LRAA高效的地址分配在于算法有效地利用了網(wǎng)絡(luò)地址，除了受網(wǎng)絡(luò)的短地址限制外，并不受其他參數(shù)的限制，更多節(jié)點(diǎn)能夠加入網(wǎng)絡(luò)。

圖2 地址分配成功率比較

2)控制報(bào)文開(kāi)銷

圖3說(shuō)明了LRAA的控制報(bào)文在各類網(wǎng)絡(luò)中均不大于DAAM算法，同時(shí)仿真實(shí)驗(yàn)驗(yàn)證了前面的理論分析。隨著網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的增加，LRAA的優(yōu)勢(shì)明顯的高于DAAM算法，原因是使用DAAM算法時(shí)，當(dāng)網(wǎng)絡(luò)規(guī)模變大，網(wǎng)絡(luò)中無(wú)法分配到地址的節(jié)點(diǎn)迅速增加，造成了多次的地址請(qǐng)求，出現(xiàn)了大量的控制報(bào)文,而網(wǎng)絡(luò)規(guī)模對(duì)LRAA的影響卻很小。

圖3 地址分配控制報(bào)文開(kāi)銷

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

圖4表明了LRAA的地址分配平均耗時(shí)整體上小于DAAM。原因在于DAAM算法中無(wú)地址的節(jié)點(diǎn)會(huì)多次向鄰居節(jié)點(diǎn)申請(qǐng)地址，增加了網(wǎng)絡(luò)地址分配的延時(shí)。當(dāng)網(wǎng)絡(luò)中的節(jié)點(diǎn)規(guī)模較小時(shí)，2種算法都能給所有節(jié)點(diǎn)分配地址，平均耗時(shí)差別不明顯，但當(dāng)網(wǎng)絡(luò)的規(guī)模變大時(shí)，LRAA的地址分配耗時(shí)明顯的低于DAAM算法。

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

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

本文提出了一種基于邏輯區(qū)域的按需地址分配算法——LRAA，當(dāng)需要加入網(wǎng)絡(luò)的節(jié)點(diǎn)無(wú)法找到合適的父節(jié)點(diǎn)時(shí)，就通知協(xié)調(diào)器再分配一塊新的區(qū)域段地址給網(wǎng)絡(luò)，算法的控制開(kāi)銷小，僅當(dāng)需要向協(xié)調(diào)器申請(qǐng)新的區(qū)域段時(shí)才發(fā)送請(qǐng)求地址塊包，算法同時(shí)使得節(jié)點(diǎn)具有“地址—區(qū)域”的特征，將區(qū)域段中的按需矢量路由算法和主干網(wǎng)的路由算法相分隔，避免由于AODVjr路由算法路由請(qǐng)求包的廣播引起網(wǎng)絡(luò)性能的下降。理論分析和仿真結(jié)果顯示:與DAAM算法相比，LRAA能夠充分的使用網(wǎng)絡(luò)地址，控制開(kāi)銷和網(wǎng)絡(luò)時(shí)延等性能均更加優(yōu)異。

參考文獻(xiàn):

[1]Zig Bee Specification Version 2008.Zig Bee Document 053474r

17[S].2008.

[2]Lin Shizhuang,Liu Jingyu,Fang Yanjun.ZigBee based wireless sensor networks and its applications in industrial[C]∥IEEE International Conference on Automation and Logistics,2007:1979-1983.

[3]Li Yanrui,Shi Haibin,Tang Biyu.Address assignment and routing protocol for large-scale uneven wireless sensor networks[C]∥Int′l Symposium on Computer Network and Multimedia Technolo-gy(CNMT),2009:1-4.

[4]Lü Yunfei.Research on address shortage in a tree based ZigBee network[C]∥Int’l Conf on Information Security and Intelligence Control (ISIC),2012:70-74.

[5]Pan Mengshiuan,Tsai ChiaHung,Tseng Yuchee.The orphan problem in Zig Bee wireless networks[J].IEEE Transactions on Mobile Computing,2009,8(11):1572-1584.

[6]Ren Zhi,Li Pengxiang,Fang Jun.Segmentation-based on-demand scalable address assignment for Zig Bee networks[C]∥IEEE Vehicular Technology Conference,2011:1-5.

[7]Fang M Q,Wang J,Xu X H.A preemptive distributed address assignment mechanism for wireless sensor networks[C]∥Proceedings of the 4th International Conference on Wireless Communications,Networking and Mobile Computing,2008:1-5.

[8]Li Y R,Shi H B.Address assignment and routing protocal for large-scale uneven wireless sensor networks[C]∥2009 International Symposium on Computer Network and Multimedia Techno-logy,2009:1-4.