机场时隙分配方法研究

机场时隙分配方法研究（共6篇）

机场时隙分配方法研究 篇1

0 引言

F1exRay总线是新一代汽车内部网络通信协议,它为车内控制系统提供所需的速度和可靠性。F1exRay与CAN、LIN等已成为现代汽车网络总线的关键技术,它们根据传输带宽和价格比的要求被应用在汽车不同的领域,相互补充、相互支撑,组合成多种总线混合的汽车网络[1,2]。

FlexRay总线系统将事件触发和时间触发两种方式相结合,具有高速可确定性和故障容错等特点。随着FlexRay重要性的日益显现,对其研究也越来越多,然而对FlexRay网络带宽利用率的研究很少。文献[3]分析了通信周期中静态部分和动态部分的时间特性,计算了消息和任务在最坏情况下的响应时间,但没有进行时序性能验证。文献[4]计算了FlexRay消息帧的传输时间,在考虑有效FlexRay帧长度情况下,分析静态部分的网络带宽丢失率,进一步得到了静态部分的网络利用率计算公式,但没有考虑FlexRay动态部分消息传输时间。文献[5]提出一种消息的调度算法来减小总线占用率,但总线占用率计算方法中没有考虑动态消息的总线占用率。

1 FlexRay消息传输方式

1.1 FlexRay消息帧格式

FlexRay消息帧[6,7]由帧头、有效数据和帧尾三部分组成。FlexRay帧格式如图1所示。帧头部分共由5个字节组成(共40位),包括保留位、有效数据指示位、空帧指示位、同步帧指示位、启动帧指示位、帧ID、有效数据长度、头部循环校验CRC和周期计数。有效数据部分可由0~254个字节组成。帧尾部分只含有单个的数据域,即一个24位的CRC。

1.2 FlexRay媒体访问方式

FlexRay提供两种媒体接入时序的选择,一种是静态的分时多址接入时序(TDMA),一种是动态的基于最小时间片的柔性时分多址接入时序(FTDMA)[2,6]。在一个通信周期内,有4个时间等级,从最低层到最高层分别是最小时间节拍层、最大时间节拍层、仲裁网格层和通信周期层[6,7],如图2所示。

最高层即通信周期层,由静态段、动态段、特征窗和网络闲置时间四部分组成。静态段由若干个长度相等的静态时间片(static slot)组成,采用的是TDMA方式;动态段由若干个长度相等的最小时间片(minislot)组成,采用的是基于最小时间片的FTDMA方式。静态时间片和最小时间片均由若干个最大时间节拍(Macrotick,MT)组成,1个MT的时长通常被配置为1~6μs,本文用gdMacrotick表示1个MT的时长。

2 总线占用率计算方法

2.1 时间片长度

时间片长度是指消息传输使用的时间长度,这里用MT的数量表示。消息在传输过程中被分成独立的字节进行传输,为保证消息的正常传输,还需使用更多的空间,包括传输起始序列(3~15位)、帧起始序列(1位)、字节起始序列(2位)、帧结束序列(2位)、通信空闲分隔符(11位)和帧前与帧尾的触发点偏移量。FlexRay的传输序列如图3所示。

如果消息帧在动态段进行传输,则还要在帧结束序列后附加动态尾部序列。动态尾部序列时间值是变化的,最小值为2gdBit(gdBit指传输1位所需的时间)。

当消息i放在静态段传输时,假设其长度为k个字节,则传输该消息所需的静态时间片长度Ti(单位为MT的个数)为

其中,29为15位传输起始序列、1位帧起始序列、11位通道空闲分隔符和2位帧结束序列的位数之和;10为字节前的2位字节起始序列与字节的位数之和;TAPO1为静态段触发点偏移量(gdActionPointOffset)。由于静态段的静态时间片长度由最长的消息决定,因此静态时间片长度为所有时间片长度的最大值,即

当消息i放在动态段传输时,其最小时间片长度Ti为

式中,TAPO2为最小时间片触发点偏移量;2gdBit为动态尾部序列时间。

2.2 总线占用率分析

假设系统中消息总数为N,其中有m条静态消息和n条动态消息,则总线占用率U计算公式为

式中,Tc为FlexRay总线的通信周期;fi为第i个消息的传输频率;Tpi为i个消息的传输周期。

由式(4)可知,在帧数目、帧传输周期、帧长度一定的情况下,FlexRay总线占用率由静态时间片长度、最小时间片长度以及消息被分配到动态段还是静态段的分配方法决定。

3 消息分配方法设计

3.1 消息分配方法分析

在图4a中,静态时间片长度由最长的静态消息决定,因此,FlexRay总线占用率为

式中,TM2为消息M2对应的静态时间片长度。

由图4a可以看出,静态段传输的消息长度是变化的,但静态段的静态时间片长度是相等的,由此导致总线占用率较大,带宽利用率不是很高,特别是最长静态消息和最短静态消息长度差值很大的情况。本文提出一种消息分配规则,即将最长的静态消息分配到动态段进行传输,如图4b所示,以降低总线占用率,提高带宽利用率。

3.2 消息分配算法

本算法以获得最小总线占用率为目标,依据分配规则不断重复运行分配过程以获得最小总线占用率。令Uk为k(k=0,1,…,N)个消息被分配到动态段的总线占用率,则最小总线占用率可表示为

其中,总线占用率Uk的计算依据式(4),计算时需要同时考虑静态消息和动态消息的总线占用率。

该分配算法以式(4)、式(5)为基础,在计算最小总线占用率Umin时,除了不考虑消息传输失败及其处理的情况以外,还必须保证所有的FlexRay消息的传输时间都在最坏情况下的响应时间之内。

图5为算法的流程图[8?11]。FlexRay网络参数值必须提前给出,参数包括系统配置信息,如节点参数、网络带宽和消息参数等。

获取输入参数值后进行网络初始化配置,该过程包括消息分配与设定及计算时序值和占用率。消息分配包括将FlexRay消息分配到节点和根据性质不同分配到静态段或者动态段。通常情况下,周期发送的消息分配到静态段,随机发生的消息分配到动态段。在运行分配规则过程中,当消息重新分配后,需要重新计算静态段中静态时间片大小与数目,同时,需要依照所给出的消息优先级次序重新设定消息传输次序,以保证消息传输的实时性。时序值是指消息实际传输时间与所规定传输时间的比较值。通过时序值判断消息是否在响应时间内传输完,若所有消息在最坏情况下的响应时间内传送,则时序值为1,否则为0。

在进行消息分配时,必须保证每个消息在截止时间前传输完毕。当分配方法改变时,如果U*<U(U和U*分别为分配方法改变前后的总线占用率),即总线占用率降低,则该消息将被分配到动态段;否则该消息被分配到静态段。在初始化网络配置完成后,分配过程被重复执行以得到总线占用率的最小值,该分配过程在没有静态消息被分配到动态段时结束。

4 实验验证

本文引用文献[5]中所用的美国汽车工程学会(SAE)的基准数据(表1)对消息分配算法进行验证。由于不同传输速率下,传输一帧要求的时间不一样,而在gdMacrotick值一定的情况下,所需MT数目也不同,为了表述方便,表1中将帧的长度用不同传输速率下所需时间片长度即MT的数目来表示。进行验证的FlexRay通信参数在表2中定义。

由表1可知,为了保证所有的消息在截止时间前传输完毕,FlexRay通信周期不能超过5ms。如果将传输周期为1000ms的帧放在静态段中传输,则200个通信周期才能传输一次,这不符合FlexRay协议中通信周期计数器不能超过63的规定。因此,消息帧16、17和18首先被分配在动态段中传输。

