基于动态信任的最优云服务选择算法

王宗江，杨淑慧

(1．中原工学院 计算机学院，河南 郑州450007;2．郑州大学 水利与环境学院，河南 郑州450001)

0 引言

云计算是近年来的一个研究热点［1］． 从云计算的权威定义可以看出［2］，服务(也是一种资源)管理是云计算的核心问题．在服务管理中，通常有两个角色:服务提供者(Service Provider，SP)和服务消费者(Service Consumption，SC)．

当前，由于不同云计算商的服务质量存在较大差异，使得用户在服务选择的过程中也存在着较大的矛盾．一方面由于缺乏专业知识，服务消费者不知道有哪些满足自己需求的服务提供者;另一方面服务提供者则不知道有哪些服务消费者需要服务，需要什么种类的服务．此外，服务提供者和服务消费者都存在恶意非合作(即满足要求，却不执行)情形．服务提供者从本身角度考虑，只选择能够获得较高收益的消费者，这样会大大增加其它服务消费者的等待时间;而服务消费者为了减少自己的等待时间，则会发出多个服务请求，最后只选择一个最快到达的服务，从而影响了服务提供者的整体利用率，对社会资源造成了极大的浪费．

现实社会中，常采用服务的最优化方法来解决服务选择问题，即利用各种优化方法为服务消费者自动寻找到最优的服务提供者． 这里的优化目标包括距离最近、花费最小等［1-2］．但是对于服务提供者和服务消费者出现的恶意非合作情况，当前研究都没有提出有效的解决方法．

笔者针对服务选择中存在的问题，提出了基于动态信任的最优服务选择算法，其核心思想为:为服务消费者和服务提供者分别建立动态信任评估方法;为每一个服务消费者提出的服务请求，找到最优的服务提供者;当前服务完成后，根据完成情况，对服务提供者和服务消费者的信任值进行动态更新;将更新后的最新信任值应用到下一个服务选择过程中．实验结果表明，该方法不但能够为众多服务消费者和服务提供者提供较优的匹配，还能有效改变当前服务消费者和服务提供者的恶意非合作情形．

1 基于动态信任的最优服务选择模型框架

根据目前关于SLA 信任的相关研究，结合现有技术等［3-6］，笔者设计出了基于动态信任的最优服务选择模型框架，如图1 所示．

该模型框架包括3 个对象:服务消费者、服务提供者和软件应用商．

服务消费者具有3 个功能:申请服务封装，主要用来封装以SLA 表示的服务申请和它自身的位置信息(x，y);信息收发，控制用于向软件应用商发送服务请求和软件应用商的交互信息;信息显示，用于显示服务消费者和服务提供者的动态位置信息和服务提供者所提供的服务信息．

服务提供者具有3 个功能:提供服务封装，主要用来封装以SLA 表示的服务申请和它自身的位置信息(x，y);信息收发控制，用于向软件应用商发送提供的各种类型的服务和和软件应用商的交互信息;信息显示，用于显示服务消费者和服务提供者的动态位置信息和服务消费者所提供的服务申请信息．

软件应用商具有3 个功能:信息收发控制，用于接收服务消费者的服务请求信息和服务提供者的服务信息;信息存储，用于将接收信息保存下来，以供处理模块使用;信息处理包括两个功能，一个是利用保存的每次交易信息，计算服务消费者和服务提供者的当前动态信任值． 另外一个功能是利用计算得到的动态信任值，选择出最优服务．

图1 基于动态信任的最优服务选择模型框架Fig．1 Optimal service selection framework based on dynamic trust

服务消费者通过该模型选择服务提供者的具体流程如下(图2)．

(1)服务提供者首先将自己的服务在软件应用商注册，服务信息包括:服务提供者ID，服务ID，服务类型，服务内容，对应的SLA 及位置信息等．

(2)服务消费者在软件应用商注册，信息包括:服务消费者ID，基本信息等．

(3)服务消费者向软件应用商发送申请服务，请求信息包括服务类型、服务内容等．

(4)软件应用商首先将请求信息保存下来，然后计算动态信任值，进行最优服务选择，然后向选择的服务提供者发送服务申请．

(5)服务提供者得到服务请求，进行服务响应，发送信号给服务消费者．

(6)本次服务结束，服务消费者支付费用给服务提供者，并对服务提供者的服务进行评价．

(7)服务提供者获得本次服务费用，并对服务消费者进行评价．

图2 服务选择场景数据流Fig．2 Data flow of service selection

2 动态信任值计算与基于动态信任的最优服务选择算法

在本节给出了动态信任值的计算方法［7-8］，以及利用该信任值的最优服务选择算法．

2．1 动态信任值计算

2．1．1 服务提供者的动态信任值

在每次交易结束后，计算本次交易的信任值，服务提供者的信任值由3 部分构成:

(1)服务提供者自身评价(SPe)． SPe =QoS完成情况的归一化，其值的范围为［0，1］．

