HANOI UNIVERSITY OF SCIENCE AND TECHNOLOGY ———————— MASTER’S GRADUATION THESIS Evolutionary algorithms to minimize the number of energy depleted sensors in wireless rechargeable sensor networks NGO MINH HAI hai.vn Thesis advisor: Dr. Nguyen Phi Le Signature of advisor Department: Department of Software engineering Institute: School of Information and Communication Technology Hanoi, 2021 HANOI UNIVERSITY OF SCIENCE AND TECHNOLOGY ———————— MASTER’S GRADUATION THESIS Evolutionary algorithms to minimize the number of energy depleted sensors in wireless rechargeable sensor networks NGO MINH HAI hai.vn Thesis advisor: Dr. Nguyen Phi Le Signature of advisor Department: Department of Software engineering Institute: School of Information and Communication Technology Hanoi, 2021 CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM Đôc lập – Tự do – Hạnh phúc ———————— BẢN XÁC NHẬN CHỈNH SỬA LUẬN VĂN THẠC SĨ Họ và tên tác giả luận văn: Ngô Minh Hải Đề tài luận văn (Tiếng Việt): Áp dụng giải thuật tiến hóa giải bài toán tối thiểu số lượng cảm biến cạn kiệt năng lượng trong mạng cảm biến sạc không dây Đề tài luận văn (Tiếng Anh): Evolutionary algorithms to minimize the number of energy depleted sensors in wireless rechargeable sensor networks Chuyên ngành: Khoa học dữ liệu và trí tuệ nhân tạo Mã số HV: 20202661M Tác giả, Người hướng dẫn khoa học và Hội đồng chấm luận văn xác nhận tác giả đã sửa chữa, bổ sung luận văn theo biên bản họp Hội đồng ngày 24/12/2021 vơi các nội dung sau: • Sửa tiêu đề phần 2.2 từ ”Problem formulation” thành ”Problem description” (trang 18). • Giải thích rõ hơn về cách tính tham số ti (trang 19).
• Vẽ lại hình để các kí hiệu hiển thị rõ ràng hơn (trang 39 - 42). • Sửa một số lỗi chính tả (trang 20). • Hiệu chỉnh lại cách mô hình hóa bài toán (trang 18-19). • Thêm hình vẽ nhằm mô tả rõ hơn các ký hiệu trong luận văn (trang 23).
• Thêm một số hướng nghiên cứu tương lai vào phần Kết luận (trang 43). • Sửa Chương 5: Kết luận thành một phần không đánh số chương (trang 43). Hanoi, ngày tháng năm 2021 Giáo viên hướng dẫn Tác giả luận văn CHỦ TỊCH HỘI ĐỒNG REQUIREMENTS OF THE THESIS 1. Student’s information: Name: Ngo Minh Hai Class: Data Science (Elitech) Affiliation: Hanoi University of Science and Technology Phone: 0353 852 045 Email: hai.
Declarations/Disclosures: I herewith formally declare that I — Ngo Minh Hai — have performed the work and presentation in this thesis independently under supervisions of Dr. Nguyen Phi Le, Assoc. Huynh Thi Thanh Binh and Mrs. Tran Thi Huong.
All of the results are genuine and are not copied from any other sources. Every reference materials are clearly listed in the bibliography. I will accept full responsibility for even one copy that violates school regulations. Hanoi, date month year 2021 Author Ngo Minh Hai 4.
Attestation of thesis advisor:. Hanoi, date month year 2021 Thesis Advisor Dr. Nguyen Phi Le ABSTRACT Wireless Sensor Networks (WSNs) are one of the most core technologies of the Internet of Things (IoTs). They have a wide range of applications and have attracted lots of atten- tions from researchers.
However, a traditional WSN remains as an energy-constrained network because of the limited energy of each sensor node. As a result, prolonging net- work lifetime has become an urgent challenge that directly affects the network perfor- mance. In recent years, the appearance of a new sensor network generation, called Wire- less Rechargeable Sensor Networks (WRSNs), has opened up a breakthrough in dealing with the energy issue. In WRSNs, we employ a Mobile Charger (MC) equipped with a charging device to charge the sensors that have rechargeable lithium battery inside wire- lessly.
Therefore, an effective charging scheme can enhance the whole network’s perfor- mance and minimize the energy depletion of sensor nodes. Although the performance of the charging scheme is decided by some essential factors including charging path and charging time of the MC, most of the existing charging schemes only consider the MC’s charging path factor with a fully charging method. Moreover, the previous works assume that the MC’s battery capacity is infinite or sufficient to charge all sensors in the network in one charging cycle. This hypothesis may lead to the energy depletion of the energy-hurry sensors and unnecessary visiting for energy-sufficient sensors.
The charging time has not been considered thoroughly in the previous works. This dissertation aims to minimize the energy depletion in wireless rechargeable sen- sor networks by optimizing both the MC’s charging path and charging time without the mentioned limitations. Since the charging schedule optimization problem is NP-hard, the dissertation will propose an approximate algorithm to solve the investigated prob- lem.Specifically, it proposes a novel network model in which the MC does not need to visit and charge every sensor node. Furthermore, it also proposes a hybrid genetic-algorithm- based charging scheme to achieve the problem’s aim.
The thesis conducts various simulations and experiments to evaluate the proposed charg- ing scheme performance. Empirical evaluations have shown that the proposed charging scheme outperforms the existing solutions by a substantial margin. CONTENTS List of Figures List of Tables Acronyms Introduction 2 1 Preliminaries 4 1.1 Overview of wireless rechargeable sensor networks .2 The charging scheme optimization problem .1 On-demand charging scheme .2 Periodic charging scheme. 13 2 The problem of minimizing the number of energy depleted sensors in wire- less rechargeable sensor networks 18 2.3 Mixed Integer Linear Programming Formulation.
19 3 Hybrid fuzzy logic and genetic-algorithm-based charging scheme 24 3.1 Fuzzy logic-based preprocessing system .2 Genetic algorithm for optimizing the charging path .3 Genetic algorithm for optimizing the charging time .1 Individual encoding and evaluation method .1 Experimental environment settings .1 Comparison between the proposed algorithm and an exact solver 38 4.2 Impact of the fuzzy logic preprocessing on charging decisions .3 Impact of the sensor density of the network .4 Impact of the data packet transmitting rate of sensors .5 Impact of the charging rate of the MC. 41 Conclusion and future works 43 Publication 44 Bibliography 45 LIST OF FIGURES 1.1 A wireless sensor network .3 Applications of WSNs .4 An illustration of WRSNs .5 A fuzzy logic system .6 Fuzzy logic temperature .7 Common fuzzy membership function plots .8 The genetic algorithm methodology .10 Genetic operator applications .1 An example of a mobile charger being on duty .1 Fuzzy membership function plots .2 The defuzzifcation process .3 An example of the decoding procedure .4 Different values of c impacts the distance between offspring and their parents in Simulated Binary Crossover (SBX) .5 An example of the Single-Point and AMXO Hybrid crossover (SPAH) crossover .1 Impact of the fuzzy logic preprocessing to the number of dead sensors .2 Impact of the density of sensor on different criteria .3 Impact of the data transmitting rate of sensors to the number of dead sensors .4 Impact of the charging rate of the MC to the number of dead sensors. 42 LIST OF TABLES 3.1 The parameters of input memberships .2 The parameters of output memberships .3 The parameters of input memberships .1 Parameters of energy model .2 Performance comparison between the exact solver MILP and HFLGA. 38 ACRONYMS ADC Analog-to-Digital Converter.
1 BS Base Station. 1, 4, 7, 8, 12, 18, 22, 24–27 COG Center of gravity. 1, 12, 28 FGA Full-charging Genetic Algorithm based charging scheme. 1, 39 FIS Fuzzy logic Inference System.
1, 25 FLCDS Fuzzy Logic-based Charging Decision Support. 1, 24, 25, 28 GA Genetic Algorithm. 1, 8, 9, 37 GACS Genetic Algorithm based Charging Scheme. 1, 37, 38, 40–42 HFLGA Hybird Fuzzy Logic and Genetic Algorithm based charging scheme.
1, 37–42 HPSOGA Hybird PSO and GA algorithm. 1, 37, 38, 40–42 INMA Invalid Node Minimized Algorithm. 1, 8, 37, 38, 40–42 IoT Internet of Thing. 1, 2 MC Mobile Charger.
1, 2, 6–9, 13, 17–20, 22, 24, 25, 30–43 MILP Mixed Integer Linear Programming. 1, 19–22, 37, 38 MNED The problem of Minimizing the Number of Energy Depleted sensors. 1, 2, 19– 22 PSO Particle Swarm Optimization. 1, 8, 37 PW Priority Weight.
1, 24–32 RGA Random-charging Genetic Algorithm based charging scheme. 1, 39 SAMER Starvation Avoidance Mobile Energy Replenishment scheme. 1, 8 SBX Simulated Binary Crossover. 1, 32–35 SPAH Single-Point and AMXO Hybrid crossover.
1, 35 SS Service Station. 1 WRSN Wireless Rechargeable Sensor Network. 1–3, 6, 7, 9, 17, 18, 37, 39, 43 WSN Wireless Sensor Network. 1–7 1 INTRODUCTION Wireless Sensor Networks (WSNs) are considered the core architecture in developing the Internet of Thing (IoT).
Applications of WSNs have been widely employed in various domains, including smart architecture, environmental monitoring, natural disaster relief, military target tracking, surveillance, etc. However, traditional WSNs remain as energy- constrained networks due to the limited battery capacity of sensor nodes. When the en- ergy of a sensor go down to its minimum battery level, it will become a dead sensor node can not monitor or transfer targets’ data, thus disrupting the network’s operation. As a result, the sensor nodes’ energy depletion avoidance has become an essential issue and has gained worldwide attention among the research community and network users.
Al- though there have been many intensive efforts, the sensor node’s energy problem remains a bottleneck phenomenon in WSNs. Wireless Rechargeable Sensor Networks (WRSNs) has emerged as a potential solution for the constrained energy problem in sensor networks in recent years. Unlike WSNs, the sensor nodes in WRSNs are equipped with a wireless energy receiver through wireless transfer waves. Furthermore, one or more mobile autonomous robots (namely Mobile Charger (MC)) are employed to charge sensor nodes periodically.
Therefore, the sensor’s lifetime is decided by charging schemes for MCs. Despite many efforts to tackle the charging scheme optimization problem, most of them still suffer from several limitations. Specifically, they are based on the assumption that the MC has sufficient or infinite energy to visit and charge all sensors within a charg- ing cycle. This constraint leads to prolonging the waiting charging time of energy-hurry sensors and unnecessary visiting of energy-sufficient one.
Furthermore, they do not try to simultaneously optimize the charging path and the charging time in the charging scheme. They extremely focus on optimizing the traveling cost of the MC and thus, sensors can be exhausted due to the increasing waiting time. Finally, none of the previous works actually consider the energy depletion avoidance of sensors while guaranteeing that the charging cost is minimized to be the ultimate objective of the charging scheme optimizing problem. This thesis investigates determining both the charging path and the charging time at each sensor to minimize the number of exhausted-energy sensors (dead sensor nodes) in WRSNs at to minimize the charging cost (i., traveling nergy of the MC) without the mentioned limitations.
This thesis simply named the investigated problem as The problem of Minimizing the Number of Energy Depleted sensors (MNED) in WRSNs. The main contributions in this thesis are as follows: • This work is one of the earliest attempts to formulate MNED as Mixed Integer Lin- ear Programming [1]. The thesis simultaneously optimize both the charging path of MC and charging time at each charged sensor. • The thesis propose a novel charging scheme based on fuzzy logic inference and a genetic algorithm to support a charging decision which sensors should be charged in each cycle and optimize both charging path simultaneously and charging time.
• The thesis finally evaluate the performance of the proposed algorithms through a range of experimental simulations. Simulation results demonstrate that the algo- rithm outperforms existing works in various evaluation criteria (i. the number of 2 energy depleted sensors and traveling cost). The rest of the thesis is constructed as follows: • Chapter 1 introduces the related knowledge of this study, including the overview of the WSN and the WRSN, the previous works of the charging scheme optimization problem and some optimization algorithms.