請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/41374
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 周承復 | |
dc.contributor.author | Ching-Ju Lin | en |
dc.contributor.author | 林靖茹 | zh_TW |
dc.date.accessioned | 2021-06-15T00:17:28Z | - |
dc.date.available | 2010-06-02 | |
dc.date.copyright | 2009-06-02 | |
dc.date.issued | 2009 | |
dc.date.submitted | 2009-05-14 | |
dc.identifier.citation | [1] MadWifi. http://madwifi.org.
[2] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, February 1993. [3] I. Akyildiz and X. Wang. A Survey on Wireless Mesh Networks. Communications Magazine, IEEE, 43(9):S23–S30, Sept. 2005. [4] I. F. Akyildiz, X.Wang, andW.Wang. Wireless Mesh Networks: A Survey. Computer Networks, 47(4):445–487, 2005. [5] M. Alicherry, R. Bhatia, and L. E. Li. Joint Channel Assignment and Routing for Throughput Optimization in Multi-Radio Wireless Mesh Networks. In MobiCom’05: Proceedings of the 11th annual international conference on Mobile computing and networking, 2005. [6] P. Bahl, R. Chandra, and J. Dunagan. SSCH: Slotted Seeded Channel Hopping for Capacity Improvement in IEEE 802.11 Ad-Hoc Wireless Networks. In MobiCom ’04: Proceedings of the 10th annual international conference on Mobile computing and networking. ACM, 2004. [7] J. Bicket. Bit-Rate Selection in Wireless Networks. PhD thesis, Massachusetts Institute of Technology, 2005. [8] S. Biswas and R. Morris. ExOR: Opportunistic Multi-Hop Routing for Wireless Networks. In SIGCOMM ’05: Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications. ACM, 2005. [9] R. Bruno, M. Conti, and E. Gregori. Mesh Networks: Commodity Multihop Ad Hoc Networks. Communications Magazine, IEEE, 43(3):123–131, March 2005. [10] J. Camp and E. Knightly. Modulation Rate Adaptation in Urban and Vehicular Environments: Cross-Layer Implementation and Experimental Evaluation. In MobiCom’08: Proceedings of the 14th ACM international conference on Mobile computing and networking, 2008. [11] G. Cantieni, Q. Ni, C. Barakat, and T. Turletti. Performance Analysis under Finite Load and Improvements for Multirate 802.11. Computer Communications, 28(10):1095–1109, 2005. [12] Y.-Y. Chen, S.-C. Liu, and C. Chen. Channel Assignment and Routing for Multi-Channel Wireless Mesh Networks Using Simulated Annealing. In Global Telecommunications Conference, 2006. GLOBECOM ’06. IEEE, 2006. [13] C. Chou, A.Misra, and J. Qadir. Low-Latency Broadcast in Multirate Wireless Mesh Networks. Selected Areas in Communications, IEEE Journal on, 24(11):2081–2091, Nov. 2006. [14] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, Second Edition. The MIT Press, September 2001. [15] A. K. Das, H. M. K. Alazemi, R. Vijayakumar, and S. Roy. Optimization Models for Fixed Channel Assignment in Wireless Mesh Networks with Multiple Radios. In Sensor and Ad Hoc Communications and Networks, 2005. IEEE SECON 2005. 2005 Second Annual IEEE Communications Society Conference on, 2005. [16] R. Draves, J. Padhye, and B. Zill. Comparison of Routing Metrics for Static Multi-Hop Wireless Networks. In SIGCOMM ’04: Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, 2004. [17] R. Draves, J. Padhye, and B. Zill. Routing in Multi-Radio, Multi-Hop Wireless Mesh Networks. In MobiCom ’04: Proceedings of the 10th annual international conference on Mobile computing and networking, 2004. [18] P.Dutta, S. Jaiswal, D. Panigrahi, and R. Rastogi. A New Channel Assignment Mechanism for Rural Wireless Mesh Networks. In INFOCOM 2008. The 27th Conference on Computer Communications. IEEE, pages 2261–2269, April 2008. [19] M. Felegyhazi, M. Cagalj, S. Bidokhti, and J. Hubaux. Non-Cooperative Multi-Radio Channel Allocation in Wireless Networks. In INFOCOM 2007. 26th IEEE International Conference on Computer Communications. Proceedings, pages 1442–1450, 2007. [20] H. Fussler, J. Widmer, M. Kasemann, M. Mauve, and H. Hartenstein. Contention based Forwarding for Mobile Ad Hoc Networks. Ad Hoc Networks, 1(4):351 – 369, 2003. [21] M. Heusse, F. Rousseau, G. Berger-Sabbatel, and A. Duda. Performance Anomaly of 802.11b. In INFOCOM 2003. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE, 2003. [22] G. Holland, N. Vaidya, and P. Bahl. A Rate-Adaptive MAC Protocol for Multi-Hop Wireless Networks. In MobiCom ’01: Proceedings of the 7th annual international conference on Mobile computing and networking, 2001. [23] Y. Jian and S. Chen. Can CSMA/CA networks be made fair? In MobiCom ’08: Proceedings of the 14th ACM international conference on Mobile computing and networking, 2008. [24] A. Kamerman and L. Monteban. WaveLAN-II: A High-Performance Wireless LAN for the Unlicensed Band. Bell Labs Technical Journal, 2(3):118–133, 1997. [25] C.-J. Lin and C.-F. Chou. Route-Aware Load-Balanced Resource Allocation for Wireless Mesh Networks. In Wireless Communications and Networking Conference, 2007.WCNC 2007. IEEE, March 2007. [26] C.-J. Lin, S.-H. Lin, and C.-F. Chou. Performance Study of Optimal Routing and Channel Assignment in Wireless Mesh Networks. In Global Telecommunications Conference, 2007. GLOBECOM ’07. IEEE, Nov. 2007. [27] T. Liu and W. Liao. Capacity-Aware Routing in Multi-Channel Multi-Rate Wireless Mesh Networks. In IEEE International Conference on Communications (ICC ’06), 2006. [28] L. Loyola, T. Kumagai, K. Nagata, S. Otsuki, and S. Aikawa. Multi-Channel Wireless LAN Mesh Architecture with DCF-based Inter-AP Communication and Idle Channel Search Packet Forwarding. In Global Telecommunications Conference, GLOBECOM ’05. IEEE, Dec. 2005. [29] A. Naveed, S. Kanhere, and S. Jha. Topology Control and Channel Assignment in Multi-Radio Multi-Channel Wireless Mesh Networks. In Mobile Adhoc and Sensor Systems, 2007. MASS 2007. IEEE International Conference on, 2007. [30] The Network Simulator NS-2. http://www.isi.edu/nsnam/ns/. [31] J. Qadir, A. Misra, and C. T. Chou. Minimum Latency Broadcasting in Multi-Radio Multi-Channel Multi-Rate Wireless Meshes. In Sensor and Ad Hoc Communications and Networks, 2006. SECON ’06. 2006 3rd Annual IEEE Communications Society on, 2006. [32] K. N. Ramachandran, E. M. Belding, K. C. Almeroth, and M. M. Buddhikot. Interference-Aware Channel Assignment in Multi-Radio Wireless Mesh Networks. In INFOCOM 2006. 25th IEEE International Conference on Computer Communications. Proceedings, 2006. [33] B. Raman. Channel Allocation in 802.11-Based Mesh Networks. In INFOCOM 2006. 25th IEEE International Conference on Computer Communications. Proceedings, pages 1–10, April 2006. [34] B. Raman and K. Chebrolu. Design and Evaluation of a New MAC Protocol for Long-Distance 802.11 Mesh Networks. In MobiCom ’05: Proceedings of the 11th annual international conference on Mobile computing and networking, pages 156–169. ACM, 2005. [35] A. Raniwala and T. cker Chiueh. Architecture and Algorithms for an IEEE 802.11-based Multi-ChannelWireless Mesh Network. In INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE, 2005. [36] A. Raniwala, K. Gopalan, and T. cker Chiueh. Centralized Channel Assignment and Routing Algorithms for Multi-Channel Wireless Mesh Networks. ACM Mobile Computing and Communications Review (MC2R), 8(2):50–65, 2004. [37] B. Sadeghi, V. Kanodia, A. Sabharwal, and E. Knightly. Opportunistic Media Access for Multirate Ad Hoc Networks. In MobiCom ’02: Proceedings of the 8th annual international conference on Mobile computing and networking, 2002. [38] R. Shah, A. Bonivento, D. Petrovic, E. Lin, J. van Greunen, and J. Rabaey. Joint Optimization of a Protocol Stack for Sensor Networks. In Military Communications Conference, 2004. MILCOM 2004. IEEE, Oct.-3 Nov. 2004. [39] J. So and N. H. Vaidya. Multi-Channel MAC for Ad Hoc Networks: Handling Multi-Channel Hidden Terminals Using a Single Transceiver. In MobiHoc ’04: Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, 2004. [40] J. Tang, G. Xue, and W. Zhang. Interference-Aware Topology Control and QoS Routing in Multi-Channel Wireless Mesh Networks. In MobiHoc ’05: Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, 2005. [41] J. Tang, G. Xue, and W. Zhang. Maximum Throughput and Fair Bandwidth Allocation in Multi-Channel Wireless Mesh Networks. In INFOCOM 2006. 25th IEEE International Conference on Computer Communications. Proceedings, April 2006. [42] Q.W. TianboKuang and C.Williamson. MRMC: A Multi-Rate Multi-Channel MAC Protocol for Multi-Radio Wireless LANs. In Workshop on Performance of Wireless Networks and Communication Systems (WiNCS), 2005. [43] K. Zeng, W. Lou, and H. Zhai. Capacity of Opportunistic Routing in Multi-Rate and Multi-Hop Wireless Networks. Wireless Communications, IEEE Transactions on, 7(12):5118–5128, December 2008. [44] K. Zeng, W. Lou, and H. Zhai. On End-to-End Throughput of Opportunistic Routing in Multirate and Multihop Wireless Networks. In INFOCOM 2008. 27th IEEE International Conference on Computer Communications. Proceedings, April 2008. [45] M. Zorzi and R. Rao. Geographic Random Forwarding (GeRaF) for Ad Hoc and Sensor Networks: Energy and Latency Performance. Mobile Computing, IEEE Transactions on, 2(4):349–365, Oct.-Dec. 2003. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/41374 | - |
dc.description.abstract | 多重網卡多重頻帶無線網狀網路(Multi-Radio Multi-Channel Wireless Mesh Networks)的架構設計提供普及的寬頻無線存取務。近年來,如何有效的分配網狀網路之頻寬資源,利用多重網卡及多重頻帶來增進網路效能,已受到諸多的關注。在多重頻帶網狀網路中,路由和頻帶分配交互影響並決定網狀網路之頻寬容量(network capacity)。目前已有文獻指出同時解決路由和頻帶分配問題(joint routing and channel assignment, i.e., JRC),可以使網狀網路達到較高的頻寬效能。雖然已經有非常多學術論文致力於解決網狀網路中之路由與頻帶分配問題(JRC problem),但其中大多數都忽略了網路中多重傳輸速率之特性,亦或假設無線鏈結僅使用基礎速(basic rate)傳送資料。然而,在多重傳輸速率網路中,當使用高傳輸速率之鏈結與使用低傳輸速率之鏈結共享相同頻帶時,由於多重速率分享問題(multi-rate sharing problem),使用高傳輸速率之鏈結可能無法獲得相當的平均吞吐量。
為了解決多重速率分享問題,我們首先提出一套量化的公式以估計無線鏈結之動態頻寬容量(dynamic link capacity)。此外,此估計公式可以有效的指出多重速率分享問題的嚴重性,幫助網狀網路配置適當的頻帶分配方式,以減輕多重速率網路中之多重速率分享問題。 本論文的第二部分旨在提出一套最佳化資源分配模型(multi-rate JRC model),藉由估計每個無線鏈結之動態頻寬容量,網狀網路能夠找到最佳的路由及頻帶配置以最大化總體網路吞吐量。我們更將此最佳化問題轉換成Lagrangian對偶問題(Lagrangian dual problem),並基於梯度演算法(subgradient-based algorithm)來解決此對偶問題。由於每個對偶問題中的子問題(Lagrangian sub-problem)仍是非線性之問題(non-linear problem),我們更推導出一套演算法使其能在有效時間內(polynomial-time)解決對偶子問題,以逼近資源分配之最佳解。我們藉由實驗來驗證所提估計公式之準確性,並使用電腦模擬來驗證最佳化資源分配模型之效能。結果顯示估計出的動態頻寬容量能真實的反應出網路中的多重速率共享問題。此外,模擬結果也顯示多重速率資源分配模型(multi-rate JRC model)能有效解決單一速率分配模型(base-rate JRC model)所產生的缺點,並提升整體網路之效能。 | zh_TW |
dc.description.abstract | Multi-radio Multi-channel wireless mesh networks (WMNs) aim to perform ubiquitous wireless broadband network access. In WMNs, much attention has been paid to the problem of resource allocation, i.e. how to efficiently utilize
multiple orthogonal channels and multiple communication radios to enhance the aggregate throughput. In multi-channel wireless mesh networks (WMNs), the routing and channel assignment can interdependently determine network capacity. Some literatures show that a multi-channel, multi-radio WMN can achieve higher aggregate throughput if it can solve the routing and channel assignment problems jointly. However, current works on the joint routing and channel assignment (JRC) problem in wireless mesh networks (WMNs) assume that all links operate at the base rate. In other words, they do not consider the presence of multiple bit-rates. However, in multi-rate WMNs, the achievable throughput of a link operating at higher rates could be much less than its bit-rate when it has to contend with low-rate links. This is also known as the multi-rate sharing problem. To address the problem, we first present a numerical formulation for estimating the dynamic link capacity, which can indicate the degree of the multi-rate sharing problem. Next, we propose an optimization model called Multi-Rate JRC, which solves the JRC problem by considering the dynamic link capacity in order to maximize the throughput in multi-rate, multi-radio, multi-channel WMNs. We then reformulate the primal problem as a Lagrangian dual problem, and apply the subgradient method to approach the dual. Finally, since each subproblem in the dual problem is also a non-linear problem, we design a polynomial-time algorithm to solve it. Our experiment results demonstrate that the proposed capacity formulation can approximate the actual link throughput. We compare the multi-rate JRC model with the base-rate JRC model via simulations. The results show that the multi-rate JRC model achieves throughput gains of 3-4 times and recover from network failure efficiently. | en |
dc.description.provenance | Made available in DSpace on 2021-06-15T00:17:28Z (GMT). No. of bitstreams: 1 ntu-98-F92922038-1.pdf: 1072531 bytes, checksum: 5832d3dfa4609807346d975655fe5489 (MD5) Previous issue date: 2009 | en |
dc.description.tableofcontents | Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
Abstract (in Chinese) . . . . . . . . . . . . . . . . . . . . . . . . . . . v Abstract (in English) . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii Chapter 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Problem Definition and Contributions . . . . . . . . . . . . . . . . . . 5 Chapter 2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.1 Multi-Channel Multi-Radio WMNs . . . . . . . . . . . . . . . . . . . 8 2.1.1 Routing in WMNs . . . . . . . . . . . . . . . . . . . . . . . . 9 2.1.2 Channel Assignment in WMNs . . . . . . . . . . . . . . . . . 10 2.1.3 Joint Routing and Channel Assignment in WMNs . . . . . . . 12 2.2 Multi-rate Wireless Networks . . . . . . . . . . . . . . . . . . . . . . 13 2.2.1 Multi-rate Sharing Problem . . . . . . . . . . . . . . . . . . . 13 2.2.2 Multi-rate Broadcasting . . . . . . . . . . . . . . . . . . . . . 13 2.2.3 Multi-rate Opportunistic Routing . . . . . . . . . . . . . . . . 14 Chapter 3 Motivating Examples . . . . . . . . . . . . . . . . . . . . 15 Chapter 4 Dynamic Link Capacity in Multi-rate WMNs . . . . . 19 Chapter 5 Multi-Rate JRC Model . . . . . . . . . . . . . . . . . . . 23 5.1 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 5.2 Primal Optimization Model . . . . . . . . . . . . . . . . . . . . . . . 29 5.3 Lagrangian Dual Problem . . . . . . . . . . . . . . . . . . . . . . . . 33 5.4 Subgradient-based Algorithm for the Lagrangian Dual Problem . . . 37 5.5 Polynomial Time Solution to the Lagrangian Subproblem . . . . . . . 41 Chapter 6 Performance Evaluation and Discussion . . . . . . . . . 51 6.1 Accuracy of Dynamic Link Capacity Estimation . . . . . . . . . . . . 53 6.2 Aggregate Throughput Comparison . . . . . . . . . . . . . . . . . . . 57 6.3 Convergence and Dynamic Adaptation . . . . . . . . . . . . . . . . . 62 Chapter 7 Conclusion and Future Work . . . . . . . . . . . . . . . 66 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 Appendix A. Proof for the Shortest Bottleneck Path . . . . . . . . . 76 Appendix B. Proof for the Best Commodity Path . . . . . . . . . . 77 | |
dc.language.iso | en | |
dc.title | 利用多重傳輸速率增進無線網狀網路之效能 | zh_TW |
dc.title | Exploiting Multiple Rates to Maximize the Throughput of Wireless Mesh Networks | en |
dc.type | Thesis | |
dc.date.schoolyear | 97-2 | |
dc.description.degree | 博士 | |
dc.contributor.oralexamcommittee | 廖婉君,張仲儒,曾煜棋,蔡子傑,陳裕賢,黃文吉,陳伶志 | |
dc.subject.keyword | 無線網狀網路,路由與頻帶分配,多重傳輸速率,多重網卡多重頻帶網路, | zh_TW |
dc.subject.keyword | Wireless Mesh Networks,Routing and Channel Assignment,Multiple Bit-Rates,Multi-Radio Multi-Channel, | en |
dc.relation.page | 79 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2009-05-15 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 資訊網路與多媒體研究所 | zh_TW |
顯示於系所單位: | 資訊網路與多媒體研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-98-1.pdf 目前未授權公開取用 | 1.05 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。