TAN Qianqian, CHENG Ting, and LI Xi

School of Information and Communication Engineering, University of Electronic Science and Technology of China, Chengdu 611731, China

Abstract: An adaptive dwell scheduling algorithm for phased ar-ray radar (PAR) is proposed in this paper.The concept of online dynamic template is introduced, based on which a general pulse interleaving technique for PAR is put forward.The pulse interleaving condition of the novel pulse interleaving is more intuitive and general.The traditional adaptive dwell scheduling algorithm combined with the general novel pulse interleaving technique results in the online adaptive dwell scheduling based on dynamic template for PAR is given.The proposed algorithm is suitable for radar tasks with multiple pulse repetition intervals (PRIs),which can be utilized in the actual radar system.For the purpose of further improving the scheduling efficiency, an efficient version is proposed.Simulation results demonstrate the effectiveness of the proposed algorithm and the efficient one.The proposed efficient algorithm can improve the time utilization ratio (TUR) by 9%, the hit value ratio (HVR) by 3.5%, and reduce the task drop ratio (TDR) by 6% in comparison with existing dwell scheduling algorithms considering pulse interleaving in PAR and the proposed efficient one.

Keywords: dynamic template, dwell scheduling, pulse interleaving.

1.Introduction

Phased array radar (PAR) can switch its beam direction rapidly, so it has the ability of multi-function.The system resources are shared by different radar tasks, therefore the effective resource management algorithm is very important for PAR to make better use of its performance.Radar resource management involves prioritization [1],parameter selection [2−7], and scheduling [8−31].We focus on the dwell scheduling problem in this paper.

The dwell scheduling based on the template is the pioneer scheduling method [8−10].As the templates are often designed offline and fixed, they lack the flexibility and adaptability to the working environment of the radar system.The adaptive dwell scheduling algorithms[11−13] are more flexible and effective than the methods based on templates.The execution time of scheduled dwells in each scheduling interval is allocated according to the working priority of tasks in [11], which is adaptive to the system resource.In [12], the quadratic programming can obtain the best execution time of tasks.A new adaptive dwell scheduling algorithm was proposed in[13], where the concept of time pointer was introduced to make the task priority dynamic during scheduling.Based on time pointer analysis method, the proposed algorithm of [14] solves the problem of two-dimensional resource management in PAR.The analysis method based on time pointer was proposed to schedule tasks for the air-defense phased array radar in [15].In previous adaptive dwell scheduling algorithms, radar task was regarded as a whole and cannot be preempted.For the purpose of further improving the utilization of radar system time and energy resources, the pulse interleaving technique was put forward in [16].In [17], a novel adaptive dwell scheduling algorithm based on pulse interleaving technique was proposed by modifying the time pointer’s sliding step in the algorithm of [13].In [18], a pulse interleaving technique based on the analysis on the state of remaining resource was proposed.In [19], the pulse interleaving in phased array radar was considered which was realized through checking if three pulse overlapping conditions are not met.The pulse interleaving was realized by updating the remaining time pieces and checking if the transmitting and receiving durations can be executed in these pieces in [20].Adaptive dwell scheduling method based on pulse interleaving for digital array radar (DAR)was proposed in [21], where the receiving duration of tasks can be overlapped in DAR.The start and end time of the receiving duration was used to analyze time constraints of pulse interleaving in [22], which reduces the complexity of the interleaving analysis.In [23], a pulse interleaving technique based on the state analysis of the scheduling interval was proposed, which was combined with convential dwell scheduling algorithm to realize dwell scheduling for DAR.A simplified pulse interleaving method was given in [24] for DAR.However, the task model is not a realistic one, which limits the application of the method.The pulse interleaving that makes full use of transmitting, waiting and receiving durations of radar dwells were proposed in MIMO radars in [25,26].This paper focuses on the dwell scheduling for PAR.

Based on the works above, it can be seen that

(i) Adaptive dwell scheduling methods and the ones based on templates are regarded to be independent.The combination of them has never been considered so far.

(ii) In existing pulse interleaving methods, only the dwell tasks with the same pulse repetition interval (PRI)and PRI number can be interleaved [21,25], or the tasks with only one single PRI are interleaved [22,27−30].In practice, multiple PRIs are contained in actual radar task to obtain the desired signal to noise ratio (SNR).

