第4次课WSN覆盖技术◆了解启发机制◆了解覆盖理论基础◆了解传感器网络的覆盖控制2.GAT算法•GAT算法是一种依据节点的地理位置进行分簇,并对簇内的节点选择性的进行休眠的路由算法。其核心思想是:在各数据源到数据目的地之问存在有效通路的前提下,尽量减少参与数据传输的节点数,从而减少用于数据包侦听和接收的能量开销。它将无线传感器网络划分成若干个单元格(簇),各单元格内任意一个节点都可以被选为代表,代替本单元格内所有其他节点完成数据包向相邻单元格的转发。被选中的节点成为本单元格的簇头节点;其他节点都进行休眠,不发送、接收和侦听数据包。•GAT算法通常分为虚拟单元格的划分和虚拟单元格中簇头节点的选择两个阶段。•(1)虚拟单元格的划分。•(2)虚拟单元格中的簇头节点的选择。(P75详解)3.5启发机制•在传感器网络的拓扑控制算法中,除了传统的功率控制和层次型拓扑控制两个方面之外,也提出了启发式的节点唤醒和休眠机制。该机制能够使节点在没有事件发生时设置通信模块为睡眠状态,而在有事件发生时及时自动醒来并唤醒邻居节点,形成数据转发的拓扑结构。•1.STEM算法STEM(sparseTopologyandEnergyManagement)算法是一种低占空比的节点唤醒机制。该算法采用双信道,即监听信道和数据通信信道。具体地讲,STEM算法又分为STEM-B(STEM-BEACON)算法和STEM-T(STEM-TONE)算法。在STEM-B算法中,当一个节点想给另外一个节点发送数据时,它作为主动节点先发送一串唤醒包。目标节点在收到唤醒包后,发送应答信号并自动进入数据接收状态。主动节点接收到应答信号后,进入数据发送阶段。在STEM-T算法中,节点周期性地进入侦听阶段,探测是否有邻居节点要发送数据;当一个节点想与某个邻居节点进行通信时,它就发送一连串的唤醒包,发送唤醒包的时间长度必须大于侦听的时间间隔,可以确保邻居节点能够收到唤醒包,紧接着节点就直接发送数据包。所以STEM-T比STEM-B更简单实用。STEM算法适用于类似环境监测或者突发事件监测等应用,经实验证明,节点唤醒速度可以满足应用的需要。但是在STEM算法中,节点的睡眠周期、部署密度以及网络的传输延迟之间有着密切的关系,要针对具体的应用要求进行调整。2.ASCENT算法•运行ASCENT算法的网络包括触发、建立和稳定三个主要阶段。触发阶段如图3-12(a)所示,在汇聚节点与数据源节点不能正常通信时,汇聚节点向它的邻居节点发出求助信息;建立阶段如图3-12(b)所示,当节点收到邻居节点的求助消息时,通过一定的算法决定自己是否成为活动节点,如果成为活动节点,就向邻居节点发送通告消息,同时这个消息是邻居节点判断自身是否成为活动节点的因素之一;稳定阶段如图3-12(c)所示,数据源节点和汇聚节点间的通信恢复正常,网络中活动节点个数保持稳定,从而达到稳定状态3.6覆盖3.6.1覆盖理论基础覆盖问题是无线传感器网络配置首先面临的基本问题,因为传感器节点可能任意分布在配置区域,它反映了一个无线传感器网络某区域被监测和跟踪的状况。在现有的研究成果当中,很多都是致力于解决传感器网络的部署和监测及覆盖与连接的关系等方面问题。另外,也有一些研究致力于特定的应用需求,但其核心思想都是与覆盖问题有关的。无线传感器网络覆盖相关的两个计算几何问题,(三角形、圆)。第一个就是艺术馆问题(ArtGalleryProblem)。设想艺术馆的业主想在馆内放置照相机,以便能够预防小偷盗窃。关于实现这个想法存在两个问题需要回答:首先就是到底需要多少台相机;其次,这些相机应当放置在哪些地方才能保证馆内每个点至少被一台相机监视到。假定相机可以有的视角而且可以极大速度旋转,相机可以监视任何位置,视线不受影响。3.6.1覆盖理论基础0360问题优化要实现的目标就是所需相机的数目应该最小化,在这个问题当中,艺术馆通常建模成一个二维平面的简单多边形。一个简单的解决办法就是将多边形分成不重叠的三角形,每个三角形里面放置一个相机。通过三角测量法将多边形分成若干个三角形,这样可以实现任何一个多边形都可被个相机所监视到,这里n表示多边形所包含的三角形的数目。这也是最糟糕情况下的最佳结果。3.6.1覆盖理论...