传感器分簇算法研究及其进展总结

《传感器分簇算法研究及其进展总结》由会员分享，可在线阅读，更多相关《传感器分簇算法研究及其进展总结（9页珍藏版）》请在金锄头文库上搜索。

1、无线传感器网络（WSN在军事、环境监测、工业控制、智能家居和城市交通 等方面都有重要的实用价值，已成为热点研究领域之一。对应于不同的应用需求, 各种WSNS硬件平台、软件系统和通信协议上都存在较大差异。 从网络拓扑的角 度看，WSNT以被分为平面结构以及分簇结构两大类。平面结构中 WSK节点的 地位都是平等的，而在分簇结构中，网络中的节点被划分为若干个称为簇的节点 集合，每个簇通常由一个簇头节点和多个成员节点组成， 簇头负责管理和控制簇 成员节点的工作，同时负责簇内数据收集及簇间数据转发。与平面结构相比，采 用分簇结构的WSN有能量效率高、可扩展性好等优点，但是如何选取簇头、划 分簇类，需要合

2、适的分簇算法加以解决。1 WSN中的分簇架构0就探节息0：醺直哥仔点一：睽自建比一：旗内建cs在采用分簇结构的无线传感器网络中，网络节点被划分为若干个簇。每 个簇通常由一个簇头节点（CH）以及多个成员节点（MN）组成。成员节点只与簇头通 信,簇头与簇头构成高一级的虚拟骨干网，负责簇内的数据融合和簇间数据转发。 因为簇头节点的能量消耗较大，通常采用周期性选择簇头节点的方法均衡网络中 节点能量的消耗。簇头的集合形成连通统治集 （CDS）,因为获得最优CDS是NPC 问题，因此实际提出的算法均为启发式的。 图1给出了分簇结构以及簇内与簇间 的数据流向。*图1及苴修内与诬间的 处辑遑问WSNK用分簇结

3、构具有如下一些显著的优点:在满足一定约束条件情况下（ 例如覆盖范围与采样精度要求等） ， 簇成员节点可以在某些时间段内关闭通信模块，大幅度减少空闲等待状况的能量消耗，因此可节省能量。簇头通常负责采集簇成员发送来的数据，这些数据具有较大的相关性，因此可以采用数据融合算法，在保证信息量的情况下降低数据通信量，降低数据转发的能量开销。因为采用层次结构，簇成员只需了解到所属簇头的路由信息，簇头只需了解簇头间的路由信息， 因此可降低路由协议的复杂度，减少路由表项数目，路由维护开销也随之降低。具有较好的可扩展性能，更加适合于大规模WSN勺应用场景。2.1 集中式 /分布式算法根据是否存在一个中心控制节点（

4、 通常是基站） 负责整个网络的簇划分，分簇算法可分为集中式与分布式两类。典型的集中式算法有LEACH-C2、 APTEEN3等。我们提出的基于径向基函数（RBF）的分簇算法4也属于此类。中心控制节点通常有持续的电源供应、较高的存储与计算能力，并能获得网络的全局信息（ 如每个节点的位置以及剩余能量等） ，因此可以采用复杂的算法获得优化的分簇结果。 但是由于普通无线传感器节点能量有限，计算与通信能力不强，因此对于大型的WSN集中式算法在灵活性、可扩展性以及健壮性等方面存在缺陷，例如很多集中式算法要求获得节点的剩余能量，因为传感器节点运行中能量不断下降，所以必须隔一段时间就得通知中心控制点更新剩余能

5、量信息，这就造成大量额外数据包的传输，使算法的开销过大。与集中式算法不同，分布式算法一般只需要相邻节点之间互相交换信息，甚至不考虑相邻节点独立作出判断，这类算法简单、高效、灵活，因此更适用于大规模WSN目前大部分经典的 WS的簇算法如LEACH HEED5隹，都属于分布式算法，Hausdorff算法6、响应式分布分簇算法（RDCA）7也属于这一类。2.2 基于地理位置/地理位置无关算法根据是否需要借助GPSt得节点的地理位置，可以将分簇算法分为基于地理位置的算法与地理位置无关算法两类。 典型的基于地理位置的算法有 GAF8等, 其他大部分常见的分簇算法，如 LEACHf HEEDJ法等，都不需

