# Efficient Energy Utilization with Device Placement and Scheduling in the Internet of Things

Authors: Yanli Zhu; Xiaoping Yang; Yi Hong; Youfang Leng; Chuanwen Luo
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

The low-power wide-area network (LPWAN) technologies, such as LoRa, Sigfox, and NB-IoT, bring new renovation to the wireless communication between end devices in the Internet of things (IoT), which can provide larger coverage and support a large number of IoT devices to connect to the Internet with few gateways. Based on these technologies, we can directly deploy IoT devices on the candidate locations to cover targets or the detection area without considering multihop data transmission to the base station like the traditional wireless sensor networks. In this paper, we investigate the problems of the minimum energy consumption of IoT devices for target coverage through placement and scheduling (MTPS) and minimum energy consumption of IoT devices for area coverage through placement and scheduling (MAPS). In the problems, we consider both the placement and scheduling of IoT devices to monitor all targets (or the whole detection area) such that all targets (or the whole area) are (or is) continuously observed for a certain period of time. The objectives of the problems are to minimize the total energy consumption of the IoT devices. We first, respectively, propose the mathematical models for the MTPS and MAPS problems and prove that they are NP-hard. Then, we study two subproblems of the MTPS problem, minimum location coverage (MLC), and minimum energy consumption scheduling deployment (MESD) and propose an approximation algorithm for each of them. Based on these two subproblems, we propose an approximation algorithm for the MTPS problem. After that, we investigate the minimum location area coverage (MLAC) problem and propose an algorithm for it. Based on the MLAC and MESD problems, we propose an approximation algorithm to solve the MAPS problem. Finally, extensive simulation results are given to further verify the performance of the proposed algorithms.


---

## Body

## 1. Introduction

The Internet of things (IoT) is a flourishing paradigm in the scenario of modern wireless telecommunications, which has been provided a wide diversity applications for all walks of life in modern time, such as home automation, transportation, industry, agriculture, mobile device applications [1], and smart systems [2]. IoT applications are required a growing number of technologies to offer low-power operation and low-cost and low-complexity end devices that will be able to communicate wirelessly over long distances. With the development of the Low Power Wide Area Network (LPWAN) technologies, such as SigFox, NB-IoT and LoRa, the low power long-range wide-area communication has become a reality [3]. Since the long range communication of the LPWAN technologies is gradually used in the Internet of things, the IoT devices can only communicate with LPWAN gateways and not directly with each other. Taking the LoRa example, a single gateway can support as many as 105 IoT devices and three gateways are enough to cover all devices in the urban area within an approximate 15 km radius [4]. The architecture of the LPWAN-based Internet of things is shown in Figure 1 [5], in which IoT devices are deployed in the monitoring area to observe targets or the whole monitoring area; the installation of few gateways over the territory allows to gather data from IoT devices that are placed at different miles from the gateways. Then, the received data by the gateways are transmitted to the users through the Internet or satellite for further computational analysis to determine the appropriate response mechanism.Figure 1
The architecture of the LPWAN-based Internet of things.Therefore, we can directly deploy IoT devices to monitor all targets (or the whole monitoring area) in any region with the LPWAN-based network without considering other data transmission methods such as virtual backbone networks [6, 7] and mobile data collectors [8, 9]. Since many IoT devices are battery-powered sensors, for example, in wireless sensor networks (WSNs) and ad hoc networks (ANs), the power usage profile should be carefully designed in order to extend the battery lifetime. How to prolong the network lifetime is a classic problem in WSNs, which is called the coverage problem [10]. Given the m targets (or the entire monitoring area) and n IoT devices in the monitoring area, the coverage problem is to schedule the activity of the IoT devices such that all targets (or the whole monitoring area) are (or is) continuously observed and the network lifetime is maximized. Research on the coverage problem benefits a lot of applications, such as environment monitoring, battlefield surveillance, indoor guarding, smart space, industrial diagnostics, and military facility [11]. Recently, many researchers proposed various problems and corresponding algorithms for the coverage problem. In [12], Cardei et al. studied the target coverage problem with the objective of maximizing the network lifetime of a power constrained WSN deployed for detecting of a set of targets with known locations, in which they did not consider the placement of sensors. In [13], Akhlaghinia et al. studied the heterogeneous point coverage problem in sensor placement to cover a large number of target points with various coverage requirements using a minimum number of heterogeneous sensors. In the problem, they only investigated the placement of sensors without considering network lifetime. In [14], Mini et al. considered both the deployment locations and scheduling of the given IoT devices to maximize the network lifetime with the required coverage level. However, they deployed all available IoT devices to cover targets randomly without considering their candidate sites. In [15], Hanh et al. investigated the problem of maximizing the area coverage in heterogeneous WSNs. The goal of the problem is to find an optimal placement scheme for the given set of sensors so that the coverage area is maximized. In the problem, they only consider the placement of sensors without considering their candidate sites.In the above literature, they only considered one of the deployment and scheduling of IoT devices or ignored the factor that candidate sites can be placed by IoT devices which has to be considered in some applications, such as a smart city. Actually, to minimize the total energy consumption of IoT devices, we not only need to consider the deployment of IoT devices but also their scheduling. Meanwhile, due to the emergence of wireless charging technologies and natural energy charging methods (e.g., solar charging) for the IoT devices, the current applications of IoTs have shifted from maximizing the network lifetime to working for a certain period of time. In this paper, we study the problems of the minimum energy consumption of IoT devices for target coverage through placement and scheduling (MTPS) and minimum energy consumption of IoT devices for area coverage through placement and scheduling (MAPS), where we consider both the placement and scheduling of IoT devices to monitor all targets or the entire monitoring area in a region such that all targets or the whole area are or is continuously observed for a certain period of time and the total energy consumption of all available IoT devices is minimized. The contributions of this paper are shown as follows:(1)
We propose two new practical models of minimizing the total energy consumption of all IoT devices by placing and scheduling them for continuously observing all targets or the entire detection area for a certain period of time. Then, we define the problems as the minimum energy consumption of IoT devices for target coverage through placement and scheduling (MTPS) and minimum energy consumption of IoT devices for area coverage through placement and scheduling (MAPS) and prove that they are NP-hard(2)
To solve the MTPS problem, we introduce two other problems, minimum location coverage (MLC) and minimum energy consumption scheduling deployment (MESD). Then, we propose an approximation algorithm for each of them. Afterwards, an approximation algorithm for the MTPS problem is proposed on the basis of the solutions for the MLC and MESD problems(3)
To solve MAPS problem, we introduce another problem, minimum location area coverage (MLAC). Then, we propose an approximation algorithm to solve the problem. Based on the problems MLAC and MESD, we propose an approximation algorithm to solve the MAPS problem(4)
We illustrate the effectiveness of the proposed algorithms by theoretical analysis and simulationsThe remainder of this paper is organized as follows. We give the related works in Section2. Section 3 introduces some models and definitions for the problems MTPS and MAPS. In Section 5, we propose an approximation algorithm to solve the MTPS problem. In Section 6, we propose an approximation algorithm to solve the MAPS problem. Simulations are shown in Section 7. Section 8 concludes this paper.


## 2. Related Works

In this section, we briefly review the major problems and methods related to the investigated problem in IoTs. As we all know, WSN is a special kind of IoTs. If there is no special explanation, the sensors in WSNs mentioned below represent IoT devices. According to the investigated problem, the related works can be categorized into three categories: IoT device placement problem, target coverage problem, and area coverage problem.


### 2.1. IoT Device Placement Problem

The IoT device placement problem aims at finding the least number of IoT devices and their locations within all known potential sensing locations for meeting requirements, such as [16–21].In [16], Altinel et al. investigated the minimum cost point coverage problem with varying sensing quality and price and formulated a binary integer linear programming model for effective sensor placement on a grid-structured area. In [17], Wang introduced the sensor placement optimization problem, where the locations of targets to be covered are known and the candidate locations to place sensors are limited. The objective of the problem is to minimize the number of sensors to cover all targets, and the problem can be solved by the greedy algorithm for solving the set covering problem as shown in [22]. In [18], Gravalos et al. investigated the gateway placement problem for IoTs, which aims at finding the minimum number of gateways along with suitable IoT devices to optimize the overall installation cost without compromising the related QoS requirements. In [19], Jiang et al. proposed a group-greedy method to solve the sensor placement in linear inverse problems, which can find suboptimal solutions with near optimality guarantee using less computational cost compared with convex relaxation methods. In [20], Hasan and Al-Rizzo investigated the sensor deployment to improve the connectivity in IoT by presenting the bioinspired metaheuristics canonical particle multiswarm optimization algorithm. In [21], Jiang et al. studied the optimal sensor placement problem for an IoT-based power grid monitoring system. Then, they proposed a modified binary particle swarm optimization algorithm to determine the optimal number and location of sensors and estimate the ratio of conductor temperature alarms that can be covered by the proposed sensor placement.


### 2.2. Target Coverage Problem

In general, IoT devices are battery-powered sensors and there are often a lot of redundant sensors randomly placed in a region to cover a certain group of targets. How to schedule deployed sensors to maximize the network lifetime is an important problem in IoTs, which is called the maximum lifetime coverage problem (MLCP) and was proved NP-hard [12]. Currently, many researches devoted themselves to investigating the various problems of the MLCP problem, such as [23–26].In [23], Berman et al. defined the MLCP problem as a sensor network life problem (SNLP) and proposed an approximation algorithm with a performance ratio of 1+lnn to solve the problem based on the minimum weigh sensor coverage problem (MWSCP) which aims at finding the minimum total weight of sensors to cover a certain set of targets, where n is the number of deployed sensors. In [24], Ding et al. first improved the algorithm for the MWSCP problem to 4+ε, where ε>0. Then, they proposed an approximation algorithm with an approximate ratio of 4+ζ in the light of the MWSCP problem, where ζ>0. In [25], Lu et al. investigated the maximum lifetime coverage scheduling (MLCS) problem to address the scheduling problem for both target coverage and data collection in WSNs for maximizing the network lifetime. Then, they proposed an approximation algorithm with a constant factor for the problem. In [26], Shi et al. defined a new coverage problem in battery-free WSN, which is not only to maximize coverage quality but also to prolong network lifetime. Then, they proposed two centralized approximate algorithms and a distributed algorithm for solving the problem.


### 2.3. Area Coverage Problem

In [27], Xing et al. divided the detection area into grids and guaranteed the coverage of vertices of each grid to approximate the area coverage. However, the proposed approach as an approximation solution can not actually ensure the coverage of the whole area. In [28], Yu et al. studied the k-coverage problem, where a minimum subset of sensors among the deployed ones is selected such that each point in the detection area is covered by at least k sensors. In [29], Qin and Chen investigated the area coverage problem to maximize the coverage lifetime of wireless sensor networks for monitoring the area of interest. They proposed the area coverage algorithm based on differential evolution, which considered the balanced cost and minimal energy for sensors.


