一种工业无线网络中基于最大匹配的时隙信道分配方法

摘要

本发明公开了一种工业无线网络中基于最大匹配的时隙信道分配方法，该方法利用最大匹配算法对网络中的时隙资源进行分配，提升了网络中单位时隙内的数据流量，保障节点的休眠时间；通过点着色算法对网络中的信道资源进行分配，解决网络中的干扰问题。综合两种分配方法为通信网络建立调度表，实现对网络中节点行为的调度管理，增加节点的休眠时间，在保障时隙通信确定性、可靠性的同时节约节点能量，延长网络的生存周期。

说明书

技术领域

本发明属于工业无线通信领域，具体涉及工业无线网络中一种基于最大匹 配的时隙信道分配的实现方法。

背景技术

近年来，工业无线通信领域相关技术的研究得到了学术界和工业界的广泛 关注，并取得了迅猛的发展。工业无线通信网络与传统有线网络相比，由于其 特殊的应用场景，存在很多现实的约束条件，如传感器节点能量限制、通信能 力限制以及计算和储存能力限制等，如何在诸多限制之下实现对工业无线通信 网络中的通信资源进行合理调度分配成为该领域的一个重要研究内容。

在工业无线通信网络中，通信资源是指数据源点到目的点之间有向通信路 径及其所使用的一系列点到点之间通信所占用的时间和频率。其中时间以时隙 的形式体现，时隙通信机制通过时分复用将时间分割成连续的时间片，保障不 同节点之间在不同时间片内进行数据通信，网络中不同的节点在不同时隙进行 合理的收发配置能够有效的避免节点之间的数据冲突。频率以信道的形式体现， 跳信道机制通过频分复用在不同的频率传送数据，不仅可以增加网络吞吐量， 还能有效的降低干扰和多径衰落的影响。

为了实现对网络中通信资源的有效分配，工业无线通信网络通过合理利用 时隙通信机制与跳信道机制制定调度表，调度表通过合理分配时隙和信道等通 信资源安排节点在网络中的行为，网络中的节点根据已经制定好的调度表来执 行相应行为，比如节点在某一时隙和某一信道上发送或者接收数据，在某些时 隙进入休眠状态。这种基于时隙通信和跳信道机制建立调度表的时隙信道分配 方式能够保证网络中相互竞争的节点获得合理的通信资源，能够有效避免冲突， 提高吞吐量和带宽利用率，解决现场设备间数据通信的确定性、可靠性问题。

在工业无线通信领域中，传统基于时隙的调度方法在研究的过程中往往只 考虑在单一的信道上面进行基于时隙的调度，直接对信道资源调度的问题避而 不谈，或者将信道资源调度过程理想化，这在一定程度上造成信道资源的浪费， 限制了网络中通信资源调度分配的合理性。

本发明针对以上工业无线通信领域传统调度方法的缺陷，创新性地提出了 一种基于最大匹配的时隙信道分配的实现方法，该调度方法可以直接应用在基 于时隙通信和跳信道机制的工业无线通信网络中，保障网络运行的实时性，可 靠性以及较高的网络吞吐量。

发明内容

针对以上现有技术中的不足，本发明的目的在于提供一种增加了网络的可 达吞吐率、减少延时、节约大量的能量、确定性加强的工业无线网络中基于最 大匹配的时隙信道分配方法，本发明的技术方案如下：一种工业无线网络中 基于最大匹配的时隙信道分配方法，其包括以下步骤：

101、工业无线网络进行初始化，设定初始时隙k_初始＝0，将此时初始时隙k＝0 对应的调度表part进行初始化，即part＝0；

102、统计工业无线网络时隙帧slotframe中初始时隙k_初始＝0到k时隙为止从 叶子节点汇聚到主节点PAN协调器总的流量数q₀(k)及工业无线网络中总的流量 数Q，当q₀(k)＝Q时，则表明调度表part已经生成，根据调度表进行时隙信道 分配，结束；当q₀(k)≠Q时，则表明调度表还没有完全生成，跳转至步骤103；

103、获取k时隙时的网络拓扑图及k时隙时的物理连通图，并采用最大匹 配算法匈牙利算法求得k时隙时的网络拓扑图的免多冲突链路集合VMCL(k)；

