Randomized Algorithms for Energy Balance in Wireless

1 PROBLEM DEFINITION Recent developments in wireless communications and digital electronics have led to the development of extremely small in size, low-power, low-cost sensor devices (often called smart dust). Such tiny devices integrate sensing, data processing and wireless commu-nication capabilities. Examining each such resource constraint device individually might appear to have small utility, however the distributed self-collaboration of large numbers of such devices into an ad-hoc network may lead to the efficient accomplishment of large sensing tasks i.e. reporting data about the realization of a local event happening in the network area to a faraway control center. The problem considered is the development of a randomized algorithm to balance en-ergy among sensors whose aim is to detect events in the network area and report them to a sink. The network is sliced by the algorithm into layers composed of sensors at approx-imately equal distances from the sink [8, 4, 5], see Figure 1. The slicing of the network depends on the communication distance. The sink initiates the process by sending a control message containing a counter which value is initially one. Sensors receiving the messag