Greedy algorithms for actor redeployment in wireless sensor-actor networks

摘要

In a wireless sensor-actor network, an actor usually has to provide services as soon as the actor receives the event signals from the sensors. Therefore, the performance of a wireless sensor-actor network depends on the actor deployment. In many circumstances, actors may fail or go out to deal with events, and thus, the sensors covered by the missing actors could be not to be reachable in time. This introduces the necessity of actor redeployment. In this paper, we study the problems of redeploying actors to maximize the number of sensors able to be covered by actors and to maximize the decrease of the residual distances of sensors, respectively. Both problems are shown to be NP-complete. Additionally, we prove that the greedy algorithm for each problem has an approximation ratio of 2. Simulations show that the greedy algorithm for each problem performs well.