Pulse interleaving scheduling algorithm for digital array radar

ZHANG Haowei,XIE Junwei,ZHANG Zhaojian,ZONG Binfeng,and SHENG Chuan

1.Air and Missile Defense College,Air Force Engineering University,Xi’an 710051,China;2.Unit 94710 of the PLA,Wuxi 214000,China

1.Introduction

The digital array radar(DAR)has great advantages such as longer detection range,lower probability of interception,and serving more simultaneous functions/tasks over the traditionally analog phased array radar.The superiorities above rely on the effective resource management in the DAR,where the task scheduling is a key problem.

The scheduling algorithm in the phased array radar has been investigated in numerous researches in recent years.The task-mode-priority-based scheduling algorithm was proposed in[1,2].The task mode priority was preset for each kind of task,and the task with the highest task mode priority was prior scheduled.The time-balance-based algorithm was presented in[3,4].The urgency of each task was introduced and the task with the immediate deadline was prior scheduled.The queue-based algorithm was developed in[5,6].The request tasks were divided into several queues,and the first in first out(FIFO)algorithm or the earliest deadline first(EDF)algorithm was utilized to schedule tasks in each queue.The mission of imaging was introduced into radar task scheduling in[7,8],and the scheduling algorithm based on the sparse-aperture inverse synthetic aperture radar(ISAR)compressive sensing(CS)cognitive imaging techniques was proposed.The threat level of the target was exploited to represent the task importance,and the dynamic-priority-based algorithm was put forward in[9,10].However,the majority of the literatures above regard radar tasks as non-preemptive ones.When a more explicit task structure is considered,the task waiting duration is able to be utilized to transmit or receive subtasks,namely,the pulse interleaving,and the time utilization level is able to be enhanced.However,the pulse interleaving also complicates the task schedulability analysis.The template-based algorithms were proposed in order to schedule the interleaved tasks as many as possible in[11–13].The online pulse interleaving technology was offered in order to match different workload situations in[14,15].In addition,the pulse interleaving scheduling method was put forward based on the swarm search in[16–18].The tabu search scheduling algorithm was offered in[16],the chaos adaptively genetic algorithm was provided in[17]and the hybrid genetic particle swarm algorithm was proposed in[18],all of which improve the efficiency and the robustness of radar task scheduling.

While the existing work has made many seminal contributions,there are still some issues to be addressed.Firstly,the full radar structure,which includes the transmitting duration,the waiting duration and the receiving duration,was not explicitly considered in[2–10].Such a simplification of the radar task model precludes the full utilization of waiting durations in radar tasks.Secondly,some does utilize the waiting durations to interleave subtasks[1,11–18],however,the task interleaving ways should be extended owing to the digital beam forming(DBF)technique in the DAR.By DBF,not only the waiting duration in the DAR task is able to be utilized,but also the receiving durations from different tasks can be overlapped on the radar time line.The variety of interleaving ways introduces both the opportunity and the challenge of how to exploit the DAR time line more efficiently.The comprehensive priority-based scheduling algorithm for this problem was developed in[19,20],however,the tasks with the same pulse repetition interval were only interleaved in[19,20],and much time maybe wasted.As such,an online pulse interleaving scheduling algorithm for the DAR is proposed,which decomposes the pulse interleaving analysis into the time resource constraint check and the energy resource constraint check,and adaptively schedules tasks only if they meet the multiple constraints.Thereby,the complexity of the pulse interleaving scheduling is decreased and the time line utilization is maximized.Computational results are presented to demonstrate the performance of the algorithm.

2.Task structure in DAR

Fig.1 shows the DAR task model.It can be seen that the kth DAR task is able to be described as

Fig.1 Task model in DAR

The parameters description in(1)is shown in Table 1.

Table 1 DAR task parameter and description

tdwkis able to be described as

tdksatisfies

Each task should be completed before its deadline or it will be useless because of the target maneuvering.The request time between two tasks of the same kind satisfies

where te(k-1)is the execution time of the former task.

3.Resource constraints

3.1 Time resource constraint

The scheduling interval(SI)is the minimum unit of the task scheduling in the phased array radar,when the radar processes the returning signals in the former SI and outputs the tasks to be executed in the next SI.All N1tasks to be executed in an SI should meet the following time constraints:

