6TiSCH分布式网络调度

叶小林

(上海理工大学 光电信息与计算机工程学院，上海 200093)

0 引言

目前，国外已经成立了6TiSCH工作组(WG)[1-3]。6TiSCH工作组(WG)将TSCH功能与6LoWPAN、ROLL标准化工作及建议联系起来。详细地讲，它将定义一个开放的基于标准的架构，尽可能重用现有协议，如邻居发现(ND)[4]、边界路由、分布式网络调度(OTF)[5-6]和路由问题(RPL)[7]等。时隙跳频(TSCH)模式是低功耗有损网络(LLN)最新一代超低功耗和可靠网络解决方案，其核心是采用时间同步媒体接入技术，实现超低功耗、信道跳频和高可靠性[8]。

IEEE802.15.4e标准没有定义如何构建调度表，也没有强调如何与网络流量要求相匹配[9]。OTF带宽预留模块起到补充作用,它用一个分布式方法调整预定带宽与网络要求。OTF决定何时添加/删除单元格(cell)，然后6Top子层对6TiSCH时间表进行适当更改[10]。本文重点是改进分布式调度算法[11-13]，主要为了解决多邻居之间信息交流、网络中突发流量问题和多跳网络中广播问题而设计。 RPL(低功耗和有损网络的路由协议)将网络组织为DODAG拓扑结构(面向目的的有向无环图)，每个节点生成的数据被转发到其根。调度算法因此试图沿着RPL路由创建有效的6TSCH调度。本文主要贡献在于：通过优化调度算法延长网络整体寿命；使用共享信元减小网络中的冲突。

1 6TiSCH调度机制

6TiSCH允许操作子层(6Top)构建并维护高效的确定性时间-频率调度。6TiSCH网络中的节点遵循时分多址(TDMA)时间表进行通信，其中时隙提供分配给邻居节点之间通信的带宽单位。6TiSCH操作子层(6Top)是6TiSCH架构中一个逻辑链路层，提供6TiSCH中MAC层(IEEE 802.15.4)IP链路的抽象。6Top层支持两步和三步6Top事务用于邻居之间的单元格(cell)协商，目前应用基于两步6Top协商，可以扩展为三步协商。调度功能调用6Top层对内存中数据单元格进行ADD/ DELETE单元格调整，以满足动态带宽需求。根据带宽要求，执行以下步骤:①检查现有6TiSCH时间表以确定可用空闲单元格满足带宽要求；②如果与邻居协商的单元格(cell)可用，则6Top层会给协商邻居发起ADD请求；③接收到6Top ADD请求的相邻节点将检查其6TiSCH调度，以确定所提出单元格列表的可行性；④邻居节点发送一个6Top的ADD响应(包含一个建议的单元格列表)。图1为6TiSCH调度模型。

图1 节点调度模型

6TiSCH机制有两个特点：所有节点都是同步的；使用信道跳变。前者使数据传输更有效率并减少占用时间，后者使数据传输更加可靠。许多分布式6TiSCH调度算法只依赖于基本的6Top随机单元格选择。OTF实现了带宽预留机制，该机制将节点发送的流量与其每个邻居以及相应被调度的单元格进行比较，高于/低于某个阈值，触发协商添加/删除单元格，由此产生的单元格时间表不是无冲突的，如图2所示, D->C、F->G发生冲突。

图2 节点数据转发

2 建议机制

本文目的是对分布式调度算法进行补充，首要目标是合理分配中继节点流量，实现负载均衡，其次是减少数据冲突。在无线传感网络中，节点大多数情况下都由电池供电，提升网络的整体寿命显得尤为重要。图1 中，C作为D和E的中继节点，如果没有相应的分流措施，C节点的能量消耗必然高于边界节点，将导致网络的整体寿命缩短，严重影响网络性能。此时，协商导致D-C、F-G的情况在相同时隙发生，而当两个数据同时被转发时，会产生冲突。如果D能意识到F-G之间的协商，或者F能提前知道D-C之间协商的时间表，就可以有效避免冲突，提升网络可靠性。

2.1 负载均衡机制

对于中继节点流量转发情况，可以通过6Top调度发送数据的节点与邻居进行协商，当邻居节点一直处于信息转发状态(单元格数量一直比较多)而其它邻居无数据可发时，发送数据的节点就可以通过协商平衡流量转发。并且对于一些优先级低、实时性要求不严格的数据，可以通过牺牲时延(寻找路径跳数较多、数据流较少的节点)分散流量，提升网络的整体性能。同时，遇到子节点或者邻居消失的突发情况，通过6Top子层调度及时清理与之有关的单元格，不再转发其数据，实现减少能耗的目标。本文通过与邻居协商实现适当的流量分配，延长网络的整体寿命，使用一个统计计数的方法实现(在优化二进制概率转发模型中加入计数器)。算法如下：

随机数X∈(0，1)，

M为单个节点内存单元存储消息的数据量，随着数据被转发会递减。

初始化，X，count=0，单元格M>0，

{ while(M≠0)

{ 转发到B; count++; M——}

else

{ 转发到C ; count- -; M——}

}

}

2.2 共享信元机制

