Keywords

1 Introduction

Mobile sensor networks have recently received significant attentions due to their potential applications. This new research field is roughly considered as the intersection of the two well established fields, wireless sensor networks and multi-robot systems, but enriched with diversification of integrating sensing awareness, communication awareness into mobility control for mobile sensor nodes in order to enhance system performances.

A mobile wireless sensor network of mobile sensors obtains several advantages over a traditional wireless sensor network due to controllable mobility of mobile sensors. For instances, a small number of mobile sensors can cooperatively navigate to explore and cover large hazardous environmental areas, detect and exploit environmental data with various equipped sensors, and transmit exploited data to human operators using a multi-hop network of mobile relays. However, we encounter more challenges when deploying and managing a mobile sensor network rather than a transitional wireless sensor network due to spatio-temporal dynamics of mobile sensor nodes, i.e., connectivity maintenance, network topology, data transmission. On the other hand, typical aspects of communication networks, such as communication channels, routing protocols, quality of services have not often considered as research problems in multi-robot systems, instead it is assumed as being available for facilitating the development of various applications, i.e., coordinative exploration, cooperative coverage, collaborative environmental patrolling and monitoring. Connectivity maintenance/preservation—the concept often mentioned in multi-robot systems—is mostly considered in terms of sensing connectivities rather communication connectivities (communication links), and its roles in guaranteeing quality of data communication in a multi-hop network of mobile nodes used to facilitate many applications of networked robotic systems has been not significantly studied. Nevertheless, the quality of communication links is the key element to guarantee inter-communication among sensor agents for their cooperative, coordinative, and collaborative operations. In this paper, we address comprehensive understanding of how to integrate advantageous properties of wireless sensor networks, i.e., communication awareness, and multi-robot systems, i.e., localisation awareness, to enhance the system performance in terms of communication throughput.

1.1 Literature Review

Graph theoretic network: graph theory is widely utilised as an useful tool to model networked systems including wireless sensor network and networked robotic systems. Agents (either robotic or sensor agents) and their connectivities in a networked system are mathematically modelled by nodes and edges of either directed or undirected graph. The Laplacian matrix-based algebraic connectivity is often used to check the global connectivity of the network. Coordinative and cooperative operations of networked systems can be modelled, controlled, and optimised using graph theories and properties [1–5]. However, the primary drawback of representing a multi-agent network in graph theory is that the second smallest eigenvalue—the Fielder value—of the Laplacian matrix is not differentiable so that it is not possible to design feedback control for connectivity maintenance. Connectivity of pairs of agents is therefore equipped with either linear [6] or non-linear weights [2] that works as potential functions to facilitate the feedback control design and stability validation [7–10].

Artificial potential field: the artificial potential field, coined out by Khatib [11], is the well-known method developing artificial potential force-based control by synthesising attractive and repulsive forces. This method is purely based on the local sensing and perception of mobile agents about their peers and environments to drive the mobile robots towards the goal without colliding with obstacles. The artificial potential field method has been extended to develop decentralised mobility control for mobile agents in multi-agent systems (including multi-robot systems and mobile sensor networks) [3, 12–17].

Mobility in wireless networks: Research on impacts of mobility in wireless networks has been traditionally investigated along the other known wireless communication issues causing reduction of quality of communication services i.e., multi-path falling, shadowing, interferences, and Doppler phenomenon. In contrast, mobility has been increasingly considered as an impact factor enhancing usabilities of wireless networks [18–23].

1.2 Motivation

In the real-world applications, a mobile wireless sensor network is deployed into an unknown environment for exploration and environmental data exploitation through two stages: network deployment, and network utilisation. In the first stage, the wireless network of mobile sensors is sent into the environment to self-organise a multi-hop network used to transfer exploited data to human operators. In the second stage, once the multi-hop wireless network is established through interconnected mobile sensor nodes, communication throughput of the network should be maximised for faster and more reliable data transmission from sources to destinations. Controllable mobility of mobile nodes can be utilised to improve the communication throughput of the wireless ad-hoc network. However, this research direction has not been significantly studied, to the best of our knowledge.

