基于膨胀图的无线传感器网络压缩感知测量矩阵和重构方法

摘要

基于膨胀图的无线传感器网络压缩感知测量矩阵和重构方法，它涉及基于膨胀图理论的压缩无线感知技术，它降低了对传感器节点的要求。步骤为：一、建立一个二部图；二、固定一个有限域，得到左子图和右子图多项式集合；三、将左子图的任意一个顶点对应的多项式f0(Y)生成其Parvaresh-Vardy代码；四、左子图和右子图的两边顶点进行对应，得到是满足条件的膨胀图；五、根据建立起膨胀图生成M×N无线传感器网络压缩感知测量矩阵Φ；六、依据无线传感器网络压缩感知测量矩阵Φ采用树形路由拓扑结构进行数据采集；七、根据已知观测数据y和无线传感器网络压缩感知测量矩阵Φ通过恢复算法将原始信号d从观测数据y中恢复出来，最终得到重构的原始信号d。它在远程控制等许多领域中应用。

权利要求

1.基于膨胀图的无线传感器网络压缩感知测量矩阵的重构方法，其特征在于它的步骤为：步骤一：建立一个二部图G=(A,B),|A|=N,|B|=M，左子图中的左顶点数对应无线传感器节点的个数N，右子图中的右顶点数对应压缩感知测量次数M；

步骤二：固定一个有限域 则二部图的左子图是一个定义在有限域 上次数不超过n-1的多项式集合 每一个多项式对应左子图的一个顶点，故左边顶点个数n为N=q，右子图是定义在 上次数不超过m的多项式集合 每一个多项式对应右子图m+1的一个顶点，故右边顶点个数为M=q ；其中， 为定义的一个有限域 q为有限域 中元素的个数；根据有限域 中元素的个数q、无线传感器节点的个数N和测量次数M确定出正整数参数n和m；

步骤三：将左子图的任意一个顶点对应的多项式f0(Y)生成其Parvaresh-Vardy代码i=1,2,…m-1；其中E(Y)是定义在有限域 上次数为n的不i

可约多项式，h 为正整数参数，用于生成Parvaresh-Vardy代码；

步骤四：左子图和右子图的两边顶点进行对应，两边顶点的对应法则为Γ(f0,y)表示f0的第y个邻接点，即是说f0的第y个邻接点是[y,f0(y),f1(y),…,fm-1(y)]所表示的m次多项式，此时的二部图是满足左子图中至多s个顶点构成的子集S在右子图中至少有(1-ε)d|S|个邻接点的(s,d,ε)膨胀图；

步骤五：根据建立起膨胀图生成M×N邻接矩阵，所述的邻接矩阵为0,1矩阵，当右子图中的第α个顶点和左子图中的第β个顶点若对应为邻接点时，则矩阵中的第α行第β列的元素为1，否则矩阵中的第α行第β列的元素为0，其中，0<α≤M，0<β≤N，所述的M×N邻接矩阵即是所要得到的无线传感器网络压缩感知测量矩阵Φ；

步骤六：依据无线传感器网络压缩感知测量矩阵Φ采用树形路由拓扑结构进行数据采集；首先，树形路由拓扑结构中的一个节点对应无线传感器网络压缩感知测量矩阵Φ中第一列的一个参量，当所有的节点均得到了它们的读数后，树形路由拓扑结构中的各个叶子节点开始传送数据，传送数据中包含子树的所有数据的加权和将被转发至数据的接收终端节点，于是得到了第一次测量的测量值y1，之后树形路由拓扑结构中的一个节点对应无线传感器网络压缩感知测量矩阵Φ中第二列的一个参量，得到了第二次测量的测量值y2，依此类推测量M次就得到了观测数据y；

步骤七：根据已知观测数据y和无线传感器网络压缩感知测量矩阵Φ通过恢复算法将原始信号d从观测数据y中恢复出来，最终得到重构的原始信号d。

