Minimizing maximum cost in task coverage problem with multiple mobile sensors: A heuristic approach based on all-pairs shortest path

Abstract

We address a task coverage problem to cover all given tasks with a given number of mobile sensors. In this context, we consider tasks as certain points or regions that should be probed by sensors. Our work is to find initial tasks to deploy sensors in advance, and find an efficient set of search paths from the initial tasks that completely covers all tasks and minimizes the maximum cost among paths. This is a challenging issue for various sensor applications, particularly those related to time-critical missions, such as search and rescue operations. We propose an algorithm that selects a set of all-pairs shortest paths with fewer duplicated tasks and extends each path using remaining tasks while covering all tasks and avoiding cost increases. Experimental results demonstrate that the proposed algorithm provides efficient solutions compared to existing algorithms in terms of coverage and maximum path costs.

Keywords

Mobile sensors distributed coordinated search task coverage problem time-critical coverage multi-robot system

Introduction

As our lives are increasingly threatened by disasters and environmental pollutants, such as earthquakes, tsunami, airborne particulate matter, and chemical contaminants, the use of sensors to monitor real-world environments has become a popular research area. Sensors are widely used not only to detect abnormal changes (e.g. temperature sensors can detect a forest fire¹) but also to search an area to respond to a disaster (e.g. chemical sensors can find contaminated areas). Conventionally, when deploying sensors, the objective is to determine the optimal sensors for maximal coverage while minimizing energy costs.² In this scenario, sensors are positioned in static locations and can thus be deployed quickly to provide continuous information; however, such sensors have limited battery capacity. Due to difficulties associated with handling exhausted batteries and deploying sensors in appropriate locations to respond to unpredictable events, mobile sensors have been investigated.^3–6 There has been active research in exploring, deploying, and covering a target environment;⁷ where to deploy sensors;⁸ and how to evolve sensor location over time.⁹

Coverage is to cover all given locations, areas, or tasks with respective sensors. To achieve coverage, we consider a mobile sensing platform and focus on coordinated search strategies to select initial sensor locations and their movement trajectories. Specifically, our problem is motivated by the requirements of unexpected time-critical events, such as disaster rescue and detoxification missions. Our goal is to find the initial locations and trajectories (paths) of a set of given sensors that allow such missions to be accomplished as quickly as possible. Specifically, it is to (1) find initial tasks, that is, find locations where sensors are to be deployed in advance and begin sensing as required, and (2) find an efficient set of search paths from the initial tasks that completely covers all tasks and minimizes the maximum cost among paths. Min and Papanikolopoulos¹⁰ suggested that a large number of robots (i.e. mobile sensors) do not always provide a quick solution to coordinated search coverage problems. They attempted to find the minimum coverage time assuming that each mobile platform is deployed from the same location. However, this assumption restricts some possibilities in terms of the coverage cost of multiple sensors. In contrast, we consider initially unfixed locations for sensors that must cover a set of target locations.

In a time-critical search with multiple coordinated sensors, it is most important to reduce the maximum search time among all sensors because such missions can only be completed after the last search has been performed by the mobile sensor with the maximum search time. Traditional coverage problems often deal with maximizing the coverage area and minimizing total coverage cost,^2,3 in which the costs of mobile sensors can be power, time, bandwidth, and so on. In our work, we consider coverage cost as the sum of costs defined in two locations, which include general terms such as power and time. However, for parallel mobile sensors executing a mission, total coverage cost is less meaningful than the maximum coverage cost. Minimizing the total cost of all mobile sensors may help minimize energy consumption; however, it may not optimize mission completion time. For parallel multiple sensors, minimizing the maximum cost among all sensors is more important for time-critical missions.

Pursuing the minimal maximum cost is very challenging even for a known number of mobile sensors due to complexity and uncertainty. Figure 1 shows an example of representing different search costs according to the selection of initial sensor locations and their corresponding trajectories. In the graphs, the vertices (blue squares) indicate locations to be visited. Edges are represented as dashed lines, and the numbers indicate their connections with respective costs. Hereafter, we refer to a location to be searched as a task. As can be seen in Figure 1(a) and (b), even though the structure of the environment is the same, the maximum search costs with two mobile sensors differ. Figure 1(a) illustrates initial tasks D and E and their trajectories. Here, the maximum cost is 6. In Figure 1(b), where the initial tasks are A and B, the maximum search cost is 7. From these examples, it is evident that the initial tasks and their trajectories can significantly affect maximum search cost, that is, the time required to accomplish the search mission.

Figure 1.

Example showing the significance of the selection of initial tasks for a given number of sensors (two). Tasks and their edges are represented by blue squares and dashed lines, respectively. We assume that the cost is the same in both directions: (a) a search from initial tasks D and E for two paths is compared with (b) a search from initial tasks A and B.

In this study, we investigate a task coverage problem (TCP) with mobile sensors in which sensors must completely cover (i.e. search and visit) all given tasks. Assuming a given number of mobile sensors and a set of predefined tasks, the goal is to find efficient paths that consist of the initial tasks and subsequent suitable tasks to solve the TCP with minimal maximum search cost. We propose a path-finding algorithm based on all-pairs shortest paths. For multiple mobile sensors, minimizing the maximum cost relies heavily on the selection of initial tasks. Therefore, the proposed algorithm selects the initial set of tasks from a pool of all-pairs shortest paths sorted in increasing order of path cost since the shortest paths usually cover more tasks with minimum costs. To avoid overlap in the initial set of tasks, we consider similarities among the visiting tasks for each path in the set. When the initial set of paths does not cover all tasks, we extend each path with the remaining shortest paths to include uncovered tasks. Since path selection may yield cost variations, that is, less than the maximum cost, we attempt to balance the cost by removing some tasks from the sensor with the maximum cost and assigning these tasks to other sensors with lower cost. The proposed algorithm minimizes the maximum cost to accomplish a time-critical search and guarantees that mobile sensors completely cover all given tasks.

