Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-25T16:51:24.465Z Has data issue: false hasContentIssue false
  • English
  • Français

A Method for Scheduling Receiver Tasks Based on Maximum Allowed Execution Time Dichotomy Search

Published online by Cambridge University Press:  14 October 2011

Wei Wu ,
Shao-jie Ni  and
Fei-xue Wang
Wei Wu*
Affiliation:
(Satellite Navigation R&D Centre, School of Electronic Science and Engineering, National Univ. of Defense Technology, Changsha, China, 410073)
Shao-jie Ni
Affiliation:
(Satellite Navigation R&D Centre, School of Electronic Science and Engineering, National Univ. of Defense Technology, Changsha, China, 410073)
Fei-xue Wang
Affiliation:
(Satellite Navigation R&D Centre, School of Electronic Science and Engineering, National Univ. of Defense Technology, Changsha, China, 410073)
*
(Email: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

In designing and developing navigation receiver embedded software, the correct scheduling of navigation tasks is critical for ensuring that a receiver works in the right way. If a receiver's timing scheduling becomes abnormal, it may lead to timing conflicts of the multi-tasking navigation receiver, which may seriously influence the system's performance of real-time features and functionalities. This paper models the timing scheduling of navigation receivers by extracting all important timing parameters including the execution time, period, deadline and priority etc., and focusing on the execution time. The maximum execution time of a navigation task relies on the design and implementation algorithms and the computing capability of the processor. The execution time parameter can be properly adjusted in receiver software design or even in the phase of the receiver requirement changes. On the other hand, the other parameters (i.e., the period, deadline and priority) mainly depend on the receiver's technical requirements, and usually these parameters are set to constant values. In this research, a novel off-line method based on the maximum allowed execution time dichotomy optimization is proposed, and the equilibrium rule is proposed to apply to the multi-task maximum allowed execution time dichotomy search and an analysis of time series of those parameters obtained from real observations of receiver tasks was also conducted. Results indicate that the relative equilibrium is more suitable to the multi-task scheduling of receiver navigation, compared to the absolute equilibrium. The proposed method provides a fast off-line scheduling approach for the top level task design of navigation receivers, and remarkably improves the development efficiency of receiver embedded software.

Keywords

Navigation ReceiverReal-time SchedulingExecution TimeDichotomy SearchEquilibrium Rule
Type
Research Article
Information
The Journal of Navigation , Volume 64 , Supplement S1: Chinese Beidou and the Next Generation GNSS , November 2011 , pp. S83 - S90
Copyright
Copyright © The Royal Institute of Navigation 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Elliott, D. K. and Christopher, J. H. (2007). Understanding GPS Principles and Applications(2nd), Publishing House of Electronics Industry.Google Scholar
Gold, K. and Brown, A. (2003). A Software GPS Receiver Application for Embedding in Software Definable Radios, Proceedings of the ION GPS/GNSS 2003, 2524–2531.Google Scholar
Kai, B., Dennis, M. A., Nicolaj, N., Peter, R. and Jensen, S. H. (2006). A Software-Defined GPS and Galileo Receiver: a Single-Frequency Approach, Birkhauser Boston.Google Scholar
Katcher, D. I., Sathaye, S. S. and Strosnider, J. K. (1995). Fixed Priority Scheduling with Limited Priority Levels, IEEE Transactions on Computers, 1140–1144.CrossRefGoogle Scholar
Jovancevic, A., Brown, A., Ganguly, S., Kirchner, M., Zigic, S., Scott, L. and Ward, P. (2001). Reconfigurable Dual Frequency Software GPS Receiver and Applications, Proceedings of the ION GPS 2001, 2888–2899.Google Scholar
Jovancevic, A., Brown, A., Ganguly, S., Goda, J., Kirchner, M. and Zigic, S. (2003). Real-Time Dual Frequency Software GPS Receiver, Proceedings of the ION GPS/GNSS 2003, 2572–2583.Google Scholar
SPIRIT Company (2008). GPS+GLONASS Baseband Software: DuoStar, from: www.spiritdsp.com/datasheets.Google Scholar
Tindell, K. W., Burns, A. and Wellings, A. (1994). An Extendible Approach for Analyzing Fixed Priority Hard Real-time Tasks, The Journal of Real-Time Systems, 6(2), 133–152.Google Scholar
Wu, W., Liu, X. H., Li, Z. R. and Wang, F. X. (2005). Implementation of Arc Tangent Function Using Assembly in Fixed-point DSP Based on Differential Evolution Algorithm, Systems Engineering and Electronics, 27(5), 926–928.Google Scholar
Wu, W., Ni, S. J. and Liu, X. H. (2009). Schedulability Analysis of Fixed Priority Systems with Limited Priority Levels, Computer Engineering and Applications, 45(5), 32–35.Google Scholar
Xing, J. X., Wang, Y. J., Liu, J. X., Zeng, H. T. and Nasro, M. A. (2007). A Static Priority Assignment Algorithm with the Least Number of Priority Levels, Journal of Software, 18(7), 1844–1854.CrossRefGoogle Scholar