Two Dimensional Swarm Formation in Time-invariant External Potential:
Modelling, Analysis, and Control

Wireless Sensor Networks (WSNs) have attracted much attention due to its ability to provide ubiquitous and multi-faceted situational awareness with a host of applications ranging from structural health monitoring, habitat surveillance, and target detection to power system management, smart car parking, and wireless luggage tags Erol-Kantarci and Mouftah (2011); Gao and Jin ; Li et al. (2002); Ling et al. (2009); Srikanth et al. . WSN depends on spatially distributed sensor node to measure and collect the desire environmental data within its sensing range, and then transmit to a control center called Base Station (BS). The ideal WSN should be autonomous, robust, scalable, and with extended network lifetime. However, WSNs are usually deployed in hostile environments where energy resources is limited. As energy is constrained and data transmission is most energy costly, WSNs algorithms need to be architect in ways where data transmission, especially to BS, is minimized. Clustering become an often utilized technique in designing energy efficient algorithm for WSNs.

Cluster formations can be readily observed in Nature, such as bird flocking and fish schooling. These organism systems are expressing collective motion behaviours and are studied in a relatively novel interdisciplinary field of research, Swarm Intelligence (SI). Individual agents in the swarm are simple agents with limited sensing abilities and computational rules, and interacting with each other locally. Nevertheless, the swarm as a whole demostrates emergent global behaviours which are unknown to the individuals. SI systems have the desirable properties of being distributed, autonomous, scalable, and robust Blum and Li (2008). All of which are key in designing algorithms for WSNs.

Plentiful of clustering algorithm has been developed Gomathi and Sivanesan (2019); Jin et al. (2008); Mehdi Afsar and Tayarani-N (2014). However, besides the main objective of energy conservation, the existing clustering algorithms mainly focus on the optimalization of sensor protocal routines to enhance WSNs in scalability, fault-tolerance, data aggregation, load balancing and network topology stability. All of which data transmission to BS is unavoidable. To address the energy efficiency challenge from a new perspective, this paper combines SI concept with WSNs. We focuses on designing WSNs algorithm where desired environmental information are obtained through analyzing the change in sensor cluster formations (swarm formation) rather than information collected directly through individual sensors, thereby minimizing the energy expenditure in data tranmission between sensors and eliminates the necessity of BS.

We identify the envrionmental information as a external potential hypersuface $M$ of $(n-1)$-dimensions ($n=3$ or $n=4$). Mathematically, $M$ is a Riemannian manifold defined by the set of solutions to a single equation

where $F$ is a $C^{\infty}$ function. We introduce a formation analysis algorithm which uses swarm formation in external potential to estimate curvature, which is invariant under isometry, of the manifold $M$.

This paper is organized as the follows. In section II, we introduce the topology of swarm lattice formation and demonstrate how to construct such formation in an arbitary external potential. In section III, we explain the theoretical basis and computations for the formation analysis algorithm. In section IV, we formulate an formation control algorithm which shows how the swarm lattice formation can be obtained by dynamical control of the individual agents. In section V, we discuss the simulation results of both formation analysis and formation control algorithms.

The topology definition of the swarm formation is inspired by Reynolds Reynolds (1987) and Olfati-Saber Olfati-Saber (2006). In this paper, we consider line formation. In the line formation, agents are being divided into two groups: one head agent and the following agents. The head agent acts as an initial stimuli to the swarm motion. Its dynamics can be predefined and are not affected by the following agents in the swarm.

Define a path graph $P_{n}$ as a pair $(\mathcal{V},\mathcal{E})$ that consists of a set of vertices $\mathcal{V}=\{v_{1},v_{2},\dots,v_{n}\}$ and a set of edges $\mathcal{E}$ such that $\mathcal{E}\subseteq\{v_{i},v_{i+1}\}$, where $i=1,2,\dots,n-1$. Each vertex represents an agent of the swarm, while the edges represent the inter-agent communications. Let $q_{i}\in\mathbb{R}$ denote the position of agent $v_{i}$ for all $v_{i}\in\mathcal{V}$. The vector $q=(q_{1},...,q_{n})^{T}$ is the configuration of all agents of the swarm. The inter-agent distance, that is the length of edges, is defined to be the geodesic length between two connected vertices over $G(q)$. To maintain identical inter-agent distance, we consider an algebraic constraint on the edges,

A configuration $q$ that satisfying the set of constraints in (2) is refered as a lattice formation.

To formulate lattice formation in any arbitary external potential $M$, we need to first define the trajectory of the head agent, then construct a representation of edges – a parallel vector field that is metrically orthogonal to the head agent trajectory, and finally calculate the geodesic deviation vector field. The trajectories of the following agents are the integral curvces of the geodesic deviation vector field. The theoretical basis Lee (1997) and details of the formulation are discussed as follows.

