Abstract
A network is k-connected if it remains connected after the removal of any kâ1 of its nodes. Assume that n sensors, modeled here as (omni)directional antennas, are dropped randomly and independently with the uniform distribution on the interior of a unit length segment or a unit square. We derive sufficient conditions on the beam width of directional antennas so that the energy consumption required to maintain k-connectivity of the resulting network of sensors is lower when using directional than when using omnidirectional antennas. Our theoretical bounds are shown by experiment to be accurate under most circumstances. For the case of directional antennae, we provide simple algorithms for setting up a k-connected network requiring low energy.
Research of the first author supported in part by NSERC (Natural Sciences and Engineering Research Council of Canada) and MITACS (Mathematics of Information Technology and Complex Systems) grants.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Agre, J., Clare, L.: An integrated architecture for cooperative sensing networks. IEEE Computer 33(5), 106â108 (2000)
Balanis, C.A.: Antenna Theory: Analysis and Design, 2nd edn. Wiley, New York (1997)
Braginsky, D., Estrin, D.: Rumor routing algorithm for sensor networks (2001), Available at http://lecs.cs.ucla.edu/strin/
Doherty, L., Ghaoui, L.E., Pister, K.S.J.: Convex position estimation in wireless sensor networks. In: Proceedings of IEEE Infocom, Anchorage, AK (April 2001)
Estrin, D., Govindan, R., Heidemann, J., Kumar, S.: Next Century Challenges: Scalable Coordination in Sensor Networks. In: Proc. 5th ACM/IEEE International Conference on Mobile Computing, MOBICOM 1999 (1999)
Goel, A., Rai, S., Krishnamachari, B.: Sharp Thresholds for Monotone Properties in Random Geometric Graphs. Stanford University (2003) (manuscript)
Gupta, P., Kumar, P.R.: Critical Power for Asymptotic Connectivity in Wireless Networks. In: Stochastic Analysis, Control, Optimization, and Applications, Birkhauser, Basel (1998)
Kahn, J.M., Katz, R.H., Pister, K.S.J.: Mobile networking for smart dust. In: Proceedings of MobiCom 1999, Seattle, WA (August 1999)
Ko, Y.B., Shankarkumar, V., Vaidya, N.H.: Medium access control protocols using directional antennas in ad-hoc networks. In: Proc. IEEE INFOCOM 2000 (March 2000)
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)
Meguerdichian, S., Koushanfar, F., Potkonjak, M., Srivastava, M.: Coverage problems in wireless ad-hoc sensor networks. In: Proceedings of IEEE Infocom, Anchorage, AK (2001)
Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)
Nasipuri, A., Ye, S., You, J., Hiromoto, R.E.: A MAC protocol for mobile ad hoc networks using directional antennas. In: Proc. IEEE Wireless Communications and Networking Conference, WCNC 2000 (2000)
National Research Council, Embedded, Everywhere: A Research Agenda for Systems of Embedded Computers, Committee on Networked Systems of Embedded Computers, for the Computer Science and Telecommunications Board, Division on Engineering and Physical Sciences, Washington, DC (2001)
Penrose, M.D.: On k-Connectivity for a Geometric Random Graph. Random Structures and Algorithms 15, 145â164 (1999)
Penrose, M.D.: The Longest Edge of the Random Minimal Spanning Tree. The Annals of Applied Probability 7(2), 340â361 (1997)
Penrose, M.D.: Random Geometric Graphs. Oxford University Press, Oxford (2003)
Ramanathan, R.: On the Performance of Ad Hoc Networks with Beamforming Antennas. In: The Proceedings of ACM Symposium on Mobile Ad hoc Networking and Computing, MobiHoc 2001 (2001)
Santi, P., Blough, D.: The Critical Transmitting Range for Connectivity in Sparse Wireless Ad Hoc Networks. IEEE Transactions on Mobile Computing (to appear)
Shakkottai, S., Srikant, R., Shroff, N.: Unreliable Sensor Grids: Coverage, Connectivity and Diameter. In: Proceedings of IEEE INFOCOM 2003, San Francisco, March 30 to April 2 (2003)
Sohrabi, K., Gao, J., Ailawadhi, V., Pottie, G.: Protocols for self- organization of a wireless sensor network. IEEE Personal Communications 7, 16â27 (2000)
Spyropoulos, A., Raghavendra, C.S.: Energy Efficient Communications in Ad Hoc Networks Using Directional Antennas. In: proceedings of INFOCOM 2002, New York, June 23-27 (2002)
Wan, P.-J., Yi, C.-W.: Asymptotic Critical Transmission Radius and Critical Neighbor Number for k-connectivity in Wireless Ad Hoc Networks. Mobihoc (2004) (to appear)
Warneke, B., Last, M., Leibowitz, B., Pister, K.: SmartDust: communicating with a cubic-millimeter computer. IEEE Computer 34(1), 44â51 (2001)
Ye, W., Heidemann, J., Estrin, D.: An energy-efficient MAC protocol for wireless sensor networks. In: Proceedings of IEEE Infocom, New York, NY (June 2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
Âİ 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kranakis, E., Krizanc, D., Williams, E. (2005). Directional Versus Omnidirectional Antennas for Energy Consumption and k-Connectivity of Networks of Sensors. In: Higashino, T. (eds) Principles of Distributed Systems. OPODIS 2004. Lecture Notes in Computer Science, vol 3544. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11516798_26
Download citation
DOI: https://doi.org/10.1007/11516798_26
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-27324-0
Online ISBN: 978-3-540-31584-1
eBook Packages: Computer ScienceComputer Science (R0)