Date Added: Oct 2012
In Wireless Sensors Networks (WSNs) the efficient use of the sensors' energy is a key point to extend the network lifetime and has been the center of attention by many researchers. Clustering formation is an important technique used to reduce the sensor's energy consumption. However, finding an optimal clustering in WSNs is a NP-Hard problem, thus efficient heuristics are needed to find good clustering in reasonable time. In this paper the authors propose and analyze a Greedy Randomized Adaptive Search Procedure (GRASP) coupled with Path Relinking intensification to obtain near-optimal clustering. They develop a clustering protocol to simulate the clusters formation and data transmission.