基于现场可编程逻辑门阵列的多优先级改进型载波感知多址协议在Ad Hoc网络中的实现和性能

丁洪伟，陆旭，2，杨志军，3，保利勇，柳虔林，4

(1.云南大学 信息学院，云南 昆明 650500；2.武警云南省总队 昆明支队，云南 昆明 650051；3.云南省教育厅 科学教育研究院，云南 昆明 650223；4.云南省军区，云南 昆明 650051)

0 引言

Ad Hoc网络的自组织性、抗毁性、抗干扰性等是军队实现有效通信的关键指标[1-2]。Ad Hoc网络中的媒体访问控制(MAC)层协议决定了节点接入信道的方式，对网络的连通具有极其重要的意义[3]，而载波感知多址(CSMA)协议是MAC层被广泛应用的随机多址接入控制协议之一。娄思佳等[4]分析了通信干扰条件下Ad Hoc网络的效能，证实了实施通信干扰的实践可行性。王海涛等[5]阐述了Ad Hoc网络面临的可生存性问题和技术挑战，并对可生存网络连接和可生存通信服务进行了全面剖析。刘广钟等[6]改进了高速无线局域网媒体竞争接入协议，有效改善了高密度节点竞争接入无线局域网 (WLAN)的性能。周圣杰等[7]实现了基于空闲时隙、传输时隙和退避控制时隙的三维概率CSMA协议，但是在现场可编程逻辑门阵列(FPGA)中时序电路不能捕捉到退避策略控制时隙，该方法不能通过硬件电路系统实现。徐智等[8]实现了基于FPGA的双优先级CSMA协议。

本文一方面改进传统的时隙分配方法，以增加传输节点针对不同信道状态的发送概率，有效改善节点接入数量较大情况下系统的吞吐量；另一方面增加多优先级控制策略，以实现针对不同用户需求的区分服务，同时为网络系统付费服务提供参考。

1 改进型三维概率CSMA协议模型的建立和计算机仿真

1.1 改进型三维概率CSMA协议

在未对Ad Hoc网络中的传输节点设定优先级时，假设所有传输节点的优先级相同，均采用公平竞争的方式接入信道。改进型三维概率CSMA协议的接入控制策略为：需要发送数据包的节点首先对信道进行检测，如果检测到信道处于空闲、成功、碰撞状态，则该节点分别以概率Pi、Pu、Pb决定发送数据(以概率(1-Pi)、(1-Pu)和(1-Pb)决定放弃发送)。

对改进型三维概率CSMA协议的模型作如下假设与变量定义：

1)传输信道无噪声干扰，为理想状态[9]。

2)信息分组的到达过程满足泊松分布，传输信道在时间t内到达k个信息分组的概率[10-11]为

(1)

式中：w为时间t内到达的信息分组数；k为非负整数；λ为信息分组的到达率；t为仿真时长。

3)归一化空闲时隙长度和时延长度都为a，有信息分组发送成功的时隙长度归一化为1(1是a的整数倍)[12-13]，信息分组发生碰撞的时隙长度定义为b.

结合(1)式，推导得出改进型三维概率CSMA协议系统的吞吐量S为

(2)

式中：v=e-(b+a)Pbλ+(b+a)Pbλe-(b+a)Pbλ；x=e-(1-b)λ；y=1-e-aPiλ；z=1-(1+a)Puλe-(1+a)Puλ.

根据(2)式，对改进型三维概率CSMA协议模型在碰撞时隙长度分别为归一化0.1、0.3、0.5、0.7、0.9条件下的吞吐量进行计算机仿真，得到如图1所示的结果。

分析图1可知，在硬件工艺设计允许的条件下，分配的碰撞时隙长度越短，得到的系统吞吐量越大。

1.2 改进型三维概率CSMA协议和其他接入控制协议的吞吐量比较

根据随机多址控制协议的接入策略和(1)式，首先对传统的P坚持CSMA协议和1坚持CSMA协议模型的吞吐量进行分析。

传统的P坚持CSMA协议的吞吐量Stp[14]为

(3)

传统的1坚持CSMA协议的吞吐量St1[15]为

