传感器路由覆盖与拓扑控制技术

Agenda12无线传感器网络拓扑控制技术无线传感器网络覆盖技术3无线传感器网络路由无线传感器网络路由1.11.2路由协议设计的关键问题简单的无结构路由协议1.31.41.5树类路由协议地理路由协议无线传感器网络路由协议比较1.6无线传感器网络路由概述11.1无线传感器网络路由概述21.1无线传感器网络路由概述31.1无线传感器网络路由概述41.1无线传感器网络路由概述在无线传感器网络的应用当中，终端用户往往只关心所采集的数据而不关心这些数据具体是从哪一个节点传送的，用户只需向网络发出一条查询命令，网络就将所查询的数据回馈给用户。目的在于解决如何节省网络节点的能量消耗，均摊网络能量，延长网络寿命。它将整个网络的节点法划分为多种类型，同类节点间可以交换数据。在路由选择中，低一级节点将数据传输至簇头节点（高一级节点），簇头节点进行数据融合，减少了冗余数据在网络中的传输，并且由于缩小了节点下一跳的选择范围，加快了路由算法的收敛速度，节省了能量。网络中的节点利用GPS设备、三角定位系统等获知自身所处的地理坐标，在进行路由选择时，合理利用这些地理信息，从而将数据分组转发给一个特定区域，而不是整个网络，减少网络能耗。在网络数据传输过程当中，通过增加传输的路径数可以增加网络的等效带宽，并且在相同数据量的前提下，能够缩短传输时延。对无线传感器网络，多路径路由协议能够提高网络的可靠性，并且可以将传输能耗分摊在更多的节点上。无线传感器网络路由路由协议设计的关键问题1.21.1无线传感器网络路由概述简单的无结构路由协议1.31.41.5树类路由协议地理路由协议无线传感器网络路由协议比较1.62路由协议设计的关键问题2路由协议设计的关键问题2路由协议设计的关键问题2路由协议设计的关键问题2路由协议设计的关键问题2路由协议设计的关键问题2路由协议设计的关键问题无线传感器网络路由简单的无结构路由协议1.31.1无线传感器网络路由概述路由协议设计的关键问题1.21.41.5树类路由协议地理路由协议无线传感器网络路由协议比较1.6简单的无结构路由协议：Flooding和Gossiping路由协议Flooding路由协议ABCDEFGHPPPPPPP以此类推，直到p到大汇聚节点D或到达TTL源节点A需要将数据包p发送至汇聚节点D节点A首先将p的副本广播，则其邻居节点B接收到p副本节点B直接将p副本通过广播的形式转发给E、F、CFlooding路由协议优缺点Flooding路由协议优缺点Gossiping路由协议Ds初始设置每个数据包TTL=6此时TTL=0，资料包在此处丢失，不再往下传至D假设任意两节点间的端到端时延相同，节点间连接表示两节点间可通信。从源节点S到汇聚节点D时延最短的路径一共要经过6跳。简单的无结构路由协议：SPIN路由协议简单的无结构路由协议：SPIN路由协议154320DATAADVADVADVADV0号节点向1号节点发送传感数据当1号节点接收到数据后，向其周边邻居节点广播ADV数据包，通知邻居节点自己有传感数据需要转发当1号节点的邻居节点接收到ADV数据包后，根据自己的情况，自主选择接受数据DATA与否，节点3与节点5选择接收数据DATA，因此其向1号节点发送REQ数据包当1号节点接收到节点3和节点5发送的REQ，即立刻将DATA发送至这两个节点REQREQDATADATASPIN路由协议转发过程简单的无结构路由协议：定向扩散路由协议兴趣消息扩散：DFBACE汇聚节点节点B收到节点A发送过来的消息之后的操作流程如下：判断是否与刚才转发给D的消息相同，如果是则丢弃该“兴趣”；否则检查本地兴趣列表，如果没有相同“兴趣”，则增加新表项并转发“兴趣”，否则判断表项中是否有邻居节点等于兴趣消息数据包中的发送节点，如果是则更新最新时间戳，否则添加新邻居节点，转发“兴趣”。以A、B、D演示兴趣消息的扩散过程汇聚节点向传感器网络内节点A、B广播兴趣消息节点A、B接收到兴趣消息，然后，节点A向节点B、D广播接收到的消息，同时节点B向节点D广播接收到的消息。简单的无结构路由协议：谣传路由协议汇聚节点相交节点传感器节点传感器节点监测区域谣传路由协议示例无线传感器网络路由树类路由协议1.41.1无线传感器网络路由概述路由协议设计的关键问题1.21.31.5简单的无结构路由协议地理路由协议无线传感器网络路由协议比较1.6高弹性多径路由协议树类路由协议：SAR路由协议树类路由协议：SAR路由协议当构建树完成后，大多数节点都将成为所建树的一部分，并且由于汇聚节点周围的邻居节点都是这些树的树根节点，因此所形成的多条路径针对汇聚节点周围的邻居节点是不相交的，如图所示.这样有效避免了汇聚节点周围节点能量消耗过快的问题。树类路由协议：SAR路由协议树类路由协议：LEACHLEACH路由拓扑按照规定选取合适的簇头当网络中部分节点选择自己为簇头节点后,则发布消息通知网络中其它节点自己是簇头节点。每个非簇头节点根据自己与簇头之间的距离来选择加入哪个簇，并通知该簇头，簇头收到消息后将该节点加入到簇成员表中。非簇头节点在簇内指定的持续时间内发送一次数据，在没有数据发送时，将进入休眠状态以节省能量，而簇头节点保持工作状态以接收数据。簇头收到所有的簇内数据之后，就执行数据融合功能，然后将处理后的数据传输到Sink节点。Sink节点树类路由协议：PEGASIS及Hierarchical-PEGASIS路由树类路由协议：TEEN路由树类路由协议：APTEEN路由无线传感器网络路由地理路由协议1.51.1无线传感器网络路由概述路由协议设计的关键问题1.21.31.4简单的无结构路由协议树类路由协议无线传感器网络路由协议比较1.6基于局部地理拓扑的单播路由协议基于局部地理拓扑的单播路由协议基于局部地理拓扑的单播路由协议设网络中源节点为S，汇聚节点为BS，S的邻居节点为{s1,s2,‥‥sn}，则S在选择路径时，将整个路径拆分为两个部分：一是从S到其邻居节点的单跳路径，二是从其某邻居节点到汇聚节点的单跳或多跳路径，实线表示源节点到邻居节点的路径，虚线表示从邻居节点到汇聚节点的路径。基于局部地理拓扑的单播路由协议对于任意一条从源节点S到汇聚节点BS的路径，其能量消耗可以用两端路径消耗能量之和u(.)+v(.)表示，其中u(.)表示第一段路径的能量消耗，v(.)表示第二段路径的能量消耗，则寻找的路径应满足min{u(.)+v(.)}，即总能量消耗最小。对于u(.)，由于节点知道其邻居节点的地理坐标，因此能够较为容易且准确地计算出通信代价，但是v(.)并不能准确计算出，因此需要估计出来，PALR采取的办法是利用最小理想能耗来计算u(.)+v(.)。每个节点在选择下一跳时，都选出使得u(.)+v(.)最小的下一跳节点。基于地理位置信息改善的多播路由协议基于地理位置信息的多播协议LBM是在保证多播精确度的前提下，利用地理位置信息，进行有目的的广播数据包转发，从而降低整个网络的通信能耗。LBM利用多播目的节点的地理位置信息，定义了转发区域，只有在转发区域内的节点才会转发多播数据包。通常，转发域主要有以下3种类型:（1）静态转发域静态转发域是通过将目标域与源节点限制在一定范围空间中，从而将节点的数据转发范围缩小，有效降低广播的通信量。基于地理位置信息改善的多播路由协议（2）自适应转发域自适应转发域是指转发域会随着数据包的不断转发进行相应的变化。通过自适应将转发区域根据当前数据发送节点进行调整，可以进一步提高网络数据通信效率，避免冗余数据通信，但是，由于节点每一次收到新数据时都需要计算自适应转发域的大小，增加了个别节点的计算复杂性程度。（3）基于前进距离的非显示转发域基于前进距离的非显示转发域不像前面两种转发域那样具有一种范围较为准确、形状相对规整的区域，而是一种根据每个节点自身计算值，决定是否将数据包向前转发，即这个转发区域是时刻在变的且没有固定形状。栅格划分：边长的选择d是两节点之间的通信距离。任意两个相邻的栅格之间，若要使得在两栅格中任意地理位置的两簇头都能够正常通信，则边长r与通信半径d满足：基于地理栅格的分层网络路由协议1234001235dr2222rrd整个网络划分成一个个正方形的小栅格，节点通过每个栅格内的簇头节点构成网络的骨干网络完成数据通信。每个栅格都有自己的编号，栅格内的所有节点都共享这个栅格编号，栅格内的簇头节点负责栅格中分组转发。栅格簇头节点的选择原则是按照停留在栅格内时间最长的节点作为簇头节点，一旦某节点担当了簇头节点，只有其离开该栅格时才会进行新一轮的簇头选择。GRID路由协议主要包括3个阶段：栅格划分路由建立路由维护节点以自己和归属栅格中心点的距离设定定时器，定时器到时，选举自己成为簇头，并周期性地发送通告消息，其他节点接收到消息后，则加入该栅格。如果同时有多个节点竞争簇头，在收到其他簇头的通告消息后，距离栅格中心较远的簇头放弃簇头地位，保证栅格中的簇头个数不超过一个。节点无线传感器网络路由无线传感器网络路由协议比较1.61.1无线传感器网络路由概述路由协议设计的关键问题1.21.31.4简单的无结构路由协议树类路由协议地理路由协议1.5路由协议单路径多路径平面结构树状结构混合路由基于地理位置基于数据融合Flooding√√可选Gossiping√√可能SPIN可能可能√√DD√√√Rumor√√√√高弹性多路径√√可能可能SAR√√LEACH√√可能√PEGASIS√√√H-PEGASIS√√√TEEN√√√APTEEN√√√PALR√√√LBM√√√√GRID√√√√√基于地理栅格的分层网络路由协议路由、覆盖与拓扑技术无线传感器网络拓扑控制技术2无线传感器网络路由1无线传感器网络覆盖技术3无线传感器网络拓扑控制技术拓扑控制技术概述2.12.2拓扑控制意义拓扑控制的设计目标2.32.42.5功率控制技术典型的层次型拓扑控制方法拓扑控制中的休眠调度技术2.6拓扑控制技术是无线传感器网络中的基本问题。动态变化的拓扑结构是无线传感器网络最大特点之一，因此拓扑控制策略在无线传感器网络中有着重要的意义。目前，在网络协议分层中没有明确的层次对应拓扑控制机制，但大多数的拓扑算法是部署于介质访问控制层（MAC）和路由层（Routing）之间，它为路由层提供足够的路由更新信息，反之，路由表的变化也反作用于拓扑控制机制，MAC层可以提供给拓扑控制算法邻居发现等消息。拓扑控制技术概述路由层拓扑管理/控制MAC层拓扑控制技术概述向上提供信息向上提供信息触发算法运行触发算法运行无线传感器网络拓扑控制技术拓扑控制意义2.22.1拓扑控制技术概述拓扑控制的设计目标2.32.42.5功率控制技术典型的层次型拓扑控制方法拓扑控制中的休眠调度技术2.6拓扑控制的意义①影响整个网络的生存时间②减小节点间通信干扰，提高网络通信效率③为路由协议、时间同步提供基础④影响数据融合⑤弥补节点失效的影响无线传感器网络拓扑控制技术拓扑控制的设计目标2.32.1拓扑控制技术概述拓扑控意义2.22.42.5功率控制技术典型的层次型拓扑控制方法拓扑控制中的休眠调度技术2.6为了实现传感器节点间的相互通信,生成的拓扑必须保证连通性,即从任何一个节点都可以发送消息到另外一个节点。连通性是任何无线传感器网络拓扑控制算法都必须保证的一个重要性质。覆盖可以看成是对传感器网络服务质量的度量。在覆盖问题中，最重要的因素是网络对物理世界的感知能力。生成的拓扑必须保证足够大的覆盖度，即覆盖面积足够大的监视区域。根据文献，衡量全网覆盖情况有一个量化指标——平均每个节点的覆盖率c（%）：在无线传感器网络中，一般情况下是不设置认证中心的，传感器节点只能依据自身从网络中收集的信息做出决策。另外，任何一种涉及节点间同步的通信协议都有建立通信的开销。显然，若节点能够了解全局拓扑和传感器网络中所有节点的能量，就能做出最优的决策；若不计同步消息的开销，得到的就是最优的性能。但是，若所有节点都要了解全局信息，则同步消息产生的开销要多于数据消息，这