Table of Contents

Experiments and Considerations on
Reaction-Diffusion based Pattern Generation
in a Wireless Sensor Network
t2pWSN2007 Workshop
June 18, 2007Helsinki
Katsuya Hyodo,Hyodo, Naoki Wakamiya, Etsushi Nakaguchi,Nakaguchi, Masayuki Murata
Graduate School of Information Science and Technology, Osaka University, Japan1

Motivation

2

Reaction-Diffusion based Mechanism

3

Experiments

4

Conclusion and Future Work

Yuki Kubo, Kentaro Yanagihara
Corporate Research & Development Center, Oki Electric Industry Co.,Ltd,Co.,Ltd, Japan

6/18/2007

Requirements of WSNs

Focusing on Reaction-Diffusion Equation– A large number of sensor nodes– Random or unplanned deployment– Dynamic topology changes– Model of a biological system– Autonomous pattern generation mechanism• Requirements of WSNs

Pattern generation on a sensor network– Scalable to the size of a network– Robust to failures of sensor nodes– Adaptive to changing topology and changes in wirelesscommunication environment

Autonomous control based on patterns– Clustering, routing, scheduling, and topology control

Fully-distributed and self-organizing control
These features can be found in biological systems

t2pWSN2007 Workshop2Approach and Main Contribution• Difficulty of centralized control in WSN

6/18/2007

t2pWSN2007 Workshop• There have been some proposals
3

Approach and Main Contribution

6/18/2007

t2pWSN2007 Workshop

4

ReactionReaction-Diffusion based Mechanism

Focusing on Reaction-Diffusion Equation– Model of a biological system– Autonomous pattern generation mechanism

1

Motivation

But, is it really possible or efficientto generateon
a patterna WSN?
Pattern generationa sensoronnetwork

2

Reaction-Diffusion based Mechanism

3

Experiments

4

Conclusion and Future Work

Autonomous control based on patterns– Clustering, routing, scheduling, and topology control
Main contribution• Therehave beenof
someproposals
We show
the applicability
reaction-diffusion
equation
to wireless sensor networks
6/18/2007

t2pWSN2007 Workshop

56/18/2007

t2pWSN2007 Workshop

61

ReactionReaction-Diffusion Equation

Pattern Generation with ReactionReaction-Diffusion• Mathematical model of pattern generation on
the surface of body of fishes and mammals• Pattern emerges through local interactions using local
information among neighboring cells• Each cell has two morphogens (chemicals):
activator and inhibitor• Two interacting parts:Zebra

Emperor Angelfish

6/18/2007– Diffusion:
Cell
Long-ranged, slowly
propagating diffusion
Activatorof morphogens
Inhibitor– Reaction:
Local reaction to morphogen
concentrations

7Condition for Pattern Generation

6/18/20071– Morphogens move only among neighboring cells– Inhibitor diffuses faster than activator– Positive feedback and negative feedback among morphogens
Reaction-diffusion equation
resolve

Activatorurestrainactivate
resolve

activate∂u= F (u , v ) + Du ∇ 2u∂t

activate

Reaction
termv

82HighActivator
Inhibitor

peak

Concentration

Lowactivatex

3x4

Peak : Kept
Activator
Inhibitor

Diffusionterm∂v= G (u , v ) + Dv ∇ 2 v∂tInhibitor

t2pWSN2007 Workshop

Pattern Generation Mechanism• Behavior of morphogens

activateReaction• Color of each cell is decided based on the concentrationof activator

Leopardt2pWSN2007 Workshop

Diffusion

Threshold
Spot

StripeMazex

Farther regions : Restrained
6/18/2007

t2pWSN2007 Workshop

96/18/2007

t2pWSN2007 Workshop

Applying Biological System to WSN

Pattern Generation in WSN• In Biological Systems• Procedure for each nodeContinuous reaction-diffusion equation∂u= F (u , v) + Du ∇ 2u∂t∂v
= G (u , v) + Dv ∇ 2 v∂tDiffusion

CellActivator
Inhibitor• In WSN
Sensor node

Reaction
Diffusion

utn + ute + uts + utw − 4ut}Δh2
vtn + vte + vts + vtw − 4vt
vt +1 = vt − Δt{G(ut , vt ) + Dv}
Δh2

Exchange concentrations of two morphogens