(4)

分析(3)式和(4)式可以发现它们之间特殊的联系：1坚持CSMA协议是P坚持CSMA协议的一种特殊形式，当概率为1时，P坚持CSMA协议就变成1坚持CSMA协议。

对两种传统接入控制协议的吞吐量进行仿真，得到如图2所示的结果。

图2 传统接入控制协议的吞吐量比较Fig.2 Throughputs of traditional access control protocols

分析图2可知，在1<λ<10的区间，P坚持CSMA协议的吞吐量大于1坚持CSMA协议，因此P坚持CSMA协议在λ较大的情况下表现更佳。

下面对改进的随机多址接入控制协议模型进行分析。

图3所示为改进型三维概率CSMA接入控制协议模型[16-17]。图3中，箭头表示信息分组的到达，箭头的数目表示到达的信息分组数，U、B和I分别表示信息分组成功发送、发生碰撞和空闲3种信道状态，Tn表示一个平均周期，1、a、b分别表示信息分组发送成功、信道空闲、发生碰撞占用的1个时隙长度。

图3 改进后的协议模型Fig.3 Optimized protocol model

传统的P坚持CSMA协议模型的数据分组碰撞和成功发送都为其分配归一化为1的时隙长度；改进型P坚持CSMA协议模型将碰撞时隙长度定义为变长的b.根据图3，再结合(1)式、(2)式、(3)式和(4)式，得到改进型P坚持CSMA协议的吞吐量Sip为

(5)

式中：xip=e-(1-b)λ；yip=1-e-aPipλ；zip=1-(1+a)λe-(1+a)λ；vip=e-(b+a)λ+(b+a)λe-(b+a)λ.

改进型二维概率CSMA协议在改进型P坚持CSMA协议的基础上，增加对数据分组发生碰撞和成功发送两种状态的检测概率Pbu.根据(1)式和(5)式，得出改进型二维概率CSMA协议的吞吐量Si2为

(6)

式中：xi2=e-(1-b)λ；yi2=1-e-aPi2λ；zi2=1-(1+a)·Pbuλe-(1+a)Pbuλ；vbu=e-(b+a)Pbuλ+(b+a)·Pbuλe-(b+a)Pbuλ.

将改进型二维概率CSMA协议的碰撞状态检测概率改为Pb，得到改进型三维概率CSMA的协议模型。根据改进型随机多址接入控制协议模型和(2)式、(3)式、(4)式、(5)式和(6)式，通过计算机仿真，得到改进型三维概率CSMA协议与传统P坚持CSMA协议、传统1坚持CSMA协议、改进型P坚持CSMA、改进型二维概率CSMA协议的吞吐量对比，如图4所示。

图4 不同随机多址模型的吞吐量对比Fig.4 Throughputs of different random multiple access models

由图4可知：在λ<1的情况下，改进后协议模型和传统协议模型的吞吐量基本一致，但是λ>1后，改进后协议模型的性能优于传统协议模型，尤其改进型三维概率CSMA协议的性能明显优于图4中的其他4种随机多址协议；与传统1坚持CSMA协议吞吐量的最大值相比，改进后三维概率CSMA协议增长24.34%；当λ=7.35时，传统1坚持CSMA协议模型的吞吐量下降为0，而改进型三维概率CSMA协议的吞吐量为0.431 8；当λ=10时，传统P坚持CSMA协议模型的吞吐量也下降为0，而改进型三维概率CSMA协议的吞吐量为0.330 8.

2 多优先级改进型三维概率CSMA协议的数学模型建立

针对Ad Hoc网络中的MAC层不同接入业务具有不同传输要求的特点，设计多优先级接入控制模型，以满足不同传输需求。考虑到不同业务的收费不一，缴纳费用越高的用户，对传输质量要求越高，传输内容可能也越多，因此优先级也可以为收费标准的制作提供参考。本文针对不同优先级的传输节点，设置优先级1～N，发送数据的信道为N条。通过采用优先级越高的节点占用的信道数越多的控制方案，达到有效利用有限信道资源的目的。图5所示为优先级和信道数皆为N的多优先级信道负载均衡接入控制模型。

