基于动态时隙分配的无线Mesh网络低时延优化方法

摘要

本发明提供一种基于动态时隙分配的无线Mesh网络低时延优化方法，在Mac算法架构设计中控制帧中通过改变节点的广播顺序，使得节点能够根据数据流的路径信息及时更新自己的时隙需求，保证转发节点在时隙分配时获得相应的时隙；在时隙竞争阶段通过调整网络中时隙申请的顺序，为相关数据流添加路径信息，完成了网络节点时隙竞争阶段的时隙需求实时更新，提高了针对数据流的时隙分配的实时性。通过广播时段对网络拓扑信息变化的及时更新，使得节点对网络拓扑变化能够及时感知并进行更新，通过对关键拓扑数据的处理使得控制协议的开销得到了降低，提高了整个网络的数据传输效率。

说明书

技术领域

本发明涉及无线网状Mesh网络技术领域，特别涉及一种基于动态时隙分配的无线Mesh网络低时延优化方法。

背景技术

无线Mesh网络一般采用载波侦听多路访问CSMA随机资源调度架构或时分多址TDMA资源调度架构。其中CSMA架构虽然网络可扩展性较强，但无法解决隐藏终端问题，而且碰撞概率随着网络节点数目增加而变大，无法提供端到端时延上的保证。TDMA资源调度架构将信道资源按照时间分成多个时隙来进行资源调度，协议设计上较为清晰，通过控制协议的交互并能够解决隐藏终端问题，但传统的TDMA资源调度架构中Mac和路由算法没有考虑到Mesh网络中多跳数据流与时隙分配的实时性问题，在时隙分配效率和路由效率上都存在改进的空间。

对于分布式调度架构的无线Mesh网络，采用基于时分的周期循环接入调度机制在保证数据端到端时延上有着随机接入调度和伪随机接入调度机制不具备的优势。为了提高信道资源，即时隙的复用率，针对无线Mesh网络的低时延调度架构的设计一般都采用基于TDMA的资源调度架构。

传统的TDMA资源调度架构Mac层分为采用固定时隙分配和动态时隙分配两种信道资源分配方法，固定时隙分配为Mesh网络中每个节点分配一个或多个固定的时隙，在工程实现上简单清晰，但没有考虑到不同的节点时隙需求不一的情况，存在时隙利用率不高，端到端时延无法保证问题。动态时隙分配不为节点指定固定时隙的数量和位置，而是根据时隙需求、业务类型等来动态分配时隙的数量、位置，一种时隙优先级的设计可以用来解决时隙位置时的冲突问题，该设计根据每个节点对时隙的不同优先级可以确定在需要多个时隙分配时除了优先级最高主的时隙外还可以分到其它不同优先级的时隙，针对Mesh网络数据流的特点，在不同时帧采用不同时隙优先级设计可以对端到端时延进行性能上的优化。

传统的动态时隙分配通过所有节点先申请后动态分配的方法在一定程度上提高了时隙利用率，但在分配时没有考虑到数据流中转发节点的时隙需求问题，因此无法保证数据流中本时帧内转发节点时隙分配的实时性，往往无法保证需多跳转发的数据的端到端时延。

申请号为201310108812.3的专利公开了一种基于时分复用的信道资源分配方法。通过将每个时隙分为控制部分和数据部分，控制部分通过对时隙竞争信息两跳范围的广播和数据优先级来进行信道的无碰撞时隙分配，该时隙分配方法中未考虑数据流转发节点的时隙需求，因此不能够充分利用时隙资源，在端到端时延、网络吞吐量等性能上有改善的空间。

申请号为201510906203.1的专利公开了一种基于TDMA的无线MESH网络分布式资源分配的方法。具体地，节点在数据发送之前先按固定的顺序进行时隙需求两跳邻居内的广播，然后根据节点的时隙需求和负载来进行时隙资源的动态分配，该发明在数据发送时隙根据不同数据流路径来选择发送时隙，在一定程度上对数据流的发送时延性能进行了提升，但在时隙分配时也没有考虑到数据流转发节点的时隙需求，并不一定能够保证转发数据流的时隙需求。

