Timely and Energy Efficient
Node Discovery
in WSNs with Mobile Elements
Giuseppe Anastasi
Pervasive Computing & Networking Lab (PerLab)
Dept. of Information Engineering, University of Pisa
E-mail: giuseppe.anastasi@iet.unipi.it
Website: www.iet.unipi.it/~anastasi/
PerLabShenzhen Institute of Advanced Technology
Chinese Academy of Sciences, April 7, 20111

Timely and Energy Efficient
Node Discovery
in WSNs with Mobile Elements
Based on Joint work withMario Di Francesco, University of Texas, Arlington
Sajal K. Das, University of Texas, Arlington
Mohan Kumar, University of Texas, Arlington
Kunal Shah, University of Texas, ArlingtonMarco Conti, IIT-CNR, Italy
Koteswararao Kondepu, IMT Institute for Advanced Studies, Lucca

8

Overview
PerLab WSNs with MEs
 ME Discovery
 Classification of proposed approaches

 Adaptive Discovery Scheme Resource-Aware Data Accumulation (RADA) Hierarchical Discovery Scheme Dual Beacon Discovery (2BD)

Timely & Energy-Efficient Node Discovery in WSNs with Mobile Elements

99

Static Sensor Networks
PerLabAll sensor nodes have a fixed location
What about introducing mobility?
Timely & Energy-Efficient Node Discovery in WSNs with Mobile Elements

1010

WSNs with Mobile Elements
PerLabAdvantages
 Connectivity
 A sparse sensor network may be a feasible solution for a large
number of applications.

 Cost Reduced number of sensor nodes  reduced costs

 Reliability
 Single-hop communication instead of multi-hop communication
 Reduced contentions/collisions and message losses Energy Efficiency
 Mobile nodes can help reducing the funneling effectTimely & Energy-Efficient Node Discovery in WSNs with Mobile Elements

1111

WSNs with Mobile Elements
PerLabChallenges
 Contact Detection
 Timely and energy efficient contact detection is required Mobility-aware Power Management
 The mobility pattern should be exploited to optimize energyefficiency

 Reliable Data Transfers
 Since contacts may be scarce and short, the (reliable) datatransfer phase must be very efficient Mobility Control
 If node mobility can be controlled, this should be exploited tooptimize the system
Timely & Energy-Efficient Node Discovery in WSNs with Mobile Elements

1212

Components of a WSN-MEPerLab

 Regular Sensor Nodes Sensing (source of information)
 Data Forwarding May be Static or Mobile Sink Nodes (Base Stations) Destination of Information
 Collect information directly o through intermediate nodes
 May be Static or Mobile

 Special Support Nodes
 Neither source nor destination of information
 Perform a specific task (e.g., data relaying) Typically mobile
Timely & Energy-Efficient Node Discovery in WSNs with Mobile Elements

1313

Mobile Elements
PerLab

 Reloctable Nodes
 Limited mobility
 Do not carry data while moving
 Typically used in dense networks

 Mobile Data Collectors
 Mobile Sinks
 Mobile Relays

 Mobile Peers
 Regular mobile nodes

Timely & Energy-Efficient Node Discovery in WSNs with Mobile Elements1414

Reloctable Nodes
PerLabTimely & Energy-Efficient Node Discovery in WSNs with Mobile Elements

1515

Mobile Sinks
PerLabTimely & Energy-Efficient Node Discovery in WSNs with Mobile Elements

1616

Mobile Relays
PerLabTimely & Energy-Efficient Node Discovery in WSNs with Mobile Elements

1717

Mobile Peers
PerLabTimely & Energy-Efficient Node Discovery in WSNs with Mobile Elements

1818

Data Collection in WSN-ME
PerLabTimely & Energy-Efficient Node Discovery in WSNs with Mobile Elements

19

19

Terminology
PerLab Contact Happens when two or more nodes are in the mutualcommunication range Discovery
 The process that allows a node to discover a contact, i.e., thepresence of a ME in the communication range Data Transfer
 Message exchange between nodes that are in contact

 Residual Contact Time Amount of time actually available for data transfer

Timely & Energy-Efficient Node Discovery in WSNs with Mobile Elements

2020

Impact of Node Mobility
PerLabMobility

Controllable

Uncontrollable

Robot

Deterministic

