基于超越数论的无线传感器网络时空编码方法

胡宗升，邢 凯，2，许 静

（1.中国科学技术大学 计算机科学与技术学院，合肥 230026；2.中国科学技术大学 苏州高等研究院，江苏 苏州 215123）

0 概述

无线传感器网络（Wireless Sensor Network，WSN）一般由一系列能够感知周围环境，使用无线信道进行通信的传感器节点组成，是一种能够进行感知、处理、存储和传输感知区域信息的分布式自组织网络，其在国防军事、防灾预警、气候监测、交通运输、环境与农业等领域具有广泛的应用。在这些领域中，存在大量应用需要WSN 能够快速、持续地收集全局信息，并及时做出决策和调度。因此，信息的收集汇聚是无线传感器网络的主要任务之一。但是，在数据多跳汇聚过程中，中继节点的存储转发产生了大量的通信、存储和能量开销。而无线传感节点只有有限的通信带宽、存储容量以及能量。在大规模分布式环境下，传统方法难以调和其信息通信、存储、能量约束与全局信息收集的持续性和及时性要求之间的冲突。为解决这一挑战，研究人员针对大规模分布式无线传感器网络在信息收集汇聚方面的传输和能耗问题进行了大量研究［1-3］。

在信息收集汇聚任务中，无线传感器网络一般通过网络的各个节点将其所感知信息经由中间节点多跳传输汇总到基站。这种方式的缺点主要是：依赖中间节点的路由中继，如果中间节点故障，则会导致某些节点信息无法到达Sink 节点，继而无法到达基站，因此需要常态化地、持续地监控并维护网络，开销巨大；受限于单点失效问题，一旦汇聚节点失效，就意味着网络可用性降低甚至不可用，对汇聚节点选取要求高；通信和能耗问题，节点离基站越近，通过该节点的信息越密集，中继通信负载越大，能耗也越高，会带来较严重的负载均衡问题，当基站附近的节点在耗尽能量、通信带宽和存储空间后，会导致可用性问题。

针对无线传感器网络在信息汇聚任务中的汇聚节点失效和中继路由可靠性问题，当前研究往往采用骨干拓扑的方式，利用簇（如LEACH［4-5］算法）或者树的方式（如LPT［6］算法）汇集数据，例如网络根据拓扑位置或能量等特性将网络划分为多个簇，或通过分布式汇聚算法形成树状等骨干拓扑，节点收集信息后发送给骨干拓扑节点并通过骨干网汇集信息。这种方式不依赖于中心节点，传感器节点只需和附近邻居节点通信，以自组织骨干网通过多跳的方式协作进行信息传输。相应地，节点也需要更多通信开销来完成骨干网拓扑维护、时间同步、节点选举等工作，从而导致较高的网络延迟和维护开销，因此对于全局信息收集有实时性要求的场景，例如防灾预警、入侵检测等难以提供有效保障，同时每个节点都有持续的通信和维护开销，进一步挤压了节点的通信和续航能力。然而，随着对掌握全局信息需求的提高，传统的信息汇聚方法不可避免地带来全网范围的信息收集和大量的中继存储转发开销，这些通信和存储所带来的能耗、带宽及存储开销巨大。因此，如何降低网络中的传输/存储开销一直是大规模分布式无线传感器网络信息收集与汇聚研究中的重点方向。

针对无线传感器网络在信息汇聚任务中的海量信息传输/存储开销问题，一个直观的做法是将数据进行编码/压缩之后再进行传输和存储。如面向多播传输的网络编码方法［7-9］，基于图论中最大流最小割原理保证了多播网络在确定性路径下可以达到网络最大信息流，直观上减少了网络传输次数，然而该方法在信息汇聚和单播网络通信应用中因拓扑/路由的不确定性而难以被广泛应用。压缩感知［10］（Compressor Sensing，CS）方法突破了传统奈奎斯特采样定理。不同于传统的压缩方法是先采样再压缩，压缩感知则是采样与压缩同时进行，且解码算法独立于压缩算法，因此尤其适合资源受限的传感器网络，压缩和恢复算法的独立意味着能够根据传输路径的变化而灵活地进行感知和数据重建。但是，压缩感知是有损压缩，其精度依赖于感知数据分布，当数据分布变化时稳定性欠佳，在信噪比较低和分布波动大时尤其如此。不难看出，信息收集汇聚过程中的信息压缩效率和相关算法的通用性始终是该研究领域的重要挑战。

