臺灣博碩士論文加值系統

使用無線網狀網路（wireless mesh networks）作為新一種無線寬頻存取技術時，使用者預期該網路應有龐大的網路傳輸容量（network capacity throughput）。由於無線傳輸廣播的特性，在此種網路下，同時傳輸的無線訊號之間的相互干擾（interference）會對整體網路傳輸容量造成很大的影響，對一個無線傳輸而言，訊號干擾愈嚴重的話，其可使用之傳輸速度就愈低。
對於無線網狀網路而言，其網路傳輸容量由傳輸速度高低與同時傳送資料的基地台數量這兩個因素來決定。因此，提升網路傳輸容量最好的辦法就是提高傳輸速度以及提高同時傳送資料的基地台數量；然而，無線傳輸在高的速度之下較無法抵抗干擾，因此當提高傳輸速度時，我們無可避免的必須要減少同時傳送資料的基地台數量。因此對於（1）提高傳輸速度以及（2）增加同時傳送資料的基地台數量這兩個選擇我們只能擇其一，無法同時達到兩者。
在本論文中，假設使用切時分工多重存取（time division multiple access）、分散式資料傳輸排程、以及實體干擾模型之無線網狀網路下，我們探討這兩種選擇結果對網路傳輸容量的影響並找出達成最大網路傳輸容量的選擇。

The wireless mesh network is expected to provide large transmission capacity in order to serve as a complementary broadband wireless access technology. The interference plays an important role to the network capacity throughput of wireless mesh networks because when there are multiple concurrent wireless transmissions in a mesh network, the interference caused by the broadcast nature of wireless transmissions decreases the sustainable spectral efficiency (transmission speed) of each individual transmission.
For a wireless mesh network, the network capacity throughput is determined by two factors: the individual transmission spectral efficiency and the number of concurrent transmissions. Therefore, the best way to increase the network capacity throughput is to increase both the individual transmission spectral efficiency as well as the number of concurrent transmissions. However, if we increase the individual transmission spectral efficiency, inevitably we have to reduce the number of concurrent transmission because we must keep interference low to make higher spectral efficiency feasible. Thus the choice between (1) increasing the transmission spectral efficiency and (2) increasing the number of concurrent transmissions is a trade-off and is critical to the network capacity throughput.
In this paper, we explore the tradeoff between these two choices in a TDMA (time division multiple access) based distributed data access scheduler wireless mesh network with physical interference model and find the optimal design that achieves highest network capacity throughput.

謝詞 I
論文摘要 II
關鍵詞：網路傳輸容量、IEEE 802.16、WiMAX、無線網狀網路、實體干擾模型 II
THESIS ABASTRACT III
Contents V
List of Tables VIII
List of Figures IX
Chapter 1 Introduction 1
1.1. Wireless Mesh Network 1
1.2. Motivation and Goal 1
1.3. Thesis Organization 3
Chapter 2 Literature Survey 4
2.1 Interference Models 4
2.2 Transmission Concurrency on CSMA Networks 5
2.3 Transmission Concurrency on TDMA Networks 6
Chapter 3 The Network Model 8
3.1 Three-way-handshake Data Access Scheme 8
3.2 Level-n Clean Air Spatial Reuse Scheme 10
3.2.1. Level-n Neighbors 10
3.2.2. Network Utilization: ρ 11
3.2.3. Level-n Clean Air Spatial Reuse Condition 12
3.3 Receiver’s Signal to Interference Power 13
3.3.1. Receiver’s Signal Threshold and Capture Threshold 13
3.3.2. The Interference 14
3.4 Transmission Spectral Efficiency 17
3.4.1. The Shannon’s Channel Capacity Theorem 17
3.4.2. The Real Product’s Requirements 18
3.5 Tradeoff between Interference and Number of Concurrent Transmissions in WMNs 19
3.6 Frame Structure and Example of How the Scheduling Algorithm Works 20
3.6.1. A Simple Example 21
3.6.2. Static TDM and Dynamic TDM 24
3.7 Distributed Data Scheduling: The Three-way-handshake Algorithm 29
3.8 Expected Data Slots Schedule 32
3.8.1. Distance between Two Transmission Pairs 32
3.8.2. Distance between Two Sets of Transmission Pairs 33
3.8.3. Expected Data Slots Schedule When the WMN is Always Backlogged 34
3.9 Control Slots Schedule that Realize the Expected Data Slots Schedule 44
3.10 Calculating the Channel Rates of Data/Control Slots 59
Chapter 4 Performance Evaluations 61
4.1. Always Backlogged WMNs – Shannon’s spectral efficiency assumption 62
4.2. Always Backlogged WMNs – WiMAX forum’s spectral efficiency assumption 64
4.3. Network Capacity Throughput under Different Offered Load 66
4.4. Network Capacity Throughput with Perturbed SSs 68
4.5. Multihop Traffic Experiment 70
Chapter 5 Conclusions 73
References 74

