基于终端干扰和链路稳定性的多终端协同维护机制

张洁，芮兰兰，郭少勇，邱雪松，丁一凡

（1. 北京邮电大学 网络与交换技术国家重点实验室，北京 100876；2. 北京交通大学 高速铁路网络管理教育部工程研究中心，北京 100044）

1 引言

泛在末梢环境是由处于用户周边终端形成的智能空间，在移动自组织网(MANET, mobile ad-hoc network)组成的泛在末梢环境中，常以面向业务的多终端协同的方式为用户提供无处不在的泛在业务[1]。然而，终端移动性造成的网络拓扑动态变化[2]、有限的终端资源属性[3]造成协同方案的不确定性，是协同执行潜在的失败风险，并且，失败引起多终端协同方案切换，对用户产生干扰。因此，需要构建一个多终端协同维护机制，保证泛在业务执行的可靠性和持续性，从而保障用户体验。

构建多终端协同维护机制面临以下挑战：首先，在动态的网络环境中，如何估计终端移动性，构造可靠的协同方案；其次，在切换多终端协同方案的时候，如何尽可能地减少对用户的干扰；最后，协同方案要在满足有限终端资源的同时，实现多样化的业务质量(QoS, quality of service)需求。

目前，有关多终端协同维护的研究成果不多。通过预估终端移动性的方法可以提高所选协同方案的可靠性[4～7]。文献[4,5]使用 GPS等设备提供的位置信息，无需复杂计算，选择可靠的协同方案，但会产生额外的辅助设备负担，在一些特定环境中无法使用(如地下)。文献[6]基于移动模型，使用概率统计的方法进行协同方案的构建，在扩展方面有局限性。文献[7]通过终端当前的属性，如信号强度来预测移动性，没有设备负担，而且扩展性较好。但目前，较多存在于链路层，缺乏面向业务的应用。本文将结合这种方法，在设计面向业务的协同维护时，通过对终端自身属性的计算确定可靠性指标。

采用优化算法可以有效提高协同方案的可靠性[8,9]。文献[8]基于贪婪路由算法，提出了一个新的预测链路生存期的方法，以便在进行终端协同选择的时候更加高效。文献[9]在贪心算法的基础上，结合执行时间，采用动态规划算法解决终端协同中的开销问题。以上两者均未考虑协同方案在切换时对用户的干扰，在发生多次中断时难以保证最佳用户体验。

针对协同方案切换产生的干扰，文献[10]通过表征节点失败引起的中断，提出了最小化切换代价的协同方案(MDSCR, minimum disruption service composition and recovery)，但是缺乏对链路稳定性和多样化QoS需求的考虑。文献[11]利用局部恢复和可靠路径，基于概率分析提出了一个快速计算中断干扰的算法，没有计算终端自身属性对 QoS的影响。

为了解决上述问题，本文通过在泛在末梢环境中抽象出泛在业务执行问题模型，并结合泛在业务特征，建立了满足个性化用户需求的指标，提出一个新的多终端协同维护机制(MDCMM, multi-devices cooperation maintenance mechanism)。MDCMM基于容忍干扰和链路稳定性来计算可靠性，并结合持续性指标确定维护评价函数。MDCMM包括初始化部署、协同构造和协同重构3个阶段，具有动态规划最优子结构的特点，并且克服了现有动态规划协同维护策略的不足。仿真结果表明，MDCMM能在满足QoS的前提下减少整体和局部维护代价，有效保障用户体验。

2 场景及模型

建立以MANET为背景的泛在末梢环境下的终端协同场景，包括用户层、业务层和网络层。当用户发起一个泛在业务时，通过起始终端设备将子业务的协同关系发布到网络层中，获取网络层中的可用终端信息，选择执行终端执行对应的子业务，以满足需求用户的要求。如图1所示，泛在业务由S1到S4顺序完成， MDCMM经过协同构造后，使S1的执行终端为 11，S2的执行终端为 22，它们之间用λ1、转接终端和l2连接。某时刻l2发生失败，MDCMM将进行协同重构，以最优的全局维护评价指标，维护业务的持续和平滑进行。

