IEICE TRANS. COMMUN., VOL.E95–B, NO.5 MAY 2012

1529

PAPER

Special Section on Frontiers of Information Network Science

Proposal for Autonomous Decentralized Structure Formation Basedon Local Interaction and Back-Diﬀusion Potential∗
Chisa TAKANO†a) , Masaki AIDA†† , Members, Masayuki MURATA††† , Fellow, and Makoto IMASE††† , Member

SUMMARY
Clustering technology is very important in ad hoc networks and sensor networks from the view point of reducing the traﬃc loadand energy consumption. In this paper, we propose a new structure formation mechanism as a tool for clustering. It meets the key clustering requirements including the use of an autonomous decentralized algorithm and aconsideration of the situation of individual nodes. The proposed mechanism follows the framework of autonomous decentralized control basedon local interaction, in which the behavior of the whole system is indirectly controlled by appropriately designing the autonomous actions of thesubsystems. As an application example, we demonstrate autonomous decentralized clustering for a two-dimensional lattice network model, and thecharacteristics and adaptability of the proposed method are shown. In particular, the clusters produced can reflect the environmental situation of eachnode given by the initial condition.
key words: autonomous decentralized control, diﬀusion equation, clustering, network configuration, structure formation, local interaction

1.

Introduction

Mobile ad hoc networks (MANETs) and sensor networks
are intended to work without a preset communication infrastructure and are attracting a great attention as communication tools that are useable in areas that have been subject
to a severe disaster, in addition to their use at event sites. In
order to utilize the infrastructure-free property and the flexibility of these networks, self-configuring mechanisms forthe networks are essential. In particular, the ability to produce a well-ordered network configuration from a chaotic
situation is a requirement. This paper focuses on a clustering mechanism to provide a self-configuring mechanisms. It
is applicable to clustering for hierarchical routing.
Many routing technologies for MANETs have been
proposed and discussed. The representative flat-type routing technologies in MANETs are classified as either proactive schemes [3], [4] or reactive schemes [5], [6]. Bothare eﬀective if the MANET does not have many mobile
nodes. As the network size grows, however, these protocols have the problem that the size of the routing table
Manuscript received September 15, 2011.
Manuscript revised December 22, 2011.
†
The author is with the Graduate School of Information Sciences, Hiroshima City University, Hiroshima-shi, 731-3194 Japan.
††
The author is with the Graduate School of System Design,
Tokyo Metropolitan University, Hino-shi, 191-0065 Japan.
†††
The authors are with the Graduate School of Information
Science and Technology, Osaka University, Suita-shi, 565-0871
Japan.
∗
Earlier versions of this paper were presented at IEEE Globecom 2010 Workshops [1] and SAINT 2011 Workshop [2].
a) E-mail: takano@hiroshima-cu.ac.jp
DOI: 10.1587/transcom.E95.B.1529

stored at each individual node becomes large. As a result,the flooding overhead of route requests increases the network load. To counter this problem, a large number of studies have looked at hierarchical routing based on clustering[7]–[9]. In hierarchical routing, mobile nodes are divided
into diﬀerent virtual groups (clusters) and routing is basedon intra-cluster and inter-cluster calculations. Here, clusterhead candidate selection is one of the important issues inclustering schemes, and some authors [10], [11] have proposed algorithms to select cluster-heads appropriately in accordance with network conditions. However, since their algorithms require non-local information, they are not strictly
autonomous decentralized algorithms.
The common basic attribute demanded from these algorithms in addition to locality is adaptability to the network environment. Each node has its specific situation that
influences the formation of clusters. So, it is preferable
for the clustering mechanism to take the situations of individual nodes into consideration. In addition, the following
flexibility is required. When there is no cluster-head candidate in the neighborhood, the mobile node itself stands
as a candidate and becomes a cluster head. On the other
hand, when there are two or more clusterhead candidates,
we need a highly eﬀective and eﬃcient metric to implement
optimal cluster-head selection. Examples of the possible
node-specific conditions include node degree, cluster size,
mobility speed, and battery energy [12].
In this paper, we introduce an autonomous decentralized clustering method that allows the nodes to act flexibly in a manner based only on the information each individual node is aware of, i.e. its individual situation. As aconcrete way to compose such a clustering mechanism withautonomous and flexible properties, we adopt the strategy
introduced by our framework for autonomous decentralized
control based on local interaction [13]; it is a novel control
mechanism for communication networks.
This framework is based on the relation between local
interaction and the solution provided by a partial diﬀerential equation. In this framework, the desired behavior of
the whole system is achieved by appropriately designing theautonomous operation of the subsystems; local action rules,
which exist at the micro-level, are used to achieve the required state of the whole system at the macro-level. To apply this framework, we proposed flow control based on thediﬀusion equation, and have confirmed the achievement ofcongestion avoidance [14]–[16]. Our clustering method isbased on our framework. However, unlike the previous au-

c 2012 The Institute of Electronics, Information and Communication Engineers
Copyright IEICE TRANS. COMMUN., VOL.E95–B, NO.5 MAY 2012

1530

tonomous algorithm, the clustering proposal of this paper
can autonomously produce spatial structures of finite size.
This paper consists of the following sections. In
Sect. 2, we present the framework of our proposed autonomous decentralized technology. Section 3 describes related work. In Sects. 4 and 5, we introduce the renormalization transformation of the diﬀusion phenomenon for a onedimensional network model and propose an autonomous decentralized structure formation whose goals include a finite
spatial size. In addition, to apply this method to a general
network topology, we extend the one-dimensional networkmodel to a general network in Sect. 6. We evaluate the characteristics of the proposed method in Sect. 7, while Sect. 8
gives the concluding remarks.
2.

