# Efficient MAC Protocol for Hybrid Wireless Network with Heterogeneous Sensor Nodes

Authors: Md. Nasre Alam; Young-Chon Kim
Journal: Journal of Sensors
 (2016)

---

## Abstract

Although several Directional Medium Access Control (DMAC) protocols have been designed for use with homogeneous networks, it can take a substantial amount of time to change sensor nodes that are equipped with an omnidirectional antenna for sensor nodes with a directional antenna. Thus, we require a novel MAC protocol for use with an intermediate wireless network that consists of heterogeneous sensor nodes equipped with either an omnidirectional antenna or a directional antenna. The MAC protocols that have been designed for use in homogeneous networks are not suitable for use in a hybrid network due to deaf, hidden, and exposed nodes. Therefore, we propose a MAC protocol that exploits the characteristics of a directional antenna and can also work efficiently with omnidirectional nodes in a hybrid network. In order to address the deaf, hidden, and exposed node problems, we define RTS/CTS for the neighbor (RTSN/CTSN) and Neighbor Information (NIP) packets. The performance of the proposed MAC protocol is evaluated through a numerical analysis using a Markov model. In addition, the analytical results of the MAC protocol are verified through an OPNET simulation.


---

## Body

## 1. Introduction

In wireless networks, directional antennas can be used to achieve a higher spatial reuse and, thus, a higher network throughput. Several MAC protocols have been proposed for use with a directional antenna in wireless networks, and these protocols assume that all nodes in the network have homogenous antennas [1–5]. However, it is difficult in practice to replace all of the sensor nodes that are equipped with an isotropic antenna with sensor nodes with a directional antenna. Thus, we should consider an intermediate wireless network that consists of heterogeneous nodes that are equipped with either an omnidirectional antenna or a directional antenna, and we refer to such a network as a hybrid network. However, existing MAC protocols are not suitable for use in hybrid networks because these protocols were originally designed for use in homogenous networks. The lack of appropriate MAC protocols for use in hybrid networks results in serious issues related to deafness, hidden terminals, and exposed nodes. The overall performance of the network may deteriorate beyond that of an omnidirectional network [6]. Therefore, we need to design a heterogeneity-aware directional MAC protocol that works efficiently with directional as well as omnidirectional nodes [7].The use of a directional antenna in a wireless network reduces the number of nodes that are blocked and achieves a higher spatial reuse. However, the Directional Medium Access Control (DMAC) protocol faces several challenges in the presence of deaf nodes, hidden nodes, and exposed nodes [3–5, 7, 8], and these problems are more severe with a hybrid network. Hidden and exposed nodes are located near the source node and may not hear the transmission from the source. Therefore, they may initiate a transmission that results in a collision.In this paper, we propose a MAC protocol that is designed for use in a hybrid network that works efficiently with heterogeneous sensor nodes in the network. The characteristics of a directional antenna are exploited, and the MAC protocol is also compatible with nodes equipped with a traditional omnidirectional antenna. The protocol helps for improving the throughput of the hybrid network by minimizing the negative impact of the deaf nodes, hidden nodes, and exposed nodes. The protocol uses a concurrent RTS/CTS for Neighbor (RTSN/CTSN) transmission scheme after the channel has been reserved by directional communicating nodes to make a neighbor aware of the imminent communication, which minimizes the deaf node problem. The transmission of the Neighbor Information Packet (NIP) by the over hearer idle nodes minimizes the hidden node problem. Moreover, we proposed a scheme to set the Network Allocation Vectors (NAV) by the omnidirectional nodes to minimize exposed node problems in the network. Finally, we evaluate the proposed MAC protocol through a numerical analysis using a Markov model. We focus on evaluating the performance of our proposed MAC with the assumption that ideal channel circumstances and a fixed number of nodes are observed in the network. A simulation is conducted using the OPNET simulator to validate the accuracy of the results.The rest of this paper is organized as follows. We present the related work in the following section. Section3 describes the MAC protocol that is herein proposed. Section 4 provides a numerical analysis of the proposed system. Section 5 discusses the results of the performance for our proposed MAC, and we finally conclude the paper in Section 6.


## 2. Related Work

Several MAC protocols have been designed and analyzed for use in wireless networks. In [9] a scheme is proposed to transmit Circular RTS (CRTS) in order to inform the entire neighborhood of future transmissions. Each node maintains a location table for its neighbors, and the CTS is sent directionally (DCTS) towards an RTS originator. As a result of the CRTS, the deafness and the hidden node problems are reduced. However, DCTS still results in some deafness and hidden node problems. In [10] the communicating nodes transmit multiple control packets before the data is transmitted. The communicating nodes (sender and receiver) successively transmit multiple control packets, such as RTS and CTS, through all beams. The neighbor of the nodes blocks their corresponding beam after the control packet is heard. Since the control packets are transmitted around the sender and the receiver, the neighboring nodes become aware of the ongoing communication. In a similar manner, authors in [5, 11, 12] proposed transmitting multiple control packet to the neighborhood before data communication. Although, there is little overhead due to the location table maintenance and the transmission of multiple control packets, there is an increase in the spatial reuse. However, the problems related to deaf, hidden, and exposed nodes are not completely solved.Figure1 shows an example of the hidden, exposed, and deaf node problems that is described in [1, 3, 5, 7–9, 11, 13–15]. In theory, a node that is located within the communication range of the receiving node and is out of the coverage range of the sender node can remain hidden and can cause a hidden node problem. Figure 1(a) shows an example of the hidden node problem. The A, B, and C nodes are within the coverage range of receiver R but are out of the coverage range of the sender S. Therefore, the nodes may be hidden during communication between the S and R nodes, which results in a hidden node problem.Figure 1
Issues with a directional antenna: (a) hidden node problem and (b) deaf node problem.
(a)
(b)In a hybrid network, the exposed node problem is more severe than in a homogeneous network, and more attention is needed [1, 7, 10, 16]. For example, if a node with an isotropic antenna transmits omnidirectional RTS (ORTS) and/or OCTS, the node with directional antenna will unnecessarily block the sectors that can be used for a concurrent transmission. Therefore, the hidden and exposed node problems can severely degrade the performance of the network [1].A node fails to communicate with the intended receiver node when the node is communicating with a different node. For example, in Figure1(b), node X tries to communicate with node S, but node S is communicating with node R. As a result, node S is deaf with respect to node X.Instead of a transmission with multiple control packets, the scheme in [14, 15] uses communicating nodes that notify the potential sender by sending additional control packets. In the scheme in [16], when a node finishes communication, a ready-to-receive (RTR) frame is transmitted to the potential sender. In the scheme in [15], when a communicating node receives RTS/CTS from other nodes, it transmits Additional RTS (A-RTS) to its potential sender.In the schemes in [1, 3], the authors proposed a dual carrier sensing scheme to address the hidden, exposed, and deaf nodes. In the scheme in [1], the proposed DSDMAC protocol uses two well-separated wireless channels to transmit data and a busy tone. The data channel carries data and control packets while the busy-tone channel is used to transmit a busy-tone sine-wave signal. On the data channel, the packet will transmit directionally while the packet will transmit omnidirectionally on the busy-tone channel. In the scheme in [3], the author proposed a DA-MAC protocol that also uses two separate wireless channels to transmit the data and control packets. In that scheme, the data and control packet transmission is directional while the nodes listen to the channel through all beams. After overhearing the packet, the neighbor nodes block the corresponding beam at the data channel but continue listening at the control channel. If a node wants to communicate with another node that blocks the data channel beam, the former replies with a DCTS at the control channel. If the communicating nodes exchange RTS and CTS over both channels, then they can transmit data.However, the previous schemes are only designed for use with homogeneous networks and will not perform well when used with hybrid networks [7]. In a hybrid network, the exposed node problem is more severe than that of a homogeneous network.


## 3. The Proposed MAC