[1]IEEE Std 802.16-2004 (Revision of IEEE Std 802.16-2001), “IEEE Standard for Local and Metropolitan Area Networks--Part 16: Air Interface for Fixed Broadband Wireless Access Systems,” 2004
[2]IEEE Std 802.16e-2005 and IEEE Std 802.16-2004/Cor1-2005 (Amendment and Corrigendum to IEEE Std 802.16-2004), “IEEE Standard for Local and Metropolitan Area Networks--Part 16: Air Interface for Fixed Broadband Wireless Access Systems--Amendment 2: Physical and Medium Access Control Layers for Combined Fixed and Mobile Operation in Licensed Bands and Corrigendum 1,” 2005
[3]http://www.wimaxforum.org/
[4]Tae-Suk Kim, Hyuk Lim, Jennifer C. Hou, “Improving Spatial Reuse through Tuning Transmit Power, Carrier Sense Threshold, and Data Rate in Multihop Wireless Network,” MobiCom’06
[5]Harish Viswanathan, Sayandev Mukherjee, “Throughput-Range Tradeoff of Wireless Mesh Backhaul Networks,” IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, VOL. 24, NO. 3, MARCH 2006
[6]Gurashish Brar, Douglas M. Blough, Paolo Santi, “Computationally Efficient Scheduling with the Physical Interference Model for Throughput Improvement in Wireless Mesh Networks,” MobiCom’06
[7]Anindya Basu, Brian Boshes, Sayandev Mukherjee, Sharad Ramanathan, “Network Deformation: Traffic-Aware Algorithms for Dynamically Reducing End-to-end Delay in Multi-hop Wireless Networks,” MobiCom’04
[8]Piyush Gupta, P.R. Kumar, “The Capacity of Wireless Networks,” IEEE Transactions on Information Theory, 2000, 46(2):388-404
[9]Benyuan Liu, Zhen Liu, Don Towsley, “On the Capacity of Hybrid Wireless Networks,” IEEE INFOCOM’03.
[10]Theodore S. Rapport, Wireless Communications Principles and Practice, Prentice Hall, 1998
[11]Andrea Goldsmith, Wireless Communications, Cambridge University Press, 2005.
[12]Andrew S. Tanenbaum, Computer Networks, Fourth Edition, Prentice Hall, 2002
[13]Marvin K. Simon, Mohamed-Slim Alouini, Digital Communication over Fading Channels, Wiley-IEEE Press, 2 edition, 2004
[14]H. Vincent Poor, Gregory W. Wornell, Wireless Communications: Signal Processing Perspectives, Prentice Hall, 1st edition, 1998
[15]Randolph Nelson, Leonard Klienrock, “Spatial TDMA: A Collision Free Multihop Channel Access Protocol,” IEEE Trans. on Comm., Vol. Com-33, No. 9, Sep 1985
[16]Shin-Ming Cheng, Di-Wei Huang, Phone Lin, Shun-Ren Yang, “A Study on Distributed/Centralized Scheduling for Wireless Mesh Network,” IWCMC 2006
[17]H-Y. Wei, S. Ganguly, R. Izmailov, and Z.J. Haas. “Interference-Aware IEEE 802.16 WiMax Mesh Networks,” In 61st IEEE Vehicular Technology Conference (VTC 2005 Spring), Stockholm, Sweden, May 29-June1, 2005
[18]A. Kabbani, T. Salonidis, and E. Knightly, "A Distributed Low-Complexity Maximum-Throughput Scheduler for Wireless Backhaul Networks," in Proceedings of IEEE INFOCOM 2007, Anchorage, AK, May 2007
[19]Jianfeng Chen, Caixia Chi, Qian Guo, “An Odd-Even Alternation Mechanism for Centralized Scheduling in WiMAX Mesh Network,” GLOBECOM 2006
[20]Hongqiang Zhai, Yuguang Fang, “Physical Carrier Sensing and Spatial Reuse in Multirate and Multihop Wireless Ad Hoc Networks,” INFOCOM 2006
[21]Cisco aironet 802.11a/b/g wireless LAN client adapters (CB21AG and PI21AG) installation and configuration guide. Cisco Systems, Inc., 2004
[22]K. Fall and K. Varadhan (Ed.), The ns-2 Manual, Technical Report, The VINT Project, UC Berkeley, LBL, and Xerox PARC, 2003.
[23]Sherif M. ElRakabawy, Alexander Klemm, and Christoph Lindemann, “TCP with Adaptive Pacing for Multihop Wireless Networks”, MobiHoc’05
[24]Zhenghua Fu, Haiyun Luoy, Petros Zerfos, Songwu Lu, Lixia Zhang, Mario Gerla, “The Impact of MultihopWireless Channel on TCP Performance,” IEEE Transactions on Mobile Computing, 2005
[25]Ruy de Oliveira, Torsten Braun, “A Dynamic Adaptive Acknowledgment Strategy for TCP over Multihop Wireless Networks,” INFOCOM 2005