Advanced
Distributed Information Extraction in Wireless Sensor Networks using Multiple Software Agents with Dynamic Itineraries
Distributed Information Extraction in Wireless Sensor Networks using Multiple Software Agents with Dynamic Itineraries
KSII Transactions on Internet and Information Systems (TIIS). 2014. Jan, 8(1): 123-144
Copyright © 2014, Korean Society For Internet Information
  • Received : May 21, 2013
  • Accepted : December 21, 2013
  • Published : January 30, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Govind P. Gupta
Department of Computer Science & Engineering, Indian Institute of Technology Roorkee-247667, India
Manoj Misra
Department of Computer Science & Engineering, Indian Institute of Technology Roorkee-247667, India
Kumkum Garg
Faculty of Engineering, Manipal UniversityJaipur-302026, India

Abstract
Wireless sensor networks are generally deployed for specific applications to accomplish certain objectives over a period of time. To fulfill these objectives, it is crucial that the sensor network continues to function for a long time, even if some of its nodes become faulty. Energy efficiency and fault tolerance are undoubtedly the most crucial requirements for the design of an information extraction protocol for any sensor network application. However, most existing software agent based information extraction protocols are incapable of satisfying these requirements because of static agent itineraries and large agent sizes. This paper proposes an Information Extraction protocol based on Multiple software Agents with Dynamic Itineraries (IEMADI), where multiple software agents are dispatched in parallel to perform tasks based on the query assigned to them. IEMADI decides the itinerary for an agent dynamically at each hop using local information. Through mathematical analysis and simulation, we compare the performance of IEMADI with a well known static itinerary based protocol with respect to energy consumption and response time. The results show that IEMADI provides better performance than the static itinerary based protocols.
Keywords
1. Introduction
A Wireless Sensor Network (WSN) is a distributed network, which consists of a large number of battery-powered sensor nodes and one or more sink nodes [1] . Sensor nodes are small electronic devices that have limited communication and computation capabilities. They are deployed for monitoring physical phenomenon such as temperature, light, humidity, vibration, sound and so on [1] . Generally, WSNs are deployed for specific applications, to accomplish certain objectives over a period of time. For this, it is crucial that the WSN continues to function over a period of time, even if some of its nodes become faulty. Energy efficiency and fault tolerance are undoubtedly the most crucial requirements for the design of an information extraction protocol for any WSN application. The design of a mobile software agent [2] based information extraction protocol should be carefully designed to optimize parameters like itinerary length, agent size and fault tolerant migration.
In recent years, the mobile agent computing paradigm has been introduced in WSNs for various purposes such as data aggregation and collection, topology discovery, network diagnostics and health monitoring, application reprogramming, etc. Successful functioning of these operations depends on the itinerary of the mobile software agent. A mobile software agent [2] is a software entity that can access the sensor nodes one by one, perform assigned task and fetch the results back to the sink node. When software agents are employed for information extraction task in the WSNs, the selection of the agent’s itineraries is extremely vital because it significantly affects the overall energy consumption, latency and information extraction cost. Thus a scheme that plans optimal length itineraries with minimum energy consumption, response time and low complexity for the nodes is required.
Most of the proposed itinerary planning algorithms [3 - 10] for agent based information extraction use a centralized algorithm that is executed at the sink node and that computes itineraries for the agents prior their migration. This is known as a static itinerary. The most notable issues associated with these algorithms are size of the agent packet and disruption in agent migration if some nodes fail along the itinerary. In the static itinerary based approach, each agent needs to carry a pre-computed itinerary which grows as network size increases, thereby also increasing agent size. Since static itineraries are computed using a centralized algorithm that requires updated global network topology information at the sink node and it does not offer quick response to possible topology changes resulting from node failure.
In order to solve the above issues, we propose a distributed algorithm for the Information Extraction protocol based on Multiple software Agents with Dynamic Itineraries, called IEMADI, where multiple agents are deployed in parallel to perform tasks assigned to them. In IEMADI, an agent computes its itinerary dynamically at each hop using local information and offers efficient and fault tolerant agent migration within the network. IEMADI is suitable for both periodic as well as query based information extraction and is resilient to sensor node failures.
In this paper we evaluate the performance of IEMADI through mathematical analysis and extensive simulation experiments and compare it with a well-known static itinerary based protocol TBID [8] and a distributed information extraction protocol, called Directed Diffusion(DD) [22] . Simulation results show that IEMADI performs notably better than TBID and DD in terms of average energy consumption, response time, network lifetime, and success rate of agents’ round trips, in the presence of node failures.
The remainder of this paper is organized as follows. In Section 2, we briefly review work related to the research presented herein. Section 3 presents the network model and the assumptions made. We describe the proposed protocol in Section 4. Section 5 gives the mathematical analysis. In Section 6, we present the performance evaluation of the proposed protocol. Finally, Section 7 concludes the paper and presents ideas for future work.
2. Related Work
In this section, we review existing mobile agent itinerary design algorithms for WSNs. WSNs usually have lower communication bandwidth than wired networks, due to which, sensory data traffic may exceed network capacity, resulting in collisions and energy wastage. To solve the problem of large sensory data traffic, Qi et al. [3] proposed a mobile agent based distributed sensor network (MADSN) for energy efficient data aggregation. The authors proved through mathematical and simulation studies that by sending mobile agents for data aggregation to the sensor nodes, a large amount of redundant data may be filtered at the sensor nodes, resulting in saving network bandwidth and reduced network latency.
In [4] , Qi et al. proposed two heuristic algorithms, Local Closest first (LCF) and Global Closest First (GCF) for itinerary design of an agent performing data aggregation. In LCF, each mobile agent originates its itinerary from the sink and chooses a sensor node with the shortest distance to its present location as the next-hop node for data aggregation. In GCF, each agent chooses a sensor node with the shortest distance to the center of the sensing field as the next-hop node.
In [5] , a genetic algorithm based approach is proposed for itinerary design of an agent. This algorithm derives a lower cost itinerary than LCF and GCF algorithms, but takes more time for itinerary calculation, which cannot be tolerated for time-sensitive applications. The algorithms proposed in [4] and [5] use only a single mobile agent deployed from the sink that successively visits all sensor nodes. The main drawback of these algorithms is that they are not scalable, i.e. their performance goes down as the network size increases. This is due to fact that the size of the mobile agent increases as it visits more and more sensor nodes, resulting in increase in overall energy consumption and the agent’s round trip time.
To overcome the drawback of single agent based itinerary design algorithms, Gavalas et al. [6] proposed a heuristic algorithm, called Near-optimal itinerary design (NOID). NOID calculates an appropriate number of agents that minimize overall communication cost and derives near optimal itineraries for each of them. NOID outperforms single agent based protocols proposed in [4] and [5] , both in terms of data fusion cost and the overall response time. The main drawback of NOID is that it is not suitable for highly dynamic networks [6] .
Cai et al. [7] proposed a genetic algorithm based Muti-Agent itinerary planning (GA-MIP) approach to address the drawback of the single agent based approach. The main drawback of this algorithm is that it requires a number of evolutionary iterations to determine efficient itineraries. This approach is time expensive and is not suitable for time-critical applications.
In [8] , Konstantopoulos et al. proposed a tree based itinerary design (TBID) algorithm, which improves upon NOID. TBID uses a greedy like approach for building a number of trees and determines the itineraries of the agents using post order tree traversal with possible shortcutting approach. The main drawback of this algorithm is that it is not suitable for dynamic network where network topology frequently changes due to channel fading or node failures.
In [9] , a clone based itinerary design (CBID) algorithm is proposed where sensor nodes are organized in a spanning tree rooted at the sink node. The sink node dispatches multiple agents, one for each branch of the tree, for data aggregation tasks. When an agent visits a node with two or more child nodes, it makes clones of itself, one for each child and sends it to its children. When all cloned agents return to the location of the master agent, they hand over their accumulated aggregated data to it. The main drawback of this algorithm is that an agent packet needs to carry additional information with it about when and where to clone, resulting in poor scalability.
In [10] , Chen et al. proposed an itinerary planning algorithm, called Itinerary Energy Minimum for First-source selection (IEMF) which extends the LCF algorithm by using the estimated communication cost. IEMF selects the next-hop node for agent migration by considering minimum energy cost.
Mpitziopoulos et al. [11] proposed a framework for supporting the visually impaired people, called PROTECT that employs autonomous software agents for locating and informing them for potential risks. PROTECT is executed at the sink where it forms a number of itinerary trees and the final itineraries for the agents are derived by tree traversal method proposed in [12] .
The algorithms proposed in [4 - 11] are centralized algorithms executed at the sink node, which generates static itineraries. There are many drawbacks of the centralized algorithm based itinerary design approach. First, it needs to collect periodically the location and residual energy information from all sensor nodes for calculating the updated itineraries, resulting in high communication overhead. Second, the agent may be unable to complete its round trip if some nodes die or become faulty along the itinerary. Third, each agent has to carry its itinerary, which increases its size as network size increases. Consequently, it takes more energy and time to transmit the agent packet. Finally, it does not offer quick response to possible topology changes.
Thus, static itinerary design does not suit highly dynamic sensor networks with large network size and is not efficient for those applications where network topology changes frequently and accurate topology information cannot be collected in advance at the sink node. Further, most of these algorithms fail to consider the requirement of fault tolerance in the context of mobile agent based WSNs.
In [13] , Xu et al. proposed a dynamic itinerary design for getting progressive fusion accuracy. In their approach, an agent selects that sensor node from its neighborhood, which has maximum residual energy, consumes minimum energy for its migration and offers more information gain. This approach is designed for target tracking applications.
In [14] , Gupta et al. proposed an agent based data dissemination protocol which decides the agent itinerary dynamically at each hop. The main weakness of this work is that the agent does not visit all nodes of the region.
Intanagonwiwat et al. [22] proposed a distributed information extraction protocol, called directed diffusion(DD). In DD, the sink disseminates interest message regarding the information to be extracted and each node records the neighboring node from which the interest message is received. Upon receiving the interest message, each node initiates the gradient setup phase in which it maintains a vector containing the next hope that has to be used to transmit the result of the query back to the sink node. The main drawback of DD is that it does not eliminate redundant data transmissions.
The advantages of the dynamic itinerary based agent migration approach are that it offers quicker response to possible topology changes and uses local information for computation of an agent’s itinerary better suited for resource-constrained sensor nodes. In addition, the size of an agent packet is noticeably smaller because it does not carry a pre-computed itinerary; instead, it decides the itinerary on the fly at each hop. Thus, the dynamic itinerary based agent migration approach suits highly dynamic sensor networks. Keeping this in mind, we propose a distributed algorithm for information extraction based on multiple agents with dynamic itineraries that is suitable for periodic as well as query based information extraction and resilient to sensor node failures.
3. Network Model and Assumptions
This work considers a sensor network consisting of N sensor nodes uniformly distributed in a circular monitoring area of radius R, similar to the model presented in [8] . A sink node is placed at the center of monitoring area. We assume each sensor node is static and knows its coordinates (x, y) in a two dimensional plane by means of some localization algorithms [15 - 17] where no GPS receiver is required. Each node knows the coordinates of the sink as well. Using these coordinates, each node x calculates its polar coordinate, denoted by (x. r, x.theta ), where x. r is the Euclidean distance of node from the sink and x. theta is an angle between the polar axis and the line connecting the sink and node x. Since sensor nodes are stationary, the setup of their polar coordinates is a one-time task [18] . We assume that node density in the network is sufficiently high to ensure migration of agent packets along the rings [19] .
4. Proposed Protocol
In this section, we present a distributed algorithm for the information extraction (IEMADI) protocol using multiple software agents with dynamic itineraries, for query based information extraction applications for WSNs. The operation of IEMADI consists of two phases: (1) initialization and (2) agent migration. This section describes each of these phases in detail. The data structures used in the design are given in Table 1 .
Data structures/variables used in processing
PPT Slide
Lager Image
Data structures/variables used in processing
- 4.1 Initialization
In the initialization phase, each node sets up its ringNo and wedgeNo using its polar coordinates. The width of the first ring is w . r max , where w is a constant in the range [0.5, 1.0] and r max is the maximum communication range of any node. The width of all other rings is r max / 2 . The pseudo code for the setup of ringNo and wedgeNo is given in Fig. 1 .
PPT Slide
Lager Image
Algorithm for the setup of ringNo and wedgeNo for node x.
Next, each node starts the neighbor discovery process, where it creates and broadcasts an ngbPkt packet. The ngbPkt packet contains five fields: nodeID, nodeEnergy, ringNo, wedgeNo, and polarCoord, where nodeID is the identifier for the node, nodeEnergy is the remaining energy of the node, ringNo is the ring identifier to which node belongs, wedgeNo is the wedge identifier to which node belongs, and polarCoord is the polar coordinate of the node.
If a node receives an ngbPkt packet from its own wedge, it updates its neighbor table with the values in the nodeID, ringNo, wedgeNo, nodeEnergy and polarCoord fields. The structure of neighbor table is shown in Fig. 2 . If a node x receives an ngbPkt packet from another wedge, it sets x.boundaryNode to true and informs its boundary state to its neighbors by broadcasting a beacon packet. At the end of this phase, each node knows its ringNo, wedgeNo and also all its neighbors within its transmission region in its wedge.
PPT Slide
Lager Image
Structure of a neighbor table
- 4.2 Agent Migration Process
In this phase, the sink node creates and dispatches software agents to the first ring of each wedge W i , where i=1, 2… W . Here W is the number of wedge regions that depends on angular width (α) of the wedge region. The structure of the mobile agent packet is shown in Fig. 3 . The header of a mobile software agent packet contains four fields: ma_ID, ma_direction, moveflag and maxRingNo, where ma_ID is the identifier for the agent, ma_direction is a flag variable which shows the direction of the agent migration from one ring to another, moveFlag is a flag variable which shows the direction of agent migration within each ring, and maxRingNo is the maximum ring number which is computed by the sink node since it knows the radius of the monitoring area (R) and width of each ring.
PPT Slide
Lager Image
Structure of the mobile agent packet
The agent migration process is divided into two sub-phases. In the first sub-phase, an agent migrates through boundary nodes with minimum theta value from the inner to the outer ring. In the second phase, data aggregation starts from the outer ring and the agent migrates within the wedge in a spiral order from the outer to inner ring towards the sink, as shown in Fig. 4 . In the initial traversal from sink to a node in outermost ring, an agent does not gather data. It starts gathering data from the node of the outer ring. The advantages of this approach is that it avoid unnecessary carry of data from the nodes during initial traversal from sink to a node in the outermost ring, as a result itinerary cost of an agent decreases.The flowcharts for agent migration process is given in Fig. 5 .
PPT Slide
Lager Image
Agent migration within wedge
PPT Slide
Lager Image
Flowchart for the agent migration algorithm executed by node x
During agent migration, if next hop in the ring does not meet threshold requirements, an agent selects an alternate node of the adjacent ring to complete the visit of the remaining nodes of the ring. If there is no alternate node available with required threshold, an agent simply jumps to the inner ring to traverse their nodes. If there is no neighbor node available in its neighbor table which satisfies the threshold condition, agent will not be move further and information extraction process is abandoned.
5. Mathematical Analysis
In this section, we evaluate the performance of our proposed protocol in terms of energy consumption and response time. These two metrics reflect the efficiency of agent based protocols. Assume N nodes are uniformly distributed over a circular sensing field which is divided into W wedge regions, each having an equal number of nodes n .
- 5.1 Energy Consumption Analysis
We first calculate the total energy consumed ( Etotal ) in one round of agent based information extraction. Etotal depends on the number of agents deployed, size of the agent packet and the number of nodes visited by each agent. In WSNs, information extraction process is performed in rounds. In each round of information extraction, the sink node dispatches a number of software agents where it visits a set of nodes, perform data aggregation and carry relevant information with it and return to the sink. This whole cycle is called one round of information extraction. Let size of agent packet at ith node be Sagentsizei Then, Etotal can be expressed by the following formula:
PPT Slide
Lager Image
Here, n = N / W . ERx and ETx is energy consumed in receiving and transmitting a byte of message respectively. EDA is the energy consumed in processing at each node. Eextra is total energy consumed in forwarding an agent from the sink to the starting sensor node from where agent starts data collection.
Let the size of agent packet when dispatched from the sink node be Sini bytes and on average a d bytes increase in agent size occurs at each sensor node after query based information. The size of agent packet at ith node, Sagentsizei is given by:
PPT Slide
Lager Image
For IEMADI protocol, initial size of the agent packet ini forIEMADI Sini _ forIEMADI , is given by:
PPT Slide
Lager Image
Here Sheader is size of header. From Fig. 3 , we can see that header of the agent packet contains four fields and the size of header is 2 bytes. Sproc _ log ic is the size of processing code carried with an agent and Spayload is the size of payload, initially value of Spayload is zero, when an agent dispatched by the sink. Equation 3 can be rewritten as:
PPT Slide
Lager Image
Therefore, from equation 2 and 4, for IEMADI, the size of the agent packet at the ith node, SIEMADI_agentsizei is given by:
PPT Slide
Lager Image
For IEMADI protocol, extra total energy consumed ( Eextra _ forIEMADI ) is equal to total energy dissipation in forwarding an agent from sink to the outer ring of the wedge. Eextra _ forIEMADI is given by:
PPT Slide
Lager Image
From equation 6, it is evident that value of Eextra _ forIEMADI is constant for each wedge. Hence, from equation 1, 5 and 6, total energy consumed in one round of query based information extraction for IEMADI protocol ( Etotal _ IEMADI ) is given by:
PPT Slide
Lager Image
Here Eextra _ forIEMADI is constant for all wedges. From equation 7, it is evident that total energy consumed in one round of query based information extraction depends on agent size and number of nodes visited by it. Since wedge angular width α = (360/ W ) and W = ( N / n ) , we can simplify equation 7 by putting the value of W , n and extra Eextra _ forIEMADI , as given by:
PPT Slide
Lager Image
The optimal value of α can be obtain by taking differential of equation 8 ( Etotal _ IEMADI ) with respect to α. We get following expression:
PPT Slide
Lager Image
For network scenario where N=300 nodes are deployed in a circular monitoring area of radius 100m. The value of Sproc _ log ic and d is 1000 and 100 bytes respectively. If ERx = 0.0074 joules per byte and ETx = 0.0074 joule per byte, we get minimum value of α is 15.19 by putting these values in equation 9. For this network scenario, Fig. 6 plots the effect of α on the average energy consumption ( Etotal _ IEMADI / N ) by using the equation 8.
PPT Slide
Lager Image
Average energy consumption vs. α for IEMADI protocol
In a static itinerary based protocol, each agent carries a pre-computed itinerary list. Initial size of the agent packet for static itinerary based protocol such as TBID, Sini _ forTBID , is given by:
PPT Slide
Lager Image
Here, value of Sheader is 1 byte since it contains only one field: agent identifier which occupies one byte. Sitinerary _ list is size of itinerary list. Let an agent visit n nodes. If the entry for each node in the itinerary list takes l bytes, the size of itinerary list ( Sitinerary _ list ) will be n * l . Initially value of Spayload will be zero. Hence equation 10 can be rewritten as:
PPT Slide
Lager Image
The size of the agent packet at the ith node, STBID _ agentsizei for TBID can be calculated from equation 2 and 10 and is given by:
PPT Slide
Lager Image
For TBID protocol, extra total energy consumed ( Eextra _ forTBID ) is equal to total energy dissipation in forwarding an agent from sink to the leftmost leaf node of the itinerary tree.
Eextra _ forTBID is given by:
PPT Slide
Lager Image
Here, h is height of itinerary tree. From equation 13, it is evident that value of Eextra _ forTBID is constant for each tree. Hence, from equation 1, 12 and 13, total energy consumed in one round of information extraction for TBID protocol ( Etotal _ TBID ) can be expressed by the following formula:
PPT Slide
Lager Image
Table 2 shows the mathematical expressions for energy consumption for IEMADI and TBID protocols. It is evident that IEMADI consumes less energy because the agent packet does not carry pre-computed itinerary list, unlike in a static itinerary based protocol such as TBID, where it does. Since size of itinerary list grows as network size increases, higher energy consumption results in case of static itinerary based protocols.
Energy consumption analysis
PPT Slide
Lager Image
Energy consumption analysis
- 5.2 Response Time Analysis
Response time ( Tresponse _ time ) is the time interval from the moment the first agent is dispatched from the sink node to the time all the agents return back to it. Agent migration time ( T migi ,i +1 ) from ith node to (i+1)th node depends on the communication bandwidth (bytes per sec) and the current size of the agent. If an agent visits n nodes in its itinerary, Tresponse _ time is given by:
PPT Slide
Lager Image
Here, Tinst is time spent in instantiation of an agent packet at the sink. The value of Tinst is constant for each agent. Textra is time spent in forwarding the agent from the sink to the starting sensor node from where the agent starts data collection. The value of Textra is constant for each agent. Tproc is the time spent by the agent to complete its assigned task at a node. The value of Tproc is constant for each agent. Tprop is the agent propagation time and depends on the physical distance travel by it. Let the agent packet be transmitted over a communication channel of bandwidth B bytes per sec. For dynamic itinerary based protocol, agent migration time ( T migi ,i +1 ) from ith node to (i+1)th is given by [20] :
PPT Slide
Lager Image
From equations 15 and 16, response time ( Tresponse _ time _ IEMADI ) for IEMADI is given by:
PPT Slide
Lager Image
By putting the value of Sini _ forIEMADI from equation 4 into equation 17, equation 17 can be rewritten as:
PPT Slide
Lager Image
Similarly, from equation 12 and 16, for a static itinerary based protocol, agent migration time ( T migi ,i +1 ) from ith node to (i+1)th is given by:
PPT Slide
Lager Image
Therefore, response time ( Tresponse _ time _ TBID ) for a static itinerary based protocol such as TBID is given by:
PPT Slide
Lager Image
Table 3 shows the mathematical expressions for response time for IEMADI and TBID protocols. It is seen that the response time Tresponse _ time is dominated by the agent size and the length of the agent’s itinerary.
Response time analysis
PPT Slide
Lager Image
Response time analysis
6. Performance Evaluation
This section presents the performance analysis of the IEMADI under different network scenarios and compares it with TBID [8] and DD [22] . We vary the network size, wedge angle, as well as percentage of faulty nodes and evaluate the average energy consumption, response time, network lifetime and success rate of the agent’s round trip under different network scenarios. All the simulation results with 95% confidence interval are shown in this section.
- 6.1 Simulation Setup
We use a discrete event simulator Castalia3.2 [21] that is based on OMNeT++ platform, for all evaluations. We adopt the network model used in [8] and [18] , in which 50-300 nodes are uniformly distributed within a circular sensing field of different radius to maintain the same node density. For simplicity, the sink node is placed at the center of the sensing field. The transmission radius of sensor nodes is 25m. All sensor nodes have the same initial battery power 18720J (equivalent to one 2AA battery). We have used T-MAC protocol at MAC layer to simulate the proposed scheme. In our experiments, T-MAC protocol takes care of disconnection issues arises between the adjacent sensor nodes due to nodes’sleep. The simulation parameters are listed in Table 4 . We used the following metrics for performance evaluation:
Simulation parameters
PPT Slide
Lager Image
Simulation parameters
  • 1.Average Energy consumption(Eavg):The amount of energy consumed by a node in performing the required network operation in each round of data collection.
  • Eavg= (Sum of energy consumption at each node) / (number of nodes)
  • 2.Response time(Tresponse_time):The average time interval required to complete one round of data collection.
  • Here,Ti ,jis the time taken by thejthagent ofithround to complete its data aggregation task, k is number of agents and p is the round number.
  • 3.Network lifetime:Lifetime of a sensor network basically depends on the energy dissipation of individual sensor nodes. It is defined as time duration until the first sensor node in the network dies due to battery exhaustion. Since agents are used for collecting the aggregated data from the network, the network lifetime is calculated as total number of successful rounds of data collection by the agents.
  • 4.Success rate of agent’s round trip:The number of agents received by the sink as a percentage of the total number of agents dispatched by it.
