Shuttle-run synchronization in mobile ad hoc networks

Abstract

In this work, we study the collective dynamics of phase oscillators in a mobile ad hoc network whose topology changes dynamically. As the network size or the communication radius of individual oscillators increases, the topology of the ad hoc network first undergoes percolation, forming a giant cluster, and then gradually achieves global connectivity. It is shown that oscillator mobility generally enhances the coherence in such networks. Interestingly, we find a new type of phase synchronization/clustering, in which the phases of the oscillators are distributed in a certain narrow range, while the instantaneous frequencies change signs frequently, leading to shuttle-run-like motion of the oscillators in phase space. We conduct a theoretical analysis to explain the mechanism of this synchronization and obtain the critical transition point.

Graphical abstract

Keywords

synchronization / phase transition / ad hoc network

1 Introduction

A mobile ad hoc network (MANET) is a time-dependent network self-organized by a collection of wireless mobile devices, such as laptops and smartphones, without the aid of any established network infrastructure or centralized administration (base stations) [1, 2]. In such a network, each mobile node operates not only as a host but also as a router, forwarding packets for other mobile nodes in the network that may not be within direct wireless transmission range of each other. A MANET has the advantages of fast and easy deployment, as well as decreased dependence on infrastructure. Therefore, wireless communications based on MANETs have great potential for applications in diverse environments, such as daily life, the battlefield, and disaster areas involving firefighting or search-and-rescue.

In the past decade, synchronization in complex networks has been extensively investigated. In most previous works, the networks are assumed to have static topologies [3–6]. However, in certain situations, synchronization among moving physical agents might be important, for example, in wireless sensor networks [7] or ad hoc vehicular networks [8], where the mobility of agents should naturally be considered. Although a few works investigated collective behaviors in time-dependent topologies [9, 10], overall we still know little about the interplay between the network topology and dynamics in such networked systems. Motivated by the idea that the MANET represents a physical problem involving both synchronization [11] and critical phenomena [12], in this work we explore the collective behavior of moving agents forming a MANET. Remarkably, we find a novel synchronization (clustering) phenomenon: in a wide parameter regime, the phases of coherent oscillators can become localized in a certain narrow range, while their directions of motion frequently reverse, leading to shuttle-run-like motion of the oscillators in phase space. We further conduct a theoretical analysis to explain the mechanism of this interesting synchronization. Moreover, we analytically obtain the critical transition point of the synchronization.

The rest of the paper is organized as follows. In Section 2, we introduce the MANET model and the dynamical model of phase oscillators. In Section 3, we investigate the percolation of the MANET and characterize its topological properties. In Section 4, we describe the shuttle-run synchronization in our model and characterize this phenomenon in both macroscopic and microscopic terms. In Section 5, we further conduct mean-field analysis to explain the observed shuttle-run synchronization and analytically obtain the critical transition point. Finally, a brief summary ends this paper.

2 Dynamical model

Our model consists of N moving oscillators in a two-dimensional (2D) domain with size L\times L. For a physical picture, one can imagine that passengers with ad hoc mobile phones roam in an airport or a railway station. All oscillators stay in certain positions for a period τ and then simultaneously move to their next positions with constant velocity (speed) v but random directions. We denote the direction of the jth oscillator as {\varphi }_j\in [0,2\pi ]. The positions of oscillators in the domain are governed by the following equations:

\begin{array}{}\text{(1)}& \begin{array}{c}{x}_j(t_{m+1})=x_j(t_m)+v\cos {\varphi }_j(t_m)\text{mod}L,\hfill \\ y_j(t_{m+1})=y_j(t_m)+v\sin {\varphi }_j(t_m)\text{mod}L,\hfill \end{array}\end{array}

where t_m denotes a discrete time step, t_{m+1}-t_m=\tau. In this work, periodic boundary conditions are adopted. Actually, this model belongs to the class of random waypoint models, which have been widely used in simulations [2]. In our study, we also assumed that the oscillators have different velocities (i.e., speeds). For example, the velocities of the oscillators take the uniform distribution or Gaussian distribution. The simulations show that these changes do not significantly affect the collective dynamics of the oscillators. Thus, in this paper, we report the results assuming a uniform distribution.

The dynamics of the coupled oscillators are described by the Kuramoto model [13, 14]:

\begin{array}{}\text{(2)}& {\dot{\theta }}_n={\omega }_n+\lambda {\displaystyle \sum _{j=1}^{k_n}}{a}_{nj}\sin ({\theta }_j-{\theta }_n),n=1,\mathrm{\dots },N.\end{array}

