Chapter 2 -Ad-hoc and Sensor

Networks

2022
Abebe Belay (PhD)
Ad-hoc and Sensor Networks
 1. Ad-hoc Networking
Types of Networks
Cellular Networks
base stations distributed over the
field
each base station covers a cell
used for mobile phones
WLAN can be seen as a special case
Sensor Networks
network of sensor devices with
controller and radio transceivers
base station with more resources
Mobile Ad Hoc Networks
self-configuring network of mobile
nodes
node serve as client and router
no infrastructure necessary
 Wireless Ad-hoc network

An ad hoc wireless network is a collection of

wireless mobile nodes that self-configure to form
a network without the aid of any established
infrastructure.
Multihop routing, whereby intermediate nodes
relay packets towards their final destination, can
improve the throughput and power efficiency of
the network. Webster’s lists two relevant
definitions for ad hoc: “formed or used for
specific or immediate problems”, and “fashioned
from whatever is immediately available.”
 MANET
A Mobile Ad hoc Network (MANET)
Formed as needed
Does not require support from any existing network
infrastructure
MANET: An autonomous system of mobile nodes or
MSs (also serving as routers) connected by wireless
links, the union of which forms a communications
network modeled in the form of an arbitrary
communication graph
 Autonomous => does not require support from any existing
network infrastructure

Notice how different from cellular network

Requires infrastructure (BS, MSC, backbone network, etc.) => not ad
hoc
Characteristics of MANETs:
Dynamically changing topology
 Changing in an unpredictable manner
Since nodes are free to move
Limited power available to nodes (e.g., a battery)
Usually communicates only with neighboring nodes
 Among other reasons, to save power
Peer-to-peer
 No more or less “important” nodes
Information transmission via store-and-forward
 Using multi-hop routing
 MSs also serve as routers
Lack of single points-of-failure. Asymmetric =
unidirectional - when
xmission power of
nodes on its ends is
Moving to a new location different (e.g., MS4
MS2 MS2 stronger than MS7)

MS4
MS3 Asymmetric link
MS5
Symmetric link MS7
MS1 MS6
 Mobile Ad Hoc Networks (MANET)
Topology change frequent B
A
A
B

No cellular infrastructure. Multi-hop wireless links.

Data must be routed via intermediate nodes.
 Mobile Ad Hoc Networks (MANET)
Communication characteristics for MANETs:
Each node equipped with a wireless transmitter and
a receiver with an appropriate antenna
Impossible to have all nodes within each other’s
radio range
When the nodes are close by (within each others radio range),
they can communicate directly
 If direct comm. => no routing needed (one hop)
Wireless connectivity modeled by a random multi-
hop graph exists between the nodes.
As nodes move:
Connectivity changes
Topology information must be updated
E.g., MS2 changes attachment: from MS3 to MS4
 Characteristics of Ad Hoc ….
Dynamic topologies
Network topology may change dynamically as the
nodes are free to move
Bandwidth-constrained, variable capacity links
Wireless links have typically lower capacity than wired
Realized throughput of wireless communication is
lower than the radio’s maximum transmission rate
Link capacity is relatively low => congestion is
common (collisions occurs frequently as application demand
approaches link capacity)

Energy-constrained operation
Nodes in ad hoc network may rely on batteries or other
limited energy sources
 Energy conservation may be a dominant design factor
Limited physical security
More prone to physical security threats than wired
networks
Incl. stealing mobile ad hoc devices
Many attacks, incl. Eavesdropping, spoofing, and DoS
attacks are easier

Decentralized network control

Eliminates single points of failure (=> better reliability)

Scalability problems
As networks get large
 Why Ad Hoc Networks ?

Setting up of fixed access points and backbone

infrastructure is not always viable
Infrastructure may not be present in a disaster area or war zone
Infrastructure may not be practical for short-range radios;
Bluetooth (range ~ 10m)

Ad hoc networks do not need backbone infrastructure support

Ad hoc networks are easy to deploy and useful when infrastructure

is absent, destroyed or impractical
Applications
Network Failure areas
Military
Deserted Areas
Entertainment
Spontanous games
Dating-Tool
Sensor networks
Environmental control
Intelligent Home
Supermarket
Car technology
Inter-car communication
Car coordination
WLAN hotspot extension
Elements of a wireless network

infrastructure mode
 base station connects
mobiles into wired
network
 handoff: mobile changes
network
infrastructure
base station providing
connection into wired
network
Elements of a wireless network

