Abstract: Node deployment is one of the important problems in Wireless Sensor Network (WSN). Concerning the problem of energy hole in the process of node employment, a Node Redeployment Based on the Firefly Algorithm (NRBFA) strategy was proposed. Firstly, the k-means algorithm was used to cluster nodes and the redundant nodes were introduced into the sensor network where nodes are randomly deployed. Then, the Firefly Algorithm (FA) was used to move the redundant nodes to share the load of Cluster Heads (CHs) and balance the energy consumption of nodes in the network. Finally, the redundant nodes were updated after finding the target node by reusing the FA. In the proposed strategy, the reduction of moving distances of nodes and the decrease of the network energy consumption were achieved through moving the redundant nodes effectively. Experimental results show that the proposed strategy can alleviate the "energy hole" problem effectively. Compared with the partition node redeployment algorithm based on virtual force, the proposed strategy reduces the complexity of the algorithm, and can better improve the energy efficiency of the network, balance the network load, as well as prolong the network lifetime by nearly 10 times.

Key words: Wireless Sensor Network (WSN), energy hole, energy consumption balance, node redeployment, redundant node, Firefly Algorithm (FA)

摘要： 节点部署是无线传感器网络研究的重要问题之一。针对节点部署过程中的能量空洞问题，提出了一种基于萤火虫算法（FA）的节点重部署（NRBFA）策略。首先，在节点随机部署的传感器网络中，利用k-means算法进行分簇并引入冗余节点；然后，利用FA移动冗余节点，以分担簇头（CH）负载并均衡网络中节点的能耗；最后，再次利用FA寻找目标节点，从而更新冗余节点。该策略通过有效地移动冗余节点，减小了节点移动距离并降低了网络能耗。实验结果表明，该策略能够有效地缓解“能量空洞”问题，并且与基于虚拟力的分区节点重部署算法相比降低了算法的复杂性，且能更好地提高网络的能量效率，均衡网络负载，并将网络生命周期延长近10倍。

关键词: 无线传感器网络, 能量空洞, 能耗均衡, 节点重部署, 冗余节点, 萤火虫算法