(2)应用商评价(Ae)． 正常情况下:Ae = 服务单价×服务时间．

恶意非合作情况下:Ae = -服务单价×服务时间

(3)服务消费者评价(SCe)．SCe =服务消费者打分的归一化，其值的范围为［0，1］．

服务提供者动态信任值:Ae + 100·SPe +100·SCe．

最新信任值:以往信任值+本次交易信任值．

2．1．2 服务消费者的动态信任值

服务消费者的信任值由两部分构成．

(1)服务提供者评价(SPe)．SPe 为服务提供者打分的归一化，其值的范围为［0，1］．

(2)应用商评价(Ae)． 正常情况下:Ae = 服务单价×服务时间;恶意非合作情况下:Ae= -服务单价×服务时间．

服务消费者动态信任值:Ae+100·SPe．

最新信任值:以往信任值+本次交易信任值．

2．2 基于动态信任的最优服务选择算法

假定最优服务是指该服务消费者距离最近的服务提供者所提供的服务． 基于动态信任的最优服务选择算法DTOS 如下．

(1)服务消费者欲获得某种服务，首先向软件应用商提出服务请求，其中每个服务请求包括用SLA 表示的服务和所在位置的坐标(x，y)．

(2)软件应用商接到请求后，将当前申请服务的所有服务消费者放入到队列Qsc 中．

(3)软件应用商将当前注册的服务提供者放入到队列Qsp 中，其中每个服务提供者包括用SLA 表示的服务和所在位置的坐标(x，y)．

(4)对队列Qsc 进行k-means 聚类，得到N 个Cluster，记为C1，C2，…，Cn．

(5)使用上面的N 个质心，将Qsp 分配到N个Cluster 中．

(6)将C1中的服务请求按照动态信任值进行降序排序，根据C1中的第一个服务请求SR1，将C1中的服务提供者按照最优服务降序排列Qsp1．

(7)将C1中的第一个服务请求SR1发送到Qsp1中的第一个服务提供者SP1，等待SP1回应．

(8)如果SP1回应，继续分配下一个服务．

(9)否则，延迟时间r 秒后，将请求SR1发送到Qsp1中的第二个服务提供者SP2．

(10)当C1中的第一个服务请求SR1分配完后，分配下一个服务请求SR2．

(11)当C1中的所有服务请求分配完后，回到步骤6 进行循环，继续下一个Cluster C2，直到结束．

3 实验分析

笔者使用了CloudSim 框架对所提出的算法进行实验和评估．CloudSim 是一个由墨尔本大学Buyya 教授领导的研究小组开发、能够对云计算环境进行建模和模拟、可以扩展的模拟工具开放源码软件［9］． 在实验中，扩展Datacenter 类，实现了自定义的调度策略，完成了对调度算法的模拟，并进行了相关测试和实验． 其中的服务提供者参数设置如表1 所示，服务消费者参数设置如表2所示．

3．1 随交易次数增加不同类型信任值的变化情况

将服务消费者和服务提供者的信任分为3类:完全可信、可信及不可信［10］，信任值为T，Tmax≤T≤1:表示“完全可信”，完全可信服务提供者所提供的服务是真实可信服务，完全可信服务消费者履行交易也是真实可信的，它们出现恶意非合作情况非常少．

表1 服务提供者参数设置Tab．1 Parameters of service providers

表2 服务消费者参数设置Tab．2 Parameters of service consumptions

Tmin≤T≤Tmax:表示“可信”，用户对可信服务提供者提供的服务满意度稍差，但能够一直提供真实可信的服务，服务消费者履行交易也是基本可信的，它们出现恶意非合作情况较少．

0≤T≤Tmin:表示“不可信”，不可信服务提供者很少提供真实可信的服务，不可信服务消费者履行交易也不是真实可信的，两者共同的特征是会经常出现恶意非合作情况．

在仿真实验中，假设Tmin=0．3，Tmax=0．8，即信任值在［0．8，1．0］时为完全可信，在［0．3，0．8］时为可信，在［0，0．3］时为不可信．定义3 类服务提供者的比例分别为20%，70%，10%．各类服务提供者的信任值变化如图3 所示，其中横坐标表示交易次数，纵坐标表示信任值．

从图3 可以看出，完全可信和可信服务提供者由于一直提供真实可信的服务，信任值随交易次数的增加而呈上升趋势． 不可信服务提供者由于一直提供不可信服务，信任值下降很快．3 类服务消费者的信任值变化和服务提供者信任值变化基本一致．

3．2 随交易次数增加不同选择策略的服务提供者的服务利用率

对3 种服务选择策略进行比较，随机服务选择策略、基于信任的服务选择策略和基于动态信任的最优服务选择策略．

图3 3 类服务提供者的信任值随交易次数的变化Fig．3 Changes of transaction times of three types service provider trust valur

随机服务选择策略:软件应用商在满足服务消费者基本功能的服务提供者列表中，随机选择一个服务提供者作为服务提供者．

