DSE精选文章
A Cost-Saving Response Scheduler for Highway Structural Health Monitoring Data Applications
文章介绍
方法框架
1. 问题定义
（1）高速公路SHM数据应用的节省成本响应调度问题：给定一组按时间到达的用户数据申请，每个申请对应若干具有类型标签和时间范围的数据集合，且本地硬盘存储空间受限。由于部分用户请求数据已存在于本地存储中，不同申请之间存在数据重叠关系，响应不同申请所产生的网络I/O传输成本存在显著差异。问题以最小化整个响应过程中的网络I/O传输成本为优化目标，确定合理的申请响应顺序。本文进一步证明该问题为NP-hard，表明在实际规模下难以获得最优解。
（2）数据重叠：直观来讲，用户申请的数据中，与当前本地硬盘已存数据在“数据类型 + 时间范围”两个维度上重合的部分所占的数据量。换句话说，它衡量的是无需额外网络传输即可直接使用的数据规模。如下图1所示，蓝色矩形为用户申请数据，阴影矩形为本地硬盘已存数据，那么两者重叠形成的红色矩形区域则为数据重叠。如果某个用户申请的数据已经（部分或全部）存在于本地硬盘中，那么该申请在响应时产生的新增网络I/O成本就会显著降低。
图1. 数据重叠定义示例
2. 整体流程
在此基础上，本文设计了一种基于数据重叠度的贪心响应调度算法，伪代码如下算法1所示。整体流程包括以下几个步骤：
（1）数据建模与标注：对用户申请的数据进行统一建模，为每个数据片段赋予数据类型标签和时间范围标签，以刻画SHM数据在语义与时间维度上的差异。
（2）数据重叠度计算：基于当前本地硬盘中的已存数据，计算每个用户申请与本地数据之间的重叠度，用以衡量该申请在当前状态下可能产生的新增网络I/O传输量。
（3）贪心响应决策：在每一轮调度中，优先选择与本地存储数据重叠度最大的用户申请进行响应，从而最大化已命中数据比例，减少远端数据调取。
（4）存储状态更新与迭代调度：在完成一次响应后，根据数据替换策略更新本地存储状态，并在新的存储状态下重新计算剩余申请的数据重叠度，重复上述过程直至所有申请被处理完成。
（5）理论分析与复杂度控制：通过证明优化目标函数的单调次模性，给出了所提贪心算法的(1+1/(e−1))近似比，同时分析了算法的时间与空间复杂度，验证其在实际平台中的可行性。
算法1. 贪心算法
实验结果
实验在合成数据集和真实高速公路SHM数据集上进行，如下表1所示。
表1. 数据集信息
（1）有效性实验
本文将所提方法（Ours）与 8 种常见响应调度策略进行对比，包括：按申请顺序响应（Order）、随机响应（Random）、按数据规模升序/降序（AscSize/DesSize）、按时间戳升序/降序（AscTime/DesTime）、基于相似度的贪心方法（Similar）和基于强化学习的方法（Q-Learn）。在总体I/O成本对比中，如图2所示，Ours 在合成数据集和真实数据集上均表现最优，平均可降低42.16%的网络I/O成本。
图2. 响应调度方法的总I/O传输大小
（2）效率实验
如图3所示，运行时间随申请数量增加而平稳上升，增长趋势符合算法的理论复杂度分析。在实际平台中，由于同时等待处理的申请数量有限，算法开销可忽略。
图3. 应用程序数量的变化带来的效率结果
（3）替换策略分析
在从存储服务器拉取数据后，需要替换本地磁盘中的部分数据，不同替换策略可能影响整体效果。本文将8种常见替换策略进行对比，包括：Random（随机替换）、SameType（同类型优先）、OldTime（最旧时间优先）、SameType & OldTime（同类型的旧时间优先）和LRU（最近最少使用）。如图4所示，在所有策略下，本文方法均保持下降趋势，表明其对替换策略不敏感；其中，Random替换在多数情况下表现最好。
图4. 不同替换策略的比较结果
结语
作者简介
期刊简介
