定向通信网络资源分配算法设计及仿真

李莹 李婥

【摘要】 为了提高定向网络中的资源利用率，以及增强资源随着业务需求及网络状态变化的快速调整能力，研究了定向通信网络特点以及资源分配算法的基本思想及关键设计要点，设计了一种分布式资源分配算法。该算法合理调度时间、频率、空间和硬件通道等资源，使得分配结果能够实时的满足不同链路的传输速率需求以及时延需求。最后，通过仿真测试的方法验证了算法可以实现在多变网络状态下的资源动态调整，满足定向网络中多种业务的传输需求，适合应用在需求多变的定向网络中。关键词：定向网络；资源分配；分布式；多业务需求

RESOURCE ASSIGN ALGORITHM DESIGN AND SIMULATION FOR DIRECTIONAL COMMUNICATION NETWORKS Li Ying①， Li Chuo②（①Southwest China Institute of Electronic Technology， Chengdu Sichuan 610036； ②China Academy of Electronics and Information Technology， Beijing 100041）

Abstract：In order to improve the resource utilization rate of the directional network， and enhance the ability to adjust the resources along with the service requirement and network state change， the characteristic of directional communication networks and the main principle of resource assign algorithm are studied. A distributed resource assign algorithm is designed. The algorithm can reasonably schedule the time， frequency， space and hardware resources， so that the assign results can meet the requirements of different link on transmission rate and time delay. Finally，the algorithm can realize the dynamic adjustment of resources in the changing network state by the method of simulation， which can meet the needs of multi service transmission in the network.

Key words：Directional networks； Resource assign； Distributed； Multi service requirement

由于定向天线具有波束窄、增益高、传输距离远、隐蔽通信等诸多优点[1]，在无线通信网络上的应用越来越广泛，采用定向天线通信的网络被称为定向通信网络。对于实时性要求比较高的通信网络，一般优先考虑TDMA接入方式[2]。其中，动态时隙分配TDMA具有更好的信道利用率及不同业务类型的能力并支持QoS[3]。在选择TDMA接入方式的定向通信网络中，可以利用定向天线窄波束的辐射特性，多对节点之间在同一个时隙内同时进行数据收发，实现时隙资源在空间维度的复用，即空分复用，提高网络的吞吐量和时隙的利用率。由于网络中的拓扑以及业务的QoS需求在不断变化，因此，如何动态的高效分配网络资源是定向通信网络亟需解决的关键问题。本文主要针对TDMA定向通信网络的动态资源分配算法展开研究。

一、资源分配算法设计原则

1.1 概述

TDMA网络中，动态资源分配算法的基本思想是：各成员入网后，当业务量调整时能自动调整各资源占有状态，从而提高了整个网络的资源利用率[4]。本文描述的定向通信网络中，可以进行动态分配的资源包括四类，分别是时隙资源、频率资源、空间资源以及成员的硬件通道资源，同一时隙内多个成员之间的空分复用如图1所示。

基于TDMA的定向通信网络的动态资源分配算法中，网络成员需要根据当前业务对传输速率以及通信时延的需求，在时隙资源的基础上合理调度其他资源，获得时隙频率分配表，使得该分配表在满足业务需求的前提下，最小化全网的资源消耗。资源分配算法原理图如图2所示。

1.2 设计目标

由于系统中存在四类可分配资源，每类资源的可用集合大小不同，因此每占用一个资源的消耗系数也不同。资源分配算法的求解目标总结为如下两点：

分配结果误差：定义分配结果误差来表示分配结果与需求之间的差距。显而易见，分配结果误差越小越好，为0则为最优。分配结果误差包含传输速率分配结果误差和时延分配结果误差两部分。

全网资源消耗：为每类资源配置不同的资源消耗系数，该系数根据资源的紧缺程度来确定，紧缺资源的消耗系数高。显然全网资源消耗越低越好。

综上，资源分配算法的设计目标为在确保资源分配误差最低的情况下，最小化全网资源消耗。算法计算流程以该目标为依据，进行资源分配计算。

1.3 控制策略

根据网络中担任资源分配计算职责的成员的不同，可以分为集中式动态资源分配算法和分布式动态资源分配算法。集中式算法通过中心控制节点收集全部成员的需求信息，再根据需求计算资源分配，最后将分配结果分发给每个成员。分布式算法中每个节点仅需评估本节点的需求信息，再根据局部的资源占用情况计算新的资源分配，新的资源分配结果与一跳邻居进行局部干扰排除，最后完成资源占用确认[5]。由于仅需要在局部邻居之间保持资源的互斥性，与全局的其他成员无关，而且分布式算法的抗毁性好，因此本文的算法选择分布式的控制策略。

分布式的控制策略中，每个成员为自己的需求负责，进行资源分配计算，与局部邻居协商完成资源分配确认，最后实现资源占用，流程如图3所示。

二、资源分配算法流程

2.1 触发条件

由资源分配算法原理图可以看出，当网络中的可用资源不变时，业务需求的变化将导致现有资源占用与新的业务需求无法匹配，即触发进行新一轮的资源分配。资源分配的触发条件如下：

