基于贝叶斯网的移动互联网应用部署算法研究

张骥先

(云南大学信息学院，云南昆明650092)

移动互联网应用已经引发了信息产业的深度变革，具有分布性广、移动性强的特点［1－2］.一个移动互联网应用完整的业务流程一般会涉及到终端和服务端交互，例如苹果手机的智能语音助手Siri，手机终端采集用户的语音并进行识别，然后将识别后的信息传输至服务端，服务端将这类信息进行识别后的得到了用户意图，然后根据此意图进行知识搜索，并将搜索得到的结果传回手机终端展现给客户.在这个业务流程当中，手机终端负责采集用户的语音并进行识别，以及最后结果的展示.但是同样是语音助手，基于Android系统的大部分手机都是将语音流传输到服务器，在服务器上完成语音的识别.其中最主要的原因在于如果在手机终端完成语音识会耗费手机大量的CPU资源及电量;而如果将语音流传输至服务器的话可以节省CPU资源及电量，但另一方面又会耗费网络通信带宽［3－4］.

这个例子说明，一个移动互联网应用由多个功能模块组成(如例子中的语音识别模块，知识搜索模块)，其中一部分功能模块既可以在终端运行，也可以在服务端运行.应用部署指的是根据终端目前状态以及应用本身复杂度来决定应用中哪些功能模块在服务端运行，哪些功能模块在终端运行可以使应用服务质量最好，系统性能最优［5］.当前研究工作多是针对单一平台上简单应用提出的应用部署算法，且不适用于大型应用.而这些方面正是移动互联网应用部署从理论走向实际所需要解决的关键问题，主要涉及到以下几个方面:

1)应用模型:一个应用由若干个功能模块组成，应用模型反映出应用中所包含各个模块间的交互关系以及拓扑结构.当前的研究有几种主流的观点，分别是将应用的功能模块表示成图的拓扑结构［6－9］、树的拓扑结构［7］和弹性应用模型［8］.但这几类模型对简单应用较为适用，一旦应用复杂度增加，应用模块间相关程度增大，其拓扑结构复杂度会增大，直接影响了应用部署算法的效率及准确性.

2)应用部署算法:基于应用模型，应用部署算法会根据终端接入应用时的环境和状态计算出最合适的部署方案，然后将应用中的模块按照此方案部署到移动端或服务端，以求达到最优的用户体验和系统性能.部署算法主要分为静态算法与动态算法两种，静态算法具有较高的准确性，但计算量大，一般通过分类或聚类算法先期计算出预测模型，这意味着需要采集大量的用户数据来完成机器学习，从而在新用户接入应用时服务端可以快速计算出最恰当的部署方案;而动态算法不需要进行前期学习，根据终端首次接入应用时的状态进行实时的计算，性能及准确性不高.应用部署算法一般放在服务端执行，文献［6］属于动态算法，其采用线性优化进行部署方案的实时计算，而且未考虑模块节点的父节点对当前应用部署的影响，所得到的结果准确性低，且效率较低;文献［7－9］属于静态算法，其提出的应用部署方案计算方法虽然考虑到了历史数据因素，但是其基于朴素贝叶斯(naive Bayesian)的分类策略中存在特征属性不独立的问题，会降低结果的准确性，且其分类器训练较为复杂.

1 国内外研究现状

目前国内外对移动互联网应用部署的研究多是针对特定平台上简单应用进行的研究.

1.1 应用模型的研究

应用模型的一个主要研究内容是应用的拓扑结构，目前有几种主流的观点，分别是将应用模块间调用关系表示成图的拓扑结构［6，9］、树的拓扑结构［7］和弹性应用模型［8］.

Giurgiu 等和 Shumao 等［6，9］提倡将应用按模块(如Java类)之间的调用关系表示为有向无环图，G={B，E}，其中节点B代表模块;边E代表模块间交互.将应用模型表示为图拓扑结构的好处是比较适合于面向对象的应用开发方式，基本可以涵盖所有的应用，缺点是当应用结构变得复杂的时候，图也会相应变得复杂，直接影响到应用部署及迁移算法的效率.

