Resilient Wireless Sensor Networks Using Topology Control: A Review
---
paper_title: Research on Key Technology and Applications for Internet of Things

paper_content:

Abstract The Internet of Things (IOT) has been paid more and more attention by the academe, industry, and government all over the world. The concept of IOT and the architecture of IOT are discussed. The key technologies of IOT, including Radio Frequency Identification technology, Electronic Product Code technology, and ZigBee technology are analyzed. The framework of digital agriculture application based on IOT is proposed.
---
paper_title: The Internet of Things: A survey

paper_content:

This paper addresses the Internet of Things. Main enabling factor of this promising paradigm is the integration of several technologies and communications solutions. Identification and tracking technologies, wired and wireless sensor and actuator networks, enhanced communication protocols (shared with the Next Generation Internet), and distributed intelligence for smart objects are just the most relevant. As one can easily imagine, any serious contribution to the advance of the Internet of Things must necessarily be the result of synergetic activities conducted in different fields of knowledge, such as telecommunications, informatics, electronics and social science. In such a complex scenario, this survey is directed to those who want to approach this complex discipline and contribute to its development. Different visions of this Internet of Things paradigm are reported and enabling technologies reviewed. What emerges is that still major issues shall be faced by the research community. The most relevant among them are addressed in details.
---
paper_title: Wireless sensor networks: a survey

paper_content:

This paper describes the concept of sensor networks which has been made viable by the convergence of micro-electro-mechanical systems technology, wireless communications and digital electronics. First, the sensing tasks and the potential sensor networks applications are explored, and a review of factors influencing the design of sensor networks is provided. Then, the communication architecture for sensor networks is outlined, and the algorithms and protocols developed for each layer in the literature are explored. Open research issues for the realization of sensor networks are also discussed.
---
paper_title: Strategies and Techniques for Node Placement in Wireless Sensor Networks : A Survey

paper_content:

The major challenge in designing wireless sensor networks (WSNs) is the support of the functional, such as data latency, and the non-functional, such as data integrity, requirements while coping with the computation, energy and communication constraints. Careful node placement can be a very effective optimization means for achieving the desired design goals. In this paper, we report on the current state of the research on optimized node placement in WSNs. We highlight the issues, identify the various objectives and enumerate the different models and formulations. We categorize the placement strategies into static and dynamic depending on whether the optimization is performed at the time of deployment or while the network is operational, respectively. We further classify the published techniques based on the role that the node plays in the network and the primary performance objective considered. The paper also highlights open problems in this area of research.
---
paper_title: Resilience is more than availability

paper_content:

In applied sciences there is a tendency to rely on terminology that is either ill-defined or applied inconsistently across areas of research and application domains. Examples in information assurance include the terms resilience, robustness and survivability, where there exists subtle shades of meaning between researchers. These nuances can result in confusion and misinterpretations of goals and results, hampering communication and complicating collaboration. In this paper, we propose security-related definitions for these terms. Using this terminology, we argue that research in these areas must consider the functionality of the system holistically, beginning with a careful examination of what we actually want the system to do. We note that much of the published research focuses on a single aspect of a system -- availability -- as opposed to the system's ability to complete its function without disclosing confidential information or, to a lesser extent, with the correct output. Finally, we discuss ways in which researchers can explore resilience with respect to integrity, availability and confidentiality.
---
paper_title: Resilience and survivability in communication networks : Strategies , principles , and survey of disciplines

paper_content:

The Internet has become essential to all aspects of modern life, and thus the consequences of network disruption have become increasingly severe. It is widely recognised that the Internet is not sufficiently resilient, survivable, and dependable, and that significant research, development, and engineering is necessary to improve the situation. This paper provides an architectural framework for resilience and survivability in communication networks and provides a survey of the disciplines that resilience encompasses, along with significant past failures of the network infrastructure. A resilience strategy is presented to defend against, detect, and remediate challenges, a set of principles for designing resilient networks is presented, and techniques are described to analyse network resilience.
---
paper_title: Network resilience: a measure of network fault tolerance

paper_content:

A probabilistic measure of network fault tolerance expressed as the probability of a disconnection is proposed. Qualitative evaluation of this measure is presented. As expected, the single-node disconnection probability is the dominant factor irrespective of the topology under consideration. The authors derive an analytical approximation to the disconnection probability and verify it with a Monte Carlo simulation. On the basis of this model, the measures of network resilience and relative network resilience are proposed as probabilistic measures of network fault tolerance. These are used to evaluate the effects of the disconnection probability on the reliability of the system. >
---
paper_title: Designing evolvable systems in a framework of robust, resilient and sustainable engineering analysis

paper_content:

''Evolvability'' is a concept normally associated with biology or ecology, but recent work on control of interdependent critical infrastructures reveals that network informatics systems can be designed to enable artificial, human systems to ''evolve''. To explicate this finding, we draw on an analogy between disruptive behavior and stable variation in the history of science and the adaptive patterns of robustness and resilience in engineered systems. We present a definition of an evolvable system in the context of a model of robust, resilient and sustainable systems. Our review of this context and standard definitions indicates that many analysts in engineering (as well as in biology and ecology) do not differentiate Resilience from Robustness. Neither do they differentiate overall dependable system adaptability from a multi-phase process that includes graceful degradation and time-constrained recovery, restabilization, and prevention of catastrophic failure. We analyze how systemic Robustness, Resilience, and Sustainability are related to Evolvability. Our analysis emphasizes the importance of Resilience as an adaptive capability that integrates Sustainability and Robustness to achieve Evolvability. This conceptual framework is used to discuss nine engineering principles that should frame systems thinking about developing evolvable systems. These principles are derived from Kevin Kelly's book: Out of Control, which describes living and artificial self-sustaining systems. Kelly's last chapter, ''The Nine Laws of God,'' distills nine principles that govern all life-like systems. We discuss how these principles could be applied to engineering evolvability in artificial systems. This discussion is motivated by a wide range of practical problems in engineered artificial systems. Our goal is to analyze a few examples of system designs across engineering disciplines to explicate a common framework for designing and testing artificial systems. This framework highlights managing increasing complexity, intentional evolution, and resistance to disruptive events. From this perspective, we envision a more imaginative and time-sensitive appreciation of the evolution and operation of ''reliable'' artificial systems. We conclude with a short discussion of two hypothetical examples of engineering evolvable systems in network-centric communications using Error Resilient Data Fusion (ERDF) and cognitive radio.
---
paper_title: Highly-resilient, energy-efficient multipath routing in wireless sensor networks

paper_content:

Previously proposed sensor network data dissemination schemes require periodic low-rate flooding of data in order to allow recovery from failure. We consider constructing two kinds of multipaths to enable energy efficient recovery from failure of the shortest path between source and sink. Disjoint multipath has been studied in the literature. We propose a novel braided multipath scheme, which results in several partially disjoint multipath schemes. We find that braided multipaths are a viable alternative for energy-efficient recovery from isolated and patterned failures.
---
paper_title: Graph-theoretic analysis of structured peer-to-peer systems: routing distances and fault resilience

paper_content:

This paper examines graph-theoretic properties of existing peer-to-peer architectures and proposes a new infrastructure based on optimal diameter de Bruijn graphs. Since generalized de Bruijn graphs possess very short average routing distances and high resilience to node failure, they are well suited for structured peer-to-peer networks. Using the example of Chord, CAN, and de Bruijn, we first study routing performance, graph expansion, and clustering properties of each graph. We then examine bisection width, path overlap, and several other properties that affect routing and resilience of peer-to-peer networks. Having confirmed that de Bruijn graphs offer the best diameter and highest connectivity among the existing peer-to-peer structures, we offer a very simple incremental building process that preserves optimal properties of de Bruijn graphs under uniform user joins/departures. We call the combined peer-to-peer architecture ODRI -- Optimal Diameter Routing Infrastructure.
---
paper_title: Conceptualizing and measuring resilience: A key to disaster loss reduction

paper_content:

A multidisciplinary research project has examined ways to improve resilience, which can be measured by the functionality of an infrastructure system after a disaster and also by the time it takes for a system to return to previous levels of performance. In this article two project leaders present the components and dimensions of resilience and the implications for disaster response strategies.
---
paper_title: Integrated coverage and connectivity configuration in wireless sensor networks

paper_content:

An effective approach for energy conservation in wireless sensor networks is scheduling sleep intervals for extraneous nodes, while the remaining nodes stay active to provide continuous service. For the sensor network to operate successfully, the active nodes must maintain both sensing coverage and network connectivity. Furthermore, the network must be able to configure itself to any feasible degrees of coverage and connectivity in order to support different applications and environments with diverse requirements. This paper presents the design and analysis of novel protocols that can dynamically configure a network to achieve guaranteed degrees of coverage and connectivity. This work differs from existing connectivity or coverage maintenance protocols in several key ways: 1) We present a Coverage Configuration Protocol (CCP) that can provide different degrees of coverage requested by applications. This flexibility allows the network to self-configure for a wide range of applications and (possibly dynamic) environments. 2) We provide a geometric analysis of the relationship between coverage and connectivity. This analysis yields key insights for treating coverage and connectivity in a unified framework: this is in sharp contrast to several existing approaches that address the two problems in isolation. 3) Finally, we integrate CCP with SPAN to provide both coverage and connectivity guarantees. We demonstrate the capability of our protocols to provide guaranteed coverage and connectivity configurations, through both geometric analysis and extensive simulations.
---
paper_title: On secure and reliable communications in wireless sensor networks: Towards k-connectivity under a random pairwise key predistribution scheme

paper_content:

To be considered for an IEEE Jack Keil Wolf ISIT Student Paper Award. We study the secure and reliable connectivity of wireless sensor networks. Security is assumed to be ensured by the random pairwise key predistribution scheme of Chan, Perrig, and Song, and unreliable wireless links are represented by independent on/off channels. Modeling the network by an intersection of a random K-out graph and an Erdős-Renyi graph, we present scaling conditions (on the number of nodes, the scheme parameter K, and the probability of a wireless channel being on) such that the resulting graph contains no nodes with degree less than k with high probability, when the number of nodes gets large. Results are given in the form of zero-one laws and are shown to improve the previous results by Yagan and Makowski on the absence of isolated nodes (i.e., absence of nodes with degree zero). Via simulations, the established zero-one laws are shown to hold also for the property of k-connectivity; i.e., the property that graph remains connected despite the deletion of any k − 1 nodes or edges.
---
paper_title: On distributed fault-tolerant detection in wireless sensor networks

paper_content:

In this paper, we consider two important problems for distributed fault-tolerant detection in wireless sensor networks: 1) how to address both the noise-related measurement error and sensor fault simultaneously in fault-tolerant detection and 2) how to choose a proper neighborhood size n for a sensor node in fault correction such that the energy could be conserved. We propose a fault-tolerant detection scheme that explicitly introduces the sensor fault probability into the optimal event detection process. We mathematically show that the optimal detection error decreases exponentially with the increase of the neighborhood size. Experiments with both Bayesian and Neyman-Pearson approaches in simulated sensor networks demonstrate that the proposed algorithm is able to achieve better detection and better balance between detection accuracy and energy usage. Our work makes it possible to perform energy-efficient fault-tolerant detection in a wireless sensor network.
---
paper_title: Exact analysis of k-connectivity in secure sensor networks with unreliable links

paper_content:

The Eschenauer--Gligor (EG) random key predistribution scheme has been widely recognized as a typical approach to secure communications in wireless sensor networks (WSNs). However, there is a lack of precise probability analysis on the reliable connectivity of WSNs under the EG scheme. To address this, we rigorously derive the asymptotically exact probability of $k$-connectivity in WSNs employing the EG scheme with unreliable links represented by independent on/off channels, where $k$-connectivity ensures that the network remains connected despite the failure of any $(k-1)$ sensors or links. Our analytical results are confirmed via numerical experiments, and they provide precise guidelines for the design of secure WSNs that exhibit a desired level of reliability against node and link failures.
---
paper_title: Designing secure and reliable wireless sensor networks under a pairwise key predistribution scheme

paper_content:

We investigate k-connectivity in secure wireless sensor networks under the random pairwise key predistribution scheme with unreliable links; a network is said to be k-connected if it remains connected despite the failure of any of its (k − 1) nodes or links. With wireless communication links modeled as independent on-off channels, this amounts to analyzing a random graph model formed by intersecting a random K-out graph and an Erdős-Renyi graph. We present conditions on how to scale the parameters of this intersection model so that the resulting graph is k-connected with probability approaching to one (resp. zero) as the number of nodes gets large. The resulting zero-one law is shown to improve and sharpen the previous result on the 1-connectivity of the same model. We also provide numerical results to support our analysis and show that even in the finite node regime, our results can provide useful guidelines for designing sensor networks that are secure and reliable.
---
paper_title: Towards $k$-connectivity of the random graph induced by a pairwise key predistribution scheme with unreliable links

paper_content:

We study the secure and reliable connectivity of wireless sensor networks. Security is assumed to be ensured by the random pairwise key predistribution scheme of Chan, Perrig, and Song, and unreliable wireless links are represented by independent ON/OFF channels. Modeling the network by an intersection of a random $K$ -out graph and an Erdős–Renyi graph, we present scaling conditions (on the number of nodes $n$ , the scheme parameter $K$ , and the probability $p$ of a wireless channel being on), such that the resulting graph contains no nodes with a degree less than $k$ with high probability. Results are given in the form of zero–one laws with $n$ getting large, and are shown to improve the previous results by Yagan and Makowski on the absence of isolated nodes (i.e., absence of nodes with degree zero) in the same model. Through simulations, the established zero–one laws are also shown to hold for the property of $k$ -connectivity, i.e., the property that graph remains connected despite the deletion of any $k-1$ nodes or edges.
---
paper_title: On Topological Properties of Wireless Sensor Networks under the q-Composite Key Predistribution Scheme with On/Off Channels

paper_content:

The q-composite key predistribution scheme [1] is used prevalently for secure communications in large-scale wireless sensor networks (WSNs). Prior work [2]-[4] explores topological properties of WSNs employing the q-composite scheme for q = 1 with unreliable communication links modeled as independent on/off channels. In this paper, we investigate topological properties related to the node degree in WSNs operating under the q-composite scheme and the on/off channel model. Our results apply to general q and are stronger than those reported for the node degree in prior work even for the case of q being 1. Specifically, we show that the number of nodes with certain degree asymptotically converges in distribution to a Poisson random variable, present the asymptotic probability distribution for the minimum degree of the network, and establish the asymptotically exact probability for the property that the minimum degree is at least an arbitrary value. Numerical experiments confirm the validity of our analytical findings.
---
paper_title: Connectivity in Secure Wireless Sensor Networks under Transmission Constraints

paper_content:

In wireless sensor networks (WSNs), the Eschenauer-Gligor (EG) key pre-distribution scheme is a widely recognized way to secure communications. Although connectivity properties of secure WSNs with the EG scheme have been extensively investigated, few results address physical transmission constraints. These constraints reflect real-world implementations of WSNs in which two sensors have to be within a certain distance from each other to communicate. In this paper, we present zero-one laws for connectivity in WSNs employing the EG scheme under transmission constraints. These laws help specify the critical transmission ranges for connectivity. Our analytical findings are confirmed via numerical experiments. In addition to secure WSNs, our theoretical results are also applied to frequency hopping in wireless networks.
---
paper_title: THE MAXIMUM CONNECTIVITY OF A GRAPH

paper_content:

Abstract : The paper solves the problem of the maximum connectivity of any graph with a given number of points and lines. In addition, the minimum connectivity. The maximum diameter, and the minimum diameter are obtained. Two unsolved problems concerning the distribution of the values of the connectivity and the diameter are included.
---
paper_title: Secure k-connectivity in wireless sensor networks under an on/off channel model

paper_content:

Random key predistribution scheme of Eschenauer and Gligor (EG) is a typical solution for ensuring secure communications in a wireless sensor network (WSN). Connectivity of the WSNs under this scheme has received much interest over the last decade, and most of the existing work is based on the assumption of unconstrained sensor-to-sensor communications. In this paper, we study the k-connectivity of WSNs under the EG scheme with physical link constraints; k-connectivity is defined as the property that the network remains connected despite the failure of any (k - 1) sensors. We use a simple communication model, where unreliable wireless links are modeled as independent on/off channels, and derive zero-one laws for the properties that i) the WSN is k-connected, and ii) each sensor is connected to at least k other sensors. These zero-one laws improve the previous results by Rybarczyk on the k-connectivity under a fully connected communication model. Moreover, under the on/off channel model, we provide a stronger form of the zero-one law for the 1-connectivity as compared to that given by Yagan.
---
paper_title: Strategies and Techniques for Node Placement in Wireless Sensor Networks : A Survey

paper_content:

The major challenge in designing wireless sensor networks (WSNs) is the support of the functional, such as data latency, and the non-functional, such as data integrity, requirements while coping with the computation, energy and communication constraints. Careful node placement can be a very effective optimization means for achieving the desired design goals. In this paper, we report on the current state of the research on optimized node placement in WSNs. We highlight the issues, identify the various objectives and enumerate the different models and formulations. We categorize the placement strategies into static and dynamic depending on whether the optimization is performed at the time of deployment or while the network is operational, respectively. We further classify the published techniques based on the role that the node plays in the network and the primary performance objective considered. The paper also highlights open problems in this area of research.
---
paper_title: Deploying sensor networks with guaranteed capacity and fault tolerance

paper_content:

We consider the problem of deploying or repairing a sensor network to guarantee a specified level of multi-path connectivity (k-connectivity) between all nodes. Such a guarantee simultaneously provides fault tolerance against node failures and high capacity through multi-path routing. We design and analyze the first algorithms that place an almost-minimum number of additional sensors to augment an existing network into a k-connected network, for any desired parameter k. Our algorithms have provable guarantees on the quality of the solution. Specifically, we prove that the number of additional sensors is within a constant factor of the absolute minimum, for any fixed k. We have implemented greedy and distributed versions of this algorithm, and demonstrate in simulation that they produce high-quality placements for the additional sensors. We are also in the process of using our algorithms to deploy nodes in a physical sensor network using a mobile robot.
---
paper_title: Poly: A reliable and energy efficient topology control protocol for wireless sensor networks