Framework for Autonomous Decentralized Control
Based on Local-Interaction

In this equation, when the initial condition of the density distribution p(x, 0) = δ(x − x0 ) is a δ function at x = x0 ,we get the solutionp(x, t) = N(x − x0 , 2κt),

(4)

where
x2
1
N(x, σ2 ) = √e− 2σ2 .
2πσ2(5)N(x, σ2 ) denotes the density function as a normal distribution with mean = 0 and variance σ2 .
As (3) is a linear diﬀerential equation, we can obtain
the general solution by superposing the normal distribution
under even more complex initial conditions p(x, 0) = p(x).
This yields the following general solution: +∞N(x − y, 2κt) p(y) dy.
(6)p(x, t) =−∞This section briefly summarizes the concept and the framework of our autonomous decentralized control based on local interaction.
2.1 Local Interaction and Partial Diﬀerential Equation
Let us consider the one-dimensional diﬀusion phenomenon
as an intuitive example of local interaction. When we let a
few drops of black ink fall into a glass tube filled with water, the ink density distribution follows a normal distribution
and the ink spreads throughout the whole tube by diﬀusion.
In this process, the action within a minute region of waterin the glass tube is very simple: the ink diﬀuses from thehigher density side towards the lower density side. The rateof ink diﬀusion is proportional to the density gradient. Even
though each segment acts autonomously and only local information is available, the ink density distribution throughout the glass tube eventually exhibits orderly behavior.
Let the density function (density distribution) of a certain quantity at time t and position x be p(x, t). In the diﬀusion phenomenon, the flow J(x, t) of that quantity at time t
and position x is expressed as
J(x, t) = −κ∂p(x, t),∂x(1)where κ (> 0) is a positive constant. This equation meansthat the quantity flows at a rate that is proportional to thegradient of the density. When that quantity is not created
and annihilated from this system, the continuous equation,∂p(x, t)∂J(x, t)
=−
,
∂t
∂x

(2)

holds. From (1) and (2), we get the following equation as
the temporal evolution of the density distribution:∂p(x, t)∂2 p(x, t)
=κ
.
∂t
∂x2
This is the well-known diﬀusion equation.

(3)

2.2 Principle of Autonomous Decentralized Control
Based on Local Interaction
We can consider a system that is based on local interaction
as a sort of autonomous decentralized control. The diﬀusion phenomenon is a typical example of this framework. In
other words, while the subsystems run autonomously using
only local information, the state of the whole system evolves
into the intended orderly behavior indirectly. Our implementation of the autonomous decentralized control based onsuch local interaction can be summarized as follows:• Let us consider the behavior that the state of the wholesystem should have (for example (4) or (6)).
• We then find the partial diﬀerential equation whose solution yields the desired behavior (for example (3)).
• Let us identify the local interaction that the partial differential equation describes (for example (1)). We thendesign the subsystem behavior to reproduce the required
local interaction.
• As a result, even though the autonomous action of eachsubsystem is based only on the local information that isavailable to it, the state of the whole system exhibits thedesired behavior as a solution of the diﬀerential equation.
It is generally known that autonomous decentralized systems may become dead locked if the subsystems are not designed properly. Our framework of autonomous decentralized control based on local interaction avoids this problem
and gives us a hint as to how to design the local actions ofsubsystems in such a way that the whole system is pushed
into the desired state. Our autonomous decentralized control approach may be summarized as follows: “by designing
the behavior of subsystems at the micro-scale properly, we
indirectly realize the desired behavior of the whole systemat the macro-scale”.
3.

Related Works

As an example of autonomous decentralized control based

TAKANO et al.: PROPOSAL FOR AUTONOMOUS DECENTRALIZED STRUCTURE FORMATION

1531

on local interaction, we have already proposed a diﬀusiontype flow control (DFC) mechanism [14]–[16] that is basedon diﬀusion phenomena and is suitable for fast recovery
from congestion. In this control mechanism, the state of
the whole network is controlled indirectly through the autonomous actions of each node. Each node manages its local traﬃc flow on the basis of only the local information
directly available to it, by using predetermined rules. By applying DFC, the distribution of the total number of packets
in each node in the network becomes uniform over time, andthe network exhibits orderly behavior.
In contrast to DFC, in this paper we consider a new application of autonomous decentralized control based on local interaction that forms structures with finite spatial size.
An example of our application includes autonomous decentralized clustering in sensor networks or ad hoc networks.
Many protocols addressing the issue of clustering inwireless sensor networks have been proposed [17]. As
an autonomous decentralized structure formation, the bioinspired approach is well known [18], [19]. This approach
can create spatial structures in the sensor network by using the Turing pattern created from reaction-diﬀusion equations. This approach is based on a biological pattern formation model [20] in which two variables, that is the activation factor (activator) and the inhibiting factor (inhibitor),
are modeled by diﬀerential equations, and a spatial pattern isformed by the eﬀects of both the activator and the inhibitor.
Since this approach needs to consider the temporal evolutionof the two variables, there are many parameters to adjust; in
one case, [18], there are seven parameters. In general, it isdiﬃcult to identify the appropriate values for these multiple
parameters to yield the intended behavior. Parameter searchtechnology is itself a research topic for reaction diﬀusion
systems [21]. As we will see in Sect. 7, our proposed approach can form spatial structures that take account of network conditions by using relatively few parameters.
4.

