DV-Hop算法

RoseKey · 2023-10-25 19:51:04 · 个人记录

DV-Hop算法调查报告 DV-Hop（Distance Vector-Hop）算法是无线传感器网络定位中的一种常用算法，特别是在 信标节点（已知自身位置的节点）密度较低的环境中。它主要通过网络中的跳数信息来估计 节点之间的距离，进而定位未知节点的位置。下面我将详细介绍DV-Hop算法，并给出相关 的代码实例。

1. 算法原理与步骤 DV-Hop算法分为三个主要步骤： 1.1 跳数计算 所有信标节点将自己的位置和跳数（初始为0）广播到网络。 当其他节点接收到这个信息时，将跳数加1，并记录下到该信标节点的最小跳数。 如果一个节点收到了多个来自同一个信标节点的消息，它将保留跳数最小的那个。 1.2 平均跳距计算 信标节点之间计算出实际距离，并广播到网络。 每个节点接收到距离信息后，利用已知的跳数，计算出到每个信标节点的平均跳距。 1.3 位置计算 每个盲节点利用到信标节点的跳数和平均跳距，估算出到信标节点的距离。 利用三点定位或其他定位方法，计算出自己的坐标。

2. 输入与输出 输入：  二维空间长度  网络中所有节点数量  信标节点数量  节点间通信半径  信标节点坐标  盲节点（未知节点）坐标

输出：  盲节点估计坐标  误差值

3. 具体代码

4. import numpy as np

5. from scipy.optimize import minimize

7. def distance(a, b):

8. return np.sqrt(np.sum((a - b)**2))

10. def compute_hops(known_nodes, unknown_nodes, communication_radius):

11. num_known = len(known_nodes)

12. num_unknown = len(unknown_nodes)

13. hops = np.full((num_known, num_unknown), np.inf)

14. for i in range(num_known):

15. for j in range(num_unknown):

16. if distance(known_nodes[i], unknown_nodes[j]) <= communication_radius:

17. hops[i, j] = 1

18. for k in range(num_known):

19. for i in range(num_known):

20. for j in range(num_unknown):

21. hops[i, j] = min(hops[i, j], hops[k, j] + 1)

22. return hops

24. def dv_hop(known_nodes, unknown_nodes, communication_radius):

25. num_known = len(known_nodes)

26. num_unknown = len(unknown_nodes)

28. 初始化跳数和跳距数组

29. hops = compute_hops(known_nodes, unknown_nodes, communication_radius)

30. hop_sizes = np.zeros(num_known)

32. 平均跳距计算

33. for i in range(num_known):

34. total_distance = 0

35. hop_count = 0

36. for j in range(num_known):

37. if i != j and distance(known_nodes[i], known_nodes[j]) <= communication_radius:

38. total_distance += distance(known_nodes[i], known_nodes[j])

39. hop_count += hops[j, :].min()

40. if hop_count != 0:

41. hop_sizes[i] = total_distance / hop_count

43. 位置计算

44. estimated_coordinates = np.zeros((num_unknown, 2))

45. for i in range(num_unknown):

46. valid_nodes = hop_sizes != 0

47. if np.sum(valid_nodes) < 3:

48. raise ValueError("三点测量至少需要3个具有非0跳数的节点")

49. distances = hops[valid_nodes, i] * hop_sizes[valid_nodes]

50. estimated_coordinates[i, :] = trilateration(known_nodes[valid_nodes], distances)

52. return estimated_coordinates

54. def trilateration(known_nodes, distances):

55. num_nodes = known_nodes.shape[0]

56. if num_nodes < 3:

57. raise ValueError("三点测量至少需要3个点")

59. A = np.zeros((num_nodes-1, 2))

60. b = np.zeros(num_nodes-1)

62. for i in range(1, num_nodes):

63. A[i-1] = 2 * (known_nodes[i] - known_nodes[0])

64. b[i-1] = distances[0]2 - distances[i]2 - np.sum(known_nodes[0]2) + np.sum(known_nodes[i]2)

66. estimate = np.linalg.lstsq(A, b, rcond=None)[0]

67. return estimate

69. def initialize_nodes(num_anchors, num_unknowns, area_size):

70. """随机初始化锚节点和未知节点的位置"""

