# Cooperative Recharge Scheme Based on a Hamiltonian Path in Mobile Wireless Rechargeable Sensor Networks

Authors: He Li; Quan Liu; Xiaopu Ma; Qinglei Qi; Jinjiang Liu; Pan Zhao; Yang Yang; Xingang Zhang
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

The energy problem and limited capacity of batteries have been fundamental constraints in many wireless sensor network (WSN) applications. For WSN, the wireless energy transmission technology based on magnetic resonance coupling is a promising energy transmission technology. To reduce the cost and energy consumption during charging in mobile wireless rechargeable sensor networks (MWRSNs), a cooperative mobile charging mechanism based on the Hamiltonian path is proposed in this paper. To improve the charging task interval, we study the use of a mobile charger (MC) as a mobile sink node to collect the data in this paper. Then, we used the sink and the charging sensors selected by the MC to construct the undirected complete graph. Finally, the Euclidean distance between nodes is used as the edge weight and a Hamiltonian loop is found by using the improved Clark–Wright (C-W) saving algorithm to solve the problem of charging a rechargeable sensor network. In addition to the energy usage efficiency (EUE) and the network lifetime, the average energy loss per unit time is considered as the evaluation index according to the impact of the MC on the energy consumption during charging. The simulation results show that the proposed scheme increases the average network lifetime, decreases the average energy loss per unit time, and improves the EUE.


---

## Body

## 1. Introduction

WSNs have been applied in various monitoring applications, including ambient air monitoring [1], forest fire detection [2], electric networks [3], ecological environment monitoring [4], and medical health monitoring [5]. However, the energy requirement was not filled because of high computational resources, unreachable sensor nodes, and additional maintenances [6]. Kurs et al. [7] proposed a coupling resonance method to charge remote targets wirelessly with high efficiency and demonstrated the feasibility of wireless charging. The wireless energy transmission technology has the following advantages[8]:Charging and charged instruments do not need to be wired or connectedCharging direction is not fixed and does not need to be in the visual rangeCompared with other environments, the method to obtain energy is predictable, stable, and controllableWith the increasing development of wireless energy transmission technology, research on wireless rechargeable sensor networks (WRSNs) is gradually increasing. Recently, WRSNs have been proposed, and multiple harvesting techniques can be used to charge the batteries of the rechargeable sensor nodes.MWRSN is a mobile module added on the basis of WRSN, which attaches the MC and wireless sensor nodes to mobile objects. A mobile rechargeable sensor network refers to the active charging power node in a network, which can charge wireless nodes for rechargeable sensor nodes by moving. Compared with ordinary sensor networks, mobile rechargeable sensor networks have the following characteristics:Rechargeability: the power of mobile rechargeable sensor nodes can be supplemented. In theory, the MWRSN can keep working permanently.Mobility: the movement of the MC nodes and sensor nodes makes the topology of WSN change dynamically.Limitation: in practical applications, the charging capacity of the MC is limited, which is reflected in the limited moving speed, charging power, and total energy.Theoretically, the MWRSN can remain in permanent operation. However, in practical applications, the charging capacity of an MC is limited, which is manifested in limited moving speed, charging power, and total energy. Therefore, to realize the permanent existence of MWRSN, an MC is required not only to dynamically adjust its mobile charging mode according to the network state when charging task requests occur but also to cooperate with wireless sensor nodes to complete charging tasks efficiently.At present, a number of studies have explored charging strategies and algorithms for MWRSN, most of which focused on offline recharging. Offline charging is assumed that the energy consumption rate of each sensor node is always fixed. The MC plans charging paths in advance according to the energy consumption of nodes in the network in the previous operation stage. During charging, MC moves along the planned paths periodically to replenish energy for sensor nodes [9]. However, in practice, the energy consumption rate of nodes is not fixed, and the energy consumption of sensor nodes shows high dynamics and diversity affected by the surrounding environment [10]. Therefore, if MC charges according to the predetermined charging path and strategy in offline charging, it will cause sensor node failure and serious degradation of the performance of the charging algorithm. To solve the problems of offline charging, some researchers put forward the online charging mechanism. In online charging, MC makes the charging strategy in real time and dynamically according to the actual residual energy of the sensor nodes. Compared with offline charging, online charging can better adapt to the energy needs and changes of actual nodes. However, the design of an online charging strategy has the following challenges: Due to the dynamic change of node energy consumption rate, it is challenging to plan the charging path of MC dynamically in real time according to the actual remaining energy status of nodes and timely charge to avoid node failure.The charging response should be fair. When the number of nodes requesting charging increases, the failure rate of sensor nodes should be reduced as much as possible.In the charging process, the energy cost caused by MC movement should be reduced as much as possible and the energy carried by MC should be converted into effective energy for sensor charging as much as possible.To solve these problems, in this paper, a stop-wait collaborative charging algorithm based on a Hamiltonian path is proposed in MWRSN. Compared with the existing work, the innovation of this paper is as follows:To improve the charging task interval, we study the use of an MC as a mobile sink node to collect the data and establish the optimum model of the stop position.To improve the EUE of MWRSN, the charging sensor node of the next round is considered as the current charging task scheduling in this algorithm when the power of MC is allowed.To reduce the mobile path, an improved C-W saving algorithm is used to establish the Hamiltonian charging path according to the stop position of the mobile charger and the location of charging sensor nodes and sink.To charge more sensors, the MC will not be fully charged for all sensors. As the MC passes by the stop-wait position, the stop-wait charging sensor node moves to meet with the MC and be charged.


## 2. Related Works

### 2.1. Optimization Schemes of the MWRSN

Rechargeable charging task scheduling problems for WSN have been studied in [9–15]. According to the wireless energy transmission technology, corresponding wireless sensor network models and optimization problems have been proposed. By solving the approximate optimal solution of the corresponding optimization problem, the charging scheme of the wireless charging node was obtained, which improves the charging efficiency of the sensor network. Budgetary constraints for different expenditure categories have been considered in [11]. The problem of scheduling the minimum number of MCs was investigated to replenish energy from all sensors in a WRSN. However, this method did not consider the dynamic topology problem when mobile charging nodes traverse sensor nodes in the network as data acquisition devices to collect data. A path planning model for mobile wireless charging equipment (WCE) based on multiobjective optimization was proposed to replenish energy and collect data in [12]. The limited energy of WCE in WRSN was considered to maximize the total energy utility of the mobile WCE and minimize the average delay of data transmission in this method. However, this method lacks charging task coordination mechanism, which affected the charging utility and network energy consumption. To maximize the utilization rate of the MC and reduce the recharging delay, a cost-balanced mobile energy replenishment strategy (CBMERS) was proposed in [13]. According to their remaining lifetime, the nodes are assigned into groups to ensure that only nodes with lower residual energy in each slot are recharged. To balance the energy consumption between multiple MCs, the optimal trajectory allocation scheme was obtained by taking the moving distance and energy consumption as constraints. However, charging requests have an unbalanced effect on spatiotemporal constraints. To maximize the charging efficiency, a mixed-integer optimization model for simultaneous charging scheduling and charging time allocation is established in [14]. An offline algorithm was proposed to solve the problem, and an online charging node insertion algorithm was developed for real-time service. However, this method was only suitable for real-time business scenarios and not suitable for sparse networks. An efficient scheme for energy replenishment of sensor nodes was proposed to improve overall charging performance in [15]. The optimal trajectories for a given number of WCVs based on the routing loads of the sensor nodes were designed to make the network operational for a longer time. However, the rate of energy consumption varies dynamically due to the uncertainty of environmental conditions; therefore, a periodical charging scheme was infeasible for complex and changeable networks. In [16], a optimization problem with the target of maximizing the ratio of MC’s vacation time over one entire cycle time is proposed to improve channel utilization and prolong network lifetime. However, this method did not involve the dynamic topology of WRSN. This method was not suitable for a mobile network with a dynamic topology. Then, an optimization problem was formulated to maximize the MC’s vacation time over the rechargeable cycle. In [17], it was assumed that an MC must charge a sensor to its full energy capacity before moving to charge the next sensor and that each sensor could be partially charged. To maximize the sum of the sensor lifetimes and to minimize the travel distance of the MC, two novel optimization problems of scheduling an MC to charge a set of sensors were formulated. Although this method increases the number of nodes that an MC can serve, it also accelerates the scheduling frequency as well as the energy consumption rate of the MC.A power beacon (PB) and multiple wireless powered user nodes were considered static networks in [18]. All user nodes assumed either a charge or work mode. A charge scheduling scheme that achieved the system's maximal energy efficiency was proposed, and this scheme was extended to a two-tier network architecture. An energy-efficient traveling path for multiple MCs was designed in [19]. This method divided the whole network into many subregions to maximize the benefit of multiple MCs. To find the charging points, the charging radius based nearest neighbor approach was used to improve the charging efficiency. However, different sensors have different contributions in terms of the monitoring quality that was ignored in this method. Similar to the study in [19], a novel fuzzy logic-based on-demand charging scheduling scheme in WRSNs [20] was proposed to equally distribute the workload to each MC. To recharge the nodes with different energy consumption rates, the adaptive threshold for charging requests was considered in this study. To prolong the life of WSN and minimize the travel distance of mobile chargers, a dynamic mobile charger scheduling (DPMCS) scheme is proposed in the literature [21]. The node requests a charge before it runs out of energy and the mobile charger charges it. This scheme uses deep reinforcement learning to determine the schedule of the mobile charger. It prolongs the life of WSN by reducing the number of dead zone nodes and minimizing the travel distance of the mobile charger. To maximize the network lifetime, a two-phase lifetime-enhancing method (TLM) is proposed in [22]. In the first phase, a multiobjective particle swarm optimization (MOPSO) algorithm was proposed to relocate useful mobile rechargeable sensor nodes at optimal locations to meet the full target coverage. In the second phase, a modified binary multiobjective evolutionary algorithm was adopted to extend the network lifetime. However, these methods did not consider the dynamic topology of an MC as a data acquisition device. In [23–26], an MC was considered a data collection device to obtain data information from the sensor node when charging the sensor node. Based on this concept, dynamic topology working modes in WRSN were proposed. However, these methods lacked the coordination mechanism of charging task, which affected the charging utility and network energy consumption.


### 2.2. Cooperative Schemes of the MWRSN

Energy efficiency remains a great challenge without collaboration. To increase the survival rate of nodes in 3D underwater networks, a new temporal and spatial collaborative charging algorithm with multiple mobile charging ships and charging stations (mCS-TS) was proposed in [27]. A concept of secondary charging stations for mobile charging ships was designed to reduce the traveling cost and improve charging efficiency. Simulation results show the effectiveness of the proposed algorithm. This method has the problem of spatiotemporal synchronization and lacks the cooperative collection mechanism of MC. The application of this method has certain scenario limitations.The collaborative feature by forming a hierarchical charging structure was proposed in [28]. The authors distinguish the chargers into two groups: the hierarchically lower MCs which charge sensor nodes and the hierarchically higher special chargers (SCs) which charge MCs. Four collaborative charging protocols were proposed to achieve efficient charging and improve important network properties. However, this method does not consider the mobility of nodes and the dynamic changes in network topology. It will cause long moving paths and excessive energy consumption during the next cycle of task coordination.To solve the periodic charging of WSN, in [29], the charging problem in WSN was modeled as a routing problem of mobile charging nodes with time windows. This method transformed multiple routing problems into a single routing problem and proposed a local optimization algorithm considering the collaboration between mobile charging nodes. Simulation results showed that the proposed algorithm had certain advantages in charging scheduling. However, this method did not consider the dynamic topology of an MC as a data acquisition device when traversing sensor nodes in the network. In [30], a collaborative scheduling algorithm was proposed for mobile charging tasks, which allowed energy transfer between MCs. It was demonstrated that this algorithm could cover an infinite length of a one-dimensional (1D) wireless sensor network under three assumptions. Then, the hypothesis was removed one by one, and the method was extended to constrained two-dimensional (2D) wireless sensor network scenarios. Simulation results showed that this method could improve the energy efficiency of charging. This method lacks the cooperative collection mechanism of MC, resulting in the problems of short network lifetime and frequent charging task scheduling. To reduce costs, a novel concept and an optimal charging algorithm were introduced in [31]. It was demonstrated that push-shuttle-back (PSB) could achieve the minimum number of chargers and the optimal shuttling distance in a 1D scenario with negligible energy loss. The algorithm extended the solution to 2D scenarios and introduced a new circle-based scheme to improve charging efficiency and reduce the number of chargers needed to serve the sensor network. However, this method incurs high overhead; the major drawback is the large traveling cost because the MC needs to go back and forth between a charging station and sensors. To adapt to large-scale WRSN, a temporal-spatial charging scheduling algorithm was developed in [32]. This method aimed to minimize the number of dead nodes while maximizing energy efficiency to prolong the network lifetime. A node deletion algorithm was developed to remove low-efficiency charging nodes. Simulation results showed that this scheme could achieve promising performance in charging throughput and efficiency. However, this method fails to take into account the heterogeneous energy consumption of the nodes which should be given further consideration since it reduces the EUE. In [33], according to the importance of the sensor node (associated with the distance to the base station), the sensor nodes were divided into two types: sensor nodes in ring 0 and sensor nodes in the outer ring. To improve the charging efficiency, a novel charging model for wireless charging vehicles (WCVs) was proposed to adopt different charging strategies for different sensor nodes. To estimate the lifetime of the network, a new metric named the normalized dead time was proposed. The simulation results indicated that the performance of the WRSN could be improved. Due to the limited energy resources of WRSNs, there will be resource competition among nodes.The limitations of these algorithms need to further study the collaborative charging scheduling problem of the MWRSN. In this work, a stop-wait collaborative charging algorithm is designed to improve the EUE of WSN. The charging sensor node of the next round is considered as the current charging task scheduling. The charging task interval of the MC is used to select the sensors and determine the charging sequence and stop-wait charging set. The position nearest to the stop-wait charging sensor node is selected as the stop-wait position. As the MC passes by the stop-wait position, the stop-wait charging sensor node moves to meet with the MC and be charged. To charge more sensors, the MC will not be fully charged for all sensors in our algorithm. The simulation results show that the stop-wait algorithm can achieve a better EUE of WSN compared with DPMCS [21], MUC [34], BNRS [35], and VN-MOAC [36] algorithms. Compared with existing cooperative mobile recharge schemes, our proposed algorithm contributes the following improvements:Considering the data collection of the MC, we first present a novel optimal approach to determine the stop position for the MC to collect data as a mobile sink node after the charging scheduling task is completed. Hence, the charging task interval can be extended.Then, a cooperative recharge scheme based on a Hamiltonian path is designed which utilizes the improved C-W method for determining the charging of the nodes by contemplating various network attributes.The charging sensor node of the next round is proposed as the stop-wait charging sensor node of the current round. The aim is to avoid the MC having to charge these nodes in the next round and reduce network energy consumption.Considering the limited power of the MC in the establishment of a mobile path, an incomplete charging mode is proposed to improve the serviceability of the MC. The sensor node is charged according to the maximum number of cycles that can be achieved between charging tasks.The proposed algorithm is evaluated through extensive simulations and compared with four existing and similar works in terms of EUE, average energy loss per unit time, and average network lifetime.This paper is organized as follows: Section2 presents brief related works of charging schemes. Section 3 introduces the assumptions, definitions, wireless rechargeable sensor network model, and network energy consumption model. Section 4 describes the algorithm of cooperative recharging based on the Hamiltonian path in the MWRSN. Simulation results and analyses of the algorithms are presented in Section 5. Finally, the conclusions are drawn in Section 6.


## 2.1. Optimization Schemes of the MWRSN

Rechargeable charging task scheduling problems for WSN have been studied in [9–15]. According to the wireless energy transmission technology, corresponding wireless sensor network models and optimization problems have been proposed. By solving the approximate optimal solution of the corresponding optimization problem, the charging scheme of the wireless charging node was obtained, which improves the charging efficiency of the sensor network. Budgetary constraints for different expenditure categories have been considered in [11]. The problem of scheduling the minimum number of MCs was investigated to replenish energy from all sensors in a WRSN. However, this method did not consider the dynamic topology problem when mobile charging nodes traverse sensor nodes in the network as data acquisition devices to collect data. A path planning model for mobile wireless charging equipment (WCE) based on multiobjective optimization was proposed to replenish energy and collect data in [12]. The limited energy of WCE in WRSN was considered to maximize the total energy utility of the mobile WCE and minimize the average delay of data transmission in this method. However, this method lacks charging task coordination mechanism, which affected the charging utility and network energy consumption. To maximize the utilization rate of the MC and reduce the recharging delay, a cost-balanced mobile energy replenishment strategy (CBMERS) was proposed in [13]. According to their remaining lifetime, the nodes are assigned into groups to ensure that only nodes with lower residual energy in each slot are recharged. To balance the energy consumption between multiple MCs, the optimal trajectory allocation scheme was obtained by taking the moving distance and energy consumption as constraints. However, charging requests have an unbalanced effect on spatiotemporal constraints. To maximize the charging efficiency, a mixed-integer optimization model for simultaneous charging scheduling and charging time allocation is established in [14]. An offline algorithm was proposed to solve the problem, and an online charging node insertion algorithm was developed for real-time service. However, this method was only suitable for real-time business scenarios and not suitable for sparse networks. An efficient scheme for energy replenishment of sensor nodes was proposed to improve overall charging performance in [15]. The optimal trajectories for a given number of WCVs based on the routing loads of the sensor nodes were designed to make the network operational for a longer time. However, the rate of energy consumption varies dynamically due to the uncertainty of environmental conditions; therefore, a periodical charging scheme was infeasible for complex and changeable networks. In [16], a optimization problem with the target of maximizing the ratio of MC’s vacation time over one entire cycle time is proposed to improve channel utilization and prolong network lifetime. However, this method did not involve the dynamic topology of WRSN. This method was not suitable for a mobile network with a dynamic topology. Then, an optimization problem was formulated to maximize the MC’s vacation time over the rechargeable cycle. In [17], it was assumed that an MC must charge a sensor to its full energy capacity before moving to charge the next sensor and that each sensor could be partially charged. To maximize the sum of the sensor lifetimes and to minimize the travel distance of the MC, two novel optimization problems of scheduling an MC to charge a set of sensors were formulated. Although this method increases the number of nodes that an MC can serve, it also accelerates the scheduling frequency as well as the energy consumption rate of the MC.A power beacon (PB) and multiple wireless powered user nodes were considered static networks in [18]. All user nodes assumed either a charge or work mode. A charge scheduling scheme that achieved the system's maximal energy efficiency was proposed, and this scheme was extended to a two-tier network architecture. An energy-efficient traveling path for multiple MCs was designed in [19]. This method divided the whole network into many subregions to maximize the benefit of multiple MCs. To find the charging points, the charging radius based nearest neighbor approach was used to improve the charging efficiency. However, different sensors have different contributions in terms of the monitoring quality that was ignored in this method. Similar to the study in [19], a novel fuzzy logic-based on-demand charging scheduling scheme in WRSNs [20] was proposed to equally distribute the workload to each MC. To recharge the nodes with different energy consumption rates, the adaptive threshold for charging requests was considered in this study. To prolong the life of WSN and minimize the travel distance of mobile chargers, a dynamic mobile charger scheduling (DPMCS) scheme is proposed in the literature [21]. The node requests a charge before it runs out of energy and the mobile charger charges it. This scheme uses deep reinforcement learning to determine the schedule of the mobile charger. It prolongs the life of WSN by reducing the number of dead zone nodes and minimizing the travel distance of the mobile charger. To maximize the network lifetime, a two-phase lifetime-enhancing method (TLM) is proposed in [22]. In the first phase, a multiobjective particle swarm optimization (MOPSO) algorithm was proposed to relocate useful mobile rechargeable sensor nodes at optimal locations to meet the full target coverage. In the second phase, a modified binary multiobjective evolutionary algorithm was adopted to extend the network lifetime. However, these methods did not consider the dynamic topology of an MC as a data acquisition device. In [23–26], an MC was considered a data collection device to obtain data information from the sensor node when charging the sensor node. Based on this concept, dynamic topology working modes in WRSN were proposed. However, these methods lacked the coordination mechanism of charging task, which affected the charging utility and network energy consumption.


