Combating Hidden And Exposed Terminal Problem In Ad Hoc Networks Computer Science

Essay add: 24-12-2015, 13:24   /   Views: 93

A wireless ad hoc network is a decentralized network. The hottest research direction in wireless ad hoc network is in the field of throughput enhancement. In this, two well known problems that can cause the performance degradation, one is hidden terminal (HT) problem, which allows transmitting but interfere with the receiver causing a collision. Another one problem is exposed terminal (ET), which is not allowed to transmit although they would not interfere. In this paper, a wireless QoS model is designed to combat hidden and exposed terminal problem in an ad hoc network by applying Hidden Free Design (HFD) and Selective Disregard of NAV's (SDN) algorithm. These two algorithms are implemented using a single virtual carrier sensing (VCS) mechanism with the Receiver Network Allocation Vector (RNAV) manipulation to improve the throughput by allowing as much as possible concurrent transmissions among the neighbouring nodes. This model concentrates the NAV mismanipulation in the transmitter and receiver side. This misbehavior is to be avoided using new timer and Mis_count value in both. In this model, the throughput and scalability of the network is maximized with the reduced power utilization by every node in the network.

A wireless ad hoc network is an infrastructure less network, where each node is willing to forward data for other nodes, and the determination of which nodes to forward data is made dynamically based on the network connectivity. In this ad hoc network, the removal of HT and ET is one of the main challenge. The following two definitions describe the HT and ET problem in ad hoc network.

Definition of HT: A node may receive concurrent transmissions from multiple neighbors that cannot hear one another. Unnecessary collisions of data packet occur which are followed by message retransmissions and reduces network throughput. For example consider three nodes A, B, C in Figure 1.





Figure 1 Hidden Node Problem

Node C is outside the transmission range of B; likewise, node B is outside the transmission range of C. Node A is in the area covered by both B and C; it can hear the signal transmitted by B or C. When node B is sending data to A, at that time node C also has data to send to node A. However, node C is out of B's range and transmission from B cannot reach C. Node C sends its data to A, which results in a collision at A, because this node is receiving data from both B and C. This is called the Hidden Terminal problem. Due to the collision it degrades the network throughput.

Definition of ET: A node within the range of a transmitting node is prohibited from accessing the medium. This affects the scalability of the network. For example consider the four stations A, B, C and D in Figure 2.





Figure 2 Exposed Terminal Problem

Node A is transmitting data to node B. Node C lies within the transmission range of node A and is exposed to the ongoing transmission. Node C wants to communicate with node D but is prohibited to transmit. Node C is exposed to transmission from A. In other words node C wastes the capacity of the channel.


In recent years, the protocol that is used to communicate over a wireless medium is 802.11. To reduce collisions caused by hidden and exposed terminals in the network, 802.11 use a four-way RTS/CTS/Data/Ack exchange. A node that wishes to send a data packet first sends an RTS (request to send) packet to the destination. If the destination believes the network is idle, it responds with CTS (clear to send). The sender then transmits the data packet, and waits for an ACK (acknowledgment) from the receiver. If a node overhears an RTS or CTS, it knows the medium will be busy for some time, and avoids new transmissions or sending any CTS packets. For avoiding such type of collisions it uses virtual carrier sensing mechanism with "network allocation vector" (NAV) as in Figure 3. In, RTS and CTS packets it include the amount of time the medium will be busy for the remainder of the exchange. Within the transmission range, each node other than the receiver node uses these times to update its NAV. The NAV value indicates the amount of time remaining before the network will become available . Upon successful receipt of an RTS frame not addressed to itself, a node updates its NAV to the maximum of the time carried in the RTS frame and its current NAV value. Upon receiving an RTS addressed to itself, a node returns a CTS frame only if its NAV value is zero, otherwise no CTS is sent. After sending CTS frame it receives DATA frame and it responses with ACK frame.



NAV (Data)












Figure 3 NAV State

DIFS-DCF Inter Frame Space.

SIFS-Short Inter Frame Space.

A. Literature Survey