从以上研究进展可以看出，以计算开销来降低/部分替代通信和存储带来的开销，是资源受限的大规模分布式无线传感器网络的信息通信、存储和能量约束与全局信息收集的持续性和及时性要求之间矛盾的一个重要趋势变化，也是当前大规模分布式无线传感器网络研究的重点，即存算通信一体化研究。

针对大规模分布式无线传感器网络中以存储转发方式为主的传统信息收集汇聚方式，本文提出一种以计算方式降低/部分替代通信和存储开销的存算通信一体化新方法，并给出相关理论分析和论证。

1 相关工作

对信息的收集和汇聚是信息系统持续优化和决策的前提条件，其中网络拓扑的感知与维护在信息汇聚过程中不可缺少。

拓扑感知（Topology Sensing）是分布式网络感知和维护拓扑信息的重要方法。Topology Sensing可以分为In-network 和Out-network 两类。早期的拓扑感知的工作主要集中在网络感知方面，并通过交换路由信息来实现。例如使用SNMP 协议主动监测网络中协议、接口、速度等信息来生成完整的网络视觉地图。也有研究利用开放最短路径OSPF 来跟踪域内拓扑信息，以此来构建一个及时准确的拓扑信息。Out-network 受到了更广泛的关注，文献［11］将信息传递过程视作一个Hawkes 过程，从有限的被动网络活动观测来表征和分析无线网络，检测现有拓扑的变化以及提取网络中信息流的信息，并利用模型和数据推断网络事件之间的联系，识别出事件链。文献［12］考虑WSN 中负载不均匀的问题，利用势博弈理论，提出了拓扑控制算法BLTC。该算法能够评估附近节点，根据效用函数选择节点构建拓扑，将节点能耗均匀问题转换为博弈问题，能够有效提高网络寿命，但缺点是网络的博弈阶段较长，延长了数据收集过程的延迟。文献［13］进一步对网络拓扑修复进行了调研，总结和分析了各类拓扑修复方法的优缺点。

无线传感器被大量应用于监测预警的场景，如何保证这些场景下信息收集的准确性、实时性以及持续性是非常关键的问题。事件检测的相关工作有基于阈值的方法、基于模式的方法和基于学习的方法［14］。在基于阈值的网络监测/事件检测研究中，阈值通常由领域专家定义，当检测到的值高于（低于）阈值时，会触发通知事件，并通过网络传输到基站或外部系统，其优点是简单，缺点是当数据需要传输到系统外部进行检测评估时，增加了通信开销，降低了事件检测及时性。文献［15］基于模式匹配的监测方法从感知数据中提取事件模式，并将事件检测问题转换为模式匹配问题。文献［16］使用Contour Map作为数学工具来对事件模式进行建模，进一步提高事件检测准确性。随着机器学习和深度学习的发展，网络监测逐步采用数据驱动的机器学习方法，取得了很好的效果。文献［17］通过主成分分析（Principal Component Analysis，PCA）在线进行降维，以处理输入数据中的无关和冗余数据。基于预测值与真实值的偏差，通过动态阈值法实现网络监测/事件检测。文献［18］在多维特征空间中应用了支持向量机（Support Vector Machine，SVM）、k近邻（k-Nearest Neighbor，k-NN）、高斯混 合模型（Gaussian Mixture Model，GMM）等方法，解决了传统方法监测效率低、误报率高的问题。此外，文献［19-20］对时效性展开研究，分别就时间同步和时延问题进行了分析。上述研究的优点在于能够识别较广泛的事件类型，缺点在于无法识别首次出现的事件，每次都需要重新训练模型以适应新事件类型。

