Designing high capacity wireless networks

Why wireless?
- enable a different class of apps
  mobility, location based, sensor networks
- cheaper to deploy(?) and pervasive

Why is wireless different (harder) than wired?
- radio is a shared medium, esp. when omnidirectional antenna is used
  no notion of "link"s
  * losses are due to fading as well as collisions
    collisions cannot be detected reliably 
    wired ethernet abandons packet in transmission if collision is detected (i.e. collision in wireless is expensive)
  * difficult to tell who might interfere with who
- radio channels vary in quality with time and location
  * routing protocol should respond to changes quickly

In general, high throughput design should:
- make every transmission count
  * reduce collisions
- control transmission errors
  * link layer retransmission
  * aggressive error correction (e.g. lower transmission rate)
- maximize spatial reuse
  * channel allocation
  * power control

Types of wireless networks:
- "cellular" vs. multi-hop
  cellular:
  Packets are transmitted over the wireless medium once to reach a wired gateway
  cellular telephone
  802.11 base stations
  multihop:
  Packets are forwarded over multiple wireless hops 
  urban mesh networks 
  sensor networks
- licensed vs. unlicensed frequency
- long vs. short range

Wireless MAC protocols

What is it?
- schedule which node is allowed to send 
- act within the "local radio neighborhood" 

Challenges:
- avoid collision
  tension with maximize capacity
- reasonable fairness among contending nodes
- hidden terminals
- exposed terminals

CDMA
- nodes w/ orthogonal codes can transmit simultaneously 

TDMA
cellular telephone network
master/slaves
master determines the transmission schedule of slaves
e.g. a simple form of bluetooth
divide slots into odd and even, master transmits in odd slot and the next slot is for the slave who received data to transmit to master

CDMA/TDMA are good during persistent high load w/ a master in control..

CSMA/CA (802.11)
- Pioneered by ALOHAnet in 1970s
- Slotted, nodes attempt to send only at the beginning of a slot. 
  collision can only only happen on slot boundaries instead of everywhere.
- carrier sense w/ a contention window (CW)
  nodes pick a random number of slots between [0,cw] as its "listening" period.
  Instead of listening for a random period, why not send immediately?
  if medium is idle during listening period, send, otherwise, defer(hold the countdown)
  Instead of defer, why not backoff?
- exponential backoff
  nodes acknowledge each transmission, since collisions can not be detected reliably
  if no ack, double cw

Carrier-sense is not ideal for wireless
- provides info. about potential collision at sender
- collision happens at receiver

hidden terminal: 
A ---> B       C ~~~~> D

exposed terminal:
A <----B       C ~~~~> D

Reservation-based scheme (802.11 w/ RTS/CTS, a.k.a MACAW)
RTS/CTS/Data/ACK
Collisions for large data packets are expensive
Use smaller control packets to contend for medium

RTS (request-to-send) CTS (clear to send) include the time duration of the data
exchange (including ack) to reserve the channel for a period of time

Assumptions: transmissions are completely symmetric, capture and interference negligible --> unit disk model of identical transmission ranges
Nodes overhear RTS/CTS remain quiet 
Nodes that do not hear CTS response do binary exponetial backoff before trying to send RTS again
How does it handle hidden terminal?
Does it reduce the effect of exposed terminal?

In practice, RTS/CTS is often not used, why?
* non-negligible overhead 
  radios support various rates ranging from 1Mbps to 55Mbps.
  RTS/CTS must be sent at lowest supported rate (1Mbps) to ensure all possible interfering nodes can decode
  hence a 30 byte RTS is effectively like a 1500 byte MTU sized data packet
* most radio deployment is in carefully managed infrastructure mode 
  hidden terminal problems less of an issue