huge proliferation of wireless devices: smartphones, tablets "more than one person per computer -> more than one computer per person" 10 billion wireless devices at Internet's edges both fixed and mobile usage common: sitting, walking, riding in a vehicle indoors, outdoors key property of wireless use scenario: *coherence time* - roughly speaking, time during which the behavior ("quality") of the wireless channel between a sender and receiver remains unchanged - depends on user's rate of movement: stationary user, longer coherence time; faster the speed of motion, shorter coherence time - why motion-dependent: intuitively, multi-path fading (reflection/environment-based) and attenuation (distance-based) determine channel quality and depend on physical location; both change as user moves - figure of merit from SoftRate paper: - walking speed: *slow fading*, tens of ms (multiple packet times); causes burst of packet losses when channel quality drops (if bit-rate unchanged) - vehicular speed: *fast fading*, 10 to few hundred us (less than one packet time) - overall, shorter coherence time, shorter duration of measurements of channel quality (e.g., RSSI, packet loss, BER) valid not just bit-rate adaptation; routing influenced by mobility, too: rate of change in neighbors proportional to speed of motion, neighbors likely to remain in range may be predictable based on current heading and speed basic observation: how aggressively one adapts (e.g., bit-rate) ought to depend on how stable channel quality is: - if coherence time short because of mobility, may want to adapt bit-rate rapidly--channel behavior is less correlated in time, and no reason to expect future to be similar to past for long - but if node isn't moving, brief fading episode may be transitory, and channel should return to previously observed quality--so may want to average for longer when measuring channel quality, and may not want to adapt bit-rate so rapidly opportunity from technology trends: mobile devices incorporate *sensors*: - GPS, accelerometer, compass - possible for software to know "is user moving?", position, speed, heading: these are *sensor hints* - useful inputs for wireless networking algorithms, to improve performance? - sensor hints may come from device's own sensor(s) or be advertised by a neighbor from its sensor(s) contributions: - sensor hint-driven bit-rate adaptation (to improve throughput) - sensor hint-driven AP association/disassociation (to improve throughput *or* minimize disruption from handoffs) - sensor hint-driven adaptation of probe traffic rate for neighbor list maintenance/link quality measurement (to reduce probe rate while stationary, increase while mobile; saves network capacity) - sensor hint-driven route selection (to favor selection of routes along which adjacent nodes won't move out of range) deducing movement of user: - indoors, use accelerometer; outdoors accelerometer and GPS - "moving" true when acceleration or velocity != 0 - every 2 ms (Sparkfun) or 20 ms (Android), query force on x, y, z axes - get time series of x, y, z force point measurements; take abs magnitude - sliding window of 5 most recent abs mags; slides by one sample - compute stdev over window; if exceeds threshold a, conclude movement - if stdev under thresh for n successive windows, report node stationary - w = 5 (win size), a = 0.15 m/s^2 (stdev thresh), n = 10 (hysteresis) - movement hint H_{t}: 1 for "movement", 0 for "no movement" - @ 50 Hz, can detect movement within 100 ms, stationary 200 ms - @ 500 Hz, can detect movement within 10 ms, stationary 20 ms - implemented for Nexus One, G1, iPhone 4, SparkFun accelerometer; good results on all - anecdotally report accurate for walking, rolling on chair, in car, on both laptop with accelerometer and Android phone - question: calibration? authors claim in Section 7 that movement hint is portable across accelerometers/devices. walking hint (Eriksson's alg) must be tuned per *type* of accelerometer; not for each instance - question: power consumption for measuring accelerometer every 2 ms or 20 ms? See table in Figure 20: 22 hours -> 19 hours lifetime other hints: - "walking detector" from TransitGenie - user's "heading" from digital compass (assume know device orientation) (XXX power? see Fig 20: 22 -> 18 hours) - speed: outdoors from GPS (XXX power? see Fig 20: 22 -> 6 hours)) - indoor-vs.-outdoor: whether GPS can be received or not! (XXX power?) can announce hints in packets, describing node's mobility status - hint message in Figure 3: source MAC, # hints, [hint type, value] - supported at end of UDP packet and raw 802.11 packets (different devices may support one but not the other) application 1: bit-rate adaptation motivation: difference in correlation between successive packet losses for static vs. mobile cases - indoors, 54 Mbps transmission, 1000-byte back-to-back pkts from laptop to smartphone (static) and to smartphone being carried at walking speed (mobile) - given loss of a packet, plot of conditional probability of loss of subsequent packets ("lag" in packets on log-scaled x-axis) (left of Fig 6) - for next 30 packets after a loss, loss in mobile case much more likely than in static case (left of Fig 6) - same fate (both lost, both successful) of pkt pairs greatest under 10 ms interval when walking (middle of Fig 6) - depending on walking speed, greatest fate sharing within 10-20 ms (right of Fig 6) - coherence time ~ 10 ms (consistent with SoftRate paper's statement for walking) intuition: - when static, average measurements of channel over longer period; don't change bit-rate too eagerly, as successive losses not strongly correlated - when mobile, don't average for too long, change bit-rate eagerly, and try multiple other rates often to search for best one atop changing channel conditions (this is RapidSample) - so decide if moving or not, then adopt either of two above bit-rate adaptation strategies, accordingly - question: evidence that wireless measurements (without sensors), e.g., RSSI over time, don't allow determination of static vs. mobile cases? RapidSample algorithm: - start at highest bit-rate - upon not receiving link-layer ACK, drop rate one step; record tx failure time - after successfully getting ACKs for transmissions for 5 ms, try a higher bit-rate: highest rate not to have had tx failure in past 10 ms and no lower bit-rate failed in past 10 ms - if exploration of higher bit-rate fails, resume at prior rate; if succeeds, adopts higher rate notes: - drops bit-rate aggressively (one loss!) - increases rate aggressively (5 ms of success!) - waits coherence time (10 ms) before trying rate at which loss seen - doesn't necessarily step one rate at a time; may jump (safe because returns to prior rate if new rate fails) - question: shouldn't parameters (delay before trying rate at which loss seen) depend on coherence time, e.g., differ for walking and driving cases? hint-aware bit-rate adaptation: - use binary mobility hint - if moving, use RapidSample (fast-adapting) - if not, use SampleRate (slow-averaging) bit-rate adaptation evaluation: experimental design: - need reproducibility with different rate adaptation protocols - but need realistic propagation (simulation inadequate) - solution: trace-driven simulation - send packets using 802.11; trace which transmissions succeed and fail - feed traces into ns-3 simulator - take trace: - laptop sends back-to-back 1000-byte packets - cycles through all 8 802.11a bit-rates in 5 ms - other laptop logs received packets - 4 mobility scenarios: - office: no line-of-sight - long hallway, line-of-sight - outdoors: "lightly crowded" pavement - vehicular: sender stationary on roadside; receiver in moving car - comparisons: RapidSample, SampleRate, RRAA (other packet-based rate adaptation algorithm), RBAR and CHARM (RSSI-based rate adaptation algorithms; require environment-specific training) - TCP workloads except for vehicular case (UDP; worrying?) all results in Figures 8 - 12 are relative numbers; impossible to determine absolute throughput! - not very transparent for reader: for example, 40% improvement over 500 bps not so important - leaves one wondering if there's something to hide Figure 8 (only one that evaluates switching between RapidSample and SampleRate using mobility hint triggers--all others just compare RapidSample to SR!) Figure 9: mix of mobile scenarios: RapidSample beats other protocols Figure 10: mix of static scenarios: RapidSample beaten by others (SampleRate fairly good) Figure 11: vehicular scenario: RapidSample beats others Figure 12: walking traces from SoftRate paper RapidSample almost as good as SoftRate question: will RapidSample ever do *better* than SoftRate? question: which is more readily deployable? question: can hints improve SoftRate? (paper claims knowing not moving might let SoftRate avoid cutting rate when fading occurs) why is "modal" protocol (either "static case" or "mobile case") the right design? alternatives: - continuously vary RapidSample's behavior on basis of speed? - continuously vary SampleRate's behavior on basis of speed? Figure 13: real implementation, static laptop to mobile smartphone - office and long hallway settings - uses mobility hint to switch between SampleRate and RapidSample - absolute throughput, finally! - left: overall results; middle: mobile only; right: static only - clear: RS better when moving, SR better when static; hint-driven wins by switching dynamically, overall application 2: AP association status quo: RSSI-based association; associate with AP whose traffic received with greatest RSSI; when RSSI falls below threshold, scan all channels and associate with AP with greatest RSSI using hints: - use GPS signal to determine whether indoors or outdoors (power?) - if indoors, detect whether "walking" or not (evaluated) - if outdoors, use position and speed to decide if moving (not evaluated) - two strategies: maximize throughput or minimize number of handoffs maximizing throughput protocol: - if detect walking, scan periodically (every T_{sc} seconds) for AP with greatest RSSI - when stop walking, immediately scan and pick AP with greatest RSSI - if static, don't scan unless RSSI falls below threshold evaluation: - 30 walking traces in MIT hallways - moving -> still randomly, roughly equal time in each result: - Figure 14: median throughput improvement ca. 30% minimizing handoffs protocol: - goal: avoid interruptions in connectivity (e.g., for VoIP calls) - training required! - central idea: measure whether heading toward AP; overrides RSSI. - training: each second, log heading hint, signal strength from every AP - for one walk, series of measurements a *track* - model: look ahead in track for which AP, if associated with, will maximize time before change of association required - when client stationary: use standard AP association - when client walking: get heading hint, query model using heading hint and current AP - model: search for tracks with similar heading hint, where current AP's RSSI first drops below handoff threshold (i.e., "might we be heading away from AP?"); return AP that maximizes connection duration for that track (found during training) - associate with AP returned most often (i.e., by most tracks) result: - Figure 15: > 90% of trials incur fewer handoffs using this protocol than the standard scheme incurs - question: what goes wrong the other just under 10% of the time? what about hint-aware disassociation: - when should a client disassociate? - who cares? turns out AP may waste time retransmitting to client that has moved out of range (wasting capacity that could be spent on other clients) - possibility: client informs AP of movement and heading; AP cuts sending rate to client that is leaving, only occasionally probing to see if client still in range - mentioned as future work application 3: neighbor discovery and link loss measurements basic idea: a moving node should probe links to neighbors more often than a static node, and links to moving neighbors more often than those to static neighbors measurements show that must probe more often to measure delivery probability accurately in mobile case than in static case implemented hint-driven probing: when stationary, probe once per second, when mobile, probe 10 times per second; results indicate that adaptive probing tracks loss rate more closely (in time) than fixed probing rate. - note: not end-to-end evaluation; really want to know how more accurate probing would improve *throughput*, e.g., in a network using the ETT metric; ETX argument no substitute for end-to-end measurements application 4: route selection in vehicular networks three metrics based on heading and speed hints that estimate expected lifetime of a route evaluation: using car position traces from vehicular sensing project (CarTel), simulate network topology, assuming links exist when cars within 100 meters of one another. Figure 18: top "buckets" of all three metrics seem to contain long-lived routes note: no end-to-end evaluation of effect on *throughput*; how much would these metrics improve it?