- 6.2 Impact of Angular Width (α) Variation
Fig. 7 (a) and (b) show the effects of the increase in angular width ( α ) of the wedge on the average energy consumption and response time respectively. For this experiment, we use a network scenario where 300 nodes are uniformly deployed with fixed node density (0.0052 nodes/ sq. m.) and value of the payload ( d ) is 100 bytes. From the Fig. 7 (a), we can observe that average energy consumption decreases as the value of α decreases from 60 to 15, but further increases as the value of α decreases from 15 to 5. Based on this result, we can conclude that when the value of α is below a threshold value, wedge region will become very narrow and an agent travels in line from sink to outer ring and return backs with almost using same path. Due to this reason, an agent visits twice each node of the wedge. As a result each node has to forward the agent packet two times, this increases average energy consumption. For the first case when value of α decreases from 60 to 15, size of wedge region decreases and each agent visits nodes of the wedge except boundary nodes only one time. However, number of nodes of the wedge visited by an agent decreases with decrease in value of α from 60 to 15, as a result average energy consumption decreases due to payload size of the agent packet decreases.
PPT Slide
Lager Image
Performance analysis of IEMADI with varying value of α
From the Fig. 7 (b), we can observe that response time decreases as the value of α decreases from 60 to 15, but almost same as the value of α decreases from 15 to 5. This is because as the value of α decreases, the number of nodes visited by the agents also decreases, resulting in decrease in response time.
- 6.3 Impact of payload size (d) variation
Fig. 8 (a) and (b) show the effects of the increase in the value of d on the average energy consumption and response time respectively. From the Fig. 8 (a), we can observe that as the value of d increases, average energy consumption also increases since the agent packet size increases. In the IEMADI, average energy consumption increases slower compare to IEMADI when the value of d increases. This is because IEMADI uses dynamic itineraries for the agents in which the agent does not carry itinerary list which makes its size smaller than the agent used in TBID. In addition, IEMADI uses shorter itinerary length for the agent compare to TBID. DD consumes higher energy than IEMADI and TBID. This is due to fact that each node sends their raw data to the sink and intermediate nodes not only transmit its data but also transmit its children’s data as well.
PPT Slide
Lager Image
Performance comparison of IEMADI and TBID with varying value of payload size (d)
From the Fig. 8 (b), we can observe that response time grows as the value of d increases. In the IEMADI, response time increases slower compare to TBID when the value of d increases due to the smaller size of agent packet and itinerary length used in IEMADI compare to TBID. However, DD takes more response time than IEMADI and TBID as the payload increases. The reason for this is same as discussed in above paragraph.
- 6.4 Impact of Network Size Variation
Fig. 9 (a) and (b) show the result of the comparison of IEMADI with TBID and DD in terms of average energy consumption with varying number of nodes for d=100 and d=200, respectively. From Fig. 9 , we observe that the average energy consumption increases with the increase in network size because of increase in agent’s itinerary and size, which increases as the number of nodes increases. IEMADI consumes approximately 12% less energy compared to TBID. This is due to the use of dynamic agent migration, where the agents need not carry the pre-computed itinerary. As a result the size of the agent packet becomes smaller and saves communication energy. However, DD consumes more energy than IEMADI and TBID. This is because each node in DD sends their data to the sink through multihop transmission towards the sink and intermediate nodes are also work as relay nodes for forwarding the data packets of its children nodes.
PPT Slide
Lager Image
Performance comparison of IEMADI, TBID, and DD in terms of average energy consumption
Fig. 10 (a) and (b) shows the comparison of IEMADI with TBID and DD, in terms of response time with varying number of nodes for d =100 and d =200, respectively. We observe that the response time increases with increase in network size, because of increase in agent’s itinerary and size. Since an agent accumulates more data as the network size increases, it takes more time to transmit the agent. IEMADI takes approximately 2% less time as compared to TBID to complete one round. This is again due to the dynamic agent migration scheme, where the agents need not carry pre-computed itineraries; as a result the size of agent packet becomes smaller and thus reduces response time. Response time for DD is less when number of nodes are less compare to TBID. When number of nodes increases, response time for DD is increases compare to TBID.
PPT Slide
Lager Image
Performance comparison of IEMADI, TBID, and DD in terms of response time
Fig. 11 gives the comparison of IEMADI with TBID and DD, in terms of network lifetime with varying number of nodes. It is evident that network life time decreases with the increase in network size because of increase in agent’s itinerary length and size. This is due to fact that an agent has to visit more nodes as the network size increases. The network life time of IEMADI is approximately 28% higher than TBID. This is because of the calculation of dynamic itinerary at each hop and smaller size of agent. As a result, it takes less energy to transmit an agent and thus enhances network lifetime. However, in TBID, sink needs to collect topology information periodically, resulting in more energy consumption. In addition, the agents carry pre-computed itineraries which increase its size, hence take more energy of the node for agent migration. The network life time of IEMADI is approximately 30% higher than DD.
PPT Slide
Lager Image
Network lifetime vs. number of nodes
- 6.5 Impact of Node Failures
Fig.12 gives a comparison of IEMADI with TBID in terms of success rate of agents’ round trip with varying percentage of faulty nodes present in the network. It is seen that success rate in IEMADI is notably higher than in TBID. This is because IEMADI calculates agents’ itineraries at each hop dynamically using local information; as a result it bypasses faulty nodes. However, in TBID, an agent carries a pre-computed itinerary and strictly follows the node sequence in it. For this reason, it is unable to complete its round trip, if some nodes fail along the itinerary.
PPT Slide
Lager Image
Success rate of agents’ trip in presence of faulty nodes
7. Conclusion
This paper has proposed an information extraction protocol, based on multiple mobile agents with dynamic itineraries, for reducing the impact of faulty nodes on the agent’s migration and enhancing network lifetime. We studied the performance of the proposed protocol IEMADI through mathematical analysis and extensive simulation experiments, and compared it with a static itinerary based protocol, TBID and a distributed information extraction protocol, DD. The mathematical analysis and simulation results confirmed that IEMADI performs notably better in terms of average energy consumption, response time, network lifetime and success rate of agents’ round trip, as compared to TBID and DD. In future, we plan to extend this work for mobile wireless sensor networks and study the impact of node mobility on the agent migration.
BIO
Govind Gupta received the B.E. degree in Computer Science and Engineering in 2000 from CCS Meerut University, Meerut, India, and M.Tech degree in Computer Science and Engineering in 2007 from UP Technical University, Lucknow, India. He is currently a PhD candidate in the Department of Computer Science & Engineering at Indian Institute of Technology, Roorkee, India. His research interests include mobile computing, wireless ad hoc and sensor network, network security, distributed computing and performance evaluation. He is a student member of IEEE.
Manoj Misra received his Bachelor’s degree in Electrical Engineering in 1983 from HBTI Kanpur, India and Master’s in Computer Science in 1986 from University of Roorkee, India. He received his PhD in Computer Science in 1997 from University of Newcastle, Upon Tyne, UK. He is currently a Professor in the Department of Computer Science and Engineering at Indian Institute of Technology, Roorkee. He has guided several PhD theses, ME/MTech dissertations. His areas of interest include mobile computing, distributed computing, wireless ad hoc and sensor network and performance evaluation. He is a senior member of IEEE.
Kumkum Garg received her Bachelor’s in Electronics Engineering from University of Roorkee, India in 1971 and Master’s in Computer Engineering in 1977 from University of Roorkee, India. She received her PhD in Computer Engineering in 1984 from University of London, UK. She has been a Professor in the Department of Computer Science and Engineering, Indian Institute of Technology, and Roorkee, India from 1989 to 2010. She has been the Head of Information superhighway Centre from 2005 to 2006 at IIT, Roorkee. Currently, she is Professor of Computing and Dean, Faculty of Engineering at Manipal University Jaipur, India. She has guided several PhD theses, ME/MTech dissertations and completed various projects. Her research interests include mobile computing, mobile agents, network security, trust, wireless ad hoc and sensor network. She is a senior member of the IEEE Computer Society.
References
Akyildiz I.F. , Su W. , Sankarasubramaniam Y. , Cayirci E. 2002 “Wireless sensor networks: a survey” Computer Networks Article (CrossRef Link) 38 393 - 422    DOI : 10.1016/S1389-1286(01)00302-4
Chen M. , Gonzalez S. , Leung V. 2007 “Applications and design issues for mobile agents in wireless sensor networks” IEEE Wireless Communication Article (CrossRef Link) 14 (6) 20 - 26    DOI : 10.1109/MWC.2007.4407223
Qi H. , Iyengar S. S. , Chakrabarty K. 2001 “Multi-Resolution Data Integration Using Mobile Agents in Distributed Sensor Networks” IEEE Transactions on Systems, Man, and Cybernetics, Part C Article (CrossRef Link) 31 (3) 383 - 391    DOI : 10.1109/5326.971666
Qi H. , Wang F. 2001 “Optimal Itinerary Analysis for Mobile Agents in Ad Hoc Wireless Sensor Networks” in Proc. 13th International Conference on Wireless Communications (Wireless’2001) Calgary, Canada vol. 1 147 - 153
Wu Q. , Rao N. , Barhen J. , Iyengar S. , Vaishnavi V. , Qi H. , Chakrabarty K. 2004 “On Computing Mobile Agent Routes for Data Fusion in Distributed Sensor Networks” IEEE Transactions on Knowledge and Data Engineering Article (CrossRef Link) 16 (6) 740 - 753    DOI : 10.1109/TKDE.2004.12
Gavalas D. , Mpitziopoulos A. , Pantziou G. , Konstantopoulos C. 2009 “An approach for near-optimal distributed data fusion in wireless sensor networks” Springer Wireless Network Article (CrossRef Link) 16 1407 - 1425    DOI : 10.1007/s11276-009-0211-0
Cai W. , Chen M. , Hara T. , Shu L. , Kwon T. 2011 “A genetic algorithm approach to multi-agent itinerary planning in wireless sensor networks” Springer Mobile Network application Article (CrossRef Link) 16 (6) 782 - 793    DOI : 10.1007/s11036-010-0269-z
Konstantopoulos C. , Mpitziopoulos A. , Gavalas D. , Pantziou G. 2010 “Effective determination of mobile agent itineraries for data aggregation on sensor networks” IEEE Transaction on Knowledge and Data Engineering Article (CrossRef Link) 22 (12) 1679 - 1693    DOI : 10.1109/TKDE.2009.203
Mpitziopoulos A. , Gavalas D. , Konstantopoulos C. , Pantziou G. “CBID: a scalable method for distributed data aggregation in WSNs” Hindawi International Journal of Distributed Sensor Network Article ID 206517, pp.13, 2010. Article (CrossRef Link) 2010
Chen M. 2011 “Itinerary Planning for Energy-efficient Agent Communication in Wireless Sensor Networks” IEEE Transactions on Vehicular Technology Article (CrossRef Link) 1 - 1
Mpitziopoulos A. , Konstantopoulos C. , Gavalas D. , Pantziou G. 2011 “A pervasive assistive environment for visually impaired people using wireless sensor network infrastructure” Journal of Network and Computer Applications Article (CrossRef Link) 34 194 - 206    DOI : 10.1016/j.jnca.2010.07.017
Averbakh I. , Berman O. 1995 “Sales-delivery man problems on treelike networks” Networks Article (CrossRef Link) 25 45 - 58    DOI : 10.1002/net.3230250204
Xu Y. , Qi H. 2008 “Mobile agent migration modeling and design for target tracking in wireless sensor networks” Ad Hoc Networks Article (CrossRef Link) 6 (1) 1 - 16    DOI : 10.1016/j.adhoc.2006.07.004
Gupta G. P. , Misra M. , Garg K. 2012 "Multiple Mobile Agents based Data Dissemination Protocol for Wireless Sensor Networks" in Proc. of Springer International Conference on Advances in Computer Science and Information Technology, Networks and Communications 334 - 345
Bulusu N. , Heidemann J. , Estrin D. 2000 “GPS-Less Low Cost Outdoor Localization for Very Small Devices” IEEE Personal Communication Article (CrossRef Link) 7 (5) 28 - 34    DOI : 10.1109/98.878533
Mao G. , Fidan B. , Anderson B. D. 2007 “Wireless sensor network localization techniques” Computer Networks Article (CrossRef Link) 51 (10) 2529 - 2553    DOI : 10.1016/j.comnet.2006.11.018
Wang Y. , Wang X. , Wang D. , Agrawal D. P. 2009 “Range-free localization using expected hop progress in wireless sensor networks” IEEE Transactions on Parallel and Distributed Systems Article (CrossRef Link) 20 (10) 1540 - 1552    DOI : 10.1109/TPDS.2008.239
Rachuri K. K. , Murthy C.S.R. 2010 “On the scalability of expanding ring search for dense wireless sensor networks” Journal of Parallel and Distributed Computing Article (CrossRef Link) 70 (9) 917 - 929    DOI : 10.1016/j.jpdc.2010.05.004
Intanagonwiwat C. , Estrin D. , Govindan R. , Heidemann J. 2002 “Impact of network density on data aggregation in wireless sensor networks” in Proc. of ICDCS’02, the 22nd International Conference on Distributed Computing Systems 457 -
Verma V , Joshi R. C. , Xie B , Agrawal D. P. 2008 “Combating the bloated state problem in mobile agents based network monitoring applications” Computer Networks Article (CrossRef Link) 52 (17) 3218 - 3228    DOI : 10.1016/j.comnet.2008.08.017
2012 Castalia Simulator [online] .
Intanagonwiwat C. , Govindan R. , Estrin D. , Heidemann J. , Silva F. 2003 “Directed diffusion for wireless sensor networking” IEEE/ACM Transactions on Networking Article (CrossRef Link) 11 2 - 16    DOI : 10.1109/TNET.2002.808417