基于能量均衡的无线传感网分簇拓扑算法研究(5)
2.2.2 基于地理位置/地理位置无关算法
根据是否需要借助GPS获得节点的地理位置，可以将分簇算法分为基于地理位置的算法与地理位置无关算法两类。典型的基于地理位置的算法有GAF等，其它大部分常见的分簇算法，如LEACH与HEED算法等，都不需要借助于地理位置信息。基于地理位置的算法有的需要获得全局信息，有的只需要通过广播包获得相邻节点的位置信息。因为传感器网络节点数量大，单个节点造价低、能量有限，而GPS模块不但成本高而且会额外消耗节点能量，因此为每个节点都配备GPS模块是不经济的。通常的做法是在网络中设置少量信标节点，一般是通过携带GPS定位设备获得自身的精确位置，然后其他传感器节点通过信标节点的位置信息根据一定的定位算法获得自身的位置。不过GPS系统应用会受到一定条件的限制，如在室内、水下或森林等有障碍环境中无法使用。基于地理位置的分簇算法一般假设节点已知自身的精确位置，而如何获得自身位置信息则不包括在算法内。
2.2.3单层/多层算法
根据算法产生的最终拓扑结构，可分为单层和多层算法，如图5所示。单层算法只进行一次分簇，目前提出的大部分分簇算法，如LEACH、HEAD、GAF等都属于此类，而多层算法在前一次分簇选举出的簇头基础上继续进行分簇，选举出第二层簇头和簇成员节点，随后可以进行第三层、第四层等簇头选举。多层算法一般只用于超大规模无线传感器网络，算法较为复杂。
图5 单层、多层算法成簇示意图
2.2.4 确定性/随机性算法
在网络拓扑结构与每个节点的剩余能量不变的情况下，根据分簇算法是否能取得确定结果，可将其分为确定性与随机性算法。在确定性算法中，节点必须等待某个特定事件发生或某些特定节点已宣布自己的角色之后才能做出决定。确定性算法的一个不足之处就是收敛时间依赖于网络规模。此外网络的鲁棒性不好，如果一个节点在拓扑发现阶段后失效，可能造成其相邻节点陷入无限期等待。为消除这种现象，一些算法会限制节点在一定时间后结束循环等待。
随机性算法根据一定的概率确定节点是否成为簇头。LEACH算法中节点成为簇头的概率仅与过去若干轮次中节点自身的状态有关，HEED算法中的概率与剩余能量有关，还有一些算法同时考虑了节点度等多种参数。随机性算法分簇结果的优化程度通常不如确定性算法，但是收敛速度较快，开销较小，鲁棒性好，比较适合于大规模网络的应用。
2.2.5 簇内单跳/多跳算法
根据簇内成员节点到簇头节点的跳数，可分为簇内单跳与簇内多跳算法，也可采用单跳算法的成员节点直接与簇头节点进行通信，而多跳算法中的成员节点可通过其他成员节点中继与簇头节点进行通信。LEACH、HEED等算法均采用单跳方式，而Max-min D等算法则使用多跳方式。
目前很多的无线传感器网络引入节点睡眠/唤醒机制，在无感知以及数据传送的情况下关闭射频电路以节省能量。当引入这种机制后，网络拓扑会发生动态变化，很难给出一个确定性的解析式，一般只能采用概率分析的方法并通过仿真得出结果。当采用单跳模式时，成员节点与簇头节点的通信可以采用TDMA方式，每个成员节点分配一个时隙，数据传送只在指配的时隙中进行，其余时间处于睡眠状态，大大降低了节点处于空闲状态的时间。而采用多跳模式时，因为节点还需考虑数据中继问题，不可避免会耗费较多的等待时间。从这一点上看，单跳方式与多跳方式相比具有一定优势。
2.3 分簇算法设计难点
下一篇：贝叶斯波束形成算法研究+文献综述