WSN 中大部分节点依赖于容量有限的电池供电，能量耗尽将影响节点的可用性，因此在设计相关信息收集算法时需要考虑到节点是否有足够的能量完成数据收发任务。LEACH（Low-Energy Adaptive Clustering Hierarchy）是WSN 中专注于低能耗的最重要协议之一，LEACH 随机挑选节点作为簇首节点，每个簇首节点汇集本簇节点数据后传输给Sink 节点，簇首节点的巨大消耗通过随机算法均摊到各个节点上。在LEACH 出现后，文献［21-22］为了改进能量使用效率，将节点剩余能量作为簇首节点选取因素。文献［23］将簇划分算法改为基于k-d树算法的递归矩形分区算法来提升性能。PEGASIS［24］不同于LEACH 以簇来划分，PEGASIS使用链划分。节点在收到数据后传递给后续节点，直到最终传递到Sink 节点。PEGASIS 依赖于节点对全局知识的掌握，节点使用贪心算法选取下一个最邻近节点作为后续节点。文献［25］提出一种自适应数据聚合方案，该方案依赖于节点能量值的上下限，如果低于较低阈值则会进入休眠状态。文献［26］考虑了由能量问题带来的延迟，提出能量碰撞的概念，即当两个节点计划进行传输时，由于其中一个节点最近的一次活动使得本次没有足够能量进行收发，导致此次传输无法进行。上述协议能够提高网络的负载均衡性，但是信息感知的延迟通常较大。由于对信息是透明的，因此无法解决大规模网络下庞大原始数据的传输带来的通信问题。

为了实现持续及时地收集网络全局信息的目标，减少网络延迟，降低网络传输次数和通信量是其中的重点。在分布式系统中，随着对把握全局信息的需求的提高，必然会出现全网信息收集和大量的洪泛开销。为解决其中产生的数据传输和存储开销问题，一个直观的做法是将数据进行压缩，之后再进行传输和存储。目前通用的压缩算法可以分为有损数据压缩算法和无损数据压缩算法。前者可以无损恢复压缩前的数据，原理是根据数据冗余特性，引入信息墒理论计算的编码极限，缺点是压缩效果不明显，对算力有一定要求，成本较高。有损数据压缩算法针对的大多是多媒体数据，压缩后重建的数据质量有所损失，如图像压缩算法JPEG、视频压缩算法H.261、音频压缩MP3 和语音压缩G.711。当分布式系统产生的数据具有一些特性时，往往可以采用一些特殊算法，这方面相关的研究有基于数据时空冗余性的压缩算法。基于时空冗余性的压缩算法利用了单个节点所采集的数据在时间上的冗余、邻居节点采集的数据之间的空间冗余性以及单个节点在关联属性之间的冗余。这类算法采用预测估计技术将实测值和预估值进行差分运算以消除冗余。由于节点运算和存储资源受限，通常使用低阶编码进行预测，因此只适用于低精度事件检测场景。也有研究使用高阶多项式最小二乘曲线拟合将采集的数据在网管进行解码。这些算法时间复杂度高，计算量大。基于奇异值分解以及离散傅里叶变换的技术在这种场景下压缩能力强，但是普遍计算量偏大。

基于压缩感知算法是根据陶哲轩等人提出的压缩方法，其突破了传统奈奎斯特采样定理。压缩感知相较于其他压缩算法，不同点在于：信号是稀疏的，数据的压缩和采样是同步的，压缩算法和解码算法之间较独立。压缩感知需要的信号是稀疏的，这在大规模网络中，尤其是传感器网络中非常符合。传统的压缩方法是先采样再压缩，而压缩感知同时进行则加快了感知的速度。在资源受限的传感器网络中，压缩和恢复算法的独立意味着能够根据情况灵活设计。文献［27］使用PCA 分析和Bayes 方法设计了一种在线压缩恢复方法，通过返回信号恢复误差到压缩感知框架来自动调整系统参数，从而动态适应信号特征。但是压缩感知的问题在于精度不稳定，在信噪比较低、信号波动大时尤其如此。

