An Energy Efficient Distributed Approach-Based Agent Migration Scheme for Data Aggregation in Wireless Sensor Networks

2.1 Centralized Approach-Based Schemes

In centralized approach-based schemes, the sink or PE collects the global information of network topology and computes the optimal migration path of the agents before dispatching them for data aggregation. In [6,7], the authors proposed a mobile agent-based distributed sensor (MADSA) network for energy efficient and scalable data aggregation. In [6], performance improvement of MADSA over the client/server model is shown using both analytically and through simulations. In [7], the authors proposed two simple heuristic algorithms, local closest first (LCF) and global closest first (GCF), to determine the itinerary for an agent migration. These heuristic algorithms are centralized and are not scalable since they are based on the global information of the network topology.

Wu et al. [8] proposed a genetic algorithm-based solution for planning the itinerary of an agent. This algorithm provides superior performance than the LCF and GCF algorithms do. However, the algorithms proposed in both [7] and [8] employ a single agent for data aggregation and collection tasks. The performance of a single agent-based approach declines as the network size increases. This is due to an increase in the agent’s state size as it traverses more sensor nodes, which results in more energy consumption and round trip delays. The algorithms proposed in [7,8] assume a perfect data aggregation model, which is a non-realistic assumption.

Mpitziopoulos et al. [9] have proposed a near-optimal itinerary design (NOID) algorithm where the Esau-Williams heuristic is used for finding an appropriate number of mobile agents and their near-optimal itineraries. In NOID, the parallel deployment of multiple agents is suggested where each agent visits a subset of nodes. NOID outperforms the single agent-based approaches (e.g., LCF, GCF, and GA), in terms of data fusion cost and overall response time [9], but it endures high computational complexity in determining the agents’ itineraries.

In [10–13], the authors proposed multi-agent itinerary planning (MIP) algorithms that help in the collection of concurrent sensor data to reduce latency. These algorithms differ in source node grouping methods. In [12], the authors used an angle gap for grouping all the source nodes in a particular direction as a single group. This approach does not describe how to find out an optimal angle gap threshold. In [13], the authors proposed a genetic algorithm by encoding how many agents are dispatched and which sensor nodes are visited by individual agents. The limitation of a genetic algorithm-based approach is its higher computational complexity [20]. These algorithms assume that the set of source nodes to be visited by the agents are predetermined, which limits the application scope of the network.

Mpitziopoulos et al. [2] proposed a CBID algorithm where agents are dispatched in parallel that sequentially visit nodes arranged in tree structures and after visiting a node with two or more child nodes, the master agent makes clones of themselves. Each slave agent visits a sub-branch of the tree. When all slave agents return back to their parent node, they hand over their collected data to the master agent [2]. In CBID [2], agent’s packet needs to carry extra cloning information about where to make clone. This algorithm has limited scalability.

In [14], the authors proposed a greedy tree-based itinerary design (TBID) algorithm to find near optimal itineraries for multiple agents. This algorithm is executed centrally at the sink and statically determines the number of agents that should be employed and their itineraries. The main theme of the TBID algorithm is to divide the area around the sink into concentric zones to construct the near optimal itinerary tree from inner zones to the outer zones. They used post order traversal with a possible shortcutting of the itinerary tree to derive an itinerary for each agent.

The main limitation of a centralized approach-based agent migration scheme is that it uses static migration paths (i.e., itineraries), which is based on a stale view of the network topology. This approach lacks dynamic recovery from node or communication link failures.

2.2 Distributed Approach-Based Schemes

The distributed approach-based agent migration protocol helps the agent to change the route dynamically according to the current state of the network.

Xu and Qi [15,16] proposed a dynamic agent migration algorithm for a target tracking application. In this method, an agent migrates to a sensor node that can get more accurate information about the target location by consuming less energy. For selecting the next node, they defined a cost function, which includes the following three components: energy consumption, information gain, and the remaining energy of a node. Once an agent accumulates sufficient information so that the accuracy of the estimation meets the desired level, the agent will terminate the migration and return to the sink [15,16]. This algorithm is more time expensive and may face difficulty in returning back to the sink without additional forwarding information.

