《Algorithms》：A Distributed Virtual Machine for Mesh-Grid Sensor Networks Supporting In-Sensor Data Processing and Distributed Machine Learning with Strictly Resource-Constrained Microcontrollers
高效分布式计算仍然是一项重大挑战，尤其是在由极低资源嵌入式系统组成的网络中，例如部署在传感器网络中的微型微控制器。本研究首先探讨了与通信中心系统紧密集成的、事件驱动且支持实时处理的低资源虚拟机（VM）的设计与实现，其次探讨了网格局网络中的消息传递与路由问题。该分布式虚拟机网络在此形成了一台大型虚拟计算机，在每个节点上通常执行相同的程序，但处理不同的数据并具有不同的控制状态。该虚拟机提供集成式程序代码编译器和优化的字节码（Bytecode）处理器。虚拟机的编程语言支持基于通道的通信、多任务处理以及遵循通信顺序进程（CSP）模型的事件驱动（异步）数据处理。该虚拟机可部署在仅具有数kB RAM和ROM的微控制器中。本研究的主要部分致力于网络消息传递（同样由虚拟机支持）以及在二维网格局网络中的路由问题，其中每个节点具有可变数量的通信端口（连接度k），并特别考虑了技术上相关但特殊的k=3情况，该情况引入了消息路由方面的挑战，本研究对此进行了解决。本研究展示了该虚拟机方法在分布式传感器网络中进行分布式机器学习和聚类的性能与适用性，且仅使用本地传感器数据。
## 研究背景与问题
随着传感器网络节点密度的增加，传感器网络范式正朝着将数据处理与传感器紧密耦合的方向转变，即实现传感器内处理（in-sensor processing）和传感器间直接通信。传感器网络可无线或有线通信，工业环境中主要采用基于以太网技术的有线网络和基于工业WLAN的无线通信。传感器网络在理论上可视为具备与相邻节点通信能力的分布式计算节点图。二维网格局是主要的网络图拓扑结构之一。
单个传感器及组合传感器网络的运行稳定性可能受到环境因素（如电源、电磁干扰、户外条件等）、其他外部设备、硬件噪声、不当测量技术和网络攻击的影响，这些因素可能导致数据不一致和严重通信问题。分布式算法（如Kenyeres等人探讨的传感器读数正确性分布式共识算法）需要合适且高效的通信架构和通信协议。若假设所有节点具有不同的异步时钟，则通信协议应提供低延迟、低抖动，并可选择辅助硬件信号用于网络时钟同步。
除数据处理系统的操作表达能力外，传感器可编程性也是必需的要求，无论是二进制编码程序（原生机器指令或抽象指令）还是文本编程语言层面。传感器网络架构和通信系统必须能够扩展到数千个交互节点，且数据处理、通信和协议需一并考虑。传感器网络可能是异构的，即存在不同的硬件架构、内存和能量资源以及外设。即使在同构网络中，也需要针对数据处理和通信的硬件层抽象，包括编译器。
虚拟机架构通常部署在功能强大的计算机上。而传感器节点，特别是关于材料集成传感器网络，通常配备极低资源的嵌入式系统和微控制器。分布式传感器网络通常在资源受限条件下运行，尤其涉及能量约束。若存在能量约束，则传感器的计算能力也将受到严格限制。在此类低资源系统上实现虚拟机是一项挑战。例如，基于Google V8的node.js平台启动时需要超过10 MB RAM和20 MB ROM代码存储，这对任何微小微控制器均不适用。Hong等人提出的TinyVM及其应用特定的虚拟机合成与代码压缩，报告的资源消耗仍高于本研究 addressing 的水平。
虚拟机可分为以寄存器为中心和以栈为中心的处理器，如?imek等人讨论和比较的那样，但其重点在于即时编译（JIT），本研究因资源原因未涉及此问题。基于栈的机器提供了程序代码编译的高级简化，如REXA-VM所证明的，可绕过寄存器分配阶段。Marques等人在TinyOS之上展示了无线传感器网络中32位基于寄存器的虚拟机部署。大多数现代虚拟机为混合架构。确定资源的下限（RAM、ROM）始终困难。Levis等人介绍了TinyOS之上的Mate虚拟机，报告了在极低资源微控制器（通常为8-128 kB RAM）上的部署，展示了在1 kB RAM和16 kB ROM约束下的虚拟机实现。Mate的部分概念（如事件驱动和通信中心编程）影响了本研究引入的PLX虚拟机架构，但重点在于网格计算，这是其他虚拟机在一级层面不支持的。
然而，所有这些虚拟机均未同时提供事件驱动处理、多任务和同步能力以及面向网格局网络的广泛网络支持——如进行分布式结构健康监测（SHM）的传感器网络所需。Mate等简单虚拟机仅提供通用或低级通信功能，路由能力有限。PLX虚拟机提供具有高度表达能力的基于通道的通信操作和高级消息路由，紧密适配于传感器网络中基于网格的分布式计算。虚拟机架构按是否集成源代码编译器可分为整体式和非整体式系统，即提供文本或二进制代码接口。二进制虚拟机在异构系统中难以处理，例如网络中存在多个ISA版本时。因此，需要使用容错源代码文本接口对虚拟机进行编程。大多数相关工作针对无线传感器网络，而有线网络在特定传感应用中是必需的，如材料集成传感器网络，其中无线（无线电或光基）通信不可行。此外，有线通信还可提供电力传输，并最终支持高级分布式计算，如使用细胞自动机（CA）范式。
机器学习（ML）用于从数据中预测系统特征，通常分为参数化模型和算法，用于模型预测和训练。分布式传感器网络应最优地在本地处理传感器数据，包括机器学习。分布式计算需要节点之间先进、高效且可靠的通信，如Seng等人针对物联网（IoT）中分布式ML所讨论的，通信层是应用层和传感层之间的中间件，对节点间数据交换至关重要。分布式聚类作为空间数据融合的常用方法，也需要高效通信，如Taherkordi等人所讨论的。
分布式传感器网络（DSN）本质上是k个连接节点N的集合，由l条边E连接。边主要提供通信链路，可以是单向、双向或成对单向的。通信提供数据传输以及节点间同步。对于SHM和GUW（引导超声波）测量，每个节点的计算能力以及节点间或沿网络路径的通信延迟设定了操作约束，并影响测量方法的精度或准确度，最终影响预测模型的精度。可选地，边缘节点还可用于通过网络中现有通信线为网络提供能源，无论是永久性还是暂时性的。
本研究针对具有极低资源节点的分布式传感器网络，节点数量可从仅两个节点到超过100个节点，但无理论上界。为所有节点单独编程并不合适，因此所有节点应配备可编程虚拟机。先前工作中提出并评估了面向极低资源嵌入式系统的简单FORTH栈处理器虚拟机REXA-VM，该虚拟机能够以高速执行程序，并展示了处理机器学习算法的能力。REXA-VM的新颖之处之一是将数据（通常驻留在堆内存段中）嵌入（用户）程序代码中，因此不需要堆内存。然而，REXA-VM并非为可扩展和互联的分布式系统设计；FORTH程序代码难以维护（基于RPL栈处理表示法），且该虚拟机无法在4-8 kB RAM的微控制器上运行，这是本研究要解决的核心问题。此外，集成式文本到字节码编译器无法增量运行，编译程序会阻塞宿主应用程序的主IO循环。
为支持具有极低资源约束的嵌入式系统、自由文本界面编程、分布式通信计算以及网格局网络通信，本研究引入"编程语言扩展"（Programming Language Extended）PLX虚拟机平台。PLX处理器以事件驱动方式运行，支持多任务处理和简单的基于通道的通信。它基本上是一种混合内存-栈处理器，具有简化的堆内存管理。该虚拟机运行时通过二进制字节码指令处理（基本上是一个基于栈的处理器）。尽管编译器集成在虚拟机中，虚拟机运行时循环可独立使用，需要为堆（变量）设置初始化指令。编译器将令牌流转换为字节码指令流。编译器可直接在通信缓冲区和虚拟机的代码段上操作，以避免文本和代码的复制。每个虚拟机由一组上下文环境组成——每个环境具有虚拟机寄存器集以及数据和帧（控制）栈，共享一个内存（代码和堆）和事件处理器表。
PLX-VM编程语言的核心是基于通信顺序进程（CSP）模型的过程模型，支持多任务以及原始的基于通道的输入和输出操作（!和?）。存在标量、字符串和数组变量，但无记录结构。只有一种数据数字类型（通常是固定位数的整数，如16位，但不限于此类型）。支持函数和过程、变量和常量（由编译器直接求值）。表达式通过数据栈由栈处理器处理，控制语句（如循环）使用专用控制栈。
针对分布式传感器数据处理和与极低资源微控制器的高度集成，通信网络的主要操作特性是代码和数据分发。但传感器数据应在每个节点上独立本地处理，仅处理后的输出数据通过网络传播。根据Flynn计算机分类，所有节点执行相同操作，需要单指令多数据流处理器，或更精确地，单程序多数据流（SPMD）处理器。通信网络和协议必须反映此处理架构。
对于二维传感器网格，需要二维串行链路通信网络，通常每个节点有四个或八个串行链路，方向由冯·诺依曼邻域或摩尔邻域连接度定义。然而，大多数微控制器，尤其是引脚数少、封装小的微控制器，仅提供2-3个双向串行通信链路。这一约束需要专用的互连和路由策略，特别是上文讨论的奇数三链路配置。
本研究假设节点以二维网格局网络（或作为特殊情况的一维）排列，存在一个连接到外部计算机的专用外围节点，称为网关节点。通过此连接交换程序代码和数据。支持三种路由策略以在此类网络中执行分布式传感和分布式计算：下行路由（从根节点向所有其他网络节点分发程序代码）、上行路由（数据处理结果传至根节点）和Delta路由（短程邻居节点数据交换，如用于数据聚类）。
网络初始化通过低级别二进制引导协议（Boot-X协议）完成，使用简化的[跳数|行索引]算法，每个节点仅向邻居节点发送一条消息，显著降低总体通信复杂度。
本研究引入了一种分层双模式网络协议栈，可在极低资源嵌入式设备上实现：低级别Boot-X调制解调器协议（模式0）用于网络初始化和编程（二进制代码）；高级别网格局通信协议（模式1）用于编程（PLX VM代码）、消息传递、事件信号和路由。
## 关键技术方法
研究人员为开展本研究采用了以下主要技术方法：虚拟机设计与实现方面，开发了PLX虚拟机——一种事件驱动、支持多任务的混合内存-双栈处理器虚拟机，集成流式编译器和字节码处理器；网络通信协议方面，设计了分层双模式协议栈，包括低级别Boot-X协议和高级别网格局通信协议，支持五种路由策略（下行、上行、Delta、范围和扫描线路由）；网络初始化与自配置方面，提出了基于最小跳数和行奇偶校验比特的自动网络配置算法，使节点无需知晓自身绝对位置即可确定端口方向；流控制机制方面，对比了硬件信号流控制（双向0-H逻辑总线信号）和软件消息流控制两种方案；分布式同步机制方面，设计了两种硬件信号协议实现分布式屏障同步和事件同步；TinyML扩展方面，通过C-API扩展提供向量运算库以支持人工神经网络和卷积神经网络；评估验证方面，采用抽象网络模拟器（精确协议栈实现，基于蒙特卡洛的简化节点处理）、UNIX替身实现（未在本研究中使用）和真实嵌入式网络三种实现层级进行性能评估。
## 研究结果
**虚拟机架构与编程接口**：PLX虚拟机采用C语言编写，代码少于8000行（含网络模块），嵌入式实现需要约32 kB ROM（简化net0模块仅支持一个通信端口时）和至少8 kB RAM。虚拟机支持三种实现环境：微控制器嵌入式实现（使用硬件串行通信端口UART和硬件总线信号）、桌面实现（使用命名FIFO设备和共享内存）和模拟器（使用虚拟电路和共享内存）。虚拟机处理器性能为15,625 VM指令/(s·MHz)，编译器速度为1500文本令牌/(s·MHz)，源代码令牌与VM操作比例接近1:1，源代码大小与VM代码大小比例约为1:2（字节）。VM启动时间低于100 μs，硬件信号处理和转发延迟约3 μs/node（STM32, 64 MHz），信号到事件处理器延迟约10 μs。
**网格局网络通信**：对于节点连接度K=3的特殊情况，研究人员提出了交替上下行连接策略，并开发了自动网络初始化算法。算法A（初始方法）的通信复杂度约为二次方增长，约1/2 N
2条消息；改进的算法B将通信复杂度降低至线性，每个通信端口仅发送一条消息。对于N=100节点的网络，完整网络初始化仅需4毫秒（忽略数据处理时间）。消息协议支持八种消息类型：网络控制消息（MSGNET）、完整程序消息（MSGPROGRAM）、部分程序消息（MSGPROGRAMPART）、命令消息（MSGCOMMAND）、上行数据消息（MSGDATA1）、下行数据消息（MSGDATA2）、用户消息（MSGUSER）和事件消息（MSGEVENT）。路由策略包括存储转发（SF）和虫洞（WH）两种数据存储策略，以及下行、上行、Delta、范围和扫描线五种路由方法。
**流控制与死锁分析**：硬件流控制使用单条双向0-H逻辑总线信号，但会引发路由死锁，概率几乎与网络规模无关，大网络约10-20%，小网络约20-40%。软件流控制通过消息注入实现，消除了路由死锁。范围路由中，边缘节点主要受通道阻塞影响，简化总线信号方法显示高且长时间的路由器和接收器阻塞，而软件方法仅显示短阻塞。
**网络初始化性能**：模拟结果显示，消息复制使K>2时的网络填充速度提高约6倍，K=3和K=4情况无显著差异。范围消息路由在K=3时略有位置依赖性，K=4时独立于位置，K=2时依赖于网络规模。
**分布式聚类验证**：在10×10传感器网络、K=3连接度的实验场景中，研究人员验证了分布式聚类方法。每个传感器采样时变传感器信号，本地处理后将相关特征传递给简单的K近邻（KNN）分类器。通过分布式聚类，假阳性标记减少90%，同时不降低真实损伤相关真阳性的检测，这些标记最终用于确定损伤的近似位置（使用网络坐标）。聚类参数为a=3, b=5, r=1, eps=1, epochs=2。所有节点发送的消息总数约1200条，每条50字节，总数据量60 kB，对于分布式聚类算法处理而言较低。
## 讨论与结论
研究人员提出了一种低资源PLX虚拟机，提供多任务处理、基于事件的数据处理、带集成流式编译器的文本编程功能，面向有线网格局网络中排列和连接的极低资源嵌入式系统，这是材料集成或表面附着传感和测量系统的典型配置。研究讨论并评估了二维空间网格局网络中奇数节点连接度k=3的通信，这在技术上具有相关性，因为许多适用于材料集成或表面附着传感器网络的微控制器仅提供三个串行通信设备。
虚拟机本身用可移植C语言编写，代码少于8000行，在ARM Cortex M系列处理器上使用32-64 kB ROM和不到12 kB RAM。整个VM可部署在使用串行UART通信端口的裸机微控制器上，或部署在使用命名FIFO链接和共享内存的POSIX类系统上，从而模拟硬件信号。
虚拟机由流式词法分析器、编译器（直接生成二进制VM字节码指令的解析器）和VM字节码处理器组成。VM是混合内存和双栈处理器，支持异步事件处理。VM可通过简单的C API进行扩展，添加函数和常量，本研究中广泛用于添加提供向量运算的TinyML层。
VM与网络模块紧密耦合，提供不同的消息类和路由模式，用于传感器网络中的高效分布式计算，所有节点处理相同的程序。软件网络消息与硬件信号的组合，使得针对极低资源嵌入式系统的分布式传感和信号处理应用的设计和高效执行变得简单。使用双向信号（双方驱动的0H逻辑）的硬件流控制会导致死锁和因路由超时丢弃的消息。单线硬件流控制中的死锁概率几乎与网络规模无关，大网络通常为10-20%，小网络为20-40%。使用软件流控制消除了路由死锁。
网络节点不知道其在网络中的位置。使用低级引导协议确定通信端口方向和每个节点在网络中的相对位置。最小跳数协议具有相对于节点数量的线性通信复杂度，即使带宽低、节点数量多，整个网络初始化时间也很短，例如N=100个节点仅需4毫秒（忽略数据处理时间）。
通信协议由控制和数据消息组成。网络控制消息可用作其他数据消息的前缀，以确定消息在网络中的路由和复制。全局分布式状态融合通过使用范围路由和数据写入消息的非常简单的邻域聚类算法实现，可有效降低噪声，即应用于局部传感器数据的机器学习模型的空间散射假阳性和假阴性预测。
如果无法建立从不同输入端口到不同输出端口的路由，且路由流控制通知发送节点停止发送（这可进一步传播到其他节点），则通信系统中可能出现死锁。这种情况仅发生在环形路由情况中，如多个节点并行范围路由时。路由超时自动释放死锁，在使用软件流控制的实验中未发生死锁。如果使用了稳定的分布式算法（如本研究所示的分布式聚类），一个节点的故障可由其他节点补偿，因为这是一种基于区间的算法。路由可以依赖路径冗余（对于K>2），如果一个节点故障，从全局系统角度来看不会失败。
