University at Buffalo, The State University of New York
Rakesh Nagi
Home Biography Research Teaching Professional Activities

Home

Biography

Research

Information Fusion

Congestion in Facilities Location and Layout

Facility Layout (Re)Design

Agile Manufacturing

Real-Time Visualization

Sensor Networks

Facilities Design and Cellular Manufacturing

Operations of Production Systems

Variant Design

Teaching

IE 684: Networks, Routing, and Logistics

IE 661: Scheduling Theory

IE 620: Agile Manufacturing

IE 505: Production Planning and Control

IE 504: Facilities Design

IE 500: Special Topics: Logistics and Supply-Chain Management

IE 327: Facilities Design

IE 320: Engineering Economy

Professional Activities


NTA/Rosettex National Imagery and Mapping Agency (NIMA)

Clustering sensors in wireless ad hoc networks

Description
Press Coverage
Objectives
Personnel
Papers and Talks

Description

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.


Click for Larger Image


Press Coverage

UB news services
Newswise 2/2/04
Science NewsFactor
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


Objectives

  • 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.
Personnel

Investigators:
Dr. Rakesh Nagi, Professor
Department of Industrial Engineering
State University of New York at Buffalo
420 Bell Hall
Buffalo, NY 14260-2050
U.S.A.
Telephone: (716) 645-2357
FAX: (716) 645-3302
E-mail: nagi@buffalo.edu

Dr. Rajan Batta, Professor
Department of Industrial Engineering
State University of New York at Buffalo
420 Bell Hall
Buffalo, NY 14260-2050
U.S.A.
Telephone: (716) 645-2357
FAX: (716) 645-3302
E-mail: batta@eng.buffalo.edu

Graduate Students:
  • 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

Papers:

Journal Papers:
  • Patel, D., Batta, R. and Nagi, R. "Clustering sensors in wireless ad hoc networks operating in a threat environment," accepted Operations 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).
Theses:
  • 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).

Talks:
  • 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).

Example Data:
  • 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).

Contact information: Phone: (716) 645-2427 • Fax: (716) 645-3302 • E-mail: nagi@buffalo.edu

Copyright 2003, University at Buffalo, All rights reserved.