In [17], the authors proposed the mobile agent-based directed diffusion (MADD) where an agent visits a subset of nodes. In MADD, the sink uses the first phase of the directed diffusion algorithm [21] to determine the subset of nodes. However, the actual data aggregation is carried out by dispatching an agent that sequentially visits the subset of nodes [20]. Shakshuki et al. [18] proposed a software agent-based directed diffusion where the order of node visits is determined at the sink node, but the authors did not describe the procedure. This method takes the routing cost and the remaining energy of a node for selecting a next node to be visited by an agent. The main limitations of the schemes described in [17,18] are that they depend on a directed diffusion scheme, that they incur extra communication overhead for agent migration, and that they are only applicable for query based data gathering applications.

Gupta et al. [19] proposed a multiple mobile agents with dynamic itineraries-based data dissemination (MMADIDD) protocol where nodes are organized in a set of the wedge regions and each agent is responsible for gathering aggregated data from each wedge region. The route of an agent is dynamically decided at each hop using cost function. MMADIDD adapts to unexpected node failures during an agent migration, but consumes slightly more energy than TBID [14]. This protocol provides a fair amount of fault tolerance, but the migration of agents depends on the wedge structure.

The work described in this paper also uses a distributed approach where nodes are organized in a set of spanning trees using a distributed algorithm. In the case of node failures, each orphaned node invokes a local recovery mechanism to find the new parent node, in order to maintain the tree topology. For agent migration, our protocol uses a dynamic and distributed approach where the migration of agents is decided at each visited sensor node.

4.1 Rooted Spanning Tree Construction

In this phase, the sink node creates an RSTreeCreationPkt packet, which contains the following three fields: senderNodeID, levelNo, and parentID. The field senderNodeID is the node ID of the sender node of this packet, levelNo is the number of hops to the root of the spanning tree, and parentID is the node ID of the sender’s parent. The field levelNo and parentID is set to 0 by the sink node. The value of levelNo of any node indicates the level number of the node in the tree. After the creation of the RSTreeCreationPkt packet, the sink broadcasts it. Any node that is within the transmission range of the sink receives the RSTreeCreationPkt packet and then becomes the children of the sink node. Each of these nodes then broadcast an RSTreeCreationPkt packet, which advertises that they are at level one. The sink node hears these broadcasts and sets the senders as its children. All the nodes of level one become the root of their spanning tree. Nodes that have not joined the spanning tree yet, make the sender their parent after receiving these packets. If a node receives more than one packet, it selects the parent node whose packet was received with the highest received signal strength indicator (rssi) value. Equation 1 expresses this condition.

Here, SN_j,k is sensor node j at level k of tree T_i and Parent(SN_j,k) is the parent node of the sensor node SN_j,k, SN_x,l is node x at level l, and l and k are the level numbers of the sensor node. This process is repeated until all of the nodes have joined the spanning tree.

Each node maintains a CandidatesForParent table having the three fields of nodeID, levelNo, and rssi. This table keeps the information of only those neighbors whose levelNo is less than or equal to its own levelNo. The rssi is the received signal strength indicator of the received RSTreeCreationPkt packet. This table is used to deal with the node failures. At the end of the tree formation phase, each node knows its parent node, its children, and its level number. Each node waits for time, t_delay before broadcasting its RSTreeCreationPkt packet. The value of t_delay depends on slot time assignment, t_st of MAC protocol. The value of t_delay is calculated as t_delay= m* t_st. Here, m is the maximum number of possible parent nodes in its transmission range. The pseudo-code for the rooted spanning tree construction phase is given in Algorithm 1.

Algorithm 1

Rooted Spanning Tree Construction Process

After the construction of the rooted spanning trees, each node disseminates the depth of its sub-tree back towards the root of the tree. Leaf nodes initiate this by disseminating a depth of 1 to their parent. When a node has received a packet from each of its children reporting its depth, it decides on the maximum depth of its children and adds one for itself and sends its depth to its parent. Once the internal sensor node SN_j of tree T_i has received the depth of the sub-tree rooted at SN_j, it sets up the maximum expected waiting time (t_wait) taken by a slave agent to complete its migration within the sub-tree T_{isubtree, k}

