无线传感器网络MAC协议研究进展

ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn Journal of Software, Vol.19, No.2, February 2008, pp.389−403 http://www.jos.org.cn DOI: 10.3724/SP.J.1001.2008.00389 Tel/Fax: +86-10-62562563 © 2008 by Journal of Software. All rights reserved. 无线传感器网络MAC协议研究进展∗ 蹇 强+, 龚正虎, 朱培栋, 桂春梅 (国防科学技术大学 计算机学院,湖南 长沙 410073) Overview of MAC Protocols in Wireless Sensor Networks JIAN Qiang+, GONG Zheng-Hu, ZHU Pei-Dong, GUI Chun-Mei (School of Computer, National University of Defense Technology, Changsha 410073, China) + Corresponding author: Phn: +86-731-4516394, E-mail: 2002qiang@vip.sina.com, http://www.nudt.edu.cn Jian Q, Gong ZH, Zhu PD, Gui CM. Overview of MAC protocols in wireless sensor networks. Journal of Software, 2008,19(2):389−403. http://www.jos.org.cn/1000-9825/19/389.htm Abstract: In wireless sensor network, medium access control (MAC) has been at the core of effective communication. Since the traditional MAC layer protocols don’t adapt themselves to the performance traits and technique request of wireless sensor network, many MAC protocols for wireless sensor network are studied. Design principles and classification methods for MAC protocols in wireless sensor network are summarized, and fundamental mechanism of each recent representative MAC protocol is analyzed in detail. The characteristics, performance, and application areas of various MAC protocols in wireless sensor network are adequately compared. Finally, the status of current research development are concluded and the open research issues on MAC layer design are pointed out. Key words: wireless sensor network (WSN); MAC (medium access control) protocol; TDMA; contention protocol; cross-layer design 摘 要: 在无线传感器网络体系结构中,MAC(medium access control)协议是保证网络高效通信的重要协议.无线 传感器网络有着与传统无线网络明显不同的性能特点和技术要求,传统无线网络 MAC 协议无法应用于传感器网 络,各种针对特定传感器网络特点的 MAC 协议相继提出.归纳无线传感器网络 MAC 协议的设计原则和分类 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 , 分析当前典型的各类MAC协议的主要机制,详细比较这些协议的特点、性能差异和应用范围.最后总结无线传感器 网络MAC协议的研究现状,指出未来的研究重点. 关键词: 无线传感器网络;MAC协议;TDMA;竞争协议;跨层设计 中图法分类号: TP393 文献标识码: A 当前,信息技术可以实现信息的海量存储、高速传输和快速处理,但信息获取却仍未达到自动化水平.微传 感器技术、微电子技术、无线通信技术以及计算技术的进步,极大地推动了集信息采集、处理、无线传输等功 能于一体的无线传感器网络(wireless sensor network,简称 WSN)的发展.WSN正在给人类生活和生产的各个领 ∗ Supported by the National High-Tech Research and Development Plan of China under Grant No.2005AA121570 (国家高技术研究 发展计划(863)); the National Basic Research Program of China under Grant No.2003CB314802 (国家重点基础研究发展计划(973)) Received 2007-03-02; Accepted 2007-09-13 390 Journal of Software 软件学报 Vol.19, No.2, February 2008 域带来深远影响,在国防军事、医疗卫生、环境监测、城市交通以及空间探索等领域具有广阔的应用前景[1,2]. 目前,国内外 WSN研究主要集中于网络协议、能量、定位、可靠性、网络架构以及数据处理等问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 ,网络 协议的研究是其中的热点之一.而作为 WSN网络协议栈重要基础架构的介质访问控制(medium access control, 简称 MAC)协议,决定着无线信道的使用方式,负责为节点分配无线通信资源,直接影响网络整体性能,成为 WSN 网络协议研究的重中之重.目前,已有大量针对 WSN 不同特点和具体应用的 MAC 协议相继提出.为了吸 取经验、分析不足,我们对当前 WSN中典型的 MAC协议进行总结和分类,详细分析和比较这些协议的核心机 制、性能特点和应用范围,并指出未来的研究策略与重点,以期为 WSN MAC协议的进一步研究提供参考. 1 WSN MAC协议概述 1.1 WSN MAC协议设计原则 在 WSN 中,节点能量有限且难以补充.为保证 WSN 长期有效工作,MAC 协议以减少能耗、最大化网络生 存时间为首要设计目标;其次,为了适应节点分布和拓扑变化,MAC 协议需要具备良好的可扩展性;传统无线网 络关注的实时性、吞吐量及带宽利用率等性能指标成为次要目标;此外,WSN节点一般属于同一利益实体,可为 系统优化作出一定的牺牲,因此,能量效率以外的公平性一般不作为设计目标[3],除非多用途 WSN重叠部署. WSN中的能量消耗主要包括通信能耗、感知能耗和计算能耗.其中,通信能耗所占比重最大.因此,减少通信 能耗是延长网络生存时间的有效手段.大量研究表明,通信过程中主要能量浪费存在于:冲突导致重传和等待重 传;非目的节点接收并处理数据形成串音;发射/接收不同步导致分组空传(overemitting)[4];控制分组本身开销; 无通信任务节点对信道的空闲侦听等.此外,无线发射装置频繁发送/接收状态切换也会造成能量迅速消耗[5]. 基于上述原因,WSN MAC 协议通常采用“侦听/休眠”交替的信道访问策略,节点无通信任务则进入低功耗 睡眠状态,以减少冲突、串音和空闲侦听;通过协调节点间的侦听/休眠周期以及节点发送/接收数据的时机,避免 分组空传和减少过度侦听;通过限制控制分组长度和数量减少控制开销;尽量延长节点休眠时间,减少状态切换 次数.同时,为了避免 MAC协议本身开销过大,消耗过多的能量,MAC协议尽量做到简单、高效. 当然,影响传统无线网络 MAC协议设计的一些基本问题,如隐藏终端和暴露终端问题、无线信道衰减和无 规律冲突(interference irregularity)问题等,在 WSN MAC协议中依然存在,需要解决. 1.2 WSN MAC协议分类 WSN与应用高度相关,研究人员从不同的方面出发提出多种 MAC协议.但目前尚无统一分类方式.可根据 信道分配方式、数据通信类型、性能需求、硬件特点以及应用范围等策略,使用多种分类方法对其分类: (1) 根据信道访问策略的不同可分为竞争协议、调度协议和混合 MAC 协议[6].竞争协议无须全局网络信 息,扩展性好、易于实现,但能耗大;调度协议有节省优势和延时保障,但帧长度和调度难以调整,扩展性 差,且时钟同步要求高;混合协议具有上述两种 MAC协议的优点,但通常比较复杂,实现难度大. (2) 根据使用单一共享信道还是多信道可分为单信道 MAC 协议和多信道 MAC 协议.前者节点体积小、 成本低,但控制分组与数据分组使用同一信道,降低了信道利用率;后者有利于减少冲突和重传,信道 利用率高、传输时延小,但硬件成本高,且存在频谱分配拥挤问题. (3) 根据数据通信类型可分为单播协议和组播/聚播(convergecast)协议.前者适于沿特定路径的数据采集, 有利于网络优化,但扩展性差;后者有利于数据融合与查询,但时钟同步要求高,且数据冗余,重传代 价高. (4) 根据传感器节点发射器硬件功率是否可变可分为功率固定 MAC 协议和功率控制 MAC 协议.前者硬 件成本低,但通信范围相互重叠,易造成冲突;后者有利于节点能耗均衡,但易形成非对称链路,且硬件 成本增加. (5) 根据发射天线的种类可分为基于全向天线的 MAC 协议和基于定向天线的 MAC 协议.前者成本低、 易部署,但增加了冲突和串音;后者有利于避免冲突,但增加了节点复杂性和功耗,且需要定位技术的 蹇强 等:无线传感器网络MAC协议研究进展 391 支持. (6) 根据协议发起方的不同可分为发送方发起的 MAC 协议和接收方发起的 MAC 协议.由于冲突仅对接 收方造成影响,因此,接收方发起的 MAC 协议能够有效避免隐藏终端问题,减少冲突概率,但控制开销 大、传输延时长;发送方发起的 MAC 协议简单、兼容性好、易于实现,但缺少接收方状态信息,不利 于实现网络的全局优化. 此外,根据是否需要满足一定的 QoS支持和性能要求,WSN MAC协议还可分为实时 MAC协议、能量高效 MAC协议、安全 MAC协议、位置感知 MAC协议、移动 MAC协议等. 2 WSN MAC协议分析 传统竞争协议如 IEEE 802.11 DCF[7],建立在 MACAW[8]协议基础之上,因其简单性和健壮性,被广泛应用于 WLAN和 Ad hoc网络.但 IEEE 802.11节点空闲侦听能耗过大,不适于 WSN.虽然 802.11提供功率节省(PS)模 式,但主要为单跳网络设计,多跳网络下部署易造成网络分割.Tseng等人[9]改进了 PS模式,提出了 3种睡眠调度 机制,但无法实现节点调度同步,冲突概率、控制开销和传输延时都很大.还有研究人员从其他角度出发,对 Ad hoc MAC协议进行改进,但若作为WSN MAC协议则都差强人意.与竞争协议相比,传统调度协议虽能实现无冲 突通信,具有一定的节能优势,但总要在延时、吞吐量和能量高效之间加以折衷,扩展性差是一个大问题,实际部 署中难以调整帧长度和时槽分配,无法有效应对节点失效和拓扑变化.其中,部分协议(如 LEACH[10]及各变种) 组织分簇结构,在一定程度上缓解了上述问题,但簇的建立和维护增加了存储和控制开销,且同步精度要求高, 实现难度大. 近年来,学术界提出了众多 WSN专用 MAC协议,部分协议已经在实验环境甚至实际系统中得到应用和验 证(如 B-MAC[11]和 EMACs[12]等).我们对这些协议进行研究,选取了部分较为重要的和近期提出的 MAC 协议, 对其核心机制、特点和优缺点等进行了分析和比较.表 1列举了本文涉及的 WSN MAC协议和部分 Ad hoc网 络 MAC 协议(用粗线区分开).为了便于比较,我们基本上采用前述第 1 种方法对其进行分类,其中,跨层设计的 MAC 协议已经突破了传统网络协议栈中 MAC 协议的实际内涵,不少协议已经兼备了链路层信道访问控制和 网络层路由功能.为此,我们将这些协议单独列举出来.下面将对表 1中阴影部分的协议进行重点分析. Table 1 MAC protocols for wireless (sensor) networks 表 1 无线(传感器)网络 MAC协议 Contention-Based MAC Schedule-Based MAC Hybrid MAC Cross layer designed MAC MACA-BI (1997) IEEE 802.11 DCF (1997/1999) PAMAS (1999) Bluetooth (1999) SMACS (1999) ADAPT (1999) BASIC (2001) SEEDEX (2001) ARC (2001) Woo & Culler (2001) SMACS/ EAR (2000) LEACH (2001) DEANA (2001) NAMA, PAMA (2001) Meta-MAC (2001) OAR (2002) Low power listening (2002) S-MAC, STEM (2002) Preamble sampling (2002) Arisha (2002) Energy-Aware TDMA-based MAC (2002) HTDMA (2002) T. Holliday, et al. (2002) PCSMAC (2003) SIFT (2003) T-MAC (2003) PCMAC (2003) ER-MAC (2003) TRAMA (2003) EMACs (2003) DEMAC (2003) Amre El-Hoiydi (2003) GeRaF (2003) MINA (2003) DSMAC (2004) AC-MAC (2004) S-MAC+ (2004) B-MAC (2004) TDMA-W (2004) BMA (2004) D-MAC (2004) LooseMAC (2004) FPS (2004) S.Cui & R.Madan (2004) P-MAC (2005) TEA-MAC (2005) TEEM (2005) WiseMAC (2005) RTMAC (2005) SSTDMA (2005) Z-MAC (2005) AIMRP (2005) O-TBMA (2005) X-MAC (2006) ArDez (2006) D-STDMA (2006) A. Kesha, et al. (2006) Funneling-MAC (2006) SARA-M (2006) 2.1 基于竞争的MAC协议 竞争协议采用按需使用信道的方式,当节点需要发送数据时,通过竞争方式使用无线信道,若发送的数据产 生了冲突,就按照某种策略重发数据,直到数据发送成功或放弃发送为止.在 WSN中,睡眠/唤醒调度、握手机制 设计和减少睡眠延时是竞争协议重点考虑的三大问题.一般而言,竞争协议对时钟同步精度要求没有调度协议 392 Journal of Software 软件学报 Vol.19, No.2, February 2008 高,但为了实现及时可靠通信并保证协议能量高效,仍需为睡眠/唤醒调度和控制分组安排合理的时序关系[13]. 2.1.1 S-MAC(sensor-MAC)[14]和T-MAC(timeout-MAC)[15]协议 这两个协议均采用节点周期睡眠调度,不同点是调度周期中节点活跃时间所占的比例(占空比). S-MAC[14]基本思想是:节点周期睡眠以减少空闲侦听,苏醒后侦听信道,判断是否需要发送或接收数据.具 有相同睡眠调度的节点形成一个虚簇 ,既保证相邻节点调度周期同步 ,又满足可扩展性 .为了避免冲突和串 音,S-MAC 采用与 802.11 类似的虚拟和物理载波侦听机制以及 RTS/CTS 通告机制,且在控制分组中捎带数据 传输剩余时间,邻居节点据此计算 NAV,并进入睡眠状态,直到长消息发送完毕为止. S-MAC成功实现周期睡眠调度,显著减少了空闲侦听,能够较好地满足WSN的节能需求.其后,大多数竞争 协议延续这一思想,并将其作为基准协议进行比较.但 S-MAC 协议帧长度和占空比(duty cycle)固定,帧长度受 限于延迟要求和缓存大小,活跃时间主要依赖于消息速率,特别是当网络负载较小时,空闲侦听时间仍然过长. 周期睡眠造成通信延迟累加.尽管 S-MAC 改进版本[16]采用流量自适应侦听机制将睡眠延时减少一半以上,但 周期睡眠造成的传输延迟仍然十分显著.因此,S-MAC不适合健康监测、目标跟踪等实时性要求较高的应用. T-MAC[15]针对 S-MAC的上述缺陷进行改进.定义了 5个激活事件,如果在 TA时间内没有发生任一激活事 件,则节点认为信道空闲,节点进入睡眠状态.每一帧中的活跃时间可根据网络流量动态调整,增加了睡眠时间. 但随机睡眠带来早睡问题,增加了延时.T-MAC 为此提供两种解决 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 :未来请求发送(FRTS)和满缓冲区优先 (FBP),但仍存在缺陷:FRTS 可以减少延时和提高吞吐率,但 DS 分组和 FRTS 分组带来额外的通信开销;FBP 方 法减少了早睡发生的可能性,并具有简单流量控制作用,但当网络流量较大时增加了冲突概率.图 1对 S-MAC和 T-MAC的基本协议机制进行了比较,其中箭头分别代表发送和接收分组. Fig.1 Basic protocol scheme of S-MAC and T-MAC 图 1 S-MAC和 T-MAC基本协议机制 2.1.2 B-MAC[11],WiseMAC[17]和X-MAC[18] S-MAC 和 T-MAC 通过精确的时序关系控制节点的睡眠调度,因此对时钟同步的要求较高.下面 3 个协议 则更多地利用了竞争协议对无线信道的“抢占”原则,睡眠调度更具主动性,同时减少对时钟同步精度的依赖. B-MAC[11]协议使用扩展前导和低功率侦听(LPL)技术实现低功耗通信,采用空闲信道评估技术进行信道 裁决.节点在发送数据分组之前先发送一段长度固定的前导序列.为避免分组空传,前导序列长度要大于接收方 睡眠时间.若节点唤醒后侦听到前导序列,则保持活跃状态,直到接收到数据分组或信道变得再次空闲为止. B-MAC 无须共享调度信息,可以有效缩短唤醒时间,因此,在吞吐量和延时等方面优于 S-MAC,但在减少能 量消耗上并没有太大优势.较长的固定前导序列造成发送方和接收方能耗增加和发送方邻居节点串音.在前导 序列结束后才接收到有效数据,平均接收延时为前导长度的一半.文献[19]对 B-MAC 和 S-MAC 等协议进行比 较后指出,B-MAC更适合于延时要求不高的应用,在延时要求较高的情况下,S-MAC等同步 MAC协议更节能. 与 B-MAC 不同,WiseMAC[17]动态调整前导长度.接收节点在最近 ACK 报文中捎带下次唤醒时间,使发送 方了解每个下游节点采样调度,进而缩短前导长度.为了减少固定前导冲突概率,采用随机唤醒前导.考虑到时 钟漂移,前导长度 Tp=min(4Lθ,Tw),其中,θ是节点时钟漂移速度,L 为从收到上次确认到现在的时间,Tw是信道侦 听时间间隔.WiseMAC中采样调度表存储开销较大,当网络密度大时尤为突出.WiseMAC使用非坚持 CSMA减 少空闲监听,无法克服隐藏终端问题.WiseMAC宜用作网络负载较轻的结构化网络中下行链路 MAC协议. X-MAC[18]协议再次缩短前导序列的长度,同时引入握手机制进一步减小发送前导序列的能量开销.前导序 Active state Sleep state Normal S-MAC Active time Normal TA TA TA T-MAC Sleep time 蹇强 等:无线传感器网络MAC协议研究进展 393 列由若干较小的频闪前导(strobed preamble)组成,其中包含目的地址,非接收节点尽早丢弃分组并睡眠.利用频 闪前导之间的时间间隔,接收节点向源节点发送早期确认.发送节点收到早期确认后立刻发送数据分组,从而避 免发送节点过度前导和接收节点过度侦听.图 2 比较了 B-MAC,WiseMAC 等一般扩展前导 MAC 协议和 X-MAC 的时序关系.X-MAC 还设计了一种自适应算法,根据网络流量变化动态调整节点的占空比以减少单跳 延时.每个节点统计 n×t 时间内接收到的报文数量 k,并根据图 3 动态调整占空比.仿真实验[18]表明,这种次优方 法的近似比不小于 98.7%.X-MAC在能量效率、吞吐量和延时等性能上优于 B-MAC和 WiseMAC.与传统的基 于 LPL 的 MAC 协议相比,X-MAC 更易于被支持分组无线发射器的无线传感器节点(如 MicaZ[20]和 iMote[21]) 所实现,但 X-MAC对时钟同步精度要求高于 WiseMAC,分组长度、数据发送速率等协议参数还需进一步确定. Long preamble Data Target address in data header Receive data Extended wait time Data Receive data Short preambles with target address information LPL sender LPL receiver X-MAC sender X-MAC receiver Time & energy saved Time Time Time Time Energy-Optimal sleep and listen times (ms) rela Load: Expected packets per second (log sc tive to load ale) Listen ( 2.1.3 PMAC[22]和Sift[19] 在基于竞争的 MAC 协议中 ,根据网络流量决定占空比是提高能量效率的有效手段 ,PMAC (pattern-MAC)[22]协议和 Sift[19]协议采用的方法为我们提供了一种新的思路. PMAC[22]根据网络负载和流量模式自适应调整睡眠调度.时间被分为连续的超时间帧(STF),每个 STF包含 两个子帧:模式循环时间帧(PRTF)和模式交换时间帧(PETF).PRTF 由 N 个时隙和 1 个附加时隙组成,节点根据 模式(pattern)决定在每个时隙睡眠或唤醒,模式用一个比特串 0m1表示,表示连续m个时隙睡眠和 1个时隙唤醒. 在附加时隙,所有节点均唤醒.PETF 也分为多个时隙,用于与邻居节点交换模式.在首个 PRTF,每个节点均唤醒, 即模式为 1.然后,在每个模式位为 1的时隙考察是否有数据需要发送,如果没有,则采用类似于 TCP慢启动算法 的方法逐步增加模式中 0 位的数量,即增加节点休眠时间;如果有数据需要发送,则将模式恢复为 1.在 PETF 阶 段,节点竞争信道并广播自己的模式,然后根据收集到的邻居节点模式计算下一个 PRTF中的睡眠调度. 在 PMAC中,当网络流量较小时节点睡眠时间更长,能量浪费更少;模式交换保证只有传输路径上的节点需 要唤醒以转发数据,减少了邻居节点过度侦听和分组冲突.但通过广播交换模式增加冲突概率;邻居节点间协商 产生睡眠-唤醒调度,收敛时间长;协议各时隙长度、模式位数、竞争窗口大小等参数未确定. Kyle等人[19]提出的 Sift协议针对事件驱动 WSN设计,其目标是:若 N个节点同时监测到同一事件,则只保 证其中 R 个节点能够在最小时间内无冲突成功发送数据,抑制剩余 N−R 个节点的发送.Sift 中竞争窗口 CW 长 度固定,节点并不选择发送的时隙,而是选择不同时隙的发送概率.如果信道空闲,则逐步增加每个时隙的发送 概率;如果有其他节点使用该时隙发送数据,则重新计算发送概率.节点第 r个时隙的发送概率根据 公式 小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载 (1)计算: (1 ) , 1,..., 1 CW r r CWP r α α α α − − = × = − CW (1) 其中, 1 1CWNα − − = .经证明,协议满足如下性质:(1) 当存在 N个竞争节点时,有且仅有 1个节点在第 1个时隙成功 ms) Sl ee p (m s) 8 7 6 5 4 3 2 1 Sleep (ms)1600 1400 1200 1000 800 600 400 200 0 1800 0.01 0.1 1 10 0.01 0.1 1 10 Li st en (m s) Fig.2 Timelines of LPL’s extended Fig.3 Energy-Optimal sleep and lis ACK 100 100 preamble and X-MAC’s 图 2 低功率侦听扩展前导与 X-MAC时序 ten times 图 3 能量优化睡眠和侦听时刻 394 Journal of Software 软件学报 Vol.19, No.2, February 2008 发送的概率大;(2) 从第 2个到第 r−1个时隙,每个时隙中有且仅有 1个节点成功发送的概率也大. Sift 是一个新颖而简单的基于竞争窗口的 MAC 协议,能满足事件驱动 WSN 数据突发性和冗余性,但未考 虑如何减少空闲侦听.协议简单地认为,当节点监听到 R 个 ACK 后就取消相应事件报告,对如何选择 R 个节点 及时无冲突发送并没有进一步研究.协议要求时钟严格同步,因此只适于在 WSN局部区域内(如簇内)使用. 2.2 基于调度的MAC协议 调度协议通常以 TDMA 协议为主,也可采用 FDMA 或 CDMA 的信道访问方式,考虑到硬件成本和计算复 杂度,在WSN中,后两种方式 MAC协议较少.调度协议基本思想是:采用某种调度算法将时槽/频率/正交码映射 为节点,这种映射导致一个调度决定一个节点只能使用其特定的时槽/频率/正交码(1 个或多个)无冲突访问信 道.因此,调度协议也可称作无冲突 MAC 协议或无竞争 MAC 协议.调度可静态分配,也可动态分配.为提高协议 可扩展性和信道利用率,往往采用分布式算法实现信道重用,但设计高度信道重用有效调度是 NP-难问题[23]. 2.2.1 Cluster-Based MAC 在 TDMA 协议中,时槽分配需要一定的全局视图,计算量较大.很多 TDMA 协议利用了分簇网络便于管理 维护、对系统变化反应迅速的特点,将时槽计算和分配任务交由簇头节点承担,既能避免扩大计算规模,又有利 于实现信道重用.下面两个协议就具有这样的特点. Energy-Aware TDMA-Based MAC[24]协议包含 4个主要阶段:在数据发送阶段,活跃节点在分配的时槽根据 转发表向网关节点发送/转发数据,非活跃节点保持睡眠,除非向簇头报告状态或接收路由广播;在更新阶段,节 点在分配的时槽向簇头报告各自状态(剩余能量、位置等);在基于更新的重路由阶段,簇头根据接收信息重新计 算时槽和更新转发表,并发布调度;在事件触发重路由阶段,当拓扑变化或某节点能量小于阈值时,簇头产生新 调度并发送给簇内节点.协议提供两种时槽分配算法:宽度时槽分配和深度时槽分配.宽度分配法为簇内节点提 供连续时槽,减少硬件切换次数;深度分配法有利于数据及时上传,减小报文丢失概率. 在 BMA 协议[25]中,节点根据剩余能量选举簇头.当选簇头广播当选通告,其余节点根据接收信号强度决定 加入哪个簇.稳定状态阶段由多个时间帧组成,每个时间帧又分成竞争时槽、数据传输时槽和空闲时槽 3 部分. 节点在竞争时槽获得数据传输时槽,并在数据传输时槽向簇头报告状态.簇头收集成员节点状态信息并发布调 度,每个有数据发送的节点获得一个确定的发送时槽,且只在发送时槽向簇头节点发送数据,其余时间休眠. 上述两个协议各个阶段时长固定,无法适应网络流量变化,降低了信道利用率.集中式时槽分配算法要求簇 头节点必须具备很强的通信和计算能力,能耗很大,对时钟同步要求高.如何合理选择簇头有待深入研究. 2.2.2 TRAMA(traffic-adaptive MAC)[26]和TDMA-W(TDMA-wakeup MAC)[27] 固定的时槽分配调度虽然能够实现无冲突通信,但节点空闲侦听的能耗很大,且网络负载越小,空闲侦听比 例越大.因此,很多 TDMA协议加入流量自适应技术,动态调整占空比,进一步减少能量开销. TRAMA[26]协议的目的是保证节点根据实际流量使用预先分配的时槽无冲突通信,没有通信任务的节点转 入睡眠状态,从而减少冲突和空闲侦听导致的能量消耗.所有节点首先获得一致的两跳内邻居信息并同步.每个 节点根据报文产生速率计算调度周期 SI,并根据报文队列长度使用 AEA算法选择[t,SI]中具有两跳内最高优先 权的若干个时槽,即获胜槽(winning slots).节点使用获胜槽发送数据并使用位图指定接收者,最后一个获胜槽用 于广播下一次调度信息.AEA 算法使用邻居协议 NP 和调度交换协议 SEP 选择发送节点和接收节点.每个节点 u在某一发送槽 t 的优先权为 prio(u,t)=hash(u⊕t).在某一时槽 t,如果节点具有两跳邻居内最高优先权并且有数 据需要发送,则进入发送状态;如果节点是当前调度的指定接收方,则进入接收状态;否则,节点进入睡眠状态. TRAMA 时钟同步存在一定的通信开销;随机和调度访问交替进行增加端到端延时;协议对节点存储空间 和计算能力要求很高,实现难度大;在 AEA 算法中,使用本地节点保存不完全的邻居节点两跳邻居信息,虽然不 影响算法的正确性,但可能造成空闲侦听,浪费能量;TRAMA协议适用于周期性数据采集和监测等 WSN应用. TDMA-W[27]协议对 TRAMA进行改进,使用固定时槽发送或接收数据.相邻节点共享调度信息.在调度产生 阶段,首先采用类似于图着色的分布式算法为所有节点分配时槽,节点每一帧分配两个时槽:一个发送槽用于发 送数据,一个唤醒槽用于侦听唤醒信号.发送槽两跳范围内唯一,唤醒槽则可以共用.在信道访问阶段,节点为每 蹇强 等:无线传感器网络MAC协议研究进展 395 个邻居保存两个计数器,分别对应于输出和输入链路.在无通信活动的情况下,计数器递减.成功传输一次数据, 则发送方和接收方分别使对应链路的计数器值加 1.节点根据计数器的值是否为 0判断是否需要发送唤醒信号. 这一机制既能减少唤醒信号的发送,又能保证在流量较小的情况下,节点有充分的睡眠时间. 睡眠延时问题是 TDMA-W 的主要缺陷.理论分析表明,平均单跳延时为一个帧的长度.调度的产生需要大 量的广播消息,容易产生冲突,协议收敛时间长,不适于拓扑变化频繁的网络环境.节点需要保存所有两跳内邻 居的调度信息,存储开销很大.TDMA-W协议适用于数据量不大的基于事件的 WSN应用. 2.2.3 Data gathering tree-based MAC[28−30] 针对 S-MAC和 T-MAC中存在的睡眠延时问题和数据转发停顿(DFI)问题,DMAC[28]提出了一种改进方法. 根据节点转发数据形成的数据采集树,采用交错唤醒调度机制,将一个周期划分为接收时间、发送时间和睡眠 时间.每个节点的调度具有不同的偏移,下层节点的发送时间对应于上层节点的接收时间.在理想情况下,数据 能够连续地从数据源节点传送到数据节点,消除了睡眠延时. DMAC 的调度机制可称为“梯型”调度,虽然有利于感知数据及时上报,却不利于兴趣查询或指令发布.文 献[29]提出一种“双梯型”调度机制,其本质是在两个传输方向上对称部署梯型调度,同时减少双向传输延时. 双梯型调度机制过于复杂,且中间节点在一个调度周期中多次唤醒,能耗不均衡.Keshavarzian[30]等人提出 一种“交叉梯型”调度机制.其基本思想是,选取某一层的中间节点作为唤醒点,唤醒点下层节点采用梯型调度,上 层节点采用双梯型调度.上述两个协议则成为交叉梯型调度的特例.为使能耗公平,各层节点轮流充当唤醒点. 以上 3 个协议在不同程度上改善了睡眠延时问题,但为了减少流内竞争,多个接收/发送时间才能发送一次 分组,降低了网络吞吐量;同时,引入额外的控制开销避免兄弟节点干扰.这种基于数据采集树的 MAC 协议非常 适合边缘节点数据流量小而中间节点数据流量大的 WSN,但需要严格的时钟同步,且数据采集树相对稳定,不 适合移动节点和规模较大的 WSN.图 4对梯型调度、双梯型调度和交叉梯型调度中双向传输延时进行了比较. Wakeup Fig.4 Comparison of ladder pattern, two-ladders pattern and crossed-ladders pattern 图 4 梯型调度、双梯型调度和交叉梯型调度比较 2.2.4 LooseMAC & TightMAC[31] Bush等人首次提出一个同时满足分布式、自稳定、无冲突和无全局时钟等特点的 MAC协议.其独特之处 在于,节点帧长度不等且无须帧对齐.LooseMAC 执行于协议初始阶段;当所有邻居节点稳定后,执行 TightMAC, 进一步提高吞吐量和减少延时.在 LooseMAC中:节点帧长度相同,为不小于 的最小的 2的整数幂,其 3 21 2min( , )δ δ 中,δ1和δ2 分别为直接邻居和两跳邻居数量上限;在每一帧节点随机选择一个数据发送时槽,并在该时槽将调度 广播给邻居节点;若在接下来一帧时间内接收到冲突报告消息或侦听到一次冲突,则重新选择一个未分配时槽, 重复上述过程;否则调度分配成功,节点进入 ready0 状态.在 TightMAC 中,帧长度进一步缩小为 log 62 iiL φ⎡⎢= ⎤⎥ ,其 中, 2 1 ( ) 2 1( ) max ( ) ( )i j i k jj kΔ Δφ δ∈ ∈= ≈∑ δ Forward delay Backward delay Forward delay Backward delay Forward delay Backward delay ,φi 是节点 i 两跳范围内两跳邻居数量的最大值,取近似值是为了减少通信 Sink 量和存储开销.注意到 LooseMAC和 TightMAC中不同节点帧长度仍然是倍数关系,因此可以共存. 该协议仅根据节点本地信息建立调度,能够较好地适应网络拓扑变化,扩展性得到显著提升.但在调度产生 过程中,节点间的潜在冲突使协议收敛时间过长,影响效率.该协议假设基于 Unit Disc 模型,与实际使用中基于 信噪比的冲突检测模型尚有差距,无法利用捕获效应改善性能.该协议更适合应用于流量稳定的网络应用环境. Lever 1 Lever 2 Lever 3 Wakeup Wakeup Wakeup Wakeup 396 Journal of Software 软件学报 Vol.19, No.2, February 2008 2.2.5 EMACs(EYEs MAC)[12]及LMAC(lightweight MAC for WSNs)[32] Van Hoesel等人结合物理层与网络层的特点,提出两个 TDMA协议.EMACs[12]为上层路由协议提供高效支 持.作为 EMACs 的补充,LMAC[32]协议进一步减少发射/接收切换次数,节省能量同时降低硬件要求.EMACs 和 LMAC 的基本原理是:采用分布式算法选举主动节点构成连通骨干网络,其他节点称为被动节点;主动节点协商 产生调度,时槽只能在 3跳外重用;被动节点只能向特定主动节点发送数据,大多数情况下保持睡眠;根据流量和 剩余能量,主动节点和被动节点可以转换;连通骨干网络有利于网络层建立路由(如动态源路由 DSR(dynamic source routing))[33],并减少路由开销.在 LMAC中,控制分组长度固定且包含控制消息(目标 ID和跳数)和数据单 元,因为没有冲突,所以可以一起直接发送,无须数据交换握手机制,更能有效减少无线收发器的切换次数. EMACs和 LMAC已经在欧洲研究计划 EYEs[34]的原型系统中得到实现.但仍有明显缺陷:帧中存在空闲时 槽,降低了信道利用率;网络流量较大时分组丢失严重;主动节点通信任务较重,而且调度协商存在冲突;协议不 能对广播和聚播通信提供有效支持.EMACs和 LMAC宜用作数据流量不大的结构化网络 MAC协议. 2.2.6 ArDeZ(asymmetric rendezvous MAC)[35] Kvan-Wu 等人借鉴了低轨道卫星系统中使用伪随机数机制建立 TDMA 信道的思想,提出了一个基于会合 点(rendezvous)的MAC协议——ArDeZ[35]协议.因无须调度协商和严格的时槽界限,适合在大规模WSN中部署. ArDeZ为每对相邻节点间的上、下行链路分别建立两个占空比不同的独立时间信道.节点根据伪随机数种 子计算不同信道的会合周期(rendezvous period),并决定信道访问时刻.然后不断循环迭代计算新的会合周期,避 免周期调度协商,减少开销和延时.具体执行过程是:节点首先保持活跃并侦听链路,当接收到邀请消息并同时 满足以下 3 个条件时成为受邀节点:(1) 可用邻居数或平均会合周期(MRP)小于给定阈值;(2) 与邀请节点之间 尚无链路;(3) 邀请节点和 Sink之间有可达路径.邀请消息最初由 Sink发送.如果邀请节点提供的两个种子和相 应会合周期与受邀节点现有调度没有冲突,则回复一个发送信道请求消息 CRM,请求采用邀请节点提供的种子 建立信道,收到 CRM的邀请节点则回复一个信道确认消息 CAM.上行链路和下行链路的种子 Su和 Sd由邀请节 点在 0~255之间随机选取,并结合时间戳计算会合周期,本次会合周期的结束时刻成为下一次会合周期的种子. ArDeZ 的伪随机特性保证仅当相邻链路的会合周期重叠且都有数据发送时才会发生冲突,但这样的冲突 概率很小.ArDeZ 协议可获得比 S-MAC 和 TRAMA 更好的节能特性,而且可根据网络流量调整会合周期,在延 时和能耗之间平衡.该协议有利于上层路由协议(如GPSR等地理路由协议)的实现,但该协议端到端通信的特性 不能较好地满足广播通信的要求;主路径上节点能量消耗较快.ArDeZ更适用于环境监测等数据采集型 WSN. 2.3 混合MAC协议 混合协议包含竞争协议和调度协议的设计要素,既能保持所组合协议的优点,又能避免各自的缺点.当时空 域或某种网络条件改变时,混合协议仍表现为以某类协议为主,其他协议为辅的特性.混合协议更有利于网络全 局优化. 2.3.1 Z-MAC(zebra MAC)[36] Z-MAC 是一种 CSMA/TDMA 混合 MAC 协议.在低流量条件下使用 CSMA 信道访问方式,可提高信道利 用率并降低延时;在高流量条件下使用 TDMA信道方式,可减少冲突和串扰.与 TDMA协议不同,Z-MAC中节点 能在任何时槽发送数据,但时槽拥有者优先级更高.当时槽拥有者不发送数据时,其邻居节点以 CSMA方式竞争 信道,获胜者“盗用”该时槽.通过邻居发现,节点收集两跳内邻居信息,然后采用分布着色算法为每个节点分配时 槽.与 LooseMAC[31]一样,节点帧长度必须是 2 的整数幂,邻居节点以 CSMA 方式竞争多余的时槽.当竞争较强 时,节点发出明确竞争通告(ECN)消息,如果节点在最近 tECN时间内收到某一两跳邻居发出的 ECN,则成为高竞 争级(HCL)节点,否则为低竞争级(LCL)节点.LCL 节点可以竞争任何时槽,但在 HCL 状态下,只有时槽拥有者及 其邻居节点可以使用该时槽,并且在时序上早于非拥有者发送.这种 ECN技术具有一定的拥塞控制能力. Z-MAC已经在 TinyOS上实现.与 TinyOS默认协议 B-MAC相比,它在中、高网络流量下能够提供更高的 吞吐量,能量消耗也更小;在低流量情况下,性能比 B-MAC 稍差.作为一种混合 MAC 协议,Z-MAC 具有比传统 TDMA 协议更好的可靠性和容错能力,在最坏情况下,协议性能接近 CSMA.Z-MAC.它存在的缺陷有:在启动阶 蹇强 等:无线传感器网络MAC协议研究进展 397 段需要全局时钟同步;在 HCL模式下,节点只能在有限的时槽发送数据,增加了传输延时,在 LCL 模式下仍然存 在隐藏终端问题;ECN机制易产生内爆,为避免内爆增加了控制开销;集中式调度分配算法只能在协议初始阶段 为节点分配时槽,无法周期重运行,这也是 Z-MAC性能不如稍后介绍的 Funneling-MAC的主要原因. 2.3.2 Funneling-MAC[37] WSN 多跳聚播通信方式造成 Sink 附近分组易冲突、拥塞和丢失,文献[12]称其为漏斗效应(funneling effect).Ahn等人[37]为此提出一种混合协议 Funneling-MAC.该协议在全网范围内采用 CSMA/CA,漏斗区域节点 ( f-节点)则采用 CSMA 和 TDMA 混合的信道访问方式,因此, f-节点有更多机会基于调度访问信道.Sink 周期广 播信标,接收到信标的节点成为 f-节点,Sink 逐渐增加广播功率级别,直到网络达到饱和为止;f-节点使用 CSMA 和 TDMA 帧交替访问信道,一个 CSMA 帧和 TDMA 帧合成为一个超帧,其中,TDMA 帧包含多个时槽,用于 f- 节点根据调度转发数据,CSMA 帧用于发送 f-节点产生的数据以及路由和其他控制信息,如图 5 所示.Sink 节点 产生的 TDMA 调度分组在信标之后发送,信标广播周期包含的超帧数量和长度固定,因此,f-节点知道何时接收 信标和调度分组,减少冲突概率,且未收到调度分组的节点仍可使用 CSMA帧发送数据,保证了协议的可靠性. Beacon Beacon Schedule Fig.5 Division of time frames in funneling-MAC 图 5 Funneling-MAC时间帧划分 Funneling-MAC 以 CSMA 为主,对时钟同步要求不高.实验表明,其各种性能指标普遍优于 Z-MAC 和 B-MAC,网络生存时间更长.但协议中时槽分配算法只提供松散的 TDMA 调度,无法消除隐藏终端问题;采用面 向 Sink的集中式 TDMA调度算法,若 Sink附近拓扑发生变化,则需重新部署,开销很大;无线通信中存在的无规 律冲突问题,造成漏斗边界的不确定性,影响协议性能.因此,Funneling-MAC目前还无法应用于大规模 WSN. 2.4 跨层设计MAC协议 目前,大部分 WSN 研究仍然沿用传统的分层设计思想,虽然具有设计简化、网络稳定、兼容性好等优点, 但协议栈各层往往关心不同的性能指标,缺少层间交互和信息的共享利用.事实上,单一性能参数的改善并不一 定能带来系统全局效率的提高,比如,物理层链路质量好的节点可能剩余能量较小,缓冲区待发送分组队列较 长,因此,MAC协议不应该将该节点选作下一跳转发节点.近年来,很多学者从跨层设计的角度研究MAC层与网 络协议栈其他层之间的优化问题,如物理层和 MAC 层的交互、MAC 协议和路由的结合等,以期进一步提高 MAC协议效率,实现协议轻量化,减少开销.跨层优化问题是目前 WSN MAC协议的研究热点之一. 2.4.1 AIMRP(address-light integrated MAC and routing)[38] AIMRP[38]协议基于 IEEE 802.11,集成了 MAC和路由机制.其主要特点是:无需全局地址,MAC协议也负责 建立路由.协议根据节点到 Sink的跳数,形成一个以 Sink为中心的多层环形结构,路由机制简化为数据分组从外 环向内环逐层转发.节点采用RTR(request to relay)/CTR(clear to relay)/DATA/ACK握手机制实现信道访问控制, 转发节点只响应直接上层节点的 RTR 请求.AIMRP 采用异步随机工作循环机制,实现节点休眠调度,其基本思 想是:节点根据参数σ的分步决定睡眠时间长度 Tσ,参数σ根据端到端延时需求确定,如果节点在睡眠状态下检 测到事件,则立刻进入侦听状态;否则,在睡眠结束后保持等待状态 Ton 时间,负责转发上层节点产生的数据,Ton 远小于分组传输时间 TData,保证节点有充足的睡眠时间;之后再次进入睡眠状态,并重新计算睡眠时间,除非以 下两类事件发生:(1) 新数据产生;(2) 接收到上层节点的 RTR请求,但尚未接收到来自本层其他节点的 CTR响 应.由于节点睡眠/唤醒相互独立,不需要相互交换睡眠调度信息. 实验表明,AIMRP 能量效率高于 S-MA,但同步精度要求高;采用集中式算法,虚拟拓扑动态适应性差;路由 机制类似于DSR等地理路由协议,未考虑能量优化.AIMRP针对典型聚播流量,更适用于事件检测等WS