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

减小字体 增大字体 作者:王声才 李艾华 王 涛 张 波  来源:www.zhonghualunwen.com  发布时间:2009-10-12 14:46:35

  随着无线传感器自组网络规模的扩大,平面路由方案会因链路处理开销的增加和动态反应速度的降低而变得不适用,解决办法之一是采用成簇的路由方案。在成簇算法中,网络由多个簇组成,每个簇包括簇首和成员两种类型的节点,处于同一簇内的簇首和成员节点共同维护所在簇内的路由信息。簇首节点负责所管辖簇内拓扑信息的压缩和融合处理,并与其他簇首节点交换处理后的拓扑信息,直到传感数据传送至基站[1]。
  采用成簇的路由思路的目的是:a)通过减少参与路由计算的节点数目,减小路由表尺寸,降低交换路由信息所需的通信开销和维护路由表所需的内存开销[2];b)基于某种簇生成策略产生较为稳定的子网络,减少拓扑结构变化对路由算法的影响[3];c)簇成员节点定期苏醒上传数据至簇首并融合,大大减少节点能耗和数据通信量,从而提高网络寿命[4]。
  
  1 无线传感器网络簇运算概述
  
  学术界对Ad hoc网络的研究比WSN要早,目前已经提出了很多针对Ad hoc网络的分簇路由算法,如采用LCC(least cluster change)算法形成簇结构的CGSR协议、结合按需和主动路由策略的ZRP(zone routing protocol)算法等[1],而无线传感器网络中的分簇算法正处于研究阶段。同Ad hoc网相比,WSN中的分簇算法更侧重于保持网络整体能量消耗的均衡,避免出现“热点”问题,最大化地延长网络生存时间[5,6]。
  LEACH是MIT的Heinzelman等人专门为WSN设计的低功耗自适应分层路由算法[7],也是WSN中最早提出的成簇路由算法。它的基本思想是以循环的方式随机选择簇首节点,将整个网络的能量负载平均分配到每个传感器节点中,从而达到降低网络能源消耗、提高网络整体生存时间的目的。这个思想贯穿于后来的很多簇算法研究之中,成为簇运算的基点。
  LEACH算法将簇的建立过程分为三个阶段,即簇首节点的选择、簇的组织和簇的连接 [6]。从目前的文献来看,对簇算法的研究大多是从这三个方面着手。
  
  2 簇首的选择
  
  成为簇首意味着要肩负额外的任务,即组织簇内媒体的接入、节点数据的融合和路由决策的选择。这是一个密集型操作,所以它必须通过轮换所有节点的角色使簇首的能量不会消耗过多。为了能进行簇首的轮换,分簇算法不能只运行一次,而必须重复执行。例如,这种重复可以周期性出现或由节点的移动触发。当然,合理地选择周期和触发阈值是一个很重要的优化问题[8]。
  按照成簇的方式可以将传感网络分为分布式和集中式两种类型。当网络是分布式时,簇首选举侧重于节点能量的均衡;当网络是集中式时,簇首选举更侧重于簇首分布的均匀性。
  2.1 分布式网络
  在分布式网络中,各节点具有同等地位,它们之间通过信息交互实现对邻居节点的感知。在进行簇首选择时,基本上都是围绕着某个指标来进行,如ID号、剩余能量、节点度、权值、定时器和属性等。通过这些指标的比较来进行簇首的选择。这些策略中,有效果好的也有效果差的,有简单的也有复杂的,但都是为了解决一个问题,那就是均衡各个节点的能量,让网络的寿命更长。
  2.1.1 LEACH算法
  LEACH算法[9]是最早也是最基本的分簇算法。簇首节点的选择依据网络

[1] [2] [3] [4] [5] [6]  下一页

Tags:

作者:王声才 李艾华 王 涛 张 波
  • 好的评价 如果您觉得此文章好,就请您
      0%(0)
  • 差的评价 如果您觉得此文章差,就请您
      0%(0)

文章评论评论内容只代表网友观点,与本站立场无关!

   评论摘要(共 0 条,得分 0 分,平均 0 分) 查看完整评论