无线Mesh网络路由算法选路的重要依据是网络拓扑，对于节点快速移动、网络拓扑高动态变化的无线Mesh网络，拓扑更新必须相应的加快，但完整、详细的网络拓扑的获取往往建立在越来越大的控制协议开销上，传统的分布式无中心Mesh网络往往采用对所有拓扑进行洪泛广播的方式来进行拓扑更新，占用了大量宝贵的带宽，而且因为拓扑中链路不同的建立时间往往没有被考虑在内，不能保证拓扑更新的有效性，从而对路由算法的正确执行造成了不利影响。

无线Mesh网络路由算法按照选路时机分为启发式路由和先验式路由。传统的先验式路由算法只考虑网络链路拓扑，按照路径的跳数距离选择最短路径，并没有结合TDMA中Mac层为节点所分配的时隙先后顺序来计算路由判据，所选择的跳数最短路由并不一定能保证是最优路由，造成数据传输时间极大的增加。传统的启发式路由只考虑到选路时拓扑的信道分配状态，没有针对动态时隙分配节点即将所获得的时隙计算路由判据，因此也不能保证获得最优路由。

申请号为201310108812.3的专利公开了一种多射频多信道无线Mesh网络路由选择方法在设计选路判据时考虑了路径中转发节点的负载和路径的期望传输时间ETT，但在ETT的设计时只是根据链路的数据递交率来进行计算，并没有考虑到基于TDMA的无线Mesh网络在传输时延上的时隙分配依赖性质，因此并不适合基于时隙分配的无线Mesh网络路由判据设计。

传统的无线Mesh网络在架构设计时往往将网络层路由算法与Mac层分开设计，以减轻架构设计的复杂度，但没有考虑到基于动态时隙分配的信道调度架构具有对路由的依赖性这个特点，往往会造成路由算法对Mac层的支持度不够，因此在针对低时延的无线mesh网络架构设计上还有优化的空间。

发明内容

本发明所要解决的技术问题是，提供一种基于动态时隙分配的特点对无线Mesh网络的媒质接入控制MAC进行优化的方法，另外基于MAC的优化，之后还提供了一种路由优化方法。

本发明所要解决的技术问题是，基于动态时隙分配的无线Mesh网络低时延优化方法，其特征在于，无线网状Mesh网络内各节点以时帧为周期完成时隙分配；所述时帧包括广播1时段、广播2时段与数据帧时段；广播1时段包括N个广播1时隙，广播2时段包括N个广播2时隙，数据帧时段包括大于等于N个的数据帧时隙，N为无线Mesh网络中最大节点数；各节点在数据帧时段对应有一个数据帧时隙为该节点的主时隙；各节点在不同时帧中由节点时隙优先级表所指定的主时隙顺序不同；

各节点在广播1时段与广播2时段按照其在当前时帧的主时隙顺序被对应分配一个广播1时隙与一个广播2时隙；各节点在每一时帧中按照当前的主时隙顺序广播本节点与邻居节点的时隙需求与拓扑变化来进行时隙的动态分配：

1)广播1时段，广播时隙需求：

各节点生成第1广播控制帧，并在对应的广播1时隙中广播本节点的第1广播控制帧，第1广播控制帧包括节点ID、待发送数据的总大小和待发送的各数据流信息，数据流信息包括数据流的数据大小和各数据流发送优先级以及各数据流剩余路径信息，待发送数据的总大小为本地广播数据缓存中待发送的各数据流的数据大小之和；本地广播数据缓存中包含有当前节点作为源节点所要发送的数据流信息与当前节点作为中间节点所要转发的数据流信息；当出现待发送的数据流信息过多使得节点的第1广播控制帧的长度超过广播1时隙发送数据的最大数据长度时，该节点则按数据流发送优先级从大到小的顺序将最大数据长度内的数据流信息放入第1广播控制帧；

数据流发送优先级w的计算方法为：

w＝α·stream_Length+β·ETT+(1-α-β)·prior

其中，ETT为路径预期发送时间，prior为数据流的业务优先级，stream_Length为该数据流的数据大小，α、β∈[0,1]且α+β≤1，分别代表数据流的数据大小和路径预期发送时间的权重系数；

