摘
而分
广泛
用的
关键
中图
1.引
自组
补无
施的
2.移
选择
间密
面结
簇首
节点
单频
要：随着移
分簇结构却能
泛的应用。在本
的分簇算法进
键词：移动自
图分类号：TN
引 言
无线 Ad Ho
组织网络[3]，
无线设备的有
的、能够迅速
移动自组网
平面结构与
在移动自组
择合适的网络
密切相关，必
结构如图
而分簇结构
首形成高一级
点仍是自动组
频分级和多频
单频分级网
移
张
北京邮
移动自组网的发
能克服扩展性
本文中首先对
进行了介绍和
自组网 分簇结
oc 网络又称
依靠节点间的
有限传输距离
速展开使用的
网的结构
与分簇结构
组网中根据网
络拓扑结构，才
必须综合考虑
所示，在平面
4
构，如图
级网络，高一级
组网，由簇首节
频分级两种。
网络只有一个
移动自组
张熊，刘元
邮电大学电子
发展，规模越
性差的缺点，有
对移动自组网
和分析。
结构 分簇算法
称为移动自组
的相互协作在
离。移动 Ad H
的网络体系，
构
络的应用规
才能最大限度
虑。移动自组
面结构中所有
1
2
图
所示，网络
级网络又可分
节点负责簇间
个通信频率，所
组网分簇
元安，胡鹤
子工程学院，
越来越大，使
有利于移动管
网及其网络结
法
组网、多跳网络
在无线环境中
Hoc 网络是一
网络节点能够
模和扩展性，
度地发挥网络
组网一般有两
有节点地位平
3
5
1 移动自组网
被划分为簇
分簇形成更高
间数据转发。
所有节点使用
簇算法研
飞，袁东明
，北京（100
使得平面的结
管理、资源分
结构进行了说
络或对等网络
中自行成网[4
一种不需要依
够动态地进入
，以及应用的
络的性能。而
种结构：平
平等，所以又
6
7
9
网平面结构
，每个簇由一
高一级网络。簇
分级结构根
用同一频率，
研究
明
876）
结构的移动自
分配性，这使
说明，同时主
络[1][2]，它是
4]，借助于多
依赖现有固定
入和离开网络
的可靠性及实
而且，网络结
面结构和分级
又称对等式结
8
一个簇首和多
簇中簇首和簇
根据硬件的不
簇首之间通
自组网不再适
使得分簇结构
主要对几种比
是没有中心实
多跳转发技术
定通信网络基
络。
实时性要求，
结构与路由算
级结构[5][6][7]
结构。
多个簇成员组
簇成员动态变
不同配置又可
通信需要网关
适合，
构得到
比较常
实体的
术来弥
基础设
必须
算法之
。平
组成，
变化，
可分为
关节点
中国科技论文在线
1
支持
范围
用另
法构
能够
移动
于其
量，
交换
第四
扩展
3 基
器的
点的
簇首
通成
较少
内节
使得
的维
持，网关节点
围大、如两级
另一个频率保
分簇结构的
平面式结构
构造分层的拓
够很好地支持
动性，在网络
其他协议，分
优化了网络
换路由控制信
四，对于多媒
展性[11][13]。
基于最大节
最高节点度
的原则，即该
的数目，相邻
首，当度数相
成员节点。反
该算法的优
少信道的空间
节点按照轮询
得系统的性能
维护开销。
点同时处于两
级网络中，簇
保持簇首之间
簇
的优点
构在节点数目
拓扑结构应该
持移动性，维持
络拓扑改变后
分簇管理有 5
络带宽的应用
信息的开销，
媒体服务提供
节点度的分
度分簇算法借
算法的目标是
邻节点中具有
相同时则选择
反复进行以上
优点在于簇的
间重用率较低
询的方式共享
能也随之降低
两个簇内;多频
簇成员节点用
通信。
簇成员
图 移
增多时，路由
该是解决这些
持网络结构的
，通过分簇管
个突出优点：
用，提高了共
强化节点管
有效的 QoS
分簇算法
借鉴了 Interne
是尽量减少簇
有最大节点度
择 ID 最小的节
上过程，直到
的数目较少，
低，该算法对簇
享，当簇内节
低。此外当节点
频分级网络中
一个频率通信
员
移动自组网分
由开销很大，
问题的一个比
的稳定性和鲁
管理能够有效
：首先，它有
共享信道的利
理[8][9][10][11][1
服务[9][10][12]；
et中选择路由
簇的数目，节
(即相邻节点
节点作为簇首
所有节点都加
从而减少了
簇内的节点数
点数量过多时
点移动性较强
中，低级节点
信，簇首节点
簇首
分簇结构
因此可扩展
比较好的方法
鲁棒性。为了
效地实现快速
有效地利用多
用率[10][11][12]
12]；第三，容
；最后，支持
由器的方法[1
节点之间通过
点中具有最多
首。簇首的一
加入某个簇。
分组的投递
数不加以限制
时，每个用户
强时簇首的更
点通信范围小
点用一个频率
展性较差。采
法。一个适当
了支持移动自
速配置、动态
多信道，大幅
][13]；第二，
容易实现局部
持大规模的无
14][15]，其原则
过交互控制消
邻居节点数
一跳邻居节点
。
递时延[16]，但
制，并且簇内
户节点的吞吐
更新频率急剧
小，高级节点
率与簇成员通
网关
采用适当的分
当的移动分簇
自组网的多跳
态重构网络。
幅度提高了系
能够有效地
部网络同步[8]
无线网络，具
则是尽量减少
消息知道其邻
目)的节点被
点则成为该簇
但是由于簇的
内的资源通常
吐量将急剧下
剧上升引入了
通信
通信，
分簇算
簇算法
跳性和
相对
统容
地减少
[10]；
具有可
路由
居节
被选为
簇的普
数目
常由簇
下降，
大量
中国科技论文在线
2
4 基
一的
成员
具有
的簇
理，
节点
算法
5 基
权重
高，
簇算
它们
并不
动情
点通
移动
移动
的更
最低
平衡
6 基
不够
簇首
动性
理的
提出
当簇
电量
量选
基于最小
最小 ID 簇算
的 ID，选相邻
员节点，并不
有最小 ID的成
簇首更新的频
网络的吞吐
点作为簇首，
法没有考虑负
基于最小移
为了适应节
重[20][21]，并依
其分配的权
算法中，需要
们相对速度绝
不是所有的环
情况。为了能
通过比较收到
动性。
该移动性指
动性较强时，
更新较频繁，
低移动性分簇
衡和节点能量
基于权值的
在前面所介
够优化。对于
首负担过重这
性太强这样会
的范围内一边
出的 WCA算法
簇首的程度。
量及邻居节点
选取邻居节点
ID 的分簇
算法是由 Gre
邻节点中具有
不再参与簇首选
成员节点。这
频率较慢，维护
吐量高于最高
将使这些节
负载平衡等因
移动性的分
节点的移动特
依据节点的权
权重越低，选择
一种机制来量
绝对值的时间
环境都可以利
能够准确刻画
到的来自某一
指标的计算不
最低移动性分
簇首的计算
簇算法和最小
量耗费的场合
的分簇算法
介绍的分簇算
于一个簇首来
这样簇首节点
会使簇变得不
边使得更好的
法[23][24]综合考
每一个点的权
点与该节点的
点数多、移动
簇算法
ela 和 Tsai 提
有最小 ID 的节
选举过程。在
这种分簇算法
护簇所需花费
高节点度分簇
点消耗更多的
素。
分簇算法
特性，提高簇结
权重来选举簇
择邻居节点中
量化节点的移
平均，但是
利用 GPS，并且
画节点的移动
一邻居节点的
不依赖于节点
分簇算法可以
算开销较大，
小 ID 分簇算法
合。
法
算法只是考虑
来说它的邻居
点就会很快失
不稳定，增加了
的通信，还应考
考虑多种因素
权值可通过公
的距离四方面
动速度小、电
提出的一种简
节点作为簇首
在某些特殊情
法计算量小，
费的开销较小
算法。该算法
的电池能量，
结构的稳定性
簇首。最低移
中权重最高的
移动性。一种
这种方法需要
且它不能真实
动性，文献[22
连续2次传输
的位置信息，
以明显减少簇
并且也没有考
法适合于计算
了一个方面的
不能过多，否
效。另外还要
了簇消亡的危
考虑簇首和成
素来为每一节
公式[25]来计算
来对每一节点
量大、邻居节
简单的分簇算
首，其一跳邻
情况下，簇首
实现方便，
小，并且由于
法的缺点在于
从而缩短了
性，可以根据
移动性分簇算
的节点作为簇
种简单的方法
要通过 GPS
实地反映一个
]提出了一种
输信号的强度
，优于单纯的
簇首的更新频
考虑系统的负
算量小和复杂
的因素，没有
否则就会很快
要考虑移动性
危险。同时为
成员节点的相
节点分配一个
算，即从节点
点综合衡量，
节点与该节点
法[17][18][19]。
邻居节点成为
首可以将其职
算法收敛较快
于簇和簇内节
于倾向于选择
了簇首节点的
据节点的移动
算法中规定，
簇首。在基于
法规定任何节
来获得节点
个节点相对周
种聚集的本地
度来估计2个
的使用距离或
频率，它的缺
负载平衡和节
杂性高，并且
有考虑其他方
快的消耗掉自
性的问题，如
为了簇首和簇
相对距离。基
个权值，用来
点的邻居节点
，看其适合作
点的距离和小
每个节点分
为该簇首所在
职责交付给其
快。最小 ID
节点的数目较
择具有较小 I
的生命期，并
动性来为节点
节点的移动
于节点移动性
节点对的移动
点的位置。但
周围邻居节点
地移动性指标
个节点之间的
或速度的方法
缺点在于节点
节点的能量损
且不过多考虑
方面的因素，
自己有限的能
如果一个簇首
簇成员的在一
基于以上考虑
来标识每一节
点数、移动速
作簇首的程度
小的节点为簇
分配唯
在簇的
其簇内
算法
较为合
ID 的
并且该
分配
性越
性的分
性为
但是，
的运
，节
相对
法。在
权重
损耗。
虑负载
分簇
能量，
首的移
一个合
虑，由
节点充
速度、
度。尽
簇首，
中国科技论文在线
3
从而
7 结
和维
目前
簇算
的算
销来
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
[11]
[12]
[13]
[14]
[15]
[16]
[17]
[18]
而提高簇的稳
结论
分簇结构有
维护开销，为
前基于权值的
算法。它避免
算法实现复杂
来获得较好的
郑少仁，王海
陈林星，曾曦
Macker J P，
Communicatio
Charles E，Pe
赵志峰，郑少
英春，史美林
Ephremides A
hopping signa
Duan SW，Yua
Conference on
McDonald A B
[J] ．IEEE Jo
] Lin CR，Gerla
Communicatio
] Feng YX，Wan
network [J] ．
] Chen S，Nahr
Areas in Comm
] Iwata A，Chia
Selected Areas
] 王海涛，张学
] Gerla M，Tsa
1995,1(3):255
] 郑少仁，王海
] . Baker an
Networks. Pro
476-483
] . Baker an
Networks .Rad
1981，1694-1
稳定性，平衡
有利于移动管
为此，必须设
的分簇算法具
免了单一因素分
杂度稍高于只
的系统性能。
海涛，赵志峰等
曦，曹毅．《移动
Corson M S．
ons Review ，
ekins．Ad Hoc
少仁．Adhoc 网
林．自组网体系
A，Wieselthier JE
aling [J] ．Proc
an XB．Explori
n Wireless and O
B，Znati T．A
ournal on Selec
a M．Adaptive
ons, 1997, 15(7
ng GX，Liu ZG
Journal of Sof
rstedt K. Distrib
munications, 19
ang CC，Pei Ge
s in Communic
学平.Ad Hoc 网
ai J T C．Multi
5-265.
海涛，赵志峰等
nd A EPhremid
oceedings of th
nd A EPhremide
dio Network vi
1701
衡整个网络的
管理、资源分配
设计合理的分
具有较低的簇
分簇引入了多
考虑单个因
等．《Ad Hoc 网
动 Ad Hoc 网络
Mobile Ad H
l998，2(4):9-l5
c Network[M]
网络体系结构研
系结构研究[J]
E，Baker D J．A
c. of the IEEE,
ing architecture
Optical Commu
A mobility base
ted Areas in Co
clustering for m
7):1265-1275.
G，Jiang YQ．A
ftware, 2003, 14
buted quality-o
999, 17(8):1488
etal. Scalable ro
cations, 1999, 1
络中的分簇算
icluster，Mobi
等．Ad Hoc 网络
des. A Distribut
he Second Inter
es．A Distribu
ia a Distributed
负载。
配和提高可扩
簇算法。本文
簇维护开销和
多种因素，在
素的分簇算法
参考文献
网络技术》[M]
络》[M] ．北京
Hoc Networkin
5.
．Addison-We
研究[J] ．电信科
．通信学报，
A design concep
1987, 75 (1):56
e for wireless ne
unications Netw
ed framework fo
ommunications,
mobile wireless
clustering algo
4(1):132-138.
of-service routin
8-1505.
outing strategie
7(8):1369-1379
算法，数据通信
le，Multimedi
络技术[M] ．北
ted Algorithm
rnational Confe
uted Algorithm
Algorithm. IEE
扩展性，但是
文比较介绍了
和较高的自适
在分簇的过程
法，但是可以
] ．北京：人民
京：电子工业
ng and the IET
esley．Decemb
科学，2001，
1999,20(9):47-
pt for reliablemo
6-73.
etworks manage
works[C]，200
for adaptive clu
, 1999, 17(8):14
s networks [J] ．
orithm applied t
ng in ad hoc net
s for ad hoc wir
9.
信.,32-35.
a Radio Netwo
北京:人民邮电
for Organizing
rence on Distri
for Organizing
EE Transaction
是分簇算法会
了几种比较经
适应性是一种
程中更加全面
以通过牺牲微
民邮电出版社，
出版社，2006
TF [J] ． Mob
er 2000.
1:14-17.
-54.
obile radio netw
ement [D]． 20
6.
ustering in wirel
466-1487.
．IEEE Journal
to the managem
tworks [J].IEEE
reless networks
rk [J] ．ACM
电出版社，2005
g Mobile Radio
ibuted Compute
g Mobile Radio
ns on Communi
会带来计算、
经典的分簇算
性能比较好
面。同时基于
微不足道的计
，2005.
.
bile Computin
works with freq
06 IFIP Interna
less ad hoc netw
on Selected Ar
ment of mobile a
E Journal on Se
s [J].IEEE Journ
Wireless Netw
5.
o Telecommuni
er Systems，19
o Telecommunic
ications COM-2
通信
算法。
的分
于权值
计算开
g and
quency
ational
works
reas in
ad hoc
lected
nal on
works，
cation
981，
cation
29(11)，
中国科技论文在线
4
[19]
[20]
[21]
[22]
[23]
[24]
[25]
] A. EPhremide
frequency hop
] BASAGNIS.
Architectures，
] S Basagni. D
Architectures,
] -1998
] M Chatterjee，
[J] ．Journal
] M Chatterjee，
[A] ． Proce
] CHEN G，N
[A] ． In：Pro
Computer Soc
es，. Wiese l
pping signaling
Distributed clu
，Algorithms a
Distributed Clu
Algorithms an
8，Distributed
S K Das，D T
of Cluster com
S K Das，D T
eedings of IEE
NOCETTIF，CO
oceedings of the
ciety 2002.
lthier and . B
.Proceedings o
ustering for Ad
and Networks [C
ustering for A
nd Networks[C]
and mobility ad
Turgut．WCA：
mputing，Specia
Turgut．An on-d
EE GLOBECOM
ONZALEJ，et
e 35th Hawaii In
Baker．A desig
of IEEE,1987,75
d hoc networks
C]. Perth: The u
Ad Hoc Netw
, June
daptive clusteri
：A Weighted C
al issue on Mob
demand weighte
M2000[C]，20
t al. Connectiv
nternational Con
gn concept for r
5(l):56-73
s [A]. In：Inter
university of W
works [A], Inte
0-315.
ng for Ad hoc n
Clustering Algo
bile Ad hoc Net
ed clustering al
000:1697-1701.
vity based k-ho
nference on Sy
reliable Mobile
rnational Sy
Western Australia
ernational Sym
networks [S].
orithm for Mobi
tworking，200
lgorithm (WCA
.
op clustering in
stem Sciences [
e radio network
ymposiun on Pa
a，1999.
mposiun on Pa
ile Ad Hoc Netw
2，5:193-204.
A) of ad hoc netw
n wireless netw
[C] ． Hawaii:
s with
arallel
arallel
works
works
works
IEEE
中国科技论文在线
5
R
Sch
With
no lo
short
This
conc
analy
Keyw
作者
张
刘元
胡鹤
袁东
Research
hool of Electr
h the developm
onger suitable
tcomings of p
s makes the c
cept of the m
yzed several c
words: Mobil
者介绍：
熊，硕士研
元安，教授，
鹤飞，讲师，
东明，讲师，
on clust
Zhang Xio
ronic Enginee
ment of mobil
e for mobile
poor expansib
clustering stru
mobile ad hoc
commonly use
le Ad Hoc Ne
研究生，主要
主要研究方
主要研究方
主要研究方
ter algor
ong, Liu Yua
ering, Beijing
P
le ad hoc netw
ad hoc netwo
bility and is co
ucture has be
c networks an
ed clustering a
etwork; cluster
要研究方向是
方向电磁兼容
方向网络技术
方向计算机网
rithm of
an’an, Hu H
g University o
PRC, (100876
Abstract
works and the
orks. But the
onducive to m
een widely us
nd its network
algorithms.
ring; cluster a
宽带无线通信
。
。
络
Mobile
Hefei, Yuan
of Posts and T
6)
e increasing sc
clustering str
mobility manag
sed. In this a
k structure ,th
algorithm
信。
Ad Hoc
n Dongming
Telecommuni
cale, the struct
ructure is abl
gement, alloc
article, we fir
hen we main
Network
g
ications, Beij
ture of the pla
e to overcom
cation of resou
rstly introduc
nly introduced
ks
jing,
ane is
me the
urces.
e the
d and
中国科技论文在线
6
