Received 27 April 2023, accepted 1 June 2023, date of publication 21 June 2023, date of current version 26 June 2023.
Digital Object Identifier 10.1109/ACCESS.2023.3288075
Autonomous Decentralized Spectral Clustering
for Hierarchical Routing of Multi-Hop
Wireless Networks
NAOKI MATSUHASHI1 , CHISA TAKANO 2 , (Member, IEEE),
AND MASAKI AIDA 1 , (Senior Member, IEEE)
1 Graduate
2 Graduate
School of Systems Design, Tokyo Metropolitan University, Hino, Tokyo 191-0065, Japan
School of Information Sciences, Hiroshima City University, Hiroshima 731-3194, Japan
Corresponding author: Masaki Aida (aida@tmu.ac.jp)
This work was supported in part by the Japan Society for the Promotion of Science (JSPS) KAKENHI under Grant 20H04179, Grant
21K19775, and Grant 21H03432; and in part by the Tokyo Metropolitan University (TMU) Local 5G Research Support.
ABSTRACT In multi-hop wireless networks (MWNs), hierarchical structures are important to achieve
scalable routing control, as well as clustering algorithms for creating such structures and so have been
extensively studied. Due to the constraints of MWNs as distributed systems, these clustering algorithms
must be implemented in an autonomous and decentralized manner. In particular, ensuring transparency to
network topology and node mobility is important. Spectral clustering is a technique for appropriately creating
clusters regardless of the network topology. However, since this technique requires information on the entire
network, it is difficult to implement it autonomously and in a decentralized manner. Therefore, autonomous
and decentralized spectral clustering has only succeeded in simple grid networks. This paper proposes a
spectral clustering algorithm that can be implemented in an autonomous and decentralized manner for any
network topology. In this method, a certain spatial structure is generated in an autonomous and decentralized
manner by using differential equation-based temporal evolution equations; clusters are then formed using the
spatial structure yielded by the temporal evolution equations. We demonstrate that this method can realize
spectral clustering in an autonomous and decentralized manner in a static network model and also can realize
a stable cluster structure that responds to node movement in a dynamic network model.
INDEX TERMS Autonomous decentralized clustering, spectral clustering, multi-hop wireless network,
hierarchical routing, spectral graph theory.
I. INTRODUCTION
A. BACKGROUND
In recent years, the IoT (Internet of Things) society is
emerging through the connection of various things, such as
sensors and devices, to the Internet and utilizing the resulting
information. In cellular communication, which is the current
mainstream mobile Internet access, communication between
mobile terminals is performed via backbone networks that
link access points in base stations. In contrast, multi-hop
wireless networks (MWNs) are a means of communication
The associate editor coordinating the review of this manuscript and
approving it for publication was Chao Tong
62424
.
that does not depend on backbone networks. MWNs are
autonomous decentralized wireless networks that transfer
data between communication terminals within radio wave
range in a bucket relay method. Since MWNs are constructed
autonomously, they are simple and have a high degree of
freedom as regards network topology. Therefore, MWNs are
expected to be used in smart meters, sensor networks, and
temporary networks in the event of large-scale disasters [1],
[2], [3].
As a distributed system, MWN has the following
features [4]:
• The network topology changes dynamically as communication terminals (nodes) move freely.
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.
For more information, see https://creativecommons.org/licenses/by-nc-nd/4.0/
VOLUME 11, 2023
N. Matsuhashi et al.: Autonomous Decentralized Spectral Clustering for Hierarchical Routing of MWNs
It may become a large-scale network with the connection
of a massive number of nodes.
• Since no particular node manages the entire WMN, each
node uses only its own local information in controlling
the WMN.
To realize efficient routing in such a large-scale distributed
system, it is effective to introduce hierarchical routing with
its improved scalability [5]. The hierarchy of MWNs can be
introduced by dividing the entire network into sub-networks
called clusters. It is desirable that the cluster structure has an
appropriate size that depends on the state of the network [6].
Many clustering algorithms for creating hierarchical structures have been proposed and studied for a wide range of
MWNs [7], [8], [9]. In particular, because each MWN is a
decentralized system, clustering cannot be based on information about the entire structure of the MWN [10]. Thus,
clustering for MWNs must be conducted autonomously by
using just the local information that each node can access
[11]. Such clustering is called autonomous decentralized
clustering.
The clustering methods for MWN can be roughly divided
into those targeting networks with static structures and those
targeting networks with dynamic structures. Typically, the
former corresponds to a sensor network consisting of sensors placed at fixed positions, and the latter corresponds to
an ad-hoc network in which users with wireless terminals
move around. It is easy to acquire the global information of
networks with static structure for clustering algorithms, but
the same is not true for networks with dynamic structure.
Thus, the clustering algorithm for dynamic environments
constrained to using only local information. Given this background, Table 1 categorizes the existing clustering algorithms
from the viewpoints of dynamic/static and global/local information usage.
Since it is easy to acquire non-local or global information
from sensor networks with their relatively fixed node positions, many higher-value-added clustering techniques have
been proposed that consider specific performance metrics.
For example, to improve the energy efficiency of each node
and the network lifetime, some clustering techniques use
fuzzy technology [12] or genetic algorithms [13]. However,
attempts have been made to based clustering on just local
information without relying on non-local information. Examples are the methods that uses the Turing patterns generated
by reaction-diffusion equations [15] and partial differential
equations to generate periodic structures for fixed regular
networks with lattice topology [16].
On the other hand, in dynamic network environments,
clustering using non-local information is complicated by
changes in the network structure created by the movement
of user nodes. Attempts have been made to apply a clustering algorithm based on the k-means method, which requires
global network information, to dynamic environments [17],
[18]. In addition, there is a method based on node information
in a range that is several hops away from each node [19].
These clustering algorithms based on non-local information
•
VOLUME 11, 2023
may be feasible only if the structural change of the dynamic
environment is relatively gradual. An ideal clustering method
is one that is applicable to dynamic environments and works
only with local information. A representative example is
one-hop clustering [20], but this effectively realizes clustering only within a one-hop range from a node, and clustering
over larger spatial ranges is difficult. In recent one-hop clustering methods, a technique has been proposed for efficiently
collecting information within the cluster using parameters
such as node position, velocity, and the number of adjacent
nodes [21]. However, clustering over a larger spatial range is
difficult. The decentralized clustering based on the FokkerPlanck equation on networks has also been proposed [22].
This method can quickly generate cluster structures at various
spatial scales, however, there are stability issues when the
network structure changes drastically.
The clustering algorithms required for general WSNs
should satisfy the following conditions:
• they utilize only local information,
• they can generate clusters of arbitrary spatial size
beyond one-hop clustering, and
• they support the dynamic environment created by network structure changes.
As studies to date have not introduced a suitable clustering algorithm, this paper proposes a framework of
autonomous decentralized clustering that can satisfy the
above
requirements.
TABLE 1. Classification of typical clustering for MWNs.
B. RELATED WORK
The k-means method is the best-known method for partitioning nodes into clusters [23]. This method performs clustering
by sequentially finding the cluster center that minimizes
the distance between the cluster center and each node. The
k-means method has been widely adopted in various fields
because of its simplicity and ease of implementation. In particular, the k-means method is one of the critical techniques
used to solve the routing problem for multi-hop wireless
networks [17], [24]. It provides fast clustering in arbitrary
network topologies, but it requires prior information on the
location of all nodes. Therefore, it cannot be implemented
using only the local information of each node.
As an alternative, spectral clustering is known to yield
appropriate clusters if given the network structure [25], [26].
Spectral clustering requires knowing the matrix representing
the entire network structure in advance. In other words, this
method also cannot be implemented using only the local
information of each node as long as it is done in the usual
way. However, spectral clustering can stably generate cluster
62425
N. Matsuhashi et al.: Autonomous Decentralized Spectral Clustering for Hierarchical Routing of MWNs
structures of various spatial scales. It would be highly desirable if this could be achieved autonomously based only on
each node’s local information.
In general, in order to achieve autonomous distributed control, it is necessary to associate the autonomous distributed
behavior of each node with the state of the entire network
generated by interactions of the nodes’ autonomous behaviors. In order to realize this relationship, one solution is to use
partial differential equations (PDE) [27], [28]. This approach
defines local behavior rules in advance for each node on the
network, and the solutions of the equation are associated with
the state of the entire network.
A method for autonomous distributed spectral clustering
has been proposed in which clusters are periodically constructed for sensor nodes arranged as static two-dimensional
grid networks [16]. This method is based on a PDE that
retains only trigonometric functions with the appropriate
frequency; other oscillation modes are attenuated. The advantage of this scheme is its ability to generate stable spatial
structures in an autonomous decentralized manner. However,
since it supports only regular grid networks, it cannot be
applied to networks with unspecified topologies. In addition,
there is little advantage in constructing cluster structures in
an autonomous decentralized manner because introducing a
periodic spatial structure to a static two-dimensional grid
network topology can be accomplished by centralized control, for example, by assigning periodic clusters in advance.
Therefore, it is necessary to derive autonomous decentralized
clustering methods that can be applied to MWNs with general
topologies.
C. OBJECTIVE
Spectral clustering is an attractive idea for creating an appropriate cluster structure for an arbitrary network topology,
but the conventional method cannot be realized with an
autonomous decentralized algorithm, so it cannot be applied
to the hierarchical routing of MWNs as is. We extend the
autonomous distributed spectral clustering of [16], which was
designed for two-dimensional grid networks, and propose
a principle that can realize distributed autonomous spectral clustering in arbitrary network topologies. Our method
focuses on the spatial structure of specific eigenvectors of
the matrix representing the network structure and introduces
a time evolution equation whose solution is a vector-valued
function that converges on that eigenvector. The clustering
algorithm is a difference equation based on the designed
time evolution equation, which is described so as to utilize
only the local information of each node and immediately
adjacent nodes. This makes it possible to realize autonomous
distributed spectrum clustering for arbitrary network structures. Simulations show that our autonomous distributed
spectrum clustering proposal also works in static environments where nodes do not move. In addition, under the
dynamic condition that nodes do move, we show that the
cluster structure retains its stability even following node
movements.
62426
This paper focuses on how constructing the cluster structure in an autonomous and decentralized way, which is the
basis of hierarchical routing. Note that it does not address
implementation problems including the energy hole problem
[29] and the optimization of various performance metrics
[30]. However, it is, of course, possible to introduce optimization techniques for various performance metrics such
as energy efficiency, protocol overhead, and latency for the
cluster structure constructed by the autonomous decentralized spectral clustering proposal. Optimization seems likely
by reflecting the characteristics of various performance metrics in the elements of the matrix representing the network
structure.
The most significant contribution of this paper is to design
a framework for generating specific eigenvectors of the
matrix representing a network even when its structure is not
fully known. Also, since the computational complexity of
the algorithm involves only the local information of each
node and its neighboring nodes, the data size handled by
each node does not depend on the scale of the network.
In addition, since the spatial structure of the eigenvectors
can be determined by the network designer in advance, it is
possible to give an appropriate cluster structure to dynamic
and complex network structures such as MWNs.
The rest of this paper is organized as follows: In Section II,
prior to introducing autonomous decentralized spectral clustering, we describe the basic operations of creating cluster structures and elementary knowledge of the spectral
graph theory required for spectral clustering. Section III
describes existing autonomous decentralized clustering techniques for sensor networks, which is only applicable to
2-dimensional lattice networks. In Section IV, we propose a
new autonomous decentralized spectral clustering approach
applicable to arbitrary network topologies. In Section V,
we demonstrate the characteristics of the proposed method
by using numerical experiments. Finally, Section VI gives
conclusions.
II. PRELIMINARY
As a preliminary to the description of our autonomous decentralized spectral clustering proposal, this section explains the
basic framework of autonomous decentralized clustering and
elementary knowledge of spectral graph theory, both of which
are necessary to fully understand the proposal.
A. FRAMEWORK OF AUTONOMOUS DECENTRALIZED
CLUSTERING
Each terminal (referred to hereafter as a ‘‘node’’) has a
state quantity as an indicator for clustering. To form a suitable cluster structure, each node exchanges its state quantity
among neighboring nodes based on predefined operation
rules. After an appropriate amount of time has elapsed, each
node compares its state quantity with those of its neighbors
to determine the cluster structure in the following procedure.
1) If the amount of the state quantity of a node is a local
maximum value, the node becomes the cluster head
VOLUME 11, 2023
N. Matsuhashi et al.: Autonomous Decentralized Spectral Clustering for Hierarchical Routing of MWNs
(CH), which is responsible for collecting and forwarding data in the cluster.
2) If the state quantity of a node is not the local maximum
value, it belongs to the same cluster as the node having
the largest state quantities among its neighbors.
Figure 1 shows an example of constructing the cluster structure for a one-dimensional network based on the
abovementioned framework. The horizontal axis represents
the configuration of nodes in the one-dimensional network,
the vertical axis represents the state quantity value of each
node, and the color coding represents each cluster. Nodes
with a bold frame are CHs. Since the cluster structure is
created based on the spatial distribution of state quantities,
in autonomous decentralized clustering, the operation rule
for exchanging the state quantity among nodes is crucially
significant.
FIGURE 1. Example of cluster structure for a one-dimensional network.
B. LAPLACIAN MATRIX
Network structures can be represented as graphs. In an MWN,
nodes correspond to communication terminals, and links correspond to the connections between terminals. Let G(V , E)
denote the undirected graph composed of V = {1, 2, . . . , n},
a set of n nodes, and E, a set of undirected links. The Laplacian matrix L is a way to represent the structure of G(V , E)
and is defined as
L := D − A.
(1)
Here, A = [Aij ]1≤i,j≤n is the adjacency matrix defined as
(
1 ( (i, j) ∈ E ),
Aij :=
0 ( (i, j) ∈
/ E ),
and D is the degree matrix defined as
D := diag(d1 , . . . , dn ),
where di is the nodal degree of node i.
Since L is a positive semi-definite matrix, we can sort n
eigenvalues λµ (0 ≤ µ ≤ n − 1) in the following ascending
order:
0 = λ0 < λ1 ≤ λ2 ≤ · · · ≤ λn−1 .
(2)
Here, the multiplicity of 0 eigenvalue corresponds to the number of connected components of G(V , E). Since we assume
here that G(V , E) is a connected graph, L has only one
VOLUME 11, 2023
0 eigenvalue λ0 = 0. In addition, the maximum eigenvalue
λn−1 satisfies
λn−1 ≤ 2 dmax ,
(3)
where dmax is the maximum nodal degree of G(V , E).
Since L is a real symmetric matrix, the eigenvectors of
L can be chosen as mutually orthogonal. Let vµ (µ =
0, 1, . . . , n − 1) be the eigenvector associated with the
eigenvalue λµ . It follows that we can choose vµ (µ =
0, 1, . . . , n − 1) as the orthonormal basis of the eigenspace
as in
(
1
(µ = ν)
⟨vµ , vν ⟩ =
,
(4)
0
(µ ̸= ν)
where ⟨vµ , vν ⟩ denotes the inner product of vectors.
With regard to the spatial patterns created by the eigenvector components of a Laplacian matrix, it is known that
the eigenvector associated with a larger eigenvalue creates a
finer spatial structure, and conversely, the eigenvector associated with a smaller eigenvalue creates a coarse-grained
spatial structure. For example, the difference in eigenvectors
in a one-dimensional network with 12 nodes is shown in
Fig. 2. Figure 2 shows the components of several eigenvectors
with µ = 0, µ = 3, µ = 7, and µ = 11 from the top; the
horizontal axis denotes the node ID. Clustering based on the
eigenvector is called spectral clustering [25], [26].
If we want to directly apply spectral clustering to an MWN,
we must know the whole structure of the MWN in advance.
That is, to know an eigenvalue of the MWN, we should
know the Laplacian matrix of the MSN first. However, since
MWN structure is not the local information available to each
node, spectral clustering seems difficult to be realized in an
autonomous decentralized manner. In this study, we realize
a spectral clustering method in an autonomous decentralized
manner based on the local actions of each node generated by
a predefined operation rule.
III. AUTONOMOUS DECENTRALIZED CLUSTERING FOR
GRID-ALIGNMENT SENSOR NETWORKS
To design autonomous decentralized control, it is essential
to associate the autonomous and decentralized action of each
node with the resulting state of the entire network caused by
the group effect of nodes. To realize this relationship, we can
adopt the idea of partial differential equations This method
expresses the predefined local action rule of each node in the
network with a PDE and makes the solution of the equation
correspond to the state of the entire network. This idea can
also be applied to autonomous decentralized clustering.
One instance of PDE-based spectral clustering is the
autonomous decentralized clustering for grid-arranged static
sensor networks [16]. This method can achieve autonomous
decentralized spectral clustering by taking advantage of the
frequency space properties of the trigonometric functions
in two-dimensional coordinates. The rule for autonomous
decentralized action of nodes is described by PDEs, and their
solutions give the spatial structure for clustering.
62427
N. Matsuhashi et al.: Autonomous Decentralized Spectral Clustering for Hierarchical Routing of MWNs
FIGURE 3. An example of equation (5).
Fourier transform as
Z
∞
qx (x, y, t) =
Q(ω, y, t) sin(ωx) dω,
(8)
−∞
FIGURE 2. Eigenvectors of a one-dimensional network.
According to [16], we briefly summarize how to derive the
PDEs describing rules for nodes’ autonomous and decentralized action. The method assumes a static network composed
of a two-dimensional lattice network. The position of a node
is denoted by (x, y), the time by t, and the value of the state
of a node by q(x, y, t). Initial state quantity q(x, y, 0) takes a
random value for each node.
First, as a property of the solution q(x, y, t) of the partial
differential equation desired by the designer, we consider a
solution having a spatial structure consisting of sinusoidal
waves in a steady state as follows.
lim q(x, y, t) = lim qx (x, y, t) + lim qy (x, y, t)
(5)
lim qx (x, y, t) ∝ sin kx
(6)
lim qy (x, y, t) ∝ sin ky
(7)
t→∞
t→∞
t→∞
t→∞
t→∞
qx (x, y, t) and qy (x, y, t) are the decomposition of q(x, y, t)
in the orthogonal directions of the x and y axes, respectively,
where k is spatial angular frequency. The stationary states
of qx (x, y, t) and qy (x, y, t) generate sine waves of the same
frequency independently in each direction. Figure 3 shows an
example of the spatial structure of q(x, y, t) created by superpositioning sinusoids of the same frequency. Each mountain
in this state distribution is a cluster.
Since the same procedure can apply to qx (x, y, t) and
qy (x, y, t), we focus on the derivation of a partial differential
equation whose solution qx (x, y, t) has the property of (6).
First, qx (x, y, t) is expressed as a superposition of
sinusoidal waves for some y by exploiting the inverse
62428
under a certain appropriate boundary condition q(0, y, t) = 0,
where Q(ω, y, t) is the amplitude for angular frequency ω.
The desired solution (6) only needs a contribution from
the sinusoidal waves of angular frequency ±k. Therefore,
we design a PDE of amplitude Q(ω, y, t) such that the sine
waves other than the angular frequency k decay with time as
follows:
∂Q(ω, y, t)
= −B (ω − k)2 (ω + k)2 Q(ω, y, t), (9)
∂t
where B is a positive constant. Thus the solution of PDE (9)
is obtained as
Q(ω, y, t) = Q(ω, y, 0) exp(−B (ω − k)2 (ω + k)2 t). (10)
The exponent of exp(−B (ω − k)2 (ω + k)2 t) in (10) is
non-positive and is 0 only when ω = ±k (Fig. 4). Therefore,
the solution (10) decays most of the frequency components
over time, leaving only the contribution at frequency ω = ±k.
Figure 5 illustrates exp(−B (ω − k)2 (ω + k)2 t) in the initial
state at t = 0 (Fig. 5(a)) and in the almost steady state at
t = 3000 (Fig. 5(b)) with respect to ω on the horizontal axis.
As a result, the steady state of qx (x, y, t) coincides with a sine
wave of angular frequency ±k.
FIGURE 4. Behavior of −B (ω − k)2 (ω + k)2 .
From PDE (9) in the frequency space, the PDE of qx (x, y, t)
is obtained by
∂qx (x, y, t)
∂ 4 qx (x, y, t)
∂ 2 qx (x, y, t)
=−B
− 2 B k2
4
∂t
∂x
∂x 2
4
− B k qx (x, y, t).
(11)
VOLUME 11, 2023
N. Matsuhashi et al.: Autonomous Decentralized Spectral Clustering for Hierarchical Routing of MWNs
the Laplacian matrix as
lim q(t) ∝ vµ .
t→∞
(12)
In order to derive a time evolution equation whose solution
is a vector-valued function q(t) with this property, q(t) is
expressed by the inverse graph Fourier transform using eigenvector vµ as
FIGURE 5. Behavior of exp(−B (ω − k)2 (ω + k)2 t ).
q(t) =
n−1
X
aµ (t) vµ ,
(13)
µ=0
Designing the rule for autonomous decentralized action of
each node for both x-axis and y-axis according to PDE (11)
yields a periodic spatial structure like that shown Fig. 3.
It is worth noting that the above autonomous decentralized
spectral clustering technique is applicable only when the
network topology is a grid-arraignment lattice network. This
is because the spatial structures are generated separately for
the x-axis and y-axis and sinusoidal waves are set along each
axis. On the other hand, if we introduce a cluster structure into
such a regular and static network, we do not need to execute
it in an autonomous decentralized manner, and we should
only arrange periodic clusters from the beginning. Therefore,
autonomous decentralized clustering is really needed when
the network structure is not regular and changes dynamically.
IV. AUTONOMOUS DECENTRALIZED SPECTRAL
CLUSTERING
where aµ (t) represents the expansion coefficient of eigenvector vµ in the vector-valued function. Figure 6 illustrates
an example of (13) in a one-dimensional network with three
nodes. Assume that each node has a certain state quantity as
shown in Fig. 6(a). (13) means that the state vector 6(a) can be
expressed by a linear combination of the eigenvectors shown
in Fig. 6(b).
FIGURE 6. The idea of the graph Fourier method.
In this section, we propose an autonomous decentralized
spectral clustering applicable to arbitrary network structures
by extending the previous work [16] in terms of spectral graph
theory. Let qi (t) denote the state quantity of node i at time t,
and q(t) := (q1 (t), . . . , qn (t))⊤ denote the state vector that
arranges the state quantity of each node; the time step to
update the state quantity is set to 1. The initial state vector
q(0) is given a random value at each node.
The desired solution (12) needs the contribution of the
eigenvector vµ associated with just the eigenvalue λµ .
To achieve this, designing the contributions of eigenvectors
other than vµ are damped, we can give the time evolution
equation of the expansion coefficient aµ (t) as
A. OPERATING PRINCIPLE
where b is a positive constant, and c is a positive constant
that determines which eigenvector converges. The solution of
time evolution equation(14) is obtained as
In general, we cannot obtain the eigenvectors of a Laplacian matrix without knowing the Laplacian matrix. Also,
knowing the Laplacian matrix is equivalent to understanding the entire graph structure. In other words, it is difficult
to compute the eigenvectors directly from local information. Autonomous decentralized spectral clustering aims to
achieve spectral clustering based on a certain eigenvector of
a network whose Laplacian matrix is unknown. The rule for
autonomous decentralized action of each node for this aim
is described by using difference equations based on the time
evolution equations. Given the above, we explain the time
evolution equation that serves as the operating principle of
our autonomous decentralized spectral clustering proposal.
To begin, as the desired solution of the time evolution equation that the state quantities of the nodes follow, we consider
a state vector whose steady state is a particular eigenvector of
VOLUME 11, 2023
d
aµ (t) = −b (λµ − c)2 aµ (t)
dt
= −b (λ2µ − 2 λµ c + c2 ) aµ (t),
aµ (t) = aµ (0) exp(−b (λµ − c)2 t).
(14)
(15)
The exponent of exp(−b (λ − c)2 t) in (15) is non-positive
and is 0 only when λ = c (Fig. 7). Therefore, the solution
(15) decays over time except when λ = c. Figure 8 illustrates
exp(−b (λ − c)2 t) in the initial state at t = 0 (Fig. 8(a)) and
the almost steady state at t = 3000 (Fig. 8(b)), with respect
to λ on the horizontal axis. As a result, the steady state of q(t)
coincides with vµ for the given µ = c.
Here, when c is given with a specific eigenvalue,
the solution converges to the eigenvector associated
with the eigenvalue. Since larger/smaller eigenvalues give
finer/coarse-grained spatial structures of clustering, clustering by eigenvectors associated with excessively large
62429
N. Matsuhashi et al.: Autonomous Decentralized Spectral Clustering for Hierarchical Routing of MWNs
this problem, the computation step of the state quantity is
divided into two steps, and a preliminary calculation step
is set prior to the main calculation. The initial time and the
main calculation steps are conducted at t = 0, 1, 2, . . . .
On the other hand, let the execution time of the preliminary
calculation step be t + 1/2 = 1/2, 3/2, /, 5/2, . . . . Then,
the autonomous decentralized operation rules based on the
time evolution equation (16) are expressed by the following
difference equations.
X
qi (t + 1/2) =
(qi (t) − qj (t))
(17)
FIGURE 7. Behavior of −b (λ − c)2 .
j∈∂i
qi (t + 1) = −b
X
qi (t + 1/2) − qj (t + 1/2)
j∈∂i
+ 2b c qi (t + 1/2) + (1 − b c2 ) qi (t)
FIGURE 8. Behavior of exp(−b (λ − c)2 t ).
eigenvalues results in excessive cluster segmentation of the
entire network structure, which loses the merit of clustering.
The time evolution equation of state vector q(t) that satisfies the time evolution equation of the expansion coefficients
(14) is obtained from the orthogonality of the eigenvectors as
d
q(t) = −b (L2 − 2 c L + c2 I) q(t),
dt
where I is the n × n unit matrix.
(16)
B. CLUSTERING ALGORITHM
In autonomous decentralized clustering, nodes should
exchange state quantities based only on local information, which is obtained from themselves and their neighbor
nodes. Therefore, to implement the time evolution equation (16) derived in the previous subsection in nodes, it is
necessary to consider the local action of each node as
determined by (16).
TABLE 2. Differentiation of each term.
For the right side of (16), the correspondence to the difference of each term is summarized in Table (2); where ∂i
denotes the set of nodes adjacent to node i. Terms I q and
L q can be calculated from just the information of self and
neighboring nodes. On the other hand, L2 q corresponds to
a fourth-order difference and requires information from not
only self and neighboring nodes, but also from the nodes adjacent to its neighbors. Therefore, it cannot be calculated in an
autonomous decentralized manner in a single step. To avoid
62430
(18)
At t + 1/2, (17) calculates L q(t) and its value is used
to calculate qi (t + 1) by (18) to update the state quantity.
With these two calculation steps, the calculation of L2 q(t)
is approximated by an operation rule based on just the information of self and neighboring nodes. By implementing this
operation, we can produce a solution corresponding to a particular eigenvector of the Laplacian matrix in an autonomous
decentralized manner.
The autonomous decentralized operating rules shown in
equations (17) and (18) generate, of course, the spatial structure created by the component distribution of a particular
eigenvector on arbitrary network topology if the parameter
c is chosen to be equal to a certain eigenvalue of L. However,
since the structure of the entire MWN is assumed to be
unknown, it is impossible to know the eigenvalues in advance.
Therefore, parameter c cannot be given as c = λµ precisely.
However, eigenvectors belonging to eigenvalues close to c
have a small attenuation rate, so eigenvectors belonging to
eigenvalues close to c become dominant over time. For this
reason, even if c does not exactly equal the eigenvalues, it is
not expected to be a major problem. The validity of this
prediction is discussed later.
Concerning the computational complexity of the proposed
clustering method, since it is autonomous and decentralized,
the data size handled by each node is independent of the
size of the network. However, the speed of convergence to
a specific eigenvector that determines the cluster structure is
a problem. Fortunately, since the eigenvectors other than the
objective eigenvector decay exponentially, even starting from
random initial conditions, converging to the desired eigenvector in less than 100 iterations is possible. For example, when
starting in a random initial state, clustering can be completed
in about 10 seconds if messages are exchanged between nodes
about 10 times per second as the initial operation mode when
the power is turned on. Under normal operating conditions,
there are smaller changes in the network state, so we can
expect to follow the dynamic environment with fewer calculations. Therefore, in normal operation mode, it is possible
to reduce the load by reducing the frequency of message
exchanges between nodes to less than once per second.
VOLUME 11, 2023
N. Matsuhashi et al.: Autonomous Decentralized Spectral Clustering for Hierarchical Routing of MWNs
C. STABILITY CONDITION FOR AUTONOMOUS
DECENTRALIZED SPECTRAL ALGORITHM
In general, when differential equations are solved as difference equations, conditions on the step size of differentiation
are important in guaranteeing the stability of the solutions of
the difference equations. In difference equation (18), a positive constant b determines the amount of state quantity
exchanged between adjacent nodes at one discrete-time step,
which affects the stability of the solution of difference equation (18). Generally speaking, b must be less than a certain
value to obtain a stable solution for difference equation (18).
On the other hand, if b is too small, the amount of state
quantity exchanged becomes small, and convergence of the
solution slows dramatically. The clustering speed depends on
the convergence speed of the solution, and high clustering
speeds are desirable if the cluster structure is to follow the
movement of the nodes. Therefore, in addressing the clustering speed, we need a stability condition of b for difference
solution (18).
Since the vector-valued function q(t) is expanded as (13),
the stability condition of the solution of (18) can be considered as conditions that all aµ (t) (µ = 0, 1, . . . , n − 1)
converge with respect to time t. From difference equation
(18), the difference equation for the expansion coefficients
(14) is given as
aµ (t + 1) − aµ (t) = −b (λµ − c)2 aµ (t).
(19)
The solution of difference equation (19) is expressed as
t
aµ (t) = aµ (0) 1 − b (λµ − c)2 .
(20)
sufficient condition (23) as it is. However, we can use (3) to
replace λn−1 with 2dmax . Let us consider d ∗ , the maximum
number of terminals that can be connected simultaneously.
Since λn−1 ≤ 2dmax ≤ 2d ∗ , we have
(2d ∗
2
2
≤
.
2
− c)
(λn−1 − c)2
In general, d ∗ is available because it is determined as a
specification of the system. Taking into account the clustering
speed, the value of b must be chosen as the maximum value
that can meet the stability condition, and can be designed as
2
2
,
.
(24)
b = min
(2d ∗ − c)2 c2
V. EXPERIMENTAL EVALUATION
In this section, we evaluate the performance of our
autonomous decentralized spectral clustering proposed in the
previous section by using a network model to evaluate its
characteristics.
The environment examined is a two-dimensional space
of [0, 1] × [0, 1], in which 50 nodes are randomly placed
(Fig. 9). The square frame in the figure represents the entire
two-dimensional space. As a model for MWNs, we construct
a network model in the form of a unit disk graph, which
generates links when nodes are within radio range of each
other (Fig. 10). In this experiment, the radio range is set to
l = 0.25. Furthermore, as the terminal specification, the
maximum number of simultaneous connections to adjacent
nodes d ∗ is restricted to 10. That is, each node cannot link
to more than the maximum number of simultaneous connections. Initial state vector q(0) is given as a random number.
Therefore, the condition that ensures aµ (t) does not diverge
is obtained as
1 − b (λµ − c)2 ≤ 1.
(21)
Then, condition b for each µ is derived as
2
2
,
0 < b ≤ min 2 ,
c (λµ − c)2
(22)
where
min
2
2
,
2
c (λµ − c)2
2
2
c
=
2
(λµ − c)2
(2c ≥ λµ ),
(2c < λµ ),
From (2),we have
2
2
≤
2
(λn−1 − c)
(λµ − c)2
for any µ under 2c < λµ . Therefore, the sufficient condition
for b is derived as
2
2
0 < b ≤ min 2 ,
.
(23)
c (λn−1 − c)2
Due to the constraints of MWN as an autonomous
decentralized system, the maximum eigenvalue λn−1 of the
Laplacian matrix cannot be known, so we cannot use the
VOLUME 11, 2023
FIGURE 9. Entire two-dimensional space.
A. EVALUATION IN A STATIC ENVIRONMENT
First, for a static environment in which no node moves,
we check that the stationary state generated from the difference equations (17) and (18) converge to the specified
eigenvectors. Setting eigenvalue λµ to the value of parameter
c determines which eigenvectors converge. However, since
62431
N. Matsuhashi et al.: Autonomous Decentralized Spectral Clustering for Hierarchical Routing of MWNs
FIGURE 10. Unit disk graph.
FIGURE 12. Spectral intensity for the case of c = 2.
the eigenvalue is unknown due to the MWN network structure is unknown, we cannot set c = λµ exactly. Even in
such a case, the eigenvectors associated with the eigenvalues
away from c decay quickly over time, so the eigenvectors
associated with eigenvalues λµ close to c become dominant.
Therefore, even if we do not give c = λµ exactly, we can
expect to get the same cluster structure as if we give c = λµ
exactly. To confirm this, we compare each clustering result
using the components of eigenvectors v4 , v6 and v8 , with
the cluster structure obtained from the proposed method with
c = 1, c = 2 and c = 3, which are values close to λ4 = 0.96,
λ6 = 1.75 and λ6 = 3.06, respectively.
with c = 1, 2, and 3. Cluster heads are marked with stars,
and other nodes are marked with circles. In addition, each
cluster is given a different color. Since clustering results for
each c and for the corresponding eigenvector exhibit the same
clustering structure, we can recognize that clustering based on
the specified eigenvectors is achieved even if we cannot set c
to the exact eigenvalue.
Concerning the above experiment with c = 2, Figure 12
shows the spectral intensity aµ (t) with respect to µ on the
horizontal axis. The initial state and the almost steady state
are shown in Figs 12(a) and (b), respectively. Initially, all
eigenvectors contribute to the state quantity randomly. In contrast, after a sufficient time, the contributions of eigenvectors
other than µ = 6 are attenuated to the point of becoming
insignificant. That is, this indicates that the desired property
(12) for the decay characteristics of the expansion coefficient
is realized.
These results reveal that even when the value of c is not
equal to the eigenvalue, clustering is realized based on the
component distribution of eigenvectors belonging to eigenvalues close to c if enough time passes.
Next, we evaluate the stability of the clustering proposal.
The evaluation results shown below are the average of
30 independent simulation results. The differences in the networks are due to differences in the initial random placement
of nodes. Initial state vector q(0) is also given by a random
number.
FIGURE 11. Comparison of cluster structure based on eigenvectors and
clustering results using the proposed method.
Figure 11 compares the cluster structure based on eigenvectors and the clustering results yielded by the proposed
method. The left side of Figure 11 shows the results of
clustering with the components of eigenvector v4 , v6 and v8 .
The right side of figure 11 shows the result of clustering
after a sufficient time as determined by the proposed method
62432
FIGURE 13. Time transition in the number of clusters in static
environment.
Figure 13 shows the time transition of the number of
clusters under c = 1, 2, 3. Figure 13 reveals that clustering
is stable regardless of the value of c. Furthermore, this result
shows that the larger the value of c is, the larger the number
of clusters is. This is due to a property of the eigenvectors
VOLUME 11, 2023
N. Matsuhashi et al.: Autonomous Decentralized Spectral Clustering for Hierarchical Routing of MWNs
of the Laplacian matrix used for clustering. The results also
indicate that the number of clusters can be roughly adjusted
by parameter c which determines which eigenvectors are to
be converged.
B. EVALUATION IN A DYNAMIC ENVIRONMENT
In the previous subsection, we showed the characteristics of our proposal in a static environment of stationary
nodes. However, since MWN generally assumes a dynamic
environment in which nodes move, it is desirable that the clustering proposal well supports dynamic environments. In this
subsection, we verify that the proposed method can achieve
stable clustering even in dynamic environments.
In dynamic environments, nodes move at random directions and speeds. We assign a random velocity to each node
at every discrete time unit of 1 s. Let ri (t) be the position
of node i at time t and ṙi denotes the velocity of node i.
The magnitude of velocity, ||r˙i ||, of node i is determined
as a uniformly distributed random variable in the range of
[0.007, 0.050] per second. The direction of the movement
of node i is determined as a uniformly distributed random
variable in the range of [0, 2π) per second. When a node
collides with a two-dimensional plane’s boundary, it moves
in a reflective manner (Fig. 14). The evaluation results are
the average of 30 independent simulation results.
FIGURE 15. Time transition in the number of clusters in dynamic
environment.
FIGURE 14. Movement of nodes at a boundary.
Figure 15 shows the time transition of the number of
clusters with c = 1, 2, and 3 under the node velocities of
||ṙi (t)|| × 1, ||ṙi (t)|| × 1/2, and ||ṙi || × 1/4. These results
reveal that stable clustering can be achieved even in dynamic
environments. Also, the change in the number of clusters is
within a certain range, and it can be confirmed that the cluster
size can be adjusted by the value of parameter c.
Figures 16 and 17 show typical examples of cluster structure at time intervals from t = 2950 to t = 3000, for velocity
||ṙi (t)|| × 1 and ||ṙi || × 1/4, respectively. In any cluster structure, the number of clusters does not show extreme changes,
the cluster structure seems stable, and it follows the movement of nodes. Also, we can recognize by comparison that the
change in cluster structure is smaller for ∥ṙi ∥ × 1/4 than that
of Therefore, it can be seen that the variation in the number
of clusters seen in Fig. 15 depends on the movement speed of
the nodes.
Figure 18 illustrates the relationship between the magnitude of fluctuations and the magnitude of node velocities.
VOLUME 11, 2023
This figure shows the mean of the variance at each 100 step
from t = 2000 to t = 3000 under c = 2. The horizontal
axis represents the magnification based on ||ṙi (t)||. Figure 18
reveals that the more slowly the nodes move, the smaller and
more stable the fluctuation in the number of clusters become.
Also, slowing down the speed of movement corresponds
to shortening the time step for updating the state quantity.
Therefore, when nodes move relatively rapidly, like vehicular
ad-hoc networks, increasing the number of updates of the
state quantity per second can suppress fluctuations in the
number of clusters. These results show that the proposed
autonomous decentralized spectral clustering works properly
even in dynamic environments.
Determining the evaluation measures that can yield
improvements in network performance is out of scope of
this paper, but the following enhancements can be considered
as future possibilities. Various performance metrics, including remaining battery capacity, can be reflected as the link
weights set between adjacent nodes for each node. As a
result, it should be possible to change clusters to accommodate a dynamic environment by using autonomous distributed
spectral clustering, which is basically the same framework
proposed in this paper. In other words, it may be possible to
62433
N. Matsuhashi et al.: Autonomous Decentralized Spectral Clustering for Hierarchical Routing of MWNs
FIGURE 18. Fluctuation in the number of clusters due to changes in node
velocity.
VI. CONCLUSION
FIGURE 16. Time transition of cluster structure at ∥ṙi (t )∥ × 1.
In this paper, we proposed an autonomous decentralized
spectral clustering technique based on spectral graph theory
that can be applied to arbitrary network topologies. This is a
significant difference between the conventional technique of
autonomous decentralized spectral clustering, which supports
only grid-arraignment lattice networks Also, the proposed
method focuses on the spatial pattern of eigenvectors of the
Laplacian matrix and derives time evolution equations whose
solutions converge to specific eigenvectors of the Laplacian
matrix. The significant point of the proposed technique is that
it is unnecessary to know the Laplacian matrix of the network,
that is, the structure of the entire network. In other words,
the most significant feature of the proposed method is that
it can generate specific eigenvectors of a matrix representing
the entire network structure for any network without knowing
its structure.
Numerical evaluations confirmed that the proposed clustering technique can realize stable cluster structures based
on spatial patterns of eigenvectors in a randomly arranged
network topology, even without information about the entire
network. Furthermore, we have shown that stable clustering
can be achieved even in a dynamic environment where nodes
move.
To clarify whether the clustering proposal can be applied
even if user movement is intense, it is necessary to investigate
the relationship between the speed of node movement and the
convergence speed of clustering. In addition, extending the
proposed method so that various performance metrics can be
considered when forming cluster structures is left for later
studies.
REFERENCES
FIGURE 17. Time transition of cluster structure at ∥ṙi ∥ × 1/4.
rearrange the cluster structure and cluster head while reflecting the situation so that power consumption is not biased to a
specific node.
62434
[1] V. C. Gungor, D. Sahin, T. Kocak, S. Ergut, C. Buccella, C. Cecati, and
G. P. Hancke, ‘‘Smart grid technologies: Communication technologies
and standards,’’ IEEE Trans. Ind. Informat., vol. 7, no. 4, pp. 529–539,
Nov. 2011.
[2] H. Karl and A. Willig, Protocols and Architectures of Wireless Sensor
Networks. Hoboken, NJ, USA: Wiley, 2005.
[3] H.-C. Jang, Y.-N. Lien, and T.-C. Tsai, ‘‘Rescue information system for
earthquake disasters based on MANET emergency communication platform,’’ in Proc. Int. Conf. Wireless Commun. Mobile Comput., Connecting
World Wirelessly, Jun. 2009, pp. 623–627.
[4] C. K. Toh, Ad Hoc Mobile Wireless Networks: Protocols and Systems.
London, U.K.: Pearson Education, 2001.
[5] X. Hong, K. Xu, and M. Gerla, ‘‘Scalable routing protocols for mobile ad
hoc networks,’’ IEEE Netw., vol. 16, no. 4, pp. 11–21, Jul. 2002.
VOLUME 11, 2023
N. Matsuhashi et al.: Autonomous Decentralized Spectral Clustering for Hierarchical Routing of MWNs
[6] N. Amini, A. Vahdatpour, W. Xu, M. Gerla, and M. Sarrafzadeh, ‘‘Cluster size optimization in sensor networks with decentralized cluster-based
protocols,’’ Comput. Commun., vol. 35, no. 2, pp. 207–220, Jan. 2012.
[7] D. Wohwe Sambo, B. Yenke, A. Förster, and P. Dayang, ‘‘Optimized clustering algorithms for large wireless sensor networks: A review,’’ Sensors,
vol. 19, no. 2, p. 322, Jan. 2019.
[8] I. G. Shayeb, A. H. Hussein, and A. B. Nasoura, ‘‘A survey of clustering
schemes for mobile ad-hoc network (MANET),’’ Amer. J. Sci. Res., vol. 20,
no. 2011, pp. 135–151, 2011.
[9] O. Senouci, S. Harous, and Z. Aliouat, ‘‘Survey on vehicular ad hoc
networks clustering algorithms: Overview, taxonomy, challenges, and open
research issues,’’ Int. J. Commun. Syst., vol. 33, no. 11, p. e4402, Jul. 2020.
[10] S. Basagni, ‘‘decentralized clustering for ad hoc networks,’’ in Proc.
4th Int. Symp. Parallel Archit., Algorithms, Netw. (I-SPAN), 1999,
pp. 310–315.
[11] M. Aida, Decentralized Control And Hierarchical Structure In Information
Networks. Tokyo, Japan: Corona Publishing Co., Ltd., 2015.
[12] I. S. Akila and R. Venkatesan, ‘‘A cognitive multi-hop clustering approach
for wireless sensor networks,’’ Wireless Pers. Commun., vol. 90, no. 2,
pp. 729–747, Sep. 2016.
[13] X. Yuan, M. Elhoseny, H. K. El-Minir, and A. M. Riad, ‘‘A genetic
algorithm-based, dynamic clustering method towards improved WSN
longevity,’’ J. Netw. Syst. Manage., vol. 25, no. 1, pp. 21–46, Jan. 2017.
[14] M. Demirbas, A. Arora, V. Mittal, and V. Kulathumani, ‘‘Design and
analysis of a fast local clustering service for wireless sensor networks,’’
in Proc. 1st Int. Conf. Broadband Netw., 2004, pp. 700–709.
[15] G. Neglia and G. Reina, ‘‘Evaluating activator-inhibitor mechanisms
for sensors coordination,’’ in Proc. 2nd Bio-Inspired Models Netw., Inf.
Comput. Syst., Dec. 2007, pp. 129–133.
[16] T. Kubo, T. Hasegawa, and T. Hasegawa, ‘‘Mathematically designing a
local interaction algorithm for decentralized network systems,’’ IEICE
Trans. Commun., vol. E95.B, no. 5, pp. 1547–1557, 2012.
[17] Z. Z. Shirazi and S. J. Mirabedini, ‘‘Dynamic k-means algorithm for
optimized routing in mobile ad hoc networks,’’ Int. J. Comput. Sci. Eng.
Survey, vol. 7, no. 2, pp. 1–14, 2016.
[18] A. P. R. Balakrishna, ‘‘Energy efficient and secured clustering algorithm
using fuzzy logic with K-means method in MANE,’’ Indian J. Sci. Technol.,
vol. 12, p. 19, May 2019.
[19] D. Zhang, H. Ge, T. Zhang, Y. Cui, X. Liu, and G. Mao, ‘‘New multi-hop
clustering algorithm for vehicular ad hoc networks,’’ IEEE Trans. Intell.
Transp. Syst., vol. 20, no. 4, pp. 1517–1530, Apr. 2019.
[20] S. Chinara and S. K. Rath, ‘‘A survey on one-hop clustering algorithms
in mobile ad hoc networks,’’ J. Netw. Syst. Manage., vol. 17, nos. 1–2,
pp. 183–207, Jun. 2009.
[21] C. Caballero-Gil, P. Caballero-Gil, and J. Molina-Gil, ‘‘Self-organized
clustering architecture for vehicular ad hoc networks,’’ Int. J. Distrib.
Sensor Netw., vol. 11, no. 8, Aug. 2015, Art. no. 384869.
[22] C. Takano, M. Aida, M. Murata, and M. Imase, ‘‘Proposal for
autonomous decentralized structure formation based on local interaction
and back-diffusion potential,’’ IEICE Trans. Commun., vol. E95.B, no. 5,
pp. 1529–1538, 2012.
[23] J. A. Hartigan, Clustering Algorithms. Hoboken, NJ, USA: Wiley, 1975.
[24] M. Ahmed, R. Seraj, and S. M. S. Islam, ‘‘The k-means algorithm: A
comprehensive survey and performance evaluation,’’ Electronics, vol. 9,
no. 8, p. 1295, Aug. 2020.
[25] F. R. K. Chung, Spectral Graph Theory (CBMS Regional Conference
Series in Mathematics), no. 92. Providence, RI, USA: AMS, 1997.
[26] A. Ng, M. Jordan, and Y. Weiss, ‘‘On spectral clustering: Analysis and
an algorithm,’’ in Proc. Adv. Neural Inf. Process. Syst., vol. 14, 2001,
pp. 849–856.
[27] M. Aida and C. Takano, ‘‘Principle of autonomous decentralized flow
control and layered structure of network control with respect to time
scales,’’ in Proc. Suppl. ISADS Conf. Fast Abstr., 2003, pp. 3–4.
[28] C. Takano and M. Aida, ‘‘Diffusion-type autonomous decentralized flow
control for end-to-end flow in high-speed networks,’’ IEICE Trans. Commun., vol. E88, no. 4, pp. 1559–1567, Apr. 2005.
VOLUME 11, 2023
[29] J. Li and P. Mohapatra, ‘‘Analytical modeling and mitigation techniques
for the energy hole problem in sensor networks,’’ Pervas. Mobile Comput.,
vol. 3, no. 3, pp. 233–254, Jun. 2007.
[30] Z. Fei, B. Li, S. Yang, C. Xing, H. Chen, and L. Hanzo, ‘‘A survey of
multi-objective optimization in wireless sensor networks: Metrics, algorithms, and open problems,’’ IEEE Commun. Surveys Tuts., vol. 19, no. 1,
pp. 550–586, 1st Quart., 2017.
NAOKI MATSUHASHI received the B.E. degree
in systems design engineering from Tokyo
Metropolitan University, Japan, in 2021, where he
is currently pursuing the degree with the Graduate
School of Systems Design. He studies autonomous
decentralized clustering algorithm and the theoretical model of social network dynamics.
CHISA TAKANO (Member, IEEE) received the
B.E. degree in telecommunication engineering
from Osaka University, Japan, in 2000, and the
Ph.D. degree in system design engineering from
Tokyo Metropolitan University, Japan, in 2008. In
2000, she joined the Traffic Research Center, NTT
Advanced Technology Corporation. From April
2008 to March 2020, she was an Associate Professor with the Graduate School of Information
Sciences, Hiroshima City University, where she
has been a Professor, since April 2020. Her research interests include computer networks, decentralized systems, and social networks. She is a member
of IEICE and IPSJ. She was a recipient of the IEICE Young Researchers’
Award, in 2003, and the Information Network Research Awards from the
IEICE in 2004, 2012, 2015, and 2019.
MASAKI AIDA (Senior Member, IEEE) received
the B.S. degree in physics and the M.S. degree
in atomic physics from Saint Paul’s University,
Tokyo, Japan, in 1987 and 1989, respectively, and
the Ph.D. degree in telecommunications engineering from The University of Tokyo, Japan, in 1999.
In April 1989, he joined NTT Laboratories. From
April 2005 to March 2007, he was an Associate
Professor with the Faculty of Systems Design,
Tokyo Metropolitan University. Since April 2007,
he has been a Professor with the Graduate School of Systems Design, Tokyo
Metropolitan University. His current interests include the analysis of social
network dynamics and the decentralized control of computer communication
networks. He is a fellow of IEICE and a member of ACM and ORSJ. He was
a recipient of the Best Tutorial Paper Award and the Best Paper Award from
the IEICE Communications Society, in 2013 and 2016, respectively, and the
IEICE 100-Year Memorial Paper Award, in 2017.
62435