Renormalization Transformation of the Diﬀusion
Phenomenon to Suit Autonomous Decentralized
Control

Up to this point we have referred to the diﬀusion eﬀect as
an example of autonomous decentralized control based on
local interaction. We now turn to consider autonomous decentralized control for creating spatial structures with finite
size for patterns other than that typifying the diﬀusion eﬀect.
4.1 The Temporal Evolution of Renormalization Transformation of the Diﬀusion Phenomenon
When we calculate the temporal evolution of density distribution p(x, t), which is the solution of (3), while simultaneously shrinking√ (scaling down) the x axis simultaneously by
the ratio of 2κt/σ, we get the density distribution q(x, t) as
follows (Fig. 1):√⎛√⎞
2κt ⎜⎜⎜ 2κt ⎟⎟⎟⎜p⎝x, t⎟⎠ ,q(x, t) :=(7)
σ
σ

Fig. 1

Renormalization transformation of diﬀusion phenomenon.

where σ is a positive constant. Carrying out both the temporal evolution (diﬀusion) and the scaling at the same time
can be regarded as a kind of renormalization transformationof the density distribution p(x, t). The temporal evolution
equation of the new density distribution q(x, t) is given by∂2∂
1 ∂q(x, t) =x + σ2 2 q(x, t).
∂t
2t ∂x
∂x

(8)

The solution of this diﬀerential equation is the following
limiting distribution:x2
1
lim q(x, t) = N(x, σ2 ) = √e− 2σ2 .
t→∞
2πσ2

(9)

This limiting distribution comes from the fact that the solution of the diﬀusion equation (3) approaches a normal distribution asymptotically with time regardless of the initialconditions.
By use of this mechanism, we expect to realize a newautonomous decentralized control that can produce structures with finite spatial size. However, using (8) instead of(3) raises two problems with regard to autonomous decentralized control.
• The existence of 1/(2t) on the right hand side of (8)causes a slowing down of the change in the distribution
over time.
• The fact that the drift term of (8) explicitly depends on x
makes it necessary to set a coordinate system in the network.
We consider the latter problem in a following section.
Let us now discuss the transformation of the timescale.
The distribution q(x, t) in (8) should have a fast temporal
evolution so that 1/(2t) on the right hand side of (8) can beeliminated.
If we use a constant, c > 0, instead of 1/(2t) in (8), thetemporal evolution is expressed as∂∂2∂
q(x, t) = c
x + σ2 2 q(x, t).
∂t
∂x
∂x

(10)

The corresponding solution q(x, t) is given by redefining therenormalization transformation as,⎛√⎞√⎟2κe2ct ⎜⎜⎜⎜ 2κe2ct
2ct ⎟
p ⎜⎝
x, e ⎟⎟⎟⎠ .
q(x, t) :=(11)σσHere, the limiting distribution (9) is invariant under the redefinition of the renormalization transformation, because
e2ct → ∞ when t → ∞.

IEICE TRANS. COMMUN., VOL.E95–B, NO.5 MAY 20121532

It is necessary to specify the flow corresponding toJ(x, t) of the continuous equation,∂∂q(x, t) = − J(x, t),∂t∂x
if we are to associate (10) with autonomous decentralized
control. J(x, t), which satisfies this equation, is expressed as∂
J(x, t) = −c x q(x, t) − c σq(x, t),
∂x
2

(12)

where c denotes the rate of temporal evolution of the density distribution and σ2 denotes the variance of the normal
distribution that is converged on. By the way, the temporal
evolution Eq. (10) obtained by the renormalization transformation (11) describes the Ornstein-Uhlenbeck process [22].
For the reason given above, if we make the local action ofeach node follow (12), the limiting distribution is given by(9), regardless of the configuration of the initial distribution.
(9) is a normal distribution that is centered on x = 0 and hasvariance σ2 , and so it is necessary to decide a special point(the origin of the coordinate system where x = 0) in the network and the coordinate system. The next section describes
a method for designing autonomous decentralized control
schemes that do not depend on any coordinate system.
5.

Design of Local Interaction Based on Back Diﬀusion-Based Potential

As shown in the previous section, the local action of eachnode can be chosen as (12) for a one dimensional network.
However, it requires the introduction of a coordinate systemin the network and specification of the origin of the coordinate system. Since we cannot introduce a globally consistent coordinate system into general networks, a coordinatefree mechanism is required.
Creating a fundamental framework that can create spatial structures with finite size relies on balancing the effect of diﬀusion and drift. Accordingly, we try to keep
this framework and introduce the eﬀect of drift defined ina coordinate-free manner.
In introducing the new coordinate-free drift, we canonly use the information of q(x, t) itself. If we want to use
other information, we should introduce another quantity inthis framework. Therefore, we try to identify the coordinatefree drift defined through q(x, t).
Our approach replaces x, which appears in the drift
term in (12), by some function f (x, t), as follows:
J(x, t) = −c f (x, t) q(x, t) − c σ2∂q(x, t).
∂x(13)Note that this replacement does not make the limiting distribution become a normal distribution (9). Our aim is not
to make a normal distribution but to form a structure with acertain finite spatial size.
The temporal evolution of distribution q(x, t) that corresponds to this replacement is given by∂∂2∂
q(x, t) = cf (x, t) + σ2 2 q(x, t).
∂t
∂x
∂x

(14)

The introduction of f (x, t) eliminates the need to set a coordinate system in the network. As a more intuitive explanation, we consider the potential function Φ(x, t) instead of
the function f (x, t):f (x, t) = −∂Φ(x, t)
.
∂x

