无线传感器网络 第10章 服务质量

1、无线传感器网络技术无线传感器网络技术讲义讲义第九章、服务质量保证内容提要1.无线传感器网络服务质量概述 2.无线传感器网络感知QoS研究3.无线传感器网络传输QoS研究4.参考文献内容提要1.无线传感器网络服务质量概述 2.无线传感器网络感知QoS研究3.无线传感器网络传输QoS研究4.参考文献无线传感器网络服务质量(QoS)概述 服务质量（QoS）背景与概述服务质量(QoS)定义服务质量(QoS)支持机制 无线传感器网络QoS研究服务质量（QoS）背景与概述 图10-1简单QoS模型网络服务质量指标 可用性 ：当用户需要时网络即能开始工作的时间百分比。 吞吐量：一定时间段内对网络流量的度量。

2、 时延变化：同一业务流中不同分组所呈现的时延不同 。 丢包率 ：是指网络在传输过程中数据包丢失的比率。 服务质量服务质量(QoS)支持机制支持机制 Int-serv集成业务 Diff-serv区分业务 MPLS多协议标签交换 无线传感器网络(QoS)研究无线传感器网络自身特点使得传统网络的QoS支持机制不适用： 节点资源非常有限 负载不均衡 大量冗余节点 网络异构图10-2 无线传感器网络参考体系结构内容提要1.无线传感器网络服务质量概述 2.无线传感器网络感知QoS研究3.无线传感器网络传输QoS研究4.参考文献无线传感器网络覆盖算法设计方式和目标无线传感器网络覆盖算法设计方式和目标节点部署

3、方式网络节能传感与通信距离网络可扩展无线传感器网络覆盖算法分类无线传感器网络覆盖算法分类 节点部署方式分类节点部署方式分类确定性覆盖确定性覆盖随机覆盖随机覆盖 覆盖目标分类覆盖目标分类区域覆盖区域覆盖点覆盖点覆盖栅栏覆盖栅栏覆盖图 10 4 区域覆盖、点覆盖与栅栏覆盖区域覆盖控制算法区域覆盖控制算法-轮换活跃轮换活跃/休眠节点的覆盖协议休眠节点的覆盖协议需要解决的问题： （1）网络中每一个节点如何判断自应该处于活动还是休眠状态； （2）网络中节点如何进行状态转换。轮换活跃轮换活跃/休眠节点的覆盖协议休眠节点的覆盖协议-节点覆盖休眠准则图10 5 节点覆盖图 轮换活跃/休眠节点的覆盖协议-节点调

4、度机制节点调度机制采用周期轮换工作方法，每个周期包括： self-scheduling 阶段：每个节点根据节点覆盖休眠准则，来判断自己是否进入休眠状态 。 sensing阶段： 执行传感操作轮换活跃/休眠节点的覆盖协议-邻居信息获取 各节点在每一轮开始时向传感半径内邻居节点广播位置通告消息PAM 其中包括节点ID和位置(若传感半径不同则包括发送节点传感半径)。轮换活跃/休眠节点的覆盖协议-退避自调度在判断节点是否可以休眠时，如果相邻节点同时检查到自身的传感任务可由对方完成并同时进入“休眠状态”，就会出现如图所示的“盲点”。 abcdefabcd图10 6 网络中出现的盲点连通传感器覆盖 在选取

5、网络中哪些节点处于活动状态时，需要考虑满足以下两个因素： (1)覆盖：活动节点集合的传感区域能够覆盖整个监测区域；(2)连通：网络活动节点集合中任意两个节点都能够互相通信，使得传感节点采集的数据能够被发回基站。 连通传感器覆盖 OGDC算法 定理定理1：假设在任何有限区域中，节点的数目有限。则保证区域被节点全覆盖即网络全连通的充要条件是节点通信半径大于两倍的传感半径。 定理定理2：假设传感节点的传感区域是以节点为中心的圆形区域，该区域相对待监测区域小很多。多个传感区域在其中相互相交。如果该区域中所有的交叉点都被覆盖，则该待监测区域也被完全覆盖。 定理定理3：如果所有传感节点的传感半径相等，并且