基于信任的服务选择策略:软件应用商在满足服务消费者基本功能的服务提供者列表中，选择信任值最高的服务提供者作为服务提供者．

基于动态信任的最优服务选择策略:软件应用商在满足服务消费者基本功能的服务提供者列表中，选择动态信任值高的最优服务提供者作为服务提供者．服务提供者的服务利用率为服务使用时间和24 h 的比值．在此假定服务提供者提供的服务是全天24 h 一直可用．

3 种不同服务策略的利用率变化如图4 所示，其中横坐标表示交易次数，纵坐标表示服务利用率．从图4 可以看出，随机服务选择策略的利用率非常低．其他两种服务策略和随机服务选择策略相比，效率提高许多．主要是随机服务选择算法不考虑是否满足服务，造成效率非常低．

3．3 随交易次数增加不同选择策略的服务消费者的等待时间

服务消费者的等待时间是指服务消费者发出服务申请到确认服务的过程所花费的时间．3 种不同服务策略的服务消费者等待时间变化如图5 所示．从图5 可以看出，随机服务选择策略的等待时间围绕一个均值(10 s)波动． 另外两种服务策略的服务消费者等待时间随着交易次数的增加逐渐降低，其中基于动态信任最优服务选择算法下降的更加明显． 主要是它不但考虑了动态信任，还考虑了最近距离，减少了服务传输时间．

由图4 和图5 可以看出，基于动态信任的最优服务选择算法不但使服务提供者获得了较高的利用率，还使服务消费者获得了较短的等待时间．而且，由于对两者出现的恶意非合作情形进行了惩罚．服务消费者和服务提供者为了自己的利益，都会减少恶意非合作情形．

图4 不同选择策略随交易次数增加时服务提供者服务利用率的变化情况Fig．4 Changes of transactions times with different service selection strategy of service provide utility

图5 不同选择策略随交易次数增加时服务消费者等待时间的变化情况Fig．5 Changes of transactions times with different service selection strategy of service consumption waiting time changes

4 结论

随着云计算的快速发展，国内外出现了大量的云服务提供商． 如何为每个服务消费者快速找到合适的服务提供者是一个难题． 笔者提出了基于动态信任的最优服务选择模型． 它不但能够为服务消费者和服务提供者提供最优匹配，还能有效减少两者出现的恶意非合作情形．如实验所示，本算法既为服务提供者提供了较高利用率，又使得服务消费者获得了较短的等待时间．

笔者的目标是将本算法应用到实际应用中．其中，本算法动态信任中使用的权重是固定值，将来考虑使用更符合实际的值．此外，将充分利用软件应用商存储的服务消费者和服务提供者交易信息，为两者提供更好的服务．例如可以为服务提供者预先提示较常用的服务消费者服务，减少不常用的服务，从而提高服务利用率．

［1］ 林伟伟，齐德昱．云计算资源调度研究综述［J］． 计算机科学，2012，39(10):1 -10．

［2］ LIU Liang，WANG Hao，LIU Xue，et al． Green-Cloud:a new architecture for green data center［C］∥Proceedings of the 6thInternational conference Industry Session on Autonomic Computing and Communicaitons industry Session． New York:ACM，2009:29 -38．

［3］ BUYYA R，GRAG S，CALHEIROS R． SLA -oriented resource provisioning for cloud computing:challenges，architecture，and solutions［C］∥Proceedings of the 2011 IEEE International Conference on Cloud and Service Computing． Washington D C:IEEE，2009:1-10．

［4］ VAN H N，TRAN F D，MENAUD J M． Sla-aware virtual resource management for cloud infrastructures［C］∥Ninth IEEE International Conference on Computer and Information Technology． Xiamen:IEEE，2009:357 -362．

［5］ WU Lin-lin，GARG S，BUYYA R． SLA-based resource allocation for software as a service provider(SaaS)in cloud computing environments［C］∥11th IEEE/ACM International Symposium on Cluster，Cloud and Grid Computing． Newport Beach:IEEE，2011:195 -204．

［6］ BlAZE M，FEIGENBAUM J，Lacy J． Decentralized trust management［C］∥Proceedings of IEEE Symposium on Security and Privacy．Oakland:IEEE，1996:164-173 ．

［7］ 胡春华，罗新星，王四春，等．云计算环境下基于信任推理的服务评价方法［J］． 通信学报，2011，32(12):72 -81．

［8］ 胡春华，陈晓红，吴敏，等．云计算中基于SLA 的服务可信协商与访问控制策略［J］．中国科学:信息科学，2012，42(3):314 -332．

［9］ CALHEIROS R，RANJAN R，ANTON B，et al．CloudSim:a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms［J］． Software:Practice and Experience，2011，41(1):23 -50．

［10］杜瑞忠，田俊峰，张焕国．基于信任和个性偏好的云服务选择模型［J］．浙江大学学报:工学版，2013，47(1):53 -61．