基于改进NSGA-II算法的物联网服务组合优化研究

Research on IoT Service Composition Optimization Based on Improved NSGA-II Algorithm

摘要: 物联网服务组合是促进物联网发展和实现资源增值的一项关键技术。对于单个的物联网服务，其功能有限，若将若干物联网服务进行组合得到功能更加强大的复合服务，则可以提升复合服务的性能。以往的物联网服务组合模型研究多关注时间、成本、质量等等，较少考虑国家的能源消耗要求和物联网平台的用户体验问题以及物联网平台的安全性。原始NSGA-II算法在种群迭代过程中容易出现提前收敛或局部收敛问题。考虑上述情况，本文提出一种新的评价模型，并改进NSGA-II算法，并用改进后的算法求解该模型。最后通过一个物联网服务组合的算例，表明改进的NSGA-II算法求解的帕累托面更加平滑，算法运行时间减少6.216%，证明了模型的有效性，以及改进算法的先进性。

Abstract: Service composition of Internet of things (IoT) is a key technology to promote the development of IoT and realize value-added resources. For a single IoT service, its function is limited. If several IoT services are composed to obtain a more powerful composite service, the performance of the composite service can be improved. Previous IoT service portfolio model studies pay more attention to the time, cost, quality, etc., less consider the national energy consumption requirements and Internet of things platform user experience problems. The original NSGA-II algorithm is prone to premature convergence or local convergence in the process of population iteration. Considering the above situation, this paper proposes a new evaluation model, and improve the elite strategy of pareto solutions sorting genetic algorithm (NSGA-II), and the improved algorithm to solve the model. Finally, an internet of things service composition example shows that the Pareto surface solved by the improved NSGA-II algorithm is smoother, and the running time of the algorithm is reduced by 6.216%, which proves the effectiveness of the model and the advancement of the improved algorithm.

1. 引言

物联网服务组合是指将多种不同类型的物联网服务以及相关资源和功能进行整合和集成，以满足用户需求并创造更高级别的价值 [1] 。这种组合可以包括传感器数据采集、数据分析与挖掘、远程控制、实时监测、自动化决策等多个层面的服务，以实现更复杂、更智能的应用场景 [2] 。

物联网服务组合的关键要素包括：

1) 服务集成：将不同领域、不同类型的物联网服务整合在一起，使它们能够协同工作，实现更全面的功能 [3] 。

2) 自动化：通过自动化技术，使不同的物联网服务能够在特定条件下自动触发、执行或协同工作，从而提高效率和响应速度。

3) 数据交互与共享：不同物联网服务之间需要进行数据的交互和共享，以便实现更准确的分析和决策。

4) 智能决策：基于整合的物联网数据，系统可以进行智能决策，自动调整参数或执行特定任务，以实现更优化的结果 [4] 。

5) 安全性与隐私保护：在物联网服务组合过程中，需要考虑数据安全性和用户隐私保护，防止潜在的安全威胁和风险。

6) 可伸缩性：物联网服务组合需要具备可扩展性，以便在需要时添加新的服务或资源，以适应不断变化的需求。

