Efficient Load-Balanced Clustering Algorithms for wireless sensor networks

Wireless sensor networks have been receiving increasing attention in recent years due to their potential applications in the establishment of dynamic communications for emergency/rescue operations, disaster relief efforts, and military networks. In this paper, we investigate the problem of grouping...

Full description

Saved in:
Bibliographic Details
Published in:Computer communications 2008-03, Vol.31 (4), p.750-759
Main Authors: Low, Chor Ping, Fang, Can, Ng, Jim Mee, Ang, Yew Hock
Format: Article
Language:English
Subjects:
Clustering
Load balancing
NP-hard approximation algorithm
Wireless sensor networks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Wireless sensor networks have been receiving increasing attention in recent years due to their potential applications in the establishment of dynamic communications for emergency/rescue operations, disaster relief efforts, and military networks. In this paper, we investigate the problem of grouping the sensor nodes into clusters to enhance the overall scalability of the network. A selected set of nodes, known as gateway nodes, will act as cluster-heads for each cluster and the objective is to balance the load among these gateways. Load-Balanced Clustering increases system stability and improves the communication between the various nodes in the network. We call the problem addressed in this paper as the Load-Balanced Clustering Problem ( LBCP). We first show that a special case of LBCP (whereby the traffic load contributed by all sensor nodes are the same) is optimally solvable in polynomial time. We next prove that the general case of LBCP is NP-hard. We then proposed an efficient 3 2 -approximation algorithm for the problem.
ISSN:0140-3664
1873-703X
DOI:10.1016/j.comcom.2007.10.020