Transcript SurveyRoutingADHOC - start [kondor.etf.rs]

Ad-Hoc Networks
Establishing node-to-node communication
with no infrastructure needed
Authors:
Đorđe Trifunović, [email protected]
Nikola Milanović, [email protected]
Prof. Dr. Veljko Milutinović, [email protected]
What will you learn from this tutorial?
This tutorial will guide you through the following sections:






Introduction
Mobile networks
Routing in ad-hoc networks
Security in ad-hoc networks
Bluetooth
The IEEE/UB ad-hoc multihop sensor network and Bluetooth;
lessons learned from the research by:
–
–
–
–
–
Gvozden Marinković ([email protected])
Aleksandar Radovanović ([email protected])
Aleksandar Berić ([email protected])
Branislav Čukanović ([email protected])
Nikola Milanović ([email protected])
Page Number: 2/130
Introduction to
Ad-Hoc Networks
Evolution of network
communications –
A new stage…
Introduction

Two basic groups of ad-hoc networks:
– Networks of mobile computers handled by users
– Wireless sensor networks

Basic characteristic:
ability to establish network communication between hosts
without any infrastructure needed.
– The most significant advance compared to classic fixed systems
– Reveals a very large scale of new possibilities
Page Number: 4/130
Introduction

Ad-hoc networks may be considered
as a new stage in evolution of network communications
 Fixed computer networks:
– Concepts and mechanisms educed and amended for long time…
– Lot of experiences acquired…
– A useful base for origin and development of mobile networks...
Page Number: 5/130
Introduction

Wireless communication has its peculiarities.
 Taking the already developed solutions is not possible.
– In the beginning:
modifications and adaptations of existing mechanisms.
– Later: more and more of new ideas,
relieved from the ballast of obsolete concepts.
Page Number: 6/130
Mobile Networks
Meet the family…
Mobile Networks

Not long time ago,
mobile networks were treated
just as extensions of fixed networks.
 Actors are:
– Fixed hosts (FH)
– Mobile hosts (MH)
– Base stations (also known as mobility support routers – MSR)
Page Number: 8/130
Mobile Networks
Mobility Support Router (MSR)

Every MSR supports the area limited by its range (wireless cell).
 MSR can communicate with MHs currently located in its cell.
– MHs directly communicate only with MSRs
– MHs can freely move from one cell to another
MH
MSR
MH
MH
Page Number: 9/130
Mobile Networks
Sending packets from FH to MH

MSRs are bridges between the wired network and mobile hosts.
 When some fixed host (FH) wants to send a packet
to a mobile host (MH), communication is divided into two parts:
– Standard communication inside the fixed network,
from FH to the proper MSR;
– Wireless communication between MSR and MH.
MH
FH
FH
MSR
FH
FH
Page Number: 10/130
MH
Mobile Networks
Hiding mobility

Mediation of MSR is entirely transparent to FH.
 For this kind of communication,
indirect protocols were developed,
with the purpose of hiding mobility
from immobile hosts.
MH
FH
FH
MSR
FH
FH
Page Number: 11/130
MH
Mobile Networks
One-hop wireless communication

Direct communication between mobile hosts does not exist
 Mobility is very limited
and dependant on the existing wired infrastructure:
– MHs can move only within areas determined by the range of MSR,
as well as by the range of its own transmitter;
– Mobility is limited to only one hop
between mobile host and fixed network

Anyhow, a step towards real, multihop wireless networks.
– Nature of wireless communications had to be considered
– Later was of great benefit for development of ad-hoc networks
Page Number: 12/130
Mobile Networks
Nature of wireless communications

Wireless vs wired links:
–
–
–
–
–

Slower
Less reliable
Prone to loss of signal due to noise and fading
With much more limited bandwidth
With much more frequent occurrence
of asymmetric quality of communication
Mobile hosts are often disconnected from the fixed network
for short or long periods of time:
– Moving out of range
– Exhausted battery
– …
Page Number: 13/130
Mobile Networks
Realizations and usage possibilities

Wireless Local Area Network (WLAN);
 Connecting mobile and portable computers
to existing widely used fixed networks like the Internet;
 …
Page Number: 14/130
Mobile Networks
Drawbacks and limitations

Infrastructure is needed…
– Requires large investments
– Time consuming installation
– Communication cannot be always established
where needed
– Expensive maintenance
Page Number: 15/130
Mobile Networks

In many cases it is necessary to establish a connection
even if infrastructure does not exist, or is damaged.
 Typical example:
alarming rescuers in case of earthquake, flood,
war destruction…
 Communication must be established
without any preliminary setup (ad-hoc).
Page Number: 16/130
Mobile Networks
Ad-Hoc Networks