网络编码（Network Coding，NC）［28］是近年来通信领域一个活跃的研究分支，其基本思想是网络节点不仅参与数据转发，还参与数据处理，这样可以大幅提高网络通信性能，但其可行性依赖于特定拓扑结构。在此之前，信息交换不会和其他信息融合。在端到端的信息交换过程中，路径上的其他节点起到的作用是简单的存储和转发，即路由交换的功能。节点不会对原始数据进行修改，数据包的完整性在整个传输过程中不会被破坏。而在网络编码中，节点可以将多个数据包混合之后转发，以提高系统的吞吐量，减少网络延迟，以及在无线传感器网络中减少每比特能量消耗。网络编码中对于节点混合信息的要求是：只要接收节点有足够多的Evidence 和Clues 用来重构从发送节点发出的原始数据包即可［29］。信息的混合在实现上若为线性操作和非线性操作，称为线性/非线性编码，此外还有引入随机系数的方法，即随机线形网络编码（Random Linear Network Coding，RLNC）。RLNC 实现更加简单，但缺点是计算复杂度为O（n3），其中，n为节点监听到的数据包。文献［30］考虑节点能耗和网络寿命问题，提出一种基于网络编码的低能耗可靠机会路由算法，该算法通过丢包率和误码率来计算失败概率，从而降低重传次数。虽然该方法能降低能耗，延长网络寿命，但缺点是转发集内数据包过多。文献［31］将网络编码和拓扑控制相结合，提出一种数学模型，在模型中同时考虑到了传输功率和接收能量。该方法使用遗传算法来搜索最佳方案，可以实现均衡的负载和更长的网络寿命，但其缺点在于计算过程非常复杂且耗时，在大规模网络中尤其如此。文献［32］提出一种机会网络编码（Opportunistic Network Coding，ONC），每个中继可以选择编码之后再发送，可直接发送原始数据、一次平衡时延和吞吐量。网络编码优点在于通过对信息进行编码，利用节点间多条传输路径，以增加传输吞吐量。而节点需要等待有足够的数据包来完成解码，这就造成了时间延迟以及能耗问题。为了等待一些数据包到达而不得不先存储已经到达的数据包，可能会导致缓冲区溢出或者数据包丢失。

2 基于超越数论计算空间的时空编码构造方法及其特性研究

2.1 计算空间中的无线传感器网络模型

2.1.1 网络模型

本文研究的对象是分布式与节点能力受限的无线传感器网络。将整个网络表达为G(V,E)，一个由节点Vi和链接E组成的无向图结构，网络中节点的个数使用N或者|G(V,E)|来表示。无线传感器网络模型如图1 所示。

图1 无线传感器网络模型Fig.1 Wireless sensor network model

WSN 使用消息来实现松散时钟同步，在初始时刻t0系统会完成初始化工作，节点通过与邻居的消息来同步推进本地时钟。在初始化阶段，节点会被赋予一个唯一的初始混沌编码，以及一个素数生成规则函数πi(t)。函数πi(t)用来生产辅助运算数组。素数生成函数可以按照某个特定规则产生，例如顺序取第(i+nt)个素数作为第i个节点的第t轮时钟的素数，即：

2.1.2 节点模型

在本文的设计中，节点需要像神经元一样能够对外界事件做出响应，根据响应计算并更新本地编码。而出于节能的考虑，节点应该在完成计算时进入休眠，所以节点应该处在动态的变化中。为此，为网络和节点设计以下4 种状态：

1）局部收敛态：当前时钟轮和上一时钟轮的编码值差值小于阈值ϵ，即

