使用定向天线的无线自组网中基于粒子群优化的最大生命期广播树构造算法

Maximum lifetime broadcast tree construction algorithm based on particle swarm optimization in wireless ad hoc networks using directional antennas

针对无线自组网中在使用单波束定向天线情况下的最大生命期广播路由问题,提出一个基于粒子群优化的最大生命期广播树构造算法.在该算法中,粒子位置表示一棵广播树,粒子适应度值为粒子位置所表示的广播树的生命期.该算法在粒子群执行搜索的过程中采用多种措施提高求解质量和效率.在更新粒子位置时对新粒子位置进行限制以保证节点的生命期不低于某个阈值.利用EPUS-PSO的粒子群体管理策略根据解的搜索状态动态地增减粒子,利用EPUS-PSO的解信息共享策略使每个粒子可以共享其他粒子的个体极值点.采用一种迭代改进广播树生命期的启发式算法对粒子位置进行局部优化.同时,使用阻尼边界条件对粒子越界进行处理.仿真实验结果表明所提算法可以有效地增加广播生命期.

To solve the maximum lifetime broadcast routing problem in wireless ad hoc networks where each node is equipped with single-beam directional antennas,a maximum-lifetime broadcast tree construction algorithm based on particle swarm optimization is proposed.In this algorithm,each particle position represents a broadcast tree,and the particle fitness is the lifetime of the broadcast tree represented by the particle position.During the searching process of the particle swarm,a number of measures are adopted to improve the solving quality and efficiency.When each particle＇s position is updated,the new position of each particle is constrained so that each node＇s lifetime is not less than a threshold.The particle population management strategy of the EPUS-PSO（efficient population utilization strategy for particle swarm optimization） is used,therefore some new particles can be added into the swarm or some existing particles can be excluded from the swarm according to the solution-searching status.The solution-sharing strategy of the EPUS-PSO is used,therefore each particle can share other particles＇ personal best positions.The heuristic algorithm which iteratively improves the lifetime of a broadcast tree is adopted to locally optimize the particle position.Meanwhile,the damping boundary condition is used to deal with every particle＇s boundary violation.The results of the simulation experiments show that the proposed approach can effectively increase the broadcast lifetime.