## 2.1. IoT Device Placement Problem

The IoT device placement problem aims at finding the least number of IoT devices and their locations within all known potential sensing locations for meeting requirements, such as [16–21].In [16], Altinel et al. investigated the minimum cost point coverage problem with varying sensing quality and price and formulated a binary integer linear programming model for effective sensor placement on a grid-structured area. In [17], Wang introduced the sensor placement optimization problem, where the locations of targets to be covered are known and the candidate locations to place sensors are limited. The objective of the problem is to minimize the number of sensors to cover all targets, and the problem can be solved by the greedy algorithm for solving the set covering problem as shown in [22]. In [18], Gravalos et al. investigated the gateway placement problem for IoTs, which aims at finding the minimum number of gateways along with suitable IoT devices to optimize the overall installation cost without compromising the related QoS requirements. In [19], Jiang et al. proposed a group-greedy method to solve the sensor placement in linear inverse problems, which can find suboptimal solutions with near optimality guarantee using less computational cost compared with convex relaxation methods. In [20], Hasan and Al-Rizzo investigated the sensor deployment to improve the connectivity in IoT by presenting the bioinspired metaheuristics canonical particle multiswarm optimization algorithm. In [21], Jiang et al. studied the optimal sensor placement problem for an IoT-based power grid monitoring system. Then, they proposed a modified binary particle swarm optimization algorithm to determine the optimal number and location of sensors and estimate the ratio of conductor temperature alarms that can be covered by the proposed sensor placement.


## 2.2. Target Coverage Problem

In general, IoT devices are battery-powered sensors and there are often a lot of redundant sensors randomly placed in a region to cover a certain group of targets. How to schedule deployed sensors to maximize the network lifetime is an important problem in IoTs, which is called the maximum lifetime coverage problem (MLCP) and was proved NP-hard [12]. Currently, many researches devoted themselves to investigating the various problems of the MLCP problem, such as [23–26].In [23], Berman et al. defined the MLCP problem as a sensor network life problem (SNLP) and proposed an approximation algorithm with a performance ratio of 1+lnn to solve the problem based on the minimum weigh sensor coverage problem (MWSCP) which aims at finding the minimum total weight of sensors to cover a certain set of targets, where n is the number of deployed sensors. In [24], Ding et al. first improved the algorithm for the MWSCP problem to 4+ε, where ε>0. Then, they proposed an approximation algorithm with an approximate ratio of 4+ζ in the light of the MWSCP problem, where ζ>0. In [25], Lu et al. investigated the maximum lifetime coverage scheduling (MLCS) problem to address the scheduling problem for both target coverage and data collection in WSNs for maximizing the network lifetime. Then, they proposed an approximation algorithm with a constant factor for the problem. In [26], Shi et al. defined a new coverage problem in battery-free WSN, which is not only to maximize coverage quality but also to prolong network lifetime. Then, they proposed two centralized approximate algorithms and a distributed algorithm for solving the problem.


## 2.3. Area Coverage Problem

In [27], Xing et al. divided the detection area into grids and guaranteed the coverage of vertices of each grid to approximate the area coverage. However, the proposed approach as an approximation solution can not actually ensure the coverage of the whole area. In [28], Yu et al. studied the k-coverage problem, where a minimum subset of sensors among the deployed ones is selected such that each point in the detection area is covered by at least k sensors. In [29], Qin and Chen investigated the area coverage problem to maximize the coverage lifetime of wireless sensor networks for monitoring the area of interest. They proposed the area coverage algorithm based on differential evolution, which considered the balanced cost and minimal energy for sensors.


## 3. Model and Problem Definitions

In this sections, we introduce some parameters and problem definitions.LetA be represented as a two-dimensional plane area; the whole of which can be observed by IoT devices that work together. There are m targets located on A. Let Q=r1,r2,⋯,rm represent the set of m targets located on A. Due to the particularity of some detection areas, such as smart cities and farmlands, IoT devices can only be deployed on some fixed locations. We call these fixed locations as candidate sites of IoT devices. Let L=L1,L2,⋯,LN denote the set of N candidate sites. Suppose that there exists n available IoT devices that can be deployed in the candidate sites to monitor targets in Q or the whole detection area A. We use S=s1,s2,⋯,sn to represent the set of n IoT devices, in which each IoT device si can be active continuously at most Ei time slots. In this paper, we assume that each IoT device si∈S continuously works Ei time slots once it starts working and Ei≤T, where T is the minimum time that the targets (or the detection area) are (or is) continuously observed. For any pair of si∈S and rj∈Q (or Lk∈L and rj∈Q), let dsi,rj (or dLk,rj) denote the Euclidean distance between si and rj (or Lk and rj).In this paper, we aim to find a subsetC⊆S of IoT devices which are deployed on some candidate sites in L to observe all targets in Q or the whole detection area and to minimize the total energy consumption of all IoT devices by scheduling IoT devices in C such that all targets or the whole detection area can be continuously observed by IoT devices at least T time. More formally, for two different kinds of problems, target coverage and area coverage, we call the research problems as the minimum energy consumption of IoT devices for target coverage through placement and scheduling (MTPS) and the minimum energy consumption of IoT devices for area coverage through placement and scheduling (MAPS), respectively, whose detailed definitions are shown in Definitions 1 and 2.Definition 1 (MTPS).
Given a setQ=r1,r2,⋯,rm of m targets located on detection area A, a set S=s1,s2,⋯,sn of n IoT devices in which all IoT devices have the same coverage range R and each IoT device si∈S can work Ei time slots, a set L=L1,L2,⋯,LN of N candidate sites to be put on IoT devices, a positive time T, the minimum energy consumption of IoT devices for target coverage through placement and scheduling (MTPS) problem aims at finding a subset C⊆S of IoT devices placed on the candidate sites in L and scheduling the IoT devices in C such that(1)
For any candidate siteLk∈L, it can be placed in more than one IoT device from C(2)
For arbitrary targetrj∈Q, it is continuously observed by IoT devices in C at least T time(3)
For each IoT devicesi∈C, it continuously works in Ei time slots once it starts working(4)
The total energy consumption of IoT devices inC, M=∑si∈CEi, is minimizedDefinition 2 (MAPS).
Given a detection areaA, a set S=s1,s2,⋯,sn of n IoT devices in which all IoT devices have the same coverage range R, and each IoT device si∈S can work Ei time slots, a set L=L1,L2,⋯,LN of N candidate sites to be put in IoT devices, a positive time T, the minimum energy consumption of IoT devices for area coverage through placement and scheduling (MAPS) problem aims at finding a subset C⊆S of IoT devices placed on the candidate sites in L and scheduling the IoT devices in C such that(1)
For any candidate siteLk∈L, it can be placed in more than one IoT devices from C(2)
For arbitrary pointp∈A, it is continuously observed by IoT devices in C at least T time(3)
For each IoT devicesi∈C, it continuously works in Ei time slots once it starts working(4)
The total energy consumption of IoT devices inC, M=∑si∈CEi, is minimized


## 4. Mathematical Formulation for the Problems

In this section, we will introduce the mathematical formulations for the problems MTPS and MAPS.We first introduce some notations as follows:i is the index of IoT devices, where 1≤i≤n.j is the index of targets, where 1≤j≤m. k is the index of candidate sites, where 1≤k≤N. t is the index of active time slots, where T time is divided into T time slots. We define the binary variables xik, ajk, and yit as follows:(1)xik=1,ifsiisplacedatLk,0,otherwise,ajk=1,ifdLk,rj≤R,0,otherwise,yit=1,ifsiisactiveatTtimeslot,0,otherwise.


### 4.1. Mathematical Formulation for the MTPS Problem

In this subsection, we will introduce the mathematical formulation for the MTPS problem. The problem can be formulated into an integer programming (IP) problem as follows:(2)min∑k=1N∑i=1nxik·Ei,(3)s.t.∑k=1N∑i=1najk·xik·yit≥1,j=1,2,⋯,m,t=1,2,⋯,T,(4)∑k=1N∑t=bibi+Ei−1xik·yit=Ei∃bi∈1,2,⋯,T,i=1,2,⋯,n,(5)xik∈0,1,i=1,2,⋯,n,k=1,2,⋯,N,(6)ajk∈0,1,j=1,2,⋯,m,k=1,2,⋯,N,(7)yit∈0,1,i=1,2,⋯,n,t=1,2,⋯,T.The function of equation (2) is to minimize the total energy consumption of IoT devices for continuous observing of all targets at least T time. Constraint (3) ensures that for each target rj∈Q, there at least exists an IoT device si∈S located at some candidate site Lk∈L to cover rj at any tth time slot. Constraint (4) guarantees that the IoT device si∈S located on Lk∈L will run out of energy as soon as it starts working. Constraints (5)–(7) define the domains of the variables.


### 4.2. Mathematical Formulation for the MAPS Problem

In this subsection, we will introduce the mathematical formulation for the MAPS problem. LetSi be the sensing region of sensor si. We use A to denote the area of A. The problem can be formulated as follows:(8)min∑k=1N∑i=1nxik·Ei,(9)s.t.⋃si∈CSi·∑k=1Nxik·yit⋂A=A,t=1,2,⋯,T,(10)∑k=1N∑t=bibi+Ei−1xik·yit=Ei∃bi∈1,2,⋯,T,i=1,2,⋯,n,(11)xik∈0,1,i=1,2,⋯,n,k=1,2,⋯,N,(12)yit∈0,1,i=1,2,⋯,n,t=1,2,⋯,T,The function of equation (8) is to minimize the total energy consumption of IoT devices for continuous observing of the whole detection area A at least T time. Constraint (9) ensures that for any point p∈A, there at least exists an IoT device si∈S located at some candidate site Lk∈L to cover p at any tth time slot. Constraint (10) guarantees that the IoT device si∈S located on Lk∈L will run out of energy as soon as it starts working. Constraints (11)–(12) define the domains of the variables.


### 4.3. NP-Hard Proofness

