IEICE Electronics Express, Vol. , No. , 1–12

Self-organizing timing allocation mechanism in distributed
wireless sensor networks
Hisa-Aki Tanaka1 , Hiroya Nakao2 , and Kenta Shinohara1
1

Department of Electric Engineering, The University of Electro-Communications
1-5-1 Chofugaoka, Chofu-shi, 182-8585, Japan2
Department of Physics, Kyoto University, Kyoto 606-8502, Japan

Abstract:
A novel, distributed timing allocation method [2, 3, 4, 5] has been
proposed for packet collision avoidance in wireless sensor networks recently. In this paper, this proposed method is theoretically examined,
and a hidden self-organization mechanism is unveiled. As the result,some important fundamental questions regarding this method are reasonably resolved. Namely, our present analysis provides a deﬁnite criterion, as to when it functions properly for densely connected networks
in real noisy environments.
Keywords: nonlinear dynamics, self-organization, wireless sensor network
Classiﬁcation: Science and engineering for electronics
References[1] D. Estrin, R. Govindan, J. Heidemann, and S. Kumar, Next Century
Challenges: Scalable Coordination in Sensor Networks, ACM MobicomConference, Seattle, WA, Aug. 1999.
[2] H. Tanaka, talk at symposium session in 2003 autumn meeting of physicalsociety of Japan. PPT slides are available at http://synchro3.ee.uec.ac.
jp/literature/butsuri20030922.pdf .
[3] M. Date, H. Tanaka, and Y. Morita, Japanese patent number 417389,
19th Sept. 2003 (ﬁling date). Summary is available at http://www.jtokkyo.com/2005/H04L/JP2005-094663.shtml (in Japanese).
[4] Y. Kubo and K. Sekiyama, Communication Timing Control with Interference Detection for Wireless Sensor Networks, EURASIP Journal
on Wireless Communications and Networking, Vol. 2007, 2007.
[5] Summary is available at http://www.soumu.go.jp/main sosiki/joho tsusin/
scope/event/h20yokousyu/session1/network3.pdf (in Japanese).
[6] Y. Kuramoto, Chemical Oscillations, Waves, and Turbulence, Berlin,
Germany: Springer, 1984; Lecture Notes in Physics, 1975, vol. 39.
[7] K. Okuda, “Variety and generality of clustering in globally coupled oscillators,” Physica D, Vol.63, pp. 424–436, 1993.

c°IEICE 2009

1

IEICE Electronics Express, Vol. , No. , 1–121

Introduction and motivation of the study

Wireless sensor networks (WSNs)[1] are now utilized for a variety of distributed sensing purposes; indoor, outdoor, mobile commerce and even inbody monitoring applications. They are usually made up with wireless sensor
nodes; small, cheap, and resource limited devices sensing the environmentand communicating with each other. In such WSNs, one of the challenging
and important design principles is the idea of scalability, which means thatthe function of WSNs should not be inﬂuenced when the number of sensor
nodes is arbitrarily varied even time-dependently. Therefore, communication protocols for WSNs generally require distributed, adaptive, and even aself-organizing mechanism.
As mentioned above, each sensor node (SN) is generally resource limited,so each SN usually shares a common communication band with other SNs.
This means that if multiple communications take place simultaneously in aWSN, they interfere with each other, and, in the worst case, data packets
collide with each other and can be lost in the network. Hence, for WSNs, it
is essential to avoid collisions of data packets in advance.
Two major approaches have been developed for collision avoidance inWSNs: carrier sense multiple access with collision avoidance (CSMA/CA)and (distributed versions of) time division multiple access (TDMA). However, neither of these methods is perfect for the following reasons. Namely,
CSMA/CA requires that the density of SNs is relatively low and the traﬃc
is not so heavy. Also, TDMA requires global timing synchronization of allSNs, as well as computation and communication overheads in each SN, toallocate the communication timings in advance.
Motivated by the above mentioned situation, an alternative collision avoiding method has been proposed recently [2, 3], which is expected to meet theneed for more ﬂexible techniques with less communication overheads. The
original idea of this method comes from a certain self-organizing mechanismof timing allocation process, which will be analyzed in this paper. Improvements of this method have been continued for these several years [4, 5]. However, we have not been able to explain why this method generates the correct
timing allocations for SNs clearly. This paper reveals the hidden mechanism
behind the presented method [2, 3, 4, 5], and explains why this method functions properly, for the ﬁrst time. Also, some new ﬁndings are provided, which
are useful for further applications of this method.
2Framework of the distributed timing allocation method

