TDMA自组网中基于业务流路径的动态时隙分配方法

摘要

本发明公开了一种TDMA自组网中基于业务流路径的动态时隙分配方法，解决了多跳传输时动态时隙分配时间过长，非瓶颈节点占用无效时隙的问题。方案是：在业务流源节点检测业务，将每个节点的动态时隙占用情况汇总到业务流路径上最后一跳节点对所有节点时隙分配；按轮次分配，保证分配完成后路径上所有节点分得的动态时隙个数是相等的，按轮分配时采取一步回退方式，增大瓶颈节点的可占用时隙个数。本发明设计包含源节点检测业务流，路径上最后一跳节点汇总各节点信息进行时隙分配，缩短了业务检测和时隙分配时间，按轮次分配和一步回退方式，避免了木桶效应，提高了时隙利用率，增加了端到端的吞吐量，用于TDMA自组织网络领域。

权利要求

1.一种TDMA自组网中基于业务流的路径级动态时隙分配方法，其特征在于，包括有如下步骤：

(1)根据业务流获得业务速率和路径信息：在TDMA自组网中，根据每个复帧到达节点的帧个数，获得业务流速率Vin，则每个节点满足业务流传输所需的时隙个数nc＝Vin，根据业务帧的头部信息查询路由表，得到业务流路径上的节点集合S0；

(2)汇总各节点的可用时隙信息并排序：将各节点的可占用时隙集合发送至业务流路径的最后一跳节点，汇总得到路径上各节点可用的时隙集合Uia，根据各节点可用的时隙集合Uia计算每个时隙可分配的节点集合Sjk，按照节点集合中节点的个数将节点集合Sjk进行升序排序；

(3)为业务流路径上的节点分配时隙：采用按轮次分配的方法，每一轮次分配使路径上每个节点各获得一个时隙；每一轮分配时，按序遍历每个时隙的可分配节点集合，得到节点集合中未分配得时隙的节点，为该节点分配时隙，每一轮分配完成后保证分配给路径上每一个节点的时隙个数是相等的，直到某一节点无法获得时隙时，本次时隙分配结束；在分配过程中出现瓶颈节点可占用时隙被抢占时，采用一步回退的方式使非瓶颈节点让出时隙供瓶颈节点占用。

2.根据权利要求1所述的TDMA自组网中基于业务流的路径级动态时隙分配方法，其特征在于，其中步骤(3)中所述的为业务流路径上的节点分配时隙，包括有如下步骤：(3a)初始化分配轮次n为1，清空分配给节点的时隙集合di，置节点i时隙个数ni为0，置N的值为路径上节点的个数，执行(3b)；

(3b)开始第n轮的分配过程，置预删除节点集的个数d为0，将遍历位置重置到第一个集合，执行(3c)；

(3c)从遍历位置遍历节点集合，直至节点集合Stk中存在节点i，使得ni

1，将ni的值加1，d的值加1，判断d是否和N相等：若是，执行步骤(3j)；否则，判断所有节点集合是否遍历结束：若是，执行步骤(3d)；否则，执行(3c)；

(3d)遍历路径上所有节点，将满足ni

(3e)遍历Sl，设节点i∈Sl，遍历预删除标志为1的节点集合，判断是否存在含节点i的集合：若是，将含有节点i的所有集合添加至大集合Si，执行步骤(3f)；否则，执行步骤(3k)；

(3f)遍历Si，设集合Stk∈Si，遍历集合Sp，得到预占用时隙为t的节点j，遍历所有预删除标志位为0的节点集合，判断是否存在含节点j的集合：若是，执行步骤(3g)；否则执行步骤(3h)；

(3g)设j∈Smk，将节点j的的预占用时隙置为m，节点i的预占用时隙置为t，将Stk的预删除标志置为2，将Smk的预删除标志置为1，将ni的值加1，d的值加1，将节点i从集合Sl删除，判断Sl是否为空：若是，执行步骤(3i)；否则，执行步骤(3e)；

(3h)将节点集合Stk从Si中删除，判断Si是否为空：若是，执行步骤(3k)；否则执行步骤(3f)；

