第02章、无线传感器网络路由协议

1、无线传感器网络技术无线传感器网络技术讲义讲义第二章、路由协议2007年8月20日内容提要WSN路由协议概述 WSN路由协议分类 2.1 以数据为中心路由协议2.2 集群结构路由协议 2.3 地理信息路由协议 2.4 QOS 路由协议WSN路由协议最新研究成果 主要参考文献内容提要WSN路由协议概述 WSN路由协议分类 2.1 以数据为中心路由协议2.2 集群结构路由协议 2.3 地理信息路由协议 2.4 QOS 路由协议WSN路由协议最新研究成果 主要参考文献WSN路由协议功能n 定义 WSN路由协议是一套将数据从源节点传输到目的节点的机制。n设计目标满足应用需求低网络开销资源利用的整体有效性

2、网络高吞吐率WSN路由协议特点n特点自组织的网络（随机部署）数据的冗余性（多节点监测同一事件）基于局部拓扑信息（硬件限制）网络功能（数据收集）数据为中心WSN路由协议要求n要求能量高效（协议简单&节省能量&均衡消耗）可扩展性（网络范围&节点密度）鲁棒性（节点变化&拓扑变化）快速收敛性WSN路由协议关键技术考虑网络和节点能量优化（硬件限制）具有高可扩展性 （网络规模&自组织） 适应强网络拓扑变化（节点移动&无线信道）传感器网络路由中使用数据融合技术（数据为中心）传感器网络中流量分布不对称 （数据收集网络&多源单Sink)传感器网络路由协议的挑战自组织布撒（Ad hoc deployment）能量

3、消耗（Energy consumption ）路由精度（Routing accuracy）计算能力（Computation capabilities）通信能力（Communication tolerance）容错能力（Fault tolerance）可扩展性（Scalability）控制负载（Control overhead）内容提要WSN路由协议概述 WSN路由协议分类 2.1 以数据为中心路由协议2.2 集群结构路由协议 2.3 地理信息路由协议 2.4 QOS 路由协议WSN路由协议最新研究成果 主要参考文献WSN路由协议分类 数据为中心路由协议 SPIN (Flooding)，Dire

4、cted Diffusion (Gradient) 集群结构的路由协议 LEACH, TTDD 地理信息路由协议 GPSR, GEAR QOS路由协议 QOS路由协议（详见第十章）路由协议（详见第十章）内容提要WSN路由协议概述 WSN路由协议分类 2.1 以数据为中心路由协议2.2 集群结构路由协议 2.3 地理信息路由协议 2.4 QOS 路由协议WSN路由协议最新研究成果 主要参考文献以数据为中心路由协议SPIN：Sensor Protocol for Information via NegotiationSPINSPIN协议是对Flooding协议的改进。Flooding的缺点：内爆：

5、节点向邻居节点转发数据包，不管其是否收到过相同的重叠：感知节点感知区域有重叠，导致数据冗余SPINn 通过和邻居节点的协商来减少通过和邻居节点的协商来减少Flooding带来的带来的内爆和重叠的影响内爆和重叠的影响n 通过元数据来完成协商过程通过元数据来完成协商过程元数据：一种对源数据的映射，比源数据短避免传输冗余数据n 3步握手协议步握手协议(ADV-REQ-DATA)n SPIN-2在在SPIN-1的基础上加入了能量阈值的基础上加入了能量阈值当一个节点的剩余能量低于能量阈值后，减少其在协议中参与的活动。SPINn协商通过元数据进行协商通过元数据进行元数据描述实数据元数据与时数据一一对应n协

6、议消息协议消息消息广播包：Advertise (ADV)数据请求包：Request (REQ)数据包：Data transfer (DATA)3步握手协议步握手协议AAAAAA节点A有新数据，通过ADV发布新数据信息，使用元数据B节点收到ADV后，发现自己没有该数据，通过REQ向A请求新数据A节点向B节点传送源数据B节点融合新数据，并通过ADV发布新数据消息如果节点ADV中描述的数据的副本就忽略该消息SPIN协议评价n优点部分解决了内爆和重叠问题不需要进行路由维护对网络拓扑变化不敏感，可用于移动WSNn缺点本质上SPIN还是向全网扩散新消息，开销比较大SPIN协议族（协议族（Protocol

