无线传感器网络分簇路由协议研究

无线传感器网络分簇路由协议研究

无线传感器网络（wsd）是一个无线传感器网络，包含数千台传感器节点。每个节点都能感知环境，执行简单的计算，并与其他相邻节点或基站（base节点，bs）直接通信。在没有网络基础设施的情况下，传感器节点可以临时组成自己的组织和管理网络。路由是指从源节点选择一条节能、距离短的路径到目的节点,在形式上,可以将无线传感器网络看做无向图,从源节点到目的节点选择一条最短的路径是一个复杂组合问题(即NP完全问题),这其中要考虑很多因素,诸如:能量消耗、数据包传输时延、能量有效性。由于传感器节点的电源能量、计算能力和通信能力都非常有限,所以节能路由协议的设计,对无线传感器网络来说极其重要。近来,科学界对无线传感器网路分簇协议进行了深入的研究,分簇网络结构由于具有良好的网络扩展性,便于能量管理、平衡负载、资源分配等,成为目前国内外延长WSN生命周期、降低每一个节点的能耗的主要方法之一。1对于集群算法的技术1.1无线传感器网络分簇协议的定位技术位置信息是传感器网络节点采集数据中不可缺少的部分,没有位置的监测信息通常是毫无意义的,因此定位技术对于要求有精确位置信息的无线传感器网络分簇协议来说具有重要的意义。根据定位过程中是否测量节点间的距离和角度,把无线传感器网络中的定位技术分为基于距离的定位技术和距离无关的定位技术。1.1.1节点位置控制基于距离的定位机制是通过测量相邻节点间的实际距离或方位来确定位置节点的位置,通常采用测距、定位和修正等步骤实现。基于距离的定位机制分为基于TOA的定位、基于TDOA的定位、基于AOA的定位和基于RSSI的定位等。1.1.2未知节点位置定位距离无关的定位机制无须实际测量节点间的绝对距离或方位就能够确定未知节点的位置,目前提出的定位机制主要有质心算法、DV-Hop算法、Amorphous算法和APIT算法等。1.2节点时钟同步时间同步是需要协同工作的传感器网络分簇协议的一个关键机制。目前已提出了多个时间同步机制,其中RBS、TINY/MINI-SYNC和TPSN被认为是三个基本的同步机制。1)RBS机制是基于接收者-接收者的时钟同步:一个节点广播时钟参考分组,广播域内的两个节点分别采用本地时钟记录参考分组的到达时间,通过交换记录时间来实现他们之间的时钟同步。2)TINY/MINI-SYNC是简单的轻量级的同步机制:假设节点的时钟漂移遵循线性变化,那么两个节点之间的时间偏移也是线性的,可通过交换时标分组来估计两个节点间的最优匹配偏移量。3)TPSN采用层次结构实现整个网络节点的时间同步:所有节点按照层次结构进行逻辑分级,通过基于发送者--接收者的节点对方式,每个节点能够与上一级的某个节点进行同步,从而实现所有节点都与根节点的时间同步。1.3去冗余信息数据融合技术是指从各个传感器节点收集数据的过程中,可利用节点的本地计算和存储能力处理数据的融合,去除冗余信息。目前数据融合技术已经在目标跟踪、目标自动识别等领域得到了广泛的应用。在无线传感器分簇网络的设计中,只有面向应用需求设计具有针对性的数据融合方法,才能最大限度地获益。2分簇算法的特点与传统的无线传感器网络路由协议相比,基于分簇的无线传感器路由协议优点有:1)自适应性:通过簇头节点的周期性轮换以及簇成员的加入或者退出来实现持续的监测和数据采集。2)节能性:由于基站远离网络,节点与基站的通信是能耗最高的操作,对网络进行分簇后,簇头负责将整个簇的数据发送到基站,减少了与基站通信的节点数,大大降低了网络能耗。3)消除数据冗余:WSN中存在着大量的数据冗余,簇头在将本簇的数据发送到基站之前可进行数据融合和压缩操作以消除冗余,进一步减少与基站的通信量。4)鲁棒性:节点通过一种自组织的方式当选为簇首,收集当前簇内信息并在融合后转发给基站,把网络的负载均匀的分布在整个网络中,大大降低了通信过程中的能量消耗,也增强了网络的健壮性。5)局部/全局优化:与其他路由协议相比,分簇算法不仅能够对局部信息进行融合优化,而且还能够对全局信息进行优化。6)可扩展性:分簇算法容易与其他路由算法相结合,从而提高路由算法的性能。3打造网络一体化共享平台,提高网络抗扰能力LEACH协议是一个典型的自适应分簇协议,它采用“轮”的概念,每轮分为簇的建立和数据传输两个阶段。簇的建立阶段:每个传感节点随机选择一个0~1之间的值,如果小于给定的阈值T(n),则选择为簇首。T(n)的计算方法如下:其中:P为节点中成为簇头的百分数(大约占节点总数的5%-6%左右),r是当前的轮数,G是在过去的1/P轮没有被选择为簇头节点的集合,mod是求模运算。一旦簇首被选定,它们便向周围节点广播这一信息,非簇首节点依据接收信号的强弱来选择它所要加入的簇,并通知相应的簇首节点,完成簇的建立。数据传输阶段:节点周期性的采集监测数据,基于时分复用(TDMA)的方式发送给簇首,簇首在进行必要的数据聚集和融合之后,将处理过的数据发送到基站。数据传输持续一段时间后,整个网络进入下一轮,不断循环。LEACH协议使用了分布式算法,使得任务被分散到每个传感器节点上,有效地减少了每个节点的负载,延长了传感器网络的生存时间。基于LEACH的路由协议是无线传感器网络中分簇路由协议中的研究基础,它采用随机簇头选择机制,能够较好地实现能量均衡消耗,但LEACH协议还存在以下缺点:(1)每一轮都进行一次簇重组,带来了大量额外开销;(2)根据公式(1)的簇首选举策略来选取簇首,可能造成簇首分布不均,簇内成员个数差异较大,使得各簇首负载不均衡,造成个别簇首较早死亡;(3)簇内的节点都直接与簇首通信,增加了簇首的能量消耗;(4)簇首采用单跳的方式直接和基站通信,当网络规模很大时,通信的距离很大,对于能量受限的传感器网络节点来说,加速了节点的能量消耗,降低了网络的生存时间。HEED协议主要根据主、次两个参数,通过将能耗平均分布到整个网络来延长网络生存时间。其中簇首选择的主参数依赖于剩余能量,用于随机选取出簇首集合,具有较多剩余能量的节点将有较大的概率成为簇首;次参数依赖于簇内通信代价,用于确定落在多个簇范围内的节点最终属于哪个簇,以及平衡簇首间的负载。HEED协议主要改进之处是在簇首的选择中考虑了节点的剩余能量,并以主次关系引入了多个约束条件。HEED协议分簇更快,能产生分布更加均匀的簇首、更合理的网络拓扑。HEED协议与LEACH协议类似,但在簇首收集完数据后,簇首之间通过多跳的方式与基站通信。由于簇首的负担较重,LEACH和HEED协议都按“轮”进行,即周期性地重新选择簇首,分配TDMA时隙。但是基于簇的TDMA协议同时带来了簇间干扰问题。因为对于分布式的簇算法,最后形成簇的覆盖区域是有重叠的,即一个节点有可能在多个簇的覆盖之下,为此XiongZhuang等人提出了一种消除无线传感器网络簇间干扰的TDMA协议,该协议分为三个阶段:第一阶段为簇建立阶段,在该阶段中采取LEACH改进算法DCHS(Determ-inisticcluster-headselection)中的T(n)计算公式产生簇首,T(n)计算公式为:其中:P是簇首占所有节点的百分比,即节点当选簇首的概率;r是目前循环进行的轮数;G是最近1/P轮中还未当选过簇首的节点集合。En_current是节点的当前能量,En_max是节点的初始能量,rs是节点连续未当选过簇首的轮次;第二阶段是TDMA调度表的生成,整个网络组网前必须根据网络模型定义TDMA调度表的时隙数M:其中:L是网内最大簇群内簇成员总和,与网络节点密度有关,K是簇额外时隙数,用于簇内命令广播、时间同步和突发事件消息传递等,P是簇首选举概率,J是预留全网时隙数,N是全网节点数;第三阶段是簇稳定运行阶段,分为簇首和簇成员两部分。该协议减少由于簇间干扰导致的数据碰撞,节省了整个分簇网络的能量,但是没有考虑簇首分布不均,簇内成员个数差异较大,使得各簇首负载不均衡的问题。为了解决簇首分布不均匀的问题,研究人员提出了LEACH-C(LEACH-Centralized)协议,LEACH-C协议是在LEACH协议的基础上改进的一种集中式的簇首选择机制,不同于LEACH分布式随机选择簇头的方式。每轮开始时各个节点把自身位置和当前能量报告给基站,能量高于平均值的节点成为候选簇首,然后采用模拟退火算法从候选节点中选出数量合适且位置最优的节点成为簇首,最后基站把分簇结果广播给每个节点。LEACH-C算法每轮选出的簇首数量稳定且分布均匀,但它需要网络的全局信息,可扩展性差。LEACH-F(LEACH-Fixed)也是在LEACH基础上做了一些改变,簇组织完成后即固定不变,而簇首实行轮转。这种方法减小了成簇开销,并且簇首分布总体上较为均匀,但可能导致节点离其他簇的簇首比离自己的簇首更近,增大了干扰和簇内通信开销,并且对于网络的变化无法响应。PEGASIS协议并不是严格意义上的簇类协议,但是它延用了簇的思想。节点通过定位技术来发现自己最近的邻居节点,然后从距离基站最远的节点开始,采用贪心算法把传感节点组织成一条链,节点只与距离它最近的邻居节点通信,并且每轮中只选一个节点作为领导节点与基站通信。PEGASIS中的数据传输使用令牌(Token)机制,首先将令牌传递给链两端的端节点,端节点向链中的邻节点发送数据,邻节点将自己的数据和接收到的数据进行数据融合处理,然后将融合后的数据再发送到下一个节点,最终由领导节点融合两边的数据并发送给基站。与LEACH协议相比,PEGASIS协议中的节点平均通信距离较短,也没有簇的重构开销,通过数据融合减少了发送次数,而且每一轮只有一个领导节点与基站通信,降低了能耗,但是PEGSIS采用令牌方式传送数据,先在簇的一侧融合数据,再在另一侧融合数据,增加了延迟。针对LEACH协议的缺点,结合PEGASIS协议优点,LiLaYuan等人提出了一种能量均衡的分簇路由协议(EBLP),基本思想是:网络运行时间仍以轮为基本单位进行分割,每轮进行簇首选择和数据传输,每隔N轮为一个周期对全网进行一次簇重组;在选择簇首时,首先计算出最优簇头数,并根据网络面积确定每个簇头间的最短距离,然后结合能量因素和改进后的阀值确定初始簇首;在建簇时,每个簇由簇首控制簇内节点数,使其在最优值,并且簇内节点利用贪心算法成链;簇首间通过建立的层次路由树选择一条最优路径把数据传送给基站;在传输数据时,每个周期的第一轮用初始簇首进行通信,之后每轮(根据改进后的阀值)选取链中节点剩余能量最大的节点作为链首,该链首也是本轮的簇首,传输数据,直到下一个周期的簇重组。EBLP协议在节点存活个数和全网的能量消耗上都明显优于LEACH协议和PEGASIS协议,延长了网络的生存时间。Manjeshwar等提出了TEEN协议。LEACH是响应型传感器网络协议,而TEEN协议是主动型网络协议。其基本思想是设置硬、软阈值以减少数据的传输量。阈值在每次簇头轮换时广播出去,节点监测到的数据第一次超过设置的硬阈值时,就把这次数据设为新的硬阈值,并在下一个时隙发给簇头。然后在以后的过程中,只有当监测到的数据超过硬阈值并且监测数据的变化幅度大于软阈值时,节点才会传送最新的监测数据。由于TEEN协议传送的数据量比响应型网络少得多,所以数据传送消耗的能量也少,从而TEEN协议在能量消耗方面要优于LEACH协议,但是TEEN协议存在两个问题:一方面,如果节点监测的数据一直不能超过设定的硬阈值,节点就不会传送数据,用户将无法得到任何数据,也不知道这个节点是否失效;另一方面,节点监测到合适的数据会实时传送数据,采用TDMA的机制会造成数据延迟。针对LEACH协议的缺点,TIANWei等人提出了一种新的位置感知分簇算法LACA(locationawareclusteringalgorithm)。该算法假设节点已知其位置信息,则可以计算出节点之间的距离和连线与水平线之间的夹角。通过引入角度比和距离比:其中Nx和Ny表示节点N的横纵坐标,Mx和My表示节点M的横坐标,R表示通信距离,这样就可以确定节点偏离理想簇头位置的程度。因此,只要设置合理的角度比和距离比阈值,节点就可以根据角度比和距离比自主决定是否作为簇头,从而形成较为理想的分簇结构,进而提高WSN的能量有效性,并通过η和δ阈值的合理设置,确保网络的可靠性。LACA算法无需建立、维护和存储路由表,无需网络拓扑信息,实现简单但是可扩展性差。GAF(GeographicAdaptiveFidelity)是以地理位置为依据的路由算法,网络被划分为若干固定区域,形成一个虚拟网格。节点通过GPS定位获取自己在网格中所处的“位置”,如果两个节点处在相同“位置”,则认为它们在路由上是等价的。等价节点中只需有一个处于工作状态,其余节点可以进入睡眠,大大节约了能量。因为传感器节点的体积和资源有限,该算法是基于节点地理位置进行分簇,这就对传感器节点提出更高的硬件要求。其次GAF是基于平面模型,算法忽略了一个问题,即实际网络中节点之间距离的邻近并不能代表节点之间可以直接通信。徐立等人提出了一种数据相关的无线传感器网络分簇算法。算法的基本过程为:在无向图的补集中寻找独立集,将找到的独立集作为一个分簇添加到簇集中,并将此独立集中的节点从无向图中删除,继续此过程直到删除全部节点,无向图已经被分为若干个不相交的簇。由于期望得到尽量少的簇,一个自然的贪婪算法为,每次将当前最大的独立集作为新的分簇,并且引入节点间数据相关性为簇头进行数据压缩和基站进行数据恢复提供依据。该算法大大降低了簇头与基站的通信量,减少了传感器节点的能量消耗,并且通过数据相关性实现了精确的能量高效的网络数据获取,但是传感器节点之间的数据关系往往存在比较复杂的相关性,具有很大挑战性。KawadiaV等人提出了CLUSTERPOW协议。CLUSTERPOW是一个针对非均匀分布网络的分簇路由协议。协议将网络根据不同的传输功率级进行一种隐式分簇,各簇内并不存在簇首或网关节点。每条路由则是由形成网络内各种簇结构的不同功率级所组成,节点以不同的功率级别发送HELLO消息对网络进行探测,并为每个功率级维护一个路由列表。在转发数据时,节点查找这些路由列表,以能够到达目的节点的最小功率级别的下一跳节点作为转发节点。CLUSTERPOW协议能够针对目的节点自适应地调整到最优发射功率,而不是全网使用统一的发射功率,如图1所示。它在非均匀分布网络中具有更好的能量效率。然而,每个节点需要为多个功率等级维护一个路由列表,这无疑会增加节点的存储负担。针对CLUSTERPOW中多个路由代理在探测网络时给网络带来大量额外开销从而增加网络能耗的问题,文献将DSDV(destinationsequenceddistancevector)路由与CLUSTERPOW相结合,提出适用于传感器网络CLUS-TERPOW-DSDV路由协议,从而通过减少路由开销降低网络的能量消耗。为了更好的改进无线传感器网络分簇协议的性能,研究人员在分簇算法中引入了智能算法,Ali-AsgharSalehpour为大规模基于簇的无线传感器网络提供了一个有效的路由算法(ERC),这个算法采用两层路由。在第一层中,簇成员直接将数据传递给他们的簇头(clusterhead),这些簇头是通过LEACH算法选择。第二层,这些簇头用ACO算法,找到一条最佳的去汇聚节点的路径,只能有簇头参与簇内路由。该算法具有很强的稳定性,并通过蚁群优化算法和分簇来减少算法的时延。基于遗传蚂蚁算法,BaoXi-rong等人提出了能量有效的分簇路由协议(ECGAC)。协议考虑了节点的能量水平、节点间相对的位置和整个网络能量的均衡。节点先成簇,然后,簇头通过多跳的方式把数据传送到汇聚节点。节点Ni计算它成为簇头的概率PCHi如下:其中,Ei代表节点目前的能量水平,α和β各自代表了节点到簇几何中心的距离与能量的权重值。簇头r上的蚂蚁i选择s作为下一跳节点基于下式:如果q<q0,否则,其中,q是一个均匀分布随机函数,q0是一个常量(0<q0<1)。ρi(r,s)代表簇头r上的蚂蚁i选择簇头s作为吓一跳节点的概率。PHi(r,s)代表了蚂蚁i从簇头r到s之间的信息素之和。Nbi(r)是蚂蚁i未到达簇头r邻居节点的集合。在文献中,苏淼等人在传感器网络分层路由协议LEACH基础上,重新定义了“轮”的概念,提出了基于蚁群的无线传感器网络双簇头算法(ACDCHA),算法把每一轮划分成3个阶段而不是传统的两个阶段。根据信息素浓度在每一簇中选择具有分工特征的主簇头和副簇头,主簇头进行数据收集和融合,副簇头进行数据传输工作。该算法较好的平衡了网络的能量消耗,延长了网络生命周期。4算法安全性对比以上总结了目前无线传感器网络中一些主要的分簇协议,其中一些协议能够较好的处理无线传感器网络中的能耗、可靠性、时延性等问题。我们从多个方面对上述协议进行综合对比,如表1所示。其中,“---”表示目前该参数不清楚,A:协议类型;B:簇负载平衡性C:数据融合;D:簇头产生速度;E:簇形成速度;F:簇维护开销;G:算法健壮性;H:算法扩展性;I:算法节能性;J:数据传输延迟;K:控制方式。5主要研究方向本文综述了目前无线传感器网络中主要的分簇协议,分簇网络结构由于具有良好的网络扩展性、便于能量管理,在平衡负载、资源分配、可靠性等方面都具有良好的性能,因此,以分簇为基础的路由协议在无线传感器网络中已得到了很好的应用。总体而言,尽管近年来研究者们对于传感器网络的分簇协议开展了大量的研究工作,取得了相当大的成果,但是,实用化的无线传感器网络分簇协议研究还处于探索阶段,要形成最终成熟的应用技术,还存在许多基础性问题和关键技术需要进一步的研究和完善:1)路由协议的节能性需要进一步提高。WSN分簇路由协议设计的首要目标是通过高效的分簇算法形成合理的网络结构,通过主动的能量管理降低网络的能量消耗,延长网络的生命周期。在已有的算法中,HEED、TE