网络的拓扑结构变化：部分消息的发送路径发生改变，使得某条链路上的业务需求变化，与原占用资源无法匹配；

节点的始发业务需求变化：消息发送路径上业务需求变化，与原占用资源无法匹配；

节点间相对位置关系变化：空间复用条件发生变化，使得某条链路必须放弃部分资源占用，其可用资源减少，与原业务需求无法匹配；

因此，节点在网络运行中仅需周期的评估需求与可用资源是否匹配，若不匹配，则启动资源分配算法计算。

2.2 资源分配计算

当满足资源分配的触发条件时，成员将在本地启动资源分配计算。

资源分配算法的输入包含网络拓扑、业务需求和节点位置三个部分。

网络拓扑：网络拓扑为节点两跳范围内的拓扑。假定网络中的最大成员数为N，则网络拓扑用3个维的矩阵topo表示。每个维的矩阵中，行号表示发送节点序号，列号表示接收节点序号，由于采用定向天线通信，每个节点配置多副定向天线。每个矩阵中的元素的含义如下：若矩阵中的元素为0，则表示发送节点与接收节点之间不存在链路，否则，第1个矩阵的元素表示发送节点使用的天线序号，第2个矩阵的元素表示接收节点使用的天线序号，第3个矩阵的元素表示发送节点与接收节点之间的通信速率。

业务需求：由于网络中采用定向链路，因此需求为每条链路的业务需求。分为两类，一类是业务传输速率需求，一类是业务传输时延需求。分别采用维矩阵和表示。行号表示发送节点序号，列号表示接收节点序号，矩阵中的元素表示发送节点到接收节点的链路上的速率需求和时延需求，单位均为时隙数。

节点位置：节点位置为两跳范围内节点的位置信息，用一个维的矩阵pos表示，行号表示节点序号，列号表示位置信息序号，其中第1列表示该节点的经度，第2列表示该节点的纬度，第3列表示该节点的高度。

资源分配算法的输出为时隙频率分配表，假定网络的循环周期为M个时隙，则采用维的矩阵ts来表示，即M个维矩阵。第t个维矩阵表示时隙t内的频率分配。行号表示发送节点序号，列号表示接收节点序号，矩阵中的元素表示发送节点到接收节点的链路上分配的频率序号。

在以TDMA为基础的定向通信系统中，节点仅考虑在同一个时隙内合理的调度频率、空间和节点的收发通道，复用的多条链路需要避免如下三种冲突：

节点收发通道冲突：如果两条链路之间存在一个共用的节点，且共用节点在两条链路上使用相同的收发信道，则存在冲突；

频率冲突：如果两条链路之间存在一个共用的节点，且共用节点在两条链路上使用不同的收发信道，但已无空闲频率分配给新增链路，则存在冲突；

空间冲突（干扰冲突）：两条链路之间不存在共用节点，根据节点位置，收发天线之间的角度以及定向天线增益等计算一条链路的发送信号对另外一条链路的接收节点的干扰，若干扰导致信噪比低于解调门限，则存在冲突。

按照实现目标，资源分配计算方法描述如下。

取出本节点的全部待分配资源的链路，根据每条链路的传输速率分配需求slot_cnt_require，把每个链路的分配机会按照需求均匀穿插排列，形成一个分配链路集合A。

确定链路（a，b）在时隙s内的可用频率集合的方法：全部可用频率集合，除掉时隙s内全部已分配链路占用的频率后，剩余的全部频率集合。

确定链路（a，b）在时隙s内是否可空分复用的计算方法：链路（a，b）选择临时频率后，计算其与时隙s内全部已有链路（c，d）之间的相互接收信号干扰，接收信号电平均在解调门限之上，则认为（a，b）可以在时隙s内复用。

对于集合A中的某一条链路（a，b），资源分配流程如下：

确定链路（a，b）的分配时延delay：取slot_cnt/ slot_cnt_require和delay_require的最小值。其中slot_cnt为资源分配循环周期内时隙个数，delay_require为该链路的时延需求。

确定链路（a，b）的第一个分配时隙：选择的优先顺序为[1，delay]内的第一个空时隙，[1，delay]内第一个空分复用时隙，[delay+1，slot_cnt]内第一个空时隙，[delay+1，slot_ cnt]内第一个空分复用时隙。若分配失败，则删除集合A中全部链路（a，b），链路（a，b）本次资源分配结束。

确定链路（a，b）的后续分配时隙：

确定ts0，tsi：ts0为上一个已分配时隙，tsi为ts0在循环周期内后移delay个时隙；

查找第一个空时隙tsj：选择的优先顺序为：先从tsi向前选择，再从tsi向后选择；

查找第一个复用时隙tsk：选择的优先顺序为：先从tsi向前选择，再从tsi向后选择；

分配时隙：从tsj和tsk中选择一个时隙分配给链路（a，b），首选满足时延需求的，若没有则选择没有满足时延需求的；同样条件下，首选空时隙，若没有则选择复用时隙。

