We consider single-hop topologies with saturated transmitting nodes, using carrier-sense multiple access with collision avoidance (CSMA/CA) for medium access, as standardized under the IEEE 802.11 distributed coordination function. We study systems where one or more backoff parameters of the CSMA/CA protocol (the initial backoff, the backoff multiplier, and the number of retries) are different from the standard. It is known that, for several classes of these protocol parameters, such systems exhibit a certain performance anomaly known as short term unfairness. We also find that the phenomenon of short term unfairness is observed in systems where the propagation delays among the participating nodes are not negligible compared with the duration of a backoff slot, even when the nodes use the default backoff parameters of the standard. It also turns out that the standard fixed point analysis technique (and its simple extensions) does not predict the system behavior well in such cases. For systems with large propagation delays, we observe that, as propagation delay increases, the collision probability of a node initially increases, but then flattens out, contrary to what is predicted by the standard fixed point approximation. Our study of several example systems reveals some interesting connections between the protocol parameters, the number of nodes, the propagation delay, and the degree of unfairness. This paper reveals that the inability of the standard fixed point model to capture the performance in such cases is due to its state-independent attempt rate assumption. In this paper, we develop a novel approximate, but accurate, analysis that uses state-dependent attempt rates with a parsimonious state representation for computational tractability. The analytical method is also able to quantify the extent of short term unfairness in the system, something not possible with existing analytical techniques, and can, therefore, be used to tune the protocol parameters to achieve desired throughput and fairness objectives.

We consider single-hop topologies with saturated transmitting nodes, using IEEE 802.11 DCF for medium access, where the propagation delays among the nodes are not negligible compared to the backoff slot duration. In this situation, we find that there is misaligned sensing of channel idleness, and also short-term unfairness in access to the medium. We demonstrate that existing analysis techniques (or, extensions thereof) are unable to account for these features, resulting in inaccurate prediction of the performance. Focusing on the case in which transmitters are equidistant from one another, and also each receiver is equidistant from all the transmitters, we provide a detailed stochastic model that accurately captures the system evolution. Since an exact analysis of this model is computationally intractable, we develop a novel approximate, but accurate, analysis that uses a parsimonious state representation for computational tractability. Numerical experiments show, the approximate analysis predicts the system throughput to a relative accuracy of 2-3%, and collision probabilities to a relative accuracy of 3-8% compared to simulations. Interestingly, we observe that as propagation delay increases, the collision probability of a node initially increases, but then flattens out, contrary to what one might intuitively expect. Finally, we also demonstrate how to optimize slot duration using the approximate analysis for maximizing system throughput.

In this paper, we study the problem of wireless sensor network design by deploying a minimum number of additional relay nodes (to minimize network design cost) at a subset of given potential relay locationsin order to convey the data from already existing sensor nodes (hereafter called source nodes) to a Base Station within a certain specified mean delay bound. We formulate this problem in two different ways, and show that the problem is NP-Hard. For a problem in which the number of existing sensor nodes and potential relay locations is n, we propose an O(n) approximation algorithm of polynomial time complexity. Results show that the algorithm performs efficiently (in over 90% of the tested scenarios, it gave solutions that were either optimal or exceeding optimal just by one relay) in various randomly generated network scenarios.