一种响应时间感知的移动服务组合方法

李 靖，任丽芳，王文剑,3

(1.山西大学 计算机与信息技术学院 山西 太原 030006；2.山西财经大学 信息学院 山西 太原 030006；3.山西大学 计算智能与中文信息处理教育部重点实验室 山西 太原 030006)

0 引言

随着云计算和移动互联网的结合，用户可以在移动环境中随时随地使用智能手机等终端设备访问网络中的云端服务[1]。由于越来越多的服务提供商进入网络服务市场，导致同一功能的任务可以由越来越多的服务实现，然而这些服务通常具有不同的服务质量(quality of service, QoS)，如响应时间、价格、吞吐量、可靠性等。网络服务的功能简单、门类繁多、属性各异，用户需要从数量巨大、QoS迥异的服务中选择适用的组件服务，并进一步实现服务组合以完成较为复杂的业务[2]。因此，如何快速找到QoS最优的组合服务成为亟须解决的问题。传统的服务选择方法是对每个任务选择QoS最优的服务，但在移动环境中，用户要调用服务时既需要考虑初始信息(例如用户所处位置、调用时刻以及设备类型)，又需要考虑用户的移动性，这导致服务选择变得更加困难。移动环境中用户的位置不固定，且响应时间属性受用户移动的影响较大，使得响应时间感知的移动服务组合方法研究成为移动服务计算领域的一个重要方向。近年来，已经有很多研究致力于解决QoS感知的服务组合问题[3]，大致可分为全局最优方法和局部最优方法两类。全局最优方法是从所有的服务组合中找到最优的组合服务，其典型方法是将满足用户QoS约束的服务组合问题建模为一个整数规划问题[4]，但这类方法求解难度很大，因此最常用的是局部最优方法，即选择最优的组件服务进行组合。文献[5]提出一种模糊线性规划方法来识别候选服务的差异，可以帮助服务使用者通过考虑他们的要求和偏好来选择最合适的服务。这类方法在传统的Internet环境中取得了较好的效果，然而在移动环境中由于用户在调用服务的过程中位置不固定，而且不同位置的网络信号质量可能不同，这导致由最优组件服务组成的组合服务的全局QoS不一定是最优的。因此，移动环境中的服务选择与组合需要考虑用户的移动性。

目前，已有一些研究工作对移动环境中服务组合问题进行探讨。文献[6]为减少服务请求的组件任务分配给边缘服务器和云服务器的时间延迟，提出一种用于移动边缘系统中服务选择的组合遗传算法和模拟退火算法。文献[7]介绍了一种针对无线移动自组织网络中可靠的服务组合问题的移动性预测方法，其目标是可以忽略服务提供商的移动性来组合服务。文献[8]针对移动应用领域的特点，提出一种探索式服务组合方法，通过感知上下文变化为用户构造当前环境下可用的服务集合，并通过交互将用户选择的服务及时组合到应用中。上述工作丰富了移动服务组合的研究，但都存在不同程度的局限性。一方面，在实际移动环境中网络信号质量是动态变化的，一般很难用显式函数来表示，而现有研究中网络信号质量通常由分段函数或余弦函数来表示，虽然这两个函数都能体现出网络质量是变化的，但不能准确体现其分布。另一方面，这些方法都是通过一些启发式算法来搜索最优的组合服务，当组合服务越接近最优时，需要的迭代次数就越多，效率就会越低。本文在一个真实的移动仿真环境下获取了各个位置的网络信号强度，提出一种响应时间感知的移动服务组合方法，根据用户实时移动位置准确地选择最优组件服务，完成服务组合。该方法每次迭代计算的是组合服务响应时间的预测值和真实值的均方误差，可大大缩短模型训练时间。

1 移动模型

1.1 模型定义

在移动环境中，用户在调用服务时位置可能会变化。用户在移动时，移动网络中的数据传输率会根据用户的位置而动态变化。