(15)

Choosing Φ(x, t) appropriately yields autonomous decentralized control that does not depend on a coordinate system.
In general, in order to determine the potential function Φ(x, 0) that will satisfy a certain global condition, wemust know the macro-scale information related to the entire
system, not the micro-scale information related to the system elements. This is a problem for autonomous decentralized systems that use only local information. To resolve thisproblem, we consider how to determine the drift term fromthe distribution q(x, t), which is local information. Because
the potential function Φ(x, t) should result in maintaining
the distribution within a certain finite spatial size, contrary
to the eﬀect of diﬀusion, Φ(x, t) is, after discrete time Δt,given by
Φ(x, t + Δt) = − q(x, t) − κ

∂2 q(x, t)
Δt ,
∂x2

(16)

where κ > 0 and Φ(x, t) is periodically renewed at Δt interval. The meaning of this equation can be expressed asfollows:• We let the time progression of the diﬀusion phenomenon
with diﬀusion coeﬃcient κ be reversed (back diﬀusion).
• Next, we reverse the distribution (up and down), and regard the completed distribution as the potential.
The temporal evolution of the distribution becomes a flatstate in the forward direction of time for general diﬀusion(Fig. 2). For back diﬀusion, on the other hand, the temporal evolution of the distribution goes against the direction oftime and the shape of the distribution becomes sharper withtime. The phenomenon that is inherent in back diﬀusion, adecrease in entropy, does not occur in the natural world, but
it can be realized easily in the framework of autonomy decentralized control. For (16), the method of generating thepotential Φ(x, t + Δt) by using distribution q(x, t) is shown in
Fig. 3.
Due to the eﬀect of the drift term, including the potential, the peak of distribution q(x, t) is emphasized and the
distribution shape is sharpened. The eﬀect of the diﬀusion

Fig. 2Diﬀusion and back diﬀusion.

TAKANO et al.: PROPOSAL FOR AUTONOMOUS DECENTRALIZED STRUCTURE FORMATION

1533

Fig. 3

Deciding potential Φ(x, t) according to back diﬀusion.

term, on the other hand, is to flatten the distribution. A structure with finite spatial size can be formed by balancing one
eﬀect against the other.
6.

Extension to Arbitrary Network Topologies

To apply the method described in the previous section to anarbitrary network, we take the following steps:• We first extend the one-dimensional model to ndimensional space in preparation for applying it to the
network.
• We next formulate the rule of the autonomous decentralized operation that is independent of any coordinate system, and discretize the operation in accordance with thestructure of networks.
We start with space-coordinates and the diﬀerential operatorof n dimensions, and replace them as follows:x → x := (x1 , x2 , . . . , xn ),∂∂∂∂→ ∇ :=,, ...,,∂x∂x1 ∂x2∂xn
f (x, t) → f (x, t) := ( f1 (x, t), f2 (x, t), . . . , fn (x, t)),J(x, t) → J(x, t) := (J1 (x, t), J2 (x, t), . . . , Jn (x, t)).

Fig. 4is necessary to restrict the coeﬃcient κ which indicates thestrength of diﬀusion. For instance, in the one-dimensional
diﬀusion Eq. (3), when we discretize time and space by Δx
and Δt, respectively, the following condition must be satisfied [23]:
κ

(17)
(18)
(19)
(20)

where  = ∇2 .
Here, it is necessary to confirm that the action rule isindependent of the coordinate system and is determined byonly local information. In addition, the operation rule must
be extended as the action rule in order to be applied to networks. In the following, the impact of the action rule on anarbitrary network is examined concretely.
q which appears in (18) represents the diﬀusion ofq(x, t). A physical meaning of q is the diﬀerence between
the value of q at point x and the mean value of q in thesurroundings of point x; note that it does not depend on any
coordinate system. Therefore, it is possible to determine q
locally for any arbitrary network topology.
Next, we address the diﬀusion coeﬃcient κ := cσ2 .
When the diﬀusion phenomenon is treated as discrete, it

1
Δt
< .
(Δx)2 2

In general, when we discretize n-dimensional space to a lattice space, the diﬀusion coeﬃcient κ needs to satisfyκThis allows us to formally rewrite (13)–(16) as follows:
J(x, t) = −c f (x, t) q(x, t) − c σ2 ∇ q(x, t),∂q(x, t) = c ∇·( f (x, t) q(x, t)) + c σ2 q(x, t),∂tf (x, t) = −∇ Φ(x, t),Φ(x, t + Δt) = − q(x, t) − κ q(x, t) Δt ,Direction of back diﬀusion in a network.

Δt
1
.
<
(Δx)2 2nIn this case, the degree of each node is 2n. Therefore, when
the above condition is generalized to the network, the diﬀusion coeﬃcient should satisfy
κ

Δt
1
,
<
2
2 (maxi di )
(Δx)

(21)

where (maxi di ) is the maximum node degree in the network.
Note that a node with larger degree is more strongly influenced by the diﬀusion eﬀects from adjacent nodes.
Though ∇ and f are vectors and have direction, they
can be defined locally even in an arbitrary network, because
they can be defined for each link.
Next we consider the direction of q in the back diﬀusion shown in (20). Figure 4 illustrates the direction of backdiﬀusion by using contour lines to represent the distribution
value in the network (see the left side of the above figure).
In general diﬀusion, the transfer of the distribution occurs
towards the direction of decreasing distribution value (referto the upper right panel in the above figure). When this is
time-reversed, it becomes the flow shown in the lower left
panel.
However, if the distribution quantity moves to two or

