[1]沈军,朱晓建.使用定向天线的无线自组网中基于粒子群优化的最大生命期广播树构造算法[J].东南大学学报(自然科学版),2013,43(2):279-285.[doi:10.3969/j.issn.1001-0505.2013.02.010]
 Shen Jun,Zhu Xiaojian.Maximum lifetime broadcast tree construction algorithm based on particle swarm optimization in wireless ad hoc networks using directional antennas[J].Journal of Southeast University (Natural Science Edition),2013,43(2):279-285.[doi:10.3969/j.issn.1001-0505.2013.02.010]
点击复制

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

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
43
期数:
2013年第2期
页码:
279-285
栏目:
计算机科学与工程
出版日期:
2013-03-20

文章信息/Info

Title:
Maximum lifetime broadcast tree construction algorithm based on particle swarm optimization in wireless ad hoc networks using directional antennas
作者:
沈军朱晓建
东南大学计算机科学与工程学院, 南京 211189
Author(s):
Shen Jun Zhu Xiaojian
School of Computer Science and Engineering, Southeast University, Nanjing 211189, China
关键词:
无线自组网 广播树 最大生命期 粒子群优化 定向天线
Keywords:
wireless ad hoc networks broadcast tree maximum lifetime particle swarm optimization directional antennas
分类号:
TP393
DOI:
10.3969/j.issn.1001-0505.2013.02.010
摘要:
针对无线自组网中在使用单波束定向天线情况下的最大生命期广播路由问题,提出一个基于粒子群优化的最大生命期广播树构造算法.在该算法中,粒子位置表示一棵广播树,粒子适应度值为粒子位置所表示的广播树的生命期.该算法在粒子群执行搜索的过程中采用多种措施提高求解质量和效率.在更新粒子位置时对新粒子位置进行限制以保证节点的生命期不低于某个阈值.利用EPUS-PSO的粒子群体管理策略根据解的搜索状态动态地增减粒子,利用EPUS-PSO的解信息共享策略使每个粒子可以共享其他粒子的个体极值点.采用一种迭代改进广播树生命期的启发式算法对粒子位置进行局部优化.同时,使用阻尼边界条件对粒子越界进行处理.仿真实验结果表明所提算法可以有效地增加广播生命期.
Abstract:
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.

参考文献/References:

[1] 李政,李德英. 无线自组织网络中能量有效的广播与组播[J]. 软件学报,2010,21(8): 2023-2036.
  Li Zheng, Li Deying. Energy-efficient broadcast and multicast in wireless ad hoc networks [J]. Journal of Software, 2010, 21(8): 2023-2036.(in Chinese)
[2] Das A K, Marks R J, El-Sharkawi M, et al. MDLT: a polynomial time optimal algorithm for maximization of time-to-first-failure in energy constrained wireless broadcast networks [C]//Proceedings of the IEEE Global Telecommunications Conference. San Francisco, California, USA, 2003: 362-366.
[3] Kang I, Poovendran R. Maximizing static network lifetime of wireless broadcast ad hoc networks [C]//Proceedings of the IEEE International Conference on Communications. Anchorage, Alaska, USA, 2003: 2256-2261.
[4] Hou Y T, Shi Y, Sherali H D, et al. Multicast communications in ad hoc networks using directional antennas: a lifetime-centric approach [J]. IEEE Transactions on Vehicular Technology, 2007, 56(3): 1333-1344.
[5] Wieselthier J E, Nguyen G D, Ephremides A. Energy-aware wireless networking with directional antennas: the case of session-based broadcasting and multicasting [J]. IEEE Transactions on Mobile Computing, 2002, 1(3): 176-191.
[6] Guo S, Yang O. Formulation of optimal tree construction for maximum lifetime multicasting in wireless ad-hoc networks with adaptive antennas [C]//Proceedings of the IEEE International Conference on Communications. Seoul, Korea, 2005: 3370-3374.
[7] Guo S, Yang O. Multicast lifetime maximization for energy-constrained wireless ad-hoc networks with directional antennas [C]//Proceedings of the IEEE Global Telecommunications Conference. Dallas, Texas, USA, 2004: 4120-4124.
[8] Guo S, Leung V C M, Yang O W W. Distributed multicast algorithms for lifetime maximization in wireless ad hoc networks with omni-directional and directional antennas [C]//Proceedings of the IEEE Global Telecommunications Conference. San Francisco, California, USA, 2006: 4151642.
[9] Guo S, Yang O, Leung V. Approximation algorithms for longest-lived directional multicast communications in WANETs [C]//Proceedings of the 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing. Montreal, Quebec, Canada, 2007: 190-198.
[10] Guo S, Leung V, Jiang X. Distributed approximation algorithms for longest-lived multicast in WANETs with directional antennas [J]. IEEE Transactions on Wireless Communications, 2010, 9(7): 2227-2237.
[11] 朱晓建,沈军. 基于粒子群优化的ad hoc网络最小能耗多播路由算法[J]. 通信学报,2012,33(3):52-58.
  Zhu Xiaojian, Shen Jun. Minimum energy consumption multicast routing in ad hoc networks based on particle swarm optimization [J]. Journal on Communications, 2012, 33(3): 52-58.(in Chinese)