2）全局收敛态：所有节点都进入局部收敛的状态，即全局处于收敛状态。

3）局部稳定态：节点相邻两轮编码差值小于阈值ϵ，或上轮状态为稳定态且本轮无邻居节点的扰动。

4）局部扰动态：在节点处于局部稳定态下，本地节点的邻居有节点加入或者退出。

2.2 节点编码计算模型

在不同状态下，节点运行不同算法过程来计算编码，主要分为扰动计算和收敛计算两个部分。

2.2.1 扰动模块

在初始化时网络处在全局收敛状态，各个节点处在局部收敛状态。当节点Vi检测到直接的拓扑变化事件，或者通过邻居节点的编码获知网络某处的拓扑发生变化时，那么就会进入到扰动态，执行扰动计算。如果没有事件发生则在下轮重新进行检测，本轮编码保持不变，即。具体步骤如下：

1）扰动检测：分为直接检测和邻居编码间接检测，两者都只有在节点处于收敛态下才有效。如果在非收敛态下检测到，直接检测的结果将会被延迟触发，间接检测结果将直接被忽略。则直接检测即节点通过心跳等方式检测到邻居节点的上下线事件，间接方式为检测是否有邻居节点的编码出现扰动信号。表达式如下：

若满足条件则进入局部扰动态，继续执行步骤2，否则跳出，并在下轮进行检测。

2）编码规范化处理：将尖峰信号处理取倒数，其他编码不变。

3）计算邻域几何均值：根据上一步统一规范化处理后的编码计算其几何均值。

5）完成扰动：推出扰动计算，进入收敛计算过程。

通过扰动计算，节点将事件产生的扰动信息以类Gossip 方式传播到全网络中，从而让所有的节点都能感知到该扰动，这种机制保证了本文算法4 个特性中的传播性。系统完成一次扰动计算之后马上就进入到收敛计算，在收敛计算过程中，节点不会再次进行扰动计算，这可以避免网络中出现同一个事件消息多次被识别为扰动源。

2.2.2 收敛模块

当结束扰动计算后，收敛计算将会持续多轮直到本地节点进入到局部收敛态。如果将扰动计算过程视作扰动产生的全局信息的传输过程，那么收敛计算则可以看作对该信息的存储过程。收敛计算的具体步骤如下：

1）编码规范化处理：计算邻域几何均值，过程同扰动模块。

2）编码更新：如果编码的差值小于阈值ϵ，则进入到局部收敛状态，编码无须更新，否则更新编码。

3）状态更新：如果当前状态被评估为非局部收敛状态，那么不退出当前收敛计算过程，下一轮将重复步骤1～步骤3。如果当前已经是局部收敛状态，那么再评估连续处于收敛状态的轮数是否大于D（D为网络直径），如果大于则进入到稳定态，否则节点将依然处于局部收敛状态并将继续执行上述算法，直到满足稳定态条件退出当前计算过程。节点状态变化过程如图2 所示。

图2 节点状态变化过程Fig.2 Process of node status change

2.2.3 整体计算模型

在网络正式运行前，需要完成节点的初始化工作，此时节点处于局部收敛状态。节点之间通过消息同步时钟，节点持续在每轮时钟下监测邻居节点的活跃性，执行扰动模块的算法过程。当检测到扰动信号时，执行收敛模块过程，2 个模块和4 种状态的交替构成了整体算法过程，如图3 所示。

图3 节点的整体计算过程Fig.3 Overall calculation process of nodes

2.2.4 性质

基本性质主要有以下4 种：

1）传递性

定义：给定一个连通网络G(V,E)，当完成初始化工作后，若网络某处发生拓扑事件变化，则时空编码构造的算法过程会将该事件传递到网络所有节点下，使得节点由全局稳定态进入局部扰动态，进而完成计算编码过程。

