3.4.2　基于分配的MAC协议

竞争型MAC协议可提高事件传输的实时性和带宽的利用率，但随着网络负载流量的增加，控制分组与数据分组发生碰撞的概率也相应增加，从而使网络发生拥塞，耗费大量能量。而基于分配的MAC协议采用TDMA、CDMA、FDMA或SDMA等技术，将一个物理信道划分为多个子信道，然后将这些子信道划分给需要发送数据的节点，从而避免产生冲突。以前的基于分配的MAC协议一般都没有考虑到节省能量的问题，因此不适合用在无线传感器网络系统中。基于能量考虑，研究人员也提出了几种适用于无线传感器网络的MAC协议，这些协议有一些共同的优点，如不存在冲突，没有隐蔽终端等问题，容易进入睡眠状态，尤其适合能量有限的无线传感器网络。下面介绍几种经典的基于分配的无线传感器网络MAC协议。

1. SMACS协议

早在1999年，美国加州大学洛杉矶分校（UCLA）的研究人员就提出了一种自组织无线传感器网络协议架构，该架构针对规模庞大、节点移动性不强且能量有限的传感器网络应用设计了协议栈，其中包括SMACS协议。SMACS是一种分配的MAC协议，可以完成网络的建立和通信链路的组织分配。在此基础上，研究人员还提出了EAR算法，该算法实现了对网络中缓慢移动节点的移动性管理，使移动节点和静止节点之间实现无缝连接。通过在GloMoSim平台上进行仿真，SMACS的性能得到了验证。

1）基本思想

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

2）关键技术

（1）链路建立。SMACS协议引入了超帧的概念，用一个固定参数Tframe表示，网络中所有节点的超帧都有相同的长度。节点在上电后先进行邻居发现，每发现一个邻居，这一对节点就形成一个双向信道，即一个通信链路。在两个节点的超帧中为该链路分配一对时隙用于双向通信。随着邻居的增加，超帧慢慢地被填满。每对时隙都会选择一个随机的频点，减少邻近链路冲突的可能。这样全网很快就能在初始化建立链路，这种不同步的时隙分配被称为异步分配通信，下面将对链路如何建立进行举例说明。

异步通信分配机制如图3.10所示，节点A和节点D分别在Ta和Td时刻开始进行邻居发现，在发现过程完成后，两个节点约定一对固定的时隙分别进行发送和接收。此后在周期性的超帧中此时隙固定不变。节点B和节点C分别在Tb和Tc时刻开始进行邻居发现，执行上述同样的步骤，由于时隙的约定彼此独立，所以有可能发生重叠，如果各个时隙在同一频点上就会发生冲突。图3.10中如果节点D向节点A发送数据，和节点B向节点C发送数据在时间上有重叠，给两个时隙分配不同的频点，如分配fx给节点A、D，分配fy给节点B、C，就可以避免冲突。SMACS中每个节点有多个频点可选，在建立链路时都要选择一个随机的频点，这就大大减少了冲突发生的可能性。

（2）邻居发现和信道分配。为了比较清楚地阐述SMACS协议中的邻居发现机制，下面以举例的形式来说明。如图3.11所示，假设节点B、C、G进行邻居发现。这些节点在随机的时间段内打开射频模块，在一个固定的频点监听一个随机长度的时间。如果在此监听时间内节点没有接收到其他节点发出的邀请消息，那么随后节点将发送一个邀请消息。在图3.11中，节点C就是在监听结束后广播的一个邀请消息Type1。节点B和节点G接收到节点C发出的Type1消息后，等待一个随机的时间，然后各自广播一个应答消息Type2。如果两个应答消息不冲突，节点C将接收到节点B和节点G发来的邀请应答。节点C在这里进行一个选择，可以选择最早到达的应答者，也可以选择接收信号强度最大的应答者。在选择了应答者后，节点C将立即发送一个Type3消息通知哪个节点被选择。此处选择最早到达的节点B作为应答者，节点G将关闭射频部分进入睡眠状态，并在一个随机的时间后重新进行邻居发现。

如果节点C已经选择了邻居，将在消息Type3中携带分配信息，该信息包含节点C的下一个超帧的起始时间。在收到该分配消息后，节点B将和本地的超帧起始时间进行比较，得到一个时间偏移，并找出两个共同的空闲时间段作为时隙对，分配给节点B和节点C之间的链路。在确定了时隙对后，节点B选择一个随机的频点，将时隙对在超帧中的位置信息以及选择的频点通过消息Type4发送给节点C。经过这些测试信息的成功交换后，节点B和节点C之间就完成了时隙分配和频率选择。

在SMACS形成的网络中，与超帧同步的节点组成一个子网，如图3.10所示，节点A、节点D和节点B、节点C分别组成子网。随着邻居的增加，子网的规模会变大，并且会和其他子网的节点建立链路，实现整个网络的无缝连接。两个不同子网的节点在建立通信链路时，如果超帧有重叠的空闲时段，可以为新链路分配时隙，则可以成功建立链路；否则，节点只能放弃并寻找其他节点来建立链路。

