教学材料WSN研究-第3章

3.1概述3.1.1无线传感器网络MAC协议无线传感器网络是一种特殊的自组织(Adhoc)网络，可应用于布线和电源供给困难的区域、人员不能到达的区域(如受到污染、环境不能被破坏或敌对区域)和一些临时场合(如发生自然灾害时，固定通信网络被破坏)等，不需要固定网络支持，具有快速展开、抗毁性强等特点。无线传感器网络具有以下明显特征:(1)传感器节点受环境的限制，通常由电量有限且不可更换的电池供电，所以在考虑传感器网络体系结构以及各层协议设计时，能量效率是设计的主要考虑目标之一。下一页返回3.1概述(2)由于无线传感器网络经常应用在环境较为恶劣的场合，而且能量受限，因此传感器节点失效的概率远大于传统网络节点，因此网络的扩展性保障是必需的，以保证部分传感器节点的失效不会影响全局任务的进行。(3)传感器节点的计算和处理能力有限，通信带宽有限，与感知目标紧密祸合，以数据为中心，高密度、大规模随机分布，这些特点都决定了网络效率在无线传感器网络中将尤其重要。上一页下一页返回3.1概述3.1.2研究热点根据无线传感器网络所面向的实际应用的特点，MAC协议在设计时需要解决很多土程和研究技术难题，这些都已经成为无线传感器网络MAC协议的研究热点问题。(1)能量效率。(2)可扩展性。(3)网络效率。(4)算法复杂度。(5)与其他层协议的协同。上一页下一页返回3.1概述3.1.3MAC协议的分类从不同的角度入手，对MAC协议进行分类的方法有多种，可以根据MAC协议使用的信道数目分为基于单信道、基于双信道和基于多信道三类;可以根据MAC协议分配信道的方式分为竞争型、分配型以及混合型;可以根据网络类型是同步网络还是异步网络，将MAC协议分为同步、异步两类。本书中采用根据MAC协议分配信道的方式来进行分类，从竞争型、分配型以及混合型三种类型入手，介绍目前比较有代表性的MAC协议，本章将要介绍的各种MAC协议方案的比较如表3-1所示。上一页返回3.2竞争型MAC协议3.2.1SMAC协议SMAC(SensorMAC)协议是较早提出的一种基于竞争的无线传感器网络MAC协议，由USC/ISI的WeiYe等人提出，并在NS2、TinyOS等平台上进行了仿真和实现。该协议继承了802.11MAC协议和PAMAS协议的基本思想，在此基础上加以改进，以WSN的能量效率为主要设计目标，较好地解决了能量问题，同时兼顾了网络的可扩展性，为广大研究人员参考和比较。下一页返回3.2竞争型MAC协议1.基本思想SMAC协议提出了适合于多跳无线传感器网络的竞争型MAC协议的节能方法。

(1)采用周期性睡眠和监听方法减少空闲监听带来的能量损耗。对周期性睡眠和监听的调度进行同步，同步节点采用相同的调度，形成虚拟簇，同时进行周期性睡眠和监听，适合多跳网络。

(2)当节点正在发送数据时，根据数据帧特殊字段让每个与此次通信无关的邻居节点进入睡眠状态，减少串扰带来的能量损耗。

(3)采用消息传递机制，减少控制数据带来的能量损耗。上一页下一页返回3.2竞争型MAC协议2.关键技术

1)周期性监听和睡眠

SMAC协议中，节点协同进行周期性监听和睡眠的状态切换，确保节点能同步进行监听和睡眠调度，而不是各个节点自发进行随机的睡眠和监听，周期性监听和睡眠的时间之和为一个调度周期。

2)自适应监听传感器网络往往采用多跳通信，而节点的周期性睡眠会导致通信延迟的累加。为了减少通信延迟的累加效应，SMAC采用了一种流量自适应监听机制。其基本思想是在一次通信过程中，通信节点的邻居在此次通信结束后唤醒并保持监听一段时一间。如果节点在这段时一间接收到RTS帧，则可以立即接收数据，而不需要等到下一个监听周期，从而减少了数据传输延迟。上一页下一页返回3.2竞争型MAC协议3)串扰避免

SMAC协议中，在RTS/CTS帧中都带有目的地址和本次通信的持续时间信息，接收到该帧后，如果发现目的地址不是本地地址，节点马上进入睡眠状态，并将此次通信的持续时间存储到本地的NAV(NetworkAllocationVector)中。NAV会随着本地时一钟的运行递减。在NAV值非零期间节点都处于睡眠状态，这就很大程度避免了串扰数据包的接收，减少了能量损耗。