各节点收到其他节点发送的第1广播控制帧后，根据接收到的第1广播控制帧进行本地拓扑信息表的更新，根据第1广播控制帧中的节点ID将该节点加入到本地维护的一跳邻居信息表中，同时根据接收到的第1广播控制帧中数据流剩余路径信息查看本节点是否为该数据流的下一个转发节点，若是，则将该数据流的数据流的数据大小和各数据流发送优先级以及各数据流剩余路径信息加入到本地广播数据缓存中，若否，则将该条数据流信息丢弃；

2)广播2时段，广播邻居节点时隙需求和拓扑变化：

各节点生成第2广播控制帧，并在对应的广播2时隙中广播本节点的第2广播控制帧，第2广播控制帧包括节点ID、邻居节点ID、待发送数据的总大小、网络拓扑数据与网络拓扑变化数据；当出现网络拓扑数据过大使得第2广播控制帧的总长度超过了节点在广播2时隙发送的最大数据长度时，该节点则对根据本地拓扑信息表对网络拓扑数据进行关键拓扑选择，在广播2时隙发送的最大数据长度内选择关键拓扑加入到第2广播控制帧中；

各节点在收到其他节点发送的第2广播控制帧后，根据接收到的第2广播控制帧中的节点ID更新到本地两跳范围内邻居列表中，并根据第2广播控制帧进行本地拓扑信息表的更新；

3)数据帧时段，动态时隙分配：

根据本地两跳范围内邻居列表中的邻居节点所对应的待发送数据的总大小得到本节点在当前数据帧时段需要的数据帧时隙数量：

若节点在本时帧没有数据要发送和转发，则不分配数据时隙给该节点，将该节点对应的主数据帧时隙作为空闲时隙；若节点只需要1个数据帧时隙，则将本节点在本时帧周期所属的主数据帧时隙分给本节点；若本节点需要2个以上的数据帧时隙，则根据节点时隙优先级表进行空闲时隙竞争；若节点被分配到2个以上的数据帧时隙，在进行数据发送时，节点优先发送能够在本时帧被转发的数据；节点在1个数据帧时隙内按照数据流发送优先级从大到小的顺序发送数据流。

进一步的，还提供给了一种新的本地拓扑信息表更新、关键拓扑选择方法。

另外，各节点在一个时帧内完成时隙分配之后进行路由选择，路由选择参考节点时隙优先级表中的主时隙顺序。

路由选路的具体步骤为：

S1：检查是否为本时帧第一次运行选路算法，若是，则清空路由集合和转发负载表，执行步骤S2，否则执行步骤S3；

S2：根据广播2时段获取的网络拓扑数据计算本节点在一个时帧内可以到达的网络范围，并将该范围内所有节点加入到路由集合中，路由集合包含到达节点的ID、到达节点的最短ETT的路径，若目的节点不在路由集合，转至步骤S3，若目的节点在路由集合中，则寻路成功，为该数据流添加该路径信息，将该数据流存放到待发送数据缓存中，同时根据数据流大小对转发负载表中该路径的中转发节点的负载进行更新；

S3：根据广度优先顺序遍历路由集合中的每个目的节点，结合下一个时帧的节点时隙优先级表中的主时隙顺序和节点的负载情况计算两个时帧内可以到达的节点；广度优先顺序遍历为树与图的数据结构中的常用遍历方法；

S4：重复步骤S3过直到目的节点被加入到路由集中完成寻路或寻路失败，若完成寻路则为目的节点所对应的数据流添加路径信息，若寻路失败则将目的节点所对应的数据流放入寻路失败的数据流缓存中。

本发明在Mac算法架构设计中控制帧中通过改变节点的广播顺序，使得节点能够根据数据流的路径信息及时更新自己的时隙需求，保证转发节点在时隙分配时获得相应的时隙，提高了信道资源的利用率，降低了数据流的发送时延。

本发明在时隙竞争阶段通过调整网络中时隙申请的顺序，为相关数据流添加路径信息，完成了网络节点时隙竞争阶段的时隙需求实时更新，提高了针对数据流的时隙分配的实时性。通过广播时段对网络拓扑信息变化的及时更新，使得节点对网络拓扑变化能够及时感知并进行更新，通过对关键拓扑数据的处理使得控制协议的开销得到了降低，提高了整个网络的数据传输效率。通过根据数据流的大小、路径ETT、业务优先级不同属性进行数据流发送优先级的计算，满足不同的网络服务质量QOS业务需求。