IEICE TRANS. COMMUN., VOL.E95–B, NO.5 MAY 20121534

more nodes, two or more peaks will be emphasized. In orderto prevent flooding of peaks, we define back diﬀusion in
networks as transferring the distribution towards the link of
the steepest ascent direction (refer to the lower right panel inFig. 4)† . Thus, back diﬀusion can be defined based on justthe state of the node and the adjacent nodes.
From the above-mentioned consideration, the action ofeach node can be determined from just the relation between
a node and adjacent nodes, and does not depend on a global
coordinate system. One exception is the diﬀusion coeﬃcientκ, which requires the maximum node degree. However, thisis not a serious weakness because by assuming a suﬃciently
large value of the maximum node degree, the requirement(21) can be satisfied. Therefore, our approach can be applied
to an arbitrary network.
Let us describe the local action rule in the network concretely. First, the set of nodes that are adjacent to node i (setof nodes that are linked to node i) is defined as Ni . In addition, we discretize time, and set the interval time of theautonomous control to be Δt.
In the following, we describe the action rule for spatial
discretization that corresponds to nodes in the network andtime discretization that corresponds to control timing. The
distribution qi (tn ) at time tn (:= n × Δt) at node i changes thenext time (after Δt passes) as follows:diﬀ
qi (tn+1 ) = qi (tn ) − Δt
(22)Ji,driftj (tn ) + Ji, j (tn ) ,Fig. 5

Fig. 6

Direction of the drift eﬀect.

Direction of the diﬀusion eﬀect.

where Ji,backj (tn ) is generated by the back diﬀusion of qi (t),and is the variation in a unit time period in the direction ofnode i → j. The variation Ji,backj (tn ) is given by
⎧
⎪
(tn )
q (t ) − qi (tn ), (Δqmax
⎪
i
⎪
⎨ j n
back
=
q
Ji, j (tn ) = ⎪j (tn ) − qi (tn )),⎪⎪⎩0,(otherwise).

(27)



(tn ) := max max q j (tn ) − qi (tn ) , 0 .
Δqmax
i

(28)

j∈Ni

j∈Ni
diﬀ
where Ji,drift
j (t) and Ji, j (t) are the variations created by thedrift eﬀect and the diﬀusion eﬀect within each unit time,
diﬀ
respectively. Ji,drift
j (t) and Ji, j (t) satisfy the following equations:
c fi, j (tn ) qi (tn ), ( fi, j (tn ) > 0),Ji,drift
(23)
(t
)
:=
n
j
−c f j,i (tn ) q j (tn ), ( f j,i (tn ) > 0),fi, j (tn ) := −(Φ( j, tn ) − Φ(i, tn )),2Ji,diﬀ
q j (tn ) − qi (tn ) .
j (tn ) := −σ

(24)
(25)

Due to the drift eﬀect, the distribution moves in direction i → j ( j → i) in the case of fi, j (tn ) > 0 ( fi, j (tn ) < 0).
Here, equation fi, j (tn ) = − f j,i (tn ) holds. The variation is
proportional to the product of the velocity of the drift fi, j (tn )( f j,i (tn )) and qi (tn ) (q j (tn )) in node i ( j) (Fig. 5). The above
description is formalized by (23).
The variation due to the diﬀusion eﬀect is proportional
to the gradient of the distribution in (25), and the directionof the diﬀusion is shown in Fig. 6.
Next, we explain how to determine the potential Φi (tn )that is related to drift. The potential value of node i at time
tn+1 is decided by the value of the distribution qi (tn ) and theback diﬀusion of qi (tn ) as follows:
⎞
⎛
⎜⎜⎜
⎟⎟⎟


back
back
⎜
Φi (tn+1 ) = − ⎜⎝⎜qi (tn )−κ Δt
Ji, j (tn )− J j,i (tn ) ⎟⎟⎠⎟ ,
j∈Ni

(26)

Δqmax
(tn ) is the diﬀerence between the distribution
ivalue of node i and the distribution value of the adjacentnode j in the direction of the steepest ascent from node i.
(27) explains the back diﬀusion shown in the lower rightpanel in Fig. 4. In the above-mentioned action rule for discretization in the network, local interaction is guaranteed because the summations for nodes j ∈ Ni in the above equations involve only the nodes adjacent to node i.
To achieve the above mentioned control, it is necessary to exchange information about the values of distribution q j (tn ) for the adjacent nodes at the interval of Δt. The
complexity of this information exchange does not dependon network size because the communication range is just 1
hop. Therefore, it is scalable against the number of nodes.
7.

Evaluation

7.1 Evaluation of Autonomous Structure Formation Using
Our Proposed ModelIn this section, we apply our proposed autonomous distributed control technique to achieve clusters with a certain finite spatial size in a sensor network, and evaluate thecharacteristics of the proposed method. We assume a twodimensional lattice model with 100 × 100 nodes to makethe space structure easy to display. The network model has
a torus topology to exclude the influence of the boundary†

Other definitions are of course possible.

TAKANO et al.: PROPOSAL FOR AUTONOMOUS DECENTRALIZED STRUCTURE FORMATION

1535

Fig. 7

Network model.

Fig. 9 Temporal variation of the cluster structure formation for the random initial distribution and cluster structures by color maps that indicate
areas. (σ2 = 0.8 in our proposed model)

Fig. 8Initial conditions (random, Type 1, and Type 2).

