Hidden Terminal Problem in Wireless LANs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

"""
RTS/CTS Duration Field Calculation
802.11 frame timing analysis
"""
 
def calculate_frame_time_ofdm(frame_bytes: int, data_rate_mbps: float, 
                                symbol_time_us: float = 4.0,
                                preamble_us: float = 20.0) -> float:
    """
    Calculate transmission time for OFDM-based PHY (802.11a/g/n/ac).
    
    Parameters:
    - frame_bytes: Total frame size in bytes including MAC header and FCS
    - data_rate_mbps: PHY data rate in Mbps
    - symbol_time_us: OFDM symbol duration (4 μs for 20 MHz channel)
    - preamble_us: PHY preamble and header duration (20 μs for 802.11a/g)
    
    Returns: Transmission time in microseconds
    """
    # Service field (16 bits) + MAC frame + tail (6 bits)
    total_bits = 16 + (frame_bytes * 8) + 6
    
    # Bits per symbol at given data rate
    bits_per_symbol = data_rate_mbps * symbol_time_us
    
    # Number of OFDM symbols (ceiling)
    import math
    n_symbols = math.ceil(total_bits / bits_per_symbol)
    
    # Total time = preamble + (symbols × symbol_time)
    return preamble_us + (n_symbols * symbol_time_us)
 
def calculate_rts_cts_duration(
    data_frame_bytes: int,
    data_rate_mbps: float,
    control_rate_mbps: float = 6.0,  # Typically 6 Mbps for control frames
    sifs_us: float = 16.0  # SIFS for 802.11g
) -> dict:
    """
    Calculate all Duration field values for RTS/CTS exchange.
    
    802.11g example with OFDM.
    """
    # Frame sizes
    RTS_BYTES = 20
    CTS_BYTES = 14
    ACK_BYTES = 14
    MAC_HEADER_BYTES = 34  # Typical MAC header for data
    
    total_data_bytes = MAC_HEADER_BYTES + data_frame_bytes + 4  # +4 for FCS
    
    # Calculate individual transmission times
    rts_time = calculate_frame_time_ofdm(RTS_BYTES, control_rate_mbps)
    cts_time = calculate_frame_time_ofdm(CTS_BYTES, control_rate_mbps)
    data_time = calculate_frame_time_ofdm(total_data_bytes, data_rate_mbps)
    ack_time = calculate_frame_time_ofdm(ACK_BYTES, control_rate_mbps)
    
    # Duration field values
    duration_rts = sifs_us + cts_time + sifs_us + data_time + sifs_us + ack_time
    duration_cts = duration_rts - cts_time - sifs_us
    duration_data = sifs_us + ack_time
    
    return {
        'rts_time': rts_time,
        'cts_time': cts_time,
        'data_time': data_time,
        'ack_time': ack_time,
        'sifs': sifs_us,
        'duration_rts': duration_rts,
        'duration_cts': duration_cts,
        'duration_data': duration_data,
        'total_exchange_time': rts_time + sifs_us + cts_time + sifs_us + data_time + sifs_us + ack_time
    }
 
# Example: 1500-byte payload at 54 Mbps data rate
result = calculate_rts_cts_duration(
    data_frame_bytes=1500,
    data_rate_mbps=54.0,
    control_rate_mbps=6.0,
    sifs_us=16.0
)
 
print("=== RTS/CTS Duration Calculation ===")
print(f"Data payload: 1500 bytes at 54 Mbps")
print(f"Control frames at: 6 Mbps")
print()
print("--- Frame Transmission Times ---")
print(f"RTS (20 bytes):     {result['rts_time']:.1f} μs")
print(f"CTS (14 bytes):     {result['cts_time']:.1f} μs")
print(f"Data (~1540 bytes): {result['data_time']:.1f} μs")
print(f"ACK (14 bytes):     {result['ack_time']:.1f} μs")
print(f"SIFS:               {result['sifs']:.1f} μs")
print()
print("--- Duration Field Values ---")
print(f"Duration in RTS: {result['duration_rts']:.0f} μs")
print(f"Duration in CTS: {result['duration_cts']:.0f} μs")
print(f"Duration in Data: {result['duration_data']:.0f} μs")
print()
print(f"Total exchange time: {result['total_exchange_time']:.0f} μs")

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119

"""
RTS/CTS Efficiency and Break-even Analysis
When does RTS/CTS overhead pay off?
"""
 
import math
 
def ofdm_frame_time(bytes_count: int, rate_mbps: float, 
                    preamble_us: float = 20.0) -> float:
    """Calculate OFDM frame transmission time in μs."""
    bits = 16 + (bytes_count * 8) + 6  # Service + data + tail
    bits_per_symbol = rate_mbps * 4  # 4 μs symbol time
    symbols = math.ceil(bits / bits_per_symbol)
    return preamble_us + (symbols * 4)
 
def calculate_efficiency(payload_bytes: int, data_rate_mbps: float,
                         control_rate_mbps: float = 6.0,
                         sifs_us: float = 16.0, difs_us: float = 34.0,
                         use_rts_cts: bool = False) -> dict:
    """
    Calculate throughput efficiency with and without RTS/CTS.
    """
    # Frame sizes
    mac_header = 34
    fcs = 4
    total_data_bytes = mac_header + payload_bytes + fcs
    
    # Transmission times
    data_time = ofdm_frame_time(total_data_bytes, data_rate_mbps)
    ack_time = ofdm_frame_time(14, control_rate_mbps)
    
    if use_rts_cts:
        rts_time = ofdm_frame_time(20, control_rate_mbps)
        cts_time = ofdm_frame_time(14, control_rate_mbps)
        total_time = (difs_us + rts_time + sifs_us + cts_time + 
                     sifs_us + data_time + sifs_us + ack_time)
    else:
        rts_time = 0
        cts_time = 0
        total_time = difs_us + data_time + sifs_us + ack_time
    
    # Efficiency = payload bits / total channel time
    payload_bits = payload_bytes * 8
    efficiency = payload_bits / total_time  # Mbps
    
    return {
        'payload_bytes': payload_bytes,
        'data_rate_mbps': data_rate_mbps,
        'rts_time': rts_time,
        'cts_time': cts_time,
        'data_time': data_time,
        'ack_time': ack_time,
        'total_time': total_time,
        'efficiency_mbps': efficiency,
        'efficiency_percent': (efficiency / data_rate_mbps) * 100,
        'overhead_time': rts_time + sifs_us + cts_time + sifs_us if use_rts_cts else 0
    }
 
def find_breakeven_frame_size(collision_rate: float, data_rate_mbps: float = 54.0):
    """
    Find frame size where RTS/CTS overhead equals collision cost savings.
    
    Collision cost = P(collision) × (data_frame_time + retry_overhead)
    RTS/CTS benefit = collision on short RTS instead of long data
    
    Simplified model: RTS/CTS beneficial when collision rate is high enough
    that savings from avoiding data frame collisions exceed RTS/CTS overhead.
    """
    control_rate = 6.0  # Mbps
    sifs = 16.0  # μs
    
    rts_time = ofdm_frame_time(20, control_rate)
    cts_time = ofdm_frame_time(14, control_rate)
    rts_cts_overhead = rts_time + sifs + cts_time + sifs  # ~128 μs
    
    # Break-even: collision_rate × data_time_saved = rts_cts_overhead
    # data_time_saved ≈ data_time (if collision, retransmit whole frame)
    # Break-even data_time = rts_cts_overhead / collision_rate
    
    if collision_rate <= 0:
        return float('inf')
    
    breakeven_data_time = rts_cts_overhead / collision_rate
    
    # Convert back to frame size (approximate)
    # For 54 Mbps: ~250 ns per byte (rough)
    # More accurate: solve ofdm_frame_time equation
    for size in range(100, 3000, 10):
        if ofdm_frame_time(size + 38, data_rate_mbps) >= breakeven_data_time:
            return size
    
    return 3000
 
print("=== RTS/CTS Efficiency Analysis ===")
print()
 
# Compare efficiency at different frame sizes
print("--- Efficiency vs Frame Size (54 Mbps data rate) ---")
print(f"{'Payload':>8} | {'Without RTS/CTS':>18} | {'With RTS/CTS':>16} | {'Overhead':>10}")
print("-" * 62)
 
for payload in [64, 256, 512, 1024, 1500, 2000]:
    without = calculate_efficiency(payload, 54.0, use_rts_cts=False)
    with_rts = calculate_efficiency(payload, 54.0, use_rts_cts=True)
    
    print(f"{payload:>6} B | {without['efficiency_mbps']:>8.2f} Mbps ({without['efficiency_percent']:>4.1f}%) | "
          f"{with_rts['efficiency_mbps']:>6.2f} Mbps ({with_rts['efficiency_percent']:>4.1f}%) | "
          f"{with_rts['overhead_time']:>6.0f} μs")
 
print()
print("--- Break-even Frame Size by Collision Rate ---")
print(f"{'Collision Rate':>15} | {'Break-even Size':>16}")
print("-" * 35)
for rate in [0.01, 0.05, 0.10, 0.20, 0.30, 0.50]:
    be_size = find_breakeven_frame_size(rate)
    print(f"{rate:>14.0%} | {be_size:>14} bytes")
 
print()
print("Insight: RTS/CTS beneficial when collision rate × data size > overhead")

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155

"""
NAV (Network Allocation Vector) State Machine
Conceptual implementation showing NAV operation
"""
 
from dataclasses import dataclass
from enum import Enum, auto
import time
 
class ChannelState(Enum):
    IDLE = auto()
    PHYSICAL_BUSY = auto()
    VIRTUAL_BUSY = auto()
    BOTH_BUSY = auto()
 