In this paper, we consider a simple, realistic situation of a WSN with N
sensor nodes (SNs) being located in a single small room, as shown in Fig.
1(a). Here, each SN can communicate with all other SNs, as its range of
wireless communication is supposed to be several tens of meters. Namely, inthis particular example, the network has a densely connected topology. Itshould be emphasized that such densely connected (sub)networks are often
embedded in a widely distributed multi-hop network. Therefore, the followc°IEICE 20092IEICE Electronics Express, Vol. , No. , 1–12

ing analysis of the densely connected network provides an essential building
block for understanding more general, widely distributed networks.
Here, we assume that each SN periodically transmits a timing beacon(and a data packet if it has any sensing data at this stage) to other SNs,
which can be a short pulse whose timing information is expressed as thetiming of transmission in itself. Also, we denote the period of transmissions
as T . Since each SN communicates periodically, it is convenient to introduce
a phase variable φ(t) (∈ [0, 2π]) for each SN. Then, for the i th SN in thenetwork, we can identify its instantaneous timer value as φi (t), and it isnaturally assumed that φi (t) increases as φi (t) = 2π
T t + φi (0). Namely, theinstantaneous state of each SN is mapped to a rotating phase point ‘◦’ onthe circle as shown in Fig. 1(b) or 1(c). In addition, we assume that each SN
transmits a timing beacon (and a data packet) when its φi (t) value becomes
0. From this coordination of φ(t), it is now clear that a reasonable allocationof transmission timings for N SNs can be either a uniformly distributed
pattern of Fig. 1(b), or an evenly clustered pattern of Fig. 1(c), because
each SN is able to avoid packet collisions by using such allocated timings,
which is similar to the ones in TDMA. One simple way for obtaining suchtiming allocations is given as follows. For each φi that evolves according todφi2πdt = T (≡ ω), we introduce mutual interactions between the i th and j thSNs. Since this interaction between i th and j th SNs is uniquely coordinatedby the phase diﬀerence of φi −φj , we assume that the interaction is expressedby a function Γ(φi − φj ) as shown in Fig. 1(d). Then, one possible modelingof the timing allocation process can be given asN√d1 ∑φi (t) = ω +Γ(φi − φj ) + 2Dξi (t),dt
N j=1(i = 1, ..., N ),(1)

where Γ is the 2π-periodic function of φi − φj , and ξi is the external noise
whose intensity is given by the parameter D (D = 0 for the noiseless case).
See [2, 3, 4] for more detailed and extensive descriptions of this modelling.
In Eq. (1), 1/N is a normalization factor, which is necessary in taking thelarge N limit properly. We note that the functions Γ in Fig. 1(d) have a‘repulsive’ eﬀect on any pair of i th and j th SNs. Namely, each pair of SNs
tends to avoid having similar values of φi (t) and φj (t) at any moment, whichis nothing but the collision avoidance.
This idea and its simulation results were presented at [2], and then soonlater applied for the patent of [3]. Since then, its improvements and further
applications have been presented (see [4], for example), and even experimental veriﬁcations have been recently conducted in real environments [5]. For allthese progresses, the very essential questions have remained to be unsolved,
which are listed as follows. (i) How does the allocation process of Eq. (1)lead to reasonable patterns such as in Fig. 1(b) or Fig. 1(c)? (ii) How can wechoose the function Γ so as to obtain the speciﬁc pattern of Fig. 1(b) or Fig.
1(c)? (iii) To what extent is the presented method robust to the external
noises ξi (t)?
c°IEICE 2009

3

IEICE Electronics Express, Vol. , No. , 1–12

It should be emphasized that these questions are important, as they represent the unknown self-organizing mechanism of the presented method.

Q

V2

P

T03

R

U 2(a)312SU4QV

W(b)56--++/4/20.5Ó)

W

R

S

P

