林城譽(yù)，李擁軍，謝嶸

（1.華南理工大學(xué)數(shù)學(xué)學(xué)院，廣州510641；2.華南理工大學(xué)計(jì)算科學(xué)與工程學(xué)院，廣州510006）

0 引言

（1）無(wú)線傳感網(wǎng)絡(luò)

無(wú)線傳感網(wǎng)絡(luò)（Wireless Sensor Network）[1-2]是由某個(gè)監(jiān)測(cè)區(qū)域用于監(jiān)測(cè)風(fēng)速、溫度、濕度等一個(gè)個(gè)的傳感器以一種自組織的形式組成的網(wǎng)絡(luò)系統(tǒng)。無(wú)線網(wǎng)絡(luò)的自組織性表現(xiàn)在每個(gè)傳感器節(jié)點(diǎn)相互協(xié)調(diào)運(yùn)作，每個(gè)節(jié)點(diǎn)地位平等。LR-WPAN[3]是IEEE 802.15.4 為無(wú)線傳感網(wǎng)絡(luò)制定的新標(biāo)準(zhǔn)[4]，與其他的為藍(lán)牙、Wi-Fi 制定的無(wú)線網(wǎng)絡(luò)協(xié)議相比，LR-WPAN 更具備短距離、低功耗的特性，更適用于低成本高利用率的場(chǎng)景。

LR-WPAN 使用CSMA/CA[5-6]機(jī)制，用于協(xié)調(diào)傳感器節(jié)點(diǎn)在數(shù)據(jù)傳輸時(shí)的信道爭(zhēng)用，該機(jī)制盡可能地降低了網(wǎng)絡(luò)傳輸?shù)墓?。?duì)于準(zhǔn)備傳輸數(shù)據(jù)的節(jié)點(diǎn)設(shè)備，會(huì)先監(jiān)測(cè)目前的傳輸信道是否被其他節(jié)點(diǎn)占用，若空閑，會(huì)有一個(gè)延遲時(shí)間來(lái)避免若干個(gè)節(jié)點(diǎn)同時(shí)發(fā)出數(shù)據(jù)造成的沖突。然而，如果網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量增多，則會(huì)加重網(wǎng)絡(luò)的負(fù)載、加大整個(gè)網(wǎng)絡(luò)的節(jié)點(diǎn)關(guān)于信道爭(zhēng)用的沖突，則整個(gè)網(wǎng)絡(luò)的性能也會(huì)隨之下降。對(duì)于傳感節(jié)點(diǎn)的沖突，尤其是隱藏節(jié)點(diǎn)引起的沖突更值得去重視與解決。隱藏節(jié)點(diǎn)的沖突指的是若有兩個(gè)節(jié)點(diǎn)是隱藏關(guān)系（不能感知到對(duì)方），則有一個(gè)節(jié)點(diǎn)在感知到信道空閑之后開始發(fā)送數(shù)據(jù)，而另一個(gè)節(jié)點(diǎn)同時(shí)也向其協(xié)調(diào)器發(fā)送數(shù)據(jù)，由于信道的半雙工機(jī)制而引起數(shù)據(jù)傳輸?shù)臎_突。在網(wǎng)絡(luò)系統(tǒng)中，每個(gè)節(jié)點(diǎn)隨機(jī)分布，隱藏節(jié)點(diǎn)間的沖突發(fā)生幾率高達(dá)41%。這種頻繁發(fā)生在隱藏節(jié)點(diǎn)的沖突不僅會(huì)延遲數(shù)據(jù)包的傳輸?shù)竭_(dá)時(shí)間，還會(huì)進(jìn)一步降低整個(gè)系統(tǒng)的吞吐量和增加不必要的能量消耗。如何準(zhǔn)確地發(fā)現(xiàn)節(jié)點(diǎn)的隱藏關(guān)系和有效地消除它們之間的沖突，是一個(gè)亟待解決的問題。文獻(xiàn)[7-8]中提出一種分組策略，實(shí)時(shí)地采集節(jié)點(diǎn)間的沖突，根據(jù)節(jié)點(diǎn)的隱藏關(guān)系動(dòng)態(tài)地劃分為幾個(gè)競(jìng)爭(zhēng)沖突的組別，每個(gè)組內(nèi)的節(jié)點(diǎn)只能在規(guī)定的時(shí)間片內(nèi)向外傳輸數(shù)據(jù)，即使當(dāng)前時(shí)間片內(nèi)并沒有其他組的節(jié)點(diǎn)在發(fā)送數(shù)據(jù)。

（2）ZigBee 局域網(wǎng)協(xié)議