Table 1 Parameters in simulation models.
Our proposed model
Neglia model (reaction diﬀusion model)
σ2cκ

0.8, 1.0
0.1
0.1

μ
ν
Da
Dh
ρ0
ρ1
c

0.75 × τ
0.80 × τ
0.000222273 × τ
0.00580619 × τ
0.25 × τ
0.30 × τ
0.50 × τ(Fig. 7). Each node has degree of 4 (maxi di = 4) since eachnode has four neighbors.
We set the initial value of distribution qi (0) at random
and then permit autonomous time evolution. By examiningqi (t) after enough time has passed, we can confirm if the desired spatial structure can be formed from the random statethat has no spatial structure.
The initial state of distribution qi (0) is shown in theleft figure in Fig. 8. The initial distribution qi (0) is set to arandom number uniformly distributed in [0, 1]. The color ofeach node shows the distribution value.
Table 1 shows the parameters used in the evaluation.
Time interval Δt is set to 1. Results for cluster formation
over time for two values of parameter σ2 (0.8 and 1.0) are
shown in the upper row of Fig. 9 and Fig. 10, respectively.
The distributions in these panels indicate autonomous cluster structure formation. We can find a peak of a distribution
by tracing the direction of the steepest ascent from a node.
We consider the node as belonging to the cluster indexed by
the peak node, so all nodes may thus be consistently categorized into their clusters. The proposed method forms clusters autonomously where the number and size of clusters are
determined by parameter σ2 .
The panels in the lower row in Figs. 9 and 10 describe
the same cluster structures by color maps. In the figures “×”denotes a cluster head, and the number of clusters corresponds to the number of cluster heads. As a result, the num-Fig. 10 Temporal variation of the cluster structure formation for the random initial distribution and cluster structures by color maps that indicate
areas. (σ2 = 1.0 in our proposed model)

Fig. 11 Dependence of mean number of clusters on value of σ2 in our
proposed model.

ber of clusters in σ2 = 0.8 and 1.0 evolves as follows:• σ2 = 0.8: 104 (t = 4, 000), 31 (t = 6, 000), 10 (t =10, 000)• σ2 = 1.0: 26 (t = 4, 000), 16 (t = 6, 000), 2 (t = 10, 000)
The number of clusters becomes stable after t = 10000. It
is clear that the number of clusters decreases with time, andwe can see that if parameter σ2 is small, many small clusters
are created.
The mean cluster size and the cluster density are determined by balance between the strength of the diﬀusion eﬀect
and the strength of the drift eﬀect. The impact of changing
σ2 , which represents the strength of the diﬀusion eﬀect, on
the mean number of clusters is shown in Fig. 11, in which
the horizontal axis is σ2 , and the vertical axis is the mean
number of clusters. Figure 11 shows a result after enough

IEICE TRANS. COMMUN., VOL.E95–B, NO.5 MAY 2012

1536

Fig. 13 Comparison of cluster formations yielded by our proposedmodel and Neglia model with initial condition Type 1.

Fig. 12 Temporal variation of the cluster structure formation for the
random initial distribution. (in Neglia model)

time has passed, and the number of clusters becomes stable, at least in our simulation experiments. We can see fromthis figure that increasing σ2 yields fewer clusters. Thus, weare able to design for the approximate number of clusters inadvance, while the cluster structure is formed autonomously
regardless of the network conditions by one local action rulein each node. Hereafter, we use σ2 = 1.0 in our proposedmodel.
Next, we compare our proposed model with the reaction diﬀusion model (Neglia model) [18]. The parameters†
for the Neglia model are shown in Table 1. Time interval Δt
is 1 as described in Sect. 7.1.
The initial value of activator ai (t) and inhibitor hi (t) are
the same and the value of each node in the Neglia model isselected at random as shown in the leftmost panel in Fig. 8.
Figure 12 shows the temporal evolution of the distributionai (t) for the Neglia model. The results show that clusters
are formed at almost equal spatial intervals given suﬃcienttime. The evolution in the number of clusters is 79 (t =2, 000), 37 (t = 10, 000) and 30 (t = 100, 000).
7.2 Evaluation of Clustering Method According to Local
Conditions
Next, we evaluate the structure formation for diﬀerent initial conditions to match certain special situations. First ofall, the two distributions shown in the middle and the rightpanels in Fig. 8 were taken as initial conditions; they arecalled Type 1 and Type 2, respectively.
The initial conditions (Type 1 and Type 2) are as follows. The areas in which the distribution is high and theareas in which the distribution is low are arranged at somespatial interval. These patterns indicate the structure of network condition with regard to the tendency to form clusters.
In the areas wherein the distribution is high, qi (t) is set to a
uniform random number between [0.5, 1.0], and in the areas where the distribution is low, qi (t) is set to a uniform
random number between [0, 0.2]. Note that our setting of
the initial condition is chosen not for making suitable cluster structure. The initial condition is given by environmental
conditions e.g. residual battery power of terminals, the position of power supplies, or the node degree of mobile termi-

Fig. 14 Comparison of cluster formations yielded by our proposedmodel and Neglia model with initial condition Type 2.

