# Imaging Tasks Scheduling for High-Altitude Airship in Emergency Condition Based on Energy-Aware Strategy

Authors: Li Zhimeng; He Chuan; Qiu Dishan; Liu Jin; Ma Manhao
Journal: The Scientific World Journal
 (2013)

---

## Abstract

Aiming to the imaging tasks scheduling problem on high-altitude airship in emergency condition, the programming models are constructed by analyzing the main constraints, which take the maximum task benefit and the minimum energy consumption as two optimization objectives. Firstly, the hierarchy architecture is adopted to convert this scheduling problem into three subproblems, that is, the task ranking, value task detecting, and energy conservation optimization. Then, the algorithms are designed for the sub-problems, and the solving results are corresponding to feasible solution, efficient solution, and optimization solution of original problem, respectively. This paper makes detailed introduction to the energy-aware optimization strategy, which can rationally adjust airship’s cruising speed based on the distribution of task’s deadline, so as to decrease the total energy consumption caused by cruising activities. Finally, the application results and comparison analysis show that the proposed strategy and algorithm are effective and feasible.


---

## Body

## 1. Introduction

One of the most significant features of emergency scheduling problem (ESP) is timeliness; that is, the execution of task must be completed in its deadline. Otherwise, the task will lose its executive value or become invalid [1–3]. Under the emergency condition, the imaging task has its observation slot to reflect the requirements on the execution timing interval. For example, the emergency tasks, such as the observations on the targets about moving missile system, massing troops, and cruising battleship, generally need the responding agencies to scout timely in order to rapidly analyze the situation and to plan the operational activity.Over the last decade, many military groups such as the US army have been devoted to development of the emergency imaging technology and improvement of the quick response ability of the reconnaissance system by incorporating multiple platforms. High-altitude airship is a promising solution for the emergency observation platform in the near-space [4, 5]. Unlike conventional heavier-than-air (HTA) aircraft, high-altitude airship is a lighter-than-air (LTA) aircraft equipped with steering and propulsion systems, and it generates lift force through the buoyancy instead of aerodynamics [6]. At present, high-altitude airship located in the near-space has attracted wide attention in many countries, and it is well known that some projects have been studied, for example, the HARV and HAA projects [7] in USA, Sky cat and CL-160 projects [8] in the European Union, ETRI [9] in South Korea, and Sky Net in Japan [10]. The scientists and engineers in China have conducted corresponding researches since the last century, and the verification airship has completed its low-altitude flight experiment in 2003.As a new application platform, the high-altitude airship has many advantages in reconnaissance activities. For instance, it has a long duration, and a great deal of load carrying, and can achieve the fixed-point successive observation, and so forth [11]. In comparison with the traditional unmanned aircraft vehicle (UAV) [12, 13], the high-altitude airship can be operated continuously for several months, even for more than one year in the assigned airspace. It is also easy to acquire data and information uninterruptedly in a long period. Due to the fuel restriction, UAV has to implement the aerial refueling or return to the base frequently, so it is impossible to achieve the long-term and continuous monitoring at a lower cost. The capsule of the high-altitude airship is usually made from the nonmetallic materials with less electromagnetism and heat reflecting, which makes it hard to be captured by radar. In addition, the high-altitude airship is invulnerable to be attacked and intercepted by many air-defense missiles, due to the operational height which is out of their fire range. Compared with the imaging reconnaissance satellite [14–16], the high-altitude airship has stronger ability of rapid response. Generally speaking, the ground support equipments for launching a high-altitude airship are fewer in number and have shorter period of launching preparation. Therefore, the theater reconnaissance, surveillance, and warning system can be established by high-altitude airship in a few hours, and the mass deployment can be rapidly implemented with its strong maneuverability. In terms of the efficiency-cost ratio, the in-orbit time of a high-altitude airship is nearly equal with that of an imaging reconnaissance satellite, but the usage cost is far less than the latter. In addition, the satellite is restricted by the fixed orbit in use and only can observe the targets in a certain time slot. On the contrary, the high-altitude airship can achieve the long-term and continuous observation on the target in the hover-and-stare way. Due to the previous advantages, the high-altitude airship has huge application potential in the emergency activities, such as the antiterrorism, disaster relief, and regional battles. The aforementioned advantages have turned high-altitude airship into an ideal imaging observation platform.Existing studies on high-altitude airship are scattered over a range of journals, conferences, books, and reports. Rao et al. [17] presented a mission path following controller for the airship by employing artificial neural network (ANN). Tan et al. [18] introduce some methods and techniques to realize lightweight structure and present a review of current research on high-altitude airship with lightweight structures. Bessert and Frederich [19] investigated the aerodynamics behavior of high-altitude airship and presented a novel technology to test the aerodynamics on the structural behavior of airship. Ren et al. [20] analyzed the aerodynamics problems of high-altitude airship while launching, recovering, hovering, and introducing the achievement of airship dynamics research. Especially, there are numerous studies on energy system of high-altitude airship. Wang et al. [21] presented a novel computation method for solar radiation on solar cells of the airship, given the effect of the airship’s attitude on the performance of its energy system. Ma and Sun [22] developed a power management framework of high-altitude airship, which can rationally distribute power to subsystems so as to lighten the energy consumption in certain situation. Wang et al. [23] proposed an energy balance method to analyze the regenerative energy system, which can streamline the configuration design of high-altitude airship. In addition, there are also great deal of works focusing on the propulsion system. Chen et al. [24] constructed a simulation model and made some analyses about propeller of high-altitude airship. Jordi et al. [25] discussed the biomimetic principles for the structural design of airship. Various development tests are completed in their research, including wind tunnel testing and flight trials. Unfortunately, there are only a handful of works reported to date in the literature that propose the task planning of high-altitude airship, which greatly degrades the system performance such as task guarantee ratio and energy consumption.In this paper, we focus on the imaging tasks scheduling problem on the high-altitude airship under the emergency condition. The power-speed model is constructed, which is employed to evaluate the energy consumption during the airship’s reconnaissance actives. We convert this scheduling problem to constrain satisfaction problem (CSP), then a heuristic algorithm based on the optimization sequence rule (OSR) is presented to obtain the task ranking scheme, and a value task detecting (VTD) method is provided to detect the key nodes that each airship needs to fly through in sequence. An energy-aware strategy (EAS) is also provided to optimize the task planning by rationally adjusting the cruising speed of airship. The simulation results show the effectiveness of this strategy.The reminder of this paper is structured as follows. Section2 makes detailed description on the reconnaissance process of high-altitude airship and establishes the corresponding models and proposed optimization objects. Section 3 converts the original problem into three sub-problems by adopting hierarchy architecture and design the solution algorithms, respectively. The simulation experiments and performance analysis are given in Section 4. The final section will conclude this paper and discuss the future research direction.


## 2. Problem Description and Modeling

The application of high-altitude airship in imaging reconnaissance activity is an asset for other reconnaissance equipments, and it is of great significance to build and improve the reconnaissance network. To facilitate analysis and modeling of this problem, we summarize the main notations used throughout this paper as follows:Tp=[tstart,tend]: the active period of airship, where tstart refers to the starting time and tend refers to the completion time of observation activity;Task={task1,task2,…,taskn}: the imaging task set, where the element taski refers to the ith task, and n refers to the task number;siti=(xi,yi): the observation projection position of  taski, where xi, yi denote the horizontal coordinate and vertical coordinate, respectively;sit0=(x0,y0): the projection coordinate of airship at the beginning;Smax: the maximum cruising speed of airship;tdi: the deadline of taski;tbi: the beginning timing instant of taski;tei: the completion timing instant of taski;ti: the duration time of taski, which includes the system stability time, load switch time, and data storage time;Si,j: the average cruising speed of airship between siti and sitj;di,j: the distance between siti and sitj;eni,jactive: the energy consumption of cruising from siti and sitj;enistatic: the energy consumption of balance resistance while airship in fixed-point state.