由表1可看出,消息12所需的时间片最多,当传输速率为5Mbit/s时,初始阶段静态时间片长度为60MT。在算法的初始阶段,静态时间片长度由最长消息12所需的MT数目决定。根据分配规则,静态段最长的消息帧被分配到动态段传输。表3显示了5Mbit/s速率下静态段参数值的变化及总线占用率的变化。在分配算法的初始化阶段,消息16、17、18被分配到动态段,其他消息被分配到静态段。通过运行分配算法,最终8个消息被分配到动态段,此时,静态段时间片长度为40MT,总线占用率减小到最小值4.8176%。

不同传输速率下,使用该消息分配算法后得到的总线占用率数据如表4所示,由表4可知,传输速率越低,该消息分配算法使总线占用率下降得越多,网络利用率越高。

5 结语

本文基于FlexRay帧格式和物理层传输规则分析FlexRay消息帧的长度,得到消息长度计算方法。通过对FlexRay消息帧在静态段和动态段传输时间的分析,计算总线带宽利用率,最终得到总线占用率的计算公式。实例验证表明,将静态段最长的消息帧放在动态段进行传输,在不同传输速率下,总线占用率都得到了降低。下一步工作将对动态段消息传输的时间性能和调度规则进行研究。

摘要：消息时隙分配问题是FlexRay汽车网络设计的关键问题之一。在分析FlexRay消息帧格式和消息物理层传输规则的基础上,推导出了FlexRay消息传输时间片长度和总线占用率计算公式,给出了影响总线占用率的主要因素;以最小总线占用率为目标,提出了将静态段最长消息帧分配到动态段的时隙分配方法。实验表明,该消息时隙分配方法可有效地降低总线占用率,提高网络使用的效率。

关键词：FlexRay总线,总线占用率,时隙分配,消息帧

参考文献

[1]王跃飞,王子涵,张利,等.基于改进调度算法的新一代汽车总线及其网关[J].电子测量与仪器学报,2011,25(10):289-295.

[2]顾嫣,张凤登.FlexRay动态段优化调度算法研究[J].自动化仪表,2009,30(12):25-29.

[3]Kang Minkoo,Park Kiejin,Kim Bongjun.Determi-ning the Size of a Static Segment and Analyzing the Utilization of In-Vehicle FlexRay Network[C]//Third International Conference on Convergence and Hybrid Information Technology.Daejeon,Korea,2008:50-53.

[4]Kang Minkoo,Park Kiejin,Kim Bongjun.A Static Message Scheduling Algorithm for Reducing FlexRay Network Utilization[C]//IEEE Interna-tional Symposium on Industrial Electronics.Lisbon,Portugal,2009:1287-1291.

[5]Matthias H,Hss V,Müller-Glaser V.Physical Layer Extraction of FlexRay Configuration Parame-ters[C]//IEEE International Symposium on Rapid System Prototyping.Paris,2009:173-180.

[6]罗峰,陈智琦,刘矗,等.基于FlexRay的车载网络系统开发[J].电子测量与仪器学报,2009,23(增刊):289-295.

[7]Schmidt K,Schmidt E G.Message Scheduling for the FlexRay Protocol:the Static Segment[J].IEEE Transactions on Vehicular Technology,2009,58(5)2170-2179.

[8]赵欢,熊振华,丁汉.基于IEEE1394的运动控制系统总线协议与同步机制研究[J].中国机械工程,2009,20(23):2850-2855.

[9]张利,李县军,王跃飞.汽车CAN网络时钟同步方法研究[J].电子测量与仪器学报,2011,25(2):147-152.

[10]张利,王跃飞,严刚,等.混合动力汽车CAN网络优先级的动态分配方法[J].农业机械学报,2011,42(5):22-26.

[11]李传斌,严刚,刘梦阳.FlexRay-CAN网关中的多队列消息处理方法[J].合肥工业大学学报,2011,34(1):28-33.

机场时隙分配方法研究 篇2

随着我国航空运输业的迅速发展,飞行需求急剧增加与机场及空域容量供给相对减小之间的矛盾日益突出,恶劣天气等突发原因引起机场及空域容量的急剧下降,严重影响空中交通的正常运行与飞行安全,导致大面积的航班延误,造成巨大的经济损失。地面等待程序(GDP)就是解决此类问题的有效途径[1]。由于传统的GDP缺乏流量管理部门与航空公司、以及航空公司之间的信息交互,难以有效地分配时隙资源。协同式地面等待程序(CDM GDP)是一种安全高效的机场流量优化管理措施,它是对一般地面等待程序GDP的加强与升级,它通过与协同决策(CDM)技术的融合,发展成增强型地面等待程序(GDP-E),使得地面等待程序分配的时隙更趋向合理化[2]。

国外对时隙分配的研究起源于20世纪90年代,取得了较为显著的理论和应用成果。主要有RBS(ration by schedule)与Compress算法、以及Optiflow优化模型等[3,4,5,6]。其中,RBS算法已在美国流量管理中应用,它是按照“先来先分配”的原则基于最初航班时刻表的时隙分配算法。该算法虽然消除了按预计到达时间分配时隙所产生的“双重惩罚”问题,但没有考虑机型、延误时间与成本关系等对航班延误成本的影响及航空公司延误成本平担的公平性问题。本文在综合考虑上述因素的基础上, 建立了基于延误成本公平分配优化模型,并利用遗传算法对其求解。

1 建 模

1.1 问题描述

CDM GDP时隙分配可描述为:某机场GDP期间由于容量受限产生m个时隙资源,有n架航班等待降落,要求每个时隙只能至多分配给一个航班,每个航班必须配置一个时隙时间比航班计划进场时间晚的时隙。在CDM GDP程序中,时隙的划分主要依据当时机场的容量,例如13:00~14:00期间,某机场容量为6架/h,则创建出10 min为间隔的时隙:13:00、13:10、13:20…。在程序执行时间内不能安排降落的航班依次堆积在此后的时段中,直到所有航班都能降落为止。

由于机型以及各航班的重要程度不同,相同的延误时间会造成不同的延误损失,传统的RBS算法得出的总延误时间最小的分配方法不一定是总延误成本最小的分配方法。Vossen和Ball提出的基于Optiflow的时隙分配优化模型,取得了较好的效果,但是没有很好的解决公平问题。存在以下问题:①每个航空公司的平均延误差距较大;②只考虑了时间上的延误,没有考虑航班延误成本以及各航空公司的平均延误成本。

航空公司最终追求的是成本上的均衡,而不仅仅是延误时间上的平均,延误时间相同机型不同,成本显然不同。因此,本文提出基于延误成本公平分配的时隙分配方法。

1.2 数学模型

对指派模型改进,从航空公司的角度出发,提出基于平均延误成本的到达时隙分配模型,使得各航空公司的延误成本均衡,提高航空公司参与决策的积极性。模型相关参数定义如下:

F为所有航班的集合,f∈F;A为所有航空公司的集合;Fa为a航空公司航班的集合,a∈A;S为所有可用时隙的集合;oagf为航班时刻表中航班f的计划进场时间;ctaf为航班f的控制进场时间;xij为当航班fi取得时隙sj时,xij=1,否则xij=0;gfi(t) 为为航班fi延误时间t所对应的延误成本;目标函数就是在所有的分配方案中,寻求每家航空公司航班所分配的平均延误成本与所有航班平均延误成本差值最小。即

$\min {\displaystyle {\sum }_{a\in A}\left[\frac{{\displaystyle \sum _{f{}_i\in F{}_a}{\displaystyle \sum _{s{}_j\in S}g}}{}_{f{}_i}(t)x{}_{ij}}{|F{}_a|}-\frac{{\displaystyle \sum _{f{}_i\in F{}_a}{\displaystyle \sum _{s{}_j\in S}g}}{}_{f{}_i}(t)x{}_{ij}}{|F|}\right]}(1)$

约束条件:

$\begin{array}{l}{\displaystyle {\sum }_{s{}_j\in S:s{}_j\ge oag{}_{f{}_i}}x}{}_{ij}=1‚f{}_i\in F(2)\\ {\displaystyle {\sum }_{f{}_i\in F}x}{}_{ij}\le 1,s{}_j\in S(3)\\ x{}_{ij}\in \{0,1\}(4)\end{array}$

式中:$\frac{{\displaystyle \sum _{f{}_i\in F{}_a}{\displaystyle \sum _{s{}_j\in S}g}}{}_{f{}_i}(t)x{}_{ij}}{|F{}_a|}$为a公司航班的平均延误成本;$\frac{{\displaystyle \sum _{f{}_i\in F{}_a}{\displaystyle \sum _{s{}_j\in S}g}}{}_{f{}_i}(t)x{}_{ij}}{|F|}$为参加地面等待的所有航班的平均延误成本。

式(2)表明每一个航班都取得一个时隙;式(3)表示每一个时隙最多只能分配给一个航班。

1.3 成本函数

航班延误时间增长,除等待成本外,还会带来更多的成本增加,如转机的乘客将可能错过联程航班需要补偿,机组和飞机则可能耽误下一次飞行任务等。为简化处理,航班延误成本函数可近似表示成分段线性的凸函数 ,航空公司可以根据航班的实际情况,合理选择分界点的数量、位置以及分段斜率。因此,航班延误成本函数gfi(t)可定义为一系列时间区间上的一组线性函数的集合:

$g{}_{f{}_i}(t)=\{\begin{array}{l}w{}_{i}t+b{}_{1}0＜t\le {\rm T}{}_1\\ w{}_{i}t+b{}_2{\rm T}{}_1＜t\le {\rm T}{}_2\\ ⋮\\ w{}_{i}t+b{}_k{\rm T}{}_{k-1}＜t\le {\rm T}{}_k\end{array}(5)$

式中:t=catfi-oagfi为航班fi的延误时间,k为函数的分界点数,wi是由航班fi机型所决定的成本系数。该函数根据航班的延误时间选择不同的函数来计算延误成本。

2 遗传算法求解

上述模型为典型的二次整数规划模型,有很多成熟的软件如Cplex可以求解,但整数规划模型的求解速度往往令人担心,使用该模型运行一个4 h的地面等待问题,将会需要10 min以上的时间,求解时间较长,不能满足实时要求。遗传算法是基于空间搜索的算法,适用于大规模并行计算,因此对本文模型能够很好地解决实时性。算法采用式(6)所示的适应度函数。

$F(f(t))=\{\begin{array}{l}c{}_{\max }-f(t),f(t)＜c{}_{\max }\\ 0,f(t)\ge c{}_{\max }\end{array}(6)$

式中:cmax为f(t)的最大估计值。

2.1 编码策略

通过为GDP期间的每个航班分配时隙,构成染色体个体,如:s1,s2…,sn。染色体基因值sf为航班f分配的时隙,其值在航班f可用的时隙中随机选择产生,而且每个时隙只允许被分配一次。这样得到的编码实际上是时隙集S中n个元素的一种无重复组合排列,如s1,s2,…,sn。种群初始化时,为了易于生成可行的个体,先按照初始计划时间升序排列航班,然后按倒序逐次为每个航班随机选派时隙。

2.2 选择操作

采用基于最优保留策略的排序选择:首先计算种群中的每个个体的适应度,并将个体按其适应度值降序排列。然后根据预先设定的淘汰率,淘汰适应度值较小的个体,并复制相同比例的最优个体(适应度值较大的个体),以保证种群大小不变。

2.3 交叉算子

交叉的目的是使个体基因遗传且使群体具有多样性,但交叉有可能破坏优良个体的负面影响。本文采用单点、大片断基因保留、小片断基因保序的交叉方法[7],该方法不仅能使新个体保留2个父个体的共性,而且尽量保证不破坏父代的优良模式。为了得到可行的个体,再进行约束修正处理。交叉具体操作步骤如下:

步骤1 随机选择交叉点,把父个体1和父个体2各分成2部分。如例中随机选择第3个基因位置为交叉点。

例 父个体1:1 3 2 | 4 6 5 7 8 9; 父个体2:2 3 5 | 7 1 4 6 9 8

步骤2 先将父个体1(或2)中的大片断基因直接遗传给子个体1(或2);再把父个体1(或2)中的小片断基因按照在父个体2(或1)中的顺序重新排列,如果新序列满足约束条件,则组成子个体1(或2)的另一部分基因,否则转至步骤1。

则 子个体1:2 3 1 | 4 6 5 7 8 9; 子个体2:3 2 5 | 7 1 4 6 9 8

2.4 变异算子

为加快算法速度,采用交换基因值的变异方法。具体操作是:在染色体基因串中随机选择2个交换变异点,如果2位置处的时隙均是对应2航班的可用时隙,则交换它们并进行公平性约束修正处理,否则重新选择交换位置。

3 仿 真

结合实际情况,选取广州机场2008年某日16:00~17:00的实际数据。假设由于天气原因,机场接收率由10架/h降为5架/h,因此对地面等待期间的航班执行地面等待程序,于当日16:00开始运行地面等待程序,17:48地面等待结束。有2家航空公司参与了地面等待程序,分别是CAG公司和CES公司,以下分别简称为A、B公司。A、B公司各有5架航班参与本次地面等待。式(6)中,以每延误30 min为一个阶段,则k=4,令b1=50,b2=100,b3=150,b4=200,其中wi则根据国际民航组织(ICAO)的标准,按照飞机的尾流强弱将飞机分为3类进行选取[8,9],如表1所列。

运行遗传算法,遗传操作时,选取种群规模为50,最大世代数为50,选择淘汰率为0.2,交叉率为0.9,变异率为0.2。经计算得到该问题的最优解,本文分配结果和RBS算法结果如表2所列。单个航班成本比较结果及航空公司总成本、平均成本比较结果如图1、2所示。

观察表2可知,两者总延误时间一致均为270 min。成本上,RBS算法总延误成本为14 246元,本文方法的总延误成本为11 748元,减少了近18%。由图1可以看出本文算法有5架航班延误成本明显低于RBS算法结果。A、B航空公司航班共同执行地面等待程序,公平性考虑应能共同分担延误成本。观察图2,RBS算法中,航空公司B的总延误成本远远大于航空公司A,在延误成本分配上显然对航空公司B是不公平的 ,而运行本文算法后航空公司A的总延误成本与航空公司B总延误成本基本相等,成本分配接近均衡;平均成本上两者也趋于平均。通过以上数据,可以看出本文算法不但减少了总延误成本,而且各航空公司能够均衡的分配延误成本,体现了公平性,达到了预期的效果。

4 结束语

本文研究了协同决策机制下机场时隙的公平分配问题,给出了一种基于延误成本公平分配的优化模型,并通过遗传算法进行了仿真验证。仿真结果表明,所提模型不仅能降低总延误成本损失,而且能在航空公司间均摊总延误损失,公平性显著提高。在本文基础上,如果再结合航班取消或替换等航空公司响应信息,可进一步研究CDM GDP时隙再次分配问题。

摘要：研究了CDM GDP机场时隙资源的公平分配问题,提出了基于延误成本公平分配的新的协同地面等待优化模型。给出了航班延误成本的计算方法,将其应用于优化模型中目标函数的计算,并利用遗传算法对模型求解。最后,应用国内某机场的实际数据进行仿真验证,并与RBS算法作了比较。仿真结果表明,所提模型不仅能有效地分配GDP期间的有限时隙,使总延误成本比RBS算法降低了18%,而且使得航空公司间的延误损失得以均衡,显著提高了分配的公平性。

关键词：协同决策,地面延误程序,延误成本,公平性

参考文献

[1]胡明华,徐肖豪.空中交通流量控制的地面保持策略[J].南京航空航天大学学报,1994,26(增刊):26-

[2]周茜,张学军,柳重堪.时隙分配算法在CDMGDP程序中的应用[J].北京航空航天大学学报,2006(9):1043-1045

[3]胡明华.空中交通地面等待问题的网络流规划模型[J].东南大学学报:自然科学版,2000(3):104-108

[4]Vossen T W M,Ball M O.Slot trading opportuni-ties in collaborative ground delay programs[J].Transportation Science,2006(2):29-43

[5]Vossen T S,Ball M.Optimization and mediatedbartering models for ground delay programs[J].Naval Research Logistics,2005(9):75-90

[6]Terrab M.Ground-holding strategies for air trafficcontrol[D].Massachusetts:Massachusetts Insti-tute of Technology,1994:167-185

[7]陶世群,浦保兴.基于遗传算法的多级目标非平衡指派问题求解[J].系统工程理论与实践,2004(8):80-85

[8]徐肖豪,李雄.航班地面等待模型中的延误成本分析与仿真[J].南京航空航天大学学报,2006(2):115-120

机场时隙分配方法研究 篇3

关键词：IEEE 802.16,Mesh,业务区分,时隙分配

1. 引言

IEEE 802.16标准[1]——固定宽带无线接入系统的空中接口,也被称为无线城域网标准。相较于IEEE802.11协议,IEEE 802.16提供一个支持真正无线网络回程的标准,提出了有关于语音、视频、数据的服务质量(Qo S)问题,为区分业务服务提供了基础。OFDM和OFDMA方式是IEEE802.16中最典型的物理层方式,比传统方式具有更高的频谱利用率,可以使得应用IEEE802.16标准的系统在同样的载波带宽下提供更高的传输速率。对于Mesh模式,服务等级的区分和相关策略都没有给出明确的定义。本文对Mesh模式下的MAC层及分布式调度方式进行深入的研究,基于业务区分思想,对比现有的IEEE 802.11和IEEE 802.16 MAC层机制,提出一种基于业务区分的时隙分配和资源预留策略。

2. 基于不同业务类型的资源预留和带宽分配策略

假设节点能够在从上层接收到的数据包识别该业务流的相关性质,根据相应的算法确定其优先级别,且该优先级别是基于其所需资源预留程度。

现假设I为一个整数集,I={0,1,2,3,4,5,6,7},分别表示8种不同类型的业务的priority/class,当节点根据相应算法得出其优先级的等级后,填入priority/class字段中,并将该值赋值给MSH-DSCH_request IE消息中的persistence字段,persistence字段在IEEE 802.16中也是3bits,并且规定了所对应帧的数量,可以将Priority/classs所区分的等级一一对应起来,不同的业务对应不同的demand persistence,从而实现了对业务的区分,流程图如1所示。该流程完成后,根据请求节点发送的MSH-DSCH消息,授权节点判断出该业务要求的数据时隙分布情况,从而分配不同的资源预留和带宽分配策略。

IEEE 802.16 Mesh模式下的带宽分配策略(SMAS)中,请求节点需要在计算下一次发送MSH-DSCH消息后重新竞争控制信道的发送机会,这会导致更大的Xmt_holdoff_exponent的产生,从而不能及时分配到合适的数据时隙;动态数据微时隙分配策略(DMAS)通过将MSH-DSCH-request IE消息中的1Bits的保留字段设定为1或0来区分是否进行动态分配带宽的参数,从而避免了此类问题。但是两者都没有从业务区分的角度考虑调整带宽分配,本文将在这个基础上提出一种基于不同业务类型的资源预留和带宽分配策略。

节点A对业务进行了区分标记,对于业务类型集合,每两种等级的业务对应一种资源预留策略,通过预留不同程度的时隙范围来体现出其优先等级。假设i为业务流对应的带宽分配策略,Ii表示策略i所对应业务带宽策略的集合,当为{1.2.3.}时分别对应不同需求的业务。priority/class字段值和demand persistence字段值是一一对应,demand persistence字段值对应不同的连续帧数,连续帧数越长,每帧中minislot range的要求越小,越容易找到合格的空闲时隙。请求节点在发送请求信息前,需要先查找本节点可用的空闲时隙:对数据帧中256个时隙从头到尾搜索。本文带宽策略的核心思想为在请求节点搜查自己空闲时隙时设定相应的搜索范围,让优先级别高的业务拥有相对宽阔的搜索范围,优先级别低的业务有相对狭窄的搜索范围,给出对应关系如下:

I1:256个数据微时隙全范围搜索,保证了搜索到空闲时隙的最大可能,对应demand persistence为single frame、2frame、4 frame,也就是demand persistence字段值为1、2、3的业务。

I2:256个数据微时隙1/2范围内搜索,规定搜索的时隙号从128到255,对应demand persistence为8 frame、32frame,也就是demand persistence字段值为4、5的业务。

I3:256个数据微时隙1/4范围内搜索,规定搜索的时隙号从192到255,对应demand persistence为128frame,也就是demand persistence字段值为6的业务。

各参数值对应表如下:

所有以上工作都在请求节点完成,请求节点将包含这些信息的MSH-DSCH消息发送,授权节点在收到MSH-DSCH消息后,按正常流程进行时隙对比,决定是否对请求信息时隙授权,完成三次握手机制,建立两节点之间的连接。需要说明的是:在128~255和192~255这两种搜索范围中,剩余的部分就相当于是对优先级别高的业务的预留时隙,保证了高优先级别业务的吞吐量和实时性。

该算法在牺牲了优先级别低的业务的代价下保证了高优先级别业务的效率,应用在特定业务类型的网络中,优先级别的设定可以根据不同的情况来考虑。优先级别设定的标准可以根据其业务本身的特性,如实时和非实时业务,也可以根据用户费用标准来划分业务优先级别。这样就实现了给不同业务预留不同资源,给有必要进行业务区别的业务提供一种解决的方案。

3. 仿真设计

分别把CBR业务分成三个优先等级加以实验:恒定比特率业务CBR,在传输层所对应的业务类型为UDP,无需对数据包的接受与否进行确认。一般代表了包括视频、音频业务,可认为是实时业务的代表,对时延具有敏感性。在一个5*5的格状拓扑中选取相应链路来进行仿真实验,格状拓扑如下:

将CBR流分成三种不同等级的业务(I1,I2,I3),其等级在priority/class字段中进行区分,在三条具有公共节点,且长度均为4跳的链路中分别配置三种等级的CBR业务。

仿真环境设置如下:

所配置的业务得到的CBR吞吐量,在应用区分机制前和区分机制后的结果如图3所示。上方线条代表了应用区分机制后优先级为I1的业务的吞吐量情况,下方线条代表的是CBR业务在未进行业务区分和配置相应的带宽分配策略时的吞吐量情况。可以看出:应用区分机制的后的CBR的吞吐量有了明显的增加,增加的幅度为近2倍。显然,由于其所拥有的最高优先级使得一半以上的带宽为其专有,在剩下的一半带宽中也可与其它两种业务进行竞争。在带宽资源利用饱和的情况下,在一定程度上减少了和次优先等级业务的时隙竞争,所以其分配到合适时隙的机率大大增加。

图4中,上方线条代表了应用区分机制前I1和I2流的吞吐量,由于未进行业务区分,链路中运行的是相同的业务,可以认为它们的吞吐量是相同的,即图3中的下方曲线。中间线条代表了I2业务在应用区分机制后的吞吐量。可以看出:其吞吐量有比较明显的下降,这是由于其空闲时隙搜索范围的减小,相当于变相减小了带宽,且波动较大,在5秒左右的时刻达到一个高点,这可能是由于其较好地争取到了发送opportunity的机会,并在一个没有和高优先级业务发生冲突的地方顺利搜索到了合适的空闲时隙,从而数据得以顺利发送。

而下方线条代表的I3业务,由于其仅仅只有原来四分之一的空闲时隙搜索范围,使得吞吐量大大降低,且波动幅度较之I2业务更为明显。它不仅要受到竞争发送opportunity机会的影响,也要受到前两种业务吞吐量的影响,其空闲时隙搜索成功率较低,也导致产生更多的opportunity机会的竞争,使得其处于更为不利的位置。同时需要注意的是:之前在设定业务类型的时候,是根据其demand_persistence及minislot_range的区分的,优先级越低的业务,其所要求的minislot_range就越小,则即使在一个相对较小的空闲时隙搜索范围内,仍然具有较大可能性找到合格的空隙时隙用于发送数据或者接收数据,这就是其空闲时隙搜索范围在缩小为四分之一后,其吞吐量并没有降到四分之一乃至以下的原因所在。I2类业务也是同样的道理。

图5所示为应用区分机制前后网络的平均吞吐量的对比,可以看出:在应用了区分机制和带宽资源预留策略以后,网络整体的平均吞吐量略有下降,平均吞吐量的略为下降主要的原因可能在于对次优先等级的业务的响应率有所降低,也就是说节点可能会花更多的开销在重复发送同一业务的请求上,使得网络的平均吞吐量有所下降,也是保证实时业务服务质量所付出的代价。

4. 小结

本文基于分布式协调调度机制,提出一种以demand_persistence长度大小区分不同业务的方法,在节点查找发送空闲时隙或接受空闲时隙时,根据不同的优先等级限定其时隙的搜索范围。仿真实验表明,本文提出的区分机制达到了既定目标,对不同优先等级的业务提供了不同的服务策略,保证了网络中重要业务或即时业务的高质量服务,而总体性能也没有因为保证高质量业务而受到大的影响。

参考文献

[1]IEEE Std802.16-2004,IEEE Standard for Local and Metropolitan Area Networks Part16:Air Interface for Fixed Broadband Wireless Access Systems[S].Otc.1,2004.

[2]Hao-Min Lin,Whai-En Chen,Han-Chieh Chao.A Dynamic Min-islot Allocation Scheme Based on IEEE802.16Mesh Mode[C].Future Generation Communication and Networking,2008,288～293.

[3]Min Cao,Wenchao Ma,Qian Zhang,Xiaodong Wang:Analysis of IEEE802.16Mesh mode scheduler performance[J].IEEE Transaction on wireless communication,VoL.6,NO.4,April2007.

[4]汪丽萍,刘富强,王新红,是元吉.IEEE802.16Mesh模式下区分服务时隙调度算法[J].计算机工程与应用,200642-34,105-108.

[5]N Bayer,B Xu,V Rakocevic,J Habermann.Improving the Perfor-mance of the Distributed Scheduler in IEEE802.16Mesh Networks[J].Proc.IEEE VTC,Apr.2007.

浅析TDMA时隙分配算法 篇4

关键词：TDMA,时隙分配,分配模型

在TDMA系统中, 时间被划分成了相互不重叠的时帧, 而时帧又被划分成了相互不重叠的时隙, 网络中各个节点在各个时隙内进行相应的操作。系统采用TDMA接入方式, 从而需要设计如何进行时隙分配, 即如何将时隙分配给网络中的各个节点, 从而使得在相邻节点之间传送分组时产生的冲突较小, 并且系统的吞吐量和空间复用性尽可能高。

1 时隙同步

网络采用TDMA方式接入信道, 首要条件便是网络中各个节点保持时隙同步。时隙同步一般可以分为3类:卫星授时同步方式, 主从同步方式和互同步方式[1]。卫星授时同步方式即是为网络中的每个节点配备能接收授时卫星信号的接收机, 通过卫星传输信号实现全网时间同步。主从同步方式即是网络中存在一个中心节点, 从而让网络中所有节点的时间与中心节点时间保持一致, 而互同步方式即是网络中的各个节点相互发送带有时间信息的数据分组进而调整自己的时钟从而逐步实现整个网络时隙同步。

2 TDMA协议中的时隙分配算法

在全网实现时隙同步之后, 需考虑的便是如何将时隙进行有效分配从而使系统获取较好的性能。研究TDMA协议最主要的是研究其时隙分配算法, 从目前的研究成果来看, 现有的时隙分配算法大致可以分为3类[2]:固定时隙分配算法、动态时隙分配算法和固定与动态相结合的混合时隙分配算法。其中, 根据算法的实现方式, 基于动态分配算法的TDMA协议又可以分为集中式和分布式;分布式动态TDMA协议还可依据时隙分配时是否需要拓扑信息从而再分为拓扑依赖和拓扑透明2种类型。协议分类如图1所示。

基于固定分配算法的TDMA协议将时间分割成时帧后, 每一帧都分成固定数目的时隙, 且每个节点分配的时隙都是唯一且固定的, 网络中的节点根据相应的算法使用时隙。比较有代表性的是启发式时隙分配算法、有序节点染色算法、均域退火算法和基于神经网络的时隙分配算法。

基于动态分配算法的TDMA协议是当节点需要发送数据时才给其分配所需时隙, 数据发送完毕后, 便不再将时隙分配给该节点。

集中式动态TDMA协议一般存在一个获知整个网络节点信息的中心控制节点, 该中心节点为整个网络中的节点进行时隙分配。具有代表性的便是集中式轮询协议[3]。

分布式动态TDMA协议不存在中心在控制节点, 网络中的各个节点通过交互信息对各自的传输时隙进行预留。

基于拓扑透明特性的分布式动态TDMA协议在为节点分配时隙时, 不需要考虑当前的局部网络拓扑信息。其中, 具有代表性的是Chlamtac等提出的扩时多址接入协议 (TSMA, Time Spread Multiple Access) [4]。

基于拓扑依赖特性的分布式动态TDMA协议在分配时隙时则需要考虑网络拓扑信息, 且根据是否需要提前收集领域信息又分为2类: (1) 是各个节点先通过交互控制信息来收集领域信息, 然后再根据收集的领域信息进行时隙分配, 其中比较有代表性的是统一时隙分配协议 (USAP, Unifying Slot Assignment Protocol) [5]和改进型协议USAP-MA (USAP Multiple Access) [6]。 (2) 通过控制包的交互, 直接解决领域内的冲突, 进行时隙预留, 其中具有代表性的是五步预留协议 (FPRP, Five-Phase Reservation Protocol) [7]。

基于混合分配算法的TDMA协议将时隙固定分配给对应的节点, 同时允许在不干扰该时隙使用节点的传输情况下其它节点可以对该时隙进行竞争。比较有代表性的有PTDMA协议、ABROAD协议[8]。

3 时隙分配模型

时隙分配模型是时隙分配算法的重要数学理论依据, 不同的时隙分配方案有着不同的时隙分配模型。以下分别介绍固定时隙分配模型和分布式动态时隙分配模型。

3.1 固定时隙分配模型

在固定时隙分配算法中, 时隙分配的目标是在系统中实现无冲突传输数据, 且时帧长度尽可能短, 信道利用率尽可能高。

设网络中节点数为n, 链路集合为E那么其连接矩阵R可以表示为:

其中,

上式表示如果节点i, j之间都可以直接收到对方发送的报文, 即链路e (i, j) ∈E存在, 则, 否则。

固定时隙分配算法要求每个节点在一个时帧中至少分配一个时隙, 因此设一个时帧由m个时隙组成, 则可以用矩阵S来表示一种时隙分配方案。

用表示节点i的信道利用率, 则整个网络的信道利用率可表示为:

在固定时隙分配算法中, 首先要保证一个节点在一个时帧中需至少分配一个时隙;其次为避免冲突, 间隔小于或等于两跳的邻节点间都必须分配不同的时隙。固定时隙分配算法的目标即是用最短的帧长度实现最高的信道利用率。

因此, 固定时隙分配问题模型为:

3.2 分布式动态时隙分配模型

在分布式动态时隙分配中, 单个节点无法获取整个系统节点信息, 因此在进行时隙分配时需要根据自身业务要求, 动态地进行时隙分配, 使得自身节点对其它节点的影响的最小, 同时使得节点业务传输性能最大。

设网络中需为节点i分配个时隙, 网络中节点总数为n, 一个时帧由m个时隙组成, 每个时隙的长度为τ, 同理可用矩阵S来表示一种时隙分配方案。

在进行时隙分配时, 如果给节点i和其它节点分配了相同的时隙, 则发生了时隙冲突。因此节点i在此次时隙分配中的时隙冲突概率可以表示为:

其中:

节点i的信道利用率表示为:

节点i的平均报文时延为:

在分布式动态时隙分配算法中, 只需保证对节点i分配的时隙数量至少满足其需求, 但目标即是要使冲突概率和时延最小, 同时使得信道利用率最高。

因此, 分布式动态时隙分配问题模型为:

4 结语

研究TDMA协议, 最主要的便是对其时隙分配算法进行研究。本文从内涵、现状、理论支撑上对TDMA时隙分配算法进行一定的分析、归纳和总结, 从而能使研究人员纵览该领域内的研究情况, 为其进一步深入研究打下重要基础。

参考文献

[1]董超, 田畅, 倪明放.Ad hoc网络时钟同步研究[J].通信学报, 2006 (9) .

[2]聂建耀, 许勇, 张金娟, 等.一种应用于Ad Hoc网络的改进型TDMA动态时隙分配算法[J].移动通信, 2008 (22) .

[3]曾勇, 黄巍, 杨静, 等.运用动态优先级轮询机制的数据链仿真[J].电子科技大学学报, 2008 (2) .

[4]Chlamtac I, Farago A.Making Transmission Schedules Immune to Topology Changes in Multihop Packet Radio Networks[J].IEEE/ACM Transactions on Networking, 1994 (1) .

[5]Young C D.USAP:A Unifying Dynamic Distributed Multichannel TDMA Slot Assingment Protocol[C].IEEE Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies, San Francisco, CA, USA, 1998.

[6]Young C D.USAP Multiple Access:Dynamic Resource Allocation for Mobile Multihop Multichannel Wireless Networking[C].IEEE Military Communications Conference, 1999.

[7]Zhu chenxi, Corson M S.A Five-Phase Reservation Protocol (FPRP) for Mobile Ad hoc networks[C].Wireless Networks, 2001

机场时隙分配方法研究 篇5

在高技术战争中,作为高效的数据交互渠道——数据链,往往需要具备高实时性、高动态性和强自组织性。基于自组织时分多址技术的数据链[1],迎合了当前战场需求,因此,成为了当前的一个研究热点。

时分多址数据链的时隙分配通常有3种方式:争抢、固定和预约。争抢的时隙分配方法易产生冲突,当用户规模较大时,系统因抢占冲突而造成通信延时甚至通信失败。而固定分配方式不适合高动态性、高强实时性的情况,因此,人们对于STDMA的时隙分配算法进行了深入的研究:张昱晖等人提出了将固定分配和预约分配相结合的复合式STDMA模型,能够较好地适应网络的不同规模和高动态性,但未能考虑不同平台和不同情况对时隙分配需求;杨恩等人提出了一种动态可变帧长的STDMA算法[2],算法具备良好的实时性和可扩展性,但对帧结构的设计考虑不周;王塬琨等人提出了基于优先级的动态时隙分配方法[3],算法的帧结构采用预约请求时隙和数据时隙相结合的方法,按优先级进行排队,考虑到了不同优先级用户时隙需求相异性,但对紧急特情的时隙分配考虑不周。

该文立足于空空数据链的高动态性和强实时性,针对不同级别和不同情况对时隙需求和发送优先级需求的不同进行综合分析,提出了一种改进的动态自组织时隙分配模型。

1 典型动态时隙分配模型

1.1 模型帧结构

典型的动态时隙分配模型是基于优先级的。模型帧结构分为预约请求时隙和数据时隙两段,预约请求时隙又分为n个微时隙,n的取值与网内节点数相等,也就是每个节点占用一个微时隙。微时隙的主要作用是用于广播发送各节点的预约请求,微时隙的长度小于数据时隙的长度,节点对微时隙的占用采用固定分配的模式。网中节点根据优先级的不同来预约申请数据时隙,之后产生一个请求时隙列表。对数据时隙的分配处理将依据相应的算法和优先级处理机制进行。模型帧结构如图1所示。

1.2 模型的算法及优先级处理机制

1.2.1 算法简介

在形成请求时隙列表后,按业务的优先级进行排序并计算需要的总数据时隙数,如果请求的数据时隙数量少于一帧中数据时隙的数量,算法根据数据包的优先级对所有申请的数据时隙进行分配,并形成完整的时隙分配表后广播给各个节点,发送的原则是优先级高的数据先发送,低的后发送。

1.2.2 优先级处理机制

该模型的优先级设计采用严格优先级排队和优先级动态提升相结合的原则。严格优先级排队对申请进行处理的时候将严格按照优先级顺序进行数据时隙的分配,体现了效率至上的原则,但缺陷是当高优先级总是占满数据时隙时,低优先级的业务将一直申请不到时隙,为解决这一问题,算法将所有的业务分为1~4的优先级,1最高,4最低。如果低优先级的请求等待时间超过预定的时间长度或者连续请求2次没有分配到数据时隙,该预约请求将在下一帧重发,但是优先级自动减1,也就是增加一级优先,依次可以一直提高至最高级。

2 改进的动态时隙分配模型

2.1 空空数据链应用场景分析

2.1.1 时隙需求分析

在空中各种武器平台中,不同作战平台对时隙的需求就很不一样。通常战斗机和负责精确打击的导弹,这些成员数量多,但发射信息较少,每个成员要占用的时隙数就较少,每时帧内只占用几个或几十个时隙,如执行远程拦截任务的战斗机,只需要用1个时隙来发射其位置和状态信息;而当战斗机执行巡逻和警戒任务时,因要上报所探测到的战场实时情况,因而需求的时隙稍多,但往往32~100时隙就已足够;有些空中平台是执行侦察、监视和预警等任务,这类成员数量少,但发射信息频繁,信息内容亦偏多,因而要占用的时隙数就较多。比如1架E-2C飞机要完成空中预警任务,需要占用的时隙多达上千个;而有些平台需求的更多,他们除了担负监视、预警和侦察任务外,还负责对其他作战平台的指挥、引导与控制,是整个空中战场乃至空地、空海一体战战场的指挥中心,比如E-3“望楼”空中指挥预警机,E-8“联合星”监视机往往需要占用网内总时隙的7%~10%,约6 000~9 000多个时隙。

2.1.2 优先级需求分析

依据不同战场情况,不同作战任务需求,各类空中平台除了对时隙多寡需求不同外,对信息发送的先后也有着不同的需求。通常,指控中心把握着整个战场态势,负责战场的统筹调度,指挥引导,总是需要优先保证发送机会;而负责战术侦察的各种侦察机乃至卫星侦察设备、战场巡逻机等由于其担负着国土警戒、对敌实时侦察以及预警等任务,因而需要给予较高的优先级以保证发现的情况能实时地上报指挥中心;而各种战斗机、运输机、轰炸机以及战术导弹等因其多数时刻处于接收指令和信息的状态,需要发送上报的信息量少,而且往往实时性要求也并不高,因此,其对发送优先级一般可以考虑设为最低级。于是,在通常情况下,可以设定优先级为3级,但是战场往往是不可测的,紧急需求时有发生,而且往往不因作战平台的不同而有差别。因而,需要设定一个最高的优先级别来保证紧急特情的时隙分配,并保证最优先发送。

2.2 帧结构设计

基于典型的帧结构,考虑到时隙和优先级需求的相异性,新模型的帧结构也分为预约请求时隙和数据时隙两大阶段,但为了提高效率,注重紧急特情;同时兼顾公平,相比原有的帧结构,新帧结构中,预约请求时隙中微时隙的数量设定将大于网络中的现有节点数,考虑到充分利用帧内时隙数又能方便新节点的入网,具体数值不同单位可以自行设定,通常以设定比现有网内节点多出一半的微时隙数。亦即若网内节点数为n,则设定预约请求时隙内的微时隙数为:k=[1.5n],其中,[]为取整的意思。而将数据时隙依时序再次划分为最高优先级数据时隙、定长分配数据时隙和一般优先级数据时隙,帧结构设计如图2所示。

初始化整个网络时,系统将为每个网内的节点分配一个相应的微时隙和设定定长分配的时隙阈值w。微时隙将包括预约请求的时隙数、节点ID和相应的优先级标识,申请完成后,根据业务优先级和请求的时隙数生成一个请求时隙列表。时隙阈值按网络整体情况设定,通常取最低优先级节点占用时隙的平均值。

预约请求阶段时隙数是固定的,而数据时隙阶段的3个分阶段时隙数均不固定,依具体的分配情况而定。

2.3 用户优先级设计

依据2.1节场景分析的结论,优先级设定为系统默认和临机决断相结合的形式,分为了4级3大组。4级为:最高级、1级、2级和3级;3大组为:最高级和1级;最高级和2级;最高级和3级。其中1、2、3级依据优先级需求情况待初始设定之后系统默认,并将之制成控制面板交由机上人员操控。比如,在预警指挥机上,可以设定最高级和1级的优先级控制面板,无紧急发送需求时,优先级选择开关放在默认档,即1级,这样,该节点业务的预约请求优先级标识就为1级;操控人员有紧急发送需求时,由其将优先级档打到最高级,此时优先级标识就改为最高级,数据将会优先发送。再如,一般的战斗机上设定的都将是最高级和3级,若遇紧急情况,飞行员能够临机决断,将数据的优先级设为最高级,以利于数据的及时上传。

2.4 时隙分配算法

在新模型的帧结构中,数据时隙阶段分为3大块,下面分段给出算法设计。

(1)最高优先级分配阶段

从请求时隙列表内提取出最高优先级的请求时隙数和相应的节点ID,依时序给相应各节点分配时隙以供紧急发送的完成。同时确定定长分配阶段的开始时隙。

(2)定长分配阶段

最高优先级时隙分配完成后,就进入定长分配阶段。首先从时隙分配列表里面选出预约的时隙数小于时隙阈值w的节点,然后将这些节点统一依时序分配w个时隙用于数据发送。最后进入一般优先级发送阶段。

(3)一般优先级分配阶段

此一阶段就将完成剩余预约业务的发送。在此阶段,该文提出将优先级与时隙多寡结合,优先级高的节点先发送;同一优先级,预约的时隙数多的节点业务先发送。这样就完成了整个的数据时隙分配和发送。

3 新模型性能分析

3.1 入网便捷性

新模型在预约申请阶段的微时隙留有一定的冗余,新入网的节点只需在侦听一帧的时间后,在空闲的预约微时隙提请时隙申请就能够立即入网,而不需要对整个网络进行重新规划和初始化的配置。

3.2 公平性

新模型考虑到优先级低的节点易长时间申请不到数据时隙的情况,将一些时隙需求很小的节点业务置于紧急发送时间段之后,在对整体网络的实时性影响不大的情况下,兼顾低优先级节点的小业务,使网络更合理、公平及有效。而且该设计相较于原模型的算法更为简洁,降低了算法设计的复杂度。

3.3 对紧急特情的独特处置

新模型最大的特点在于对紧急特情的优先处置。结合空中战场的实际情况,给予了紧急特情数据发送最优先的安排。这种设计保证了对高实时性的战场态势的精准把握和对紧急特情的及时预警,将给予指挥员更多的时间来指挥战斗。

4 结束语

综上所述,通过初步的性能分析,该文提出的改进的时态时隙分配的新模型及算法较好地解决了新节点的入网、紧急数据的发送以及不同平台对数据时隙和发送时刻需求不同等问题,具备高的实时性和自组织性,比较适合空空战场环境。

参考文献

[1]张军,张其善,邓秋林.S-TDMA数据链系统时隙预约选择算法分析[J].北京航空航天大学学报,2001,27(5):514-517.

[2]杨恩,张有光,唐积强.数据链时隙分配算法设计与仿真[J].通信技术,2010,43(7):124-130.

机场时隙分配方法研究 篇6

1 模型假设

假设信道为瑞利信道, 网络中每个节点发送数据的ACK应答都可以被其他节点接收到 (ACK信息的数据量很小, 可以采用冗余更大的信道编码, 增加其抗干扰、衰减的能力, 而增加的开销很小) 。每个接收机可以估计每个链路的信噪比, 而且该信噪比在一个时隙内保持不变。每个节点只有一根天线, 每个节点对收到的数据按最大比合并的方式处理。

2 协作重传的动态TDMA

2.1 数据帧设计

如图1所示, 本文采用了类似文献[8]的帧结构, 整个时隙分为预约和数据传输两个阶段。

数据传输部分为各个节点分配了固定的用于数据传输的时隙。每个节点的时隙又分为本节点的数据发送部分和数据接收节点的应答部分ACK。每个节点在不传输信息时, 侦听其他节点发送的数据是否得到了数据接收节点的应答ACK。如果侦听到ACK, 则认为该节点的数据传输是成功的;否则认为该节点的数据传输是失败的, 需要重新传输。当噪声的功率一定时, 发送失败的数据多是受到了瑞利衰落和通信距离大而导致衰减过大的影响, 因此可以采用协作通信的方式, 降低该影响。预约时隙又分为多个子时隙, 这些子时隙用来交换协作通信所需要的信息, 并动态地分配协作通信的时隙。在动态分配协作通信阶段, 如果某节点没有新数据包产生, 在当前数据帧中该节点相应的时隙时, 协作转发上一帧中其他节点传输失败的数据包, 该策略避免了文献[3]中空闲时隙不足导致传输速率降低的缺点。

2.2 传输失败的计算公式

如图2所示, 假设在第n帧中节点A发送数据包Di给节点C, B, D, E和F为邻居节点。当A向C发送数据Di时, 如果不通过协作直接传输成功, 则认为第一次传输即成功。当第一次没有成功时, 在下一帧中再次传输Di。如果有其他节点愿意帮助A协作重新传输Di, 例如节点B, 则A和B将在各自的数据传输时隙向C传输Di。C在这两个时隙将接收到的Di按最大比合并, 如果译码失败, 则需要在下一时隙继续协作重传。如果Di在需要协作重传时没有其他节点愿意协作传输, 则A单独传输, 如果仍未传输成功, 将继续在下一帧中重新协作或单独传输, 直至成功传输。

当采用BPSK调制时, 节点A发送数据s, 节点C接收的信号可以表示为

则直接传输数据s时, 节点C处的信噪比为

式中:hAC为A和C之间的信道衰减系数, n为高斯白噪声, 满足n~CN (0, N0) 。假设节点之间没有直射波, 所以信道为瑞利信道, hAC~CN (0, kdAC-α) 。k为和信道有关的常数, dAC为A和C之间的距离, α为路径损耗系数。同理, 节点B发送给节点C的信号可以表示为

根据文献[9], 可以得到A和B分别发送的数据在C处按最大比合并 (MRC) 后, 信噪比为

当采用BPSK的调制方式时, 根据文献[9]可以得到A、B组成的天线阵列的平均误码率为

式中:为平均信噪比;m为空间分集数量。如果采用了信道编码, 信道编码的增益为g, 单位是d B, 则采用了信道编码后的平均误码率为

其中

当m=1时, 数据包的长度为N, 当采用了信道编码后, 可以根据式 (5) 计算直接传输, 即第一次传输数据的失败概率为

当m=2时, 表示两个节点协作重传, 一个数据包被协作重传的失败概率为

2.3 协作重新传输策略

如图3所示, 如果A单独发送Di给C失败, 而其没有其他节点正确接收Di, 则A在其下个时隙再次直接重传。如果A单独发送Di给C失败, 并且存在邻居节点B成功接收Di, 则B节点有义务在n+1帧中协作转发Di给C, 前提是在n+1帧的预约阶段B没有本节点的数据需要发送。该协作方式相当于文献[6]中的译码-转发模式。若协作重传不成功, 则A和B在下个时隙中依然协作重传, 直至传输成功才会传输其他数据包。

图4表示的是节点B决定是否协作重传A传输的失败数据包的流程图。假设A节点在第n帧传输数据包Di失败。如图1所示, 预约阶段为每个节点分配了一个子时隙, 如果B在n+1帧的预约阶段没有本节点的数据需要发送, 而且B计算其协作重传的失败率小于A单独重传的一半时, B在其相应的预约子时隙内广播B协作重传A数据包的意愿。A、B节点在第n+1帧中相应的数据传输时隙发送Di。

当B节点子时隙之前的时隙, 已经有其他的节点宣布协作转发Di时, B在本时隙放弃转发Di。如果还有其他节点在第n帧发送数据失败, 例如数据包M, 而且在之前的时隙内没有节点表示愿意协作传输M, B节点会在其第n+1帧的预约阶段子时隙广播协作转发M的意愿。

协作重传的机制可以提高重传成功的概率, 但是为了实现预约协作重传的机制, 在时隙帧的数据传输部分前面增加了预约阶段, 占用了信道资源。每个节点在预约阶段都拥有一个子时隙, 用于广播其协作传输其他节点数据的意愿, 在本文中该子时隙的长度为100 bit。每个数据包的长度为1 024 bit。与图5所示的传统TDMA帧结构相比, CD-TDMA有以下两个特点:

1) 预约阶段占用的时间相当于一个数据子时隙, 对信道的占用降低了数据传输的速率;

2) 提高了重新传输错误数据的概率, 相当于提高了数据传输速率。