nals. Therefore, the structure of clustering should reflect thecharacteristics of the given initial conditions.
The evaluation results for our proposed model and the
Neglia model for initial conditions Types 1 and 2 are shownin Fig. 13 and Fig. 14, respectively. These panels show thecluster structures after suﬃcient time had passed.
The left panel and the panel in the centre are the resultsof our proposed model for σ2 = 0.7 and 1.0, and the rightpanel is the result of the Neglia model. We can see fromthese results that the Neglia model forms a cluster structurewith equal intervals, as in the previous case, even though theinitial condition exhibited a strong pattern.
If we want to make clusters that divide the network into
almost the same size, Neglia model may have some advantages. However, other mechanisms can be considered tomake similar cluster structure. For example, we can consider that nodes with specific attributes (e.g. node ID is amultiple of 10) are cluster heads.
Our model, on the other hand, yielded a cluster structure that responded to the initial condition. In particular,
it is important that diﬀerent cluster structures are obtainedby changing the value of parameter σ2 . The left panels of
Fig. 13 and Fig. 14 contain many peaks in accordance withthe fine structure of the initial condition, and the center panels of Fig. 13 and Fig. 14 contain fewer peaks in accordancewith the coarse grained structure of the initial condition.
Therefore, a fine cluster structure or coarse grained cluster
structure can be formed by a small or larger σ2 .
If we can tune the values of parameters for Neglia
model to reflect the initial condition, the Neglia model may
yield cluster structures that reflect the characteristics of theinitial condition. However, tuning the value of the parameter everywhere in the network demands that we know global
information of the network. Such a mechanism is not an†
Though Δt = 0.003 (= τ) in Neglia model [18], we set Δt = 1
to allow comparison with our proposed model. For such a modification of Δt for Neglia model, we revise the other parameters
except Δt.

TAKANO et al.: PROPOSAL FOR AUTONOMOUS DECENTRALIZED STRUCTURE FORMATION

1537

autonomous decentralized mechanism.
8.

Conclusions

Autonomous decentralized control based on the principle oflocal interaction oﬀers a general framework in which a local interaction rule at the micro-level yields orderly behavior of the entire system at the macro-level. Our previous
study considered the diﬀusion eﬀect for autonomous decentralized control based on local interaction, and focused onload-balancing. This paper has considered a new type ofautonomous decentralized control that can create structureswith finite spatial size. The structures obtained represent
a diﬀerent macro-level behavior from that obtained fromthe diﬀusion eﬀect. First, we introduced the renormalization transformation of the diﬀusion phenomenon for a onedimensional network model and considered autonomous
structure formation with a certain finite spatial size. Next
we formulated a rule for autonomous decentralized operation that does not depend on the use of a coordinate system. In addition, to apply this method to a general network
topology, we extended the one-dimensional network model
to n-dimensional Euclid space. We used the discretization
method to derive a control rule that can be applied to general
networks. As an application example, we introduced a technique yielding autonomous decentralized structure formation in a two-dimensional lattice network and confirmed thefeasibility of the autonomous decentralized clustering mechanism for sensor networks. Future studies will investigate
the characteristics of our structure formation mechanism for
diﬀerent values of the parameters used in our proposal anddetermine the appropriate parameter values for diﬀerent network conditions. In addition, we will establish a dynamic
clustering technology that takes the movement of nodes into
consideration.
Acknowledgment
This work was supported by Grant-in-Aid for Young Scientists (B) No. 21700086 (2009–2011) from the Japan Society
for the Promotion of Science.
References[1] C. Takano, M. Aida, M. Murata, and M. Imase, “New frameworkof back diﬀusion-based autonomous decentralized control and its
application to clustering scheme,” IEEE Globecom 2010 Workshop
on Network of the Future (The 3rd International Workshop on the
Network of the Future (FutureNet III)), Miami, FL, USA, Dec. 2010.
[2] C. Takano, M. Aida, M. Murata, and M. Imase, “Autonomous decentralized mechanism of structure formation adapting to network conditions,” The 11th IEEE/IPSJ International Symposium on Applications and the Internet (SAINT 2011) Workshops (The Second Workshop on Heuristic Methods for the Design, Deployment, and Reliability of Networks and Network Applications (HEUNET 2011)),
Munich, Germany, July 2011.
[3] R. Ogier, F. Templin, and M. Lewis, “Topology dissemination basedon reverse-path forwarding (TBRPF),” Request for Comments 3684,
Feb. 2004.