Here {\theta }_n ({\omega }_n) is the instantaneous phase (the natural frequency) of the nth oscillator. The dot denotes the temporal derivative, and λ is the global coupling strength. Further, a_{nj} are the elements of the network’s adjacency matrix, which is determined dynamically by the positions of oscillators governed by Eq. (1) (a_{nj}=1 when nodes n and j are connected, and a_{nj}=0 otherwise). In addition, k_n={\sum }_{j=1}^N{a}_{nj} is the degree of oscillator (node) n.

The set of N natural frequencies \{{\omega }_n\} is drawn from a certain frequency distribution (FD) g(\omega ). Without losing generality, we consider typical FDs, such as the triangle, Lorentzian, and uniform distributions. In Table 1, we summarize the formula and parameters for these FDs. We emphasize that under different FDs, the results obtained are qualitatively the same.

To characterize the phase synchronization in the model, a global order parameter can be defined as

\begin{array}{}\text{(3)}& r{\mathrm{e}}^{\mathrm{i}\psi }={\displaystyle \frac{1}{N}}{\displaystyle \sum _{j=1}^N}{\mathrm{e}}^{\mathrm{i}{\theta }_j},\end{array}

where r and ψ are the module and argument of the mean field, respectively. Geometrically, the complex order parameter can be regarded as a vector on the complex plane. According to its definition, r is between 0 and 1. Typically, r\approx 0 indicates a totally random phase distribution, i.e., the incoherent state, where oscillators rotate almost according to their natural frequencies; in contrast, r>0 indicates a (partially) phase-locking state, i.e., the coherent or synchronized state, where some of the oscillators become phase-locked to the mean field. A larger r value indicates a more coherent system. For the classical Kuramoto model, it has been shown that as the coupling strength increases, the system will bifurcate from the incoherent state into the (partially) coherent state. This transition can usually be characterized as a second-order transition of the order parameter. Throughout this paper, numerical integrations of coupled ordinary differential equations are computed by the fourth-order Runge–Kutta method with time step h=0.01. The initial conditions for the phase variables are random, and the initial positions of the oscillators in the simulation domain are also random.

3 Percolation and topology

In our simulations, we set the dimensionless length of the square domain L to 1000. The velocity of the oscillators v is a constant between 0 and 100. Typically, . The time interval τ is also a constant, typically \tau =0.1 (The integration time step h is 0.01.) We assume that N oscillators move in the square domain. Each has an effective communication radius denoted by R. If two oscillators are within the distance R of each other, they are regarded as connected. Owing to the motion of the oscillators, this link may be maintained or break, yielding a MANET with a dynamic topology.

We first investigate the connectivity of this MANET. Apparently, both N and R affect its topology. It is shown that with sufficiently large N and R, all the oscillators connect with each other to form a connected network. In this case, we say that global connectivity has been achieved. Here, by global connectivity, we mean that all the oscillators have connected with each other to form a giant cluster. We do not mean all-to-all coupling among the oscillators. Figure 1(a) shows a snapshot of one such MANET. Note that although the topology constantly changes, the MANET as a whole remains a single connected network. It is well known that global connectivity in a MANET is achieved through percolation. Figure 1(b) characterizes this transition when R is used as the control parameter. We define f=N_c/N, where N_c is the number of oscillators in the largest cluster. For small R, oscillators connect with their neighbors to form many small clusters, but those clusters are essentially isolated. In this case, f\approx 0. When R is increased to exceed a critical value, a giant cluster forms whose size is comparable to N. The point where f becomes greater than 0 indicates the transition point of percolation. As shown in Fig. 1(b), the percolation belongs to the second order, i.e., continuous percolation. Moreover, percolation occurs at smaller R when N increases. After percolation, f increases rapidly to reach 1, showing that the MANET has achieved global connectivity. Similarly, we observe continuous percolation when N is used as the control parameter, as shown in Fig. 1(c). Figure 1(d) shows the phase diagram on the N–R plane. The two lines are guides to the eyes and mark percolation (dot-dashed line) and full connectivity (dashed line). Because static and homogeneous conditions are assumed, the density of oscillators in the physical domain is \rho =N/L^2. Global connectivity will be achieved when \rho \pi R^2=1. Thus, N\propto R^{-2}. This approximately explains the power-law relation between N and R in Fig. 1(d).