Our contributions are as follows. (1) Compared to existing studies that focus on a single initial task for all sensors or multiple predefined initial tasks, the proposed task coverage algorithm provides trajectories and identifies initial tasks. (2) The proposed technique minimizes maximum cost; thus, a mission can be accomplished as quickly as possible, which is the most important goal for a time-critical mission. (3) We formally demonstrate that the proposed algorithm completely covers all tasks, and provide extensive experimental results to demonstrate that the proposed technique minimizes the maximum coverage cost.

TCP with mobile sensors

In our TCP, a task represents a position or a stationary object that a mobile sensor must cover. Tasks can be considered regions of interest, for example, regions suspected of containing bombs. They can also be considered the locations of stationary sensors, for example, a battery may need to be charged at a given location (i.e. task). In other words, with regard to deploying mobile sensors, the problem is to find a certain number of tasks where the tasks act as sensor’s start positions in order to traverse paths that minimize the maximum travel cost. Note that we assume that a predefined set of tasks is known a priori. We will discuss the k-task coverage problem (kTCP) for a k number of mobile sensors in the “Problem description” and “Objective” sections, respectively. We will then mention a real-world application for the target problem in the “Application” section.

Problem description

For simplicity and without loss of generality, we use a graph representation for our coverage problem. We consider a weighted graph $G = (P, E)$ , where $P = {p_{1}, \dots, p_{| P |}}$ is the set of tasks representing points (note that P is used same as a set of nodes N or a set of vertices V in a general graph), and $E = {e_{ij} | e_{ij} = (p_{i}, p_{j}), p_{i}, p_{j} \in P}$ is the set of task edges. Here, two tasks $p_{i}$ and $p_{j}$ are connected and have cost $cost (e_{ij})$ when traversing $p_{i}$ to $p_{j}$ . In addition, $Π = {π_{1}, \dots, π_{k}}$ is a set of paths for mobile sensors where each path has a certain cost represented by the sum of the weighted edges on the path. Note that the initial number of sensors is denoted as k, and $cost (π_{r})$ denotes the cost of the rth path $π_{r}$ , that is, $cost (π_{r}) = \sum_{e_{ij} \in π_{r}} cost (e_{ij})$ . Note that $π_{i, j}^{(r)}$ and $cost (π_{i, j}^{(r)})$ represent the rth path in $Π (1 \leq r \leq k)$ , and its initial and destination tasks are denoted as $p_{i}$ and $p_{j}$ , respectively. Other tasks between $p_{i}$ and $p_{j}$ may exist in the path. Note that $Γ (\cdot)$ represents a set of tasks arranged in a path.

For a given set of nodes with their weighted edges, we attempt to minimize the maximum path cost (MPC) for k available sensors along paths that cover all tasks. Note that the k number of sensors varies depending on the number of sensors required to complete a given mission. kTCP finds the search paths of k sensors and is defined as follows.

Definition 1

The kTCP is to find a set $Π = {π_{1}, \dots, π_{k}}$ of paths that are sequentially connected subsets for a given tasks P with weighted edges E. The set $Π$ satisfies that $\cup_{r = 1}^{k} Γ (π_{r}) = P,$ where the ∪ operator indicates the union of tasks in a path.

MPC is the search cost of the maximum (i.e. longest) path among the k paths and is defined as follows.

Definition 2

MPC: The maximum cost path denoted as $π_{\max}$ is the path with the maximum cost in $Π$ when the selected paths in $Π$ cover all tasks. MPC is defined as $cost (π_{\max})$ . For a set $Π$ of distinct subsets (paths) satisfying $\cup_{r = 1}^{k} Γ (π_{r}) = P,$ the MPC is defined as

c_{mpc} \equiv \max_{r = 1}^{k} cost (π_{r})

(1)

Note that tasks do not need to be visited more than once; however, multiple visits to the same tasks are allowed only if including them in a path reduces the respective path cost. We also assume that all edges have non-negative weights and the graph must be connected.

Objective

The objective is to find a solution for kTCP that minimizes the MPC when a graph $G = (P, E)$ and k sensors are given. Specifically, we attempt to find a set of paths $Π$ (among all possible sets) that completely cover a given set of tasks and minimize the maximum travel cost. We review relevant research considering optimization of maximum cost in detail in the “Literature review” section. Differing from them, our problem considers to find initial tasks to minimize MPC. This is expressed in equation (1a), where the complementary condition is satisfied and the constraints are distinct start and destination tasks in each path (equations (1b)–(1d)). Note that start tasks are not defined in a priori and the start tasks in different paths are distinct in equation (1d)

minimize \max_{r = 1}^{k} c o s t (π_{r})

(1a)

subject to \cup_{r = 1}^{k} Γ (π_{r}) = P

(1b)

π_{i, j}^{(s)} \neq π_{u, v}^{(r)} for \forall s, r = 1, \dots, k, (s \neq r)

(1c)

p_{i} \neq p_{u} for p_{i} \in π_{i, j}^{(s)}, p_{u} \in π_{u, v}^{(s)}

(1d)

Here, k is the given number of sensors and $| π_{r} |$ is the number of tasks in the path $π_{r}$ .

Application

Here, we introduce a real-world application suitable for our TCP. The proposed kTCP algorithm can be used for a team of mobile platforms with sensors. Here, a team of sensors gather information regarding tasks in an environment and a team of mobile search sensors cover the environment cooperatively. For example, consider an aerial vehicle flying in an environment in which moving platforms with sensors must execute a search mission. In such a mission, a team of fast aerial vehicles with appropriate resources can cooperate with mobile sensors. This type of cooperation is also applicable to underwater environments. One team of vehicles constructs an information map, including tasks and their edges, while another team of search sensors distributively controls along with the generated paths.

Figure 2 shows an example of map generation using an unmanned aerial vehicle, that is, a drone (Figure 2(a)). Here, assume that a bomb has been placed underneath a car. We must know where the car is in a certain parking lot and cover candidate cars to search for the bomb. Images are captured sequentially as the drone flies over the parking lot to generate images with identified search positions (red dot, Figure 2(b)). The tasks and their edges are shown in Figure 2(c). Here, we assume that fast and large platforms can generate an information map consisting of tasks and their edges. The proposed technique can be applied to generate a set of cost-efficient paths using known resources (i.e. k sensors) to search the bomb.