2.根据权利要求1所述的基于膨胀图的无线传感器网络压缩感知测量矩阵的重构方法，其特征在于采用以下算法实现对原始信号d的重构：j

步骤1：初始化迭代次数j=0，第j次迭代恢复值d=0N×1；

步骤2：重复进行T次迭代运算，每次迭代运算的过程为：

j-1 j-1

首先，迭代次数j=j+1，则残差为c=y-Φd ，即c=Φ(d-d )+v；

其 次，求 取 与 顶 点 i 相 连 接 的 右 顶 点 集 合 对 应 值 的 中 值其中，N(i)表示与顶点i相连接的右顶点集合；

然后，阈值算子使 中2K个最大分量保持不变，其余设置为0，即j j-1 j j

最终，更新d=d +ωj，d=ΞK[d]；

步骤3：输出原始信号d的恢复值

v表示测量带来的误差；原始信号d是稀疏的或者是可压缩的数据，K表示稀疏度，即原始信号d中只有K个系数的绝对值比较大，其余N-K个系数接近于0。

说明书

基于膨胀图的无线传感器网络压缩感知测量矩阵和重构方

法

技术领域

[0001] 本发明是涉及到无线传感器网络、数据恢复、压缩感知等技术领域的方法，具体涉及一种基于膨胀图理论的压缩无线感知技术。

背景技术

[0002] 无线传感器网络是计算、通信和传感器这三项技术相结合的产物，它综合了传感器技术、嵌入式计算技术、现代网络及无线通信技术、分布式信息处理等技术，能够通过各类集成化得微型传感器协作地实时监测、感知和采集各种环境或监测对象的信息，这些信息通过无线方式被发送，并以自组多跳的网络方式传送到用户终端。传感器网络具有十分广阔的应用前景，在军事国防、工农业、城市管理、生物医疗、环境监测、抢险救灾、危险区域远程控制等许多重要领域都有潜在的实用价值。无线传感器网络具有节点数目多，组成节点同构性，能量受限，网络带宽受限等特点，如何利用节点感知数据的时、空相关性，以能量有效的方式更加高效地获取感兴趣的数据是无线传感器网络应用亟待解决的问题。

[0003] 压缩感知(Compressed Sensing)理论提供的是不同于传统采样形式的一种新的数据采样模式，它表明，只要信号在某个变换域是稀疏的或是可压缩的，就可以用一个与变换基不相关的观测矩阵将变换所得高维信号投影到一个低维空间上，然后通过求解一个优化问题就可以从这些少量投影中以高概率重构出原始信号。压缩感知方法主要包含两个方面：一是测量矩阵，它能够使K-稀疏或可压缩信号x从 的过程中能量损失尽可能小，且观测到的这些信息能够保证准确重建出原始信号；二是重建算法，选择合适的算法使得信号从测量值 恢复原信号 压缩感知是将压缩和采样同时进行的一种采样模式，对于一个K-稀疏的N维信号，投影到这个低维空间的维数将会远小于N，这使得在带宽受限的无线传感器网络中压缩采样的数据的高效传输成为可能。

[0004] 将压缩感知理论应用到无线传感器网络数据采集主要目的在于两方面：一是压缩传感器的数据，降低网络数据流量，二是将能量消耗均匀地分布在整个网络以提高整个网络的寿命。在数据采集过程中，数据的压缩和路由耦合在一起，彼此相互关联的传感器数据联合传送可以实现更高的采集效率。目前在压缩感知中常用的测量矩阵是随机测量矩阵，但是随机矩阵的缺点是显而易见的：一方面随机产生的测量矩阵不能保证最有效的对数据进行采集压缩，对数据的选择带有一定的盲目性，另一方面一定分布的随机数在硬件设备中难以实现。这些不足限制了压缩感知在传感器网络中的应用甚至是压缩感知理论本身的发展。所以基于确定性测量矩阵的压缩感知方法更适合应用于无线传感器网络技术中。首先，确定性矩阵可以集成到通讯协议中，解决了采用随机矩阵时每次进行数据采集时现场生成随机数的问题，降低了对传感器节点的要求。其次，优选出的确定矩阵能够保证压缩感知重构算法的要求，进而保证重构数据的正确性和高精度。基于以上分析，本发明提出应用一种确定性测量矩阵在无线传感器网络中进行数据采集，并且根据所用的测量矩阵特点设计合适的数据重建算法以达到高效数据获取与处理的目的。所用的到得确定性测量矩阵是基于膨胀图理论设计的，且这样的矩阵能很好满足压缩感知理论所要求的条件。

