Wireless ad hoc networksAcknowledgement: Slides borrowed from Richard Y. Yang @ YaleInfrastructure-based v.s. ad hoc• Infrastructure-based networks– Cellular network– 802.11, access points•Ad hoc networks•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 hocinfrastructuremodeAPAPAPwired networkAP: Access Point3ad-hoc (mesh) modeInfrastructure-based v.s. ad hoc• Infrastructure-based networks– Deployment is costly. Structures are not flexible.– Vulnerable to attacks.•Ad hoc networks•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 networksMultiple projects tested in Berlin, Germany, South africa, India. DIY guide on wikiCapacity 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?•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 protocols6Interference 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 thereceiverreceiver7receiversenderr(1+∆)rDerivation 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–the transmission rate is W bits/sec8Two Constraints transmissionsuccessful if there areno other transmitterswithin a distance Interference constraint a single half-duplex transceiver at each node: either transmits or Radio interface constraint9within a distance (1+∆)r of the receiverreceiversenderr(1+∆)reither transmits or receives transmits to only one receiver receives from only one senderAssumptions• Optimal power assignment /transmission range• Optimal scheduling & multi-hop routing•Node are static.•Node are static.• Random source-destination pairs• Consider asymptotic capacity when n-> inftyCapacity• Capacity = λ• Total bits transmitted by all nodes11Transmission range• Transmission range is big– Interference constraints prevent simultaneous transmissions•Transmission range is small•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->inftyTransmission Model: Bit-time Perspective• Chop time into a total of WT bit-times in T seconds• The transmission decision is made for each bit13bit time 2 bit time tbit time WTbit time 11235412354Transmission 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 rbhdenote the hop-length of the h-th hop of the b-th bit14212λTHop-Count ConstraintSince there are a total of WT bit-times, and during each bit-timethere are at most n/2 simultaneous transmissions, we have∑=≤TbWTnbhλ12)(152Area Constraint• Consider two simultaneoustransmissions at a bit-timemk(1+∆)r’r’j(1+∆)r½ ∆r½ ∆r’16ijrDjm+ r >= Dim>= (1+∆)r’⇒Djm>= (r+r’) ∆ /2Djm+ r’ >= Djk>= (1+∆)rArea Constraint• For each transmissionwith distance r from sender to receiver, we draw a circle we draw a circle with radius ½ ∆ r• These circlesdo not overlap17Area Constraint: Global Picture182Area Constraint: Global Picturesum over all circles, since each circle has at least ¼ of its area in the unit disk, 192Summary: Two Constraints transmissionsuccessful if there areno other transmitterswithin a distance Interference constraint a single half-duplex transceiver at each nodeRadio interface constraint20within a distance (1+∆)r of the receiver∑=≤TbnWTbhλ12)(21)(1216)(∆≤∑∑= =πλWTrTbbhhhbCapacity Bound∑∑= =≤TbbhhhbrTLλλ1)(1∑∑==≤niiniixnx1221Note: Let L be the average (direct-line) distance for all source-destination pairs.∑∑∑∑∑≤≤→TbhhTTbhhλλλλ)(2)()()(21∑∑∑∑∑= === =≤≤Tb hhbTbTb hhbrbhrTLλλλλ1 1211 1)()(nWTWTWTnTL∆=∆≤→ππλ81622nWL∆≤→πλ8Question: what does the result mean?Capacity• Capacity (in bit-meter) for n nodes is•On average, each node has O(W/√n) bit-nWL∆≤πλ8•On average, each node has O(W/√n) bit-meter/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–Use multiple radio interfaces– Reduce interference– Use multiple channelsImproving 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 24FEAB CDBS1 BS2STinfrastructureImproving Capacity: Reduce Radio Interface Constraint• Multiple radio interfaces/codes251mImproving Capacity: Reduce Interference Constraint• Antenna design: steered/switched directional antennas26• Non-interfering channels ADCBABDCImproving capacity: exploiting interference• Network codingA CBa bACBa⊕b a⊕b• Hidden terminal problemACBWireless broadcastCCCCHidden Terminal ScenarioR1R2SrcDstHidden Terminal ScenarioCCCCR1R2SrcDstP1Hidden Terminal ScenarioCCCCR1R2SrcDstP2P11) Src and R2 transmit simultaneouslyHidden Terminal ScenarioCCCCR1R2SrcDst1) Src and R2 transmit simultaneously2) R1 subtracts P1, which he relayed earlier to recover P2 that he wantsP1P2Hidden Terminal ScenarioCCCCR1R2SrcDstR2 and Src are hidden terminalsSimultaneous transmission CollisionWith analog network coding, Simultaneous transmission Success!P1P2Next• 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 –Each node can choose operating 802.11 channels to increase spatial reuse341122Operating Channels for