RandomShuttlePeople, Animals,Cars, Buses, Cabs…

Timely & Energy-Efficient Node Discovery in WSNs with Mobile Elements

2121

Approaches to Data Collection
PerLabM. Di Francesco, S. Das, G. Anastasi, Data Collection in Wireless Sensor Networks withMobile Elements: A Survey, ACM Transactions on Sensor Networks, to appear (2012),
Available at http://info.iet.unipi.it/~anastasi/pubblications.html
Timely & Energy-Efficient Node Discovery in WSNs with Mobile Elements

22

22

Mobile Element Discovery

How to miss the minimum number contacts
while
consuming the minimum amount of energy?

23

Ideal Scenario
PerLabME

SensorNodeTimely & Energy-Efficient Node Discovery in WSNs with Mobile Elements2424

In practicePerLab ME arrival times are typically not known inadvance Sensors nodes cannot be always active
 Low duty cycle δ to save energy Discovery Protocol
 Strictly related with power management

Timely & Energy-Efficient Node Discovery in WSNs with Mobile Elements2525

Approaches to ME DiscoveryPerLab Schedule Rendez-vous Sensor node and ME agree on the visit time (at least with someapproximation)
 Simple to implement and Energy Efficient Synchronization required Not applicable in some contexts

 On demand The ME wakes up the static node when it is nearby
 Radio triggered activation
 Dual Radio Special hardware required

Timely & Energy-Efficient Node Discovery in WSNs with Mobile Elements

2626

Approaches to ME Disciovery
PerLab Asynchronous Periodic listening

Timely & Energy-Efficient Node Discovery in WSNs with Mobile Elements

2727

Periodic Listening
PerLabTON= TB + TD
δ = TON/(TON + TOFF)
Timely & Energy-Efficient Node Discovery in WSNs with Mobile Elements

2828

Classification of Periodic Listening Schemes
PerLab Fixed Schemes Both the beacon period and the sensor node’s duty
cycle are fixed over time Adaptive Schemes
 The beacon time and/or sensor node’s duty cycle are
dynamically adapted Hierarchical Schemes Two different operation modes for sensor nodes
 Low-power mode (most of the time) High-power mode (when the ME is nearby) Typically require two different communication channels
Timely & Energy-Efficient Node Discovery in WSNs with Mobile Elements

2929

Fixed SchemesPerLab Fixed Beacon Period Fixed Sensor’s Duty Cycle (δ)
 A low duty cycle saves energy, but contacts may be missed A high duty cycle increases the % of detected contacts, butdecreases the sensor’s lifetime

 Key Question Which is the optimal duty cycle that allows to detect all
contacts with the minimum energy expenditure?
 The optimal duty cycle depends on a number of factorsthat are difficult (if not impossible) to know in advance.
G. Anastasi, M. Conti, M. Di Francesco, Reliable and Energy-efficient Data Collection in Sparse Sensor
Networks with Mobile Elements, Performance Evaluation, Vol. 66, N. 12, December 2009.
Timely & Energy-Efficient Node Discovery in WSNs with Mobile Elements

3030

Fixed SchemesPerLab Fixed approach Fixed Beacon Period Fixed Sensor’s Duty Cycle [Mat05] [Jai06]
 A low duty cycle saves energy, but contacts may be missed A high duty cycle increases the % of detected contacts, butdecreases the sensor’s lifetime

This approach is quite inefficient, especially whensensor nodes spend a long time in the discovery phase[Mat05] R. Mathew, M. Younis, S. Elsharkawy Energy-Efficient Bootstrapping Protocol for WirelessSensor Network, Innovations in Systems and Software Engineering, Vol. 1, No 2, Sept. 2005
[Jai06] S. Jain, R. Shah, W. Brunette, G. Borriello, and S. Roy, Exploiting Mobility for Energy Efficient Data
Collection in Wireless Sensor Networks, Mobile Networks and Applications, Vol. 11, No. 3, June 2006.
Timely & Energy-Efficient Node Discovery in WSNs with Mobile Elements

3131

Adaptive Beacon RatePerLab Reference Scenario
 All sensor nodes are mobile Can be easily adapted to a scenario where sensor
nodes are static and data collection is though MEs

 Basic idea
 Adaptive beacon emission rate Time is divided in slots (1-hour duration)
 For each time slot the expected contact probability is derived
