Simulation and Diagnosis of Package Losses Due to Collision and Weak Signal in Wireless Network
CHAPTER ONE
PREAMBLE
Carrier-Sense Multiple Access or CSMA which evolved from the slotted-Aloha protocol in the early 1970s, has become the de-facto mechanism for implementing distributed access to shared communication medium.
It is commonly used by the Ethernet class of link technologies for both wired (802.3) and wireless (802.11) media. An important facet to the proper implementation of the CSMA method is being able to detect concurrent access of the media by two or more entities that usually leads to a collision.
In the case of a wired Ethernet, transmitting stations continue to listen for incoming signals (collisions) and emit a jamming signal to notify all other stations if a collision is detected. This provides accurate and timely feedback to the CSMA protocol which triggers a back off in order to resolve the concurrent access.
CHAPTER TWO
LITERATURE REVIEW
FEEDBACK-BASED COLLISION INFERENCE
A critical component in COLLIE is the client-side component which takes advantage of feedback from the receiver such as an AP in WLAN (or a peer if in ad-hoc mode) in order to infer the cause of a packet loss (weak signal versus collision). COLLIE implements most of the logic on the client device requiring minimal support from the receivers. We describe two versions of this inferencing algorithm.
(i) A basic version (Single-AP), which requires minimal support from the AP to which the client is associated to. This applies to environments where a single AP provides wireless access to the entire establishment, such as in hotspots – coffee shops, apartments, etc.
(ii) An enhanced version (Multi-AP) which builds on top of the basic version, by leveraging input from two or more APs to provide very high accuracy in detecting collisions. This approach applies to enterprise WLANs where multiple APs belong to the same administrative domain. As with the basic case, APs here also implement a very minimal relaying of information that assists in collision inferencing. We evaluate our algorithm quantitatively by considering the following (i) the probability of false positives – that is, the cases where our algorithm outputs a collision while the actual cause was weak signal, and
(ii) the accuracy – that is, the number of cases our algorithm identifies as collision over the total number of cases. Our design of metrics, discussed later in this chapter, allows the link management algorithms to specify a certain false positive rate, making the exact accuracy a function of this rate. This choice is by design, thereby leaving a significant control to the actual link management algorithms in the client. However, to provide a sense of the strong performance of our algorithms we observe that, given a desired false positive rate of 2%, our basic algorithms achieve an accuracy of about 60% on average, while the multi-AP enhancements achieve an accuracy of 95% on average.
Basic Approach (Single AP)
The basic algorithm for collision inferencing presented here, uses a simple relaying back of data packet received in error. This relaying is done by the intended recipient of the packet which is the AP to which the client is associated to (in the infrastructure mode of 802.11). Our observations indicate that due to receiver-synchronization using the physical-layer preamble, data that immediately follows the preamble is seldom found in error — this includes critical fields in the header such as the source and destination MAC addresses. Thus, practically for all cases of packets received in error at the AP, it was possible to relay it back to the correct associated client. By analyzing these packets, we design a necessary and
sufficient set of metrics comprising of bit-error rates (BER), symbol-error rates (SER), error- per-symbol (EPS), and joint distributions of these, which can act as strong indicators for packets suffering collision versus signal attenuation. We now describe the experiments designed to understand collisions and identify the set of metrics used for loss diagnosis. Experiment Design for Detecting Collisions Figure 3 shows the experiment setup designed to induce collisions. T1 and T2 are two transmitters placed a certain distance apart. Receivers R1 and R2 are co-located with respective transmitters. Receiver R was placed in common range of both transmitters and was modified to capture and log all packets received (whether correctly or in error). The chances of collision is greatly increased by disabling the MAClevel backoffs at both T1 and T2. The signal between the transmitters T1, T2 and the receiver R was strong enough so as to not cause any bit-level errors due to attenuation. This was verified through rigorous testing.
CHAPTER THREE
METHODOLOGY FOR FACT FINDING AND DETAILED DISCUSSION OF THE SUBJECT
USING COLLIE FOR LINK ADAPTATION
In this chapter we present a simple, yet effective protocol used to enhance link adaptation mechanisms based on the COLLIE framework. The algorithm implemented in this simple protocol is only to serve as a reference implementation of COLLIE and is by no means is an optimal algorithm. The goal of this description is to demonstrate how COLLIE can be effective in making more intelligent link adaptation decisions leading to improvements in throughput.
COLLIE-based link adaptation protocol: The goal of this link adaptation protocol is to utilize the collision inference results available from COLLIE in deciding how to best react to a packet loss and its consequent recovery. Consider a client which transmits a packet to an AP, but the latter receives the packet in error. Using feedback mechanisms, as outlined in Chapter two and shown in Figure 2, the client can infer the cause of the packet error. This knowledge is, then, fed into the link adaptation decision at the client. If the packet loss is due to a collision, then the correct adaptation mechanism is to perform exponential back off. On the other hand, if the packet loss is determined to be due to a weak signal, then we allow an existing rate adaptation algorithm to explore and find a better data rate to transmit future packets. In general, any existing rate adaptation algorithm, e.g., RRAA, Sample Rate, AARF, and ARF, can be used here to leverage such feedback from COLLIE.
CHAPTER FOUR
RELATED WORK
The problem of loss diagnosis is a fairly difficult one, and there has been a few prior efforts in the wireless domain that have tried to address this problem. For example, Whitehouse et. al. [10] showed that if two frames arrive at a receiver with certain timing characteristics (the second message arrives after the preamble and start bytes of the first message) and with certain power levels (the second message has significantly higher power level when compared to the first) then it was possible for the receiver to conclude that collision had, indeed, occurred.
This mechanism was implemented on the Mica2 sensor mote platform using a 433 MHz Chipcon CC1000 radio transceiver, and required low-level access to timing and signal strength measurements that were available on that platform. In comparison, COLLIE is implemented for off-the-shelf 802.11 wireless transceivers that do not provide such low-level access to communication parameters. Hence, the mechanisms in [10] could not be applied in this environment.
CHAPTER FIVE
CONCLUSION
In this project, we have tried to address the fundamental issue of identifying the cause of an erroneous packet reception in 802.11 systems. Unlike most of the previous approaches, our proposed mechanism, COLLIE employs a direct approach by using explicit feedback from the receiver to immediately determine the cause of the packet loss.
Through rigorous evaluations conducted on regular laptops over a wide range of experiments, we find that our collision inferencing mechanisms can provide up to 95% accuracy in detecting packets in collision while allowing a configurable false positive rate of 2% and lead to throughput improvements between 20-60%.
Through an emulation of voice call (made using the Netgear SPH101 Voice-over-WIFI phone), we also showed that COLLIE reduces retransmission related costs by 40% for different mobility scenarios. Since all analysis performed in this paper was based on actual experiments and implementation over contemporary 802.11 hardware, we expect that the implications of our results and the various insights gained from this study will be very useful in other problem domains such as link adaptation, channel management, transmit power control etc., where understanding the link behavior is critical.
REFERENCES
- [1] Kenneth W. Ouyang, Yin-Kung Huang, and Phil Shieh, “Auto adjustment circuit for collision detection of ethernet,” US Patent No 378824, 1996.
- [2] J. Bicket, “Bit-rate selection in wireless networks,” MIT Master’s Thesis, 2005.
- [3] A. Kamerman and L. Monteban, “Wavelan ii: A high-performance wireless lan for the unlicensed band,” 1997.
- [4] T. Henderson, D. Kotz, and I. Abyzov, “The changing usage of a mature campus-wide wireless network,” in ACM MOBICOM, 2004.
- [5] V. Bychkovsky, B. Hull, A. Miu, H. Balakrishnan, and S. Madden, “A measurement study of vehicular internet access using in situ wi-fi networks,” in MOBICOM, 2006.
- [6] S. Wong, S. Lu, H. Yang, and V. Bhargavan, “Robust rate adaptation for 802.11 wireless networks,” in ACM Mobicom, 2006.
- [7] J. Kim et al., “Cara: Collision-aware rate adaptation for ieee 802.11 wlans,” in Infocom, 2006, pp. 139–150.
- [8] C. Reis, R. Mahajan, M. Rodrig, D. Wetherall, and J. Zahorjan, “Measurement-based models of delivery and interference in static wireless networks,” in ACM SIGCOMM, 2006.
- [9] “Mobile Edge Architecture of Aruba Wireless Networks,” URL:http://www.arubanetworks.com/technology/mobileedge/ architecture.
- [10] K. Whitehouse, A. Woo, F. Jiang, J. Polastre, and D Culler, “Exploiting the capture effect for collision detection and recovery,” in EmNetS-11, 2005.
- [11] Ji-Hoon Yun and Seung-Woo Seo, “Collision detection based on rf energy duration in ieee 802.11 wireless lan,” in Comsware, 2006.
