How Well Can Graphs Represent Wireless Interference?

A family of conflict graphs is proposed that is parameterized by a non-decreasing sub-linear function, and it is shown that with a judicious choice of functions, the graphs can capture feasibility with a cost of O(log* Δ), where Δ is the ratio between the longest and the shortest link length. Expand The Price of Local Power Control in Wireless Scheduling

The price of oblivious power for wireless scheduling, or the value of allowing unfettered power control, is resolved by representing interference by a conflict graph, which allows the application of graph-theoretic results for a variety of related problems, including the weighted capacity problem. Expand Universal Framework for Wireless Scheduling Problems

This work proposes the first framework for approximation algorithms in the physical model that addresses these questions in full, including rate control, and shows that the approximation obtained is provably the best possible for any conflict graph formulation. Expand On the Capacity of Oblivious Powers

A family of power assignments are shown, including the mean power assignment, which yield larger capacity than uniform and linear power assignments, for each network instance, and upper and lower bounds on the gap between optimal capacities using any power assignment in these communication models are shown. Expand On Some Bounds on the Optimum Schedule Length in the SINR Model

- Tigran Tonoyan
- Mathematics, Computer Science
- ALGOSENSORS
- 13 September 2012

The problem of wireless transmissions scheduling in the path-loss/SINR model is considered for different fixed power schemes and it is shown that the lower bound for the linear power scheme is tight, by presenting a constant-factor approximation algorithm. Expand Dynamic Adaptation in Wireless Networks Under Comprehensive Interference via Carrier Sense

A natural exponential backoff procedure to manage contention in a fading channel is analyzed, and it is shown that it attains a fast convergence, stabilizing contention from any state in logarithmic time. Expand Algorithms for Scheduling with Power Control in Wireless Networks

This work correct and complement one of recent papers on this theme, by giving approximation algorithms for scheduling with power control for the case, when the nodes of the network are located in a doubling metric space. Expand Wireless Link Capacity under Shadowing and Fading

This work considers the following basic link capacity problem in wireless networks, and treats this problem under stochastic shadowing under general distributions, bound the effects of shadowing on optimal capacity, and derive constant approximation algorithms. Expand Efficient randomized distributed coloring in CONGEST

This work presents a new randomized distributed vertex coloring algorithm for the standard CONGEST model, where the network is modeled as an n-node graph G, and where the nodes of G operate in synchronous communication rounds in which they can exchange O(logn)-bit messages over all the edges of G. Expand Comparing Schedules in the SINR and Conflict-Graph Models with Different Power Schemes

The theoretical gap between the schedule length in the SINR model and in the corresponding conflict-graph model is evaluated, and it is shown that this gap depends largely on the power scheme used and on the metric space where the network is located. Expand