請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/38264完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 陳健輝 | |
| dc.contributor.author | Chia-Cheng Hu | en |
| dc.contributor.author | 胡家正 | zh_TW |
| dc.date.accessioned | 2021-06-13T16:29:04Z | - |
| dc.date.available | 2005-07-20 | |
| dc.date.copyright | 2005-07-20 | |
| dc.date.issued | 2005 | |
| dc.date.submitted | 2005-07-13 | |
| dc.identifier.citation | [1] C. M. Cordeiro, H. Gossain, and D. P. Agrawal, “Multicast over wireless mobile ad-hoc networks: present and future directions,” IEEE Network, Special Issue on Multicasting: An Enabling Technology, January/February, pp. 52-59, 2003.
[2] W. L. Winston, Introduction to Mathematical Programming: Applications and Algorithms, PWS-Kent: Boston, 1991. [3] H. Karloff, Linear Programming, Birkhauser: Boston, 1991. [4] L. A. Wolsey, Integer Programming, J. Wiley: New York, 1998. [5] G. B. Dantzig, “Programming of interdependent activities: II. mathematical model,” Econometrica, vol. 17, pp. 200-211, 1949. [6] N. Karmarkar, “A new polynomial-time algorithm for linear programming,” Combinatorica, vo. 4, pp. 373-395, 1984. [7] A. B. Kurzhanskiand and I. Vályi, Ellipsoidal Calculus for Estimation and Control, MA: Birkhäuser: Boston, 1996. [8] G. Arfken, “Lagrange multipliers,” Mathematical Methods for Physicists, Academic Press: Orlando, 1985. [9] R. E. Gomory, “Outline of an algorithm for integer solutions to linear programs,” Bulletin of the American Mathematical Society, pp. 275-278, 1958. [10] R. S. Garfinkel and G. L. Nemhauser, Integer Programming, Wiley: New York, 1972. [11] P. C. Gilmore and R. E. Gomory, “Multistage cutting stock problems of two and more dimensions,” Operations Research, vol. 13, pp. 94-120, 1965. [12] P. L. Hammer and S. Rudeanu, Boolean methods in operations research and related areas, Springer-Verlag: Berlin, 1968. [13] F. Granot and P. L. Hammer, “On the use of boolean functions in 0-1 programming,” Methods of Operations Research, vol. 12, pp. 154-184, 1972. [14] P. L. Hammer and U. N. Peled, “On the maximization of a pseudo-boolean function,” Journal of the Association for Computing Machinery, vol. 19, pp. 265- 282, 1972. [15] J. J. H. Forrest, J. P. H. Hirst, and J. A. Tomlin, “Practical solution of large mixed integer programming problems with UMPIRE,” Management Science, vol. 20, pp. 736-773, 1974. [16] A. Geoffrion and R. Marsten, “Integer programming algorithms: a framework and state-of-the-art survey,” Management Science, vol. 18, pp. 465-491, 1972. [17] A. Land and S. Powell, “Computer codes for problems of integer programming,” Discrete Optimization II, pp. 221-269, 1979. [18] C. D. Laird, L.T. Biegler, and A. Waechter, “IPOPT Tutorial,” Presented at INFORMS, 2004. [19] R. H. Byrd, and M. E. Hribar, and J. Nocedal, “An interior point algorithm for large scale nonlinear programming,” Optimization Technology Center, Northwestern University, 1997. [20] R. J. Vanderbei and D. F. Shanno. “An interior point algorithm for nonconvex nonlinear programming.” Technical Report SOR9721, CEOR, Princeton University, Princeton, NJ, 1997. [21] P. E. Gill, W. Murray, M. A. Saunders, and M. H. Wright, “User's Guide for NPSOL (Version 4.0): A Fortran Package for Nonlinear Programming. Technical Report SOL 86-2,” Department of Operations Research, Stanford University, Stanford, California, 1986. [22] L. T. Biegler, J. Nocedal, C. Schmid, and D. J. Ternet, “Numerical experience with a reduced Hessian method for large scale constrained optimization,” Computational Optimization and Applications, vol. 15, pp. 45-67, 2000. [23] P. E. Gill, W. Murray, and M. A. Saunders, “User's guide for SNOPT: A FORTRAN package for large-scale nonlinear programming,” Technical report, Department of Mathematics, University of California, San Diego, 1998. [24] J. T. Betts, Practical Methods for Optimal Control Using Nonlinear Programming, SIAM, Philadelphia, 2001. [25] J. E. Dennis, M. Heinkenschloss, and Vicente, “Trust-region interior-point SQP algorithms for a class of nonlinear programming problems,' SIAM Journal on Control and Optimization, vol. 36, pp. 1750-1794. 1998. [26] A. R. Conn, N. Gould, and P. Toint, Trust Region Methods, SIAM, Philadelphia, 2000. [27] B. A. Murtagh and M. A. Saunders, “MINOS 5.1 User’s Guide,” Technical Report SOL 83-20R, Stanford University, 1987. [28] T. F. Edgar, D. M. Himmelblau, and L. S. Lasdon, Optimization of Chemical Processes, McGraw-Hill, New York, 2001. [29] P. E. Gill, W. Murray, and M. H. Wright, Practical Optimization, Academic Press, New York, 1981. [30] K. Zhou, J. C. Doyle, and K. Glover, Robust and Optimal Control, Prentice-Hall, New Jersey, 1996. [31] S. J. Wright, Primal-Dual Interior Point Methods, SIAM, Philadelphia, 1996. [32] C. W. Wu and C. K. Toh, “AMRIS: a multicast protocol for ad hoc wireless networks,” Proceedings of the IEEE Military Communications Conference, vol. 1, 1999, pp. 25-29. [33] M. S. Corson and S. G. Batsell, “A reservation-based multicast (RBM) routing protocol for mobile networks: initial route construction phase,” ACM/Baltzer Journal of Wireless Networks, vol. 1, no. 4, pp. 427-450, 1995. [34] E. M. Royer and C. E. Perkins, “Multicast operation of the ad hoc on-demand distance vector routing protocol,” in Proceedings of ACM MOBICOM, 1999, pp. 207-218. [35] J. Xie, R. R. Talpade, A. Mcauley, and M. Liu, “AMRoute: ad hoc multicast routing protocol,” ACM/Kluwer Journal of Mobile Networks and Applications, vol. 7, pp. 429-439, 2002. [36] S. K. S. Gupta and P. K. Srimani, “Cored-based tree with forwarding regions (CBT-FR): a protocol for reliable multicasting in mobile ad hoc networks,” Journal of Parallel and Distributed Computing, vol. 61, no. 9, pp. 1249-1277, 2001. [37] K. Chan and K. Nahrstedt, “Effect location-guided tree construction algorithms for small group multicast in MANET,” Proceedings of the 21th International Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 3, 2002, pp. 1180-1189. [38] L. Ji and M. S. Corson, “A lightweight adaptive multicast algorithm,” Proceedings of the IEEE Global Telecommunications Conference, vol. 2, 1998, pp. 1036-1042. [39] S. J. Lee and M. Gerla, “On-demand multicast routing protocol in multihop wireless mobile networks,” ACM/Kluwer Journal of Mobile Networks and Applications, vol. 7, pp. 441-453, 2002. [40] J. J. Garcia-Luna-Aceves and E. L. Madruga, “The core-assisted mesh protocol,” IEEE Journal on Selected Areas in Communications, vol. 17, pp. 1380-1394, 1999. [41] C. C. Chiang, M. Gerla, and L. Zhang, “Forwarding group multicast protocol (FGMP) for multihop, mobile wireless networks,” ACM/Baltzer Journal of Cluster Computing: Special Issue on Mobile Computing, vol. 1, no. 2 pp. 187-196, 1998. [42] U. C. Kozat, G. Kondylis, B. Ryu, and M. K. Marina, “Virtual dynamic backbone for mobile ad-hoc networks,” Proceedings of the IEEE International Conference on Communications, vol. 1, 2001, pp. 250-255. [43] R. Sivakumar, P. Sinha, and V. Bharghavan, ”CEDAR: A Core-Extraction Distributed Ad Hoc Routing Algothrim,” IEEE Journal on Selected Areas in Communications, vol. 17, pp. 1454-1465, August 1999. [44] P. Sinha, R. Sivakumar, and V. Bhanghavan, “MCEDAR: multicast core-extraction distributed ad-hoc routing,” Proceedings of the IEEE Wireless Communications and Networking Conference, 1999, pp. 1313-1317. [45] R. Sivakumar, B. Das, and V. Bharghavan, “Spine routing in ad-hoc networks,” ACM/Baltzer Journal of Cluster Computing: Special Issue on Mobile Computing, vol. 1, no. 2, pp. 237-248, 1998. [46] C. Jaikaeo and C. C. Shen, “Adaptive backbone-based multicast for ad hoc networks,” Proceedings of the IEEE International Conference on Communications, vol. 5, 2002, pp. 3149-3155. [47] S. Chen and K. Nahrstedt, ”Distributed quality-of-service routing in ad hoc networks,” IEEE Journal on Selected Areas in Communications, vol. 41, pp. 120-124, June 1999. [48] Q. Xue and A. Ganz, ”Ad hoc QoS on-demand routing (AQOR) in mobile ad hoc networks,” ACDEMIC PRESS: Journal of Parallel and Distributed Computing, vol. 41, pp. 120-124, June 2003. [49] E. Pagani, G.P. Rossi, “A framework for the admission control of QoS multicast traffic in mobile ad hoc networks,” Proceedings of the ACM International Workshop on Wireless Mobile Multimedia, 2001, pp. 3-12. [50] V. V. Vazirani, Approximation Algorithms, Springer-Verlag: Berlin Heidelberg 2001. [51] D. B. Shmoys, E. Tardos, and K. Aardal, “Approximation algorithms for facility location problem,” Proceedings of the 29th Annual ACM Symposium on Theory of Computing, 1997, pp. 265-274. [52] M. Charikar and S. Guha, “Improved combinatorial algorithm for facility location and k-media problems,” Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, 1999, pp. 378-388. [53] K. Jain and V. Vazirani, “Primal-dual approximation algorithms for metric facility location and k-media problems, Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, 1999, pp. 2-13. [54] J. H. Lin and J. S. Vitter, “e-approximations with minimum packing constraint violations,” Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992, pp. 771-782. [55] D. Hochbaum and D. Shmoys, “A Best Possible Heuristic for the K-center Problem,” Math of Operations Research, vol. 10(2), pp. 180-184, 1985. [56] A. Meyerson, “Profit-earning facility location,” Proceedings of the 33th Annual ACM Symposium on Theory of Computing, 2001, pp. 30-36. [57] V. Devarapalli and D. Sidhu, “MZR: a multicast protocol for mobile ad hoc networks,” Proceedings of the IEEE International Conference on Communications, 2001, pp. 3149-3155. [58] E. M. Belding-Royer and C. E. Perkins, “Transmission range effects on AODV multicast communication,” ACM/Kluwer Journal of Mobile Networks and Applications, vol. 7, pp. 455-470, 2002. [59] V. Devarapalli and D. Sidhu, “MZR: a multicast protocol for mobile ad hoc networks,” Proceedings of the IEEE International Conference on Communications, 2001, pp. 3149-3155. [60] Z. J. Haas and M. R. Pearlman, “The zone routing protocol (ZRP) for ad hoc networks,” Internet Draft, draft-ietf-manet-zone-zrp-02.txt, June 1999. [61] E. L. Johnson and S. Powell, “Integer programming codes,” Design and Implementation of Optimization Softwar, NATO Advanced Study Institute Series, Sijthoff & Noordhoff, pp. 225-248, 1978. [62] M. L. Fisher, “The Lagrangian method for solving integer programming problems,” Management Science, vol. 27, pp. 1-18, 1981. [63] M. Guignard and S. Kim, “Lagrangian decomposition: a model yielding stronger Lagrangian bounds,” Mathematical Programming, vol. 39, pp. 215-228, 1987. [64] M. Padberg and G. Rinaldi, “A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems,” SIAM Review, vol. 33, pp. 60-100, 1991. [65] K. L. Hoffman and M. Padberg, “LP-based combinatorial problem solving,” Annals Operations Research, vol. 4, pp. 145-194, 1985. [66] K. L. Hoffman and M. Padberg, “Improving the LP-representation of zero-one linear programs for branch-and-cut,” ORSA Journal Computing, vol. 3, pp. 121-134, 1991. [67] K. L. Hoffman and M. Padberg, “Solving airline crew scheduling problems by branch-and-cut,” Management Science, vol. 39, pp. 657-682, 1993. [68] M. Barahona, M. Grötschel, G. Jünger, and G. Reinelt, “An application of combinatorial optimization to statistical physics and circuit layout design,” Operations Research, vol. 36, pp. 493-513, 1988. [69] S. Chopra, E. Gorres and M. R. Rao, “Solving the steiner tree problem on a graph using branch and cut,” ORSA Journal on Computing, vol. 4, pp. 320-335, 1992. [70] M. Grötschel, C. L. Monma, and M. Stoer, “Computational results with a cutting plane algorithm for designing communication networks with low-connectivity constraint,' Report No. 187, Schwerpunktprogramm der Deutschen Forschungsgemeinschaft, Universität Augsburg, 1989. [71] T. L. Magnanti and R. Vachani. “A strong cutting plane algorithm for production scheduling with changeover costs,” Operations Research, vol. 38, pp. 456-473, 1990. [72] Y. Pochet and L. A. Wolsey, “Solving multi-item lot sizing problems using strong cutting planes,” Management Science, vol. 37, pp. 53-67, 1991. [73] T. J. VanRoy and L. A. Wolsey, “Solving mixed integer programming problems using automatic reformulation,” Operations Research, vol. 35, pp. 45-57, 1987. [74] P. Agrawal, D.K. Anvekar, and B. Narendran, “Optimal prioritization of handovers in mobile cellular networks,” Proceedings of the IEEE PIMRC, 1994, pp. 1393-1398. [75] B. Narendran, P. Agrawal, and D.K. Anvekar, “Minimizing cellular handover failures without channel utilization loss,” Proceedings of the IEEE GLOBECOM, 1994, pp. 1679-1685. [76] C. K. Toh, “Associativity-based routing for ad hoc networks,” Wireless Personal Communications, vol. 4, no. 2, pp. 103-139, 1997. [77] C. K. Toh, Wireless ATM & Ad-Hoc Networks, Kluwer Nov. 1996. [78] R. Dube, C. D. Rais, K.-Y. Wang, and S. K. Tripathi, “Signal stability based adaptive routing (SSA) for ad-hoc mobile networks,” IEEE Personal Communications, vol. 4, no. 1, pp. 36-45, 1997. [79] Network Simulator (Version 2), http://www.isi.edu/nsnam/ns/. [80] C. Bettstetter, G. Resta, and P. Santi, “The node distribution of the random waypoint mobility for wireless ad hoc,” IEEE Transactions on Mobile Computing, vol. 2, no. 3, pp. 257-269, 2003. [81] H. Lim and C. Kim, “Multicast tree construction and flooding in wireless ad hoc networks,” Proceedings of the ACM international workshop on Modeling, analysis and simulation of wireless and mobile systems, 2000, pp. 61-68. [82] V. Bharghavan, A. Demers, S. Shenker, and L. Zhang, “MACAW: A Media Access Protocol for Wireless LAN’s,” in Proceedings of ACM SIGCOMM, 1994, pp. 212-225. [83] K. Bharath-Kumar and J. M. Jaffe, ”Routing to multiple destinations in computer networks,” IEEE Transaction on Communications, vol. 31, pp. 343-351, 1983. [84] C. P. Low and X. Song, ”On finding feasible solutions for the delay constrained group multicast routing problem,” IEEE Transaction on Computers, vol. 51, pp. 581-588, 2002. [85] V P. Kompella, J. C. Pasquale and G. C. Polyzos, ”Multicast routing for multimedia communication,” IEEE Transaction on Computers, vol. 51, pp. 581-588, 2002. [86] Q. Sun and H. Langendoerfer, ”Multicast routing for multimedia communication,” Proceedings of Second Wokshop Protocols for Multimedia Systems, 1995, pp. 452-458. [87] Y. S. Chen, Y. C. Tseng, J. P. Sheu, and P. H. Kuo, “An on-demand, link-state, multi-path QoS routing in a wireless mobile ad-hoc network,” Computer Communications, Vol. 27, No. 1, 2004, pp. 27-40. [88] Y. Ho and R. Liu, “On-demand QoS-based routing protocol for ad hoc mobile wireless networks,' Proceedings of IEEE Symposium on Computers and Communications, pp. 560-565, 2000. [89] Y. C. Hu and D. B. Johnson, “Caching strategies in On-demand routing protocols for wireless ad hoc networks,” Proceedings of MOBICOM, pp. 231-242, 2000. [90] W. H. Liao, Y. C. Tseng, J. P. Sheu, and S. L. Wang, “A multi-path QoS routing protocol in a wireless mobile ad hoc network,” Telecommunication Systems, vol. 19, pp. 329-347, 2002. [91] C. R. Lin, “On-demand QoS routing in multihop mobile networks,” Proceedings of IEEE INFOCOM, 2001, pp. 1735-1744. [92] C. R. Lin and J. S. Liu, “QoS routing in ad hoc wireless networks,” IEEE Journal on Selected Areas in Communications, vol. 17, pp. 1426-1438, 1999. [93] H. C. Lin and P. C. Fung, “Finding available bandwidth in multihop mobile wireless networks,” Proceedings of IEEE Vehicular Technology Conference, pp. 15-18, 2000. [94] R. Battiti, A. A. Bertossi, and M. Brunato, “Distributed code assignment in multihop radio networks: object-oriented software simulations,” Proceedings of SoftCOM, pp. 1-9, 2000. [95] H. S. Chhaya and S. Gupta, “Throughput and fairness properties of asynchronous data transfer method in the IEEE 802.11 MAC protocol”, Proceedings of Personal, Indoor, Mobile, and Radio Communication, pp. 613-617, 1995. [96] B. P. Crown, I. Widjaja, J. G. Kim, and P. Sakai, “Investigation of the IEEE 802.11 medium access control (MAC) sublayer functions,” Proceedings of INFOCOM, vol. 1, pp. 126-133, 1997. [97] J. Weinmiller, H. Woesner, and A. Wolisz, “Analyzing and improving the IEEE 802.11-MAC protocol for wireless LANs,” Proceedings of MASCOT, pp. 200-206, 1996. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/38264 | - |
| dc.description.abstract | 為了有效管理封包之傳遞，近年來在大型隨意網路(MANET)上之多重通訊協定(multicast protocols)主要採取兩階層架構(two-tier infrastructures)之設計。但是這些多重通訊協定有以下三個缺點。第一，它們選取有較多相鄰通訊點之通訊點作為主幹通訊點(backbone hosts)來代理封包的遞送。此種選取方式易造成大量封包集中在這些主幹通訊點而形成網路瓶頸。第二，它們在選取主幹通訊點時未考量其移動性，因此易造成大量封包之遺失。第三，它們未能提供不同等級傳輸服務品質(Quality-of-Service)之功能。為滿足多媒體或其它有及時性需求之應用程式，多重通訊協定必須具備此功能。
本論文之目的在於發展一套適用於大型隨意網路上之兩階層架構多重通訊協定。為了避免上述三項缺點，此新協定有以下五個設計目標。這五個設計目標同時也是目前在大型隨意網路上發展多重通訊協定的主要挑戰工作。 (1)減少控制封包(control packets)數目及避免封包在網路上無限制地濫送 (flooding)。 (2)減少網路壅塞。 (3)縮短多重通訊路徑。 (4)選擇移動性較低之主幹通訊點。 (5)提供不同等級傳輸服務品質之功能。 為了建立兩階層架構，我們首先必須挑選主幹通訊點。我們嘗試將此問題以數學規劃來表示。數學規劃是一種數學模式且已被證明非常適用於解決在已知限制條件(constraints)下對有限資源做最佳配置(optimal allocation)之問題。上述五個設計目標將表成數學規劃之目標函數(objective functions)與限制條件。然後，藉由解出數學規劃之一組有效解(feasible solution)，主幹通訊點便可決定。我們將運用這些主幹通訊點來完成一套符合我們需要的多重通訊協定。以下是此多重通訊協定所具備之功能。 (1)建立與管理兩階層架構。 (2)建立多重通訊路徑。 (3)管理多重通訊群組之動態關係(dynamic group membership)。 (4)因應通訊點之移動，隨時更新多重通訊路徑與調整兩階層架構。 (5)提供一個進出控管機制(admission control mechanism)以滿足多重通訊應用程式傳輸服務品質之需求。 我們所設計之多重通訊協定，不僅能建立一個具有較少控制封包與較少遺失封包之穩定兩階層架構，而且能建立較短的多重通訊路徑與滿足多重通訊應用程式傳輸頻寬(bandwidth)之需求。 | zh_TW |
| dc.description.abstract | Recent multicast protocols for large-scale mobile ad hoc networks (MANETs) adopted two-tier infrastructures to achieve effective flooding schemes. They have three disadvantages. First, hosts with a large number of neighbors were selected as backbone hosts (BHs) for forwarding packets. It is very likely that these BHs will become traffic concentrations or bottlenecks of the networks. Second, they suffered from more lost packets because they did not consider host mobility in selecting BHs. Third, they did not provide quality-of-service (QoS) function. A multicast protocol is desired to provide different levels of QoS for multimedia and real-time applications.
In this dissertation, we aim to develop a new two-tier multicast protocol for a large-scale MANET. In order to avoid the above disadvantages, the new multicast protocol has the following five design goals, which are the main challenges to providing multicast services in MANETs. (1)To reduce the number of control packets and avoid flooding over the entire network. (2)To lower traffic concentrations and bottlenecks of the network. (3)To shorten multicast routes. (4)To select stable BHs. (5)To provide the QoS function. To establish a two-tier infrastructure, BHs will be selected first. We attempt to formulate the problem of selecting BHs by mathematical programming (MP), which is a mathematical model that has been proved useful for optimal allocation of limited resources to known activities under some constraints. The five design goals are merged into the formulated MP as objective functions and constraints. Then BHs will be determined by solving the formulated MP for a feasible solution. Finally, the new multicast protocol will be developed based on the selected BHs. The new multicast protocol is responsible for the following tasks. (1)Establish and maintain the infrastructure. (2)Construct multicast routes. (3)Manage dynamic group membership. (4)Update multicast routes and adjust the infrastructure in response to host movements. (5)Provide an admission control mechanism. The new multicast protocol not only establishes a stable two-tier infrastructure with fewer control packets transmitted and fewer data packets lost, but also constructs shorter multicast routes and meets the bandwidth requirements of multicast applications. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-13T16:29:04Z (GMT). No. of bitstreams: 1 ntu-94-D90922017-1.pdf: 989176 bytes, checksum: 41d1fa90828fc32aaa27c1095f4d1278 (MD5) Previous issue date: 2005 | en |
| dc.description.tableofcontents | 摘 要 I
Abstract III Contents V Tables and Figures IX Chapter 1 Introduction 1 1.1 Mobile Ad-Hoc Networks 1 1.2 Multicast 4 1.3 Mathematical Programming 6 1.3.1 Linear Programming 7 1.3.2 Nonlinear Programming 9 1.4 Problems 9 1.5 An Integer Programming Approach 16 1.6 Goals 18 1.7 Dissertation Overview 20 1.7.1 A New Two-Tier Multicast Protocol 21 1.7.2 A Mobility-Aware Two-Tier Multicast Protocol 22 1.7.3 Bandwidth-Satisfied Multicast Routes 23 Chapter 2 Related Work 25 2.1 Previous Multicast Protocols 25 2.1.1 Tree-Based Protocols 25 2.1.2 Tree-Based Protocols 27 2.1.3 Two-Tier Protocols 29 2.2 Previous QoS Routing/Multicasting Protocols 30 2.2.1 Link-Based Protocols 31 2.2.2 Host-Based Protocols 32 2.3 Algorithms for Integer Linear Programming 32 2.3.1 Enumerative Methods 33 2.3.2 Branch-and-Bound Methods 34 2.3.3 Lagrangian Relaxation and Decomposition Methods 34 2.3.4 Cutting Plane Methods 35 2.3.5 Branch-and-Cut Methods 36 Chapter 3 A Two-Tier Multicast Protocol 39 3.1 Finding BHs 39 3.2 Protocol Design 44 3.2.1 Selecting BHs 45 3.2.2 Determining Multicast Routes 48 3.2.3 Merging Multicast Regions 52 3.2.4 Handling Host Mobility 57 3.3 Performance Evaulation 59 3.3.1 Comparison of BH Section Strategies 60 3.3.2 Comparison of Two-Tier Multicast Protocols 64 Chapter 4 A Mobility-Aware Two-Tier Multicast Protocol 73 4.1 Link Prediction 73 4.2 Finding Stable BHs 75 4.3 Protocol Design 79 4.3.1 Selecting Stable BHs 80 4.3.2 Determining Stable Multicast Routes 82 4.3.3 Updating Multicast Routes 83 4.4 Performance Evaulation 85 Chapter 5 Bandwidth-Satisfied Multicast Routes 93 5.1 Two Bandwidth-Violation Problems 94 5.1.1 HRP 94 5.1.2 HMRP 95 5.1.3 Performance Effect of HRP and HMRP 97 5.2 Finding Bandwidth-Satisfied Multicast Trees 98 5.3 Protocol Design 103 5.3.1 A Basic Procedure 103 5.3.2 A Bandwidth-Satisfied Multicast Tree 107 5.4 Performance Evaulation 111 5.4.1 HRP and HMRP Aviodance 112 5.4.2 Performance Comparison: Static Hosts 117 5.4.3 Performance Comparison: Mobile Hosts 120 Chapter 6 Conclusion 123 6.1 Summary 123 6.2 Future Work 127 References 129 | |
| dc.language.iso | en | |
| dc.subject | 最佳化 | zh_TW |
| dc.subject | 隨意網路 | zh_TW |
| dc.subject | 數學規劃 | zh_TW |
| dc.subject | 多重通訊 | zh_TW |
| dc.subject | mathematical programming | en |
| dc.subject | optimization | en |
| dc.subject | multicast | en |
| dc.subject | Ad hoc network | en |
| dc.title | 應用數學規劃在大型隨意網路上多重通訊協定之研究 | zh_TW |
| dc.title | Multicasting on Large-Scale Mobile Ad-Hoc Networks with Mathematical Programming | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 93-2 | |
| dc.description.degree | 博士 | |
| dc.contributor.coadvisor | 吳曉光 | |
| dc.contributor.oralexamcommittee | 賴威光,歐陽彥正,劉邦鋒,趙坤茂,林俊宏 | |
| dc.subject.keyword | 隨意網路,數學規劃,多重通訊,最佳化, | zh_TW |
| dc.subject.keyword | Ad hoc network,mathematical programming,multicast,optimization, | en |
| dc.relation.page | 143 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2005-07-13 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-94-1.pdf 未授權公開取用 | 965.99 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。