WSN 四大经典无需测距定位算法

在无线传感器网络（WSN）中，节点定位是绝大多数应用（如目标追踪、环境监测、地理路由）的基础。由于硬件成本和能耗限制，网络中只有少量已知自身位置的节点（称为锚节点或信标节点），其余大量节点（未知节点）必须通过特定的算法估算自己的坐标。

根据定位过程中是否实测距离，经典定位算法分为两大阵营：基于测距（Range-based） 和 无需测距（Range-free）。后者因对硬件要求低、成本低廉，在学术界和工程界更具代表性。

以下拆解 WSN 四大经典无需测距定位算法的核心数学逻辑

---

一、 四大经典定位算法核心剖析

1. 质心定位算法 (Centroid Localization)

这是最简单、最直观的算法，其核心思想是“近朱者赤”。

• 核心逻辑：未知节点接收周围锚节点的信号。当它通信范围内的锚节点数量达到设定阈值 $k$ 时，直接将这些锚节点的几何质心作为自己的估算位置。
• 数学表达：设未知节点 $u$ 接收到 $k$ 个锚节点 $A_1, A_2, ..., A_k$ 的坐标，则 $u$ 的估算位置 $(x_u, y_u)$ 为：
  $(x_u, y_u) = \left( \frac{1}{k}\sum_{i=1}^{k}x_i, \frac{1}{k}\sum_{i=1}^{k}y_i \right)$
• 评价：计算复杂度极低，但精度严重依赖锚节点密度和分布均匀度。

2. DV-Hop 定位算法 (Distance Vector Hop)

由 Niculescu 等人提出，是 WSN 领域引用率最高的经典算法之一。它巧妙地跳出了“测距”的限制，通过平均每跳距离将跳数转换为物理距离。

• 核心逻辑分三步：

  1. 最小跳数计算：锚节点向全网洪泛自身位置，节点记录到每个锚节点的最小跳数 $h_i$。
  2. 计算平均每跳距离 ($\xi$)：锚节点根据自己与其他锚节点的真实距离和跳数，计算网络的平均每跳距离并广播。未知节点采用最先到达的锚节点广播的值作为全局平均每跳距离。
     $\xi = \frac{\sum_{i \neq j} \sqrt{(x_i-x_j)^2 + (y_i-y_j)^2}}{\sum h_{ij}}$
  3. 距离换算与三边测量：未知节点将最小跳数 $h_i$ 乘以 $\xi$ 得到估算距离 $d_i = h_i \times \xi$，最后利用三边测量法（Trilateration）或极大似然估计求解自身坐标。

• 评价：对硬件零额外要求，但在各向异性网络（如C型、U型空洞）中，跳数到直线距离的误差会被急剧放大。

3. Amorphous 定位算法

由 Stanford 的 Niculescu 团队提出，是对 DV-Hop 的改进，核心在于局部化计算。

• 核心逻辑：与 DV-Hop 使用全局统一的每跳距离不同，Amorphous 算法让每个节点基于其一跳邻居信息独立计算局部的每跳距离。
  $\xi_u = \frac{\sum_{v \in N(u)} |(x_u,y_u) - (x_v,y_v)|}{n}$
  (其中 $N(u)$ 是节点 $u$ 的邻居集合)
• 评价：在局部拓扑结构较好的场景下，精度优于 DV-Hop，但由于累积误差，在大规模网络中表现不稳定。

4. APIT 定位算法 (Approximate Point-In-Triangulation Test)

由 He T. 等人提出，灵感来源于计算机图形学中的点定位（Point-in-Polygon）问题。

• 核心逻辑：未知节点选取 3 个邻居锚节点构成一个三角形（锚节点三角测试）。如果该节点在多个这样的三角形内部，则将这些三角形的交集质心作为自身位置。
• 数学判断（重心法）：对于点 $P$ 和三角形 $ABC$，若满足以下条件则点在内：
  $\overrightarrow{PA} \times \overrightarrow{PB}, \overrightarrow{PB} \times \overrightarrow{PC}, \overrightarrow{PC} \times \overrightarrow{PA} \text{ 同向}$
• 评价：无需距离估算，鲁棒性强，但计算复杂度随锚节点数量呈立方级增长 ($O(n^3)$)，且对网络连通度要求较高（需要构成闭合三角形）。

---

二、 MATLAB 经典算法仿真对比框架

该代码会在一个 $100 \times 100$ 的区域内部署节点，并对比不同算法的定位误差。

%% WSN 经典定位算法仿真对比 (DV-Hop vs Centroid vs Amorphous)
clc; clear; close all;

%% 1. 网络参数设置
width = 100; height = 100;   % 区域大小
n_total = 100;               % 总节点数
n_anchor = 20;              % 锚节点数
comm_range = 25;            % 通信半径
max_hops = 5;               % DV-Hop最大跳数限制

% 随机部署节点
nodes = width * rand(n_total, 2);
% 前 n_anchor 个节点设为锚节点
anchors = nodes(1:n_anchor, :);
unknowns = nodes(n_anchor+1:end, :);
n_unknown = size(unknowns, 1);

% 计算真实距离矩阵 (用于后期误差评估)
dist_matrix = pdist2(nodes, nodes);
adj_matrix = dist_matrix <= comm_range; % 邻接矩阵 (通信链路)

