3rd International IEEE/CreateNet Workshop on Broadband Advanced Sensor Networks

Research Article

Optimal Load Balanced Clustering in Two-Tiered Sensor Networks

  • @INPROCEEDINGS{10.1109/BROADNETS.2006.4374424,
        author={Ataul Bari and Arunita Jaekel and Subir Bandyopadhyay},
        title={Optimal Load Balanced Clustering in Two-Tiered Sensor Networks},
        proceedings={3rd International IEEE/CreateNet Workshop on Broadband Advanced Sensor Networks},
        publisher={IEEE},
        proceedings_a={BASENETS},
        year={2006},
        month={10},
        keywords={},
        doi={10.1109/BROADNETS.2006.4374424}
    }
    
  • Ataul Bari
    Arunita Jaekel
    Subir Bandyopadhyay
    Year: 2006
    Optimal Load Balanced Clustering in Two-Tiered Sensor Networks
    BASENETS
    IEEE
    DOI: 10.1109/BROADNETS.2006.4374424
Ataul Bari1,*, Arunita Jaekel1,*, Subir Bandyopadhyay1,*
  • 1: School of Computer Science, University of Windsor, 401 Sunset Ave., Windsor, ON N9B 3P4, Canada
*Contact email: bari1@uwindsor.ca, arunita@uwindsor.ca, subir@uwindsor.ca

Abstract

In hierarchical sensor networks, sensor nodes are arranged in clusters, and higher-powered relay nodes can be used as cluster heads. The scalability and the lifetime of sensor networks are affected by the limited transmission range and battery power of the nodes. Proper techniques for assigning sensor nodes to clusters have been shown to improve the lifetime of the network. Previous approaches to clustering focus on different heuristics to achieve load balancing. In this paper, we have proposed two fast and efficient integer linear program (ILP) formulations for assigning sensor nodes to clusters in a two-tiered network, where the relay nodes are used as cluster heads. The first is for single hop routing and the second is a generalized formulation that can be used with any multi-hop routing strategy. The objective, in both cases, is to maximize the lifetime of the relay node network. We have tested our formulations with a number of different routing strategies, and for each case, we have compared our formulation to several existing heuristics for clustering. The results demonstrate that our ILP's consistently outperform the heuristics and are fast enough to be used for practical networks with hundreds of sensor nodes.