where tstartand tendare the start time and the end time of the SI respectively.tend=tstart+tSI,where tSIis the scheduling interval time.If a task cannot be successfully scheduled in the SI,it will be delayed to the latter SIs or be deleted.

As mentioned previously,the pulse interleaving technique,shown in Fig.2,improves the time utility by transmitting or receiving subtasks during a task waiting duration.In addition,the different receiving durations of DAR tasks are able to be overlapped.However,the transmitting duration is non-preemptive,or the executing task will fail.As such,the N1tasks also should satisfy

3.2 Energy resource constraint

The pulse interleaving technique prolongs the transmitting time,as such,the energy resource constraint should be taken into consideration.In order to protect the radar to be safe,the radar transmitter must satisfy the transient constraint all the time[10,21]:

where Pτmaxis the upper bound of the power consumption and Pτ(t)is the power consumed by the radar in time t.Pτ(t)is able to be expressed as

where p(x)is the instantaneous power dissipation in the radar,and τ is the look-back period,which characterizes the heat dissipation performance of the radar.Assume that,the cool duration tcis calculated[10]as

4.Online pulse interleaving scheduling algorithm

In view of the previously discussed assumptions of the existing scheduling algorithms,a novel online pulse interleaving scheduling method is proposed for the DAR in this section,which is with the following salient characteristics.The first is that the waiting durations in the DAR tasks are utilized to interleave subtasks.The second is that all kinds of tasks are able to be interleaved if only they meet the time and the energy constraints.The third is that the receiving durations from different tasks are able to be overlapped.Last but not least is that the algorithm performs only as needed and occurs naturally rather than as a preset step.

Fig.2 shows the four pulse interleaving ways in the DAR.

Fig.2 Four pulse interleaving ways in DAR

The shadow box is task 0 and the blank box is task 1.tp0and P0are the time indicator and the power indicator respectively.It can be seen that the two tasks which are interleaved should meet the following time constraints:

In addition, the two interleaved tasks should also satisfy the constraints shown in Section 3. It is obvious that the variety of pulse interleaving ways complicates the task schedulability analysis. Therefore, a simple but effective onlinepulse interleaving analysis method is proposed, which includes the time constraint check and the energy constraint check.

Without loss of generality,assume that there are Nrerequest tasks which have been sorted by theirpriorities di-minishingly in an SI,the number of successfully scheduled tasks is n,the timeline of the SI is[tstart,tend],the time indicatoris tp0,the powerindicator is P0,the ith time piece which has been occupied by the receiving durations of scheduled tasks is[trsi,trei](i=1,2,...,m,m≤n),and the remaining Nre-n tasks are signed as task 0,1,2,...,Nre-n-1 respectively.When task 0 is attempted to be scheduled in tp0,the time constraint check should be firstly applied to the transmitting duration of task 0:

where treiis the end time of the i th time piece which has been occupied by the receiving durations,and trs(i+1)is the start time of the(i+1)th time piece which has been occupied by the receiving durations.The transmitting duration of task 0 meets the time constraint when it sat is fies(14)or(15)or(16).Then,the receiving duration of task 0 should be checked by the time resource constraint:

When the receive interval of task 0 sat is fies the time constraint,the energy constraint check should be applied further:

When

task 0 will satisfy the energy constraint,and schedule task 0 in tp0and update tp0and P0as

In addition,update the time piece which has beenoccupied by the receiving durations.If task 0 does not meet the time or the energy constraint, slide the time indicator and update tp0and P0as ?

where Δtpis the preset smallest sliding step for tp0.Then,continue to analyze the schedulability of task 0 under the time and the energy constraint.The analysis method for task 0 should be referenced when analyzing the remaining Nre-n tasks.In this way,where the continuous update of tp0,P0,and the time pieces occupied by the receiving durations,the specific task interleaving ways are able to be ignored and the task interleaving analysis is simplified.

The flow chart of the algorithm is shown in Fig.3.

Fig.3 Flow chart of the proposed algorithm

5.Simulations and results

5.1 Performance evaluation indexes

The following indexes are chosen in order to evaluate the performance of the scheduling algorithms.

(i)The successful scheduling ratio(SSR)[7,8,18,22],which is the ratio between the number of successfully scheduled tasks Nsucand that of all request tasks Ntotal,is able to be expressed as