发明内容

[0005] 本发明为了降低对传感器节点的要求，并根据测量矩阵自身的特点，而提出了一种基于膨胀图的无线传感器网络压缩感知测量矩阵和重构方法。

[0006] 基于膨胀图的无线传感器网络压缩感知测量矩阵和重构方法的步骤为：

[0007] 步骤一：建立一个二部图G＝(A，B)，|A|＝N，|B|＝M，左子图中的左顶点数对应无线传感器节点的个数N，右子图中的右顶点数对应压缩感知测量次数M；

[0008] 步骤二：固定一个有限域 则二部图的左子图是一个定义在有限域 上次数不超过n-1的多项式集合 每一个多项式对应左子图的一个顶点，故左边n
顶点个数为N＝q，右子图是定义在 上次数不超过m的多项式集合 每一个多项m+1
式对应右子图的一个顶点，故右边顶点个数为M＝q ；其中， 为定义的一个有限域q为有限域 中元素的个数；根据有限域 中元素的个数q、无线传感器节
点的个数N和测量次数M确定出正整数参数n和m；

[0009] 步骤三：将左子图的任意一个顶点对应的多项式f0(Y)生成其Parvaresh-Vardy代码 i＝1，2，…m-1；其中E(Y)是定义在有限域 上次数为n的不可约多项式，hi为正整数参数，用于生成Parvaresh-Vardy代码；

[0010] 步骤四：左子图和右子图的两边顶点进行对应，两边顶点的对应法则为，Γ(f0，y)表示f0的第y个邻接点，即是说f0的第y个邻接点是[y，f0(y)，f1(y)，…，fm-1(y)]所表示的m次多项式，此时的二部图是满足左子图中至多s个顶点构成的子集S在右子图中至少有(1-ε)d|S|个邻接点的(s，d，ε)膨胀图；

[0011] 步骤五：根据建立起膨胀图生成M×N邻接矩阵，所述的邻接矩阵为0，1矩阵，当右子图中的第α个顶点和左子图中的第β个顶点若对应为邻接点时，则矩阵中的第α行第β列的元素为1，否则矩阵中的第α行第β列的元素为0，其中，0＜α≤M，0＜β≤N，所述的M×N邻接矩阵即是所要得到的无线传感器网络压缩感知测量矩阵Φ；

[0012] 步骤六：依据无线传感器网络压缩感知测量矩阵Φ采用树形路由拓扑结构进行数据采集；首先，树形路由拓扑结构中的一个节点对应无线传感器网络压缩感知测量矩阵Φ中第一列的一个参量，当所有的节点均得到了它们的读数后，树形路由拓扑结构中的各个叶子节点开始传送数据，传送数据中包含该子树的所有数据的加权和将被转发至数据的接收终端节点，于是得到了第一次测量的测量值y1，之后树形路由拓扑结构中的一个节点对应无线传感器网络压缩感知测量矩阵Φ中第二列的一个参量，得到了第二次测量的测量值y2，依此类推测量M次就得到了观测数据y；

[0013] 步骤七：根据已知观测数据y和无线传感器网络压缩感知测量矩阵Φ通过恢复算法将原始信号d从观测数据y中恢复出来，最终得到重构的原始信号d。

