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

摘要

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

说明书

技术领域

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

背景技术

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

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

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

发明内容

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

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

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

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

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

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

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

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

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

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

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

附图说明

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

具体实施方式

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

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

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

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

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

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

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

在现实中，传感器节点通常分布于空间的一个二维区域内，并且总的路由拓扑呈现出 一个树状结构。图3展示了一个典型的路由树的拓扑结构，它拥有5个路由子树，如图中 的虚线相隔所示。为了融合传感器的读数并且将其转发出去，每一个节点需要知道其局部 路由树的结构特性。下面以图4为例来说明CDG具体的数据采集过程，并且其具体的压缩 数据的传输过程如图5所示。如图3中的虚线框所示，图4为图3中一子树的一部分。当 所有的节点均得到了它们的读数后，各个叶子节点开始传送数据。在此示例中，首先节点s₃根据确定系数φ_i3计算出φ_i3d₃，并且将其传送至s₂，而后s₂便可计算φ_i2d₂并且将数据和转发至s₁。索引号i表示第i个加权和(i＝1，2，...，M)。s₅和s₆也分别将加权和φ_i5d₅同φ_i6d₆发送 至s₄。当s₄收到这两组数据，并立即计算φ_i4d₄，并且将其所有数据的加权和发送至s₁。 同理，节点s₈，s₉和s₁₀也分别将数据φ_i8d₈，φ_i9d₉和φ_i10d₁₀发送至s₇，然后s₇便计算φ_i7d₇，最后 将数据发送至s₁。此时，节点s₁₁也将数据φ_i11d₁₁发送至s₁。综上，节点s₁便立即计算 φ_i1d₁，并且将总的数据加权和转发至下一网络节点。最终，包含该子树的所有数据 的加权和将被转发至数据的接收终端节点。

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

y_COMM＝N₁+(N₁+N₂)+…+(N₁+…+N_n+N₀)    (1)

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

y_CDG＝M(N₀+N₁+…+N_n)    (2)

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

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

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

y＝Φd+v，

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

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

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

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

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

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

最终，更新d^j＝d^j-1+ω_j，d^j＝Ξ_K[d^j]；

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