71. anchors = np.random.rand(num_anchors, 2) * area_size

72. unknowns = np.random.rand(num_unknowns, 2) * area_size

73. return anchors, unknowns

75. 示例节点坐标

76. known_nodes = np.array([[0, 0], [10, 0], [5, 8.6603], [2, 2], [8, 2]])

77. unknown_nodes = np.array([[5, 0], [10, 5]])

78. num_anchors = 30

79. num_unknowns = 10

80. area_size = 50

81. known_nodes, unknown_nodes = initialize_nodes(num_anchors, num_unknowns, area_size)

83. 设置通信半径

84. communication_radius = 30

86. 调用dv_hop函数进行定位

87. estimated_coordinates = dv_hop(known_nodes, unknown_nodes, communication_radius)

89. 打印结果

90. print("盲节点的估计值")

91. print(estimated_coordinates)

93. errors = np.linalg.norm(estimated_coordinates - unknown_nodes, axis=1)

94. average_error = np.mean(errors)

95. print("\n误差：实际坐标与估计值之间的平均欧几里得距离")

96. print(average_error)

97. 误差分析 DV-Hop算法的精度受多种因素影响，包括信标节点的密度、通信半径的大小、网络的拓扑结构等。 4.1 信标节点密度 信标节点的密度直接影响到跳数计算的精度。信标节点越密集，跳数计算越准确，进而估计的距离和位置也越准确。

4.2 通信半径 通信半径的大小也是一个重要因素。如果通信半径过小，节点之间可能无法直接通信，导致跳数计算不准确。如果通信半径过大，跳数可能都为1，无法区分不同节点间的距离。

4.3 网络拓扑 网络的拓扑结构也会影响定位精度。在一些极端情况下，例如信标节点都位于网络的一边，盲节点的定位误差会较大。

4.4 优化建议 增加信标节点的密度，提高跳数计算的精度。 优化通信半径的大小，确保网络的连通性，同时避免跳数过小。 在可能的情况下，尽量使信标节点在空间上均匀分布，避免出现不利于定位的拓扑结构。

5. 具体优化 5.1 平均跳数计算优化 通过查阅论文得知，传统DV-Hop定位算法只考虑了最近一个锚节点估计的平均跳距离值,而单个锚节点估计的平均跳距离值无法准确地反映网络的实际平均跳距离。刘峰[1]等人提出了一种基于加权处理的平均跳距离估计算法,考虑多个锚节点估计的平均跳距离值,根据距离未知节点的跳数进行加权,使网络平均跳距离的估计更加准确,从而提高定位精度。

   假设未知节点共收到 n 个锚节点的信息，将每个锚节点 的平均跳距离的加权值记为Wi ，则取

   将锚节点 i 的估计的平均跳距离记为Si ，将未知节点距离锚节点 i 的跳数记为Ni (其中 i＝1，2，3…) 即未知节点的平均每跳距离等于每个锚节点平均每跳 距离的加权值Wi 与每个锚节点的平均每跳距离Si 的乘积之 和。这样各个锚节点的平均每跳距离值按照其离未知节点的 距离进行了加权的处理，从而使未知节点的平均每跳距离的 估计值更为准确，更好地反映了网络的实际平均每跳距离。 改进部分代码：

6. def weighted_hop_size(known_nodes, hops_between_anchors, hops_to_unknown, communication_radius):
7. num_known = len(known_nodes)
8. hop_sizes = np.zeros(num_known)
10. for i in range(num_known):
11. total_distance = 0
12. total_hops = 0
13. for j in range(num_known):
14. if i != j and distance(known_nodes[i], known_nodes[j]) <= communication_radius:
15. total_distance += distance(known_nodes[i], known_nodes[j])
16. total_hops += hops_between_anchors[i, j]
17. if total_hops != 0:
18. hop_sizes[i] = total_distance / total_hops
20. return hop_sizes

用以下参数作为评价指标，其中 t(i)为估计值，r(i)为真实值，N 是锚节点数，M=1 由此得到的均方根结果如下表所示：

总结点数 DV-Hop Weight-DV-HOP 50 0.038721 0.005961 100 0.035462 0.002553 300 0.018621 0.002320 500 0.015721 0.001984

