Cluster-based self-organization scheme is attracting tremendous research interest in the studies of the wireless sensor networks (WSN), because it meets the critical runtime requirement of the WSN based applications: working in self-organized and energy efficient way. Whereas, an important problem in the cluster scheme remains seldom studied, that the cluster heads depletes energy very fast and the rotation strategy of the cluster head is needed to prolong the system?s lifetime.

In this paper, the cluster head rotation problem is studied with the dynamic programming method. An energy first cluster head rotation strategy is proposed and is proved to be the optimal in the means of the cluster lifetime. Further, the upper bound and the lower bound of the cluster lifetime are derived based on the Law of Conservation of Energy. We show that the optimal strategy is not unique, which can be accomplished in different ways. Based on the analysis, a practical, LEast-rotation, Near-Optimal cluster head rotation algorithm (LENO) is proposed to practice the inner cluster rotation. The validity of LENO is verified with the node level simulation tool PowerTOSSIM. Near optimal cluster lifetime is obtained as desired, which is much better than the performances of Leach and EDAC etc.