and updated dynamically based on the past history The beacon emission rate is varied accordingly Based on reinforcement learning
V. Dyo, C. Mascolo, Efficient Node Discovery in Mobile Wireless Sensor Networks, Proceedings DCOSS
2008, LNCS, vol. 5067. Springer, Heidelberg (2008)
Timely & Energy-Efficient Node Discovery in WSNs with Mobile Elements

3232

Adaptive Data Collection (RADA)
PerLab Reference Scenario
 Static Sensor Nodes (with energy limitations) MEs are resource-rich devices

 Basic ideas
 Fixed (Periodic) Beacon Emission by ME Sensor’s wake-up period (duty cycle) is dynamically adjusted
 Based on DIRL framework

 DIRL framework Based on Q-learning Autonomous and adaptive resource management
 suitable to sparse WSNs
M. Di Francesco, K. Shah, M. Kumar, G. Anastasi, An Adaptive Strategy for Energy Efficient Data Collection inSparse Wireless Sensor Networks, Proc. European Conference on Wireless Sensor Systems (EWSN 2010),
Coimbra, Portugal, February 17-19, 2010.
Timely & Energy-Efficient Node Discovery in WSNs with Mobile Elements3333

DIRL framework
PerLab Set of tasks to be executed
 Applicability predicates Task priority

 Set of states
 State representation includes system and application variables

 Utility Lookup Table: Q(s, t) Q(s,t) gives the long-term utility of executing task t in state s

 Exploration/Exploitation strategy
 Exploration with probability ε A random task is executed

 Exploitation with probability 1−ε The best task, according to Q-values, is selected
K. Shah, M. Kumar, Distributed Independent Reinforcement Learning (DIRL) Approach to Resource
Management in Wireless Sensor Networks, Proc. IEEE International Conference on Mobile Adhoc and Sensor
Systems (MASS07), Pisa, Italy, October 2007
Timely & Energy-Efficient Node Discovery in WSNs with Mobile Elements

3434

DIRL Algorithm
PerLabQ(s,t)= (1−α)Q(s,t)+α(r+γe(s’))

K. Shah, M. Kumar, Distributed Independent Reinforcement Learning (DIRL) Approach to Resource
Management in Wireless Sensor Networks, Proc. IEEE International Conference on Mobile Adhoc and Sensor
Systems (MASS07), Pisa, Italy, October 2007
Timely & Energy-Efficient Node Discovery in WSNs with Mobile Elements

3535

Resource-Aware Data Accumulation (RADA)PerLab Discovery tasks
 High duty-cycle (HDC):
 Low duty-cycle (LDC): Very low duty-cycle (VLDC):

δ=δmaxδ= 0.5 δmax
δ= 0.1 δmax

(δ=5%)(δ=2.5%)(δ=0.5%)

 Reward Function
 For any task t
 r=expected_price–energy_spent
 r=–energy_spent

if contact is detected
if contact is not detected Time Domains (TDs) Time is split in a number of time intervals (Time Domains)
 Each task is executed for a TD
 TDs are part of the state characterization
M. Di Francesco, K. Shah, M. Kumar, G. Anastasi, An Adaptive Strategy for Energy Efficient Data Collection inSparse Wireless Sensor Networks, Proc. European Conference on Wireless Sensor Systems (EWSN 2010),Coimbra, Portugal, February 17-19, 2010.
Timely & Energy-Efficient Node Discovery in WSNs with Mobile Elements

3636

ADC StrategyPerLab Mobility-aware exploration policy
 ε=εmin+max(0, k(cmax-c)/cmax)
 cmax= maximum number detected contacts
 c= current number detected contacts
 k= descending rate In our experiments:

 εmax= 0.3
 εmin= 0.1

Timely & Energy-Efficient Node Discovery in WSNs with Mobile Elements

3737

Simulation Parameter Values
PerLabParameterValueParameter

Min Exploration Probability (εmin)

0.1

Beacon Duration

Max Exploration Probability (εmax)

0.3

Window Size (Comm. Protocol)

16Descending Rate (k)0.2

Lost Contact Threshold (Nack)

5

Max Number of Contacts (cmax)

10Message Payload Size

24 bytes

Time Domain duration

100 s

Frame Size

36 bytes

Message Generation Interval

