Distributed medium access control protocol based on successive collision detection for dense wireless sensor networks

Abstract

The medium access control protocol plays an important role to decrease access collisions in dense wireless sensor networks where multiple sensors in the same vicinity attempt to transmit a packet simultaneously. In this article, we propose a distributed medium access control protocol that uses successive multiple collision detection phases for dense wireless sensor network environments by enhancing the typical carrier sense multiple access with collision resolution protocol that uses only a single collision detection phase. In the proposed medium access control protocol, colliding stations are filtered in each collision detection phase and only surviving stations compete again in the next collision detection phase. Therefore, the collision detection probability becomes higher as the collision detection phases proceed. Utilizing the successive multiple collision detection phases, we analyze the throughput numerically and find optimal operating parameters—such as the number of collision detection phases and the number of collision detection slots per phase—that maximize the throughput. Analysis and simulation results show that the proposed medium access control protocol using the successive collision detection technique significantly outperforms the conventional carrier sense multiple access with collision resolution protocol.

Introduction

With the rapid growth of various Internet of Things (IoT) applications, massive IoT devices will form a dense wireless sensor network (WSN) in future. One of the most performance-effective factors in a dense WSN is the medium access control (MAC) protocol, which efficiently and fairly distributes the limited radio resources to a number of users by controlling the random access from them. The MAC protocol should be designed to minimize access collisions, which occur when two or more stations attempt to transmit a packet at the same time. The access collision results in the retransmission or loss of packets and deteriorates network performances in terms of throughput, delay, and energy efficiency. Many carrier sense multiple access (CSMA)-based MAC protocols have been proposed in WSNs to avoid collisions.^1,2 These protocols can efficiently reduce collisions, but inherently cannot eliminate all collisions because of hidden terminal problems as well as collisions when multiple nodes sense the medium free at the same time. Previous studies^3–5 demonstrate that CSMA-based MAC protocols dramatically deteriorate its performance when the number of simultaneous transmitting nodes increases. Such collisions become severe in dense WSNs for two reasons. First, many dense WSNs are event-driven and generate bursty spatially correlated traffic, where a plurality of sensors in the same vicinity have messages to send simultaneously in response to the same event. ⁶ Second, WSNs are typically established with few sink nodes to which packets from many sensors converge. Such convergence causes many collisions around sink nodes, which is known as funneling effect. ⁷ Therefore, it becomes more important to reduce the access collision in dense WSNs.

A representative MAC protocol widely used in WSNs is the carrier sensing multiple access with collision avoidance (CSMA/CA) protocol because of its operational simplicity. However, it is well known that the efficiency of CSMA/CA is reduced by the successive collisions of retransmitted packet as the number of contending stations increases.^3–5 To improve the efficiency of CSMA-based MAC protocols, recently the CSMA with collision detection (CSMA/CD)-like behavior has been emulated in wireless environments.^8–11 This attempt is due to the fact that the CSMA/CD enables the transmitter to detect a collision while transmitting data and to stop the transmission immediately if a collision is detected. ¹² However, the original CSMA/CD protocol is designed for wired networks and thus infeasible in a wireless channel, because the wireless transmitter cannot simultaneously transmit and listen on the same channel as the receiver of the transmitting station is overwhelmed by its own transmission power (a.k.a. the deafness problem).

As the first attempt to overcome the deafness problem and allow the CSMA/CD operation in a wireless network, CSMA with time-split collision detection (CSMA-TCD) has been proposed under assuming a long propagation delay. ⁸ In CSMA-TCD, the transmitter pauses after transmitting a preamble with a fixed length and briefly executes carrier sensing. Because of the discriminating radio propagation delay, simultaneously transmitting stations can detect the other preamble signals and thus pause their data transmissions. As another reasonable approach to collision detection (CD) in wireless channels, a wireless CSMA/CD (WCSMA/CD) protocol has been proposed.^9,10 In WCSMA/CD, all stations define a CD period equally and each transmitting station randomly determines a short CD slot within the CD period after starting the data transmission. The transmitting station then senses the channel during the selected CD slot to check whether a collision has occurred. If colliding stations are present and they all do not choose the same CD slot, each station senses a higher energy level than the threshold during the CD slot (i.e. a collision is detected). In this case, the colliding stations abort their transmission within the CD period and perform a backoff procedure; thus, the wasted time is reduced. By enhancing the WCSMA/CD, the CSMA with collision resolution (CSMA/CR) protocol has been proposed recently. ¹¹ Upon detecting a collision during the CD period in CSMA/CR, the transmitter immediately aborts its own transmission and broadcasts a jam signal to inform the other stations that they must stop their transmissions. After the station has transmitted the jam signal during the CD period, it is allowed to retransmit the data promptly without backoff, whereas the other stations automatically defer access. This eventually resolves a next collision that might occur, thereby leading to more performance improvement.