Mobile hosts
can communicate
between each other
on much greater distances
than covered by their ranges.
– That is practicable
thanks to presence
of other mobile hosts
that can be reached by the source host,
and that are willing to retransmit its packets further on
– Thus, propagating from one MH to another,
packets are conveyed to the destination

That is how multihop wireless communication
through a temporally formed ad-hoc network is realized.
Page Number: 17/130
Routing in Ad-Hoc Networks
How to find
the right way?
Routing in Ad-Hoc Networks





Efficient routing of packets
In conventional networks,
the most widely used routing algorithms are such as
distant vector or link state
Periodical broadcast,
with the purpose of keeping routing tables up-to-date
In some cases
those algorithms were adapted to be used in ad-hoc networks
We will just mention two representatives:
– Destination-Sequenced Distance-Vector (DSDV)
– Wireless Routing Protocol (WRP)

Benefit: Route to every host in the network is always known.
But…
Page Number: 19/130
Routing in Ad-Hoc Networks

Drawbacks of adapted conventional routing algorithms
seem to be of much more significance than the benefits:
–
–
–
–
–
Large bandwidth overhead
Batteries quickly become exhausted
Significantly reduced scalability
Unneeded cumulation of redundant routes
Often not able to quickly enough respond to dynamics of changes
in systems in which the hosts can move
Page Number: 20/130
Routing in Ad-Hoc Networks
On-demand routing protocols

Because of specified constraints of said solutions,
we are going to pay more attention on another approach,
which is fundamental for the so-called on demand routing protocols.
 We will shortly describe three of those protocols,
which attack the problem from different standpoints,
introducing different assumptions
and diversely prioritising problems that are to be solved:
– Dynamic Source Routing (DSR)
– Ad-Hoc On-Demand Distance Vector Routing (AODV)
– Temporally Oriented Routing Algorithm (TORA)
Page Number: 21/130
Routing in Ad-Hoc Networks

All the proposed solutions
contribute to the apparent reclamation of performance,
compared to classic algorithms,
which work much better in the stationary environment
for which they were designed in the first place.
 Algorithms that will be presented here are just specimens
of a large number of solutions developed by now (ietf.org).
 New algorithms are still being developed and evolved.
Page Number: 22/130
Routing Protocols - DSR
1. Dynamic Source Routing (DSR)

Based on the concept of source routing:
– Sender provides the sequence of nodes
through which the packets will be sent
– Sequences are held in route cache
that every host must maintain for itself

Route is determined dynamically, when it is needed:
– There are no periodical advertisements of routers
– Instead, every host initiates route discovery
when it needs to send a packet to another host
for which initiator does not have the associated route in its cache
Page Number: 23/130
Routing Protocols - DSR
Route Discovery – route request

Initiated by sending a route request packet:
– Propagates through the network
until it reaches the destination host (if the route exists);
– On its way, it collects addresses of all visited hosts,
and stores them into its route record;
3
1
5
1,3
1,3,4
1,3,4,5
1
src
1,2
1
4
1,3,4
2
6
dst
Page Number: 24/130
Routing Protocols - DSR
Route Discovery – route reply

The first route request packet that arrives to destination is accepted,
its route record is copied and returned to the initiator
using the route reply packet.
 Destination host returns the route reply
to the initiator of route discovery, using the route from its own cache.
(1,3,4,6)
5
3
(1,3,4,6)
1
4
(1,3,4,6)
6
2
Page Number: 25/130
Routing Protocols - DSR
Route Discovery – route reply (2)

If destination host does not have
a route to the source host in its cache,
there are two options:
1. Route reply is returned using inverse route
that was found by the route request packet;
2. Destination host initiates route discovery
to find a route to the original initiator.

First option requires symmetric links:
– Transfer quality must be the same
in both directions;
– But that is often not the fact
in mobile communications.
Page Number: 26/130
Routing Protocols - DSR
Route Discovery – route reply (3)

Second opportunity (inverse route discovery,
from destination to source) is more significant:
– Providing support for non-symmetric links
(very important merit of this algorithm).
– I that case, the original route reply
must be sent together with new route request,
i.e. attached to it (that is called piggybacking)
Page Number: 27/130
Routing Protocols - DSR
Route Maintenance

Implemented by acknowledgements
and route error packets.
 Acknowledgements may be:
– hop-by-hop – links must be symmetric
– end-by-end – important when links are not symmetric
Page Number: 28/130
Routing Protocols - DSR
Route Maintenance (2)

When using hop-by-hop
acknowledgement:
– Host which did not
get acknowledgement
?
for its retransmission
sends route error packet
with information about hop that broke down;
– Upon that error packet, source host truncates routing tree
being held in its cache, at the point of that hop:

