Deployment optimization of laser chargers in self-organizing power transfer internet of things

Internet of Things (IoT) is the network of physical objects, encompassing sensors, vehicles, instruments, and so on. This interconnected web enables these devices to gather and exchange data^[1]. Boasting attributes like low cost, convenient deployment, and self-organization of IoT Devices (IoTDs), IoT networks have been applied in various fields, including agricultural production, smart cities, and environmental monitoring^[2−4], etc.

While IoTDs have clear advantages, their practical applications also face significant challenges. Specifically, IoTDs' limited battery capacity restricts their ability to operate sustainably. The rapid and uneven energy depletion of IoTDs significantly hinders the widespread practical utilization of IoT networks. To address this limitation, one of the effective solutions is to deploy Laser Static Chargers (LSCs) to power IoTDs by using laser charging, a kind of Wireless Power Transfer (WPT) technique^[5−7]. However, deploying LSCs to cover all IoTDs to supply sufficient energy will consume enormous costs. Motivated by the above analysis, to prolong the lifetime of IoT while reducing the deployment costs of LSCs, we first propose a novel network framework called Self-organizing Power Transfer Internet of Things (SPTIoT), where each IoTD is equipped with a laser transmission module and a laser reception module, enabling laser energy transferred between IoTDs, as shown in Fig. 1. The SPTIoT network consists of several IoT devices with rechargeable batteries. All IoTDs form a self-organizing power transfer network by transmitting laser energy to each other in their neighbourhood. In the network, each IoTD can be used both as a receiver to receive energy from other IoTDs within its neighbourhood and as a charger to charge neighbour IoTDs. As a receiver, the laser reception module of the IoTD receives laser energy, converts the laser energy into electrical energy, and stores it in rechargeable batteries. As a charger, the laser transmission module of the IoTD converts its electrical energy into laser energy and transmits it to other IoTDs. Unlike general IoTs, the SPTIoT distinguishes itself by forming a self-organizing power transfer network, where IoTDs with lower energy can be charged by the IoTDs within their neighbourhood. This innovative architecture not only helps balance the energy distribution across IoTDs and extend the overall lifespan of the network but also significantly reduces the number of LSCs required, because covering a portion of IoTDs can meet the energy requirements of all IoTDs in SPTIoT.

Figure 1. 

Architecture of the SPTIoT network.

Then, based on the SPTIoT, comprehensively considering the energy requirements of IoTDs and deployment costs of LSCs, we study the Minimizing Laser Chargers Coverage (MLCC) problem. The objective of the problem is to minimize the number of LSCs deployed in SPTIoT while ensuring that all IoTDs can work continuously.

The contributions of this paper can be summarized as follows:

(1) We propose a novel network architecture called the Self-organizing Power Transfer Internet of Things (SPTIoT), allowing energy transfer between IoTDs. We propose the concept of self-organizing wireless charging network for the first time;

(2) We first identify the SPTIoT with LSCs (SPTIoT-LSC) network model, where LSCs are deployed in the network to replenish energy for IoTDs. Based on SPTIoT-LSC, we study the Minimizing Laser Chargers Coverage (MLCC) problem, whose objective is to minimize the number of LSCs deployed in the network while enabling all IoTDs to work continuously. Then we prove that the MLCC problem is NP-hard;

(3) To solve the MLCC problem, we first propose a sub-problem, Charging Scheduling Problem (CSP), to maximize the working time of IoTDs with the given LSCs and their positions. Then the Layered Charging Scheduling Strategy (LCSS) algorithm is proposed to solve the CSP problem. After that, the Deploy Chargers based on Multi-agent deep deterministic policy gradient (DCM) algorithm is employed to deploy the given LSCs based on the CSP problem. Finally, we propose an approximation algorithm MLCC Algorithm (MLCCA) to solve the MLCC problem based on the above two algorithms;

(4) Extensive simulations are presented to demonstrate the efficiency of the proposed algorithm for the MLCC problem as well as the superiority of the SPTIoT compared with general IoT.

This section discusses relevant research and puts forward the differences between previous literature and this paper. We classify the investigated problems into two types: wireless charging in IoT, and deployment optimization of static chargers.

Wireless charging in IoT

Commonly used wireless charging methods include magnetic resonance coupling, solar charging, laser charging, etc. In the study by Xie et al.^[8], they utilized a wireless charging vehicle with the magnetic resonant coupling charging method to provide periodic recharging for sensors in a wireless sensor network. However, magnetic resonant coupling technology suffers from limited charging distances, facing the problems of high deployment cost and low charging efficiency. In previous studies^[9−11], solar charging was used to prolong the lifetime of IoTDs. However, the solar charging method is weather-dependent, and in bad weather or at night, IoTDs cannot be charged. Laser charging, in contrast, offers a reliable and stable energy supplyment, less susceptible to weather variations. The attenuation of laser beam transmission in air is very small^[12], making it an effective long-distance charging method. In previous studies^[13,14], laser charging technology was used to replenish energy for electric vehicles, overcoming the drawbacks including long charging times and short charging ranges. In a study by Fu et al.^[7], an Unmanned Aerial Vehicle (UAV) was utilized to collect data from IoTDs and charge IoTDs using laser charging technology. By optimizing the UAV's trajectory, they maximized its residual energy while meeting all IoTDs' energy requirements. In the research of Zhang et al.^[15], they used a laser-beamed WPT technology and presented a multitier tile grid-based spatial structure to charge Aerial User Equipment (AUE) in a high-altitude platform.

Deployment optimization of static chargers