paper_content:

Energy efficiency and reliability are the two important requirements for mission-critical wireless sensor networks. In the context of sensor topology control for routing and dissemination, Connected Dominating Set (CDS) based techniques proposed in prior literature provide the most promising efficiency and reliability. In a CDS-based topology control technique, a backbone - comprising a set of highly connected nodes - is formed which allows communication between any arbitrary pair of nodes in the network. In this paper, we show that formation of a polygon in the network provides a reliable and energy-efficient topology. Based on this observation, we propose Poly, a novel topology construction protocol based on the idea of polygons. We compare the performance of Poly with three prominent CDS-based topology construction protocols namely CDS-Rule K, Energy-efficient CDS (EECDS) and A3. Our simulation results demonstrate that Poly performs consistently better in terms of message overhead and other selected metrics. We also model the reliability of Poly and compare it with other CDS-based techniques to show that it achieves better connectivity under highly dynamic network topologies.
---
paper_title: An energy-efficient topology construction algorithm for wireless sensor networks

paper_content:

Topology management schemes have emerged as promising approaches for prolonging the lifetime of the wireless sensor networks (WSNs). The connected dominating set (CDS) concept has also emerged as the most popular method for energy-efficient topology control in WSNs. A sparse CDS-based network topology is highly susceptible to partitioning, while a dense CDS leads to excessive energy consumption due to overlapped sensing areas. Therefore, finding an optimal-size CDS with which a good trade-off between the network lifetime and network coverage can be made is a crucial problem in CDS-based topology control. In this paper, a degree-constrained minimum-weight version of the CDS problem, seeking for the load-balanced network topology with the maximum energy, is presented to model the energy-efficient topology control problem in WSNs. A learning automata-based heuristic is proposed for finding a near optimal solution to the proxy equivalent degree-constrained minimum-weight CDS problem in WSN. A strong theorem in presented to show the convergence of the proposed algorithm. Superiority of the proposed topology control algorithm over the prominent existing methods is shown through the simulation experiments in terms of the number of active nodes (network topology size), control message overhead, residual energy level, and network lifetime.
---
paper_title: Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons

paper_content:

Motivated by routing issues in ad hoc networks, we present polylogarithmic-time distributed algorithms for two problems. Given a network, we first show how to compute connected and weakly connected dominating sets whose size is at most O([email protected]) times the optimum, @D being the maximum degree of the input network. This is best-possible if [email protected]?DTIME[n^O^(^l^o^g^l^o^g^n^)] and if the processors are required to run in polynomial-time. We then show how to construct dominating sets that have the above properties, as well as the ''low stretch'' property that any two adjacent nodes in the network have their dominators at a distance of at most O(logn) in the output network. (Given a dominating set S, a dominator of a vertex u is any [email protected]?S such that the distance between u and v is at most one.) We also show our time bounds to be essentially optimal.
---
paper_title: Impact of random failures and attacks on Poisson and power-law random networks

paper_content:

It appeared recently that the underlying degree distribution of networks may play a crucial role concerning their robustness. Empiric and analytic results have been obtained, based on asymptotic and mean-field approximations. Previous work insisted on the fact that power-law degree distributions induce high resilience to random failure but high sensitivity to attack strategies, while Poisson degree distributions are quite sensitive in both cases. Then, much work has been done to extend these results. ::: We aim here at studying in depth these results, their origin, and limitations. We review in detail previous contributions and give full proofs in a unified framework, and identify the approximations on which these results rely. We then present new results aimed at enlightening some important aspects. We also provide extensive rigorous experiments which help evaluate the relevance of the analytic results. ::: We reach the conclusion that, even if the basic results of the field are clearly true and important, they are in practice much less striking than generally thought. The differences between random failures and attacks are not so huge and can be explained with simple facts. Likewise, the differences in the behaviors induced by power-law and Poisson distributions are not as striking as often claimed.
---
paper_title: Fault-Tolerant Relay Node Placement in Heterogeneous Wireless Sensor Networks

paper_content:

Existing work on placing additional relay nodes in wireless sensor networks to improve network connectivity typically assumes homogeneous wireless sensor nodes with an identical transmission radius. In contrast, this paper addresses the problem of deploying relay nodes to provide fault-tolerance with higher network connectivity in heterogeneous wireless sensor networks, where sensor nodes possess different transmission radii. Depending on the level of desired fault-tolerance, such problems can be categorized as: (1) full fault-tolerance relay node placement, which aims to deploy a minimum number of relay nodes to establish k (k ges 1) vertex-disjoint paths between every pair of sensor and/or relay nodes; (2) partial fault-tolerance relay node placement, which aims to deploy a minimum number of relay nodes to establish k (k ges 1) vertex-disjoint paths only between every pair of sensor nodes. Due to the different transmission radii of sensor nodes, these problems are further complicated by the existence of two different kinds of communication paths in heterogeneous wireless sensor networks, namely two-way paths, along which wireless communications exist in both directions; and one-way paths, along which wireless communications exist in only one direction. Assuming that sensor nodes have different transmission radii, while relay nodes use the same transmission radius, this paper comprehensively analyzes the range of problems introduced by the different levels of fault-tolerance (full or partial) coupled with the different types of path (one-way or two-way). Since each of these problems is NP-hard, we develop O(sigmak2)-approximation algorithms for both one-way and two-way partial fault-tolerance relay node placement, as well as O(sigmak3)-approximation algorithms for both one-way and two-way full fault-tolerance relay node placement (sigma is the best performance ratio of existing approximation algorithms for finding a minimum k-vertex connected spanning graph). To facilitate the applications in higher dimensions, we also extend these algorithms and derive their performance ratios in d-dimensional heterogeneous wireless sensor networks (d ges 3). Finally, heuristic implementations of these algorithms are evaluated via simulations.
---
paper_title: Approximation algorithms for connected dominating sets

paper_content:

The dominating set problem in graphs asks for a minimum size subset of vertices with the following property: each vertex is required to either be in the dominating set, or adjacent to at least one node in the dominating set. We focus on the question of finding a connected dominating set of minimum size, where the graph induced by vertices in the dominating set is required to be connected. This problem arises in network testing, as well as in wireless communication.
---
paper_title: Radio irregularity problem in wireless sensor networks: New experimental results

paper_content:

A key design issue in wireless networks is represented by the irregular and dynamic radio coverage at each node. This is especially true for wireless sensor networks, which usually employ low quality radio modules to reduce the cost. It results in irregularity in radio coverage and variations in packet reception in different directions. Due to its likely impact on the upper layer protocols, many services, such as localization, routing and others, needs to be resilient to the irregular and dynamic radio propagation, and to include mechanisms to deal with these problems. As such, accurate models of radio propagation patterns are important for protocol design and evaluation. In this paper, measurements of radio propagation patterns have been carried out using the motes themselves. With empirical data obtained from the Mica2 platforms we were able to observe and further quantify such phenomena. The results demonstrate that the radio pattern is largely random; however, radio signal attenuation varies along different direction, and more importantly, is time-varying while stationary.
---
paper_title: Impact of radio irregularity on wireless sensor networks

paper_content:

In this paper, we investigate the impact of radio irregularity on the communication performance in wireless sensor networks. Radio irregularity is a common phenomenon which arises from multiple factors, such as variance in RF sending power and different path losses depending on the direction of propagation. From our experiments, we discover that the variance in received signal strength is largely random; however, it exhibits a continuous change with incremental changes in direction. With empirical data obtained from the MICA2 platform, we establish a radio model for simulation, called the Radio Irregularity Model (RIM). This model is the first to bridge the discrepancy between spherical radio models used by simulators and the physical reality of radio signals. With this model, we are able to analyze the impact of radio irregularity on some of the well-known MAC and routing protocols. Our results show that radio irregularity has a significant impact on routing protocols, but a relatively small impact on MAC protocols. Finally, we propose six solutions to deal with radio irregularity. We evaluate two of them in detail. The results obtained from both the simulation and a running testbed demonstrate that our solutions greatly improve communication performance in the presence of radio irregularity.
---
paper_title: Finding Minimum Energy Disjoint Paths in Wireless Ad-Hoc Networks

paper_content:

We develop algorithms for finding minimum energy disjoint paths in an all-wireless network, for both the node and link-disjoint cases. Our major results include a novel polynomial time algorithm that optimally solves the minimum energy 2 link-disjoint paths problem, as well as a polynomial time algorithm for the minimum energy k node-disjoint paths problem. In addition, we present efficient heuristic algorithms for both problems. Our results show that link-disjoint paths consume substantially less energy than node-disjoint paths. We also found that the incremental energy of additional link-disjoint paths is decreasing. This finding is some what surprising due to the fact that in general networks additional paths are typically longer than the shortest path. However, in a wireless network, additional paths can be obtained at lower energy due to the broadcast nature of the wireless medium. Finally, we discuss issues regarding distributed implementation and present distributed versions of the optimal centralized algorithms presented in the paper.
---
paper_title: Fault tolerance measures for large-scale wireless sensor networks

paper_content:

Connectivity, primarily a graph-theoretic concept, helps define the fault tolerance of wireless sensor networks (WSNs) in the sense that it enables the sensors to communicate with each other so their sensed data can reach the sink. On the other hand, sensing coverage, an intrinsic architectural feature of WSNs plays an important role in meeting application-specific requirements, for example, to reliably extract relevant data about a sensed field. Sensing coverage and network connectivity are not quite orthogonal concepts. In fact, it has been proven that connectivity strongly depends on coverage and hence considerable attention has been paid to establish tighter connection between them although only loose lower bound on network connectivity of WSNs is known. In this article, we investigate connectivity based on the degree of sensing coverage by studying k-covered WSNs, where every location in the field is simultaneously covered (or sensed) by at least k sensors (property known as k-coverage, where k is the degree of coverage). We observe that to derive network connectivity of k-covered WSNs, it is necessary to compute the sensor spatial density required to guarantee k-coverage. More precisely, we propose to use a model, called the Reuleaux Triangle, to characterize k-coverage with the help of Helly's Theorem and the analysis of the intersection of sensing disks of k sensors. Using a deterministic approach, we show that the sensor spatial density to guarantee k-coverage of a convex field is proportional to k and inversely proportional to the sensing range of the sensors. We also prove that network connectivity of k-covered WSNs is higher than their sensing coverage k. Furthermore, we propose a new measure of fault tolerance for k-covered WSNs, called conditional fault tolerance, based on the concepts of conditional connectivity and forbidden faulty sensor set that includes all the neighbors of a given sensor. We prove that k-covered WSNs can sustain a large number of sensor failures provided that the faulty sensor set does not include a forbidden faulty sensor set.
---
paper_title: Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networks

paper_content:

In ad hoc wireless networks, it is crucial to minimize power consumption while maintaining key network properties. This work studies power assignments of wireless devices that minimize power while maintaining k-fault tolerance. Specifically, we require all links established by this power setting be symmetric and form a k-vertex connected subgraph of the network graph. This problem is known to be NP-hard. We show current heuristic approaches can use arbitrarily more power than the optimal solution. Hence, we seek approximation algorithms for this problem. We present three approximation algorithms. The first algorithm gives an O(kalpha)-approximation where is the best approximation factor for the related problem in wired networks (the best alpha so far is O(log k)). With a more careful analysis, we show our second (slightly more complicated) algorithm is an O(k)-approximation. Our third algorithm assumes that the edge lengths of the network graph form a metric. In this case, we present simple and practical distributed algorithms for the cases of 2- and 3-connectivity with constant approximation factors. We generalize this algorithm to obtain an O(k2c+2)-approximation for general k-connectivity (2 les c les 4 is the power attenuation exponent). Finally, we show that these approximation algorithms compare favorably with existing heuristics. We note that all algorithms presented in this paper can be used to minimize power while maintaining -edge connectivity with guaranteed approximation factors. Recently, different set of authors used the notion of k-connectivity and the results of this paper to deal with the fault-tolerance issues for static wireless network settings.
---
paper_title: Robust topology control for indoor wireless sensor networks

paper_content:

Topology control can reduce power consumption and channel contention in wireless sensor networks by adjusting the transmission power. However, topology control for wireless sensor networks faces significant challenges, especially in indoor environments where wireless characteristics are extremely complex and dynamic. We first provide insights on the design of robust topology control schemes based on an empirical study in an office building. For example, our analysis shows that Received Signal Strength Indicator and Link Quality Indicator are not always robust indicators of Packet Reception Rate in indoor environments due to significant multi-path effects. We then present Adaptive and Robust Topology control (ART), a novel and practical topology control algorithm with several salient features: (1) ART is robust in indoor environments as it does not rely on simplifying assumptions about the wireless properties; (2) ART can adapt to variations in both link quality and contention; (3) ART introduces zero communication overhead for applications which already use acknowledgements. We have implemented ART as a topology layer in TinyOS 2.x. Our topology layer only adds 12 bytes of RAM per neighbor and 1.5 kilobytes of ROM, and requires minimal changes to upper-layer routing protocols. The advantages of ART have been demonstrated through empirical results on a 28-node indoor testbed.
---
paper_title: Efficient topology control for ad-hoc wireless networks with non-uniform transmission ranges

paper_content:

Wireless network topology control has drawn considerable attention recently. Priori arts assumed that the wireless ad hoc networks are modeled by unit disk graphs (UDG), i.e., two mobile hosts can communicate as long as their Euclidean distance is no more than a threshold. However, practically, the networks are never so perfect as unit disk graphs: the transmission ranges may vary due to various reasons such as the device differences, the network control necessity, and the perturbation of the transmission ranges even the transmission ranges are set as the same originally. Thus, we assume that each mobile host has its own transmission range. The networks are modeled by mutual inclusion graphs (MG), where two nodes are connected iff they are within the transmission range of each other. Previously, no method is known for topology control when the networks are modeled as mutual inclusion graphs.The paper proposes the first distributed mechanism to build a sparse power efficient network topology for ad hoc wireless networks with non-uniform transmission ranges. We first extend the Yao structure to build a spanner with a constant length and power stretch factor for mutual inclusion graph. We then propose two efficient localized algorithms to construct connected sparse network topologies. The first structure, called extended Yao-Yao, has node degree at most O(log γ), where γ = maxu maxuv∈MG ru/rv. The second structure, called extended Yao and Sink, has node degree bounded by O(log γ), and is a length and power spanner. The methods are based on a novel partition strategy of the space surrounded each mobile host. Both algorithms have communication cost O(n) under a local broadcasting communication model, where each message has O(log n) bits.
---
paper_title: Deploying sensor networks with guaranteed capacity and fault tolerance

paper_content:

We consider the problem of deploying or repairing a sensor network to guarantee a specified level of multi-path connectivity (k-connectivity) between all nodes. Such a guarantee simultaneously provides fault tolerance against node failures and high capacity through multi-path routing. We design and analyze the first algorithms that place an almost-minimum number of additional sensors to augment an existing network into a k-connected network, for any desired parameter k. Our algorithms have provable guarantees on the quality of the solution. Specifically, we prove that the number of additional sensors is within a constant factor of the absolute minimum, for any fixed k. We have implemented greedy and distributed versions of this algorithm, and demonstrate in simulation that they produce high-quality placements for the additional sensors. We are also in the process of using our algorithms to deploy nodes in a physical sensor network using a mobile robot.
---
paper_title: An effective approach for tolerating simultaneous failures in wireless sensor and actor networks

paper_content:

Wireless Sensor and Actor Networks (WSANs) engage mobile nodes with actuators to respond to certain events in inhospitable environments. The harsh surroundings make actors susceptible to failure. Tolerating occasional actor failure is very important to avoid degrading the performance. In some cases, multiple actors simultaneously fail which makes the recovery very challenging. In this paper, we propose a new recovery approach which can handle simultaneous failures in WSANs. The approach is based on ranking network nodes relevant to a pre-assigned root actor. Ranking creates a tree to be used for coordinating the recovery among nodes. To minimize the recovery overhead, the nodes are virtually grouped to clusters and each node is assigned a recovery weight as well as a nearby cluster member which serves as a gateway to lost nodes. Designation of cluster heads is based on the number of children in the recovery tree. The simulation results confirm the correctness and effectiveness of the proposed approach in restoring network connectivity and also show that on the average the incurred overhead is low compared to contemporary single-failure recovery approaches.
---
paper_title: Octopus: a fault-tolerant and efficient ad-hoc routing protocol

paper_content:

Mobile ad-hoc networks (MANETs) are failure-prone environments; it is common for mobile wireless nodes to intermittently disconnect from the network, e.g., due to signal blockage. This paper focuses on withstanding such failures in large MANETs: we present Octopus, a fault-tolerant and efficient position-based routing protocol. Fault-tolerance is achieved by employing redundancy, i.e., storing the location of each node at many other nodes, and by keeping frequently refreshed soft state. At the same time, Octopus achieves a low location update overhead by employing a novel aggregation technique, whereby a single packet updates the location of many nodes at many other nodes. Octopus is highly scalable: for a fixed node density, the number of location update packets sent does not grow with the network size. And when the density increases, the overhead drops. Thorough empirical evaluation using the ns2 simulator with up to 675 mobile nodes shows that Octopus achieves excellent fault-tolerance at a modest overhead: when all nodes intermittently disconnect and reconnect, Octopus achieves the same high reliability as when all nodes are constantly up.
---
paper_title: Impact of random failures and attacks on Poisson and power-law random networks

paper_content:

It appeared recently that the underlying degree distribution of networks may play a crucial role concerning their robustness. Empiric and analytic results have been obtained, based on asymptotic and mean-field approximations. Previous work insisted on the fact that power-law degree distributions induce high resilience to random failure but high sensitivity to attack strategies, while Poisson degree distributions are quite sensitive in both cases. Then, much work has been done to extend these results. ::: We aim here at studying in depth these results, their origin, and limitations. We review in detail previous contributions and give full proofs in a unified framework, and identify the approximations on which these results rely. We then present new results aimed at enlightening some important aspects. We also provide extensive rigorous experiments which help evaluate the relevance of the analytic results. ::: We reach the conclusion that, even if the basic results of the field are clearly true and important, they are in practice much less striking than generally thought. The differences between random failures and attacks are not so huge and can be explained with simple facts. Likewise, the differences in the behaviors induced by power-law and Poisson distributions are not as striking as often claimed.
---
paper_title: Localized and Energy-Efficient Topology Control in Wireless Sensor Networks Using Fuzzy-Logic Control Approaches

