基于GPS卫星授时的时分多址MAC协议

王 宇，朱益锋，赵增华

（天津大学计算机科学与技术学院，天津300072）

1 概述

互联网的普及和应用不仅给人类生活带来了便利，而且正改变着人类的生活习惯和生活方式，极大促进了人类社会的发展。然而，大部分居住在发展中国家贫困农村和发达国家偏远地区的人们，由于有线网络设备部署和维护费用高等原因，一直没有享受到快速和稳定的网络服务。基于IEEE802．11的长距离无线 Mesh网络（Long－distance Wireless Mesh Network，LDmesh）是指相邻节点间距离很长（几十甚至上百公里）的新型网络，其中的工作节点通常配置高增益无线保真（Wireless Fidelity，WiFi）定向天线以达到长距离的信号覆盖［1］。LDmesh网络与传统的有线网络相比，具有搭建成本低、覆盖范围广、易于部署和维护等特点，适用于地广人稀的区域或偏僻落后的农村。由此可见，研究长距离无线Mesh网络，对促进社会和经济发展具有重要的意义。

在长距离无线Mesh网络中对媒体访问控制（Media Access Control，MAC）协议的研究和设计一直都是核心问题。文献［2］将低成本的网络设备引入长距离无线Mesh网络，文献［3－4］利用实验设备分别在高密度和低密度人口地区进行测试和应用。文献［5－7］设计和应用分时MAC协议，对长距离无线Mesh网络的性能进行评估。传统基于IEEE 802．11的MAC协议是针对小范围移动网络而提出。LDmesh网络虽然与传统无线局域网（Wireless Local Area Network，WLAN）一样都是使用IEEE 802．11无线网卡，但是与传统 WLAN相比，长距离的单跳传输距离特点使得IEEE 802．11中常用的网络协议和机制效率低下，如采用自动重传（Automatic Repeat Requset，ARQ）。 因 此，在LDmesh网络中，需要重新设计MAC协议来提升网络性能。

针对LDmesh网络中MAC协议的设计，国内外研究人员提出多种设计方案。文献［8］给出SynOp概念，在分析其可行性后，提出2PMAC协议［9］，并在实验床上进行系统研究，奠定了长距离无线Mesh网络MAC协议研究的基础，为该领域研究提供了良好的理论基础。文献［10－12］针对2PMAC协议的不足，结合实际情况对2PMAC协议进行改进，提出自适应时隙的MAC协议，克服了外部环境的干扰，使其能更好地应用于长距离无线Mesh网络。这些协议能优化长距离无线Mesh网络的性能，为长距离无线Mesh网络的应用提供技术支持。但当前协议都使用信令包（如Marker包或Token包）来实现不同节点间以及同一节点不同接口间的同步，一旦用于同步的信令包丢失则会导致MAC协议失效，重新同步需要很长时间来恢复网络，从而导致网络性能低下。

因此，在长距离无线Mesh网络中设计一种简单易行的时隙同步MAC协议十分必要。考虑到目前卫星授时功能的广泛应用，本文在长距离无线Mesh网络MAC协议中引入卫星授时技术，提出基于GPS卫星授时的TDMA MAC协议GT－MAC，利用GPS卫星的秒脉冲信号中的精准时钟信息来实现不同节点间及同一节点不同接口间的同步。本文使用的实验平台为自主研发的 WiZiTJU－GPS，能够获取GPS卫星秒脉冲信号并更新节点时间，改进网卡驱动Madwifi，并通过实验对GT－MAC协议性能进行评估。

2 GT－MAC协议设计

GT－MAC协议采用2PMAC协议提出的SynOp思想［8］，通过控制网络中节点的统一接收或发送，避免接口间的相互干扰，即节点的全部接口同时处于发送（Tx）或接收（Rx）状态，若一个接口转换状态，则它的全部对应邻居接口也相应转换状态。

2．1 GT－MAC时隙调度