A large body of literature is dedicated to minimizing the deployment cost of static chargers in IoT networks while meeting the energy requirements of IoT devices. Liao & Jiang^[16] studied the problem: minimizing the number of chargers deployed on grid points at a fixed height to make the wireless rechargeable sensor network sustainable. And then they presented two greedy algorithms to solve it. In the research of Chen & Jiang^[17], a Particle Swarm Charger Deployment (PSCD) algorithm was proposed to deploy chargers by using the Particle Swarm Optimization (PSO) method. The results indicated its superiority compared with two greedy algorithms proposed by Liao & Jiang^[16]. In the study by Chien et al.^[18], the authors presented a layoff algorithm combining the Simulated Annealing-based (SA) method to optimize the chargers' positions in the WRSN. The proposed algorithm can reduce the number of chargers efficiently according to their simulation results. In the research of Li et al.^[19], they studied how to efficiently deploy wireless static chargers in UAV networks. They presented a binary integer programming method to determine the minimum number of wireless static chargers as well as the location of each charger so that the energy requirements of UAVs are satisfied during flight. Liu et al.^[20] investigated the problem of charging nodes with uncertain mobility by static chargers. They proposed a genetic-algorithm-based multi-objective optimization scheme to address the charger deployment problem. Lin et al.^[21] proposed a hybrid search and removal strategy to discover the minimum number of chargers required to cover all sensor nodes. You et al.^[22] studied a fundamental issue of wireless charger placement with obstacles and proposed a greedy algorithm for placing chargers. In summary, there are many articles studying the optimization of static charger deployment. However, the aforementioned studies neglected the energy transfer between devices, thereby necessitating the deployment of more chargers to ensure comprehensive coverage for IoTDs, which is more costly.

It is clear from previous discussions that there are many studies on wireless charging in IoT and the deployment optimization of static chargers. However, they have not studied the energy transfer between IoTDs. Inspired by the above research, this paper, investigates the Minimize Laser Chargers Coverage problem in SPTIoT networks by considering laser charging technology, deployment optimization of chargers, and energy transfer between IoTDs, to minimize the number of LSCs deployed in SPTIoT and satisfy the energy requirements of all IoTDs.

In this section, we first introduce the network model. Then, we give the laser charging model for charging IoTDs. Finally, the formal definition of our problem is presented.

Network model

In this paper, we consider the network architecture of SPTIoT with Laser Static Chargers (SPTIoT-LSC), where a set of n IoTDs S = {s₁, s₂, ···, s_n} is randomly located at a two-dimensional square detection area $ A\subseteq {\mathfrak{R}}^{2} $ for a monitoring mission and several LSCs are deployed into the area to replenish energy for IoTDs. In the network, each IoTD $ {s}_{i}\in S $ has a two-dimensional coordinate (x_i, y_i). All IoTDs have the uniform battery capacity E_M and energy threshold E_T. The IoTD stops working when its remaining energy is less than E_T. Since IoTDs are in different positions and may take different tasks in the mission, each IoTD $ {s}_{i}\in S $ has its unique energy consumption rate δ_i.

To satisfy the charging requirements of the network, multiple LSCs are deployed in the detection area to replenish energy for IoTDs, which can be collected in the set C = {c₁, c₂, ···, c_m}. For simplicity, we assume that IoTDs and LSCs have the same laser transmission distance R_c. For any IoTD $ {s}_{i}\in S $, it can be charged by $ {c}_{j}\in C $ if and only if $ {d}_{i{{,}}j}^{c}\le {R}_{c} $, where $ {d}_{i{{,}}j}^{c} $ denotes the Euclidean distance between s_i and c_j. Similarly, any IoTD $ {s}_{i}\in S $ can be charged by $ {s}_{k}\in S $ if and only if $ {d}_{i{{,}}k}^{s}\le {R}_{c} $, where $ {d}_{i{{,}}k}^{s} $ denotes the Euclidean distance between s_i and s_k. Let $ {\mathcal{N}}_{i}^{s}=\left\{{s}_{k}\right|k\ne i{{,}}{d}_{i{{,}}k}^{s}\le {R}_{c}\} $ represent the set of neighbor IoTDs of $ {s}_{i}\in S $.

Furthermore, let T_w represent the working period during which all IoTDs must remain continuously operational in SPTIoT-LSC. We discretize T_w evenly into $ \mathrm{\Gamma } $ time slots, with each slot having a duration of $ l=\dfrac{{T}_{w}}{\mathrm{\Gamma }} $. The set of time slots is denoted as $ \mathcal{T}=\{\mathrm{1{{,}\;}2}{{,}}\;\cdots{{,}}\;\mathrm{\Gamma }\} $. For any IoTD $ {s}_{i}\in S $, we utilize $ {E}_{i}^{r}\left(\tau \right) $ to signify its remaining energy at time slot $ \tau $, with the initial energy set as $ {E}_{i}^{r}\left(0\right)={E}_{M} $.

Laser charging model

We consider the one-on-one laser charging model. We use a linear laser energy harvesting model^[23,24] with efficiency ω to derive the energy transmission link from the c_j to s_i. The power of s_i received from c_j can be expressed as:

where, P_c is the source power of LSC, δ_s represents the the power splitting factor to separate the energy transfer link and communication link, $ {\eta }_{el} $ is the electricity-to-laser conversion efficiency, A_c is the area of the charging panel of each IoTD, $ \chi $ represents the optical efficiency of the combined transmission-receiver, α is the laser attenuation coefficient, $ D $ denotes the size of the initial laser beam, $ {\mathrm{\Delta }}_{\theta } $ represents the angular expansion of the laser beam.

Similar to the laser charging model from LSC to IoTD, for any pair of $ {s}_{i}\in S $ and $ {s}_{k}\in S $, we can obtain the power of s_i received from s_k as:

where, P_s is the source power of IoTD.

Problem definition

In this subsection, we investigate the Minimizing Laser Chargers Coverage (MLCC) problem, whose goal is to minimize the number of LSCs deployed into the detection area while ensuring the energy of each IoTD in S is greater than or equal to E_T during the working period T_w.

We first define the binary variables $ {a}_{i}^{k}\left(\tau \right) $ and $ {b}_{i}^{j}\left(\tau \right) $ as follows.

Then, we give the expression for the remaining energy of $ {s}_{i}\in S $ at any time slot $ \tau > 0 $:

Finally, the MLCC problem can be mathematically formulated as:

s.t.

where, the constraint C1 ensures the remaining energy of each IoTD is upper than or equal to E_T at any time slot $ \tau \in \mathcal{T} $, the constraint C2 limits that one IoTD can only be charged by one IoTD or one LSC at each time slot $ \tau \in \mathcal{T} $, the constraint C3 states one LSC can only charge one IoTD at every time slot $ \tau \in \mathcal{T} $ and the constraint C4 guarantees one IoTD can only charge another one IoTD at each time slot $ \tau \in \mathcal{T} $.

Theorem 1. The MLCC problem is NP-hard.

