一种基于最小生成树的无线多跳网络信道分配算法

引言

在无线多跳网络中，包括无线自组织网络、无线mesh网络和无线传感器网络，各节点既可以作为数据的终端节点，也可以是网络的路由节点。无线链路动态、时变和丢失特性，导致无线链路质量较差且稳定性较低，这对提高无线多跳网络的吞吐量和传输可靠性提出了挑战顽。

1信道分配

移动通信系统发展至今信道分配技术一直都是热门话题,一个好的信道分配算法可以在特定的服务等级下(包括链路质量,新呼叫阻塞概率和切换阻塞概率)产生很高的频谱利用率。所谓信道分配是指在采用信道复用技术的小区制蜂窝移动通信系统中，在多信道共用的情况下。为每个小区的通信设备安排多少可用信道。信道分配的目的是如何使频谱利用率更高,信道分配的方式主要有三种：固定信道分配、动态信道分配和混合信道分配。

图1所示是信道分配技术的一般方案图。

固定信道分配(FixedChannelAssignment，FCA)就是把所有的信道分成几个组，每一组固定地分配给某个小区。固定的信道分配策略在小区业务量小的时候会造成资源浪费,同时由于资源的平均分配会使得业务量大的小区通话阻塞率高。但是可以采用多种从相邻小区借用信道的方法降低这些阻塞概率。其中最基本的方法便是简单的借用，即移动台能从相邻小区分配到一个信道。一旦一个信道被借用，所有在共道复用距离内的其他小区将被禁止使用这个信道。这在大业务量的情况下资源效率将会降低，信道利用率甚至不如FCA。利用混合借用机制可以部分地解决这类问题。混合信道分配是把分配给一个小区的信道分成两组：小区自己所使用的信道为一组，可以被借用的信道为另一组。

动态信道分配［4］(DynamicChannelAssignment，DCA)把所有的信道组成一个缓存池，当邻近小区的信道未分配时,可以借用给别的小区使用，以达到资源的动态分配，提高资源利用率。DCA可以分为集中式DCA,分布式DCA和完全分布式DCA。集中式DCA方案［5］为了进行信道分配需要完整的系统信息和控制机制，它能在理论上提供最好的性能，但是大量的运算以及各基站之间的通信导致额外的系统等待时间使集中式DCA方案实用效率较低，尽管如此，它能为更加实用的分布式DCA提供参考比较。完全分布式DCA是另外一种极端，不需要网络规划或基站问的通信，如DECT系统(DigitalEnhancedCordlessTelecommunicationsSystem),它们依赖于被动监视每个基站的空闲信道，允许小区占用任意一个被认为有足够载波干扰比的空闲信道。分布式DCA方案又分为动态资源占用和简单动态信道分配。

混合信道分配(HybridChannelAssignment,HCA),此算法综合了固定信道分配和动态信道分配方法，即每个小区分配一组固定的信道。另一组信道储备用于灵活的动态信道分配。预定的分配方法依赖于已知的业务方式的改变，这些灵活的信道分给那些预定的小区以解决那些业务方式的可预见的变化。使用预测的分配方式，每个基站的业务量被持续地或周期地检测，然后信道根据这些测量值分配给小区。实际上HCA是FCA和DCA两者结合起来的产物，故称混合信道分配。

2算法描述

为了充分利用无线频谱，需要有一个既能增加用户容量又能减小干扰频率信道复用方案。根据之前介绍的三种信道分配策略，本节提出一种混合式信道分配算法，即一种基于用户的信道分配算法，根据网络拓扑构造最小生成树并且在分配信道资源时优先考虑生成树内的链路，尽可能满足节点的通信需求，以提高网络整体吞吐量。

2.1构造最小生成树

现有构造最小生成树的算法主要有两种：Prim算法[8]和Kruskal算法四。这两种方法都能在连通图中构造最小生成树，与Prim算法不同，Kruskal算法先根据边的权值进行排序再进行构造最小生成树，Prim算法在构造过程中需要对权重边做多次排序，而Kruskal算法只需进行一次排序，因此