图5 多优先级接入控制模型Fig.5 Multi-priority access control model

由图5可知，优先级从低到高依次为优先级1，优先级2，…，优先级N.优先级越高，占用的信道资源也越多，处于优先级N的节点占用信道1～信道N.因此，优先级节点为y的节点在通道x上的到达率[18-21]为

(7)

式中：Gx为信道x的容量。

考虑到信道的负载均衡，每条信道的容量是有限的并且是一致的。在对多优先级改进型三维概率CSMA接入控制协议进行分析前，对如下变量进行定义：

1) 传输节点的优先级总数和总的信道数量都为N.

2) 由于信道负载均衡，信道容量为Gx=G(x=1，2，3，…，N)。

3) 优先级为y的节点在无线信道x上的到达率为λy.

4)KUi、KIi和KBi分别表示信道i中的成功事件、空闲事件和碰撞事件的平均数目；E(Ui)、E(Ii)和E(Bi)分别表示信道i中的成功事件、空闲事件和碰撞事件的占用时隙平均长度；Sy表示优先级为y的节点吞吐量；SN表示多优先级改进型三维概率CSMA接入控制协议的系统吞吐量。

Ad Hoc网络中MAC层的N优先级改进型三维概率CSMA接入控制协议的吞吐量[18-21]为

(8)

多优先级改进型三维概率CSMA协议系统优先级为y的节点吞吐量[18-21]为

(9)

对三优先级系统吞吐量进行计算机仿真，得到如图6所示的结果。

图6 多优先级模型的系统吞吐量Fig.6 System throughput of multi-priority model

分析图6可知：传输节点的优先级越高，吞吐量越高。根据(7)式可以得到优先级为1、2和3的节点分别占据一条信道容量的1/3、5/6和11/6.图6中没有设定优先级的节点吞吐量大于优先级1和优先级2，但是明显小于优先级3，该结论与理论值刚好吻合，同时三优先级改进型三维概率CSMA协议系统的吞吐量是没有设定优先级的3倍，亦与信道均衡的原理相符，从而证明了本文模型的合理性。

3 基于FPGA的多优先级改进型三维概率CSMA协议实现

FPGA应用于硬件电路设计有许多优势，通过FPGA的设计能够实现异步传输；部分功能模块可以通过编程实现，缩短开发周期；电路系统是分模块设计，对部分功能做出调整时无需改变电路全局。

根据理论分析，在进行多优先级改进型三维概率CSMA协议的硬件设计时，有4方面需要重点改进：重新对信道状态进行定义和分类；调整时隙分配的策略；针对不同信道状态设定不同的发送概率；添加多优先级模块，使信道资源得到更加合理地利用。多优先级改进型三维概率CSMA协议的硬件实现模块分为数据源模块、信道状检测分类模块、时隙分配模块、多优先级模块和数据接收统计模块。系统设计模型如图7所示。

图7 硬件实现的系统图Fig.7 System diagram of hardware implementation

若无特殊说明，硬件设计均采用以下参数。分别设定碰撞时隙长度b=0.5，检测概率Pi=0.9、Pu=0.8、Pb=0.5.下面对各个硬件功能模块进行逐一介绍。

1)数据源模块。数据源模块模拟了信息分组的到达过程，该模块通过Quartus Ⅱ中的只读存储器(ROM)和计数器读取MATLAB软件产生的泊松数据。图8中，INPUT表示数据源模块的输入；count5000为计数器；VCC表示接入电路电压，是系统的电源端；ROM1表示ROM模块；address[15..0]是计数器count5000的输出和ROM模块存取的控制端；clock为ROM模块的时钟控制信号；Block type:AUTO表明ROM的类型为自动；q[3..0]表示ROM读取数据的输出；OUTPUT为数据源模块的输出。MATLAB软件提供的泊松数据源能够更好地保证信号源随机性原则，为后续验证系统的正确性提供保证[8]。

图8 数据源模块的硬件实现Fig.8 Hardware implementation of data source module