证明：假设拓扑事件发生时与事件源所在节点为Vi，其所关联的邻居节点Ni一定能直接检测到事件信息并运行扰动模块，传递尖峰编码。当邻居节点Ni产生尖峰编码后，节点的邻居节点将在本时钟轮收到尖峰编码，在下一个时钟轮中，将由局部收敛态进入到局部扰动态。同样地，邻居节点也会生成尖峰编码，并传递给其邻居节点。由于给定的网络为连通网络，且拓扑事件不改变连通性，那么邻居节点Ni发出的尖峰编码将最多经历|D| 个时钟轮就使得所有的节点从稳定态进入局部扰动态，这里的|D|为网络的直径大小。也就是说，时空编码构造过程能够在最多|D|个时钟轮之后将网络中的某处发生的拓扑事件传递到全网所有节点，即传递性得证。

2）收敛性

定义：给定一个连通网络G(V,E)，当网络中某处产生了拓扑事件，所有节点从全局收敛态进入到局部扰动态（传递性），收敛性将保证网络所有节点按照收敛模块算法运行有限时间之后重新收敛到全局稳定态。

定理1任意节点Vi的编码可以表示为，其中，αi是代数数，pi是素数［33］。

证明：网络G(V,E)的某处发生了拓扑事件，节点将不断执行收敛模块算法，更新本地编码值，变化的编码值始终处在范围（0，1）中。由定理1 可知，在第t时钟轮，节点Vi的编码可以表示如下：

式（10）说明，节点在执行收敛模块算法过程中，节点的编码值不断递减。而收敛模块中当节点的编码值小于阈值ϵ时，编码将保持不变，多轮之后节点进入本地收敛态。上述过程说明，节点在多轮时钟之后将进入本地收敛态，当所有节点都进入本地收敛态后，全网状态则进入全局收敛态。

3）因果性

定义：给定一个连通网络G(V,E)，在相同的初始化配置和相同输入的情况下，时空编码的算法过程将产生相同的编码序列。而在初始化配置不同和（或）输入不同的情况下，算法过程将产生不同的编码序列，即以下3 种情况：（1）相同初始条件，不同的拓扑事件原因将产生不同结果；（2）不同初始条件，相同的拓扑事件原因将产生不同结果；（3）不同初始条件，不同的拓扑事件原因产生不同结果。

定理2对于一个连通网络G(V,E)，在某个时刻下，全局的拓扑连接矩阵表示为C，全局编码集合表示为X。在经过一次拓扑事件后，全局拓扑连接改变为C1，对于任意两个网络中的节点Vi、Vj,i≠j，必然有

定理3对于一个连通网络G(V,E)，在某时刻下，全局的拓扑连接矩阵表示为C，全局编码集合表示为X。当经过两次拓扑事件后，全局拓扑发生改变：

由此造成的全局网络中各个节点的本地编码均不相同，有：

其中：Vi、Vj为网络中的节点，且允许i=j的情况，这种情况即相同节点在不同的拓扑结构下编码是不同的。

证明：由以上两个引理可以推出在相同初始配置和相同输入情况下编码序列相同。而不满足任意一个条件都将使得编码序列不同，有：（1）相同初始条件，不同的事件序列导致不同的全局编码序列；（2）不同初始条件，相同的事件序列有不同全局编码序列；（3）不同初始条件和不同时间序列有不同全局编码序列，即事件原因和结果一一对应。

4）确定性

定义：在相同的网络初始化条件下，给定系统相同的输入，时空编码算法过程总是到达相同的网络状态，产生一致的输出结果。

证明：由时空编码算法的数学过程可知，涉及编码计算的函数均为单射的确定性函数。因此，给定相同的初始条件，保证节点能正确执行编码算法的情况下，时空编码运行的整个过程是确定的，不会有随机因素参与并改变执行的结果。其演化过程在相空间中表现为固定的轨迹。

3 基于超越数论时空编码的无线传感器网络信息存算通信一体化方法

3.1 基于无线传感器网络模型的编码方法