[0014] 基于膨胀图理论得到的无线传感器网络压缩感知测量矩阵是确定型测量矩阵，能降低对传感器节点的要求，使得整个框架成为一种全新的无线传感器数据采集与处理的模式。本发明是通过以下技术方案实现的：从Parvaresh-Vardy代码出发，得到符合要求的膨胀图，进而得到所需的测量矩阵，即此膨胀图的邻接矩阵。根据所设计的测量矩阵指导传感器进行数据采集，然后对采集回来的数据用独特的恢复算法进行原始信号d重建。

[0015] 本发明与现有技术相比有如下优点：①从节能角度来说，从压缩感知原理出发既能有效延长网络的生命周期，又能在此基础上节省网间通讯损耗、大大减少工作节点的数目；②采用膨胀图理论设计的确定性测量矩阵，使得网间通讯损耗降低，且使用适合于测量矩阵特点的重建算法具有速度快、迭代次数少、恢复精度高等优点。

附图说明

[0016] 图1为建立一个二部图的结构示意图；图2为膨胀图的结构示意图；图3为一个典型的路由树的拓扑结构图；图4为图3中一子树的部分结构图；图5为压缩数据的传输过程示意图；图6为实际的原始信号；图7为恢复得到是原始信号。

具体实施方式

[0017] 具体实施方式一：结合图1至图7说明本实施方式，本实施方式的实施步骤为：

[0018] 步骤一：建立一个二部图G＝(A，B)，|A|＝N，|B|＝M，左子图中的左顶点数对应无线传感器节点的个数N，右子图中的右顶点数对应压缩感知测量次数M；

[0019] 步骤二：固定一个有限域 则二部图的左子图是一个定义在有限域 上次数不超过n-1的多项式集合 每一个多项式对应左子图的一个顶点，故左边n
顶点个数为N＝q，右子图是定义在 上次数不超过m的多项式集合 每一个多项m+1
式对应右子图的一个顶点，故右边顶点个数为M＝q ；其中， 为定义的一个有限域q为有限域 中元素的个数；根据有限域 中元素的个数q、无线传感器节
点的个数N和测量次数M确定出正整数参数n和m；

[0020] 步骤三：将左子图的任意一个顶点对应的多项式f0(Y)生成其Parvaresh-Vardy代码 i＝1，2，…m-1；其中E(Y)是定义在有限域 上次数为n的不可约多项式，hi为正整数参数，用于生成Parvaresh-Vardy代码；

[0021] 步骤四：左子图和右子图的两边顶点进行对应，两边顶点的对应法则为，Γ(f0，y)表示f0的第y个邻接点，即是说f0的第y个邻接点是[y，f0(y)，f1(y)，…，fm-1(y)]所表示的m次多项式，此时的二部图是满足左子图中至多s个顶点构成的子集S在右子图中至少有(1-ε)d|S|个邻接点的(s，d，ε)膨胀图；

[0022] 步骤五：根据建立起膨胀图生成M×N邻接矩阵，所述的邻接矩阵为0，1矩阵，当右子图中的第α个顶点和左子图中的第β个顶点若对应为邻接点时，则矩阵中的第α行第β列的元素为1，否则矩阵中的第α行第β列的元素为0，其中，0＜α≤M，0＜β≤N，所述的M×N邻接矩阵即是所要得到的无线传感器网络压缩感知测量矩阵Φ；

[0023] 步骤六：依据无线传感器网络压缩感知测量矩阵Φ采用树形路由拓扑结构进行数据采集；首先，树形路由拓扑结构中的一个节点对应无线传感器网络压缩感知测量矩阵Φ中第一列的一个参量，当所有的节点均得到了它们的读数后，树形路由拓扑结构中的各个叶子节点开始传送数据，传送数据中包含该子树的所有数据的加权和将被转发至数据的接收终端节点，于是得到了第一次测量的测量值y1，之后树形路由拓扑结构中的一个节点对应无线传感器网络压缩感知测量矩阵Φ中第二列的一个参量，得到了第二次测量的测量值y2，依此类推测量M次就得到了观测数据y；

