物联网环境下QoS驱动的服务组合能量优化研究

付 佳，李爱萍，段利国，王舒漫，赵菊敏

(太原理工大学 信息与计算机学院，太原 030000)

E-mail：tyutli@163.com

1 引 言

随着新一代信息技术的发展，物联网成为继计算机、互联网之后信息发展的又一次变革[1]，面对物联网设备及环境都具有动态变化的特点[2]，在将物联网设备根据其功能封装为服务的同时[3，4]，如何实现物联网服务的动态组合以达到最优配置是目前的主要挑战之一.

2018物联网白皮书指出，据IDC数据统计，到2022年，将有超过500亿的终端与设备联网，形成一个高密度的物联网环境[5].这将导致服务组合中候选服务的数量规模宏大.可能存在许多功能相同或相似但非功能属性QoS(Quality of Service)不同的原子服务，所以物联网环境下QoS的优选仍是主要的研究方向之一.

当前，大量文献研究主要基于QoS进行物联网环境下的服务选择[6]，然而，在实际应用中，物联网服务的提供受到周围环境的影响和相关的制约因素较多[7]，导致物联网服务是高度资源受限服务，随着服务类别及数量的增加，选择服务时候选服务所消耗的能量也使得服务组合中的总体能耗随之增长.因此，不同于传统的web服务组合只进行最大化整体的QoS单元的策略，物联网环境下的服务组合，旨在能量消耗和QoS之间寻找平衡以延长网络生存周期.

2 相关工作

针对上述挑战，国内外已经有许多研究人员对物联网环境下的服务组合问题进行了深入研究.Zhou等人[8，9]提出了一种基于能源效率的无线传感器网络智能对象服务发现链和选择方法，该方法采用多目标遗传算法优化，根据传感器设备的功能和适合度对传感器设备进行分类，选择最优的组合服务.在此基础上，Sun等人[10]提出利用遗传算法、蚁群算法、粒子群算法对服务类链进行实例化.以上方法对网络的能耗进行了详细的考量，但是没有考虑到在实际应用中，由于规模宏大的原子服务数量，可能存在很多功能相同或者功能相似的服务，所以物联网的服务组合方法必须同时考虑组合对象的QoS属性值和能源效率.

杨臻等人[11]提出一种基于功能价值择优的信息服务组合方法，结合物联网中数据信息与地理位置密切相关、设备资源受限的特点，将剩余能量考虑为QoS的一个属性值，建立物联网QoS模型，进行加权计算.但是，该方法没有单独评估在动态配置过程中能量消耗对海量服务的影响.

Tong等人[12]将服务能量引入到无线传感器网络的工作流管理中，给出了服务能量的计算方法，并对传统的QoS模型进行了扩展，采用QoS约束分解的方法，通过同时考虑QoS和服务能量，将工作流的全局质量约束分解为原子服务的一组局部质量约束，实现高效的本地服务选择，提出了一种动态工作流适应机制.Alsaryrah等人[13]将物联网服务组合的QoS水平与消耗能量之间的最优平衡问题简化为双目标最短路径优化问题，并采用脉冲算法求解.上述研究只简单考虑了QoS水平和能源效率问题，没有针对物联网服务组合动态配置中不同时期对QoS和能源的不同要求进行衡量.

综上所述，针对物联网环境下原子服务数量宏大、设备资源高度受限、服务组合过程动态变化的特点，本文提出一种改进的自适应方法，综合考虑QoS属性值和能源效率，解决服务组合过程中对能耗的不同要求，构建不同的目标函数；结合物联网数据信息与地理位置密切相关的特点，利用位置信息进行局部优选，缩小候选服务范围；最后利用多目标优化算法在可行服务组合空间中全局寻优.

3 能量优化建模

3.1 概念定义

定义1.(物联网服务)：一个服务Service是一个三元组Service=(name，desc，QoS)，其中：

1.name是服务名称；

2.desc是服务的语义描述；