We now investigate the statistical properties of the MANET with full connectivity. First, we study the degree distribution. Figure 2(a) shows some examples. The degree approximately satisfies a Poisson distribution. With increasing R or N, the average degree increases. Because an oscillator can connect only to its neighbors within the distance R, on average its degree should be proportional to the area of this circle and N; i.e., ⟨k⟩=\rho \pi R^2\propto N{R}^2. This relation is verified in Figs. 2(b) and (c). Then we calculate the clustering coefficient of the MANET with global connectivity. It is found that with increasing N, the clustering coefficient rapidly saturates to 0.6 or so, as shown in Fig. 2(d). From the inset there, we can see that the same happens with respect to R. The approximate clustering coefficient of such a MANET can be analytically estimated as 0.59 [15]. The simulation results agree well with the theory.

4 Shuttle-run synchronization

We now study the synchronization of Kuramoto phase oscillators on the MANET. First, we explore an example with N=500 and R=80. From the phase diagram in Fig. 1(d), we know that the network has achieved global connectivity with these parameters. Figure 3(a) plots the order parameter r with respect to the coupling strength λ. We find that the velocity plays an important role in achieving synchronization in such a dynamic network. Increasing the velocity of the oscillators will generally enhance the synchronization. Remarkably, we find that as long as the velocity of the oscillators is sufficiently large, synchronization can also be induced in the MANET even when it has not reached global connectivity. Figure 3(b) shows a typical example of this case. According to the phase diagram in Fig. 1(d), N=500 and R=50 does not lie in the regime of global connectivity. In fact, these parameters are located between the two lines marking percolation and global connectivity; i.e., in this case, only a giant cluster that does not contain all the oscillators forms. As shown in Fig. 3(b), as the velocity increases, oscillators can achieve synchronization when the velocity is sufficiently large. This point can be explained as follows. As shown in Ref. [9], the mobility of the oscillators favors the exchange of information in the network. In our model, a large velocity apparently strengthens the interaction among the oscillators, thus inducing or enhancing synchronization in such a system.

We then investigate the microscopic picture of the synchronous (coherent) state. As shown in Fig. 4(a), when the coupling strength is large, the order parameter rapidly approaches 1, indicating that a coherent state has been achieved in the system. Interestingly, the coherent state here is essentially different from those observed in previous studies of Kuramoto-like models, where the phases of the oscillators in the coherent cluster are locked to the phase of the mean field. As shown in Figs. 4(b) and (c), in our model, the phases of the oscillators in the coherent cluster are only loosely locked to the phase of the mean field. Specifically, this state has two characteristics. First, each oscillator in the coherent cluster has a different phase lag with respect to the mean phase. On the whole, the phases of synchronous oscillators are distributed within a narrow band around the phase of the mean field. In phase space, they are concentrated on a small arc of the unit circle [Fig. 4(b)]. Second, the phases of coherent oscillators actually fluctuate within a very small range. They are not constants as in typical cases. This can be further verified in Fig. 4(d), where the instantaneous frequencies of coherent oscillators are plotted. The instantaneous frequencies all fluctuate around the mean value, leading to the fluctuations of the phases. Thus, the coherent state in our model can be regarded as a weaker form of the phase synchronization observed in classical Kuramoto-like models. In such a state, the coherent oscillators are distributed in a narrow range in phase space, and, most importantly, they keep rotating in a manner resembling a shuttle run. For this reason, we call this phenomenon shuttle-run phase synchronization.

5 Theoretical analysis

To further reveal how this special coherent state is generated, we carefully examine the time series of oscillators in the network. The results are presented in Fig. 5, in which the temporal evolution of some typical oscillators is plotted. From Fig. 5(a), we see that the phases of the oscillators may increase or decrease, but very slowly. This phenomenon can be explained by Fig. 5(c), which shows that the instantaneous frequencies of the oscillators frequently change their signs. Because the sign of the frequency represents the rotational direction of an oscillator, this leads directly to the shuttle-run-like motion of the oscillators in phase space. Furthermore, the instantaneous frequencies of the coherent oscillators are generally small, which guarantees that the coherent oscillators can only rotate forward and backward within a narrow range in the unit circle. This situation will generally hold when the characteristic time scale of the shuttle run is much smaller than that of the dynamics of the oscillators.

