Geometric Graphs for Directional Communication

This research project studies fundamental combinatorial, geometric, and graph-theoretical problems related to the design of wireless networks with directional antennas. The types of antennas used in wireless networks can be roughly divided into omnidirectional antennas, which emit in all directions, and directional antennas, which emit only within a given wedge, whose orientation and angle can be specified. Although the properties of omnidirectional networks are by now quite well understood mathematically, configuring directional antennas appropriately to form efficient communication graphs poses additional challenges. The goal is to maximize communication robustness and security while minimizing power consumption and interference. The technical focus of this research is determining theoretical and algorithmic relationships between antenna parameters (orientation, range, angle), and the structure of the induced communication graph (such as connectivity, fault tolerance, and spanning ratio). This research is supported by the NSF grant CCF-1218814 (2012-2017).

Publications resulted from this project (Villanova student names underlined):

  1. Mirela Damian and Naresh Nelavalli. "Improved Bounds on the Stretch Factor of Y4." In Computational Geometry Theory and Applications, 62(1):14-24, April 2017.

  2. Michiel Smid, Prosenjit Bose, Paz Carmi, Mirela Damian, Jean-Lou De Carufel, Darryl Hill, Anil Maheshwari and Yuyang Liu. "On the Stretch Factor of Convex Polyhedra whose Vertices are (Almost) on a Sphere." In Computational Geometry Theory and Applications, 7(1):444-472, 2016.

  3. Luis Barba, Prosenjit Bose, Mirela Damian, Rolf Fagerberg, Wah Loon Keng, Joseph O'Rourke, André van Renssen, Perouz Taslakian, Sander Verdonschot and Ge Xia. "New and Improved Spanning Ratios for Yao Graphs." In Computational Geometry Theory and Applications, 6(2):19-53, January 2015.

  4. Mirela Damian and Dumitru V. Voicu. "Spanning Properties of Theta-Theta Graphs." In Proc. of the 8th Int. Conference on Combinatorial Optimization and Applications, COCOA'14, LNCS 8881, pp. 216-230, December 2014.

  5. Luis Barba, Prosenjit Bose, Jean-Lou De Carufel, Mirela Damian, Rolf Fagerberg, André van Renssen, Perouz Taslakian and Sander Verdonschot. "Continuous Yao Graphs." In online Proc. of the 26th Canadian Conference on Computational Geometry, CCCG'14, Halifax, Nova Scotia, August 2014.

  6. Luis Barba, Prosenjit Bose, Mirela Damian, Rolf Fagerberg, Wah Loon Keng, Joseph O'Rourke, André van Renssen, Perouz Taslakian, Sander Verdonschot and Ge Xia. "New and Improved Spanning Ratios for Yao Graphs." In Proc. of the 30th Symposium on Computational Geometry, SoCG'14, Kyoto, Japan, June 2014.

  7. Prosenjit Bose, Paz Carmi, Mirela Damian, Robin Flatland, Matthew Katz and Anil Maheshwari. "Switching to Directional Antennas with Constant Increase in Radius and Hop Distance." In Algorithmica, 56(1):1-15, June 2014.

  8. Mirela Damian and Robin Flatland. "Spanning Properties of Graphs Induced by Directional Antennas." In Discrete Mathematics, Algorithms and Applications, 5(3):1-16, August 2013.

  9. Greg Aloupis, Mirela Damian, Robin Flatland, Matias Korman, Özgür Özkan, David Rappaport and Stefanie Wuhrer. "Establishing Strong Connectivity using Optimal Radius Half-Disk Antennas." In Computational Geometry Theory and Applications, 46(3):328-339, April 2013.

  10. Matthew Bauer and Mirela Damian. "An Infinite Class of Sparse-Yao Spanners." In Proc. of the 24th ACM-SIAM Symposium on Discrete Algorithms, SODA'13, pages 184-196, New Orleans, Louisiana, January 6-8, 2013.

Abstracts (student names underlined):

  1. Naresh Nelavalli and Mirela Damian. "Improved Bounds on the Stretch Factor of Yao Graphs." In Proc. of the Sigma Xi Student Research Poster Symposium, Villanova University, April 22, 2016.

  2. Kelly Gremban, Kelly O'Conor and Mirela Damian. "Spanning Properties of Theta Graphs." In Proc. of the Sigma Xi Student Research Poster Symposium, Villanova University, April 25, 2014.

  3. Mathura S. Srishar, Sreevidya Pothineni and Mirela Damian. "Wireless Connectivity under the Random Waypoint Mobility Model." In Proc. of the Sigma Xi Student Research Poster Symposium, Villanova University, April 26, 2013.

Software (student names underlined):

Past NSF Research Support