Although the previous CSMA/CD-based MAC protocols improve the MAC efficiency considerably, the access collision still exists and the throughput degrades due to the collision, backoff time, and additional protocol overhead. These problems become severe particularly when the number of accessing stations increases significantly in a highly dense WSN environment. In this article, we propose an advanced MAC protocol that employs successive multiple CD phases by extending the typical CSMA/CR protocol, in order to further decrease the probability of access collision when a large number of stations attempt to access. Multiple CD phases can filter out the colliding station successively and thus the number of contending stations decreases in each CD phase. We explain the operation of the proposed MAC protocol in detail and analyze its throughput numerically with respect to the number of CD phases and the number of stations. Thereafter, we investigate optimal operating parameters, such as the number of CD phases and the number of CD slots per phase, to maximize the throughput. Finally, we discuss implementation issues and present feasible solutions from the practical point of view.

The rest of this article is organized as follows. Section “Original CSMA/CR protocol” reviews the operation of the original CSMA/CR protocol. Section “Proposed MAC protocol” explains the operation of the proposed MAC protocol in detail. Section “Performance analysis” analyzes the performance of the proposed scheme numerically and section “Results and discussion” shows the throughput performance by considering various operating parameters. Section “Implementation issue” indicates some implementation issues for the practical use of the proposed MAC protocol. Finally, section “Conclusion” presents the conclusions drawn in this article.

Original CSMA/CR protocol

The CSMA/CR protocol adopts the CD process of WCSMA/CD but adds distinct operations in which a station can transmit or detect a jam signal when a collision is detected. More specifically, the transmitting station in CSMA/CR can detect not only the energy, but also the jam signal during the randomly selected CD slot. This operation divides CSMA/CR into possible four event cases, as shown in Figure 1.

Figure 1.

Possible event cases in the original CSMA/CR operation. (a) First success case: only one station accesses the channel, (b) second success case: collision is resolved because only one station selects the earliest CD slot, (c) first failure case: all stations select the same CD slot, and (d) second failure case: two or more (not all) stations select the earliest CD slot.

Figure 1(a) illustrates the first success case in which no simultaneously accessing stations are present (i.e. no collision occurs); therefore, neither energy nor jam is not detected during the CD slot. The station continues its data transmission right after the brief sensing during the allocated CD slot and successfully completes transmission.

Figure 1(b) illustrates the second success case in which the station that selects the earliest CD slot among the colliding stations (i.e. Station 1) detects the energy but not a jam signal. Being the first station to detect a collision, Station 1 subsequently transmits a jam signal, instead of a data signal, for the remainder of the CD period. This allows the stations that select a later CD slot (i.e. Stations 2 and 3) to detect both the energy and jam signal, causing their ongoing transmissions to stop immediately. Once the CD period ends, only the station that transmitted the jam signal is allowed to retransmit its data promptly without backoff while the other stations automatically defer their access. This collision resolution (CR) technique ensures successful data retransmission of one station if a collision is detected during the CD period.

Figure 1(c) shows the first failure case in which all colliding stations select the same CD slot. Thus, they are unable to detect the energy and therefore continue transmission, leading to transmission failure. When transmission failure occurs, the transmitter identifies it by the lack of receipt of the acknowledgement (ACK) packet and then retries to access after backoff.

Figure 1(d) shows another transmission failure case where two or more stations (but not all) select the same earliest CD slot. Hence, the stations detect only the energy and therefore transmit the jam signal equally during the remaining CD period and also transmit the new data simultaneously after the CD period. This action also leads to transmission failure. In this case, the station that selects the later CD slot (i.e. Station 3) detects the overlapped jam signal. Because an overlapped signal with the same pattern is generally detectable, ¹³ Station 3 can recognize the jam signal and stop its transmission. Here, we denote the lengths of the CD slot, CD period, and transmitted data by $T_{\mathrm{slot}}$ , $T_{\mathrm{cdp}}$ , and $T_{\mathrm{data}}$ , respectively, and we indicate the channel usage time in each case. Note that in the second success and failure cases, the wasted channel time is more than that in the first ones.

Proposed MAC protocol