In the following, we will prove that the problems MTPS and MAPS are NP-hard. We first prove that the MTPS problem is NP-hard. Then, based on the MTPS problem, we prove that the MAPS problem is also NP-hard.We consider a special case of the MTPS problem where we setT=1, N=n, and Ei=1 for any IoT device si∈S. At this point, the objective of the MTPS problem can be transformed to find a subset C⊆S of IoT devices with minimum cardinality such that all targets are covered. Since for any IoT device si∈C, it needs to be placed at the corresponding candidate site to cover targets, the objective of the MTPS problem changes from finding the minimum subset C to looking for the minimum subset L′⊆L of candidate sites, where C=L′. Therefore, the special case of the MTPS problem can be equivalently transformed into the minimum point cover (MPC) problem as shown in Definition 3.Definition 3 (MPC).
Given a setQ=r1,r2,⋯,rm of m targets, a set L=L1,L2,⋯,LN of N candidate sites to be put in IoT devices, and all IoT devices have the same coverage range R, the minimum point cover (MPC) problem is to find a subset L′⊆L of candidate sites such that all targets are covered by IoT devices located on the candidate sites in L′ and the number of candidate sites L′ is minimized.In the MPC problem, for each candidate siteLk∈L, we use Uk to denote the set of targets covered by Lk where for each target rj, rj∈Uk if and only if dLk,rj≤R. Let F=U1,U2,⋯,UN. Then, the MPC problem can be equivalently transformed into the set cover (SC) problem, as shown in Definition 4.Definition 4 (SC).
Given a setQ=r1,r2,⋯,rm of m targets and a collection F=U1,U2,⋯,UN of N sets, where each Uk∈F is a subset of Q, the set cover (SC) problem is to find a subset F′⊂F such that ⋃Uk∈F′Uk=Q and F′ is minimum.Theorem 5.
The MPC problem is NP-hard.Proof.
According to the SC and MPC problems, we can obtain that the decision version of the MPC problem has a YES answer if and only if the decision version of the SC problem has a YES answer andF′=L′. Since the SC problem was proved NP-hard [30], the MPC problem is NP-hard.Theorem 6.
The MTPS problem is NP-hard.Proof.
According to Theorem5, we can verify that the MPC is NP-hard. Since the MPC problem is a special case of the MTPS problem, the MTPS problem is also NP-hard.Theorem 7.
The MAPS problem is NP-hard.Proof.
Since the continuous regionA is made up of an infinite set of points, we can take any set of discrete points in A as a special case of the MAPS where all the discrete points can be seen as targets for being observed by IoT devices. In such a case, the MAPS problem can be transformed into the MTPS problem. According to Theorem 6, we can verify that the MTPS is NP-hard. Therefore, the MAPS problem is also NP-hard.


## 4.1. Mathematical Formulation for the MTPS Problem

In this subsection, we will introduce the mathematical formulation for the MTPS problem. The problem can be formulated into an integer programming (IP) problem as follows:(2)min∑k=1N∑i=1nxik·Ei,(3)s.t.∑k=1N∑i=1najk·xik·yit≥1,j=1,2,⋯,m,t=1,2,⋯,T,(4)∑k=1N∑t=bibi+Ei−1xik·yit=Ei∃bi∈1,2,⋯,T,i=1,2,⋯,n,(5)xik∈0,1,i=1,2,⋯,n,k=1,2,⋯,N,(6)ajk∈0,1,j=1,2,⋯,m,k=1,2,⋯,N,(7)yit∈0,1,i=1,2,⋯,n,t=1,2,⋯,T.The function of equation (2) is to minimize the total energy consumption of IoT devices for continuous observing of all targets at least T time. Constraint (3) ensures that for each target rj∈Q, there at least exists an IoT device si∈S located at some candidate site Lk∈L to cover rj at any tth time slot. Constraint (4) guarantees that the IoT device si∈S located on Lk∈L will run out of energy as soon as it starts working. Constraints (5)–(7) define the domains of the variables.


## 4.2. Mathematical Formulation for the MAPS Problem

In this subsection, we will introduce the mathematical formulation for the MAPS problem. LetSi be the sensing region of sensor si. We use A to denote the area of A. The problem can be formulated as follows:(8)min∑k=1N∑i=1nxik·Ei,(9)s.t.⋃si∈CSi·∑k=1Nxik·yit⋂A=A,t=1,2,⋯,T,(10)∑k=1N∑t=bibi+Ei−1xik·yit=Ei∃bi∈1,2,⋯,T,i=1,2,⋯,n,(11)xik∈0,1,i=1,2,⋯,n,k=1,2,⋯,N,(12)yit∈0,1,i=1,2,⋯,n,t=1,2,⋯,T,The function of equation (8) is to minimize the total energy consumption of IoT devices for continuous observing of the whole detection area A at least T time. Constraint (9) ensures that for any point p∈A, there at least exists an IoT device si∈S located at some candidate site Lk∈L to cover p at any tth time slot. Constraint (10) guarantees that the IoT device si∈S located on Lk∈L will run out of energy as soon as it starts working. Constraints (11)–(12) define the domains of the variables.


## 4.3. NP-Hard Proofness

In the following, we will prove that the problems MTPS and MAPS are NP-hard. We first prove that the MTPS problem is NP-hard. Then, based on the MTPS problem, we prove that the MAPS problem is also NP-hard.We consider a special case of the MTPS problem where we setT=1, N=n, and Ei=1 for any IoT device si∈S. At this point, the objective of the MTPS problem can be transformed to find a subset C⊆S of IoT devices with minimum cardinality such that all targets are covered. Since for any IoT device si∈C, it needs to be placed at the corresponding candidate site to cover targets, the objective of the MTPS problem changes from finding the minimum subset C to looking for the minimum subset L′⊆L of candidate sites, where C=L′. Therefore, the special case of the MTPS problem can be equivalently transformed into the minimum point cover (MPC) problem as shown in Definition 3.Definition 3 (MPC).
Given a setQ=r1,r2,⋯,rm of m targets, a set L=L1,L2,⋯,LN of N candidate sites to be put in IoT devices, and all IoT devices have the same coverage range R, the minimum point cover (MPC) problem is to find a subset L′⊆L of candidate sites such that all targets are covered by IoT devices located on the candidate sites in L′ and the number of candidate sites L′ is minimized.In the MPC problem, for each candidate siteLk∈L, we use Uk to denote the set of targets covered by Lk where for each target rj, rj∈Uk if and only if dLk,rj≤R. Let F=U1,U2,⋯,UN. Then, the MPC problem can be equivalently transformed into the set cover (SC) problem, as shown in Definition 4.Definition 4 (SC).
Given a setQ=r1,r2,⋯,rm of m targets and a collection F=U1,U2,⋯,UN of N sets, where each Uk∈F is a subset of Q, the set cover (SC) problem is to find a subset F′⊂F such that ⋃Uk∈F′Uk=Q and F′ is minimum.Theorem 5.
The MPC problem is NP-hard.Proof.
According to the SC and MPC problems, we can obtain that the decision version of the MPC problem has a YES answer if and only if the decision version of the SC problem has a YES answer andF′=L′. Since the SC problem was proved NP-hard [30], the MPC problem is NP-hard.Theorem 6.
The MTPS problem is NP-hard.Proof.
According to Theorem5, we can verify that the MPC is NP-hard. Since the MPC problem is a special case of the MTPS problem, the MTPS problem is also NP-hard.Theorem 7.
The MAPS problem is NP-hard.Proof.
Since the continuous regionA is made up of an infinite set of points, we can take any set of discrete points in A as a special case of the MAPS where all the discrete points can be seen as targets for being observed by IoT devices. In such a case, the MAPS problem can be transformed into the MTPS problem. According to Theorem 6, we can verify that the MTPS is NP-hard. Therefore, the MAPS problem is also NP-hard.


## 5. Algorithm for the MTPS Problem

According to the definition of the MTPS problem, we can obtain that the total energy consumption of the IoT devices depends on the number of IoT devices with their corresponding initial energy. Therefore, we need to deploy IoT devices as few as possible to cover targets and schedule the placement of IoT devices to minimize the total energy consumption such that every target inQ is continuously observed at T time slots by IoT devices. Based on these considerations, we can find that the MTPS problem consists of two subproblems, minimum location coverage (MLC) and minimum energy consumption scheduling deployment (MESD), as shown in Definitions 8 and 9. In this section, we first propose an approximation algorithm for each of the problems MLC and MESD. Then, based on the problems MLC and MESD, we propose an approximation algorithm to solve the MTPS problem.Definition 8 (MLC).
Given a setQ=r1,r2,⋯,rm of m targets, a set L=L1,L2,⋯,LN of N candidate sites to be put in IoT devices with coverage range R, the minimum location coverage (MLC) problem is to find minimum subset L′⊆L of candidate sites such that all targets are within the coverage range of candidate sites in L′.Definition 9 (MESD).
Given a setS=s1,s2,⋯,sn of n IoT devices in which each IoT device si∈S has active time Ei, a set P=L1,L2,⋯,LK of K sites to be put IoT devices, a positive time T, the Minimum Energy consumption Scheduling Deployment (MESD) problem is to find a subset C⊆S of IoT devices placed at the sites in P and to schedule the IoT devices in C such that(1)
for any siteLk∈P, it can be placed more than one IoT device from C(2)
for arbitrary siteLk∈P, the IoT devices located at Lk can cumulatively work at least T time(3)
for each IoT devicesi∈C, it continuous works Ei time once it starts working, and(4)
the total energy consumption of IoT devices inC, M=∑si∈CEi, is minimizedAlgorithm 1: MLCA.
Input: Q=r1,r2,⋯,rm, L=L1,L2,⋯,LN, R;Output: L′;1: Sets of L′=∅, Uk=∅ for any Lk∈L;2: for arbitrary Lk∈Ldo3:  for any rj∈Qdo4:   ifdLk,rj≤Rthen5:    Uk=Uk∪rj;6:   end7:  end8: end9: whileL≠∅&&Q≠∅do10:  Pick Lk=argmaxLk∈LUk;11:  L′=L′∪Lk, L=L\Lk, Q=Q\Uk;12:  for any Li∈Ldo13:   Ui=Ui\Uk;14:  end15: end16: ifQ=∅then17: There is no solution for the MLC problem;18: end


### 5.1. Algorithm for the MLC Problem

