传感网原理及应用—第2讲(路由协议)

1、陈永乐陈永乐计算机科学与技术学院计算机科学与技术学院目录InternetInternet路由机制概述路由机制概述传感器网络的路由概述传感器网络的路由概述典型传感器网络路由协议典型传感器网络路由协议p能量路由p以数据为中心的路由（基于查询的路由）p地理路由p多路径路由(可靠路由)WSNWSN路由协议的最新研究成果路由协议的最新研究成果总结总结 2Internet 路由机制InternetInternet节点的标识节点的标识pIPIP地址（全球或内部唯一；地址含义：国际分配），地址（全球或内部唯一；地址含义：国际分配），如邮政编码；如邮政编码；p域名（如：省域名（如：省. .地区地区. .县县.

2、.乡乡. .村）村）p域名服务器：域名到域名服务器：域名到IPIP地址的解析；地址的解析；IPIP层实现路由机制层实现路由机制p实际是根据目标实际是根据目标IPIP所在的网络所在的网络路由的依据是路由的依据是IPIP地址地址3Internet 路由机制4路由器：实现数据的转发，如邮局；路由器：实现数据的转发，如邮局；Internet 路由机制5路由表和转发过程路由表和转发过程n路由协议形成路由表中的内容；Internet通信模式传统网络的通信模式传统网络的通信模式p单播：点到点通信（主要方式）；单播：点到点通信（主要方式）；l如果一台发送者同时给多个的接收者传输相同的数据，也必须如果一台发送者

3、同时给多个的接收者传输相同的数据，也必须相应的复制多份的相同数据包相应的复制多份的相同数据包p组播：点到一组内的所有节点组播：点到一组内的所有节点 （都有相应的都有相应的IPIP地址）地址）l如果一台发送者同时给多个的接收者传输相同的数据，也只需如果一台发送者同时给多个的接收者传输相同的数据，也只需复制一份的相同数据包复制一份的相同数据包p广播：点到网络内的所有节点广播：点到网络内的所有节点p其他：泛播等（点到一组内的一个节点其他：泛播等（点到一组内的一个节点 ）6单播数据流传播示意图7组播数据流传输示意图8广播数据流传输示意图9目录InternetInternet路由机制概述路由机制概述传感

4、器网络的路由概述传感器网络的路由概述典型传感器网络路由协议典型传感器网络路由协议p能量路由p以数据为中心的路由（基于查询的路由）p地理路由p多路径路由(可靠路由)WSNWSN路由协议的最新研究成果路由协议的最新研究成果总结总结 10传感器网络的通信模式11任意两点的点到点通信任意两点的点到点通信 没有意义没有意义传感器网络的通信模式传感器网络的通信模式传感器网络的通信模式p点 多点（汇聚节点传感器节点）p单播/广播（局部范围）传感器节点的标识传感器节点的标识p节点ID没有位置的含义；p通信关注的是：某个位置上或某种属性相关信息p节点ID：l不求全网唯一，局部唯一；l邻居之间可相互区别；p好处

5、? 不需要；节省能量；12WSN路由协议定义定义pWSN路由协议是一套将数据从源节点传输到目的节点的机制设计目标设计目标p满足应用需求p低网络开销p资源利用的整体有效性p网络高吞吐率13传感器网络的典型应用时间驱动时间驱动p周期性报告（森林中节点定期报告环境参数）14图1 周期报告图2 目标跟踪事件驱动事件驱动p监测（报告失火、动物出现事件）WSN路由协议的特点与需求特点（特点（WhyWhy现有协议不适合？）现有协议不适合？）p能量优先（节点能耗受限）p基于局部拓扑信息（硬件限制）p与应用相关，(不同应用采用不同路由，降低路由复杂度)p以数据为中心要求要求p能量高效（协议简单|节省能量/均衡消

6、耗）p可扩展性 （网络范围|节点密度）p鲁棒性 （节点变化|拓扑变化）p快速收敛性15根据协议的宏观特性，可有多种分类方法：根据协议的宏观特性，可有多种分类方法：p依据网络结构l平面型(flat)和层次型(hierarchical)p依据执行位置l集中式(centralized)和分布式(distributed)p依据路径数目l单路径(single-path)和多路径(multi-path)根据协议的操作，可有多种分类方法：根据协议的操作，可有多种分类方法：p基于局部信息的和基于地理位置的pproactive，reactive，hybrid路由协议分类方法其它辅助描述特性其它辅助描述特性p是否