## 2.2. Cooperative Schemes of the MWRSN

Energy efficiency remains a great challenge without collaboration. To increase the survival rate of nodes in 3D underwater networks, a new temporal and spatial collaborative charging algorithm with multiple mobile charging ships and charging stations (mCS-TS) was proposed in [27]. A concept of secondary charging stations for mobile charging ships was designed to reduce the traveling cost and improve charging efficiency. Simulation results show the effectiveness of the proposed algorithm. This method has the problem of spatiotemporal synchronization and lacks the cooperative collection mechanism of MC. The application of this method has certain scenario limitations.The collaborative feature by forming a hierarchical charging structure was proposed in [28]. The authors distinguish the chargers into two groups: the hierarchically lower MCs which charge sensor nodes and the hierarchically higher special chargers (SCs) which charge MCs. Four collaborative charging protocols were proposed to achieve efficient charging and improve important network properties. However, this method does not consider the mobility of nodes and the dynamic changes in network topology. It will cause long moving paths and excessive energy consumption during the next cycle of task coordination.To solve the periodic charging of WSN, in [29], the charging problem in WSN was modeled as a routing problem of mobile charging nodes with time windows. This method transformed multiple routing problems into a single routing problem and proposed a local optimization algorithm considering the collaboration between mobile charging nodes. Simulation results showed that the proposed algorithm had certain advantages in charging scheduling. However, this method did not consider the dynamic topology of an MC as a data acquisition device when traversing sensor nodes in the network. In [30], a collaborative scheduling algorithm was proposed for mobile charging tasks, which allowed energy transfer between MCs. It was demonstrated that this algorithm could cover an infinite length of a one-dimensional (1D) wireless sensor network under three assumptions. Then, the hypothesis was removed one by one, and the method was extended to constrained two-dimensional (2D) wireless sensor network scenarios. Simulation results showed that this method could improve the energy efficiency of charging. This method lacks the cooperative collection mechanism of MC, resulting in the problems of short network lifetime and frequent charging task scheduling. To reduce costs, a novel concept and an optimal charging algorithm were introduced in [31]. It was demonstrated that push-shuttle-back (PSB) could achieve the minimum number of chargers and the optimal shuttling distance in a 1D scenario with negligible energy loss. The algorithm extended the solution to 2D scenarios and introduced a new circle-based scheme to improve charging efficiency and reduce the number of chargers needed to serve the sensor network. However, this method incurs high overhead; the major drawback is the large traveling cost because the MC needs to go back and forth between a charging station and sensors. To adapt to large-scale WRSN, a temporal-spatial charging scheduling algorithm was developed in [32]. This method aimed to minimize the number of dead nodes while maximizing energy efficiency to prolong the network lifetime. A node deletion algorithm was developed to remove low-efficiency charging nodes. Simulation results showed that this scheme could achieve promising performance in charging throughput and efficiency. However, this method fails to take into account the heterogeneous energy consumption of the nodes which should be given further consideration since it reduces the EUE. In [33], according to the importance of the sensor node (associated with the distance to the base station), the sensor nodes were divided into two types: sensor nodes in ring 0 and sensor nodes in the outer ring. To improve the charging efficiency, a novel charging model for wireless charging vehicles (WCVs) was proposed to adopt different charging strategies for different sensor nodes. To estimate the lifetime of the network, a new metric named the normalized dead time was proposed. The simulation results indicated that the performance of the WRSN could be improved. Due to the limited energy resources of WRSNs, there will be resource competition among nodes.The limitations of these algorithms need to further study the collaborative charging scheduling problem of the MWRSN. In this work, a stop-wait collaborative charging algorithm is designed to improve the EUE of WSN. The charging sensor node of the next round is considered as the current charging task scheduling. The charging task interval of the MC is used to select the sensors and determine the charging sequence and stop-wait charging set. The position nearest to the stop-wait charging sensor node is selected as the stop-wait position. As the MC passes by the stop-wait position, the stop-wait charging sensor node moves to meet with the MC and be charged. To charge more sensors, the MC will not be fully charged for all sensors in our algorithm. The simulation results show that the stop-wait algorithm can achieve a better EUE of WSN compared with DPMCS [21], MUC [34], BNRS [35], and VN-MOAC [36] algorithms. Compared with existing cooperative mobile recharge schemes, our proposed algorithm contributes the following improvements:Considering the data collection of the MC, we first present a novel optimal approach to determine the stop position for the MC to collect data as a mobile sink node after the charging scheduling task is completed. Hence, the charging task interval can be extended.Then, a cooperative recharge scheme based on a Hamiltonian path is designed which utilizes the improved C-W method for determining the charging of the nodes by contemplating various network attributes.The charging sensor node of the next round is proposed as the stop-wait charging sensor node of the current round. The aim is to avoid the MC having to charge these nodes in the next round and reduce network energy consumption.Considering the limited power of the MC in the establishment of a mobile path, an incomplete charging mode is proposed to improve the serviceability of the MC. The sensor node is charged according to the maximum number of cycles that can be achieved between charging tasks.The proposed algorithm is evaluated through extensive simulations and compared with four existing and similar works in terms of EUE, average energy loss per unit time, and average network lifetime.This paper is organized as follows: Section2 presents brief related works of charging schemes. Section 3 introduces the assumptions, definitions, wireless rechargeable sensor network model, and network energy consumption model. Section 4 describes the algorithm of cooperative recharging based on the Hamiltonian path in the MWRSN. Simulation results and analyses of the algorithms are presented in Section 5. Finally, the conclusions are drawn in Section 6.


## 3. System Model

### 3.1. WSN Charging Model

AssumeS = {si, where i in 1, 2, …, n} is the senor node set of WSN, and the location of mobile wireless sensor node si is li = (xi, yi). The communication radius of sensor si is ri, and the average moving velocity of sensor si is vi. The energy consumption of each sensor includes the energy consumption of data transmission and the movement of sensor nodes. The battery capacity of si is bi, and the average energy consumption rate of si is ei. The energy consumed by the sensor moving one unit distance is em,i. The maximum lifetime of si is τi and τi = bi/ei. The charge cycles of sensor si are τc,i and τc,i = bi(1 − ω)/ei, where ω is the low power indicator percentage of the sensor to guarantee the normal work of sensor si. The MC will recharge sensor si when the power is less than biω. Assume that a low-power indicator percentage ω can ensure the remaining survival time of sensor node biω/ei and will not fail due to battery drainage before the MC task scheduling.The battery capacity of the MC isBC, and the average moving velocity of the MC is vc. The movement and wireless charging of the MC share a battery charge, and the energy consumption of moving per unit distance for the MC is ec. The sink node in this model serves as the base station data service point as well as the energy source. Without loss of generality, the sink is taken as the coordinate origin (0, 0). The MC starts to move from the sink node for the sensor network charging task and will return to the sink node to receive the charging service when the power is low. The charging efficiency of the MC and the sensor node is ηc. If the power consumed by the MC to charge the sensor node is C, then the power obtained by the sensor node is ηcC. The lifetime of the MWRSN Tl is the minimum lifetime of a sensor in the set S and can be calculated in the following formula:(1)Tl=mini=1nτi=mini=1nbiei.The lifetime of sensorsi is τi, ei is the average energy consumption rate of si, and n is the number of sensor nodes in the WSN. Considering the actual situation, the charging task interval of MC Tcti is defined based on the network lifetime in this paper. If the power of sensor si is less than biω, the MC will recharge sensor si. Therefore, the charging task interval of MC, Tcti, is the time between the completion of charging and the start of the next charging task in this paper. The charging task interval of MC Tcti is defined as follows:(2)Tcti=mini=1nτc,i=mini=1nbi1−ωei.


### 3.2. WSN Transmission Energy Consumption Model

Here, we consider the radio model and the related parameters referenced in [34]. The energy consumption of each sensor node sends a packet to the next forwarding node over a distance rc, which is defined as follows:(3)ETl,r=leelec+lεfsrc2.The energy consumption of each sensor node receives a packet as shown in the following formula:(4)ERl=leelec,where l is the packet length, eelec is the energy consumption of the electronic equipment of a bit, and εfs is the energy consumption of the wireless antenna amplifier. Thus, the energy consumption of i to relay a packet one time is defined as follows:(5)Ei=ET,il,rc+ERl.


### 3.3. WSN Mobile Energy Consumption Model

The mobile energy consumption model of mobile sensor nodes and the MC are referred to in [37]. The wireless sensor network transmission energy consumption model is defined as follows:(6)Em,cdm,c=dm,cec,(7)Em,idm,i=dm,iem,i,where Em,c(dm,c) is the mobile energy consumption of the MC and ec is the energy consumption per unit distance moved by the MC, where ec = mc gμc, mc is the mass of the MC, g is the gravitational acceleration, and μc is the dynamic friction factor between the MC and the ground. Em,i(dm,i) is the mobile energy consumption of sensor si, and em,i is the energy consumption per unit distance moved by sensor si, where em = mm,igμm,i, mm,i is the mass of sensor si, and μm,i is the dynamic friction factor between sensor si and the ground.


### 3.4. The MWRSN Evaluation Index

The energy consumption of WSN in a charging scheduling cycle contains the energy obtained by the sensors, the moving energy consumption of the MC and sensors, and the energy loss consumed during charging. The payload energy is the energy obtained by the sensors and is defined asEpl. The overhead energy is the moving energy consumption of the MC and sensors during charging and is defined as Eoh. The EUE is defined as follows:(8)EUE=EplEpl+Eoh.The network lifetime is the time when the first node in the wireless sensor network runs out of energy. The average network lifetime is the average lifetime of MWRSN when the sensor network is randomly deployed for many times in the case of the same battery capacity. The average network energy consumption per unit time is the ratio of wireless transmission energy consumption of MWRSN to the same charging task interval under multiple random deployments of MWRSN. The mobile energy consumption is the moving energy consumption of the MC and mobile sensors. The average mobile energy consumption is the average moving energy consumption of the MC and mobile sensors under multiple random deployments of MWRSN. Charging task scheduling times is the number of charging scheduling performed by MC at the same battery capacity. Average charging scheduling times are the average number of MC charging task scheduling times when the sensor network is randomly deployed for many times in the case of the same battery capacity.To better evaluate the mobile sensor network charging model, in addition to energy efficiency, network lifetime, and energy consumption, the average moving loss per unit time (AMUT) is introduced to evaluate the mobile energy cost of the MWRSN charging task. In a charging task interval, the moving energy consumption of a mobile rechargeable sensor networkEme mainly includes the moving energy consumption of the MC and sensor nodes. For the whole MWRSN, the moving energy consumption Eme is the lower the better. The charging task interval Tcti of MWRSN is the longer the better. The AMUT is defined as follows:(9)AMUT=EmeTcti.


### 3.5. Main Symbols in Section3

The main symbols in Section3 are shown in Table 1.Table 1
Table of main symbols in Section3.
SymbolParameterliLocation of mobile wireless sensor nodesiviAverage moving velocity of sensorsi (m/s)biBattery capacity ofsi (J)eiAverage energy consumption rate (J/s)em,iEnergy consumption ofsi moving one unit distance (J/m)τiMaximum lifetime of nodesi (s)τc,iCharge cycles of sensorsi (s)ΩLow power indicator percentage of the sensors (%)BCBattery capacity of the MC (KJ)vcAverage moving velocity of the MC (m/s)ηcCharging efficiency of the MC and the sensor node (%)TlLifetime of the MWRSN (s)TctiCharging task interval of the MC (s)rcCommunication radius (m)LPacket length (bit)ET(l, r)Energy consumption of each sensor node sends a packet to the next forwarding node over a distancerc (J)ER (l)Energy consumption of each sensor node receives a packet (J)EiEnergy consumption ofi to relay a packet one time (J)DiThe data size collected by the sensor node per unit time (bit/s)eelecEnergy consumption of the electronic equipment ofl bit (nJ/bit)εfsEnergy consumption of the wireless antenna amplifier (pJ/bit)Em,c (dm,c)Mobile energy consumption of the MC (J)mcgForce of gravity in the MC (N)ecEnergy consumption per unit distance moved by the MC (J/m)μcDynamic friction factor between the MC and the groundEm,i (dm,i)Mobile energy consumption of sensorsi (J)em,iEnergy consumption per unit distance moved by sensorsi (J/m)mm,igForce of gravity in sensorsi (N)μm,iDynamic friction factor between sensorsi and the groundEplPayload energy (the energy obtained by the sensors) (J)EohOverhead energy (the moving energy consumption of the MC and sensors and the energy consumed loss during charging) (J)EmeMoving energy consumption of the MWRSN (J)


## 3.1. WSN Charging Model

AssumeS = {si, where i in 1, 2, …, n} is the senor node set of WSN, and the location of mobile wireless sensor node si is li = (xi, yi). The communication radius of sensor si is ri, and the average moving velocity of sensor si is vi. The energy consumption of each sensor includes the energy consumption of data transmission and the movement of sensor nodes. The battery capacity of si is bi, and the average energy consumption rate of si is ei. The energy consumed by the sensor moving one unit distance is em,i. The maximum lifetime of si is τi and τi = bi/ei. The charge cycles of sensor si are τc,i and τc,i = bi(1 − ω)/ei, where ω is the low power indicator percentage of the sensor to guarantee the normal work of sensor si. The MC will recharge sensor si when the power is less than biω. Assume that a low-power indicator percentage ω can ensure the remaining survival time of sensor node biω/ei and will not fail due to battery drainage before the MC task scheduling.The battery capacity of the MC isBC, and the average moving velocity of the MC is vc. The movement and wireless charging of the MC share a battery charge, and the energy consumption of moving per unit distance for the MC is ec. The sink node in this model serves as the base station data service point as well as the energy source. Without loss of generality, the sink is taken as the coordinate origin (0, 0). The MC starts to move from the sink node for the sensor network charging task and will return to the sink node to receive the charging service when the power is low. The charging efficiency of the MC and the sensor node is ηc. If the power consumed by the MC to charge the sensor node is C, then the power obtained by the sensor node is ηcC. The lifetime of the MWRSN Tl is the minimum lifetime of a sensor in the set S and can be calculated in the following formula:(1)Tl=mini=1nτi=mini=1nbiei.The lifetime of sensorsi is τi, ei is the average energy consumption rate of si, and n is the number of sensor nodes in the WSN. Considering the actual situation, the charging task interval of MC Tcti is defined based on the network lifetime in this paper. If the power of sensor si is less than biω, the MC will recharge sensor si. Therefore, the charging task interval of MC, Tcti, is the time between the completion of charging and the start of the next charging task in this paper. The charging task interval of MC Tcti is defined as follows:(2)Tcti=mini=1nτc,i=mini=1nbi1−ωei.


## 3.2. WSN Transmission Energy Consumption Model

Here, we consider the radio model and the related parameters referenced in [34]. The energy consumption of each sensor node sends a packet to the next forwarding node over a distance rc, which is defined as follows:(3)ETl,r=leelec+lεfsrc2.The energy consumption of each sensor node receives a packet as shown in the following formula:(4)ERl=leelec,where l is the packet length, eelec is the energy consumption of the electronic equipment of a bit, and εfs is the energy consumption of the wireless antenna amplifier. Thus, the energy consumption of i to relay a packet one time is defined as follows:(5)Ei=ET,il,rc+ERl.


## 3.3. WSN Mobile Energy Consumption Model

The mobile energy consumption model of mobile sensor nodes and the MC are referred to in [37]. The wireless sensor network transmission energy consumption model is defined as follows:(6)Em,cdm,c=dm,cec,(7)Em,idm,i=dm,iem,i,where Em,c(dm,c) is the mobile energy consumption of the MC and ec is the energy consumption per unit distance moved by the MC, where ec = mc gμc, mc is the mass of the MC, g is the gravitational acceleration, and μc is the dynamic friction factor between the MC and the ground. Em,i(dm,i) is the mobile energy consumption of sensor si, and em,i is the energy consumption per unit distance moved by sensor si, where em = mm,igμm,i, mm,i is the mass of sensor si, and μm,i is the dynamic friction factor between sensor si and the ground.