paper_content:

The sensor nodes in the Wireless Sensor Networks (WSNs) are prone to failures due to many reasons, for example, running out of battery or harsh environment deployment; therefore, the WSNs are expected to be able to maintain network connectivity and tolerate certain amount of node failures. By applying fuzzy-logic approach to control the network topology, this paper aims at improving the network connectivity and fault-tolerant capability in response to node failures, while taking into account that the control approach has to be localized and energy efficient. Two fuzzy controllers are proposed in this paper: one is Learning-based Fuzzy-logic Topology Control (LFTC), of which the fuzzy controller is learnt from a training data set; another one is Rules-based Fuzzy-logic Topology Control (RFTC), of which the fuzzy controller is obtained through designing if-then rules and membership functions. Both LFTC and RFTC do not rely on location information, and they are localized. Comparing them with other three representative algorithms (LTRT, List-based, and NONE) through extensive simulations, our two proposed fuzzy controllers have been proved to be very energy efficient to achieve desired node degree and improve the network connectivity when sensor nodes run out of battery or are subject to random attacks.
---
paper_title: Highly-resilient, energy-efficient multipath routing in wireless sensor networks

paper_content:

Previously proposed sensor network data dissemination schemes require periodic low-rate flooding of data in order to allow recovery from failure. We consider constructing two kinds of multipaths to enable energy efficient recovery from failure of the shortest path between source and sink. Disjoint multipath has been studied in the literature. We propose a novel braided multipath scheme, which results in several partially disjoint multipath schemes. We find that braided multipaths are a viable alternative for energy-efficient recovery from isolated and patterned failures.
---
paper_title: Fault tolerance measures for large-scale wireless sensor networks

paper_content:

Connectivity, primarily a graph-theoretic concept, helps define the fault tolerance of wireless sensor networks (WSNs) in the sense that it enables the sensors to communicate with each other so their sensed data can reach the sink. On the other hand, sensing coverage, an intrinsic architectural feature of WSNs plays an important role in meeting application-specific requirements, for example, to reliably extract relevant data about a sensed field. Sensing coverage and network connectivity are not quite orthogonal concepts. In fact, it has been proven that connectivity strongly depends on coverage and hence considerable attention has been paid to establish tighter connection between them although only loose lower bound on network connectivity of WSNs is known. In this article, we investigate connectivity based on the degree of sensing coverage by studying k-covered WSNs, where every location in the field is simultaneously covered (or sensed) by at least k sensors (property known as k-coverage, where k is the degree of coverage). We observe that to derive network connectivity of k-covered WSNs, it is necessary to compute the sensor spatial density required to guarantee k-coverage. More precisely, we propose to use a model, called the Reuleaux Triangle, to characterize k-coverage with the help of Helly's Theorem and the analysis of the intersection of sensing disks of k sensors. Using a deterministic approach, we show that the sensor spatial density to guarantee k-coverage of a convex field is proportional to k and inversely proportional to the sensing range of the sensors. We also prove that network connectivity of k-covered WSNs is higher than their sensing coverage k. Furthermore, we propose a new measure of fault tolerance for k-covered WSNs, called conditional fault tolerance, based on the concepts of conditional connectivity and forbidden faulty sensor set that includes all the neighbors of a given sensor. We prove that k-covered WSNs can sustain a large number of sensor failures provided that the faulty sensor set does not include a forbidden faulty sensor set.
---
paper_title: Recovery from multiple simultaneous failures in wireless sensor networks using minimum Steiner tree

paper_content:

In some applications, wireless sensor networks (WSNs) operate in very harsh environments and nodes become subject to increased risk of damage. Sometimes a WSN suffers from the simultaneous failure of multiple sensors and gets partitioned into disjoint segments. Restoring network connectivity in such a case is crucial in order to avoid negative effects on the application. Given that WSNs often operate unattended in remote areas, the recovery should be autonomous. This paper promotes an effective strategy for restoring the connectivity among these segments by populating the least number of relay nodes. Finding the optimal count and position of relay nodes is NP-hard and heuristics are thus pursued. We propose a Distributed algorithm for Optimized Relay node placement using Minimum Steiner tree (DORMS). Since in autonomously operating WSNs it is infeasible to perform a network-wide analysis to diagnose where segments are located, DORMS moves relay nodes from each segment toward the center of the deployment area. As soon as those relays become in range of each other, the partitioned segments resume operation. DORMS further model such initial inter-segment topology as Steiner tree in order to minimize the count of required relays. Disengaged relays can return to their respective segments to resume their pre-failure duties. We analyze DORMS mathematically and explain the beneficial aspects of the resulting topology with respect to connectivity, and traffic balance. The performance of DORMS is validated through extensive simulation experiments.
---
paper_title: Network resilience: a measure of network fault tolerance

paper_content:

A probabilistic measure of network fault tolerance expressed as the probability of a disconnection is proposed. Qualitative evaluation of this measure is presented. As expected, the single-node disconnection probability is the dominant factor irrespective of the topology under consideration. The authors derive an analytical approximation to the disconnection probability and verify it with a Monte Carlo simulation. On the basis of this model, the measures of network resilience and relative network resilience are proposed as probabilistic measures of network fault tolerance. These are used to evaluate the effects of the disconnection probability on the reliability of the system. >
---
paper_title: Impact of random failures and attacks on Poisson and power-law random networks

paper_content:

It appeared recently that the underlying degree distribution of networks may play a crucial role concerning their robustness. Empiric and analytic results have been obtained, based on asymptotic and mean-field approximations. Previous work insisted on the fact that power-law degree distributions induce high resilience to random failure but high sensitivity to attack strategies, while Poisson degree distributions are quite sensitive in both cases. Then, much work has been done to extend these results. ::: We aim here at studying in depth these results, their origin, and limitations. We review in detail previous contributions and give full proofs in a unified framework, and identify the approximations on which these results rely. We then present new results aimed at enlightening some important aspects. We also provide extensive rigorous experiments which help evaluate the relevance of the analytic results. ::: We reach the conclusion that, even if the basic results of the field are clearly true and important, they are in practice much less striking than generally thought. The differences between random failures and attacks are not so huge and can be explained with simple facts. Likewise, the differences in the behaviors induced by power-law and Poisson distributions are not as striking as often claimed.
---
paper_title: Modelling wireless challenges

paper_content:

A thorough understanding of the network behaviour when exposed to challenges is of paramount importance to construct a resilient MANET (mobile ad hoc network). However, modelling mobile and wireless networks as well as challenges against them is non-trivial due to dynamic and intermittent connectivity caused by channel fading and mobility of the nodes. We treat MANETs as time-varying graphs (TVGs) represented as a weighted adjacency matrix, in which the weights denote the link availability. We present how centrality-based attacks could affect network performance for different routing protocols. Furthermore, we model propagation loss models that represent realistic area-based challenges in wireless networks.
---
paper_title: Octopus: a fault-tolerant and efficient ad-hoc routing protocol

paper_content:

Mobile ad-hoc networks (MANETs) are failure-prone environments; it is common for mobile wireless nodes to intermittently disconnect from the network, e.g., due to signal blockage. This paper focuses on withstanding such failures in large MANETs: we present Octopus, a fault-tolerant and efficient position-based routing protocol. Fault-tolerance is achieved by employing redundancy, i.e., storing the location of each node at many other nodes, and by keeping frequently refreshed soft state. At the same time, Octopus achieves a low location update overhead by employing a novel aggregation technique, whereby a single packet updates the location of many nodes at many other nodes. Octopus is highly scalable: for a fixed node density, the number of location update packets sent does not grow with the network size. And when the density increases, the overhead drops. Thorough empirical evaluation using the ns2 simulator with up to 675 mobile nodes shows that Octopus achieves excellent fault-tolerance at a modest overhead: when all nodes intermittently disconnect and reconnect, Octopus achieves the same high reliability as when all nodes are constantly up.
---
paper_title: On distributed fault-tolerant detection in wireless sensor networks

paper_content:

In this paper, we consider two important problems for distributed fault-tolerant detection in wireless sensor networks: 1) how to address both the noise-related measurement error and sensor fault simultaneously in fault-tolerant detection and 2) how to choose a proper neighborhood size n for a sensor node in fault correction such that the energy could be conserved. We propose a fault-tolerant detection scheme that explicitly introduces the sensor fault probability into the optimal event detection process. We mathematically show that the optimal detection error decreases exponentially with the increase of the neighborhood size. Experiments with both Bayesian and Neyman-Pearson approaches in simulated sensor networks demonstrate that the proposed algorithm is able to achieve better detection and better balance between detection accuracy and energy usage. Our work makes it possible to perform energy-efficient fault-tolerant detection in a wireless sensor network.
---
paper_title: Sensor network data fault types

paper_content:

Little of the work in sensor network studies related to data quality has presented a detailed study of sensor faults and fault models. We provide a comprehensive look at sensor network data fault types and a unified basis for describing sensor faults backed up by real world deployment examples. We also identify several considerations one must take into account when developing a fault detection or diagnosis system. We suggest a broad framework of important considerations when developing a data fault detection system and discuss some assumptions that can be made in this context. Based upon experience and previous work we define a series of features to consider when modeling sensor data for either fault detection or fault correction. We define three main headings of types of features and explore the effect that each type has on a sensor. Then we list all common faults that we have observed in actual sensor network deployments. We provide an example of how one may use such a taxonomy of faults.
---
paper_title: Fault-tolerant target detection in sensor networks

paper_content:

Fault-tolerant target detection and localization is a challenging task in collaborative sensor networks. The paper introduces our exploratory work toward identifying a stationary target in sensor networks with faulty sensors. We explore both spatial and temporal dimensions for data aggregation to decrease the false alarm rate and improve the target position accuracy. To filter out extreme measurements, the median of all readings in the close neighborhood is used to approximate the local observation to the target. The sensor whose observation is a local maximum computes a position estimate at each epoch. Results from multiple epochs are combined to decrease the false alarm rate further and improve the target localization accuracy. Our algorithms have low computation and communication overheads. A simulation study demonstrates the validity and efficiency of our design.
---
paper_title: Localized fault-tolerant event boundary detection in sensor networks

paper_content:

This paper targets the identification of faulty sensors and detection of the reach of events in sensor networks with faulty sensors. Typical applications include the detection of the transportation front line of a contamination and the diagnosis of network health. We propose and analyze two novel algorithms for faulty sensor identification and fault-tolerant event boundary detection. These algorithms are purely localized and thus scale well to large sensor networks. Their computational overhead is low, since only simple numerical operations are involved. Simulation results indicate that these algorithms can clearly detect the event boundary and can identify faulty sensors with a high accuracy and a low false alarm rate when as many as 20% sensors become faulty. Our work is exploratory in that the proposed algorithms can accept any kind of scalar values as inputs, a dramatic improvement over existing works that take only 0/1 decision predicates. Therefore, our algorithms are generic. They can be applied as long as the "events" can be modelled by numerical numbers. Though designed for sensor networks, our algorithms can be applied to the outlier detection and regional data analysis in spatial data mining.
---
paper_title: Fault detection of wireless sensor networks

paper_content:

This paper presents a distributed fault detection algorithm for wireless sensor networks. Faulty sensor nodes are identified based on comparisons between neighboring nodes and dissemination of the decision made at each node. Time redundancy is used to tolerate transient faults in sensing and communication. To eliminate delay involved in time redundancy scheme a sliding window is employed with some storage for previous comparison results. Simulation results show that sensor nodes with permanent faults are identified with high accuracy for a wide range of fault rates, while most of the transient faults are tolerated with negligible performance degradation.
---
paper_title: Random coverage with guaranteed connectivity: joint scheduling for wireless sensor networks

paper_content:

Sensor scheduling plays a critical role for energy efficiency of wireless sensor networks. Traditional methods for sensor scheduling use either sensing coverage or network connectivity, but rarely both. In this paper, we deal with a challenging task: without accurate location information, how do we schedule sensor nodes to save energy and meet both constraints of sensing coverage and network connectivity? Our approach utilizes an integrated method that provides statistical sensing coverage and guaranteed network connectivity. We use random scheduling for sensing coverage and then turn on extra sensor nodes, if necessary, for network connectivity. Our method is totally distributed, is able to dynamically adjust sensing coverage with guaranteed network connectivity, and is resilient to time asynchrony. We present analytical results to disclose the relationship among node density, scheduling parameters, coverage quality, detection probability, and detection delay. Analytical and simulation results demonstrate the effectiveness of our joint scheduling method
---
paper_title: Distributed protocols for ensuring both coverage and connectivity of a wireless sensor network

paper_content:

Wireless sensor networks have attracted a lot of attention recently. Such environments may consist of many inexpensive nodes, each capable of collecting, storing, and processing environmental information, and communicating with neighboring nodes through wireless links. For a sensor network to operate successfully, sensors must maintain both sensing coverage and network connectivity. This issue has been studied in wang et al. [2003] and Zhang and Hou [2004a], both of which reach a similar conclusion that coverage can imply connectivity as long as sensors' communication ranges are no less than twice their sensing ranges. In this article, without relying on this strong assumption, we investigate the issue from a different angle and develop several necessary and sufficient conditions for ensuring coverage and connectivity of a sensor network. Hence, the results significantly generalize the results in Wang et al. [2003] and Zhang and Hou [2004a]. This work is also a significant extension of our earlier work [Huang and Tseng 2003; Huang et al. 2004], which addresses how to determine the level of coverage of a given sensor network but does not consider the network connectivity issue. Our work is the first work allowing an arbitrary relationship between sensing ranges and communication distances of sensor nodes. We develop decentralized solutions for determining, or even adjusting, the levels of coverage and connectivity of a given network. Adjusting levels of coverage and connectivity is necessary when sensors are overly deployed, and we approach this problem by putting sensors to sleep mode and tuning their transmission powers. This results in prolonged network lifetime.
---
paper_title: Integrated coverage and connectivity configuration in wireless sensor networks

paper_content:

An effective approach for energy conservation in wireless sensor networks is scheduling sleep intervals for extraneous nodes, while the remaining nodes stay active to provide continuous service. For the sensor network to operate successfully, the active nodes must maintain both sensing coverage and network connectivity. Furthermore, the network must be able to configure itself to any feasible degrees of coverage and connectivity in order to support different applications and environments with diverse requirements. This paper presents the design and analysis of novel protocols that can dynamically configure a network to achieve guaranteed degrees of coverage and connectivity. This work differs from existing connectivity or coverage maintenance protocols in several key ways: 1) We present a Coverage Configuration Protocol (CCP) that can provide different degrees of coverage requested by applications. This flexibility allows the network to self-configure for a wide range of applications and (possibly dynamic) environments. 2) We provide a geometric analysis of the relationship between coverage and connectivity. This analysis yields key insights for treating coverage and connectivity in a unified framework: this is in sharp contrast to several existing approaches that address the two problems in isolation. 3) Finally, we integrate CCP with SPAN to provide both coverage and connectivity guarantees. We demonstrate the capability of our protocols to provide guaranteed coverage and connectivity configurations, through both geometric analysis and extensive simulations.
---
paper_title: Coverage problems in sensor networks: A survey

paper_content:

Sensor networks, which consist of sensor nodes each capable of sensing environment and transmitting data, have lots of applications in battlefield surveillance, environmental monitoring, industrial diagnostics, etc. Coverage which is one of the most important performance metrics for sensor networks reflects how well a sensor field is monitored. Individual sensor coverage models are dependent on the sensing functions of different types of sensors, while network-wide sensing coverage is a collective performance measure for geographically distributed sensor nodes. This article surveys research progress made to address various coverage problems in sensor networks. We first provide discussions on sensor coverage models and design issues. The coverage problems in sensor networks can be classified into three categories according to the subject to be covered. We state the basic coverage problems in each category, and review representative solution approaches in the literature. We also provide comments and discussions on some extensions and variants of these basic coverage problems.
---
paper_title: Fault tolerance measures for large-scale wireless sensor networks

paper_content:

Connectivity, primarily a graph-theoretic concept, helps define the fault tolerance of wireless sensor networks (WSNs) in the sense that it enables the sensors to communicate with each other so their sensed data can reach the sink. On the other hand, sensing coverage, an intrinsic architectural feature of WSNs plays an important role in meeting application-specific requirements, for example, to reliably extract relevant data about a sensed field. Sensing coverage and network connectivity are not quite orthogonal concepts. In fact, it has been proven that connectivity strongly depends on coverage and hence considerable attention has been paid to establish tighter connection between them although only loose lower bound on network connectivity of WSNs is known. In this article, we investigate connectivity based on the degree of sensing coverage by studying k-covered WSNs, where every location in the field is simultaneously covered (or sensed) by at least k sensors (property known as k-coverage, where k is the degree of coverage). We observe that to derive network connectivity of k-covered WSNs, it is necessary to compute the sensor spatial density required to guarantee k-coverage. More precisely, we propose to use a model, called the Reuleaux Triangle, to characterize k-coverage with the help of Helly's Theorem and the analysis of the intersection of sensing disks of k sensors. Using a deterministic approach, we show that the sensor spatial density to guarantee k-coverage of a convex field is proportional to k and inversely proportional to the sensing range of the sensors. We also prove that network connectivity of k-covered WSNs is higher than their sensing coverage k. Furthermore, we propose a new measure of fault tolerance for k-covered WSNs, called conditional fault tolerance, based on the concepts of conditional connectivity and forbidden faulty sensor set that includes all the neighbors of a given sensor. We prove that k-covered WSNs can sustain a large number of sensor failures provided that the faulty sensor set does not include a forbidden faulty sensor set.
---
paper_title: Highly connected random geometric graphs

paper_content:

