SR-RCD

将缺陷覆盖精炼算法应用于解决时变度量（特别是（准）度量）空间中的声测问题。

是“Decaennead：关于抽象空间（时间）中的声测及相关主题的沉思”项目的一部分。

声测

未知点 s（源），在未知时刻 t₀ 发出声音。声波通过空间传播并到达已知点 r_i（传感器），在已知时刻 t_i。声测（SR）问题，也称为源定位或到达时间差（TDOA）问题，是从 {r_i，t_i} 确定未知点 s 和 t₀。

据信 SR 问题的最早记录可以追溯到第一次世界大战时期；1915 年，它在 E. Borel 和 H. Lebesgue 之间的通信中简要提到。

通过将声音替换为电磁波或某种“传播”，例如在图中，从声学转移到光学和其他环境。

时度量

F-时度量。 设 X 是一个非空集，τ 是一个在 ℝ×X×X 上定义的非负函数，它满足以下公理

1. 前向自反性： 对于任何 t ∈ ℝ：τ_t(x, y) = 0 当且仅当 x = y，

2. 前向时间三角不等式： 对于任何 t ∈ ℝ 和任何 x、y、z ∈ X：τ_t(x, y) ≤ τ_t(x, z) + τ_{t + τt(x, z)}(z, y)。

则 (X, τ) 被称为一个 F-时度量 空间。

在 SR 环境中，τ_t(x, y) 被解释为在 t 时刻从 x 发出的声波传播到 y 所需的时间。该波在 t + τ_t(x, y) 时刻到达 y。

B-时度量。 设 X 是一个非空集，τ̅ 是一个在 ℝ×X×X 上定义的非负函数，它满足

1. 后向自反性： 对于任何 t ∈ ℝ：τ̅_t(x, y) = 0 当且仅当 x = y，

2. 后向时间三角不等式： 对于任何 t ∈ ℝ 和任何 x、y、z ∈ X：τ̅_t(x, y) ≤ τ̅_t(z, y) + τ̅_{t - τ̅t(z, y)}(x, z)。

则 (X, τ̅) 被称为一个 B-时度量 空间。

在SR（空间相关）背景下，τ̅_t(x, y) 被解释为从 x 发出并在 t 时刻到达 y 的声波传播从 x 到 y 所需要的时间。这个波在 t - τ̅_t(x, y) 时刻从 x 发出。

定时三角不等式表示“波尽可能快地通过介质”的概念。请注意，在例如正向 TTI 中，存在 τ_{t + τt(x, z)}(z, y)，而不仅仅是 τ_t(z, y)，因为介质会改变，并且波同时通过它传播。

f-时距和 b-时距之间的关系

τ̅_t(x, y) = τ_{t - τ̅t(x, y)}(x, y)

τ_t(x, y) = τ_{t + τt(x, y)}(x, y)

如果 τ 不依赖于 t，那么我们有一个 准度量

1. 自反性： τ(x, y) = 0 当且仅当 x = y,

2. 有向三角不等式： 对于任何 x, y, z ∈ X: τ(x, y) ≤ τ(x, z) + τ(z, y)。

如果准度量 τ 满足

3. 对称性： 对于任何 x, y ∈ X: τ(x, y) = τ(y, x)

那么 (X, τ) 是一个普通的 度量空间。

对于固定的 t，在一般情况下，时距 τ_t(·) 不一定是度量或甚至是准度量。

快速开始

extern crate sr_rcd;

use std::time::Instant;

use sr_rcd::{    
    Point,
    TimetricSpace,
    rcd,
    RMPAtmo,
    Sensor
};