Intel Labs Berkeley 的 Chun 等［7］提出了克隆云(clone cloud)的概念，为应用模型提出了一种新的思路，通过分析应用中函数调用关系，将应用体现为树的拓扑结构(profile tree)，树中每个节点代表一个函数，而边代表调用关系.树的拓扑结构比较适合于面向过程的应用开发方式，模块粒度多为函数级别，优点是较易分离出造成性能瓶颈的函数;缺点是此类应用的设计与实现不便，且模块间相互调用关系不易处理，树的拓扑结构并不适合于描述目前大多数的应用.

Samsung实验室的Zhang等［8］提出了弹性应用模型(elasticity patterns)的概念，应用中各模块叫做Weblet，并且支持在运行时对Weblet进行动态配置，旨在无缝并且透明地使用服务端来扩展移动设备受限的计算及存储能力.弹性应用模型会因不同的应用配置体现出不同的运行时行为，比如能量消耗、资费开销、应用性能，甚至安全与隐私特性，虽体现了应用部署的动态性但也存在一些缺陷，如Weblet在需要时才计算执行的位置，也带来了额外的开销，影响应用执行的效率.

通过上述研究可以发现，应用模型的主要工作是将应用描述为相互独立的功能模块.模块的粒度可能是函数、类、或者对象，采用图或树的方式来表现应用拓扑结构，并抽象出属性因素，建立应用代价模型.但随着移动应用的发展，应用模型会日趋复杂，之前的研究对如何简化应用拓扑结构并没有提出较好的方法，所以，简化应用拓扑结构是本文的主要的研究内容之一.

1.2 应用部署算法的研究

应用部署算法主要包括静态算法与动态算法2种，静态算法具有较高的准确性，但计算量大，一般通过分类或聚类算法先期计算出预测模型，这意味着需要采集大量的用户数据来完成机器学习，从而在新用户接入应用时给出较优的部署方案;而动态算法不需要进行前期学习，根据终端首次接入应用时的状态进行实时的计算，性能及准确性不高.目前的研究成果主要包括有遍历法［6］、线性规划法［7］、统计分类法［8］、最小生成树法［9］等几种方式来实现，其中文献［6］属于动态算法，文献［7－9］属于静态算法.

Giurgiu等［6］提出了适用于离线应用的ALL算法和适用于在线应用的K－step算法.前者通过遍历应用模型产生所有可用的部署方案，并找出其中执行时间最短的一个方案.后者选定一个入口功能模块作为初始子集，然后计算与当前子集距离为K的所有集合，并在上述集合中再选取执行时间最短的一个，将其作为新的子集迭代计算，直至应用模型遍历结束或达到移动终端限制.ALL算法的优点是可靠性高，缺点是耗时长，计算量大，并不适合实时的进行;K－step算法通过局部最优策略计算的应用部署方案，优点是计算速度快，计算量可控，缺点是随着应用功能模块的增多，算法计算量增大，且准确性下降.Giurgiu等通过测试指出在实际应用中功能模块之间的调用次数会直接影响结果，但并没有提出相应的解决方案.2种算法仅在应用运行前进行计算，无法实时、动态的调整.基于遍历法的应用部署方案计算方式需要对应用所有可能的部署方案进行实时计算，计算量相当大，即使对于服务端来说也是不能忽略的.

Chun等［7］在计算应用部署方案时不仅考虑到了应用的执行时间也考虑到了移动终端执行时的电量消耗，其应用部署方案的计算包括静态分析(static analyzer)、动态分析(dynamic profile)、优化配置(optimization Solver)3个部分组成.静态分析通过分析应用间函数调用关系，在代码中构建迁移点和还原点，决定哪些函数可以迁移到服务端执行，迁移点和还原点的构建也有一些限制;在动态分析中通过大量随机用例的执行，搜集应用中各个函数在移动终端以及在服务端执行时的代价情况，最后通过整数线性规划(ILP)算法得到应用最优的结果.但该算法计算量大，而且输入用例是随机产生的，并不能保证对应用中各函数完整的覆盖度.