2)信道状态检测和分类模块。在总线结构中，通过检测当前的信道状态为节点确定发送概率提供参考条件，采用不同的二进制数值代表检测出的信道状态[8](没有数据包发送用“00010001”(即十进制的17)表示；只有一个数据包发送用“00010010”(即十进制的18)表示；超过一个数据包发送用“00010011”(即十进制的19)表示)。具体的FPGA设计如图9所示。图9中，g[7..0]表示状态检测的输出；gc[3..0]表示节点发送的信息分组数；s1表示信号源模块；div8是八分频模块，通过八分频实现一个字节八位的时钟控制；CT表示信道的检测分类模块。

图9 信道状态检测和分类模块Fig.9 Channel state detection and classification module

对信道状态检测和分类模块的硬件实现进行验证，结果如图10所示。

图10 信道状态检测和分类模块仿真结果图Fig.10 Simulated results of channel state detection and classification module

图10中，clk为系统的时钟控制信号；rst为复位信号；g表示检测到的信道状态，gc表示节点发送的信息分组。节点发送的信息分组数分别为0、1、2、3、1、0、1、2、1，检测到的信道状态分别为17、18、19、19、18、17、18、19、18.节点发送信息分组数和检测到信道状态完全吻合，表明该模块设计的正确性。

3)时隙分配模块。进行该模块的硬件设计时，根据理论模型的时隙分配方法，为碰撞状态分配归一化为0.5的时隙长度；为成功状态分配归一化为1的时隙长度，为空闲状态分配归一化为0.1的时隙长度。通过异步先入先出(FIFO)在不同时钟控制下完成数据的读写，反馈控制模块control针对信道的实时状态完成时隙分配并将分配情况反馈到异步FIFO.FPGA设计如图11所示。图11中，data[7..0]表示未进行时隙控制的输出；site1表示反馈控制信号；q[7..0]表示完成时隙控制的输出；Switch1是完成状态检测分类的集成模块；FIFO为异步FIFO，control为反馈控制模块。

图11 时隙分配模块的硬件实现Fig.11 Hardware implementation of slot allocation module

对时隙分配模块的硬件实现进行验证，结果如图12所示。

图12 时隙分配模块的硬件实现仿真结果Fig.12 Simulated results of hardware implementation of slot allocation module

图12中，ena为时隙控制的使能端；q表示通过反馈控制模块control后的输出，data表示没有进行时隙控制情况下的输出。

从图12中可以看出：17作为信道的空闲状态时，反馈前后的时隙长度一致；18作为数据包成功发送的状态，被延长为10倍；19作为数据包发生碰撞的状态，被延长为5倍。验证结果和理论分析完全一致，表明该模块设计的正确性。

4)多优先级模块。该模块为不同发送节点提供不同的带宽，优先级越高，获得的带宽越宽，发送的数据量越大。FPGA设计如图13所示。图13中，P1、P2和P3分别表示优先级为1、2和3的传输节点发送信息分组情况。

图13 多优先级模块的硬件实现Fig.13 Hardware implementation of multi-priority module

5)数据接收统计模块。在进行该模块设计时，为了确保接收的数据准确性，必须保证接收时钟和时隙分配时钟一致。FPGA设计如图14所示。

图14中，CH1模块表示信道1中传输的数据，statiscs1模块用以实现对信道1中数据的接收、统计。

图14 接收情况统计模块的硬件实现Fig.14 Hardware implementation of receiving statistics module

4 系统性能分析

4.1 吞吐量分析

4.1.1 改进型三维概率CSMA协议硬件系统的吞吐量统计分析

将不同到达率下硬件系统的吞吐量测试值和理论值进行对比，验证硬件系统设计的合理性。

发送数据的最小单元为1个字节，设定系统时钟是10 ns，最小时隙的长度为80 ns，即空闲状态占用的时隙长度；数据成功发送占用的有效时隙长度为最小时隙的10倍，其占用的时隙长度为800 ns；数据发生碰撞占用的有效时隙长度为最小时隙的5倍，其占用的时隙长度为400 ns.因此硬件系统的吞吐量为

(10)

式中：Sh为硬件系统的吞吐量；KU为发送成功的信息分组数；T为仿真的总时长。

