{'fraction_non_alphanumeric': 0.04437291368621841, 'fraction_numerical': 0.00977587029089175, 'mean_word_length': 4.05739780537803, 'pattern_counts': {'":': 0, '<': 16, '<?xml version=': 0, '>': 38, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Effective Energy Restoration of Wireless Sensor Networks by a Mobile Robot

As most existing sensors are powered by batteries, the coverage provided by a sensor network degrades over time and eventually disappears if energy is not restored. A popular approach to energy restoration is to use a robot acting as a mobile battery charger/changer. The robot decides where to move next according to a predefined on-line energy restoration strategy. The effectiveness of such a strategy depends on the number of nodes it is able to maintain operational at any given time, as well as on for how long a node whose battery is depleted remains nonoperational. The ideal optimal on-line strategy (called OPTIMAL) occurs when the robot knows at any time the current status of all sensors, and it computes the best request to satisfy next, based on this information. Although optimal in terms of effectiveness, this centralized strategy would constantly require up-to-date global information; hence its high computational and communication costs make it not feasible. We consider a drastically different on-line strategy (called LIC), which is simple and fully decentralized, uses only local communication, requires no computations, and is highly scalable. In our strategy, the robot visits the sensors in a predefined circular order, moving in a “clockwise” direction and only when aware of a pending request. A sensor whose battery is about to become depleted originates a recharging request and waits for the robot; the request is forwarded according to the circular order in a “counter-clockwise” direction until it reaches either the robot or another sensor waiting for the robot. We show the perhaps unexpected result that, once the system becomes stable, in most networks the effectiveness of LIC is equivalent to that of OPTIMAL. In other words, in most cases, in spite of its simplicity and its extremely small (communication and computation) costs, the proposed decentralized strategy is as effective as the optimal centralized one. We augment our theoretical results with experimental analysis, confirming all the analytical results and showing among other things that the system stabilizes very quickly. 1A preliminary version of this paper appeared in the proceedings of the Seventh International Symposium on Computer and Networking (CANDAR) 2019.


Effectiveness, Costs and Contribution
The fact that some sensors might become inactive is not a problem if an energy restoration strategy is in place that guarantees that every inactive sensor is recharged and becomes operational again. From the point of view of maintaining as much as possible of the network operational at all times, the effectiveness of an energy restoration strategy depends on the number of sensors guaranteed to be operational at any given time. We shall call this measure operational size or, with an abuse of notation, coverage. Note that effectiveness can be equivalently measured by the number of sensing holes in the network at any given time (the smaller the number, the more effective the strategy); interestingly, unless the deployment has k > 1 redundant coverage, this measure corresponds to the number of coverage holes at that time.
The other effectiveness measure of interest is the time from the moment a sensor ceases to be operational to the time when the robot arrives to serve it; i.e., for how long a sensing hole lasts. We shall call this measure disconnection time.
Associated with each energy restoration strategy are also the computation and communication costs incurred when the robot operates in the network according to that strategy.
The effectiveness and the costs of the strategy employed by the robot to service the sensors depends on many factors, a crucial one being the amount of information about the network status available at any given time to the robot.
From the effectiveness point of view, the "ideal" optimal on-line strategy, which we shall call simply OPTIMAL, is clearly when the robot knows at any time the current status of all sensors, and it computes on-line the request it must satisfy next so to minimize the number of sensing holes and/or their duration. Even more that any other on-line strategy, in addition to a high computational complexity, OPTIMAL would require constantly up-to-date global information; hence the communication costs required to implement it severely limit its feasibility.
In this paper, we propose a drastically different on-line strategy, which we shall call Local Information and Communication (LIC). In this strategy, the robot visits the sensors in a predefined circular order, moving in a "clockwise" direction when aware of a pending request. A node whose battery is about to become depleted originates a recharging request and waits for the robot; the request is forwarded in a "counter-clockwise" direction until it reaches either the robot or another node waiting for the robot. In other words, each node communicates only locally: with the neighbouring sensors in the circular order (to send or receive a request), or with the robot if currently there (to communicate the presence of a pending request); the robot moves only from one node to the next in the cyclic order, is aware only of whether or not there is a pending request, and has no need of memory or calculation. In contrast to the existing centralized strategies, this simple on-line strategy is fully distributed and decentralized, uses only local communication, requires no computations, and it is highly scalable.

Main Results
We study the effectiveness and costs of LIC, both analytically and experimentally in an abstract setting.
Like in every energy restoration strategy, effectiveness depends on two crucial system parameters: the battery life, i.e., the amount of time ∆ a fully charged battery lasts under normal operations; and the recharging time, i.e., the amount of time ρ required for the charging/replacement once the robot is at the sensor's site. Let N (∆, ρ) denote the (infinite) class of sensor networks with those specific component characteristics.
We establish several results related to the stability of the system under LIC, whereas the network is deemed to be in a stable state if the order in which the nodes are charged in a round is the same in every round. In particular, we prove analytically that almost all networks in N (∆, ρ) become stable under LIC; when that happens, although the set of operational nodes changes in time, its size remains unchanged; furthermore this value is the same regardless of the initial network size. We also determine the disconnection time for such stable networks, providing a precise characterization of the performance and effectiveness of LIC.
We then compare the effectiveness of LIC with that of the optimal (but expensive to implement) strategy OPTIMAL We show the perhaps unexpected result that, in most networks, the effectiveness of LIC is equivalent to that of OPTIMAL. In other words, in most cases, in spite of its simplicity and its extremely small (communication and computation) costs, the decentralized strategy is as effective as the ideal optimal one. We support our theoretical results with experimental analysis, showing that the system stabilizes very quickly and confirming all the theoretical bounds established for coverage size and disconnection time.

Model
Let X = {x 0 . . . , x n−1 } be the set of sensor nodes, or simply nodes, forming the network. Each node has sensory equipment that allows it to monitor its surroundings; it also has provision for wireless communication within a limited range.
Let π be a cyclic order of the nodes; successive nodes in the order (e.g., x π(i) and x π(i+1) , where all operations on the indices are modulo n) are called neighbours, and can communicate (possibly by multiple hops).
Normal operations require sensing and occasional communication; both operations consume energy, which is provided by an on-board battery of limited capacity. When the battery is nearly depleted, the node becomes non-operational, thus creating a sensing hole in the network; and the remaining energy is used for local communication necessary for the recharging. In the following, with an abuse of notation, we will say that the battery is depleted when the node becomes nonoperational.
Let ∆ denote the amount of time it takes for a fully charged battery to become depleted under normal operations. Each node monitors the energy level of its battery and determines whether it is below a fixed threshold. We denote by τ the amount of time, under normal operations, elapsed from the moment the battery falls below the threshold to the time it becomes depleted. In the following, for ease of discussion, we will sometimes refer to ∆ as the battery life or capacity, and to τ as the threshold.
A mobile robot R is available in the system to recharge/replace the nodes's batteries; once R reaches a node, if the energy level of the node is below the threshold, the robot will restore the energy. We denote by ρ the amount of time it takes for a battery to become replaced/recharged; i.e., if the robot reaches a node x whose battery is below the threshold at time t, x's battery will be fully charged at time t + ρ; we assume that x will start being operational as soon as the robot starts restoring its energy. The robot can move from node to node; we denote by d i,j the time it takes the robot to travel from node x i to x j . We assume uniform distances among neighbours in the circular order; that is, We now introduce the measures we use to study the effectiveness of energy restoration strategies. Let S be an energy restoration strategy. The operational size, or coverage, at time t under S (denoted by Coverage(S, t)) is the number of operational nodes at that time. Note that the coverage implicitly measures the number Holes(S, t) = n − Coverage(S, t) of the sensing holes at time t.
The disconnection time for a node x is the amount of time from the moment x becomes inactive to the time when the robot arrives to serve x. Disconnection time is, of course, zero if the node is charged before it becomes inactive. More precisely, the disconnection time for node x at time t under S (denoted by Disconnect(S, t, x)) is the amount of time x had been inactive when last serviced by the robot before or at time t. This measures indicates for how long a sensing hole lasts.
Since the focus of this study is on the effectiveness of the recharging strategies and on their computing and communication costs, we will not address how the robot acquires the means to service the sensor nodes (e.g., by stopping at a recharging station, by extracting it from the environment, etc.) and we assume (as in [30,36]) that the robot is always capable of doing so.

Decentralized Strategy: LIC
We now describe a simple decentralized on-demand strategy, which uses only local information and requires only local communication, hence the name Local Information and Communication (LIC).
The proposed strategy assumes the availability of a cyclic ordering π of the nodes (see Figure 1); the construction of such an order is discussed in Section 6. Once each node x π(i) has identified its two neighbours x π(i−1) and x π(i+1) , the algorithm can start.

Description
Starting from its initial position at an arbitrary node, the robot visits the nodes according to the circular order π, moving in the "counter-clockwise" direction (i.e., from x π(i) to x π(i+1) ) when aware of a pending request. A node whose battery is about to become depleted originates a recharging request and waits for the robot; the request is forwarded in the "clockwise" direction (i.e., from x π(i) to x π(i−1) ) until it reaches either the robot or another node waiting for the robot, creating in this way a trail to be followed by the robot when it becomes available. Note that a request contains no specific information (e.g., id, location, etc.) about the node issuing or forwarding it. All nodes have the ability to receive and forward a single request even if they are not operational.
Summarizing, (1) each node communicates only locally: with the neighboring nodes in the cyclic order (to send or receive a request), or with the robot if currently there (to communicate the presence of a pending request); (2) the robot moves only from one node to the next in the cyclic order, is aware only of whether or not there is a pending request, and has no need of additional memory or calculation.
Algorithm LIC prescribing the behavior of the nodes and of the robot is shown in Figure 2, using the State×Event→Action notation. With respect to the protocol, a node x can be in one of two states, Regular or Waiting, and keeps track of whether or not it has received a pending request from its predecessor in the order (Boolean variable Q(x)). Initially all nodes are in state Regular, Q(x) = 0 for all x ∈ X , and the robot is at an arbitrary node.

Properties: Tours and Weakness
A tour from node x is defined as the visit of all the nodes by the robot starting from x (and possibly charging it) and ending when arriving again at x. Let∆ = ∆ − τ denote the amount of time before a fully charged battery falls below the threshold. Lemma 1. Let x π(i) require recharging both at the beginning and at the end of a tour from it; then also x π(i−1) requires recharging when reached by the robot in this tour.
Proof. Let x π(i) be found to be needing recharging at time t 0 , fully recharged at time t 1 = t 0 + ρ, and found empty again at the end of this tour, at time t 2 .
By contradiction, let the previous node x π(i−1) be found not needing recharging when visited by the robot in this tour. Let k ≥ 0 be the number of the nodes (other than x π(i) ) that have been recharged in this tour. In other words, the robot has spent in this tour kρ time units to charge them before reaching x 0 at time t 2 ; that is, t 2 ≥ t 1 + kρ + nd. Since x π(i) is found needing recharging at time t 2 , we must have On the other hand, the time elapsed between the time t = t 0 − d the robot left x π(i−1) in the previous tour from x π(i) and the time t it reached it again in this tour is at least (k + 1)ρ + nd, since x π(i) was recharged in this interval. Since x π(i−1) is assumed to be found non needing recharging, we must have (k + 1)ρ + nd <∆ a contradiction.
Analogously, Lemma 2. Let x π(i) require recharging both at the beginning and at the end of a tour from it; then also x π(i+1) will need to be recharged when reached by the robot in the next tour from x π(i) .
Proof. Let x π(i) be found needing recharging by the robot at time t 0 , fully recharged at time t 1 = t 0 + ρ, and found needing recharging at the end of the tour, at time t 2 . Let k ≥ 0 be the number of other nodes recharged in this tour. For node x π(i) to be needing recharging at time t 2 , we must have kρ + dn ≥∆.
Consider now the state of node x π(i+1) when it is reached by the robot once x π(i) has been recharged. The time elapsed from the previous visit is greater than or equal to (k + 1)ρ + dn (since also x π(i) was recharged in this interval). Since (k + 1)ρ + dn = kρ + ρ + dn >∆, it follows that node x i+1 needs recharging when it is reached by the robot.
We say that x is weak if there exists a tour from x where x needs recharging both at the beginning and at the end of the tour. Let t weak be the first time when this happens. Lemmas 1 and 2, together, prove the following important property: Theorem 1. If there is a weak node then from time t weak every node visited by the robot is found to need recharging. This holds regardless of the threshold τ .
This, in turns, has important consequences on the size of the coverage of the network: . If there is a weak node, then there exists a time t, such that, ∀t > t, m ≤ Coverage(LIC, t ) ≤ m + 1, and all nodes have the same disconnection time: Proof. Let x π(i) be weak; thus, there is a tour where x π(i) will be recharged both at the start and the end of that tour; let t be the time when the recharging at the end of that tour will be completed. By Theorem 1, from this time on the robot finds only nodes needing recharging; since it takes ρ time units for the robot to recharge a node and d time units to move to the next node, by time t = t + ∆ the robot has recharged the consecutive nodes x π(i+1) , x π(i+2) , ..., x π(i+m−1) where m = ∆ (ρ+d) and all operations on the indices are modulo n; if ∆ is not a multiple of ρ + d, then it is currently recharging x π(i+m) , otherwise also x π(i+m) has been fully recharged. But, at this time t = t + ∆, x π(i) 's battery is totally depleted, and so obviously is the battery of all the nodes after x π(i+m) up to and including x π(i) . This means that, at time t 0 = t + m(ρ + d), exactly n − m nodes have their battery completely empty; hence Coverage(LIC, t 0 ) = m.
Observe that, when x π(i+m+1) is reached and fully recharged, at time On the other hand, at any time t j < t < t j+1 x π(i+j) 's battery might not yet be depleted; that is, Coverage(LIC, t ) ≤ m + 1.
Since after time t the robot keeps charging every node it encounters, it will spend n(ρ + d) time units to complete a tour. During that time, each node is not disconnected for ρ + ∆ time units. Therefore, every node will have disconnection time (n − 1)(ρ + d) + d − ∆.

Properties: Rounds and Stability
Let us call round from node x any sequence of consecutive tours from x where at the beginning of the first tour and at the end of the last x's battery needs to be recharged, and in all others it does not. Clearly a round from x might include several tours from x.
We will denote by r j (x) the j-th round from x, j ≥ 1; when no ambiguity arises, we will indicate a round from x simply by r(x).
Let σ j (x) denote the ordered sequence of the nodes charged during r j (x). We say that the network is stable if ∃j ≥ 1 such that ∀x ∈ X , ∀j > j, σ j (x) = σ j (x). That is, in a stable network, the order in which the nodes are charged is the same in every round; hence, in a stable network, we can omit the indication of the round and denote σ j (x) simply as σ(x).
When a network is (or has become) stable, it enjoys some obvious properties. Among them: is a cyclic shift of σ(y); (iii) every round from any node is composed of the same number of tours.
An important property of a network once it becomes stable under LIC is the following.
Theorem 3. If the network is stable under LIC and n > 2 ∆ ρ + 1, each round is composed by a single tour.
Proof. Let the network be stable; then, by Lemma 3 (iii), every round from any node x is composed of the same number s of tours. We want to show that s = 1 if n > 2 ∆ ρ + 1. By contradiction, let s > 1. Consider a round from node x and let f (x, s) be the number of nodes charged in the last tour of this round. We will consider three cases depending on the value of f (x, s).
In this case, the number of nodes charged in the first s − 1 tours is k = n − f (x, s) ≥ n 2 + 1. Consider the amount of time T elapsed from the moment x has been charged at the beginning of the round, to the beginning of the last tour of this round.
By definition, and since k ≥ n 2 + 1 and s > 1, we have Since, by definition of round, x is found by the robot not to need recharging at this time, we have ∆ − τ =∆ ≥ T , that is: But n > 2 ∆ ρ + 1 by hypothesis; that is, (n−1) 2 ρ > ∆; a contradiction.
In this case, there must exist a node y such that f (y, s) < n 2 . By considering the round from y (instead than from x), by Case 1 the contradiction occurs.
Case 3 : f (x, s) = n 2 . If s > 2 then there must exist a node y such that f (y, s) < n 2 ; by considering the round from y (instead than from x), by Case 1 the contradiction occurs.
Finally, let s = 2. In this case, n is even, the round r(x) is composed of two tours, and f (x, 1) = f (x, 2) = n 2 . Note that the nodes charged in the second tour of r(x) are the complement of the ones charged in the first tour.
Consider now the node y, next in the cycle, visited by the charger right after x. We have two cases (see Figure 3) depending on whether or not y needs to be recharged at this time. Case (3a) : y needs to be charged. In this case, consider the round r(y) starting after charging y (see Figure  3 (3a), bottom). Round r(y) must also be composed of two tours each containing exactly n 2 nodes in need of charge (i.e., we must have f (y, 1) = f (y, 2) = n 2 ), otherwise a contradiction would arise because of the previous reasoning applied to y. However, the nodes in need of charge in the first tour of r(y) are the same as the ones in the first tour of r(x) except for y itself; thus f (y, 1) = n 2 − 1, a contradiction. Case (3b) : y does not need to be charged. In this case, consider the round r(y) starting from y the last time it was charged before time t s (x). By definition, the nodes in need of charge in the first tour of r(y) are the complement of the ones charged in the first tour of r(x, 1) excluding y, thus f (y, 1) = n 2 − 1, a contradiction.

FUN 2012
Case%(3a)% Case%(3b)% x% y% x% y% Figure 3: Cases (3a) and (3b) of Theorem 3 in a stable network with n = 8. Each row corresponds to a tour starting from x; black (white) circles represent nodes charged (not charged) in that tour. A round r(x) consists of two consecutive tours starting after a black x. Highlighted in the top (resp. bottom) is the first tour of r(x) (resp. r(y)) in the two cases.

Stability and Effectiveness
All the analytical properties we have established on LIC hold if and when the network becomes stable. In the following, we prove that stability under LIC is inevitably achieved in almost all networks, establish an upper bound on the number of rounds before that happens, as well as tight bounds on the effectiveness of LIC.

Stability of LIC
In the following, we prove that, in all networks with n > 2∆ ρ + 1, stability under LIC is always achieved. To do so, we need some additional terminology and lemmas.
Given a round r(x) from x, let tour 1 (r(x)), tour 2 (r(x)), . . . , tour s (r(x)) denote the tours it is composed of, and let k(x, i) be the number of nodes charged in tour i (r(x)). In particular, let k(x, s). In the following, let n > 2 ∆ ρ + 1.

Lemma 4.
If there exists a node x starting a round r(x) at time t with s = 1, then the network is stable from time t.

Proof.
A node x starting a round r(x) at time t with s = 1 is, by definition, a weak node. From Theorem 1, we know that from time t every node visited by the robot is found to need recharging, that is, after this time, the order in which the nodes are charged is the same in every round and thus the network is stable by definition.
We next show that a round from any node which is composed by more than one tour (i.e. with s > 1) have the property that, during the first s − 1 tours of the round, less than half of the nodes are charged.
Lemma 5. There exist no node x completing a r(x) with s > 1 tours with k(x) ≥ n 2 . Proof. By contradiction. Consider a node x starting a round composed by s > 1 tours, such that its first s−1 tours contain at least n 2 recharges; i.e., k(x) ≥ n 2 . Since x is found in no need of charge after s − 1 tours, we have that ρk(x) + (s − 1)nd <∆. However, by hypothesis, ρk(x) + (s − 1)nd > ρ n 2 , which implies ρ n 2 <∆, and thus In other words, a necessary condition for having only rounds composed by more than one tour is that k(x) < n 2 for all nodes and all rounds. Lemma 6. If there exists a node x starting round r(x) at time t with k(x, s) ≥ n 2 , then there exists a node x starting round(x ) at some time t > t such that round(x ) is composed by a single tour (i.e., x is weak).
Proof. Consider the last node x charged in tour s−1 (x) and round(x ) starting after the charge of x . Assume by contradiction that round(x ) is composed by more than a single tour. Since round(x ) fully includes the k(x, s) nodes charged in tour s (x) and since, by hypothesis, k(x, s) ≥ n 2 we have that k(x ) > n 2 , which is impossible by Lemma 5. Lemma 7. If a node is not charged in an entire round it will be charged in the first tour of the next round.
Proof. Let y not be charged in round r(x) from x, started at time t 1 and ended at time t 2 . Since x needed to be recharged at time t 2 , then t 2 − (t 1 + ρ) ≥∆. But since y was charged before time t 1 , this means that at time t 2 also its battery life is below the threshold; hence it will be charged as soon as it is reached by the robot in the first tour.
We can now prove the main stability result.

Theorem 4. Let n > 2∆
ρ + 1. Then, under the LIC strategy, the network becomes stable within finite time.
Proof. Consider the first node x that is recharged twice by the robot since the beginning. In other words, the first round r 1 (x) from x is the first to be completed among all the first rounds from all nodes. Let t 1 and t 2 be the time when r 1 (x) starts and ends, respectively. Let r 1 (x) be composed of s tours.
If s = 1, then the network is stable from time t 1 by Lemma 4, proving the Theorem. Let then s > 1. In this case, by Lemma 5, the number of nodes, other than x, recharged by the robot in the first s − 1 tours of r 1 (x) is k 1 (x) < n 2 . Consider the total number k 1 (x) of nodes, other than x, recharged by the robot in r 1 (x).
If k 1 (x) > n 2 , let x be the last node charged in the (s − 1)-th tour of r 1 (x); by Lemma 6, its first round r 1 (x ), started at time t < t 2 , is composed by a single tour; hence, by Lemma 4, the network is stable from time t , proving the Theorem.
Finally, consider the case k 1 (x) ≤ n 2 . Clearly, in this case, the numberk = n−k 1 (x) of nodes that are not charged at all during r 1 (x) isk ≥ n 2 . By Lemma 7, all of them will be charged in the first tour of the next round r 2 (x) from x. This implies that, if r 2 (x) had more than one tour, then k 2 (x) > n 2 contradicting Lemma 5; hence the network is stable from time t 2 , proving the Theorem.

Effectiveness of LIC
By bringing together the result of Theorem 4 with the observations on weakness and stability made in Sections 3.2 and 3.3, we can immediately establish tight bounds on the effectiveness of LIC.

Theorem 5. Let n > 2∆
ρ + 1. Then, under the LIC strategy, there is a time t such that, for all t ≥ t, we have Proof. By Theorem 4, the network will become stable within the first two rounds. By Theorem 3, it follows that, from time t stable , each round is composed by a single tour; hence, by definition, every node is weak. The bounds on coverage and disconnection time then follow from Theorem 2.

Round Bounds for Stability
We have shown that all networks with n > 2∆ ρ + 1 become stable under LIC. In this subsection we investigate how long it takes for stability to be reached, and establish an upper bound on the number S of tours within which stability will always occur.
Consider the first node x that is recharged twice by the robot since the beginning. In other words, the first round r 1 (x) from x is the first to be completed among all the first rounds from all nodes. Let r 1 (x) be composed of s tours; let us see how large can s be. From the last case considered in the proof of Theorem 4, it follows that the network becomes stable after at most one more round; that is S ≤ s + 1. Consider the number k 1 (x) of nodes, other than x, recharged by the robot in the first s − 1 tours of r 1 (x); then obviously, s ≤ k 1 (x) + 1. Since by Lemma 5, k 1 (x) < n 2 when s > 1, we have s ≤ n 2 . Hence, we have the first upper bound This bound can be refined. In addition to x, at least one node is recharged in each tour of r 1 (x). However, since by Lemma 5 k 1 (x) < n 2 , k 1 (x) − k 1 (x) > n 2 nodes will not be recharged in the first s − 1 tours. Among them, let y be the one closest to x in the cyclic order. Since y has not been recharged in the first s − 1 tours, it means that its energy level when visited by the robot in the (s − 1)-th tour was high enough. This in spite of the fact that, from time t 1 when this round started, after x is fully recharged at time t 1 + ρ, at least one node is recharged in each tour of r 1 (x). In other words, ∆ − ρ > (s − 1)ρ + (s − 1)nd; that is, ∆ > s(ρ + nd) − nd; hence ∆ (ρ+nd) + 1 > s which gives us a better upper bound The experimental evidence, to be shown in Section 5, indicates that this bound is quite far from the actual value of S.

LIC versus OPTIMAL
We are going to compare the effectiveness of LIC with that of the optimal on-line strategy OPTIMAL.
In OPTIMAL, each request message is sent by the node to the charger; the robot processes all the current request messages, and it computes which request to satisfy next so to minimize the number of sensing holes and their duration. We are actually going to consider an ideal cost settings for OPTIMAL: every request from every node reaches the robot directly, regardless of its current location; the robot can reach any node from any node in the same amount d of time, regardless of its distance; and the robot's processing time is negligible regardless of the complexity of the computation.
Notice that the behaviour of the robot under OPTIMAL in this setting is easy to describe: the robot just processes and services the request messages in the order they arrive; if two or more requests arrive at the same time, ties are broken by Ids.
The effectiveness of OPTIMAL is simple to derive for most networks: Theorem 6. If n > (∆ + ρ)/(ρ + d) then, under the OPTIMAL strategy, there exists a time t such that, for all t > t Proof. Let x 0 , x 1 , . . . x n−1 be the nodes ordered by their initial battery level, where nodes with the same level are ordered by their Id. Clearly this is the order in which the requests are considered by the robot. Let t i,1 be the time when x i is fully charged for the first time; thus, t i,1 + ρ + d ≤ t i+1,1 . This implies that the time t i,j when the node x i will been fully charged for the j-th time is t i,j + ρ + d ≤ t i+1,j . In other words, the nodes will be always serviced according to the initial order. After fully charging node x i for the j-th time at time t i,j , the robot will have fully charged all other nodes after at least (ρ + d)(n − 1) time units. By hypothesis, n ≥ ∆+ρ+d ρ+d ; thus, (ρ + d)(n − 1) ≥∆. In this case, by time t i,j + (ρ + d)(n − 1), the (j + 1)-th request by x i is already in the queue and thus the robot goes to service x i next. In other words, after a full round, the robot continuously charges the nodes in the same order without ever stopping.
The coverage size in this case is easy to compute. Let X be the total number of nodes that are alive at any given time. This means that ρ(X − 1) + (X − 1)d < ∆, but ρX + Xd ≥ ∆ and thus ∆ (ρ+d) < X < ∆+ρ+d (ρ+d) . Since after time t 0,2 the robot keeps charging every node it encounters, it will spend (n − 1)(ρ + d) + d time units to complete a round; hence, every node will have disconnection time This theorem has an immediate very strong consequence for the effectiveness of LIC. Proof. Since 2∆ ρ + 1 > ∆+ρ ρ+d , the claim follows directly from Theorems 5 and 6.
In other words, for all networks with n > 2∆ ρ + 1, the recharging strategy LIC, with its low communication and computations costs, performs as well as the optimal strategy.

Experimental Analysis
The results of the previous Section describe the behaviour of the network once it stabilizes in time. We run extensive simulation to determine the stability of the network under LIC and to observe its behaviour in terms of Coverage Size and Disconnection Time (already studied theoretically).

Simulation Environment
The experiments were implemented in the simulator discrete-event MAS toolkit MASON [18].
The variable parameters involved in the experiments are: the number of nodes n, the battery life ∆, the charging time ρ, and the travel time d from a node to the next.
The following Each node x has initially an amount of energy level chosen uniformly at random in the range [τ , ∆]; the charger's initial placement is at a node chosen uniformly at random.
For each combination of the values of the parameters, we have executed 20 executions and computed the average coverage size and disconnection time. To detect stability we have also maintained the information about the charging order of the nodes under LIC.

Stability
Starting with arbitrary initial charge levels, the experimental results show that, for all values of the parameters, the charging order becomes periodic and the network stable; moreover stabilization occurs within two rounds. In other words, under LIC the network becomes stable within two rounds. See Figure 4 where stability is shown for some choices of the parameters; the results for all the other parameters' combinations are consistent with these. Note that, for smaller capacities, as well as for larger networks, stabilization occurs even sooner, within one round.
Once the network stabilizes, the theoretical bounds on coverage size and disconnection time established analytically (Theorem 5) hold; indeed, the simulation results of the next section confirm all these bounds.  In order to determine the impact of the charging time ρ on the effectiveness of the proposed algorithm, we start by analyzing the effects of various charging time on disconnection time for different network sizes using n = 100, 200, 300, 400, 500 nodes. In these scenarios, we fix the node capacity ∆ = 2000 and we consider unitary travel time between neighboring nodes (the case of d = 1 will be treated separately). The results obtained varying ∆ are consistent with the ones displayed here and are not shown. In all cases the results are as one would have expected. The graphs in Figure 5 shows the trend in the disconnection time for the considered network sizes. In general, we can see a similar pattern in the graph: for a given number of nodes, the disconnection time increases as the charging time increases because the waiting time for the robot increases.

Effects of Node Capacity ∆.
We now analyze the effect of node capacity ∆. In the graphs below we show the impact of ∆ by fixing n and varying ρ, as well as by fixing ρ and varying n. Also here, the travel time between nodes is considered unitary (the case of d = 1 will be treated separately). Figure 6 shows the impact on disconnection Time (a), (b): when n = 300 nodes while ρ varies. The results reveal no surprises: for a given network size and charging time, the disconnection time decreases as the node capacity increases.  time increases, as expected, while the network size increases, and they do so also when varying ρ.

Effects of Travel Time.
We now study the impact of the time it takes the robot to go from a node to the next in the cyclic order on disconnection time. In the experiments, we set node capacity ∆ = 2000 unit of energy, and we vary the travel time between nodes to be uniform, but not necessarily unitary: we consider d = 1, 5, 10 units. We consider various network sizes n = 100, 200, 300, 400, 500, and various charging time ρ = 1, 10, 20, 30, 40, 50. Figures 8 depicts the effect of the travel time on the disconnection time. We conclude that as the travel time between nodes increases, the disconnection time increases too. In general, most nodes get charged before their battery becomes empty, which means a lower disconnecting time. As the number of inactive nodes increases due to the increase in travel time, the disconnecting time increases.

Coverage Size
While the impact on disconnection time is as expected, the observation of coverage size has revealed much more interesting behaviors. From Figure 9 we observe that when ρ = 1 the increase in size corresponds to an increase of coverage size up to n = 400, at which point the coverage size seems to stabilize to a constant value. The same behavior can be observed for larger ρ, where however the stabilization occurs earlier; in fact, for ρ ≥ 10 we observe it when n = 200. This behavior is quite interesting and will be discussed further later. From the graph, we can also see that coverage size decreases varying ρ, when observing a fixed value of n, which is to be expected. Figure 10 (a) shows that, as one would expect, when node capacity increases, also the coverage size increases (when n is fixed). On the other hand, fixing a given capacity, the increase in the network size correspond to a decrease of coverage size. Interestingly, from Figure 10 (b) we observe again that the coverage size does not change when fixing a given node capacity, even when n changes. In other words, the node capacity is independent of the network size and confirms the theoretical derived in Theorem 5, even for n smaller that 2∆ ρ + 1. The observation just made can be clearly seen also in Figure 11, where we note that the coverage size increases with the network size but eventually stabilizes. The stabilization occurs earlier for smaller values of charging time ρ still confirming the theoretical bounds established in the previous Section. When the travel time between two nodes is not unitary, but still constant, we make observations that are consistent with what already seen (see Figure 12), which makes us conclude that, as long as the travel time between two nodes is the same, the actual value does not influence the general behavior of the strategy. To better analyses the observed phenomena concerning coverage size, we now focus on some specific scenarios to analyze how the coverage size changes in time.

Effects of Node Capacity ∆
Starting with arbitrary initial charge levels, the experimental results show that the first few tours of the ring performed by the robot follow a schedule that highly depends on the initial distribution of charges; however, we confirm our conjecture by observing that, for all choices of parameters: • the charging pattern stabilizes becoming periodic; • stabilization occurs within two rounds.
In other words, the networks become stable within two rounds. Figure 9, for example, shows coverage size varying ρ confirming that whenever we have n > 2∆ ρ + 1, the average coverage size stabilizes, that coincides with the theoretical value shown in Theorem 5. The same is observed when varying the node capacity ∆.  When executing each scenario, computing coverage size and disconnection time, we have also recorded the charging order of the nodes. We have seen that, after at most two rounds, regardless of the size, the network stabilizes. Stability occurs for any value of n, we then can observe that for n > 2∆ ρ + 1 (i.e., n = 200, 300, 400, 500 in Figure 13 and all values of n in Figure 14), coverage does not depend on n and coincides with the theoretical value which is shown in the next section. Finally, we observe that these phenomena hold in all experiments regardless of the initial distribution of charges; that is, the same phenomenon has been observed not only with random distributions, but also with specific ones, such as when the charges are increasing in a clockwise order (see Figure  15) or in counterclockwise order (see Figure 16).

Comparison with OPTIMAL
We now turn to the comparison between LIC and OPTIMAL. We already established that, when n > 2∆ ρ + 1, the two strategies are equivalent both in terms of coverage size and disconnection time (Theorem 7). Extensive experimental results, varying ∆, ρ, d, and n, confirm the theoretical findings.  For example, Figure 17 shows coverage and disconnection time of the two strategies for different network sizes when ∆ = 2000, ρ = 20 and d = 1. Notice that Theorem 7 does not hold when n < 2∆ ρ + 1; in fact, as shown in Figure 17, OPTIMAL has a much better coverage than LIC for the case n = 100.

Concluding Remarks
In this paper, we introduced the notion of effectiveness of energy restoration strategies. We proposed a very simple decentralized battery recharging strategy, which, in spite of its simplicity and of the use of very limited resources, achieves optimal effectiveness in most cases. The technique is based on the on-demand visit of the nodes by a mobile robot in a predefined circular order only when aware of a pending request. The optimality of the strategy is proven for sufficiently large networks (n > 2∆ ρ + 1). It would be interesting to consider also the case of smaller n, where our strategy is not optimal; the detailed analysis of the charging dynamics for that case will be the object of future study.
Our studies, both analytical and experimental, have been carried out in an abstract setting, with several simplifying assumptions. Among them, we assumed that the time necessary for the robot to move from a node to its successor in the cyclic order is uniform. We did run experiments with variable distances between nodes; all these experiments do not show any significant difference with the results obtained in the paper with uniform distances; the theoretical validation is however left for future work. Our strategy is based on the existence of a cyclic order to be used by the charging robot, where successive nodes in the order are within direct communication range. Should such a cycle not exist in the communication graph (because it is not Hamiltonian) or be difficult to compute, a virtual cycle based on a simple DFS could be used (see Figure 18). The drawback would be that the communication distance between two neighbours in the cycle might be more than one (i.e., multihop communication might be required) and the physical distance between them might increase. Alternatives to the cyclic order, to be considered and explored, are less regular ordering structures which decentralized building techniques already exist (e.g., [4]).
Another assumption that would be interesting to lift is the one of constant charging rate ρ, the same for all nodes. The case of variable charging rates, possibly depending on the current battery level, as well as other physical factors (e.g., battery capacity decay) are important open research directions.