This paper studies the performance of contention based medium access control (MAC) protocols. In particular, a simple and accurate technique for estimating the throughput of the IEEE 802.11 DCF protocol is developed. The technique is based on a rigorous analysis of the Markov chain that corresponds to the time evolution of the back-off processes at the contending nodes. An extension of the technique is presented to handle the case where service differentiation is provided with the use of heterogeneous protocol parameters, as, for example, in IEEE 802.11e EDCA protocol. Our results provide new insights into the operation of such protocols. The techniques developed in the paper are applicable to a wide variety of contention based MAC protocols.

We consider the problem of throughput-optimal cross-layer design of wireless networks. We propose a joint congestion control and scheduling algorithm that achieves a fraction 1/dI(G) of the capacity region, where dI(G) depends on certain structural properties of the underlying connectivity graph G of the wireless network and also on the type of interference constraints. For a wide range of wireless networks, dI(G) can be upper bounded by a constant, independent of the number of nodes in the network. The scheduling element of our algorithm is the maximal scheduling policy. Although maximal scheduling policy has been considered in many of the previous works, the difficulties that arise in implementing it in a distributed fashion in the presence of interference have not been dealt with previously. In this paper, we propose two novel randomized distributed algorithms for implementing the maximal scheduling policy under the 1-hop and 2-hop interference models.

Abstract — We study the performance of contention based medium access control (MAC) protocols. In particular, we pro-vide a simple and accurate method for estimating the throughput of IEEE 802.11 DCF and IEEE 802.11e EDCA. Our method is based on a rigorous analysis of the Markov chain associated with the back-off process at the contending nodes. Our results provide new insights into the operation of IEEE 802.11 DCF and IEEE 802.11e EDCA. Although we focus on IEEE 802.11 MAC protocol in this paper, the techniques developed are applicable to a wide variety of contention based MAC protocols. I.

We consider the problem of throughput-optimal scheduling in wireless networks subject to interference constraints. We model the interference using a family of K -hop interference models. We define a K-hop interference model as one for which no two links within K hops can successfully transmit at the same time (Note that IEEE 802.11 DCF corresponds to a 2-hop interference model.) .For a given K, a throughput-optimal scheduler needs to solve a maximum weighted matching problem subject to the K-hop interference constraints. For K=1, the resulting problem is the classical Maximum Weighted Matching problem, that can be solved in polynomial time. However, we show that for K>1,the resulting problems are NP-Hard and cannot be approximated within a factor that grows polynomially with the number of nodes. Interestingly, we show that for specific kinds of graphs, that can be used to model the underlying connectivity graph of a wide range of wireless networks, the resulting problems admit polynomial time approximation schemes. We also show that a simple greedy matching algorithm provides a constant factor approximation to the scheduling problem for all K in this case. We then show that under a setting with single-hop traffic and no rate control, the maximal scheduling policy considered in recent related works can achieve a constant fraction of the capacity region for networks whose connectivity graph can be represented using one of the above classes of graphs. These results are encouraging as they suggest that one can develop distributed algorithms to achieve near optimal throughput in case of a wide range of wireless networks.

There has been significant recent interest within the networking research community to characterize the impact of mobility on the capacity and delay in mobile ad hoc networks. In this correspondence, the fundamental tradeoff between the capacity and delay for a mobile ad hoc network under the Brownian motion model is studied. It is shown that the two-hop relaying scheme proposed by Grossglauser and Tse (2001), while capable of achieving a per-node throughput of /spl Theta/(1), incurs an expected packet delay of /spl Omega/(logn//spl sigma//sub n//sup 2/), where /spl sigma//sub n//sup 2/ is the variance parameter of the Brownian motion model. It is then shown that an attempt to reduce the delay beyond this value results in the throughput dropping to its value under static settings. In particular, it is shown that under a large class of scheduling and relaying schemes, if the mean packet delay is O(n/sup /spl alpha////spl sigma//sub n//sup 2/), for any /spl alpha/<0, then the per-node throughput must be O(1//spl radic/n). This result is in sharp contrast to other results that have recently been reported in the literature.

In this paper, we investigate the use of limited infrastructure, in the form of wires, for improving the energy efficiency of a wireless sensor network. We call such a sensor network - a wireless sensor network with a limited infrastructural support - a hybrid sensor network. The wires act as short cuts to bring down the average hop count of the network, resulting in a reduced energy dissipation per node. Our results indicate that adding a few wires to a wireless sensor network can not only reduce the average energy expenditure per sensor node, but also the non-uniformity in the energy expenditure across the sensor nodes.

We study the asymptotic throughput capacity and delay in mobile ad hoc networks following the 2-hop relaying algorithm proposed by Grossglauser and Tse (2001). We assume the nodes to be uniformly distributed on a sphere, and consider two canonical mobility models: the Brownian mobility model (BMM), and the random way-point mobility model (RWMM). We show that for an ad hoc network formed by n mobile nodes the delay scales as O (log/sup 2/n//spl sigma//sup 2/(n)) under the BMM, and, /spl Theta/ (1/r(n)v(n)) under the RWMM, where /spl sigma//sup 2/(n) is the variance parameter of the BMM, v(n) is the average speed of nodes under the RWMM, and r(n) is the communication radius of the nodes.

1 Introduction 1.1 Microarrays and Gene Expression Gene Expression is the process by which a gene's coded information is translated into the proteins present and operating in the cell. Changes in gene expression are associated with many important biological phenomena, including morphogenesis and aging, cancer and disease states, and adaptive responses to the environment. The advent of high density microarrays, introduced by Schena et al.[1] in 1995, made it possible for the first time to measure the expression levels simultaneously of all or most of the genes in a given genome. Since then, cDNA microarrays[2] and GeneChips (also called high-density oligonucleotide arrays)[6] have been used extensively in generating genome-wide expression profiles for different organisms under different environmental conditions. The microarray technologies for whole-genome expression profiling are new and rapidly evolving, and we refer the reader to the recent reviews ([4],[3],[5]).