(3i)将每个节点的预占用时隙添加至对应节点的时隙集合di，执行步骤(3k)；

(3j)将分配轮次n的值加1，将每个节点的预占用时隙添加至对应节点的时隙集合di，将所有节点预占用时隙置为无，删除预删除标志位不为0的所有节点集合，判断n是否和业务流所需时隙nc相等：若是，执行步骤(3k)；否则，执行步骤(3b)；

(3k)记录每个节点此次分配过程的分配结果di，逐跳将分配结果通知路径上的相应节点，分配过程结束。

3.根据权利要求1所述的TDMA自组网中基于业务流的路径级动态时隙分配方法，其特征在于，其中步骤(1)中，所述的根据业务流获得业务速率和路径信息，按如下步骤进行：(1a)设每个时隙的长度为s，每个复帧包含m个时隙，则定时检测的周期为T，T＝m*s,检测周期T内到达的该业务帧的个数为nin，则业务流的速率为Vin，Vin＝nin，每个节点满足业务流传输所需的时隙个数nc，nc＝Vin；

(1b)根据数据帧的传输层头部信息，判断业务流类型，若为TCP业务，nc＝nc+2；否则，nc不变；根据自组织网帧头部的源地址和目的地址查询路由表获得路径上所有节点的集合S0；

(1c)记录该业务流的类型、路径节点集合和业务流速率Vin。

4.根据权利要求1所述的TDMA自组网中基于业务流的路径级动态时隙分配方法，其特征在于，其中步骤(2)中，所述的汇总各节点的可用时隙信息并排序，按如下步骤进行：(2a)获取节点可占用的时隙集合：网络中的每个节点维护两跳内邻节点的时隙占用信息，该信息是通过一个一维数组实现，数组下标为时隙号，值为占用该时隙的节点号，-1代表该时隙未被两跳内节点占用，其他值代表占用该时隙的节点号；节点可以根据此信息和两跳内时隙不冲突原则，获得本节点可预约的时隙集合，节点将标记值为-1的所有时隙添加至节点的可预约时隙集合中，Uia为节点i的可占用时隙集合；

(2b)将可占用的时隙集合传递至路径上的最后一个节点：源节点将路径信息和自己的可占用时隙集合封装起来发送至路径的下一跳节点，其他节点收到信息后，将自己的可占用时隙集合和收到的信息封装在一起向下一跳发送，直至路径的最后一跳节点；

(2c)计算每个时隙的可分配节点集合：路径上的最后一跳节点收到其他节点的可占用时隙集合后，从0号时隙开始，根据节点号升序遍历节点的可占用时隙集合，节点i的可占用时隙集合为Uia，若0∈Uia，则将节点i添加至时隙0的可分配节点集合S0k；划分节点集合Sjk时，根据两跳内时隙不冲突原则和路径信息，使得每一个节点集合Sjk中的只有一个节点可被分配时隙j；得出所有时隙的所有节点集合后，按照集合内节点的个数进行排序，集合内节点的个数相同时，按照时隙号升序排列。

说明书

TDMA自组网中基于业务流路径的动态时隙分配方法

技术领域

[0001] 本发明属于无线通信技术领域，更进一步涉及MAC层中一种基于业务路径的时隙分配，具体是一种TDMA自组网中基于业务流路径的动态时隙分配方法，可广泛使用于自组网TDMA协议中。

背景技术

[0002] 作为自组网中控制节点的报文传输对无线媒体的占用，保证网络整体性能的MAC协议是移动自组网的关键技术，通过把信道划分为时隙来提高信道的空间复用度和节点接入公平性。动态时隙分配算法作为TDMA多址协议的研究方向，如何在实际应用中满足各节点的业务需求，如何高效地分配时隙，在TDMA的应用中显得尤为重要。

