CN101932012B - 基于最优阶估计与分布式分簇的传感器网络数据压缩方法 - Google Patents

Abstract

本发明涉及一种基于最优阶估计与分布式分簇的传感器网络数据压缩方法。现有的数据压缩方法效率低。本发明利用传感节点采集数据的时空相关性，一方面通过引入最优阶估计，从而界定了系统要传输的原始数据组数，既获得了有效的相关性系数，又避免了冗余系数的产生；另一方面对网络进行分簇处理，以簇为单位处理节点数据，这样不仅可以提高基站处理各节点数据效率，还可以增强基站迅速定位产生异值或出现异常节点的能力。本发明适用于基于无线传感器网络的环境实时监测系统，可实现对无线传感器网络数据有效压缩，并有效地降低了节点平均能耗。

Description

基于最优阶估计与分布式分簇的传感器网络数据压缩方法

技术领域

本发明属于数据压缩技术领域，涉及一种基于最优阶估计与分布式分簇的传感器网络数据压缩方法。

背景技术

基于无线传感器网络(WSNs)的监测系统中，各个传感器节点收集自身周围的局部信息，对其进行处理后传送至汇聚节点，汇聚节点汇总所有节点采集的局部数据得到感兴趣区域的整体信息。在无线传感器网络中，由于受多种因素比如背景噪音、节点失效、无线通信存在不稳定性及能量约束等的影响，节点获取、处理和传输的感知数据信息常常存在一定的误差，并具有一定程度的不确定性，然而在某些应用中通常允许一定的误差存在。即在保证应用要求的前提下，可以通过降低一定的数据精度来减少在网络中传输的数据量，从而降低网络中节点的能量消耗。无线传感网络中的数据压缩算法就是保证在一定数据精度的前提下，寻求一种有效的减少传输中数据量，从而降低节点能耗，提高整个网络综合性能的方法。在无线传感器网络的许多实际应用中，被监测区异常情况发生的概率总是相对较小，在没有异常发生的情况下，同一传感节点在连续采集数据时，前后连续时刻所采集数据必然存在很大相关性，同时，处于相邻区域的不同的传感器节点在同一时刻采集的数据必然具有空间相关性，如果将这些具有时间，空间冗余的数据都发送到基站必然耗费节点大量的能量，因此如何有效地消除节点感知数据在时间、空间上的冗余性已成为无线传感网络中数据压缩要解决的关键性问题。如何针对WSNs在环境监控方面的具体应用需要，设计出有效的无线传感网络数据压缩算法，是一个很有意义的研究课题。

无线传感器网络数据压缩算法利用节点感知数据中存在的时间、空间冗余，先直接传输若干组节点感知数据，从中提取同一节点不同时刻，同一时刻不同节点间的相关性，再结合分布式编码，在基站处恢复节点原始感知数据，节点处仅有简单的取模运算，大量算法运算被转移到基站，这样就能够在保证一定精度的情况下，最大限度地减小节点传输单位数据的能耗，而实际应用中仅对基站定期更换电池或直接长期供电也是可行的，故该种算法具有较广的应用前景。然而该类算法还存在一些缺点，比如在估计预测相关性系数时，对所要传输的原始数据的组数没有清晰的界定，若让节点传输过多原始数据，势必会耗费节点大量的能量，这样不仅不利于延长节点使用寿命，还会导致基站处要计算的相关性系数维数增大，即引入了冗余相关系数，从而使基站计算量过大，进而影响到系统的响应时间及数据精度；若节点传输的原始数据组数太少，基站无法计算出足够的相关性系数，则预测出的数据将很难满足精度要求，导致系统可用性降低，故如何有效地界定要传输的原始数据量是该算法值得深入探讨和解决的问题。另外，随着网络规模的增大，该种算法的多节点对应单一基站的模式就很难高效运行了，因为基站要接收各节点压缩编码并根据相关性系数逐一计算出各节点原始数据，这样在计算首个节点与最后一个节点数据时，必然存在一个较大时间差，故网络规模越大，时间差越大，这就增大了系统时延，影响了该算法的应用范围，基于这两点，最优阶分布式分簇结构树压缩算法一方面引入最优阶估计，从而界定系统要传输的原始数据组数，既要获得有效的相关性系数，又要避免冗余系数的产生，另一方面对网络进行分簇处理，以簇为单位处理节点数据，这样不仅可以提高基站处理各节点数据效率，还可以增强基站迅速定位产生异值或出现异常节点的能力，从而有效提高整个无线传感网络系统对监控区的综合监控能力。

