Select a calendar:
Filter July Events by Event Type:
SUNMONTUEWEDTHUFRISAT
Events for July 28, 2009
-
SINR Diagrams: Towards Algorithmically Usable SINR Models of Wireless Networks
Tue, Jul 28, 2009 @ 11:00 AM - 12:00 PM
Ming Hsieh Department of Electrical and Computer Engineering
Conferences, Lectures, & Seminars
Abstract:
The rules governing the availability and quality of connections in a wireless network are
described by physical models such as the signal-to-interference & noise ratio (SINR) model. For
a collection of simultaneously transmitting stations in the plane, it is possible to identify a
reception zone for each station, consisting of the points where its transmission is received
correctly. The resulting SINR diagram partitions the plane into a reception zone per station and
the remaining plane where no station can be heard. SINR diagrams appear to be fundamental to
understanding the behavior of wireless networks, and may play a key role in the development of
suitable algorithms for such networks, analogous perhaps to the role played by Voronoi diagrams
in the study of proximity queries and related issues in computational geometry. So far, however,
the properties of SINR diagrams have not been studied systematically, and most algorithmic
studies in wireless networking rely on simplified graph-based models such as the unit disk graph
(UDG) model, which conveniently abstract away interference-related complications, and make it
easier to handle algorithmic issues, but consequently fail to capture accurately some important
aspects of wireless networks. The current paper focuses on obtaining some basic understanding
of SINR diagrams, their properties and their usability in algorithmic applications. Specifically,
based on some algebraic properties of the polynomials defining the reception zones we show that
assuming uniform power transmissions, the reception zones are convex and relatively wellrounded.
These results are then used to develop an efficient approximation algorithm for a
fundamental point location problem in wireless networks.
To appear in PODC-09.
Joint work with: Yuval Emek, Erez Kantor, Zvi Lotker, David Peleg and Liam Roditty.
Bio:
Dr. Chen Avin received the B.Sc. degree in Communication Systems Engineering from Ben
Gurion University, Israel, in 2000. He received the M.S. and Ph.D. degrees in computer science
from the University of California, Los Angeles (UCLA) in 2003 and 2006 respectively.
He is now a Lecturer in the Department of Communication Systems Engineering at the Ben
Gurion University since October 2006. His current research interests are: Graphs and Networks
Algorithms, Sensor Networks, Random Graphs,Complex Systems and Random Walks.
Host: Bhaskar KrishnamachariLocation: Hughes Aircraft Electrical Engineering Center (EEB) - 248
Audiences: Everyone Is Invited
Contact: Rahul Jain
