5.2.2 基于用户感知最小干扰的服务恢复策略

5.2.2 基于用户感知最小干扰的服务恢复策略

与服务组合不同， 服务恢复策略不仅要考虑重建路径的服务质量、 可用性及稳定性， 而且也要考虑服务组合失效前使用过的服务路径。 本节使用覆盖层的拓扑和信息作为输入， 综合考虑基于服务层及网络层的可靠性、 可用性、 价格和时延四个影响用户感知的最关键服务属性， 设计优化的服务路径恢复算法。 在第三章中我们研究过基于服务覆盖层设计的QoS驱动服务路径选择方法， 但并没有结合服务路径失效后的重建进行深入研究， 本节将对服务路径失败后的恢复问题进行深入探讨。

我们来形式化描述服务组合失效后的服务恢复问题。 首先， 定义某组合服务及其恢复策略是一系列服务路径的集合：π＝｛P（t1），P（t2），…， P（tl）｝，π∈ψ，0＜t1＜t2…＜tl＜T∈ξ，π给出了最初服务组合路径P（t1）以及所有的服务恢复策略P（tv）→P（tv＋1），v＝1，…，l－1。基于上一节提出的用户感知干扰强度的定义， 服务重建的目标可转化为在服务覆盖层Soverlay中，寻找最好的策略π，使得（π）在服务生存期内达到最小：

至此服务恢复问题模型化为minimize （π）， 鉴于VANETs下节点的移动具有规律性及可预测性， 对于上述问题的求解可转化为一个动态规划问题。假设在时刻tw∈T，服务恢复路径Ptw( )令用户感知的最小干扰强度为φ（Ptw( )），

鉴于VANETs节点移动的可预测性，可用标准动态规划算法［135］求解公式（5－11），即可得到在时刻tw从服务路径Ptw( )恢复到Ptw＋1( )的最优服务组合重建策略，特殊地，求解φ（Pt1( )）得到的就是最优的初始化服务组合路径Pt1( )。

这一服务恢复策略具有两个显著的特征： 首先， 它是一种反应式的服务恢复策略， 服务路径的替换仅发生在底层网路链路断裂后， 这样的特点决定了服务重建前后服务组件极有可能没有任何调整， 仅仅是底层网络链路的修复， 且失效节点不会出现在恢复后的服务路径上， 我们用定理5.1描述该特性。 其次， 服务层的恢复只有在网络层对于支撑组件服务的拓扑链路无法修复时才启动。 我们用定理5.2描述该特性。

定理5.1：

设π∗＝｛P∗（t1），P∗（t2），…，P∗（tl）｝是一组最优的服务恢复策略，对于前后存在替换关系的两条服务组合路径P∗（tw）和P∗（tw＋1），P∗（tw）不再适应于tw＋1时刻网络的拓扑结构Gseroverlay（τi）（τi＜tw＋1＜τi＋1， τi，τi＋1∈T′）

证明：假定上述定理不成立。 设存在一组最优服务恢复策略πA＝｛PA（t1），PA（t2），…，PA（tl）｝，时刻tw之后具有前后继承关系的两服务组合路径分别是PA（tw）和PA（tw＋1），所以时刻tw时对应的服务路径PA（tw）满足时刻tw＋1时的网络拓扑结构Gseroverlay（τi），（τi＜tw＋1＜τi＋1）。设在时刻tw＋1之后，组合服务路径PA（tw）不适应当前网络拓扑结构的时刻为tw＋h，tw＋h时对应服务组合策略为PA（tw＋h），则该服务组合恢复策略的最小干扰强度为：

假设服务组合策略πB＝｛PB（t1），PB（t2），…，PB（tw），PB（tw＋h），…，PB（tl）｝，对其中每一条服务组合路径PB（tv）＝PA（tv），v＝t1，…，tw， tw＋h，…，tl，该服务组合策略的最小干扰强度为

＋I（β×NPB（tw）→PB（tw＋h））｝

由于NPB（tw）→PB（tw＋h）≤NPA（tv）→PA（tv＋1）且用户感知干扰函数单调递增，所以

I（NPB（tw）→PB（tw＋h））≤I（NPA（tv）→PA（tv＋1））

因此，与最初假定A是最优服务组合策略相悖，所以原命题成立。

定理5.2：

设π∗＝｛P∗（t1），P∗（t2），…，P∗（tl）｝是一组最优的服务恢复策略，假定在π∗中部分服务路径的服务组件发生了替换，相应的服务路由策略记为π∗s＝（P∗S（ts1），…，P∗S（tsg）），前后具有替换关系服务组合策略P∗S（tsw）和P∗S（tsw＋1），P∗S（tsw）也不再适应于t Sw＋1时刻网络的拓扑结构Gseroverlay（τi）（τi＜tsw＋1＜τi＋1，τi，τi＋1∈T′）

证明： 假定命题不成立。 设存在一组发生了服务组件替换的最优服务恢复路由策略πAS＝｛PAS（ts1），PAS（ts2），…，PAS（tsg）｝，时刻tw之后具有前后接续关系的两服务组合路径分别是PA（tw）和PA（tw＋1），其对应的服务路由分别PAS（tw）和PAS（tw＋1），则时刻tsw时对应的服务路由PAS（tsw）满足时刻tsw＋1之后的网络拓扑结构Gseroverlay（τi），（τi＜tsw＋1＜τi＋1）。设在时刻tsw＋1之后，组合服务路径PA（tsw）不适应当前网络拓扑结构的时刻为tw＋h，tw＋h时对应服务组合策略为PA（tw＋h），则该服务组合恢复策略的最小干扰强度为：

假设服务组合策略πB＝｛PB（t1），PB（t2），…，PB（tw），PB（tw＋h），…， PB（tl）｝，对其中每一条服务组合路径PB（tv）＝PA（tv），v＝t1，…，tw， tw＋h，…，tl，该服务组合策略的最小干扰强度为

由于NPB（tw）→PB（tw＋h）≤NPA（tv）→PA（tv＋1）且用户感知干扰函数I（·）单调递增， 所以

I（NPB（tw）→PB（tw＋h））≤I（NPA（tv）→PA（tv＋1））

因此，与最初假定A是最优服务组合策略相悖，所以原命题成立。

上述分析为我们设计基于用户感知最小干扰的服务恢复算法提供了重要的设计原则：

①为使用户感知到的服务中断干扰最小， 首先选择网络层对服务路径进行修复， 减少重新发现服务组件的开销以及建立新的服务路径及底层网络无线链路的代价， 尤其是在网络规模较大的时候， 收益更加明显。

②若网络层修复无法在服务组件之间重新建立底层网络无线链路， 服务路径重建失败； 将启动服务层上基于用户感知最小干扰的服务恢复策略。