发明内容

本发明的目的是针对现有技术的不足，提供了一种可用于环境监测的无线传感器网络(WSNs)数据压缩方法，使得由数据精度和节点平均能耗构成的综合指标最优化。

为了达到上述目的，本发明的技术方案是这样实现的：

步骤(1).由监测区节点向基站传输各自监测值，所有节点每传输完一组监测值，基站采用联合信息准则(CIC)进行最优阶判定，若所得阶数不是最优，且节点所传数据组数没有超过N/3，节点继续传输原始监测值；否则基站由节点所传输的数值获得初始的预测系数矩阵Φ_m，并在基站处建立结构树，其中N表示一个算法周期包含的节点传输数据组数，所述的获得初始预测系数矩阵方法和建立结构树方法均为成熟技术；

步骤(2).基站根据预测系数矩阵Φ_m，将监控区节点划分为若干簇，以簇为单位，基站根据节点监测值产生压缩指令，节点根据压缩指令产生所要传输的二进制位数i；基站轮流指定簇内节点担当簇头，簇头负责传输自身未经压缩的监测值及簇内其它节点的压缩编码至基站，同时簇头接收来自基站的指令；

步骤(3).簇内各节点经簇头依次获得基站压缩指令，各节点将其模数转换后的二进制值对2ⁱ取模，得到i位二进制压缩码，将该压缩码经簇头传至基站，同时簇头向基站传输其未经压缩的监测值；

步骤(4).基站以簇为单位由步骤(1)中计算的预测系数矩阵Φ_m及簇头所传原始监测值，可得到簇内各节点估计值

(

对应第m个节点第r组监测值的估计值)，再由该节点的i位压缩码可以在结构树中定位出一个子序列，由于子序列间隔距离2^i-1Δ以概率P大于均方误差N_r，m，故在该子序列中离

最近的序列值即为节点最终估计值

同时

又成为估计同一时刻下一节点的已知条件，即在更新Φ_m时要考虑新估计出的数值；

步骤(5).当获得各簇所有节点的最终估计值后，由基站计算并发布下一时刻各簇内节点需要的压缩指令，当节点监测到的数值组数达到N，则跳转至步骤(1)，否则跳转至步骤(2)。

本发明提出了基于最优阶估计与分布式分簇的传感器网络数据压缩方法。由于节点能量主要消耗在传输原始监测信息上，通过引入最优阶估计，减少了节点向基站传输的原始数据的组数，从而降低了节点平均能耗；将计算集中于时间域和空间域上与待估计节点更加接近的系列节点值上，剔除了与待估计节点相关性微弱的边远节点，从而有效降低了算法所处理数据的维度，提高了算法运算速度及节点数据恢复精度；若监控区网络规模较大，基站对区域节点分簇处理后，如果区域出现异常，基站能够迅速定位异常区所在的簇，进而与监测到异常的节点直接建立连接，与全区域逐个搜寻相比，可有效降低系统时延，提高系统监控实时性。采用本发明方法，在不同的网络规模下，基于最优阶估计与分布式分簇的传感器网络数据压缩方法在数据精度和节点平均能耗构成的综合指标上优于直接的分布式结构树压缩算法。

附图说明

图1是分布式编码方法框图；

图2是解码结构树；

图3是本发明方法流程图。

具体实施方式

