改进压缩感知算法的WSN数据恢复方法

陈 雪，胡玉平

(1.广州工商学院 计算机科学与工程系，广东 广州 510850；2.广东财经大学 信息学院，广东 广州 510320)

0 引 言

无线传感器网络(wireless sensor networks，WSN)[1]是人们采集数据、重建数据的重要工具。但是由于环境的影响，利用WSN采集数据时很容易产生数据丢失[2,3]。因此，针对WSN中丢失数据的恢复研究很显得至关重要。

常用的数据恢复算法有以下几种：K-最近邻(K-nearest neighbors，KNN)算法[4]。该算法首先给定K的值，找到分布在丢失数据节点附近的K个相邻节点，利用这些相邻节点携带的数据信息值，结合加权平均算法或者线性拟合方法估算出丢失的数据。多通道奇异频谱分析(multi-channel singular spectrum analysis，MSSA)[5]是一种插值算法，它是一种自适应的基于非参数的算法，在气象或者地理等领域中应用广泛。压缩感知(compressive sensing，CS)是一种新型的数据恢复算法，该算法可以根据少量的已知数据实现丢失数据的恢复[6,7]。

近年来，在传统WSN数据恢复算法的基础上，学者们相继提出许多新型的算法。例如，文献[8]提出一种基于多属性协助和压缩感知的数据恢复精度优化算法(MACS)，大大降低了数据恢复中的差错率，然而，该方法中的多属性协助需要准备的前期工作较多，不利于实际应用。文献[9]为解决数据丢失问题，利用线性预测编码进行稀疏化变换，采用正交匹配追踪(OMP)算法进行数据恢复，一定程度上提高了数据恢复精度，然而，该方法仅适用于小规模网络数据的恢复。文献[10]设计一种用于无线传感网络的离散拉普拉斯算子(DLO-WSN)，提出基于该算子的数据选择算法(LDS)，可适用于较大规模的数据恢复，然而，该方法具有较高的计算开销。

在保证数据恢复成功率的情况下，为了更好地降低所耗费的成本，提出了一种基于改进压缩感知算法和单位圆盘图模型的WSN数据恢复方法。主要创新点如下：①根据改进的压缩感知算法，估算出部分丢失数据的传感器节点数据信息，并把这些估算出信息的传感器节点当作已知节点，从而更好地估算其它丢失信息节点；②通过二次规划实现数据的重构，并采用一组具有先进移动能力的移动传感器来访问失效传感器的邻居节点，重新获取丢失数据，有助于提升数据恢复的精度；③通过构建最优汇聚树和查找不同网络结构(如线性图和网格)中的最优节点位置，有效降低了数据恢复的成本。

1 改进压缩感知算法

利用该算法实现数据恢复，实际上就是求解一个欠定状况下的线性方程组。由于该类方程组存在无数组解，为了得到较好的结果，有学者将该类方程组转换成1范数最小化问题，并提出多种匹配算法，比如匹配追踪(matching pursuit，MP)算法[11]、正交匹配追踪(orthogonal matching pursuit，OMP)算法[12]、分段正交匹配追踪(stage wise OMP，St OMP)算法等[13]。但以上算法对于数据恢复的效果并不是很理想。于是，本小节提出利用二次规划的方式求解欠定状况下的线性方程组，并结合阿米霍步长准则(Armijo rule)实现数据恢复。

(1)

另外，由于外界传输环境的影响，Sink节点[14]接收的数据和WSN节点传输的数据会有所差别，具体可表示为

y=φx+n

(2)

(3)

利用二次规划的方式解决式(3)所示的1范数最小化问题。根据二次线性规划理论，可用式(4)所示的凸优化问题的解来代替式(3)所述问题，其中τ>0

(4)

在式(4)中，为了方便求解，可以将变量x用变量x1和x2的差值表示，则变量x可写成如下形式

x=x1-x2(x1≥0,x2≥0)

(5)

从而有

(6)

其中，(xi)+=max{0,xi}。 综上可得

(7)

其中，IN=[1,1,…1]T，该向量包含N个元素1。那么式(4)可表示为二次规划的形式

(8)

其中，x1≥0,x2≥0。

将式(8)改写成标准的二次规划表示形式

(9)

其中

(10)

式中：e(k)>0。 令

z(k+1)=z(k)+λ(k)(w(k)-z(k))

(11)

式中：λ(k)∈[0,1]，并且

(12)

通过定义向量g(k)来估算e(k)的初始值，以便使F(z) 存在最小值，g(k)可表示为

(13)

根据式(13)求得e(k)的初始值e0为

e0=argminF(z(k)-eg(k))

(14)

综上所述，改进算法的步骤如下：

(1)给定z(0)，参数f∈(0,1)，μ∈(0,1/2)，k=0；

(2)由式(14)得到e0的值；

(3)根据e0、f构建序列γ=e0,fe0,f2e0,…；

若不满足上述条件，k←k+1，返回(2)。

2 数据骡子(data mule)

数据骡子(data mule)[15]是一种通过物理方式携带计算机与存储器的交通工具，它的移动性能强，可在远程位置处创建有效数据通讯链路，进行数据的采集和监控。

