Abstract
One practical goal of sensor deployment in the design of distributed sensor systems is to achieve an optimal monitoring and surveillance of a target region. The optimality of a sensor deployment scheme is a tradeoff between implementation cost and coverage quality levels. In this paper, we consider a probabilistic sensing model that provides different sensing capabilities in terms of coverage range and detection quality with different costs. A sensor deployment problem for a planar grid region is formulated as a combinatorial optimization problem with the objective of maximizing the overall detection probability within a given deployment cost. This problem is shown to be NP-complete and an approximate solution is proposed based on a two-dimensional genetic algorithm. The solution is obtained by the specific choices of genetic encoding, fitness function, and genetic operators such as crossover, mutation, translocation for this problem. Simulation results of various problem sizes are presented to show the benefits of this method as well as its comparative performance with a greedy sensor placement method.
| Original language | English |
|---|---|
| Pages (from-to) | 2721-2734 |
| Number of pages | 14 |
| Journal | Computer Communications |
| Volume | 30 |
| Issue number | 14-15 |
| DOIs | |
| State | Published - Oct 15 2007 |
Funding
Vijay K. Vaishnavi (SM ’89-F’01) received the BE degree (with distinction) in electrical engineering from Jammu and Kashmir University and the M.Tech and Ph.D. degrees in electrical engineering (with major in computer science) from the Indian Institute of Technology, Kanpur. He has also done postdoctoral work in computer science for two years at McMaster University, Canada. Dr. Vaishnavi is currently Professor of Computer Information Systems and Professor of Computer Science at Georgia State University. His current areas of research interest include inter-organizational systems (semantic interoperability, directory services, web-based virtual communities, coordination, security), software development (object-oriented metrics, software specifications and their maturity, object-oriented modeling and design), and data structures and algorithms (multi-sensor networks and fusion). The National Science Foundation and private organizations, including IBM, Nortel, and AT&T, have supported his research. He has authored numerous papers in these and related areas. His papers have appeared in IEEE Transactions on Software Engineering, IEEE Transactions on Knowledge and Data Engineering, IEEE Transactions on Computers, SIAM Journal on Computing, Journal of Algorithms, and several other major international journals and conference proceedings. Dr. Vaishnavi is an IEEE Fellow. He is also member of the IEEE Computer Society, the Association for Computing Machinery (ACM), and the Association for Information Systems (AIS). This research is supported in part by Defense Advanced Research Projects Agency under Grant No. N66001-00-C-8046 and by Office of Naval Research under Grant No. N000140110712. This research is also sponsored by Ballistic Missile Defense Organization Under MIPR No. 0100568954 and by the Engineering Research Program of the Office of Science, U.S. Department of Energy, managed by UT-Battelle, LLC under Contract No. DE-AC05-00OR22725. Dr. S.S. Iyengar is the Chairman and Roy Paul Daniels Chaired Professor of Computer Science and is also Satish Dhawan Chaired Professor at the Indian Institute of Science. He has been awarded the Distinguished Alumnus Award at the Indian Institute of Science in March 2003. He is the Distinguished Research Master Award winning Professor of the Computer Science Department at Louisiana State University. He has been involved with research in high-performance algorithms, data structures, sensor fusion, data mining, and intelligent systems since receiving his Ph.D. degree (in 1974 at Mississippi State University) and his M.S. from the Indian Institute of Science (1970). He has directed over 30 Ph.D. candidates, many of whom are faculty at major universities worldwide or scientists or engineers at national labs/industry around the world. He has served as a principal investigator on research projects supported by the Office of Naval Research (ONR), Defense Advanced Research Project Agency (DARPA), the National Aeronautics and Space Administration (NASA), the National Science Foundation (NSF), California Institute of Technology’s Jet Propulsion Laboratory (JPL), the Department of Navy-NORDA, the Department of Energy (DOE), LEQSF-Board of Regents, and the U.S. Army Research Office. His publications include 13 books (authored or coauthored textbooks; Prentice-Hall, CRC Press, IEEE Computer Society Press, John Wiley & Sons, etc.) and over 280 research papers in refereed journals and conference in areas of high-performance parallel and distributed algorithms and data structures for image processing and pattern recognition, and distributed data mining algorithms for biological databases. His books have been used in Berkeley, Purdue, University of Southern California, University of New Mexico, etc. He was a visiting professor at the Jet Propulsion Laboratory-Cal. Tech, Oak Ridge National Laboratory, the Indian Institute of Science, and at the University of Paris. Dr. Iyengar has served as an associate editor for the Institute of Electrical and Electronics Engineers and as guest editor for the IEEE Transactions on Knowledge and Data Engineering, IEEE Transactions and SMC, IEEE Transactions on Software Engineering, Journal of Theoretical Computer Science, Journal of Computer and Electrical Engineering, Journal of the Franklin Institute, Journal of American Society of Information Science, International Journal of High Performance Computing Applications, etc. He has served on review panel committees for NSF, NASA, DOE-ORNL, the U.S. Army Research Office, etc. He has been on the prestigious National Institute of Health-NLM Review Committee, in the area of Medical Informatics for 4 years. Dr. Iyengar is a series editor for Neuro-Computing of Complex Systems for CRC Press.
| Funders | Funder number |
|---|---|
| Ballistic Missile Defense Organization | 0100568954 |
| Department of Navy-NORDA | |
| LEQSF-Board of Regents | |
| U.S. Army Research Office | |
| UT-Battelle, LLC | |
| National Science Foundation | |
| Office of Naval Research | |
| U.S. Department of Energy | |
| National Aeronautics and Space Administration | |
| Defense Advanced Research Projects Agency | N66001-00-C-8046 |
| International Business Machines Corporation | |
| Office of Science | |
| Jet Propulsion Laboratory | |
| Nortel Networks Inc |
Keywords
- Distributed sensor systems
- Genetic algorithm
- Optimal surveillance
- Sensor deployment