Proof. We consider a special case of the MLCC (scMLCC) problem with four conditions: (1) P_s = 0; (2) P_c = +∞; (3) for each $ {s}_{i}\in S $, E_M − δ_iT_w < E_T; (4) LSCs can only be deployed at the positions that coincide with IoTDs. Based on the above four conditions, the objective of the scMLCC problem is to minimize the number of LSCs, which can only be deployed at the locations coinciding with IoTDs, for coveraging all IoTDs to satisfy their charging requirements.

The decision version of the scMLCC problem, called K-scMLCC, is that given a set of IoTDs S and a positive integer K, does there exists a positive integer m (m ≤ K) such that m LSCs deployed at the locations coinciding with m IoTDs can cover all IoTDs?

To prove the scMLCC problem is NP-hard, we use the Minimum Dominating Set (MDS) problem for reduction, which has proven NP-hard^[25]. The decision version of MDS, called J-MDS, is defined as: given an undirected graph G(V, E) and a positive integer J, does there exists a subset $ {V}^{{'}}\subseteq V $ and $ \left|{V'}\right|\le J $ satisfying that for each node $ u\in V\setminus {V'} $, there must be at least one node $ v\in {V'} $ such that the edge $ \left(u{{,}}v\right)\in E $?

For given an instance of J-MDS, with G(V,E), V = {v₁, ···, v_n} and a positive integer J, we construct the instance of K-scMLCC problem as follows:

● K = J;

● |S| = |V|;

● each $ {s}_{i}\in S $ corresponds to node $ {v}_{i}\in V $ on graph G;

● any pair of s_i, $ {s}_{j}\in S $ are neighbors iff edge $ ({v}_{i}{{,}}{v}_{j})\in E $.

In the following, we will prove that J-MDS problem has a YES answer if K-scMLCC has a YES answer.

'Sufficiency'. Suppose m(m ≤ K) LSCs, whose locations coincide with$ m $ IoTDs, can coverage all IoTDs. Let $ {S'}\in S $ be the set of these m IoTDs and $ {V'}\subseteq V $ be the set of nodes on graph G corresponding to IoTDs in S'. Apparently, the subset $ {V'}\subseteq V $ is a dominating set in G and |V'| = |S'| = m ≤ K = J.

