Evaluation of Robustness in Time Synchronization for
Sensor Networks
Akira Mutazono

Masashi Sugano

Masayuki Murata

Graduate School ofInformation Science andTechnology, Osaka University
1-5 Yamadaoka, Suita-shi,
Osaka, 565-0871, Japan

School of Comprehensive
Rehabilitation, Osaka
Prefecture University
3-7-30 Habikino, Habikino-shi,
Osaka, 583-8555, Japan

Graduate School ofInformation Science andTechnology, Osaka University
1-5 Yamadaoka, Suita-shi,
Osaka, 565-0871, Japana-mutazono@ist.osakau.ac.jp

sugano@rehab.osakafuu.ac.jp

murata@ist.osaka-u.ac.jp

ABSTRACT

used, ensures a sensor node wakes up only when it is required

In sensor networks, time synchronization between sensor
nodes is important because it aects not only the eciency
of information gathering but also energy consumption. Since
sensor network environments and sizes change at varying
rates, dierent time synchronization techniques are requiredfor dierent networks. The pulse-coupled oscillator (PCO)
model can be used to achieve local interactions between individuals for the synchronization of entire networks. Other
methods also exist, such as the multi-hop reference broadcast synchronization (RBS) method which synchronizes theentire network by transmitting the dierences in the timersof reference nodes through networks divided into clusters.
We compare here the inuence of jitter delay and packet
loss resulting from the lower layer protocol on these twotechniques. We also investigate the inuence on the performance of both methods on network size and wireless channel
quality. The simulation results show the conditions in which
each method performs better.

to work [2]. In addition, data gathering becomes more efcient when the sensor nodes transmit information at coordinated times [3]. These power-saving techniques cannot
be implemented without the synchronization of all sensor
nodes.
Reference Broadcast Synchronization (RBS) [4] has been
proposed as the time synchronization technique for use witha wireless network.

This technique realizes an exact syn-chronization by not absolute time but relative time.

Theadvantage of RBS is that it is not aected by send time oraccess time, which occurs in the MAC layer, because it uses
relative time. However, as RBS uses centralized control, it isinapplicable if the network size exceeds transmission range.
Therefore, multi-hop RBS is being applied to large-scale networks [4]. However, multi-hop RBS which is centralized timesynchronization control can achive a accuracy synchronization, there are some problems in realstic sensor networks(i.e., scalability and packet loss).
Increasing importance is being placed on distributed control as a way to combat these problems. In particular, at-Keywords

tention is being paid to the control method which is in-sensor networks, synchronization, pulse coupled oscillator,
CSMA/CA, multi-hop RBS

spired by the synchronization phenomena seen in a nature.
Some papers have dened the eciency of bio-inspired approach [5]. Then we are motivated to nd out the superiority of bio-inspired method against centralized method also

1. INTRODUCTION

in time synchronization control. The pulse-coupled oscilla-

Continued improvements in wireless technology that pro-tor (PCO) is modeled on biological systems, such as groupvides low-cost, compact and reliable sensor devices are fo-of reies or cardiac pacemaker cells [6]. Past research has

cusing research on sensor nodes networks from which theseevaluated the performance characteristics of the PCO, but

devices are comprised [1]. In a sensor network, the time syn-has rarely compared it with other synchronization control

chronization between sensor nodes is becoming an important

techniques [7, 8]. Those studies that do evaluate PCO, dofeature. For example, energy consumption is a crucial prob-

so only under ideal conditions and do not consider the in-lem for sensor networks, as each sensor node has only theuences of, for example, delays and packet losses that have

limited power resources of a low capacity battery.

a marked eect on precision in synchronization and time

Sleep

control is one ecient power-saving technique, which whento synchronization.

Moreover, although the goal of thosepapers is rapid time synchronization based on the communication of pulses in spite of usual packets, it is not realisticfrom an economic viewpoint to prepare a circuit for this ex-

Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.
Bionetics’07 December 10-13, 2007, Budapest, Hungary.
Copyright 2007 ICST 978-963-9799-11-0.

clusive use. In this paper, we apply packet level PCO thatworks as overlay of the packet transmission based on IEEE
802.15.4 for applications that do not need high accuracy andhigh-speed synchronization. We also consider the eects of
the low layers in the comparative evaluations of PCO andmulti-hop RBS. Carrier Sense Multiple Access with CollisionAvoidance (CSMA/CA), which is used in IEEE 802.15.4 assynchronization dicult, but it is necessary for synchroniza-

standard protocol in sensor networks, works as the trans-

tion control to synchronize real network.

mission protocol on the MAC layer. We implemented PCO
and multi-hop RBS as synchronization mechanisms in the

3.1

