基于服务功能价值的物联网信息服务组合

杨 臻，李德识，2

（1.武汉大学 电子信息学院，湖北 武汉430070；2.武汉大学 深圳研究院，广东 深圳518000）

0 引 言

物联网信息服务主要为用户提供来自RFID 标签、传感器等设备的感知数据［1］。随着面向服务的体系结构思想（service－oriented architecture，SOA）引入物联网［2］，每一个感知设备的功能都可以作为服务被其它物理实体发现和调用。

为满足复杂的用户需求，需要将位置信息、感知信息不同的多个设备的数据信息进行组合。目前服务组合的研究多基于互联网，侧重验证服务组合的可行性和逻辑性［3］，而物联网信息服务旨在为用户提供感知信息，各感知设备之间相互独立，无严格的逻辑前驱、后继关系，侧重服务体验最优化。互联网以人工方式产生语音、文本、多媒体文件等服务数据，QoS性能主要包括服务可靠性、可用性、信誉度等［4］，而物联网主要处理电子标签、传感器等设备生成的数据，服务性能还需考虑感知设备的地理位置信息。因此研究物联网环境下的信息服务组合十分必要。

Li Kun提出了基于上下文的服务组合方法［5］，利用上下文精简候选服务集，再选择各功能属类下QoS评分最优的服务进行组合，这种组合方式缺乏全局约束，是局部意义的最优；Jin Liu 等提出搜索全局QoS 最优的组合方案［6］，但未体现不同功能信息对用户的价值差异；Xinming Li等提出从空间、时间与功能相似性匹配的角度，准确地衡量候选服务与用户需求的匹配程度，将匹配度最高的服务组合定义为最优方案［7］，但该方法未涉及服务组合的QoS性能。

文章提出了一个物联网QoS模型，定义了服务的功能信息对用户的价值，将其作为评价服务的用户偏好，应用改进的遗传算法搜索最佳组合方案，能筛选出更符合用户需求的感知数据。

1 服务组合流程

信息服务组合应考虑从局部、全局上两阶段择优。局部上，将初始候选服务集按功能分簇。为了提高服务组合效率，可评比同一功能属类下不同服务的QoS性能，选取QoS性能较好的k个服务作为该功能属类下的最终候选服务。在最终候选服务集中，任选多个功能不同的信息服务进行组合，即可构成一个服务组合方案。全局上，将服务组合的择优问题，转化为给定约束条件下求解目标函数最优值的优化问题，利用改进的遗传算法全局寻优，获得QoS性能、功能需求匹配程度最佳的服务组合。

物联网信息服务的组合过程主要包括需求分析、服务发现、单个服务选择、服务组合选择4个阶段。服务组合寻优流程如图1所示。

图1 用户请求处理流程

（1）分析用户需求。分析用户需求描述文档，能获得目标服务的功能需求与非功能需求，功能需求由功能关键词集合表述；非功能信息包括QoS属性值，以及用户对QoS各个属性的偏好程度。统计各功能关键词在Google知识库中的索引数目，定量评价该功能对用户的价值。

（2）服务发现。在用户指定的信息获取地为中心的一定地域范围内，搜索能满足各子功能需求的原子信息服务。多个功能不同、位置信息不同的感知设备，构成初始候选服务集合。

（3）单个服务评分。根据功能信息将候选服务分簇，基于多属性决策对同一功能属类下的初始候选服务子集进行细粒度个性化评分，择优选择评分排名前k个服务作为最终候选服务，为组合服务的选择打下基础。

（4）服务组合择优。采用全局优化算法，搜索QoS性能与功能信息更满足用户需求的组合方案，为用户提供相应感知数据。

2 服务组合匹配

用户需求可分为功能需求和非功能需求。功能需求表征用户希望获得何种感知数据，非功能需求表征用户对服务性能的需求，是对功能需求的个性化补充。功能需求可能是简单的原子需求，也可能是复杂需求。原子需求定义为构成服务需求的最小单元，不可细分，复杂需求由多个原子需求组合而成。在基于SOA 的物联网中，信息服务往往是功能细化的原子服务，但用户需求往往是粗粒度的复杂需求，为了充分利用物联网服务资源，更好地满足用户需求，需要对各功能细化的原子服务进行组合。