Let $U\subseteq\mathbb{R}^{n}$ be a non-empty open subset and $F:U\rightarrow\mathbb{R}$ a $C^{\infty}$ function defining the external potential. Let $M\subseteq U\times\mathbb{R}$ be the graph of $f$. The closed subset $M$ in $U\times\mathbb{R}$ projects homeomorphically onto $U$ with inverse $(x_{1},\ldots,x_{n})\mapsto(x_{1},\ldots,x_{n},F(x_{1},\ldots,x_{n}))$ that is a smooth mapping from $U$ to $U\times\mathbb{R}$. $M$ is a closed smooth submanifold of $U\times\mathbb{R}$. Using the standard Riemannian metric on $U\times\mathbb{R}\subseteq\mathbb{R}^{n+1}$, the induced metric $g$ on $M$ at a point $p\in M$ is

with coordinate chart $\{q_{i}\}$ on $M$. Each $\partial_{q_{i}}|_{p}\in T_{p}M$ can be represented as a linear combination of $\{\partial_{x_{i}}|_{p}\}\in T_{p}(\mathbb{R}^{n+1})$, given as

Consider the aforementioned graph $M$ as a $C^{\infty}$ Riemannian manifold. Given a curve, $C:[a,b]\longrightarrow M$, a vector field $X$ along $C$ is any section of the tangent bundle $TM$ over $C$ ($X:[a,b]\longrightarrow TM$, projection $\pi:TM\longrightarrow M$, such that $\pi\circ X=C$). If $M$ is a smooth manifold, all vector field on the manifold are also smooth. We denote the collection of all smooth vector fields on manifold $M$ as $\mathfrak{X}(M)$. For a Riemannian manifold $(M,g)$, the Levi-Civita connection $\nabla_{g}$ on M is the unique connection on $TM$ that has both metric compatibility and torsion freeness. The Christoffel symbols of the second kind are the connection coefficients (in a local chart) of the Levi-Civita connection denoted as

For a Riemannian manifold $(M,g)$, a curve is called geodesic with respect to the connection $\nabla_{g}$ if its acceleration it zero. That is a curve $\gamma$ where $\nabla_{\dot{\gamma}}\dot{\gamma}=0$. A geodesic curve in n-dimensional Riemannian manifold can be expressed as a system of second order ordinary differential equations,

All geodesics are the shortest path between any two points on the manifold.

We predefine the trajectory of the head agent to be a geodesic curve on manifold. Base on (6), for a two-dimensional manifold $(M,g)$, head agent trajectory $h(t)$ can be expressed as a system of ordinary differential equations

where basis $\{x,y\}$ are used in the index, and $\dot{h}$ are the first derivative with respect to time. Each Christoffel symbols depends entirely on the metric at a certain point in $M$ in terms of basis $\{x,y\}$. Given initial conditions, $[x_{1},x_{2},\dot{x}_{1},\dot{x}_{2}]$, (7) is guaranteed to have a solution according to the Picard-Lindel$\rm{\ddot{o}}$f theorem. This choice of head agent trajectory is made to simplify agent’s dynamic control. On the geodesic, the head agent is traveling with constant velocity given initial position and velocity, thus no requirement for outside reference beacon.

The distance of the edges of lattice formation needs to be identical. For edges representation, a parallel vector field $K$ that is orthogonal to the head agent trajectory $h(t)$ is constructed as

$K$ forms a family of geodesics where we require the initial position and velocity conditions $(u^{j}_{0},v^{j}_{0})$ for $j$th geodesic $\gamma_{j}\in K$ are $u^{j}_{0}=h(t_{j})$, $v^{j}_{0}=v:g(v,\dot{h}(t_{j}))=0$, $j\in\mathbb{Z}$. The frequency of inter-agent communications is defined by the number of geodesics in $K$ within given traveling time.

The separation vector $s(t)$ connects a point $\gamma(t)$ on one geodesic to a point $\gamma(t)+s(t)$ on a nearby geodesic at the same time. For parallel vector field $K$, we can construct a separation vector field $S$ such that $s\in S$ are the separation vector discribed above. For the swarm lattice formation, the following agents’ trajectories are the integral curves of $S$. Fig. 1 gives a visual example of two-dimensinal swarm lattice formation traveling in external potential.

