频率竞争查询策略：优化与分析

### 频率竞争查询策略：优化与分析 #### 1. 基础概念与参数定义 在探讨查询优化之前，我们需要了解一些重要的参数和概念。 - **参数λd,x**：定义为λd,x = cd,x / (1 + cd,x)。对于任意ξ ≥ 0，当x ≥ (3 + ξ)d时，有cd,x ≥ ξ。这是因为与球B间距至多为ξ的单位半径球都必须能放入与B同心、半径为3 + ξ的球内。所以，当x ≥ 4d时，1/2 ≤ λd,x < 1。 - **参数Xd**：Xd是使得cd,x = 0的最大x值，例如X2 = 6。显然，若x ≤ Xd，存在实体配置Z使得σZi (x) = 0。对于这样的x，任何查询方案要在指定目标时间将不确定性程度维持在至多x可能通常是不可能的。此后，我们假设x（拥塞潜力的界限）大于Xd。 #### 2. 固定目标时间的查询优化 假设我们的目标是针对给定的实体集E，优化查询以确保在未来某个固定目标时间τ时拥塞潜力较低，初始时实体位置完全不确定。 - **查询粒度分析**：由于初始时不确定性区域无界，若E相对于允许的潜在拥塞度量足够大，任何查询方案都必须在区间[0, τ]内查询至少固定比例的实体。因此，此区间内的最小查询粒度必须为O(τ/|E|)。若粒度不是问题，在足够接近目标时间进行O(|E|)次查询就足够了。然而，最大化最小查询粒度并不简单。 - **最优查询方案**：任何使用最小查询粒度γ、能保证在目标时间τ时拥塞潜力度量至多为x的合理查询方案，在最后n次查询内不会对任何实体查询超过一次。这样的最优查询方案为每个实体ei ∈ E确定一个半径1 + kiγ，其中： - k1, k2, ..., kn是1, 2, ..., n的一个排列。 - 不确定性配置中，实体ei的不确定性区域ui中心为ζi(τ - kiγ)，半径为1 + kiγ，且拥塞度量至多为x。对于任何度量，我们为E关联一个内在固定目标粒度，即满足这些条件的最大γ。 - **“安全”实体的识别**：通过将当前不确定性区域投影到目标时间（假设不再进行查询），可以确定一些“安全”实体，即它们的投影不确定性区域不可能导致拥塞度量（对于自身或其他任何实体）在目标时间超过x。一些查询方案利用这一思想，以几何递减的时长轮询实体，每轮之后将一部分“安全”实体搁置，不再关注，直到没有“不安全”实体为止。 #### 3. 固定目标时间的查询方案 ##### 3.1 Fixed - Target - Time - ply (FTT - ply)查询方案 该方案表明，对于任意0 ≤ Δ ≤ x，在固定目标时间可以保证不确定性层至多为x + Δ，且使用的最小查询粒度至多比任何保证不确定性层至多为x的查询方案（即使是有先见之明的方案）小Θ(x / (1 + Δ))。 - **初始查询**：由于所有实体在时间0时不确定性区域无界，若x + Δ < n，没有实体一开始就是(x + Δ) - 层安全的。因此，任何方案（包括有先见之明的方案）为避免在目标时间层大于x，必须至少查询除x个实体之外的所有实体一次。FTT - ply[x + Δ]方案首先以查询粒度τ / (2n)对所有实体进行一轮查询，假设n - (x + Δ) = Ω(x + Δ)，这与其他任何方案的操作具有O(1)竞争力。 - **后续轮询**：之后，该方案识别出尚未达到(x + Δ) - 层安全的n1个实体（不安全幸存者），将其他实体搁置。然后以查询粒度τ / (4n1)对这n1个幸存者进行第二轮查询。一般来说，第r轮之后，识别出nr个不安全幸存者（若nr > 0），并以粒度τ / (2r + 1nr)进入第(r + 1)轮。第r轮在时间τ - τ / 2r完成，且所有未被搁置的实体投影不确定性区域半径在(1 + τ / 2r, 1 + τ / 2r - 1]范围内。 - **定理1**：对于任意0 ≤ Δ ≤ x，FTT - ply[x + Δ]查询方案保证在目标时间τ时不确定性层至多为x + Δ，且在区间[0, τ]内使用的最小查询粒度至多比保证不确定性层至多为x的内在固定目标粒度小一个因子Θ(x / (1 + Δ))。 ##### 3.2 Fixed - Target - Time - degree (FTT - degree)查询方案 此方案更为复杂，它表明对于任意0 ≤ Δ ≤ x，在固定目标时间可以保证不确定性度至多为x + Δ，且使用的最小查询粒度至多比任何保证不确定性度至多为x的查询方案小Θ(x / (1 + Δ))。