ad hoc mode
 no base stations
 nodes can only
transmit to other
nodes within link
coverage
 nodes organize
themselves into a
network: route
among themselves
 Wireless network taxonomy

single hop multiple hops

Infrastructure host connects to host may have to
(e.g., APs) base station (WiFi, relay through several
WiMAX, cellular) wireless nodes to
which connects to connect to larger
larger Internet Internet: mesh net
no no base station, no no base station, no
infrastructure connection to larger connection to larger
Internet (Bluetooth, Internet. May have to
ad hoc nets) relay to reach other
a given wireless node
MANET, VANET
Challenges of Ad-hoc network
 Routing in MANETS
Many factors affecting routing in MANETs:
Models of topology
Selection of routers
Initiation of route requests
Specific underlying characteristics
 E.g. application-based characteristics

Major goals in selecting routing protocols:

Provide the maximum possible reliability - use alternative
routes if an intermediate node fails
Choose a route with the least cost
 E.g., minimal # of hops from source to destination
Give the nodes the best possible response time and
throughput
Each node in MANETs expected to serve as a router
All execute the same routing protocol
Protocol calculates a route
 Routing Classification
Types of routing protocols:
1) Proactive protocols
Keep routes ready at all times
have lower latency due to maintenance of routes at all times
can result in much higher overhead due to frequent route updates
Example: distance vector routing protocols .

2) Reactive (= on-demand) protocols

Route determination on demand
Determine a route only when there is a packet to send.
Characterized by:
Higher latency since the routes have to be discovered when the source node initiates a
route request
Lower overhead since routes are maintained only on-demand basis
 Examples:flooding routing algorithms, ad hoc on-demand distance vector
(AODV), temporarily ordered routing algorithm (TORA).
 Ad hoc Routing
Protocols

Table Driven Source-Initiated

Hybrid
(Proactive) On-demand Driven
(Reactive)

ZRP

CGSR DSDVWRP
AODV DSR TORA ABR SSR
 Assignments

1. Use a python program to implement the

following routing protocols accordingly, and
report the performances (individual Project
10%).
1. Distance vector routing protocols-maraf
2. Flooding routing algorithms-Bilisua
3. Ad hoc on-demand distance vector (AODV)
- Kassahun
4. Temporarily ordered routing algorithm
(TORA).- Mohamed
5. ABR - Yetsedaw
6. SSR - Awol

• Due date will be 26/12/2022 G.C

 2. Sensor Network
Sensor networks promise to revolutionize sensing in a wide
range of application domains.
Characterized by Reliability, accuracy, flexibility, Cost-
effectiveness, ease of deployment.
Key Features that differentiate them from conventional data networks
Power autonomous (operating mainly on batteries)
Highly scalable: distributed in scales of hundreds (or
thousands)
Operate in a ad-hoc manner, i.e., does not require fixed
infrastructure (e.g. GSM or WiFi routers)
Easy to deploy and cost-effective (cheap hardware)
Low data rates (max 1Mbps)
Usually special-purpose devices, use very limited resource,
operate without human interface and has Specialized
routing patterns
 Sensor Network
Realization of pervasive/ubiquitous computing
relies on the wireless sensor nodes (smart sensors)
or simply sensors that have the ability to monitor
physical, chemical or biological properties.
Ad-hoc network of sensor nodes is also required to
accomplish the intended sensing, monitoring and
dissemination .
Wireless network of smart sensors have become
feasible for many applications because of
technological advances.
Sensor network: leads towards the realization of
the vision of “Internet of things”!
 Advantages
Collect information from the physical
environment – regardless of how easily
accessible that is;
Couple the end-users directly to the sensor
measurements ( cyber to physical space);
Provide information that is precisely localized
(in spatio-temporal terms) according to the
application demands;
Establish a bi-directional link with the
physical space (remote & adaptable actuation
based on the sensing stimulus)
Example of WSN
 Sensor Network

Tasks in Wireless Sensor Network

• Neighbour discovery
• Self-organization or self-configuration
• Sensing
• Signal processing or sensor data processing
• Data aggregation, storage, and caching
• Target detection, target tracking and target monitoring
• Topology control for energy savings
• Localization
• Time synchronization
• Routing
• Medium access control
 Sensor Network
Smart, networked sensors will soon be all around us
 Homes, offices, factories, automobiles, shopping centers,
supermarkets, farms, forests, rivers, dams and lakes
 Collectively processing vast amounts of previously unrecorded data
