PROGETTO PATTERN Attività di Ricerca del gruppo di Catania nel I Anno Energy efficient solutions...

PROGETTO PATTERN

Attività di Ricerca del gruppo di Catania nel I Anno

Energy efficient solutions for connectivity and data delivery in self-organizing networks

University of CataniaDipartimento di Ingegneria Informatica e delle Telecomunicazioni

© Laura Galluccio 04

Progetto PATTERN Firenze 12/10/04 2

Outline

Energy efficiency and Timeliness of Neighbor Discovery in Self-Organizing Networks

Integrated MAC/Routing protocol for Geographical Forwarding in Self-Organizing Networks


Energy efficiency and Timeliness of Neighbor

Discovery in Self-Organizing Networks


The ProblemAd hoc and sensor networks: nodes mobility and

failures lead to very dynamic topology

If nodes are able to discover very rapidly…..

……Self-organization can be achieved…..

….but Higher responsiveness is paid in terms of energy consumption!


Scenario

N2

N1

1Nv

R

dN1,N2

2Nv


Scenario

N1

N2


Scenario

• A and B enter each others coverage range they become neighbors

N1

N2t=0


Scenario

• A and B exit each others coverage range they are no longer neighbors

N1

N2

t=


Scenario

N1

N2


Neighborhood Time

Neighborhood time (): time interval during which a pair of nodes are neighbors.

Discovery time (T): time interval necessary for the discovery between two nodes.

Transmit time (TT): time interval necessary for the exchange of the data required by the application.

In case of correct functioning: TT ≤ -T Probability of discovery success (PDS):

probability that the above relationship holds


The Approach

A Trade-off is needed between increasing the PDS and decreasing the energy cost associated to this process.

We derived a Markov analytical framework for evaluating the energy cost of the hunting process which is the process of searching for other nodes in the proximity.

This framework allows the developer to design the hunting process so as to meet the requirements in terms of the energy consumption


211' NNN vvv

cos2'21211

22NNNNN vvvvv

If remains constant in direction and magnitude for a sufficient amount of time:

and

1'Nv

11'/'/2 NNy vSvP

44

1)(

4

1)(

22

22

sR

s

Rsf

sRR

RsF SS


The Hunting Process

DSSIIHFtHS .....,2,1.....,2,1

)()()(

)(HQ

)(H

)(HF

To discover neighbors, a node periodically runs a set of procedures which we call hunting process. The states of this process could be:

• Inquiry: a beacon message is transmitted (I)• Inquiry Scan: a node listens for beacon messages (S)• Doze: no inquiry or scan procedures are executed (D)

If M channels are used for discovery, the hunting process can be described as:

state space state of the hunting process

transition rate matrix steady state array


Neighbor Discovery Process (NDP) Suppose that in t the two nodes N1 and N2 become

neighbors. NDP is the result of the interactions between the 2 hunting processes

)()2(

),()1(

)()(

tH

StH

StP

S )()()( HFx

HF

PF

tPQe

Pt

P )()0(

)()(

)( )2()1(

)0()( H

xHP

otherwise0

)''2σ,''1(σ)'

2σ,'1(σif

)'2

σ,'1

(σ(P)F)2

σ1,

(σ )]2

σ,1

(σ),'2

σ,'1

[(σ

](P)[Q

''1σ'

1σif]''

2σ,'2[σ

])2(H

[Q

''2σ'

2σif]''1σ,'1[σ

])1(H

[Q

)]''2,''1(),'

2,'1[(])([

PQ


Conditions for Discovery

mH

mHH

