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

doi:10.3724/SP.J.1087.2012.01499

Journal of Computer Applications ›› 2012, Vol. 32 ›› Issue (06): 1499-1502.DOI: 10.3724/SP.J.1087.2012.01499

• Network and communications • Previous Articles Next Articles

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

JIANG Ai-lian¹,YANG Xing-tong¹,Wu Weili²

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

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

降爱莲¹,杨兴彤¹,Wu Weili²

1. 太原理工大学计算机科学与技术学院，太原 030024
2. Department of Computer Science and Technology, University of Texas at Dallas, Dallas Texas 70085, USA

通讯作者: 降爱莲
作者简介:降爱莲（1969-），女，山西太原人，副教授，博士，主要研究方向:无线自组织网络、近似算法设计与分析；〓杨兴彤（1988-），男，山东泰安人，硕士研究生，主要研究方向：算法设计与分析、机器学习;〓WU Weili（1968-），女，美籍华人，副教授，博士，主要研究方向:近似算法设计与分析、数据挖掘与知识发现。
基金资助:
山西省回国留学人员科研资助项目;山西省高等学校留学回国人员科研资助项目

Abstract

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

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

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

CLC Number:

TP393

JIANG Ai-lian YANG Xing-tong Wu Weili. Heuristic algorithm for minimum energy multicast in Ad Hoc networks with multi-radio multi-channel adaptive antennas[J]. Journal of Computer Applications, 2012, 32(06): 1499-1502.

降爱莲杨兴彤 Wu Weili. 多射频多信道自适应波束天线自组网最小化能量组播启发式算法[J]. 计算机应用, 2012, 32(06): 1499-1502.

[1]	Xinming GUO, Rui LIU, Fei XIE, Deyu LIN. β-QoM target-barrier coverage construction algorithm for wireless visual sensor network [J]. Journal of Computer Applications, 2023, 43(9): 2877-2884.
[2]	Zhihui GAO, Meng HAN, Shujuan LIU, Ang LI, Dongliang MU. Survey of high utility itemset mining methods based on intelligent optimization algorithm [J]. Journal of Computer Applications, 2023, 43(6): 1676-1686.
[3]	Zhihao XIAO, Zhihua HU, Lin ZHU. Hybrid adaptive large neighborhood search algorithm for solving time-dependent vehicle routing problem in cold chain logistics [J]. Journal of Computer Applications, 2022, 42(9): 2926-2935.
[4]	Xinming ZHANG, Shaochen WEN, Shangwang LIU. Differential disturbed heap-based optimizer [J]. Journal of Computer Applications, 2022, 42(8): 2519-2527.
[5]	Jie YANG, Mingyang ZHANG, Xiaobin RUI, Zhixiao WANG. Influence maximization algorithm based on node coverage and structural hole [J]. Journal of Computer Applications, 2022, 42(4): 1155-1161.
[6]	WEI Qianqian, DONG Xingye, WANG Huanzheng. Modeling of dyeing vat scheduling and slide time window scheduling heuristic algorithm [J]. Journal of Computer Applications, 2020, 40(1): 292-298.
[7]	ZHANG Xianli, TANG Jianxin, CAO Laicheng. Influence maximization algorithm based on reverse PageRank [J]. Journal of Computer Applications, 2020, 40(1): 96-102.
[8]	WU Bin, WANG Chao, DONG Min. Hybrid fruit fly optimization algorithm for field service scheduling problem [J]. Journal of Computer Applications, 2018, 38(9): 2706-2711.
[9]	LIANG Lidong, JIA Wenyou. Heuristic packing algorithm based on forbearing stratified strategy [J]. Journal of Computer Applications, 2018, 38(4): 1195-1200.
[10]	CHEN Chuang, Ryad CHELLALI, XING Yin. Improved grey wolf optimizer algorithm using dynamic weighting and probabilistic disturbance strategy [J]. Journal of Computer Applications, 2017, 37(12): 3493-3497.
[11]	XU Dayu, LIU Renping. Improved self-organized criticality optimized gray wolf optimizer metaheuristic algorithm [J]. Journal of Computer Applications, 2016, 36(6): 1588-1593.
[12]	XIONG Fang, ZHANG Xianyong. Regional attribute reduction and their structural heuristic algorithms for variable precision rough sets [J]. Journal of Computer Applications, 2016, 36(11): 2954-2957.
[13]	XIANG Ting, PAN Dazhi. Clustering algorithm for split delivery vehicle routing problem [J]. Journal of Computer Applications, 2016, 36(11): 3141-3145.
[14]	CHEN Juan. Heuristic anti-monitoring path finding algorithm based on local Voronoi tessellation in sensory field [J]. Journal of Computer Applications, 2015, 35(1): 15-18.
[15]	WANG Yong, XU Dongchuan, NONG Lanjing. Research of location-routing problem in emergency logistics system for post-earthquake transitional stage [J]. Journal of Computer Applications, 2015, 35(1): 243-246.

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

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics