基于进化多目标合作博弈的体域网通信优化

2018-03-19 05:54钱兰美王晔娇
计算机工程与设计 2018年3期
关键词:数据量种群收益

周 晖,钱兰美,薛 磊,王晔娇

(南通大学 电子信息学院,江苏 南通 226019)

0 引 言

在基于云计算的体域网(cloud-body sensor network,CBSN)[1,2]中,云计算的效用计算、虚拟化技术、数据存储等优势使大规模感知数据的实时获取成为可能,研究云计算与体域网之间的数据通信是其关键技术[3,4]。由于传感器节点能量有限、通信带宽受限,使获取大规模感知数据与降低通信带宽占用量和传感器节点能耗相冲突[5]。

目前,主要有两类解决方案。一类是采用多目标进化算法[6,7]。文献[8,9]采用选择、交叉、变异等遗传算子实现种群进化,通过非支配排序法与拥挤度比较算子,最终得到Pareto解集,仿真结果显示该方法能获得质量好的解,但解的分布不均匀、不稳定,且在寻优后期收敛速度较慢,计算成本较高。另一类是采用非合作博弈方法[10]。文献[11]采用演化博弈算法(evolutionary game algorithm,EGA),利用目标间约束支配关系决定优胜者,同时采用复制者动态和进化稳定策略最终达到Nash均衡状态,仿真实验将其与NSGA-II[12]相比较,在优化性能和稳定性方面均优于NSGA-II。然而,在博弈过程中由于竞争过于激烈易导致部分质量好的解丢失,甚至陷入局部次优,另外非合作博弈具有目标偏好,不能实现整体目标利益的均衡。

针对上述问题,提出CBSN的进化多目标合作博弈方法(sensor cloud-evolutionary multi-objective cooperative game,SC-EMCG)。根据目标之间的竞争与合作关系构造收益函数,进行共谋合作博弈,在竞争中开展合作,在各个冲突目标之间互相权衡、竞争,以实现目标整体收益的最大化;同时结合进化计算,引入精英保留策略,将博弈获胜方复制到种群中,落败方被移除种群;引入Levy飞行算子,扩大种群搜索范围,避免陷入局部次优。

1 CBSN博弈模型

针对图1中的CBSN通信架构,建立数据量、通信带宽和传感器节点能耗三者之间的博弈模型。

图1 CBSN通信架构

1.1 符号列表

与CBSN通信问题相关的基本符号说明见表1。

表1 基本符号说明

1.2 博弈方与博弈策略集

博弈方为相互冲突的3个目标,包括云端数据量、通信带宽占用量和传感器节点能耗。博弈策略集s(bi)为决策变量的组合,如式(1)所示

(1)

1.3 收益函数

在CBSN博弈模型中,各博弈方的收益函数即为其适应度函数,分别是传输层和云服务层之间的通信带宽占用量,物理传感器的能量消耗,云服务层数据收益。

带宽占用量收益函数fB:传输层和云层之间单位时间内传输数据总量

式中:第1项为传输层与云服务层单向push通信带宽占用量;第2项为传输层与云服务层双向pull通信带宽占用量;dr为常量,表示云层向传输层之提出一个pull请求的大小。

能耗收益函数fE:在时间窗口W内传感器节点进行数据传输消耗总能量

数据量收益函数fY:云应用为用户收集的数据总量

(4)

1.4 约束条件

在CBSN中,博弈过程的约束条件如下

约束1:fE

(5)

约束2:fY

(6)

其中,cE是能量消耗fE的上界,cY是数据受益fY的下界。

2 SC-EMCG算法

2.1 合作博弈收益函数的构造

根据各博弈方之间的竞争与合作关系,构造各博弈方的收益函数

(7)

2.2 共谋合作博弈步骤

根据式(7)构造的收益函数进行共谋合作博弈,具体博弈步骤见流程如图2所示。

图2 共谋合作博弈流程

在生成初始策略组合后,各博弈方在自身策略空间,以自身收益函数为目标进行单目标优化,得到最佳策略组合,再根据约束条件以及前后策略组合之间的范数是否满足收敛准则确定其是否可行。

2.3 进化计算

SC-EMCG算法将合作博弈与进化计算相结合。进化算子包括Levy飞行算子[13]与精英保留策略。初始化策略空间后,采用Levy飞行算子进行位置更新。其实现如下

(8)

其中,α>0是搜索步长,通常令α=1;符号⊕表示点对点乘法。Levy飞行的随机步长满足Levy分布,即Levy~u=t-λ, (1<λ≤3),采用Levy飞行可扩大算法的搜索范围,促进全局收敛。

采用精英保留策略[14],父代种群与子代种群共同参与下一代种群的进化,以加快算法执行速度,保证种群多样性。

2.4 算法流程

SC-EMCG算法流程如图3所示。

图3 SC-EMCG算法流程

SC-EMCG算法将共谋合作博弈与进化计算相结合,其合作博弈收益函数的构造见式(7);共谋合作博弈过程见2.2节;Levy飞行策略进行位置更新,其飞行步长满足heavy-tailed分布;精英保留将获胜方复制到种群中,将落败方移除种群。

3 仿真研究

为了验证SC-EMCG算法在求解CBSN通信优化问题的性能和计算效率,分别从收敛结果、收敛速度、解的稳定性和解的多样性4个方面进行研究。并将其与多目标进化算法NSGA-II和非合作博弈中的EGA比较。为保证实验的公平性,NSGA-II、EGA与SC-EMCG的基本参数设置相同。仿真实验采用Matlab7.8实现,运行在3.10 GHz Core i5-2400CPU,4 GBRAM的计算机上。

3.1 仿真场景及参数设置

建立一个远程监控10个病人生理活动的仿真环境,每个病人携带一个sink节点,佩戴5种传感器,组成一个单跳身体传感网络。在时间周期3小时内云端提出10 000个数据请求,请求均匀分布在虚拟传感器节点上,传感器节点参数见表2,仿真参数见表3。根据带宽占用量,传感器节点能耗以及数据量三者之间的竞争与合作关系,令wii服从正态分布ω11~(0.75,0.005),ω22~(0.5,0.005),ω33~(0.5,0.005)。

3.2 仿真结果与分析

收敛结果分析。图4(a),图4(b),图4(c)分别是算法SC-EMCG、EGA和NSGA-II数据量、节点能耗和带宽占用量收益函数的收敛曲线。由图4可知,SC-EMCG算法的数据量、节点能耗和带宽占用量,均优于NSGA-II;当迭代次数比较小时,算法SC-EMCG优化性能略低于EGA算法,但随着迭代次数的增加,SC-EMCG算法的收敛结果明显优于EGA算法。

表2 传感器节点参数设置

表3 仿真参数设置

图4 收益函数收敛曲线

表4为3种算法各个收益函数的最优值、平均值和最劣值。由表可见,无论是最优值、最劣值、平均值,SC-EMCG算法得到的数据量、带宽占用量和节点能耗均优于算法NSGA-II和EGA。由图4和表4所列出的仿真结果可见,SC-EMCG算法有效实现数据量、通信带宽和传感器节点能耗三者之间的均衡。

收敛速度分析。表5为SC-EMCG、EGA和NSGA-II这3种算法的运行时间,由表5可知,在迭代次数小于100时,3种算法运行时间相差不大。但是,在100代之后,算法SC-EMCG和EGA运行时间明显优于NSGA-II算法,SC-EMCG算法的整体运行时间比MOEA快18.4%。由此可见,NSGA-II在算法前期收敛速度较快,但在算法后期收敛速度较慢;而算法SC-EMCG和EGA一直保持较快的收敛速度。

解的分布性分析。图5(a),图5(b),图5(c)分别为算法SC-EMCG、EGA和NSGA-II所有个体在三维目标空间的映射。由图5可见,SC-EMCG算法解的分布集中,且均匀;EGA算法次之;而NSGA-II算法的解分布比较分散,不均匀。可见,SC-EMCG算法解的分布性好。

表4 收益函数值

表5 SC-EMCG、EGA和NSGA-II运行时间

图5 三维目标空间分布

解的多样性分析。通过Hypervolume指标[15]衡量解的多样性,指标数据进行归一化处理。图6为3种算法的Hypervolume值。由图6所示,SC-EMCG算法的Hypervolume值显著优于其它两种算法,可见,SC-EMCG算法的种群多样性优于其它两种算法,反映该算法在避免局部次优,实现全局收敛方面的优势。

图6 3种算法的Hypervolume值

4 结束语

