Experimental Study of Capture Effect for Medium Access Control with ALOHA

ETRI Journal.
2015.
Apr,
37(2):
359-368

- Received : February 10, 2014
- Accepted : November 28, 2014
- Published : April 01, 2015

Download

PDF

e-PUB

PubReader

PPT

Export by style

Article

Metrics

Cited by

TagCloud

In this paper, we investigate the capture effect through experiments conducted with Iris nodes equipped with AT86RF230 radio transceivers. It is shown that the first arriving packet in a collision can capture the radio channel for equal power transmissions and may be decoded depending on the amount of overlap. A new 3-packet-capture scenario is introduced and implemented. To be able to understand the impact of capture on the throughput performance of wireless sensor networks, we present an analysis of the capture coefficient using our practical results. For real-world implementations, the throughput of pure ALOHA considering a finite number of users is presented in analytical form. The capture coefficient is then applied to pure ALOHA as a case study. Using analytical and practical implementations of the capture effect on ALOHA, a very good match in channel throughput performance enhancement is demonstrated over the non-capture effect case. TinyOS-2.x is used to program the nodes and to observe data exchange on a computer through a base station.
The capture coefficient is determined in terms of the degree of packet overlap and probability of any value of overlap occurring, up to the packet size. It is shown that the impact of capture is dependent on packet length because the capture effect does not occur beyond a certain overlap length. The capture coefficient is then adapted so that it can be used numerically to generate further results and predict the impact of capture on larger networks.
ALOHA schemes are a good example of simple MAC protocols, which are appropriate for lightly loaded networks but suffer from the drawbacks of employing a blind transmission strategy. ALOHA-based techniques are important for certain categories of wireless personal networks and WSNs such as those based on radio-frequency identification (RFID) systems that have limited memory and power capabilities. The pure ALOHA scheme, essentially the easiest and simplest technique, allows users to transmit their packets as soon as they have a packet for transmission, requiring no pre-coordination with other users accessing the transmission medium. One of the main assumptions in modelling this scheme is that the colliding packets (either fully or partly) will be lost. A packet transmission can be started at any time, so packet overlapping can occur to different extents. To demonstrate and quantify the impact of the capture effect on the throughput of pure ALOHA, a pure ALOHA network with a finite number of users is initially considered. The throughput calculation with a finite number of users through the binomial formula is presented. Then we calculate the probability of 2-packet- and 3-packet-capture scenarios occurring in the pure ALOHA. These probabilities are then multiplied by the capture coefficient derived to incorporate the impact of capture on the pure ALOHA throughput. Finally, we present the pure ALOHA throughput formula with finite users and the capture effect. We show that the throughput, with or without capture effect, decreases with an increasing number of users. The throughputs of two systems, one with four users and one with twelve users, are systematically analyzed, providing both analytical and practical results. Later, the impact of packet size on the throughput of the 12-user system is rigorously analyzed, considering three different packet sizes. Finally, we study the throughput with a high number of users.
The rest of the paper is organized as follows. Related work is covered in Section II. In Section III, the capture phenomenon is described and common scenarios are defined. In Section IV, the methodology of this study is presented, including the testbed, hardware, and software used. The results of the capture effect scenarios and the capture coefficient are then presented in Section IV. Section V analyzes the throughput of the ALOHA protocol with a finite number of users and the capture effect. The throughput performance evaluation of the pure ALOHA is presented in Section VI. Finally, Section VII concludes the paper.
C
/
I
ratio, the carrier power (
C
), and the sum of the interfering carrier powers (
I
), with up to four interferers. They carried out both simulation and testbed validation for comparison and achieved a very good agreement.
The capture effect has been thoroughly studied through theoretical work on the throughput of ALOHA networks. Throughput can be measured in Erlangs, where one Erlang corresponds to a single channel in use 100% of the time, or equivalently, ten channels each in use 10% of the time. For example, the maximum throughput of Slotted ALOHA network is around 0.36 Erlangs when assuming a finite-user network and no capture effect. This implies that 36% of the channel capacity can be used for useful data reception, but it has been markedly increased to nearly 0.53 Erlangs by exploiting the capture effect using two power groups; one transmitting at a relatively high power and the other at a relatively low power
[8]
. In
[9]
, the maximum throughput of Slotted ALOHA was shown to be increased to 0.65 Erlangs, assuming that one of the colliding packets can survive a collision and be received. In the case of pure ALOHA, the maximum throughput can be increased from 0.18 Erlangs to 0.26 Erlangs by exploiting the capture effect where users randomly select from one of two power levels from a given set
[10]
. The higher power level is chosen according to a pre-defined power capture threshold of the receiver in which the packets with the higher power can be successfully received. However, this is a theoretical study that did not consider real-world sensor node characteristics, so it only represents an analytical analysis of accounting for the capture effect in pure ALOHA.
Common capture cases: (a) stronger first (case 1) and (b) stronger last (case 2).
In this study, the capture effect phenomenon is considered by using the same transmission power level, so that case 1 is identical to case 2, which will be called here 2-packet-capture. In practice, the capture features of radio transceivers depend on their hardware design and implementation, particularly the modulation and decoding scheme. For example, in the case of “stronger last,” it is possible that a radio allows the stronger packet to resynchronize with itself. Therefore, as in the case of “stronger first,” the strong packet is received as long as it carries sufficient power. For example,
[4]
empirically shows that the strong packet can be captured if it arrives later but within the preamble of the first arriving packet. This case is illustrated in
Fig. 2
. Moreover, as in case 2, it has been shown that the strong packet can be captured regardless of the timing relation with the first arriving packet
[6]
. As described in the next section, the length of the preamble is very short so that its transmission time is tiny. Also, use of the same transmission power level may not allow the radio to resynchronize to the second arriving packet within the preamble of the first arriving packet. Hence, we did not consider this case.
Stronger last, but it is within the preamble of weak packet.
In the case of a higher traffic density in a network, we study a more realistic condition. Successive packets may arrive with small time differences, as depicted in
Fig. 3
. In this case, a simplified model, which will be called here as 3-packet-capture, is practically evaluated.
3-packet-capture scenario: (a) consecutive packets and (b) simplified model.
TinyOS is a richly documented open-source operating system, specifically designed for tiny low-power wireless devices
[11]
. It is aimed at low-cost, low-power operation and provides a large number of components that are statically linked together through their interfaces. Each application specifies the set of components used. In some ways, components are very similar to objects in traditional object-oriented programming.
Iris nodes
[12]
, manufactured by Crossbow Technology, are IEEE 802.15.4–compliant devices that operate in the 2.4 GHz (ISM) band and are used specifically for making up low-power WSNs. They feature an ATmega1281 low-power microcontroller and an AT86RF230 radio transceiver
[13]
. TinyOS-2.0 provides software support for the design specifications of Iris nodes. AT86RF230 has an internal 128 byte Frame Buffer, which is shared between transmission and reception, and it can only keep track of one TX or RX frame at a time (half-duplex communication). The IEEE 802.15.4 employs clear channel assessment (CCA) and back-off in the physical layer to ascertain whether the medium is occupied. In this study, CCA and back-off were disabled to allow concurrent transmissions and to enable ALOHA to be implemented.
The complete packet structure provided by IEEE 802.15.4 is shown in
Fig. 4
. The length of a packet can be varied up to 128 bytes by adjusting the payload length. The packet structure used in all of our experiments is shown in
Fig. 4
.
Packet format with lengths in bytes.
Successful reception of a packet is performed in two stages at the radio transceiver: valid preamble detection for synchronization and the CRC check for accuracy of the packets, which includes the headers and data payload fields. When the radio detects the preamble of a packet, it synchronizes and locks onto this packet. If the data has not been corrupted, then it is passed to the CRC check stage. In terms of the two capture scenarios described, the experiments conducted with Iris nodes confirm that reception of a packet in a collision condition is only successful in the case where a stronger packet arrives first (case 1).
All the experiments were conducted in an indoor, closed-office environment where the surrounding objects were stationary. All the nodes were in range of each other and were deployed at the same distance (15 cm) from the receiver, transmitting at the same power level. A view of the testbed is shown in
Fig. 5
.
Capture effect application environment; three senders, one receiver in the middle, and a base station.
The purpose of deploying the nodes at a short range from the receiver was to maximize the signal-to-noise ratio of the received packets at the receiver and to minimize multipath effects. A computer linked to the base station was used to observe data exchange.
C
_{p}
; that is,
C
_{p}
[1],
C
_{p}
[2], ... ,
C
_{p}
[packet length]. The individual contribution of each overlap amount to the capture coefficient is given as
(1) $$\frac{{C}_{\text{p}}[i]}{L},$$
where
i
denotes the number of bytes of overlap and
L
is the length of a packet in bytes. Therefore, the capture coefficient (
C
) is the sum of all of the individual contributions, which is
(2) $$C=\frac{{C}_{\text{p}}[1]}{L}+\frac{{C}_{\text{p}}[2]}{L}+\frac{{C}_{\text{p}}[3]}{L}+\text{\hspace{0.17em}\hspace{0.17em}}\cdots \text{\hspace{0.17em}\hspace{0.17em}}+\frac{{C}_{\text{p}}[L]}{L}.$$
Therefore, the capture coefficient is the arithmetic average of the capture probabilities; that is,
(3) $$\text{}C=\frac{{{\displaystyle \sum}}_{i=1}^{L}{C}_{\text{p}}[i]}{L}.$$
This coefficient can be used analytically to add the impact of capture to the throughput performance of MAC schemes in simulation. To demonstrate this, new throughput figures are obtained by applying the capture coefficient and are compared with practical results obtained from the testbed for the ALOHA protocol in Section VI.
Average number of captured packets with variability.
The results given in
Table 1
show that the capture of the first arriving packet always occurs if there is no overlap between packets. However, there is no capture when the length of overlap exceeds 50 bytes. The reason is that the SINR is below the sensitivity threshold of the radio transceiver. Between these limits, as the overlap length increases, the number of capture events reduces, as noted by the mean values.

