Loading [MathJax]/jax/element/mml/optable/BasicLatin.js
高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

一种使用改进预测成本矩阵任务优先排序的异构计算系统列表调度算法

姚宇 宋宇鲲 杨国伟 黄英 张多利

方剑, 林为干, 赵愉深. 电磁波在对流层中传播的抛物化方程的有限差分解法[J]. 电子与信息学报, 1995, 17(3): 315-320.
引用本文: 姚宇, 宋宇鲲, 杨国伟, 黄英, 张多利. 一种使用改进预测成本矩阵任务优先排序的异构计算系统列表调度算法[J]. 电子与信息学报, 2023, 45(1): 125-133. doi: 10.11999/JEIT211150
Fang Jian, Lin Weigan, Zhao Yushen. NUMERICAL SOLUTION OF THE PARABOLIC EQUATION REPRESENTING ELECTROMAGNETIC WAVE PROPAGATION IN THE TROPOSPHERE USING BOX METHOD[J]. Journal of Electronics & Information Technology, 1995, 17(3): 315-320.
Citation: YAO Yu, SONG Yukun, YANG Guowei, HUANG Ying, ZHANG Duoli. A List Scheduling Algorithm for Heterogeneous Computing Systems Using Improved Predict Cost Matrix for Task Prioritizing[J]. Journal of Electronics & Information Technology, 2023, 45(1): 125-133. doi: 10.11999/JEIT211150

一种使用改进预测成本矩阵任务优先排序的异构计算系统列表调度算法

doi: 10.11999/JEIT211150
基金项目: 安徽高校协同创新项目(GXXT-2019-030)
详细信息
    作者简介:

    姚宇:男,博士生,研究方向为多核片上网络系统编译技术

    宋宇鲲:男,副研究员,研究方向为片上网络优化、多核系统设计、数字信号处理的VLSI实现

    杨国伟:女,硕士生,研究方向为可重构计算技术

    黄英:女,教授,博士生导师,研究方向为敏感材料与传感器技术

    张多利:男,研究员,博士生导师,研究方向为多核处理器体系架构和设计方法

    通讯作者:

    张多利 zhangduoli@hfut.edu.cn

  • 中图分类号: TN401

A List Scheduling Algorithm for Heterogeneous Computing Systems Using Improved Predict Cost Matrix for Task Prioritizing