In the scope of this paper, we assume that the first stage of the network deployment has been done since mobile sensor nodes have been deployed in the environment. We primarily consider the second stage of the network utilisation with an emphasis on throughput optimisation of mobile sensor networks by incorporating two distributed optimisation techniques: position-aware optimisation and communication-aware optimisation. Specifically, the distributed co-optimisation is developed by integrating advantages of artificial potential fields maintaining sensing and communication connectivities of mobile sensor nodes, and the Max-Flow-Min-Cut graph theory representing communication capacity and information flows of communication links.

1.3 Contributions of This Paper

This paper provides a novel method of distributed co-optimisation of throughput for mobile sensor networks. The contributions can be seen in twofolds:

  • Enforcing two research fields, wireless sensor networks and multi-robot systems, closer by integrating advantages of artificial potential force field and the Max-Flow Min-Cut graph theorem to design the distributed control of mobile sensors for throughput optimisation.

  • Realising a method of distributed co-optimisation—an event-triggered optimisation—based on information flows between mobile sensor notes. This method is fully distributed, allowing a mobile sensor network to enhance its convergence, adaptability, and scalability.

1.4 Paper Outline

The rest of this paper is organised as follows. A short tutorial on graph-theoretic network model of the Max-Flow Min-Cut theorem is described in Sect. 2. Preliminaries of research statement and motivation are in Sect. 3. Detailed description of distributed co-optimisation method consisting of position-aware optimisation and communication-aware optimisation is explained in Sect. 4. Monte-Carlo simulation based statistical results are shown and discussed in Sect. 5. We conclude this paper with future research directions in Sect. 6.

2 Graph-Based Network Model—A Short Tutorial

A graph \(G(V, E) \) is employed to describe a multi-hop wireless ad-hoc network of mobile sensor nodes. V is defined as collection of mobile sensor nodes while E is denoted for the set of peer-to-peer communication links between them. V is divided in three groups: sources S—sending data packets, sinks T—receiving data packets, and routers R—relaying data packets from a source to a destination, where S and T must be non-empty. Each edge \(e(v_i,v_j) \in E\) represents a communication link with a nonnegative capacity \(c(v_i,v_j)\ge 0\). Actual data flow \(f(v_i, v_j)\) between two mobile nodes \(v_i\) and \(v_j\) must be less than capacity of the communication link, \(f(v_i,v_j)\le c(v_i, v_j)\) for every \(v \in V \backslash \{s,t\}\). On a node \(r \in R\), inflow data must be equal to outflow data, \(f_i(r) = f_o(r)\), where inflow \(f_i(r)\) is the sum of incoming data into the node while outflow \(f_o(r)\) is the total data coming out from such a node. Data packets can be transferred from a source \(s \in S\) to a destination \(t \in T\) through either single or multiple communication channels in the wireless ad-hoc network of mobile nodes. The value of a flow f, denoted val(f), from a source s is the amount of data sending out from a source s to a sink t: \(val(f) = \sum _{v \in V}f(s,t)\). Maximum flow, denoted \(f^{max}\), is the maximum network flow: \( val(f^{max}) \ge val(f), \forall {f}\). A cut is a group of edges connecting a group of sources \(V_s\) and a group of destinations \(V_t\) through a number of relay nodes \(V_r \in V\). Capacity of a cut is the total capacity of communication links on the cut, \(c(V_s,V_t)\). Minimum cut, denoted \(c^{min}(V_s,V_t)\), of the network is the minimum total capacity of the set of communication links involved in the cut.