ZigBee[9-10]是一種基于IEEE 802.15.4 標(biāo)準(zhǔn)的低功耗LAN 協(xié)議。它具有體積小，成本低，功耗低，數(shù)據(jù)傳輸率低的特點(diǎn)，是無(wú)線短程通信領(lǐng)域的典型協(xié)議。Zig-Bee 網(wǎng)絡(luò)使用一個(gè)中心節(jié)點(diǎn)來(lái)協(xié)調(diào)整個(gè)網(wǎng)絡(luò)的通信，需要一種類似路由器將本地協(xié)議轉(zhuǎn)換為Internet 協(xié)議的功能。ZigBee 網(wǎng)絡(luò)中主要環(huán)節(jié)在于每個(gè)設(shè)備分配到有效的相應(yīng)的地址，主流的地址分配機(jī)制是Fang M 等人[11]提出的DAAM（Distributed Address Assignment Mechanism）機(jī)制，此機(jī)制在TI 協(xié)議棧中是默認(rèn)配置的，且該算法可以根據(jù)參數(shù)定制不同級(jí)別的地址。

（3）Bloom Filter

判斷數(shù)據(jù)是否存在，一般使用互斥的集合結(jié)構(gòu)來(lái)對(duì)數(shù)據(jù)去重和常數(shù)時(shí)間地獲取元素。隨著數(shù)據(jù)規(guī)模的增大，集合的內(nèi)存占用比例也逐漸增多，在其不是業(yè)務(wù)主功能的情況下，占用過多的內(nèi)存顯然是不合理的，Bloom Filter[12]就是一種減少內(nèi)存占用，可以在元素不存在的情況下返回確定的不存在，而由于可能存在的哈希沖突，對(duì)于判斷元素存在的情況會(huì)有誤判的小幾率。例如需要對(duì)URL 去重，使用多個(gè)哈希函數(shù)將URL映射到提前預(yù)估好的位數(shù)組中，將其位置置為1，若URL 在多個(gè)哈希函數(shù)映射之后在位數(shù)組中的位置都為1，則可以判定其為重復(fù)的。在Mutaf P 等人[13-14]的研究中，Bloom Filter 的誤判率已經(jīng)大大下降。

1 模型

本文討論了在無(wú)線傳感網(wǎng)絡(luò)下，LR-WPAN 的CSMA/CA 機(jī)制在節(jié)點(diǎn)間傳輸數(shù)據(jù)的信道控制管理機(jī)制，指出其在節(jié)點(diǎn)數(shù)量增多的情況下，基于隱藏節(jié)點(diǎn)關(guān)系而出現(xiàn)的傳輸沖突對(duì)整體網(wǎng)絡(luò)性能的重大損耗。本文基于此問題，考慮組建一個(gè)完整的ZigBee 局域網(wǎng)絡(luò)，提供完善的中心節(jié)點(diǎn)路由功能，提出可行的分組策略和基于Bloom Filter 的非隱藏關(guān)系節(jié)點(diǎn)的存儲(chǔ)方法，最終有效地解決了發(fā)生在隱藏節(jié)點(diǎn)間的沖突問題。

1.1 組建ZigBee網(wǎng)絡(luò)

發(fā)現(xiàn)無(wú)線傳感網(wǎng)絡(luò)中的節(jié)點(diǎn)隱藏關(guān)系的沖突，首先需要組建一個(gè)ZigBee 網(wǎng)絡(luò)。網(wǎng)絡(luò)中的中心節(jié)點(diǎn)負(fù)責(zé)協(xié)調(diào)網(wǎng)絡(luò)的各個(gè)節(jié)點(diǎn)，具有路由功能，管理子節(jié)點(diǎn)的入網(wǎng)。ZigBee 地址分配協(xié)議分配唯一的地址給加入的節(jié)點(diǎn)，具體地，ZigBee 地址分派公式如下：

其中An是以A 為父節(jié)點(diǎn)的第n 個(gè)子節(jié)點(diǎn)的地址，Cm是每個(gè)父節(jié)點(diǎn)擁有的子節(jié)點(diǎn)數(shù)，Lm是網(wǎng)絡(luò)的最大深度,Rm是子節(jié)點(diǎn)當(dāng)中有幾個(gè)具有路由功能。

1.2 分組策略

