請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/64541
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 傅立成(Li-Chen Fu) | |
dc.contributor.author | Ping-Che Hsiao | en |
dc.contributor.author | 蕭稟哲 | zh_TW |
dc.date.accessioned | 2021-06-16T17:53:26Z | - |
dc.date.available | 2017-08-16 | |
dc.date.copyright | 2012-08-16 | |
dc.date.issued | 2012 | |
dc.date.submitted | 2012-08-13 | |
dc.identifier.citation | [1] S. Okdem, D. Karaboga, and C. Ozturk, 'An application of Wireless Sensor Network routing based on Artificial Bee Colony Algorithm,' in Proceedings of IEEE Congress on Evolutionary Computation, 2011, pp. 326-330.
[2] X. M. Hu, J. Zhang, Y. Yu, H. S. H. Chung, Y. L. Li, Y. H. Shi, and X. N. Luo, 'Hybrid genetic algorithm using a forward encoding scheme for lifetime maximization of wireless sensor networks,' IEEE Transactions on Evolutionary Computation, vol. 14, pp. 766-781, 2010. [3] C.-C. Lai, C.-K. Ting, and R.-S. Ko, 'An effective genetic algorithm to improve wireless sensor network lifetime for large-scale surveillance applications,' in Proceedings of IEEE Congress on Evolutionary Computation, 2007, pp. 3531-3538. [4] M. Younis and K. Akkaya, 'Strategies and techniques for node placement in wireless sensor networks: A survey,' Ad Hoc Networks, vol. 6, pp. 621-655, 2008. [5] W. Guiling, C. Guohong, and T. La Porta, 'Movement-assisted sensor deployment,' in Proceedings of IEEE International Conference on Computer Communications, 2004, pp. 2469-2479. [6] J.-A. Jiang, T.-S. Lin, C.-L. Chuang, C.-P. Chen, C.-H. Sun, J.-Y. Juang, J.-C. Lin, and W.-W. Liang, 'A QoS-guaranteed coverage precedence routing algorithm for wireless sensor networks,' Sensors, vol. 11, pp. 3418-3438, 2011. [7] S. Guo and O. W. W. Yang, 'Energy-aware multicasting in wireless ad hoc networks: A survey and discussion,' Computer Communications, vol. 30, pp. 2129-2148, 2007. [8] M. Čagalj, J.-P. Hubaux, and C. Enz, 'Minimum-energy broadcast in all-wireless networks: NP-completeness and distribution issues,' in Proceedings of the 8th Annual International Conference on Mobile Computing and Networking, 2002, pp. 172-182. [9] W. Liang, 'Constructing minimum-energy broadcast trees in wireless ad hoc networks,' in Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing, Lausanne, Switzerland, 2002, pp. 112-122. [10] C. Miller and C. Poellabauer, 'A decentralized approach to minimum-energy broadcasting in static ad hoc networks,' Ad-Hoc, Mobile and Wireless Networks, vol. 5793, pp. 298-311, 2009. [11] P. Floreen, P. Kaski, J. Kohonen, and P. Orponen, 'Lifetime maximization for multicasting in energy-constrained wireless networks,' IEEE Journal on Selected Areas in Communications, vol. 23, pp. 117-126, 2005. [12] S. Guo and O. Yang, 'Multicast lifetime maximization for energy-constrained wireless ad-hoc networks with directional antennas,' in Proceedings of IEEE Global Telecommunications Conference, 2004, pp. 4120-4124. [13] A. Konstantinidis, K. Yang, H.-H. Chen, and Q. Zhang, 'Energy-aware topology control for wireless sensor networks using memetic algorithms,' Computer Communications, vol. 30, pp. 2753-2764, 2007. [14] J. Bauer, D. Haugland, and D. Yuan, 'A fast local search method for minimum energy broadcast in wireless ad hoc networks,' Operations Research Letters, vol. 37, pp. 75-79, 2009. [15] W. Xiang, W. Xinheng, and L. Rui, 'Solving minimum power broadcast problem in wireless ad-hoc networks using genetic algorithm,' in Proceedings of Communication Networks and Services Research Conference, 2008, pp. 203-207. [16] I. Kang and R. Poovendran, 'Iterated local optimization for minimum energy broadcast,' in Proceedings of International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, 2005, pp. 332-341. [17] M. Cardei and J. Wu, 'Energy-efficient coverage problems in wireless ad-hoc sensor networks,' Computer Communications, vol. 29, pp. 413-420, 2006. [18] J. E. Wieselthier, G. D. Nguyen, and A. Ephremides, 'On the construction of energy-efficient broadcast and multicast trees in wireless networks,' in Proceedings of IEEE International Conference on Computer Communications, 2000, pp. 585-594. [19] I. Kang and R. Poovendran, 'A novel power-efficient broadcast routing algorithm exploiting broadcast efficiency,' in Proceedings of IEEE Vehicular Technology Conference, 2003, pp. 2926-2930. [20] P. J. Wan, G. Călinescu, X. Y. Li, and O. Frieder, 'Minimum-energy broadcasting in static ad hoc wireless networks,' Wireless Networks, vol. 8, pp. 607-617, 2002. [21] R. Klasing, A. Navarra, A. Papadopoulos, and S. Perennes, 'Adaptive Broadcast Consumption (ABC), a new heuristic and new bounds for the minimum energy broadcast routing problem,' in Networking 2004, Lecture Notes in Computer Science. vol. 3042, N. Mitrou, K. Kontovasilis, G. Rouskas, I. Iliadis, and L. Merakos, Eds.: Springer Berlin / Heidelberg, 2004, pp. 866-877. [22] M. X. Cheng, J. Sun, M. Min, and D.-Z. Du, 'Energy-efficient broadcast and multicast routing in ad hoc wireless networks,' in Proceedings of IEEE International Performance, Computing, and Communications Conference, 2003, pp. 87-94. [23] M. X. Cheng, J. Sun, M. Min, Y. Li, and W. Wu, 'Energy-efficient broadcast and multicast routing in multihop ad hoc wireless networks,' Wireless Communications and Mobile Computing, vol. 6, pp. 213-223, 2006. [24] L. Lin and W. Qiwu, 'A label based greedy algorithm for minimum energy consumption multicast routing in ad hoc networks,' in Proceedings of IEEE International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery, 2011, pp. 113-117. [25] A. K. Das, R. J. Marks, M. El-Sharkawi, P. Arabshahi, and A. Gray, 'r-shrink: a heuristic for improving minimum power broadcast trees in wireless networks,' in Proceedings of IEEE Global Telecommunications Conference, 2003, pp. 523-527. [26] S. Guo and O. Yang, 'A dynamic multicast tree reconstruction algorithm for minimum-energy multicasting in wireless ad hoc networks,' in Proceedings of IEEE International Conference on Performance, Computing, and Communications, 2004, pp. 637-642. [27] I. Kang and R. Poovendran, 'Broadcast with heterogeneous node capability,' in Proceedings of IEEE Global Telecommunications Conference, 2004, pp. 4114-4119. [28] F. Li and I. Nikolaidis, 'On minimum-energy broadcasting in all-wireless networks,' in Proceedings of IEEE Conference on Local Computer Networks, 2001, pp. 193-202. [29] P. Hansen and N. Mladenović 'Variable neighborhood search,' Handbook of Metaheuristics, pp. 145-184, 2003. [30] A. Konstantinidis, K. Yang, Q. Zhang, and D. Zeinalipour-Yazti, 'A multi-objective evolutionary algorithm for the deployment and power assignment problem in wireless sensor networks,' Computer Networks, vol. 54, pp. 960-976, 2010. [31] A. Konstantinidis, K. Yang, and Q. Zhang, 'An evolutionary algorithm to a multi-objective deployment and power assignment problem in wireless sensor networks,' in Proceedings of Global Telecommunications Conference, 2008, pp. 1-6. [32] G. Molina and E. Alba, 'Location discovery in Wireless Sensor Networks using metaheuristics,' Applied Soft Computing, vol. 11, pp. 1223-1240, 2011. [33] J.-A. Jiang, C.-P. Chen, C.-L. Chuang, T.-S. Lin, C.-L. Tseng, E.-C. Yang, and Y.-C. Wang, 'CoCMA: Energy-efficient coverage control in cluster-based wireless sensor networks using a memetic algorithm,' Sensors, vol. 9, pp. 4918-4940, 2009. [34] S. Wolf and P. Merz, 'Evolutionary local search for the minimum energy broadcast problem,' in Proceedings of the 8th European Conference on Evolutionary Computation in Combinatorial Optimisation, Lecture Notes in Computer Science. vol. 4972, J. van Hemert and C. Cotta, Eds.: Springer Berlin / Heidelberg, 2008, pp. 61-72. [35] A. Singh and W. N. Bhukya, 'A hybrid genetic algorithm for the minimum energy broadcast problem in wireless ad hoc networks,' Applied Soft Computing, vol. 11, pp. 667-674, 2011. [36] H. Hernandez and C. Blum, 'Ant colony optimization for multicasting in static wireless ad-hoc networks,' Swarm Intelligence, vol. 3, pp. 125-148, 2009. [37] H. Hernandez and C. Blum, 'Minimum energy broadcasting in wireless sensor networks: An ant colony optimization approach for a realistic antenna model,' Applied Soft Computing, vol. 11, pp. 5684-5694, 2011. [38] H. Hernandez, C. Blum, and G. Frances, 'Ant colony optimization for energy-efficient broadcasting in ad-hoc networks,' in Proceedings of International Conference on Ant Colony Optmization and Swarm Intelligence, Lecture Notes in Computer Science. vol. 5217, M. Dorigo, M. Birattari, C. Blum, M. Clerc, T. Stutzle, and A. Winfield, Eds.: Springer Berlin / Heidelberg, 2008, pp. 25-36. [39] H. Hernandez and C. Blum, 'Distributed ant colony optimization for minimum energy broadcasting in sensor networks with realistic antennas,' Computers & Mathematics with Applications, 2012. [40] A. K. Das, R. J. Marks, M. El-Sharkawi, P. Arabshahi, and A. Gray, 'The minimum power broadcast problem in wireless networks: an ant colony system approach,' in Proceedings of IEEE CAS Workshop on Wireless Communications and Networking, Pasadena, CA, 2002. [41] H.-G. Beyer and H.-P. Schwefel, 'Evolution strategies – A comprehensive introduction,' Natural computing, vol. 1, pp. 3-52, 2002. [42] J. Kennedy and R. C. Eberhart, 'Particle swarm optimization,' in Proceedings of IEEE International Conference on Networks, 1995, pp. 1942-1948. [43] T. J. Ai and V. Kachitvichyanukul, 'A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery,' Computers & Operations Research, vol. 36, pp. 1693-1702, 2009. [44] R. V. Kulkarni and G. K. Venayagamoorthy, 'Particle Swarm Optimization in Wireless-Sensor Networks: A Brief Survey,' IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, vol. 41, pp. 262-267, 2011. [45] X. Wang and L. Tang, 'A discrete particle swarm optimization algorithm with self-adaptive diversity control for the permutation flowshop problem with blocking,' Applied Soft Computing, vol. 12, pp. 652-662, 2012. [46] Y. Shi and R. Eberhart, 'Parameter selection in particle swarm optimization,' in Evolutionary Programming VII, Lecture Notes in Computer Science. vol. 1447, V. Porto, N. Saravanan, D. Waagen, and A. Eiben, Eds.: Springer Berlin / Heidelberg, 1998, pp. 591-600. [47] J. Kennedy and R. Mendes, 'Population structure and particle swarm performance,' in Proceedings of IEEE Congress on Evolutionary Computation, 2002, pp. 1671-1676. [48] H. Xiaohui and R. Eberhart, 'Multiobjective optimization using dynamic neighborhood particle swarm optimization,' in Proceedings of IEEE Congress on Evolutionary Computation, 2002, pp. 1677-1681. [49] S. Al-Shihabi, P. Merz, and S. Wolf, 'Nested partitioning for the minimum energy broadcast problem,' in Proceedings of Learning and Intelligent Optimization, Lecture Notes in Computer Science. vol. 5313, V. Maniezzo, R. Battiti, and J.-P. Watson, Eds.: Springer Berlin / Heidelberg, 2008, pp. 1-11. [50] P. Merz. 'Minimum energy broadcast problem (MEB) instances,' http://dag.informatik.uni-kl.de/research/meb/. [51] H. Hernandez. 'Benchmark instances for Minimum Energy Broadcasting/Multicasting,' http://www.lsi.upc.edu/~hhernandez/mem/. [52] S. Guo and O. Yang, 'Minimum-energy multicast in wireless ad hoc networks with adaptive antennas: MILP formulations and heuristic algorithms,' IEEE Transactions on Mobile Computing, vol. 5, pp. 333-346, 2006. [53] M. Clerc and J. Kennedy, 'The particle swarm - explosion, stability, and convergence in a multidimensional complex space,' IEEE Transactions on Evolutionary Computation, vol. 6, pp. 58-73, 2002. [54] F. Gruau and D. Whitley, 'Adding learning to the cellular development of neural networks: Evolution and the Baldwin effect,' Evolutionary Computation, vol. 1, pp. 213-233, 1993. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/64541 | - |
dc.description.abstract | 這篇論文中研究如何解決無線隨意網路(Wireless Ad-hoc Networks)下的最少資源群播(Minimum Energy Broadcast)問題,且此問題已被證明是NP-complete。由於無線隨意網路可以被快速的佈建,因此已被廣泛地應用在不同的領域中,其中一項主要的應用即是無線感測網路(Wireless Sensor Networks)。在無線感測網路中,由於每個感測節點皆只配備了有限的電力資源,因此網路的消耗資源最小化是在研究領域中一個非常重要的議題。最少資源群播問題即是無線感測網路中的一個重要情況,在這個問題中需要把所要傳遞的封包由一個指定的來源節點傳達到網路中其他所有節點上,而這個問題的目的是要將傳送所消耗的資源最小化。我們使用結合了粒子群聚演算法和區域搜尋的混合式方法來解決此問題,我們提出了一個用來定義每個粒子位置的編碼方法,稱作資源階層編碼(power degree encoding);我們也更進一步的分析一個知名的區域搜尋演算法並提出一個改進的版本,稱作強化型r皺縮(intensified r-shrink)。除此之外,為了處理節點故障和節點尋獲下的動態最少資源群播問題,我們在這篇論文中也會使用一個新的架構以快速地連接分離的子網路,其中也提出一個簡易啟發式演算法來選擇連結的對象。實驗結果指出提出的演算法有可被實際應用的潛力。 | zh_TW |
dc.description.abstract | In this thesis, we addressed the NP-complete minimum energy broadcast (MEB) problem in wireless ad-hoc networks (WANETs). The researches in WANETs have attracted significant attentions because of their convenient deployment and a variety of applications including wireless sensor networks (WSNs). One of the most critical issues in WSNs is lifetime maximization and energy consumption minimization because each node in the network is only equipped limited energy resource. The MEB problem is one of the most important scenarios in WSNs, where the packets have to be transported from a given source node to all other nodes in the network. The objective of the MEB problem is to minimize the total transmission power consumption. A hybrid algorithm based on particle swarm optimization (PSO) and local search was presented to solve the MEB problem. We proposed a power degree encoding to reflect the extent of transmission power level, and it was used to define the particle position in PSO. We also analyzed a well-known local search mechanism, r-shrink, and proposed an improved version, the intensified r-shrink. In order to deal with the dynamic MEB problem, which runs into node removal/insertion, this thesis provided a framework for rapidly linking up disconnected components and presented an effective simple heuristic, Conditional Incremental Power, to repair the network. The promising results indicated the potential of proposed method to be applied to practical use. | en |
dc.description.provenance | Made available in DSpace on 2021-06-16T17:53:26Z (GMT). No. of bitstreams: 1 ntu-101-R99922111-1.pdf: 6529914 bytes, checksum: bea668b967e5aff7e55f5912f7d2bd95 (MD5) Previous issue date: 2012 | en |
dc.description.tableofcontents | 摘要 i
ABSTRACT ii CONTENTS iii LIST OF FIGURES vi LIST OF TABLES vii Chapter 1 Introduction 1 1.1 Motivation 1 1.2 Problem Description 3 1.3 Contribution 6 1.4 Organization 7 Chapter 2 Literature Review 8 2.1 Simple Heuristics 8 2.1.1 Broadcast Incremental Power (BIP) 10 2.1.2 Adaptive Broadcast Consumption (ABC) 10 2.1.3 Greedy Perimeter Broadcast Efficiency (GPBE) 11 2.1.4 Minimum Weighted Spanning Tree (MST) and Shortest Path Tree (SPT) 11 2.2 Local Search Algorithms 12 2.2.1 Sweep 12 2.2.2 Embedded Wireless Multicast Advantage (EWMA) 13 2.2.3 Iterative Maximum-Branch Minimization (IMBM) 14 2.2.4 r-shrink 15 2.3 Metaheuristics 16 2.3.1 Evolutionary Local Search Algorithm (ELS) 17 2.3.2 Hybrid Genetic Algorithm (HGA) 17 2.3.3 Ant Colony Optimization (ACO) 18 2.4 Encoding Mechanisms 20 2.4.1 Power Level Encoding 21 2.4.2 Permutation Encoding 22 Chapter 3 Particle Swarm Optimization for the Minimum Energy Broadcast (MEB) Problem 25 3.1 Particle Swarm Optimization (PSO) 25 3.2 Power Degree Encoding 29 3.3 Acceleration 32 3.4 Landing 33 3.4.1 Increasing Power Degree 34 3.4.2 Decreasing Power Degree 35 3.5 Intensified r-shrink 36 3.6 The Proposed PSO Algorithm 40 3.7 Extension to the Dynamic MEB Problem 42 3.7.1 Repairing Scheme 42 3.7.2 Conditional Incremental Power (CIP) 44 Chapter 4 Experiments and Results 47 4.1 Benchmark Instances 47 4.2 Benchmark Algorithms 48 4.3 Parameter Setting 49 4.4 Performance Evaluation in the Static MEB problem 50 4.4.1 50-node Instances 50 4.4.2 100-node Instances 53 4.4.3 Intensified r-shrink 57 4.5 Performance Evaluation in the Dynamic MEB problem 58 4.5.1 Benchmark Instances and Algorithms 58 4.5.2 Node Removal 59 4.5.3 Node Insertion 60 4.5.4 100-node Instances 61 4.6 Discussions 63 Chapter 5 Conclusions and Future Work 65 5.1 Conclusions 65 5.2 Future Work 66 REFERENCE 68 PUBLICATION LIST 75 | |
dc.language.iso | zh-TW | |
dc.title | 以粒子群聚演算法解決無線隨意網路下靜態與動態最少資源群播問題 | zh_TW |
dc.title | Particle Swarm Optimization for the Static and Dynamic Minimum Energy Broadcast Problem in Wireless Ad-Hoc Networks | en |
dc.type | Thesis | |
dc.date.schoolyear | 100-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 蔣宗哲(Tsung-Che Chiang),曹承礎(Seng-Cho Chou),林軒田(Hsuan-Tien Lin),江昭皚(Joe-Air Jiang) | |
dc.subject.keyword | 粒子群聚演算法,最少資源群播問題,無線隨意網路,無線感測網路,動態最少資源群播問題, | zh_TW |
dc.subject.keyword | Particle Swarm Optimization,Minimum Energy Broadcast Problem,Wireless Ad-Hoc Network,Wireless Sensor Network,Dynamic MEB Problem, | en |
dc.relation.page | 75 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2012-08-13 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-101-1.pdf 目前未授權公開取用 | 6.38 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。