目前，对于物联网服务组合优化问题，已经具有阶段性的成果。Asghari, Rahmani提出了一种隐私感知的服务组合技术。采用混合进化算法和物联网概念模型优化服务组合过程中的各种安全性(QoS)参数 [5] 。Sefati和Navimipour提出了一种面向物联网服务组合的安全性(QoS)优化方法。他们结合蚁群优化(ACO)算法和隐马尔可夫模型来解决服务组合问题。该方法采用基于微分算子的马尔可夫聚类，并多次应用于网络以识别聚类。这个过程涉及增加簇内的边值，同时减少簇间的边值。对于聚类来说，这些操作更快、更简单、更自然，适合各种应用。安全性的评估是通过蚁群算法来完成的，这有助于找到合适的路径。这种方法的主要重点是实现高可靠性和可用性。然而，能源效率并不是他们工作的主要考虑因素 [6] 。Guzel和Ozdemir提出了一种多目标物联网服务组合框架设计的光纤陀螺仪的物联网环境。这个框架的目的是生成服务组合策略考虑的安全性(QoS)，能源消耗，和公平。将该任务视为一个多目标优化问题，以获得有效的物联网应用组合技术。一个通用的QoS模型开发和集成到框架来处理物联网领域的多样性和不断变化的特征。将应用请求划分为时间窗口，利用定义的优化模型对每个时间窗口进行优化；优化方法侧重于降低能源消耗、最小化相同物联网服务的重复使用、最小化服务水平协议被破坏的数量。测试结果显示了能源消耗和公平目标之间的权衡。在能源消耗目标的驱动下，该架构倾向于优先考虑低能源消耗的物联网服务。然而，这种方法没有考虑可扩展性，这对于可能需要适应越来越多的设备和用户的物联网系统来说是一个至关重要的方面。综上所述，Guzel和Ozdemir提出的面向雾环境的多目标物联网服务组合框架提供了综合考虑QoS、能源消耗和公平性的组合策略。通用QoS模型的使用允许对各种物联网特性的适应性。然而，该框架没有解决可扩展性问题，在物联网设备和用户数量不断增加的场景中，这可能是一个限制 [7] 。Ullah Khan针对高风能集成智能电网的日前调度问题，提出了一种新的需求侧管理(DSM)策略。该策略旨在优化一个三目标问题，最小化运行成本、污染排放和减载成本，同时确保风力机出力与需求之间的协调。该模型采用蒙特卡罗模拟对风能进行预测，以考虑风能的不确定性 [8] 。Ali, Ullah在智能电网中引入需求侧管理(DSM)策略，通过涉及分布式能源资源并考虑不同类型的消费者来优化能源管理。利用多目标风力驱动优化算法对日前调度问题进行求解，优化运行成本、污染排放、弃负荷成本以及风力发电与移动负荷之间的协调 [9] 。以往的服务组合模型研究多关注时间、成本、质量等等，较少考虑物联网平台的能源消耗和用户体验要求。

本文综合考虑物联网服务需求方和物联网平台的利益，针对原始NSGA-Ⅱ算法在种群迭代过程中出现的提前收敛或局部收敛问题，提出了一种新的物联网服务组合数学模型，该模型以任务完成时间、服务响应时间、安全性、云平台能源消耗、用户体验为指标体系，设计了改进的精英保留策略，运用改进的NSGA-Ⅱ算法对该模型进行求解。

2. 物联网服务组合问题描述

假设一个复杂的物联网服务T可以分解为n个子任务，即 $\text{T}=\left\{{\text{ST}}_{\text{1}},{\text{ST}}_{\text{2}},{\text{ST}}_{\text{3}},\cdots ,{\text{ST}}_n{}_{-\text{1}},{\text{ST}}_n\right\}$ 。在物联网平台的资源池中，将几种合适的服务组合在一起，协同完成物联网服务 [10] 。每个物联网子任务对应一个候选服务集，n个子任务对应的候选服务集表示为 ${\text{S}}_{\text{1}},{\text{S}}_{\text{2}},\cdots ,{\text{S}}_n$ 。候选服务集S₁被表示为 ${\text{S}}_{\text{1}}=\left\{{\text{S}}_{\text{1}}{}_{,\text{1}},{\text{S}}_{\text{1}}{}_{,\text{2}},{\text{S}}_{\text{1},\text{3}},\cdots ,{\text{S}}_{\text{1}}{}_{,m-\text{1}},{\text{S}}_{\text{1}}{}_{,m}\right\}$ ，表示候选服务集S₁有m个候选服务。候选服务集S_i被表示为 ${\text{S}}_i=\left\{{\text{S}}_i{}_{,\text{1}},{\text{S}}_i{}_{,\text{2}},{\text{S}}_i{}_{,\text{3}},\cdots ,{\text{S}}_i{}_{,m-\text{1}},{\text{S}}_i{}_{,m}\right\}$ ，表示候选服务集S_i有m个候选服务。根据要求，从每个候选服务集里选出符合要求的服务，被选出的服务协作完成物联网服务T。物联网服务组合示意图如图1。

3. 物联网服务组合数学建模

考虑物联网平台在服务执行过程中的动态性、不稳定性，为方便建立数学优化模型，作出以下假设：1) 物联网服务组合过程中不存在一个物联网资源同时为多个物联网子任务服务的情况；2) 以顺序结构作为物联网服务组合的研究对象。

3.1. 物联网服务需求方约束指标

本发明充分考虑服务需求方的需求和物联网服务运行特点，并结合指标的可量化性，选取任务完成时间、服务响应时间、安全性3个指标，构建服务需求方指标约束体系。

