2nd International ICST Conference on Performance Evaluation Methodologies and Tools

Research Article

Optimal Cluster-head Deployment in Wireless Sensor Networks with Redundant Link Requirements

Download245 downloads
  • @INPROCEEDINGS{10.4108/valuetools.2007.1953,
        author={Xu Ning and Christos G. Cassandras},
        title={Optimal Cluster-head Deployment in Wireless Sensor Networks with Redundant Link Requirements},
        proceedings={2nd International ICST Conference on Performance Evaluation Methodologies and Tools},
        proceedings_a={VALUETOOLS},
        year={2010},
        month={5},
        keywords={Wireless Sensor Network Clustering Facility Location},
        doi={10.4108/valuetools.2007.1953}
    }
    
  • Xu Ning
    Christos G. Cassandras
    Year: 2010
    Optimal Cluster-head Deployment in Wireless Sensor Networks with Redundant Link Requirements
    VALUETOOLS
    ICST
    DOI: 10.4108/valuetools.2007.1953
Xu Ning1,*, Christos G. Cassandras1,*
  • 1: Department of Manufacturing Engineering and Center for Information and Systems Engineering Boston University Brookline, MA 02446, USA
*Contact email: nx@bu.edu, cgc@bu.edu

Abstract

In this paper, a Wireless Sensor Network (WSN) deployment problem is posed: in a two-level heterogeneous WSN, we need to optimally determine the location of cluster-heads in order to minimize communication power. We require that each sensor node connects to at least p cluster-heads for reliability, and each cluster-head can accept at most q connections. The optimization problem in formulated as a Mixed Integer Nonlinear Programming (MINLP) problem. To overcome the fact that a MINLP solver fails to solve large-scale cases or obtain a global optimum, we propose an iterative decomposition algorithm and use a randomized multi-start technique for global optimization. We also propose an incremental deployment approach and use it to solve the original problem as if the WSN is built incrementally. Numerical results show that the decomposition algorithm is very efficient. While the incremental deployment method is slower in each run, it produces a better solution distribution compared to the pure multi-start approach. Both, however, are capable of solving large-scale problems.