高效的动态按需时隙分配协议

李杨，韩志韧

(1.哈尔滨工程大学信息与通信工程学院，黑龙江哈尔滨150001;2.武汉船舶通信研究所，湖北武汉430079)

海上无线自组网是一种具有高度动态特性的网络.在网络运行过程中，如网络规模、拓扑结构等各种直接影响网络性能的因素随时会发生变化.因而要求适用于海上无线自组网的MAC层协议必须能够适应网络的各种变化，并保持相对稳定的性能.

以TDMA(time division maltiple access)为基础的分配类MAC层协议具有性能稳定、可靠，平均传输时延等QoS指标可控、便于管理等特点，近年来在对MANET(mobile Ad Hoc networks)的相关研究中受到广泛的关注.其核心问题是如何有效地为各节点分配时隙资源.针对该问题，文献[1-5]采用集中式的染色算法完成网内对节点或链路的时隙分配，该算法必须首先获得节点2～3跳范围内其他节点的拓扑和状态信息，增加了协议的开销和复杂度.以FPRP(five-phase reservation protocol)为代表的动态竞争类时隙分配协议[6-11]通过简单而可靠的握手机制与邻居节点协调预留时隙资源，但此类协议均以平均分配为原则，并没有根据实际业务负载情况对有限的时隙资源进行按需分配.文献[11]提出一种新的ODSA(on-demand and dynamic slot assign-ment)协议，以按需的策略动态分配时隙，改善了网络效率，但引入了一定的协议开销.文献[12]提出采用动态调整时帧长度的方法匹配当前业务量，具有一定的理论价值.

针对时隙分配中的预留冲突和网络效率较低的问题提出了一种新的动态竞争类时隙分配协议，即按需随机时隙分配协议(DRSA).该协议在时隙竞争过程中采用全新的随机化竞争策略，可以有效减小竞争分配过程中的碰撞概率.同时，本协议还能够根据当前业务量需求和拓扑情况灵活地为网络节点分配时隙资源，以适应网络及业务的变化，提高网络效率.

1 DRSA协议设计

在典型的海上无线自组网络环境中，网络节点通常具有较强的移动性，因而导致网络规模、节点分布密度、拓扑结构等网络参数变化较快.其次，平台上需要承载各种不同类型的数据业务，导致网络中业务负载的分布情况差异较大.为适应海上自组网的特点，DRSA协议主要采用动态竞争的时隙分配策略，根据业务量的负载情况动态地为各节点分配所需时隙资源，同时采用全新的按需跳跃预留算法(on-demand hop slot reservation，ODHR)有效地提高了时隙分配的效率和有效性.协议默认全网时间同步.

1.1 协议帧结构

DRSA协议帧格式如图1所示.在DRSA协议中，基本的周期性时间单位为时元.时元内包含1个竞争帧和若干个信息帧，其中信息帧的个数可根据需要进行裁剪.每个信息帧可分为N个信息时隙，分配给不同网络节点用于传输数据.竞争帧可分为M个竞争时隙.有需求的网络节点需在竞争帧内随机选择某一竞争时隙，以握手方式参与竞争.

协议的具体握手过程借鉴FPRP[6]协议中的5步握手机制，但采用全新的ODHR算法，通过在握手数据包中增加携带竞争标识字段和采用跳跃预留策略，有效提高时隙分配的效率和有效性.竞争标识字段记录了当前握手数据包的种类和预留发起节点需求的目标信息时隙编号.

1.2 ODHR时隙预留算法

ODHR时隙预留算法主要分为业务量评估竞争仲裁过程和跳跃时隙预留过程.算法默认全网各节点拥有相同的协议参数配置.设整个时元共配置KF个信息帧，每个信息帧中有N个信息时隙，配置一个竞争帧，包含M个竞争时隙.

业务量评估竞争仲裁过程负责评估当前业务量及可获得的时隙资源，以判定是否需要竞争新的时隙.设当前MAC层发送队列中缓冲的实际业务量为Db.而根据协议评估，某节点在当前时元内能支持的业务量为已经预留到的信息时隙资源Sp，计划预留的信息时隙资源Pp，信息帧个数KF和信道带宽B的函数:

当Db≤时，该节点已获得足够时隙资源，协议不允许该节点竞争新的时隙;而当Db＞时，协议允许该节点继续竞争新的时隙.

协议一般将竞争帧内的M个竞争时隙分为n个竞争组，每组m个竞争时隙.当某节点需要新的时隙时，跳跃时隙预留过程要在当前竞争组内选定竞争时隙号ci和目标信息时隙号rj:

式中:Rf为空闲时隙集，若Rf=∅则当前时元内无可用时隙.当时间到达选定的竞争时隙时，协议在握手数据包竞争标识字段中填入选定的目标信息时隙rj，开始竞争.

设在当前竞争组内有k个节点同时参与竞争，每个节点选定的竞争时隙为

当某节点选定竞争时隙cl满足式(4)条件时，

协议即可为该节点完成其对目标时隙的预留，并在随后的每个信息帧内均有权使用该信息时隙.在预留完成后需要更新Sp、Pp、Rf和时隙预留表.

在随后的竞争组内，重复该算法，继续为有需求的节点分配空闲的信息时隙.当整个竞争帧完成时，仍空闲的时隙将无法被使用，造成时隙浪费.设已经完成分配的时隙总数为wcell，则协议在当前时元内的时隙分配效率为

1.3 协议流程

DRSA协议共有5个主要状态，状态转移图如图2所示.当协议检测到MAC层队列中有业务数据缓冲时，从等待状态进入竞争准备状态，并完成业务量评估及竞争仲裁过程，根据仲裁结果决定是否需要预留新的时隙资源;若需要，协议开启跳跃时隙预留过程，根据时隙预留表随机选择当前空闲的信息时隙和竞争时隙，准备参与竞争.待时间到达选定的竞争时隙，协议即可进入竞争状态.当协议在等待状态时，若收到其他节点的时隙预留请求，会被动进入竞争状态配合预留发起节点完成竞争过程.在竞争完成后，协议进入更新预留状态，记录预留结果更新时隙预留表.而后，协议回到等待状态.当时间进行到本节点成功预留的信息时隙时，协议即进入业务数据发送状态，发送MAC层队列中缓冲的业务数据.

图2 DRSA协议状态转移Fig.2 The state machine of DRSA

2 DRSA协议性能分析与仿真

2.1 协议时隙分配效率分析与仿真

根据DRSA协议，时隙的分配过程完全独立.容易证明Ωg的统计平均值可以成为 E[Ωg]的无偏估计.由此，定义协议时隙分配效率Ωp为

设竞争帧的第Gj个竞争组中共有K个节点利用组内的m个竞争时隙参与竞争.各节点选择竞争时隙的所有结果可以表示为如下数学模型:

式中:a1、a2、…、am分别代表编号为1～m的竞争时隙.将该表达式逐步完全展开为多项式形式可得:

式中:

将所有同类项合并，可将式(8)简化为

式中:每项都代表所有K个节点随机选定竞争时隙的一种结果，指数k1、k2、…、km代表该结果中选择相应竞争时隙的节点数，系数 Ak1，k2，…，km代表产生相应结果的情况总数.根据式(4)定义的条件，当∃kj∈{k1，k2，…，km}∪kj=1时，在该竞争时隙内不会发生竞争碰撞，节点可完成预留.则在当前竞争组内能成功分配d个时隙的概率为

式中:

由此，在当前第Gj个竞争组内能够成功分配的时隙数的期望为wgroup(Gj):

假设，平均每个竞争组内均有K个节点参与竞争，则在当前时元内，能够成功分配时隙总数的期望为

将式(14)代入式(6)，即可得到协议的时隙分配效率.

通过蒙特卡洛仿真，图3给出了在同一竞争域内，不同数量节点同时参与竞争情况下的协议时隙分配效率Ωp.图中m×n代表不同竞争时隙总数及其分组方法，K为在同一竞争域内参与竞争的节点总数.

图3 不同参数配置下时隙分配效率Fig.3 The efficiency of slot assignment under different parameters

从图3中可以看出，竞争时隙总数对Ωp有直接影响.随着竞争时隙总数的增加，协议可有效支持更多节点同时参与竞争并保持协议时隙分配效率稳定在85%以上，但同时会增加协议的开销.在竞争时隙总数一定时，不同的分组方法也会对协议时隙分配效率造成影响.适当调整竞争组数n和每组竞争时隙数m可以在不增加协议开销的基础上进一步提高协议时隙分配效率.

同时通过图3还可以看到，适当选定竞争时隙总数及分组方法后，协议可以保证竞争节点总数K的值在较宽范围内变化时仍然有较高的协议时隙分配效率.这说明本协议具有较强的适应性和健壮性，对于因节点移动、业务分布变化而引起的网络环境变化，仍然能够保证网络的高效运行.

2.2 DRSA协议在海上自组网中的性能