tItSStSS

)()()(lim )2()1()1(

mHH

tm

H ItSSStS

)()(lim)( )2()2()1(

mHH

tm

H StSSItS

)()(lim)( )2()2()1(

mH

mHH

tStSItSS

)()()(lim )2()1()1(

1.

2.

3.

4.


Probability of discovery and array of discovery rate

MmIandSiftQ

MmSandIiftQ

MmIandSiftQ

MmSandIiftQ

tttP

mmmSH

mmmIH

mmmSH

mmmIH

DISC

,][

,][

,][

,][

),(

21],1[)1(

21],1[)1(

12],2[)2(

12],2[)2(

)()2,1(

MmIandSifQ

MmSandIifQ

MmIandSifQ

MmSandIifQ

mmmSH

mmmIH

mmmSH

mmmIH

DISC

,][

,][

,][

,][

][

21],1[)1(

21],1[)1(

12],2[)2(

12],2[)2(

)]2,1[()(

*)()( )()( DISCP tt overall discovery rate at t


Evolution of the process when nodes do not succeed in discovery

tTtSPt PDISCtT |),()()]([ 21

)()2,1(

)'(

The probability that the state of the pair of neighbors is given that the 2 nodes have not discovered

We derived matrix which is the state transition rate matrix of the process, given that the mobile nodes have not discovered each other. This matrix can be related to Consequently:

),( 21

)(PNODISCQ

)(PQ

tPNODISCQPP

tT e)(

)()( )0(

*)()( )()( DISCPtTtT tt


QoS Parameters

Energy Cost

][)(

1][

)( ][][[ mSH

SCAN

M

mmI

HINQ PWPWc

Pdf of the discovery time T )(1)( tAT ektF

M

mmSmI

PmImS

Pk1

),()(

),()( ][][1

*)(

1

11)(

0

....,1

.,.........1

)0()()( DISC

RL

tRLdtdP

t

tT ttd

e

d

ediagdtA

id eigenvalues of )(PNODISCQ eigenvectors of which is the )(P

NODISCQ

matrix of the transition rates, given that the mobile nodes do not discover each other


PDS in data transfer

TTvs

T

R

SS dsddffsfP)('/

0

2

0 0

)()()(


Cycle Time

The cycle time can be related to the scan, inquiry and doze probabilities.It can be demonstrated that, once the probabilities are set, does not depend on or or .

SP

CycleTv TT

DozeScanInqCycle TTTT


Cycle Time 5. vTwithTvsP CycleCycleS

0Cycle

T

T

T

5Cycle

T

T

T


Case Study

SP

Cycle

T

T

T

We applied the proposed methodology to a relevant case study:

•A single channel system

We derived some design implications on neighbor discovery algorithms and verified that increases as the cost constraint increases and the ratio decreases.


Case Study0,1.

Cycle

TCycleScanS T

TvTwithPvsP

C*=0.3

C*=0.7


Case Study0,1

Cycle

TCycle T

TvT

1vTCycle


Case Study

1vTCycle


Conclusions 1

1. Nodes in self-organizing ad hoc and sensor networks execute the hunting process procedures

2. These procedures imply high energy consumption if a timely discovery occurs

3. A trade-off is needed4. An analytical framework for evaluation of the maximum probability

of discovery success, given some energy constraints, was introduced5. This framework can be used for designing appropriately the

discovery process in a mobile network so as to satisfy the application requirements


Integrated MAC/Routing protocol for Geographical

Forwarding in Self-Organizing Networks


The Problem

In commercial sensor devices different TX power levels are available

This feature can be exploited for reducing energy consumption

We propose a MAC/ROuting protocol which uses this capability

This protocol works with a cross-layer approach, is simple and does not require any location information knowledge

Uses competition to select the most efficient next relay


Prerequisites

P

DRdDRdG RR

),''(),'('','

)'()....'()'(....... 2121 RSRSRSPPP MM

Weighted progress factor (WPF)

Set of power levels and coverage range

R’’

R’ D

)'(1 RS


Protocol FunctioningRouting functionalities

P

DRdDRdG RR

),''(),'('','

)'()....'()'(....... 2121 RSRSRSPPP MM



R’’

R’ D

)'(1 RS

1. To select the next relay node R’ triggers a competition

2. Be R’’ the winner of the competition in the set S1(R’) and GR’R1’’ its WPF

3. If R’ estimates that a higher WPF can be obtained increasing P, a new competition is triggered in the set S2(R’).

4. The procedure is repeated until no better relay nodes can be found

5. When the best relay is identified the information is transmitted


Protocol FunctioningMAC functionalities

P

