This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Patel, D. J. Articles by Nagi, R. Search for Related Content

Clustering Sensors in Wireless Ad Hoc Networks Operating in a Threat Environment

Department of Industrial Engineering and Center for Multisource Information Fusion, University at Buffalo (SUNY), 342 Bell Hall, Buffalo, New York 14260
Department of Industrial Engineering and Center for Multisource Information Fusion, University at Buffalo (SUNY), 342 Bell Hall, Buffalo, New York 14260
Department of Industrial Engineering and Center for Multisource Information Fusion, University at Buffalo (SUNY), 342 Bell Hall, Buffalo, New York 14260
dipjpatel{at}yahoo.com
batta{at}eng.buffalo.edu
nagi{at}buffalo.edu

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.

Subject classifications: wireless ad hoc networks; military applications; maximal expected coverage.
History: Received December 2002; revision received March 2004; accepted March 2004.