In this subsection, we propose a greedy algorithm, called MLCA, to solve the MLC problem. LetUk denote the set of targets within the coverage range of Lk. The MLCA algorithm consists of two steps. Firstly, for arbitrary Lk∈L, we compute its coverage set Uk. For any rj∈Q, if dLk,rj≤R, then, Uk=Uk∪rj. Secondly, we repeat the following steps until one of the conditions L=∅ and Q=∅ is satisfied.(i)
SelectLk with the maximum Uk from L(ii)
Execute the operationsL′=L′∪Lk, L=L/Lk and Q=Q/Uk(iii)
For arbitraryLi∈L, update its coverage set by deleting targets in Uk∩Ui from UiAfter executing the above algorithm, we can obtain a setL′⊆L of candidate sites, which can cover all targets in Q. The pseudocode of the algorithm is shown in Algorithm 1. Then, we will analyze the performance of the MLCA algorithm.Theorem 10.
Suppose thatL∗ is an optimal solution for the MLC problem. If there exists a solution for the MLC problem, then, we can verify that the approximation ratio of the MLCA algorithm is lnm+1, where m is the number of targets.Proof.
According to the MLCA algorithm, we can observe that the while loop terminates after at mostm steps, since in each iteration of the while loop, there is at least one target that is covered by the candidate site Lk. Let Qk denote the number of targets that are still not covered at iteration k of the while loop. In each iteration k, we can use all L∗ candidate sites in the optimal solution to cover all targets in Q. Therefore, there must exist a candidate site in L∗ that covers at least Qk/L∗ targets, which means at least Qk/L∗ targets are covered in every iteration. In other words, we can obtain after iteration k; there are left at most Qk−Qk/L∗ targets that have not been covered by candidate sites, that is,(13)Qk+1≤1−1L∗·Qk≤1−1L∗2·Qk−1≤,⋯,≤1−1L∗k+1·Q0=1−1L∗k+1·m,where the last equality depends on the fact that Q0=m, since all m tragets are not covered by candidate sites before the first iteration of the while loop. Notice that there exists 1≤i≤m such that after executing i iterations of the while loop, Qi≤1. Based on the fact that 1+x≤ex for any x∈−∞,+∞, we have(14)1−1L∗i=1−1L∗L∗i/L∗≤e−i/L∗.
Based on inequations (13) and (14), we can obtain(15)m·e−i/L∗≤1⇔i≥L∗·lnm.
Therefore, we can obtain that afteri=L∗·lnm iterations, the remaining number of targets in Qi is smaller or equal to 1. Thus, the algorithm will terminate after at most L∗·lnm+1 iterations, which can obtain L′≤L∗·lnm+1≤lnm+1·L∗, since L∗≥1 and only one candidate site is added into L′ in each iteration based on the algorithm MLCA.Theorem 11.
The time complexity of the MLCA algorithm isOmN, where m and N are the number of targets and the number of candidate sites, respectively.Proof.
The MLCA algorithm consists of two phases. Firstly, the algorithm needsN iterations to compute the corresponding coverage sets for all candidate sites in L, as shown in the first while loop. In each iteration, since the number of targets is less than or equal to m, at most m steps are needed to determine which coverage set targets belong to. Therefore, we need at most mN steps to compute the coverage sets for all candidate sites in L. Secondly, at most minN,m iterations are needed in the while loop. In each iteration, we need to pick the candidate site Lk with the maximum Uk for executing N steps since 1≤k≤N. Then, we update all coverage sets of candidate sites with N steps. Therefore, we need at most N·minN,m steps in the second while loop.
Consequently, the time complexity of the MLCA algorithm isOmN=OmN+N·minN,m.


### 5.2. Algorithm for the MESD Problem

In this subsection, we propose an approximation algorithm to solve the MESD problem, called MESDA. Before describing the algorithm, we introduce some notations. For any1≤k≤K, we use Ck to denote the set of IoT devices placed at location Lk and let Φ=C1,C2,⋯,CK. Let Mk represent the total energy consumption of the IoT devices in Ck.The MESDA consists of two phases. The first phase is to find a subsetCk⊆S of IoT devices from S for any 1≤k≤K such that ∑si∈CkEi≥T. The second phase is to optimize Mk by replacing the high-energy-consuming IoT devices in Ck with low-energy-consuming ones from the remaining IoT devices in S for any 1≤k≤K. Afterwards, we compute Φ=C1,C2,⋯,CK, C=⋃1≤k≤KCk, and M=∑Ck∈ΦMk. The detailed description of the algorithm is shown as follows.Initially, we setΦ=∅, C=∅, M=0, Ck=∅, and Mk=0 for each 1≤k≤K. The first phase of the MESD algorithm repeats the following four steps until the conditions P=∅ and S=∅ are satisfied.(i)
Selectsi with the maximum Ei from S, where if there exists two IoT devices si,sj∈S such that Ei=Ej, then, their maximum ID is selected(ii)
PickLk with the minimum Mk for any 1≤k≤K, where if there exist Mk and Ml such that Mk=Ml, then, their minimum ID is selected(iii)
Addsi into Ck, and Mk=Mk+Ei. Then, S=S/si(iv)
CompareMk with T. If Mk≥T, then, P=P/LkAfter executing the first phase of the algorithm, we can obtain a setCk of IoT devices for any Lk∈P, where the total working time Mk of IoT devices is greater than or equal to T. In the following, for any 1≤k≤K, we optimize Mk by replacing the high-energy-consuming IoT devices in Ck with low-energy-consuming ones in S.The second phase of the algorithm repeats the following steps untilS=∅.(i)
Selectsi with the maximum Ei from S(ii)
Compute atuple<sj,k≥argminsj∈Ck,1≤k≤KMk−Ej+Ei such that Mk−Ej+Ei≥T(iii)
CompareEi with Ej. If Ei≥Ej, then, si is deleted from S, otherwise, Ck=Ck∪sj/si, Mk=Mk−Ei+Ej, and si is removed from SAfter executing the second phase of the algorithm, we can obtain a setCk of IoT devices located on each Lk∈P and the total energy consumption Mk=∑si∈CkEi of IoT devices in Ck such that all targets covered by site Lk are continuously observed at least T time. Finally, we can obtain Φ=C1,C2,⋯,CK, M=∑Ck∈ΦMk, and C=⋃1≤k≤KCk. The pseudocode of the algorithm is shown in Algorithm 2.Algorithm 2: MESDA.
Input: S=s1,s2,⋯,sn, Ei for each si∈S, P=L1,L2,⋯,LK, T;Output: C, M, Φ;1: Sets of C=∅, M=0, Ck=∅ and Mk=0 for each 1≤k≤K;2: whileP≠∅&&S≠∅do3:  Pick si=argmaxsi∈SEi;4:  Pick Lk=argminLk∈PMk;5:  Ck=Ck∪si, Mk=Mk+Ei, S=S\si;6:  ifMk≥Tthen7:   P=P\Lk;8:  end9: end10: whileS≠∅do11:  Pick si=argmaxsi∈SEi;12:  Select <sj,k>=argminsj∈Ck,1≤k≤KMk−Ej+Ei such that Mk−Ej+Ei≥T;13:  ifEi≥Ejthen14:   S=S\si;15:  else16:   Ck=Ck∪sj\si, Mk=Mk−Ej+Ei, S=S\si;17:  end18: end19:Φ=⋃1≤k≤KCk, M=∑Ck∈ΦMk, C=⋃Ck∈ΦCk;We useC∗ to represent the optimal set of IoT devices placed at sites in P for the MESD problem. Let M∗ denote the total energy consumption of IoT devices in C∗. Without loss of generality, we use Ck∗ to be the optimal set of IoT devices placed at Lk∈P when C∗ has been confirmed. Let Mk∗ represent the total energy consumption of IoT devices in Ck∗.Theorem 12.
If the MESDA algorithm has the feasible solution, then, we can verify that the approximation ratio of the algorithm is 2.Proof.
According to the definition of the MESD problem, we haveMk∗≥T for any 1≤k≤K and M∗=∑1≤k≤KMk∗≥K·T.
For any1≤k≤K, we let <si,Ei≥argmaxsj∈CkEj, where Ck is obtained by the MESDA algorithm. We analyze the performance of the algorithm in the light of the following two cases.(1)
0<Ei<T/2. Then, we can obtain that for any sj∈Ck, Ej<T/2. Based on the algorithm, the last IoT device added into Ck makes Mk be greater than or equal to T, which means Mk≤T+Ej<3T/2≤1.5Mk∗(2)
T/2≤Ei<T. If there exists Ej∈Ck such that T/2<Ej≤Ei, then based on the algorithm, we can obtain Ck=si,sj and Mk=Ei+Ej<2T<2Mk∗. Otherwise, we can derive Mk≤T+Ej≤1.5Mk∗
From what have been discussed, we can obtainMk<2Mk∗. Therefore, we have M=∑1≤k≤KMk≤∑1≤k≤K2Mk∗≤2M∗, which means that the approximation ratio of the MESDA algorithm is 2.Theorem 13.
The time complexity of the MESDA algorithm isOn3+nK, where n and K are the number of IoT devices and the number of sites, respectively.Proof.
According to the MESDA algorithm, we can verify that the algorithm contains two while loops running and the other operations with constant running time. The first while loop consists of at mostn iterations, since S≤n. In each iteration, at most n steps are needed to select the IoT device si with the maximum energy and K steps are required to compute the site Lk with the minimum total energy consumption of IoT devices located on Lk. The other operations in the iteration can be executed in constant time. Therefore, the first while loop runs at most On2+nK time. The second while loop runs S iterations. In each iteration, the algorithm runs at most S steps to select the IoT device si with the maximum energy. Then, it calculates the total energy consumption with at most On·S running time by replacing each IoT device that has been deployed on site in P with si and selects sj with the minimum Mk−Ej+Ei among all IoT devices except IoT devices in S. The other operations in the iteration can be executed in constant time. Therefore, the total running time of the second while loop is at most On3=On·S2+S2.
Consequently, we can obtain that the time complexity of the MESDA algorithm isOn3+nK=On2+nK+On3.


### 5.3. Algorithm for the MTPS Problem

