An articulation point is a node whose removal partitions the network into disconnected segments. The articulation points may affect the reliability and efficiency of wireless multi-hop networks from different aspects. Although all articulation points destroy the connectivity of the network, their negative impact on the network is not equal. Removing some articulation points may disconnect a large subset of nodes or generate a large number of partitions, while removing some other articulation points may only disconnect a few nodes. In this paper, we present two novel problems for identifying the most vital articulation points that significantly impact the network. The first problem is finding the$p$most important articulation points that minimize the largest connected component in the remaining network. The second problem is finding the$p$most important articulation points whose removal maximizes the number of partitions in the network. We prove that both problems are NP-Hard and propose a distributed algorithm to identify the vital articulation points in both problems. The proposed algorithm establishes a distributed depth-first search tree to identify the articulation points, assigns a score to each articulation point, and selects the prominent articulation points based on their scores. We compare the proposed algorithm with a brute force-based exact algorithm. The simulation result shows that after removing the detected prominent articulation points by the proposed algorithm, the maximum difference between the largest partition size and the number of partitions with the optimal solutions are less than 27.6% and 28.2%, respectively, while the sent bytes of the proposed algorithm can be 89.9% lower.

Underwater wireless sensor networks (UWSNs) are utilized for a wide range of monitoring and surveillance applications. Lifetime maximization and maintenance of network reliability are among the most important considerations in the deployment of UWSNs.$k$-connectivity is a robust approach for reinforcing reliability. However, maintaining$k$disjoint paths from each sensor node to the BS, inevitably, results in extra energy dissipation, which reduces the network lifetime (NLT). Yet, there is no systematic exploration to determine the extent of lifetime reduction due to the increase in the$k$value, in the literature, to the best of our knowledge. In this study, we create an optimization framework to be able to explore the tradeoff between NLT and$k$-connectivity-based reliability in UWSNs. Through the optimal solutions of the proposed optimization model for a large set of salient parameters, we characterize the interplay between lifetime and$k$-connectivity. Our analysis reveals that the$k$value to be maintained in a UWSN can affect the NLT significantly.

Communicating over multi-hop connections simplifies the establishment of wireless multi-hop networks but brings new challenges such as limited reliability, bottlenecks, and weak connections. The minimum cut of a graph is the smallest subset of edges whose removal disconnects some nodes from the others. Finding minimum cuts of a wireless multi-hop network may reveal useful information such as bottlenecks and critical areas. This article introduces a distributed algorithm for detecting minimum cuts of a given witless multi-hop network by finding available edge-disjoint paths. Initially, the paths between two arbitrary neighbors are detected and these nodes are grouped as visited nodes. Then, the other nodes are added to the visited group one by one by finding at most$O(n)$paths in total where$n$is the number of nodes. The comprehensive simulation results showed that the proposed asynchronous algorithm detects minimum cuts with up to 37.1 and 55.8 percent lower sent bytes than the existing synchronous and central algorithms, respectively.

Mobile sensor networks (MSNs) have emerged from the interaction between mobile robotics and wireless sensor networks. MSNs can be deployed in harsh environments, where failures in some nodes can partition MSNs into disconnected network segments or reduce the coverage area. A$k$-connected network can tolerate at least$k$-1 arbitrary node failures without losing its connectivity. In this study, we present a coverage-aware distributed$k$-connectivity maintenance (restoration) algorithm that generates minimum-cost movements of active nodes after a node failure to preserve a persistent$k$value subject to a coverage conservation criterion. The algorithm accepts a coverage conservation ratio (as a trade-off parameter between coverage and movements) and facilitates coverage with the generated movements according to this value. Extensive simulations and testbed experiments reveal that the proposed algorithm restores$k$-connectivity more efficiently than the existing restoration algorithms. Furthermore, our algorithm can be utilized to maintain$k$-connectivity without sacrificing the coverage, significantly.

Finding critical links and weak points is an important task in almost all types of networks. Minimum cuts provide useful information about the critical links. However, finding a minimum cut of a network may provide insufficient or misleading information on critical links since the number of disconnected nodes in the residual network is not taken into account in this problem. In this work, we study the minimum cut into bounded sets problem, which limits the number of nodes in portioned sets. Finding the minimum cut into bounded sets can provide useful information on important critical links in a different network, whose failure has a hard and unacceptable effect. The minimum cut into bounded sets problem is an open NP-Complete problem. We propose a greedy algorithm for this problem with$O\left(c \times n^{2}\right)$time complexity and present computational results on random networks. To the best of our knowledge, the proposed algorithm is the first heuristic for the minimum cut into bounded sets problem.