本发明在路由算法中，通过一种结合时隙分配表的贪婪算法，结合时帧周期中广播阶段及时更新的网络拓扑信息，并考虑路径节点负载，能够为数据流寻找到最短时延的传输路径，同时达到了负载均衡的目的，提高了整个网络的吞吐量。路由算法根据动态时隙分配表进行数据流发送路径的选择，Mac层控制帧结合动态时隙分配算法为数据流负载节点及时更新时隙需求，Mac层与路由算法跨层协作完成数据发送，这种架构设计极大的降低了数据流的端到端时延，保证了低时延设计的实现。

本发明的有益效果是：提高了整个网络在数据吞吐量、端到端时延、负载均衡方面上的性能，显著提高无线Mesh网络的信道资源利用率，降低网络的端到端时延，适用于通信资源调度采用TDMA模式的无线Mesh网络场景，满足高动态、低时延的无线Mesh网络架构设计。

附图说明

图1为本发明的架构设计流程图；

图2为周期循环调度架构超帧图；

图3为Mesh网络示例图；图4为拓扑更新流程图；

图5为路由算法流程图。

具体实施方式

下面结合附图进一步详细描述本发明的技术方案，但本发明的保护范围不局限于以下所述。

本发明的优化流程结构如图1所示，在路由算法执行之前要先在Mac层完成拓扑更新，这是保证路由有效性的重要基础；同时因为数据流的发送路径中转发节点需要发送时隙，所以本时帧路由算法是下个时帧数据流在Mac层进行的时隙分配的基础，这就要求在基于本流程进行低时延设计时Mac与路由算法要协同设计。

如图2所示，基于动态时隙分配的无线Mesh网络周期循环调度架构可以将时隙这种信道资源根据功能看作不同的帧，一个超帧由L个时帧构成，其中L≥N，根据网络需求、时隙优先级表的设计进行取值。

每个时帧分为3部分，即广播1时段、广播2时段、数据帧时段，其中广播1时段和广播2时段通常可以被统称为控制帧时段。广播1时段和广播2时段都分为N个时隙，保证每个节点在有一个时隙来进行控制信息的广播，具体时隙长度可以根据网络的规模、拓扑特点、业务需求来设计，数据帧分为M个时隙，M≥N，保证每个节点拥有一个属于自己的主时隙。各节点在数据帧时段对应有一个数据帧时隙为该节点的主时隙；各节点在不同时帧中节点由时隙优先级表所指定的主时隙顺序不同。

M可以根据网络对传输效率η的需要来设计，η由下面公式给出。

其中，time_broad1为广播1时段中的时隙长度，time_broad2为广播2时段中的时隙长度，time_deta为数据帧时段中的时隙长度，时隙长度均包含了保护间隔。

动态时隙分配的流程是：在控制时隙节点按一定的次序轮流将自己的待发送数据大小和邻居的待发送数据大小广播出去，运用一种时隙分配算法来完成时隙分配，使得各节点在没有信道冲突的情况下获得足够的时隙资源。这种时隙分配算法会结合节点时隙优先级表来进行，为保证网络的信道均匀、公平，在每个时帧都会对时隙优先级表做出一定规律的、可预测的调整，其结果就是每个时帧中节点的主时隙都会变化，而主时隙是节点在有时隙需求时固定要分配的时隙，根据这种动态时隙分配算法，对无线Mesh网络端到端时延在Mac层可以进行以下分析。

如图2所示，当数据流路径为单跳时，数据端到端时延只有物理层上的传输时延，传输时延相比转发时延一般可以忽略不计，为便于分析，将物理层上的传输时延设为0。转发时延要根据转发节点收到数据之后本时帧内是否存在数据时隙分为两种情况,即转发时延T_relay如公式(2)所示：

其中，T_relay(i，j)表示节点j为数据流发送路径中节点i下一跳时的转发时延，单位为数据时隙，Slot(j)表示转发节点j所分配的数据时隙编号，Slot(i)表示数据节点i所分配的数据时隙序号，Slot_next(j)表示下一时帧节点j的所分配的最小时隙序号，M表示一个时帧所划分的时隙数量。