104、将步骤103求得的免多冲突链路集合VMCL(k)与k时隙时的物理连通 图进行对比，以k时隙物理连通图作为参考，对VMCL(k)链路集合进行修正，剔 除VMCL(k)链路集合中存在而k时隙物理连通图中不存在的链路，将k时隙物理 连通图中存在而VMCL(k)链路集合中不存在且与现有VMCL(k)链路集合不产生 冲突的链路填补进VMCL(k)链路集合中，由此形成冲突干扰图 IC(k)＝{V_I(k),E_I(k)}，其中V_I(k)表示冲突干扰图IC(k)中节点的集合，E_I(k)表示冲 突干扰图IC(k)中链路的集合。

105、将步骤104中得到的冲突干扰图IC(k)＝{V_I(k),E_I(k)}采用顺序点着色算 法着色，选取质量较好的信道制作成抗干扰信道序列对着色的点进行信道的分 配，将上述过程中分配得到的时隙和信道信息的填入调度表part，将所述调度 表part进行升级更新，网络根据调度表中的时隙信道分配信息进行调度运行。

进一步的，步骤104中的最大匹配算法匈牙利算法步骤如下：

201、将k时隙时的网络拓扑图顶点划分为两个互不相交子集X,Y,且拓扑 图中的每条边的所关联的两个顶点分别属于这两个不同的顶点集，由此形成 该网络拓扑具有二部划分(X,Y)的二分图,在二分图中任意选定一初始匹配 集合M；

202、若顶点集X或Y中每一个顶点都在匹配集合M中，则称匹配集合M饱 和，若匹配集合M饱和，则跳至步骤207，若匹配集合M不饱和，则跳至步骤 203；

203、若图中一顶点不在匹配集合M中,则称该顶点为非M饱和点,在集合X 中任意选定初始匹配集合M的一个非M饱和点x，将x存入集合X对应的非饱 和点集合S中，即S＝{x}，集合Y对应的非饱和点集合T为空集，即T＝φ；

204、获取非饱和点集合S中所有与x相邻的点的集合N(S)，若N(S)＝T， 则跳转至步骤207；否则任选一点y∈N(S)-T；

205、若y为匹配集合M的一个顶点，即y为M饱和点，则转到步骤206， 否则选取一条从x到y的M可增广路P，将集合M与集合P的并集去除集合M与 集合P的交集后的集合作为新的匹配集合M，即M＝M⊕P，转到步骤202；

206、由于y是匹配集合M中的M饱和点，则匹配集合M中必然存在一条 边{y,u}，将这条边的另一个顶点u加入到X对应的非饱和点集合S中，即 S＝S∪{u}，将y加入到Y对应的非饱和点集合T中，即T＝T∪{y}，最后从顶点 u的相邻的点的集合中选出非M饱和点加入到N(S)中，转到步骤/204；

207、结束寻找，得到最大匹配集合M'。

进一步的，所述步骤105中的顺序点着色算法步骤中，还包括采用选择函 数Q_i(k)＝max{Q_j(k)|n_j∈ch(p_i)∧q_j(k)≠0}，对节点i的流量Q_i(k)进行逆序排列的步 骤，其中ch(p_i)表示节点p_i的所有子节点。

本发明的优点及有益效果如下：

本发明提出的时隙信道分配方法通过利用最大匹配算法以及点着色算法对 网络中的时隙资源以及信道资源进行合理的分配，并且通过匹配问题解决了网 络中的隐蔽端问题，最大匹配提升了网络中的对流量发送最大的要求，增加了 网络的可达吞吐率，通过点着色问题解决了网络中干扰问题，使网络更加稳定。 两种方法的结合使网络中的延时减少，确定性加强，由于调度表在每个时隙都 安排最多的数据发送，可以使节点有更多的时间休眠，因此可以节约大量的能 量，使节点的生存期更长。因此本发明提出的算法满足资源受限无线传感网对 实时性、确定性以及低功耗的设计要求。