集合A全部链路分配结束后，检查每个链路的分配结果，若最后一个分配时隙和第一个分配时隙之间的时隙间隔大于时延需求，则继续按照步骤（4）的c）的方法，继续完成时隙分配，直至最后一个时隙与第一个时隙的时隙间隔满足链路的时延需求或者无资源可分为止。

2.3 资源分配确认与占用

在资源分配节点完成资源分配计算后，进入资源分配确认及占用阶段。

资源分配节点将分配结果分发给邻居；

邻居收到新的资源分配结果后，将其与本地的资源分配结果比较，并将发生冲突的资源回复给资源分配节点；

资源分配节点收到冲突资源后，将其删除，确认最终的资源分配结果。并将该结果分发给全部邻居。资源分配节点完成最终的资源分配结果确认；

资源分配节点与其邻居同时完成对本次资源分配结果中资源的占用。

三、 仿真分析

为了验证资源分配算法的合理性及算法性能，采用Matlab仿真软件进行建模仿真。仿真采用固定拓扑结构，传输速率需求固定，如表1所示。拓扑结构如图4所示。

在上述拓扑结构和传输速率需求的基础上，本文仿真了10个场景，每个场景中时隙分配周期不同，以及时延需求不同，如表2所示。

为了验证算法的性能，统计以下仿真指标：

时延需求满足百分比：链路的满足时延需求的时隙数除以该链路总分配时隙数

传输速率需求满足百分比：链路已分配时隙个数除以总需求时隙数。

资源分配结果误差：为每条链路的传输速率分配结果误差和时延分配结果误差之和的平均值。其中，传输速率分配结果误差为需求速率与实际速率之差的绝对值；时延分配结果误差为每两个分配时隙之间的时隙间隔与时延需求之差再求和的平均值。

全网资源消耗：全网已分配资源的消耗系数之和。网络中四个资源搭配的资源消耗系数如下：Cost_time =0.2；Cost_freq=0.4；Cost_space = 0.05；Cost_txrx=0.05。

10个仿真场景的统计结果如下所示。图5和图6给出了四个场景的传输速率需求满足百分比和时延需求满足于百分比。10个场景仿真结果中，除循环周期为50个时隙的场景之外，需求满足百分比均在100%以上。若定义时隙需求数与循环周期内时隙数的倍数为时隙复用率需求，则循环周期为50个时隙的场景下，仅考虑传输速率需求，时隙复用率需求即达到6.86，再结合时延需求，时隙复用率需求更高。本文算法在考虑时延和复用条件等约束条件下，实际时隙复用率达到4.76，链路BF的资源分配结果未能完全满足需求。

图7和图8分别给出了10个场景的资源分配结果误差和全网资源消耗。本文算法设计中将资源分配结果误差最小，全网资源消耗最小作为设计原则，通过仿真统计可以看出，算法在资源分配结果误差和全网资源消耗方面的性能。

四、结语

本文设计的定向网络资源分配算法为分布式算法，通过仿真结果可以看出，各成员仅需根据其本地及邻居的资源分配状态以及本地的业务需求作为输入，进行资源分配计算，再与邻居完成资源分配确认，最终实现资源占用， 全部采用局部信息交互，无需全网广播，因此更适合于大型网络中应用，可扩展性强，且开销较低。此外，该算法的目标为确保资源分配误差最低的情况下，最小化全网资源消耗，通过仿真表明，算法可以实现在多变网络状态下的资源动态调整，满足定向网络中多种业务的传输需求。

参 考 文 献

[1]王锦江，王玉冰，尹忠海.航空作战平台定向天线通信网络构型效能评估[J].空军工程大学学报（自然科学版），2013， 14（2）：61-65

Wang Jin-jiang， Wang Yu-bing， Yin Zhong-hai， Combat Aircraft Directional Antenna Communication Network Formation Efficiency Evaluation[J].JOURNAL OF AIR FORCE ENGINEERING UNIVERSITY（NATURAL SCIENCE EDITION），Apr.2013，Vol.14 No.2：61-65.

[2] 闫鲁生，王涛，李威.一种基于 多天线的动态TDMA协议仿真研究[J].通信技术，2011，44（12）：107-110YAN Lu-sheng， WANG Tao， LI Wei， Simulation Study of Multi-Channel Dynamic TDMA Protocol[J]， Communications Technology， 2011， Vol.44， No.12： 107-110.

[3] 郝东.无线AdHoc网络定向接入与空间复用机制设计[D].北京邮电大学， 2012Hao Dong， Directional Access and Spatial Multiplexing Mechanism Design for Wireless Ad Hoc Networks[D]， Bejing University of Posts and Communications， 2012

[4] 任浩，毛玉泉，李波.适用于link22超网结构的时隙分配算法[J].火力与指挥控制，2011，36（12）：160-163REN Hao， MAO Yu-quan， LI B，A Time-Slot Assignment Scheme Suitable for Link22 Super Network[J]， Fire Control &Command; control，De c，2011，Vol.36，No.12：160-163

[5] 王文政.战术数据链时隙分配协议及其仿真研究[D]，国防科学技术大学，2010Wang Wen-zheng， Study on Slot Assignment Protocol and Its Simulation for Tactical Data Links[D]， National University of Defense Technology，2010