International Journal on Advances in Intelligent Systems, vol 7 no 1 & 2, year 2014, http://www.iariajournals.org/intelligent_systems/

64

New Autonomous Decentralized Structure Formation
Based on Huygens’ Principle and Renormalization
for Mobile Ad Hoc Networks
Kenji Takagi

Chisa Takano

Masaki Aida

Graduate School of System Design,
Tokyo Metropolitan University
Tokyo, Japan
Email: kenji.takagi.tmu@gmail.com

Graduate School of Information Sciences,
Hiroshima City University
Hiroshima, Japan
Email: takano@hiroshima-cu.ac.jp

Graduate School of System Design,
Tokyo Metropolitan University
Tokyo, Japan
Email: aida@tmu.ac.jp

Makoto Naruse
National Institute of Information
and Communications Technology (NICT)Tokyo, Japan
Email: naruse@nict.go.jp
Abstract—This paper proposes an autonomous distributed algorithm that can construct spatial structures for clustering in
mobile ad hoc networks. Since the topology of a mobile ad hoc
network changes frequently, a fast, light-weight, and autonomousclustering mechanism is required. However, existing autonomousclustering mechanisms are based on differential equations andthus demand a lot of calculations for generating the spatial structures that yield clustering. This paper proposes an autonomousclustering algorithm that is based on Huygens’ principle andrenormalization. The most remarkable characteristics of our
proposed scheme are light calculation loads and fast convergenceon the cluster structures. We verify the basic characteristics ofthe proposed scheme. In addition, we introduce an algorithm tocontrol the number of generated clusters in the framework of the
proposed scheme by introducing a logarithmic representation of
network state.
Keywords—Mobile ad hoc network, Autonomous decentralized
control, Clustering, Huygens’ principle, Renormalization.

I.

I NTRODUCTION

This paper is an extended version of the paper presented at
COLLA2013 [1]. The significant progress of this paper fromthe earlier version is that we can control the number of cluster
even if we cannot know the network state and its metric in
advance. Details are explained in the body of this paper.
In large-scale communication networks, hierarchical architectures are effective for scalable network control. Let us
consider how hierarchical structure can be introduced into
networks. For the case of fixed networks, we can set the desired
hierarchical structure at the time of designing the networks.
However, this is not possible for mobile networks since their
topology changes dynamically. A typical example the mobile
ad hoc network (MANET) [2]. A MANET consists of mobile
terminals that work as routers. That is, each terminal offers
routing functions and data forwarding functions. Two terminals
can directly communicate if their coverage areas of wirelesscommunications overlap. If the areas do not overlap, theterminals communicate but relaying data through the terminals

between them, they can establish multihop communications.
To achieve multihop communications, routing is one of mostimportant issues in MANETs.
The most primitive route finding approach is called flooding [3]. In flooding, the sender terminal sends route finding
packets to all adjacent terminals, which resend them to all theiradjacent terminals until at least one copy of the packet reaches
the destination terminal. The total amount of route finding
packets sent in MANETs increases exponentially with network
size (the number of terminals). It is known as the broadcast
storm problem [4]. So one of the challenges in MANETs,
realizing scalable routing control [5][6], is best addressed by
setting a hierarchical structure through clustering [7][8].
Hereafter, we call a MANET terminal a node. An autonomous clustering mechanism for generating a hierarchicalstructure must offer several characteristics, as follows:•

Each node acts autonomously based on local information about its neighboring nodes.

•

The generated cluster structure should reflect the state
information of the network (e.g., battery power ofnodes).

•The generated cluster structure should be flexible sothat it can adapt to the dynamic environment.

•

The convergence time of clustering should be sufficiently shorter than the timescale of topology change
caused by node movement. This is because clustering
should dynamically adapt to the network topology.

•

Action rules of each node should be as simple as possible in order to reduce the battery power consumed
by computation or processing at the node.

Since MANETs are expected to be an effective communication
tool after serious disasters, the above requirements are essential
for realizing clustering in ad hoc networks.

2014, © Copyright by authors, Published under agreement with IARIA - www.iaria.org

International Journal on Advances in Intelligent Systems, vol 7 no 1 & 2, year 2014, http://www.iariajournals.org/intelligent_systems/

65!"#$%"&'()*!

A. Concept of Cluster Formation*)!+,!
Figure 1.

Concept of cluster forming.