4.2 Clone-Based Agent Migration Phase

In this phase, the sink node creates mobile agents, MA_j for each rooted spanning tree, T_i. After that, the sink node dispatches an agent to each root of T_i for data aggregation and collection tasks. An agent starts data aggregation and collection from the leaf node of the T_i.

Each MA_j starts its migration from the root node of spanning tree T_i. When it reaches a sensor node SN_i with two or more child nodes, it builds clones of itself MA_clonej,k similar to [2], where k = 1, 2, ..m and m is number of children of the visiting node SN_i. Each clone agent MA_{clone j,k} is dispatched to visit the child node of the tree branch. However MA_j remains on the parent node SN_i. When slave agent MA_{clone j,k} reaches a leaf node, it starts performing the data aggregation task and returns back to the parent node SN_i where all of the data collected by MA_{clone j,k} is handed over to MA_j. After that the MA_{clone j,k} destroy it selves.

The structure of mobile agent packet is shown in Fig. 3. An agent packet contains the following four fields: MA_header, Processing code, MA_direction, and Payload. Initially, the MA_direction is set to DOWN, which indicates the moving direction of an agent from the root to the leaf node of the spanning tree T_i. When an agent reaches the leaf node, it sets the MA_direction to UP and starts data aggregation from the leaf node towards the root node. During MA migration from the root to the leaf node, the processing code part of the agent packet is stored at each node. Therefore, there is no need to carry the processing code parts of an agent when an agent moves in the UP direction.

Fig. 3

Structure of a master mobile agent (MA) (a) when the MA_direction is DOWN, (b) when the MA_direction is UP.

Algorithm 2 gives the details of the agent migration process within each tree T_i. Each MA_j waits for its clone agent MA _{clone j,k} up to t_wait maximum time, which can be computed by Eq. (2).

Algorithm 2

Clone-Based Agent Migration Process

Here, depth_Ti is depth of sub-tree T_i, t_trans is one hop transmission delay, and t_proc is the time needed for the agent to complete its data aggregation at each node. Fig. 4 illustrates the agent migration in a tree, T_i.

Fig. 4

Illustration of the clone-based agent migration scheme.

4.3 Dealing with Node Failures

The sensor nodes are a resource-constrained device, which make them highly prone to sudden failures. The most common reason for node failure is due to energy depletion. Therefore, in the proposed scheme, whenever the residual energy of a node SN_i goes down below a threshold energy level E_threshold, SN_i broadcasts a beacon packet to inform its neighbors that it cannot be a part of the spanning tree T_i. After receiving this beacon packet from node SN_i, each node deletes the entry of the dying node from its CandidatesForParent table. When a node fails, its children become orphan nodes. For dealing with this case, each orphaned child (u) finds another sensor node (v) in its CandidatesForParent table with the maximum RSSI and u.levelNo > v.levelNo that should be connected to the spanning tree to act as a parent node. If u failed to find any parent node with above condition, it looks for a node v with maximum RSSI and u.levelNo = v.levelNo. But in case of later, there is some possibility that siblings may become parent of each other which may cause a loop. After finding the suitable parent node, each orphaned node u sends an AttachMe packet to its new parent v. The AttachMe packet contains the following three fields: the orphaned node ID (orphaned_nodeID), the node ID of the new parent v (newParentID), and the depth of its sub-tree (depth_of_tree). After receiving the AttachMe packet from the orphaned node u, the parent node v sends acknowledgement to u and adds node u in its list of children. If the new parent node v finds any changes in its depth, it sends new depth to its parent and this process continues up to the root node of the spanning tree T_i.

5.1 Simulation Environment

We have simulated and tested the proposed protocol using the Castalia simulator, v.3.2 [22]. The sensor nodes were randomly deployed over a square-monitoring field with a fixed node density (0.0052 nodes/m²). The number of nodes was varied from 25 to 200 nodes to show the scalability property of the protocols. All of the sensor nodes had the same transmission range and battery power. For analyzing the results, each network scenario was executed 10 times and the results were plotted using a confidence interval of 95%. The simulation parameters used in our experiments are shown in Table 3.

