Mirela Damian

Professor of Computer Science

Villanova University

Proximity Structures for Wireless Communication

The main objective of this research project is to develop effcient algorithmic methods for building various proximity structures that lie at the heart of wireless network communication. Examples include quality spanners serving as virtual backbones for routing in wireless networks, dominating set-based structures supporting fault-tolerance and scheduling for energy savings, and clusterings aimed at conserving bandwidth and energy.

This project involves understanding the behavior and combinatorial complexity of proximity structures for various network models, developing efficient local constructions, and handling dynamic updates efficiently.

Images produced by Nagesh Javali as illustrations of wireless communication structures.

Research Support

Villanova students involved in this project

Nagesh Javali Graduate: link
Worked on this project throughout the 2007-2008 academic year. His primary focus was on constructing wireless network topologies with minimum interference. He developed a novel distributed method for constructing a low-interference light spanner of constant maximum degree for wireless ad-hoc networks modeled as quasi-unit disk graphs
Nawar Molla Graduate
Worked on this project throughout the 2008-2009 academic year. She investigated the problem of channel assignment for interference reduction in wireless networks, and separately the spanning property of the class of Yao graphs defined by the four standard quadrants. She developed a positive result for the special case of points in convex position.
Kory Kirk Undergraduate
Worked on this project throughout the 2008-2009 academic year. He developed a highly-interactive, distributed network simulator, which he used to investigate upper bounds on the spanning ratio of two well-known structures, namely the Delaunay triangulation and the Sparse Neighborhood graph, on a random point set.
Abhaykumar Kumbhar Graduate
Worked on this project throughout the 2009-2010 academic year. He conducted an experimental analysis of the connectivity of the Yao graph Y3 defined by three quadrants, under arbitrary cone orientations. He derived lower and upper bounds on the minimum antenna radius required to establish weak connectivity of Y3.
Kristin Raudonis Undergraduate / Graduate
Worked on this project throughout her undergraduate academic year 2009-2010 and graduate academic year 2010-2011. She proved that the Yao graph Y6 defined by six cones is a spanner.
Jenny Liang Undergraduate
Started working in 2010 on developing software for interactive visualization of communication graphs for wireless networks and embedding algorithms derived from this project. Her further efforts in 2011 were funded by the Collaborative Research Experience for Undergraduates program.
Lauren McDermott Undergraduate
Started working in 2010 on developing software for interactive visualization of communication graphs for wireless networks and embedding algorithms derived from this project. Her further efforts in 2011 were funded by the Collaborative Research Experience for Undergraduates program.
Research Class Undergraduate
Five undergraduate students enrolled in the research seminar in the fall semesters of 2007 and 2008 invesigated various aspects of this project.

Publications resulted from this project

  1. Mirela Damian and Kristin Raudonis*. "Yao Graphs Span Theta Graphs". In Proc. of the International Conference on Combinatorial Optimization and Applications, COCOA'10, pages 181-194, Berlin, Heidelberg, December 2010. A revised version appeared later in Discrete Mathematics, Algorithms and Applications, vol. 4(2), p. 181-194, June 2012.
  2. Prosenjit Bose, Mirela Damian, Karim Douieb*, Joseph O'Rourke, Ben Seamone*, Michiel Smid and Stefanie Wuhrer*. "Pi/2-Angle Yao Graphs are Spanners. In Proc. of the International Symposium on Algorithms and Computation, vol. 6507, p. 446-457, 2010.
  3. Mirela Damian and Robin Flatland. "Connectivity of Graphs Induced by Directional Antennas". In Computing Research Repository, 2010.
  4. Mirela Damian and Sriram Pemmaraju. "Localized Spanners for Wireless Networks". In Ad Hoc & Wireless Sensor Networks, vol. 9, no.3-4, p.305-328, April 2010.
  5. Brad Ballinger, Nadia Benbernou*, Prosenjit Bose, Mirela Damian, Erik Demaine, Vida Dujmovic, Robin Flatland, Ferran Hurtado, John Iacono, Anna Lubiw, Pat Morin, Vera Sacristan, Diane Souvaine, Ryuhei Uehara. "Coverage with k-Transmitters in the Presence of Obstacles". In Proc. of the International Conference on Combinatorial Optimization and Applications, COCOA'10, pages 1-15, Berlin, Heidelberg, December 2010.
  6. Mirela Damian and Nagesh Javali*. "Distributed Construction of Low-Interference Spanners". In Distributed Computing, vol. 22, no. 1, p.15-28, April 2009.
  7. Mirela Damian, Nawar Molla* and Val Pinciu. "Spanner Properties of Pi/2-Angle Yao Graphs". In Proc. of the 25th European Workshop on Computational Geometry, EuroCG'09, p. 21-24, Brussels, Belgium, March 2009.
  8. Mirela Damian and Nagesh Javali*. "Bounded-Degree Low-Interference Spanners for Wireless Ad-Hoc Networks". In Proc. of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc'08, p. 101--110, Hong Kong, China, May 26-30, 2008.
  9. Mirela Damian, "A Simple Yao-Yao-Based Spanner of Bounded Degree". In Computing Research Repository, CG ArXiv, arxiv.org/abs/0802.4325, 2008.
  10. Mirela Damian, Robin Flatland, Joseph O'Rourke and Suneeta Ramaswami.. "A New Lower Bound on Guard Placement for Wireless Localization". In Proc. of the 17th Fall Workshop on Computational Geometry, 2007.

* denotes student