定义1用户的移动路径。用户的移动路径用一个四元组ump=(Location,Direction,Time,Speed)表示，其中Location表示用户调用服务时的起始位置；Direction表示用户的移动方向；Time表示用户的移动时间；Speed表示用户的移动速率。一般假设用户是匀速运动，所以用户下一时刻的位置可通过计算得到。

定义2组件服务。一个服务将被建模为一个四元组s=(Sid,Input,Output,Q)，其中Sid表示服务的编号；Input表示服务的输入；Output表示服务的输出；Q表示服务的QoS。

定义3组合服务。为满足用户的功能需求，将不同功能的组件服务按照一定的逻辑进行集成，形成可扩展的增值服务。这样，组合服务就可以形式化地表示为一个序列sc=(s1,s2,…,sn),其中si(i=1,2,…,n)为依次组成组合服务的组件Sid，n为组合服务中组件服务的个数。

定义4响应时间。组件服务的响应时间定义为参数输入时间、服务执行时间以及结果输出时间之和；组合服务的响应时间定义为所有组件服务的响应时间之和。

1.2 响应时间计算

1.2.1移动网络质量 移动网络质量通常指一个特定位置的移动信号强度，本文将数据传输率作为移动网络质量的度量指标。虽然数据传输率在数据传输过程中不可能一直保持恒定，但在短距离内变化并不明显，因为每个任务在数据传输上花费的时间非常短，通常只有几秒钟，而步行用户在数据传输的时间内移动的路程也仅仅只有几米。目前常用的宏基站的覆盖范围有几百米，用户在数据传输的时间内不换基站的概率非常大。因此，假设每个任务在进行数据传输时移动网络质量保持恒定。

1.2.2组件服务响应时间 移动环境中QoS描述了移动环境中组件服务的性能。不同路径的网络质量有所差异，导致用户在不同位置调用组件服务时影响了服务的输入、输出数据量的传输时间。组件服务s的响应时间可以表示为

RT_CSs=tvodi+Es+tvodo，

(1)

其中：tvodi代表组件服务s传输输入数据所需的时间；Es代表组件服务s的执行时间；tvodo代表组件服务s传输输出数据所需的时间。tvodi可以表示为

(2)

其中：vodi表示输入的数据量(数据集中给定服务的数据量)；QoMNi表示用户在刚开始输入数据时所在位置的移动网络质量。根据同样的方法可以计算出tvodo。

1.2.3组合服务响应时间 具有循环、分支和并行结构的服务组合都能转化为一种顺序结构[9]，本文主要解决业务逻辑的过程模型为顺序结构的服务组合问题。QoS表示整个组合服务的性能，组合服务的响应时间可以表示为

(3)

其中：sc表示组合服务中所有组件服务的执行序列。

2 移动服务组合方法

本文提出的NNSC算法，其目标是在移动环境中从所有的服务组合中找到响应时间最短的组合服务。NNSC算法由两部分组成：一是通过随机森林分类算法过滤掉响应时间较长的组合服务；二是通过前馈神经网络建立移动组合服务与其响应时间的回归模型。图1描述了服务组合的一般过程。首先将任务按照条件、循环等控制语句组合成复杂的任务，然后再为每个任务找到合适的候选服务，此过程即为服务发现，服务发现通常由虚拟服务提供商来完成。最后进行服务选择，即对每个任务从候选服务中选择一个合适的服务，将这些服务进行组合，组合时的控制语句与任务组合时的控制语句相同。

图1 服务组合的一般过程

2.1 组合服务分类

当子任务的候选服务数量一定时，组合服务的数量与子任务数呈指数级关系，使得选择最优组合服务成为一个NP-hard问题。此外，这些组合服务的响应时间差异较大，响应时间较短的组合服务只占小部分。为了缩小解空间，提出了组合服务分类算法，用来过滤掉响应时间较长的组合服务。首先，初始化需要用到的集合，并根据比例选取训练集。其次，计算训练集中组合服务的响应时间，然后设定阈值，并根据阈值为组合服务设置标签。在此基础上，对训练集进行训练得到分类模型。最后，使用训练好的分类器预测服务集，返回响应时间较短的组合服务集。组合服务分类算法的主要步骤如下。