Let P be a Poisson process of intensity 1 in a square S"n of area n. We construct a random geometric graph G"n","k by joining each point of P to its k nearest neighbours. For many applications it is desirable that G"n","k is highly connected, that is, it remains connected even after the removal of a small number of its vertices. In this paper we relate the study of the s-connectivity of G"n","k to our previous work on the connectivity of G"n","k. Roughly speaking, we show that for s=o(logn), the threshold (in k) for s-connectivity is asymptotically the same as that for connectivity, so that, as we increase k, G"n","k becomes s-connected very shortly after it becomes connected.
---
paper_title: Connectivity properties of a random radio network

paper_content:

Pure and routing-algorithm-based connectivities of random radio networks are studied by theoretical analyses and computer simulation respectively. The 'magic number' of average neighbours of each station from connectivity point of view is obtained.
---
paper_title: Error and attack tolerance of complex networks

paper_content:

Many complex systems display a surprising degree of tolerance against errors. For example, relatively simple organisms grow, persist and reproduce despite drastic pharmaceutical or environmental interventions, an error tolerance attributed to the robustness of the underlying metabolic network1. Complex communication networks2 display a surprising degree of robustness: although key components regularly malfunction, local failures rarely lead to the loss of the global information-carrying ability of the network. The stability of these and other complex systems is often attributed to the redundant wiring of the functional web defined by the systems' components. Here we demonstrate that error tolerance is not shared by all redundant systems: it is displayed only by a class of inhomogeneously wired networks, called scale-free networks, which include the World-Wide Web3,4,5, the Internet6, social networks7 and cells8. We find that such networks display an unexpected degree of robustness, the ability of their nodes to communicate being unaffected even by unrealistically high failure rates. However, error tolerance comes at a high price in that these networks are extremely vulnerable to attacks (that is, to the selection and removal of a few nodes that play a vital role in maintaining the network's connectivity). Such error tolerance and attack vulnerability are generic properties of communication networks.
---
paper_title: Connectivity of the mutual k-nearest-neighbor graph in clustering and outlier detection

paper_content:

For multivariate data sets, we study the relationship between the connectivity of a mutual k-nearest-neighbor graph, and the presence of clustering structure and outliers in the data. A test for detection of clustering structure and outliers is proposed and its performance is evaluated in simulated data.
---
paper_title: Error and Attack Tolerance of Complex Networks

paper_content:

Communication/transportation systems are often subjected to failures and attacks. Here we represent such systems as networks and we study their ability to resist failures (attacks) simulated as the breakdown of a group of nodes of the network chosen at random (chosen accordingly to degree or load). We consider and compare the results for two different network topologies: the Erdos–Renyi random graph and the Barabasi–Albert scale-free network. We also discuss briefly a dynamical model recently proposed to take into account the dynamical redistribution of loads after the initial damage of a single node of the network.
---
paper_title: Network robustness and fragility: percolation on random graphs.

paper_content:

Recent work on the Internet, social networks, and the power grid has addressed the resilience of these networks to either random or targeted deletion of network nodes or links. Such deletions include, for example, the failure of Internet routers or power transmission lines. Percolation models on random graphs provide a simple representation of this process but have typically been limited to graphs with Poisson degree distribution at their vertices. Such graphs are quite unlike real-world networks, which often possess power-law or other highly skewed degree distributions. In this paper we study percolation on graphs with completely general degree distribution, giving exact solutions for a variety of cases, including site percolation, bond percolation, and models in which occupation probabilities depend on vertex degree. We discuss the application of our theory to the understanding of network resilience.
---
paper_title: Critical Sensor Density for Partial Connectivity in Large Area Wireless Sensor Networks

paper_content:

Assume sensor deployment follows the Poisson distribution. For a given partial connectivity requirement ρ, 0.5 < ρ < 1, we prove, for a hexagon model, that there exists a critical sensor density λ0, around which the probability that at least 100ρ% of sensors are connected in the network increases sharply from ε to 1-ε within a short interval of sensor density ρ. The location of ρ0 is at the sensor density where the above probability is about 1/2. We also extend the results to the disk model. Simulations are conducted to confirm the theoretical results.
---
paper_title: A Novel Topology Control Approach to Maintain the Node Degree in Dynamic Wireless Sensor Networks

paper_content:

Topology control is an important technique to improve the connectivity and the reliability of Wireless Sensor Networks (WSNs) by means of adjusting the communication range of wireless sensor nodes. In this paper, a novel Fuzzy-logic Topology Control (FTC) is proposed to achieve any desired average node degree by adaptively changing communication range, thus improving the network connectivity, which is the main target of FTC. FTC is a fully localized control algorithm, and does not rely on location information of neighbors. Instead of designing membership functions and if-then rules for fuzzy-logic controller, FTC is constructed from the training data set to facilitate the design process. FTC is proved to be accurate, stable and has short settling time. In order to compare it with other representative localized algorithms (NONE, FLSS, k-Neighbor and LTRT), FTC is evaluated through extensive simulations. The simulation results show that: firstly, similar to k-Neighbor algorithm, FTC is the best to achieve the desired average node degree as node density varies; secondly, FTC is comparable to FLSS and k-Neighbor in terms of energy-efficiency, but is better than LTRT and NONE; thirdly, FTC has the lowest average maximum communication range than other algorithms, which indicates that the most energy-consuming node in the network consumes the lowest power.
---
paper_title: Impact of random failures and attacks on Poisson and power-law random networks

paper_content:

It appeared recently that the underlying degree distribution of networks may play a crucial role concerning their robustness. Empiric and analytic results have been obtained, based on asymptotic and mean-field approximations. Previous work insisted on the fact that power-law degree distributions induce high resilience to random failure but high sensitivity to attack strategies, while Poisson degree distributions are quite sensitive in both cases. Then, much work has been done to extend these results. ::: We aim here at studying in depth these results, their origin, and limitations. We review in detail previous contributions and give full proofs in a unified framework, and identify the approximations on which these results rely. We then present new results aimed at enlightening some important aspects. We also provide extensive rigorous experiments which help evaluate the relevance of the analytic results. ::: We reach the conclusion that, even if the basic results of the field are clearly true and important, they are in practice much less striking than generally thought. The differences between random failures and attacks are not so huge and can be explained with simple facts. Likewise, the differences in the behaviors induced by power-law and Poisson distributions are not as striking as often claimed.
---
paper_title: The Japan earthquake: the impact on traffic and routing observed by a local ISP

paper_content:

The Great East Japan Earthquake and Tsunami on March 11, 2011, disrupted a significant part of communications infrastructures both within the country and in connectivity to the rest of the world. Nonetheless, many users, especially in the Tokyo area, reported experiences that voice networks did not work yet the Internet did. At a macro level, the Internet was impressively resilient to the disaster, aside from the areas directly hit by the quake and ensuing tsunami. However, little is known about how the Internet was running during this period. We investigate the impact of the disaster to one major Japanese Internet Service Provider (ISP) by looking at measurements of traffic volumes and routing data from within the ISP, as well as routing data from an external neighbor ISP. Although we can clearly see circuit failures and subsequent repairs within the ISP, surprisingly little disruption was observed from outside.
---
paper_title: Localized and Energy-Efficient Topology Control in Wireless Sensor Networks Using Fuzzy-Logic Control Approaches

paper_content:

The sensor nodes in the Wireless Sensor Networks (WSNs) are prone to failures due to many reasons, for example, running out of battery or harsh environment deployment; therefore, the WSNs are expected to be able to maintain network connectivity and tolerate certain amount of node failures. By applying fuzzy-logic approach to control the network topology, this paper aims at improving the network connectivity and fault-tolerant capability in response to node failures, while taking into account that the control approach has to be localized and energy efficient. Two fuzzy controllers are proposed in this paper: one is Learning-based Fuzzy-logic Topology Control (LFTC), of which the fuzzy controller is learnt from a training data set; another one is Rules-based Fuzzy-logic Topology Control (RFTC), of which the fuzzy controller is obtained through designing if-then rules and membership functions. Both LFTC and RFTC do not rely on location information, and they are localized. Comparing them with other three representative algorithms (LTRT, List-based, and NONE) through extensive simulations, our two proposed fuzzy controllers have been proved to be very energy efficient to achieve desired node degree and improve the network connectivity when sensor nodes run out of battery or are subject to random attacks.
---
paper_title: The Number of Neighbors Needed for Connectivity of Wireless Networks

paper_content:

Unlike wired networks, wireless networks do not come with links. Rather, links have to be fashioned out of the ether by nodes choosing neighbors to connect to. Moreover the location of the nodes may be random.The question that we resolve is: How many neighbors should each node be connected to in order that the overall network is connected in a multi-hop fashion? We show that in a network with n randomly placed nodes, each node should be connected to Θ(log n) nearest neighbors. If each node is connected to less than 0.074 log n nearest neighbors then the network is asymptotically disconnected with probability one as n increases, while if each node is connected to more than 5.1774 log n nearest neighbors then the network is asymptotically connected with probability approaching one as n increases. It appears that the critical constant may be close to one, but that remains an open problem.These results should be contrasted with some works in the 1970s and 1980s which suggested that the "magic number" of nearest neighbors should be six or eight.
---
paper_title: Deploying wireless sensors to achieve both coverage and connectivity

paper_content:

It is well-known that placing disks in the triangular lattice pattern is optimal for achieving full coverage on a plane. With the emergence of wireless sensor networks, however, it is now no longer enough to consider coverage alone when deploying a wireless sensor network; connectivity must also be con-sidered. While moderate loss in coverage can be tolerated by applications of wireless sensor networks, loss in connectivity can be fatal. Moreover, since sensors are subject to unanticipated failures after deployment, it is not enough to have a wireless sensor network just connected, it should be k-connected (for k > 1 ). In this paper, we propose an optimal deployment pattern to achieve both full coverage and 2-connectivity, and prove its optimality for all values of rc/rs, where rc is the communication radius, and rs is the sensing radius. We also prove the optimality of a previously proposed deployment pattern for achieving both full coverage and 1-connectivity, when rc/rs < √3 .Finally, we compare the efficiency of some popular regular deployment patterns such as the square grid and triangular lattice, in terms of the number of sensors needed to provide coverage and connectivity.
---
paper_title: Deploying sensor networks with guaranteed capacity and fault tolerance

paper_content:

We consider the problem of deploying or repairing a sensor network to guarantee a specified level of multi-path connectivity (k-connectivity) between all nodes. Such a guarantee simultaneously provides fault tolerance against node failures and high capacity through multi-path routing. We design and analyze the first algorithms that place an almost-minimum number of additional sensors to augment an existing network into a k-connected network, for any desired parameter k. Our algorithms have provable guarantees on the quality of the solution. Specifically, we prove that the number of additional sensors is within a constant factor of the absolute minimum, for any fixed k. We have implemented greedy and distributed versions of this algorithm, and demonstrate in simulation that they produce high-quality placements for the additional sensors. We are also in the process of using our algorithms to deploy nodes in a physical sensor network using a mobile robot.
---
paper_title: Integrated coverage and connectivity configuration in wireless sensor networks

paper_content:

An effective approach for energy conservation in wireless sensor networks is scheduling sleep intervals for extraneous nodes, while the remaining nodes stay active to provide continuous service. For the sensor network to operate successfully, the active nodes must maintain both sensing coverage and network connectivity. Furthermore, the network must be able to configure itself to any feasible degrees of coverage and connectivity in order to support different applications and environments with diverse requirements. This paper presents the design and analysis of novel protocols that can dynamically configure a network to achieve guaranteed degrees of coverage and connectivity. This work differs from existing connectivity or coverage maintenance protocols in several key ways: 1) We present a Coverage Configuration Protocol (CCP) that can provide different degrees of coverage requested by applications. This flexibility allows the network to self-configure for a wide range of applications and (possibly dynamic) environments. 2) We provide a geometric analysis of the relationship between coverage and connectivity. This analysis yields key insights for treating coverage and connectivity in a unified framework: this is in sharp contrast to several existing approaches that address the two problems in isolation. 3) Finally, we integrate CCP with SPAN to provide both coverage and connectivity guarantees. We demonstrate the capability of our protocols to provide guaranteed coverage and connectivity configurations, through both geometric analysis and extensive simulations.
---
paper_title: Strong minimum energy topology in wireless sensor networks: NPcompleteness and heuristics

paper_content:

Wireless sensor networks have recently attracted lots of research effort due to the wide range of applications. These networks must operate for months or years. However, the sensors are powered by battery, which may not be able to be recharged after they are deployed. Thus, energy-aware network management is extremely important. In this paper, we study the following problem: Given a set of sensors in the plane, assign transmit power to each sensor such that the induced topology containing only bidirectional links is strongly connected. This problem is significant in both theory and application. We prove its NP-completeness and propose two heuristics: power assignment based on minimum spanning tree (denoted by MST) and incremental power. We also show that the MST heuristic has a performance ratio of 2. Simulation study indicates that the performance of these two heuristics does not differ very much, but; on average, the incremental power heuristic is always better than MST.
---
paper_title: A Topology Reorganization Scheme for Reliable Communication in Underwater Wireless Sensor Networks Affected by Shadow Zones

paper_content:

Effective solutions should be devised to handle the effects of shadow zones in Underwater Wireless Sensor Networks (UWSNs). An adaptive topology reorganization scheme that maintains connectivity in multi-hop UWSNs affected by shadow zones has been developed in the context of two Spanish-funded research projects. A mathematical model has been proposed to find the optimal location for sensors with two objectives: the minimization of the transmission loss and the maintenance of network connectivity. The theoretical analysis and the numerical evaluations reveal that our scheme reduces the transmission loss under all propagation phenomena scenarios for all water depths in UWSNs and improves the signal-to-noise ratio.
---
paper_title: A fast distributed approximation algorithm for minimum spanning trees

paper_content:

We give a distributed algorithm that constructs a O(logn)- approximate minimum spanning tree (MST) in arbitrary networks. Our algorithm runs in time $\tilde{O}(D(G) + L(G,w))$ where L(G,w) is a parameter called the local shortest path diameter and D(G) is the (unweighted) diameter of the graph. Our algorithm is existentially optimal (up to polylogarithmic factors), i.e., there exists graphs which need Ω(D(G)+ L(G,w)) time to compute an H-approximation to the MST for any H ∈[1, Θ(logn)]. Our result also shows that there can be a significant time gap between exact and approximate MST computation: there exists graphs in which the running time of our approximation algorithm is exponentially faster than the time-optimal distributed algorithm that computes the MST. Finally, we show that our algorithm can be used to find an approximate MST in wireless networks and in random weighted networks in almost optimal $\tilde{O}(D(G))$ time.
---
paper_title: Fault tolerance measures for large-scale wireless sensor networks

paper_content:

Connectivity, primarily a graph-theoretic concept, helps define the fault tolerance of wireless sensor networks (WSNs) in the sense that it enables the sensors to communicate with each other so their sensed data can reach the sink. On the other hand, sensing coverage, an intrinsic architectural feature of WSNs plays an important role in meeting application-specific requirements, for example, to reliably extract relevant data about a sensed field. Sensing coverage and network connectivity are not quite orthogonal concepts. In fact, it has been proven that connectivity strongly depends on coverage and hence considerable attention has been paid to establish tighter connection between them although only loose lower bound on network connectivity of WSNs is known. In this article, we investigate connectivity based on the degree of sensing coverage by studying k-covered WSNs, where every location in the field is simultaneously covered (or sensed) by at least k sensors (property known as k-coverage, where k is the degree of coverage). We observe that to derive network connectivity of k-covered WSNs, it is necessary to compute the sensor spatial density required to guarantee k-coverage. More precisely, we propose to use a model, called the Reuleaux Triangle, to characterize k-coverage with the help of Helly's Theorem and the analysis of the intersection of sensing disks of k sensors. Using a deterministic approach, we show that the sensor spatial density to guarantee k-coverage of a convex field is proportional to k and inversely proportional to the sensing range of the sensors. We also prove that network connectivity of k-covered WSNs is higher than their sensing coverage k. Furthermore, we propose a new measure of fault tolerance for k-covered WSNs, called conditional fault tolerance, based on the concepts of conditional connectivity and forbidden faulty sensor set that includes all the neighbors of a given sensor. We prove that k-covered WSNs can sustain a large number of sensor failures provided that the faulty sensor set does not include a forbidden faulty sensor set.
---
paper_title: Optimal Sensor Location Design for Reliable Fault Detection in Presence of False Alarms

paper_content:

To improve fault detection reliability, sensor location should be designed according to an optimization criterion with constraints imposed by issues of detectability and identifiability. Reliability requires the minimization of undetectability and false alarm probability due to random factors on sensor readings, which is not only related with sensor readings but also affected by fault propagation. This paper introduces the reliability criteria expression based on the missed/false alarm probability of each sensor and system topology or connectivity derived from the directed graph. The algorithm for the optimization problem is presented as a heuristic procedure. Finally, a boiler system is illustrated using the proposed method.
---
paper_title: Efficient fault—tolerant routings in networks

paper_content:

Abstract We analyze the problem of constructing a network with a given number of nodes which has a fixed routing and which is highly fault tolerant. A construction is presented which forms a “product route graph” from two or more constituent “route graphs.” The analysis involves the surviving route graph , which consists of all nonfaulty nodes in the network with two nodes being connected by a directed edge iff the route from the first to the second is still intact after a set of component failures. The diameter of the surviving route graph is a measure of the worst-case performance degradation caused by the faults. The number of faults tolerated, the diameter, and the degree of the product graph are related in a simple way to the corresponding parameters of the constituent graphs. In addition, there is a “padding theorem” which allows one to add nodes to a graph and to extend a previous routing.
---
paper_title: Biconnectivity approximations and graph carvings

paper_content:

A spanning tree in a graph is the smallest connected spanning subgraph. Given a graph, how does one find the smallest (i.e., least number of edges) 2-connected spanning subgraph (connectivity refers to both edge and vertex connectivity, if not specified)? Unfortunately, the problem is known to be NP -hard. We consider the problem of finding an approximation to the smallest 2-connected subgraph, by an efficient algorithm. For 2-edge connectivity our algorithm guarantees a solution that is no more than 3/2 times the optimal. For 2-vertex connectivity our algorithm guarantees a solution that is no more than 5/3 times the optimal. The previous best approximation factor is 2 for each of these problems. The new algorithms (and their analyses) depend upon a structure called a carving of a graph, which is of independent interest. We show that approximating the optimal solution to within an additive constant is NP -hard as well. We also consider the case where the graph has edge weights. We show that an approximation factor of 2 is possible in polynomial time for finding a k -edge connected spanning subgraph. This improves an approximation factor of 3 for k =2 due to [FJ81], and extends it for any k (with an increased running time though).
---
paper_title: A randomized linear-time algorithm to find minimum spanning trees

