Evolution analysis of a UAV real-time operating system from a network perspective
|
摘要
With the flourishing development of Unmanned Aerial Vehicles(UAVs), the mission tasks of UAVs have become more and more complex. Consequently, a Real-Time Operating System(RTOS) that provides operating environments for various mission services on these UAVs has become crucial, which leads to the necessity of having a deep understanding of an RTOS. In this paper, an empirical study is conducted on FreeRTOS, a commonly used RTOS for UAVs, from a complex network perspective. A total of 85 releases of FreeRTOS, from V2.4.2 to V10.0.0, are modeled as directed networks, in which the nodes represent functions and the edges denote function calls. It is found that the size of the FreeRTOS network has grown almost linearly with the evolution of the versions, while its main core has evolved steadily. In addition, a k-core analysis-based metric is proposed to identify major functionality changes of FreeRTOS during its evolution.The result shows that the identified versions are consistent with the version change logs. Finally,it is found that the clustering coefficient of the Linux OS scheduler is larger than that of the FreeRTOS scheduler. In conclusion, the empirical results provide useful guidance for developers and users of UAV RTOSs.
With the flourishing development of Unmanned Aerial Vehicles(UAVs), the mission tasks of UAVs have become more and more complex. Consequently, a Real-Time Operating System(RTOS) that provides operating environments for various mission services on these UAVs has become crucial, which leads to the necessity of having a deep understanding of an RTOS. In this paper, an empirical study is conducted on FreeRTOS, a commonly used RTOS for UAVs, from a complex network perspective. A total of 85 releases of FreeRTOS, from V2.4.2 to V10.0.0, are modeled as directed networks, in which the nodes represent functions and the edges denote function calls. It is found that the size of the FreeRTOS network has grown almost linearly with the evolution of the versions, while its main core has evolved steadily. In addition, a k-core analysis-based metric is proposed to identify major functionality changes of FreeRTOS during its evolution.The result shows that the identified versions are consistent with the version change logs. Finally,it is found that the clustering coefficient of the Linux OS scheduler is larger than that of the FreeRTOS scheduler. In conclusion, the empirical results provide useful guidance for developers and users of UAV RTOSs.
With the flourishing development of Unmanned Aerial Vehicles(UAVs), the mission tasks of UAVs have become more and more complex. Consequently, a Real-Time Operating System(RTOS) that provides operating environments for various mission services on these UAVs has become crucial, which leads to the necessity of having a deep understanding of an RTOS. In this paper, an empirical study is conducted on FreeRTOS, a commonly used RTOS for UAVs, from a complex network perspective. A total of 85 releases of FreeRTOS, from V2.4.2 to V10.0.0, are modeled as directed networks, in which the nodes represent functions and the edges denote function calls. It is found that the size of the FreeRTOS network has grown almost linearly with the evolution of the versions, while its main core has evolved steadily. In addition, a k-core analysis-based metric is proposed to identify major functionality changes of FreeRTOS during its evolution.The result shows that the identified versions are consistent with the version change logs. Finally,it is found that the clustering coefficient of the Linux OS scheduler is larger than that of the FreeRTOS scheduler. In conclusion, the empirical results provide useful guidance for developers and users of UAV RTOSs.
引文
1.Stankovic JA,Rajkumar R.Real-time operating systems.RealTime Syst 2004;28(2):237-53.
2.Costa LDF,Oliveira Jr ON,Travieso G,Rodrigues FA,Villas Boas PR,Antiqueira L,et al.Analyzing and modeling real-world phenomena with complex networks:A survey of applications.Adv Phys 2011;60(3):329-412.
3.Erdos P,Re′nyi A.On random graphs I.Publ Math Debrecen1959;6:290-7.
4.Merton RK.The Matthew effect in science.Science 1968;159(3810):56-63.
5.Watts DJ,Strogatz SH.Collective dynamics of’small-world’networks.Nature 1998;393(6684):440-2.
6.Baraba′si AL,Albert R.Emergence of scaling in random networks.Science 1999;286(5439):509-12.
7.Giot L,Bader JS,Brouwer C,Chaudhuri A,Kuang B,Li Y,et al.A protein interaction map of Drosophila melanogaster.Science2003;302(5651):1727-36.
8.Cohen R,Erez K,Ben-Avraham D,Havlin S.Breakdown of the Internet under intentional attack.Phys Rev Lett 2001;86(16):3682.
9.Du WB,Liang BY,Yan G,Lordan O,Cao XB.Identifying vital edges in Chinese air route network via memetic algorithm.Chinese J Aeronaut 2017;30(1):330-6.
10.Saberi M,Mahmassani HS,Brockmann D,Hosseini A.Acomplex network perspective for characterizing urban travel demand patterns:Graph theoretical analysis of large-scale origin-destination demand networks.Transportation 2017;44(6):1383-402.
11.Wang WX,Wang BH,Yin CY,Xie YB,Zhou T.Traffic dynamics based on local routing protocol on a scale-free network.Phys Rev E 2006;73(2):026111.
12.Du WB,Zhou XL,Lordan O,Wang Z,Zhao C,Zhu YB.Analysis of the Chinese Airline Network as multi-layer networks.Transport Res E-Log 2016;89:108-16.
13.Lordan O,Sallan JM.Analyzing the multilevel structure of the European airport network.Chinese J Aeronaut 2017;30(2):554-60.
14.Du WB,Ying W,Yan G,Zhu YB,Cao XB.Heterogeneous strategy particle swarm optimization.IEEE Trans Circuits-II2017;64(4):467-71.
15.Yan G,Ve′rtes PE,Towlson EK,Chew YL,Walker DS,Schafer WR,et al.Network control principles predict neuron function in the Caenorhabditis elegans connectome.Nature 2017;550(7677):519.
16.Wang L,Fu YB,Chen MZ,Yang XH.Controllability robustness for scale-free networks based on nonlinear load-capacity.Neurocomputing 2017;251:99-105.
17.Louridas P,Spinellis D,Vlachos V.Power laws in software.ACMTrans Softw Eng Meth 2008;18(1):2.
18.Valverde S,Cancho RF,Sole RV.Scale-free networks from optimal design.Europhys Lett 2002;60(4):512.
19.Myers CR.Software systems as complex networks:Structure,function,and evolvability of software collaboration graphs.Phys Rev E 2003;68(4):046116.
20.Sui YL,Xue JL.SVF:interprocedural static value-flow analysis in LLVM.Proceedings of the 25th international conference on compiler construction;2016 Mar 17-18;Barcelona.New York:ACM;2016.p.265-6.
21.Sui YL,Xue JL.On-demand strong update analysis via value-flow refinement.Proceedings of the 2016 24th ACM SIGSOFT international symposium on foundations of software engineering;2016 Nov13-18;Seattle.New York:ACM;2016.p.460-73.
22.Zheng XL,Zeng D,Li HQ,Wang FY.Analyzing open-source software systems as complex networks.Physica A 2008;387(24):6190-200.
23.Gao YC,Zheng Z,Qin FY.Analysis of Linux kernel as a complex network.Chaos Soliton Fract 2014;69:246-52.
24.Wang HQ,Chen Z,Xiao GP,Zheng Z.Network of networks in Linux operating system.Physica A 2016;447:520-6.
25.Xiao GP,Zheng Z,Wang HQ.Evolution of Linux operating system network.Physica A 2017;466:249-58.
26.Freertos.org[Internet].London:Real Time Engineers Ltd.[updated 2017 Nov 23;cited 2017 Nov 23].Available from https://www.freertos.org.
27.Stingu E,Lewis FL.A hardware platform for research in helicopter UAV control.In:Kimon PV,Paul O,Les AP,editors.Unmanned aircraft systems.Netherlands:Springer;2008.p.387-406.
28.Furci M,Casadei G,Naldi R,Sanfelice RG,Marconi L.An opensource architecture for control and coordination of a swarm of micro-quadrotors.2015 international conference on uAircraft systems;2015 Jun 9-12;Denver.Piscataway:IEEE Press;2015p.139-46.
29.Mistry J,Naylor M,Woodcock J.Adapting FreeRTOS for multicores:An experience report.Software Pract Exper 2014;44(9):1129-54.
30.Andrade WL,Machado PD,Alves EL,Almeida DR.Test case generation of embedded real-time systems with interruptions for FreeRTOS.2009 12th brazilian symposium on formal methods2009 Aug 19-21;Gramado.Berlin:Springer;2009.p.54-69.
31.Ferreira JF,Gherghina C,He GH,Qin SC,Chin WN.Automated verification of the FreeRTOS scheduler in Hip/Sleek.Int J Softw Tools Technol 2014;16(4):381-97.
32.Guan F,Peng L,Perneel L,Timmerman M.Open source FreeRTOS as a case study in real-time operating system evolution J Syst Software 2016;118:19-35.
33.Lehman MM.Laws of software evolution revisited.1996 5th European workshop on software process technology;1996 Oct 9-11Nancy.Berlin:Springer;1996.p.108-24.
34.Seidman SB.Network structure and minimum degree.Soc Networks 1983;5(3):269-87.
35.Montresor A,De Pellegrini F,Miorandi D.Distributed k-core decomposition.IEEE Trans Parall Distr 2013;24(2):288-300.
36.Barry R.Mastering the FreeRTOS real time kernel-a hands on tutorial guide[Internet].London:Real Time Engineers Ltd.;2016[cited 2017 Nov 23].Available from:https://www.freertos.org/Documentation/161204_Mastering_the_FreeRTOS_Real_Time_Kernel-A_Hands-On_Tutorial_Guide.pdf.
37.Fagiolo G.Clustering in complex directed networks.Phys Rev E2007;76(2):026107.
38.Batagelj V,Zaversnik M.An O(m)algorithm for cores decomposition of networks.Comput Sci 2003;1(6):34-7.
39.Zhang HH,Zhao H,Cai W,Liu J,Zhou WL.Using the k-core decomposition to analyze the static structure of large-scale software systems.J Supercomput 2010;53(2):352-69.
40.Zhang GQ,Zhang GQ,Yang QF,Cheng SQ,Zhou T.Evolution of the Internet and its cores.New J Phys 2008;10(12):123027.
41.Pan WF,Li B,Liu J,Ma YT,Hu B.Analyzing the structure of Java software systems by weighted K-core decomposition.Futur Gener Comp Syst 2018;83:431-44.
42.Sheskin DJ.Handbook of parametric and nonparametric statistical procedures.Boca Raton(FL):CRC Press;2003.
43.Bovet DP,Cesati M.Understanding the Linux Kernel:from I/Oports to process management.Sebastopol(CA):O’Reilly Media;2005.
44.Pabla CS.Completely fair scheduler.Linux J 2009;2009(184):4.
2.Costa LDF,Oliveira Jr ON,Travieso G,Rodrigues FA,Villas Boas PR,Antiqueira L,et al.Analyzing and modeling real-world phenomena with complex networks:A survey of applications.Adv Phys 2011;60(3):329-412.
3.Erdos P,Re′nyi A.On random graphs I.Publ Math Debrecen1959;6:290-7.
4.Merton RK.The Matthew effect in science.Science 1968;159(3810):56-63.
5.Watts DJ,Strogatz SH.Collective dynamics of’small-world’networks.Nature 1998;393(6684):440-2.
6.Baraba′si AL,Albert R.Emergence of scaling in random networks.Science 1999;286(5439):509-12.
7.Giot L,Bader JS,Brouwer C,Chaudhuri A,Kuang B,Li Y,et al.A protein interaction map of Drosophila melanogaster.Science2003;302(5651):1727-36.
8.Cohen R,Erez K,Ben-Avraham D,Havlin S.Breakdown of the Internet under intentional attack.Phys Rev Lett 2001;86(16):3682.
9.Du WB,Liang BY,Yan G,Lordan O,Cao XB.Identifying vital edges in Chinese air route network via memetic algorithm.Chinese J Aeronaut 2017;30(1):330-6.
10.Saberi M,Mahmassani HS,Brockmann D,Hosseini A.Acomplex network perspective for characterizing urban travel demand patterns:Graph theoretical analysis of large-scale origin-destination demand networks.Transportation 2017;44(6):1383-402.
11.Wang WX,Wang BH,Yin CY,Xie YB,Zhou T.Traffic dynamics based on local routing protocol on a scale-free network.Phys Rev E 2006;73(2):026111.
12.Du WB,Zhou XL,Lordan O,Wang Z,Zhao C,Zhu YB.Analysis of the Chinese Airline Network as multi-layer networks.Transport Res E-Log 2016;89:108-16.
13.Lordan O,Sallan JM.Analyzing the multilevel structure of the European airport network.Chinese J Aeronaut 2017;30(2):554-60.
14.Du WB,Ying W,Yan G,Zhu YB,Cao XB.Heterogeneous strategy particle swarm optimization.IEEE Trans Circuits-II2017;64(4):467-71.
15.Yan G,Ve′rtes PE,Towlson EK,Chew YL,Walker DS,Schafer WR,et al.Network control principles predict neuron function in the Caenorhabditis elegans connectome.Nature 2017;550(7677):519.
16.Wang L,Fu YB,Chen MZ,Yang XH.Controllability robustness for scale-free networks based on nonlinear load-capacity.Neurocomputing 2017;251:99-105.
17.Louridas P,Spinellis D,Vlachos V.Power laws in software.ACMTrans Softw Eng Meth 2008;18(1):2.
18.Valverde S,Cancho RF,Sole RV.Scale-free networks from optimal design.Europhys Lett 2002;60(4):512.
19.Myers CR.Software systems as complex networks:Structure,function,and evolvability of software collaboration graphs.Phys Rev E 2003;68(4):046116.
20.Sui YL,Xue JL.SVF:interprocedural static value-flow analysis in LLVM.Proceedings of the 25th international conference on compiler construction;2016 Mar 17-18;Barcelona.New York:ACM;2016.p.265-6.
21.Sui YL,Xue JL.On-demand strong update analysis via value-flow refinement.Proceedings of the 2016 24th ACM SIGSOFT international symposium on foundations of software engineering;2016 Nov13-18;Seattle.New York:ACM;2016.p.460-73.
22.Zheng XL,Zeng D,Li HQ,Wang FY.Analyzing open-source software systems as complex networks.Physica A 2008;387(24):6190-200.
23.Gao YC,Zheng Z,Qin FY.Analysis of Linux kernel as a complex network.Chaos Soliton Fract 2014;69:246-52.
24.Wang HQ,Chen Z,Xiao GP,Zheng Z.Network of networks in Linux operating system.Physica A 2016;447:520-6.
25.Xiao GP,Zheng Z,Wang HQ.Evolution of Linux operating system network.Physica A 2017;466:249-58.
26.Freertos.org[Internet].London:Real Time Engineers Ltd.[updated 2017 Nov 23;cited 2017 Nov 23].Available from https://www.freertos.org.
27.Stingu E,Lewis FL.A hardware platform for research in helicopter UAV control.In:Kimon PV,Paul O,Les AP,editors.Unmanned aircraft systems.Netherlands:Springer;2008.p.387-406.
28.Furci M,Casadei G,Naldi R,Sanfelice RG,Marconi L.An opensource architecture for control and coordination of a swarm of micro-quadrotors.2015 international conference on uAircraft systems;2015 Jun 9-12;Denver.Piscataway:IEEE Press;2015p.139-46.
29.Mistry J,Naylor M,Woodcock J.Adapting FreeRTOS for multicores:An experience report.Software Pract Exper 2014;44(9):1129-54.
30.Andrade WL,Machado PD,Alves EL,Almeida DR.Test case generation of embedded real-time systems with interruptions for FreeRTOS.2009 12th brazilian symposium on formal methods2009 Aug 19-21;Gramado.Berlin:Springer;2009.p.54-69.
31.Ferreira JF,Gherghina C,He GH,Qin SC,Chin WN.Automated verification of the FreeRTOS scheduler in Hip/Sleek.Int J Softw Tools Technol 2014;16(4):381-97.
32.Guan F,Peng L,Perneel L,Timmerman M.Open source FreeRTOS as a case study in real-time operating system evolution J Syst Software 2016;118:19-35.
33.Lehman MM.Laws of software evolution revisited.1996 5th European workshop on software process technology;1996 Oct 9-11Nancy.Berlin:Springer;1996.p.108-24.
34.Seidman SB.Network structure and minimum degree.Soc Networks 1983;5(3):269-87.
35.Montresor A,De Pellegrini F,Miorandi D.Distributed k-core decomposition.IEEE Trans Parall Distr 2013;24(2):288-300.
36.Barry R.Mastering the FreeRTOS real time kernel-a hands on tutorial guide[Internet].London:Real Time Engineers Ltd.;2016[cited 2017 Nov 23].Available from:https://www.freertos.org/Documentation/161204_Mastering_the_FreeRTOS_Real_Time_Kernel-A_Hands-On_Tutorial_Guide.pdf.
37.Fagiolo G.Clustering in complex directed networks.Phys Rev E2007;76(2):026107.
38.Batagelj V,Zaversnik M.An O(m)algorithm for cores decomposition of networks.Comput Sci 2003;1(6):34-7.
39.Zhang HH,Zhao H,Cai W,Liu J,Zhou WL.Using the k-core decomposition to analyze the static structure of large-scale software systems.J Supercomput 2010;53(2):352-69.
40.Zhang GQ,Zhang GQ,Yang QF,Cheng SQ,Zhou T.Evolution of the Internet and its cores.New J Phys 2008;10(12):123027.
41.Pan WF,Li B,Liu J,Ma YT,Hu B.Analyzing the structure of Java software systems by weighted K-core decomposition.Futur Gener Comp Syst 2018;83:431-44.
42.Sheskin DJ.Handbook of parametric and nonparametric statistical procedures.Boca Raton(FL):CRC Press;2003.
43.Bovet DP,Cesati M.Understanding the Linux Kernel:from I/Oports to process management.Sebastopol(CA):O’Reilly Media;2005.
44.Pabla CS.Completely fair scheduler.Linux J 2009;2009(184):4.