Acharya, Mishra and Bansal [1] proposed MACA-P. The key feature of MACA-P is that it introduces a control gap between the RTS/CTS exchange and the subsequent DATA/ACK exchange of the first pair of communicating nodes. This control gap is then exploited by other pairs of nodes to complete their own RTS/CTS exchange and to align their data transfer with the DATA and ACK packets of the first pair.

Jiang and Liew [2] proposed to reduce hidden nodes in wireless networks by applying Hidden Free Design (HFD) algorithm with both carrier sensing PCS (Physical Carrier Sensing) and VCS (Virtual Carrier Sensing). This can be dealt with only for hidden nodes.

Jiang and Liew [4] proposed HFD and SDN algorithm to remove hidden and exposed nodes with PCS and VCS. By using both carrier sensing mechanisms each node can require more power to avoid interference between the nodes.

In this paper, we are interested to explore the removal of hidden and exposed terminal problem using a single carrier sensing mechanism with NAV state information is updated for whole duration of ongoing transmission. The paper is organized as follows: Section III explains the proposed architecture, HFD, SDN and NAV mismanipulation, Section IV models implementation and results and Section V concludes the paper.


In this proposed model, the HFD and SDN algorithm which follow the single virtual carrier sensing mechanism to allow packet transmission. It requires a simple receiver NAV timer to allow the transmission in the network. If any transmission is started the receiver also set the NAV for the whole transmission. Before start a transmission every node checks receiver NAV fields. Depends on the NAV value, a node can take decision to transmit the RTS packet to the receiver. If any scheduled transmission is ongoing NAV value will be greater than zero. So, it checks

RNAV≠ 0; cannot transmit the RTS packet.

RNAV= 0; can transmit the RTS packet.

By checking this value the transmitting node will avoid the new transmission interference in the network. The system can reduce the overhead by using a single VCS mechanism instead of using both PCS (Physical Carrier Sensing) and VCS. It works under the NAV timer, so the mismanipulation of NAV is handled in both transmitter and receiver sides with Adaptive NAV. ANAV can adjust their timer values if it exceeds the counter threshold value. It controls the mismanipulation of NAV. Because this model depends only on the NAV timer information.


In this design, to remove HN's we should forewarn each node from other node by using the virtual carrier sensing mechanism. For that, VCS range should always be larger than interference range (IR) and maximum distance (d max).

VCS range > IR max

VCS range > d max

Then only nodes can hear RTS or CTS from other nodes. With the decoded RTS message each node can update their NAV timer. To avoid the maximum number of RTS and CTS interference between the nodes set the VCS range as,

VCS ≥ d max + IR max

Here, we are setting VCS range is always greater than the dmax with the IR max. Here no need of physical carrier sensing to avoid the collision instead of we are using receiver NAV timer. Normally in any network a node can send the RTS message after a DIFS time, other nodes within the transmission range can set their NAV, by setting their NAV which cannot interpret the ongoing transmission for a specified period.

This is for the case, the nodes within the transmission range. Hidden nodes are mainly occurring due to the out of range of the nodes. So, the nodes cannot know the status of the receiver node. In this design, the receiver can set the RNAV timer for every transmission with the encoded RTS message. RTS frame has the fields of

2 2 6 6 4






Frame control


Figure 4 RTS Frame

RNAV helps to avoid interference between nodes by setting the NAV timer value in receiver node. The average power received at a receiver (Pr) from a transmitter at a distance d is

Pr = Pt / dα

Consider the example in figure 6, in which node S1 starts its transmission with R1by sending RTS message. With the RTS message the other nodes in S1 transmission range can set their NAV and it should not interfere with S1. Here, we introducing new NAV timer in receiver R1. If S1 transmitting RTS, R1 also setting the NAV timer. Now, the transmission is going between S1 to R1. Node S2 wants to communicate with R1 means it checks the RNAV. If the receiver node R1 having the RNAV value zero it starts to transmit the RTS message. Here R1 having RNAV value greater than zero. So S2 wait until it becomes zero. After, sometime R1 becomes idle. Then s2 starts its transmission with RTS message.

S1's VCS range

S2's VCS range

S2's Interference range

S1's Interference range

S2 transmission range

S1 transmission range


Figure 5 Example scenario

HFD algorithm:CASE I: Initially a node starting the transmission it checks RNAV

If (RNAV=0)