10 sRadio Transmit Power (0 dBm)

49.5 mW

Expected Price Multiplier

10

Radio Receive/Idle Power28.8 mW

Beacon Emission Period

100 msRadio Sleep Power0.6 µW

Timely & Energy-Efficient Node Discovery in WSNs with Mobile Elements

Value
10 ms3838

Other Discovery Strategies
PerLab Random At each step the sensor node executes a random task

 SORA (Self-Organizing Resource Allocation)
 SORA-based adaptive discovery Heuristic strategy based on reinforcement learning Does not consider any state-based learning Oracle Assumes a complete knowledge of MDC mobility

Timely & Energy-Efficient Node Discovery in WSNs with Mobile Elements3939

Analysis in Stationary Conditions
PerLab Discovery Ratio
 % of Detected Contacts

Timely & Energy-Efficient Node Discovery in WSNs with Mobile Elements

4040

Analysis in Stationary Conditions
PerLab Activity Ratio Average Duty Cycle in Discovery State

Timely & Energy-Efficient Node Discovery in WSNs with Mobile Elements

4141

Limits of Adaptive Schemes
PerLab The duty cycle id adjusted at the beginning ofeach time slots
 Based on the estimated contact probability or longterm reward

 If the time slot is large the sensor node may
remain at a high duty cycle for a long time This results in energy wastage

Timely & Energy-Efficient Node Discovery in WSNs with Mobile Elements

4242

Hierarchical Discovery
PerLab Radio Hierarchy [Per05]
 Scenario : Mobile opportunistic network of handheld devices
 Multiple-radio strategy
 Higher-level radio for data exchange, lower-level radio fordiscovery– Bluetooth and WiFi
– Mote and WiFi

 The lower-level radio is used to discover, configure and activate
the higher-level radio– Bluetooth used to discover a nearby WiFi Access Point and configure theWiFi interface

This proposal refers to opportunistic networks of handeld devices
And requires multiple radios[Per05] T. Pering, V. Raghunathan, R. Want, Exploiting Radio Hierarchies for Power-Efficient WirelessDevice Discovery and Connection Setup, Proc. International Conference on VLSI Design, 2005
Timely & Energy-Efficient Node Discovery in WSNs with Mobile Elements

4343

Hierarchical Discovery
PerLab Hierarchical Power Management [Jun09]
 Scenario : Opportunistic networks of handheld devices
 Multiple radio’s strategy
 Low- power radio for discovery
 High-power radio for both discovery and data exchange High-power radio is awakened by the low-power radio

This proposal refers to opportunistic networks of handeld devices
And requires multiple radios[Jun09] H. Jun, M. Ammar, M. Corner, E. Zegura, Hierarchical Power Management in Disruption Tolerant
Networks with Traffic-aware Optimization, Computer Communications, Vol. 32 (2009), pp. 1710-1723
Timely & Energy-Efficient Node Discovery in WSNs with Mobile Elements

4444

Hierarchical DiscoveryPerLab Network Interrupts [Bro07]
 Scenario : Sensor Networks (with MEs) Based on two different radio channels
 A primary high-power radio usually in sleep mode
– Used for data communication

 Control Low-power radio always powered on– Used for control messages

 A node can activate the high-power radio of a nearby nodeby sending it a beacon through the low-power radio,
This approach requires multiple radios, which may not be
available in some sensor platforms[Bro07] J. Brown, J. Finney, C. Efstratiou, B. Green,N. Davies, M. Lowton, G. Kortuem, Network Interrupts:
Supporting Delay Sensitive Applications in Low Power Wireless Control Networks, Proc. ACM
Workshop on Challenged Networks (CHANTS 2007), Montreal, Canada, 2007
Timely & Energy-Efficient Node Discovery in WSNs with Mobile Elements

4545

Hierarchical DiscoveryPerLab Dual Beacon Discovery
 Scenario : Sensor Networks with MEs
 Sensor nodes alternate bewee two duty cycles
 Low duty cycle when the ME is far
 High cycle when the ME is nearby

 Based on two different Beacon messages
 Long-Range Beacons Short-Range Beacons