本发明提出的分配方法有效的实现了时隙和信道资源的合理分配，根据该 分配方法制定的调度表，可以直接应用在基于时隙通信和跳信道机制的工业无 线通信网络中，满足了工业无线领域中对网络资源合理分配的需求，实现了工 业无线网络的长期可靠运行。

附图说明

图1为本发明优选实施例时隙信道分配算法流程图；

图2网络拓扑图及相应的二分图；

图3一个任意匹配图；

图4步骤1～4的循环后获得的匹配；

图5简单网络拓扑图；

图62.4Ghz信道分配举例图。

具体实施方式

下面结合附图给出一个非限定性的实施例对本发明作进一步的阐述。

参照图1-6所示，本发明的总体技术方案如下，网络中各节点设备未通电 前保持关闭状态，协调器上电后，首先初始化网络参数，形成一个新的PAN网 络，网络物理连通图为空，网络中的各个节点流量为0。

(1)网络进行初始化，规定时隙从零开始，即k＝0；调度表进行初始化，即part＝0； (2)q₀(k)表示在slotframe帧上到k时隙为止，网络中从其它叶子节点汇聚到的 主节点PAN协调器中总的流量数，Q表示网络中总的流量数。当q₀(k)≠Q时，k 时隙网络中的主节点的流量数与网络中的流量数不相同，表示调度表还没有完 全生成，继续进行执行(3)-(7)；否则表示调度表已经完成生成，返回生成的调度 表，并结束算法。

(3)根据在k时隙时的网络拓扑图，运用匹配相关知识制作免多冲突链路，这 时查找到的链路可以放在同一个时隙上，但是找到的链路数不一定是最多的， 即这个时候发送的流量数不一定是最大的，因此这时引入了最大匹配的概念， 用最大匹配查找网络拓扑图中的链路，此时找到的链路数是最多的，这个时候 可以发送的流量数是最大的，该时隙的网络拓扑图中的免多冲突链路集合 VMCL(k)查找完成。

(4)将免多冲突链路集合VMCL(k)与k时隙时的物理连通图进行对比，以k时隙 物理连通图作为参考，对VMCL(k)链路集合进行修正，剔除VMCL(k)链路集合中 存在而k时隙物理连通图中不存在的链路，将k时隙物理连通图中存在而 VMCL(k)链路集合中不存在且与现有VMCL(k)链路集合不产生冲突的链路填补 进VMCL(k)链路集合中，由此形成冲突干扰图IC(k)＝{V_I(k),E_I(k)}，其中V_I(k)表 示冲突干扰图IC(k)中节点的集合，E_I(k)表示冲突干扰图IC(k)中链路的集合。

(5)利用得到的冲突干扰图IC(k)，根据点着色的原理对IC(k)图中的各个节点 进行着色并生成点着色后的图。

(6)选取信道质量较好的信道制作成抗干扰信道序列对着色的点进行信道的分 配。

(7)将k时隙的发送链路安排在调度表中，记录此时q的流量数以及网络中的 流量数并升级调度表，最后将时隙k进行加1处理，跳转至步骤(2)进行循环 判断。

具体地，下面介绍最大匹配算法；

(1)最大匹配算法

本发明利用图论中最大匹配算法对网络拓扑图进行免多冲突链路VMCL(k) 的查找，在时隙k上找到网络最多的免多冲突链路，可以实现该时隙发送数据 流量最大。首先对最大匹配问题进行阐述：

由于传感器节点能量资源有限，在发送和接收数据以及空闲状态时会消耗 很多的能量，而在休眠过程中几乎不消耗能量。如果有一种调度方法能保障数 据都安排在一个相对集中的时隙中接收或者发送，那么将会节约网络中节点的 总体能量开销，使网络生命周期最大化。因此在本算法中引入了最大匹配的概 念，即在网络中每个时隙上都安排最多的链路进行发送，在网络中发送数据量 一定的情况下，以一种流量最大的方式发送数据将使网络中的节点有较多的时 间进行休眠。

