The complexity of symmetric connectivity in directional wireless sensor networks

Tien Tran () and Dung T. Huynh ()
Additional contact information
Tien Tran: University of Texas at Dallas
Dung T. Huynh: University of Texas at Dallas

Journal of Combinatorial Optimization, 2020, vol. 39, issue 3, No 2, 662-686

Abstract: Abstract In this paper, we investigate the Antenna Orientation (AO) and Antenna Orientation and Power Assignment (AOPA) problems concerning symmetric connectivity in Directional Wireless Sensor Networks (DWSNs) where each sensor node is equipped with $$ 2 \le k \le 5$$2≤k≤5 directional antennas having beam-width $$\theta \ge 0$$θ≥0. The AO problem for DWSNs is closely related with the well-known Euclidean Degree-Bounded Minimum Bottleneck Spanning Tree (EBMBST) problem where different cases for the degree bound have been studied. While current works on DWSNs focus on solving each case of k ($$=2,3,4$$=2,3,4) separately, we propose a uniform approach for the AO problem that yields constant-factor approximation algorithms for the AO as well as the EBMBST problem where the degree bound is between 2 and 4. Our method achieves the same constant factors. For the AOPA problem, to the best of our knowledge, our paper provides the first results concerning this problem. We show that the problem is NP-hard when $$2 \le k \le 4$$2≤k≤4. We also establish the first constant-factor approximation algorithms for the problem. Finally, we perform some simulations to understand the practical performance of our algorithms.

Keywords: Wireless sensor network; Directional antenna; Symmetric connectivity; Algorithm; Complexity (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-019-00509-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:39:y:2020:i:3:d:10.1007_s10878-019-00509-8

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-019-00509-8

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().