基于完全服务轮询机制MAC协议的FPGA设计

FPGA Design of MAC Protocol Based on Exhaustive Service Polling Mechanism

摘要: MAC协议是连接物理链路和网络层直接的纽带，是保证网络高效通信的关键协议之一。本文根据轮询系统的特性，提出了一种基于完全服务轮询机制MAC协议的FPGA设计。该设计充分利用FPGA的灵活性和可重构性的特点，采用硬件描述语言Verilog HDL和原理图相结合的方法，使用Quartus II 8.0进行综合和布线，在DE2开发板上进行测试。该设计具有实时性好、可靠性高、可移植性强等特点，能够有效减小传输时延，提高总线利用率。可广泛用于无线传感器网络、Ad Hoc网络、移动通信网络、物联网等领域。

Abstract: MAC protocol is a direct link between physical and network layer, which is one of the key protocols to ensure high efficient communication. According to the characteristics of polling system, this pa-per presents a FPGA design of MAC protocol based on exhaustive service polling mechanism. The design makes full use of the characteristics of flexibility and reconfigurability of FPGA. The method of combination of the hardware circuit description language Verilog HDL and the principle diagram is adopted, using Quartus II 8.0 to carry on the synthesis and routing, testing in the DE2. The design has the characteristics of good real-time, high reliability, strong portability, and can effectively reduce the transmission delay, and improve the bus utilization. The system designed can be widely used in wireless sensor networks, Ad Hoc networks, mobile communications networks, and net-working and other fields.

1. 引言

物联网是继计算机、互联网之后，世界信息产业的第三次浪潮，是将信息化技术的应用更加全面地为人类生活和生产服务的信息化大升级 [1] 。2014年全球物联网发展报告 [2] 中指出，物联网技术正在全球范围内飞速发展，所带动的新型信息化与传统领域走向深度融合。物联网对行业和市场带来的冲击和影响已广受关注。物联网技术的应用也将推动多行业的生产工作模式向信息化、智能化转变。目前，物联网技术已在工程检测 [3] 、灾害预警 [4] 、环境监测 [5] 、现代农业 [6] [7] 、危险物品监测 [8] 等领域得到应用。

在物联网中有着诸多协议保证网络正常通信。其中对网络性能影响较大的是MAC协议，其规定了信道的使用方式，是物联网研究的热点。传统的CSMA协议、改进型的CSMA/CA协议以及后来发展的S-MAC协议和T-MAC协议都是基于竞争型的协议，由于竞争和冲突的存在，无法为时延要求较高的业务提供QoS保障，同时也大大降低了系统的吞吐量 [9] 。

轮询系统具有的独特性使得基于轮询机制的MAC协议能够有效克服传送冲突给系统造成的不利影响。FPGA具有灵活性高、可重构性好、运算能力强等特点 [10] 。利用FPGA设计的基于完全服务轮询机制的MAC协议能够有效防止碰撞、冲突的发生，减小网络传输时延，提高信道利用率。

本文以MAC协议为研究对象，分别讨论了CSMA、CSMA/CA、S-MAC、T-MAC协议在竞争情况下的不足。根据轮训系统的独特性和FPGA的灵活性，设计了基于完全服务下的MAC协议的FPGA实现，并做了系统仿真、分析。仿真结果表明，基于完全服务轮询机制的MAC协议能够有效避免数据冲突、减小传输时延、提高系统吞吐量和总线利用率。该设计在功能上和参数指标上都达到了要求，实现了设计目标。

2. 系统原理

MAC (Multiple Access Control)协议，即多路访问控制协议，该协议决定了节点什么时候允许发送分组，而且通常控制对物理层的所有访问。共分为三大类：1) 按信道划分，将信道划分为较小的“段”，一般有频分多址(FDMA)、时分多址(TDMA)、码分多址(CDMA)。2) 随即访问，即不划分信道，允许碰撞发生并想办法从“碰撞”恢复。一般而言为竞争类的MAC协议，当然也有分配类和混合类的协议。对于WLAN，其中竞争类协议主要有CSMA，MACA，MACAW，FAMA，BTMA等。而非竞争类的协议主要有FPRP等协议。3) 轮询，主结点轮流“邀请”从属结点发送数据。

