Keywords

1 Introduction

Wireless Sensor Networks (WSNs) have been widely used for data collection and situation monitoring in various applications. The raw data collected by sensors can then be forwarded through a number of relay nodes to a remote base station, denoted as the sink node, [5, 6]. In a WSN, sensor nodes with limited energy are often randomly deployed in massive quantities, and each node may act both as a data collector and a traffic relay, as shown in existing research [1].

Agent-based technology has attracted growing attention to improve energy efficiency, scalability, and reliability of a WSN [2–4, 7, 21]. In an agent-based WSN, the main technical challenges include data fusion, energy efficiency, as well as energy balancing. For example, Lin et al. [8] leveraged the agent-based technology to balance energy consumption in data collection process of WSNs.

A critical problem of an agent-based WSN is how to design the itinerary through the WSN for the mobile agent to collect data. Existing approaches for agent itinerary in WSNs can be classified into two categories: (i) single agent itinerary planning based on clustering [9–12], and (ii) multi-agent itinerary planning. For example, Xu et al. [9] investigated static, dynamic, and predictive dynamic schemes to solve the target tracking problem in a WSN. Nonetheless, their work assumes that there is only one target node in the field, and the itinerary is for only one agent. In reality, using a single agent is not practical because of large delay, unbalanced load, and insecurity with large accumulated size [14, 15]. So, multi-agent based WSN and the problem of multi-agent itinerary planning have attracted growing attention [13, 14]. Chen et al. [14] proposed a source-grouping scheme and an iterative algorithm for multi-agent based itinerary planning. They partition source nodes into several sets and use the least number of agents while achieving the required coverage of source nodes. Nonetheless, finding an optimal number of agents is a NP-hard problem and their algorithm is heuristic. Cai et al. [15] applied the genetic algorithm for multiple mobile agents traversing a WSN. Nonetheless, their proposed scheme is complicated and hard to be realized in reality.

Clustering is another important strategy to solve the data fusion and collection problem in WSNs and has been widely adopted. In the typical clustering algorithm called LEACH (Low Energy Adaptive Clustering Hierarchy) [16], the high-energy cluster-head positions are randomly rotated so that the energy consumption of sensors can be balanced. But LEACH assumes a homogeneous distribution of sensor nodes in the given area, which may not be realistic. We will compare our algorithm with clustering based algorithms [21–24].

Existing research efforts on multi-agent routing mainly focus on how to select source nodes to generate itineraries other than how to compute routes. Our work fills this gap. The rest of this paper is organized as follows: In Sect. 2, we present the problem. In Sect. 3, we present the agent routing approach considering energy balancing. In Sect. 4, we present performance evaluation results. Finally, we conclude the paper in Sect. 5.

2 Mobile-Agent Based Wireless Sensor Networks

2.1 Problem Definition

Given a WSN, we utilize mobile agent techniques to accomplish data collection and fusion with less energy consumption and longer life-cycle. A sink node (e.g., base station) is responsible for gathering data from sensor nodes. The objective of our research is to find multiple disjoint paths which cover all sensor nodes in the WSN. The disjoint paths will be assigned to mobile agents.

Our problem is defined as follows: Given an undirected connected graph G = <V, E>, where V is the set of nodes and E is the set of edges, the problem is to find k disjoint paths in G to cover all nodes in V, where every edge in these paths can be found in E. It is NP-hard to find optimal number of disjoint paths as we mentioned in Sect. 1. We focus on developing efficient heuristic and polynomial time algorithms to make agents work effectively in a WSN and produce near-optimal itineraries.

2.2 Multi-Agent Based WSN

We propose a multi-agent based data collection scheme. As shown in Fig. 1, there are three parts: remote user, sink node, sensor node in our scheme. Remote user assigns tasks to sink node. All sensor nodes have operating environment installed for mobile agent. When sink node receives a task from remote user, sink node traversals network topology to generate a spanning tree, then assigns every path to a mobile agent. When a mobile agent moves along its own path to a sensor node, it will do data processing and carry the raw data to the next node. All agents will perform tasks in parallel until they visit all nodes of their paths. Sink node will manipulate data from every path and send back the final results to remote user. Figure 2 shows the detailed workflow.

Fig. 1.
figure 1

Multi mobile agent data collection model

Full size image
Fig. 2.
figure 2

Task flow model

Full size image

