Clustering Algorithm for CubeSat Constellations

In recent years, constellations of CubeSat are redefining the concept of space missions. Complex missions that in the past could only be accomplished using large and expensive satellites can now be performed by CubeSat constellations that, thanks to their coordinated action, can guarantee a certain efficiency level and fulfil the same required goals, reducing costs, system singularities and risk of catastrophic disasters. However, a CubeSat constellation system presents critical organizational issues in terms of creation and managing of network structures and interaction between elements. Orbital characteristics of CubeSats, mutual mobility, low-level features and obviously the final goal of the constellation are some of the critical factors that affect the efficiency of the system. In our paper, we present a novel algorithm able to consider the specific characteristics and the mobility behaviours of every CubeSats to autonomously create and optimize a network structure for the constellation. This network structure will be exploited to facilitate the data flow inside and outside the constellation and to facilitate the management of the CubeSat constellation. The basic idea is to consider the CubeSat constellation as a Mobile ad-hoc network (MANET): MANETs are systems of autonomous mobile nodes connected between them to form a graph by a wireless ad-hoc network. The formation and management of MANETs is mostly related to the physical structure and mobility behaviour of nodes composing the network; clustering algorithms aim to face several problems related to the network formation and maintenance of the MANETs structure. The main goal of the clustering algorithms is to group nodes in virtual sub-groups based on specific grouping parameters which differ depending on the used algorithm. To develop our algorithm, we selected some concepts and specific features from other clustering algorithms to fit the CubeSat constellations scenario requirements. A complete survey of the main clustering algorithms can be found in [1]. By applying some modifications, we unified the strengths and we introduced new concepts during the design process to minimize the weakness points and to be coherent with our concepts of simplicity, flexibility and energy saving. The key factors identified to form the sub-networks (clusters) inside the CubeSat constellation are: mutual relative speed, relative distances, CubeSat ID and cluster-head serving time. These factors are combined to elect the best local managers of a neighbourhood inside the CubeSat constellation: The Cluster-Heads. During the clusters formation process CubeSats can assume different states: Initial, Cluster-Head, Cluster-Member, Cluster-Member-Gateway, Cluster-Guest, Cluster-Guest-Gateway. The Cluster-Head is responsible for its cluster management, it administrates the communication in input and output to/from its cluster and organizes the data flow and the behaviour of the Cluster-Members. The Cluster-Guests are exploited to make the algorithm more flexible in case of undefined or difficulties in the communication link establishment, moreover they are exploited to reduce undesirable effect such as the ripple effect of the re-clustering [1]. The Gateway capability is the ability of a node to create a direct link with other elements of external clusters, it represents the key factor to unify the constellation and create a stable backbone for the data flow over the whole network. Figure 1 shows an example of CubeSat constellation network after the cluster formation process; every node has assumed one of the state described before. A typical cluster trend is shown in figure 2: role that each satellite assume depends on the communication features and the mobility behaviour of each node. Most of the analysed algorithms require an initial frozen period of motion to establish the roles of node. By introducing the dynamic analysis of the mutual velocity and distance, our algorithm does not need this stationary assumption. This characteristic results fundamental in a CubeSat constellation scenario, where the release in orbit makes impossible to obtain a period where satellites remain stationary. The clusters formation results stable and durable in time because an estimation of the motion evolution is considered when mutual motion parameters are exchanged, clusters dynamically adapt and stay stable also in situation where satellites have high mobility behaviour. Thanks to the combination of the selected parameters our algorithm guarantees very high flexibility and results to be efficient over a wide range of mobility behaviour combinations of nodes. During the cluster maintenance phase, the motion behaviour of satellites can affect the entire cluster structures. The ripple effect of the re-clustering is kept under control and the flooding effect is avoided thanks to the ability of the algorithm to limit the re-election process only to the interested satellites. Moreover, the cluster-guest nodes provide additional help in case of high mobility or significant differences in mobility characteristics of node. These factors help to keep the cluster stable in case of dynamic changes or brief meeting period between clusters, thus implying that the whole clusters network is scalable and expandable and the algorithms makes clusters robust enough to deal with radical network structure changes