使用Qualnet网络仿真软件，在典型海上自组网应用场景下，对DRSA协议、802.11以及静态TDMA协议在不同的业务负载情况下的平均吞吐量性能进行充分地仿真.仿真场景的相关主要参数如表1所示.

表1 仿真场景主要参数Table 1 The main parameters of simulation scenario

吞吐量仿真结果如图4所示.从图4中可以看出，当网络处于轻负载时，3种协议吞吐量性能相当.当网络处于中度负载时，由于静态TDMA协议服从固定的时隙分配方案，不能在空间中形成有效的时隙复用，导致静态TDMA协议的平均吞吐量性能出现瓶颈;而DRSA与802.11协议在中度负载时的吞吐量性能相当，均明显优于静态TDMA.随着网络中业务负载的进一步加重，DRSA协议与802.11协议的平均吞吐量性能开始分化.借助于ODHR时隙预留算法，DRSA协议可以在拥挤的网络环境和密集的业务环境下根据业务需求有效地协调各发送节点，高效地分配和利用空闲的时隙资源，在空间上形成有效复用，使平均吞吐量性能得到进一步提高.最终DRSA协议的平均吞吐量稳定在4×105bit/s水平，而802.11协议的平均吞吐量稳定在2.5×105bit/s水平.DRSA协议的吞吐量较802.11协议提高约60%.

图4 吞吐量对比仿真结果Fig.4 The performance comparison on throughput

3 结束语

根据建模分析和仿真验证，DRSA协议能够根据当前网络中各节点的业务负载情况，以完全分布式的方式按各节点的业务需求高效地为各节点分配时隙资源，而不依赖任何关于当前网络拓扑情况的先验信息，使得协议具有较强的适应性、健壮性和可扩展性.

[1]MOSCIBRODA T，WATTENHOFER R.Coloring unstructured radio networks[C]//Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures.New York，USA，2005:39-48.

[2]SAGDUYU Y E，EPHREMIDES A.On joint MAC and network coding in wireless Ad Hoc networks[J].IEEE Transactions on Information Theory，2010，53(10):3697-3713.

[3]SRINIVASAN P，RAJIV G.Distributed algorithms for coloring and domination in wireless Ad Hoc networks[C]//Proceedings of FSTTCS＇04.Chennai，India，2004:447-459.

[4]胡致远，郭建丁，王景，等.多接口无线mesh网络的信道时空分配[J].重庆大学学报，2011，34(2):26-31.HU Zhiyuan，GUO Jianding，WANG Jing，et al.Spatiotemporal channel assignment in multi-radio wireless mesh networks[J].Journal of Chongqing University，2011，34(2):26-31.

[5]RHEE I，WARRIER A，JEONGKI M，et al.DRAND:distributed randomized TDMA scheduling for wireless Ad Hoc networks[J].IEEE Transactions on Mobile Computing，2009，8(10):1384-1396.

[6]ZHU C X，CORSON M S.A five-phase reservation protocol(FPRP)for mobile ad hoc networks[C]//Proceedings of Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies.San Francisco，USA 1998:322-331.

[7]SAYADI A，WEHBI B，LAOUITI A.One shot TDMA-based reservation MAC protocol for wireless Ad Hoc networks[C]//Proceedings of Vehicular Technology Conference.Evry，France，2011:1-5.

[8]ZHU C X，CORSON M S.An evolutionary-TDMA scheduling protocol(E-TDMA)for mobile Ad Hoc networks[R].Baltimore:University of Maryland，2000.

[9]VALLATI C.Dynamic resources allocation in wireless mesh networks[C]//Proceedings of IEEE International Symposium on World of Wireless，Mobile and Multimedia Networks.Pisa，Italy，2011:1-3.

[10]LI Hongyan，VALAEE S.An efficient algorithm for time slot assignment in Ad Hoc networks[C]//Proceedings of 22nd Biennial Symposium in Commucications.Kingston，Canada，2004:225-227.

[11]XU Mingxia，ZHAO Minjian，SONG Zhengwei，et al.An on-demand and dynamic slot assignment protocol for Ad Hoc networks[C]//Proceedings of APCC＇06.Busan，Korea，2006:1-5.

[12]马柯，俞能海，杨福荣.EASA:一种分簇Ad Hoc网络高效自适应TDMA时隙分配算法[J].电子学，2010，38(7):1678-1682.MA Ke，YU Nenghai，YANG Furong.EASA:an efficient adaptive TDMA slot assignment protocol for clustered Ad Hoc network[J].Acta Electronica Sinica，2010，38(7):1678-1682.