Projects in DNA Lab - 802.11 Wireless

Return to Main Projects Page

• Active Projects:

  • Scheduling and Modeling in Physical Layer Capture: A traditional assumption on the analysis of CSMA/CA MAC protocols is that the collisions occur with any overlapped transmissions from neighbors while transmissions from far-away nodes can be parallelized. However, a phenomenon where transmitted packets get through collisions, which is referred to as the physical layer capture, has been observed in real implementations including 802.11 wireless networks. In this research, we have shown that the previous models based on the assumption do not correctly describe the behavior of CSMA/CA MAC protocols and been focusing to develop fair scheduling algorithms from our accurate models, which reflecs the effect of the physical layer capture.

    • A General Model of 802.11 DCF: We present a general analytical model and uses the fixed-point method to predict error probabilities and throughputs of packet transmissions with multiple 802.11 DCF sender-receiver pairs. Our model takes into account the cumulative strength of interference signals for the physical layer capture and this permits the analysis of packet reception with interference from neighbors at any set of locations.

      Publications:

      • Hoon Chang, Vishal Misra and Dan Rubenstein, A General Model and Analysis of Physical Layer Capture in 802.11 Networks. Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE Infocom), Barcelona, Spain, April, 2006.

    • Fair Scheduling Algorithms in CSMA/CA Networks: The goal of this work is to formally investigate the utility-based fairness under the effect of the physical layer capture in CSMA/CA wireless networks. We present a formula to obtain the optimal access rates of senders and distributed algorithms to achieve the fairness.

  • MANET and Mesh Incentives: Unlike traditional wired hosts, wireless nodes in ad-hoc networks are supposed not only to participate in the networks for their own services, but also to forward packets for other nodes voluntarily. If all nodes come from a single authority and work for the same objective, they have incentives to cooperate with each other. However, nodes are generally autonomous and naturally prone to refuse to forward packets for other nodes. Because forwarding packets may consume scarce resources like battery power, bandwidth and CPU cycles. In order to encourage autonomous nodes to forward packets for other nodes, incentive protocols for ad-hoc networks are needed. We propose a budget-balanced virtual credit exchange protocol. The choice of virtual credit in stead of monetary credit comes naturally because we do not want to sacrifice the self-organizing and self-contain system structure of ad-hoc networks. The "budget-balance" feature of the protocol has two meanings. First, when a serving node help a requesting node forward packets, the number of credits paid from the requesting node equals the number of credits received by the serving node. Second, with a fixed number of nodes, the total number of virtual credits in the network is a constant. Thus, one can imagine that the flow of data packets should be in the opposite direction of the credit flow.

    Contact Richard Ma for details.

  • Competetive MAC: Slotted-Aloha is commonly deployed Medium Access Control (MAC) protocols in environments where multiple transmitting devices compete for a medium, yet may have difficulty sensing each other's presence (the "hidden terminal problem"). We model and evaluate the throughput that can be achieved in a system where nodes compete for bandwidth using a generalized version of slotted-Aloha protocols. The protocol is implemented as a two-state system, where the probability that a node transmits in a given slot depends on whether the node's prior transmission attempt was successful. Using Markov Models, we evaluate the channel utilization and fairness of these types of protocols for a variety of node objectives, including maximizing aggregate throughput of the channel, each node greedily maximizing its own throughput, and attacker nodes that attempt to jam the channel. If all nodes are selfish and greedily attempt to maximize their own throughputs, a situation similar to the Prisoner's Dilemma arises. Our results reveal that under heavy loads, a greedy strategy reduces the utilization, and that attackers cannot do much better than attacking during randomly selected slots.

    Publications:

    • Richard T. B. Ma, Vishal Misra and Dan Rubenstein, Modeling and Analysis of Generalized Slotted-Aloha MAC Protocols in Cooperative, Competetive and Adversarial Environments, The 26th International Conference on Distributed Computing Systems (ICDCS 06), Lisboa, Portugal, July, 2006.
    • Richard T. B. Ma, Vishal Misra and Dan Rubenstein, Cooperative and Non-cooperative Models for slotted-Aloha type MAC protocols, ACM Sigmetrics Performance Evaluation Review, Volume 33, Number 2, pp. 30-32, 2005.

• Old Projects:

  • Distributed Scalable Replica/Task Placement: Content distribution systems increase their resilience and efficiency in delivering content by replicating the content at multiple points in the network. Wireless 802.11 ad-hoc networks can utilize multiple channels to reduce interference among neighbor's competing transmissions. We viewed the challenge of replicated task placement as a non-traditional graph coloring problem, and constructed distributed, self-configuring algorithms that assign colors to nodes such that the coloring is provably within a constant factor of an optimal assignment.