6、要借助于地理位 置信息。 基于地理位置的算法有的需要获得全局信息，有的只需要通过广播包获得相邻节点的位置信息。因为传感器网络节点数量大，单个节点造价低、能量有限，而GPS真块不但成本高而且会额外消耗节点能量，因此为每个节点都配备 GPS真块是不经济的。通常的做法是在网络中设置少量信标节点，一般是通过携 带GPS1位设备获得自身的精确位置，然后其他传感器节点通过信标节点的位置 信息根据一定的定位算法获得自身的位置。常用的定位算法有到达时间（TOA）、到达时间差（TDOA接收信号强度指示（RSSI）、到达角度（AOA刖距离向量-跳数 （DV-Hop）9等。不过在室内、水下或森林等有障碍环境中无法使

7、用GPS系统，使其应用受到一定限制。基于地理位置的分簇算法一般假设节点已知自身的精确位置，而如何获得自身位置信息则不包括在算法内。2.3 确定性 /随机性算法在网络拓扑结构与每个节点的剩余能量不变的情况下，根据分簇算法是否能取得确定结果，可将其分为确定性与随机性算法。在确定性算法中，节点必须等待某个特定事件发生或某些特定节点已宣布自己的角色 （CH还是MN后，才能做 出决定。例如DCAK法10必须等待所有权值高于自己的相邻节点宣布成为CH或者加入到某个簇后，才能确定自身是成为 CH还是MN确定性算法的一个不足 之处就是收敛时间依赖于网络规模，DCAT法的时间复杂度为O（d ） , d为网络 直

8、径 （ 通常用跳数来定义） ，在最差情况下（ 节点线性分布） ， d 可达到 n -1（n 为节点个数）。此外网络的鲁棒性不好，如果一个节点在拓扑发现阶段后失效，可能造成其相邻节点陷入无限期等待。 为消除这种现象，一些算法，例如ACE算法 限制节点在一定次数（ 如 5 次后 ） 结束循环等待11 。随机性算法根据一定的概率确定节点是否成为簇头。 LEACHT法中节点成为 簇头的概率仅与过去若干轮次中节点自身的状态有关， HEED（法中的概率与剩 余能量有关，还有一些算法同时考虑了节点度等多种参数。随机性算法分簇结果的优化程度通常不如确定性算法，但是收敛速度较快，开销较小，鲁棒性好，特 别适合于

9、大规模网络。2.4 单层 /多层算法根据算法产生的最终拓扑结构，可分为单层和多层算法。单层算法只进行一次分簇，目前提出的大部分分簇算法，如 LEACH HEAD GAF?都属于此类，而多层算法在前一次分簇选举出的簇头基础上继续进行分簇，选举出第二层簇头和簇成员节点，随后可以进行第三层、第四层等簇头选举。多层算法一般只用于超大规模WSN算法较为复杂。文献12提出了一种多层算法（层数从1到5）,该算法以最小化系统整体能量消耗为目标，推导出系统整体能量消耗的解析式，然后通过数值计算求出不同节点密度条件下的最优解。2.5 簇内单跳/多跳算法根据簇内MNiIJ CH的跳数，可分为簇内单跳与簇内多跳算法，

10、也可采用单跳 算法的MNft接与CH进行通信，而多跳算法中的 MNW通过其他Mhfr继与CH1 行通信。LEACH HEE劳算法采用单跳方式，而Max-min D等算法使用多跳方式。Mhatre 等对簇内单跳和多跳的情况做了深入研究13 ，提出以簇内第一个节点死亡作为簇的生命周期（不考虑CH的能耗）并假设所有MN的初始能量相同。 单跳情况下，离CH越远的MNffi早耗尽能量；多跳情况下，如果 MN的发射功率 相同，则离CH最近的MN因为负担的中继任务最重故消耗的能量最多。 其分析存 在的缺陷是只考虑了节点发送以及接收状态下消耗的能量，没有考虑空闲状态下的能量消耗。目前很多 WSNH入节点睡眠/

