Clustering sensors in wireless ad hoc networks operating in a threat environment

Dipesh J. Patel, Rajan Batta, Rakesh Nagi

Research output: Contribution to journalReview articlepeer-review


Sensors in a data fusion environment over hostile territory are geographically dispersed and change location with time. 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 discussed.

Original languageEnglish (US)
Pages (from-to)432-442
Number of pages11
JournalOperations Research
Issue number3
StatePublished - May 2005
Externally publishedYes


  • Maximal expected coverage
  • Military applications
  • Wireless ad hoc networks

ASJC Scopus subject areas

  • Computer Science Applications
  • Management Science and Operations Research


Dive into the research topics of 'Clustering sensors in wireless ad hoc networks operating in a threat environment'. Together they form a unique fingerprint.

Cite this