TY - CONF
T1 - Approximation algorithms for throughput maximization in wireless networks with delay constraints
T2 - 2011 Proceedings IEEE INFOCOM
Y1 - 2011
A1 - Guanhong Pei
A1 - Anil Kumar,V. S
A1 - Parthasarathy,S.
A1 - Srinivasan, Aravind
KW - Approximation algorithms
KW - Approximation methods
KW - approximation theory
KW - Delay
KW - delay constraints
KW - delays
KW - general interference model
KW - Interference
KW - multihop wireless networks
KW - optimisation
KW - Optimized production technology
KW - radio networks
KW - radiofrequency interference
KW - target delay bound
KW - Throughput
KW - throughput maximization
KW - Wireless networks
AB - We study the problem of throughput maximization in multi-hop wireless networks with end-to-end delay constraints for each session. This problem has received much attention starting with the work of Grossglauser and Tse (2002), and it has been shown that there is a significant tradeoff between the end-to-end delays and the total achievable rate. We develop algorithms to compute such tradeoffs with provable performance guarantees for arbitrary instances, with general interference models. Given a target delay-bound Δ(c) for each session c, our algorithm gives a stable flow vector with a total throughput within a factor of O (logΔm/log log Δm) of the maximum, so that the per-session (end-to-end) delay is O ((logΔm/log log Δm Δ(c))2), where Δm = maxc{Δ(c)}; note that these bounds depend only on the delays, and not on the network size, and this is the first such result, to our knowledge.
JA - 2011 Proceedings IEEE INFOCOM
PB - IEEE
SN - 978-1-4244-9919-9
M3 - 10.1109/INFCOM.2011.5934887
ER -
TY - CONF
T1 - Distributed Strategies for Channel Allocation and Scheduling in Software-Defined Radio Networks
T2 - IEEE INFOCOM 2009
Y1 - 2009
A1 - Han,Bo
A1 - Kumar,V. S.A
A1 - Marathe,M. V
A1 - Parthasarathy,S.
A1 - Srinivasan, Aravind
KW - access hash function
KW - Channel allocation
KW - channel assignment algorithm
KW - channel capacity
KW - collision avoidance
KW - Computer science
KW - cryptography
KW - distributed algorithm
KW - distributed algorithms
KW - Educational institutions
KW - inductive-scheduling technique
KW - Interference
KW - interference set
KW - packet scheduling algorithm
KW - Peer to peer computing
KW - Radio network
KW - radio networks
KW - radiofrequency interference
KW - random oracle methodology
KW - scheduling
KW - Scheduling algorithm
KW - simultaneous channel allocation
KW - software radio
KW - software-defined radio wireless network capacity
KW - telecommunication congestion control
KW - telecommunication security
KW - Throughput
KW - wireless channels
KW - Wireless networks
AB - Equipping wireless nodes with multiple radios can significantly increase the capacity of wireless networks, by making these radios simultaneously transmit over multiple non-overlapping channels. However, due to the limited number of radios and available orthogonal channels, designing efficient channel assignment and scheduling algorithms in such networks is a major challenge. In this paper, we present provably-good distributed algorithms for simultaneous channel allocation of individual links and packet-scheduling, in software-defined radio (SDR) wireless networks. Our distributed algorithms are very simple to implement, and do not require any coordination even among neighboring nodes. A novel access hash function or random oracle methodology is one of the key drivers of our results. With this access hash function, each radio can know the transmitters' decisions for links in its interference set for each time slot without introducing any extra communication overhead between them. Further, by utilizing the inductive-scheduling technique, each radio can also backoff appropriately to avoid collisions. Extensive simulations demonstrate that our bounds are valid in practice.
JA - IEEE INFOCOM 2009
PB - IEEE
SN - 978-1-4244-3512-8
M3 - 10.1109/INFCOM.2009.5062069
ER -
TY - CONF
T1 - Approximation Algorithms for Computing Capacity of Wireless Networks with SINR Constraints
T2 - IEEE INFOCOM 2008. The 27th Conference on Computer Communications
Y1 - 2008
A1 - Chafekar,D.
A1 - Kumart,V. S.A
A1 - Marathe,M. V
A1 - Parthasarathy,S.
A1 - Srinivasan, Aravind
KW - Algorithm design and analysis
KW - approximation algorithm
KW - Approximation algorithms
KW - approximation theory
KW - Computer networks
KW - Computer science
KW - graph theory
KW - graph-based model
KW - Interference constraints
KW - polynomial time algorithm
KW - Propagation losses
KW - Protocols
KW - radio networks
KW - radiofrequency interference
KW - signal to interference plus noise ratio
KW - Signal to noise ratio
KW - Throughput
KW - wireless interference
KW - wireless network
KW - Wireless networks
AB - A fundamental problem in wireless networks is to estimate its throughput capacity - given a set of wireless nodes, and a set of connections, what is the maximum rate at which data can be sent on these connections. Most of the research in this direction has focused on either random distributions of points, or has assumed simple graph-based models for wireless interference. In this paper, we study capacity estimation problem using the more general Signal to Interference Plus Noise Ratio (SINR) model for interference, on arbitrary wireless networks. The problem becomes much harder in this setting, because of the non-locality of the SINR model. Recent work by Moscibroda et al. (2006) has shown that the throughput in this model can differ from graph based models significantly. We develop polynomial time algorithms to provably approximate the total throughput in this setting.
JA - IEEE INFOCOM 2008. The 27th Conference on Computer Communications
PB - IEEE
SN - 978-1-4244-2025-4
M3 - 10.1109/INFOCOM.2008.172
ER -
TY - CONF
T1 - Capacity of Asynchronous Random-Access Scheduling in Wireless Networks
T2 - IEEE INFOCOM 2008. The 27th Conference on Computer Communications
Y1 - 2008
A1 - Chafekar,D.
A1 - Levin,D.
A1 - Kumar,V. S.A
A1 - Marathe,M. V
A1 - Parthasarathy,S.
A1 - Srinivasan, Aravind
KW - asynchronous random-access scheduling
KW - channel access probability
KW - Computer networks
KW - Computer science
KW - Educational institutions
KW - Interference
KW - Optimal scheduling
KW - Peer to peer computing
KW - probability
KW - Processor scheduling
KW - radio link
KW - radio links
KW - radio networks
KW - Routing
KW - scheduling
KW - Throughput
KW - throughput capacity
KW - wireless channels
KW - Wireless networks
AB - We study the throughput capacity of wireless networks which employ (asynchronous) random-access scheduling as opposed to deterministic scheduling. The central question we answer is: how should we set the channel-access probability for each link in the network so that the network operates close to its optimal throughput capacity? We design simple and distributed channel-access strategies for random-access networks which are provably competitive with respect to the optimal scheduling strategy, which is deterministic, centralized, and computationally infeasible. We show that the competitiveness of our strategies are nearly the best achievable via random-access scheduling, thus establishing fundamental limits on the performance of random- access. A notable outcome of our work is that random access compares well with deterministic scheduling when link transmission durations differ by small factors, and much worse otherwise. The distinguishing aspects of our work include modeling and rigorous analysis of asynchronous communication, asymmetry in link transmission durations, and hidden terminals under arbitrary link-conflict based wireless interference models.
JA - IEEE INFOCOM 2008. The 27th Conference on Computer Communications
PB - IEEE
SN - 978-1-4244-2025-4
M3 - 10.1109/INFOCOM.2008.170
ER -
TY - CONF
T1 - Reliable broadcast in radio networks: the bounded collision case
T2 - Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing
Y1 - 2006
A1 - Koo,Chiu-Yuen
A1 - Bhandari,Vartika
A1 - Katz, Jonathan
A1 - Vaidya,Nitin H.
KW - broadcast
KW - byzantine failure
KW - Fault tolerance
KW - radio networks
AB - We study the problem of achieving global broadcast in a radio network where a node can multicast messages to all of its neighbors (that is, nodes within some given distance r), and up to t nodes in any single neighborhood may be corrupted. Previous work assumes that corrupted nodes can neither cause collisions nor spoof addresses of honest nodes. In this work, we eliminate these assumptions and allow each faulty node to cause a (known) bounded number of collisions and spoof the addresses of arbitrary other nodes. We show that the maximum tolerable t in this case is identical to the maximum tolerable t when collisions and address spoofing are not allowed. Thus, by causing collisions and spoofing addresses an adversary may be able to degrade the efficiency of achieving broadcast, but it cannot affect the feasibility of this task.
JA - Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing
T3 - PODC '06
PB - ACM
CY - New York, NY, USA
SN - 1-59593-384-0
UR - http://doi.acm.org/10.1145/1146381.1146420
M3 - 10.1145/1146381.1146420
ER -