to help run factories, optimize farming, monitor health, monitor
weather, monitor dams and even watch for earthquakes

New developments are bringing wireless sensors

that talk with each other, forming intelligent
networks spread over wide areas.
Wireless sensor networks are one of the first real-
world examples of "pervasive" computing - small,
smart, cheap, sensing and computing devices that
flood the environment.
 Sensor Network

RFID sensors – Radio Frequency

Identification

RFIDs exist in two forms

RFID Readers/Sensors
RFID tags
 Ad-hoc and Sensor Network

RFID readers/sensors/ devices exist as:

1. Wired Sensors with no serious power

constraints
 Has physical Sensors/Readers
 Has microprocessor for local data
processing and a network connection
 Has gateways and controllers
 Ad-hoc and Sensor Network

RFID readers …
2. PDA-like battery-driven mobile devices (embedded)
 Functionally, similar to the wired sensors
 Use wireless connections to the backbone network
 Used for RFID-based inventory control, personal smart
sensor systems for example medical control.
3. Battery-driven, low-power, low-performance smart
sensors
 Needs a gateway to connect to a computer network
 Ad-hoc and Sensor Network

RFID Tags exist in the form of

Active tags
Have own energy source
Passive Tags
Have no own energy source
Powered by electromagnetic field generated
by reader
 3. Ad-hoc and Sensor Network
Common Applications
Military applications
Command, control, communications, computing
Intelligence, surveillance
Targeting system

Health care
Monitoring/Tracking patients
Assist disabled persons

Commercial applications
Managing inventory
Monitoring product quality
Monitoring disaster area
 Ad-hoc and Sensor Network
Common Applications…
Agriculture and environment
Air/Water/Noise/Light monitoring
Soil/weather/plant monitoring
Food/animal monitoring

Industrial
Process control
Equipment monitoring
Asset tracking
Personnel safety

Batch identification
Automatic clocking in marathon and other races
Automatic luggage sorting
Automatic inventory
 Ad-hoc and Sensor Network

• Modeling indoor positioning using (WiFi) RF signal strength

Methods exist to detect positions in an (x, y) coordinate

but neighbourhood relation between users is expressed
not by the physical proximity but by the perception of the
presence in the same bounded space/room.

Inline with this requirement, in addition to physical

proximity, our proposed neighbourhood localisation
brings some semantic information concerning the space
containing the entities.
 Ad-hoc and Sensor Network
Modeling indoor positioning using RF signal strength …

Among localization and distance measuring methods

are
 Global Positioning Systems (GPS)
 Radio Frequency delay measurement(RFDM)
 Association to nearest Access Point (AAP)
 Received RF signal strength

Systems like GPS are good for outdoor positioning services.

Most of the other techniques (RFDM and AAP) are based on
triangulation methods and/or they assume prior knowledge of
position of the access point infrastructure.
Received RF signal Strength is used in this work
 Ad-hoc and Sensor Network
Modeling indoor positioning using RF signal strength …
Involved two phases:
Learning phase: data is collected, classified, and interpreted to create
the prediction model
Prediction phase: uses the model for location prediction based on the
real-time data values
Learning phase Prediction phase
(Offline) (Real time)
Signal Signal
Tracking Distributed on Tracking
Capable Peers

Data
Calibration and Calibration and Data Calibration
Treatment Treatment Rules Context –Aware
Service
(Interpretation
Data Mining Prediction Rules and Action)
Prediction Context
(Decision Tree) (PMML Format)
room name
Architecture of the prediction model
 Ad-hoc and Sensor Network
Learning Phase …

A person holding a PDA moves around the rooms in the

building including meeting halls, offices, common rooms,
printing rooms and corridors
201 203 205 207 209 215 217 221 223 225 227
Salle Serveurs D. Magnin M. Martinez
WC
Atelier
Détente AEDI TP 5IF1 TP PC4 Réseau G.Neubert I. El Kalkali
Elèves
TP PC5
211 213 219 Y.Ouzrout P.A. Millet

Ascenseur
B501225A PRISMA

PRISMA PRISMA
L.Frécon PRISMA
M.MATAR Salle réunion
TP PC3 TP PC2 TP 5IF2 TP PC1 TP PC0 Salle TD secretariat étudiants
202 204 208 J.FAVREL
210 212
214 216 218 220 222 224
206

N
305 307 309 311 313 315 317 319 321 323
301 325
Benel

Passerelle Masson Besson Berhe Salle TD Salle TD Salle TP - FC Salle TD Amphi FC