Figure 1. Illustration of IoT service composition

图1. 物联网服务组合示意图

1) 任务完成时间T。服务需求方提交服务请求到取得服务结果所花费的总时间。表达式为

$T={\displaystyle {\sum }_{i=1}^n{t}_i}$

式中，t_i为子任务i对应服务提供方完成子任务时间， $i=1,2,\cdots ,n$ 。

2) 服务响应时间R。服务响应时间是物联网应用的关键性能指标之一，尤其是对于实时性要求较高的应用。优化模型可以尝试最小化服务组合的平均服务响应时间，以确保及时的数据交换和处理。从服务需求方向物联网平台提交任务开始，到获得服务结果的总的服务响应时间R。表达式为

$R={\displaystyle {\sum }_{i=1}^n{r}_i}$

式中，r_i为子任务i对应服务提供方的服务响应时间， $i=1,2,\cdots ,n$ 。

3) 安全性S：物联网系统的安全性对于防止恶意攻击和保护数据的隐私至关重要。优化模型考虑最大化系统的安全性，通过选择合适的服务来降低潜在的安全风险。安全性S表达式为

$S=1-\frac{{\displaystyle {\sum }_{i=1}^n{s}_i}}{n}$

式中，s_i为子任务i的候选服务资源所生产服务的无故障率，取值范围为[0, 1]，1表示没有发生故障， $i=1,2,\cdots ,n$ 。

QOS计算表达式为

$\text{QoS}=W_T\cdot \frac{T}{T_{\max }}+W_R\cdot \frac{R}{R_{\max }}+W_S\cdot \frac{S}{S_{\max }}$

$S_{\max }=1-S_{\min }$

式中：W_T、W_R、W_S分别为任务完成时间、服务响应时间、安全性的权重；T_max、R_max分别为服务需求方所规定的最长时间、最大服务响应时间；S_min为服务需求方须达到的最低安全性。

3.2. 物联网平台约束指标

为了减少环境破坏，发展低能源消耗、低排放的低碳经济，物联网平台运营方考虑国家关于能源消耗的要求，从而会增加对供应商的能源消耗E评估。为防止匹配到过低的服务质量的服务提供方，物联网平台会对服务提供方的用户体验A进行约束。

1) 能源消耗E：物联网设备和服务的能源消耗是一个重要的考虑因素，尤其在能源有限的环境中。优化模型可以尝试最小化整体能源消耗，以提高系统的可持续性。能源消耗E的计算公式为

$E={\displaystyle {\sum }_{i=1}^n{e}_i}$

式中：e_i为子任务i的能源消耗；n为子任务数， $i=1,2,\cdots ,n$ 。

2) 用户体验A：物联网应用的用户体验对于广泛的采用至关重要。优化模型可以考虑最大化用户体验，通过选择适合的服务组合来提供更好的用户感知。物联网服务组合的用户体验A是服务需求方对各个服务提供方的历史打分，取值在0~1之间，数值越高，表示物联网平台服务提供方的服务水平越好。表达式为

$A=\frac{{\displaystyle {\sum }_{i=1}^n{A}_i}}{n}$

式中：A_i为服务需求方对子任务i所对应的服务提供方的用户体验；n为子任务数， $i=1,2,\cdots ,n$ 。

3.3. 优化目标

物联网服务组合的总体目标是服务需求方的QoS最小、物联网平台的能源消耗最低、用户体验最高来完成物联网服务。综合考虑，建立物联网服务组合数学模型：