输入: 移动路径及起始位置、服务集、训练集占服务集的比例k。

输出：较优的组合服务集。

Step 1 按服务组合过程进行服务组合，并创建响应时间、组合服务标签、较优服务集三个空集合；

Step 2 根据比例k从服务集中选择训练集；

Step 3 FOR 组合服务 IN训练集：

通过式(3)计算出用户在该路径中起始位置调用组合服务的响应时间，并将结果存入响应时间集合中；

END FOR

Step 4 设置阈值为响应时间中最大值与最小值的平均值；

∥ 组合服务对应的标签为1时，表示其响应时间较短；标签为0时，表示其响应时间较长。

Step 5 FORtIN 响应时间:

IFt<阈值

将1添加到组合服务标签中；

ELSE

将0添加到组合服务标签中；

END IF

END FOR

Step 6 使用随机森林分类器训练得到模型；

∥result用于存放分类结果0或1，1表示该组合服务的响应时间较短；0表示该组合服务的响应时间较长。

Step 7 使用该模型预测服务集，并将分类结果存入result中；

Step 8 FOR EACHres∈resultDO:

IFres==1

将该组合服务添加到较优服务集；

END IF

END FOR

Step 9 RETURN 较优服务集。

2.2 响应时间预测

在识别出响应时间较短的组合服务之后，为了找到响应时间最短的组合服务，提出了组合服务响应时间预测算法。组合服务与响应时间之间是非线性关系，而神经网络处理非线性模型有较大的优势。因此，通过tensorflow搭建了如图2所示的前馈神经网络模型。图2的神经网络模型包含输入层、2个隐藏层、输出层。输入层包含12个神经元，第一隐藏层包含10个神经元，第二隐藏层包含4个神经元，输出层包含1个神经元。在此模型中将预测值与真实值的均方误差作为损失函数，并通过Adam算法来优化损失函数。为缓解梯度消失的情形，激活函数采用ReLU函数。当迭代次数小于最大迭代次数时，使用该神经网络训练数据集，直到模型收敛或者达到最大迭代次数，然后通过训练好的神经网络进行预测。

图2 前馈神经网络模型

3 实验设计

实验环境配置为Intel(R)Core(TM)i7-7700 3.60 GHz 处理器，内存为16.0 GB，Windows 10操作系统，Python 3.7版本。

3.1 实验部分

3.1.1移动仿真环境 为了使移动环境中各个位置的网络质量相对真实，选取了一个真实的移动环境，如图3所示。由于条件限制，选取了长约1 000 m、宽约500 m的区域，真实环境中基站分布如图4所示。

图3 一个真实的移动环境

图4 真实环境中基站分布

图3和图4中的三角形表示环境中基站的位置，数字1、2、3、4分别表示四条路径，区域中共有1-2、2-1、1-3-4、4-3-1、2-3-4、4-3-2 六条路径。图5给出了这六条路径中各位置的网络质量(用网络传输速度表示)。根据基站的位置，通过模型cost231-hata计算出基站到用户当前位置的路径损耗。基站的总功率减去路径损耗、车辆穿透损耗、建筑穿透损耗等，即为各位置的网络质量。可以看出，网络信号质量的变化不是由分段函数或余弦函数等简单函数表示的。

图5 路径中各位置的网络传输速度

3.1.2实验数据集 实验数据集为文献[10]使用的某些服务器的日志文件，该数据集是由阿里巴巴与浙江大学搜集的，可从www.bruceluo.net网站中下载，其中一个组合服务样例如表1所示。表1中每一行表示一个服务，用输入量、输出量、执行时间这三项来描述。如第一行表示该组件服务接受1 697 kB的输入，2.84 s执行完该服务，并有1 686 kB的输出，然后发送到下一个组件服务。对于每一个任务都有很多候选服务，每个服务执行时间不同，服务的执行时间从均匀分布中随机生成。为避免其他因素影响评估结果，假设每个任务的候选服务的输入和输出数据量相同。

