Advanced
A Hierarchical Autonomous System Based Topology Control Algorithm in Space Information Network
A Hierarchical Autonomous System Based Topology Control Algorithm in Space Information Network
KSII Transactions on Internet and Information Systems (TIIS). 2015. Sep, 9(9): 3572-3593
Copyright © 2015, Korean Society For Internet Information
  • Received : April 23, 2015
  • Accepted : July 18, 2015
  • Published : September 30, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Wei Zhang
College of Communication Engineering, PLA University of Science and Technology Nanjing, China
Gengxin Zhang
College of Communication Engineering, PLA University of Science and Technology Nanjing, China
Liang Gou
College of Communication Engineering, PLA University of Science and Technology Nanjing, China
Bo Kong
College of Communication Engineering, PLA University of Science and Technology Nanjing, China
Dongming Bian
College of Communication Engineering, PLA University of Science and Technology Nanjing, China

Abstract
This article investigates the topology control problem in the space information network (SIN) using a hierarchical autonomous system (AS) approach. We propose an AS network topology control (AS-TC) algorithm to minimize the time delay in the SIN. Compared with most existing approaches for SIN where either the purely centralized or the purely distributed control method is adopted, the proposed algorithm is a hybrid control method. In order to reduce the cost of control, the control message exchange is constrained among neighboring sub-AS networks. We prove that the proposed algorithm achieve logical k -connectivity on the condition that the original physical topology is k -connectivity. Simulation results validate the theoretic analysis and effectiveness of the AS-TC algorithm.
Keywords
1. Introduction
T he space information network (SIN) is a new type of self-organizing system constituted by information systems of space, air, land and sea [1 - 4] . It is proposed to solve the problems that current space systems’ lacking of universality and the inconvenience in cooperation between different missions. SIN accepts various kinds of platforms as network nodes, such as satellites, high altitude platforms (HAPs), aerial vehicles and terrestrial sensors [5] . Due to the distinguishing characteristics of SIN such as large scale, high component complexity and dynamic, how to make an efficient and reliable topology control of SIN is challenging.
Existing works about network topology control mainly focus on maintaining a specified topology to achieve a set of network-wide objectives such as reducing energy consumption, guaranteeing the robustness, increasing the network capacity and reducing end-to-end delay, e.g., [6 - 14] . But in most studies, either the purely centralized or the purely distributed control method is adopted. Centralized algorithms rely on a central entity which knows the conditions of all the nodes in order to calculate the optimal topology [15 - 17] . However, these algorithms are not suitable for large scale networks such as SIN where excessive amount of control messages need to be collected by the central entity. On the other hand, in distributed algorithms, each node collects the information from its neighboring nodes and autonomously decides which link should be preserved [17 - 19] . Considering that the information each node obtains is limited, the final topology usually cannot achieve global optimization for large scale networks. Thus, it is important to develop a special topology control algorithm for the large scale SIN.
Considering the scale of SIN, a substantial proportion of the links are extremely long. Excessive use of these long-distance links data not only brings additional delay but also reduces the system efficiency [20 , 21] . Thus in the SIN topology control, end-to-end delay should be considered more. Instead of using long links, nodes in SIN collaboratively determine which links should be used and define the network topology through forming proper neighbor relations. That is, topology control algorithms actually remove unnecessary links. As a result, the network topology is susceptible to unpredictable events such as hardware failures. Therefore, to design robust topology control algorithm, k -connectivity of the network is considered, where a k -connected network is k -1 fault-tolerant, i.e., the failure of less than k -1 nodes will not disconnect the whole network.
In this article, we study the topology control problem in SIN using a hierarchical autonomous system (AS) approach. An AS network is a collection of nodes have similar properties. The reasons for using hierarchical AS approach are twofold. Firstly, the complex SIN is decoupled into a series of AS networks, and each AS network could have different topology control strategy. Secondly, AS network is divided into small sub-AS networks to ensure strong connectivity after topology control. We propose an AS network topology control (AS-TC) algorithm using a hybrid approach. AS-TC preserves k -connectivity and is min-max delay optimal. A min-max algorithm tries to minimize the maximum end-to-end delay between any pair of nodes in the network. Briefly, the AS-TC algorithm consists of three phases: (i) Nodes in AS network of SIN autonomously form sub-AS networks and elect sub-AS cores. (ii) With the topology information gathered from the members of its sub-AS network, each sub-AS core minimize the maximum delay between any pair of nodes in the sub-AS network and guarantee strong connectivity using centralized method. (iii) Each sub-AS core selects a set of border nodes, shares topology information with neighboring sub-AS cores, and computes min-max delay links between neighboring sub-AS networks using distributed method. The main contributions of this article are summarized as follows:
1) An AS network model of SIN is proposed. The large scale, complex and dynamic SIN is decoupled into AS networks with similar nodes, which makes the control of the SIN easier.
2) An AS network topology control (AS-TC) algorithm is proposed to achieve low time delay and strong connectivity. It is a hybrid algorithm within a sub-AS network and among neighboring sub-AS networks.
3) The strong connectivity of AS-TC algorithm is proved that the algorithm could achieve logical k -connectivity on the condition that the original physical topology is k -connectivity.
The rest of this article is organized as follows. In Section 2, we define the network model and provide some definitions. In Section 3, we propose a hierarchical AS based algorithm AS-TC to achieve low time delay and strong connectivity. Then, the validity of AS-TC is proved in Section 4, and the message complexity of our algorithm is analyzed in Section 5. In Section 6, simulation results and discussion are presented. Finally, we make conclusion in Section 7.
2. Network Model
In this section, the network model of AS network is defined. As presented above, SIN is a new type of self-organizing system constituted by various kinds of nodes. As demonstrated in Fig. 1 , the nodes distribute at different altitude, and work in different environment with either mobile (e.g., in HAPs networks) or static (e.g., in terrestrial wireless sensor networks) statuses. If we apply a unified strategy to manage the whole SIN, it will induce low efficiency, and even cannot maintain the normal operation of the network with too much control information. So, as shown in Fig. 2 , we divide the SIN into a series of AS networks according to the property of the nodes. Each AS network can adopt an independent topology control strategy. In this way, the complex SIN is decoupled into sub-networks constituted by similar nodes, and the control of them is easier to carry out. AS-1 contains all the satellites of SIN and the topology of it is usually high dynamic but predictable. Topology control of AS-1 is usually based on satellites constellations design. We will not discuss the topology control of AS-1 in this paper. AS-2 contains the HAPs, AS-3 contains the airplanes and AS-4 contains the ground nodes. Properties of AS-2/3/4 are similar: nodes in them move slowly, and they connect to each other autonomously. In this article, we mainly focus on the topology control problem in AS-2/3/4.
PPT Slide
Lager Image
The architecture of SIN.
PPT Slide
Lager Image
The whole SIN is divided into a series of AS networks according to the property of the nodes.
Considering that the properties of nodes in an AS network are similar, we assume that nodes in the same AS network are homogeneous. They have the same maximal transmission range R max . Let an AS network topology be represented by an undirected simple graph G =( V , E ), where V ={ u 1 , u 2 ,⋯, un ) is the set of nodes (or equivalently, vertices) and E ={( ui , uj )|( ui , uj V )∧( r ( ui , uj )≤ R max )} is the set of links (edges). r ( ui , uj ) is the distance between nodes ui and uj . Each node is assigned a unique identifier (ID) according to its property, such as MAC address.
We assume that G is a general graph, that is, if ( u , v )∈ E , u and v can exchange information with each other. We also assume that the link is symmetric and obstacle-free, and each node is able to obtain its location information by some means (e.g., GPS). We then define several graphs related terms in the following, which will be used both in algorithms and proofs. For all definitions, we refer to graph G =( V , E ) and sub-graphs Gi =( Vi , Ei ) and Gj =( Vj , Ej ) .
Definition 1: Weight Function . For an edge e =( u , v ), the weight function is w ( u , v )=( d ( u , v ), min( ID ( u ), ID ( v )),max( ID ( u ), ID ( v ))), where d ( u , v ) is the time delay between u and v when exchanging information, and ID (·) denotes the unique identifier of a node. Node’s ID is included in the weight calculation to break ties. Given ( u 1 , v 1 ),( u 2 , v 2 )∈ E , the relationship between w ( u 1 , v 1 ) and w ( u 2 , v 2 ) is given as
PPT Slide
Lager Image
It is obvious that edges with the same vertices have equivalent weights. However, edges with different end-vertices have different weights.
Definition 2: k-connected . In graph (topology) G , node u is said to be connected to node v , if there exists a path
PPT Slide
Lager Image
, where xi V and ( u , x 1 ), ( xi , xj ),( xm , v )∈ E . And for any u , v V , if there exists at least k disjoint paths between them. Graph G is k -connected, and denoted by CON ( G , k ). If G is k -connected, it follows that, there does not exist a set of k -1 vertices, whose removal will partition G into two or more connected components.
Definition 3: Neighboring k-connected sub-graphs . For two disjoint sub-graphs Gi and Gj of G , if ∃ u Vi , v Vj and ∃( u , v )∈ E , Gi and Gj are are neighboring sub-graphs, denoted by NBRG ( Gi , Gj ). If CON ( Gi , k )∧ CON ( Gj , k ), and ∃( u 1 , v 1 ),⋯, ( uk , uk )∈ E , where u 1 ,⋯, uk Vi and v 1 ,⋯, vk Vj , Gi and Gj are neighboring k -connected sub-graphs, denoted by NBRG ( Gi , Gj , k ).
Definition 4: Multihop k-connected sub-graphs . G 1 , G 2 ,⋯, Gn be a partitioning of G . If ∃ Gi subject to NBRG ( Gi , Gj , k )∧ NBRG ( Gl , Gj , k ), Gi and Gj are multihop k -connected sub-graphs, denoted by MCONG ( Gi , Gj , k )
3. Algorithms for Topology Control
Recall from the introduction, the design aims of the AS-TC algorithm in each AS are twofold: 1) to provide min-max delay optimal through a hierarchical AS approach, and 2) to achieve strong connectivity in the resulting network. The AS-TC algorithm does not require the global topology of the AS network to be known by any entity. On the contrary, AS-TC relies on sub-AS network where nodes autonomously form groups in AS, and select a core for each sub-AS network. It is a hybrid of centralized algorithm and distributed algorithm. A centralized topology control algorithm is applied to each sub-AS network to achieve the desired connectivity within the sub-AS, while the desired connectivity between adjacent sub-AS networks is achieved via localized information sharing between adjacent sub-AS cores. The following subsections detail the three phases of the AS-TC algorithm.
- 3.1 Phase 1: Sub-AS network Formation
The main function of Phase 1 is to select a minimal number of nodes as cores that dominate the sub-AS networks by using only 1-hop transmission. And these cores will take the main responsibility for the subsequent two phases.
Step 1: Broadcasting hello messages . When starting up, each node broadcasts hello messages periodically in order to let them discover each other in the surrounding area. A hello message is of the form ( NdeID , Location , CoreID , Degree , Delay ). The explanation of each field is as follows. 1) NdeID : the unique ID of each node. 2) Location : the location of each node. 3) CoreID : the ID of the core with which the sending node is currently associated. If the sending node does not associate to any core, it is zero. Note that a core node uses its own ID for this field. 4) Degree : the degree of connectivity (the number of neighbors). 5) Delay : time delay to each neighbor when exchange information. It may contain processing, transmission and propagation delay in practice. In order to facilitate the analysis, we only consider propagation delay in this paper.
Step 2: Core selection process . The core selection process of each node begins after it has broadcasted hello messages for a certain waiting time. The waiting time should be long enough to allow this node receive at least one hello message from every immediate neighbor. In this process, every node will decide whether it is suitable as a core of a sub-AS, or become a member of a sub-AS by checking for its local optimality. Each node computes its own height from its current states. The height metric should be chosen to suit the design goals of the AS topology control algorithm. Recall that the design goals of the AS-TC algorithm in each AS are twofold: 1) to provide min-max delay optimal through a hierarchical AS approach, and 2) to achieve strong connectivity in the resulting network. To achieve the first part of this goal, it is appropriate to choose the node with lower delay to each neighbor. On the other hand, to achieve the second part of the goal and to select a minimal number of nodes as cores, the nodes which have a higher degree should be considered. Therefore, we define the height metric as ( Delay , Degree , NodeID ). NodeID is included in the metric calculation to break ties. The height function is height ( u )=( h ( u ), ID ( u )). In order to balance the factor of Delay and Degree , we formulate h ( u ) as
PPT Slide
Lager Image
In (2), f (·) denotes the balance function, vi are the neighboring nodes of node u , i =1,⋯, Degree ( u ) and α denotes the balance factor. There can be many methods to formulate f (·), here we provide one of these methods for instance as
PPT Slide
Lager Image
In (3),
PPT Slide
Lager Image
is the average of reciprocal delay with every neighboring node. We use reciprocal delay
PPT Slide
Lager Image
here to guarantee that when the delay is lower and the degree is higher, we will obtain the higher h ( u ). The value of α is choosed with the consideration of the following two aspects: 1) to determine which is more important between delay optimization and number of cores in the network, and 2) to make Degree ( u ) and
PPT Slide
Lager Image
be of the same order of magnitude. The relationship between hight ( u ) and hight ( v ) is given by
PPT Slide
Lager Image
Then, if a node has the highest height among its neighbors, it is considered as a local optimal node and should serve as a core. After this process, the first batch of cores is selected, and all consequent hello messages will be changed accordingly. Note that, nodes will continue broadcasting hello messages at other steps to maintain the algorithm. The frequency of the hello messages can be divided into two types. Firstly, at each step, the hello message is broadcast with a fixed period, e.g. every one second. Secondly, when the status ( CoreID in the hello message) of a node changes, it will broadcast one hello message immediately.
Step 3: Supplement of cores . After Step 2, each node checks if there are cores in the range R max . If there exists, it will regard the core who has the least Delay between them as its parent. That is, this node will be the member of the sub-AS dominated by its parent core. Then nodes update the CoreID in their hello messages with their parent cores' ID. Note that, a core node uses its own ID for this field. However, each node only has the local information. After Step 2, some nodes may remain without parent. As shown in Fig. 3 , the height values of node A , B , C , D and E are 2, 3.1, 3, 4 and 1 respectively. A is the highest height neighbor of E ; C is the height neighbor of A ; and D is the height neighbor of C . So after the first core selection step, node A and E remain without parent.
PPT Slide
Lager Image
Node A and E remain without parent.
Hence, supplement of new cores is needed. Nodes whose CoreID are zero (without parent) calculate their height functions (e.g., node A and E in Fig. 3 ). And the node who has the highest height among its neighbors without parent in the range R max should serve as a core (e.g., node A in Fig. 3 ). If there are still nodes without parent, another cycle of supplement starts. After λ cycles of supplement, there are only two kinds of nodes, cores and members.
Step 4: Optimization and maintenance process . Considering nodes' mobility, and in order to keep the number of cores as low as possible, if a core detects there are other cores in the range R max (from the hello process), it will check whether it has the highest height among these cores. If not, it will turn into a member of the highest height core, and its member nodes will turn into nodes without parent. If there exist nodes without parent in the AS, process will turn to Step 3. Finally, there are only two kinds of nodes, cores and members. And this optimization and maintenance process will keep monitoring the AS network. For instance, if a new node joint in the network, the process will take this node as a without parent node, and turn to Step 3.
- 3.2 Phase 2: Intra-sub-AS Topology Control
In this phase, we present a centralized algorithm for intra-sub-AS network. Each core will calculate the links for all of the members of its sub-AS such that the resulting topology of the sub-AS meets the given topology constraint (min-max delay and k -connectivity). The intra-sub-AS topology control algorithm is described in Algorithm 1 , where G represents the AS, and let G 1 , G 2 ,⋯, Gn (sub-AS) be a partitioning of G .
PPT Slide
Lager Image
For each sub-AS, Algorithm 1 ensures that Gk preserve the k -connectivity of Gs i.e., CON ( Gs , k )⇒ CON ( Gk , k ) And the maximum end to end delay among all edges in the sub-AS network is minimized by Algorithm 1 , i.e., let D max ( Gk ) be the maximum delay of all edges in the sub-AS minimized by Algorithm 1 , and let Sk ( Gs ) be the set of all kinds of k-connected sub-graphs of ( Gs ), then we have D max ( Gk )=min{ D max ( Gi )| Gi Sk ( Gs )}. The strong connectivity of Algorithm 1 is provided in section 4.
- 3.3 Phase 3: Inter-sub-AS Topology Control
In this phase, connectivity between adjacent sub-AS networks is considered. In order to allow adjacent sub-AS networks to discover each other, every node continue broadcasting hello message ( NdelID , Location , CoreID , Degree , Delay ) as in Phase 1 periodically. When a node u receives a hello message from a node that belongs to a different sub-AS (e.g., they have different CoreID ), u will place v 's information in its border list. Then this border list is reported to the node's parent core. With these border lists, we present a distributed algorithm for inter-sub-AS. This algorithm is described in Algorithm 2 . Where G represents the AS, and let G 1 , G 2 ,⋯, Gn (sub-AS) be a partitioning of G .
In this algorithm, the core of a sub-AS A checks whether there exist k disjoint links from this sub-AS to each adjacent sub-AS B . That is accomplished by applying an algorithm ( MaxMatching ) [22] that computes a matching of maximum cardinality in a bipartite graph defined by the nodes in respective sub-AS networks and the edges with one vertex in each sub-AS. If k does not exceed the size of maximum cardinality matching, the core of sub-AS A select k disjoint links that meet the min-max delay optimal. When there does not exist k disjoint links between A and B (only km disjoint links), the core preserve the km -connectivity between these two sub-AS networks and minimize the maximum delay between them. Note that this connectivity preservation ( km -connectivity) cannot guarantee k -connectivity between sub-AS A and B . However, global k -connectivity can be guaranteed after Phase 3 is completed when connectivity with other neighboring sub-AS networks is already established. This will be proved in section 4.
Parameter DIA ( G 1 , G 2 ) in Algorithm 2 is used to perform an optimization which removes unnecessary links between certain adjacent sub-AS networks, while preserving the connectivity of the resulting topology. DIA ( G 1 , G 2 ) is the maximum delay of the selected k links. However, when the number km of disjoint links between two adjacent sub-AS networks is less than k , DIA ( G 1 , G 2 ) is ∞ . Then, as shown in Fig. 4 , sub-AS A will not connect to a neighboring sub-AS B directly if it observes that there exists another sub-AS C , where C is also a neighbor of B , and both DIA ( GA , GC ) and DIA ( GB , GC ) are less than DIA ( GA , GB ).
PPT Slide
Lager Image
Inter-sub-AS links between A and B are not necessary if there exist an neighboring sub-AS C such that both DIA(GA,GC) and DIA(GB,GC) are less than DIA(GA,GB).
PPT Slide
Lager Image
After Phase 3 is completed, each node is assigned a link list, and nodes connect each other according to these lists. This topology will be maintained by every node with hello message periodically, and always preserve the objective connectivity of the network.
4. Proof of Strong Connectivity
In this section, we prove that the strong connectivity of Algorithm 1 and Algorithm 2 [23] . The results are given as the following theorems.
- 4.1 Strong connectivity ofAlgorithm 1
Theorem 1. Algorithm 1 can preserve k-connectivity of sub-AS Gs, i.e., CON ( Gs,k )⇒ CON ( Gs,k ). And the maximum delay among all nodes in the network is minimized by Algorithm 1 .
Before proving the correctness of Theorem 1, two lemmas are first provided. Let
PPT Slide
Lager Image
be the path from node u to v (as defined in Definition 2). Let the maximal set of disjoint paths from node u to v be represented by P u,v ( Gs ), i.e., ∀ pm , pn P u,v ( Gs ), pm pn ={ u , v }. If edge e 0 ( u , v ), let Gs - e 0 be the resulting graph by removing the edge e 0 from Gs
Lemma 1. Let u and v be two vertices in the k-connected graph Gs, if u and v are still k-connected after the removal of edge e 0 , =( u , v ) then CON ( Gs - e 0 , k ).
Proof of Lemma 1: In order to prove CON ( Gs - e 0 , k ), we prove G's = Gs - e 0 is connected with the removal of any k -1 vertices from G's . We already know that u and v are k -connected in G's . Thus, considering any two vertices { u 1 , v 1 }, we assume that { u 1 , v 1 }∩{ u , v }= φ . We only need to prove u 1 is still connected to v 1 after the removal of a set k -1 vertices X ={ x 1 ,⋯, x k-1 }, where xi ∈( V ( G's )-{ u 1 , v 1 }). If ( u 1 , v 1 ) is an edge in G's . that is obviously true. Hence, we only consider the case that there is no directly edge from u 1 to v 1
Since CON ( Gs , k ) we have | P u1,v1 ( Gs )|≥ k , where | P u1,v1 ( Gs )| is the number of paths in the set P u1,v1 ( Gs ). Let r 1 be the number of paths in P u1,v1 ( G's ) that are broken after the removal of vertices in the set of X , i.e., r 1 ={ p P u1,v1 ( G's )|( xi X )∧( xi p )}. We know that paths in P u1,v1 ( G's ) are disjoint, so the removal of any one vertex in X can only break at most one path in P u1,v1 ( G's ). Given | X |= k -1, we have r 1 k -1.
Let G"s be the resulting graph by removing X from G's . If | P u1,v1 ( G's )|≥ k , we have | P u1,v1 ( G"s )|≥(| P u1,v1 ( G's )|- r 1 )≥1, i.e., u 1 is still connected to v 1 in G"s . Otherwise, | P u1,v1 ( G's )|< k , it occurs only if the removal of edge e 0 =( u , v ) breaks one path pj P u1,v1 ( Gs ). Without loss of generality, let the order of vertices in the path pj be
PPT Slide
Lager Image
. Since the paths in P u1,v1 ( Gs ) are disjoint, the removal of edge e 0 breaks at most one path, i.e., | P u1,v1 ( Gs )-{ pj }|≥ k -1. So we have | P u1,v1 ( G's )-{ pj }|= k -1
If r 1 < k -1, it is obvious that (| P u1,v1 ( G's )|- r 1 )≥1. Hence | P u1,v1 ( G"s )|≥1. That is, u 1 is still connected to v 1 in G"s . Otherwise, if r 1 = k -1, every vertex in the set X belongs to the paths in P u1,v1 ( G's ). We know that pj P u1,v1 ( Gs ) is disjoint with the paths in P u1,v1 ( G's ), so we have pj X = φ . Hence, no vertex in
PPT Slide
Lager Image
is removed with the removal of X . So, with the removal of e 0 , u 1 is still connected to u , and v is still connected to v 1 in G"s . With the assumption that u and v are still k -connected after the removal of edge e 0 =( u , v ) in Lemma 1. It is obvious that u is still connected to v in G"s . So u 1 is still connected to v 1 in G"s .
We have proved that for any two vertices { u 1 , v 1 }∈ G's , u 1 is connected to v 1 with the removal of any k -1 vertices from V ( G's )-{ u 1 , v 1 }. Hence, CON ( G's , k ).
Lemma 2. Let Gs and Ĝs be two graphs, where CON ( Gs , k ) and V ( Gs )= V ( Ĝs ). If every edge subject to ( u , v )∈( E ( Gs )- E ( Ĝs )) satisfies that u is still k-connected to v in graph Gs -{( u' , v' )∈ E ( Gs )| w ( u' , v' )≥ w ( u , v )} , then CON ( Ĝs , k ).
Proof of Lemma 2: Without loss of generality, let { e 1 , e 2 ,⋯, em }= E ( Gs )- E ( Ĝs )={( u 1 , v 1 ),( u 2 , v 2 ),⋯,( um , vm )} be a set of edges subject to w ( e 1 )> w ( e 2 )>⋯> w ( em ). We define a series of sub-graphs of Gs : G 0 s = Gs , and Gis =
PPT Slide
Lager Image
- ei , where i =1,2,⋯, m . Then we have Gms = Gs -{ e 1 , e 2 ,⋯, em }, and E ( Gms )⊆ E ( Ĝs ). Here we prove Lemma 2 by induction.
Base: Obviously, we have G 0 s = Gs , and CON ( G 0 s , k ).
Induction: If CON (
PPT Slide
Lager Image
, k ), we prove that CON ( Gis ), where i =1,2,⋯, m . Since Gs -{( u' , v' )∈ E ( Gs )| w ( u' , v' )≥ w ( ui , vi )}⊆
PPT Slide
Lager Image
-( ui , vi ), and from the assumption of Lemma 2 ( ui is k -connected to vi in graph Gs -{( u' , v' )∈ E ( Gs )| w ( u' , v' )≥ w ( ui , vi )}), we obtain that ui is k -connected to vi in graph
PPT Slide
Lager Image
-( ui , vi ). Applying Lemma 1 to
PPT Slide
Lager Image
, it is obvious CON (
PPT Slide
Lager Image
-( ui , vi ), k ). That is, CON ( Gis , k ).
By induction, we have CON ( Gms , k ). Since E ( Gms )⊆ E ( Ĝs ), hence CON ( Ĝs , k ).
Finally, we prove the correctness of Theorem 1.
Proof of Theorem 1: In Algorithm 1 , we sort all edges in Gs =( Vs , Es ) in ascending order of weight . Whether ( u , v )∈ Es should be placed into Gk depending on the connection of u and v , and edges of smaller weights. ∀( u 0 , v 0 )∈ E ( Gs )- E ( Gk ), the edge ( u 0 , v 0 ) is not placed Gk , but u 0 is k-connected to v 0 . Obviously, any edge ( u' , v' ) subject to (( u' , v' )∈ E ( Gs ))∧( w ( u' , v' )≥ w ( u 0 , v 0 )) is not needed to be placed into Gk for the current node u 0 and v 0 . Hence, for every edge ( u , v )∈ E ( Gs )- E ( Gk ), we have u is k -connected to v in Gs -{( u' , v' )∈ E ( Gs ))∧( w ( u' , v' )≥ w ( u , v )}. Applying Lemma 2 here, then we can prove that CON ( Gs , k )⇒ CON ( Gk , k ).
Recall that D max ( Gk ) is the maximum delay of all edges in the sub-AS minimized by Algorithm 1 , and Sk ( Gs ) is the set of all kinds of k -connected sub-graphs of Gs . The maximum delay among all edges in the network is minimized by Algorithm 1 can be described as D max ( Gk )=min{ D max ( Gi )| Gi Sk ( Gs )}.
Let ( um , vm ) be the last edge that is placed into Gk , i.e., w ( um , vm )=max (u,v)∈E(Gk) { w ( u , v )}. Let G'k = Gk -( um , vm ), then we obtain that | P um,vm ( G'k )|< k . Now, we assume that there is a graph Hs =( V ( Hs ), E ( Hs )) , where V ( Hs )= V ( Gs ) , and E ( Hs )={( u , v )∈ E ( Gs )| w ( u , v )< w ( um , vm )}. If we can prove that CON ( Hs , k ) is not true, we will obtain that any Gi Sk ( Gs ) should have at least one edge equal to or heavier than ( um , vm ). That is, D max ( Gk )=min{ D max ( Gi )| Gi Sk ( Gs )}. We prove CON ( Hs , k ) is not true by contradiction in the following.
Assume that CON ( Hs , k ), hence, | P um,vm ( Hs )|≥ k . We have Hs - G'k ≠φ. Since all edges are placed into G'k the ascending order, ∀( u , v )∈ Hs - G'k should satisfy that u is k -connected to v in Hs -{( u' , v' )∈ E ( Hs )| w ( u' , v' )≥ w ( u , v )}. Applying Lemma 2 here, we obtain that CON ( G'k , k ). That is, | P um,vm ( G'k )|≥ k , which is a contradiction.
- 4.2 Strong connectivity ofAlgorithm 2
Theorem 2. Let G =( V , E ) be the initial topology of an AS. Let G' =( V , E' ) be the topology after Algorithm 2 is completed. Then we have CON ( G , k )⇔ CON ( G' , k ).
Before proving the correctness of Theorem 1, several lemmas used in that proof are first provided.
Lemma 3. Let Gi =( Vi , Ei ) and Gj =( Vj , Ej ) be two sub-graphs of graph G. If NBRG ( Gi , Gj , k ) , then CON ( Gi G Gj , k ).
Proof of Lemma 3: In order to prove CON ( Gi G Gj , k ), we prove Gi G Gj is connected with the removal of any k -1 vertices from it. Since NBRG ( Gi , Gj , k ), we have CON ( Gi , k ) and CON ( Gj , k ), i.e., consider any u , v Gi or u , v Gj , u is k -connected to v . Then we only need to consider the case ( u Gi )∧( v Gj ).
Since NBRG ( Gi , Gj , k ), ∃ u 0 Gi , v 0 Gj , u 0 is connected to v 0 with the removal of any k -1 vertices from Vi Vj -{ u 0 , v 0 }. With CON ( Gi , k ) and CON ( Gj , k ), we know that u is connected to u 0 , and v is connected to v 0 . Hence u is connected to v . That is, Gi G Gj is connected with the removal of any k -1 vertices from it.
Corollary 1. Let sub-graphs G 1 , G 2 ,⋯, Gn be a partitioning of G. Let Sm be the maximal set of sub-graphs subject to Gi , Gj Sm , MCONG ( Gi , Gj , k ) . Then, G { Gi | Gi Sm } is k-connected.
Lemma 4. Let Gs be a sub-graph of G, and let G's be edges reduction of Gs . Let G" =( V , E' )=( G - Gs )∪ G G's . If CON ( Gs , k )∧ CON ( G's , k )∧ CON ( G , k ) , then CON ( G"s , k ).
Proof of Lemma 4: In order to prove CON ( G"s , k ), we prove ∀ u , v G" is connected with the removal of any k -1 vertices from G" . Without loss of generality, three cases are considered in the following.
1) u , v Vs : It is obvious true because of CON ( G's , k )
2) u Vs and v V - Vs Since CON ( G , k ), u is connected to v in path p with the removal of any k -1 vertices in G . If p E - Es , p is also exist in G" , u is connected to v by removing those k -1 vertices. Otherwise, ∃( a p )∧( a Vs ) and a is connected to v in G - Gs . Since CON ( G's , k ), u is connected to a by removing those k -1 vertices. Then u is connected to v with the removal of any k -1 vertices in G" .
3) u , v V - Vs : Similarly, since CON ( G , k ), u is connected to v in path p with the removal of any k -1 vertices in G . If p E - Es , u is k -connected to v in G" . Otherwise, ∃( a 1 , a 2 p )∧( a 1 , a 2 Vs ), u is connected to a 1 and a 2 is connected to v in G - Gs . Since CON ( G's , k ), a 1 is connected to a 2 by removing those k -1 vertices. Then u is connected to v with the removal of any k -1 vertices in G" .
Corollary 2. Let G 1 , G 2 ,⋯, Gn be k-connected sub-graphs of k-connected graph G. Let G' 1 , G' 2 ,⋯, G'n be edges reduction of G 1 , G 2 ,⋯, Gn , and G' 1 , G' 2 ,⋯, G'n are k-connected. Then,
PPT Slide
Lager Image
is k-connected.
Lemma 5. Let G =( V , E ) be the initial topology of an AS. Let G' =( V , E' ) be the topology after Algorithm 2 is completed. Let Gi =( Vi , Ei ) be the sub-AS networks resulting from Phase 1 in the topology control, where i =1,⋯, n . Let G'i =( Vi , E'i ) , where E'i = Ei E' . Then, i , j subject to 1≤ i j n , we have MCONG ( Gi , Gj , k )⇒ MCONG' ( G'i , G'j , k ).
Proof of Lemma 5: Since nodes of any intra-sub-AS are k -connected. We take sub-AS as a node here. Formally, we represent graph G as
PPT Slide
Lager Image
, where Vs ={ G 1 , G 2 ,⋯, Gn } and Es ={( Gi , Gj )| NBRG ( Gi , Gj , k )}. Actually, edge ( Gi , Gj ) contains at least k disjoint paths between Gi and Gj . Let
PPT Slide
Lager Image
be the sub-AS level representation of G' , where E's ={( G'i , G'j )| NBRG' ( G'i , G'j , k )}. We use Vs to represent the set of sub-AS networks in
PPT Slide
Lager Image
, because we need not to consider the topology of intra-sub-AS (both Gi and G'i are k -connected). We take all of them as nodes, so we consider ( Gi , Gj ) and G'i , G'j as the same edge. Recall that in Algorithm 2 , each edge ( Gi , Gj )∈ Es has a weight DIA ( Gi , Gj ).
In order to prove Lemma 5, it suffices to show that
PPT Slide
Lager Image
is connected to Gj in
PPT Slide
Lager Image
. We order all edges in
PPT Slide
Lager Image
in the ascending sequence of weights, and then judge whether an edge should be place into
PPT Slide
Lager Image
. Without loss of generality, let the ordering be ( e 1 , e 2 ,⋯, em ), where m =| Es |. Then we prove Lemma 5 by induction.
Base: Obviously, the pair of sub-AS networks corresponding to edge e 1 should always be placed into
PPT Slide
Lager Image
, i.e., e 1 E's .
Induction: t m , if for all q < t , the pair of sub-AS networks corresponding to eq are connected in
PPT Slide
Lager Image
(either directly or indirectly). And suppose et =( Gi , Gj ). From Algorithm 2 , the only reason why et E's ( Gi is not directly connected to Gj in
PPT Slide
Lager Image
) is that there exists another sub-AS Gi , where both DIA ( Gi , Gl ) and DIA ( Gl , Gj ) is less than DIA ( Gi , Gj ). However, since edges ( Gi , Gl ) and ( Gl , Gj ) come before ( Gi , Gj ) in the ascending order. From path
PPT Slide
Lager Image
, Gi is connected to Gj in
PPT Slide
Lager Image
.
By induction, we prove that Gi is connected to Gj in
PPT Slide
Lager Image
, and then MCONG ( Gi , Gj , k )⇒ MCONG' ( G'i , G'j , k ).
Finally, we prove the correctness of Theorem 2. In the proof, Gi and G'i have the same definition in Lemma 5.
Proof of Theorem 1: For every sub-AS Gi , we know that CON ( Gi , k ) is true after Algorithm 1 . Then we partition those sub-AS networks into sets A 1 ,⋯, As , where each set contains sub-AS networks are multihop k -connected in G , i.e., ∀ r =1,⋯, s , then, ( Gi Ar )∧( MCONG ( Gi , Gj , k ))⇒ Gj Ar . Then we define sets A'1 ,⋯, A's , where ∀ i , Gi Ar )⇒ G'i A'r . Applying Lemma 5 here, for every
PPT Slide
Lager Image
∀1≤ i j m , we have
PPT Slide
Lager Image
Take A'r as a sub-graph of G' ,
PPT Slide
Lager Image
where
PPT Slide
Lager Image
and
PPT Slide
Lager Image
Since A'r only contains multihop k -connected sub-graphs, applying Corollary 1 here, we have A'r is k -connected. Then, applying Corollary 2 here, we have
PPT Slide
Lager Image
is k -connected. Then CON ( G , k )⇔ CON ( G' , k ).
5. Control Message Complexity Analysis
We study the control message complexity here by computing the total number of control messages exchanged during the three phases of the AS-TC algorithm. The following terms are used in the complexity analysis.
Let N be the total number of nodes in the AS network. Let S be the number of sub-AS networks, and NS be the average number of nodes per sub-AS, i.e., NS = N / S . Let RB be the average probability of nodes that are border nodes in a sub-AS, where 0< RB <1. Let SN be the average number of neighboring sub-AS networks for each sub-AS, i.e., 0< SN < S . Let λ be the cycles of cores supplement.
Table 1 shows the average control messages utilized in each phase to complete the topology algorithm for each sub-AS. We partition each phase into major steps. Hence, from Table 1 , the total number of control messages required in the AS is S ((2+ λ + RB ) NS +2 SN +2). It can be simplified as (2+ λ + RB ) N +2 SNS +2 S , which is O ( N )+ O ( SNS ) in the worst case.
Average message complexity in each phase of a sub-AS
PPT Slide
Lager Image
Average message complexity in each phase of a sub-AS
6. Simulation Results and Discussions
In this section, we present several sets of simulation results to evaluate the effectiveness of the proposed AS-TC algorithm. Recall that the proposed algorithm is a hybrid of centralized algorithm and distributed algorithm. We compare it with typical centralized algorithm FGSS k [17] and distributed algorithm FGSS k [17] . We chose these two algorithms because they are also min-max optimal as our algorithm. These simulations were carried out using the NS2 simulator.
In this simulation study, the wireless channel is symmetric (i.e., both the sender and the receiver should observe the same channel fading) and obstacle-free, and each node has an equal maximal transmission range R max =350 km. Nodes are randomly distributed in a 2000×2000 km 2 region. In order to study the effect of sub-AS size on the resulting topologies, we vary the number of nodes in the region among 125, 150, 175, 200, 225, 250.
For each network, we consider:
1) k -connectivity: k =1, k =2 and k =4;
2) algorithms: the proposed hybrid algorithm AS-TC, centralized algorithm FGSS k and distributed algorithm FGSS k ;
3) 1000 Monte Carlo simulations.
Relative to AS-TC, recall that in Phase 1 of sub-AS network formation, we configure that each node is at most one hop away from its parent core. In our simulations, algorithm in Phase 1 generates sub-AS networks where the average number of nodes per sub-AS is 6.68, 7.67, 8.64, 9.69 and 10.15 (results of 1000 simulations), respectively. Note that, by varying the number of nodes in the network while maintaining other parameters such as the region size and maximal transmission range of nodes, we implicitly adjust the node degree of these topology control algorithms.
Before providing the experimental results regarding time delay, we first observe the actual topologies for one simulated network using AS-TC algorithm. Four figures are given here.
1) Fig. 5 (a) shows the original physical topology without topology control. All nodes communicate with the maximal transmission range R max .
2) Fig. 5 (b) shows the topology after applying algorithm of Phase 1. Nodes of the AS are divided into 19 sub-AS networks, where the average number of nodes per sub-AS is 6.58.
3) Fig. 5 (c) is the topology resulting from the intra-sub-AS topology control algorithm of Phase 2, when k =2.
4) Fig. 5 (d) shows the topology after applying inter-sub-AS Topology control algorithm of Phase 3, when k =2. The inter-sub-AS links are represented by black color.
PPT Slide
Lager Image
Network topologies of 125 nodes with different topology control settings. (a) Without topology control. (b) After applying algorithm of Phase 1. (c)k=2, after applying algorithm of Phase 2. (d)k=2, after applying algorithm of Phase 3.
In Fig. 6 , we show average and maximum delay between two nodes which obtained from three topology control algorithm (the proposed hybrid algorithm AS-TC, centralized algorithm FGSS k [17] and distributed algorithm FGSS k [17] . Note that, we only consider link propagation delay in the simulation. It is evident from those results that AS-TC is very effective in reducing the delay between nodes. Recall that the maximal transmission range R max of one node is 350 km. The corresponding delay is 1.167 ms. When k =1 ( Fig. 6 (a)), AS-TC reduces the maximum delay to 0.864 ms when there are 125 nodes in the AS and as low as 0.577 ms when there are 225 nodes. The maximum delay is approximately 9.5% to 18.1% lower than FLSS 1 distributed algorithm, and 10.9% to 18.9% higher than FGSS 1 centralized algorithm. For the average delay, AS-TC reduces the delay to 0.524 ms when there are 125 nodes in the AS and as low as 0.354 ms when there are 225 nodes, which is approximately 9.0% to 12.1% lower than FLSS 1 distributed algorithm, and 10.8% to 13.2% higher than FGSS 1 centralized algorithm.
PPT Slide
Lager Image
Results from three topology control algorithms (AS-TC, FGSSk and FLSSk) showing average and maximum link delay when (a)k=1, (b)k=2, (c)k=4 and (d) average node degree.
When k =2 ( Fig. 6 (b)), both the maximum and average delay resulting from AS-TC, FGSS 2 and FLSS 2 are all higher than when k =1. That is expected because 2-connected is a stronger property than 1-connected. What's more, the difference among the three algorithms when k =2 is in a greater range than when k =1. This is the consequence of having to maintain another higher delay link between adjacent sub-AS networks and one more additional disjoint path from each node to other nodes within all sub-AS networks. The maximum delay of AS-TC is approximately 12.9% to 19.8% lower than FLSS 2 distributed algorithm, and 14.9% to 20.8% higher than FGSS 2 centralized algorithm. The average delay of AS-TC is approximately 12.9% to 16.6% lower than FLSS 2 distributed algorithm, and 10.7% to 18.4% higher than FGSS 2 centralized algorithm.
When k =4 ( Fig. 6 (c)), as expected, both the maximum and average delay resulting from the three algorithms are all higher than when k =1 and k =2. However, the differences among the three algorithms are in a small range when there is little number of nodes in the network, e.g., when number of nodes is 125. The main causes of this phenomenon are the following two aspects: 1) The maximal transmission range R max of each node is 350 km, and the corresponding delay is 1.167 ms (we only consider link propagation delay in the simulation). In order to achieve stronger connectivity ( k =4), more links are preserved, but all the links’ delay is less than 1.167 ms. This upper bound of link delay make the performance differences among the three algorithms small when most links of the original topology should be preserved. 2) When the density of nodes in the network is relative low, the connectivity of the original network topology (without topology control) may not achieve k =4, i.e., only k' -connectivity, k' <4. In this case, the three algorithms not only do their best to preserve global k' -connectivity but also guarantee local or partly k -connectivity that the original network can achieve. So, a lot of long delay links are preserved. And considering the upper bound of link delay (1.167 ms), the performance differences among the three algorithms become smaller. The maximum delay of AS-TC is approximately 1.3% to 16.0% lower than FLSS 4 distributed algorithm, and 3.3% to 12.7% higher than FGSS 4 centralized algorithm. The average delay of AS-TC is approximately 5.3% to 12.3% lower than FLSS 4 distributed algorithm, and 7.1% to 13.3% higher than FGSS 4 centralized algorithm.
The delay performance of the proposed algorithm AS-TC falls in between FGSS k and FLSS k . This is expected because AS-TC is a hybrid of centralized algorithm and distributed algorithm. Even though centralized algorithm has better delay performance (only 7.1% to 18.4%), they are not suitable for large scale networks. Because excessive amounts of control messages need to be collected by one central entity, and long delay makes the control messages exchanged with remote nodes costly. However, the control message exchange in AS-TC is constrained among neighboring sub-AS networks, and the delay performance is better than distributed algorithm in the simulation result. Thus, the proposed AS-TC algorithm is better than centralized algorithm and distributed algorithm for SIN.
Fig. 6 (d) shows the average node degree of the topologies derived under AS-TC, FGSS k and FLSS k for k =1, 2 and 4. The average degree without topology control increases almost linearly with the number of nodes. In contrast, the average degree under all the three algorithms actually slightly decreases. It is obvious that the node degree of a network with AS-TC does not depend on the size or density of the network. What’s more, when with the same k , the average degree under AS-TC falls in between FGSS k and FLSS k . This is because AS-TC is a hybrid of centralized algorithm and distributed algorithm, and the centralized algorithm usually has the best performance.
Fig. 7 illustrates the number of messages exchanges required per node to complete AS-TC, FGSS k and FLSS k . Each node in FLSS k only exchanges control messages with its visible neighborhoods ( R max =350 km), so FLSS k has the lowest message complexity. Recall that the message complexity of the AS-TC algorithm is O ( N )+ O ( SNS ). For each node, the average number of messages required is ( O ( N )+ O ( SNS )/ N = O (1). The result validates the analysis. When number of nodes in the AS increases from 125 to 225, the average number of messages required per node in AS-TC does not increase. This shows the AS-TC algorithm has little extra overhead. In contrast, each node in FGSS k algorithm sends a message to announce its existence to all other nodes in the network. Since no node has global knowledge of the network at the beginning, the message distribution in the simulation is done by flooding. Thus, a message from one node may travel every link of the network. Therefore, the total number of messages is O ( N 2 ) in the worst case. For each node, the average number of messages required is O ( N 2 )/ N = O ( N ). When number of nodes in the AS increases, the average number of messages required per node in FGSS k also increases.
PPT Slide
Lager Image
Number of messages exchanges per node derived under AS-TC, FGSSk, FGSSk for k=2 .
7. Conclusion
We studied the topology control problem in the SIN using a hierarchical AS approach. The motivation was that the AS network model decouples the complex SIN into simple sub-AS networks, and make the topology control of the SIN easier to carry out. Then we proposed the AS-TC algorithm to minimize time delay in the SIN. Compared with most existing approaches for SIN where either the purely centralized or the purely distributed control method is adopted, AS-TC utilizes a hybrid method. In this way, not only the control message exchange is constrained among local neighboring sub-AS networks, but also the strong connectivity of the network is preserved. Our simulation results validated the theoretic analysis and effectiveness of the AS-TC algorithm.
Although the assumptions stated in Section 2 are widely used in existing topology algorithms, some of them may not be practical. Our future work will focus on how to relax these constraints (e.g. nodes in one AS are homogeneous, and they have the same R max ) for AS-TC algorithm so as to improve its practicality in real applications. Furthermore, we will also consider the topology control of AS-1 (constituted by satellites) in the near future.
BIO
Wei Zhang received the B.S. degree (with honors) in communication engineering from Xidian University, Xi’an, China, in 2009 and the M.S. degree from College of Communication Engineering, PLA University of Science and Technology, Nanjing, China, in 2012. He is currently pursuing the Ph.D. degree in communications and information systems in College of Communications Engineering, PLA University of Science and Technology. His research interests include satellite communications, deep space communications, space information networks and wireless sensor networks. He currently serves as a regular reviewer for International Journal of Distributed Sensor Networks.
Gengxin Zhang received his M.S. and Ph.D. degrees from the Institute of Communication Engineer, Nanjing, China in 1990 and 1993 respectively. He is currently a Professor in PLA University of Science and Technology (PLAUST), Nanjing, China. His research interests include the design of communication systems, satellite and deep space communications.
Liang Gou received his B.S. and M.S. degrees from PLA University of Science and Technology (PLAUST), Nanjing, China in 2004 and 2008 respectively. He is currently a Ph.D. candidate in PLAUST. His research interests are focused on satellite communications, deep space communications, network coding and wireless sensor networks.
Bo Kong received the B.S. degree from Xidian University, Xi’an, China in 2010, and his M.S. degree from PLA University of Science and Technology (PLAUST), Nanjing, China in 2013. He is currently a Ph.D. candidate in PLAUST. His research interests are focused on satellite communications, deep space communications, and cooperative communications.
Dongming Bian received his Ph.D. degree from PLA University of Science and Technology (PLAUST), Nanjing, China in 2004. He is currently a Professor in PLAUST. His research interests mainly fall in the area of wireless communications, satellite communications and deep space communications.
References
Mukherjee J. , Ramamurthy B. 2013 “Communication Technologies and Architectures for Space Network and Interplanetary Internet,” IEEE Communication Surveys and Tutorials 15 (2) 881 - 897    DOI : 10.1109/SURV.2012.062612.00134
Bhasin K. B. , Hayden J. K. “Architecting Communication Network of Networks for Space System of Systems,” in Proc. of the IEEE System of Systems Engineering Conference 2008 1 - 7
Hu H.-F. , Liu Y.-A. “A Feasible Mesh-based Architecture and Protocol Model of Space Information Network,” in Proc. of the IEEE Geoscience and Remote Sensing Conference 2010 529 - 531
Ren F. , Fan J.-L. 2013 “An Adaptive Distributed Certificate Management Scheme for Space Information Network,” IET Information Security 7 (4) 318 - 326    DOI : 10.1049/iet-ifs.2012.0253
Zhang G.-X. , Zhang W. , Zhang H. , Xie Z.-D. “A Novel Proposal of Architecture and Network Model for Space Communication Network,” in Proc. of the IAF 65th International Astronautical Congress 2014 https://iafastro.directory/iac/archive/browse/IAC-14/B2/3/23563/ 1 - 7
Guo B.-Y. , Guan Q.-S. , Yu F. R. , Jiang S.-M. , Leung V. C. M. 2014 “Energy-Efficient Topology Control with Selective Diversity in Cooperative Wireless Ad Hoc Networks: A Game-Theoretic Approach,” IEEE Transactions on Wireless Communications 13 (11) 6484 - 6495    DOI : 10.1109/TWC.2014.2325864
Ao X. , Yu R. , Jiang S.-M. , Guan Q.-S. , Leung V. C. M. 2013 “Distributed Cooperative Topology Control for WANETs with Opportunistic Interference Cancelation,” IEEE Transactions on Vehicular Technology 63 (2) 789 - 801    DOI : 10.1109/TVT.2013.2278101
Liu L.-F. , Liu Y. , Zhang N. S. 2014 “A Complex Network Approach to Topology Control Problem in Underwater Acoustic Sensor Networks,” IEEE Transactions on Parallel and Distributed Systems 25 (12) 3046 - 3055    DOI : 10.1109/TPDS.2013.2295793
Shang D.-Z. , Zhang B.-X. , Yao Z. , Li C. 2014 “An Energy Efficient Localized Topology Control Algorithm for Wireless Multihop Networks,” Journal of Communication and Networks 16 (4) 371 - 377    DOI : 10.1109/JCN.2014.000066
Huang M.-S. , Chen S.-Y. , Zhu Y. , Wang Y. 2013 “Topology Control for Time-Evolving and Predictable Delay-Tolerant Networks,” IEEE Transactions on Computers 62 (11) 2308 - 2321    DOI : 10.1109/TC.2012.220
Li M. , Li Z.-J. , Vasilakos A. V. 2013 “A Survey on Topology Control in Wireless Sensor Networks: Taxonomy, Comparative Study, and Open Issues,” inProc. of the IEEE 101 (12) 2538 - 2557    DOI : 10.1109/JPROC.2013.2257631
Sardellitti S. , Barbarossa S. , Swami A. 2012 “Optimal Topology Control and Power Allocation for Minimum Energy Consumption in Consensus Networks,” IEEE Transactions on Signal Processing 60 (1) 383 - 399    DOI : 10.1109/TSP.2011.2171683
Awwad O. , Al-Fuqaha A. , Khan B. , Brahim G. B. 2012 “Topology Control Schema for Better QoS in Hybrid RF/FSO Mesh Networks,” IEEE Transactions on Communications 60 (5) 1398 - 1406    DOI : 10.1109/TCOMM.2012.12.110069
Aziz A. A. , Sekercioglu Y. A. , Fitzpatrick P. , Lvanovich M. 2013 “A Survey on Distributed Topology Control Techniques for Extending the Lifetime of Battery Powered Wireless Sensor Networks,” IEEE Communication Surveys and Tutorials 15 (1) 121 - 144    DOI : 10.1109/SURV.2012.031612.00124
Ramanathan R. , Rosales-Hain R. “Topology Control of Multihop Wireless Networks Using Transmit Power Adjustment,” in Proc. of IEEE INFOCOM 2000 404 - 413
Yu J. , Roh H. , Lee W. , Pack S. , Du D.-Z. 2012 “Topology Control in Cooperative Wireless Ad-Hoc Networks,” IEEE Journal on Selected Areas in Communications 30 (9) 1771 - 1779    DOI : 10.1109/JSAC.2012.121022
Li N. , Hou J. C. 2006 “Localized Fault-Tolerant Topology Control in Wireless Ad Hoc Networks,” IEEE Transactions on Parallel and Distributed Systems 17 (4) 307 - 320    DOI : 10.1109/TPDS.2006.51
Wattenhofer R. , Li L. , Bahl P. , Wang Y.-M. “Distributed topology control for power efficient operation in multihop wireless ad hoc networks,” in Proc. of IEEE INFOCOM 2001 1388 - 1397
Chiwewe T. M. , Hancke G. P. 2012 “A Distributed Topology Control Technique for Low Interference and Energy Efficiency in Wireless Sensor Networks,” IEEE Transactions on Industrial Informatics 8 (1) 11 - 19    DOI : 10.1109/TII.2011.2166778
Liu J. , Lin C. , Ye N. , Li S.-H. , Liu Y. “Importance Evaluation Algorithm of Links and Nodes in Space Information Networks,” in Proc. of the IEEE Internet Technology and Applications Conference 2011 1 - 4
Ye N. , Zhu Z.-L. , Shi J. P. “Distributed Cluster-based Fault-tolerant Topology Control for Space Information Networks,” in Proc. of IEEE Cyber-Enabled Distributed Computing and Knowledge Discovery Conference 2010 210 - 217
Azad A. , Halappanavar M. , Rajamanickam S. , Boman E. G. , Khan A. , Pothen A. “Multithreaded Algorithms for Maximum Matching in Bipartite Graphs,” in Proc. of IEEE Parallel and Distributed Processing Symposium 2012 860 - 872
Bondy J. A. , Murty U. S. R. 2008 Graph Theory Springer https://www.springer.com/us/book/9781846289699