本发明的核心思想是：一方面引入最优阶估计，从而界定系统要传输的原始数据组数，既要获得有效的相关性系数，又要避免冗余系数的产生，另一方面对网络进行分簇处理，以簇为单位处理节点数据，这样不仅可以提高基站处理各节点数据效率，还可以增强基站迅速定位产生异值或出现异常节点的能力，从而有效提高整个无线传感网络系统对监控区的监控能力。

下面结合附图对本发明做进一步的详细描述。

如图1所示，分布式编码即监控区有两个或两个以上节点同时感知原始数据时，在节点间采用不对称的编码方式，建立无线传感器网络分布式压缩结构，当节点采集的数据序列为高斯相关独立同分布离散序列时，实验证明，节点B在压缩自身数据时，无论其是否知道当前时刻A，B节点数据的相关性系数，采用上述分布式压缩模式，均能获得等效的压缩性能。将框图由两个节点扩展到n各节点，根据自身之前采集数据压缩当前数据所得的压缩码，由基站计算并确定各节点数据之间相关性，并向各节点发送各自的压缩码比特位数，最后还原出各节点原始监测值。

基于上述分布式编码基本原理，分布式结构树压缩算法首先由所有节点向基站传输N/3组原始值，N的大小可根据具体应用确定，基站根据这些原始值建立一个结构树，并计算出预测系数矩阵Φ_m，基站还需计算出与各节点对应的压缩指令，即下一采集时刻各节点需将各自监测值(经A/D后的)压缩后的位数，与此同时，基站要指定一个节点传输其未压缩的监测值，为使监控区各节点能量被均衡消耗，该节点可由基站轮流指定，节点按各自收到的指令，对原始监测值进行2ⁱ取模运算，从而将各自采集数据压缩至i位，基站处接收到各节点i位编码后，可以在之前建立的结构树中定位出一个较小数值序列，结合指定节点所传原始监测值及之前计算的预测系数矩阵Φ_m，恢复出该i位压缩码对应的原始监测值，当前时刻所有节点值恢复完毕，基站将更新预测系数矩阵及各节点下一时刻编码位数，类此循环往复，当前时刻各节点的值将不断被预测估计出来。有必要对以上算法涉及到的结构树，预测系数及i值的确定作进一步的说明，结构树首先是以前述N/3组原始数据的均值为起点，以Δ为间隔向两端扩展，Δ大小决定算法精度，扩展范围由具体应用决定，对上述以Δ为间隔的扩展序列进行奇偶序列分裂，可得到间距为2Δ的两组子序列，以同样的方式可再对子序列进行分裂，分裂次数由i的位数决定，i次分裂后，各子序列相邻节点间距为2ⁱΔ，第i层每个子序列对应唯一的i位编码，根据以上表述即可建立如图2所示解码结构树，当基站按获得某节点发送的i位编码，可以定位出对应的子序列，再由预测系数计算出一个估计值，通过在定位的子序列中寻找与估计值最接近的序列值，从而恢复出该节点监测值。

本方法在上述二维空间实现无线传感器网络数据压缩遵循以下的过程，见图3：

步骤(1).由监测区节点向基站传输各自监测值，所有节点每传输完一组监测值，基站采用联合信息准则(CIC)进行最优阶判定，若所得阶数不是最优，且节点所传数据组数没有超过N/3，节点继续传输原始监测值；否则基站由节点所传输的数值获得初始的预测系数矩阵Φ_m，并在基站处建立结构树，其中N表示一个算法周期包含的节点传输数据组数，获得初始预测系数方法和建立结构树方法均为成熟技术；

步骤(2).基站根据预测系数矩阵Φ_m，将监控区节点划分为若干簇，以簇为单位，基站根据节点监测值产生压缩指令，节点根据压缩指令产生所要传输的二进制位数i；基站轮流指定簇内节点担当簇头，簇头负责传输自身未经压缩的监测值及簇内其它节点的压缩编码至基站，同时簇头接收来自基站的指令，其中i值根据公式