When using end-by-end acknowledgement:
– Information about the point of breakage does not exist;
– Source host may only assume that the last hop is broken.
Page Number: 29/130
Routing Protocols - DSR
Modifications / Optimisations

Various modifications and amendments
of this algorithm are feasible.
 We’ll mention just one of them –
capability of working in the so-called
promiscuous receive mode:
– Host auscultate packets
that were sent to other hosts,
and updates its own cache
according to the information thus received;
– This, however,
causes more power to be used
and more rapid battery discharge .
Page Number: 30/130
Routing Protocols - DSR
Summary – DSR merits

Ability to work with asymmetric links.
 No periodical routing advertisement:
– Enables bandwidth and energy conservation;
– Overhead does not exist
when there are no changes in the network.

Can be easily improved to become able
for providing multiple routes:
– That way, it is not always necessary
to initiate new route discovery when some link breaks.
Page Number: 31/130
Routing Protocols - DSR
Summary – DSR drawbacks
Caused by the nature of source routing.
 Large bandwidth overhead:
– Route request packets rapidly grow
as they propagate through the network
(in their route records they store information
about every host over which they passed);
– That causes potential huge route reply packets;
– Also larger message packets,
because addressing demands the whole route to be specified.

Scalability problems – acceptable size of the network is limited:
– Diameter of the network (the largest number of hops
needed for communication between any two hosts in the network)
directly refers to bandwidth overhead.
Page Number: 32/130
Routing Protocols - DSR
Summary

Dynamic Source Routing protocol
is suitable for appliance in ad-hoc networks:
– with moderate numbers of mobile hosts;
– which move with moderate velocities.
Page Number: 33/130
Routing Protocols - AODV
2. Ad-Hoc On-Demand
Distance Vector Routing (AODV)

New route is discovered in a manner
that looks similar to route discovery by DSR:
– Source host (src) broadcasts route request (RREQ) to all of its neighbours
when needs to discover route to some destination host (dst);
– Then, it waits for route reply (RREP).

But similarity is discontinued at this point.
?
src
Page Number: 34/130
Routing Protocols - AODV
Route Request

Sequence number
– Number that every host generates for itself.
– It is incremented every time when something
is changed in adjacency (e.g., when some link breaks).
– For every route, destination sequence number (DSN)
is stored in the routing table
– Last DSN that src earlier knew for any route to dst, is sent in RREQ,
together with current sequence number of src
and other information needed:
RREQ (src, dst, srcSN, dstDSN, … )
Page Number: 35/130
Routing Protocols - AODV

RREQ does not contain the route record:
– Does not collect information
about hosts through which it propagates;
– Remembers only the number of hops.

Instead, the host through which RREQ propagates
adds inverse route (towards src) to its routing table:
– Stores, together with other relevant information,
the address of the neighbour (n1) that sent RREQ to it;
– If that host later receives relevant RREP, it will automatically know
that reply should be transferred to the neighbour (n1);
– In that case, it also records the address of the neighbour (n2)
that sent RREP, thus establishing route towards dst.
n1
RREQ
route to src
RREP
route to dst
Page Number: 36/130
n2
Routing Protocols - AODV

Instead of recording the whole route, as with DSR applied,
host here keeps only next hop (among other relevant information
about some destination), i.e. address of its neighbour
to which it transfers packets addressed to the destination:
D
S
N
A
O
D
V
3
6: 3,4,6
5
6: 4,6
1
4
2
6: 6
6
3
6: 3
5
6: 4
1
4
2
6: 6
Page Number: 37/130
6
Routing Protocols - AODV
Route Reply

When RREQ reaches a host that has a route to dst,
comparison of DSNs from the packet and from the routing table
is made:
– If DSN from RREQ is greater
 the host’s route to dst is not recent enough
 the host rebroadcasts the request;
DSN=10
DSN=10
DSN(dst)=8
– Otherwise, the host returns RREP to src,
with the calculated information about the discovered route
(total hop count, lifetime that remains…),
DSN=10
DSN=12
among which more recent DSN,
copied from the routing table of the host.
DSN(dst)=12
Page Number: 38/130
Routing Protocols - AODV

RREQ may reach dst itself, and then dst returns RREP to src.
 Anyway, RREP is returned using inverse route
formed by intermediate hosts during the propagation of RREQ.
dst
src
Page Number: 39/130
Routing Protocols - AODV
Route Maintenance

For every route
that a host is acquainted with,
it maintains the list of neighbours
that use that route,
so that it is able to notice them
about eventual link breakage
on the route.
 Link breakage is detected
by the absence of hello messages,
which must be emitted by every host
after the specified time interval expires.
Page Number: 40/130
Routing Protocols - AODV
Summary – Advantages of AODV over DSR