[0024] 在现实中，传感器节点通常分布于空间的一个二维区域内，并且总的路由拓扑呈现出一个树状结构。图3展示了一个典型的路由树的拓扑结构，它拥有5个路由子树，如图中的虚线相隔所示。为了融合传感器的读数并且将其转发出去，每一个节点需要知道其局部路由树的结构特性。下面以图4为例来说明CDG具体的数据采集过程，并且其具体的压缩数据的传输过程如图5所示。如图3中的虚线框所示，图4为图3中一子树的一部分。当所有的节点均得到了它们的读数后，各个叶子节点开始传送数据。在此示例中，首先节点s3根据确定系数φi3计算出φi3d3，并且将其传送至s2，而后s2便可计算φi2d2并且将数据和转发至s1。索引号i表示第i个加权和(i＝1，2，...，M)。s5和s6也分别将加权和φi5d5同φi6d6发送至s4。当s4收到这两组数据，并立即计算φi4d4，并且将其所有数据的加权和 发送至s1。同理，节点s8，s9和s10也分别将数据φi8d8，φi9d9和φi10d10发送至s7，然后s7便计算φi7d7，最后将数据 发送至s1。此时，节点s11也将数据φi11d11发送至s1。综上，节点s1便立即计算φi1d1，并且将总的数据加权和 转发至下一网络节点。最终，包含该子树的所有数据的加权和将被转发至数据的接收终端节点。

[0025] 在此路由树的设计理念下，为了叙述方便，采取如下的路由树节点的组织方式。对于一棵完整的路由树而言，令最外层有Nn个传感器节点。次外层有Nn-1个传感器节点，且每个节点均匀地与Nn/Nn-1个子节点相连。依次类推，次内层N1个节点，且每个节点拥有N2/N1个子节点。则最内层的路由树节点N0＝1，并且拥有N1个子节点。若按照传统的数据采集方式，总的数据通信量可用如下公式表示：

[0026] yCOMM＝N1+(N1+N2)+…+(N1+…+Nn+N0) (1)

[0027] 若按照所得到的测量矩阵的CDG数据采集方式，总数据通信量可表示为：

[0028] yCDG＝M(N0+N1+…+Nn) (2)

[0029] 由上述典型的树形路由结构通讯量的计算公式得知，当路由树的层数N越大时，采用CDG的方式来进行数据的采集所能节省的网络通讯量也就越大。

[0030] 步骤七：根据已知观测数据y和无线传感器网络压缩感知测量矩阵Φ通过恢复算法将原始信号d从观测数据y中恢复出来，最终得到重构的原始信号d；

[0031]

[0032] 观测数据y由如下公式表示：

[0033] y＝Φd+v，

[0034] 其中，v表示测量带来的误差；原始信号d是稀疏的或者是可压缩的数据，K表示稀疏度，即原始信号d中只有K个系数的绝对值比较大，其余N-K个系数接近于0，采用以下算法实现对原始信号d的重构：

[0035] 步骤1：初始化迭代次数j＝0，第j次迭代恢复值dj＝0N×1；

[0036] 步骤2：重复进行T次迭代运算，每次迭代运算的过程为：

[0037] 首先，迭代次数j＝j+1，则残差为c＝y-Φdj-1，即c＝Φ(d-dj-1)+v；

[0038] 其 次，求 取 与 顶 点 i相 连 接 的 右 顶 点 集 合 对 应 值 的 中 值其中，N(i)表示与顶点i相连接的右顶点集合；

[0039] 然后，阈值算子使 中2K个最大分量保持不变，其余设置为0，即

[0040] 最终，更新dj＝dj-1+ωj，dj＝ΞK[dj]；

[0041] 步骤3：输出原始信号d的恢复值