@conference {17564, title = {Approximation algorithms for throughput maximization in wireless networks with delay constraints}, booktitle = {2011 Proceedings IEEE INFOCOM}, year = {2011}, month = {2011/04/10/15}, pages = {1116 - 1124}, publisher = {IEEE}, organization = {IEEE}, abstract = {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.}, keywords = {Approximation algorithms, Approximation methods, approximation theory, Delay, delay constraints, delays, general interference model, Interference, multihop wireless networks, optimisation, Optimized production technology, radio networks, radiofrequency interference, target delay bound, Throughput, throughput maximization, Wireless networks}, isbn = {978-1-4244-9919-9}, doi = {10.1109/INFCOM.2011.5934887}, author = {Guanhong Pei and Anil Kumar,V. S and Parthasarathy,S. and Srinivasan, Aravind} } @conference {17585, title = {Distributed Strategies for Channel Allocation and Scheduling in Software-Defined Radio Networks}, booktitle = {IEEE INFOCOM 2009}, year = {2009}, month = {2009/04/19/25}, pages = {1521 - 1529}, publisher = {IEEE}, organization = {IEEE}, abstract = {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{\textquoteright} 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.}, keywords = {access hash function, Channel allocation, channel assignment algorithm, channel capacity, collision avoidance, Computer science, cryptography, distributed algorithm, distributed algorithms, Educational institutions, inductive-scheduling technique, Interference, interference set, packet scheduling algorithm, Peer to peer computing, Radio network, radio networks, radiofrequency interference, random oracle methodology, scheduling, Scheduling algorithm, simultaneous channel allocation, software radio, software-defined radio wireless network capacity, telecommunication congestion control, telecommunication security, Throughput, wireless channels, Wireless networks}, isbn = {978-1-4244-3512-8}, doi = {10.1109/INFCOM.2009.5062069}, author = {Han,Bo and Kumar,V. S.A and Marathe,M. V and Parthasarathy,S. and Srinivasan, Aravind} } @conference {17559, title = {Approximation Algorithms for Computing Capacity of Wireless Networks with SINR Constraints}, booktitle = {IEEE INFOCOM 2008. The 27th Conference on Computer Communications}, year = {2008}, month = {2008/04/13/18}, pages = {1166 - 1174}, publisher = {IEEE}, organization = {IEEE}, abstract = {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.}, keywords = {Algorithm design and analysis, approximation algorithm, Approximation algorithms, approximation theory, Computer networks, Computer science, graph theory, graph-based model, Interference constraints, polynomial time algorithm, Propagation losses, Protocols, radio networks, radiofrequency interference, signal to interference plus noise ratio, Signal to noise ratio, Throughput, wireless interference, wireless network, Wireless networks}, isbn = {978-1-4244-2025-4}, doi = {10.1109/INFOCOM.2008.172}, author = {Chafekar,D. and Kumart,V. S.A and Marathe,M. V and Parthasarathy,S. and Srinivasan, Aravind} }