Figure 2.

Map generation process: (a) drone, (b) map generated by the drone, and (c) tasks and their edges in a coordinate system.

Literature review

In sensor networks, coverage typically indicates the degree to which the sensing field is monitored by sensors.¹¹ Here, the sensing field can be areas (i.e. regions),^12–14 points,^15,16 or barriers^17,18 that should be fully covered. However, these traditional coverage studies only deal with static sensors and primarily focus on maximizing coverage while minimizing energy to prolong a sensor network’s lifetime.²

More recently, mobile sensor networks have become a popular research area because, with mobile sensors, it is possible to increase capabilities and reduce communication costs.³ However, most mobile sensor network studies focus on increasing a network’s lifetime,⁴ increasing channel capacity,⁵ and enhancing coverage,⁶ while our work handles trajectories and the work time of mobile sensors. Note that the mobile sink routing problem^19,20 is similar to our problem. In sensor networks, sinks or base stations aggregate data from many sensor nodes and forward the results to a server. Sink mobility enhances the connectivity of sensor networks, reduces the number of hops in data routes, and provides load balancing among sensor nodes. However, most mobile sink studies only considered energy efficiency,^21,22 network latency,²³ and reliability²⁴ when finding optimal moving paths for sinks. Another issue in sensor networks is the task allocation problem in crowdsensing. Task allocation in crowdsensing gathers sensing information from mobile sensors, such as sensors in mobile phones and vehicles.^25,26 Here, a reward function is utilized for the problem’s objective, that is, maximizing the total reward of the system while assigning tasks to users/vehicles.

In robotics, the multi-robot coverage problem, which conducts given tasks using multiple robots, is closely related to our problem. Agmon et al.²⁷ proposed a spanning tree-based method for a multi-robot coverage problem. In addition, Even et al.²⁸ presented a min-max tree-based algorithm for robots to completely cover all given tasks and reduce the total path costs. Such algorithms have been exploited to address the multi-robot exploration problem,²⁹ which is based on a global optimization strategy for balanced exploration with K-means clustering in order to assign robots to an area divided by cells. However, the algorithms assume that the initial robot locations are predefined. Min and Papanikolopoulos¹⁰ indicated that having a large number of robots is not always sufficiently fast to solve coverage problems, and attempted to determine minimum coverage time under the assumption that each robot starts from the same location.

In terms of finding a given number of paths, our problem can be considered an extension of the Traveling Salesman Problem, which has conventionally been solved using heuristic approaches.^30,31 Rosenkrantz et al.³² presented that a nearest neighbor (NN) method finding a tour provides the upper and lower bounds relative to the ratio of the obtained length to the minimal length; the upper bound is half of $1 + \log (n)$ where n is the number of nodes. Since our proposed algorithm finds initial tasks to minimize MPC, we evaluated the effectiveness of our initial task selection method. In the “Experimental results” section, we compare the MPC acquired by the proposed algorithm with that of the k-nearest neighbor (kNN) approach, which is a simple greedy algorithm that selects the nearest tasks from a set of tasks.

Proposed algorithm

The proposed algorithm uses all-pairs shortest paths. Among the shortest paths, we select an initial set of paths and combine them to cover all given tasks. The all-pairs shortest-path algorithm provides optimal paths from each node to all available nodes. Rather than connecting between nodes, we employ a methodology to combine the shortest paths. The proposed algorithm efficiently selects an initial set of shortest paths while avoiding overlapped tasks and maintaining the current MPC. For complete coverage, we combine possible shortest paths with the initial path selections.

Let $Δ = {δ_{1}, \dots, δ_{| Δ |}}$ be the set of all-pairs shortest paths in a given environment represented as a graph $G (P, E)$ . Here, $δ_{s}$ denotes the sth shortest path, and each path includes at least two tasks. In addition, $δ_{i, j}^{(s)}$ and $cost (δ_{i, j}^{(s)})$ denote the shortest path from $p_{i}$ to $p_{j}$ in the sth path and its path cost, respectively. For $p_{i} \in P$ for $\forall i = 1, \dots, | P |$ , there are at most $| P | - 1$ shortest paths, that is, $δ_{i, j}^{(s)}$ for $\forall j (\neq i) = 1, \dots, | P |$ . The proposed algorithm supports both directed and undirected graphs $G$ , $| Δ | = | P | (| P | - 1)$ if $G$ is fully connected. We utilize the set of shortest paths $Δ$ as a building block to construct the set of mobile sensor paths $Π$ because the proposed algorithm selects and combines shortest paths in $Δ$ to generate a moving sensor’s path.

Our motivation for the use of all-pairs shortest paths is as follows: (1) a shortest-path algorithm is well-studied and provides optimal paths from one node to another with minimum cost and (2) if $δ_{u, x}$ and $δ_{x, v}$ are the shortest paths from u to x and from x to v, respectively, for $u, v, x \in P$ , $δ_{u, x} + δ_{x, v}$ should be the shortest path from u to v including x according to triangle inequality. In the proposed algorithm, we address the following conflicting issues. (1) (Incompleteness) To minimize MPC, if we simply select a path $δ_{s}$ with minimum cost $cost (δ_{s})$ from the set of shortest paths $Δ$ , then the set of selected paths may not cover all tasks. (2) (Non-optimal) To cover all tasks, if we simply select a path that covers more tasks, it may not always be possible to reduce the maximum cost by selecting multiple paths with lower cost whose coverage includes the same tasks.

Our kTCP with the minimum MPC algorithm is given in Algorithm 1. For inputs, the algorithm only takes a graph $G$ comprising a set of tasks $P$ , their weighted edges $E$ , and the number of sensors $k$ . The sensors’ initial tasks and their corresponding paths are the outputs. First, the algorithm finds all-pairs shortest paths (step 2), and then selects initial paths from the shortest paths in increasing order in terms of path cost only if the new initial path is largely dissimilar to the previously selected initial paths (step 3). Then, to cover all tasks, the algorithm positions the shortest paths at the end of the selected initial paths that do not have MPC (step 5). Finally, the algorithm balances cost among the sensor paths by moving tasks from the maximum cost path to lower cost paths (step 6). The algorithm also handles special cases, for example, a single task for a sensor (step 1), unassigned sensors (step 4), and duplicate visits (step 7).