To make the implementation of this scenario more practical, we used the simplified model shown in
Fig. 3(b)
. In this model, the first and second packets comprise the 2-packet-capture model, as described previously. The overlap between the first and second packets is a small fixed length, and the radio always detects the preamble of the first packet. Therefore, the second packet causes distortion on the detection of the preamble of the third packet. The overlap length between the second and third packet is created by adjusting the transmission time of the third packet. The focus is now only on the reception of the third packet using the same overlapping technique implemented earlier. The outcome of this scenario is presented in
Table 2
, where the mean of number of packets captured is calculated over one hundred runs.

It can be seen from these results that nearly half of the packets are missed with only a 5-byte overlap of packets 2 and 3. This is because packet 3 has its entire preamble and synchronization fields distorted by the tail end of packet 2 (since these segments are five bytes long). When the overlap length exceeds 40 bytes, no packets are captured. Note that this is a lower threshold than the experiment with 2-packet-capture because half of the packets have already been lost at the preamble detection stage and the initial five bytes of overlap.
C
_{p5}
, is given in
Tables 1
and
2
. Finally, the capture coefficient,
C
, is given by
(4) $$\text{}C=\frac{{{\displaystyle \sum}}_{i=1}^{L/\text{}5}{\text{C}}_{\text{p}5}[i]}{L\text{\hspace{0.05em}}/\text{\hspace{0.05em}}5}.$$
This coefficient has been used to add the impact of capture to the throughput of pure ALOHA in Section VI.
n
users, where each user transmits a packet with the same probability (
p
) based upon the channel traffic level. For a successful transmission, there should be no overlapping transmissions before or after the start time of a packet, as illustrated in
Fig. 7
.
Successful transmission in pure ALOHA.
The probability of
k
arrivals/transmissions from
n
users in the time duration of one packet can be given by the binomial distribution as
(5) $$P(k\text{\hspace{0.17em}\hspace{0.17em}in\hspace{0.17em}\hspace{0.17em}}n)\text{\hspace{0.17em}\hspace{0.17em}}=\text{\hspace{0.17em}\hspace{0.17em}}\frac{n!}{k!(n-k)!}{p}^{k}{(1-p)}^{n-k}.$$
Therefore, the probability of only one arrival/transmission from the
n
users is
(6) $$\begin{array}{cc}P(1\text{\hspace{0.17em}in\hspace{0.17em}}n)& =\frac{n!}{1!\left(n-1\right)!}{p}^{1}{(1-p)}^{n-1}\hfill \\ \hfill & =np{(1-p)}^{n-1}.\hfill \end{array}$$
The probability of no arrivals/transmissions before the start time of Packet 1 is
(7) $$\begin{array}{cc}P\left(0\text{\hspace{0.17em}\hspace{0.17em}in\hspace{0.17em}\hspace{0.17em}}(n-1)\right)& =\frac{\left(n-1\right)!}{0!\left(n-1-0\right)!}{p}^{0}{(1-p)}^{n-1}\hfill \\ \hfill & ={(1-p)}^{n-1}.\hfill \end{array}$$
The probability of a packet arriving and being transmitted in a period equal to the packet transmission duration (
p
) is related to the channel traffic by the following equation:
(8) $$p=\frac{1}{n}G,$$
where
G
denotes the channel traffic in Erlangs (equivalent to the average number of packets arriving/being transmitted in the packet transmission time) and
n
is the total number of users in the system; the throughput of which can be calculated as follows:
(9) $$\begin{array}{cc}\text{Throughput}& =P(1\text{\hspace{0.17em}\hspace{0.17em}in\hspace{0.17em}\hspace{0.17em}}n)P\left(0\text{\hspace{0.17em}\hspace{0.17em}in\hspace{0.17em}\hspace{0.17em}}(n-1)\right)\hfill \\ \hfill & =np{(1-p)}^{n-1}{(1-p)}^{n-1}\hfill \\ \hfill & =np{(1-p)}^{2(n-1)}.\hfill \end{array}$$
Two possible cases for collision of two packets: (a) case 1 and (b) case 2.
The probability of a 2-packet collision is the summation of the two cases; that is,
(10) $$P\left(\text{collisionoftwopackets}\right)\text{}=P\left(\text{case}1\right)\text{}+P\left(\text{case}2\right).$$
The probability of a 2-packet collision in case 1 is
(11) $$\begin{array}{cc}P(\text{case\hspace{0.17em}\hspace{0.17em}1})& =P(2\text{\hspace{0.17em}\hspace{0.17em}in\hspace{0.17em}\hspace{0.17em}}n)P\left(0\text{\hspace{0.17em}\hspace{0.17em}in\hspace{0.17em}\hspace{0.17em}}(n-2)\right)\hfill \\ \hfill & =\frac{n(n-1)}{2}{p}^{2}{(1-p)}^{2(n-2)}.\hfill \end{array}$$
The probability of a 2-packet collision in case 2 is
(12) $$\begin{array}{cc}P(\text{case\hspace{0.17em}\hspace{0.17em}2})& =P(1\text{\hspace{0.17em}\hspace{0.17em}in\hspace{0.17em}\hspace{0.17em}}n)P\left(1\text{\hspace{0.17em}\hspace{0.17em}in\hspace{0.17em}\hspace{0.17em}}(n-1)\right)\hfill \\ \hfill & =n(n-1){p}^{2}{(1-p)}^{2n-3}.\hfill \end{array}$$
Combining the two cases, the probability of a 2-packet collision is
(13) $$n(n-1){p}^{2}\left(\frac{{(1-p)}^{2(n-2)}}{2}\text{\hspace{0.17em}\hspace{0.17em}}+\text{\hspace{0.17em}\hspace{0.17em}}{(1-p)}^{2n-3}\right).$$
Having calculated the probability of 2-packet-capture, we now derive the probability for the 3-packet-capture scenario, which again includes two cases, as shown in
Fig. 9
.
Two possible cases for collision of three packets: (a) case 1 and (b) case 2.
Similarly, the probability of 3-packet collision is the summation of the two cases; that is,
(14) $$P\left(\text{collisionofthreepackets}\right)\text{}=P\left(\text{case}1\right)\text{}+P\left(\text{case}2\right).$$
The probability of 3-packet collision in case 1 is
(15) $$\begin{array}{cc}P(\text{case\hspace{0.17em}\hspace{0.17em}1})& =\text{\hspace{0.17em}\hspace{0.17em}}P(2\text{\hspace{0.17em}\hspace{0.17em}in\hspace{0.17em}\hspace{0.17em}}n)P\text{\hspace{0.17em}}\left(1\text{\hspace{0.17em}\hspace{0.17em}in\hspace{0.17em}\hspace{0.17em}}(n-1)\right)\hfill \\ \hfill & =\frac{n{(n-1)}^{2}}{2}{p}^{3}{(1-p)}^{2(n-2)}.\hfill \end{array}$$
And the probability of 3-packet collision in case 2 is
(16) $$\begin{array}{cc}P(\text{case\hspace{0.17em}\hspace{0.17em}2})& =\text{\hspace{0.17em}\hspace{0.17em}}P(1\text{\hspace{0.17em}\hspace{0.17em}in\hspace{0.17em}\hspace{0.17em}}n)P\text{\hspace{0.17em}}\left(2\text{\hspace{0.17em}\hspace{0.17em}in\hspace{0.17em}\hspace{0.17em}}(n-1)\right)\hfill \\ \hfill & =\frac{n(n-1)(n-2)}{2}{p}^{3}{(1-p)}^{2(n-2)}.\hfill \end{array}$$
Combining the two cases, the probability of a 3-packet collision is
(17) $$\frac{n(n-1){p}^{3}{(1-p)}^{2(n-2)}}{2}\left((n-1)+(n-2)\right).$$
Using the capture derived, coefficient the throughput accounting for the capture effect is given by
(18) $$\begin{array}{l}\text{Throughput}=np{(1-p)}^{2(n-1)}\\ \text{\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}}+n(n-1){p}^{2}\left(\frac{{(1-p)}^{2(n-2)}}{2}+{(1-p)}^{(2n-3)}\right){C}_{2}\\ \text{\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}}+\frac{n(n-1){p}^{3}{(1-p)}^{2(n-2)}}{2}\left((n-1)+(n-2)\right){C}_{3},\end{array}$$
where
C
_{2}
denotes the capture coefficient for 2-packet collision and
C
_{3}
for 3-packet collision.
(19) $$I=\frac{LN\text{}}{GD},$$
where
I
denotes the average packet inter-arrival times,
L
is the packet length,
N
is the number of nodes in the network,
G
is the generated traffic, and
D
is the data rate of the channel. The transmit power of all packets is set to the same level.
Table 3
summarizes the implementation parameters.
ALOHA implementation testbed; a receiver in the middle, and transmitters: (a) 4-user ALOHA system and (b) 12-user ALOHA system.