由此公式(2)可知，若要降低数据流的转发时延，数据流的路径顺序应尽量按照转发节点的数据时隙顺序来设计，而在Mac层进行时隙分配之前必须将转发节点所需时隙信息进行广播，以保证转发节点能够获得数据时隙，否则该转发节点的转发时延将不得不增加若干个时帧周期的时间。因此为了保证数据流发送路径中的转发节点能够按照这种时隙需求，在采用动态时隙分配的TDMA调度架构设计的无线Mesh网络中必须从Mac算法和路由算法上同时考虑，具体设计目标如下：

首先，Mac层的架构设计要保证数据流转发节点的时隙需求能够得到及时更新，同时维护一个与网络属性相匹配的拓扑更新速度，保证转发节点数据时隙顺序在符合本时帧内转发需求的情况下能够及时获取时隙需求信息，这样才能够完成针对多跳数据流有效的时隙分配。

其次，数据流在网路层路由算法的选路阶段就应考虑路径中转发节点的时隙顺序问题，这样才能保证上述Mac层架构设计的有效执行。

针对以上分析，本发明采用以下所述步骤完成一种基于动态时隙分配的无线Mesh网络低时延MAC与路由架构设计。每个节点以时帧为周期，在每个时帧内在TMDA信道模式下基于动态时隙分配完成Mac与路由的设计。

S1：广播1时段，按主时隙顺序进行广播本地节点的时隙需求，包括以下子步骤：

S11：每个节点按照自己本时帧内的主时隙顺序广播自己数据流的时隙需求；

广播数据broad1_Data中包含自己的节点ID、待发送数据的总大小Data_Length、待发送数据流的数据大小stream_Length和数据流发送优先级w以及数据流剩余路径信息path，若有多个数据流造成广播broad1_Data长度超过广播时隙能够发送的最大数据长度，则根据数据流的业务优先级prior以及数据的大小stream_Length、路径预期发送时间ETT进行数据流的发送权值w大小进行排序并选择权值大的数据流信息加入广播数据中，这样既能保证不影响通知剩余的转发节点更新时隙需求信息，又能减少一定的控制协议开销，其中数据流的发送权值w按照下面公式来计算：

W＝α·stream_Length+β·ETT+(1-α-β)·prior (3)

其中α、β∈[0,1]，且α+β≤1，分别代表stream_Length和ETT的权重系数，路径预期发送时间ETT由路由层在为数据选路时计算得出，业务优先级prior则根据网络提供业务类型和服务需要来计算。α、β的取值可以根据Mesh网络的拓扑特点、主要数据类型、业务需求来灵活设置。比如当α＝1时表示只考虑数据大小，不考虑数据流路径路径预期发送时间ETT和数据优先级；而当β＝1时表示只考虑数据流路径路径预期发送时间ETT，不考虑数据大小和数据优先级；当α＝β＝0时表示只考虑数据类型所具备的优先级；其它情况可以照此分析。

一个时隙能够发送的最大数据长度max_Length按下面公式(4)计算。

max_Length＝time_slot·Band_phy(4)

其中，time_slot为时隙长度，Band_phy为节点物理层所提供的带宽。

在进行broad1_Data的构造时，节点可以根据本时帧内的节点时隙优先级表进行数据流信息的筛选，如果数据流路径中本节点下一条转发节点已经广播了broad1_Data数据，说明该数据流不会在本时帧内被下一条转发节点主时隙转发，下一条转发节点并不一定有其它能够完成转发的时隙，所以认为该条数据流不符合纳入broad1_Data进行转发告知的条件。

待发送数据的总大小Data_Length表示在待发送缓存中本节点的待发送数据大小，以字节为单位。数据流剩余路径信息path包含从本节点下一跳开始的剩余路径。

S12：节点在收到其他节点发送的第1广播控制帧broad1_Data后，节点要完成两部分内容的更新。1)根据第1广播控制帧broad1_Data中的节点ID将该节点加入到自己所维护的一跳邻居信息表中，这样在广播1之后，所有的节点都会获取到自己的一跳邻居节点。