[0003] 目前，主要有固定时隙分配、竞争时隙分配、动态时隙分配算法，其中固定时隙分配算法为网络中的节点预先分配了时隙，但不能根据节点业务需求变化动态调整分配方案，资源浪费十分严重，实用性较差；竞争时隙分配算法允许网络内节点在一定范围内竞争时隙，从而实现时隙的复用，但这类算法完全基于随机竞争机制，因此存在冲突较多、吞吐量小的问题；动态时隙分配算法综合了固定时隙分配算法和竞争时隙分配算法的优势，在节点需要发送数据时，才分配给其所用时隙，数据发送完毕，节点取消对时隙的占用，这样可以提高信道的利用率，但也存在一些不足，如业务流在多跳路径上传输时，路径上每个节点都要检测业务、进行时隙预约的判断和计算，会延长动态时隙资源分配的时间，而且会出现木桶效应，影响端到端的吞吐量以及时隙的有效利用率。

发明内容

[0004] 本发明的目的在于针对上述现有技术的不足，提出一种缩短时隙分配时间和提高时隙效率的TDMA自组网中基于业务流路径的动态时隙分配方法。

[0005] 本发明是一种TDMA自组网中基于业务流的路径级动态时隙分配方法，其特征在于，包括有如下步骤：

[0006] (1)根据业务流获得业务速率和路径信息：在TDMA自组网中，根据每个复帧到达节点的帧个数，获得业务流速率Vin，则每个节点满足业务流传输所需的时隙个数nc＝Vin，根据业务帧的头部信息查询路由表，得到业务流路径上的节点集合S0。

[0007] (2)汇总各节点的可用时隙信息并排序：将各节点的可占用时隙集合发送至业务流路径的最后一个节点，汇总得到路径上各节点可用的时隙集合Uia，根据各节点可用的时隙集合Uia计算每个时隙可分配的节点集合Sjk，按照节点集合中点的个数将节点集合Sjk进行升序排序。

[0008] (3)为业务流路径上的节点分配时隙：

[0009] 采用按轮次分配的方法，每一轮次分配使路径上每个节点各获得一个时隙；每一轮分配时，按序遍历每个时隙的可分配节点集合，得到节点集合中未分配得时隙的节点，为该节点分配时隙，每一轮分配完成后保证分配给路径上每一个节点的时隙个数是相等的，直到某一节点无法获得时隙时，本次时隙分配结束；在分配过程中出现瓶颈节点可占用时隙被抢占时，采用一步回退的方式使非瓶颈节点让出时隙供瓶颈节点占用。

[0010] 本发明避免木桶效应的发生，缩短动态时隙资源分配的时间，提高时隙的有效利用率，增加端到端的吞吐量，提高通信质量。

[0011] 本发明与现有技术相比具有以下优点：

[0012] 第一，缩短时隙分配时间：由于本发明是在业务流路径的最后一跳节点进行路径节点预约时隙的决策，当对应节点收到决策指令后，在一个节点的检测周期内计算整个路径所有节点的分配结果，业务流的检测仅在源节点进行，无需每个节点单独检测，加快了路径资源分配的时间。

[0013] 第二，提高时隙的有效利用率：由于本发明是以业务流路径为对象按轮次分配时隙，计算业务流路径上每一个节点所需预约的动态时隙，当路径上某节点的可用时隙不足，无法满足业务流的速率时，其他节点只需要预约该瓶颈节点可预约的数目的时隙即可，而无需以业务流的速率预约时隙，减少非瓶颈节点无效的时隙资源占用。

[0014] 本发明从路径的角度在节点间协商共享时隙资源的分配，通过全路径按轮次分配的方法，避免非瓶颈节点上的无效资源分配，以及分布式时隙测了把导致的资源冲突，从而提高了时隙资源的利用率和端到端的QoS的保障能力。

附图说明

[0015] 图1是本发明的实现流程图；

[0016] 图2是本发明中的节点动态时隙信息数据结构图；

[0017] 图3是本发明中的时隙可分配节点数据结构图。

具体实施方式

[0018] 以下对本发明作详细描述：

[0019] 实施例1：