Figures 11
and
12
show the practical throughput characteristics for the 4- and 12-node systems, respectively and are compared to the finite-user analytical model with and without the capture coefficient. The standard infinite-user curve is also included for comparison. For the practical implementation, we have chosen a 50-byte packet size, as the capture effect did not occur beyond an overlap of this length.
ALOHA throughput with four users.
ALOHA throughput with twelve users.
The throughput with a finite number of nodes is higher than the infinite-node case, and as expected, as the number of nodes increases, the throughput difference decreases. With the capture effect model, the maximum throughput of the 4-user scenario is slightly greater than double that predicted by the standard infinite-node theory model; and for the 12-user case, it is enhanced by two-thirds. The practical results show that our capture effect model closely matches the practical results. The small discrepancy is because it is impossible to model and implement every capture scenario; and we only modeled two of the most common scenarios. It can be concluded that the two capture scenarios represent the majority of the capture effect.
The impact of packet length on throughput has been studied since the capture coefficient is dependent on packet size (see (3)). Therefore, an important purpose of this study is to demonstrate the capture effect in association with varying packet lengths. Three different packet lengths (75 bytes, 100 bytes, and 125 bytes) have been implemented with 12 nodes in the network.
Figure 13
presents the throughput performance of pure ALOHA with both the analytical (A) and practical (P) results.
Figure 13
illustrates that the throughput has an increasing trend as the packet size decreases. The analytical model effectively predicts the practical results with a small difference of approximately 0.01 Erlangs. A maximum throughput of around 0.28 Erlangs is achieved with a 50-byte packet when the traffic load is 0.7 Erlangs. On the other hand, a packet size of 125 bytes can achieve around 0.245 Erlangs throughput. The packet size is an important factor when considering the influence of the capture effect on performance. The capture effect has greater influence with smaller packets where the capture coefficient has a high value, resulting in higher throughput.
ALOHA throughput with twelve users in association with packet lengths.
A 100-node system is now considered to demonstrate the effectiveness of the finite-user capture model in predicting the performance that would be observed practically with a much larger testbed. The impact of packet size is again considered.
Figure 14
presents the analytical throughput predictions.
ALOHA throughput with 100 users in association with packet lengths.
It is clear that the throughput with 100 nodes approaches the infinite-node theoretical value. A maximum throughput of 0.295 Erlangs is achieved with a traffic load of 0.8 Erlangs for a packet size of 50 bytes, whereas it is around 0.223 Erlangs with a traffic load of 0.6 Erlangs for a packet size of 125 bytes. We therefore conclude that if the packet size is decreased, the throughput increases as an overall trend.
Corresponding Author 772@york.ac.uk
Selahattin Kosunalp received his BS degree in electronics and telecommunications engineering from Kocaeli University, Turkey, in 2009 and his MS degree in communications engineering from the University of York, UK, in 2011. He is currently working toward his PhD degree in electronics engineering at the University of York. His research interests include WSNs, medium access control protocol design, and real-time embedded systems.
paul.mitchell@york.ac.uk
Paul D. Mitchell is a senior lecturer with the Department of Electronics, University of York, UK. He has been a researcher in wireless communications for over 15 years and has industrial experience with British Telecommunications and QinetiQ. His research expertise lies in WSNs, satellite systems, medium access control, cognitive radio, queuing theory, and system level simulation. He is an author of over 90 refereed journal and conference papers and has served on numerous technical program committees, including VTC and ICC. He was general chair of ISWCS in 2010. He is currently an associate editor for both the IET Wireless Sensor Systems journal and the International Journal of Distributed Sensor Networks; and he has experience as a guest editor and reviewer for a number of IEEE, ACM, and IET journals. He has experience with research council and EU-funded research, including management of projects and multi-partner work packages. He is a senior member of the IEEE and a member of the IET.
david.grace@york.ac.uk
David Grace received his PhD in electronics engineering from the University of York, UK, in 1999. Since 1994, he has been a member of the Department of Electronics at the University of York, where he is now a senior research fellow and head of the Communications and Signal Processing Research Group. He is also a co-director of the York–Zhejiang Lab on Cognitive Radio and Green Communications, as well as a guest professor at Zhejiang University, China. His current research interests include cognitive green radio, particularly applying distributed artificial intelligence to resource and topology management to improve overall energy efficiency; 5G system architectures; and dynamic spectrum access and interference management. He is one of the lead investigators on FP7 ABSOLUTE, which is dealing with extending LTE-A for emergency/temporary events through application of cognitive techniques, and more recently, he has become a co-investigator of the FP7 BuNGee project dealing with broadband next-generation access. He is the author of over 180 papers and the author/editor of two books. He currently chairs the IEEE Technical Committee on Cognitive Networks and the Worldwide Universities Network Cognitive Communications Consortium; and he was a member of COST IC0902. He is a founding member of the IEEE technical committee on Green Communications and Computing. In 2000, he jointly founded SkyLARC Technologies Ltd., and was one of its directors.
tim.clarke@york.ac.uk
Tim Clarke received his BA degree in biology from the University of York, UK, in 1975. He joined the Royal Air Force as an air traffic control officer before becoming an education officer. He underwent advanced training at the Royal Military College of Science, Shrivenham, Swindon, UK, where he received his MS degree in guided weapons systems engineering. He is a senior lecturer in control engineering and is head of the control systems laboratory, intelligent systems group, Department of Electronics, University of York. His research interests are in the areas of biologically inspired engineering and control systems. He is a member of the IET and has served on IFAC Technical Committees 5.4 (Large Scale Complex Systems), 7.3 (Aerospace), and 7.5 (Intelligent Autonomous Vehicles).