2)同时根据第一广播控制帧broad1_Data中数据流剩余路径信息path查看自己是否为该数据流的下一个转发节点，若是则将该数据流的数据大小stream_Length、剩余路径path、数据流发送权值w信息加入到本地广播数据缓存中，否则表示本节点不需要转发该数据流，将该条数据流信息丢弃。节点在属于自己的广播1时隙将本地广播数据缓存中的信息以及自己作为源节点的数据流信息作为第1广播控制帧broad1_Data广播出去。

节点在收到其他节点发送的第1广播控制帧broad1_Data后，进行本地拓扑信息表一跳邻居更新。

对于一个节点来说，如果已经完成了S11步骤，表示它的主时隙排在其余未广播的节点主时隙之前，它不会承担主时隙排在其之后的其余节点的数据流转发任务，那么在本步骤中它只需要完成上述内容1)所述部分的工作，即更新邻居节点，这从步骤S11中broad1_Data的筛选流程分析也可以看出。

考虑图3中的拓扑情况，假设本时帧内各节点的主时隙即为节点ID，则节点3在完成了自己broad1_Data的发送后，在接下来的广播1时隙中，其不会作为转发节点出现在剩余节点4、5、6、7、8的broad1_Data的数据流路径中，因为其数据主时隙3在节点4、5、6、7、8的数据主时隙之前，此时节点3只需根据broad1_Data来更新自己的邻居信息。

即在本节点还没有广播出自己的broad1_Data数据时，每收到一个broad1_Data它都需要完成上述内容1)、2)的所述工作，而当它完成了broad1_Data广播后只需要完成内容1)所述工作，这样就可以可以减少很大一部分节点的数据处理量。

从上述分析还可以看出，一个节点的主时隙顺序越靠后，该节点承担转发任务的概率就越大，因此在一个超帧中不同时帧采用不同的主时隙顺序能够起到一定的负载均衡作用。

S2：广播2时段，按主时隙顺序在自己的广播2时隙中广播邻居节点时隙需求和拓扑变化信息，包括以下子步骤：

S21：邻居节点时隙需求和拓扑变化承载于第2广播控制帧broad2_Data中，时隙需求通过待发送数据的总大小Data_Length体现，拓扑变化通过网络拓扑数据topology和网络拓扑变化topology_change体现。每个节点按照自己本时帧内的主时隙顺序广播自己邻居的时隙需求信息，同时根据自己的邻居信息来广播自己所维护的网络拓扑数据topology、网络拓扑变化topology_change。第2广播控制帧broad2_Data中包含自己的节点ID、邻居节点ID及待发送数据总大小Data_Length、网络拓扑数据topology和网络拓扑变化topology_change，若broad2_Data数据的总长度超过了该广播时隙能够发送的最大数据长度，则对拓扑数据进行压缩，选择关键拓扑数据加入到广播数据broad2_Data中。

S22：节点在收到邻居发送的broad2_Data后，根据broad2_Data的时隙需求信息将这些邻居节点信息更新到自己的两跳范围内邻居列表中，同时根据这些邻居信息和拓扑数据更新自己所维护的拓扑信息表topology_Table。

在topology_Table的设计中为每条链路附一个权值TL(Time of Living)表示该链路信息获取的新旧程度，该TL值定义如下式所示：

另外，对于本架构设计中的无线Mesh网络节点，节点维护一张的拓扑信息表topology_Table，表示节点所探知的周围网络拓扑情况，具体拓扑信息表topology_Table的数据结构采用邻接矩阵表示。为了降低拓扑更新数据占用的带宽，分以下两种情况处理：

一是而当节点的一跳邻居节点中出现新节点时，采取将全部拓扑数据广播的方式进行拓扑告知，这是因为当邻居中出现新节点时，表示该新节点没有收到过本节点之前广播的拓扑信息，所以无法在之前的基础上进行变量的叠加更新，所以必须发送全部拓扑信息。由于邻居的时隙需求信息中已经包含了一部分拓扑信息，所以这里topology_Table可以将邻居的时隙需求信息中那部分拓扑去除，以节省拓扑信息占用的信道带宽。另外，对于在本时帧内获取的拓扑进行单独标识，表示这部分拓扑具有更高的可信度。