In this subsection, we propose an approximation algorithm, called MTPSA, to solve the MTPS problem based on the MLC and MESD problems. The algorithm consists of two steps corresponding to Algorithms1 and 2. The detailed illustration of the algorithm is shown in Algorithm 3.Algorithm 3: MTPSA.
Input: Q=r1,r2,⋯,rmS=s1,s2,⋯,sn, Ei for each si∈S, L=L1,L2,⋯,LN, R, T;Output: C, M, Φ;Step 1: Compute the set L′ of candidate sites to cover all targets in Q by executing Algorithm 1;Step 2: Compute Φ, C, M based on L′ by executing Algorithm 2,whereP=L′;Suppose thatCopt∗ is an optimal subset of S for the MTPS problem. Let Mopt∗ be the total energy consumption of IoT devices in Copt∗. Since each rj∈Q needs to be continuously observed at least T time, we divide T into equal T time slots. We use ct∗ to represent the minimum energy consumption of all active IoT devices for the MTPS problem such that all targets are covered at the tth time slot, and let Lt∗ denote the set of candidate sites placed in the active IoT devices in the tth time slot.Lemma 14.
For any1≤t≤T, we have ct∗≥L∗, where L∗ is the minimum set of candidate sites for the MLC problem.Proof.
In the MTPS problem, all targets need to be covered by IoT devices placed at candidate sites inL for any 1≤t≤T, which means that there exists a subset Lt⊆L that can cover all targets for the arbitrary tth time slot. Thus, based on the definitions of MTPS problem and MLC problem, we can obtain that for any such subset Lt, it is a feasible solution for the MLC problem. Therefore, we have Lt∗≥L∗, since Lt∗ is a feasible solution for the MLC problem. Therefore, we can derive ct∗≥L∗ since ct∗=Lt∗.Lemma 15.
We can obtainMopt∗≥L∗·T.Proof.
According to Lemma14, we can obtain ct∗≥L∗ for arbitrary 1≤t≤T. Based on the definition of the MTPS problem, we have Mopt∗≥∑1≤t≤Tct∗≥L∗·T.Theorem 16.
The performance ratio of the MTPSA algorithm is2lnm+2, where m is the number of targets.Proof.
According to the MTPSA algorithm, we haveM=∑Lk∈L′Mk, where M is the total energy consumption of IoT devices obtained by the MTPSA algorithm and Mk is the energy consumption of IoT devices located on Lk. On the basis of Theorems 10 and 12, we can derive L′≤lnm·L∗+1 and Mk<2T for any 1≤k≤L′. Based on Lemma 15, we can obtain(16)M=∑Lk∈L′Mk≤L′·maxMk∣Lk∈L′≤lnm·L∗+1·2T≤2lnm+1·Mopt∗.
The theorem has been proved.Theorem 17.
The time complexity of the MTPSA algorithm isOn3+mN+nN, where n is the number of available IoT devices in S, m denotes the number of targets in Q, and N represents the number of candidate sites in L.Proof.
Based on Theorems11 and 13, we can obtain that the time complexity of the MTPSA algorithm is On3+mN+nN=OmN+n3+nK, since K=L′≤N.


## 5.1. Algorithm for the MLC Problem

In this subsection, we propose a greedy algorithm, called MLCA, to solve the MLC problem. LetUk denote the set of targets within the coverage range of Lk. The MLCA algorithm consists of two steps. Firstly, for arbitrary Lk∈L, we compute its coverage set Uk. For any rj∈Q, if dLk,rj≤R, then, Uk=Uk∪rj. Secondly, we repeat the following steps until one of the conditions L=∅ and Q=∅ is satisfied.(i)
SelectLk with the maximum Uk from L(ii)
Execute the operationsL′=L′∪Lk, L=L/Lk and Q=Q/Uk(iii)
For arbitraryLi∈L, update its coverage set by deleting targets in Uk∩Ui from UiAfter executing the above algorithm, we can obtain a setL′⊆L of candidate sites, which can cover all targets in Q. The pseudocode of the algorithm is shown in Algorithm 1. Then, we will analyze the performance of the MLCA algorithm.Theorem 10.
Suppose thatL∗ is an optimal solution for the MLC problem. If there exists a solution for the MLC problem, then, we can verify that the approximation ratio of the MLCA algorithm is lnm+1, where m is the number of targets.Proof.
According to the MLCA algorithm, we can observe that the while loop terminates after at mostm steps, since in each iteration of the while loop, there is at least one target that is covered by the candidate site Lk. Let Qk denote the number of targets that are still not covered at iteration k of the while loop. In each iteration k, we can use all L∗ candidate sites in the optimal solution to cover all targets in Q. Therefore, there must exist a candidate site in L∗ that covers at least Qk/L∗ targets, which means at least Qk/L∗ targets are covered in every iteration. In other words, we can obtain after iteration k; there are left at most Qk−Qk/L∗ targets that have not been covered by candidate sites, that is,(13)Qk+1≤1−1L∗·Qk≤1−1L∗2·Qk−1≤,⋯,≤1−1L∗k+1·Q0=1−1L∗k+1·m,where the last equality depends on the fact that Q0=m, since all m tragets are not covered by candidate sites before the first iteration of the while loop. Notice that there exists 1≤i≤m such that after executing i iterations of the while loop, Qi≤1. Based on the fact that 1+x≤ex for any x∈−∞,+∞, we have(14)1−1L∗i=1−1L∗L∗i/L∗≤e−i/L∗.
Based on inequations (13) and (14), we can obtain(15)m·e−i/L∗≤1⇔i≥L∗·lnm.
Therefore, we can obtain that afteri=L∗·lnm iterations, the remaining number of targets in Qi is smaller or equal to 1. Thus, the algorithm will terminate after at most L∗·lnm+1 iterations, which can obtain L′≤L∗·lnm+1≤lnm+1·L∗, since L∗≥1 and only one candidate site is added into L′ in each iteration based on the algorithm MLCA.Theorem 11.
The time complexity of the MLCA algorithm isOmN, where m and N are the number of targets and the number of candidate sites, respectively.Proof.
The MLCA algorithm consists of two phases. Firstly, the algorithm needsN iterations to compute the corresponding coverage sets for all candidate sites in L, as shown in the first while loop. In each iteration, since the number of targets is less than or equal to m, at most m steps are needed to determine which coverage set targets belong to. Therefore, we need at most mN steps to compute the coverage sets for all candidate sites in L. Secondly, at most minN,m iterations are needed in the while loop. In each iteration, we need to pick the candidate site Lk with the maximum Uk for executing N steps since 1≤k≤N. Then, we update all coverage sets of candidate sites with N steps. Therefore, we need at most N·minN,m steps in the second while loop.
Consequently, the time complexity of the MLCA algorithm isOmN=OmN+N·minN,m.


## 5.2. Algorithm for the MESD Problem

In this subsection, we propose an approximation algorithm to solve the MESD problem, called MESDA. Before describing the algorithm, we introduce some notations. For any1≤k≤K, we use Ck to denote the set of IoT devices placed at location Lk and let Φ=C1,C2,⋯,CK. Let Mk represent the total energy consumption of the IoT devices in Ck.The MESDA consists of two phases. The first phase is to find a subsetCk⊆S of IoT devices from S for any 1≤k≤K such that ∑si∈CkEi≥T. The second phase is to optimize Mk by replacing the high-energy-consuming IoT devices in Ck with low-energy-consuming ones from the remaining IoT devices in S for any 1≤k≤K. Afterwards, we compute Φ=C1,C2,⋯,CK, C=⋃1≤k≤KCk, and M=∑Ck∈ΦMk. The detailed description of the algorithm is shown as follows.Initially, we setΦ=∅, C=∅, M=0, Ck=∅, and Mk=0 for each 1≤k≤K. The first phase of the MESD algorithm repeats the following four steps until the conditions P=∅ and S=∅ are satisfied.(i)
Selectsi with the maximum Ei from S, where if there exists two IoT devices si,sj∈S such that Ei=Ej, then, their maximum ID is selected(ii)
PickLk with the minimum Mk for any 1≤k≤K, where if there exist Mk and Ml such that Mk=Ml, then, their minimum ID is selected(iii)
Addsi into Ck, and Mk=Mk+Ei. Then, S=S/si(iv)
CompareMk with T. If Mk≥T, then, P=P/LkAfter executing the first phase of the algorithm, we can obtain a setCk of IoT devices for any Lk∈P, where the total working time Mk of IoT devices is greater than or equal to T. In the following, for any 1≤k≤K, we optimize Mk by replacing the high-energy-consuming IoT devices in Ck with low-energy-consuming ones in S.The second phase of the algorithm repeats the following steps untilS=∅.(i)
Selectsi with the maximum Ei from S(ii)
Compute atuple<sj,k≥argminsj∈Ck,1≤k≤KMk−Ej+Ei such that Mk−Ej+Ei≥T(iii)
CompareEi with Ej. If Ei≥Ej, then, si is deleted from S, otherwise, Ck=Ck∪sj/si, Mk=Mk−Ei+Ej, and si is removed from SAfter executing the second phase of the algorithm, we can obtain a setCk of IoT devices located on each Lk∈P and the total energy consumption Mk=∑si∈CkEi of IoT devices in Ck such that all targets covered by site Lk are continuously observed at least T time. Finally, we can obtain Φ=C1,C2,⋯,CK, M=∑Ck∈ΦMk, and C=⋃1≤k≤KCk. The pseudocode of the algorithm is shown in Algorithm 2.Algorithm 2: MESDA.
Input: S=s1,s2,⋯,sn, Ei for each si∈S, P=L1,L2,⋯,LK, T;Output: C, M, Φ;1: Sets of C=∅, M=0, Ck=∅ and Mk=0 for each 1≤k≤K;2: whileP≠∅&&S≠∅do3:  Pick si=argmaxsi∈SEi;4:  Pick Lk=argminLk∈PMk;5:  Ck=Ck∪si, Mk=Mk+Ei, S=S\si;6:  ifMk≥Tthen7:   P=P\Lk;8:  end9: end10: whileS≠∅do11:  Pick si=argmaxsi∈SEi;12:  Select <sj,k>=argminsj∈Ck,1≤k≤KMk−Ej+Ei such that Mk−Ej+Ei≥T;13:  ifEi≥Ejthen14:   S=S\si;15:  else16:   Ck=Ck∪sj\si, Mk=Mk−Ej+Ei, S=S\si;17:  end18: end19:Φ=⋃1≤k≤KCk, M=∑Ck∈ΦMk, C=⋃Ck∈ΦCk;We useC∗ to represent the optimal set of IoT devices placed at sites in P for the MESD problem. Let M∗ denote the total energy consumption of IoT devices in C∗. Without loss of generality, we use Ck∗ to be the optimal set of IoT devices placed at Lk∈P when C∗ has been confirmed. Let Mk∗ represent the total energy consumption of IoT devices in Ck∗.Theorem 12.
If the MESDA algorithm has the feasible solution, then, we can verify that the approximation ratio of the algorithm is 2.Proof.
According to the definition of the MESD problem, we haveMk∗≥T for any 1≤k≤K and M∗=∑1≤k≤KMk∗≥K·T.
For any1≤k≤K, we let <si,Ei≥argmaxsj∈CkEj, where Ck is obtained by the MESDA algorithm. We analyze the performance of the algorithm in the light of the following two cases.(1)
0<Ei<T/2. Then, we can obtain that for any sj∈Ck, Ej<T/2. Based on the algorithm, the last IoT device added into Ck makes Mk be greater than or equal to T, which means Mk≤T+Ej<3T/2≤1.5Mk∗(2)
T/2≤Ei<T. If there exists Ej∈Ck such that T/2<Ej≤Ei, then based on the algorithm, we can obtain Ck=si,sj and Mk=Ei+Ej<2T<2Mk∗. Otherwise, we can derive Mk≤T+Ej≤1.5Mk∗
From what have been discussed, we can obtainMk<2Mk∗. Therefore, we have M=∑1≤k≤KMk≤∑1≤k≤K2Mk∗≤2M∗, which means that the approximation ratio of the MESDA algorithm is 2.Theorem 13.
The time complexity of the MESDA algorithm isOn3+nK, where n and K are the number of IoT devices and the number of sites, respectively.Proof.
According to the MESDA algorithm, we can verify that the algorithm contains two while loops running and the other operations with constant running time. The first while loop consists of at mostn iterations, since S≤n. In each iteration, at most n steps are needed to select the IoT device si with the maximum energy and K steps are required to compute the site Lk with the minimum total energy consumption of IoT devices located on Lk. The other operations in the iteration can be executed in constant time. Therefore, the first while loop runs at most On2+nK time. The second while loop runs S iterations. In each iteration, the algorithm runs at most S steps to select the IoT device si with the maximum energy. Then, it calculates the total energy consumption with at most On·S running time by replacing each IoT device that has been deployed on site in P with si and selects sj with the minimum Mk−Ej+Ei among all IoT devices except IoT devices in S. The other operations in the iteration can be executed in constant time. Therefore, the total running time of the second while loop is at most On3=On·S2+S2.
Consequently, we can obtain that the time complexity of the MESDA algorithm isOn3+nK=On2+nK+On3.