自顶而下［8，9］组合匹配是一种服务自动组合方式，原理是将复杂的功能需求分解为多个功能语义相关的子功能需求，通过对子需求的共同满足来实现复杂需求的满足。这种组合方法以单服务的本体语义匹配为基础，实现简单，能很好地解决子需求的服务匹配问题，但是未充分利用已发布的服务，组合灵活性受限。自底而上［10，11］组合匹配则是根据用户需求，在服务库中选择多个原子服务自由组合，判断组合与用户需求的功能匹配度。这种组合方法充分利用了已发布的服务资源，非常适合服务挖掘，但由于物联网服务资源丰富，组合方案搜索空间庞大，不仅增加了组合匹配实现的难度，还不能保证搜索效率。本文结合以上两种方法的优势进行需求分析与服务匹配。

在需求分析方面，对用户提出的复杂功能需求，采用自顶而下思想进行需求分解，得到多个较粗粒度的子功能需求，将组合匹配转变成对各子需求的服务发现、匹配，能筛选掉服务库中一部分不满足功能需求的服务，减小搜索范围。

在服务匹配方面，可以牺牲一部分语义匹配精度，换取服务挖掘的能力。因为物联网感知信息多涉及细粒度的专业概念，而用户描述可能是大语义范围的语言描述，根据本体库计算得到的语义相似度，能反映候选服务功能与用户描述的概念之间的语义距离，但不能完全反映该服务的功能对用户的重要性程度。可在服务数据库中，搜索服务功能描述与用户功能需求满足一定语义相似度的服务，这些服务的功能构成服务组合的功能关键词集，权衡各个服务的功能对用户的价值，用以衡量候选服务对用户的重要性。考虑到关键词在Google知识库中的索引数目一定程度上能反映当前社会对该关键词的关注程度，索引越多反映该功能信息对用户的价值越大，文中统计各功能关键词在Google知识库中的索引数目，定量地表征各服务功能的相对重要性。

例如用户输入的功能需求为 “空气污染”，在服务库中搜索与该概念语义相关的服务，获得服务组合关键词集为CO2、SO2、PM2.5、CO、CFCs、碳 氢 化 合 物、PM10、NO2。在Google中分别将以上8个关键词连同与 “空气污染”一同搜索，获得索引数目约为：v ［8］＝｛9，8，42，6，4，4，5，7｝ （单位：十万个），用无量纲数值表征相应的功能价值，各个功能之间的相对重要性就能明确地区分开来。

3 物联网服务QoS建模与评价

随着物联网的发展，各行业应用需求推动各种类型的传感器节点广泛应用。每个传感器能提供某一特定功能的感知数据，表示为原子信息服务。大量的物联网信息服务功能相同或相似，但服务QoS不同，因此服务组合需要考虑QoS性能的优劣。

QoS概念源于通信网络，主要描述数据传输中的质量特性，关键指标通常有代价、响应时间、信誉度等，但物联网的特点决定了物联网信息服务还需考虑实体设备的资源有限性、网络环境动态性及其物理语境与应用场景。结合以上分析，可将物联网信息服务的QoS关键指标建模为五元组：代价、响应时间、可靠性、地理距离与剩余能量，各指标的定义和量化方法描述如下。

代价：用户发起一次感知信息查询需要支付给服务提供商的费用。

响应时间：从用户提交请求到接受到服务响应之间的时间间隔，包括用户请求处理时间和感知设备的采样、处理、传输时延，常以一段时间内的历史响应时间的平均值衡量。

可靠性：物联网感知设备的软硬件环境、通信网络环境会影响信息服务的成功率，一定时间内为用户提供感知数据的成功率能衡量信息服务的可靠性。

地理距离：感知设备的数据信息与设备所在的地理环境密切相关。若用户指定的感知地附近已部署了感知设备，感知数据必然精准，但往往感知设备与用户指定的感知地之间存在距离差，可能导致信息数据误差。测定每个候选服务的设备地理位置与用户指定感知地之间的距离差，将其作为物理距离参数值。距离差越小，代表感知数据更贴近用户需求。

剩余能量：与互联网服务设备不同，物联网底层传感设备能量受限。传感器的可持续服务时间与剩余能量成正比。剩余能量低的传感器在一段时间后电池能量耗尽，会导致服务失效，无法继续提供感知数据。将每个传感器的剩余能量纳入评价标准，优先将剩余服务时间长的传感器加入组合，能增加服务组合的可重用性。

