移动Ad-hoc网络中无线跳频频率资源分配机制研究*

古稀林，王 超，冯志先，姜永广

（中国电子科技集团公司第三十研究所，四川 成都 610041）

0 引 言

移动Ad-hoc环境中大量使用无线传输设备，例如SRD（Soldier Radio Device），SRD通过无线电波相互通联，组成了灵活、庞大、复杂的用频网系[1］。典型移动Ad-hoc网络（Mobile Ad-hoc network，MANET）拓扑如图1所示，多个节点（NODE）通过SRW（Soldier Radio Waveform）实现分层组网，以满足节点间的互联互通需求。

图1 典型移动Ad-hoc网络拓扑示意图

跳频频率规划需要为各个子网分配跳频表号和网号，不同的子网可以采用不同频表，也可以采用相同频表，但需使用不同的网号来区分[2］，每个频表中存在若干个频率值（频点），与网号一一对应。针对采用同一频表的多个子网而言，可以将网号对应的频点视为起跳频点，不同的网号决定了子网拥有不同的起跳频点。子网之间通过组建同步正交网络[3-4］，使子网间的频率间隔始终保持一致，因此，在一定条件下，子网之间的频率间隔就等于起跳频点之间的间隔。

移动Ad-hoc网络中跳频频率资源规划存在以下几个方面的困难：

（1）通信需求多样，导致网络拓扑中组网关系十分复杂且多变，从而对频率规划求解模型的适应性提出较高要求。

（2）SRD工作频段窄，且SRD数量及子网数量往往较大，导致频率资源十分紧缺[5］，这也是多个子网采用同一个频表，并采用不同网号的主要原因。另外，某些子网也存在特殊需求，导致这些子网必须采用不同频表，因此，频率规划求解模型应具备多频表协同规划的能力。

（3）不同的频表可能具有不同的频点数量，从而对频率规划求解模型的扩展性提出要求。

（4）为了防止频率碰撞或干扰，要求子网间存在一定的频率间隔，特别是同节点内的多个SRD，相互之间影响较大。频率规划需要兼顾网络拓扑中所有节点内SRD的频率间隔，导致频率资源统筹规划难度大。

针对上述问题，本文以移动Ad-hoc网络中无线跳频频率规划为研究背景，将复杂网络的拓扑抽象出三种组网场景，并通过定义节点集、子网集、组网集，实现对复杂组网场景统一描述，以此为基础，提出一种无线跳频频率规划求解模型，实现多节点、多子网、多频表协同规划，一方面减少网间频率干扰，提高网络运行稳定性，另一方面降低频率统筹规划难度，实现频率规划过程自动化，提高频率规划效率。

1 SRD组网场景

实际应用中的网络拓扑较为复杂，一个节点（NODE）可能加入多个子网（MANET），这与节点内部的SRD数量及组网方式相关。如图2所示节点内部包含了3个SRD，说明该节点在某时刻最多能加入到三个不同的子网中。根据实际使用需求，节点内部可能存在以下三种组网场景。

图2 节点内部一台一网组成示意图

（1）一台一网场景（One SRD One MANET，OSOM）

OSOM场景是指节点内一个SRD最多加入一个子网。如图2所示的SRD1、SRD3分别加入了一个子网，SRD2没有加入子网。

（2）一台多网场景（One SRD Many MANET，OSMM）

OSMM场景是指一个SRD具备加入不止一个子网的能力。如图3所示，SRD1具备加入三个子网的能力，但某时刻SRD1只能加入到MANET1/MANET2/MANET3中的其中之一。此场景主要是为了满足一台多用的使用需求，SRD1可以按需切换通信信道以实现不同的通信需求。此场景提高了SRD的使用率，但无疑增大了频率规划的难度，因为需要根据入网情况可能会给一个SRD规划出多个频率值。

图3 节点内部一台多网组成示意图

（3）多台一网场景（Many SRD One MANET，MSOM）

MSOM场景是指节点内部存在多个SRD加入到同一个子网，如图4所示的SRD1和SRD2均加入MANET1。此场景主要是为了达到通信信道备份的目的，但在某时刻SRD1与SRD2不能同时工作，否则会导致频率干扰及通信环路问题。

图4 NODE内部多台一网组成示意图

上述三种场景互为补充，实际应用由三种基本场景组合而成。本文通过定义节点集、子网集、组网集，以对各种组网场景实现统一描述。

节点集：GNODE={NODE1,NODE2,NODE3,…}表示网络拓扑中的节点信息。

子网集：GMANET={MANET1,MANET2,MANET3,…}，表示网络拓扑中的子网信息。

组网集：GCONNECT={CONNECTMANET|MANET∈GMANET,…}表示网络拓扑中的组网信息。针对∀CONNECTMANET∈GCONNECT，CONNECTMANET={(NODE,SRD)|NODE∈GNODE,SRD∈NODE}

表示一个子网的入网信息，入网信息又由多个二元组(NODE,SRD)组成。例如：CONNECTMANET1={(NODE1,SRD1),(NODE2,SRD1),(NODE3,SRD2)}，表明节点NODE1的SRD1，NODE2的SRD1，NODE3的SRD2加入到子网MANET1。

2 频率规划算法

基于节点集、子网集、组网集，建立频率规划求解模型，并将实际应用对频率的相关要求转化为算法的约束条件，通过遍历所有的频率资源，不断尝试为所有子网分配频率，直至满足约束条件为止。

2.1 算法描述

频率资源用频率集来表示，频率规划算法的输入描述如下。

（1）组网集：GCONNECT

（2）频表集：GFTBL={FTBL1,FTBL2,…}

（3）子网与频表映射：MAP:MANET➔FTBL

频表集包含了若干个频表，根据实际应用需求维护子网与频表的映射关系，支持不同的子网选择使用不同的频表，达到多频表协同规划的目的。不同频表可能存在不同数量的频点，因此在理论上算法不限制频表中频点的数量，以使算法能适应多种规格的频表应用。

为防止频率干扰，子网之间存在频率间隔要求，主要包括两个方面：一是不同子网应具有不同的频率；二是每个节点加入的子网两两之间的频率间隔应大于一个固定值。形成的算法约束条件如下。

约束条件一：∀MANETu∈GMANET，∀MANETv∈GMANET，u!=v，要求FreqMANETu!=FreqMANETv，其中，FreqMANETu表 示MANETu的 频 率，FreqMANETv表 示MANETv的频率。

约束条件二：∀NODE∈GNODE，令节点内所有SRD加入的子网集合为GMANET-OF-NODE，显然存在GMANET-OF-NODE⊆GMANET。针对∀MANETu∈GMANET-OF-NODE，∀MANETv∈GMANET-OF-NODE，且u!=v，要求|FreqMANETu-FreqMANETv|＞K，K为一个固定值。

若算法获得一个解，表示在给定频率资源和约束条件下能为每个子网分配出频率资源，得到集合{FreqMANET|MANET∈GMANET}，其中，FreqMANET为一个子网的频率；否则，算法无解。

2.2 频率规划求解模型

求解模型如图5所示，以图论中的树作为算法求解的基础，求解过程采用回溯法，为了减少计算时间，通过深度优先策略在构建树的同时实现求解。

图5 频率规划求解模型

当构建一个树节点时，需要先判断当前约束条件是否成立，若约束条件成立，则构建此树节点，并继续纵深至下一层；若约束条件不成立，则无法创建该树节点，此时就回溯至上一层节点。

树的节点（TNode）用一个三元组表示：TNode={MANET，FTBL，FPoint}，表示子网MANET采用了频表FTBL中的频点FPoint为频率值。树的根节点（Root Tree Node，RTNode）是个空节点，RTNode={NULL，NULL，NULL}，它仅用于模型建立与算法计算。

树的深度取决于子网集GMANET中元素的数量，GMANET中每个元素与树的一个层级相对应，即同一深度的树节点表示一个子网的不同频率取值，如图5中所示，树深度为2的节点均表示MANET1的不同频率取值，树深度为3的节点均表示MANET2的不同频率取值，依次类推。

通过子网与频表的映射关系MAP，可映射出每个子网应采用的频表，频表中的所有频点（FPoint）就是该子网可能的频率取值，因此，某深度的树节点最大个数取决于该子网对应频表的容量。

由于资源总量有限，而子网数量较大，往往多个子网共用频表，根据约束条件，子网的频率取值不能相同，因此，为一个子网分配频率时，需要判断该频点是否已经被使用。

算法执行结束时，存在两种情况，一是算法获得满足约束条件的一个解后立即退出，此时GMANET中所有子网均分得频率，且树的一个分支到达叶子节点，树的深度为GMANET中子网的数量加1；二是遍历完成所有可能情况后算法终止，此种情况表明算法无解，进而表明在给定约束条件下，当前的频率资源无法满足网络拓扑需求，因此，此时需要对频率资源进行调整或适当放宽约束条件。

算法执行流程如图6所示，基本步骤描述如下：

第①步：创建树的根节点RTNode，令算法的当前处理节点为Current，初始情况下Current=RTNode；

第②步：尝试为Current创建子节点X，根据X={MANET，FTBL，FValue}，需先确定出X对应子网，通过遍历子网集GMANET，获取出一个子网作为节点X对应的子网，进入下一步；若子网集GMANET遍历结束，进入第⑧步；

第③步：根据上一步获取的子网，通过MAP映射出该子网采用的频表索引，基于频表索引在频表集GFTBL中获取该频表的所有频点；

第④步：通过遍历依次获取出上一步所得频表中的每个频点，遍历过程需要跳过已经被其它子网占用的频点。若该频表遍历结束，表明无法给该子网寻找到一个合适的频点，进入下一步；否则，获取到该频表的一个频点，进入第⑥步；

图6 频率规划算法流程

第⑤步：判断当前节点Current的父节点（设为F）是否为NULL，若F为NULL，表明此时Current=RTNode，即算法无法为RTNode创建出子节点，进入第⑧步；若F不为NULL，回溯至树的上一层，即令Current=F，进入第②步，继续尝试为Current创建子节点；

第⑥步：针对遍历所得的一个频点，判断若将此频点分配给当前MANET，是否满足算法约束条件，若不满足，进入第④步尝试下一个频点；若满足则进入下一步；

第⑦步：创建树节点X，使X为Current的子节点，并更新Current为X，继续为Current尝试创建子节点，进入第②步。

第⑧步：算法结束。分为两种情况，一是若子网集中的所有子网均分配得到一个频率值或树的深度等于子网集中元素数量加1，则表明算法获得了一个解；二是表明频率资源不足，无法获取一个满足约束条件的解。

3 算法时间复杂度分析及优化建议

3.1 算法时间复杂度分析

考虑算法最坏的情况是：

（1）假定子网集中的子网个数为N，每个子网采用不同的频表，每个频表中频点个数最大为M；

（2）算法无解且穷尽了所有可能的情况，每个树节点均有M个子节点，整棵树是个完整M叉树，如图7所示。

图7 算法复杂度分析

遍历完整棵树，算法的时间复杂度为O(M+M2+M3+…+MN)=O(MN)，当频点个数M及子网个数N较大，且在给定条件下算法无解导致算法完整遍历整棵树时，将需要大量的计算时间。

3.2 算法流程优化

可以从两个方面入手对算法进行优化，一是优化节点入网集GMANET-OF-NODE以降低频率资源开销，有利于为更多的子网规划出频率资源；二是通过优化子网集GMANET中的元素顺序，在算法存在解的情况下，有利于较早获得算法的解，缩短算法执行时间。

（1）优化节点入网集

以图3为例，SRD1加入了MANET1、MANET2、MANET3，SRD2加入了MANET4，SRD3加入了MANET5。当为上述子网分配频率资源并进行约束条件判断时，存在两种情形。

情形一：

该节点的入网集为：

GMANET-OF-NODE={MANET1,MANET2,MANET3,MANET4,MANET5}，假设GMANET-OF-NODE中每个子网对应的频率为：G1={FreqMANET1,FreqMANET2,FreqMANET3,FreqMANET4,FreqMANET5}。

情形二：

上文已经提及，某时刻SRD1只能加入三者MANET1、MANET2、MANET3之一，因此该节点的入网集GMANET-OF-NODE只能是下面三种可能之一：

可能一：

GMANET-OF-NODE={MANET1,MANET4,MANET5}

可能二：

GMANET-OF-NODE={MANET2,MANET4,MANET5}

可能三：

GMANET-OF-NODE={MANET3,MANET4,MANET5}

上述三种可能对应的频率分别为G2、G3、G4：

G2={FreqMANET1,FreqMANET4,FreqMANET5}

G3={FreqMANET2,FreqMANET4,FreqMANET5}

G4={FreqMANET3,FreqMANET4,FreqMANET5}

令：

J1=G1中两两之间频率间隔大于固定值K；

J2=G2中两两之间频率间隔大于固定值K；

J3=G3中两两之间频率间隔大于固定值K；

J4=G4中两两之间频率间隔大于固定值K。

比较上述两种情形，J1与（J2&J3&J4）均能满足算法的约束条件。从算法实现的难易角度而言，J1较（J2&J3&J4）容易；但从对频率资源要求角度而言，J1比（J2&J3&J4）苛刻一些，因为（J2&J3&J4）并不要求FreqMANET1、FreqMANET2、FreqMANET3两两之间的频率间隔。因此，算法实现建议采用（J2&J3&J4）来判断约束条件满足情况。

（2）优化子网集中元素顺序

算法的求解过程是根据约束条件的满足情况进行回溯，减少回溯次数，有利于减少算法执行时间。导致回溯的原因是约束条件无法满足，无法创建树的节点，需要回溯至父节点重新利用频表中的其它频点进行尝试。

通过约束条件可知，发现节点入网集GMANET-OF-NODE中元素数量越大，该节点对频率资源的要求就越苛刻，因此，根据节点入网集的元素数量进行排序，使算法先处理数量较大的节点入网集中的子网。例如，节点NODE1、NODE2、NODE3的节点入网集如下：

NODE1：GMANET-OF-NODE1={MANET1,MANET4}

NODE2：GMANET-OF-NODE2={MANET1,MANET2,MANET3}

GMANET-OF-NODE3={MANET2}

按照节点入网集元素数量多少的排序结果为：NODE2、NODE1、NODE3，其中，NODE2对频率资源要求最高，因为需要满足三个子网之间的频率间隔。

根据排序结果，依次将各节点入网集中的子网加入到子网集，得到GMANET={MANET1,MANET2,MANET3,MANET4}。根据子网集中元素顺序可以看出，NODE2的节点入网集中的子网会优先得到处理（位置靠前），此举可以在构建求解树过程中让回溯操作大概率地发生在深度较小的树节点，从而减少在深度较大的树节点发生回溯操作的几率，即让需要发生回溯的操作尽可能地提前，使算法减少执行时间。

4 结 语

本文以移动Ad-hoc网络的无线跳频频率规划为研究背景，针对组网场景复杂多变、多频表混合使用、频表中频点数量不统一、子网间存在频率间隔要求等问题，本文完成工作如下：

（1）将网络拓扑中复杂多变的组网关系，抽象出三种基本的组网场景，并通过定义节点集、子网集、组网集，实现对各种复杂组网场景统一描述。

（2）构建频率规划求解模型，先后阐述了算法输入、约束条件、求解过程、算法输出，实现了多节点、多子网、多频表资源协同规划，降低了频率资源统筹规划难度，提升了频率规划效率。

（3）基于算法流程，通过优化节点入网集以节省频率资源开销；通过优化子网集中元素顺序，有利于减少算法执行时间。

本文算法从理论上回答了在给定频率资源和约束条件下，能否为网络拓扑中所有子网分配出频率资源的问题。并分析了算法的时间复杂度，指出当算法无解时可能会耗费大量的计算时间，因此，如何结合实际具体应用，优化算法求解过程，减少算法求解时间是下一步研究的主要工作。