This paper considers the problem of scheduling real-time traffic in wireless networks. We consider ad hoc wireless networks with general conflict graph-based interference model and single-hop traffic. Each packet is associated with a deadline and will be dropped if it is not transmitted before the deadline. The number of packet arrivals in each time-slot and the maximum delay before the deadline are independent and identically distributed across time. We require a minimum fraction of packets to be delivered. At each link, we assume the link keeps track of the difference between the minimum number of packets that need to be delivered so far and the number of packets that are actually delivered, which we call the deficit. The largest-deficit-first (LDF) policy schedules links in descending order according to their deficit values, which is a variation of the longest-queue-first (LQF) policy for non-real-time traffic. We prove that the efficiency ratio of LDF, which is the fraction of the throughput region that LDF can achieve for given traffic distributions, can be lower-bounded by a quantity that we call the real-time local-pooling factor (R-LPF). We further prove that a lower bound on the R-LPF can be related to the weighted sum of the service rates, with a special case of 1/(β+1) by considering the uniform weight, where β is the interference degree of the conflict graph. We also propose a heuristic consensus algorithm that can be used to obtain a good weight vector for such lower bounds for given network topology.

We consider the problem of distributed admission control without knowledge of the capacity region in single-hop wireless networks, for flows that require a pre-specified bandwidth from the network. We present an optimization framework that allows us to design a scheduler and resource allocator, and by properly choosing a suitable utility function in the resource allocator, we prove that existing flows can be served with a prespecified bandwidth, while the link requesting admission can determine the largest rate that it can get such that it does not interfere with the allocation to the existing flows.

This paper considers the problem of scheduling real-time traffic in wireless networks. We consider an ad hoc wireless network with general interference and general one-hop traffic. Each packet is associated with a deadline and will be dropped if it is not transmitted before the deadline expires. The number of packet arrivals in each time slot and the length of a deadline are both stochastic and follow certain distributions. We only allow a fraction of packets to be dropped. At each link, we assume the link keeps track of the difference between the minimum number of packets that need to be delivered and the number of packets that are actually delivered, which we call deficit. The largest-deficit-first (LDF) policy schedules links in descending order according to their deficit values, which is a variation of the largest-queue-first (LQF) policy for non-real-time traffic. We prove that the efficiency ratio of LDF can be lower bounded by a quantity that we call the real-time local-pooling factor (R-LPF). We further prove that given a network with interference degree β, the R-LPF is at least 1/(β+1), which in the case of the one-hop interference model translates into an R-LPF of at least 1/3.

This paper studies the problem of scheduling in single-hop wireless networks with real-time traffic, where every packet arrival has an associated deadline and a minimum fraction of packets must be transmitted before the end of the deadline. Using optimization and stochastic network theory we study the problem of scheduling to meet quality of service (QoS) requirements under heterogeneous delay constraints and time-varying channel conditions. Our analysis results in an optimal scheduling algorithm which fairly allocates data rates to all flows while meeting long-term delay demands. We also prove that under a simplified scenario our solution translates into a greedy strategy that makes optimal decisions with low complexity.

This paper studies the problem of congestion control and scheduling in ad hoc wireless networks that have to support a mixture of best-effort and real-time traffic. Optimization and stochastic network theory have been successful in designing architectures for fair resource allocation to meet long-term throughput demands. However, to the best of our knowledge, strict packet delay deadlines were not considered in this framework previously. In this paper, we propose a model for incorporating the quality-of-service (QoS) requirements of packets with deadlines in the optimization framework. The solution to the problem results in a joint congestion control and scheduling algorithm that fairly allocates resources to meet the fairness objectives of both elastic and inelastic flows and per-packet delay requirements of inelastic flows.

This paper studies the problem of congestion control and scheduling in ad hoc wireless networks that have to support a mixture of best-effort and real-time traffic. Optimization and stochastic network theory have been successful in designing architectures for fair resource allocation to meet long-term throughput demands. However, to the best of our knowledge, strict packet delay deadlines were not considered in this framework previously. In this paper, we propose a model for incorporating the quality of service (QoS) requirements of packets with deadlines in the optimization framework. The solution to the problem results in a joint congestion control and scheduling algorithm which fairly allocates resources to meet the fairness objectives of both elastic and inelastic flows, and per-packet delay requirements of inelastic flows.

Mobile ad-hoc networks are deployed under the assumption that participating nodes are willing to forward other nodes' packets. In reputation-based mechanisms cooperation is induced by means of a threat of partial or total disconnection from the network if a node is non-cooperative; however packet collisions and interference may make cooperative nodes appear selfish sometimes. In this paper we use a simple network model to first study the performance of some proposed reputation strategies and then present a new mechanism that we call DARWIN (Distributed and Adaptive Reputation mechanism for WIreless ad-hoc Networks). The idea is to avoid a retaliation situation after a node has been falsely perceived as selfish so cooperation can be restored quickly. We prove that our strategy is robust to imperfect measurements, is collusion-resistant and can achieve full cooperation among nodes.