3.3.2 基于服务强度及生存时间的服务路径生成算法

3.3.2 基于服务强度及生存时间的服务路径生成算法

本章采用经典图论中有向无环图DAG理论来设计服务路径生成算法［73，74］，鉴于VANETs高动态性，我们提出了基于服务强度及链路生存时间来最优选择下一服务实例的路径生成策略： 在服务覆盖层中提取服务节点信息及服务链路当前状态来共同决策并驱动功能图中实现fi的服务组件实例化进程， 该方法在增强服务路径稳定性及可靠性的同时最大限度地减小服务路径解空间， 提高了服务组合的成功率及执行效率。

首先， 我们给出算法设计中用到的两个指导服务选择关键参数： 链路生存时间和服务强度。 服务覆盖层中支撑服务路径的底层路由链路上任意节点间断链就导致整条服务路由的失败。 为提高服务路径的稳定性及可靠性， 我们考虑选择链路生存时间较长且服务强度较大的服务组件来完成相应的功能fi，争取最大服务路由生存时间。

定义3.18 （路由生存时间）：

路由生存时间RLT （Route Life Time） 由相邻节点所维系的链路生存时间的最小值确定， 即

RLT＝Min{LET（li，j）}　（3－35）

式中li，j表示路由链路中相邻两节点之间的无线链路，LET（li，j） 为链路li，j的预测生存时间。 当一个节点从另一个节点的通信范围内移出时， 就会发生链路中断。

接下来我们就链路预测生存时间的求解过程给予详细说明。假设lij为某时刻VANETs节点Ni和Nj之间的无线链路。基于对移动节点运动矢量和有效通信范围的分析，可计算出节点Ni与节点Nj的链路预测生存时间LET（li，j）等于节点Ni运动出节点Nj有效通信范围时所需要的时间ty。如图3.7所示，在t1时刻节点Ni运动到Nj节点的有效通信范围内时，节点Ni广播的Hello－（t1） 报文被节点Nj接收到，Nj节点记录Hello－（t1） 报文中携带的位置及时间信息，并把其加入邻居节点。在t2时刻，Nj节点再次接收到Ni节点发出的Hello－（t2） 报文，通过提取该消息中的位置及时间信息，可以计算得到Δt＝t2－t1时间段内节点Ni的移动速度。同样，可以通过t1，t2时刻及Nj节点内的GPS模块得到Nj节点在这两个时刻的位置信息，进而得到Nj点的移动速度。进一步，可以通过向量减法得到Ni点相对于Nj点的相对速度。

如图3.8所示，设节点无线传输有效通信半径为R，在t2时刻，移动节点Nj运动至Q点，Ni运动至O点。

利用向量点积关系计算可得，

经由三角关系和勾股定理计算可得：

应用余弦定理可得当前链路lij的预测生存时间tij为：

以上关于VANETs中车辆节点间链路预测生存时间的推导适应于任何移动模型，因而公式（3－38） 可以很好的涵盖不同运动场景下链路预测生存时间的计算。 事实上， 在选择的MH移动模型中， 车辆在各自车道上行驶， 而每一条车道上的节点只有相同（α＝0） 和相反 （α＝π） 两种运动方向， 因此预测生存时间相对简单，只需代入公式（3－38） 即可。

接下来， 我们讨论影响服务选择的第二个关键因素， 服务强度。

定义3.19 （服务强度SI）：

服务强度是对车载终端Ni获取服务组件sj能力的定量表达， 可记作Abi Ni（sj），表达式为：

其中，Qj是节点Nj提供服务sj的能力，与其发射功率成正比，dis（Ni， Nj） 表示从当前节点Ni到节点Nj的跳数，α为一个常数，并不影响服务发现的决策。

我们采用图论中有向无环图DAG理论来设计服务路径的生成算法， 改进了传统图论求解服务组合路径的思路， 结合VANETs典型动态特性， 提出了基于链路预测生存时间及服务强度最优策略来高效进行服务实例选择算法，具体步骤如下：

步骤1： 假定复合服务具有功能自动拆分能力， 基于用户服务组合请求生成的服务组合方案DAG图中含有m个服务组件：S＝ ｛S1，S2，…，Sm｝，系统预定义生成具有相同功能的每个服务组件所属服务区域： SA（Sj）＝{s1j，s2j，…，smjj} （1≤j≤m，mj＞0），其中，smjj为具体的服务实例。如图3.9所示， 其节点表示完成某种功能 （任务） 的服务区域。

步骤2：在DAG图中，基于以下步骤判断当前节点Vi与前趋节点Vj的QoS是否保持一致：

①假定当前节点 Vi与前趋节点 Vj所属的服务区域分别为SA（Si），SA（Sj）。

②对SA（Sj） 中的每个元素snj（1≤n≤mj），与SA（Si） 中的所有元素sni（1≤n≤mi）进行两两比较：若出现，则将snj从服务区域中删除；若出现，将snj标记为有效候选服务。

步骤3： 在服务覆盖层中提取节点服务信息、 节点移动信息及物理网络层路由链路状态，依照公式（3－39） 及公式（3－38） 计算实现下一功能fi＋1的服务组件在当前车辆节点Vi处的服务强度Abi Ni（sj）以及服务组件所在链路预测生存时间tij，加权平均后排序。选择结果最优及次优的服务组件作为服务选择返回值生成最终服务路径， 则构成一张子图G′（V′， E′）， 图的顶点V′为相应服务区域中实例化后的服务组件snj，边E′表示两个服务实例Vi与前趋节点Vj之间存在输入输出关系，同时实现服务强度及链路连通时间加权平均最优， 并满足QoS一致性。 如图3.10为按照本研究思路生成满足QoS要求的服务路径执行过程示意图， 表3.2为本章提出的服务路径生成算法。

综上所述， 服务路径生成算法的设计思路是， 基于图论知识结合VANETs节点移动性特征， 提出一种基于服务强度及链路预测生存时间的服务路径生成算法， 即服务路径将沿着服务强度增加最快且路由预测生存时间最长的方向建立。 如何权衡两者达到最优， 本算法采用加权平均的思想， 将会选择其邻居节点中服务信息强度与链路生存时间加权平均值最大的节点作为下一跳服务节点。 该算法不仅提高了服务执行路径的稳定性及可靠性， 也大大缩短了下一步执行路径选择的解空间， 提高了服务组合的执行效率及成功率。