[0020] TDMA自组织网技术不仅可以满足通信网络以低成本实现高数据速率之外，还能够有效支持各种灵活的组网形式，具有良好的适应性和生存能力，因此可以广泛应用于公众应用、行业应用以及国防领域等宽带无线接入系统之中。时隙作为TDMA自组织网中的链路资源，它的分配决定端到端的吞吐量以及资源的有效利用率。目前的时隙分配方法主要有固定时隙分配、竞争时隙分配、动态时隙分配算法，动态时隙分配算法综合了固定时隙分配算法和竞争时隙分配算法的优势，在节点需要发送数据时，才分配给其所用时隙，数据发送完毕，节点取消对时隙的占用，这样可以提高信道的利用率，但也存在一些不足，延长动态时隙资源分配的时间，而且会出现木桶效应，影响端到端的吞吐量以及时隙的有效利用率。

[0021] 本发明针对上述现状展开了研究，提出一种TDMA自组网中基于业务流的路径级动态时隙分配方法，参见图1，包括有如下步骤：

[0022] (1)根据业务流获得业务速率和路径信息：在TDMA自组网中，根据每个复帧到达节点的帧个数，获得业务流速率Vin，Vin代表每个复帧到达的帧个数。则每个节点满足业务流传输所需的时隙个数nc，nc＝Vin；根据业务帧的头部信息查询路由表，得到业务流路径上的节点集合S0。

[0023] (2)汇总各节点的可用时隙信息并排序：参见图2，图2是每个节点维护的两跳内动态时隙占用情况的数据结构图，图2的左侧为数组下标，代表时隙号，右侧为对应下标的值，代表该时隙的占用标志。根据节点的维护的时隙占用情况，获得节点的可占用时隙集合，将各节点的可占用时隙集合发送至业务流路径的最后一跳节点，汇总得到路径上各节点可用的时隙集合Uia，Uia表示的是节点i的可占用时隙集合。根据各节点可用的时隙集合Uia计算每个时隙可分配的节点集合Sjk，参见图3，图3中左侧为数组下标，代表时隙号，右侧为对应下标的值，代表该时隙的可分配节点集合，图3是每个时隙的可分配节点集合的数据结构图。每个时隙的可分配节点集合表示方式有多种，本例仅以一种数组的方式表示。Sjk代表时隙j的第k个可分配节点集合。按照节点集合中点的个数将节点集合Sjk进行升序排序。节点的可占用时隙集合由自组织网的节点间交互协议获得。

[0024] 现有的时隙分配方法大都以节点出发进行时隙的分配，这类方法优势在于逻辑清晰，可操作性强，但是仍存在的问题是无法以路径的角度充分利用TDMA自组织网中时隙可复用的特性。本发明开辟了从时隙角度分配的方法，同时结合以节点的出发的方法，并参考业务流路径将时隙分配给节点，充分发挥了TDMA自组织网中时隙可复用的特性，提高端到端的吞吐量。

[0025] (3)为业务流路径上的节点分配时隙：

[0026] 采用按轮次分配的方法，每一轮次分配使路径上每个节点各获得一个时隙；每一轮分配时，按序遍历每个时隙的可分配节点集合，得到节点集合中未分配得时隙的节点，为该节点分配时隙，每一轮分配完成后保证分配给路径上每一个节点的时隙个数是相等的，直到某一节点无法获得时隙时，本次时隙分配结束。在分配过程中出现瓶颈节点可占用时隙被抢占时，采用一步回退的方式使非瓶颈节点让出时隙供瓶颈节点占用。

[0027] 本发明的技术思路是：在业务流的源端检测业务类型、业务速率和业务路径上节点信息，通过动态时隙信息帧中包含的两跳及两跳以内节点的时隙占用信息获取网络中各节点的可占用时隙，每个节点将本节点的可占用时隙信息传递至路径最后一跳节点，将每个时隙可分配的节点划分为多个冲突点集合，按照一定的策略进行决策，决策完成后将分配结果传递至路径上的每一个节点，节点根据分配结果进行时隙的预约。