Therefore, the concept of online dynamic template is introduced, which represents the occupied time and energy situation of the remaining time in a scheduling interval (SI).Combined with the traditional adaptive dwell scheduling algorithm, an online adaptive dwell scheduling algorithm based on dynamic template for PAR is put forward, whose contributions include

(i) The proposed algorithm is a combination of the adaptive dwell scheduling algorithm and online dynamic template.

(ii) The novel pulse interleaving based on online dynamic template is put forward, whose conditions of successful interleaving are more intuitive.

(iii) Because the proposed algorithm is based on the radar task model with multiple PRIs, it can be utilized in actual radar.

(iv) Based on the proposed algorithm, an efficient version is developed to improve the execution efficiency of the algorithm.

The rest of the paper is organized as follows: Section 2 describes the model formulation of dwell scheduling.Section 3 puts forward the online adaptive dwell scheduling algorithm based on dynamic template for PAR.Section 4 develops an efficient version of the proposed one in Section 3.The simulation results are shown in Section 5,and the conclusions of this paper are drawn in Section 6.

2.Model formulation of dwell scheduling in PAR

To obtain desired SNR, multiple PRIs are included in a radar task.In each PRI, the system transmits, waits, and receives the echoes, which can be depicted in Fig.1.

Fig.1 Radar task model

Therefore, construct the model of Taskias follows:

The parameters of the radar task model are described in Table 1, where the calculation of other parameters of the task can obtain the deadline in [31].According to the expected execution time and the time window, we can get the earliest and latest execution time of a task, which are rti−liand r ti+lirespectively.

Table 1 Description of the radar task model

In the process of dwell scheduling, firstly the radar time resource constraints should be satisfied, including:

(i) All scheduled tasks must be completed before the deadline.

(ii) The transmitting durations and receiving durations of these tasks do not overlap with each other.

When pulse interleaving is considered during scheduling, the duration of transmitting is prolonged.For example, in Fig.2 which shows that the interleaving in the first PRI of Task0 and Task1, tx0+tx1is the total transmitting duration length of radar system after Task0 and Task1 interleaving.Therefore, the energy constraint should be considered:

Fig.2 Interleaving of two tasks in the first PRI

whereE(t) is the radar system energy consumption at timetand can be calculated as follows:

where τ is the look-back period andP(x) is the power function.Ethis a threshold of the maximum energy consumption of the system.

Note that the tasks with different PRIs and PRI numbers may be interleaved in this paper.It is more general compared with existing pulse interleaving techniques,which will be explained in detail in Section 3.

In the process of arranging the task scheduling sequence, the priority and deadline of the radar task is considered comprehensively.AssumeMradar tasks are requested to be scheduled at the moment, the synthetic priority s wiforTiis calculated as follows [13]:

where Npiand Ndiare the serial number ofTiin the task request queues arranged according to the working mode priority and deadline respectively.η is a controllable parameter.

Assume there areNdwell tasks applied to be executed in current SI.Based on above synthetical priority and constraints, the dwell scheduling optimization model is given:

wheret0is the beginning time of the SI andtendis the end of the SI.etiis the actual execution time ofTi.Obviously,N1+N2+N3=N.And the task numbers of scheduled, delayed and deleted sequence areN1,N2, andN3respectively.

There are seven constraints in the above dwell scheduling optimization model.The first one means that the actual execution time allocated to each task should be within its executable time range.The second to the fourth constraints correspond to no interrupt during transmitting and receiving.The energy constraint is shown in the fifth inequality.The conditions for delayed tasks and deleted tasks are described by the last two inequalities in the dwell scheduling optimization model respectively.

3.Online adaptive dwell scheduling based on dynamic template for PAR

3.1 Introduction of online dynamic template

The conventional adaptive dwell scheduling algorithm in[13] is chosen as the basic dwell scheduling algorithm as its superiority over other conventional adaptive dwell scheduling algorithms.It includes the following steps:

Step 1Initialize the time pointer tp(tp≥t0) of the scheduling interval, andi=0.

Step 2Select the task requests meeting that tp is larger than the latest execution time of them.Assume the number of selected tasks isn, then delete them andi=i+n.