本节提出基于非定域感知理论的时空编码方法，将非定域感知理论的拓扑感知场景扩展到普遍的信息感知场景下，并给出数据收集与感知的具体编码过程。

在网络处于全局收敛的状态下，节点或者边的增加或者删除会生成一个尖峰信号，尖峰信号将会被记录在节点的本地编码中，最终被全网所有节点感知到。这种蝴蝶效应的结果将会被反映到网络所有的节点的本地编码中。节点将本地编码运行分解算法得到传播路径，从可以定位得到扰动源节点，实现非定域感知。如果将扰动源节点固定为两个节点，并将其映射为0 和1，那么可以将普遍的信息映射到每个节点的本地编码中，编码过程如图4 所示。如算法1 所示，将一系列事件信息以0-1 序列形式注入到网络中，经过节点反复的收敛和传播计算，这些信息将会被编码存储在网络所有节点中。

图4 编码过程Fig.4 Encoding process

算法1基于非定域感知理论的混沌编码过程

3.2 基于无线传感器网络模型的解码方法

根据前文对非定域感知理论的讨论可知，本文算法具有因果性和确定性，在某个时间点下产生的事件将会唯一地被记录在网络中各个节点的本地编码中，并能够唯一地被解析恢复。基于前面的编码算法，本文提出一个基于编码序列的解码方案，解码过程如图5 所示。如算法2 所示，此方案利用基于扫描线的搜索算法定位引起上一次网络拓扑变化的源节点，通过多次定位事件源节点来解析出源事件序列。对于节点来说，只需在解码时执行此算法，在一般情况下只需要接受邻居编码并更新本地编码即可。通过这种策略，本文将通信和存储域上的开销转移到计算域上的开销，突破了节点存储和通信能力的限制，从而能达到持续地、实时地、非定域地感知信息。

图5 解码过程Fig.5 Decoding process

算法2非定域时空编码解码过程

4 实验结果与分析

4.1 实验设置

实验使用Ubuntu 18.04 LTS 版本为操作系统，CPU 为i7-9750H，软件环境为Java17.0.2，JVM 为HotSpotTM64 bit Server VM。实验通过多线程模拟节点，使用线程的创建，销毁仿真节点的加入退出的行为。节点之间的通信使用Socket 通信方式来完成，这一方案也有利于模拟实际通信过程中的丢包、重连等情况。另外，系统中的松散时钟部分使用了基于消息的同步机制来进行模拟。实验将网络分为编码输入节点、普通节点以及在普通节点中随机选取的节点作为解码节点。实验将编码固定输入节点表示为NODE0、NODE1，以拓扑变化事件信息源固定为编码输入节点的拓扑变化事件，将感知信息抽象为0-1 序列，随机选择要输入的0-1 序列信息Sin=b0,b1,…,bn，其长度为n=|Sin|，bi∊0,1。输入完毕后网络处于全局收敛状态，此时随机选取节点NODEr作为解码节点，运行算法2，解码得到序列Sout=B0,B1,…,Bm，比较Sin和Sout。改变网络拓扑、网络规模|S|以及输入序列Sin的长度，检测算法在不同场景下的表现。

4.2 结果分析

为验证本文方法的正确性和有效性，以网络中的拓扑变化事件作为信息源进行测试，实验将从准确度、通信开销、存储开销、计算开销、收敛速率等方面进行评估。

1）准确度。如图6 所示，在节点数目较多的网络中，对于中短序列检测准确度接近于100%，长序列检测准确度下降。当序列长度一致时，节点数目越多的网络，检测度越高。对此现象可以解释为当节点数量增加时，群体的整体存储计算能力增强，同时对应的抗干扰能力也会增强，从而增加了信息恢复准确度。而在网络规模确定的情况下，准确度随着输入序列长度增加而降低。这是由于时空编码依赖于浮点数计算，而计算机二进制表达浮点数的精度有限，因此出现准确度下降问题。