$\begin{array}{l}F\left(X\right)=\left(\min \text{QoS},\min E,\max A\right);\\ \text{s}.\text{t}.\{\begin{array}{l}T\le T_{\max },\\ R\le R_{\max },\\ S\ge S_{\min },\\ E\le E_{\max },\\ A\ge A_{\min },\end{array}\end{array}$

5个约束分别表示模型中的任务完成时间T不超过服务需求者规定的最长时间T_max，服务响应时间R不超过服务需求者规定的最高服务响应时间R_max，安全性S不低于服务需求者规定的最低安全性S_min，能源消耗E不超过物联网平台运营方要求的物联网服务过程中产生的最大能源消耗E_max，用户体验A不低于物联网平台规定的最低用户体验A_min。

4. NSGA-Ⅱ算法

本文所构建的物联网服务组合模型是一个多目标优化问题，与传统的单目标优化不同，它考虑同时优化多个相互关联的目标。在单目标优化中，我们试图找到一个解决方案，使得单一目标函数达到最优值。然而，在许多实际问题中，存在多个冲突的目标，改善其中一个目标可能会对其他目标产生负面影响。与单目标优化相比，多目标优化需要在解决方案空间中寻找一组解，这些解被称为Pareto解集，也被称为非支配解集(Non-Dominated Set) [11] 。在Pareto解集中，不存在一个解能在所有目标上优于其他解，而是每个解在某些目标上优于其他解，同时在其他目标上可能表现较差。Pareto解集呈现出一个平衡的前沿，代表了不同权衡取舍的解决方案。多目标优化的目标是寻找Pareto解集中的最优解或一组最优解，以实现在多个目标之间取得平衡 [12] 。为了比较不同解决方案，常常使用Pareto支配的概念，一个解支配另一个解意味着在所有目标上至少有一个目标优于另一个解，且至少有一个目标严格优于另一个目标。

本文所选NSGA-II算法 [13] 是由Deb和Srinivas在NSGA的基础上提出的，它是基于遗传算法的演化算法，在处理多目标问题时，能够找到一组非支配(Pareto)解集，这些解集在多个目标之间存在权衡。NSGA-II算法的设计旨在提供更好的性能和收敛性，以及有效地处理非支配解集。

与NSGA相比，NSGA-II主要有以下三方面改进 [14] ：与传统的NSGA算法相比，NSGA-II算法在以下几个方面具有优势：

1) 快速非支配排序：NSGA-II使用一种快速的非支配排序算法，减少了计算非支配关系的复杂性，提高了算法的执行效率。

2) 多样性维护：NSGA-II引入了拥挤度距离来维护解集的多样性，使得算法能够在解空间中更均匀地分布解，避免陷入局部最优。

3) 更好的收敛性：NSGA-II在选择操作中考虑了个体的等级和拥挤度距离，有利于选择高质量的解，使算法更快地收敛到Pareto前沿。

4) 更稳定的性能：NSGA-II对参数的选择相对较少敏感，因此在不同问题上表现更加稳定，适用性更广泛。

使用NSGA-II算法求解物联网服务优选组合模型的具体步骤如图2所示。

Figure 2. Flowchart of the NSGA-II algorithm

图2. NSGA-II算法流程图

步骤1：g = 0，随机生成初始化种群P_g，个数为N，每个个体表示一个潜在的解决方案，对P_g进行非支配排序和整个个体拥挤度计算。

步骤2：通过锦标赛法，从种群P_g选取部分个体，对选定的个体进行交叉和变异操作，生成下一代种群Q_g，种群数量为N。交叉操作可以将两个个体的信息融合产生新个体，而变异操作则对个体进行微小的随机改变，以保持种群的多样性。

步骤3：将经过选择、交叉和变异操作得到的新个体Q_g与原始种群P_g结合，形成新的数量为2N的种群R_g用于下一代的迭代。

步骤4：对种群R_g的个体进行非支配排序，划分为不同的前沿等级，得到i个非支配解集 $F_1,F_2,\cdots ,F_i$ 。将种群中的个体按照非支配关系划分为多个前沿等级。在每个等级中，个体不会被其他个体支配，而在更高等级的个体会支配低等级的个体。这个步骤确定了解集的多样性。

步骤5：按照非支配解集排序从组合种群R_g依次选取种群个体，直到种群数量大于N，假设此时的非支配解集为F_j。

步骤6：若 $F_{\text{1}},F_{\text{2}},\cdots ,F_j$ 中的所有个体数目超过N，对F_j中所有个体进行拥挤度计算。拥挤度距离表示个体在解空间中的分布密度，用于维持解集的多样性。距离较大的个体会被保留，以避免解集过于密集。根据精英策略，选择F_j中较好的个体和F₁~F_j−1中的所有个体合并组成种群数量为N的新种群P_g+1。

步骤7：令g = g + 1反复执行步骤2到步骤6，直到达到预定的迭代次数。此时求解出物联网服务服务组合模型的Pareto解集。

5. 改进的精英保留策略