[0028] 现有的时隙分配方法大都是以本节点为中心进行时隙的预约，此类方法的优势在于只需考虑本节点的时隙占用情况，实现较为简单，但存在的不足是，未考虑到业务流路径上其他节点的时隙占用情况，容易出现木桶效应，使非瓶颈节点占用无效的时隙。本发明开辟了以路径上所有节点的时隙占用情况为参考按轮次为路径上所有节点分配时隙，并采取一步回退的方法，保证每个节点占用相同数目的时隙，避免了木桶效应发生，提高了时隙的利用率和端到端的吞吐量。

[0029] 本发明在业务流的源节点检测业务，在业务流路径的最后一个节点进行路径所有节点的时隙分配，缩短业务的检测时间和路径上节点的时隙分配时间。采用按轮次分配，保证非瓶颈节点获得的时隙个数与瓶颈节点获得的时隙个数相等，避免木桶效应的发生，消除非瓶颈节点的无效时隙占用，提高时隙的有效利用率。本发明可广泛使用于自组网TDMA协议中。

[0030] 实施例2：

[0031] TDMA自组网中基于业务流的路径级动态分配方法同实施例1，其中步骤(3)中所述的为业务流路径上的节点分配时隙，是在步骤(1)和步骤(2)得到的业务流速率、路径信息、每个时隙可分配的节点集合等信息的基础上进行的，步骤(3)是采用按轮次分配的方式为业务流路径上所有的节点分配时隙，包括有如下步骤：

[0032] (3a)轮次分配方式的初始化：初始化分配轮次n为1，清空分配给节点的时隙集合di，置时隙个数ni为0，置N的值为路径上节点的个数，执行(3b)，开始第一轮的分配。

[0033] (3b)第n轮分配的初始化：开始第n轮的分配过程，置预删除节点集的个数d为0，将遍历位置重置到第一个集合，执行(3c)，开始本轮次遍历时隙可分配点集合。

[0034] (3c)为每一个节点分配时隙：从遍历位置遍历节点集合，如果节点集合中的所有节点在该轮次都已经预分配的时隙，则继续遍历下一个节点集合，直至集合Stk中存在节点i，使得ni

[0035] (3d)获得本轮次未分配得时隙的节点集合：遍历路径上所有点，将满足ni

[0036] (3e)获得Sl中节点的其他可占用时隙的节点集合的大集合Si：遍历Sl，设点i∈Sl。遍历预删除标志为1的点集合，即该集合中已有节点分配得该节点集合对应的时隙。判断是否存在含有点i的集合，即判断节点i的可占用时隙是否被其他节点占用：若是，即存在含有点i的预删除节点集合，将含有节点i的所有节点集合添加至大集合Si，大集合Si中都是节点集合，执行步骤(3f)，遍历集合Sp；否则，即不存在含有点i的预删除节点集合，节点i已经没有时隙可占用，执行步骤(3k)，结束本次时隙分配过程。

[0037] (3f)获得抢占时隙的节点：遍历大集合Si，设集合Stk∈Si，遍历集合Sp，得到预占用时隙为t的节点j，遍历所有预删除标志位为0的点集合，判断是否存在含j的集合：若是，即时隙j还存在除时隙t之外其他的可占用时隙，执行步骤(3g)，节点j让出时隙t供节点i占用；否则，即时隙j不存在除时隙t之外其他的可占用时隙，执行步骤(3h)。

[0038] (3g)抢占时隙的节点让出时隙：设j∈Smk，将点j的的预占用时隙置为m，点i的预占用时隙置为t，将Stk的预删除标志置为2，将Smk的预删除标志置为1，将ni的值加1，d的值加1，将点i从集合Sl删除，判断Sl是否为空：若是，即本轮次已经没有未获得时隙的节点，执行步骤(3i)，将本轮次节点预占用时隙添加到节点占用的时隙集合中的；否则，执行步骤(3e)，继续遍历Sl。

[0039] (3h)判断大集合Si是否为空：将点集合Stk从Si中删除，判断大集合Si是否为空：若是，执行步骤(3k)，结束本次分配过程；否则执行步骤(3f)，继续遍历节点大集合Si。

[0040] (3i)将预占用时隙转换为占用时隙：将每个节点的预占用时隙添加至对应点的时隙集合di，执行步骤(3k)，结束本次时隙分配过程。

