We propose two novel algorithms for distributed and location-free boundary recognition in wireless sensor networks. Both approaches enable a node to decide autonomously whether it is a boundary node, based solely on connectivity information of a small neighborhood. This makes our algorithms highly applicable for dynamic networks where nodes can move or become inoperative. We compare our algorithms qualitatively and quantitatively with several previous approaches. In extensive simulations, we consider various models and scenarios. Although our algorithms use less information than most other approaches, they produce significantly better results. They are very robust against variations in node degree and do not rely on simplified assumptions of the communication model. Moreover, they are much easier to implement on real sensor nodes than most existing approaches.
@cite_15: Many algorithms for routing in sensor networks exploit greedy forwarding strategies to get packets to their destinations. We study a fundamental difficulty such strategies face: the "local minimum phenomena" that can cause packets to get stuck. We give a definition of stuck nodes where packets may get stuck in greedy multi-hop forwarding, and develop a local rule, the TENT rule, for each node in the network to test whether a packet can get stuck at that node. To help the packets get out of stuck nodes, we describe a distributed algorithm, BOUNDHOLE, to build routes around holes, which are connected regions of the network with boundaries consisting of all the stuck nodes. We show that these hole-surrounding routes can be used in many applications such as geographic routing, path migration, information storage mechanisms and identification of regions of interest.
@cite_10: Wireless Sensor Networks (WSNs) consist of a large number of nodes networked via wireless links. In many WSN settings, sensor nodes are deployed in an ad hoc manner. One important issue in this context is to detect the boundary of the deployed network to ensure that the sensor nodes cover the target area. In this paper, we propose a new algorithm that can be used to discover the boundary of a randomly deployed WSN. The algorithm does not require the sensor nodes to be equipped with positioning devices and is scalable for large number of nodes. Simulation experiments are developed to evaluate the performance of the proposed algorithms for different network topologies. The simulation results show that the algorithm detects the boundary nodes of the network with high accuracy.
@cite_2: This paper introduces a distributed localized algorithm where sensor nodes determine if they are located along the perimeter of a wireless sensor network. The algorithm works correctly in sufficiently dense wireless sensor networks with a minimal requisite degree of connectivity. Using 1-hop and 2-hop neighbour information, nodes determine if they are surrounded by neighbouring nodes, and consequently, if they are located within the interior of the wireless sensor network. The algorithm requires minimal communication between nodes a desirable property since energy reserves are generally limited and non-renewable. keywords: wireless sensor network, distributed algorithms, perimeter detection
use information about node positions, distances between nodes, or angular relationships to detect network boundaries and holes. Accordingly, these approaches are limited to situations where GPS devices or similar equipment are available. Unfortunately, in many realistic scenarios this is not the case. Examples for geometrical approaches are Fang @cite_15 , Martincic @cite_2 , and Deogun @cite_10 .