Step 3Choose the task requests satisfying that tp is larger than the earliest execution time of them.And the synthetic priorities of them are calculated according to (4).

Step 4Choose the task request with the highest synthetic priority to be the scheduled one, and denote it asTj.

Step 5Update t p=tp+prij×Mjandi=i+1 .Ifi>Nor tp>t0+LSI, the process of scheduling ends, otherwise go to Step 2.

It can be seen in Step 5 that once a task is scheduled,the time pointer will slide the length of its dwell time as shown in Fig.3.Therefore, the waiting duration of this task is not utilized.

Fig.3 Sliding process of the time pointer

As shown in Fig.3, it can be seen that the time pointer continuously slides in the scheduling interval and the left resource in the SI is the one during the time pointer and the ending time of this SI.Based on the sliding time pointer, a dynamic template can be constructed, which can be described as follows:

where tp is the start time of templateBandt0+LSIis the end time of templateB.LSIis the length of the current SI.Δtis the length of the slot in the templateB.The time resource occupation, energy consumption of templateBare described by the vectorsSandE.Fig.4 shows the illustration of the template.The length ofSandEis

Fig.4 Characterizations of dynamic template

where rounding up is denoted by.

3.2 A general pulse interleaving analysis based on dynamic template

When developing the dwell scheduling algorithm for PAR, this paper fully considers the pulse interleaving technique.Based on dynamic templateB, a general pulse interleaving analysis method can be designed.Suppose taskT1is scheduled, then analyze if the system can scheduleT2at tp according to the following way:

(i) The state variation vectors caused byT2are calculated.When the system schedules taskT2at tp, the situation of time and energy resource in templateBwill be changed where ΔSand ΔEdescribe variations in time and energy resource consumption caused.ΔSand ΔEare calculated as follows:

In (9), the energy state variation of thejth slot in the dynamic templateBis denoted as ΔEk(j), which is caused by thekth PRI of taskT.

(ii) The constrains in dynamic templateBare judged.Check whether the inequalities (11) and (12) meet the following time and energy constraints:

where (11) denotes that taskT2and other scheduled tasks will not interrupt with each other during execution.Equation (12) indicates that the energy by consumed of dynamic templateBwill not exceed the threshold, which corresponds to the fifth constraint in (5).If (11) and (12)are met, the system can scheduleT2at tp.The parametersSandEof the template will be updated.Fig.5 shows the detailed ΔSand ΔE.Obviously, the two tasks have different PRIs and the number of PRIs.

Fig.5 Analysis process of pulse interleaving in dynamic template

Based on the dynamic template, the pulse interleaving involved in the above scheduling analysis method is easier and general.

3.3 Online adaptive dwell scheduling algorithm based on dynamic template

Combing the adaptive dwell scheduling algorithm in [13]and the above novel online pulse interleaving method, the online adaptive scheduling algorithm based on dynamic template is obtained.Assume during the current SI[t0,t0+LSI],Ndwell tasks applied to be scheduled are denoted asT={T1,T2,···,TN}.The steps of the online adaptive scheduling algorithm based on dynamic template are as follows:

Step 1Dynamic templateBis initialized.The start time of initial template ist0and the end time of initial template ist0+LSI.Leti=0 .The time pointer tp and the state vectorsSandEof initial template are set as follows:

wherentpis calculated by (7).

Step 2Select the task requests meeting that tp is larger than the latest execution time of them.Assume the number of selected tasks isn, then delete them andi=i+n.

Step 3Choose the task requests satisfying that tp is larger than the earliest execution time of them.And the synthetic priorities of them are calculated according to(4).Denote the task with the highest synthetic priority asTtestand judge whetherTtestis scheduled at tp in the dynamic templateBaccording to Section 3.2.

Step 4IfTtestcan be scheduled at tp, parameters are updated as follows:

where tx is the transmitting duration ofTtest.Otherwise,Δtp=Δt.

Step 5Let tp=tp+Δtp, other parameters in the dynamic templateBare updated as follows:

Step 6Ifi>Nor tp>t0+LSI, the analysis process of task scheduling ends, otherwise go to Step 2.

In the proposed algorithm, the complexity is mainly based on (18) and (19).The time pointer slides a time slot Δteach time.At the beginning of SI, the lengths ofSandEareand the calculation of (18) and (19) involvestimes summation.Then it involvestimes summation in the next step and so on.Therefore,in general, the complexity of the algorithm can be described as.