I. Introduction

Medium access control (MAC) protocols for wireless sensor networks (WSNs) are designed to regulate and control user access to a shared medium. In the design of most MAC protocols, a prominent assumption about the integrity of the received packets is that they will be corrupted and not correctly received when there is concurrent reception. The main function of a MAC protocol is to detect, resolve, and avoid collisions. Collision avoidance is a crucial task in WSNs, since all packets that are lost in a collision have to be discarded and retransmitted
[1]
. An effective collision avoidance scheme is a prerequisite for an ideal protocol, since a good MAC scheme will be able to sense a clear channel before attempting a transmission. In a poor scheme, collisions cause waste of channel resources, with the consequence of low throughput and high delay.
It is commonly assumed that when two or more senders transmit simultaneously over the same channel, a packet collision occurs at the receiver, resulting in packet loss and the failure of all colliding packets. However, through the capture effect, packets from the strongest user may be successfully received in the presence of the simultaneous reception (collision) of packets. WSNs can benefit from the capture effect, which would enhance the throughput performance of the associated MAC protocols. This paper explores this phenomenon practically, contributing the following;
- ▪ This is the first practical study on capture for equal power transmissions.
- ▪ A new 3-packet-capture scenario is introduced and tested, extending prior work for realistic systems.
- ▪ A capture coefficient, the packet reception rate in collisions, is derived for any capture scenario based on packet length. This enables the capture effect to be incorporated into the performance evaluation of WSNs through simulation.