原始的NSGA-Ⅱ算法中，根据支配关系，将支配等级低的个体加入到新种群中，等级相同时将拥挤度大的个体放入种群中，直到种群规模达到N [15] 。这种精英保留策略是将所有的精英进行保留，可能会导致快速收敛或者收敛于局部最优解。因此，本文设计了改进的精英保留策略如图3所示。设置参数α，将前N × α个个体直接加入到新种群中，剩余的 N × (1 − α)个个体从次优平面上随机选择。

Figure 3. Improved elite retention strategy

图3. 改进的精英保留策略

6. 测试验证

6.1. 算例模型

物联网服务组合环境下，某个复杂的物联网服务按照一定的规范准则被分解为对应的6个简单子任务，每个简单子任务又能从物联网服务池中找到满足条件的物联网候选服务集子任务和候选资源服务集的关系如表1。

Table 1. Candidate resource service

表1. 候选资源服务

每个候选任务都有不同的QoS指标值与之对应，详细的QoS指标值和能源消耗，用户体验数值如表2所示。

Table 2. Candidate resource evaluation index related parameters

表2. 候选资源评价指标相关参数

物联网服务组合中所需的算例参数分别为：W_T = 0.15，W_R = 0.5，W_S = 0.35；T_max = 800 h，R_max = 3800秒，S_min = 0.93，E_max = 2500 kW·h，A_min = 0.92。

6.2. 算例仿真结果

采取最大迭代次数G_max = 200，交叉率P_c = 0.9，变异率P_m = 0.1，种群数量N_p = 50。通过算例仿真求解，原始NSGA-Ⅱ算法求解物联网服务组合模型的非支配层实验结果如图4所示。图5为原始NSGA-Ⅱ帕累托前沿面与帕累托解集，图中每个圆点代表一个Pareto最优服务组合方案，可以看出通过原始NSGA-II算法求解模型所得的服务组合数量为31个，31个服务组合的具体数值在表3。改进的NSGA-Ⅱ算法求解物联网服务组合模型的非支配层实验结果如图6所示。图7为改进的NSGA-Ⅱ帕累托前沿面与帕累托解集，图中每个圆点代表一个Pareto最优服务组合方案，可以看出通过改进的NSGA-II算法求解模型所得的服务组合数量为13个，13个服务组合的具体数值在表4。图8为两个算法的帕累托前沿对比。表3为原始的NSGA-Ⅱ算法的帕累托解集，表4为改进的NSGA-Ⅱ算法的帕累托解集。

Figure 4. The non-dominated layer of NSGA-Ⅱ algorithm solving the IoT service composition model

图4. NSGA-Ⅱ算法求解物联网服务组合模型的非支配层

Figure 5. Pareto front and Pareto solution set of original NSGA-Ⅱ

图5. 原始NSGA-Ⅱ帕累托前沿面与帕累托解集

Figure 6. The non-dominated layer of improved NSGA-Ⅱ algorithm solving the IoT service composition model

图6. 改进NSGA-Ⅱ算法求解物联网服务组合模型的非支配层

Figure 7. Pareto front and Pareto solution set of improved NSGA-II

图7. 改进的NSGA-II帕累托前沿面与帕累托解集

Figure 8. Comparison of the Pareto fronts of the two algorithms

图8. 两个算法的帕累托前沿对比

Table 3. Pareto solution set of NSGA-Ⅱ algorithm

表3. NSGA-Ⅱ算法的帕累托解集

Table 4. Pareto solution set of improved NSGA-Ⅱ

表4. 改进的NSGA-Ⅱ算法的帕累托解集

相比原始的NSGA-Ⅱ算法，改进的NSGA-Ⅱ算法运行时间减少6.216%，改进的NSGA-Ⅱ算法求解的帕累托面更加平滑。

7. 结论

本文分析了物联网服务组合的重要性和服务流程，在充分考虑物联网平台在服务过程的不确定性前提下，提出了一种以任务完成时间最少、服务响应时间最低、交付物质量最优、能源消耗最小、用户体验最高的物联网服务组合优化模型，为了使多个目标同时达到优化，运用NSGA-Ⅱ对多目标数学模型求解，为了充分发挥NSGA-Ⅱ算法的优势，本文对NSGA-Ⅱ算法进行的精英保留策略进行改进。通过算例实验论证，改进的NSGA-Ⅱ算法运行时间减少6.216%，改进的NSGA-Ⅱ算法求解的帕累托面更加平滑，验证了所提模型和改进的NSGA-Ⅱ算法在解决物联网服务组合问题的有效性和可行性。

参考文献