随着无线通信技术的不断发展, 对传输数据速率和频谱效率的要求不断提高^[1,2], 在这些技术中, 无线传感器网络(Wireless Sensor Networks, WSN)作为数据监测和数据获取的主要应用方式^[1], 通过多跳路由从传感器发送到一个或多个数据接收器. 同时, 随着移动技术的进步, 提出了在数据聚合过程中应用无人机的思想^[2,3], 由于传感器节点通常具有有限的计算能力和功率储备, 在数据聚合过程中利用无人机的主要目标是以所需的精度收集数据, 同时降低传感器的消耗^[4,5]. 压缩感知技术(Compressive Sensing, CS)^[6]对于有限资源的传感节点, 可以实现采集和压缩的功能, 这是资源有限的传感器节点的理想特性^[7], 文献[8]在CS数据采集方案中, 将WSN的N个传感器节点生成的原始数据向量表示为 ${{x = \{ }}{x_{\rm{1}}},{x_{\rm{2}}}{\rm{,}}\cdots{\rm{,}}{x_{{N}}}{{\rm{\} }}^{\rm{T}}}$ , 聚合过程建模为:

${\rm{y = }}\sum\limits_{j = 1}^{\rm{N}} {{x_j}{\phi _j}} {\rm{ = }}{\boldsymbol{\varPhi }}{\rm{x}}$

(1)

式(1)中, 每个原始数据x_j由权重向量φ_j编码, 该权重向量也是测量矩阵Φ的第j列向量, 测量矩阵Φ通常为M×N随机矩阵, M为权重向量数, N为网络传感器节点数, 以下均为此表述. 因此, 聚合向量y小于未知数据的数目, 当x满足k-稀疏时且矩阵Φ^M×N满足限定等矩性^[7](Restricted Isometry Property, RIP)条件时, Sink移动节点可以从 ${{y = \{ }}{y_{\rm{1}}},{y_{\rm{2}}}{\rm{,}}\cdots{\rm{,}}{y_{{N}}}{{\rm{\} }}^{\rm{T}}}$ 中恢复原始数据向量x的精度. 文献[8]采用局部混合CS方法构建簇的大小与传输次数之间的关系的模型, 以找到最优簇的大小, 以此来提高数据聚合的效率, 但由于无线传感网络拓扑结构具有动态性, 当新增传感器时, 局部CS方法较难快速构造出可行测量矩阵, 网络向所有传感器节点广播新的测量矩阵会增加能耗且数据重建误差增大; 文献[9]提出了全局CS的方法, 将感知数据进行加权计算而非将单个原始数据传送到每个Sink节点, 有利于数据向量的聚合, 但由于全局CS方法中点到点传输的次数一般大于传感器节点的最大传输单元, 需要将每个数据编码的权重向量分割成多个包, 这样会使传输的次数急剧增加, 导致更高的能耗.

综上所述, 为了解决上述基于CS方法的挑战, 本文提出了一种拓扑感知的无线传感网络数据聚合方案(TADA). 主要是利用拓扑信息以高精度重建原始数据, 构造测量矩阵对无线传感网络多路径转发, 从而进行全网络矢量分配, 并提出了基于平衡最小生成树的数据聚合算法, 使数据聚合更能适应拓扑结构的动态变化.

1 问题描述

在数据聚合过程中, 编码集D是一组权重向量, 用于对传感器节点的原始数据进行编码. 在接收器端, 该过程可以表示为:

$ {{y = }}{{\boldsymbol{\varPhi }}^{M \times N}}{{{x}}_J} , \;\; {{{x}}_{{J}}} \in {{{R}}^{N \times 1}}, {{y}} \in {{{R}}^{M \times 1}} $

(2)

式(2)中, ${{{x}}_{{J}}}{\rm{ = \{ }}{x_{\rm{1}}},{x_{\rm{2}}}{\rm{,}}\cdots{\rm{,}}{x_{{N}}}{{\rm{\} }}^{\rm{T}}}$ 表示路径J的数据, ${{\boldsymbol{\varPhi }}^{{{M}} \times {{N}}}}$ 为映射矩阵, 它由D的权重向量构成(即列向量), R为当前传感器节点. 当数据沿着从叶节点到汇聚节点的路径聚合时, 每个节点将它的数据加权向量与从它的子节点接收的向量组合, 然后将组合后的向量转发给相应的父节点; 最后通过多跳方式, 在接收端收集数据向量, 利用路径J的路由信息对 ${{{x}}_{{J}}}$ 进行解码. 在式(2)中, 测量信号 ${{{y}}_J}{\rm{ = \{ }}{y_{\rm{1}}},{y_{\rm{2}}}{\rm{,}}\cdots{\rm{,}}{y_{{N}}}{{\rm{\} }}^{\rm{T}}}$ 为在接收器处收集的数据编码矢量.

2 通信过程 2.1 TADA数据流

(1)网络初始化: N个传感器节点在有限区域内随机均匀分布. 设置一个平衡最小生成树(Balanced Minimum Spanning Tree, BMST)的拓扑构造算法(将在第4小节中进一步阐述), 在BMST形成拓扑结构后, 每个节点沿着BMST给出的路由路径向Sink发送帧跳信号, Sink收集所有的帧跳并相应地生成一个哈希表. 如图1所示, 首先, 哈希表记录每个路径的路径索引号和路由序列, 通过哈希表接收器获取最长的路由路径l_max, Sink生成一个权重向量数M≥l_max的向量编码集D={d_i}, 其中d_i∈R^M×1; 然后, 按照此权重向量分配策略, 从D中为每个节点分配一个权重向量, 即为矢量分配的策略, 将在2.2节中阐述.

(2)数据分帧: 初始化完成后, 每个节点通过将其与指定的权重向量 ${x_i} \times {{\boldsymbol{\varPhi }}^{M \times 1}}{\rm{(}}i{\rm{)}}$ 相乘, 对其原始传感基准 ${x_i}$ 进行编码, 并将其发送到其父节点. 如果节点J从节点i接收到包 ${x_i} \times {{\boldsymbol{\varPhi }}^{M \times 1}}{\rm{(}}i{\rm{)}}$ , 则将其编码的分组与接收的分组线性结合, 即 ${x_i} \times {{\boldsymbol{\varPhi }}^{M \times 1}}{\rm{(}}i{\rm{) + }}{x_j} \times {{\boldsymbol{\varPhi }}^{M \times 1}}{\rm{(}}j{\rm{)}}$ . 同时, 如图2所示, 帧头记录已将其向量添加到线性组合中的节点的索引号, 如果节点上没有需要上传的数据, 那么它会转发接收到的数据包, 帧头也不会记录其节点的索引号.

(3)数据预处理: 当接收器接收到一个数据包时, 就会检查来自帧头的索引号, 然后形成未知的原始数据向量, 最后运行数据检测算法.

2.2 数据检测

上所述过程中, 每个节点在发送到其父节点之前用权重向量 ${\phi _j}$ 对其自身的数据 ${x_j}$ 进行编码, Sink接收的数据包是所有数据编码向量沿路径的线性组合, 如式(3)所示:

${{y = }}\sum\limits_{j{\rm{ = }}1}^N {{x_j}{\phi _j}} $

(3)

图2描述了TADA中数据转发和收集处理的示例, 节点R₁将其数据编码向量发送到其父节点R₃. 然后, 节点R₃将其自身的数据向量与从节点R₁接收到的向量线性地组合成一个分组, 并将其转发到节点R₄. 这些进程不断重复, 直到组合的数据到达接收器为止. 在Sink节点收集的数据向量为:

${{y = }}{x_1}{\phi _1} + {x_3}{\phi _3} + {x_4}{\phi _4} + {x_7}{\phi _7} + {x_{10}}{\phi _{10}}$

(4)

原始数据向量的维数为N, 即为网络中的传感器节点数, 任何路径的原始数据向量只在路径上与这些节点对应的位置具有非零值. 对于上述示例中的x₁, 这些节点是节点R₁、R₃、R₄、R₇和R₁₀. 根据矩阵, 收集过程表示为:

${{y = }}\left[ \begin{gathered} {\phi _{1,1}}\cdots{\phi _{1,3}}\cdots{\phi _{1,7}}\cdots{\phi _{1,10}}\cdots \\ {\phi _{2,1}}\cdots{\phi _{2,3}}\cdots{\phi _{2,7}}\cdots{\phi _{2,10}}\cdots \\ \vdots \\ {\phi _{M,1}}\cdots{\phi _{M,3}}\cdots{\phi _{M,7}}\cdots{\phi _{M,10}}\cdots \\ \end{gathered} \right]\left[ \begin{gathered} {x_1} \\ 0 \\ {x_3} \\ {x_4} \\ 0 \\ 0 \\ \vdots \\ {x_{10}} \\ \vdots \\ \end{gathered} \right]$

(5)

3 向量分配策略 3.1 编码集D构造

从一个编码集D构造映射为矩阵Φ^M×N, 然后进一步解释网络中加入更多节点时如何扩展映射矩阵. 对编码集建模为:

${{\boldsymbol{\varPhi }}^{{{M}} \times {{N}}}}{{{x}}^{{N}}}{{ = }}{{{y}}^{{M}}}{{\rm ,\;\;s.t.}}\;{{N}} \ge {{M}}$

(6)

式中,N为网络中的传感器节点数或原始数据向量维数, ${{\boldsymbol{\varPhi }}^{{{M}} \times {{N}}}}$ 是存储在Sink节点中用于数据恢复的映射矩阵. 当节点数N增加时, 映射矩阵也随之改变, 使得映射矩阵的构造成为关键问题. 本文所提出的一种利用编码集D构造 ${{\boldsymbol{\varPhi }}^{{{M}} \times {{N}}}}$ 的方法, 首先将数据聚合过程并行分解为多条路由路径的数据转发过程. 如图3所示, 描述了路径1由{x₁, x₃, x₄, x₇, x₁₀}组成, 借鉴文献[10]的方法可分析为: 如果相应的权重向量{φ₁, φ₂, φ₃, φ₇, φ₁₀}为正交, 则Sink是具有路径1的路由表知识, Sink可以成功地检索{x₁, x₃, x₄, x₇, x₁₀}, 从而求解检测方程并得到唯一解.

基于上述分析, 设计了一个正交向量集 $D =\{ {d_{\rm{1}}}{\rm{,}} $ $ {d_{\rm{2}}}{\rm{,}}\cdots{\rm{,}}{d_{{l_{{\rm{max}}}}}}{\rm{\} }}$ , 其中 ${l_{{\rm{max}}}}{\rm{ = ma}}{{\rm{x}}_{_{{i}}}}{\rm{\{ }}{l_i}{\rm{\} }}$ , ${l_i}$ 为路径i的路径长度, ${d_j} \in {R^{{{M}} \times {\rm{1}}}}$ , $j \in {\rm{\{ 1,2,}}\cdots{\rm{,}}{l_{{\rm{max}}}}{\rm{\} }}$ 是相互正交. 很明显, 任何一个路径, 只要 ${{M > }}{l_{{\rm{max}}}}$ 且所有 ${l_i}$ 节点从集合中选择它们的权重向量D, 接收器Sink可以成功检索原始数据.

3.2 全网矢量分配策略

在构造编码集D之后, 下一步就需要将D扩散到整个网络, 利用哈希表进行矢量分配, 由于BMST总会生成一个树结构, 因此从接收器到任何节点的路径都是唯一的, 向量分配过程由Sink节点执行.

如图4所示, 前一示例的权重向量分配对于任何路径i, Sink首先检查哈希表中的信息, 然后Sink按照节点存储在哈希表中的顺序逐个分配D的向量. 路径2由4个传感器节点组成. Sink首先从哈希表中查询信息, 然后依次将权重向量d₁, d₂, d₃, d₄分配给节点R₁₀, 节点R₇, 节点R₆, 节点R₅. 然后, 按照分配给传感器节点的权重向量的顺序, 通过对齐来构建整个网络的矩阵Φ^M×N. 从而构造一个了策略矩阵, 得出最长路径完全消耗了编码集D的权值向量, 由于每个路径权值向量的正交性, 测量矩阵可以高精度地检索任意路径的原始数据, 从而进行网络扩展.

