基于邻居监测的时隙动态复用算法

田永春

(中国电子科技集团公司第30研究所，成都 610041)

0 引言

在以无线通信为主的高动态战术通信环境中，一般采用多跳的Ad hoc网络结构，没有一个可靠的中心控制点，节点间分布式协调困难，存在隐藏终端和暴露终端等问题，导致进行全局资源优化的难度较大。较低的通信带宽和低下的信道利用率一直是战术通信发展的主要瓶颈，因此动态信道分配与复用技术一直是战役/战术通信系统的主要研究难点。

战术业务类型通常可分为周期性和突发性业务，为了保证周期性业务的及时、可靠传输，要求节点必须具有无冲突的周期性信道资源;而为了满足突发性业务及大报文业务的及时传输，要求节点具有可动态使用的额外信道资源。这给信道分配带来了新的困难。

为了满足战术业务的传输需要，提高信道资源利用率，有两个基本解决途径:一是增加单个节点可用信道资源，在战术环境下，该途径会带来较大的代价;二是提高信道的利用率，结合多种信道分配方式，在保证节点一定固定信道资源的同时，进行资源的动态复用，充分利用战术通信网的多跳特性，进行空间复用。

信道分配方式主要可以分为竞争协议和预留协议[1]。由于战术环境对信息传输的及时性和可靠性要求较高，因此竞争协议不能作为主要的信道接入手段;FDMA、CDMA均无法有效避免隐藏终端和暴露终端等问题，采用固定分配TDMA方式时，又存在效率较低等问题;而基于波形成形技术的信道空间复用技术还在研究阶段[2]。

将单信道固定分配TDMA方式与动态时隙竞争协议结合起来，通过信道监测与节点的邻居关系，实现信道的空间复用，试图以较小的代价与算法复杂度，获得较高的信道利用率。第1节将对算法模型进行描述，并在第2节对算法进行仿真分析，最后对算法进行总结。

1 算法描述

1.1 算法前提

本文的算法以单信道固定分配TDMA协议为基础，假设信道具有较高的通信速率，能进行较精确的时间和跳频同步，支持TDMA和CSMA方式，支持动态信道占用。

为了满足周期性和突发性业务的传输需要，采用TDMA+CSMA组合的信道访问方式，将信道划分为时帧T，每个时帧包括固定分配时隙FS和竞争时隙CS，则T={FS CS}。帧结构如图1所示。

图1 信道帧结构示意图

其中FS的时隙数量与网内节点数n一致，每个节点固定占用一个时隙，用于节点初始组网和周期性信息的传递;CS的时隙数量c主要作为紧急突发业务的传输及临时入网用户的随机接入信道。为了提高突发业务传输速度，CS可与FS进行交错排列。复用算法针对整个时帧T进行。

每个节点Ni保持一个信道监测矢量CULi=(s1，…，sn，…，sn+c)i，其中每个 sj，j=1…(n+c)代表节点Ni所监测到的信道状态。在统一时隙分配协议(USAP)[3]中，sj有三种状态:发送、接收、邻居传输或冲突。为了简化协议，只设定两种状态，时隙忙和闲。假如节点Ni监测到时隙忙，即该时隙已经被占用，则sj=1;否则sj=0。因此每个sj用1 bit就可以标识。

信道复用是为了在有效避免隐藏终端与暴露终端等问题的情况下，最大限度地利用信道资源，避免冲突。隐藏终端与暴露终端还可根据发送或接收再进行细分[4]，其中隐藏发射终端和暴露接收终端主要引起接收冲突，而隐藏接收终端与暴露发送终端主要引起资源浪费。为了保证信息的可靠传输，必须避免冲突;但为了解决隐藏接收终端与暴露发送终端引起的资源浪费，会给算法带来很大的复杂度和动态性，所引起的开销会抵消所带来的好处，因此本算法对这部分资源不进行利用。

1.2 复用算法

在网络初始化时，为每个节点Ni指定一个时隙FSi作为固定的时隙，如果在复用后发生冲突时，其余节点应进行退避。节点在该时隙上进行初始化，建立邻居关系表和路由表。在网络初始化完成后，根据监测到的信道状况生成 CULi，并进行CULi的维护与更新。当节点检测到某个时隙被使用后，将对应的位状态置1;如果检测到某个使用的时隙在某个时间内一直处于空闲状态，则将对应的位状态置0。生成 CULi后，节点即可进行信道复用。

复用算法拓扑示意图，如图2所示。进行分析可以发现，节点1与节点11～14无论是发送还是接收，都不会互相影响，同样，节点2与节点9、10、11、14等都不会互相影响。因此节点1可以复用节点11～14的时隙，达到类似空分复用的效果。

图2 复用算法拓扑示意图

根据上面的分析，可推得如下结论。

设节点Ni与Nj之间的跳数为h，则节点Ni可以复用的时隙集合RSi为

式中，FSj是节点Nj的固有时隙。

由于竞争时隙CS也可以与FS一样进行信道复用，一般地，设节点Ni的邻居节点集合为Nbi，则可推得RSi为