In this section, we discuss the detailed mechanism of the proposed MAC protocol. The basic concept, including interframe spacing, the binary backoff, and the congestion mechanism, is taken from the IEEE 802.11 Distributed Coordination Function (DCF) standard. The proposed MAC protocol is designed for use with a hybrid wireless network with two types of sensor nodes, including an (1) omnidirectional node equipped with an isotropic antenna and (2) a Directional node equipped with a Multibeam Smart Antenna (MBSA). The MBSA can formM number of nonoverlapping beams to cover the entire 360° area around the node, and the beams are pointed in a fixed direction. A packet can be transmitted or received concurrently by using all beams and can achieve a higher range of transmission in all directions. Therefore, a node can transmit/receive packets through any/all of these beams.The node in the network does not consider caching the Angle of Arrival (AoA) and the beam locking/unlocking feature presented in traditional DMAC protocols. We maintain the location table that contains the location of the one-hop neighbors in the Neighbor Information Table (NIT).


### 3.1. Neighbor Determination

In order to determine the location of the neighborhood, we use a gossip algorithm in which a node sends a “hello packet” to its one-hop neighbors. When a node receives the “hello packet” from the other nodes, it stores the neighbor’s address and the receiving sector number in the NIT. When an omnidirectional node receives the packet, it stores the neighbor’s address in the NIT and the beam number field value will always be zero. Algorithm1 shows the algorithm that is used to determine the neighbor’s location for the system model.Algorithm 1:Neighbor determination algorithm.
(1) Procedure neighbor_determination
(2)     if (node = omni)
(3)       if (hello packet receive)
(4)           nit.neighbor_add = packet.add
(5)           nit.beam_number = 0
(6)           nit.beam_status = free
(7)       end if
(8)       else
(9)           transmit hello packet omni directional
(10)end
(11)      end if
(12)      else
(13)If (hello packet receive)
(14)            nit.neighbor_add = packet.add
(15)            nit.beam_number = packet.sector
(16)            nit.beam_status = free
(17)end if
(18)else
(19)            transmit hello packet through all beams
(20)end
(21)      end
(22)  end


### 3.2. Channel Sensing

The omnidirectional nodes sense the channel as traditional MAC protocols, and the directional node senses the channel through an MBSA that hasM number of nonoverlapping beams fixed in different sectors around the node. The nodes that hear the transmission through any of the beams set their Directional Network Allocation Vector (DNAV) and continue to sense the channel through the other beams.


### 3.3. Packet Transmission

The omnidirectional node transmits a packet by following the traditional approach of the IEEE 802.11 MAC protocol. A node simply transmits an omnidirectional packet, and if a directional node has a packet, it sends a Directional RTS (DRTS) only towards the destination node while the receiver node replies with a Directional CTS (DCTS) only towards the sender node. After a successful DRTS/DCTS handshake, the communicating nodes send RTSN and CTSN concurrently toward their vicinity through other beams to inform the neighbors of the impending communication. Then the nodes start the DATA communication. The other beams of the communicating nodes are blocked for the communication. Algorithm2 shows the algorithm to transmit the packet for our proposed MAC.Algorithm 2:Packet transmission algorithm.
(1)Procedure Pkt_Tx
(2)     if (node == omni)
(3)        Pkt.sector = 0
(4)        send Packet to antenna controller
(5)     else
(6)        i
=
0
(7)        while (nit[i].add NOT dest_add)
(8)          i
=
i
+
1
(9)        end while
(10)          sector = nit[i].sector
(11)           if (pkt = RTS)
(12)       RTS.sector = sector
(13)       send RTS to antenna controller
(14)       wait CTS_timeout + SIFS
(15)       if (CTS received)
(16)         RTS.sector = 0
(17)         send RTS to antenna controller
(18)       else
(19)         Retransmit
(20)           else if (pkt = CTS)
(21)       CTS.sector = sector
(22)       send CTS to antenna controller
(23)       wait for SIFS time
(24)       CTS.secor = 0
(25)       send CTS to antenna controller
(26)           else
(27)       DATA/ACK.sector = sector
(28)       send DATA/ACK to antenna controller
(29) End


### 3.4. Packet Reception

The omnidirectional nodes follow the same approach that is used in a traditional IEEE 802.11 MAC protocol, but setting the NAV is quite different. When a directional node overhears the DRTS/DCTS/ORTS/OCTS, it sets NAV1. If the packet is RTSN/CTSN, then it sets NAV2. When a directional node receives DRTS, it replies with a DCTS and waits for the CTS-timeout + SIFS period. Then, RTSN is transmitted to its vicinity after the SIFS time, and then data communication starts. The rest of the beams are deactivated for transmission/reception during communication. When a node overhears a packet, it sets DNAV for the receiving beam and continues channel sensing through other beams. Algorithm3 depicts the algorithm that is used to receive the packet in our system model.Algorithm 3:Packet reception algorithm.
(1)Procedure Pkt_Rx
(2)     if (packet recvd AND pkt.dest_add = self_add)
(3)        if (node = omni)
(4)             if (packet = RTS)
(5)             CTS.sector = 0
(6)             send CTS to antenna controller
(7) else if (packet = CTS)
(8)             wait for DATA
(9) else if (packet = DATA)
(10)  ACK.sector = 0
(11)  send ACK to antenna controller
(12)else
(13)  transmission complete
(14)  go to End
(15)         else
(16)          if (packet = RTS)
(17)  CTS.sector = RTS.sector
(18)  send CTS to antenna controller
(19)  wait for SIFS time
(20)  CTS.sector = 0
(21)  send CTS to antenna controller
(22)          else if (packet = CTS)
(23)  RTS.sector = 0
(24)  send RTS to antenna controller
(25)  wait for SIFS
(26)  DATA.sector = CTS.sector
(27)  send DATA to antenna controller
(28)          else if (packet = DATA)
(29)  ACK.sector = DATA.sector
(30)  send ACK to antenna controller
(31)          else
(32)  transmission complete
(33)  go to End
(34)      else if (packet recvd AND pkt.dest_add NOT self_add)
(35)         if (node = omni)
(36)          if (packet = RTSN/CTSN)
(37)  set NAV2
(38)          else
(39)  set NAV1
(40)         else
(41)          set DNAV for the beam
(42)          nit.beam_status = BLOCKED
(43)      else
(44)         sense the channel through its all beams
(45) End


### 3.5. NAV and DNAV

The Network Allocation Vector (NAV) and the Directional Network Allocation Vector (DNAV) comprise the virtual carrier sensing mechanism that is used with the wireless network protocols. The NAV mechanism is used by the omnidirectional MAC protocols, and the DNAV is used by the directional MAC protocol. Since our system model is designed for hybrid network, we follow both the mechanisms for virtual carrier sensing. In our system model, the omnidirectional nodes follow the NAV mechanism, and the directional nodes follow the DNAV mechanism.We proposed two types of NAV for the omnidirectional nodes in the network: NAV1 and NAV2. When a node overhears the RTS/CTS packet, it means the node is in the same communication sector, and its transmission may interrupt ongoing communication. Therefore, the node sets NAV1 and defers the transmission until NAV1 does not expire. When a node overhears RTSN/CTSN, it means that the node is not in the same communication sector, and its communication with other nodes will not interrupt the ongoing communication. Therefore, it sets NAV2 and can communicate with other nodes in the network. Thus, we increase the spatial reuse in the network by minimizing the exposed node problem.When a directional node overhears the packet, it sets DNAV for the respective beam. The node updates the DNAV table upon overhearing every packet in that direction and defers its transmission for the duration of the communication.


### 3.6. Channel Access Mechanism

Figure2 shows the basic operation, including the channel access mechanism, the scheme to set NAV/DNAV, and the control packet transmission for the proposed MAC protocol. In the figure, nodes A, B, and F are directional nodes, and nodes C, D, and E are omnidirectional nodes.Figure 2
Access mechanism of the proposed MAC.Step 1.
NodeA sends DRTS to node B.Step 2.
NodeB responds with DCTS.Step 3.
NodesA and B transmit RTSN and CTSN, respectively. The RTSN and CTSN are transmitted concurrently through all beams, except the communicating beams (the beams are pointed towards the sender and receiver node). Nodes E and D set NAV2 (since nodes E and D do not reside in the communicating sector so they hear RTSN/CTSN and can communicate with other nodes in the network. It overcomes exposed node problem) whereas node C sets NAV1 (since node C resides in the communicating sector, so it sets NAV1 and cannot communicate during the communication of nodes A and B).Step 4.
NodeA starts DATA transmission.Step 5.
NodeD initiates communication to node E by sending ORTS.Step 6.
NodeE responds with OCTS.Step 7.
NodeE starts data communication.Step 8.
NodesA and B finish their communication.Step 9.
NodeF sends NIP (since nodes A and B are unaware about the communication of nodes E and D due to their communication) packet to node A.The NIP packet carries communicating node ids and the remaining duration of their communication. When a node receives a NIP packet, it extracts the communicating node ids and sets the DNAV/NAV for the remaining duration given in the packet.


