臺灣博碩士論文加值系統

近年來隨著網路技術與網路頻寬的大幅進步，多媒體影音的服務也愈來愈普及，即時視訊與隨選視訊更是在目前網路多媒體影音需求上佔有很大的部分。而隨著無線網狀網路的興起，更為寬頻網際網路存取服務與技術，提供了一種新的選擇，利用無線網狀網路來收看即時影音的使用者數目也隨之增加。因此，近年來有許多的研究人員紛紛發表在無線網狀網路（WMN, Wireless Mesh Network）面的應用及相關研究。在本論文中，在無線網狀網路上，我們將研究如何利用多頻道與多重無線電並配合無線廣播優勢(wireless broadcast advantage) 的方式，滿足群播的影音串流需求。當在無線網路上接收即時影音串流人數增多時，容易因為頻道的干擾以及傳輸路徑的影響，造成封包的遺失以及影音串流品質的下降。因此傳輸路徑的規劃與頻道分配演算法的設計成為了一個重要的議題。在大部分研究中，當進行影音串流傳輸時，多是以先規劃傳輸路徑後再進行頻道的分配為主，這會造成當規劃的路徑無法分配頻道時，在此路徑上的使用者就無法獲取影音串流服務，降低被服務的使用者數目。因此本研究提出以跨層設計結合路徑規劃與頻道分配同時進行的演算法The Load-based Routing and Channel Assignment，在確定可以分配頻道的情況下尋找較佳的路徑規劃，並以分配無干擾的頻道方式，希望提供高品質的影音串流且達到最大化接收此影音服務的使用者數目。

In recent years, with the advances in the internet technology and network bandwidth, multimedia services are more and more popular. Real-time videos and on-demand videos are in a large part of multimedia needs. The rising of wireless mesh networks provide a new option for broadband Internet access services and technology. A large amount of research work related to multimedia applications on wireless mesh networks has been published. The investigations conducted in this thesis study the problem of multicast routing and channel assignment for the multi-channel and multi-interface wireless mesh networks, where the wireless broadcast advantage is used to meet the needs of multicast streaming. When the numbers of people receiving real-time video streaming increases in wireless mesh networks, it is likely to increase packet loss rate and reduce the quality of stream because of transmission interference. Therefore, constructing interference-free multicast trees becomes an important issue. In most studies, they construct multicast trees first and then allocate channels. This approach may have many links deleted because the conflict-free channels are not available. As a result, the users whose connecting with the link cannot access the video streams. The number of users being served is then reduced. Therefore, we propose the cross-layer design algorithms named “The Load-based Routing and Channel Assignment”, in which multicast trees constructing procedure and channel assignment procedure are taken into considerations at the same time. The goal of this study is to provide high quality multimedia streaming and maximize the number of serviced users.

摘 要 II
ABSTRACT III
誌謝 IV
表目錄 VII
圖目錄 VIII
第一章 緒論 1
1.1 研究背景 1
1.2 研究動機與目標 3
1.3 論文貢獻 4
1.4 論文架構 5
第二章 文獻回顧與探討 7
2.1 群播路由 7
2.1.1 LMCM演算法 7
2.1.2 LOAD-BASED GREEDY演算法 9
2.2 頻道分配 11
2.3 跨層設計 13
第三章 研究方法 15
3.1 LRCA 演算法 17
3.2 計算負載值 19
3.3 尋找可共享頻道節點 21
3.4 分配頻道 22
3.5 檢測WBA 23
3.6 分配新頻道 23
3.7 檢查干擾 24
3.8 圖例驗證 26
第四章 模擬環境與軟體 31
4.1 模擬環境 31
4.2 模擬軟體 31
第五章 實驗數據與分析 38
5.1 正交與非正交評比 38
5.2 客戶端數目 39
5.3 吞吐量 41
5.4 封包遺失率 44
5.5 最長延遲時間 46
結論與未來發展 49
參考文獻 50