## 3.4. The MWRSN Evaluation Index

The energy consumption of WSN in a charging scheduling cycle contains the energy obtained by the sensors, the moving energy consumption of the MC and sensors, and the energy loss consumed during charging. The payload energy is the energy obtained by the sensors and is defined asEpl. The overhead energy is the moving energy consumption of the MC and sensors during charging and is defined as Eoh. The EUE is defined as follows:(8)EUE=EplEpl+Eoh.The network lifetime is the time when the first node in the wireless sensor network runs out of energy. The average network lifetime is the average lifetime of MWRSN when the sensor network is randomly deployed for many times in the case of the same battery capacity. The average network energy consumption per unit time is the ratio of wireless transmission energy consumption of MWRSN to the same charging task interval under multiple random deployments of MWRSN. The mobile energy consumption is the moving energy consumption of the MC and mobile sensors. The average mobile energy consumption is the average moving energy consumption of the MC and mobile sensors under multiple random deployments of MWRSN. Charging task scheduling times is the number of charging scheduling performed by MC at the same battery capacity. Average charging scheduling times are the average number of MC charging task scheduling times when the sensor network is randomly deployed for many times in the case of the same battery capacity.To better evaluate the mobile sensor network charging model, in addition to energy efficiency, network lifetime, and energy consumption, the average moving loss per unit time (AMUT) is introduced to evaluate the mobile energy cost of the MWRSN charging task. In a charging task interval, the moving energy consumption of a mobile rechargeable sensor networkEme mainly includes the moving energy consumption of the MC and sensor nodes. For the whole MWRSN, the moving energy consumption Eme is the lower the better. The charging task interval Tcti of MWRSN is the longer the better. The AMUT is defined as follows:(9)AMUT=EmeTcti.


## 3.5. Main Symbols in Section3

The main symbols in Section3 are shown in Table 1.Table 1
Table of main symbols in Section3.
SymbolParameterliLocation of mobile wireless sensor nodesiviAverage moving velocity of sensorsi (m/s)biBattery capacity ofsi (J)eiAverage energy consumption rate (J/s)em,iEnergy consumption ofsi moving one unit distance (J/m)τiMaximum lifetime of nodesi (s)τc,iCharge cycles of sensorsi (s)ΩLow power indicator percentage of the sensors (%)BCBattery capacity of the MC (KJ)vcAverage moving velocity of the MC (m/s)ηcCharging efficiency of the MC and the sensor node (%)TlLifetime of the MWRSN (s)TctiCharging task interval of the MC (s)rcCommunication radius (m)LPacket length (bit)ET(l, r)Energy consumption of each sensor node sends a packet to the next forwarding node over a distancerc (J)ER (l)Energy consumption of each sensor node receives a packet (J)EiEnergy consumption ofi to relay a packet one time (J)DiThe data size collected by the sensor node per unit time (bit/s)eelecEnergy consumption of the electronic equipment ofl bit (nJ/bit)εfsEnergy consumption of the wireless antenna amplifier (pJ/bit)Em,c (dm,c)Mobile energy consumption of the MC (J)mcgForce of gravity in the MC (N)ecEnergy consumption per unit distance moved by the MC (J/m)μcDynamic friction factor between the MC and the groundEm,i (dm,i)Mobile energy consumption of sensorsi (J)em,iEnergy consumption per unit distance moved by sensorsi (J/m)mm,igForce of gravity in sensorsi (N)μm,iDynamic friction factor between sensorsi and the groundEplPayload energy (the energy obtained by the sensors) (J)EohOverhead energy (the moving energy consumption of the MC and sensors and the energy consumed loss during charging) (J)EmeMoving energy consumption of the MWRSN (J)


## 4. Cooperative Mobile Recharge Method

The cooperative mobile recharge method of MWRSN based on the Hamiltonian path (STCI-TR) in this paper consists of six parts: charging task scheduling request, determining stop position of the MC, determining the charging sensor set, determining stop-wait charging sensor set and stop-wait position, establishing the Hamiltonian path, and cooperative charging. The flowchart of the STCI-TR algorithm is shown in Figure1.Figure 1
Flowchart of the STCI-TR algorithm.


### 4.1. Definitions and Assumptions

The definitions used in the cooperative mobile recharge method of MWRSN are as follows:Thenetwork lifetime is the time when the first node in the wireless sensor network runs out of energy [22]Thecharging task interval is the time from the beginning of a charging task to the beginning of the next charging task for the MC in the sensor networkThestop position is the best location for the MC as a mobile sink node to collect data in WRSN after the charging scheduling task is completed by the MCThestop-wait position is the location where the MC and the stop-wait charging sensor nodes meet to charge during the process of the MC moving and charging along the specified pathTheenergy usage effectiveness is the ratio of the effective energy obtained by WRSN to the total energy cost of the MC and sensor nodes during the charging process [30]The assumptions in the wireless rechargeable sensor network model are as follows:Assumption 1: the sensor node in the mobile rechargeable sensor network sends a 256 bit packet per second for data transmission.Assumption 2: the sink node and the MC are able to obtain the geographic location (such as through BeiDou, GPS positioning, or other positioning methods) of all nodes in the wireless sensor network.Assumption 3: the connectivity of the mobile rechargeable sensor network is at least 2 connections. This means that at least 2 nodes are deleted to destroy the connectivity of the network.Assumption 4: the coverage of the mobile rechargeable sensor network is at least 2 times the coverage. This means that every point in the monitoring area can be covered by at least 2 sensor nodes.Assumption 5: after the low power prompt of the node in MWRSN, the remaining lifetime of the node can ensure that the MC will arrive at the node. Node failure will not occur due to power exhaustion before charging.


### 4.2. Charging Task Scheduling Request

When the power of sensorsi is less than biω, sensor si will send the charging request message (CRequest (i)) to the MC. After receiving the message CRequest (i), the MC will collect the residual power, geographical location, and low-power indicator percentage of all sensors in the MWRSN. In practical application, the power information of the sensor nodes changes little in a short time. To reduce the unnecessary energy, the sensor will carry its own information (including residual power bi′, geographical location li,, and low power indicator percentage ω) when sending data to sink nodes. The maximum lifetime τi and residual lifetime τi′ of sensor si will be calculated by the MC according to this information. Next, the MC determines its stopping position according to the collected information.


### 4.3. Determining the Stop Position of the MC

The stopping position in this paper refers to the optimal position for the MC to collect data as a mobile sink node after the charging scheduling task is completed. To prolong the network lifetime and reduce the overall energy consumption of the network, after the charging is completed, the MC will move to the stop position as mobile sink nodes for the data acquisition task. The MC will wait for the next round of charging task scheduling at the stop position. The new data transmission path of the MWRSN will be planned according to the movement of the MC and its position. The stop position of the MC will affect the lifetime and energy consumption of wireless rechargeable sensor networks. Therefore, it is a key point of this algorithm to determine the appropriate stopping position.


#### 4.3.1. Stop Position Problem of MC

AssumeS = {si: 1, 2, …, n} is the set of WSNs, and the location of mobile wireless sensor node si is li = (xj, yj). The nodes of the wireless rechargeable sensor network are divided into a service group of sink Ss and a service group of MC Sm. When sensor node si,s is served by a sink, si,s ϵ Ss = {si,s: 1, 2, …, ns}, its data are transferred to a sink node through one or more hops; then, the decision variable Xi is 1; otherwise, it is 0. When sensor node sj,mc is served by the MC, sj,mc ϵ Ss = {sj,mc: 1, 2, …, nmc}, its data are transferred to the MC through one or more hops; then, the decision variable Xj is 1; otherwise, it is 0. Di,s and Di,mc are the amount of data sent per unit time by sensor nodes in the service group of the sink and service group of the MC, respectively. ei,s and ej,mc are the unit energy consumption of sensor nodes in the service group of the sink and service group of the MC, respectively. bi,s′ and bj,mc′ are the actual remaining power of the sensor nodes in the service group of the sink and the service group of the MC, respectively. di,s is the Euclidean distance from sensor node si,s to the sink, and dj,mc is the Euclidean distance from sensor node sj,mc to the MC.To reduce energy consumption and prolong the network lifetime, it is necessary for the MC to select the location that has a long remaining lifetime and the minimum total distance from each node. The objective function of this problem is to minimize the total weighted distance from the sink service group node to the sink (the sum of the ratio of Euclidean distancedi,s to remaining lifetime of sensor si,s) and from the MC service group node to the MC (the sum of the ratio of Euclidean distance dj,mc to remaining lifetime of sensor sj,mc). The sink node and the MC can obtain the geographic location (Assumption 2) of sensors in the wireless sensor network and the network uses the GPSR (greedy perimeter stateless routing) protocol. So the sink node and MC can calculate the di,s and dj,mc easily. Di,s and Di,mc can be obtained by the sink node and the MC when they collect the data. The sink node and the MC know the geographic location of the sensor nodes in the wireless sensor network and use the GPSR protocol. According to the network topology, it is easy for the sink node to evaluate and calculate the amount of data received and forwarded by each sensor node. Therefore, ei,s and ej,mc can be calculated by the sink node according to formulas (3)–(5). The problem model of the MC stop position is as follows:(10)min∑i=0nsdi,sXi,sτi,s′+∑j=0nmcdj,mcXj,mcτj,mv′,(11)s.t.∑i=1nXi=ns,(12)∑j=1nXj=nmc,(13)ns+nmc=n,where ∑i=0nsdi,sXi,s/τi,s′ is the sum of the ratio of Euclidean distance di,s to the remaining lifetime τi,s′ of sensor si,s and τi,s′=bi,s′/Di,sei,s. ∑j=0nmcdj,mcXj,mc/τj,mv′ is the sum of the ratio of Euclidean distance dj,mc to the remaining lifetime τi,mc′ of sensor sj,mc, and τi,mc′=bi,mc′/Di,mcei,mc. The number of sensor nodes in the service group of the sink is ns and the number of sensor nodes in the service group of the MC is nmc. The number of nodes in the MWRSN is n. The decision variables Xi and Xj are defined as follows:(14)Xi=1,if sensorsiis served by Sink,0,else.Xj=1,if sensorsjis served by MC,0,else.Constraint formula (11) is the sensor node served by the sink node. Constraint formula (12) is the sensor node served by the MC. Constraint formula (13) ensures that each sensor node can only send data to the nearest sink node or MC, and the sum of the two service group nodes is the number of nodes in the MWRSN.


#### 4.3.2. Solution of Stop Position Problem

To quickly obtain the stopping position of the MC, the Newton method with fast convergence is selected to solve the problem. The specific solution process is as follows:Step 1: the MC selects the initial point. The MC node starts from the sink node at the beginning, and the coordinate origin (taking the sink node as the coordinate origin) is selected as the initial point. The initial point is defined asLmc,0(x0, y0) and x0 = y0 = 0. The termination error is ε > 0 and let t = 0.Step 2: the MC calculates the gradient vector. LetfLmc,t=∑i=0nsdi,sXi,s/τi,s′+∑j=0nmcdj,mcXj,mc/τj,mv′. The gradient vector can be calculated as in formula (15). If the magnitude of the gradient vector is less than the termination error ∇fLmc,t≤ε, the iteration is stopped and the position coordinate Lmc,t = (xt, yt) is output. Then, the coordinate value is the stop position Sp, and the algorithm ends. Otherwise, go to Step 3.Step 3: the MC constructs Newtonian directions. MC calculates∇2fLmc,t−1 and constructs Newtonian directions Pt: Pt=−∇2fLmc,t−1∇fLmc,t.Step 4: find the next iteration point. LetLmc,t+1 = Lmc,t + Pt, t = t + 1; return to Step 2.(15)∇fLmc,k=∑jnmcDj,mcej,mcxk−xj,mcXj,mcbj,mc′xk−xj,mc2+yk−yj,mc2∑jnmcDj,mcej,mcyk−yj,mcXj,mcbj,mc′xk−xj,mc2+yk−yj,mc2.


### 4.4. Determining the Charging Sensor Set

After the MC stop position is determined, the MC calculates the charging task intervalTcti according to its stop position and selects the sensor node. First, the sink node collects information such as the location, residual power, and battery capacity of sensors in the MWRSN. Then, the MC predicts the data transmission path and transmission energy consumption of the sensor nodes according to the information collected by the sink node. The lifetime of the MWRSN Tl and charging task interval Tcti can be calculated according to formulas (1) and (2). Finally, according to the calculated charging task interval Tcti, the MC selects the sensor node as the element in the charging set SC of the current scheduling cycle. When τi′ < Tcti, the remaining lifetime of sensor node si is less than the charging task interval. Then, the node is added to the charging sensor set Sc = <s1, s2, …, sq>.After determining the charging sensor setSc, the charging quantity of each charging sensor node in the current round of the charging task should be calculated by the MC. To make the MC charge more sensor nodes, in this model, the MC is not always fully charged when charging the sensor node. The charging task interval is considered, and the charging power of sensor si is calculated based on the number of charging task intervals that sensor node si can work at full charge. The charging power of sensor si is defined as bi,c and can be calculated in the following formula:(16)bi,c=τiTcti∗Tcti∗ei−bi′,where bi′ is the remaining battery power of sensor si and ei is the average unit transmission energy consumption of sensor si. ⌊τi/Tcti⌋ is the number of charging task intervals that sensor node si can work at full charge.


### 4.5. Determining Stop-Wait Charging Sensor Set and Stop-Wait Position

#### 4.5.1. Establishing Complete Graph

A complete graphG (Sink, Sc, Sp) is established by the MC. It is composed of the sink node, charging sensor set Sc, and stopping position Sp. In addition, any two points are connected by edges. The MC will construct the Hamiltonian path based on the established complete graph. Initially, the MC starts from the sink node and traverses the charging sensor set Sc = <s1, s2, …, sq> to charge the sensor nodes. After the sensors are charged by the MC, the MC will move to stop position Sp as a mobile sink for data collection. The mobile rechargeable sensor network performs routing planning according to the location of sink nodes and the stop position of the MC.


#### 4.5.2. Determining the Stop-Wait Charging Sensor Set

After the charging sensor setSc is determined, to be able to charge more sensor nodes, the sensor nodes that need to be charged in the next round are also added to this charging task. According to the charging task interval, the MC selects the nodes that need to be charged in the next round as the stop-wait charging sensor nodes. When the survival time of sensor node si meets Tcti < τi′ < 2Tcti, the si node is added to the stop-wait sensor charging set and the stop-wait charging sensor set is determined to be S2,c = <s2,1, s2,2, …, s2,w>.


#### 4.5.3. Determining the Stop-Wait Position

In this paper, the stop-wait positions refer to the positions where the MC and stop-wait charging sensor nodes meet to perform cooperative charging during the mobile charging process of the MC in the specified path. When the MC is moving, it will evaluate the time to reach the stop-wait position according to the moving speed of the MC and the distance between the MC and the stop-wait position. Then, the MC will send this information to the stop-wait charging sensor nodes on the path. The stop-wait charging sensor nodes will move according to the received information. Finally, the MC will meet with them at the stop-wait positions to charge the stop-wait charging sensor nodes. To reduce mobile energy consumption, it is important to determine reasonable stop-wait positions. The set of edges in complete graphG(Sink, Sc, Sp) is defined as E(G) = (E1, E2, …, E(q+1) (q+2)/2). Here, q is the number of charging sensor nodes, and the number of edges in complete graph G(Sink, Sc, Sp) is (q + 1) (q + 2)/2. The stop-wait position is the position with the shortest distance from the stop-wait sensor node to the edge set E(G) of graph G(Sink, Sc, Sp). The shortest distance d(s2,i) from the stop-wait sensor node s2,i to the edge set E(G) can be calculated as in the following formula:(17)ds2,i=minu=1q+2q+1/2ds2,i,Eu,where Eu is an edge of E(G) and Eu ϵ E(G). The shortest distance from the stop-wait sensor node s2,i to the edge Eu is defined as d(s2,i, Eu). The vector algorithm is used to calculate the shortest distance and determine the stop-wait position. Because of the directionality of the vector, the judgment of the direction can be obtained directly according to its sign, which makes the calculation of the shortest distance and the determination of the stop-wait position easy to solve. Especially when the amount of data to be calculated is large, this method has obvious advantages. d(s2,i, Eu) can be calculated as follows:(18)ds2,i,Eu=su−1s2,i⟶,ifψ≤0,sus2,i⟶,ifψ≥1,s2,pis2,i⟶,otherwise.Thed(s2,i, Eu) is described in Figure 1. The unit vector in the direction of su−1su⟶ is su−1su⟶/su−1su⟶. su−1s2,i⟶,su−1su⟶ is the inner product of two vectors, and su−1s2,i⟶,su−1su⟶=su−1s2,i⟶⋅su−1su⟶cosθ, where θ is the angle between the vectors su−1s2,i⟶ and su−1su⟶ and su−1s2,i⟶ and su−1su⟶ are modules of vectors su−1s2,i⟶ and su−1su⟶, respectively.The length ofsu−1s2,pi⟶ is su−1s2,i⟶⋅su−1su⟶/su−1su⟶=su−1s2,i⟶⋅su−1su⟶cosθ/su−1su⟶. The projection vector of su−1s2,i⟶ in the su−1s2,i⟶ direction is su−1s2,pi⟶, and s2, pi is the projection point. The shortest distance is calculated according to the ratio ψ of the projection vector su−1s2,i⟶ to the vector su−1su⟶. The ratio ψ can be calculated as ψ=su−1s2,i⟶⋅su−1su⟶/su−1su⟶⋅su−1su⟶. In Figure 2(a), the stop-wait position of the MC in the edge Eu is s2,pi when 0 < ψ < 1. In Figure 2(b), the stop-wait position of the MC in the edge Eu is su when ψ ≥ 1. In Figure 2(c), the stop-wait position of the MC in the edge Eu is su−1 when ψ ≤ 0.Figure 2
The shortest distance from the stop-wait sensor nodes2,i to the edge set Eu: (a) the shortest distance d(s2,i, E(u)) when 0 < ψ < 1; (b) the shortest distance d(s2,i, E(u)) when ψ > 1; (c) The shortest distance d(s2,i, E(u)) when ψ ≤ 0.
(a)(b)(c)