### 2.1. The Process of Task Execution

The imaging payload is usually installed in the cabin of high-altitude airship, which can be tilted or rotated within a certain angle to observe targets on the ground. During the task execution, the high-altitude airship flies according to the predetermined route and hover at a certain observation position, and in this way, the targets can be observed by imaging payload.As shown in Figure1, taski and taskj are located in different positions. After completing taski, the airship moves to another observing position to execute taskj. The cruising of airship will take a long time due to the limited speed, which makes it almost impossible to execute taskj timely.Figure 1
The cruising of high-altitude airship.Theorem 1.
Iftaski can be observed before its deadline, it is called a value task; otherwise, it is called an invalid task.
Assume that the current time isT0, and L is the distance between the airship and taski. If taski is a value task, the following conditions must be met:
(1)T0+LSmax+ti≤tdi.Obviously, the number of value tasks decreases with the time advancement, and this trend is irreversible. Considering that the imaging targets are widely distributed in the battle area, it is nearly impossible to ensure all tasks to be observed timely. Therefore, it is necessary to choose a reasonable task set and allocate the observation time for airship in accordance with various constraint conditions, so as to realize maximum efficiency of observing activity.


### 2.2.  The Power-Velocity Model

The energy system of high-altitude airship converts the solar radiation into electrical energy, thereby providing energy to the entire platform. Assume that the power of the propulsion system isPt, and the efficiency is η; then, the actual propulsion power is
(2)Pr=Pt×η.The cruising of high-altitude airship is subject to the impact of wind. The magnitude and direction of the propeller thrust are adjusted to balance the wind resistance, so as to realize continuous monitoring at fixed-point position. In this paper, it is assumed that the airship mainly relies on the electric propeller device to provide the thrust, which can be quickly adjusted in accordance with the wind direction and task position [26]. Since the working height of the airship is maintained, we only need to consider its horizontal movement as shown in Figure 2.Figure 2
The plane motion of high-altitude airship.Normally, the wind field in near-space is stable; hence, the wind speed can be decomposed along the axial direction and normal direction of the airship. Consider(3)Wa=Wcos(θ2-θ1),Wn=Wsin(θ2-θ1),
where W is the velocity of wind, θ1 is the cruising direction of airship, and θ2 is the direction of wind field.The typical power-velocity model of airship is [24, 27, 28]:
(4)Pa=12ρV2/3(S-Wa)3CaPn=12ρV2/3Wn3Cn,
where ρ is the air density, V2/3 is the characteristic area of airship based on its volume V, S is the airship’s cruising speed relative to the ground, and Ca and Cn refer to the aerodynamic coefficients.


### 2.3. The Optimization Objectives

LetX=(x1,x2,…,xn), Y=[yi,j]n×n, and S=[Si,j](n+1)×(n+1) be the decision variables. If taski is effectively performed, then it is a value task (assume that xi=1); otherwise, let xi=0. If xixj=1 and taski is the preceding task of taskj, then let yi,j=1; otherwise, let yi,j=0.The primary optimization objective of the tasks scheduling problem on the high-altitude airship is to maximize the guarantee rationER(X,Y,S):
(5)ER(X,Y,S)=1n∑i=1nxi.The total energy consumptionEntotal(X,Y,S) should be minimized on the base of the maximization of ER(X,Y,S). Entotal(X,Y,S) includes two parts; Enactive(X,Y,S) and Enstatic(X,Y,S) are the energy consumptions caused by cruising and balance resistance in the suspension position, respectively.According to (2)–(4), the energy consumption of airship’s cruising from siti to sitj is
(6)eni,jactive=ρV2/3Cndi,j2ηSi,j|Wsin(θ2-θ1)|3+ρV2/3Cadi,j2ηSi,j|Si,j-Wcos(θ2-θ1)|3.If the high-altitude airship locate in the observation position oftaski, the energy consumption caused by resisting the effect of wind is
(7)enistatic=ρV2/3Cati2η|Wcos(θ2-θ1)|3+ρV2/3Cnti2η|Wsin(θ2-θ1)|3.According to (6) and (7), the total energy consumption of airship during execution of the tasks is
(8)Entotal(X,Y,S)=Enactive(X,Y,S)+Enstatic(X,Y,S)=∑i=1n∑j=1nyi,jeni,jactive+∑i=1nxienistatic.


### 2.4. The Programming Model