由于topology_Table是一个图的数据结构，图是顶点与边的集合，即Graph{Vertex,Edge}。在图的数据结构表示中，邻接矩阵表示结构直观清晰，查找、插入算法简单，占用的数据存储空间网络中节点数平方正正比。邻接表数据结构表示占用数据大小随着拓扑图的节点数和图的连通度成正比，因此比采用邻接矩阵数据结构表示占用的存储空间要小，但查找速度没有邻接矩阵数据结构表示快。综上，在节点所维护的本地拓扑数据采用邻接矩阵数据结构来表示，这样可以降低在处理拓扑相关的一些算法的时间复杂度，而broad2_Data中的拓扑数据采用邻接表数据结构表示，以降低控制协议的开销。

二是当节点的一跳邻居节点中没有出现新节点时，采取只须对广播拓扑变化信息topology_Change的进行广播告知，这样邻居节的可以在之前接收到该节点发送的拓扑信息基础上完成拓扑更新并且减少广播的拓扑数据大小。拓扑的变化体现在拓扑图中边的添加或减少上，对应无线Mesh网络中链路的建立、和丢失，所以topology_Change的数据包含两种类型的边，增加的边和减少的边。

在S1步骤中节点可以获取到自己周围的一跳邻居节点信息以及这些一跳邻居节点针对数据流及时更新了的时隙需求信息，那么在广播2时段将这个信息广播出去，当邻居节点收到自己周围邻居发送的这个信息后就可以得知自己2跳范围内的邻居信息及其时隙需求，这就构成了动态时隙分配的数据基础。

根据broad2_Data中的拓扑数据进行拓扑更新的步骤如图4所示：

(1)广播1时段开始时对topology_Table表中所有不为0的TL加1，表示所有拓扑的探知时间增加了1个时帧；

(2)根据广播2时段所接收到的S21中所述的neighbor_Info更新两条范围内的拓扑，这些拓扑的TL值为1；

(3)在广播2时段接收到广播数据broad2_Data时，根据其中的邻居信息、拓扑信息(topology或topology_Change)更新拓扑，在更新时采取以最新的拓扑为准，只有当接收到的拓扑TL值比本节点的topology_Table中的TL值小的时侯或本节点的topology_Table中的TL值为0的时候才会更新，表示以最新探知的链路为准，当收到删除链路<m,n>的拓扑信息时，将TL_mn置为0即可。

(4)根据实际网络拓扑的实际变化特点，为TL设置一个阈值TL_max，当拓扑中TL值超过TL_max表示该拓扑已经有TL_max个时帧未更新，可以认为该链路已经过期无效，将其对应的TL值置0。

根据上述拓扑更新算法以及topology_Table的定义，可以看出TL值越小表示该拓扑实时性越强，这样，本发明根据topology_Table来设计关键拓扑的定义，以便于在进行拓扑数据广播时进行合理选择。即关键拓扑数据以下面所述步骤来选择：

(1)以本节点为源节点，以topology_Table中非0的TL值为边的权值，采用图论中prim最小生成树算法构造最小生成树，该最小生成树中的所有拓扑为优先级最高的关键拓扑数据，根据最小生成树定义，如果拓扑为连通图，此时会选择N-1条边表示的链路，若拓扑为非联通图，本节点所在的连通子图节点数为K，则会选择K-1条边；

(2)需删除的拓扑：需要删除的拓扑一定是本节点通过广播1发现的某些不再是自己邻居的节点，是实时性最强的拓扑，因此也是关键拓扑信息；

(3)剩余拓扑中TL值越小该拓扑越关键；

(4)删除通过以上三个步骤所获取拓扑数据中的1跳范围内拓扑，因为1跳邻居的拓扑信息已经在“邻居时隙需求信息”中包含，所以这里不用重复包含。

按照(1)、(2)、(3)、(4)的先后顺序来构建关键拓扑信息，直到topology_Table中的拓扑数据被完全覆盖或broad2_Data大小已达一个广播2时隙最大能发送的大小。

S3：广播2时段，根据及时更新了的时隙需求信息进行动态时隙分配，包括以下子步骤：

S31：根据S2步骤中获取的两条范围内的邻居时隙需求信息，计算本节点所能够分到的时隙数量；

