BPEC：无线传感器网络中一种能量感知的分布式分簇算法

BPEC:An Energy-Aware Distributed Clustering Algorithm in WSNs

无线传感器网络的大面积铺设以及数据融合的需求,促使必须有效地组织网络的拓扑结构,以达到均衡负载、延长网络的生命周期的目标.分簇已被证实是将网络组织成层次相连结构的有效方式.提出了一种新的以邻居节点的平均剩余能量与节点本身的剩余能量的比值作为竞争簇头的主要参数,以节点的"度"作为节点竞争簇头辅助参数的节能分布式分簇算法BPEC.如果执行BPEC算法,整个网络的广播消息量复杂度为O(n),整个网络的时间复杂度为O(1).证明了由BPEC算法产生的簇头集合是一个最大独立集,簇头集合能覆盖网络的所有节点.当节点足够多时,仿真实验结果表明,簇头集合的尺寸大小与理论推导值十分接近.

The large-scale deployment of wireless sensor networks and the need for data aggregation necessitate efficient organization of the network topology for the purpose of balancing the load and prolonging the network lifetime. Clustering has proved to be an effective approach for organizing the network into a connected hierarchy. In this paper, a distributed energy saving clustering algorithm BPEC is proposed. Cluster-heads are elected by two probabilities. The primary probability is based on the ratio between the average residual energy of neighbor nodes and the node itself residual energy. The subsidiary probability is the node＇s degree. By using BPEC algorithm, the complexity of the entire network broadcasting is O（n）, and the complexity of the entire network computing is O（1）. It is proved that the cluster head set C by BPEC clustering algorithm is the dominating set of wireless sensor networks G（V,E）. It is derived theoretically that the cluster head number of set C has a clear upper and lower bounds. The cluster head set generated by BPEC is proved to be a maximum independent set, which can cover all network nodes. Simulation experiments show that when the network has higher communication coverage density, analysis results and experimental results are very close, which shows that the cluster number of BPEC clustering algorithm is identical to the theoretical value.