论文部分内容阅读
摘 要 介绍了无线传感器网络分簇路由协议的相关技术及其优点，总结了近年来提出的各种分簇协议及主要设计思想.首先介绍了无线传感器网络分簇协议的相关技术及优点；然后介绍了近几年代表性的分簇路由算法研究工作，并且对其涉及的主要方法进行分类分析；最后进行了各种分簇路由协议的综合比较，并指出了无线传感器网络分簇路由协议面临的问题和挑战以及今后的发展方向。
关键词 无线传感器网络 分簇算法 路由协议
无线传感器网络（WSN）是一种无线自组织网络，它包含成百上千的传感器节点，每一个节点有感知环境、执行简单的计算与其他临近节点或基站（ase station，简称BS）直接通信的能力，能在事先没有构建网络基础设施的环境下，由传感器节点临时组成的一种自组织、自管理的网络[1，2]。
路由是指从源节点选择一条节能、距离短的路径到目的节点，在形式上，可以将无线传感器网络看做无向图，从源节点到目的节点选择一条最短的路径是一个复杂组合问题（即NP完全问题）[3]，这其中要考虑很多因素，诸如：能量消耗、数据包传输时延、能量有效性。由于传感器节点的电源能量、计算能力和通信能力都非常有限，所以节能路由协议的设计，对无线传感器网络来说极其重要。
近来，科学界对无线传感器网路分簇协议[4]进行了深入的研究，分簇网络结构由于具有良好的网络扩展性，便于能量管理、平衡负载、资源分配等，成为目前国内外延长WSN生命周期、降低每一个节点的能耗的主要方法之一。
1 分簇算法相关的技术
1.1 定位技术
位置信息是传感器网络节点采集数据中不可缺少的部分，没有位置的监测信息通常是毫无意义的，因此定位技术对于要求有精确位置信息的无线传感器网络分簇协议来说具有重要的意义。根据定位过程中是否测量节点间的距离和角度，把无线传感器网络中的定位技术分为基于距离的定位技术和距离无关的定位技术。
1.1.1 基于距离的定位技术
基于距离的定位机制是通过测量相邻节点间的实际距离或方位来确定位置节点的位置，通常采用测距、定位和修正等步骤实现。基于距离的定位机制分为基于TOA[5]的定位、基于TDOA[1]的定位、基于AOA[6]的定位和基于RSSI[7]的定位等。
1.1.2 距离无关的定位技术
距离无关的定位机制无须实际测量节点间的绝对距离或方位就能够确定未知节点的位置，目前提出的定位机制主要有质心算法[1]、DV-Hop[8]算法、Amorphous[9]算法和APIT[10]算法等。
1.2 同步技术
时间同步是需要协同工作的传感器网络分簇协议的一个关键机制。目前已提出了多个时间同步机制，其中RBS、TINY/MINI-SYNC和TPSN被认为是三个基本的同步机制。
（1）RBS机制[11，12]是基于接收者-接收者的时钟同步：一个节点广播时钟参考分组，广播域内的两个节点分别采用本地时钟记录参考分组的到达时间，通过交换记录时间来实现他们之间的时钟同步。
（2）TINY/MINI-SYNC是简单的轻量级的同步机制[1]：假设节点的时钟漂移遵循线性变化，那么两个节点之间的时间偏移也是线性的，可通过交换时标分组来估计两个节点间的最优匹配偏移量。
（3）TPSN[13，14]采用层次结构实现整个网络节点的时间同步：所有节点按照层次结构进行逻辑分级，通过基于发送者——接收者的节点对方式，每个节点能够与上一级的某个节点进行同步，从而实现所有节点都与根节点的时间同步。
1.3 数据融合技术
数据融合技术[15]是指从各个传感器节点收集数据的过程中，可利用节点的本地计算和存储能力处理数据的融合，去除冗余信息。目前数据融合技术已经在目标跟踪、目标自动识别等领域得到了广泛的应用。在无线传感器分簇网络的设计中，只有面向应用需求设计具有针对性的数据融合方法，才能最大限度地获益。
2 基于分簇的传感器路由协议的优点
与传统的无线传感器网络路由协议相比，基于分簇的无线传感器路由协议优点有[16，17]：
（1）自适应性：通过簇头节点的周期性轮换以及簇成员的加入或者退出来实现持续的监测和数据采集。
（2）节能性：由于基站远离网络，节点与基站的通信是能耗最高的操作，对网络进行分簇后，簇头负责将整个簇的数据发送到基站，减少了与基站通信的节点数，大大降低了网络能耗。
（3）消除数据冗余：WSN中存在着大量的数据冗余，簇头在将本簇的数据发送到基站之前可进行数据融合和压缩操作以消除冗余，进一步减少与基站的通信量。
（4）鲁棒性：节点通过一种自组织的方式当选为簇首，收集当前簇内信息并在融合后转发给基站，把网络的负载均匀的分布在整个网络中，大大降低了通信过程中的能量消耗，也增强了网络的健壮性。
（5）局部/全局优化：与其他路由协议相比，分簇算法不仅能够对局部信息进行融合优化，而且还能够对全局信息进行优化。
（6）可扩展性：分簇算法容易与其他路由算法相结合，从而提高路由算法的性能。
3 基于分簇的无线传感器路由协议
LEACH[18]协议是一个典型的自适应分簇协议，它采用“轮”的概念，每轮分为簇的建立和数据传输两个阶段。簇的建立阶段：每个传感节点随机选择一个0～1 之间的值，如果小于给定的阈值T（n），则选择为簇首。T（n）的计算方法如下：
其中： P 为节点中成为簇头的百分数（大约占节点总数的5%-6%左右）[19]， r 是当前的轮数， G 是在过去的1/ P 轮没有被选择为簇头节点的集合，mod 是求模运算。一旦簇首被选定，它们便向周围节点广播这一信息，非簇首节点依据接收信号的强弱来选择它所要加入的簇，并通知相应的簇首节点，完成簇的建立。数据传输阶段：节点周期性的采集监测数据，基于时分复用（TDMA）的方式发送给簇首，簇首在进行必要的数据聚集和融合之后，将处理过的数据发送到基站。数据传输持续一段时间后，整个网络进入下一轮，不断循环。L EACH协议使用了分布式算法，使得任务被分散到每个传感器节点上，有效地减少了每个节点的负载，延长了传感器网络的生存时间。基于L EACH的路由协议是无线传感器网络中分簇路由协议中的研究基础，它采用随机簇头选择机制，能够较好地实现能量均衡消耗，但L EACH协议还存在以下缺点：①每一轮都进行一次簇重组，带来了大量额外开销；②根据公式（1）的簇首选举策略来选取簇首，可能造成簇首分布不均，簇内成员个数差异较大，使得各簇首负载不均衡，造成个别簇首较早死亡；③簇内的节点都直接与簇首通信，增加了簇首的能量消耗；④簇首采用单跳的方式直接和基站通信，当网络规模很大时，通信的距离很大，对于能量受限的传感器网络节点来说，加速了节点的能量消耗，降低了网络的生存时间。
HEED[20]协议主要根据主、次两个参数，通过将能耗平均分布到整个网络来延长网络生存时间。其中簇首选择的主参数依赖于剩余能量，用于随机选取出簇首集合，具有较多剩余能量的节点将有较大的概率成为簇首；次参数依赖于簇内通信代价，用于确定落在多个簇范围内的节点最终属于哪个簇，以及平衡簇首间的负载。HEED协议主要改进之处是在簇首的选择中考虑了节点的剩余能量， 并以主次关系引入了多个约束条件。HEED协议分簇更快，能产生分布更加均匀的簇首、更合理的网络拓扑。
HEED协议与LEACH协议类似，但在簇首收集完数据后，簇首之间通过多跳的方式与基站通信。由于簇首的负担较重，LEACH和HEED协议都按“轮”进行，即周期性地重新选择簇首，分配TDMA时隙。但是基于簇的TDMA协议同时带来了簇间干扰问题。因为对于分布式的簇算法，最后形成簇的覆盖区域是有重叠的，即一个节点有可能在多个簇的覆盖之下，为此Xiong Zhuang[21]等人提出了一种消除无线传感器网络簇间干扰的TDMA协议，该协议分为三个阶段：第一阶段为簇建立阶段，在该阶段中采取LEACH改进算法DCHS[22] （Determ- inistic cluster-head selection）中的T（n）计算公式产生簇首，T（n）计算公式为：
关键词 无线传感器网络 分簇算法 路由协议
无线传感器网络（WSN）是一种无线自组织网络，它包含成百上千的传感器节点，每一个节点有感知环境、执行简单的计算与其他临近节点或基站（ase station，简称BS）直接通信的能力，能在事先没有构建网络基础设施的环境下，由传感器节点临时组成的一种自组织、自管理的网络[1，2]。
路由是指从源节点选择一条节能、距离短的路径到目的节点，在形式上，可以将无线传感器网络看做无向图，从源节点到目的节点选择一条最短的路径是一个复杂组合问题（即NP完全问题）[3]，这其中要考虑很多因素，诸如：能量消耗、数据包传输时延、能量有效性。由于传感器节点的电源能量、计算能力和通信能力都非常有限，所以节能路由协议的设计，对无线传感器网络来说极其重要。
近来，科学界对无线传感器网路分簇协议[4]进行了深入的研究，分簇网络结构由于具有良好的网络扩展性，便于能量管理、平衡负载、资源分配等，成为目前国内外延长WSN生命周期、降低每一个节点的能耗的主要方法之一。
1 分簇算法相关的技术
1.1 定位技术
位置信息是传感器网络节点采集数据中不可缺少的部分，没有位置的监测信息通常是毫无意义的，因此定位技术对于要求有精确位置信息的无线传感器网络分簇协议来说具有重要的意义。根据定位过程中是否测量节点间的距离和角度，把无线传感器网络中的定位技术分为基于距离的定位技术和距离无关的定位技术。
1.1.1 基于距离的定位技术
基于距离的定位机制是通过测量相邻节点间的实际距离或方位来确定位置节点的位置，通常采用测距、定位和修正等步骤实现。基于距离的定位机制分为基于TOA[5]的定位、基于TDOA[1]的定位、基于AOA[6]的定位和基于RSSI[7]的定位等。
1.1.2 距离无关的定位技术
距离无关的定位机制无须实际测量节点间的绝对距离或方位就能够确定未知节点的位置，目前提出的定位机制主要有质心算法[1]、DV-Hop[8]算法、Amorphous[9]算法和APIT[10]算法等。
1.2 同步技术
时间同步是需要协同工作的传感器网络分簇协议的一个关键机制。目前已提出了多个时间同步机制，其中RBS、TINY/MINI-SYNC和TPSN被认为是三个基本的同步机制。
（1）RBS机制[11，12]是基于接收者-接收者的时钟同步：一个节点广播时钟参考分组，广播域内的两个节点分别采用本地时钟记录参考分组的到达时间，通过交换记录时间来实现他们之间的时钟同步。
（2）TINY/MINI-SYNC是简单的轻量级的同步机制[1]：假设节点的时钟漂移遵循线性变化，那么两个节点之间的时间偏移也是线性的，可通过交换时标分组来估计两个节点间的最优匹配偏移量。
（3）TPSN[13，14]采用层次结构实现整个网络节点的时间同步：所有节点按照层次结构进行逻辑分级，通过基于发送者——接收者的节点对方式，每个节点能够与上一级的某个节点进行同步，从而实现所有节点都与根节点的时间同步。
1.3 数据融合技术
数据融合技术[15]是指从各个传感器节点收集数据的过程中，可利用节点的本地计算和存储能力处理数据的融合，去除冗余信息。目前数据融合技术已经在目标跟踪、目标自动识别等领域得到了广泛的应用。在无线传感器分簇网络的设计中，只有面向应用需求设计具有针对性的数据融合方法，才能最大限度地获益。
2 基于分簇的传感器路由协议的优点
与传统的无线传感器网络路由协议相比，基于分簇的无线传感器路由协议优点有[16，17]：
（1）自适应性：通过簇头节点的周期性轮换以及簇成员的加入或者退出来实现持续的监测和数据采集。
（2）节能性：由于基站远离网络，节点与基站的通信是能耗最高的操作，对网络进行分簇后，簇头负责将整个簇的数据发送到基站，减少了与基站通信的节点数，大大降低了网络能耗。
（3）消除数据冗余：WSN中存在着大量的数据冗余，簇头在将本簇的数据发送到基站之前可进行数据融合和压缩操作以消除冗余，进一步减少与基站的通信量。
（4）鲁棒性：节点通过一种自组织的方式当选为簇首，收集当前簇内信息并在融合后转发给基站，把网络的负载均匀的分布在整个网络中，大大降低了通信过程中的能量消耗，也增强了网络的健壮性。
（5）局部/全局优化：与其他路由协议相比，分簇算法不仅能够对局部信息进行融合优化，而且还能够对全局信息进行优化。
（6）可扩展性：分簇算法容易与其他路由算法相结合，从而提高路由算法的性能。
3 基于分簇的无线传感器路由协议
LEACH[18]协议是一个典型的自适应分簇协议，它采用“轮”的概念，每轮分为簇的建立和数据传输两个阶段。簇的建立阶段：每个传感节点随机选择一个0～1 之间的值，如果小于给定的阈值T（n），则选择为簇首。T（n）的计算方法如下：
其中： P 为节点中成为簇头的百分数（大约占节点总数的5%-6%左右）[19]， r 是当前的轮数， G 是在过去的1/ P 轮没有被选择为簇头节点的集合，mod 是求模运算。一旦簇首被选定，它们便向周围节点广播这一信息，非簇首节点依据接收信号的强弱来选择它所要加入的簇，并通知相应的簇首节点，完成簇的建立。数据传输阶段：节点周期性的采集监测数据，基于时分复用（TDMA）的方式发送给簇首，簇首在进行必要的数据聚集和融合之后，将处理过的数据发送到基站。数据传输持续一段时间后，整个网络进入下一轮，不断循环。L EACH协议使用了分布式算法，使得任务被分散到每个传感器节点上，有效地减少了每个节点的负载，延长了传感器网络的生存时间。基于L EACH的路由协议是无线传感器网络中分簇路由协议中的研究基础，它采用随机簇头选择机制，能够较好地实现能量均衡消耗，但L EACH协议还存在以下缺点：①每一轮都进行一次簇重组，带来了大量额外开销；②根据公式（1）的簇首选举策略来选取簇首，可能造成簇首分布不均，簇内成员个数差异较大，使得各簇首负载不均衡，造成个别簇首较早死亡；③簇内的节点都直接与簇首通信，增加了簇首的能量消耗；④簇首采用单跳的方式直接和基站通信，当网络规模很大时，通信的距离很大，对于能量受限的传感器网络节点来说，加速了节点的能量消耗，降低了网络的生存时间。
HEED[20]协议主要根据主、次两个参数，通过将能耗平均分布到整个网络来延长网络生存时间。其中簇首选择的主参数依赖于剩余能量，用于随机选取出簇首集合，具有较多剩余能量的节点将有较大的概率成为簇首；次参数依赖于簇内通信代价，用于确定落在多个簇范围内的节点最终属于哪个簇，以及平衡簇首间的负载。HEED协议主要改进之处是在簇首的选择中考虑了节点的剩余能量， 并以主次关系引入了多个约束条件。HEED协议分簇更快，能产生分布更加均匀的簇首、更合理的网络拓扑。
HEED协议与LEACH协议类似，但在簇首收集完数据后，簇首之间通过多跳的方式与基站通信。由于簇首的负担较重，LEACH和HEED协议都按“轮”进行，即周期性地重新选择簇首，分配TDMA时隙。但是基于簇的TDMA协议同时带来了簇间干扰问题。因为对于分布式的簇算法，最后形成簇的覆盖区域是有重叠的，即一个节点有可能在多个簇的覆盖之下，为此Xiong Zhuang[21]等人提出了一种消除无线传感器网络簇间干扰的TDMA协议，该协议分为三个阶段：第一阶段为簇建立阶段，在该阶段中采取LEACH改进算法DCHS[22] （Determ- inistic cluster-head selection）中的T（n）计算公式产生簇首，T（n）计算公式为：