On Computing Mobile Agent Routesfor Data Fusion in Distributed Sensor NetworksQishi Wu, Member, IEEE, Nageswara S.V. Rao, Senior Member, IEEE , Jacob Barhen, Member, IEEE,S. Sitharama Iyengar, Fellow, IEEE, Vijay K. Vaishnavi, Fellow, IEEE, Hairong Qi, Member, IEEE, andKrishnendu Chakrabarty, Senior Member, IEEEAbstract—The problem of computing a route for a mobile agent that incrementally fuses the data as it visits the nodes in a distributedsensor network is considered. The order of nodes visited along the route has a significant impact on the quality and cost of fused data,which, in turn, impacts the main objective of the sensor network, such as target classification or tracking. We present a simplifiedanalytical model for a distributed sensor network and formulate the route computation problem in terms of maximizing an objectivefunction, which is directly proportional to the received signal strength and inversely proportional to the path loss and energyconsumption. We show this problem to be NP-complete and propose a genetic algorithm to compute an approximate solution bysuitably employing a two-level encoding scheme and genetic operators tailored to the objective function. We present simulation resultsfor networks with different node sizes and sensor distributions, which demonstrate the superior performance of our algorithm over twoexisting heuristics, namely, local closest first and global closest first methods.Index Terms—Genetic algorithms, mobile agents, distributed sensor networks.æ1INTRODUCTIONMULTIPLE sensor systems have been the target of activeresearch since the early 1990s [1] with a particularemphasis on the information fusion methods for distributedsensor networks (DSNs) [2], [3], [4]. Recent developments inthe sensor, networking, and computing areas now make itpossible to deploy a large number of inexpensive and smallsensors to “achieve quality through quantity” in complexapplications. In an important subclass of DSNs that aredeployed for remote operat ions in large unstructuredgeographical areas, wireless networks with low bandwidthare usually the only means of communication among thesensors. These sensors are typically lightweight withlimited processing power, battery capacity, and commu-nication bandwidth. The communication tasks consume thelimited power available at such sensor nodes and, therefore,in order to ensure their sustained operations, the powerconsumption must be kept to a minimum. Furthermore, themassively deployed senso rs typically generate a hugeamount of data of various modalities, which makes itcritical to collect only the most important data and to collectit efficiently. In addition, despite the abundance ofdeployed sensors, not all sensor data is critical to ensuringthe quality of fused information such as adequate detectionenergy for target detection or tracking.In conventional fusion architectures, all the sensor data issent to a central location where it is fused. But, thetransmission of noncritical sensor data in military DSNdeployments increases the risk of being detected in additionto consuming the scarce resources such as battery powerand network bandwidth. To meet these new challenges, theconcept of mobile agent-based distribute d sensor networks(MADSNs) has been proposed by Qi et al. [5] wherein amobile agent selectively visits the sensors and incrementallyfuses the appropriate measurement data. Mobile agents arespecial programs that can be dispatched from a source nodeto be executed at remote nodes. Upon arrival at a remotenode, a mobile agent presents its credentials, obtains accessto local services and data to collect needed information orperform certain actions, and then departs with the results.One of the most important aspects of mobile agents is thesecurity, which is not addressed here, but is being activelyinvestigated [6], [7]. The transfer of partial fusion results bya mobile agent may still have the risk of being spied on withhostile intent; the serial data collection process employed bythe mobile agent obviously decreases the chance ofexposing the individual raw data. Although there areadvantages and disadvantages of using mobile agents [8]in a particular scenario, their successful applications rangefrom e-commerce [9] to military situation awareness [10].They are found to be particularly useful for data fusiontasks in DSN. The motivations for using mobile agents inDSN have been extensively studied [5]. For a particularmultiresolution data integration application, it is shown740 IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, VOL. 16, NO. 6, JUNE 2004. Q. Wu, N.S.V. Rao, and J. Barhen are with the Center for EngineeringScience Advanced Research, Computer Science and Mathematics Division,Oak Ridge National Laboratory, One Bethel Valley Road, PO Box 2008,MS-6016, Oak Ridge, TN 37831-6016.E-mail: {wuqn, raons, barhen}@ornl.gov.. S.S. Iyengar is with the Department of Computer Science, Louisiana StateUniversity, Baton Rouge, LA 70803. Email: [email protected].. V.K. Vaishnavi is with the Department of Computer Information Systems,Georgia State University, PO Box 4015, Atlanta, GA 30302-4015.E-mail: [email protected].. H. Qi is with the Electrical and Computer Engineering Department,University of Tennessee, Knoxville, TN 37996. E-mail: [email protected].. K. Chakrabarty is with the Department of Electrical and ComputerEngineering, Duke University, Box 90291, 130 Hudson Hall, Durham,NC 27708. E-mail: [email protected] received 11 June 2003; revised 4 Dec. 2003; accepted 16 Jan. 2004.For information on obtaining reprints of this article, please send e-mail to:[email protected], and reference IEEECS Log Number TKDE-0092-0603.1041-4347/04/$20.00 ß 2004 IEEE Published by the IEEE Computer Societythat a mobile-agent implementation saves up to 90 percentof the data transfer time due to savings in avoiding the rawdata transfers. Also, the con ditions under which anMADSN performs better than a DSN are analyzed andthe conditions for an optimum performance of the formerare determined in [5]. In this paper, we direct our researchefforts to the networking aspects of MADSNs with a focuson a new routing method for mobile agents.The order and number of nodes on the route traversedby a mobile agent determine the energy consumption, pathloss, and detection accuracy and, hence, have a significantimpact on the overall performance of a MADSN. Lowenergy consumption, low path loss, and high detectionaccuracy are always