Significantly smaller
network bandwidth overhead:
– Both control and message packets are smaller;
– The reason is the requirement of only two addresses when routing
(destination and next hop), instead of the whole route
as with sequenced routing;
– This is good for scalability,
because the size of a packet
does not depend on the network diameter.

Provides support for multicasting.
Page Number: 41/130
Routing Protocols - AODV
Summary – AODV drawbacks

Works only with symmetric links.
 Hosts must periodically advertise hello messages:
– Increased bandwidth overhead;
– Reduced possibility of energy conservation
by remaining in the sleep mode.

Does not support multi path routing
(offers only one route per destination):
– Every time when some link
on the route breaks,
new route must be discovered;
– Increased probability of congestion.
Page Number: 42/130
Routing Protocols - TORA
3. Temporally Oriented
Routing Algorithm (TORA)

Offers an interesting approach to problem solution.
 Conceived as link-reversal algorithm.
 The idea is to define topology of a network
using a directed acyclic graph (DAG):
– Hosts represented as nodes
and with directed links;
– Direction of link is realized
by assigning height to every node,
so that the link is directed
from the node with greater height
to the node with lower height.
Page Number: 43/130
Routing Protocols - TORA
General idea

The destination node should have the minimal height in the graph.
 Other nodes get greater and greater height
as the distance from the destination grows.
 Packets may be sent only from “higher” to “lower” nodes,
i.e., only via downstream links.
Page Number: 44/130
Routing Protocols - TORA
DAG Forming

Starts when node that does not have downstream links
wants to send a packet to a destination node.
 Initially, all nodes in the graph have undetermined height (NULL),
except the destination node that has the height of ZERO
(which is considered less even from NULL).
 Source node then broadcasts QRY packet to its neighbours.
 QRY packet propagates through the network,
marking every node over which it passes
as “interested for route discovery”
by setting its route request flag.
Page Number: 45/130
Routing Protocols - TORA

When QRY packet arrives to a node
that has at least one downstream link,
the node then emits the UPD packet.
 UPD propagates back through the network,
setting the height to all nodes with the route request flag set,
at the same time resetting those flags.
 Every further node gets greater height
then the precedent one on the path of the UPD propagation.
dst
src
Page Number: 46/130
Routing Protocols - TORA

Many downstream links can lead to the same destination.
 Algorithm enables multiple path routing.
Page Number: 47/130
Routing Protocols - TORA

In case of link break:
– If the node still has downstream links left, no action is performed
– Otherwise, the node broadcasts a UPD packet, thus recovering DAG

Recovering is a one-pass process,
except in the case of network partitioning
Page Number: 48/130
Routing Protocols - TORA
Advantages of TORA:





Fast route discovery
Multiple path routing
Recovering is localised
Multicast support
Lightweight Adaptive Multicast (LAM) algorithm
Page Number: 49/130
Routing Protocols - TORA
Downsides of TORA:
Requires external timing mechanism (GPS…)
 DAG becomes less optimal as the time passes

– Can be solved using refresh packets
Page Number: 50/130
Routing Protocols - TORA
TORA is designed for:

Large networks
 Many nodes with dense distribution
Page Number: 51/130
Issue of Security
in Ad-Hoc Networks
There is no need to see
his identification...
Attributes of security
The attributes of security are:





Availability
Confidentiality
Integrity
Authentication
Non-repudiation.
Page Number: 53/130
Attributes of security




Availability
ensures the survivability of network services
despite denial of service attacks.
A denial of service attack could be launched
at any layer of an ad hoc network.
On the physical and media access control layers,
an adversary could employ jamming
to interfere with communication on physical channels.
On the network layer disruption of the routing protocol
can cause a break of the network.
Page Number: 54/130
Attributes of security

Confidentiality ensures that certain information
is never disclosed to unauthorized entities.
 Leakage of information could have devastating
consequences.
 Routing information must also remain confidential in some cases.
Page Number: 55/130
Attributes of security

Integrity guarantees that a message being transferred is
never corrupted.
 A message could be corrupted because of benign failures,
such as radio propagation impairment,
or because of a malicious attacks on the network.
Page Number: 56/130
Attributes of security

Authentication enables a node
to ensure the identity of the peer
node it is communicating with.
 Without authentication, an
adversary could masquerade a
node, thus gaining unauthorized
access to resource and sensitive
information and interfering with
the operation of other nodes.
Page Number: 57/130
Attributes of security

Non-repudiation ensures that that the origin
of a message cannot deny having sent the message.
 Non-repudiation is useful for detection and isolation
of compromised nodes.
Page Number: 58/130
Challenges and opportunities

Attacks ranging from passive eavesdropping
to active impersonation, message replay, and message distortion.
 Eavesdropping might give an adversary access