提出进化多目标合作博弈算法,解决CBSN中数据量、通信带宽和传感器节点能耗相互冲突问题。采用共谋合作博弈能够在保证快速收敛的同时,实现目标的整体收益的最大化;采用Levy飞行和精英保留策略,扩大种群搜索范围,实现全局收敛。仿真研究表明,该算法与现有算法相比较,其解集不仅具有更好的分布性与多样性,而且收敛速度快,能够有效实现体域网通信中数据量、通信带宽和传感器节点能耗三者之间的均衡。

[1]Movassaghi S,Abolhasan M,Lipman J,et al.Wireless body area networks:A survey[J].IEEE Communications Surveys & Tutorials,2014,16(3):1658-1686.

[2]Ghamari M,Janko B,Sherratt RS,et al.A survey on wireless body area networks for ehealthcare systems in residential environments[J].Sensors,2016,16(6):234-251.

[3]Fortino G,Fatta GD,Pathan M,et al.Cloud-assisted body area networks:State-of-the-art and future challenges[J].Wireless Networks,2014,20(7):1925-1938.

[4]Fortino G,Pathan M,Fortino G,et al.Integration of cloud computing and body sensor networks[C]//IEEE,International Conference on Cloud Computing Technology and Science.IEEE Computer Society,2012:57-61.

[5]Ren YC,Suzuki J,Omura S,et al.Evolutionarily reconfigurable cloud-integrated body sensor networks[C]//Internatio-nal Conference on E-Health Networking,Application & Ser-vices.IEEE,2015:78-102.

[6]Azzouz R,Bechikh S,Said LB.Dynamic multi-objective optimization using evolutionary algorithms:A survey[M]//Recent Advances in Evolutionary Multi-objective Optimization.Springer International Publishing,2017.

[7]ZHOU Hui,YANG Zhen,ZHU Liqing,et al.On the global convergence of real-coaded chemical reaction optimization[J].Systems Engineering Theory and Practice,2015,35(12):3233-3240(in Chinese).[周晖,杨振,朱立庆,等.实数编码化学反应优化的全局收敛性研究[J].系统工程理论与实践,2015,35(12):3233-3240.]

[8]Phan DH,Suzuki J,Omura S,et al.Toward sensor-cloud integration as a service:Optimizing three-tier communication in cloud-integrated sensor networks[C]//Int’l Conference on Body Area Networks.Boston:ACM,2013:212-219.

[9]Phan DH,Suzuki J,Omura S,et al.Multiobjective communication optimization for cloud-integrated body sensor networks[C]//IEEE/ACM International Symposium on Cluster,Cloud and Grid Computing.IEEE,2014:685-693.

[10]Xu M,Yang Q,Kwak K.Distributed topology control with lifetime extension based on non-cooperative game for wireless sensor networks[J].IEEE Sensors Journal,2016,16(9):3332-3342.

[11]Ren YC,Suzuki J,Phan DH,et al.An evolutionary game theoretic approach for configuring cloud-integrated body sensor networks[C]//IEEE International Symposium on Network Computing and Applications.Cambridge:IEEE,2014:277-281.

[12]Verdejo H,Gonzalez D,Delpiano J,et al.Tuning of power system stabilizers using multiobjective optimization NSGA-II[J].IEEE Latin America Transactions,2015,13(8):2653-2660.

[13]Suresh S,Lal S.An efficient cuckoo search algorithm based multilevel thresholding for segmentation of satellite images using different objective functions[J].Expert Systems with Applications,2016,58(C):184-209.

[14]LIU Jian,LI Jinghang,BAI Xiaoli.Reactive power optimization of distribution network using genetic algorithm with elitist strategy[J].Electrical Engineering,2015,16(4):35-38(in Chinese).[刘健,李京航,柏小丽.基于精英保留策略遗传算法的配电网无功优化[J].电气技术,2015,16(4):35-38.]

[15]Jiang S,Zhang J,Ong YS,et al.A simple and fast hypervolume indicator-based multiobjective evolutionary algorithm[J].IEEE Transactions on Cybernetics,2015,45(10):2202-2213.

猜你喜欢
数据量种群收益
山西省发现刺五加种群分布
基于大数据量的初至层析成像算法优化
计算Lyapunov指数的模糊C均值聚类小数据量法
螃蟹爬上“网” 收益落进兜
高刷新率不容易显示器需求与接口标准带宽
宽带信号采集与大数据量传输系统设计与研究
中华蜂种群急剧萎缩的生态人类学探讨
怎么设定你的年化收益目标
2015年理财“6宗最”谁能给你稳稳的收益
岗更湖鲤鱼的种群特征