3 Novel Algorithm for Multi-Agent Itinerary

In this section, we present a novel DFS based Multi-Agent Itinerary Planning (DMAIP) algorithm in WSNs. Particularly, we first present the DMAIP algorithm that decreases the communication distance between sensor nodes in the agent’s migration path. We then present the enhanced DMAIP algorithm, denoted as, DMAIP-E. DMAIP-E changes the process of traversing the network, considering distance between sink node and sensors when generating disjoint paths.

3.1 DMAIP Algorithm

We firstly build a network topology graph from WSN, then generate a spanning tree of the connected graph in the order of increasing weight and finally traverse the spanning tree recursively to find disjoint paths of all the subtrees.

Algorithm 1 introduces how we build the network topology G. We assume that the wireless sensor nodes can locate themselves. They will send position coordinates to the sink node. Accordingly, the sink node will collect position data and compute distances between all the pairs of nodes. If the distance is not larger than the radius, we leave it as what it is. Otherwise, we will mark it inaccessible explicitly by value −1.

Algorithm 2 generates a spanning tree of the connected graph G. Basically, we traverse weighted adjacent matrix M (the graph) by DFS and generate a spanning tree.

In Algorithm 3, we traverse the spanning tree recursively to find disjoint paths of all the subtrees.

3.2 DMAIP-E Algorithm

If the sensor node is far away from the sink node, energy consumption increases and this will reduce the life time of the WSN. Based on DMAIP, we propose an algorithm called DMAIP-E that considers the distance between the sink node and all sensor nodes, as shown in Algorithm 4. We first build network topology graph according to Algorithm 1 of DMAIP to get the distance matrix \( {\text{M}} = [{\text{d}}_{{{\text{u}},{\text{v}}}} ]_{\text{n*n}} \). Secondly, we generate multiple paths for agents.

In Algorithm 4, we start from the nearest node A to the sink node, find the next node B that meets these conditions

$$ {\text{d}}_{{{\text{A}},{\text{sink}}}} < {\text{d}}_{{{\text{B}},{\text{sink}}}} \;{\text{and }}\;{\text{d}}_{{{\text{A}},{\text{B}}}} < {\text{d}}_{{{\text{B}},{\text{sink}}}} $$
(2)

We illustrate the process of choosing appropriate node B in Fig. 3. Node B must be satisfied with Formula (2). So nodes 1, 2 and 3 are being considered. Besides, we require the nearest node to node A. Therefore, node 2 is the node B. Assume node B as the next A and find the next node B. Once there is no more node B to be found, it will form a path from the first node A to the last node B. Then go back to the sink node and repeat the process above. It will stop when all nodes are included in all generated paths.

Fig. 3.
figure 3

A process of choosing appropriate node B

Full size image

The sink node will dispatch an agent to the farthest node of every disjoint path generated above. When an agent finished its task, it will return from the other end of its path to the sink node, and the sink node will manipulate all data from all paths. In fact, we let the sink node dispatch agents to the outermost location of the path to decrease the distance that the agent loaded with data migrates.

The time complexity of DMAIP algorithm is \( O(n^{3} ) \). The time complexity of DMAIP-E algorithm is \( O(n^{2} ) \).

4 Performance Evaluation

We implemented the DMAIP and DMAIP-E schemes in the Qualnet environment [20], and compared them with LEACH based algorithms [16, 22, 23]. At last, we present the experimental results of comparing DMAIP, DMAIP-E and LEACH.

4.1 Methodology

We deployed sensor nodes randomly in an area of 200 m × 200 m. Each node was deployed at a fixed position. Sink node is located at (100, 100). Table 1 gives the parameter settings.

Table 1. Simulation experimental parameter settings
Full size table

We take the following assumptions: (i) wireless sensor network is of large-scale and nodes are distributed randomly, (ii) the initial energy batteries of all the sensor nodes are the same, (iii) The data packet is of the same size, and (iv) all sensor nodes stay in the fixed position.

4.2 Results

We evaluate the performance of our proposed schemes in terms of energy efficiency and life cycle. In the following, we first compare three related algorithms and then show their performance results.

  • Results Generated by three Algorithms

All LEACH based algorithms use a typically clustering mechanism for data collection, while our proposed DMAIP and DMAIP-E use multi-path methods. The WSN has 100 sensor nodes. In our experiments, the three algorithms run in the same environment. Initially, all sensor nodes are deployed as shown in Figs. 4, 5 and 6.

