A Mapping of Wireless Network Boundaries Using Localised Alpha-Shapes

Intuitively, many wireless and sensing applications benefit from knowledge of network boundaries. Many virtual coordinate constructions rely on the furthest set of nodes as beacons. Network edges may also bound routing holes in the network, regions of failure due to environmental effects, or indicate the need for additional deployment. In this paper we propose an algorithm to identify nodes and links that sit on the boundaries of the physical network. Edge nodes may then participate to map the network boundaries. Our algorithm is provably correct and exploits the relationship between alphahulls, a generalisation of the convex hull, and communication range. This relationship allows nodes on network boundaries to identify themselves without outside intervention. We then show via simulation that our algorithm identifies meaningful boundaries even in networks of low-density and non-uniform distribution.