## 3.1. Neighbor Determination

In order to determine the location of the neighborhood, we use a gossip algorithm in which a node sends a “hello packet” to its one-hop neighbors. When a node receives the “hello packet” from the other nodes, it stores the neighbor’s address and the receiving sector number in the NIT. When an omnidirectional node receives the packet, it stores the neighbor’s address in the NIT and the beam number field value will always be zero. Algorithm1 shows the algorithm that is used to determine the neighbor’s location for the system model.Algorithm 1:Neighbor determination algorithm.
(1) Procedure neighbor_determination
(2)     if (node = omni)
(3)       if (hello packet receive)
(4)           nit.neighbor_add = packet.add
(5)           nit.beam_number = 0
(6)           nit.beam_status = free
(7)       end if
(8)       else
(9)           transmit hello packet omni directional
(10)end
(11)      end if
(12)      else
(13)If (hello packet receive)
(14)            nit.neighbor_add = packet.add
(15)            nit.beam_number = packet.sector
(16)            nit.beam_status = free
(17)end if
(18)else
(19)            transmit hello packet through all beams
(20)end
(21)      end
(22)  end


## 3.2. Channel Sensing

The omnidirectional nodes sense the channel as traditional MAC protocols, and the directional node senses the channel through an MBSA that hasM number of nonoverlapping beams fixed in different sectors around the node. The nodes that hear the transmission through any of the beams set their Directional Network Allocation Vector (DNAV) and continue to sense the channel through the other beams.


## 3.3. Packet Transmission

The omnidirectional node transmits a packet by following the traditional approach of the IEEE 802.11 MAC protocol. A node simply transmits an omnidirectional packet, and if a directional node has a packet, it sends a Directional RTS (DRTS) only towards the destination node while the receiver node replies with a Directional CTS (DCTS) only towards the sender node. After a successful DRTS/DCTS handshake, the communicating nodes send RTSN and CTSN concurrently toward their vicinity through other beams to inform the neighbors of the impending communication. Then the nodes start the DATA communication. The other beams of the communicating nodes are blocked for the communication. Algorithm2 shows the algorithm to transmit the packet for our proposed MAC.Algorithm 2:Packet transmission algorithm.
(1)Procedure Pkt_Tx
(2)     if (node == omni)
(3)        Pkt.sector = 0
(4)        send Packet to antenna controller
(5)     else
(6)        i
=
0
(7)        while (nit[i].add NOT dest_add)
(8)          i
=
i
+
1
(9)        end while
(10)          sector = nit[i].sector
(11)           if (pkt = RTS)
(12)       RTS.sector = sector
(13)       send RTS to antenna controller
(14)       wait CTS_timeout + SIFS
(15)       if (CTS received)
(16)         RTS.sector = 0
(17)         send RTS to antenna controller
(18)       else
(19)         Retransmit
(20)           else if (pkt = CTS)
(21)       CTS.sector = sector
(22)       send CTS to antenna controller
(23)       wait for SIFS time
(24)       CTS.secor = 0
(25)       send CTS to antenna controller
(26)           else
(27)       DATA/ACK.sector = sector
(28)       send DATA/ACK to antenna controller
(29) End


## 3.4. Packet Reception

The omnidirectional nodes follow the same approach that is used in a traditional IEEE 802.11 MAC protocol, but setting the NAV is quite different. When a directional node overhears the DRTS/DCTS/ORTS/OCTS, it sets NAV1. If the packet is RTSN/CTSN, then it sets NAV2. When a directional node receives DRTS, it replies with a DCTS and waits for the CTS-timeout + SIFS period. Then, RTSN is transmitted to its vicinity after the SIFS time, and then data communication starts. The rest of the beams are deactivated for transmission/reception during communication. When a node overhears a packet, it sets DNAV for the receiving beam and continues channel sensing through other beams. Algorithm3 depicts the algorithm that is used to receive the packet in our system model.Algorithm 3:Packet reception algorithm.
(1)Procedure Pkt_Rx
(2)     if (packet recvd AND pkt.dest_add = self_add)
(3)        if (node = omni)
(4)             if (packet = RTS)
(5)             CTS.sector = 0
(6)             send CTS to antenna controller
(7) else if (packet = CTS)
(8)             wait for DATA
(9) else if (packet = DATA)
(10)  ACK.sector = 0
(11)  send ACK to antenna controller
(12)else
(13)  transmission complete
(14)  go to End
(15)         else
(16)          if (packet = RTS)
(17)  CTS.sector = RTS.sector
(18)  send CTS to antenna controller
(19)  wait for SIFS time
(20)  CTS.sector = 0
(21)  send CTS to antenna controller
(22)          else if (packet = CTS)
(23)  RTS.sector = 0
(24)  send RTS to antenna controller
(25)  wait for SIFS
(26)  DATA.sector = CTS.sector
(27)  send DATA to antenna controller
(28)          else if (packet = DATA)
(29)  ACK.sector = DATA.sector
(30)  send ACK to antenna controller
(31)          else
(32)  transmission complete
(33)  go to End
(34)      else if (packet recvd AND pkt.dest_add NOT self_add)
(35)         if (node = omni)
(36)          if (packet = RTSN/CTSN)
(37)  set NAV2
(38)          else
(39)  set NAV1
(40)         else
(41)          set DNAV for the beam
(42)          nit.beam_status = BLOCKED
(43)      else
(44)         sense the channel through its all beams
(45) End


## 3.5. NAV and DNAV

The Network Allocation Vector (NAV) and the Directional Network Allocation Vector (DNAV) comprise the virtual carrier sensing mechanism that is used with the wireless network protocols. The NAV mechanism is used by the omnidirectional MAC protocols, and the DNAV is used by the directional MAC protocol. Since our system model is designed for hybrid network, we follow both the mechanisms for virtual carrier sensing. In our system model, the omnidirectional nodes follow the NAV mechanism, and the directional nodes follow the DNAV mechanism.We proposed two types of NAV for the omnidirectional nodes in the network: NAV1 and NAV2. When a node overhears the RTS/CTS packet, it means the node is in the same communication sector, and its transmission may interrupt ongoing communication. Therefore, the node sets NAV1 and defers the transmission until NAV1 does not expire. When a node overhears RTSN/CTSN, it means that the node is not in the same communication sector, and its communication with other nodes will not interrupt the ongoing communication. Therefore, it sets NAV2 and can communicate with other nodes in the network. Thus, we increase the spatial reuse in the network by minimizing the exposed node problem.When a directional node overhears the packet, it sets DNAV for the respective beam. The node updates the DNAV table upon overhearing every packet in that direction and defers its transmission for the duration of the communication.


## 3.6. Channel Access Mechanism

Figure2 shows the basic operation, including the channel access mechanism, the scheme to set NAV/DNAV, and the control packet transmission for the proposed MAC protocol. In the figure, nodes A, B, and F are directional nodes, and nodes C, D, and E are omnidirectional nodes.Figure 2
Access mechanism of the proposed MAC.Step 1.
NodeA sends DRTS to node B.Step 2.
NodeB responds with DCTS.Step 3.
NodesA and B transmit RTSN and CTSN, respectively. The RTSN and CTSN are transmitted concurrently through all beams, except the communicating beams (the beams are pointed towards the sender and receiver node). Nodes E and D set NAV2 (since nodes E and D do not reside in the communicating sector so they hear RTSN/CTSN and can communicate with other nodes in the network. It overcomes exposed node problem) whereas node C sets NAV1 (since node C resides in the communicating sector, so it sets NAV1 and cannot communicate during the communication of nodes A and B).Step 4.
NodeA starts DATA transmission.Step 5.
NodeD initiates communication to node E by sending ORTS.Step 6.
NodeE responds with OCTS.Step 7.
NodeE starts data communication.Step 8.
NodesA and B finish their communication.Step 9.
NodeF sends NIP (since nodes A and B are unaware about the communication of nodes E and D due to their communication) packet to node A.The NIP packet carries communicating node ids and the remaining duration of their communication. When a node receives a NIP packet, it extracts the communicating node ids and sets the DNAV/NAV for the remaining duration given in the packet.