Mirollo and Strogatz Modelhigh layer above CSMA/CA, compared PCO and multi-hop

The M&S model [6] is the time synchronization mecha-

RBS using simulations, and investigated the network envi-

nism applied by PCO to sensor network. An oscillator works

based on its phase, ϕ ∈ [0, 1], representing the internal timeronment for which each method is most suited.
The organization of this paper is follows. We rst explain

and the state,x ∈ [0, 1], representing the phase.

Let usthe network models and dene synchronization in Section 2.

consider the set O = {O1 , · · · ON } of N oscillators. Each os-

In Section 3, we describe synchronization with PCO. And incillator has phase ϕi and state xi , which changes over time,

Section 4, we show how multi-hop RBS operates. In Section

and xi is given by the function fi .

5, we present the results of our simulations and conclude by

xi = fi (ϕi )discussing plans for future work.

(6)

In particular, fi (0) = 0 , fi (1) = 1, and phase ϕi changes
dϕ
1
0 to 1 every clock cycle Ti and dti = T . When a phase

2. SYSTEM DEFINITION

ireaches 1, the oscillator res and the phase is reset to 0. If

2.1 Network ModelAll the sensor nodes have the same capability, and havean oscillator indicating internal time.

It is assumed thatthe cycle of all the oscillators is the same.

oscillator τi receives a pulse, then its oscillator increases εto its own state, the two oscillators, Oi and Oj , are coupled.

Internal time

xj (τi+ ) =of oscillator Ci (t) is expressed as Eq. (1) using clock driftai (t), oset bi (t), and clock cycle Ti of node i. In this paper,
we assume that none of sensor nodes is synchronized at theinitial state, and the oset is set at random.

Ci (t) = ai (t) Ti + bi (t)(1)ȷ

xj (τi ) + ε,0,

if xj (τi ) + ε < 1(7)otherwise

By giving such a stimulus to each other, a coupled oscillator
becomes synchronized over time.

3.2

Effect of Delay on Time Synchronization

Sensor nodes use CSMA/CA as their MAC layer protocol.

The M&S model considers that the eect of the ring ofWith CSMA/CA, carrier sensing is done before the packet

a neighboring node instantaneously takes place, regardlessis transmitted, and it is known whether a packet can accessof delay.

the channel. We adopt the CSMA/CA protocol according

time a sensor node res and transmits information, it isto IEEE 802.15.4.

necessary for a node to take account of the delay.

However, since delay will in fact occur by the

Reach-back Firey Algorithm (RFA)

2.2 Synchronization ModelIn the[9], the timestamp isused to announce the access delay on MAC layer.

First,In real networks, it is dicult for all sensor nodes to be

the sensor node stores the time of ring and transmits data

completely synchronized due to transmission delay, inter-

after a waiting period when it is conrmed by CSMA/CA

face, and packet loss.

In addition, the required precisionthat the channel is free. Thus, the receiving node can knowof the synchronization diers according to the application.

the delay after a source node res by marking data packet

Therefore, we use a synchronization window W as the pa-

using delay as the time stamp. Although access delay canrameter to determine a synchronization and use this as an

be indicated with a time stamp, it is not sucient for theindex of target synchronous accuracy [9]. Consider the rel-M&S model to remove the eects of delay, since a phase

ative oset zij ∈ [−0.5, 0.5] between node ni and nj , which
has the internal time bi , bj ∈ [0, 1]. zij is expressed aszij = ((bj − bi + 1.5) mod 1.0) − 0.5(2)cannot be changed simultaneously with ring. Additionally,
when a phase is changed at the same time as the eect of thering is experienced, some problems arise. To avoid these
problems, even if a sensor node receives information about

Gi (w) which starts
from node ni and synchronization window size w which de-a ring, the amount of the change in the phase should becides the size of group. Then we nd the biggest group.

the stack is announced and, the phase is changed after self

We dene the synchronization group

Gi (w) = {nj | 0 < zij < w}

(3)

Si = |Gi (w)|(4)

Sk = max Si

(5)

∀i

where Si is the number of nodes in group Gi (w) and Sk is
the ratio of synchronized nodes. If Sk is equivalent to thenumber of all sensor nodes, the group Gk is in the complete
synchronous state.

stacked at once without being changed. Then, the value ofring and waiting xed time waiting time W . W should be
longer than the back-o time of CSMA/CA.

4.

CENTRALIZED TIME SYNCHRONIZATION CONTROL

4.1 Reference Broadcast Synchronization
Reference broadcast synchronization (RBS) [4] is a timesynchronization mechanism that does not use a time stamp.
RBS does not set the time of the transmission node and the

3. BIO-INSPIRED TIME SYNCHRONIZATION CONTROL

