Localized criteria for detection of critical nodes and links and k-connectivity in ad hoc networks

Abstract

Ad hoc network normally has critical connectivity properties before partitioning. The timely recognition is important in order to perform some data or service replication. Several existing centralized or globalized algorithms declare an edge or a node as critical if their removal will separate the network into several components. We introduce several localized definitions of critical nodes and critical links, using topological or positional information. A node is critical if the subgraph of p-neighbours of node (without the node itself) is disconnected. We propose three definitions of critical links, based on verifying common p-hop neighbours, loop length, and critical status of link endpoints, respectively. The experiments with random unit graph model of ad hoc networks show high correspondence of local and global decisions. Existing algorithms for testing k-connectivity are centralized. In this thesis, we introduce localized criteria for testing k-connectivity. In the first proposed local neighbor detection (LND) criterion, each node verifies whether or not itself and each of its p-hop neighbors have at least k neighbors. In the second local critical node detection (LCND) protocol, it also tests if the subgraph of its p-hop neighbours of a given node is k-connected. The third local subgraph connectivity detection (LSCD) protocol is based on communications between neighboring nodes to exchange the local decisions starting from k=1. All nodes declare themselves locally 1-connected. For k=2,3,..., iteratively, local decisions are propagated to p-hop neighbors. If node A is (k-1)-connected, all its p-hop neighbors are (k-1)-connected, and the graph consisting of p-hop neighbors of A (excluding A) is (k-1)-connected, then node A declares its neighborhood as k-connected. The experiments are carried with two ways of uniform generation of connected unit disk graphs. They show low percentage of false 'alarms', ability to locate critical areas in k-disconnected networks, and increased accuracy with increased local knowledge.