In Wireless Sensor Networks (WSNs), maintaining connectivity with the sink node is a crucial issue to collect data from sensors without any interruption. While sensors are typically deployed in abundance to tolerate possible node failures, a large number of simultaneous node failures within the same region may result in partitioning the network which may disrupt the network operation significantly. Given that WSNs are deployed in inhospitable environments, such node failures are very likely due to storms, fires, floods, etc. The self-recovery of the network from these large-scale node failures is challenging since the nodes will not have any information about the location and span of the damage. In this paper, we first present a distributed partition detection algorithm which quickly makes the sensors aware of the partitioning in the network. This process is led by the sensors whose upstream nodes fail due to damages. Upon partition detection, sensors federate the partitions and restore data communication by utilizing the former routing information stored at each sensor to the sink node and exploiting sensor mobility. Specifically, the locations of failed sensors on former routes are used to assess the span of the damage and some of the sensors are relocated to such locations to re-establish the routes with the sink node. Relocation on such former routes is performed in such a way that the movement overhead on sensors is also minimized. Our proposed approach solely depends on the local information to ensure autonomicity, timeliness and scalability. The effectiveness of the proposed federation approach is validated through realistic simulation experiments and has been shown to provide the mentioned features.