求得，其中p是概率，Δ是图2结构树中序列间距，

是方差；

步骤(3).簇内各节点经簇头依次获得基站压缩指令，各节点将其模数转换后的二进制值对2ⁱ取模，得到i位二进制压缩码，将该压缩码经簇头传至基站，同时，簇头向基站传输其未经压缩的监测值；

步骤(4).基站以簇为单位由步骤(1)中计算的预测系数矩阵Φ_m及簇头所传原始监测值，可得到簇内各节点估计值(对应第m个节点第r组监测值的估计值)，再由该节点的i位压缩码可以在结构树中定位出一个子序列，由于子序列间隔距离2^i-1Δ以概率P大于均方误差N_r，m，故在该子序列中离

最近的序列值即为节点最终估计值

，同时，

又成为估计同一时刻下一节点的已知条件，即在更新Φ_m时要考虑新估计出的数值；

步骤(5).当获得各簇所有节点的最终估计值后，由基站计算并发布下一时刻各簇内节点需要的压缩指令，当节点监测到的数值组数达到N，则跳转至步骤(1)，否则跳转至步骤(2)。

总之，本发明提出的是基于最优阶估计与分布式分簇的传感器网络数据压缩方法：网络节点在监控区随机分布，经最优阶估计后，本方法能够将具有空间相关性的节点划分在同簇，通过在基站建立预测系数矩阵及解码结构树，实现对节点监控值编码的恢复与还原，节点仅仅在预测系数初始化过程中传输监测值，然后仅需作简单取模运算实现监控值编码并传输数据量相对较小的编码，节点平均能耗能够被大幅度降低，进而有效提高传感器网络综合监控性能。应当说明的是，基站处利用最优阶估计的方式不同(如应用在空间相关性阶估计或时间相关性阶估计)等方法都是不脱离本发明技术方案的精神和范围的。

Claims (1)

1.基于最优阶估计与分布式分簇的传感器网络数据压缩方法，其特征在于该方法包括如下步骤：

步骤(1).由监测区节点向基站传输各自监测值，所有节点每传输完一组监测值，基站采用联合信息准则进行最优阶判定，若所得阶数不是最优且节点所传数据组数没有超过N/3，则节点继续传输原始监测值；若所得阶数是最优，则基站由节点所传输的数值获得初始的预测系数矩阵Φ_m，并在基站处建立结构树，其中N表示一个算法周期包含的节点传输数据组数；

步骤(2).基站根据预测系数矩阵Φ_m，将监控区节点划分为若干簇；以簇为单位，基站根据节点监测值产生压缩指令，节点根据压缩指令产生所要传输的二进制位数i；基站轮流指定簇内节点担当簇头，簇头负责传输自身未经压缩的监测值及簇内其它节点的压缩编码至基站，同时簇头接收来自基站的指令；

步骤(3).簇内各节点经簇头依次获得基站压缩指令，各节点将其模数转换后的二进制值对2ⁱ取模，得到i位二进制压缩码，将该压缩码经簇头传至基站，同时簇头向基站传输其未经压缩的监测值；

步骤(4).基站以簇为单位，由步骤(1)中计算的预测系数矩阵Φ_m及簇头所传原始监测值得到簇内各节点估计值

再由该节点的i位压缩码在结构树中定位出一个子序列，在该子序列中离

最近的序列值即为节点最终估计值

同时

又成为估计同一时刻下一节点的已知条件，即在更新Φ_m时考虑新估计出的数值；

步骤(5).当获得各簇所有节点的最终估计值后，由基站计算并发布下一时刻各簇内节点需要的压缩指令，若节点监测到的数值组数达到N，则跳转至步骤(1)；若节点监测到的数值组数未达到N，则跳转至步骤(2)；

其中r表示组数，m表示节点编号，Φ_m表示m节点的预测系数矩阵，

表示第m个节点第r组的最终估计值，

表示第m个节点第r组监测值的估计值。

Images