关于动态拓扑的物联网终端任务时隙调度研究

奚 军，汤嘉立

(1. 东南大学电气工程学院，江苏 南京 210096；2. 无锡市教育科学研究院，江苏 无锡 214001)

1 引言

由于无线通信技术与万物互连理念的推动，物联网越来越多的被汽车行业、电子行业、制造行业等诸多领域重视[1-2]。通过网络拓扑中部署的节点，可以实现数据共享与交互操作，提高生产生活中事务的处理效率。在物联网展现出各种优势的同时，其发展也面临着很多难题。很多物联网空间内的节点具有移动特性，导致网络拓扑实时变化，组网与路由也随之动态改变，给网络功耗和任务调度性能带来严峻的挑战[3-5]。针对物联网终端任务调度，文献[6]通过物联网中增长的任务对有限资源的抢占，设计了一种资源反馈调度模型，采取加权轮询方式对任务的评价模型进行分析，该方法获得了较好的公平性，但是终端响应速度还有待提高。文献[4]根据终端任务之间的关联，采用任务轮询的方式构造调度等级模型，进行时间片处理，并在每个时间片结束后对关联矩阵采取调整操作，重构任务调度模型。该方法能够有效处理关联任务的调度，但是对于弱关联任务的调度性能还有待优化。文献[7]根据刷新率的差异，对节点任务采取不同等级的调度，从而提高任务处理的效率要求，同时由于不同任务对应不同的刷新率，使任务信号在传递时有效降低能量消耗。该方法获得了较好的网络吞吐量和抗噪性能。基于当前研究的优缺点，本文针对动态拓扑物联网，同时考虑网络能量与任务调度双重性能，提出了一种基于移动节点追踪的终端任务时隙调度策略。利用移动追踪感知网络拓扑中节点的实时位置，从而对其进行准确的子网络区域划分，有效控制节点的能耗。再利用优化的时隙分配方案准确及时的完成任务执行，指派任务节点，提高任务的实时调度性能。

2 动态拓扑物联网调度模型

由于物联网的节点具有移动特征，使得网络拓扑随之动态变化，所以本文在建立终端任务调度模型时，需要确定当前的网络节点位置，根据节点位置便可以得到准确的网络拓扑结构。利用拓扑结构将网络任务进行区域划分，同时把区域任务看做是包含时隙的帧。在节点移动的过程中，利用区域划分与节点的时隙变化，随时规划网络内终端的任务。根据调度的调整，物联网内节点的任务包括进程、存储，以及文件的处理。基于以上描述，本文设计的动态拓扑物联网任务调度模型如图1所示。在进行任务调度时，为了防止通信链路在某时隙帧内发生槽溢出，应该确保区域划分中的任何节点不存在收发同步的状况。另外，还要保证任何两条链路之间不存在干扰冲突，即某时隙中任意链路的发送不会干扰到其它链路的接收。于是，处于某时隙中的任务在调度时必须选择无冲突链路。

3 动态拓扑节点跟踪

设定物联网中节点的移动处于二维空间，任何一个节点在移动过程中涉及的参数包括方向、速度和噪声，于是，任意节点在时刻t的移动方程可以描述为

(1)

其中，xt与yt依次代表t时刻节点在x、y方向的状态；M代表控制矩阵；ut代表噪声；vx，t与vy，t依次代表t时刻节点在x、y方向的速度。根据节点的移动方程和距离计算，可以得到其移动感知方程如下

(2)

其中，(xi，yi)表示节点i的位置；wt表示感知噪声。假定感知的时间间隔为Δt，则控制矩阵M表示为

(3)

受网络中的节点移动与感知距离的影响，任意节点可能被多个节点感知，利用移动感知方程，可以得到全部感知的平均状态如下

(4)

(5)

(6)

利用感知功效Et，用来衡量感知节点对目标节点移动状态的感知效果。由于无线传感器的硬件特性，Et与能量和功耗存在一定关系，因此，合理的感知功效有助于改善网络节点的功耗均衡。将后验概率代入功效中，整理得到

(7)

由于节点移动状态的感知与能量、功耗有关，所以利用能量和功耗，计算出全部感知节点的感知能效，公式如下

(8)

其中，EDj表示节点j可用能量；EA表示全部感知节点可用能量的均值；ECj表示节点j对应功耗；EA表示全部节点功耗均值。根据功效和能效，将感知节点对应的累计效能描述如下

Etotal=αEt+(1-α)Wt

(9)

式中的α代表均衡系数，根据α值可以调整节点的感知性能。当感知节点较为稀疏，且需要获取节点的精确位置时，可以把均衡系数适当调大。而当感知节点较为密集，可以根据大量感知数据提高位置精度时可以把均衡系数适当调小，以获得较低的能耗。

4 基于时隙的终端任务调度

为了改善节点移动时终端的任务调度性能，这里基于节点的移动跟踪，设计一种时隙分配策略。在节点移动过程中，通过对时隙的管理，能够使物联网任务调度适应拓扑的动态变化。假定物联网内具有N个节点，则对应的前导时隙可以表示为N×N维度的矩阵TS，在进行时隙分析时，分配间隔应该符合以下约束

(10)

根据约束条件得到的时隙节点和拓扑中的所有节点存在自关联。为了准确分配时隙，利用区域划分中的节点稀疏性sni和关联度aj，得到时隙节点的自关联特征

(11)

