距离向量算法描述

    技术2022-06-12  93

    距离向量算法描述DV算法是迭代的、异步的、分布式的。分布式的(asynchronous):节点根据从一个或多个直接相连的邻居接收信息,执行计算,并周期性的与邻居交换计算结果。迭代的(Iterative):计算过程要持续到邻居之间没有更多信息要交换为止;异步的(Distributed):不要求节点步调一致。Bellman-Ford 等式: 定义  dx(y) := x 到 y的最短距离 则dx(y) = min {cv(x,v) + dv(y) }, 其中,v 是 x的所有直接邻居基本思想:每个节点x以Dx(y)开始,对N中的节点y估计x到y的最低费用路径的费用dx(y);每个节点x需要维护:cost to each neighbor v: c(x,v)distance vector Dx = [Dx(y): y є N ]its neighbors’ distance vectorsFor each neighbor v, x maintains Dv = [Dv(y): y є N ]节点定期或发生变化时向它的邻居节点发送它的距离向量拷贝。当节点x从任意邻居节点v收到一个新的距离向量Dv = [Dv(y): y є N ] ,则存储Dv,,并使用B-F 等式更新自己的距离向量Dx(y) :

    节点x再将更新后的距离向量发送给它的邻居。只要所有节点继续以这种方式交换他们的距离向量, Dx(y)将收敛于( converge )实际的 最低费用路径的费用 dx(y) 希望看到我的博客,可以帮帮忙


    最新回复(0)