A List Scheduling Algorithm for Heterogeneous Computing Systems Using Improved Predict Cost Matrix for Task Prioritizing
-
摘要: 异构计算系统执行应用效率的提高高度依赖有效的调度算法。该文提出一种新的列表调度算法,称为改进的预测优先任务和乐观处理器选择调度(IPPOSS)。通过在任务优先级排序阶段引入任务的后向预测成本,来减少调度长度。与现有工作相比,该文使用改进预测成本矩阵(IPCM),更合理地进行了任务优先级排序,从而在处理器选择阶段获得了更好的解,并保持2次时间复杂度。IPCM考虑了任务优先级排序阶段的各种计算、通信因素,比预测优先任务调度(PPTS)提出的预测成本矩阵(PCM)更容易获得合理的优先级列表。随机生成应用的有向无环图(DAG)和真实世界应用的DAG的实验结果分析表明,IPPOSS的性能优于相关算法。Abstract: The improvement of application efficiency of heterogeneous computing systems is highly dependent on effective scheduling algorithms. A new list scheduling algorithm called Improved Predict Priority and Optimistic processor Selection Scheduling (IPPOSS) is proposed by this paper. By introducing the backward prediction cost of tasks in task prioritizing phase, the scheduling length is reduced. Compared with the existing work, an Improved Predict Cost Matrix (IPCM) is adopted to prioritize tasks more reasonably and a better solution in processor selection phase when keeping quadratic time complexity is obtain. IPCM, which considers various calculation and communication factors in the task prioritization stage, is easier to obtain a reasonable priority list than Predict Cost Matrix (PCM) proposed by Predict Priority Task Scheduling (PPTS). That the performance of IPPOSS is better than related algorithms is shown by the analysis of the experimental results of randomly generated application Directed Acyclic Graphs (DAGs) and real-world application DAGs.
-
Key words:
- Heterogeneous systems /
- Parallel computing /
- List scheduling /
- Static scheduling
-
1. 引言
随着无线通信设备的普及,确保通信安全变得愈发关键,特别是随着物联网(Internet of Things, IoT)在各个领域的应用[1],使得通信安全成为一个广受关注的问题。传统的无线通信安全研究主要侧重于通过加密[2,3]和物理层安全(Physical Layer Security, PLS)[4–6]来保护通信内容免受窃听。然而,在某些情况下,通信行为的隐藏也非常重要,这就需要进行私密消息的隐蔽传输。例如,在战场上的军事侦察信号、公共场所中的个人隐私信号传输以及机密的金融数据传输等场景中,不仅需要确保传输信息的安全性,还需要确保传输行为本身的隐蔽性,由此隐蔽通信应运而生。隐蔽通信的历史可以追溯到上世纪初兴起的扩频通信[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方向发送人工噪声干扰。基于该场景,推导出隐蔽性约束和隐蔽吞吐量的闭合表达式。在此基础上,联合优化发送功率和包长,以最大化隐蔽吞吐量。通过仿真测试,发现了使隐蔽吞吐量最大化的最优包长,且所提出的优化方法相较于基准方案实现了更好的隐蔽性能。此外,还可观察出隐蔽吞吐量随着总功率的提高而增加。
2. 系统模型
本文研究的场景如图1所示,Alice使用了一个具有M个天线的TMA系统。系统由两个通道组成:一个信道用于向Bob传输固定包长N的隐蔽信息,另一个信道用于向Bob的零空间方向发送人工噪声干扰。同时,Willie的目标是检测Alice是否发送信息。考虑AWGN信道,并且假设Willie和Bob均配置单天线。
2.1 共口径干扰辅助发射机
本文提出的发射器架构基于TMA,如图1所示。由信号处理器生成的隐蔽信息和人工噪声经过数字-模拟转换器(Digital-to-Analog Converter, DAC)和混频器进行处理。随后,它们通过功率放大器(Power Amplifier, PA)进入射频开关。与传统的TMA系统不同,本系统在每个天线的后面连接两个射频开关。这允许在相同的频率下,在同一个阵列孔径内生成两个不同辐射模式的波束。具体而言,负责传输隐蔽信息的波束对Bob来说具有最高的增益,而在其他方向上具有明显较低的增益。相反,用于传输人工噪声的波束对Bob来说具有最低的增益,而在其他所有方向上都能达到更高的增益。传统的人工噪声源一般与发射机隔离,分布在空间中的不同位置,为此会增加许多额外开销,而本文所采用的方案有利于减少这类开销,同时通过波束形成设计减小噪声源对Bob的影响。TMA中的信号传输和人工噪声发射的阵列因子可分别表示为
AFs(θ,t)=ej2πf0tM∑m=1Usm(t)ejkd(m−1)sinθAFj(θ,t)=ej2πf0tM∑m=1Ujm(t)ejkd(m−1)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,s和tonm,j, toffm,j分别表示调制周期Tp中第m个阵元的开启和关闭时间。经过傅里叶变换后,Usm(t)和Ujm(t)可以表示为
Usm(t)=∞∑h=−∞asm,hej2πhfptUjm(t)=∞∑h=−∞ajm,hej2πhfpt} (3) 其中,fp是调制频率,asm,h和ajm,h是h次谐波的傅里叶级数系数,表达式为
asm,h={sin[πh(toffm,s−tonm,s)]πhe−jπh(toffm,s+tonm,s),h≠0toffm,s−tonm,s,h=0,ajm,h={sin[πh(toffm,j−tonm,j)]πhe−jπh(toffm,j+tonm,j),h≠0toffm,j−tonm,j,h=0 (4) 进一步地,信号传输和人工噪声发射的阵列因子可以表示为
AFs(θ,t)=∞∑h=−∞ej2π(f0+hfp)tM∑m=1asm,hejkd(m−1)sinθAFj(θ,t)=∞∑h=−∞ej2π(f0+hfp)tM∑m=1ajm,hejkd(m−1)sinθ} (5) 通过式(1)—式(5)可以看出,通过适当的开关时间设计可使得TMA可以产生两个方向的理想波束方向图。基于上述原理,可以分别设计用于信号传输和人工噪声的波束方向图。
2.2 Willie的检测性能
从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],ξ∗的下界可以写为ξ∗≥1−√D(P1‖P0)/D(P1‖P0)22表示Kullback-Leibler(KL)散度[28],其中P1=∏Mi=1f(yaw[i]|H1)和P0=∏Mi=1f(yaw[i]|H0)分别表示在H1和H0下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(P1‖P0)=∫yf(yaw|H1)lnf(yaw|H1)f(yaw|H0)dx=N∞∫−∞e−x2Pad−α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)×e−x2Pad−α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)+σ2−1Pad−αawAF2s(θw,t)+Pjd−αawAF2j(θw,t)+σ2)x2)×e−x2Pad−α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)+σ2−ln(1+Pad−αawAF2s(θw,t)Pjd−αawAF2j(θw,t)+σ2))a≤N2(Pad−αawAF2s(θw,t)Pjd−αawAF2j(θw,t)+σ2)2 (8) 式中a表示条件:ln(1+x)≥x–x2, x≥0。
那么,在所考虑的模型中,隐蔽性约束条件可进一步放缩为
√N2Pad−αawAF2s(θw,t)Pjd−αawAF2j(θw,t)+σ2≤ε (9) 2.3 合法传输
当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(ln2√N(log2(1+γab)−R)√1−(γab+1)−2) (13) 其中,Q(x)=∫∞x(1/√2π)e−t2/2dt,R表示信道编码速率。
本文采用隐蔽吞吐量衡量系统的隐蔽通信性能。隐蔽吞吐量定义为在满足隐蔽约束的条件下,Alice每次能可靠地传输给Bob的信息量,其表达式可写为
ρ=NR(1−δ), s.t. √N2Pad−αawAF2s(θw)Pjd−αawAF2j(θw)+σ2≤ε (14) 3. 优化和问题描述
本节描述了基于TMA的发射机方向图优化,并借助人工噪声实现隐蔽通信。在此基础上,还提出了一种隐蔽吞吐量优化方法。
3.1 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])较差的巢被放弃,并建立新的巢; 保留最佳解决方案; 对解决方案进行排序,找出当前最佳解决方案; 得到最优的开关序列。 结束 首先初始化开关时间序列,经过调整后输入到适应度函数中,在迭代过程中计算它们的适应度值。当迭代次数低于指定值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。
3.2 隐蔽吞吐量优化
考虑到 {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)得到最大隐蔽吞吐量。
4. 仿真结果
4.1 参数设置
本节对所提出模型的性能进行了仿真验证,表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 仿真过程中,首先验证了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 (比特每信道使用)。
4.2 TMA方向图优化
图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方向上的增益非常低。
4.3 最大隐蔽吞吐量优化
图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的增加在一定程度范围不变后再减小,这是由于合法路径的路径损耗增大导致误包率逐渐变大造成的。
5. 结束语
本文将TMA用于短包隐蔽通信,通过设计共孔径人工噪声来提升隐蔽性能,采用CS算法对TMA进行优化设计,以有效抑制Bob零空间的传输信号的天线增益,同时最大化除Bob之外方向上的干扰信号增益。本文推导出用于表征基于TMA共孔径干扰辅助的短包通信隐蔽性约束的解析式,并分析和确定了最佳的发射功率和包长,以最大化隐蔽吞吐量。仿真结果表明,与基准方案相比,优化后的包长提升了最大隐蔽吞吐量,突显了所提方案的有效性。此外,本文观察到随着发射功率的增加,最大隐蔽吞吐量会下降,但通过增加隐蔽容忍度可以进一步改善。未来的工作将探索和分析更一般的信道模型对基于TMA系统的短包隐蔽通信的影响,并研究不同的时间调制架构以提高隐蔽性能,以面向通感一体化[32]等场景。
-
表 1 计算消耗
任务 p1 p2 p3 t1 6 45 4 t2 13 12 34 t3 45 23 34 t4 5 33 4 t5 3 16 42 t6 23 54 7 t7 99 56 34 t8 54 13 44 t9 75 13 87 t10 84 32 37 表 2 图 1 中 DAG1 的 IPCM
任务 p1 p2 p3 t1 218 242 214 t2 156 102 177 t3 196 174 176 t4 130 123 129 t5 127 106 166 t6 178 144 162 t7 195 120 108 t8 149 77 118 t9 204 77 161 t10 84 32 37 表 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}}}} t1 325.0 114.0 224.0 224.7 t2 247.0 80.3 137.3 145.0 t3 189.0 77.0 182.0 182.0 t4 211.3 68.3 145.7 127.3 t5 228.7 67.7 128.7 133.0 t6 212.0 78.7 162.7 161.3 t7 146.0 44.3 122.7 141.0 t8 119.0 44.0 97.7 114.7 t9 174.3 51.0 120.3 147.3 t10 51.0 0 51.0 51.0 表 4 不同方法的SLR对比(%)
PEFT PPTS IPPOSS with EFTOCT 更好 57.50 35.90 16.30 相同 13.40 29.90 41.70 更差 29.10 34.10 42.00 平均降低 1.75 0.13 –0.48 算法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 表 5 4种算法的调度长度的成对比较(%)
IPPOSS PPTS PEFT HEFT IPPOSS 更好
相同
更差* 44.9
32.4
22.758.8
26.0
15.266.7
9.7
23.5PPTS 更好
相同
更差22.7
32.4
44.9* 57.3
11.5
31.163.5
9.2
27.3PEFT 更好
相同
更差15.2
26.0
58.831.1
11.5
57.3* 54.2
5.0
40.8HEFT 更好
相同
更差23.5
9.7
66.727.3
9.2
63.540.8
5.0
54.2* -
[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. -