1 Introduction

Mobile agent (MA) systems employ migrating codes to facilitate flexible application re-tasking, local processing, and collaborative signal and information processing. This provides extra flexibility, as well as new capabilities to wireless sensor networks (WSNs) in contrast to the conventional WSN operations based on the client–server computing model [1–9]. By changing the program code of MAs, different data processing techniques/methods can be carried out at each source node. Otherwise, source nodes should store the program code of each possible application, resulting in increased memory demands in sensors. Recent advances show the efficiency of MA-based data collection and aggregation in WSNs with intrinsically distributed and collaborative features [10–14].

MA design in WSNs can be decomposed into a few components [15] (1) an overall framework, (2) itinerary planning, (3) a middleware system design, and (4) agent cooperation. Among these components, itinerary planning determines the order of source nodes to be visited during the MA migration, which has a significant impact on the performance of MA-based WSNs. While it is crucial to find out an optimal itinerary for a MA to visit the given set of the source nodes, this has been identified as a NP-hard problem [13]. Furthermore, using only a single MA may also bring some shortcomings, e.g., increased task completion latency and unbalanced energy consumption at the nodes. In order to alleviate this issue, multiple agents can be utilized, which gives rise to a new challenging issue of multi-agent itinerary planning (MIP). As a simple but representative MIP solution, a heuristic algorithm named simple source grouping based MIP (denote by SG-MIP in this paper) is proposed. In SG-MIP, the determination of the number of MAs and source node grouping is dependent on the distribution of source nodes and the network deployment. However, the optimality of the solution cannot be guaranteed. Given the scenario presented in Sect. 4, Fig. 1 shows the OPNET simulation results of SG-MIP’s itinerary planning. As an example, the position of node \(1\) is selected as the first visiting central location (VCL). Given VCL as the center of disk with a certain radius, the source nodes along the first itinerary can be identified. As shown in Fig. 1, the dashed line represents the first itinerary.

Fig. 1
figure 1

Illustration of SG-MIP Algorithm

Full size image

However, the source node (i.e., node \(2\)) close to the network edge at right side is not included in the itinerary. Due to the failure of setting an efficient radius of the disk, the isolated source finally consumes an individual MA based on SG-MIP algorithm, which mitigates the benefit obtained by other MAs. Such an adverse outcome happens mainly because of the following two reasons:

  • In SG-MIP, the source-grouping algorithm identifies the source nodes within the circular area centered at the VCL with a certain radius. Then, the source nodes will be assigned to the current agent. However, SG-MIP only exhibits high efficiency when source nodes are distributed in clusters. According to this assumption, a number of closely distributed source nodes are triggered at the proximity of the position where an individual event occurs. Such a position is analogous to the VCL. However, this assumption poses much limitation on the range of applications which can be supported by the multi-agent architecture. This assumption of clustering in event detection can be relaxed by considering a flat sensor network architecture in terms of event detections, which may be suitable for a wide range of sensor applications.

  • SG-MIP likely causes overlapping of itineraries, which leads to interference among multiple data flows along different itineraries. As an extreme example, let us assume source nodes are distributed along a straight line starting from the sink node. Then, an itinerary reaching farther sources will cover a large part of a relatively shorter itinerary.

In order to address the issues existing in SG-MIP, this paper proposes an improved algorithm, entitled by directional source grouping based MIP (DSG-MIP), which partitions a directional sector zone where the source nodes are included in an itinerary. The scale of an itinerary is controlled by the angle of the directional sector zone in such a way that near-optimal routes for MAs can be obtained by selecting efficient angle adaptively. Simulation results confirm the effectiveness of the proposed algorithm as well as its performance gain over alternative approaches.

The remainder of the paper is organized as follows. Related work is introduced in Sect. 2. We describe the novel directional source-grouping-based multi-agent itinerary planning scheme in Sect. 3.1. Simulation experiments are performed in Sect. 4. Finally, Sect. 5 concludes this paper.

2 Related works

2.1 Single-agent itinerary planning