4)消息传递如果在发送长信息时由于几个比特错误造成重传，则会造成较大的延时和能量损耗。但如果简单地将长包分段，则又会由于RTS/CTS的使用形成过多的控制开销。上一页下一页返回3.2竞争型MAC协议基于此，SMAC提出了“消息传递”机制。将长的信息包分成若干个DATA，并将它们一次传递，但是只使用一个RTS/CTS控制分组作为交互。节点为整个传输预留信道，当一个分段没有收到ACK响应时，节点便自动将信道预留向后延长一个分段传输时间，并重传该分段，整个传输过程中DATA和ACK都带有通信剩余时间信息，邻居节点可以根据此时间信息避免串扰。上一页下一页返回3.2竞争型MAC协议3.算法描述（1）GSA算法GSA是一种分布式算法，该算法能使大规模网络中不同步的调度方式最终汇聚成一个全局的调度方式。GSA算法将发起该调度方式的节点地址和该调度方式的存在时间相结合，得到调度方式的全局ID号。如果只采用节点地址作为调度方式ID号，则节点如果重启将会导致调度方式重名。调度方式的存在时间为调度方式自创建起在网络中存在的时间长度，相当于该调度方式的年龄。节点在创建一个调度方式时，需要将创建时间记录下来。如果节点要广播该调度方式，则根据当前时间计算调度方式已经存在的时间长度，并存储在SYVC帧中。接收到此SYVC帧的节点先将调度方式的年龄加上接收数据包所需要的时间，对年龄进行更新。上一页下一页返回3.2竞争型MAC协议然后记录下该时间点，并将调度方式的年龄与本地调度方式进行比较，如果新调度方式年龄更大，则切换到新调度方式;如果两者一年龄相同，则选择节点号较小的调度方式。该节点选择了新的调度方式后，在其调度周期的监听段内，节点也会广播该调度方式，广播时同样要更新调度方式的年龄，这样，其虚拟簇内的邻居节点很快也会切换到新调度方式。经过一段时间的扩散之后，全网所有的节点都会同步到年龄最大的调度方式下。上一页下一页返回3.2竞争型MAC协议2)FPA算法FPA(FastPathAlgorithm)算法来管理多跳路径上的调度方式，给定一个数据源节点和Sink节点以及它们之间的传输路径，对该路径上的所有节点，通知其切换到一种快速路径调度方式下，来消除多跳延迟。如图3-3所示，当节点严格按照调度方式进行监听和睡眠时，如果数据从Node1传到Node2是在监听时间段t1，那么Node1必须等到t3才能将数据发给Node3。在进行快速路径调度后(如图3-3中虚线部分)，Node3会在t2进行监听并接收数据，减少延迟。上一页下一页返回3.2竞争型MAC协议4.小结通过采用低占空比的周期性监听和睡眠的调度，SMAC协议减少了节点空闲监听的能量损耗;通过采用串扰避免和消息传递机制，SMAC协议减少了串扰和控制数据包带来的能量损耗;为低功耗无线传感器网络应用开发提供了基础。3.2.2TMAC协议TMAC协议提出了一种自适应调整占空比的方法:通过动态调整调度周期中的活跃时间长度来改变占空比。作者在OMNET++上对协议进行仿真，并在EYES平台上实现，验证了TMAC协议的性能特点。上一页下一页返回3.2竞争型MAC协议1.基本思想TMAC协议中，数据的发送都是以突发方式进行，如图3-4所示为TMAC协议进行调度的基本方法。每个节点都周期性地唤醒，进入活跃状态，和邻居进行通信，然后进入睡眠状态，直到下一个周期的开始。同时，新的消息在队列中进行缓存。节点之间进行单播通信使用RTS-CTS-DATA-ACK交互的方法，以确保避免冲突和可靠传输。上一页下一页返回3.2竞争型MAC协议2.关键技术

1)周期性监听的同步如同SMAC协议，在TMAC协议中，每个节点进行周期性监听也需要进行调度方式的同步，TMAC协议采用了与SMAC协议相同的机制。通过周期性发送SYNC帧来保持节点之间的同步。

2)RTS操作和TA的选择当节点发送RTS帧后，如果没有接收到相应的CTS帧，那么有以下三种可能:①接收节点处发生碰撞，没能正确接收RTS帧;②接收节点在此之前已经接收到串扰数据;③接收节点处于睡眠状态。如果发送节点在时间几之内没有接收到CTS帧，如上文所述，节点会进入睡眠状态。但是如果是前两种可能导致节点没有接收到CTS帧，那么当它进入睡眠时，它的接收节点还处于监听状态，发送节点此时进行睡眠会增加传输延迟。上一页下一页返回3.2竞争型MAC协议TMAC协议中，当邻居节点还处于通信状态时，节点不应该进行睡眠，因为节点可能是接下来信息的接收者。节点发现串扰的RTS或CTS都能够触发一个新的监听间隔TA。为了确保节点能够发现邻居的串扰，TA的取值必须保证当节点能够发现串扰的CTS，所以TMAC协议规定TA的取值范围如下:TA>C+R+T

如图3-5所示，C为竞争信道的时间，R为发送RTS需要的时间，T为RTS发送结束到开始发送CTS的时间。上一页下一页返回3.2竞争型MAC协议3)串扰避免在TMAC协议中，串扰避免机制是可选的。SMAC协议中采用的串扰避免机制能够显著减少串扰带来的能量损耗。但是实验表明，这样会导致冲突的增加:节点在睡眠过程中可能无法发现邻居的RTS或CTS帧，当它唤醒并发起通信时就可能对邻居的通信造成干扰。这会导致碰撞，而碰撞引起的重传同样会浪费能量，在数据量较大时碰撞概率增加，所以协议不宜采用串扰避免机制。TMAC协议中可以根据网络中的数据量大小选择是否使用与SMAC相同的串扰避免机制。上一页下一页返回3.2竞争型MAC协议3.算法描述在采用周期性调度的MAC协议中，如果一个节点在邻居准备向其发送数据时进入了睡眠状态，这种现象称为早睡。为了解决早睡问题，TMAC提出了两种方法。下面对这两种方法进行介绍。1)Futurerequest-to-send

