隱藏節點沖突的發現與研究

林城譽，李擁軍，謝嶸

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

0 引言

（1）無線傳感網絡

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

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

（2）ZigBee 局域網協議

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

（3）Bloom Filter

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

1 模型

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

1.1 組建ZigBee網絡

發現無線傳感網絡中的節點隱藏關系的沖突，首先需要組建一個ZigBee 網絡。網絡中的中心節點負責協調網絡的各個節點，具有路由功能，管理子節點的入網。ZigBee 地址分配協議分配唯一的地址給加入的節點，具體地，ZigBee 地址分派公式如下：

其中An是以A 為父節點的第n 個子節點的地址，Cm是每個父節點擁有的子節點數，Lm是網絡的最大深度,Rm是子節點當中有幾個具有路由功能。

1.2 分組策略

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

1.3 Bloom Filter數據壓縮

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

1.4 節點通信的時間復雜度

在只有一個中心節點，N 個傳感器節點的ZigBee 網絡中，從分組策略中可以得知每個節點都生成nearbloomfilter 記錄需要3N 次通信時間，中心節點接收到nearbloomfilter 則需要N 次通信時間，即在4N 次通信時間（復雜度為O（N））內完成存在隱藏關系節點的發現。

2 實驗

2.1 關于隱藏節點沖突關系發現與收集在ZigBee協議下的仿真實驗

ZigBee 網絡初始化：首先選取中心節點作為整個網絡的協調器，協調器檢測信道并選取最佳信道。配置網絡具體參數，分配當前網絡的唯一標識符。

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

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

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

圖1 節點分布圖

表1 分組

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

圖2 最終分組結果圖

2.2 實驗結果說明與討論

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

3 結語

本文分析了隱藏節點在無線傳感網絡中的沖突問題，并具體闡述了一種分組算法，有效地劃分隱藏節點的關系，同時使用Bloom Filter 的數據壓縮功能進一步解決具體環境中某些節點負載不均衡的問題，整體上是一套解決由隱藏節點沖突導致系統性能下降的問題的可行方案。