图1 泛在业务场景

2.1 问题模型

1) 网络模型

网络模型用GN=(D,L,I,TP)表示。由于网络拓扑随时间动态变化，将泛在业务执行时间T设置为基于中断时刻的离散变量(t1,t2,…)，其中Ti表示时间段[ti,ti+1)。在时间段Ti内，网络拓扑保持在ti时刻的状态不变，终端集合D={di︱i=1,2, …}，无线链接集合L={li︱i=1,2, …}，终端干扰能力集合I={Idi︱i=1,2, …}，以及链路持续时间集合TP={TPi︱i=1, 2,…}均不变。其中，两终端之间的链路表示为P(d,d')(t)={d1,…,dn,d1=d,dn=d’}。如果终端不再满足质量需求，或者移动到通信范围外时，网络中的节点和边会被删除。

2) 业务模型

业务模型用一个有向无环图GS=(S,E,IS)表示。其中协同关系由一系列子业务构成，第i个子业务Si和下一个执行业务Si+1之间用有向边Ei连接。当网络层中与Si和Si+1对应两终端间的链路失败时，Ei被删除。

2.2 评价指标模型

综合上述网络模型和业务模型，选择终端执行泛在业务的问题，即从GN=(D,L,I,TP)中选取符合GS=(S,E,IS)的子图，包括终端选择RD=(ds1→ds2→…→dsr)和链路选择RP=(P(d1,di+1)|i=1, 2,…,r-1)。

建立以协同方案评价指标为目标函数的数学模型来解决该问题。为了使用户感知到的干扰最小，保障用户体验，建立指标函数来评价中断干扰对用户的影响，下面给出评价函数的相关计算。

协同方案的不可靠性引起泛在业务的中断。用中断时间所占的比例C作为泛在业务持续性指标，如式(1)所示。C越小表示协同方案不容易发生中断，持续性越好。

假设R(tj)是tj时刻的协同方案，R(tj+1)是tj+1时刻的协同方案，Δtj为中断时间，即从方案R(tj)切换到方案R(tj+1)花费的恢复时间。在协同维护过程中，Δtj是动态的，由于网络拓扑的不确定性等，中断时间很难计算，此过程对用户的干扰很大程度上依赖于终端和链路两方面，可从这两方面来定量计算Δtj。

用ND(Δtj→Δtj+1)表示从方案R(tj)切换到方案R(tj+1)的替代终端数如式(2)所示。

其中，r是子业务数目，|R(tj+1)∩R(tj)|是2个集合中的相同节点数目。同样，假设P(tj)是tj时刻的路径，P(tj+1)是tj+1时刻的路径，用NP(Δtj→Δtj+1)表示从路径P(tj)切换到路径P(tj+1)的替代链接数

基于以上预测，结合终端和链路的性质，重新定义评价指标。从方案R(tj)切换到方案R(tj+1)花费的恢复时间Δtj定义如下

其中，ρ和δ是常数，表示终端和链路因素各自所占比重。Idk为终端干扰效益，ε为链路稳定性。

2.3 MDCMM问题阐述

基于上述评价指标的定义，下面将描述MDCMM问题。根据2.1节中离散时间(t1,t2,…)的描述，定义多终端协同维护为一系列协同方案：R=(R(t1),R(t1),…R(tn))，其中，0=t1＜t2＜…＜tn＜T。R包括最初的协同方案R(t1)和所有的维护方案R(tj)→R(tj+1)，j=1,…n-1。

在网络GN(tj)中，当且仅当协同方案R(tj)中所有的链路都存在的情况下，R(tj)是可行的。进而当且仅当每个协同方案R(tj)在时间段[tj,tj+1)内是可行的情况下，R是可行的。在GN(t)中，定义所有的可行协同方案集合为S(GN)。每个可行的R对应一个指标为

MDCMM问题的目标：在集合中S(GN)寻找可行的最优决策R，使指标C(R)最小化，最终抽象出目标函数(见式(6))，用来评价最佳协同方案。

3 MDCMM优化算法

3.1 动态规划算法

