Improved algorithms in directional wireless sensor networks. (English) Zbl 1519.90050
Summary: Recent advances in wireless sensor networks (WSNs) allow directional antennas to be used instead of omni-directional antennas. However, the problem of maintaining (symmetric) connectivity in directional wireless sensor networks is significantly harder. Contributing to this field of research, in this paper, we study two problems in WSNs equipped with \(k\) directional antennas \((3 \leq k \leq 4)\). The first problem, called antenna orientation (AO) is that given a set \(S\) of nodes equipped with omni-directional antennas of unit range, the goal is to replace omni-directional antennas by directional antennas with beam-width \(\theta \geq 0\) and to find a way to orient them such that the required range to yield a symmetric connected communication graph (SCCG) is minimized. For this problem, we propose an \(O(n \log n)\) time algorithm yielding \(r = 2\sin (\frac{180^\circ}{k})\). The second problem, called antenna orientation and power assignment (AOPA) is to determine for each node \(u\) an orientation of its antennas and a range \(r_u\) in order to induce an SCCG such that the total power assignment \(\sum_u r_u^\beta\) is minimized, where \(\beta\) is a distant-power gradient. We show that our solution for the AO problem also induces an \(O(1)\)-approximation algorithm for the AOPA problem. Simulation results demonstrate that our algorithms have better performance than previous approaches, especially in case \(k = 3\).
MSC:
| 90B18 | Communication networks in operations research |
| 68M10 | Network design and communication in computer systems |
References:
| [1] | Andersen, PJ; Ras, CJ, Minimum bottleneck spanning trees with degree bounds, Networks, 68, 4, 302-314 (2016) · Zbl 1390.90088 · doi:10.1002/net.21710 |
| [2] | Aschner, R.; Katz, MJ, Bounded-angle spanning tree: modeling networks with angular constraints, Algorithmica, 77, 2, 349-373 (2017) · Zbl 1359.68229 · doi:10.1007/s00453-015-0076-9 |
| [3] | Aschner R, Katz MJ, Morgenstern G (2012) Do directional antennas facilitate in reducing interferences? In: Scandinavian workshop on algorithm theory. Springer, pp 201-212 · Zbl 1357.94005 |
| [4] | Aschner, R.; Katz, MJ; Morgenstern, G., Symmetric connectivity with directional antennas, Comput Geom, 46, 9, 1017-1026 (2013) · Zbl 1272.78014 · doi:10.1016/j.comgeo.2013.06.003 |
| [5] | Bhattacharya B, Hu Y, Shi Q, Kranakis E, Krizanc D (2009) Sensor network connectivity with multiple directional antennae of a given angular sum. In: 2009 IEEE international symposium on parallel and distributed processing. IEEE, pp 1-11 |
| [6] | Biniaz A (2020) Euclidean bottleneck bounded-degree spanning tree ratios. In: Proceedings of the fourteenth annual ACM-SIAM symposium on discrete algorithms. SIAM, pp 826-836 · Zbl 07304073 |
| [7] | Calinescu, G.; Wan, PJ, Range assignment for biconnectivity and k-edge connectivity in wireless ad hoc networks, Mob Netw Appl, 11, 2, 121-128 (2006) · doi:10.1007/s11036-006-4466-8 |
| [8] | Calinescu G, Kapoor S, Olshevsky A, Zelikovsky A (2003) Network lifetime and power assignment in ad hoc wireless networks. In: European symposium on algorithms. Springer, pp 114-126 · Zbl 1266.68022 |
| [9] | Caragiannis, I.; Kaklamanis, C.; Kanellopoulos, P., Energy-efficient wireless network design, Theory Comput Syst, 39, 5, 593-617 (2006) · Zbl 1100.68505 · doi:10.1007/s00224-005-1204-8 |
| [10] | Caragiannis I, Kaklamanis C, Kranakis E, Krizanc D, Wiese A (2008) Communication in wireless networks with directional antennas. In: Proceedings of the twentieth annual symposium on parallelism in algorithms and architectures, pp 344-351 |
| [11] | Carmi, P.; Katz, MJ; Lotker, Z.; Rosén, A., Connectivity guarantees for wireless networks with directional antennas, Comput Geom, 44, 9, 477-485 (2011) · Zbl 1233.05123 · doi:10.1016/j.comgeo.2011.05.003 |
| [12] | Dobrev, S.; Kranakis, E.; Krizanc, D.; Opatrny, J.; Ponce, OM; Stacho, L., Strong connectivity in sensor networks with given number of directional antennae of bounded angle, Discrete Math Algorithms Appl, 4, 3, 1250038 (2012) · Zbl 1253.68031 · doi:10.1142/S1793830912500383 |
| [13] | Kirousis, LM; Kranakis, E.; Krizanc, D.; Pelc, A., Power consumption in packet radio networks, Theor Comput Sci, 243, 1-2, 289-305 (2000) · Zbl 0944.68001 · doi:10.1016/S0304-3975(98)00223-0 |
| [14] | Kranakis, E.; MacQuarrie, F.; Ponce, OM, Connectivity and stretch factor trade-offs in wireless sensor networks with directional antennae, Theor Comput Sci, 590, 55-72 (2015) · Zbl 1327.68178 · doi:10.1016/j.tcs.2015.04.035 |
| [15] | Lam TD, Huynh DT (2022) Improved algorithms in directional wireless sensor networks. In: 2022 IEEE wireless communications and networking conference (WCNC). IEEE, pp 2352-2357 |
| [16] | Lam NX, Nguyen TN, An MK, Huynh DT (2011) Dual power assignment optimization for k-edge connectivity in WSNs. 2011 8th Annual IEEE communications society conference on sensor, mesh and ad hoc communications and networks. IEEE, pp 566-573 |
| [17] | Li L, Halpern JY, Bahl P, Wang YM, Wattenhofer R (2001) Analysis of a cone-based distributed topology control algorithm for wireless multi-hop networks. In: Proceedings of the twentieth annual ACM symposium on principles of distributed computing, pp 264-273 · Zbl 1333.68147 |
| [18] | Lloyd, EL; Liu, R.; Marathe, MV; Ramanathan, R.; Ravi, SS, Algorithmic aspects of topology control problems for ad hoc networks, Mob Netw Appl, 10, 1, 19-34 (2005) · doi:10.1023/B:MONE.0000048543.95178.f5 |
| [19] | Lloyd, EL; Liu, R.; Ravi, S., Approximating the minimum number of maximum power users in ad hoc networks, Mob Netw Appl, 11, 2, 129-142 (2006) · doi:10.1007/s11036-006-4467-7 |
| [20] | Monma, C.; Suri, S., Transitions in geometric minimum spanning trees, Discrete Comput Geom, 8, 3, 265-293 (1992) · Zbl 0764.05022 · doi:10.1007/BF02293049 |
| [21] | Papadimitriou, CH; Vazirani, UV, On two geometric problems related to the travelling salesman problem, J Algorithms, 5, 2, 231-246 (1984) · Zbl 0551.90093 · doi:10.1016/0196-6774(84)90029-4 |
| [22] | Tran T, Huynh DT (2018) Symmetric connectivity algorithms in multiple directional antennas wireless sensor networks. In: IEEE INFOCOM 2018-IEEE conference on computer communications. IEEE, pp 333-341 |
| [23] | Tran, T.; Huynh, DT, The complexity of symmetric connectivity in directional wireless sensor networks, J Comb Optim, 39, 3, 662-686 (2020) · Zbl 1441.90144 · doi:10.1007/s10878-019-00509-8 |
| [24] | Tran T, An MK, Huynh DT (2017a) Antenna orientation and range assignment algorithms in directional WSNs. IEEE/ACM Trans Network 25(6):3368-3381 |
| [25] | Tran T, An MK, Huynh DT (2017b) Symmetric connectivity in wsns equipped with multiple directional antennas. In: 2017 international conference on computing, networking and communications (ICNC). IEEE, pp 609-614 |
| [26] | Wang, C.; Willson, J.; Park, MA; Farago, A.; Wu, W., On dual power assignment optimization for biconnectivity, J Comb Optim, 19, 2, 174-183 (2010) · Zbl 1187.90239 · doi:10.1007/s10878-008-9173-x |
| [27] | Wu, W.; Du, H.; Jia, X.; Li, Y.; Huang, SCH, Minimum connected dominating sets and maximal independent sets in unit disk graphs, Theor Comput Sci, 352, 1-3, 1-7 (2006) · Zbl 1086.68107 · doi:10.1016/j.tcs.2005.08.037 |
| [28] | Ye D, Zhang H (2004) The range assignment problem in static ad-hoc networks on metric spaces. In: International colloquium on structural information and communication complexity. Springer, pp 291-302 · Zbl 1085.68526 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
