隱藏節(jié)點沖突的發(fā)現(xiàn)與研究

林城譽，李擁軍，謝嶸

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

0 引言

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

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

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

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

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

（3）Bloom Filter

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

1 模型

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

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

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

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

1.2 分組策略

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

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

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

1.4 節(jié)點通信的時間復(fù)雜度

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

2 實驗

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

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

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

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

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

圖1 節(jié)點分布圖

表1 分組

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

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

2.2 實驗結(jié)果說明與討論

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

3 結(jié)語

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