11、唤醒机制，在无感知以及数据传送的情况下关闭射频电路以节省能量。当引入这种机制后，网络拓扑会发生动态变化，很难给出一个确定性的解析式，一般只能采用概率分析的方法并通过仿真得出结果。当采用单跳模式时，MNt CH的通信可以采用TDMA&式，每个MN配一个时隙， 数据传送只在指配的时隙中进行，其余时间处于睡眠状态，大大降低了节点处于空闲状态的时间（如LEACH）而采用多跳模式时，因为节点还需考虑数据 中继问题，不可避免会耗费较多的等待时间。从这一点上看，单跳方式与多跳方式相比具有一定优势。3 分簇算法设计难点从网络协议分层上看，分簇算法可以看做是拓扑控制的一大类，位于 MAC层与网络层之间。在算法设

12、计中，需要考虑网络连通性、CH仑转频率、簇半径优化以及节点同步等一系列问题，对这些问题的深入研究可以从跨层设计的角 度，结合MAC!、网络层甚至应用层进行。3.1 连通性问题WS即，保持节点到基站的连通性是极为重要的。对于采用分簇结构的无线 传感器而言，连通性问题包括 MNgJ CH（!内通信）以及CHgJ基站（簇间通信）两 个层次的连通性。如前所述，簇内通信分为单跳与多跳两种模式，一般由成簇算法确保连通性问题。而簇间通信需要通过虚拟骨干网进行，根据构成虚拟骨干网的节点不同，可将簇间通信分为两大类。大部分虚拟骨干网完全由CH节点构成（如HEEEM法），为保证连通性，这一类算法要求节点发射功率可

13、调， 且CH的密 度和覆盖范围满足一定的条件14;另一些虚拟骨干网则由CHW簇边缘的网关 节点（GN）构成，如CEO法15, 一般适用于使用固定发射功率的网络。 两类方 法相比，前者的优势在于非CH节点在没有感知及数据发送任务时可以进入睡眠 状态， 因此更加节省能量。连通性所带来的簇半径以及簇间通信范围的优化选取问题仍然是分簇算法研究的一个重点。3.2 MAC层设计通常进行分簇算法分析和仿真时都假设信道是无冲突的，而在实际情况下，尤其是单信道环境下，冲突和干扰不可避免。分簇算法经常使用TDMAg式的MAC 层协议，使用TDMAT式虽然能够消除簇内通信冲突，对相邻簇之间的簇间冲突 却无能为力，当

14、CH为进行簇间通信而提高发射功率时，这种冲突带来的影响更 为明显。使用CDMAT式可以使簇内通信与簇间通信并发进行成为可能，但CDMA器件价格昂贵，难以在强调低成本的无线传感器节点中大规模使用。如何设计与选用合适的MAC1协议降低冲突与干扰，也是分簇算法研究的难点之一。3.3 簇头轮换机制WSN 勺设计以最大化网络生命期为最终目标，因而使各节点尽可能均衡地消耗能量极为重要。而分簇算法中一般 CH的能量消耗大大高于MN容易造成CH 节点因为能量耗尽而提前死亡，为避免这一情况出现，一种方式就是采用簇头轮换机制， 使各节点每隔一段时间轮流担任簇头，从而使各节点剩余能量尽可能接近相等。 簇头轮换机制通

15、常独立于分簇算法，与分簇算法互为补充。常见的簇头轮换机制有被动与主动式两种。前者每隔固定时间引发，后者需要预先设定一个阀值， 当监视的参数低于或者超过某阀值时引发重新分簇，常见的阀值有节点剩余能量、 节点度等。无论是被动还是主动式簇头轮换机制，选择合适的参数都会对算法的最终结果产生重要影响。如果簇头轮换过于频繁，则会带来大量的额外开销和网络中断；如果簇头轮换频率过低，则可能造成某些节点能量过早耗尽。 因此，只有进行合理的折中才能获得最优化的网络生命期。3.4 节点休眠/唤醒机制采用节点休眠/唤醒机制，使非活跃节点尽可能处于睡眠状态可以大大延长节点电池寿命。WSNE节点部署时一般是高度冗余的，即只需要一部分节点处于 活跃状态就可以完成任务，这是引入休眠/ 唤醒机制的前提条件。WSN是应用相关的，不同应用层业务适宜采用的休眠/唤醒机制也有所不同。 对于周期性数据采集网络（例如用于环境监测的网络），非CH节点在不需要进行 感知或者与CH通信时将尽可能地处于休眠状态。对于突发事件监测网络（例如用 于森林防火、入侵检测等），CHP将所属的MN分为若干个冗余组，通知各组 轮流进入睡眠