分布式异构数据流监测与实时网络计算范式探索

### 分布式异构数据流监测与实时网络计算范式探索 #### 分布式异构数据流监测 在处理分布式异构数据流时，节点数量众多且每个节点有两个坐标，这使得问题的复杂度较高。为了缓解这个问题，我们可以采取以下步骤： 1. **节点的层次聚类**： - 首先，对节点进行自下而上的层次聚类。这需要定义节点之间的距离度量，由于节点由其数据向量表示，所以要定义欧几里得空间子集之间的距离。这里采用了一种方法，通过集合的矩向量（坐标为集合的低阶矩的向量）之间的 L2 距离来定义集合之间的距离。矩只需要在初始化阶段计算一次。 - 聚类树的叶子是单个节点，内部顶点可以看作“超级节点”，每个超级节点包含相应子树中节点数据的并集（闵可夫斯基平均）。因为集合并集的矩只是各个集合矩的总和，所以内部节点矩的计算非常快。 2. **安全区域的分配**： - 层次聚类完成后，自上而下分配安全区域。首先，在根节点的子节点的闵可夫斯基平均包含在集合 C 这个约束条件下，为根节点的子节点分配安全区域。 - 在下一层，在根节点的孙节点的闵可夫斯基平均包含在其父节点的安全区域这个约束条件下，为根节点的孙节点分配安全区域，依此类推。叶子节点要么是单个节点，要么是足够均匀的聚类，可以为它们分配形状相同的安全区域。 以下是这个过程的 mermaid 流程图： ```mermaid graph LR A[开始] --> B[节点层次聚类] B --> C[计算节点间距离（矩向量 L2 距离）] C --> D[构建聚类树（叶子为单个节点，内部为超级节点）] D --> E[计算内部节点矩（集合矩总和）] E --> F[完成层次聚类] F --> G[安全区域分配（自上而下）] G --> H[为根节点子节点分配（闵可夫斯基平均在 C 内）] H --> I[为根节点孙节点分配（闵可夫斯基平均在父节点安全区域内）] I --> J[处理叶子节点（单个节点或均匀聚类）] J --> K[结束] ``` #### 实验部分 我们实现了 HGM 方法，并将其与 GM 方法进行了比较。实验内容如下： 1. **数据、设置和监测函数**： - **数据**：数据来自“AirBase – 欧洲空气质量数据库”的空气污染物测量值，以微克每立方米为单位。节点对应不同地理位置的传感器，不同节点的数据在大小、形状和随时间的变化上差异很大。 - **监测函数**：选择监测函数是因为它们具有实际重要性，并且是非线性和非单调的，大多数现有方法无法处理。例如，监测 NO 与 NO₂ 的比率，这是空气质量分析中的重要指标；还监测了一个三元二次函数，二次函数在许多应用中都很重要。 - **安全区域族的选择**： - 对于比率查询，选择三角形安全区域，其结构与集合 C 相同，但大小和位置不同，且易于定义和应用。 - 对于二次函数，允许使用一般多面体，并测试不同顶点数量的结果，最终选择 12 个顶点的模型，此时目标优化函数“饱和”（即增加更多顶点，值的增加小于 0.1%）。 - **优化参数和工具**： - 三角形安全区域每个有两个自由度（Mi 和 βi），对于 n 个节点，有 2n 个参数需要优化。二次函数的安全区域每个需要 36 个参数。 - 在所有情况下，都使用 Matlab 例程 fmincon 来解决优化问题。为了计算安全区域上概率密度函数的积分，使用 Matlab 例程将数据近似为高斯混合模型（GMM）。 2. **比率查询实验**： - 该实验监测不同传感器测量的两种污染物 NO 和 NO₂ 之间的比率。每个节点持有一个向量 (xi, yi)（两种浓度），监测函数为当前读数的瞬时比率。当该函数高于阈值 T（实验中取 4）和/或 NO₂ 浓度高于 250 时，必须发送警报。 - 可允许区域 A 是一个三角形，因此是凸的，所以 C = A。测试的安全区域是图 3 所示形式的三角形，这是受集合 C 的形状启发而选择的。使用半平面方法来测试约束条件。 - 通过一个四个节点的例子可以看出，允许不同节点有不同的安全区域具有优势。节点分布更紧凑的分配较小的安全区域，监测函数值高的节点的安全区域向左平移以覆盖更多数据。与之前的工作不同，HGM 允许安全区域大于可允许区域 A。 - 在产生的局部违规数量方面，HGM 与 GM 相比有显著优势。即使节点数量较少，HGM 产生的局部违规也明显更少。随着节点数量的增加，HGM 相对于 GM 的优势更加明显。对于 10 个节点的适度网络规模，HGM 需要的消息数量比 GM 少一个数量级。 以下是不同节点数量下 HGM 和 GM 安全区域违规数量的对比表格： | 节点数量 | HGM 违规数量 | GM 违规数量 | | ---- | ---- | ---- |