## 5.3. Algorithm for the MTPS Problem

In this subsection, we propose an approximation algorithm, called MTPSA, to solve the MTPS problem based on the MLC and MESD problems. The algorithm consists of two steps corresponding to Algorithms1 and 2. The detailed illustration of the algorithm is shown in Algorithm 3.Algorithm 3: MTPSA.
Input: Q=r1,r2,⋯,rmS=s1,s2,⋯,sn, Ei for each si∈S, L=L1,L2,⋯,LN, R, T;Output: C, M, Φ;Step 1: Compute the set L′ of candidate sites to cover all targets in Q by executing Algorithm 1;Step 2: Compute Φ, C, M based on L′ by executing Algorithm 2,whereP=L′;Suppose thatCopt∗ is an optimal subset of S for the MTPS problem. Let Mopt∗ be the total energy consumption of IoT devices in Copt∗. Since each rj∈Q needs to be continuously observed at least T time, we divide T into equal T time slots. We use ct∗ to represent the minimum energy consumption of all active IoT devices for the MTPS problem such that all targets are covered at the tth time slot, and let Lt∗ denote the set of candidate sites placed in the active IoT devices in the tth time slot.Lemma 14.
For any1≤t≤T, we have ct∗≥L∗, where L∗ is the minimum set of candidate sites for the MLC problem.Proof.
In the MTPS problem, all targets need to be covered by IoT devices placed at candidate sites inL for any 1≤t≤T, which means that there exists a subset Lt⊆L that can cover all targets for the arbitrary tth time slot. Thus, based on the definitions of MTPS problem and MLC problem, we can obtain that for any such subset Lt, it is a feasible solution for the MLC problem. Therefore, we have Lt∗≥L∗, since Lt∗ is a feasible solution for the MLC problem. Therefore, we can derive ct∗≥L∗ since ct∗=Lt∗.Lemma 15.
We can obtainMopt∗≥L∗·T.Proof.
According to Lemma14, we can obtain ct∗≥L∗ for arbitrary 1≤t≤T. Based on the definition of the MTPS problem, we have Mopt∗≥∑1≤t≤Tct∗≥L∗·T.Theorem 16.
The performance ratio of the MTPSA algorithm is2lnm+2, where m is the number of targets.Proof.
According to the MTPSA algorithm, we haveM=∑Lk∈L′Mk, where M is the total energy consumption of IoT devices obtained by the MTPSA algorithm and Mk is the energy consumption of IoT devices located on Lk. On the basis of Theorems 10 and 12, we can derive L′≤lnm·L∗+1 and Mk<2T for any 1≤k≤L′. Based on Lemma 15, we can obtain(16)M=∑Lk∈L′Mk≤L′·maxMk∣Lk∈L′≤lnm·L∗+1·2T≤2lnm+1·Mopt∗.
The theorem has been proved.Theorem 17.
The time complexity of the MTPSA algorithm isOn3+mN+nN, where n is the number of available IoT devices in S, m denotes the number of targets in Q, and N represents the number of candidate sites in L.Proof.
Based on Theorems11 and 13, we can obtain that the time complexity of the MTPSA algorithm is On3+mN+nN=OmN+n3+nK, since K=L′≤N.


## 6. Algorithm for the MAPS Problem

In this section, we propose an algorithm to solve the MAPS problem.Similar to the definition of the MTPS problem, the total energy consumption of the IoT devices depends on the number of IoT devices with their corresponding initial energy. Therefore, we also need to deploy IoT devices as few as possible to cover the whole detection area and schedule the placement of IoT devices to minimize the total energy consumption such that the whole area is continuously observedT time slots by IoT devices. Therefore, we can find that the MAPS problem is also composed of two subproblems, minimum location area coverage (MLAC) and MESD, as shown in Definitions 18 and 9. The MESD problem has been solved by Algorithm 2. Thus, in this section, we first propose an approximation algorithm to solve the MLAC problem. Then, based on the problems MLAC and MESD, we propose an approximation algorithm to solve the MAPS problem.We useALk to denote the coverage region of Lk when the coverage range of IoT devices put on Lk is R, that is, for any point p∈ALk, dLk,p≤R. Let DLk be the border of ALk.Definition 18 (MLAC).
Given a detection areaA, a set L=L1,L2,⋯,LN of N candidate sites, Δ=AL1,AL2,⋯,ALN, the minimum location area coverage (MLAC) problem is to find a minimum subset L′⊆L of candidate sites such that ⋃Lk∈L′ALk⋂A=A.In the following, we first introduce the definition of the Voronoi diagram of candidate sites onL, which is used to solve the MLAC problem.


### 6.1. Voronoi Diagram of Candidate Sites

The definition of the Voronoi diagram of candidate sites inL can be defined as the subdivision of the detection area A into N cells as shown in [31]. Any point p∈A, in the cell corresponding to a candidate site Lk, is closer to Lk than to any other candidate site in L. Formally, the Voronoi cell corresponding to Lk can be defined as(17)CellLk=⋂k=1,j≠knp∣dLk,p≤dLj,p.In equation (17), two Voronoi cells meet along a Voronoi edge and three cells meet at a Voronoi vertex. For simplicity, we use GVV,VE to denote the Voronoi diagram of candidate sites in L, where VV represents the set of Voronoi vertices and VE denotes the set of Voronoi edges.


### 6.2. Algorithm for the MLAC Problem

In this subsection, we propose an approximation algorithm to solve the MLAC problem, which is called the MLAC Algorithm (MLACA).Before describing the algorithm, we introduce some definitions and parameters as follows:Definition 19 (neighbor Voronoi diagram).
The Neighbor Voronoi diagram of a candidate siteLk is the Voronoi diagram of the Voronoi neighbors of Lk when Lk is excluded, where we call a site Lj a Voronoi neighbor of Lk if their cells share an edge.Definition 20 (redundant candidate site).
A candidate siteLk is said to be a redundant candidate site if ⋃Lj∈L/LkALj⋂A=A.Definition 21 (neighbor Voronoi vertices).
The neighbor Voronoi vertices of a candidate siteLk are the Voronoi vertices of the neighbor Voronoi diagram of Voronoi neighbors of Lk.Definition 22 (neighbor Voronoi intersection vertices).
Neighbor Voronoi intersection vertices ofLk are the intersections between edges of the neighbor Voronoi diagram and the circumcircle DLk of ALk.We useregL=cellL1,cellL2,⋯,cellLN to represent the set of all cells for GVV,VE. Let NVLk be the set of Voronoi neighbors of Lk. We use GVVLk,NELk to represent the neighbor Voronoi diagram of Voronoi neighbors of Lk, where VVLk denotes the set of the neighbor Voronoi vertices and NELk represents the set of the Voronoi edge of GVVLk,NELk. We use NILk to be the set of the neighbor Voronoi intersection vertices of Lk.Based on Theorem10 in the work [31], we can obtain the following lemma.Lemma 23.
A candidate siteLk is a redundant candidate site if and only if all the neighbor Voronoi vertices and neighbor Voronoi intersection vertices of Lk are covered by the Voronoi neighbors of Lk.In the following, we will introduce the detailed description of the MLACA algorithm.Initially, we setL′=L, VV=∅, VE=∅, and NVLk=∅ for any Lk∈L. The execution of the algorithm consists of three steps as follows.Firstly, we compute the Voronoi diagramGVV,VE and regL′ of candidate sites in L′ by using the algorithm in [32].Secondly, we delete all redundant candidate sites fromL′. For any Lk∈L′, we compute the set NVLk based on GVV,VE and RegL′. Then, we construct the Voronoi diagram GVVLk,NELk on NVLk by using the algorithm in [32]. Next, we compute the set NILk based on GVVLk,NELk. Afterwards, we judge whether or not all points in VVLk and NILk are covered by coverage regions of all Voronoi neighbors. If yes, we delete Lk from L′ and update the Voronoi diagram GVV,VE of candidate sites in new L′ by using the algorithm in [32].Finally, the algorithm returnsL′.The pseudocode of the algorithm is shown in Algorithm4.Algorithm 4: MLACA.
Input: The dimensions of A, the coverage range R, L=L1,L2,⋯,LN;Output: L′;1: Sets of L′=L, VV=∅, VE=∅, NVLk=∅ for any Lk∈L;2: Compute the Voronoi diagram GVV,VE and RegL′ of candidate sites on L′ by using algorithm in [32];3: for any Lk∈L′do4:  Compute NVLk based on GVV,VE and RegL′;5:  Construct GVVLk,NELk on NVLk by using algorithm in [32];6:  Compute NILk based on GVVLk,NELk;7:  ifVVLk∪NILk⊂⋃Lj∈NVLkALjthen8:   L′=L′\Lk;9:   Compute the Voronoi diagram GVV,VE of candidate sites in L′ by using algorithm in [32];10: end11: end forTheorem 24.
The time complexity of the MLACA algorithm isON2logN, where N represents the number of candidate sites in L.Proof.
According to the MLACA algorithm, we can find that the algorithm consists of three steps. Firstly, we compute the Voronoi diagram of candidate sites inL with ONlogN time by using the algorithm in [32]. Secondly, we need at most N iterations in the for loop since L=N. In each iteration, we first need at most N times to compute the set NVLk of Voronoi neighbors of Lk. Then, we need at most ONVLklogNVLk time to compute the neighbor Voronoi diagram on NVLk. Next, we need at most N times to compute NILk. We need at most another ONlogN time to update the Voronoi diagram by using the algorithm in [32] when Lk is a redundant candidate site. Therefore, we need at most ON2logN=ON∗N+NVLklogNVLk+NlogN time for the for loop since NVLk≤N.
From what has been discussed, we can verify that the time complexity of the MLACA algorithm isON2logN.


