Research output

Article in Journal ()

Localised alpha-shape computations for boundary recognition in sensor networks

Fayed M & Mouftah HT (2009) Localised alpha-shape computations for boundary recognition in sensor networks, Ad Hoc Networks, 7 (6), pp. 1259-1269.

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 solve the edge detection problem locally using a geometric structure called the alpha-shape (αα-shape). For a disc of radius 1/α1/α, the αα-shape consists of nodes (and joining edges) that sit on the boundary of the discs that contain no other nodes in the network. In the simplest terms a node decides it is on a network boundary by asking the following question: "Do I sit on the boundary of a disc of radius 1/α1/α that contains no other nodes in the network?" We show that using only local communications our algorithm is provably correct. Boundary nodes may further participate to reduce unwanted detail. We show via simulation that our algorithm identifies meaningful boundaries even in networks of low-density and non-uniform distribution.

Wireless; Sensor networks; Boundary detection; Alpha-shapes

Subject headings
Sensor networks; Wireless LANs

AuthorsFayed Marwan, Mouftah Hussein T
Publication date08/2009
ISSN 1570-8705

ad hoc Networks: Volume 7, Issue 6 (AUG 2009)

© University of Stirling FK9 4LA Scotland UK • Telephone +44 1786 473171 • Scottish Charity No SC011159
My Portal