Kruskal算法的效率要优于Prim算法。Kruskal算法是一种按照边的权值递增的顺序构造最小生成树的方法，其基本思想是：设无向连通网为G=(V,E)，设G的最小生成树为T，其初态为T=(V，｛))，即初始时，最小生成树T由图G中的n个顶点构成，顶点之间没有一条边，这样T中各个顶点各自构成一个连通分量。然后，按照边的权值由小到大的顺序,考察G的边集E中的各条边。若被考察的边的两个顶点属于T的两个不同的连通分量，则将此边作为最小生成树的边加入到T中，同时把两个连通分量连接为一个连通分量；若被考察边的两个顶点属于同一个连通分量，则舍去此边，以免造成回路，以此类推，当T中的连通分量个数为1时，此连通分量即为G的一棵最小生成树。

本文采用Kruskal算法进行最小生成树的构造，其具体过程如图2所示。首先，按照互通网中边的权值由小到大的顺序，不断选取当前未被选取的边集中权值最小的边，直至构成最小生成树。

2.2信道分配算法

在无线多跳接入网中，网络中每条链路的可用信道不同,每个节点不能同时收发，用户需求可以用信道数量来表示，假定节点的上行和下行业务需求相同。在这样一个静态网络中,首先构造出一个最小生成树，由于最小生成树中链路权值较小，所以优先利用生成树内链路分配信道资源能够有效提高相距一定范围内的节点进行通信，若只考虑最小生成树上的信道会造成一定的信道资源浪费，也就是说除了最小生成树以外,还存在许多其他可用信道，这里我们保证优先利用最小生成树的同时，也要充分利用这些信道资源。所以，优先考虑最小生成树分配信道后，根据节点的通信需求是否得到满足进而决定是否通过给其他符合条件的链路分配信道，以满足节点需求并达到提高网络吞吐量的目的。这里最小生成树外链路要符合的条件有：与此节点相连的节点上还存在可用信道，否则无法进行通信；与此节点相连的节点跳数少于此节点，否则会出现延时太大，以至于影响通信质量。

根据上述Kruskal算法，针对图3所示的网络拓扑，即一个AP和8个节点的网络中构造最小生成树，其结果如图4所示(假设每条链路有三条可用信道，节点下方标注节点的信道需求)。

完成构造最小生成树后，我们根据节点的通信需求进行信道资源的分配，如图5所示。这里我们按由上到下，由左到右的顺序来依次分配信道。这里以节点e和节点f为例来说明提出的信道分配算法。