由以上阐述可知，MDCMM问题可表示为多阶段决策最优化问题。为了对MDCMM问题进行优化求解，接下来，将分析网络拓扑已知情况下的动态规划算法，以及网络拓扑未知情况下的预测计算。

在网络拓扑已知的情况下，GN(tj)是确定的，MDCMM 是一个动态规划问题。用f(R(tj))表示tj时间段，使用业务组合方案R(tj)情况下的最小代价

式(8)描述了从R(tj)切换到R(tj+1)的最优维护方案，第一部分表示从失败的方案R(tj)到新的方案R(tj+1)的评价指标，第二部分刻画了新方案的持续性。可采用自底向上的计算方法，逐步构造满足最小维护代价的方案。

在泛在末梢环境中，由于节点移动性造成网络拓扑不确定性。而ti+1时刻的维护决策需要知道该中断时刻后的网络拓扑来计算f(R(tj+1))。所以接下来，将结合可靠性预测来解决该问题。

3.2 可靠性预测

给出终端干扰。在计算终端干扰效益之前，根据子业务对终端各项属性的要求来确定子业务的容忍干扰效益，作为选择终端的限定条件。

1) 容忍干扰效益ISi。泛在业务具有个性化的资源需求，当终端因为能力受限产生干扰时，子业务Si所能容忍的极限值如式(9)所示，对能量ESi、带宽BSi、执行时间TSi进行归一化处理。

其中，能量最小值min(E)，带宽最大值max(B)，服务时间最大值 max(T)是子业务所能容忍的各项能力极限值。α、β和γ为相应的权值系数，表示不同的泛在业务对终端自身能力的偏重。如多媒体业务对实时性的要求比较高，因此强调干扰因素执行时间，文件下载业务则更偏重干扰因素带宽，这些偏重决定了α、β和γ的取值。

2) 终端干扰效益Idk。结合受限的终端能力对业务执行产生的干扰效益进行计算，如式(10)所示，对终端dk的属性能量Edk、网络带宽Bdk、执行时间Tdk进行归一化处理。

其中，能量最小值 min(E')，物理带宽最大值max(B')，服务时间最大值 max(T')是终端的各项能力极限值。只有当终端的各项能力满足子业务的容忍值，并且终端干扰效益小于容忍干扰效益时，终端才可选。

结合终端属性，采用预测的方法计算链路不稳定性。

3) 预估链路稳定性LS。链路持续时间TP越长，说明路径失败频率越小，网络路径越稳定。将链路持续时间与其下限的比值作为链路稳定性LS测度为

通过获取网络中任意时刻的终端接收信号强度，估计链路持续时间TPdi→di+1来表征链路可靠性。TPlimit表示链路持续时间下限。其中r表示网络中终端的通信半径，在初始化时设置，v表示终端间的相对移动速度，可由计算得出[7]。

4) 链路失败频率。终端间链路稳定性的倒数。

求解过程实际上就是计算所有状态值的过程。根据式(4)，第一部分的计算要枚举网络中的所有能组成协同路径的可用终端，为了在网络规模较大的情况下较少计算量，优先选择具有较高可靠性的终端。在计算终端干扰效益之前，根据子业务对终端各项属性的要求来确定子业务的容忍干扰效益，作为选择终端的限定条件。针对网络GN中，未来时刻的变化无法获悉的情况，按式(11)和式(12)，采用预测的方法预估链路不稳定性，选取与最优子结构最接近的方案。

3.3 MDCMM流程及说明

以一个泛在业务为例介绍维护机制的工作流程，如图2所示。

1) 初始化部署

用户发起泛在业务U请求时，初始化业务模型GS=(S,E,IS)和网络模型GN=(D,L,I,TP)，构造4个数据集合SS、DS、ADS和ODS。SS是泛在业务集合，包括U的终端协同信息，Si的容忍干扰DSi、BSi、TSi。DS是终端集合，包括各个终端dk所能提供的业务Sk及其干扰能力。ADS是可用协同方案，包括执行每个子业务的终端及其信息，初始时刻为NULL。ODS是最终协同执行方案，包括执行每个子业务的终端及其信息，初始时刻为NULL，如图3所示。

