A technology for scheduling of data exchange over bus with centralized control in onboard avionics systems

Abstract

In this paper, the problem of automatic scheduling of data exchange over a channel with centralized control in real-time avionics (RTA) systems is addressed. Examples of such channels are MIL STD-1553B multiplex data bus and Fibre Channel FC-AE-1553. Scheduling algorithms implementing greedy strategy and ant colony method are presented and evaluated experimentally. These algorithms support customization for specific requirements of the target onboard RTA system. Results of experimental evaluation demonstrate that the ant colony algorithm outperforms greedy algorithms on most of the considered classes of input data, with realistic technological requirements to data exchange. The proposed technology for data exchange scheduling is implemented in a tool system. Two case studies of industrial application of the system to the development of onboard real-time systems are described.

Keywords

scheduling distributed avionics systems real-time data exchange

Get full access to this article

View all access options for this article.

References

Aircraft internal time division command/response multiplex data bus U.S. Department of Defense, Washington, DC, 1978.

Guide to digital interface standards for military avionics applications. Technical report ASSC/110/6/2-Issue 3, Avionics Systems Standardization Committee, 2006.

Information Technology — Fibre Channel — Avionics Environment — Upper Layer Protocol and Profile based on MIL-STD-1553B Notice 2 (FC-AE-1553). Technical report INCITS/TR-42:2007, INCITS, 2007.

Lee

Y.-H.

Kim

Younis

Zhou

Scheduling tool and algorithm for integrated modular avionics systems. In Proceedings of the 19th Digital Avionics Systems Conference, Philadelphia, Pennsylvania, USA, 2000.

Goltz

H.-J.

Pieth

A tool for generating partition schedules of multiprocessor systems In Proceedings of the 23rd Workshop on

(Constraint) Logic programming, Potsdam, Germany, 2009.

RAPID RMA: the art of modeling real-time systems. Available from http://www.tripac.com/html/prod-fact-rrm.html

Douglass

B. P.

Doing hard time: developing real-time systems with UML, objects, frameworks, and patterns (Reading, Massachusetts, USA: Addison-Wesley 2004)

Coffman

E. G.

Eds. Computer and job-shop scheduling theory (New York: John Wiley & Sons 1976)

Lazarev

A. A.

Gafarov

E. R.

Scheduling theory: the total tardiness problem (in Russian), 2006 (Computing Centre of the Russian Academy of Sciences, Moscow, Russia)

10.

Lazarev

A. A.

Kvaratskhelia

Tchernykh

Solution algorithms for the total tardiness scheduling problem on a single machine. In Workshop Proceedings of the ENC04 International Conference, Colima, Mexico, 2004, pp. 474–480

11.

Della Croce

Grosso

Paschos

Lower bounds on the approximation ratios of leading heuristics for the single-machine total tardiness problem

J. Schedul. 7 200485–91

12.

Federgruen

Groenevelt

Preemptive scheduling of uniform machines by ordinary network flow technique

Manage. Sci. 323 1986341–349

13.

Tanaev

V. S.

Gordon

V. S.

Shafransky

Y. M.

Scheduling theory, single-stage systems (Dordrecht, The Netherlands: Kluwer 1994)

14.

Gus

D. S.

Furugyan

M. G.

Scheduling computations and memory load for single-processor hard real-time systems (in Russian)

Model. Control Process. (2004): 162–169

15.

Gus

D. S.

Furugyan

M. G.

Computation scheduling in multiprocessor real-time automatic control systems with constrained processor memory

Autom. Rem. Control 662 2005295–303

16.

Kostenko

V. A.

Scheduling algorithms for single-device real-time systems (in Russian) In Proceedings of the 3rd Conference on

Methods and tools for information processing, Moscow, Russia, 2009, pp. 245–258

17.

Kostenko

V. A.

Guryanov

E. S.

An algorithm for scheduling exchanges over a bus with centralized control and an analysis of its efficiency

Progr. Comp. Softw. 316 2005340–346

18.

Dorigo

Optimization, learning and natural algorithms PhD Thesis, Politechnico di Milano, Milano, 1992.

19.

Shtovba

S. D.

Ant algorithms: Theory and applications

Progr. Comp. Softw. 314 2005167–178

20.

Balashov

V. V.

Kostenko

V. A.

Smeliansky

R. L.

A tool system for automatic scheduling of data exchange in real-time distributed avionics systems In Proceedings of the 2nd EUCASS European Conference on

Aerospace sciences, Brussels, Belgium, 2007.

21.

Bakhmurov

A. G.

Balashov

V. V.

Chistolinov

M. V.

Smeliansky

R. L.

Volkanov

D. Y.

Youshchenko

N. V.

A hardware-in-the-loop simulation environment for integration of distributed avionics systems In Proceedings of the 3rd EUCASS European Conference on

Aerospace sciences, Versailles, France, 2009.

22.

Liu

C. L.

Layland

J. W.

Scheduling algorithms for multiprogramming in a hard-real-time environment

J. ACM 201 197346–61

23.

Bychkov

I. A.

Kostenko

V. A.

Problems of data exchange scheduling and network topology selection for arbitrated loop (in Russian) In Proceedings of the 3rd Conference on

Methods and tools for information processing, Moscow, Russia, 2009, pp. 204–214

24.

Balashov

V. V.

Recommendation generation algorithms for scheduling of data exchange through a channel with centralized control

J. Comp. Syst. Sci. Int. 466 2007887–894

25.

Balashov

V. V.

Shestov

P. E.

Recommendation generation for providing compatibility of requirements to data exchange over a bus with centralized control in real-time embedded systems (in Russian)In Proceedings of the 4th International Conference on

Parallel computations and control problems, Moscow, Russia, 2008, pp. 1385–1404