节点e:由于优先考虑最小生成树上的信道，所以节点e的路径为e-a-AP,在这里，我们可以看到，即使链路(a,AP)已经给节点a分配了一个信道，最小生成树仍然可以完系统整体的性能。在无线通信网络中，每个节点都能和与其全满足这个节点的需求，所以我们查找链路(e,a)和(a.AP）上的可用信道，为节点e分配（e,a）上的可用信道13,和（a,AP）上的可用信道1。由于节点e的需求已经得到满足,所以这里不需要再考虑为它分配生成树外链路上的可用信道。

图5节点信道分配示意图

节点f：与节点e类似，首先考虑最小生成树上的信道资源，节点f的路径为f-g-c-AP,由于节点c和节点g已经先于节点f分配了信道，所以在链路（c,AP）上只剩下一条信道（信道9）,所以将这条信道分配给节点f,并且在链路（g,f）和链路（f,g）上查找一条可用信道，分别是信道29和信道22分配给节点f。此时节点f的需求并没有得到满足，所以我们需要利用生成树外链路来提供信道资源。根据之前所述的最小生成树需要符合的条件，首先考虑与f相连的链路，链路（f,e）符合条件，而节点e所在的路径只能提供一条可用信道，所以在链路（f,e）、链路（e,a）和链路（a,AP）上查找一条可用信道，分别为19,14,3分配给节点f。此时节点f的需求仍然没有满足，而链路（f,g）上还存在可用信道，所以接着查找与节点g相连的链路，可以看到链路（g,b）也满足要求而节点b所在的路径上还存在两条可用信道，所以，分别将链路（g,b）和链路（b,AP）上的信道25,26和5,6分配给节点f。此时，三条跳数相同的候选路径联合为节点f提供传输服务，满足了节点f的通信需求。

根据上述算法描述，本算法为节点分配信道资源的具体流程如图6所示。

C开始］）

图6算法流程图

3仿真分析

3.1网络拓扑

本节采用MATLAB软件进行仿真，仿真场景为在一块1kmX1km的空间内，节点位置进行随机部署，节点个数可以根据仿真需要进行调整。由于节点之间进行的是无线通信，所以规定每个节点可以和与之距离250m之内的所有节点通信,因此，在这些能够通信的节点间建立链路，并将这些信息存储在邻接矩阵中。

按照信道分配算法的步骤，针对网络拓扑构造最小生成树并添加最小生成树外链路，如图7所示。其中，粗实线为最小生成树中包含的链路，而虚线部分为添加的最小生成树外的链路。

图7网络拓扑图（40个节点）

3.2仿真分析比较

当网络中节点个数一定，改变每条链路上的可用信道时,分别对网络吞吐量进行仿真。设定网络中有60个节点，每个节点最大的业务需求为4,改变每条链路上的可用信道数目从10个到30个，网络吞吐量仿真结果如图8所示。图中每组柱状图中第一条为理想情况下，当所有节点的需求都被满足，整个网络所获得的吞吐量；第二条为采用本文提出的算法进行信道分配得到的网络吞吐量；第三条为不考虑最小生成树外链路信道资源时得到的网络吞吐量；第四条则为前两者的差值。由仿真结果可以看出这种算法能有效提高网络的吞吐量。当每条链路上的可用信道太少时，所有链路上的信道使用情况已接近饱和，所以吞吐量提高并不明显，但在这种情况下吞吐量仍有一定的增长。另一方面，当每条链路上的可用信道数目很多时，即使不考虑生成树外的链路，用户需求的满足状况也已经接近理想状态，所以能够提高的空间并不大，而我们提出的算法同样能使其得到一定提高。由此可见，这种算法是能够提升包含60个节点的网络的性能。

当网络中每个节点有20个可用信道，每个节点最大的业务需求为4,网络中节点数从40个到80个，分别对网络吞吐量进行仿真，结果如图9所示。由仿真结果可以看出，不管节

点数如何发生变化，我们提出的算法都有效提升了网络整体的吞吐量。但当节点个数较少时，由节点分布比较稀疏，而节点之间无线通信的距离限制，相对于分布比较稠密的网络来说，网络中存在的可用链路数比较少，那么在添加生成树外的链路时，可以选择的个数也相对降低。所以，当网络中节点数较少的时，吞吐量的提升也相对比较小。而图中吞吐量之差并不是线性增长的趋势，这是因为网络中拓扑生成的时候，节点的分布并不是完全均匀的，而是随机分布的，所以也会有一定因素的影响，但总的来说节点个数相对多的时候吞吐量的差值还是比节点个数少时较高，而且不管节点个数如何变化，系统的吞吐量都有显著的提高。

图8不同可用信道数对应的网络吞吐量(60个节点)

图 9 不同节点数对应的网络吞吐量（20 个可用信道）

4结语

混合信道分配策略既降低了固定信道分配策略的频谱规划的复杂性，又能够根据通信业务的实际发生量以调整信道的使用情况，因此混合信道分配策略是一种比较实际可行的方案。

本文基于混合信道分配策略在无线多跳接入网环境下提出了一种应用最小生成树算法的信道分配算法，并且针对不同节点数和不同可用信道情况分别进行了仿真比较。仿真结果表明，这种无线多跳接入网信道分配算法确实能够提高信道的吞吐量。

20211223_61c350af565cd__一种基于最小生成树的无线多跳网络信道分配算法