3）算法描述

在静态的MAC协议进行类似于TDMA帧结构的时隙分配时，静止的节点需要周期地广播邀请信息，这样可以周期地进行邻居发现，允许新节点加入网络，使协议适应网络拓扑的变化。邀请信息不需要在每个超帧广播，每间隔固定个数的超帧再多进行一次广播即可。移动节点侦听这些邀请信息，所以这些邀请信息也可以作为移动节点的引导信号。移动节点根据这些引导信号决定最佳路线，所以SMACS协议将邀请信息作为EAR算法的触发器。移动节点可以从邀请信息中获得信噪比、节点地址、功率等信息。为了记录相邻节点的信息，移动节点都要保持一个邻居记录，每条记录包含了建立、保持和取消一个通信链路所需要的信息。同样地，静止节点也要保存一个邻居记录，每条记录只包含与该节点建立链路的移动节点的地址，如果链路取消，则需要删除对应节点的记录信息。建立和取消通信链路的过程由移动节点分配。

EAR算法定义了一种新的信令机制，主要使用以下4种消息：Broadcast Invite（BI），静止节点邀请其他节点加入；Mobile Invite（MI），移动节点响应BI并请求建立连接；Mobile Response（MR），静止节点取消连接，不需要响应；Mobile Disconnect（MD），移动节点取消连接。移动节点和静止节点通过交换信令实现EAR算法的机制，也就是如何建立移动节点和静止节点之间通信链路的机制。主要有以下步骤：

（1）静止节点会每间隔固定个超帧发送一次BI消息，移动节点在接收到静止节点的BI消息后将开始连接过程。首先，静止节点被记录，移动节点在接收BI消息时可以得到链路的质量，根据链路质量决定是否向静止节点发起连接请求。如果不发起连接请求，相关的静止节点信息只是简单地保存在邻居记录中；如果发起连接请求，则移动节点回复一个MI消息，等待响应，同时继续侦听其他BI消息。移动节点如果接收到其他相邻节点的BI信息，暂时将对应相邻节点消息保存到邻居记录，如果直到记录表被填满的时候，还接收到新节点的BI信息，移动节点会将其链路质量（通过信道的SNR值大小判断）和当前记录表中最差链路质量相比较，决定是否替换相应的相邻节点信息。

（2）静止节点在接收到MI消息后需要检查是否可以建立连接。如果可以建立，则静止节点在TDMA帧中选择可用的时隙，并回复一个确认信息给移动节点，表示接收建立连接请求。同时，静止节点会记录此移动节点的地址信息。如果没有可用的时隙，则无法建立连接，静止节点回复一个拒绝信息。所有的回复信息都包含在MR消息中。

（3）连接建立后，移动节点在移动过程中会接收到新的相邻静止节点发送的BI消息，移动节点会根据信道质量选择淘汰相邻节点记录中连接质量较差的相邻节点。如果移动节点在移动过程中远离了已经建立连接的静止节点，则连接质量将会下降，最后将被淘汰，这就需要取消已经建立的连接（发送MD消息）。决定是否取消和建立连接都需要根据相应的门限值，当一个已建立连接的信道SNR值低于取消连接门限值时，就需要发送MD消息给对应的静止节点以取消连接。设置较大的建立连接门限值能提高网络连接质量，但会减少网络中的通信链路；设置较大的取消连接门限值能提高网络的平均SNR值，但移动节点会更频繁地取消连接，增加控制开销产生的能量损耗。

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

2. TRAMA协议

TRAMA（Traffic Adaptive Medium Access，流量自适应媒体访问）协议是较早提出的基于分配的WSN MAC协议，其基本思想源于NAMA协议，在NAMA协议的基础上引入了睡眠机制，该协议的信道分配机制不仅能够保证能量效率，而且对于带宽利用率、延迟和公平性也有很好的支持。通过在QualNet平台上的仿真，将TRAMA协议与S-MAC、NAMA等协议进行了分析比较。

1）基本思想

TRAMA协议采用了流量自适应的分布式选举算法，节点交换两跳内的邻居信息，在传输分配时指明在时间顺序上哪些节点是目的节点，然后选择在每个时隙上的发送节点和接收节点。TRAMA协议由三部分组成，其中邻居协议（Neighbor Protocol，NP）和分配交换协议（Schedule Exchange Protocol，SEP）允许节点交换两跳内的邻居信息和分配信息；自适应选举算法（Adaptive Election Algorithm，AEA）利用邻居和分配信息选择当前时隙的发送者和接收者，让其他与此次通信无关的节点进入睡眠状态以节省能量。

TRAMA协议将一个物理信道分成多个时隙，通过对这些时隙的复用为数据和控制信息提供信道。图3.12所示为TRAMA协议信道的时隙分配情况。每个时间帧分为随机接入和分配接入两部分，随机接入时隙也称为信令时隙，分配接入时隙也称为传输时隙。由于无线传感器网络传输速率普遍较低，所以对于时隙的划分以毫秒为单位。传输时隙的长度是固定的，可根据物理信道带宽和数据包长度计算得出。由于控制信息量通常比数据信息量要小得多，所以传输时隙通常为信令时隙的整数倍，以便于同步。

