一种适用于自组织网的动态时隙分配算法

王宝玺，文运丰，马鹏飞，扈 鹏

(中国电子科技集团公司第五十四研究所，河北石家庄050081)

0 引言

在无线自组织网络［1，2］中，基于分配和基于竞争是2类主要的网络接入协议，其中分别代表TDMA和DCF协议。固定TDMA协议具有协议复杂度小、可以保证所有节点发送数据的公平性且控制开销小等优点，但在网络规模大、网络节点多时，网络的平均时延增大、时隙资源有很大浪费。DCF［3－6］协议中每次发送数据都需要进行分布式竞争以及RTS/CTS、DATA/ACK四次握手，开销较大，对网络的吞吐量和平均时延均有影响。

通过结合和改进上述2类分配算法，提出一种动态 TDMA(DTDMA)算法［7－10］，可以有效实现节点动态入网退网，并且动态地调节时隙分配，减少空白时隙的浪费，从而获得较高的系统吞吐量，减小时延，弥补了上述2种算法的缺点。

1 DTDMA算法

1．1 DTDMA算法描述

提出的DTDMA算法将网络节点的时间轴同步划分为一系列连续、不定长的网络时帧，如图1所示。网络节点在每一个网络时帧内发起数据传输，传输过程包括节点同步、时隙请求、时隙分配和数据发送4个阶段，如图2所示。组网协议中，网络时帧的长度根据网络中节点的业务需求自适应的调整。

图1 DTDMA网络时帧划分网络时间轴

图2 DTDMA不定长网络时帧的结构

1．1．1 同步阶段

同步阶段在网络时帧的同步时隙内完成。在该阶段内，初始时，网络中的各节点采用竞争广播同步帧的方法，实现各节点间的时间同步，并产生当前网络时帧的中心节点，负责完成当前网络时帧内数据子时隙的分配。节点在广播同步帧之前，首先在一定长度的时间范围内随机选择一段以定长时隙为单位的同步帧前退避时间，并在退避时间内持续监听信道。若信道保持空闲，则退避时间结束后，节点即可向网络中的其他节点广播同步帧。本文算法提出的节点组网协议采用以下分布式的方法判断同步帧广播是否成功:

①节点广播同步帧后，在一定长度的时间内持续监听信道，如果信道保持空闲，则判定本次同步帧广播成功，本节点当选为当前网络时帧的中心节点，负责完成网络中各节点数据时隙的分配，节点同步阶段结束;如果在这段时间内信道变忙，则节点判定本次同步帧广播失败，并尝试接收其他节点广播的同步帧。

②如果节点成功接收了网络中某个节点广播的同步帧，则该节点在同步帧接收结束后一定长度的时间内持续监听信道，如果信道保持空闲，则节点判定同步帧广播成功，该同步帧的广播节点即为当前网络时帧的中心节点，并采用同步帧中携带的同步时间信息对自身的时钟进行校准;如果信道在这段时间内变忙，则节点判定同步帧广播失败，并尝试接收新的同步帧。

③如果节点接收同步帧失败，则节点等待信道恢复空闲后，在一定时间范围内随机选择退避时间并监听信道，如果在退避时间内信道保持空闲，则退避过程结束后，该节点向网络中的其他节点广播同步帧。

之后的各网络时帧中的同步时隙中，上一时帧中心节点发送同步帧，其余节点等待一段时间。若中心节点退网或被摧毁，则其余节点等待超时后，以上述方式重新竞争中心节点。

1．1．2 请求阶段

时隙请求阶段在网络时帧的请求时隙内完成。DTDMA算法将请求时隙划分为N+1个请求子时隙，N为当前网络中的节点数量。其中，第1个和第N+1个请求子时隙用于新入网节点，其余N－1个请求子时隙用于网络中除中心节点外的N－1个节点。在与本节点相对应的请求子时隙到来时，根据当前需要发送的业务量及业务优先级确定需要请求的数据子时隙数量，将各时隙请求及业务优先级等信息发送给中心节点。

