As a sensor network grows large, it may become increasingly complex in topology due to its close ties to the surrounding environment. Previous work has shown that proper geometric processing of the network (e.g., boundary detection and localization) can provide very helpful information for applications to optimize their performance. To that end, numerous algorithms have been developed, providing a variety of inspiring solutions, yet exhibiting an ad hoc style in principle and implementation. In this thesis we show that the crux of solving many of the problems caused by complex topology is to identify the concave nodes, nodes that are located at concave network corners, where the boundary has an inner angle greater than π. The knowledge of such nodes makes several important tasks...[ Read more ]

As a sensor network grows large, it may become increasingly complex in topology due to its close ties to the surrounding environment. Previous work has shown that proper geometric processing of the network (e.g., boundary detection and localization) can provide very helpful information for applications to optimize their performance. To that end, numerous algorithms have been developed, providing a variety of inspiring solutions, yet exhibiting an ad hoc style in principle and implementation. In this thesis we show that the crux of solving many of the problems caused by complex topology is to identify the concave nodes, nodes that are located at concave network corners, where the boundary has an inner angle greater than π. The knowledge of such nodes makes several important tasks, namely geometric embedding, full localization, convex segmentation, and boundary detection, relatively easier or perform significantly better, as confirmed by simulations. These findings suggest that concave nodes can serve as a basic supporting structure for general geometric processing tasks and geometry-related applications in sensor networks.