服务组合的QoS平均性能受组合内各原子服务QoS性能的影响。在本文的物联网QoS模型中，可靠性、剩余能量是效益型属性，而代价、响应时间、地理距离是成本型属性。不同属性量纲不同、数量级不同，因此需要对各个属性值进行标准化。采用极差变换法式 （1）、式 （2），能分别将成本型属性与效益型属性标准化，从而消除量纲与数量级的影响［12］。式 （1）、式 （2）中i表示服务编号，j表示服务的第j 种QoS属性，qij表示第i 个服务、第j种属性的值，maxqj与minqj分别表示所有服务中第j 种QoS属性的最大、最小值，sij表示第i个服务、第j种属性的归一化评分。

加权算术平均式 （3）能计算各候选服务的综合评分，这种计算方法允许数据之间线性补偿，强调整体数据影响，Qij值越大，表示服务的QoS性能越佳。ωi是用户对各属性相对重要性的偏好估计，可采用熵值法等主、客观赋权方法测定［12］。为了提高服务组合的搜索效率，在每个功能属类下，择优选取Qij值排名前k 个服务，作为最终候选服务集

4 服务组合优化求解

根据用户需求描述文档能获得服务组合的功能关键词集，表示如图2所示F1，F2，…，Fm。依据QoS评分精简初始候选服务集后，每个功能属类下存在多个候选服务实例BSij（i＝1，2，...m，j＝1，2，…，k）。由于各查询请求之间不存在严格的前驱、后继逻辑关系，只要符合功能需求、满足总代价约束的任意服务实例都可加入组合，因此存在大量的备选方案。

图2 服务组合

组合寻优求解方法有穷举搜索、贪婪算法、回溯法、动态规划法、遗传算法等。穷举搜索一定能发现最优组合，但搜索时间及空间代价都很大；贪婪算法计算复杂度低，但不能保证得到最优解；回溯法与动态规划算法的求解耗时会根据问题规模呈幂级数增加；遗传算法不需要与应用背景相关的启发式知识，搜索代价相对较小，只需要目标函数和相应适应值函数即可高效、健壮地求解大规模组合问题，被广泛用于求解最优化问题。

基于以上分析，文章采用遗传算法思想全局优化。传统的遗传算法通过交叉、变异操作不断产生新染色体，直到满足迭代次数N ＝Nmax 后算法才停止。历来研究者们更倾向从避免遗传算法过早收敛、保持种群多样性方面改进遗传算法，加大搜索空间。但对于物联网中某些特定的应用场景，用户对物联网信息服务的实时性要求较高，服务组合决策时间对信息服务的感知数据准确性有直接影响，适当加快种群收敛，根据种群收敛状态适时终止迭代，提高最优化求解的效率显得更为重要。采用精英保留策略，并将种群相似度加入算法终止条件有助于解决这个问题。

种群相似度可定义为式 （4），sim（G）为第G 次迭代种群的相似度，SimF（G）是在当前种群中适应度值相同的染色体个数，Gnum 是种群的规模。当种群相似度值在 ［r，1］区间 （相似度阈值r可取0～0.9 之间的数）内时，表示种群中绝大多数的染色体相同，算法已收敛，可终止种群迭代

从用户角度，兼顾QoS性能与功能价值的服务组合才是最好的选择。根据遗传算法的思想，适应度函数与约束条件可定义为式 （5）。将各个待组合的候选服务按功能关键词分簇，实现第i种功能的服务对用户的价值为vi。实现第i种功能的第j 个服务实例的QoS评分值为Qij，耗费代价为cij。bi是标志位，取 “0”表示服务组合中不包含实现第i个功能的服务；取 “j”表示将第i种功能的第j 个服务实例BSij加入组合。 （b1b2b3...bm）组成一个染色实数编码码串，各基因位的取值形象地反应了各功能相应服务实例的选取状态。在满足总代价约束时，功能价值加权的QoS总评分越高，相应的服务组合与用户需求的匹配程度越高

采用改进遗传算法全局寻优，流程如图3 所示。实数编码使遗传算法能灵活地在大候选服务空间中寻优，基于效益贪心策略的可行性检查能修正不可行的组合方案，交叉和变异能维持种群多样性，精英保留策略与种群相似度检查能加快算法收敛。

图3 改进遗传算法流程

算法实现流程可表述为：