表1 组合服务样例

3.2 实验结果及分析

3.2.1参数的选择k为训练集占服务集的比例，k值越大，算法的执行时间就越长。选择k的起始值是8%，逐渐增加至12%，观察其寻找到的最优组合服务的执行时间。在不同的位置处，对于每个k值，实验执行20次，结果取多次执行时间的平均值，实验结果如图6 所示。图6中每个柱形图都由两部分组成，上面较窄的部分表示执行算法找到最优组合服务所用的时间，剩余部分表示最优组合服务的执行时间。可以看出，当k值为10%时，算法找到的最优组合服务的执行时间相对较短。因此，后续实验中选择k值为10%。

图6 不同k值时算法的执行时间

3.2.2算法的性能 为了验证NNSC算法的有效性，从神经网络的收敛速度方面来考虑方法的效率。图7为不同候选服务数时的收敛速度,图8为不同任务数时的收敛速度。可以看出，当任务数不变时，前馈神经网络模型很容易收敛。候选服务数相同，当任务数不超过5时，收敛速度较快。

图7 不同候选服务数时的收敛速度

图8 不同任务数时的收敛速度

3.2.3与其他算法的比较 最优移动组合服务的选择是组合优化问题，该问题被证明是NP-hard问题，不存在多项式时间算法。目前，最优组合服务的选择常用一些近似算法或启发式算法来求解，例如模拟退火算法、粒子群算法等。为了验证NNSC算法的优越性，与以下四种算法进行了比较：① 支持向量机(SVM)。完成组合服务分类算法后，使用SVM建立组合服务与其响应时间的回归模型，从而预测其响应时间。② 基于教与学的优化算法(TLBO)。TLBO是基于教学过程的自然现象而开发的一种启发式算法，已用于解决服务组合问题，并且具有很高的效率[11]。③ 粒子群优化算法(PSO)。PSO是一种根据给定的质量度量并通过反复迭代来改进候选解决方案的优化算法，已经广泛应用于服务组合研究中[12]。④ 局部最优方法(LOM)。对于每一个任务，LOM从候选服务中选择响应时间最短的服务进行组合。任务数为4，在每个任务10个候选服务的情况下进行实验，在相同的实验环境中实现了上述算法，并对每种算法进行了参数优化。

因为移动环境中各个位置周围网络质量的变化程度不同，所以用户在不同位置调用服务的响应时间不同。为了验证NNSC算法的有效性，在六条路径中的初始点和极值点附近开始调用服务，观察NNSC算法与其他算法所选出的最优组合服务的执行时间。图9显示了用户在路径1-2、路径2-1、路径1-3-4、路径4-3-1、路径2-3-4、路径4-3-2 各极值点附近，调用通过不同算法得到的最优组合服务的响应时间。可以看出，通过传统的局部最优方法得到的组合服务的响应时间普遍较长。结合图5中各位置的网络传输速度，发现在传输速度较慢的位置，这种差异更加明显。这说明移动环境中网络质量的变化对服务选择产生了重要的影响。本文NNSC算法在不同路径多个位置处找到的最优组合服务的执行时间都是最短的。这是因为通过分类算法过滤掉响应时间较长的组合服务的数量较大，并且不会将响应时间近似最短的组合服务过滤掉。与启发式算法相比，NNSC算法缩小了解空间，能获得较高的效率。

图9 路径中不同位置响应时间的比较

4 小结

本文首先建立了可计算的移动模型，其次根据此模型过滤掉响应时间较长的组合服务，最后采用前馈神经网络建立组合服务与响应时间的回归模型来选择出响应时间最短的组合服务。结果表明，在相对真实的移动网络环境中，本文方法的实验效果优于其他一些启发式算法。由于只考虑了移动环境中服务的响应时间这一最重要的QoS属性，未来工作将综合考虑QoS的其他属性，为用户推荐更合适的服务。