一种基于图形方法来帮助创建移动网络应用

一种基于图形方法来帮助创建移动网络应用

前言：

作为一种广泛采用的开发方式，混搭集成数据(mashup integrates data)，计算和用户界面元素从多个网络交付(delivered)服务成一个单一的网络应用程序，这是一种很有前途的方法来为移动设备开发应用程序。然而，通过mashup 开发移动web应用面临着2个挑战：一方面：网络提供的服务的日益普及，特别是这些具备了移动特征，比如：LBS,增加了找到合适的服务和服务之间的连接创建情境应用的难度；另一方面：移动计算的收益率（yields）为敏捷（agile）开发和快速迭代 fast iteration，以满足用户不断变化的需求，给开发者施加更多的负担。本文提出了一种基于图形的方法来帮助移动开发人员创建移动网络应用程序。基于此图模型，通过综合不同的推荐模式算法的设计，协助完成混搭，比如寻找丢失的组件，它们之间的连接，或有可能相关的选项。

关键词：Web应用；服务混搭；建议

INTRODUCTION:

移动电话和表格的广泛应用和巨大的成功需要应用程序以适应移动计算环境。由于对发展的易用性，可移植性和更新，移动Web应用程序是最流行的一种趋势。这些移动web应用程序通常由所谓的mashup开发，从多个Web提供的服务为一个单一的Web应用程序集成了数据，计算和用户界面。

一般来说，混搭是由一系列专门实现特定功能的混搭组件来组成。混搭的组件可能会包含数据源比如由RSS/Atom所提供的新闻，功能，这是可以通过web服务或者Web APIs

外部访问。

虽然有一些可利用的混搭编辑器去缓解创建混搭，即 Yahoo。为企业和个人用途的管道和IBM MashupHub，在移动环境中开发网络应用程序总是很有挑战性的。一方面，有巨大潜力的mashup组件和新的随时都在出现，特别是那些配备移动特征像LBS。开发人员可能无法选择合适的应用程序。在另一方面，敏捷开发和快速迭代的移动计算是为了得到满足用户不断变化的需求，而混搭组件之间的关系可能是复杂的。一个单一的mashup组件很可能是由各种其他的混搭组件组成。此外，也通常有许多具有相似功能，但是具有不同的属性的混搭，这使得开发人员很难去构建正确的连接。

为了克服上述挑战，本文提出了一种基于图形的方法，协助创建移动网络应用通过建议有益的混搭建议。为了指定混搭组件和其组成的逻辑，我们描述了一个通用的数据驱动模型。依据这个模型，我们把混搭构件组织成了一个分层图。然后，我们应用了一个斯坦纳树算法（Steiner-tree），有效地检索可能的建议，并与数据合成的多因素排序。

LAYERED GRAPH MODEL（分层图模型）

A. Mashup Component 形式上，C是二元组< IC，OC >，其中：IC是C的输入数据对象集，指定输入数据的约束。IC 实际上也是在接口规范的变量。

B Data Relationship of Components 假设C1和C2两个组件，c2取决于c1如果 Ic2属于Oc1, 这意味着输出C1可以覆

盖输入C2，这样通过C1产生的数据可以用来为C2服务。请注意，我们使用 属于号 来表示在在语义和句法层面上的依赖关系。定义函数 DEP（x，y）= 1如果y取决于x，否则DEP（x，y）= 0。

C. Inheritance Relationship of Components 将组件分为类别这是一种通用的方式。在一类别的组件具有类似的功能，但可能在输入/输出的丰富性上面会有所不同。我们使用类T去表示类别。假设C1和C2是一个类的两个组件，如果C2的接口是C1的接口的超级组，那么C2继承自C1。

D. Components Layered Graph Model（组件分成图模型） 继承关系实际上反映了一个类中的组件层之间的关系，而依赖关系表示不同类别之间的层间的数据流动。因此，可以构造一个组件分层图模型。形式上，假设ti和tj是2个类（i不等于j）,定义分层图Ti和TJ之间的概念：Gij,在Cij = Cti ∪ Ctj and Eij = Ii ∪ Ij ∪ Dij .在这里Ii = {< x, y > |x, y ∈ Cti , inh(y, x) = 1} and Dij = {< x, y > |x ∈ Cti , y ∈ Ctj , dep(x, y) = 1}.边的方向是从x到y。

GRAPH-BASED RECOMMENDATION（基于图推荐）

A. Recommendation for Two Components（推荐2个组件） 我们从最简单的例子开始，最初仅仅有2个组件被选中，x和y。如果在x和y之间有一种依赖关系，例如y依赖于x，（图1_a，依赖关系用实心箭头表示）即：Iy属于Ox,然后根据这种依赖关系x可以直接连接到y。如果x和y直接没有这种依赖的关系，我们

首先研究和x或者y具有继承关系的组件。例如：如果一个组件Z是继承自X，并且被Y依赖（图1_b，继承关系是用虚线箭头表示的），即： O x < O z , I y < O z ，然后Iy可能被Ox部分覆盖。因此，这是可能需要消耗一些成本去连接X和Y。如果我们不区分继承的边缘和依赖的边缘的话，从X到Y的路径，在X和Z之间这个成本是通过反向的箭头以视觉的方式呈现的。在更复杂的情况下，X和Z之间可能具有不直接的继承关系（图1_c）在相应的无向图上，有一条从×到Z的路径。我们应该计算从×到Z的路线上的反向箭头所带来的所有费用。如果既没有发现依赖关系，也没有发现继承关系，我们可以引进一些其他类的组件作为从X到Y的“桥”。图1_d展示的是一个例子，组件v被添加到X和Y之间，这表示了： I y < O v ,I v < O x。如果从X到Y构建联系的时候有多种依赖和继承关系被包含，我们需要计算路径上面的反向继承箭头所带来的所有费用，并给他们排序。

总之，在相应的无向图的路径，分层图G，建议的两个组件是找到从一个到另一个的路径，表示为G~。从×到γ的路径的长度是所有反向边的总和。按其长度按递减顺序排序每一条路径可以产生一个排名推荐列表。

B. Recommendation for General Case（一般情况下的建议）

很容易将上述分析扩展到更一般的案例中，其中初步选择超过2个组件，在相应的无向图G~中，这可以减少连通子图问题。和2个组件的推荐相比，我们应该考虑类的信息。我们定义dep_value(x,y)统一代表连接X和Y的最低成本，在只有这些组件在同一个类的时候。

我们首先考虑的是最好的建议，其成本应该是最低的。根据图论理论[ 3 ]，这个问题可以归结为Steiner树问题。由于Steiner树问题是一个NP完全问题，我们设计了一个简

单的近似算法来计算建议解决方案，通过考虑以下几个方面：

1）在 G ij < C ij ,E ij >中，计算每对预选的顶点的最短长度

2）构造一个新的完整的图 G ‘< V’ ,E’>， V’是给定顶点的集合，各边的值是对应的最短长度

3）在G’中计算最小生成树，然后映射回原始图得到一个近似的Steiner树

考虑建议的成本是高于最好的，但是在所有的子图中是相对小的，一个优化的算法就是构建多个G’ 在第一步检索Steiner树的时候。因此，对于每一个G’,建议可以找到。当建议的数目超过给定的阈值时，我们按照它们的消耗递减的顺序排序。为了得到更多的G’，除了最短的一个以外，我们要计算了更多的路径。