臺灣博碩士論文加值系統

隨著科技日新月異，現今無線裝置要搭配多網卡多頻道可說是比從前要容易許多。一般而言，在無線網狀網路裡，路由協定主要是替資料轉送選擇一條較合適的路徑，而每個路由協定一定也會搭配一個路由度量，好讓協定能夠從這麼多的路徑裡，選擇一條來使用。而所謂的路由度量則是指一條路徑上的花費，這個花費是一個可計算的值，路由協定會將這些值指派到路徑上藉以判斷這條路徑的好壞。至於要如何設計出一個有效的路由度量，必須視乎於目標網路的要求需要哪些限制或特色來決定。而在無線網路裡，頻道間的干擾對效能則是一個很重要的影響。

在現行的路由度量裡，有些能考量到路徑內部干擾，但卻沒捕捉到路徑間的干擾；有些路徑內部與路徑間的干擾都有考慮的，在實作方面又過於複雜。我們的方法不僅考慮路徑內部與路徑間的干擾，實作方面也較為容易，並適用在多網卡多頻道的環境裡。

我們提出一個能夠應用在多網卡多頻道的無線網路環境的方法叫MCAB。它的主要概念是藉由計算有效頻寬使得系統能夠選擇一條有較低總和延遲的路徑，畢竟這是多重網卡多重頻道的重要特色之一。除此之外，我們的方法也考慮了路徑間的干擾和路徑內部的干擾，能夠避開干擾較多的地方。最後，我們的模擬數據中指出，在頻道和網卡數增加時，MCAB確實能比其他方法要來的好些。

Now it becomes economically feasible to employ multiple radio interfaces and multiple channels in wireless communication devices. A routing protocol is responsible for finding multi-hop paths for forwarding data packets in wireless mesh networks. A routing protocol needs to use a routing metric to evaluate all possible routes between a pair of nodes and selects one for packets delivery. The design of effective routing metrics mainly depends on specific characteristics of the target network. Routing metric is a key element of a routing protocol, and it plays an important role in finding optimal paths for delivering packets to their destination nodes. Several routing metrics have been proposed for evaluating paths in wireless communication networks with MIMC capability. Some of them only consider intra-flow interference of a path, and they are not able to characterize the impact of inter-flow interference. Other metrics consider both intra-flow and inter-flow interference, but they are too complex to implement on wireless MIMC communication devices. In this thesis, we intend to present a new, cost-effective metric that can be easily implemented with considerably low computation complexity.

Our proposed routing metric is called MCAB (Multi-channel Available Bandwidth). It takes into account both inter-flow interference and intra-flow interference. More importantly, our metric can be efficiently implemented on wireless communication networks with MIMC devices. Using the metric, we can rapidly compute cumulative latency for all possible paths leading to the destination, and choose the one with the smallest latency as the routing path. This is crucial to efficient routing through MIMC communication networks. Our metric can accurately indicate those paths that come across high inter-flow and intra-flow interference. And this helps us avoid choosing paths through areas with high interference and bottlenecks as well. Simulation results show that the proposed metric can be effectively used to increase delivery ratio and minimize end-to-end delay, especially in the case that multiple interfaces are deployed.

誌謝 i
摘要 ii
Abstract iii
目錄 iv
圖目錄 v
表目錄 vi
1.1 簡介 1
1.2 研究動機與目的 2
1.3 論文架構 2
第二章　背景及相關文獻探討 3
2.1 Wireless Mesh Networks的背景及特點 3
2.2 Wireless Mesh Networks的架構 5
2.3 考慮鏈結品質之路由演算法 7
2.4 Multi-radio　Multi-channel　with　WMNs之相關研究 14
第三章　在WMNs裡考量多網卡多頻道的路由度量 18
3.1 基本假設與設計目標 18
3.2 MCAB　Routing　Metric 19
3.2.1 AODV　簡介 22
3.2.2 路由控制封包的修改 24
3.2.3 範例 28
第四章　實驗結果與分析 29
4.1 NS2簡介 29
4.2 參數設定 31
4.3 模擬結果 33
第五章　結論與未來研究工作 37
參考文獻 38