This approach do NOT requires multiple radios, and can thus
be implmeneted on all sensor platforms[Kon11] K. Kondepu, G. Anastasi, M. Conti, Dual-Beacon Mobile-Node Discovery in Sparse WirelessSensor Networks, Proceedings of the IEEE International Symposium on Computers and Communications(ISCC 2011), Corfu, Greece, June 28 – July 1, 2011.
Timely & Energy-Efficient Node Discovery in WSNs with Mobile Elements

46

46

Single Beacon Scheme
PerLabTimely & Energy-Efficient Node Discovery in WSNs with Mobile Elements

4747

2BD Protocol
PerLabTimely & Energy-Efficient Node Discovery in WSNs with Mobile Elements

4848

Simulation Setup
PerLab Event-driven simulator implemented for sparse wirelesssensor networks
 Single Sensor Node, Single ME Scenario
 Adopted the disc model for packet loss

Timely & Energy-Efficient Node Discovery in WSNs with Mobile Elements4949

Performance MetricsPerLab Contact Miss Ratio The fraction of potential contacts that are not detected bythe sensor node Residual Contact Ratio The ratio between the average residual contact time andthe nominal contact time Energy Consumption
 The average energy consumed by the sensor node per detectedcontact

Timely & Energy-Efficient Node Discovery in WSNs with Mobile Elements

5050

Simulation Parameter Values
PerLabParameter

Value

Beacon period (TBI)

100 msBeacon duration (TBD)

10 ms

ME Speed

40 Km/hDistance from the sensor nodeDiscovery range (R)15 m{100m, 200m}

Communication range (r)50 mNominal contact time

8.6 sHigh duty cycle δH

3%Transmission power (Ptx) at 0 dBm

52.2 mW

Reception power (Prx)56.4 mW

Timely & Energy-Efficient Node Discovery in WSNs with Mobile Elements

5151

Results
PerLab Contact Miss Ratio, Residual Contact Ratio (r=50m)

Timely & Energy-Efficient Node Discovery in WSNs with Mobile Elements

5252

Results
PerLab Energy consumption

R=200
R=100

Timely & Energy-Efficient Node Discovery in WSNs with Mobile Elements

5353

Results
PerLab ENERGY SAVINGS WITH DUAL BEACON (r=50m)
r=50m)
WaitingTime (s)R=100
δL =0.8%

R=200
δL =0.5%

153060120180
240
300

22.2%

22.2%

33.3%

33.3%

38.5%

46.2%

40.8%

55.1%

42.2%

57.7%

42.6%

58.5%

43.1%

59.5%

Timely & Energy-Efficient Node Discovery in WSNs with Mobile Elements

5454

2BD in Dense Network Scenario
PerLabr

Timely & Energy-Efficient Node Discovery in WSNs with Mobile Elements

5555

References
PerLab

M. Di Francesco, S. Das, G. Anastasi, “Data Collection in Wireless Sensor Networks
with Mobile Elements: A Survey”, ACM Transactions on Sensor Networks, to appear(2012), Available at http://info.iet.unipi.it/~anastasi/pubblications.html

M. Di Francesco, K. Shah, M. Kumar, G. Anastasi, “An Adaptive Strategy for Energyefficient Data Collection in Sparse Wireless Sensor Networks”, Proceedings of theEuropean Conference on Wireless Sensor Networks (EWSN 2010), Coimbra,Portugal, Feb. 17-19, 2010.

K. Shah, M. Di Francesco, G. Anastasi, M. Kumar, “A Framework for Resource
Aware Data Accumulation in Sparse Wireless Sensor Networks”, submitted toComputer Communications.

K. Kondepu, G. Anastasi, M. Conti, “Dual-Beacon Mobile-Node Discovery in Sparse WirelessSensor Networks”, Poceedings of the IEEE International Symposium on Computers andCommunications (ISCC 2011), Corfu, Greece, June 28 – July 1, 2011.

Timely & Energy-Efficient Node Discovery in WSNs with Mobile Elements

56

56

Conclusions
PerLab Mobile Node Discovery in WSN-Mes
 Classification of Discovery Schemes Adaptive Discovery Scheme (RADA) Based on DIRL (Q-learning) Hierarchical Discovery Scheme (2BD)
 Based on two different Beacon messages

Timely & Energy-Efficient Node Discovery in WSNs with Mobile Elements57

57

PerLabThank you!

Timely & Energy-Efficient Node Discovery in WSNs with Mobile Elements

58

58