Relay placement for restoring connectivity in partitioned wireless sensor networks under limited information

Several factors such as initial deployment, battery depletion or hardware failures can cause partition wireless sensor networks (WSNs). This results in most of the sensors losing connectivity with the sink node and thus creating disruption of the delivery of the data. To restore connectivity, one possible solution is populating relay nodes to connect the partitions. However, this solution requires information regarding the availability of the damaged area, number of partitions in the network and the location of the remaining nodes which may not be obtained for all applications. Thus, a distributed self-deployment strategy may better fit the application requirements. In this paper, we propose two distributed relay node positioning approaches to guarantee network recovery for partitioned WSNs by minimizing the movement cost of the relay nodes. The first approach is based on virtual force-based movements of relays while the second exploits Game Theory among the leaders of the partitions. Force-based approach stretches the network gradually with the deployment of additional relays. In the game-theoretic approach, the partition to be connected with is determined by the leader relay nodes based on the probability distribution function (pdf) of the partitions. Partitions with a higher pdf have priority over other partitions for recovery. Once the partition is connected with the relay nodes, it becomes the part of the connected network. Recovery proceeds with the partition having the next highest priority until network is completely recovered by reaching the system-wide unique Nash equilibrium. Both approaches are analyzed and evaluated extensively through simulation. Game-theoretic approach has been shown to outperform force-based approach as well as a centralized approach under most of the conditions.