#### 4.5.4. Charging Quantity of Stop-Wait Charging Sensors

The mobile energy consumption of the stop-wait charging sensor nodes is considered in the cooperative charging and the charging quantity of the stop-wait charging sensor nodes2,i can be calculated by the MC as follows:(19)b2,i,c=τ2,iTctil∗Tcti∗e2,i−b2,i′+2ds2,iec,2,i,ifτ2,iTctilTctie2,i+2ds2,iec,2,i≤b2,i,b2,i−b2,i′+ds2,iec,2,i,else.The mobile energy consumption of the stop-wait sensor nodes2,i moving from its location to the stop-wait position is d(s2,i)ec,2,i, where ec,2,i is the energy consumption per unit distance of sensor node s2,i. ⌊τ2,i/Tcti⌋ is the number of charging task intervals that sensor node s2,i can work at full charge. When the stop-wait charging sensor nodes s2,i and the MC meet at the stop-wait position, the MC will supplement this part of the mobile energy to the stop-wait charging sensor node.


#### 4.5.5. Updating the Stop-Wait Charging Sensor Set

To avoid invalid charging of the stop-wait charge sensor nodes, when the stop-wait charging sensor node occurs as follows, it will be removed from the set of stop-wait charging sensors.The power of the stop-wait charging sensor node cannot reach the stop-wait position, that isd(s2,i)ec,2,i > b2,i′The moving energy consumption of the stop-wait sensor is greater than its charging capacity, that is, 2 ∗d(s2,i)ec,2,i > b2,i,cThe lifetime of the stop-wait charging sensor node returning to the original position after charging is less than 2Tcti, that is, ⌊τi/Tcti⌋ ∗ Tcti ∗ e2,i + 2d(s2,i)ec,2,i > b2,iIf the stop-wait charging sensor node has the above-mentioned situation, the MC will remove it from the set of stop-wait charging sensors and its corresponding stop-wait position.


### 4.6. Establishing the Hamiltonian Path

The mobile energy consumption of the stop-wait sensors2,i and the MC are defined as the weight of the edges in the complete graph G(Sink, Sc, Sp). The two charging sensors are defined as si, sj, si, sj ∈ Sc, and i ≠ j. The weight of edge (si, sj) is defined as Dh(si, sj) = d(si,sj)ec + d(s2,i)ec,2,i. Here, d(si,sj) is the Euclidean distance between si and sj. d(s2,i) is the moving distance of the stop-wait charging sensor s2,i from the original position to the stop-wait position. ec is the mobile energy consumption per unit distance of the MC, and ec,2,i is the mobile energy consumption per unit distance of the stop-wait charging sensor s2,i.According to graphG(Sink, Sc, Sp) and the weights of edges in the graph, the path is selected to minimize the total energy consumption. The essence of this problem is to find a Hamiltonian path with minimum weight in an undirected complete graph with weights, which is a NP complete problem. The proof of a NP complete problem is as follows.Theorem 1.
The mobile stop-wait charging path problem of MC in MWRSN is a NP complete problem.Proof:.
To prove that the mobile stop-wait charging path problem of MC in MWRSN is NP, we first prove that a special case of the problem is a NP complete problem. The special case of constructing the mobile stop-wait charging path problem is as follows.
The distanceDh(si,sj) between each charging sensor and sink and stop position Sp is known. MC should start from the location of the sink node to q charging sensor nodes to charge them, go to stop position Sp to collect data as sink node, and return to the starting node after completion.
If charging nodes, sink node, and stop positionSp are defined as cities, MC is defined as traveling salesman. The distance Dh(si, sj) between each charging sensor and sink and stop position Sp is defined as the distance between cities. Then, the special case is equivalent to the traveling salesman problem (TSP). TSP is a NP complete problem, so this special case is a NP complete problem. Therefore, the mobile stop-wait charging path problem is a NP complete problem.
Due to the imbalance of data transmission tasks in WSN, the number of sensor nodes that need to be charged in each round is smaller than that of the whole network. A simple, practical, and suitable small-scale C-W saving algorithm is selected to solve the Hamiltonian path in this paper. This algorithm was proposed by Clarke and Wright to solve the traveling salesman problem, but it does not consider various constraints. Therefore, it is necessary to consider the energy consumption of the MC and power parameters to improve the C-W algorithm to solve the Hamiltonian path problem of mobile charging.
LetV(G) = (s0, s1, s2, …, sq) be the set of vertices in graph G(Sink, Sc, Sp), where s0 is the sink node. The saving value between any two vertices is CS(si, sj) = Dh(s0, si) + Dh(s0, sj) − Dh(si, sj), where si, sj ∈ Sc and i ≠ j. The larger the CS(si, sj) is, the greater the reduction in the total cost of connecting si and sj is. When constructing the path, it is sorted in descending order according to the size of CS(si, sj). The specific steps of establishing the Hamiltonian path of MC based on the C-W algorithm are as follows:Step 1: the saving valueCS(si, sj) is calculated and sorted in descending order according to the size of CS(si, sj).Step 2: determine whether sensor nodessiand sj corresponding to the maximum edge of CS(si, sj) in the sequence satisfy the following conditions.If sensor nodessi and sj are not on the established path, then si and sj can be connected. After connecting, the path is <s0 ⟶ si ⟶ sj ⟶ s0> and turns to Step 3.If sensor nodessi and sj are on the established path but not the inner point in the line (which means that the node is not directly connected to source point s0), then connect them and turn to Step 3.If the sensor nodessi and sj are on the established path and all not inner points on the line, then connect them and turn to Step 3.If the sensor nodessi and sj are on the established path but not the inner point on the line, then do not connect them and turn to Step 4.Step 3: The sum mobile energy consumption to traverse the connected path is calculated by MCSumEG,c,moh, and the sum energy of the sensor nodes needs to be charged in the path SumbG,c. If SumEG,c,moh+SumbG,c>P′ (which means that the remaining power of MC P′ is insufficient to complete the charging of this path), the MC removes the path from sensor node si to other nodes. Then, turn to Step 5; otherwise, turn to Step 4.Step 4: The MC removes the path from sensor nodesi to other nodes. When all the paths of charging sensors are removed, the complete Hamiltonian path is obtained and the algorithm terminates. Otherwise, the MC selects the node with the maximum saving value from the path of sensor nodes not removed and turns to Step 2.Step 5: When the remaining power of the MC is enough to reach the sink node, the MC connects the sink node to the next path node of sensor nodesi. When the remaining power of the MC cannot reach the sink node, the MC removes sensor node si and the previous path node of sensor node si is selected to connect with the sink node. Then, the MC replenishes the power at the sink node, and after electricity replenishment is completed, the MC establishes the complete graph composed of the sink node, the stop position, and the remaining unconnected nodes. Return to Step 1 and reestablish the Hamiltonian path.


### 4.7. Cooperative Charging

According to the established Hamiltonian path, the MC moves along edgesE1 = <s0, s1>, E2 = <s1, s2>, …, Eq = <sq−1, sq>, Eq+1 = <sq, s0>. In the beginning, the MC starts from the sink (s0) node, and when there is a stop-wait position at edge E1, the MC stops at this position and meets with stop-wait charging sensor nodes s2,1 to charge. After charging the stop-wait charging sensor nodes s2,c, the MC moves to the position of charging sensor node s1 and charges s1. The MC will traverse the edges E(G) = (E1, E2, …, Eq+1) and charge the sensor node.To save charging scheduling time, according to the position and moving speed of the MC, the time to reach the stop-wait position is calculated by the stop-wait charging sensors2,i of S2,c. The stop-wait charging sensor s2,i adjusted its moving speed to ensure that it reached the stop-wait position at the same time as the MC. Then, the stop-wait sensor nodes meet with the MC at the stop-wait position to charge the sensor nodes. This method can save the mobile energy consumption of the MC and improve the charging efficiency. Finally, after the MC charges the stop-wait sensor nodes in the path, the stop-wait charging sensor nodes will return to their original positions. The MC continues to traverse the path of the Hamiltonian loop and charge the sensor nodes.The MC and stop charging sensor nodes will send their location information to their neighbor sensor nodes during the mobile charging process. When the neighboring sensor nodes receive the location information, they will share it with other sensor nodes. The sensor nodes in the network reconstruct the network topology according to the location of the MC, stop-wait charging sensor nodes, and sink nodes. When the MC completes the charging task, they will return to the stop position and wait for the next round of charging task scheduling. At this point, the MC will perform collaborative data collection as a sink node, and the collected data will be transmitted by 4G or 5G technology to the sink node or Data center. The MC will also send its location information to its neighboring sensor nodes. The sensor nodes in the network replan their routing paths according to the location of the sink node and the MC to reduce the excessively long path from some nodes to sink nodes, thus reducing network energy consumption.


### 4.8. Algorithm Description and Analysis

The description of the MWRSN charging task coordination algorithm based on the Hamiltonian path is shown in Algorithm1.Algorithm 1: The MWRSN charging task cooperative algorithm based on the Hamiltonian path (STCI-TR).
(1)
The sensor nodesi initializes the IDi, li and vi(2)
Initial network topology of the MWRSN(3)
while (∃bi′/bi < ω) do(4)
The sensor nodesi send charging request message (CRequest)(5)
MC calculatesTcti and Tl according to bi′, li, ω after receiving CRequest(6)
MC calculates its stop position (xsp0, ysp0)(7)
MC calculatesTcti and Tl according to its stop position(8)
for (i = 1, i++, i ≤ n) do(9)
if (τi′ < Tl) do(10)
Thesi is added to set Sc = <s1, s2, …, sq > by MC, where q ≤ n(11)
MC calculates the charging power of the sensors in setSc(12)
end if(13)
if (Tl < τi′ < 2 ∗ Tl) do(14)
MC establishes theG(Sp, Sc, Sink) and determines the set S2,c(15)
MC determines stop-wait position, and charging power ofS2,c(16)
end if(17)
end for(18)
MC establishes the Hamiltonian path according to sectionE of the part III(19)
MC moves along edgeE1 = <s0, s1>, E2 = <s1, s2>, …, Eq = <sq−1, sq>, Eq+1 = <sq, s0>(20)
if (There are stop-wait positions in edge E1)then(21)
Stop-wait sensors2,i meets with MC for cooperative charging(22)
After thes2,i is charged, it will return to its original positions(23)
end if(24)
After MC completes charging task, it will return to stop position(25)
end whileTable2 shows a comparison of the time complexity using the DPMCS [21], MUC [34], BNRS [35], VN-MOAC [36], and STCI-TR algorithms. The nt is defined as the number of time steps in each episode and nm is the number of episodes.Table 2
Simulation parameters.
AlgorithmMaximum problem sizeTime complexityMUC6.5n2 + 23.5n + 9O(n2)BNRS5n2 + 12n + 3O(n2)DPMCS8nt ∗ nm + 2nm + 2O(n2)VN-MOACn + n2 ∗ lg n2O(n2 lg n2)STCI-TR3.5n2 + 13.5n + 5O(n2)The time complexity of the STCI-TR algorithm isO(n2). The number of charging sensors q and the stop-wait charging sensor w are the problem size. The time complexity of the shortest distance d(s2,i) with the number of sensors q is T(q) = (q + 2) (q + 1)/2. The time complexity to compute the saving value CS(si, sj) with the number of sensors q and the stop-wait charging sensor w is T(q + w) = 3(q + w + 1)2. So the time complexity of the algorithm is O(n2).The algorithm example is shown in Figure3. In the power grid substation field, the substation inspection robots are used for condition monitoring of electrical equipment. The mobile vehicle can be integrated with data collection equipment and the energy transmitter as MC to charge these substation inspection robots. The sink node is used for data aggregation and transfer the data to the substation monitoring center. MC also can replenish the power at the sink node.Figure 3
Schematic diagram of the STCI-TR algorithm example.We assumed that there are 12 substation inspection robots as mobile rechargeable sensor nodes (s1, s2, …, s12) deployed in a two-dimensional scene, and the MC starts from the position of the sink node and charges the sensor node. At the beginning of the algorithm, we assumed that the power of sensor node s1 is lower than the low power indicator percentage ω, and the charging task request information CRequest is sent to the MC. After the MC receives the charging task request, the MC collects the remaining power bi′, position information li,, and the percentage of power. Then, MC calculates the charging cycle τi and the actual lifetime τi′ of the sensor node.The MC determines its stop position(1)Sp in the first round. The MC determines the charging sensor set and selects the charging sensor set (1)Sc = (s1, s2, s3, s4, s5) in this example. The MC determines the stop-wait charging sensor set and corresponding stop-wait position. The selected stop-wait set is (1)S2,c = (s6, s7, s8) and corresponding stop-wait positions are s2,p6, s2,p7, s2,p8. The Hamiltonian path <Sink ⟶ s1 ⟶ s2 ⟶ s3 ⟶ s4 ⟶ s5 ⟶ (1)Sp ⟶ Sink> is established.The MC moves to charge the sensor nodes. The MC moves along edgesE1 = <s0, s1>, E2 = <s1, s2>, E3 = <s2, s3>, E4 = <s3, s4>, E5 = <s4, s5>, E6 = <s5, (1)Sp>, and E7 = <(1)Sp, s0>. In the initial stage, the MC starts from sink node (s0) to s1, and there is no stop-wait position in E1. The MC moves directly to s2, and there is stop-wait position s2,p6 in E2. Then, the MC moves to s2,p6 and meets this position with sensor S2,1 to charge. When sensor S2,1 is charged by the MC, the MC will continue to move until the charging of sensor nodes in Sc and S2,c is completed. Finally, the MC moves along E6 = <s5, (1)Sp> to stop position (1)Sp for data collection.


### 4.9. Main Symbols in Section4

The main symbols in Section4 are shown in Table 3.Table 3
Table of main symbols in Section4.
SymbolParameterSsService group of the sinkSmService group of the MCsi,sSensor node is served by the sink nodesj,mcSensor node is served by the MCXjDecision variable (0 or 1)Di,sAmount of data sent per unit time bysi,s in the Ss (bit/s)Di,mcAmount of data sent per unit time bysj,mc in the Sm (bit/s)ei,sThe unit energy consumption of sensors in theSs (J/s)ej,mcThe unit energy consumption of sensors in theSs(J/s)bi,s′The actual remaining power of sensor nodes in theSs(J)bj,mc′The actual remaining power of sensor nodes in theSm (J)di,sEuclidean distance from sensor nodesi,s to the sink (m)dj,mcEuclidean distance from sensor nodesj,mc to the MC (m)τi,s′Remaining lifetime of sensorsi,s (s)τi,mc′Remaining lifetime of sensorsj,mc (s)nsThe number of sensor nodes in theSsnmcThe number of sensor nodes in theSmLmc,0The initial point of the MC (0, 0)Lmc,tThe location of the MC after iterativet-roundSpThe MC stop positionScThe charging setbi,cThe charging power of sensorsiGComplete graphG (Sink, Sc, Sp) established by MCS2,cThe stop-wait sensor charging set, (s2,i ϵ S2,c)E(G)The set of edges in complete graphG (Sink, Sc, Sp)QThe number of charging sensor nodesd(s2,i)The shortest distance from thes2,i to the edge set E(G)d(s2,i, Eu)The shortest distance from thes2,i to the edge EuΘThe angle between the vectorssu−1s2,i⟶ and su−1su⟶ΨThe ratio of the projection vectorsu−1s2,i⟶ to su−1su⟶b2,i,cThe charging quantity of the stop-wait charging sensor nodes2,iec,2,iThe energy consumption per unit distance of sensor nodes2,iDh(si, sj)The weight of edge(si, sj)V(G)The set of vertices in graphG(Sink, Sc, Sp)CS(si, sj)The saving value between verticessi and sjSumEG,c,mohThe sum mobile energy consumption to traverse the connected pathSumbG,cThe sum energy of the sensors needs to be charged in pathP′The remaining power of MC


## 4.1. Definitions and Assumptions

The definitions used in the cooperative mobile recharge method of MWRSN are as follows:Thenetwork lifetime is the time when the first node in the wireless sensor network runs out of energy [22]Thecharging task interval is the time from the beginning of a charging task to the beginning of the next charging task for the MC in the sensor networkThestop position is the best location for the MC as a mobile sink node to collect data in WRSN after the charging scheduling task is completed by the MCThestop-wait position is the location where the MC and the stop-wait charging sensor nodes meet to charge during the process of the MC moving and charging along the specified pathTheenergy usage effectiveness is the ratio of the effective energy obtained by WRSN to the total energy cost of the MC and sensor nodes during the charging process [30]The assumptions in the wireless rechargeable sensor network model are as follows:Assumption 1: the sensor node in the mobile rechargeable sensor network sends a 256 bit packet per second for data transmission.Assumption 2: the sink node and the MC are able to obtain the geographic location (such as through BeiDou, GPS positioning, or other positioning methods) of all nodes in the wireless sensor network.Assumption 3: the connectivity of the mobile rechargeable sensor network is at least 2 connections. This means that at least 2 nodes are deleted to destroy the connectivity of the network.Assumption 4: the coverage of the mobile rechargeable sensor network is at least 2 times the coverage. This means that every point in the monitoring area can be covered by at least 2 sensor nodes.Assumption 5: after the low power prompt of the node in MWRSN, the remaining lifetime of the node can ensure that the MC will arrive at the node. Node failure will not occur due to power exhaustion before charging.


## 4.2. Charging Task Scheduling Request

