Title | ||
---|---|---|
Strong connectivity in sensor networks with given number of directional antennae of bounded angle |
Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1007/978-3-642-17461-2_6 | Discrete Mathematics, Algorithms and Applications |
Keywords | DocType | Volume |
optimal range,additional o,multiplicative factor,n sensor,directional antenna,sensor network,strong connectivity,bounded angle,np completeness result,minimum spanning tree,antenna,sensors,spanner,ad hoc network,strongly connected | Journal | 4 |
Issue | ISSN | ISBN |
3 | 1793-8309 | 3-642-17460-4 |
Citations | PageRank | References |
13 | 0.85 | 13 |
Authors | ||
6 |
Name | Order | Citations | PageRank |
---|---|---|---|
Stefan Dobrev | 1 | 528 | 41.68 |
Evangelos Kranakis | 2 | 3107 | 354.48 |
Danny Krizanc | 3 | 1778 | 191.04 |
Jaroslav Opatrny | 4 | 481 | 44.39 |
Oscar Morales Ponce | 5 | 52 | 9.46 |
Ladislav Stacho | 6 | 259 | 35.64 |