@dataclass
class StationNAV:
    """Represents a station's NAV state."""
    nav_value: float = 0  # Current NAV in microseconds
    nav_set_time: float = 0  # When NAV was last set
    
    def update_nav(self, duration_us: float, current_time: float) -> bool:
        """
        Update NAV based on received Duration field.
        Returns True if NAV was updated, False if ignored.
        
        802.11 Rule: Only update if new duration > remaining NAV
        """
        remaining_nav = self.get_remaining_nav(current_time)
        
        if duration_us > remaining_nav:
            self.nav_value = duration_us
            self.nav_set_time = current_time
            return True
        return False
    
    def get_remaining_nav(self, current_time: float) -> float:
        """Get remaining NAV time in microseconds."""
        elapsed = (current_time - self.nav_set_time) * 1e6  # Convert to μs
        remaining = self.nav_value - elapsed
        return max(0, remaining)
    
    def is_nav_zero(self, current_time: float) -> bool:
        """Check if NAV has expired."""
        return self.get_remaining_nav(current_time) <= 0
 
class Station:
    """Wireless station with physical and virtual carrier sensing."""
    
    def __init__(self, station_id: str):
        self.id = station_id
        self.nav = StationNAV()
        self.physical_rx_active = False  # Physical carrier sense
        
    def receive_frame(self, frame_type: str, duration_us: float, 
                     from_station: str, current_time: float):
        """Process received frame and update NAV if applicable."""
        
        print(f"[{self.id}] Received {frame_type} from {from_station}, "
              f"Duration={duration_us} μs")
        
        if frame_type in ['RTS', 'CTS', 'DATA']:
            updated = self.nav.update_nav(duration_us, current_time)
            if updated:
                print(f"  → NAV updated to {duration_us} μs")
            else:
                remaining = self.nav.get_remaining_nav(current_time)
                print(f"  → NAV not updated (remaining {remaining:.0f} μs > {duration_us} μs)")
    
    def get_channel_state(self, current_time: float) -> ChannelState:
        """Determine channel state from physical and virtual sensing."""
        phy_busy = self.physical_rx_active
        virt_busy = not self.nav.is_nav_zero(current_time)
        
        if phy_busy and virt_busy:
            return ChannelState.BOTH_BUSY
        elif phy_busy:
            return ChannelState.PHYSICAL_BUSY
        elif virt_busy:
            return ChannelState.VIRTUAL_BUSY
        else:
            return ChannelState.IDLE
    
    def can_transmit(self, current_time: float) -> bool:
        """Check if station is allowed to transmit."""
        state = self.get_channel_state(current_time)
        if state == ChannelState.IDLE:
            return True
        print(f"  [{self.id}] Cannot transmit - channel state: {state.name}")
        return False
 
# Simulation example
def simulate_rts_cts_nav_operation():
    """
    Simulate NAV operation during RTS/CTS exchange.
    
    Scenario:
    - Station A wants to send to AP
    - Station B is in range of A (hears RTS)
    - Station C is hidden from A but in range of AP (hears CTS only)
    """
    print("=== NAV Operation Simulation ===")
    print()
    
    # Create stations
    station_a = Station("A (Sender)")
    station_b = Station("B (Visible)")
    station_c = Station("C (Hidden)")
    ap = Station("AP (Receiver)")
    
    # Timing (in seconds for simulation, values in μs for NAV)
    t = 0.0
    
    # RTS/CTS timing for 1500-byte frame at 54 Mbps
    SIFS = 16
    RTS_DURATION = 1000  # μs until end of ACK
    CTS_DURATION = RTS_DURATION - 44 - SIFS  # After CTS transmission
    DATA_DURATION = 100  # μs (ACK time only)
    
    print(f"T={t:.6f}s: Station A sends RTS")
    # Station B hears RTS, sets NAV
    station_b.receive_frame("RTS", RTS_DURATION, "A", t)
    # Station C does NOT hear RTS (hidden from A)
    print(f"  Station C: Does not receive RTS (hidden from A)")
    print()
    
    t += 0.000060  # 60 μs for RTS + SIFS
    print(f"T={t:.6f}s: AP sends CTS")
    # Station B hears CTS (updates NAV with lower value - no change)
    station_b.receive_frame("CTS", CTS_DURATION, "AP", t)
    # Station C hears CTS (first NAV update!)
    station_c.receive_frame("CTS", CTS_DURATION, "AP", t)
    print()
    
    t += 0.000050  # 50 μs for CTS + SIFS
    print(f"T={t:.6f}s: Station A sends DATA")
    print(f"  Station B: Remaining NAV = {station_b.nav.get_remaining_nav(t):.0f} μs")
    print(f"  Station C: Remaining NAV = {station_c.nav.get_remaining_nav(t):.0f} μs")
    
    # Can stations B or C transmit?
    print()
    print("--- Can stations transmit during data? ---")
    station_b.can_transmit(t)
    station_c.can_transmit(t)
    
    # After exchange completes
    t += 0.001100  # 1100 μs for data + ACK
    print()
    print(f"T={t:.6f}s: Exchange complete")
    print(f"  Station B: Remaining NAV = {station_b.nav.get_remaining_nav(t):.0f} μs")
    print(f"  Station C: Remaining NAV = {station_c.nav.get_remaining_nav(t):.0f} μs")
    print(f"  Station B can transmit: {station_b.can_transmit(t)}")
    print(f"  Station C can transmit: {station_c.can_transmit(t)}")
 
simulate_rts_cts_nav_operation()