此外，还要确定质量需求和网络中终端各项能力的极限值。不同的泛在业务，对业务质量有不同的需求，由此需要确定α、β和γ。用户对终端自身的质量和路径的质量有不同需求，由此确定δ和ρ。

图2 维护机制工作流程

图3 初始部署

2) 协同构造

包括协同发现、协同选择、协同执行3个阶段。协同发现是对复杂的泛在业务请求做出响应，构造子业务协同方案，此阶段得到一个可用协同方案集合ADS；协同选择是从协同发现阶段的协同方案集合 ADS中，进行终端选择和网络路径选择，即为每个子业务选择执行终端以及2个子业务相邻的执行终端间的链路，构造满足需求的协同执行方案；协同执行即子业务的协同执行过程。具体分为以下几个步骤。

①根起点d1产生源数据流，将初始化协同关系信息封入数据分组内，在网络中进行广播，寻找能提供子业务的终端。

②终端d1接收到请求分组以后，如果该终端能提供终端协同关系中相应的子业务，且满足Ek＞ESi，Bk＜BSi,Tk＜TSi，则发送应答信息给d1；如果不能提供则转发该广播信息。

③每个终端dk估计其与各邻居终端的链路稳定性LSdi→di+1，也将这个信息发送给d1，形成ADS信息集合。最终根起点d1计算f(R(t1))，从而确定使其最小的各个子业务的执行终端，存入 ODS中。同时，根起点d1产生监控分组。

④选择网络路径：根据集合 ODS中的协同信息，依据IP层建立起通信路径。借用按需路由协议(AODV, ad hoc on-demand distance vector routing)里的Hello分组进行消息广播，综合考虑链路稳定性，选择稳定链路建立端到端路径。

3) 协同重构

①根据根起点d1产生的监控分组，获得执行终端的质量和泛在业务完成情况。

②若发现发生业务失败时，进入到协同重构阶段。从上次决策过程得到的集合 ADS中，选择最优协同方案，存入ODS中。

③如果不存在协同方案则重新发起业务请求，进行一次新的协同构造，计算恢复代价，选择使式(8)最小的协同方案R(tj+1)。确定各个子业务的执行终端，更新ADS和ODS信息，为下一时刻的维护过程做准备。

4 仿真实验

本文提出的多终端协同维护机制，提高协同方案可靠性的角度保持泛在业务执行的持续性，降低干扰对用户的影响。为验证本文提出机制的有效性，设计并搭建了实验环境，并对结果进行了比较和分析。

4.1 仿真设置

1) 网络设置。基于现有的面向业务的多终端协同选择框架[12]，以 OPNET 为仿真平台模拟MANET 组成的泛在末梢环境。在大小为1 000 m×1 000 m的网络中，随机分布30个移动终端，以支持泛在业务的提供。

3.绩效考核体系具有客观公正性，因此可以很好的区分职工工作状态是高效还是低效，根据不同职工工作水平决定他们不同的工资和福利待遇，合理的分配奖金和晋升机会，这样才能可以对员工起到激励作用。

为了使网络中的终端更好地提供 MDCMM 中的泛在业务，设置了3种属性。①终端移动性：每个终端均使用manet_station的移动模型，均具有接收和转发数据分组的功能，终端遵循随机移动模型，以向量路径（VECTOR）方式移动，最大速度默认为10 m/s。②终端能力：每个终端均能提供电池能量(E)、带宽(B)、服务时间(T)3种属性。③链路状况：考虑2个终端之间存在通信时，链路的稳定性，参数在表1中给出。

2) 业务设置。在网络中设置具有由5个子业务按照串行顺序组合而成的协同关系的泛在业务请求。每个子业务对应的可用终端数目默认为 3。终端1a提供业务S1，源业务流的到达时间间隔服从指数分布（CBR），使用恒定比特率CBR流来模拟数据流量，数据分组长度为512 bit，数据分组间隔为1 packet/s。参数的具体说明如表1所示。

