Journal of Computer Applications
计算机应用,
2012
,
32(6):1499
一
1502
ISSN 1001-9081
CODEN JYIIDU
2012-06-01
http://www.joca.cn
文章编号:
1001 - 9081
(2012
)06
- 1499 - 04
doi:10.3724/SP.J.1087.2012.01499
多射频多信道自适应波束天线自组网最小化能量组播启发式算法
降爱莲
I\
杨兴彤
1 ,
WU
Weil?
(1.太原理工大学计算机科学与技术学院,太原
030024;
2.
Department
of
Computer
Science
and
Technology
,
University
of
Texas
at
Dallas
,
Dallas
Texas
70085
,
USA)
(
*通信作者电子邮箱
ailianjiang@
126.
com)
摘
要:为解决能量约束的无线自纽网最小化能量组播问题,建立了多射频多信道自适应波未天线方式
(MR
MCAAs)
实现的多波未天线通信模型,进而给出
MR-MCAAs
多波未天线自纽网最小化能量组播问题的形式化定义,然
后提出解决该
NP-
难问题的一个启发式算法。该算法提出两种可能的波未重新分自己策略以优化每个节点的波未分配
和波未发射方案,并构建基于
MR-MCAAs
多波未天线的最小化能量纽播树。该算法的时间复杂度是
O(n
3
log
n)
,
其
中
n
表示网络中的节点数。仿真结果表明:与羊波未定向天线相比
,
2-i
友来天线最小化组格总能耗减少了
59
'J
毛
-72
'J
毛。
关键词:多射频多信道;自适应波未天线;最小化能量组播
;NP-
难问题;启发式算法;无线自纽网
中图分类号:
TP393.01
文献标志码
:A
Heuristic
algorithm
for
minimum
energy
multicast
in
Ad
Hoc
networks
with
multi-radio
multi-channel
adaptive
antennas
JIANG
Ai-lian
1
'
,
YANG
Xing-tong
1
,
WU
Weili
2
(
1.
College 01 Computer
Science
α
nd
Technology,
T
,
α
iyuan
University 01 Technology,
r.
α
iyuan
Shanxi
030024
, China;
2. Department 01 Computer
science
α
nd
Techrwlogy, University 01
Tex
ωα
tDa
U,
田
,
Dallα
:s
Tex
ω
70085
,
USA)
Abstract:
To
solve the problem of
ml
nI
mUm
energy multicast in energy-constraint wireless Ad Hoc networks, the
communication model of multi
- beam antennas based on Multi-Radio Multi-Channel Adaptive Antennas (MR-MCAAs)
was
constructed, and the formal definition
on
the problem of the minimum energy multicast with MR-MCAAs
was
given, and then
a heuristic algorithm for this NP-hard problem was proposed. The algorithm suggested
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(
旷
log
n) ,
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 has reduced
by
59 percent
to
72 percent, compared with the single beam directional antennas.
Key
words:
Multi-Radio Multi-Channel
(MR-MC);
adaptive beam antenna; minimum energy multicast; NP-hard
problem; heuristic algorithm; wireless Ad Hoc network
。
引言
组播是将信号从信源节点同时传送到多个目的节点的一
种网络通信。它是无线自组网中的一个非常重要的功能。自
组网节点由电池供电,能量十分有限,在战争、灾难救助等特
殊应用场合,更换节点的电池是不可想象的。因此,能量有效
的组播始终是无线自组网中的一个重要研究课题
[IJ
。定向
天线把信号能量集中在某个特定方向,本身就具有更好的节
能性,同时减少了对其他方向的信号干扰,提高了空间复用
度,网络传输容量和性能得到显著提高。因此,国内外学者对
基于定向天线的能量高效的组播进行了大量研究
[2
-5J
。然而
这些研究工作中假设的单波束定向天线模型,在能量有效的
组播通信中缺乏足够的灵活性
[6J
剧。在当前多射频多信道无
线自组网
[7
-9J
以及自适应波束天线自组网[
10
一
l1J
技术支持下,
本文探索基于多射频多信道自适应波束天线(
Multi-Radio
Multi-Channel Adaptive Antennas
,
MR-MCAAs)
方式实现的多
收稿日期
:2011-11
-D
7
;修回日期
:2012
-D
2-27
o
波束天线自组网最小化能量组播算法,简称为
MEM-MB
(Minimum Energy Multicast-Multi-Beam) 0
MR-MCAAs
多波束
天线是多射频多信道技术和自适应波束天线技术的融合,可
以用来进一步降低自组网节点的能量消耗,同时减少无线通
信干扰,提高网络容量。文献[
12
J
从降低信道冗余和减少信
道冲突出发,设计了一种构建多射颇多信道
Ad
Hoc
网络最小
冗余广播树算法。文献[
13
J
提出了一个多接口多信道元钱
mesh
网络的组播算法来优化组播容量。文献[
14
J
提出了每
个节点装备多个定向天线的多信道网络体系结构,并对这种
体系结构的网络容量进行理论分析。文献
[6J
探索网络节点
装备一个智能天线阵列以产生多个定向波束的无线自组网组
播生命周期问题以及针对小规模网络的混合整数线性规划
(Mixed Integer Linear
Programmi
吨,
MILP)
精确求解方案。本
文为解决能量约束的元线自组网最小化能量组播问题提出了
一种新的近似求解方案,即:建立了多射频多信道技术和自适
应波束天线技术相互融合的
MR-MCAAs
多波束天线通信模
基金项目·山西省回国留学人员科研资助项目
(2010-30)
;山西省高等学校留学回国人员科研资助项目
(2011-10)
。
作者简介:降爱莲
(1969
-),女,山西太原人,副教授,博士,主要研究方向:无线自组织网络、近似算法设计与分析;
杨兴彤
(1988
-),男,
山东泰安人,硕士研究生,主要研究方向:第法设计与分析、机器学习
WU
Weili(
1968
一),女,美籍华人,副教授,博士,主要研究方向·近似算
法设计与分析、数据挖掘与知识发现。