In a wireless sensor network (WSN), sensors collect data that need to be delivered to a base station. This requires that the WSN should be a connected network. However, due to possible failures of sensors, a WSN might be partitioned into multiple isolated blocks. A solution to reconnect the WSN is to deploy mobile relays in the WSN, and schedule the mobile relays to positions that can reconnect the isolated blocks. In this paper, we target at a mobile relay scheduling algorithm with the minimal total movement cost such that the partitioned WSN becomes connected. We give a definition for boundary sensors of blocks, and show that, to connect two blocks, fewer mobile relays are used if we connect the two blocks through a pair of their boundary sensors. To connect a given pair of boundary sensors from two blocks, we derive the optimal new positions of mobile relays, which minimize the total energy consumption of mobile relays when relaying information between the two blocks.
To connect a partitioned WSN with multiple isolated blocks, a mobile relay scheduling problem is formulated and shown to be NP-complete. Then a greedy mobile relay scheduling algorithm is proposed to select boundary sensor pairs and reconnect the WSN by scheduling mobile relays to optimal new positions of connecting the selected boundary sensor pairs. Since the selected boundary sensors are gateways of blocks, and the moved mobile relays serve as routers to connect the blocks, any failure of them may disconnect the WSN again. Accordingly, another greedy mobile relay scheduling algorithm is proposed to reconnect a partitioned WSN such that the reconnected WSN can tolerate failure of one gateway or one router. Extensive simulations demonstrate that the proposed algorithms have better performance over other existing methods in terms of higher success probability and less movement cost.