## 4. Numerical Analysis

In this section, we use a mathematical approach to study the performance of our proposed MAC protocol. We analyze the aggregate throughput (the average information payload transmitted in a time slot over the average duration of the time slot) with a discrete-time Markov chain model that assumes a finite number of nodes. We assume that all nodes always have data to send, and we also assume that all of the control frames, except the DRTS frame, are always successfully delivered to the destination node. Since our MAC protocol is particularly designed for use with a hybrid network, we have designed two state transition diagrams. Figures3 and 4 show the state transition process of a node represented by a discrete-time Markov chain model for omnidirectional and directional nodes.Figure 3
State diagram of an omnidirectional node.Figure 4
State diagram of a directional node.In Figure3, let the steady-state probability of the Markov chain of the omnidirectional node be denoted as π
o
i, π
o
c, π
o
t, π
o
t
c, π
o
r, π
o
o, and π
o
n and the time periods during which a node is in the corresponding states be T
o
i, T
o
c, T
o
t, T
o
t
c, T
o
r, T
o
o, and T
o
n, where “o” indicates an omnidirectional node and i, c, t, t
c, r, o, and n represent the “idle,” “wait for CTS,” “transmit,” “transmit-CTS,” “receive,” “overhear,” and “nip” states, respectively.Similarly, the steady-state probability of the Markov chain of the directional node in Figure4 is denoted by π
d
i, π
d
c, π
d
r
n, π
d
t, π
d
t
c, π
d
t
c
n, π
d
r, π
d
o, and π
d
n and the time periods during which a node is in the corresponding states are T
d
i, T
d
c, T
d
r
n, T
d
t, T
d
t
c, T
d
t
c
n, T
d
r, T
d
o, and T
d
n, where “d” denotes a directional node and i, c, r
n, t, t
c, t
c
n, r, o, and n represent the “idle,” “wait for CTS,” “tx-RTSN,” “transmit,” “transmit-CTS,” “tx-CTSN,” “receive,” “overhear,” and “nip” states, respectively.The Tx-RTS, Tx-ACK, and Wait-for-ACK states are not depicted in Figures3 and 4; we merge the Tx-RTS, Tx-ACK, and Wait-for-ACK state with IDLE, Receive, and Transmit state, respectively.


### 4.1. Derivation of Transition Probability

In this section, we derive the transition probability from moving one state to another state for both omnidirectional and directional nodes.First, we can deriveP
o
i
c and P
d
i
c as(1)
P
o
i
c
=
Pr
⁡
N
o
d
e
t
r
a
n
s
m
i
t
s
R
T
S
i
n
t
h
e
f
i
r
s
t
b
a
c
k
o
f
f
s
t
a
g
e
=
τ
o
1
,
P
d
i
c
=
Pr
⁡
N
o
d
e
t
r
a
n
s
m
i
t
s
D
R
T
S
i
n
t
h
e
f
i
r
s
t
b
a
c
k
o
f
f
s
t
a
g
e
=
τ
d
1
.We consider the same random backoff scheme as in [17] for our proposed MAC protocol. For that scheme, the authors calculated the probability τ
1 that a node transmits in the first backoff stage using the backoff Markov chain model:(2)
τ
1
=
2
1
-
2
p
1
-
p
1
-
2
p
W
0
+
1
+
p
W
0
1
-
2
p
m
,where τ
1 denotes the probability that a node transmits in the first backoff stage, p is the conditional probability, W
0 is the minimum contention window size, and m is the maximum number of the stages. Further, they calculated p as(3)
p
=
1
-
1
-
τ
N
-
2
,where τ denotes the probability that a node transmits in a random slot time for all backoff stages and can be calculated as follows:(4)
τ
=
2
1
-
2
p
1
-
2
p
W
0
+
1
+
p
W
0
1
-
2
p
m
.Since the network is a hybrid, we can rewrite (2) for P
o
i
c and P
d
i
c as (5)
τ
o
1
=
2
1
-
2
p
o
1
-
p
o
1
-
2
p
o
W
0
+
1
+
p
o
W
0
1
-
2
p
o
m
,
τ
d
1
=
2
1
-
2
p
d
1
-
p
d
1
-
2
p
d
W
0
+
1
+
p
d
W
0
1
-
2
p
d
m
.
p
o and p
d denote the collision probability of omnidirectional and directional nodes, respectively. To calculate the conditional probabilities, we can rewrite (3) as (6)
p
o
=
1
-
1
-
1
M
·
n
d
N
·
τ
d
+
n
o
N
·
τ
o
N
-
2
,
p
d
=
1
-
1
-
1
M
2
·
n
d
N
·
τ
d
+
1
M
·
n
o
N
·
τ
o
N
-
2
,where n
d, n
o, N, and M denote the “number of directional nodes, number of omnidirectional nodes, total number of nodes in the network, and number of beams,” respectively. τ
o and τ
d are the probability that a node transmits in a random time slot for all backoff stages. It can be calculated by rewriting (4) as(7)
τ
o
=
2
1
-
2
p
o
1
-
2
p
o
W
0
+
1
+
p
o
W
0
1
-
2
p
o
m
,
τ
d
=
2
1
-
2
p
d
1
-
2
p
d
W
0
+
1
+
p
d
W
0
1
-
2
p
d
m
.Next, we can derive P
o
c
t, P
d
c
r
n, and P
d
r
n
t, since there is only one transition P
d
r
n
t to move from the π
d
r
n to the π
d
t state.Therefore,(8)
P
d
r
n
t
=
P
d
c
r
n
,
P
o
c
t
=
P
d
c
r
n
=
Pr
⁡
n
o
o
t
h
e
r
t
r
a
n
s
m
i
s
s
i
o
n
i
n
t
h
e
s
e
c
t
o
r
o
r
r
e
c
e
i
v
e
r
r
a
n
g
e
=
1
-
1
M
·
n
d
N
·
τ
d
+
n
o
N
·
τ
o
N
-
2
.We can derive P
o
c
i and P
d
c
i as (9)
P
o
c
i
=
P
d
c
i
=
Pr
⁡
sender  does  not  receive  any  response  within  retransmission  limit
k
=
p
k
+
1and P
o
c
c and P
d
c
c can be calculated as(10)
P
o
c
c
=
1
-
P
o
c
i
+
P
o
c
t
,
P
d
c
c
=
1
-
P
d
c
i
+
P
d
c
r
n
.Similarly we can derive P
o
i
t
c and P
d
i
t
c, as (11)
P
o
i
t
c
=
P
d
i
t
c
=
1
M
·
n
d
N
·
τ
d
1
+
n
o
N
·
τ
o
1
·
1
-
1
M
·
n
d
N
·
τ
d
+
n
o
N
·
τ
o
N
-
2
.Further, we calculate the rest of transition probabilities as(12)
P
o
o
c
=
1
-
1
M
·
P
o
i
c
,
P
d
o
c
=
1
-
1
M
·
P
d
i
c
,
P
o
o
t
c
=
1
-
1
M
·
P
o
i
t
c
,
P
d
o
t
c
=
1
-
1
M
·
P
d
i
t
c
,
P
o
t
c
r
=
P
o
i
t
c
+
P
o
o
t
c
,
P
d
t
c
c
n
=
P
d
i
t
c
+
P
d
o
t
c
,
P
d
c
n
r
=
P
d
t
c
c
n
,
P
o
i
i
=
1
-
n
o
N
·
τ
o
1
·
1
-
1
M
·
n
d
N
·
τ
d
+
n
o
N
·
τ
o
N
-
1
,
P
d
i
i
=
1
-
n
d
N
·
τ
d
1
·
1
-
1
M
·
n
d
N
·
τ
d
+
n
o
N
·
τ
o
N
-
1
,
P
o
i
o
=
1
-
P
o
i
i
+
P
o
i
t
c
+
P
o
i
c
,
P
d
i
o
=
1
-
P
d
i
i
+
P
d
i
t
c
+
P
d
i
c
,
P
o
o
n
=
1
-
P
o
o
t
c
+
P
o
o
c
,
P
d
o
n
=
1
-
P
d
o
t
c
+
P
d
o
c
.Since we have assumed that all frames except DRTS/RTS are successfully delivered, therefore, (13)
P
o
r
i
,
P
o
t
i
,
P
o
n
i
,
P
d
r
i
,
P
d
t
i
,
P
d
n
i
=
1
.