### 6.3. Algorithm for the MAPS Problem

In this subsection, we propose an approximation algorithm to solve the MAPS problem, which is called MAPSA. Similar to the MTPSA algorithm, the MAPSA algorithm consists of two phases. The first phase is to find a subsetL′⊆L of candidate sites by using Algorithm 4 such that the whole area A is covered by the coverage region of candidate sites in L′. The second phase is to find a subset C⊆S of IoT devices placed at the sites in L′ by executing Algorithm 2 such that for any point p∈A, it is observed by IoT devices in C at least T time. The detailed illustration of the algorithm is shown in Algorithm 5.Algorithm 5: MAPSA.
Input: S=s1,s2,⋯,sn, Ei for each si∈S, L=L1,L2,⋯,LN, R, T;Output: C, M;Step 1: Compute the set L′ of candidate sites to cover the whole area by executing Algorithm 4;Step 2: Compute C, M based on L′ by executing Algorithm 2,whereP=L′;Theorem 25.
The time complexity of the MAPSA algorithm isOn3+nN+N2logN, where n is the number of available IoT devices in S, and N represents the number of candidate sites in L.Proof.
Based on Theorems13 and 24, we can verify that the time complexity of the MAPSA algorithm is On3+nN+N2logN.


## 6.1. Voronoi Diagram of Candidate Sites

The definition of the Voronoi diagram of candidate sites inL can be defined as the subdivision of the detection area A into N cells as shown in [31]. Any point p∈A, in the cell corresponding to a candidate site Lk, is closer to Lk than to any other candidate site in L. Formally, the Voronoi cell corresponding to Lk can be defined as(17)CellLk=⋂k=1,j≠knp∣dLk,p≤dLj,p.In equation (17), two Voronoi cells meet along a Voronoi edge and three cells meet at a Voronoi vertex. For simplicity, we use GVV,VE to denote the Voronoi diagram of candidate sites in L, where VV represents the set of Voronoi vertices and VE denotes the set of Voronoi edges.


## 6.2. Algorithm for the MLAC Problem

In this subsection, we propose an approximation algorithm to solve the MLAC problem, which is called the MLAC Algorithm (MLACA).Before describing the algorithm, we introduce some definitions and parameters as follows:Definition 19 (neighbor Voronoi diagram).
The Neighbor Voronoi diagram of a candidate siteLk is the Voronoi diagram of the Voronoi neighbors of Lk when Lk is excluded, where we call a site Lj a Voronoi neighbor of Lk if their cells share an edge.Definition 20 (redundant candidate site).
A candidate siteLk is said to be a redundant candidate site if ⋃Lj∈L/LkALj⋂A=A.Definition 21 (neighbor Voronoi vertices).
The neighbor Voronoi vertices of a candidate siteLk are the Voronoi vertices of the neighbor Voronoi diagram of Voronoi neighbors of Lk.Definition 22 (neighbor Voronoi intersection vertices).
Neighbor Voronoi intersection vertices ofLk are the intersections between edges of the neighbor Voronoi diagram and the circumcircle DLk of ALk.We useregL=cellL1,cellL2,⋯,cellLN to represent the set of all cells for GVV,VE. Let NVLk be the set of Voronoi neighbors of Lk. We use GVVLk,NELk to represent the neighbor Voronoi diagram of Voronoi neighbors of Lk, where VVLk denotes the set of the neighbor Voronoi vertices and NELk represents the set of the Voronoi edge of GVVLk,NELk. We use NILk to be the set of the neighbor Voronoi intersection vertices of Lk.Based on Theorem10 in the work [31], we can obtain the following lemma.Lemma 23.
A candidate siteLk is a redundant candidate site if and only if all the neighbor Voronoi vertices and neighbor Voronoi intersection vertices of Lk are covered by the Voronoi neighbors of Lk.In the following, we will introduce the detailed description of the MLACA algorithm.Initially, we setL′=L, VV=∅, VE=∅, and NVLk=∅ for any Lk∈L. The execution of the algorithm consists of three steps as follows.Firstly, we compute the Voronoi diagramGVV,VE and regL′ of candidate sites in L′ by using the algorithm in [32].Secondly, we delete all redundant candidate sites fromL′. For any Lk∈L′, we compute the set NVLk based on GVV,VE and RegL′. Then, we construct the Voronoi diagram GVVLk,NELk on NVLk by using the algorithm in [32]. Next, we compute the set NILk based on GVVLk,NELk. Afterwards, we judge whether or not all points in VVLk and NILk are covered by coverage regions of all Voronoi neighbors. If yes, we delete Lk from L′ and update the Voronoi diagram GVV,VE of candidate sites in new L′ by using the algorithm in [32].Finally, the algorithm returnsL′.The pseudocode of the algorithm is shown in Algorithm4.Algorithm 4: MLACA.
Input: The dimensions of A, the coverage range R, L=L1,L2,⋯,LN;Output: L′;1: Sets of L′=L, VV=∅, VE=∅, NVLk=∅ for any Lk∈L;2: Compute the Voronoi diagram GVV,VE and RegL′ of candidate sites on L′ by using algorithm in [32];3: for any Lk∈L′do4:  Compute NVLk based on GVV,VE and RegL′;5:  Construct GVVLk,NELk on NVLk by using algorithm in [32];6:  Compute NILk based on GVVLk,NELk;7:  ifVVLk∪NILk⊂⋃Lj∈NVLkALjthen8:   L′=L′\Lk;9:   Compute the Voronoi diagram GVV,VE of candidate sites in L′ by using algorithm in [32];10: end11: end forTheorem 24.
The time complexity of the MLACA algorithm isON2logN, where N represents the number of candidate sites in L.Proof.
According to the MLACA algorithm, we can find that the algorithm consists of three steps. Firstly, we compute the Voronoi diagram of candidate sites inL with ONlogN time by using the algorithm in [32]. Secondly, we need at most N iterations in the for loop since L=N. In each iteration, we first need at most N times to compute the set NVLk of Voronoi neighbors of Lk. Then, we need at most ONVLklogNVLk time to compute the neighbor Voronoi diagram on NVLk. Next, we need at most N times to compute NILk. We need at most another ONlogN time to update the Voronoi diagram by using the algorithm in [32] when Lk is a redundant candidate site. Therefore, we need at most ON2logN=ON∗N+NVLklogNVLk+NlogN time for the for loop since NVLk≤N.
From what has been discussed, we can verify that the time complexity of the MLACA algorithm isON2logN.


## 6.3. Algorithm for the MAPS Problem

In this subsection, we propose an approximation algorithm to solve the MAPS problem, which is called MAPSA. Similar to the MTPSA algorithm, the MAPSA algorithm consists of two phases. The first phase is to find a subsetL′⊆L of candidate sites by using Algorithm 4 such that the whole area A is covered by the coverage region of candidate sites in L′. The second phase is to find a subset C⊆S of IoT devices placed at the sites in L′ by executing Algorithm 2 such that for any point p∈A, it is observed by IoT devices in C at least T time. The detailed illustration of the algorithm is shown in Algorithm 5.Algorithm 5: MAPSA.
Input: S=s1,s2,⋯,sn, Ei for each si∈S, L=L1,L2,⋯,LN, R, T;Output: C, M;Step 1: Compute the set L′ of candidate sites to cover the whole area by executing Algorithm 4;Step 2: Compute C, M based on L′ by executing Algorithm 2,whereP=L′;Theorem 25.
The time complexity of the MAPSA algorithm isOn3+nN+N2logN, where n is the number of available IoT devices in S, and N represents the number of candidate sites in L.Proof.
Based on Theorems13 and 24, we can verify that the time complexity of the MAPSA algorithm is On3+nN+N2logN.


## 7. Simulations

In this section, we evaluate the average performance of the approximation algorithms MTPSA and MAPSA depending on simulations with several critical performance metrics under different configurations. The code of the algorithms is implemented using MATLAB 2016a. For every group of parameter settings, we create 100 instances, execute the simulations, and obtain the average results.


### 7.1. Simulations for the MTPSA Algorithm

In order to ensure that all targets can be covered by candidate sites, we use a grid to cover the detection area where the distance between neighbor grid points isR except for all grids in the boundary of the area. As an instance shown in Figure 2(a), all targets are randomly deployed on a 2000 m ×2000 m detection area and the grid points as the candidate sites are located on the area, where we set T=1000, n=2000, and R=200 m; pick the active time slots Ei of each IoT devices si∈S from range [100, 200]. After executing the algorithm MTPSA for the instance, we can verify that the number of the placed sites of IoT devices is 42, as the green nodes shown in Figure 2(b); the number of IoT devices placed at the sites is 252 and the total time consumption of all used IoT devices is 4.2072e+04.Figure 2
A coverage solution for an instance of the MTPS problem, where targets are deployed on the 2000 m×2000 m detection area.
(a)
The grid points as candidate sites(b)
The green points as placed sitesIn the following, we will evaluate how the network settings, such as the number of targetsm, the certain period of time T, the active time slots Ei for each IoT device si∈S, the coverage range R and the size of the detection area, affect the performance of the MTPSA algorithm.Firstly, we evaluate how the number of targetsm and the coverage range R affect the performance of the MTPSA algorithm when we set n=1000 and T=1000; use the interval [200, 300] to pick a uniformly distributed random active time slots Ei for each IoT device si∈S; change R to 100, 120, 140, 160, and 180 m; and vary m from 100 to 700 in the 2000 m ×2000 m detection area, as shown in Figure 3. It is observed that the total time consumption of IoT devices increases with the increasing of m, as shown in Figure 3(a). This is because the number of IoT devices that are placed at candidate sites increases as m grows and the active time slots of IoT devices are fixed, as shown in Figure 3(b). Figure 3(a) also shows that the total time consumption of the used IoT devices decreases with increasing R since the less candidate sites are used to place IoT devices as R grows, which leads to a decline in the number of IoT devices being used, as shown in Figure 3(b).Figure 3
Simulations by varyingm from 100 to 700 under different R.
(a)
Performance of MTPSA(b)
Effects ofm and RFigure4 illustrates the impact of the certain period of time T and the number of targets m on the performace of the MTPSA algorithm when we set n=2000; pick the active time slots Ei of each IoT device si∈S from [200, 300], R=100 m, m=100, 200, 300, 400, and 500; and change T from 800 to 2000 in the 2000 m×2000 m detection area. Figure 4(a) shows that the total time consumption of used IoT devices is becoming larger with increasing T, since more IoT devices are needed to be placed on candidate sites for continuously observing targets as T increases when the active time slots of IoT devices are fixed, as shown in Figure 4(b). It is also observed that the performance gap is becoming smaller with the increasing of m. This is because the increase of the number of sites placing IoT devices is becoming smaller as more and more targets are randomly deployed on the detection area, which results in a reduction of the number of IoT devices placed at the sites, as shown in Figure 4(b). We also find that the number of used IoT devices increases as T grows since each IoT device si∈S continuously works Ei time slots once it starts working.Figure 4
Results by varyingT from 800 to 2000 under different m.
(a)
Performance of MTPSA(b)
Effects ofT and mFigure5 evaluates the impact of the active time slots of IoT devices and the size of the detection area on the performance of the MTPSA algorithm when we set n=2000, R=200 m, m = 600, and T = 2000; deploy targets in the monitoring area 1500 m × 1500 m, 2000 m × 2000 m, 2500 m× 2500 m, 3000 m × 3000 m, and 3500 m × 3500 m; and assign the active time slots of each IoT device si∈S from [100, 200], [200, 300], [300, 400], [400, 500], [500, 600], [600, 700], and [700, 800], respectively. Figure 5(a) shows that the total time consumption of used IoT devices levels off when Ei<700,800 with increasing of the active time slots of IoT devices and increases as the size of the monitoring area increases. This is because when Ei<700,800, at least three IoT devices should be placed at each placement site to continuously observe target T time, which is obviously greater than T.Figure 5
Simulations by varyingEi from [100, 200] to [700, 800] under different monitoring areas.
(a)
Performance of MTPSA(b)
Effects of the size of the detection area and active time slotsEi