在物联网中，终端任务模型与调度流量有关，并受时间因素影响。假定任务i所需的流量为σi，则根据时隙节点的自关联特征，构建任务模型如下

(12)

(13)

(14)

同时，还需要结合距离确定数据传输的最佳跳数。当某节点距离所在划分区域中心节点的距离是d，则在计算该节点对应的最佳跳数时，应该采取d/d0求解距离，d0是衡量效能后节点的最佳感知距离。结合效能分析，对于节点i的调度任务tni，在经过调度处理后的衰减表示如下

(15)

对衰减方程进行求导，于是时隙特征可以描述为

(16)

这里，f(·)用于求解前导时隙矩阵TS内的中断帧；τ代表延迟。考虑到可能发生的时频聚集，如果时隙管理采取了单跳，且能够保证时隙k到达时对节点i的数据帧进行指派，则设置此次调度间隔tki等于1。而其余情况设置tki等于0，说明任务处于阻塞状态，应该采取多跳方式。对于任何时间区间T，采用前述方式进行任务调度均满足Poisson分布，于是，针对多区域划分形成的多进程调度，应该做如下限定

(17)

时隙分配有利于改善任务调度的效率，以及网络资源的利用情况。根据前述时隙分配策略，当考虑到网络拓扑中全部的节点资源，在不发生调度失衡情况下，信道利用情况应该描述如下

(18)

5 仿真与结果分析

实验评估环境选择Matlab，设置物联网拓扑部署范围为5km×5km，节点初始位置以随机方式生成，所有节点可以感知到的最大距离为80m。考虑到单时隙的数据传递能力，设置时隙是10ms，可以利用的信道数量是[1，20]，时隙分配时迭代计算上限设定200，数据传输速度为500kbps。基于评估环境参数设置，通过实验任务生成，并采样得到终端任务信号，图2显示了信号的采样结果。

图2 终端任务时域信号

利用本文设计的调度策略，对采样得到的时域信号进行时隙分析，提取出相应的时隙特征波形，如图3所示。从波形图可以看出，在时隙分配的过程中，有效过滤掉了原始信号中的噪声，波形更加纯净。表明优化的时隙分配处理能够获得更准确的特征提取，从而更为准确的用于指导终端任务调度。

图3 时隙特征波形

配置网络中节点的刷新率分别是1s、2s、4s、8s，根据本文的时隙调度策略，节点任务执行的时段应该选择合适的刷新率，并且保证任务调度不失衡。通过仿真，得到网络中任务调度与时隙分配之间的关系，如图4所示。其中，白色区域是节点的挂起时隙；颜色区域是节点的调度时隙。从任务调度与时隙分配结果分析可知，网络中刷新率高的节点将会出现更多的调度机会，但是在总体的调度时间上，不同的刷新率节点之间基本保持一致。该结果的出现是由于本文在对物联网动态拓扑节点追踪时，充分考虑了感知功效和感知能效，动态调整了移动节点的感知性能。说明本文方法在时隙调度的过程中，具有良好的负载和能量的均衡性，有利于避免网络空洞的产生。另外，从调度时隙上可以看出，无论是纵向比较，还是横向比较，不同刷新率下的调度时隙都不存在冲突情况，也说明本文方法具有良好的时隙调度效率，有利于提高网络数据的吞吐量。

图4 任务调度与时隙分配结果

仿真中，统计所有网络节点的平均功耗。为了对比验证本文方法的有效性，引入文献[7]方法进行实验对比，实验过程中，保证网络拓扑的初始化配置相同，得到的平均功耗结果如图5所示。从平均功耗的结果曲线可见，统计的网络节点数量改变，并没有给平均功耗带来明显的影响，这说明两种方法都具有良好的节点能耗均衡性。但是本文方法的平均功耗一致维持在0.16mW左右，而文献方法的平均功耗则维持在0.83mW左右，显然本文方法显著降低了节点的功耗。一方面得益于网络中移动节点的有效追踪，一方面得益于时隙分配对节点和信道的均衡利用。

图5 平均功耗实验结果

最后，通过仿真验证方法对终端任务调度的准确性。在不同信噪比的情况下，得到两种方法对应的调度性能，结果如图6所示。从调度准确性曲线分析可知，本文方法在信噪比为-20dB左右时，任务调度的准确性就基本稳定，达到最优状态，显然比文献方法具有更好的抗干扰效果。对于动态拓扑的网络节点进行准确追踪定位，并进行实时的区域划分，针对区域中的节点采取时隙任务分配优化，有效提高了物联网终端任务调度的准确性。

图6 任务调度准确性结果

6 结束语

针对动态拓扑的物联网终端任务调度问题，本文提出了一种时隙分配的调度策略，并设计了一种移动节点追踪方法。对于移动节点的感知，通过能效与精度的平衡，达到节点的准确追踪，为拓扑区域划分提供依据，形成局部通信节点簇。在时隙分配时，引入了自关联因素，利用非线性时序进行模型分解，并根据时隙特征确定单跳或者多跳路由，从而使时隙更好的适应数据流量和路由变化，尽可能改善网络资源的利用情况。仿真基于终端任务时域信号分析，并从时隙特征提取、时隙分配、平均功耗，以及准确性等方面，验证了本文提出的方法具有良好的时隙分配效果，为终端任务调度提供准确的时频依据；

在时隙调度的过程中，具有良好的负载和能量均衡性，能够避免网络空洞的产生；此外，有效提高了物联网终端任务调度的准确性和抗噪性。