4.An efficient version of online adaptive dwell scheduling algorithm based on dynamic template for phased array radar

In the proposed algorithm, the time pointer slides according to the length of the transmitting duration of the scheduled task.However, if the occupancy of the dynamic templateBis already high, then the time pointer can slide further to improve the execution efficiency of the proposed algorithm.In order to evaluate the occupancy ofB,the time utilization ratio of a period after tp is considered.

As shown in Fig.6, the positions of the red lines are between the continuously occupied time slot and the next unoccupied time slot adjacent to it in the dynamic templateB.They are described by vectorPas follows:

wheremis the number of red lines.For example,P(1)=2,P(2)=5,P(3)=8 in Fig.6.The utilization ratio corresponds toPis denoted as

Fig.6 Illustration of the red lines in the dynamic template

whereu(j) is the utilization ratio ofj=1,2,···,m.The indexj*of the first element in vectorUthat makes the following inequality hold is found:

whererthis an expected utilization ratio.The sliding length of the time pointer is updated accordingly as Δtp=P(j*)×Δt.Especially, Δ tp=tx whenu(1)

Fig.7 describes the flow chart of the efficient algorithm, where Step 4 of the original proposed algorithm in Section 3.3 is replaced by Steps 4A−4D.

Fig.7 Flow chart of the efficient version

Step 4AIfTtestcan be scheduled at tp, go to Step 4B.Otherwise, Δtp=tx andi=i+1, go to Step 5 in Section 3.3.

Step 4BFind the vectorPin the dynamic templateBaccording to (22) and calculate the utilization ratio of,j=1,2,···,mto form vectorU.Ifu(1)

Step 4CFind the indexj*of the first element in vectorUthat satisfies (24).

Step 4DUpdate the sliding length as follows:

It can be seen that in the efficient version of the proposed algorithm, the sliding step can be adaptive with the utilization ratio of the template.If it has already been fully used, the sliding step is relatively large.Otherwise,it slides as before.It is specially noted that ifrthis selecsmaller isrth, the easier is the time pointer slides forward.Therefore, the complexity of the efficient version is proted as 100%, the efficient algorithm is the original one proposed in Section 3.3.In the efficient algorithm, the portional to

5.Simulation results

Considering horizon searching, airspace searching, precise tracking, normal tracking and confirmation tasks in the simulation scene, set the whole simulation time as 4 s,SI=4ms,Eth=10J, τ=200ms and Δt=0.5ms.The searching task requires many beams to complete the searching of a given area, therefore, the dwell number is more than 1.For the confirmation task, the position where there is possibly a target should be illuminated.It is a random event, and usually involves one dwell.For the tracking task, at each sampling moment, the beam should be transmitted towards the predicted position of the target, and only one dwell is included.The detailed radar task parameters are given in Table 2 [13].Increasing the target number from 0 to 100, the ratio of targets with precise tracking and ones with normal tracking is set as 1:4.The performances indices of the proposed algorithm are compared with two existing dwell scheduling algorithms, which are the algorithm in [17] (Algorithm A) and the one in [13] (Algorithm B).

Table 2 Parameters of radar tasks

(i) Task drop ratio (TDR): it is defined as the ratio between the number of radar tasks deleted and the total number of tasks requested to be executed.It can be calculated as

whereNtotalis the total number of tasks requested to be executed,Nloseis the number of radar tasks deleted.

(ii) Time utilization ratio (TUR): it is defined as the ratio between the total time of the transmitting and receiving durations of radar tasks scheduled and the total simulation time.It can be calculated as

whereTtotalis the simulation time.

(iii) Hit value ratio (HVR): it is defined as the ratio of the hit value of radar tasks scheduled to that of all tasks requested to be scheduled.It can be expressed as

whereNsucis the number of successfully scheduled tasks.

Fig.8 to Fig.13 show the average results of 100 Monte Carlo simulations.

When using the proposed algorithm, parameterrthshould be given firstly.Considerrthis set to be 0.25, 0.5,0.75 and 1.00.

