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 - JOUR
T1 - Maximum bipartite flow in networks with adaptive channel width
JF - Theoretical Computer Science
Y1 - 2011
A1 - Azar,Yossi
A1 - Mądry,Aleksander
A1 - Moscibroda,Thomas
A1 - Panigrahi,Debmalya
A1 - Srinivasan, Aravind
KW - Adaptive channel width
KW - graph algorithm
KW - Linear program rounding
KW - Maximum flow
KW - Wireless networks
AB - Traditionally, network optimization problems assume that each link in the network has a fixed capacity. Recent research in wireless networking has shown that it is possible to design networks where the capacity of the links can be changed adaptively to suit the needs of specific applications. In particular, one gets a choice of having a few high capacity outgoing links or many low capacity ones at any node of the network. This motivates us to have a re-look at classical network optimization problems and design algorithms to solve them in this new framework. In particular, we consider the problem of maximum bipartite flow, which has been studied extensively in the fixed-capacity network model. One of the motivations for studying this problem arises from the need to maximize the throughput of an infrastructure wireless network comprising base-stations (one set of vertices in the bipartition) and clients (the other set of vertices in the bipartition). We show that this problem has a significantly different combinatorial structure in this new network model from the fixed-capacity one. While there are several polynomial time algorithms for the maximum bipartite flow problem in traditional networks, we show that the problem is NP-hard in the new model. In fact, our proof extends to showing that the problem is APX-hard. We complement our lower bound by giving two algorithms for solving the problem approximately. The first algorithm is deterministic and achieves an approximation factor of O ( log N ) , where N is the number of nodes in the network, while the second algorithm is randomized and achieves an approximation factor of e e − 1 .
VL - 412
SN - 0304-3975
UR - http://www.sciencedirect.com/science/article/pii/S0304397510005852
CP - 24
M3 - 10.1016/j.tcs.2010.10.023
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 - Cross-layer latency minimization in wireless networks with SINR constraints
T2 - Proceedings of the 8th ACM international symposium on Mobile ad hoc networking and computing
Y1 - 2007
A1 - Chafekar,Deepti
A1 - Kumar,V. S. Anil
A1 - Marathe,Madhav V.
A1 - Parthasarathy,Srinivasan
A1 - Srinivasan, Aravind
KW - cross-layer design
KW - end-to-end scheduling
KW - Interference
KW - SINR model
KW - Wireless networks
AB - Recently, there has been substantial interest in the design of cross-layer protocols for wireless networks. These protocols optimize certain performance metric(s) of interest (e.g. latency, energy, rate) by jointly optimizing the performance of multiple layers of the protocol stack. Algorithm designers often use geometric-graph-theoretic models for radio interference to design such cross-layer protocols. In this paper we study the problem of designing cross-layer protocols for multi-hop wireless networks using a more realistic Signal to Interference plus Noise Ratio (SINR) model for radio interference. The following cross-layer latency minimization problem is studied: Given a set V of transceivers, and a set of source-destination pairs, (i) choose power levels for all the transceivers, (ii) choose routes for all connections, and (iii) construct an end-to-end schedule such that the SINR constraints are satisfied at each time step so as to minimize the make-span of the schedule (the time by which all packets have reached their respective destinations). We present a polynomial-time algorithm with provable worst-case performance guarantee for this cross-layer latency minimization problem. As corollaries of the algorithmic technique we show that a number of variants of the cross-layer latency minimization problem can also be approximated efficiently in polynomial time. Our work extends the results of Kumar et al. (Proc. SODA, 2004) and Moscibroda et al. (Proc. MOBIHOC, 2006). Although our algorithm considers multiple layers of the protocol stack, it can naturally be viewed as compositions of tasks specific to each layer --- this allows us to improve the overall performance while preserving the modularity of the layered structure.
JA - Proceedings of the 8th ACM international symposium on Mobile ad hoc networking and computing
T3 - MobiHoc '07
PB - ACM
CY - New York, NY, USA
SN - 978-1-59593-684-4
UR - http://doi.acm.org/10.1145/1288107.1288123
M3 - 10.1145/1288107.1288123
ER -
TY - JOUR
T1 - Wireless Network Security and Interworking
JF - Proceedings of the IEEE
Y1 - 2006
A1 - Shin,M.
A1 - Ma,J.
A1 - Mishra,A.
A1 - Arbaugh, William A.
KW - 3G mobile communication
KW - 3G systems
KW - Authentication
KW - Bandwidth
KW - Communication system security
KW - computer network security
KW - computer security
KW - Data security
KW - internetworking
KW - Land mobile radio cellular systems
KW - Paper technology
KW - security architectures
KW - security of data
KW - telecommunication security
KW - wireless communication
KW - wireless communications
KW - Wireless LAN
KW - wireless network security
KW - Wireless networks
KW - wireless technologies
KW - WLAN systems
AB - A variety of wireless technologies have been standardized and commercialized, but no single technology is considered the best because of different coverage and bandwidth limitations. Thus, interworking between heterogeneous wireless networks is extremely important for ubiquitous and high-performance wireless communications. Security in interworking is a major challenge due to the vastly different security architectures used within each network. The goal of this paper is twofold. First, we provide a comprehensive discussion of security problems and current technologies in 3G and WLAN systems. Second, we provide introductory discussions about the security problems in interworking, the state-of-the-art solutions, and open problems.
VL - 94
SN - 0018-9219
CP - 2
M3 - 10.1109/JPROC.2005.862322
ER -
TY - CONF
T1 - Algorithmic aspects of capacity in wireless networks
T2 - Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems
Y1 - 2005
A1 - Kumar,V. S. Anil
A1 - Marathe,Madhav V.
A1 - Parthasarathy,Srinivasan
A1 - Srinivasan, Aravind
KW - capacity modeling
KW - end-to-end scheduling
KW - Linear programming
KW - Wireless networks
AB - This paper considers two inter-related questions: (i) Given a wireless ad-hoc network and a collection of source-destination pairs {(si,ti)}, what is the maximum throughput capacity of the network, i.e. the rate at which data from the sources to their corresponding destinations can be transferred in the network? (ii) Can network protocols be designed that jointly route the packets and schedule transmissions at rates close to the maximum throughput capacity? Much of the earlier work focused on random instances and proved analytical lower and upper bounds on the maximum throughput capacity. Here, in contrast, we consider arbitrary wireless networks. Further, we study the algorithmic aspects of the above questions: the goal is to design provably good algorithms for arbitrary instances. We develop analytical performance evaluation models and distributed algorithms for routing and scheduling which incorporate fairness, energy and dilation (path-length) requirements and provide a unified framework for utilizing the network close to its maximum throughput capacity.Motivated by certain popular wireless protocols used in practice, we also explore "shortest-path like" path selection strategies which maximize the network throughput. The theoretical results naturally suggest an interesting class of congestion aware link metrics which can be directly plugged into several existing routing protocols such as AODV, DSR, etc. We complement the theoretical analysis with extensive simulations. The results indicate that routes obtained using our congestion aware link metrics consistently yield higher throughput than hop-count based shortest path metrics.
JA - Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems
T3 - SIGMETRICS '05
PB - ACM
CY - New York, NY, USA
SN - 1-59593-022-1
UR - http://doi.acm.org/10.1145/1064212.1064228
M3 - 10.1145/1064212.1064228
ER -
TY - JOUR
T1 - Proactive key distribution using neighbor graphs
JF - IEEE Wireless Communications
Y1 - 2004
A1 - Mishra,A.
A1 - Min Ho Shin
A1 - Petroni,N. L.
A1 - Clancy,T. C
A1 - Arbaugh, William A.
KW - access points
KW - Authentication
KW - authentication time
KW - Base stations
KW - Communication system security
KW - Delay
KW - graph theory
KW - GSM
KW - IEEE 802.11 handoff
KW - Land mobile radio cellular systems
KW - Message authentication
KW - mobile radio
KW - Multiaccess communication
KW - neighbor graph
KW - Network topology
KW - Roaming
KW - telecommunication security
KW - Telephone sets
KW - user mobility
KW - Wi-Fi networks
KW - wireless data networks
KW - Wireless LAN
KW - Wireless networks
AB - User mobility in wireless data networks is increasing because of technological advances, and the desire for voice and multimedia applications. These applications, however, require that handoffs between base stations (or access points) be fast to maintain the quality of the connections. In this article we introduce a novel data structure, the neighbor graph, that dynamically captures the mobility topology of a wireless network. We show how neighbor graphs can be utilized to obtain a 99 percent reduction in the authentication time of an IEEE 802.11 handoff (full EAP-TLS) by proactively distributing necessary key material one hop ahead of the mobile user. We also present a reactive method for fast authentication that requires only firmware changes to access points and hence can easily be deployed on existing wireless networks.
VL - 11
SN - 1536-1284
CP - 1
M3 - 10.1109/MWC.2004.1269714
ER -
TY - JOUR
T1 - The dangers of mitigating security design flaws: a wireless case study
JF - IEEE Security & Privacy
Y1 - 2003
A1 - Petroni,N. L.
A1 - Arbaugh, William A.
KW - Communication system security
KW - computer security
KW - cryptography
KW - design flaw mitigation
KW - Dictionaries
KW - legacy equipment
KW - privacy
KW - Protection
KW - Protocols
KW - security design flaws
KW - security of data
KW - synchronous active attack
KW - telecommunication security
KW - Telecommunication traffic
KW - wired equivalent privacy protocol
KW - Wireless LAN
KW - wireless local area networks
KW - Wireless networks
AB - Mitigating design flaws often provides the only means to protect legacy equipment, particularly in wireless local area networks. A synchronous active attack against the wired equivalent privacy protocol demonstrates how mitigating one flaw or attack can facilitate another.
VL - 1
SN - 1540-7993
CP - 1
M3 - 10.1109/MSECP.2003.1176993
ER -