### 4.2. Steady-State Probability for Omnidirectional Node

By solving the balance equation for the steady-state probabilities, we obtain each state probability for the omnidirectional node as(14)
π
o
o
=
P
o
i
o
·
π
o
i
,
π
o
n
=
P
o
o
n
·
P
o
i
o
·
π
o
i
,
π
o
t
c
=
P
o
o
t
c
·
P
o
i
o
+
P
o
i
t
c
·
π
o
i
,
π
o
r
=
π
o
t
c
,
π
o
c
=
P
o
o
c
·
P
o
i
o
+
P
o
i
c
·
π
o
i
1
-
P
o
c
c
,
π
o
t
=
P
o
c
t
·
P
o
o
c
·
P
o
i
o
+
P
o
i
c
·
π
o
i
1
-
P
o
c
c
,
π
o
i
=
1
-
P
o
c
c
1
-
P
o
c
c
2
+
P
o
i
o
-
P
o
i
i
+
1
-
P
o
c
i
P
o
i
c
+
P
o
o
c
·
P
o
i
o
,
π
o
i
+
π
o
o
+
π
o
n
+
π
o
t
c
+
π
o
r
+
π
o
t
+
π
o
c
=
1
.


### 4.3. Steady-State Probability for Directional Node

Similarly we obtain each state probability for the directional node as(15)
π
d
o
=
P
d
i
o
·
π
d
i
,
π
d
n
=
P
d
o
n
·
P
d
i
o
·
π
d
i
,
π
d
t
c
=
P
d
o
t
c
·
P
d
i
o
+
P
d
i
t
c
·
π
d
i
,
π
d
c
n
=
π
d
t
c
,
π
d
r
=
π
d
c
n
,
π
d
c
=
P
d
o
c
·
P
d
i
o
+
P
d
i
c
1
-
P
d
c
c
·
π
d
i
,
π
d
r
n
=
P
d
c
r
n
·
P
d
o
c
·
P
d
i
o
+
P
d
i
c
1
-
P
d
c
c
·
π
d
i
,
π
d
t
=
π
d
r
n
,
π
d
i
=
1
-
P
d
c
c
1
-
P
d
c
c
2
+
P
d
i
o
-
P
d
i
i
+
1
-
P
d
c
i
P
d
i
c
+
P
d
o
c
·
P
d
i
o
,
π
d
o
+
π
d
n
+
π
d
t
c
+
π
d
c
n
+
π
d
r
+
π
d
c
+
π
d
r
n
+
π
d
t
+
π
d
i
=
1
.


### 4.4. Throughput Analysis

In our proposed system, the ORTS, DRTS, RTSN, OCTS, DCTS, CTSN, DATA, and ACK frames are in bits and there is no waiting time for the data arrival from the upper layer. So the time only requires a backoff process at stage zero in the carrier sense. Therefore, in a manner similar to [17], the expected time in the idle state for the omnidirectional and the directional nodes is E
o
[
T
i
] and E
d
[
T
i
], respectively:(16)
E
o
T
i
=
D
I
F
S
+
σ
·
W
0
+
1
2
+
R
T
S
d
.
E
d
T
i
=
D
I
F
S
+
σ
·
W
0
+
1
2
+
R
T
S
d
,where σ is the backoff slot duration and W
0 is the minimum backoff window size for stage 0 and d is the data rate.As in Figures3 and 4, there are three transitions to move from “wait for CTS” state. If the sender receives CTS, it moves to a “transmit/tx-RTSN” state with “P
o
c
t
/
P
d
c
r
n” probability; otherwise, the sender retransmits “ORTS/DRTS” and stays in the same state with “P
c
c” probability. It moves into an “idle” state with “P
c
i” probability when the sender reaches a maximum retransmission limit.Therefore, the expected waiting time in the “wait for CTS” stateE
o
T
c and E
d
T
c for the omnidirectional node and directional node is(17)
E
o
T
c
=
P
o
c
c
·
E
o
c
T
c
+
P
o
c
t
·
E
o
t
T
c
+
P
o
c
i
·
E
o
i
T
c
,
E
d
T
c
=
P
d
c
c
·
E
d
c
T
c
+
P
d
r
n
t
·
E
d
t
T
c
+
P
d
c
i
·
E
d
i
T
c
,where E
o
c
T
c and E
d
c
T
c are the conditional expectation of the sender that does not receive CTS within k
-
1 retransmissions, E
o
t
T
c and E
d
t
T
c are for the sender that receives CTS within the k retransmission limit, and E
o
i
T
c and E
o
i
T
c denote the sender that reaches the maximum retransmission limit:(18)
E
o
c
T
c
=
P
o
c
c
k
-
1
·
k
-
1
·
CTS_
t
i
m
e
o
u
t
+
D
I
F
S
+
σ
·
W
0
+
1
2
+
R
T
S
d
,
E
d
c
T
c
=
P
d
c
c
k
-
1
·
k
-
1
·
CTS_
t
i
m
e
o
u
t
+
D
I
F
S
+
σ
.
W
0
+
1
2
+
R
T
S
d
,
E
o
t
T
c
=
E
o
c
T
c
+
CTS_
t
i
m
e
o
u
t
+
S
I
F
S
,
E
d
t
T
c
=
E
d
c
T
c
+
CTS_
t
i
m
e
o
u
t
+
S
I
F
S
,
E
o
i
T
c
=
P
d
c
c
k
∑
i
=
1
k
CTS_
t
i
m
e
o
u
t
+
D
I
F
S
+
σ
·
W
0
+
1
2
+
R
T
S
d
,
E
d
i
T
c
=
P
d
c
c
k
∑
i
=
1
k
CTS_
t
i
m
e
o
u
t
+
D
I
F
S
+
σ
·
W
0
+
1
2
+
R
T
S
d
.The expected time spent in other states is given as (19)
E
o
T
t
=
E
d
T
t
=
2
·
S
I
F
S
+
D
A
T
A
+
A
C
K
d
,
E
d
T
r
n
=
S
I
F
S
+
R
T
S
N
d
,
E
o
T
t
c
=
E
d
T
t
c
=
S
I
F
S
+
C
T
S
d
,
E
o
T
r
=
E
d
T
r
=
2
·
S
I
F
S
+
D
A
T
A
+
A
C
K
d
,
E
d
T
c
n
=
S
I
F
S
+
C
T
S
N
d
,
E
o
T
o
=
E
d
T
o
=
D
I
F
S
+
5
·
S
I
F
S
+
R
T
S
+
C
T
S
+
C
T
S
N
+
R
T
S
N
+
D
A
T
A
+
A
C
K
d
,
E
o
T
n
=
E
d
T
n
=
S
I
F
S
+
N
I
P
d
.Finally, we can calculate the network throughput with N nodes. Since the network is a hybrid network that consists of two types of nodes, the network throughput is (20)
S
=
T
H
O
+
T
H
D
,where(21)
T
H
O
=
n
o
/
N
·
π
o
r
·
E
P
π
o
i
·
E
o
T
i
+
π
o
c
·
E
o
T
c
+
π
o
t
·
E
o
T
t
+
π
o
t
c
·
E
o
T
t
c
+
π
o
r
·
E
o
T
r
+
π
o
o
·
E
o
T
o
+
π
o
n
·
E
o
T
n
,
T
H
D
=
n
d
/
N
·
π
d
r
·
E
P
π
d
i
·
E
d
T
i
+
π
d
c
·
E
d
T
c
+
π
d
r
n
·
E
d
T
r
n
+
π
d
t
·
E
d
T
t
+
π
d
t
c
·
E
d
T
t
c
+
π
d
c
n
·
E
d
T
c
n
+
π
d
r
·
E
d
T
r
+
π
d
o
·
E
d
T
o
+
π
d
n
·
E
d
T
nwith E
P as the average payload size for the data packet.From (20), we can analyze the aggregate throughput of the network. In our analysis, we summarize the parameter used to obtain the numerical results for the analytical and the simulation model in Table 1.Table 1
Parameters used to obtain numerical results.
Packet payload
1024 bytes
MAC header
34 bytes
PHY header
16 bytes
ACK
14 bytes
ORTS/DRTS/RTSN
20 bytes
OCTS/DCTS/CTSN/NIP
14 bytes
Channel bit rate
54 Mbps
Slot time
20μs
SIFS
10μs
DIFS
50μsFigures5(a), 5(b), and 5(c) show a comparison of the transmission probability of the directional and omnidirectional nodes in the network in terms of the number of nodes, percentage of the directional nodes, and number of beams, respectively. As seen in the figure, the transmission probability of the directional nodes is much better than that of the omnidirectional nodes due to the directional transmission in the network. In the case of Figure 5(b) the transmission probabilities for both types of nodes increase as the percentage of directional nodes increases in the network as a result of the directional transmission decreasing the probability of a collision.Figure 5
Transmission probability. (a) Number of nodes. (b) Percentage of directional nodes in the network. (c) Number of beams.
(a)
(b)
(c)Figures6(a), 6(b), and 6(c) show the collision probability versus the number of nodes, the percentage of directional nodes in the network, and the number of beams, respectively. As expected, the figures indicate that the collision probability increases as the number of nodes increases (Figure 6(a)). However, when the percentage of directional nodes in the network increases, the collision probability accordingly decreases, as seen in Figure 6(b). In the case with the number of beams shown in Figure 6(c), when the number of beams increases, the collision probability decreases, as expected. In all cases, the collision probability of the directional nodes is much lower than that of the omnidirectional nodes.Figure 6
Collision Probability. (a) Number of nodes. (b) Percentage of directional node in the network. (c) Number of beams.
(a)
(b)
(c)Figures7 and 8 show steady-state probability of the directional and omnidirectional nodes. In the figures, “PAID and PAIO” denote π
d and π
o (directional and omnidirectional node states) and “c
,
i
,
n
,
o
,
r, and t” denote the corresponding states.Figure 7
Steady-state probabilities of the directional node. (a) Number of nodes. (b) Percentage of directional nodes in the network. (c) Number of beams.
(a)
(b)
(c)Figure 8
Steady-state probabilities for omnidirectional node. (a) Number of nodes. (b) Percentage of the directional nodes in the network. (c) Number of beams.
(a)
(b)
(c)In Figures7 and 8, the P
A
I
D
i
π
d
i and P
A
I
O
i
π
o
i states are the same for all cases because the directional nodes sense the channel through its beam pointed around the nodes, which acts as an isotropic antenna. Therefore, the probability of a node staying in the “idle” state is the same for both kinds of nodes in the network. For the rest of states, we can see that the direction nodes have a better probability to stay in the individual states.