II. Related Work

Theoretical studies of the capture effect have been undertaken to understand packet reception in the presence of interference and to improve the performance of sensor networks. An early study
[2]
utilized a perfect capture model, in which the packet with the highest received power is always received, thereby achieving dramatic improvements in throughput and delay reduction. Later, researchers
[3]
proposed a signal-to-interference-plus-noise ratio (SINR)–based capture model. If the SINR of a received packet is above a specified threshold, then the received packet is captured.
In the literature, there have been few practical studies
[4]
–
[7]
of the capture effect. Reference
[4]
empirically observed the capture effect from real-life measurements using Prism2 chipset wireless cards with IEEE 802.11b. They showed that a strong packet can be decoded either when it arrives first or last but within the preamble of the first arriving packet. In
[5]
, the packet reception rate for a single sender and interferer is presented; the measurements were conducted using Mica2 nodes equipped with CC1000 radios. They identified a critical threshold value such that if the SINR exceeds the threshold value, there is a high probability that capture will be achieved. Also, the measured threshold value increases with varying numbers of interferers. In
[6]
, the frame reception rate is given against different PHY bit rates, based on the signal-to-interference power ratio (SIR), taking the arrival timing of the received packets into account. The capture effect in IEEE 802.15.4 networks is presented in
[7]
, providing a mathematical model using 13192-SARD and 13192-EVB boards equipped with MC13192 radio transceivers. They give the packet capture probability versus
III. Capture Scenarios and Methodology

