臺灣博碩士論文加值系統

無線網狀網路提供企業與個人一個容易擴充和配置的網際網路存取
方案。進一步藉由多頻道與多天線的技術，無線網狀網路將可支援更
高的網路流量，以滿足現今越來越高的頻寬需求量。許多研究專注於
IEEE 802.11無線網狀網路的頻道分配與路由機制，探討此無線網路
可達到的頻寬增益與網路效能在理論上的限制。然而，IEEE 802.11
在資料傳輸頻寬與傳輸距離的限制下，並不適用於都會型的無線網狀
網路架構。本篇論文即針對下一代的無線寬頻last-mile網路連結：
IEEE 802.16無線都會型網路，提出一個適合IEEE 802.16無線都會型
網狀網路的速率調適頻道分配與路由演算機制。論文中將IEEE
802.16的TDMA特性納入考量。模擬結果顯示，所提出的速率調適頻道
分配機制與現今IEEE 802.11直接移植的方法比較，不但在頻道的使
用數量上較少，而且具有較高的頻道利用率。而在三個路由演算法的
比較上，提出的速率調適隨機多重路徑演算法善加利用了IEEE
802.16多重調變的性質，達到了整體上較高的網路吞吐量。

Wireless mesh networks provide an easy deployed and extensi-
ble solution to access Internet or communicate with each other for both
enterprises and individuals. With the help of multi-channel and multi-
radio, wireless mesh network can support more tra¢ c load to meet
higher and higher bandwidth requirement in this modern time. There
have been researches that focus on channel assignment and routing al-
gorithm for IEEE 802.11 multi-channel environment to achieve better
network throughout. However, the data rate and transmission range
of 802.11 is limited and is not suitable for a large area metropolitan
mesh network deployment. This thesis presents a rate-adaption chan-
nel assignment and routing algorithm for IEEE 802.16 multi-channel
multi-radio network in mesh mode which is expected as the last-mile
wireless broadband connectivity. We takes 802.16 TDMA characteris-
tic and modulation/rate adaption into consideration. The Simulation
results show that our channel assignment procedure uses fewer chan-
nels and better channel utilization than the migrated 802.11 greedy
approach. Among the three comparing routing protocols, our protocol
performs better in multi-rate 802.16 mesh network and results in higher
aggregate throughput.

1 Introduction 1
1.1 Multi-channel wireless networks . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Wireless mesh networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 The IEEE 802.16 standard . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Goal of the thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5 Thesis organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 Related Works 8
2.1 Multi-channel hidden terminal . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Multi-channel and multi-radio cooperation . . . . . . . . . . . . . . . . . . . 12
2.3 Multi-channel wireless mesh networks . . . . . . . . . . . . . . . . . . . . . 13
2.4 Routing Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.5 Cellular Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3 Proposed Scheme 18
3.1 IEEE 802.16 Control Messages . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2 Proposed Channel Assignment . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.3 Proposed Routing Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4 Simulation 27
4.1 Channel Usage and Utilization . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.2 RA-CA and RA-Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
5 Conclusion 37
Reference 39