Algorithm 1. kTCP with minimized MPC algorithm.
Input: a set of graph G and k sensors Output: the set of paths ( $π_{l}$ ) satisfying $\cup_{l = 1}^{k} Γ (π_{l}) = P$ with a set of distinct start tasks. 1. If $K \geq \| P \|$ , return $π_{i} = i$ for $\forall i = 1, \dots, \| P \|$ : assign a sensor to each task. 2. Find all-pairs shortest paths for each $p_{i}$ : $Δ = {δ_{1}, \dots, δ_{\| Δ \|}}$ , and sort $Δ$ in increasing order of path cost $cost (δ_{s})$ . 3. $Π$ = Select-Initial-Paths ( $Δ$ ): construct an initial set of paths $Π$ by sequentially choosing $δ_{j}$ from the ordered shortest paths $Δ$ if $δ_{j}$ satisfies the dissimilarity condition (i.e. $δ_{j}$ is sufficiently different from the tasks already covered by $Π$ ). Let the number of paths in $Π$ , that is, $\| Π \|$ , be $m$ ( $m \leq k$ ). 4. If $m < k$ (i.e. the number of initial paths $m$ does not reach the given number of sensors $k$ ), Assign-Remain-Sensors ( $Π, m, P_{uncovered}$ ): until $\| Π \|$ (i.e. $m$ ) becomes $k$ , add new paths to $Π$ from tasks in $P_{uncovered}$ , where $P_{uncovered}$ is a set of tasks not covered by $π_{i}$ in $Π$ . 5. If $\| P_{uncovered} \| \neq 0$ , Extension-of-Paths ( $Π, Δ, P_{uncovered}$ ): until $\| P_{uncovered} \|$ becomes $0$ , combine a path $π_{i}$ in the set of paths $Π$ with a shortest path $δ_{j}$ in $Δ$ if $δ_{j}$ connects an end point of $π_{i}$ to $p_{j}$ in $P_{uncovered}$ . 6. Balancing-Paths ( $Π$ ): to minimize the current MPC, rearrange tasks from the maximum cost path to smaller cost paths. 7. Eliminate-Multi-tasks ( $Π$ ): count the number of tasks in all paths and eliminate start or destination tasks in a path if they have multiple visits.

Algorithm 1. kTCP with minimized MPC algorithm.

Input: a set of graph G and k sensors
Output: the set of paths (

π_{l}

) satisfying

\cup_{l = 1}^{k} Γ (π_{l}) = P

with a set of distinct start tasks.
1. If

K \geq | P |

, return

π_{i} = i

for

\forall i = 1, \dots, | P |

: assign a sensor to each task.
2. Find all-pairs shortest paths for each

p_{i}

Δ = {δ_{1}, \dots, δ_{| Δ |}}

, and sort

Δ

in increasing order of path cost

cost (δ_{s})

.
3.

Π

= Select-Initial-Paths (

Δ

): construct an initial set of paths

Π

by sequentially choosing

δ_{j}

from the ordered shortest paths

Δ

δ_{j}

satisfies the dissimilarity condition (i.e.

δ_{j}

is sufficiently different from the tasks already covered by

Π

). Let the number of paths in

Π

, that is,

| Π |

, be

m

(

m \leq k

).
4. If

m < k

(i.e. the number of initial paths

m

does not reach the given number of sensors

k

),
Assign-Remain-Sensors (

Π, m, P_{uncovered}

): until

| Π |

(i.e.

m

) becomes

k

, add new paths to

Π

from tasks in

P_{uncovered}

, where

P_{uncovered}

is a set of tasks not covered by

π_{i}

Π

.
5. If

| P_{uncovered} | \neq 0

, Extension-of-Paths (

Π, Δ, P_{uncovered}

): until

| P_{uncovered} |

becomes

0

, combine a path

π_{i}

in the set of paths

Π

with a shortest path

δ_{j}

Δ

δ_{j}

connects an end point of

π_{i}

p_{j}

P_{uncovered}

.
6. Balancing-Paths (

Π

): to minimize the current MPC, rearrange tasks from the maximum cost path to smaller cost paths.
7. Eliminate-Multi-tasks (

Π

): count the number of tasks in all paths and eliminate start or destination tasks in a path if they have multiple visits.

Algorithm 1 is described in detail as follows:

Each sensor is assigned to each task if the number of sensors $K$ is greater than or equal to the number of tasks $| P |$ . It then returns the set of paths.

All-pairs shortest paths ( $Δ = {δ_{1}, \dots, δ_{| Δ |}}$ ): the all-pairs shortest paths guarantee optimized cost between any nodes in a graph. We apply Dijkstra’s algorithm³³ repeatedly to find the all-pairs shortest paths from any start nodes to all other nodes (excluding the start node). For a non-negative weighted graph, the computational complexity of the repeated Dijkstra’s algorithm is $O (| P | \cdot | E | \log | P |)$ . Note that the proposed algorithm is not restricted to a specific all-pairs shortest-path algorithm.

Select-Initial-Paths ( $Δ$ ): this constructs an initial set of paths in which the number of paths is less than or equal to the given number of sensors $k$ . The main idea of this step is to select paths from $Δ$ that have lower path cost and greater coverage. To select a low-cost path, we sequentially select a path from $Δ$ , which is sorted in increasing order of path cost $cost (δ_{s})$ , as a candidate. For greater coverage, we select a candidate path as a new member of $Π$ only when the tasks covered by the candidate are significantly dissimilar (i.e. the tasks are unique) from tasks already covered by all paths in the current $Π$ . The dissimilarity of each path should reveal how many distinct nodes are present in the set of selected paths. To measure dissimilarity, we utilize the Jaccard distance,³⁴ which is the ratio of the intersection to the union of two sets. We formally define this measure as follows

