Wireless ad hoc networks Acknowledgement Slides borrowed from Richard Y Yang Yale Infrastructure based v s ad hoc Infrastructure based networks Cellular network 802 11 access points Ad hoc networks Mobile ad hoc networks Military applications emergency rescue Mesh networks Last mile of the Internet Provide high speed wireless network Infrastructure v s ad hoc infrastructure mode AP Access Point AP AP wired network AP ad hoc mesh mode 3 Infrastructure based v s ad hoc Infrastructure based networks Deployment is costly Structures are not flexible Vulnerable to attacks Ad hoc networks Flexible easy to deploy cheaper Robust and resilient to attacks failures self healing Problem many research problems to achieve high capacity Mesh networks Multiple projects tested in Berlin Germany South africa India DIY guide on wiki Capacity of Wireless Networks The question we study how much traffic can a wireless network carry assuming we can solve MAC issues perfectly Why study capacity learn the fundamental limits of wireless networks separate the spatial reuse perspective and the distributed synchronization MAC perspective gain insight for designing effective wireless protocols 6 Interference Model Transmission successful if there are no other transmitters transmit at the same freq and code within a distance 1 r of the receiver where r is the distance from the sender to the receiver receiver 1 r r sender 7 Derivation of Capacity for Arbitrary Networks Model domain is a disk of unit area there are n nodes in the domain the transmission rate is W bits sec 8 Two Constraints Interference constraint transmission successful if there are no other transmitters within a distance 1 r of the receiver Radio interface constraint a single half duplex transceiver at each node receiver 1 r r either transmits or receives transmits to only one receiver receives from only one sender sender 9 Assumptions Optimal power assignment transmission range Optimal scheduling multi hop routing Node are static Random source destination pairs Consider asymptotic capacity when n infty Capacity Capacity Total bits transmitted by all nodes 11 Transmission range Transmission range is big Interference constraints prevent simultaneous transmissions Transmission range is small It takes a lot of hops to arrive at the destination Even at optimal configuration the capacity is low In fact it converges to 0 as n infty Transmission Model Bit time Perspective Chop time into a total of WT bit times in T seconds The transmission decision is made for each bit 1 1 2 2 3 3 4 4 5 5 bit time 1 bit time 2 bit time t bit time WT 13 Transmission Model End to end Perspective Assume the network sends a total of T end to end bits in T seconds Assume the b th bit makes a total of h b hops from the sender to the receiver Let rbh denote the hop length of the h th hop of the b th bit 1 2 T 2 14 Hop Count Constraint 2 Since there are a total of WT bit times and during each bit time there are at most n 2 simultaneous transmissions we have T WTn h b 2 b 1 15 Area Constraint Consider two simultaneous transmissions at a bit time 1 r 1 r r j r Djm r Dim 1 r Djm r Djk 1 r Djm r r 2 m r r k i 16 Area Constraint For each transmission with distance r from sender to receiver we draw a circle with radius r These circles do not overlap 17 Area Constraint Global Picture 2 18 Area Constraint Global Picture 2 sum over all circles since each circle has at least of its area in the unit disk 19 Summary Two Constraints Radio interface constraint a single half duplex transceiver at each node T n h b WT 2 b 1 Interference constraint transmission successful if there are no other transmitters within a distance 1 r of the receiver T h b 16WT r 2 b 1 h 1 h 2 b 20 Capacity Bound Let L be the average direct line distance for all source destination pairs T h b TL r h b b 1 h 1 T h b TL rbh b 1 h 1 T Note n i 1 xi 2 n n x i2 i 1 T h b h b h 2 r b b 1 b 1 h 1 WTn 16WT 8 WT TL 2 2 8W L n n Question what does the result mean 21 Capacity Capacity in bit meter for n nodes is 8W L n On average each node has O W n bitmeter sec When n infty the capacity per node is 0 Capacity upper bound An ad hoc network does not scale To improve capacity Avoid multi hop traffic Use multiple radio interfaces Reduce interference Use multiple channels Improving Capacity Change Traffic Pattern To make communications local node placement change the demand patterns thus L e g base stations access points with high speed backhaul use mobility BS1 infrastructure B A F S C BS2 D E T 24 Improving Capacity Reduce Radio Interface Constraint Multiple radio interfaces codes 1 m 25 Improving Capacity Reduce Interference Constraint Antenna design steered switched directional antennas A B C D A B C D Non interfering channels 26 Improving capacity exploiting interference Network coding A A a B a b B b a b Wireless broadcast Hidden terminal problem C C Hidden Terminal Scenario C Src C R1 C R2 C Dst Hidden Terminal Scenario C Src P1 C R1 C R2 C Dst Hidden Terminal Scenario C Src P2 C R1 C R2 P1 1 Src and R2 transmit simultaneously C Dst Hidden Terminal Scenario C Src C R2 C R1 P1 C Dst P2 1 Src and R2 transmit simultaneously 2 R1 subtracts P1 which he relayed earlier to recover P2 that he wants Hidden Terminal Scenario C Src C R2 C R1 P1 P2 R2 and Src are hidden terminals Simultaneous transmission Collision With analog network coding Simultaneous transmission Success C Dst Next Improving capacity using multiple channels in 802 11 mesh SSCH Multi Channel 802 11 Mesh Wireless LANs APs determine the channel Clients share the same channel as their associated APs 802 11 mesh networks Each node can choose operating 802 11 channels to increase spatial reuse 1 2 2 1 34 Operating Channels for 802 11b Europe ETSI channel 1 2400 2412 channel 7 channel 13 2442 2472 22 MHz 2483 5 MHz US FCC Canada IC channel 1 2400 2412 channel 6 channel 11 2437 2462 22 MHz 2483 5 MHz 35 Operating channels for 802 11a US U NII 36 5150 40 44 48 52 56 60 64 5180 5200 5220 5240 5260 5280 5300 5320 channel 5350 MHz 16 6 MHz 149 153 157 161 channel center frequency 5000 5 channel number MHz 5725 5745 5765 5785 5805 5825 MHz 16 6 MHz 36 Multi Channel 802 11 Mesh Goal Goal Using right channels at right nodes at right time to improve network throughput 1 1 2 2 1 c 1 1 m c 37 Multi Channel Network Capacity c number of channels Channels 38 Setup A …