[0041] (3j)结束本轮分配：将分配轮次n的值加1，将每个节点的预占用时隙添加至对应点的时隙集合di，将所有节点预占用时隙置为无，删除预删除标志位不为0的所有点集合，判断n是否和业务流所需时隙nc相等：若是，即所有节点已经分配得足够的时隙满足业务流，执行步骤(3k)，结束本次时隙分配过程；否则，所有节点还未分配得足够的时隙满足业务流，执行步骤(3b)，继续下一轮次的时隙分配。

[0042] (3k)记录并通告本次分配结果：记录每个点此次分配过程的分配结果di，逐跳将分配结果通知路径上的相应节点，分配过程结束。

[0043] 本发明采用按轮次分配，保证非瓶颈节点获得的时隙个数与瓶颈节点获得的时隙个数相等，避免木桶效应的发生，消除非瓶颈节点的无效时隙占用，提高时隙的有效利用率。发生时隙抢占时，采取一步回退的方式，增加瓶颈节点的时隙占用个数，增大端到端的吞吐量，提高通信质量。

[0044] 实施例3：

[0045] TDMA自组网中基于业务流的路径级动态时隙预约方法同实施例1-2，其中步骤(1)中，所述的根据业务流获得业务速率和路径信息，按如下步骤进行：

[0046] (1a)获得业务流速率和业务所需时隙：设每个时隙的长度为s，每个复帧包含m个时隙，则定时检测的周期为T，T＝m*s,检测周期T内到达的该业务帧的个数为nin，则业务流的速率为Vin，Vin＝nin，每个点满足业务流传输所需的时隙个数为nc，nc＝Vin。

[0047] (1b)获得业务类型和路径信息：根据数据帧的传输层头部信息，判断业务流类型。若为TCP业务，nc＝nc+2；否则，nc不变。根据自组织网帧头部的源地址和目的地址查询路由表获得路径上所有节点的集合S0，集合中节点的顺序为业务流的源节点到目的节点上一跳的节点。

[0048] (1c)记录(1a)和(1b)中获得得信息：记录该业务流的类型、路径节点集合S0和业务流速率Vin，每个点满足业务流传输所需的时隙个数为nc。

[0049] 本发明是在业务流的源节点检测业务特性，通知进行时隙分配的节点即业务流路径上的最后一个节点，避免了路径上的每个节点重复检测业务流，缩短了业务流检测的时间。

[0050] 实施例4：

[0051] TDMA自组网中基于业务流的路径级动态时隙分配方法同实施例1-3，在步骤(1)获得业务流路径信息后，沿路径将各节点的可占用时隙汇总，其中步骤(2)中，所述的汇总各节点的可用时隙信息并排序，按如下步骤进行：

[0052] (2a)获取节点可占用的时隙集合：

[0053] TDMA自组织网络中的每个节点通过定时广播本节点的时隙占用情况，维护两跳内邻节点的时隙占用信息，该信息是通过一个一维数组实现，数组下标为时隙号，值为占用该时隙的节点号，-1代表该时隙未被两跳内节点占用，其他值代表占用该时隙的节点号。节点可以根据此信息和两跳内时隙不冲突原则，获得本节点可预约的时隙集合，节点将标记值为-1的所有时隙添加至节点的可预约时隙集合中，Uia为节点i的可占用时隙集合。

[0054] (2b)将可占用的时隙集合传递至路径上的最后一个节点：

[0055] 源节点将路径信息和自己的可占用时隙集合封装起来发送至路径的下一跳节点，其他节点收到信息后，将自己的可占用时隙集合和收到的信息封装在一起向下一跳发送，直至路径的最后一跳节点。

[0056] (2c)计算每个时隙的可分配点集合。

