請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/46988完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 林永松(Frank Yeong-Sung Lin) | |
| dc.contributor.author | Martin Yung-Pin Tsai | en |
| dc.contributor.author | 蔡永斌 | zh_TW |
| dc.date.accessioned | 2021-06-15T05:44:43Z | - |
| dc.date.available | 2010-08-20 | |
| dc.date.copyright | 2010-08-20 | |
| dc.date.issued | 2010 | |
| dc.date.submitted | 2010-08-19 | |
| dc.identifier.citation | [1] I. F. Akyildiz, X. Wang and W. Wang, “Wireless Mesh Networks: a Survey,” Computer Networks, Vol. 47, Issue 4, Pages 445-487, March 2005.
[2] P. Gupta and P. R. Kumar, “The Capacity of Wireless Networks,” IEEE Transactions on information theory, Vol. 46, No. 2, Pages 388-404, 2000. [3] B. Li, “End-to-End Fair Bandwidth Allocation in Multi-Hop Wireless Ad Hoc Networks,” Proc. IEEE ICDCS’05. [4] V. Gambiroza, B. Sadeghi and E. W. Knightly, “End-to-End Performance and Fairness in Multihop Wireless Backhaul Networks,” Proc. ACM MobiCom, Pages 287-301, Sept.-Oct. 2004. [5] Y. F. Wen and Frank Y. S. Lin, “The Top Load Balancing Forest Routing in Mesh Networks”, Proc. IEEE CCNC, pages 468-472, Jan. 2006. [6] A. Tang, J. Wang and S. H. Low, “Counter-Intuitive Throughput Behaviors in Networks Under End-to-End Control,” IEEE Transactions on Networking, Vol. 14, No. 2, Pages 355-368, April 2006. [7] IEEE Standard, “Draft STANDARD for Information Technology- Telecommunications and information exchange- between systems- Local and metropolitan area networks- Specific requirements- Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications,” March 2009. [8] L. Kleinrock and J. Silvester, “Optimum Transmission Radii for Packet Radio Networks or Why Six Is A Magic Number,” Proc. IEEE National Telecommunications Conference, Pages 4.3.1-4.2.5, December 1978. [9] E. M. Royer, P. M. M. Smith and L. E. Moser, “An Analysis of the Optimum Node Density for Ad hoc Mobile Networks,” Proc. IEEE ICC, Vol. 3, Pages 857-861, June 2001. [10] J. Gomez and A. T. Campbell, “Variable-Range Transmission Power Control in Wireless Ad Hoc Networks,” IEEE Transaction on Mobile Computing, Vol. 6, No. 1, Pages 87-99, January 2007. [11] H. Yu, P. Mohapatra and X. Lin, “Channel Assignment and Link Scheduling in Multi-Radio Multi-Channel Wireless Mesh Networks,” Mobile Networks and Applications, Vol. 13, Issue 1-2, Pages 169-185, April 2008. [12] Y.F. Wen, F.Y.S. Lin, Y.C. Tzeng and C.T. Lee, 'Backhaul Assignment and Routing Algorithms with End-to-End QoS Constraints for Wireless Mesh Networks', Springer Wireless Personal Communications, Feb. 2009. [13] J. Tang, G. L. Xue and W. Y. Zhang, “Cross-Layer Optimization For End-To-End Rate Allocation in Multi-Radio Wireless Mesh Networks,” Wireless Networks, Vol. 15, No. 1, January 2009. [14] M. Kodialam and T. Nandagopal, “Characterizing the Capacity Region in Multi-Radio Multi-Channel Wireless Mesh Networks,” Proc. MobiCom’05. [15] W. Wang and X. Liu, “A Framework for Maximum Capacity in Multi-channel Multi-radio Wireless Networks,” Proc. IEEE CCNC’06. [16] X. Y. Li, A. Nusairat, Y. Wu, Y. Qi, J. Zhao, X. Chu and Y. Liu, “Joint Throughput Optimization for Wireless Mesh Networks,” IEEE Transactions on Mobile Computing, Vol. 8, Issue 7, Pages 895-909, July 2009. [17] J. Zhang and X. Jia, “Capacity analysis of wireless mesh networks with omni or directional antennas,” Proc. INFOCOM’09. [18] D. Bertsekas and R. Gallager, “Data network (2nd edition),” 1992. [19] A. Giannoulis, T. Salonidis and E. Knightly, “Congestion Control and Channel Assignment in Multi-Radio Wireless Mesh Networks,” Proc. IEEE SECON’08. [20] W. Fu, Y. Wang and D. P. Agrawal, “Delay and Capacity Optimization in Multi-radio Multi-channel Wireless Mesh Networks,” Proc. IEEE IPCCC’08. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/46988 | - |
| dc.description.abstract | 無線網狀網路(WMNs)為一項可提供寬頻存取網際網路的「最後一里(last mile) 」技術，能夠提供可靠且更加廣泛的服務給無線使用者。研究顯示，由於與出口閘道較遠的用戶能夠使用的頻寬較少，因此在建置無線網狀網路的同時如何兼顧網路效能與服務品質(QoS)是重要的議題。
本論文提出一個最大最小公平性(max-min fairness)的數學模型，在網路規劃階段考慮營運階段的端點對端點流量公平性問題(end-to-end throughput fairness)，並且聯合考慮網路節點佈署、出口閘道佈署、傳輸能量控制、信道佈署、路由規劃以及流量控制最佳化。本論文所提出的解決方案是基於拉格蘭日鬆弛法(Lagrangean Relaxation)為基礎所開發之啟發式演算法。 本論文提出前置處理方法(preprocessing)處理原先棘手的問題，並提出了適合多信道多網卡無線網狀網路(multi-channel multi-radio wireless mesh networks)的最大最小流量控制演算法(max-min flow control algorithm)。實驗結果顯示，以拉格蘭日對偶解(Lagrangean dual solution)為提示開發的啟發式演算法能夠有效地找到好的解。此外結果也顯示出，在本論文所設計的環境下，平均地將信道分配給使用者通訊(user communications)與骨幹通訊(backbone communications)能夠更有效地利用網路資源。 | zh_TW |
| dc.description.abstract | Wireless Mesh Networks (WMNs) are considered as a technology for last-mile broadband Internet access to provide reliable and more extensive connectivity to wireless users. Previous studies stated that users with longer paths must endure lower bandwidth allocation; as a result, performance and Quality of Service (QoS) are important factors in network planning stage.
In this paper, a max-min fairness mathematical model is proposed, which jointly consider end-to-end throughput fairness problem with network deployment, transmission power control, channel assignment, routing and flow control optimization. The solution approach introduced in this paper is a heuristic algorithm derived from Lagrangean Relaxation based problem formulation. This thesis proposes a preprocessing stage for handling the originally intractable problem. A max-min flow control algorithm is established for multi-channel multi-radio wireless mesh networks. The experiment results show the heuristic algorithm, which takes dual solutions of Lagrangean Relaxation method as hints, can efficiently get a good solution. And the results also show that network designers can better use the resource through evenly allocate available channels to user communications and backbone communications. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-15T05:44:43Z (GMT). No. of bitstreams: 1 ntu-99-R97725037-1.pdf: 1448439 bytes, checksum: 2b45c94a8ee091f81953959bfa951fa5 (MD5) Previous issue date: 2010 | en |
| dc.description.tableofcontents | 謝詞 V
論文摘要 IX THESIS ABSTRACT XI Chapter 1 Introduction 1 1.1 Background 1 1.2 Motivation 5 1.3 Literature Survey 6 1.3.1 Capacity of WMNs 7 1.3.2 End-to-End Throughput Fairness of WMNs 9 1.3.3 IEEE 802.11s 11 1.3.4 Multi-channel Multi-radio Wireless Mesh Networks 13 1.4 Proposed Approaches 15 1.5 Thesis Organization 15 Chapter 2 Problem Formulation 17 2.1 Problem Description 17 2.2 Problem Notations 25 2.3 Problem Formulation 28 Chapter 3 Solution Approach 35 3.1 Preprocessing 35 3.2 Lagrangean Relaxation Method 37 3.3 Lagrangean Relaxation 40 3.3.1 Subproblem 1 (related to decision variable h_v,b_v and η_v^k) 44 3.3.2 Subproblem 2 (related to decision variable r_v^k) 46 3.3.3 Subproblem 3 (related to decision variable y_l^k) 47 3.3.4 Subproblem 4 (related to decision variable f_(ll^')^k) 48 3.3.5 Subproblem 5 (related to decision variable a_q^k) 49 3.3.6 Subproblem 6 (related to decision variable c_l^k) 50 3.3.7 Subproblem 7 (related to decision variable g_l^k) 52 3.3.8 Subproblem 8 (related to decision variable x_p and γ_w) 53 3.3.9 Subproblem 9 (related to decision variable s) 55 3.4 The Dual Problem and the Subgradient Method 56 Chapter 4 Getting Primal Feasible Solution 57 4.1 Lagrangean Relaxation Results 57 4.2 Getting Primal Heuristics 57 4.2.1 Initialize WMN deployment 59 4.2.2 Routing heuristic 59 4.2.3 Adjust equipment heuristic 60 4.2.4 Max-min flow control algorithm 60 Chapter 5 Computational Experiments 63 5.1 Experiment Environment 63 5.2 Simple Algorithms and Performance Metrics 64 5.3 Experiment Scenarios 66 5.3.1 Different Number of Wireless Users 67 5.3.2 Different Number of Available Channels 70 5.3.3 Different Budget Constraints 72 5.3.4 Different Channel Allocation Schemes 74 Chapter 6 Conclusion 79 6.1 Summary 79 6.2 Future Work 81 References 83 | |
| dc.language.iso | en | |
| dc.subject | 拉格蘭日鬆弛法 | zh_TW |
| dc.subject | 無線網狀網路 | zh_TW |
| dc.subject | 網路規劃 | zh_TW |
| dc.subject | 服務品質 | zh_TW |
| dc.subject | 最大最小公平性 | zh_TW |
| dc.subject | 資料流競爭圖 | zh_TW |
| dc.subject | Lagrangean Relaxation | en |
| dc.subject | Wireless Mesh Networks | en |
| dc.subject | Network Planning | en |
| dc.subject | Quality of Service | en |
| dc.subject | Flow Contention Graph | en |
| dc.subject | Max-min Fairness | en |
| dc.title | 考慮端點對端點流量公平性之無線網狀網路最佳化建置 | zh_TW |
| dc.title | Deployment Optimization of Wireless Mesh Networks Considering End-to-End Throughput Fairness | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 98-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 鐘嘉德,莊東穎,趙啟超,呂俊賢 | |
| dc.subject.keyword | 無線網狀網路,網路規劃,服務品質,最大最小公平性,資料流競爭圖,拉格蘭日鬆弛法, | zh_TW |
| dc.subject.keyword | Wireless Mesh Networks,Network Planning,Quality of Service,Flow Contention Graph,Max-min Fairness,Lagrangean Relaxation, | en |
| dc.relation.page | 87 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2010-08-19 | |
| dc.contributor.author-college | 管理學院 | zh_TW |
| dc.contributor.author-dept | 資訊管理學研究所 | zh_TW |
| 顯示於系所單位： | 資訊管理學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-99-1.pdf 未授權公開取用 | 1.41 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。