In the CSMA/CR protocol, collision can be resolved by one random slot selection in one CD period. However, there is still a chance of collision in CSMA/CR, as shown in Figure 1(c) and (d). To decrease these collisions, we try to repeat the CD period to provide more opportunities for random slot selection, thus utilizing the successive multiple CD phases.

To facilitate to understand the operation of the proposed protocol using multiple CD phases, we first try to illustrate the possible event cases when only two CD phases are used and three stations access simultaneously, as shown in Figure 2. There are three successful transmission cases and three failure cases. Figure 2(a) shows the case when only one station accesses the channel and no collision occurs. Figure 2(b) shows the case when only one station chooses the earliest CD slot at the first CD phase, and CD is successful at the first CD phase. Figure 2(c) shows the case when CD fails as two stations of the total three stations choose the earliest CD slot at the first CD phase. However, at the second CD phase, these two colliding stations continue the CR process and only one station among them chooses the earliest CD slot and eventually collision is resolved. As shown, in each CD phase, only the stations that select the earliest CD slot are filtered and they compete again in the next CD phase. In this way, as the CD phase proceeds, the number of contending stations decreases and the CD probability (i.e. the probability that only one station selects the earliest CD slot in each CD phase) increases. Note that each case has a different channel usage time. In other words, each case is classified according to the channel usage time.

Figure 2.

Possible event cases in the proposed scheme using two CD phases when three stations access simultaneously. (a) First success case: only one station accesses the channel, (b) second success case: collision is resolved at the first CD phase, (c) third success case: collision is resolved at the second CD phase, (d) first failure case: all stations choose the same CD slot in all CD phases, (e) second failure case: some stations choose the earliest CD slot at the first CD phase and all the surviving stations choose the same CD slot at the second CD phase, and (f) third failure case: some stations choose the earliest CD slot at the second CD phase after any failure at the first CD phase.

As shown in Figure 1(c) and (d), transmission fails when all stations select the same CD slot or some stations select the earliest CD slot. In each case, the wasted channel time is different. By an appropriate arrangement of two such cases in two CD phases, we get three cases of transmission failure based on wasted channel times. Figure 2(d) shows the case when all stations choose the same CD slot in every CD phase. Figure 2(e) shows the case when some stations choose the earliest CD slot at the first CD phase and all the surviving stations choose the same CD slot at the second CD phase. Figure 2(f) shows the case when some stations choose the earliest CD slot at the second CD phase after any failure at the first CD phase. Note that in the latter case more channel time is wasted.

Next, we consider the event cases when three CD phases are employed. As illustrated in Figure 3, there are four successful transmission cases and four failure cases. Although Figure 3 might be a simple extension of Figure 2, we add it here to clarify the operation of the proposed scheme and to facilitate the numerical analysis for an arbitrary number of CD phases, which will be presented in section “Performance analysis.”

Figure 3.

Possible event cases in the proposed scheme using three CD phases when four stations access simultaneously: (a) first success case, (b) second success case, (c) third success case, (d) fourth success case, (e) first failure case, (f) second failure case, (g) third failure case, and (h) fourth failure case.

It is worth noting that the proposed MAC protocol using successive CD phases has two strong points that contribute to performance improvement. The first one is the only stations that choose the earliest CD slot are filtered in each CD phase and have a chance to retry at the next CD phase. This makes the number of contending stations decreases as the CD phase proceeds, eventually increasing the probability of successful transmission. The second point is that if the collision is resolved at a certain CD phase (i.e. only one station chooses the earliest CD slot), then all the data transmitted during the following CD phases is valid (not corrupted), and just one CD slot in each CD phase is added as the overhead. This advantage hardly causes a transmission overhead although the CD phases remain after a collision is successfully resolved.

The flowchart of the proposed MAC protocol using an arbitrary number of CD phases (h) is described in Figure 4. First, a station tries to access if it has data in buffer and the channel is idle. In each CD phase, it selects a CD slot number with a random integer between 1 and the number of CD slots per CD phase (m) and starts to transmit data. Thereafter, the station pauses its transmission at the selected CD slot and senses the channel again. The following operation depends on the sensing results: (1) if neither energy nor jam is detected, the station continues data transmission; (2) if the energy is detected but the jam is not, the station transmits a jam signal until the current CD period ends and retransmits data from the beginning; and (3) if both the energy and jam are detected, the station stops data transmission immediately and performs a backoff procedure. This CD process is repeated as many times as the predetermined number of CD phases (h). Then, the station waits the ACK packet from its receiver. If the ACK is received, the transmission is successful. Otherwise, the station retries to access after the backoff.

Figure 4.

Flowchart of the proposed MAC protocol.

