限定K=1非对称轮询系统的FPGA实现

路秀迎，丁洪伟，杨志军，保利勇，何 敏

（云南大学 信息学院，昆明 650500）

无线传感器网络WSN（wireless sensor network）是由大规模随机分布在监控区域的微型传感器节点组成的以数据为中心的任务型网络，媒体接入控制 MAC（media access control）协议是联接 WSN物理层与网络层的纽带，是保证节点之间高效通信的重要因素。

文献[1-8]基于概率母函数与嵌入式马尔可夫链的方法就平均排队队长、轮询周期、等待时延等性能指标对对称式轮询系统展开分析，忽略了多样性业务的信息非对称性与服务器处理差异性，仅适用于单一服务类型的网络应用，大大限制了该技术的使用范围和适用空间。研究非对称轮询系统对WSN多业务应用具有重要的理论意义与研究价值[9]。

FPGA基于硬件并行机制工作，具有半定制、非固化的特点，控制灵活，开发周期短，运行速度相比传统串行计算CPU提高近100倍[10]，可将其作为异构加速资源应用于WSN，实现节点数据的实时处理，满足了非对称WSN在软硬件延展性、可移植性方面的要求。

系统采用限定K=1服务策略进行轮询调度，保证了簇内传感器节点之间访问介质的公平性。基于QUARTUSⅡ平台进行功能测试，并对系统性能展开理论与统计分析，结果表明该非对称轮询系统能够满足多样性业务服务质量的弹性要求，具有更好的普适性。

1 理论介绍

非对称限定K=1轮询系统的基本模型如图1所示，系统由1个中央控制器与N个排队队列（终端）组成，各终端随机变量所服从的概率分布不同，具体表现为以下几点：

图1 非对称轮询系统示意Fig.1 Schematic diagram of asymmetric polling system

（1）到达各终端的信息分组服从泊松分布，其到达速率λi表示i号终端单位时间内接收到信息分组的个数。终端之间信息分组到达率的随机变量λi相互独立且遵从不同的概率分布。其分布的概率母函数、均值、方差分别是

（2）各终端的服务时间βi表示各终端发送单位信息分组需要的时间，各终端服务时间的随机变量βi相互独立且服从不同的概率分布。其分布的概率母函数、均值、方差分别是

（3）控制器访问空闲终端i或服务完终端i后经过时间γi查询访问终端i+1，相邻终端之间的转换时间的随机变量γi相互独立且服从不同的概率分布。其分布的概率母函数、均值、方差分别为R（z），

中央控制器按照物理连接的逻辑顺序对各终端进行轮询访问，访问到的非空终端享有信息发送权，否则经过设定的转换时间访问下一终端。获得服务权限的终端按照限定K=1的服务规则发送数据，即每次只发送该终端缓存的1个信息分组。

评估轮询系统性能的参数主要有平均排队对长和平均时延，文中采用内嵌马尔可夫链与概率母函数的方法对系统展开理论分析，定义的随机变量有：vi（n）为服务器对 i号终端服务的时间，ui（n）为服务器从第i号终端转向第i+1号终端的轮询转换时间，μj（ui）为在 ui（n）时间内进入第 j号终端的信息分组数，ηj（vi）为在 vi（n）时间内进入第 j号终端中的信息分组数。定义随机变量ξi（n）为第i号终端站点在tn时刻其存储器内存储的信息分组数，各终端服务强度 ρi（ρi=λiβi）。 那么排队系统在 tn时刻的状态可表示为［ξ1（n），ξ2（n），…，ξN（n），ξh（n）］，分布函数为

定义gi（j）为tn时刻第i号节点接受服务时，第j号节点平均存储信息分组数，则有：

式中：i=1，2，…，N；j=1，2，…，N。

定义：

对式（1）求二阶偏导可得：

由式（5）～式（8）求得：