对最大匹配的进一步说明如下，一个图中的任何匹配m，均存在m≤M，则 M就是这个图的最大匹配。也就是说，最大匹配问题就是为了使网络拓扑图中 的免多冲突链路VMCL(k)数最大的问题，即解决k时隙网络中能够发送最多不冲 突数据的问题。从网络整体运行的角度看，通过调度使得在同一个时隙k上能 够发送的数据越多，就能大幅提高网络吞吐量，也能够使网络中的数据尽快传 送完毕后进入空闲状态，进而节约大量的电能，使网络能够运行更长的时间， 延长网络的寿命。

为了更好地解释最大匹配算法，下面通过举例介绍一种基于匹配查找最大 匹配的算法。

在数学界，通过图G中任一匹配M扩充为最大匹配的算法称谓匈牙利算法， 假设给出的图都是具有二部划分(X,Y)的二分图。匈牙利算法步骤如下：

(1)将k时隙时的网络拓扑图顶点划分为两个互不相交子集X,Y,且拓扑 图中的每条边的所关联的两个顶点分别属于这两个不同的顶点集，由此形成 该网络拓扑具有二部划分(X,Y)的二分图,在二分图中任意选定一初始匹配 集合M；

(2)若顶点集X或Y中每一个顶点都在匹配集合M中，则称匹配集合M饱 和，若匹配集合M饱和，则跳至步骤(7)，若匹配集合M不饱和，则跳至步骤 (3)；

(3)若图中一顶点不在匹配集合M中,则称该顶点为非M饱和点,在集合X 中任意选定初始匹配集合M的一个非M饱和点x，将x存入集合X对应的非饱 和点集合S中，即S＝{x}，集合Y对应的非饱和点集合T为空集，即T＝φ；

(4)获取非饱和点集合S中所有与x相邻的点的集合N(S)，若N(S)＝T， 则跳转至步骤(7)；否则在集合N(S)-T中任选一点y，即y∈N(S)-T；

(5)若点y为匹配集合M的一个顶点，即y为M饱和点，则转到步骤(6)， 否则选取一条从x到y的M可增广路P，将集合M与集合P的并集去除集合M与 集合P的交集后的集合作为新的匹配集合M，即M＝M⊕P，转到步骤(2)；

(6)由于y是匹配集合M中的M饱和点，则匹配集合M中必然存在一条 边{y,u}，将这条边的另一个顶点u加入到X对应的非饱和点集合S中，即 S＝S∪{u}，将y加入到Y对应的非饱和点集合T中，即T＝T∪{y}，最后从顶点 u的相邻的点的集合中选出非M饱和点加入到N(S)中，转到步骤(4)；

(7)结束寻找，得到最大匹配集合M'。

对上述算法过程中出现的术语进行如下解释，M-顶点即为M饱和点，M是 图G的匹配，G中与M中的边关联的顶点。非M-顶点则为G中的部分顶点不 是M匹配中边关联的顶点。S表示非饱和点集合，N(S)集合表示集合S中点的 相邻点的集合。二部划分的二分图，该算法运行网络中对网络冲突的定义可以 理解为网络拓扑中的奇数层节点在发送数据的时候，偶数层的节点肯定不能再 发送数据，同理偶数层的节点在发送数据的时候，奇数层的节点也不能发送数 据。则本算法研究的网络拓扑都可以二部划分成为二分图。

为了更好的解释上述算法，分析图2中A图的网络拓扑结构，获得其对应 的二分图B，并根据二分图B详细介绍最大匹配算法，并找出在k时隙时该网 络拓扑图中最多免冲突链路集合VMCL(k)。

具体操作步骤如下：

(1)首先在根据网络拓扑图A画出原始的二分图B，图B中节点y1-y6组 成集合Y，节点x1-x7组成集合X，然后在二分图中找出一个任意的初始匹配即 免冲突链路集合。如图3，找到初始匹配为M＝{(y₁,x₁),(y₂,x₂),(y₃,x₄),(y₄,x₃)}。

(2)由于集合Y中仍然存在顶点不在匹配M中，因此集合Y尚未饱和， 在集合Y中任取一个非饱和点y₅放入Y的非饱和点集合S中，此时S＝{y₅}，集 合X对应的非饱和点集合为空，即T＝φ。