Bottlenecks of a network are where communication links with maximum flows are existing. According to the Max-Flow Min-Cut graph theorem [24], maximum flows are minimum cuts so that we can search for minimum cuts, instead maximum flows, to find bottlenecks of a network. The residual graph, \(G(V,E): c_{f}(e_j,e_i) = c(e_i,e_j) - f(e_i,e_j)\) is used to check whether an augmenting path exists in the residual graph \(G(V, E) \) connecting a source S to a destination T. No existence of augmenting path in the residual graph guarantees that the network is at maximum flow. Note that, if the network has more than one source (destination), a super-source (super-destination) connecting with all sources (all destinations) by edges of infinity capacity is required for generating the residual graph.

3 Preliminaries and Problem Statement

3.1 Relative Localisation and Communication Capacity

We consider a kind of wireless networks of mobile sensor nodes communicating each other in the peer-to-peer fashion. The network is deployed into an unknown environment for fast exploration, monitoring, patrolling, and data collection. The mobile sensor nodes automatically navigate to explore in the environment while preserving connectivities with their neighbouring peers. Mobile sensor nodes are capable of self-organising a multi-hop wireless network for information exchange. A node becomes a source if it transfers environment-exploited data through the self-organising network of mobile routers—working as relays of the network—to a destination. Data packets are delivered through either single or multiple communication channels of the wireless network before reaching the destination. Therefore, communication throughput of such channels is expectedly maximised for faster and more reliable data transmission.

We assume that the mobile sensor nodes are equipped with ranging sensors that can sense and measure the relative distance to other sensor nodes and obstacles within its local vicinity for their manoeuvrability. Without loss of generality, we presume that the communication range is longer than the sensing range for all mobile sensors so that two sensor nodes can communicate well if they are mutually within their sensing range. In other words, communication connectivity can be identified through sensing connectivity. According to the principle of path-loss of signal propagation (without considering effectiveness of multi-path fading and shadowing as explained in [25, 26]), capacity of a communication link established by two mobile sensor nodes is inversely proportional to their relative distance so that capacity of a communication link of two mobile sensor nodes increases if such mobile sensor nodes manoeuvre towards each other. However, this principle can not apply for the actual information flow because it depends on usage of such a communication link in the network—a communication link is established between two nodes but no actual information is delivered throughout this link due to routing protocols.

Relative localisation of the mobile sensor nodes can be identified through estimation of relative distance and relative bearing extracted by the ranging sensors. Artificial potential force field (APF) coined out in [11] is the popular method maintaining relative localisation of mobile sensor nodes by the trade-off of attractive forces pulling the nodes closer and repulse forces pushing the nodes away. Artificial Physics-based potential force field introduced in [14] is a simple but efficient method for preserving sensing connectivities of mobile sensor nodes using a combination of relative distance and relative bearing. However, the Artificial Physics-based mobility control might not directly optimise communication throughput of the network because this mobility control is not aware of capacity and information flow of communication links. Note that the Artificial Physics-based mobility control might implicitly improve capacity of communication links since the potential forces drive mobile sensor nodes to equilibrium positioning among their neighbouring nodes.

Communication-aware mobility control on a sensor node is expected to relocate the node to appropriate positioning among their nearest neighbours where they contribute better to the network throughput. To do so, this sensor node must be aware of its relative localisation and capacity and information flow of communication links made with its nearest neighbours. However, on one hand, measures of capacity and actual information flow of communication links are not sufficient enough to design the mobility control of mobile sensor nodes due to lacking information of relative localisation because most of communication mechanisms used for wireless sensor networks is a kind of unidirectional signal propagation. On the other hand, sensing-based relative localisation is not sufficient enough to design mobility control of mobile sensor nodes for throughput optimisation as this control is not aware of capacity and information flow of communication links. As a result, we synthesise sensing-based relative localisation and measures of capacity and information flows of communication links to design the distributed mobility control of mobile sensor nodes that is capable of improving the network throughput.

3.2 Shortcomings of the Max-Flow Min-Cut Theorem in Distributed Schemes