fn main() {
    let space = RMPAtmo::new(3, 3.14, &Point::new(vec![3.4, -5.6, 7.8]), 0.03, 1e-4);

    let sensorium = vec![
        Sensor::make(&Point::new(vec![19.894, -437.750, -455.413]), -244.940),
        Sensor::make(&Point::new(vec![216.980, -481.563, -45.759]), -153.382),
        Sensor::make(&Point::new(vec![85.351, -196.650, -422.263]), -300.745),
        Sensor::make(&Point::new(vec![61.788, 287.007, 384.448]), 383.750),
        Sensor::make(&Point::new(vec![-467.058, -97.973, -241.471]), 246.294),
        Sensor::make(&Point::new(vec![-234.397, -150.994, -429.143]), 10.128),
        Sensor::make(&Point::new(vec![-86.850, -215.597, 248.349]), 175.276),
        Sensor::make(&Point::new(vec![50.284, 460.754, -16.951]), 315.329),
        Sensor::make(&Point::new(vec![-294.371, -61.068, -427.287]), 82.082),
        Sensor::make(&Point::new(vec![475.401, 353.986, 62.538]), 242.594),
        Sensor::make(&Point::new(vec![263.802, -321.952, -408.792]), -480.919),
        Sensor::make(&Point::new(vec![-112.307, 493.069, -168.420]), 343.031)
    ];

    let start = Instant::now();
    match rcd(&space, &sensorium, &Point::new_default(space.dim()), 1000.0, 0.1, 0.001, false) {
        Ok(z) => {
            println!("Time: {:.3} sec", start.elapsed().as_secs_f64());
            println!("RCD-approximated source: {:.4?}", &z);
        },
        Err(s) => println!("ERROR: {}", s)
    }
}

执行结果如下

Iteration 1: 75 coverands, d = 3342.0306
Iteration 2: 428 coverands, d = 4013.1741
Iteration 3: 501 coverands, d = 2568.8301
Iteration 4: 87 coverands, d = 848.0291
Iteration 5: 59 coverands, d = 357.5475
Iteration 6: 44 coverands, d = 178.7737
Iteration 7: 20 coverands, d = 40.2004
Iteration 8: 13 coverands, d = 20.1002
Iteration 9: 15 coverands, d = 10.0501
Iteration 10: 15 coverands, d = 3.8286
Iteration 11: 17 coverands, d = 2.1544
Iteration 12: 16 coverands, d = 0.9355
Iteration 13: 17 coverands, d = 0.4677
Iteration 14: 16 coverands, d = 0.2339
Iteration 15: 17 coverands, d = 0.1365
Iteration 16: 15 coverands, d = 0.0585
Time: 4.348 sec
RCD-approximated source: [262.0173, -319.4046, -392.4598]

这里的 Time 是使用 release 配置文件获得的；dev 配置文件几乎慢了 5 倍。

请参阅 bin/random.rs 和 bin/manual.rs。

RCD

该算法在 PDF 草稿中被考虑；还可以参见先前的 另一个 PDF 草稿 和 doi:10.12697/ACUTM.2020.24.14，其中分别讨论了准度量空间和适当度量空间的相关简单版本。（或者这个方法是不是早在 1920-50 年代的某些论文中就已经构想出来了？..）基本来说，部分空间被球覆盖，然后通过用半径减半的球覆盖每个球并丢弃那些在其中心“过去传播”范围大于其两倍半径的球，迭代地细化覆盖，直到覆盖足够小。这是所谓的“排除 & 包围”方法的一个特例。

它的实现位于 rcd.rs。

自定义空间

从原则上讲，该算法在满足某些假设的任何 b-时距空间中工作，这里只有一个具有周期性移动的大气或恒定风速的赋范空间 ℝ^m_p，— 请参阅 rmp.rs。一旦为 AnotherSpace 实现了与 TimetricSpace 相同的 trait，RCD 就可以使用 AnotherSpace 中的 SR 问题。此外，RCD 本身不需要该 trait 的 ftau() 方法，因此，如果 SR 数据已经存在，则此方法可以是占位符。

鲁棒性

为了模拟测量中的噪声，通过将 err_dev 参数设置为 σ，将 N_0,σ² 分布的错误添加到每个 t_i。当其他参数采用默认值时，特别是近似精度 δ = 0.1，当 σ = δ/10 时，算法在近 30% 的运行中失败，因为覆盖范围变为空；当 σ = δ/5 时，失败率接近 90%。

更高维度和更强的风

在 4D（以及 5D 等）或大气角频率从 0.03 增加到 0.07 的情况下，过程几乎总是在第二次迭代时在通用计算机上长时间停滞，第一次迭代后的覆盖范围数量在数百。广泛来说，可以通过使用足够快的计算机来避免这种情况，但也可能有其他优化方法。

因此，对于更高维度或更强的风，目前这主要处于理论领域...