Energy Efficient Routing Algorithms for Application to
Download
Report
Transcript Energy Efficient Routing Algorithms for Application to
Energy Efficient Routing Algorithms
for Application to Agro-Food
Wireless Sensor Networks
Francesco Chiti*, Andrea De Cristofaro*, Romano Fantacci *, Daniele Tarchi*,
Giovanni Collodi§, Gianni Giorgetti*, Antonio Manes▲
*Dipartimento di Elettronica e Telecomunicazioni,
▲Dipartimento di Energetica, §Consorzio MIDRA
Università di Firenze -Via di S. Marta, 3 - 50139 Firenze, Italy
[email protected], [email protected], [email protected],
[email protected], [email protected], [email protected]
COST 289 7th MCM - München March, 7-8 2005
1/24
Contents
1. WSN features
2. Routing protocols
3. Proposed approach
4. Performance analysis
5. Conclusions
COST 289 7th MCM - München March, 7-8 2005
2/24
Research involvements
“GoodFood” EU Integrated Project
• Development of novel solutions for the safety and quality assurance, along the
food chain within the agro-food industry.
• Work Package 7 aims at investigating integrated solutions according to the AmI
concepts, allowing full interconnection and communication of multi-sensing
systems.
“NEWCOM” EU NoE
Project A is addressed to “Ad Hoc and Sensor networks” with regards to:
Cross-layer design of sensor networks;
Simulation models and architectures for cross-layered sensor networks.
COST 289 7th MCM - München March, 7-8 2005
3/24
1. WSN features
Definition
Wireless Sensor Network (WSN) is composed of a large number of sensor
nodes (N) that are densely deployed either inside the investigated
phenomenon or very close to it.
N
N
IPvx
Task Mng
Satellite
N
N
Gateway
N
N
2G/3G/
4G
N
N
N
Gateway
N
N
N
N
N
COST 289 7th MCM - München March, 7-8 2005
4/24
1. WSN features
WSN Applications
• Military, Environmental, Health, Home, Space Exploration, Chemical
Processing, Disaster Relief
Sensor types
• Seismic, Low sampling rate magnetic, Thermal, Visual, Infrared, Acoustic,
Radar
Sensor tasks
• Temperature, Humidity, Lightning Condition, Pressure, Soil Makeup,
Noise Levels
• Vehicular, Movement, Presence or Absence of certain types of objects,
Mechanical stress levels on attached Objects, current characteristics
(Speed, Direction, Size) of an object
COST 289 7th MCM - München March, 7-8 2005
5/24
1. WSN features
WSN implementation (HW & SW)
Functional blocks
Network Nodes
Location Finding
Sensor ADC
Mobilizer
Processor Memory
Transceiver
Gateway
Power Unit
COST 289 7th MCM - München March, 7-8 2005
6/24
1. WSN features
Multi-Hop WSN
Theorem (Stojmenovic, Xu Lin)
Let be the source and the gateway at distance d and the
needed transmitted power satisfies:
ud ad c
This is minimized if:
1
c
d
1
a
1
2
Otherwise, the overall requested energy can be minimized by
choosing equally spaced n-1 relay nodes such that n is the
integer closer to:
1
a 1
d
c
COST 289 7th MCM - München March, 7-8 2005
7/24
1. WSN features
Multi-Hop WSN
Communication paradigm
Source
relay
relay
Gateway
COST 289 7th MCM - München March, 7-8 2005
8/24
1. WSN features
Multi-Hop WSN
Flexibility:
Adaptability
Re-configurability
Robustness
Scalability
Power saving
Untethered
3
1
Dummy node
2
6
No nw planning
•
•
•
0
Energy-awareness
•
•
WSN
GATEWAY
4
Sensor Node
5
Random deployment
Self-organization
Re-configuration
Cooperative approach
•
•
Distributed procedures
Data processing
COST 289 7th MCM - München March, 7-8 2005
9/24
2. Routing protocols
Protocol design
Ad Hoc protocol are often unsuitable because:
• Number of sensor nodes can be several order of magnitude higher
• Sensor nodes are densely deployed and are prone to failures
• The topology of a sensor network changes very frequently due to node
mobility and node failure
• Sensor nodes are power, computational capacities and memory limited
• May not have global ID like IP address
• Need tight integration with sensing tasks
Specific cross-layer protocols design with an across layers information
passing and functionalities adaptation to channel and load variations
COST 289 7th MCM - München March, 7-8 2005
10/24
2. Routing protocols
Network layer
This layer is in charge of discovering the best path between a couple
of nodes (Sender and Destination), relaying on the following
characteristics:
•
Sensor networks are mostly data centric
•
An ideal sensor network has attribute based addressing
and location awareness
•
Data aggregation may be joined with a collaborative effort
•
Power efficiency is always a key factor
Application
Transport
Network
LLC
MAC
Physical
COST 289 7th MCM - München March, 7-8 2005
11/24
2. Routing protocols
Network layer
Metrics considered to develop energy efficient routing algorithms:
•
Power Available (PA) at each node
•
Energy () needed to send a packet over a link
Resorting to these, there 4 possible approaches to choose the
proper path:
Maximum PA Route (PAs summation)
Minimum Energy Route ( summation)
Minimum Hop Route (number of hops)
Maximum Minimum PA Route (minimum of maximum PA)
COST 289 7th MCM - München March, 7-8 2005
12/24
2. Routing protocols
Network layer
Flooding
Each node forwards the packets to all the neighbor
nodes within its transmission range
PROs
CONs
Simple implementation
No table updating
No neighbor nodes
discovering
Scalability
Implosion and goodput
decreasing
Duplicate packets
No available resource
knowledge
COST 289 7th MCM - München March, 7-8 2005
13/24
2. Routing protocols
Network layer
Gossiping
Each node sends a packet only to one neighbor node
chosen according to a suited criterion (random or metric
based)
PROs
CONs
Scalability
Long convergence transient
time
Adaptability
Possible presence of loops
Modularity
Graceful performance
degradation
Packet loss if TTL expires
Signaling overhead
No implosion
COST 289 7th MCM - München March, 7-8 2005
14/24
3.
Proposed approach
Network layer
Dynamic table driven and link state
Each idle node periodically broadcasts an HELLO message with
fields:
•
SOURCEID: unique hardware identifier;
•
NUMHOPS: number of hops to reach the sink;
•
COORDINATES: location with respect to the gateway;
•
AVAILABLE ENERGY: i.e., the energy that is still available
to transmit and process the packets.
COST 289 7th MCM - München March, 7-8 2005
15/24
3.
Proposed approach
Network layer
an HELLO reception makes the routing table to be updated and,
hence, to select the best next hop by means of the following
procedure:
i.
entries with minimum NUMHOPS to the sink are chosen;
ii.
among the remaining nodes those with higher AVAILABLE
ENERGY are the candidates;
iii.
finally, the node minimizing the Euclidean distance to the
gateway is selected;
COST 289 7th MCM - München March, 7-8 2005
16/24
3.
Proposed approach
Protocol behavior
Dynamic Gossiping
Packet
Optimum
next hop selection
HELLOforwarding
broadcasting
COST 289 7th MCM - München March, 7-8 2005
17/24
4.
Performance analysis
Application scenario
Field-trial of the University of Florence’s Montepaldi farm for the Wine
Chain monitoring (wine production and ageing chain steps)
Sensed parameters: air, ground, plants (leaf temperature, stem growth, xylem flux and
pathogenic diseases), fermentation and ageing issues
1
2
2
1
1
3
2
3
1
2
3
3
COST 289 7th MCM - München March, 7-8 2005
18/24
4.
Performance analysis
Simulation results
Reference metrics:
power consumption or, equivalently node lifetime especially for
the most solicited nodes (connectivity);
end-to-end throughput or delivering efficiency;
end-to-end packet delivering delay.
Compared approaches:
basic flooding routing scheme;
a static gossiping: proactive link state evaluation;
proposed dynamic gossiping.
Utilization of Network Protocol Simulator (NePSing): a C++
framework for modeling time-discrete, asynchronous systems
[“the NePSing Project,” 2004. [Online]. Available: http://nepsing.sourceforge.net]
COST 289 7th MCM - München March, 7-8 2005
19/24
4.
Performance analysis
Power consumption
6X6
9X4
12000
12000
8000
4000
8000
Flooding
Random G
Proposed G
UE
UE
Flooding
Random G
Proposed G
4000
0
0
1
2
3
4
5
6
7
8
9
10
1
2
3
4
time [slot]
5
6
7
8
9
10
time [slot]
remarkable gain of the dynamic gossiping vs flooding scheme;
same behavior of the static and the dynamic gossiping;
Increasing signaling overhead (slightly worse performance) especially in an
asymmetric network topology, i.e., in a rectangular-wise grid if compared with a
square-wise.
COST 289 7th MCM - München March, 7-8 2005
20/24
4.
Performance analysis
Delivering efficiency
6X6
9X4
1
Flooding
Random G
Proposed G
0,5
Delivery efficiency
Delivery efficiency
1
0
Flooding
Random G
Proposed G
0,5
0
0
1
2
3
4
5
6
7
8
9
10 11
time [slot]
0
1
2
3
4
5
6
7
8
9
10 11
time [slot]
increasing end-to-end packet delivering of dynamic vs static gossiping;
worse delivering efficiency (throughput).
COST 289 7th MCM - München March, 7-8 2005
21/24
4.
Performance analysis
Network connectivity
Static gossiping
Dynamic gossiping
Topology
Node 1
Node 2
Node 3
Topology
Node 1
Node 2
Node 3
6×6
105
35
105
6×6
82
76
85
9×4
42
21
182
9×4
86
70
89
50% reduction of power consumption for the most solicited nodes (1,2,3);
lesser spatial variance of energy wasting;
lesser dependency with the topology.
COST 289 7th MCM - München March, 7-8 2005
22/24
5.
Conlusions
Pervasive use of AmI concepts in agriculture, relying on highlyintegrated WSNs to create a sensitive and responsive environment;
Proposal of an energy efficient dynamic routing protocol;
Performance analysis:
•
signaling overhead, delay and throughput;
•
Power consumption;
•
Network life-time (connectivity).
Further developments:
•
On-board implementation and testing;
•
Cross-layer integration with energy efficient Link Layer schemes (e.g.,
SMAC);
•
Management of differentiated services.
Francesco Chiti, Andrea De Cristofaro, Romano Fantacci, Daniele Tarchi, Giovanni Collodi, Gianni
Giorgetti and Antonio Manes, “Energy Efficient Routing Algorithms for Application to Agro-Food
Wireless Sensor Networks” in Proc. of IEEE ICC 2005.
COST 289 7th MCM - München March, 7-8 2005
23/24
Energy Efficient Routing Algorithms
for Application to Agro-Food
Wireless Sensor Networks
Francesco Chiti*, Andrea De Cristofaro*, Romano Fantacci *, Daniele Tarchi*,
Giovanni Collodi§, Gianni Giorgetti*, Antonio Manes▲
*Dipartimento di Elettronica e Telecomunicazioni,
▲Dipartimento di Energetica, §Consorzio MIDRA
Università di Firenze -Via di S. Marta, 3 - 50139 Firenze, Italy
[email protected], [email protected], [email protected],
[email protected], [email protected], [email protected]
COST 289 7th MCM - München March, 7-8 2005
24/24
2. Routing protocols
Network layer
Quality of Service oriented routing protocols
•
Routes based on QoS requirements without periodic table
updating (no need for routing tables )
•
Flexibile, robust and modular
•
One-to-one, many-to-one, one-to-many, and many-tomany communications
Types of Streams
Type 1: Time critical and loss sensitive
Type 2: time critical but not loss sensitive data
Type 3: loss sensitive data that is not time critical
Type 4: neither time critical nor loss sensitive
COST 289 7th MCM - München March, 7-8 2005
25/24