|
11:45 am, Lecture Hall 6 How Well Can Graphs Represent Wireless Interference? Magnus M. Halldorsson ICE-TCS, School of Computer Science, Reykjavik University. 14-12-15 Abstract From the early days of wireless networking research, graphs have commonly been used to model wireless communications and interference. Much theoretical work was done on simple range models, like Unit Disc Graphs. Unfortunately, such models were generally found to be quite far from the reality on the ground. This has led to sustained efforts in recent years to formulate and analyze algorithms in the SINR or physical model. Dealing with graphs is, however, more preferable, as it makes all analysis easier and allows for the transfer of a lot of well-explored theory. We re-examine how well graphs can capture wireless receptions as encoded in SINR relationships, placing them in a framework in order to understand the limits of such modelling. We propose a new type of conflict graphs and show that they come very close to capturing the SINR interference relationships. This leads to greatly improved approximation algorithm for a host of fundamental problems, including link scheduling and packet scheduling. The performance guarantees obtained are O(log* Delta), where Delta is the ratio between the longest and the shortest link length, improving on previous logarithmic factors. We show that this is tight: no conflict graph representation schema can guarantee a better than Omega(log* Delta)-approximation. We can view this a tight characterization on the "price" of using the simpler graph-based representation in the setting of wireless communication. This is joint work with Tigran Tonoyan.
|
