[工程科技]关于Geographical Routing Using Partial Information for Wireless Ad Hoc Networks的幻灯片.ppt

4、地理路由算法 基本思想:使用目的地的地理位置进行路由决策 每一个节点只知道在网络中的少量节点,相比于距它较远的节点它更了解接近它的节点 该算法具有一个内置的数据包越接近目的地越能找到好的路线的能力，即使源节点非常“粗略”地“知道”目的地周围网络拓扑结构 通过证明路由表是非循环的且数据包到达目的地证明它的正确性。 我们在平均路由表长度方面量化算法的性能。 4、地理路由算法 4.1.1Voronoi单元 我们引入Voronoi视图的概念。这是一个查看路由操作的几何方式。 让 ={S1,S2,...,Sk}是一组在时间t地理位置对于节点S是已知的节点（我们假设S ） 这些节点作为节点S中心 把所在区域IR2划分成单元 中心为Si的Voronoi单元:围绕中心Si的单元包括比任何其他Sj更接近Si的所有点 4、地理路由算法 4.1.1Voronoi单元 例1（Voronoi单元） 节点S在其路由表中有节点A，B，C，D作为中心，但E不是。 但是如果节点E是节点S一些数据包的目的地，那么S发送数据包给恰好是S的Voronoi视图中最接近节点E的邻居节点D。 4、地理路由算法 4.1.2路由表结构 NextS(S)表示N S的每个路由表条目是一个四元组 （Si，pos(Si)，NextS(Si)，TSi） 例如（－，pos(Si)，NextS(Si)，－） 时间戳是目的节点答复路由发现消息的时间点 4、地理路由算法 4.1.3数据包格式 源和目标的唯一名称在包中指定。 目的地的位置也在数据包中被指定。 目标名称和位置用于数据包转发和路由发现。 包括源时间戳，源名称和源位置，因为实施GRA可能需要这些。 4、地理路由算法 4.2数据包转发 CS表示S知道的所有节点的一组名称 数据包的转发决定:当节点S接收到一个目的地为D的数据包，它发现条目（Si，pos(Si)，NextS(Si)）使得Si比任何其他Sj更接近D。然后它将数据包传送给NextS(Si) 还有可能出现以下情况... 4、地理路由算法 4.2数据包转发 注：≤id表示节点名称的完整顺序。 节点S本身最接近D,即数据包卡住在A 路由发现过程route_discovery(S，D)发现一个从S到D的非周期性路径Path(S,D)=k0,k1,...,kl，并且它通过条目（D，pD，ki+1）更新节点ki的路由表。 2.节点Si和Sj到目的地D一样近,即节点位于单元边界 假设名称之中有一个总顺序，且使用这个去解决这个束缚（即，如果Si Sj，这个就发送给NextS(Si)，否则发送给NextS(Sj)） 4、地理路由算法 4.2数据包转发 对以上情况的举例 例2 4、地理路由算法 4.2数据包转发 例2更新后的路由表 即使A的路由表中没有E，它也可以把数据包发送给E 4、地理路由算法 4、地理路由算法 4.2数据包转发 如果a b，1和2都要选择a 4、地理路由算法 4.3路由发现 路由发现机制的唯一要求是，它返回一个到目的地的非循环路径，并以适当的方式更新该路径上的路由表 性质1（路由发现协议）如果一个数据包被卡在节点S，那么S启动一个路由发现协议。这个路由发现协议找到一条非周期性路径Path(S,D)=k0,k1,...,kl并且加入一个条目（D，pos(D)，ki+1）到Table(ki)其中0≤il。我们也要求路由发现协议在更新Table(ki+1)之前先更新路由表Table(ki)。 4、地理路由算法 4.3.1寻路阶段 广度优先有哪些信誉好的足球投注网站 节点A广播一个路由发现数据包（RD packet）启动路由发现协议 接收到RD包的每个节点如果以前没转发过这个数据包，则它也广播这个数据包，路由发现发现的路径是无周期的 每个节点广播数据包，并将其名称和地址放入数据包，这样路由发现走过的路径被包被保留 数据包返回到一个节点，则会被丢弃 路由发现过程完成，每个到达D的数据包包含一条从S到D的非循环性路径 4、地理路由算法 4.3.1寻路阶段 深度优先有哪些信誉好的足球投注网站 只产生一个从节点S到目的节点D的单一的非循环路径 将包转发到一个以前没有看到过这个数据包的邻居，得到节点转发数据包的邻居是一个最大限度减少距离度量的选择 如果 其中NX是节点X的可以向之转发数据包的一组邻居，d（X,Z）是节点X与节点Z之间的欧氏距离 则，节点X将目的节点为D的数据包转发给邻居节点Y 4、地理路由算法 4.3.2更新路由表 节点D然后通过沿路径Path(D,S)=kl,kl-1,...,k0发回一个ACK数据包启动路由更