7、基于协商p是否进行数据融合p是否考虑安全性p是否考虑QoSp是否与上层协议紧耦合p等等路由协议分类的其它考虑目录InternetInternet路由机制概述路由机制概述传感器网络的路由概述传感器网络的路由概述典型传感器网络路由协议典型传感器网络路由协议p能量路由p以数据为中心的路由（基于查询的路由）p地理路由p多路径路由(可靠路由)WSNWSN路由协议的最新研究成果路由协议的最新研究成果总结总结 18能量路由（能量路由（1）19能量路由能量路由p基于节点的可用能量（Power Available）或传输路径上链路的能量需求选择数据的发送路径路径1：汇聚点-A-B-源节点，总PA=4，总a=3；

8、路径2：汇聚点-A-B-C-源节点，总PA=6，总a=6路径3：汇聚点-D-源节点，总PA=3，总a=4；路径4：汇聚点-E-F-源节点，总PA=5，总a=6；能量路由（2） 最大PA路由：选取从数据源到汇聚点所有路径中节点PA之和最大的路径why？ 最小能量路由：选取从数据源到汇聚点所有路径中节点耗能之和最少的路径why？ 最大最小PA节点路由：选取从数据源到汇聚点所有路径中包含最小节点PA最大的路径why？20路1：汇聚点-A-B-源，总PA=4，总a=3；路2：汇聚点-A-B-C-源，总PA=6，总a=6路3：汇聚点-D-源，总PA=3，总a=4；路4：汇聚点-E-F-源，总PA=5，总

9、a=6；能量路由（3）21路径1：汇聚点-A-B-源节点，总PA=4，总a=3；路径2：汇聚点-A-B-C-源节点，总PA=6，总a=6路径3：汇聚点-D-源节点，总PA=3，总a=4；路径4：汇聚点-E-F-源节点，总PA=5，总a=6；最大最大PA路由：路由：路径2最大的，但包含路径1，因不高效而排除，选择路径4； 最最少少消耗消耗能量路由：能量路由：路径1 最大最小PA节点路由：路径3 评价评价：全网信息 理想路由能量路由（4）优点优点p优先考虑WSN最关心：能量；p最大PA路由：能量均衡消耗（路径）；p最小能量路由：能量最小消耗；p最大最小PA节点路由：能量均衡消耗（节点）缺点缺点p需

10、要维护全网的拓扑信息和能量信息；结论结论p理想路由22能量多路径路由（1）目标目标p均衡消耗节点能量增加网络的生存期。方法方法p在源和目的之间建立多条路径，根据能量因素给每条路径赋予被选择使用的概率p在发送数据时，基于概率随机选择其中的一条路径结果结果p没有一条路径一直在传送数据，防止一条路径上节点能量消耗过快23能量路由、多路径路由能量路由、多路径路由能量多路径路由（2）三个阶段：三个阶段：p路径建立阶段：路径建立阶段：根据能量代价建立源节点到目的节点的多条路径，并建立路由表；p数据通信阶段或数据传播阶段：数据通信阶段或数据传播阶段：使用前阶段的信息，转发从源到目的节点的数据。根据早期计算的