## 4.1. Derivation of Transition Probability

In this section, we derive the transition probability from moving one state to another state for both omnidirectional and directional nodes.First, we can deriveP
o
i
c and P
d
i
c as(1)
P
o
i
c
=
Pr
⁡
N
o
d
e
t
r
a
n
s
m
i
t
s
R
T
S
i
n
t
h
e
f
i
r
s
t
b
a
c
k
o
f
f
s
t
a
g
e
=
τ
o
1
,
P
d
i
c
=
Pr
⁡
N
o
d
e
t
r
a
n
s
m
i
t
s
D
R
T
S
i
n
t
h
e
f
i
r
s
t
b
a
c
k
o
f
f
s
t
a
g
e
=
τ
d
1
.We consider the same random backoff scheme as in [17] for our proposed MAC protocol. For that scheme, the authors calculated the probability τ
1 that a node transmits in the first backoff stage using the backoff Markov chain model:(2)
τ
1
=
2
1
-
2
p
1
-
p
1
-
2
p
W
0
+
1
+
p
W
0
1
-
2
p
m
,where τ
1 denotes the probability that a node transmits in the first backoff stage, p is the conditional probability, W
0 is the minimum contention window size, and m is the maximum number of the stages. Further, they calculated p as(3)
p
=
1
-
1
-
τ
N
-
2
,where τ denotes the probability that a node transmits in a random slot time for all backoff stages and can be calculated as follows:(4)
τ
=
2
1
-
2
p
1
-
2
p
W
0
+
1
+
p
W
0
1
-
2
p
m
.Since the network is a hybrid, we can rewrite (2) for P
o
i
c and P
d
i
c as (5)
τ
o
1
=
2
1
-
2
p
o
1
-
p
o
1
-
2
p
o
W
0
+
1
+
p
o
W
0
1
-
2
p
o
m
,
τ
d
1
=
2
1
-
2
p
d
1
-
p
d
1
-
2
p
d
W
0
+
1
+
p
d
W
0
1
-
2
p
d
m
.
p
o and p
d denote the collision probability of omnidirectional and directional nodes, respectively. To calculate the conditional probabilities, we can rewrite (3) as (6)
p
o
=
1
-
1
-
1
M
·
n
d
N
·
τ
d
+
n
o
N
·
τ
o
N
-
2
,
p
d
=
1
-
1
-
1
M
2
·
n
d
N
·
τ
d
+
1
M
·
n
o
N
·
τ
o
N
-
2
,where n
d, n
o, N, and M denote the “number of directional nodes, number of omnidirectional nodes, total number of nodes in the network, and number of beams,” respectively. τ
o and τ
d are the probability that a node transmits in a random time slot for all backoff stages. It can be calculated by rewriting (4) as(7)
τ
o
=
2
1
-
2
p
o
1
-
2
p
o
W
0
+
1
+
p
o
W
0
1
-
2
p
o
m
,
τ
d
=
2
1
-
2
p
d
1
-
2
p
d
W
0
+
1
+
p
d
W
0
1
-
2
p
d
m
.Next, we can derive P
o
c
t, P
d
c
r
n, and P
d
r
n
t, since there is only one transition P
d
r
n
t to move from the π
d
r
n to the π
d
t state.Therefore,(8)
P
d
r
n
t
=
P
d
c
r
n
,
P
o
c
t
=
P
d
c
r
n
=
Pr
⁡
n
o
o
t
h
e
r
t
r
a
n
s
m
i
s
s
i
o
n
i
n
t
h
e
s
e
c
t
o
r
o
r
r
e
c
e
i
v
e
r
r
a
n
g
e
=
1
-
1
M
·
n
d
N
·
τ
d
+
n
o
N
·
τ
o
N
-
2
.We can derive P
o
c
i and P
d
c
i as (9)
P
o
c
i
=
P
d
c
i
=
Pr
⁡
sender  does  not  receive  any  response  within  retransmission  limit
k
=
p
k
+
1and P
o
c
c and P
d
c
c can be calculated as(10)
P
o
c
c
=
1
-
P
o
c
i
+
P
o
c
t
,
P
d
c
c
=
1
-
P
d
c
i
+
P
d
c
r
n
.Similarly we can derive P
o
i
t
c and P
d
i
t
c, as (11)
P
o
i
t
c
=
P
d
i
t
c
=
1
M
·
n
d
N
·
τ
d
1
+
n
o
N
·
τ
o
1
·
1
-
1
M
·
n
d
N
·
τ
d
+
n
o
N
·
τ
o
N
-
2
.Further, we calculate the rest of transition probabilities as(12)
P
o
o
c
=
1
-
1
M
·
P
o
i
c
,
P
d
o
c
=
1
-
1
M
·
P
d
i
c
,
P
o
o
t
c
=
1
-
1
M
·
P
o
i
t
c
,
P
d
o
t
c
=
1
-
1
M
·
P
d
i
t
c
,
P
o
t
c
r
=
P
o
i
t
c
+
P
o
o
t
c
,
P
d
t
c
c
n
=
P
d
i
t
c
+
P
d
o
t
c
,
P
d
c
n
r
=
P
d
t
c
c
n
,
P
o
i
i
=
1
-
n
o
N
·
τ
o
1
·
1
-
1
M
·
n
d
N
·
τ
d
+
n
o
N
·
τ
o
N
-
1
,
P
d
i
i
=
1
-
n
d
N
·
τ
d
1
·
1
-
1
M
·
n
d
N
·
τ
d
+
n
o
N
·
τ
o
N
-
1
,
P
o
i
o
=
1
-
P
o
i
i
+
P
o
i
t
c
+
P
o
i
c
,
P
d
i
o
=
1
-
P
d
i
i
+
P
d
i
t
c
+
P
d
i
c
,
P
o
o
n
=
1
-
P
o
o
t
c
+
P
o
o
c
,
P
d
o
n
=
1
-
P
d
o
t
c
+
P
d
o
c
.Since we have assumed that all frames except DRTS/RTS are successfully delivered, therefore, (13)
P
o
r
i
,
P
o
t
i
,
P
o
n
i
,
P
d
r
i
,
P
d
t
i
,
P
d
n
i
=
1
.