CD-TDMA由于比传统的TDMA多了预约阶段, 所以在相同的时间内, CD-TDMA的帧数要比TDMA少, 这意味着数据传输的机会要少。但是, 每个节点在单位时间内产生数据包的概率是相同的, 即在相同时间内产生的数据量基本相同。所以CD-TDMA重新传输数据的机会要比TDMA少, 但是由于CD-TDMA采用协作重传, 重传数据的成功率大大增加, 所以在相同的时间内CD-TDMA传输的数据比传统的TDMA要多。本文第3节将用仿真结果对以上推论进行验证。

3 性能仿真及分析

仿真区域为1 km×1 km的正方形平面, 在该区域内随机分布n个通信节点, 通信速率为200 kbit/s, 仿真时间为10 min。ACK的时间为0.5 ms, 则CD-TDMA和TDM A的数据传输时隙部分, 每个节点被分配了1 kbit/ (200 kbit/s) +0.5 ms=5.5 ms。为了比较CD-TDMA和TDMA的吞吐量性能, 在运行10 min时统计此时各个节点数据缓存区还未发送的数据包之和, 以及在10 min内产生的所有数据包数。未发送的数据包总数与已经产生的所有数据包总数之比可以衡量两种协议的吞吐量性能。当仿真时间达到10 min时, 两种协议产生的数据包总数是基本一致的 (差异小于0.1%) , 此时该比值可以反映两种协议的吞吐量性能。