图2～图4分别为非对称限定K=1服务轮询系统的性能参数与到达率、服务时间、转换时间之间的关系图。图2 中 N=4，λ2=0.0498，λ3=0.03，λ4=0.01，β1=4，β2=2，β3=1，β4=2，γ1=2，γ2=1，γ3=3，γ4=4；图3 中N=4，λ1=0.0195，λ2=0.0498，λ3=0.03，λ4=0.01， β2=2，β3=1，β4=2，γ1=2，γ2=1，γ3=3，γ4=4； 图4 中 N=4，λ1=0.0195，λ2=0.0498，λ3=0.03，λ4=0.01，β1=4，β2=2，β3=1，β4=2，γ2=1，γ3=3，γ4=4。

2 硬件实现

图2 系统性能参数与到达率的关系Fig.2 Relation between system performance parameters and arrival rate

图3 系统性能参数与服务时间的关系Fig.3 Relation between system performance parameters and service time

图4 系统性能参数与转换时间的关系Fig.4 Relation between system performance parameters and conversion time

设计中按照WSN簇内通信的工作原理、采用“自顶向下”的设计方法把系统分为信源、节点、控制、接收4个模块部分进行硬件设计，图5为系统设计框图，表1为非对称系统相关参数值。

图5 系统设计框图Fig.5 Block diagram of the system

表1 系统设定参数值Tab.1 Values of the system parameters

2.1 信源模块

信源模块用于产生满足马尔科夫特性的信息分组，但在FPGA时序电路中难以实现“单位时隙产生具有泊松特性的多个信息分组”的精确控制，故设计中利用分频技术并借助Matlab工具产生泊松文档协同解决这一难题。利用自加1计数器原理设计地址译码电路，使得RAM在50 MHz时钟源触发下读取泊松分布.mif文档并完成原始信息在时序电路中的映射转换，为便于区分，设计中基于计数器原理将读取到的λ数值映射到电路中的λ个报文分组10 100 110，无效信息分组则转换为00 000 000，信源产生的原始数据混合了有效信息分组与无效信息分组。

2.2 节点模块

非对称轮询系统中服务器对各终端业务服务效率不同，各终端实时缓存到达信息分组并在获得服务权限时按照FCFS顺序发送，实现时通过调用FPGA异步fifo解决读写过程的速度匹配问题和独立控制问题，其工作流程分缓存与发送两部分分别进行描述。

2.2.1 缓存功能

终端缓存信息分组过程即该终端dcfifo写入过程，各终端写时钟源皆为50 MHz时钟源，其工作过程：

（1）信源产生的混合数据经过滤波电路，检测到有效信息分组置写使能信号有效，否则无效；

（2）写使能信号有效时，dcfifo在写时钟源触发下把相应的有效数据写入存储器，从根本上杜绝了信息冗余问题。

2.2.2 发送功能

非空节点获得服务权限后按照 “先到先出”的顺序发送已缓存数据，其读时钟源频率特性与系统设定服务时间一致，其工作流程：

（1）根据控制信号与dcfifo工作特性设置下溢保护电路，防止存储器读空；

（2）节点服务信号有效时，dcfifo开始输出数据；

（3）各节点设置限定指示器，通过边缘检测判定该节点进入服务状态后，根据服务时间与系统工作频率特性设计计数器，保证该节点发送一个信息分组（即经过单位服务时间）后指示器指示信号为由高电平变为低电平，结束当前服务。图6为终端1限定指示器工作流程。

2.3 数据融合

轮询系统基于资源共享理论控制各节点无竞争接入网络，保证同一时间内只有1个通信节点占用信道，有效避免了各终端发送数据的碰撞问题。簇首接收到簇内节点的数据后按照相应的算法进行融合发送至总线上。

图6 限定指示器工作流程Fig.6 Work flow chart of the limited indicator

2.4 控制模块

按照WSN簇内轮询控制原理，利用有限状态机在控制模块分别设置了4个节点服务状态与4个相邻节点轮询转换状态， 分别记为 s1，s2，s3，s4，jishu1，jishu2，jishu3，jishu4。 图7 为控制模块的状态转移图，其中各状态表示：