(ii)The time utilization ratio(TUR)[2–4,6–22],which is defined as the ratio between the time consumption of the successfully scheduled tasks and the totally available time resource Ttotal,is able to be expressed as

(iii)The high value ratio(HVR)[7,8,14,18–20,22],which is the ratio between the total priority of all successfully scheduled tasks and that of all request tasks,is able to be expressed as

Note that the higher indexes above the algorithm achieves,the better the scheduling algorithm performs.

5.2 Simulation parameters and results

The whole simulation frame-work is based on[23].The number of targets increases from 10 to 100 in order to denote the different workloads of the DAR.Set tSI=50 ms,Pτmax=1.25 kW,τ=200 ms,and Δtp=0.5 ms.The highest task mode priority and earliest deadline first(HPEDF)algorithm[22],the dynamic priority scheduling algorithm[10]and the online interleaving algorithm[14]a in the simulations.The parameters of tasks[9,10]are shown in Table 2.The simulation results are shown from Fig.4 to Fig.6.

Table 2 Parameters of tasks

Fig.4 Comparison of SSR

Fig.5 Comparison of HVR

Fig.6 Comparison of TUR

Fig.4 compares the SSR as a function of the number of targets.As the number of targets increases,the available space on the DAR time line quickly decreases.Since the HPEDF algorithm and the dynamic priority algorithm do not exploit the pulse interleaving technique,the waiting durations in the DAR tasks are wasted,leading to more tasks being dropped.In contrast,the online interleaving algorithm introduces the pulse interleaving and successfully scheduled more tasks.However,the proposed algorithm achieves the highest SSR among the four algorithms.It is because the proposed algorithm not only adopts the pulse interleaving technique to utilize the waiting durations,but also overlaps the receiving durations of different kinds of tasks.As such,more radar tasks are successfully scheduled and the maximum workload of the DAR is improved.

Fig.5 shows the comparison of the HVR.It is clear that the proposed algorithm achieves the highest HVR among the four algorithms owing to the efficient utilization of the transmitting duration and the receiving duration of the DAR task.The HPEDF algorithm wastefully ignores the opportunity of pulse interleaving and hence achieves the worst HVR.In addition,the dynamic priority algorithm achieves the approximate HVR compared with the online interleaving algorithm though it does not take advantage of the pulse interleaving.The reason is that all request tasks are set into dynamic priorities in the dynamic priority algorithm,and the most important and urgent task is to be prior scheduled.

Fig.6 compares the TUR of the four algorithms.It can be seen that the proposed method offers much better TUR compared with the other algorithms.Especially when the number of targets is 100,the TUR of the proposed algorithm is around 66%,whereas the TURs of the other three algorithms are all lower than 60%.

Table3 shows the average runtime of the four algorithms in an SI.It is clear that the algorithms all meet the real time demand of the DAR(＜50 ms).In addition,the proposed algorithm provides faster runtime than the online interleaving algorithm.It is because the proposed algorithm decomposes the pulse interleaving scheduling into the time constraint check and the energy constraint check,the specific interleaving ways in the online interleaving algorithm as such are able to be left out and the pulse interleaving analysis is simplified.While the HPEDF algorithm and the dynamic algorithm run faster than the proposed algorithm,it should be noted that they provide vastly inferior performance compared with the proposed algorithm.However,the proposed method offers better performance as verified in Fig.4 to Fig.6 while maintaining an appropriate runtime.Therefore,the proposed method should be prior considered in order to make full use of the DAR.

Table 3 Average runtime of the algorithms in an SI ms

6.Conclusions

The optimal resource scheduling algorithm counts in releasing the full potential of the DAR.A heuristic pulse interleaving scheduling algorithm is proposed in this paper,which decomposes the pulse interleaving analysis into the time constraint check and the energy constraint check and adaptively schedules different types of tasks.In addition,the algorithm overlaps the receiving durations of different tasks considering the characteristics of the DAR.Owing to the efficient utilization of the waiting duration and the receiving duration in the DAR task,the proposed algorithm successfully schedules much more tasks and achieves better performance compared with the three existing algorithms in the simulations.

[1]ORMAN A J,POTTS C N,SHAHANI A K,et al.Scheduling for a multi-function phased array radar system.European Journal of Operational Research,1996,90(1):13–25.

[2]ZENG G,LU J B,HU W D.Research on adaptive scheduling algorithm for multifunction phased array radar.Modern Radar,2004,26(6):14–18.(in Chinese)

