王成杰 徐九韵 朱兰芳 李世宝

（1.中国石油大学（华东）海洋与空间信息学院 青岛 266580）（2.中国石油大学（华东）计算机科学与技术学院 青岛 266580）（3.中国石油大学（华东）东营科教园区 东营 257061）

1 引言

随着物联网的快速发展，现实环境中大量数据需要以高效和简易的方式传输到数据中心［1］。为了解决这一问题，数据融合技术被广泛应用于处理物联网环境中产生的海量数据。在物联网环境中，无线传感器网络应用广泛，大量传感器收集的数据传输到融合中心进行处理，并将处理后的信息发送给用户［2］。无线传感器网络目前主要应用在环境监测［3］、智慧城市［4］、智能家居［5］、远程医疗［6］及工业制造［7］等领域。

如何将大量的数据快速有效的传输到数据融合处理中心是进行数据处理和决策的先决条件。数据传输的性能指标主要在两个方面：吞吐量和延迟［8］。针对以上问题的研究，以往的文献主要是针对调度算法［9］、传输协议（CSMA 或者TDMA）［10～11］、传感器分布［12］进行研究，忽略了链路在未来一段时间内的接收数据量以及到达率等变化情况，这会导致链路无法根据即将到来的数据及时做出传输调整，算法的服务效率无法及时满足链路的数据生成效率，产生队列积压，也就导致传输时延增大，吞吐量降低。设计高性能的调度算法以实现最大吞吐量和低时延是非常重要的，这是本文的研究重点。

2 网络模型

本文主要研究从传感器节点到融合中心的单跳组网情况，它提供从一组传感器节点到相应融合中心的异步数据传输。整个网络由L个传感器和E个链路组成，可以将其建模为一个有向无环图G=()

L,E，其中L为传感器集，E为融合链路集。每个融合链路Li，iE，保持一个输出队列。第i条链路中的第j个数据包表示为Pij。

Li的队列积压由Qi(t)表示，Qi(t)≥0,Qi( 0 )=0。传感器的缓冲区长度统一由M表示。t时刻到达队列Li的数据包数量表示为Ai(t)，服务向量由Si(t)表示，当Si(t)为1时表示链路Li在当前时刻获得传输机会并成功将数据包传输到数据融合处理中心。无线传感器为实时数据包分配延迟阈值，在延迟阈值内无法成功传输到融合中心的实时数据包将被丢弃，丢弃的数据包数量被定义为Di(t)。非实时数据包不被丢弃。

3 问题描述

因此调度集合满足条件xi+yj≤1,iE,jC(i)。xi=1，代表链路Li在该集合中进行数据传输，xi=0，链路Li不进行数据传输。本文的目标表示如式（1），在冲突集合中找到最优的链路集合即最大优先级调度集合。

其中Pi1是链路Li中具有最高优先级的数据包。

4 数据优先级

在物联网环境中，数据包对时延的要求不同，链路数据传输量的积压对融合中心的数据传输影响极大。因此，数据传输的调度机制应该考虑数据包的优先级和队列内数据包及即将到达的数据包的多少，以满足多节点数据融合的要求。

4.1 队列占用率预测模型

无线网络中传感器节点在获得新数据包时，进入队列等待发送。本文使用泊松过程模型来描述数据生成，泊松过程［13］N(T)，t≥0，发生次数λ≥0是具有以下性质的计数过程：对于所有的t0=00 ，N(s+t)−N(s)～Poisson(λt)。

根据泊松定理，网络中的每个节点从时隙帧开始到结束产生的数据包数量N(T)的分布等于以下公式：

其中，λ是经过一定数量的时隙帧之后生成的分组的平均数。数学上，由以下公式定义：

2.1 2组治疗前后中医证候积分比较 2组治疗后反酸嗳气、胃脘胀满、双胁疼痛、胸闷、食欲不振及大便不畅等中医证候积分比较。中年治疗组与对照组比较，χ2=6.624，P=0.010(P＜0.05)差异具有统计学意义；老年治疗组与对照组比较，χ2=6.624，P=0.010(P＜0.05)，差异具有统计学意义；中老年治疗组比较，χ2=5.875，P=0.017(P＜0.05)，差异具有统计学意义； 中老年对照组比较，χ2=2.43，P=0.119(P＞0.05)，差异无统计学意义。详见表1。