Performance analysis

Assumptions and notations

First, we enumerate some assumptions and notations needed for the numerical analysis of the proposed MAC protocol:

1. We consider a fully connected network topology.^9–11 This means that the stations are densely packed, and each station can hear the transmission of any other station in the network so that no hidden node exists. Some commercial IoT applications are deployed in a limited geographical area, such as home, classroom, or building, with several sink nodes. In the vicinity of the sink node, we realistically assume that all stations lie at a single-hop distance of one another and form a fully connected network.

2. We assume ideal channel conditions, and thus, no channel and sensing errors are present. Therefore, transmission failure is caused only by access collision.^14–16

3. We assume a saturation condition, that is, each station always has data packets in the transmission buffer and always tries to access the channel.^16–18

4. We suppose a slotted p-persistent CSMA for access; hence, each station accesses the channel in the idle slot with the probability $p(0<p\le 1)$ .^10,15 Although the access probability p can be adapted to the network conditions or traffic loads, we fix the value of p in this study to focus on the effect of the other parameters on the performance, because the related access control issues have already been investigated in many literatures.^19–21

5. We assume that the propagation delay is much smaller than the slot time, and thus it is neglected.

6. We assume that all stations transmit data of the same size and denote the data transmission time by $T_{\mathrm{data}}$ , which includes the SIFS and ACK reception time. ¹⁰

7. We denote the length of the CD slot by $T_{\mathrm{slot}}$ and assume the CD slot length to be the same as the generic slot length by considering the worst-case scenario, because the CD slot time cannot be longer than the generic slot time to prevent the other stations from attempting a new access when a station senses during a CD slot. ⁹ In practice, the length of the CD slot depends on the channel assessment method, radio propagation delay, and sensing module’s processing speed. The details of this subject will be addressed in section “Implementation issue.”

8. We denote the number of available CD slots per CD phase by m. For analysis simplicity, we assume that the number of CD slots is fixed in each CD phase. Moreover, we denote the length of one CD period by $T_{\mathrm{cdp}}$ , which becomes $T_{\mathrm{cdp}}=(1+m)T_{\mathrm{slot}}$ because the first slot in the CD period cannot be used for sensing. Practically, the first slot must include the preamble and the information of the selected CD slot number to preserve synchronization and data integrity at the receiving station.

9. We denote the number of CD phases by h.

10. We denote the number of stations by n.

Probability analysis

First, we calculate the probabilities of all event cases in Figures 1–3. The probability $P_{\mathrm{tr}}$ that at least one transmission from n contending stations exists within a slot time is given by

$$P_{\mathrm{tr}}=1-(1-p{)}^n$$

(1)

The probability $P_a(i)$ that $i\ge 1$ stations out of the n ready ones attempt to access is obtained as

$$P_a(i)=\frac{\left(\begin{array}{c}n\hfill \\ \multicolumn{1}{c}{i}\end{array}\right)p^i{(1-p)}^{n-i}}{P_{\mathrm{tr}}}=\frac{\left(\begin{array}{c}n\hfill \\ \multicolumn{1}{c}{i}\end{array}\right)p^i{(1-p)}^{n-i}}{1-{(1-p)}^n}$$

(2)

When i stations access simultaneously, the probability that j stations select the earliest CD slot in m slots is given by

• 1. If $j<i$

$$\begin{array}{c}{P}_b(i,j)=\left(\begin{array}{c}i\hfill \\ \multicolumn{1}{c}{j}\end{array}\right){\left(\frac{1}{m}\right)}^j{\left(\frac{m-1}{m}\right)}^{i-j}\hfill \\ +\left(\begin{array}{c}i\hfill \\ \multicolumn{1}{c}{j}\end{array}\right){\left(\frac{1}{m}\right)}^j{\left(\frac{m-2}{m}\right)}^{i-j}\hfill \\ +\cdots +\left(\begin{array}{c}i\hfill \\ \multicolumn{1}{c}{j}\end{array}\right){\left(\frac{1}{m}\right)}^j{\left(\frac{1}{m}\right)}^{i-j}\hfill \\ =\left(\begin{array}{c}i\hfill \\ \multicolumn{1}{c}{j}\end{array}\right)\frac{1}{m^i}\sum _{k=1}^{m-1}{(m-k)}^{(i-j)}\hfill \\ =\left(\begin{array}{c}i\hfill \\ \multicolumn{1}{c}{j}\end{array}\right)\frac{1}{m^i}\sum _{k=1}^{m-1}{k}^{(i-j)}\hfill \end{array}$$