Réseau WC
Salle de Réunion Direction Sécrétariat Laforest Servigne Verdier Saoula Samir Piersno Meger Leschi Robardet Seitz 329 331 333 335 337

Tchounikine Miquel Cardenas Arias Ahmed- Leleu Rigotti Prensa Tribollet

Ascenseur

Servin Ouamer
Suela Bohé Hunor Dejene

30

Taher Ahmed Andrianarisoa Secrétariat

Chatti Egyed Coulondre Calabretto Alvarez Boumediene Ou-halima Varet
Arara Keita Flory Badr EDIIS
Salle Balhoul Boulicaut
Manzi Accary Amghar Rifaieh Coquil Brunie Secrétariat Abbas Demars Direction Secrétariat Coquard
Jossan Pozzoli détente Réseau Taqafi Kouloumdjian Salle TD Salle TD
Berkane Oularbi Pivano Pech EDIIS formation Formation
Ouziri Ridh Hadj 340 342
Chaari Jouve continue continue
M’tir Lebel
302 314 324
304 306 308 316 318 320 322 326 328 330 332 334 336 338

Topology of the two floors used in the experiments

Passerelle
 Ad-hoc and Sensor Network
Learning Phase …
A WiFi-Spotter and management program tracks,
processes and stores received signal strength from all n
visible access points at each tracking location.
Tracking signals coming
from different access
points
 Ad-hoc and Sensor Network
Learning Phase …

For each tracking point i in room k, we have array of signal

strength values and a label corresponding to the literal name
of the place (room) where the point is situated.

ap 1
k ,i
2 n
, ap ,..., ap , roomk ,i
k ,i k ,i  i 1, 2 ,....
Room 00:06:5A:40:0D:C6 00:06:5A:40:0D:D7 00:06:5A:10:0D:C6 00:06:5A:10:0D:D7
501.317 -60 -60 -60 -57
501.317 -60 -60 -60 -57
501.317 -68 -63 -59 -65
501.319 -60 -62 -64 -100
501.319 -57 -57 -60 -100
501.319 -57 -66 -57 -100

Sample attribute-value table showing tracked values.

 Ad-hoc and Sensor Network
Learning Phase …

Signal strength values are classified for pattern identification

using data mining tool (decision tree algorithm
implemented) or machine learning.

The result from this process become working model

that can later be used for real-time location
detection.

The model is represented in the Predictive Model

Mark-up Language – PMML - format.
 Ad-hoc and Sensor Network
Prediction Phase…
The two important input parameters for prediction are:
 Decision rules obtained from the prediction model created during the
learning phase
 Real-time signal strength values collected at a specific location

If Value is in this region If Value is in this region

Predict Room-501_317 Predict Room-501_319
with 56% Accuracy with 90% Accuracy

Simple
prediction model
using two APs
and three rooms.

If Value is in this region If Value is in this region

Predict Room-501_315 Predict Room-501_317
with 88% Accuracy with 80% Accuracy
 Ad-hoc and Sensor Network
Prediction Model

IF 00_06_5A_E0_0D_FA < -74,00 and 00_06_5A_80_0D_C9 >=-

87,00 THEN LOCATION in [501.342] with accuracy 1,0000

IF 00_06_5A_E0_0D_FA < -74,00 and 00_06_5A_80_0D_C9 < -

87,00 and 00_06_5A_60_0D_C6 < -68,50 and 00_06_5A_20_0D_DB
< -77,50 and 00_06_5A_80_0C_BD >=-73,50 and
00_06_5A_C0_0D_D7 >=-92,50 and 00_06_5A_E0_0D_D7 < -85,00
THEN LOCATION in [501.329] with accuracy 0,9877

IF 00_06_5A_E0_0D_FA < -74,00 and 00_06_5A_80_0D_C9 < -

87,00 and 00_06_5A_60_0D_C6 < -68,50 and 00_06_5A_20_0D_DB
< -77,50 and 00_06_5A_80_0C_BD >=-73,50 and
00_06_5A_C0_0D_D7 >=-92,50 and 00_06_5A_E0_0D_D7 >=-85,00
THEN LOCATION in [501.210] with accuracy 1,0000
Sample rules generated as a
prediction model
 Ad-hoc and Sensor Network
Prediction Model…

Using the Principal Component Analysis (PCA) algorithm,

projection of multidimensional data from all visible APIs into 2
dimensions space: Clear color grouping shows that the data is
well separable.