（信号与信息处理专业论文）基于动态拓扑的无线传感器网络的研究.pdf

南京邮电大学硕士研究生学位论文 摘要 i 摘要摘要 针对无线传感器网络能量受限、网络拓扑动态变化的特点，提高能量效率和可扩展性是 无线传感器网络 mac 协议设计的主要目标。s-mac 协议是一种典型的基于竞争的 mac 协 议，具有良好的节能特性和扩展性，但也存在占空比固定等缺点。 本文基于 s-mac 协议引入了排队论的思想，提出一种动态占空比调整的设计方案。该 方案在有突发流量负载的情况下，通过对网络中数据包到达率与节点处理速率的调整，动态 调整占空比。分析结果表明，改进协议在保持能量节省的基础上，时延、吞吐量等性能指标 都有了一定的改善，特别适用于拓扑变化频繁或传输负载变化范围大的网络。 本文还研究了动态拓扑无线传感器网络的数学模型。通过分析网络节点度分布、平均路 径长度和聚类系数三个反映网络拓扑的性能指标以及对比相关模型的仿真数据，证明了在动 态占空比设计方案仿真时使用该模型的合理性和准确性。 关键字：无线传感器网络，s-mac，动态占空比，动态拓扑 南京邮电大学硕士研究生学位论文 abstract ii abstract with regard to the specific feature of wsn, improving energy-efficiency and scalability are the major goals of mac protocol design in wsn. s-mac protocol is a typical contention-based mac protocol. it has good energy-saving features and extended, but also has some deficiencies. in this paper, we propose a novel scheme with dynamic adjustment duty cycle based on s-mac protocol. in the case of sudden traffic load, it can adjust the duty cycle according to the packet arrival rate and processing rate. analysis and simulation results show that the improved protocol, by adapting with sudden traffic load, reduces the delay and increases the throughput. we propose a novel model for dynamic wireless sensor network infrastructures. we also analyzed the comparison results of the degree distribution, average path length, clustering coefficient and network congestion which are typical topology property parameters. compared with simulation results in other relative model, it show that proposed novel model is considerably practicable and precise. keyword: wireless senor network; s-mac; dynamic duty cycle; dynamic topology 南京邮电大学学位论文原创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得南京邮电大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留本人所送 交学位论文的复印件和电子文档，可以采用影印、缩印或其它复制手段保存论 文。本文电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布（包括刊登）论文的全部或部分内容。 论文的公布（包括刊登）授权南京邮电大学研究生院（筹）办理。 研究生签名：_ 日期：_ 研究生签名：_ 导师签名：_ 日期：_ 南京邮电大学硕士研究生学位论文 第一章 绪论 1 第一章第一章 绪论绪论 1.1 研究背景研究背景 无线传感器网络（wireless sensor network，wsn）作为一种新型网络，是集信息采集、 信息传输、信息处理于一体的综合智能信息系统1。它是由大量具有特定功能的传感器节点 通过自组织的无线通信方式，相互传递信息，协同地完成特定功能的智能专用网络。 无线传感器网络是当前在国际上倍受关注的、涉及多学科高度交叉、知识高度集成的前 沿热点研究领域，它综合了微机电系统（micro-electron mechanical system，mems） 、传感 器技术、嵌入式计算技术、现代网络及无线通信技术、分布式信息处理技术等，能够通过各 类集成化的微型传感器协作地实时监测、感知和采集各种环境或监测对象的信息，这些信息 通过无线方式被发送出去，并以自组多跳的网络方式传送到用户终端，从而实现物理世界、 计算机世界以及人类社会三元世界的连通。无线传感器网络具有十分广阔的应用前景，在军 事国防、工农业、城市管理、生物医疗、环境监测、抢险救灾、危险区域远程控制等许多重 要领域都有实用价值，已经引起了许多国家学术界和工业界的高度重视，被认为是 21 世纪产 生巨大影响力的技术之一2。 1.2 无线传感器网络的特点无线传感器网络的特点 无线传感器网络的主要特点3有以下几点。 （1）传感器节点数目大，密度高 在一个无线传感器网络中，为了保证网络的可用性和生存能力，可能有成千上万的节点， 从而其节点的密度高。正由于传感器节点数目大，而且网络中一般不支持任意两个节点之间 的点对点通信。 （2）传感器节点的能量、计算能力和存储容量有限 随着传感器节点的微型化，在设计中大部分节点的能量靠电池提供，其能量有限，而且 由于条件限制，难以在使用过程中给节点更换电池，所以传感器节点的能量限制是整个无线 传感器网络设计的瓶颈，它直接决定了网络的工作寿命；另一方面，传感器节点的计算能力 南京邮电大学硕士研究生学位论文 第一章 绪论 2 和存储能力都较低，使得其不能进行复杂的计算和数据存储。因而对于无线传感器网络的研 究者们提出了挑战，它们必须设计简单有效的路由协议等，来适用于无线传感器网络。 （3）无线传感器网络的拓扑结构易变化，具有自组织能力 由于无线传感器网络中节点节能的需要，传感器节点可以在工作和睡眠状态之间切换， 传感器节点随时可能由于各种愿意发生故障而失效，或者添加新的传感器节点到网络中，这 些情况的发生都使得无线传感器网络的拓扑结构在使用中很容易发生变化。此外，如果节点 具备移动能力，也必定会带来网络的拓扑变化。基于网络的拓扑结构易变化，无线传感器网 络具有自组织、自配置的能力。 （4）传感器节点具有数据融合能力 在无线传感器网络中，由于传感器节点数目大，很多节点会采集到具有相同类型的数据， 因而，通常要求其中的一些节点具有数据融合能力，其能对来自多个传感器节点采集的数据 进行融合，再送给信息处理中心。数据融合可以减少冗余数据，从而可以减少在传送数据过 程中的能量消耗，延长网络的寿命。 跟无线 mesh 网络相比，无线传感器网络的业务量较小，无线 mesh 网络业务量较大，主 要是 internet 业务（包括多媒体业务） ；无线传感器网络移动性较强，因而能源问题是无线传 感器网络的主要问题，而无线 mesh 网络是固定的，即使移动其移动性也很小，所以可以直 接由电网供电，故其节点能量不受限制。 无线传感器网络是无线 ad hoc 网络的一种典型应用， 虽然它具有无线自组织特征， 但与 传统的无线自组织（ad hoc）网络相比，又有一些不同之处，它们之间的主要区别456有以 下几点： 在网络规模方面，无线传感器网络包含的节点数量比 ad hoc 网络高几个数量级。 在分布密度方面，无线传感器网络节点的分布密度很大。 由于能量限制和环境因素，无线传感器节点易损坏出故障。 由于节点的移动和损坏，无线传感器网络的拓扑结构频繁变化。 在通信方式方面，无线传感器网络节点主要使用广播通信，而 ad-hoc 节点采用点对 点通信。 无线传感器网络节点的能量、计算能力和存储能力受限。 由于无线传感器网络节点数量的原因，无线传感器网络节点没有统一标识。 无线传感器网络以数据为中心。 南京邮电大学硕士研究生学位论文 第一章 绪论 3 1.3 研究研究前景前景和和目的目的 未来移动通信网络除了以低成本实现数据的高速传输外，还要求在无专用通信基础设施 的场景下，网络具有适应性和生存能力，因此无线传感器网络和自组织网络将因其灵活性而 在未来移动通信网络中起到重要作用7。 无线传感器网络是由分布在给定局部区域内足够多的无线传感器节点构成的一种新型信 息获取系统。每一个传感器节点都具有一种或多种感知器，并且具有一定的计算能力。各节 点之间通过专用网络协议实现信息的交流、汇集和处理，从而实现给定局部区域内目标的探 测、识别、定位与跟踪。随着通信技术、嵌入式计算技术和传感器技术的飞速发展和日益成 熟，具有感知能力、计算能力和通信能力的微型传感器开始在世界范围内出现，由这些微型 传感器构成的传感器网络引起了人们的极大关注。 无线自组织网络是一种没有预定基础设施支撑的自组织可重构得多跳无线网络。在该网 络中，网络的拓扑、信道的环境、业务的模式随节点的移动而动态改变。无线自组织网络可 以快速地为民用和军事应该建立通信平台。 本文的研究目的旨在针对无线传感器网络结构动态变化的特点，综合考虑无线传感器网 络的节能、自组织、多跳路由以及动态拓扑等方面的要求,，在能量有效的无线传感器网络的 s-mac 协议下，提出了一种有利于网络自适应规模扩展的 mac 层算法，增强了网络自适应 网络规模变化的能力。 由于 mac 层的首要任务是避免冲突，因而在避免冲突的前提下，针对不同的网络又有 不同的侧重点。无线传感器网络是由许多智能传感器节点组成的多跳无线网络，其节点工作 能量是由电池供应，而且有可能工作在比较危险的环境中。这一特点决定了设计无线传感器 网络的 mac 协议应首要考虑能量效率问题，延长节点的网络寿命。但在节点能量必定会耗 尽的条件下，网络应该可以不断地增加新的节点，来增强网络的工作能力，延长网络的工作 寿命。这就需要在设计无线传感器网络的 mac 协议时，在考虑节能的条件下，还应使网络 具有可扩展的能力。 1.4 论文的论文的组织结构组织结构 第一章 介绍了无线传感器网络的研究背景，以及本文的主要内容和研究目的。 第二章 简述了目前无线传感器网络的主要技术，重点介绍了与本文相关的 mac 层技术 南京邮电大学硕士研究生学位论文 第一章 绪论 4 和拓扑控制技术。 第三章 详细介绍 s-mac 协议的原理及主要机制，同时也分析了其存在的问题，并列举 了现有的几种改进方案。 第四章 本文的重点， 提出了一个动态占空比调整的改进设计， 通过仿真结果进行了分析。 第五章 对一个动态拓扑的无线传感器网络模型进行建模， 与现有几种模型进行了性能比 较。 第六章 对本文所作工作的一个全面总结，展望了未来研究工作的方向。 南京邮电大学硕士研究生学位论文 第二章 无线传感器网络技术概述 5 第二章第二章 无线传感无线传感器器网络技术概述网络技术概述 2.1 概述概述 无线传感器网络是由大量的、低成本的传感器节点组成的分布式自组网络，它的特点是 节点数量众多，传感器节点随机投放，邻居节点采用低功率的多跳通信模式用来节省能耗、 增强通信的抗干扰性和可靠性。 无线频谱是无线移动通信的通信介质，它作为一种广播介质，属于有限的资源。在无线 传感器网络中，可能发生多个节点设备同时接入信道，导致分组之间相互冲突，使接收方无 法分辨出接收到的数据，浪费信道资源，吞吐量显著下降。为了解决这些问题，就需要网络 中的媒体访问控制（medium access control，mac）协议来协调资源的分配。具体说来，为 了实现多点通信，在网络中 mac 协议决定了局部范围无线信道的使用方式，以及多跳自组 织无线传感器网络节点之间的通信资源分配，也就是说必须实现两大基本功能目标：在密集 散布的传感器现场能够有助于建立起一个基本网络基础设施所需的数据通信链路；协调共享 介质的访问，以便传感器网络节点能够公平有效地分享通信资源8。mac 协议处于无线传感 器网络的底层部分，对无线传感器网络的自适应可扩展性有较大影响，是保证无线传感器网 络无线通信的关键网络协议。 2.2 无线传感器无线传感器网络的网络的 mac 层层特性特性 无线传感网络作为一种自组织网络，但由于其网络独特的资源限制和应用需求，与传统 的 ad hoc 网络有很大不同。无线自组织网络（wahn）的主要目标是在高宽带情况下提供高 吞吐量和低延迟，在这样的网络中，所有节点进行相同类型的活动并且每个用户都享有平等 访问介质层的机会。因此，每个节点的公平性是一个很重要的问题，而网络寿命并不被考虑 得很重要，因为能量源会被充电或者替换掉。 相反，对于一个无线传感器网络，延长网络寿命是一个优先考虑的问题。自始至终，在 每个节点网络操作期间节能都是很必要的。为了实现这个目标，一个网络设计方案必须准备 好在一定程度上牺牲网络吞吐量和反应时间。此外，由于无线传感器网络的节点密度、拓扑 南京邮电大学硕士研究生学位论文 第二章 无线传感器网络技术概述 6 结构等都是动态变化的，如一段时间之后会有部分节点因能量耗尽，而离开网络；同时网络 中又有一些新节点会不断地加入；还有一些节点有可能因某种需求而移动到不同的位置等， 甚至导致网络的规模发生变化。此时，吞吐量和反应时间的设计要求将取决于具体应用。 同样和 wahn 形成对比，在 wahn 中的节点有很高的冗余，因此，在其他节点活动的 时候一些节点可能被设置成睡眠状态直到出现某些需要。那些担当簇集头、网关或是接收器 的节点可能比普通节点、一件传感器节点积聚、处理并且传播更多量的数据。此外，在有些 应用中，由于节点感知数据的重要性可能对于网络目标的重要性和适应性也在变化。因此， 使用为 wahn 设计的 mac 层方案可能在没有合适修改的传感器网络中并不能使人满意。如 对于一个基于基础设施的蜂窝系统，其 mac 协议的设计基本目标是提供高质量的服务质量 （qos）和带宽效率，且主要致力于资源分配策略。而无线传感器网络没有像基站一样的中 央控制机构，况且网络节点的有效节能直接影响无线传感器网络的使用寿命，因此在设计无 线传感器网络的 mac 协议时，有几个方面问题值得重点关注：能量感知和节省；网络效率 （包括公平性、实时性、网络吞吐率和带宽利用率等） ；可扩展性9。尽管蓝牙（bluetooth） 、 wahn 和无线传感器网络在通信基础设施上有相似的地方，但由于网络寿命的制约，没有哪 个现有的蓝牙或 wahn 的 mac 协议可以直接用在无线传感器网络。相比之下，除了节能和 有效节能外，移动性管理和故障恢复策略也是无线传感器网络 mac 协议首要关注的问题之 一。尽管移动蜂窝网络、ad hoc 和蓝牙是当前主流的无线网络技术，但它们各自的 mac 协 议不适合无线传感器网络。 cdma 中的介质访问控制主要关心如何满足用户的 qos 要求和节 省带宽资源，能耗是第二位的；ad hoc 网络则考虑如何在节点具有高度移动性的环境中建立 彼此间的链接，同时兼顾一定的 qos 要求，能耗也不是其首要关心的；而蓝牙采用了主从式 的星型拓扑结构，这本身就不适合传感器网络自组织的特点。 2.2.1 无线传感器网络 mac 协议的设计要求 无线传感器网络的特性和应用决定了其主要设计目标是节能和自组织，而每个节点的公 平和时延是次要的，这也导致现有的自组网技术不能直接应用于无线传感器网络。为了建立 可靠稳定的无线传感器网络，在设计无线传感器网络的 mac 协议时需要着重考虑以下 5 个 方面1011： （1）降低能耗。 无线传感器网络的基本特征就是能量受限，mac 层协议要尽可能地节约能量，如减少冲 南京邮电大学硕士研究生学位论文 第二章 无线传感器网络技术概述 7 突和串音、降低占空比和尽量避免长距离通信。协议中还应包括折中机制，使用户可以在节 能和提高吞吐量、降低延迟之间做出选择。另外，设计协议中应该注意能量不是随时可用的， 因为节点可能处于睡眠状态或者由于不可知的原因死亡。传统的 mac 层协议的设计目标是 最大化吞吐量、最小化时延并且提供公平性。而为无线传感器网络设计的 mac 层协议关注 的是最小化能耗，这就决定了它要适度地减小吞吐量和增加时延。由于无线传感器网络的节 点总是协作完成某项应用任务，所以公平性通常不是主要问题。另外，无线传感器网络的一 些典型应用（如战场目标跟踪） ，也对其 mac 层协议的设计提出了不同于传统无线网络的要 求。 （2）实时性。 无线传感器网路经常被应用于军事、医疗等对实时性要求很高的领域，及时地检测、处 理和传递信息是其不可缺少的要求。mac 层应和其他层合作提供实时保证。 （3）自组织。 由于传感器节点数目、节点分布等在无线传感器网络生存过程中不断变化，网络的拓扑 结构也经常变化，节点位置可能移动，考虑无线传感器网络的可扩展性，节点的加入与退出 使得网络拓扑呈动态变化。 mac 层协议应该具有可扩展性以适应无线传感器网络动态变化的 拓扑结构。 （4）分布性。 由于无线传感器网络的节点计算能力和存储能力受限，需要众多节点协同完成某应用任 务，所以 mac 层协议应该运行分布式的算法，这也是有效避免某些节点的死亡造成网络瘫 痪的需要。 （5）网络性能。 mac 层协议的设计需要在各种性能间取得平衡， 各性能间的平衡往往比单个性能的表现 更重要。因为一个不平衡的协议即使在实验室里表现好，也可能在实际环境中表现很差。比 如，一个协议如果太频繁地关闭无线收发装置来节能，不仅使实时性和可靠性受到影响，包 丢失引起的重传也会反过来影响节能的效果。无线传感器网络针对不同的应用显示出了不同 的网络特性，mac 协议应该能适应不同应用的各种流量模式。 2.2.2 无线传感器网络 mac 协议的研究现状 目前针对无线传感器网络不同的应用，研究人员从不同的方面提出多个 mac 协议设计 南京邮电大学硕士研究生学位论文 第二章 无线传感器网络技术概述 8 方案1213，因而还缺乏一个统一的分类方式，但是大体依据标准分为三种，如根据网络拓扑 结构方式（分布式和集中式控制） ；使用单一或多信道方式；采用固定分配信道还是随机访问 信道方式。针对本文关注的无线传感器网络规模可扩展、拓扑结构动态变化的特点，可以把 现有的 mac 层协议大体分为 2 种： （1）基于竞争的 mac 层协议 基于无线信道随机竞争方式的 mac 协议采用按需使用信道的方式，其主要思想为：当 节点有数据需要发送时，通过竞争方式抢占无线信道。此时如果发送的数据产生冲突，则按 照某种指定策略 （如 ieee 802.11 mac 协议的分布式协调工作模式 dcf 采用的是二进制退避 重传机制） ，重新发送数据，直到数据发送成功或彻底放弃发送的数据。在 ieee 802.11 mac 协议基础上，研究者提出了许多适合无线传感器网络的基于竞争的 mac 层协议，下面首先 介绍 ieee 802.11 mac 层协议，然后说明一个典型的无线传感器网络的 mac 协议及改进。 1) ieee 802.11 mac 协议 ieee 802.11 mac141516协议是 ieee 802.11 无线局域网（wlan）标准的一部分，其主 要功能是信道分配、协议数据单元（pdu）寻址、组帧、纠检错、分组分片和重组等。ieee 802.11 协议的 mac 层有两种控制方式：中心点协调功能（point coordination function，pcf） 和分布式协调功能（distributed coordination function，dcf） 。其中以 dcf 为主要媒体访问 控制方式，dcf 以 csma/ca 为主，以 rts/cts 消息交换机制为辅；在 pcf 方式下网络中 心控制点轮询各个工作站实现中心控制方式。由于在无线信道中难以检测到信号的冲突，故 只能采用随机退避方式来减小数据冲突的概率。在 dcf 工作方式下，节点在侦听到无线信道 忙之后，采用 csma/ca 机制和随机退避等待时间算法，实现无线信道的共享。另外，所有 定向通信都采用立即的主动确认（ack）机制：如果没有收到 ack 帧，则发送方会重新传 送数据。 pcf 工作方式是基于优先级的无竞争访问，是一种可选的控制方式。它通过访问接入点 （access point，ap）协调节点的数据收发，通过轮询方式查询当前哪些节点有数据发送的请 求，并在必要时给与数据发送权。 在 dcf 工作方式下， 载波侦听机制通过物理载波侦听和虚拟载波侦听来确定无线信道的 状态。物理载波侦听由物理层提供，而虚拟载波侦听由 mac 层提供。当节点 a 向节点 b 发 送数据时，节点 c 在 a 的无线通信范围之内，节点 d 在节点 b 的无线通信范围内，但不在 节点 a 的无线通信范围内部。 节点 a 首先向节点 b 发送一个请求帧 （request to send， rts） ， 节点 b 返回一个清除帧（clear to send，cts）进行应答。在这两个帧中都有一个字段表示 南京邮电大学硕士研究生学位论文 第二章 无线传感器网络技术概述 9 这次数据交换所需要的时间长度，称为网络分配矢量（network allocation vector，nav） ，其 他帧的 mac 头也会捎带这一信息， 节点 c 和 d 在侦听到这个信息后， 就不再发送任何数据， 直到这次数据交换完成。nav 可以看作是一个计数器，以均匀速率递减到零。当计数器为零 时，虚拟载波侦听指示信道为空闲状态；否则，指示信道状态为忙状态。 在 ieee 802.11 mac 层协议中，规定了 3 种基本的帧间间隔（interframe spacing，ifs） 用来提供访问无线信道的优先级。这 3 种帧间间隔分别为： sifs（short ifs） ：最短帧间间隔，使用 sifs 的帧优先级别最高，用于需要立即响应 的服务，比如 ack 帧、cts 帧、控制帧等。 pifs（pcf ifs） ：pcf 方式下节点使用的帧间间隔，用于获得在无竞争访问周期启动 时访问信道的优先权。 difs（dcf ifs） ：dcf 方式下节点的帧间间隔，用于发送数据帧和管理帧。 sifs、pifs、difs 的大小关系为：difspifssifs。 在 csma/ca 协议中，当一个节点要传输一个数据包时，节点首先侦听信道状态，如果 信道空闲，而且经过帧间间隔时间（difs）后，信道仍然空闲，则该节点立即开始发送信息。 如果信道忙，则一直侦听信道直到信道的空闲时间超过 difs。当信道最终空闲时，节点进一 步使用二进制退避算法（binary backoff algorithm） ，进入退避状态来避免发生碰撞。节点在 进入退避状态时启动一个退避计数器，当计时完成时结束退避状态。在退避状态下，只有当 检查到信道空闲时才进行计时，如果信道忙，退避计时器中止计时，直到检测到信道空闲时 间大于 difs 后才继续计时。当多个节点推迟且进入随即退避时，利用随机函数选择最小退 避时间的节点作为竞争优胜者。 基于竞争的 mac 层协议一般使用广播式信道，连接到这条信道上的节点都可以向信道 发送广播信息。想要通信的节点遵循某种规则竞争信道，得到使用权的节点可以发送信息。 传统的基于竞争的 mac 层协议包括 aloha 和带有冲突避免的载波侦听多点接入等。 2) 其他基于 ieee 802.11 改进的 mac 协议 尽管传统的基于 csma 方式的 mac 协议也是基于载波侦听和退避机制，但它们并不太 适合无线传感器网络，因为它们都基本假设了随机分布的业务，并且趋向于支持独立的点到 点的业务流。此外，无线传感器网络的 mac 协议必须支持可变的并且高度相关和可控的周 期业务。任意基于 csma 的 mac 机制都有两个重要组成部分：侦听和退避机制。实际上， 无线传感器网络 mac 协议关注的基本问题主要还是能耗管理，而射频通信模块是能耗的最 大部件，而 mac 协议直接控制射频通信模块，对无线传感器网络节点节能具有重要的影响。 南京邮电大学硕士研究生学位论文 第二章 无线传感器网络技术概述 10 wei ye1718等通过实验证实了无线传感器网络无效能耗的四大来源：空闲侦听，由于节 点不知何时邻居节点会向自己发送数据，射频通信模块一直处于接收状态，消耗大量能量； 数据冲突，邻居节点同时向同一节点发送多个数据帧，信号相互干扰，接收方无法准确接收， 重发数据造成能量浪费；串扰，接收和处理无关的数据；控制开销，控制报文不传送有效数 据，消耗节点能量。在 ieee 802.11 mac 协议基础上，wei ye 等提出了第一个完全针对无线 传感器网络设计的 mac 协议 s-mac（sensor mac） ，具有有效节能、扩展性和冲突避免三 大优点。s-mac 协议对网络做了三大基本假设：拥有很多小的传感器节点；采用 ad hoc 网 络配置； 节点致力于协作完成一个或多个共同任务。 此外， 对于无线传感器网络应用， s-mac 协议还假设了网络能够容忍一定的通信延迟；具有较长的空闲周期（直到检测到事件发生为 止） ；应用关注网络的寿命。针对 s-mac 协议的问题分析，本文将在第三章做进一步介绍， 此处暂时略过。 （2）基于时分复用的无竞争 mac 协议 时分复用（tdma）机制就是为每个无线传感器网络节点分配独立的用于数据收发的时 隙，而节点在其他空闲时隙内转入睡眠节能状态。相比随机竞争接入机制，时分复有方式本 身就更节省能量，是实现信道分配的简单成熟机制，因为无线电波的工作时间缩短，而且没 有任何竞争带来的开销和冲突。如蓝牙技术就是采用基于 tdma 的 mac 层协议。 基于 tdma 机制的 mac 协议具有如下优点： 无竞争机制的冲突重传问题； 数据传输不需额外的控制信息； 节点在空闲时隙能够及时进入睡眠阶段。 然而 tdma 机制也存在不足之处，如 tdma 机制要求节点严格的时间同步；当有节点 数量变化时，很难调整时隙帧的长度和时隙的分配，且对节点发送数据量的变化不敏感，对 网络节点的移动、节点失效等动态拓扑结构适应性较差，因此在网络扩展性方面存在严重的 不足。以下介绍几个典型协议。 smacs1912是一个分布式协议， 节点可以发现自己的邻居节点并建立邻居列表， 进而建 立通信链路。smacs 采用多信道，并且用中心调度方式来对信道进行分配。节点的射频模块 可在不同的信道采用不同的频率，从而降低了冲突发生的概率。在此协议中还使用了随机唤 醒机制，没有通信任务时，节点进入睡眠状态，以节省电源。 ear20协议用于固定节点和移动节点间的通信，它是 smacs 协议的补充。在采用 ear 协议的无线传感器网络中，连接的建立和断开完全由移动节点来负责，并且以信噪比的值来 南京邮电大学硕士研究生学位论文 第二章 无线传感器网络技术概述 11 决定是否要断开连接。 trama2122协议是基于能量的协议，在此协议中，时隙的分配是通过节点所携带能量 的多少来决定的。该协议按照一定的规则选出能量最低的节点，为其分配时隙。在此时隙内， 节点可以工作或睡眠。当某一节点携带的能量比选出的节点具有的能量低时，它进入选举阶 段。如此反复，各节点间的能量将会得到有效平衡，从而延长了网络的生存期。 2.3 拓扑控制技术拓扑控制技术 对于一个具有规模可扩展的无线传感器网络来说，一般具有随机部署、环境复杂、传感 器节点资源有限、网络拓扑经常发生变化的特点。这些特点也向科技工作者提供了一个具有 挑战性的课题拓扑控制。拓扑控制就是要形成一个优化的网络拓扑结构，这也是其他研 究课题的支撑技术之一。 首先，拓扑控制是一种重要的节能技术，通过拓扑控制尽可能高效合理地使用能量，从 而延长整个网络的生命周期；其次，通过对网络进行拓扑控制，可以实现对传感器节点通信 功率的控制，保证网络的连通性，同时可以减少节点间的通信干扰，提高整个网络的通信效 率；再次，拓扑控制能够降低通信干扰、提高 mac 层协议和路由协议的效率，为数据融合 提供拓扑基础；此外，拓扑控制还对路由协议中转发节点的选择和数据融合中对融合节点的 选择起着重要的作用，拓扑控制还能够提高网络的可靠性、可扩展性等其他性能。 2.3.1 拓扑控制的设计目标 拓扑控制研究的问题是：在保证一定的网络连通质量和覆盖质量的前提下，一般以延长 网络的生命期为主要目标，兼顾通信干扰、网络延迟、负载均衡、简单性、可靠性、可扩展 性等其他性能，形成一个优化的网络拓扑结构。无线传感器网络是与应用相关的，不同的应 用对底层网络的拓扑控制设计目标的要求也不尽相同23。 （1）覆盖 覆盖可以看成是对无线传感器网络服务质量的度量。在覆盖问题中，最重要的因素是网 络对物理世界的感知能力。 覆盖问题可以分为区域覆盖、 点覆盖和栅栏覆盖 （barrier coverage） 。 区域覆盖研究对目标区域的覆盖（监测）问题；点覆盖研究对一些离散的目标点的覆盖问题； 栅栏覆盖研究运动物体穿越网络部署区域被发现的概率问题。相对而言，对区域覆盖的研究 较多。如果目标区域中的任何一点都被k个传感器节点监测，就称网络是k-覆盖的，或者称 南京邮电大学硕士研究生学位论文 第二章 无线传感器网络技术概述 12 网络的覆盖率为k。一般要求目标区域的每一个点至少被一个节点监测，即 1-覆盖。对于已 部署的静态网络，覆盖控制主要是通过睡眠调度实现的，voronoi 图是常用的覆盖分析工具。 对于动态网络，可以利用节点的移动能力，在初始随机部署后，根据网络覆盖的要求实现节 点的重部署，虚拟势场方法是一种重要的重部署方法。覆盖控制是拓扑控制的基本问题。 （2）连通 无线传感器网络一般是大规模的，所以传感器节点感知到的数据一般要以多跳的方式传 送到汇聚节点，这就要求拓扑控制必须保证网络的连通性。如果至少要去掉k个传感器节点 才能使网络不连通，就称为网络是k-连通的，或者称网络的连通度为k。拓扑控制一般要保 证网络是连通（至少是 1-连通）的，有些应用可能要求网络配置到指定的连通度。功率控制 和睡眠调度都必须保证网络的连通性，这是拓扑控制的基本要求。 （3）网络生命期 网络生命期有多种定义。一般将网络生命期定义为直到死亡节点的百分比低于某个阈值 时的持续时间。也可以通过对网络的服务质量的度量来定义网络的生命期，我们可以认为网 络只有在满足一定的覆盖质量、连通质量、某个或某些其他服务质量时才是存活的。功率控 制和睡眠调度是延长网络生命期的十分有效的技术。最大限度地延长网络的生命期是一个十 分复杂的问题，它一直是拓扑控制研究的主要目标。 （4）吞吐能力 假设目标区域是一个凸区域，每个节点的吞吐率为 bit/s，在理想情况下，则有下面的关 系式： 2 161aw l nr （2-1） 式中 a目标区域的面积 w节点的最高传输速率； 圆周率； 大于 0 的常数； l源节点到目的节点的平价距离； n节点数； r理想球状无线电发射模型的发射半径。 由此可以看出，通过功率控制减小发射半径和通过睡眠调度减小工作网络的规模，在省 南京邮电大学硕士研究生学位论文 第二章 无线传感器网络技术概述 13 能量的同时，可以在一定程度上提高网络的吞吐能力。 （5）干扰和竞争 减小通信干扰、减少 mac 层的竞争和延长网络的生命期基本上是一致的。功率控制可 以调节发射范围， 睡眠调度可以调节工作节点的数量。 这些都能改变一跳邻居节点的个数 （也 就是与它竞争信道的节点数） 。事实上，对于功率控制，网络无线信道竞争区域的大小与节点 的发射半径r成正比，所以减小r就可以减少竞争区域大小。睡眠调度显然也可以通过使尽可 能多的节点睡眠来减小干扰和减少竞争。 （6）网络延迟 当网络负载较重时，低发射功率会带来较小的端到端延迟；而在轻负载情况下，低发射 功率会带来较大的端到端延迟。对于这一点，一个直观的解释是：当网络负载较轻时，高发 射功率减少了源节点到目的节点的跳数，所以降低了端到端的延迟；当网络负载较重时，节 点对信道的竞争是激烈的，低发射功率由于缓解了竞争而减少了网络延迟。这是功率控制和 网络延迟之间的大致关系。 （7）拓扑性质 事实上，对于网络拓扑的优劣，很难直接根据拓扑控制的目标给出定量的度量。因此， 在设计拓扑控制（特别是功率控制）方案时，往往退而追求良好的拓扑性质。 此外，拓扑控制还要考虑诸如负载均衡、简单性、可靠性、可扩展性等其他方面。拓扑 控制的各种设计目标之间有着错综复杂的关系。对这些关系的研究也是拓扑控制研究的重要 内容。 2.3.2 拓扑控制的研究现状 当前，拓扑控制的研究主要以最大限度地延长网络的生命期作为设计目标，并集中于功 率控制和睡眠调度两个方面。下面分别介绍几种具有代表性的拓扑控制协议和算法。 compow 协议24是一种简单的将功率控制与路由协议相结合的解决方案，其基本思想 是：所有的传感器节点使用一致的发射功率，在保证网络连通的前提下，将功率最小化。 compow 建立各个功率层上的路由表， 在功率 i p层上， 通过使用功率 i p交换 hello 消息建 立路由表 i p rt，所有可达节点都是路由表中的表项。compow 选择最小的发射功率 com p，使 得 pcom rt与 maxp rt具有相同数量的表项， 其中 max p是最大发射功率。 因此整个网络都使用公共 南京邮电大学硕士研究生学位论文 第二章 无线传感器网络技术概述 14 的发射功率 com p。在节点均匀分布的情况下，compow 具有较好的性能。但是如果在无线传 感器网络中存在一个相对孤立的节点将会导致所有的节点使用很大的发射功率，因此在节点 分布不均的情况下，compow 的缺陷是较突出的。 leach 算法25是一种周期性执行的低功耗自适应分簇拓扑算法。它的基本思想是：以 循环的方式随机选择簇首节点，将整个网络的能量负载平均分配到每个传感器节点中，丛而 达到降低网络能源消耗、提高网络整体生存时间的目的。它的执行过程是周期性的，每轮循 环分为簇的建立阶段和稳定的数据通信阶段。在簇的建立阶段，相邻节点动态地形成簇，随 机产生簇头；在数据通信阶段，簇内节点把数据发送给簇头，簇头进行数据融合并把结果发 送给汇聚节点。由于簇头需要完成数据融合、与汇聚节点通信等工作，所以能量消耗大。 leach 算法能够保证各节点等概率的担任簇头， 使得网络中的节点相对均匀地消耗能量。 但 leach 需要较为严格的时间同步机制作保证， 也不能保证簇头的均匀分布， 此外簇头与汇聚 节点的单跳通信方式限制了网络的规模。 sran 算法26的基本思想是：在不破坏网络原有连通性的前提下，根据节点的剩余能量、 邻居的个数、节点的效用等多种因素，自适应地决定是成为骨干节点还是进入睡眠状态。睡 眠节点周期性地唤醒，以判断自己是否应该成为骨干节点；骨干节点周期性地判断自己是否 应该退出。span 算法对传感器节点没有特殊的要求，这是它的优点。但是，随着节点密度 的增加，sran 的节能效果表现越来越差。这主要是因为 span 采用了 802.11 的节能特性： 睡眠节点必须周期性地苏醒并侦听，这种方式的代价是相当大的。 2.4 小结小结 由于基于固定分配类的 mac 层协议通常用在拓扑结构不变或子网数目较少的网络，并 不能很好地处理传感器节点加入和节点失效的情况。所以下文的设计方案选用基于竞争类的 mac 层协议进行研究。 南京邮电大学硕士研究生学位论文 第三章 s-mac 协议研究及现有改进方案 15 第三章第三章 s-mac 协议研究及现有改进方案协议研究及现有改进方案 s-mac 协议是基于 802.11 mac 协议基础上，针对无线传感器网络的节能需求的 mac 层协议。s-mac 采用类似 ieee 802.11 中的方式来避免冲突，即包括虚拟和物理的载波侦听 和 rts/cts 交换。与 ieee802.11 相比，s-mac 具有很好的节能特性，并且可以根据流量情 况在能量和时延之间折中。s-mac 假设通常情况下传感器网络的数据传输量少，节点协作完 成共同的任务，网络能够容忍一定程度的通信时延。它的主要设计目标是减少节点能量的消 耗，并提供良好的扩展性。本章及第四章提出的改进协议都是基于此协议，但在延迟处理与 吞吐量等方面都优于 s-mac。 3.1 s-mac 原理原理 无线传感器网络是一个能量极度受限的网络，节能是 mac 协议设计的首要目标。对于 如何减小能量损耗，有不少 mac 协议都提出了相应的解决方案，其中最为基本的思想就是 当节点不需要发送数据时，尽可能让它处于功耗较低的睡眠状态。ieee 802.11 mac 协议中， pcf 和 dcf 都有一种节省能量（power-save）模式，运行于该模式时设备可以周期性地进入 睡眠状态以节省能量。但是该协议有一个前提，那就是所有的设备都只进行单跳通信。基于 这种假设，设备通过简单地广播一个信标帧就可以保持同步睡眠和唤醒。此外对于如何减少 串扰，pamas 协议给出了解决方案：当邻居节点在发送数据时，节点主动转入睡眠状态。基 于上述两种基本思想，s-mac 协议提出了适合于多跳无线传感器网络的竞争型 mac 协议的 节能方法。 （1）采用周期性睡眠和监听方法减少空闲监听带来的能量损耗。对周期性睡眠和监听的 调度进行同步，同步节点采用相同的调度，形成虚拟簇，同时进行周期性睡眠和监听，适合 多跳网络。 （2）当节点正在发送数据时，根据数据帧特殊字段让每个与此次通信无关的邻居节点进 入睡眠状态，减少串扰带来的能量损耗。 （3）采用长消息分割传递机制，通过减少控制数据带来的能量损耗，提高长消息的传输 效率。 南京邮电大学硕士研究生学位论文 第三章 s-mac 协议研究及现有改进方案 16 下面简单介绍一下 s-mac 的工作原理17： 节点 x 开机以后，首先监听一段时间，其时间长度至少为一个同步周期的长度。在该时 间段内，节点 x 监听邻居节点广播的同步（sync）分组，sync 分组包含了该节点的时间表 （schedule table）信息。如果节点 x 从一个邻居节点接收到了 sync 分组，则其采用刚接收 到的时间表进行周期性的睡眠和唤醒，并在其邻居节点的下一个监听时段广播 sync 分组。 如果节点 x 在该监听时间段内没有接收到任何 sync 分组，则其选择默认的时间表并广播 sync 分组。 确定了时间表后，节点 x 开始周期性的监听和睡眠，并在监听时段发送和接收数据。 s-mac 试图调整邻居节点的时间表，以使相邻的所有节点的监听时段同时开始。节点 x 的监 听时段被进一步划分为三个不同的阶段： 在第一阶段（sync 阶段） ，节点 x 接收来自其相邻节点的 sync 分组。在这个分组中， 相邻节点说明其自身的时间表，节点 x 将这些时间表存储在一个表中（即时间表） 。同时，节 点 x 也从 sync 分组中提取邻居节点 id 号等信息， 将这些信息存储在一个表中 （即邻居表） 。 节点 x 通过接收相邻节点的 sync 分组来掌握邻居节点的情况。节点 x 的 sync 阶段，x 的 相邻阶段依据 csma/ca 进行竞争，并有相应的回退。即如果在前面任意时刻没有接收到数 据，则每一个希望发送 sync 分组的相邻节点 y 可以随机地选择一个时刻并启动发送。在其 他情况下，节点 y 会返回到睡眠模式，并等待节点 x 的下一次被唤醒。在另一个方向上，由 于节点 x 了解其相邻节点 y 的时间表，因此，节点 x 可以在适当的时刻被唤醒，并向节点 y 发送它自己的 sync 分组（以广播的方式） 。节点 x 不需要在节点 y 的每一个唤醒时段均进 行广播。然而，为了保证时间同步，并使新的节点能够学习了解网络的拓扑结构，节点 x 应 该周期性地发送 sync 分组。相应的时段称为同步时段（synchronization period） 。 在第二个阶段（rts 阶段） ，节点 x 监听来自相邻节点的 rts 分组。在 s-mac 中，使用 rts/cts 握手机制来减少数据分组的碰撞和隐终端效应的影响。此外，有数据需要发送的相 邻节点之间在此阶段可能会发生竞争，节点间也是依据 csma/ca 进行信道竞争。 在第三阶段（cts 阶段） ，如果前一阶段接收到了一个给自己的 rts 分组，则节点 x 发 送一个 cts 分组。此后，连续地进行数据交换，数据交换可以在监听时段结束之前完成，也 可能在随后的“睡眠时段”完成，这取决于信道竞争时的回退时间及数据的长度。数据交换 完成后，节点 x 进入名义上的睡眠时间。如果前一阶段接收到给自己的 rts 分组，则节点 x 可以立即进入睡眠时间。 南京邮电大学硕士研究生学位论文 第三章 s-mac 协议研究及现有改进方案 17 3.2 s-mac 协议的主要机