請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/36063
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 林永松 | |
dc.contributor.author | Lin-Chih Fu | en |
dc.contributor.author | 傅琳智 | zh_TW |
dc.date.accessioned | 2021-06-13T07:50:37Z | - |
dc.date.available | 2006-07-30 | |
dc.date.copyright | 2005-07-30 | |
dc.date.issued | 2005 | |
dc.date.submitted | 2005-07-25 | |
dc.identifier.citation | 【1】 Ahuja, R. K., Magnanti, T. L. and Orlin, J. B., “Network flows : theory, algorithms, and applications”, London: Prentice-Hall International (1993)
【2】 Bertsekas, D. and Gallager, R., “Data Networks – second edition”, Englewood Cliffs: Prentice-Hall (1992) 【3】 Broch, J., Maltz, D. A., Johnson, D. B., Hu, Y-C and Jetcheva, J., “A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols”, in Proceedings of ACM/IEEE International Conference on Mobile Computing and Networking (MOBICOM) (1998), pp. 85-97 【4】 Camp, T., Boleng, J. and Davies, V., “A Survey of Mobility Models for Ad Hoc Network Research”, Wireless Communications & Mobile Computing, Vol. 2, No. 5 (2002), pp. 483-502 【5】 Cavin, D., Sasson, Y. and Schiper, A., “On the Accuracy of MANET Simulators”, in Proceedings of ACM International Workshop on Principles of Mobile Computing (2002), pp. 38-43 【6】 Clementi, A. E. F., Crescenzi, P, Penna, P., Rossi, G. and Vocca, P., “On the Complexity of Computing Minimum Energy Consumption Broadcast Subgraphs”, in Proceedings of Annual Symposium on Theoretical Aspects of Computer Science (STACS), Vol. 2010 (2001), pp. 121-131 【7】 Das, A. K., Marks, R. J., El-Sharkawi, M., Arabshahi, P. and Gray, A., “Minimum Power Broadcast Trees for Wireless Networks: Integer Programming Formulations”, in proceedings of IEEE INFOCOM, Vol. 2 (2003), pp. 1001-1010 【8】 Fisher, M. L., “The Lagrangian Relaxation Method for Solving Integer Programming Problems”, Management Science, Vol. 27, No.1 (1981), pp. 1-18 【9】 Frodigh, M., Johansson, P. and Larsson, P., “Wireless Ad Hoc Networking: The Art of Networking without a Network”, Ericsson Review, No. 4 (2000), pp. 248-263 【10】 Haas, Z. J. and Tabrizi, S., “On some challenges and design choices in ad-hoc communications”, in proceedings of IEEE Military Communications Conference (MILCOM), Vol. 1 (1998), pp. 187-192 【11】 Held, M., Wolfe, P. and Crowder, H. P., “Validation of Subgradient Optimization”, Mathematical Programming, Vol. 6 (1971), pp. 62-88 【12】 Jeffery, E. W., Nguyen, G. D. and Ephremides, A., “Algorithms for Energy-Efficient Multicasting in Static Ad Hoc Wireless Networks”, Mobile Networks and Applications, Vol. 6, No. 3 (2001), pp. 251-263 【13】 Kang, I. and Poovendran, R., “On Lifetime Extension and Route Stabilization of Energy-Efficient Broadcast Routing over MANET”, in Proceedings of International Network Conference (INC), (2002) 【14】 Lee, S-J, Gerla, M. and Chiang, C-C, “On-Demand Multicasting Routing Protocol”, in Proceedings of IEEE Wireless Communications and Networking Conference (WCNC), Vol. 3 (1999), pp. 1298-1302 【15】 Lee, S-J, Su, W. and Gerla, M., “On-Demand Multicast Routing Protocol in Multihop Wireless Mobile Networks”, Mobile Networks and Applications, Vol. 7, No. 6 (2002), pp. 441-453 【16】 Liang, B. and Haas, Z. J., “Predictive Distance-Based Mobility Management for Multidimensional PCS Networks”, IEEE/ACM Transactions on Networking, Vol. 11, No. 5 (2003), pp. 718-732 【17】 Liang, W., “Constructing Minimum-Energy Broadcast Trees In Wireless Ad-Hoc Networks”, in Proceedings of International Symposium on Mobile Ad Hoc Networking & Computing (2002), pp. 112-122 【18】 Maltz, D. A., Broch, J., Jetcheva, J. and Johnson, D. B., “The Effects of On-Demand Behavior in Routing Protocols for Multihop Wireless Ad Hoc Networks”, IEEE Journal on Selected Areas in Communications, Vol. 17, No. 8 (1999), pp. 1439-1453 【19】 Marks, R. J., Das, A. K. and El-Sharkawi, M., “Maximizing Lifetime in an Energy Constrained Wireless Sensor Array Using Team Optimization of Cooperating Systems”, in Proceedings of International Joint Conference on Neural Networks, Vol. 1 (2002), pp. 371-376 【20】 Marks, R. J., Das, A. K., El-Sharkawi, M., Arabshahi, P. and Gray, A., “Minimum Power Broadcast Trees for Wireless Networks: Optimizing Using the Viability Lemma”, in Proceedings of IEEE International Symposium on Circuits and Systems, Vol. 1 (2002), pp. 273-276 【21】 Musolesi, M., Hailes, S. and Mascolo, C., “An Ad Hoc Mobility Model Founded on Social Network Theory”, in Proceedings of ACM International Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems (2004), pp. 20-24 【22】 Obraczka, K. and Tsudik, G., “Multicast Routing Issues in Ad Hoc Networks”, in Proceedings of IEEE International Conference on Universal Personal Communications (ICUPC), Vol. 1 (1998), pp. 751-756 【23】 Perkins, C. E., “Ad Hoc Networking”, Boston: Addison-Wesley Publishing Company (2002) 【24】 Raychaudhuri, D. and Wilson, N. D., “ATM-Based Transport Architecture for Multiservices Wireless Personal Communication Networks”, IEEE Journal on Selected Areas in Communications, Vol. 12, No. 8 (1994), pp. 1401-1414 【25】 Royer, E. M. and Toh, C-K, “A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks”, IEEE Personal Communications, Vol. 6, No.2 (1999), pp. 46-55 【26】 Wieselthier, J. E., Nguyen, G. D. and Ephremides, A., “On the Construction of Energy-Efficient Broadcast and Multicast Trees in Wireless Networks”, in proceedings of IEEE INFOCOM, Vol. 2 (2000), pp. 585-594 | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/36063 | - |
dc.description.abstract | 移動性的Ad Hoc網路使用無線傳播,是一個不需事先決定網路拓樸設計的網路。這種網路架構的特性使得它可以被快速的部署,並且不需依賴已存的基礎建設。值得注意的是在這顯著的特徵下,它適合使用在設計階段無法預測的網路架構的應用。
然而,在設計移動性的Ad Hoc網路存在很多關鍵的挑戰需要被解決。其中三個主要的挑戰是: 1) 缺乏集中式管理, 2) 節點的自主移動, 3) 所有通訊透過無線媒介傳播。 本篇論文我們著重在探討當每個節點受限於有限的電力資源,且整個路由的路徑是由每個自主移動的節點所組成的情況下,要如何以低能耗的路由決策,成功傳送資料給群播成員,在會因為節點移動而導致傳輸中斷,而需要重新作路由決策的網路拓樸。 不同於傳統設計的單層結構,我們同時考慮在有效的傳送半徑範圍內(網路連接性,屬實體層)以及群播樹的建立(路由功能,屬網路層),來做出低能耗的路由決策。我們將此問題設計成最佳化的數學模型,並且採用拉格蘭日鬆弛法(Lagrangian relaxation)為基礎的方法來處理此複雜的問題。 | zh_TW |
dc.description.abstract | The Mobile Ad Hoc Network (MANET) is an emerging network topology based on a radio propagation model. The network topology, which is neither fixed nor predetermined, can be rapidly deployed and does not need to rely on a pre-existing infrastructure. It is noteworthy that this salient feature makes it suitable for the network operations that, by their nature, are unpredictable during the design stage.
However, a lot of critical challenges in the design and operation of MANET need to be solved. The three main challenges come from: 1) the lack of a centralized entity, 2) the possibility of platform movements, 3) the fact that all the communication is carried over the wireless medium. The issues we address here are 1) a node operates on limited battery resources, and 2) multi-hop routing paths are used over constantly changing network environments due to node mobility. Hence, efficient utilization of routing packets and immediate recovery of route breaks are critical in routing and multicasting protocols in MANET. Our approach to energy-efficient communication departs from the traditional layered structure in that we jointly address the issues of transmitted power levels (a network connectivity function, related to the Physical layer) and multicast tree formulation (a routing function, associated with the Network layer). We model the problem as a linear integer mathematical programming problem. In addition, we propose a set of heuristic solution procedures based on Lagrangian relaxation methods to solve the complicated problem. | en |
dc.description.provenance | Made available in DSpace on 2021-06-13T07:50:37Z (GMT). No. of bitstreams: 1 ntu-94-R92725019-1.pdf: 511258 bytes, checksum: edc6a447075dbf40d535fe613f11f5d3 (MD5) Previous issue date: 2005 | en |
dc.description.tableofcontents | 謝詞 III
論文摘要 IV THESIS ABSTRACT V TABLE OF CONTENTS VII LIST OF TABLES IX LIST OF FIGURES X CHAPTER 1 INTRODUCTION 1 1.1 BACKGROUND 1 1.2 MOTIVATION 3 1.3 LITERATURE SURVEY 5 1.3.1 Minimal power consumption in wireless networks 5 1.3.2 Gauss-Markov mobility model 6 1.3.3 Adapting the refresh interval via mobility prediction 8 1.3.4 Lagrangian relaxation 10 1.4 PROPOSED APPROACH 12 CHAPTER 2 PROBLEM FORMULATION 13 2.1 PROBLEM DESCRIPTION 13 2.2 NOTATION 17 2.3 PROBLEM FORMULATION 19 CHAPTER 3 SOLUTION APPROACH 24 3.1 LAGRANGIAN RELAXATION 24 3.1.1 Subproblem1 (related to decision variable ) 26 3.1.2 Subproblem2 (related to decision variable ) 27 3.1.3 Subproblem3 (related to decision variable ) 29 3.1.4 Subproblem4 (related to decision variable ) 35 3.2 THE DUAL PROBLEM AND THE SUBGRADIENT METHOD 36 CHAPTER 4 GETTING PRIMAL FEASIBLE SOLUTION 37 4.1 HEURISTIC FOR ROUTING POLICY ADJUSTMENT 37 CHAPTER 5 COMPUTATIONAL EXPERIMENT 41 5.1 LARGRANGIAN RELAXATION BASE ALGORITHM (LR) 41 5.2 EXPERIMENT ENVIRONMENTS 43 5.2.1 Assumptions 43 THE ASSUMPTIONS WE MAKE IN THIS STUDY ARE AS FOLLOWS: 43 5.2.2 Parameters 43 5.3 SCENARIOS AND EXPERIMENT RESULTS 44 5.3.1 Scenario 1 (controlling factor: number of destination nodes) 44 5.3.2 Scenario 2 (controlling factor: mobility pattern) 46 5.3.3 Scenario 3 (controlling factor: maximum power radius) 47 CHAPTER 6 CONCLUSION 48 6.1 SUMMARY 48 6.2 FUTURE WORK 49 REFERENCES 50 簡歷 53 | |
dc.language.iso | en | |
dc.title | 移動性Ad Hoc 網路之低能耗群播路由演算法研究 | zh_TW |
dc.title | Energy-Efficient Multicast Routing in Mobile Ad Hoc Networks | en |
dc.type | Thesis | |
dc.date.schoolyear | 93-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 顏宏旭,趙啟超,林盈達,呂俊賢 | |
dc.subject.keyword | 移動性的Ad Hoc 網路,能源最佳化,移動性,數學最佳化,拉格蘭日鬆弛法, | zh_TW |
dc.subject.keyword | MANET,Energy-Efficient,Mobility,Mathematical Optimization,Lagrangian Relaxation Method, | en |
dc.relation.page | 53 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2005-07-26 | |
dc.contributor.author-college | 管理學院 | zh_TW |
dc.contributor.author-dept | 資訊管理學研究所 | zh_TW |
顯示於系所單位: | 資訊管理學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-94-1.pdf 目前未授權公開取用 | 499.28 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。