請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/31508完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 謝宏昀(Hung-Yun Hsieh) | |
| dc.contributor.author | Tsai-Wei Wu | en |
| dc.contributor.author | 吳蔡偉 | zh_TW |
| dc.date.accessioned | 2021-06-13T03:13:59Z | - |
| dc.date.available | 2006-08-17 | |
| dc.date.copyright | 2006-08-17 | |
| dc.date.issued | 2006 | |
| dc.date.submitted | 2006-08-05 | |
| dc.identifier.citation | [1] Atheros Communication, Inc. Online Available at: http://www.atheros.com/
[2] Seattle Wireless. Online Available at: http://www.seattlewireless.net/ [3] Bay area wireless users group. Online Available at: http://www.bawug.org [4] MIT Roofnet. Online Available at: http://pdos.csail.mit.edu/roofnet/design/ [5] ECSL. Online Available at: http://www.ecsl.cs.sunysb.edu/multichannel/ [6] Microsoft Mesh Networking. Online Available at: http://research.microsoft.com/mesh/ [7] BWN. Online Available at: http://www.ece.gatech.edu/research/labs/bwn/mesh/ [8] Tropos Networks. Online Available at: http://www.tropos.com/ [9] MeshDynamics. Online Available at: http://www.meshdynamics.com/ [10] P. Gupta and P. Kumar, “The capacity of wireless networks,” IEEE Transactions on Information Theory, vol. 46, no. 2, pp. 388–404, March 2000. [11] P. Kyasanur and N. H. Vaidya, “Routing and interface assignment in multichannel multi-interface wireless networks,” in IEEE Wireless Communications and Networking Conference (WCNC), March 2005, pp. 2051–2056, new Orleans, LA, USA. [12] A. Raniwala, K. Gopalan, and T. cker Chiueh, “Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks,” SIGMOBILE Mob. Comput. Commun. Rev., vol. 8, no. 2, pp. 50–65, 2004. [13] Architecture and algorithms for an IEEE 802.1 1 -based multi-channel wireless mesh network, vol. 3, 2005. Online Available at: http://ieeexplore.ieee.org/xpls/abs all.jsp?arnumber=1498497 [14] 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. New York, NY, USA: ACM Press, 2004, pp. 114–128. [15] M. Kodialam and T. Nandagopal, “Characterizing the capacity region in multiradio multi-channel wireless mesh networks,” in MobiCom ’05: Proceedings of the 11th annual international conference on Mobile computing and networking. New York, NY, USA: ACM Press, 2005, pp. 73–87. [16] 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. New York, NY, USA: ACM Press, 2005, pp. 58–72. [17] B. P. Crow, I. Widjaja, L. G. Kim, and P. T. Sakai, “IEEE 802.11 wireless local area networks,” Communications Magazine, IEEE, vol. 35, no. 9, pp.116–126, 1997. Online Available at: http://ieeexplore.ieee.org/xpls/abs all.jsp?arnumber=620533 [18] I. F. Akyildiz, X. Wang, and W. Wang, “Wireless mesh networks: a survey.”Computer Networks, vol. 47, no. 4, pp. 445–487, 2005. [19] R. Bruno, M. Conti, and E. Gregori, “Mesh networks: commodity multihop ad hoc networks,” Communications Magazine, IEEE, vol. 43, no. 3, pp.123–131, 2005. Online Available at: http://ieeexplore.ieee.org/xpls/abs all.jsp? arnumber=1404606 [20] R. Karrer, A. Sabharwal, and E. Knightly, “Enabling large-scale wireless broadband:the case for TAPs,” SIGCOMM Comput. Commun. Rev., vol. 34, no. 1,pp. 27–32, 2004. [21] Nortel Networks. Online Available at: http://www.nortel.com/ [22] WiFly. Online Available at: http://www.wifly.com.tw/Wifly3/tw/ [23] B. Awerbuch, D. Holmer, and H. Rubens, “The medium time metric: High throughput route selection in multi-rate ad hoc wireless networks.” MONET, vol. 11, no. 2, pp. 253–266, 2006. [24] G. Holland, N. Vaidya, and P. Bahl, “A rate-adaptive MAC protocol for multihop wireless networks,” in MobiCom ’01: Proceedings of the 7th annual international conference on Mobile computing and networking. New York, NY, USA: ACM Press, 2001, pp. 236–251. [25] S.-T. Sheu, Y. Tsai, and J. Chen, “MR2RP: the multi-rate and multi-range routing protocol for IEEE 802.11 ad hoc wireless networks,” Wirel. Netw., vol. 9, no. 2, pp. 165–177, 2003. [26] J. Chen, C. Ting, and J. Guo, “M3RP: Multi-rate/multi-range multicast routing protocol for mobile ad hoc networks,” Mobile Computing, pp. 469–478, March 2005, taoyuan. Taiwan. [27] B. Awerbuch, D. Holmer, and H. Rubens, “Effects of multi-rate in ad hoc wireless networks,” Technical Report, July 2003. [28] H. Zhu and G. Cao, “rDCF: a relay-enabled medium access control protocol for wireless ad hoc networks,” IEEE Transactions on Mobile Computing, vol. 5,no. 9, pp. 1201–1214, 2006. [29] P. Bahl, A. Adya, J. Padhye, and A. Walman, “Reconsidering wireless systems with multiple radios,” SIGCOMM Comput. Commun. Rev., vol. 34, no. 5, pp.39–46, 2004. [30] R. Chandra, V. Bahl, and P. Bahl, “MultiNet: connecting to multiple IEEE 802.11 networks using a single wireless card.” in INFOCOM, 2004. [31] A. Adya, P. Bahl, J. Padhye, A.Wolman, and L. Zhou, “A multi-radio unification protocol for IEEE 802.11 wireless networks,” broadnets, vol. 00, pp. 344–354,2004. [32] 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. New York, NY, USA: ACM Press, 2004, pp. 222–233. [33] S.-L. Wu, C.-Y. Lin, Y.-C. Tseng, and J.-P. Sheu, “A new multi-channel MAC protocol with on-demand channel assignment for multi-hop mobile ad hoc networks,”in ISPAN ’00: Proceedings of the 2000 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN ’00). Washington, DC, USA: IEEE Computer Society, 2000, p. 232. [34] S. McCanne and S. Floyd. The Network Simulator – ns-2. Online Available at:http://www.isi.edu/nsnam/ns/ [35] 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. New York, NY, USA: ACM Press, 2004, pp. 216–230. [36] J. So and N. H. Vaidya, “Routing and Channel Assignment in Multi-Channel Multi-Hop Wireless Networks with Single Network Interface,” in The Second International Conference on Quality of Service in Heterogeneous Wired/Wireless Networks (QShine), Aug 2005. [37] K. Ramachandran, E. Belding, K. Almeroth, and M. Buddhikot, “Interferenceaware channel assignment in multi-radio wireless mesh networks,” IEEE INFOCOM, April 2006, barcelona, Spain. [38] J. Li, C. Blake, D. S. J. De Couto, H. I. Lee, and R. Morris, “Capacity of ad hoc wireless networks,” in Proceedings of the 7th ACM International Conference on Mobile Computing and Networking, Rome, Italy, July 2001, pp. 61–69. [39] P. Kyasanur and N. H. Vaidya, “Capacity of multi-channel wireless networks: impact of number of channels and interfaces,” in MobiCom ’05: Proceedings of the 11th annual international conference on Mobile computing and networking. New York, NY, USA: ACM Press, 2005, pp. 43–57. [40] K. Jain, J. Padhye, V. N. Padmanabhan, and L. Qiu, “Impact of interference on multi-hop wireless network performance,” in MobiCom ’03: Proceedings of the 9th annual international conference on Mobile computing and networking. New York, NY, USA: ACM Press, 2003, pp. 66–80. [41] H. A. Taha, Operations Research: An Introduction, 7th ed. Prentice Hall, July 2002. [42] ILOG CPLEX mathematical programming optimizers. Online Available at:http://www.ilog.com/products/cplex/ [43] lp solve: linear programming code. Online Available at: http://groups.yahoo.com/group/lp solve/ [44] LINGO. Online Available at: http://www.lindo.com/ [45] SoPlex. Online Available at: http://www.zib.de/Optimization/Software/Soplex/ [46] QSopt. Online Available at: http://www2.isye.gatech.edu/»wcook/qsopt/ [47] EMSOL. Online Available at: www.emsolgroup.com/ [48] D. B. West, Introduction to Graph Theory, 2nd ed. Prentice Hall, 2001. [49] IEEE standard for information technology- telecommunications and information exchange between systems- local and metropolitan area networks- specific requirements Part II: wireless LAN medium access control (MAC) and physical layer (PHY) specifications, IEEE Computer Society Std., 2003. [50] J. Robinson, K. Papagiannaki, C. Diot, X. Guo, and L. Krishnamurthy, “Experimenting with a multi-radio mesh networking testbed,” in Proceedings of the First Workshop on Wireless Network Measurements (WiNMee), April 2005, trentino,Italy. [51] J. W. Moon and L. Moser, “On cliques in graphs,” Israel Journal of Mathematics 3, pp. 23–28, 1965. [52] B. Aoun, R. Boutaba, Y. Iraqi, and G. Kenward, “Gateway placement optimization in WMN with QoS constraints,” IEEE Journal on Selected Areas in Communications (JSAC), Special Issue on Multi-hop Wireless Mesh Networks, 2006. [53] R. Chandra, L. Qiu, K. Jain, and M. Mahdian, “Optimizing the placement of internet TAPs in wireless neighborhood networks,” ICNP, vol. 00, pp. 271–282, 2004. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/31508 | - |
| dc.description.abstract | The wireless mesh network (WMN) is designed as an economical solution for last-mile broadband Internet access. Some commercial applications have emerged, such as “community wireless networks”. These WMNs offer increased reliability, coverage and reduced infrastructure costs over their single-hop counterpart, namely wireless LANs. Providing broadband access to Internet is their major objective. Equipping mesh nodes with multiple radios can further improves the network capacity by transmitting over multiple radios simultaneously using orthogonal channels. Efficient channel assignment and routing are essential to capture the benefits of them.
However, most previous studies only focus on heuristic approaches. In this thesis, our objective is to investigate the capacity region of 802.11 based multi-radio multi-channel wireless mesh networks for network designers to plan network deployment. First, we present a network model which captures the characteristics of 802.11 MAC mechanism and 802.11 a/b/g multi-mode radio, including RTS/CTS/DATA/ACK handshake, wireless interference, adaptive data rates, orthogonal channels, multi-mode radios, and evaluate the performance. Then, we formulate the problem as a linear programing (LP) in wireless mesh networks with 802.11 a/b/g multi-mode radios. And we evaluate the performance in the three different topologies to analyze the affects of each parameter. Finally, we extend our formulation and discuss the impact of gateway placement, wired bandwidth limitation and fairness schemes on the performance of wireless mesh networks. Our work can be used for planning of wireless mesh networks with respect to the performance trade-offs of different important deployment parameters. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-13T03:13:59Z (GMT). No. of bitstreams: 1 ntu-95-R93942098-1.pdf: 3545349 bytes, checksum: f2bf8addad4290e8c4a26ea71eeede43 (MD5) Previous issue date: 2006 | en |
| dc.description.tableofcontents | ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
LIST OF TABLES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi LIST OF FIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii CHAPTER 1 INTRODUCTION . . . . . . . . . . . . . . . . . . . . . 1 CHAPTER 2 BACKGROUND . . . . . . . . . . . . . . . . . . . . . . 4 2.1 IEEE 802.11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.1.1 IEEE 802.11 Architecture . . . . . . . . . . . . . . . . . . . . 4 2.1.2 Physical Layer . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1.3 Medium-Access Control (MAC) Layer . . . . . . . . . . . . . 6 2.2 Wireless Mesh Networks . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2.1 A Case Study of MIT Roofnet . . . . . . . . . . . . . . . . . 11 2.2.2 WMNs in Taiwan . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3 Exploiting Multiplicity in Wireless Mesh Networks . . . . . . . . . . 12 2.3.1 Using Multi-Radio and Multi-Channel . . . . . . . . . . . . . 13 2.3.2 Multi-Radio Multi-Channel Protocols . . . . . . . . . . . . . 16 2.4 Capacity Characterization in Wireless Mesh Networks . . . . . . . . 20 2.4.1 Asymptotic Approaches . . . . . . . . . . . . . . . . . . . . . 20 2.4.2 Optimization Approaches . . . . . . . . . . . . . . . . . . . . 21 CHAPTER 3 OPTIMIZATION FRAMEWORK . . . . . . . . . . . 26 3.1 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.1.1 Node Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.1.2 Network Model . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.1.3 Interference Model . . . . . . . . . . . . . . . . . . . . . . . . 29 3.2 LP Formulation (I) . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.2.1 Upper Bound Using Maximal Cliques . . . . . . . . . . . . . 33 3.2.2 Lower Bound Using Maximal Independent Sets . . . . . . . . 36 3.2.3 Issues with Maximal Independent Sets and Maximal Cliques 37 3.3 LP Formulation (II) . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.3.1 Upper Bound Using Node Interference Pairs . . . . . . . . . 40 3.3.2 Lower Bound Using Link Interference Sets . . . . . . . . . . 40 CHAPTER 4 SIMULATION RESULTS AND ANALYSIS . . . . . 43 4.1 Chain Topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.1.1 Impact of Number of Channels . . . . . . . . . . . . . . . . . 43 4.1.2 Impact of Interference Range . . . . . . . . . . . . . . . . . . 44 4.1.3 Impact of Number of Radios . . . . . . . . . . . . . . . . . . 45 4.2 Grid Topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 4.2.1 Starvation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 4.2.2 Effect of number of MISs and cliques . . . . . . . . . . . . . 47 4.2.3 Impact of Number of Flows . . . . . . . . . . . . . . . . . . . 49 4.2.4 Impact of Number of Radios . . . . . . . . . . . . . . . . . . 50 4.2.5 Heterogeneous Radio Systems . . . . . . . . . . . . . . . . . 51 4.2.6 Impact of Gateway Placement . . . . . . . . . . . . . . . . . 51 4.3 Roofnet Topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.3.1 Impact of Number of Radios . . . . . . . . . . . . . . . . . . 53 4.3.2 Interference between 802.11b and 802.11g . . . . . . . . . . . 56 4.3.3 Impact of Number of Gateways . . . . . . . . . . . . . . . . . 56 CHAPTER 5 EXTENSION OF THE OPTIMIZATION FRAMEWORK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 5.1 Gateway Placement . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 5.1.1 Simulation Setup and Results . . . . . . . . . . . . . . . . . . 60 5.2 Wired Bandwidth Limitation . . . . . . . . . . . . . . . . . . . . . . 62 5.2.1 Simulation Setup and Results . . . . . . . . . . . . . . . . . . 64 5.3 Fairness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 5.3.1 Simulation Setup and Results . . . . . . . . . . . . . . . . . . 66 5.4 Other Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 CHAPTER 6 CONCLUSIONS AND FUTURE WORK . . . . . . . 69 REFERENCES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 | |
| dc.language.iso | en | |
| dc.subject | 最佳化 | zh_TW |
| dc.subject | 無線網狀網路 | zh_TW |
| dc.subject | Capacity | en |
| dc.subject | 802.11a/b/g | en |
| dc.subject | Wireless Mesh Networks | en |
| dc.title | 802.11a/b/g多模無線網狀網路之系統最佳化分析 | zh_TW |
| dc.title | Capacity Characterization in Wireless Mesh Networks with 802.11a/b/g Multi-Mode Radios | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 94-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 林永松(Yeong-Sung Lin),廖婉君(Wanjiun Liao),逄愛君(Ai-Chun Pang) | |
| dc.subject.keyword | 無線網狀網路,最佳化, | zh_TW |
| dc.subject.keyword | Wireless Mesh Networks,Capacity,802.11a/b/g, | en |
| dc.relation.page | 73 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2006-08-07 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 電信工程學研究所 | zh_TW |
| 顯示於系所單位： | 電信工程學研究所 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-95-1.pdf 未授權公開取用 | 3.46 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。