To obtain insights on shuttle-run synchronization in our model, we conduct an analysis based on mean-field theory. We notice that the most important characteristic in our model is the dynamic topology. To reveal how this factor affects the collective behavior of oscillators, we define a local parameter as

\begin{array}{}\text{(4)}& r_n{\mathrm{e}}^{\mathrm{i}{\psi }_n}={\displaystyle \frac{1}{k_n}}{\displaystyle \sum _{j=1}^{k_n}}{\mathrm{e}}^{\mathrm{i}{\theta }_j},\end{array}

where k_n is the degree of oscillator n. Then Eq. (2) can be written in the mean-field form:

\begin{array}{}\text{(5)}& {\dot{\theta }}_n={\omega }_n+k_n\lambda r_n\sin ({\psi }_n-{\theta }_n),n=1,\mathrm{\dots },N.\end{array}

From Eqs. (3) and (4), we have

\begin{array}{}\text{(6)}& r={\displaystyle \frac{1}{N}}{\displaystyle \sum _{n=1}^N}{\displaystyle \frac{k_n}{⟨k⟩}}{r}_n;\end{array}

i.e., the global order parameter r equals the weighted average of the local order parameter r_n. If the network is homogeneous, r\approx r_n. This condition can be well satisfied because in our model the degree distributions [Fig. 2(a)] are generally Poisson-like. Therefore, Eq. (5) can be approximated as

\begin{array}{}\text{(7)}& {\dot{\theta }}_n={\omega }_n+k_n\lambda r\sin (\psi -{\theta }_n),n=1,\mathrm{\dots },N.\end{array}

This equation has a similar form to that for the classical Kuramoto model. However, owing to the dynamic topology, k_n will constantly change. Thus, we cannot expect a rigorous steady state for Eq. (7), which requires \dot{\theta }=0. The interesting physics here is that although the instantaneous frequency for each oscillator in the coherent cluster cannot be strictly 0, its average, ⟨\dot{\theta }⟩, could be approximately 0. This point can be heuristically understood on the basis of Eq. (7). Because the topology of the MANET in our model turns out to be homogeneous, as time passes, the instantaneous degree of the oscillators n will generally fluctuate around the mean degree of the network. In addition, we find that the fluctuation of k_n depends crucially on the parameter τ. Note that τ characterizes the time scale of changes in the positions of the oscillators, which cause a relatively large perturbation to the topology of the network. As shown in our simulations, it is at these special moments that the degrees of the oscillators fluctuate most significantly [Fig. 5(c)]. According to Eq. (7), the fluctuation of the local degree induces the fluctuation of the effective strength of the mean field, i.e., k_{n}r. Consequently, the instantaneous frequency of the oscillator fluctuates around a mean value (here it is 0) in the long term. As evidence, Fig. 5(d) shows that the instantaneous frequency of an arbitrary oscillator in the network is basically correlated with the change in its degree. Therefore, we have successfully revealed the mechanism of shuttle-run synchronization observed in our model.

On the other hand, it is always desirable to obtain the critical point in synchronization issues. For our model, we can analytically obtain the critical coupling strength for the synchronization transition using mean-field theory. According to Ref. [11], under the constraint of fast switching, we can perform an approximate analysis of the synchronization properties of our model by replacing the time-dependent coupling matrix A in Eq. (2) with its time average \overline{A}, where \overline{A} is an all-to-all weighted matrix. Eq. (2) then becomes

\begin{array}{}\text{(8)}& {\dot{\theta }}_n={\omega }_n+\lambda {\displaystyle \sum _{j=1}^N}{\overline{a}}_{nj}\sin ({\theta }_j-{\theta }_n),n=1,\mathrm{\dots },N,\end{array}

where all the elements in \overline{A} are identical, and {\overline{a}}_{nj}=pN. Here, p is the probability that a link is activated (i.e., that two oscillators are neighbors). Because p=\pi R^2/L^2 and the density of oscillators \rho =N/L^2, {\overline{a}}_{nj}=pN=\rho \pi R^2=⟨k⟩/N. Then Eq. (8) can be written as

\begin{array}{}\text{(9)}& {\dot{\theta }}_n={\omega }_n+{\displaystyle \frac{⟨k⟩\lambda }{N}}{\displaystyle \sum _{j=1}^N}\sin ({\theta }_j-{\theta }_n),n=1,\mathrm{\dots },N.\end{array}

This is essentially the original Kuramoto model with an effective coupling strength ⟨k⟩\lambda. In fact, if we approximate k_n by ⟨k⟩in Eq. (7), we obtain the same mean-field form as Eq. (9).