第一种方法是未来请求发送(Futurerequest-to-send,FRTS)。如图3-7所示，当节点C收到B发给A的CTS后，立即向D发送一个FRTS帧。FRTS帧包含节点D接收数据前需要等待的时间长度，D在此时间内必须保持在监听状态。上一页下一页返回3.2竞争型MAC协议此外，由于C发送的FRTS可能干扰A发送的数据，所以A需要将发送的数据延迟相应的时间。A在接收到CTS之后发送一个与FRTS长度相同的DS帧，该帧不包含有用信息，只是为了保持AB对信道的占用，在发送DA之后A立即向B发送数据信息。由于采用了FRTS机制，TA需要增加一个CTS时间，如图3-7所示。FRTS方法可以提高吞吐量，减少延迟，但是增加了控制开销，会降低TMAC协议的能量效率。上一页下一页返回3.2竞争型MAC协议2)Full-bufferpriority

第二种方法是满缓冲区优先(Full-bufferpriority)。当节点的缓冲区接近占满时，对接收到的RTS帧不回复CTS,而是立即向缓冲区中数据包的目的节点发送RTS，以建立数据传输。如图3-8所示。向C发送RTS,C因缓冲区快占满不发送CTS,而是发送RTS给D。这个方法的优点是减少了早睡问题发生的可能性，在一定程度上能够控制网络的流量。缺点是在网络数据量较大时增加了冲突的可能。上一页下一页返回3.2竞争型MAC协议3.2.3PMAC协议1.基本思想PMAC协议引入了模式信息，即一种包含睡眠唤醒信息的二进制位串，节点能够通过模式信息提前获知邻居的下一步活动。基于这些模式信息，网络没有数据传输时一节点能够在几个预知的调度周期内减少监听时间，邻居节点将要发生通信时节点进入监听状态，从而减少节点的空闲监听带来的能量损耗。带有睡眠唤醒信息的模式信息由一个二进制位串组成。位串中的何一位都表不在一个固定的时一间段内节点应处于何种状态，1为监听状态，0为睡眠状态。在PMAC协议中，节点的监听和睡眠调度都根据模式信息来进行，节点根据自身的活动生成本地模式信息，调度时还需要结合邻居的模式信息。上一页下一页返回3.2竞争型MAC协议2.关键技术1)模式的生成假设Pj代表节点j的模式二进制串，模式二进制串的长度定义为N，节点在一个长为N个时一隙的周期内根据二进制串调度自己的状态。如果二进制串的长度小于N，则节点重复该串来调度，比如:N=5,Pj=O1，则节点在当前周期内按照01010这个串来调度。在PMAC协议中，模式串必须是如下形式:0m1,m=0,1,……N-1,其中m代表串中0的个数，m越小表示数据流量越大。假设pij代表节点j在第i个周期中的模式，xi表示在第i个周期和Pji,n中更新的模式个数，其中，z=0,1,……xi，表示第n个更新的模式。第i个周期中节点1采用的第一个模式Pji,0，为工作模式Pji。上一页下一页返回3.2竞争型MAC协议2)模式的交换

PMAC协议中，节点实际的监听和睡眠调度不仅要参考本地的模式，还需要参考邻居的模式。节点为下一个周期生成新的模式在当前周期结束时将进行广播来交换模式信息。为了满足这种交换方式，PMAC协议引入了超帧(STF,supertimeframes)，如图3-10所示。每个超帧分为两个子帧，第一个子帧为模式重复时间帧(PRTF,PatternRepeatTimeFrame)，在此帧内每个节点重复自己的模式，PRTF对应上文所述的一个周期，分为N个时隙，每个时隙长为TR;除此之外，PRTF还包括一个固定的W时隙，在这个特殊时隙中，所有节点都不睡眠。上一页下一页返回3.2竞争型MAC协议该时隙可以用来进行广播，也可以防止节点准备发送数据时邻居因自身无数据发送而进入更长时间的睡眠。第二个子帧为模式交换时间帧(PETF,PatternExchangeTimeFrame)，在此帧内邻居节点之间进行模式信息的交换。PETF分为多个时隙，每个时隙长度为TE。节点在第二部分时间内广播第一部分时间结束时更新的模式。

3)调度的生成对于PRTF中的N个时隙，节点是处于睡眠状态还是应该唤醒，应根据二进制串中对应的位来进行调度。该位的值不仅取决于节点自己的模式中对应的位，还取决于邻居节点对应的位。对于节点j的一个给定的时隙，下面列举出j可能进行的调度，如表3-2所示。上一页下一页返回3.2竞争型MAC协议3.小结

PMAC引入了流量自适应的调度机制，节点的调度由本地和邻居的流量共同决定。实验表明和SMAC相比，在网络数据流量较小时，PMAC协议具有更好的能效性;在网络数据流量较大时，PMAC协议具有更小的延时，提高了系统吞吐量，PMAC协议引入的基于模式交换的调度方式非常适合WSN的应用。下一步PMAC协议还将与TMAC和DMAC进行比较，深入研究TMAC中的timeout机制和PMAC的结合，对模式和调度生成方法进行改进，使PMAC协议在性能上能有更好的表现。上一页下一页返回3.2竞争型MAC协议3.2.4WiseMAC协议

