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

第 49卷 第 9期2023年 9月Computer Engineering 计算机工程基于超越数论的无线传感器网络时空编码方法胡宗升1，邢凯1，2，许静1（1.中国科学技术大学 计算机科学与技术学院，合肥 230026；2.中国科学技术大学 苏州高等研究院，江苏 苏州 215123）摘要：在无线传感器网络(WSN)规模逐渐增大与传感器逐渐微型化的背景下，全局信息收集的持续性和实时性的要求与无线传感节点受限能力之间的矛盾日益严峻。传统方法使用压缩、融合、聚合等方式降低数据传输量，并通过优化路由增加网络能力，但越来越难以应对上述挑战。为此，考虑利用计算能力克服存储、传输瓶颈，通过本地化计算范式实现全局信息的感知，并基于超越数论和非定域感知方法，提出一种面向大规模分布式 WSN 的信息存算与通信一体化方法。通过对网络进行建模，将网络每时每刻产生的信息以去中心化本地计算的方式融合到常数量级的可计算编码中。该方法通过节点邻居之间周期性地交换搭载时空编码的 Beacon 消息。根据时空编码在相空间中构造具有确定性和因果性的相空间轨迹来存储和交换信息，避免直接存储和传输庞大的原始数据，从而降低计算、通信、存储等开销。实验结果表明，该方法能够实现 O(1)的存储和通信开销，具有毫秒级的收敛速率，相较现有 WSN存储方法，在通信开销方面具有明显优势。关键词：无线传感器网络；事件感知；低延迟；高可用；分布式去中心化开放科学（资源服务）标志码（OSID）：源代码链接：https：/ J.计算机工程，2023，49（9）：172-182.英文引用格式：HU Z S，XING K，XU J.Spatio-temporal coding method for wireless sensor networks based on transcendence number theory J.Computer Engineering，2023，49（9）：172-182.Spatio-Temporal Coding Method for Wireless Sensor Networks Based on Transcendence Number TheoryHU Zongsheng1，XING Kai1，2，XU Jing1（1.School of Computer Science and Technology，University of Science and Technology of China，Hefei 230026，China；2.Suzhou Institute for Advanced Research，University of Science and Technology of China，Suzhou 215123，Jiangsu，China）【Abstract】In recent years，the scale of Wireless Sensor Network（WSN）has expanded，with sensors trending toward miniaturization.This expansion has intensified the tension between the need for continuous，real-time global information collection and the limited capabilities of wireless sensor nodes.Historical strategies，such as data compression，fusion，and aggregation，have been used to reduce data transmission volume and enhance network capacity through optimized routing.However，addressing emerging demands with these techniques is increasingly challenging.This study explores the utilization of computational power to overcome storage and transmission bottlenecks and proposes that global information perception can be achieved via localized computing paradigms.Drawing inspiration from transcendence number theory and non-local sensing methodologies，this study introduces a comprehensive approach to information storage and communication tailored for expansive distributed wireless sensor networks.The proposed strategy capitalizes on the periodic exchange of Beacon messages enriched with spatiotemporal encoding between neighboring nodes.By crafting deterministic and causal trajectories in phase space via spatiotemporal coding，information is encapsulated and relayed without the direct storage or transmission of extensive raw data，significantly reducing computational，communication，and storage costs.Experimental findings validate that the proposed method realizes a storage and communication overhead of O（1），converging rapidly within milliseconds，this approach offer significant advantages over existing WSN storage-centric techniques.【Key words】Wireless Sensor Network（WSN）；event awareness；low latency；high availability；distributed decentralizationDOI：10.19678/j.issn.1000-3428.0067183基金项目：国家自然科学基金（61332004）。作者简介：胡宗升（1998），男，硕士研究生，主研方向为无线传感器网络；邢 凯，副教授、博士；许 静，博士。收稿日期：2023-03-16 修回日期：2023-05-07 Email：移动互联与通信技术文章编号：1000-3428（2023）09-0172-11 文献标志码：A 中图分类号：TP212第 49卷 第 9期胡宗升，邢凯，许静：基于超越数论的无线传感器网络时空编码方法0概述 无线传感器网络（Wireless Sensor Network，WSN）一般由一系列能够感知周围环境，使用无线信道进行通信的传感器节点组成，是一种能够进行感知、处理、存储和传输感知区域信息的分布式自组织网络，其在国防军事、防灾预警、气候监测、交通运输、环境与农业等领域具有广泛的应用。在这些领域中，存在大量应用需要 WSN 能够快速、持续地收集全局信息，并及时做出决策和调度。因此，信息的收集汇聚是无线传感器网络的主要任务之一。但是，在数据多跳汇聚过程中，中继节点的存储转发产生了大量的通信、存储和能量开销。而无线传感节点只有有限的通信带宽、存储容量以及能量。在大规模分布式环境下，传统方法难以调和其信息通信、存储、能量约束与全局信息收集的持续性和及时性要求之间的冲突。为解决这一挑战，研究人员针对大规模分布式无线传感器网络在信息收集汇聚方面的传输和能耗问题进行了大量研究1-3。在信息收集汇聚任务中，无线传感器网络一般通过网络的各个节点将其所感知信息经由中间节点多跳传输汇总到基站。这种方式的缺点主要是：依赖中间节点的路由中继，如果中间节点故障，则会导致某些节点信息无法到达 Sink 节点，继而无法到达基站，因此需要常态化地、持续地监控并维护网络，开销巨大；受限于单点失效问题，一旦汇聚节点失效，就意味着网络可用性降低甚至不可用，对汇聚节点选取要求高；通信和能耗问题，节点离基站越近，通过该节点的信息越密集，中继通信负载越大，能耗也越高，会带来较严重的负载均衡问题，当基站附近的节点在耗尽能量、通信带宽和存储空间后，会导致可用性问题。针对无线传感器网络在信息汇聚任务中的汇聚节点失效和中继路由可靠性问题，当前研究往往采用骨干拓扑的方式，利用簇（如 LEACH4-5算法）或者树的方式（如 LPT6算法）汇集数据，例如网络根据拓扑位置或能量等特性将网络划分为多个簇，或通过分布式汇聚算法形成树状等骨干拓扑，节点收集信息后发送给骨干拓扑节点并通过骨干网汇集信息。这种方式不依赖于中心节点，传感器节点只需和附近邻居节点通信，以自组织骨干网通过多跳的方式协作进行信息传输。相应地，节点也需要更多通信开销来完成骨干网拓扑维护、时间同步、节点选举等工作，从而导致较高的网络延迟和维护开销，因此对于全局信息收集有实时性要求的场景，例如防灾预警、入侵检测等难以提供有效保障，同时每个节点都有持续的通信和维护开销，进一步挤压了节点的通信和续航能力。然而，随着对掌握全局信息需求的提高，传统的信息汇聚方法不可避免地带来全网范围的信息收集和大量的中继存储转发开销，这些通信和存储所带来的能耗、带宽及存储开销巨大。因此，如何降低网络中的传输/存储开销一直是大规模分布式无线传感器网络信息收集与汇聚研究中的重点方向。针对无线传感器网络在信息汇聚任务中的海量信息传输/存储开销问题，一个直观的做法是将数据进行编码/压缩之后再进行传输和存储。如面向多播传输的网络编码方法7-9，基于图论中最大流最小割原理保证了多播网络在确定性路径下可以达到网络最大信息流，直观上减少了网络传输次数，然而该方法在信息汇聚和单播网络通信应用中因拓扑/路由 的 不 确 定 性 而 难 以 被 广 泛 应 用。压 缩 感 知 10（Compressor Sensing，CS）方法突破了传统奈奎斯特采样定理。不同于传统的压缩方法是先采样再压缩，压缩感知则是采样与压缩同时进行，且解码算法独立于压缩算法，因此尤其适合资源受限的传感器网络，压缩和恢复算法的独立意味着能够根据传输路径的变化而灵活地进行感知和数据重建。但是，压缩感知是有损压缩，其精度依赖于感知数据分布，当数据分布变化时稳定性欠佳，在信噪比较低和分布波动大时尤其如此。不难看出，信息收集汇聚过程中的信息压缩效率和相关算法的通用性始终是该研究领域的重要挑战。从以上研究进展可以看出，以计算开销来降低/部分替代通信和存储带来的开销，是资源受限的大规模分布式无线传感器网络的信息通信、存储和能量约束与全局信息收集的持续性和及时性要求之间矛盾的一个重要趋势变化，也是当前大规模分布式无线传感器网络研究的重点，即存算通信一体化研究。针对大规模分布式无线传感器网络中以存储转发方式为主的传统信息收集汇聚方式，本文提出一种以计算方式降低/部分替代通信和存储开销的存算通信一体化新方法，并给出相关理论分析和论证。1相关工作 对信息的收集和汇聚是信息系统持续优化和决策的前提条件，其中网络拓扑的感知与维护在信息汇聚过程中不可缺少。拓扑感知（Topology Sensing）是分布式网络感知和维护拓扑信息的重要方法。Topology Sensing可以分为 In-network和 Out-network两类。早期的拓扑感知的工作主要集中在网络感知方面，并通过交1732023年 9月 15日Computer Engineering 计算机工程换路由信息来实现。例如使用 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树 算 法 的 递 归 矩 形 分 区 算 法 来 提 升 性 能。PEGASIS24不同于 LEACH 以簇来划分，PEGASIS使用链划分。节点在收到数据后传递给后续节点，直到最终传递到 Sink 节点。PEGASIS 依赖于节点对全局知识的掌握，节点使用贪心算法选取下一个最邻近节点作为后续节点。文献 25 提出一种自适应数据聚合方案，该方案依赖于节点能量值的上下限，如果低于较低阈值则会进入休眠状态。文献 26考虑了由能量问题带来的延迟，提出能量碰撞的概念，即当两个节点计划进行传输时，由于其中一个节点最近的一次活动使得本次没有足够能量进行收发，导致此次传输无法进行。上述协议能够提高网络的负载均衡性，但是信息感知的延迟通常较大。由于对信息是透明的，因此无法解决大规模网络下庞大原始数据的传输带来的通信问题。为了实现持续及时地收集网络全局信息的目标，减少网络延迟，降低网络传输次数和通信量是其中的重点。在分布式系统中，随着对把握全局信息的需求的提高，必然会出现全网信息收集和大量的洪泛开销。为解决其中产生的数据传输和存储开销问题，一个直观的做法是将数据进行压缩，之后再进行传输和存储。目前通用的压缩算法可以分为有损数据压缩算法和无损数据压缩算法。前者可以无损恢复压缩前的数据，原理是根据数据冗余特性，引入信息墒理论计算的编码极限，缺点是压缩效果不明显，对算力有一定要求，成本较高。有损数据压缩算法针对的大多是多媒体数据，压缩后 重 建 的 数 据 质 量 有 所 损 失，如 图 像 压 缩 算 法JPEG、视频压缩算法 H.261、音频压缩 MP3 和语音压缩 G.711。当分布式系统产生的数据具有一些特性时，往往可以采用一些特殊算法，这方面相关的研究有基于数据时空冗余性的压缩算法。基于时空冗余性的压缩算法利用了单个节点所采集的数据在时间上的冗余、邻居节点采集的数据之间的空间冗余性以及单个节点在关联属性之间的冗余。这类算法采用预测估计技术将实测值和预估值进行差分运算以消除冗余。由于节点运算和存储资174第 49卷 第 9期胡宗升，邢凯，许静：基于超越数论的无线传感器网络时空编码方法源受限，通常使用低阶编码进行预测，因此只适用于低精度事件检测场景。也有研究使用高阶多项式最小二乘曲线拟合将采集的数据在网管进行解码。这些算法时间复杂度高，计算量大。基于奇异值分解以及离散傅里叶变换的技术在这种场景下压缩能力强，但是普遍计算量偏大。基于压缩感知算法是根据陶哲轩等人提出的压缩方法，其突破了传统奈奎斯特采样定理。压缩感知相较于其他压缩算法，不同点在于：信号是稀疏的，数据的压缩和采样是同步的，压缩算法和解码算法之间较独立。压缩感知需要的信号是稀疏的，这在大规模网络中，尤其是传感器网络中非常符合。传统的压缩方法是先采样再压缩，而压缩感知同时进行则加快了感知的速度。在资源受限的传感器网络中，压缩和恢复算法的独立意味着能够根据情况灵活设计。文献 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(VE)，一个由节点Vi和链接E组成的无向图结构，网络中节点的个数使用N或者|G(VE)|来表示。无线传感器网络模型如图 1所示。WSN 使用消息来实现松散时钟同步，在初始时刻t0系统会完成初始化工作，节点通过与邻居的消息来同步推进本地时钟。在初始化阶段，节点会被赋予一个唯一的初始混沌编码x0i，以及一个素数生成规则函数i(t)。函数i(t)用来生产辅助运算数组Ai=a0ia1iati，其中，ati=1qti，qti=i(t)。素数生成函数可以按照某个特定规则产生，例如顺序取第(i+nt)个 素 数 作 为 第 i 个 节 点 的 第 t 轮 时 钟 的 素数，即：i()t=primeListi+n t（1）2.1.2节点模型在本文的设计中，节点需要像神经元一样能够对外界事件做出响应，根据响应计算并更新本地编码。而出于节能的考虑，节点应该在完成计算时进入休眠，所以节点应该处在动态的变化中。为此，为网络和节点设计以下 4种状态：1）局部收敛态：当前时钟轮和上一时钟轮的编码值差值小于阈值，即|xt+1i-xti|1，|Nti|Nt-1i（2）若满足条件则进入局部扰动态，继续执行步骤2，否则跳出，并在下轮进行检测。2）编码规范化处理：将尖峰信号处理取倒数，其他编码不变。ti=xt-1j 1？1xt-1j：xt-1j（3）3）计算邻域几何均值：根据上一步统一规范化处理后的编码计算其几何均值。ti=()j Nitjati（4）4）生成信号尖峰：取倒数的尖峰信号。xti=1ti（5）5）完 成 扰 动：推 出 扰 动 计 算，进 入 收 敛 计 算过程。通过扰动计算，节点将事件产生的扰动信息以类 Gossip 方式传播到全网络中，从而让所有的节点都能感知到该扰动，这种机制保证了本文算法 4 个特性中的传播性。系统完成一次扰动计算之后马上就进入到收敛计算，在收敛计算过程中，节点不会再次进行扰动计算，这可以避免网络中出现同一个事件消息多次被识别为扰动源。2.2.2收敛模块当结束扰动计算后，收敛计算将会持续多轮直到本地节点进入到局部收敛态。如果将扰动计算过程视作扰动产生的全局信息的传输过程，那么收敛计算则可以看作对该信息的存储过程。收敛计算的具体步骤如下：1）编码规范化处理：计算邻域几何均值，过程同扰动模块。2）编码更新：如果编码的差值小于阈值，则进入到局部收敛状态，编码无须更新，否则更新编码。xti=()|xti-xt-1i n2，那么：|t+1k=|1qt+1ij Nitktkn tmaxqt+1i tmax（10）式（10）说明，节点在执行收敛模块算法过程中，节点的编码值不断递减。而收敛模块中当节点的编码值小于阈值时，编码将保持不变，多轮之后节点进入本地收敛态。上述过程说明，节点在多轮时钟之后将进入本地收敛态，当所有节点都进入本地收敛态后，全网状态则进入全局收敛态。3）因果性定义：给定一个连通网络G(VE)，在相同的初始化配置和相同输入的情况下，时空编码的算法过程将产生相同的编码序列。而在初始化配置不同和（或）输入不同的情况下，算法过程将产生不同的编码序列，即以下 3种情况：（1）相同初始条件，不同的拓扑事件原因将产生不同结果；（2）不同初始条件，相同的拓扑事件原因将产生不同结果；（3）不同初始条件，不同的拓扑事件原因产生不同结果。定理 2 对于一个连通网络G(VE)，在某个时刻下，全局的拓扑连接矩阵表示为 C，全局编码集合表示为X。在经过一次拓扑事件后，全局拓扑连接改变为C1，对于任意两个网络中的节点Vi、Vji j，必然有xt1i xt2j。定理 3 对于一个连通网络G(VE)，在某时刻下，全局的拓扑连接矩阵表示为 C，全局编码集合表示为X。当经过两次拓扑事件后，全局拓扑发生改变：C C1C1 C2（11）由此造成的全局网络中各个节点的本地编码均不相同，有：xt1i|C1 xt2jC2（12）其中：Vi、Vj为网络中的节点，且允许i=j的情况，这种情况即相同节点在不同的拓扑结构下编码是不同的。证明：由以上两个引理可以推出在相同初始配置和相同输入情况下编码序列相同。而不满足任意一个条件都将使得编码序列不同，有：（1）相同初始条件，不同的事件序列导致不同的全局编码序列；（2）不同初始条件，相同的事件序列有不同全局编码序列；（3）不同初始条件和不同时间序列有不同全局编码序列，即事件原因和结果一一对应。4）确定性定义：在相同的网络初始化条件下，给定系统相同的输入，时空编码算法过程总是到达相同的网络状态，产生一致的输出结果。证明：由时空编码算法的数学过程可知，涉及编码计算的函数均为单射的确定性函数。因此，给定相同的初始条件，保证节点能正确执行编码算法的情况下，时空编码运行的整个过程是确定的，不会有1772023年 9月 15日Computer Engineering 计算机工程随机因素参与并改变执行的结果。其演化过程在相空间中表现为固定的轨迹。3基于超越数论时空编码的无线传感器网络信息存算通信一体化方法 3.1基于无线传感器网络模型的编码方法本节提出基于非定域感知理论的时空编码方法，将非定域感知理论的拓扑感知场景扩展到普遍的信息感知场景下，并给出数据收集与感知的具体编码过程。在网络处于全局收敛的状态下，节点或者边的增加或者删除会生成一个尖峰信号，尖峰信号将会被记录在节点的本地编码中，最终被全网所有节点感知到。这种蝴蝶效应的结果将会被反映到网络所有的节点的本地编码xti=pt+111pt+122，pt+1nn中。节 点 将 本 地 编 码 运 行 分 解 算 法 得 到 传 播 路 径ati，at-1j，at-2k，at1z，从可以定位得到扰动源节点，实现非定域感知。如果将扰动源节点固定为两个节点，并将其映射为 0 和 1，那么可以将普遍的信息映射到每个节点的本地编码中，编码过程如图 4所示。如算法 1所示，将一系列事件信息以 0-1序列形式注入到网络中，经过节点反复的收敛和传播计算，这些信息将会被编码存储在网络所有节点中。算法 1 基于非定域感知理论的混沌编码过程输入 待输入的 0-1比特序列 BitSequence；输入源节点Node0，Node1；网络中所有的节点集合 N输出 网络每个节点的编码序列1.For BitSequence 中的每个比特 do2.if 比特为 0 then3.扰动 Node04.end5.扰动 Node16.while未全局收敛 do7.for node in N do8.监测邻居节点是否活跃9.while未局部收敛 do10.接收邻居编码11.计算并更新本地编码12.发送本地编码至邻居节点13.end14.end15.end16.end3.2基于无线传感器网络模型的解码方法根据前文对非定域感知理论的讨论可知，本文算法具有因果性和确定性，在某个时间点下产生的事件将会唯一地被记录在网络中各个节点的本地编码中，并能够唯一地被解析恢复。基于前面的编码算法，本文提出一个基于编码序列的解码方案，解码过程如图 5所示。如算法 2所示，此方案利用基于扫描线的搜索算法定位引起上一次网络拓扑变化的源节点，通过多次定位事件源节点来解析出源事件序列。对于节点来说，只需在解码时执行此算法，在一般情况下只需要接受邻居编码并更新本地编码即可。通过这种策略，本文将通信和存储域上的开销转移到计算域上的开销，突破了节点存储和通信能力的限制，从而能达到持续地、实时地、非定域地感知信息。算法 2 非定域时空编码解码过程输入 已完成注入了 0-1序列的网络，处于全局收敛状态；了解全局初始配置知识的节点Vi，以及该节点本地编码xti；全局节点的初始参数及邻接表 Cnn，按照节点通信半径划分出区域 R=R1，R2，Rr输出 扰动事件序列 EventSequence1.EventSequence=for round in 0，1，t do2.for region ri R do3.for nodej S do4.for 处于节点Vi通信半径范围内的节点 k do5.Cn+1，k=Ck，n+2=16.end7.x0n+1=x0j，r=08.for节点Vi N do9.执行一个完整时钟轮10.end11.r+12.while 混沌编码没有收敛 do图 5解码过程Fig.5Decoding process图 4编码过程Fig.4Encoding process178第 49卷 第 9期胡宗升，邢凯，许静：基于超越数论的无线传感器网络时空编码方法13.if 当前编码序列和输入编码序列不一致 then14.break15.end16.for Vi N do17.执行一个完整时钟轮18.end19.r+20.end21.if r=T then22.append（EventSequence，nodej）23.end24.end25.end26.end4实验结果与分析 4.1实验设置实验使用 Ubuntu 18.04 LTS 版本为操作系统，CPU 为 i7-9750H，软 件 环 境 为 Java17.0.2，JVM 为HotSpotTM 64 bit Server VM。实验通过多线程模拟节点，使用线程的创建，销毁仿真节点的加入退出的行为。节点之间的通信使用 Socket 通信方式来完成，这一方案也有利于模拟实际通信过程中的丢包、重连等情况。另外，系统中的松散时钟部分使用了基于消息的同步机制来进行模拟。实验将网络分为编码输入节点、普通节点以及在普通节点中随机选取的节点作为解码节点。实验将编码固定输入节点表示为NODE0、NODE1，以拓扑变化事件信息源固定为编码输入节点的拓扑变化事件，将感知信息抽象为 0-1 序列，随机选择要输入的 0-1 序列信息Sin=b0b1bn，其长度为n=|Sin|，bi 01。输入完毕后网络处于全局收敛状态，此时随机选取节点NODEr作 为 解 码 节 点，运 行 算 法 2，解 码 得 到 序 列Sout=B0B1Bm，比较Sin和Sout。改变网络拓扑、网络规模|S|以及输入序列Sin的长度，检测算法在不同场景下的表现。4.2结果分析为验证本文方法的正确性和有效性，以网络中的拓扑变化事件作为信息源进行测试，实验将从准确度、通信开销、存储开销、计算开销、收敛速率等方面进行评估。1）准确度。如图 6 所示，在节点数目较多的网络中，对于中短序列检测准确度接近于 100%，长序列检测准确度下降。当序列长度一致时，节点数目越多的网络，检测度越高。对此现象可以解释为当节点数量增加时，群体的整体存储计算能力增强，同时对应的抗干扰能力也会增强，从而增加了信息恢复准确度。而在网络规模确定的情况下，准确度随着输入序列长度增加而降低。这是由于时空编码依赖于浮点数计算，而计算机二进制表达浮点数的精度有限，因此出现准确度下降问题。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 需要将数据切分成数据块，并额外生成校验数据块，增加了额外的通信次数和数据量。相比之下，本文的方法在通信开销方面有更好的表现。图 6不同网络规模和本地编码大小下的准确率Fig.6Accuracy under different network sizes and local code sizes1792023年 9月 15日Computer Engineering 计算机工程3）存储复杂度。本文方法中每个节点只需存储邻居节点发来的上轮编码，以及节点自身的编码，节点只需不断利用邻居节点的编码计算并更新自身编码 即 可。类 似 通 信 复 杂 度，节 点 的 存 储 开 销 为O(m)，其中，m为节点的邻居节点个数，是一个常数，所以整体存储开销为O(1)。如图 8 所示，DR 方法需要将数据把副本复制到ReplicateCurve上的节点，所以会产生大量存储。基于纠删码的方法需要额外存储校验数据，所以会产生少量冗余（这里纠删码冗余度为 1.33）。从实验结果可以看出，本文方法相比其他方法有明显的优势。图 8不同序列长度和网络规模下的存储开销Fig.8Storage overhead under different sequence lengths and network scales图 7不同序列长度和网络规模下的通信开销Fig.7Communication overhead under different sequence lengths and network scales180第 49卷 第 9期胡宗升，邢凯，许静：基于超越数论的无线传感器网络时空编码方法通过理论分析，本文编码计算过程的复杂度为O(m)，解码为O(n2)，对比其他算法具有较低的复杂度，算法的整体相关复杂度如表 1所示。4）收敛速率。在 Mesh 拓扑结构中，对网络中节点的平均收敛轮数进行测试，网络中节点的收敛轮数大致呈正态分布，这从实验的角度进一步验 证 了 本 文 算 法 的 收 敛 性。实 验 结 果 如 图 9 所示，网络中的大部分节点都能在有限时