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 non-operational. 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.