無線網格網路之效能分析與設計決策

Location-Dependent Network Performance and Design Strategies in Wireless Mesh Networks

劉得煌(Tehuang Liu)

指導教授 ： 廖婉君

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

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

摘要

無線網格網路(Wireless Mesh Networks, WMNs)因為具有較低的前期佈建和維護成本，以及具有可靠性較高的網路架構和服務覆蓋範圍，近年來受到諸多的關注。研究報告指出在此種網路中，結點的產率(throughput)和延遲(delay)皆隨著位置(location)的不同而變化。雖然已經有非常多的學術論文在分析無線多重跳躍網路(multi-hop wireless networks)中的產率和延遲，但其大多數都是侷限在漸近分析(asymptotic analysis)上。然而，現實生活中的網路應用關注的卻是實值的產率和延遲表現，而不是漸近分析所得來的效能表現趨勢。因此，本論文旨在分析無線網格網路中每個結點的實值產率和延遲表現。
首先，我們考慮單一通道(single-channel)的無線網格網路。我們採用一個一般性的網路模型。基於此網路模型，我們分析每個中繼結點(relaying node)上的封包進出速率，並由此推導出每個結點所能得到的產率和所感受到的封包延遲。我們進而分析網路的效能表現(如產率、延遲和平等性)是如何受到模型中的參數所影響。此外，我們提出兩個網路設計決策(network design strategies)以達到平等產率(fair throughputs)和最小化封包延遲。電腦模擬的結果顯示我們所提出的分析模型可以精準地預測每個結點的產率和延遲表現，而且我們所提出的網路設計決策皆能有效地且正確地達到目標。
本論文的第二部份旨在延伸我們的分析模型，使其能夠應用於多天線多通道(multi-radio multi-channel) 的無線網格網路中。在多天線多通道的環境中，每個結點可以有多個天線，而每個天線操作在不同的通道上。每個天線的操作通道由通道配置(channel assignment)所決定。在我們的網路模型中，我們假設通道配置是已知的一個參數。基於這樣的假設，我們推導出每個結點所能得到的產率和所感受到的封包延遲。我們藉由電腦模擬來驗證我們的分析。結果顯示我們的分析模型可以精準地預測每個結點的產率和延遲表現。此外，我們也示範如何藉由我們的分析模型來調查通道配置可能對網路效能表現所造成的問題。本論文不但提供了一個針對無線網格網路的效能分析模型，並且幫助我們更深入了解無線網格網路在應用上面臨到的設計議題。

關鍵字

無線網格網路 ； 多天線多通道 ； 產率 ； 延遲 ； 效能分析 ； 網路設計決策

並列摘要

Wireless mesh networks (WMNs) have received much attention in recent years due to their desirable features such as low up-front cost, easy network maintenance, robustness, and reliable service coverage. Previous work shows that throughput and delay for each node in such a network vary with the location of the node. While many papers have been devoted to analyzing the throughput and delay performance in multi-hop wireless networks, most of them are focused on asymptotic cases. Since most of the applications in real-world networks are concerned about the exact network performance rather than the asymptotic performance, in this dissertation, we model the exact location-dependent throughput and delay for each node in WMNs.
We start by considering single-channel WMNs. Based on a general network model, we analyze the packet arrival rate and the packet departure rate for the forwarding queues of each relaying node in the network, and then derive the per-user throughput and the end-to-end packet delay for each node. We also study the effects of the network design parameters in our model on the location-dependent network performance in terms of throughput, delay, and fairness. In particular, two network design strategies are proposed to provide fair throughputs and minimize the end-to-end packet delay in WMNs, respectively. We conduct simulations to validate the correctness of our analytical model and evaluate the performance of the proposed network design strategies. The simulation results show that our analytical model can precisely predict the location-dependent throughput and delay for each node and that the proposed network design strategies are effective.
In the second part of this dissertation, we generalize our analysis to multi-radio multi-channel (MRMC) environments. In an MRMC WMN, nodes can communicate with each other using non-overlapping channels, and each node is equipped with multiple radios, which are tuned to different channels according to the channel assignment. Given the channel assignment as an input parameter of our model, we derive the location-dependent throughput and delay for each node in MRMC WMNs. The simulation results show that our model can accurately predict the location-dependent performance for each node in MRMC WMNs. Furthermore, we demonstrate how to utilize our analytical model to investigate the impact of channel assignments on the network performance.
This dissertation not only provides a theoretical framework for studying the location-dependent network performance in WMNs but also gives insight into the network design strategy for WMNs.

並列關鍵字

Wireless Mesh Networks ； Multi-Radio Multi-Channel ； Throughput ； Delay ； Performance Analysis ； Network Design Strategies

參考文獻

[1] R. Karrer, A. Sabharwal, and E. Knightly, “Enabling Large-scale Wireless Broadband: The Case for TAPs,” ACM HotNets, Nov. 2003.

[2] F. Akyildiz, X. Wang, and W. Wang, “Wireless Mesh Networks: A Survey,” Computer Networks Journal, Mar. 2005.

[3] R. Bruno, M. Conti, and E. Gregori, “Mesh Networks: Commodity Multihop Ad Hoc Networks,” IEEE Communications, Mar. 2005.

[4] M. J. Lee, J. Zheng, Y.-B. Ko, and D. M. Shrestha, “Emerging Standards for Wireless Mesh Technology,” IEEE Wireless Communications, Apr. 2006.

[5] V. Gambiroza, B. Sadeghi, and E. W. Knightly, “End-to-End Performance and Fairness in Multihop Wireless Backhaul Networks,” ACM MOBICOM, Sep. 2004.