TUTORIAL
Computing with Directional Antennae in WSNs
By
Evangelos Kranakis
Carleton University Schools of Computer Science
(ICDCN, Jan 03, 2012)
Scope: Directional and omnidirectional are the two types of antennae being used in sensor networking. The former emit greater power in one direction thus achieving increased transmission range and performance as well as reduced interference from unwanted sources. On the contrary, omnidirectional antennae radiate power uniformly in all directions. Regardless of the type of antenna being used the transmission cost of each antenna is proportional to the coverage area of the antenna. By providing a comparative analysis of directional vs omnidirectional antennae the purpose of the tutorial is to understand how the use of directional antennae can improve energy consumption, security, and topology control. We introduce basic concepts and ideas for 2D and 3D antennae and look at topology control with directional antennae, e.g., connectivity, neighbor discovery, coverage, routing, and stretch factor. We discuss and analyze several recent algorithms and study trade-offs on the beam width, range and number of antennae being used per sensor. We also provide directions for future research and give several challenging recent open problems.
Slides for the Tutorial (in pdf)
You have two options: either you can download all the slides in a single file or in multiple files per topic. (Updated Dec 29, 2011)
Two Main Antenna Orientation Papers
  1. I. Caragiannis, C. Kaklamanis, E. Kranakis, D. Krizanc, A. Wiese, Communication in Wireless Networks with Directional Antennae. In proceedings of 20th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'08), pp. 344-351, Munich, Germany June 14 - 16, 2008. ACM Press. (download)
    First paper on for orientation algorithms connectivity with one directional antenna per sensor.
  2. E. Kranakis, D. Krizanc, O. Morales. Maintaining Connectivity in Sensor Networks Using Directional Antennae. Chapter 4, pages 59-84. In Theoretical Aspects of Distributed Computing in Sensor Networks, S. Nikoletseas and J. Rolim, editors, Springer, ISBN 978-3-642-14848-4. (download)
    Survey paper on orientation algorithms for connectivity with directional antennae.
    Other Antenna Orientation Papers
  3. E. Kranakis, D. Krizanc, A. Modi, O. Morales Ponce. Connectivity Trade-offs in 3D Wireless Sensor Networks Using Directional Antennae. In proceedings of IPDPS 2011, May 16-20, 2011 Anchorage (Alaska). IEEE Press. (download)
    Orientation algorithms for connectivity in 3D with one directional antennae per sensor.
  4. B. Bhattacharya, Y. Hu, E. Kranakis, D. Krizanc, Q. Shi. Sensor Network Connectivity with Multiple Directional Antennae of a Given Angular Sum. In proceedings of 23rd IEEE International Parallel and Distributed Processing Symposium (IPDPS 2009), pp. 344-351, May 25-29, 2009, Rome, Italy. IEEE Press. (download)
    Orientation algorithms for minimizing the sum of angles for connectivity.
  5. S. Dobrev, E. Kranakis, O. Morales Ponce, M. Plzik. Robust Sensor Range for Constructing Strongly Connected Spanning Digraphs in UDGs. (download)
    Optimal orientation algorithms for connectivity with four antennae.
  6. S. Dobrev, E. Kranakis, D. Krizanc, O. Morales Ponce, J. Opatrny, L. Stacho. Strong Connectivity in Sensor Networks with Given Number of Directional Antennae of Bounded Angle. In proceedings of 4th annual International Conference on Combinatorial Optimization and Applications (COCOA'10). Big Island, Hawaii, Dec 18-20. COCOA 2010, Part II, LNCS 6509, pp. 72--86. Springer LNCS. (download)
    Approximation algorithms for orientating at most five antennae per sensor for connectivity.
  7. E. Kranakis, O. Morales Ponce, L. Stacho. Strong Orientations of Planar Graphs with Bounded Stretch Factor. In proceedings of 17th SIROCCO (Colloquium on Structural Information and Communication Complexity) 2010. B. Patt-Shamir, T. Ekim (Eds.), Sirince, Turkey, June 7-11, 2010. LNCS 6058 Springer. (download)
    Approximation algorithms on the total number of antennae for strong connectivity.
  8. J. Du, E. Kranakis, O. Morales Ponce, S. Rajsbaum, Neighbor Discovery in a Sensor Network with Directional Antennae. In proceedings of Algosensors 2011, Saarbruecken, Germany, September 08-09, 2011. (download)
    Neighbor discovery algorithms with one directional antennae per sensor.
    Related Papers and Ideas
  9. D. Bauer, H. Broersma, H., and E. Schmeichel, Toughness in graphs--a survey, Graphs and Combinatorics, 22, (1), 1--35, 2006. (download)
    Survey paper on graph toughness.
  10. P. Gupta and P.R. Kumar, The capacity of wireless networks, IEEE Trans. on Information Theory, vol. IT-46, no. 2, March 2000. (download)
    Classic paper on network capacity with omnidirectional antennae
  11. S. Yi, Y. Pei, S. Kalyanaraman, On the capacity improvement of ad hoc wireless networks using directional antennas, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, 2003. (download)
    Network Capacity with Directional Antennae
  12. L. Hui, D. Evans, Using directional antennas to prevent wormhole attacks Network and Distributed System Security Symposium, 2004. (download)
    Protocols to prevent wormhole attacks using directional antennae
  13. Reza Shokri, Marcin Poturalski, Gael Ravot, Panos Papadimitratos, and Jean-Pierre Hubaux. A Practical Secure Neighbor Verification Protocol for Wireless Sensor Networks Proceedings of the second ACM conference on Wireless network security, 2009 (download)
    Protocols for detecting wormhole attacks
  14. R. Maheshwari, J. Gao, Samir Das. Detecting wormhole attacks in wireless networks using connectivity information INFOCOM 2007 (download)
    Topology based protocols for detecting wormhole attacks