6TiSCH定义了6Top协议，它允许邻居节点彼此直接协商以在本地修改其通信时间表。然而，节点使用分布式调度并发执行数据传输，并没有考虑邻居的邻居以相同信道和时间表发送数据，因此传输数据会发生冲突。本文机制是节点时间表随着与邻居的协商而更新，通过共享信元广播给那些可以收到数据而不是邻居的节点，这些节点通过共享信元和OTF调度，预先知道协商的时间表、信道，通过6Top调度避免分配被使用的单元格，可以有效减少冲突。由图1可知，6TiSCH网络有两种信元：一种专用信元，用于邻居之间的协商和数据转发；一种共享信元，用于接收广播或者特殊流量。利用共享信元的特点，接收那些不是邻居但会产生冲突的节点时序分配消息，并且通过内部缓存机制，在冲突发生时进行数据重传，提升网络可靠性。当发生数据冲突时，R(接收数据)节点可以快速为突发流量生成相应时序，同时通过与邻居协商启用碰撞退避算法更新单元格的接收时序，重新接收T(发送节点)的数据。碰撞退避次数K值的选取与协商有关，K值使用6Top事务概率模型计算,是单元格的大小。假设邻居成功接收事务的概率是P,并且成功接收到的传输量Y遵循B(K,P)分布。

Y～B(K，P)P0=P(Y≥1)=1-(1-P)K

(1)

(2)

通过模拟示例拓扑，本文已经计算了每个节点邻居的分组传递比(PDR)平均值。为了保证建议合理，采取较低的PDR值(P=0.6),根据方程，得到表1的结果。

表1 模拟结果

3 6TiSCH模拟器

6TiSCH模拟器是一个用Python编写的开源离散事件模拟器，它实现了6TiSCH体系结构文档中定义的标准和协议。图3总结了模拟器使用的一组参数。每个无线链路都与一个数据包传输率(PDR，一个介于0～1之间的数字)相关联。当一个传感器节点发送数据时，连接到链路的PDR被用来确定邻居是否接收到该分组。PDR根据每个链路的无线电信号强度指示器(RSSI)计算，由无线电传播模型根据两个传感器微粒之间的距离确定，在仿真运行期间恒定。如果不同传感器在相同时隙以相同的频率传输，则包冲突，图4中黑色小方格即为冲突数据。在这种情况下，接收器将每个冲突分组的RSSI转换为映射到PDR的信号与干扰加噪声比(SINR)，链路的PDR作为冲突分组的干扰函数被降低。图5所示为OTF的调度机制。

图3 模拟器参数

图4 节点运行模拟

图5 OTF调度机制

4 模拟器优化结果

4.1 网络整体寿命延长

在6TiSCH网络中，由于通信发生在一个时隙内的特定时间，所以发送节点确切知道何时发送数据。发送者与接收者节点时间完全同步，接收者节点将在发送者开始发送的瞬间开启无线电，其它时间则处于睡眠待机状态，以节省能耗。但是，OTF调度中给出的SF函数并没有明确指出使用什么方法。本文提出分配流量转发策略，避免网络中出现中继节点流量过大而邻居没有数据可传的情况。模拟图1网络结构，如图6所示，实验模型在6TiSCH 模拟器里建立，静态调度已经在每个节点进行预先配置。本文通过监控一段时间内网络中继节点的能耗情况和数据包分配，以验证网络整体寿命延长。

图6 实验模型

需要注意的是，睡眠状态没有能耗。已经考虑预期的信道误差，可以忽略不计。图7给出未优化两个中继节点转发数据包的数量对比，图8给出优化以后数据包的对比(总量1 000数据包)，两个曲线转发数据包的数量差别不大，说明优化可靠。

图7 转发数据包

图8 优化转发数据包

4.2 冲突优化

首先，比较OTF的性能，在没有优化网络冲突的情况下，OTF曲线代表原始OTF协议下的冲突，通过跟踪PDR检查传输有问题的数据帧(见图9)。其中节点只避免了与邻居保留单元的冲突，P曲线对应使用共享数据单元检查冲突的机制，模拟运行1次，运行1 000个周期。仿真开始时，碰撞相对较多，是因为在网络初始化阶段，RPL创建DODAG期间，所有节点通过在共享单元中发送6个顶部消息以请求专用单元。共享单元格中的冲突能够在调度第一个专用单元格之前由CSMA/CA逐步解决[14-15]。随着网络稳定，碰撞信元的数目也趋于稳定。从图9中也可以看出，虽然该方法减少了碰撞，但并不能消除碰撞，而且在某些时候会增加碰撞。可能原因有：①网络状态不稳定，共享信元被占用；②数据量太大，缓存不够；③突发节点比较多。

图9 碰撞模型

5 结语

本文讨论了提高网络整体性能与非邻居之间冲突的问题，解释了冲突的来源、OTF调度存在的问题，并提出解决方案。首先，本文首要目标是增加网络的整体寿命而不是减小节点能耗，延长网络整体寿命也是无线传感网比较关注的问题，通过流量分流减小中继节点的传输压力，一定程度上延长了网络的整体寿命。其次，减少冲突是利用6TiSCH网络共享信元特点实现的。该方法虽然增加了共享信元的开销，但是减少了专用信元的碰撞，不影响网络整体性能。模拟结果显示，碰撞次数明显减少。