完全服务轮询系统的服务规则是：获得发送权的站点既要发送服务间隔时间内到达的信息分组，还要发送服务期间新到达的信息分组 [11] 。系统工作方式可描述为三个基本过程：信息分组到达过程；信息分组传输服务过程；站点间轮询转换过程。信息分组到达过程是符合到达率为 $\lambda$ 的泊松分布，其随机变量的概率母函数为 $A\left(z\right)$ 。信息分组的服务过程中，单个信息分组的服务时间为 $\beta$ ，其随机变量的概率母函数为 $B\left(z\right)$ 。轮询转换过程中，转换时间为 $\gamma$ ，其随机变量的概率母函数为 $R\left(z\right)$ 。系统服务强度为 $\rho \left(\rho =\lambda \beta \right)$ ，系统稳定的条件为 $\rho <1$ 。

假定 $i\left(i=1,2,\cdot \cdot \cdot ,N\right)$ 号站点是在 $t_n$ 时刻接收服务器服务，当i号站点以完全服务方式发送完其存储器内的信息分组后，服务器就转去查询 $i+1$ 号站点， $i+1$ 号站点在 $t_n+1$ 时刻接受服务。定义随机变量 ${\xi }_i\left(n\right)$ 表示i号站点在 $t_n$ 时刻，其存储器内的信息分组数，那么完全服务系统在 $t_n$ 时刻的状态就可以表示为 $\left[{\xi }_1\left(n\right),{\xi }_2\left(n\right),\cdots ,{\xi }_i\left(n\right),\cdots ,{\xi }_N\left(n\right)\right]$ ，其概率分布为 $P\left[{\xi }_i\left(n\right)=x_i;i=1,2,\cdot \cdot \cdot ,N\right]$ ，描述该系统中N个系统状态变量的概率分布函数为 ${\pi }_i\left(x_1,x_2,\cdots ,x_i,\cdots ,x_N\right)$ 。那么，在 $t_n$ 时刻，系统状态变量的概率分布函数为： $\underset{n\to \infty }{\lim }P\left[{\xi }_i\left(n\right)=x_i;i=1,2,\cdots ,N\right]={\pi }_i\left(x_1,x_2,\cdots ,x_i,\cdots ,x_N\right)$ ， ${\pi }_i\left(x_1,x_2,\cdots ,x_i,\cdots ,x_N\right)$ 的概率母函数定义为：

$\begin{array}{l}{G}_i\left(z_1,z_2,\cdots ,z_N\right)={\displaystyle \underset{x_1=0}{\overset{\infty }{\sum }}{\displaystyle \underset{x_2=0}{\overset{\infty }{\sum }}\cdots {\displaystyle \underset{x_i=0}{\overset{\infty }{\sum }}\cdots {\displaystyle \underset{x_N=0}{\overset{\infty }{\sum }}{\pi }_i\left(x_1,x_2,\cdots ,x_i,\cdots x_N\right)}}}}\\ z_1^{x_1}{z}_2^{x_2}\cdots z_i^{x_i}\cdots z_N^{x_N}\left(i=1,2,\cdots ,N\right)\end{array}$ (1)

假设服务器对在任何一个时隙内进入任何一个站点的信息分组进行完全服务所需时间的随机变量是相互独立且服从相同概率分布的，其概率母函数 $F\left(z_i\right)$ 为：

$F\left(z_i\right)=E\left[z_i^{v_i,m}\right]=A\left(B\left(z_{i}F\left(z_i\right)\right)\right)\left(i=1,2,\cdots ,N\right)$

在 $t_n+1$ 时刻开始对 $i+1$ 号站点服务，有关系式：