6、能够完全覆盖监控区域。减少网络中活动节点个数等效于减小所有节点传感覆盖区域的重叠。栅栏覆盖控制算法栅栏覆盖控制算法最坏与最佳情况覆盖最坏与最佳情况覆盖 最坏覆盖是指如何在网络中找到一条路径，使得沿该路径前进的目标被网络中节点发现的概率最小。该路径称为最大突破路径(maximal breach path)，即最大化该路径上点到周围最近传感器的最小距离。 最佳覆盖是指网络中找到一条路径，使得沿该路径前进的目标被网络中节点发现的概率最大。该路径称为最大支撑路径(maximal support path)，即最小化路径上的点到周围最近传感器的最大距离。 最坏覆盖与最大突破路径最坏覆盖与最大突破路径(1

7、) 基于各节点的位置产生网络Voronoi图;(2) 为Voronoi图中每一条边界赋一个权值。该值表示这条边界到离他最近的传感器节点的距离;(3) 利用二分查找法和宽度优先查找算法来获取最大突破路径。图 10 7最大突破路径Voronoi图 (c) (d)(a) (b)最坏覆盖与最大突破路径最坏覆盖与最大突破路径最佳覆盖与最大支撑路径最佳覆盖与最大支撑路径以Delaunay三角取代Voronoi图作为几何结构。图中每条边的权值算法变为计算该边到周围最近传感器节点的最大距离。查找参数由突破权值变为支撑权值，查找网络中支撑权值最小的边 图 10 8传感器网络Delaunay三角以及最大支撑路径

8、最佳覆盖与最大支撑路径最佳覆盖与最大支撑路径暴露穿越暴露穿越问题(Exposure)：即观察传感区域内目标的平均期待能力，或一个传感函数的积分，该积分值依赖于目标移动原点至终点的路径到传感节点的距离。暴露穿越算法将连续问题域转化为离散域应用图理论抽象利用Dijkstra的单源最短路径算法(Single-Source-Shortest-Path algorithm)图 10 9全节点强度模型下所获得的最小暴露路径。网格精度区别：n=8,m=1(左)；n=16,m=2(中)；n=32,m=8(右)。暴露穿越算法图 10 16最近节点全节点强度模型下所获得的最小暴露路径。网格精度区别：n=8,m=1

9、(左)；n=16,m=2(中)；n=32,m=8(右)。暴露穿越算法内容提要1.无线传感器网络服务质量概述 2.无线传感器网络感知QoS研究3.无线传感器网络传输QoS研究4.参考文献无线传感器网络服务区分参数 数据包抵达概率(可靠性) ：高优先级的数据包传送至基站节点的概率更高。 时延：高优先级的数据包抵达基站节点的时延要少于低优先级数据包。 可靠数据传输造成数据包丢失的原因主要有三个方面： 无线传感器网络所使用的无线信道较之有线链路有更大的不稳定性以及更高的误码率， 很容易受到周围环境噪声的影响造成数据包的丢失。另外在无线传感器网络中，传感器节点的布撒密度非常高，不同节点在发送数据时极易发

10、生信道竞争冲突以及碰撞造成数据包丢失。 当无线传感器网络中发生拥塞时，拥塞节点缓冲区溢出造成数据包丢失。接收节点因为数据包到达过快来不及处理造成数据包丢失。差错避免可靠传输 ACK确认重传机制确认重传机制 数据包冗余传输机制数据包冗余传输机制 多路径传输机制多路径传输机制 FEC前向纠错码机制前向纠错码机制 单分组传递：ReInForm路由ReInForm方法是基于在多条路径上发送数据包的多个拷贝来提高数据包传输可靠性。从数据源节点开始，根据数据传输可靠性、信道质量以及传感器节点到汇聚节点的跳数，确定需要的传输路径数目，以及下一跳节点数目和相应的节点。邻居节点在接收到数据源节点的数据后，将自己

11、视作数据源节点，重复上述数据源节点的选路过程。实现满足可靠要求的数据传输。 图 10 10ReInform所需传送概率为70%时数据转发举例。(A)图是源节点在链路差错率为0时传递1个数据包；(B)图是源节点在链路差错率为0时传递10个数据包；(C)是源节点在链路差错率为30%时传递1个数据包(D)是源节点在链路差错率为30%时发送10个单分组 图 10 11洪泛、单路径转发以及40%、70%可靠性要求的多路径转发在链路出错率增加时所能保证的可靠性比较 图 10 12洪泛、单路径转发以及40%、70%可靠性要求的多路径转发在链路出错率增加时为保证可靠性所引发的开销 数据块传输:RMST 无线传