d_{Jac} (δ_{s}, Π) = \frac{1}{m} \sum_{j = 1}^{m} (1 - \frac{| Γ (δ_{s}) \cap Γ (π_{j}) |}{| Γ (δ_{s}) \cup Γ (π_{j}) |})

(2)

where $m = | Π |$ . This is the average Jaccard distance of the candidate path $δ_{s}$ in terms of all paths $π_{j}$ in $Π$ . According to the predefined threshold, we accept path $δ_{s}$ in $Π$ as a new path only when each value acquired from equation (2) exceeds a threshold. The value of $d_{Jac} (δ_{s}, Π)$ is between $0$ and $1$ . If we set the threshold to $1$ , we accept a path in $Δ$ as an initial path only when all tasks in the path are not present in $Π$ .

Assign-Remain-Sensors ( $Π, m, P_{uncovered}$ ): if there is an insufficient number of unique paths in $Π$ , there may exist a case where $m < k$ after Select-Initial-Paths ( $Δ$ ) is performed. When $m < k$ , we consider two cases, that is, some tasks are not covered yet or all tasks are fully covered by only $m$ paths. For either case, this step attempts $| Π |$ to be exactly $k$ (i.e. assign all sensors to some tasks). For the former case, we generate new paths in $Π$ with tasks in $P_{uncovered}$ , where $P_{uncovered}$ is a set of tasks that are not covered by $π_{j}$ in $Π$ . For the latter case, we eliminate tasks in a path with the MPC in $Π$ and create a new path using the eliminated task in $Π$ . New paths are created with a single task by rearranging tasks from the maximum cost path until $m = k$ . This reduces the MPC and distributes the cost burden to unassigned sensors. This step is repeated until $| Π | = k$ .

Extension-of-Paths ( $Π, Δ, P_{uncovered}$ ): this step attempts to cover all tasks if uncovered tasks remain in $P_{uncovered}$ . We extend paths in $Π$ using the shortest paths in $Δ$ . Here, the main idea is to find the lowest cost path among all shortest paths between an uncovered task in $P_{uncovered}$ and the end points (i.e. start or end tasks) of paths in $Π$ . Then, the shortest path is combined with the corresponding path of moving sensors in $Π$ . In other words, uncovered tasks are connected to paths in $Π$ with the minimum cost. To prevent increasing path costs excessively, a threshold $T$ is employed to limit this extension. We select a shortest path $δ_{s}$ for extension when $δ_{s}$ satisfies the following

(a) $\min_{s} cost (δ_{j, u}^{(s)})$ for $p_{u} \in P_{uncovered}$

(b) $cost (π_{i, j}^{(r)}) + cost (δ_{j, u}^{(s)}) \leq T$

With the chosen $π_{i, j}^{(r)}$ and $δ_{j, u}^{(s)}$ where $r = 1, \dots, k$ and $p_{j}$ is simultaneously the tail of $π_{i, j}^{(r)}$ and the head of $δ_{j, u}^{(s)}$ , we combine these two paths into an extended path $π_{i, u}^{(r)}$ . This means that the potential shortest paths $δ_{s}$ in $Δ$ are extended to each available path in $Π$ , where the additional cost does not exceed threshold $T$ . This step is performed if the updated $Π$ covers all tasks; otherwise, threshold $T$ increases by a certain amount and this step is repeated until all tasks are covered.

Balancing-Paths ( $Π$ ): in the previous steps, all sensors were assigned to tasks (i.e. $m = k$ ) and all tasks were fully covered. This step balances costs among paths in $Π$ to reduce MPC. This balance is achieved by rearranging tasks from larger cost paths to smaller cost paths. A path with MPC in $Π$ is investigated if we can balance its path cost by moving the last task to another path in $Π$ .

Eliminate-Multi-nodes ( $Π$ ): finally, all paths in $Π$ are inspected and redundant tasks in the paths are eliminated. We remove a start or a destination task in a path repeatedly if it is covered in another path.

Proposition 1 addresses the result of Algorithm 1, that is, $Π$ covers all given tasks $P$ . This means that the proposed algorithm solves kTCP for a connected non-negative weighted graph which does not include isolated nodes.

Proposition 1: coverage

For $G = (P, E)$ and $k$ , if $Π = {π_{1}, \dots, π_{k}}$ is constructed by Algorithm 1, then paths in $Π$ cover all tasks in $P$ .

Proof

Let $P = {p_{1}, \dots, p_{| P |}}$ be a set of given tasks and $Δ = {δ_{1}, \dots, δ_{| Δ |}}$ be a set of all-pairs shortest paths.

For $| P | \leq k$ , all sensors should be assigned to a single task; therefore, $| π_{r} | = 1$ and $cost (π_{r}) = 0$ for all $π_{r}$ in $Π$ . Thus, it is trivial to achieve complete coverage.

For $| P | > k$ , let $Π_{initial}$ be a set of $k$ initial paths after Select-Initial-Paths ( $Δ$ ) is executed. Note that $Π_{initial}$ is a subset of all shortest paths $Δ$ .

If $\forall p_{i} \in P$ is in $Π_{initial}$ , then $Π$ covers all tasks in $P$ . If not, during Extension-of-Paths ( $Π, Δ, P_{uncovered}$ ), $Π$ can cover all $π_{i}$ in $P_{uncovered}$ because all-pairs shortest paths from each task to any task in $P$ exist, that is, there exists a path $δ_{s}$ covering the remaining tasks in $P_{uncovered}$ . Thus, $Π$ covers all tasks in $P$ .□