1.基本思想基于竞争的MAC协议在占用信道时都采用CSMA机制，节点在发送数据之前首先监听信道，在接收状态时直监听信道。WiseMAC协议基于CSMA机制，具有如下特点:使用前导采样技术;使用链路级ACK保证可靠性和本地同步;通过本地同步的广播获得最小的前导长度;随机的前导长度保证冲突避免;数据包头捎带信息，建立流量突发的传输;设置大于灵敏门限的接收门限，减少不必要的唤醒;载波监听范围大于干扰范围，减少隐藏终端现象等。上一页下一页返回3.2竞争型MAC协议2.关键技术1)前导采样WiseMAC采用了前导采样技术，在该技术中，对信道进行采样息味着在短时间内对无线信道进行监听，比如一个调制符号的持续时间。网络中所有节点都保持相同的采样时间Tw，但各节点的采样调度是独立的。如果采样时监听到信道忙，节点会继续监听，直到接收到数据或者信道空闲。在发送端，每个数据包发送之前都要发送一个唤醒前导序列，该序列的长度和采样周期的长度相等，这样就可以保证在数据部分到达时节点处于监听状态。WiseMAC必须选择尽可能小的唤醒前导序列长度，以减少控制开销。上一页下一页返回3.2竞争型MAC协议2)前导长度最小化由于无线信道出错的概率较大，WiseMAC协议采用了ACK机制来重传出错的数据。在ACK帧内，不仅含有节点对接收到的数据的确认信息，还含有节点距离下一次采样发生的时间。每个节点都维护一个表，该表存储了直接邻居节点的采样时间偏移量。使用这些信息，节点在适当的时间发起一次通信，使用最小长度的唤醒前导，如图3-11所示。

唤醒前导的长度必须能够覆盖源节点和目标节点之间可能的时钟漂移，假设θ是节点晶振的频率容限，L为通信时间，则需要的持续时间为Tp=min(4θL,Tw)。该前导称为时一钟偏移补偿前导（CDCP），如图3-12所示。上一页下一页返回3.2竞争型MAC协议3)冲突避免为了防止多个节点在同一采样时间向同一目标节点发送数据，WiseMAC在最小长度的时钟偏移补偿前导之前引入了信道保留前导(MRP),该前导具有随机的长度，这两个前导共同组成了WiseMAC协议的唤醒前导。唤醒前导之后包括一个位同步前导和一个帧起始分隔符，如图3-13所示。

4)捎带机制

WiseMAC协议的数据包中引入了一个“more”标志位，如果该位为1，表示该数据包的源节点的缓存中还有数据要发往目标节点，目标节点在发送完成ACK后继续进行监听，源节点在接收到ACK后继续发送缓存中的数据，这种捎带机制能够减少数据从端到端的延迟，使用WiseMAC协议具备了如同SMAC协议中的消息传递机制带来的类似功能，节点可以将长数据包分段，并以突发方式发送上一页下一页返回3.2竞争型MAC协议3.小结WiseMAC协议持续非坚持CSMA机制，引入了前导采样技术来减少空闲监听，通过最小化前导机制提供了对网络通信流量的自适应，在网络数据量较小时具有超低的能量损耗，网络数据量较大时具有很高的能量效率。但由于节点需要存储邻居节点的信道监听时间，会占用宝贵的存储空间，增加协议实现复杂度，在节点密度高的网络内这个问题尤为突出。3.2.5Sift协议Sift协议采用CSMA机制，竞争窗口长度固定，在窗口内每个时隙通过非均匀概率分布来选择是否发送。通过在NS2平台上的仿真，研究人员将Sift协议与802.11协议进行了比较，在实时性等方面证明了Sift协议的优越性。上一页下一页返回3.2竞争型MAC协议1.基本思想Sift协议是一种基于CSMA机制的MAC协议，采用了固定长度的竞争窗口。

Sift协议的流程用伪代码描述如图3-14所示。其中函数pickslot根据Sift协议提出的概率分布在[1,CW]中选择时隙。moveto状态表示退出当前状态并执行新状态的代码。Wait表示等待具体的时间间隔，tslot，tsift,tdifs,tACK,timeout参数和802.11协议中的定义相同。上一页下一页返回3.2竞争型MAC协议2.关键技术

Sift协议的核心部分是对于固定窗口的每个时隙，节点如何确定发送数据的概率。如图3-15所示，为Sift协议提出的几何增长概率分布图，下文将给出具体的定义，并讨论如何选择参数a。在Sift协议中，每个节点都根据假设目前参与竞争的节点数来竞争时间窗口[1,CW]中的任一时隙，该假设值开始比较大，随每个节点传输的概率增大而相应减小。如果第一个时隙没有节点发送数据，节点减小竞争节点数假设值，增加在第二个时隙中的传输概率，这一过程每个时隙中都重复执行。上一页下一页返回3.2竞争型MAC协议如果某个节点选择了某个时隙发送数据，那么其他竞争节点只能选择新的时隙，在退避固定长度的竞争窗口后重复整个过程。如果多个节点选择同一个时隙发送，将会产生碰撞。碰撞后各个节点只能选择新的时隙，在退避固定长度的竞争窗口后重复整个过程。如图3-16所示为4个节点运行sift协议的状态切换过程。阴影部分表示数据帧传输状态。当信道空闲时，节点根据概率分布在传输之前退避随机长度。上一页下一页返回3.2竞争型MAC协议假设每个节点选择时隙r∈[1,CW]发送数据的概率为Pr。Pr的概率分布如下:式中a为分布参数(0<a<1)，可以看出Pr随着r呈指数级增长，所以窗口中后面的时隙有更大的发送概率。上一页下一页返回3.2竞争型MAC协议3.小结Sift协议是一种非常新颖的竞争型MAC协议，它充分考虑了无线传感器网络的业务特点，特别适合冗余、竞争与空间相关的应用场景。Sift协议实现简单，关键在于在固定长度的竞争窗口中选择时隙时需要用到一种递增的非均匀概率分布，而不是传统协议中的可变长度竞争窗口。Sift协议提高了事件消息的实时性和网络的带宽利用率，但是没有充分考虑能量效率，研究人员下一步将考虑把Sift协议与Span或GAR协议结合，提高能量效率。上一页返回3.3分配型MAC协议3.3.1SMACS协议