receiving node but sets the times of nodes receiving fromThe distributed communication strategy that we propose

access delay. Since the error in the reference time between

is based on packet instead of pulse. This condition makes

the nodes is an error until a packet is transmitted and re-each other. The main benet of RBS is that it achieves ahigh accuracy in synchronization which is not aected byceived. The access delay, which is the time until a packet isTable 1: Default parameter settingstransmitted, can be eliminated.

parameter

Step1.

A base node broadcasts a reference packet

Step2.

n sensor nodes, which receives the reference packet,
store their own reception time T .

Step3.

A reception node exchanges reception times withother sensor nodes that receive the reference packet.

Step4.

A reception node calculates the average time oferror oset[i] of the exchanged reception timeand its own reception time.

n is the number of the sensor nodes within thetransmission range of base node, and Tr is the time whensensor node r receives the reference packet. The oset[i] is
where

given by Equation (8).

value

Number of sensor nodes

200

Radius of monitoring region

100 mCommunication range

50 m

Packet loss rate

0.001

Synchronous window size

0.1

Stimulation of re ε (PCO)

0.0008Firing cycle T (PCO)

0.16 sec

Maximum simulation time (PCO)

100 sec

PCO stays for ve continuous cycles in a completely synn

1X
(Ti − Tk )oset[i] =n∀i ∈ n(8)k=1chronous state. We consider a network as synchronized when
multi-hop RBS cluster synchronous information spreads toall the clusters and the network is in a completely synchronous state. The time taken is assumed to be the time to

4.2 Multi-hop RBS
RBS can be eective only when all sensor nodes are arranged within the communication range of a base node.

synchronization. Similarly, the time synchronous accuracy
is measured by the variance of the phase of the sensor node.
n

In other words, RBS can not synchronize large scale net-v=

works because of the communication distances eliminationof the base nodes. Therefore, the whole network is divided
into clusters and RBS is applied to every cluster. A sensor
node called a gateway node, which belongs to two or moreei =clusters, translates the relative time between clusters. The
mechanism for transmitting synchronous time information
to the whole network is called multi-hop RBS.
In multi-hop RBS, the sensor node called the sink plays a
key role in controlling the synchronization of the whole network. First, the sink transmits the schedule for executing
RBS to a cluster head by multi-hop communication.

The

cluster head that receives the schedule information carries
out RBS within its own cluster, and when it is conrmedthat all the sensor nodes in the cluster can be synchronized,
it tells that RBS was completed. After a sink conrms thatRBS has been carried out by all the clusters, it broadcasts
the synchronization time information in its own cluster to
set the time of the entire network at the synchronous time ofits own cluster. The gateway node that receives synchronoustime information spreads it to the next cluster while it calculates the error in the synchronous time between clusters
and noties other sensor nodes in a cluster of it.

In thisway, time synchronous information spreads through out the
network, and all sensor nodes are synchronized.

5. SIMULATION RESULTS

ȷ

1X 2
ei
n i=1

x̄ − xi ,1 − |x̄ − xi |,(9)|x̄ − xi | < 0.5(10)otherwise

where n is the number of nodes, xi is the phase of sensor
node i, x̄ is the phase average of the largest group, and ei isthe error between xi and x̄. Reliability of data was veriedby using condence interval of 95% with 400 trials.

5.1

Network Scalability

In sensor networks, lots of devices can be deployed over awide area, so it is important for synchronous technique tobe able to synchronize networks of various size.

Figure 1

shows how the size of the network aects each synchronization mechanism.

Figure 1(b), 1(c) shows that multi-hop

RBS establishes precise synchronization in a short time inhigh node density environments. However, multi-hop RBS
loses a signicant number of synchronized nodes as the density of sensor nodes decreases (Figure 1(a)).

By contrast,

PCO shows stable performance. This is because of the lackof connectivity of multi-hop RBS compared with PCO. It
is necessary for RBS to communicate between the sensor
nodes on dierent edges of a cluster, and the radius of acluster is limited to half of transmission range. Thus, PCO
and multi-hop RBS show relative performance advantages

In this paper, two versions of the simulation program thatover each other based on network environment, and which

operate at higher layer above CSMA/CA were formulated,

technique is used should be decided based on the application

one with PCO and one with multi-hop RBS. The perfor-

and node density in which it will be used.

mance of these two versions will now be evaluated and compared. The observation area in which sensor nodes are deployed is circular.

5.2

Robustness to Packet Loss

The parameters that were used in the

Synchronous techniques must be robust to packet loss be-

simulations are shown in Table 1. We use various metrics

cause the radio technology used in a sensor network is fragile

to evaluate the simulation results: the ratio of synchronized

and the packets do not always reach the destination. Fig-