图6和图7中, δ表示一个节点数据在发送时隙的时间长度内产生数据包的概率, 即在5.5 ms的时间长度内产生一个数据包的概率。由于CD-TDMA和TDMA的仿真时间相同, δ也相同, 所以产生的数据包总量是基本一致的。由图6可以看出, 当δ=0.06时, 无论是CD-TDMA还是TDMA, 因为信噪比增加而导致传输失败的概率降低, 其未发送出的数据包的比例随着信噪比的增加而降低;无论当节点数n=10还是n=15, 未发送数据包的比例基本一致。从图6中还可以看出本文提出的CD-TDMA的性能明显优于传统的TDMA。图7中δ=0.05, 可以得到与图6类似的结论, 证明当δ发生变化时, CD-TDMA协议的性能依然优于传统的TDMA。

图8中描述的是当信噪比为18 d B, 节点数n=10时, 未发送的数据包占总产生数据包比例随δ的变化曲线。从图8可以看出, 随着δ的增加, CD-TDMA和TDMA未发送的数据包显著增加, 这是因为当δ增加时, 产生的数量增加, 未发送的数据比例自然增加。无论δ如何变化, CD-TDMA未发送数据的概率都比传统的TMDA要小, 证明了CD-TDMA协议可以有效地利用协作提高网络的吞吐量。

