第九章、服务质量保证

《无线传感器网络技术》第九章、服务质量保证内容提要1.无线传感器网络服务质量概述2.无线传感器网络感知QoS研究3.无线传感器网络传输QoS研究4.参考文献内容提要1.无线传感器网络服务质量概述2.无线传感器网络感知QoS研究3.无线传感器网络传输QoS研究4.参考文献无线传感器网络服务质量(QoS)概述•服务质量（QoS）背景与概述服务质量(QoS)定义服务质量(QoS)支持机制•无线传感器网络QoS研究服务质量（QoS）背景与概述图10-1简单QoS模型网络服务质量指标•可用性：当用户需要时网络即能开始工作的时间百分比。•吞吐量：一定时间段内对网络流量的度量。•时延变化：同一业务流中不同分组所呈现的时延不同。•丢包率：是指网络在传输过程中数据包丢失的比率。服务质量(QoS)支持机制•Int-serv集成业务•Diff-serv区分业务•MPLS多协议标签交换无线传感器网络(QoS)研究无线传感器网络自身特点使得传统网络的QoS支持机制不适用：•节点资源非常有限•负载不均衡•大量冗余节点•网络异构图10-2无线传感器网络参考体系结构CommunicationProtocolStackPhysicalLayer(Sensing,Processing&CommunicationCapabilities)MACLayerConnectivityMaintenanceNetworkLayerTransportLayerDataManagementIn-NetworkDataProcessingSensorNetworkApplicationsLocationServiceTimeServiceCoverageMaintenanceSensorNetworkSpecificServicesHybridOn-demandEvent-DrivenContinuousDataPlacement&Discovery内容提要1.无线传感器网络服务质量概述2.无线传感器网络感知QoS研究3.无线传感器网络传输QoS研究4.参考文献无线传感器网络覆盖算法设计方式和目标•节点部署方式•网络节能•传感与通信距离•网络可扩展无线传感器网络覆盖算法分类•节点部署方式分类确定性覆盖随机覆盖•覆盖目标分类区域覆盖点覆盖栅栏覆盖图10-4区域覆盖、点覆盖与栅栏覆盖区域覆盖控制算法--轮换活跃/休眠节点的覆盖协议需要解决的问题：•（1）网络中每一个节点如何判断自应该处于活动还是休眠状态；•（2）网络中节点如何进行状态转换。轮换活跃/休眠节点的覆盖协议--节点覆盖休眠准则图10-5节点覆盖图轮换活跃/休眠节点的覆盖协议--节点调度机制节点调度机制采用周期轮换工作方法，每个周期包括：•self-scheduling阶段：每个节点根据节点覆盖休眠准则，来判断自己是否进入休眠状态。•sensing阶段：执行传感操作轮换活跃/休眠节点的覆盖协议--邻居信息获取•各节点在每一轮开始时向传感半径内邻居节点广播位置通告消息PAM•其中包括节点ID和位置(若传感半径不同则包括发送节点传感半径)。轮换活跃/休眠节点的覆盖协议--退避自调度•在判断节点是否可以休眠时，如果相邻节点同时检查到自身的传感任务可由对方完成并同时进入“休眠状态”，就会出现如图所示的“盲点”。abcdefabcd图10-6网络中出现的盲点连通传感器覆盖在选取网络中哪些节点处于活动状态时，需要考虑满足以下两个因素：(1)覆盖：活动节点集合的传感区域能够覆盖整个监测区域；(2)连通：网络活动节点集合中任意两个节点都能够互相通信，使得传感节点采集的数据能够被发回基站。连通传感器覆盖–OGDC算法•定理1：假设在任何有限区域中，节点的数目有限。则保证区域被节点全覆盖即网络全连通的充要条件是节点通信半径大于两倍的传感半径。•定理2：假设传感节点的传感区域是以节点为中心的圆形区域，该区域相对待监测区域小很多。多个传感区域在其中相互相交。如果该区域中所有的交叉点都被覆盖，则该待监测区域也被完全覆盖。•定理3：如果所有传感节点的传感半径相等，并且能够完全覆盖监控区域。减少网络中活动节点个数等效于减小所有节点传感覆盖区域的重叠。栅栏覆盖控制算法—最坏与最佳情况覆盖•最坏覆盖是指如何在网络中找到一条路径，使得沿该路径前进的目标被网络中节点发现的概率最小。该路径称为最大突破路径(maximalbreachpath)，即最大化该路径上点到周围最近传感器的最小距离。•最佳覆盖是指网络中找到一条路径，使得沿该路径前进的目标被网络中节点发现的概率最大。该路径称为最大支撑路径(maximalsupportpath)，即最小化路径上的点到周围最近传感器的最大距离。最坏覆盖与最大突破路径(1)基于各节点的位置产生网络Voronoi图;(2)为Voronoi图中每一条边界赋一个权值。该值表示这条边界到离他最近的传感器节点的距离;(3)利用二分查找法和宽度优先查找算法来获取最大突破路径。图10-7最大突破路径Voronoi图(c)(d)(a)(b)最坏覆盖与最大突破路径最佳覆盖与最大支撑路径•以Delaunay三角取代Voronoi图作为几何结构。•图中每条边的权值算法变为计算该边到周围最近传感器节点的最大距离。•查找参数由突破权值变为支撑权值，查找网络中支撑权值最小的边图10-8传感器网络Delaunay三角以及最大支撑路径最佳覆盖与最大支撑路径暴露穿越暴露穿越问题(Exposure)：即观察传感区域内目标的平均期待能力，或一个传感函数的积分，该积分值依赖于目标移动原点至终点的路径到传感节点的距离。暴露穿越算法•将连续问题域转化为离散域•应用图理论抽象•利用Dijkstra的单源最短路径算法(Single-Source-Shortest-Pathalgorithm)图10-9全节点强度模型下所获得的最小暴露路径。网格精度区别：n=8,m=1(左)；n=16,m=2(中)；n=32,m=8(右)。暴露穿越算法图10-16最近节点全节点强度模型下所获得的最小暴露路径。网格精度区别：n=8,m=1(左)；n=16,m=2(中)；n=32,m=8(右)。暴露穿越算法内容提要1.无线传感器网络服务质量概述2.无线传感器网络感知QoS研究3.无线传感器网络传输QoS研究4.参考文献无线传感器网络服务区分参数•数据包抵达概率(可靠性)：高优先级的数据包传送至基站节点的概率更高。•时延：高优先级的数据包抵达基站节点的时延要少于低优先级数据包。可靠数据传输造成数据包丢失的原因主要有三个方面：•无线传感器网络所使用的无线信道较之有线链路有更大的不稳定性以及更高的误码率，•很容易受到周围环境噪声的影响造成数据包的丢失。另外在无线传感器网络中，传感器节点的布撒密度非常高，不同节点在发送数据时极易发生信道竞争冲突以及碰撞造成数据包丢失。•当无线传感器网络中发生拥塞时，拥塞节点缓冲区溢出造成数据包丢失。接收节点因为数据包到达过快来不及处理造成数据包丢失。差错避免可靠传输•ACK确认重传机制•数据包冗余传输机制•多路径传输机制•FEC前向纠错码机制单分组传递：ReInForm路由•ReInForm方法是基于在多条路径上发送数据包的多个拷贝来提高数据包传输可靠性。•从数据源节点开始，根据数据传输可靠性、信道质量以及传感器节点到汇聚节点的跳数，确定需要的传输路径数目，以及下一跳节点数目和相应的节点。•邻居节点在接收到数据源节点的数据后，将自己视作数据源节点，重复上述数据源节点的选路过程。实现满足可靠要求的数据传输。图10-10ReInform所需传送概率为70%时数据转发举例。(A)图是源节点在链路差错率为0时传递1个数据包；(B)图是源节点在链路差错率为0时传递10个数据包；(C)是源节点在链路差错率为30%时传递1个数据包(D)是源节点在链路差错率为30%时发送10个单分组图10-11洪泛、单路径转发以及40%、70%可靠性要求的多路径转发在链路出错率增加时所能保证的可靠性比较图10-12洪泛、单路径转发以及40%、70%可靠性要求的多路径转发在链路出错率增加时为保证可靠性所引发的开销数据块传输:RMST•无线传感器网络中，有时需要传输大量的数据。比如在传送图像、声音等数据时，或者当网络需要重新配置，基站将新的代码发送至节点。•相对于单数据包的可靠性传输，保证数据块传输的可靠性机制有很大的不同。数据块传输:RMST•FredStann等人认为在无线传感器网络中，无线链路不稳定及易受干扰的特点是造成网络传输不可靠的主要原因.•除了在物理层实现高效的纠错码之外，如何在MAC层、传输层以及应用层提供可靠性是实现可靠传输的重要保证。•在MAC层实现可靠性保证的重要性体现在，它除了能为传输层提供跳段之间的错误恢复之外，还是实现路由发现及维持的保证。数据块传输:RMST图10-13每跳链路出错率为10%，数据传输40跳时，传输成功概率数据块传输:RMST图10-14数据传输6跳时，传输成功概率比较数据块传输:RMST•802.11中提供了数据包分片与重组的方法，但是并没有提供传输可靠性保证。•而传统有线网络中的传输层TCP协议提供的传输可靠保证主要是为解决网络拥塞问题而提出的，并不适用于无线网络。•RMST提出了两种传输层可靠性保证方法:端到端选择请求NACK和跳段之间选择请求NACK。数据块传输:RMST端到端选择请求NACK是当基站节点发现接收的数据包有丢失或损坏时，沿着基站到源节点的反向增强路径发送重传请求。当重传请求到达源节点后，源节点将重传所需数据。端到端选择请求NACK方法只需在基站和源节点缓存数据，中间节点无需缓存数据。跳段选择请求NACK方法是在路由路径上的每个节点都缓存数据，当节点发现有数据包丢或损坏时直接向其上一跳节点发送重传请求。拥塞控制•无线传感器网络大部分时间都处于零负载或轻负载，只有在异常事件发生时，网络中才会突发性的产生较大的数据量。这些数据非常重要，需要在不影响系统性能的前提下可靠的传送给基站。但是这种突发性的大数据量传输很容易导网络不同程度拥塞的发生。•网络吞吐量随源速率的增加而减小.•节点数量越大，实际吞吐量减少的越大.CODA拥塞控制方案拥塞场景:(1)节点密集分布的网络中，当有异常事件发生时，源节点会突发性产生大量数据。在源节点附近(几跳范围内)形成持续拥塞区域。(2)在节点分布稀疏并且源节点数据发送速率较低的网络中，不会在源节点附近产生持续的拥塞，而可能在远离源节点的网络区域中任意位置产生短暂的拥塞。(3)在节点分布稀疏并且源节点数据发送速率较高的网络中，有可能在网络区域的任意位置发生短暂或持续的拥塞。CODA拥塞控制方案1.基于接收者的拥塞检测；2.开环跳段反向压力信标机制(open-loophop-by-hopbackpressure)；3.闭环多源调整机制(closed-loopmulti-sourceregulation)。CODA拥塞控制方案--拥塞检测•CODA将节点缓冲区管理方法与链路负载监测方法二者相结合，提出了一个能量高效基于接收者的拥塞检测方法。•在CODA中，只有当节点缓冲区队列不为空时，才启动链路负载监测。当节点缓冲区队列为空时，表明没有拥塞发生，链路负载监测将关闭。•由于CSMA在发送数据前需要监听信道判断信道是否空闲，所以将链路负载监测放在该段时间一起进行将不会带来任何额外的开销。CODA拥塞控制方案--开环跳段反向压力信标机制•检测到网络发生拥塞时，节点将向邻居节点广播一个反向压力信标，同时采用相应的数据包丢弃策略或调整数据发送速率来防止拥塞的进一步传播。•当上游节点接收到反向压力信标后，它将根据局部拥塞策略选择直接丢弃到来的数据包以防止缓冲区溢出，而不继续传送反向压力信标。•如果节点当前的缓冲区溢出，则选择向上游节点继续传送该信标。CODA拥塞控制方案--闭环多源调整机制•CODA中提出的闭环多源调整机制，能够在无线传感器网络中发生持续拥塞时，通过基站节点对源节点进行拥塞控制。•当源