1 引言
?
近年来移动服务伴随着移动互联网的普及迅速地发展起来，对移动环境下服务的研究也成为了新的热点. 在传统服务中会遇到的服务选择问题在移动环境下也同样会遇到. 在众多的提供相同服务功能的移动服务中，选择出更优的服务是用户时刻的需求. 移动环境下的服务QoS 如价格和延迟等指标与在传统互联网中的服务类似，但部分指标在移动环境下会有所不同. 在移动环境下用户使用服务时面临的可用性问题相比传统服务挑战更大. 移动环境下服务以无线传输的方式提供，使得服务具有一定的物理服务范围，也使服务的可用性与用户的位置相关联. 较直接的例子就是WIFI 热点与蜂窝信号的切换问题. 现代城市中遍布了许多WIFI 热点，这些热点因为传输限制只能覆盖信号发射位置附近的一定范围，目前的移动智能终端在切换WIFI 热点与蜂窝信号时都会造成本机网络的暂时中断. 基于上网速率与经济效益的综合考虑，用户的需求往往会更倾向于在WIFI 环境中使用WIFI 信号，而在没有的情况下使用蜂窝信号. 但是当用户离开WIFI 信号范围时就会发生信号切换问题，如果此时用户需要使用的在线服务如在线视频、网络支付并未结束，就导致这些服务受到中断并可能发生失败. 所以如何在移动环境的背景下，根据用户的服务任务，选择出避免服务切换且代价最优的服务方案是本文所要研究的目标. 需要注意的是无线网络是移动环境下应用服务的载体，也正因为无线网络具有覆盖范围的问题使得移动环境下的服务具有了本文所描述的可用性的问题.
?
是一个移动环境下二阶段的服务选择任务，该图表示一共有两个抽象服务S1和S2需要在用户的移动过程中先后执行，S1有3 个可选服务实体分别为c11，c12，c13，S2有3 个可选服务实体分别为c21，c22，c23; 以服务为圆心辐射开的圆形表示该服务实体可以对外提供服务的范围. 假设用户在移动过程中会从Pus直线移动至Pue，可以直观的看出先选择c13是无法完成服务任务的，因为它无法在用户移动的过程中的任何时刻提供服务. 选择服务c23也是不合理的，因为服务任务需要顺序执行，而在执行服务c23之前没有可以执行S1的服务实体. 如果不考虑服务本身需要被执行的时间，从c11 c12与c21 c22中任选一个服务都可以组成免切换的服务方案. 如果考虑服务的执行时间，则c11极有可能因为与用户的移动轨迹覆盖较短而会在用户离开其服务范围时还未执行完服务，导致服务任务执行失败.
?
为了在移动环境下解决上述问题，本文针对性的将问题抽象成具体的数学模型，在满足避免服务切换的约束条件下，以服务的总代价最小为目标条件，提出了避免服务切换的服务选择算法.
?
2 相关工作
?
2. 1 服务质量
?
对于有线网络和无线网络网络层的QoS 研究已经有了大量的研究，这类研究偏重于研究网络本身的服务性质，例如带宽，延时，丢包率等属性. 近几年来，也涌现了许多用户感知的服务质量的研究成果. 如Sullivan等和Zeng等将服务质量拓展到了更宽泛的意义，即包含可用性( availability)，可靠性( reliability) ，信誉度( reputation) 和价格( price)等在内的服务非功能性的属性. 而在移动环境下由于本身的动态性，考虑服务质量问题会有很大的挑战. 因为移动环境下，服务的位置，传播能力的变化以及服务接受者的移动性都会严重影响着服务的可用性，这些是由移动网络传输本身的特点造成的.
?
2. 2 服务选择
?
在服务选择领域已经有很多的相关研究成果，主要有基于QoS 的、基于信任和信誉的、基于上下文的、基于偏好的等等. 基于QoS 的Web 服务选择能够很好地满足用户对于组合服务的全局约束，因此大部分Web 服务选择都是QoS 感知( QoS-aware) 的.
?
基于QoS 的服务选择就是根据用户对服务实体与组合服务的QoS 要求，对流程中的每个抽象服务选择一个服务实体，并使得衡量服务选择效果的目标函数最优，对于上述QoS感知的服务选择问题，现有的文章一般是将其作为基于QoS的局部或者全局约束的组合优化问题，并采用已有的优化方法对问题进行求解，这其中的方法包括了整数规划、多维多选择0-1 背包、遗传算法等等.
?
但是一般的服务选择方法都是基于有线网络环境下，而在无线环境下，由于服务QoS 属性会受到更多条件的约束而不同，因而传统的服务选择方法无法直接应用于无线环境下.Yang通过对无线环境下对服务QoS 几个关键属性进行了重新描述，提出了无线环境下，普适服务的QoS 感知服务选择算法. 其中在描述服务节点可用性时，规定了用户的移动范围为一个圆形区域，并提出服务提供者提供的服务也具有一定的范围，用圆形区域描述这个范围. 进而利用两者的覆盖面积交集与服务提供范围总面积的比值作为服务可用性的概率描述. 同时论文将节点可用性与其他QoS 同等作为服务选择的定量约束条件，在服务选择中，只是针对每个服务组件执行QoS 约束的扫描，并没有结合前后组件服务之间的位置、用户的移动位置、服务针对用户是否可用等综合考虑.
?
3 问题定义
?
在移动环境下，用户发起的一个服务选择的任务可以表示为n 维向量Σ = < S1，S2，…，Sn > ，其中Si表示用户需要执行的第i 个服务. 针对每一个Si都有一个服务实体的集合Ci= { ci1，ci2，…，c ij} 提供具体的服务. 针对每一个服务实体cij，假设其处于空间中的一个固定位置，并有相应的服务范围和QoS 指标. 本文假定服务实体cij提供的服务范围是一个以服务实体的物理位置为中心向外覆盖的圆形区域，用服务半径rij表示，距离服务中心距离大于rij的点，无法使用该服务实体. 此外定义cij的服务时间为tij，服务费用为pij，本文以费用最小作为服务选择的优化目标.
?
为了描述用户移动性，需要确定用户u 的移动路径与其在移动路径上的速度，为了简化问题，本文假定用户是以直线方式移动的. 令用户移动起点为Pus，移动终点为Pue，移动速度为vu，就可以在二维空间中描述用户的移动轨迹.下面对文本待解决的服务选择问题进行描述.
?
移动环境下避免服务切换的服务选择问题. 给定用户u的移动起点Pus与终点Pue，和其需要的服务选择任务Σ，在服务集合C 中选择一组服务选择方案，使得这组服务选择方案在用户移动过程中，保证每个服务都满足不发生服务切换的约束条件下，可以顺次执行，并使得所选择的方案在所有的符合约束的服务选择方案中，服务整体代价最小.
?
4 避免服务切换的服务选择算法
?
本文提出的避免服务切换的服务选择算法( Switch-AvoidService Selection Algorithm，后简称SASS 算法) 通过两个过程解决前一章提出的问题. 本章主要介绍了SASS 算法，也给出了一种线性规划的方法，其中4. 1 与4. 2 具体地阐述SASS 算法的两个过程， 4. 3 节中介绍了用线性规划解决本问题的方法.
?
4. 1 筛选免切换的服务
?
对于服务Si，我们首先需筛选出符合免切换约束的服务实体cij，即用户在移动过程中与服务实体cij的服务范围相交的路径可以保证服务的执行时间. 判断服务实体cij是否满足这种条件的具体方法分为两步: 第一步判断移动服务是否可以在用户移动过程中存在可用的时间段; 第二步判断如果存在可用的时间段，是否可以保证服务的执行时间.
?
4. 2 优化方法寻找最优服务选择方案
?
为了寻找最优解，枚举算法需要找出所有符合约束的选择方案，然后从中找出费用最优的方案，显然枚举算法会导致很多不必要的搜索分支. 举例来说，在选择服务Si的某个服务实体cik时，在服务Si – 1中可能会存在多个结束时间满足在cik的最晚开始时间之前的服务. 对于这些服务，如果结束时间在Tik之前，那么当执行完它们之后，c ik的开始时间与结束时间都是确定的，对于这些服务只要选择其中代价最小的服务进行扩展搜索就可以满足最优目标了. 显然，在相同的结束时间显然费用更少的是具有状态最优的性质的.
?
为了过滤多余的搜索状态，首先需要定义一种结构来保存搜索时的状态. 本文定义了α 表示在某个服务选择阶段中选择完成c 服务实体后，结束时间在γ 时，累计花费为ρ 的状态，状态中还需要记录其前一个阶段的服务选择状态αr 以在得出最优的最终状态后可以反向求选择方案的序列. 则α 可表示为α = < c，γ，ρ，αr > . 定义gi表示在选择第i 阶段服务后，满足免切换约束下所能达到的所有状态的集合，也即gi ={ αi1，αi2，…，αin} . 定义fi为gi删除多余状态后的集合. 本文一共有以下两种方式对多余状态进行过滤.
?
第一种: 即前文中提到的，对于结束服务时间相同的状态过滤掉花费更多的状态.
?
第二种: 如果存在结束时间更早且花费更小的状态，则舍弃结束时间更晚且花费更大的状态.
?
后者可以用反证法证明，假设结束时间早的状态为α1，较晚的为α2，如果此时选择结束时间更晚且花费更大的状态α2为更优的状态，那在最终的最优任务方案里，由于结束时间更早的α1是可以替换α2的，但是此时由于α1的花费更小，所以替换后的方案花费更小，与最优方案矛盾，得证.
?
αik，αij∈fi，αik . γ < = αij . γ→αik . ρ > αij . ρ ( 3)
?
两种筛选的约束合并表示如( 3) ，( 3) 式表示fi中的任意两个元素αik，αij，如果αik的结束时间比αij的结束时间更早或者两者时间相等，那么αij的花费肯定要比αik的小，否则αij就没有存在的价值，而fi就是符合( 3) 约束下gi的最大子集. 显然，在对fi中元素按照γ 升序排序时，ρ 的值应该是严格单调递减的，因此算法实现的方式为对每阶段的gi进行按γ 升序排序，然后去掉排序后结果中ρ 值不符合单调递减原则的α状态，集合中剩余的就是fi . 这部分算法由算法2 所示. 其中定义el 操作为从集合中根据索引获取元素.
?
4. 3 线性规划寻找最优服务选择方案
?
作为比较，我们提出了一个基于线性规划的方法来选择最优方案. 线性规划需要三个输入: 决策变量，目标函数和一系列约束，其中目标函数和约束条件必须是线性可表示的. 线性规划求解时，会在用户输入的约束条件范围内通过调整变量来最大化或者最小化目标函数，最后输出满足目标函数为最大或者最小时的值，以及此时各个决策变量的值.
?
为了将全局最优问题用线性规划问题表示，我们作了以下的映射. 为了表示整个服务选择方案，我们引入整数变量yij，当取值为1，表示服务cij被选择了，如果取值为0 则表示服务cij没有被选择. 这里我们仍采用算法1 得出的Ai集合中的服务进行线性规划.
?
5 实验与性能评价
?
在这一节中我们对移动服务以及用户移动等信息进行了数据模拟，然后针对不同规模与不同参数的数据对枚举算法、SASS 算法与线性规划方法进行了比较. 本实验采用的编程语言为Java，进行实验的计算机环境如下: CPU 为Intel Corei7，内存为8G，Java 版本为JDK 1. 6.
?
5. 1 数据模拟
?
我们针对本文中提出的问题进行了环境的模拟，模拟的数据对象是本文所涉及到的移动服务实体的服务半径，服务时间以及服务花费. 为了使模拟的结果更具现实意义，我们根据现实情况做出了两个假设. 其一是服务半径与服务的花费成反比，例如蜂窝网络价格一般较高，而WIFI 热点等服务价格一般较低; 其二是服务半径大的服务实体占的是少数，绝大多数是服务范围较小的服务，例如城市中心的WIFI 热点往往很多，而蜂窝网络则只有几家运营商提供. 在模拟数据中，我们令90%的服务为小范围覆盖的服务，剩余10% 的服务为大范围覆盖的服务，而服务的价格则根据距离反比计算.
?
6 总结
?
本文对比移动服务与传统服务的区别，并结合移动服务面临的现实问题，提出移动环境下服务免切换的概念，并针对免切换的约束提出了相应的服务选择问题. 本文也给出了移动环境下免切换服务选择算法SASS，用以寻找满足免切换约束而且代价最优的服务选择方案. 实验表明该算法相较枚举算法和线性规划方法具有更高的效率.
?
下一步的研究工作将从以下几个方面展开. 首先在本文中作为提供服务的服务实体并不具备移动性质，而在移动互联网和移动电子设备高速发展的今天，移动设备在作为服务的使用者的同时作为服务的提供者，因此加入服务实体的移动性将是下一步的研究重点. 对于服务的辐射范围根据无线传输的特点，越靠近中心的服务质量就应该越好，因此需要具有一定实际意义的函数来刻画距离与可用性的关系. 此外，某些情景下用户更倾向于减少切换而非完全避免切换，这也是未来需要考虑的研究问题. 目前本文采用的是模拟数据，在真实场景中进行实验也是我们进一步工作的方向.