如图1所示，节点首先在初始时刻分配一个初始状态。在Tx状态下，节点发送数据包（如果需要发送）直到下一个时隙到来，然后切换至Rx状态；而在Rx状态下，节点被动接收数据包直到下一个时隙到来，然后切换至Tx状态。

图1 GT－MAC协议的节点时隙状态切换

2．2 邻居节点及接口的时隙同步

当进行GT－MAC协议的设计时，首先要保证各节点以及同一节点的各接口间的时隙同步，从而使整个网络进行正确的时隙调度。

GT－MAC协议使用GPS卫星授时进行同步。在每个节点部署具有授时功能的卫星定位模块，用于接收GPS秒脉冲来实现各个节点间、同一节点的不同接口间的时钟同步。图2描述了GT－MAC邻居接口的时隙同步原理。

图2 GT－MAC邻居接口的时隙同步

网络中所有节点工作在同一个信道，为避免相邻链路间的干扰，需要采用2个状态（发送／接收状态）的工作方式，同一节点中所有接口的状态相同，与其相邻节点的状态不同。也就是说，一个节点的各个接口如果处于发送状态，与其相邻的节点的各个接口必须都处于接收状态；反之亦然。基于这个特点，要求网络拓扑结构为二分图。

假定网络在构建时已经具有二分图拓扑结构，即节点分为2个互不相交的集合A和B，若一个节点在集合A中，则它的所有邻居节点都在集合B中。假定所有节点事先配置好所属集合。接收／发送的时隙长度相同，且设为固定值Ts，通常为20 ms。这样1s就可以分成n个时隙，其中：

本文选择适当的Ts，使得n为整数。为简单起见，n为偶数值。规定属于集合A的节点在奇数时隙（第1个，第3个，第5个，…，第n-1个时隙）处于发送状态，在偶数时隙（第2个，第4个，第6个，…，第n个时隙）处于接收状态。属于集合B的节点在奇数时隙处于接收状态，在偶数时隙处于发送状态。

基于GPS卫星授时的TDMA MAC协议GTMAC运行在无线路由器中，网络中的每个节点均是配备卫星授时功能的无线路由器。图3是长距离无线Mesh网络一个典型的网络拓扑图。在网络初始化阶段，各节点首先通过卫星定位模块同步自身的时钟，Tx时隙和Rx时隙长度都设置为20ms。网络已经具有二分图拓扑结构，节点2、节点6、节点7、节点8组成独立集A，其中的各节点所有接口的状态设定：在每秒开始的奇数时隙为Tx，偶数时隙为Rx。节点1、节点3、节点4、节点5、节点9构成独立集B，其中的各节点所有接口的状态设定：在每秒开始的奇数时隙为Rx，偶数时隙为Tx。

图3 长距离无线Mesh网络中的典型网络拓扑

2．3 累积反馈的可靠传输机制

虽然在上述2个状态TDMA调度机制下，不会产生链路间信号干扰，但是长距离无线链路容易受到外部干扰或者信号传输衰落的影响而造成丢包。另外，在一个发送时隙通常能发送多个数据包，但由于长距离无线网络的往返时延（Round－trip Time，RTT）较大，要尽量减少反馈（Acknowledgement，ACK）的发送，以提高信道利用率。鉴于此，本文通过改进网卡驱动Madwifi，设计累积ACK的可靠传输机制以提高传输可靠性和效率。

3 GT－MAC协议实现

3．1 GT－MAC协议授时功能实现

3．1．1 授时实验平台 WiZiTJU－GPS的搭建

GT－MAC协议的实验平台 WiZiTJU－GPS是基于天津大学计算机网络实验室自主研发的WiZiTJU嵌入式开发平台［13］。WiZiTJU嵌入式开发平台主要的软硬件参数如表1所示。通过WiZiTJU的串口获取GPS卫星的秒脉冲信号，从中解析出时钟信息，并使用该时钟信息来实现各个节点及各节点接口间的同步。

