A Traveling Wave based Communication
Mechanism for Wireless Sensor Networks
Yoshiaki Taniguchi, Naoki Wakamiya, Masayuki Murata
Graduate School of Information Science and Technology, Osaka University, Osaka, Japan
Email: {y-tanigu, wakamiya, murata}@ist.osaka-u.ac.jp

Abstract— In this paper, we propose and evaluate a selforganizing communication mechanism for wireless sensor
networks where a large number of sensor nodes are deployed. To accomplish application-oriented periodic communication without any centralized controls, we adopt traveling wave phenomena of a pulse-coupled oscillator modelby regarding sensor nodes as oscillators and emission ofradio signals as firing. We first investigate conditions of aphase-response curve to attain wave-formed firing patterns
regardless of the initial phase of oscillators. We adopt thederived phase-response curve to accomplish the desired formof message propagation through local and mutual interactions among neighboring sensor nodes. Through simulation
experiments, we confirm that our mechanism delivers sensor
information to / from a designated node in a more energyefficient manner than other method, although it takes timeto generate a traveling wave.
Index Terms— sensor network, traveling wave, pulse-coupledoscillator model, communication mechanism

I. I NTRODUCTION
The development of low-cost microsensor equipments
having the capability of wireless communication has
caused sensor network technology to attract the attentionof many researchers and developers. It is possible toobtain information on behavior, condition, and positionof elements in a local or remote region by deploying
a network of battery-powered sensor nodes there. Eachsensor node in such a sensor network has a general
purpose processor with a limited computational capability,a small memory, and a radio transceiver.
A. Motivation
Due to several restrictions including limited battery
capacity, random deployment, and a large number offragile sensor nodes, a communication mechanism should
be energy efficient, adaptive, robust, fully distributed,
and self-organizing. Furthermore, it should be able tohandle various types of communication, i.e., diffusionand gathering, involving the whole network in accordancewith application requirements. For example, a sensor nodeThis paper is based on “A Self-organizing Communication Mechanism using Traveling Wave Phenomena for Wireless Sensor Networks,”
by Yoshiaki Taniguchi, Naoki Wakamiya, and Masayuki Murata, whichappeared in the Proceedings of the 2nd International Workshop on Ad
Hoc, Sensor, and P2P Networks (AHSP 2007), Sedona, USA, March
c 2007 IEEE.
2007. [1] detecting an emergency would distribute the information
over the whole sensor network to alert the other nodes
and make them cooperatively react to the emergency.
On the contrary, a sensor node detecting an uncertain
condition would collect and aggregate sensor informationof the other nodes to have a more precise view of theenvironment by conjecturing from collected information.
Most of communication schemes cannot adopt to dynamically changing application requirements. For example, directed diffusion [2, 3] also considers both typesof communication, i.e., pull and push. In the two-phasepull diffusion, sinks first emit an interest message to findsources. Interest messages are flooded across a network,and matching sources periodically send exploratory data
to the sink along paths that interest messages traversed.
After the initial exploratory data come, the sink chooses
one and reinforces the corresponding paths to sources
so that following data traverse them to the sink withthe smallest latency. The pull-type communication isshown to be appropriate for a case with many sources
and few sinks. On the contrary, in the push diffusion,
sources first send exploratory data to notify possible sinksof the existence of data. The push-type communicationis good for a case with many sinks and few sources.
Although directed diffusion can support two different
application requirements, these mechanisms cannot be
used simultaneously and the mechanism to employ must
be determined in advance taking into account expectedconditions, including the number of sources and sinks andtheir communication frequency.
To answer dynamically changing application requirements, a communication mechanism should handle bothtypes of communication, especially in an autonomous andself-organizing manner. In addition, taking into accountthe insufficient computational capability and memory capacity of inexpensive small sensor nodes, the mechanism
must be as simple as possible. A simple mechanism
can also avoid introducing programming and operational
errors.
B. Overview of Our Mechanism
For this purpose, we adopt a pulse-coupled oscillator(PCO) model based on biological mutual synchronizationsuch as that observed in flashing fireflies [4, 5]. In aΔ(φ)

synchronization

time
traveling wave

2.5
2
1.5
1
0.5
0
-0.5
-1
-1.5

a=0.5
a=1.0
a=-0.5

0

0.2

0.4

0.6

0.8

1

φ

(a) PRC of QIF model ΔQIF
time
firing node

Figure 1. Global synchronization and traveling wave