由于将一个图划分成为K+1个满足预先设置条件的部分，各部分之间通信量最小这个命题已被证明是一个NP－Complete问题［10］，Shumao等提出的K+1 Coarse partition应用部署算法旨在找到符合限制条件的一种应用部署方案［9］，并不要求此方案是最优的.其算法的核心是HELVM(heavy edge light vertex)算法，HELVM 算法改进自RM、HEM 和LEM 算法［11－12］，是一种基于最小生成树的算法.其优点在于不仅考虑了边的权值(功能模块间交互)，也考虑了节点的权值(功能模块特性如所占空间及运行内存等)，使得带有终端限制的应用部署方案会更加合理.但是HELVM算法不是每次都能将恰好将图划分成K+1个部分，每部分恰好满足预先定义的限制(事实上大部分情况下不能)，一般需要多次执行才能得到理想的结果.此算法的复杂度是，计算量较大.

2 改进方案

应用部署需要客户端和服务端完成一系列的交互，其流程描述如下图所示:

2.1 应用模型及服务模型

传统的观念将一个应用中的模块以及模块之间的联系看做应用的拓扑结构，并称之为应用模型，但随着移动应用的发展，应用模型会日趋复杂，之前的研究对如何简化应用模型并没有提出较好的方法，本文提出服务模型的概念，将一个应用表示为若干个服务模型的合集，并针对服务模型进行分析处理，简化了应用拓扑结构.例如在一个手机应用当中，可能有网络通信模块，图形渲染模块，图片解码模块，语音采集模块，而这些模块之间会有数据通信，例如语音采集模块会将采集到的语音传送给网络通信模块进行网络传输.将这些模块和模块间通信抽象出来表示就形成了应用模型.应用模型指的是应用中功能模块的拓扑图结构，是一种有向无环图，其中应用功能模块代表有向无环图中的节点，功能模块之间的数据交互代表有向无环图中的边.如果两功能模块之间有数据通信是单向的，则边的表示具有方向性.

移动应用的发展使得一个应用可能包含多个服务，例如手机微信应用具有聊天服务，朋友圈服务，扫二维码服务，(简单类应用可视为提供单一服务).此类应用有几个显著的特点:

1)应用所提供各服务相对独立;

2)应用功能模块多、交互复杂，且一个功能模块可能被多个服务共享;

3)应用即使具有多个服务，用户同时也只能访问一个服务.

这种情况下对应用的所有功能模块进行应用部署方案计算寻找最优配置是非常耗时且基本不能完成的，所以，本文拟采用子图的方式来简化应用模型.其原理是以应用中的各服务为单位构建服务模型，各服务模型的并集组成完整的应用模型.服务模型是应用模型的一个子集，也是由应用功能模块代表的节点以及功能模块间交互代表的边组成，体现了部分的应用功能模块的拓扑图结构.

图2左侧的应用模型是由右侧的两个服务模型构成的，有些功能模块被不同的服务共享，如1，3，6，8等功能模块，而有些功能模块则只存在于某一服务中，如16，17，18等功能模块.由此可见，服务模型较为独立，更容易分析，可以有效降低分析整个应用模型的复杂度，提高应用部署算法效率，而对服务模型中各功能模块统计数据的汇总可以从应用层面清晰的观察到性能瓶颈或设计问题.

应用部署的最终目的是终端接入应用时根据终端当前状态(所处位置，网络状况，电量)决策应用模型或服务模型中哪些功能模块在服务端执行，哪些功能模块在终端执行.所以首先终端需要搜集当前的状态信息传输至服务器(图1中的step1)，服务器会根据这些信息结合应用模型信息计算出恰当的部署方案(图1中的step2)，服务端在计算部署方案时需要以下几类信息:

功能模块基本信息:

1)功能模块的类型(可移动的还是不可移动的，可移动的功能模块可以在服务端或终端执行);

2)当前模块所处服务模型;

3)功能模块的所占用的存储空间;

4)功能模块的运行时所占用的内存空间;

5)功能模块在移动终端运行时所耗电量统计;

6)功能模块的移动终端运行累计时间;

7)功能模块的数据输入量

8)功能模块的数据输出量

终端实时状态信息进行搜集，主要包括:

1)终端所接入的服务器;

2)终端当前电量;

3)终端当前网络状况;

4)终端当前CPU负载;

5)终端当前可用的内存及存储空间.

在终端上，这些信息采集后会被保存为XML格式的描述，然后在应用首次运行时发送到服务端.

2.2 基于贝叶斯网络预测模型的应用部署算法

移动终端接入应用后，会从服务端获得适用于当前情况的应用部署方案(图1中step3)，部署方案是服务端根据终端当前的状况通过一定算法运算得到的结果.本文中使用贝叶斯网络预测模型来获得应用的部署方案，基于贝叶斯网络预测模型获取应用部署方案是一种静态算法，需要预先通过大量的数据采用机器学习过程形成预测模型，当新终端接入的时候可以根据终端当前状态结合预测模型来确定每个功能模块的运行位置.贝叶斯网络依赖于稳定的网络拓扑结构，本文使用2.1中描述的应用模型或服务模型来做为稳定的拓扑结构;之后贝叶斯网络采集大量的数据进行机器学习，通过这些数据，可以更新每个功能模块在在不同位置运行的概率(后称之为预测模型).当有新的终端接入应用时，服务端会根据此终端当前的状态以及最新的预测模型计算出每个应用功能模块最适合的执行位置，以求达到最好的用户体验.这里需要指出的是服务端在首次运行时需要事先定义初始的预测模型.

服务端运行的贝叶斯网络预测模型算法实现如下，首先，我们假定每个可移动的功能模块的执行位置C依赖于此功能模块的基本信息r、终端状态信息s，图3说明了一个可移动的功能模块执行位置的决策依据，在此功能模块的基本信息r1以及终端当前状态信息s1的条件下，通过概率表可得出该功能模块在终端执行的概率是0.8，在服务端执行的概率是0.2，所以此功能模块适合在终端执行.

根据图4以及贝叶斯网络基本算法，我们可以得到任意一个功能模块在服务端或终端执行的概率如公式1.其中，OC代表具有r，s条件的功能模块在服务端或者终端执行的概率，cl代表功能模块所有可能的执行位置，在这里只用考虑在终端或服务端执行2种情况;ri代表功能模块的基本信息;sj代表终端状态信息s;而L、M分别表示，L个功能模块的基本信息及M个终端状态信息.终端首次接入应用时，服务端会根据终端此时的状态计算出适合于此终端的应用功能模块部署方案，并将此方案传输到终端，终端会根据此部署方案来对应用功能模块进行部署.

预测模型的更新是一个机器学习的过程，预测模型包括每个功能模块在在不同位置运行的概率数据，服务端在首次运行时需要事先定义初始的预测模型，初始的预测模型通过人为设置每个应用模块在客户端和服务端运行的概率表，然后通过应用上传的数据进行更新，应用运营开始的一段时间，预测模型可能会更新的比较频繁，但随着应用运营的时间增长，预测模型会逐步稳定下来.预测模型是提供给所有终端进行部署方案的依据.少量终端运行时上传的信息并不会对预测模型造成很大影响，只有大量终端运行时数据呈现出同样变化趋势(如大量终端上传的数据表明某应用模块在移动设备上运行时间过长)时才会对预测模型造成影响，例如有超过30%的终端上传的数据表明某应用模块在移动设备上运行时间长于一定值时，就会更新预测模型中概率表的数据.