从上表中可以看到，在使用了基于加权处理的平均跳距离估计算法后，平均跳距离估计值的均方根误差比原算法要小得多，在不同场景中大约只有 1/10 到 1/6。由此采用新算法得到的平均跳距离值与实际值更吻合，可以更准确的反映网络实际平均跳距离，从而提高定位精度。

5.2 PSO粒子群优化 5.2.1 PSO概率 粒子群优化（PSO）是一种模拟鸟群觅食行为的启发式优化算法。该算法是通过模拟鸟群中的个体之间的交互行为，使整个鸟群向最优解移动。PSO算法的每个解都被看作是一个“粒子”，每个粒子都有自己的速度和位置。通过不断地更新粒子的速度和位置，使得粒子群逐渐趋向于最优解。 PSO算法的主要步骤如下：

1. 初始化粒子群的位置和速度。
2. 计算每个粒子的适应度值。
3. 更新每个粒子的速度和位置。
4. 重复步骤2和3，直到满足停止条件。 由于PSO算法的全局搜索能力和高效的收敛性，它被广泛应用于各种优化问题。

5.2.2 改进 无线传感器网络的定位问题本质上是对非线性方程组求出精确解，因此定位问题已经被证明是一个 NP 难解的问题。 DV-Hop 算法的误差来源主要是网络中锚节点的平均每跳距 离，未知节点认为接收到的平均每跳距离都是相同的，而且每个节点都是在线计算平均每跳距离，通信开销比较大，因此平均定位误差较大。已经有研究利用遗传算法、模拟退火算法和粒子 群算法来提高定位估计的精度。在此提出利用粒子群优化算法 对定位问题后期进行优化，即对未知节点坐标进行校正。

无线传感器网络定位误差主要来源于相关测距技术的错误，因此误差必然存在，定位问题的实质就是使误差最小化。利 用粒子群算法校正节点的位置实质上可以转化为对定位误差的最小化。假设( x，y) 为未知节点需要定位的坐标，可得未知节点与第 i 个锚节点之间的距离 di。那么定位误差可以定义为: 

其中: di hat 为 di 的实际测量距离值。采用上式作为适应度函数可来评价粒子的适应度值。当达到迭代次数后停止 PSO 算法，将当前找到的最优解作为未知节点的最终估算位置。

其中，αi 是未知节点与锚节点 i 之间的跳数值的倒数，n 表示未知节点的数量 具体改进代码:

1. def pso(known_nodes, estimated_positions, distances, num_particles=30, max_iter=100):
2. num_unknown = estimated_positions.shape[0]
3. dim = estimated_positions.shape[1]

5. 初始化粒子群

6. particles = np.random.rand(num_particles, num_unknown, dim) * 50 # 假设区域大小为50x50
7. velocities = np.random.rand(num_particles, num_unknown, dim) * 0.1
8. personal_best_positions = np.copy(particles)
9. personal_best_scores = np.full(num_particles, np.inf)

11. 初始化全局最优

12. global_best_position = None
13. global_best_score = np.inf
15. for iter in range(max_iter):
16. for i in range(num_particles):

17. 评估粒子性能

18. score = objective_function(particles[i], known_nodes, distances)

20. 更新个体最优

21. if score < personal_best_scores[i]:
22. personal_best_scores[i] = score
23. personal_best_positions[i] = particles[i]

25. 更新全局最优

26. if score < global_best_score:
27. global_best_score = score
28. global_best_position = particles[i]

30. 更新粒子速度和位置

31. w = 0.5 # 惯性权重
32. c1 = 1.5 # 个体学习因子
33. c2 = 1.5 # 社会学习因子
34. for i in range(num_particles):
35. r1 = np.random.rand(num_unknown, dim)
36. r2 = np.random.rand(num_unknown, dim)
37. velocities[i] = (w * velocities[i] +
38. c1 r1 (personal_best_positions[i] - particles[i]) +
39. c2 r2 (global_best_position - particles[i]))
40. particles[i] += velocities[i]

42. return global_best_position

    经过实验验证，得到的评价指标对比如下表所示（评价指标定义在上文）

总结点数 DV-Hop DV-Hop based on PSO 50 0.038721 0.002638 100 0.035462 0.002581 300 0.018621 0.001432 500 0.015721 0.001053