2.2.3  DV-Hop定位算法
DV-Hop算法是一种估计未知节点与信标节点之间的多跳累计距离的算法，由三个阶段组成。在每个阶段中数学模型同时给出。
第一阶段，计算未知节点与每个信标节点的最小跳数。首先使用典型的距离矢量交换协议，使网络中所有节点获得距信标节点的跳数。在算法开始的时候，每个信标节点都发出一个包括自己位置信息、地址和跳数值为0的位置信息包，它们周围所有跳数为1的邻居都收到这样的信息，将信标节点的位置信息和跳数记录下来，并将收到信息包的跳数值加l，再向自己的邻居广播。这个过程一直持续下去，直到网络中每个节点都获得每个信标节点的位置信息和相应的跳数值。由于广播是全向传播的，一个信标节点发出的广播信息可能会多次到达一个节点，这导致了节点可能会收到很多多余的广播信息。为了防止广播信息的无限循环，只有最新收到的信息才被重新广播。最新信息是指该节点最近收到的来自某个信标节点的信息包中的跳数小于之前已经收到的来自该信标节点的跳数。如果收到的信息是最新的信息，就会引起一个新的广播，而旧的信息则被丢弃，不会再进行广播。
第二阶段，计算未知节点与信标节点的平均每跳距离。每个信标节点根据第一阶段获得的其他信标节点位置和相隔跳数之后，根据下式计算网络平均每跳距离 。
                                        (2.2)
其中 、 是信标节点 、 的坐标， 是信标节点 与 之间的跳数。随后将网络平均每跳距离作为一个校正值广播至网络中。校正值采用可控洪泛法在网络中传播，这意着一个未知节点仅接受其获得的第一个校正值，而丢弃所有后来者，这个策略确保了绝大多数未知节点可从最近的信标节点处接收校正值，在大型网络中，可通过为数据包设置一个TTL域来减少通信量。
第三阶段，当未知节点接收到校正值之后，根据跳数计算出与信标节点之间的距离。最后当某一未知节点获得与3个或更多个信标节点之间的距离时，则采用极大似然估计算法实现定位计算。
假设未知节点坐标为 ，信标节点坐标分别为 、 、…、 ，信标节点到未知坐标的相应距离分别为 、 、…、 ，则根据二文空间的距离公式可列出下列方程：
上方程前k-1个方程式减去最后一个方程式，可得下列线性方程组：  (2.4)
上述方程可表现为矩阵形式                           (2.6)
使用标准的最小均方差估计方法求未知数的解，可以得到未知节点坐标：
                                                               
图2.3  DV-Hop定位算法原理示意图
在图2.3中对DV-Hop算法的原理进行了简单的图示。信标节点L2获知了与其余两个信标节点L1、L3之间的距离和跳数，根据图中所注明的数据，L2计算得到校正值（即平均每跳距离）为： 。假设未知节点A从L2处获得校正值，则它与3个信标节点之间的距离分别为3×16.42=49.26m（至L1），2×16.42=32.84m（至L2），3×16.42=49.26m（至L3），然后使用三边测量法确定未知节点A的位置。上述采用DV-Hop算法获取距离估计值的定位方案在网络平均连通度为10，信标节点比例为10%的各向同性网络中定位精度约为33%。其缺点是仅在各向同性的密集网络中，利用校正值才能合理地估算平均每跳距离[13～14]。 基于网络节点的机动目标跟踪定位技术仿真(4):http://www.751com.cn/jixie/lunwen_3038.html