Much of the prior work on the capture effect assumes two overlapping packets in one of two situations. In case 1, the strong packet arrives first and the radio transceiver synchronizes to it. As long as it has sufficient power, it is received normally. In case 2, the stronger packet arrives later, the radio transceiver synchronizes to the weak packet and reception fails, resulting in both packets being lost because the strong packet corrupts the weak packet.
Figure 1
demonstrates the two possible capture cases.
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

IV. Experimental Results

- 1. Calculating Capture Coefficient

In most existing simulation and analytical models for throughput calculation, researchers would make the assumption that all packets involved in a collision are completely lost. However, this is not a realistic assumption. Therefore, if the probability of collision can be analytically expressed, depending on the system, then the effect of capture can be simply incorporated into the overall system performance (throughput). If the probability of collision is known and the packet reception rate in collision conditions is also known, then the capture effect can be estimated theoretically and incorporated into the prediction of the throughput performance by multiplying the probability of collision by the packet reception rate in collisions. This is referred to as the capture coefficient in association with a packet length.
To derive the capture coefficient precisely, we assume that the number of overlapping bytes in collisions is uniformly distributed. This means that the probabilities associated with the numbers of possible bytes of overlap occurring are all equal. The number of possible bytes of overlap can vary from zero to anything up to and including the length of the packet. The array of capture probabilities for each overlap length is defined as
- 2. 2-Packet-Capture Scenario

