求解无线传感器网络路由问题的蚁群最优化算法及其收敛性

ANT COLONY OPTIMIZATION ALGORITHM AND ITS CONVERGENCE FOR WIRELESS SENSOR NETWORK ROUTING PROBLEM

首先将无线传感器网络的路由问题转化成求解最小Steiner树问题,然后给出了求解无线传感器网络路由的蚁群优化算法,并对算法的收敛性进行了证明．最后对找到最优解后信息素值的变化进行了分析．即在限制信息素取值的条件下,当迭代次数充分大时,该算法能以任意接近于1的概率找到最优解,并且当最优解找到后,最优树边上的信息素单调增加,而最优解以外边上的信息素在有限步达到最小值．

In this paper, the Steiner tree model for the wireless sensor network routing is first proposed, then an ant colony optimization algorithm and its convergence proof for solving the minimal Steiner tree model is presented and finally changes of the pheromone trails after an optimal solution has been found and analysised. In particularly, it is shown that under condition of constraint of pheromone trails, the probability of finding an optimal solution tends the to 1 for sufficiently large number of iterations. And after an optimal solution has been found, the pheromone trails associated to the optimal solution monotonically increase to reach the maximum value while others pheromone trails reach the minimum one in finite iterations.