Table 3

Parameters for simulations

We have used the following metrics to evaluate the performance of the protocols:

Here, N_{receivedAg ents} is the number of agents successfully received at the sink after completing their round trip and is the total number of agents dispatched by the sink in the network.

5.2 Impact of the Network Size

Fig. 5(a) and (b) shows the performance comparison of CDDAM with CBID, TBID, and MMADIDD, in terms of the average energy consumption with the varying number of nodes for different accumulated data, d (i.e. for d=100 and d=200, respectively). It demonstrates that average energy consumption increases as the number of node increases. This occurs due to the increase in the length of an agent’s itinerary and the number of nodes visited by an agent. The CDDAM protocol takes approximately 8% less energy than CBID, as shown in Fig. 5(a). This is due to the use of a shorter agent packet in the CDDAM protocol, which results in lower energy consumption than CBID. However, CBID is a centralized approach-based protocol where an agent needs to carry a pre-computed itinerary list, as well as cloning information, which increases the size of the agent packet. This results in extra transmission energy consumption for the agent migration within the network. Moreover, we observed that CDDAM consumes approximately 14% less energy than TBID. This is because CDDAM dynamically computes the routes of an agent at each host and uses the agent-cloning concept. Also, the agent’s itinerary length is shorter than TBID and MMADIDD. Due to the use of the cloning concept, each clone agent (SA) needs to carry a lighter payload. Furthermore, CDDAM consumes approximately 16% less energy than MMADIDD. This is because MMADIDD does not use the agent-cloning concept and agent’s itinerary length is longer, as compared to CDDAM.

Fig. 5

Performance of CDDAM and TBID in terms of average energy consumption for (a) d=100 and (b) d=200. CDDAM=clone-based dynamic and distributed agent migration, CBID=clone- based itinerary design, TBID=tree-based itinerary design, MMADIDD=multiple mobile agents with dynamic itineraries-based data dissemination.

Fig. 6(a) and (b) shows the performance comparison of CDDAM with CBID, TBID, and MMADIDD in terms of the overall response time for d=100 and d=200, respectively. It demonstrates that the overall response time increases as the number of nodes increases. This is due to the increase in the number of nodes visited by an agent. The overall response time of CDDAM is approximately 2% less than CBID. This is because an agent does not need to carry a pre-computed itinerary list and cloning information in the CDDAM protocol. However, CDDAM takes approximately 36% less time than TBID to complete one round of data aggregation and collection tasks. Moreover, the overall response time of MMADIDD is approximately 38% more than CDDAM. This is because CDDAM uses the agent-cloning concept, which offers a parallel deployment of the clone agent to complete the task, which results in a better response time than other schemes.

Fig. 6

Performance of CDDAM and TBID in terms of overall response time for (a) d=100 and (b) d=200. CDDAM=clone-based dynamic and distributed agent migration, CBID=clone-based itinerary design, TBID=tree-based itinerary design, MMADIDD=multiple mobile agents with dynamic itineraries-based data dissemination.

5.3 Impact of Faulty Nodes

Fig. 7 shows the performance comparison of CDDAM with CBID, TBID, and MMADIDD in terms of the success rate of the agents’ trip in the presence of faulty nodes. It can be observed from Fig. 6 that CDDAM and MMADIDD perform better than the protocols for other schemes in the presence of faulty nodes. This is because CDDAM and MMADIDD protocols are distributed algorithm based protocols where next the hop to be visited by an agent is dynamically decided at each host. However, CBID and TBID protocols are centralized algorithm based protocols where agents follow pre-computed routes for the migration of agents, which reduces the success rate in the presence of faulty nodes.

Fig. 7

Success rate of an agent’s trip in the presence of faulty nodes. CDDAM=clone-based dynamic and distributed agent migration, CBID=clone-based itinerary design, TBID=tree-based itinerary design, MMADIDD=multiple mobile agents with dynamic itineraries-based data dissemination.