7、Family）n SPIN-PPFor networks using point-to-point transmissionmediaIdeal conditions assumed with no packet lossn SPIN-ECSPIN-PP with low energy thresholdn SPIN-BC3-stage handshake protocol for broadcast median SPIN-RLSPIN-BC for Lossy networks数据中心网络和地址中心网络DC，Data-centricAC，Address-centricDC网络可进行数据融合

8、，减少网络中的数据量以数据为中心路由协议Directed DiffusionDirected DiffusionnSink节点查询兴趣消息兴趣消息采用泛洪的方法传播到网络有和兴趣匹配数据的节点发送数据兴趣扩散阶段建立节点到Sink的路径n兴趣的定义：由属性值对组成type = four-legged animal / detect animal locationinterval = 20 ms / send back events every 20 msduration = 10 seconds / . for the next 10 seconds rect = -100, i00, 200

9、, 400 / from sensors within rectangle兴趣和梯度 Sink节点向全网查询兴趣M建立源节点和Sink间路径兴趣在全网中扩散对每一个活动任务，Sink周期进行查询 邻居更新自己的兴趣cach，并且转发 兴趣cach中的条目时间戳：指示接收到相关兴趣消息的最近时间若干梯度域：每个梯度和其邻居节点相关联 每个梯度中含有一个指定的数据传输率持续时间：该兴趣消息的有效期Directed Diffusionn 查询消息的传播建立数据的传输梯度 汇聚节点发送查询消息 兴趣消息：任务性质、数据采集/发送数率、时间戳等 中间节点： 记录 转发 梯度：表示了数据的传输方向路径修复

10、问题n加强路径上的节点可以触发和启动路径的加强过程 新路径C和源节点之间路径断裂DD协议评价n 优点数据中心路由，定义不同任务类型/目标区域消息；路径加强机制可显著提高数据传输的速率；周期性路由：能量的均衡消耗；n 缺点周期性的洪泛机制-能量和时间开销都比较大；节点需要维护一个兴趣消息列表，代价较大；Directed Diffusion Familyn GBR路由(Gradient-Based Routing)协议：梯度域扩展（传感器节点到Sink节点的跳数信息、无线链路评估信息）n EAR(Energy Aware Routing)路由协议建立路由过程中加入能量评估机制；路由路径的能量开销大

11、于某一阈值不采用；n CADR路由(Constrained Anisotropic Diffusion routing)协议兴趣消息往指定方向发送Directed Diffusion Familyn 谣传路由（基于代理(agent)消息的单播随机转发方法）内容提要WSN路由协议概述 WSN路由协议分类 2.1 以数据为中心路由协议2.2 集群结构路由协议 2.3 地理信息路由协议 2.4 QOS 路由协议WSN路由协议最新研究成果 主要参考文献集群结构路由协议LEACH : Low-Energy Adaptive ClusteringHierarchyLEACH算法n 每个节点直接和Sink节