The coverage problem that minimizes cost for multiple sensors and simultaneously finds initial tasks is NP-hard and our algorithm is a heuristic approach. Due to the reason, instead of formal analysis, we here provide a simple case study of the approximation ratio which is represented by the MPC over optimal path cost as shown in Table 1. We assumed that tasks are uniformly distributed with a certain edge cost $e$ , and the optimal path cost is computed by $(⌜ \frac{| P |}{k} ⌝ - 1) \times e$ , where $P$ and $k$ are the number of tasks and the number of sensors, respectively. In the table, horizontal lines (5, 10, 20, and 40) are the number of mobile sensors and vertical lines (9, 16, 25, 36, 49, 64, 81, and 100) are the number of tasks. It reveals that the lower and upper bounds for optimizing performance are $1$ and $2$ . Overall, our heuristic algorithm provides affordable solutions with the upper bound for choosing an initial set from the shortest paths since it avoids overlapped tasks and maintains the current MPC.

Table 1.

Performance ratio (coverage cost over optimal performance).

	9	16	25	36	49	64	81	100
$5$	$1$	$1$	1.45	1.26	1.38	1.47	1.31	1.32
10		$1$	1.5	1.3	1.75	1.3	1.17	1.33
20			$1$	$1$	1.5	1.7	1.5	$2$
40					$1$	$1$	$1$	$2$

Experimental results

Setups

Experiments were performed to demonstrate the performance of the proposed algorithm. The experimental results indicate that the proposed algorithm fully covers all given tasks and finds search paths for mobile sensors with initial tasks that have smaller MPC than other competitive algorithms. For the weighted graph $G$ representing tasks and the traveling cost between tasks, we consider spaces with and without obstacles. For a space without obstacles (i.e. an open space), we define the width and length of the space, generate tasks in the space randomly, and then connect two randomly selected tasks with traveling cost proportional to their Euclidean distance. For a space with obstacles, we utilize the office map acquired from the Player/State robot simulator.³⁵

For comparison, we include the kNN algorithm³⁰ and the parallel path coverage (PPC) algorithm.¹⁰Table 2 briefly describes the compared algorithms. The kNN algorithm is a simple greedy method to find the minimum traveling cost from $k$ initial tasks. Here, the $k$ initial tasks should be given as inputs because the algorithm does not find initial tasks. The kNN algorithm, the minimum spanning tree-based method,²⁸ and the K-means clustering-based method²⁹ have common concepts (i.e. they begin with predefined k tasks and expand to the NNs to construct paths); thus, we only examine the results of the kNN algorithm as a representative example. Here, we execute the proposed algorithm to find initial tasks. Then, the kNN algorithm is executed using the found initial tasks. In addition, the kNN algorithm is executed with $k$ randomly selected initial tasks. We refer to the former as kNN and the latter as kNN-random.

Table 2.

Compared algorithms.

Algorithm	Description	Initial tasks	Number of sensors
kNN ³⁰	Non-parameterized classification algorithm that connects nearest neighbors from predefined initial tasks	Same as the proposed algorithm	Same as the proposed algorithm
kNN-random ³⁰	Same as the kNN algorithm	Randomly chosen initial tasks	Same as the proposed algorithm
PPC ¹⁰	Optimizes MPC starting at a single initial task	Chosen by the algorithm	Chosen by the algorithm

We include kNN in our comparisons to demonstrate that the proposed algorithm finds paths with minimized MPCs that are comparable to the results of kNN, which finds minimized MPCs for a given set of initial tasks. In addition, we include kNN-random in our comparisons to demonstrate the importance of finding proper initial tasks to minimize MPCs. Note that choosing $k$ initial tasks randomly in kNN-random may provide a reasonable solution. This point should not be neglected because uniformly distributed starting points in uniformly distributed tasks may reduce the total traveling cost. The PPC algorithm also finds paths with minimized MPCs; however, in the proposed algorithm, all sensors start with the same initial task and the number of sensors is considered relative to cost minimization. The PPC algorithm is compared in order to demonstrate how performance can be improved by extending a single initial task to multiple initial tasks. Note that MPCs in the PPC algorithm have upper bounds in TCPs.

First, the algorithms are applied to a graph (size, $130 \times 130$ ) in open space with various numbers of tasks ( $3$ to 120). This experiment is performed to compare the MPCs of each algorithm to demonstrate the efficiency and effectiveness of the proposed algorithm’s initial task selection and sensor path selection. Figure 3 compares the MPCs acquired with 5, 10, 20, and 40 sensors. The PPC algorithm does not fix the number of sensors; thus, we do not explicitly show PPC results; however, a quantitative analysis is provided in the following.

Figure 3.

MPC comparison. Each experiment is run on the same graph $G$ with different number of sensors (5, 10, 20, and 40). Red crosses, blue circles, and green triangles show the MPCs of the proposed, kNN-random, and kNN algorithm, respectively: (a) k = 5, (b) k = 10, (c) k = 20, and (d) k = 40.

Results

The experimental results demonstrate that the proposed method has acquired lower MPCs than kNN and much lower MPCs than kNN-random due to the choice of a seed set of paths depending on the dissimilarity and the shortest paths. The comparison with kNN-random shows the effect of selecting proper initial tasks relative to MPC. As seen in Figure 3, the MPCs acquired with the proposed method are 83.0%, 73.2%, 65.3%, and 34.9% of those obtained with kNN-random on average for $k = 5, 10, 20,$ and 40, respectively. These results indicate that the proposed method, which selects initial tasks in consideration of the shortest paths, reduces MPCs effectively, while kNN-random uniformly scatters initial tasks in the space to equally distribute tasks to each sensor. Figure 3 also shows that the MPCs acquired by the proposed method are less than 86.0%, 81.7%, 71.2%, and 71.5% compared to kNN for $k = 5, 10, 20,$ and 40, respectively. Note that this performance gap is not prominent; however, kNN is specialized to find optimal paths from predefined start points. In contrast, the proposed algorithm produces competitive results from scratch. In addition, the kNN-random algorithm shows fluctuation in MPCs as the number of tasks increases, while the proposed algorithm demonstrates stable changes to MPCs. This is because kNN-random randomly selects initial tasks regardless of the structure of the tasks and edges. In contrast, the proposed method selects a seed set of paths according to the order of path costs from the shortest paths. For considering the randomness of kNN-random, we use the average MPC from 15 kNN-random trials in Figure 3.

