《路由协议》PPT课件.ppt

1、第2章 路由协议,-林志贵 2012/3/10,主要内容：,概述 路由协议分类 能量感知路由 基于查询的路由 地理位置路由 可靠路由协议 路由协议自主切换,概述,路由协议负责将数据分组从源节点通过网络转发到目的节点。 功能： 1）寻找源节点和目的节点间的优化路径； 2）将数据分组沿着优化路径正确转发。,概述,特点： 能量优先 基于局部拓扑信息 以数据为中心 应用相关,要求： 能量高效 可扩展性 鲁棒性 快速收敛性,路由协议分类,1）能量感知路由协议 从数据传输中的能量消耗出发，讨论最优能量消耗路径以及最长网络生存期等问题。 2）基于查询的路由 通信流量主要是查询节点和传感器节点之间的命令和数据

2、传输。 3）地理位置路由协议-节点的位置 4）可靠的路由协议-网络的可靠性和实时性,能量感知路由,1）能量路由 根据节点的可用能量(PA)或传输路径上的能量需求，选择数据的转发路径。 特点：需要知道整个网络的全局信息,策略：最大PA路由、最小能量消耗路由、最少跳数路由及最大最小PA节点路由,能量感知路由,2）能量多路径路由 思想：在源节点和目的节点之间建立多条路径，根据路径上节点的通信能量消耗以及节点的剩余能量情况，给每条路径赋予一定的选择概率，使得数据传输均衡消耗整个网络的能量，延长整个网络的生存期。 过程：路径建立、数据传播和路由维护。,能量感知路由,目的节点向邻居节点广播路径建立消息，启

3、动路径建立过程-代价域。 当节点收到邻居节点发送的路径建立消息时，相对发送该消息的邻居节点，只有当自己距源节点更近，而且距目的节点更远的情况下，才需要转发该消息，否则将丢弃该消息 如果节点决定转发路径建立消息，需要计算新的代价值来替换原来的代价值。,能量感知路由,节点要放弃代价太大的路径，节点j将节点i加入本地路由表FTj中的条件：,能量感知路由,节点为路由表中每个下一跳节点计算选择概率，节点选择概率与能量消耗成反比。,节点根据路由表中每项的能量代价和下一跳节点选择概率计算本身到目的节点代价。,基于查询的路由,定向扩散路由 思想：汇聚节点通过兴趣消息发出查询任务，采用洪泛方式传播兴趣消息到整个

4、区域或部分区域内的所有传感器节点。 在兴趣消息的传播过程中，协议逐跳地在每个传感器节点上建立反向的从数据源到汇聚节点的数据传输梯度。传感器节点将采集到的数据沿着梯度方向传送到汇聚节点。 途径：兴趣扩散、梯度建立和路径加强三个阶段。,基于查询的路由,定向扩散路由,基于查询的路由,谣传路由 思想：事件区域中的传感器节点产生代理消息，代理消息沿着随即路径向外扩散传播，同时汇聚节点发出的查询消息也沿随机路径在网络中传播。代理消息和查询消息的传输路径交叉在一起时，就会形成一条汇聚节点到事件区域的完整路径。,基于查询的路由,谣传路由,地理位置路由,节点通常需要获取它的位置信息，使采集的数据更加有意义。 如

5、：森林防火应用。消防人员不仅需要知道发生了火灾事件，还需要知道发生火灾事件的确切位置。,地理位置路由,GEAR(geographical and energy aware routing) 原理：根据事件区域的地理位置信息，建立汇聚节点到事件区域的优化路径，避免洪泛传播方式，减少路由建立的开销。,地理位置路由GERA,1 查询消息传送到事件区域 GERA用实际代价和估计代价表示路由代价， 没有建立从汇聚节点到事件区域路径时，中间节点用估计代价来决定下一条节点。 估计代价定义：节点到事件区域的距离以及节点的剩余能量两部分 计算公式：C(N，R)=ad(N，R)+(1-a)e(N) 其中：C(N，

6、R)表示估计代价，d(N，R)为节点N到事件区域的距离，e(N)节点N中的剩余能量，a为比例参数。,地理位置路由GERA,查询信息到达事件区域后，事件区域的节点沿着查询路径的反向传输检测数据消息。数据消息中包含每跳节点到事件区域的实际能量消耗。 路由空洞产生。 贪婪算法。,地理位置路由GERA,2 查询消息在事件区域内传播 1 洪泛机制 2 迭代转发机制,地理位置路由,GEM(graph embedding) 适用于数据中心 存储方式的路由，主要思想是建立一个虚拟极坐标系统，用来表示实际的网络拓扑。网络中的节点形成一个以汇聚节点为根的环树，每个节点用到树根的跳数距离和角度范围表示，节点间的数据

7、路由通过这个环树实现。,地理位置路由GEM,三种数据存储方式 1 本地存储 2 外部存储 3 数据中心存储,地理位置路由GEM,1 虚拟极坐标系统 建立步骤：生成树形结构、反馈子树大小、确定虚拟角度范围。 2 基于虚拟极坐标系统的路由算法,地理位置路由GEM,3 对网络拓扑的变化适应 一致性条件： (1)除了汇聚节点外每个节点只有一个父节点 (2)每个节点跳数值为父节点的跳数值加1 (3)每个节点的角度范围是父节点角度范围的子集 (4)每个节点的子节点角度范围不相交,地理位置路由,边界定位地理路由 基本思想：通过网络中自身位置信息确定一个全局坐标系，然后确定其他节点在这个坐标系的位置，最后根据

8、节点在坐标系中的位置进行数据路由。,地理位置路边界定位地理路由,1 边界节点均为信标节点 2 使用两个信标节点 3 使用一个信标节点,可靠路由协议,主要考虑因素 1 利用节点的冗余性提供多条路径以保证通信可靠性 2 建立可靠性估计机制，从而保证没跳传输的可靠性,基于不相交路径的多路径路由机制,基本思想：首先建立从源节点到汇聚节点的主路径，然后在建立多条备用路径；数据通过主路径进行传输，同时利用备用路径低速传送数据来维护路径的有效性；当主路径失败时，从备用路径中选择次优路径作为新的住路径。 多路径建立方法 不相交路径 缠绕路径,ReInForM路由,基本过程： 数据源节点根据传输的可靠性要求，计算需要传输路径数目的要求；然后，在邻居节点中选择若干节点作为下一跳节点，并给每个节点按照一定比例分配路径，最后数据源节点将分配的路径作为数据报头中的一个字段发给邻居节点。,ReInForM路由协议实现过程,1 计算传