nodes, the probability of synchronization, the time to syn-ure 2 shows the eects of packet loss on the two synchronous

chronization, and the clock variance.

methods. Almost all sensor nodes can be synchronized by

In the PCO program, contrary stimuli can be given mutu-

both synchronous techniques even in unstable environments

ally and a completely synchronous state can collapse because

where packet loss occurs frequently. This is because PCO

the network that reached the synchronous state was unsta-

compensates for the eects of packet loss by causing sensor

ble.

nodes to give repeated mutual stimulation, and multi-hop

Therefore, we consider a network synchronized when103Time to synchronization [sec]

0.8
0.6
0.4
0.2
PCO
multi-hop RBS

10

101
100

50
100
150
200
250
Radius of monitoring region [m]

10

300

(a) PCO can synchronize all sensor nodes in a much wider monitoring region than multi-hop RBS

10-3
10-3
10-4
10-5
10-5

PCO
multi-hop RBS

-1

0
0

10-2

2

Clock variance

Ratio of synchronized nodes

1

0

50
100 150 200 250
Radius of monitoring region [m]PCOmulti-hop RBS

10-6
300

(b) Multi-hop RBS is not able
to synchronize a network where
the radius of monitoring region islarger than 110m

050
100 150 200 250
Radius of monitoring region [m]300(c) Multi-hop RBS can accurately
synchronize a network in a smallmonitoring region

Figure 1: Evaluation over the size of the monitoring region

ACKNOWLEDGMENTS

Probability of synchronization1
0.8

This research was supported in part by  Special Coordina-

0.6

Project and Grant-in-Aid for Scientic Research (contracttion Funds for Promoting Science and Technology: Yuragi
number (C) 19500060) of the Ministry of Education, Cul-

0.4

ture, Sports, Science and Technology.

0.2
PCO
multi-hop RBS
000.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4
Packet loss

7.

REFERENCES[1] I. Akyildiz, W. Su, Y. Sankarasubramaniam andE. Cayirci. Wireless sensor networks: A survey.
Computer Networks, 38:393422, 2002.

Figure 2: Packet loss performance. Only few sensor nodes
are out of synchronization in multi-hop RBS due to expanding of the error caused by the packet loss

[2] F. Sivrikaya and B. Yener. Time synchronization insensor networks: A survey. IEEE Network Magazine,
18(4):4550, 2004.
[3] N. Wakamiya and M. Murata. Synchronization-based
data gathering scheme for sensor networks. IEICE
Trans. on Commun., E88-B:873881, 2005.

RBS retransmits the packet if the ACK packet is not re-[4] J. Elson, L. Girod and D. Estrin. Fine-grained network

turned. However, in multi-hop RBS, almost all sensor nodes

time synchronization using reference broadcasts. In

can be synchronized, but it is dicult for all sensor nodes

Proceedings of Operational Systems and Design

to carry out a complete time synchronization since the syn-

Implementation (OSDI), pages 147163, 2002.

chronous error produced by the packet loss within the cluster[5] S. Barbarossa and G. Scutari. Bio-Inspired Sensor

increases by a synchronous time spreading between clusters
by multi-hop communications. For these reasons, it is foundthat PCO is eective in an unstable communication environment and complete time synchronization is needed.

Network Design. IEEE Signal Processing Magazine,
24:26-35, 2007.
[6] R. E. Mirollo and S. H. Strogatz. Synchronization ofpulse-coupled biological oscillators. Journal on
Applied Mathematics, 50(6):16451662, 1990.

6. CONCLUSION
We comparatively evaluated two time synchronization techniques, PCO and multi-hop RBS, from the viewpoint of
scalability and robustness to packet loss in considerationof delay by CSMA/CA. We found that, bio-inspired timesynchronization control with PCO, can achieve very stable
time synchronization regardless of radio quality over a wide
observation area. We also found that multi-hop RBS, centralized time synchronization control, can establish highly
precise time synchronization in a short time at high nodedensities, and in high radio quality environments. We leave
to future work the discussion of the energy eciency of bioinspired synchronization method.

[7] Y. W. Hong and A. Scaglione. A scalable
synchronization protocol for large scale sensor
networks and its applications. IEEE Journal on
Selected Areas in Commun., 23(5):10851099, 2005.
[8] S. F. Bush. Low-energy sensor network timesynchronization as an emergent property. In
Proceedings of the 14th ICCCN, pages 9398, 2005.
[9] G. Werner-Allen, G. Tewari, A. Patel, M. Welsh and
R. Nagpal. Firey-inspired sensor network
synchronicity with realistic radio eects. In
Proceedings of the 3rd ACM SenSys '05, pages
142153, 2005.