(3)从图3找到集合S＝{y₅}相邻的点的集合N(S)＝{x₄}，因为{x₄,y₃}为匹 配的子集，此时x₄为饱和点，将点x₄加入到集合T中，则T＝{x₄}。将点y₃加入 到集合S中，此时集合S＝{y₃,y₅}。

(4)继续在图3中查找集合S＝{y₃,y₅}的邻集N(S)＝{x₁,x₄,x₇}，该集合中点 x₇是非饱和点，则做一条从点y₅到点x₇的可增广路P， p＝{(y₃,x₇),(y₃,x₄),(y₅,x₄)}。将集合M与集合P的并集去除集合M与集合P的交 集后的集合作为新的匹配集合M，即M＝M⊕P，则此时匹配集合 M＝{(y₁,x₁),(y₂,x₂),(y₃,x₇),(y₄,x₃),(y₅,x₄)}。

(5)经过步骤1～4的循环，得到了图4所示的新的匹配集合M。此时的匹 配是不是最大匹配还需要重复上述步骤继续进行查找才能确认。取图4中集合Y 的非饱和点y₆，则此时有S＝{y₆}，T＝φ，N(S)＝{x₄}，由于x₄是饱和点，加入 到集合T中，此时T＝{x₄}；{x₄,y₅}是匹配M中的子集，则将y₅加入到集合S中， 此时S＝{y₅,y₆}，N(S)＝{x₄}由于此时N(S)＝T，最大匹配的查找过程停止，得到 了最大匹配M＝{(y₁,x₁),(y₂,x₂),(y₃,x₇),(y₄,x₃),(y₅,x₄)}。

对于网络拓扑图图2-A，根据匈牙利算法的基本原理经过推算得到了图的 最大匹配，则最大匹配集中的链路都可以安排在同一个时隙k上发送数据，并 且可以保证链路之间不会产生任何干扰，这样就可以使网络在单位时间内发送 最大的数据量，增加了网络的吞吐量。网络中的数据能在相对较短的时间完成 发送，则传感器网络中的节点有更多的时间用来休眠，节约了节点设备的能源， 这对于资源受限的工业无线通信网络有重大意义。

(2)点着色算法

利用点着色算法对在k时隙的物理连通图中存在的干扰冲突链路进行信 道的分配，解决了在同时隙上网络中发送链路的干扰冲突问题。

在时隙k上，建立网络中的VMCL(k)集合，将免多冲突链路集合VMCL(k) 与k时隙时的物理连通图进行对比，以k时隙物理连通图作为参考，对VMCL(k)链 路集合进行修正，剔除VMCL(k)链路集合中存在而k时隙物理连通图中不存在的 链路，将k时隙物理连通图中存在而VMCL(k)链路集合中不存在且与现有 VMCL(k)链路集合不产生冲突的链路填补进VMCL(k)链路集合中，由此形成冲突 干扰图IC(k)＝{V_I(k),E_I(k)}，其中V_I(k)表示冲突干扰图IC(k)中节点的集合，E_I(k) 表示冲突干扰图IC(k)中链路的集合。获得冲突干扰图IC(k)后给IC(k)中的链路 分配不同的信道，这样可以使网络中的节点在不引起干扰的情况下同时在时 隙k发送数据。

本发明将无线传感器网络中的频率分配问题简化成为一个相关图的点 着色问题，即要对冲突干扰图IC(k)进行着色处理，由于目前没有一个有效的 算法用来确定图色数，我们使用了一种求点色数的近似有效算法，顺序着色 算法，其核心思路如下：

设G＝(V,E)是无向图，V＝{x₁,x₂,L,x_n}用N(x_i)表示与x_i相邻的全部顶点集 合；对顶点x_i着色C，记为π(x_i)＝C

(1)i:＝1

(2)c:＝1

(3)若对则令π(x_i)＝c并转入第5步。

(4)c:＝c+1并转入第3步。

(5)若i<n，则i:＝i+1并转回第2步，否则停止

以图5为例对顺序着色法进行简单的说明。

首先给第一个节点x₁着第一种颜色，即i＝1，c＝1；

对于与节点x₁相邻的节点集合N(x₁)＝{x₂,x₃}，因为顺序着色法规定与x₁相 邻的点不能着同一种颜色，需要第二种颜色，此时c＝c+1。

