NTA/Rosettex National Imagery and Mapping Agency (NIMA)
Clustering sensors in wireless ad hoc networks
Sensors in a data fusion environment over hostile territory are geographically dispersed and change location with time. In order to collect and process data from these sensors an equally flexible network of fusion beds (i.e., clusterheads) is required. To account for the hostile environment, we allow communication links between sensors and clusterheads to be unreliable. We develop a mixed integer linear programming (MILP) model to determine the clusterhead location strategy that maximizes the expected data covered minus the clusterhead reassignments, over a time horizon. A column generation (CG) heuristic is developed for this problem. Computational results show that CG performs much faster than a standard commercial solver and the typical optimality gap for large problems is less than 5%. Improvements to the basic model in the areas of modeling link failure, consideration of bandwidth capacity, and clusterhead changeover cost estimation are also considered.
UB news services
Sarnoff news and press release
Justice Technology and Information Network
Wbfo 88.7 FM (click on media logo of 4/16/04)
Understanding battlefield realities, Industrial Engineer Vol. 36, No. 3, p. 19, March 2004
- Determining the ideal network architecture (hierarchical, heterarchical or hybrid) for particular decentralized fusion problems. This would depend on the mobility of the entities, and hence, is expected to be different for land and air tracking.
- Maximizing the coverage of sensors by (s)election of “Clusterheads” or “Gateways” to enhance the state of information gathering, fusion and communication. This problem would be addressed at two levels: (i) Near optimal optimization-based approaches, and (ii) Fast heuristic-based approaches.
- Consideration of threat, enemy attack, or natural hazards through wireless link failure probabilities. Developing scenarios that would specify the presence or likely presence of enemy in the theater.
- Consideration of fusion processing capacity and bandwidth considerations in the topology design problem.
- Performance evaluation of these schemes in terms of computational speed and optimality gap.
Dr. Rakesh Nagi
117 Transportation Building
104 S. Mathews
Urbana Illinois 61801
Phone: (217) 244-3848
Fax: (217) 244-57052
Dr. Rajan Batta, Professor
Department of Industrial Engineering
State University of New York at Buffalo
420 Bell Hall
Buffalo, NY 14260-2050
Telephone: (716) 645-2357
FAX: (716) 645-3302
- Abhay Joshi; PhD 1/06. “Optimization Approaches to Network Topology Design For Dynamic Distributed Wireless Sensing in a Hostile Environment.” (co-advised with Rajan Batta). Position: OR Analyst, Curbell Inc., Orchard Park NY.
- Dipeshkumar Patel; MS 12/02. “Clustering Sensors in Wireless ad hoc Networks using a Dynamic Expected Coverage Model.” (co-advised with Rajan Batta). Entrepreneur at Dipesh Engineering Works, Mumbai India.
- Nishant Mishra: MS 8/03. “Capacity and Non-steady state Generalizations to the Dynamic MEXCLP model for Distributed Sensing Networks.” (co-advised with Rajan Batta). Currently pursuing PhD in London Business School.
- Esra Cosar: MS 7/05. “Performance Evaluation of a Mathematical Programming-based Clustering Algorithm for a Wireless Ad Hoc Networks Operating in a Threat Environment.” (co-advised with Rajan Batta). Currently Operations Research Analyst at ZS Associates, New York, NY.
Papers and Talks
- Patel, D., Batta, R. and Nagi, R. “Clustering sensors in wireless ad hoc networks operating in a threat environment,” acceptedOperations Research, 2003.
- Joshi, A., Batta, R. and Nagi, R. “Two Tactical Models for Clustering Sensors in Wireless Ad Hoc Sensor Networks Operating in a Threat Environment,” submitted Computers & Operations Research, 2006 PDF (914k).
- Joshi, A., Batta, R. and Nagi, R. “Enemy Track Based Threat Assessment in Distributed Sensing Networks,” submitted to Military Operations Research, September 2005. PDF (1,932k).
- Patel, D. “Clustering sensors in wireless ad hoc networks using dynamic expected coverage model,” MS Thesis, Department of Industrial Engineering, University at Buffalo, 2003 PDF (845k).
- Mishra, N. “Capacity and Non-steady state Generalizations to the Dynamic MEXCLP model for Distributed Sensing Networks,” MS Thesis, Department of Industrial Engineering, University at Buffalo, 2003 PDF (914k).
- Cosar, E. “Performance Evaluation of a Mathematical Programming Based Clustering Algorithm for a Wireless Ad Hoc Network Operating in a Threat Environment,” MS Thesis, Department of Industrial Engineering, University at Buffalo, 2005 (draft) PDF (605k).
- Joshi, A., Batta, R. and Nagi, R., “Enemy Track Based Threat Evaluation for Military Sensor/Fusion Networks,” presentation in the INFORMS Fall 2005 Conference, San Francisco CA, November 2005.
- Joshi, A., Mishra, N., Batta, R. and Nagi, R., “Ad hoc Sensor Network Topology Design for Distributed Fusion: A Mathematical Programming Approach,” 7th International Conference on Information Fusion, Stockholm, Sweden, June 2004.
- Patel, D., Batta, R. and Nagi, R., “Cluster Head (Re)Assignment in Ad Hoc Sensor Networks to Maximize Coverage,” presentation in the INFORMS Fall 2002 Conference, San Jose CA, November 2002. PDF (330k).
- An illustrative example here Illustrative Example.xls demonstrates the change in coverage due to change in threat level p. Please go to “Tools” in MS Excel and select “Add-Ins” and check “Solver Add-in”. Next go to “Tools” and select “Solver” to solve the model. You can change the threat probability p (between 0 and 1) in cell S189 and re-run the model to study coverage behavior.
- Example Data for . Excel File (330k).