PCO model, synchronous behavior of a group of oscillators is considered. Each oscillator operates on a timer.
When the phase of the timer reaches one, an oscillator
fires. Oscillators coupled with the firing oscillator are
stimulated and they shift the phase of timers by a small
amount. Through mutual interactions by stimuli among
oscillators, they eventually reach a synchronized behavior.
There are several papers which employ a PCO model
to make sensor nodes operate in synchrony, e.g., clock
synchronization, through a distributed and self-organizing
control mechanism [6-12]. In [11, 12], we proposed a data
gathering scheme which employ synchronized behavior of
a PCO model, and confirmed that it worked in a fullydistributed, self-organizing, robust, adaptive, scalable, andenergy-efficient manner.
In this paper, in contrast to the other works, we focus on
another phenomenon observed in a PCO model. In a PCO
model, it is shown that not only the global synchronization
where all oscillators fire synchronously, but a travelingwave, where oscillators behave synchronously but with
fixed phase difference, appears (Fig. 1) [5]. By adjusting
parameters and functions of a PCO model, we can control
the frequency, form, and direction of a wave. We firstinvestigate conditions of a phase response curve (PRC)with which a wireless sensor network reached a preferred
phase-lock condition where the phase differences among
sensor nodes are kept constant from arbitrary settingsof the initial phase of sensor nodes. Next, we propose
a self-organizing communication mechanism which generated concentric traveling waves centered at a sensor
node, which wanted to gather information from all sensor
nodes or diffuse information to all sensor nodes. In
our mechanism, each sensor node broadcasts its sensor
information in accordance with the phase of its own timer.
When a sensor node receives a radio signal of others, it
shifts the phase of its timer. Through mutual interactions
among neighboring sensor nodes, they reach the phaselock and emit sensor information alternately. Throughsimulation experiments, we confirm the basic behavior of
our mechanism. Furthermore, we evaluate effectivenessof our mechanism in comparison with other method.
The rest of this paper is organized as follows. First, inΔ(φ)

non-firing node

2.5
2
1.5
1
0.5
0
-0.5
-1
-1.5

a=0.5
a=1.0
a=-0.5

0

0.2

0.4

0.6

0.8

1

φ

(b) PRC of RIC model ΔRIC
Figure 2. PRC examples

Section II, we briefly introduce the pulse-coupled oscillator model we adopted in this paper. Next, we investigate
conditions of a PRC which leads to a desired form of a
traveling wave from arbitrary settings of the initial phasein Section III. Then, we propose a distributed and selforganizing communication mechanism for wireless sensor
networks in Section IV, and show simulation results in
Section V. Finally, we conclude the paper and describe
future research work in Section VI.
II. P ULSE -C OUPLED O SCILLATOR M ODEL
A pulse-coupled oscillator model is developed to explain synchronous behaviors of biological oscillators suchas pacemaker cells, fireflies, and neurons. In this section,
mainly following the model described in [5], we give a
brief explanation of the model.
Consider a set of N oscillators. Each oscillator i has
phase φi ∈ [0, 1] (dφi /dt = 1). As time passes, φi shifts
toward one and, after reaching it, the oscillator fires andthe phase jumps back to zero. Oscillator j coupled withthe firing oscillator i is stimulated and advances its phaseby an amount Δ(φ j ). Thus, we have
φj → φj + Δ(φj ),(1)

where Δ(φ) is called a phase-response curve (PRC). For
example, for the quadratic integrate-and-fire (QIF) model,
ΔQIF (φ) = a(1 − cos 2πφ) (Fig. 2 (a)) and for the radialisochron clock (RIC) model, Δ RIC (φ) = −a sin 2πφ(Fig. 2 (b)) [5]. Here, an oscillator ignores all stimuli at
the moment of firing, and an oscillator identifies multiple
stimuli received at the same time as one stimulus.
Through mutual interactions, a set of oscillators reacheither of the global synchronization where they havethe same phase and fire all at once, or the phase-lockglobal synchronization
firingphase

1firing

1

φi
0

phase

phase lockfiring

Δ(φ )

Δ(φ )

0

time
firingfiring1

firingfiringΔ(φ )0stimuliFigure 5. Oscillators in tandem

firing

Δ(φ )

0

time

N

time

1

φj

P
1
2
pacemaker oscillator

time

Figure 3. Global synchronization and phase-lock

is firing. Therefore, they fire at the same time. On thecontrary, if oscillators have a PRC corresponding to Fig. 4(b), h(φ) converges at φ c independently of the initial
phase. It means that all oscillators reach the condition
where the phase is always φc when being stimulated.
Therefore, oscillators fire with the time difference of φ c
at the stable condition.

1

III. C ONDITION OF PRCh(φ)

TO G ENERATE T RAVELING WAVES

00

φ1 φ 2φ31phase φ(a) h(φ) generating the global synchronization

h(φ)

1

In this section, we investigate conditions of PRC thatlead to desired phase-lock condition regardless of theinitial phase to generate preferred traveling waves. We
call an oscillator which dominates and controls a PCO
network as a pacemaker. To keep the timing and frequency
of communication, a pacemaker will not be stimulated andwill fire at regular intervals, which corresponds to the data
gathering or diffusion cycle in a wireless sensor network.
A. Oscillators in Tandem

0
0

φ1

φ2

φ3

φc

1

phase φ(b) h(φ) generating the phase-lockFigure 4. Phase transition