找结点x₂，x₃的邻居节点N(x₂,x₃)＝{x₁,x₄,x₅,x₆}，由于节点x₁着了第一种 颜色，并且x₁节点与x₄,x₅,x₆节点都不相邻，则节点x₄,x₅,x₆可以与节点x₁着同 一种颜色。此时停止，该图的色数为2。

现在详细介绍顺序着色法在信道分配中的应用。

首先V_I(k)集合中的节点根据Q_i(k)中流量大小按照逆序进行排列，然后根 据网络中所有节点的全局队列水平大小进行比较，第一次着色给网络中拥有 网络中流量最大的节点n_i，剩下的节点按照如下分组原则分为两个组：与着 色的节点n_i有干扰(即图中相邻的点)的节点分为一个组，与着色节点n_i没 有干扰的节点分为第二个组。从非干扰节点中找出一个节点，然后将这个节 点着上与第一个节点相同的颜色，接下来剩余列表中的其他节点利用上述规 则再一次分为两组。按照这种方法进行着色完成后，相同着色的链路集合能 在时隙k上安排在同一个信道c上进行数据发送，VCL_c(k)就这样被建立起 来。

最后，网络运用相同的方法把建立的不同VCL_c(k)链路集合安排在不同的 信道上面，并完成时隙k时刻的调度资源的分配，形成了调度表。

根据五色定理即连通简单平面图G的色数为5，可以分析对查找到干扰 冲突图IC进行顶点着色，其理论上使用信道数可以不超过5条。根据五色定 理下面提供另一种方法对信道序列进行排列。

对连通图经过顺序着色算法实施后，根据五色定理分析得出网络中有充 裕的信道可以进行分配，本课题将工业无线网络2.4Ghz频段分配成为5部分。

如图6所示，将在2.4Ghz频段分配成为5部分，首先信道扫描确定2.4Ghz 的16条信道的质量，根据图中相应的划分尽量挑选每部分相对距离较远的信道， 在信道质量相同的情况下，本课题建议选择每部分中间的信道这样可以避免不 同网络相互之间的干扰以及信道之间的干扰。

(3)选择函数

在该时隙信道分配方法中，选择函数使用了迭代的方式，从网络拓扑图 中的根节点开始遍历，直到遍历完所有的叶子节点，这个函数可以表示为：

Q_i(k)＝max{Q_j(k)|n_j∈ch(p_i)∧q_j(k)≠0}

由表达式可以看出，在时隙k，只有当子节点n_i有数据发送到它的父节 点p_i时，链路(n_i,p_i)才能被激活，如果没有数据在该时隙需要发送，则这条 链路将不被激活。正是因为选择函数具有的这样的一种能力，才最大限度避 免了将宝贵的时隙资源分配给没有任何数据发送的空节点，减少了调度资源 的浪费。网络拓扑上对链路的选择是基于局部链路和全局链路流量的，通过 网络中每条链路上的网络流量来选择查找匹配即免多冲突链路集合，这样可 以使找到的链路具有此时刻在网络中流量最大化的特征。同时，为了能够节 约更多的能源，该调度方法中设计的VMCL(k)链路通过选择函数进行选择， 因此还可以将连续的时隙保留给拥有大量数据发送的链路。

在对点着色的过程中，选择函数也发挥了其应有的作用，V_I(k)集合中的 节点根据Q_i(k)中流量大小按照逆序进行排列，这里Q_i(k)流量的大小就是选择 函数进行统计，然后根据网络中节点的Q_i(k)得到每次进行比较的第一个节 点。每次都首先把时隙安排给最大流量的链路进行发送，这样有利于网络中 的数据尽快的传递完成。

通过选择函数这种机制，可以减少网络的延时，增强了算法对网络确定 性的支持，增加网络吞吐量，减少了资源浪费以及节约了能耗，使无线传感 器网络能够更长时间的稳定运行。

以上这些实施例应理解为仅用于说明本发明而不用于限制本发明的保护范 围。在阅读了本发明的记载的内容之后，技术人员可以对本发明作各种改动或 修改，这些等效变化和修饰同样落入本发明方法权利要求所限定的范围。