A packet transmission can start at any time, so packet overlap can vary. In this study, the number of overlapping bytes in a collision is systematically increased until the capture effect does not occur. To create packet collisions, the time between the colliding packets must be carefully adjusted. The minimum overlapping length was chosen as five bytes, and it was increased in 5-byte steps until the capture effect did not occur. The reason for choosing 5-byte steps is to precisely arrange the time between the colliding packets as the time for transmitting a single bit is tiny.
The number of observed collisions has to be sufficiently large to give meaningful results. It was found that 6,000 or more collisions would enable us to calculate the average number of successful captures reliably.
Figure 6
shows a graph of the results with the variability from the average included. To see the possible differences when the system restarts, we ran each overlapping ratio one hundred times.
Table 1
presents the practical results: the mean number of packets captured over the hundred runs, with respect to various overlapping lengths, and the capture probabilities for each overlapping length.
PPT Slide

Lager Image

2-packet-capture scenario: mean number of captured packets and capture probability for each overlapping ratio.

Number of overlapping bytes | 0 | 5 | 10 | 15 | 20 | 25 | 30 | 35 | 40 | 45 | 50 |
---|---|---|---|---|---|---|---|---|---|---|---|

Mean | 6,000 | 5,945 | 5,290 | 4,266 | 3,605 | 2,744 | 1,836 | 1,155 | 540 | 136 | 0 |

Capture probability | 1 | 0.99 | 0.88 | 0.71 | 0.60 | 0.45 | 0.30 | 0.19 | 0.09 | 0.02 | 0 |

- 3. 3-Packet-Capture Scenario

In this model, the possible reception scenarios at the receiver are (see
Fig. 3(a)
) as follows:
- ▪ Reception of a third packet (detection of preamble and CRC check) in the presence of second-packet interference.
- ▪ If reception of the third packet fails, then the possibility of detecting the preamble of a fourth packet arises.
- ▪ If reception of the fourth packet fails, then the possibility of detecting the preamble of a fifth packet arises, and so on.

3-packet-capture scenario: mean number of captured packets and capture probability for each overlapping ratio.

Number of overlapping bytes | 0 | 5 | 10 | 15 | 20 | 25 | 30 | 35 | 40 |
---|---|---|---|---|---|---|---|---|---|

Mean | 6,000 | 3,102 | 2,960 | 2,264 | 1,554 | 873 | 401 | 35 | 0 |

Capture probability | 1 | 0.51 | 0.49 | 0.37 | 0.25 | 0.14 | 0.06 | 0.005 | 0 |

- 4. Adapting Capture Coefficient

To adapt the capture coefficient to this study, we approximated the length of a packet to be a multiple of five bytes. The overlap length was increased in 5-byte increments, and similarly, the probabilities associated with all of the 5-byte increment overlaps are equivalent. The array of capture probabilities,
V. Analysis of ALOHA Protocol

- 1. Throughput Analysis of Pure ALOHA with Finite Users

A large body of prior work has studied the throughput of ALOHA networks assuming an infinite number of users
[14]
. However, for practical deployments, it is essential to recalculate the theoretical throughput with a small number of users. Some research has addressed the throughput of Slotted ALOHA with finite user numbers, as in
[15]
, or through binomial distribution, as in
[16]
. However, an extensive review of the literature has not revealed the same analysis for the pure ALOHA case. In this section, the throughput calculation of pure ALOHA with a finite number of users is presented based on the binomial distribution. Consider
PPT Slide

Lager Image

- 2. Throughput Analysis of Pure ALOHA with Capture Effect

The probabilities of 2-packet-capture and 3-packet-capture based on the scenarios described previously are derived for the pure ALOHA scheme. Then, these probabilities with the capture coefficient are added to the throughput of pure ALOHA. There are two cases for the collision of two packets, depicted in
Fig. 8
.
PPT Slide

Lager Image

PPT Slide

Lager Image

VI. ALOHA Performance Evaluation

The testbed consists of transmitters and a single receiver, all in range of each other.
Figure 10
presents a view of the testbed. Each node generates a packet with exponentially distributed inter-arrival time and immediately transmits it. The packet inter-arrival time fits an exponential distribution, which is a practical model. Each node has the same average inter-arrival time, which is given as below
PPT Slide

Lager Image

ALOHA implementation parameters.

Parameters | Values |
---|---|

Channel bit rate | 250 kbits/s |

Packet length | 50, 75, 100, and 125 bytes |

Transmit power | 2 mW |

Number of transmitters | 4 and 12 |

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

VII. Conclusion