sn：站点 n服务状态，高电平有效；jishun：相邻站点间转换状态；Crn：站点n限定指示器指示信号；Cntn：相邻站点间转换时间计时信号；kn：站点nFIFO空信号。

图7 控制模块状态转移图Fig.7 State transition diagram of the control module

其具体工作过程：

（1）转换时间γi到，控制器访问站点i+1的存储容量，若该容量显示非0，系统进入si+1服务状态，否则进入jishui+1的转换状态。

（2）若站点i+1进入si+1服务状态，控制器根据该终端限定指示信号控制状态转移，若指示信号cri+1为低电平，系统进入γi+2的转换状态，否则表示该终端的1个信息分组尚未发送完成，系统继续si+1的服务状态。

2.5 接收模块

接收模块利用同步控制信号进行各节点发送数据信息的恢复，系统发送部分控制信号包含节点传输信息分组的时序信息，在接收端用同步控制信号作为同步fifo写使能信号便可从总线数据中正确恢复出各节点数据信息。

3 实验结果

按照上述硬件实现描述方法，对FPGA非对称限定服务轮询系统编译后于QUARTUSⅡ进行功能仿真，图8为系统仿真图。

图8 系统仿真图Fig.8 System simulation diagram

仿真图中clk信号是系统时钟，clk1是clk四分频后的时钟信号，也是系统工作的基准时钟；cp信号是服务器轮询相邻站点的转换时间信号，高电平有效；s信号是站点服务信号，高电平有效；cr信号为限定指示器的继续读取信号，高电平有效；d信号是服务器输出信号；r信号是接收端恢复信号；pbus信号是总线信号；use信号是各站点存储器缓存的数据容量信号；

由仿真图得：

（1）各终端的服务时间设定值是 4、2、1、2，限定指示器在检测到服务信号有效后变为高电平，在相应节点单位服务时间到达前电平置低。控制模块在时钟源触发下检测到cr信号失效后置其服务信号为低电平。仿真图中发送单位信息分组占据时隙数与设定值一致，表明系统实现了限定K=1服务规则的要求。

（2）系统服务过程中各终端服务信号与其输出信号在时钟控制下同步动作，高电平有效，相应的终端输出信息分组，实现了各终端存储器缓存与发送的功能。

（3）轮询系统工作过程分为相邻站点转换过程与站点服务过程，图中cp信号与s信号交互出现，cp信号占据时隙个数分别为2、1、3、4，验证了控制模块设计的正确性；

（4）系统接收信号与发送信号一致，时间延时2时隙，实现了系统对发送数据的正确接收功能。

表2～表3为系统性能参数（平均排队对长与平均时延）理论值与统计值的对比表。

表2 各节点平均排队队长理论值与统计值对比表Tab.2 Comparison of theoretical value and statistical value of average queue length of each node

表3 各节点平均时延统计值与理论值对比表Tab.3 Comparison of theoretical value and statistical value of average time delay of each node

根据表2～表3中，得出：

（1）系统参数统计值与理论值在误差允许范围内相一致，验证了设计的可行性与正确性；

（2）系统各节点平均排队队长与平均时延均随着到达率增加而提高，不会出现高并发忙碌节点的相位滞留，反映了系统为各节点提供服务的公平性；

（3）各节点平均排队队长与平均时延均随着到达率增加而非线性提高，这是由于系统节点工作的非对称性决定的，更适用于多业务应用。

4 结语

本文根据WSN网络应用中服务类型多样化、信息传递不对称的工作特点，首次基于FPGA对非对称限定K=1轮询系统进行了硬件实现，对系统信息分组到达率、服务时间、转换时间等工作特性参数设置非一致性数值，采用限定K=1服务策略实现WSN的轮询MAC层控制，保证了簇区域内节点之间介质访问的公平性，时延特性优良。功能测试与统计分析结果验证了设计的可行性，稳定性强，可拓展性高，对WSN多业务应用有更大的实用价值。