1.基本思想

SMACS协议假设每个节点都能在多个载波频点上进行切换，协议将每个双向信道定义为两个时间段，类似于TDMA机制中分配的时隙。SMACS协议是一种分布式协议，允许一个节点集发现邻居并进行收发信道的分配，不需要全局节点来进行分配。为了实现这种机制，SMACS协议将邻居发现和信道分配进行了组合。传统的链路分簇算法首先要在整个网络执行发现邻居的步骤，然后分配信道或时隙给相邻节点之间的通信链路。下一页返回3.3分配型MAC协议SMACS协议在发现相邻节点之间存在链路后立即分配信道，当所有节点都发现邻居后这些节点就组成一个互联的网络，网络中节点两两之间至少存在一个多跳路径。由于邻近节点分配的时隙有可能产生冲突，为了减少冲突的可能性，每个链路都分配一个随机选择的频点，相邻链路都有不同的工作频点。从这点上来讲，SMACS协议结合了TDMA、FDMA的基本思想。当链路建立后，节点在分配的时隙中打开射频部分，与邻居进行通信，如果没有数据收发，则关闭射频部分进行睡眠，在其余时隙节点关闭射频部分，降低能量损耗。上一页下一页返回3.3分配型MAC协议2.关键技术

1)链路建立

SMACS协议引入了超帧的概念，用一个固定参数Tframe表示。网络中所有节点的超帧都有相同的长度。节点在上电后先进行邻居发现，何发现一个邻居，这一对节点就形成一个双向信道，即一个通信链路。在两个节点的超帧中为该链路分配一对时隙用于双向通信。随着邻居的增加，超帧慢‘漫被填满。每对时隙都会选择一个随机的频点，减少邻近链路冲突的可能。这样全网很快就能在初始化后建立链路，这种不同步的时一隙分配称为异步分配通信。上一页下一页返回3.3分配型MAC协议2)邻居发现和信道分配为了比较清楚地阐述SMACS协议中的邻居发现机制，下面以举例的形式来说明。如图3-18所示假设节点B,C,G进行邻居发现。这些节点在随机的时间段内打开射频部分，在一个固定的频点监听一个随机长度的时间。如果在此监听时间内节点没有接收到其他节点发出的邀请消息，那么随后节点将发送一个邀请消息。图中节点C就是在监听结束后广播一个邀请消息Typel。节点B和G接收到C发出的Typel消息后，等待一个随机的时间，然后各自广播一个应答消息Type2。如果两个应答消息不冲突，C将接收到B和G发来的邀请应答。C在这里要进行一个选择，可以选择最早到达的应答者，也可以选择接收信号强度最大的应答者。在选择了应答者后C将立即发送一个Type3消息通知哪个节点被选择。此处选择最早到达的B做为应答者，节点G将关闭射频部分进行睡眠，并在一个随机的时间后重新进行邻居发现。上一页下一页返回3.3分配型MAC协议

如果节点C已经选择了邻居，将在Type3消息中携带分配信息，该信息包含节点C的下一个超帧的起始时间。在收到该分配信息后，节点B将和本地的超帧起始时间进行比较，得到一个时间偏移，并找出两个共同的空闲时间段作为时隙对，分配给B和C之间的链路。在确定了时隙对后，节点B选择一个随机的频点，将时隙对在超帧中的位置信息以及选择的频点通过Type4发送给节点C。经过这些测试信息的成功交换后，B和C之间就完成了时隙分配和频率选择。上一页下一页返回3.3分配型MAC协议3.算法描述在静态MAC协议进行类似于TDMA帧结构的时隙分配时，静止的节点需要周期性地广播邀请信息，这样可以周期性地进行邻居发现，允许新节点加入网络，使协议适应网络拓扑的变化。邀请信息不需要在每个超帧广播，何间隔固定个数的超帧再多进行一次广播即可。移动节点窃听这些邀请信息，所以这些邀请信息也可以作为移动节点的引导信号。移动节点根据这些引导信号决定最佳路线，所以SMACS协议将邀请信息作为EAR算法的触发器。移动节点可以从邀请信息中获得信噪比、节点地址、功率等信息。上一页下一页返回3.3分配型MAC协议EAR算法定义了一种新的信令机制，主要使用以下四种消息:BroadcastInvite(BI),静止节点邀请其他节点加入;MobileInvite(MI)，移动节点响应BI并请求建立连接;MobileResponse(MR)，静止节点接受MI请求;MobileDisconnect(MD)，移动节点通知静止节点取消连接，不需要响应。移动节点和静止节点通过交换信令实现EAR算法的机制，也就是如何建立移动节点和静止节点之间通信链路的机制。上一页下一页返回3.3分配型MAC协议主要有以下步骤:(1)静止节点会何间隔固定个超帧发送一次BI消息，移动节点在接收到静止节点的BI消息后将开始连接过程。(2)静止节点在接收到MI消息后需要检查连接是否可以建立。(3)连接建立后，移动节点在移动过程中会接收新的邻近静止节点发送的BI消息，根据信道质量移动节点会选择淘汰邻居记录中连接质量较差的邻居。上一页下一页返回3.3分配型MAC协议4.小结