130228 7(c)(T0-0.5-1- /2 - /4Ó0(d)

Fig. 1. (a) Sensor networks of N nodes (N = 8, for instance). (b), (c) Resulting timing allocation for
type1 and type2 functions, and (d) Function Γwith a tuning parameter a (blue line); type1 function (green line, a = 0), type2 function (red line,a = d)3

Systematic simulations and analysis

To answer these questions systematically, we introduce the following familyof the function Γ,Γ(φ) = −φ+dφφ−d(−d ≤ φ < −a),(|φ| ≤ a), −(a < φ ≤ d),d−aad−a(2)and Γ(φ) = 0 for d < |φ| < π, as shown in the graph in Fig. 1(d), andconsider the eﬀect of external noise by tuning a and D. The constant d(0 ≤ d ≤ π) in Eq. (2) determines the range of phase interaction for eachSN, and the parameter a (0 ≤ a ≤ d) tunes the shape of Γ. Then, this familyof the function Γ includes both the type1 and type2 functions as the a → 0
and a → d limits, respectively, as in Fig. 1(d). Note that these two speciﬁcfunctions have already been considered in [4] and in [2, 3], respectively.
First, we present results of systematic simulations for timing allocations
from Eq. (1). Without loss of generality, we can put ω = 0 in Eq. (1) bymoving to a rotating frame and redeﬁning the phase variables as φi +ωt → φifor all i. In addition to direct simulations of Eq. (1) for ﬁnite N , we also
perform numerical simulations of the corresponding nonlinear Fokker-Planckequation [6],∂∂
P (φ, t) = −∂t∂φc°IEICE 2009{[∫ 2π0]}Γ(φ − θ)P (θ, t)dθ P (φ, t) + D∂2P (φ, t),∂φ2(3)

which can be derived from Eq. (1) in the N → ∞ limit. This describes thedynamics of the one-body probability density function (PDF) P (φ, t) of thephase φ of any oscillator at time t, and this P (φ, t) indicates how the allocated timings φi (t) are distributed on the circle of [0, 2π] in the N → ∞limit. Thus, P (φ, t) is 2π-periodic in φ as P (φ + 2π, t) = P (φ, t) and normal∫
ized as 02π P (φ, t)dφ = 1. Note that Eq. (3) always has a uniform stationarysolution, P0 (φ) = 1/2π, corresponding to the uniform state. However it may
be unstable and cannot be observed in some situations, reﬂecting non-trivial
dynamics of Eq. (1). Here, we also note that Eq. (1) has been analyzed
and phase clustering behavior due to certain repulsive interactions have been4

IEICE Electronics Express, Vol. , No. , 1–12

demonstrated in [7]. However, [7] focuses on the noiseless situation, whereas
our present analysis is for real environments with noises and for distinct classof phase coupling functions with extremely simple functional forms.
In the following simulations, we ﬁx the constant d as π/2 for instance,and vary the parameter a. Figure 2(a) shows typical snapshots of the phasevariables for the type1 (a = 0) and type2 (a = π/2) functions obtained bydirect numerical simulations of Eq. (1) with N = 500 and D = 0.01 of smallnoise, starting from random initial conditions. The resulting phase variables
φi (i = 1, ..., 500) at t = 100 are almost uniformly spread in [0, 2π] for thetype1 function (black crosses), whereas they are split into several groups (4clusters in this example) for the type2 function (red circles). Figure 2(b)compares normalized phase histograms obtained from Eq. (1) with the stationary PDFs from Eq. (3) for several values of a, showing good agreement.
The phase is uniformly distributed over [0, 2π] for relatively small values ofa (e.g. a = 0, black crosses in Fig. 2(b)), whereas they exhibit regularlyaligned peaks for larger values of a (e.g. a = 1.2 and π2 , blue circles andred triangles, respectively in Fig. 2(b)), reﬂecting the formation of phaseclusters. Thus, the system undergoes a transition from the uniform state ofP0 (φ) = 1/2π to clustered states as the parameter a is increased.
(a)2(b) d1.5(c)
clusteredi

PD F

1.0

d/2

uniform

0.5

a000.0100 200 300 400 500i0020D

0.01

0.02

Fig. 2. (a) Typical snapshot of phase variables φi fromEq.(1) for the type1 and type2 functions. (b) Normalized histograms and PDFs of φ. Data points
and curves are respectively obtained from Eq. (1)and Eq. (3), showing a good match. (c) Stability
diagram of the uniform state and observed patterns.

c°IEICE 2009

To understand this observed transition, we perform a linear stability analysis of the uniform state by applying a small perturbation q(φ, t) to theuniform solution P0 (φ) = 1/2π and examining whether this perturbation decays or not. Substituting P (φ, t) = P0 (φ) + q(φ, t) into Eq. (3), a linearized
equation of q(φ, t) is easily obtained. Expanding q(φ, t) and Γ(φ) into Fourier∑
imφ Γ with q (t)imφ q (t) and Γ(φ) = ∑∞series as q(φ, t) = ∞mmm
m=−∞ em=−∞ eand Γm being Fourier coeﬃcients, this linearized equation of q(φ, t) is decomposed into linear equations of the form q̇m (t) = (−imΓm − Dm2 )qm (t) form = −∞, · · · , +∞. Thus, for each qm , the real part of the linear growth(I)(I)
rate λm is given by λm = mΓm − Dm2 where Γm is the imaginary part ofΓm . The uniform solution P0 (φ) is linearly stable if λm is negative for all m(except λ0 that is constantly zero). If λm is positive at some values of m, the5IEICE Electronics Express, Vol. , No. , 1–12

uniform solution is destabilized and the corresponding Fourier modes grow.
By calculating Γm from Eq. (2), the growth rate λm is explicitly obtained,λm =dπ(d − a)(sin md sin ma−mdma)− Dm2 (m = −∞, · · · , ∞).
((4))

md
Then, in the type1 limit (a → 0), we obtain λm = − π1 1 − sinmd− Dm2 .
Clearly, λm is always negative for any m (except λ0 being 0), so the uniform( state is stable.
) On the contrary, in the type2 limit (a → d), λm =1sin mdcos
md−− Dm2 is obtained, which becomes positive when m isπ
mdnear 2π/d and its integer multiples, for small D. Therefore, the uniform state
does become unstable and the clustered states may possibly be organized. In
between these two limits, there exists a critical value of a at ac , where theuniform state changes its stability. Note that the noise always tends to stabilize the uniform state, and, if D is suﬃciently large, no mode of m becomes
unstable even in the type2 limit. Therefore, a critical value Dc of the noise
intensity D also exists.
Figure 2(c) shows a stability diagram of the uniform state, together withthe observed stationary patterns from direct numerical simulations of Eq. (1).
The red thick curve represents the set of critical parameter pairs (ac , Dc )where the uniform state changes its stability. Note that this curve is obtained
from the condition that λm = 0 for all m, and in the upper region (colored ingreen) of this curve, λm > 0 is always satisﬁed for some m. Also, the resultof direct simulations of Eq. (1) for N = 100 nodes is plotted on each grid inFig. 2(c). Filled marks with color indicate phase-clustered states (◦ in blue:4-cluster, ∆ in yellow: 5-cluster, and 3 in violet: 9-cluster) and crosses (×in black) indicate the uniform state. We see that cluster states are actuallyformed in this region of a and D where λm is positive and the uniform stateis unstable (slight discrepancy is due to ﬁnite-size eﬀect).
The above facts reveal the self-organizing mechanism behind the presented method, so reasonable answers are thus provided for the three basic
questions posed in the chapter 2.

4Conclusions

In this paper, we have revealed the self-organizing mechanism in the timing
allocation method [2, 3, 4, 5] for densely connected WSNs. Theoretical andpartly numerical results obtained here provide useful guidelines leading toproper functioning of the proposed method. More speciﬁcally, to the question (i) posed in the end of chapter 2, the linear stability and the associatedmode analysis of Eq. (3) provides reasonable understanding of this mechanism. Also, to the question (ii) and (iii), the theoretically obtained criterion
shown in Fig. 2(c) gives a useful information, which is expected to provide
further application of the proposed method.
In addition to such practical signiﬁcance of the result, the analysis here
sheds a new light on the uncovered side of synchronization phenomena, longforgotten since [7]. Further analysis and experiments are expected to explore
this new area of researches in distributed systems.
c°IEICE 20096