2）关键技术

（1）邻居协议（NP）。在无线传感器网络中，由于节点失效或者新节点加入等现象存在，网络拓扑在动态地变化，TRAMA协议需要适应这种变化。在TRAMA协议中，节点启动后处于随机接入时隙，在此时隙内节点为接收状态，可以选择一个随机时隙发送指令。随机接入时隙的长度选择可根据应用来决定，如果网络移动性不强，拓扑相对稳定，则该时隙较短；否则就需要适当延长该时隙，但该时隙的延长会增加空闲侦听的能量损耗，降低网络的能量效率。节点之间的时钟同步信息也是在随机接入时隙中发送的。由于在随机接入时隙中各个节点都可以选择随机接入时隙进行发送，控制信息有可能发生碰撞而丢失，为了减少碰撞，随机接入时隙的长度和控制信息的重传次数都要进行相应的设置。对于一个有N个两跳邻居的节点，当控制信息的重传次数为7且重传间隔为1.44N时能保证99%的成功率，因此随机接入时隙的长度可设置为7×1.44×N。

通过在随机接入时隙中交换控制信息，邻居协议实现了相邻节点信息的交互。图3.13所示为控制信息帧的帧头格式。控制信息中携带了增加的邻居的更新，如果没有更新，控制信息作为通知邻居自己存在的信标。每个节点发送关于自己下一跳邻居的增加更新，用来保持邻居之间的连通性。如果一个节点在一段时间内都没有再收到某个邻居的信标，则该邻居失效。由于节点知道下一跳邻居和这些邻居的下一跳邻居的信息，所以网络中每个节点都能交换两跳邻居信息。

（2）分配交换协议（SEP）。分配交换协议用于建立和维护发送者与接收者选择时隙需要的分配信息。首先每个节点生成分配信息，然后通过广播实现分配信息交换和维护。

分配信息生成的过程为，节点根据高层应用产生数据的速率计算出一个分配间隔SCHEDULE_INTRVAL，该间隔代表了节点能够广播分配信息给相邻节点的时隙个数，然后在[t，t+SCHDULE_INTRVAL]内，节点计算在其两跳邻居范围内具有最高发送优先级的时隙数，这些时隙称为赢时隙。由于在这些时隙中节点可能被选为发送者，故节点需要通知这些时隙中数据的接收者。当然，如果节点没有带发送的数据，也需要通知邻居它将放弃相关时隙，其他需要发送数据的节点可以使用这些空闲时隙。在一个分配间隔内最后一个置1的赢时隙称为变更时隙，用于广播节点下一次分配间隔内的时隙分配情况。

节点通过分配帧广播分配信息，其过程为节点通过邻居协议获得两跳邻居信息，分配帧不需要指定目的地址，通过位图来指定接收者。位图中每一位对应一个一跳相邻节点，位图的长度等于节点的一跳邻居数，需要该节点接收数据则将对应位设置为1，这样可以方便地实现单播、组播和广播。节点根据当前的赢时隙分布形成位图，将没有数据要发送的赢时隙对应位设置为0，否则设置为1。图3.14所示为分配帧格式，其中SourceAddr是发送分配帧的节点地址，Timeout是从当前时隙开始本次分配有效的时隙数，Width是邻居位图长度，NumSlots是总的赢时隙数。

此外，节点采用携带机制，在每个节点的数据包中都携带有节点的分配摘要，如图3.14所示，减少广播冲突对分配交换的影响。分配摘要带有该分配的Timeout、NumSlots和位图信息。

节点需要维护下一跳邻居的分配信息，过程为分配信息的交换通过分配摘要来完成，如果节点不是数据的目标，那么节点的分配处于不同步状态，直到节点根据发送者发来数据中的分配摘要更新分配。

3）算法描述

为了提高能量效率，TRAMA尽可能地让节点处于睡眠状态，通过重用已经分配但未使用的时隙来提高带宽利用率。在分配接入周期任意一个给定的时隙t中，所有节点的状态是由该节点的两跳邻居信息和该节点的一跳邻居发布的分配信息来确定的，有发送、接收、睡眠三种状态。

在相关文献提出的NCR算法中，如果节点在其竞争集中有最高的优先级，则选择该节点作为发送者。节点u的竞争集是节点所有两跳邻居的集合，节点u在时隙t的优先级定义为一个伪随机hash函数，由节点的地址u和时隙t共同决定，即prio(u, t)=hash(u⊕t)。在任意一个给定的时隙，节点u处于发送状态只有两种可能：节点u有最高优先级或节点u有数据要发送。当节点处于接收状态时，节点是当前某个发送者的目标节点，否则节点就进入睡眠状态。每个节点通过AEA算法来确定当前应处于何种状态。AEA算法的伪码描述如图3.15所示，表3.1列出了AEA算法描述中一些基本术语和符号。

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