对硬件系统在到达率λ取值为1～7时的吞吐量进行统计分析，具体结果如图15～图21所示。

图15 到达率为1的信息分组接收情况Fig.15 Information packet receiving with arrival rate of 1

由图15可见，每成功接收一个信息分组，成功事件“sucess”的统计就加1.500 μs的测试时间内，成功接收的信息分组数为327，应用(10)式得到系统吞吐量为0.523 2，根据(2)式可求出系统的理论吞吐量为0.523 9.故硬件测试值和理论值的相对误差为0.134%.

由图16可见，500 μs的测试时间内，成功接收的信息分组数为368，应用(10)式得到系统吞吐量为0.588 8，根据(2)式可求出系统的理论吞吐量为0.585 1.故硬件测试值和理论值的相对误差为0.632%.

图16 到达率为2的信息分组接收情况Fig.16 Information packet receiving with arrival rate of 2

由图17可见，500 μs的测试时间内，成功接收的信息分组数为342，应用(10)式得到系统吞吐量为0.547 2，根据(2)式可求出系统的理论吞吐量为0.558 5.故硬件测试值和理论值的相对误差为2.02%.

图17 到达率为3的信息分组接收情况Fig.17 Information packet receiving with arrival rate of 3

由图18可见，500 μs的测试时间内，成功接收的信息分组数为321，应用(10)式得到系统的吞吐量为0.513 6，根据(2)式可求出系统的理论吞吐量为0.515 4.故硬件测试值和理论值的相对误差为0.35%.

图18 到达率为4的信息分组接收情况Fig.18 Information packet receiving with arrival rate of 4

由图19可见，500 μs的测试时间内，成功接收的信息分组数为290，应用(10)式得到系统吞吐量为0.464，根据(2)式可求出系统的理论吞吐量为0.469 1.故硬件测试值和理论值的相对误差为0.51%.

图19 到达率为5的信息分组接收情况Fig.19 Information packet receiving with arrival rate of 5

由图20可见，500 μs的测试时间内，成功接收的信息分组数为267，应用(10)式得到系统的吞吐量为0.427 2，根据(2)式可求出系统的理论吞吐量为0.422 2.故硬件测试值和理论值的相对误差为1.18%.

图20 到达率为6的信息分组接收情况Fig.20 Information packet receiving with arrival rate of 6

由图21可见，500 μs的测试时间内，成功接收的信息分组数为234，应用(10)式得到系统吞吐量为0.374 4，根据(2)式可求出系统的理论吞吐量为0.375 4.故硬件测试值和理论值的相对误差为0.27%.

图21 到达率为7的信息分组接收情况Fig.21 Information packet receiving with arrival rate of 7

根据图15～图21，得到硬件系统的测试值和理论值的对比如表1所示。

表1 硬件系统的测试值和理论值比较Tab.1 Comparison of simulated and theoretical values of hardware system

由表1可知：基于FPGA设计的硬件电路系统吞吐量的测试值和理论值基本吻合，相对误差最大值也仅为2.02%，证明了系统设计的合理性。

4.1.2 多优先级的改进型三维概率CSMA协议硬件系统的吞吐量统计分析

根据(7)式设置硬件系统中优先级为1的节点到达率为4，优先级为2的节点到达率为10，优先级为3的节点到达率为22.对多优先级硬件系统成功接收信息分组的情况进行统计，得到如图22所示结果。

图22 系统信息分组的接收情况统计Fig.22 Statistics on the receiving of system information packets

图22中，500 μs的测试时间内，channel1_*显示优先级为1的节点在信道1中成功发送的信息分组数分别为352和357；channel2_*显示优先级为2的节点在信道1和2中成功发送的信息分组数分别为357、339、349、343、356；channel3_*显示了优先级为3的节点在信道1、2和3中成功发送的信息分组数分别为348、359、350、351、352、364、345、357、345、353、349.优先级为1、2和3的节点占用信道的比例分别为0.336 2、0.827 1和1.836 7.根据(9)式可得优先级为1、2和3的节点占用信道的比例分别为0.333 3、0.833 3和1.833 3.因此，硬件系统中各优先级占用信道的比例和理论值一致，证明了系统设计的正确性。

