cs144: Review SessionChallenges in WirelessModulation Signal, Noise, Interference CD vs. CAWireless RoutingDSDVAODVOLSRLink Cost MetricsSrcrEncodingErasure CodesNetwork CodingQuestions?cs144: Review Sessiony Intro to Wirelessy Routing Protocolsy Coding & Network Coding12y No wires, no links; Signal goes through airy Attenuationy Interferencey Selfy Other signalsy Obstaclesy Collision detection very difficulty Different typesy on –off keyingy amplitude shift keying y frequency shift keyingy phase shift keyingy Why is it cool?y Quadrature allows 2 bits of info per 1 physical bity Multiple transmissions in the same medium3y Signaly You are talking to mey Noisey That ringing in my earsy Interferencey Ben talkingy dBm is a log scale: dBmdBmdBmINS459550||||=−−=+4y Which one is harder in wireless?y Why?y How do we do it in wireless?y If channel cleary Sendy Elsey Back offy Hidden‐terminal problemy RTS/CTS5Wireless Routingy The wired worldy Assume topology is stabley Links are less dynamicy Usually not battery constrainedy The wireless worldy Nodes come and goy Lots of link dynamicsy Interferencey Want energy‐efficient routing6DSDVy Proactivey Maintains routes to all nodes; continuouslyy Destination SEQ numbersy To avoid loopsy If you hear newer SEQ for a dest Æ use ity If a link breaks Æ increment SEQy Too many route advertisements?y Don’t send all the timey Compute settling time7AODVy Reactive (on‐demand)y Look for route to destination only when you need ity Mechanismy Flood a “route request” messagey Use controlled flooding (TTL 1, TTL 2, etc)y Receive “route reply” from node with cached route or from destination itselfy Set up route along the rev erse path8OLSRy Use Multi‐Point Relays to limit floodingy Node keeps track of:y Ne ighborsy MPRs, which gives 2‐hop neighborhoody Periodic HELLO msgs to discover linksy Topology Control msgs through MPRs to advertise link state9Link Cost Metricsy Want to minimize hop county Causes protocol to pick somewhat longer linksy Links more likely to be on SNR/PRR edgey ETXy Number of transmissions required to get a ACKy Add ETX across links to get path ETXy ETT – estimated time of transmissiony Probe different bit rates & pick bestBAABARRPRR110Srcry Source Routingy Source specifies one or more hops along the pathy Broadcast periodic packets at all bit‐rates to determine best ETTy Data packets contain link cost metricy Use ETT/ETX to pick path + dynamically change bit‐ratey (For bit‐rate adaptation algorithm see Phil’s notes)11Enc odingy CRCs = Can’t Remember Crapy Alternatively, Cy clic Redundancy Checksy Computed at the physical layery Encode n bits into c bits of CRCy Detects bursts of errors up to cy Message Authentication Code (MAC)y Similar to CRC, seeded with a secret numbery Reed‐Solomony Treat data as a polynomial of degree k‐1y k data points are enough to reconstruct the datay Giving more than k points allows for corruption of some12Er asure Codesy Large piece of data + many clientsy Send k(1+γ) packets & any k can be used to reconstruct the datay LT codes (Luby Tornado)y Break data into chunky XOR chunks (1, 2, or more together Æ degree)y Send XORed codewordsy Get data out of degree 1 codewords (easy)y XOR known input symbols out of code wordsy Important to control the degree of code wordsy Guarantee that after some n packets the other side can recov er the datay Key: ANY packets, so no need to keep state!!!13Network Codingy Use the broadcast nature of the mediumy MOREy Send linear combinations of packetsy Hope 2‐hop neighbor overheard some packetsy Opportunistic Receptiony Allow more than one node to forward the packetsy When destination discovers that it can decode packets, it sends an end‐to‐end ACKy Need K linearly independent combinationsy Nodes stop forwarding ; Source stops sendingy Bidirectional Network Coding1415define: llama: the Quake‐lingo version of lamer, loser,
View Full Document
Unlocking...