3.QoS={ QoS1，QoS2…QoSn}是服务的服务质量属性值集合.

定义2.(QoS)：服务质量QoS是反映服务性能的指标，是服务组合的主要依据，2003年，W3C提出了13种可能通用的QoS指标[14]，截止到目前为止，已经提出的QoS属性指标有30余种[15].结合物联网的特点，物联网环境下的服务需要考虑每个设备的动态变化特性以及应用环境，所以本文取用代价、响应时间、可用性和可靠性四种属性构建QoS模型：QoSij(S)=(Cost，Response Time，Availability，Reli-ability).

1.Cost表示响应一次服务，用户需支付的成本花销，由服务提供商给出；

2.Response Time表示用户请求服务和用户接收回答的时间间隔；

3.Availability表示一个服务在一定时间间隔可访问的时间比；

4.Reliability表示一个服务正确和稳定的行为能力.

定义3.(服务请求)：服务请求r是一个三元组r=(I，O，w)，其中：

1.I是用户能够提供的输入集合；

2.O是用户期待得到的输出集合；

3.0

3.2 能量模型

在本研究中，整个网络生存周期内主要考虑的能量消耗包括环境感知、发送数据和接收数据的消耗，本研究中的能量消耗计算模型采用一阶无线电模型[16]，表1表示的是该模型中各参数的含义.

表1 能量模型参数含义Table 1 Meaning of the energy model parameters

PSense表示的是节点环境感知消耗的能量，PTx和PRx表示的是将一个b比特的数据包传送r的距离的过程中的传输耗能和接收耗能，公式如下所示：

PSense=α1b

(1)

PTx=(β1+β2rn)b

(2)

PRx=γ1b

(3)

n为传播衰减系数，数值范围为2-5，n的取值取决于设备的环境，假设在当前物联网环境下，设备在传输数据包时是无障碍物的，将n的值定为2[17].根据一阶无线电模型，一些典型的参数值如下公式所示：

α1=60*10-9J/bit

(4)

β1=45*10-9J/bit

(5)

β2=10*10-12J/bit/m2

(6)

γ1=135*10-9J/bit

(7)

4 物联网服务组合流程

在基于用户需求QoS限制的物联网服务组合应主要从局部、全局两个阶段上考虑.局部上，引入语义网的相关技术，实现QoS的语义化；全局上，计算QoS的属性值对服务进行选择.

物联网服务组合过程主要包括用户需求分析、服务发现、服务匹配、服务选择和服务组合五个阶段，处理流程如图1所示.

4.1 服务匹配

通过需求分解单元将用户需求分解为功能性需求和非功能性需求，根据功能性需求，利用语义相似度计算方法，从服务库中选取符合要求的候选服务集[18，19].

图1 用户请求处理框图Fig.1 Processing block diagram of the user′s request

为提高求解效率，利用每个服务的位置信息，采用局部优选方法，从候选服务集中，为每个抽象服务优选出优秀候选服务集.

4.2 服务选择

针对优秀候选服务集中服务的选择，在全局最优策略中，不能只考虑当前功能环节的QoS和能量计算，需要考虑各个功能节点聚合后的QoS和能量评价值，使组合方案整体的QoS和能量满足限制条件.而具体的QoS的聚合计算和服务组合的执行路径有着密不可分的关系，一般存在四种基本结构，即并行结构、串行结构、分支结构和循环结构[19]，如图2所示.

图2 四种基本工作流Fig.2 Four basic workflows

根据不同QoS属性的特点，给出每个QoS属性在四种工作流下的不同计算方法，如表2所示.

表2 四种工作流下QoS计算方法Table 2 QoS calculation methods under four kinds of workflows

4.3 服务组合实例化

4.3.1 服务组合目标函数

1.最小化目标

f1=Econsumption

(8)

EConsumption=PSense+PTx+PRx

(9)

2.最大化目标

f2=QoS′i,j(S)

(10)

(11)

3.目标函数

(12)