[1] “WiMAX Forum”; http://www.wimaxforum.org/home
[2] IEEE 802.16 Presentation Submission Template (Rev. 8.3), 2005 July.
[3] IEEE Standard for Local metropolitan area networks. Part 16: Air Interface for Fixed
Broadband Wireless Access Systems, 2004 October.
[4] K. Jain. J. Padhye. V. N. Padmanabhan. L. Qiu; “Impact of interference on multi-hop
wireless network performance.”; Proc. ACM MobiCom, pp. 66-80, September 2003.
[5] A. Raniwala, K. Gopalan, T. Chiueh; “Centralized Channel Assignment and Routing
Algorithms for Multi-Channel Wireless Mesh Networks.”; ACM Mobile Computing and
Communication review, vol. 8, pp. 50-65, April 2004.
[6] A. Raniwala, K. Gopalan, T. Chiueh; “Architecture and Algorithms for an IEEE 802.11-Based Multi-Channel Wireless Network.”; INFOCOM, vol. 3, pp. 2223-2234
, March 2005.
[7] M. Alicherry, R. Bhatia, Li (Erran) Li; “Joint Channel Assignment and Routing for
Throughput Optimization in Multi-Radio Wireless Mesh Networks.”; MobiCom, pp.
58-72, August 2005.
[8] S. Yuan, S. Vannat, and J. P. Juex; “Minimum-Color Path Problems for Reliability in
Mesh Networks”; INFOCOM, Volume 4, pp. 2658-2669, March 2005.
[9] K. Ramachandran, E. Belding, K.Almeroh, M.Buddhikot; “Interference-Aware Chan-
nel Assignment in Multi-Radio Wireless Mesh Networks.”; (to appear) INFOCOM,
April, 2006.
[10] M. Kodialam, T. Nandagopal; “Characterizing the Capacity Region in Multi-Radio
Multi-Channel Wireless Mesh Networks.”; MobiCom, pp. 73-87, August 2005.
[11] V. Bahl, A. Adya, J. Padhye, A. Wolman. “Reconsidering wireless systems with mul-
tiple radios”; ACM SIGCOMM Computer Communication Review, vol.34, pp. 39-46,
October 2004.
[12] P. H. Hsiao, A. Hwang, H. T. Kung, and D. Vlah; “Load-Balancing Routing for Wireless
Access Networks”; INFOCOM, vol. 2, pp. 986-995, April 2001.
[13] A. Iwata, C.-C. Chiang, G. Pei, M. Gerla, and T.-W. Chen; "Scalable Routing Strate-
gies for Ad Hoc Wireless Networks"; IEEE JSAC, vol. 17, NO. 8, pp. 10-31, August
1999
[14] E.M. Royer and C-K Toh; "A Review of Current Routing Protocols for Ad Hoc Mobile
Wireless Networks"; IEEE Personal Communications, pp. 46-55, April 1999.
[15] K. Wu, J. Harms; "Performance Study of a Multipath Routing Method for Wireless
Mobile Ad Hoc Networks"; MASCOTS, pp. 99-107, Aug 2001.
[16] Lianfang Zhang, Zenghua Zhao, Yantai Shu, Lei Wang, and Oliver W.W. Yang; "Load
Balancing of Multipath Source Routing in Ad Hoc Networks"; Proc. of IEEE ICC, vol.
5, pp. 3197-3201, April 2002.
[17] S. Bak, J. A. Cobb, E. L. Leiss; "Load-Balanced Routing via Bounded Randomization";
PDCS, pp. 857-862, Oct. 1999.
[18] J. So, N. Vaidya; “Multi-Channel MAC for Ad Hoc Networks: Handling Multi-Channel
Hidden Terminals Using A Single Transceiver.”; MobiHoc, pp. 222-233, May 2004.
[19] S. Wu, C. Lin, Y. Tseng, J. Sheu; “A New Multi-Channel MAC Protocol with On-
Demand Channel Assignment for Multi-Hop Mobile Ad Hoc Networks.”; I-SPAN,
pp.232, 2000.
[20] N. Jain, S. R. Das, A. Nasipuri; “A Multichannel CSMA MAC Protocol with Receiver-
Based Channel Selection for MultihopWireless Networks.”; IC3N, pp. 432-439, October
2001.
[21] Z. Tang and J.J. Garcia-Luna-Aceves; “Hop-Reservation Multiple Access (HRMA) for
Ad-Hoc Networks.”; INFOCOM, vol. 1, pp. 194-201, May 1999.
[22] A. Tzamaloukas. J. J. Garcia-Luna-Aceves; “A Receiver-Initiated Collision-Avoidance
Protocol for Multi-channel Networks”; INFOCOM, vol. 1, pp. 189-198, April 2001.
[23] Y. Y. Huang, M. L. Molle; "An improved topology discovery algorithm for networks
with wormhole routing and directed link"; IEEE Computer Networks, pp. 98-105, Sept.
1997.
[24] R. Chandra, C. Fetzer, K. Hogstedt; "Adaptive Topology Discovery in Hybrid Wireless
Networks"; Informatics, vol. 16, pp. 1-16, Sept. 2002.
[25] K. C. Cla¤y, H.W. Braun, G. C. Polyzos; "A parameterizable methodology for Internet
tra¢ c ‡ow pro…ling"; IEEE JSAC, vol. 13, Issue 8, pp. 1481-1494, Oct. 1995.
[26] Y. J. Lin, M. C. Chan; "A Scalable monitoring approach based on aggregation and
re…nement"; IEEE JSAC, vol. 20, pp. 677-690, May 2002.
[27] J. Deng and Z. J. Haa; “Dual Busy Tone Multiple Access (DBTMA): A New Medium
Access Control for Packet Radio Networks.”; ICUPC, vol. 2, pp. 973-977, October
1998.
[28] T. R. Jensen, B. Toft; “Graph Coloring Problems”; Wiley Interscience, New York,
1995.
[29] G. L. Nemhauser and S. Park. A polyhedral approach to edge coloring. Operations
Research Letters 10 315-322, 1991.
[30] I. Katzela, M. Naghshineh; "Channel assignment schemes for cellular mobile telecom-
munication systems: a comprehensive survey"; IEEE Personal Communications, vol.
3, pp. 10-31, Jun 1996.