在組建好的網(wǎng)絡(luò)中，采用一種分組策略，可以快速地發(fā)現(xiàn)節(jié)點(diǎn)的隱藏關(guān)系和采取相應(yīng)的措施解決沖突問題。基本策略闡述如下：中心節(jié)點(diǎn)依次從A1～An發(fā)送廣播，收集每個(gè)子節(jié)點(diǎn)的響應(yīng)信息，其中發(fā)送地址來(lái)自中心節(jié)點(diǎn)，接收范圍為整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)，數(shù)據(jù)包包含子節(jié)點(diǎn)的地址Ai。每次發(fā)送bcRequestAlive1～bcRequest-Aliven 標(biāo)志檢測(cè)子節(jié)點(diǎn)存活狀態(tài)，使用centerBroadcastEnd 標(biāo)志最后收集各個(gè)節(jié)點(diǎn)發(fā)生沖突的詳情。具體地，當(dāng)發(fā)送bcRequestAlivei 后，每個(gè)子節(jié)點(diǎn)會(huì)開始網(wǎng)絡(luò)偵聽，并且需要節(jié)點(diǎn)i 的廣播應(yīng)答。節(jié)點(diǎn)i 以廣播的形式應(yīng)答childBroadcastAlivei，與i 節(jié)點(diǎn)不為隱藏關(guān)系的其他所有節(jié)點(diǎn)會(huì)記錄i 的存活狀態(tài)，而與i 節(jié)點(diǎn)為隱藏關(guān)系的子節(jié)點(diǎn)則收不到i 的廣播內(nèi)容。中心節(jié)點(diǎn)收到i 節(jié)點(diǎn)的應(yīng)答，再向所有節(jié)點(diǎn)廣播centerBroadcastAlivei消息，標(biāo)志i 節(jié)點(diǎn)存活的狀態(tài)。與i 節(jié)點(diǎn)不為隱藏關(guān)系的節(jié)點(diǎn)在收到centerBroadcastAlivei 消息，確定與i 的非隱藏關(guān)系，在自己的nearbloomfilter 記錄i 節(jié)點(diǎn)信息，相應(yīng)的與i 節(jié)點(diǎn)存在隱藏關(guān)系的節(jié)點(diǎn)也可以確定。最后子節(jié)點(diǎn)收到centerBroadcastEnd 消息后，整理nearbloomfilter 記錄，發(fā)送給中心節(jié)點(diǎn)。至此，中心節(jié)點(diǎn)可以確定節(jié)點(diǎn)間的非隱藏關(guān)系，按照算法對(duì)節(jié)點(diǎn)分組（一般不超過6 組），同時(shí)每個(gè)組i 會(huì)生成groupbloomfilteri記錄組內(nèi)節(jié)點(diǎn)地址。中心節(jié)點(diǎn)依次廣播組序號(hào)和groupbloomfilter 到所有子節(jié)點(diǎn)broadcaseGroup（i,groupbloomfilteri），子節(jié)點(diǎn)確認(rèn)自己所屬的組別。每個(gè)子節(jié)點(diǎn)確認(rèn)自己所屬的分組，之后每個(gè)節(jié)點(diǎn)使用分組通訊，只在自己的分組所對(duì)應(yīng)的時(shí)間片里發(fā)送報(bào)文。至此分組完成且有效解決隱藏關(guān)系節(jié)點(diǎn)間的沖突問題。

1.3 Bloom Filter數(shù)據(jù)壓縮

每個(gè)傳感器節(jié)點(diǎn)內(nèi)存有限，分組策略中的每個(gè)節(jié)點(diǎn)的非隱藏關(guān)系節(jié)點(diǎn)數(shù)量在隨機(jī)分布的無(wú)線傳感網(wǎng)絡(luò)中，對(duì)于每個(gè)節(jié)點(diǎn)來(lái)說是不均勻的，每個(gè)節(jié)點(diǎn)對(duì)非隱藏關(guān)系的存儲(chǔ)而占用的內(nèi)存也是不均勻的，有一定可能出現(xiàn)某些節(jié)點(diǎn)資源不足的情況，導(dǎo)致有些節(jié)點(diǎn)資源損耗過多，性能變差。而使用Bloom Filter 存儲(chǔ)非隱藏關(guān)系的節(jié)點(diǎn)信息，對(duì)與所有子節(jié)點(diǎn)，其所占用的內(nèi)存是明確的，不會(huì)出現(xiàn)某些節(jié)點(diǎn)需要消耗過多的內(nèi)存。具體地，若網(wǎng)絡(luò)中存在120 個(gè)節(jié)點(diǎn)，一個(gè)分組中就擁有80個(gè)節(jié)點(diǎn)，每個(gè)地址16 位，需要160 個(gè)字節(jié)，超過ZigBee協(xié)議傳輸幀關(guān)于最大字節(jié)只有127 字節(jié)的限制，而Bloom Filter 可以只使用100 字節(jié)，便能夠充分記錄組內(nèi)節(jié)點(diǎn)。然而Bloom Filter 在節(jié)點(diǎn)數(shù)目少的時(shí)候并不占優(yōu)勢(shì)，這是可預(yù)見的。