Fig. 4.
figure 4

The branches generated by LEACH

Full size image
Fig. 5.
figure 5

The branches generated by DMAIP

Full size image
Fig. 6.
figure 6

The branches generated by DMAIP-E

Full size image

Itineraries of LEACH Algorithm:

In LEACH algorithm, we choose 13 sensor nodes as cluster heads from 100 ones. Ordinary nodes can only communicate with cluster heads, and only cluster heads can communicate with sink nodes. As shown in Fig. 4, according to LEACH strategy, ordinary nodes will choose the nearest cluster head as theirs because of the randomness of deployed sensor nodes and cluster head nodes. Therefore, each cluster head node manages unbalanced number of ordinary nodes within its domain. A cluster head may communicates with many cluster members, and may have long communication distance with the sink node. This phenomenon leads to fast death of some cluster head due to the fast energy consumption. With the increasing number of the sensor nodes in large-scale WSNs, the distance between a cluster head, its cluster member nodes and sink node will be larger and consume much more energy.

Itineraries of DMAIP and DMAIP-E Algorithms:

Figure 5 illustrates the results for DMAIP. It has 4 paths and the last node along each path consumes the most energy. For example, in Fig. 5, the 70th node, the last node of a path, is far from the sink node and dies fast because of the fast energy consumption. Figure 6 shows the results for DMAIP-E algorithm. Recall that DMAIP-E is the enhanced version of the DMAIP algorithm and considers not only the distance between nodes, but also the distance between the last node of each path and sink node. The sink node dispatches mobile agents to the farther end of each path, and the agent returns to the other end of the path. This reduces the amount of energy consumption to a certain degree and extends the life cycle of the wireless sensor network.

  • Performance Results

The following three performance metrics are considered in our simulation: life cycle, energy consumption, impact of the number of nodes. Table 2 gives the evaluation metrics.

Table 2. Performance metrics
Full size table

Life cycle:

From Fig. 7, we can see that with different number of nodes, the life cycle of DMAIP -E is much longer than that of DMAIP, and the life time of DMAIP is a little longer than that of LEACH algorithm as the communication distance of DMAIP-E is the smallest, while the distance of LEACH is mostly very large.

Fig. 7.
figure 7

Life cycle with different number of nodes

Full size image

The Number of Residual Nodes:

Figure 8 illustrates results that present the number of remaining nodes versus the number of rounds. As we can see, as the number of rounds increases, some sensor nodes will die. The number of rounds for LEACH, DMAIP and DMAIP-E to have dead nodes are 250, 280 and 650, respectively. DMAIP-E has the largest number of rounds, i.e., the longest life cycle, more than twice rounds of the other two algorithms. The reason why nodes in DMAIP die very early is that it is very far from the end node of some paths to the sink node and therefore transmitting data from the end node to the sink node will consume energy heavily. In addition, all nodes for LEACH die in about 600th round, while for DMAIP and DMAIP-E, nodes will not be all dead until about 1500th round. This is because DMAIP and DMAIP-E adopt a mobile agent model that saves and balances the energy of sensor nodes. Since DMAIP-E outperforms the others.

Fig. 8.
figure 8

Changes of residual nodes’ number with rounds

Full size image

Energy consumption:

Energy consumption is another important performance metric for WSNs [17–19]. This experiment was performed in a network with 100 nodes and the results are shown in Fig. 9. As we can see, the energy consumption of DMAIP and DMAIP -E algorithm is almost the same while the energy consumption of LEACH is not stable. This is because DMAIP and DMAIP-E collect data according to preset paths while LEACH chooses cluster head randomly and changes it every few rounds. Therefore, energy consumption of LEACH varies with rounds. After every round, DMAIP-E algorithm consumes the least energy while LEACH uses the most.

Fig. 9.
figure 9

Changes of total energy of nodes with rounds

Full size image

5 Conclusion

The itinerary planning problem is a key issue in distributed WSN. In this paper, we present a multi-agent based paradigm for data collecting in WSN. Since the optimal multi-agent itinerary generation problem is NP-hard, we propose an approximate algorithm called DMAIP-E based on the global topology graph. Our simulation results show that DMAIP-E is appropriate for large-scale WSN and has better performance than the existing clustering based algorithms in terms of life cycle and energy consumption.