SMACS协议提出了一种TDMA/FDMA结合的信道分配机制，该协议不需要集中控制的算法，可用来建立一种平面结构的网络。通过为何对时隙分配随机的载波频率，SMACK协议避免了全局时间同步，减少了复杂性。通过在超帧未分配的时隙进行睡眠，SMACS协议减少了空闲监听和串扰，提供了较好的能量效率。通过引入EAR算法，SMACS协议对节点的移动性提供了一定的支持。但是协议需要节点能提供多个载波频点，对节点硬件提出了要求。此外，EAR算法收敛较慢，不适合移动性较张的应用。上一页下一页返回3.3分配型MAC协议3.3.2TRAMA协议

1.基本思想

TRAMA协议采用了流量自适应的分布式选举算法，节点交换两跳内邻居信息，传输分配时指明在时间顺序上哪些节点是目的节点，然后选择在每个时隙上的发送节点和接收节点。TRAMA协议由三个部分组成，其中NP协议(NP,NeighborProtocol)和分配交换协议(SEP,ScheduleExchangeProtocol)允许节点交换两跳内的邻居信息和分配信息。自适应选举算法(AEA,AdaptiveElectionAlgorithm)利用邻居和分配信息选择当前时隙的发送者和接收者，让其他与此次通信无关的节点进入睡眠状态以节省能量。上一页下一页返回3.3分配型MAC协议2.关键技术1)NP协议通过在随机接入时隙中交换控制信息，NP协议实现了邻居信息的交互。图3-20为控制信息帧的帧头格式。控制信息中携带了增加的邻居的更新，如果没有更新，控制信息作为通知邻居自己存在的信标。每个节点发送关于自己下一跳邻居的增加更新，可以用来保持邻居之间的连通性。如果一个节点在一段时间内都没有再收到某个邻居的信标，则该邻居失效。由于节点知道下一跳邻居和这些邻居的下一跳邻居的信息，所以网络中每个节点都能交换两跳邻居信息。上一页下一页返回3.3分配型MAC协议2)分配交换协议分配交换协议用于建立和维护发送者和接收者选择时需要的分配信息。首先每个节点要生成分配信息，然后通过分配信息的广播实现分配信息交换和维护。

3.算法描述为了提高能量效率，TRAMA尽可能让节点处于睡眠状态，通过重用已经分配但未使用的时一隙来提高带宽利用率。在分配接入周期任一给定的时隙t中，任一节点的状态根据该节点的两跳邻居信息和该节点的一跳邻居发布的分配信息来确定，有发送、接收、睡眠三种可能的状态。上一页下一页返回3.3分配型MAC协议4.小结

TRAMA协议是一种分配型MAC协议，节点通过NP协议获得邻居信息，通过SEP协议建立和维护分配信息，通过AEA算法分配时隙给发送节点和接收节点。TRAMA协议在冲突避免、延时、带宽利用率等方面都能提供较好的性能，但协议需要较大的存储空间来存储两跳邻居信息和分配信息，需要运行AEA算法，复杂度较高。由于AEA算法更适合于周期性数据采集任务，所以TRAMA协议非常适合周期性监测应用。上一页下一页返回3.3分配型MAC协议3.3.3DMAC协议

1.基本思想

DMAC协议深入分析了SMAC协议中的监听睡眠调度机制的缺点，同步的睡眠会增加多跳传输的延迟，同步的监听和竞争信道会增加冲突的可能。SMAC协议虽然又引入了自适应睡眠机制，但只减少了两跳延迟，数据在多跳传输到Sink的过程中仍会因中间节点的睡眠而中止。为了解决这些问题，DMAC协议引入了一种交错的监听睡眠调度机制，保证数据在多跳路径上的连续传输。上一页下一页返回3.3分配型MAC协议2.关键技术1)交错唤醒机制在一些传感器网络应用中,数据从多个数据源汇聚到一个Sink节点，数据传输的路径都包含在一个树状拓扑结构中DMAC协议将其定义为数据采集树。图3-23所示为数据采集树和节点的交错唤醒方法。每个间隔分为接收、发送和睡眠三个周期。DMAC协议中数据的传输没有采用RTS-CTS机制，减少了控制开销。采用ACK机制来保障可靠传输。如果节点发送完成后没有收到ACK，必须缓存该数据，并等到下个发送周期再重传，通常重传次数超过三次就丢弃该数据包。上一页下一页返回3.3分配型MAC协议