The Max-Flow Min-Cut theorem cannot be directly applied to search for bottlenecks of a mobile sensor network due to the following shortcomings: (1) information of the entire network about the nodes and communication links must be deterministic; (2) computational complexity is high according to the centralisation scheme; (3) a super-source(-destination) is required if more than one communication channel exist. Indeed, in the Max-Flow-Min-Cut theorem [24], maximum flows are identified through capacity of minimum cuts, \(f^{max}(V_s,V_t) = c^{min}(V_s,V_t)\), in a network, so that we can search for minimum cuts instead maximum flows in a multi-hop wireless network of mobile routers. However, to search for minimum cuts of a graph representing a network of mobile sensor nodes using the Max-Flow Min-Cut theorem, the database of all the nodes and their communicational links must be deterministic for any heuristic searching algorithms applied for finding an augmenting path. That is, all the mobile nodes must exchange information about communication capacity and information flows of their communication links through the entire network, which is usually not applicable to wireless networks of mobile sensor nodes due to dynamic changes in terms of relative localisation and communication link capacity. Moreover, if multiple sources (destinations) exist, a virtual super source (destination) must be created and all sources (sinks) are connected to this super source (destination) with \(\infty \) capacity of communication links to make a multi-commodity source (destination) for augmenting path algorithms, which is not often implementable for wireless networks in the real world. Computational complexity of the Max-Flow Min-Cut theorem is dependent to number of nodes and communication links in the network, i.e., Ford-Fulkerson algorithm O(E |f|), Edmonds-Karp algorithm \(O(VE^2)\), Dinitz blocking flow algorithm \(O(V^2E)\), as so the more nodes and communication, the higher computational cost. As a result, a large-scale network of mobile sensor nodes is not scalable to number of nodes as the sensor nodes encounter highly computational cost while a part of network bandwidth is reserved for transferring updating information of communication capacity of communication links and actual information flows from all other sensor nodes to every node for its operations of searching for minimum cuts of the network.

4 Distributed Co-optimisation

The great advantage of the Max-Flow Min-Cut theorem is to find bottlenecks—minimum cuts—of a graph-modelled network. Without this algorithm, we cannot find minimum cuts where the mobile sensor nodes should move towards in order for increasing capacity of the existing communication links. However, to employ the Max-Flow Min-Cut algorithm for throughput optimisation of mobile sensor networks, we encounter the limitations which are not feasible in distributed schemes as explained in Sect. 3.2.

We propose a distributed co-optimisation that decentralises the Max-Flow Min-Cut theorem by searching for possible minimum cuts, where there highly possibly exist saturated communication links, \(f(v_i,v_j) \le c(v_i,v_j)\). The mobile sensor nodes are capable of estimating possible minimum cuts by measuring differential between capacity and information flow of communication links made with their neighbouring nodes, \(c(v_i,v_j) - f(v_i,v_j)\). Such nodes also need to identify relative directions of possible minimum cuts and maintain relative localisation (relative distance and relative bearing) with their neighbouring nodes through the Artificial Physics-based potential forces. As a result, we synthesise capacity and information flows of communication links and the Artificial Physics-governed relative localisation to develop a distributed mobility control of mobile sensor nodes for throughput optimisation as seen in (1):