表1 泛在环境参数设置

4.2 实验指标

在仿真过程中，首先从可用终端数和移动速度对目标函数进行影响因子分析；其次为了评价MDCMM机制的性能，在多终端协同执行过程中，从切换代价和用户体验方面进行了评价，设置实验指标如下。

1) 目标函数。是子过程切换代价之和C(R)，表示在发生中断的情况下整体业务质量的优劣。目标函数的值越低，业务可靠性和持续性越好。用于对MDCMM机制的分析和比较。

2) 业务平滑性。用 2个指数来表示业务平滑性，评价用户体验。

一是各个子过程中干扰指数CI，根据持续性指标计算(见式(13))，CI浮动越小，说明相邻子过程的切换具有越平滑的波动，用户体验越好。用于对MDCMM机制的分析。

二是各个子过程中目标函数的方差CS(见式(14))。该值越小，说明维护越稳定，用户体验越好。用于对不同机制进行比较。

分别对 MDCMM、MDSCR[10]和 MPCMM 3种不同的机制在相同参数设置的场景中进行实验，说明MDCMM的优越性。其中MDSCR是基于预测的维护机制，选择具有最长预估链路持续时间的终端协同方案；MPCMM是基于ad hoc最短路径路由算法的维护机制，以跳数作为选择标准。实验是比较不同机制对用户的干扰。

4.3 结果分析

通过以上环境设置，在OPNET中进行仿真。将得到的评价指标数据输出到 MATLABR2013a中，进行比较分析。

1) 目标函数影响因子

如图4所示，设置横坐标为中断次数n，纵坐标为评价函数。移动终端的最大速度设置为5 m/s、10 m/s、15 m/s；网络中的最大可用终端数分别设置为1～5。

由图可知，评价函数是随中断次数n而增加的。横行对比图，在最大可用终端数固定的情况下，终端移动速度会对评价函数造成影响。在具有较高动态性的MANET中，失败率增加，评价函数数值较大，说明维护花费更高。

图4 目标函数影响因素分析

纵向对比，在网络动态性固定的情况下，分析可用终端数的影响。以图4(b)为例，终端最大速度为10 m/s，可用终端数不同，目标函数的曲线发生变化。如果每个子业务具有较多的可用终端，在协同构造过程中，对可用终端的搜索和计算将会更复杂，并且由于不可靠终端增加，因此评价函数更高。可用终端数目为4和5时，曲线差别不大。另外，可用终端数的影响在中断次数较多时表现得尤其明显。

2) 不同机制目标函数的比较

为了对MDCMM、MDSCR和MPCMM机制进行比较，在相同的环境和终端参数设置下进行仿真，每次仿真时间为2 000 s。

图 5给出了在终端移动速度最大值为 5 m/s、10 m/s、15 m/s时，3种机制产生目标函数的比较，可以看出MDCMM具有较低数值的目标函数，并且，随着移动速度最大值增加，不同机制之间目标函数的差值也拉大了。因为MDCMM优先选择具有较小干扰能力，并且可以稳定执行业务的终端和路径，保证业务执行。而MDSCR和MPCMM均没有考虑终端干扰给QoS带来的不可靠性，前者选择的协同方案具有最长持续时间，后者选择的协同方案具有最少跳数。在这些协同方案中，执行终端可能会因为电量不足，带宽超出等受限的自身能力等，对业务维护产生干扰，不能给用户很好的QoS体验。

图5 不同机制目标函数比较

3) MDCMM平滑性

延长仿真时间，移动终端的最大速度设置为5 m/s、10 m/s、15 m/s，其他参数取默认值，在OPNET中设置随机种子进行多次实验。取前5次多终端协同维护过程，比较泛在业务干扰指数CI变化幅度。

依据各子过程的维护代价来计算泛在业务干扰指数CI，由图6可知，业务的CI指数抖动较小且变化平缓。整体看，移动终端的最大速度越小，干扰指数CI越大，变化幅度在取值范围内较小，平滑性较好。

图6 MDCMM平滑性

4) 不同机制平滑性比较