Single-agent itinerary planning (SIP) determines the order of nodes to be visited by a single agent during agent migration, which has a significant impact on energy efficiency of MA systems. Though SIP is critical to the network performance, it has been shown that finding an optimal itinerary is NP-hard and still an open area of research. Therefore, heuristic SIP algorithms [10–12] and genetic algorithms [13] are generally used to compute itineraries with a sub-optimal performance. Though our previously introduced itinerary energy minimum for first-source-selection (IEMF) and itinerary energy minimum algorithm (IEMA) approaches [12] exhibit higher performance in terms of energy efficiency and delay compared to the existing solutions, the limitation of utilizing a single agent to perform the whole task makes the algorithm unscalable in applications where a large number of source nodes need to be visited. Typically, SIP algorithms exhibit high efficiency when the source nodes are distributed geographically close to each other, and the number of source nodes is not large.

For large scale WSNs, in which many nodes need to be visited, single-agent data dissemination exhibits the following pitfalls:

  1. 1.

    Large delays Extensive delays are incurred when a single agent needs to visit hundreds of sensor nodes.

  2. 2.

    Unbalanced load There are two kinds of problems with unbalanced power consumption while using a single agent. First, from the perspective of the whole WSN, all the traffic is put on a single flow. Therefore, sensor nodes in the agent itinerary will deplete battery energy more quickly than other nodes. Secondly, from the perspective of the itinerary, the agent size increases continuously while it visits more source nodes, and so the agent propagation by wireless transmissions will consume more energy in its itinerary back to the sink node.

  3. 3.

    Reduced reliability The increasing amount of data accumulated by the agent during its migration task increases its chances of being lost due to noise and interference in the wireless medium. Thus, the longer the itinerary, the higher risk that the agent migration becomes unreliable.

2.2 Multi-agent itinerary planning

In [16], we state our assumptions and define a generic MIP algorithm as follows:

  • primary itinerary design algorithms are executed at the sink, which has relatively plenty of resources in terms of energy and computation.

  • the sink node knows the geographic information of all the source nodes. Note that in our algorithm, only source locations are needed, while the other algorithms [10, 13] need all of the nodes’ geographical positions.

In fact, the above assumptions are common in most of the solutions presented in [10, 12, 13] for the SIP problem. The previous SIP algorithms assume that the set of source nodes to that the agent should visit is predetermined. In contrast, our MIP algorithm aims to dynamically group source nodes that will be visited by different mobile agents. The proposed MIP algorithm can be deemed as an iterative version of a SIP solution, which can be divided into four parts:

  • VCL selection for each agent It is a challenging NP-hard problem to find the least number of agents that cover all the source nodes. Strategically, an agent’s VCL is selected to be the center of an area with a high density of source nodes.

  • Determining the source visiting set In order to determine the source visiting set of a particular agent, we first isolate the visiting area, which is typically a circle of a certain radius centered at the corresponding VCL. All of the source nodes in the disk will be included in the visiting list of the agent.

  • Determining a source-visiting sequence This is the itinerary plan for the specific agent. In this step, the problem is simplified into a SIP problem, whereby existing SIP solutions, such as LCF [10], GCF [10], MADD [11], IEMF and IEMA [12] , etc. can be applied,

  • Algorithm iteration If there are uncovered source nodes, the next VCL will be calculated based on the remaining set of source nodes. The previous steps are repeated until all the source nodes have been assigned to some MAs.

3 Directional source-grouping for multi-agent itinerary planning

In this section, we present an enhanced version of SG-MIP named DSG-MIP, which operates centrally in the processing element (PE) located at the sink node, and statically determines the number of MAs that should be used, as well as the itineraries these MAs should follow. Compared to the previous work, the main contribution of DSG-MIP is the introduction of a directional source grouping algorithm, the main idea of which is to partition the network area into sector zones whose centers are the immediate neighbors of the sink node. The rationale is that the route of each MA’s round-trip naturally converges at the sink node while gradually expanding when the MA migrates far away from the sink node. Thus, the area covered by a typical itinerary will have a sector-like shape.

