李旭杰，臧振楠，孙 颖，刘春燕，黄凤辰
(1.南通河海大学海洋与近海工程研究院，江苏 南通 226300；
2.河海大学 计算机与信息学院，南京 211100)
泵闸站工程是防洪排涝及配水的基础性工程，通过将物联网技术、计算机技术、通信技术与自动控制技术有机结合形成泵站智能监控系统[1]，实现泵站实时智能监测、控制及调度，可实现无人值守或少人值守，确保泵闸站安全、可靠、高效地运行，有力提升水资源的高效利用。
但是，目前泵闸站型号多种多样，测量设备的测量方式差异等，从而造成泵站(群)运行监控数据的取值频率、尺度和时间上存在较大差异。泵站自动化监控系统收集了大量泵站运行时的工况、测控信息，各泵站平均采集指标多达上千种。除少量数据以非实时方式被同步至管理调度系统外，大量数据只能保留在泵站现场，无法得到有效利用。随着大量传感器在泵闸站的部署及应用，大量实时及非实时数据呈爆发性增长，若采用传统的端-云(服务器)信息传输及处理体系则易造成网络堵塞及时延激增，甚至信息系统崩溃的危情。因此，如何设计优化的信息传输体系及任务分发机制，及时处理泵闸站的实时、非实时等大量异构数据则尤显重要。边缘计算可将数据在终端或边缘端进行计算处理，相比传统的服务器端处理模式，可有效降低时延，提升系统效率。
目前，已有不少学者对边缘架构的处理模式进行了研究。文献[2]将雾计算网络架构作为云计算网络架构的扩展，将云计算的计算、存储等各项功能从云数据中心转移到更加贴近终端用户的网络边缘，从而有效降低了数据的传输时延。文献[3]在更贴近终端用户的网络边缘部署了大量的雾节点，其具有通信、计算、缓存、控制等能力；
通过任务调度技术将任务分配给不同的边缘服务器或雾节点进行处理，可以有效缩短任务的响应时延。文献[4]中，作者首先介绍了一种支持多无人机的移动边缘计算系统，其中部署的无人机作为地面大规模终端所产生的任务卸载的计算服务器，然后提出了一种两层优化的策略来优化无人机的数量和任务调度方案从而最小化系统的能耗。文献[5]面向移动边缘计算系统，针对无人机电池容量有限的问题提出了一种以最小化系统能耗的任务调度方法。文献[6]中，作者针对多无人机辅助的移动边缘计算系统，对计算资源分配、无人机的轨迹进行了优化，从而最小化系统中任务的完成时间。
综上所述，目前较少对泵闸站数据处理任务的分发进行分析及优化。因此，本文针对泵闸站系统，研究设计一种基于边缘计算架构的泵闸站数据处理分发机制，对需要及时处理的任务在终端上即时处理，或将任务迁移至边缘节点进行处理，从而整体提升系统性能。
1.1 通信模型
上述系统架构模型中，泵闸站传感器与泵闸边缘节点的信道可建模为自由空间传播信道模型。泵闸站传感器与泵闸边缘节点之间的信道增益可以表示为
(1)
(2)
(3)
(4)
式中：B为信道带宽；
Pi为泵闸站传感器节点的发射功率；
n0为噪声功率谱密度。
1.2 计算模型
在该系统架构模型中，泵闸站传感器的任务处理方式有两种：本地计算和完全分发给泵闸边缘节点计算。具体计算模型如下：
(1)本地计算
当泵闸站传感器Si在本地计算其任务Taski时，将Si的CPU的计算能力表示为fi，则本地计算任务的处理时延表示为[7]
(5)
(2)泵闸边缘节点
当泵闸站传感器Si与泵闸边缘节点Ej之间的距离满足式(3)并根据任务分发决策将其任务Taski分发到泵闸边缘节点上计算时，Taski的传输时延可以表示为
(6)
Taski的计算时延可以表示为
(7)
式中：fi,j表示泵闸边缘节点Ej的计算服务器分配给任务Taski的计算资源。
在大多数实际场景中，任务计算结果的数据包比特数较小，与很多研究类似，本文忽略计算结果的返回时延。任务Taski的处理时延记作传输时延和计算时延之和[8]：
(8)
通过优化本地的fi以及边缘端的fi,j可取得更好的时延性能。
根据上述系统架构模型的分析，本小节进一步对问题进行描述并分析优化的性能指标。
在基于边缘计算架构的泵闸站数据处理任务分发模型中，多个泵闸站传感器节点有计算任务需求，这些泵闸站传感器节点产生的任务大小通常是不同的。同时，泵闸站传感器节点可能位于多个泵闸边缘节点的通信覆盖范围内。因此，根据任务Taski是否在本地计算或者任务Taski是否分发到泵闸边缘节点Ej计算，定义二进制决策变量μi,0和μi,j。具体定义如下：
(9a)
(9b)
式中：μi,0表示任务Taski是否在本地计算；
μi,j表示是否将任务Taski分发到泵闸边缘节点Ej计算。
根据上述分析，泵闸站传感器Si产生的任务Taski的处理时延可以表示为
(10)
则系统模型中所有泵闸站传感器产生的任务的处理时延之和，即所有任务处理总时延为
(11)
由上可见，如何选择μi,j则直接影响系统的分发性能。为满足泵闸站传感器对时延敏感型任务的计算需求，本文最小化系统中所有任务处理总时延，并根据上述分析将优化问题建模如下：
P1:minF(μi,0,μi,j,fi,j)
(12a)
(12b)
(12c)
(12d)
(12e)
根据问题建模以及对相关约束条件的分析，μi,0是整数变量，而fi,j是线性变量，因此目标函数是一个混合整数非线性函数。
上一小节对系统模型进行了详细描述并提出了本文的性能优化指标以及相应的目标函数优化问题。由于问题P1中约束C2用于约束整数变量μi,0和μi,j，约束C3和C4用于约束线性变量fi,j，它们之间是相互解耦的，因此，本小节将优化问题P1转化为两个子问题分别进行求解。其中，当泵闸站传感器节点产生的任务的分发决策确定时，将原问题转化为泵闸边缘节点服务器计算资源分配子问题，可证该子问题是一个典型的凸优化问题。当最优的计算资源分配策略确定时，将原问题转化为计算任务分发子问题，该子问题是一个0-1整数规划问题。针对子问题1，其含有线性约束，因此可利用拉格朗日乘子法将有限制的凸优化问题转化为没有限制的问题来求解。针对子问题2，其为典型的组合优化问题，其变量空间的不连续性导致难以用传统的优化方法来进行求解，因此利用樽海鞘群算法(Salp Swarm Algorithm，SSA)来进行求解。
3.1 基于拉格朗日乘子法的计算资源分配
拉格朗日乘子法通过使用拉格朗日乘子将相关的约束条件与原目标函数构成一个新的拉格朗日函数，将有约束的最优化问题转化为一个无约束的极值问题，使得目标函数保持线性关系并进行求解[9]。针对上述分析的计算资源分配子问题，其满足拉格朗日乘子法的使用条件，因此可以使用该方法进行求解。
在上一节分析的系统模型中，泵闸边缘节点仅为确定分发到其上处理的计算任务分配计算资源，因此，定义一个集合H表示确定分发到泵闸边缘节点Ej的任务集合，记作H={i|μi,j=1}。由此，将计算资源分配子问题P2的目标函数表示为
(13)
此外，计算资源子问题P2可以建模为
P2:minT(fi,j)
(14a)
(14b)
(14c)
定理1：计算资源分配子问题P2是一个凸优化问题。
证明：首先，使用海塞矩阵(Hessian Matrix)对目标函数求二阶导数。海塞矩阵的每一项可以具体表示为
(15)
由于目标函数T(fi,j)的约束C3和C4是关于fi,j的线性约束，即目标函数T(fi,j)的域是凸的，因此，目标函数T(fi,j)是关于计算资源fi,j的凸函数，计算资源分配子问题P2是一个凸优化问题。
根据凸优化相关理论，使用拉格朗日乘子法和KKT(Karush-Kuhn-Tucher)条件以求得子问题P2的最优解。
引入拉格朗日乘子λ且λ≥0，根据式(14)凸优化问题构建目标函数T(fi,j)的拉格朗日函数：
(16)
(17)
通过求解式(17)，可以得到最优计算资源分配策略
(18)
将式(18)代入式(13)中，可以得到计算资源分配子问题P2目标函数T(fi,j)的最优值为
(19)
3.2 基于樽海鞘群算法的泵闸站数据处理任务分发算法
樽海鞘群算法是一种新型的启发式智能优化算法，于2017年由Mirjalili等[10]提出。为模拟樽海鞘链的觅食行为，首先按照樽海鞘在种群中的位置，将其分为两种类型，将位于樽海鞘链最前端的樽海鞘称作领导者，将其他个体称作追随者。处于樽海鞘链最前端的领导者对于食物源的位置有着最优的判断，因此领导者能够朝着食物源的正确方向移动并指导紧随其后的追随者移动。在基本的樽海鞘群算法中，只有一个领导者，当解决的问题存在大量局部最优解时，算法容易陷入局部最优解，可将领导者的数量设置为种群数量的一半，从而增强算法的局部开发能力[11]。
樽海鞘群算法的具体流程如图1所示。
图1 樽海鞘群算法流程图
在樽海鞘群算法的搜索空间中，定义矢量X表示个体数为NP的樽海鞘种群的位置：
(20)
根据3.1小节的分析与讨论，确定了在泵闸边缘节点进行计算的任务分配到的最佳计算资源的封闭形式解。将最优的计算资源分配结果(式(18))代入原始问题P1中，可以得到
(21)
原始问题P1转变为关于μi,0和μi,j的分发决策的0-1整数规划问题。因此，可以将计算任务分发子问题建模为
P3:minU(μi,0,μi,j)
(22a)
(22b)
(22c)
计算任务分发子问题P3是组合优化问题中的NP-hard问题，可以使用前面介绍的樽海鞘群算法通过搜索和迭代进行求解。本文所提出的基于樽海鞘群算法的泵闸站任务分发算法详细实现步骤如下：
(1)种群编码及初始化
本文将泵闸站任务分发问题建模为整数规划问题，为使得樽海鞘群算法能够应用于解决多任务分发问题，需要建立以下映射关系：以樽海鞘种群中个体的位置代表任务分发决策，将寻找最优任务分发决策的过程转化为樽海鞘群算法觅食寻优，寻找食物源的过程，因此需对樽海鞘群算法进行离散处理。
(23)
Xi=(1,3,0,2,0,3,4,1,2) 。
(24)
上式表示9个泵闸站传感器和4个泵闸边缘节点场景下的多任务分发问题的一个可行的解决方案，其中，行向量中的位置表示泵闸站传感器的编号，对应的值表示对应泵闸站传感器的分发决策。对应的分发策略为Task3和Task5在本地计算，Task1和Task8分发给泵闸边缘节点E1计算，Task4和Task9分发给泵闸边缘节点E2计算，Task2和Task6分发给泵闸边缘节点E3计算，Task7分发给泵闸边缘节点E4计算。
(2)食物源位置初始化
本文以优化系统中任务处理总时延为目标，因此使用公式(21)作为樽海鞘群算法的适应度函数。根据种群初始化结果，计算所有个体的适应度函数值，选取适应度函数值最优的个体的位置，并将其标记为食物源的位置，记为F=(F1,…,Fm,…,FM)，F即为当前种群的全局最优解。
(3)种群位置更新
樽海鞘群算法在每次迭代过程中，种群中的每个个体通过跟随全局最优或其他同伴的位置来更新自身的位置，具体表现为两种不同的位置更新方式，即领导者位置更新方式和追随者位置更新方式[12]。传统的樽海鞘群算法只有一个领导者，这种机制会增大算法陷入局部最优解的概率。因此，将种群中的前NP/2个个体均按照领导者的方式对其位置进行更新，种群中的后NP/2个个体的位置按照追随者的方式更新，并分别进行离散处理，从而增强算法的局部探索能力。具体地，对领导者位置更新进行离散处理，种群中前NP/2个个体Xi,i>NP/2的位置更新如下：
(25)
(26)
式中：l为当前的迭代次数；
L为最大的迭代次数。
对追随者位置更新进行离散处理，种群中后NP/2个个体Xi,i>NP/2的位置更新如下：
(27)
(4)种群位置修正
(28)
式中：%表示取余。
此外，由于仍需要考虑泵闸边缘节点的通信覆盖约束，如公式(3)所示，因此修正结果首先需要判断是否满足通信覆盖约束，若不满足，则在该修正值的基础上累加1，直至满足约束条件位置。至此，得到新一代的樽海鞘种群。
(5)食物源位置更新
对于新种群中的每个个体，计算其适应度函数值，找出当前适应度函数值最优的个体，并将其与食物源位置相比较。如果优于F，则将原来的食物源位置更新为此个体的位置，完成全局最优解的更新；
反之不更新，继续更新种群位置，进入下一次迭代。
综上所述，基于樽海鞘群算法的泵闸站任务分发算法具体步骤归纳如下：
Step1 初始化参数：种群大小NP，泵闸站传感器数量M，最大迭代次数L，上边界ub，下边界lb，樽海鞘种群位置X，等。
Step2 根据公式(21)计算所有个体的适应度函数值，并按照适应度值排序，找到当前种群最优个体，记为食物源F。
Step3 根据公式(26)更新c1，在区间[0,1]内随机生成c2、c3。
Step4 如果i≤NP/2，根据公式(25)更新领导者位置。
Step5 如果i>NP/2，根据公式(27)更新追随者位置。
Step6 根据公式(28)进行位置修正。
Step7 计算种群个体的适应度函数值，并更新食物源位置。
Step8 若达到设定迭代次数L，结束算法，返回最优分发策略；
若否，则返回Step 3。
Step9 结束。
4.1 仿真场景与参数设定
为验证樽海鞘群算法在解决泵闸站任务分发性能优化问题时的合理性与有效性，使用Matlab仿真平台对系统模型进行模拟，并对实验结果展开分析[13-14]。具体参数如表1所示。
表1 仿真参数设置
4.2 结果分析
图2描述了不同算法下随着迭代次数的增加，最佳任务处理总时延的变化情况。实验结果表明，樽海鞘群算法不仅收敛速度最快，并且性能表现最优。在收敛速度方面，樽海鞘群算法在第21代就开始收敛，而遗传算法在第28代开始收敛到一个可行解。在性能表现方面，遗传算法收敛到的最佳任务处理总时延比樽海鞘群算法高，随机算法性能表现最差。樽海鞘群算法中由于种群中存在领导者，领导者在全局范围内进行寻优，算法在刚开始迭代时就在靠近最优解的方向寻优，因此樽海鞘群算法的收敛速度更快。该结果证明了樽海鞘群算法在全局搜索能力和寻优速度方面的优越性。
(a)Di∈[10,500]×103 b,Ci∈[20,1 000]×106 cycle
(b)Di∈[10,500]b,Ci∈[20,1 000]×103 cycle图2 不同算法下的任务处理总时延
为提高实验结果的可靠性，增加了蒙特卡洛仿真实验次数并进行统计，图3描述了不同算法下最低任务处理总时延的累积分布函数曲线(Cumulative Distribution Function,CDF)曲线，展示了最低任务处理总时延的分布情况。由于每次仿真时泵闸站传感器产生的任务的数据量大小都会重新初始化，同时泵闸边缘节点相对于泵闸站传感器的分布具有随机性，因此最低任务处理总时延在一定范围内波动。从图3中CDF曲线的走势可以看出，随机算法的性能最劣，基于樽海鞘群算法的性能最优。在樽海鞘群算法下，系统中任务处理总时延低于45 s的概率为0.76，而遗传算法和随机算法下相应的概率分别只有0.67和0.42。该实验结果进一步体现了樽海鞘群算法可以有效提高时延敏感型任务的处理性能。
(a)Di∈[10,500]×103 b,Ci∈[20,1 000]×106 cycle
(b)Di∈[10,500]b,Ci∈[20,1 000]×103 cycle图3 不同算法下最佳任务处理总时延的CDF曲线
图4给出了在樽海鞘群算法、遗传算法和随机算法三种不同算法下，优化所得的最低任务处理总时延与泵闸站传感器数量的变化情况。从图中可以直观地看出，在泵闸站传感器数量较少时，樽海鞘群算法和另外两种算法的最低任务处理总时延仿真结果差异并不明显。随着泵闸站传感器数量的增加，三种算法下的系统中所有任务处理总时延呈上升趋势。在泵闸站传感器数量大于20时，樽海鞘群算法优化所得的系统中所有任务处理总时延明显低于遗传算法和随机算法所得到的所有任务处理总时延；
当泵闸站传感器数量大于100时，樽海鞘群算法下得到最低任务处理总时延依旧是最优的，但三种算法下的最低任务处理总时延差异较小。这是由于泵闸站传感器较多时，网络中泵闸站传感器和泵闸边缘节点资源有限，不能满足大规模泵闸站传感器的计算需求。
图4 不同算法下最佳任务处理总时延与泵闸站传感器节点数量的关系
为了验证基于拉格朗日乘子法的计算资源分配的优越性，图5展示了平均资源分配和最优资源分配下的系统中所有任务处理总时延，分别对比了随机算法、遗传算法和樽海鞘群算法下的两种计算资源分配情况。从仿真结果可以看出，随着泵闸站传感器数量的增多，两种资源分配方案下得到的任务处理总时延也随之增加。此外，对于相同数量的泵闸站传感器，三种算法下的基于拉格朗日乘子法的最优资源分配得到的任务处理总时延总是低于平均资源分配，进一步体现了基于拉格朗日乘子法的最优资源分配在所研究问题中的重要作用。
图5 不同资源分配方法下的任务处理总时延
图6描述了在终端节点数量从10增加到50时，任务全随机卸载和平均资源分配、樽海鞘群卸载和平均资源分配、樽海鞘群卸载和拉格朗日资源分配等几种算法的系统任务处理总时延。从图中可见，任务全随机卸载和平均资源分配的任务处理总时延最高，本文所提的樽海鞘群卸载和拉格朗日资源分配算法的任务处理总时延最低。本文所提算法比任务全随机卸载和平均资源分配算法可以降低76.9%的任务处理时延，比樽海鞘群卸载和平均资源分配算法降低了29.2%的任务处理时延。这是由于任务全随机卸载和平均资源分配算法没有对边缘节点的计算资源进行有效的利用，所以性能最劣。樽海鞘群卸载和平均资源分配算法虽然对卸载策略进行了优化但对平均资源的分配没有优化，其性能也较差。樽海鞘群卸载和拉格朗日资源分配对本地节点、边缘节点的计算资源进行了最优的分配，有效降低了任务处理总时延。
图6 不同任务卸载与资源分配算法下的任务处理总时延
本文针对泵闸站数据处理任务分发问题，将其建模为混合整数非线性规划问题。为求解该问题，将其解耦为计算资源分配子问题和任务分发子问题，然后利用拉格朗日乘子法对计算资源分配子问题进行求解计算，利用樽海鞘群算法对任务分发子问题进行求解计算。通过不断迭代交替求解，得到最佳的计算资源分配和任务分发策略。仿真结果表明，本文所提算法能够有效降低系统中所有任务处理的总时延，从而保障了泵闸站传感器时延敏感型任务的处理质量。
猜你喜欢海鞘资源分配时延改进樽海鞘群优化K-means算法的图像分割包装工程(2022年9期)2022-05-14新研究揭示新冠疫情对资源分配的影响 精读英语文摘(2020年10期)2020-11-26基于GCC-nearest时延估计的室内声源定位电子制作(2019年23期)2019-02-23一种基于价格竞争的D2D通信资源分配算法测控技术(2018年7期)2018-12-09基于改进二次相关算法的TDOA时延估计测控技术(2018年6期)2018-11-25基于动态规划理论的特种设备检验资源分配研究智富时代(2018年3期)2018-06-11基于动态规划理论的特种设备检验资源分配研究智富时代(2018年3期)2018-06-11中国沿海污损性海鞘生态特点及研究展望生态科学(2018年1期)2018-03-26云环境下公平性优化的资源分配方法计算机应用(2016年10期)2017-05-12FRFT在水声信道时延频移联合估计中的应用系统工程与电子技术(2016年7期)2016-08-21