According to Kuramoto’s theory, the critical transition point for synchronization is at {\lambda }_c^{KM}=2/[\pi g(0)], given a symmetric FD centered at 0. Therefore, the critical point for Eq. (9) can be obtained by the scaling transformation ⟨k⟩{\lambda }_c={\lambda }_c^{KM}, which yields

\begin{array}{}\text{(10)}& {\lambda }_c={\lambda }_c^{KM}/⟨k⟩.\end{array}

Substituting ⟨k⟩=\rho \pi R^2=N\pi R^2/L^2 and g(0)=1/(\pi \mathrm{\Delta }) (these are the same for all three FDs shown in Table 1) into the above equation, we finally obtain the critical point as

\begin{array}{}\text{(11)}& {\lambda }_c={\displaystyle \frac{2\mathrm{\Delta }{L}^2}{N\pi R^2}}.\end{array}

This is approximately the critical point for our model, Eq. (2). To verify the theoretical result in Eq. (11), we conduct numerical simulations. As shown in Fig. 6, the analytical analysis agrees well with the numerical results.

6 Conclusion

In this work, we investigated synchronization in a MANET. Interestingly, we found a novel synchronization phenomenon in which the coherent phase oscillators are distributed in a narrow range in phase space. They continue to move slowly, but they frequently reverse directions, just as in a shuttle run. Through numerical simulations and a theoretical analysis, we revealed that this special type of synchronization is induced by the fluctuation of the mean field, which is a natural consequence of the dynamic topology of a MANET. We demonstrated that the characteristic time scale of the shuttle-like motion is dominated by the time scale on which the positions of the oscillators in the physical domain change. Using mean-field analysis, we successfully explained the mechanism of shuttle-run synchronization and obtained the critical transition point analytically. The theory is well supported by the simulation results. This work enhances our understanding of collective behaviors in time-dependent networks.

References

[1] C. E. Perkins, Ad Hoc Networking, New York: Addison-Wesley, 2000

[2] T. Camp, J. Boleng, and V. Davies, A survey of mobility models for ad hoc network research, Wireless Commun. Mobile Comput. 2(5), 483 (2002)

[3] S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, and D. U. Hwang, Complex networks: Structure and dynamics, Phys. Rep. 424(4–5), 175 (2006)

[4] S. Liu, Z. W. He, and M. Zhan, Firing rates of coupled noisy excitable elements, Front. Phys. 9(1), 120 (2014)

[5] Y. Zhang and W. H. Wan, States and transitions in mixed networks, Front. Phys. 9(4), 523 (2014)

[6] P. Ke and Z. G. Zheng, Dynamics of rotator chain with dissipative boundary, Front. Phys. 9(4), 511 (2014)

[7] F. Sivrikaya and B. Yener, Time synchronization in sensor networks: A survey, IEEE Netw. 18(4), 45 (2004)

[8] C. Thiemann, M. Treiber, and A. Kesting, Longitudinal hopping in intervehicle communication: Theory and simulations on modeled and empirical trajectory data, Phys. Rev. E 78(3), 036102 (2008)

[9] Z. Liu, Effect of mobility in partially occupied complex networks, Phys. Rev. E 81(1), 016110 (2010)

[10] N. Fujiwara, J. Kurths, and A. Díaz-Guilera, Synchronization in networks of mobile oscillators, Phys. Rev. E 83(2), 025101 (2011) (R)

[11] M. Frasca, A. Buscarino, A. Rizzo, L. Fortuna, and S. Boccaletti, Synchronization of moving chaotic agents, Phys. Rev. Lett. 100(4), 044102 (2008)

[12] L. Wang, C. P. Zhu, and Z. M. Gu, Scaling of critical connectivity of mobile ad hoc networks, Phys. Rev. E 78(6), 066107 (2008)

[13] Y. Kuramoto, Chemical Oscillations, Waves, and Turbulence, New York: Springer, 1984

[14] S. H. Strogatz, From Kuramoto to Crawford: Exploring the onset of synchronization in populations of coupled oscillators, Physica D 143, 1 (2000)

[15] W. Krause, I. Glauche, R. Sollacher, and M. Greiner, Impact of network structure on the capacity of wireless multihop ad hoc communication, Physica A 338(3–4), 633 (2004)

Rights & permissions

Higher Education Press and Springer-Verlag Berlin Heidelberg 2015