其中，w1和 w2都是权重因子，均为大于0的正数，分别表示f1和f2所占比的重要程度，并且w1+ w2=1.在本文中，考虑网络负载均衡的要求，采用如下自适应方法自动地调节权重因子的值：

(13)

其中，Emax为节点能量的最大值，Eres为节点能量的剩余值，Eave为节点能量的平均值，0≤k1,k2≤1为常数.

4.3.2 服务组合优化方法

启发式算法可以有效解决大规模问题及NP难问题[20]，因此在本文研究过程中引入了遗传算法和粒子群算法，其步骤如下：

1.遗传算法

遗传算法是一种通过模拟自然进化过程寻找优化解的算法，它包括：选择、交叉、变异.在本文中，基因表示为物联网服务，染色体表示为不同的服务组合，染色体的适应度反映了群体个体的适应度.

算法1.遗传算法

输入：

MAX：最大迭代次数

N：初始种群中染色体的数量

输出：一条相对优化的染色体序列

1.while 迭代次数

2.for i

3.采用轮盘赌选择法选择种群中的染色体，将其加入到下一代种群中，其中具有较大适应度函数值的个体更容易被选择

4.采用单点交叉方法进化下一代染色体

5.采用变异算子进化下一代染色体

6.end for

7.基于适应度将子代插入到新种群中

8.end while

算法1是遗传算法的具体流程，在产生初始种群后，计算其适应度函数值，采用轮盘赌选择法选择当前种群中的染色体，并加入到下一代种群中(第3行).采用单点交叉和变异(第4、5行)，对种群中的染色体进化处理.基于适应度函数值将进化后的个体插入到下一代种群中(第7行).不断重复上述过程，直到找到最优染色体或达到最大迭代次数时循环终止.

2.粒子群算法

粒子群算法是受鸟群觅食行为启发的一种优化算法，粒子代表的是不同的服务组合.在该算法的每一次迭代中，粒子通过两个极值进行更新：1)粒子局部最优解pBest；2)目前整个种群中全局最优解gBest.粒子更新d维速度和位置时遵循如下公式：

popv(i，:)=w*popv(i，:)+c1*rand*(pBest(i，:)-
popx(i，:))+c2*rand*(gBest-popx(i，:))

(14)

popx(i，:)=popx(i，:)+popv(i，:)

(15)

其中，w叫惯性权重，c1、c2为学习因子popv(i，：)为粒子的当前速度.

算法2.粒子群算法

输入：

MAXGEN：最大迭代次数

M：初始种群中粒子的数量

输出：一条相对优化的粒子序列

1.for i

2.计算每个粒子的适应度，并初始化个体最优解pBest和整体最优解gBest

3.end for

4.while 迭代次数

5.for i

6.利用公式(14)、公式(15)更新个体的位置和速度

7.计算目标函数值

8.更新pBest和gBest

9.end for

10.找到最优解粒子

11.end while

算法2是粒子群算法的具体流程，在产生初始种群后，计算每个粒子的适应度，并对个体最优解和整体最优解进行初始化(第2行).根据公式14和公式15更新粒子的速度和位置(第6行)，计算目标函数值并更新pBest和gBest.不断重复上述过程直到达到最大迭代次数时循环终止.

5 实验及仿真结果

5.1 实验仿真

实验模拟500m×700m的网络区域中的空气污染环境感知，其中部署了PM2.5，PM10，CO，SO2，O3，NO2六个服务类共1200个传感器节点，采用随机分布方式，获取每个节点的地理位置值，图3表示的是PM2.5的节点部署位置.

假设每个节点上只封装一个服务.在本次实验中，我们设置每个节点的初始能量为0.01J，为求取某一地点的空气污染程度，模拟工作流如图4所示，实验采用Al-Masri E等人[21]提供的数据集，如图5所示，设定每个节点的服务质量属性值，通过Matlab平台来验证本文算法的可行性和有效性.

图3 PM2.5节点部署情况Fig.3 PM2.5 node deployment

图4 模拟工作流Fig.4 Simulation workflow