12、点通信：节点能量消耗过大节点密度较大时冲突过大，效率低n LEACH算法：簇头节点作为一定区域所有节点的代理，负责和Sink的通信；非簇头节点可以使用小功率和簇头节点通信；簇头节点可以对所辖区域节点数据进行融合，减少网络中传输的数据；簇头选举算法的设计，要求保证公平性簇头选择算法n 每个传感器节点选择0，1之间的一个随机数，如果选定的值小于某一个阈值，那么这个节点成为簇头节点，计算如下： N表示网络中传感器节点的个数，k为一个网络中的簇头节点数，r为已完成的回合数，G为网络生存期总的回合数。Gn 0)/mod()(如其它情况knrkNknTLEACH算法n 网络按照周期工作，每个周期分为两个阶

13、段：簇头建立阶段： 节点运行算法，确定本次自己是否成为簇头； 簇头节点广播自己成为簇头的事实； 其他非簇头节点按照信号强弱选择应该加入的簇头，并通知该簇头节点； 簇头节点按照TDMA的调度，给依附于他的节点分配时间片；数据传输阶段： 节点在分配给他的时间片上发送数据；LEACH算法评价n优点优化了传输数据所需能量；优化了网络中的数据量；n缺点节点硬件需要支持射频功率自适应调整；无法保证簇头节点能遍及整个网络；LEACH Familyn LEACH-c：簇头由Sink节点指定；通过模拟退火算法选择簇头；n PEGASIS：将网络中所有节点连成一条线；每次只有一个簇头节点负责和Sink的通信，簇头

14、在链上移动；集群结构路由协议TTDD: A Two-tier Data Dissemination Model for Large-scale Wireless Sensor NetworksTTDD传感器节点不移动，Sink节点移动；多Sink；以源节点为中心建立格状网；运用代理，实现对移动Sink的透明传输；Sink通过泛洪查找感兴趣的事件，泛红区域限定在一个网格区间；格状网的建立 源节点B的坐标(x,y)； 网格的边长为 B建立的格状网的交叉点坐标为 B为中心建立网络的转发点选择与交叉点最近的点，如图中黑点 成为转发节点的点启动下一级转发节点的选取过程, 21, 0,)*,*(jijyi

15、x格状网建立时的上下游关系n上游节点转发节点在格状网建立阶段由源节点或者其它转发节点指定，这个指定本转发节点的源节点或者转发节点称为本转发节点的上游节点 n下游节点和上游节点的定义相反查询过程 所有的转发节点都包含有源节点的数据公告消息 Sink通过泛洪方式发起查询请求，查询范围是一个网格区间 匹配节点通过格状网建立时的上下游关系将查询传送到源节点 源节点响应查询，沿查询消息的反向传输路径传送数据对移动Sink的支持n 直接转发节点 第一个响应Sink查询的格状网中的转发节点n 初级代理(PA) Sink节点指定的一个节点，负责接收直接转发节点发送过来的数据n 直接代理(IA) Sink节点移

16、动时动态指定IA，PA将数据传送给IA，由IA将数据提交给Sink。PA和IA可以是同一个节点。当Sink移出距离太远，找不到IA时，Sink重新发起查询过程。TTDD路由协议评价n优点提出了一种新的应用场景 支持多Sink以及Sink移动的网络环境n缺点需要地理位置信息的支持网格大小不容易确定内容提要WSN路由协议概述 WSN路由协议分类 2.1 以数据为中心路由协议2.2 集群结构路由协议 2.3 地理信息路由协议 2.4 QOS 路由协议WSN路由协议最新研究成果 主要参考文献地理位置信息n地理位置信息路由协议要求每个节点知地理位置信息路由协议要求每个节点知道自己在网络中的位置道自己在网

17、络中的位置n下列方法可确定节点位置下列方法可确定节点位置GPS(Global Positioning System)超声波三角定位系统标定标定n用途用途作为其它路由算法的辅助 直接用于路由的计算地理位置信息路由协议GPSR：Greedy Perimeter Stateless RoutingGPSR贪婪算法利用节点的地理位置信息转发节点选取： 选择邻居节点中离数据包目的节点更近的点作为转发节点局部优化问题存在x到D的路径x的邻居w,y离D的距离比x大解决方法：边界转发边界转发n平面图：二维空间结构；平面图中任意两条边都不相交；nGPSR算法中构造平面图的方法是删除网络拓扑图中交叉的边 n算法：

18、RNG(Relative Neighborhood Graph)GG(Gabriel Graph) RNGn 节点u，v之间存在边的条件是对于任意一个节点w，u到v的距离要小于或等于u到w或是v到w的距离的最大值，用下式表示： ),(),(max),(:,wvdwudvudvuwGGn节点u，v之间存在边的条件是在以d(u，v)为直径的圆中没有其它节点，用下式表示： ),(),(),(:,222wvdwudvudvuw边界转发时的右手法则一个数据分组从节点y到达节点x；下一条边的选择： 下一边是以x为定点，沿(x，y)逆时针方向上的第一条边，图中为(x，z)后续各边同样依次法则确定 Facen

19、 平面图的边将整个图分成许多小的互补重叠的有界多边形和一些无界区域，这些有界多边形和无界区域统称为face。其中，有界区域称为内部face，无界区域称为外部face。途中xD通过3个有界face和一个无界face。边界转发 数据包在x点进入边界转发模式，通过face边界向目的节点D转发，这些face都被xD穿越； 转发边的选择采用右手法则，初始边为xD； 数据包在同一个face中转发时采用右手法则，当碰到与xD相交的边时，进行face切换，进入下一个face；GPSR协议评价n优点采用局部最优的贪婪算法，不需要维护网络拓扑，路由开销小；可适用于静态和移动的WSN网络；n缺点需要地理位置信息的支

20、持；需要维护邻居节点位置信息；GPSR FamilynGRA（Geographical Routing Algorithm)：发生局部优化问题时通过泛洪查找到目的节点的路由nf-GEDIR(f表示泛洪)和c-GEDIR ： 发生局部优化问题，采用尽最大努力发送的方式：f-GEDIR：向所有邻节点广播该分组 c-GEDIR：选择部分邻节点转发该分组 收到数据包的节点继续使用GPSR协议转发该数据分组n2-hop GEDIR ：节点保存一跳和两跳范围邻居节点的位置信息 常用的贪婪策略n MFR(Most Forward within Radius)：使到目的节点的跳数最少n NFP(Nearest

21、 with Forward Progress)： 使节点之间干扰最少n CR(Compass Routing) ：减小数据传输范围地理位置信息路由协议GEAR ：Geographic and Energy Aware RoutingGEAR路由协议n应用建立到特定区域的路由查询工作方式n前提 已知目标区域的位置信息节点知道自己位置信息和剩余能量节点间无线链路是对称的GEAR路由过程n分两个阶段：查询消息到达目的区域的路径查询消息在目标区域的传播n选路依据 节点到查询区域通信能量能耗 节点本身的剩余能量 最小代价节点为转发节点GEAR路由过程n查询命令传送到目标区域贪婪算法选择邻居节点到达指定区