Neglia et al. proposed a clustering mechanism basedon reaction-diffusion equations [9]. Let us call it the bioinspired approach. This is an application of Turing patterns
and satisfies the first requirement listed above. Takano et al.
has proposed a clustering mechanism based on the FokkerPlanck equation and includes the drift motion given by backdiffusion [10][11][12]. Let us call it the back-diffusion based
approach. The back-diffusion based approach satisfies the firsttwo requirements listed above. In addition, Hamamoto et al.
recently propose a mechanism that guarantees the asymptotic
stability of the cluster structure generated by the back-diffusion
based approach; they showed that their mechanism can satisfy
the first three requirements listed above [13].
The guarantee mechanism of asymptotic stability, in particular, implies the possibility of new autonomous clustering
mechanisms. Specifically, we might be able to make a newclustering algorithm that satisfies all the requirements listed
above by replacing the back-diffusion algorithm with a simple and fast-converging rule. This is because the guarantee
mechanism of asymptotic stability does not depend on detailsof the clustering mechanism. In this paper, we use Huygens’
principle as the simple and fast-converging rule, and propose
a new clustering mechanism that satisfies all the requirements
listed above.
The paper is organized as follows: Section II explains
the concept of cluster formation and the guarantee mechanism of asymptotic stability, which is the foundation ofthis research. Section III proposes an autonomous clustering
mechanism based on Huygens’ principle. Section IV showscluster structures generated by our proposed scheme using
numerical examples and verifies that they reflect the network
condition. Section V introduces an algorithm to control thenumber of generated clusters in the framework of the proposed
scheme by introducing a logarithmic representation of network
state. In addition, we show a control method of the number ofclusters. The conclusion is discussed in Section VI.

II.

P RELIMINARY

This section shows the framework of autonomous decentralized clustering and the related mechanism to stabilize thecluster structure.

In our clustering model, each node has a certain value andcluster formation is conducted by the distribution of the valuesof nodes. The initial value is determined by considering acertain network metric (e.g., battery power of each node). The
clustering algorithm extracts a coarse grained spatial structurefrom the initial distribution of the values and this procedurecorresponds to clustering. Figure 1 shows an example of cluster
formation in a simple 1-dimensional network. The horizontal
axis represents node position, and the vertical axis represents
the value of the distribution for each node. The upper-halfof Figure 1 represents the initial distribution, which reflects a
certain network state. The lower-half of Figure 1 represents
the generated coarse grained spatial structure. Each peak of
the coarse grained distribution corresponds to the center of acluster, and cluster structures reflect the initial condition.
The back-diffusion based approach is an example of thismechanism, and has a relatively faster convergence rate thanthe bio-inspired approach [14]. However, this clustering mechanism does not consider change from the initial condition,and so cannot adapt to the dynamic environment common to
MANETs. That is why this mechanism does not satisfy thethird requirement listed in the previous section.
B. Guarantee mechanism of Asymptotic Stability
To adapt the spatial structure to dynamic environments,
the guarantee mechanism of the asymptotic stability of cluster
structures was proposed by Hamamoto et al. [13]. In thismechanism, cluster structure generation can adapt to changes
in network state; the mechanism generates stable spatial structures if the network state is fixed. As an alternative approach,Takayama et al. proposed the self-adjustment approach tostabilize the cluster structure [15]. However, it has a restrictionthat is applicable only to the back-diffusion based clustering.
Thus, we focus on [13] in this paper.
Let us consider a one-dimensional network model for
simplicity, and let q(i, t) be the distribution value at node
position i at time t. The distribution value, q(i, t), determines
the cluster structure. As an example, the initial condition q(i, 0)
and cluster structure q(i, t) obtained at time t are shownin Figure 1. The conventional back-diffusion based approachdescribed in Takano et al. [12] presents a rule that governs
the temporal evolution of the distribution, q(i, t). However,as shown in the previous section, it is difficult to guarantee
the stability of q(i, t) for large t. In other words, the cluster
structure is not stable in a dynamic environment.
Let us consider discrete time tk (k = 1, 2, . . . ), anddistribution q(i, tk ). Since we need an autonomous decentralized algorithm, the temporal evolution of distribution q(i, tk )is determined by its local information. By introducing the
temporal evaluation operator of T , the temporal evolution isformally described asq(i, tk+1 ) = T (q(i − 1, tk ), q(i, tk ), q(i + 1, tk )).

(1)

This rule states that the distribution of node i at the next time iscompletely determined by the values of the present distribution
at node i and its adjacent nodes.

2014, © Copyright by authors, Published under agreement with IARIA - www.iaria.org

International Journal on Advances in Intelligent Systems, vol 7 no 1 & 2, year 2014, http://www.iariajournals.org/intelligent_systems/

66