为方便描述，表1给出了本文常用的特殊符号及其含义。

表1 符号及其含义

图1表示两个节点失效的mule旅行示意图。灰色表示已经失效的传感器节点；虚线表示mule旅行；旅行从m节点开始，结束于m节点。T是一棵基于欧式平面，根为r，具有n个无线传感器的汇聚树。数据从叶子节点传播到根节点r。 文中用有向完全图G=(V,E) 表示仿真环境，其中节点集表示无线传感器，边集表示传感器间的距离或通讯时间。若传感器v发生故障，我们并不希望丢失从其子节点T,δ(v,T) 获取的数据。因此，mule必须穿越于δ(v,T) 间，恢复丢失的信息。文中将该问题定义为(α,β)-mule问题，其中α表示发生故障的节点数，β表示旅行的mule数。

图1 两个节点失效的mule旅行

3 单位圆盘图模型

本文主要对单位圆盘图模型进行了研究。在单位圆盘图模型中，当且仅当d(u,v)≤1时，节点对存在有向边。其中d(u,v) 表示节点u和v之间的欧式距离。表2所示为基于单位圆盘图模型的4种(1,1)-Mule变异问题。其中任意两节点u,v∈V，如果满足d(u,v)≤1，则能互相通讯。

表2 基于单位圆盘图模型的4种(1,1)-Mule变异问题

3.1 基于线性拓扑的(1,1)-Mule问题

假设有n个节点，它们间的距离为单位距离，分布在欧式平面上。该设置确保节点只能与相邻节点进行通讯。对于那些基于通讯约束下的线拓扑结构，定义树的结构和方向只需知道根r的位置。因此，解决方案成本由r和m的位置唯一决定。为了更清楚地表述，定义节点编号为1到n，m和r分别表示解决方案中所指的mule和根。考虑对称性，因为c(m,r)=c(n-m+1,n-r+1)，其中c(m,r) 是最优解决方案成本，假设r≥m。 此时mule位于m、 根位于r，解决方案由r的位置决定。图2所示为线路拓扑图，共包含6个节点，4种不同的情况。其中，树T的不同解决方案有两种情况，mule的位置选择有两种情况。累加和表示失效节点i,i∈{1,…,6} 对应的成本。

图2 线路拓扑

引理1 对于线性拓扑结构，根r的最优位置是n-1。

证明：假设m