1.4 節(jié)點(diǎn)通信的時(shí)間復(fù)雜度

在只有一個(gè)中心節(jié)點(diǎn)，N 個(gè)傳感器節(jié)點(diǎn)的ZigBee 網(wǎng)絡(luò)中，從分組策略中可以得知每個(gè)節(jié)點(diǎn)都生成nearbloomfilter 記錄需要3N 次通信時(shí)間，中心節(jié)點(diǎn)接收到nearbloomfilter 則需要N 次通信時(shí)間，即在4N 次通信時(shí)間（復(fù)雜度為O（N））內(nèi)完成存在隱藏關(guān)系節(jié)點(diǎn)的發(fā)現(xiàn)。

2 實(shí)驗(yàn)

2.1 關(guān)于隱藏節(jié)點(diǎn)沖突關(guān)系發(fā)現(xiàn)與收集在ZigBee協(xié)議下的仿真實(shí)驗(yàn)

ZigBee 網(wǎng)絡(luò)初始化：首先選取中心節(jié)點(diǎn)作為整個(gè)網(wǎng)絡(luò)的協(xié)調(diào)器，協(xié)調(diào)器檢測(cè)信道并選取最佳信道。配置網(wǎng)絡(luò)具體參數(shù)，分配當(dāng)前網(wǎng)絡(luò)的唯一標(biāo)識(shí)符。

節(jié)點(diǎn)加入網(wǎng)絡(luò)：初始化完成后，當(dāng)前只有中心節(jié)點(diǎn)存在，當(dāng)其他節(jié)點(diǎn)加入網(wǎng)絡(luò)的時(shí)候，會(huì)選擇自己感應(yīng)到信號(hào)最強(qiáng)的節(jié)點(diǎn)作為父節(jié)點(diǎn)（剛開始是中心節(jié)點(diǎn)），加入成功后會(huì)獲得一個(gè)一個(gè)網(wǎng)絡(luò)地址。

本次實(shí)驗(yàn)使用20 個(gè)節(jié)點(diǎn)組成的ZigBee 網(wǎng)絡(luò)進(jìn)行仿真，假定每個(gè)節(jié)點(diǎn)最大偵聽范圍為500M，以中心節(jié)點(diǎn)為圓心，每個(gè)節(jié)點(diǎn)隨機(jī)分布，如圖1 所示。

每個(gè)節(jié)點(diǎn)被分配不同的地址，Bloom Filter 使用10字節(jié)存儲(chǔ)非隱藏關(guān)系節(jié)點(diǎn)信息，在一輪centerBroadcastEnd 后，中心節(jié)獲取記錄所有非隱藏關(guān)系的節(jié)點(diǎn)并且分組如表1 所示。

圖1 節(jié)點(diǎn)分布圖

表1 分組

同時(shí)使用Bloom Filter 記錄每個(gè)組的組內(nèi)節(jié)點(diǎn)地址，子節(jié)點(diǎn)通過groupbloomfilter 確認(rèn)自己是否在組中，分組圖如2 圖。

圖2 最終分組結(jié)果圖

2.2 實(shí)驗(yàn)結(jié)果說明與討論

本次通過仿真實(shí)驗(yàn)，觀察到每個(gè)節(jié)點(diǎn)的分布以及相應(yīng)的分組情況。通過對(duì)每個(gè)節(jié)點(diǎn)的分組進(jìn)行可視化，與實(shí)際節(jié)點(diǎn)是否為隱藏關(guān)系做比較，該分組算法正確地劃分了節(jié)點(diǎn)。通過對(duì)每個(gè)節(jié)點(diǎn)記錄數(shù)據(jù)所占用的內(nèi)存進(jìn)行數(shù)據(jù)分析，每個(gè)節(jié)點(diǎn)關(guān)于節(jié)點(diǎn)信息的記錄所占用的內(nèi)存是均衡的。在不使用Bloom Filter 的情況下，系統(tǒng)性能會(huì)有所下降。

3 結(jié)語(yǔ)

本文分析了隱藏節(jié)點(diǎn)在無(wú)線傳感網(wǎng)絡(luò)中的沖突問題，并具體闡述了一種分組算法，有效地劃分隱藏節(jié)點(diǎn)的關(guān)系，同時(shí)使用Bloom Filter 的數(shù)據(jù)壓縮功能進(jìn)一步解決具體環(huán)境中某些節(jié)點(diǎn)負(fù)載不均衡的問題，整體上是一套解決由隱藏節(jié)點(diǎn)沖突導(dǎo)致系統(tǒng)性能下降的問題的可行方案。