paper_content:

We present a randomized linear-time algorithm to find a minimum spanning tree in a connected graph with edge weights. The algorithm uses random sampling in combination with a recently discovered linear-time algorithm for verifying a minimum spanning tree. Our computational model is a unit-cost random-access machine with the restriction that the only operations allowed on edge weights are binary comparisons.
---
paper_title: Relay Placement for Higher Order Connectivity in Wireless Sensor Networks

paper_content:

Sensors typically use wireless transmitters to communicate with each other. However, sensors may be located in a way that they cannot even form a connected network (e.g, due to failures of some sensors, or loss of battery power). In this paper we consider the problem of adding the smallest number of additional (relay) nodes so that the induced communication graph is 2-connected. The problem is NP -hard. In this paper we develop O(1)-approximation algorithms that find close to optimal solutions in time O((kn)) for achieving k-edge connectivity of n nodes. The worst case approximation guarantee is 10, but the algorithm produces solutions that are far better than this bound suggests. We also consider extensions to higher dimensions, and the scheme that we develop for points in the plane, yields a bound of 2dMST where dMST is the maximum degree of a minimum-degree Minimum Spanning Tree in d dimensions using Euclidean metrics. In addition, our methods extend with the same approximation guarantees to a generalization when the locations of relays are required to avoid certain polygonal regions (obstacles). We also prove that if the sensors are uniformly and identically distributed in a unit square, the expected number of relay nodes required goes to zero as the number of sensors goes to infinity.
---
paper_title: Complete optimal deployment patterns for full-coverage and k-connectivity (k≤6) wireless sensor networks

paper_content:

In this paper, we propose deployment patterns to achieve full coverage and three-connectivity, and full coverage and five-connectivity under different ratios of sensor communication range (denoted by Rc) over sensing range (denoted by Rs) for wireless sensor networks (WSNs). We also discover that there exists a hexagon-based universally elemental pattern which can generate all known optimal patterns. The previously proposed Voronoi-based approach can not be applied to prove the optimality of the new patterns due to their special features. We propose a new deployment-polygon based methodology, and prove their optimality among regular patterns when Rc/Rs ≥ 1. We conjecture that our patterns are globally optimal to achieve full coverage and three-connectivity, and full coverage and five-connectivity, under all ranges of Rc/Rs. With these new results, the set of optimal patterns to achieve full coverage and k-connectivity (k≤6) is complete, for the first time.
---
paper_title: A reliable node-disjoint multipath routing with low overhead in wireless ad hoc networks

paper_content:

Wireless ad hoc networks are characterized by the use of wireless links with limited bandwidth, dynamically varying network topology and multi-hop connectivity. AODV and DSR are the two most widely studied on-demand ad hoc routing protocols. Previous work has shown some limitations of the two protocols: whenever there is a link break on the active route, each of the two routing protocols has to invoke a route discovery process. This leads to increase in both delay and control overhead as well as decrease in packet delivery ratio. To alleviate these problems, we modify and extend AODV to include the path accumulation feature of DSR in route request/reply packets so that much lower route overhead is employed to discover multiple node-disjoint routing paths. The extended AODV is called Reliable Node-Disjoint Multipath Routing Protocol (NDMR), which has two novel aspects compared to the other on-demand multipath protocols: it reduces routing overhead dramatically and achieves multiple node-disjoint routing paths. Simulation results show that performance of NDMR is much better than that of AODV and DSR.
---
paper_title: Resilience is more than availability

paper_content:

In applied sciences there is a tendency to rely on terminology that is either ill-defined or applied inconsistently across areas of research and application domains. Examples in information assurance include the terms resilience, robustness and survivability, where there exists subtle shades of meaning between researchers. These nuances can result in confusion and misinterpretations of goals and results, hampering communication and complicating collaboration. In this paper, we propose security-related definitions for these terms. Using this terminology, we argue that research in these areas must consider the functionality of the system holistically, beginning with a careful examination of what we actually want the system to do. We note that much of the published research focuses on a single aspect of a system -- availability -- as opposed to the system's ability to complete its function without disclosing confidential information or, to a lesser extent, with the correct output. Finally, we discuss ways in which researchers can explore resilience with respect to integrity, availability and confidentiality.
---
paper_title: Random coverage with guaranteed connectivity: joint scheduling for wireless sensor networks

paper_content:

Sensor scheduling plays a critical role for energy efficiency of wireless sensor networks. Traditional methods for sensor scheduling use either sensing coverage or network connectivity, but rarely both. In this paper, we deal with a challenging task: without accurate location information, how do we schedule sensor nodes to save energy and meet both constraints of sensing coverage and network connectivity? Our approach utilizes an integrated method that provides statistical sensing coverage and guaranteed network connectivity. We use random scheduling for sensing coverage and then turn on extra sensor nodes, if necessary, for network connectivity. Our method is totally distributed, is able to dynamically adjust sensing coverage with guaranteed network connectivity, and is resilient to time asynchrony. We present analytical results to disclose the relationship among node density, scheduling parameters, coverage quality, detection probability, and detection delay. Analytical and simulation results demonstrate the effectiveness of our joint scheduling method
---
paper_title: On k-coverage in a mostly sleeping sensor network

paper_content:

Sensor networks are often desired to last many times longer than the active lifetime of individual sensors. This is usually achieved by putting sensors to sleep for most of their lifetime. On the other hand, event monitoring applications require guaranteed k-coverage of the protected region at all times. As a result, determining the appropriate number of sensors to deploy that achieves both goals simultaneously becomes a challenging problem. In this paper, we consider three kinds of deployments for a sensor network on a unit square--a √n × √n grid, random uniform (for all n points), and Poisson (with density n). In all three deployments, each sensor is active with probability p, independently from the others. Then, we claim that the critical value of the function npπ r2/ log(np) is 1 for the event of k-coverage of every point. We also provide an upper bound on the window of this phase transition. Although the conditions for the three deployments are similar, we obtain sharper bounds for the random deployments than the grid deployment, which occurs due to the boundary condition. In this paper, we also provide corrections to previously published results. Finally, we use simulation to show the usefulness of our analysis in real deployment scenarios.
---
paper_title: CLTC: a cluster-based topology control for ad hoc networks

paper_content:

The topology of an ad hoc network has a significant impact on its performance in that a dense topology may induce high interference and low capacity, while a sparse topology is vulnerable to link failure and network partitioning. Topology control aims to maintain a topology that optimizes network performance while minimizing energy consumption. Existing topology control algorithms utilize either a purely centralized or a purely distributed approach. A centralized approach, although able to achieve strong connectivity (k-connectivity for k /spl ges/ 2), suffers from scalability problems. In contrast, a distributed approach, although scalable, lacks strong connectivity guarantees. We propose a hybrid topology control framework, cluster-based topology control (CLTC) that achieves both scalability and strong connectivity. By varying the algorithms utilized in each of the three phases of the framework, a variety of optimization objectives and topological properties can be achieved. In this paper, we present the CLTC framework; describe topology control algorithms based on CLTC and prove that k-connectivity is achieved using those algorithms; analyze the message complexity of an implementation of CLTC, namely, CLTC-A, and present simulation studies that evaluate the effectiveness of CLTC-A for a range of networks.
---
paper_title: Topology Control for Fault-Tolerant Communication in Wireless Ad Hoc Networks ∗

paper_content:

Fault-tolerant communication and energy efficiency are important requirements for future-generation wireless ad hoc networks, which are increasingly being considered also for critical application domains like embedded systems in automotive and aerospace. Topology control, which enables multi-hop communication between any two network nodes via a suitably constructed overlay network, is the primary target for increasing connectivity and saving energy here. In this paper, we present a fault-tolerant distributed topology control algorithm that constructs and continuously maintains a k-regular and k-node-connected overlay for energy-efficient multi-hop communication. As a by-product, it also builds a hierarchy of clusters that reflects the node density in the network, with guaranteed and localized fault-tolerant communication between any pair of cluster members. The construction algorithm automatically adapts to a dynamically changing environment, is guaranteed to converge, and exhibits good performance as well.
---
paper_title: Low-Energy Fault-Tolerant Bounded-Hop Broadcast in Wireless Networks

paper_content:

This paper studies asymmetric power assignments in wireless ad hoc networks. The temporary, unfixed physical topology of wireless ad hoc networks is determined by the distribution of the wireless nodes as well as the transmission power (range) assignment of each node. We consider the problem of bounded-hop broadcast under k-fault resilience criterion for linear and planar layout of nodes. The topology that results from our power assignment allows a broadcast operation from a wireless node r to any other node in at most h hops and is k -fault resistant. We develop simple approximation algorithms for the two cases and obtain the following approximation ratios: linear case-O(k); planar case-we first prove a factor of O(k 3) , which is later decreased to O(k 2) by a finer analysis. Finally, we show a trivial power assignment with a cost O(h) times the optimum. To the best of our knowledge, these are the first nontrivial results for this problem.
---
paper_title: Span: an energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks

paper_content:

This paper presents Span, a power saving technique for multi-hop ad hoc wireless networks that reduces energy consumption without significantly diminishing the capacity or connectivity of the network. Span builds on the observation that when a region of a sharedchannel wireless network has a sufficient density of nodes, only a small number of them need be on at any time to forward traffic for active connections. Span is a distributed, randomized algorithm where nodes make local decisions on whether to sleep, or to join a forwarding backbone as a coordinator. Each node bases its decision on an estimate of how many of its neighbors will benefit from it being awake, and the amount of energy available to it. We give a randomized algorithm where coordinators rotate with time, demonstrating how localized node decisions lead to a connected, capacity-preserving global topology. Improvement in system lifetime due to Span increases as the ratio of idle-to-sleep energy consumption increases. Our simulations show that with a practical energy model, system lifetime of an 802.11 network in power saving mode with Span is a factor of two better than without. Additionally, Span also improves communication latency and capacity.
---
paper_title: Fault-tolerant and 3-dimensional distributed topology control algorithms in wireless multi-hop networks

paper_content:

We can control the topology of a multi-hop wireless network by varying the transmission power at each node. The life-time of such networks depends on battery power at each node. This paper presents a distributed fault-tolerant topology control algorithm for minimum energy consumption in these networks. More precisely, we present algorithms which preserve the connectivity of a network upon failing of, at most, k nodes (k is constant) and simultaneously minimize the transmission power at each node to some extent. In addition, we present simulations to support the effectiveness of our algorithm. We also demonstrate some optimizations to further minimize the power at each node. Finally, we show how our algorithms can be extended to 3-dimensions.
---
paper_title: Finding Minimum Energy Disjoint Paths in Wireless Ad-Hoc Networks

paper_content:

We develop algorithms for finding minimum energy disjoint paths in an all-wireless network, for both the node and link-disjoint cases. Our major results include a novel polynomial time algorithm that optimally solves the minimum energy 2 link-disjoint paths problem, as well as a polynomial time algorithm for the minimum energy k node-disjoint paths problem. In addition, we present efficient heuristic algorithms for both problems. Our results show that link-disjoint paths consume substantially less energy than node-disjoint paths. We also found that the incremental energy of additional link-disjoint paths is decreasing. This finding is some what surprising due to the fact that in general networks additional paths are typically longer than the shortest path. However, in a wireless network, additional paths can be obtained at lower energy due to the broadcast nature of the wireless medium. Finally, we discuss issues regarding distributed implementation and present distributed versions of the optimal centralized algorithms presented in the paper.
---
paper_title: On minimizing the total power of k-strongly connected wireless networks

paper_content:

Given a wireless network, we want to assign each node a transmission power, which will enable transmission between any two nodes (via other nodes). Moreover, due to possible faults, we want to have at least k vertex-disjoint paths from any node to any other, where k is some fixed integer, depending on the reliability of the nodes. The goal is to achieve this directed k-strong connectivity with a minimal overall power assignment. The problem is NP-Hard for any k ? 1 already for planar networks. Here we first present an optimal power assignment for uniformly spaced nodes on a line for any k ? 1. We also prove a number of useful properties of power assignment which are also of independent interest. Based on it, we design an approximation algorithm for linear radio networks with factor $$\hbox{min}\left\{2,\left(\frac {\Updelta} {\delta}\right)^\alpha \right\},$$ where Δ and ? are the maximal and minimal distances between adjacent nodes respectively and parameter ? ? 1 being the distance-power gradient. We then extend it to the weighted version. Finally, we develop an approximation algorithm with factor O(k 2), for planar case, which is, to the best of our knowledge, the first non-trivial result for this problem.
---
paper_title: Highly-resilient, energy-efficient multipath routing in wireless sensor networks

paper_content:

Previously proposed sensor network data dissemination schemes require periodic low-rate flooding of data in order to allow recovery from failure. We consider constructing two kinds of multipaths to enable energy efficient recovery from failure of the shortest path between source and sink. Disjoint multipath has been studied in the literature. We propose a novel braided multipath scheme, which results in several partially disjoint multipath schemes. We find that braided multipaths are a viable alternative for energy-efficient recovery from isolated and patterned failures.
---
paper_title: Distributed fault-tolerant topology control in wireless multi-hop networks

paper_content:

In wireless multi-hop and ad-hoc networks, minimizing power consumption and at the same time maintaining desired properties of the network topology is of prime importance. In this work, we present a distributed algorithm for assigning minimum possible power to all the nodes in a static wireless network such that the resultant network topology is k-connected. In this algorithm, a node collects the location and maximum power information from all nodes in its vicinity, and then adjusts the power of these nodes in such a way that it can reach all of them through k optimal vertex-disjoint paths. The algorithm ensures k-connectivity in the final topology provided the topology induced when all nodes transmit with their maximum power is k-connected. We extend our topology control algorithm from static networks to networks having mobile nodes. We present proof of correctness for our algorithm for both static and mobile scenarios, and through extensive simulation we present its behavior.
---
paper_title: A survey of game-theoretic approaches in wireless sensor networks

paper_content:

Wireless sensor networks (WSNs) comprising of tiny, power-constrained nodes are gaining popularity due to their potential for use in a wide variety of environments like monitoring of environmental attributes, intrusion detection, and various military and civilian applications. While the sensing objectives of these environments are unique and application-dependent, a common performance criteria for wireless sensor networks is prolonging network lifetime while satisfying coverage and connectivity in the deployment region. Security is another important performance parameter in wireless sensor networks, where adverse and remote environments pose various kinds of threats to reliable network operation. In this paper, we look at the problems of security and energy efficiency and different formulations of these problems based on the approach of game theory. The potential applicability of WSNs to intruder detection environments also lends itself to game-theoretic formulation of these environments, where pursuit-evasion games provide a relevant framework to model detection, tracking and surveillance applications. The suitability of using game theory to study security and energy efficiency problems and pursuit-evasion scenarios using WSNs stems from the nature of strategic interactions between nodes. Approaches from game theory can be used to optimize node-level as well as network-wide performance by exploiting the distributed decision-making capabilities of WSNs. The use of game theory has proliferated, with a wide range of applications in wireless sensor networking. In the wake of this proliferation, we survey the use of game-theoretic approaches to formulate problems related to security and energy efficiency in wireless sensor networks.
---
paper_title: ATPC: adaptive transmission power control for wireless sensor networks

paper_content:

Extensive empirical studies presented in this paper confirm that the quality of radio communication between low power sensor devices varies significantly with time and environment. This phenomenon indicates that the previous topology control solutions, which use static transmission power, transmission range, and link quality, might not be effective in the physical world. To address this issue, online transmission power control that adapts to external changes is necessary. This paper presents ATPC, a lightweight algorithm of Adaptive Transmission Power Control for wireless sensor networks. In ATPC, each node builds a model for each of its neighbors, describing the correlation between transmission power and link quality. With this model, we employ a feedback-based transmission power control algorithm to dynamically maintain individual link quality over time. The intellectual contribution of this work lies in a novel pairwise transmission power control, which is significantly different from existing node-level or network-level power control methods. Also different from most existing simulation work, the ATPC design is guided by extensive field experiments of link quality dynamics at various locations and over a long period of time. The results from the real-world experiments demonstrate that 1) with pairwise adjustment, ATPC achieves more energy savings with a finer tuning capability and 2) with online control, ATPC is robust even with environmental changes over time.
---
paper_title: Transmission Power Control in Body Area Sensor Networks for Healthcare Monitoring

paper_content:

This paper investigates the opportunities and challenges in the use of dynamic radio transmit power control for prolonging the lifetime of body-wearable sensor devices used in continuous health monitoring. We first present extensive empirical evidence that the wireless link quality can change rapidly in body area networks, and a fixed transmit power results in either wasted energy (when the link is good) or low reliability (when the link is bad). We quantify the potential gains of dynamic power control in body-worn devices by benchmarking off-line the energy savings achievable for a given level of reliability.We then propose a class of schemes feasible for practical implementation that adapt transmit power in real-time based on feedback information from the receiver. We profile their performance against the offline benchmark, and provide guidelines on how the parameters can be tuned to achieve the desired trade-off between energy savings and reliability within the chosen operating environment. Finally, we implement and profile our scheme on a MicaZ mote based platform, and also report preliminary results from the ultra-low-power integrated healthcare monitoring platform we are developing at Toumaz Technology.
---
paper_title: Localized and Configurable Topology Control in Lossy Wireless Sensor Networks

paper_content:

Wireless sensor networks (WSNs) introduce new challenges to topology control due to the prevalence of lossy links. We propose a new topology control formulation for lossy WSNs that captures the stochastic nature of lossy links and quantifies the worst-case path quality in a network. We develop a novel localized scheme called Configurable Topology Control (CTC). The key feature of CTC is its capability of flexibly configuring the topology of a lossy WSN to achieve desired path quality bounds in a localized fashion. Furthermore, CTC can incorporate different control strategies (per-node/per-link) and optimization criteria. Simulations using a realistic radio model of Mica2 motes show that CTC significantly outperforms a representative traditional topology control algorithm called LMST in terms of both communication performance and energy efficiency. Our results demonstrate the importance of incorporating lossy links of WSNs in the design of topology control algorithms.
---
paper_title: Practical control of transmission power for Wireless Sensor Networks