discarddiscarddiscardqN (t0 )qN (t1 )qN (t2 )qN (t3 )qN −1 (t0 )qN −1 (t1 )qN −1 (t2 )qN −1 (t3 )q5 (t0 )q5 (t1 )q5 (t2 )q5 (t3 )q4 (t0 )q4 (t1 )q4 (t2 )q4 (t3 )q3 (t0 )q3 (t1 )q3 (t2 )q3 (t3 )q2 (t0 )q2 (t1 )q2 (t2 )q2 (t3 )q1 (t0 )q1 (t1 )q1 (t2 )q1 (t3 )q0 (t0 )q0 (t1 )q0 (t2 )q0 (t3 )coarser grained
structure
conventional
methodfiner structure

Figure 2.

qinit (t0 )qinit (t1 )qinit (t2 )qinit (t 3)

t0

t1

t2

t3

Outline of the guarantee mechanism of asymptotic stability.

the network state at time tk . Then we set!"#$%&'()*")*+,$*)56)!

q0 (i, tk+1 ) = qinit (i, tk+1 ).

(3)

If qinit (i, tk ) is independent of time, q0 (i, tk+1 ) = q(i, 0), thatis, the initial condition of the conventional mechanism. Note
that, in general, we allow the time-dependence of qinit (i, tk ).
Next, for qn+1 (i, tk+1 ) (n = 0, 1, . . . , N − 1), we set
qn+1 (i, tk+1 ) = T (qn (i − 1, tk ), qn (i, tk ), qn (i + 1, tk )).
(4)-./$&01"2*
3"#$4*!

Although the above rule may look complicated, we can easily understand it through graphical representation. Figure 2
explains the temporal evolution of vector (2) at node i. The
horizontal axis represents discrete time as t0 , t1 , . . . , andqinit (tk ) is a certain value expressing the network state of anode at time tk . Each component of the vector is a value of the
distribution and (4) is the temporal evolution rule for the nthcomponent (n = 1, 2, . . . , N − 1). The temporal evolution ofeach component will be updated to the upper-right component
in Figure 2. The component at the bottom, q0 (i, tk+1 ), is
overwritten by the network condition qinit (i, tk+1 ) at thepresent time. The component at the top will be discarded.

!"#$%&'()*")*+,$*)!
Figure 3.

Example of wave propagation obeying Huygens’ principle.

To guarantee asymptotic stability, we consider a vectorof the distribution. Each node i has the following N + 1
dimensional vector
q(i, tk ) = {q0 (i, tk ), q1 (i, tk ), . . . , qN (i, tk )}.

(2)

Here, we define the rule for the temporal evolution of thevector q(i, tk ). Let qinit (i, tk ) be the distribution describing

The temporal evolution of the conventional mechanism corresponds to the sequence indicated by the green broken line in
Figure 2. In the guarantee mechanism of asymptotic stability,
we focus on the sequence of the same vector components. If
we choose small n for the nth component, we obtain a finergrained spatial structure as indicated by the blue line. A largen yields a coarse grained spatial structure as indicated by the
red line.

2014, © Copyright by authors, Published under agreement with IARIA - www.iaria.org

International Journal on Advances in Intelligent Systems, vol 7 no 1 & 2, year 2014, http://www.iariajournals.org/intelligent_systems/

distributionnode!"#$%&%'(")&*'+,'-$./0$1&2+3'(")&*'"/'2%*'/'45/!

distribution

67

distribution

node/#,.0"1!

203%4(560"'!

!"#$%&%'(")&*'+,'-$./0$1&2+3'"/'2%*'/'!
Figure 5.

Fixed point under renormalization transformation.

scaling
node

Figure 4.

!"#$%&%"'()*(+,-%.%'!

T . Specifically, each node generates spherical wave-like information for temporal evolution of the distribution. Concrete
procedures of the renormalization transformation are shown
below.

Renormalization transformation as per Huygens’ principle.

III. D ESIGN OF THE AUTONOMOUS S TRUCTURE
F ORMATION T ECHNOLOGY BASED ON H UYGENS ’
P RINCIPLE
In this section, we first propose a new autonomous decentralized clustering based on Huygens’ principle and its
renormalization transformation. Second, we investigate theattenuation of the cluster structure caused by the fixed point of
the renormalization transformation, and introduce a procedureof amplification for avoiding the attenuation.
A. Huygens’ principle and Renormalization
Huygens’ principle, or the Huygens-Fresnel principle describes the temporal evolution of the wavefront and can explain
the laws of reflection and refraction. Figure 3 shows anexample of wave propagation obeying Huygens’ principle.
Let us consider a wavefront at present time t. In Huygens’
principle, spherical waves originate from all points on the
wavefront and the envelope of these spherical waves gives the
temporal evolution of the wavefront at time t + ∆t.
Renormalization is a way to extract simple and important
macroscopic characteristics from a large-scale and complex
system, and its procedure is called renormalization transformation. This procedure is suitable for generating a simple
cluster structure extracted from the spatial structure of the
network state. Renormalization transformation is defined as
the combination of coarse-grained transformation and scaling.
In this paper, we adopt the renormalization transformation
based on Huygens’ principle as temporal evolution operation