下文将论证当使用成本为0时 (r

3.2 基于线性拓扑的(α-1)-Mule问题

下面论证求解该问题的一种算法。

引理3 当m∈[1,n-2] 时，c(m,n-1) 存在多项式时间内的解析解。

由引理1可知根的最优位置为n-1。因此，为了找到最优的解决方案，可搜索令c(m,n-1) 最小化的m值。使用动态规划和记忆表，在O(n2) 时间内计算c(i,j) 值总成本。因此，算法运行时间复杂度为O(n2)。

引理4 当mi时，满足π(i,m,r)=π(i,m-1,r)。

证明：只要m≠i，则i处的mule就不改变方向。

引理5c(m+1,r)=c(m,r)+πl(m,r)+π(m,m+1,r)-πr(m,r) 并且c(m-1,r)=c(m,r)-πl(m,r)+π(m,m-1,r)+πr(m,r)。

引理7 当πl(m,r) 单调递增时，πr(m,r) 也单调递增。

由引理4可知，无论数据骡子怎么放置，只要i>m，骡子到一个特定节点的旅行次数是不变的，由于增加m意味着有较少的节点分布在右侧，相对于m而言方向不变，πl(m,r) 的值也在增大。当在m的左侧节点数目逐渐增加时，πl(m,r) 的值会逐渐变小。

证明：基于引理6和引理7。

结合引理5和引理6，可知0≤c(m+1,n-1)-c(m,n-1)=πl(m,n-1)-πr(m,n-1)+π(m+1,m,n-1)=πl(m,n-1)-(πr(m,n)-Δ)+π(m+1,m,n-1)=π(m+1,m,n-1)+Δ。 0≤c(m-1,n-1)-c(m,n-1)=-πl(m,n-1)+πr(m,n-1)+π(m-1,m,n-1)=π(m-1,m,n-1)-Δ。

综上，结论如下：

3.3 基于随机线性拓扑的(1,1)-Mule问题

本节将讨论基于随机直线的(1,1)-Mule问题，其中n分布于直线上，n≥L，这样便可基于预先定义的分布函数进行取样作为相邻节点间的距离，最大距离为1。基于单位圆盘图的通讯模型，只有当且仅当d(u,v)≤1时，节点u和v之间才会形成边，这意味着该图是连接的。然后，简化假设，设mulem，根r为直线最左边的节点，并且L∈N。

根据算法1构建树T，其中Topt为最优树；两者成本分别为c(T)、c(Topt)。 定义TL为经过L节点的树，这样相邻节点间的距离正好为1；c(TL) 为对应的成本。观察算法1可知，B为树T中的骨干节点集，而不是叶子节点。

算法1：生成树1

(1)V′=B=C={r}；

(2)E′=∅；

(3)当|C|≠n时，

(4)令C为B中节点可到达的所有节点；

(5)找到B中节点可到达的最远节点v；

(6)找到使得d(u,v) 最小化的u∈B；

(7)将v添加入B中；

(8)将边e(v,u) 添加入E′；

(9)对于每个节点w∈C(〗v} 添加指向E′的有向边；

(10)V′=V′∪C∪{v}；

(11)结束。

(12)发射T=(V′,E′)。

论述如下：

引理11c(TL)≤c(Topt)。

证明：至少需要L个节点来覆盖长度为L的区域，并且在直线上的每个单位间隔必须包含至少一个节点。因此，可通过将区间 [i,i+1] 上的节点映射到T中i处的对应节点，并删除区间内多余节点，将任意树转换为TL树。当m=0时，该转换将降低解决方案的整体成本，即c(TL)≤c(Topt)。

引理12 |V(T)|≤2L。

证明：设v和l为算法1两次迭代后得到的非叶子节点，vx和lx分别为其在x线性轴上的坐标。当lx与vx接近时，该算法以最慢速度收敛；但是，当l为区间 [vx,vx+1] 内最远节点时，意味着在l之后选择的非叶子节点必定在区间 [vx+1,vx+1+λ] 内。因此，在最坏的情况下，在两次迭代中，算法只覆盖了一个单位距离，这意味着至少得经过2L步才能完成迭代。过程如图3所示。

图3 覆盖长度L须放置将近2L个节点

引理

c

T

c

T

L

因此，将有：

引理14 基于算法1生成(1,1)-Mule问题的4-approximation解决方案。

3.4 基于网格拓扑的(1,1)-Mule问题

引理15 mule位于特定位置m处，(1,1)-mule问题中的任一颗树的近似比不超过dmax。

证明：显然，在任意一种算法中，mule必须访问所有非根节点。在最坏的情况下，T中节点v只有一个子孙节点时，将会产生最小绝对值。那么，mule的旅行只能覆盖一个节点。在最好的情况下，旅行包含了G中节点v的所有子孙节点，很显然这与节点的度有关。论证结果表明，在最坏情况下节点v产生的成本和最优解决方案成本的比例为dv，而在算法2中，mule必须访问节点v的所有子孙节点(图4)。

图4 算法2

然后，将论述最优旅行方案OPT的成本下边界OPT。

图5 锯齿树，成本为

接下来，利用算法2构建一棵近似最优成本树。为了在每次故障时尽可能多地访问节点，本文在多个连续星型的顶部构建树。

算法2：生成树2

(1)星型：为所有节点(坐标为 (x,y)) 调整星的分布，满足1≡ymod3(如图4(a)所示)。

(2)指向：沿网格方向连接星。

设c为算法2生成树成本，s为锯齿树成本。

4 实验仿真与分析

基于不同拓扑结构利用NS2仿真软件[16]进行了多次实验，每次实验均进行了50次迭代，计算得出解决方案的平均成本。在大型网络中，直接计算最短TSP问题是不可行的。因此，使用基于遗传算法的TSP启发式框架[17]。

为了验证本文算法的优势，文中通过计算不同的拓扑设置下限，基于最优旅行方案OPT成本的下边界OPT比较了所提算法间的比例。

在第一次仿真结果如图6所示，研究了算法1步骤4中选择不同的领导对算法总成本的影响。文中基于不同竞争算法比较了实验结果：随机选择一个节点作为领导者的贪婪算法1、选择接近最右边领导者的节点的贪婪算法2和改变相邻节点到L/n的距离的最优旅行方案算法。在仿真过程中，测试了相邻节点距离的分布函数对算法性能的影响。图6(a)使用了均值为0.1的指数分布；图6(b)使用了均为值0.5的均匀分布。由实验数据可知，指数分布的突发性导致了mule旅行距离的增加，从而导致了方案整体成本的增加。另外，算法1的实际近似比远低于引理13中的证明。这表明，理论可能加强了近似比。

图6 算法1与不同竞争算法间的成本比例

第二次仿真结果如图7所示，将算法2与下述算法进行了比较：基于锯齿树的锯齿算法(图5)、基于最小平面树的贪婪算法和最优旅行方案算法。文中研究了两种变化：mule置于坐标最左下角和置于中心。但值得注意的是，虽然两个仿真中的算法保持不变，但将mule置于角落里时，成本高出许多。

图7 算法2与不同竞争算法间的成本比例

5 结束语

该文首先利用改进压缩感知算法，估算出部分丢失数据的传感器节点数据信息，并把这些估算出信息的传感器节点当作已知节点，参与到其余丢失信息节点的估算中。再利用mule来执行关键任务，根据mule移动性能优势防止关键信息丢失。文中解决方案涉及构建最优汇聚树和查找不同网络结构(如线性图和网格)中的最优节点位置。基于各类拓扑结构特点，构造了近似算法，并进行了仿真实验，验证了算法的性能。仿真结果表明，相比其它几种算法，提出的算法完成数据恢复所用成本更低。

然而提出的算法也并非完美，它并没有考虑不同硬件环境对传感器耐久性的影响以及传输半径对mule旅行的影响，下一步的工作主要集中在这两方面上。