（1）随机产生规模为M 的初始种群，采用实数编码随机生成染色体码串，定义式 （4）所示的适应度函数与约束条件。

（2）基于效益贪心策略，检查种群内M 条染色体的合法性。种群迭代的过程中必然会产生部分不满足总代价约束的染色体，在值非0的基因位中，优先选取功能价值最低的位，将服务组合中实现功能Fi的服务用代价更小的服务替代，直至染色体合法。

（3）检查当前迭代次数与种群相似度。当满足最大迭代次数或种群相似度达到阈值时，停止种群迭代，返回当前最优解。

（4）采用赌轮法产生M 条父染色体复制到交配池，进行单点交叉、变异。变异是以一定的概率在染色体中随机选择一个基因位，在取值区间内随机改变bi的值，生成新染色体，保证尽量多的服务组合方案能加入寻优过程。

（5）采用精英保留策略。在父代种群中选取适应度值较大的部分染色体作为精英保留，直接代替子代种群中同比例适应度值小的染色体，共同构成新种群，避免优秀染色体在下一轮迭代的选择、交叉操作中丢失。

重复上述过程直至迭代终止，最终搜索到总价值最大的最优解决方案。

5 实例分析

基于VS2008仿真服务组合的状态，将本文的方法与基于QoS约束的传统服务组合方法进行对比。开发环境为Intel Core 3.3GHz处理器，3.4GB内存，操作系统为Windows XP。遗传算法初始配置为：交叉概率为0.8 （一般为0.4－0.9），变异概率为0.09 （一般为0.01－0.1），父代精英比例20%，最大迭代次数为300，种群相似度阈值为0.8，基于C＋＋编程。

设定服务需求为某地的 “空气污染”信息。假设在感知目的地附近区域共部署了CO2、SO2、PM2.5、CO、CFCs、碳氢化合物、PM10、NO2共24个传感器节点，每个传感器对应一个提供感知信息的候选服务。各服务的代价与QoS评分值在一定范围内随机生成，用二维数组表示，代价为Cost［8］［3］＝ ｛｛3，2，2｝，｛1，5，3｝，｛1，4，2｝，｛1，3，5｝，｛2，4，3｝，｛1，2，3｝，｛1，1，3｝，｛2，2，1｝｝，QoS评分为QoS［8］［3］＝｛｛0.88，0.85，0.81｝，｛0.87，0.84，0.92｝， ｛0.72，0.61，0.88｝， ｛0.88，0.90，0.90｝，｛0.65，0.85，0.98｝，｛0.85，0.80，0.90｝，｛0.90，0.86，0.96｝，｛0.80，0.89，0.99｝｝。在Google知识库中统计8种功能的索引数目，得到功能价值：v ［8］＝ ｛9，8，42，6，4，4，5，7｝。

Qiufen Wang采用与贪心策略相结合、二进制编码的遗传算法，在迭代次数N＝Nmax后停止算法［13］。为了满足服务组合的需要，将遗传算法的编码改变为实数编码，其它策略不变。在候选服务的功能种类规模不同时，比较加速收敛的遗传算法与自然收敛的遗传算法［13］的求解效率。预先设定功能种类个数分别为8，12，16，20，24，28，每种功能都拥有3个候选服务供选择，采用遗传算法独立运行30次，统计组合优化求解的平均耗时，结果如图4所示。实验结果表明，为遗传算法添加精英保留策略与收敛性判定准则后，在可行服务组合方案达428种时，服务组合优化求解都能在12.8ms内完成；而自然收敛的遗传算法［13］求解耗时达31.33 ms，这是因为无论种群是否收敛，算法依然要迭代300次，增加了执行时间。

图4 组合求解耗时比较

将功能价值与QoS相结合的择优策略与仅基于QoS的择优策略［13］作对比，应用相同的遗传算法搜索全局优化解，实验结果见表1。

表1 实验结果对比

若用户能承受的最大服务组合代价为10 （单位：元），在不考虑信息服务之间的功能价值差异时，最优染色体的基因位b1＝0，代表服务组合仅不提供CO2感知信息，但此功能价值对用户的重要性排名第二，明显是用户不希望丢失的信息。而本文应用功能价值与QoS双重标准进行组合匹配，最优染色体的基因位b5＝0，表示服务组合仅不提供CFCs感知信息，此功能对用户的重要性相对最低，与前种方法相比更好地保留了用户最需要的功能信息，同时服务组合的QoS平均性能也相差不大。

