無線網格網路下的編碼認知性群播樹

Coding-Aware Multicast Trees in Wireless Mesh Networks

謝志鴻(Chih-Hung Hsieh)

指導教授 ： 廖婉君

國立臺灣大學/電機資訊學院/電信工程學研究所/碩士(2010年)

https://doi.org/10.6342/NTU.2010.10569

摘要

近年來無線網格網路(wireless mesh networks)逐漸躍升成為提供無線寬頻接取服務的關鍵技術。然而，隨著網路流量的增加，無線鏈結間的交互干擾將降低網路系統的容量。為了讓更多的使用者能享受網路服務，如何有效的使用網路資源變成一個重大的課題。網路編碼(network coding)[1]是增進網路使用率的熱門技術。奠基於網路編碼理論的COPE[2]是一種利用無線網路廣播特質的傳送結構，可以從本質上提升靜態無線網格網路的吞吐量。另一方面，群播樹(multicast trees)則是一種以最小成本傳遞相同訊息給多位使用者的傳輸策略，它同樣也能改善網路使用效率。基於上述理由，我們嘗試結合這兩種傳輸結構，希冀達到善用網路資源的目標。由於先前關於COPE型式的網路編碼研究中只鑽研於單播架構，因此我們將重新定義網路編碼條件以適用在群播情境。根據新定義的群播編碼條件，我們加入網路編碼的考量以建立最小成本群播樹。我們設計兩階段式的編碼認知性群播樹演算法，意使傳輸成本最小化。第一階段，我們在不考慮網路編碼的情況下，找出前n小成本樹。接著，第二階段的演算法在從這些候選群播樹中，挑出編碼認知性群播樹。最後，模擬結果也顯示，當群播結合上網路編碼後確實有助於網路容量的提升。

關鍵字

最小成本群播樹 ； 網路編碼 ； 編碼認知性路由 ； 編碼認知性群播樹 ； 群播樹演算法 ； 無線網格網路 ； 前n小成本樹

並列摘要

Over the past few years, wireless mesh networks (WMNs) have emerged as a key technology for wireless broadband access. However, as the traffic grows, interference between wireless links degrades the capacity in WMNs. Under the goal of providing more users to access the network, intelligent use of network resources becomes a major issue. Network coding [1] is a popular scheme to increase the network utilization. A recent approach, COPE [2] inspired by the theory of network coding is a forwarding architecture which takes advantage of wireless broadcast nature. It substantially increases the throughput of wireless mesh networks. Additionally, multicast is a transmission strategy that enable cost optimization of one-to-many sessions. It also has the ability to improve network capacity.In virtue of the above reasons, we combine multicast with network coding. Because the prior proposed works of COPE-type network coding only focus on unicast sessions, we need to define coding conditions for multicast sessions. Based on these conditions, we tackle the minimum cost multicast tree (MCMT) problem with network coding consideration. We design a two-phase approach to construct a “coding-aware” multicast tree. At the first phase, n minimum cost trees are found without the awareness of network coding. After that, the coding-aware multicast tree is chosen from the n candidates at the second phase. Finally, according to our simulation result, we show that it indeed increases the network capacity if we combine multicast with network coding.

並列關鍵字

MCMT ； network coding ； coding-aware routing ； multicast trees algorithm ； coding-aware multicast trees ； wireless mesh networks ； top-n minimum cost trees

參考文獻

[2] S. Katti, H. Rahul, W. Hu, D. Katabi, M. Medard and J.Crowcroft. “XORs in the Air: Practical Wireless Network Coding,” ACM SIGCOMM, 2006.

[3] B. Ni, N. Santhapuri, Z. Zhong, S. Nelakuditi, “Routing with Opportunistically Coded Exchanges in Wireless Mesh Networks,” IEEE WiMesh, 2006.

[4] Richard M. Karp , “Reducibility among combinational problem,” Complexity of computer Computations, 1975.

[5] J. E. Wieselthier, G. D. Nguyen, and A. Ephremides, “Energy-efficient broadcast and multicast trees in wireless networks,” Mobile Networks and Applications, vol. 7, pp. 481–492, 2002.

[6] P. M. Ruiz, A.F. Gomez-Skarmeta, “Heuristic algorithms for minimum bandwidth consumption multicast routing in wireless mesh networks,” ADHOC-NOW, 2005.