1	Course Overview Introduction Data in Wireless Cellular Systems Data in Wireless Local Area Networks Internet Protocols TCP over Wireless Link Ad-Hoc Networks, Sensor Networks Services and Service Discovery System Support for Mobile Applications
2	Some References: Some slides are from the Tutorial on Mobile Ad Hoc Networks: Routing, MAC and Transport Issues, prepared by Nitin Vaidya, see http://www.crhc.uiuc.edu/wireless/tutorials.html Some slides are from the Tutorial on Wireless Sensor Networks by Deborah Estrin, Akbar Sayeed, and Mani Srivastava, see http://nesl.ee.ucla.edu/tutorials/mobicom02/
3	One Type of Wireless Networks: “Infrastructure-based” Infrastructured wireless networks Cellular Networks and Wireless LAN Fixed, wired backbone and centralized control Mobiles communicate directly with access points (AP) Suitable for locations where APs can be deployed
4	Another Type of Wireless Networks: “Infrastructure-less” (Mobile) Ad-Hoc Networks Neither pre-existing, wired backbone nor centralized administration Peer-to-Peer and self-organizing networks Each mobile serves as routers, not just an end point. Mesh: has wireless infrastructure (multihop wireless) Maintains separation between (mobile) routers and end hosts Wireless Sensor Networks: mostly static topology, no separation between routes and sensors, multihop wireless
5	Manet: Mobile Ad-hoc Networking
6	Ad hoc Networks In Latin, “ad hoc” literally means "for this purpose only” It can be regarded as a “spontaneous network” A Mobile Ad-hoc NETwork (MANET) is a collection of mobile nodes which communicate over radio and do not need any pre installed communication infrastructure. Mobile, multihop wireless network capable of autonomous operation Communication can be performed if two nodes are close enough to exchange packets.
7	Use of the Ad-Hoc Technology for Military Communications
8	Ubiquitous Networking
9	Applications of Ad-Hoc Networks Application of the ad-hoc network technology is appropriate when a network needs to be rapidly deployed without prior planning and to provide reliable communication in harsh propagation conditions. Examples: Military: for tactical communications National security: in times of natural disaster or global war Rescue missions: in lieu of adequate wireless coverage Law enforcement: similar to tactical communications Commercial use: for setting up sales presentations Education: wall-free (virtual) classrooms Local Area Networks (LANs): for limited-coverage communication Sensor Networks (more later) Embedded computing and networking applications (ubiquitous computers with short-range interactions, vehicle networks) Cellular range extension (interoperability with infrastructured networks) Community Mesh Networks
10	Wireless Mesh Community Networks: Bridging the Broadband Divide Next few Slides from Presentation at http://www.research.microsoft.com/mesh/, Keynote Presentation by V. Bahl
11	Why Broadband? The future is about rich multimedia services and information exchange …possible only with wide-scale availability of broadband Internet access but… Many people are still without broadband service Up to 30% of America (32 million homes) cannot get broadband service (rural areas, older neighbourhoods, poor neighbourhoods) A large majority of the developing world does not have broadband connectivity It is not economically feasible to provide wired connectivity to these customers
12	Density = Broadband
13	Broadband is Not Yet a Reality “For Internet access, there are 15 ISPs for every 100K users, for Cable or DSL there are two providers for every 100K users” - Consumer Federation of America, July 2002 “One reason often cited for low penetration of broadband services is their high cost, typically $50 a month” - The Mercury News “[Broadband users] are much more likely to create content for the Web or share files, telecommute, download music, or game files, or enjoy streaming audio or video” - Cox News Service “Applications will drive broadband access and justify the investment for citizens, businesses and government” - Office of Technology Policy, US Dept. of Commerce, Sept., 2002
14	Broadband Access: Wiring the Last Mile? The Last Mile: Connection between a home and local hub Scale & legacy make last mile expensive ~ 135 million housing units in the US (U.S. Census Bureau 2001) POTS (legacy) network designed for voice & built over 60 years Cable TV networks built over last 25 years The Truck Roll Problem: Touching each home incurs cost: customer equipment; installation & servicing; and central office equipment improvements In our (i.e., Microsoft Research’s) estimate building an alternate, physical last mile replacement to hit 80% of US homes will take 19 years and cost ~ US $60-150 billion
15	Community Mesh Network The natural evolution of broadband connectivity
16	Why MOBILE Ad-Hoc Networks? Mesh, at first sight, as a rather static, albeit multihop wireless network Mobility of hosts/routers => Dynamic Topology Dynamic Topology however does not imply Mobile Network: Nodes come and go Uncontrolled Interference Testbeds show that IEEE 802.11 links are highly asymmetric due to different interference environment at receiver and variable over time Personal Opinion: Mesh Community Networks will have many of the same challenges and will benefit from same solutions as MANETs Deal with dynamic topology Little to no configuration/peer-to-peer operation
17	Challenges in Ad-Hoc Networks The challenges in the design of Ad-Hoc networks stem from the following facts: the lack of centralized entity Þ self-organizing and distributed protocols the possibility of rapid platforms movement (highly versatile topology) Þ efficient and robust protocols all communication is carried over the wireless medium Þ power and spectrum efficient communications Compare this with the fixed (cellular) networks …
18	Ad-Hoc Networks vs. Cellular Networks The distinctive differences between ad-hoc networks and cellular networks are: no fixed infrastructure is present multi-hop routing (network diameter >> node transmission range) peer-to-peer operation frequent changes of associations
19	Other Challenges of Ad-Hoc Networks Application/Market penetration is multihop technology commercializable? Design/Implementation reliable, manageable, survivable, and secure Operational/Business-related how to manage the network? how to bill for services?
20	Characteristics of Ad Hoc Networks Advantages Easy and rapid deployment Reduced administrative cost Disadvantages and Challenges Limited resources (power, transmission range,…) Unstable wireless transmissions (higher error rates and quality variability) Asymmetric wireless links Dynamic topology change Security hazard (easy of snooping on wireless transmissions) A mobile ad hoc network is a promising and neat technology platform, but there are still many technical and business challenges to solve !
21	“Mobile Ad Hoc Networking is a multi-layer problem !”
22	Medium Access Control in MANET Some interesting issues, but skipped here Most testbeds use IEEE 802.11x, which works in multihop environment, though it was not designed for that scenario.
23	Network Layer in MANET Has been the focus of past research Particularly: Routing
24	Main Issue – “Routing” If there is NO direct link between a source and a destination, multi-hop routing is needed to discover their routes. Routing is a very challenging task in mobile ad hoc networks. Mobility and link failure/repair may cause frequent route changes. Routing protocol must be distributed, with a minimal overhead.
25	Ad hoc Routing Protocols Routing problem has received a significant interest in the research community, resulting in several protocols proposed. Some have been invented specifically for MANET. Others are adapted from traditional routing protocols for wired networks (i.e., distance vector or link state algorithms) These traditional protocols do not work efficiently or fail completely. The main group of proposals comes from the work of IETF’s MANET working group Designed for IP based, homogeneous, mobile ad hoc networks. Focuses on fast route establishment and maintenance with minimal overhead Number of hops is used as the only route selection criteria. Other parameters, such as energy usage or QoS, are not considered.
26	Ad-Hoc Networking: MANET Mobile Ad-hoc Networks (manet) at IETF: http://www.ietf.org/html.charters/manet-charter.html A "mobile ad hoc network" (MANET) is an autonomous system of mobile routers (and associated hosts) connected by wireless links routers are free to move randomly and organize themselves arbitrarily; thus, the network's wireless topology may change rapidly and unpredictably The primary focus of the working group is to develop and evolve MANET routing specification(s) and introduce them to the Internet Standards track. The goal is to support networks scaling up to hundreds of routers.
27	MANET Routing Protocols Protocols: On-demand protocols AODV (RFC 3561, July 2003) DSR (Draft 10, July 2004, currently under review by IESG) Pro-active protocols OLSR (RFC 3626, Oct. 2003) TBRPF: Topology Dissemination Based on Reverse-Path Forwarding (RFC 3684, February 2004) Mixed modes: Fisheye state routing Zone routing
28	Routing Protocols - Design Proactive, Table-driven Approach Based on traditional link-state and distance-vector routing protocols. Continuously update the topological view of the network by periodically exchanging appropriate information among the nodes. Determine routes independent of traffic pattern Examples: DSDV, OLSR (Optimized Link State), TBRPF etc. Reactive, On-demand Approach Discover and maintain routes only if needed Do not continuously maintain the overall network topology The network is flooded with “route request” control packets when a new route is required. Examples: DSR, AODV, LAR, etc. Hybrid Approach Combine the two approaches above: locally proactive, globally reactive ! Example: ZRP
29	Trade-Off Various simulation studies have shown that reactive protocols perform better in mobile ad hoc networks than proactive ones. However, no single protocol works well in all environments. Which approach achieves a better trade-off depends on the traffic and mobility patterns.
30	Leading MANET Contenders DSR: Dynamic Source Routing Source routing protocol Complete path in packet header AODV: Ad-hoc On-demand Distance Vector Routing “Hop-by-hop” protocol Uses only standard IP packets, intermediate nodes maintain routing table Both are “on demand” protocols: route information discovered only as needed Two phases: route discovery and route maintenance Difference: in DSR, source controls complete route, in AODV it only know the next hop Military: OLSR (Optimized Link State Routing) Proactive routing protocol Similar to OSPF, but more efficient link state updates
31	AODV Route Requests (RREQ) are forwarded via flooding When a node re-broadcasts a Route Request, it sets up a reverse path pointing towards the source AODV assumes symmetric (bi-directional) links When the intended destination receives a Route Request, it replies by sending a Route Reply Route Reply travels along the reverse path set-up when Route Request is forwarded
32	Route Requests in AODV
33	Route Requests in AODV
34	Route Requests in AODV
35	Reverse Path Setup in AODV
36	Reverse Path Setup in AODV
37	Reverse Path Setup in AODV
38	Route Reply in AODV
39	Route Reply in AODV An intermediate node (not the destination) may also send a Route Reply (RREP) provided that it knows a more recent path than the one previously known to sender S To determine whether the path known to an intermediate node is more recent, destination sequence numbers are used The likelihood that an intermediate node will send a Route Reply when using AODV not very high A new Route Request by node S for a destination is assigned a higher destination sequence number. An intermediate node which knows a route, but with a smaller sequence number, cannot send Route Reply
40	Forward Path Setup in AODV
41	Data Delivery in AODV
42	Timeouts A routing table entry maintaining a reverse path is purged after a timeout interval timeout should be long enough to allow RREP to come back A routing table entry maintaining a forward path is purged if not used for a active_route_timeout interval if no is data being sent using a particular routing table entry, that entry will be deleted from the routing table (even if the route may actually still be valid)
43	Link Failure Reporting A neighbor of node X is considered active for a routing table entry if the neighbor sent a packet within active_route_timeout interval which was forwarded using that entry When the next hop link in a routing table entry breaks, all active neighbors are informed Link failures are propagated by means of Route Error messages, which also update destination sequence numbers
44	Route Error When node X is unable to forward packet P (from node S to node D) on link (X,Y), it generates a RERR message Node X increments the destination sequence number for D cached at node X The incremented sequence number N is included in the RERR When node S receives the RERR, it initiates a new route discovery for D using destination sequence number at least as large as N When node D receives the route request with destination sequence number N, node D will set its sequence number to N, unless it is already larger than N
45	Link Failure Detection Hello messages: Neighboring nodes periodically exchange hello message Absence of hello message is used as an indication of link failure Alternatively, failure to receive several MAC-level acknowledgement may be used as an indication of link failure
46	Why Sequence Numbers in AODV To avoid using old/broken routes To determine which route is newer To prevent formation of loops Assume that A does not know about failure of link C-D because RERR sent by C is lost Now C performs a route discovery for D. Node A receives the RREQ (say, via path C-E-A) Node A will reply since A knows a route to D via node B Results in a loop (for instance, C-E-A-B-C )
47	Summary: AODV Routes not included in packet headers Nodes maintain routing tables containing entries only for routes that are in active use At most one next-hop per destination maintained at each node Other protocols may maintain several routes for a single destination Unused routes expire even if topology does not change
48	Proactive Routing: OLSR Protocol OLSR (Optimized Link State Routing Protocol) Optimizes the link state flooding mechanism Multipoint Relay (MPR) nodes achieve the optimization A set of MPR nodes is chosen by each node in the network The node’s view of the topology becomes partial
49	OLSR Protocol (2) MPR nodes are chosen in such a way that every 2-Hop neighbor can be reached by the MPRs
50	MPR Computation MPRs optimize the classical flooding mechanism Each node selects its own MPRs from its 1-hop symmetric neighbours Through the MPRs all symmetric strict 2-hop neighbours must be reached Recalculated when symmetric neighbourhoods change (1-hop or strict 2-hop)
51	MPR Computation (2) MPRs are signalled as MPR neighbour type, inside Hello messages MPR Selector (MPRS) set is populated when any node is signalled as a MPR neighbour MPRs are computed per interface. MPR candidate nodes must have willingness different from Will_Never
52	MPR Computation (3) MPR set = Ø MPR += 1-hop neighbors with willingness=Will_always MPR += 1-hop neighbors that are the only ones reaching a 2-hops neighbor Remove the 2-hop neighbors reached by the MPRs Add 1-hop nodes (to the MPR set) providing maximum reachability of 2-hop neighbors UNTIL reaching all 2-hop neighbors.
53	Routing Table Each node maintains its own routing table Based on the Link and Topology sets. Recalculated (without transmitting any message) when a change is detected in either: Link set Neighbor set 2-hop neighbor set Topology set Multiple interface association set.
54	Multicast: Motivation Many applications for ad hoc networks require one-to-many and many-to-many communication Multicast protocols are intended to efficiently support such communication patterns Multicasting well researched in fixed networks (i.e., the Internet), building efficient distribution structures (typically a multicast tree) Ad hoc networks: dynamic topology makes it harder to maintain distribution structure with low overhead
55	Motivation (cont.) MANET specific protocols are being proposed MAODV: multicast extensions for AODV, establishes shared tree ODMRP: new multicast protocol, based on per-source mesh ADMR: completely on-demand, per-source tree Own study done at CRC last year: Study multicasting protocols Develop a protocol that achieves high packet delivery ratio with low overhead
56	Multicast Protocol Performance Multicast protocols perform poorly (packet delivery ratio below 90%) as network topology changes more often (nodes move with higher speed and/or pause less) Multicast protocols also often do not scale well with number of multicast senders and/or number of multicast receivers Open question how to build efficient multicast routing protocols in a MANET (tree vs. mesh, single tree vs. source-based tree, etc.) Quite a bit of work on efficient broadcast protocols, rather than simplistic flooding approach, as broadcasting control messages inherent part of many routing protocols
57	Are Multicast Protocols Right Choice? Broadcast protocols only explored for broadcast purposes, but can also be employed for multicasting Another alternative is to use unicasting, creating appropriate number of 1-to-1 communication pairs Own study: Compare unicast, multicast, and broadcast protocols under same scenarios Evaluate under one-to-many and many-to-many communication patterns
58	Simulation Results: Summary I
59	Simulation Results: Summary II
60	Broadcast Protocols Competitive Broadcast protocols work well. BCAST and FLOOD are almost always as good as or better than other protocols, though sometimes impose higher packet latency. Protocol overhead lower/competitive with best multicast protocol For a single multicast sender, FLOOD is the obvious choice, for increasing number of multicast senders BCAST has the edge over FLOOD ADMR performs very well in the presence of many multicast senders, (is optimal choice in two scenarios under low mobility), with BCAST being runner-up. All other protocols perform poorly in these scenarios. The choice of an optimal multicasting solution is largely independent of the mobility rate.
61	Many Challenges Yet to be Addressed Issues other than routing have received much less attention Comment from one conference: “there is, yet again, another routing paper, oh no…..” J However: there are still interesting problems as well (some of my PhD students work on specific issues too) Other interesting problems: Applications for MANET Address assignment, node configuration à network management Support for real-time multimedia traffic (QoS) Security and access control Service discovery Improving interaction between protocol layers (cross-layer design) Integration with other wireless/wired technologies
62	Wireless Sensor Networks (aka Embedded Networked Sensors)
63	Embedded Networked Sensing Potential Micro-sensors, on-board processing, and wireless interfaces all feasible at very small scale can monitor phenomena “up close” Will enable spatially and temporally dense environmental monitoring Embedded Networked Sensing will reveal previously unobservable phenomena
64	Sensor Applications IEEE Computer, August 2004: special issue on sensor networks Classification of Applications Monitoring Space Habitat monitoring, precision agriculture, surveillance, treaty verification, indoor climate control, …. Monitoring Things Structural monitoring, ecophysiology, medical diagnostics, urbain terrain mapping, …. Monitoring interaction of Things with each other and surrounding Space Wildlife habitat, disaster management, pervasive computing, asset tracking, manufacturing process flow, ….
65	Sensor Applications (IEEE Computer) GlacsWeb project, University of Southampton Monitor subglacial bed deformation Particular challenge: collect data from sensors in remote locations Radiation Detection, Los Alamos National Labs and University of New Mexico Distributed sensor network to detect vehicles that could potentially transport radioactive isotopes (I.e., dirty bomb) PinPtr, Vanderbilt University Detecting and locating a sniper in a challenging environment such as a complex urban terrain
66	App#1: Seismic Interaction between ground motions and structure/foundation response not well understood. Current seismic networks not spatially dense enough to monitor structure deformation in response to ground motion, to sample wavefield without spatial aliasing. Science Understand response of buildings and underlying soil to ground shaking Develop models to predict structure response for earthquake scenarios. Technology/Applications Identification of seismic events that cause significant structure shaking. Local, at-node processing of waveforms. Dense structure monitoring systems. ENS will provide field data at sufficient densities to develop predictive models of structure, foundation, soil response.
67	Field Experiment
68	Research Challenges Real-time analysis for rapid response. Massive amount of data ® Smart, efficient, innovative data management and analysis tools. Poor signal-to-noise ratio due to traffic, construction, explosions, …. Insufficient data for large earthquakes ® Structure response must be extrapolated from small and moderate-size earthquakes, and force-vibration testing. First steps Monitor building motion Develop algorithm for network to recognize significant seismic events using real-time monitoring. Develop theoretical model of building motion and soil structure by numerical simulation and inversion. Apply dense sensing of building and infrastructure (plumbing, ducts) with experimental nodes.
69	App#2: Contaminant Transport Science Understand intermedia contaminant transport and fate in real systems. Identify risky situations before they become exposures. Subterranean deployment. Multiple modalities (e.g., pH, redox conditions, etc.) Micro sizes for some applications (e.g., pesticide transport in plant roots). Tracking contaminant “fronts”. At-node interpretation of potential for risk (in field deployment).
70	ENS Research Implications Environmental Micro-Sensors Sensors capable of recognizing phases in air/water/soil mixtures. Sensors that withstand physically and chemically harsh conditions. Microsensors. Signal Processing Nodes capable of real-time analysis of signals. Collaborative signal processing to expend energy only where there is risk.
71	App#3: Ecosystem Monitoring Science Understand response of wild populations (plants and animals) to habitats over time. Develop in situ observation of species and ecosystem dynamics. Techniques Data acquisition of physical and chemical properties, at various spatial and temporal scales, appropriate to the ecosystem, species and habitat. Automatic identification of organisms (current techniques involve close-range human observation). Measurements over long period of time, taken in-situ. Harsh environments with extremes in temperature, moisture, obstructions, ...
72	Field Experiments Monitoring ecosystem processes Imaging, ecophysiology, and environmental sensors Study vegetation response to climatic trends and diseases. Species Monitoring Visual identification, tracking, and population measurement of birds and other vertebrates Acoustical sensing for identification, spatial position, population estimation. Education outreach Bird studies by High School Science classes (New Roads and Buckley Schools).
73	ENS Requirements for Habitat/Ecophysiology Applications Diverse sensor sizes (1-10 cm), spatial sampling intervals (1 cm - 100 m), and temporal sampling intervals (1 ms - days), depending on habitats and organisms. Naive approach ® Too many sensors ®Too many data. In-network, distributed signal processing. Wireless communication due to climate, terrain, thick vegetation. Adaptive Self-Organization to achieve reliable, long-lived, operation in dynamic, resource-limited, harsh environment. Mobility for deploying scarce resources (e.g., high resolution sensors).
74	Transportation and Urban Monitoring
75
76	Enabling Technologies
77	Sensors Passive elements: seismic, acoustic, infrared, strain, salinity, humidity, temperature, etc. Passive Arrays: imagers (visible, IR), biochemical Active sensors: radar, sonar High energy, in contrast to passive elements Technology trend: use of IC technology for increased robustness, lower cost, smaller size COTS adequate in many of these domains; work remains to be done in biochemical
78	Some Networked Sensor Node Developments
79	Sensor Node Energy Roadmap
80	Comparison of Energy Sources
81	Communication/Computation Technology Projection
82	"“The network is the..." “The network is the sensor” (Oakridge National Labs) Requires robust distributed systems of thousands of physically-embedded, unattended, and often untethered, devices.
83	New Design Themes Long-lived systems that can be untethered and unattended Low-duty cycle operation with bounded latency Exploit redundancy and heterogeneous tiered systems Leverage data processing inside the network Thousands or millions of operations per second can be done using energy of sending a bit over 10 or 100 meters Exploit computation near data to reduce communication Self configuring systems that can be deployed ad hoc Un-modeled physical world dynamics makes systems appear ad hoc Measure and adapt to unpredictable environment Exploit spatial diversity and density of sensor/actuator nodes Achieve desired global behavior with adaptive localized algorithms Can’t afford to extract dynamic state information needed for centralized control
84	From Embedded Sensing to Embedded Control Embedded in unattended “control systems” Different from traditional Internet, PDA, Mobility applications More than control of the sensor network itself Critical applications extend beyond sensing to control and actuation Transportation, Precision Agriculture, Medical monitoring and drug delivery, Battlefied applications Concerns extend beyond traditional networked systems Usability, Reliability, Safety Need systems architecture to manage interactions Current system development: one-off, incrementally tuned, stove-piped Serious repercussions for piecemeal uncoordinated design: insufficient longevity, interoperability, safety, robustness, scalability...
85	Sample Layered Architecture