[0057] 路径上的最后一跳节点收到其他节点的可占用时隙集合后，从0号时隙开始，根据节点号升序遍历节点的可占用时隙集合，节点i的可占用时隙集合为Uia，若0∈Uia，则将i添加至时隙0的可分配节点集合S0k。划分点集合Sjk时，根据两跳内时隙不冲突原则和路径信息，使得每一个节点集合Sjk中的只有一个点可被分配时隙j，节点集合Sjk表示时隙j的第k个可分配的节点集合。得出所有时隙的所有点集合后，按照集合内点的个数进行排序，集合内点的个数相同时，按照时隙号升序排列。

[0058] 本发明将路径上各节点的可占用时隙汇总到路径上的最后一个节点，根据两跳外时隙可复用和两跳内时隙不可冲突的原则，计算出每个时隙可分配的节点集合。路径上最后一个节点从路径的角度进行时隙的分配，缩短路径上节点时隙分配的时间。

[0059] 下面给出一个更详细的例子，对本发明进一步说明：

[0060] 实施例5：

[0061] TDMA自组网中基于业务流的路径级动态时隙分配方法同实施例1-4，[0062] 步骤1：源节点检测业务流，获得业务速率和路径信息：

[0063] 1.1)设每个时隙的长度为s，每个复帧包含m个时隙，则定时检测的周期为T＝m*s,检测周期T内到达的该业务帧的个数为nin，则业务流的速率为Vin，Vin＝nin，每个点满足业务流传输所需的时隙个数nc，nc＝Vin。

[0064] 1.2)根据数据帧的传输层头部信息，判断业务流类型。若为TCP业务，nc＝nc+2；否则，nc不变。根据TDMA自组织网帧头部的源节点地址和目的节点地址查询路由表获得路径上所有节点的集合S0。

[0065] 1.3)在源节点记录该业务流的类型、路径节点集合S0和业务流速率Vin。

[0066] 步骤2：收集汇总S0中各节点的可占用时隙集合，计算每个时隙可分配的节点集合：

[0067] 2.1)获取节点可占用的时隙集合：

[0068] 网络中的每个节点维护两跳内邻节点的时隙占用信息，该信息是通过一个一维数组实现，数组下标为时隙号，值为占用该时隙的节点号，-1代表该时隙未被两跳内节点占用，其他值代表占用该时隙的节点号。节点可以根据此信息和两跳内时隙不冲突原则，获得本节点可预约的时隙集合，节点将标记值为-1的所有时隙添加至节点的可预约时隙集合中，Uia为节点i的可占用时隙集合。

[0069] 2.2)将可占用的时隙集合传递至路径上的最后一个节点：

[0070] 源节点将路径信息和自己的可占用时隙集合封装起来发送至路径的下一跳节点，其他节点收到信息后，将自己的可占用时隙集合和收到的信息封装在一起向下一跳发送，直至路径的最后一跳节点，路径的最后一跳节点指的是目的节点的上一跳节点。

[0071] 2.3)计算每个时隙的可分配节点集合。

[0072] 路径上的最后一跳节点收到其他节点的可占用时隙集合后，从0号时隙开始，根据节点号升序遍历节点的可占用时隙集合，节点i的可占用时隙集合为Uia，假设时隙0∈Uia，则将节点i添加至时隙0的可分配点集合S0k。划分节点集合Sjk时，根据两跳内时隙不冲突原则和路径信息，使得每一个节点集合Sjk中的只有一个点可被分配时隙j，假设节点1、2、3只能有一个节点占用时隙0，节点7、8、9只有一个时隙可以占用时隙0，同时，根据TDMA自组织网中两跳外节点可以复用时隙得出节点1、2、3对时隙0的占用不影响节点7、8、9对时隙0的占用，则节点集合{1,2,3}和节点集合{7,8,9}为时隙0的两个可分配节点集合，获得所有时隙的所有可分配节点集合后，按照节点集合内点的个数进行排序，集合内节点的个数相同时，按照时隙号升序排列。

[0073] 步骤3：为业务流路径上的节点分配时隙：

[0074] 3.1)初始化分配轮次n为1，清空分配给节点的时隙集合di，置时隙个数ni为0，置N的值为路径上节点的个数，执行3.2)。

[0075] 3.2)开始第n轮的分配过程，置预删除点集的个数d为0，将遍历位置重置到第一个集合，执行3.3)。

