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

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/

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

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

Manet: Mobile Ad-hoc Networking

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.

Use of the Ad-Hoc Technology for Military Communications

Ubiquitous Networking

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

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

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

Density = Broadband

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

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

Community Mesh Network
The natural evolution of broadband connectivity

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

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 …

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

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?

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 !

“Mobile Ad Hoc Networking is a multi-layer problem !”

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.

Network Layer in MANET

	Has been the focus of past research
	Particularly: Routing

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.

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.

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.

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

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

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.

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

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

Route Requests in AODV

Route Requests in AODV

Route Requests in AODV

Reverse Path Setup in AODV

Reverse Path Setup in AODV

Reverse Path Setup in AODV

Route Reply in AODV

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

Forward Path Setup in AODV

Data Delivery in AODV

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)

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

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

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

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 )

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

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

OLSR Protocol (2)

	MPR nodes are chosen in such a way that every 2-Hop neighbor can be reached by the MPRs

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)

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

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.

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.

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

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

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

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

Simulation Results: Summary I

Simulation Results: Summary II

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.

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

Wireless Sensor Networks
(aka Embedded Networked Sensors)

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

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, ….

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

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.

Field Experiment

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.

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).

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.

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, ...

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).

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).

Transportation and Urban Monitoring

Slide 75

Enabling Technologies

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

Some Networked Sensor Node Developments

Sensor Node Energy Roadmap

Comparison of Energy Sources

Communication/Computation Technology Projection

"“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.

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

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...

Sample Layered Architecture