22、域的代价 估计代价： F(Ni ,R)=Distance( Ni , R) + (1)Left_Enery(Ni ) 实际代价：F(Ni ,R)=Enery_Cost(Ni ,R)+(1)Left_Enery(Ni ) Ni为有转发需求的节点的邻居节点，R为目标区域的中心位置。当N不知道Ni的实际代价时使用估计代价。 GEAR路由过程n 查询在监测区域内传送：洪泛方式，迭代地理转发n 将目标区域分解为若干子区域、 向子区域的中心位置转发）路由空洞问题n路由空洞邻居节点传输代价都比本地节点大；选择邻居节点中代价最下的作为转发节点；修改本地节点的转发代价； F(N ,R)= F(Nmin,R)+C

23、(N,Nmin) ， C(N,Nmin)表示将数据包从N传送到Nmin的代价 GEAR路由评价n 优点利用了位置信息，避免了查询消息的Flooding；考虑了消耗的能量和节点剩余能量，均衡消息；路径选择可达到局部最优；迭代地理转发对洪泛机制的补充；n 缺点可能出现路由空洞（局部信息）- 两跳信息；不适合在移动WSN使用内容提要WSN路由协议概述 WSN路由协议分类 2.1 以数据为中心路由协议2.2 集群结构路由协议 2.3 地理信息路由协议 2.4 QOS 路由协议WSN路由协议最新研究成果 主要参考文献WSN路由协议最新研究成果n 现阶段WSN路由设计主要关注下面几个方面 提高能量效率，实