4 结论

本文提出的动态分配时隙的CD-TDMA算法, 通过协作传输曾经传输失败的数据包, 提高了数据包的传输概率。仿真结果证明了CD-TDMA可以在不同的数据产生速率下, 比传统的TDMA协议有更高的数据传输速率。本文提出的CD-TDMA假设所有的节点都可以直接通信, 在以后的工作中, 需要研究在多跳通信的情况下, CD-TDMA协议的具体性能。

摘要：协作通信可以有效地降低衰落信道中数据传输的中断概率, 从而提高数据的传输速率。但是在TDMA系统中采用协作通信必然引入额外的带宽开销, 为了提高传输速率而采用协作通信, 是否能克服因此而产生的不利因素并不明确。在提出的CD-TDMA时隙算法中, 在传统TDMA帧的前部增加了一个侦听和动态分配时隙的预约阶段。所有节点在每个数据帧的开始如果没有新产生的数据, 则有义务协作转发其他节点在上个时隙帧中发送失败的数据。该算法提高了数据重传的成功概率, 提高了整个网络的吞吐量。仿真结果表明, 尽管该算法引入了额外的时隙开销, 和传统的TDMA接入方式相比, 该算法可以有效地提高整个网络的吞吐量。

关键词：无线网络,时分复用,协作,动态时隙分配