11、能量消耗，基于概率地选择数据传播的路径；p路由维护：路由维护：通过不经常的从目的到源节点的洪泛查询，维持所有路径的活动性。路径建立阶段是最关键的一个阶段路径建立阶段是最关键的一个阶段24能量多路径路由（3）路径建立路径建立p目的节点向邻居节点广播路径建立消息，发起路径建立过程p中间节点：距离源节点更近同时距离目的节点更远的节点p路径建立消息从节点Ni发送到节点Nj时p本地路由表:p节点Nj评价：评价：多路经含义多路经含义/ /目的目的25,()(,)jiNNijiCCost NMetric NN, |(min()jijkjNNNNkFTi CC,1/1/jijijkjNNNNNNk FTCPC

12、,()jijkjjNNNNk FTCost NPC目录InternetInternet路由机制概述路由机制概述传感器网络的路由概述传感器网络的路由概述典型传感器网络路由协议典型传感器网络路由协议p能量路由p以数据为中心的路由（基于查询的路由）p地理路由p多路径路由(可靠路由)WSNWSN路由协议的最新研究成果路由协议的最新研究成果总结总结 26两个极端路由机制洪泛（洪泛（FloodingFlooding）机制机制p节点节点产生或收到数据后向所有邻节点广播产生或收到数据后向所有邻节点广播, ,数据包直到数据包直到过期或到达目的地才停止传播过期或到达目的地才停止传播；p缺点缺点l内爆内爆(节点几乎

13、同时从邻节点收到多份相同数据)l交叠交叠(节点先后收到监控同一区域的多个节点发送的几乎相同的数据)l资源利用盲目资源利用盲目(节点不考虑自身资源限制,在任何情况下都转发数据)谣传（谣传（GossipingGossiping）机制）机制p随机选择一个邻结点来发送数据。避免了内爆随机选择一个邻结点来发送数据。避免了内爆, ,但增加但增加了时延。了时延。共同点共同点p不需要维护路由信息不需要维护路由信息, ,也不需要任何算法也不需要任何算法, ,简单但扩展性简单但扩展性很差很差27SPIN路由 Sensor Protocol for Information via NegotiationSensor

14、 Protocol for Information via Negotiation 基于数据、协商的路由基于数据、协商的路由p出发点：针对洪泛算法的缺陷而设计的；传感器在发送数据前先进行协商，仅把数据发送到需要的相邻节点；p命名：以抽象的元数据单元对数据进行命名；p三个消息：ADV、REQ、DATA 三次握手方式 优点优点pADV消息减轻了内爆问题;通过数据命名解决了交叠问题；节点根据自身资源和应用信息决定是否进行ADV通告,避免了资源利用盲目问题；与Flooding和Gossiping协议相比,有效地节约了能量 缺点缺点p当产生或收到数据的节点的所有邻节点都不需要该数据时,将导致数据不能继续

15、转发；虽然减轻了数据内爆,但在较大规模网络中,ADV内爆仍然存在；28定向扩散路由（Direct Diffusion）基于数据的、查询路由基于数据的、查询路由Sink节点：节点：p发送查询消息；p 通过广播的方式；节点：节点：p接收仅广播一次查询消息；网络：网络：p洪泛（Flooding）；29查询：温度查询：温度30度的区域度的区域定向扩散路由（2）查询消息的传播查询消息的传播建立数据的传输梯度建立数据的传输梯度p汇聚节点发送查询消息p兴趣消息：任务性质、数据采集/发送数率、时间戳等p中间节点：l记录（邻居节点和兴趣内容why?） 数据发送的节点梯度 l转发 邻居节点p梯度：表示了数据的传输

16、方向30定向扩散路由（3）匹配数据的传输匹配数据的传输p节点 邻居节点 （发送interest）p多个相同数据在网络中传递；p路径：沿梯度发送给sink节点31定向扩散路由（4）路径增强路径增强形成主路形成主路径径HowHow？p兴趣：建立多条路径p增强：建立主路径l发送数据多少l发送数据稳定性周期性周期性WhyWhy？32定向扩散路由评价优点优点p数据中心路由，定义不同任务类型/目标区域消息；p路径加强机制可显著提高数据传输的速率；p周期性路由：能量的均衡消耗；缺点缺点p周期性的洪泛机制-能量和时间开销都比较大；p节点需要维护一个兴趣消息列表，代价较大；结论结论p以数据为中心，适合大规模量数

17、据的查询采集33Rumor路由34 基本思想基本思想p出发点：一次查询出发点：一次查询DDDD路由开销太大；路由开销太大；p基础理论：欧氏平面图上任意两条曲线交叉几率很大；基础理论：欧氏平面图上任意两条曲线交叉几率很大；p基本过程：事件区域中的传感器节点产生代理（基本过程：事件区域中的传感器节点产生代理（agentagent）消息，代理消）消息，代理消息沿随机路径向外扩散，同时汇聚节点发送查询消息也沿随机路径在网息沿随机路径向外扩散，同时汇聚节点发送查询消息也沿随机路径在网络中传送，当二者相遇时就形成一条节点到事件区域的完整路径。络中传送，当二者相遇时就形成一条节点到事件区域的完整路径。如不如

18、不交叉交叉,sink,sink点可点可floodingflooding查询请求。查询请求。 评价评价p在多在多sinksink点、查询请求数目很大、网络事件很少的情况下点、查询请求数目很大、网络事件很少的情况下,Rumor,Rumor协议较协议较为有效为有效. .但如果事件非常多但如果事件非常多, ,维护事件表和收发维护事件表和收发AgentAgent带来的开销会很大。带来的开销会很大。 新的路由新的路由目录InternetInternet路由机制概述路由机制概述传感器网络的路由概述传感器网络的路由概述典型传感器网络路由协议典型传感器网络路由协议p能量路由p以数据为中心的路由（基于查询的路由）

19、p地理路由p多路径路由(可靠路由)WSNWSN路由协议的最新研究成果路由协议的最新研究成果总结总结 35GPSR路由 Greedy Perimeter Stateless RoutingGreedy Perimeter Stateless Routing 基于地理位置的路由基于地理位置的路由p已知：每个传感器节点的位置和sink位置；p基础思想：各节点利用贪心算法尽量沿直线转发数据.产生或收到数据的节点向以欧氏距离计算最靠近目的节点的邻节点转发数据 路由空洞：路由空洞：p由于数据会到达没有比该节点更接近目的点的区域(称为空洞),导致数据无法传输；p右手规则：空洞周围的节点探测到,并利用右手法则

20、沿空洞周围传输来解决此问题 评价评价p在节点中建立、维护、存储路由表,只依赖直接邻节点进行路由选择,几乎是一个无状态的协议36地理路由: GEAR路由（1）应用应用p到特定区域的路由前提前提p已知目标区域的位置信息p节点知道自己位置信息和剩余能量p节点间无线链路是对称的37对特定区域的查询Geographical and energy aware routing(GEAR)GEAR路由的基本思想两两步步路由路由将查询命令传输到查询区域查询区域内传输到所有节点选路依据选路依据p节点到查询区域通信能量能耗p节点本身的剩余能量。38(, )_(, )(1)_()F N REneryCost N RL

21、eftEnery NGEAR路由过程查询命令传送到目标区域查询命令传送到目标区域p估计代价代替实际代价p节点到达指定区域的代价p贪婪算法选择最小代价邻居数据传输数据传输p数据捎带技术l捎带每跳节点到达时间区域的实际能耗值p实际代价39(, )(, )(1)_()F N RDistance N RLeftEnery N(, )_(, )(1)_()F N REneryCost N RLeftEnery N查询命令的路由GEAR路由：事件区域内查询传播查询在监测区域内传送查询在监测区域内传送p洪泛方式p迭代地理转发l将目标区域分解为若干子区域l向子区域的中心位置转发实际采用方式实际采用方式p当区域

22、内节点数据较少时，采用洪泛方式p当区域内节点数目较多时，采用迭代转发p判断条件：中心节点邻居数目阀值GEAR路由：路由空洞问题路由空洞路由空洞p贪婪算法（局部信息）l产生路由空洞p解决办法：从终止节点2选择最小代价邻居节点4节点2的代价变为节点4的代价+2到4的通信能耗代价当1号节点再发送查询时，会直接选择低代价的4号41GEAR路由评价优点优点p利用了位置信息，避免了查询消息的Flooding；p考虑了消耗的能量和节点剩余能量，均衡能耗；p路径选择可达到局部最优；p迭代地理转发对洪泛机制的补充；缺点缺点p需要提前预知所有节点位置p可能出现路由空洞（局部信息）- 两跳信息；结论结论p适合移动性

23、不强的应用；目录InternetInternet路由机制概述路由机制概述传感器网络的路由概述传感器网络的路由概述典型传感器网络路由协议典型传感器网络路由协议p能量路由p以数据为中心的路由（基于查询的路由）p地理路由p多路径路由(可靠路由)WSNWSN路由协议的最新研究成果路由协议的最新研究成果总结总结 43多路径路由多路径路由建立基础建立基础p节点数量多；使用目的使用目的p提高数据传输的可靠性（同时传送多个路径）p实现网络负载平衡（概率选择一条路径）使用方式使用方式p在多条路径上传送相同的数据；p在多条路径上选择一条路径，传送一份数据；44相交和不相交多路径路由（相交和不相交多路径路由（1）思

24、想思想p主动建立一条主路径和多条备用路径（避免洪泛维护路径）；p多条路径可以同时使用，也可使用一条；p仅使用一条：lSink节点决定哪一条路径；（不相交多路径）l每个节点决定下一跳节点；（相交多路径）多路径的种类多路径的种类p相交多路径p不相交多路径45多路径路由多路径路由-不相交多路径（不相交多路径（2）不相交多路径不相交多路径p主路径：DD方式p次路径：增强消息 -应答消息p从汇聚节点开始46多路径路由多路径路由-缠绕多路径（缠绕多路径（3）目的目的p克服主路径上单个节点失败问题；缠绕路径缠绕路径p对于主路径上的任意一个节点，在网络不包括该节点时，从源节点到目的节点的最优备用路径；缠绕多路

25、径缠绕多路径p主路径上每个节点都有对应的缠绕路径，这些缠绕路径构成一组备用路径，称为缠绕多路径；47多路径路由多路径路由-缠绕多路径（缠绕多路径（4）缠绕多路径形成过程缠绕多路径形成过程p主路径上每个节点，假设它的下一跳节点失效，形成最优路径，直到节点在主路经上为止；p如果最终也不能到达主路径？48相交相交/不相交多路径路由不相交多路径路由-评价评价优点优点p主动建立备用路径；p失效时及时更新，或随机选择一条可用路径；p在可靠性、能量均衡性和实时性等方面提供支持p避免了洪泛路径维护增加增加p存储开销p计算开销49可靠路由可靠路由:ReInform路由（路由（1）目标目标p多路径路由机制p满足对

26、可靠性的定量要求p综合考虑可靠性需求、信道质量以及传感器节点到汇聚节点的距离等因素p适用于数据采集型应用 50可靠路由可靠路由:ReInform路由（路由（2）路由过程路由过程p源节点发起路径建立过程p源节点由可靠性要求和信道质量确定路径数p源节点在邻居节点中分配路径p邻居节点按同样策略重新计算路径数l迭代过程，直到目的结点为止51可靠路由可靠路由:ReInform路由（路由（3）源节点确定路径数源节点确定路径数p数据源节点发送数据分组到达汇聚节点的可靠性参数rsp信道差错率es , hs为源节点到汇聚节点跳数p源节点根据下式计算需要的路径数(1)( , ,)(1 (1) )ssssshslo

27、grP r e hloge52可靠路由可靠路由:ReInform路由（路由（4）在邻居节点中分配路径在邻居节点中分配路径p将邻居节点分为H0，H-，H+三类p在H-中选择一个默认下一跳节点，分配给该节点（1- es ）条路径p剩余路径按以下比例分配021(1)HHHssPPPeen邻居节点按照和得到的路径数相同的概率转发数据包53可靠路由可靠路由:ReInform路由（路由（5）节点转发数据包节点转发数据包p按照和源节点相同的策略计算路径数并在邻居节点中分配路径p每一跳通信都保证了源节点要求的可靠性评价评价p保证了节点间数据传输的可靠性p考虑到信道质量因素54目录InternetInterne

28、t路由机制概述路由机制概述传感器网络的路由概述传感器网络的路由概述典型传感器网络路由协议典型传感器网络路由协议p能量路由p以数据为中心的路由（基于查询的路由）p地理路由p多路径路由(可靠路由)WSNWSN路由协议的最新研究成果路由协议的最新研究成果总结总结 55分簇路由 优点优点p成员节点大部分时间可以关闭通信模块,由簇头构成一个更上一层的连通网络来负责数据的长距离路由转发.这样既保证了原有覆盖范围内的数据通信,也在很大程度上节省了网络能量; p簇头融合了成员节点的数据之后再进行转发,减少了数据通信量,从而节省了网络能量; ; p成员节点的功能比较简单,无须维护复杂的路由信息.这大大减少了网络

29、中路由控制信息的数量,减少了通信量; ; p分簇拓扑结构便于管理,有利于分布式算法的应用,可以对系统变化作出快速反应,具有较好的可扩展性,适合大规模网络; ; p与平面路由相比,更容易克服传感器节点移动带来的问题. 56分簇路由过程过程p簇头选举（等概率）p簇的数据传输 分层和数据融合分层和数据融合 思想思想p相邻节点周期性动态地自动形成簇并基于概率产生簇首；簇内节点把数据发给簇首，簇首进行数据融合后把结果发送道到目的节点 p节点通过轮流担任簇首使网络能量的均衡消耗 LEACH路由58 层次的、基于数据的路由层次的、基于数据的路由 目标目标p在反应网络中对LEACH改进，通过过滤减少通信数据量 特点特点p簇首广播数据采集的硬阈值和软阈值p当采集的数据第一次大于硬阈值时，节点记录数据并发送给簇首p此簇首周期内的后续采样值，只有在大