其中，T 是实际时刻，Ai(t)是时刻T=t中节点生成的分组数量，β是可以通过仿真验证的先前时隙帧数量的总和。为了得到λ的精确值，协议将在K个时隙帧之后执行其调度算法。

传感器从终端或者其他传感器节点接收数据包，从时隙帧K=10 开始，传感器节点确定自接收开始，在之前的时隙帧中接收的实时数据包的平均数，如式（3）所示。然后在式（2）中，使用平均数量，以得到确定数量包的概率，然后重复进行式（4）的计算，直到达到最大的概率值，计算终止，得到最大值PMAX。

在时刻T=t，实时数据量和预测即将到达的实时数据量的和为

根据式（5），在时刻T=t，预测的实时数据队列占用率为

同理，非实时链路队列预测占用率为Onr(t)。

4.2 历史丢失率

其中Iij(·),jK是指标函数，Tdij是数据包的生成时间，wij(t)是pij由传感器在传输前的等待时间。因为网络是动态变化的，在此我们只计算最近传输的K个数据包的丢失率，对丢失率进行实时动态更新。

4.3 剩余生存时间

Tij(t)是数据包的剩余生存时间，其计算如式（8）：

其中Tcij和Tdij分别是数据包的生成时间和延迟阈值，t是当前时间。

4.4 数据优先级

时隙t中的实时数据包pij的优先级表示为Pij(t)，其定义如式（9）所示：

Tij(t)的值越小，数据包的剩余生存时间越短，调度优先级更高。参数δ从区间(0,1)中取值以反映优先级的紧急性，具有较小Tij(t)值的数据包优先级更高。ω1和ω2是当前数据包队列预测占用率特征和丢包率特征在数据优先级中的权衡因子，ω1越大，意味着丢包率在数据优先级中占主要地位，ω2越大，意味着数据包的队列预测占用率在数据优先级中占主要地位。

非实时数据包的优先级定义如式（10）所示：

非实时数据包相对实时数据包的优先级较低，在传输过程中，当非实时数据包的等待时间超过延迟阈值时间时，非实时数据包不会因为截止时间到期而被丢弃，因此在非实时链路中不需要进行历史丢失率的计算（不考虑网络的其他因素）。当实时队列数据量较少且在未来一段时间内即将到达的数据量较小时，非实时队列中积压较多数据且预测的到达数据量较大会对数据优先级起重要作用，这使得非实时队列中的数据包传输竞争力增强，有更多机会传输数据，并将队列保持在较低水平，降低队列延迟和丢包率。

本文提出的数据优先级方案综合考虑了数据截止时间、队列预测占用率和队列丢包率，目的是计算数据包的综合优先级，根据优先级对传输进行动态调度。在保证数据包时间约束的情况下，使链路服务速率能够与链路的数据产生速率相匹配，避免链路饥饿，缩短链路队列长度，降低传输时延和丢包。

5 分布式调度算法

该在此介绍我们提出的基于动态队列感知的CSMA 算法（QACSMA），该算法的基本思想是为紧急程度较大的链路分配较小的退避时间，避免具有相同紧急程度的链路因同时传输而产生冲突，每条链路在指定的间隔内随机选择退避时间，形成无冲突的调度机制，优先级越高得数据，退避时间越短，传输优先级越高。

在算法中，我们将时隙划分为两个部分，一部分是控制子时隙，每个控制子时隙被分成B帧，并且每一帧被再次划分为W个微时隙。另一部分是传输子时隙，当传感器节点在控制时隙中等待一定时间后，在传输时隙进行数据传输。Pi1被划分成不同的间隔并映射到不同的帧。每个链路Li将根据Pi1在指定的映射帧中随机选择退避时间wi，算法将产生一组最佳的可行调度集合。退避时间wi由公式wi=f(w)+NW定义［14］，中w在[0,W−1]上离散均匀分布，根据以上公式可得到wi与Pi1的映射关系。

