传感网原理与技术第四章传感网关键技术课件.ppt

1、第四章第四章 传感网关键技术传感网关键技术主要内容主要内容n 4.1 命名与寻址命名与寻址n 4.2 拓扑控制拓扑控制n 4.3 能量管理能量管理n 4.4 时间同步时间同步n 4.5 节点定位节点定位n 4.6 本章小结与进一步阅读的文献本章小结与进一步阅读的文献4.1 命名与寻址命名与寻址n 目的目的将将WSNWSN中的节点赋予逻辑上的名称和中的节点赋予逻辑上的名称和地址信息，能够把不同的节点区分地址信息，能够把不同的节点区分开。开。4.1 命名与寻址命名与寻址n 基本原理基本原理 名称（名称（NameName）是表示节点、数据、）是表示节点、数据、处理等的名字。处理等的名字。 地址（地址

2、（AddressAddress）是为了找到某个事）是为了找到某个事物而提供的相应信息物而提供的相应信息4.1 命名与寻址命名与寻址n 基本原理基本原理 在传统的网络中，独立节点、网站在传统的网络中，独立节点、网站以及它们的数据都被命名并分配地以及它们的数据都被命名并分配地址。址。 但是在无线传感器网络中，所有的但是在无线传感器网络中，所有的节点都不是独立的。节点都不是独立的。4.1 命名与寻址命名与寻址n 基本原理基本原理 名称、地址和标识符名称、地址和标识符 唯一的节点标识符（唯一的节点标识符（Unique node Unique node identifier, UIDidentifier

3、, UID）。UIDUID的设定可的设定可以与生产厂家、产品名称和序列号以与生产厂家、产品名称和序列号结合起来，在节点生产时就分配结合起来，在节点生产时就分配好，并且恒定不变。好，并且恒定不变。4.1 命名与寻址命名与寻址n 基本原理基本原理 名称、地址和标识符名称、地址和标识符 MACMAC地址地址。在单跳邻近节点之间区分。在单跳邻近节点之间区分节点地址。在无线传感器网络中，节点地址。在无线传感器网络中，使用基于竞争的使用基于竞争的MACMAC协议时，把协议时，把MACMAC地址包含在单播地址包含在单播MACMAC分组中，节点就分组中，节点就能判断哪些数据分组没有到达。能判断哪些数据分组没有

4、到达。4.1 命名与寻址命名与寻址n 基本原理基本原理 名称、地址和标识符名称、地址和标识符 网络地址网络地址。网络地址是用来在多跳。网络地址是用来在多跳范围内表示和找到某个节点的。因范围内表示和找到某个节点的。因此，网络地址常常与路由关联起此，网络地址常常与路由关联起来。来。4.1 命名与寻址命名与寻址n 基本原理基本原理 名称、地址和标识符名称、地址和标识符 网络标识符网络标识符。多个无线传感器网络。多个无线传感器网络部署在同一区域，如果无线射频芯部署在同一区域，如果无线射频芯片是相同的类型并工作在同一频片是相同的类型并工作在同一频段，就需要通过网络标识符来区分段，就需要通过网络标识符来区

5、分不同的网络。不同的网络。4.1 命名与寻址命名与寻址n 基本原理基本原理 名称、地址和标识符名称、地址和标识符 资源标识符资源标识符。名称或资源标识符。名称或资源标识符（Resource identifiersResource identifiers）是以用）是以用户可以理解的语言表达的，对于用户可以理解的语言表达的，对于用户来说资源标识符具有一定的含户来说资源标识符具有一定的含义。如，这个名称。义。如，这个名称。4.1 命名与寻址命名与寻址n 地址管理地址管理 名称、地址的唯一性名称、地址的唯一性 全局唯一全局唯一。地址在全局范围内至多只出。地址在全局范围内至多只出现一次。现一次。 网内唯

6、一网内唯一。地址在指定的网络内唯一。地址在指定的网络内唯一。 局部唯一局部唯一。地址在同一网络中可能会出地址在同一网络中可能会出现几次，但是在某个恰当的邻域范围内现几次，但是在某个恰当的邻域范围内是唯一的。是唯一的。4.1 命名与寻址命名与寻址n 地址管理地址管理 地址分配地址分配。 地址再分配地址再分配。如果地址空间较小，需要。如果地址空间较小，需要回收地址再重新分配。回收地址再重新分配。 地址表达地址表达。 地址的冲突检测地址的冲突检测。 绑定绑定。4.1 命名与寻址命名与寻址 地址表达地址表达 地址所需二进制数的长度地址所需二进制数的长度。假设采用假设采用IEEE 802.3IEEE 8