Start pkt txm.

If (RNAV≠0)

Listen RNAV of the Recr until becomes 0.

CASE II: Packet arrives

Find pkt frame type= RTS/CTS/DATA/ACK

If ( pkt type=RTS)


Get Duration field, source addr and Dest addr;


NAV Timer in neighbor nodes


RNAV timer in Recr

Recr receives RTS

Responses with CTS within SIFS

If( pkt type=CTS)

Dec NAV and RNAV timer

Transmit CTS

If( pkt type=DATA)

Dec NAV and RNAV timer

Transmit DATA

If( pkt type=ACK)

Dec NAV and RNAV timer

Transmit ACK

Set (RNAV==0)


If RNAV of a receiver is not checked and RTS message is transmitted it causes two effects

Sender node cannot know the receiver is under any transmission with other nodes.

If any sender node can directly transmit RTS to receiver node, the other nodes within the range of transmitter can set their NAV even if the receiver is busy with another transmission. So, other nodes in the transmission range further cannot transmit to the sender node due to their NAV information.


For the successful concurrent transmissions in the network, the interferences between the nodes should be tolerable and at the same time the channel utilization is also needed to be high. This can be achieved by applying the SDN algorithm with NAV timer information. ET's can avoid interference between the nodes but its channel utilization is poor. Concurrent transmissions are not possible even the transmitting node is not interfered with the ongoing transmission. In our proposed model, concurrent transmissions between the nodes are allowed by updating its NAV for every transmission with the link status.

For example see figure 2, transmission between the nodes A → B link status information can be maintained in the nodes A and B. Any node in the coverage range can take transmission it checks with the ongoing transmission link nodes. Here C wants to communicate with D, so C checks the link status of the nodes within the coverage range. A only communicating with B it know from A link status, C continues its transmission with D.

Link status of node A, A→B

Link status of node B, A→B

Node C checks A its only in coverage range

A→B≠ C→D

Link status is not same it can start to transmit with its own transmission with NAV==0. If NAV! =0 it cannot transmit until NAV becomes zero. Link status is same it cannot continue with its own transmission. Wait until NAV==0 and link status becomes not same. The node can take decision to transmit data it consider NAV value and the link status.

SDN algorithm:

SDN algorithm follows the below 2 cases to transmit

data packets concurrently in the network

Case 1: For the first node transmission

Initially Set NAV=0 to all nodes

Send RTS after SIFS period

Set the NAV of other nodes within the range from the RTS header.

Set the link status a→b with transmitter and receiver address in both.

Receiving node responses with CTS.

Transmit the DATA packet

Responses with ACK.

Case 2: For other nodes transmission

Check its NAV and link status


((NAV == 0)&& link status not same(a→ b))

transmit the packet


(NAV != 0) && link status same (a→ b)

Wait until NAV becomes zero and link status

not same

transmit the packet.

end if

Receiving node responses with CTS.

Set the NAV for CTS frame continue as step 2 for DATA and ACK also.

Transmit the DATA packet

Responses with ACK.

Other node also to transmit the data packet follows the step 4. The link status is kept in every node helps to transmit the data packet concurrently. It results high utilization of the same channel for many transmissions in the network.

.C. NAV mismanipulation

The reason for NAV misbehavior is to maximize the current node throughput by keeping the channel busy to complete its all transmission. Due to this effect, the neighbor nodes that overhear the exchange will have to adjust their Network Allocation Vector with larger duration. So other regular nodes cannot occupy the channel for transmission which leads to DoS (Denial of service). NAV value can be changed by changing the time duration of Short Inter Frame Spacings (SIFS) intervals or changing the time of RTS, CTS, DATA and ACK frame. NAV information frame (IF) having the transmission times of,


NAV mismanipulation may occur in two ways. One is at transmitter side and other is receiver side. This misbehaving can be reduced by ANAV (Adaptive Network Allocation Vector) timer. It can adjust the time of NAV to increase the response time in the network.

Receiver Side Mismanipulation

Receiver side NAV mismanipulation may occur by changing the value of SIFS. To avoid this type of misbehavior we are introducing the new timers TORTS,CTS and TOTot. in the sender shown in figure 6.


