无线网络_Geographic Routing

GeographicRouting——基于地理信息的路由算法GeographicRouting的基本运行原理每个节点需要具备定位系统数据传输前源节点需要知道目的节点的地理位置不同的数据包传输策略•限制性泛洪传输（GPSR等）•分层次传输（GridRouting等）GPSR(GreedyPerimeterStatelessRouting)路由协议GPSR协议核心思想：GPSR协议是一个典型的基于位置的路由协议。使用GPSR协议，网络节点都知道自身地理位置并被统一编址，各节点利用贪心算法尽量沿直线转发数据。产生或收到数据的节点向以欧氏距离计算最靠近目的节点的邻节点转发数据，但由于数据会到达没有比该节点更接近目的点的区域(称为空洞)，导致数据无法传输，当出现这种情况时，空洞周围的节点能够探测到，并利用右手法则沿空洞周围传输来解决此问题GPSR(GreedyPerimeterStatelessRouting)路由协议当y是x邻节点中最靠近D（目的节点）的节点，x将数据包转发给y：当x的邻节点中没有比x更接近D的节点：GPSR(GreedyPerimeterStatelessRouting)路由协议遭遇空洞，此时采用右手法则选取下一跳节点，本图中选取w为下一跳节点：GPSR(GreedyPerimeterStatelessRouting)路由协议另一个GRSR路由实例：GPSR(GreedyPerimeterStatelessRouting)路由协议GPSR协议优点：•避免了在节点中建立、维护、存储路由表，只依赖直接邻节点进行路由选择，几乎是一个无状态的协议；•使用接近于最短欧氏距离的路由，数据传输时延小；并能保证只要网络连通性不被破坏，一定能够发现可达路由。GPSR(GreedyPerimeterStatelessRouting)路由协议GPSR协议的不足：•1.当网络中sink点和源节点分别集中在两个区域时，由于通信量不平衡易导致部分节点失效，从而破坏网络连通性；•2.需要GPS定位系统或其他定位方法协助计算节点位置信息。GPSR(GreedyPerimeterStatelessRouting)路由协议Landmark路由协议Landmark路由是一种分层次路由协议•上层次采用landmark路由•普通节点采用FSR路由它可以在任意大小的网络中自动而有效的运行；它随着网络条件的变化而变化；它能够提供足够的基础地址，充分适应任何比例的移动节点。Landmark路由协议Landmark路由分群策略：•Landmark路由是利用运动趋势的相关性或者功能的相似性来进行分群的，即把具有相同运动趋势的节点或者是执行同一种任务的节点分成一个群，由于这个群是在动态的情况下建立的，在节点的移动时间、功能、任务发生变化时，群的位置、成员数都可能会发生变化，所以我们称这个群为”动态”群。•通过观察节点之间的相对运动来识别•根据节点的跳数来确定（同时确定了群的大小为n跳）Landmark路由协议在Landmark路由中各节点的地址类似于IP地址，不同的群体使用子网掩码进行区别。每个群体都动态的选举出一个节点作为Landmark。Landmark路由协议Landmark路由类似树结构的层级划分Level2LandmarkLevel1LandmarkLevel0LandmarkNodea’sAddress：a,b,cLandmark路由协议Landmark路由的群内通信（FSR协议）：•鱼眼链路状态路由协议FSR(FisheyeStateRouting)是一种先应式(表驱动)的基于链路状态的路由协议，它是一种隐性分等级(hierarchical)的路由协议。“鱼眼”技术在路由中用来维护精确的距离和路由质量信息，但也会距离的变大而逐渐不精确。鱼眼域就是在一定跳数范围内的节点的集合。FSR使用了鱼眼技术，在不同的鱼眼域中，节点以不同的频率（由节点的距离决定）只向邻居节点广播链路信息。这样能够大大减少链路状态更新信息，从而降低了洪泛的开销。Landmark路由协议Landmark路由的群内通信（FSR协议）：鱼眼域鱼眼域减少路由图形Landmark路由协议Landmark路由的群移动模式：•利用群首的移动来代表整个群的移动•把群的区域定义为以群的重心为圆心、以预定距离为半径的圆形区域。Landmark路由协议Landmark路由的群移动模式：Landmark路由协议Landmark路由群移动的实现：•群中心的确定Landmark路由协议Landmark路由中群首的选择•网络中，群的容量是有限的——这就是为什么一个节点停留的范围要大于群首的范围。节点的“信息量”被定义为群的相关性的大小，即：在TCs的成员S中，每一个节点都记录了群首ID和”信息量”，每个节点都可以竞争群首，这个消息(可能是携带在路由信息中的)周期性地进行广播，并且实时传播最新的竞争结果。群首的竞争就是通过通用的竞争规则来确定：如果那个节点的信息量最大，那么它就是这个动态群的群首，其他节点延期。不同的群移动方式决定了不同的传播路径，也决定了群的选择。在群的动态结构中，群首作为群标志，把他的ID作为唯一的合法ID确定下来。然后。群与群之间的路由向量将周期性的向群中的全体成员和网络中的所有群首广播身份。Landmark路由协议Landmark路由的实例：Landmark路由协议Landmark路由的实例：•当同一个群中的两个节点A和D发送数据包时，源节点A通过自身的路由信息表获知目的节点D是在本群范围内，那么它就会通过自身的路由表查找出最恰当的路由而将信息包成功发送到目的节点D；Landmark路由协议Landmark路由的实例：•而在群LM2中的节点E向另外一个群LM1中的节点I发送信息包时，E首先查找自己的路由信息表，得知节点I不是本群范围内的节点，那么它就通过自身所在的群的Landmark节点E查找出节点I在群LM1中，此时它就查找最佳路径将信息包发送到节点I：它首先将信息包通过本群内的节点F、G转发到H，到达H之后，它会发现A节点H中存在着直接到达I的最佳路由，所以它就直接从H发往I，注意此时信息并没有经过I的群首LM1节点；Landmark路由协议Landmark路由的实例：•同样，另一条路由是当源节点J向不同群中的目的节点Q发送信息包时，它也会通过自身群的Landmark节点查找最佳路由，此时信息包虽然经过了LM3中的节点M和LM4中的节点O、P、Q，但是并没有通过Landmark节点LM3和LM4，Landmark路由协议Landmarkd的路由策略：•发向本群内节点的数据通过fisheye路由表来获得目的节点的直接路由•发向远方目的节点的数据根据目的节点的ID直接发向对应的Landmark•一旦数据进入Landmark的范围，就可以通过FSR路由找到目的节点谢谢！