Note that the results obtained with the PPC algorithm are not shown in Figure 3 because this algorithm does not fix the number of sensors $k$ but finds minimum $k$ to avoid increasing MPCs in the given graph $G$ . This means that PPC increases the number of sensors $k$ during execution. For the graph $G$ used in Figure 3, the minimized MPCs selected by PPC are 92, 93, and 92 for 40, 80, and 120 tasks, respectively. The target MPCs are typically greater than the MPCs acquired by the proposed and kNN-based algorithms because the PPC algorithm only uses a single initial task. For a greater number of tasks, it is obvious that the PPC algorithm requires a greater number of sensors $k$ , for example, up to approximately 5, 10, 27, and 52 tasks for 5, 10, 20, and 40 sensors, respectively. Figure 4 shows drastic increase in the number of sensors while the chosen costs remain steady. Note that the results acquired by the PPC algorithm were applied to the same environments shown in Figure 3.

Figure 4.

Comparison of the number of sensors (blue circles) and MPCs (red crosses) for the PPC algorithm.

Second, we evaluate the effects of the dissimilarity threshold in the Select-Initial-Paths step (Algorithm 1) because selection of the initial task set is highly sensitive to this threshold (until now, the threshold has been set to 1.0). Here, we investigate the degree to which MPCs are influenced by this dissimilarity threshold. As a representative example to demonstrate this sensitivity, Figure 5 compares the MPCs acquired with complete dissimilarity ( $d_{Jac} \geq 1.0$ ) to complete similarity ( $d_{Jac} \geq 0$ ) in equation (2), where the number of sensors $k$ is 40. This comparison shows that considering dissimilarity is essential to finding effective initial paths in order to reduce the MPC and that a suitable threshold is highly coupled with the task distribution in the graph.

Figure 5.

Comparison of MPCs relative to the choice of dissimilarity. Blue diamonds, light-red squares, green triangles, and red crosses indicate MPCs acquired by the proposed algorithm ( $k = 40$ ) with average dissimilarities of 0, 0.5, 0.8, and $1$ .

Here, we demonstrate that the proposed algorithm can be applied to both open spaces and spaces with obstacles. For a space with obstacles, we utilize the office map acquired from the Player/State³⁵ robot simulator (Figure 6(a)). In such a space, the routes between tasks may not be straight if obstacles exist in the middle of the tasks; however, we represent all edges as straight lines with the corresponding cost (i.e. Euclidean distance) by appropriately connecting each task to a feasible route in order to move sensors (Figure 6(b)). Here, we utilize an office map with randomly generated tasks and their edges.¹⁰

Figure 6.

Randomly generated tasks and edges applied to a map from the Player/Stage³⁵ robot simulator: (a) office map with 19 randomly generated and intermediate tasks and (b) graph with 19 tasks and their edges.

For the space with obstacles, we compare the MPCs of the proposed, kNN, kNN-random, and PPC algorithms in Figure 7. Similar to the results obtained with open spaces, the proposed algorithm acquires the best MPC compared to the other algorithms. The proposed algorithm reduces the MPCs of the kNN, kNN-random, and PPC algorithms by 16.9%, 36.4%, and 34.1%, respectively.

Figure 7.

Comparison of MPCs by the proposed algorithm to the best results of PPC, kNN, and kNN-random. The proposed algorithm reduces MPCs by 16.9%, 36.4%, and 34.1% compared to kNN, kNN-random, and PPC, respectively. Each method is applied to the graph (Figure 6(b)).

Figure 8 shows the coverage results of the proposed algorithm compared to kNN because the completeness of all tasks is an important goal in a TCP. As proved in Proposition 1, the proposed algorithm completes all tasks for each case, while kNN results in coverage of 81.4%, 90.7%, 94.9%, and 99.2%. Note that the average MPCs acquired by the proposed algorithm are still less than those of kNN while maintaining 100% coverage (225.1, 145.6, 70.6, and 24.5 compared to 277.3, 151.0, 81.6, and 25.6 for $k = 5, 10, 20,$ and 40, respectively). Note that the PPC algorithm finds the number of sensors; thus, a comparison of coverage with an equal number of sensors is not valid. The PPC algorithm generally requires more sensors to cover all tasks. The coverage ratio of the PPC algorithm is 4.2%, 8.5%, 18.6%, and 40.2% if we set the number of mobile sensors to 5, 10, 20, and 40, respectively.

Figure 8.

Average completeness while covering entire tasks. The x- and y-axis represent the number of sensors and the ratio of covered tasks, respectively.

The experimental results demonstrate that the proposed method completely solves kTCP with lower MPCs than the existing methods.

Conclusion

In this article, we have presented kTCP to cover all given tasks with a given number of mobile sensors. The proposed method attempts to find an efficient set of paths, including initial tasks, in terms of minimizing the maximum cost. We expect that our research will inspire various mobile sensor applications, particularly those that deal with deploying moving sensor platforms in order to accomplish a search and rescue mission. Thus, the proposed algorithm selects a set of shortest paths with fewer duplicate tasks and extends each path with remaining tasks while covering all tasks and avoiding cost increases. We run our algorithm on various numbers of tasks in both an open space and an obstacle space, and showed the advantages of finding start locations from scratch as well as reducing coverage cost due to dissimilarity of the shortest paths. The experimental results demonstrate that the proposed algorithm provides efficient solutions compared to the well-known kNN and PPC algorithms in terms of coverage and MPC. In future, we will focus on timely changes and dynamics in tasks for kTCP.

Footnotes

Handling Editor: Pascal Lorenz

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This material is based on the work supported by the BK21 plus program through the National Research Foundation (NRF) funded by the Ministry of Education of Korea. Hyo-Sang Lim was supported by the Institute for Information & Communications Technology Promotion (IITP) grant funded by the Korea government (MSIT; no. R7117-17-0214, Development of an Intelligent Sampling and Filtering Techniques for Purifying Data Streams).

References

Aslan

Korpeoglu

Ulusoy

Ö.

A framework for use of wireless sensor networks in forest fire detection and monitoring. Comput Environ Urban 2012; 36(6): 614–625.

Batalin