[3]BUTLER J M.Multi-function radar tracking and control.London:UCL University of London,1998.

[4]REINOSO-RONDINEL R,YU T Y,TORRES S.Multifunction phased-array radar:time balance scheduler for adaptive weather sensing.Journal of Atmospheric and Oceanic Technology,2010,27(11):1854–1867.

[5]HUIZING A G,BLOEMEN A A F.An efficient scheduling algorithm for a multifunction radar.Proc.of IEEE International Symposium on Phased Array Systems and Technology-Revolutionary Developments in Phased Arrays,1996:359–364.

[6]JIMENEZ M I,DEL VAL L,VILLACORTA J J.Design of task scheduling process for a multifunction radar.IET Radar,Sonar and Navigation,2012,6(5):341–347.

[7]CHEN Y J,LUO Y,ZHANG Q,et al.Adaptive scheduling algorithm for phased array radar based on cognitive ISAR imaging.Journal of Electronics&Information Technology,2014,36(7):1566–1572.(in Chinese)

[8]CHEN Y J,ZHANG Q,YUAN N,et al.An adaptive ISAR-imaging-considered task scheduling algorithm for multifunction phased array radars.IEEE Trans.on Signal Processing,2015,63(19):5096–5110.

[9]ZHANG HW,XIE J W,SHENG C.Adaptive scheduling algorithm over comprehensive priority for phased array radar.Acta Armamentarii,2016,37(11):2164–2169.(in Chinese)

[10]ZHANG H W,XIE J W,ZONG B F,et al.Dynamic priority scheduling method for the air defense phased array radar.IET Radar,Sonar&Navigation,2017,11(7):1140–1146.

[11]GOPALAKRISHNAN S,CACCAMO M,SHIH C S,et al.Finite-horizon scheduling of radar dwells with online template construction.Real-Time Systems,2004,33(1–3):47–75.

[12]LEE C G,KANG P S,SHIH C S,et al.Schedulability envelope for real-time radar dwell scheduling.IEEE Trans.on Computers,2006,55(12):1599–1613.

[13]GOPALAKRISHNAN S,CACCAMO M,SHA L.Sharp thresholds for scheduling recurring tasks with distance constraints.IEEE Trans.on Computers,2008,57(3):344–358.

[14]CHENG T,HE Z S,TANG T.Novel radar dwell scheduling algorithm based on pulse interleaving.Journal of Systems Engineering and Electronics,2009,20(2):247–253.

[15]MIR H,GUITOUNI A.Variable dwell time task scheduling for multifunction radar.IEEE Trans.on Automation Science and Engineering,2014,11(2):463–472.

[16]F ABDELAZIZ B,MIR H.An optimization model and tabu search heuristic for scheduling of tasks on a radar sensor.IEEE Sensors Journal,2016,16(17):6694–6702.

[17]ZHANG H W,XIE J W,SHENG C.Scheduling method for phased array radar over chaos adaptively genetic algorithm.Proc.of the 6th International Conference on Information Science and Technology,2016:111–116.

[18]ZHANG H W,XIE J W,LU W L,et al.A scheduling method based on the hybrid genetic particle swarm algorithm for the multifunction phased array radar.Frontiers of Information Technology&Electronic Engineering,2017,18(11):1806–1816.

[19]CHENG T,HE Z S,LI H Y.Adaptive dwell scheduling for digital array radar based on online pulse interleaving.Chinese Journal of Electronics,2009,18(3):574–578.

[20]CHENG T,LIAO W W,HE Z S.MIMO radar dwell scheduling based on novel pulse interleaving technique.Journal of Systems Engineering and Electronics,2013,24(2):234–241.

[21]GHOSH S,HANSEN J,RAJKUMAR R,et al.Integrated resource management and scheduling with multi-resource constraints.Proc.of the 25th IEEE International Real-Time Systems Symposium,2004:12–22.

[22]J LU B,XIAO H,XI Z M,et al.Phased array radar resource management:task scheduling and performance evaluation.Journal of Computational Information Systems,2013,9(3):1131–1138.

[23]KUO T W,Y CHAO S,KUO C F,et al.Real-time dwell scheduling of component-oriented phased array radars.IEEE Trans.on Computers,2005,54(1):47–60.