为了减少在发送周期中处于树中同一深度的节点之间的碰撞，每个节点在发送数据之前先退避一个固定时间BP(BackoffPeriod)，然后在竞争时间窗口CW(ContentWindow)中再退避一个随机时间。接收到数据的节点在等待一个短周期SP(ShortPeriod)后回复一个ACK应答。发送周期和接收周期的长度u可以由下式得出:u=BP+CW+DATA+SP+ACK式中DATA为数据包的传输时一间，ACK为ACK帧的传输时间。上一页下一页返回3.3分配型MAC协议2)自适应占空比机制DMAC协议中，如果节点在一个发送周期内有多个数据包要发送，就需要该节点和树状路径上的上层节点一起加大发送周期占空比。DMAC协议引入了一种更新机制，使占空比能自适应调整。通过在MAC层数据帧的帧头加入一个标记(moredataflag)，以较小控制开销发送更新请求。如果缓存有多个数据包，或者待转发的数据包中已经将标记设置为有效，那么节点就需要设置标记再发送该数据。节点调整占空比的条件是:发送一个标记有效的数据而且接收到标记有效的ACK，或者接收到标记有效的数据。上一页下一页返回3.3分配型MAC协议3)数据预测机制在数据采集树中，越靠近上层的节点，汇聚的数据越多，所以对树的底层节点适合的占空比不一定适合中间节点。比如节点A和B有共同的父节点C,A和B在每个发送周期都只有一个数据包要发送。如果A通过竞争获得了信道，就向C发送数据，此数据的占空比更新标记设置为无效，而C在接收到数据后向A发送一个ACK，随后进入睡眠，这样就给B节点的数据带来了睡眠延迟。上一页下一页返回3.3分配型MAC协议DMAC协议引入了数据预测机制来解决此问题。如果一个节点在接收状态下接收到一个数据包，该节点预测子节点仍有数据等待发送。在发送周期结束后再等待3u个周期，节点重新切换到接收状态。所有接收到该数据包的节点都执行这样一个操作，增加了一个接收周期。在这个增加的接收周期中，节点如果没有接收到数据则直接转入睡眠状态，不会进入发送周期。如果接收到数据，那么在3u个周期之后再增加一个接收周期。在节点的发送周期，如果节点竞争信道失败，会接收到父节点发给其他节点的ACK，那么节点就知道父节点在3u个周期后会增加一个接收周期，所以节点在睡眠3u个周期后进入发送状态，在这个增加的发送周期中向父节点发送数据。上一页下一页返回3.3分配型MAC协议4)MTS帧机制

MTS帧只包含目的地址和MTS标志位。标志位为1时称为MTS请求，标志位为0时称为MTS清除。节点发送MTS请求有两种可能:第一种情况下，节点在退避后没有足够的时间发送数据，也没有接收到父节点的ACK串扰，由于信道忙导致节点无法发送数据;第二种情况下，节点接收到子节点发来的MTS请求。节点发送MTS清除需要同时满足以下条件:缓存区为空;所有从子节点接收到的MTS请求都已经清除;向父节点发送了MTS请求且还没有发送MTS清除。发送或接收到MTS请求的节点何隔3u个周期就唤醒一次，只有当其发送了MTS清除或所有子节点发来的MTS请求已经被清除时，节点才回到原来的占空比方式。上一页下一页返回3.3分配型MAC协议3.小结

DMAC协议是一种针对树状数据采集网络提出的能量高效、低延迟的MAC协议。DMAC协议根据节点在数据采集树上的深度为节点分配交错的活动/睡眠周期，在占空比方式下避免了数据多跳传输中的睡眠延迟。通过引入自适应占空比机制，DMAC协议能根据网络数据流量动态调整占空比。通过引入数据预测和MTS机制，DMAC协议能降低干扰造成的传输延迟。由于DMAC协议提出了一系列的假设，这在一定程序上限制了它的应用，但是对于符合假设的应用，DMAC协议能较好地满足性能需要。上一页返回3.4混合型MAC协议3.4.1基本思想

ZMAC是一种混合型的MAC协议，采用CSMA机制作为基本方法，在竞争加剧时使用TDMA机制来解决信道冲突问题。ZMAC引入了时间帧的概念，每个时间帧又分为若干个时隙。在ZMAC中，网络部署时每个节点执行一个进行时隙分配的DRAVD算法.时隙分配结束后，每个节点都会在时间帧中拥有一个时隙。分配了时隙的节点称为该时隙的所有者，所有者在对应的时隙中发送数据的优先级最高。和TDMA的策略不同，在ZMAC中，节点可以选择任何时隙发送数据。节点在某个时隙发送数据需要先监听信道的状态，但是该时隙的所有者拥有更高的发送优先级。发送优先级的设置通过设定退避时间窗口的大小来实现。时隙的所有者被赋子一个较小的时间窗口，所以能够抢占信道。通过这种机制，时隙在被所有者闲置时还能被其他的节点使用，从而提高信道利用率。此机制还隐含了根据信道的竞争情况在CSMA机制和TDMA机制间切换的方法。下一页返回3.4混合型MAC协议3.4.2关键技术1.邻居发现和时隙分配当一个节点启动后，就会开始一个邻居节点的发现过程，周期性发送PING消息。PING消息包含节点发现的所有一跳范围内的节点，可以在一定范围内随机发送。通过这个过程，每个节点可以获得自己两跳范围内的所有节点的信息，作为时隙分配算法的输入参数。时隙分配算法采用DRAVD算法，可以确保不会分配相同的时隙给两跳范围内的节点，从而使节点在给一跳邻居节点传送数据的时候不会被两跳邻居节点干扰。上一页下一页返回3.4混合型MAC协议2.本地时间帧交换ZMAC协议使用一种新的调度方法，这种方法采用一种局部的策略，每个节点维持一个本地的时间帧长度该时间帧和它的两跳范围内的节点数相适应。假设某个节点i的两跳范围内的节点数为Fi;那么节点i的本地时间帧长度就是2α。其中α是满足2α-1≤Fi