12、感器网络中，有时需要传输大量的数据。比如在传送图像、声音等数据时，或者当网络需要重新配置，基站将新的代码发送至节点。 相对于单数据包的可靠性传输，保证数据块传输的可靠性机制有很大的不同。 数据块传输:RMST Fred Stann等人认为在无线传感器网络中，无线链路不稳定及易受干扰的特点是造成网络传输不可靠的主要原因. 除了在物理层实现高效的纠错码之外，如何在MAC层、传输层以及应用层提供可靠性是实现可靠传输的重要保证。 在MAC层实现可靠性保证的重要性体现在，它除了能为传输层提供跳段之间的错误恢复之外，还是实现路由发现及维持的保证。 数据块传输:RMST图10- 13每跳链路出错率为10%，

13、数据传输 40跳时，传输成功概率数据块传输:RMST图10-14数据传输6跳时，传输成功概率比较 数据块传输:RMST 802.11中提供了数据包分片与重组的方法，但是并没有提供传输可靠性保证。 而传统有线网络中的传输层TCP协议提供的传输可靠保证主要是为解决网络拥塞问题而提出的，并不适用于无线网络。 RMST提出了两种传输层可靠性保证方法:端到端选择请求NACK和跳段之间选择请求NACK。 数据块传输:RMSTl 端到端选择请求NACK是当基站节点发现接收的数据包有丢失或损坏时，沿着基站到源节点的反向增强路径发送重传请求。当重传请求到达源节点后，源节点将重传所需数据。端到端选择请求NACK方

14、法只需在基站和源节点缓存数据，中间节点无需缓存数据。l 跳段选择请求NACK方法是在路由路径上的每个节点都缓存数据，当节点发现有数据包丢或损坏时直接向其上一跳节点发送重传请求。拥塞控制 无线传感器网络大部分时间都处于零负载或轻负载，只有在异常事件发生时，网络中才会突发性的产生较大的数据量。这些数据非常重要，需要在不影响系统性能的前提下可靠的传送给基站。但是这种突发性的大数据量传输很容易导网络不同程度拥塞的发生。 网络吞吐量随源速率的增加而减小. 节点数量越大，实际吞吐量减少的越大. CODA拥塞控制方案拥塞控制方案拥塞场景 :(1)节点密集分布的网络中，当有异常事件发生时，源节点会突发性产生大

15、量数据。在源节点附近(几跳范围内)形成持续拥塞区域。 (2)在节点分布稀疏并且源节点数据发送速率较低的网络中，不会在源节点附近产生持续的拥塞，而可能在远离源节点的网络区域中任意位置产生短暂的拥塞。 (3)在节点分布稀疏并且源节点数据发送速率较高的网络中，有可能在网络区域的任意位置发生短暂或持续的拥塞。 CODA拥塞控制方案拥塞控制方案1. 基于接收者的拥塞检测；2. 开环跳段反向压力信标机制(open-loop hop-by-hop backpressure)；3. 闭环多源调整机制(closed-loop multi-source regulation) 。 CODA拥塞控制方案拥塞控制方案

16、-拥塞检测 CODA将节点缓冲区管理方法与链路负载监测方法二者相结合，提出了一个能量高效基于接收者的拥塞检测方法。 在CODA中，只有当节点缓冲区队列不为空时，才启动链路负载监测。当节点缓冲区队列为空时，表明没有拥塞发生，链路负载监测将关闭。 由于CSMA在发送数据前需要监听信道判断信道是否空闲，所以将链路负载监测放在该段时间一起进行将不会带来任何额外的开销。 CODA拥塞控制方案拥塞控制方案-开环跳段反向压力信标机制开环跳段反向压力信标机制 检测到网络发生拥塞时，节点将向邻居节点广播一个反向压力信标，同时采用相应的数据包丢弃策略或调整数据发送速率来防止拥塞的进一步传播。 当上游节点接收到反向