S32：若本节点在本时帧没有数据要发送和转发，则不分配数据时隙给本节点；若本节点只需要一个数据时隙，则将本节点在本时帧周期所属的主时隙分给本节点；若本节点能够分到的数据时隙超过一个，则按照节点对剩余可分配节点时隙的优先级选择所需数量的数据时隙分给本节点；

S33：若节点分配的时隙多余1个，在进行数据发送时，优先发送能够在本时帧被转发的数据。

S4：根据时隙分配优先级表进行数据流的路由选择，如图5所示，包括以下子步骤：

S41：检查是否为本时帧第一次运行选路算法，若是，则清空路由集合Set_Path<>和转发负载表relay_Load[]，执行S42步骤，否则执行S43步骤。

S42：根据步骤S2所获取的网络拓扑信息运行计算本节点在一个时帧内可以到达的网络范围，并将该范围内所有节点加入到路由集合Set_Path<>中，其中应包含到达节点的ID、到达节点的最短ETT路径path，若目的节点不在Set_Path<>内，转至S43。否则，寻路成功，为该数据流添加该路径信息，将该数据存放到待发送数据缓存中，同时根据数据大小增加路径中转发节点的负载relay_Load。若否则进入下一步。

S43：根据广度优先顺序遍历Set_Path<>中的每个节点，结合下一个时帧时隙分配优先级表的主时隙顺序和节点的负载情况，计算两个时帧内可以到达的节点。为避免路由中出现环路，在计算路径的下一跳节点时，该下一跳节点必须从Set_Path<>的补集中选取，将该节点纳入Set_Path<>，同时将Set_Path<>遍历过的节点标记，以免重复遍历。为避免负载过于集中于某些转发节点，当转发节点的负载超过一个数据时隙所能发送的数据长度的一定比例λ时，也将该节点标记，在以后的选路过程中将不再考虑该节点，除非该节点在网络中处于到目的节点的路径的必经位置或所有可用转发节点均已超出负载。

其中λ的取值网络拓扑的连通度、节点位置、网络的业务属性相关，应视具体情况而定，例如在图3的mesh网络拓扑中，如果节点1到节点3的路由中，节点5为割点，则其必为路径的转发节点，所以就不用考虑λ，而对于其它转发节点，比如节点4和节点7，则可以考虑λ以达到负载均衡的效果。

S44：重复S43过程直到目的节点被加入到Set_Path<>中，为该数据流添加路径信息，该数据流寻路完成，若拓扑中本节点所在的联通子图中所有节点都已经加入到Set_Path<>中，仍没有目的节点，表示寻路失败，将该数据流并放入寻路失败数据流缓存中，并将寻路次数加1，本时帧内不再为该数据寻路。即本发明采用的寻路策略是一种贪婪算法，保证了每次寻找的结果总是ETT最小的路径。

S45：当本时帧内有到新的目的节点的数据流产生时，首先查询目的节点是否已经在Set_Path<>中，若不在则跳转至S43步骤，按广度优先顺序继续遍历未标记过的节点；若在则根据路径的已有负载检测该路径是否能够负载该数据流的传输，若能则将其路径信息直接加入到该数据流，更新转发节点负载，并将该数据流加入待发送数据缓存中；若不能则从路径失效节点的前一节点开始为该数据流重新寻路，若可用转发节点均已超出负载，则以可用转发节点的下一个时帧主时隙顺序作为寻路算法的依据。

考虑在图3的mesh网络拓扑，假如节点8有向节点5发送的数据，当前路由Set_Path<>中有8-7-4-5的发送路径，但节点4负载已经超出，则从路径中节点4之前的节点7继续遍历寻找到节点5的路由，若节点7的负载也超出，则在计算ETT时，选择节点5和7的下一时帧主时隙作为计算的依据。

S46：查看数据流缓存是否为空，如否，则对本时帧之前产生的数据流进行重新寻路，重新寻路成功则将该数据流取出添加到待发送数据缓存中，如是，则将其寻路次数加1，本时帧不再为该数据寻路，当寻路次数超过一个数值time_Failuer后，表示该数据流寻路失败，丢弃该数据。time_Failuer的设置一般和阈值TL_max对应，和网络拓扑变化的属性相关。

S5:新的时帧开始后，按照本时帧内节点主时隙顺序进入S1步骤开始新一轮Mac和路由算法的执行周期。