2. 北京邮电大学 网络与交换技术国家重点实验室, 北京 100876
综合业务模型和网络模型提出了面向多业务的终端聚合问题模型, 并在此基础上, 提出了一种面向多业务的终端聚合算法, 包括多终端协同集合的构造与决策两部分.通过仿真与面向业务的终端组合模式及随机分配算法比较可知, 所提算法具有更高的性能.
2. State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China
It is critical problem how to meet all requested ubiquitous services simultaneously in ubiquitous stub environment with resource-limited devices and bandwidth-limited network. To achieve this goal, we first formulate multi-devices cooperation problem with ubiquitous service model and network model. And then a devices aggregative mechanism is proposed to support two key modules of multi-devices cooperation set construction and decision-making. At last, the simulation is implemented with OPNET and Matlab. The result shows this mechanism has better performance than others.
目前，泛在网成为了国内外研究关注的焦点[1].随着网络泛化的发展，各种终端具有不同的能力并逐步开放，如存储能力、接入能力、计算能力和播放能力等，通过协同扩展分布式的业务能力来支持泛在末梢环境的自助服务[2]，使用户任何时间任何地点享有高质量的服务.如何权衡多用户的效益，避免为保证某个用户的业务质量而影响到其他用户的体验，提高泛在末梢资源的使用效益，是泛在末梢环境提供自助服务的关键问题之一.
在移动自组织网络中，典型的2种面向业务的终端协同机制为动态任务嵌入选播(DTA, dynamic task-embedding anycasting)[3]和选播服务导向装置(SDA, service-oriented device anycasting)[4]模型. DTA利用基于树的业务模型，而SDA是弥补了DTA描述业务种类局限性外，融合业务间的质量约束而提出的一种基于图的泛在业务模型(USM, ubiquitous service model).然而，二者均是支持面向单业务的多终端协同构造机制，无法适用于未来多泛在业务环境.另外，Su等[5]提出一种面向业务的终端组合(SODC, service-oriented device composer)模式，仅解决了多业务组合分配过程的组合问题，但该机制的参数需用户干预设定，导致难以支持多样性的业务以及业务失败率相对较高.
为此，首先综合USM和网络模型(NM, network model)提出面向多业务的终端聚合问题(MSDP, multi-service-oriented devices aggregation problem)；然后针对MSDP，提出了一种面向多业务的终端聚合算法(MDA, multi-service oriented devices aggregation algorithm)，包括多终端协同集合(MCS, multi-devices cooperation set)的构造与决策模型，解决同时请求多个泛在业务时为业务选取相应的MCS来执行相应的业务；最后通过仿真与SODC以及随机分配(RS, random selection)算法进行比较，表明该算法具有较高的性能.
1 MSDP为了建立多业务的泛在末梢环境模型，将泛在末梢环境抽象为业务层USM和网络层的NM以及支持泛在业务i的MCS，如图 1所示，研究的问题是将GUSM(Si, Li)映射到GUN(D, E)中选取最佳的终端集合提供服务.
|
图 1 泛在业务场景 |
USM：每个泛在业务i(i=1, 2, …, n)用一个逻辑图的形式表示，即业务逻辑图GUSM(Si, Li)，包含业务集合Si={si, v|v=1, 2, …, Vi}和业务关联集合Li={li, u|u=1, 2, …, Ui}.其中，si, v为业务i中的第v个子业务，li, u为子业务间的第u条关联.
UN：在泛在末梢网络下，多业务终端通过无线方式组成UN GUN(D, E)，包括终端集合D={dk|dk, k=1, 2, …, K}和通信链路集合E={Ee|Ee, e=1, 2, …, O}，对应的终端dk的资源向量Rk={Rk, w|Rk, w, k=1, 2, …, K, w=1, 2, …, W}和链路Ee带宽资源Be.
MCS：对应执行一个泛在业务i中对应子业务的终端协同集合，标记为Ci, m(m=1, 2, …, Mi).表示Ci, m表示执行相应泛在业务Si的第m个MCS，每个Ci, m满足式(1) 和式(2) 的约束.
|
(1) |
|
(2) |
其中：dr为被选取来执行业务Si中子业务si, v，Ee为被选取执行业务Si中li, u关联.
为了抽象GUSM(Si, Li)与GUN(D, E)之间的映射数学模型，以业务质量为效益函数来衡量用户的体验.每个泛在业务i均有Qi个MCS，即Ci, m(m=1, 2, …, Mi).针对Ci, m引入Pi=[pmq]Mi×Q，其中pmq为衡量Ci, m的第q个质量指标.为了避免评价函数主观依赖性，利用TOPSIS(technique for order preferenceby similarity to ideal solution)多属性决策和方差最大化的权值计算选取最佳MCS.首先，为将指标进行归一化处理生成P′i=[p′mq]Mi×Q，将指标划分为以下2类.
效益型指标：其取值越大越好，如覆盖范围、可用带宽等指标，计算公式为
|
(3) |
其中：pq+=max{pmq|m=1, 2, …, Mi}，pq－=min {pmq|m=1, 2, …, Mi}.
成本型指标：其取值越小越好，如通信费用、传输功耗、业务距离等，计算公式为
|
(4) |
假设ωq(q=1, 2, …, Q)为归一化的权重，针对P′i=[p′mq]Mi×Q求取相应的正理想解V+=(v1+, …, vn+)和负理想解V－=(v1－, …, vn－)，其计算公式分别为
|
(5) |
|
(6) |
综合正理想解V+=(v1+, …, vn+)和负理想解V－=(v1－, …, vn－)来计算相应的距离ym+和ym－，进而求取效益决策值φi，即
|
(7) |
其中相应的权重ωq(q=1, 2, …, Q)为
|
(8) |
由此，该MSDP模型为
|
(9) |
其中xi, m、ym, v, ki和zm, u, ei为3个0-1变量，其定义为
|
在终端聚合过程中，将每个泛在业务分为等待、就绪和执行3种状态.其中，处于等待状态的泛在业务不会获取终端上所需的资源和网络链路上所需的带宽，处于就绪状态的泛在业务已经获得相应的资源和带宽并且准备执行，处于执行状态的泛在业务正在被执行.根据业务层协议(SLA, service layer agreement)赋予每个请求的泛在业务一个优先级.当网络资源紧张时，选择优先级高的泛在业务来优先执行，以实现不同级别业务的区分服务.同时，为了避免总有高级业务不断到达，低级业务总不能被执行的尴尬情况，在先前的高级业务被执行后立即提高这些低级业务的优先级.
为此，提出了一种MDA，如图 2所示，包含MCS构造和选取两模块. MCS构造模块是根据USM从UN中构造所有支持该业务的MCS形成Ci, m(m=1, 2, …, Mi)，将MSDP模型转化成MMKP模型.
|
图 2 面向多业务的终端聚合流程 |
在MCS构造过程中，就是将MSDP转化成MMKP，进而为每个泛在业务i形成Ci, m(m=1, 2, …, Mi).过程就是将终端资源和链路资源合并为一维约束，转化公式定义为
|
(10) |
|
(11) |
式(9) 转变为
|
(12) |
其中
|
由此，将MSDP转化成MMKP. MCS构造模块是根据USM从UN中构造所有支持该业务的MCS形成Ci, m(m=1, 2, …, Mi)转化成MMKP，然后利用现有的MMKP相关算法进行求解.
2.3 MCS选取模块另外，利用一种MMKP的近似算法WS-HEU[6]对(Web service selection-heuristic education)具有相同优先级的多泛在业务进行处理，选出一种服务效益最高的多终端聚合方案来执行泛在业务.
提出MCS选取的流程如图 3所示，分为以下3步.
|
图 3 MCS选取算法流程 |
步骤1首先将新到达的泛在业务置于等待状态，然后确定所有处于等待状态业务的优先级.根据优先级对所有的泛在业务请求进行排序，然后将排好序的泛在业务分为若干批，分批的大小会对稍后WS-HEU算法的性能产生影响.
步骤2将优先级最高的一批泛在业务添加到处理队列中，对处理队列中的所有泛在业务使用WS-HEU算法.若找到一个可行解，则将这些泛在业务转为就绪状态，等待执行，并查看是否还有别的分批，若存在，则重新执行步骤2，否则转入步骤3.若找不到一个可行解，则表明网络中不足于同时支持这些泛在业务，将该泛在业务中的部分提高优先级，并重置于等待队列中；另外，也要将当前处于等待状态的其他泛在业务的优先级提高，然后转入步骤1.
步骤3将处于就绪状态的所有业务添加到执行队列.
2.4 复杂度分析为便于分析MDA的时间复杂度，引入以下假设.假设1：所有请求的泛在业务具有相同的优先级；假设2：所有请求的泛在业务初始化时具有相同的质量等级数；假设3：每个终端提供的资源数目相同；假设4：所有请求的泛在业务对应的MCS具有相同的终端数目.符号说明如表 1所示.
|
表 1 符号说明 |
在MCS构造阶段，时间复杂度是由备选终端集合选取和关联约束2部分组成的.第1部分MCS构造和MSDP转换为MMKP需要VKW来完成；第2部分MCS选取是MUE.因此，MCS构造阶段的时间复杂度为O(n(VKW+MUE)).
在MCS选取模块中，时间复杂度和WS-HEU相同，则MCS选取模块的时间复杂度为O(n2(WK+E)(M－1)2).
3 仿真结果利用OPNET搭建仿真环境，相应的参数：业务数量为5、10、15和20；设备数量为60；每个设备支持5个不同业务类别；每个终端提供CPU频率(GHz)、内存(MB)和硬盘容量(MB)3种资源.
3.1 无资源竞争的场景在无资源竞争场景中，泛在末梢环境提供了充足的各业务所需要的资源.实验结果如图 4所示.平均效益的定义为
|
图 4 平均效益 |
在资源竞争场景中，泛在末梢环境所需要的资源不是很充足.实验结果如图 5和图 6所示.在资源不足的同一场景中，业务的总体效益反映各机制的优劣，MDA在业务数量为5、10、15和20的总效益分别为3.5、7、10.6和12.1，相比SODC的3.2、6.2、8.5和9.6提高了10%~30%，相比于RS的3.1、5.6、7.4和8.5提高了11%~40%.业务的成功率随着业务数量的增加而逐渐下降，MDA相对于其他2种方法提高了约8%以上.
|
图 5 效益分布 |
|
图 6 业务成功率 |
针对多业务的泛在末梢环境，提出了一种MDA，通过降维将MSDP转换成MMKP，利用TOPSIS方法来选择最佳的多终端集合以支撑相应的多业务执行，与SODC和RS相比，在平均效益、各个业务的效益以及业务成功率方面均有提高.但该算法是在一种理想的状态下研究的，在实际中，面向多业务的多终端聚合需要继续加强实验，为未来网络处于末梢的网络资源提供自助服务奠定基础.
| [1] | Ji Yang, Ping Zhang, Hu Zheng. Towards mobile ubiquitous service environment[J].Springer Wireless Personal Communications, 2006, 38(1): 67–78. doi: 10.1007/s11277-006-9024-y |
| [2] | Lu Shanshan, Chacan Gautam, Liu Yanliang, et al. Design and analysis of a mobile file sharing system for opportunistic networks[C]//20th International Conference on Computer Communications and Networks (ICCCN). 2011: 1-6. |
| [3] | Basu P, Ke W, Little T D C. Dynamic task-based anycas-ting in mobile ad hoc networks[J].Springer Mobile Networks and Applications, 2003, 8(5): 593–612. doi: 10.1023/A:1025198129990 |
| [4] | Su Wei-Tsung, Kuo Yau-Hwang, Huang Po-Cheng. A QoS-driven approach for service-oriented device anycas-ting in ubiquitous environments[J].Elsevier Computer Networks, 2008, 52(18): 3342–3357. doi: 10.1016/j.comnet.2008.09.001 |
| [5] | Su Wei-Tsung, Liao Ing-Hsiu, Lee Kuan-Rong, et al. Service-oriented device composition in resource constrained ubiquitous environments [C]//IEEE Wireless Communications and Networking Conference (WCNC), Las Vegas: [s.n.], 2008: 3110-3115. |
| [6] | Tao Yu, Yue Zhang, Lin Kwei-Jay. Efficient algorithms for Web services selection with end-to-end QoS constraints[J].ACM Transactions on the Web, 2007, 1(1): 103–126. |