Firstly, the performances of the original proposed algorithm and the efficient one withrth=1 are compared.Fig.8(a) shows the comparison of TDRs.Fig.8(b) shows the comparison of TURs.Fig.8(c) shows the comparison of HVRs.It can be seen that they have similar performances.The reason is that when the threshold is 1, the effect is equivalent to sliding the time pointer Δteach time.Obviously, the TDRs, HVRs and TURs of two algorithms are almost the same.Fig.9 shows the cost time comparison.The dwell scheduling efficiency is slightly improved by the efficient version withrth=1.Therefore,to obtain obvious efficiency improvement,rthshould be decreased further.

Fig.8 Comparison of the performances of the original proposed algorithm and the efficient one with rth=1

Fig.9 Comparison of cost time of the original proposed algorithm and the efficient one with rth=1

Fig.10 shows the comparison results with differentrthin the proposed algorithm.Obviously, the HVR declines more slowly and the TDR rises faster asrthincreases from 0.25 to 1.00.However, whenrthincreases from 0.25 to 1.00, more time is spent by the scheduling process.The introduction ofrthcan save the cost time compared with the original proposed algorithm.Moreover, with the increase ofrth, TDR and HVR will become closer to that withrth=1.Consider the TDR, the HVR, and cost time comprehensively,rthis selected as 0.75.

Fig.10 Comparison of the proposed algorithm in different rth

Fig.11 shows the comparison of TDRs.The TDR of Algorithm B rises rapidly with the increase of the target number whenN=40.This is because the pulse interleaving technology is not used in Algorithm B.Therefore, the radar system wastes the waiting durations of tasks.Although the pulse interleaving technology is introduced to Algorithm A and the proposed one, the TDR of Algorithm A rises faster compared with the proposed one.When the targets number reaches 50, the radar tasks start to be dropped in Algorithm A.However, the target number increases as 60, the proposed one begins to lose radar tasks.That is because the tasks with different PRIs and PRI number may be interleaved in the dynamic templateB.The proposed algorithm breaks the strict conditions of Algorithm A which only allows the tasks with the same PRI and PRI number to be interleaved.

Fig.11 Comparison of TDRs

Fig.12 compares the TURs of these algorithms.Because the waiting durations of radar tasks are neglected by Algorithm B, the TUR of it is much lower than the proposed algorithm and Algorithm A.Increasing of the number of targets, radar resources are insufficient for scheduling more tasks in Algorithm B, which leads to the losing of more and more tasks and the TUR of Algorithm B decreases quickly after the targets number reaches 40.Because of too strict conditions of pulse interleaving in Algorithm A, the interleaved tasks are fewer than the proposed algorithm.Therefore, the proposed algorithm can schedule more tasks and the TUR of it is much higher than Algorithm A after the targets number reaches 50.

Fig.12 Comparison of TURs

Fig.13 compares the HVR of these algorithms.Before the targets number reaches 40, the HVRs of Algorithm B,Algorithm A and the proposed one are same as 1.The HVR of Algorithm B is the first to drop from 1.Then the HVR of Algorithm A begins to decrease correspondingly when the targets number reaches 50.Until the number of targets reaches 60, the HVR of the proposed algorithm starts to change, the decreasing trend of which is slower compared with other two algorithms.

Fig.13 Comparison of HVRs

Therefore, compared with other existing pulse interleaving algorithms in PAR, the TDR is significantly reduced by 6% and the TUR and the HVR are improved by 9% and 3.5% respectively in the proposed algorithm.Furthermore, the value ofrthis recommended to be 75%,which can balance the scheduling performance and efficiency effectively.

6.Conclusions

For the purpose of fully exerting the performance of PAR, it is necessary to manage its limited resources effectively.And it is the key point to design the dwell scheduling algorithm in PAR.The concept of online dynamic template is introduced, based on which the novel online pulse interleaving technique is proposed.Compared with existing pulse interleaving methods, it is easier and more general to realize pulse interleaving between tasks.Combining the existing dwell scheduling method and the novel pulse interleaving technique, an online adaptive dwell scheduling algorithm based on dynamic template for PAR is put forward.Moreover, in order to improve the execution efficiency of the proposed algorithm, an efficient version is developed.The simulation results show that the algorithm can effectively improve the TDR, TUR, and HVR.In addition, the scheduling performance of the efficient version of the proposed algorithm can be further improved.