In Fig. 1, one can notice the change in swarm lattice formation as it travels due to the curvature of the external potential manifold. As an invariant property under isometry, curvature tensor gives valuable information about the external potential manifold itself. We quantify this change as the acceleration of the separation vectors $s\in S$ along $K$, which is equivalent to the change in the difference of neighbouring agents’ velocities. Geodesic deviation equation relates the acceleration of the separation vector between two neighbouring geodesic curves to Riemann curvature tensor. The theoretical elements Lee (1997); Ivancevic and Ivancevic (2007) and analysis method are discribed in details as follows.

The Riemann curvature tensor is a $(1,3)$ tensor defined through the Lie bracket on $(M,g)$ as

where $X,Y,Z\in\mathfrak{X}(M)$, and $R(X,Y)Z$ is vector-valued. $R(X,Y)Z$ can be express in local chart as

By our definition in section II, the separation vector $s$ can be written as vectors,

between two nearby geodesics. The separation acceleration field $W$ is

where $V$ is the separation velocity field . In a local chart, $W$ and $V$ can be expressed as

where $\dot{\gamma}\equiv\displaystyle\frac{d\gamma}{dt}$. Combining (13) and (14) gives

where $\ddot{\gamma}\equiv\displaystyle\frac{d^{2}\gamma}{dt^{2}}$. Rearranging (11) to be

where separation vector $s(t)$ is treated as an expansion parameter. Make use of the fact that both $\gamma$ and $\widetilde{\gamma}$ are geodesics, then we have

Inserting (17) into (15), the first-order geodesic deviation equation is

A vector field $J$ along a geodesic $\gamma$ is called a Jacobi field if

where $\ddot{J}\equiv\nabla_{\frac{d}{dt}}\nabla_{\frac{d}{dt}}J$, and $\dot{\gamma}\equiv\frac{d\gamma}{dt}$. Obviously, the deviation vector field $S$ is a Jacobi field.

Furthermore, sectional curvature is a equivalent but more geometrical description of the curvature of Riemannian manifolds. Let tangent 2-plane, $\Pi_{p}$, be the two dimensional subspace in $T_{p}M$ defined as $\Pi_{p}\equiv span\{u,v\}$, with $u,v\in T_{p}M$. Sectional curvature $\kappa$ of $(M,g)$ at a point $p\in M$ with respect to the plane $\Pi_{p}$ is defined as

Substitude the vector fields $K$ and $S$ we constructed in section II into (20), we have

Also $S$ is in fact a Jacobi field along $K$ that is also orthogonal to $K$. That is $W\equiv\nabla^{2}_{\tau}S=-R(K,S)K$, and $\langle K,S\rangle=0$. Combining with the fact that the integral curves of $K$ are geodesics set to have velocity $|\dot{\gamma}|=1$, the equation for sectional curvature is simplified to

For a two dimensional Riemannian manifold $(M,g)$, there is only one sectional curvature at each point $p\in M$.

In summary, by recording the change of swarm lattice formation in external potential, observer can quantify two variables: $S$, agents’ velocities; $W$, the second-order differences of nearby agents’ velocities. The geodesic deviation equation (22) relates $W$ and $S$ by sectional curvature $\kappa$ of the external potential manifold.

To stay in lattice formation as the swarm travling through external potential, individual agent needs dynamic control of its trajectory. The trajectory of individual agent can be considered as a dynamical system of the form Strogatz (1994)

where $\mathbf{x}$ is the state of the system, that is the position of the agent, and $\mathbf{F}$ is a vector field depends on the system. In practice, we consider the equivalent discrete-time dynamical system,

where $\mathbf{x}_{k}$ is the sampling of agent trajectory in (23) discretely in timesteps $\Delta t$. If we can assume the system is of linear dynamic, then we can work with the form

where it admits a closed-form solution

The entire system dynamic is characterized by the eigenvalues and eigenvectors of the matrix $\mathbf{A}$. Using spectral decomposition, one can simplify the dynamic system to

with $\mathbf{A}=\mathbf{P\lambda P}^{-1}$, and $\mathbf{w}=\mathbf{P}^{-1}\mathbf{x}$. Using $\mathbf{A}$, we can also predict agents’ trajectories in time, thereby controlling the swarm to be in its lattice formation as time evolves.

Even though it is desirable to work with linear dynamical systems, the curvature property of the external potential manifold, and thus the trajectories of agents are essentially nonlinear. To analyze nonlinear dynamic with linear technique, we utilize Koopman operator theory.

We introduced a new approach for designing energy efficient WSNs algorithms inspired by swarm intelligence. In this approach, we identify clustering WSN as swarm, and external potentials as manifolds. By observing the change of swarm lattice formation in external potential, we are able to estimate the curvature of the manifold, which are valuable information of the external potential. To maintain lattice formation in external potential, fomation control algorithm uses DMD to predict the optimal agent’s velocity in time thus guiding the trajectory of following agents.