When the power of sensorsi is less than biω, sensor si will send the charging request message (CRequest (i)) to the MC. After receiving the message CRequest (i), the MC will collect the residual power, geographical location, and low-power indicator percentage of all sensors in the MWRSN. In practical application, the power information of the sensor nodes changes little in a short time. To reduce the unnecessary energy, the sensor will carry its own information (including residual power bi′, geographical location li,, and low power indicator percentage ω) when sending data to sink nodes. The maximum lifetime τi and residual lifetime τi′ of sensor si will be calculated by the MC according to this information. Next, the MC determines its stopping position according to the collected information.


## 4.3. Determining the Stop Position of the MC

The stopping position in this paper refers to the optimal position for the MC to collect data as a mobile sink node after the charging scheduling task is completed. To prolong the network lifetime and reduce the overall energy consumption of the network, after the charging is completed, the MC will move to the stop position as mobile sink nodes for the data acquisition task. The MC will wait for the next round of charging task scheduling at the stop position. The new data transmission path of the MWRSN will be planned according to the movement of the MC and its position. The stop position of the MC will affect the lifetime and energy consumption of wireless rechargeable sensor networks. Therefore, it is a key point of this algorithm to determine the appropriate stopping position.


### 4.3.1. Stop Position Problem of MC

AssumeS = {si: 1, 2, …, n} is the set of WSNs, and the location of mobile wireless sensor node si is li = (xj, yj). The nodes of the wireless rechargeable sensor network are divided into a service group of sink Ss and a service group of MC Sm. When sensor node si,s is served by a sink, si,s ϵ Ss = {si,s: 1, 2, …, ns}, its data are transferred to a sink node through one or more hops; then, the decision variable Xi is 1; otherwise, it is 0. When sensor node sj,mc is served by the MC, sj,mc ϵ Ss = {sj,mc: 1, 2, …, nmc}, its data are transferred to the MC through one or more hops; then, the decision variable Xj is 1; otherwise, it is 0. Di,s and Di,mc are the amount of data sent per unit time by sensor nodes in the service group of the sink and service group of the MC, respectively. ei,s and ej,mc are the unit energy consumption of sensor nodes in the service group of the sink and service group of the MC, respectively. bi,s′ and bj,mc′ are the actual remaining power of the sensor nodes in the service group of the sink and the service group of the MC, respectively. di,s is the Euclidean distance from sensor node si,s to the sink, and dj,mc is the Euclidean distance from sensor node sj,mc to the MC.To reduce energy consumption and prolong the network lifetime, it is necessary for the MC to select the location that has a long remaining lifetime and the minimum total distance from each node. The objective function of this problem is to minimize the total weighted distance from the sink service group node to the sink (the sum of the ratio of Euclidean distancedi,s to remaining lifetime of sensor si,s) and from the MC service group node to the MC (the sum of the ratio of Euclidean distance dj,mc to remaining lifetime of sensor sj,mc). The sink node and the MC can obtain the geographic location (Assumption 2) of sensors in the wireless sensor network and the network uses the GPSR (greedy perimeter stateless routing) protocol. So the sink node and MC can calculate the di,s and dj,mc easily. Di,s and Di,mc can be obtained by the sink node and the MC when they collect the data. The sink node and the MC know the geographic location of the sensor nodes in the wireless sensor network and use the GPSR protocol. According to the network topology, it is easy for the sink node to evaluate and calculate the amount of data received and forwarded by each sensor node. Therefore, ei,s and ej,mc can be calculated by the sink node according to formulas (3)–(5). The problem model of the MC stop position is as follows:(10)min∑i=0nsdi,sXi,sτi,s′+∑j=0nmcdj,mcXj,mcτj,mv′,(11)s.t.∑i=1nXi=ns,(12)∑j=1nXj=nmc,(13)ns+nmc=n,where ∑i=0nsdi,sXi,s/τi,s′ is the sum of the ratio of Euclidean distance di,s to the remaining lifetime τi,s′ of sensor si,s and τi,s′=bi,s′/Di,sei,s. ∑j=0nmcdj,mcXj,mc/τj,mv′ is the sum of the ratio of Euclidean distance dj,mc to the remaining lifetime τi,mc′ of sensor sj,mc, and τi,mc′=bi,mc′/Di,mcei,mc. The number of sensor nodes in the service group of the sink is ns and the number of sensor nodes in the service group of the MC is nmc. The number of nodes in the MWRSN is n. The decision variables Xi and Xj are defined as follows:(14)Xi=1,if sensorsiis served by Sink,0,else.Xj=1,if sensorsjis served by MC,0,else.Constraint formula (11) is the sensor node served by the sink node. Constraint formula (12) is the sensor node served by the MC. Constraint formula (13) ensures that each sensor node can only send data to the nearest sink node or MC, and the sum of the two service group nodes is the number of nodes in the MWRSN.


### 4.3.2. Solution of Stop Position Problem

To quickly obtain the stopping position of the MC, the Newton method with fast convergence is selected to solve the problem. The specific solution process is as follows:Step 1: the MC selects the initial point. The MC node starts from the sink node at the beginning, and the coordinate origin (taking the sink node as the coordinate origin) is selected as the initial point. The initial point is defined asLmc,0(x0, y0) and x0 = y0 = 0. The termination error is ε > 0 and let t = 0.Step 2: the MC calculates the gradient vector. LetfLmc,t=∑i=0nsdi,sXi,s/τi,s′+∑j=0nmcdj,mcXj,mc/τj,mv′. The gradient vector can be calculated as in formula (15). If the magnitude of the gradient vector is less than the termination error ∇fLmc,t≤ε, the iteration is stopped and the position coordinate Lmc,t = (xt, yt) is output. Then, the coordinate value is the stop position Sp, and the algorithm ends. Otherwise, go to Step 3.Step 3: the MC constructs Newtonian directions. MC calculates∇2fLmc,t−1 and constructs Newtonian directions Pt: Pt=−∇2fLmc,t−1∇fLmc,t.Step 4: find the next iteration point. LetLmc,t+1 = Lmc,t + Pt, t = t + 1; return to Step 2.(15)∇fLmc,k=∑jnmcDj,mcej,mcxk−xj,mcXj,mcbj,mc′xk−xj,mc2+yk−yj,mc2∑jnmcDj,mcej,mcyk−yj,mcXj,mcbj,mc′xk−xj,mc2+yk−yj,mc2.


## 4.3.1. Stop Position Problem of MC

AssumeS = {si: 1, 2, …, n} is the set of WSNs, and the location of mobile wireless sensor node si is li = (xj, yj). The nodes of the wireless rechargeable sensor network are divided into a service group of sink Ss and a service group of MC Sm. When sensor node si,s is served by a sink, si,s ϵ Ss = {si,s: 1, 2, …, ns}, its data are transferred to a sink node through one or more hops; then, the decision variable Xi is 1; otherwise, it is 0. When sensor node sj,mc is served by the MC, sj,mc ϵ Ss = {sj,mc: 1, 2, …, nmc}, its data are transferred to the MC through one or more hops; then, the decision variable Xj is 1; otherwise, it is 0. Di,s and Di,mc are the amount of data sent per unit time by sensor nodes in the service group of the sink and service group of the MC, respectively. ei,s and ej,mc are the unit energy consumption of sensor nodes in the service group of the sink and service group of the MC, respectively. bi,s′ and bj,mc′ are the actual remaining power of the sensor nodes in the service group of the sink and the service group of the MC, respectively. di,s is the Euclidean distance from sensor node si,s to the sink, and dj,mc is the Euclidean distance from sensor node sj,mc to the MC.To reduce energy consumption and prolong the network lifetime, it is necessary for the MC to select the location that has a long remaining lifetime and the minimum total distance from each node. The objective function of this problem is to minimize the total weighted distance from the sink service group node to the sink (the sum of the ratio of Euclidean distancedi,s to remaining lifetime of sensor si,s) and from the MC service group node to the MC (the sum of the ratio of Euclidean distance dj,mc to remaining lifetime of sensor sj,mc). The sink node and the MC can obtain the geographic location (Assumption 2) of sensors in the wireless sensor network and the network uses the GPSR (greedy perimeter stateless routing) protocol. So the sink node and MC can calculate the di,s and dj,mc easily. Di,s and Di,mc can be obtained by the sink node and the MC when they collect the data. The sink node and the MC know the geographic location of the sensor nodes in the wireless sensor network and use the GPSR protocol. According to the network topology, it is easy for the sink node to evaluate and calculate the amount of data received and forwarded by each sensor node. Therefore, ei,s and ej,mc can be calculated by the sink node according to formulas (3)–(5). The problem model of the MC stop position is as follows:(10)min∑i=0nsdi,sXi,sτi,s′+∑j=0nmcdj,mcXj,mcτj,mv′,(11)s.t.∑i=1nXi=ns,(12)∑j=1nXj=nmc,(13)ns+nmc=n,where ∑i=0nsdi,sXi,s/τi,s′ is the sum of the ratio of Euclidean distance di,s to the remaining lifetime τi,s′ of sensor si,s and τi,s′=bi,s′/Di,sei,s. ∑j=0nmcdj,mcXj,mc/τj,mv′ is the sum of the ratio of Euclidean distance dj,mc to the remaining lifetime τi,mc′ of sensor sj,mc, and τi,mc′=bi,mc′/Di,mcei,mc. The number of sensor nodes in the service group of the sink is ns and the number of sensor nodes in the service group of the MC is nmc. The number of nodes in the MWRSN is n. The decision variables Xi and Xj are defined as follows:(14)Xi=1,if sensorsiis served by Sink,0,else.Xj=1,if sensorsjis served by MC,0,else.Constraint formula (11) is the sensor node served by the sink node. Constraint formula (12) is the sensor node served by the MC. Constraint formula (13) ensures that each sensor node can only send data to the nearest sink node or MC, and the sum of the two service group nodes is the number of nodes in the MWRSN.


## 4.3.2. Solution of Stop Position Problem

To quickly obtain the stopping position of the MC, the Newton method with fast convergence is selected to solve the problem. The specific solution process is as follows:Step 1: the MC selects the initial point. The MC node starts from the sink node at the beginning, and the coordinate origin (taking the sink node as the coordinate origin) is selected as the initial point. The initial point is defined asLmc,0(x0, y0) and x0 = y0 = 0. The termination error is ε > 0 and let t = 0.Step 2: the MC calculates the gradient vector. LetfLmc,t=∑i=0nsdi,sXi,s/τi,s′+∑j=0nmcdj,mcXj,mc/τj,mv′. The gradient vector can be calculated as in formula (15). If the magnitude of the gradient vector is less than the termination error ∇fLmc,t≤ε, the iteration is stopped and the position coordinate Lmc,t = (xt, yt) is output. Then, the coordinate value is the stop position Sp, and the algorithm ends. Otherwise, go to Step 3.Step 3: the MC constructs Newtonian directions. MC calculates∇2fLmc,t−1 and constructs Newtonian directions Pt: Pt=−∇2fLmc,t−1∇fLmc,t.Step 4: find the next iteration point. LetLmc,t+1 = Lmc,t + Pt, t = t + 1; return to Step 2.(15)∇fLmc,k=∑jnmcDj,mcej,mcxk−xj,mcXj,mcbj,mc′xk−xj,mc2+yk−yj,mc2∑jnmcDj,mcej,mcyk−yj,mcXj,mcbj,mc′xk−xj,mc2+yk−yj,mc2.


## 4.4. Determining the Charging Sensor Set

After the MC stop position is determined, the MC calculates the charging task intervalTcti according to its stop position and selects the sensor node. First, the sink node collects information such as the location, residual power, and battery capacity of sensors in the MWRSN. Then, the MC predicts the data transmission path and transmission energy consumption of the sensor nodes according to the information collected by the sink node. The lifetime of the MWRSN Tl and charging task interval Tcti can be calculated according to formulas (1) and (2). Finally, according to the calculated charging task interval Tcti, the MC selects the sensor node as the element in the charging set SC of the current scheduling cycle. When τi′ < Tcti, the remaining lifetime of sensor node si is less than the charging task interval. Then, the node is added to the charging sensor set Sc = <s1, s2, …, sq>.After determining the charging sensor setSc, the charging quantity of each charging sensor node in the current round of the charging task should be calculated by the MC. To make the MC charge more sensor nodes, in this model, the MC is not always fully charged when charging the sensor node. The charging task interval is considered, and the charging power of sensor si is calculated based on the number of charging task intervals that sensor node si can work at full charge. The charging power of sensor si is defined as bi,c and can be calculated in the following formula:(16)bi,c=τiTcti∗Tcti∗ei−bi′,where bi′ is the remaining battery power of sensor si and ei is the average unit transmission energy consumption of sensor si. ⌊τi/Tcti⌋ is the number of charging task intervals that sensor node si can work at full charge.


## 4.5. Determining Stop-Wait Charging Sensor Set and Stop-Wait Position

### 4.5.1. Establishing Complete Graph

A complete graphG (Sink, Sc, Sp) is established by the MC. It is composed of the sink node, charging sensor set Sc, and stopping position Sp. In addition, any two points are connected by edges. The MC will construct the Hamiltonian path based on the established complete graph. Initially, the MC starts from the sink node and traverses the charging sensor set Sc = <s1, s2, …, sq> to charge the sensor nodes. After the sensors are charged by the MC, the MC will move to stop position Sp as a mobile sink for data collection. The mobile rechargeable sensor network performs routing planning according to the location of sink nodes and the stop position of the MC.


### 4.5.2. Determining the Stop-Wait Charging Sensor Set

After the charging sensor setSc is determined, to be able to charge more sensor nodes, the sensor nodes that need to be charged in the next round are also added to this charging task. According to the charging task interval, the MC selects the nodes that need to be charged in the next round as the stop-wait charging sensor nodes. When the survival time of sensor node si meets Tcti < τi′ < 2Tcti, the si node is added to the stop-wait sensor charging set and the stop-wait charging sensor set is determined to be S2,c = <s2,1, s2,2, …, s2,w>.


### 4.5.3. Determining the Stop-Wait Position

In this paper, the stop-wait positions refer to the positions where the MC and stop-wait charging sensor nodes meet to perform cooperative charging during the mobile charging process of the MC in the specified path. When the MC is moving, it will evaluate the time to reach the stop-wait position according to the moving speed of the MC and the distance between the MC and the stop-wait position. Then, the MC will send this information to the stop-wait charging sensor nodes on the path. The stop-wait charging sensor nodes will move according to the received information. Finally, the MC will meet with them at the stop-wait positions to charge the stop-wait charging sensor nodes. To reduce mobile energy consumption, it is important to determine reasonable stop-wait positions. The set of edges in complete graphG(Sink, Sc, Sp) is defined as E(G) = (E1, E2, …, E(q+1) (q+2)/2). Here, q is the number of charging sensor nodes, and the number of edges in complete graph G(Sink, Sc, Sp) is (q + 1) (q + 2)/2. The stop-wait position is the position with the shortest distance from the stop-wait sensor node to the edge set E(G) of graph G(Sink, Sc, Sp). The shortest distance d(s2,i) from the stop-wait sensor node s2,i to the edge set E(G) can be calculated as in the following formula:(17)ds2,i=minu=1q+2q+1/2ds2,i,Eu,where Eu is an edge of E(G) and Eu ϵ E(G). The shortest distance from the stop-wait sensor node s2,i to the edge Eu is defined as d(s2,i, Eu). The vector algorithm is used to calculate the shortest distance and determine the stop-wait position. Because of the directionality of the vector, the judgment of the direction can be obtained directly according to its sign, which makes the calculation of the shortest distance and the determination of the stop-wait position easy to solve. Especially when the amount of data to be calculated is large, this method has obvious advantages. d(s2,i, Eu) can be calculated as follows:(18)ds2,i,Eu=su−1s2,i⟶,ifψ≤0,sus2,i⟶,ifψ≥1,s2,pis2,i⟶,otherwise.Thed(s2,i, Eu) is described in Figure 1. The unit vector in the direction of su−1su⟶ is su−1su⟶/su−1su⟶. su−1s2,i⟶,su−1su⟶ is the inner product of two vectors, and su−1s2,i⟶,su−1su⟶=su−1s2,i⟶⋅su−1su⟶cosθ, where θ is the angle between the vectors su−1s2,i⟶ and su−1su⟶ and su−1s2,i⟶ and su−1su⟶ are modules of vectors su−1s2,i⟶ and su−1su⟶, respectively.The length ofsu−1s2,pi⟶ is su−1s2,i⟶⋅su−1su⟶/su−1su⟶=su−1s2,i⟶⋅su−1su⟶cosθ/su−1su⟶. The projection vector of su−1s2,i⟶ in the su−1s2,i⟶ direction is su−1s2,pi⟶, and s2, pi is the projection point. The shortest distance is calculated according to the ratio ψ of the projection vector su−1s2,i⟶ to the vector su−1su⟶. The ratio ψ can be calculated as ψ=su−1s2,i⟶⋅su−1su⟶/su−1su⟶⋅su−1su⟶. In Figure 2(a), the stop-wait position of the MC in the edge Eu is s2,pi when 0 < ψ < 1. In Figure 2(b), the stop-wait position of the MC in the edge Eu is su when ψ ≥ 1. In Figure 2(c), the stop-wait position of the MC in the edge Eu is su−1 when ψ ≤ 0.Figure 2
The shortest distance from the stop-wait sensor nodes2,i to the edge set Eu: (a) the shortest distance d(s2,i, E(u)) when 0 < ψ < 1; (b) the shortest distance d(s2,i, E(u)) when ψ > 1; (c) The shortest distance d(s2,i, E(u)) when ψ ≤ 0.
(a)(b)(c)


### 4.5.4. Charging Quantity of Stop-Wait Charging Sensors

The mobile energy consumption of the stop-wait charging sensor nodes is considered in the cooperative charging and the charging quantity of the stop-wait charging sensor nodes2,i can be calculated by the MC as follows:(19)b2,i,c=τ2,iTctil∗Tcti∗e2,i−b2,i′+2ds2,iec,2,i,ifτ2,iTctilTctie2,i+2ds2,iec,2,i≤b2,i,b2,i−b2,i′+ds2,iec,2,i,else.The mobile energy consumption of the stop-wait sensor nodes2,i moving from its location to the stop-wait position is d(s2,i)ec,2,i, where ec,2,i is the energy consumption per unit distance of sensor node s2,i. ⌊τ2,i/Tcti⌋ is the number of charging task intervals that sensor node s2,i can work at full charge. When the stop-wait charging sensor nodes s2,i and the MC meet at the stop-wait position, the MC will supplement this part of the mobile energy to the stop-wait charging sensor node.