图5 数据集Fig.5 Data set

5.2 性能参数

1.网络生命周期

网络生命周期定义为从整个网络开始响应用户请求到任一用户请求无法响应为止.根据节点的最小剩余能量判断网络的生命周期，网络中节点的最小剩余能量越充足，网络生命周期越长.

2.剩余能量方差

根据整个网络中节点的剩余能量方差大小，判断网络的负载均衡情况.方差值越小，说明该网络中节点的使用越平均.

5.3 实验结果

首先，将本文提出的自适应方法控制目标函数的方法在遗传算法和粒子群算法下与只考虑能耗的目标函数和只考虑QoS属性值的目标函数的方法分别执行30次后进行比较，如图6、图7所示.

从图6、图7中可以看出，利用遗传算法和粒子群算法进行服务组合实例化时，本文提出的方法QoS属性值变化接近于只考虑QoS性能的目标函数方法下属性值的变化，能耗变化接近于只考虑能耗的目标函数方法下能耗的变化.这说明本文方法在保证低能耗的同时，也能保证QoS属性值的优选.

图6 本文方法与只考虑能耗的目标函数方法分别执行30次能量消耗的变化Fig.6 Energy consumption value for the method of this paper and the objective function method considering onlyenergy consumption when the algorithms are executed in 30 contiguous time slots

图7 本文方法与只考虑QoS值的目标函数方法分别执行30次能量消耗的变化Fig.7 Energy consumption value for the method of this paper and the objective function method considering onlyQoS value when the algorithms are executed in 30 contiguous time slots

其次，将本文提出的自适应控制目标函数的方法在遗传算法和粒子群算法下与固定目标函数的方法进行比较，如图8所示.

图8 本文方法与固定目标函数的方法在整个网络生命周期中剩余能量方差的变化Fig.8 Variance of the residual energy of the methods proposed in this study and the methods offixed objective functions throughout the network life cycle

从图8(a)中可以看出，利用遗传算法进行服务组合实例化时，在整个网络生命周期中，固定目标函数的方法可以执行1352次服务请求，本文提出的自适应控制目标函数的方法可以执行1491次服务请求.从图8(b)中可以看出，利用粒子群算法进行服务组合实例化时，在整个网络生命周期中，固定目标函数的方法可以执行1212次服务请求，本文提出的自适应控制目标函数的方法可以执行1309次服务请求.在图8中，本文的方法和固定目标函数的方法方差变化基本一致，并且本文的方法的方差比固定目标函数的方法的方差小.说明改进的算法能更好维持QoS和能耗的平衡，进而延长网络生存周期.

再将本文与参考文献[11]Yang等人提出的方法和参考文献[13]Alsaryrah等人提出的方法进行对比，如图9所示.

图9 本文方法与参考文献[11，13]在整个网络生命周期中剩余能量方差的变化Fig.9 Variance of the residual energy of the methodsproposed in this study and the method proposed inreferences[11，13] throughout the network life cycle

从图9中可以看出，在整个网络生命周期中，本文提出的自适应控制目标函数的方法可以执行1491次服务请求，Yang等人的方法可以执行1295次服务请求，Alsaryrah等人的方法可以执行1346次服务请求.三种方法的方差变化基本一致，并且本文方法的方差小于其他两种方法的方差，随着服务请求次数的增加，本文方法的方差与其他两种方法的方差差距逐渐明显，说明改进的算法能更好的避免某一节点的过度使用，进而延长网络生命周期.

6 总 结

物联网环境下服务组合要求兼顾服务的时空约束条件、功能约束条件和能量约束条件，以及每个智能设备的地理位置、应用环境、网络延迟和剩余能量等因素，以确保网络中的设备能量负载均衡.本文基于网络生命周期不同阶段对节点能耗的不同要求，提出一种自适应方法来动态地构建目标函数，实验结果表明，本文的算法提供了QoS属性值和能源效率更好的平衡，避免了单个节点的过度消耗，延长了整个网络生存周期.