臺灣博碩士論文加值系統

無線網狀網路(Wireless Mesh Networks)因為具有建置容易跟成本低廉的優點，已成為目前熱門的廣域無線網路接取技術。本論文所討論的無線網狀網路為兩階層式的架構，包含用戶接取端(Access Tier)及骨幹接取端(Backhaul Tier)。用戶接取端主要負責無線網路用戶和骨幹網路間的傳輸；而骨幹接取端則是負責網狀網路節點間的資料傳遞並連接至網際網路。為了達到服務品質保證，我們針對不同的議題進行研究以提升網路品質傳輸。
在用戶接取端，我們提出新的差異性服務模型稱之為per-CLAss Flow fixed proportional differentiated service model (CLAF)，來確保每個服務等級中的資料流都能有固定的頻寬分配比率，根據傳統IEEE 802.11的架構，我們提出可調式競爭時框(contention window)以確保頻寬分配；此外，我們所提出的差異性服務模型更可搭配允入控制(admission control)來支援網路電話等即時應用之服務。
在骨幹接取端，我們研究TCP在多重跳躍無線網路(multi-hop wireless networks)上的行為，清楚定義多重跳躍無線網路中著名的隱藏終端問題(hidden terminal problem)與暴露終端問題(exposed terminal problem)，並利用模擬的方式呈現這兩個問題對於TCP效能的影響。為避免無線網路的傳輸競爭與干擾及考慮到TCP不對稱流量的特性，我們提出分時多工存取排程(spatial TDMA scheduling)來提升TCP的效能。

Wireless mesh networking technology is currently receiving a great deal of attention because it offers a promising solution to the challenges presented by next generation networks. In this dissertation, the Infrastructure/Backbone Wireless Mesh Network with access tier that connects the client wireless device to a mesh node and the backhaul tier that interconnects the mesh nodes to forward traffic to and from wireline Internet entry points or gateway mesh nodes is considered. To fulfill the quality of service guarantee in the two-tier wireless mesh access networks, different issues on the access and backhaul tier are addressed.
In the access tier, we propose a new per-CLAss Flow fixed proportional differentiated service model (CLAF) and a companioning medium access control scheme for multi-service wireless LANs (WLANs), based on the IEEE 802.11 framework. Different from conventional differentiated services, CLAF provides a) policy-based fixed proportional differentiated service; b) such fixed proportional service differentiation is on per-class flow basis; and c) each class contention window size is adjusted to reflect the actual traffic load of the class.
In the backhaul tier, we analyze how the multi-hop hidden terminal and exposed terminal problems affect the TCP throughput performance in multi-hop wireless networks via simulations. It shows that the performance interference due to the hidden and exposed terminal problems between wireless links is location-dependent. Therefore, based on the spatial reuse properties and considering the asymmetric traffic load of TCP connections, we propose spatial TDMA scheduling algorithm to resolve channel access contentions and thus improve the TCP performance in multi-hop wireless networks. The simulation results show that the proposed spatial TDMA scheduling algorithm can achieve better throughput performance. Since there is no channel interference within wireless links, the end-to-end TCP throughput is limited by the available bandwidth as expected.

Chapter 1 Introduction 1
1.1 Two-Tier Wireless Mesh Access Networks 1
1.2 Motivation 3
1.3 Organization of the Dissertation 7
Chapter 2 A New per-CLAss Flow Fixed Proportional Differentiated Service 9
2.1 Preliminaries 9
2.2 CLAF – The per-CLAss Flow Fixed Proportional Differentiated Service Model 14
2.3 The Medium Access Control 15
2.3.1 Baseline Intra-Class Channel Access Procedure 15
2.3.2 Inter-Class Channel Access Scheme 16
2.3.2.1 The Size of the Class Contention Window 16
2.3.2.2 The Class Frame and Coordination Periods 17
2.3.3 Channel Access and Packet Scheduling at a Wireless Station 18
2.3.4 Procedure for Flow Joint and Leave 22
2.3.5 Base Contention Window Function 23
2.4 Performance Evaluations 26
2.4.1 Fixed Proportional Bandwidth Differentiation 26
2.4.2 Performance Comparison with IEEE 802.11e EDCA 28
2.4.3 VoIP over Wireless LAN 29
2.5 Support of Real-time Traffic 31
2.5.1 Call Admission Control 32
2.5.2 Improvement (multiple contention periods) 36
2.6 Summary 42
Chapter 3 TCP Performance in Multi-hop Wireless Networks 44
3.1 Preliminaries 44
3.2 The Properties of Multi-Hop Wireless Communication Networks 47
3.2.1 Carrier Sense, Transmission and Interference Ranges 47
3.2.2 The Hidden Terminal Problem 50
3.2.3 The Exposed Terminal Problem 52
3.3 On-Way Wireless TCP Transmission 53
3.3.1 HTP Failure Count and ETP Count 56
3.3.2 HTP Contention Pattern Failure Count 57
3.3.3 MAC Frame Analysis 58
3.3.4 Summary 62
3.4 Two-Way Wireless TCP Transmissions 63
3.4.1 HTP Contention Pattern Failure Count 63
3.4.2 MAC Frame Analysis 64
3.5 Spatial Reuse Property 69
3.6 Performance Improvement Approaches 71
3.7 Summary 77
Chapter 4 TCP Throughput Enhancement in Multi-hop Wireless Networks 79
4.1 Preliminaries 79
4.2 Network Model and Assumptions 83
4.2.1 Interference Model 83
4.2.1.1 Protocol Model 83
4.2.1.2 Physical Model 84
4.2.2 Spatial Reuse in TDMA-based Wireless Networks 85
4.3 Problem Definition 87
4.3.1 Normalized Bandwidth Ratio 88
4.4 Spatial TDMA Scheduling Algorithm 90
4.4.1 System Model 92
4.4.2 Spatial TDMA Scheduling Algorithm 94
4.5 Performance Evaluations 97
4.6 Summary 101
Chapter 5 Conclusions 103
References 106