### 4.5.5. Updating the Stop-Wait Charging Sensor Set

To avoid invalid charging of the stop-wait charge sensor nodes, when the stop-wait charging sensor node occurs as follows, it will be removed from the set of stop-wait charging sensors.The power of the stop-wait charging sensor node cannot reach the stop-wait position, that isd(s2,i)ec,2,i > b2,i′The moving energy consumption of the stop-wait sensor is greater than its charging capacity, that is, 2 ∗d(s2,i)ec,2,i > b2,i,cThe lifetime of the stop-wait charging sensor node returning to the original position after charging is less than 2Tcti, that is, ⌊τi/Tcti⌋ ∗ Tcti ∗ e2,i + 2d(s2,i)ec,2,i > b2,iIf the stop-wait charging sensor node has the above-mentioned situation, the MC will remove it from the set of stop-wait charging sensors and its corresponding stop-wait position.


## 4.5.1. Establishing Complete Graph

A complete graphG (Sink, Sc, Sp) is established by the MC. It is composed of the sink node, charging sensor set Sc, and stopping position Sp. In addition, any two points are connected by edges. The MC will construct the Hamiltonian path based on the established complete graph. Initially, the MC starts from the sink node and traverses the charging sensor set Sc = <s1, s2, …, sq> to charge the sensor nodes. After the sensors are charged by the MC, the MC will move to stop position Sp as a mobile sink for data collection. The mobile rechargeable sensor network performs routing planning according to the location of sink nodes and the stop position of the MC.


## 4.5.2. Determining the Stop-Wait Charging Sensor Set

After the charging sensor setSc is determined, to be able to charge more sensor nodes, the sensor nodes that need to be charged in the next round are also added to this charging task. According to the charging task interval, the MC selects the nodes that need to be charged in the next round as the stop-wait charging sensor nodes. When the survival time of sensor node si meets Tcti < τi′ < 2Tcti, the si node is added to the stop-wait sensor charging set and the stop-wait charging sensor set is determined to be S2,c = <s2,1, s2,2, …, s2,w>.


## 4.5.3. Determining the Stop-Wait Position

In this paper, the stop-wait positions refer to the positions where the MC and stop-wait charging sensor nodes meet to perform cooperative charging during the mobile charging process of the MC in the specified path. When the MC is moving, it will evaluate the time to reach the stop-wait position according to the moving speed of the MC and the distance between the MC and the stop-wait position. Then, the MC will send this information to the stop-wait charging sensor nodes on the path. The stop-wait charging sensor nodes will move according to the received information. Finally, the MC will meet with them at the stop-wait positions to charge the stop-wait charging sensor nodes. To reduce mobile energy consumption, it is important to determine reasonable stop-wait positions. The set of edges in complete graphG(Sink, Sc, Sp) is defined as E(G) = (E1, E2, …, E(q+1) (q+2)/2). Here, q is the number of charging sensor nodes, and the number of edges in complete graph G(Sink, Sc, Sp) is (q + 1) (q + 2)/2. The stop-wait position is the position with the shortest distance from the stop-wait sensor node to the edge set E(G) of graph G(Sink, Sc, Sp). The shortest distance d(s2,i) from the stop-wait sensor node s2,i to the edge set E(G) can be calculated as in the following formula:(17)ds2,i=minu=1q+2q+1/2ds2,i,Eu,where Eu is an edge of E(G) and Eu ϵ E(G). The shortest distance from the stop-wait sensor node s2,i to the edge Eu is defined as d(s2,i, Eu). The vector algorithm is used to calculate the shortest distance and determine the stop-wait position. Because of the directionality of the vector, the judgment of the direction can be obtained directly according to its sign, which makes the calculation of the shortest distance and the determination of the stop-wait position easy to solve. Especially when the amount of data to be calculated is large, this method has obvious advantages. d(s2,i, Eu) can be calculated as follows:(18)ds2,i,Eu=su−1s2,i⟶,ifψ≤0,sus2,i⟶,ifψ≥1,s2,pis2,i⟶,otherwise.Thed(s2,i, Eu) is described in Figure 1. The unit vector in the direction of su−1su⟶ is su−1su⟶/su−1su⟶. su−1s2,i⟶,su−1su⟶ is the inner product of two vectors, and su−1s2,i⟶,su−1su⟶=su−1s2,i⟶⋅su−1su⟶cosθ, where θ is the angle between the vectors su−1s2,i⟶ and su−1su⟶ and su−1s2,i⟶ and su−1su⟶ are modules of vectors su−1s2,i⟶ and su−1su⟶, respectively.The length ofsu−1s2,pi⟶ is su−1s2,i⟶⋅su−1su⟶/su−1su⟶=su−1s2,i⟶⋅su−1su⟶cosθ/su−1su⟶. The projection vector of su−1s2,i⟶ in the su−1s2,i⟶ direction is su−1s2,pi⟶, and s2, pi is the projection point. The shortest distance is calculated according to the ratio ψ of the projection vector su−1s2,i⟶ to the vector su−1su⟶. The ratio ψ can be calculated as ψ=su−1s2,i⟶⋅su−1su⟶/su−1su⟶⋅su−1su⟶. In Figure 2(a), the stop-wait position of the MC in the edge Eu is s2,pi when 0 < ψ < 1. In Figure 2(b), the stop-wait position of the MC in the edge Eu is su when ψ ≥ 1. In Figure 2(c), the stop-wait position of the MC in the edge Eu is su−1 when ψ ≤ 0.Figure 2
The shortest distance from the stop-wait sensor nodes2,i to the edge set Eu: (a) the shortest distance d(s2,i, E(u)) when 0 < ψ < 1; (b) the shortest distance d(s2,i, E(u)) when ψ > 1; (c) The shortest distance d(s2,i, E(u)) when ψ ≤ 0.
(a)(b)(c)


## 4.5.4. Charging Quantity of Stop-Wait Charging Sensors

The mobile energy consumption of the stop-wait charging sensor nodes is considered in the cooperative charging and the charging quantity of the stop-wait charging sensor nodes2,i can be calculated by the MC as follows:(19)b2,i,c=τ2,iTctil∗Tcti∗e2,i−b2,i′+2ds2,iec,2,i,ifτ2,iTctilTctie2,i+2ds2,iec,2,i≤b2,i,b2,i−b2,i′+ds2,iec,2,i,else.The mobile energy consumption of the stop-wait sensor nodes2,i moving from its location to the stop-wait position is d(s2,i)ec,2,i, where ec,2,i is the energy consumption per unit distance of sensor node s2,i. ⌊τ2,i/Tcti⌋ is the number of charging task intervals that sensor node s2,i can work at full charge. When the stop-wait charging sensor nodes s2,i and the MC meet at the stop-wait position, the MC will supplement this part of the mobile energy to the stop-wait charging sensor node.


## 4.5.5. Updating the Stop-Wait Charging Sensor Set

To avoid invalid charging of the stop-wait charge sensor nodes, when the stop-wait charging sensor node occurs as follows, it will be removed from the set of stop-wait charging sensors.The power of the stop-wait charging sensor node cannot reach the stop-wait position, that isd(s2,i)ec,2,i > b2,i′The moving energy consumption of the stop-wait sensor is greater than its charging capacity, that is, 2 ∗d(s2,i)ec,2,i > b2,i,cThe lifetime of the stop-wait charging sensor node returning to the original position after charging is less than 2Tcti, that is, ⌊τi/Tcti⌋ ∗ Tcti ∗ e2,i + 2d(s2,i)ec,2,i > b2,iIf the stop-wait charging sensor node has the above-mentioned situation, the MC will remove it from the set of stop-wait charging sensors and its corresponding stop-wait position.


## 4.6. Establishing the Hamiltonian Path

The mobile energy consumption of the stop-wait sensors2,i and the MC are defined as the weight of the edges in the complete graph G(Sink, Sc, Sp). The two charging sensors are defined as si, sj, si, sj ∈ Sc, and i ≠ j. The weight of edge (si, sj) is defined as Dh(si, sj) = d(si,sj)ec + d(s2,i)ec,2,i. Here, d(si,sj) is the Euclidean distance between si and sj. d(s2,i) is the moving distance of the stop-wait charging sensor s2,i from the original position to the stop-wait position. ec is the mobile energy consumption per unit distance of the MC, and ec,2,i is the mobile energy consumption per unit distance of the stop-wait charging sensor s2,i.According to graphG(Sink, Sc, Sp) and the weights of edges in the graph, the path is selected to minimize the total energy consumption. The essence of this problem is to find a Hamiltonian path with minimum weight in an undirected complete graph with weights, which is a NP complete problem. The proof of a NP complete problem is as follows.Theorem 1.
The mobile stop-wait charging path problem of MC in MWRSN is a NP complete problem.Proof:.
To prove that the mobile stop-wait charging path problem of MC in MWRSN is NP, we first prove that a special case of the problem is a NP complete problem. The special case of constructing the mobile stop-wait charging path problem is as follows.
The distanceDh(si,sj) between each charging sensor and sink and stop position Sp is known. MC should start from the location of the sink node to q charging sensor nodes to charge them, go to stop position Sp to collect data as sink node, and return to the starting node after completion.
If charging nodes, sink node, and stop positionSp are defined as cities, MC is defined as traveling salesman. The distance Dh(si, sj) between each charging sensor and sink and stop position Sp is defined as the distance between cities. Then, the special case is equivalent to the traveling salesman problem (TSP). TSP is a NP complete problem, so this special case is a NP complete problem. Therefore, the mobile stop-wait charging path problem is a NP complete problem.
Due to the imbalance of data transmission tasks in WSN, the number of sensor nodes that need to be charged in each round is smaller than that of the whole network. A simple, practical, and suitable small-scale C-W saving algorithm is selected to solve the Hamiltonian path in this paper. This algorithm was proposed by Clarke and Wright to solve the traveling salesman problem, but it does not consider various constraints. Therefore, it is necessary to consider the energy consumption of the MC and power parameters to improve the C-W algorithm to solve the Hamiltonian path problem of mobile charging.
LetV(G) = (s0, s1, s2, …, sq) be the set of vertices in graph G(Sink, Sc, Sp), where s0 is the sink node. The saving value between any two vertices is CS(si, sj) = Dh(s0, si) + Dh(s0, sj) − Dh(si, sj), where si, sj ∈ Sc and i ≠ j. The larger the CS(si, sj) is, the greater the reduction in the total cost of connecting si and sj is. When constructing the path, it is sorted in descending order according to the size of CS(si, sj). The specific steps of establishing the Hamiltonian path of MC based on the C-W algorithm are as follows:Step 1: the saving valueCS(si, sj) is calculated and sorted in descending order according to the size of CS(si, sj).Step 2: determine whether sensor nodessiand sj corresponding to the maximum edge of CS(si, sj) in the sequence satisfy the following conditions.If sensor nodessi and sj are not on the established path, then si and sj can be connected. After connecting, the path is <s0 ⟶ si ⟶ sj ⟶ s0> and turns to Step 3.If sensor nodessi and sj are on the established path but not the inner point in the line (which means that the node is not directly connected to source point s0), then connect them and turn to Step 3.If the sensor nodessi and sj are on the established path and all not inner points on the line, then connect them and turn to Step 3.If the sensor nodessi and sj are on the established path but not the inner point on the line, then do not connect them and turn to Step 4.Step 3: The sum mobile energy consumption to traverse the connected path is calculated by MCSumEG,c,moh, and the sum energy of the sensor nodes needs to be charged in the path SumbG,c. If SumEG,c,moh+SumbG,c>P′ (which means that the remaining power of MC P′ is insufficient to complete the charging of this path), the MC removes the path from sensor node si to other nodes. Then, turn to Step 5; otherwise, turn to Step 4.Step 4: The MC removes the path from sensor nodesi to other nodes. When all the paths of charging sensors are removed, the complete Hamiltonian path is obtained and the algorithm terminates. Otherwise, the MC selects the node with the maximum saving value from the path of sensor nodes not removed and turns to Step 2.Step 5: When the remaining power of the MC is enough to reach the sink node, the MC connects the sink node to the next path node of sensor nodesi. When the remaining power of the MC cannot reach the sink node, the MC removes sensor node si and the previous path node of sensor node si is selected to connect with the sink node. Then, the MC replenishes the power at the sink node, and after electricity replenishment is completed, the MC establishes the complete graph composed of the sink node, the stop position, and the remaining unconnected nodes. Return to Step 1 and reestablish the Hamiltonian path.


## 4.7. Cooperative Charging

According to the established Hamiltonian path, the MC moves along edgesE1 = <s0, s1>, E2 = <s1, s2>, …, Eq = <sq−1, sq>, Eq+1 = <sq, s0>. In the beginning, the MC starts from the sink (s0) node, and when there is a stop-wait position at edge E1, the MC stops at this position and meets with stop-wait charging sensor nodes s2,1 to charge. After charging the stop-wait charging sensor nodes s2,c, the MC moves to the position of charging sensor node s1 and charges s1. The MC will traverse the edges E(G) = (E1, E2, …, Eq+1) and charge the sensor node.To save charging scheduling time, according to the position and moving speed of the MC, the time to reach the stop-wait position is calculated by the stop-wait charging sensors2,i of S2,c. The stop-wait charging sensor s2,i adjusted its moving speed to ensure that it reached the stop-wait position at the same time as the MC. Then, the stop-wait sensor nodes meet with the MC at the stop-wait position to charge the sensor nodes. This method can save the mobile energy consumption of the MC and improve the charging efficiency. Finally, after the MC charges the stop-wait sensor nodes in the path, the stop-wait charging sensor nodes will return to their original positions. The MC continues to traverse the path of the Hamiltonian loop and charge the sensor nodes.The MC and stop charging sensor nodes will send their location information to their neighbor sensor nodes during the mobile charging process. When the neighboring sensor nodes receive the location information, they will share it with other sensor nodes. The sensor nodes in the network reconstruct the network topology according to the location of the MC, stop-wait charging sensor nodes, and sink nodes. When the MC completes the charging task, they will return to the stop position and wait for the next round of charging task scheduling. At this point, the MC will perform collaborative data collection as a sink node, and the collected data will be transmitted by 4G or 5G technology to the sink node or Data center. The MC will also send its location information to its neighboring sensor nodes. The sensor nodes in the network replan their routing paths according to the location of the sink node and the MC to reduce the excessively long path from some nodes to sink nodes, thus reducing network energy consumption.


## 4.8. Algorithm Description and Analysis

The description of the MWRSN charging task coordination algorithm based on the Hamiltonian path is shown in Algorithm1.Algorithm 1: The MWRSN charging task cooperative algorithm based on the Hamiltonian path (STCI-TR).
(1)
The sensor nodesi initializes the IDi, li and vi(2)
Initial network topology of the MWRSN(3)
while (∃bi′/bi < ω) do(4)
The sensor nodesi send charging request message (CRequest)(5)
MC calculatesTcti and Tl according to bi′, li, ω after receiving CRequest(6)
MC calculates its stop position (xsp0, ysp0)(7)
MC calculatesTcti and Tl according to its stop position(8)
for (i = 1, i++, i ≤ n) do(9)
if (τi′ < Tl) do(10)
Thesi is added to set Sc = <s1, s2, …, sq > by MC, where q ≤ n(11)
MC calculates the charging power of the sensors in setSc(12)
end if(13)
if (Tl < τi′ < 2 ∗ Tl) do(14)
MC establishes theG(Sp, Sc, Sink) and determines the set S2,c(15)
MC determines stop-wait position, and charging power ofS2,c(16)
end if(17)
end for(18)
MC establishes the Hamiltonian path according to sectionE of the part III(19)
MC moves along edgeE1 = <s0, s1>, E2 = <s1, s2>, …, Eq = <sq−1, sq>, Eq+1 = <sq, s0>(20)
if (There are stop-wait positions in edge E1)then(21)
Stop-wait sensors2,i meets with MC for cooperative charging(22)
After thes2,i is charged, it will return to its original positions(23)
end if(24)
After MC completes charging task, it will return to stop position(25)
end whileTable2 shows a comparison of the time complexity using the DPMCS [21], MUC [34], BNRS [35], VN-MOAC [36], and STCI-TR algorithms. The nt is defined as the number of time steps in each episode and nm is the number of episodes.Table 2
Simulation parameters.
AlgorithmMaximum problem sizeTime complexityMUC6.5n2 + 23.5n + 9O(n2)BNRS5n2 + 12n + 3O(n2)DPMCS8nt ∗ nm + 2nm + 2O(n2)VN-MOACn + n2 ∗ lg n2O(n2 lg n2)STCI-TR3.5n2 + 13.5n + 5O(n2)The time complexity of the STCI-TR algorithm isO(n2). The number of charging sensors q and the stop-wait charging sensor w are the problem size. The time complexity of the shortest distance d(s2,i) with the number of sensors q is T(q) = (q + 2) (q + 1)/2. The time complexity to compute the saving value CS(si, sj) with the number of sensors q and the stop-wait charging sensor w is T(q + w) = 3(q + w + 1)2. So the time complexity of the algorithm is O(n2).The algorithm example is shown in Figure3. In the power grid substation field, the substation inspection robots are used for condition monitoring of electrical equipment. The mobile vehicle can be integrated with data collection equipment and the energy transmitter as MC to charge these substation inspection robots. The sink node is used for data aggregation and transfer the data to the substation monitoring center. MC also can replenish the power at the sink node.Figure 3
Schematic diagram of the STCI-TR algorithm example.We assumed that there are 12 substation inspection robots as mobile rechargeable sensor nodes (s1, s2, …, s12) deployed in a two-dimensional scene, and the MC starts from the position of the sink node and charges the sensor node. At the beginning of the algorithm, we assumed that the power of sensor node s1 is lower than the low power indicator percentage ω, and the charging task request information CRequest is sent to the MC. After the MC receives the charging task request, the MC collects the remaining power bi′, position information li,, and the percentage of power. Then, MC calculates the charging cycle τi and the actual lifetime τi′ of the sensor node.The MC determines its stop position(1)Sp in the first round. The MC determines the charging sensor set and selects the charging sensor set (1)Sc = (s1, s2, s3, s4, s5) in this example. The MC determines the stop-wait charging sensor set and corresponding stop-wait position. The selected stop-wait set is (1)S2,c = (s6, s7, s8) and corresponding stop-wait positions are s2,p6, s2,p7, s2,p8. The Hamiltonian path <Sink ⟶ s1 ⟶ s2 ⟶ s3 ⟶ s4 ⟶ s5 ⟶ (1)Sp ⟶ Sink> is established.The MC moves to charge the sensor nodes. The MC moves along edgesE1 = <s0, s1>, E2 = <s1, s2>, E3 = <s2, s3>, E4 = <s3, s4>, E5 = <s4, s5>, E6 = <s5, (1)Sp>, and E7 = <(1)Sp, s0>. In the initial stage, the MC starts from sink node (s0) to s1, and there is no stop-wait position in E1. The MC moves directly to s2, and there is stop-wait position s2,p6 in E2. Then, the MC moves to s2,p6 and meets this position with sensor S2,1 to charge. When sensor S2,1 is charged by the MC, the MC will continue to move until the charging of sensor nodes in Sc and S2,c is completed. Finally, the MC moves along E6 = <s5, (1)Sp> to stop position (1)Sp for data collection.