### 7.2. Simulations for the MAPSA Algorithm

In order to ensure that the whole area can be covered by candidate sites, we select candidate sites evenly in the monitoring area. As an instance shown in Figure6(a), given a 2000 m ×2000 m monitoring area, 100 candidate sites are located on the area and we set R = 200. The process of the MLACA algorithm is shown in Figures 6(b)–6(d). Firstly, we construct the Voronoi diagram of the candidate sites in L, as shown in Figure 6(b). Secondly, we find all redundant candidate sites from L such that all remaining candidate sites can cover the whole area, as the red points shown in Figure 6(c). Finally, we can obtain the placed sites of IoT devices, as shown in Figure 6(d).Figure 6
The executing process of the MLACA.
(a)
The full candidate sites inL(b)
The Voronoi diagram of candidate sites inL(c)
The redundant candidate sites identified by MLACA(d)
The placed sites of IoT devices obtained by MLACAIn the following, we will evaluate how the network settings, the active time slots, and the size of the detection area affect the performance of the MAPSA.Figure7 evaluates the impact of the active time slots of IoT devices and the size of the detection area on the performance of the MAPSA algorithm when we set n=3000, R= 200 m, and T = 2000; deploy targets in the monitoring area 1500 m × 1500 m, 2000 m × 2000 m, 2500 m × 2500 m, 3000 m × 3000 m, and 3500 m × 3500 m; and assign the active time slots of each IoT device si∈S from [100, 200], [200, 300], [300, 400], [400, 500], [500, 600], [600, 700], and [700, 800], respectively. Figure 7(a) shows that the total time consumption of used IoT devices increases with the increase of the active time slots of IoT devices when Ei<400,500. This is because when Ei<400,500, at least five IoT devices should be placed at each placement site to continuously observe the area T time and their total energy consumption increases with Ei increasing. When Ei>400,500, the total time consumption decreases with the increasing of Ei, since as Ei grows, the less devices are needed for working a certain time. Figure 7(b) shows that the number of used devices decreases with the increasing of Ei for each device. We also find that the number of placed devices decreases as the size of area decreases.Figure 7
Performance of MAPSA under different monitoring areas.
(a)
Performance of MLACA(b)
Effects of active time slotsEi


## 7.1. Simulations for the MTPSA Algorithm

In order to ensure that all targets can be covered by candidate sites, we use a grid to cover the detection area where the distance between neighbor grid points isR except for all grids in the boundary of the area. As an instance shown in Figure 2(a), all targets are randomly deployed on a 2000 m ×2000 m detection area and the grid points as the candidate sites are located on the area, where we set T=1000, n=2000, and R=200 m; pick the active time slots Ei of each IoT devices si∈S from range [100, 200]. After executing the algorithm MTPSA for the instance, we can verify that the number of the placed sites of IoT devices is 42, as the green nodes shown in Figure 2(b); the number of IoT devices placed at the sites is 252 and the total time consumption of all used IoT devices is 4.2072e+04.Figure 2
A coverage solution for an instance of the MTPS problem, where targets are deployed on the 2000 m×2000 m detection area.
(a)
The grid points as candidate sites(b)
The green points as placed sitesIn the following, we will evaluate how the network settings, such as the number of targetsm, the certain period of time T, the active time slots Ei for each IoT device si∈S, the coverage range R and the size of the detection area, affect the performance of the MTPSA algorithm.Firstly, we evaluate how the number of targetsm and the coverage range R affect the performance of the MTPSA algorithm when we set n=1000 and T=1000; use the interval [200, 300] to pick a uniformly distributed random active time slots Ei for each IoT device si∈S; change R to 100, 120, 140, 160, and 180 m; and vary m from 100 to 700 in the 2000 m ×2000 m detection area, as shown in Figure 3. It is observed that the total time consumption of IoT devices increases with the increasing of m, as shown in Figure 3(a). This is because the number of IoT devices that are placed at candidate sites increases as m grows and the active time slots of IoT devices are fixed, as shown in Figure 3(b). Figure 3(a) also shows that the total time consumption of the used IoT devices decreases with increasing R since the less candidate sites are used to place IoT devices as R grows, which leads to a decline in the number of IoT devices being used, as shown in Figure 3(b).Figure 3
Simulations by varyingm from 100 to 700 under different R.
(a)
Performance of MTPSA(b)
Effects ofm and RFigure4 illustrates the impact of the certain period of time T and the number of targets m on the performace of the MTPSA algorithm when we set n=2000; pick the active time slots Ei of each IoT device si∈S from [200, 300], R=100 m, m=100, 200, 300, 400, and 500; and change T from 800 to 2000 in the 2000 m×2000 m detection area. Figure 4(a) shows that the total time consumption of used IoT devices is becoming larger with increasing T, since more IoT devices are needed to be placed on candidate sites for continuously observing targets as T increases when the active time slots of IoT devices are fixed, as shown in Figure 4(b). It is also observed that the performance gap is becoming smaller with the increasing of m. This is because the increase of the number of sites placing IoT devices is becoming smaller as more and more targets are randomly deployed on the detection area, which results in a reduction of the number of IoT devices placed at the sites, as shown in Figure 4(b). We also find that the number of used IoT devices increases as T grows since each IoT device si∈S continuously works Ei time slots once it starts working.Figure 4
Results by varyingT from 800 to 2000 under different m.
(a)
Performance of MTPSA(b)
Effects ofT and mFigure5 evaluates the impact of the active time slots of IoT devices and the size of the detection area on the performance of the MTPSA algorithm when we set n=2000, R=200 m, m = 600, and T = 2000; deploy targets in the monitoring area 1500 m × 1500 m, 2000 m × 2000 m, 2500 m× 2500 m, 3000 m × 3000 m, and 3500 m × 3500 m; and assign the active time slots of each IoT device si∈S from [100, 200], [200, 300], [300, 400], [400, 500], [500, 600], [600, 700], and [700, 800], respectively. Figure 5(a) shows that the total time consumption of used IoT devices levels off when Ei<700,800 with increasing of the active time slots of IoT devices and increases as the size of the monitoring area increases. This is because when Ei<700,800, at least three IoT devices should be placed at each placement site to continuously observe target T time, which is obviously greater than T.Figure 5
Simulations by varyingEi from [100, 200] to [700, 800] under different monitoring areas.
(a)
Performance of MTPSA(b)
Effects of the size of the detection area and active time slotsEi


## 7.2. Simulations for the MAPSA Algorithm

In order to ensure that the whole area can be covered by candidate sites, we select candidate sites evenly in the monitoring area. As an instance shown in Figure6(a), given a 2000 m ×2000 m monitoring area, 100 candidate sites are located on the area and we set R = 200. The process of the MLACA algorithm is shown in Figures 6(b)–6(d). Firstly, we construct the Voronoi diagram of the candidate sites in L, as shown in Figure 6(b). Secondly, we find all redundant candidate sites from L such that all remaining candidate sites can cover the whole area, as the red points shown in Figure 6(c). Finally, we can obtain the placed sites of IoT devices, as shown in Figure 6(d).Figure 6
The executing process of the MLACA.
(a)
The full candidate sites inL(b)
The Voronoi diagram of candidate sites inL(c)
The redundant candidate sites identified by MLACA(d)
The placed sites of IoT devices obtained by MLACAIn the following, we will evaluate how the network settings, the active time slots, and the size of the detection area affect the performance of the MAPSA.Figure7 evaluates the impact of the active time slots of IoT devices and the size of the detection area on the performance of the MAPSA algorithm when we set n=3000, R= 200 m, and T = 2000; deploy targets in the monitoring area 1500 m × 1500 m, 2000 m × 2000 m, 2500 m × 2500 m, 3000 m × 3000 m, and 3500 m × 3500 m; and assign the active time slots of each IoT device si∈S from [100, 200], [200, 300], [300, 400], [400, 500], [500, 600], [600, 700], and [700, 800], respectively. Figure 7(a) shows that the total time consumption of used IoT devices increases with the increase of the active time slots of IoT devices when Ei<400,500. This is because when Ei<400,500, at least five IoT devices should be placed at each placement site to continuously observe the area T time and their total energy consumption increases with Ei increasing. When Ei>400,500, the total time consumption decreases with the increasing of Ei, since as Ei grows, the less devices are needed for working a certain time. Figure 7(b) shows that the number of used devices decreases with the increasing of Ei for each device. We also find that the number of placed devices decreases as the size of area decreases.Figure 7
Performance of MAPSA under different monitoring areas.
(a)
Performance of MLACA(b)
Effects of active time slotsEi


## 8. Conclusion

In this paper, we investigate the problems minimum energy consumption of IoT devices for target coverage through placement and scheduling (MTPS) and minimum energy consumption of IoT devices for area coverage through placement and scheduling (MAPS), which focuses on finding the placement locations of IoT devices from candidate sites and scheduling them to cover all targets or the whole monitoring area such that all targets or the entire area are (or is) continuously observed for a certain period of time and the total energy consumption of the placed IoT devices is minimized. We first propose the mathematical models for the proposed problems and prove that they are NP-hard. Then, we propose an approximation algorithm for each of them. Finally, extensive simulation results are shown to further verify the performance of the proposed algorithm.



---

*Source: 5921181-2021-09-14.xml*