[1]V. Bhandari and N. H. Vaidya, "Connectivity and Capacity of Multi-Channel Wireless Networks with Channel Switching Constraints," in INFOCOM 2007. 26th IEEE International Conference on Computer Communications., 2007, pp. 785-793.
[2]P. Kyasanur and N. H. Vaidya, "Capacity of Multichannel Wireless Networks Under the Protocol Model," IEEE/ACM Transactions on Networking, vol. 17, pp. 515-527, 2009.
[3]W. Wang and X. Liu, "A framework for maximum capacity in multi-channel multi-radio wireless networks," 2006.
[4]M. Alicherry, R. Bhatia, and L. Li Erran, "Joint Channel Assignment and Routing for Throughput Optimization in Multiradio Wireless Mesh Networks," IEEE Journal on Selected Areas in Communications, vol. 24, pp. 1960-1971, 2006.
[5]L. Xiaojun and S. Rasool, "A Distributed Joint Channel-Assignment, Scheduling and Routing Algorithm for Multi-Channel Ad-hoc Wireless Networks," in INFOCOM 2007. 26th IEEE International Conference on Computer Communications, pp. 1118-1126.
[6]H. Pingshi and X. Ziping, "Channel assignment and routing in multi-channel, multi-interface wireless mesh networks," in 2010 2nd International Conference on Computer Engineering and Technology (ICCET), pp. V3-69-V3-74.
[7]W. M. N. 無線網狀網路, "http://www.gss.com.tw/index.php/eis/476."
[8]R. Bruno, M. Conti, and E. Gregori, "Mesh networks: commodity multihop ad hoc networks," Communications Magazine, IEEE, vol. 43, pp. 123-131, 2005.
[9]Y. Sooyeol, B. Youngmi, K. Junhyung, C. Keuchul, and H. Kijun, "A routing metric for load balance in wireless mesh networks," in 11th International Conference on Advanced Communication Technology, ICACT 2009, pp. 1560-1565.
[10]D. S. J. D. Couto, D. Aguayo, J. Bicket, and R. Morris, "A high-throughput path metric for multi-hop wireless routing," Wirel. Netw., vol. 11, pp. 419-434, 2005.
[11]R. Draves, J. Padhye, and B. Zill, "Routing in multi-radio, multi-hop wireless mesh networks," in Proceedings of the 10th annual international conference on Mobile computing and networking Philadelphia, PA, USA: ACM, 2004.
[12]K. Junhyung, Y. Jangkyu, Y. Mahnsuk, C. Keuchul, L. Honggil, and H. Kijun, "A routing metric based on Available Bandwidth in wireless mesh networks," in The 12th International Conference on Advanced Communication Technology (ICACT), 2010 pp. 844-849.
[13]A. Raniwala and C. Tzi-cker, "Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh network," in INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies., pp. 2223-2234 vol. 3.
[14]H. Pai-Hsiang, A. Hwang, H. T. Kung, and D. Vlah, "Load-balancing routing for wireless access networks," in INFOCOM 2001. Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies, pp. 986-995 vol.2.
[15]Y. Yang, J. Wang, and R. H. Kravets, "Designing routing metrics for mesh networks," in IEEE WiMesh, 2005.
[16]A. Raniwala, K. Gopalan, and T.-c. Chiueh, "Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks," SIGMOBILE Mob. Comput. Commun. Rev., vol. 8, pp. 50-65, 2004.
[17]Y. Yang, J. Wang, and R. Kravets, "Interference-aware load balancing for multihop wireless networks," University of Illinois at Urbana-Champaign, Tech. Rep, vol. 361702, 2005.
[18]X. Jing, L. Wei, Y. Zongkai, C. Jun, and C. Xiaohui, "A Delay-Aware Routing Metric for Multi-Radio Multi-Channel Wireless Mesh Networks," in 2010 6th International Conference on Wireless Communications Networking and Mobile Computing (WiCOM), , pp. 1-4.
[19]Y. Sook-Chin, T. Su-Wei, and C. Teong-Chee, "Data Rate-Aware Channel Assignment algorithm for multi-rate multi-channel wireless mesh networks," in Wireless and Pervasive Computing (ISWPC), 2011 6th International Symposium on, pp. 1-6.
[20]N. Hoang Lan and N. Uyen Trang, "Algorithms for bandwidth efficient multicast routing in multi-channel multi-radio wireless mesh networks," in Wireless Communications and Networking Conference (WCNC), 2011 IEEE, pp. 1107-1112.
[21]C. E. Perkins and E. M. Royer, "Ad-hoc on-demand distance vector routing," in WMCSA ''99. Second IEEE Workshop on Mobile Computing Systems and Applications, 1999, pp. 90-100.
[22]C. Lei and W. B. Heinzelman, "QoS-aware routing based on bandwidth estimation for mobile ad hoc networks," IEEE Journal on Selected Areas in Communications, vol. 23, pp. 561-572, 2005.
[23]R. A. Calvo, "Adding Multiple Interface Support in NS-2."
[24]P.-J. Wu, "NSG2," 2008/11/18.