表1 WiZiTJU嵌入式开发平台的软硬件参数配置

在WiZiTJU平台的基础上，采用的GPS模块，即Trimble公司生产的Resolution T GPS授时接收机，如图4所示。Resolution T GPS授时接收机是全功能的、具有12信道、并行跟踪的嵌入式授时板，工作在L1（1 575．42 MHz）频率，能够为很多授时应用提供精确的GPS或UTC时钟或同步。通过WiZiTJU－GPS的串口获取GPS模块产生的高精度时钟信息（秒脉冲（Pulses Per Second，PPS）），并使用该时钟信息来实现各个节点及各节点接口间的同步。实验平台WiZiTJUGPS的硬件架构如图5所示。

3．1．2 WiZiTJU－GPS授时的实现

图6描述了WiZiTJU－GPS上授时功能的设计思路。程序共分为两部分：一部分是GPS秒脉冲触发中断模块，其在内核态中执行；另一部分是读取串口中GPS时钟信息并更新系统时间程序，其在用户态中执行。

图6 WiziTJU－GPS授时功能设计

GPS秒脉冲触发硬中断，首先注册中断，使用WiZiTJU－GPS实验平台通用输入／输出（General Purpose Input Output，GPIO）的PC7引脚，注册中断号58，这里采用反相器把上升沿触发中断转换为下降沿触发中断，保证秒脉冲信号精度。每当PC7引脚捕获到GPS秒脉冲中断信号后，产生硬件中断，调用中断服务程序。此时，中断服务程序向用户态程序发送信号。同时在获取时间信息并更新系统时间程序中，首先在获得GPS秒脉冲信号之前进行串口配置，之后等待来自内核态发来的信号。一旦收到来自内核态发来的信号，程序进入信号处理函数。在该函数中，首先读取串口数据，然后根据Trimble公司标准接口协议（Trimble Standard Interface Protocol，TSIP）［14－15］对数据进行解析，获取时间信息后更新系统时间。

3．2 改进网卡驱动Madwifi的GT－MAC协议实现

GT－MAC协议采用TDMA的方式进行数据发送和接收，每个时隙处于一个状态（发送／接收），待下一个时隙开始与相邻的节点同时互换状态。该方式与原有的Madwifi设计不同，因此，需要对网卡驱动进行改进，以满足GT－MAC的设计需要。

在Madwifi中，采用载波侦听多路访问／碰撞避免（Carrier Sense Multiple Access with Collision Avoidance，CSMA／CA）机制来避免冲突。节点在发送数据之前，先对链路进行监听，当空闲一段时间后，发送端根据指数退避算法选择随机等待时间开始退避，退避结束后直接发送数据。为了使CSMA／CA更加可靠，在MAC层增加了ACK机制。接收节点接收到数据包后，首先进行循环冗余校验码（Cyclical Redundancy Check，CRC）校验，如果校验正确则向发送节点回复一个ACK，对收到的数据包进行确认，发送节点收到该ACK后才继续发送下一个包。IEEE 802．11协议使用请求发送／清除发送（Ready to Send／Clear to Send，RTS／CTS）机制来解决隐藏终端引起的冲突问题。发送节点在发送数据帧之前先发送RTS，若信道空闲，则目的节点发送CTS，允许发包。因此，结合GT－MAC的功能，对Madwifi进行以下改进：

（1）禁用 ACK，CSMA／CA，RTS／CTS。驱动中的ACK，CSMA／CA 的功能是在硬件抽象层（Hardware Abstraction Layer，HAL）和硬件中实现。通过把网卡中地址为0x8048的寄存器的第2位置1，来关闭ACK。通过提高网卡的监听阈值，缩小短帧间隙（Short Interframe Space，SIFS）、分布式帧间间隙（Distributed Inter－frame Spacing，DIFS）和退避时间slot＿time的值，综合使用禁用队列退避的3个方法来关闭 CSMA／CA 功能；最后使用iwconfig命令来关闭RTS／CTS功能。