[1] IEEE Std 802.16-2004: Air Interface for Fixed Broadband Wireless Access Systems, October 2004.
[2] IEEE Std 802.11-1997: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications, June 1997.
[3] IEEE Std 802.11a-1999: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications, High-speed Physical Layer in the 5 GHZ Band, September 1999.
[4] IEEE Std 802.11b-1999: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications, Higher-Speed Physical Layer Extension in the 2.4 GHz Band, September 1999.
[5] IEEE Std 802.11g-2003: Amendment 4: Further Higher Data Rate Extension in the 2.4 GHz Band, June 2003.
[6] IEEE Std 802.11e-2005: Amendment 8: Medium Access Control (MAC) Quality of Service Enhancements, November 2005.
[7] Qiang Ni, “Performance Analysis and Enhancements for IEEE 802.11e Wireless Networks,” IEEE Networks, Vol. 19, No. 4, July-Aug. 2005, pp. 21-27.
[8] Xiang Chen, Hongqiang Zhai, Xuejun, and Yuguang Fang, “Supporting QoS in IEEE 802.11e Wireless LANs,” IEEE Trans. on Wireless Communications, Vol. 5, No. 8, Auguest 2006, pp. 2217-2227.
[9] Juha Heinanen, Fred Baker, Walter Weiss, and John Wroclawski, “RFC 2597: Assured Forwarding PHB Group,” IETF Network Working Group, June 1999.
[10] Imad Aad and Claude Castelluccia, “Differentiation Mechanisms for IEEE 802.11,” Proc. IEEE INFOCOM 2001, Anchorage, AK, April 2001, pp. 209-218.
[11] Jiunn Deng and Ruay-Shiung Chang, “A Priority Scheme for IEEE 802.11 DCF Access Method,” IEICE Trans. Communications, Vol. E82-B, No. 1, Jan. 1999, pp.96-102.
[12] Wasan Pattara-Atikom, Sujata Banerjee and Prashant Krishnamurthy, “Starvation Prevention and Quality of Service in Wireless LANs,” Proc. 5th International Symposium on Wireless Personal Multimedia Communications (WPMC 2002), Honolulu, Hawaii, Oct. 2002, pp. 1078-1082.
[13] Michael Barry, Andrew T. Campbell, and Andras Veres, “Distributed Control Algorithm for Service Differentiation in Wireless Packet Networks,” Proc. IEEE INFOCOM 2001, Anchorage, AK, April 2001, pp. 22-26.
[14] Kanghee Kim, Aftab Ahmad and Kiseon Kim, “A Wireless Multimedia LAN Architecture Using DCF with Shortened Contention Window for QoS Provisioning,” IEEE Communications Letters, Vol. 7, No. 2, February 2003, pp. 97-99.
[15] Albert Banchs and Xavier Pérez, “Providing Throughput Guarantees in IEEE 802.11 Wireless LAN,” Proc. IEEE Wireless Communications and Networking Conference (WCNC 2002), Orlando, FL, March 2002, pp. 130-138.
[16] Albert Banchs and Xavier Pérez, “Distributed Weighted Fair Queuing in 802.11 Wireless LAN,” Proc. IEEE International Conference Communications (ICC 2002), New York, April. 2002, pp. 3121-3127.
[17] Nitin Vaidya, Seema Gupta, and Paramvir Bahl, “Distributed Fair Scheduling in a Wireless LAN,“ IEEE Trans. on Mobile Computing, Vol. 4, No. 6, Nov/Dec 2005, pp. 616-629.
[18] S. Jamaloddin Golestani, “A Self-Clocked Fair Queueing Scheme for Broadband Applications, “Proc. IEEE INFOCOM 1994, Toronto, June 1994, pp. 636-646.
[19] M. Shreedhar and George Varghese, “ Efficient Fair Queueing Using Deficit Round Robin, “ IEEE/ACM Trans. on Networking, Vol. 4, No. 3, June 1996, pp. 375-385.
[20] Constantinos Dovrolis and Parameswaran Ramanathan, “A Case for Relative Differentiated Services and the Proportional Differentiation Model,” IEEE Network, Vol. 13, No. 5, Sep/Oct 1999, pp. 26-34.
[21] Andrew Odlyzko, “Paris Metro Pricing: The Minimalist Differentiated Services Solution,” Proc. IEEE/IFIP International Workshop on Quality of Service (IWQoS 1999), London, UK, June 1999, pp. 159-161.
[22] Alan Demers, Srinivasan Keshav, and Scott Shenker, “Analysis and Simulation of a Fair Queueing Algorithm,” Proc. ACM SIGCOM 1989, Austin, Texas, Sept. 1989, pp. 1-12.
[23] Abhay K. Parekh, and Robert G. Gallager, “A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: The Single-Node Case,” IEEE/ACM Trans. on Networking, Vol. 1, No. 3, June 1993, pp. 344-357.
[24] Jon C. R. Bennett and Hui Zhang, “Hierarchical Packet Fair Queueing Algorithm,” IEEE/ACM Trans. on Networking, Vol. 5, No. 5, Oct. 1997, pp. 675-689.
[25] Constantinos Dovrolis, and Dimitrios Stiliadis, “Relative Differentiated Services in the Internet: Issues and Mechanism,” Proc. ACM SIGMETRICS 1999, Atlanta, Georgia, May 1999, pp. 204-205.
[26] Network Simulator ns-2, <http://www.isi.edu/nsnam/ns/>
[27] Hongqiang Zhai, Xiang Chen, and Yuguang Fang, “How Well can the IEEE 802.11 Wireless LAN Support Quality of Service?,” IEEE Trans. on Wireless Communications, Vol. 4, No. 6, Nov 2005, pp. 3084-3094.
[28] Mario Gerla, Rajive Bagrodia, Lixia Zhang, Ken Tang, and Lan Wang, “TCP over Wireless Multi-hop Protocols: Simulation and Experiments,” Proc. IEEE International Conference Communications (ICC 1999), Vancouver, Canada, June 1999, pp. 1089-1094.
[29] Gavin Holland and Nitin Vaidya, “Analysis of TCP Performance over Mobile Ad Hoc Networks,” Proc. ACM MOBICOM 1999, Seattle, Washington, USA, August 1999, pp. 219-230.
[30] Kaixin Xu, Sang Bae, Sungwook Lee, and Mario Gerla, “TCP Behavior across Multihop Wireless Networks and the Wired Internet,” Proc. 5th International Workshop on Wireless Mobile Multimedia (WoWMoM 2002), Atlanta, Georgia, September 2002, pp. 41-48.
[31] Theodore S. Rappaport, Wireless Communications: Principles and Practice. New Jersey: Prentice Hall, 1996.
[32] Kaixin Xu, Mario Gerla, and Sang Bae, “How Effective is the IEEE 802.11 RTS/CTS Handshake in Ad Hoc Networks?,” Proc. IEEE Global Telecommunications Conference (GLOBECOM 2002), Taipei, Taiwan, November 2002, pp.72-76.
[33] Jitendra Padhye, Victor Firoiu, Don Towsley, and Jim Kurose, “Modeling TCP Throughput: A Simple Model and its Empirical Validation,” Proc. ACM SIGCOMM 1998, Vancouver, Canada, September 1998, pp. 303-314.
[34] Kai Chen. , Yuan Xue, Samarth H. Shah, and Klara Nahrstedt, “Understanding Bandwidth-delay Product in Mobile Ad Hoc Networks,” Elsevier Computer Communications Journal, Special Issue on Protocol Engineering for Wired and Wireless Networks, vol. 27, no. 10, 2004, pp. 923-934.
[35] Eitan Altman and Tania Jiménez,” Novel Delayed ACK Techniques for Improving TCP Performance in Multihop Wireless Networks”, Proc. Personal Wireless Communications (PWC 2003), Venice, Italy, September 2003, pp. 237-253.
[36] Mark Allman, “On the Generation and Use of TCP Acknowledgments,” ACM SIGMCOMM Computer Communication Review, Vol. 28, No, 5, Oct. 1998, pp.4-21.
[37] Ruy de Oliveira and Torsten Braun, “A Dynamic Adaptive Acknowledgment Strategy for TCP over Multihop Wireless Networks,” Proc. IEEE INFOCOM 2005, Miami, March 2005, pp. 1863-1874.
[38] Ruy de Oliveira and Torsten Braun, “A Smart TCP Acknowledgment Approach for Multihop Wireless Networks,” IEEE Trans. on Mobile Computing, Vol. 6, No. 2, Feb. 2007, pp. 192-205.
[39] Carlos de M. Cordeiro, Samir R. Das, and Dharma P. Agrawal, “COPAS: Dynamic Contention-Balancing to Enhance the Performance of TCP over Multi-hop Wireless Networks,” Proc. International Conference Computer Communications and Networks (ICCCN 2002), Miami, October 2002, pp.14-16.
[40] Zhenghua Fu, Haiyun Luo, Petros Zerfos, Lixia Zhang, and Mario Gerla, “The Impact of Multihop Wireless Channel on TCP Performance,” IEEE Trans. Mobile Computing, Vol. 4, No. 2, March/April 2005, pp. 209-221.
[41] Alex Varshavsky and Eyal de Lara, “Alleviating Self-Interference in MANETs,” Proc. 29th Annual IEEE International Conference on Local Computer Networks (LCN 2004), Tampa, FL, USA, November 2004, pp. 642-649.
[42] Sherif M. ElRakabawy, Alexander Klemm, and Christoph Lindemann, ”TCP with Adaptive Pacing for Multihop Wireless Networks,” Proc. ACM MOBIHOC 2005, Urbana-Champaign, Illinois, USA, May 2005, pp. 288-299.
[43] Mark Allman, Vern Paxson, and W. Richard Stevens, “RFC 2581: Transmission Control Protocol”, IETF Network Working Group, April 1999.
[44] Robert Braden, “RFC 1122: Requirements for Internet Hosts -- Communication Layers”, IETF Network Working Group, October 1989.
[45] Hari Balakrishnan, and Venkata N. Padmanabhan, “How Network Asymmetry Affects TCP,” IEEE Communications Magazine, April 2001, pp. 60-67.
[46] Subir Varma, “Performance and Buffering Requirements of TCP Applications in Asymmetric Networks,” Proc. IEEE INFOCOM 1999, New York, NY, USA, March 1999, pp. 1548-1555.
[47] T. V. Lakshman, Upamanyu Madhow, and Bernhard Suter, “Window-based Error Recovery and Flow Control with a Slow Acknowledgement Channel: A Study of TCP/IP Performance,” Proc. IEEE INCOFOM 1997, Kobe, Japan, April 1997, pp. 1199-1209.
[48] T. V. Lakshman, Upamanyu Madhow, and Bernhard Suter, “TCP/IP Performance with Random Loss and Bidirectional Congestion,” IEEE/ACM Trans. On Networking, Vol. 8, No. 5, October 2000, pp. 541-555.
[49] Van Jacobson, “Congestion Avoidance and Control,” Proc. ACM SIGCOMM 1988, Stanford, CA, August 1998, pp. 314-329.
[50] IEEE, “802.11 TGs ESS Mesh Networking proposal,” IEEE, Protocol Proposal IEEE 802.11-05/0575r3, September 2005.
[51] Piyush Gupta and P. R. Kumar, “The Capacity of Wireless Networks,” IEEE Trans. on Information Theory, Vol. 46, No. 2, March 2000, pp. 388-404.
[52] Randolph Nelson and Leonard Kleinrock, “Spatial TDMA: A Collision-free Multihop Channel Access Protocol,” IEEE Trans. Communications., Vol. 33, No. 9, September 1985, pp. 934-944.
[53] Ewa Kubicka and Allen J. Schwenk, “An Introduction to Chromatic Sums,” Proc. ACM Computing Science Conference (CSC 1989), Louisville, Kentucky, USA, February 1989, pp. 39-45.
[54] Amotz Bar-Noy, Mihir Bellare, Magnús M. Halldórsson, Hadas Shachnai, and Tami Tamir, “On Chromatic Sums and Distributed Resource Allocation,” Information and Computation, Vol. 140, No. 2, February 1998, pp. 183-202.
[55] F.T. Leighton, “A Graph Coloring Algorithm for Large Scheduling Problems,” Journal of Research of the National Bureau of Standards, Vol. 84, No. 6, 1979, pp. 489-506.
[56] Daniel Brélaz, “New methods to color the vertices of a graph,” Communications of the ACM, Vol. 22, No. 4, April 1979, pp. 251-256.
[57] J. Randall Brown, “Chromatic Scheduling and the Chromatic Number Problem,” Management Science, Vol. 19, No. 4, Application Series, Part 1, 1972, pp. 456-463.
[58] A. Hertz, “A Fast Algorithm for Coloring Meyniel Graphs,” Journal of Combinational Theory, Series B, Vol. 8, 1990, pp. 231-240.