Time Out period of RTS and CTS.


Time Out period of whole information exchange.


These two time periods are maintained in the sender to detect NAV mismanipulation. If the receiver is not responded within the SIFS period it checks the TORTS,CTS and TOTot timer to detect if SIFS time is changed.









TO Tot


Figure 6 Sender initiated with timer

Here the misbehaving receiver node chooses larger SIFS i.e... SIFS* (SIFS* > Actual SIFS). So that it send CTS or ACK after timeout (TO) period. Because of this timeout the sender sends RTS again for retransmission. If it continues for N times, sender found that may receiver is misbehaving and checks with the TORTS,CTS and TOTot timer with the threshold counter value. With the sender initiated timer the SIFS value is equated with the modified SIFS*value.

Detection system for receiver side misbehaving with Adaptive NAV

Every sender node can maintains the sequence counter for its transmission, if the receiving node cannot responses the sender again send the message to the receiver and increments the Mis_count value. It wait for the response from the receiver if not, it checks their Mis_count value.

Mis_count(Tx) > Threshold valueSIFS = SIFS*.

If it is greater than the threshold value ANAV timer can increase the value of SIFS to higher SIFS* value to avoid the misbehaving of node. Threshold value may equal to 3 or 4. Then the sender node transmits CTS with adjusted higher SIFS value to avoid mismanipulation of NAV timer. After that sender node continues to transmit DATA packet to the receiver. Then the receiver node does not responded with the ACK means, again it continues with the TOTot timer to check the SIFS value, if it misbehaves SIFS value is equated with the SIFS* value to avoid retransmissions.

Transmitter side Misbehaving

Transmitter side misbehaving may occur by decreasing the response time value from the receiver by TOCTS frame. To avoid this type of misbehavior approach the new timer TODATA (Time Out period of DATA i.e.. TRTS + SIFS + TCTS + SIFS + TDATA) is transmitted along the RTS frame and is enabled only in RNAV. For implementation, a new bit can be added to the MAC header to indicate whether this field is to be enabled in the destination address. After the MAC header is decoded, receiver node can refer this time period if the DATA is not reached within the time period mentioned in header and decide whether the sender is misbehaving.











Figure 6 Receiver initiated with timer

The misbehaving sender node chooses smaller TOCTS i.e…TOCTS*. So that it receives CTS after timeout. Because of this timeout the sender sends RTS again. If it continues again and again, the receiver found sender is misbehaving and it checks TODATA. Within the timeout period DATA is not reached and RTS is transmitted greater then threshold value the receiver adjust the TOCTS to TOCTS*.

Detection system for transmitter side misbehaving with Adaptive NAV

Every receiver can maintains the sequence counter for its packet reception. If the receiver receives RTS frame more than once it increments the Mis_count value. Receiver wait for the response from the sender if DATA is not received, it checks the Mis_count value. Once it reaches the

Mis_count(Rx) > ThresholdTOCTS*= TOCTS

ANAV adjust with smaller TOCTS* to receive the DATA packet from the sender. Then receiver sends the ACK to sender node. This indicates that the misbehaving node may have,

(1) Either sender node is in under attack.

(2) Sender node is not aware of the detection system implemented by Receiver.

(3 Sender node is aware but is avoiding degrading further its trust level.


To validate the proposed QoS model we have implemented in the Network Simulator 2 (NS2). The simulation scenario is created with 20 nodes. The throughput of the network is measured and compared with the IEEE 802.11. Here we are setting the experimental setup as,


Number of nodes


Network Size


VCS range










Thus the number of nodes is increased the throughput will also increases. The performance of the nodes without hidden and exposed nodes is increased shown in figure 8.

Figure 6 Throughput of the network with HFD and SDN


In this QoS model, the Hidden and Exposed terminals are removed with the HFD and SDN algorithms. By using this model the throughput of the network is increased and overhead is reduced due to the consideration of single virtual carrier sensing mechanism. With the updated RNAV timer the transmission in the network from one node to another successfully takes place without any interference. This MAC layer problem can be solved in MAC layer itself with the use of VCS.

Article name: Combating Hidden And Exposed Terminal Problem In Ad Hoc Networks Computer Science essay, research paper, dissertation