3.1 Directional source grouping algorithm

As shown in Fig. 2, the PE-zone is a disk around the PE with radius \(\alpha R_{max}\), where \(R_{max}\) denotes the maximum transmission range and \(\alpha \) is an input parameter in the range (0,1], [14]. Let \(K\) be the number of neighbors of the sink node within the PE-zone. These nodes are potential starting points for the migration of each MA. As illustrated in Fig. 2, with \(K = 4\), the algorithm can create a maximum number of four itineraries that MAs can follow. By controlling the value of parameter \(\alpha \), the size of the PE-zone and hence the maximum number of MAs can be adjusted.

Fig. 2
figure 2

Illustration of directional source-grouping Algorithm

Full size image
figure e

Algorithm 1 shows the pseudo-code of the proposed directional source grouping algorithm. At the beginning of the algorithm, the set of source nodes to be grouped (i.e., \(T\)) is reset to empty. Let \(Z_{PE}\) represents the PE-zone, and starting node \(SN_j\) denotes the immediate neighbor of the sink node within the radius of \(\alpha R_{max}\). We can see that with the iteration of the algorithm, the number of available starting nodes decreases. Let us denote \(Z_{PE}^{'}\) as the set of remaining starting nodes. If \(|Z_{PE}^{'}|\) is equal to 1, then all of the remaining source nodes are included in \(T\). Otherwise, a VCL needs to be determined. In the example shown in Fig. 2, \(VCL_2\) is selected to form the second itinerary, where a line connecting \(VCL_2\) and PE (i.e., \(line(VCL_2,PE)\) ) is depicted. A starting node (e.g., node \(e\)) is selected based on the metric of closest to \(line(VCL_2,PE)\). Next, the central line of the directional sector zone can be obtained (denoted by \(line(VCL_2,e)\). With node \(e\) as the center point and \(line(VCL_2,e)\) as the central line, if an expanding angle \(\theta \) is given, a directional sector zone can be determined, as shown in Fig. 2.

3.2 Iterative framework

For each iteration, a new CL will be calculated for the remaining source nodes. Then, a new list of source nodes will be assigned to a new MA. At this moment, the itinerary for the MA can be planned using any SIP algorithm, with the set of grouped source nodes \(T\) obtained by Algorithm 1. The SIP algorithms can be tree-based or loop-based, as shown in Fig. 2. If there are still remaining source nodes, the above process is repeated until all of the source nodes have been assigned to some MAs. The pseudo code of the iterative MIP framework is shown in Algorithm 2. After several iterations, there may remain only a few isolated source nodes. In the example shown in Fig. 2, two isolated nodes \(u\) and \(v\) are left after three iterations. In this case, \(u\) and \(v\) are simply assigned to the last itinerary with node \(f\) as the starting point.

figure f

3.3 Determination of sector size \(\theta \)

In SG-MIP, the radius of the disk is an important parameter in source grouping operation. Similarly, selection of the expanding angle \(\theta \) determines the sector size, which is important to yield an efficient itinerary. Though we have addressed the issue of effectively determining the central line of the sector zone, how to choose a suitable value for \(\theta \) remains a challenging problem. First, \(\theta \) can be selected based on the estimated node density in the WSN. On the other hand, \(\theta \) should be adaptively set for a different itinerary. In the example shown in Fig. 2, some sector zone should have a larger expanding angle (e.g., the one including \(VCL_1\)) to accommodate the full branch of source nodes in the corresponding direction. Finally, after several rounds of itinerary planning, the approach to handling the isolated source nodes can be fine-tuned. For example, instead of simply grouping the remaining isolated source nodes into the last itinerary, the algorithm can insert those isolated sources into existing itineraries one by one according to the metric of shortest distance to itinerary, so that the incremental cost of the formed itinerary is minimized.

4 Simulations

4.1 Simulation setup

We have implemented the proposed DSG-MIP algorithm as well as one existing SIP algorithm (i.e., LCF [10]) and one MIP algorithm (i.e., SG-MIP [16]), using OPNETFootnote 1 Modeler to perform computer simulations. The same network model in [16] is adopted, in which 800 nodes are uniformly deployed within a \(1000 \times 500\) m\({^2}\) field, and the sink node is located at the center of the field and multiple source nodes are randomly distributed in the network. The parameters for the MA system are shown in Table 1.

Table 1 Simulation parameters for mobile agent system
Full size table

4.2 Performance evaluation

In this section, we examine the impact of the number of source nodes on the energy and delay performance. We set the number of source nodes \(n\) from 10 to 40 in steps of 5, and obtain a set of results for each case. Figure 3 shows the impact of the number of source nodes on task energy, which includes transmitting, receiving, retransmitting, overhearing and collision, to obtain sensory data from all the source nodes. As shown in Fig. 3, when the number of source nodes is increased, more energy is needed for agents to perform the tasks in all of the three schemes. As the reference SIP solution, the task energy of LCF increases from 0.2 to 0.54 J/Task, while the number of source nodes increases from 10 to 40. By comparison, the MIP solutions exhibit higher energy efficiency. When the number of source nodes is 40, the energy of SG-MIP is decreased by 0.08 J/Task relative to LCF, whereas DSG-MIP achieves an extra energy saving of 0.02 J/Task above that of SG-MIP.

Fig. 3
figure 3

The impact of the number of source nodes on task energy

Full size image

Figure 4 shows the performance comparison of the three schemes in terms of task duration. In a SIP algorithm, the task duration is equivalent to the average end-to-end reporting delay, from the time when a MA is dispatched by the sink to the time when the agent returns to the sink. In an MIP algorithm, since multiple agents work in parallel, there must be one agent which is the last one to return to the sink. Then, the task duration of an MIP algorithm is the delay of that agent. Compared to energy performance, the number of source nodes \(n\) has a bigger impact on the delay. In LCF, it becomes much larger for a larger \(n\) value. With more source nodes to visit, the size of the MA becomes larger and more transmissions will be made. In reality, \(n\) is a good indicator of the MA related traffic load when a single agent is used. Compared to LCF, a typical MIP algorithm, SG-MIP, decreases task duration to about 0.6 s when \(n=40\). The reason for this outcome is that in single MA systems, one MA travels along the whole network to collect information from all source nodes. This procedure incurs a larger latency since the source nodes may be distributed all over the network. A multi-agent approach can speed up the task because multiple itineraries are applied simultaneously. As shown in Fig. 4, the task duration of the proposed DSG-MIP algorithm is always the lowest among all the schemes. The DSG-MIP scheme has 0.2 s less delay than SG-MIP when \(n=40\).

Fig. 4
figure 4

The impact of the number of source nodes on task duration

Full size image

For time-sensitive applications over energy constrained WSNs, the energy-delay product (EDP), given by \(EDP = energy \times delay\), is defined to facilitate assessment of the overall energy and delay performance of the algorithms. The smaller this value is, the better the unified performance will be. Figure 5 compares the overall EDP performance of LCF, SG-MIP and DSG-MIP. Due to its inferior performance in task duration, LCF has the largest value of EDP, which yields the worst overall performance among all of the algorithms. DSG-MIP outperforms SG-MIP with a decrease of EDP up to 35 % when \(n=40\).

Fig. 5
figure 5

The impact of the number of source nodes on EDP

Full size image

5 Conclusion

Deploying multiple MAs enhances the overall performance of MA systems in WSNs by providing a trade-off between energy consumption and task duration. However, the application of our previously proposed MIP algorithm, SG-MIP, is limited to WSNs with clustered source nodes. In this paper, we have proposed an enhanced MIP solution, DSG-MIP, which contains a directional source grouping algorithm for MIP in WSNs. The proposed source grouping approach partitions the network into directional sector zones with certain angles. Then, the source nodes within each sector zone are assigned to an itinerary. Extensive simulations have been carried out to show the superior performance of DSG-MIP in terms of delay and energy consumption. For future work, we shall address the adaptive selection of suitable expanding angles of the directional sector zones.