3 应用原型及测试

我们搭建了一个移动应用框架来模拟现有移动互联网应用场景以及实现应用模块的跨平台运行，框架分为前后端2部分.前端基于Android平台实现，后台使用J2EE框架搭建服务器，应用模块跨平台运行方案例如 Rellermeyer 等的 R － OSGi［13－14］，Houacine等［15］的 MCC － OSGi，我们最后采用了改进的R－OSGi实现，一方面R－OSGi较为成熟稳定，开源支持也比较好.在应用中每个模块均由一个R－OSGi Bundle构成，不同的Bundle可以在手机中运行也可以在服务器上运行，对应用模型提供了良好的支撑.图4是实验终端和服务端系统框架图.

位于终端的Monitor负责监控终端状态以及外界情况变化;客户端的R－OSGi框架负责运行本地Bundle或通过Bundleproxy接口调用服务端的Bundle.应用服务器采用J2EE架构，并包含了核心模块Static Partitioner、Statistic、Application Manager 及Service Manager模块;Static Partitioner模块负责使用贝叶斯算法计算出符合终端当前时刻状态的应用部署方案;Statistic模块搜集每个终端接入应用的状态用于更新贝叶斯网络;Application Manager负责对不同的应用进行管理;Service Manager负责对应用中的不同服务进行管理.

为了验证应用部署策略中的各项理论，我们开发了一套全景人脸识别应用进行测试.该应用包含多个方便移植的功能模块，分别是:图片拼接、图片预处理以及人脸识别模块，每个既可以在手机端运行，也可以在服务端运行.应用需要在手机上通过水平方向旋转拍摄3张照片，然后使将3张照片拼接成为一个全景照片，之后进行图像预处理如色彩均衡和肤色分隔，最后进行人脸识别.这3个功能模块的实现都来自于与OpenCV库，OpenCV的开源性质使得不同的功能模块可以方便移植到不同的平台上，是应用模块可以部署在客户端和服务器的前提条件，应用在运行的时候会根据不同的状况选择每个应用模块执行的位置，从而对应用的执行时间以及效率带来不同的影响.为了使测试结果更具有说服力，我们对后台的部署算法进行了改进，调整了客户端不同状态在贝叶斯网络进行概率计算时的权重，这会影响到最终的预测模型.我们分为2组共5种情况对应用进行了测试，表1是测试结果，我们将所有模块都在终端运行的状态作为对比参考，在这种情况下，整个应用完整运行下来大概需要30 s左右.

我们首先对Wifi/4G网络状况下的应用进行了2种不同倾向性的测试，一种是性能优先，即应用运行时间最少，在这种情况下，预测模型将全部模块部署到服务端运行，耗时约17 s左右，各个模块在服务短端运行的时间很快，时间主要消耗在将初始图片传输至服务端以及服务端将识别的结果传回终端这个过程;而在能耗优先测试中，部署算法将图片拼接和图片预处理置于终端运行，将人脸识别模块置于服务端运行，因为4G网络传输带来的电量消耗较大，而预处理后的图片体积较小，利于传输，这种情况下程序运行时间约28 s.

在2G网络下，由于网络传输速度很慢，所以在性能优先的前提下，部署算法直接将所有模块都部署到终端运行;在节约能耗优先的测试中，部署算法倾向于将所有的模块都部署到服务端运行，因为2G环境下，网络传输的能耗较低，但是带来的问题就是大量是时间被消耗在网络数据传输的过程中，这种情况下程序的运行时间将近60 s.不同应用部署方案测试结果如表1所示.

表1 不同应用部署方案测试结果 s

可以看出，对应用进行恰当的模块划分并进行合理的部署可以有效提高应用运行的效率，另一方面测试的结果也验证了部署算法在不同倾向性的前提下对应用的确起到了优化作用.