condition where phases are different among oscillatorswith a constant offset as shown in Fig. 3. In the caseof the phase lock, the geographic propagation of firings
seems like a traveling wave as shown in Fig. 1.
Whether a network reaches the global synchronizationor the phase-lock depends on the initial phase of timers
or properties of the PRC [13]. In Fig. 4, h(φ) indicatesthe phase at which an oscillator is stimulated again by aneighboring oscillator, after the oscillator is stimulated
from a neighboring oscillator at the phase of φ. For
example, in the case of a pair of oscillators, it is definedas h(φ) = 1 − F (1 − F (φ)) where F (φ) = φ + Δ(φ). A
dotted diagonal line stands for h(φ) = φ, and a stepwiseline stands for phase transition of an oscillator whose
initial phase is φ1 . When an oscillator is stimulated at
φ1 , the oscillator changes its phase by using Eq. (1), andit will observe the next fire and be stimulated at φ 2 .
In Fig. 4 (a), through being stimulated several times,
the phase h(φ) becomes one from arbitrary initial phase.
h(φ) = 1 means that an oscillator receives a stimulus
from another firing oscillator when the oscillator itself

First, we consider a traveling wave in a PCO network
where oscillators are arranged in a line as shown in Fig. 5.
Each circle stands for an oscillator, each arrow shows
the direction of stimuli, and oscillators are numbered by
the number of hops from the pacemaker. An oscillator
is stimulated only by its neighboring oscillator which is
closer to the pacemaker. A pacemaker fires periodicallyat regular intervals of one time unit. Oscillators fire inorder of the pacemaker, oscillator 1, oscillator 2, · · ·,oscillator N at constant phase-difference τ . Therefore,
if a pacemaker fires at time 0, oscillator 1 fires at time
τ , and oscillator N fires at time N τ . Here, we consider
0 < τ < 1.
Now, consider phase transitions of oscillators at thephase-lock condition. Assume that after t time unit sinceoscillator i (1 ≤ i ≤ N ) fired, an oscillator i is
stimulated by oscillator i − 1. Oscillator 0 corresponds
to the pacemaker. Since oscillators fire at constant phasedifference τ , the phase of an oscillator becomes 1 − τwhen it is stimulated by a neighboring oscillator, i.e.,
F (t) = 1 − τ . Then, oscillator i fires at τ + t. Sincean oscillator fires at regular intervals of one at the phaselock condition, we have t + τ = 1. Hence, we haveΔ(1 − τ ) = 0.

(2)

To generate a desired traveling wave regardless of
the initial phase, an oscillator should advance its phasetowards 1 − τ when it is stimulated during 0 ≤ φ < 1 − τ ,and push back its phase towards 1−τ when it is stimulated
during 1 − τ < φ < 1. Finally, we have following

0.8
0.6
Δ(φ)

3

a=0.1, b=0.5
a=0.05, b=0.3

3

0.4

Δ(φ)=1-τ−φpacemaker
P
1

1

2

2

N

1
2

oscillator

stimuli

0.2
0Δ(φ)=0Figure 8. Two-dimensional arrangement of oscillators

-0.2
0

0.2

0.4

0.6

0.8

1

phase φemerges by only one interaction, i.e., stimulus, among
oscillators with a = 0 and b = 1. However, suchaggressive setting spoils the resilience of the mechanism
against a failure of node and unexpected influence fromthe environment, since a single firing emitted at a wrong
time will drastically change the state of the whole system.
Therefore, a PRC function and its parameters should beappropriately determined taking into account the trade-off
between the speed that a traveling wave emerges and theresilience against failures.

phase at stimulus reception

Figure 6. PRC Δs from Eq. (4)1

a=0 b=1
a=0.1 b=0.6
a=0.05 b=0.6
a=0.01 b=0.5

0.5
1

2

3

4

5

6

7

8

number of stimuli from the pacemaker

Figure 7. Phase transition of oscillator 1