Connectivity maintenance is an important requirement in wireless sensor and actuator networks (WSANs) because node failures can, potentially, lead to destructive changes in the network topology, which, in turn, can create a partitioned network. Preserving k-connectivity in a WSAN is important for keeping stable connections. A k-connected network is a network that remains connected after removing any k-1 nodes. Higher k values provide more reliable connectivity and a higher level of fault tolerance. In this article, we present a distributed k-connectivity restoration approach for heterogeneous WSANs where the nodes can be static or mobile. In the proposed algorithm, each node identifies the mobile nodes in the network and its 2-hop local subgraph. After a node is incapacitated, a neighbor of the failed node calls a mobile node with minimum moving cost to the location of the failed node if the failure reduces k. A minimum cost movement path between a neighbor of the failed node and a mobile node is constructed by considering the locations of the nodes, moving costs, and obstacles. Testbed experiments and comprehensive simulations reveal that the proposed distributed algorithm is capable of restoring k-connectivity with up to 35.5% lower sent Bytes and up to 40.9% lower movement cost than the existing algorithms.

The edge connectivity of a network is the minimum number of edges whose removal disconnect the network. The edge connectivity determines the minimum number of edge-disjoint paths between all nodes. Hence finding the edge connectivity can reveal useful information about reliability, alternative paths and bottlenecks. In this paper, we propose a cost-effective distributed algorithm that finds a lower bound for the edge connectivity of a network via finding at most c depth-first-search trees, where c is the edge connectivity. The proposed algorithm is asynchronous and does not need any synchronization between the nodes. In the proposed algorithm, the root node starts a distributed depth-first-search algorithm, and the nodes select next node in the tree based on their available edges to maximize the total number of established trees. The simulation results show that the proposed algorithm finds the edge connectivity with an average of 48% accuracy ratio.

In Wireless Sensor Networks (WSNs) keeping the network connectivity is a challenging task because failure in some nodes may cut off the communication paths between other nodes. A k-connected network remains connected after failure in any k-1 nodes, hence we can consider the k value as a metric for measuring the connectivity robustness of WSNs. In this paper we consider the effect of random node distribution and transmission range of nodes on k value of WSNs. To evaluate the effect of node count and transmission range on k, we generated 1000 random topologies with different transmission range and node count and measured the k value of established networks. Our simulation result showed that in a field of 1000 × 1000 m2area, with unified random distribution we need at least 200 nodes with minimum transmission range 80 m to expect a network with k ≥ 1. Also, the simulation results showed that random distributing of up to 500 nodes with transmission range lower than 80 in a field with mentioned area, generally leads to disconnected networks.

A critical node (cut vertex or articulation point) in wireless sensor networks, is a node which its failure breaks the connectivity of the network. Therefore, it is crucial that critical nodes be detected and treated with caution. This paper provides two localized distributed algorithms for determining the states of nodes (critical or noncritical). The first proposed algorithm identifies most of the critical and noncritical dominator nodes from two-hop local subgraph and connected dominating set (CDS) information that limits the computational complexity to O(Δ2) and bit complexity to O(clog2n) where Δ is the maximum node degree, c is the critical node count, and n is the node count. The testbed experiments and simulation results show that this algorithm detects up to 93% of critical nodes and achieves up to 91% of state determination with low energy consumption. The second proposed algorithm, which is based on the first one, finds the states of all nodes by running a limited distributed depth-first search algorithm in unrecognized parts of the network without traversing the whole network. Comprehensive testbed experiments and simulation results reveal that, in the presence of a CDS, this algorithm finds all critical nodes with lower energy consumption than all existing algorithms.

Maintaining connectivity is a very important objective of wireless sensor networks (WSNs) in successfully achieving data collection for applications. A cut vertex (node) is defined as a critical vertex whose removal disconnects a network component and partially disables data delivery. Hence, it is crucial that cut vertices be detected and treated with caution. In this paper, we propose an energy-efficient cut vertex detection (CVD) algorithm for WSNs. Our algorithm uses a depth-first search approach and is completely distributed. It benefits from the radio multicast capabilities of sensor nodes and is the first algorithm with a time complexity of O(N) and a sent message complexity of O(N), in which each message is O(log2(N)) bits. We show the operation of the algorithm, analyze it in detail, provide testbed experiments and extensive simulations. We compare our proposed algorithm with the other CVD algorithms and show that our algorithm saves up to 6.8 times more energy in less time.