## 4.9. Main Symbols in Section4

The main symbols in Section4 are shown in Table 3.Table 3
Table of main symbols in Section4.
SymbolParameterSsService group of the sinkSmService group of the MCsi,sSensor node is served by the sink nodesj,mcSensor node is served by the MCXjDecision variable (0 or 1)Di,sAmount of data sent per unit time bysi,s in the Ss (bit/s)Di,mcAmount of data sent per unit time bysj,mc in the Sm (bit/s)ei,sThe unit energy consumption of sensors in theSs (J/s)ej,mcThe unit energy consumption of sensors in theSs(J/s)bi,s′The actual remaining power of sensor nodes in theSs(J)bj,mc′The actual remaining power of sensor nodes in theSm (J)di,sEuclidean distance from sensor nodesi,s to the sink (m)dj,mcEuclidean distance from sensor nodesj,mc to the MC (m)τi,s′Remaining lifetime of sensorsi,s (s)τi,mc′Remaining lifetime of sensorsj,mc (s)nsThe number of sensor nodes in theSsnmcThe number of sensor nodes in theSmLmc,0The initial point of the MC (0, 0)Lmc,tThe location of the MC after iterativet-roundSpThe MC stop positionScThe charging setbi,cThe charging power of sensorsiGComplete graphG (Sink, Sc, Sp) established by MCS2,cThe stop-wait sensor charging set, (s2,i ϵ S2,c)E(G)The set of edges in complete graphG (Sink, Sc, Sp)QThe number of charging sensor nodesd(s2,i)The shortest distance from thes2,i to the edge set E(G)d(s2,i, Eu)The shortest distance from thes2,i to the edge EuΘThe angle between the vectorssu−1s2,i⟶ and su−1su⟶ΨThe ratio of the projection vectorsu−1s2,i⟶ to su−1su⟶b2,i,cThe charging quantity of the stop-wait charging sensor nodes2,iec,2,iThe energy consumption per unit distance of sensor nodes2,iDh(si, sj)The weight of edge(si, sj)V(G)The set of vertices in graphG(Sink, Sc, Sp)CS(si, sj)The saving value between verticessi and sjSumEG,c,mohThe sum mobile energy consumption to traverse the connected pathSumbG,cThe sum energy of the sensors needs to be charged in pathP′The remaining power of MC


## 5. Simulation Results and Analysis

In this section, the proposed algorithms are validated by comparing their performances with other mobile recharge schemes in terms of the EUE, network lifetime, and average moving loss per unit time. There is a sink node to collect the information and an MC to charge the sensors in the MWRSN. Simulink in MATLAB 2012 is used to test the algorithm performances. The performance of DPMCS [21], MUC [34], BNRS [35], VN-MOAC [36], and STCI-TR algorithms are compared by simulation. The DPMCS considers the dynamic topology of WSN and uses deep reinforcement learning to determine the schedule of the mobile charger. In BNRS, the moving path of MCs along power banks is optimized so that every power bank can be recharged before falling below a critical threshold. To improve the operation time of the nodes, the energy quota of each node is calculated based on its energy consumption level. The directed coverage subsets with the largest charging gain in WSN are first searched in MUC. Then, the charging anchor points are determined according to the directed coverage subset and the charger movement path is planned. Finally, the constraints of mobile charger energy and charging cycle are considered and the charging time is optimized. In VN-MOAC, charging requirements and data collecting are taken into consideration simultaneously. A one-to-many charging and data collecting model for MC is established with two optimization objectives, maximizing the total energy utilization and minimizing the average delay of data collecting.


### 5.1. Simulation Parameters

In the communication simulation, the transmission rate of the ZigBee 802.15.4 protocol is selected in our simulation model. The detailed simulation parameters are shown in Table4.Table 4
Simulation parameters.
SymbolParameterValuert,iTransmission rate of sensorsi128 kbpsrc,iCommunication radius of sensorsi50 mlpPacket length of the sensor256 biteelecEnergy consumption of the electronic equipment ofl bit50 nJ/bitεfsEnergy consumption of the wireless antenna amplifier10 pJ/bitmcThe mass of MC1.5 kggGravitational acceleration9.8 m/s2μcDynamic friction factor between the MC and the ground0.7ecEnergy consumption per unit distance moved by the MC6.91 J/mmm,iThe mass of sensorsi0.2 kgμm,iDynamic friction factor between the MC and the ground0.47em,iEnergy consumption per unit distance moved by sensorsi0.92 J/mBCBattery capacity of the MC (kJ)80 kJbiInitial power of all of the sensors1000 JThe maximum data transmission rate of this protocol is 250 kbps. The median value (128 kbps) is selected as the simulation parameter. The packet length of ZigBee 802.15.4 protocol ranges from 128 bit to 127 byte. The packet length of the sensor in the simulation islp = 256 bit. Literature [38] proposed an algorithm to generate the unified dataset for the general and some specific applications system models in WSNs. The results produced by the proposed algorithm reflect the pseudorandomness. Therefore, the standard datasets in [38] are used to evaluate our methods and the comparison algorithms. The routing protocol is greedy perimeter stateless routing (GPSR). Fifty sensor nodes are randomly deployed in a 400 × 400 m area. These nodes are subject to a uniform random distribution; that is, the horizontal and vertical coordinates of 50 sensor nodes corresponding to two groups of uniformly distributed random numbers (50 for each group) are generated in 0–400 m, and then, the deployment position is determined. The moving speed of the sensors and MC is 2 m/s according to [34]. We consider the communication energy parameters referenced in [39]. The communication energy parameters are set as eelec = 50 μJ/bit and εfs = 10 nJ/bit. The communication radius is rc,i = 50 m. The initial energy of the sensor is set bi = 1000 J, and the battery capacity of the MC is set BC = 80 KJ according to [36]. The mass of MC is set mc = 1.5 kg, and the mass of sensor si is set mm,i = 0.2 kg. The dynamic friction factor is set μc = μm,i = 0.47 according to [40]. The moving energy consumption of the sensor node es = 0.92 J/m can be calculated according to formula (6). The moving energy consumption of the MC ec = 6.91 J/m can be calculated according to formula (7).


### 5.2. EUE Analysis of the Algorithm

Figure4 shows a comparison of the EUE with different numbers of sensors using the DPMCS, MUC, BNRS [35], VN-MOAC, and STCI-TR algorithms.Figure 4
Comparison of the EUE with different numbers of sensor nodes.In Figure4, the EUE of nodes decreases little with the increase in the number of nodes. This is because the energy consumption increase caused by the movement of the MC during charging accounts for a small proportion of the total energy consumption. The STCI-TR algorithm takes the MC as a sink node for collaborative collection, which improves the network lifetime. Therefore, the EUE of STCI-TR is 17.56% higher than that of MUC and 8.07% higher than that of BNRS. The charging sensor node of the next round is considered in the STCI-TR algorithm for the current charging task scheduling. It avoids the MC charging the node in the next round and reduces the mobile energy consumption of MC. So the EUE of STCI-TR is 4.84% higher than that of DPMCS and 2.94% higher than that of VN-MOAC.Figure5 shows a comparison of the EUE with different battery capacities of sensors using the MUC, BNRS, DPMCS, VN-MOAC, and STCI-TR algorithms. The EUEs of the nodes are all improved with different battery capacities of the sensor. With the increase in the battery capacity of sensor nodes, the energy of the MC primary charge scheduling is increased. However, the energy consumption caused by the movement does not increase at this time. So the EUEs are improved. The STCI-TR algorithm takes the MC as a sink node for collaborative collection and considers the charging sensor node of the next round for the current charging task scheduling. It reduces the network transmission energy consumption and mobile energy consumption of MC. Therefore, the EUE of STCI-TR is 28.54% higher than that of MCU and 14.87% higher than that of BNRS. The scheduling times of the MC are reduced, and the mobile energy consumption is reduced at the same time. So the EUE of STCI-TR is 6.33% higher than that of DPMCS and 4.84% higher than that of VN-MOAC.Figure 5
Comparison of the EUE with different node battery capacities.Figure6 shows the comparison of the EUE with different mobile energy consumption of the MC using the MUC, BNRS, DPMCS, VN-MOAC, and STCI-TR algorithms. The EUEs of all methods decrease with increasing MC mobile energy consumption. This is because the energy consumption increase caused by the movement of the MC during charging accounts for a large proportion of the total energy consumption. So the EUEs are decreased. The STCI-TR algorithm takes the MC as a sink node for a collaborative collection. It reduces the network transmission energy consumption. Therefore, the EUE of STCI-TR is 38.76% higher than that of MUC and 18.64% higher than that of BNRS. The STCI-TR algorithm considers the charging sensor node of the next round for the current charging task scheduling. This method can reduce the mobile energy consumption of MC and the MC scheduling times at the same time. So the EUE of STCI-TR is 9.83% higher than that of DPMCS and 7.05% higher than that of VN-MOAC.Figure 6
Comparison of EUE with different mobile energy consumptions of MC.Figure7 shows the comparison of EUE with different charging efficiencies using the MUC, BNRS, DPMCS, VN-MOAC, and STCI-TR algorithms.Figure 7
Comparison of the EUE with different charging efficiencies.In Figure7, the EUE of nodes is improved with increasing charging efficiency. This is because the charging energy consumption of the MC during charging is reduced with increasing charging efficiency. However, the network transmission energy consumption and the energy consumption caused by the movement do not increase at this time. So the EUEs are improved. The STCI-TR algorithm takes the MC as a sink node for a collaborative collection. It reduces the network transmission energy consumption. Therefore, the EUE of STCI-TR is 19.56% higher than that of MUC and 14.62% higher than that of BNRS. The STCI-TR algorithm considers the charging sensor node of the next round for the current charging task scheduling. This method can reduce the mobile energy consumption of MC and the MC scheduling times at the same time. Therefore, the EUE of STCI-TR is 5.04% higher than that of DPMCS and 2.78% higher than that of VN-MOAC.


### 5.3. Network Lifetime Analysis of the Algorithm

Figure8 shows the comparison of network lifetimes with different numbers of sensor nodes using the MUC, BNRS, DPMCS, VN-MOAC, and STCI-TR algorithms. According to the simulation parameter settings in Table 4 and the transmission energy consumption model of the wireless sensor network in Section 3.3, the lifetime of a single sensor node without moving and one-hop data transmission is approximately 3.125 × 107 s. In Figure 8, the network lifetimes of all methods decrease as the number of sensor nodes increases. This is because the energy consumption of the sensor nodes closest to the sink is increasing and reduces the network lifetime. The STCI-TR algorithm takes the MC as a sink node for a collaborative collection. It reduces the network transmission energy consumption. The STCI-TR can improve the network lifetime and charging task interval. The MC is not considered a sink node for collaborative collection in MCU and BNRS. So they have the same network lifetime. The network lifetime of STCI-TR is 13.08% higher than that of BNRS and MCU. The DPMCS algorithm considers the MC as a sink node to collect the data in the charging process. However, the charging process is shorter than the whole network lifetime and less improved than VN-MOAC and DPMCS. Therefore, the network lifetime of STCI-TR is 10.28% higher than that of DPMCS and 7.04% higher than that of VN-MOAC.Figure 8
Comparison of network lifetime with different numbers of nodes.


### 5.4. Average Network Energy Consumption per Unit Time

Figure9 shows a comparison of the average network energy consumption per unit time with different numbers of sensor nodes using the MUC, BNRS, DPMCS, VN-MOAC, and STCI-TR algorithms. The average network energy consumption per unit time of all methods is improved as the number of sensor nodes increases. This is because the path from some sensor nodes to sink is increasing, and it increases the average network energy consumption per unit time. The STCI-TR algorithm takes the MC as a sink node for a collaborative collection. After the charging and the completion of charging, the route planning is carried out again. It reduces the path length from some sensor nodes to sink and MC and the network transmission energy consumption. The MC is not considered a sink node for collaborative collection in BNRS and MCU, so they have the same average network energy consumption per unit time. The average network energy consumption per unit time of STCI-TR is 6.73% lower than that of BNRS and MCU. The DPMCS and VN-MOAC algorithms consider MC as a sink node to collect the data in the charging process. However, the MC is not used as a sink node for collaborative collection in DPMCS and VN-MOAC after charging scheduling. The STCI-TR algorithm reduces the length of the route path from some sensor nodes to sink and MC before the next round of charging task scheduling requests. So the reduced network energy consumption of DPMCS and VN-MOAC is less than that of STCI-TR. Therefore, the average network energy consumption per unit time of STCI-TR is 2.68% lower than that of VN-MOAC and 4.76% lower than that of DPMCS.Figure 9
Comparison of average network energy consumption with different numbers of nodes.


### 5.5. Average Movement Loss per Unit Time

Figure10 shows a comparison of the average moving loss per unit time with different numbers of sensor nodes using MUC, BNRS, DPMCS, VN-MOAC, and STCI-TR algorithms. The average moving loss per unit time of all methods increases as the number of sensor nodes increases. This is because the mobile energy consumption caused by the MC charging is increasing, and the average mobile loss per unit time is also increasing. The STCI-TR algorithm takes the MC as a sink node for collaborative collection, which improves the network lifetime and reduces the MC scheduling times and average moving loss per unit time at the same time. The MC is not considered a sink node for collaborative collection in MUC and BNRS. This causes the transmission path of some sensor nodes to be too long and increases the network transmission energy consumption. It increases the MC scheduling frequency and average moving loss per unit time. The average moving loss per unit time of STCI-TR is 26.74% lower than that of MCU and 16.96% lower than that of BNRS. The DPMCS and VN-MOAC algorithms consider MC as a sink node to collect the data in the charging process. However, the charging process is shorter than the whole network lifetime. The network transmission energy consumption of DPMCS and VN-MOAC is less reduced than STCI-TR. The STCI-TR algorithm also considers the charging sensor node of the next round for the current charging task scheduling. It can also reduce the mobile energy consumption of MC and the MC scheduling times at the same time. Therefore, the average moving loss per unit time of STCI-TR is 9.95% lower than that of DPMCS and 6.87% lower than that of VN-MOAC.Figure 10
Comparison of average moving loss per unit time with different numbers of nodes.


### 5.6. Average Mobile Energy Consumption

Figure11 shows a comparison of the average mobile energy consumption with different numbers of sensor nodes using MUC, BNRS, DPMCS, VN-MOAC, and STCI-TR algorithms.Figure 11
Comparison of average mobile energy consumption with different numbers of nodes.The average mobile energy consumption of all methods increases as the number of sensor nodes increases. As the number of nodes increases, the number of nodes that need to be charged by MC for each charging schedule also increases. So the moving distance of MC becomes longer and mobile energy consumption caused by the MC is increasing. The STCI-TR algorithm considers the charging sensor node of the next round (the stop-wait sensor nodes) for the current charging task scheduling. In the next round, the number of nodes that need to be charged by MC will be reduced. Therefore, the average mobile energy consumption of STCI-TR is lower than that of MCU, BNRS, DPMCS, and VN-MOAC.


### 5.7. Average Charging Task Scheduling Times

Figure12 shows a comparison of the average charging task scheduling times with different numbers of sensor nodes using MUC, BNRS, DPMCS, VN-MOAC, and STCI-TR algorithms. According to the simulation parameter settings in Table 3, the charging task interval of these algorithms is 2.0 × 106 s (it is the average value of the simulation with 50 sensor nodes). The average charging task scheduling times of all methods decrease as the number of sensor nodes increases. As the number of nodes increases, the mobile energy consumption caused by the MC moving is increasing and the average network energy consumption is also increasing. The STCI-TR algorithm takes the MC as a sink node for a collaborative collection. It reduces the network transmission energy consumption. The MC is not considered a sink node for collaborative collection in MCU and BNRS. So the average charging task scheduling times of STCI-TR is 7.52% higher than that of MCU and 6.81% higher than that of BNRS.Figure 12
Comparison of average charging task scheduling times with different numbers of nodes.The DPMCS and VN-MOAC algorithms consider MC as a sink node to collect the data in the charging process. However, the charging process is shorter than the whole network lifetime. The network transmission energy consumption of DPMCS and VN-MOAC is less reduced than STCI-TR. The STCI-TR algorithm considers the charging sensor node of the next round (the stop-wait sensor nodes) for the current charging task scheduling. In the next round, the number of nodes that need to be charged by MC will be reduced and can also reduce the mobile energy consumption of MC. Therefore, the average charging task scheduling times of STCI-TR is 4.73% higher than that of DPMCS and 2.52% higher than that of VN-MOAC.