≤2α-1的一个整数。时隙的分配采用DRAND算法，假设分配给i的时隙是Si，可以保证节点i两跳范围内的任何节点不会使用Si。上一页下一页返回3.4混合型MAC协议3.传输控制在网络的初始化阶段完成之后，每个节点都同步到了一个全局的时钟，并且都拥有了自己的时间帧和时隙，可以对外提供服务。在ZMAC协议下，每个节点可以工作在两种模式下:低冲突级别(LCL,LowContentionLevel)和高冲突级别(HCL,HighContentionLevel)。当节点i有数据要传送的时候，它首先检查自己是否是现在时隙的拥有者，如果是的话，它就选择一个在[0,T0]之间的随机数作为退避时间。当退避时间到达后，它启动CCA来检查信道是否空闲，如果空闲的话，那么它就发送数据，否则它就等待，直到信道空闲，然后重复上面的过程。上一页下一页返回3.4混合型MAC协议如果节点i不是现在时隙的拥有者，并且它处于LCL状态，但是当前的时隙没有被其两跳邻居范围内的节点占用，在这两种情况下，节点首先等待一段时间T0，然后在[T0,Tn0]的退避窗口中选择一个随机的退避时间。当退避时间到达后，采用和前面一样的方法处理。还有第三种情况，那就是节点i处于HCL状态，在这种情况下节点会一直等待，直到遇到一个时隙，这个时隙要么被i所拥有，要么i的两条邻居节点没有任何节点使用它。上一页下一页返回3.4混合型MAC协议4.局部同步由于使用了载波监听和拥塞退避机制，在发生时钟错位的情况下，ZMAC协议比TDMA协议有更张的生命力，在完全失去时钟同步的情况下，ZMAC蜕化为CSMA协议。在低的冲突情况下，ZMAC可以不需要时钟同步，此时协议的性能和CSMA相仿。在高冲突的情况下，ZMAC协议需要在时间同步的基础上面实现HCL。ZMAC协议只需要维护临近的发送节点之间的时间同步，是一种局部同步。上一页下一页返回3.4混合型MAC协议在ZMAC协议中，每个发送数据的节点都要周期性地发送时间同步包，当一个节点收到该时间同步包后，它采用下面的计算公式来修正自己与发送时间同步包的节点的时间偏差，公式如下:式中，Cavgnew代表接收节点收到同步时间包后修正过后的时间，Cavglod代表接收节点现在的时间，Cnew代表发送时间同步包的节点的时间，βt是发送时间同步包的节点的可信因子，表不发送时间同步包的节点时钟的偏移程度。βt可以用下面的式子来计算:上一页下一页返回3.4混合型MAC协议3.4.3小结

ZMAC协议是一种混合型MAC协议，可以根据网络中的信道竞争情况来动态调整MAC协议所采用的机制，在CSMA和TDMA机制间进行切换。在网络数据量较小时，竞争者较少，协议工作在CSMA机制下;在网络数据量较大时，竞争者较多，ZMAC协议工作在TDMA机制下，使用拓扑信息和同步时钟信息来改善协议性能。ZMAC协议结合了竞争型MAC协议和分配型MAC协议的特点，能很好地适应网络拓扑的变化并提供均衡的网络性能。不过DRAVD算法较为复杂，这在一定程度上限制了ZMAC的应用。上一页返回3.5MAC层与跨层设计3.5.1MINA网络架构

MINA(multi-hopinfrastructurenetworkarchitecture)是一种基于跨层设计的大规模无线网络协议架构，网络通常由数百个低电量低运算能力的传感器节点组成，同时网络中还有一些基站节点，基站通常具有较强的运算能力，并且有充足的能量。如图3-24所示，在MINA架构中，节点分成三种类型:大量静止的低容量(内存、CPU,能量)传感器节点;少量手持移动节点(PDA);静止的大容量基站节点。下一页返回3.5MAC层与跨层设计在MINA架构中，网络流量类型主要为传感器节点到基站的上行链路，移动节点到移动节点之间的通信也是先通过上行链路先到达基站，然后再下行广播给相应的移动节点。网络数据帧主要有三种:控制帧，也就是从基站向传感器节点发送的控制信息，通过直接广播完成;信标帧，所有节点都需要在一个公共信道上周期性发送，包含有节点信息和本地TDMA分配给节点发送数据的时隙信息;数据帧，由传感器节点生成。上一页下一页返回3.5MAC层与跨层设计

分层架构:MINA架构中网络节点以层的形式来组织，距离基站跳数相同的节点组成一层。第一层节点距离基站跳数为一，第二层节点距离基站跳数为二，依此类推，如图3-24所示，网络共有三层。根据距离基站的跳数，每个节点的邻居