实验结果表明，不论是从最优求解结果与用户需求的匹配程度，还是从全局优化求解效率的角度，本文算法能更好地解决物联网信息服务组合求解问题。

6 结束语

物联网信息服务组合可看作兼顾功能需求匹配度、QoS性能、组合决策效率的全局优化问题。基于物联网感知设备资源受限、感知信息与物理环境密切相关的特点，提出从服务质量与服务对用户的价值两方面评价候选服务与用户需求的功能匹配度，结合物联网QoS模型，应用效率提升的遗传算法全局优化。实验结果表明，将功能价值纳入服务评价标准后所得的服务组合更符合用户需求。目前直接采用关键词在Google中的索引数目作为功能价值，简单方便，未来可考虑采用大数据分析方法衡量功能价值，获得更精确的功能价值。

［1］ZHANG Feizhou，YANG Dongkai，CHEN Zhi.An introduction to Internet of things technology ［M］.Beijing：Publishing House of Electronics Industry，2010：25－26 （in Chinese）.［张飞舟，杨东凯，陈智.物联网技术导论 ［M］.北京：电子工业出版社，2010：25－26.］

［2］Guinard D.Interacting with the SOA－based Internet of things：Discovery，query，selection and on－demand provisioning of Web services［J］.IEEE Transactions on Services Computing，2010，3 （3）：223－235.

［3］TIAN Hao，FAN Hong.A semantic rule based method of phased semantic Web service discovery ［J］.Computer Engineering and Design，2012，33 （5）：1806－1810 （in Chinese）.［田浩，樊红.基于语义规则的分阶段语义Web服务发现方法［J］.计算机工程与设计，2012，33 （5）：1806－1810.］

［4］ZHANG Peiyun，HUANG Bo，SUN Yamin.A semantic and QoS－aware based Web service match mechanism ［J］.Computer Research and Development，2010，47 （5）：780－787 （in Chinese）. ［张佩云，黄波，孙亚民.一种基于语义与QoS感知的Web服务匹配机制 ［J］.计算机研究与发展，2010，47 （5）：780－787.］

［5］Li Kun.The research of Web services composition based on context in Internet of things ［J］.IEEE International Conference on Computer Science and Automation Engineering，2012，1：25－27.

［6］Liu Jin，Chen Yuxi，Chen Xu，et al.A cooperative evolution for QoS－driven IoT service composition ［J］.Automatika，2013，54 （4）：438－447.

［7］Li Xinming，Sun Yan.A service mining scheme based on semantic for Internet of things ［J］.Chinese Journal of Electronics，2014，23 （2）：236－242.

［8］WANG Yu，XIANG Chaocan，WANG Meng，et al.Research status and development of semantic Web service discovery ［J］.Application Research of Computers，2013，30 （1）：7－12 （in Chinese）.［王珏，向朝参，王萌，等.语义Web服务发现研究现状与发展 ［J］.计算机应用研究，2013，30 （1）：7－12.］

［9］Tian YH，Su YL，Zhuang XF.Research on service identification methods based on SOA ［C］／／3rd International Conference on Advanced Computer Theory and Engineering，2010：V6－27－V6－31.

［10］Zheng Xiaolin，Lin Zhen，Yang Yanbo，et al.Research on context aware Web service composition based on the fluent caculus ［J］.Advances in Information Sciences and Service Sciences，2011，3 （7）：62－74.

［11］Anne HH Ngu，Michael P Carlson，Hye－young Paik，et al.Semantic－based mashup of composite applications ［J］.IEEE Transactions on Services Computing，2010，3 （1）：2－15.

［12］ZHANG Quan.Complex multiple attribute decision making research ［M］.Shengyang：Northeastern University Press，2008：16－56 （in Chinese）. ［张全.复杂多属性决策研究［M］.沈阳：东北大学出版社，2008：16－56.］

［13］WANG Qiufen，LIANG Daolei.A heuristic genetic algorithm for solving 0－1knapsack problem ［J］.Computer Applications and Software，2013，30 （2）：33－37 （in Chinese）.［王秋芬，梁道雷.一种求解0－1背包问题的启发式遗传算法 ［J］.计算机应用与软件，2013，30 （2）：33－37.］