QACSMA算法分为两个部分，第一部分根据数据包的优先级对链路i中的数据包进行排序。优先级最高的数据包Pi1排在每条链路的最前面。第二部分是链路i根据链路上第一个数据包的优先级在指定帧中选择退避时间wi，优先级越高的数据包，退避时间越短，也就具有更多的传输机会。同一冲突集中的链路将优先传输退避时间最短的数据包，不同冲突集中的链路可以同时传输数据包。经过以上算法，在时隙t中可以同时将最大可行调度集合中链路的第一个数据包发送到融合中心。

我们使用以下指标来评估提出算法的各项性能：

指标一：链路Li的吞吐量Ti定义如式（11）：

指标二：链路Li的平均队列长度Ni定义如式（12）：

该算法在相互干扰的链路集合中，优先传输紧急度较高的数据包，同时考虑了各队列间数据包传输的冲突问题，将控制子时隙划分区间，针对不同紧急度的数据队列，通过各队列数据头包的优先级映射到不同的退避区间，该方法大大降低了各队列间的冲突，避免了因同时传输造成的数据拥堵。该调度算法有利于为数据紧急度较高且队列预测占用率较高也就是数据流量较大的链路提供更多的传输时间，增大紧急度较高链路的传输机会。同时可以根据各队列的数据包优先级的调整，动态调整退避时间，使得队列的实时服务效率跟随链路数据接收效率随时变化，具有良好的适应性。

6 实验设置与评估

6.1 参数设置

本文使用Matlab 模拟了一个有6 条链路的网络，其中链路1，2，3模拟为实时链路，链路4，5，6模拟为非实时链路。干扰集C(i)定义如下：C( )1 ={2 ,5},C( 2 )={1 ,3,4,5,6},C( 3) ={2 ,4,5},C( 4 )={2 ,3,5},C( 5) ={1 ,2,3,4,6},C( 6 )={2,5}。

数据包在时隙中到达链路的概率服从参数为v的伯努利分布。在不同网络流量负载下测试性能，实验更强调突出队列长度预测占用率在数据优先级中的作用，因此将w1设置为0.3，w2设置为0.7，K=100 ，β=10 。参与对比实验的算法为DMS、QCSMA、GDCSMA、VDCSMA。

6.2 评估

本文的仿真实验，统计了不同网络负载下的总吞吐量和平均队列长度。图1 显示，网络流量较小时，本文提出的算法与其他算法总吞吐量基本一致，当数据包到达率超过0.25 时，本文提出的算法相对其他算法吞吐量较高，表现更好，主要是因为本文提出的算法根据队列预测信息进行动态调度，使得算法的实时服务效率能够跟随各队列的数据接收效率而动态变化。确保了各传输节点的分组队列长度保持在最低水平，即最大限度地发送分组，避免了队列溢出。

图1 总吞吐量统计

图2 表明，在中低负载下，对比算法均具有较小的平均队列长度。当负载逐渐增大时，其他算法的平均队列长度会急剧增加，表明其时延性能较差。

图2 中低网络负载下的链路平均队列长度

在图3 中，QACSMA 比其他算法具有更短的平均队列长度。当分组到达率大于0.84时，其他算法的平均队列长度会随着分组到达率线性增加，本文提出的算法平均队列长度相对更短且相对稳定，侧面表明我们所提出算法的数据传输效率更高，数据在传感器节点的等待时间更短，延迟更低。

图3 高网络负载下的链路平均队列长度

7 结语

本文提出了一种基于动态队列感知的分布式CSMA 调度算法，该算法根据链路预测占用率和数据优先级，动态调整竞争传输窗口，当传输队列变长时，链路竞争优先级更高，传输概率更高。该算法尽可能将传感器的队列保持在较低水平，提高了较长队列的链路服务效率，降低了数据丢包率和传输延迟，保证了紧急数据包的优先传输，同时传感器会实时监测队列变化情况和数据到达速率，很好的考虑了网络流量在下一时刻的状态，在一定程度上预测了网络变化情况，及时针对网络变化对调度机制作出调整，满足了不同链路的实时服务效率，在吞吐量和延迟性能上均有所提高。大量的仿真结果表明，该方案在不同网络负载下均能获得较好的性能，尤其在高负载下，相对其他算法有更好的表现。