固定时隙分配论文（精选7篇）
固定时隙分配论文 篇1
战术数据链 (Tactical Data Link, TDL) 是汇集通信、导航和识别的综合化战场信息系统, 可在不同的指控平台与武器平台之间交换监视和控制信息, 为各平台提供多重接入、高性能、抗干扰的数据和保密话音通信、导航和识别信息[1]。在复杂多变的作战领域, 战场态势快速变化, 时延的重要性不言而喻。战术信息的时延抖动同样重要。文献[2]指出, 时延直接反映了数据从发布者 (信息源) 到订阅者 (接收端) 的通信代价, (时延) 抖动则反映通信的最坏情况。抖动越大, 说明通信网络越不稳定。对于图像、音频和视频等多媒体业务, 抖动的影响更为突出。实际测量发现, 抖动大于80ms是不可接受的。如高速运动的战斗机通常需要话音来进行实时交换战场信息和实施战术战法, 以实现协同作战, 过大的抖动会产生不够连续平缓的话音, 最坏情况会导致话音无法为人所辨识, 失去话音通信的意义。文献[3]提到, 预警机发送目标机监视信息的抖动如果大于时延的10%, 地面站将如无法将目标机位置坐标精确到100m以下, 这将为指挥员预测敌方意图或实行远程精确打击带来困难。再者, 无人机实时传输的目标区域监视视频, 也有可能由于信息传输的抖动过大, 接收端无法正常实时播放该视频或无法产生为人所能观看的平滑视频。因此, 时延抖动是战术数据链性能中不可忽视因素。
1 相关研究
TDMA战术数据链网络中, 通信信道是以时隙来表征的。时隙分配, 就是将时隙这一有限的时间资源按照一定算法 (固定、预约、竞争、动态等) , 指派给战术数据链各用户的过程。现有的TDMA时隙分配方面的算法, 大多数主要考虑减少战术信息传输的时延, 根据通信需求给用户分配适当数量的时隙。算法[4]认为每一个节点在一个TDMA周期内至少发送一次消息报文。它们都利用基于图论的着色算法, 去除两跳范围内邻居的冲突, 或者获得最大时隙利用率, 或者最小化TDMA周期长度, 或者是最小化能量消耗等。但为了降低其时延抖动, 需要实现均匀间隔的时隙分配, 即分配到一个用户的相邻两个时隙之间的间隔数相对固定。文献[5]、文献[7]指出, 研究最小抖动的人很少。有些通过增加消息报文缓冲池长度来降低抖动, 但这样带来的时延是要求很高实时性的战术数据链所不能接受的。文献[8]、文献[9]通过协议的修改动态分配实现最小时隙, 这不太适合于已装备并使用中的战术数据链。文献[6]、文献[10]提出的最大相邻时隙间隔约束的分配算法。但在实际战术使用中, 很难根据某个战术需求给出特定的时隙间隔约束, 不超过这个间隔消息报文接收端就可以接受。这个阈值很难给出, 但由于约束条件无法给出, 不能实用于战术数据链。
而TDMA战术数据链自身采用二叉树法实现时隙的固定分配。文献[11]指出, 虽然二叉树能保证同一块中的时隙间隔非常均匀, 但它无法保证不同块内的均匀性, 且块分解得越小, 则不同块中时隙所组成的时隙块均匀性越差。于是提出一种二叉树块内均分法, 定义时隙块间间隔
其中, Code1和Code2分别表示两个节点块的编码, Value (Code) 表示将二进制字符串编码Code转换成10进制的数值。该时隙块选择准则, 以块间间隔BI越大越好, 可以实现良好的时隙间隔均匀性, 但时隙块间间隔计算方法比较繁杂, 实现起来比较困难。
2 最小时延抖动的固定时隙分配算法
在TDMA战术数据链中, 既需要考虑时隙块内相邻分配时隙的间隔, 还要考虑时隙块间相邻时隙的间隔, 因此不能简单转化为点对点路径问题, 而是从某个点出发, 重新回来该点的闭合环问题。换句话来说, 就是将TDMA战术数据链时隙均匀分配问题, 转化为图论中包含确定边数的不含回路的最短路径环问题。
2.1 问题的数学描述
对于一个周期N的时帧T, T={T1, T2, …, TN}, 其中包含有m个空闲时隙S, S={S1, S2, …, Sm}, 需要在S中指定k个时隙M, M={M1, M2, …, Mk}, 用于分配给当前网络成员。此时, A=N/k为最理想的相邻时隙间隔。记D={D1, D2, …, Dk}为所要分配的时隙块相邻时隙之间时隙间隔的序列。记location (Mi) (i=1, 2, …, k) 为时隙Mi在整个时隙块T中的位置, 即Mi是T中第location (Mi) 个时隙。则Di=location (Mi+1) -location (Mi) , 即时隙Mi与其后续一个时隙的间隔。如果D1=D2=…=Dk=A, 表明分配的时隙是完全均匀的, 抖动最小, 为0。在实际中, 由于有S的存在以及D为正整数, 不能保证达到这种均匀程度。故希望找到一个最优的时隙分配方案, 能使Di尽可能接近A.那么, 求最小时延抖动的时隙均匀分配的数学模型可表示为单目标多约束规划问题:
目标:
约束:
2.2 算法的符号说明
定义一个有向图G= (V, E) , 其中V是包含m个节点的节点集合, E是边的集合。每一个节点vi表示S中的第i个空闲时隙。每一个有向边ei, j表示从节点vi到vj的边 (i≠j) 。
边的权重w (ei, j) 定义如下:
(1) 当location (i) <location (j) , w (ei, j) =[location (j) -location (i) -A]2/A, 表示如果空闲时隙Mi和Mj被选择作为相邻时隙分配出去, 则这两个相邻节点的间隔tj-ti将对最终的抖动产生一个[location (j) -location (i) -A]2/A的影响。
(2) 当location (i) >location (j) , w (ei, j) =[location (j) +M-location (i) -A]2/A, 表示如果空闲时隙ti和tj被选择作为相邻时隙分配出去, 则这两个相邻节点的间隔tj-ti将对最终的抖动产生一个[location (j) +M-location (i) -A]2/A的影响。
由此, 求最小时延抖动的时隙均匀分配问题就转化成求图论中求包含确定边数的不含回路的最短路径环问题。
2.3 算法的实现步骤
本文采用动态规划法求解。
(1) 定义m×m的矩阵Π (n) , 矩阵中每一个元素π (n) i, j为从vi到vj的包含n条边的最短路径的权重。
(2) 对于矩阵Π (1) , 由2.2节的有向图G= (V, E) 有
(3) 由于一条从vi到vj包含k个跳的路径, 总是由一条从vi到vq包含k-1跳的路径加上从vq到vj权重为vq, j的边而组成。因此, 对于矩阵Π (n) , n∈ (2, k], 有π (n) i, j=min (πk-1i, q+w (vq, j) ) 。为了保证不包含重复节点和回路, 有i<q<j.同时通过矩阵P (n) 记录经过的节点vq.
(4) 显然最小的对角线元素π (n+1) ii就是从vi开始回到vi的包含n+1条边的不含回路的最短路径环。
归纳起来, 就是根据有向图G= (V, E) 构造矩阵Π (1) ;再通过步骤 (3) 逐步推进计算矩阵Π (2) 、Π (3) 、…、Π (k-1) , 最终得到矩阵Π (k) ;而步骤 (4) 指出矩阵Π (k) 的对角线元素π (k) ii就是从vi开始回到vi的包含k条边的不含回路的最短路径环, 只要选择最小的对角线元素π (k) ii即为要找的最短路径环的起点;剩下的只需倒退回去通过矩阵P (n) 找出该最短路径环所经过的节点即可。
3 计算案例
现在再看图1的例子, 一个长度N=16的时帧中有m=5个空闲时隙{3, 5, 9, 12, 13}, 需要分配k=4个时隙给某个网络成员。根据其5个空闲时隙定义有向图G= (V, E) 的五个节点, 节点3、5、9、13和15分别对应节点v1、v2、v3、v4和v5, 如图1所示。
此时理想相邻时隙间隔A=N/k=16/4=4。由此可以根据2.2节来计算有向图G= (V, E) 各边的权重, 结果如图2和表1所示。
值得注意的是, 本文为了显示清楚, 并没有在图中标出边的方向以及边的权重值。其实图中每一条边都代表着两条有向边, 如节点v1和节点v2存在着两条边, 分别为e1, 2和e2, 1;每条有向边存在一个权重值, 分别为w1, 2和w2, 1.
然后根据2.3节步骤 (2) 构造矩阵Π (1) , 可得:
再按照2.3节步骤 (3) 逐步计算矩阵Π (2) 、Π (3) 和Π (4) :
由矩阵Π (4) 得知, 分别从节点v1和v2开始出发形成的环的最短路径均为2, 都为包含4跳的最短路径环。以从节点v2出发的环为例, 查看矩阵P (4) 中对应元素p
4 仿真验证
在仿真环境中, 通过随机方式生成长度为N的时帧 (即一个周期包含N个时隙) , 其中有m个空闲时隙, 需要分配k个时隙给某个网络功能模块/网络节点。在仿真实验中取N=128。
在仿真实验中主要考虑两个技术指标。一个是成功概率, 指的是成功指定k个时隙的仿真实验次数与总仿真实验次数的比值。这主要是针对TDMA战术数据链自身的二叉树分配技术, 因为该二叉树分配技术存在一定局限性, 并不能保证每次都能找到符合条件的时隙分配方案;而对于本节提出的时隙均匀分配技术, 则不存在问题, 它总能找到一个合适的时隙分配方案。另一个是指定的k个时隙的均匀度, 指的是2.1节定义的σ, 这主要是针对本节提出的时隙均匀分配技术, 表示其能找到的时隙分配方案的均匀程度;而对于TDMA战术数据链自身的二叉树分配技术, 只要能成功分配, 所得的时隙分配方案必然是均匀的, σ=0。
设计两类仿真实验:一类是空闲时隙数量m固定为100, 需分配时隙数量k从2开始按步长翻倍增加到64 (即2, 4, 8, 16, 32, 64) ;另一类是需分配时隙数量k固定为4, 空闲时隙数量m从30按步长增加到100 (即30, 40, 50, 60, 70, 80, 90) 。对每一个空闲时隙数量/需分配时隙数量组合 (m, k) , 随机生成1000个时隙空闲状况 (指的是N=128个时隙中m个空闲时隙的具体序号) , 对每一个状况进行仿真实验, 统计其成功概率和均匀度。对每个 (m, k) 得到100组数据, 求其平均值, 作为其实验数据, 分别如图3、图4、图5、图6所示。
从图3和图4看出, TDMA战术数据链的二叉树时隙分配技术在实际应用中存在不足, 随着需分配时隙数量k的增加或空闲时隙数量m的减少, 能成功把时隙分配出去的成功概率迅速减少。如图3, 在总计N=128个时隙的时帧中, 有m=100个空闲时隙, 需分配时隙数量k达到8个, 成功分配概率约为20%, 当需要分配超过32个时隙, 该时隙分配技术的成功分配概率为0。如图4, 需分配时隙数量仅仅为k=4个, 如果要想保证成功分配概率超过25%, 那么至少需要预留m=80个空闲时隙数量。这是由于空闲时隙的不规整性而引起的:空闲时隙数量m一定, 需分配时隙数量k越多, 越是难以找到相邻时隙间隔刚好为A=N/k的k个空闲时隙;需分配时隙数量k一定, 空闲时隙数量m越多, 越是容易找到相邻时隙间隔刚好为A=N/k的k个空闲时隙。
从图5和图6看出, 按照本节提出的时隙均匀分配技术来分配时隙, 分配的时隙均匀度随着需分配时隙数量k的增加以及空闲时隙m的减少而增加。如图5, 在总计N=128个时隙的时帧中, 有m=100个空闲时隙, 需分配时隙数量k达到32个, 最差的时隙分配均匀度σ=3;当需要分配为64个时隙, 最差的时隙分配均匀度σ不过也只有23。如图6, 需要分配时隙数量k=4, 空闲时隙数量m=30, 最差的时隙分配均匀度σ不过也只有0.8;当空闲时隙数量m超过70, 那么σ=0, 即是说, 已经可以保证时隙分配绝对的均匀了。这是由于本节提出的时隙分配技术总是尽力地取获取相邻时隙间隔最接近理想值A的空闲时隙集合:空闲时隙数量m一定, 需分配时隙数量k越多, 可调整或挑选的范围就越少, 导致均匀度不可避免的增加;需分配时隙数量k一定, 空闲时隙数量m越多, 可调整或挑选的范围就越多, 均匀度越是可以减小。从2.1节所定义的均匀度σ来看, 在N=128, m=100和k=64时, A=N/k=2, σ=23, 表示平均分摊到k个相邻时隙间隔Di与理想间隔A的差距还不到2个时隙, 这已经可以完全满足战术数据链的作战需求了。
5 结论
随着以网络为中心的联合作战的深入发展, 战术信息高实时性的传输需求日益凸显。本文通过研究发现除了传输时延影响战术信息接收质量以外, 传输时延抖动更大程度的影响战术信息接收质量, 甚至可能导致战术信息完全不可用。本文在关注战术信息传输的时延的同时, 引入了最小时延抖动的目标指标, 提出一种基于最小时延抖动的固定时隙分配算法。通过仿真实验证实了算法具有了较好时隙分配的成功概率和均匀度, 提高了TDMA战术数据链中战术信息的高实时性传输能力。
摘要：现有TDMA战术数据链的时隙分配算法主要关注战术信息传输的时延, 随着以数据链网络为中心的联合作战的深入发展, 战术信息高实时性的传输需求日益凸显。提出一种基于最小时延抖动的固定时隙分配算法, 首先将TDMA战术数据链时隙均匀分配问题转化为图论中包含确定边数的不含回路的最短路径环问题, 然后采用动态规划法来求解这个包含确定边数的不含回路最短路径环问题并给出具体的算法步骤, 最后进行仿真实验来验证算法的正确性和有效性, 算法较好地满足了高实时性战术信息的传输需求。
关键词：战术数据链,时延抖动,固定时隙分配,动态规划
参考文献
[1]DOD.Tactical DataA Link (TDL) 16 Message Standard[EB/OL].2002.
[2]艾小锋.协同作战能力 (CEC) 中实时信息分发控制技术研究[D].长沙:国防科技大学, 2007.
[3]Baruah S, Bestavros A.Pinwheel scheduling for fault-tolerant broadcast disks in real-time database systems[Z].ICDE’97, 1997:543.
[4]Dong L B, Melhem R, Mosse D.Effect of scheduling jitter on end-to-end delay in TDMA protocols[Z].RTCSA’00, 2000:543.
[5]Tao L Q.Low-jitter slot assignment algorithm for deadline-aware packet transmission in wireless video surveillance sensor networks[J].International Journal of Communication, 2011.
[6]Scheduling algorithms for dynamic message streams with distance constraints in TDMA protocol[J].Real-Time Systems, 2000:239～246.
[7]Ergen S C.TDMA scheduling algorithms for sensor networks[Z].Berkeley University, 2005.
[8]Verma D C, et al.Delay jitter control for real-time communication in a packet switching network[J].Communications Software, 1991:35～43.
[9]Erari D, Verma D C.A scheme for real-time channel establishment in wide-area network[J].Selected Areas in Communications, 1990:368～379.
[10]Han C C, et al.Distance-constrained scheduling and its applications to real-time systems[J].Computers, IEEE Transactions, 1996, 45 (7) :814～826.
[11]梁爽等.地空数据链中的时隙分配算法[J].空军工程大学学报, 2005, 6 (3) :12～14.
浅析TDMA时隙分配算法 篇2
关键词：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
固定时隙分配论文 篇3
在高技术战争中,作为高效的数据交互渠道——数据链,往往需要具备高实时性、高动态性和强自组织性。基于自组织时分多址技术的数据链[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.
固定时隙分配论文 篇4
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.
固定时隙分配论文 篇5
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,Hss 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.
固定时隙分配论文 篇6
随着我国航空运输的迅速发展, 航班需求的急剧增加使得空中交通网络日趋拥挤, 其中机场拥塞是空中交通拥塞的瓶颈所在[1]。当预测到机场的需求超出容量时, 流量管理部门就要采取相应的措施来缓解拥挤问题, 地面等待策略 (GHP, Ground Holding Policy) 就是解决此类问题的一种有效手段。GHP可以描述为: 在航班延误不可避免的前提下, 让航班在各自起飞机场延误一定的时间后再起飞, 将空中延误转化成地面延误, 其核心问题是时隙分配问题[2]。时隙分配是一种特殊的资源配置问题, 指按照一定的方式或依靠某种机制, 将机场时隙资源分配给航班或航空公司。随着协同决策 (CDM, Collaborate Decision Making) 思想的引入和发展, CDM GHP的时隙分配问题已经成为空中交通流量管理一个新的研究热点和重点。
在CDM GHP中, NEXTOR (National Center of Excellence in Aviation Operations Research) 研究小组将时隙分配过程分为初始分配和再次分配2个阶段, 并提出了RBS (Ration-By-Schedule) 与compression算法分别分配时隙, 在美国得到了实际应用[3]。虽然执行RBS和compression算法提高了航空公司的决策能力, 但前提是航班取消导致时隙空闲, 决策空间依然十分有限。为了寻求更大的决策空间, Vossen等建立了1-1和2-2的时隙交换模型并进行了仿真。结果表明, 即便没有航班取消, 2-2的交换形式也能很好地满足航空公司的决策目标, 同时指出了可以将2个时隙作为组合与另外2个时隙进行交换[4,5]。在这些研究中都认为时隙对于航空公司的价值是已知的, 在此基础上寻求收益最大化的分配结果。但是在实际中, 如果不是以延误时间为决策目标的话, 这种假设是难以成立的。由于票价、客座率等信息属于“商业秘密”, 航空公司往往只知道时隙对于本公司的价值, 并不清楚时隙对于其他航空公司的真实价值。拍卖方式正是解决这种情况的一种有效手段。
Hamsa针对1-1的时隙交易问题, 研究了单一时隙拍卖模型[6]。1-1的时隙交易目的是减少延误, 存在局限性, 所以需要对2-2时隙交易的组合拍卖进行研究。组合拍卖作为资源配置的一种有效方式, 已经广泛应用于合作规划[7]、运输服务[8]等领域。在时隙分配领域, Rassenti等研究了机场降落和起飞权的组合分配问题[9]。组合拍卖机制包括了分配规则和支付规则两部分, 组合拍卖竞胜标确定问题是分配规则中的是一个难题[10]。文献[11]、文献[12]、 文献[13]、 文献[14]分别对这一问题及其传统的精确算法和近似算法做了分析研究, 结果表明传统的精确算法因求解问题的规模相对较小在实际应用中受到限制, 近似算法因求解问题的精度相对不足或耗时相对过多在实际应 用中受到限制。随后, 遗传算法[15]、蚁群算法[16]、粒子群算法[17]等人工智能算法相继用来求解竞胜标模型, 取得了较好的应用效果。人工鱼群算法自产生以来就在优化领域得到广泛发展[18], 王飞等将该算法应用于GHP和终端区飞机降落排序问题, 取得了良好的效果[19]。
本文针对2-2时隙交易问题, 建立组合拍卖模型, 并设计人工鱼群算法, 为GHP时隙分配的研究提供一种有益的指导。
2 竞胜标模型
所谓竞胜标, 就是使得整体收益最大的那一组投标。在组合拍卖中, 利用竞胜标模型来确定最优分配结果的。在时隙分配中, 流量管理部门作为拍卖人, 航空公司作为竞拍人。流量管理部门同时向航空公司提供一组时隙S={1, 2, …, N}, 每个航空公司i知道自己对时隙的评价, 即时隙对于本公司的价值, 但该信息是私人的, 并且流量管理部门和其他航空公司都无权使用。对于每个可能的时隙子集s⊆S, 共有2N-1个可能的子集, 每个航空公司对其所提交的投标s的标价记为bi (s) 。由于不同的航空公司可能对于相同的时隙组合感兴趣而分别投标, 此时就需要按照式 (1) 对投标进行筛选:保留每个时隙组合的最高投标, 其它投标视为无竞争力而被放弃。
然后利用筛选后投标建立组合拍卖的竞胜标模型:
约束条件:
其中, 式 (2) 表示以最大化拍卖方的收益为目标;xs=1意味着在投标s上最高投标的航空公司是被承认的, 反之xs=0意味着在s上没有投标被承认;式 (3) 保证每个时隙只能分配给一个投标的航空公司。
该模型是一个组合优化问题, 模型的求解是一个NP难题。规模不大的情况下可用传统的线性规划方法快速求解, 但是随着组合投标数量的增加, 存在维数爆炸的缺陷, 所以本文采用人工鱼群智能算法求解该模型。
3 人工鱼群算法设计
本节首先对人工鱼群算法的符号进行定义, 然后阐述了算法的行为描述, 最后对收敛性能进行了分析。
3.1 符号定义
人工鱼群算法最初是应用于连续型优化问题上的, 本文所讨论的组合拍卖模型是离散型优化问题。因此需要对原始的定义进行相应的改进以满足应用需求。
①fi:第i条人工鱼。假设经过筛选的投标共有n个, 则采用一个n位的0-1编码串 (x1, …, xs…, xn) 来表示一条人工鱼的构造, 每条人工鱼就代表问题的一个解。其中fi代表第i个投标的取值, fi=1表示中标, fi=0表示未中标。
③d (fi, fj) :表示人工鱼fi和fj之间的距离, 令fi= (a1, …, an) , fj= (b1, …, bn) , 其计算公式为:
④v:表示人工鱼的感知距离。
⑤N (fi, v) :表示当前状态fi的visual-邻域, 也称视野范围。
⑥δ:表示拥挤度因子。
3.2 行为描述
该算法主要有四种典型的行为:觅食、聚群、追尾和随机行为。
①觅食行为。
这是鱼的基本行为, 当发现附近有食物时, 会向该方向游动。对当前人工鱼fi, 根据式 (7) 在视野范围内任选一个状态fj, 计算目标函数值yi和yj. 如果yj>yi, 则向该方向前进一步, 用fj替代fi, 成为新的当前人工鱼;反之, 在视野范围内再重新随机选择fj, 判断是否满足前进条件;试探一定次数后, 如果仍不满足前进条件, 则执行其他行为。
②聚群行为。
它们往往能形成非常庞大的群。对当前人工鱼fi, 其visual-邻域的伙伴数目为nf, 人工鱼总数为num. 如果 (nf/num) <δ, 0<δ<1, 表明中心位置有较多食物并且不太拥挤。visual-邻域中心位置为fc, 对应的函数值为yc. 如果此时yc>yi, 则人工鱼向中心位置fc前进一步;否则执行其他行为。δ的取值要根据具体情况确定, 本文通过试探法取δ=0.9。
本文采用如下方法来确定中心位置: 首先将fi的visual-邻域的人工鱼按照目标函数值yi的大小次序排列;然后借鉴遗传算法中对人工鱼的选择操作, 选取目标函数值较大的部分人工鱼组成新的集合, 在此集合中选择新的状态fj; 接着计算yi-yj, 采用模拟退火算法中依概率接受新解的思想, 如果满足 (yj-yi) /yi<β (β是设定的误差值, 没有统一的取值规则, 本文采用试探法取β=0.2) , 则要依概率接受新的状态, 这些被接受了的新的状态就组成了集合U. 若U不是空集, 则在U中任选一个作为中心位置, 否则fi作为中心位置。这样, 既可保证当前状态向较优的方向移动, 也可避免陷入局部最优而无法跳出, 同时也降低了计算复杂度, 提高了算法的执行效率。
③追尾行为。
当某条鱼发现该处食物丰富时, 其它鱼会快速尾随而至。设当前人工鱼为fi, 其邻域内状态最优的邻居为fmax, 如果ymax>yi, 并且fmax的邻域内伙伴的数目nf满足 (nf/num) <δ, 0<δ<1, 表明fmax的附近有较多的食物并且不太拥挤, 则向fmax的位置前进一步;否则执行其他行为。
④随机行为。
当闲暇无事时, 轻松的自由游动。随机行为是从当前状态无约束的转移到另一可行状态。在寻优过程中, 当最优解长时间没有得到改进, 在对计算量没有太大影响的前提下, 可以加入随机行为来搜索另一个可行解空间。
这4种行为并没有明确的先后执行顺序, 通常是按照进步最快的原则或者进步即可的原则来选择。本文采取的策略是依次进行追尾、觅食和聚群行为, 如果依然没有明显进步就进行随机行为。算法采用自下而上的设计方法, 即首先构造人工鱼的个体模型, 个体在寻优的过程中自适应的选择合适的行为, 最后全局最优结果通过群体或者某个个体表现出来。
3.3 收敛性能分析
对于算法而言, 收敛性是首要关心的问题。在人工鱼群算法中, 人工鱼的觅食行为奠定了算法收敛的基础, 聚群行为增强了算法收敛的稳定性和全局性, 追尾行为则增强了算法收敛的快速性和全局性。文献[18]通过仿真试验和数据分析, 研究了步长step、拥挤度因子δ、人工鱼数量、感知距离visual等参数对算法收敛性能的影响, 结果证明了该算法具有较稳定的收敛性能。
收敛准则是优化算法的重要组成部分。收敛准则选择的好与坏直接影响到算法是否收敛以及收敛的快慢。本文选择已经得到广泛应用的收敛准则:前后迭代点的逼近是否满足一定的精度, 即
其中, ε为一个足够小的正数。当前后迭代点的差值连续30次小于ε, 认为满足收敛准则, 算法结束。
4 算例分析
对3家航空公司的10架航班进行算例仿真, 没有航班取消。初始分配用RBS算法来实现。由于没有航班取消, 无法使用compression, 体现了其局限性。所以, 再次分配过程用组合拍卖模型来解决。RBS初始分配结果见图1所示, 图中航班A1:1∶00代表航空公司A的第一架航班, 计划着陆时隙为1∶00, 其余依此类推。
航空公司只对自身感兴趣的时隙组合进行真实标价。同一个时隙对于不同的航空公司的价值往往都不是一样的, 甚至对于同一个航空公司的不同决策目标的价值也不一样。因此, 在对时隙估价时, 要考虑本公司的决策目标以及相应的航班、航线的影响。如何对时隙进行估价, 不是本文的重点, 本文对此作了简化, 直接给出标价结果。
假设航空公司A没有特殊的决策要求, 系统默认以减少延误成本为目标; 航空公司B期望B2下移到时隙6, B3上移到时隙8以满足banking限制[20]; 航空公司期望比较重要的航班C2上移到时隙5, 相对不重要的C3下移到时隙9。表1列出了经过筛选后的部分组合及标价。
在表1中, 航空公司A列出了单一时隙的投标, 没有进行组合投标, B和C都分别进行了组合投标。
将表1的投标代入竞胜标模型, 得到如下整数规划标准形式:
其中, 式 (10) 保证了每一个时隙最终只能出现在一个组合里;式 (11) 是对航空公司A的时隙数量的约束。
用人工鱼群算法求解该模型, 可得x1=1, x4=1, x6=1, x12=1, x14=1, 其余变量为0, 由此可得到竞胜标的分配结果为图2所示。
由于本算例中并不存在空闲时隙, 所以compression算法并不适用。RBS算法、文献[5]建立的2-2网络流模型以及组合拍卖模型分配结果的对比分析如表2所示。
从表2可以看出, RBS算法得到的总收益为900元, 其他两种方法得到的总的收益为1140元, 说明人工鱼群算法具有较好的优化效果。2-2网络流模型中航空公司需要相互独立的构造大量的时隙交易申请, 各航空公司的交易申请很可能是重复冗余或相互排斥的, 流量管理部门 需要保证整体安全性的基础上, 决定接受还是拒绝这些交易申请, 其计算量相当庞大。而利用人工鱼群算法求解本算例的组合拍卖模型, 耗时不到5秒, 满足实时应用的要求, 说明了用人工鱼群算法求解组合拍卖模型是可行和有效的。
5 结语
本文针对2-2时隙交易问题, 建立了组合拍卖模型, 并设计了人工鱼群算法来求解模型。算例仿真结果验证了2-2组合交易能够提高航空公司的决策能力, 更好地满足航空公司决策目标, 说明了模型是可行的, 人工鱼群算法具有较好的求解效率, 满足实时应用要求。下一步将会研究满足预算平衡的支付规则, 从而完善整个拍卖机制。
固定时隙分配论文 篇7
关键词：时分多址,统一时隙分配协议,Ad Hoc
随着硬件和无线通讯技术的迅猛发展, 激发了Ad Hoc (一种自组织网) 网络的发展。平均分配时隙TDMA (时分多址) 是传统的无线通讯技术, 具有可避免负载信息包传输冲突的能力。目前已有很多TDMA在Ad Hoc上应用的研究, 但均没有考虑自组织移动主机的情况, 所以它们不能在自组织网络中进行时隙分配。一些协议通过提供足够多的时隙以保证分配时隙的冗余性, 但巨大的预留时隙使信道利用率下降[1,2,3,4,5,6]。
这里设计了一个新TDMA时隙分配协议可以使其在Ad Hoc环境中应用, 并提升信道利用率。该协议根据争夺区域内移动主机的数目, 动态的改变帧长以适应自组网对变化时隙分配的要求[7,8,9]。
1 UASP协议介绍
目前在TDMA中大量使用的是戴维·杨提出的统一时隙分配协议 (USAP) , 图1所示TDMA在统一分配时隙协议USAP中的形式。它由N个帧组成, 每个帧由M个时隙组成, M和N都是定值。每个帧的第一个时隙用于描述该传送节点的控制信息包, 叫做NMOP (节点管理操作信息包) 。这样, 统一分配时隙协议USAP允许N个节点存在于网络中, 每个节点拥有相应的NMOP (节点管理操作信息包) , 这N个帧组成一个循环。
节点间通过一系列的信息交换使每个节点明白存在的未分配时隙的状态并在其中为自己分配一个时隙使用。因为每个节点收到一个新节点管理操作信息包NMOP都会刷新自己的统一时隙分配协议USAP, 所以统一时隙分配协议可以反映出网络内节点的存在状况。例如当一个新加入网络的用户, 开始时它没有参与信息传送的时隙, 也不知道邻居的信息, 它首先通过侦听网内信道一个完整的循环并收集网内节点管理操作信息包NMOP, 这样它就可以明白所在区域内各节点的时隙分配情况。然后, 新节点会选择一个未分配的时隙为自己使用。最后它要将自己的选择向邻居进行申明。由于统一时隙分配协议需要提供足够多的时隙用于网内节点的分配, N和M值的设置将以实际存在用户数目最大的情况进行考虑, 这样就会导致存在大量的未分配时隙使信道利用率降低[7,8,9,10,11,12]。
图2是一个统一分配时隙多址的帧长控制示意图, 它通过减少非分配时隙促进了通道利用率, 但通道的利用率依然很低。
2 新协议介绍
该协议是根据处在竞争区域节点个数和最少非分配时隙个数为新节点设置帧长, 以促进通道的利用率。
图3表示该协议中TDMA的形式, 相似于ABC协议, 本协议帧长也是2的幂次数, 帧的第一个时隙被保留给新节点去发送控制数据包以要求安排一个时隙分配。这样就不会有数据包在这个时隙被发送。
2.1 关于协议的数据的两个形式
协议的数据有两个形式:发送方式和控制方式, 不同的方式对应不同的节点运行。
(1) 发送方式:主要发送DAT数据包。
数据包 (DAT) 包含有发送者的帧长信息和被分配时隙以及邻居中最大帧长数, 还包括要发送的数据内容。
(2) 控制方式:发送一些网络控制用数据包。
请求数据包 (REQ) 只由新节点发送。通过向邻居发该信息包, 新节点向区域内的节点表明要求得到它们的帧长和时隙分配信息。
信息数据包 (INF) 含有发送者的帧长信息和发送者及其邻居的信息时隙分配信息。
建议数据包 (SUG) 和REQ数据包一样, 只能由新节点发送。通过向邻居发送该数据包, 新节点发布了它的帧长和时隙信息。
回复数包 (REP) 发送的是对SUG数据包的回应。
2.2 关于时隙分配
节点通过下列步骤完成为自己选择一个时隙的过程。
(1) 向区域内发布信息请求。
当一个新节点加入网络的时候, 既不知道网络拓扑信息, 也不知道区域内其它节点的时隙分配情况。为了得到这些信息, 新节点首先侦听通道和搜索邻居发送的数据信息包一段时间。然后从获得的DAT (数据包) 信息中分析出邻居节点的帧长、时隙分配和邻居中最大帧长信息。然后, 新节点在下一个帧的第一个时隙发送一个REQ数据包。
(2) 设置帧长和控制时隙分配。
在收集完邻居节点的信息后, 新节点设置帧长, 如果同一区域内的节点具有相同的帧长, 新节点将该帧长作为自己的帧长。否则, 新节点选择区域内最大的帧长作为自己的帧长。然后从获得的信息字中, 新节点知道区域内的时隙分配信息。在以前, 收到的信息只进行合并处理, 现在则可通过下述步骤要求得到时隙分配信息。首先, 新节点创建它自己的帧长时隙分配信息。M0表示新节点的帧长, 此时如果邻居节点的帧长与M0相同, 新节点就拷贝邻居节点INF中的时隙分配信息。否则, 当M0=αMi, 所有邻居节点的时隙分配信息被拷贝到新节点并加入的对应M0/α时隙中, Mi表示邻居节点帧长, α是2的整数倍整数。通过这种方法, 新节点合并邻居节点的信息并创建它自己的时隙分配信息。例如当新节点设置它的帧长为8, 节点a的时隙分配信息中帧长和时隙分别为8和4, 在新节点中每4个时隙重复一次, 如图4所示。
(3) 选择时隙。
根据新节点创建的时隙分配信息, 新节点按如下步骤为自己选择一个时隙, 在图5, 图6和图7中, 黑和白时隙分别表示第一时隙和未分配时隙, 阴影时隙表示已分配给其它节点的时隙。每个时隙中的数字和字母表示时隙号和时隙分配给的节点。
1) 得到一个未分配时隙 (GU) 。
如果时隙分配信息中含有未分配时隙, 新节点则在它们中为自己分配一个。例如图5中, 3, 7时隙为未分配时隙, 新节点可以在3, 7中为自己选择一个时隙。
2) 释放重复时隙 (RMA) 。
如果没有未分配时隙可用, 新节点则查找是否节点中有占用多个时隙的节点, 如果有这样的节点, 新节点在重复占用时隙的节点中释放一个时隙为自己使用。如果这里有多个节点拥有多个时隙, 那么这其中占用时隙最多的节点被要求释放一个时隙。例如图6, 节点a, b都拥有多时隙, 新节点就在1, 5和2, 6中选择一个时隙给自己使用。
3) 双帧 (DF) 。
如果没有未分配时隙也没有多时隙复用情况可被新节点利用, 新节点可通过加倍时隙帧长, 并将分配信息复制到增倍帧长的前边和后边。由上述内容可知, 帧的第一个时隙不分配给任何节点。这样, 经过倍增后的帧长后半部分的第一个时隙成为未分配时隙, 新节点选择它作为自己的时隙使用。例如图7所示, 当新节点倍增帧长后, 时隙8被分配给自己使用。
(4) 发布和认证。
新节点给自己选择了一个时隙后, 会发送一个建议数据包SUG给它的邻居, 该信息包包含新的帧长和时隙分配信息。当区域内的邻居收到这些信息包就会按该信息包的内容更新自己的帧长和时隙信息。更新的方法见步骤 (2) 设置帧长和控制时隙分配。
每次收到SUG信息包更新完后, 每个节点向邻居发送一个回复数据包REP指令。发送REP表明节点已收到新节点的SUG信息包、更新了时隙分配信息并且退出了对所有邻居的控制方式。发送和接收REP信息的节点均采纳了新时隙分配方法并在下一帧开始发送数据。新节点在收到所有邻居REP数据包后, 新节点转入发送数据状态。
在本协议中, 当新节点面临两个或多个节点分给相同时隙的时候, 就会出现一个时隙分配冲突, 如图8所示。
在a, b节点间的新节点就会遇见一个时隙都为4的冲突, 它可以按如下方法进行解决:
1) 删除冲突时隙。
如果有一些非冲突时隙分配给节点引起了冲突, 冲突时隙保留在具有最少时隙节点的节点内, 其余的节点删除该时隙内容, 如图9所示。
当节点a, b分配有非冲突时隙7, 11, 15和冲突时隙3, 那么从a节点释放时隙3, 因为a节点比b节点的时隙多。
2) 分离分配。
如果多个时隙冲突出现在新节点中, 这些时隙在冲突节点内被分给不同的节点。如图10所示, 冲突时隙被分别分给节点a和b。
3) 倍增帧长并分离时隙。
如果冲突的节点都只有一个时隙分配, 这样的冲突不能依靠现有的帧长去解决, 可以通过倍增帧长再分开的办法进行解决。如图11所示冲突时隙空间扩大一倍, 再把它分别分给节点a和节点b。
经过上述重新构划的时隙分配后, 新节点发送一个SUG指令信息汇同自己的重构时隙分配和时隙选择, 收到SUG信息的邻居重构他们的时隙分配内容并发送REP指令和重构信息。当然在某些情况下, 新节点可能因为出现INF冲突使信息收集失败, 如果这种情况出现, 新节点向邻居发送冲突出现数据包, 邻居收到后会在等待一个随机数的时候重新发送INF数据包。这些操作一直重复, 直到新节点完全收到邻居INF信息。
当一个节点离开了网络时, 它自己释放所占用的时隙并停止发送数据DAT。当邻居节点发现该节点没有在它的发送时隙发送数据, 就认为该节点已离开, 而执行从它们的时隙分配中释放离开节点所占时隙。
3 结束语