A Time-Evolving Connected Dominating Set Based Routing Algorithm In Multi-Layered Satellite Networks

Since the 21^stcentury,the high dynamic satellite network that can interconnect,obtain and handle all kinds of information has been more and more widely used in the field of politics,military affairs,culture.And satellite network are distinguished by several characteristics that different from other networks such as wide-area continuous communication,global coverage,cost-effective broadcast/multipoint capabilities,flexible network configuration/capacity allocation and so on.But,in satellte network,the lack of continuous connectivity,network partition,the lack of end-to-end links,and dynamic topology caused by high dynamic of satellite nodes pose new challenges in the design of satellite routing.So how to maintain the connectivity of network topology efficientiy and dynamicly become crucial.As we know,establishing a backbone network is an important way to maintain network topology connectivity in current wireless terrestrial networks（such as sensor networks and Ad Hoc networks）.However,unlike wireless terrestrial networks,the time-varying nature of satellite networks makes establishing an effective backbone network to deliver data become an challenge.Clustering is often used in the existing satellite networks to construct the backbone network,which selects the cluster headers as the backbone nodes to maintain the network connectivity,and non-cluster nodes are interconnected by the cluster headers.However,this method ignores the connectivity,and lead the instability of network.On the other hand,clustering leads to artificial network delamination and the increase of the backbone network,which is not conducive to the management of topology connectivity.In this paper,in view of the above problem,we proposed a time-evolving connected dominating set（TCDS）incorporated GEO/MEO/LEO routing strategy.We usually use topology control strategy to shield the dynamic of satellite network in the design of routing algorithm.In this paper,a series of snapshots are used to discretize the dynamic topology of the satellite network,and the analysis framework based on time-evolving graph is adopted.Then on the above basis,the routing algorithm based on the classical connected dominating set（CDS）and the time-varying connected dominating set is constructed respectively,the aim of CDS based algorithm is to build a sparse backbone network such that the network is still connected over time and space.The algorithm of CDS in single snapshot is formed after analyzing the existing classical CDS algorithms,which also proved the applicability of the connected dominating thought on the satellite network at the same time.After then,The description of backbone network based on time-varying connectivity is given by considering the temporal characteristics.And we also proved that the proposed dynamic connected dominating set is a NP-hard problem.Then combined with the related definitions of static connected dominating sets and the time-varying characteristics of satellite networks,the related definitions of time-varying connected dominating sets are given.the proposed algorithm can exactly capture the dynamic property of a multi-layer satellite network in two space and temporal dimensions.In this paper,we proposed a group of construction algorithms for building a time-evolving CDS based backbone network,which could significantly reduce the time length of operation and total number of edges required for maintaining the connectivity.In particular,the proposed algorithms will repeatedly add a set of edges in the space-time graph in order to connect other nodes by backbone nodes,until all nodes in the network are connected within a period of time.Then we use total edges of backbone network,maximum snapshot of proposed routing and maximum delivery delay as performance metrics and establish the corresponding mathematical models.the simulations verified the proposed algorithms.Moreover the convergence time and maximum transmission delay of time-varying CDS routing strategy is relatively superior to the traditional routing policy.