中心节点维护一个用于存储各节点时隙请求和业务优先级信息的线性链表。中心节点首先将自身的时隙请求信息存入链表，然后在时隙请求阶段的各个请求子时隙中接收其余节点发送的数据时隙请求帧，并将其中的相关信息存入链表。时隙请求阶段结束后，中心节点通过遍历链表，即可获知当前网络时帧内网络中各节点的时隙请求及业务优先级信息。

1．1．3 时隙分配阶段

时隙分配阶段在网络时帧的分配时隙内完成。在该阶段内，中心节点根据请求链表中存储的网络中各节点的时隙请求及业务优先级信息，对本网络时帧中的数据子时隙进行分配，为网络中的各优先级业务提供QoS保障。分配方法见1．2节。数据子时隙分配完毕后，中心节点将网络中节点总数量、当前网络时帧内数据子时隙的总数量及各节点的时隙分配情况等信息写入数据时隙分配帧，通过广播数据时隙分配帧，将数据子时隙的分配情况告知网络中的各节点。

1．1．4 数据发送阶段

数据发送阶段在数据时隙内完成。网络中的各节点在接收到中心节点广播的数据时隙分配帧后，从数据时隙分配帧中获取当前网络时帧内的总数据子时隙数及自身分配到的数据子时隙信息。各节点等待自身分配到的数据子时隙到来时向网络中的其他节点发送自身的数据分组。各个数据子时隙内的数据分组传输完成后，当前网络时帧结束，网络中的各节点进入下一网络时帧的同步阶段。

1．1．5 新节点入网过程

当有新节点需要加入网络时，DTDMA算法要求新节点至少持续监听信道一个网络时帧的时间，从而保证新节点能通过侦听同步帧和数据时隙分配帧获知时间同步信息和网络节点的总数量(假定为N)。成功侦听上述信息后，新节点在下一个网络时帧的第1个请求子时隙中向中心节点发送入网请求帧。同时，在第1个请求子时隙内，为了避免由于多个新节点同时发送入网请求帧而导致冲突，本方案提出的节点组网协议要求节点在发送入网请求帧之前，首先在一定范围内随机选择一段以定长时隙为单位的入网退避时间，并在退避时间内持续监听信道。若信道保持空闲，则新节点退避结束后即可向中心节点发送入网请求帧;而若信道变忙，新节点则等待在下一个网络时帧内重新竞争发送入网请求帧。中心节点成功接收入网请求帧后，即向新节点发送入网应答帧。若新节点正确接收到入网应答帧，则表明本节点入网成功。

入网成功后，新节点将自身的编号设置为N+1，并使用请求时隙的第N+1个子时隙向中心节点发送数据时隙请求帧。数据时隙请求帧发送成功后，中心节点即可为新入网的节点分配数据子时隙，并通过广播数据时隙分配帧，将更新后的网络节点总数量告知全网节点。

1．1．6 节点退网过程

如果某节点需要主动退出网络，则该节点从当前时刻起不再参与同步帧的竞争广播。同时，在自身的请求子时隙到来时，该节点向中心节点发送退网请求帧进行退网。

DTDMA算法允许多个节点在同一个网络时帧的时隙请求阶段向中心节点发起退网请求。时隙请求阶段结束后，中心节点将当前网络时帧内成功退网节点的编号及退网后网络节点的总数量分别写入数据时隙分配帧。数据时隙分配帧广播成功后，网络中的其余节点即可根据帧中的退网节点编号更新自身的编号。

由上述讨论可知，DTDMA具有以下优势:

①允许网络中的各节点以自组织方式组网，并且每网络时帧中各节点通过竞争产生中心节点，负责完成当前网络时帧内数据时隙的分配，具有很强的抗毁性;

②组网协议根据网络中节点的业务需求自适应的调整网络时帧的长度，能够有效提高时隙利用率;