Funds: The University Synergy Innovation Program of Anhui Province (GXXT-2019-030)
  • 摘要: 异构计算系统执行应用效率的提高高度依赖有效的调度算法。该文提出一种新的列表调度算法,称为改进的预测优先任务和乐观处理器选择调度(IPPOSS)。通过在任务优先级排序阶段引入任务的后向预测成本,来减少调度长度。与现有工作相比,该文使用改进预测成本矩阵(IPCM),更合理地进行了任务优先级排序,从而在处理器选择阶段获得了更好的解,并保持2次时间复杂度。IPCM考虑了任务优先级排序阶段的各种计算、通信因素,比预测优先任务调度(PPTS)提出的预测成本矩阵(PCM)更容易获得合理的优先级列表。随机生成应用的有向无环图(DAG)和真实世界应用的DAG的实验结果分析表明,IPPOSS的性能优于相关算法。
  • 随着无线通信设备的普及,确保通信安全变得愈发关键,特别是随着物联网(Internet of Things, IoT)在各个领域的应用[1],使得通信安全成为一个广受关注的问题。传统的无线通信安全研究主要侧重于通过加密[2,3]和物理层安全(Physical Layer Security, PLS)[46]来保护通信内容免受窃听。然而,在某些情况下,通信行为的隐藏也非常重要,这就需要进行私密消息的隐蔽传输。例如,在战场上的军事侦察信号、公共场所中的个人隐私信号传输以及机密的金融数据传输等场景中,不仅需要确保传输信息的安全性,还需要确保传输行为本身的隐蔽性,由此隐蔽通信应运而生。隐蔽通信的历史可以追溯到上世纪初兴起的扩频通信[7],其核心是使发送信号功率低于背景噪声,以实现对传输信号的隐藏。尽管已有不少利用扩频技术实现信息隐蔽的案例[8],但隐蔽通信的理论机理一直没有得到严格的论证和定量的表征。直到2013年,Bash等人[9]揭示了在加性白高斯噪声(Additive White Gaussian Noise, AWGN)信道上进行隐蔽传输的基本性能界,奠定了隐蔽通信的信息论基础,掀起了一轮隐蔽通信研究的热潮。此后,研究人员针对隐蔽通信的不同方面展开广泛研究,包括考虑不同的信道模型[7]、不确定性来源[10,11]和不同的网络架构[12,13]

    为了增强隐蔽通信的性能,研究人员在传统的隐蔽通信系统中加入了人工噪声。如文献[14]利用干扰节点向窃听者发送人工噪声,以干扰其检测行为。文献[15]分析了时变干扰对隐蔽吞吐量的影响。文献[16]通过采用一个能够感知Alice传输信息的认知干扰节点,增强了系统的隐蔽传输速率。文献[17]首次考虑了一个全双工的接收节点,它发送变功率的人工噪声,以干扰检测者的检测行为。在此基础上,文献[18]给出了最优的干扰功率范围和最优的先验发送概率。由于单天线发送的干扰信号存在泄露问题,因此对接收端有一定影响。为了提高干扰控制能力,研究人员进一步采用多天线技术(Multi-Antenna Technology, MAT)[19]控制干扰信号的发送范围。文献[20]引入了MAT实现人工噪声干扰以提升D2D用户隐蔽通信能力。此外,MAT可以增强接收信噪比[21],并可以用于改善中继性能[22]等。

    然而,传统的MAT系统复杂度与功耗较高,需要较多的射频链路和移相器等组件以实现波束形成,阻碍了其在隐蔽通信中的广泛应用。时间调制阵列(Time-Modulated Array, TMA)作为一种有着独特优势的前沿技术备受关注[23]。与传统天线阵列相比,TMA引入的时间维提高了自由度,并采用单通道结构有效降低了复杂度,带来移相精度更高、频率一致性更好等一系列优势[24]。TMA在战场物联网和目标自动跟踪等应用场景中具有广泛的应用前景,这些场景往往资源非常匮乏,如传感器和发射机需要尽可能保持低复杂度,且需要较高的移相精度。目前研究中产生干扰信号需要加入额外的节点,而利用TMA则可在原有通道中并联另一个通道,以便捷地实现干扰和信号的同时发送。尽管TMA作为一种先进的技术具有广泛的功能,但如何通过TMA实现隐蔽通信仍是一个开放的课题。

    在IoT等应用场景中,数据包长较短,尤其是在功率、频谱等资源有限的情况下,对通信传输速率等方面有较为严苛的限制。与长包相比,短包隐蔽通信使得窃听者所检测的数据样本是有限的,有利于增强通信的隐蔽性。文献[25]基于短包传输,对具有随机发送功率的隐蔽通信进行了研究,确定了最大化平均有效隐蔽吞吐量的最优发送功率和包长。文献[26]出一种基于毫米波的隐蔽通信系统,并研究了最大化有效隐蔽吞吐量的波束训练时间、训练功率和数据传输功率。此外,文献[27]分析了短包的隐蔽性能,同时考虑了传统的和截断的信道反转功率控制方案,以隐藏发送者的位置和通信行为。目前干扰辅助大部分通过额外的节点实现,因而需要更多的资源开销。共口径干扰在发送端传输信息的同时发送干扰信号,可进一步提升干扰控制能力,同时增强隐蔽性能。

    基于上述背景,本文研究了基于TMA的共口径干扰辅助隐蔽通信。首先提出并设计一种共口径干扰辅助的TMA系统架构,旨在最大化Bob方向上的信号天线增益,并抑制其余方向上的旁瓣。系统中采用了双通道架构,在发送隐蔽信息的同时,向非Bob方向发送人工噪声干扰。基于该场景,推导出隐蔽性约束和隐蔽吞吐量的闭合表达式。在此基础上,联合优化发送功率和包长,以最大化隐蔽吞吐量。通过仿真测试,发现了使隐蔽吞吐量最大化的最优包长,且所提出的优化方法相较于基准方案实现了更好的隐蔽性能。此外,还可观察出隐蔽吞吐量随着总功率的提高而增加。

    本文研究的场景如图1所示,Alice使用了一个具有M个天线的TMA系统。系统由两个通道组成:一个信道用于向Bob传输固定包长N的隐蔽信息,另一个信道用于向Bob的零空间方向发送人工噪声干扰。同时,Willie的目标是检测Alice是否发送信息。考虑AWGN信道,并且假设Willie和Bob均配置单天线。

    图 1  基于TMA的隐蔽通信系统架构

    本文提出的发射器架构基于TMA,如图1所示。由信号处理器生成的隐蔽信息和人工噪声经过数字-模拟转换器(Digital-to-Analog Converter, DAC)和混频器进行处理。随后,它们通过功率放大器(Power Amplifier, PA)进入射频开关。与传统的TMA系统不同,本系统在每个天线的后面连接两个射频开关。这允许在相同的频率下,在同一个阵列孔径内生成两个不同辐射模式的波束。具体而言,负责传输隐蔽信息的波束对Bob来说具有最高的增益,而在其他方向上具有明显较低的增益。相反,用于传输人工噪声的波束对Bob来说具有最低的增益,而在其他所有方向上都能达到更高的增益。传统的人工噪声源一般与发射机隔离,分布在空间中的不同位置,为此会增加许多额外开销,而本文所采用的方案有利于减少这类开销,同时通过波束形成设计减小噪声源对Bob的影响。TMA中的信号传输和人工噪声发射的阵列因子可分别表示为

    AFs(θ,t)=ej2πf0tMm=1Usm(t)ejkd(m1)sinθAFj(θ,t)=ej2πf0tMm=1Ujm(t)ejkd(m1)sinθ} (1)

    其中,k表示波数,f0是主频率,θ表示目标相对于Alice的方向,d是阵列元件的间距,假设d为半个波长。Usm(t)Ujm(t)分别表示信号传输和人工噪声发射的开关函数,可以分别表示为

    Usm(t)={1,tonm,s<t<toffm,s0,Ujm(t)={1,tonm,j<t<toffm,j0,} (2)

    其中tonm,s, toffm,stonm,j, toffm,j分别表示调制周期Tp中第m个阵元的开启和关闭时间。经过傅里叶变换后,Usm(t)Ujm(t)可以表示为

    Usm(t)=h=asm,hej2πhfptUjm(t)=h=ajm,hej2πhfpt} (3)

    其中,fp是调制频率,asm,hajm,hh次谐波的傅里叶级数系数,表达式为

    asm,h={sin[πh(toffm,stonm,s)]πhejπh(toffm,s+tonm,s),h0toffm,stonm,s,h=0,ajm,h={sin[πh(toffm,jtonm,j)]πhejπh(toffm,j+tonm,j),h0toffm,jtonm,j,h=0 (4)

    进一步地,信号传输和人工噪声发射的阵列因子可以表示为

    AFs(θ,t)=h=ej2π(f0+hfp)tMm=1asm,hejkd(m1)sinθAFj(θ,t)=h=ej2π(f0+hfp)tMm=1ajm,hejkd(m1)sinθ} (5)

    通过式(1)—式(5)可以看出,通过适当的开关时间设计可使得TMA可以产生两个方向的理想波束方向图。基于上述原理,可以分别设计用于信号传输和人工噪声的波束方向图。

    从Alice到Willie的信号可表示为

    H0:yaw[i]=PjdαawAFj(θw,t)xj[i]+naw[i]H1:yaw[i]=PadαawAFs(θw,t)xab[i]+PjdαawAFj(θw,t)xj[i]+naw[i]} (6)

    其中i = 1,2,···,N表示一个数据包中信号使用索引,naw[i]CN(0,σ2)表示观测到均值为0、方差为σ2的复高斯噪声,xj[i]CN(0,1)表示发送的人工噪声,xab[i]表示Alice发送到Bob的信号,零假设H0表示Alice和Bob之间没有传输,而H1表示Alice向Bob发送信号,daw是Alice和Willie之间的距离,Pa是信号发射功率,Pj是人工噪声的发射功率,θw是Willie相对于Alice的角度。Willie处的信噪比可以推导为

    γaw=PadαawAF2s(θw,t)PjdαawAF2j(θw,t)+σ2 (7)

    当满足一定约束条件ξ1ε[9],可认为传输对于Willie是隐蔽的,其中ε是预先确定的隐蔽容忍度,ξ表示Willie的最小检测错误概率。根据文献[25],ξ的下界可以写为ξ1D(P1P0)/D(P1P0)22表示Kullback-Leibler(KL)散度[28],其中P1=Mi=1f(yaw[i]|H1)P0=Mi=1f(yaw[i]|H0)分别表示在H1H0下Willie的观测样本概率分布,其中f(yaw[i]|H1)=CN(0,PadαabAF2s(θb,t)+σ2)f(yaw[i]|H0)=CN(0,σ2)。为了确保更严格的隐蔽性,采用了更严格的约束条件D(P1||P0)/D(P1||P0)22ε,进一步地,KL散度可推导为

    D(P1P0)=yf(yaw|H1)lnf(yaw|H1)f(yaw|H0)dx=Nex2PadαawAF2s(θw,t)+PjdαawAF2j(θw,t)+σ2π(PadαawAF2s(θw,t)+PjdαawAF2j(θw,t)+σ2)×ln(π(PjdαawAF2j(θw,t)+σ2)π(PadαawAF2s(θw,t)+PjdαawAF2j(θw,t)+σ2)×ex2PadαawAF2s(θw,t)+PjdαawAF2j(θw,t)+σ2+x2PjdαawAF2j(θw,t)+σ2)dx=N(lnPjdαawAF2j(θw,t)+σ2PadαawAF2s(θw,t)+PjdαawAF2j(θw,t)+σ2+(1PjdαawAF2j(θw,t)+σ21PadαawAF2s(θw,t)+PjdαawAF2j(θw,t)+σ2)x2)×ex2PadαawAF2s(θw,t)+PjdαawAF2j(θw,t)+σ2π(PadαawAF2s(θw,t)+PjdαawAF2j(θw,t)+σ2)dx=N(PadαawAF2s(θw,t)PjdαawAF2j(θw,t)+σ2ln(1+PadαawAF2s(θw,t)PjdαawAF2j(θw,t)+σ2))aN2(PadαawAF2s(θw,t)PjdαawAF2j(θw,t)+σ2)2 (8)

    式中a表示条件:ln(1+x)≥xx2, x≥0。

    那么,在所考虑的模型中,隐蔽性约束条件可进一步放缩为

    N2PadαawAF2s(θw,t)PjdαawAF2j(θw,t)+σ2ε (9)

    当Alice向Bob传输时,Bob接收到的信号可以表示为

    yab[i]=PadαabAFs(θb,t)xab[i]+PjdαabAFj(θb,t)xj[i]+nab[i] (10)

    其中,nab[i]CN(0,1)表示AWGN,dab是Alice和Bob之间的距离,θb是Bob相对于Alice的角度。随后,Bob处的信噪比可写为

    γab=PadαabAF2s(θb,t)PjdαabAF2j(θb,t)+σ2 (11)

    其中,σ2是噪声功率。

    当数据包长有限时,译码错误不可忽略,吞吐量可写为[29]

    ρ=NR(1δ) (12)

    其中,R表示信道编码速率,短包通信的误包率δ可以表示为[30]

    δ=Q(ln2N(log2(1+γab)R)1(γab+1)2) (13)

    其中,Q(x)=x(1/2π)et2/2dtR表示信道编码速率。

    本文采用隐蔽吞吐量衡量系统的隐蔽通信性能。隐蔽吞吐量定义为在满足隐蔽约束的条件下,Alice每次能可靠地传输给Bob的信息量,其表达式可写为

    ρ=NR(1δ), s.tN2PadαawAF2s(θw)PjdαawAF2j(θw)+σ2ε (14)

    本节描述了基于TMA的发射机方向图优化,并借助人工噪声实现隐蔽通信。在此基础上,还提出了一种隐蔽吞吐量优化方法。

    通过优化式(5)中的开关时间,可以实现TMA的理想方向图。为了确保结果符合期望的要求,在算法中设置了优化目标。本研究选择了布谷鸟搜索(Cuckoo Search, CS)算法,因为与粒子群优化算法和遗传算法等方法相比,它具有更高的计算精度以及且相对较低的复杂度[31]。本文中给出的算法步骤如算法1所示。

    表 1  基于CS算法的TMA方向图优化程序
     初始化:使用随机实数来生成s个巢穴的初始种群xi(i = 1, 2, ···,
     S),其中xi表示切换序列。
     适应度计算:将每个宿主巢穴代入适合度函数fi,计算适合度值。
     当t<K时:通过Lévy飞行随机选择一个巢穴,并评估其适应度值;
          随机选择一个巢;
          如果fi>fo,则用新解代替o
          一部分(P[0,1])较差的巢被放弃,并建立新的巢;
          保留最佳解决方案;
          对解决方案进行排序,找出当前最佳解决方案;
     得到最优的开关序列。
     结束
    下载: 导出CSV 
    | 显示表格

    首先初始化开关时间序列,经过调整后输入到适应度函数中,在迭代过程中计算它们的适应度值。当迭代次数低于指定值K时,利用Lévy飞行机制在评估适应度的同时探索解空间。在这个搜索过程中,任何适应度较低的巢都会被随机替换。随着迭代的进行,不良解被丢弃,新的解由算法生成。最终,最佳解决方案被存储和评估。假设我们使用第h个谐波进行波束成形,那么第i步的适应度函数可以表示为

    fi=c1(ψmax (15)

    其中, \psi _{\text{d}}^{i,h} \psi _{\text{d}}^{} 分别表示 {\text{A}}{{\text{F}}_{\text{s}}}\left( {\theta ,t} \right) 的优化和期望的旁瓣衰减(Side-Lobe Level, SLL), \theta _i^{\text{s}} \theta _i^{\text{j}} 分别是 {\text{A}}{{\text{F}}_{\text{s}}}\left( {\theta ,t} \right) {\text{A}}{{\text{F}}_{\text{j}}}\left( {\theta ,t} \right) 的优化波束指向方向, \varpi _{\text{d}}^{\mathrm{j}} 表示 {\text{A}}{{\text{F}}_{\text{j}}}\left( {\theta ,t} \right) 的期望零陷水平, \varpi _{\text{d}}^{\max } 表示除 \theta _i^{\text{j}} 之外的方向上 {\text{A}}{{\text{F}}_{\text{j}}}\left( {\theta ,t} \right) 的预期增益。 {c_1} , {c_2} , {c_3} , {c_4} , {c_5} 分别是权重因子,它们的和为1。

    考虑到 {N_{\min }} \le N \le {N_{\max }} ,假设总发射功率为P以及Alice到Bob的传输功率为Pa,则最大化隐蔽吞吐量的优化问题可以表示为

    \left. \begin{aligned} & {\mathop {\max }\limits_{N,{P_{\text{a}}}} \;\;\,\rho } \\ & {{\mathrm{s.t}}.\;\;\,\frac{{\sqrt N }}{2}\frac{{{P_{\text{a}}}d_{{\text{aw}}}^{ - \alpha }{\text{AF}}_{\text{s}}^{\text{2}}({\theta _{\text{w}}},t)}}{{{P_{\text{j}}}d_{{\text{aw}}}^{ - \alpha }{\text{AF}}_{\text{j}}^{\text{2}}({\theta _{\text{w}}},t) + {\sigma ^2}}} \le \varepsilon } \\ & {\quad \quad {P_{\text{a}}} > 0,{P_{\text{j}}} \ge 0,P = {P_{\text{j}}} + {P_{\text{a}}}} \\ & {\quad \quad {N_{\min }} \le N \le {N_{\max }},N \in {\mathbb{N}^ + }} \end{aligned} \right\} (16)

    推论1 对于给定的包长N,最优发射功率 P_{\text{a}}^\dagger 应设为满足隐蔽约束时发射功率的最大值,可表示为

    P_{\text{a}}^\dagger = \frac{{P{\text{AF}}_{\text{s}}^{\text{2}}\left( {{\theta _{\text{w}}},t} \right) + {{{\sigma ^2}} \mathord{\left/ {\vphantom {{{\sigma ^2}} {d_{{\text{aw}}}^{ - \alpha }}}} \right. } {d_{{\text{aw}}}^{ - \alpha }}}}}{{({{\sqrt N } \mathord{\left/ {\vphantom {{\sqrt N } {2\varepsilon }}} \right. } {2\varepsilon }}){\text{AF}}_{\text{s}}^{\text{2}}({\theta _{\text{w}}},t) + {\text{AF}}_{\text{j}}^{\text{2}}({\theta _{\text{w}}},t)}} (17)

    证明 参考式(16),在最优的N下,下式的左侧关于Pa单调递增,则较大的Pa值会提升隐蔽性能

    \frac{{\sqrt N }}{2}\frac{{{P_{\text{a}}}d_{{\text{aw}}}^{ - \alpha }{\text{AF}}_{\text{s}}^{\text{2}}({\theta _{\text{w}}},t)}}{{{P_{\text{j}}}d_{{\text{aw}}}^{ - \alpha }{\text{AF}}_{\text{j}}^{\text{2}}({\theta _{\text{w}}},t) + {\sigma ^2}}} \le \varepsilon (18)

    对不等号左侧的方程关于Pa求导将得到

    \begin{split} & \frac{{d\left(\dfrac{{\sqrt N {P_{\text{a}}}d_{{\text{aw}}}^{ - \alpha }{\text{AF}}_{\text{s}}^{\text{2}}({\theta _{\text{w}}},t)}}{{2(P - {P_{\text{a}}})d_{{\text{aw}}}^{ - \alpha }{\text{AF}}_{\text{j}}^2({\theta _{\text{w}}},t) + {\sigma ^2}}}\right)}}{{d({P_{\text{a}}})}} \\ & \quad = \frac{{d_{{\text{aw}}}^{ - \alpha }{\text{AF}}_{\text{s}}^{\text{2}}({\theta _{\text{w}}},t)((P - {P_{\text{a}}})d_{{\text{aw}}}^{ - \alpha }{\text{AF}}_{\text{j}}^{\text{2}}({\theta _{\text{w}}},t) + {\sigma ^2}) + {P_{\text{a}}}d_{{\text{aw}}}^{ - 2\alpha }{\text{AF}}_{\text{s}}^{\text{2}}({\theta _{\text{w}}},t){\text{AF}}_{\text{j}}^{\text{4}}({\theta _{\text{w}}},t)}}{{{{((P - {P_{\text{a}}})d_{{\text{aw}}}^{ - \alpha }{\text{AF}}_{\text{j}}^{\text{2}}{\text{(}}{\theta _{\text{w}}},t) + {\sigma ^2})}^2}}} > 0 \end{split} (19)

    由式(19)可知,式(18)不等号左侧的方程关于Pa的导数大于0,因而其关于Pa单调递增,证毕。

    对于优化问题式(16),存在最优发射功率 P_{\text{a}}^\dagger ,因此可进一步写为

    \left. \begin{aligned} & \mathop {\max }\limits_{N,{P_{\text{a}}}} \;\;\,\rho \\ & \,{\text{s}}.{\text{t}}.\;\;{P_{\text{a}}} = P_{\text{a}}^\dagger ,{P_{\text{j}}} = P - {P_{\text{a}}} \\ &\quad \quad {N_{\min }} \le N \le {N_{\max }},N \in {\mathbb{N}^ + } \end{aligned} \right\} (20)

    由式(20)可知,通过一维搜索得到最优包长,将最优包长代入式(21)可获得最优发射功率 P_{\text{a}}^\dagger 。相应地,将最优包长和最优发射功率 P_{\text{a}}^\dagger 代入式(18)得到最大隐蔽吞吐量。

    本节对所提出模型的性能进行了仿真验证,表1中给出了所有仿真参数。

    表 1  仿真参数设置
    天线数 迭代次数 谐波级数 巢数 信号旁瓣 干扰旁瓣 Bob方向 Willie方向 信道编码速率
    M=12 K=1 000 h=1 S=25 –40 dB –25 dB –20° –5° R=0.1 BPCU
    dab daw dbw 总发射功率 噪声功率 路径衰减 最大包长 最小包长
    40 m 10 m 10 m P=–20 dBm σ2=–80 dBm α=3 Nmax=800 Nmin=100
    下载: 导出CSV 
    | 显示表格

    仿真过程中,首先验证了TMA方向图的优化。CS算法的迭代次数K设置为1000,天线数量M设置为12。谐波级数h=1,CS算法中主巢的数量设置为S=25。 {\text{A}}{{\text{F}}_{\text{s}}}\left( {\theta ,t} \right) 的期望SLL \psi _{\text{d}}^{i,h} 设置为–40 dB,期望零陷水平设置为 \psi _{\text{d}}^{} =–25 dB。预期增益 \varpi _{\text{d}}^{\max } 设置为归一化值1。 \theta _i^{\text{s}} \theta _i^{\text{j}} 分别设置为–20°和–5°。根据文献[30],对于系统隐蔽吞吐量的优化考虑以下参数:路径衰减为α=3,Alice和Bob之间的距离、Alice和Willie之间的距离以及Bob和Willie之间的距离分别为dab=40 m, daw=10 m和dbw=10 m。噪声功率设置为σ2=–80 dBm,总发射功率为P=–20 dBm,包长的最小值和最大值分别为Nmin=100和Nmax=800,信道编码速率R=0.1 BPCU (比特每信道使用)。

    图2(a)图2(b)展示了优化后得到的信号方向图和人工噪声方向图开关时间,将开关时间代入式(1)可以得到与之对应的方向图优化结果。图2(c)展示了TMA方向图的优化结果,可以观察到优化后的信号传输阵列因子 {\text{A}}{{\text{F}}_{\text{s}}}\left( {\theta ,t} \right) 和人工噪声阵列因子 {\text{A}}{{\text{F}}_{\text{j}}}\left( {\theta ,t} \right) 满足期望的要求。 {\text{A}}{{\text{F}}_{\text{s}}}\left( {\theta ,t} \right) 在指向Bob的方向上具有最大增益,而 {\text{A}}{{\text{F}}_{\text{j}}}\left( {\theta ,t} \right) 在Bob方向上的增益非常低。

    图 2  开关时间优化结果与TMA方向图

    图3(a)表明,最大隐蔽吞吐量随着N值的变化呈现先增加后减小的趋势。存在一个最佳的N值最大化有效隐蔽吞吐量。此外,可以观察到引入人工噪声可以改善隐蔽性能,相比基准方案有所提升。再次,随着发射功率的增加,性能逐渐提高。图3(b)中的仿真结果说明了隐蔽吞吐量与ε的关系。可以观察到,随着ε的增加,隐蔽性能得到改善。此外,随着总发射功率P的增加,本文所提出的基于TMA的干扰方案在所有情况下的隐蔽吞吐量随之增大,超过了基准方案。图3(c)显示了当daw增加时,最大隐蔽吞吐量逐渐改善。与基准方案相比,引入人工噪声的方案性能更好。此外,尽管存在隐蔽性能的上限,随着发射功率的增加,隐蔽性能逐渐提高。本文进一步研究了dab对隐蔽性能的影响。如图3(d)所示,可以观察到随着dab的增加,引入人工噪声的方案性能优于基准方案。最后,本文研究了总发射功率对隐蔽性能的影响,如图3(e)所示。可以发现,随着总发射功率P的增加,ρ也会增大。相比基准方案,引入人工噪声的方案在性能方面显著改善,通过观察不同N, ε, daw, dab以及P变化时最大隐蔽吞吐量的变化可以证明提升总发射功率和隐蔽容忍度的有助于提高最大隐蔽吞吐量。此外,图3(b)图3(c)图3(e)显示ρ随着隐蔽容忍值εdaw增加到一定程度后保持不变,这是因为随着εdaw的增加,最优包长逐渐变大,同时误包率逐渐减小为0,但由于存在上限Nmax,在R一定的情况下ρ不再增大。图3(d)显示ρdab的增加在一定程度范围不变后再减小,这是由于合法路径的路径损耗增大导致误包率逐渐变大造成的。

    图 3  不同参数对最大隐蔽吞吐量的影响

    本文将TMA用于短包隐蔽通信,通过设计共孔径人工噪声来提升隐蔽性能,采用CS算法对TMA进行优化设计,以有效抑制Bob零空间的传输信号的天线增益,同时最大化除Bob之外方向上的干扰信号增益。本文推导出用于表征基于TMA共孔径干扰辅助的短包通信隐蔽性约束的解析式,并分析和确定了最佳的发射功率和包长,以最大化隐蔽吞吐量。仿真结果表明,与基准方案相比,优化后的包长提升了最大隐蔽吞吐量,突显了所提方案的有效性。此外,本文观察到随着发射功率的增加,最大隐蔽吞吐量会下降,但通过增加隐蔽容忍度可以进一步改善。未来的工作将探索和分析更一般的信道模型对基于TMA系统的短包隐蔽通信的影响,并研究不同的时间调制架构以提高隐蔽性能,以面向通感一体化[32]等场景。

  • 图  1  具有10 任务和3 处理器的任务以及计算消耗

    图  2  4种算法对图1中DAG1产生的调度结果

    图  3  4种算法对不同任务数量的DAG的调度结果

    图  4  4种算法对不同ccr的DAG的调度结果

    图  5  4种算法对不同处理器数量的DAG的调度结果

    图  6  4种算法对不同矩阵尺寸的高斯消元应用的调度结果

    图  7  4种算法对不同任务数量的蒙太奇应用的调度结果

    表  1  计算消耗

    任务p1p2p3
    t16454
    t2131234
    t3452334
    t45334
    t531642
    t623547
    t7995634
    t8541344
    t9751387
    t10843237
    下载: 导出CSV

    表  2  图 1 中 DAG1 的 IPCM

    任务p1p2p3
    t1218242214
    t2156102177
    t3196174176
    t4130123129
    t5127106166
    t6178144162
    t7195120108
    t814977118
    t920477161
    t10843237
    下载: 导出CSV

    表  3  图 1 中 DAG1 的各算法任务优先级列表

    任务{\text{ran}}{{\text{k}}_\mu }{\text{ran}}{{\text{k}}_{{\text{OCT}}}}{\text{ran}}{{\text{k}}_{{\text{PCM}}}}{\text{ran}}{{\text{k}}_{{\text{IPCM}}}}
    t1325.0114.0224.0224.7
    t2247.080.3137.3145.0
    t3189.077.0182.0182.0
    t4211.368.3145.7127.3
    t5228.767.7128.7133.0
    t6212.078.7162.7161.3
    t7146.044.3122.7141.0
    t8119.044.097.7114.7
    t9174.351.0120.3147.3
    t1051.0051.051.0
    下载: 导出CSV

    表  4  不同方法的SLR对比(%)

    PEFTPPTSIPPOSS with EFTOCT
    更好57.5035.9016.30
    相同13.4029.9041.70
    更差29.1034.1042.00
    平均降低1.750.13–0.48
    下载: 导出CSV
    算法1 IPPOSS算法
     (1) 从出口任务到入口任务递归地为每个任务计算{\text{IPCM}}{\text{OCT}}
     (2) 计算所有任务的 {\text{ran}}{{\text{k}}_{{\text{IPCM}}}}
     (3) 更新就绪列表
     (4) while 就绪列表非空 do
     (5)   {{\mathbf{t}}_i} \leftarrow 就绪列表中具有最高 {\text{ran}}{{\text{k}}_{{\text{IPCM}}}}({{\mathbf{t}}_i})的任务
     (6)   for {{\mathbf{p}}_m} \in {\mathbf{P}}
     (7)     使用基于插入的策略计算{\text{EFT(}}{{\mathbf{t}}_i},{{\mathbf{p}}_m}{\text{)}}
     (8)     计算 {\text{EF}}{{\text{T}}_{{\text{OCT}}}}({{\mathbf{t}}_i},{{\mathbf{p}}_m})
     (9)   end for
     (10)   为{{\mathbf{t}}_i}选择可以最小化 {\text{EF}}{{\text{T}}_{{\text{OCT}}}}({{\mathbf{t}}_i},{{\mathbf{p}}_m}) {{\mathbf{p}}_m}
     (11)   更新就绪列表
     (12) end while
    下载: 导出CSV

    表  5  4种算法的调度长度的成对比较(%)

    IPPOSSPPTSPEFTHEFT
    IPPOSS更好
    相同
    更差
    *44.9
    32.4
    22.7
    58.8
    26.0
    15.2
    66.7
    9.7
    23.5
    PPTS更好
    相同
    更差
    22.7
    32.4
    44.9
    *57.3
    11.5
    31.1
    63.5
    9.2
    27.3
    PEFT更好
    相同
    更差
    15.2
    26.0
    58.8
    31.1
    11.5
    57.3
    *54.2
    5.0
    40.8
    HEFT更好
    相同
    更差
    23.5
    9.7
    66.7
    27.3
    9.2
    63.5
    40.8
    5.0
    54.2
    *
    下载: 导出CSV
  • [1] SINNEN O and SOUSA L A. Communication contention in task scheduling[J]. IEEE Transactions on Parallel and Distributed Systems, 2005, 16(6): 503–515. doi: 10.1109/TPDS.2005.64
    [2] GAREY M R, JOHNSON D S, and STOCKMEYER L. Some simplified NP-complete problems[C]. The 6th Annual ACM Symposium on Theory of Computing, Seattle, USA, 1974: 47–63.
    [3] ULLMAN J D. NP-complete scheduling problems[J]. Journal of Computer and System Sciences, 1975, 10(3): 384–393. doi: 10.1016/S0022-0000(75)80008-0
    [4] PAPADIMITRIOU C H and YANNAKAKIS M. Scheduling interval-ordered tasks[J]. SIAM Journal on Computing, 1979, 8(3): 405–409. doi: 10.1137/0208031
    [5] AGUILAR J and GELENBE E. Task assignment and transaction clustering heuristics for distributed systems[J]. Information Sciences, 1997, 97(1/2): 199–219. doi: 10.1016/S0020-0255(96)00178-8
    [6] HUANG Kuochan, GU D S, LIU H C, et al. Task clustering heuristics for efficient execution time reduction in workflow scheduling[J]. Journal of Computers, 2017, 28(1): 43–56. doi: 10.3966/199115592017022801004
    [7] TIAN Qiao, LI Jingmei, XUE Di, et al. A hybrid task scheduling algorithm based on task clustering[J]. Mobile Networks and Applications, 2020, 25(4): 1518–1527. doi: 10.1007/s11036-019-01356-x
    [8] SULAIMAN M, HALIM Z, WAQAS M, et al. A hybrid list-based task scheduling scheme for heterogeneous computing[J]. The Journal of Supercomputing, 2021, 77(9): 10252–10288. doi: 10.1007/s11227-021-03685-9
    [9] AHMAD W and ALAM B. An efficient list scheduling algorithm with task duplication for scientific big data workflow in heterogeneous computing environments[J]. Concurrency and Computation:Practice and Experience, 2021, 33(5): e5987. doi: 10.1002/cpe.5987
    [10] HAGRAS T, ATEF A, and MAHDY Y B. Greening duplication-based dependent-tasks scheduling on heterogeneous large-scale computing platforms[J]. Journal of Grid Computing, 2021, 19(1): 13. doi: 10.1007/s10723-021-09554-2
    [11] TOPCUOGLU H, HARIRI S, and WU Minyou. Performance-effective and low-complexity task scheduling for heterogeneous computing[J]. IEEE Transactions on Parallel and Distributed Systems, 2002, 13(3): 260–274. doi: 10.1109/71.993206
    [12] BITTENCOURT L F, SAKELLARIOU R, and MADEIRA E R M. DAG scheduling using a lookahead variant of the heterogeneous earliest finish time algorithm[C]. The 2010 18th Euromicro Conference on Parallel, Distributed and Network-Based Processing, Pisa, Italy, 2010: 27–34.
    [13] ARABNEJAD H and BARBOSA J G. List scheduling algorithm for heterogeneous systems by an optimistic cost table[J]. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(3): 682–694. doi: 10.1109/TPDS.2013.57
    [14] DJIGAL H, FENG Jun, and LU Jiamin. Task scheduling for heterogeneous computing using a predict cost matrix[C]. The 48th International Conference on Parallel Processing: Workshops, Kyoto, Japan, 2019: 25.
    [15] ZHAO Yi, CAO Suzhi, and YAN Lei. List scheduling algorithm based on pre-scheduling for heterogeneous computing[C]. 2019 IEEE Intl Conf on Parallel & Distributed Processing with Applications, Big Data & Cloud Computing, Sustainable Computing & Communications, Social Computing & Networking, Xiamen, China, 2019: 588–595.
    [16] IJAZ S and MUNIR E U. MOPT: List-based heuristic for scheduling workflows in cloud environment[J]. The Journal of Supercomputing, 2019, 75(7): 3740–3768. doi: 10.1007/s11227-018-2726-6
    [17] DOROSTKAR F and MIRZAKUCHAKI S. List scheduling for heterogeneous computing systems introducing a performance-effective definition for critical path[C]. The 2019 9th International Conference on Computer and Knowledge Engineering, Mashhad, Iran, 2019: 356–362.
    [18] JIANG Chao, WANG Jinlin, and YE Xiaozhou. PVBTS: A novel task scheduling algorithm for heterogeneous computing platforms[J]. International Journal of Innovative Computing, Information and Control, 2020, 16(2): 701–713. doi: 10.24507/ijicic.16.02.701
    [19] GHOLAMI H and ZAKERIAN R. A list-based heuristic algorithm for static task scheduling in heterogeneous distributed computing systems[C]. The 2020 6th International Conference on Web Research, Tehran, Iran, 2020: 21–26.
    [20] HU Wei, GAN Yu, LV Xiangyu, et al. A improved list heuristic scheduling algorithm for heterogeneous computing systems[C]. 2020 IEEE International Conference on Systems, Man, and Cybernetics, Toronto, Canada, 2020: 1111–1116.
    [21] HU Wei, GAN Yu, WEN Yuan, et al. An improved heterogeneous dynamic list schedule algorithm[C]. The 20th International Conference on Algorithms and Architectures for Parallel Processing, New York City, USA, 2020: 159–173.
    [22] DJIGAL H, FENG Jun, LU Jiamin, et al. IPPTS: An efficient algorithm for scientific workflow scheduling in heterogeneous computing systems[J]. IEEE Transactions on Parallel and Distributed Systems, 2021, 32(5): 1057–1071. doi: 10.1109/TPDS.2020.3041829
    [23] SHI Zhiao, JEANNOT E, and DONGARRA J J. Robust task scheduling in non-deterministic heterogeneous computing systems[C]. 2006 IEEE International Conference on Cluster Computing, Barcelona, Spain, 2006: 1–10.
    [24] frs69wq. DAGGEN: A synthetic task graph generator[EB/OL].https://github.com/frs69wq/daggen, 2021.
    [25] AMOURA A K, BAMPIS E, and KONIG J C. Scheduling algorithms for parallel Gaussian elimination with communication costs[J]. IEEE Transactions on Parallel and Distributed Systems, 1998, 9(7): 679–686. doi: 10.1109/71.707547
    [26] JIANG Qingye, LEE Y C, ARENAZ M, et al. Optimizing scientific workflows in the cloud: A montage example[C]. The 2014 IEEE/ACM 7th International Conference on Utility and Cloud Computing, London, UK, 2014: 517–522.
  • 加载中
图(7) / 表(6)
计量
  • 文章访问数:  959
  • HTML全文浏览量:  595
  • PDF下载量:  134
  • 被引次数: 0
出版历程
  • 收稿日期:  2021-10-21
  • 修回日期:  2022-01-12
  • 录用日期:  2022-01-20
  • 网络出版日期:  2022-02-03
  • 刊出日期:  2023-01-17

目录

/

返回文章
返回