Sukhatme

GS.

The design and analysis of an efficient local algorithm for coverage and exploration based on sensor network deployment. IEEE T Robot 2007; 23: 661–675.

Rezazadeh

Moradi

Ismail

Mobile wireless sensor networks overview. Int J Comput Commun Netw 2012; 2(1): 17–22.

Gandham

Dawande

Prakash

et al . Energy efficient schemes for wireless sensor networks with multiple mobile base stations. In: IEEE global telecommunications conference (GLOBECOM), San Francisco, CA, 1–5 December 2003, vol. 1, pp.377–381. New York: IEEE.

Kansal

Somasundara

Jea

et al . Intelligent fluid infrastructure for embedded networks. In: Proceedings of the 2nd international conference on mobile systems, applications, and services, Boston, MA, 6–9 June 2004, pp.111–124. New York: ACM.

Wang

Cao

La Porta

et al . Sensor relocation in mobile sensor networks. In: Proceedings of the 24th annual joint conference of the IEEE computer and communications societies (INFOCOM), Miami, FL, 13–17 March 2005, vol. 4, pp.2302–2312. New York: IEEE.

Tuna

Gungor

Gulez

An autonomous wireless sensor network deployment system using mobile robots for human existence detection in case of disasters. Ad Hoc Netw 2014; 13: 54–68.

Heo

Varshney

PK.

Energy-efficient deployment of intelligent mobile sensor networks. IEEE T Syst Man Cy A 2005; 35: 78–92.

Martínez

Bullo

Optimal sensor placement and motion coordination for target tracking. Automatica 2006; 42: 661–668.

10.

Min

Papanikolopoulos

The multi-robot coverage problem for optimal coordinated search with an unknown number of robots. In: IEEE international conference on robotics and automation, Shanghai, China, 9–13 May 2011, pp.2866–2871. New York: IEEE.

11.

Liang

Liu

Kui

A survey of coverage problems in wireless sensor networks. Sensor Transducer 2014; 163(1): 240.

12.

Huang

C-F

Tseng

Y-C.

The coverage problem in a wireless sensor network. Mobile Netw Appl 2005; 10(4): 519–528.

13.

Wang

Xing

Zhang

et al . Integrated coverage and connectivity configuration in wireless sensor networks. In: International conference on embedded networked sensor systems, Los Angeles, CA, 5–7 November 2003, pp.28–39. New York: ACM.

14.

Zhou

R Das

Gupta

Variable radii connected sensor cover in sensor networks. ACM T Sens Netw 2009; 5(1): 1–36.

15.

Cardei

Improving network lifetime using sensors with adjustable sensing ranges. Int J Sens Netw 2006; 1(1–2): 41–49.

16.

Zhao

Gurusamy

Lifetime maximization for connected target coverage in wireless sensor networks. IEEE ACM T Network 2008; 16(6): 1378–1391.

17.

Sun

Zheng

Research on target locating algorithms in wireless sensor networks. Comput Eng Appl 2004; 40(3): 132–134.

18.

Ahmed

Kanhere

Jha

The holes problem in wireless sensor networks: a survey. ACM SIGMOBILE Mob Comput Commun Rev 2005; 9(2): 4–18.

19.

Tunca

Isik

Donmez

et al . Distributed mobile sink routing for wireless sensor networks: a survey. IEEE Commun Surv Tut 2014; 16(2): 877–897.

20.

Ren

et al . The evolution of sink mobility management in wireless sensor networks: a survey. IEEE Commun Surv Tut 2016; 18(1): 507–524.

21.

Yuan

X-X

Zhang

R-H.

An energy-efficient mobile sink routing algorithm for wireless sensor networks. In: International conference on wireless communications, networking and mobile computing (WiCOM), Wuhan, China, 23–25 September 2011, pp.1–4. New York: IEEE.

22.

Chen

Salim

Matsumoto

Modeling the energy performance of event-driven wireless sensor network by using static sink and mobile sink. Sensors 2010; 10(12): 10876–10895.

23.

Wang

et al . A geographic routing algorithm in duty-cycled sensor networks with mobile sinks. In: International conference on mobile ad-hoc and sensor networks (MSN), Beijing, China, 16–18 December 2011, pp.343–344. New York: IEEE.

24.

Karenos

Kalogeraki

Traffic management in sensor networks with a mobile sink. IEEE T Parall Distr 2010; 21(10): 1515–1530.

25.

Shin

D-H

Zhang

et al . Near-optimal allocation algorithms for location-dependent tasks in crowdsensing. IEEE T Veh Technol 2016; 66: 3392–3405.

26.

Rui

Zhang

Huang

et al . A location-dependent task assignment mechanism in vehicular crowdsensing. Int J Distrib Sens N 2016; 12(9): 1–9.

27.

Agmon

Hazon

Kaminka

GA.

Constructing spanning trees for efficient multi-robot coverage. In: IEEE/RSJ international conference on intelligent robots and systems, Orlando, FL, 15–19 May 2006, pp.1698–1703. New York: IEEE.

28.

Even

Garg

Kónemann

et al . Min-max tree covers of graphs. Oper Res Lett 2004; 32: 309–315.

29.

Puig

Garcia

A new global optimization strategy for coordinated multi-robot exploration: development and comparative evaluation. Robot Auton Syst 2011; 59: 635–653.

30.

Arora

Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J ACM 1998; 45(5): 753–782.

31.

Bektas

The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega 2006; 34: 209–219.

32.

Rosenkrantz

Stearns

Lewis II

. An analysis of several heuristics for the traveling salesman problem. SIAM J Comput 1977; 6(3): 563–581.

33.

Dijkstra

EW.

A note on two problems in connexion with graphs. Numer Math 1959; 1(1): 269–271.

34.

Strehl

Ghosh

Mooney

Impact of similarity measures on web-page clustering. In: Workshop of artificial intelligence for web search, Austin, TX, 30 July 2000, pp.58–64. Association for the Advancement of Artificial Intelligence (AAAI).

35.

Player/Stage. The Player project, 2010, http://playerstage.sourceforge.net/