[4] T. Clausen and P. Jacquet, “Optimized link state routing protocol(OLSR),” Request for Comments 3626, Oct. 2003.
[5] C.E. Perkins, E.M. Royer, and S. Das, “Ad hoc on-demand distancevector (AODV) routing,” Request for Comments 3561, July 2003.
[6] D. Johnson, Y. Hu, and D. Maltz, “The dynamic source routing protocol (DSR) for mobile ad hoc networks for IPv4,” Request for Comments 4728, Feb. 2007.
[7] S. Basagni, “Distributed clustering for ad hoc networks,” Proc. International Symposium on Parallel Architectures, Algorithms andNetworks, pp.310–315, 1999.
[8] A.D. Amis, R. Prakash, T.H.P. Vuong, and D. Huynh, “Max-min
D-cluster formation in wireless ad hoc networks,” Proc. IEEE INFOCOM 2000.
[9] T. Ohta, S. Inoue, Y. Kakuda, and K. Ishida, “An adaptive multihop
clustering scheme for ad hoc networks with high mobility,” IEICE
Trans. Fundamentals, vol.E86-A, no.7, pp.1689–1697, July 2003.
[10] N. Malpani, J.L. Welch, and N. Vaidya, “Leader election algorithms
for mobile ad hoc networks,” Proc. 4th International Workshop on
Discrete Algorithms and Methods for Mobile Computing and Communications, pp.96–103, Aug. 2000.
[11] C. Johnen and L. Nguyen, “Self-stabilizing weight-based clustering
algorithm for ad hoc sensor networks,” 2nd International Workshop
on Algorithmic Aspects of Wireless Sensor Network AlgoSensors
2006, Springer LNCS, vol.4240, pp.83–94, 2006.
[12] J.Y. Yu and P.H.J. Chong, “A survey of clustering schemes for mobile ad hoc networks,” IEEE Commun. Survey and Tutorial, vol.7,
no.1, pp.32–48, 2005.
[13] M. Aida and C. Takano, “Principle of autonomous decentralized
flow control and layered structure of network control with respect
to time scales,” Supplement of the ISADS 2003 Conference Fast
Abstracts, pp.3–4, April 2003.
[14] C. Takano and M. Aida, “Stability and adaptability of autonomous
decentralized flow control in high-speed networks,” IEICE Trans.
Commun., vol.E86-B, no.10, pp.2882–2890, Oct. 2003.
[15] C. Takano, K. Muranaka, K. Sugiyama, and M. Aida, “Mutual complementarity of diﬀusion-type flow control and TCP,” IEICE Trans.
Commun., vol.E89-B, no.10, pp.2850–2859, Oct. 2006.
[16] C. Takano and M. Aida, “Diﬀusion-type autonomous decentralized
flow control for multiple flows,” IEICE Trans. Commun., vol.E90-B,
no.1, pp.21–30, Jan. 2007.
[17] D. Ganesan, et al., “Networking issues in wireless sensor networks,”
J. Parallel Distrib. Comput., vol.64, no.7, pp.799–814, 2004.
[18] G. Neglia and G. Reina, “Evaluating activator-inhibitor mechanisms
for sensors coordination,” 2nd IEEE/ ACM International Conference
on Bio-Inspired Models of Network, Information and Computing
Systems (IEEE/ACM BIONETICS 2007), Budapest, Hungary, Dec.
2007.
[19] K. Hyodo, N. Wakamiya, E. Nakaguchi, M. Murata, Y. Kubo, and K.
Yanagihara, “Reaction-diﬀusion based autonomous control of wireless sensor networks,” Int. J. Sensor Networks, vol.7, no.4, pp.189–
198, May 2010.
[20] H. Meinhardt, Models of biological pattern formation, Academic
Press, London, 1982.
[21] M.A. Dewar, V. Kadirkamanathan, M. Opper, and G. Sanguinetti,“Parameter estimation and inference for stochastic reactiondiﬀusion systems: Application to morphogenesis in D. melanogaster,”
BMC Systems Biology, vol.4, no.1, no.21, 2010.
[22] G.E. Uhlenbeck and L.S. Ornstein, “On the theory of Brownian Motion,” Physical Review, vol.36, pp.823–841, Sept. 1930.
[23] C. Takano, K. Sugiyama, and M. Aida, “Parameter design for
diﬀusion-type autonomous decentralized flow control,” IEICE
Trans. Commun., vol.E91-B, no.9, pp.2828–2837, Sept. 2008.

IEICE TRANS. COMMUN., VOL.E95–B, NO.5 MAY 2012

1538

Chisa Takano
received the B.E. degree in Telecommunication Engineering from
Osaka University, Japan, in 2000, and the
Ph.D. in System Design Engineering from Tokyo Metropolitan University, Japan, in 2008.
In 2000 she joined the Traﬃc Research Center,
NTT Advanced Technology Corporation (NTTAT). Since April 2008, she has been an Associate Professor of the Graduate School of Information Sciences, Hiroshima City University.
Her research interests lie in the area of computer
networks and distributed systems. She received the IEICE’s Young Researchers’ Award in 2003.

Masaki Aida
received his B.S. and M.S.
degrees in Theoretical Physics from St. Paul’s
University, Tokyo, Japan, in 1987 and 1989, respectively, and received the Ph.D. in Telecommunications Engineering from the University ofTokyo, Japan, in 1999. In April 1989, he joined
NTT Laboratories. From April 2005 to March
2007, he was an Associate Professor at the Faculty of System Design, Tokyo Metropolitan University. He has been a Professor of the Graduate
School of System Design, Tokyo Metropolitan
University since April 2007. His current interests include traﬃc issues incomputer communication networks. He is a member of the IEEE and the
Operations Research Society of Japan.

Masayuki Murata
received the M.E. and
D.E. degrees in Information and Computer Sciences from Osaka University, Japan, in 1984 and1988, respectively. In April 1984, he joined
IBM Japan’s Tokyo Research Laboratory, asa Researcher. From September 1987 to January 1989, he was an Assistant Professor with
the Computation Center, Osaka University. In
February 1989, he moved to the Department ofInformation and Computer Sciences, Faculty ofEngineering Science, Osaka University. In April
1999, he became a Professor of Osaka University, and since April 2004, hehas been with the Graduate School of Information Science and Technology, Osaka University. He has contributed more than four hundred andfifty papers to international and domestic journals and conferences. His
research interests include computer communication networks and performance modeling and evaluation. He is a member of the IEEE, ACM, theInternet Society, and IPSJ.

Makoto Imasereceived his B.E. and M.E.
degrees in Information Engineering from Osaka
University in 1975 and 1977, respectively. He
received his D.E. degree from Osaka University in 1986. From 1977 to 2001, he worked
for Nippon Telegraph and Telephone Corporation (NTT). Since 2002 he has been a Professor of the Graduate School of Information Science and Technology at Osaka University. His
research interests are in the area of information
networks, distributed systems and graph theory.
He is a member of IPSJ and JSIAM.