Given a set S of n sensors in the plane we consider the problem of establishing an ad hoc network from these sensors using directional antennae. We prove that for each given integer 1 ≤ k ≤ 5 there is a strongly connected spanner on the set of points so that each sensor uses at most k such directional antennae whose range differs from the optimal range by a multiplicative factor of at most 2·sin (π/k+1). Moreover, given a minimum spanning tree on the set of points the spanner can be constructed in additional O(n) time. In addition, we prove NP completeness results for k = 2 antennae.

, , , , ,
School of Computer Science

Dobrev, S. (Stefan), Kranakis, E, Krizanc, D. (Danny), Opatrny, J. (Jaroslav), Ponce, O.M. (Oscar Morales), & Stacho, L. (Ladislav). (2010). Strong connectivity in sensor networks with given number of directional antennae of bounded angle. doi:10.1007/978-3-642-17461-2_6