Transcript Skr4800_CHP7

Ad Hoc and
Sensor Networks
Azizol Bin Abdullah
[email protected] (A2.04)
Rujukan: Text Book Chapter 13
RECAP: What is Ad Hoc Network?
adhoc or ad-hoc or ad hoc network:
Local network with wireless or temporary plug-in connection, with
mobile devices are part of the network only while they are within
close proximity. Mobile ad hoc network = MANET
Example:
military; soldiers sharing info on their notebooks in close proximity
technique is used to increase the effectiveness
-Network topology frequently change(dynamic). No fixed infra
and information is passed in peer-to-peer in multihop routing.
Info is transmitted in a store-and-forward method from source
to destination, via intermediate nodes (no routers!!!)
RECAP: What is Sensor Network?
“Sensor” network:
A lot of tiny mobile sensors are planted on ad hoc basis(e.g drop from
low flying airplanes) to sense and transmit some physical
characteristics of the environment.
- The associated BS(the airplane) collects the info gathered by the
sensors.
Examples:
Battlefield surveillance of enemy territory, environmental monitoring
etc
How Ad Hoc Being Used?
The term has been applied to future office or home networks in which
new devices can be quickly added, using, for example, the proposed
Bluetooth technology in which devices communicate with the computer
and perhaps other devices using wireless transmission.
One vendor offers an ad-hoc network technology that allows people to
come to a conference room and, using infrared transmission or radio
frequency (RF) wireless signals, join their notebook computers with
other conferees to a local network with shared data and printing
resources.
Taken from: http://searchmobilecomputing.techtarget.com/
Characteristics of Ad Hoc Networks
1) Dynamic topologies: network topology may change regularly and
at unpredictable times
2) Bandwidth-constrained: wireless links have lower capacity than
infrastructured network
3) Energy-constrained operation: Majority of the nodes in an ad hoc
network may rely on batteries or such exhaustive means for their
energy
4) Limited physical security: mobile wireless networks are prone to
physical security threats than wireline networks.
Some Ad Hoc Applications
- Besides military-based applications, some useful apps include:
*Education via the Internet: remote area where wireline access is not
available
*Crisis-management apps: quick restoration is needed as a result of
distasters in which entire communication infrastructure in a mess
*Telemedicine: accessing medical reports and/or video conferencing
from remote areas(accident site)
*Tele-geoprocessing apps: combination of geographical information
system, GPS and wireless mobile systems – location information.
*Virtual navigation: database of city map/street/traffic is constantly
transmitted to a vehicle
Routing Criteria
-Due to MANET’s low resource availability, optimal routing is indeed
required to efficiently use the limited resources.
-The dynamic of MANET also makes the design for its routing protocol
much harder, thus when selecting a routing protocol, the following
3 major criterias must be followed:
i) high reliability: alternative routes are needed wherever there is a
failure on particular node connectivity
ii) least cost path: minimizing the number of intermediate nodes need
to be visited from source to destination
iii) best possible response time and throughput: crucial for interactive
sessions between user applications.
NOTE:Each node is to serve as a routerexecutes routing algo and
calculates best path. As network grows larger, overhead in computing,
storing and communicating routing table info increases. Thus
hierarchical structure is to be adopted(not flat architecture).
RECAP:Routing Protocols
- 2 types: Interior & Exterior Routing Protocols
- Interior protocols are RIP and OSPF(interior to one domain known
as Autonomous System(AS)). Exterior is BGP between ASes.
RIP(Routing Information Protocol):
Uses distance vector routing; each router periodically shares its knowledge with its
neighbor over the entire Internet. Means update for topology changes come in periodic table
updates(usually 30-60 seconds), usually generates more network traffic and results in slower
convergence. RIP is an efficient routing protocol for most of the small to medium size
networks.
OSPF(Open Shortest Path First):
Uses link-state routing updates are usually triggered by topology changes. Relatively small Link
State packets are passed to all other routers, usually result in faster time to converge on any
internetwork topology change. OSPF is extremely dynamic for routing between large
internetworks.
BGP(Border Gateway Protocol):
InterASes communicate with each other to exchange reachability information. Based on path
vector routing.
How Routing in Ad Hoc Should Be?
-Existing routing protocols are not suitable for Ad Hoc environment
-Proactive routing* continuously use large portion of
resources to keep routing info up to date
-Reactive routing* (ad hoc on-demand distance vector) could cause
delay[route info may not available when datagram is received]
Thus, routing protocols for Ad Hoc are introduced and classified as:
• Table-driven protocols
• Source initiated(on-demand) protocols
*all routing protocols can be classified either in proactive or reactive
i)Table-Driven Routing Protocol
-uses proactive schemes
-each node maintains consistent, up-to-date routing info
-respond to changes by each node propagates updates throughout
network
Some of the table-driven ad hoc routing protocols are:
• Destination-Sequenced Distance Vector Routing
• Cluster-Head Gateway Switch Routing
• Wireless Routing Protocol
ii)Source-Initiated On-Demand
Routing
-uses reactive schemes
-creates routes only when desired by source node
-when a node requires a route to a destination, it initiates a route
discovery process within the network
-once all possible paths being examined, and the best path has been
chosen, the process is completed
Some of the Source-Initiated On-Demand ad hoc routing protocols are:
• Ad Hoc On-Demand Distance Vector Routing
• Dynamic Source Routing
• Temporarily Ordered Routing Algorithm
• Associativity-Based Routing
• Signal Stability-based Routing
iii)Hybrid Routing Protocol
-creates environment whereby the protocol initiates the routedetermination procedure on demand, but at limited search cost
Some of the Hybrid routing protocols are:
• Zero Routing
• Fisheye State Routing
• Landmark Routing(LANMAR) Protocol
• Location-Aided Routing
• Distance Routing Effect Algorithm for Mobility(DREAM)
• Relative Distance Microdiscovery Ad Hoc Routing
• Power Aware Routing
MANET Projects
Simulation-based:
– Network simulators: Omnet++, NS-2
– Robot simulators: MissionLab, Player/Stage
– Traffic simulators: SUMO
– Combination of the above
– Create your own simulator
Implementation-based:
– Construct MANET test bed using Gumstix with Wi-Fistix (and optionally GPS-stix, robo-stix), moving toys,
laptops, you, bikes, etc.
MANET Application I:
Vehicular Ad-hoc NETwork (VANET)
Integrated traffic simulator with
network simulator
Vehicle mobility-based routing
strategy
Make use of public transport (e.g.
trams, trains, buses) or traffic
facilities (traffic light, lamp post)
as data carrier or relay in MANET
E.g. A biker-NET in the Blackforest
MANET Application II:
Robot (-assisted) Ad hoc Network
Mobile robots moving around wireless
sensor network
Mobile robots serve as relay in
MANET
– to collect/send data from/to sensors
– How to guarantee connectivity?
– to aid in localization
– How to conserve energy?
MANET Application III: Others
Search & Rescue /
Emergency Services
MANET Project Ideas (I)
Followings are some project ideas based on the example MANET
applications above:
Realistic mobility analysis
– Collect traces of human-beings’ movement. Analyze the data and propose
a mobility prediction algorithm to improve current MANET protocols.
Modeling radio propagation
– For indoor or outdoor environment. Examine its impact to data
communications in MANET.
Energy consumption analysis
– Analyze power usage of different components of computing devices, e.g.
radio, CPU, sensors, of Gumstix/laptops/sensors. Propose and evaluate
the techniques to reduce the cost.
MANET Project Ideas (II)
Route selection algorithm
– Develop a route selection algorithm for MANET protocols to determine the
best strategy for different network conditions. Evaluate the performance of
the proposed algorithm.
QoS in MANET routing protocol
– Improve any MANET routing protocol to maintain route and guarantee data
delivery.
Real-time multimedia streaming in MANET
– Identify limitation of wireless link and problem in MANET for multimedia
streaming. Enhance routing protocol to be robust to network dynamics.
Application development
– Develop an application for Gumstix, considering the hardware constraints.
E.g. Gumstix phone.
Wireless Sensor Networks
-a wireless sensor network is a collection of tiny disposable and lowpower devices
-a sensor node is a device that converts a sensed attribute(eg vibration,
temp) into a form understandable by users
-the device requires sensing module, communication module, memory
and a small battery
-wired sensors have long been used, however are large and expensive
(such as airplane).
-Nowadays wireless sensors are used due to:
*ease of deployment:can be deployed easily without much preparation
*extended range:many sensors can be dropped at wider area(same cost)
*fault tolerant:unattended, failure on one node does not affect entire
*mobility:equipped with battery, thus can rearrange them
Wireless Sensor Networks
-There is a great potential for networked micro sensors esp. in military
-DARPA(Defense Advanced Research Project Agency) sponsoring
most of the research done on this tech
-One of the famous one is the SenIT(Sensor IT), a program that
developes software for distributed micro sensors
-Such research is needed as future battlefield should be intelligent, and
inexpensive
Classification of Sensor Networks
i) Proactive
Nodes in this network periodically switch on their sensors and
transmitters; sense the environment and send the relevant data (since
data is sent regularly it is good for data monitoring apps)
ii) Reactive
Nodes react immediately to sudden changes in the value of sensed
attributes (good for time-critical apps since updates is not done based
on periodic time)
-Once the network type is identified, the data is to be routed using
MAC layer( data link layer)
-In proactive network, 2 important chars are RT(Report Time) & Attribute
MAC Protocol in Wireless SN
- wireless, means broadcast (all nodes within radio range can hear its
transmission)
-to have unicast, “address” such as destination is used and all other
nodes will drop the packet they receive
-2 types to allocate a single broadcast channel among competing nodes;
static vs dynamic
Static Channel Allocation
N nodes, the bandwidth is divided to N equal portion. No interference between multiple users.
Works well for a small network with fixed number of users.
Dynamic Channel Allocation
No fixed assignments. Good when number of users changes dynamically and contains bursty
data. Contention-based scheme, at the same time try to minimize collision. If collided,
retransmit data and this will choke the bandwidth + causes delay.
Hierarchical vs Flat
Hierarchical
Reservation-based
Flat
Contention-based
Data aggregation by cluster head Node on multihop path
aggregates incoming data from
neighbors
Simple but not optimal
Complex and optimal
Fair Channel Allocation
Fairness not guarantted
Collision avoided
Collision overhead present
Require global and local sync
No sync and links formed on the
fly
Wireless Sensor Networks
-a wireless sensor network is a collection of tiny disposable and lowpower devices
-a sensor node is a device that converts a sensed attribute(eg vibration,
temp) into a form understandable by users
-the device requires sensing module, communication module, memory
and a small battery
-wired sensors have long been used, however are large and expensive
(such as airplane).
-Nowadays wireless sensors are used due to:
*ease of deployment:can be deployed easily without much preparation
*extended range:many sensors can be dropped at wider area(same cost)
*fault tolerant:unattended, failure on one node does not affect entire
*mobility:equipped with battery, thus can rearrange them
Case Study: Wireless Sensors Network
Implementation
http://webs.cs.berkeley.edu/800demo/