图6 不同网络规模和本地编码大小下的准确率Fig.6 Accuracy under different network sizes and local code sizes

2）通信复杂度。在本文提出的算法中，每个节点只需和m个邻居节点通信，其通信复杂度为O(mn)，其中，m为节点平均的邻居个数，在最好情况下为m=1。在理论的最坏情况下，如在全连接的网络拓扑中，每个节点都和其他节点连接，最差通信复杂度为O(n2)，所以编码消息整体通信复杂度为O(n)。然而，本文是通过将本地编码搭载在Beacon消息上来完成邻居节点之间的通信的，所以不会产生额外的通信开销，从额外通信数据角度来看，本文的通信开销为常数级。实验中将通信次数C和通信数据包大小S的乘积来衡量通信开销CCostc，通信包含数据输入并存储在网络中的过程store，也包括数据从网络中取出来的过程query，总的开销表示为：CCostc=Cstore×Sstore+Cstore×Sstore。将时空编码方法和其他WSN 存储相关方法进行比较，包括基于分布式存储方式使用Double Rulings（DR）［34］方法来解决数据可用性问题方法、基于分布式存储使用纠删码系统RRNS 来提高数据安全性的方法［35］、基于本地存储的Directed-Diffusion（DD）方法［36］。不同序列长度和网络规模下通信开销如图7 所示。在图7（a）中，本文方法随着网络规模的增长呈线形增长，这是因为在输入序列数据较小的情况下，编码的开销不可忽略。而在输入比特序列增加的情况下，发现本文方法的通信开销逐渐逼近到了常数级别。理论上Directed-Diffusion 由于需要使用洪泛的方式获取数据，从而产生了较高的开销。RRNS 需要将数据切分成数据块，并额外生成校验数据块，增加了额外的通信次数和数据量。相比之下，本文的方法在通信开销方面有更好的表现。

图7 不同序列长度和网络规模下的通信开销Fig.7 Communication overhead under different sequence lengths and network scales

3）存储复杂度。本文方法中每个节点只需存储邻居节点发来的上轮编码，以及节点自身的编码，节点只需不断利用邻居节点的编码计算并更新自身编码即可。类似通信复杂度，节点的存储开销为O(m)，其中，m为节点的邻居节点个数，是一个常数，所以整体存储开销为O(1)。

如图8 所示，DR 方法需要将数据把副本复制到ReplicateCurve 上的节点，所以会产生大量存储。基于纠删码的方法需要额外存储校验数据，所以会产生少量冗余（这里纠删码冗余度为1.33）。从实验结果可以看出，本文方法相比其他方法有明显的优势。

图8 不同序列长度和网络规模下的存储开销Fig.8 Storage overhead under different sequence lengths and network scales

通过理论分析，本文编码计算过程的复杂度为O(m)，解码为O(n2)，对比其他算法具有较低的复杂度，算法的整体相关复杂度如表1 所示。

表1 通信、存储和计算复杂度 Table 1 Communication，storage，and calculation complexity

4）收敛速率。在Mesh 拓扑结构中，对网络中节点的平均收敛轮数进行测试，网络中节点的收敛轮数大致呈正态分布，这从实验的角度进一步验证了本文算法的收敛性。实验结果如图9 所示，网络中的大部分节点都能在有限时间内完成收敛计算，能够在一定程度上应对实时性的要求。

图9 收敛轮数及频率Fig.9 Convergence rounds and frequency

5 结束语

为了解决无线传感器网络中的及时持续收集全局信息、巨大的网络通信量与较高的时延之间的问题，本文借助网络状态信息和计算空间时空结构之间的数学关联，提出在存储、通信、计算上常数开销的时空编码算法，实现对拓扑变化信息的计算感知，解决通过洪泛手段收集全局信息带来的通信开销问题。实验结果表明，该方法具有良好特性。后续将研究在节能、通信受限、存储有限等场景下的优化问题，提高时空编码方法的实用性。