實現及實測在無線網狀網路中廣播演算法

Abstract

氾濫式廣播機制已經被證實在多節點跳躍無線網路上造成嚴重的廣播風暴問題，而此問題在無線網狀網路中變得更為嚴重。由於無線網狀網路介接有線區域網路，使得區域網路的廣播封包流入無線網路，造成更嚴重的碰撞機率。此外，無線網狀網路使用連結層廣播傳遞許多網路控制、路由、拓樸維持協定。因此，其對於廣播可靠性的要求也更高。已經有許多廣播演算法以提高有效性及可靠性而被提出，但鮮少在真實系統上被驗證。在本文中，我們研究五種具有代表性的廣播演算法，包括基於機率、基於延遲、使用鄰居資訊等方法。我們討論這些演算法在實作上的問題，並在真實系統上實現它們。此外，針對不同的拓樸及封包大小，透過實驗比較各演算法的可靠度、轉送機率與效益。不同於以往模擬結果中氾濫式廣播機制較為可靠，我們的研究結果顯示由於碰撞機率較輕微，Self-Pruning演算法可提供最可靠的廣播。另外，當同時考量可靠度與轉送機率時，Domain-Pruning演算法提供最佳的廣播效益。最後，以機率為基礎的演算法則因為過低的可靠性，不論在何種情況下皆不建議被使用。

Broadcasting by flooding has been proved to cause broadcast storm problems in the multi-hops wireless networks, and it becomes more serious in a wireless mesh network (WMN). Due to bridging the wired LAN in WMN, the amount of broadcast traffic increases and the collision probability raises. In addition, the broadcast reliability is more important in WMN where the protocols of network-controlling, routing and topology maintaining are directly designed with layer-2 broadcast. Many algorithms have been developed for efficient and reliable broadcasting, though those approaches are seldom verified in the real world. In this work, we study five representative broadcast algorithms including the probability-based algorithms, delay-based algorithms and the algorithms using neighbor information. We discuss the common and algorithm-specific implementation issues, and implement them on the real-world testbed. The reliability, forwarding ratios and efficiencies are compared through experiments under different topologies and packet lengths. Different from the simulation results, in which the flooding approach performs better than others, our study shows that the self-pruning algorithm resulting in the best reliability due to its lighter collision probability. In addition, the domain-pruning algorithm always performs the best efficiency over others when taking both the reliability and forwarding ratios into consideration. Finally, the probability-based algorithms are not suggested in any situations due to its worst reliability.