In the typical route planning of UAV, it is necessary to simultaneously consider the maximum turning angle, maximum climbing angle, minimum flight altitude, minimum path length, and other constraints. The purpose is to ensure that the cruising path can meet the aircraft’s maneuvering characteristics and reduce the probability of damaging the aircraft in the no-fly zone and threatened area. As for the high-altitude airship in this paper, its working space has no spatial constraint, so the no-fly zone is an unnecessary consideration. At the same time, the low speed and slow dynamics provide the airship with a large-angle cornering ability, and it is also unnecessary to consider the minimum path length due to its suspension ability. Moreover, the threatened area of the high-altitude airship can be ignored due to the difficulty of being captured by the radar. However, the main constraints of tasks scheduling on the high-altitude airship are listed as follows.Constraint 1. The high-altitude airship only executes the observation task within its active period.Constraint 2. Each task can be executed only once, and it must be completed before its deadline.Constraint 3. If a task can be executed, the execution time should be no less than the required continuous working time.Constraint 4. Only one preceding task or one following task of each task is allowable at most.Constraint 5. The preemptive service in the task execution is prohibited. Once the execution starts, the process cannot be terminated until completion.Constraint 6. Before performing a new task, the airship needs sufficient time to change the observation position.Constraint 7. For any two tasks to be executed, the certain priority order exists.Constraint 8. The moving processes of airship only exist in different observation positions.Constraint 9. The cruising speed of high-altitude airship in each path segment cannot be higher than the maximum cruising speed.LetR1, R2, and R2 be the feasible solution space of the decision variables X, Y, and S. In the separate optimization of ER(X,Y,S), their optimal solution spaces are Q1, Q2, and Q3, respectively. The programming model of this scheduling problem is given as follows:
(9)Z1(X,Y,S)=maxX∈R1,Y∈R2,S∈R3{1n∑i=1nxi},Z2(X,Y,S)=minX∈Q1,Y∈Q2,S∈Q3{∑i=1n∑j=1nyi,jeni,jactive+∑i=1nxienistatic}s.t.{[tbi,tei]⊂[tstart,tend]∑i=1nxi≤1,tei≤tditei-tbi≥ti,ifxi=1∑i=1nyi,j≤1,∑j=1nyi,j≤1[tbi,tei]∩[tbj,tej]=∅,ifxi·xj=1tei+di,jSi,j-K(1-yi,j)≤tbjyi,j·yj,i=0∑i=1nyi,i=0Si,j≤Smaxxi,yi,j∈{0,1}∀i,j∈{1,2,…,m},k∈{1,2,…,n},
where the former nine inequality formulas correspond to the aforementioned constraints, respectively, and the tenth inequality formula restricts the range of the decision variables.


## 2.1. The Process of Task Execution

The imaging payload is usually installed in the cabin of high-altitude airship, which can be tilted or rotated within a certain angle to observe targets on the ground. During the task execution, the high-altitude airship flies according to the predetermined route and hover at a certain observation position, and in this way, the targets can be observed by imaging payload.As shown in Figure1, taski and taskj are located in different positions. After completing taski, the airship moves to another observing position to execute taskj. The cruising of airship will take a long time due to the limited speed, which makes it almost impossible to execute taskj timely.Figure 1
The cruising of high-altitude airship.Theorem 1.
Iftaski can be observed before its deadline, it is called a value task; otherwise, it is called an invalid task.
Assume that the current time isT0, and L is the distance between the airship and taski. If taski is a value task, the following conditions must be met:
(1)T0+LSmax+ti≤tdi.Obviously, the number of value tasks decreases with the time advancement, and this trend is irreversible. Considering that the imaging targets are widely distributed in the battle area, it is nearly impossible to ensure all tasks to be observed timely. Therefore, it is necessary to choose a reasonable task set and allocate the observation time for airship in accordance with various constraint conditions, so as to realize maximum efficiency of observing activity.


## 2.2.  The Power-Velocity Model

The energy system of high-altitude airship converts the solar radiation into electrical energy, thereby providing energy to the entire platform. Assume that the power of the propulsion system isPt, and the efficiency is η; then, the actual propulsion power is
(2)Pr=Pt×η.The cruising of high-altitude airship is subject to the impact of wind. The magnitude and direction of the propeller thrust are adjusted to balance the wind resistance, so as to realize continuous monitoring at fixed-point position. In this paper, it is assumed that the airship mainly relies on the electric propeller device to provide the thrust, which can be quickly adjusted in accordance with the wind direction and task position [26]. Since the working height of the airship is maintained, we only need to consider its horizontal movement as shown in Figure 2.Figure 2
The plane motion of high-altitude airship.Normally, the wind field in near-space is stable; hence, the wind speed can be decomposed along the axial direction and normal direction of the airship. Consider(3)Wa=Wcos(θ2-θ1),Wn=Wsin(θ2-θ1),
where W is the velocity of wind, θ1 is the cruising direction of airship, and θ2 is the direction of wind field.The typical power-velocity model of airship is [24, 27, 28]:
(4)Pa=12ρV2/3(S-Wa)3CaPn=12ρV2/3Wn3Cn,
where ρ is the air density, V2/3 is the characteristic area of airship based on its volume V, S is the airship’s cruising speed relative to the ground, and Ca and Cn refer to the aerodynamic coefficients.


## 2.3. The Optimization Objectives

LetX=(x1,x2,…,xn), Y=[yi,j]n×n, and S=[Si,j](n+1)×(n+1) be the decision variables. If taski is effectively performed, then it is a value task (assume that xi=1); otherwise, let xi=0. If xixj=1 and taski is the preceding task of taskj, then let yi,j=1; otherwise, let yi,j=0.The primary optimization objective of the tasks scheduling problem on the high-altitude airship is to maximize the guarantee rationER(X,Y,S):
(5)ER(X,Y,S)=1n∑i=1nxi.The total energy consumptionEntotal(X,Y,S) should be minimized on the base of the maximization of ER(X,Y,S). Entotal(X,Y,S) includes two parts; Enactive(X,Y,S) and Enstatic(X,Y,S) are the energy consumptions caused by cruising and balance resistance in the suspension position, respectively.According to (2)–(4), the energy consumption of airship’s cruising from siti to sitj is
(6)eni,jactive=ρV2/3Cndi,j2ηSi,j|Wsin(θ2-θ1)|3+ρV2/3Cadi,j2ηSi,j|Si,j-Wcos(θ2-θ1)|3.If the high-altitude airship locate in the observation position oftaski, the energy consumption caused by resisting the effect of wind is
(7)enistatic=ρV2/3Cati2η|Wcos(θ2-θ1)|3+ρV2/3Cnti2η|Wsin(θ2-θ1)|3.According to (6) and (7), the total energy consumption of airship during execution of the tasks is
(8)Entotal(X,Y,S)=Enactive(X,Y,S)+Enstatic(X,Y,S)=∑i=1n∑j=1nyi,jeni,jactive+∑i=1nxienistatic.


## 2.4. The Programming Model

In the typical route planning of UAV, it is necessary to simultaneously consider the maximum turning angle, maximum climbing angle, minimum flight altitude, minimum path length, and other constraints. The purpose is to ensure that the cruising path can meet the aircraft’s maneuvering characteristics and reduce the probability of damaging the aircraft in the no-fly zone and threatened area. As for the high-altitude airship in this paper, its working space has no spatial constraint, so the no-fly zone is an unnecessary consideration. At the same time, the low speed and slow dynamics provide the airship with a large-angle cornering ability, and it is also unnecessary to consider the minimum path length due to its suspension ability. Moreover, the threatened area of the high-altitude airship can be ignored due to the difficulty of being captured by the radar. However, the main constraints of tasks scheduling on the high-altitude airship are listed as follows.Constraint 1. The high-altitude airship only executes the observation task within its active period.Constraint 2. Each task can be executed only once, and it must be completed before its deadline.Constraint 3. If a task can be executed, the execution time should be no less than the required continuous working time.Constraint 4. Only one preceding task or one following task of each task is allowable at most.Constraint 5. The preemptive service in the task execution is prohibited. Once the execution starts, the process cannot be terminated until completion.Constraint 6. Before performing a new task, the airship needs sufficient time to change the observation position.Constraint 7. For any two tasks to be executed, the certain priority order exists.Constraint 8. The moving processes of airship only exist in different observation positions.Constraint 9. The cruising speed of high-altitude airship in each path segment cannot be higher than the maximum cruising speed.LetR1, R2, and R2 be the feasible solution space of the decision variables X, Y, and S. In the separate optimization of ER(X,Y,S), their optimal solution spaces are Q1, Q2, and Q3, respectively. The programming model of this scheduling problem is given as follows:
(9)Z1(X,Y,S)=maxX∈R1,Y∈R2,S∈R3{1n∑i=1nxi},Z2(X,Y,S)=minX∈Q1,Y∈Q2,S∈Q3{∑i=1n∑j=1nyi,jeni,jactive+∑i=1nxienistatic}s.t.{[tbi,tei]⊂[tstart,tend]∑i=1nxi≤1,tei≤tditei-tbi≥ti,ifxi=1∑i=1nyi,j≤1,∑j=1nyi,j≤1[tbi,tei]∩[tbj,tej]=∅,ifxi·xj=1tei+di,jSi,j-K(1-yi,j)≤tbjyi,j·yj,i=0∑i=1nyi,i=0Si,j≤Smaxxi,yi,j∈{0,1}∀i,j∈{1,2,…,m},k∈{1,2,…,n},
where the former nine inequality formulas correspond to the aforementioned constraints, respectively, and the tenth inequality formula restricts the range of the decision variables.


## 3. Scheduling Algorithms

There exist numerous constraints in the tasks scheduling problem, so it is difficult to solve this problem directly. Therefore, the hierarchical optimization can be used to convert the original problem to the following sub-problems.(1)
Determine the priority execution order of the tasks, that is, the task sorting problem, which can be solved by the OSR algorithm.(2)
Select the observation tasks for the airship, that is, the value tasks detection problem, which can be solved by the VTD algorithm.(3)
Adjust the planning scheme to reduce energy consumption of the airship, that is, the energy conservation problem, which can be solved by the EAS algorithm.Firstly, the task guarantee ration is the primary optimization objective of this scheduling problem. Thus, this paper considers that maximum cruising speed should be used by the airship to execute tasks as frequently as possible. Then, the distributions of value tasks are tested, and the initial scheduling scheme of the original problem is obtained. On this basis, energy conservation is regarded as another optimization goal. The cruising speed of airship at each leg is adjusted, and the execution time of all value tasks is updated.Theorem 2.
The feasible solution of the original problem is expressed with two-tuplesSP=〈vq,sq〉, where vq={taskv1,taskv2,…,taskvn} is the task set rearranged by priority execution order and sq={S0,v1,Sv1,v2,…,Sv(n-1},vn} is the speed set of airship at each leg.Theorem 3.
For any feasible solutionsSP1 and SP2, if SP1 is superior to SP2, then SP1⊳SP2 or SP2⊲SP1; if SP1 is inferior to SP2, then SP1⊲SP2 or SP2⊳SP1; otherwise, SP1=SP2.The comparison method of any two feasible solutionsSP1 and SP2 is presented as follow:SP1⊳SP2,ifER(SP1)>ER(SP2),SP1⊳SP2,ifER(SP1)=ER(SP2),Entotal(SP1)<Entotal(SP2),SP1=SP2,ifER(SP1)=ER(SP2),Entotal(SP1)=Entotal(SP2),SP1⊲SP2,otherwise.Theorem 4.
For any effective solutionSP1=〈vq,sq〉 and feasible solution SP2=〈vq*,sq*〉, if SP1⊲SP2, then SP2 is an optimal solution of SP1.The conventional methods to obtain effective solutions including (a) improving the priority execution order of tasks in order to obtain more value tasks; (b) reducing energy consumption by adjusting the cruising speed of airship on the basis of ensuring the quantity of value tasks. The previous methods are realized by the OSR algorithm and EAS algorithm, respectively.


### 3.1. The OSR Algorithm

The OSR algorithm sorts all elements inTask to get the priority execution order of tasks, and the guarantee ration is the primary optimization objective. Although all tasks are ranked, only part of the tasks can be observed timely; that is, the ranking result is only available for value tasks tested by the VTD algorithm, and it shows the observation sequence of executable tasks. The analysis of sorting rules in two tasks is as follows.LetTask={task1,task2} denote the task set, T0 the current timing instant and sit0 the initial position of airship. Given two feasible solutions SP1=〈vq1,sq〉 and SP2=〈vq2,sq〉, where vq1={task1,task2}, vq2={task2,task1} and sq={Smax,Smax}, there is no harm in assuming that td1-d0,2Smax-1≥td2-d0,1Smax-1, and then, the relationship between ER(SP1) and ER(SP2) is discussed as follows.(a)
Iftask1 and task2 are both value tasks in SP1, then
(10)T0+d0,1Smax-1+t1≤td1,T0+(d0,1+d1,2)Smax-1+t1+t2≤td2.
In accordance with the assumption, we can get
(11)T0+d0,2Smax-1+t2≤td2,T0+(d0,2+d2,1)Smax-1+t2+t1≤td1.
Then, task1 and task2 are both value tasks in SP2; thereby, ER(SP1)=ER(SP2).(b)
As forSP1, if task1 is a value task while task2 is an invalid task, then:
(12)T0+d0,1Smax-1+t1≤td1,T0+(d0,1+d1,2)Smax-1+t1+t2>td2.
As for SP2, if task2 is a value task, then ER(SP1)≤ER(SP2); if task2 is an invalid task, we can still ensure that ER(SP1)=ER(SP2) due to T0+d0,1Smax-1+t1≤td1.(c)
As forSP1, if task1 is an invalid task while task2 is a value task, then
(13)T0+d0,1Smax-1+t1>td1,T0+d0,2Smax-1+t2≤td2.
As for SP2, task2 is a value task; thereby, ER(SP1)≤ER(SP2).(d)
Iftask1 and task2 are both invalid tasks in SP1, then
(14)T0+d0,1Smax-1+t1>td1,T0+d0,2Smax-1+t2>td2.
There is an equation ER(SP1)=ER(SP2).Iftd1-d0,2Smax-1≤td2-d0,1Smax-1, the similar method can be used to analyze the sorting rules. However, the following conclusions can be acquired.(i)
Iftd1-d0,2Smax-1≥td2-d0,1Smax-1, then ER(SP1)≤ER(SP2).(ii)
Iftd1-d0,2Smax-1≤td2-d0,1Smax-1, then ER(SP1)≥ER(SP2).According to the previous conclusions, the OSR algorithm is proposed to solve the task sorting problem. The main steps of OSR are presented as in Algorithm1.Algorithm 1:Pseudocode of OSR algorithm.
(
1
)  Queue←Task; NQueue←NULL; point0←sit0;
(
2
)  while  Queue≠NULL  do
(
3
) Let set G←NULL
(
4
)  for each task taski in Queuedo
(
5
)  Calculate the distance li,0 beween point0 and taski;
(
6
)  Addgi=tdi+l0,iSmax-1 to set G;
(
7
)   end  for
(
8
)   gk=mingi∈G{gi}; /*Select the minimal member in G*/
(
9
)   Search the last element taskr in NQueue;/*The set
NQueue is used to save the execution equence*/
(
10
)  Let taskk≻taskr;/*Assign the order for taskk*/
(
11
)  Remove taskk from Queue to NQueue, and taskk is the last element in NQueue;
(
12
)  point0←sitk;
(
13
) endwhileThe task sorting problem is a combinatorial optimization problem. At present, there is no algorithm which can be used to obtain the optimal solution within the polynomial time complexity. Similar to the EDF algorithm, the OSR algorithm is a heuristic algorithm, which only generates the optimal scheme instead of a common optimized scheme. The effectiveness of the OSR algorithm will be verified in the subsequent experiments.


### 3.2. The VTD Algorithm

According to the task sorting result obtained by OSR, the deadline constraints for each element in setTask are checked in order. The value tasks in set Task are considered as the key nodes, and the cruising path optimization method between the successive key nodes can be learned from [17, 29, 30].Theorem 5.
If bothtaski and taskj are value tasks, and taskj is arranged to be executed just next to taski, then taski is called the preceding task of taskj, and taskj is the following task of taski.
Considertaskj to be the following task of taski, so the execution time interval of taskj is presented as follows:
(15)tbj=tei+di,jSi,j-1,tej=tbj+tj.Assume that the airship has maximal cruising speed while solving the value tasks detection problem based on the hierarchy architecture. The pseudocode of VTD is shown as Algorithm2.Algorithm 2:Pseudocode of VTD algorithm.
(
1
)   idle←0; VQueue←NULL; point0←sit0;/*Initialization*/
(
2
)   for each task taski∈NQueue in sequence do
(
3
)  point1←siti;/*Search the value task in NQueue*/
(
4
)  Calculate the distance L0,1 between point0 and point1;
(
5
)  if  idle+L0,1Smax-1+ti≤tdi  then/*taski is a value task*/
(
6
)   Calculate tbi and tei by (15);
(
7
)   idle←tei; point0←point1;
(
8
)   Add taski to the value task set  VQueue;
(
9
)  else
(
10
) Reject taski;/*taski is a invalid task, which can not been executed in its deadline*/
(
11
)
end  if
(
12
) end  for
(
13
) for  each  task  taskgi∈G in sequence do
(
14
)  Delete taskgi from G, and set xgi←1; /*Assign value to the decision vector X*/
(
15
)  if  G≠NULL  then
(
16
)   Select the first task taskgj in Gk; /*taskgj is the next value task behind taskgi*/
(
17
)   Let ygi,gj←1;
(
18
)  end  if
(
19
) end  for


### 3.3. The EAS Algorithm

Iftaski is executed, the power consumption of the high-altitude airship caused by cruising in speed S* to the position sitj and to observe taskj can be calculated as
(16)energyi,j(S*)=eni,jactive+enjstatic=αCa[di,jS*|Wcos(θ2-θ1)|3ti+di,jS*|S*-Wcos(θ2-θ1)|3]+αCn(di,jS*+ti)|Wsin(θ2-θ1)|3,
where α=ρV2/3(2η)-1 is a constant.If the cruising speed of airship is limited atSi,j∈[Smin,Smax], the optimal cruising speed of airship between siti and sitj will be S*={S*∣energyi,j(S*)≤energyi,j(S),forallS*,S∈[Smin,Smax]}. For the convenience to describe this problem, we define the function of the optimal cruising speed (value range: [Smin,Smax]) between siti and sitj as
(17)S*=OPTEi,j(Smin,Smax).Theorem 6.
If[S1,S2]⊃[S3,S4],Sa=OPTEi,j(S1,S2), and Sb=OPTEi,j(S3,S4), then one can get energyi,j(Sa)≤energyi,j(Sb).Proof.
SinceSa=OPTEi,j(S1,S2), we obtain that energyi,j(Sa)≤energyi,j(S),forallS∈[S1,S2]. For Sb∈[S1,S2], energyi,j(Sa)≤energyi,j(Sb) exists.Inference 1. If S3∈[S1,S2], S4=OPTEi,j(S1,S2), then energyi,j(S3)≥energyi,j(S4) is proven.Proof.
It can be considered thatS3=OPTEi,j(S3,S3). According to Theorem 6, since [S3,S3]∈[S1,S2], so Theorem 6 exists.Assume thatSP=〈vq,sq〉 is an efficient solution, where vq={taskv1,taskv2,…,taskvg}, and sq={S0,v1,Sv1,v2,…,Sv(g-1},vg}. Let SP*=〈vq,sq*〉 denote the improved solution of SP, and it is obtained by the EAS listed as followsStep 1.
Lettask0  denote a virtual task, and set t0←0, tb0←0, tb0←0, i←0.Step 2.
On the premise of ensuring the value tasks, the speed range[Svi,v(i+1)min,Svi,v(i+1)min] of airship cruised from sitvi to sitv(i+1) is calculated.Step 3.
The optimal speedSvi,v(i+1)*=OPTE(Svi,v(i+1)min,Svi,v(i+1)min) of the airship cruised from sitvi to sitv(i+1) is calculated by (17). Let Svi,v(i+1)←Svi,v(i+1)* and i←i+1.Step 4.
The execution period oftaskvi is updated by (15).Step 5.
Ifi≤g, go to Step 2; otherwise, the iteration ends.In the previous algorithm,Smax is the maximum cruising speed of airship along each leg. The minimum cruising speed of airship from sitvi to sitv(i+1) is
(18)Svi,v(i+1)min=maxj=i+1,…,g{∑k=ij-1dvk,v(k+1)tdvj-∑k=ij-1tv(k+1)-tevi}.Theorem 7.
As fortaski and taskj, if taski is priority to taskj, let taski≻taskj or taskj≺taski; otherwise, let taski≺taskj or taskj≻taski.Theorem 8.
Assume thatSP=〈vq,sq〉 is the optimized solution obtained by the EAS algorithm, and then for all taskvi∈vq={taskv1,taskv2,…,taskvg},Svi,v(i+1)min≤Smax exists.Proof.
For alltaskvj∈vq, taskvj≺taskvi, since taskvj is a value task, we obtain that
(19)tevi+∑k=ij-1(tv(k+1)+dvk,v(k+1)Smax-1)≤tdvj.
We may reach the following conclusion:(20)tdvj-∑k=ij-1tv(k+1)-tevi≥∑k=ij-1dvk,v(k+1)Smax-1.
In other words,(21)∑k=ij-1dvk,v(k+1)tdvj-∑k=ij-1tv(k+1)-tevi≤Smax.
For the discretion oftaskvj, we may find that
(22)Svi,v(i+1)min=maxj=i+1,…,g{∑k=ij-1dvk,v(k+1)tdvj-∑k=ij-1tv(k+1)-tevi}≤Smax.
Hereby, Theorem8 holds.Theorem 9.
The optimized solutionSP=〈vq,sq〉 obtained by EAS algorithm is still an efficient solution.Proof.
According to Theorem3, if SP=〈vq,sq〉 is still an efficient solution, the following conditions are satisfied: (a) for all taskvi∈vq is a value task; (b) for all Svi,v(i+1)∈sq is no larger than Smax.
As for alltaskvi∈vq, according to (18), we may find that
(23)Svi,v(i+1)min=maxj=i+1,…,g{∑k=ij-1dvk,v(k+1)tdvj-∑k=ij-1tv(k+1)-tevi}≥dvi,v(i+1)tdv(i+1)-tv(i+1)-tevi.
In other words,(24)dvi,v(i+1)Svi,v(i+1)min≤tdv(i+1)-tv(i+1)-tevi.
So(25)tevi+dvi,v(i+1)Svi,v(i+1)+tv(i+1)≤tevi+dvi,v(i+1)Svi,v(i+1)min+tv(i+1)=tdv(i+1).
Thus, it can be regarded thattaskvi∈vq is a value task. According to Theorem 8, for all taskvi∈vq, there always exists Svi,v(i+1)min≤Smax. As for this, there exist Svi,v(i+1)∈[Svi,v(i+1)min,Smax] and Svi,v(i+1)≤Smax.
In conclusion, Theorem9 is valid.The feasible solution can be converted into an efficient solution by VTD algorithm, so as to figure out the decision variableX, Y; on this basis, the efficient solution can be transformed into an optimal solution by EAS strategy in order to figure out the decision variable S. According to the decision variables, the power consumption of optimized solution SP can be described as follows:
(26)Entotal(SP)=∑taski∈Task∑taskj∈Taskyi,jenergyi,j(Si,j).Conclusion.
IfSP* is the optimized solution of the efficient solution SP, there exists ER(SP)=ER(SP*).Proof.
According to Theorem9, SP* is still an efficient solution, so that SP and SP* have the same value tasks that is, ER(SP)=ER(SP*) exists.Theorem 10.
Assume thatSP=〈vq,sq〉 is an efficient solution and SP*=〈vq,sq*〉 is an optimized solution obtained with EAS algorithm; as for this, SP*⊳SP exists.Proof.
For anySvi,v(i+1)*∈sq*, there is Svi,v(i+1)*∈[Svi,v(i+1)min,Smax]. According to Theorem 6, energyvi,v(i+1)(Svi,v(i+1)*)≤energyvi,v(i+1)(Smax) is exists. Therefore, we can get
(27)Entotal(SP*)=∑taski∈Task∑taskj∈Taskyi,jenergyi,j(Si,j*)≤∑taski∈Task∑taskj∈Taskyi,jenergyi,j(Smax)=Entotal(SP).
Based on Conclusion1, ER(SP)=ER(SP*); hereby, SP*⊳SP exists.Theorem10 is actually an authentication to the effectiveness of the EAS algorithm. In other words, if the efficient solution is adjusted in accordance with the EAS algorithm, the obtained result is always more optimal than the original scheme.


## 3.1. The OSR Algorithm

The OSR algorithm sorts all elements inTask to get the priority execution order of tasks, and the guarantee ration is the primary optimization objective. Although all tasks are ranked, only part of the tasks can be observed timely; that is, the ranking result is only available for value tasks tested by the VTD algorithm, and it shows the observation sequence of executable tasks. The analysis of sorting rules in two tasks is as follows.LetTask={task1,task2} denote the task set, T0 the current timing instant and sit0 the initial position of airship. Given two feasible solutions SP1=〈vq1,sq〉 and SP2=〈vq2,sq〉, where vq1={task1,task2}, vq2={task2,task1} and sq={Smax,Smax}, there is no harm in assuming that td1-d0,2Smax-1≥td2-d0,1Smax-1, and then, the relationship between ER(SP1) and ER(SP2) is discussed as follows.(a)
Iftask1 and task2 are both value tasks in SP1, then
(10)T0+d0,1Smax-1+t1≤td1,T0+(d0,1+d1,2)Smax-1+t1+t2≤td2.
In accordance with the assumption, we can get
(11)T0+d0,2Smax-1+t2≤td2,T0+(d0,2+d2,1)Smax-1+t2+t1≤td1.
Then, task1 and task2 are both value tasks in SP2; thereby, ER(SP1)=ER(SP2).(b)
As forSP1, if task1 is a value task while task2 is an invalid task, then:
(12)T0+d0,1Smax-1+t1≤td1,T0+(d0,1+d1,2)Smax-1+t1+t2>td2.
As for SP2, if task2 is a value task, then ER(SP1)≤ER(SP2); if task2 is an invalid task, we can still ensure that ER(SP1)=ER(SP2) due to T0+d0,1Smax-1+t1≤td1.(c)
As forSP1, if task1 is an invalid task while task2 is a value task, then
(13)T0+d0,1Smax-1+t1>td1,T0+d0,2Smax-1+t2≤td2.
As for SP2, task2 is a value task; thereby, ER(SP1)≤ER(SP2).(d)
Iftask1 and task2 are both invalid tasks in SP1, then
(14)T0+d0,1Smax-1+t1>td1,T0+d0,2Smax-1+t2>td2.
There is an equation ER(SP1)=ER(SP2).Iftd1-d0,2Smax-1≤td2-d0,1Smax-1, the similar method can be used to analyze the sorting rules. However, the following conclusions can be acquired.(i)
Iftd1-d0,2Smax-1≥td2-d0,1Smax-1, then ER(SP1)≤ER(SP2).(ii)
Iftd1-d0,2Smax-1≤td2-d0,1Smax-1, then ER(SP1)≥ER(SP2).According to the previous conclusions, the OSR algorithm is proposed to solve the task sorting problem. The main steps of OSR are presented as in Algorithm1.Algorithm 1:Pseudocode of OSR algorithm.
(
1
)  Queue←Task; NQueue←NULL; point0←sit0;
(
2
)  while  Queue≠NULL  do
(
3
) Let set G←NULL
(
4
)  for each task taski in Queuedo
(
5
)  Calculate the distance li,0 beween point0 and taski;
(
6
)  Addgi=tdi+l0,iSmax-1 to set G;
(
7
)   end  for
(
8
)   gk=mingi∈G{gi}; /*Select the minimal member in G*/
(
9
)   Search the last element taskr in NQueue;/*The set
NQueue is used to save the execution equence*/
(
10
)  Let taskk≻taskr;/*Assign the order for taskk*/
(
11
)  Remove taskk from Queue to NQueue, and taskk is the last element in NQueue;
(
12
)  point0←sitk;
(
13
) endwhileThe task sorting problem is a combinatorial optimization problem. At present, there is no algorithm which can be used to obtain the optimal solution within the polynomial time complexity. Similar to the EDF algorithm, the OSR algorithm is a heuristic algorithm, which only generates the optimal scheme instead of a common optimized scheme. The effectiveness of the OSR algorithm will be verified in the subsequent experiments.


## 3.2. The VTD Algorithm

According to the task sorting result obtained by OSR, the deadline constraints for each element in setTask are checked in order. The value tasks in set Task are considered as the key nodes, and the cruising path optimization method between the successive key nodes can be learned from [17, 29, 30].Theorem 5.
If bothtaski and taskj are value tasks, and taskj is arranged to be executed just next to taski, then taski is called the preceding task of taskj, and taskj is the following task of taski.
Considertaskj to be the following task of taski, so the execution time interval of taskj is presented as follows:
(15)tbj=tei+di,jSi,j-1,tej=tbj+tj.Assume that the airship has maximal cruising speed while solving the value tasks detection problem based on the hierarchy architecture. The pseudocode of VTD is shown as Algorithm2.Algorithm 2:Pseudocode of VTD algorithm.
(
1
)   idle←0; VQueue←NULL; point0←sit0;/*Initialization*/
(
2
)   for each task taski∈NQueue in sequence do
(
3
)  point1←siti;/*Search the value task in NQueue*/
(
4
)  Calculate the distance L0,1 between point0 and point1;
(
5
)  if  idle+L0,1Smax-1+ti≤tdi  then/*taski is a value task*/
(
6
)   Calculate tbi and tei by (15);
(
7
)   idle←tei; point0←point1;
(
8
)   Add taski to the value task set  VQueue;
(
9
)  else
(
10
) Reject taski;/*taski is a invalid task, which can not been executed in its deadline*/
(
11
)
end  if
(
12
) end  for
(
13
) for  each  task  taskgi∈G in sequence do
(
14
)  Delete taskgi from G, and set xgi←1; /*Assign value to the decision vector X*/
(
15
)  if  G≠NULL  then
(
16
)   Select the first task taskgj in Gk; /*taskgj is the next value task behind taskgi*/
(
17
)   Let ygi,gj←1;
(
18
)  end  if
(
19
) end  for


## 3.3. The EAS Algorithm

Iftaski is executed, the power consumption of the high-altitude airship caused by cruising in speed S* to the position sitj and to observe taskj can be calculated as
(16)energyi,j(S*)=eni,jactive+enjstatic=αCa[di,jS*|Wcos(θ2-θ1)|3ti+di,jS*|S*-Wcos(θ2-θ1)|3]+αCn(di,jS*+ti)|Wsin(θ2-θ1)|3,
where α=ρV2/3(2η)-1 is a constant.If the cruising speed of airship is limited atSi,j∈[Smin,Smax], the optimal cruising speed of airship between siti and sitj will be S*={S*∣energyi,j(S*)≤energyi,j(S),forallS*,S∈[Smin,Smax]}. For the convenience to describe this problem, we define the function of the optimal cruising speed (value range: [Smin,Smax]) between siti and sitj as
(17)S*=OPTEi,j(Smin,Smax).Theorem 6.
If[S1,S2]⊃[S3,S4],Sa=OPTEi,j(S1,S2), and Sb=OPTEi,j(S3,S4), then one can get energyi,j(Sa)≤energyi,j(Sb).Proof.
SinceSa=OPTEi,j(S1,S2), we obtain that energyi,j(Sa)≤energyi,j(S),forallS∈[S1,S2]. For Sb∈[S1,S2], energyi,j(Sa)≤energyi,j(Sb) exists.Inference 1. If S3∈[S1,S2], S4=OPTEi,j(S1,S2), then energyi,j(S3)≥energyi,j(S4) is proven.Proof.
It can be considered thatS3=OPTEi,j(S3,S3). According to Theorem 6, since [S3,S3]∈[S1,S2], so Theorem 6 exists.Assume thatSP=〈vq,sq〉 is an efficient solution, where vq={taskv1,taskv2,…,taskvg}, and sq={S0,v1,Sv1,v2,…,Sv(g-1},vg}. Let SP*=〈vq,sq*〉 denote the improved solution of SP, and it is obtained by the EAS listed as followsStep 1.
Lettask0  denote a virtual task, and set t0←0, tb0←0, tb0←0, i←0.Step 2.
On the premise of ensuring the value tasks, the speed range[Svi,v(i+1)min,Svi,v(i+1)min] of airship cruised from sitvi to sitv(i+1) is calculated.Step 3.
The optimal speedSvi,v(i+1)*=OPTE(Svi,v(i+1)min,Svi,v(i+1)min) of the airship cruised from sitvi to sitv(i+1) is calculated by (17). Let Svi,v(i+1)←Svi,v(i+1)* and i←i+1.Step 4.
The execution period oftaskvi is updated by (15).Step 5.
Ifi≤g, go to Step 2; otherwise, the iteration ends.In the previous algorithm,Smax is the maximum cruising speed of airship along each leg. The minimum cruising speed of airship from sitvi to sitv(i+1) is
(18)Svi,v(i+1)min=maxj=i+1,…,g{∑k=ij-1dvk,v(k+1)tdvj-∑k=ij-1tv(k+1)-tevi}.Theorem 7.
As fortaski and taskj, if taski is priority to taskj, let taski≻taskj or taskj≺taski; otherwise, let taski≺taskj or taskj≻taski.Theorem 8.
Assume thatSP=〈vq,sq〉 is the optimized solution obtained by the EAS algorithm, and then for all taskvi∈vq={taskv1,taskv2,…,taskvg},Svi,v(i+1)min≤Smax exists.Proof.
For alltaskvj∈vq, taskvj≺taskvi, since taskvj is a value task, we obtain that
(19)tevi+∑k=ij-1(tv(k+1)+dvk,v(k+1)Smax-1)≤tdvj.
We may reach the following conclusion:(20)tdvj-∑k=ij-1tv(k+1)-tevi≥∑k=ij-1dvk,v(k+1)Smax-1.
In other words,(21)∑k=ij-1dvk,v(k+1)tdvj-∑k=ij-1tv(k+1)-tevi≤Smax.
For the discretion oftaskvj, we may find that
(22)Svi,v(i+1)min=maxj=i+1,…,g{∑k=ij-1dvk,v(k+1)tdvj-∑k=ij-1tv(k+1)-tevi}≤Smax.
Hereby, Theorem8 holds.Theorem 9.
The optimized solutionSP=〈vq,sq〉 obtained by EAS algorithm is still an efficient solution.Proof.
According to Theorem3, if SP=〈vq,sq〉 is still an efficient solution, the following conditions are satisfied: (a) for all taskvi∈vq is a value task; (b) for all Svi,v(i+1)∈sq is no larger than Smax.
As for alltaskvi∈vq, according to (18), we may find that
(23)Svi,v(i+1)min=maxj=i+1,…,g{∑k=ij-1dvk,v(k+1)tdvj-∑k=ij-1tv(k+1)-tevi}≥dvi,v(i+1)tdv(i+1)-tv(i+1)-tevi.
In other words,(24)dvi,v(i+1)Svi,v(i+1)min≤tdv(i+1)-tv(i+1)-tevi.
So(25)tevi+dvi,v(i+1)Svi,v(i+1)+tv(i+1)≤tevi+dvi,v(i+1)Svi,v(i+1)min+tv(i+1)=tdv(i+1).
Thus, it can be regarded thattaskvi∈vq is a value task. According to Theorem 8, for all taskvi∈vq, there always exists Svi,v(i+1)min≤Smax. As for this, there exist Svi,v(i+1)∈[Svi,v(i+1)min,Smax] and Svi,v(i+1)≤Smax.
In conclusion, Theorem9 is valid.The feasible solution can be converted into an efficient solution by VTD algorithm, so as to figure out the decision variableX, Y; on this basis, the efficient solution can be transformed into an optimal solution by EAS strategy in order to figure out the decision variable S. According to the decision variables, the power consumption of optimized solution SP can be described as follows:
(26)Entotal(SP)=∑taski∈Task∑taskj∈Taskyi,jenergyi,j(Si,j).Conclusion.
IfSP* is the optimized solution of the efficient solution SP, there exists ER(SP)=ER(SP*).Proof.
According to Theorem9, SP* is still an efficient solution, so that SP and SP* have the same value tasks that is, ER(SP)=ER(SP*) exists.Theorem 10.
Assume thatSP=〈vq,sq〉 is an efficient solution and SP*=〈vq,sq*〉 is an optimized solution obtained with EAS algorithm; as for this, SP*⊳SP exists.Proof.
For anySvi,v(i+1)*∈sq*, there is Svi,v(i+1)*∈[Svi,v(i+1)min,Smax]. According to Theorem 6, energyvi,v(i+1)(Svi,v(i+1)*)≤energyvi,v(i+1)(Smax) is exists. Therefore, we can get
(27)Entotal(SP*)=∑taski∈Task∑taskj∈Taskyi,jenergyi,j(Si,j*)≤∑taski∈Task∑taskj∈Taskyi,jenergyi,j(Smax)=Entotal(SP).
Based on Conclusion1, ER(SP)=ER(SP*); hereby, SP*⊳SP exists.Theorem10 is actually an authentication to the effectiveness of the EAS algorithm. In other words, if the efficient solution is adjusted in accordance with the EAS algorithm, the obtained result is always more optimal than the original scheme.


## 4. Experimental Analysis

In this section, simulation experiment is conducted to illustrate the effectiveness of the proposed method. For VTD to be the precise algorithm, we only analyze the effectiveness of OSR and EAS.


### 4.1. Experimental Parameters

The proposed algorithms are implemented by Matlab2007 on a PC with Pentium IV 3.06 GHz CPU, 2 GB memory. As far as we know, there are no accepted benchmarks yet in scheduling problem of high-altitude airships, so the random models are used to construct the application scenario and simulate the battlefield area with 200 × 300 km2.The main parameters for high-altitude airships simulation are listed in Table1.Table 1
Parameters for high-altitude airship.
Parameters
Value
Active period
[6, 18] h
Maximum speed
90 km/h
Efficiency index
0.5
Duration time
[1, 6] minWe divide task number into ten levels from 30 to 300 for offering the flexibility to simulate the various workloads on high-altitude airships. The positions of tasks are generated randomly in battlefield, and their deadline is distributed in a uniform distribution spanning over the active period of airship.Table2 gives the configuration of environment parameters employed in our experiment.Table 2
Parameters for environment.
Parameters
Value
Wind direction
30°
Wind speed
5 m/s
Aerodynamic coefficientCa
0.025Additionally, in order to reduce the calculation complexity of experiments, we let the constantα of (16) be equal to “1.” Then the calculation results of total energy consumption are relation values instead of real values.


### 4.2. The Effectiveness of the OSR Algorithm

The heuristic algorithm OSR is employed to solve the task sorting problem. The effectiveness of this algorithm will directly affect the number of value tasks. In order to test the performance of the OSR algorithm, we have compared it with the EDF algorithm and Greedy algorithm.Figure3 shows that OSR obtains a higher guarantee ration than EDF and Greedy. In various task scales, the guarantee ration obtained by OSR can be 12.84% higher than that of EDF and 8.89% higher than that of Greedy, which shows a very high scheduling performance. It can be seen in Figure 3(a) that as the quantity of tasks increases, the number of value tasks also increases gradually. However, the task guarantee ration shows a descending tendency. As the quantity of tasks increases, the number of tasks compatible with the airship observation also increases, so that more executable tasks appear. However, the observation capability of airship is limited. Thus, the increasing rate of value task will be much lower than the growth speed of task as the quantity of tasks increases to a certain degree. As for this, the task guarantee ration tends to decrease. As is shown in Figure 3(b), as the task quantity increases, the total energy consumption of airship also increases. However, when the task amount reaches the range of 30~120, the value task amount has a higher growth speed, leading to a sharp increase in energy consumption. By contrast, when task amount is around 120~300, the number of value tasks is nearly saturated, so that the growth of energy consumption slows down.The scheduling results of OSR algorithm.
(a)
Guarantee ration impact of task number
(b)
Total energy consumption impact of task number


### 4.3. The Effectiveness of the EAS Algorithm

The EAS algorithm is used to realize energy-saving optimization of the scheduling scheme based on the deadline distribution of value tasks. In order to test the performance of this algorithm, its scheduling results will be compared with the performance before optimization (called HSA algorithm), that is, to compare the optimized solution with the efficient solution. According to Conclusion1, the optimized solution has the same task guarantee ration as the efficient solution. As for this, the only parameter to be tested is the energy-saving performance of the EAS algorithm. The statistical indexes include the total energy consumption and energy consumption per tasks (ECPT).It can be observed in Figure4 that the total energy consumption of the EAS algorithm is always lower than that of the HSA algorithm in different task scales. This conclusion complies with Theorem 10. When keeping the same task guarantee ration, the total energy consumption of the EAS algorithm is 8.25% lower than that of the HSA algorithm, showing a higher energy saving performance. It can be seen in Figure 4(a) that the total energy consumption firstly increases sharply and then slows down as the task number increases. This phenomenon is in line with the analysis conclusion in Figure 3(b). The main reason for this trend is the variation tendency of the value task quantity. In Figure 4(b), we may find that ECPT reduces gradually as the task scale increases. As the area of battlefield is a constant, increase of the task scale will improve the density of task in the area. Therefore, the airship is able to execute more tasks within a short route, which in return reduces the energy consumption caused by cruising. In the meantime, we may find that the ECPT of the EAS algorithm is lower than that of the HSA algorithm in different task scales. This is because the EAS algorithm always adopts the most optimal cruising speed in each route, which reduces the energy consumption to the maximum degree.The scheduling results of EAS algorithm.
(a)
Total energy consumption impact of task number
(b)
ECPT impact of task number


## 4.1. Experimental Parameters

The proposed algorithms are implemented by Matlab2007 on a PC with Pentium IV 3.06 GHz CPU, 2 GB memory. As far as we know, there are no accepted benchmarks yet in scheduling problem of high-altitude airships, so the random models are used to construct the application scenario and simulate the battlefield area with 200 × 300 km2.The main parameters for high-altitude airships simulation are listed in Table1.Table 1
Parameters for high-altitude airship.
Parameters
Value
Active period
[6, 18] h
Maximum speed
90 km/h
Efficiency index
0.5
Duration time
[1, 6] minWe divide task number into ten levels from 30 to 300 for offering the flexibility to simulate the various workloads on high-altitude airships. The positions of tasks are generated randomly in battlefield, and their deadline is distributed in a uniform distribution spanning over the active period of airship.Table2 gives the configuration of environment parameters employed in our experiment.Table 2
Parameters for environment.
Parameters
Value
Wind direction
30°
Wind speed
5 m/s
Aerodynamic coefficientCa
0.025Additionally, in order to reduce the calculation complexity of experiments, we let the constantα of (16) be equal to “1.” Then the calculation results of total energy consumption are relation values instead of real values.


## 4.2. The Effectiveness of the OSR Algorithm

The heuristic algorithm OSR is employed to solve the task sorting problem. The effectiveness of this algorithm will directly affect the number of value tasks. In order to test the performance of the OSR algorithm, we have compared it with the EDF algorithm and Greedy algorithm.Figure3 shows that OSR obtains a higher guarantee ration than EDF and Greedy. In various task scales, the guarantee ration obtained by OSR can be 12.84% higher than that of EDF and 8.89% higher than that of Greedy, which shows a very high scheduling performance. It can be seen in Figure 3(a) that as the quantity of tasks increases, the number of value tasks also increases gradually. However, the task guarantee ration shows a descending tendency. As the quantity of tasks increases, the number of tasks compatible with the airship observation also increases, so that more executable tasks appear. However, the observation capability of airship is limited. Thus, the increasing rate of value task will be much lower than the growth speed of task as the quantity of tasks increases to a certain degree. As for this, the task guarantee ration tends to decrease. As is shown in Figure 3(b), as the task quantity increases, the total energy consumption of airship also increases. However, when the task amount reaches the range of 30~120, the value task amount has a higher growth speed, leading to a sharp increase in energy consumption. By contrast, when task amount is around 120~300, the number of value tasks is nearly saturated, so that the growth of energy consumption slows down.The scheduling results of OSR algorithm.
(a)
Guarantee ration impact of task number
(b)
Total energy consumption impact of task number


## 4.3. The Effectiveness of the EAS Algorithm

The EAS algorithm is used to realize energy-saving optimization of the scheduling scheme based on the deadline distribution of value tasks. In order to test the performance of this algorithm, its scheduling results will be compared with the performance before optimization (called HSA algorithm), that is, to compare the optimized solution with the efficient solution. According to Conclusion1, the optimized solution has the same task guarantee ration as the efficient solution. As for this, the only parameter to be tested is the energy-saving performance of the EAS algorithm. The statistical indexes include the total energy consumption and energy consumption per tasks (ECPT).It can be observed in Figure4 that the total energy consumption of the EAS algorithm is always lower than that of the HSA algorithm in different task scales. This conclusion complies with Theorem 10. When keeping the same task guarantee ration, the total energy consumption of the EAS algorithm is 8.25% lower than that of the HSA algorithm, showing a higher energy saving performance. It can be seen in Figure 4(a) that the total energy consumption firstly increases sharply and then slows down as the task number increases. This phenomenon is in line with the analysis conclusion in Figure 3(b). The main reason for this trend is the variation tendency of the value task quantity. In Figure 4(b), we may find that ECPT reduces gradually as the task scale increases. As the area of battlefield is a constant, increase of the task scale will improve the density of task in the area. Therefore, the airship is able to execute more tasks within a short route, which in return reduces the energy consumption caused by cruising. In the meantime, we may find that the ECPT of the EAS algorithm is lower than that of the HSA algorithm in different task scales. This is because the EAS algorithm always adopts the most optimal cruising speed in each route, which reduces the energy consumption to the maximum degree.The scheduling results of EAS algorithm.
(a)
Total energy consumption impact of task number
(b)
ECPT impact of task number


## 5. Conclusions

The emergency scheduling problem on the high-altitude airship for imaging observation tasks is a multiobjective combination optimization issue. In research, this paper mainly made the following contributions(1)
The task execution process of airship is analyzed, and the method to detect the value tasks is provided. In this paper, a power-velocity model was also constructed by considering the influence of the wind field on airship’s cruising. Moreover, the programming model of this problem is presented by proposing the optimal objectives and listing corresponding constraints.(2)
In order to simplify the solution process, a hierarchy optimization framework which divides the original problem into three subproblems is provided in the paper. As is shown in the experiment, this method is valid in reducing the solution space of the original problem, which is beneficial to efficiently obtain the scheduling scheme.(3)
The OSR algorithm is proposed to rank the priority execution order of tasks. The EDF algorithm and Greedy algorithm only use the deadline and cruising distance as the basis of task sorting. By contrast, the OSR algorithm considers both factors at the same time, so as to produce more reasonable results.(4)
The EAS algorithm is employed to optimize the scheduling scheme with minimum energy consumption as the objective. This algorithm can adjust the cruising speed of airship in each leg according to the deadline distribution of value tasks. As for this, the total energy consumption of airship can be reduced with no influence on the task guarantee ration. It is of great importance to extend the duration of airship in the observation activity.Also for our future work, we plan to develop the cooperation scheduling problem of multiple airship in observation activity. This research will be performed based on the research in this paper, with the aim to integrate observation resources and to improve the overall observation efficiency.



---

*Source: 242836-2013-06-22.xml*