We consider the problem of distributed scheduling in wireless networks where heterogeneously delayed information about queue lengths and channel states of all links are available at all the transmitters. In an earlier work (by Reddy et al. in Queuein
g Systems, 2012), a throughput optimal scheduling policy (which we refer to henceforth as the R policy) for this setting was proposed. We study the R policy, and examine its two drawbacks -- (i) its huge computational complexity, and (ii) its non-optimal average per-packet queueing delay. We show that the R policy unnecessarily constrains itself to work with information that is more delayed than that afforded by the system. We propose a new policy that fully exploits the commonly available information, thereby greatly improving upon the computational complexity and the delay performance of the R policy. We show that our policy is throughput optimal. Our main contribution in this work is the design of two fast and near-throughput-optimal policies for this setting, whose explicit throughput and runtime performances we characterize analytically. While the R policy takes a few milliseconds to several tens of seconds to compute the schedule once (for varying number of links in the network), the running times of the proposed near-throughput-optimal algorithms range from a few microseconds to only a few hundred microseconds, and are thus suitable for practical implementation in networks with heterogeneously delayed information.
In this document, we are primarily interested in computing the probabilities of various types of dependencies that can occur in a multi-cell infrastructure network.
In this paper, we study the performance of greedy scheduling in multihop wireless networks, where the objective is aggregate utility maximization. Following standard approaches, we consider the dual of the original optimization problem. The dual can
be solved optimally, only with the knowledge of the maximal independent sets in the network. But computation of maximal independent sets is known to be NP-hard. Motivated by this, we propose a distributed greedy heuristic to address the problem of link scheduling. We evaluate the effect of the distributed greedy heuristic on aggregate utility maximization in detail, for the case of an arbitrary graph. We provide some insights into the factors affecting aggregate utility maximization in a network, by providing bounds on the same. We give simulation results for the approximate aggregate utility maximization achieved under distributed implementation of the greedy heuristic and find them close to the maximum aggregate utility obtained using optimal scheduling.
In this paper, we consider the problem of modelling the average delay experienced by an application packets of variable length in a single cell IEEE 802.11 DCF wireless local area network. The packet arrival process at each node i is assumed to be a
stationary and independent increment random process with mean ai and second moment a(2) i . The packet lengths at node i are assumed to be i.i.d random variables Pi with finite mean and second moment. A closed form expression has been derived for the same. We assume the input arrival process across queues to be uncorrelated Poison processes. As the nodes share a single channel, they have to contend with one another for a successful transmission. The mean delay for a packet has been approximated by modelling the system as a 1-limited Random Polling system with zero switchover times. Extensive simulations are conducted to verify the analytical results.
In this paper, we consider the problem of modelling the average delay experienced by a packet in a single cell IEEE 802.11 DCF wireless local area network. The packet arrival process at each node i is assumed to be Poisson with rate parameter lambda_
i. Since the nodes are sharing a single channel, they have to contend with one another for a successful transmission. The mean delay for a packet has been approximated by modelling the system as a 1-limited Random Polling system with zero switchover time. We show that even for non-homogeneous packet arrival processes, the mean delay of packets across the queues are same and depends on the system utilization factor and the aggregate throughput of the MAC. Extensive simulations are conducted to verify the analytical results.
In this paper, we consider the problem of modelling the average delay in an IEEE 802.11 DCF wireless mesh network with a single root node under light traffic. We derive expression for mean delay for a co-located wireless mesh network, when packet gen
eration is homogeneous Poisson process with rate lambda. We also show how our analysis can be extended for non-homogeneous Poisson packet generation. We model mean delay by decoupling queues into independent M/M/1 queues. Extensive simulations are conducted to verify the analytical results.