③中心节点根据网络中各节点业务的优先级完成网络时帧中数据子时隙的动态分配，能够为网络中的不同优先级业务提供QoS保障;

④支持节点的入网和退网，能够满足网络规模动态变化的需求。

1．2 DTDMA时隙分配算法

中心节点在遍历请求链表后，计算业务请求的优先级和数量，根据以下算法进行区分优先级的数据时隙动态分配。

①设置最大总数据时隙数，以及各优先级最大数据时隙数，避免某一时帧过长，若有节点入网，会使得其入网时间变长。其中高优先级可分配的时隙数多于低优先级。这样既可保证高优先级业务的QoS，又能保证低优先级业务能够发送，兼顾公平性。

②计算总请求时隙数和各优先级时隙数，并分别与相应最大时隙数对比，选择其中小的为可分配的时隙数。若可分配的总时隙数大于各优先级可分配时隙数之和，则将剩余时隙按照优先级从高到低依次分配给各优先级。

③首先分配优先级高的业务时隙。判断当请求等于实际可分配的时隙数时，则按照请求的情况依次分配。若请求多于实际可分配的时隙数时，则首先给每个请求的节点分配一个时隙，保证其在本时帧中能够发送数据。再将剩余的时隙按照概率分配给各请求节点。

④之后再以同样方法分配其它优先级的数据时隙。

2 EXata网络建模仿真

EXata是一款能够产生连接真实网络及应用的网络仿真软件拥有一套综合体系工具对有线及无线网络进行精确建模和预测。

2．1 仿真场景设置

场景采用三维笛卡尔坐标系，仿真区域为水平35 km×35 km。在区域内随机放置节点，设置各节点的传输距离为50 km。采用静态路由方式，传输层采用UDP协议，物理层采用DSSS模型，仿真业务使用CBR，业务优先级由高到低分别为2、1和0，数据包长度为2 006 bytes。DTDMA设置最大时隙数为36，优先级2、1和0的业务可分配的最大时隙数分别为16、12和8。仿真时间80 s。带宽为2 Mbps。

2．1．1 应用层不存在优先级

随机放置8个节点。业务分别为节点1和节点2互发，节点3和节点4互发，节点5和节点6互发，节点7和节点8互发。节点1每隔一段时间发送一个数据包，其余节点每隔0．2 s发一个数据包。固定TDMA分配8个时隙，每个时隙长度为8．5 ms。仿真结果如图3和图4所示。

由图3和图4可以看出，若业务为恒定比特流，DTDMA、TDMA和DCF在业务负载较轻时，吞吐量和平均时延性能几乎一致，且由于DTDMA每个时帧需要进行同步阶段、请求阶段和分配阶段;DCF每次发送数据也要有RTS/CTS以及ACK等开销，因此它们的平均时延都比TDMA略大。当网络中负载逐渐加重时，由于TDMA的时隙固定分配给每一个节点，突发业务不能利用其它节点的发送时隙，因此，其吞吐量很快饱和，并且饱和后时延迅速增大。而DTDMA可以动态分配时隙，其吞吐量和平均时延性能均优于TDMA。而饱和时的DCF由于4次握手的开销大，因此其饱和时的网络吞吐量小于DTDMA，平均时延也大于DTDMA。

图3 DTDMA、TDMA和DCF吞吐量对比

图4 DTDMA、TDMA和DCF平均时延对比

2．1．2 应用层存在优先级

随机放置6个节点。业务为节点1和节点2互发，节点3和节点4互发，节点5和节点6互发。各节点均每隔相同一段时间发送一个数据包。设置应用层CBR业务有3种优先级分别为2、1和0。其中节点1和节点2发送数据包的优先级为2，表示为LINK2;节点3和节点4发送数据包的优先级为1，表示为LINK1;节点5和节点6发送数据包的优先级为0，表示为LINK0。固定TDMA分配6个时隙，长度均为8．5 ms。仿真结果如图5和图6所示。