Let us consider a one-dimensional network and a distribution on the network. The panel at the top of Figure 4 shows anexample of the distribution at the present time. We consider
the shape of the distribution as the wavefront. The panel at
the middle of Figure 4 shows the temporal evolution of the
wavefront as given by Huygens’ principle. This procedure
has a smoothing effect in which the fine-grained structure in
the shape of the distribution becomes smooth. The temporal
evolution of the distribution causes an increase in the valueof the distribution, that is, the wavefront proceeds upward. Inorder to compensate for this increase, we introduce scaling
as shown in the panel at the bottom of Figure 4. We define
the renormalization transformation as the combination of such
temporal evolution and scaling.
Let the distribution value of node i at time tk be q(i, tk ),and let the set of nodes that are adjacent to node i at time tk
be M (i, tk ). In addition, q̃(i, j, tk+1 ) is the wavefront of thespherical wave at node i at time tk+1 that originated from node
j at time tk . Our renormalization transformation is expressedas1
q(i, tk+1 ) =max q̃(i, j, tk+1 ),(5)
b j∈M (i,tk )where, the maximizing operation in (5) means Huygens’ principle; it determines the most advanced wavefront of sphericalwaves that originated from the node itself and its neighborhood, b is the scaling parameter.
Next, let us consider a method of tuning parameter busing Figure 5. In Figure 5, the horizontal axis represents the
maximum value of the distribution at time t , and the verticalaxis represents the maximum value of the distribution after
renormalization transformation at time t + ∆t. Here, the black

2014, © Copyright by authors, Published under agreement with IARIA - www.iaria.org

International Journal on Advances in Intelligent Systems, vol 7 no 1 & 2, year 2014, http://www.iariajournals.org/intelligent_systems/

68!"#$%"&'()*!

v∆t

θ
∆x

+,2)!/!
+,-.'#$/%,0/1!!
+,-.'#$/%!

Figure 7.

Determination of the cluster and cluster head.

!"#$!

i −1
Figure 6.

i +1

iB. Amplification of the Range of the Distribution

The wavefront of the spherical wave reaches an adjacent node.

line shows the linear equation y = x. This linear equation
corresponds to the top of Figure 4. Next, the maximum value ofthe distribution is increased obeying Huygens’ principle. This
increment can be expressed by v∆t and the blue line, which isshifted up from y = x by v∆t. The red line is obtained fromthe blue line by dividing the latter by the scaling parameterb (b > 1). There is an intersection point between the red line
and the black line, and this intersection point is given by
p∗ =

v ∆t
.
b−1

(6)

The value of interaction point p∗ is the fixed point underrenormalization transformation. We can understand that the
maximum value of distribution q(i, tk ) converges to p∗ with
iterations of the temporal evolution, regardless of initial condition q(i, 0). Hence, the method of tuning parameter b does
not need to be highly accurate.
Next, we consider the concrete form of q̃(i, j, tk+1 ). Let
the propagation speed of the spherical wave be v, the distance
between two adjacent nodes be ∆x, and the interval of thetemporal evolution (renormalization transformation (5)) be ∆t(i.e., tk+1 − tk = ∆t). Here, ∆x is not physical distance but isa kind of hop count, so we choose ∆x = 1. We consider thesituation wherein the temporal evolution (5) is determined only
by adjacent nodes, v is chosen as 1 ≤ v ∆t < 2. As shown in
Figure 6, the wave front of the spherical wave originating fromnode i influences both node i and its adjacent nodes. They are
expressed asq̃(i ± 1, i, tk+1 ) = q(i, tk ) + v ∆t sin θ,q̃(i, i, tk+1 ) = q(i, tk ) + v ∆t,where θ is a constant and, from v ∆t cos θ = ∆x,()∆x
θ = arccos.
v ∆t

Our renormalization transformation (5) makes the distribution flat and we can obtain a coarse-grained spatial structure.
However, different from physical phenomena, there are situations that the distribution does not change when the difference
in distribution values is small. This is because the positionsof nodes in the network are discrete. If the distribution value
at a node can affect that of the adjacent node, the following
relation is required;|q(i ± 1, tk ) − q(i, tk )| > v ∆t (1 − sin θ).