设置默认可用终端数目数，改变终端移动速度最大值为5 m/s、10 m/s、15 m/s，分别计算3种机制的平滑测度。

如图7所示，可以看出MDCMM和MDSCR的目标函数方差明显低于MPCMM，因为MDCMM和MDSCR均采用具有最优子结构的算法，选取维护代价最小的协同方案。而相比MDSCR，MDCMM使协同方案的维护更稳定。

图7 不同机制平滑性比较

5) 不同机制预测效益比较

从图8中可看出，与MDSCR和MPCMM相比，MDCMM的预测效益更接近1。MDCMM是0.9～1.0，MDSCR是0.80～0.95，MPCMM 是0.70～0.97。

图8 不同机制预测效益比较

5 结束语

协同维护是泛在网络中的一个重要问题。是泛在网络中，终端的类型得到了扩展，能更好地为用户提供服务。但是由于终端本身的能力受限，以及网络的动态特性，泛在业务会发生中断，从而影响用户体验。

本文提出了维护机制 MDCMM，用维护评价指标将协同构造和协同中断恢复2个过程综合起来，采用了动态规划优化策略。实验表明MDCMM能减少泛在业务执行时间内中断对用户的干扰，保障用户体验。接下来的工作将在构建协同方案的时候，考虑终端协同需求，如相邻子业务之间的协同意愿、协同时间、协同资源分配等，进一步提升用户体验。

[1] BRONSTED J, AARHUS U, AARHUS D. Service composition Issues in pervasive computing[J]. IEEE Pervasive Computing, 2010, 9(1): 62-20.

[2] VASKAR R, CAO J N, WU W G. Reliable service discovery in MANET[J]. Pervasive and Mobile Computing, 2011,7(1):140-158.

[3] LIU C, CAO J, LE M F. A low-latency service composition approach in mobile ad hoc networks[A]. The 29th Annual ACM Symposium on Applied Computing (SAC'2014)[C]. Korea, 2014.

[4] JIN L, LI L Y, ZHU X Y. A multi-constraint QoS routing protocol with route-request selection based on mobile predicting in MANET[A]. International Conference on Computational Intelligence and Security Workshops(CIS)[C]. Harbin, China, 2007.342-345.

[5] CHOUDHURY P. Mobility aware distributed service composition framework in SOA based MANET application[A].The 10th IEEE In-ternational Conference onIndustrial Informatics (INDIN)[C]. 2012.1016-1021.

[6] WANG J P. Exploiting mobility prediction for dependable service composition in wireless mobile ad hoc networks[J]. IEEE Transactions on Services Computing, 2011, 4(1):44-55.

[7] 吴大鹏, 武穆清. 面向链路稳定性的MANET路径建立机制[J]. 电子与信息学报, 2009, 31(9): 2226-2231.WU D P, WU M Q. Reliable routing mechanism in MANET towards link stability[J]. Journal of Electronics ＆ Information Technology,2009, 31(9): 2226-2231.

[8] HADI N, QIANG N, MING Y. A new link lifetime prediction method for greedy and contention-based routing in mobile ad hoc networks[A].The 10th IEEE International Conference on Computer and Information Technology (CIT 2010)[C]. 2010.2662-2667.

[9] WANG X M, WANG J P, ZENG Z Y, Service composition in service-oriented wireless sensor networks with persistent queries[A].IEEE Communications Society[C]. Washington, D C, USA,2009.1-5.

[10] JIANG S S, XUE Y, SCHMIDT D C. Minimum disruption service composition and recovery in mobile ad hoc networks[J]. Computer Networks, 2009, 53(10):1649-1665.

[11] XIAO L, NAHRSTEDT K. Minimum user-perceived interference routing in service composition[A]. Proc of IEEE INFOCDM[C]. 2006.

[12] 郭少勇,芮兰兰.面向业务的多终端动态协同构造机制[J]. 电子与信息学报, 2012,34(7):2226-2231.GUO S Y, RUI L L. Service-oriented multi-devices dynamic cooperation mechanism[J]. Journal of Electronics & Information Technology,2012, 34(7):2226-2231.