4.2 时延分析

4.2.1 理论模型的时延分析

在Ad Hoc网络的接入控制模型中，Edi表示第i条信道中时延平均长度，Sdi表示第i条信道中时延占仿真时长的比例。则平均时延和时延占仿真时长的比例分别[16-17]为

Edi=N·a·(KUi+KBi)；

(11)

(12)

对改进前后系统的时延占比进行仿真分析，结果如图23、图24所示。

图23 改进后模型的理论时延占比情况Fig.23 Delay proportion of the modified model

图24 传统模型的理论时延占比情况Fig.24 Delay proportion of traditional model

由图23和图24可见，随着到达率的增加系统，时延所占的比例不断增加，但是图24在到达率大于6后不再增加，因为此时系统的吞吐量基本趋近于0，改进后模型则在到达率大于20后才趋于稳定，间接证明了改进后系统在到达率较大情况下的吞吐量明显大于改进前。相同到达率情况下，改进后模型的时延占比大于改进前，但是改进后模型在相同仿真时间下，成功接收信息分组的数更多。

4.2.2 硬件系统的时延分析

为了验证系统的时延性能，在λ=2的条件下，对改进前后硬件系统进行仿真，并统计碰撞事件、空闲事件和成功事件的数量。计算出系统的时延为

τ=T-800KU-400KB-80KI.

(13)

系统设定仿真时长T为500 000 ns，统计结果如图25和图26所示。

图25 到达率为2的传统CSMA协议接收信息分组情况Fig.25 Information packets received by traditional CSMA protocol with arrival rate of 2

图26 到达率为2的改进型CSMA协议接收信息分组的情况Fig.26 Information packets received by improved CSMA protocol with arrival rate of 2

图25中，“success”表示成功接收的信息分组数，“collision”表示碰撞事件数，“idle”表示空闲事件数。每成功发送1个信息分组，“success”的数目加1；1个碰撞事件发生时，“collision”的数目加1；每个空闲事件发生时，“idle”的数目加1.500 μs的测试时间内，成功事件(success)、空闲事件(idle)和碰撞事件(collision)的数量最终统计分别为284、209和265.根据(13)式得到系统总时延为44 080 ns，占仿真长度的8.816%，因此平均成功发送一个信息分组的时延为155.211 ns.理论时延占比为8.109%，仿真时延占比和该值仅相差0.71%.

图26中，500 μs的测试时间内，成功事件、空闲事件和碰撞事件的数量最终统计分别为359、287和335.根据(13)式得到系统时延为54 400 ns，占仿真长度的11.168%，因此平均成功发送一个信息分组的时延为151.53 ns.理论时延占比为10.16%，仿真时延占比和该值仅相差1.008%.

由此可知，改进后系统时延占比增加了2.352%，但是改进后系统成功发送的信息分组比改进前增加了75，平均成功发送一个信息分组时延减少了3.681 ns.因此，改进后系统有效减少了系统时延，改善了Ad Hoc网络传输数据的实时效果。

5 结论

本文针对Ad Hoc网络中MAC层的传统随机接入控制协议吞吐量不高、时延较大的问题，在传统协议基础上加入三维概率Pi、Pu和Pb，为空闲、成功和碰撞3种不同状态分配不同的时隙长度，增加区分服务的优先级，得到多优先级改进型三维概率CSMA协议。通过数学实验工具MATLAB软件分析，结果表明该协议有效改善了Ad Hoc网络传输的吞吐量和时延，增强了Ad Hoc的可靠性，减少了传输时延。结合FPGA模块化设计易于改进、异步传输等特点，在理论推导基础上设计了多优先级改进型三维概率CSMA接入控制协议的硬件电路系统，并对硬件系统吞吐量和时延进行测试分析，得到吞吐量测试结果和理论值的相对误差不大于2.02%，改进后系统传输时延比改进前减少了3.681 ns，吞吐量最大值增长了24.34%.由此可见，基于FPGA设计的多优先级改进型三维概率CSMA协议模型在Ad Hoc网络MAC层具有明显的优势。