参考文献

[1]LANEMAN J N, WORNELL G W, TSE D N C.Cooperative diversity in wireless networks:efficient protocols and outage behavior[J].IEEE Trans.Information Theory, 2004, 50 (12) :3062-3080.

[2]NOSRATINIA A, HUNTER T E, HEDAYAT A.Cooperative communication in wireless networks[J].IEEE Communication Magazine, 2004, 42 (10) :74-80.

[3]王翠, 唐加山.协作通信技术在恶劣信道条件下的应用研究[J].电视技术, 2013, 37 (13) :101-104.

[4]SADEK A K, LIU K J R, EPHREMIDES A.Collaborative multiple-access protocols for wireless networks[C]//Proc.IEEE ICC’06.Istanbul:IEEE Press, 2006:4495-4500.

[5]JIAO H Z, LI F Y.A mini-slot-based cooperative MAC protocol for wireless mesh networks[C]//Proc.IEEE Global Communicaitons Workshops.Miami:IEEE Press, 2010:89-93.

[6]YANG Zhuo, YAO Yudong, LI Xiaochen, et al.A TDMA-based MAC protocol with cooperative diversity[J].IEEE Comm.Letters, 2010, 14 (6) :542-544.

[7]JIAN Z, KUHN M, WITTNEBEN A, et al.Cooperative transmission schemes for decode-and-forward relaying[C]//Proc.IEEE 18th International Symposium on Personal, Indoor and Mobile radio Communications.Athens:IEEE Press, 2007:1-5.

[8]LEE J K, LEE K M, LIM J S.Distributed dynamic slot assignment scheme for fast broadcast transmission in tactical ad hoc networks[C]//Proc.IEEE MILCOM.Orlando:IEEE Press, 2012:1-6.