to secret information, violating confidentiality.
 Active attack might allow the adversary:
–
–
–
–

to delete messages,
to inject erroneous messages,
to modify messages, and
to impersonate a node
Violating availability, integrity, authentication, and non-repudiation.
Page Number: 59/130
Challenges and opportunities

We should take into account the attacks
launched from within the network, by compromised nodes.
 The ad-hoc networks should have a distributed architecture
with no central entities.
 Introducing any central entity into our security solution
could lead to significant vulnerability.
Page Number: 60/130
Challenges and opportunities

There are two sources of threats to routing protocols:
– from external attackers
– from compromised nodes
Page Number: 61/130
Challenges and opportunities

Detection of incorrect information is difficult
 Outdated routing information
 False routing information generated by compromised nodes
could be considered as the outdated information
 If routing protocols can discover multiple routers,
nodes can switch to an alternative route
Page Number: 62/130
Challenges and opportunities

Another way is to use diversity coding
 Diversity coding takes advantage of multiple paths
in an efficient way, without message retransmission
 Even if certain routes are compromised,
the received node may still be able to validate
and to recover messages
Page Number: 63/130
Challenges and opportunities

Cryptographic schemes
– digital signature
– public and private keys

Key management service
 A public key infrastructure is superior in distributing keys
and in achieving integrity and non-repudiation.
 In a public key infrastructure,
each node has a public/private key pair.
 Public keys can be distributed to other nodes,
while private keys should be kept confidential
to individual nodes.
Page Number: 64/130
Challenges and opportunities







There is a trusted entity called Certification Authority (CA)
for key management.
The CA has a public/private key pair
Public key is known to every node
CA signs certificates binding public keys to nodes
The trusted CA has to stay on-line to reflect the current binding
Although no single node is trustworthy in an ad hoc network
we can distribute trust to an aggregation of nodes.
Assuming that any t+1 nodes will unlikely be all compromised,
consensus of at least t+1 nodes is trustworthy.
Page Number: 65/130
Challenges and opportunities

This is the principle of distributed trust.
 To accomplish distribution of trust in key management service
one can use threshold cryptography.
 An (n,t+1) threshold cryptography
scheme allows n parties to share
the ability to perform a cryptographic
operation (e.g., creating a digital
signature), so that any t+1 parties
can perform this operation jointly,
whereas it is infeasible for most t
parties to do so, even by collusion.
Page Number: 66/130
Challenges and opportunities

We divide the private key k of the service into n shares
(s1,s2,…,sn), assigning one share to each server.
 Each server generates a partial signature for the certificate using
its private key share
 With t +1 correct partial signature,
the combiner is able to compute the signature for the certificate.
 Compromised servers cannot generate
correctly signed certificates by themselves
Page Number: 67/130
Challenges and opportunities





A combiner can verify the validity of a computed signature
using the service public key.
In case verification fails
the combiner tries another set of partial signatures.
A problem with threshold cryptography is that it assumes
synchronous system and an ad hoc network is asynchronous by its nature
Any synchrony assumption is a vulnerability in the system
Fortunately there is an asynchrony prototype of such a key management
service, which has been implemented recently.
Page Number: 68/130
Summary





An ad hoc network is very vulnerable to many kinds of attacks.
We have to protect not only the data, but also the routing information.
The best way for that is a cryptography scheme
with public/private key management, combined with distribution of trust.
But it is not cheap and it is complex.
A lot of things still have to be done in this area in the future.
Page Number: 69/130
Bluetooth
Following the steps of
King Harald...
Bluetooth
Special Interest Group (SIG):





Ericsson Mobile Communications AB
IBM Corp.
Intel Corp.
Nokia Mobile Phones
Toshiba Corp.
Page Number: 71/130
Bluetooth
Bluetooth wireless technology:






