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.
- NSF 0728909, amount $91,942 (2007-2010).
Villanova students involved in this project
Publications resulted from this project
- 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.
- 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.
- Mirela Damian and Robin Flatland. "Connectivity of Graphs Induced by Directional Antennas". In Computing Research Repository, 2010.
- 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.
- 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.
- Mirela Damian and Nagesh Javali*. "Distributed Construction of Low-Interference Spanners". In Distributed Computing, vol. 22, no. 1, p.15-28, April 2009.
- 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.
- 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.
- Mirela Damian, "A Simple Yao-Yao-Based Spanner of Bounded Degree". In Computing Research Repository, CG ArXiv, arxiv.org/abs/0802.4325, 2008.
- 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