4 基于BMST的数据聚合算法

上述策略矩阵的构造, 是通过编码集D的基数l_max逐步扩展网络, 而l_max则是整个网络中最长路径的长度, 为使扩展的网络达到平衡状态, 采用平衡最小生成树(Balanced Minimum Spanning Tree, BMST)^[11]. 网络中的节点i先不发送原始数据d_i, 而是根据从编码集D分配的权重向量对d_i进行编码, 并将长度l_max的权重数据发送到其父节点. 因此, 每次传输的有效载荷是l_max, 而本文的主要目的是降低l_max, 从而降低数据聚合过程中的能耗. 在所有路径长度均为平衡的条件下, 在所提方法中考虑了树构造的邻居节点选择跳数. 树的构造过程从Sink节点开始, Sink选择一个最优节点, 并在每个结构更新步骤中将其添加到网络中. 此进程终止, 直到所有节点都在网络上. 这里, 最优节点是指对平衡树贡献值最大的节点. 将树上未连接节点k与节点n连接的贡献评估函数表示为C(D'(d_{n, k}), J(h_n)). 其中, D'是编码集，包含了原始数据d_i到d_k的距离, k是节点k到节点n的距离, J是h_n的函数, h_n是连接节点n到Sink的跳数. 用C来表示k到n的连接贡献, 定义为:

${C} {\rm{(}}{d_{n{\rm{,}}k}}{\rm{,}}{h_n}{\rm{) = }}\alpha {D'} {\rm{(}}{d_{n{\rm{,}}k}}{\rm{) - }}{J} {\rm{(}}{h_n}{\rm{)}}$

(7)

其中, α是D'(d)的正系数, 控制距离对路径选择的影响, 选择附近的节点加入网络可以促进降低能耗. 因此, 函数D'定义为:

${D'} {\rm{(}}d{\rm{) = 1/}}{d^{\rm{2}}}$

(8)

式中, 函数J(h_n)表示节点n到达接收器的跳数函数, 而跳数越多会导致拓扑不平衡, 即对网络贡献的一种惩罚. 因此, 为了让J(h)随着跳数h的增加而增长得更快, 加入系数λ为惩罚度, 使函数J(h)定义为:

$J{\rm{(}}{h_n}{\rm{) = }}{{\rm{e}}^{\lambda h}}$

(9)

BMST生成方法如算法1所示.

算法1. BMST生成

1. 输入: N //节点数量, T_t//拓扑表, F_t //未连接节点集合, h_j //从节点j到Sink的单跳数量, p_j //父类节点索引

2. 搜索最近的节点j至Sink 且生成一个路由表

3. T_t ={Node_j:{h_j, p_j}};

F_t ={ Node₁, …, Node_N }/ Node_j;

4. Set C_max←−∞

5. while i in N−1 do

6. 　Set C_max←−∞

7.　　 while Node_k in F_t do

8.　　　 while Node_n in T_t.Node do

9.　　　　Count C(d_n,k , h_n);

10.　　　　 if C(d_n,k , h_n)≥C_max then

11.　　　　　Set C_max←C(d_n,k , h_n)

12.　　　　　Set s←k

13.　　　　　Set h_s←h_n+1

14.　　　　　Set p_s←n

15.　　　　 end if

16. 　　　 end while

17.　　 end while

18.　　 T_t←T_t∪{Node_s:{h_s, p_s}}

19.　　 F_t←F_t / Node_s

20. end while

21. 输出: T_t

5 实验结果分析

将本文所提方法与RW方法^[12]和ICS方法^[13]进行比较, 并从数据聚合能耗、数据重建恢复率和测量矩阵存储要求3个方面对本文所提方法进行了评估.

5.1 数据聚合能耗

假设N个传感器节点随机均匀地分布在一个正方形区域中, 准备将其读数发送到Sink节点. 这时, 将网络通信能量消耗表示为E, 表示与权重向量大小和传输次数有关. 计算为:

$E{\rm{ = }}O\left( {\left[1 + \frac{{{{Vector Si{\textit{z}}e}}}}{{{{MTU}}}}\right] \times {{Transmission Number}}} \right)$

(10)

式中, MTU表示由通信协议确定的最大传输单元, 如果在所考虑的数据聚合网络中由M确定的向量大小大于MTU, 则将每个加权向量分割成 $\left[1 +\dfrac{{{{Vector Si{\textit{z}}e}}}}{{{{MTU}}}}\right]$ 个包. 让每一轮数据表示每个节点完成将其缓冲区的第一次读取上载到Sink节点的时间段, 传输数是指每一轮数据聚合中的点对点传输的总数.

(1)第一种情况下: 在WiFi环境下权重向量M的远远小于MTU, E主要由发送的数目N_T控制. 如图5所示, 本文所提方法与ICS和RW相比, 本文方法比RW能量消耗更低, 这是由于本文所提TADA方法构造了一个编码集D映射为矩阵Φ^M×N, 进而扩散到整个网络, 相比RW方法降低了传输的次数, 让每一轮数据表示在一定正方形区域内. 但是本文方法与ICS相比, 能量消耗仍然较高, 这是由于在形成网络过程中, 形成了一个BMST树形结构, 每一次通信传输均需要计算到叶子节点, 增加了每轮数据的传输计算次数和时间.

(2)第二种情况下: 考虑传感器节点正在利用轻量级通信协议(如蓝牙或ZigBee网络环境下), 其具有较小的MTU, 它需要将一个数据编码的权重向量分割为若干个数据包进行发送. 考虑包括300个节点和M_ICS＝86和M_TADA＝9的场景, 能耗比较如图6所示. 由于权值向量较小, TADA在能耗方面具有更好的性能优势. 这是由于本文方法采用了最小平衡树, 使网络达到平衡状态, 用贡献平衡函数使Sink跳到最优节点, 控制距离对路径选择的影响, 达到聚合过程中的能耗. 因此, 当使用轻量级通信协议时, TADA是首选的.

5.2 数据重建恢复率

由于数据聚合的目标是收集感测到的原始数据, 因此会检查不同协议的数据恢复率. 在CS中, 通过一些贪婪的算法从M维数据向量y中恢复N维信号向量.

考虑一个N=100节点的WSN网络, 假设原始数据x由k∈{4, 5, 6, 7, 8, 9, 10}稀疏源产生, RW, ICS和TADA的权重向量M=20. 如图7所示, 显示了具有3个协议的网络的错误率曲线. 结果表明: 无论稀疏度k有多大, TADA网络的错误率都可以忽略不计, 但RW和ICS的错误率都随着稀疏度k的增加而增加. 参考文献[14]所得出的证明, CS随机矩阵成功恢复数据的概率为 ${{P = 1 - 2}}{{\rm{e}}^{{\rm{ - }}{\delta ^{\rm{2}}}{{M/8}}}}$ , 其中δ是限定等距常数(RIC), 换言之, RW和ICS的恢复误差是不可避免的. 这是由于本文方法逐步分配权重向量和策略矩阵, 在贡献平衡函数中选择控制距离, 从而使将叶子节点到父节点的每条路径由相应的权重向量子集构成正交矩阵的子矩阵, 以顽强满足数据恢复的要求.

6 结论与展望

本文构造测量矩阵将数据分解为多个路径转发, 从而进行全网络矢量分配, 并提出了基于平衡最小生成树的数据聚合算法, 缓解了无线传感网络中数据聚合能耗和重建误差问题. 但本文方法对数据的构造还不够精确, 在聚合过程中较难把握通信数据的语义方向, 在下步工作中需要进一步完善编码集D的构造和矢量分配, 以优化整个算法性能, 进一步适应动态拓扑的变化.