SINR diagrams and their application to interference cancellation

Speaker : Yoram Haddad
Jerusalem College of Technology and Ben-Gurion University
Date: 18/07/2012
Time: 2:00 pm - 3:00 pm
Location: LINCS Meeting Room 40


In this talk we will first present what a SINR diagram is and why it is important to the design of efficient algorithms for wireless networks. Then we will discuss the reception zones of a wireless network in the SINR model with receivers that employ interference cancellation (IC). IC is a recently developed technique that allows a receiver to decode interfering signals, and cancel them from the received signal in order to decode its intended message. We first derive the important topological properties of the reception zones and their relation to high-order Voronoi diagrams and other geometric objects. We then discuss the computational issues that arise when seeking an efficient description of the zones. Our main fundamental result states that although potentially there are exponentially many possible cancellation orderings, and as a result, reception zones, in fact there are much fewer nonempty such zones. We prove a linear bound (hence tight) on the number of zones and provide a polynomial time algorithm to describe the diagram. Moreover, we introduce a novel parameter, the Compactness Parameter, which influences the tightness of our bounds. We then utilize these properties to devise a logarithmic time algorithm to answer point-location queries for networks with IC.

This work was published in the Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’12).

Biography: Yoram Haddad received his BSc, Engineer diploma and MSc (Radiocommunications) from SUPELEC in 2004 and 2005, and his PhD in computer science and networks from Telecom ParisTech in 2010. Since 2010 he is a tenure-track senior lecturer (Assistant Professor) at the Jerusalem College of Technology (JCT) in Jerusalem, Israel. In parallel, since 2011 he is a post-doctoral research associate at the Ben- Gurion University (BGU) in Beer-Sheva, Israel. Yoram’s main research interests are in the area of Wireless Networks and Algorithms for networks. He is specifically interested in energy efficient wireless deployment, Femtocell, modeling of wireless networks, wireless application to Intelligent Transportation Systems (ITS) and more recently Wireless Software Defined Networks (SDN).