## 4.2. Steady-State Probability for Omnidirectional Node

By solving the balance equation for the steady-state probabilities, we obtain each state probability for the omnidirectional node as(14)
π
o
o
=
P
o
i
o
·
π
o
i
,
π
o
n
=
P
o
o
n
·
P
o
i
o
·
π
o
i
,
π
o
t
c
=
P
o
o
t
c
·
P
o
i
o
+
P
o
i
t
c
·
π
o
i
,
π
o
r
=
π
o
t
c
,
π
o
c
=
P
o
o
c
·
P
o
i
o
+
P
o
i
c
·
π
o
i
1
-
P
o
c
c
,
π
o
t
=
P
o
c
t
·
P
o
o
c
·
P
o
i
o
+
P
o
i
c
·
π
o
i
1
-
P
o
c
c
,
π
o
i
=
1
-
P
o
c
c
1
-
P
o
c
c
2
+
P
o
i
o
-
P
o
i
i
+
1
-
P
o
c
i
P
o
i
c
+
P
o
o
c
·
P
o
i
o
,
π
o
i
+
π
o
o
+
π
o
n
+
π
o
t
c
+
π
o
r
+
π
o
t
+
π
o
c
=
1
.


## 4.3. Steady-State Probability for Directional Node

Similarly we obtain each state probability for the directional node as(15)
π
d
o
=
P
d
i
o
·
π
d
i
,
π
d
n
=
P
d
o
n
·
P
d
i
o
·
π
d
i
,
π
d
t
c
=
P
d
o
t
c
·
P
d
i
o
+
P
d
i
t
c
·
π
d
i
,
π
d
c
n
=
π
d
t
c
,
π
d
r
=
π
d
c
n
,
π
d
c
=
P
d
o
c
·
P
d
i
o
+
P
d
i
c
1
-
P
d
c
c
·
π
d
i
,
π
d
r
n
=
P
d
c
r
n
·
P
d
o
c
·
P
d
i
o
+
P
d
i
c
1
-
P
d
c
c
·
π
d
i
,
π
d
t
=
π
d
r
n
,
π
d
i
=
1
-
P
d
c
c
1
-
P
d
c
c
2
+
P
d
i
o
-
P
d
i
i
+
1
-
P
d
c
i
P
d
i
c
+
P
d
o
c
·
P
d
i
o
,
π
d
o
+
π
d
n
+
π
d
t
c
+
π
d
c
n
+
π
d
r
+
π
d
c
+
π
d
r
n
+
π
d
t
+
π
d
i
=
1
.


## 4.4. Throughput Analysis

In our proposed system, the ORTS, DRTS, RTSN, OCTS, DCTS, CTSN, DATA, and ACK frames are in bits and there is no waiting time for the data arrival from the upper layer. So the time only requires a backoff process at stage zero in the carrier sense. Therefore, in a manner similar to [17], the expected time in the idle state for the omnidirectional and the directional nodes is E
o
[
T
i
] and E
d
[
T
i
], respectively:(16)
E
o
T
i
=
D
I
F
S
+
σ
·
W
0
+
1
2
+
R
T
S
d
.
E
d
T
i
=
D
I
F
S
+
σ
·
W
0
+
1
2
+
R
T
S
d
,where σ is the backoff slot duration and W
0 is the minimum backoff window size for stage 0 and d is the data rate.As in Figures3 and 4, there are three transitions to move from “wait for CTS” state. If the sender receives CTS, it moves to a “transmit/tx-RTSN” state with “P
o
c
t
/
P
d
c
r
n” probability; otherwise, the sender retransmits “ORTS/DRTS” and stays in the same state with “P
c
c” probability. It moves into an “idle” state with “P
c
i” probability when the sender reaches a maximum retransmission limit.Therefore, the expected waiting time in the “wait for CTS” stateE
o
T
c and E
d
T
c for the omnidirectional node and directional node is(17)
E
o
T
c
=
P
o
c
c
·
E
o
c
T
c
+
P
o
c
t
·
E
o
t
T
c
+
P
o
c
i
·
E
o
i
T
c
,
E
d
T
c
=
P
d
c
c
·
E
d
c
T
c
+
P
d
r
n
t
·
E
d
t
T
c
+
P
d
c
i
·
E
d
i
T
c
,where E
o
c
T
c and E
d
c
T
c are the conditional expectation of the sender that does not receive CTS within k
-
1 retransmissions, E
o
t
T
c and E
d
t
T
c are for the sender that receives CTS within the k retransmission limit, and E
o
i
T
c and E
o
i
T
c denote the sender that reaches the maximum retransmission limit:(18)
E
o
c
T
c
=
P
o
c
c
k
-
1
·
k
-
1
·
CTS_
t
i
m
e
o
u
t
+
D
I
F
S
+
σ
·
W
0
+
1
2
+
R
T
S
d
,
E
d
c
T
c
=
P
d
c
c
k
-
1
·
k
-
1
·
CTS_
t
i
m
e
o
u
t
+
D
I
F
S
+
σ
.
W
0
+
1
2
+
R
T
S
d
,
E
o
t
T
c
=
E
o
c
T
c
+
CTS_
t
i
m
e
o
u
t
+
S
I
F
S
,
E
d
t
T
c
=
E
d
c
T
c
+
CTS_
t
i
m
e
o
u
t
+
S
I
F
S
,
E
o
i
T
c
=
P
d
c
c
k
∑
i
=
1
k
CTS_
t
i
m
e
o
u
t
+
D
I
F
S
+
σ
·
W
0
+
1
2
+
R
T
S
d
,
E
d
i
T
c
=
P
d
c
c
k
∑
i
=
1
k
CTS_
t
i
m
e
o
u
t
+
D
I
F
S
+
σ
·
W
0
+
1
2
+
R
T
S
d
.The expected time spent in other states is given as (19)
E
o
T
t
=
E
d
T
t
=
2
·
S
I
F
S
+
D
A
T
A
+
A
C
K
d
,
E
d
T
r
n
=
S
I
F
S
+
R
T
S
N
d
,
E
o
T
t
c
=
E
d
T
t
c
=
S
I
F
S
+
C
T
S
d
,
E
o
T
r
=
E
d
T
r
=
2
·
S
I
F
S
+
D
A
T
A
+
A
C
K
d
,
E
d
T
c
n
=
S
I
F
S
+
C
T
S
N
d
,
E
o
T
o
=
E
d
T
o
=
D
I
F
S
+
5
·
S
I
F
S
+
R
T
S
+
C
T
S
+
C
T
S
N
+
R
T
S
N
+
D
A
T
A
+
A
C
K
d
,
E
o
T
n
=
E
d
T
n
=
S
I
F
S
+
N
I
P
d
.Finally, we can calculate the network throughput with N nodes. Since the network is a hybrid network that consists of two types of nodes, the network throughput is (20)
S
=
T
H
O
+
T
H
D
,where(21)
T
H
O
=
n
o
/
N
·
π
o
r
·
E
P
π
o
i
·
E
o
T
i
+
π
o
c
·
E
o
T
c
+
π
o
t
·
E
o
T
t
+
π
o
t
c
·
E
o
T
t
c
+
π
o
r
·
E
o
T
r
+
π
o
o
·
E
o
T
o
+
π
o
n
·
E
o
T
n
,
T
H
D
=
n
d
/
N
·
π
d
r
·
E
P
π
d
i
·
E
d
T
i
+
π
d
c
·
E
d
T
c
+
π
d
r
n
·
E
d
T
r
n
+
π
d
t
·
E
d
T
t
+
π
d
t
c
·
E
d
T
t
c
+
π
d
c
n
·
E
d
T
c
n
+
π
d
r
·
E
d
T
r
+
π
d
o
·
E
d
T
o
+
π
d
n
·
E
d
T
nwith E
P as the average payload size for the data packet.From (20), we can analyze the aggregate throughput of the network. In our analysis, we summarize the parameter used to obtain the numerical results for the analytical and the simulation model in Table 1.Table 1
Parameters used to obtain numerical results.
Packet payload
1024 bytes
MAC header
34 bytes
PHY header
16 bytes
ACK
14 bytes
ORTS/DRTS/RTSN
20 bytes
OCTS/DCTS/CTSN/NIP
14 bytes
Channel bit rate
54 Mbps
Slot time
20μs
SIFS
10μs
DIFS
50μsFigures5(a), 5(b), and 5(c) show a comparison of the transmission probability of the directional and omnidirectional nodes in the network in terms of the number of nodes, percentage of the directional nodes, and number of beams, respectively. As seen in the figure, the transmission probability of the directional nodes is much better than that of the omnidirectional nodes due to the directional transmission in the network. In the case of Figure 5(b) the transmission probabilities for both types of nodes increase as the percentage of directional nodes increases in the network as a result of the directional transmission decreasing the probability of a collision.Figure 5
Transmission probability. (a) Number of nodes. (b) Percentage of directional nodes in the network. (c) Number of beams.
(a)
(b)
(c)Figures6(a), 6(b), and 6(c) show the collision probability versus the number of nodes, the percentage of directional nodes in the network, and the number of beams, respectively. As expected, the figures indicate that the collision probability increases as the number of nodes increases (Figure 6(a)). However, when the percentage of directional nodes in the network increases, the collision probability accordingly decreases, as seen in Figure 6(b). In the case with the number of beams shown in Figure 6(c), when the number of beams increases, the collision probability decreases, as expected. In all cases, the collision probability of the directional nodes is much lower than that of the omnidirectional nodes.Figure 6
Collision Probability. (a) Number of nodes. (b) Percentage of directional node in the network. (c) Number of beams.
(a)
(b)
(c)Figures7 and 8 show steady-state probability of the directional and omnidirectional nodes. In the figures, “PAID and PAIO” denote π
d and π
o (directional and omnidirectional node states) and “c
,
i
,
n
,
o
,
r, and t” denote the corresponding states.Figure 7
Steady-state probabilities of the directional node. (a) Number of nodes. (b) Percentage of directional nodes in the network. (c) Number of beams.
(a)
(b)
(c)Figure 8
Steady-state probabilities for omnidirectional node. (a) Number of nodes. (b) Percentage of the directional nodes in the network. (c) Number of beams.
(a)
(b)
(c)In Figures7 and 8, the P
A
I
D
i
π
d
i and P
A
I
O
i
π
o
i states are the same for all cases because the directional nodes sense the channel through its beam pointed around the nodes, which acts as an isotropic antenna. Therefore, the probability of a node staying in the “idle” state is the same for both kinds of nodes in the network. For the rest of states, we can see that the direction nodes have a better probability to stay in the individual states.