Open specification for short-range wireless connectivity
Effortless, instant connections
Wide range of communication devices
Based on a radio link
Facilitates fast and secure transmission of both voice and data
Operates in a globally available frequency band
Page Number: 72/130
Bluetooth
Bluetooth module:
• ports (USB, UART, PCM)
• baseband
• voltage regulator
• crystal
• radio
• antenna interface
• flash
Page Number: 73/130
Bluetooth
External interfaces:
• USB 1.1 (12 Mbps), full USB slave functionality
• UART (Rx, Tx, RTS and CTS), 460.8 kbs
• PCM (sync 8kHz, clock 200kHz-2MHz)
Antenna Interface:
• 50 ohm Bluetooth ISM band antenna (2.4 - 2.5 GHz)
Page Number: 74/130
Bluetooth
Communication layers:
• Base Band (BB)
• Link Manager (LM)
• Host Controller Interface (HCI)
Additional software:
• L2CAP
• RFCOMM
Page Number: 75/130
Bluetooth
Base Band General Description:
• Frequency hop transceiver
• Shaped, binary FM modulation
• Symbol rate is 1 Ms/s
• Slotted channel is applied with a nominal slot length of 625 ms.
• Time-Division Duplex (TDD) scheme
• Information is exchanged through packets
• Each packet is transmitted on a different hop frequency
• Combination of circuit and packet switching.
Page Number: 76/130
Bluetooth
Bluetooth can support:
• Asynchronous data channel
• Up to three simultaneous synchronous voice channels
• Channel which simultaneously supports asynchronous data
and synchronous voice
Page Number: 77/130
Bluetooth
Bluetooth system consists of:
• Radio unit
• Link control unit
• Link management and host terminal interface functions
Page Number: 78/130
Bluetooth
Connection types:
Master/slave communication:
• point-to-point
• piconets
• point-to-multipoint
• scatternets
Page Number: 79/130
Bluetooth
Other features:
• Link Manager Protocol
• Logical Link Control
• Service Discovery Protocol
• RFCOMM
Potential platform for
ad-hoc network realization!
• IrDA
• Telephony Control Protocol
• ...
Page Number: 80/130
Design of ad-hoc multihop sensor net
with Bluetooth: Lessons learned
How to make your
electronic devices
cooperate with each other?
Introduction
The main goals of this project:

Creating hw/sw specification for replacing and/or upgrading the
existing wire systems for data acquisition and process control
– Development of routing protocol
– Connecting Bluetooth with a microcontroller (router)
– Integration of routing protocol on the base Bluetooth chip

Universal platform for wireless integration:
– Stable and universal hardware platform
– Reliable and easy replaceable software
Page Number: 82/130
System Overwiev
An open data acquistion system, based on wireless
ad-hoc multihop sensor network:






Routing protocol
Interface and routing module (IFRM)
Personal Digital Assistant (PDA)
Digital Signal Processing System (DSPS)
Software for data acquisition (Shell)
Internet accessible database
Page Number: 83/130
System Overview
DSPS
PDA
IFRM
IFRM
Bluetooth
Bluetooth
simulated
sensors
Bluetooth
Web Server
database
AD-HOC
network
Web
client
Page Number: 84/130
System Overview
Basic advantages:

Universal and open platform
 Can be implemented in any environment
Possibilites of use:





Factories
Power plants
Health-care institutions
Rescue actions
Research of inhospitable terrain
Page Number: 85/130
System Overview
Main problems:

Providing critical data transmission rate
 Stable ad-hoc networks
Proposed solutions:

Bluetooth technology
 Designed routing protocol
Page Number: 86/130
Implementation - routing protocol
Designed with the following guidelines:

speed
 reliability
 simplicity
Existing solutions considered:

DSR
 AODV
 TORA
Page Number: 87/130
Implementation - routing protocol
The routing algorithm defines three types of messages:

Route Request (RREQ)
 Route Reply (RREP)
 Route Error (RERR)
Page Number: 88/130
Implementation - routing protocol
Route Request:
RREQ:
Hop Count
BCID
Dest Address
DSN
Source Address
SSN
Hop Count – number of hops to the ending node
BCID – unique RREQ identifier
Destination Address – address to which the route is requested
DSN – the last known sequence number
Source Address – address of the node that issued RREQ
SSN – current route sequence number
Page Number: 89/130
Implementation - routing protocol
Route Reply:
RREP:
Destination
Source
DSN
Lifetime
Address
Address
Hop Count – numer of hops between the source and destination
Destination Address – address of node for which a route is found
DSN – route sequence number
Source Address – address of the node that sent RREQ
Lifetime – time in which the route is considered valid
Hop Count
Page Number: 90/130
Implementation - routing protocol
Route Error:
RERR:
Unreachable
Unreachable
Dest Address
DSN
DestCount – number of unreachable nodes
Unreachable Dest Address – address of the unreachable node
Unreachable DSN – last knows DSN, incremented by 1
DestCount
Page Number: 91/130
Implementation - routing protocol
Functioning of the protocol:

Master
 Gateway
 Slave
Page Number: 92/130
Implementation - routing protocol
Possible network topology
11 M4
master
16 M3
gateway
8
10
9
plain node
2
10
12
0 M0
11 M4
3
13
7
4
M1
Page Number: 93/130
14
6
5
M2
15 M5
Implementation - routing protocol
System initialization:

Forming of piconets
 Creation of neighboor tables
 Initialization of empty routing tables
