Archives

  • 2018-07
  • 2018-10
  • 2018-11
  • 2019-04
  • 2019-05
  • 2019-06
  • 2019-07
  • 2019-08
  • 2019-09
  • 2019-10
  • 2019-11
  • 2019-12
  • 2020-01
  • 2020-02
  • Nevertheless two problems exist in BGCFC in practice The fir

    2019-09-11

    Nevertheless, two problems exist in BGCFC in practice. The first one is that time complexity of the ID assignment algorithm presented in Section 3.1 is O(N!), which means a factorial time complexity. Because it obtains the consecutive IDs by enumerating all permutations of ID to N−1, the total number of all permutation is N’s factorial. In practice, N is large (usually >300) so it is very time-consuming. Fortunately, this algorithm runs on the personal computer (PC) on ground instead of the OBC of the small satellite. Thanks to the high performance of current PCs, we can wait for several hours to obtain the consecutive IDs without affecting the effectiveness of BGCFC. However, it is still inconvenient and inflexible for this algorithm. Suppose if we run the algorithm on a large program with thousands of basic blocks, then probably it will take us several days to obtain the result. Therefore the main task of future work is to decrease the time complexity of the ID assignment algorithm to quadratic O(N2) or linear O(N). The second problem is potential. In case that there exists a target program whose control flow graph is so special that IDs are not consecutive enough, the storage density of the bitmap will be quite low and the bitmap length may exceed the word length, then the performance of BGCFC may decay to the level of SCFC and RSCFC. Currently, we have no way to prove which patterns of control flow graphs may result in the worst case of the consecutive IDs theoretically, so it is potential. Fortunately, by far we have not suffered this problem while performing BGCFC to various real programs of satellites. Both of the problems are related to graph WM-1119 and we will attempt to resolve them referring to this theory in future work.
    Conclusions
    Acknowledgment The authors would like to give their acknowledgement to the support from the National Natural Science Foundation of China and the Fundamental Research Funds for the Central Universities of China.
    Introduction In recent years a new trend has emerged in the design and verification of spacecraft. Rapid advances within the field of integrated electronics have enabled the use of inexpensive and highly performant electronic components, which have also found their way into the space industry. These so-called Commercial off-the-Shelf (COTS) components allow the constructions of spacecraft, specifically satellites, at significantly lower costs and development times. This has allowed small, interwoven teams (as typically found within university environments) to design nanosatellites from the initial concept stages to the final stages within drastically reduced time frames. These nanosatellites typically have a WM-1119 mass of less than 10kg and occupy a volume of less than 8.4dm3. Indeed, the popularity of this approach cannot be denied, with more than 90 different nanosatellites being launched in 2013 alone, with the number expected to increase even further in the following years [1]. Though their roots lie in university-based education and technology demonstration missions, their usages since their inceptions have evolved into including science, remote sensing, telecommunication, and even commercial interests [2]. Indeed, perhaps the most important aspect of the nanosatellite approach is the possibility of launching a multitude of nanosatellites as a single satellite constellation, whereby these tasks previously thought of as too expensive could be accomplished (e.g. on-demand remote sensing, global monitoring, other real-time satellite applications). Though these limitations have already resulted in the failure of a couple of nanosatellite missions [3], their use in primarily Low Earth Orbit (LEO) meant that most missions proceeded without major problems even with the potential lack in reliability. However, talks are already underway to bring the nanosatellite platforms along even further by using them for interplanetary missions. In order for nanosatellites to still be practical beyond LEO, where the radiation environment and operational constraints are much harsher, one method would be to modify their designs to be more in line with how larger satellites are designed and built [4].