通过图5和图6可以看出，在网络负载量小，3种协议的网络均未饱和的时候，3种协议的3种优先级业务的吞吐量和平均时延性能基本相同，其中平均时延的优先级的微小差别是由于按照节点ID顺序发送数据包造成的。而当网络负载量逐渐增加到一定程度时，对于DTDMA首先是低优先级的业务的吞吐量减小，中高优先级业务吞吐量继续增加，这是由于协议牺牲了低优先级业务来满足中、高优先级业务需要，之后网络负载量再增加到一定程度时，牺牲中优先级业务来满足高优先级业务的发送。但是，中、低优先级业务吞吐量并没有无限的减小来保证高优先级业务的传输，而是最终稳定在一个数值上，这表明DTDMA在满足高优先级业务发送的同时，也兼顾中、低优先级业务的发送，从而保证一定的公平性，使得高优先级业务不会垄断发送。因此，DTDMA可以进行区分业务优先级传输。对于TDMA，3种优先级业务的吞吐量和平均时延始终重合，这是因为它的业务是在各自固定时隙内发送，所有业务处于平等地位，所以不能区分业务优先级。对于DCF，也可以看出吞吐量和平均时延与优先级无关，这是因为DCF中的业务传输是通过竞争进行，所以也不能区分优先级。而且可以看出，对于高优先级业务，DTDMA协议的吞吐量和平均时延均优于DCF和TDMA协议。这说明在传输有优先级区分的业务时，DTDMA协议相对TDMA和DCF，可以提高高优先级业务的传输质量。

图5 3种优先级业务吞吐量对比

图6 3种优先级业务平均时延对比

3 结束语

综上所述提出的算法，综合分配类和竞争类协议的优点，可根据网络中的业务需求，利用较小的控制开销，动态调节时帧长度，在有突发业务时，保证较大的网络吞吐量和较小的平均时延;在支持不同优先级业务QoS的同时，保证一定的发送公平性;可以支持多节点的无冲突入网退网。

该项研究可以提高网络的传输效率，改善网络性能，对于组网技术发展具有指导和验证的意义。可以提高飞行器编队的高效协同组网能力，实现空战向基于战场信息共享网络的多机协同作战模式的转变，为天空地一体信息化作战体系及现代网络中心战的实现提供新概念、新技术和新方法。

［1］ 郑少仁，王海涛，赵志峰，等．Ad Hoc网络技术［M］．北京:人民邮电出版社，2005．

［2］ 陈林星，曾 曦，曹 毅，等．移动Ad Hoc网络:自组织分组无线网络技术［M］．北京:电子工业出版社，2006．

［3］ 孙义明，杨丽萍．信息化战争中的战术数据链［M］．北京:北京邮电大学出版社，2005．

［4］ IEEE Std 802．11 － 1997．Wireless LAN Medium Access Control(MAC)and Physical Layer(PHY)Speci-fications［S］，1997．

［5］ O’HARA B，PETRICK A．IEEE 802．11 Handbook:A Designer’s Companion［M］．New York:IEEE Press，1999:2－5．

［6］ BIANCHI G．Performance Analysis of the IEEE 802．11 Distributed Coordination Function［J］．IEEE Journal on Selected Areas in Communication，2000，18(3):535－547．

［7］ 齐忠杰，李春风，牛增新．一种拓扑自适应时帧同步方法［J］．无线电工程，2010，40(9):4 －6，18．

［8］ 常 扬，陈建民，马鹏飞．高速无人机网络MAC协议设计与性能分析［J］．无线电工程，2011，41(3):23－26．

［9］ 田加敏，雷 磊，许宗泽．一种适用于可扩展 Ad Hoc网络的动态时隙分配算法［J］．小型微型计算机系统，2011，32(8):1 521 －1 525．

［10］商英俊，黄 伟，贾慧英．动态TDMA接入协议仿真分析［J］．无线电通信技术，2011，37(3)，23－25．