Page Number: 94/130
Implementation - routing protocol
Routing table entry
Dest
Address
DSN
Hop
Count
Last
Hop Count
Next
Hop
Precursors
Dest Address – address of the destination node
DSN – destination sequence number
Hop Count – number of hops to destination
Last Hop Count – hop count before route invalidation
Precursors – list of forwarding nodes
Lifetime – time for which route is valid
Page Number: 95/130
Lifetime
Implementation - routing protocol
Sending RERR:

Link is broken
 No active route to destination
 RRER is received from a neigboring node
Page Number: 96/130
Implementation - routing protocol
Simulation:





Starting topology specified in the configuration file
Number of nodes is not limited
For each node, a separate thread of execution is created
Messages and destinations are being generated in random fashion
Traversing of nodes between piconets
Page Number: 97/130
Implementation - routing protocol
Process of route discovery (RREQ forwarding)
M0
M1
0
16 M3 M0
M1
RREQ
2
2
0
0
2
RREQ
M0
11 M4
8
0
RREQ
RREQ
8
RREQ
RREQ
4
1
M1
M0
1
0
0 M0
RREQ
5
M0
M1
3,7
3,7
M2
RREQ
3 M0
M1
0
RREP
0
Page Number: 98/130
Implementation - routing protocol
Process of route discovery (RREP forwarding)
6
M1
0
RREP 4
1
M1
M0
6
RREP
1
3,7
0
0
0 M0
6
1
0
RREP
3 M0
Page Number: 99/130
M1
0
Implementation - routing protocol
Usability analysis:

Advantages compared to classic broadcast algorithms
number of connections
number of nodes
Page Number: 100/130
Implementation - routing protocol
Usability analysis:

Elimination of redundant piconets
master
3
1
slave hosts break connections
1
4
2
master
3
2
master is detecting
a new host
5
5
5
5
host is entering piconet
5
host is entering piconet
master
3
1
2
4
5
Page Number: 101/130
5
4
Implementation - IFRM
The routing protocol was implemented
in a separate hardware module:

Serial (UART) connection with Bluetooth

HCI level
Page Number: 102/130
Implementation - IFRM
The main functions of IFRM:

Forming of a wireless multihop ad-hoc network

Link maintenance

Packet routing

Route discovery

Providing a transparent interface
between the ad-hoc network and any serial (RS-232) device

Providing PDA functionality
Page Number: 103/130
Implementation - IFRM
The architecture of IFRM:
CON6
ICSP
External RAM
16 KB
(8 Kwords)
CON4
serial port 2
to Bluetooth
module
PIC 17C756A
microcontoller
External FLASH
ROM
64 KB
(32 Kwords)
CON3
serial port 1
CON2 & CON5
I/O ports
to keyboard
(optional)
signaling
LEDs
to LCD
(optional)
Page Number: 104/130
to host
(sensor, PC, etc.)
Implementation - IFRM
Routing protocol - host side
The modified AODV protocol, with the following restrictions:
– Size of routing tables is limited to 79 entries
– Communication in the network is server centric
MH
MH
MH
MH
MH
MH
MH
MH
SERVER
MH
MH
MH
MH
MH
MH – mobile host (e.g. sensor)
data flow
Page Number: 105/130
Implementation - IFRM
Routing protocol - host side
The modified AODV protocol, with the following restrictions:
–
–
–
–
End-to-end flow control is omitted
CRC checking and retransmission are not implemented
Packet sequence is not checked
Restrictions due to fact that Bluetooth modules do not conform
to the Bluetooth V1.0B specification
Page Number: 106/130
Implementation - IFRM
Routing protocol - host side
Assumptions due to uncomformance to V1.0b specification:
– In course of full-duplex communication
there is no implicit master-slave switch
– Inquiry and paging are possible
without interfering with the current transmission
– Only the master can broadcast on the piconet
– A node can transparently be a member in more piconets
(Bluetooth baseband controller is capable of transparent TD multiplexing)
– It is possible to have more than 7 nodes in a piconet
(parking and unparking is done transparently by the baseband controller)
Page Number: 107/130
Implementation - IFRM
Routing protocol - host side
Bugs and workarounds:
– Sending two consecutive broadcast packets causes a reset
– During maximum full-duplex transfer,
packets or parts of the packets disappear
Page Number: 108/130
Implementation - IFRM
Connection of IFRM with the mobile host
IFRM
HOST
(e.g. sensor, PC, etc.)
Routing
Page Number: 109/130
BLUETOOTH
MODULE
Ad-hoc
network
Implementation - IFRM
Routing protocol - server side

No routing module
 The software performs routing
 Special mechanism for implicit destination address discovery
Page Number: 110/130
Implementation - IFRM
Routing protocol - server side