24、现网络负载的平衡，延长网络生存时间； 满足各种应用场景的参数指标(也就是QOS)； 实现一定程度的数据安全性。后两条留待后面的章节介绍。WSN路由协议最新研究成果n一些解决办法路由协议专用性设计 跨层设计新技术开发（UWB等）一种平衡网路能量和负载的路由协议Joint Mobility and Routing for Lifetime Elongation in Wireless Sensor Networks一种平衡网路能量和负载的协议n需要解决的问题多源单汇数据流远远大于控制流离汇聚节点近能量消耗快需要解决流量和能量的均衡问题一种平衡网路能量和负载的协议n提出的方法l最优移动策略Sink节

25、点在网络外边界移动，左图为圆形网络模型，灰色区域是Sink节点移动区域。汇聚节点移动B为Sink节点,Rm为其移动圆形轨迹半径，R为网络半径，最好RmR一种平衡网路能量和负载的协议n路由方法mRR最好是取一个和Sink移动区节点数据Sink移动区外节点数据数据沿着以O为中心的环转发，直到该数据包到达OB(B为节点Sink所在的位置)线附近的一个节点，到达该节点后再沿着OB，采用最短路径算法到达Sink节点。直接采用最短路径路由算法到达Sink节点 。一种平衡网路能量和负载的协议n优点 提出了一种新思路，通过Sink移动的方式从一定程度上削弱了网络中能耗和负载不平衡的现象n缺点 大多数应用背景下

26、要求Sink节点固定； 普通节点定位Sink节点的问题不能很好的解决；一种跨层设计路由协议Cross-Layer Scheduling for Power Efficiency in Wireless Sensor Networks一种跨层设计路由协议n网络协议软件设计方法分层设计比较成熟的方法，比如TCP/IP。分层的设计方法使协议设计规范化，但是效率不高。 跨层设计不成熟，设计复杂，但是效率高，系统优化性能强。传输控制层物理层网络层数据链路层应用层一种跨层设计路由协议 方法传感器采样事件(S，Sample)节点接收数据事件(R，Receive)节点发送数据事件(T，Transmit) 每个

27、节点在事件发生时醒来工作，其他时间休眠一种跨层设计路由协议n时间片分配约束时间片的分配保证相邻节点的R与T事件互相配合。时间片调度要避免冲突6号节点接收事件与其邻居节点4和9的发送事件时刻匹配4号节点在发送数据时，其邻居节点2和5都不能接收(会发生隐终端的问题)和发送数据(会引起数据冲突)R与T的匹配自动建立路径一种跨层设计路由协议n优点 无需路由维护，网络开销小； 节点休眠，节省了能量；n缺点 需要比较精确的节点同步； 对拓扑变化敏感，不能快速调整节点的时间片调度；WSN路由协议未来的研究方向传感器网络路由协议未来的研究方向 新型网络结构的提出 节点密集部署及空间多样性的考虑 网内存储及网内

28、处理 时间和位置的同步 自组织与重配置 主动传感器网络内容提要WSN路由协议概述 WSN路由协议分类 2.1 以数据为中心路由协议2.2 集群结构路由协议 2.3 地理信息路由协议 2.4 QOS 路由协议WSN路由协议最新研究成果 主要参考文献主要参考文献1 唐勇, 周明天, 张欣. 无线传感器网络路由协议研究进展. Journal of Software, 2006, 17(3): pp.410-4212 郭午平. 无线传感器网络的研究现状及发展. 中国通信学会信息通信网络技术委员会2005年年会 3 JAMALN.AL-KARAKI, THE HASHEMITE UNIVERSITY A

29、HMED E.KAMAL, IOWA STATE UNIVERSITY. ROUTING TECHNIQUES IN WIRELESS SENSOR NETWORKS:A SURVEY. IEEE Wireless Communications, 2004, 11(6): pp.6-284 高传善, 杨珉, 毛迪林. 无线传感器网络路由协议研究. 世界科技研究与发展, 2005, 27(8): PP.1-85 W.Heinzelman, J.Kulik, and H.Balakrishnan. Adaptive Protocols for Information Dissemination i