为了保证每个节点都能获得公平的复用机会，在获得可复用时隙集合RSi以后，节点Ni并不立即占用该集合中的所有时隙，而是从中选择出Tr个时隙进行占用。每个节点的Tr与节点的优先级、业务量大小有关。在某个节点进行复用时，其邻居节点将冻结其他的复用请求，在同时进行复用时，高优先级节点首先进行复用。在首次复用完成后，如果时隙资源仍不能满足节点传输需求，则进行第二次复用。选择的时隙位置应尽可能地间隔均匀，降低突发业务的接入时延。

采用该算法后，在初始化过程中，在一个时帧内每个节点只有一个固有时隙(与固定分配TDMA一样)，在完成复用后，每个节点在一个时帧内将获得多个动态复用时隙。

1.3 算法实现

从上述算法可设计出算法的实现。为了实现对空闲时隙的复用，每个节点或新加入的节点在通信过程中持续监视信道。假如节点需要增加时隙以满足业务传输的需要，它首先发送复用请求(Req_resume)，邻居节点将传输它当前的信道监测矢量CULi给请求的节点，进行“位或”运算后，选择Tr个空闲时隙进行占用，并向邻居发送占用消息(Slot_Occup_NUM)，指定占用的时隙位。假如在移动过程中，有节点发现了冲突，则发送否认消息(NAK_NUM)，所有占用了否认消息内指示时隙的节点将释放这些时隙，并重新进行复用。如果冲突时隙是自己的固有时隙，则拒绝释放。节点在占用了除固有时隙以外的时隙时，如果节点业务量较小，应释放不用的时隙资源，发送释放消息(Slot_Rel_NUM)，邻居节点更新自己的CULi。

算法实现流程如图3所示。

图3 动态时隙占用

2 仿真结果

为了对算法的复用效果进行分析，建立仿真场景进行分析。场景设置如下:节点个数100个，均匀随机分布在覆盖范围内，信道设为UHF信道，通信距离设置为10 km，每个时隙长度设为16 ms，竞争时隙CS个数设为0，每次最大复用时隙个数Tr=10，可重复复用。因此一时帧长度就为1.6 s，FS个数为100。针对静止时信道复用情况、信道接入时延以及运动时时隙复用的变化情况进行仿真，仿真结果如图4所示。

图4 静止时动态时隙占用情况

由图4可见，在静止时，节点复用时隙的个数与节点所处的位置、邻居关系及复用的时机有较大的关系。不同的位置分布与不同的起始复用节点，节点可复用到的时隙数量是有差异的。而不同的节点分布密度对复用的时隙数量有较大的影响，越密集复用率越低，在本次仿真中，当节点分布在60 km×60 km时，节点平均复用时隙748/100=7.48个;在100 km×100 km时，节点平均复用时隙1815/100=18.15个;在120 km×120 km时，节点平均复用时隙2112/100=21.12个。而不进行复用时，每个节点仅有1个时隙。由此可见，复用对提高信道利用率的提高效果显著。

信道平均接入时延的变化情况，如图5所示。在不复用时，节点的平均信道接入时延在0.69 s左右，复用后减少到0.44 s左右。可见复用也可降低信道接入时延。

图5 静止时信道平均接入时延

为了分析运动过程中信道复用情况，设置100个节点分布在60 km×60 km，运动速度设为5～50 km/h，平均30 km/h，不同方向运动速度有较大差异，用于模拟战术使用场景。节点在运动过程中会经历稀疏到稠密然后再稀疏的过程。仿真结果表明，在节点运动过程中，网络平均时隙复用个数随着节点的分布密度而变化。当节点较密时，平均复用个数下降，但当节点较稀疏时，平均复用个数将增加。由于篇幅限制，这里不详细列出。因此，本文的算法在网络分布较稀疏时，空间复用效果更加明显，在动态过程中，算法也有较好的效果。

3 结语

本算法适应于以时隙为基本传输单元的战术电台，结合了固定分配TDMA与动态时隙分配的优势，在保证每个节点都获得周期性时隙资源的同时，尽可能进行信道复用，保证每个节点在固定时隙之外，获得额外的时隙资源。仿真表明，复用对节点可用资源的提高效果是明显的。算法对战术通信的特点也能很好的适应，通过分配时隙数量、优先级、复用次序及单次最大复用时隙数等，可以保证重要的或大业务量的节点获得更多的时隙，具有较好的适应能力。

该算法的缺点是在动态过程中每个节点获得的时隙资源是波动的，不同的复用时机与次序会影响复用效果，先复用节点选择的时隙位置也会影响其他节点的复用效率，这也是本算法下一步要解决的问题。算法没有对隐藏接收终端与暴露发送终端所引起的资源浪费进行利用，因此复用效率是次优的，但算法简单，便于实现。

[1]郑相全，等.无线自组网技术[M].北京:清华大学出版社，2004.

[2]刘强，吴炜霞，苏旸.波束成形技术在超短波电台中的应用研究[J].中国电子科学研究院学报，2010，5(4):30-33.

[3]YOUNG C D.USAP Multiple Access:Dynamic Resource Allocation for Mobile Multihop Multichannel Wireless Networking[C]//Proceedings of the IEEE MILCOM 1999 Conference，Atlantic City，New Jersey，1999:271-275.

[4]GARCES R，GARCIA-LUNA-ACEVES J J Collision Avoidance and Resolution Multiple Access for Multichannel Wireless Networks[C]//Proc IEEE INFOCOM 2000，Tel-Aviv，Israel，2000.