摘要
针对分簇算法中的重新分簇所带来的高负载问题,提出了一种基于完全图的能量有效的分簇算法(CGCA).系统启动时刻,CGCA把网络划分成多个完全图,每个完全图独立成簇.CGCA利用完全图中节点之间是等价的性质,只是在系统启动的时刻执行分簇算法,而在以后的重新选举簇头阶段,簇头只需要在每个簇的内部节点间进行轮换,而不是像以前的分簇算法需要进行全局性的触发来选举簇头,这使得CGCA的通信和计算负载可以大量减少,它在单个节点的处理复杂度和消息复杂度均为O(1).另外,通过优先选择距离簇头近的节点加入簇内,CGCA不仅减少了簇头和簇内成员的簇内通信能量,而且使得簇头比较均匀地分布在部署区域.仿真实验表明:在节点密集部署的情况下,CGCA产生的消息交换个数远小于HEED分簇算法.最后在簇头均匀分布方面,CGCA也明显优于LEACH分簇算法.
Aiming to address the high overload problem in the re-clustering process in the clustering algorithm,an energy efficient,complete graph-based clustering algorithm is proposed（CGCA）.CGCA is employed to divide the network into a few complete graphs at the system activation time,each complete graph independently being a cluster.By using the property that the nodes are of equivalence each other in a complete graph,CGCA is only executed at the system activation time and the cluster head role needs only to be rotated among the internal nodes in each cluster at the subsequent re-clustering phase,while the previous clustering algorithms need a global trigger to re-elect cluster heads,which incurs greatly reduced communication and computation overheads.CGCA achieves a process and message complexity of O（1） at each node.Moreover,the preferred selection of nodes close to cluster heads into the cluster,not only reduces the intra-cluster communication energy of cluster heads and their inner cluster members,but leads to the even distribution of cluster heads in the deployment region.The simulation experiments demonstrate that the number of exchanged message produced by CGCA is much less than that of HEED clustering algorithm in the densely deployed case.Finally,CGCA significantly outperforms LEACH algorithm in terms of evenly distributing cluster heads.
出处
《计算机研究与发展》
EI
CSCD
北大核心
2008年第7期1106-1114,共9页
Journal of Computer Research and Development
基金
国家“九七三”重点基础研究发展规划基金项目(2006CB303006)
关键词
传感器网络
分簇算法
拓扑控制
完全图
能量有效性
sensor networks
clustering algorithm
topology control
complete graph
energy efficiency