4 结语

在以往移动互联网应用部署研究的基础上，基于目前移动应用复杂性、实时性、多样性的发展趋势针对应用模型及应用部署算法几个方面进行了研究:首先通过抽象服务模型的概念，简化了应用拓扑结构，降低应用复杂度，解决了以往应用模型用于复杂应用时导致应用部署方案计算执行效率低的问题;其次基于应用模型或服务模型结合贝叶斯网的分类算法使得在服务端执行的应用部署方案计算较以往的算法更加高效.

应用模块的部署是一个复杂的问题，在本文测试中的应用比较简单，模块数量少，且是顺序执行的流程，不存在复用的问题，也不存在终端和服务器多次数据交互问题，所以测试结果较为理想;但是很多应用的功能模块数量多，应用模型拓扑结构复杂，在这种情况下算法是否能够取得很好的效果是我们将来的研究方向.

［1］工业和信息化部电信研究院.云计算白皮书［EB/OL］.(2014 －5 －12)［http://www.catr.cn/xwdt/kydt/201405/t20140512_1017555.htm］

［2］SATYANARAYANAN M.Mobile computing:the next decade［J］.ACM SIGMOBILE Mobile Computing and Communications Review，2011，15(2):2－10.

［3］ARMBRUST M，FOX A，GRIFFITH R，et al.A view of cloud computing［J］.Communications of the ACM，2010，53(4):50－58.

［4］KUMAR K，LU Y H.Cloud computing for mobile users:Can off loading computation save energy［J］.Computer，2010，43(4):51－56.

［5］徐光侠，陈蜀宇.面向移动云计算弹性应用的安全模型［J］.计算机应用，2011，31(4):952－955.

［6］GIURGIU I，RIVA O，JURIC D，et al.Calling the cloud:enabling mobile phones as interfaces to cloud applications［M］//Middleware 2009.Springer Berlin Heidelberg，2009:83－102.

［7］CHUN B G，IHM S，MANIATIS P，et al.Clonecloud:elastic execution between mobile device and cloud［C］//Proceedings of the sixth conference on computer systems.ACM，2011:301－314.

［8］ZHANG X，JEONG S，KUNJITHAPATHAM A，et al.Towards an elastic application model for augmenting computing capabilities of mobile platforms［M］//Mobile wireless middleware，operating systems，and applications.Springer Berlin Heidelberg，2010:161－174.

［9］OU S，YANG K，ZHANG J.An effective offloading middleware for pervasive services on mobile devices［J］.Pervasive and Mobile Computing，2007，3(4):362－385.

［10］MICHAEL R G，DAVID S J.Computers and intractability:a guide to the theory of NP － completeness［J］.WH Freeman ＆ Co，San Francisco，1979.

［11］KARYPIS G，KUMAR V.A fast and high quality multilevel scheme for partitioning irregular graphs［J］.SIAM Journal on scientific Computing，1998，20(1):359－392.

［12］KARYPIS G，KUMAR V.Parallel multilevel series k－way partitioning scheme for irregular graphs［J］.Siam Review，1999，41(2):278－300.

［13］RELLERMEYER J S，ALONSO G，ROSCOE T.R －OSGi:distributed applications through software modularization［C］//Proceedings of the ACM/IFIP/USENIX 2007 International Conference on Middleware.New York:Springer－Verlag，2007:1 －20.

［14］RELLERMEYER J S，RIVA O，ALONSO G.AlfredO:an architecture for flexible interaction with electronic devices［C］//Proceedings of the 9th ACM/IFIP/USENIX International Conference on Middleware.New York:Springer－Verlag，2008:22 －41.

［15］HOUACINE F，BOUZEFRANE S，LI L，et al.Mcc － osgi:An osgi－ based mobile cloud service model［C］//Autonomous Decentralized Systems(ISADS)，2013 IEEE Eleventh International Symposium on.IEEE，2013:1－8.