$\{\begin{array}{l}{\xi }_j\left(n+1\right)={\xi }_j\left(n\right)+{\eta }_j\left(v_i\right)+{\mu }_j\left(u_i\right)\\ {\xi }_i\left(n+1\right)={\mu }_j\left(u_i\right)\end{array}\left(j\ne i\right)$ (2)

$\begin{array}{l}{G}_{i+1}\left(z_1,z_2,\cdots ,z_i,\cdots ,z_N\right)=\underset{n\to \infty }{\lim }E\left[{\displaystyle \underset{j=1}{\overset{N}{\prod }}{z}_j^{{\xi }_j^{\left(n+1\right)}}}\right]\\ =\underset{n\to \infty }{\lim }E\left[{\displaystyle \underset{j}{\overset{N}{\prod }}{z}_j^{{\xi }_j\left(n\right)+{\mu }_j\left(u_i\right)+{\eta }_j\left(v_i\right)}\cdot z_i^{{\mu }_j\left(u_i\right)}}\right]=R\left[{\displaystyle \underset{j=1}{\overset{N}{\prod }}{A}_j\left(z_j\right)}\right]\underset{n\to \infty }{\lim E}\left[\left({\displaystyle \underset{\begin{array}{l}j=1\\ j\ne 1\end{array}}{\overset{N}{\prod }}{z}_j^{{\xi }_j\left(n\right)}}\right)\left({\displaystyle \underset{\begin{array}{l}j=1\\ j\ne 1\end{array}}{\overset{N}{\prod }}{z}_j^{{\eta }_j\left(v_i\right)}}\right)\right]\\ =R\left[{\displaystyle \underset{j=1}{\overset{N}{\prod }}{A}_j\left(z_j\right)}\right]G_i[z_1,z_2,\cdots ,z_{i-1},B_i\left({\displaystyle \underset{\begin{array}{l}j=1\\ j\ne 1\end{array}}{\overset{N}{\prod }}{A}_j\left(z_j\right)}\right)F\left({\displaystyle \underset{\begin{array}{l}j=1\\ j\ne 1\end{array}}{\overset{N}{\prod }}{A}_j\left(z_j\right)}\right),z_{i+1},\cdot \cdot \cdot ,z_N]\left(i=1,2,\cdot \cdot \cdot ,N\right)\end{array}$ (3)

定义在 $t_n$ 时刻第i号站点开始接受服务时，第j号站点存储器中平均存储的信息分组数(即信息分组的平均排队队长)为：

$g_i\left(j\right)=\underset{z_1,z_2,\cdot \cdot \cdot ,z_i,\cdot \cdot \cdot ,z_N\to 1}{\lim }\frac{\partial G_i\left(z_1,z_2,\cdots ,z_i\cdots ,z_N\right)}{\partial z_j}\left(i=1,2,\cdot \cdot \cdot ,N;j=1,2,\cdot \cdot \cdot ,N\right)$

化简得到完全服务系统的平均排队队长：

$g_i\left(i\right)=\frac{N\gamma \lambda \left(1-\rho \right)}{1-N\rho }$ (4)

轮询周期为服务器按照完全服务策略对所有站点完成一次服务所用时间的统计平均值，它由服务时间和转换时间构成。利用平均循环周期和平均排队队长的关系得：

$\begin{array}{l}\bar{\theta }={\displaystyle \underset{i=1}{\overset{N}{\sum }}\left[g_i\left(i\right){\beta }_i+g_i\left(i\right){\beta }_i{\lambda }_i{\beta }_i+g_i\left(i\right){\beta }_i{\left({\lambda }_i{\beta }_i\right)}^2+\cdot \cdot \cdot +{\beta }_i{\gamma }_i\right]}\\ =N{\beta }_i{g}_i\left(i\right)\frac{1}{1-\rho }+N{\beta }_i{\gamma }_i=\frac{N\gamma }{1-N\rho }\end{array}$ (5)

系统的吞吐量是指单位时间内完全服务轮询系统所能传输的信息分组数，其表达式为：

$T=N\rho$ (6)

3. FPGA设计实现

FPGA (Field-Programmable Gate Array)，即现场可编程门阵列，它是在PAL、GAL、CPLD等可编程器件的基础上进一步发展的产物。它是作为专用集成电路(ASIC)领域中的一种半定制电路而出现的，既解决了定制电路的不足，又克服了原有可编程器件门电路数有限的缺点。以硬件描述语言(Verilog或VHDL)所完成的电路设计，可以经过简单的综合与布局，快速的烧录至FPGA上进行测试，本文采用Verilog语言。可以根据需要，通过可编辑的连接把FPGA内部的逻辑块连接起来，内部电路的逻辑块和连接可以按照设计者而改变，所以FPGA可以完成所需要的逻辑功能。FPGA开发需要从顶层设计、模块分层、逻辑实现、软硬件调试等多方面着手。本文采用Altera公司的开发平台Quartus II来进行开发。

根据FPGA并行计算的特点 [12] 和自顶向下的设计思路，完全服务轮询系统需要区分功能进行模块化设计。信源模块需要能够产生具有一定到达率的、符合泊松分布达到的信息分组；站点模块能够在读、写信号的控制下实现信息分组的存储和发送功能；轮询控制模块能够实现符合完全服务策略的控制功能；接收终端模块能够完成从总线上读取该终端所对应的站点发送的信息分组的功能。

3.1. 信源模块

根据实际网络中的业务情况，信源模块要产生多位符合泊松分布到达的信息分组。利用现有的FPGA软核来设计是不易实现的。MATLAB软件中有可产生泊松分布的函数Poissrnd。那么就可以利用FPGA的ROM对MATLAB产生的泊松分布序列进行读取，但读出结果是2位的。再设计出具有2位到8位映射功能的转换模块，将ROM读出的2位序列转换为8位，作为信源输出的信息分组。设计时，统一将有效信源输出设定为10101010。图1为信源模块输出仿真结果。图中，gc为ROM读取的泊松分布序列，q为8位信源输出信息分组。

3.2. 站点模块

根据完全服务轮询系统的工作模式，站点模块需具备以下功能：当写信号有效时，存储信息分组；当读信号有效且站点存储器中有需要发送的信息分组时，按照FCFS (First Come First Served)的原则读取存储器内的信息分组；当存储器内的信息分组全部发送完时，输出存储器为“空”的标志信号为高电平。图2为4个站点的电路设计框图。4个站点是采用异步Fifo进行设计的。“写入信号”有效时，则存储当前的信息分组；“读出信号”有效且站点存储器不为“空”时，则按“先进先出”的顺序读取存储器内的信息分组；存储器内的信息分组全部发送完时，存储器为“空”的标志信号“empty”置为高电平。此时，开始查询下一个站点。若所查询的站点的存储器为“空”的标志信号“empty”为低电平，即存储器内有需要发送的信息分组，则对该站点进行服务，否则转到查询下一个站点。这与设计站点模块所要完成的功能是一致的。

Figure 1. Simulation results for the source module

图1. 信源模块仿真结果

Figure 2. Block diagram of the site circuit design

图2. 4站点电路设计结构框图

3.3. 轮询控制模块

轮询控制模块是完全服务轮询系统的核心模块，控制系统按照完全服务的策略进行工作。图3是轮询控制模块状态转换图。当某一站点获得服务权限时，首先判断该站点的存储器为“空”的标志信号“empty”是否为低电平，若为低电平，则说明该站点有需要发送的信息分组，就开始对该站点服务。同时，每发送完一个信息分组就对该站点存储器为“空”的标志信号“empty”进行一次判断，若为高电平，则说明

已发送完该站点存储器内所有的信息分组，就转到查询下一个站点，否则，继续为当前站点服务，这与完全服务策略是相符的。

3.4. 接收终端模块

接收终端要完成从总线上读取该终端所对应的站点发送的信息分组。终端模块结构如图4所示。图中，滤波模块的作用是滤除全零的不正确信息分组。接收到的信息分组存储在Fifo内，由持续高电平的“读取控制r”信号控制读取信息分组。输出端，只有当Fifo不为空(即empty为低电平)时，读出的数据才是所要接收的正确的信息分组。

3.5. 轮询控制模块

图5为完全服务轮询系统的FPGA顶层设计图。图中，4个信源产生的信息分组在轮询控制模块的控制下，在4个站点中按照完全服务策略进行存储和发送。4个站点发送的信息分组经“或”运算后发送到总线上。由于4个站点不可能同时发送信息分组，故不会产生碰撞问题。4个接收终端从总线上读取各自所对应的站点发送的信息分组，完成正确接收，实现系统功能。

4. 系统性能评估

4.1. 仿真测试

图6是所设计的完全服务轮询系统的仿真测试结果。4号接收终端的信息分组r4与4号站点发送的信息分组d4是完全相同的，只是在时间上有一个时隙的延迟。而且信息分组都是10101010，这与信源

Figure 3. State machine of the polling control module

图3. 轮询控制模块状态机

Figure 4. Module structure diagram of the receiving terminal

图4. 接收终端模块结构图

Figure 5. FPGA top-level design diagram of the full service polling system

图5. 完全服务轮询系统FPGA顶层设计图

Figure 6. Module structure diagram of the receiving terminal

图6. 接收终端模块结构图

模块产生的信息分组是一致的。图中s1、s2、s3、s4为4个站点获得服务权限的标志信号，可以看出，4个站点是按照由1到4再到1的逻辑顺序循环查询的，这与轮询系统的工作原理是相符的。pbus为总线上传输的信息分组，可以看出总线空闲的时段较短，说明总线的利用率较高。把所设计的系统下载到DE2开发板上，测试结果与仿真结果相同。

4.2. 统计分析

统计仿真过程中总线上传输的信息分组的总数(图6中gro的值)和循环周期总数。在FPGA系统仿真中，利用MATLAB产生泊松数据作为系统的输入数据源，当数据到达时，把数据存入数据接收模块。

Table 1. The statistical value and the theoretical value

表1. 统计值与理论值对比

如果某一站点获得服务权限时，对该站点发送控制信号并对其进行服务，统计其到达的数目，直至统计完所有的数据。最后，统计每一个站点的信息分组总数、循环周期总数、平均队长、平均轮询周期、系统的吞吐量等重要指标。根据完全服务策略可得到平均排队队长、平均轮询周期和系统吞吐量的统计表达式：

平均排队队长

$\stackrel{\approx }{g}=\frac{N_{gro}}{N\times N_{cp}}$ (7)

平均轮询周期

$\stackrel{\approx }{\theta }=\frac{T_{all}}{N_{cp}}$ (8)

系统吞吐量

$\stackrel{\approx }{T}=\frac{N_{gro}}{T_{all}}$ (9)

其中， $N_{gro}$ 为总线上传输的信息分组总数，N为终端个数， $N_{cp}$ 为统计循环周期总数， $T_{all}$ 为仿真总时长。表1是利用式(4)、式(5)、式(6)和式(7)、式(8)、式(9)计算了在分组到达率 $\lambda =0.15$ 、服务时间 $\beta =1$ 、转换时间 $\gamma =2$ 和仿真时长分别为 $T_{all}=100\text{μs}$ 、 $T_{all}=200\text{μs}$ 、 $T_{all}=500\text{μs}$ 、 $T_{all}=600\text{μs}$ 、 $T_{all}=800\text{μs}$ 条件下的平均排队队长、平均轮询周期和系统吞吐量的理论值和统计值。

通过表1中统计值和理论值的比较可以看出，二者是非常接近的，且随着仿真时长的增加，统计值是向着理论值收敛的，这与理论实际是一致的。

5. 结论

本文着眼于物联网MAC协议，讨论了CSMA、CSMA/CA、S-MAC等基于竞争型的MAC协议的不足。根据轮询系统的独特性和FPGA具有的灵活性、可重构性等优势，对基于完全服务轮询机制的MAC协议进行了设计。通过软件仿真、硬件测试和统计分析，所设计的系统在功能上和指标参数上都达到了要求，实现了设计目标。利用FPGA设计的基于完全服务轮询机制的MAC协议能够有效避免数据冲突、减小传输时延、提高系统吞吐量和总线利用率，可广泛用于无线传感器网络、物联网、蓝牙网络、WLAN等领域。