(3)

• 2. If $j=i$

$$P_b(i,j)=\frac{m}{m^i}=\frac{1}{m^{i-1}}$$

(4)

Therefore

$$P_b(i,j)=\{\begin{array}{c}\left(\begin{array}{c}i\hfill \\ \multicolumn{1}{c}{j}\end{array}\right)\frac{1}{m^i}\sum _{k=1}^{m-1}{k}^{(i-j)},\mathrm{if}j<1\hfill \\ \multicolumn{1}{c}{\frac{1}{m^{i-1}},\mathrm{if}j=i}\end{array}$$

(5)

When the number of CD phases, h, is 1, 2, or 3, the probability of the kth success and failure cases in Figures 1–3 is expressed as follows

• 1. When $h=1$

$$P_{\mathrm{succ}}^1=P_a(1)$$

(6)

$$P_{\mathrm{succ}}^2=\sum _{i=2}^n{P}_a(i)P_b(i,1)$$

(7)

$$P_{\mathrm{fail}}^1=\sum _{i=2}^n{P}_a(i)P_b(i,i)$$

(8)

$$P_{\mathrm{fail}}^2=\sum _{i=2}^n\sum _{j=2}^{i-1}{P}_a(i)P_b(i,j)$$

(9)

• 2. When $h=2$

$$P_{\mathrm{succ}}^1=P_a(1)$$

(10)

$$P_{\mathrm{succ}}^2=\sum _{i=2}^n{P}_a(i)P_b(i,1)$$

(11)

$$P_{\mathrm{succ}}^3=\sum _{i=2}^n\sum _{j=2}^i{P}_a(i)P_b(i,j)P_b(j,1)$$

(12)

$$P_{\mathrm{fail}}^1=\sum _{i=2}^n{P}_a(i)P_b(i,i)P_b(i,i)$$

(13)

$$P_{\mathrm{fail}}^2=\sum _{i=2}^n\sum _{j=2}^{i-1}{P}_a(i)P_b(i,j)P_b(j,j)$$

(14)

$$P_{\mathrm{fail}}^3=\sum _{i=2}^n\sum _{j=2}^i\sum _{k=2}^{j-1}{P}_a(i)P_b(i,j)P_b(j,k)$$

(15)

• 3. When $h=3$

$$P_{\mathrm{succ}}^1=P_a(1)$$

(16)

$$P_{\mathrm{succ}}^2=\sum _{i=2}^n{P}_a(i)P_b(i,1)$$

(17)

$$P_{\mathrm{succ}}^3=\sum _{i=2}^n\sum _{j=2}^i{P}_a(i)P_b(i,j)P_b(j,1)$$

(18)

$$P_{\mathrm{succ}}^4=\sum _{i=2}^n\sum _{j=2}^i\sum _{k=2}^j{P}_a(i)P_b(i,j)P_b(j,k)P_b(k,1)$$

(19)

$$P_{\mathrm{fail}}^1=\sum _{i=2}^n{P}_a(i)P_b(i,i)P_b(i,i)P_b(i,i)$$

(20)

$$P_{\mathrm{fail}}^2=\sum _{i=2}^n\sum _{j=2}^{i-1}{P}_a(i)P_b(i,j)P_b(j,j)P_b(j,j)$$

(21)

$$P_{\mathrm{fail}}^3=\sum _{i=2}^n\sum _{j=2}^i\sum _{k=2}^{j-1}{P}_a(i)P_b(i,j)P_b(j,k)P_b(k,k)$$

(22)

$$P_{\mathrm{fail}}^4=\sum _{i=2}^n\sum _{j=2}^i\sum _{k=2}^j\sum _{l=2}^{k-1}{P}_a(i)P_b(i,j)P_b(j,k)P_b(k,l)$$

(23)

From the developing pattern of equations (6)–(23), we can generalize the probabilities of the kth success and failure cases for any $h\ge 1$ , as follows

$$P_{\mathrm{succ}}^1=P_a(1)$$

(24)

$$P_{succ}^k={\displaystyle \sum _{i_1=2}^n{\displaystyle \sum _{i_2=2}^{i_1}{\displaystyle \sum _{i_3=2}^{i_2}\cdots }}}{\displaystyle \sum _{i_{k-1}=2}^{i_{k-2}}{P}_a}(i_1)P_b(i_1,i_2)P_b(i_2,i_3)\cdots P_b(i_{k-1},1),\mathrm{for}k=2,3,\dots ,h+1$$

(25)

$$P_{fail}^k={\displaystyle \sum _{i_1=2}^n{\displaystyle \sum _{i_2=2}^{i_1}{\displaystyle \sum _{i_3=2}^{i_2}\dots }}}{\displaystyle \sum _{i_{k-1}=2}^{i_{k-2}}{\displaystyle \sum _{i_k=2}^{i_{k-1}-1}{P}_a}}(i_1)P_b(i_1,i_2)P_b(i_2,i_3)\dots P_b(i_{k-1},i_k)P_b{(i_k,i_k)}^{h-k+1},\mathrm{for}k=1,2,\dots ,h+1$$

(26)

Throughput analysis

Now, we derive the numerical expression of the throughput of the proposed MAC protocol. In the CSMA protocol, the system state consists of a sequence of regeneration cycles composed of consecutive busy and idle periods. ¹⁶ We define the idle period as the time during which all the stations do not transmit and the busy period as the time during which a transmission (successful or not) takes place. If n stations are contending, the expected channel idle time $T_{\mathrm{idle}}$ is calculated as follows

$$\begin{array}{cc}\multicolumn{1}{c}{T_{\mathrm{idle}}}& =T_{\mathrm{slot}}\sum _{i=1}^{\infty }i(1-P_{\mathrm{tr}}{)}^{i-1}{P}_{\mathrm{tr}}\hfill \\ \multicolumn{1}{c}{}& =\frac{T_{\mathrm{slot}}}{P_{\mathrm{tr}}}=\frac{T_{\mathrm{slot}}}{1-{(1-p)}^n}\hfill \end{array}$$

(27)

As indicated in Figures 1–3, when $h=1,2,\mathrm{or}3$ , the time consumed in the kth success and failure cases, $T_k$ , where $k=1,2,\dots ,h+1$ , is given by

• 1. When $h=1$

$$T_1=T_{\mathrm{slot}}+T_{\mathrm{data}}$$

(28)

$$T_2=T_{\mathrm{cdp}}+T_{\mathrm{data}}$$

(29)

• 2. When $h=2$

$$T_1=2T_{\mathrm{slot}}+T_{\mathrm{data}}$$

(30)

$$T_2=T_{\mathrm{cdp}}+T_{\mathrm{slot}}+T_{\mathrm{data}}$$

(31)

$$T_3=2T_{\mathrm{cdp}}+T_{\mathrm{data}}$$

(32)

• 3. When $h=3$

$$T_1=3T_{\mathrm{slot}}+T_{\mathrm{data}}$$

(33)

$$T_2=T_{\mathrm{cdp}}+2T_{\mathrm{slot}}+T_{\mathrm{data}}$$

(34)

$$T_3=2T_{\mathrm{cdp}}+T_{\mathrm{slot}}+T_{\mathrm{data}}$$

(35)

$$T_4=3T_{\mathrm{cdp}}+T_{\mathrm{data}}$$

(36)

By extending the pattern of equations (28)–(36), for any $h\ge 1$ , the time consumed in the kth success and failure cases is given by

$$\begin{array}{l}{T}_k=(k-1)T_{cdp}+(h-k+1)T_{slot}\\ +T_{data},\mathrm{for}k=1,2,\dots ,h+1\end{array}$$

(37)

The normalized throughput S is defined as the fraction of time the channel is used to successfully transmit the data packets. Because we assume the saturation condition in this work, the considered throughput means the saturation throughput, which is a fundamental performance figure defined as the limit reached by the system throughput as the offered load increases. ¹⁶ As the instants immediately after the end of a transmission are renewal points, analyzing a single renewal interval between two consecutive transmissions is sufficient; thus, the throughput S is defined as ¹⁷

$$S=\frac{E(\mathrm{time\; used\; for\; successful\; transmission\; in\; interval})}{E(\mathrm{length\; of\; a\; renewal\; interval})}$$

(38)

Therefore, the throughput of the proposed MAC protocol using h CD phases is expressed as follows

$$S(h)=\frac{\sum _{k=1}^{h+1}{P}_{\mathrm{succ}}^k{T}_{\mathrm{data}}}{T_{\mathrm{idle}}+\sum _{k=1}^{h+1}{P}_{\mathrm{succ}}^k{T}_k+\sum _{k=1}^{h+1}{P}_{\mathrm{fail}}^k{T}_k}$$

(39)

Results and discussions

We compare the proposed MAC protocol using multiple CD phases with the original CSMA/CR protocol using a single CD phase (i.e. $h=1$ ). The original CSMA/CR protocol outperforms the other conventional CSMA-based MAC protocols, such as CSMA/CA and WCSMA/CD. Thus, in this study, we omit the results for CSMA/CA and WCSMA/CD, which can be found in Choi et al. ¹¹ For evaluation, we fix the values of p, $T_{\mathrm{slot}}$ , and $T_{\mathrm{data}}$ and vary the values of n, m, and h within appropriate ranges. We set $p=0.1$ to verify the effectiveness of the proposed scheme under dense node and heavy traffic conditions. Moreover, $T_{\mathrm{slot}}$ is set to 9 µs by considering the OFDM PHY mode specified in the IEEE 802 standards^22,23 and the default of the data size $T_{\mathrm{data}}$ is set to 512 bytes under the assumption of a data transmission rate of 6 Mbps. Monte Carlo simulations are also performed to verify the analytical results.

Figure 5 shows the probability of successful transmission versus some $(h,m)$ pairs, which are chosen in order that the length of the total CD period does not exceed 20 slots (i.e. $h(m+1)\le 20$ ). As the number of CD phases (h) increases, the number of CD slots per phase (m) decreases. Therefore, the probability of successful transmission initially increases but begins to decrease at $h=5$ in all cases of the number of stations (n). This is because the initial increase in h is effective to resolve the collision, but the reduced m induces more collisions in each CD phase. Hence, there exists an appropriate $(h,m)$ pair that maximizes the probability of successful transmission.

Figure 5.

Transmission success probability versus $(h,m)$ pair subject to $h(m+1)\le 20$ .

Figure 6 shows the normalized throughput versus the number of stations for some $(h,m)$ pairs subject to $h(m+1)\le 20$ . The throughput decreases as the number of stations increases because of the increase in access collision. Compared to the typical CSMA/CR (i.e. $h=1$ ), the proposed scheme (i.e. $h\ge 2$ ) significantly improves the throughput although a smaller m is used. However, as h increases, the performance gain is gradually reduced and the throughput is maximized at $h=4$ , because a large value of h diminishes the m value and induces more collisions in each CD phase. Therefore, it is noteworthy that the proposed scheme has a suitable $(h,m)$ pair that will maximize the throughput.

Figure 6.

Throughput versus number of stations subject to $h(m+1)\le 20$ .

We now investigate the throughput when one of the parameters h and m is fixed while the other is variable. Figure 7 shows the throughput versus the number of stations (n) when h is fixed as 2 and m is variable. For smaller values of n, it is better to decrease m because of the overhead of the longer CD period. On the contrary, for larger values of n, it is better to increase m in order to decrease access collisions. Therefore, there exists an appropriate m that maximizes the throughput according to n when h is fixed. On the other hand, Figure 8 shows the throughput versus the number of stations when h is variable and m is fixed as 10. As h increases, the throughput improves because multiple CD phases increase the probability of successful transmission. However, an excessively large h decreases the throughput, because it increases the overhead of the total CD period. Similarly, there exists a suitable h that maximizes the throughput when m is fixed.

Figure 7.

Throughput versus number of stations when h is fixed as 2 and m is variable.

Figure 8.

Throughput versus number of stations when h is variable and m is fixed as 10.

Figure 9 shows the throughput versus the $(h,m)$ pair when n is fixed as 500. As both h and m increase, the throughput increases sharply but begins to decrease gradually at a certain point. That is, the throughput follows a concave form as a function of h and m and it reaches the maximum at $(h,m{)}^{*}=(6,4)$ . The reason why the decreasing rate of the throughput is smaller than the increasing rate is because once the collision is resolved at a certain CD phase, all the transmitted data except just one CD slot per phase in the following CD phase are valid. Namely, the excessively allocated CD phases do not induce a significant throughput degradation, which is a good property of the proposed scheme.

Figure 9.

Throughput versus $(h,m)$ pair when $n=500$ .

Figure 10 shows the optimal $(h,m)$ pair as a function of the number of stations. Here, the optimal $(h,m)$ pair that maximizes the throughput was found by exhaustive search. Interestingly, the optimal value of m is fixed as 4 except when $n\le 20$ . On the other hand, the optimal value of h gradually increases from 4 to 6 as n increases. The reason why the optimal value of m is fixed as 4, which is smaller than the optimal value of h, is because it is more effective for CR to reduce the number of contending stations in each CD phase by increasing h rather than to reduce the collision probability within each CD phase by increasing m. This observation informs that the use of multiple CD phases is more effective to the throughput improvement than the use of long CD period, and this proves the effectiveness of the proposed scheme. In addition, the optimal value of h gradually increases and approaches 6 even when the number of stations increases to 1000. This is due to the fact that the proposed MAC protocol, the number of contending stations significantly decreases as the CD phase proceeds because the only stations that choose the earliest CD slot are filtered in each CD phase and retry at the next CD phase. These results show the desirable performance of the proposed MAC protocol which does not require a large value of h and m even in a dense network with a large number of accessing stations.

Figure 10.

Optimal $(h,m)$ pair versus number of stations.

Figure 11 shows the throughput versus the number of stations when the optimal $(h,m)$ pair obtained in Figure 10 is applied. For comparison, we fix h and obtain again the optimal m that maximizes the throughput. As shown, the highest throughput is always achieved when the optimal $(h,m)$ pair is applied based on the change in the number of stations.

Figure 11.

Throughput versus number of stations when the optimal $(h,m)$ pair is applied.

Implementation issue

We discuss some implementation issues that should be considered for the practical use of the proposed MAC protocol. Most importantly, we need to investigate how to design the jam signal and decide the length of the CD slot for the reliable detection of collision. The IEEE 802.11 or IEEE 802.15.4 standard specifies the clear channel assessment (CCA) method.^22,23 This judges that the channel is busy through a energy detection or a carrier sensing or both. The carrier sensing detects a carrier signal with a specific pattern, such as the preamble used in the physical (PHY) layer or the direct sequence spread spectrum (DSSS) signal in the DSSS PHY mode. When this CCA method is utilized, the standard specifies a required CCA time ( $T_{\mathrm{CCA}}$ ) and defines a slot time ( $T_{\mathrm{slot}}$ ) as a basic time unit, which is the minimum time required for the channel sensing and accessing, as follows

$$\begin{array}{l}{T}_{Slot}=T_{CCA}+T_{RxTxTurnaround}\\ +T_{AirPropagation}+T_{MACProcessing}\end{array}$$

(40)

where $T_{\mathrm{RxTxTurnaround}}$ denotes the maximum time that the PHY layer requires to change the mode from receiving to transmitting, $T_{\mathrm{AirPropagation}}$ denotes the maximum propagation time for a signal to travel between two stations at the maximum distance within the network, and $T_{\mathrm{MACProcessing}}$ denotes the maximum time required for the MAC to generate a request primitive to the PHY.

It is possible for the proposed MAC protocol to detect the jam signal within $T_{\mathrm{CCA}}$ if we design the jam signal pattern similar to but distinguishable from the preamble in the IEEE 802.15.4 or 802.11 standard. However, the proposed MAC protocol needs a Tx–Rx–Tx transition for sensing in the middle of transmission; thus, a Tx/Rx turnaround time should be added to the basic slot time. Therefore, the required length of CD slot should satisfy this condition

$$T_{\mathrm{CDSlot}}\ge T_{\mathrm{Slot}}+T_{\mathrm{TxRxTurnaround}}$$

(41)

where $T_{\mathrm{TxRxTurnaround}}$ is the maximum time that the PHY layer requires to change the mode from transmitting to receiving.

In addition, $T_{\mathrm{CDSlot}}$ must be shorter than the distributed inter-frame space (DIFS) time in order to make other stations do not intervene during the CD slot time. In the standard, the DIFS time is defined as $T_{\mathrm{SIFS}}+2T_{\mathrm{Slot}}$ where $T_{\mathrm{SIFS}}$ is the SIFS time. By considering this upper bound and equations (40) and (41), we can finally determine the condition for the length of the CD slot as follows

$$\begin{array}{l}{T}_{CCA}+T_{RxTxTurnaround}+T_{AirPropagation}\\ +T_{MACProcessing}+T_{TxRxTurnaround}\le T_{CDSlot}\\ <T_{SIFS}+2T_{Slot}\end{array}$$

(42)

Conclusion

In this article, we proposed a distributed MAC protocol using a successive CD technique in a dense WSN environment. Numerical results showed that the proposed MAC protocol using multiple CD phases significantly improves the conventional CSMA/CR protocol using a single CD phases. The results also showed that under the conditions of the same length of the total CD period, the increase in the number of CD phases (h) is more effective for achieving successful transmission than the increase in the number of CD slots per phase (m). Regarding the parameters h and m, we revealed that there exists an optimal $(h,m)$ pair that maximizes the throughput and h is more sensitive to the performance than m. This verifies that the use of successive multiple CD phases in the proposed scheme is effective to the throughput improvement. Taking into account its improved performance and practicality, we expect that the proposed MAC protocol can be useful in future dense WSN with massive IoT devices.