7、02.3标准分配地址，在无线标准分配地址，在无线传感器网络中，数据分组可能很小，传感器网络中，数据分组可能很小，4848位长位长的地址甚至比数据还长。的地址甚至比数据还长。 寻址所需要的通信开销寻址所需要的通信开销。在基于竞争的在基于竞争的MACMAC协议中，任何节点都可能向协议中，任何节点都可能向任何其他节点传送数据，这种情况下地址长任何其他节点传送数据，这种情况下地址长度越短越好。度越短越好。4.2 拓扑控制拓扑控制n 目的目的 形成一个优化的网络拓扑结构。对形成一个优化的网络拓扑结构。对于延长网络的生存时间、减小通信于延长网络的生存时间、减小通信干扰、提高干扰、提高MACMAC协议和路由

8、协议的效协议和路由协议的效率等具有重要意义。率等具有重要意义。 是是WSNWSN中许多研究问题的基础。中许多研究问题的基础。4.2 拓扑控制拓扑控制n 设计目标设计目标 连通连通。WSNWSN中的节点感知到的数据一中的节点感知到的数据一般要以多跳的方式传送到汇聚节点般要以多跳的方式传送到汇聚节点。如果至少要去掉。如果至少要去掉k k个节点才能使网个节点才能使网络不连通，就称该网络是络不连通，就称该网络是k-k-连通的连通的。拓扑控制一般要保证网络是。拓扑控制一般要保证网络是1-1-连连通的。通的。4.2 拓扑控制拓扑控制n 设计目标设计目标 覆盖覆盖。覆盖可以看成是对。覆盖可以看成是对WSNW

9、SN服务质服务质量的度量，可以分为区域覆盖、点量的度量，可以分为区域覆盖、点覆盖和栅栏覆盖。如果目标区域中覆盖和栅栏覆盖。如果目标区域中的任何一点都被的任何一点都被k k个节点监测，就称个节点监测，就称该网络是该网络是k-k-覆盖的。一般要求目标覆盖的。一般要求目标区域的每一个点至少被一个节点监区域的每一个点至少被一个节点监测，即测，即1-1-覆盖。覆盖。4.2 拓扑控制拓扑控制n 设计目标设计目标 网络生命期网络生命期。一般将其定义为：从。一般将其定义为：从网络开始运行直到死亡节点的百分网络开始运行直到死亡节点的百分比低于某个阈值时的持续时间。我比低于某个阈值时的持续时间。我们可以认为网络只

10、有在满足一定的们可以认为网络只有在满足一定的覆盖质量、连通质量、某个或某些覆盖质量、连通质量、某个或某些其他服务质量时才是存活的。其他服务质量时才是存活的。4.2 拓扑控制拓扑控制n 设计目标设计目标 吞吐能力吞吐能力。WSNWSN中节点的吞吐率中节点的吞吐率与与结点规模结点规模n n和节点的无线射频芯片的和节点的无线射频芯片的发射半径成反比例关系。通过拓扑发射半径成反比例关系。通过拓扑控制减小发射半径或减小网络规模控制减小发射半径或减小网络规模，在节省能量的同时，可以在一定，在节省能量的同时，可以在一定程度上提高网络的吞吐能力。程度上提高网络的吞吐能力。4.2 拓扑控制拓扑控制n 设计目标设

11、计目标 干扰和竞争干扰和竞争。减小通信干扰和。减小通信干扰和MAC MAC 层的竞争有助于延长网络生命期。层的竞争有助于延长网络生命期。拓扑控制可以调节发射范围或工作拓扑控制可以调节发射范围或工作节点的数量。这些都能改变节点的数量。这些都能改变1 1跳邻居跳邻居节点的个数（也就是与它竞争信道节点的个数（也就是与它竞争信道的节点数），从而减小干扰和减少的节点数），从而减小干扰和减少竞争。竞争。4.2 拓扑控制拓扑控制n 设计目标设计目标 网络延迟网络延迟。当网络负载较高时，较。当网络负载较高时，较低的发射功率会带来较小的端到端低的发射功率会带来较小的端到端延迟；而当网络负载较低时，较低延迟；而当

12、网络负载较低时，较低的发射功率会带来较大的端到端延的发射功率会带来较大的端到端延迟。迟。4.2 拓扑控制拓扑控制n 功率控制功率控制为为WSNWSN中的节点选择合适的发射功率中的节点选择合适的发射功率。但是求解最优的发射功率控制问。但是求解最优的发射功率控制问题是题是NPNP难的，因此只需寻找实用解难的，因此只需寻找实用解。当前的一些解决方案的基本思想。当前的一些解决方案的基本思想都是通过降低发射功率来延长网络都是通过降低发射功率来延长网络的生命期。的生命期。4.2 拓扑控制拓扑控制n 功率控制功率控制 基于节点度的功率控制基于节点度的功率控制 基于邻近图的功率控制基于邻近图的功率控制 分布式

