Abstract
The problem of computing a route for a mobile agent that incrementally fuses the data as it visits the nodes In a distributed sensor 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 simplified analytical model for a distributed sensor network and formulate the route computation problem in terms of maximizing an objective function, which is directly proportional to the received signal strength and inversely proportional to the path loss and energy consumption. We show this problem to be NP-complete and propose a genetic algorithm to compute an approximate solution by suitably employing a two-level encoding scheme and genetic operators tailored to the objective function. We present simulation results for networks with different node sizes and sensor distributions, which demonstrate the superior performance of our algorithm over two existing heuristics, namely, local closest first and global closest first methods.
| Original language | English |
|---|---|
| Pages (from-to) | 740-753 |
| Number of pages | 14 |
| Journal | IEEE Transactions on Knowledge and Data Engineering |
| Volume | 16 |
| Issue number | 6 |
| DOIs | |
| State | Published - Jun 2004 |
Funding
The authors would like to thank four anonymous reviewers for their insightful suggestions and constructive comments that greatly improved the presentation of the revised paper. This research was supported in part by the US Defense Advanced Research Projects Agency under grants No. N66001-00-C-8046 and No. K153, US Office of Naval Research under grant No. N000140110712, and by Engineering Research Program, US Department of Energy under contract No. DE-AC0500OR22725 with UT-Batelle, LLC. degree from the Indian Institute of Technology, Kharagpur, in 1990 and the MSE and PhD degrees from the University of Michigan, Ann Arbor, in 1992 and 1995, respectively, all in computer science and engineering. He is now an associate professor of electrical and computer engineering at Duke University. During 2000-2002, he was also a Mercator Visiting Professor at the University of Potsdam in Germany. He is a recipient of the US National Science Foundation Early Faculty (CAREER) award and the US Office of Naval Research Young Investigator award. His current research projects include: design and testing of system on-chip integrated circuits, embedded real-time systems, distributed sensor networks, modeling, simulation and optimization of microfluidic systems, and microfluidics-based chip cooling. Dr. Chakrabarty is a coauthor of two books: Microelectrofluidic Systems: Modeling and Simulation (CRC Press, 2002) and Test Resource Partitioning for System-on-a-Chip (Kluwer, 2002), and the editor of SOC (System-on-a-Chip) Testing for Plug and Play Test Automation (Kluwer 2002). He has published more than 150 papers in journals and refereed conference proceedings, and he holds a US patent in built-in self-test. He is a recipient of a best paper award at the 2001 Design, Automation, and Test in Europe (DATE) Conference. He is also a recipient of the Humboldt Research Fellowship, awarded by the Alexander von Humboldt Foundation, Germany. He is an associate editor, editor, and editorial board member of several publications. He has also served as an associate editor IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing. He is a member of the ACM and ACM SIGDA and a member of Sigma Xi and also a senior member of the IEEE and the IEEE Computer Society. He serves as vice chair of technical activities on IEEE’s Test Technology Technical Council, and is a member of the program committees of several IEEE/ ACM conferences and workshops.
Keywords
- Distributed sensor networks
- Genetic algorithms
- Mobile agents