Communication with Bluetooth
–
–
–
–
–
TCP ports
For each mobile host exists a corresponding TCP port on the sever
Port numbers start from 10 000
All communication is performed over the TCP/IP connections on these ports
The mapping of ports and hardware addresses of Bluetooth modules is static
SERVER (PC)
Expert system
BLUETOOTH
MODULE
Page Number: 111/130
Ad-hoc
network
Implementation - PDA
The role of PDA is to provide mobility to the expert.

PDA is capable of receiving two types of messages:
– Sensors have reported irregular data, but expert system managed to stabilize
the system. The confirmation is required.
– Sensors have reported irregular data and expert system did not manage
to stabilize the system. The remote command and presence is required.

PDA is capable of sending two types of messages:
– Confirmation of received warning
– Command that initiates some action in the system, based on received data

In this phase, the internal battery supply is not designed.
Page Number: 112/130
Implementation - DSPS
DSPS is realised as an example of device
that can be connected to this platform.

Based on TI Digital Signal Processor
 Gathering of information from different peripherals
 Real-time processing
 Transferring data to server over IFRM
Page Number: 113/130
Implementation - DSPS
The DSPS architecture:
CON8:
Address, Data &
Control DSP Bus
Signaling
LED
PWM
CON8:
Analog
Inputs
Resistor
Capacitor
Diode
Matrix
TI
TMS320LF2407
SPI
Interface
CON 9:
Synchronous
Serial Link
LCD (optional)
SCI
Interface
MAX3225
CON2:
RS232
Page Number: 114/130
Capture
Timer
CON6:
Event
Manager
A
CAN BUS
Interface
PCA82C250
CON3:
CAN BUS
Implementation - DSPS
DSPS Communication:

Standard RS-232 connection (MAX3225cpp)
 CAN driver
 Synchronous Serial Interface (SPI)
Analog Input
Digital
Signal
Processing
Module
Page Number: 115/130
Interface
Module
(IFRM)
Implementation - DSPS
DSPS function:

Finding spectrum of some analog signal using FFT
 Transferring data to server via transparent ad-hoc network
 Receiving commands from the system,
thus creating positive feedback system
Page Number: 116/130
Implementation - Shell
Multipurpose software platform:






Data acquisition
Decision making
Signal processing
Slarming
Tracking the current state
of the system
Database administration
Page Number: 117/130
Implementation - Shell
Communication with sensors:

TCP/IP ports
 Two-way socket communication
 Conformance to IEEE 999-1992. SCADA specification
Page Number: 118/130
Implementation - Shell
System configuration:




Type of the sensor
Name of the sensor
Factory address of
corresponding Bluetooth module
Range of allowed values
Page Number: 119/130
Implementation - Shell
Readings display




Simple view
Graph view
Real-time
monitoring
History
Page Number: 120/130
Implementation - Shell
Spectrum analysis
Page Number: 121/130
Implementation - Shell
Database

Realized with MySQL Server
 ODBC
 Flexible, DBMS independent
Page Number: 122/130
Implementation - Shell
Expert System





Monitoring (controlling)
Knowledge base
Algorithm of direct chaining
Based on preconditions (sensor readings) and using the rules,
the expert system reaches a decision
Depending on the actual application,
any expert system with its knowledge base can be easily integrated
Page Number: 123/130
Implementation - Internet connectivity
The system database can be accessed from a Web client,
with the purpose of shortening the response time.

MySQL Server
 PHP 4.0.4
 Apache Web Server 1.3.14
Page Number: 124/130
Implementation - Internet connectivity
Standard three-tier architecture is used:
http request
server
web client
http reply
sql query
PHP script
Page Number: 125/130
recordset
DBMS
Implementation - Internet connectivity
Web client access:



Username and password
Choosing between sensors
Formulating search queries:
– by time
– by value

Extending the system
towards full Internet automation
Page Number: 126/130
Testing and integration
Separate component testing:







Routing protocol
IFRM
DSPS
PDA
Shell
Database
Internet connectivity
Page Number: 127/130
Testing and integration
Component integration:



Shell and database
Internet access
Communication between Shell and IFRM
Page Number: 128/130
Testing and integration
Final integration:



Modification of the simulator
Testing IFRM in the network with more than 100 nodes
Integration of DSPS
Page Number: 129/130
Summary







Indicating a new course of development of wireless communication
Integration of different electronic devices in a single information network
Open system: any device capable of serial communication can be connected
Creation of custom ad-hoc networks
Java-enabled microcontrollers
Integration of the routing protocol on the Bluetooth baseband
Possible improvements:
–
–
–
–
–
–
Additional research of the routing protocol
Testing IFRM in real-world working conditions
Making software even more modular
Development of several classes of sensors
Potential GPS integration
Internet automation
Page Number: 130/130