paper_content:

Transmission power control (TPC) has the potential to reduce power consumption in Wireless Sensor Networks (WSNs). However, despite a multitude of existing protocols, they still face significant challenges in real-world deployments. A practical TPC protocol must be robust against complex and dynamic wireless properties, and efficient for resource-constrained sensors. This paper presents P-TPC, a practical TPC protocol designed on control-theoretic techniques. P-TPC features a highly efficient controller designed on a dynamic model that combines a theoretical link model with online parameter estimation. P-TPC's robustness and energy savings are demonstrated through trace-driven simulations and real-world experiments in a campus building and residential environments.
---
paper_title: Robust topology control for indoor wireless sensor networks

paper_content:

Topology control can reduce power consumption and channel contention in wireless sensor networks by adjusting the transmission power. However, topology control for wireless sensor networks faces significant challenges, especially in indoor environments where wireless characteristics are extremely complex and dynamic. We first provide insights on the design of robust topology control schemes based on an empirical study in an office building. For example, our analysis shows that Received Signal Strength Indicator and Link Quality Indicator are not always robust indicators of Packet Reception Rate in indoor environments due to significant multi-path effects. We then present Adaptive and Robust Topology control (ART), a novel and practical topology control algorithm with several salient features: (1) ART is robust in indoor environments as it does not rely on simplifying assumptions about the wireless properties; (2) ART can adapt to variations in both link quality and contention; (3) ART introduces zero communication overhead for applications which already use acknowledgements. We have implemented ART as a topology layer in TinyOS 2.x. Our topology layer only adds 12 bytes of RAM per neighbor and 1.5 kilobytes of ROM, and requires minimal changes to upper-layer routing protocols. The advantages of ART have been demonstrated through empirical results on a 28-node indoor testbed.
---
paper_title: Deploying sensor networks with guaranteed capacity and fault tolerance

paper_content:

We consider the problem of deploying or repairing a sensor network to guarantee a specified level of multi-path connectivity (k-connectivity) between all nodes. Such a guarantee simultaneously provides fault tolerance against node failures and high capacity through multi-path routing. We design and analyze the first algorithms that place an almost-minimum number of additional sensors to augment an existing network into a k-connected network, for any desired parameter k. Our algorithms have provable guarantees on the quality of the solution. Specifically, we prove that the number of additional sensors is within a constant factor of the absolute minimum, for any fixed k. We have implemented greedy and distributed versions of this algorithm, and demonstrate in simulation that they produce high-quality placements for the additional sensors. We are also in the process of using our algorithms to deploy nodes in a physical sensor network using a mobile robot.
---
paper_title: Integrated coverage and connectivity configuration in wireless sensor networks

paper_content:

An effective approach for energy conservation in wireless sensor networks is scheduling sleep intervals for extraneous nodes, while the remaining nodes stay active to provide continuous service. For the sensor network to operate successfully, the active nodes must maintain both sensing coverage and network connectivity. Furthermore, the network must be able to configure itself to any feasible degrees of coverage and connectivity in order to support different applications and environments with diverse requirements. This paper presents the design and analysis of novel protocols that can dynamically configure a network to achieve guaranteed degrees of coverage and connectivity. This work differs from existing connectivity or coverage maintenance protocols in several key ways: 1) We present a Coverage Configuration Protocol (CCP) that can provide different degrees of coverage requested by applications. This flexibility allows the network to self-configure for a wide range of applications and (possibly dynamic) environments. 2) We provide a geometric analysis of the relationship between coverage and connectivity. This analysis yields key insights for treating coverage and connectivity in a unified framework: this is in sharp contrast to several existing approaches that address the two problems in isolation. 3) Finally, we integrate CCP with SPAN to provide both coverage and connectivity guarantees. We demonstrate the capability of our protocols to provide guaranteed coverage and connectivity configurations, through both geometric analysis and extensive simulations.
---
paper_title: Span: an energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks

paper_content:

This paper presents Span, a power saving technique for multi-hop ad hoc wireless networks that reduces energy consumption without significantly diminishing the capacity or connectivity of the network. Span builds on the observation that when a region of a sharedchannel wireless network has a sufficient density of nodes, only a small number of them need be on at any time to forward traffic for active connections. Span is a distributed, randomized algorithm where nodes make local decisions on whether to sleep, or to join a forwarding backbone as a coordinator. Each node bases its decision on an estimate of how many of its neighbors will benefit from it being awake, and the amount of energy available to it. We give a randomized algorithm where coordinators rotate with time, demonstrating how localized node decisions lead to a connected, capacity-preserving global topology. Improvement in system lifetime due to Span increases as the ratio of idle-to-sleep energy consumption increases. Our simulations show that with a practical energy model, system lifetime of an 802.11 network in power saving mode with Span is a factor of two better than without. Additionally, Span also improves communication latency and capacity.
---
paper_title: PEAS: a robust energy conserving protocol for long-lived sensor networks

paper_content:

Small, inexpensive sensors with limited memory, computing power and short battery lifetimes are turning into reality. Due to adverse conditions such as high noise levels, extreme humidity or temperatures, or even destructions from unfriendly entities, sensor node failures may become norms rather than exceptions in real environments. To be practical, sensor networks must last for much longer times than that of individual nodes, and have yet to be robust against potentially frequent node failures. This paper presents the design of PEAS, a simple protocol that can build a long-lived sensor network and maintain robust operations using large quantities of economical, short-lived sensor nodes. PEAS extends system functioning time by keeping only a necessary set of sensors working and putting the rest into sleep mode. Sleeping ones wake up now and then, probing the local environment and replacing failed ones. The sleeping periods are self-adjusted dynamically, so as to keep the sensors' wakeup rate roughly constant, thus adapting to high node densities.
---
paper_title: A new approach to the maximum flow problem

paper_content:

All previously known efftcient maximum-flow algorithms work by finding augmenting paths, either one path at a time (as in the original Ford and Fulkerson algorithm) or all shortest-length augmenting paths at once (using the layered network approach of Dinic). An alternative method based on the preflow concept of Karzanov is introduced. A preflow is like a flow, except that the total amount flowing into a vertex is allowed to exceed the total amount flowing out. The method maintains a preflow in the original network and pushes local flow excess toward the sink along what are estimated to be shortest paths. The algorithm and its analysis are simple and intuitive, yet the algorithm runs as fast as any other known method on dense. graphs, achieving an O(n)) time bound on an n-vertex graph. By incorporating the dynamic tree data structure of Sleator and Tarjan, we obtain a version of the algorithm running in O(nm log(n'/m)) time on an n-vertex, m-edge graph. This is as fast as any known method for any graph density and faster on graphs of moderate density. The algorithm also admits efticient distributed and parallel implementations. A parallel implementation running in O(n'log n) time using n processors and O(m) space is obtained. This time bound matches that of the Shiloach-Vishkin
---
paper_title: Survey: A survey on relay placement with runtime and approximation guarantees

paper_content:

We discuss aspects and variants of the fundamental problem of relay placement: given a set of immobile terminals in the Euclidean plane, place a number of relays with limited viewing range such that the result is a low-cost communication infrastructure between the terminals. We first consider the problem from a global point of view. The problem here is similar to forming discrete Steiner tree structures. Then we investigate local variants of the problem, assuming mobile relays that must decide where to move based only on information from their local environment. We give a local algorithm for the general problem, but we show that no local algorithm can achieve good approximation factors for the number of relays. The following two restricted variants each address different aspects of locality. First we provide each relay with knowledge of two fixed neighbors, such that the relays form a chain between two terminals. The goal here is to let the relays move to the line segment between the terminals as fast as possible. Then we focus on the aspect of neighbors that are not fixed, but which may change over time. In return, we relax the objective function from geometric structures to just forming a single point. The goal in all our local formation problems is to use relays that are as limited as possible with respect to memory, sensing capabilities and so on. We focus on algorithms for which we can prove performance guarantees such as upper bounds on the required runtime, maximum traveled distances of the relays and approximation factors for the solution.
---
paper_title: Strategies and Techniques for Node Placement in Wireless Sensor Networks : A Survey

paper_content:

The major challenge in designing wireless sensor networks (WSNs) is the support of the functional, such as data latency, and the non-functional, such as data integrity, requirements while coping with the computation, energy and communication constraints. Careful node placement can be a very effective optimization means for achieving the desired design goals. In this paper, we report on the current state of the research on optimized node placement in WSNs. We highlight the issues, identify the various objectives and enumerate the different models and formulations. We categorize the placement strategies into static and dynamic depending on whether the optimization is performed at the time of deployment or while the network is operational, respectively. We further classify the published techniques based on the role that the node plays in the network and the primary performance objective considered. The paper also highlights open problems in this area of research.
---
paper_title: Modelling and Solving Optimal Placement problems in Wireless Sensor Networks

paper_content:

In this work, the optimal sensor displacement problem in wireless sensor networks is addressed. It is assumed that a network, consisting of independent, collaborative and mobile nodes, is available. Starting from an initial configuration, the aim is to define a specific sensors displacement, which allows the network to achieve high performance, in terms of energy consumption and travelled distance. To mathematically represent the problem under study, different innovative optimization models are proposed and defined, by taking into account different performance objectives. An extensive computational phase is carried out in order to assess the behaviour of the developed models in terms of solution quality and computational effort. A comparison with distributed approaches is also given, by considering different scenarios.
---
paper_title: Design of fault tolerant wireless sensor networks satisfying survivability and lifetime requirements

paper_content:

Sensor networks are deployed to accomplish certain specific missions over a period of time. It is essential that the network continues to operate, even if some of its nodes fail. It is also important that the network is able to support the mission for a minimum specified period of time. Hence, the design of a sensor network should not only provide some guarantees that all data from the sensor nodes are gathered at the base station, even in the presence of some faults, but should also allow the network to remain functional for a specified duration. This paper considers a two-tier, hierarchical sensor network architecture, where some relay nodes, provisioned with higher power and other capabilities, are used as cluster heads. Given a distribution of sensor nodes in a sensor network, finding the locations to place a minimum number of relay nodes such that, each sensor node is covered by at least one relay node, is known to be a computationally difficult problem. In addition, for successful and reliable data communication, the relay nodes network needs to be connected, as well as resilient to node failures. In this paper, a novel integrated Integer Linear Program (ILP) formulation is proposed, which, unlike existing techniques, not only finds a suitable placement strategy for the relay nodes, but also assigns the sensor nodes to the clusters and determines a load-balanced routing scheme. Therefore, in addition to the desired levels of fault tolerance for both the sensor nodes and the relay nodes, the proposed approach also meets specified performance guarantees with respect to network lifetime by limiting the maximum energy consumption of the relay nodes.
---
paper_title: Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networks

paper_content:

In ad hoc wireless networks, it is crucial to minimize power consumption while maintaining key network properties. This work studies power assignments of wireless devices that minimize power while maintaining k-fault tolerance. Specifically, we require all links established by this power setting be symmetric and form a k-vertex connected subgraph of the network graph. This problem is known to be NP-hard. We show current heuristic approaches can use arbitrarily more power than the optimal solution. Hence, we seek approximation algorithms for this problem. We present three approximation algorithms. The first algorithm gives an O(kalpha)-approximation where is the best approximation factor for the related problem in wired networks (the best alpha so far is O(log k)). With a more careful analysis, we show our second (slightly more complicated) algorithm is an O(k)-approximation. Our third algorithm assumes that the edge lengths of the network graph form a metric. In this case, we present simple and practical distributed algorithms for the cases of 2- and 3-connectivity with constant approximation factors. We generalize this algorithm to obtain an O(k2c+2)-approximation for general k-connectivity (2 les c les 4 is the power attenuation exponent). Finally, we show that these approximation algorithms compare favorably with existing heuristics. We note that all algorithms presented in this paper can be used to minimize power while maintaining -edge connectivity with guaranteed approximation factors. Recently, different set of authors used the notion of k-connectivity and the results of this paper to deal with the fault-tolerance issues for static wireless network settings.
---
paper_title: IPSD: new coverage preserving and connectivity maintenance scheme for improving lifetime of wireless sensor networks

paper_content:

In many applications it is necessary to have some guarantees on the coverage, connectivity and lifetime of the Wireless Sensor Networks (WSN). Coverage problem is regarding how to ensure that each of the points in the region to be monitored is covered by the sensors. In maximizing coverage, the sensors need to be placed not too close to each other so that the sensing capability of the network is fully utilized and at the same time they must not be located too far from each other to avoid the formation of coverage holes. On the other hand from connectivity point of view, the sensors need to be placed close enough so that they are within each other communication range thus connectivity is ensured. Once coverage and connectivity are ensured, the overall lifetime of the network gets increased thereby improving the quality of service (QoS) of the Wireless Sensor Network (WSN). The concept of Integer Programmed Sensor Deployment (IPSD) scheme is being proposed, with a set of relay nodes a triangular lattice is formed by the grid based approach thus providing maximum coverage and connectivity. Integer Linear Programming (ILP) is brought into existence for eliminating the unused relay nodes thereby enhancing the coverage and connectivity with minimum number of relay nodes. Simulation is performed using NS-2 and the results shows that the proposed scheme provides better results in large scale WSN with improved coverage and connectivity.
---
paper_title: Steiner tree problem with minimum number of Steiner points and bounded edge-length

paper_content:

Abstract In this paper, we study the Steiner tree problem with minimum number of Steiner points and bounded edge-length (STPMSPBEL), which asks for a tree interconnecting a given set of n terminal points and a minimum number of Steiner points such that the Euclidean length of each edge is no more than a given positive constant. This problem has applications in VLSI design, WDM optimal networks and wireless communications. We prove that this problem is NP-complete and present a polynomial time approximation algorithm whose worst-case performance ratio is 5.
---
paper_title: An improved LP-based approximation for steiner tree

paper_content:

The Steiner tree problem is one of the most fundamental NP-hard problems: given a weighted undirected graph and a subset of terminal nodes, find a minimum-cost tree spanning the terminals. In a sequence of papers, the approximation ratio for this problem was improved from 2 to the current best 1.55 [Robins,Zelikovsky-SIDMA'05]. All these algorithms are purely combinatorial. A long-standing open problem is whether there is an LP-relaxation for Steiner tree with integrality gap smaller than 2 [Vazirani,Rajagopalan-SODA'99]. In this paper we improve the approximation factor for Steiner tree, developing an LP-based approximation algorithm. Our algorithm is based on a, seemingly novel, iterative randomized rounding technique. We consider a directed-component cut relaxation for the k-restricted Steiner tree problem. We sample one of these components with probability proportional to the value of the associated variable in the optimal fractional solution and contract it. We iterate this process for a proper number of times and finally output the sampled components together with a minimum-cost terminal spanning tree in the remaining graph. Our algorithm delivers a solution of cost at most ln(4) times the cost of an optimal k-restricted Steiner tree. This directly implies a ln(4)+e
---
paper_title: An effective approach for tolerating simultaneous failures in wireless sensor and actor networks

paper_content:

Wireless Sensor and Actor Networks (WSANs) engage mobile nodes with actuators to respond to certain events in inhospitable environments. The harsh surroundings make actors susceptible to failure. Tolerating occasional actor failure is very important to avoid degrading the performance. In some cases, multiple actors simultaneously fail which makes the recovery very challenging. In this paper, we propose a new recovery approach which can handle simultaneous failures in WSANs. The approach is based on ranking network nodes relevant to a pre-assigned root actor. Ranking creates a tree to be used for coordinating the recovery among nodes. To minimize the recovery overhead, the nodes are virtually grouped to clusters and each node is assigned a recovery weight as well as a nearby cluster member which serves as a gateway to lost nodes. Designation of cluster heads is based on the number of children in the recovery tree. The simulation results confirm the correctness and effectiveness of the proposed approach in restoring network connectivity and also show that on the average the incurred overhead is low compared to contemporary single-failure recovery approaches.
---
paper_title: Recovery from multiple simultaneous failures in wireless sensor networks using minimum Steiner tree

paper_content:

In some applications, wireless sensor networks (WSNs) operate in very harsh environments and nodes become subject to increased risk of damage. Sometimes a WSN suffers from the simultaneous failure of multiple sensors and gets partitioned into disjoint segments. Restoring network connectivity in such a case is crucial in order to avoid negative effects on the application. Given that WSNs often operate unattended in remote areas, the recovery should be autonomous. This paper promotes an effective strategy for restoring the connectivity among these segments by populating the least number of relay nodes. Finding the optimal count and position of relay nodes is NP-hard and heuristics are thus pursued. We propose a Distributed algorithm for Optimized Relay node placement using Minimum Steiner tree (DORMS). Since in autonomously operating WSNs it is infeasible to perform a network-wide analysis to diagnose where segments are located, DORMS moves relay nodes from each segment toward the center of the deployment area. As soon as those relays become in range of each other, the partitioned segments resume operation. DORMS further model such initial inter-segment topology as Steiner tree in order to minimize the count of required relays. Disengaged relays can return to their respective segments to resume their pre-failure duties. We analyze DORMS mathematically and explain the beneficial aspects of the resulting topology with respect to connectivity, and traffic balance. The performance of DORMS is validated through extensive simulation experiments.
---
paper_title: Survey: A survey on relay placement with runtime and approximation guarantees

paper_content:

We discuss aspects and variants of the fundamental problem of relay placement: given a set of immobile terminals in the Euclidean plane, place a number of relays with limited viewing range such that the result is a low-cost communication infrastructure between the terminals. We first consider the problem from a global point of view. The problem here is similar to forming discrete Steiner tree structures. Then we investigate local variants of the problem, assuming mobile relays that must decide where to move based only on information from their local environment. We give a local algorithm for the general problem, but we show that no local algorithm can achieve good approximation factors for the number of relays. The following two restricted variants each address different aspects of locality. First we provide each relay with knowledge of two fixed neighbors, such that the relays form a chain between two terminals. The goal here is to let the relays move to the line segment between the terminals as fast as possible. Then we focus on the aspect of neighbors that are not fixed, but which may change over time. In return, we relax the objective function from geometric structures to just forming a single point. The goal in all our local formation problems is to use relays that are as limited as possible with respect to memory, sensing capabilities and so on. We focus on algorithms for which we can prove performance guarantees such as upper bounds on the required runtime, maximum traveled distances of the relays and approximation factors for the solution.
---
paper_title: Relay sensor placement in wireless sensor networks

paper_content:

This paper addresses the following relay sensor placement problem: given the set of duty sensors in the plane and the upper bound of the transmission range, compute the minimum number of relay sensors such that the induced topology by all sensors is globally connected. This problem is motivated by practically considering the tradeoff among performance, lifetime, and cost when designing sensor networks. In our study, this problem is modelled by a NP-hard network optimization problem named Steiner Minimum Tree with Minimum number of Steiner Points and bounded edge length (SMT-MSP). In this paper, we propose two approximate algorithms, and conduct detailed performance analysis. The first algorithm has a performance ratio of 3 and the second has a performance ratio of 2.5.
---
paper_title: Relay node placement in structurally damaged wireless sensor networks via triangular steiner tree approximation

paper_content:

Wireless sensor networks (WSNs) have many applications which operate in hostile environments. Due to the harsh surroundings, WSNs may suffer from a large scale damage that causes many nodes to fail simultaneously and the network to get partitioned into multiple disjoint segments. In such a case, restoring the network connectivity is very important in order to avoid negative effects on the applications. In this paper, we pursue the placement of the least number of relay nodes to re-establish a strongly connected network topology. The problem of finding the minimum count and the position of relay nodes is NP-hard and hence we pursue heuristics. We present a novel three-step algorithm called FeSTA which is based on steinerizing appropriate triangles. Each segment is represented by a terminal. Each subset of 3 terminals forms a triangle. Finding the optimal solution for a triangle (i.e. connecting 3 segments) is a relatively easier problem. In the first step, FeSTA finds the best triangles and form islands of segments by establishing intra-triangle connectivity. Then in the second, disjoint islands of segment are federated. In the final step, the steinerized edges are optimized. The performance of FeSTA is validated through simulation.
---
paper_title: Steiner tree problem with minimum number of Steiner points and bounded edge-length

paper_content:

Abstract In this paper, we study the Steiner tree problem with minimum number of Steiner points and bounded edge-length (STPMSPBEL), which asks for a tree interconnecting a given set of n terminal points and a minimum number of Steiner points such that the Euclidean length of each edge is no more than a given positive constant. This problem has applications in VLSI design, WDM optimal networks and wireless communications. We prove that this problem is NP-complete and present a polynomial time approximation algorithm whose worst-case performance ratio is 5.
---
paper_title: Optimal relay node placement in delay constrained wireless sensor network design

paper_content:

The Delay Constrained Relay Node Placement Problem (DCRNPP) frequently arises in the Wireless Sensor Network (WSN) design. In WSN, Sensor Nodes are placed across a target geographical region to detect relevant signals. These signals are communicated to a central location, known as the Base Station, for further processing. The DCRNPP aims to place the minimum number of additional Relay Nodes at a subset of Candidate Relay Node locations in such a manner that signals from various Sensor Nodes can be communicated to the Base Station within a pre-specified delay bound. In this paper, we study the structure of the projection polyhedron of the problem and develop valid inequalities in form of the node-cut inequalities. We also derive conditions under which these inequalities are facet defining for the projection polyhedron. We formulate a branch-and-cut algorithm, based upon the projection formulation, to solve DCRNPP optimally. A Lagrangian relaxation based heuristic is used to generate a good initial solution for the problem that is used as an initial incumbent solution in the branch-and-cut approach. Computational results are reported on several randomly generated instances to demonstrate the efficacy of the proposed algorithm.
---
paper_title: Augmenting the Connectivity of Geometric Graphs

paper_content:

Let G be a connected plane geometric graph with n vertices. In this paper, we study bounds on the number of edges required to be added to G to obtain 2-vertex or 2-edge connected plane geometric graphs. In particular, we show that for G to become 2-edge connected, 2n3 additional edges are required in some cases and that 6n7 additional edges are always sufficient. For the special case of plane geometric trees, these bounds decrease to n2 and 2n3, respectively.
---
paper_title: Independence free graphs and vertex connectivity augmentation

paper_content:

Given an undirected graph G and a positive integer k, the k-vertex-connectivity augmentation problem is to find a smallest set F of new edges for which G + F is k-vertex-connected. Polynomial algorithms for this problem have been found only for k ≤ 4 and a major open question in graph connectivity is whether this problem is solvable in polynomial time in general.In this paper, we develop an algorithm which delivers an optimal solution in polynomial time for every fixed k. In the case when the size of an optimal solution is large compared to k, our algorithm is polynomial for all k. We also derive a min-max formula for the size of a smallest augmenting set in this case. A key step in our proofs is a complete solution of the augmentation problem for a new family of graphs which we call k-independence free graphs. We also prove new splitting off theorems for vertex connectivity.
---
paper_title: Relay Node Placement for Multi-Path Connectivity in Heterogeneous Wireless Sensor Networks

paper_content:

Abstract In this paper, we study the problem of deploying additional relay nodes to provide multi-path connectivity (kconnectivity) between all nodes in wireless sensor network. Specifically given a disconnected wireless network, few additional nodes is to be deployed so that the augmented network will have higher degree of connectivity for fault tolerance. We propose an algorithm based on Particle Swarm Optimization, that places optimum number of energy constrain relay nodes to achieve desired connectivity between heterogeneous wireless sensor nodes in which the communication range of each sensor node is different. In simulation, the proposed algorithm is compared with the heuristic algorithm for number of relay nodes required to obtain desired k-connectivity and the average value degree of nodes in resulting network. Result shows that Particle Swarm Optimization based algorithm perform over heuristic algorithm.
---
paper_title: Relay placement for restoring connectivity in partitioned wireless sensor networks under limited information

paper_content:

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.
---
paper_title: Fault-Tolerant Relay Node Placement in Heterogeneous Wireless Sensor Networks

paper_content:

Existing work on placing additional relay nodes in wireless sensor networks to improve network connectivity typically assumes homogeneous wireless sensor nodes with an identical transmission radius. In contrast, this paper addresses the problem of deploying relay nodes to provide fault-tolerance with higher network connectivity in heterogeneous wireless sensor networks, where sensor nodes possess different transmission radii. Depending on the level of desired fault-tolerance, such problems can be categorized as: (1) full fault-tolerance relay node placement, which aims to deploy a minimum number of relay nodes to establish k (k ges 1) vertex-disjoint paths between every pair of sensor and/or relay nodes; (2) partial fault-tolerance relay node placement, which aims to deploy a minimum number of relay nodes to establish k (k ges 1) vertex-disjoint paths only between every pair of sensor nodes. Due to the different transmission radii of sensor nodes, these problems are further complicated by the existence of two different kinds of communication paths in heterogeneous wireless sensor networks, namely two-way paths, along which wireless communications exist in both directions; and one-way paths, along which wireless communications exist in only one direction. Assuming that sensor nodes have different transmission radii, while relay nodes use the same transmission radius, this paper comprehensively analyzes the range of problems introduced by the different levels of fault-tolerance (full or partial) coupled with the different types of path (one-way or two-way). Since each of these problems is NP-hard, we develop O(sigmak2)-approximation algorithms for both one-way and two-way partial fault-tolerance relay node placement, as well as O(sigmak3)-approximation algorithms for both one-way and two-way full fault-tolerance relay node placement (sigma is the best performance ratio of existing approximation algorithms for finding a minimum k-vertex connected spanning graph). To facilitate the applications in higher dimensions, we also extend these algorithms and derive their performance ratios in d-dimensional heterogeneous wireless sensor networks (d ges 3). Finally, heuristic implementations of these algorithms are evaluated via simulations.
---
paper_title: Fault-tolerant relay node placement in wireless sensor networks: formulation and approximation

paper_content:

A two-tiered network model has been proposed for prolonging lifetime and improving scalability in wireless sensor networks (Gupta, G. and Younis, M., Proc. IEEE WCNC'03, p.1579-84, 2003; Proc. IEEE ICC'03, p.1848-52, 2003). This two-tiered network is a cluster-based network. Relay nodes are placed in the playing field to act as cluster heads and to form a connected topology for data transmission in the higher tier. They are able to fuse data packets from sensor nodes in their clusters and send them to sinks through wireless multi-hop paths. However, this model is not fault-tolerant as the network may be disconnected if a relay node fails. We formulate and study a fault-tolerant relay node placement problem in wireless sensor networks. In this problem, we want to place a minimum number of relay nodes in the playing field of a sensor network such that (1) each sensor node can communicate with at least two relay nodes and (2) the relay node network is 2-connected. We present a polynomial time approximation algorithm for this problem and prove the worst-case performance given by our algorithm is bounded within O(D log n) times of the size of an optimal solution, where n is the number of sensor nodes in the network, D is the (2, 1) diameter of the network formed by a sufficient set of possible positions for relay nodes.
---
paper_title: Survey: A survey on relay placement with runtime and approximation guarantees

paper_content:

We discuss aspects and variants of the fundamental problem of relay placement: given a set of immobile terminals in the Euclidean plane, place a number of relays with limited viewing range such that the result is a low-cost communication infrastructure between the terminals. We first consider the problem from a global point of view. The problem here is similar to forming discrete Steiner tree structures. Then we investigate local variants of the problem, assuming mobile relays that must decide where to move based only on information from their local environment. We give a local algorithm for the general problem, but we show that no local algorithm can achieve good approximation factors for the number of relays. The following two restricted variants each address different aspects of locality. First we provide each relay with knowledge of two fixed neighbors, such that the relays form a chain between two terminals. The goal here is to let the relays move to the line segment between the terminals as fast as possible. Then we focus on the aspect of neighbors that are not fixed, but which may change over time. In return, we relax the objective function from geometric structures to just forming a single point. The goal in all our local formation problems is to use relays that are as limited as possible with respect to memory, sensing capabilities and so on. We focus on algorithms for which we can prove performance guarantees such as upper bounds on the required runtime, maximum traveled distances of the relays and approximation factors for the solution.
---
paper_title: Relay sensor placement in wireless sensor networks

paper_content:

This paper addresses the following relay sensor placement problem: given the set of duty sensors in the plane and the upper bound of the transmission range, compute the minimum number of relay sensors such that the induced topology by all sensors is globally connected. This problem is motivated by practically considering the tradeoff among performance, lifetime, and cost when designing sensor networks. In our study, this problem is modelled by a NP-hard network optimization problem named Steiner Minimum Tree with Minimum number of Steiner Points and bounded edge length (SMT-MSP). In this paper, we propose two approximate algorithms, and conduct detailed performance analysis. The first algorithm has a performance ratio of 3 and the second has a performance ratio of 2.5.
---
paper_title: REER: Robust and Energy Efficient Multipath Routing Protocol for Wireless Sensor Networks

paper_content:

Wireless Sensor Networks (WSNs) are subject to node failures because of energy constraints, as well nodes can be added to or removed from the network upon application demands, resulting in unpredictable topology changes. Furthermore, due to limited transmission range of wireless sensor nodes, multiple hops are usually needed for a node to exchange information with other nodes or sink node(s). This makes the design of routing protocols in such networks a challenging task. In all proposed single path routing schemes a periodic low-rate flooding of data is required to recover from path failures, which causes consumption of scarce resources of the sensor node. Thus multipath routing schemes is an optimal alternative to maximize the network lifetime. Multipath routing schemes distribute the traffic across multiple paths instead of routing all the traffic along a single path, which spreads consumed energy evenly across the nodes within the network, potentially resulting in longer lifetimes. ::: ::: In this paper, we propose a robust and energy efficient multipath routing protocol (shortly abbreviated as REER). REER uses the residual energy, node available buffer size, and Signal-to-Noise Ratio (SNR) to predict the best next hop through the paths construction phase. REER examines two methods of traffic allocation; the first method uses a single path among the discovered paths to transfer the data message, when this path cost falls bellow a certain threshold, it then switches to the next alternative path. The second method is to split up the transmitted message into number of segments of equal size, add XOR-based error correction codes, and then transmit it across multiple paths simultaneously to increase the probability that an essential portion of the packet is received at the destination without incurring excessive delay. ::: ::: Through computer simulation, we evaluate and study the performance of our routing protocol and compare it with other protocols. Simulation results show that our protocol achieves more energy savings, lower average delay and higher packet delivery ratio than other protocols.
---
paper_title: Survey paper: A survey on routing algorithms for wireless Ad-Hoc and mesh networks

paper_content:

Wireless networking technology is evolving as an inexpensive alternative for building federated and community networks (relative to the traditional wired networking approach). Besides its cost-effectiveness, a wireless network brings operational efficiencies, namely mobility and untethered convenience to the end user. A wireless network can operate in both the ''Ad-Hoc'' mode, where users are self-managed, and the ''Infrastructure'' mode, where an authority manages the network with some Infrastructure such as fixed wireless routers, base stations, access points, etc. An Ad-Hoc network generally supports multi-hopping, where a data packet may travel over multiple hops to reach its destination. Among the Infrastructure-based networks, a Wireless Mesh Network (with a set of wireless routers located at strategic points to provide overall network connectivity) also provides the flexibility of multi-hopping. Therefore, how to route packets efficiently in wireless networks is a very important problem. A variety of wireless routing solutions have been proposed in the literature. This paper presents a survey of the routing algorithms proposed for wireless networks. Unlike routing in a wired network, wireless routing introduces new paradigms and challenges such as interference from other transmissions, varying channel characteristics, etc. In a wireless network, routing algorithms are classified into various categories such as Geographical, Geo-casting, Hierarchical, Multi-path, Power-aware, and Hybrid routing algorithms. Due to the large number of surveys that study different routing-algorithm categories, we select a limited but representative number of these surveys to be reviewed in our work. This survey offers a comprehensive review of these categories of routing algorithms. In the early stages of development of wireless networks, basic routing algorithms, such as Dynamic Source Routing (DSR) and Ad-Hoc On-demand Distance Vector (AODV) routing, were designed to control traffic on the network. However, it was found that applying these basic routing algorithms directly on wireless networks could lead to some issues such as large area of flooding, Greedy Forwarding empty set of neighbors, flat addressing, widely-distributed information, large power consumption, interference, and load-balancing problems. Therefore, a number of routing algorithms have been proposed as extensions to these basic routing algorithms to enhance their performance in wireless networks. Hence, we study the features of routing algorithms, which are compatible with the wireless environment and which can overcome these problems.
---
paper_title: RELAX: An Energy Efficient Multipath Routing Protocol for Wireless Sensor Networks

paper_content:

This paper presents an energy efficient multipath routing protocol specifically designed for wireless sensor networks (referred as RELAX). RELAX protocol tries to utilize the relaxation phenomenon of certain batteries to increase the battery lifetime and hence increasing the overall lifetime of the sensor network. Relaxation periods enable the battery to recover a portion of its lost power; it has been proven that the intermittent operation of some alkaline batteries increases its lifespan by about 28%. RELAX uses a link cost function that depends on current residual energy, available buffer size, and link quality (in terms of Signal-to-Noise ratio) to predict the best next hop during the path construction phase. RELAX routes data across multiple paths to balance the energy consumed across multiple nodes and to increase the throughput as well as minimizing packet end-to-end delay. Before transmitting the data, RELAX protocol adds data redundancy through a light weight Forward Error Correction (FEC) technique to increase the protocol reliability and resiliency to path failures. Many simulation experiments have been cried out to evaluate the protocol performance. Results show that RELAX protocol achieves lower energy consumption, lower packet delay, higher throughput, and long node lifetime duration compared to other protocols.
---
paper_title: LIEMRO: A Low-Interference Energy-Efficient Multipath Routing Protocol for Improving QoS in Event-Based Wireless Sensor Networks

paper_content:

In the recent years, multipath routing techniques are recognized as an effective approach to improve QoS in Wireless Sensor Networks (WSNs). However, in most of the previously proposed protocols either the effects of inter-path interference are ignored, or establishing low-interference paths is very costly. In this paper, we propose a Low-Interference Energy-efficient Multipath ROuting protocol (LIEMRO) for WSNs. This protocol is mainly designed to improve packet delivery ratio, lifetime, and latency, through discovering multiple interference-minimized node-disjoint paths between source node and sink node. In addition, LIEMRO includes a load balancing algorithm to distribute source node’s traffic over multiple paths based on the relative quality of each path. Simulation results show that using LIEMRO in high traffic load conditions can increase data reception rate and network lifetime even more than 1.5x compared with single path routing approach, while end-to-end latency reduces significantly. Accordingly, LIEMRO is a multipath solution for event-driven applications in which lifetime, reliability, and latency are of great importance.
---
paper_title: PEAS: a robust energy conserving protocol for long-lived sensor networks

paper_content:

Small, inexpensive sensors with limited memory, computing power and short battery lifetimes are turning into reality. Due to adverse conditions such as high noise levels, extreme humidity or temperatures, or even destructions from unfriendly entities, sensor node failures may become norms rather than exceptions in real environments. To be practical, sensor networks must last for much longer times than that of individual nodes, and have yet to be robust against potentially frequent node failures. This paper presents the design of PEAS, a simple protocol that can build a long-lived sensor network and maintain robust operations using large quantities of economical, short-lived sensor nodes. PEAS extends system functioning time by keeping only a necessary set of sensors working and putting the rest into sleep mode. Sleeping ones wake up now and then, probing the local environment and replacing failed ones. The sleeping periods are self-adjusted dynamically, so as to keep the sensors' wakeup rate roughly constant, thus adapting to high node densities.
---
paper_title: Design of an enhanced energy conserving routing protocol based on route diversity in wireless sensor networks

paper_content:

This paper presents a new Energy Conserving Routing Protocol (ECRP) that aims to optimize the transmission cost over a path from a source to a defined destination in a Wireless Sensor Network. Energy consumption remains a significant metric related to the service lifetime of a Wireless Sensor Network. This parameter is included in our model in order to generate a set of maximally disjoint paths between each sensor and the sink, so as to avoid or partially reduce the appearance of congestion in the network. We aim to spread the data traffic over non-overlapping paths in order to increase the global network lifetime. Simulations have shown that our ECRP is more efficient than existing protocols in terms of congestion avoidance and energy saving.
---
paper_title: An Energy Efficient Fault Tolerant Multipath (EEFTM) Routing Protocol for Wireless Sensor Networks

paper_content:

Currently, there is very little research that aims at handling QoS requirements using multipath routing in a very energy constrained environment like sensor networks. In this paper, Energy efficient fault-tolerant multipath routing technique which utilizes multiple paths between source and the sink. has been proposed. This protocol is intended to provide a reliable transmission environment with low energy consumption, by efficiently utilizing the energy availability and the available bandwidth of the nodes to identify multiple routes to the destination. To achieve reliability and fault tolerance, this protocol selects reliable paths based on the average reliability rank (ARR) of the paths. Average reliability rank of a path is based on each node's reliability rank (RR), which represents the probability that a node correctly delivers data to the destination. In case the existing route encounters some unexpected link or route failure, the algorithm selects the path with the next highest ARR, from the list of selected paths. Simulation results show that the proposed protocol minimizes the energy and latency and maximizes the delivery ratio.
---
paper_title: Research on Key Technology and Applications for Internet of Things

paper_content:

Abstract The Internet of Things (IOT) has been paid more and more attention by the academe, industry, and government all over the world. The concept of IOT and the architecture of IOT are discussed. The key technologies of IOT, including Radio Frequency Identification technology, Electronic Product Code technology, and ZigBee technology are analyzed. The framework of digital agriculture application based on IOT is proposed.
---
paper_title: Octopus: a fault-tolerant and efficient ad-hoc routing protocol

paper_content:

Mobile ad-hoc networks (MANETs) are failure-prone environments; it is common for mobile wireless nodes to intermittently disconnect from the network, e.g., due to signal blockage. This paper focuses on withstanding such failures in large MANETs: we present Octopus, a fault-tolerant and efficient position-based routing protocol. Fault-tolerance is achieved by employing redundancy, i.e., storing the location of each node at many other nodes, and by keeping frequently refreshed soft state. At the same time, Octopus achieves a low location update overhead by employing a novel aggregation technique, whereby a single packet updates the location of many nodes at many other nodes. Octopus is highly scalable: for a fixed node density, the number of location update packets sent does not grow with the network size. And when the density increases, the overhead drops. Thorough empirical evaluation using the ns2 simulator with up to 675 mobile nodes shows that Octopus achieves excellent fault-tolerance at a modest overhead: when all nodes intermittently disconnect and reconnect, Octopus achieves the same high reliability as when all nodes are constantly up.
---
paper_title: Ad-hoc on-demand distance vector routing

paper_content:

An ad-hoc network is the cooperative engagement of a collection of mobile nodes without the required intervention of any centralized access point or existing infrastructure. We present Ad-hoc On Demand Distance Vector Routing (AODV), a novel algorithm for the operation of such ad-hoc networks. Each mobile host operates as a specialized router, and routes are obtained as needed (i.e., on-demand) with little or no reliance on periodic advertisements. Our new routing algorithm is quite suitable for a dynamic self starting network, as required by users wishing to utilize ad-hoc networks. AODV provides loop-free routes even while repairing broken links. Because the protocol does not require global periodic routing advertisements, the demand on the overall bandwidth available to the mobile nodes is substantially less than in those protocols that do necessitate such advertisements. Nevertheless we can still maintain most of the advantages of basic distance vector routing mechanisms. We show that our algorithm scales to large populations of mobile nodes wishing to form ad-hoc networks. We also include an evaluation methodology and simulation results to verify the operation of our algorithm.
---
paper_title: The complexity of finding two disjoint paths with min-max objective function

paper_content:

Abstract Given a network G = (V,E) and two vertices s and t, we consider the problem of finding two disjoint paths from s to t such that the length of the longer path is minimized. The problem has several variants: The paths may be vertex-disjoint or arc-disjoint and the network may be directed or undirected. We show that all four versions as well as some related problems are strongly NP-complete. We also give a pseudo-polynomial-time algorithm for the acyclic directed case.
---
paper_title: Highly-resilient, energy-efficient multipath routing in wireless sensor networks

paper_content:

Previously proposed sensor network data dissemination schemes require periodic low-rate flooding of data in order to allow recovery from failure. We consider constructing two kinds of multipaths to enable energy efficient recovery from failure of the shortest path between source and sink. Disjoint multipath has been studied in the literature. We propose a novel braided multipath scheme, which results in several partially disjoint multipath schemes. We find that braided multipaths are a viable alternative for energy-efficient recovery from isolated and patterned failures.
---
paper_title: Constructing disjoint paths for failure recovery and multipath routing

paper_content:

Applications such as Voice over IP and video streaming require continuous network service, requiring fast failure recovery mechanisms. Proactive failure recovery schemes have been recently proposed to improve network performance during the failure transients. These proactive failure recovery schemes need extra infrastructural support in the form of routing table entries, extra addresses etc. In this paper, we study if the extra infrastructure support can be exploited to build disjoint paths in those frameworks, while keeping the lengths of the recovery paths close to those of the primary paths. Our evaluations show that it is possible to extend the proactive failure recovery schemes to provide support for nearly-disjoint paths which can be employed in multipath routing for load balancing and QoS.
---
paper_title: Disjoint paths in a network

paper_content:

Routes between two given nodes of a network are called diversified if they are node-disjoint, except at the terminals. Diversified routes are required for reliability in communication, and an additional criterion is that their total cost, assumed to be the sum of individual arc lengths or costs, is minimum. An algorithm and related theory is described for a general number K of node-disjoint paths with minimum total length. The algorithm applies shortest path labeling algorithms familiar in the literature. K node-disjoint paths are found in K iterations of a single shortest path algorithm.
---
paper_title: Strategies and Techniques for Node Placement in Wireless Sensor Networks : A Survey

paper_content:

The major challenge in designing wireless sensor networks (WSNs) is the support of the functional, such as data latency, and the non-functional, such as data integrity, requirements while coping with the computation, energy and communication constraints. Careful node placement can be a very effective optimization means for achieving the desired design goals. In this paper, we report on the current state of the research on optimized node placement in WSNs. We highlight the issues, identify the various objectives and enumerate the different models and formulations. We categorize the placement strategies into static and dynamic depending on whether the optimization is performed at the time of deployment or while the network is operational, respectively. We further classify the published techniques based on the role that the node plays in the network and the primary performance objective considered. The paper also highlights open problems in this area of research.
---
paper_title: How Reliable Can Two-Path Protection Be?

paper_content:

This paper investigates the subject of reliability via two link-disjoint paths in mesh networks. We address the issues of how reliable two-path protection can be and how to achieve the maximum reliability. This work differs from traditional studies, such as MIN-SUM, MIN-MAX, and MIN-MIN, in that the objective in this paper is to maximize the reliability of the two-path connection given the link reliability, or equivalently, to minimize the end-to-end failure probability. We refer to this problem as MAX-REL. Solving MAX-REL provides 100% protection against a single failure while maximizing the reliability regardless of how many link failures occur in the network. We prove that this problem is NP-complete and derive a corresponding upper bound, which is the theoretical maximum reliability for a source-destination pair, and a lower bound, which is the worst case of the proposed algorithm. The time efficiency of the algorithms is analyzed, and the performance of the algorithms is evaluated through simulation. We demonstrate that our heuristic algorithms not only achieve a low computing complexity, but also achieve nearly equivalent performance to the upper bound.
---
paper_title: A greedy-based stable multi-path routing protocol in mobile ad hoc networks

paper_content:

With the increasing popularity of multimedia, there is a growing tendency in mobile ad hoc networks (MANETs) to establish stable routes with long route lifetimes, low control overhead and high packet delivery ratios. According to recent analytical result, the lifetime of a route, which can reflect the route stability, depends on the length of the route and the lifetime of each link in the route. This paper presents a Greedy-based Backup Routing (GBR) protocol that considers both route length and link lifetime to achieve high route stability. In GBR, the primary path is constructed primarily based on a greedy forwarding mechanism, whereas the local-backup path for each link is established according to the link lifetime. Both analytical and simulation results demonstrate that GBR has excellent performance in terms of route lifetime, packet delivery ratio, and control overhead.
---
paper_title: An energy efficient and QoS aware multipath routing protocol for wireless sensor networks

paper_content:

Enabling real time applications in Wireless Sensor Networks (WSNs) demands certain delay and bandwidth requirements which pose more challenges in the design of networking protocols. Therefore, enabling such applications in this type of networks requires energy and Quality of Service (QoS) awareness in different layers of the protocol stack. In many of these applications (such as multimedia applications, or real time and mission critical applications), the network traffic is mixed of delay sensitive and reliability demanding data. Hence, QoS routing becomes an important issue. In this paper, we propose an Energy Efficient and QoS aware multipath routing protocol (we name it shortly as EQSR) that maximizes the network lifetime through balancing energy consumption across multiple nodes, uses the concept of service differentiation to allow high important traffic (or delay sensitive traffic) to reach the sink node within an acceptable delay, reduces the end to end delay through spreading out the traffic across multiple paths, and increases the throughput through introducing data redundancy. EQSR uses the residual energy, node available buffer size, and Signal-to-Noise Ratio (SNR) to predict the best next hop through the paths construction phase. Based on the concept of service differentiation the EQSR protocol employs a queuing model to handle both real time and non-real time traffic. By means of computer simulations, we evaluated and studied the performance of our routing protocol and compared it with another protocol. Simulation results have shown that our protocol achieves lower average delay and higher packet delivery ratio than the other protocol.
---
paper_title: Fibonacci Heaps And Their Uses In Improved Network Optimization Algorithms

paper_content:

In this paper we develop a new data structure for implementing heaps (priority queues). Our structure, Fibonacci heaps (abbreviated F-heaps), extends the binomial queues proposed by Vuillemin and studied further by Brown. F-heaps support arbitrary deletion from an n-item heap in 0(log n) amortized time and all other standard heap operations in 0(1) amortized time. Using F-heaps we are able to obtain improved running times for several network optimization algorithms.
---
paper_title: A new approach to the maximum flow problem

paper_content:

All previously known efftcient maximum-flow algorithms work by finding augmenting paths, either one path at a time (as in the original Ford and Fulkerson algorithm) or all shortest-length augmenting paths at once (using the layered network approach of Dinic). An alternative method based on the preflow concept of Karzanov is introduced. A preflow is like a flow, except that the total amount flowing into a vertex is allowed to exceed the total amount flowing out. The method maintains a preflow in the original network and pushes local flow excess toward the sink along what are estimated to be shortest paths. The algorithm and its analysis are simple and intuitive, yet the algorithm runs as fast as any other known method on dense. graphs, achieving an O(n)) time bound on an n-vertex graph. By incorporating the dynamic tree data structure of Sleator and Tarjan, we obtain a version of the algorithm running in O(nm log(n'/m)) time on an n-vertex, m-edge graph. This is as fast as any known method for any graph density and faster on graphs of moderate density. The algorithm also admits efticient distributed and parallel implementations. A parallel implementation running in O(n'log n) time using n processors and O(m) space is obtained. This time bound matches that of the Shiloach-Vishkin
---
paper_title: Finding Minimum Energy Disjoint Paths in Wireless Ad-Hoc Networks

paper_content:

We develop algorithms for finding minimum energy disjoint paths in an all-wireless network, for both the node and link-disjoint cases. Our major results include a novel polynomial time algorithm that optimally solves the minimum energy 2 link-disjoint paths problem, as well as a polynomial time algorithm for the minimum energy k node-disjoint paths problem. In addition, we present efficient heuristic algorithms for both problems. Our results show that link-disjoint paths consume substantially less energy than node-disjoint paths. We also found that the incremental energy of additional link-disjoint paths is decreasing. This finding is some what surprising due to the fact that in general networks additional paths are typically longer than the shortest path. However, in a wireless network, additional paths can be obtained at lower energy due to the broadcast nature of the wireless medium. Finally, we discuss issues regarding distributed implementation and present distributed versions of the optimal centralized algorithms presented in the paper.
---
paper_title: Highly-resilient, energy-efficient multipath routing in wireless sensor networks

paper_content:

Previously proposed sensor network data dissemination schemes require periodic low-rate flooding of data in order to allow recovery from failure. We consider constructing two kinds of multipaths to enable energy efficient recovery from failure of the shortest path between source and sink. Disjoint multipath has been studied in the literature. We propose a novel braided multipath scheme, which results in several partially disjoint multipath schemes. We find that braided multipaths are a viable alternative for energy-efficient recovery from isolated and patterned failures.
---
paper_title: A proactive maintaining algorithm for dynamic topology control in wireless sensor networks

paper_content:

A proactive topology control algorithm named PMD (Proactive Maintaining Algorithm for Dynamic Topology Control) is proposed for solving the problem of network partitioning. The algorithm controls the starting of BFS (Breadth-First Search) by recognizing the addition of invalid nodes, monitoring the network structure dynamically. The definition, 'Communication Quality', is proposed to measure the quality of communications link. Only after network partitioning happens does PMD (Proactive Maintaining Algorithm for Dynamic Topology Control) start the link rebuilding mechanism to maintain the topology. The algorithm restrains isolated nodes generation and makes the energy be used efficiently. The results show that PMD (Proactive Maintaining Algorithm for Dynamic Topology Control) not only improves the efficiency of the energy, but also constructs a robust topology.
---
paper_title: Local heuristic for the refinement of multi-path routing in wireless mesh networks

paper_content:

We consider wireless mesh networks and the problem of routing end-to-end traffic over multiple paths for the same origin-destination pair with minimal interference. We introduce a heuristic for path determination with two distinguishing characteristics. First, it works by refining an extant set of paths, determined previously by a single- or multi-path routing algorithm. Second, it is totally local, in the sense that it can be run by each of the origins on information that is available no farther than the node's immediate neighborhood. We have conducted extensive computational experiments with the new heuristic, using AODV and OLSR, as well as their multi-path variants, as underlying routing methods. For two different CSMA settings (as implemented by 802.11) and one TDMA setting running a path-oriented link scheduling algorithm, we have demonstrated that the new heuristic is capable of improving the average throughput network-wide. When working from the paths generated by the multi-path routing algorithms, the heuristic is also capable to provide a more evenly distributed traffic pattern.
---
paper_title: Strong minimum energy topology in wireless sensor networks: NPcompleteness and heuristics

paper_content:

Wireless sensor networks have recently attracted lots of research effort due to the wide range of applications. These networks must operate for months or years. However, the sensors are powered by battery, which may not be able to be recharged after they are deployed. Thus, energy-aware network management is extremely important. In this paper, we study the following problem: Given a set of sensors in the plane, assign transmit power to each sensor such that the induced topology containing only bidirectional links is strongly connected. This problem is significant in both theory and application. We prove its NP-completeness and propose two heuristics: power assignment based on minimum spanning tree (denoted by MST) and incremental power. We also show that the MST heuristic has a performance ratio of 2. Simulation study indicates that the performance of these two heuristics does not differ very much, but; on average, the incremental power heuristic is always better than MST.
---
paper_title: How Reliable Can Two-Path Protection Be?

paper_content:

This paper investigates the subject of reliability via two link-disjoint paths in mesh networks. We address the issues of how reliable two-path protection can be and how to achieve the maximum reliability. This work differs from traditional studies, such as MIN-SUM, MIN-MAX, and MIN-MIN, in that the objective in this paper is to maximize the reliability of the two-path connection given the link reliability, or equivalently, to minimize the end-to-end failure probability. We refer to this problem as MAX-REL. Solving MAX-REL provides 100% protection against a single failure while maximizing the reliability regardless of how many link failures occur in the network. We prove that this problem is NP-complete and derive a corresponding upper bound, which is the theoretical maximum reliability for a source-destination pair, and a lower bound, which is the worst case of the proposed algorithm. The time efficiency of the algorithms is analyzed, and the performance of the algorithms is evaluated through simulation. We demonstrate that our heuristic algorithms not only achieve a low computing complexity, but also achieve nearly equivalent performance to the upper bound.
---

Title: Resilient Wireless Sensor Networks Using Topology Control: A Review

Section 1: Introduction
Description 1: This section provides an overview of WSNs, their applications, challenges, and importance for IoT. It also sets the stage for discussing network resilience and outlines the paper's organization.

Section 2: Network Resilience
Description 2: This section defines network resilience, differentiates it from related concepts like robustness and survivability, and explains its significance in WSNs. It introduces stages of deployment impacting resilience: pre-deployment, post-deployment, and re-deployment.

Section 3: Resilient WSNs: k-Connected Network
Description 3: The section explains k-connected networks, introduces related terminologies and definitions, and discusses the importance of k-connectivity for resilient WSNs.

Section 4: Network Model
Description 4: This section delves into various network models, including homogeneous, heterogeneous, ideal, and irregular radio models, and the significance of asymmetric links in WSNs.

Section 5: Failure Model
Description 5: This section discusses various failure models affecting WSNs, including node failures, link failures, and attack-based failures, and how these influence network design and resilience.

Section 6: Topology Control
Description 6: This section explores topology control methods to preserve or improve WSN connectivity, focusing on three deployment stages: pre-deployment, post-deployment, and re-deployment.

Section 7: Multi-Path Routing Protocol
Description 7: This section introduces multi-path routing protocols, their importance for resilient WSNs, and popular routing strategies, including complete disjointed and brained paths.

Section 8: NP-Complete and NP-Hard Problems in Resilient WSNs
Description 8: This section summarizes the NP-complete and NP-hard problems related to resilient WSNs and discusses the significance of approximation algorithms and heuristics.

Section 9: Open Issues
Description 9: This section highlights remaining challenges and areas for future research, including mobility, distributed algorithms, and integration of approaches across deployment stages.

Section 10: Conclusions
Description 10: This section summarizes the paper's findings on resilient WSNs, emphasizing the importance of k-connectivity, realistic modeling, and multi-path routing. It offers guidelines for designing resilient WSNs and highlights the need for future research.