(10)

When smoothing proceeds and the condition (10) is no longer
met, the two adjacent nodes no longer interact and the distribution is unchanged. To avoid this phenomenon, we introduce
amplification of the range of the distribution in addition torenormalization transformation (5). The additional operationisq(i, tk+1 ) ← p∗ + a (q(i, tk+1 ) − p∗ ) ,(11)

after renormalization transformation (5). This operation meansthat the difference between the distribution value and p∗
is amplified by a factor of a. Here, the aforementionedp∗ = v ∆t/(b − 1) is the fixed point of renormalizationtransformation, and also is the convergence point. Note that,the value of parameter a should be chosen as a > b.
Finally, we explain how to determine clusters and cluster
heads from the generated spatial structure (Figure 7). By following the direction of the steepest gradient of the distribution,
we can find a node with local maximum value. We define it as
the cluster head, and the nodes belonging to the same cluster
head belong to the same cluster.
IV.

E VALUATION FOR S TATE D EPENDENTC HARACTERISTICS OF C LUSTERS

(7)
(8)

This section shows cluster structures generated by our
proposed scheme using numerical examples and verifies thatthey reflect the network condition. Our simulation programs
are written by C language.

(9)

A. Simulation Model and Parameters

Since v, ∆t, and sin θ are constants and we can know themin advance, temporal evolution (5) is a simple operation.

In this subsection, we explain a simulation model and parameters used in our verification. In this verification, we use aunit disk graph having a torus boundary as the network model.

2014, © Copyright by authors, Published under agreement with IARIA - www.iaria.org

International Journal on Advances in Intelligent Systems, vol 7 no 1 & 2, year 2014, http://www.iariajournals.org/intelligent_systems/

69!"#"$%!

!"#"&%!

!"#"'%!

!"#"$%%!