In this paper, we have investigated the capture effect to clarify its impact based on real-world measurements. Contrary to theory, we show that using the same transmission power level at the same distance, the capture effect is seen. We have modeled the impact of the capture and incorporated it into the performance evaluation of WSNs through simulation. The throughput of pure ALOHA with a finite-user case has been modelled for practical implementation. The increase in the throughput of pure ALOHA due to the capture effect has been presented. Two factors affecting ALOHA performance have been investigated, packet size and number of users, using both mathematical analysis and practical implementations. Results show that the throughput capacity of pure ALOHA with the capture effect is better than that predicted by the standard assumptions. The maximum throughput in a 4-user scenario is slightly more than double that predicted by theory (37.62%). It can be predicted that a high-user-density system would tend toward the theoretical limit based on the validated model. It can be concluded that the throughput of existing MAC schemes may be greater than currently predicted as a result of the capture effect described here.
BIO

Demirkol I.
,
Ersoy C.
,
Alagoz F.
2006
“MAC Protocols for Wireless Sensor Networks: A Survey,”
IEEE Commun. Mag.
44
(4)
115 -
121

Ramamurthi B.
,
Saleh A.M.
,
Goodman D.J.
1987
“Perfect-Capture ALOHA for Local Radio Communications,”
IEEE J. Sel. Areas Commun.
5
(5)
806 -
814
** DOI : 10.1109/JSAC.1987.1146592**

Lau C.
,
Leung C.
1992
“Capture Models for Model Packet Radio Networks,”
IEEE Trans. Commun.
40
(5)
917 -
925
** DOI : 10.1109/26.141457**

Kochut A.
2004
“Sniffing out the Correct Physical Layer Capture Model in 802.11b,”
IEEE Int. Conf. Netw. Protocols
Berlin, Germany
252 -
261

Son D.
,
Krishnamachari B.
,
Heidemann J.
2006
“Experimental Study of Concurrent Transmission in Wireless Sensor Networks,”
ACM Int. Conf. Embedded Netw. Sensor Syst.
Boulder, CO, USA
237 -
250

Lee J.
2007
“An Experimental Study on the Capture Effect in 802.11a Networks,”
ACM Int. Workshop Wireless Netw. Testbeds, Experimental Evalutaion Characterization
Montreal, Canada
19 -
26

Gezer C.
“Capture Effect in IEEE 802.15.4 Networks: Modelling and Experimentation,”
IEEE Int. Symp. Wireless Pervasive Comput.
Modena, Italy
May 5–7, 2010
204 -
209

Metzner J.
1976
“On Improving Utilization in ALOHA Networks,”
IEEE Trans. Commun.
24
(4)
447 -
448
** DOI : 10.1109/TCOM.1976.1093317**

Namislo C.
1984
“Analysis of Mobile Radio Slotted ALOHA Networks,”
IEEE J. Sel. Areas Commun.
2
(4)
583 -
588
** DOI : 10.1109/JSAC.1984.1146088**

Borchardt R.L.
,
Ha T.T.
1994
“Capture ALOHA with Two Random Power Levels,”
Comput. Commun.
17
(1)
67 -
71
** DOI : 10.1016/0140-3664(94)90019-1**

Levis P.
2005
“TinyOS: An Operating System for Wireless Sensor Networks,” Ambient Intell.
Springer Berlin Heidelberg
New York, NY, USA
115 -
148

Iris Wireless Measurement System Datasheet
http://bullseye.xbow.com:81/Products/Product_pdf_files/Wireless_pdf/IRIS_Datasheet.pdf

Data Sheet for AT86RF230 2.4 GHz IEEE 802.15.4-Compliant RF Transceiver
http://www.atmel.com/Images/doc5131.pdf

Abramson N.
1970
“The ALOHA System: Another Alternative for Computer Communications,”
ACM Fall Joint Comput. Conf.
Montvale, NJ, USA
281 -
285

Rom R.
,
Sidi M.
1990
“Multiple Access Protocols: Performance and Analysis,”
Springer-Verlag
New York, NY, USA

Brand A.
,
Aghvami H.
2002
Multiple Access Protocols for Mobile Communications: GPRS, UMTS, and Beyond
Wiley
Chichester, UK

Citing 'Experimental Study of Capture Effect for Medium Access Control with ALOHA
'

@article{ HJTODO_2015_v37n2_359}
,title={Experimental Study of Capture Effect for Medium Access Control with ALOHA}
,volume={2}
, url={http://dx.doi.org/10.4218/etrij.15.0114.1369}, DOI={10.4218/etrij.15.0114.1369}
, number= {2}
, journal={ETRI Journal}
, publisher={Electronics and Telecommunications Research Institute}
, author={Kosunalp, Selahattin
and
Mitchell, Paul D.
and
Grace, David
and
Clarke, Tim}
, year={2015}
, month={Apr}