13、功率分配算法分布式功率分配算法XTC 集中式功率分配算法集中式功率分配算法COMPOW4.2 拓扑控制拓扑控制n 基于节点度的功率控制基于节点度的功率控制 算法思想算法思想一个节点的度数一个节点的度数是指所有距离该节点是指所有距离该节点一跳的邻居节点的数目。一跳的邻居节点的数目。WSN中每个节点可以通过功率控制机中每个节点可以通过功率控制机制调节发射功率，以均衡节点的单跳可制调节发射功率，以均衡节点的单跳可达邻居数量的方式优化网络拓扑结构，达邻居数量的方式优化网络拓扑结构，改进系统的相关性能。改进系统的相关性能。代表性算法：代表性算法：LMA，LMN。4.2 拓扑控制拓扑控制n 基于节点度的功

14、率控制基于节点度的功率控制 LMA（本地平均算法）（本地平均算法） 开始时所有节点都有相同的发射功率开始时所有节点都有相同的发射功率TransPower，每个节点定期广播一个包含自，每个节点定期广播一个包含自己己ID的的LifeMsg消息。消息。 如果节点接收到如果节点接收到LifeMsg消息，发送一个消息，发送一个LifeAckMsg应答消息。该消息中包含所应答应答消息。该消息中包含所应答的的LifeMsg消息中的节点消息中的节点ID。4.2 拓扑控制拓扑控制n 基于节点度的功率控制基于节点度的功率控制 LMA（本地平均算法）（本地平均算法） 每个节点在下一次发送每个节点在下一次发送Life

15、Msg时，首先检查已经收时，首先检查已经收到的到的LifeAckMsg消息，利用这些消息统计出自己的消息，利用这些消息统计出自己的邻居数邻居数NodeResp。 如果如果NodeResp小于下限小于下限NodeMinThresh，那么节点，那么节点在这轮发送中将增大发射功率；同理，如果在这轮发送中将增大发射功率；同理，如果NodeResp大于上限大于上限NodeMaxThresh，那么节点将减，那么节点将减小发射功率。发射功率的范围为：最大为小发射功率。发射功率的范围为：最大为Bmax倍的倍的，最小为，最小为Bmin倍的倍的TransPower。4.2 拓扑控制拓扑控制n 基于节点度的功率控制

