Autonomous Decentralized Spectral Clustering for Hierarchical Routing of Multi-Hop Wireless Networks

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