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 \cdot \sin(\frac{\pi}{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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bao, L., Garcia-Luna-Aceves, J.J.: Transmission scheduling in ad hoc networks with directional antennas. In: Proceedings of the 8th Annual International Conference on Mobile Computing and Networking, pp. 48–58 (2002)
Bhattacharya, B., Hu, Y., Kranakis, E., Krizanc, D., Shi, Q.: Sensor Network Connectivity with Multiple Directional Antennae of a Given Angular Sum. In: 23rd IEEE IPDPS 2009, May 25-29 (2009)
Calamoneri, T., Petreschi, R.: An Efficient Orthogonal Grid Drawing Algorithm For Cubic Graphs. In: Li, M., Du, D.-Z. (eds.) COCOON 1995. LNCS, vol. 959, pp. 31–40. Springer, Heidelberg (1995)
Caragiannis, I., Kaklamanis, C., Kranakis, E., Krizanc, D., Wiese, A.: Communication in Wireless Networks with Directional Antennae. In: Proceedings of 20th ACM SPAA, Munich, Germany, June 14-16 (2008)
Francke, A., Hoffmann, M.: The Euclidean degree-4 minimum spanning tree problem is NP-hard. In: Proceedings of the 25th Annual Symposium on Computational Geometry, pp. 179–188. ACM, New York (2009)
Gupta, P., Kumar, P.R.: The Capacity of Wireless Networks. IEEE Transactions on Information Theory 46(2), 388–404 (2000)
Khuller, S., Raghavachari, B., Young, N.: Balancing minimum spanning trees and shortest-path trees. Algorithmica 14(4), 305–321 (1995)
Kranakis, E., Krizanc, D., Urrutia, J.: Coverage and Connectivity in Networks with Directional Sensors. In: Danelutto, M., Vanneschi, M., Laforenza, D. (eds.) Euro-Par 2004. LNCS, vol. 3149, pp. 917–924. Springer, Heidelberg (2004)
Kranakis, E., Krizanc, D., Williams, E.: Directional versus omnidirectional antennas for energy consumption and k-connectivity of networks of sensors. In: Higashino, T. (ed.) OPODIS 2004. LNCS, vol. 3544, pp. 357–368. Springer, Heidelberg (2004)
Parker, R.G., Rardin, R.L.: Guaranteed performance heuristics for the bottleneck traveling salesman problem. Oper. Res. Lett. 2(6), 269–272 (1984)
Ramanathan, R.: On the Performance of Ad Hoc Networks with Beamforming Antennas. In: Proceedings of the 2nd ACM International Symposium on Mobile Ad Hoc Networking & Computing, pp. 95–105 (2001)
Spyropoulos, A., Raghavendra, C.S.: Energy efficient communications in ad hoc networks using directional antennas. In: Proceedings of the Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies, INFOCOM 2002, vol. 1. IEEE, Los Alamitos (2002)
Spyropoulos, A., Raghavendra, C.S.: Capacity Bounds for Ad-Hoc Networks Using Directional Antennas. In: IEEE International Conference on Communications, ICC 2003, vol. 1 (2003)
Yi, S., Pei, Y., Kalyanaraman, S.: On the capacity improvement of ad hoc wireless networks using directional antennas. In: Proceedings of the 4th ACM International Symposium on Mobile Ad hoc Networking & Computing, pp. 108–116 (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dobrev, S., Kranakis, E., Krizanc, D., Opatrny, J., Ponce, O.M., Stacho, L. (2010). Strong Connectivity in Sensor Networks with Given Number of Directional Antennae of Bounded Angle. In: Wu, W., Daescu, O. (eds) Combinatorial Optimization and Applications. COCOA 2010. Lecture Notes in Computer Science, vol 6509. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-17461-2_6
Download citation
DOI: https://doi.org/10.1007/978-3-642-17461-2_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-17460-5
Online ISBN: 978-3-642-17461-2
eBook Packages: Computer ScienceComputer Science (R0)