Tài liệu Á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

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 [email protected] Thesis advisor: Dr. Nguyen Phi Le Department: Institute: Department of Software engineering School of Information and Communication Technology Hanoi, 2021 Signature of advisor 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 [email protected] Thesis advisor: Dr. Nguyen Phi Le Department: Institute: Department of Software engineering School of Information and Communication Technology Hanoi, 2021 Signature of advisor 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 Giáo viên hướng dẫn tháng Tác giả luận văn CHỦ TỊCH HỘI ĐỒNG năm 2021 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: [email protected] Duration: 01/10/2020 - 31/09/2021 2. Thesis statement: 3. 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. Prof. 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 Author year 2021 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 attentions 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 network lifetime has become an urgent challenge that directly affects the network performance. In recent years, the appearance of a new sensor network generation, called Wireless 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 wirelessly. Therefore, an effective charging scheme can enhance the whole network’s performance 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 sensor 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 problem.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-algorithmbased charging scheme to achieve the problem’s aim. The thesis conducts various simulations and experiments to evaluate the proposed charging 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 . . . . . . . . . . . 4 1.2 The charging scheme optimization problem . . . . . . . . . . . . . . . 7 1.3 Related works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.3.1 On-demand charging scheme . . . . . . . . . . . . . . . . . . 7 1.3.2 Periodic charging scheme . . . . . . . . . . . . . . . . . . . . 8 1.4 Optimization Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.4.1 Fuzzy Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.4.2 Genetic algorithms . . . . . . . . . . . . . . . . . . . . . . . 13 2 The problem of minimizing the number of energy depleted sensors in wireless rechargeable sensor networks 18 2.1 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2 Problem definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.3 Mixed Integer Linear Programming Formulation . . . . . . . . . . . . 19 3 Hybrid fuzzy logic and genetic-algorithm-based charging scheme 3.1 24 Fuzzy logic-based preprocessing system . . . . . . . . . . . . . . . . . 24 3.2 Genetic algorithm for optimizing the charging path . . . . . . . . . . . 30 3.2.1 Individual encoding . . . . . . . . . . . . . . . . . . . . . . . 30 3.2.2 Evaluation method . . . . . . . . . . . . . . . . . . . . . . . 32 3.2.3 Genetic operators . . . . . . . . . . . . . . . . . . . . . . . . 32 3.3 Genetic algorithm for optimizing the charging time . . . . . . . . . . . 34 3.3.1 Individual encoding and evaluation method . . . . . . . . . . 34 3.3.2 Genetic operators . . . . . . . . . . . . . . . . . . . . . . . . 35 3.3.3 Individual Adjustment . . . . . . . . . . . . . . . . . . . . . . 36 4 Performance evaluations 37 4.1 Experimental environment settings . . . . . . . . . . . . . . . . . . . 37 4.2 Experimental evaluations . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.2.1 Comparison between the proposed algorithm and an exact solver 38 4.2.2 Impact of the fuzzy logic preprocessing on charging decisions . 39 4.2.3 Impact of the sensor density of the network . . . . . . . . . . . 39 4.2.4 Impact of the data packet transmitting rate of sensors . . . . . . 40 4.2.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 . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 A sensor structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 Applications of WSNs . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4 An illustration of WRSNs . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.5 A fuzzy logic system . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.6 Fuzzy logic temperature . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.7 Common fuzzy membership function plots . . . . . . . . . . . . . . . 12 1.8 The genetic algorithm methodology . . . . . . . . . . . . . . . . . . . 15 1.9 Natural selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.10 Genetic operator applications . . . . . . . . . . . . . . . . . . . . . . 17 2.1 An example of a mobile charger being on duty . . . . . . . . . . . . . . 23 3.1 Fuzzy membership function plots . . . . . . . . . . . . . . . . . . . . 27 3.2 The defuzzifcation process . . . . . . . . . . . . . . . . . . . . . . . . 30 3.3 An example of the decoding procedure . . . . . . . . . . . . . . . . . . 31 3.4 Different values of c impacts the distance between offspring and their parents in Simulated Binary Crossover (SBX) . . . . . . . . . . . . . . 34 3.5 An example of the Single-Point and AMXO Hybrid crossover (SPAH) crossover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.1 Impact of the fuzzy logic preprocessing to the number of dead sensors . 39 4.2 Impact of the density of sensor on different criteria . . . . . . . . . . . 40 4.3 Impact of the data transmitting rate of sensors to the number of dead sensors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.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 . . . . . . . . . . . . . . . . . . 26 3.2 The parameters of output memberships . . . . . . . . . . . . . . . . . 26 3.3 The parameters of input memberships . . . . . . . . . . . . . . . . . . 27 4.1 Parameters of energy model . . . . . . . . . . . . . . . . . . . . . . . 38 4.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 energyconstrained networks due to the limited battery capacity of sensor nodes. When the energy 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. Although 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 charging 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.e., 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 Linear 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 algorithm outperforms existing works in various evaluation criteria (i.e. 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. • Chapter 2 describes the network model and mathematical model, and mixed-integer linear programming for the The problem of minimizing the number of energy depleted sensors in wireless rechargeable sensor networks. • Chapter 3 presents the proposed algorithms, which are comprised of the fuzzy logic algorithm and genetic approach. • Chapter 4 evaluates and comparesthe performance of our proposed algorithms with existing research. • The last part concludes the thesis and discusses about future works. 3 CHAPTER 1. PRELIMINARIES 1.1 Overview of wireless rechargeable sensor networks A WSN refers to a network comprising multiple spatially dispersed and specialized sensors with a communications infrastructure for monitoring and recording the physical conditions in various environments. In WSN, the sensors will cooperatively forward the sensing data to the Base Station (BS), also known as a sink, where the data will be collected, analyzed, and/or several actions are taken accordingly. Fig. 1.1 illustrates a typical WSN communicating with end-users. End-users Internet Base station Base station Sensor
elds Sensor nodes Figure 1.1: A wireless sensor network Sensors play an important role in a sensor network. To monitor the physical environments and communicate with others efficiently, sensors have a lot of requirements. They not only need to record surroundings accurately and precisely, be capable of computing, analyzing, and storing the sensing data, but also have to be small in space, low in cost, and effective in power consumption. Sensors commonly comprise four fundamental units: a sensing unit, which monitors environments and converts the analog signal into a digital signal; a processing unit, which processes the digital data and stores in memory; a transceiver unit, which provides communication capability; and a power unit, which supplies energy to the sensor [2]. In addition, some sensors also have a navigation system to determine positions of themselves, 4 other sensors and sensing targets, a mobilizer to add the mobile capability, etc. A sensor structure is shown in Fig. 1.2. Navigaton system Mobilizer Processor Sensor ADC Storage Transceiver Power unit Figure 1.2: A sensor structure A WSN has many advantages in practical situations. Because of using radio signals instead of wires to connect sensors, A WSN can be deployed, self-organized, and scaled effortlessly in unreachable areas. In addition, since the cost of deploying a WSN is also pretty low, a WSN is very flexible to many applications. WSNs have various applications in many fields (Fig. 1.3). The first time they were used was in a sound surveillance system developed by the United States military in the 50s to detect and track Soviet submarines. Today, WSNs are presently applied in many civilian applications, such as environmental monitoring, health monitoring, smart agriculture, etc. Particularly, a WSN can be deployed in a forest to alert authorities to the possibility of a forest fire. Moreover, WSN can track the location of the fire before it dramatically spread and can not be stopped. Health monitoring is also a very potential application of WSNs. For example, scientists have developed a sugar-level monitoring system based on WSN. The system can record the fluctuation rate of glucose in diabetes patients’ blood and warn them in time. Despite many advantages, a WSN still has some limitations. Because a WSN needs to keep its low-cost characteristic, it has to cut out some features. Specifically, a sensor in WSNs has a low-capacity battery, which is commonly non-rechargeable. If WSNs are deployed in inaccessible terrains, it is impossible to get battery replacements. When a sensor’s battery runs out of energy, it can not record, transfer data, or communicate, thus disrupting the network’s operation. Moreover, a sensor in WSNs is small, resulting in restricted computing and storing capability. Although there are a lot of issues about communicating range, signal attenuation, security, etc. in WSNs, this thesis concerns the energy challenge in WSNs as one of the most essential issue. As a result, the sensor nodes’ energy depletion avoidance has gained a lot of worldwide attention among the research community and network users. There has been many intensive efforts in reducing the energy consumption of WSNs. Particularly, they have tried to optimize radio signals using cognitive radio standardization [3], reduce data rate using data aggregation technique [4], save more energy using sleep/wake-up schemes [5], or select efficient energy routing protocols [6]. However, 5 Figure 1.3: Applications of WSNs none of them thoroughly solved the sensor node’s energy problem in WSNs. If there is no outside source supplying energy to sensors, the battery will eventually be exhausted. Another approach which can resolve the sensor’s energy depletion problem is gathering energy from the environment. Each sensor has an energy harvester to convert power from external sources such as solar energy, thermal energy, wind energy, kinetic energy, etc. into electrical power. Sensors can use the converted power to recharge theirs battery and prolong the lifetime of the network. Nevertheless, this technique depends too much on an ambient energy source which is unstable and uncontrollable. In recent years, on account of the breakthrough of wireless energy transfer and rechargeable battery technology, one can use a recharging device to replenish the battery of sensors in WSNs. As a result, a new sensor network generation, called WRSNs, was born (Fig. 1.4). WRSNs have the advantage over traditional WSNs because the sensor nodes in WRSNs are equipped with a wireless energy receiver through wireless transfer radio waves based on electromagnetic radiation and magnetic resonant coupling technology. WRSNs introduce one or more chargers to recharge sensor nodes periodically. Therefore, the network’s lifetime is ideally extended for perpetual operations. WRSNs provide a more flexible, adjustable, and dependable energy replenishment than traditional WSNs, thus WRSNs easy to maintain long-term and reliable operations. However, a new network generation appearance would raise new challenges that have never been countered before. Specifically, WRSNs require a charger employment strategy. One can classify chargers into two categories: charging terminals and MCs. A charging terminal has a fixed location in the network area and can recharge more than one sensor. Because the network scale is typically large, the network would need many charging terminals. The network wants to determine the minimum number of charging terminals required to replenish all sensors, which is similar to the coverage problem in WSNs. Besides, a charging terminal do not have an eternal energy source, which means it still need to recharge after a period of time. Thus, the charging terminal is not a reliable device for maintaining long-term operations. Using MCs to recharge sensors is a better idea. A MC can travel through the network, thus it can cover lots of network area and will return to the 6 Sensor with charging requests Sensor Base Station Mobile Charger Service Station Figure 1.4: An illustration of WRSNs BS to recharge its own battery if it do not have enough power to move and supply energy to sensors. Therefore, the only problem is that we need to determine the charging scheme of the MC. 1.2 The charging scheme optimization problem The charging scheme of a MC in a WRSN consists of two elements: the charging path and the charging time of the MC. Because the wireless charging technology requires a proper distance to enable charging sequence, the MC has to visit some predetermined locations to charge sensors in the network. Moreover, at each location, the MC need time to charge sensors to an substantial amount of energy in order to prolong the network’s lifetime. The charging path is the visiting order of the MC in the WRSN and the charging time is a sequence of times that the MC has to spend at each location. Therefore, WRSNs desires to determine the charging path and charging time at each sensor to prolong the lifetime of the network. This problem can be called as the charging scheme optimization problem in WRSNs. The scientific community is extremely excited and focuses more on solving this type of problem instead of problems with traditional WSNs. 1.3 Related works The charging scheme optimization problem in WRSNs would be classified into two groups: periodic charging scheme optimization and on-demand charging scheme optimization. 1.3.1 On-demand charging scheme In the on-demand charging scheme, or the online charging scheme, if a sensor has energy reached its threshold, a charging request will be sent to the BS. When the request pool of the BS has enough requests, the MC will start traveling to charge. Because BS can receive requests in real time, the MC may change its route to adapt to the new charging order. Thus, this charging model is more flexible than the periodic charging scheme. But in contrast, this approach is mainly concentrate on optimizing the charging path of the MC. So that, if the distance between requesting sensors is extremely far or the network is large, the 7 traveling time of the MC will rapidly increase and will let sensors exhausted. Secondly, the charging request threshold strongly impacts on the performance of the on-demand charging scheme and determining a proper threshold is a really hard problem. Kaswan et al. [7] investigated a linear programming formulation to minimize the networks’ charging latency. They proposed a charging strategy based on a gravitation search algorithm to determine the charging scheme of the MC. Several works studied the minimizing invalid sensor nodes problem with limited charging energy. Particularly, Feng et al. [8] proposed a Starvation Avoidance Mobile Energy Replenishment scheme (SAMER) which can avoid energy starvation through calculating and considering the maximum tolerable latency of each charging requirement. Furthermore, Zhu et al. [9] proposed a online algorithm named Invalid Node Minimized Algorithm (INMA) in order to optimizing the charging queue of the BS. The algorithm aimed to minimize the number of invalid sensor nodes in the queue. 1.3.2 Periodic charging scheme In the periodic charging scheme, the MC follows periodically a charging schedule to charge sensors. The MC need to analyze the network information and determine the optimal periodic schedule before traveling to charge. Hence, The MC will not get any information when it serves the network. Because of that, the periodic charging scheme can be called the offline charging scheme. There were many research works select this approach. Shi et al. [10][11] proposed a periodic charging scheme to maximize the vacation time of the MC at the depot over each charging cycle. Furthermore, the MC has to travel across all sensors precisely once in a charging cycle and renews sensors’ battery to be fully charged. They found that the solution to the problem is equivalently the shortest Hamiltonian path. These studies have some issues such as: assuming energy capacity of the MC is infinite, while in real life it is finite; no ensuring that waiting-for-charging sensors would not be exhausted before the MC can reach them; assuming the energy-consuming rate of sensors is constantly the same. Lyu et al. [12] also investigated the problem of maximizing the vacation time of the MC. This study tried to limit the traveling energy of the MC and examine the network with imbalanced-energy-consumption-rate sensor nodes. A hybrid algorithm between Particle Swarm Optimization (PSO) and Genetic Algorithm (GA) is proposed to determine an optimal charging path to deal with the problem. Although this model had considered some unrealistic features in previous works, it still had some limitations. Firstly, the charging energy capacity of the MC is still infinite. Secondly, the charging time at each sensor is constant at every charging cycle. In fact, at each charging cycle, the energy amount of each sensor can not be the same which causes many sensors would eventually run out of energy. Fu et al. [13] studied minimizing the charging latency of the network. Besides, they took into account minimizing the total traveling distance of the MC. However, a disadvantage of these works is that there is no consideration of minimizing the charging time of the MC. The battery capacity of the MC is limited, thus it is impractical to fully charge every sensor in a charging cycle. Another field that attracts much attention from researchers is the point-to-multipoint charging scheme. In point-to-multipoint charging scheme, a MC can charge more than one sensor at a time. In this model, instead of visiting every sensor, the MC would visit some charging locations to charge multiple of sensors. Hence, optimizing the charging 8 locations and the number of charging locations are parts of the objectives of this problem [14]. Lu et al. [15] and Fu et al. [16] studied how to minimize the number of charging locations while ensuring all sensor nodes are charged. They found that the shortest Hamiltonian cycle has been adopted as a charging path for the MC travels across al charging locations. Most of the research mentioned above focused on optimizing the charging path of the MC, while the charging time of the MC was ignored [1]. By contrast, Huong et al. [17] optimize both the charging path and charging time to minimize the number of exhausted sensors in WRSN. They proposed a two phase algorithm based on GA to deal with the concerned problem. Particularly, phase one determined an optimal charging path of the MC, prioritizing charging as soon as possible for sensors on the edge of exhaustion. Phase two calculated the charging time of the MC according to the charging path had found in the phase one. Although this study has tried to reduce limitations from previous works, the MC must visit all sensors in the entire network at least a charging cycle. In fact, there are some sensors can stay functional for a long time without charging. Therefore, the MC can spent more time charging other sensors in the first few charging cycles. Inspire of many attempts to tackle the charging scheme optimization problem, most of them still suffer from several common shortcomings [1]. Firstly, previous works in periodic charging scheme assumed that a MC has sufficient (or infinite) battery capacity to all charging locations in the entire network at least a charging cycle.This condition, however, is unrealistic in large-scale sensor network scenarios. Furthermore, there’s no need to charge all sensors in a charging cycle because there is several sensors can survive without charging for a long time. Secondly, most works lack investigation of optimizing two critical factors simultaneously: the charging path and the charging time in a charging scheme design. They mostly focus on optimizing traveling cost and employing a fullycharged strategy for all sensors. Without considering the charging time, it may prolong the waiting time of uncharged sensors, so that they can rapidly run out of energy. Lastly, the charging scheme’s ultimate objective is energy depletion avoidance of sensors while guaranteeing that the charging cost is minimized. Nevertheless, none of previous works tackles the charging scheme optimization comprehensively with the above objective. 1.4 Optimization Algorithms 1.4.1 Fuzzy Logic Nowadays, decision-making is a daily activity of our lives. However, it is hard to decide if a statement is certainly true or false in some cases. In such situations, fuzzy logic can be used as a flexible method for reasoning, given the uncertainty. Basic concept A classic logical statement is a declarative sentence that delivers factual information. If the information is correct, the statement is true; if the information is erroneous, the statement is false. For example, the statement “Hanoi is the capital of Vietnam.” is a true statement and the statement “The sun is cold.” is a false statement. However, sometimes, true or false values are not enough. For instance, to determine if one has diabetes, doctors have to perform several blood tests. Doctors will evaluate the blood sugar level and make a diagnosis for the patient. According to the blood sugar level, the patient would be considered as normal, prediabetes, or diabetes. Prediabetes is actually a serious health condition where blood sugar level is higher than normal, but 9 not high enough yet to be diagnosed as diabetes. In logical statement, there is no value between “true” and “false”, or between “high” and “low”. If the statement “I have diabetes” is considered as a logical statement, it will just be true or false. Thus, doctors may never refer to prediabetes, and patients can not get a timely warning for their conditions. In the 60s of twenty century, Lotfi et al. [18] has used a novel term “fuzzy logic” to declare a form of logic processing that has more than two true values. Fuzzy logic is influenced by the observation that some statements contains imprecise or non-numerical information. The term “fuzzy” also had the meaning of representing vagueness and imprecise information. Therefore, fuzzy logic are capable of representing and manipulating ambiguous and uncertain information and has been applied to many fields. Fuzzy logic is using certain input values, such as multi-numeric values or linguistic variables, to produce a certain output following the fuzzy approach. The fuzzy approach will specify if a object possesses a property fully or only partly, though the given property is vague. For instance, “very strong engine” is a phrase that based on the fuzzy approach. There is a hidden degrees of intensity (“very”) of the property (“strong”) in concern. Fuzzy logic system A fuzzy logic system mainly consists of four parts: a fuzzification module, a fuzzy inference module, a rule base, and a defuzzification module. A fuzzy logic architecture is illustrated in Fig. 1.5. Fuzzy logic system Rulebase Crisp input Fuzzi
cation module Fuzzy inference module Defuzzi
cation Module Crisp output Figure 1.5: A fuzzy logic system Each component plays an essential role in the fuzzy logic system. Firstly, the fuzzification module (or fuzzifier) can assign raw input values to fuzzy sets with some fuzzy membership values using fuzzy membership functions. A membership value ranges from 0 to 1. If it equals 0 then it is not a part of the given fuzzy set. In contrast, if it equals 1 then it completely belongs to the given set. Any value between 0 and 1 indicates the degree of uncertainty that it belongs within the given set. In some applications, those fuzzy sets are depicted by words, thus one can reason in a linguistically natural manner. Fig. 1.6 is an example of a fuzzy membership function. The crisp input values are temperatures of the atmosphere at the earth’s surface in Celsius. The blue line indicates the membership values mapping with the low temperatures, the orange one is the member10