计算机应用 ›› 2012, Vol. 32 ›› Issue (06): 1499-1502.DOI: 10.3724/SP.J.1087.2012.01499

• 网络与通信 • 上一篇    下一篇

多射频多信道自适应波束天线自组网最小化能量组播启发式算法

降爱莲1,杨兴彤1,Wu Weili2   

  1. 1. 太原理工大学 计算机科学与技术学院,太原 030024
    2. Department of Computer Science and Technology, University of Texas at Dallas, Dallas Texas 70085, USA
  • 收稿日期:2011-11-07 修回日期:2012-02-27 发布日期:2012-06-04 出版日期:2012-06-01
  • 通讯作者: 降爱莲
  • 作者简介:降爱莲(1969-),女,山西太原人,副教授,博士,主要研究方向:无线自组织网络、近似算法设计与分析;〓杨兴彤(1988-),男,山东泰安人,硕士研究生,主要研究方向:算法设计与分析、机器学习;〓WU Weili(1968-),女,美籍华人,副教授,博士,主要研究方向:近似算法设计与分析、数据挖掘与知识发现。
  • 基金资助:
    山西省回国留学人员科研资助项目;山西省高等学校留学回国人员科研资助项目

Heuristic algorithm for minimum energy multicast in Ad Hoc networks with multi-radio multi-channel adaptive antennas

JIANG Ai-lian1,YANG Xing-tong1,Wu Weili2   

  1. 1. College of Computer Science and Technology, Taiyuan University of Technology, Taiyuan Shanxi 030024,China
    2. Department of Computer Science and Technology, University of Texas at Dallas, Dallas Texas 70085, USA
  • Received:2011-11-07 Revised:2012-02-27 Online:2012-06-04 Published:2012-06-01
  • Contact: JIANG Ai-lian

摘要: 为解决能量约束的无线自组网最小化能量组播问题,建立了多射频多信道自适应波束天线方式(MR-MCAAs)实现的多波束天线通信模型,进而给出MR-MCAAs多波束天线自组网最小化能量组播问题的形式化定义,然后提出解决该NP-难问题的一个启发式算法。该算法提出两种可能的波束重新分配策略以优化每个节点的波束分配和波束发射方案,并构建基于MR-MCAAs多波束天线的最小化能量组播树。该算法的时间复杂度是O(n3logn),其中n表示网络中的节点数。仿真结果表明:与单波束定向天线相比,2-波束天线最小化组播总能耗减少了59%~72%。

关键词: 多射频多信道, NP-难问题, 启发式算法, 无线自组网

Abstract: To solve the problem of minimum energy multicast in energy-constraint wireless Ad hoc networks, the communication model of MR-MCAAs multi-beam antennas was constructed, and the formal definition of the problem of the minimum energy multicast with MR-MCAAs multi-beam antennas was given, and then proposed a heuristic algorithm for this NP-hard problem. The algorithm proposed the two possible strategies for beam reassignment to optimize the scheme of the beam assignment and beam transmitting of every node, and constructed the minimum energy multicast tree with MR-MCAAs multi-beam antennas. The algorithm has the time complexity of O(n3logn), where n denotes the number of nodes in the networks. The simulations show that the energy consumption of minimum energy multicast with 2–beam antennas reduced by 65~75 percent compared with the single beam directional antennas.

Key words: Multi-Radio Multi-Channel (MR-MC), NP-hard problem, heuristic algorithm, wireless Ad Hoc network

中图分类号: