无线传感器网络的成簇算法

1、无线传感器网络的成簇算法摘要:如何合理、有效地利用成簇算法使得网络节点具有均衡的负载和较小能耗率成为当前无线传感器网络研究领域的热点问题之一。根据无线传感器网络的分簇机制，着重从 簇首的选举、簇组织和簇的路由三个方面系统地分析了当前 典型的成簇算法,对算法的特点和适用情况进行了比较分析, 并指出了目前算法存在的问题和需要进一步研究的内容。关键词:无线传感器；成簇算法；路由；簇中图分类号:TP393文献标志码:A文章编号:1001-3695(2009)09-3222-05doi:10.3969/j.issn.1001-3695.2009.09.006Clustering algorithm in

2、 wireless sensor networksWANG Sheng-cai ,LI Ai-hua ,WANG Tao ,ZHANG Bo?2?(1.Second Artillery Engineering College, Xi an 710025,China;2.96634 Unit in PLA, Nanchang 330201, China)Abstract:One of the current hot topics in wireless sensornetworks is how to make the nodes load more balanced andconsuming

3、energy rate lower by adopting new clusteringalgorithms reasonably and effectively. This paper analyzed the current classic algorithms by electing cluster heads, forming clusters, and clustering routing. Analyzed the character and applicability of the algorithms comparatively, and pointed out the exi

4、sting problems and research trends.Key words:wireless sensor networks（WSN）; clustering algorithm; routing; cluster随着无线传感器自组网络规模的扩大，平面路由方案会 因链路处理开销的增加和动态反应速度的降低而变得不适 用，解决办法之一是采用成簇的路由方案。在成簇算法中，网 络由多个簇组成，每个簇包括簇首和成员两种类型的节点，处 于同一簇内的簇首和成员节点共同维护所在簇内的路由信 息。簇首节点负责所管辖簇内拓扑信息的压缩和融合处理, 并与其他簇首节点交换处理后的拓扑信息，直到传感数据传

5、 送至基站1。采用成簇的路由思路的目的是:a）通过减少参与路由计 算的节点数目，减小路由表尺寸,降低交换路由信息所需的通 信开销和维护路由表所需的内存开销2;b ）基于某种簇生成 策略产生较为稳定的子网络，减少拓扑结构变化对路由算法 的影响3;c ）簇成员节点定期苏醒上传数据至簇首并融合，大 大减少节点能耗和数据通信量,从而提高网络寿命4。1无线传感器网络簇运算概述学术界对Ad hoc网络的研究比WSN要早,目前已经提出 了很多针对Ad hoc网络的分簇路由算法，如采用LCC(least cluster change)算法形成簇结构的CGSR协议、结合按需和主 动路由策略的ZRP(zone r

6、outing protocol)算法等1,而无线传 感器网络中的分簇算法正处于研究阶段。同Ad hoc网相 比,WSN中的分簇算法更侧重于保持网络整体能量消耗的均 衡，避免出现“热点”问题，最大化地延长网络生存时间5,6。LEACH是MIT的Heinzelman等人专门为WSN设计的低 功耗自适应分层路由算法7,也是WSN中最早提出的成簇路 由算法。它的基本思想是以循环的方式随机选择簇首节点, 将整个网络的能量负载平均分配到每个传感器节点中,从而 达到降低网络能源消耗、提高网络整体生存时间的目的。这 个思想贯穿于后来的很多簇算法研究之中，成为簇运算的基 点。LEACH算法将簇的建立过程分为三个

7、阶段，即簇首节点 的选择、簇的组织和簇的连接? 6。从目前的文献来看，对 簇算法的研究大多是从这三个方面着手。2簇首的选择成为簇首意味着要肩负额外的任务，即组织簇内媒体的 接入、节点数据的融合和路由决策的选择。这是一个密集型 操作，所以它必须通过轮换所有节点的角色使簇首的能量不 会消耗过多。为了能进行簇首的轮换，分簇算法不能只运行一 次,而必须重复执行。例如，这种重复可以周期性出现或由节 点的移动触发。当然，合理地选择周期和触发阈值是一个很重 要的优化问题8。按照成簇的方式可以将传感网络分为分布式和集中式 两种类型。当网络是分布式时，簇首选举侧重于节点能量的均 衡;当网络是集中式时，簇首选举更

8、侧重于簇首分布的均匀性。2.1分布式网络在分布式网络中,各节点具有同等地位，它们之间通过信 息交互实现对邻居节点的感知。在进行簇首选择时，基本上都 是围绕着某个指标来进行，如ID号、剩余能量、节点度、权 值、定时器和属性等。通过这些指标的比较来进行簇首的选 择。这些策略中，有效果好的也有效果差的，有简单的也有复 杂的,但都是为了解决一个问题,那就是均衡各个节点的能量, 让网络的寿命更长。LEACH 算法LEACH算法9是最早也是最基本的分簇算法。簇首节点的选择依据网络中所需要的簇首节点总数和迄今为止每个节点已成为簇首的次数来决定。具体的选择办法是:每个传感 器节点随机选择01的一个值,如果选定

9、的值小于某一个阈 值?T(n),那么？?这个节点成为簇首节点。T(n)值计算如下：T(n)=k/N-kr? mod?(N/k)若 nG0其他情况(1)其中:N为网络中传感器节点的总数;k为一个回合网络中 的簇首节点数;r为已完成的回合数。?对于这种随机选举簇首的方法，需要得到簇首数与节点 总数的最优比。考虑到与距离较远的簇首节点通信时成本较 高，所以增加几个簇首的操作会迅速提高整体的能量效率，但 当超过某个比值时，分簇的优点会慢慢消失。Heinzelman等人 7经过计算认为最优值是5%。LCALEACH在簇首的选举机制中通过?N/k?次循环轮换了 所有的节点，在一定程度上均衡了各个节点的能耗

10、。但由于 LEACH算法采用随机的方式产生簇首,可能导致簇首节点的 分布不均匀。在这种情况下,Baker等人10提出了基于节点ID 判断的成簇思想:a)每个节点广播自身的ID并且监听其他节 点的传播信息;b)节点广播其监听到的邻居节点信息，直到每 一个节点都知道它一跳和两跳内邻居节点的情况;c)在某个 节点的一跳邻居节点中拥有最大ID号的将成为簇首。这种方法通过ID值的比较可以将簇首初步分开,至少能 保证在节点一跳范围内只存在一个簇首。DCHS 算法LCA虽然初步解决了簇首分布不均的问题,但由于只有邻居节点中有最大ID号的节点才能成为簇首，导致ID号越大的 节点成为簇首的机会越大，也越容易耗尽

11、能量。因而Handy 等人11 将节点剩余能量考虑到了成簇的过程中，形成了 DCHS(deterministic cluster-head selection)算法，即将 LEACH 中 的时间阈值改进为?T(n)=k/N-kr? mod?(N/k) X (E?current?/E?max?)(2)其中:E?current?为当前节点的能量,E?max? 为节点的最大能量。这种策略保证了有较多能量的节点有更 大的机会成为簇首，从而均衡了整个网络的能量消耗。?HEED 算法DCHS算法仍然采用了随机策略，所不同的只是增大了能 量高的节点成为簇首的概率，这虽然均衡了节点的能耗，但对 簇之间的负载均

12、衡无法解决，即各个簇的能耗率可能随节点 分布的不均而产生很大差别。Younis等人12提出了 HEED(hybrid energy-efficient distributed clusting)算法,通过采 用节点剩余能量和通信代价两个指标选举簇首，一方面保证 了拥有能量多的节点有更大几率成为簇首，另一方面保证了 生成的簇具有大致均衡的能耗率。算法分为三个阶段，在初始化阶段,所有节点设置一个初始的簇首概率值?C?prob?,并按式(3)计算其成为簇 首的概率?CH?prob?:?CH?prob?(r,0)=?max?C?prob?*E?res idual?/E?max?,p?min?(3)其中

13、:CH?prob?(r,0)是节点在第r轮第0次迭代成 为簇首的概率,E?residual?是节点的剩余能 量,E?max?是节点的初始能量,p?min?是概率底 线值。在迭代阶段,节点按式进行迭代直到CH?prob?(r,j)=1。迭代结束并声明自己为簇首节点，其他 未成为簇首的节点收到声明后停止迭代。CH?prob?(r,j)=2XCH?prob?(r,j-1)(4)在最后阶段，若非簇首节点收到多个簇首的声明,将选择 通信代价低的簇加入，以达到簇间能耗尽可能均匀。2.1.5加权分簇算法到目前为止，讨论过的节点的指标都相当简单，这些参数 并不能完全表示节点作为簇首的各个方面的特性。而且，可能

14、 还有其他系统层强加给拓扑选择的限制,如簇的大小或深度， 而通常规定一个簇首能够有效控制的簇大小是一件优化簇 必须要做的事情。?Chatterjee?等人8,13 介绍了一个考虑了以下因素来计算节点权值的分簇算法:簇不应超过最大规模5电池功率、 移动性(倾向于移动慢的节点)、邻节点的接近程度(簇内成员 的距离越小越好)。节点v的权值用公式表示为W?v?=w?1?d?v?-(5 +w?2?EueN(v)?dist?(v,u)+w?3?S(v)+w?4?T(v)(5)其中:w?i?是非负权值因子,N(v)是v的邻节点,S(v)是节 点v的平均速率,T(v)是节点v已经作为簇首的时间。?实际的算法和

15、上面讨论过的那些基本一致，其中小权值 优先。这个算法的一个令人感兴趣的方面是它会在节点中自 适应地轮换簇首的角色，以保证在这些节点中分担负载。2.1.6 EA(emergent algorithms)上面的算法虽然复杂程度不一，但都存在一个与算法结 合的明确目标，即依据某个指标来确定簇首。Chan Hao-wei等 人14 构建了一种可以不使用这种明显目标的本地算法，即浮 现算法，它能够移动簇首节点，直到簇的分布是均匀的为止。算法中，每个节点都会有三种状态，即未分簇的、簇首和 追随者。如果在未分簇的节点附近没有簇，它们会自发地变成 簇首，这些簇首把它们的邻节点征召为追随者。如果一个簇首 的追随

16、者能够成为一个更好的簇首，如它有更多的追随者并 且与其他簇的重叠部分少,那么这个簇首就会退位。这个追随 者就会由旧簇首，即退位的簇首才隹选为新簇首。实际上，簇首 的角色在网络中不断移动。这个算法的一个特性是对给定区域的压缩接近于最紧六边形分布，它的运行时间是恒定的(因为簇首是由分布式算 法产生的)，与网络的规模无关。2.2集中式网络分布式算法通过对指标的比较可以均衡节点的能量，让 网络节点尽量同时死亡，但是由于缺少全局信息，很难做到让 簇首均匀分布，导致部分簇首能量消耗过快。集中式网络在此 基础上发挥了它掌握全局信息的优点，从地理位置、节点能量 占网络平均能量的比值等参数开展了大量对簇首均匀分

17、布 的思考。目前流行的如LEACH-C、GAF等,算法先用集中式选 择簇首使得算法具有较好的健壮性，然后又进行局部的簇首 选举算法，使得所选簇首在区域内分布较均匀,延长网络的生 命期。LEACH系列算法针对LEACH算法簇首分布不均的问题,Heinzelman等人9 在LEACH的基础上提出了一系列算法，包括LEACH-C、LEACH-F 等,它们均采用集中式算法，在成簇阶段各节点将自身位置信 息和剩余能量汇报给基站，由基站根据各节点剩余能量占网 络总能量的比例等指标进行优化运算，并指导节点分布，选出 合适的簇首,再向全网广播。改进后节点?S?i?在第r轮成 为簇首的概率为P?i?(r)=?m

18、in?kE?i?(r)/E?total?(r),1(6)其中:k表示簇首个数,E?i?(r)表示节点S?i?在第r轮的 剩余能量,E?total?(r)表示在第r?轮全网的剩余能量。 该方法不仅可以促使节点的能量均衡,还能改善簇首节点的 分布。这两种算法的不同之处在于,LEACH-C仍然采用定期成 簇、簇首轮转的策略，但LEACH-F 一旦成簇后就不再组织簇， 簇头节点仅在本簇内轮转,这样虽然减少了开销，但不能动态 处理节点的加入、失败和移动。GAF 算法LEACH系列算法通过基站对各节点的地理位置、剩余能 量的采集，达到了掌握全局的目的，但这需要消耗较多的通信 能量和较大的延时。GAF(ge

19、ographical adaptive fidelity)算法把 监测区域划分成虚拟单元格(图1),将节点按照地理位置信息 划入相应的单元格，在每个单元格中定期选举产生一个簇首 节点，并且簇内只有簇首节点保持活动，其他节点进入睡眠状 态15。与GAF算法类似的GS?32和Voronoi图算法16也 同样采用预先从地理上划分出相互隔离的区域，然后在小区 域中选举簇首的方法，所不同的是GS?3?构筑的是正六边形 的结构(图2),而Voronoi图算法是进行Voronoi图划分。3 簇组织算法簇组织通常是基于传感器节点的剩余能量和与簇首的接近程度来进行的。大部分与LEACH 一样，根据收到信号的强

20、度决定加入哪个簇。随着研究的深入，又产生了一些新的更适 合的成簇方式,如上面讲到的HEED算法，采用了一种基于通 信代价的成簇方式，当节点落入多个簇首的覆盖范围时，选择 通信代价比较小的簇首加入，以达到簇的负载均衡。DWEHC 算法在簇的组织过程中,一般簇内节点采用一跳的方式与簇 首通信，但是当距离较远时，这种方式的能耗仍然比较高,因而 Mhatre等人17研究了什么时候应该在簇内使用多跳的问题, 假设了一个非齐次的系统模型。其中簇首与远处的基站直接 通信,传感器把自己的数据发送给簇首,并在簇首进行融合。 这些传感器要么与簇首直接通信,要么通过多跳进行通信。作 者认为超过某个确定的距离就应该使

21、用多跳，并提供了一个 表达式来计算它,这个距离只由无线参数决定(尤其时路径损 耗系数),并且与网络特性相互独立。在这种情况下,Ding Ping等人18提出了 DWEHC(distri-buted? weight-based energy-efficient hierarchical clustering)算法,它是一种分布式的成簇算法，时间 复杂度为?O?(1)。每个传感器节点根据节点的剩余能量和 与邻居节点的接近程度确定权值，在所有邻居节点中拥有最 大权重的节点首先成为簇首，其他节点则成为成员节点。由于 它们能直接与簇首通信，也称为第一层成员节点。这些节点遍 历邻居非簇首节点寻找到达簇首的

22、最小通信代价路径，并评 估出是作为第一层节点好还是第二层节点好。若作为第二层 节点更加节省能量，那么该成员节点将变为第二层成员节点, 直到簇内形成最有效的拓扑结构。为了限制簇内信号转发的 层数,算法为每个簇都指派了一个区域,在区域之外的节点将 加入别的簇,簇内拓扑如图3所示。PEGASIS 和分层 PEGASIS 算法与上面的多簇结构不同,PEGASIS协议19在传感器节点 中采用链式结构进行连接，运行时每个节点首先利用信号的 强度来衡量其所有邻居节点距离的远近，在确定其最近邻居 的同时调整发送信号的强度，以便只有这个邻居能够听到。其 次，链中每个节点向邻居节点发送和接收数据,并且只选择一 个

23、节点作为链首向汇聚点传输数据。采集到的数据以点到点 的方式传送、融合，并最终被送到汇聚点。这种算法减小了 LEACH在簇重构过程中产生的开销，并且通过数据融合降低 了收发过程的次数，从而降低了能量的消耗;但算法所构建的 节点链中,元距离的节点会引起过多的数据延迟,而且链首节 点的惟一性使得链首会成为瓶颈。为此,Lindsy等人又在PEGASIS的基础上提出了分层 PEGASIS来降低数据包到汇聚点传送过程中所引起的延时。 该算法采用树状分层结构的方式，每一层选择的节点向更高 一级的节点传送数据。要求在每个回合的数据采集中,给定层 的节点都向附近的邻居发送数据，所有接收数据的节点被提 升为上一层

24、的节点。依此类推，最后顶层只有一个节点被保留 下来并成为链首节点。这种分层方式保证了数据的并行传输, 并有效地降低了传输时延。EEUCAA 算法目前，大多分簇都是尽量将簇大小分成一致，以满足簇的 负载均衡,但是在簇间通信时可能会出现热点问题。因为某些 距离基站比较近的簇首,除了需要承担本簇内数据的收集、融 合和传输任务，还需要为其他的簇首提供中继数据的服务,能 量消耗非常大。一旦这些簇首的能量耗尽，就会严重影响网络 的正常工作，因此，不等簇的概念应运而生。EEUCAA算法通过 减小基站附近簇的规模(即增大基站附近簇的数量)来均衡热 点问题，取得了较好的效果。a)网络中具有较多能量的节点以一定的

25、概率参与簇首的 竞争,并根据与基站的距离，产生一个竞争范围？?R?comp?R?comp?=1-c(d?max?-d(s?i?,BS)/(d?max? ?-d?min?)R?0?comp?(7)其中:C 为(0,1 )间的常数,d?max?、d?min?分 别为网络中节点距离基站的最大与最小距离,d(s?i?,BS)为 节点s?i?与基站之间的距离,R?0?comp?为所允许 的最大竞争范围(预先设定)。?b?)其余节点为了节能先进入休眠状态,等待新选出的 簇首广播簇首消息,一旦监测到簇首广播了簇首消息就进入 工作状态并加入该簇。通过竞争的方式，最终成为簇首的节点应该满足这样的 条件，即在它的

26、竞争范围R?comp?内不存在其他的簇首 节点;当距离基站越近时，竞争范围的取值越小,即竞争范围随 着节点与基站间距的减小而减小，这样可以保证在基站附近 产生的簇的数目较多,而距离基站较远的区域产生的簇的数 目较少,使得在基站附近的簇首可以保留更多的能量用于簇 间的数据转发，从而延长网路的寿命，如图4所示。?4簇的路由LEACH算法最大的优势在于它将多个节点形成了一个集 合,而只由簇首节点进行数据的传输，大大减少了能量的消耗 和路由的复杂度。但它是在所有节点能够与基站直接通信的 假设下进行的，具有一定的局限性，能耗也很大。为此，很多学 者对簇的路由算法进行了研究用前，簇的路由有三种方式,即 多

27、层分簇、簇首多跳和设置网关节点。HCC(hierarchical control clustering)算法无线信道中,能量消耗?E与距离d存在关系:E=kd?n?。 其中k为常数,2WnW4。？?传感器网络中节点通常贴近地面, 应用环境中有很多障碍物，接收天线能力有限,所以节点直接 将数据传送到基站将耗费大量的能量。由于LEACH的先天不 足，一个很自然的改进策略就是在保持簇数量不变的前提下， 减少直接向基站传输的节点数。Bandyopadhyay建议,在传感器节点将传感器的数据报送 远端处理中心的情况下，可以使用多层分簇来节省能量8。他 们从一个简单的、随机选举簇首的算法开始。其中节点成为

28、 簇首的概率为?p,簇的大小为k;没有被这些簇覆盖的节点将 “被迫地”成为簇首。假设能量消耗和节点部署都是标准的,p 和k的闭合解均可以通过解析的方法来求得。用这种随机的 算法能很容易地形成多个层:?a?）从第一层簇首中选出一些 节点作为第二层簇首，并把这个消息向邻居不多于k?1?跳 的簇首节点通告;?b?）这些节点会加入第二层形成第二级簇。 显然，这还可以扩展到更多的层。通过处理中心发送数据时所 需的最小能量可以确定p?i?和k?i?的最优值。收集数据 时，每个节点把它的数据发送到上一级的簇首,进行数据融合 并转发。多层分簇的示意图如图5所示,这个方案在节省能量 方面比其他分簇方案性能优越,

29、而且这个算法的复杂度也比 较低。?LEACH-M 算法多层分簇的方式在减少能量消耗方面起了不小的作用, 但是它仍然是以假定所有节点都能与基站通信为前提，需要 某个或某几个节点直接向基站传输数据。在大型网络中，这种 方法将显得不太现实，因而，将平面路由算法应用于簇首之间 的路由成为改善网络结构的一个方向。当网络是中小规模时，簇首节点并不多，这样采用最简单 的泛洪策略就可以将数据传输出去。但是随着网络规模的扩 大，这种泛洪策略就像在平面路由中一样，可能会导致“内爆” 现象，因而李岩等人20将DD算法应用到簇首的路由中，取得 了较好的效果。a）汇聚节点以广播、多跳的方式向网络中所有簇首发布 命令,命

30、令信息用含有任务类型、数据发送速率、时间戳等参 数的兴趣描述。每个簇首缓存接收到兴趣，并通过记录发来兴 趣的相应邻居节点等来建立梯度。b）当节点采集到匹配数据 时，通过梯度路径发向汇聚点，汇聚点或中间节点可能收到经 过多个邻居节点的相同数据，中间节点利用本地化规则实现 数据的再融合。c）汇聚点在收到这些低速数据后，向数据到达 最快的邻居簇首节点发送增强消息，增强消息表示汇聚节点 要求高速率发送数据，据此构建数据发送的主路径，数据以后 就通过主路径发送到汇聚节点,该算法在节能和减小延时方 面效果明显。4.3设置网关节点数据在簇首之间进行传播时，若簇首分布不均或者由于 障碍物的阻隔，可能导致个别簇

31、首相对孤立，不能与其余簇首 建立起有效的连接。为了增加簇的连通性，一个有效且稳妥的 办法就是在相邻簇间寻找一些能够担任中转任务的网关节 点,保证簇的可靠连通。滑楠等人21 建立了一种簇间网关路由的方法。设有两 个相邻簇cluster 1和cluster 2,其簇首分别用CH1和CH2标志, 用CM1和CM2分别标志两个簇的任意成员，并假定路由建立 过程由cluster 1发起。簇间路由算法包含四个并行过程，分别 对应图6中的四种连通方式。这四个过程在应用中究竟采用哪一种路由方式,主要取 决于邻近簇首最先收到的请求信息来源于何种节点。若簇首 CH2最先收到的信息来源于节点CM1,则说明簇首间不能

32、直 接连通，必须通过网关节点路由，对应过程3。这种方法对动态 簇组织算法有很好的支持能力,但由于节点间协商的存在，增 大了网络的开销。采用目前市场上流行的可调发射功率芯片 可以简化簇间路由，建立簇间的直接通信。5算法的比较分析上述算法大多都是针对特定的应用而设计的，在不同的 环境中表现出各自的特色和优势，因此不能绝对地判断哪种 算法的优劣。表1对上述的算法进行了比较。a）选择簇首有三种方法。最简单的方法就是按概率自我 选择，周期轮换。为了能提高算法的能量均衡：(a)在门限值中 加入剩余能量是一个不错的选择，但是这种方法选择的簇首 过于随机，在数据收集时浪费了太多的能量;(b)通过邻居节点 间的

33、信息交互来达到对局部网络的了解，从而选出合适的簇 首，该方法具有较好的扩展性、较快的收敛速度和较低的能耗 率，但算法比较复杂，时间延迟、网络均衡仍然是一大挑战 22;(c)基站节点通过收集各个传感节点的能量和位置等信息 来计算网络最佳的簇首数量、大小和位置，这种方法生成的簇 首均匀、能量均衡、健壮性好,但成簇开销大，扩展性差、网 络流量以及信号干扰的概率都会增加,一般只适合中小型网 络。簇的轮转周期的确定。簇的建立阶段会有大量能量开 销，且不能传输数据,从而导致事件延迟,所以尽可能缩短这个 周期，增大工作阶段和建立阶段的比值是提高效率的有效手 段，但每轮的周期又不能太长，否则对网络的变化响应太

34、慢。 目前，采用固定周期或以某个量(如节点剩余能量)的百分比作 为门限来实现网络同步轮转的方法比较常见,如果不用全网 同步轮转,则同步要求和网络开销会得到很大降低，这是一个 值得研究的问题23,24。簇组织在一般算法中都是根据信号的强弱来加入簇, 如果簇首分布不均匀就可能导致簇间的负载不均衡,引入通 信代价可以减弱这种不均衡，但同时也增加了开销和算法的 复杂度。米用簇内多跳是减小成簇开销的一种有效方法，尤其 是簇的通信半径比较大，簇内节点较多的时候。当然要想延长 网络的寿命,还必须对网络中的热点进行考虑,采用小半径成 簇或不均匀簇是解决这个问题的常用方法。此外，利用分布式 的特点建立更高效的启

35、发机制、通过节点之间的互动和信息 反馈来分簇是目前重点研究的一个方向25,26。d）由于簇首单跳向基站传输数据能耗过大且不能保证连 通,采用簇间路由是一个理想的办法。目前簇间路由最广泛的 方法是使用树状拓扑27 或到基站的最小跳数来组织路由，但 热点问题的存在又极大限制了路由算法的发展。采用分层路 由实际是LEACH算法和簇间路由的一种折中，在中小型网络 中具有很好的应用前景。6需要进一步研究的内容本文总结了当前无线传感器网络分簇算法中最具代表 性的工作,并将簇首选择、簇的形成以及簇的路由三方面的算 法进行了比较分析，总结了各自的特点和不足，点明了分簇算 法的发展趋势。分簇算法中需要进一步研究

36、的内容概括如下:a）设计兼有平面结构和分簇结构优点的新型数据传输模 式是目前很有趣的一个研究方向。在某些基于簇的路由协议 中，并没有簇首的概念，每个节点直到它将转发的下一个节点, 将这类协议叫做基于虚拟簇的平面路由协议。这类协议既能 有效地管理网络拓扑结构,较好地处理节点的移动性,又能有 效利用能量传输数据。b）进一步提高算法的节能性。WSN通过高效的分簇算法 形成合理的网络结构，通过主动的能量管理阻止网络连通性 的下降，从而在保证数据可靠传输的前提下，延长网络的生命 周期。但仅仅考虑网络层的节能是远远不够的，将MAC层和 路由层协议捆绑,用跨层技术来进一步节省功耗是一个值得 关注的方向。c）

37、在簇内进行合理的数据融合。为避免浪费通信带宽和 能量、提高信息收集效率，采用数据融合是必要的手段。但如 何引入簇内被测数据的相关性,使得相关性强的节点形成在 一个簇中,从而提高数据压缩率和融合率,还值得深入探索。 此外，寻找网络数据融合率和网络延迟、鲁棒性之间的合理折 中，也是进一步提高网络性能的必要保证。研究符合实际应用环境的模型系统。一般认为网络中 的所有节点都具有相同的最大发射功率,但由于天线质量、地 形等许多方面的差异，各个节点所形成的发射范围各不相同, 异构网络相对于同构网络而言是更现实的网络模型28。但 由于网络的异构性给理论分析带来了困难，人们对异构网络 的研究还比较少。这使得目

38、前的研究结果普遍停留在仿真的 水平,缺乏足够的说服力。参考文献：于海斌,曾鹏,梁韦华.智能无线传感器网络系统M.北京:科学出版社,2006.AKKAYA K, YOUNIS M. A survey on routing protocols for wireless sensor networksJ. Ad hoc Networks, 2003, 3(5):325-?349.HOU Y T, SHI Y, SHERALI H D, ?et al?. On energy provisioning and relay node placement for wireless sensor networ

39、ksJ. IEEE Trans on Wireless Communications, 2005, 4(5):2579-?2590.AL-KARAKI J N, KAMAL A E. Routing techniques in wireless sensor networks:a surveyJ. IEEE Wireless Communications, 2004, 11(6):6-?28.李莉，董树松，温向明.无线传感器网络中的分簇算法 J.无线通信技术,2006,15(3):47-51,62.沈波，张世永,钟亦平.无线传感器网络分簇路由协议J. 软件学报,2006,17(7):1588-

40、1600.HEINZELMAN W R, CHANDRAKASAN A, BALAKRISHNAN H. Energy-efficient communication protocols for wireless microsensor networksC/Proc of the 33rd Hawaii International Conference on System Sciences. Washington DC:IEEE ComputerSociety, 2000.KARL H, WILLIG A. Protocols and architectures for wireless se

41、nsor networksM. Beijing:Publishing House of Electronics Industry, 2007.HEINEELMAN W, CHANDRAKASAN A, BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networksJ. IEEE Trans on Wireless Communications, 2002,1(4):660-?670.BAKER D, EPHREMIDES A. The architectural or

42、ganization of a mobile? radio network via a distributed algorithmJ. IEEE Trans on Communications, 1981, 29(11):1694-?1701.HANDY M J, HAASE M, TIMMERMANN D. Low energy adaptive clustering hierarchy with deterministic cluster-head selectionC/Proc of the 4th International Workshop on Mobile and Wireles

43、s Communications Network.2002:368-?372.YOUNIS O, FAHMY S. HEED: a hybrid, energy-efficient distributed clustering approach for Ad hoc sensor networksJ. IEEE Trans on Mobile Computing, 2004,3(4):366-?379.CHATTERJEE M, DAS S K, TRUGUT D. WCA: a weighted clustering algorithm for mobile Ad hoc networksJ

44、. Cluster Computing Journal, 2002,5(2):193-?204.CHAN Hao-wei, PERRIG A. ACE: an emergent algorithm for highly uniform cluster formationC/Proc of the 1st European Workshop on Wireless Sensor Networks. Berlin:Springer, 2004:154-?171.孙利民，李建中陈渝.无线传感器网络M.北京:清华 大学出版社,2005.王威,唐文胜，罗娟.分簇算法中簇首分布及可靠性问 题研究J.计算机工程与应用,2007,43(27):133-136.MHATRE V, ROSENBERG C. Design guidelines for wireless sensor networks:communication, clustering and aggregationJ. Ad hoc