Coordinated Science Laboratory
http://hdl.handle.net/2142/2303
Thu, 24 May 2018 14:09:39 GMT2018-05-24T14:09:39ZA Theory of QoS for Wireless
http://hdl.handle.net/2142/99609
A Theory of QoS for Wireless
Hou, I-Hong; Borkar, Vivek; Kumar, P.R.
Wireless networks are increasingly used to carry applications with QoS constraints. Two problems arise when dealing with traffic with QoS constraints. One is admission control, which consists of determining whether it is possible to fulfill the demands of a set of clients. The other is finding an optimal scheduling policy to meet the demands of all clients. In this paper, we propose a framework for jointly addressing three QoS criteria: end-to-end delay, delivery ratio, and channel reliability.
We analytically prove the necessary and sufficient condition for a set of clients to be feasible with respect to the above three criteria. We then establish an efficient algorithm for admission control to decide whether a set of clients is feasible. We further propose two scheduling policies and prove that they are feasibility optimal in the sense that they can meet the demands of every feasible set of clients. In addition, we show that these policies are easily implementable on the IEEE 802.11 mechanisms. We also present the results of simulation studies that appear to confirm the theoretical studies and suggest that the proposed policies outperform others tested under a variety of settings
Wireless networks; QoS for wireless; End-to-end delay; Delivery ratio; Channel reliability
Mon, 01 Sep 2008 00:00:00 GMThttp://hdl.handle.net/2142/996092008-09-01T00:00:00ZHou, I-HongBorkar, VivekKumar, P.R.Enforcing End-to-End Proportional Fairness with Bounded Buffer Overflow Probabilities
http://hdl.handle.net/2142/99608
Enforcing End-to-End Proportional Fairness with Bounded Buffer Overflow Probabilities
Singh, Nikhil; Sreenivas, Ramavarapu S.; Shanbhag, Uday V.
In this paper we present a distributed flow-based access scheme for slotted-time protocols, that provides proportional fairness in ad hoc wireless networks under constraints on the buffer overflow probabilities at each node. The proposed scheme requires local information exchange at the link-layer and end-to-end information exchange at the transport-layer, and is cast in the framework of nonlinear optimization. We say a medium access control protocol is proportionally fair with respect to individual end-to-end flows in a network, if the product of the end-to-end rates of flows is maximized. A key contribution of this work lies in the construction of a distributed dual approach that comes with low computational overhead. We discuss the convergence properties of the proposed scheme and present simulation results to support our conclusions.
Proportional fairness; Buffer overflow probabilities; Wireless LAN; Access protocols; Resource management
Fri, 01 Aug 2008 00:00:00 GMThttp://hdl.handle.net/2142/996082008-08-01T00:00:00ZSingh, NikhilSreenivas, Ramavarapu S.Shanbhag, Uday V.Dense Error Correction via l1-Minimization
http://hdl.handle.net/2142/99607
Dense Error Correction via l1-Minimization
Wright, John; Ma, Yi
In this paper, we study the problem of recovering a sparse signal x 2 Rn from highly corrupted linear measurements y = Ax+e 2 Rm, where e is an unknown error vector whose nonzero entries could be unbounded. Motivated by the problem of face recognition in computer vision, we will prove that if a signal has a sufficiently sparse representation with respect to a highly correlated dictionary A (either overcomplete or not), then with overwhelming probability, it can be recovered by solving the following l1-minimization problem: min kxk1 + kek1 subject to y = Ax + e; even for very dense e. More precisely, in this paper we prove that under the above conditions, for any _ < 1, as m goes to infinity, solving the above l1-minimization problem correctly recovers any sparse enough non-negative signal x from almost any error e with support size _ _m. This result suggests that accurate recovery of sparse signals is possible and computationally feasible even with errors asymptotically approaching 100%! The proof relies on a careful characterization of the neighborliness of a convex polytope spanned together by the standard cross polytope and a nonzero mean Gaussian ensemble with a small variance, which we call the “cross-and-bouquet” model. The high neighborliness of this polytope enables the striking error correction ability of the above l1-minimization. We will also show simulations and experimental results that corroborate our findings.
Sparse signal recovery; Dense error correction; l1-minimization; Gaussian random ensemble; Polytope neighborliness
Tue, 01 Jul 2008 00:00:00 GMThttp://hdl.handle.net/2142/996072008-07-01T00:00:00ZWright, JohnMa, YiERP: An Efficient and Reliable Protocol for Emergency Message Dissemination in Vehicular Ad Hoc Networks
http://hdl.handle.net/2142/99606
ERP: An Efficient and Reliable Protocol for Emergency Message Dissemination in Vehicular Ad Hoc Networks
Hou, I-Hong; Gao, Yan; Tsai, Yu-En; Hou, Jennifer
Many safety-related applications in Vehicular Ad Hoc Networks require fast and reliable emergency message dissemination through multi-hop broadcast. However, the conventional broadcast mechanism is neither efficient nor reliable because it results in serious contention and collisions, which is usually referred to as the broadcast storm problem. In this paper, we propose ERP, a two-phase broadcast protocol that improves both efficiency and reliability. The first phase, a “fast-propagation phase”, is designed to improve efficiency. We explicitly designate forwarders to relay the message and thus ensure both collision free and quick propagation. The second phase, a “loss recovery phase”, enhances reliability. In this phase, nodes overhear the message and repeatedly broadcast it for the benefit of nodes which have not received the message in the first phase. We analytically show that using a density-aware power control mechanism in the second phase can efficiently improve the recovery rate. We also demonstrate how to find the optimal transmission power. Simulation results illustrate that our protocol outperforms probabilistic forwarding, which is currently the most widely studied solution, by a factor of 2 to 3.
Vehicular ad hoc networks; Dissemination strategies; Emergency messaging; Power control
Thu, 01 May 2008 00:00:00 GMThttp://hdl.handle.net/2142/996062008-05-01T00:00:00ZHou, I-HongGao, YanTsai, Yu-EnHou, JenniferDelayed State Estimation in Discrete Event Systems and Applications to Security Problems
http://hdl.handle.net/2142/99605
Delayed State Estimation in Discrete Event Systems and Applications to Security Problems
Saboori, Anooshiravan; Hadjicostis, Christoforos N.
Application of discrete event systems in modeling and analyzing security problems has given rise to applications that require keeping track of (part of the) sequence of states that have been visited so far. Specifically, the notion of opacity requires that the truth of a certain predicate on the system state cannot be determined by an outside observer for the duration of a certain time window (or even at all times). Depending on the notion of opacity that is used, this predicate can be defined for states visited in the past (with no bound on how far into the past) or for states which have been visited a fixed number of observations in the past. In this report, motivated by such questions we introduce the problem of delayed estimation in discrete event systems modeled as a finite automaton with a finite number of states, unknown initial state, and partial event observation (but no state observation). Specifically, we consider two estimation problems: (i) initial state estimation which requires the estimate of the initial state following a sequence of observations and, (ii) K- delayed state estimation which requires the estimate of the state the system was in when it generated the Kth to last output (i.e., the state of the system K observations ago). To solve these two problems we construct appropriate state estimators and show that these delay state estimators can be used to verify opacity notions of interest.
Discrete event systems; State estimation; Automata; Security
Sat, 01 Mar 2008 00:00:00 GMThttp://hdl.handle.net/2142/996052008-03-01T00:00:00ZSaboori, AnooshiravanHadjicostis, Christoforos N.A Comparative Study of Duobinary and NRZ Modulation for High-Speed I/O
http://hdl.handle.net/2142/99604
A Comparative Study of Duobinary and NRZ Modulation for High-Speed I/O
Koh, Yee Lih
High-speed serial I/O links are limited in throughput due to intersymbol interference (ISI) and noise. At high data rates, on-board traces are bandlimited due to frequency dependent skin effect and dielectric losses. In order to analyze the effectiveness of using different modulation schemes in improving the reliability of serial links, we conduct a system level study to compare duobinary modulation with the traditional non-return-to-zero (NRZ) modulation scheme. The advantage presented by duobinary is that the modulation scheme only requires half the bandwidth required by NRZ. As a result, signal attenuation at high frequencies is avoided and noise enhancement is reduced. Nevertheless, the use of duobinary comes with a penalty at the receiver as the received signal consists of three signaling levels while NRZ has only two. Analytical results are presented to show when one scheme proves to be advantageous over the other. Comparisons for the modulation schemes are done across data rates using a measured 20-in FR4 channel, and across channel attenuations at 10 Gb/s. These comparisons are done using receive side equalization, comparing both modulation schemes using a linear equalizer as well as a decision feedback equalizer. In this thesis, we find that the advantages of utilizing duobinary appear at high data rates and high channel attenuation.
Backplane; Signaling; Duobinary; NRZ; I/O; Equalizer
Tue, 01 Jan 2008 00:00:00 GMThttp://hdl.handle.net/2142/996042008-01-01T00:00:00ZKoh, Yee LihCapacity-Approaching Practical Codes for Queueing Channels: An Algebraic, State-Space, Message-Passing Approach
http://hdl.handle.net/2142/99603
Capacity-Approaching Practical Codes for Queueing Channels: An Algebraic, State-Space, Message-Passing Approach
Coleman, Todd P.; Kiyavash, Negar
This report introduces a coding theory for queueing channels and discusses a practical capacity-approaching scheme. Here we consider a communication channel where the encoder communicates information based upon timings between successive packets. A receiver observes packet timings after they have traveled through a communication network with queues at intermediate router nodes. Based upon the encoding mechanism, the statistical structure of the network queues, and the packet timings it observes, the receiver finds the most likely bit sequence. Despite queueing system being nonlinear, non-stationary, and non-memoryless, Verdu and Anantharam provided a closed-form theoretical characterization of the maximum amount of information (i.e. capacity, in bits per second) that can be reliably communicated across a queue in their Information Theory Society Best Paper Award-Winning manuscript “Bits Through Queues”. However, to date, there has been a lack of practical ways to realize these theoretical possibilities. Indeed, the authors themselves claimed in 1998 that ‘Coding theory for queueing channels is virtually nonexistent.’ Here we introduce an architecture - based on algebraic codes, a state-space perspective on queues, and iterative message-passing on graphs – that is capacity-approaching and has low decoding complexity. To the best of the authors' knowledge, this is the first known such scheme.
Queueing theory; Information theory; Message-passing algorithms; Algebraic codes; State-space models
Wed, 01 Aug 2007 00:00:00 GMThttp://hdl.handle.net/2142/996032007-08-01T00:00:00ZColeman, Todd P.Kiyavash, NegarReliable Control of Multi-Agent Systems
http://hdl.handle.net/2142/99602
Reliable Control of Multi-Agent Systems
Al Hokayem, Peter Farid
In this dissertation we propose semiautonomous and autonomous solutions to multi-agent problems. We first utilize the concept of input-to-state stability to address the problem of semiautonomous control of multi-agent systems, and show that stability of the system is maintained in the presence of unreliable communication channels. We show that this result can be applied to specific cases such as bilateral one-to-one and one-to-many teleoperation. Then, we address the problem of collision avoidance in multi-agent systems using the concept of avoidance control, which provides provable guarantees for collision-free maneuvers. We show how these two approaches can be combined to render a viable solution to search and- rescue type missions. Finally, we propose an algorithmic and autonomous solution to the dynamic coverage and persistent coverage control problems and derive some bounds that characterize the performance of these algorithms with respect to completion time and communication demands.
Semi-autonomous multi-agent systems; Collision avoidance control; Coverage control
Sat, 01 Sep 2007 00:00:00 GMThttp://hdl.handle.net/2142/996022007-09-01T00:00:00ZAl Hokayem, Peter FaridLinear and Nonlinear Pricing for Network Games with Complete and Incomplete Information
http://hdl.handle.net/2142/99601
Linear and Nonlinear Pricing for Network Games with Complete and Incomplete Information
Shen, Hongxia
This dissertation addresses optimal linear and nonlinear pricing policy design for a monopolistic network service provider with various types of public and private information on user types. In the communication network pricing literature, it is the linear pricing schemes that have been largely adopted, and here we investigate both linear and nonlinear pricing within the framework of a hierarchical Stackelberg (leader-follower) game, where the service provider sets prices for the resources (bandwidth) he offers as the leader, and the users respond by their choices of the amount of bandwidth (flow) they are willing to pay for. At the lower level, the presence of congestion cost (negative network effect) in the net utility functions of users leads to a noncooperative game among themselves, with Nash or Bayesian equilibrium being natural candidates for a solution. In the nonlinear pricing case, the approach is to view the problem as a reverse Stackelberg game, which is also an incentive-design problem. We also consider, for both linear and nonlinear pricing, three different scenarios based on the information sharing structure for all parties on the users' true types, namely complete information, partially incomplete information, and totally incomplete information. For each case, we obtain the optimal, or near-optimal, pricing policy that maximizes the service provider's profit given the noncooperative price-taking behavior of the users, generally for the asymptotic case regarding the number of users, since our focus is on communication networks with a large user population. Comparative studies between linear and nonlinear pricing, as well as between the three classes of informational scenarios, are carried out to evaluate profit improvement by adoption of nonlinear pricing and the service provider's game preferences.
Network games; Pricing; Nonlinear pricing; Incomplete information; Network externality; Incentive; Stackelberg game
Tue, 01 May 2007 00:00:00 GMThttp://hdl.handle.net/2142/996012007-05-01T00:00:00ZShen, HongxiaReal-Time Scheduling in Wireless Networks
http://hdl.handle.net/2142/99600
Real-Time Scheduling in Wireless Networks
Raghunathan, Vivek; Cao, Min; Kumar, P.R.
We study a canonical real-time scheduling problem for time-slotted collocated wireless networks serving users with diverse real-time requirements and wireless loss patterns arising from fading. We study two traffic patterns: periodic arrivals with deadline equal to period, and renewal arrivals, in which a new packet from a user arrives when the current one leaves. Wireless channel conditions are modelled as Bernoulli losses.
For periodic arrivals, we prove that the optimal policy that minimizes the expected number of deadline misses has a strong property: it only switches between users on arrivals, successful completions or deadline expiry. When users have similar periods, this optimal policy is a linear switching curve characterized by a single number. Our result explicitly captures the trade-off between two competing aspects of the problem: the real-time tendency to schedule users in earliest-deadline-first (EDF) order, and the wireless tendency to exploit multi-user diversity by scheduling users with good channel conditions first. When users have similar channels, a common occurrence, we establish the optimality of EDF. For renewal arrivals, the optimal policy continues to have a switching structure, although not necessarily characterized by a single parameter. It schedules the user most likely to complete when it also has the earlier deadline. When the "better" user has a later deadline, it is scheduled till a worse user's deadline gets "close'", and then the worse user is scheduled till expiry.
Our results for periodic arrivals are strong and significant. They reduce the search space for optimal wireless real-time scheduling policies by an exponential order of magnitude. They establish optimality of "virtual-deadline-first" policies, where each user's deadline is modified to take channel quality into account. Policies in this class are easy to implement in a distributed manner.
Real-time; Wireless networks; Loss; Opportunistic scheduling; Dynamic; Programming
Thu, 01 Mar 2007 00:00:00 GMThttp://hdl.handle.net/2142/996002007-03-01T00:00:00ZRaghunathan, VivekCao, MinKumar, P.R.