16、基于节点度的功率控制LMA（本地平均算法）（本地平均算法）发射功率计算方法：发射功率计算方法：其中，其中，Bmax, Bmin, Ainc, Adec是可调参数。是可调参数。maxTransPowerminTransPower,NodeMinThresh-NodeRespTransPowerincBAminTransPowermaxTransPower,(1 (NodeRespNodeMaxThresh) TransPowerdecBA4.2 拓扑控制拓扑控制n 基于节点度的功率控制基于节点度的功率控制LMN（本地邻居平均算法）（本地邻居平均算法）与与LMA相比，仅在以下步骤中不同：相比，仅在

17、以下步骤中不同： 如果节点接收到如果节点接收到LifeMsg消息，发送一个消息，发送一个LifeAckMsg应答消息。该消息中包含节点应答消息。该消息中包含节点自己的邻自己的邻居数居数。每个节点在下一次发送每个节点在下一次发送LifeMsg时，首先检查已经收时，首先检查已经收到的到的LifeAckMsg消息，消息，将消息中的所有邻居数求平将消息中的所有邻居数求平均值作为自己的邻居数均值作为自己的邻居数NodeResp。4.2 拓扑控制拓扑控制n 基于邻近图的功率控制基于邻近图的功率控制 算法思想算法思想邻近图可以用邻近图可以用G = (V, E)的形式表示，其中的形式表示，其中V代表图中顶点的

18、集合，代表图中顶点的集合，E代表图中边的集合代表图中边的集合。设所有节点都使用最大发射功率发射时形成设所有节点都使用最大发射功率发射时形成的拓扑图是的拓扑图是G，按照一定的邻居判别条件求，按照一定的邻居判别条件求出该图的邻近图出该图的邻近图G，每个节点以自己所邻接，每个节点以自己所邻接的最远节点来确定发射功率。的最远节点来确定发射功率。代表性算法：代表性算法：DRNG，DLMST。4.2 拓扑控制拓扑控制n 基于邻近图的功率控制基于邻近图的功率控制 基本定义基本定义 E中的元素可以表示为中的元素可以表示为l = (u, v)，其中，其中u, vV。所有由一个图。所有由一个图G = (V, E)

19、导出的邻导出的邻近图近图G= (V, E)是指：对于任意一个节是指：对于任意一个节点点vV，给定其邻居的判别条件，给定其邻居的判别条件q，E中中满足满足q的边的边(u, v)属于属于E。4.2 拓扑控制拓扑控制n 基于邻近图的功率控制基于邻近图的功率控制 基本定义基本定义 (u, v)和和(v, u)是两组不同的边，即边是有是两组不同的边，即边是有向的。向的。 d(u, v)表示节点表示节点u、v之间的距离，之间的距离，r(u)代代表节点表节点u的通信半径。的通信半径。4.2 拓扑控制拓扑控制n 基于邻近图的功率控制基于邻近图的功率控制 基本定义基本定义 可达邻居集合可达邻居集合 代表节点代表

20、节点u以最大发射以最大发射半径可以到达的节点集合，有节点半径可以到达的节点集合，有节点u和和 以及这些节点之间的边构成可达邻居子以及这些节点之间的边构成可达邻居子图图RuNRuNRuG4.2 拓扑控制拓扑控制n 基于邻近图的功率控制基于邻近图的功率控制 基本定义基本定义定义由节点定义由节点u和和v构成边的权重函数构成边的权重函数w(u,v)满足满足:上述关系式中，上述关系式中，id(x)表示节点表示节点x的编号的编号)(),(min)(),(min&)(),(max)(),(max&),(),()(),(max)(),(max&),(),(),(),(),(),(221122112211221

21、1221122112211viduidviduidviduidviduidvudvudorviduidviduidvudvudorvudvudvuwvuw4.2 拓扑控制拓扑控制n 基于邻近图的功率控制基于邻近图的功率控制 准备阶段准备阶段 每个节点以自己的最大发射功率广播每个节点以自己的最大发射功率广播HELLO消息，该消息中至少要包括自消息，该消息中至少要包括自己的己的ID和自己所在的位置。这个阶段完和自己所在的位置。这个阶段完成后，每个节点通过接收到的成后，每个节点通过接收到的HELLO消息确定自己可达的邻居集合消息确定自己可达的邻居集合RuN4.2 拓扑控制拓扑控制n 基于邻近图的功率

22、控制基于邻近图的功率控制 DRNG算法算法 假设节点假设节点u、v满足条件满足条件 ，且不存在另一节点且不存在另一节点p同时满足同时满足 ， ， 时，时，节点节点v则被选为节点则被选为节点u的邻居节点。的邻居节点。( , )ud u vr( , )( , )w u pw u v( , )( , )w p vw u v( , )pd p vr）4.2 拓扑控制拓扑控制n 基于邻近图的功率控制基于邻近图的功率控制 DLSS算法算法 假设已知节点假设已知节点u以及它的可到达邻居子图以及它的可到达邻居子图 ，将，将p到所有可达邻居节点的边以权重到所有可达邻居节点的边以权重 为标准按升序排列；依次取出这

23、些边，直到为标准按升序排列；依次取出这些边，直到u与所有可达邻居节点直接相连或通过其他与所有可达邻居节点直接相连或通过其他节点相连；最后，与节点相连；最后，与u直接相连的节点构成直接相连的节点构成u的邻居集合。的邻居集合。RuG( , )w u v4.2 拓扑控制拓扑控制n 基于邻近图的功率控制基于邻近图的功率控制 结束阶段结束阶段 经过执行经过执行DRNG和和DLSS算法后，节点算法后，节点u确定了自己的邻居集合，然后将发射半确定了自己的邻居集合，然后将发射半径调整为到最远邻居节点的距离。更进径调整为到最远邻居节点的距离。更进一步，通过对所形成的拓扑图进行边的一步，通过对所形成的拓扑图进行边

24、的增删，使网络达到双向连通。增删，使网络达到双向连通。4.2 拓扑控制拓扑控制n 基于邻近图的功率控制基于邻近图的功率控制 DRNG算法、算法、DLSS算法对比算法对比 (a) 优化前优化前 (b) DRNG优化优化 (c) DLSS优化优化4.3 能耗优化技术能耗优化技术n 传感器节点的体系结构传感器节点的体系结构 传感器节点由电源、感知、计算和通信四个传感器节点由电源、感知、计算和通信四个子系统组成子系统组成4.3 能耗优化技术能耗优化技术n 传感器节点的能耗分布传感器节点的能耗分布 节点传输节点传输1 1比特数据所消耗的能量与比特数据所消耗的能量与MCUMCU执执行行10001000条指

25、令的能耗大致相当条指令的能耗大致相当4.3 能耗优化技术能耗优化技术n 节点能耗分布的共性节点能耗分布的共性 通信子系统的功耗高于计算子系统通信子系统的功耗高于计算子系统 RadioRadio的传输、接收和空闲状态的功耗位于的传输、接收和空闲状态的功耗位于同一数量级，而休眠状态的功耗较低同一数量级，而休眠状态的功耗较低 感知子系统的能耗取决于传感器的类型，可感知子系统的能耗取决于传感器的类型，可能成为另一主要的能耗来源能成为另一主要的能耗来源4.3 能耗优化技术能耗优化技术n 能耗优化的对象能耗优化的对象 网络子系统网络子系统以以“计算计算”换换“通信通信”RadioRadio无需通信时应尽量

26、置于休眠状态无需通信时应尽量置于休眠状态 感知子系统感知子系统4.3 能耗优化技术能耗优化技术n Radio的体系结构的体系结构n 功耗模型功耗模型n 通信能耗模型通信能耗模型12rtxEkkd3rxEk()()cTTonstoutonRRonstPNP TTP TNP RR4.3 能耗优化技术能耗优化技术n 节能策略概览节能策略概览4.3 能耗优化技术能耗优化技术n 节点级能量优化节点级能量优化 来自于传统的嵌入式系统节能技术来自于传统的嵌入式系统节能技术硬件技术、软件技术硬件技术、软件技术 功耗感知计算功耗感知计算DPMDPM、DVSDVS 能量感知的软件技术能量感知的软件技术低功耗操作系

27、统、任务调度低功耗操作系统、任务调度 射频管理技术射频管理技术关键在于决定何时关闭射频芯片关键在于决定何时关闭射频芯片4.3 能耗优化技术能耗优化技术n 无线通信级能量优化无线通信级能量优化 优化节点的单跳通信能耗优化节点的单跳通信能耗 可进一步分为：物理层、数据链路层、可进一步分为：物理层、数据链路层、MACMAC层、功率控制、协作通信技术、认知通信技层、功率控制、协作通信技术、认知通信技术和网络编码技术术和网络编码技术 物理层：物理层：DMCSDMCS根据网络通信流量和无线信道状况，动态调整根据网络通信流量和无线信道状况，动态调整信号调制和编码参数信号调制和编码参数 数据链路层：差错控制技

28、术数据链路层：差错控制技术4.3 能耗优化技术能耗优化技术n 网络级能量优化网络级能量优化从网络全局的角度优化、调度各节点的计算从网络全局的角度优化、调度各节点的计算和通信任务，强调节点间的相互协作以提高和通信任务，强调节点间的相互协作以提高全局网络的生存周期全局网络的生存周期路由技术路由技术多径路由和自适应逐跳路由多径路由和自适应逐跳路由节点休眠状态调度节点休眠状态调度Sleep/WakeupSleep/Wakeup协议协议网络体系结构技术网络体系结构技术平面型平面型WSN vs.WSN vs.分簇分簇WSNWSN（层次型（层次型WSNWSN）4.3 能耗优化技术能耗优化技术n 基于数据的能

29、量优化基于数据的能量优化从数据角度减少网络中不必要的通信和数据操作，从数据角度减少网络中不必要的通信和数据操作，提高整个系统的能量有效性，包括数据的采集、处提高整个系统的能量有效性，包括数据的采集、处理和存储等技术理和存储等技术 数据冗余数据冗余感知数据具有较强的时间和空间相关性感知数据具有较强的时间和空间相关性数据压缩、网内数据处理数据压缩、网内数据处理感知子系统的功耗不可忽略感知子系统的功耗不可忽略优化节点的数据采集活动优化节点的数据采集活动数据预测技术、用计算换通信数据预测技术、用计算换通信4.3 能耗优化技术能耗优化技术n 基于移动的能量优化基于移动的能量优化 产生移动的原因产生移动的

30、原因移动作为网络设施的一部分移动作为网络设施的一部分移动作为感知环境的一部分移动作为感知环境的一部分 移动移动SinkSink、移动、移动RelayRelay如何控制节点的移动以优化网络性能、提高网如何控制节点的移动以优化网络性能、提高网络的能量有效性络的能量有效性4.3 能耗优化技术能耗优化技术n Energy Harvesting技术技术 为节点补充能量为节点补充能量太阳能技术太阳能技术无线充电技术无线充电技术 最新研究热点最新研究热点如何实现节点如何实现节点/ /网络的能量网络的能量“收支平衡收支平衡”4.4 时间同步时间同步n 基础概念基础概念 由于由于WSNWSN中节点的晶体振荡器频

31、率存在偏中节点的晶体振荡器频率存在偏差，以及温度变化和电磁干扰等，他们差，以及温度变化和电磁干扰等，他们的时间会逐渐出现偏差。在像的时间会逐渐出现偏差。在像WSNWSN这类分这类分布式系统的协同工作中，节点间的时间布式系统的协同工作中，节点间的时间必须保持同步，因此时间同步是分布式必须保持同步，因此时间同步是分布式系统中的一个关键技术。系统中的一个关键技术。4.4 时间同步时间同步n 基本原理基本原理 WSNWSN中节点的本地时钟依靠对自身晶振的中节点的本地时钟依靠对自身晶振的计数实现，晶振的频率误差和初始计时计数实现，晶振的频率误差和初始计时时刻不同，就使得节点之间的本地时钟时刻不同，就使得

32、节点之间的本地时钟不同步。若能估算出本地时钟与物理时不同步。若能估算出本地时钟与物理时钟的关系或者本地时钟之间的关系，就钟的关系或者本地时钟之间的关系，就可以构造对应的逻辑时钟实现同步。可以构造对应的逻辑时钟实现同步。4.4 时间同步时间同步n 基本原理基本原理 节点时钟通常用晶体振荡器脉冲来度量，所节点时钟通常用晶体振荡器脉冲来度量，所以任意一节点在物理时刻的本地时钟读数可以任意一节点在物理时刻的本地时钟读数可表示为：表示为： - - 节点节点i i的晶振的实际频率，的晶振的实际频率， - - 节点晶振的标准频率；节点晶振的标准频率； - - 开始计时的物理时刻，开始计时的物理时刻， - -

33、 节点节点i i在时刻的时钟读数。在时刻的时钟读数。0001( )( )( )tiiic tfdc tf( )if0f0t0( )ic t4.4 时间同步时间同步n 时间差异的来源时间差异的来源 节点开始计时的初始时间不同节点开始计时的初始时间不同； 每个节点的石英晶体可能以不同的频率每个节点的石英晶体可能以不同的频率跳动，导致时钟值逐渐偏离，称为偏差跳动，导致时钟值逐渐偏离，称为偏差误差；误差； 随着时间推移，时钟老化或随着周围环随着时间推移，时钟老化或随着周围环境如温度的变化而导致时钟频率的变化境如温度的变化而导致时钟频率的变化，称为漂移误差。，称为漂移误差。4.4 时间同步时间同步n 时

34、间同步的挑战时间同步的挑战 能耗能耗 可扩展性可扩展性；时间的同步应容忍节点数目；时间的同步应容忍节点数目变化和密度变化变化和密度变化 同步时间同步时间；同步时间越长，所需的通信；同步时间越长，所需的通信量、计算量就越大，能耗也越高量、计算量就越大，能耗也越高 同步精度同步精度4.4 时间同步时间同步n 时间同步方法、分类时间同步方法、分类 事件同步事件同步，要能够实现对事件的排序，要能够实现对事件的排序，即能够对事件的发生顺序作出判断。即能够对事件的发生顺序作出判断。 相对同步相对同步，绝对同步绝对同步，不同点在于是否，不同点在于是否能够修改节点的本地时间。能够修改节点的本地时间。 局部同步

35、局部同步，全网同步全网同步，局部部分节点之，局部部分节点之间，或者网络中所有节点之间维护时间间，或者网络中所有节点之间维护时间一致。一致。4.4 时间同步时间同步n 事件同步事件同步 在使用无线传感器网络追踪移动目标时在使用无线传感器网络追踪移动目标时，捕获到移动目标的多个节点将会记录，捕获到移动目标的多个节点将会记录移动目标的位置移动目标的位置l l和经过时间和经过时间t t，由位置由位置l l和经过时间和经过时间t t构成的消息称为事件构成的消息称为事件。多个。多个节点将探测到的事件发送到一个指定节节点将探测到的事件发送到一个指定节点，该指定节点可以动态的根据这些消点，该指定节点可以动态的

36、根据这些消息预测节点的速度，运动方向。息预测节点的速度，运动方向。4.4 时间同步时间同步n 事件同步（事件同步（TMOS）消息到达接收节点的顺序与发送节点发送的顺序一致；消息到达接收节点的顺序与发送节点发送的顺序一致；节点节点1, 2, 3, 4构成一个逻辑上的环。构成一个逻辑上的环。4.4 时间同步时间同步n 事件同步（事件同步（TMOS）节点节点3如果要发送探测到的事件如果要发送探测到的事件m3，必须沿着环在两个方向上向节点必须沿着环在两个方向上向节点4分别发送一次事件分别发送一次事件m3和和m3。事件事件m3沿着时钟方向到达节点沿着时钟方向到达节点4，事件事件m3沿着反向时钟方向到达节

37、点沿着反向时钟方向到达节点4。4.4 时间同步时间同步n 事件同步（事件同步（TMOS）节在收到事件节在收到事件m3后，节点后，节点1检查检查是否本地产生的事件都已发送出去，接着再把是否本地产生的事件都已发送出去，接着再把m3转发到节点转发到节点4。在收到事件在收到事件m3后，节点后，节点2检查是否本地产生的事件都已发送出去，检查是否本地产生的事件都已发送出去，接着再把接着再把m3转发到节点转发到节点4。4.4 时间同步时间同步n 事件同步（事件同步（TMOS）如果节点如果节点1（2）需要向节点）需要向节点4发送发送本地产生的事件本地产生的事件m1（m2），也要沿着环发送两次事件。），也要沿着

38、环发送两次事件。节点节点4将会在收到第二个将会在收到第二个m3事件之前收到每个时间戳早于事件之前收到每个时间戳早于m3.t的事件的事件至少至少1次。次。4.4 时间同步时间同步n 事件同步（事件同步（TMOS）总结）总结 根据事件同步模型，当一个事件的第二根据事件同步模型，当一个事件的第二次消息到达节点次消息到达节点4 4时，能够保证所有早于时，能够保证所有早于该事件的事件都至少已被节点该事件的事件都至少已被节点4 4接收到一接收到一次。也就是说，当一个事件转交给应用次。也就是说，当一个事件转交给应用程序时，除非所有节点产生的时间戳早程序时，除非所有节点产生的时间戳早于该事件的消息都已被转交给

39、应用程序于该事件的消息都已被转交给应用程序处理。处理。4.4 时间同步时间同步n 局部同步局部同步 RBSRBS原理原理RBSRBS在接收者之间相互同步。在接收者之间相互同步。4.4 时间同步时间同步n 局部同步局部同步 RBSRBS原理原理发送节点发送的消息不是为了向接收节点通知发送节点的时间，发送节点发送的消息不是为了向接收节点通知发送节点的时间，而是为了激发接收节点同时记录各自的本地时间而是为了激发接收节点同时记录各自的本地时间4.4 时间同步时间同步n 局部同步局部同步 RBSRBS原理原理发送节点发送的消息不是为了向接收节点通知发送节点的时间，发送节点发送的消息不是为了向接收节点通知

40、发送节点的时间，而是为了激发接收节点同时记录各自的本地时间，而是为了激发接收节点同时记录各自的本地时间，并交换各自最近记录的多个时刻信息。并交换各自最近记录的多个时刻信息。4.4 时间同步时间同步n 局部同步局部同步 RBSRBS原理原理RBS采用最小平方误差的线性回归方法对时间偏移数据进行线性拟合，采用最小平方误差的线性回归方法对时间偏移数据进行线性拟合，经过对时间漂移的补偿后，接收节点间的同步误差可以在较长时间内经过对时间漂移的补偿后，接收节点间的同步误差可以在较长时间内保持在较小的范围内。保持在较小的范围内。4.4 时间同步时间同步n 全网同步全网同步 RBSRBS全网同步原理全网同步原

41、理针对节点针对节点1, 9：节点节点9和节点和节点4以以及节点及节点4和节点和节点1根据局部根据局部RBS可可以实现时间互换，以实现时间互换，因此，经由节点因此，经由节点4，节点，节点1和节点和节点9的本地时间可的本地时间可以相互转换。以相互转换。4.4 时间同步时间同步n 全网同步全网同步 RBSRBS全网同步原理全网同步原理在网络规模较大在网络规模较大时，依靠静态指时，依靠静态指定中转节点不能定中转节点不能够保证同步协议够保证同步协议的健壮性，需要的健壮性，需要采用采用“时间路由时间路由”寻找一条连接同寻找一条连接同步源节点和目标步源节点和目标节点本地时间的节点本地时间的转换路径。转换路径

42、。4.4 时间同步时间同步n 全网同步全网同步 RBSRBS全网同步原理全网同步原理右图是左图的逻右图是左图的逻辑拓扑结构，在辑拓扑结构，在每个单跳网络范每个单跳网络范围内，如果两个围内，如果两个节点可以直接进节点可以直接进行本地时间转换，行本地时间转换，在逻辑拓扑结构在逻辑拓扑结构中，两个节点之中，两个节点之间就有一条边连间就有一条边连接。接。4.4 时间同步时间同步n 全网同步全网同步 RBSRBS全网同步原理全网同步原理通过在右图中的通过在右图中的逻辑结构中寻找逻辑结构中寻找一跳连接源节点一跳连接源节点和目标节点的最和目标节点的最短路径，那么，短路径，那么，沿着该路径可以沿着该路径可以逐

43、跳进行两节点逐跳进行两节点之间的时间同步。之间的时间同步。4.5 节点定位节点定位n 基本概念基本概念 将将WSNWSN中需要定位的节点称为中需要定位的节点称为未知节未知节点点（unknown nodeunknown node）；）； 已知位置，并协助未知节点定位的已知位置，并协助未知节点定位的节点称为节点称为锚节点锚节点（anchor nodeanchor node）或）或信标节点信标节点。4.5 节点定位节点定位n 定位方法定位方法 测距定位（测距定位（range-basedrange-based） 通过测量节点间点到点的距离或角度信息通过测量节点间点到点的距离或角度信息，使用三边测量（，

44、使用三边测量（trilaterationtrilateration）、三）、三角测量（角测量（triangulationtriangulation）或最大似然估）或最大似然估计（计（multilaterationmultilateration）法计算未知节点）法计算未知节点位置。位置。 常见测距定位方法：到达时间（常见测距定位方法：到达时间（TOATOA），到），到达时间差（达时间差（TDOATDOA），接收信号强度。），接收信号强度。4.5 节点定位节点定位n 定位方法定位方法 非测距定位（非测距定位（range-freerange-free） 无须距离和角度信息，仅根据网络连通无须距离和角

45、度信息，仅根据网络连通性等信息即可确定未知节点的位置。性等信息即可确定未知节点的位置。 常见非测距方法：质心定位，平均跳数常见非测距方法：质心定位，平均跳数距离（距离（DV-HopDV-Hop），近似三角形内点测试），近似三角形内点测试（APITAPIT）。）。4.5 节点定位节点定位n 节点位置的计算方法节点位置的计算方法 三边测量法三边测量法 当未知节点当未知节点D(x,y)D(x,y)获取其到三个（或三获取其到三个（或三个以上）信标节点的距离时，可通过距个以上）信标节点的距离时，可通过距离公式计算出自己的坐标。离公式计算出自己的坐标。222222()()()()()()aaabbbccc

46、xxyydxxyydxxyyd4.5 节点定位节点定位n 节点位置的计算方法节点位置的计算方法 三角测量法三角测量法在已知三个锚节点的坐标和未知节点在已知三个锚节点的坐标和未知节点D(x,y)D(x,y)相对于锚节点的三相对于锚节点的三个角度情况下，先通过平面几何关系求出三个已知角度对应圆个角度情况下，先通过平面几何关系求出三个已知角度对应圆的圆心坐标和半径，再利用三边测量法，计算出未知节点坐的圆心坐标和半径，再利用三边测量法，计算出未知节点坐标。标。1111221221222211()()()()()()22cosOaOaObObacacxxyyrxxyyrxxyyrr4.5 节点定位节点定

47、位n 节点位置的计算方法节点位置的计算方法 最大似然估计法最大似然估计法已知未知节点已知未知节点D(x,y)D(x,y)到锚节点到锚节点1(x1(x1 1,y,y1 1) )，2(x2(x2 2,y,y2 2) )，n(xn(xn n,y,yn n) )的距离。将距离公式的线性的距离。将距离公式的线性方程组转换为矩阵，使用标准的最小均方差可得到节方程组转换为矩阵，使用标准的最小均方差可得到节点点D D的坐标。的坐标。222111222()()()()nnnxxyydxxyyd4.5 节点定位节点定位n 测距定位测距定位 基于到达时间的定位方法基于到达时间的定位方法两个节点间的时间已同步，发送节

48、点的扬声器模块在发送伪噪声序列信号的同两个节点间的时间已同步，发送节点的扬声器模块在发送伪噪声序列信号的同时，无线电模块通过无线电同步消息通知接收节点伪噪声序列信号发送的时间，时，无线电模块通过无线电同步消息通知接收节点伪噪声序列信号发送的时间，接收节点的麦克风模块在检测到伪噪声序列信号后，根据声波信号的传播时间接收节点的麦克风模块在检测到伪噪声序列信号后，根据声波信号的传播时间和速度计算发送节点和接收节点之间的距离。节点在计算出到多个临近锚节点和速度计算发送节点和接收节点之间的距离。节点在计算出到多个临近锚节点的距离后，可以利用三边测量法或者最大似然估计法计算出自己的位置。的距离后，可以利用

49、三边测量法或者最大似然估计法计算出自己的位置。4.5 节点定位节点定位n 测距定位测距定位 基于到达时间差的定位方法基于到达时间差的定位方法发射节点同时发射两种不同传播速发射节点同时发射两种不同传播速度的无线信号，接收节点根据两种度的无线信号，接收节点根据两种信号的到达时间差，并已知两种信信号的到达时间差，并已知两种信号的传播速度，计算两个节点之间号的传播速度，计算两个节点之间的距离，再通过前面介绍的位置计的距离，再通过前面介绍的位置计算方法计算节点的位置。算方法计算节点的位置。4.5 节点定位节点定位n 非测距定位非测距定位 质心定位方法质心定位方法多边形的几何中心称为质心，多边形顶点多边形

50、的几何中心称为质心，多边形顶点坐标的平均值就是质心节点的坐标。坐标的平均值就是质心节点的坐标。多边形多边形ABCDEABCDE的顶点坐标分别为的顶点坐标分别为A(xA(x1 1,y,y1 1), ), B(xB(x2 2,y,y2 2), C(x), C(x3 3,y,y3 3), D(x), D(x4 4,y,y4 4), E(x), E(x5 5,y,y5 5) )，质心的，质心的坐标：坐标：1234512345( , )(,)55xxxxxyyyyyx y4.6 本章小结与进一步阅读的文献本章小结与进一步阅读的文献n 小结小结 WSNWSN关键技术内容较多，研究成果更新很关键技术内容较多