30、n Wireless Sensor Networks. In: Proc. 5th ACM/IEEE Mobicom, Seattle, WA, Aug. 1999: pp.174856 S. Hedetniemi and A. Liestman. A Survey of Gossiping and brocadcasting in Communication Networks. IEEE Network, 1988, 18(4): pp. 319-497 Bhaskar Krishnamachari, Deborah Estrin, and Stephen Wicker. Modelling

31、 Data-Centric Routing in Wireless Sensor Networks. Department of Electrical Engineering-Systems University of Southern California Los Angeles, Tech Rep: Computer Engineering Technical ReportCENG 02-148 C. Intanagonwiwat, R. Govindan, and D. Estrin. Directed Diffusion: a Scalable and Robust Communica

32、tion Paradigm for Sensor Networks. In: Proc. ACM Mobi-Com 2000, Boston, MA, 2000: pp. 5667.9 C. Schurgers and M.B. Srivastava. Energy Efficient Routing in Wireless Sensor Networks. MILCOM Proc.Commun for Network-Centric Ops: Creating the Info.Force, McLean VA, 2001, 1(1): pp.357-361主要参考文献10 M. Chu,

33、H. Haussecker, and F. Zhao. Scalable Information Driven Sensor Querying and Routing for Ad Hoc Heterogeneous Sensor Networks. Intl. J. High Perf. Comp. Apps., 2002, 16(3): pp.219-31411 R. C. Shah and J. Rabaey. Energy Aware Routing for Low Energy Ad Hoc Sensor Networks. In: IEEE WCNC, Orlando, FL, 2

34、002: pp.172112 D. Braginsky and D. Estrin. Rumor Routing Algorithm for Sensor Networks. In: Proc.1st Wksp. Sensor Networks and Apps., Atlanta, GA, 2002: pp.22-3113 Wendi Rabiner Heinzelman, Anantha Chandrakasan, and Hari Balakrishnan. Energy-Efficient Communication Protocol for Wireless Microsensor

35、Networks. In: Proceedings of the 33rd Hawaii International Conference on System Sciences, Hawaii, USA, 2000: 14 Wendi Rabiner Heinzelman, Anantha Chandrakasan, and Hari Balakrishnan. An Application-specific protocol architecture for wireless micosensor networks. IEEE Transaction on Wireless Communic

36、ation, 2002, 1(4): pp.660-67015 Lindsey S, Raghavendra CS. PEGASIS: Power-efficient gathering in sensor information systems. In: Proc. of the IEEE Aerospace Conf. Montana: IEEE Aerospace and Electronic Systems Society, 2002: pp.1125-1130.16 A. Manjeshwar and D. P. Agarwal. TEEN: a Routing Protocol f

37、or Enhanced Efficiency in Wireless Sensor Networks. In: 1st Intl. Wksp. on Parallel and Distrib. Comp. Issues in Wireless Networks and Mobile Comp., 2001: pp.2009-201517 A. Manjeshwar and D. P. Agarwal. APTEEN: A Hybrid Protocol for Efficient Routing and Comprehensive Information Retrieval in Wirele

38、ss Sensor Network. In: Proc Intl Parallel and Distrib Proc Symp, Florida, USA, 2002: pp.19520218 H LUO, FAN YE, J CHENG, S LU, L ZHANG. TTDD: A Two-tier Data Dissemination Model for Largescale Wireless Sensor Networks. Wireless Networks, 2005, 11(2): pp.161-175主要参考文献19 Young-Bae Ko and Nitin H. Vaidya. Location-Aided Routing (LAR) in mobile ad hoc networks. ACM/Baltzer Wireless Networks(WINET) Journal, 2000, 6(4): pp.307-32120 Ya Xu，John Heidemann，Deborah Estrin. Geography-informed Energy Conservation for Ad Hoc Routing. In: ACM SIGMOBILE 7/01 Rome, Italy，20