拓扑感知的无线传感网络数据聚合方法①

熊 英,李 芸

1(江门开放大学 信息技术部,江门 529234)

2(东华理工大学 水资源与环境工程学院,南昌 330013)

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

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

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

1 问题描述

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

式(2)中,xJ={x1,x2,···,xN}T表示路径J的数据,ΦM×N为映射矩阵,它由D的权重向量构成(即列向量),R为当前传感器节点.当数据沿着从叶节点到汇聚节点的路径聚合时,每个节点将它的数据加权向量与从它的子节点接收的向量组合,然后将组合后的向量转发给相应的父节点;最后通过多跳方式,在接收端收集数据向量,利用路径J的路由信息对xJ进行解码.在式(2)中,测量信号yJ={y1,y2,···,yN}T为在接收器处收集的数据编码矢量.

2 通信过程

2.1 TADA 数据流

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

图1 哈希表

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

图2 TADA 数据传输

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

2.2 数据检测

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

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

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

3 向量分配策略

3.1 编码集D 构造

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

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

图3 并行分解的数据转发过程

基于上述分析,设计了一个正交向量集D={d1,d2,···,dlmax},其中lmax=maxi{li},li为路径i的路径长度,dj∈RM×1,j∈{1,2,···,lmax}是相互正交.很明显,任何一个路径,只要M＞lmax且所有li节点从集合中选择它们的权重向量D,接收器Sink 可以成功检索原始数据.

3.2 全网矢量分配策略

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

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

图4 权重向量分配和策略矩阵构造

4 基于BMST的数据聚合算法

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

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

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

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

算法1.BMST 生成1.输入:N//节点数量,Tt//拓扑表,Ft//未连接节点集合,hj//从节点j 到Sink的单跳数量,pj//父类节点索引2.搜索最近的节点j 至Sink 且生成一个路由表3.Tt={Nodej:{hj,pj}};Ft={ Node1,…,NodeN }/ Nodej;4.Set Cmax←-∞5.while i in N-1 do 6.Set Cmax←-∞7.while Nodek in Ft do 8.while Noden in Tt.Node do 9.Count C(dn,k,hn);10.if C(dn,k,hn)≥Cmax then 11.Set Cmax←C(dn,k,hn)12.Set s←k 13.Set hs←hn+1 14.Set ps←n 15.end if 16.end while 17.end while 18.Tt←Tt∪{Nodes:{hs,ps}}19.Ft←Ft/ Nodes 20.end while 21.输出:Tt

5 实验结果分析

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

5.1 数据聚合能耗

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

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

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

图5 本文所提方法与ICS、RW在节点数的能耗比较

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

图6 本文所提方法与ICS、RW在MUT 大小的能耗比较

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-2e-δ2M/8,其中δ是限定等距常数(RIC),换言之,RW和ICS的恢复误差是不可避免的这是由于本文方法逐步分配权重向量和策略矩阵,在.贡献平衡函数中选择控制距离,从而使将叶子节点到父节点的每条路径由相应的权重向量子集构成正交矩阵的子矩阵,以顽强满足数据恢复的要求.

图7 本文所提方法与ICS、RW 数据重建错误率比较

6 结论与展望

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