[0076] 3.3)从遍历位置遍历点集合，直至集合Stk中存在节点i，使得ni

[0077] 3.4)遍历路径上所有节点，将满足ni

[0078] 3.5)遍历Sl，设点i∈Sl。遍历预删除标志为1的点集合，判断是否存在含节点i的集合：若是，将含有点i的所有集合添加至大集合Si，执行步骤3.6)；否则，执行步骤3.11)。

[0079] 3.6)遍历Si，设集合Stk∈Si，遍历集合Sp，得到预占用时隙为t的节点j，遍历所有预删除标志位为0的节点集合，判断是否存在含节点j的集合：若是，执行步骤3.7)，否则执行步骤3.8)。

[0080] 3.7)设j∈Smk，将节点j的的预占用时隙置为m，节点i的预占用时隙置为t，将Stk的预删除标志置为2，将Smk的预删除标志置为1，将ni的值加1，d的值加1，将点i从集合Sl删除，判断Sl是否为空：若是，执行步骤3.9)；否则，执行步骤3.5)。

[0081] 3.8)将节点集合Stk从Si中删除，判断Si是否为空：若是，执行步骤3.11)；否则执行步骤3.6)。

[0082] 3.9)将每个节点的预占用时隙添加至对应点的时隙集合di，执行步骤3.11)。

[0083] 3.10)将分配轮次n的值加1，将每个节点的预占用时隙添加至对应点的时隙集合di，将所有节点预占用时隙置为无，删除预删除标志位不为0的所有点集合。判断n是否和业务流所需时隙nc相等，若是，执行步骤3.11)，否则，执行步骤3.2)。

[0084] 3.11)记录每个点此次分配过程的分配结果di，将分配结果通知路径上的相应节点，分配过程结束。

[0085] 其中，当本节点需要通知路径上其他节点计算结果时，路径点集合S0经步骤1已传递至本节点，将本节点的分配结果保存，用来预约相应的时隙。将路径上其他节点的分配结果发送至上一跳节点，其他节点收到分配结果后，将自己的分配结果保存，并从数据帧中删除，将处理后的分配结果继续发送至上一跳节点，直至业务流的源节点。

[0086] 本发明是在业务流路径的最后一跳节点进行路径节点预约时隙的决策，当对应节点收到决策指令后，在一个节点的检测周期内计算整个路径所有节点的分配结果，业务流的检测仅在源节点进行，无需每个节点单独检测，缩短了路径资源分配的时间。

[0087] 本发明是以业务流路径为对象按轮次分配时隙，计算业务流路径上每一个节点所需预约的动态时隙，当路径上某节点的可用时隙不足，无法满足业务流的速率时，其他节点只需要预约该瓶颈节点可预约的数目的时隙即可，而无需以业务流的速率预约时隙，减少非瓶颈节点无效的时隙资源占用。

[0088] 本发明从路径的角度在节点间协商共享时隙资源的分配，通过全路径按轮次分配的方法，避免非瓶颈节点上的无效资源分配，以及分布式时隙测了把导致的资源冲突，从而提高了时隙资源的利用率和端到端的QoS的保障能力。

[0089] 简而言之，本发明公开的TDMA自组网中基于业务流路径的动态时隙分配方法，主要解决多跳路径传输时动态时隙分配时间过长，非瓶颈节点占用无效时隙的问题。其方案是：在业务流的源节点检测业务特性，将路径上每个节点的动态时隙占用情况汇总到业务流路径上的最后一个节点进行所有节点的时隙分配；采用按轮次分配的方式，保证分配完成后路径上所有节点分得的动态时隙个数是相等的，按轮分配时采取一步回退的方式，增大瓶颈节点的可占用时隙个数。本发明设计包含源节点检测业务流特性，路径上最后一跳节点汇总路径上各节点信息进行时隙的分配，缩短业务检测和时隙分配的时间，提出按轮次分配和一步回退的方式，避免了木桶效应，提高了时隙的利用率，增加了端到端的吞吐量，可广泛用于TDMA自组织网络中的时隙分配。