17、压力信标后，它将根据局部拥塞策略选择直接丢弃到来的数据包以防止缓冲区溢出，而不继续传送反向压力信标。 如果节点当前的缓冲区溢出，则选择向上游节点继续传送该信标。 CODA拥塞控制方案拥塞控制方案-闭环多源调整机制闭环多源调整机制 CODA中提出的闭环多源调整机制，能够在无线传感器网络中发生持续拥塞时，通过基站节点对源节点进行拥塞控制。 当源事件速率r小于最大理论带宽Smax的一定百分比时(即rSmax时，该源节点认为网络很可能发生了拥塞，因此将触发闭环多源调整机制。 数据率控制算法为避免或者解除无线传感器网络拥塞，可以通过数据率控制方法控制网络中节点的传输速率。当节点的速率保持一定时，可以通过

18、控制在此速率下发送数据的节点个数来达到控制网络流量的目的。 基于基于Gur Game的的QoS控制算法控制算法l River等人将无线传感器网络QoS定义为传感器网络中任意时刻向基站发送传感数据的节点个数，并提出了一种新的QoS控制算法。l 在该算法中，基站利用广播信道来与各个传感器节点进行QoS信息通信，并使用Gur Game 分布式算法来动态调整网络中节点的状态。l 通过该算法，网络中节点可选择周期性睡眠实现节能，同时还保证网络中有足够的活动节点向基站发送信息。基于基于Gur Game的的QoS控制算法控制算法 图 10 17Gur Game函数 基于基于Gur Game的的QoS控制算法

19、控制算法 算法赋予每个玩家一个有限离散时间自动机用来记忆其之前的选择。 每个有限状态自动机由一组连续状态所组成，状态个数为2N代表玩家的记忆容量，参数N称为记忆参数。从最左边的状态开始，给每个状态顺序编号-N到-1，再从1编号到N。基于基于Gur Game的的QoS控制算法控制算法 任何时刻玩家只能处于一种状态，而且玩家状态的改变只能在状态j, j+1, j-1之间进行(即相邻状态之间)。当玩家状态为N(或-N)时，状态将在N(-N)与N-1(-N+1)之间改变。 当裁判公布奖励概率r后，玩家如果处于状态j，就以概率r转到状态j+1, 以概率1-r转到状态i-1。当玩家处于正状态时，他将投票选

20、择“是”，处于负状态选择“否”。排除随机波动的影响，在经过i轮循环后，裁判接收到“是”的票数将收敛到k。基于基于Gur Game的的QoS控制算法控制算法图 10 18Gur Game 状态机 (N=2) 基于基于Gur Game的的QoS控制算法控制算法图 10 19网络活动节点个数 实时数据传输 在某些无线传感器网络应用中，需要保证采集的传感数据实时地传送到汇聚节点。比如在无线监控系统应用中，传感数据与基站间的通信延迟直接影响系统的跟踪质量和效果。 SPEED路由 RPAR路由SPEED路由协议 为满足数据包传输的时延需求，Tian He等人设计了一个基于反馈控制和无状态算法，支持实时通信

21、的路由协议SPEED SPEED是地理位置信息相关的路由协议，它面向实时应用提供端到端数据包传输速率保证。 SPEED协议中实现了网络拥塞控制、负载平衡以及路由空洞避免机制，能有效提高数据包传输成功率、节省能量消耗、延长网络寿命。 该协议是无状态的结构，节点只需保持其邻居节点信息，无须保存路由表全局信息，有很好的扩展性。无须MAC层提供QoS或实时性支持。 SPEED路由协议图 10 20SPEED路由协议模块 SPEED路由协议-邻居信标交换机制 SPEED协议中每一个节点向邻居节点周期广播信标数据包。该周期信标用于邻居节点之间交换地理位置信息。 除了邻居信标之外，SPEED还有延迟估计信标

22、和反向压力信标。延迟估计信标用于在节点与邻居节点之间传输延迟估计。当节点发现网络发生拥塞时，SPEED使用反向压力信标通知上游节点做出相应调整。 SPEED路由协议-延迟估计 在发送端，发送节点在数据包进入到网络输出队列时打上时间戳，然后在接收到该数据包ACK时，从收发时间差中减去接收端的处理时间得到一跳的通信延迟。 在接收端，接收节点处理ACK数据包的时间将作为ACK的一个字段发送回去。通过将新计算的延迟值与原延迟值进行指数加权平均来更新延迟值。 考虑到无线传感器网络的传播距离，在延迟计算中忽略了传播延迟。SPEED路由协议-SNGF算法 节点利用局部地理信息和传输速率信息在邻居节点中选择下

23、一跳路由。 邻居节点定义为处于当前节点通信范围内的节点。节点在其邻居节点中，选择比自己距离目标区域更近的节点组成候选转发节点集合（forwarding candidate set, FCS）。 节点利用前面介绍的延迟估计获得到所有邻居节点的延迟。根据该延迟及节点间的距离，节点可计算其FCS集合中每个节点的传输速率。SPEED路由协议-SNGF算法根据传输速率是否满足预定的传输速率域值，FCS集合中的节点分为两类：大于速率域值的邻居节点集合和小于速率域值的邻居节点集合。若大于速率域值的邻居节点集合不为空，则在该集合的节点中按照一定的概率分布选择下一跳节点，节点的传输速率越大，被选中的概率也越大；

24、若大于速率域值的邻居节点集合为空，则在小于速率域值的邻居节点集合中，使用邻居反馈循环NFL算法计算转发概率，并按这个概率决定是否丢弃分组。如果决定转发分组，FCS集合内的节点按照一定的概率分布选择为下一跳节点。SPEED路由协议-邻居反馈循环策略 邻居反馈循环策略NFL(Neighbor Feedback Loop)是SPEED协议中保证网络单跳传输速度的关键部分。当节点将数据包发送到转发速度小于传输速率阈值的节点或者发生了数据包丢失时，节点认为发生了传输差错。NFL策略将统计当前节点的所有邻居节点传输差错率，并使该差错率收敛为0。MAC层收集差错信息，并将传输差错率反馈到转发比例控制器(Re

25、lay Ratio Controller)。转发比例控制器是一个多输入单输出的控制器，将根据这些差错率计算转发概率，供SNGF路由算法作路由选择。转发比例控制器只有当大于速率域值的邻居节点集合为空时才会启动。 SPEED路由协议-邻居反馈循环策略图 10 21邻居反馈循环 RPAR(Real-time Power-Aware Routing)路由 Octav Chipara认为在无线网络中传输功率与通信延迟之间存在一个折衷。为分析无线传感器网络节点的传输功率对通信延迟的影响，他在XSM2节点上进行了实验分析。 实验结果如图10-22所示RPAR路由图 10-22发射功率和跳段距离对传输速度的影

26、响 RPAR路由实验表明： 节点的发射功率对数据包传输速度有着非常明显的影响。 当固定节点发射功率不变，改变跳段距离时，数据包传输速度一开始有所增加，当到达一定距离后会急剧下降。 数据包传输速度在最开始增加是由于数据包每跳的传输距离更远了，而之后的急剧下降是因为距离超过了发射功率范围。 在轻负载时，发射功率调整将是控制通信延迟的有效方法。但是增加功率也有其它的一些负面影响：由于提高了发射功率会增加信道的竞争和干扰，从而导致网络的最大可用吞吐量下降。 RPAR路由协议组成 动态速度分配策略 转发策略 延迟估计 邻居管理器。 RPAR路由协议-动态速度分配策略动态速度分配策略在节点转发数据包之前，

27、它将根据到目的节点的距离和数据包所剩时限slack，使用动态速度分配策略计算出所需速度。应用在源节点初始化slack时限，在每一条节点需要根据缓冲队列延迟、竞争延迟、传输延迟更新数据包中的slack时限值。为计算缓冲队列延迟，节点在接收到数据包和数据包成为传输队列头时分别打上时戳，这样当数据包成为传输队列头时，数据包所需速度按下面公式计算：)()()(),(),(StStSslackDSdDSvrecheadrecreqRPAR路由协议-转发策略转发策略 当节点接收到数据包，并利用动态速度分配策略计算出其所需速度后，它需要在其邻居表中查找能够满足当前速度需求的下一跳转发节点。下一跳节点所能提供

28、的速度保证由下面公式给出：)( ,(),(),(),( ,(pN,SdelayDNdDSdPNDSvprovRPAR路由协议-延迟估计延迟估计 延迟估计负责对估计各个不同转发选择的延迟。源节点使用功率p发送数据包到邻居节点N的延迟时间取决于多个因素：竞争信道延迟、数据包和ACK报文传输延迟，以及传输次数。 RPAR路由协议-邻居管理器邻居管理器 RPAR中的邻居管理器负责动态发现可用高效的转发选择并管理节点邻居表。当邻居表中的所有节点都不能满足当前数据包速度要求时，邻居管理器被触发。邻居管理器为发现新的可用转发选择提供了两种机制：调整邻居表中节点的发射功率(功率调整)和发现新邻居。 功率调整： 当转发策略无法在邻居节点中发现满足速度要求的节点时，邻居管理器将从邻居中选择一个节点增大它的发射功率以取得更快的传输速度。在邻居节点中，如果节点通过增大发射功率能够减少传输次数，则该节点能够作为增大发射功率的候选节点。 当节点处于以下情况时，则不适于继续增大