[12] Hsiao P C, Chiang T C, Fu L C. Particle swarm optimization for the minimum energy broadcast problem in wireless ad-hoc networks [C]//Proceedings of the IEEE Congress on Evolutionary Computation. Brisbane, Australia, 2012: 6252949.
[13] 王楷. 基于粒子群优化的Ad Hoc网络多播路由研究[D]. 武汉:华中师范大学计算机科学系,2007.
[14] Huang T, Mohan A S. A hybrid boundary condition for robust particle swarm optimization [J]. IEEE Antennas and Wireless Propagation Letters, 2005, 4: 112-117.
[15] Xu S, Rahmat-Samii Y. Boundary conditions in particle swarm optimization revisited [J]. IEEE Transactions on Antennas and Propagation, 2007, 55(3): 760-765.
[16] Hsieh S T, Sun T Y, Liu C C, et al. Efficient population utilization strategy for particle swarm optimizer [J]. IEEE Transactions on Systems, Man, and Cybernetics—Part B: Cybernetics, 2009, 39(2): 444-456.
[17] Kennedy J, Eberhart R. Particle swarm optimization [C]//Proceedings of the IEEE International Conference on Neural Networks. Perth, Australia, 1995: 1942-1948.
[18] Eberhart R, Kennedy J. A new optimizer using particle swarm theory [C]//Proceedings of the Sixth International Symposium on Micro Machine and Human Science. Nagoya, Japan, 1995: 39-43.
[19] Robinson J, Rahmat-Samii Y. Particle swarm optimization in electromagnetics [J]. IEEE Transactions on Antennas and Propagation, 2004, 52(2): 397-407.
[20] Shi Y, Eberhart R. A modified particle swarm optimizer [C]//Proceedings of the IEEE International Conference on Evolutionary Computation. Anchorage, Alaska, USA, 1998: 69-73.
[21] Salman A, Ahmad I, Al-Madani S. Particle swarm optimization for task assignment problem [J]. Microprocessors and Microsystems, 2002, 26(8): 363-371.
[22] Liu X, Su J, Han Y. An improved particle swarm optimization for traveling salesman problem [C]//Proceedings of the 3rd International Conference on Intelligent Computing. Qingdao, China, 2007: 803-812.

备注/Memo

备注/Memo:
作者简介: 沈军(1963—),男,博士,教授,博士生导师,junshen@seu.edu.cn.
基金项目: 国家重点基础研究发展计划(973计划)资助项目(2009CB320501).
引文格式: 沈军,朱晓建.使用定向天线的无线自组网中基于粒子群优化的最大生命期广播树构造算法[J].东南大学学报:自然科学版,2013,43(2):279-285. [doi:10.3969/j.issn.1001-0505.2013.02.010]
更新日期/Last Update: 2013-03-20