（2）完善ath＿softc结构。这个数据结构中保存着网卡各种配置信息。为了设置GT－MAC协议中的固定时隙切换，需要在ath＿softc结构中添加时隙状态和固定时隙计时器等数据成员，用于判断和转换时隙。

（3）在MAC层定义累积ACK：当接收时隙结束时，节点切换到发送时隙，同时发送一个累计ACK，对接收时隙接收的数据包进行确认。

（4）在 MAC层上增加逻辑链路控制（Logical Link Control，LLC）层。LLC层的作用是维护2个逻辑队列：发送队列和接收队列。文献［16］发送数据时先要把数据包添加到逻辑发送队列，等到节点切换到发送时隙时，再将发送队列中的数据包添加到硬件发送队列中进行发送。当节点处于接收时隙时，先把接收到的包放入接收队列，等到切换到发送状态后，对上一个时隙接收到的数据包进行确认，将累计ACK发给发送节点，再将接收队列中的数据包交给上层。

通过以上对Madwifi的改进，不仅提升了MAC协议在长距离中的性能，同时实现GT－MAC协议的固定时隙切换策略和累积ACK的可靠确认机制，从而产生能够在 WiZiTJU－GPS实验平台上运行的GT－MAC协议。

4 实验结果与分析

4．1 GT－MAC时隙同步验证

实验使用 WiZiTJU－GPS平台运行GT－MAC协议，记录2个对应节点a和b的时隙切换时间，通过对比验证GT－MAC协议节点时隙调度策略的可行性。

随机选取某时间段内10个连续时隙内的两节点切换时隙时间，如图7所示，2个节点均可保证每20ms切换时隙状态，记录的切换时隙的时间对应，误差小于0．5ms，表明时隙调度策略能够保证节点间时隙状态相对应。

图7 GT－MAC协议节点a，b对应的时隙切换时间对比

通过实验可以看出，GT－MAC在2个节点上运行时，每个节点都可以独立进行时隙调度，且2个节点均可保证每20ms切换时隙状态，2个节点彼此时隙状态对应较好、误差较小。综上所述，GT－MAC协议的时隙调度策略可行，能够满足2个节点时隙状态的周期性切换，使得节点时隙的发送和接收状态在一定程度上的对应。

4．2 GT－MAC性能评估

在20km的长链路上，如图8所示（图中天津理工大学新校区简称为“理工新校区”，是天津大学仁爱学院简称为“仁爱”），采用高增益的定向天线，如图9所示。在链路两端使用WiZiTJU－GPS实验平台，分别运行2PMAC协议和GT－MAC协议，在2个对应节点上分别运行Iperf进行实验，实验参数如表2所示，链路单跳吞吐率对比如图10所示。

表2 GT－MAC性能参数

图10 2PMAC和GT－MAC的吞吐率对比

通过实验可以看出，2PMAC和GT－MAC的单跳吞吐率分别为 3．47Mb／s和 3．82Mb／s，GTMAC提升约10．1%，GT－MAC在长距离链路有更好的适应性。但采用2种协议下链路的整体吞吐率都不高，造成这种现象的原因主要是由于WiZiTJUGPS实验平台自身时钟精度不高，不同节点的时钟走势不同且有时会有跳跃，尽管每个节点的时隙调度策略正确且能正常工作，但是仍旧无法实现不同节点间的时隙同步，一旦长时间运行就会导致误差积累，从而导致整体吞吐率不高。

5 结束语

