Localized motion-based connectivity restoration algorithms for wireless sensor and actor networks
Introduction
Wireless Sensor and Actor Networks (WSANs) (Akyildiz and Kasimoglu, 2004) are gaining growing interest because of their suitability for mission critical applications that require autonomous and intelligent interaction with the environment. Examples of these applications include forest fire monitoring, disaster management, search and rescue, security surveillance, battlefield reconnaissance, space exploration, coast and border protection, etc. WSANs consist of numerous miniaturized stationary sensors and fewer mobile actors. The sensor nodes report an event of interest to one or multiple actors for processing, making decisions and performing appropriate actions. The role of an actor is extremely crucial for a timely response to events such as fire, earthquakes, disasters, etc., and depends on the environment and capabilities of actors that may vary from one application to another. For example, an actor can extinguish a fire, lift rubbles, rescue trapped survivors, deactivate a landmine and carry weapons. A sample WSAN environment is depicted in Fig. 1.
In these critical WSAN applications, actors need to collaborate and coordinate with each other on planning an optimal response and synchronize their operations. For instance, in a forest monitoring applications, sensors report of the detection of a fire to the actors in the vicinity. Actors such as fire extinguishing robots and flying aircrafts need to be engaged as rapidly as possible in order to control the erupted fire and prevent it from spreading. Therefore, actors should collaboratively identify the most appropriate set of actors that will participate in the operation. This requires that actors are able to communicate with each other and a strongly connected inter-actor topology should be maintained at all time.
The harsh application environment that WSANs operate in makes actors susceptible to physical damage and component malfunction. Failure of one or multiple nodes may partition the inter-actor network into disjoint segments. Consequently, an inter-actor interaction may cease and the network becomes incapable of delivering a timely response to a serious event. Therefore, recovery from an actor failure is of utmost importance. Since, WSANs operate autonomously in unattended setups, replacing the failed actor may be infeasible or take significant time, and the recovery should be a self-healing and agile process that involves reconfiguring the inter-actor topology. The criticality of the applications and the resource constrained nature of these networks necessitate low restoration time and reduced overhead.
Most of the existing approaches in the literature are purely reactive (Abbasi et al., 2007, Younis et al., 2010, Tamboli and Younis, 2009), with the recovery process initiated once the failure of “F” is detected. The main idea is replace the failed node “F” with one of its neighbors or move those neighbors inward to autonomously mend severed topology in the vicinity of F. Usually the repositioning of the neighbors of F causes more links to break and the relocation process repeats in a cascaded manner. Since these reactive schemes require coordination among the healthy nodes, the recovery process often imposes high messaging overhead. In addition, these approaches only deal with single node failure, focus on resource efficiency and do not consider recovery time.
In this paper, we present a novel distributed partitioning Detection and Connectivity Restoration (DCR) algorithm, which proactively determines potential critical actors and assign backup nodes in order to rapidly repair the topology with little overhead. The design philosophy of DCR is based on “Guardian nomination” inspired from social and legal systems. First each actor proactively assesses its criticality, i.e., being a cut-vertex in the network topology, in a distributed manner based on the local information. Each critical (primary) actor designates appropriate neighbor (preferably non-critical) as its backup. The backup actor continuously monitors its primary for possible failure. Once the failure is detected, the backup initiates a recovery process by replacing the primary so that the connectivity is restored. The algorithm is recursively executed until all actors become strongly connected.
DCR assumes single critical actor failure at time and no other node fails during the recovery process. Although, the possibility of concurrent multiple actor failure is exceptional, it may precipitated by harsh environment and disastrous events such as explosions in battlefield. Recovery from such failures is very challenging and requires careful consideration especially when the failed actors are neighbors. We extend DCR to address one scenario of the multi-node failure when no more than two of the failed actors are adjacent. We present a recovery algorithm for the failure of multiple node failures (RAM) in order to handle concurrent failures of multiple actors. RAM identifies critical actors and designates for them distinct backups. The designated backups detect the failure of adjacent actors and simultaneously execute the recovery process. Like DCR, the recovery procedure is applied recursively until connectivity is restored. The overall purpose is to avoid procrastination, engage actors locally to monitor each other, reduce recovery time and overhead. To the best of our knowledge, RAM is the first localized approach that strives to minimize the recovery overhead while recovering from simultaneous failure of multiple actors. Simulation results validate the performance of the proposed approaches in terms of total distance movement, nodes involved in recovery, messaging and coverage reduction. It is worth noting that our algorithm is equally applicable to mobile sensor networks (MSNs) (Dantu et al., 2005) and mobile robot networks (MRNs) (Das et al., 2007).
This paper is organized as follows. Section 2 discusses the system model and problem statement. The related work is discussed in Section 3. The proposed DCR and RAM algorithms are detailed in Section 4. Section 5 presents the analysis the proposed recovery algorithm. The performance of DCR and RAM is evaluated through simulation and presented in Section 6. Section 7 concludes the paper.
Section snippets
System model and problem statement
Our algorithm is applicable to WSANs that involve sensors and actors. Sensors detect and report events of interest to one or multiple actors. Actors receive reports from sensors, process and collaborate with each other to plan an optimal coordinated response. Sensors are deployed in abundance while actors are significantly fewer than sensors. Sensors are inexpensive and have scarce resources compared to actors in terms of energy, communication and computation (processing and memory). The
Related work
The issue of fault tolerance in different WSAN contexts has only been studied in few studies. For instance, the fault-tolerant model presented in Ozaki et al. (2006) designates multiple actors to each sensor and multiple sensors to each actor in order ensure guaranteed event notification even in case of either failure or inaccessibility. However, our fault-tolerant model is in context of maintaining inter-actor connectivity rather than reliable event notification delivery. On the other hand,
Partition detection and connectivity restoration
As mentioned earlier, hybrid algorithms better suits time-sensitive applications that require a rapid recovery. The proposed DCR algorithm is hybrid in the sense it consists of two parts, i.e. proactive and reactive. In the proactive part, critical actors are determined using a localized algorithm. Once critical nodes (primary) are determined, they select and designate an appropriate neighbor (backup) to handle their failure when such contingency arises in the future. Each backup starts
Algorithms analysis
In this section, we analyze the performance of DCR and RAM algorithms. We show that both algorithms converge and successfully restore the connectivity of the network lost due to failure of critical actor (s).
Results and analysis
The performance of DCR and RAM is validated through simulation. This section describes the simulation environment, performance metrics and results.
Conclusion and future work
This paper has presented a novel distributed hybrid movement control algorithm for restoring connectivity lost due to critical actor failure. The proposed DCR algorithm identifies critical actors in advance based on localized information and designates for them backup actors. DCR pursues controlled node relocation in order to reorganize the topology and regain the pre-failure strong connectivity. In order to handle multiple simultaneous failures of critical actors, we have proposed RAM. RAM
Acknowledgment
The author is thankful to Universiti Teknologi PETRONAS for providing partial support. Younis' work is supported by the National Science Foundation, award # CNS 1018171.
References (27)
- et al.
Wireless sensor and actor networks: research challenges
Ad Hoc Networks
(2004) - Abbasi, AA, Akkaya, K, Younis, M. A distributed connectivity restoration algorithm in wireless sensor and actor...
- Akkaya, K, Younis, M. COLA: a coverage and latency aware actor placement for wireless sensor and actor networks. In...
- et al.
Sink repositioning for enhanced performance in wireless sensor networks,
Computer Networks
(2005) - Akkaya, K, Thimmapuram, A, Senel, F, Uludag, S. Distributed recovery of actor failures in wireless sensor and actor...
- Azadeh, Z. A hybrid approach to actor−actor connectivity restoration in wireless sensor and actor networks. In:...
- et al.
Distributed recovery from network partitioning in movable sensor/actor networks via controlled mobility
IEEE Transactions on Computers
(2010) - Batalin, MA, Sukhatme, GS. The analysis of an efficient algorithm for robot coverage and exploration based on sensor...
- et al.
GPS-less low-cost outdoor localization for very small devices
IEEE Personal Communications
(2000) - et al.
Movement control algorithms for realization of fault-tolerant ad hoc robot networks
IEEE Networks
(2004)
Measuring the survivability of a network: connectivity and rest-connectivity. European Transactions on Telecommunications
Cited by (80)
UAVs assisted Network Partition Detection and Connectivity Restoration in Wireless Sensor and Actor Networks
2022, Ad Hoc NetworksCitation Excerpt :Generally, a node may need to relocate simultaneously to serve two single node failures at different locations. The usage of synchronization mechanisms can solve this dispute [32,39]. The centralized techniques handle this case by resolving multiple single-node failures independently [40–43].
A Distributed Evolutionary algorithm for detecting minimum vertex cuts for wireless ad hoc and sensor networks
2019, Journal of Network and Computer ApplicationsDECK: A distributed, asynchronous and exact k-connectivity detection algorithm for Wireless Sensor Networks
2018, Computer CommunicationsCitation Excerpt :Finally, conclusions are drawn in Section 6. Connectivity detection and restoration for constant k values is a well-known research problem for various types of networks [31–37]. When k= 1, the problem is finding the cut vertices (articulation points) whose removal breaks the connectivity of the given graph.
Optimized repair of a partitioned network topology
2017, Computer NetworksDynamic weight-based connectivity recovery in wireless sensor and actor networks
2024, Journal of SupercomputingDynamic Weight-Based Connectivity Recovery in Wireless Sensor and Actor Networks
2023, Research Square