'Necessity'. Suppose $ {V}^{{'}}\subseteq V $ is the dominating set in G and $ \left|{V}^{{'}}\right|\le J $. Let $ {S}^{{'}}\subseteq S $ be the set of IoTDs corresponding to nodes in $ {V}^{{'}} $ on graph $ G $. Apparently, any $ {s}_{i}\in S\setminus {S}^{{'}} $ has at least one neighbor in S'. m(m = |S'|) LSCs deployed at the locations coinciding with the IoTDs in S' can coverage all IoTDs and m = |S '| = |V '| ≤ J = K.

Therefore, the scMLCC problem is NP-hard. Since the scMLCC problem is a special case of the MLCC problem, the MLCC problem is also NP-hard.

In this section, we propose an approximation algorithm called MLCC Algorithm (MLCCA) to solve the MLCC problem.

Before introducing the MLCCA algorithm, we first study a sub-problem, the Charging Scheduling Problem (CSP), as shown in Definition 1, whose goal aims to provide a charging scheduling strategy of LSCs and IoTDs to maximize the working time of all IoTDs based on the given number and positions of LSCs. Then, we design the Layered Charging Scheduling Strategy (LCSS) algorithm to solve the sub-problem, which is a subroutine of the MLCCA.

The MLCCA algorithm consists of two steps. Firstly, we divide the monitoring area A evenly into L × L grids. Secondly, we propose the Deploy Chargers based on Multi-agent deep deterministic policy gradient (DCM) algorithm to deploy the LSCs into the monitoring area A to charge the IoTDs by using the Multi-Agent Deep Reinforcement Learning (MADRL) method, where the output of the LCSS algorithm is utilized as one of the metrics of the reward function in the DCM algorithm.

In the following, we first give a detailed description of the CSP problem.

Definition 1 (CSP): Given a set S = {s₁, s₂, ···, s_n} of n IoTDs, a set C = {c₁, c₂, ···, c_m} of m LSCs, a set $ \mathcal{T}=\{\mathrm{1{{, }} \;2}{{, }} \;\cdots {{, }}\; \Gamma \} $ of time slots, working period T_w, the objective of Charging Scheduling Problem (CSP) is to maximize the working time T_c of IoTDs such that the remaining energy of each IoTD is greater than or equal to E_T at every time slot $ \tau \in [1{{,}}\dfrac{{T}_{c}}{l}] $.

The mathematical formulation of the CSP problem can be expressed as:

s.t.

where, the contsraint C1 states that T_c is less than or equal to the working periodT_w, the constraint C2 ensures the remaining energy of each IoTD is greater than or equal to E_T at any time slot $ \tau \in [1{{,}}\dfrac{{T}_{c}}{l}] $, the constraint C3 limits that any one IoTD can only be charged by one IoTD or one LSC at each time slot $ \tau \in [1{{,}}\dfrac{{T}_{c}}{l}] $, the constraint C4 states one LSC can only charge one IoTD at every time slot $ \tau \in [1{{,}}\dfrac{{T}_{c}}{l}] $, and the constraint C5 guarantees one IoTD can only charge another one IoTD at each time slot $ \tau \in [1{{,}}\dfrac{{T}_{c}}{l}] $.

Algorithm for the CSP problem

In this subsection, we give a detailed description of the Layered Charging Scheduling Strategy (LCSS) algorithm, as shown in Algorithm 1.

Before describing the algorithm, we first introduce some notations. Let $ l{y}_{i} $ denote the minimum number of hops from the nearest LSC to s_i, which is named the layer number of s_i. Let $ {S}_{o}=\{{s}_{{\rho }_{1}}{{, }}\; {s}_{{\rho }_{2}}{{, }} \;\cdots {{, }} \;{s}_{{\rho }_{n}}\} $ be an ordered set of IoTDs arranged in ascending order according to their remaining energy. If more than one IoTD has the same remaining energy, then sort them in descending order by their layer numbers. If more than one IoTD has the same layer number, then sort them in ascending order by their subscript numbers.

The LCSS algorithm consists of four steps.

In the first step, we initialize T_c = 0.

In the second step, for each $ {s}_{i}\in S $, we compute the set $ {\mathcal{N}}_{i}^{c}=\left\{{c}_{j}\right|{d}_{i{{,}}j}^{c}\le {R}_{c}\} $ of its neighbor LSCs.

In the third step, we compute $ l{y}_{i} $ for each $ {s}_{i}\in S $, where the computation process is that for each $ {c}_{j}\in C $, we use the Dijkstra algorithm to compute the hops from c_j to each IoTD, and then for each $ {s}_{i}\in S $, we select the smallest one as $ l{y}_{i} $ from all LSCs to s_i.

In the fourth step, we schedule the charging process in the network, i.e., for any time slot $ \tau $, we update $ {E}_{i}^{r}\left(\tau \right) $ for each $ {s}_{i}\in S $ according to equation (5). At each time slot $ 1\le \tau \le \mathrm{\Gamma } $, the following substeps are executed:

● For each $ {s}_{i}\in S $, update the remaining energy $ {E}_{i}^{r}\left(\tau \right)={E}_{i}^{r}(\tau - 1)-{\delta }_{i}l $.

● We obtain $ {S}_{o}=\{{s}_{{\rho }_{1}}{{,}}\cdots {{,}}{s}_{{\rho }_{n}}\} $ by sorting all IoTDs.

● For each $ 1\le i\le n $, we execute the following steps to find the LSC or IoTD that can supply energy for $ {s}_{{\rho }_{i}} $ to charge $ {s}_{{\rho }_{i}} $. Firstly, we compute the set $ {C}_{{\rho }_{i}}=\left\{{c}_{j}\right|{c}_{j}\in {\mathcal{N}}_{{\rho }_{i}}^{c}\wedge {\mathrm{\Sigma }}_{q=1}^{n}{b}_{q}^{j}\left(\tau \right)=0\} $ of the LSCs that can charge $ {s}_{{\rho }_{i}} $ and the set $ {S}_{{\rho }_{i}}^{u}=\left\{{s}_{k}\right|{s}_{k}\in {\mathcal{N}}_{{\rho }_{i}}^{s}\wedge l{y}_{k}= l{y}_{{\rho }_{i}}-1\wedge {\mathrm{\Sigma }}_{q=1}^{n}{a}_{q}^{k}\left(\tau \right)=0\wedge {E}_{k}^{r}\left(\tau \right)-{P}_{s}l > {E}_{{\rho }_{i}}^{r}\left(\tau \right)\} $ of the IoTDs with layer number equal to $ l{y}_{{\rho }_{i}}-1 $ that can charge $ {s}_{{\rho }_{i}} $ and the set $ {S}_{{\rho }_{i}}^{e}= \left\{{s}_{k}\right|{s}_{k}\in{\mathcal{N}}_{{\rho }_{i}}^{s}\wedge l{y}_{k}=l{y}_{{\rho }_{i}}\wedge {\mathrm{\Sigma }}_{q=1}^{n}{a}_{q}^{k}\left(\tau \right)=0\wedge {E}_{k}^{r}\left(\tau \right)-{P}_{s}l > {E}_{{\rho }_{i}}^{r}\left(\tau \right)\} $ of the IoTDs with layer number equal to $ l{y}_{{\rho }_{i}} $ that can charge $ {s}_{{\rho }_{i}} $. Secondly, we find the LSC or IoTD to charge $ {s}_{{\rho }_{i}} $ in the light of three cases: (1) $ {C}_{{\rho }_{i}}\ne \mathrm{\varnothing } $, (2) $ {S}_{{\rho }_{i}}^{u}\ne \mathrm{\varnothing }\wedge {C}_{{\rho }_{i}}==\mathrm{\varnothing } $, and (3) $ {S}_{{\rho }_{i}}^{e}\ne \mathrm{\varnothing }\wedge {C}_{{\rho }_{i}}==\mathrm{\varnothing }\wedge {S}_{{\rho }_{i}}^{u}==\mathrm{\varnothing } $.

(1) $ {C}_{{\rho }_{i}}\ne \mathrm{\varnothing } $.

Let $ {c}_{v}=\mathrm{arg}min\left\{{d}_{{\rho }_{i}{{,}}v}^{c}\right|{c}_{v}\in {C}_{{\rho }_{i}}\} $. Update $ {b}_{{\rho }_{i}}^{v}\left(\tau \right)=1 $, $ {E}_{{\rho }_{i}}^{r}\left(\tau \right)=min\{{E}_{M}{{,}} {E}_{{\rho }_{i}}^{r}(\tau )+{P}_{c}^{v{{,}}{\rho }_{i}}l\} $.

(2) $ {S}_{{\rho }_{i}}^{u}\ne \mathrm{\varnothing }\wedge {C}_{{\rho }_{i}}==\mathrm{\varnothing } $.

Let $ {s}_{v}=\mathrm{arg}max\left\{{E}_{v}^{r}\right(\tau \left)\right|{s}_{v}\in {S}_{{\rho }_{i}}^{u}\} $. Update $ {a}_{{\rho }_{i}}^{v}\left(\tau \right)=1 $, $ {E}_{{\rho }_{i}}^{r}\left(\tau \right)= {E}_{{\rho }_{i}}^{r} \cdot \left(\tau \right)+ {P}_{s}^{v{{,}}{\rho }_{i}}l $ and $ {E}_{v}^{r}\left(\tau \right)={E}_{v}^{r}\left(\tau \right)-{P}_{s}l $.

(3) $ {S}_{{\rho }_{i}}^{e}\ne \mathrm{\varnothing }\wedge {C}_{{\rho }_{i}}==\mathrm{\varnothing }\wedge {S}_{{\rho }_{i}}^{u}==\mathrm{\varnothing } $.

Let $ {s}_{v}=\mathrm{arg}max\left\{{E}_{v}^{r}\right(\tau \left)\right|{s}_{v}\in {S}_{{\rho }_{i}}^{e}\} $. Update $ {a}_{{\rho }_{i}}^{v}\left(\tau \right)=1 $, $ {E}_{{\rho }_{i}}^{r}\left(\tau \right)={E}_{{\rho }_{i}}^{r}\cdot \left(\tau \right)+{P}_{s}^{v{{,}}{\rho }_{i}}l $ and $ {E}_{v}^{r}\left(\tau \right)={E}_{v}^{r}\left(\tau \right)-{P}_{s}l $.

Thirdly, update $ {S}_{o}={S}_{o}\setminus \left\{{s}_{{\rho }_{i}}\right\} $ and re-sort $ {S}_{o}=\{{s}_{{\rho }_{i+1}}{{,}}{s}_{{\rho }_{i+2}}{{,}}\cdots {{,}}{s}_{{\rho }_{n}}\} $.

● If $ min\left\{{E}_{i}^{r}\right(\tau \left)\right|1\le i\le n\} < {E}_{T} $, then jump out of the loop, otherwise, let $ {T}_{c}=l\tau $.

Finally, we can obtain the value of T_c.

Theorem 2. Time complexity of the LCSS algorithm is $ O(\mathrm{\Gamma }{n}^{2}+m{n}^{2}) $.

Proof. The primary time complexity of the LCSS algorithm involves the following calculations:

Firstly, the computation of $ {\mathcal{N}}_{i}^{c} $ for each $ {s}_{i}\in S $ necessitates a running time of O(m). Consequently, the overall complexity of computing $ {\mathcal{N}}_{i}^{c} $ across all $ {s}_{i}\in S $ amounts to O(mn).

Secondly, we repeatedly apply the Dijkstra algorithm $ m $ times to compute the minimum hops from each $ {c}_{j}\in C $ to each IoTD $ {s}_{i}\in S $, which contributes a complexity of O(mn²).

Thirdly, we need $ \mathrm{\Gamma } $ iterations to update $ {E}_{i}^{r}\left(\tau \right) $ for each $ {s}_{i}\in S $ at any time slot $ 1\le \tau \le \mathrm{\Gamma } $. In the interior of the loop, first, we need O(nlogn) to obtain the ordered set S_o. Second, for any 1 ≤ i ≤ n, the computation of $ {C}_{{\rho }_{i}} $, $ {S}_{{\rho }_{i}}^{u} $ and $ {S}_{{\rho }_{i}}^{e} $ incurs a complexity of O(n(g_c + 2g_s)), where $ {g}_{c}=max\left\{\right|{\mathcal{N}}_{{\rho }_{i}}^{c}\left|\right|1\le i\le n\} $ and $ {g}_{s}= max\left\{\right|{\mathcal{N}}_{{\rho }_{i}}^{s}\left|\right|1\le i\le n\} $. Third, for any 1 ≤ i ≤ n, $ {s}_{{\rho }_{i}} $ is removed from S_o and S_o is re-sorted. Since only when $ {s}_{{\rho }_{i}} $ is charged by another IoTD s_v, we need to re-sort S_o by moving s_v to the correct position in S_o according to its remaining energy, the re-sorting process requires at most n steps and the time complexity is O(n²).

Taken together, we can conclude that the time complexity of the LCSS algorithm is $ O(mn+mn^2+\mathrm{\Gamma}n(g_c+2g_s)+\mathrm{\Gamma}nlogn+\mathrm{\Gamma}n^2)= O(mn^2+\mathrm{\Gamma}n^2) $, since g_c ≤ n and g_s ≤ n.

Markov game formulation for deploying LSCs

Given m LSCs and L × L grids, we hope to deploy these LSCs into optimal grids of the detection area such that LSCs can serve IoTDs more effectively and IoTDs can work for a longer period. To this end, we formulate the deployment process of LSCs as a discrete-time Markov Game^[26], employing the MADRL method to find a solution.

We utilize the tuple $ (\mathcal{S}{{,}}\mathcal{A}{{,}}\mathcal{R}{{,}}\mathcal{P}{{,}}\gamma ) $ to represent the Markov Game for LSC deployment, where each LSC functions as an agent. $ \mathcal{S} $ is the global state space of the environment, containing the locations of all IoTDs and LSCs. In the initial state, m LSCs are placed in the center of the intermediate grid, which is the grid in row $ \lceil \dfrac{L}{2}\rceil $ and column $ \lceil \dfrac{L}{2}\rceil $.The set of joint actions $ \mathcal{A} $ comprises the potential actions of all agents. The reward functions of agents are captured in $ \mathcal{R} $. $ \mathcal{P} $ is the state transition probability from the current state to the next state, and $ \gamma \in \left[\mathrm{0{{,}}1}\right] $ is the discount factor. Additionally, due to the partial observability of the Markov Game^[27], agents can only observe local information from the environment. We use observation space $ \mathcal{O} $ to represent the set of local information observed by agents.

(1) Time Steps

We set t = 1···T as the time steps of each episode in MADRL. Each episode has T time steps, and at every time step, each agent takes action to change its position by transferring to one of the adjacent grids. After T steps, the final deployment of LSCs is obtained. We set T = L to ensure that each agent can reach any grid in the area within T time steps.

(2) Observation Space $ \mathcal{O} $

We set $ {\mathbf{o}}^{\mathbf{t}}=\{{o}_{1}^{t}{{,}}\cdots {{,}}{o}_{m}^{t}\} $ to denote the joint observations of all agents at time step t. Since the IoTDs are placed beforehand and their positions no longer change, each agent obtains their location information in advance. Hence, the observation space $ {o}_{j}^{t} $ of j-th agent at step t is denoted as $ {o}_{j}^{t}=\left\{\right({x}_{j}^{t}{{,}}{y}_{j}^{t}){{,}}\{({x}_{i}{{,}}{y}_{i})|{s}_{i}\in S\}\} $, where $({x}_{j}^{t}{{,}}{y}_{j}^{t}) $ denotes the current coordinate of j-th agent at time step t.

(3) Action Space $ \mathcal{A} $

We set $ {\mathbf{a}}^{\mathbf{t}}=\{{a}_{1}^{t}{{, }}\cdots {{, }} {a}_{m}^{t}\} $ to denote the joint actions of all agents at time step t. Each agent can move to the center of one adjacent grid or keep still in any time step. Concretely, at any time step t, the action $ {a}_{j}^{t} $ of j-th agent can be expressed as a five-dimensional vector from the set {(0,0,0,0,1), (0,0,0,1,0), (0,0,1,0,0,), (0,1,0,0,0), (1,0,0,0,0)}. Each component of this vector corresponds to a specific movement direction:

● $ {a}_{j}^{t}=(\mathrm{0{{,}}0}{{,}}\mathrm{0{{,}}0}{{,}}1) $ indicates that j-th agent transfers to adjacent grid on the left.

● $ {a}_{j}^{t}=(\mathrm{0{{,}}0}{{,}}\mathrm{0{{,}}1}{{,}}0) $ represents that j-th agent moves to adjacent grid on the right.

● $ {a}_{j}^{t}=(\mathrm{0{{,}}0}{{,}}\mathrm{1{{,}}0}{{,}}0) $ signifies a transfer to the adjacent grid in front.

● $ {a}_{j}^{t}=(\mathrm{0{{,}}1}{{,}}\mathrm{0{{,}}0}{{,}}0) $ denotes that j-th agent moves to adjacent grid behind it.

● $ {a}_{j}^{t}=(\mathrm{1{{,}}0}{{,}}\mathrm{0{{,}}0}{{,}}0) $ means that j-th agent remains in its current grid.

(4) Reward Function $ \mathcal{R} $

At any time step t > 0, each agent takes action $ {a}_{j}^{t} $, moving to a new position. We obtain tf^t, which is equal to the output of Algorithm 1 when these agents are located in new positions after taking joint actions $ {\mathbf{a}}^{\mathbf{t}} $. At time step t = 0, tf⁰ is determined by executing Algorithm 1 when agents are in the initial positions.

Then, the set of reward functions $ {\mathbf{r}}^{\mathbf{t}}=\{{r}_{1}^{t}{{,}}\cdots {{,}}{r}_{m}^{t}\} $ can be computed based on the value of tf^t. The reward function $ {r}_{j}^{t} $ of j-th agent at time step t is formulated as:

where, P_b is the punishment if the j-th agent moves out of the boundary of the area or collides with other agents or IoTDs, $ {\xi }_{j}^{t}\in \left\{\mathrm{0{{,}}1}\right\} $ with $ {\xi }_{j}^{t}=1 $ indicating that j-th agent accepts the punishment at time step t and $ {\xi }_{j}^{t}=0 $ otherwise.

Algorithm for deploying LSCs

In this subsection, we propose Deploy Chargers based on Multi-agent deep deterministic policy gradient (DCM) algorithm to deploy $ m $ LSCs in SPTIoT-LSC network. The Multi-Agent Deep Deterministic Policy Gradient (MADDPG)^[28] algorithm is one of the MADRL methods with the paradigm of centralized training and decentralized execution. In the centralized training phase, agents use joint observations and actions of all agents to train the neural networks. In the decentralized execution phase, each agent only uses local observation to obtain its action.

We first introduce the fundamental components and corresponding notations of MADDPG, encompassing the actor networks, critic networks, target networks, and the replay buffer. The framework of MADDPG is shown in Fig. 2. Each agent learns a $ Q $ value function serving as a critic and a policy function acting as an actor. The actor of j-th agent is built via a neural network (denoted as its parameters $ {\theta }_{j}^{\mu } $). The actor network $ {\theta }_{j}^{\mu } $ of j-th agent generates the action $ {a}_{j}^{t}={\mu }_{j}({o}_{j}^{t}{{;}}{\theta }_{j}^{\mu }) $ based on the input observation $ {o}_{j}^{t} $ at each time step t, where $ {\mu }_{j}({o}_{j}^{t}{{;}}{\theta }_{j}^{\mu }) $ is the output of the actor network. Similarly, the critic of j-th agent is also built via a neural network (denoted as its parameters $ {\theta }_{j}^{Q} $). The critic network $ {\theta }_{j}^{Q} $ of j-th agent gives the estimated $ {Q}_{j}({\mathbf{o}}^{\mathbf{t}}{{,}}{\mathbf{a}}^{\mathbf{t}}{{;}}{\theta }_{j}^{Q}) $ value based on the input joint observations $ {\mathbf{o}}^{\mathbf{t}} $ and joint actions $ {\mathbf{a}}^{\mathbf{t}} $ at any time step $ t $. Any j-th agent possesses a target actor network (represented as parameters $ {\theta }_{j}^{{\mu '}} $) and a target critic network (represented as parameters $ {\theta }_{j}^{{Q'}} $) to make the training process more stable. Let $ \mathcal{D} $ represent the replay buffer to store the transition $ ({\mathbf{o}}^{\mathbf{t}}{{,}}{\mathbf{a}}^{\mathbf{t}}{{,}}{\mathbf{r}}^{\mathbf{t}}{{,}}{\mathbf{o}}^{\mathbf{t}+1}) $. We can randomly select a mini-batch $ \mathcal{K} $ of transitions from $ \mathcal{D} $ for training the networks, effectively breaking the correlation among sequential samples and enhancing stability of the training process.

Figure 2. 

The framework of the MADDPG algorithm. The blue arrows represent the interaction among the agents and the environment. The black arrows are used to update the parameters of the networks.

Then, we give the methods to update the actor networks, critic networks and target networks.

The actor network of j-th agent is updated by using sampled policy gradient for the policy function $ {J}_{j} $:

where $ {k}^{\text{'}}=({\mathbf{o}}^{\mathbf{k}}{{,}}{\mathbf{a}}^{\mathbf{k}}{{,}}{\mathbf{r}}^{\mathbf{k}}{{,}}{\mathbf{o}}^{\mathbf{k}+1}) $ is a transition in $ \mathcal{K} $.

The critic network of j-th agent is updated by minimizing the Mean Square Error (MSE) loss:

where, $ {y}_{j}^{k}={r}_{j}^{k}+\gamma {Q}_{j'}({\mathbf{o}}^{\mathbf{k}+1}{{,}}{\mathbf{a}}^{\mathbf{k}+1}{{;}}{\theta }_{j}^{{Q'}}){|}_{{a}_{j}^{k+1}={\mu '}({o}_{j}^{k+1}{{;}}{\theta }_{j}^{{\mu '}})} $.

The parameters of the target networks of j-th agent are updated through a soft update, that is:

where, $ \epsilon $ is a small constant.

The details of the DCM algorithm are summarized in Algorithm 2, which consists of two phases: training phase (Lines 1−26) and executing phase (Lines 27−35).

In the training phase, our target is to train the actor and critic networks of agents. The training phase contains $ {N}_{e} $ episodes and each episode has $ T $ time steps. First, we initialize the parameters of neural networks $ {\theta }_{j}^{\mu } $, $ {\theta }_{j}^{{\mu }^{\text{'}}} $, $ {\theta }_{j}^{Q} $, and $ {\theta }_{j}^{{Q}^{\text{'}}} $ of each $ {c}_{j}\in C $ and execute Algorithm 1. to acquire $ t{f}^{0} $ and the replay buffer $ \mathcal{D} $ is cleared out. Then, at each episode, we initialize positions of $ m $ LSCs and an exploration noise $ \mathcal{N} $. After that, for each time step $ t $ at any one episode, any j-th agent derives the action $ {a}_{j}^{t}={\mu }_{j}({o}_{j}^{t};{\theta }_{j}^{\mu })+\mathcal{N} $ by inputing the local observation $ {o}_{j}^{t} $ in the actor network, and then executes its action. Subsequently, agents get their rewards $ {\mathbf{r}}^{\mathbf{t}} $ and next observations $ {\mathbf{o}}^{\mathbf{t}+1} $ and store the transition $ ({\mathbf{o}}^{\mathbf{t}}{{,}}{\mathbf{a}}^{\mathbf{t}}{{,}}{\mathbf{r}}^{\mathbf{t}}{{,}}{\mathbf{o}}^{\mathbf{t}+1}) $ in the replay buffer $ \mathcal{D} $. Then, the set $ \mathcal{K} $ of random transitions are selected from $ \mathcal{D} $ to train the actor, critic, and target networks. The critic network of j-th agent is updated by minimizing the MSE loss function $ L\left({\theta }_{j}^{Q}\right) $ in Eqn (12) and the actor network of j-th agent is updated by using the policy gradient for policy function $ {J}_{j} $ in Eqn (11). The updates of the target actor network and target critic network of j-th agent are shown in Eqns (13) and (14), respectively.

In the executing phase, we leverage the well-trained actor networks to determine the actions of agents. Any j-th agent inputs its local observation $ {o}_{j}^{t} $ in its actor network and obtains an action $ {a}_{j}^{t}={\mu }_{j}({o}_{j}^{t};{\theta }_{j}^{\mu }) $ for execution. After $ T $ steps, we obtain the final positions of LSCs and execute Algorithm 1 to obtain $ {T}_{c} $.

Algorithm for MLCC problem

In this subsection, we propose an approximation algorithm to solve the MLCC problem, which is called MLCC Algorithm (MLCCA). The steps of the MLCCA algorithm are as follows (Algorithm 3).

First, we divide the monitoring area A evenly into L × L grids.

Second, for m from 1 to n, we execute Algorithm 2 to obtain the deployment result of m LSCs and T_c. If T_c == T_w then we obtain the value m, otherwise, let m = m + 1.

In this section, we demonstrate and evaluate the performance of the proposed MLCCA algorithm and the ascendency of SPTIoT through a series of meticulously designed experiments. We first evaluate the convergence of the MADDPG approach under different learning rates and compare the performance of MADDPG with Deep Deterministic Policy Gradient (DDPG). Then, we compare the MLCCA algorithm with other baseline algorithms to demonstrate its effectiveness. Finally, we compare the performance of the SPTIoT network with the general IoT network to highlight its advantages.

The code is implemented by using MATLAB 2019b and Python 3.6. Table 1 lists some constant parameters utilized in our experiments.

An instance of the MLCCA algorithm

As the example shown in Fig. 3, we set the configurations as n = 45, R_c = 50 m, E_M = 10,000 J, T_w = 3,600 s, P_c = 3,000 W, P_s = 200 W. We execute the MLCCA algorithm for the instance. Figure 3a−d are the deployment results of LSCs when m = 1, 2, 3, 4, respectively. In these subfigures, the solid lines represent the movement paths of these LSCs during deployment and the dotted circles indicate the coverage areas of these LSCs. Only when m = 4, the equality T_c = 3,600 s = T_w holds. Hence, we conclude that m = 4 is the solution of MLCC problem in this instance.

Figure 3. 

The deployment result of LSCs for a given instance obtained by the MLCCA algorithm. The deployment result (a) when m = 1, (b) when m = 2, (c) when m = 3, (d) when m = 4.

Convergence of the MADDPG approach

In this subsection, we first evaluate the convergence performance of the MADDPG algorithm under different learning rates. Then, we compare the performance of MADDPG with DDPG.

We set n = 40, m =3, E_M = 10,000 J, T_w = 3,600 s, R_c = 50 m, P_c = 3,000 W, P_s = 200 W.

In Fig. 4a, we illustrate the convergence performance of the MADDPG algorithm under different learning rates lr = 0.1, lr = 0.01, and lr = 0.001. As seen in the figure, a too high learning rate is unstable and has obvious fluctuation while a too low learning rate causes convergence to local optimal values. Notably, the best convergence effect is achieved with lr = 0.01 compared to rates of 0.1 and 0.001. Consequently, the learning rate is set as 0.01 in subsequent experiments.

Figure 4. 

The convergence performance of the MADDPG approach. (a) The convergence evaluation under different learning rates. (b) Comparison between MADDPG and DDPG.

In Fig. 4b, we compare the convergence performance of MADDPG with DDPG, where the DDPG algorithm has the same htype parameters, observation space, action space, and reward functions. However, the difference is that the actor and critic networks of any LSC are trained only relying on its own observation and action and are not affected by the observations and actions of other LSCs. The results show that the MADDPG algorithm outperforms the DDPG algorithm, reflecting the superiority of multi-agent collaborative working.

Performance comparison of different algorithms

In this subsection, we compare the performance of the MLCCA algorithm with four other algorithms under different settings and verify the superiority of our proposed algorithm. The baseline algorithms for comparison are listed as follows:

(1) K-means. The K-means algorithm consists of the following steps. In the first step, initialize m = 1. In the second step, we use the K-means^[29] algorithm to obtain m clustering centers by Euclidean distance clustering, and deploy m LSCs to the m clustering centers. In the third step, execute the LCSS algorithm to obtain T_c. Finally, if T_c == T_w then we obtain the value m, otherwise, let m = m + 1 and return to the second step.

(2) Greedy. The Greedy algorithm is summarized in the following steps. In the first step, we divide the monitoring area A evenly into L × L grids. In the second step, for j from 1 to n, we deploy the j-th LSC in the optimal grid and call LCSS algorithm to obtain T_c, where the optimal grid is defined as: j-th LSC deployed in this grid can obtain larger T_c than deployed in any other grid. If T_c == T_w then we obtain the value m = j, otherwise, let j = j + 1.

(3) Simulated Annealing (SA)^[18]. We employ the Simulated Annealing^[18] method to deploy LSCs, where the center of each grid is a candidate charger deployment location.

(4) Wireless chArger placement wIth obsTacles (WAIT)^[22]. We employ the WAIT^[22] method (ignoring obstacles) to deploy LSCs, and the goal is to minimize the number of deployed LSCs and meet the energy demands of all IoTDs.

In Fig. 5, we evaluate the performance of three algorithms by setting E_M = 10,000 J, T_w = 3,600 s, R_c = 60 m, P_c = 3,000 W, P_s = 200 W, and changing n from 10 to 40. It can be observed that the MLCCA algorithm outperforms the other algorithms and with the increasing of n, the number of LSCs increases. The SA and WAIT algorithms perform significantly worse than the other three algorithms. This is primarily because previous studies did not consider the energy transfer between IoTDs, needing to deploy more LSCs to cover all IoTDs.

Figure 5. 

Performance comparison by changing the number of IoTDs n.

In Fig. 6, we evaluate the performance of three algorithms by setting n = 30, E_M = =10,000 J, T_w = 3,600 s, P_c = 3,000 W, P_s = 200 W, and changing R_c from 40 to 100 m. The figure illustrates that the MLCCA algorithm outperforms the other algorithms and with the increasing of R_c, the performance difference between the five algorithms is getting smaller. The reason is that as the R_c increases, LSCs can cover and provide energy to more IoTDs, thus narrowing the performance difference between the three algorithms. Additionally, the SA and WAIT algorithms notably lag behind the other three algorithms.

Figure 6. 

Performance comparison by changing the charging radius R_c.

In Fig. 7, we compare the performance of three algorithms by setting n = 30, T_w = 3,600 s, R_c = 60 m, P_c = 3,000 W, P_s = 200 W, and changing E_M from 5,000 to 20,000 J. The figure shows that the performance of MLCCA algorithm is superior compared with the other algorithms. With the increasing of E_M, the curves corresponding to MLCCA, Greedy, and K-means algorithms gradually decrease, while the curves associated with SA and WAIT algorithms remain almost unchanged. This is because n and R_c remain unchanged, requiring the same number of LSCs to cover all IoTDs.

Figure 7. 

Performance comparison by varying the maximum battery capacity of IoTDs E_M.

Comparison between SPTIoT and the general IoT network

In this subsection, we undertake a comparative analysis of the SPTIoT and the general IoT network in terms of the number of LSCs required under various parameter settings. Notably, in the general IoT network, IoTDs are incapable of charging other IoTDs. The charging scheduling mechanism in the general IoT operates as follows: during each time slot $ \tau $, each $ {c}_{j}\in C $ charges the IoTD $ {s}_{i}= \mathrm{a}\mathrm{r}\mathrm{g}min\{{E}_{i}^{r}(\tau )|{d}_{i,j}^{c}\le {R}_{c}\wedge \sum _{{c}_{v}\in C\setminus\{{c}_{j}\}} {a}_{i}^{v}\left(\tau \right)=0\} $. All results are illustrated in Fig. 8.

Figure 8. 

Performance comparison between SPTIoT and the general IoT network by varying n, R_c, P_c, T_w. Performance comparison by varying (a) the number of IoTDs n, (b) the charging radius R_c, (c) the source power of LSCs P_c, and (d) the working period T_w.

In Fig. 8a, we show the performance comparison of SPTIoT and general IoT network as we set E_M = 10,000 J, T_w = 3,600 s, R_c = 60 m, P_c = 3,000 W, P_s = 200 W, and change n from 10 to 40. The figure shows that the SPTIoT outperforms the general IoT network, and as n increases, the number of LSCs in SPTIoT increases less than that in the general IoT network.

In Fig. 8b, we set n = 30, E_M = 10,000 J, T_w = 3,600 s, P_c = 3,000 W, P_s = 200 W, and change R_c from 40 to 100 m. The figure shows that as R_c increases, the SPTIoT has better performance, and the difference between the number of LSCs in the two networks reduces. The reason is that with the increase of R_c, LSCs can cover and provide energy to more IoTDs, thus narrowing the performance difference between the two networks.

In Fig. 8c, we set n = 30, E_M = 10,000 J, T_w = 3,600 s, R_c = 60 m, P_s = 200 W, and change from P_c from 2,000 to 8,000 W. The figure expresses that the SPTIoT maintains superior performance, and as P_c increases, the number of LSCs in SPTIoT has significantly decreased, while it remains almost unchanged in the general IoT network. This is because in the general IoT, each IoTD needs to be covered by LSCs, and increasing P_c will not change the coverage situation.

In Fig. 8d, we set n = 30, E_M = 10,000 J, R_c = 60 m, P_c = 3,000 W, P_s = 200 W, and change from T_w from 1,200 to 8,400 s. The figure illustrates that the SPTIoT has better performance. This superiority is attributed to the efficient charging scheduling mechanisms employed by SPTIoT, which enable it to effectively meet the energy demands of IoTDs over extended periods.

In this paper, we consider the Self-organizing Power Transfer Internet of Things (SPTIoT) network framework and investigate the Minimizing Laser Chargers Coverage (MLCC) problem, which aims at minimizing the number of LSCs deployed in SPTIoT and ensuring all IoTDs in SPTIoT work continuously. Then, we prove the MLCC problem is NP-hard. To solve the problem, we first propose a sub-problem, Charging Scheduling Problem (CSP), and corresponding Layered Charging Scheduling Strategy (LCSS) algorithm to solve it. Then we designed the Deploy Chargers based on the MADDPG (DCM) algorithm to deploy the given LSCs in the network. After that, we propose an approximation algorithm called the MLCC Algorithm (MLCCA) to solve the MLCC problem based on the LCSS algorithm and the DCM algorithm. Finally, we verify the effectiveness of the proposed algorithm as well as the superiority of SPTIoT compared to the general IoT with a large number of simulations.