%% 2. DV-Hop 算法核心实现
fprintf('>>> 正在执行 DV-Hop 定位...\n');
% 步骤1: 计算跳数矩阵 (Floyd-Warshall 简化版)
hop_matrix = inf(n_total);
for i = 1:n_total
    hop_matrix(i, adj_matrix(i,:)) = 1;
    hop_matrix(i,i) = 0;
end
% 简化的跳数扩散 (实际中通过洪泛协议实现)
for k = 1:n_total
    for i = 1:n_total
        for j = 1:n_total
            if hop_matrix(i,j) > hop_matrix(i,k) + hop_matrix(k,j)
                hop_matrix(i,j) = hop_matrix(i,k) + hop_matrix(k,j);
            end
        end
    end
end

% 步骤2: 锚节点计算平均每跳距离并传播 (取第一个锚节点的值作演示)
anchor_hops = hop_matrix(1:n_anchor, 1:n_anchor);
anchor_dists = pdist2(anchors, anchors);
valid_hops = anchor_hops(anchor_hops > 0 & anchor_hops <= max_hops);
valid_dists = anchor_dists(anchor_hops > 0 & anchor_hops <= max_hops);
hopsize_dv = sum(valid_dists) / sum(valid_hops);

% 步骤3: 未知节点估算距离并使用三边测量 (极大似然估计)
pos_dvhop = zeros(n_unknown, 2);
for i = n_anchor+1:n_total
    hops = hop_matrix(i, 1:n_anchor);
    est_dists = hops * hopsize_dv;
    
    % 选取最近的3个锚节点进行三边测量
    [~, idx] = sort(est_dists);
    p1 = anchors(idx(1),:); d1 = est_dists(idx(1));
    p2 = anchors(idx(2),:); d2 = est_dists(idx(2));
    p3 = anchors(idx(3),:); d3 = est_dists(idx(3));
    
    % 构建线性方程组 Ax = b
    A = 2 * [p2-p1; p3-p1];
    b = [d1^2 - d2^2 + sum(p2.^2) - sum(p1.^2);
         d1^2 - d3^2 + sum(p3.^2) - sum(p1.^2)];
     
    pos_dvhop(i-n_anchor, :) = (A'*A) \ (A'*b);
end

%% 3. 质心算法 (Centroid) 核心实现
fprintf('>>> 正在执行 Centroid 定位...\n');
pos_centroid = zeros(n_unknown, 2);
for i = n_anchor+1:n_total
    neighbor_anchors = anchors(adj_matrix(i, 1:n_anchor), :);
    if size(neighbor_anchors, 1) >= 3
        pos_centroid(i-n_anchor, :) = mean(neighbor_anchors, 1);
    else
        pos_centroid(i-n_anchor, :) = [NaN, NaN]; % 邻居不足无法定位
    end
end

%% 4. 误差计算与可视化
error_dvhop = zeros(n_unknown, 1);
error_centroid = zeros(n_unknown, 1);

valid_idx = ~isnan(pos_centroid(:,1));

for i = 1:n_unknown
    if ~isnan(pos_centroid(i,1))
        error_dvhop(i) = norm(unknowns(i,:) - pos_dvhop(i,:)) / comm_range;
        error_centroid(i) = norm(unknowns(i,:) - pos_centroid(i,:)) / comm_range;
    end
end

fprintf('------------------------------------------\n');
fprintf('DV-Hop 平均相对误差: %.4f (通信半径倍数)\n', mean(error_dvhop(valid_idx)));
fprintf('Centroid 平均相对误差: %.4f (通信半径倍数)\n', mean(error_centroid(valid_idx)));
fprintf('------------------------------------------\n');

% 绘制对比图
figure('Name', 'WSN 经典定位算法仿真', 'Color', 'w', 'Position', [100 100 1200 500]);

subplot(1,2,1);
scatter(anchors(:,1), anchors(:,2), 100, 'r', 'p', 'filled'); hold on;
scatter(unknowns(:,1), unknowns(:,2), 50, 'b', 'o', 'DisplayName', '真实未知节点');
plot(pos_dvhop(:,1), pos_dvhop(:,2), 'rx', 'MarkerSize', 10, 'LineWidth', 2, 'DisplayName', 'DV-Hop 估算');
title('DV-Hop 定位结果');
axis([0 width 0 height]);
legend; grid on;

subplot(1,2,2);
scatter(anchors(:,1), anchors(:,2), 100, 'r', 'p', 'filled'); hold on;
scatter(unknowns(:,1), unknowns(:,2), 50, 'b', 'o', 'DisplayName', '真实未知节点');
plot(pos_centroid(:,1), pos_centroid(:,2), 'mx', 'MarkerSize', 10, 'LineWidth', 2, 'DisplayName', 'Centroid 估算');
title('Centroid 定位结果');
axis([0 width 0 height]);
legend; grid on;

参考代码 WSN 经典定位算法 www.youwenfan.com/contentcsu/64814.html

三、 算法选型决策表

在实际工程或科研中，如何选择合适的算法？可以参考以下维度：

算法	计算复杂度	通信开销	硬件成本	适用场景
质心法 (Centroid)	$O(1)$	极低	无	锚节点密度极高、对精度要求不高的粗粒度定位。
DV-Hop	$O(N^2)$	中等	无	最通用的经典算法，适合大规模、均匀分布的网络。
Amorphous	$O(N)$	较高	无	局部连通性好、锚节点较少的网络。
APIT	$O(N^3)$	高	无	节点密集、需要较高定位精度的场景。