conditions of PRC to generate a traveling wave regardlessof the initial phase.
⎧⎨ 0 < Δ(φ) ≤ 1 − τ − φ (0 ≤ φ < 1 − τ )Δ(φ) = 0(φ = 1 − τ )(3)⎩
1 − τ − φ ≤ Δ(φ) < 0 (1 − τ < φ < 1).
For example, following PRC function satisfies Eq. (3).
π
φ + b(1 − τ − φ)(4)Δs (φ) = a sin
1−τ))Here, a (− b(1−τ< a ≤ (1−b)(1−τ) and b (0 < b ≤ 1)π
π

are parameters which determine characteristics of PRC.
Figure 6 illustrates PRC Δs (φ) for two different settingsof a and b when τ = 0.2. Two dot-and-dash lines standfor Δ(φ) = 0 and Δ(φ) = 1 − τ − φ, respectively. The
curve of PRC satisfying Eq. (3) must lie between these
two lines.
With a PRC satisfying the above conditions, oscillators
fire in order of the pacemaker, oscillator 1, oscillator
2, · · ·, oscillator N at constant phase-difference of τ atthe phase-lock condition. This can also be regarded asa traveling wave propagating from oscillator N toward
the pacemaker, with constant phase-difference 1 − τ .
Therefore, to have a diffusion type of communication,
where information propagates from the peacemaker tooscillator N with constant phase-difference τ , τ should
be set as τ < 0.5. On the contrary, to have a gathering
type of communication, τ should be set as τ > 0.5.
Figure 7 shows a phase of oscillator 1 when it receives
a stimulus from the pacemaker where τ = 0.1 andN = 1. The initial phase of oscillator 1 is randomly
chosen, and results are averaged over 1000 simulations.
At a = 0, as parameters a and b increase, a travelingwave emerges more rapidly. Especially, a traveling wave

B. Oscillators in Two-Dimensional Arrangement
A PRC satisfying Eq. (3) can also be applied to thecase of two dimensional arrangement of oscillators. By
making a tree whose root is the pacemaker and setting
the direction of stimuli as shown in Fig. 8, we can adopt
the same PRC and generate a traveling wave propagatingfrom or to the pacemaker in a two-dimensional area. Although any routing protocol for wireless sensor networks
is viable to organize such tree-type topology, a simple
way of setting such relationship among oscillators will
be given in the next section.
IV. A D ISTRIBUTED AND S ELF - ORGANIZINGC OMMUNICATION M ECHANISM
In this section, we propose a fully-distributed and selforganizing communication mechanism for wireless sensor
networks. In our mechanism, any of sensor nodes canbecome a point, called core node, from which messages
are disseminated or to which messages are gatheredin accordance with application requirements. Core nodeplays a role of a pacemaker in the PCO model.
A. Basic Behavior
Sensor node i (1 ≤ i ≤ N ) has a timer with phaseφi ∈ [0, 1]. It maintains PRC function Δ(φ), level value
li , session identifier si , direction δi , and offset τ (0 <
τ < 0.5). Initially a level value, a session identifier, anda direction are set to zero. A level value indicates thenumber of hops from the core node and it is used todefine the relationship among sensor nodes. Direction δ i
is a parameter which controls the direction of information
propagation, and it is set at 1 for diffusion and −1for gathering. The offset defines the interval of message
emission between a node of level l − 1 and that oflevel l. The PRC function and offset are determined at
the deployment phase, but the offset can be dynamicallyadjusted as explained later. In this paper, based on Eq. (4),
we use the following PRC function for all sensor nodes.
πΔ(φ) = a sin φ + b(g − φ),(5)gHere, g is defined as (1 − δi τ ) mod 1.
As time passes, phase φi shifts toward one and, after
reaching it, sensor node i broadcasts a message andthe phase jumps back to zero. A message that sensor
node i emits contains level value l i , session identifiersi , direction δi , and its information aggregated withother sensor’s information kept in its buffer. To initiate a
new communication, a core node broadcasts a message
containing a new session identifier set at the current
value plus one, a level value of zero, the direction, andinformation to disseminate or gather.
Now, sensor node i receives a message from sensor
node j. If session identifier s j is larger than si , sensor
node i considers that a new communication begins. Therefore, it sets its level value li at lj + 1, session identifier
si at sj , and direction δ i at δj . Then, it is stimulated tojoin a new traveling wave. This mechanism means thatthe current communication is terminated by a newly initiated communication. To avoid unintended termination ofcommunication by other sensor nodes, a core node might
advertise its desired communication period in a message itemits. However, it requires an additional mechanism suchas clock synchronization, and it is left as one of future
research issues. If session identifiers are the same but thelevel value lj is smaller than li , sensor node i sets its levelvalue li at lj + 1, direction δi at δj , and it is stimulated.
Stimulated sensor node i shifts its phase based on the
PRC function. As in the PCO model, a sensor node is notstimulated by messages from sensor nodes with a smaller
level value during the following duration of τ when it
has already been stimulated, to avoid being stimulated bydeferred messages. If the session identifier is the sameand level value l j is li − δi , sensor node j is an upstream
node of sensor node i. Therefore, to relay information of
sensor node j to the next downstream node, sensor nodei deposits the received information in its local buffer. If
a message does not satisfy any of the above conditions,sensor node i ignores it. We should note here that a sensor
node only emits a message in accordance with the phaseof its timer. No additional message is required to organize
a traveling wave. The algorithm is illustrated in Fig. 9.

sensor node i receives a message
from sensor node j

YES

YES
(new communication)si ← s jNO

s j = si ?

NO

s j > si ?

NO

l j < li ?

li ← l j + 1
δi ← δ jYES

φ i ← φ i + Δ (φ i )※※ stimulatedli ← l j + 1
δi ← δ j

φ i ← φ i + Δ (φ i )※l j = li − δ i ?

NO

YES

sensor node i deposits
received information

end of processing

Figure 9. Node behavior on message reception

Here, τ should be appropriately determined considering
trade-off between the rate of successful message reception
and the lifetime of sensor network. The smaller τ is, thesmaller probability of successful message reception by
missing messages delayed by collisions in radio signals.
At the same time, a smaller τ leads to longer lifetime ofsensor network, since a node is awake for the duration of2τ in one communication cycle.
To judge whether the phase-lock condition is globally
accomplished or not, we consider T max as the worst-casetime required for a sensor node to establish the phaselock condition with a neighboring node closer to the corenode. We can expect that a sensor node can move to a
power-saving mode after (l i + (1 − δi )/2) × Tmax since
the level value is updated.
If the phase-lock condition is lost for some reasons
after a power-saving mode is activated, a sensor node
does not receive any valid message when it is awake.
In such a case, a sensor node stops a power-saving mode
to reorganize the phase-lock condition.
C. Addition and Removal of Sensor Nodes

B. Power-Saving Mode
Through mutual interactions among neighboring sensor
nodes, they reach the phase-lock, and a sensor node
moves to a power-saving mode. In power-saving mode,a sensor node wakes up when its phase is at 1 − τ toreceive messages from upstream nodes. Upstream nodes
are scheduled to emit their messages from 1 − τ to 1.
When its phase reaches one, a sensor node broadcasts
a message. After that, it keeps awake for τ to receive
messages from downstream nodes, and then goes to sleepby turning off its radio transceiver and other needlessmodules.

Next, we consider the case where a new sensor node
is introduced in a sensor network in operation. Initially,
the session identifier of a new sensor node is set atzero. Therefore, it does node affect other sensor nodes.
Being stimulated several times, its level value, session
identifier, and direction are correctly identified, and its
timer synchronizes at constant phase-difference with thatof a neighboring sensor node whose level is smaller byone.
On the contrary, when a sensor node disappears due
to battery depletion or removal, a sensor node that issynchronized with the vanished node will be stimulated

by another of the same level as the vanishing node. If
there is no other node with a smaller level value in its
vicinity, the sensor node becomes isolated. Since it does
not receive stimuli any more, it can recognize the isolationand then it initializes its session identifier so that it cansynchronize with other neighboring sensor nodes.
D. Multiple Core Nodes
In addition, we consider the case that there are two
or more core nodes with the same session identifier ina sensor network. Since it takes time for information to
propagate between the edge of a wireless sensor network
and a core node, it is a good idea to have multiple corenodes for one communication to solve the scalability
problem. In such case, the sensor network is divided into
clusters each of which has one core node. Each core node
can gather or diffuse information in its cluster.
A sensor node which is at the same hop count from
more than one core node, which we call a border node,
receives messages from different clusters. Since session
initiation is not necessarily synchronized among corenodes and time required for stimulus propagation would
differ among paths from core nodes, such multiple stimuli
prevent a border node from establishing the phase-lockcondition with neighboring nodes.
Therefore, a border node chooses one cluster which it
belongs to. First, after a level value is updated, a bordernode waits for the duration of (l i − 1) × Tmax + τ until
the phase-lock condition is established in each of clusters.
Then, it begins to stick on the timing of the first message it
receives. To avoid being stimulated by deferred messages
or message originated from another core node, it ignores
received stimuli during the following duration of 1 − τwhen it has already been stimulated.
E. Node Failures
Finally, we consider cases of node failures. First, thefailure of a radio transmitter has no influence on othercommunication, since a failed sensor node can not emit
any message and never stimulate neighboring nodes. On
the other hand, a sensor node with a failed receiverkeeps sending messages based on its timer. The timer
of a failed node keeps its own pace independently ofthe others. Therefore, when the phase-lock condition is
not established yet, the failed node disturbs establishmentof the phase-lock condition by stimulating neighboring
nodes at inappropriate timings. However, a failed node
eventually considers it is isolated for not receiving any
message from neighboring nodes. Then, it initializes its
state and it does not affect others anymore.
In some cases, a timer gains or loses, being affectedby, for example, geomagnetism. Basically, a wrong timer
will be correctly adjusted from stimulations. A sensor
node with a timer which gains, stimulates neighboring
nodes at a wrong timing, since sensor nodes take thefirst message it receives and ignores the following delayed
messages. If a wrong timer keeps an advanced phase, theproblem is that the interval between message emission of
the failed node and its upstream node becomes smaller
than τ and it does not bring any serious influence on
message propagation.
On the other hand, a sensor node with a timer whichloses does not affect the phase-lock condition very much.
If a sensor node which is stimulated by a failed node
has another normal node with a smaller level value, it isalways stimulated by the normal sensor node and ignores
delayed messages from the failed node. Otherwise, theinterval of message emission of the failed sensor nodeand the affected sensor node becomes longer than τ .
In addition, we consider wrong setting of parameterssuch as δi , li , and si of sensor node i by temporal errorof memory or CPU. Direction δ i is updated periodicallywhen a sensor node receives a message from a sensor
node with a smaller level value.
When level value l i is incorrectly larger than the actual
hop count from a core node, messages emitted by sensor
node i do not affect neighboring sensor nodes with asmaller level value. On the contrary, if the level value is
too small, neighboring nodes would wrongly identify theirdistance from the core node. It first disturbs establishing
the phase-lock condition. However, since the level valueof the failed sensor node is the smallest in its range ofradio signals, it does not receive any stimulus, i.e., amessage with a further larger level value. Therefore, it
considers it is isolated and initializes its session identifier
so that its level value will be adjusted correctly.
When the session identifier s i is incorrectly smaller
than the current session identifier used in a wirelesssensor network, the failed sensor node does not affectthe others at all. Its session identifier will be corrected
on receiving a message from a neighboring sensor node.
On the contrary, a larger session identifier s i means thata new communication is initiated by the failed sensor
node. Since the other nodes cannot judge whether a newcommunication is actually initiated or not, it is handled
as normal. When another sensor node initiates a newcommunication, a new session identifier is used and thefailed node does not affect the others any more.
V. S IMULATION E XPERIMENTS
In this section, we show results of simulation experiments. In the simulation, the range of the radio signal isfixed at 2 units of length. The initial phase of sensor nodeis randomly chosen. A sensor node consumes 81 mW fortransmission, 30 mW for receiving and idle, and 0.003
mW for sleep [14]. Initial energy is 50 J for all nodes.
We use Eq. (5) with a = 0.01 and b = 0.5 as the PRC
function and τ is set at 0.1.
A. Basic Behavior
We first confirm the basic behavior of our communication mechanism. We consider sensor networks of 100
sensor nodes randomly distributed in a 10 × 10 region.
From 0 to 20 time units, we randomly chose a sensor
node A as a core node for information diffusion. Then,

4hop

80
3hop

60
40
2hop

20
1hop
0hop

0
0

5

10

15

20

time

4hop

100
label of sensor nodelabel of sensor node

100

80

3hop

60
40

2hop

20
1hop
0hop

0
0

5

10

15

20

time

(a) Diffusion
Figure 12. Timing of message emission with dynamic deployment

label of sensor node

100

7hop
6hop

80

5hop

60
4hop

40
3hop

20

2hop
1hop
0hop

0
20

25

30
time

35

40

(b) Gathering
Figure 10. Timing of message emissions

0.6

a=0.01 b=0.5
a=0.05 b=0.6

probability

0.5
0.4
0.3
0.2
0.1
0
0

5
10
15
20
time to establish the phase-lock25

Figure 11. Distribution of the time to establish the phase-lock condition

from 20 to 40 time units, we randomly chose anothersensor node B as a core node for information gathering.
Figure 10 shows how the sensor network reached thephase-lock condition in a certain simulation experiment.
Each mark stands for an instant when a sensor node
emitted a message. For easier understanding, sensor nodes
are sorted in order of the hop count from the core node. In
the upper figure, at first, all sensor nodes randomly andindependently emit messages. However, by exchanging
stimuli several times, the phase-lock condition is eventually accomplished and a regular pattern appears. It isclearly shown that message emission is in order of the
hop count of sensor nodes, from the core node to nodes
with larger numbers. In the lower figure, it is shown thatthe phase-lock condition for information diffusion is firstbroken for information gathering initiated by sensor node
B. Then, although it takes longer time than for diffusion,
the new phase-lock condition appears, where information
propagates from the edge of the sensor network towards
the core node B.
Over 100 experiments, the average time to establish
the phase-lock condition is 15.5 time units. The time

ranges from 11.6 to 19.6 depending on the distributionof sensor nodes, location of the core node, and phaseof sensor nodes. The histogram is shown in Fig. 11.
The time to reach the stable phase-lock condition canbe reduced by using a set of larger a and b satisfying
Eq. (3). For example, with a = 0.05 and b = 0.6, theminimum, average, and maximum are 5.96, 8.10, and10.7, respectively.
We confirmed that traveling waves can be formed in awireless network with addition, movement, and removalof sensor nodes, and failed nodes. In Fig. 12, an exampleof the case of node addition is illustrated. At 10 timeunits, after the phase-lock condition is established for
information diffusion, ten sensor nodes are deployed at
random locations in the wireless sensor network. As canbe seen in the figure, newly added sensor nodes initiallyemit messages independently of their location. When a
new sensor node receives a message from an existing
sensor node, it sets the level value as the received value
plus one. However, its timer has not been adjusted wellyet. Therefore, the phase-lock condition of neighboring
sensor nodes is lost as in the case of timer errors. However, as time passes, they begin to behave in synchrony
with sensor nodes at the same distance from the core nodeand the phase-lock condition is re-established in the wholesensor network.
B. Effectiveness of the Mechanism
We next evaluate effectiveness of our communication
mechanism. We consider wireless sensor networks of100, 900, and 2500 sensor nodes randomly distributed in
10×10, 30×30, and 50×50 region, respectively. A corenode is randomly chosen for data gathering or information
diffusion. For comparison purposes, we also conductsimulation experiments for the directed diffusion [2, 3]
where per-hop delay is set at 0.1 time units. All results
are averaged over 100 simulation experiments.
The response time indicates the duration from emissionof an interest or a message with a new session identifier
to reception of sensor information from all nodes. The
topology time indicates the duration from emission of
an interest or a message with a new session identifier
to reception of reinforcement messages at all nodes orto establish the phase-lock condition. The number ofmessages indicates the average number of messages thatnumber of messages

80
60
40

proposal
20

two-phase pull diffusion

response time
topology time

2000
1500
1000

two-phase pull diffusion
500
proposal

0

0
0

500

1000

1500

2000

2500

0

500

number of nodes

proposalpush diffusion

20
0
0

500

1000

1500

2500

proposalpush diffusion
0

500

2000

2500

number of nodes

0.8
0.6
0.4
0.2
0
0.01

1500

2000

2500

(c) Response and topology time in diffusion

proposal
two-phase pull diffusion
0.1(e) Data gathering ratio

160
140
120
100
80
60
40
20
0

proposal
two-phase pull diffusion
using power-saving mode0

packet loss probability(d) Number of messages in diffusion

1000

number of nodes

1

60
40

2000

(b) Number of messages in gathering

data gathering ratio

number of messages

response time
topology time

80

1500

response time
topology timenumber of nodes(a) Response and topology time in gathering
100

1000

80
70
60
50
40
30
20
10
0

number of available nodes

time

2500

response time
topology time

time

100

2000

4000

6000

time

(f) Number of available nodes in gathering

Figure 13. Comparison among proposal and directed diffusiona node sends and receives during the response time or
the topology time. The data gathering ratio is defined as
the ratio of data reached to a core node or a sink node
to the number of nodes. The lifetime is defined as theduration from emission of an interest or a message witha new session identifier to death of any sensor node due
to depletion of energy.
In Fig. 13 (a), both of the response time and topology
time with our mechanism are longer than those with thedirected diffusion. A traveling wave is generated thoroughlocal and mutual interactions, whereas the directed diffusion relies on message flooding. However, the overhead interms of the number of messages is much smaller with ourmechanism. It is only 1 to 6 % of the directed diffusionin the response time and 4 to 26 % in the topology
time as shown in Fig. 13 (b). Since a sensor node emits
a message per cycle in our mechanism, the number ofmessage increases in proportional to the response andtopology time. As described in Section III, the responsetime and topology time can be reduced by adjusting a
PRC function and its parameters.
Figure 13 (c) shows results for the case of information
diffusion, where a randomly chosen node diffuses information to the whole sensor network. When comparing to
the push diffusion of the directed diffusion, our proposal
takes longer to diffuse information to all nodes. Differently from the data gathering scenario, the overhead islarger with our mechanism. It is 220 to 790 % of thedirected diffusion in response time and 718 to 877 %in topology time as shown in Fig. 13 (d). In the case ofdiffusion, only one source node floods exploratory data to
all other nodes in the push diffusion, but our mechanism
takes time to generate a traveling wave and thus requires
much message exchanges.

Figure 13 (e) shows the data gathering ratio against
the packet loss probability in a 10×10 network. A sensor
node randomly fails in transmitting a message at thepacket loss probability shown on the x-axis. In Fig. 13(e), our mechanism always achieves higher data gathering
ratio than the directed diffusion with the same packet loss
probability. In our mechanism, broadcasting contributes
to achieving multi-path effect and this leads to the higher
gathering ratio.
Finally, we verify energy efficiency of our mechanism
from a viewpoint of a lifetime of a sensor network of
100 nodes. As shown in Fig. 13 (f), the lifetime with
our mechanism is 1577 time units whereas that withthe directed diffusion is 265 time units in the case of
information gathering. Furthermore, by using a powersaving mode, the lifetime with our mechanism becomesas long as 2733 time units wheres that with the directeddiffusion is 304 time units. On the contrary, although thefigure is not shown, the lifetime with our mechanism is1577 time units whereas that with the directed diffusion
is 251 time units in the case of information diffusion.
Furthermore, by using a power-saving mode, the lifetime
with our mechanism becomes as long as 3680 time units
whereas that with the directed diffusion is 286 time units.
VI. C ONCLUSION AND F UTURE W ORK
In this paper, we first investigated initial conditions thatlead to a desired form of traveling wave regardless of theinitial phase of oscillators in a pulse-coupled oscillator
model. Next, we proposed a fully-distributed and selforganizing communication mechanism in wireless sensor
networks. Through simulation experiments, we confirmedthat our scheme can gather or diffuse information inaccordance with application requirements in a dynamic

wireless sensor network. In addition, we confirmed that
our mechanism delivers sensor information to / fromdesignated nodes in a more energy-efficient manner thanother method, although it takes time to generate a traveling wave.
As future research work, we plan to implement ourmechanism using off-the-shelf sensor to verify the practicality of our mechanism. In an actual environment, radio
signals are unstable and unreliable. Due to collisions
among synchronized transmission of messages from sensor nodes at the same distance from a core node, i.e, withthe same level value, messages will be lost or delayed. In[12], we implemented another PCO-based data gathering
scheme where all sensor nodes of the same level value
behave in synchrony and confirmed that it worked as
expected with some additional mechanisms to solve theinstability and unreliability of radio communication. We
consider the mechanism proposed in this paper can also
work well with a similar approach.
ACKNOWLEDGMENTS
This work was partly supported by “Special Coordination Funds for Promoting Science and Technology:
Yuragi Project”, Grant-in-Aid for Scientific Research on
Priority Areas 18049050, and a Grant-in-Aid for Scientific
Research (A)(2) 16200003 of the Ministry of Education,
Culture, Sports, Science and Technology in Japan.
R EFERENCES[1] Y. Taniguchi, N. Wakamiya, and M. Murata, “A selforganizing communication mechanism using travelingwave phenomena for wireless sensor networks,” in Proceedings of 2nd International Workshop on Ad Hoc, Sensor
and P2P Networks (AHSP 2007), Mar. 2007, pp. 562–569.
[2] J. Heidemann, F. Silva, and D. Estrin, “Matching data
dissemination algorithms to application requirements,” inProceedings of the ACM SenSys conference, Nov. 2003,
pp. 218–229.
[3] F. Silva, J. Heidemann, D. Estrin, and T. Tran, “Directed diffusion,” Technical Report ISI-TR-2004-586,
USC/Information Science Institute, Jan. 2004.
[4] R. E. Mirollo and S. H. Strogatz, “Synchronization ofpulse-coupled biological oscillators,” Society for Industrial
and Applied Mathematics Journal, pp. 1645–1662, Dec.
1990.
[5] P. Goel and B. Ermentrout, “Synchrony, stability, and firing
patterns in pulse-coupled oscillators,” Physica D, pp. 191–
216, Mar. 2002.
[6] Y.-W. Hong and A. Scaglione, “A scalable synchronization
protocol for large scale sensor networks and its appliations,” IEEE Journal on Selected Areas in Communications, vol. 23, pp. 1085–1099, May 2005.
[7] S. F. Bush, “Low-energy network time synchronization
as an emergent property,” in Proceedings of the 14th
International Conference on Computer Communications
and Networks (ICCCN 2005), Oct. 2005, pp. 93–98.
[8] G. Werner-Allen, G. Tewari, A. Patel, M. Welsh, and
R. Nagpal, “Firefly-inspired sensor network synchronicity
with realistic radio effects,” in Proceedings of the 3rdinternational conference on Embedded networked sensor
systems (SenSys 2005), Nov. 2005, pp. 142–153.

[9] A.-S. Hu and S. D. Servetto, “On the scalability of cooperative time synchronization in pulse-connected networks,”
IEEE Transactions on Information Theory, vol. 52, no. 6,
pp. 2725–2748, June 2006.
[10] A. Tyrrell, G. Auer, and C. Bettstetter, “Synchronization
inspired from nature for wireless meshed networks,” inProceedings of the 2nd IEEE International Conference on
Wireless Communications, Networking and Mobile Computing (WiCOM 2006), Sept. 2006, pp. 1–4.
[11] N. Wakamiya and M. Murata, “Synchronization-based data
gathering scheme for sensor networks,” IEICE Transactions on Communications, vol. E88-B, pp. 873–881, Mar.
2005.
[12] S. Kashihara, N. Wakamiya, and M. Murata, “Implementation and evaluation of a synchronization-based data
gathering scheme for sensor networks,” in Proceedingsof the IEEE International Conference on Communication,
Wireless Networking (ICC 2005), May 2005, pp. 3037–
3043.
[13] M. B. H. Rhouma and H. Frigui, “Self-organization ofpulse-coupled oscillators with application to clustering,”
IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 180–195, Feb. 2001.
[14] “MOTE,” available at http://www.xbow.com/Products/
wproductsoverview.aspx.

Yoshiaki Taniguchi received his BE and ME Degrees in Information and Computer Science from Osaka University in 2002
and 2004, respectively. He is currently a Ph.D. candidate at
Osaka University. His research interests include wireless sensor
networks and QoS architecture for real-time and interactive
video distribution system. He is a member of IEICE.

Naoki Wakamiya received his ME and DE Degrees from Osaka
University, Japan, in 1994 and 1996 respectively. He was a
Research Associate from 1996 and an Assistant Professor at theGraduate School of Engineering Science of Osaka University
from 1999 to 2002. Since 2002, he has been an Associate
Professor at the Graduate School of Information Science andTechnology, Osaka University. His research interests include
wireless sensor networks, mobile ad hoc networks, and overlay
networks. He is a member of IEICE, IPSJ, ACM and IEEE.

Masayuki Murata received his ME and DE Degrees from
Osaka University, Japan, in 1984 and 1988 respectively. In 1984,
he joined the Tokyo Research Laboratory, IBM Japan, as a
Researcher. He was an Assistant Professor from 1987 and an
Associate Professor at Osaka University from 1992 to 1999.
Since 1999, he has been a Professor at Osaka University. He
has more than 400 papers in international and domestic journals
and conferences. His research interests include computer communication networks, performance modeling and evaluation. He
is a member of IEEE, ACM, The Internet Society, IEICE andIPSJ.