!"#$%&!
!"'()&*&++""",$--./(,01$/""")0/2&""
Figure 8.

Unit disk graph having torus boundary.

!"#"$%!

!"#"$%!

High

High

Low

Low
Figure 10.

Figure 9.

The cluster structures generated from a randomized state.

Initial condition.

B. Evaluation
We can configure the unit disk graph through the following
procedure. We set the position of each node randomly, and set
a circle of a certain radius around each node. If the circle of anode encloses another node(s), we set a link between the center
node of the circle and each node lying within the circle. Since
we can assume that circle radius is wireless communication
range, the unit disk graph is a model that can express MANET
topology. Figure 8 shows an example of the torus boundary
by focusing on the wireless communication range of a certain
node. The reason of setting the torus boundary condition is toeliminate the effect of the network edge, and to concentrate
our attention on the characteristics of clustering mechanism
itself. In this evaluation, we set 1, 000 nodes on a plane of
1 km × 1 km, and use 60 m as the wireless communication
range.
In order to verify the state dependent characteristics of thecluster structures generated, we use two initial distributions asshown in Figure 9 where distribution values are described by acolor map. The left figure in Figure 9 expresses a randomized
state. The initial values of qinit (i, 0) for all node positions,i, are random values that obey a uniform distribution withrange [0, 10]. The right figure in Figure 9 expresses a spatiallystructured state. Three areas have relatively high values, andthe values of these areas are determined by random values
that obey a uniform distribution with range [5, 10]. The valuesof other area are determined by random values that obey auniform distribution with range [1, 2]. If, for example, thevalue represents battery energy, the randomized state does not
express any power-supply information whereas the spatiallystructured state indicates three power-supply zones. The parameters used in the evaluation are shown in Table I.

Figures 10 and 11 show the cluster structures generated
from a randomized state and a spatially structured state, respectively. The four panels of each figure shows the number of
iterations or, equivalently, the position of the vector component
in the guarantee mechanism of the asymptotic stability of cluster structures. From these results, if we choose few iterations,
we get a finer-grained cluster structure, and if we choose
more iterations, we get a coarse grained cluster structure.
We can also recognize that the cluster structures reflect the
spatially configured state of the initial condition. Since theinitial condition reflects the network state (e.g., battery powerof each node), it means the cluster structure generated byour proposed scheme can reflect the state information of the
network.
V. C ONTROLLABILITY OF T HE N UMBER OF C LUSTERSBASED ON THE G UARANTEE MECHANISM OF A SYMPTOTICS TABILITY
This section investigates the clusters generated by our
proposed scheme combined with the guarantee mechanism
of asymptotic stability and reveals a technological problem
TABLE I.

PARAMETER SETTING .

parameter
v
b
a
∆x
∆t

value
1.5
1.1
1.2
1.0
1.0

2014, © Copyright by authors, Published under agreement with IARIA - www.iaria.org

International Journal on Advances in Intelligent Systems, vol 7 no 1 & 2, year 2014, http://www.iariajournals.org/intelligent_systems/

70!"#"$%!

!"#"&%!

!"#"'%!

!"#"$%%!

Figure 12. The number of generated clusters for randomized initial conditions
w.r.t. the number of iterations.

Figure 11. The cluster structures generated from a spatially structured state.

for ensuring control of the number of clusters. To solve thisproblem, we propose a control method of the number ofclusters by introducing a logarithmic representation of network
state.
A. Metric for Describing Network StateLet us consider what metrics can be used to describe
network state. For example, we can use node battery power
as the initial condition of nodes that reflects the state of the
network. There are many ways to express the battery powerin numerical values: ampere-hour [Ah], milli-ampere hour[mAh], coulomb [C], etc. Incidentally, 1 Ah = 1,000 mAh= 3,600 C. Thus, the ranges of the initial distribution may
quite different depending on the metric used, even if thetarget networks are in the same environment. In addition, it
is possible that some other network state metrics might be
included as a part of the distribution value. Therefore, it isdifficult to specify the metric for describing network state inadvance.
In our proposed clustering scheme combined with theguarantee mechanism of asymptotic stability, the number ofclusters are controlled by choosing the number of iterations(i.e., the position of the vector component of (2)). In order torealize the control of the number of clusters based on ourframework, for any given iteration number, the number ofgenerated clusters should be independent of the metric.
B. Evaluation for Dependence Characteristics on the Rangeof the Initial Distribution
In this subsection, we investigate the convergence of thenumber of generated clusters with respect to the range ofthe initial distributions. We use the same network model andparameter setting as used in the previous section. The valuesof the initial distribution qinit (i, 0) for all node positions, i,are given by a random values that obey a uniform distribution;
four kinds of uniform distributions are examined. Their ranges
are [1, 5], [10, 5 × 10], [102 , 5 × 102 ] and [103 , 5 × 103 ]. The
difference in ranges means the difference in the metrics. An
example of an initial condition is shown in the left pane of
Figure 9.
Figure 12 shows the temporal evolutions of the number ofclusters obtained from four different initial conditions. Fromthese results, we can recognize that the number of clusters
strongly depends on the range of the initial distribution.
Also, the relationship between the number of clusters and theiteration times depends on the range of the initial distribution.
Since we cannot know the network state and its metric in
advance, we cannot control the number of clusters.
The cause of the above problem is the excessive sensitivityof cluster formation to the range of the distribution. The
mechanism of the excessive sensitivity with respect to therange of the distribution can be recognized through Figure 13.
Figure 13 shows the behaviors of cluster formation obtained
from our proposed scheme for the initial distributions withlarge and small ranges. First, each node performs temporal
evolution obeying Huygens’ principle, and then scaling. Smallvalued nodes, which are next large-valued nodes, are greatly
influenced by the latter, and the difference in values between
them is strongly decreased. Therefore, if the range of the initial
distribution is large, the distribution is rapidly harmonized.
C. Proposal of Control Method of the Number of Clusters
In order to avoid the problem caused by the difference inthe ranges of distribution, we redefine the initial condition. The
details are as follows. We do not use the network condition
directly as the initial condition, but instead use
q(i, 0) = log(qinit (i, 0)).

(12)

In the vector formulation, we replace (3) withq0 (i, t) = log(qinit (i, t)).

2014, © Copyright by authors, Published under agreement with IARIA - www.iaria.org(13)

International Journal on Advances in Intelligent Systems, vol 7 no 1 & 2, year 2014, http://www.iariajournals.org/intelligent_systems/!"#$%"&'()*!

!"#$%"&'()*!

71

*)!+!
*)!+!

!"#$%&'()"*%(+,%-!

#%&'(%)*+"!!

#%&'(%)*+"!!

!"#$%&'()"*%(+,%-!

!"#$!

!"#$!

!"#$!
Figure 13.

!"#$%&'!

#%&'(%)*+"!!

#%&'(%)*+"!!

!"#$%&'!

!"#$!

An example of the behavior of the proposed mechanism on two different distribution ranges.

The reasons for introducing a logarithmic function are as
follows:•

It is possible to maintain the magnitude relation of thevalues of the original initial distribution.

•

If the value of the original initial distribution is large,
its new equivalent value is smaller in the sense of theratio.

Let us consider the situation wherein the range of initialcondition is given by [Ax, Bx]. Where x is a positive constantrepresenting the difference between metric values. Here, we
define the distribution range function R[q] as the difference
between the maximum and minimum values of distribution q.
The range of the conventional distribution, qinit , is expressed
as follows:(14)

Figure 14. The number of clusters generated using logarithmic function fromrandomized initial conditions, w.r.t. the number of iterations.

This means that the range of the distribution depends on x.
On the other hand, the range of the new distribution log qinit
is expressed as follows:
( )
B
.
(15)
R[log(qinit )] = log(Bx) − log(Ax) = log
AThis means that the range of the distribution is independentof x. It also means that the range of the redefined initial
distribution is independent of the metric used.

R[qinit ] = (B − A) x.

2014, © Copyright by authors, Published under agreement with IARIA - www.iaria.org

International Journal on Advances in Intelligent Systems, vol 7 no 1 & 2, year 2014, http://www.iariajournals.org/intelligent_systems/

72
be independent of the metric representing the initial network
condition. However, unfortunately, the convergence speed ofcluster configuration depends strongly on the range of theinitial distribution that describes the network state. Since wecannot know the distribution value for each node in advance,
the difference in convergence speed makes it impossible tocontrol the number of clusters. To avoid this problem, we introduced new distribution defined by the logarithm of the original distribution. Consequently, the difference in convergence
speed is significantly weakened, and the number of clusters
becomes controllable. The above characteristics are suitablefor clustering in MANET. As future work, we will consider
the response of our mechanism to dynamic environments.
ACKNOWLEDGMENT
Figure 15. The number of clusters generated using logarithmic function fromthe initial condition having patterned structure, w.r.t. the number of iterations.

D. Evaluation for Controllability of the Number of Clusters
Figure 14 shows similar evaluations to Figure 12 by using
the redefined initial condition (13). We recognize that the
impact of the initial condition is sufficiently weakened. In particular, all initial conditions yield completely the same result.
This means that we have a robust clustering mechanism thatcan control the number of clusters by appropriately choosing
the number of iterations or the component of the vector.
Next, we evaluate an effectiveness of our control method onother type of initial distribution. We use the initial distribution
having spatially structured state (right figure in Figure 9).
Also, we prepare the range of initial conditions in the samemanners as the previous evaluation. Specifically, their ranges
are as follows. The values on the three areas are determinedby random values that obey a uniform distribution with range[5, 10]. The values on the other areas are also determined byrandom values that obey a uniform distribution with range[1, 2]. Let us call this initial condition type 1. Next, we define
the initial condition type 2, whose ranges are calculated byraising the ranges of type 1 by a factor of ten. In the samemanner, we define type 3 and type 4.
Figure 15 shows the temporal evolution in the number ofclusters obtained from our scheme with the logarithmic initialconditions for the four different ranges. From these results,
we can recognize that the number of clusters is independentof the range of initial distribution even if the initial distribution
is spatially structured. Therefore, our proposed scheme can be
expected to control the number of clusters even if the initial
distribution has a complex spatial structure.
VI.

C ONCLUSION AND F UTURE W ORK

In this paper, we proposed an autonomous clustering
mechanism based on Huygens’ principle for MANETs. For
verification, we used a unit disk graph to evaluate the characteristics of the proposed scheme. The benefits of the proposed
algorithm lie in its simplicity and its ability to form the spatial
structure reflecting the initial condition of network states. To
control the number of clusters generated, the number shouldThis work was supported by a Grant-in-Aid for Scientific
Research (B) No. 23300031 (2011-2013) from the Japan
Society for the Promotion of Science.
R EFERENCES[1] Kenji Takagi, Masaki Aida, Chisa Takano, and Makoto Naruse, “Aproposal of new autonomous decentralized structure formation basedon Huygens’ principle and renormalization,” in Proceedings of the
3rd International Conference on Advanced Collaborative Networks,
Systems and Applications (COLLA 2013), Jul. 21–26, 2013, Nice,
France, pp. 75–80, ISBN: 978-1-61208-287-5, ISSN: 2308-4227.
[2] Charles E. Perkins, Ad Hoc Networking, Addison-Wesley, Jan. 2001,
ISBN: 978-0201309768.
[3] Charles E. Perkins, Elizabeth M. Belding-Royer, and Samir R. Das,
“Ad hoc on-demand distance vector (AODV) routing,” Request forComments 3561, Jul. 2003.
[4] Yu-Chee Tseng, Sze-Yao Ni, Yuh-Shyan Chen, and Jang-Ping Sheu,“The broadcast storm problem in a mobile ad hoc network,” Wireless
Networks, Kluwer Academic Publishers, vol. 8, issue 2–3, Mar. 2002,
pp. 153–167, ISSN: 1572-8196.
[5] Josh Broch, David A. Maltz, David B. Johnson, Yih-Chun Hu, andJorjeta Jetcheva, “A performance comparison of multi-hop wireless ad
hoc network routing protocols,” in Proceedings of MOBICOM’98 of the
4th annual ACM/IEEE international conference on Mobile computing
and networking, Oct. 25–30, 1998, Dallas, TX, USA, pp. 151–162,
ISBN: 1-58113-142-9.
[6] Stefaan Seys and Bart Preneel, “ARM: Anonymous routing protocol formobile ad hoc networks,” International Journal of Wireless and Mobile
Computing, Inderscience Publishers, vol. 3, issue 3, Oct. 2009, pp. 145–
155, ISSN: 1741-1084.
[7] Stefano Basagni, “Distributed clustering for ad hoc networks,” inProceedings of the 4th International Symposium on Parallel Architectures, Algorithms, and Networks, 1999 (I-SPAN’99), Jun. 23–25, 1999,
Perth/Fremantle, WA, USA, pp. 310–315, ISSN: 1087-4089.
[8] Tomoyuki Ohta, Shinji Inoue, Yoshiaki Kakuda, and Kenji Isida, “Anadaptive multihop clustering scheme for ad hoc networks with highmobility,” IEICE Transactions on Fundamentals, vol. E86-A, no. 7,
Jul. 2003, pp. 1689–1697, ISSN: 0916-8508.
[9] Giovanni Neglia and Giuseppe Reina, “Evaluating activator-inhibitor
mechanisms for sensors coordination,” in Proceedings of the 2nd IEEE/
ACM International Conference on Bio-Inspired Models of Network,
Information and Computing Systems (Bionetics 2007), Dec. 10–12,
2007, Budapest, Hungary, pp. 129–133, ISBN: 978-963-9799-05-9.
[10] Masaki Aida, “Using a renormalization group to create ideal hierarchical network architecture with time scale dependency,” IEICE Transactions on Communications, vol. 95-B, no. 5, May 2012, pp. 1488–1500,
ISSN: 0916-8516.
[11] Chisa Takano, Masaki Aida, Masayuki Murata, and Makoto Imase,“New framework of back diffusion-based autonomous decentralized
control and its application to clustering scheme,” in Proceedings ofthe IEEE Globecom 2010 Workshop on the Network of the Future

2014, © Copyright by authors, Published under agreement with IARIA - www.iaria.org

International Journal on Advances in Intelligent Systems, vol 7 no 1 & 2, year 2014, http://www.iariajournals.org/intelligent_systems/

73

[12]

[13]

[14]

[15]

(FutureNet III), Dec. 6–19, 2010, Miami, FL, USA, pp. 362–367, ISBN:
978-1-4244-8863-6.
Chisa Takano, Masaki Aida, Masayuki Murata, and Makoto Imase,“Proposal for autonomous decentralized structure formation based on
local interaction and back-diffusion potential,” IEICE Transactions on
Communications, vol. E95-B, no. 5, May 2012, pp. 1529–1538, ISSN:
0916-8516.
Ryo Hamamoto, Chisa Takano, Kenji Ishida, and Masaki Aida, “Guaranteeing asymptotic stability of clustering by autonomous decentralized
structure formation,” in Proceedings of the 9th IEEE International
Conference on Autonomic and Trusted Computing (ATC 2012), Sep. 4–
7, 2012, Fukuoka, Japan, pp. 408–414, ISBN: 978-1-4673-3084-8.
Kenji Takagi, Yusuke Sakumoto, Chisa Takano, and Masaki Aida, “Onconvergence rate of autonomous decentralized structure formation technology for clustering in ad hoc networks,” in Proceedings of the 32nd
International Conference on Distributed Computing Systems Workshops(ADSN 2012), Jun. 18–21, 2012, Macau, P.R.China, pp. 356–361,
ISBN: 978-1-4673-1423-7, ISSN: 1545-0678.
Hiroki Takayama, Sota Hatakeyama, and Masaki Aida, “Self-adjustment
mechanism guaranteeing asymptotic stability of clusters formed byautonomous decentralized mechanism,” Journal of Communications,vol. 9, no. 2, Feb. 2014, pp. 180–187, ISSN: 1796-2021.

2014, © Copyright by authors, Published under agreement with IARIA - www.iaria.org