[1]新通訊：無線網狀網路，2011/6/30
http://www.2cm.com.tw/markettrend_content.asp?sn=0701011004.
[2]無線寬頻網路建設，2011/6/18
http://www.gss.com.tw/index.php/eis/476
[3]陳偉業,張政偉,黃淑玲,陳肇宏, “適用於無線網狀網路之跨層路由協定設計,” The 2009 Conference on Computer Science and Information Engineering Applications (CISE).
[4]黃韋璁，楊文霖， “使用Qualnet實驗分析無線網狀網路群播串流”， The 2011 Information Technologies, Applications and Management Conference (ITAMC)，2011/6/25，高雄義守大學.
[5]Wen-Lin Yang, “A Maximum-Revenue Multicast Routing Problem on Wireless Mesh Networks,” The 24th International Conference on Information Networking 2010 (ICOIN 2010), Jan. 2010, Busan, Korea
[6]I.F. Akyildiz, X. Wang, and W. Wang, ”Wireless mesh networks: a survey,” Computer Networks, 2005, vol. 47, pp. 445-487.
[7]Ashish Raniwala and Tzi-cker Chiueh, ”Architecture and Algorithms for an IEEE 802.11-based Multi-Channel Wireless Mesh Network,” IEEE INFOCOM, 2005, pp. 2223- 2234.
[8]Cheng, S.-M., Lin, Phone, Huang, D.-W. “A Survey on Radio Resource and Mobility Management for Wireless Mesh Network”.
[9]L. Kou, G. Markowsky and L. Berman, ”A Fast Algorithm for Steiner Trees,” Acta Infomatica, Spring-Verlag, 1981, vol.15, pp.141-145
[10]U.T Nguyen and J. Xu, “Multicast Routing in Wireless Mesh Networks: Minimum Cost Trees or Shortest Path Trees,” IEEE Communications Magazine, 2007, pp. 72-75.
[11]G. Zeng, B. Wang, Y. Ding, L. Xiao and M. Mutka, ”Multicast Algorithms for Multi-Channel Wireless Mesh Networks,” IEEE ICNP, 2007, pp. 1-10.
[12]P.M. Ruiz and A.F. Gomez-Skarmeta, ”Approximating Optimal Multicast Trees in Wireless Multihop Networks,” ISSC 2005, pp. 686-691.
[13]H.L. Nguyen and U.T. Nguyen, ”Minimum Interference Channel Assignment for Multicast in Multi-Radio Wireless Mesh Networks,” IWCMC’08, 2008, pp. 626-631.
[14]A. Mishra, E. Rozner, S. Banerjee, and W. Arbaugh. Exploiting partially overlapping channels in wireless networks: Turning a peril into an advantage. In ACM/USENIX Internet Measurement Conference, 2005.
[15]Wen-Lin Yang and Wei-Tsung Huang, “ The study of interference-free multicast using non-orthogonal channels for Multi-Radio and Multi-channel Wireless Mesh Networks,“ International Computer Symposium (ICS) , Dec. 2010, pp. 547-552, Tainan, Taiwan.
[16]Wen-Lin Yang and Cheng-Huang Tung, “An Interference-free Multicast for Mesh Networks with Directional Antennas,“ Proceedings of the First International Conference on Ubiquitous and Future Networks, June, 2009, pp. 171-176, HK; (IEL DL).
[17]A. Mishra, E. Rozner, S. Banerjee, and W.Arbaugh,“Exploiting partially overlapping channels in wireless networks: Turning a peril into an advantage,” ACM/USENIX Internet Measurement Conference, 2005.
[18]A. Raniwala, K. Gopalan, and T. Chiueh,“Centralized Channel Assignment and Routing Algorithms for Multi-Channel Wireless Mesh Networks,” ACM SIGMOBILE Mobile Computing and Communications Reviews, Apr. 2004, vol. 8,no, 2, pp. 50-65.
[19]Y. Chen, S. Liu, and C. Chen, “Channel Assignment and Routing for Multi-Channel Wireless Mesh Networks Using Simulated Annealing,” IEEE GLOBECOM, Nov.2006, pp. 1-5.
[20]S. Avallone and I. Akyildiz, “A Channel Assignment Algorithm for Multi-Radio Wireless Mesh Networks,” IEEE ICCCN, Aug. 2007, pp. 1034-1039.
[21]A. Raniwala and T. Chiueh, “Architecture and Algorithms for an IEEE 802.11-based Multi-Channel Wireless Mesh Network,” IEEE INFOCOM, March 2005, pp. 2223-2234.
[22]C. Lin and C. Chou, “Route-Aware Load-Balanced Resource Allocation for Wireless Mesh Networks,” IEEE WCNC, Mar. 2007, pp. 3093-3098.
[23]W. Fu, B. Xie, D. P. Agrawal, and A. kumar,“A Tree-based Channel Assignment Scheme for Wireless Mesh Networks, ” IEEE MASS, Oct. 2007, pp. 1-6.
[24]J.-W. Ding, W.-T. Wang, and C.-T. Wang, ”An Efficient Data Replication Scheme for Peer-to-Peer Video Streaming Over Wireless-Mesh Community Networks, “ IEEE International Conference on Intelligent Information Hiding and Multimedia Signal Processing, 2008, pp767-770.
[25]F. Akyildiz, et. al., “NeXt Generation / Dynamic Spectrum Access / Cognitive Radio Wireless Networks: A Survey,” Computer Networks Journal （Elsevier）, vol. 50, 2006, pp. 2127-2159
[26]J.A. Stine, “Cross-Layer Design of MANETs：The Only Option,” in Proc. IEEE MILCOM 2006,” Washington, 2006, pp. 1-7.
[27]W. Su and T. L. Lim, “Cross-Layer Design and Optimization for Wireless Sensor Networks,” Proceedings of the 7th ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/ Distributed Computing（ SNPD） , 2006, pp. 278-284.
[28]V. Srivastava and M. Motani, “Cross-Layer Design : A Survey and the Road Ahead,” IEEE Communications Magazine, vol. 43, no. 12, pp. 112-119
[29]J. Tang, G. Xue, and W. Zhang, “Interference- Aware Topology Control and QoS Routing in Multi-Channel Wireless Mesh Networks,” in Proc. MobiHoc 2005, Urbana-Champaign, IL, , 2005 pp. 68-77.
[30]M. Jahanshahi, M. Dehghan, M.R. Meybodi “A Mathematical Formulation for Joint Channel Assignment and Multicast Routing in Multi-channel Multi-radio Wireless Mesh Networks” J Network Comput Appl(2011), doi:10.1016/j.jnca.2011.01.003.
[31]Cheng H, Yang S. ”Joint QoS Multicast Routing and Channel Assignment in Multiradio Multichannel Wireless Mesh Networks Using Intelligent Computational Methods” International Journal of Applied Soft Computing 2011;11(2):1953-64.
[32]Vanessa Gardellin, Sajal K. Das, Luciano Lenzini, Claudio Cicconetti, Enzo Mingozzi, “G-PaMeLA: A Divide-and-Conpuer Approach for Joint Channel Assignment and Routing in Muitl-radio Multi-channel Wireless Mesh Networks” journal Parallel Distribution Computing 71(2011),381-396.
[33]Wei-Tsung Huang and Wen-Lin Yang, “A Study on Cross-layer Design for Constructing Interference-free Multicast Trees in Wireless Mesh Networks, “The 7th International Workshop on Wireless, Ad hoc and Sensor Networks (WASN)”, 2011
[34]NCYUns, NCTUns 6.0 Network Simulator and Emulator，2011/6/21
http://nsl.csie.nctu.edu.tw/nctuns.html
[35]K. Fall, K. Varadhan, The ns Manual, http://www.isi.edu/nsnam/ns, April 2002
[36]NS2.Notebook: Multi-channel Multi-interface Simulation in NS2 (2.29)，2011/6/10
http://www.cse.msu.edu/~wangbo1/ns2/nshowto8.html
[37]Multicast Extensions of AODV (MAODV)，2011/6/10
http://www.hynet.umd.edu/research/maodv/MAODV-UMD.html
[38]QualNet 5.0.2，2011/6/25 http://www.scalable-networks.com/products/qualnet/