## 5. Performance Comparison

In this section, we evaluate the performance of the MAC proposed for use in the hybrid network. To validate our results, we conducted a simulation using the OPNET simulator. The parameters of the simulation are given in Table2.Table 2
Simulation parameter.
Parameter
Value
Maximum number of nodes
100
Omnidirectional range
150 m
Directional communication range
300 m
Data rate
54 Mbps
Data size
1024 bytesWe have developed a simulation scenario for which all nodes are randomly distributed in a 1500 × 1500 m2 area. All of the receiver nodes are located within the sender’s communication range. The simulation runs for 600 seconds and each result is an average over ten runs with random seeds. We do not consider mobility of the nodes in our simulations.Figures9 and 10 show the aggregate network throughput of a network versus the variation in the number of nodes in the network, and the number of nodes is seen to vary from 6 to 100 nodes in the network.Figure 9
Performance of the network with different percentages of directional and omnidirectional nodes.Figure 10
Performance of the network with different number of beams.In Figure9, we compared the performance of the network for a variation in the percentage of the directional nodes with four beams in the network. The figure indicates that when the directional nodes comprise 10% of the network, the saturation throughput is less than 70 Mbps for 40 nodes. When we increase the percentage of directional nodes to 40%, the saturation throughput becomes more than 110 Mbps at 70 nodes. In the case of 70% of directional nodes, the performance significantly increases to more than 140 Mbps saturation at a throughput with 90 nodes. The reason for the improvement in performance in terms of the throughput with directional nodes is that the directional transmission increases the spatial reuse in the network and decreases the collision probability. Moreover, the directional antenna has a higher gain than that of an isotropic antenna, so the higher number of directional nodes provides a significantly improved performance with a dense network.In Figure10, we compared the performance of the network for a varying number of beams of the directional nodes in the network. In this scenario, half of the nodes are directional nodes and the other half are omnidirectional nodes. The saturation throughput increases with a dense network according to the number of beams because the spatial reuse in the network increases as the number of beams increases.Since our proposed MAC is designed for hybrid network, so we implement DA-MAC [3] for directional nodes and IEEE 802.11 for omnidirectional nodes for simulation. In the scenario, there are total hundred nodes in the network. The 50% nodes are directional and the rest of 50% are omnidirectional nodes. We named these implemented MAC as previous MAC. To evaluate our results we compared the performance of our proposed MAC and previous MAC.Figure11 shows the aggregate throughput versus offered load. As the figure, the performance of our proposed MAC is better than that of previous MAC, because the scheme of transmitting NIP and simultaneous transmission of RTSN/CTSN overcome the deaf and hidden node problem while the scheme of setting NAV1 and NAV2 overcomes exposed node problem. On the other hand, in previous MAC, the nodes follow the DA-MAC (directional node) and IEEE 802.11 (omnidirectional node). In DA-MAC there is no scheme to overcome the hidden and exposed node problem. Moreover, with IEEE 802.11, there is no scheme to overcome the exposed node problem in hybrid network. So the hidden and exposed node problem is the main reason of poor performance of previous MAC.Figure 11
Performance comparison with previous MAC versus offered load.Figure12 shows the aggregate throughput versus percentage of directional nodes in the network. As the figure, in both cases the throughput is increasing as the percentage of directional node is increasing; it shows that we achieve better spatial reuse in the network with directional antenna. As expected our proposed MAC performs better than that of the previous MAC.Figure 12
Performance comparison with previous MAC versus offered load.


## 6. Conclusion

In this paper, we have considered the intermediate wireless network (hybrid network) with respect to the advancements in the use of a directional antenna. The hybrid network contains heterogeneous sensor nodes equipped with either an omnidirectional antenna or a directional antenna. In the network, we find that deaf, hidden, and exposed nodes had more severe effects due to the lack of a suitable MAC protocol. The existing MAC protocols were designed for homogeneous networks did not work effectively when used in a hybrid network. We have proposed a MAC protocol for use with heterogeneous sensor nodes in a hybrid network. The proposed MAC protocol includes concurrent transmission of RTSN/CTSN after a successful channel reservation, transmission of NIP packets by the ideal nodes, and a scheme to set the NAV with omnidirectional nodes to overwhelm the deaf nodes, hidden nodes, and exposed nodes, respectively. We analyzed the proposed MAC by using a Markov model and validated the performance results by conducting a simulation using the OPNET simulator. The analytical and simulation results indicate there was a significant increase in the network throughput for the proposed protocol.



---

*Source: 7951965-2016-03-07.xml*