2Calculate discrete reaction-diffusion equation

3

Perform an action based on morphogens

1. Exchange the information

Communicates only withneighboring nodes

2. Calculate the equationNode

3. Turn on the LED

Reaction
6/18/2007

1Discrete reaction-diffusion equation
ut +1 = ut − Δt{F(ut , vt ) + Du

Activator : 1Inhibitor : 2

10

t2pWSN2007 Workshop

116/18/2007

t2pWSN2007 Workshop

122Methods for Faster Pattern Generation

Experiments• Normal method– Large energy consumption• A large number of communication• A large number of calculation

Energy-efficiency is important for WSNs

• Methods to accelerate pattern generation– Method (a)• Enlarge discrete step Δt

utn + ute + uts + utw − 4ut}
Δh 2vtn + vte + vts + vtw − 4vt}
vt +1 = vt − Δt{G(ut , vt ) + Dv
Δh 2

ut +1 = ut − Δt{F (ut , vt ) + Du

1Motivation

2

Reaction-Diffusion based Mechanism

3Experiments

4

Conclusion and Future Work– Method (b)• Calculate K iterations of reaction-diffusion equation at each step
6/18/2007

t2pWSN2007 Workshop

13

6/18/2007

Simulation Experiments

t2pWSN2007 Workshop

14

Simulation Experiment: Result of Method (a)Simulation Settings• 5 × 5 = 25 nodes• Synchronized nodes– Exchange the information about morphogens concentrations
at the same time
• No information loss / Random information loss
– Calculate the reaction-diffusion equation at the same time

Nodenumber of communication and calculation

Evaluation Metrics• Communication and calculation time until concentrationsof morphogens converge• Probability of successful pattern generation
against information loss
6/18/2007

t2pWSN2007 Workshop

15• Method (a) : Enlarge discrete step Δt• Decrease in number of communication and calculation• Mathematical upper limit of Δt = 4.35
– If Δt > 4.35, the patterns do not converge
6/18/2007

Simulation Experiment: Result of Method (b)Generated pattern

t2pWSN2007 Workshop

16

Simulation Results with Information LossNormal: Δt = 0.1, K = 1
Method (a) : Δt = 1, K = 1
Method (b) : Δt = 0.1, K =10
Probability of successful pattern generation:
The rate of simulation runs which reach the samestable pattern as without loss of information• Method (b) :Calculate equation K times per information exchange• Decrease in number of communication 1 Information exchange• No decrease in number of calculation
Calculate2
Reaction-Diffusion• Upper limit of K : 130– If K > 130, the patterns do not converge
6/18/2007

t2pWSN2007 Workshop

K-1

3 Take action
17

Probability of information loss:
The rate of information which is not received.

• Without acceleration method– Tolerate up to 23% information loss

• With acceleration method– Tolerate up to 4% information loss
6/18/2007

t2pWSN2007 Workshop

183

Practical Experiments

Practical Experiment Result
Practical ExperimentSensor node

Simulation Experiment

Broadcastcommunication
IEEE 802.15.4
non-beacon mode

Asynchronous
broadcasting andcalculation• Broadcast interval T = 1.4 [sec]• Using Method (a) : Discrete step Δt = 1
6/18/2007

t2pWSN2007 Workshop

Generated pattern

LED（RED）ON ：Concentration of activator is highWhite square ：Concentration of activator is highLED（RED）OFF：
Concentration of activator is low

Black square :Concentration of activator is low

LED（GREEN） :Broadcast the information
19

Conclusion and Future Work

6/18/2007

t2pWSN2007 Workshop

20

Conclusion and Future Work• Conclusion

1

Motivation

2

Reaction-Diffusion based Mechanism

3

Experiments

4

Conclusion and Future Work

6/18/2007

t2pWSN2007 Workshop– We show the applicability of reaction-diffusion equation to awireless sensor network• We can accelerate the pattern generation to achieve energyefficiency• The nodes can make the pattern in actual environment withsome loss of information• Future Work– Evaluate scalability for a large number of nodes– Random node layout, dynamic changes in topology– Mobile nodes– Much faster pattern generation– Target application using patterns
21

6/18/2007

t2pWSN2007 Workshop

22

Thank you.

6/18/2007

t2pWSN2007 Workshop

234