### 5.8. Total Travelled Path

Figure13 shows a comparison of the total travelled path with different numbers of sensor nodes using MUC, BNRS, DPMCS, VN-MOAC, and STCI-TR algorithms. The total travelled path of all methods increases as the number of sensor nodes increases. As the number of nodes increases, the number of nodes that need to be charged by MC for each charging schedule also increases. So the moving distance of MC becomes longer and the total travelled path caused by the MC is increasing. The STCI-TR algorithm considers the charging sensor node of the next round (the stop-wait sensor nodes) for the current charging task scheduling. In the next round, the number of nodes that need to be charged by MC will be reduced. Therefore, the total travelled path of STCI-TR is lower than that of MCU, BNRS, DPMCS, and VN-MOAC.Figure 13
Comparison of the total travelled path with different numbers of nodes.


### 5.9. Average Remaining Energy

Figure14 shows a comparison of the average remaining energy with different numbers of sensor nodes using MUC, BNRS, DPMCS, VN-MOAC, and STCI-TR algorithms. The average remaining energy of all methods decreases as the number of sensor nodes increases. As the number of nodes increases, the number of nodes that need to be charged by MC for each charging schedule also increases. So the travelled path of MC becomes longer and the power of MC uses for charging sensors is reduced. The STCI-TR algorithm takes the MC as a sink node for a collaborative collection. After the charging and the completion of charging, the route planning is carried out again. It reduces the path length from some sensor nodes to sink and MC and the network transmission energy consumption. Therefore, the mobile energy consumption of MC and the stop-wait sensor nodes can be at the same time. The average remaining energy of STCI-TR is higher than that of MCU, BNRS, DPMCS, and VN-MOAC.Figure 14
Comparison of average remaining energy with different numbers of nodes.


## 5.1. Simulation Parameters

In the communication simulation, the transmission rate of the ZigBee 802.15.4 protocol is selected in our simulation model. The detailed simulation parameters are shown in Table4.Table 4
Simulation parameters.
SymbolParameterValuert,iTransmission rate of sensorsi128 kbpsrc,iCommunication radius of sensorsi50 mlpPacket length of the sensor256 biteelecEnergy consumption of the electronic equipment ofl bit50 nJ/bitεfsEnergy consumption of the wireless antenna amplifier10 pJ/bitmcThe mass of MC1.5 kggGravitational acceleration9.8 m/s2μcDynamic friction factor between the MC and the ground0.7ecEnergy consumption per unit distance moved by the MC6.91 J/mmm,iThe mass of sensorsi0.2 kgμm,iDynamic friction factor between the MC and the ground0.47em,iEnergy consumption per unit distance moved by sensorsi0.92 J/mBCBattery capacity of the MC (kJ)80 kJbiInitial power of all of the sensors1000 JThe maximum data transmission rate of this protocol is 250 kbps. The median value (128 kbps) is selected as the simulation parameter. The packet length of ZigBee 802.15.4 protocol ranges from 128 bit to 127 byte. The packet length of the sensor in the simulation islp = 256 bit. Literature [38] proposed an algorithm to generate the unified dataset for the general and some specific applications system models in WSNs. The results produced by the proposed algorithm reflect the pseudorandomness. Therefore, the standard datasets in [38] are used to evaluate our methods and the comparison algorithms. The routing protocol is greedy perimeter stateless routing (GPSR). Fifty sensor nodes are randomly deployed in a 400 × 400 m area. These nodes are subject to a uniform random distribution; that is, the horizontal and vertical coordinates of 50 sensor nodes corresponding to two groups of uniformly distributed random numbers (50 for each group) are generated in 0–400 m, and then, the deployment position is determined. The moving speed of the sensors and MC is 2 m/s according to [34]. We consider the communication energy parameters referenced in [39]. The communication energy parameters are set as eelec = 50 μJ/bit and εfs = 10 nJ/bit. The communication radius is rc,i = 50 m. The initial energy of the sensor is set bi = 1000 J, and the battery capacity of the MC is set BC = 80 KJ according to [36]. The mass of MC is set mc = 1.5 kg, and the mass of sensor si is set mm,i = 0.2 kg. The dynamic friction factor is set μc = μm,i = 0.47 according to [40]. The moving energy consumption of the sensor node es = 0.92 J/m can be calculated according to formula (6). The moving energy consumption of the MC ec = 6.91 J/m can be calculated according to formula (7).


## 5.2. EUE Analysis of the Algorithm

Figure4 shows a comparison of the EUE with different numbers of sensors using the DPMCS, MUC, BNRS [35], VN-MOAC, and STCI-TR algorithms.Figure 4
Comparison of the EUE with different numbers of sensor nodes.In Figure4, the EUE of nodes decreases little with the increase in the number of nodes. This is because the energy consumption increase caused by the movement of the MC during charging accounts for a small proportion of the total energy consumption. The STCI-TR algorithm takes the MC as a sink node for collaborative collection, which improves the network lifetime. Therefore, the EUE of STCI-TR is 17.56% higher than that of MUC and 8.07% higher than that of BNRS. The charging sensor node of the next round is considered in the STCI-TR algorithm for the current charging task scheduling. It avoids the MC charging the node in the next round and reduces the mobile energy consumption of MC. So the EUE of STCI-TR is 4.84% higher than that of DPMCS and 2.94% higher than that of VN-MOAC.Figure5 shows a comparison of the EUE with different battery capacities of sensors using the MUC, BNRS, DPMCS, VN-MOAC, and STCI-TR algorithms. The EUEs of the nodes are all improved with different battery capacities of the sensor. With the increase in the battery capacity of sensor nodes, the energy of the MC primary charge scheduling is increased. However, the energy consumption caused by the movement does not increase at this time. So the EUEs are improved. The STCI-TR algorithm takes the MC as a sink node for collaborative collection and considers the charging sensor node of the next round for the current charging task scheduling. It reduces the network transmission energy consumption and mobile energy consumption of MC. Therefore, the EUE of STCI-TR is 28.54% higher than that of MCU and 14.87% higher than that of BNRS. The scheduling times of the MC are reduced, and the mobile energy consumption is reduced at the same time. So the EUE of STCI-TR is 6.33% higher than that of DPMCS and 4.84% higher than that of VN-MOAC.Figure 5
Comparison of the EUE with different node battery capacities.Figure6 shows the comparison of the EUE with different mobile energy consumption of the MC using the MUC, BNRS, DPMCS, VN-MOAC, and STCI-TR algorithms. The EUEs of all methods decrease with increasing MC mobile energy consumption. This is because the energy consumption increase caused by the movement of the MC during charging accounts for a large proportion of the total energy consumption. So the EUEs are decreased. The STCI-TR algorithm takes the MC as a sink node for a collaborative collection. It reduces the network transmission energy consumption. Therefore, the EUE of STCI-TR is 38.76% higher than that of MUC and 18.64% higher than that of BNRS. The STCI-TR algorithm considers the charging sensor node of the next round for the current charging task scheduling. This method can reduce the mobile energy consumption of MC and the MC scheduling times at the same time. So the EUE of STCI-TR is 9.83% higher than that of DPMCS and 7.05% higher than that of VN-MOAC.Figure 6
Comparison of EUE with different mobile energy consumptions of MC.Figure7 shows the comparison of EUE with different charging efficiencies using the MUC, BNRS, DPMCS, VN-MOAC, and STCI-TR algorithms.Figure 7
Comparison of the EUE with different charging efficiencies.In Figure7, the EUE of nodes is improved with increasing charging efficiency. This is because the charging energy consumption of the MC during charging is reduced with increasing charging efficiency. However, the network transmission energy consumption and the energy consumption caused by the movement do not increase at this time. So the EUEs are improved. The STCI-TR algorithm takes the MC as a sink node for a collaborative collection. It reduces the network transmission energy consumption. Therefore, the EUE of STCI-TR is 19.56% higher than that of MUC and 14.62% higher than that of BNRS. The STCI-TR algorithm considers the charging sensor node of the next round for the current charging task scheduling. This method can reduce the mobile energy consumption of MC and the MC scheduling times at the same time. Therefore, the EUE of STCI-TR is 5.04% higher than that of DPMCS and 2.78% higher than that of VN-MOAC.


## 5.3. Network Lifetime Analysis of the Algorithm

Figure8 shows the comparison of network lifetimes with different numbers of sensor nodes using the MUC, BNRS, DPMCS, VN-MOAC, and STCI-TR algorithms. According to the simulation parameter settings in Table 4 and the transmission energy consumption model of the wireless sensor network in Section 3.3, the lifetime of a single sensor node without moving and one-hop data transmission is approximately 3.125 × 107 s. In Figure 8, the network lifetimes of all methods decrease as the number of sensor nodes increases. This is because the energy consumption of the sensor nodes closest to the sink is increasing and reduces the network lifetime. The STCI-TR algorithm takes the MC as a sink node for a collaborative collection. It reduces the network transmission energy consumption. The STCI-TR can improve the network lifetime and charging task interval. The MC is not considered a sink node for collaborative collection in MCU and BNRS. So they have the same network lifetime. The network lifetime of STCI-TR is 13.08% higher than that of BNRS and MCU. The DPMCS algorithm considers the MC as a sink node to collect the data in the charging process. However, the charging process is shorter than the whole network lifetime and less improved than VN-MOAC and DPMCS. Therefore, the network lifetime of STCI-TR is 10.28% higher than that of DPMCS and 7.04% higher than that of VN-MOAC.Figure 8
Comparison of network lifetime with different numbers of nodes.


## 5.4. Average Network Energy Consumption per Unit Time

Figure9 shows a comparison of the average network energy consumption per unit time with different numbers of sensor nodes using the MUC, BNRS, DPMCS, VN-MOAC, and STCI-TR algorithms. The average network energy consumption per unit time of all methods is improved as the number of sensor nodes increases. This is because the path from some sensor nodes to sink is increasing, and it increases the average network energy consumption per unit time. The STCI-TR algorithm takes the MC as a sink node for a collaborative collection. After the charging and the completion of charging, the route planning is carried out again. It reduces the path length from some sensor nodes to sink and MC and the network transmission energy consumption. The MC is not considered a sink node for collaborative collection in BNRS and MCU, so they have the same average network energy consumption per unit time. The average network energy consumption per unit time of STCI-TR is 6.73% lower than that of BNRS and MCU. The DPMCS and VN-MOAC algorithms consider MC as a sink node to collect the data in the charging process. However, the MC is not used as a sink node for collaborative collection in DPMCS and VN-MOAC after charging scheduling. The STCI-TR algorithm reduces the length of the route path from some sensor nodes to sink and MC before the next round of charging task scheduling requests. So the reduced network energy consumption of DPMCS and VN-MOAC is less than that of STCI-TR. Therefore, the average network energy consumption per unit time of STCI-TR is 2.68% lower than that of VN-MOAC and 4.76% lower than that of DPMCS.Figure 9
Comparison of average network energy consumption with different numbers of nodes.


## 5.5. Average Movement Loss per Unit Time

Figure10 shows a comparison of the average moving loss per unit time with different numbers of sensor nodes using MUC, BNRS, DPMCS, VN-MOAC, and STCI-TR algorithms. The average moving loss per unit time of all methods increases as the number of sensor nodes increases. This is because the mobile energy consumption caused by the MC charging is increasing, and the average mobile loss per unit time is also increasing. The STCI-TR algorithm takes the MC as a sink node for collaborative collection, which improves the network lifetime and reduces the MC scheduling times and average moving loss per unit time at the same time. The MC is not considered a sink node for collaborative collection in MUC and BNRS. This causes the transmission path of some sensor nodes to be too long and increases the network transmission energy consumption. It increases the MC scheduling frequency and average moving loss per unit time. The average moving loss per unit time of STCI-TR is 26.74% lower than that of MCU and 16.96% lower than that of BNRS. The DPMCS and VN-MOAC algorithms consider MC as a sink node to collect the data in the charging process. However, the charging process is shorter than the whole network lifetime. The network transmission energy consumption of DPMCS and VN-MOAC is less reduced than STCI-TR. The STCI-TR algorithm also considers the charging sensor node of the next round for the current charging task scheduling. It can also reduce the mobile energy consumption of MC and the MC scheduling times at the same time. Therefore, the average moving loss per unit time of STCI-TR is 9.95% lower than that of DPMCS and 6.87% lower than that of VN-MOAC.Figure 10
Comparison of average moving loss per unit time with different numbers of nodes.


## 5.6. Average Mobile Energy Consumption

Figure11 shows a comparison of the average mobile energy consumption with different numbers of sensor nodes using MUC, BNRS, DPMCS, VN-MOAC, and STCI-TR algorithms.Figure 11
Comparison of average mobile energy consumption with different numbers of nodes.The average mobile energy consumption of all methods increases as the number of sensor nodes increases. As the number of nodes increases, the number of nodes that need to be charged by MC for each charging schedule also increases. So the moving distance of MC becomes longer and mobile energy consumption caused by the MC is increasing. The STCI-TR algorithm considers the charging sensor node of the next round (the stop-wait sensor nodes) for the current charging task scheduling. In the next round, the number of nodes that need to be charged by MC will be reduced. Therefore, the average mobile energy consumption of STCI-TR is lower than that of MCU, BNRS, DPMCS, and VN-MOAC.


## 5.7. Average Charging Task Scheduling Times

Figure12 shows a comparison of the average charging task scheduling times with different numbers of sensor nodes using MUC, BNRS, DPMCS, VN-MOAC, and STCI-TR algorithms. According to the simulation parameter settings in Table 3, the charging task interval of these algorithms is 2.0 × 106 s (it is the average value of the simulation with 50 sensor nodes). The average charging task scheduling times of all methods decrease as the number of sensor nodes increases. As the number of nodes increases, the mobile energy consumption caused by the MC moving is increasing and the average network energy consumption is also increasing. The STCI-TR algorithm takes the MC as a sink node for a collaborative collection. It reduces the network transmission energy consumption. The MC is not considered a sink node for collaborative collection in MCU and BNRS. So the average charging task scheduling times of STCI-TR is 7.52% higher than that of MCU and 6.81% higher than that of BNRS.Figure 12
Comparison of average charging task scheduling times with different numbers of nodes.The DPMCS and VN-MOAC algorithms consider MC as a sink node to collect the data in the charging process. However, the charging process is shorter than the whole network lifetime. The network transmission energy consumption of DPMCS and VN-MOAC is less reduced than STCI-TR. The STCI-TR algorithm considers the charging sensor node of the next round (the stop-wait sensor nodes) for the current charging task scheduling. In the next round, the number of nodes that need to be charged by MC will be reduced and can also reduce the mobile energy consumption of MC. Therefore, the average charging task scheduling times of STCI-TR is 4.73% higher than that of DPMCS and 2.52% higher than that of VN-MOAC.


## 5.8. Total Travelled Path

Figure13 shows a comparison of the total travelled path with different numbers of sensor nodes using MUC, BNRS, DPMCS, VN-MOAC, and STCI-TR algorithms. The total travelled path of all methods increases as the number of sensor nodes increases. As the number of nodes increases, the number of nodes that need to be charged by MC for each charging schedule also increases. So the moving distance of MC becomes longer and the total travelled path caused by the MC is increasing. The STCI-TR algorithm considers the charging sensor node of the next round (the stop-wait sensor nodes) for the current charging task scheduling. In the next round, the number of nodes that need to be charged by MC will be reduced. Therefore, the total travelled path of STCI-TR is lower than that of MCU, BNRS, DPMCS, and VN-MOAC.Figure 13
Comparison of the total travelled path with different numbers of nodes.


## 5.9. Average Remaining Energy

Figure14 shows a comparison of the average remaining energy with different numbers of sensor nodes using MUC, BNRS, DPMCS, VN-MOAC, and STCI-TR algorithms. The average remaining energy of all methods decreases as the number of sensor nodes increases. As the number of nodes increases, the number of nodes that need to be charged by MC for each charging schedule also increases. So the travelled path of MC becomes longer and the power of MC uses for charging sensors is reduced. The STCI-TR algorithm takes the MC as a sink node for a collaborative collection. After the charging and the completion of charging, the route planning is carried out again. It reduces the path length from some sensor nodes to sink and MC and the network transmission energy consumption. Therefore, the mobile energy consumption of MC and the stop-wait sensor nodes can be at the same time. The average remaining energy of STCI-TR is higher than that of MCU, BNRS, DPMCS, and VN-MOAC.Figure 14
Comparison of average remaining energy with different numbers of nodes.


## 6. Conclusions

A charging task coordination algorithm based on the Hamiltonian path for MWRSN is proposed to improve the EUE. This algorithm considers the cooperation of an MC and the next round of charging sensor nodes. In this paper, the MC is considered a mobile sink node to determine the stop position, and the charging task interval of the MC is determined. According to the charging task interval, the next round of the charging sensor node is taken as the stop-wait charging sensor node of the current round, and its stop-wait position is determined. In this way, the next round of charging by the MC node is avoided, and the mobile energy consumption of the MC in the next round of charging tasks is reduced. Simulation results show that the proposed algorithm can improve charging efficiency and network lifetime and reduce network energy consumption and average moving loss per unit time. However, the proposed charging task coordination algorithm needs more control information. The time complexity of the STCI-TR algorithm is still high for the MC and sink nodes. Multiple MCs are not considered in our work. Currently, the proposed method is not suitable for the large-scale network. In future research, collaborative charging between sensors will be considered to improve EUE. In addition, to improve the scalability and adapt to the application of large-scale sensor networks, the multiple sinks and MCs will be considered for cooperative charging. The decomposition of large-scale charging areas is the focus of our future research. The large-scale charging areas will be divided into several small subcharging areas according to the number of MC. An MC is responsible for charging the sensors in a subcharging area and our method in this paper can be used in this scenario. The charging cooperation among multiple MCs and between sensors will be considered in the future research. Another possible direction for future work is the 3D mobile charging of the MWRSN.



---

*Source: 6955713-2022-05-19.xml*