請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/47029完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 林永松 | |
| dc.contributor.author | Yi-Wei Li | en |
| dc.contributor.author | 李怡緯 | zh_TW |
| dc.date.accessioned | 2021-06-15T05:45:38Z | - |
| dc.date.available | 2012-08-20 | |
| dc.date.copyright | 2010-08-20 | |
| dc.date.issued | 2010 | |
| dc.date.submitted | 2010-08-18 | |
| dc.identifier.citation | [1]. F. Akyildiz, X. Wang, and W. Wang, “Wireless Mesh Networks: A Survey,” Computer Networks, Vol. 47, No.4, pp. 445-487, March 2005.
[2]. V. Gambiroza, B. Sadeghi, and E. Knightly, “End-to-End Performance and Fairness in Multihop Wireless Backhaul Networks,” Proc. MobiCom ’04, pp. 287–301, October, 2004. [3]. N. Ben Salem and J.P. Hubaux, “A Fair Scheduling for Wireless Mesh Networks,” Proc. IEEE Workshop on Wireless Mesh Networks (WiMesh), 2005. [4]. D. Bertsekas and R.G. Gallager, “Data Networks,” 2nd ed., Upper Saddle River, NJ: Prentice Hall, 1992. [5]. T. Bonald, L. Massoulie, A. Proutiere and J. Virtamo, “A Queueing Analysis of Max-Min Fairness, Proportional Fairness and Balanced Fairness,” Queueing Systems: Theory and Applications, pp. 65–84, 2006. [6]. T. Bonald and A. Prouti`ere, “On performance bounds for balanced fairness,” Performance Evaluation 55, pp. 25–50, 2004. [7]. Liu and W. Liao, “Location-Dependent Throughput and Delay in Wireless Mesh Networks,” IEEE Trans. Vehicular Technology, Vol. 57, No. 2, pp. 1188-1198, 2008. [8]. 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, February 2009. [9]. H.H. Yen and F.Y.S. Lin, “Delay constrained routing and link capacity assignment in virtual circuit networks,” IEICE Trans. Commun., Vol.E88–B, No.5, pp. 2004-2014, May 2005. [10]. Y.F. Wen and F.Y.S. Lin, “Fair Bandwidth Allocation and End-to-end Delay Routing Algorithms for Wireless Mesh Networks,” IEICE Transactions on Communications, Vol. E90-B, No. 5, 2007. [11]. K.T. Cheng and F.Y.S. Lin, “Minimax End-to-end Delay Routing and Capacity Assignment for Virtual Circuit Networks,” Proc. IEEE GLOBECOM’95, 1995. [12]. M. L. Fisher, “The Lagrangean Relaxation Method for Solving Integer Programming Problems,” Management Science, Vol. 27, No. 1, pp. 10-21, January 1981. [13]. M.L. Fisher, “An Application Oriented Guide to Lagrangean Relaxation,” Interfaces, Vol. 15, NO. 2, pp. 10-21, April 1985. [14]. S. Chen and K. Nahrstedt, “An Overview of Quality of Service Routing for Next-Generation High-Speed Networks: Problems and Solutions,” IEEE Network, Vol. 12, No. 6, pp. 64-79, November 1998. [15]. Z. Wang and J. Crowcroft, “QoS Routing for Supporting Resource Reservation,” IEEE JSAC, September 1996. [16]. E. Dijkstra, “A Note on Two Problems in Connexion with Graphs,” Numerische Mathemotik, Vol. 1, pp. 269-71, 1959. [17]. R. E. Bellman, “Dynamic Programming,” Princeton University Press, NJ: Princeton, 1957. [18]. Y. F. Wen and Frank Y.S. Lin, “The Top Load Balancing Forest Routing in Mesh Networks,” Proc. IEEE CCNC, January 2006. [19]. Frank Y.S. Lin and J.R. Yee, “Three Algorithms for Routing and Flow Control in Virtual Circuit Networks,” Proc. IEEE GLOBECOM’90, 1990. [20]. Atilla Eryilmaz and R. Srikant, “Joint Congestion Control, Routing and MAC for Stability and Fairness in Wireless Networks”, IEEE J. Sel. Areas Commun., Vol. 24, No. 8, pp. 1514–1524, August. 2006. [21]. R. Jain, D. Chiu, and W. Hawe, “A quantitative measure of fairness and discrimination for resource allocation in shared computer systems,” Technical Report TR-301, DEC Research, September 1984. [22]. Y.F. Wen, “Performance Optimization Algorithm for Wireless Networks,” Department of Information Management, National Taiwan University, July 2007. [23]. S. Haber and W. Stornetta, “How to Time-Stamp a Digital Document,” Advances in Cryptology, Vol. 537, 1990. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/47029 | - |
| dc.description.abstract | 無線網狀網路被視為提供客戶寬頻接入至網際網路之“最後一哩”的方式之一。隨著閘道器與無線路由器的功能日漸增強，所服務的區域也隨之擴增。公平性一直是網路研究者所重視的研究議題之一。然而，以現有的頻寬分配法則及流量控管機制，並無法達成公平性目標。因此，本研究之目標為藉由流量控制機制及頻寬分配來達成兼顧各用戶延遲及吞吐量之公平性，更進一步結合路由決策使系統吞吐量最大化。
本論文採用數學模型來完整描述問題，再試圖以最佳化為基礎的演算法解決該混合整數非線性數學規劃問題。由於必須同時處理若干決策變數，同時效能均符合一定服務品質，在解題過程中，首先採用兩階段經驗法則，計算出具有公平性之頻寬分配基準，其目的為保證端點至端點吞吐量及端點至端點延遲公平性。再引用拉格蘭日鬆弛法及次梯度法為基礎逐步調整決策變數以逼近最佳值。最後藉由電腦實驗結果證明所提出的解決方案之優異性。 | zh_TW |
| dc.description.abstract | Wireless mesh networks provide connectivity to communities and act as a solution for last-mile broadband Internet access. By improvements of routers and gateways, service region expands much broader than before. Fairness, which is an important issue since Internet has been researched, is our objective subject to the capacity of equipments. The hop count from client to gateway influences the performance. A more hop count may experience lower quality of service (QoS) and even starvation. In this thesis, we focus on capacity allocation, flow control and routing to achieve end-to-end fairness.
This end-to-end fairness problem is formulated as a mathematical programming model and then deal with by an optimization-based algorithm. In this thesis, two important performance metrics, end-to-end delay and throughput are discussed. Several decision variables need to be determined where a certain level of QoS requirements is satisfied. We purpose a two-phased heuristic to ensure end-to-end delay and throughput fairness. To solve this problem, the Lagrangean Relaxation method is introduced to decompose the primal problem into several subproblems and we also adopt the subgradient method to obtain a reasonable lower bound. Further, we show the efficiency and effectiveness of the purposed algorithm by computational experiments. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-15T05:45:38Z (GMT). No. of bitstreams: 1 ntu-99-R97725036-1.pdf: 3881537 bytes, checksum: ecbe2ca30a42f1c35185b248bc2be3bf (MD5) Previous issue date: 2010 | en |
| dc.description.tableofcontents | 論文摘要 VI
THESIS ABSTRACT VIII Table of Contents X List of Figures XIII List of tables XV Chapter 1 Introduction 1 1.1 Background 1 1.2 Motivation 4 1.3 Literature Survey 6 1.4 Thesis Organization 11 Chapter 2 Problem Formulation 12 2.1 Problem Description 12 2.1.1 Problem introduction 12 2.1.2 Problem Description 15 2.1.3 Problem Scenarios and algorithms 16 2.1.4 Problem Assumptions 25 2.1.5 Problem Description Table 27 2.2 Problem Formulation 30 2.2.1 Notation 30 2.2.2 Problem Formulation 33 Chapter 3 Solution Approach 36 3.1 Lagrangean Relaxation Method 36 3.2 Lagrangean Relaxation 40 3.3 The Dual Problem and the Subgradient Method 49 Chapter 4 Computational Experiments 51 4.1 Simple algorithm and Lagrangean algorithm 51 4.2 Getting primal feasible solution 53 4.3 Experiment Environment 57 4.4 Experiment result 58 4.4.1 Link utilization and traffic requirement 58 4.4.2 Capacity allocation 60 4.4.3 Number of clients 61 4.4.4 Link utilization vector 62 Chapter 5 Conclusion and Future Works 64 5.1 Conclusion 64 5.2 Future work 68 References: 69 | |
| dc.language.iso | en | |
| dc.title | 基於配置頻寬、流量控制與路由決策達成無線網狀網路端點至端點延遲及吞吐量之公平性 | zh_TW |
| dc.title | Joint Flow Control, Capacity Allocation and Routing Strategy to Achieve End-to-end Delay and Throughput Fairness in Wireless Mesh Networks | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 98-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 呂俊賢,鐘嘉德,趙啟超,莊東穎 | |
| dc.subject.keyword | 無線網狀網路,流量控制,頻寬分配,路由決策,服務品質,端點至端點公平性,最佳化,拉格蘭日鬆弛法, | zh_TW |
| dc.subject.keyword | Flow control,Capacity Allocation,Routing,End-to-end Fairness,Mathematical Programming,Optimization,Lagrangean Relaxation, | en |
| dc.relation.page | 74 | |
| 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 目前未授權公開取用 | 3.79 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。