DRdDRdG RR

),''(),'('','

)'()....'()'(....... 2121 RSRSRSPPP MM



1. Nodes periodically switch ON and OFF to reduce energy consumption

2. Synchronization is not needed

3. A wake up phase is requires for R’ identifying the best relay node in Si(R’)

4. To this purpose R’ transmits several short WAKE-UP messages for a TCycle

5. Then R’ sends a Go MESSAGE which triggers competition among nodes in Si(R’)

6. A node in Si(R’) hearing the WAKE_UP messages calculates its WPF and stays awake waiting for the GO MESSAGE

7. Then upon hearing the GO MESSAGE a node sends randomly back to R’ its WPF so that R’ performs the choice of the best relay in Si(R’)

CycleT

ONT

TXWUON

InWU TTT 2


Questions Analytical Framework

What is the probability that outside the coverage area obtained using , exists at least one node whose WPF is higher than , provided that

Once the probability is known, when it is worth enlarging the coverage area?

If we stop the competition at time t, what is the probability to choose not the best available relay node in the considered coverage area?

?)(i

Mi GG

g

iP


Answer to Question 1

)|()()(1 1}|Pr{ iGga

iM

iM

i eGGgG

)|( iGgaWhere is the nodes’ density and is the area where a node B must be located in order to belong to and have a WPF higher than g.

)'(1 RSi

gP

R

i

i 1

gP

R

i

i 1



11

1)()(

1

/

/ |

)()(1 )|(}|{

ii

iiiM

iM

i

PR

PPG iGGiM

iM

i dgGgfgGGGE

Where is the probability density function which can be evaluated using the previous results as

)|()()(1 | iGG

Ggf Mi

Mi

)|()|( )|(

| )()(1

iGga

iGGGga

dg

deGgf i

Mi

Mi



iPiR

iG MiGARAAiARi dggfgGttGGRSA /

)(,','1 )(}|Pr{1},:)'(Pr{

This represents the probability that a node having a WPF higher than the best available one exists out of and its CONTROL ACK message arrives later than other nodes’ messages.

)'(RSi

gkt

ARA egGt

1}|Pr{ ,'

}Pr{ )()( gG

dg

df M

iMiG


Performance evaluationPolicy for the TX power level choice

Policy 1: TX power levels increase linearlyPolicy 2: TX power levels give a linear increase inPolicy 3: TX power levels give a linear increase in

)'(RSi

iR


Performance evaluationPolicy for the TX power level choice

Average TX power

Average power consumption

Average range


Performance evaluationComparison with other protocols

Average power consumption

Average number of hops


Performance evaluationNumber of packets delivered at destination


Conclusions 2

1. MACRO is an integrated MAC/Routing geocast protocol 2. Convenient in case of strict requirements in terms of energy

efficiency 3. The increase in end-to-end delay can turn into an

advantage in terms of data aggregation4. MACRO greately extends node’s lifetime


Publications

L. Galluccio, A. Leonardi, G. Morabito, S. Palazzo: Tradeoff between Energy-Efficiency and Timeliness of Neighbor Discovery in Self-Organizing Ad Hoc and Sensor Networks. Proc. of HICSS 2005, Big Island, Hawaii, January 2005.

L. Galluccio, A. Leonardi, S. Palazzo: Design Guidelines for Geocast Protocols in Ad Hoc and Sensor Networks. Proc. of Med-Hoc Net 2004, Bodrum, Turkey, June 2004.

L. Galluccio, S. Palazzo: A Taxonomy of Location Management Schemes in Mobile Ad Hoc Networks. To appear in Journal of Communications and Networks.

D. Ferrara, L. Galluccio, A. Leonardi, G. Morabito, S. Palazzo: MACRO: An Integrated MAC/Routing Protocol for Geographical Forwarding in Wireless Sensor Networks. Submitted for Publication.

PROGETTO PATTERN Attività di Ricerca del gruppo di Catania nel I Anno Energy efficient solutions...

Documents

Transcript of PROGETTO PATTERN Attività di Ricerca del gruppo di Catania nel I Anno Energy efficient solutions...