本文针对长距离无线Mesh网络中信令包丢失降低网络性能的问题，提出GT－MAC协议，使用GPS卫星的秒脉冲信号对节点进行硬同步。首先搭建WiZiTJU－GPS硬件实验平台，利用硬中断的方式接收秒脉冲信号，同时对系统时间进行更新，完成同步。然后对网卡驱动Madwifi进行修改，使节点的时隙状态能够周期性切换，同时实现了累积ACK的可靠确认机制。最后通过在长距离链路上的实验，证明了GT－MAC协议比传统2P MAC协议有更好的吞吐率，说明GT－MAC协议在长距离无线Mesh中有较好的适应性。由于本文设计的WiZiTJU－GPS实验平台在接收GPS卫星秒脉冲信号时，能获取高精度的时间信息及地理位置信息，因此可以利用地理位置信息确定节点位置，为进一步研究基于集中式节点管理的控制系统提供技术支持。

［1］赵增华，王 楠，窦志斌，等．基于IEEE 802．11的长距离无线 Mesh网络［J］．计算机学报，2012，35（6）：1209－1222．

［2］Surana S，Patra R，Nedevschi S，et al．Beyond Pilots：Keeping Rural Wireless Networks Alive ［C］／／Proceed－ings of NSDI’08．San Francisco，USA：USENIX Association，2008：119－132．

［3］Subramanian L，Surana S，Patra R，et al．Rethinking Wireless for the Developing World［EB／OL］．（2014－07－16）．http：／／tier．cs．berkeley．edu／docs／wireless／large＿wild．pdf．

［4］Raman B，Chebrolu K．Experiences in Using WiFi for Rural Internet in India［J］．IEEE Communications Magazine，2007，45（1）：104－110．

［5］Paul K，Varghese A，Iyer S，et al．WiFiRe：Rural Area Broadband Access Using the WiFi PHY and a Multisector TDD MAC［J］．IEEE Communications Magazine，2007，45（1）：111－119．

［6］Dhekne A，Uchat N，Raman B．Implementation and Evaluation of a TDMA MAC for Wifi－based Rural Mesh Networks［C］／／Proceedings of iSoSP Workshop on Net－work System for Developing Regions．Washington D．C．，USA：IEEE Press，2009：124－137．

［7］Partha D，Vivek M，Debmalya P，et al．Joint Routing and Scheduling in Wireless Mesh Networks with Directional Antennas ［C ］／／Proceedings of International Conference on Computer Communications．Washington D．C．，USA：IEEE Press，2010：491－495．

［8］Bhaskaran R．Channel Allocation in 802．11－based Mesh Networks［C］／／Proceedings of International Conference on Computer Communications．Washington D．C．，USA：IEEE Press，2006：1－10．

［9］Bhaskaran R，Kameswari C．Design and Evaluation of a New MAC Protocol for Long Distance 802．11Mesh Networks［C］／／Proceedings of Annual International Conference on Mobile Computing and Networking．New York，USA：ACM Press，2005：156－169．

［10］Rabin P，Sergiu N，Sonesh S，et al．WiLDNet：Design and Implementation of High Performance Wi－Fi Based Long Distance Networks ［C ］／／Proceedings of Network－ed System Design and Implementation．Washington D．C．，USA：IEEE Press，2007：87－100．

［11］Nedevschi S，Patra R，Surana S，et al．An Adaptive，High－performance MAC for Long－distance Multihop Wireless Networks［C］／／Proceedings of Annual International Conference on Mobile Computing and Networking．New York，USA：ACM Press，2008：259－270．

［12］Yahel B D，Matthias V，Seth F，et al．JaldiMAC：Taking the Distance Further［C］／／Proceedings of Workshop on Network System for Developing Regions．New York，USA：ACM Press，2010：2－7．

［13］韩双立，张力晨，周文涛，等．基于WIFI和Zigbee的无线网络设备：中国，200910068172．1［P］．2009－08－19．

［14］Trimble Navigation Limited．TSIP Application Developer’s Guide：Revision A［M］．［S．l．］：Trimble Navigation Limited，2005．

［15］Xue Yanrong，Li Xiaohui．GPS Time System and Its Application in Time Transfer Technology［J］．Applied Mechanics and Materials，2013，401－403：1872－1878．

［16］王 楠．长距离无线 Mesh网络2PMAC协议的实验研究［D］．天津：天津大学，2011．