$$\begin{aligned} F_{dco}(v_i) = \left\{ \begin{array}{cl} \displaystyle \sum _{v_j \in {N(v_i)}}\frac{f(v_i,v_j)}{ \varepsilon + ( c(v_i,v_j) - f(v_i,v_j))}*\frac{\overrightarrow{F_{AP}}(v_i,v_j)}{\parallel \overrightarrow{F_{AP}}(v_i,v_j)\parallel } &{} \quad \text { if } f(v_i,v_j) \ne 0 \\ \displaystyle \sum _{v_j\in {N(v_i)}}\overrightarrow{F_{AP}}(v_i,v_j) &{} \quad \text { if } f(v_i,v_j) = 0 \end{array} \right. \end{aligned}$$
(1)

where \(c(v_i,v_j)\) and \(f(v_i, v_j)\) is the capacity and information flow of communication link \(e(v_i,v_j)\) made by the sensor node \(v_i\) with its neighbouring nodes, \(v_j \in {N(v_i)}\), respectively; \(\overrightarrow{F_{AP}}(v_i,v_j) = \frac{G*m(v_i)*m(v_j)}{r^2} \) is the Artificial-Physics-based potential force between the sensor node \(v_i\) and its neighbouring nodes, \(v_j \in {N(v_i)}\), in which r is the relative distance between i and j and the gravitational constant G is arbitrarily chosen; \(\varepsilon \) is arbitrarily chosen as small as possible, \(\varepsilon \ll \sum _{v_j \in {N(v_i)}}{c(v_i,v_j)} \), to avoid the case of fully saturated communication links, \(c(v_i,v_j) = f(v_i,v_j)\), \(\forall v_j \in {N(v_i)}\).

All the mobile sensor nodes with the distribtued mobility control described in (1) operate in two stages:

  • Position-Aware Optimisation: If no information flow is detected by the mobile sensor node, it only uses the Artificial Physics-based potential forces to maintain connectivities with their neighbouring nodes, which might indirectly impact on improvement of capacity of communication links leading to better throughput.

    $$\begin{aligned} F_{pao}(v_i) = \sum _{v_j\in {N(v_i)}}\overrightarrow{F_{AP}}(v_i,v_j) \quad \text { if }f(v_i,v_j) = 0 \end{aligned}$$
    (2)

  • Communication-Aware Optimisation: If information flows are detected by the mobile sensor node, it uses possible minimum cut based potential force \(F_{cao}\) to navigate towards the neighbouring node involved in the minimum cut with the most saturated communication links in order for gaining capacity of communication links leading to better throughput (Fig. 1).

$$\begin{aligned} F_{cao}(v_i) = \displaystyle \sum _{v_j \in {N(v_i)}}\frac{f(v_i,v_j)}{ \varepsilon + ( c(v_i,v_j) - f(v_i,v_j))}*\frac{\overrightarrow{F_{AP}}(v_i,v_j)}{\parallel \overrightarrow{F_{AP}}(v_i,v_j)\parallel } \quad \text { if } f(v_i,v_j) \ne 0 \end{aligned}$$
(3)
Fig. 1
figure 1

Distributed co-optimisation for mobile sensor networks—information flow triggered optimisation—in two stages: if the information flows are detected, the communication-aware optimisation is activated to relocate mobile sensor nodes to new positions with better throughput through Eq. 3; if information flows are not detected, the position-aware optimisation is used to preserve the communication connectivities among the sensor nodes, which might implicitly improve throughput through Eq. 2

Full size image

5 Monte-Carlo Simulations and Discussions

5.1 Experiment Setup and Performance Metrics:

The Monte-Carlo simulation method is applied to generate randomised experimental scenarios. A typical scenario with three stationary base stations operated as sources and destinations are created as seen in Fig. 2a. We have applied the Gaussian random distribution to place the sensor nodes into the experimental scenario as an example illustrated in Fig. 2b. The generated scenarios are selected for experiments if three base stations are well connected through an ad-hoc wireless network of mobile sensor nodes. For each experiment, we executed 10000 simulation steps to measure the network throughput between the base stations. The statistical results shown in Fig. 3 were collected from 100 randomised scenarios.

Fig. 2
figure 2

The experimental scenario with three stationary base stations (LHS) stationary base stations, (RHS) randomly placed mobile robots. a Three stationary base stations. b 15 randomly placed sensor nodes

Full size image
Fig. 3
figure 3

The Monte-Carlo simulation based statistical results of 3 stationary base stations. a 10 sensor nodes b 15 sensor nodes c 20 sensor nodes

Full size image

We propose four key performance metrics to evaluate the developed distributed co-optimisation algorithm:

  • Optimality: how much is the network throughout of the mobile wireless sensor network gained over time?

  • Adaptability: is the network throughput adaptable to incremental number of sensor nodes added into the network?

  • Convergence: how fast does the network throughput converge to a steady state?

  • Scalability: does computational complexity of sensor nodes increase to infinity if the number of sensor nodes added into the network increases to infinity?

5.2 Results and Discussions

Based on the statistical results, we discuss on the key performance metrics of the distributed co-optimisation algorithm.

Fig. 4
figure 4

Statistical results of random scenarios with the number of sensor nodes increased from 9 to 20

Full size image

Optimality: Looking at the statistical results shown in Figs. 3 and 4, the network throughput is improved at all cases, which affirms that the distributed co-optimisation algorithm is capable of locally optimising the overall network throughout of mobile sensor networks.

Adaptability: The statistical results shown in Figs. 3 and 4 show that the network throughput of mobile sensor networks is gained with the improvement rate from 15 to 50 % approximately when the number of sensor nodes used in the network increases from 10 to 20 nodes. It is proved that the distributed co-optimisation adaptively deals with the number of sensor nodes used in the network.

Convergence: Looking into the statistical results of the network throughput in Fig. 3, the distributed co-optimisation algorithm enables the network throughput of mobile sensor networks converge to a steady state after 5000 running steps approximately in all cases. Convergence is one of the most important issues of mobile sensor networks because the sensor nodes no longer need to consume energy for their mobility control, and the communication channels become stable for data transmission between the base stations.

Scalability: Supposing that we use a centralisation method, i.e., Ford-Fulkerson algorithm, Edmonds-Karp, or Dinitz blocking flow algorithm, to search for minimum-cuts, a sensor node must collect all information about capacity of communication links and information flows from the other sensor nodes through the network communication. This leads to dramatically increased computational cost on every sensor nodes i.e., Ford-Fulkerson algorithm O(E |f|), Edmonds-Karp algorithm \(O(VE^2)\), Dinitz blocking flow algorithm \(O(V^2E)\) as well as an substantial amount of the network bandwidth reserved for updating such information (depending the number of sensor nodes deployed in the network). Applying the distributed co-optimisation algorithm, each mobile sensor node only uses its local information of information flows and capacity of communication links made with its nearest neighbours, as so no network bandwidth is reserved for updating such information of the network. Moreover, the computational complexity of mobile sensor nodes is almost constant, O(1), as it is only dependant to the number of its nearest neighbours which is usually a small number in the real world.

Overall, the distributed co-optimisation method is reliably practical in the real-world applications because it enables mobile sensor networks to be adaptable in dynamic environments where communication links of mobile sensor nodes do not often last long due to mobility of mobile sensor nodes and uncertainty of environmental conditions, and scalable with the number of sensor nodes according to applicable requirements.

6 Conclusions and Future Directions

We have addressed the problems of throughput optimisation in mobile sensor networks. The distributed co-optimisation algorithm used to control mobility of mobile sensor nodes for throughput optimisation is developed by cross-fertilising advantages of the artificial potential force field and the Max-Flow Min-Cut graph theorem. The concept possible minimum-cuts is proposed as the key factor to optimise the throughput using the distributed optimisation algorithm. Through the Monte-Carlo simulations, we have proved that the developed algorithm have achieved all the four performance metrics: optimality, adaptability, scalability, and convergence.

In the near future, we are going to work on realistic communication models of communication links with considerations of multi-path fading, shadowing, and interferences as discussed in [26, 27] and even delay models of mobile relays before we call back this distributed co-optimisation method to validate system performances. We believe that network throughput might vary according to new parameters introducted, but this distributed optimisation method is highly applicable due to its systematic characteristics in terms of adaptability, scalability and convergence.