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 (ASTC) 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 subAS 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 ASTC algorithm.
1. Introduction
T
he space information network (SIN) is a new type of selforganizing 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 networkwide objectives such as reducing energy consumption, guaranteeing the robustness, increasing the network capacity and reducing endtoend 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 longdistance links data not only brings additional delay but also reduces the system efficiency
[20
,
21]
. Thus in the SIN topology control, endtoend 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 faulttolerant, 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 subAS networks to ensure strong connectivity after topology control. We propose an AS network topology control (ASTC) algorithm using a hybrid approach. ASTC preserves
k
connectivity and is minmax delay optimal. A minmax algorithm tries to minimize the maximum endtoend delay between any pair of nodes in the network. Briefly, the ASTC algorithm consists of three phases: (i) Nodes in AS network of SIN autonomously form subAS networks and elect subAS cores. (ii) With the topology information gathered from the members of its subAS network, each subAS core minimize the maximum delay between any pair of nodes in the subAS network and guarantee strong connectivity using centralized method. (iii) Each subAS core selects a set of border nodes, shares topology information with neighboring subAS cores, and computes minmax delay links between neighboring subAS 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 (ASTC) algorithm is proposed to achieve low time delay and strong connectivity. It is a hybrid algorithm within a subAS network and among neighboring subAS networks.
3) The strong connectivity of ASTC 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 ASTC to achieve low time delay and strong connectivity. Then, the validity of ASTC 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 selforganizing 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 subnetworks constituted by similar nodes, and the control of them is easier to carry out. AS1 contains all the satellites of SIN and the topology of it is usually high dynamic but predictable. Topology control of AS1 is usually based on satellites constellations design. We will not discuss the topology control of AS1 in this paper. AS2 contains the HAPs, AS3 contains the airplanes and AS4 contains the ground nodes. Properties of AS2/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 AS2/3/4.
The architecture of SIN.
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}
,⋯,
u_{n}
) is the set of nodes (or equivalently, vertices) and
E
={(
u_{i}
,
u_{j}
)(
u_{i}
,
u_{j}
∈
V
)∧(
r
(
u_{i}
,
u_{j}
)≤
R
_{max}
)} is the set of links (edges).
r
(
u_{i}
,
u_{j}
) is the distance between nodes
u_{i}
and
u_{j}
. 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 obstaclefree, 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 subgraphs
G_{i}
=(
V_{i}
,
E_{i}
) and
G_{j}
=(
V_{j}
,
E_{j}
) .
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
It is obvious that edges with the same vertices have equivalent weights. However, edges with different endvertices have different weights.
Definition 2: kconnected
. In graph (topology)
G
, node
u
is said to be connected to node
v
, if there exists a path
, where
x_{i}
∈
V
and (
u
,
x
_{1}
), (
x_{i}
,
x_{j}
),(
x_{m}
,
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 kconnected subgraphs
. For two disjoint subgraphs
G_{i}
and
G_{j}
of
G
, if ∃
u
∈
V_{i}
,
v
∈
V_{j}
and ∃(
u
,
v
)∈
E
,
G_{i}
and
G_{j}
are are neighboring subgraphs, denoted by
NBR_{G}
(
G_{i}
,
G_{j}
). If
CON
(
G_{i}
,
k
)∧
CON
(
G_{j}
,
k
), and ∃(
u
_{1}
,
v
_{1}
),⋯, (
u_{k}
,
u_{k}
)∈
E
, where
u
_{1}
,⋯,
u_{k}
∈
V_{i}
and
v
_{1}
,⋯,
v_{k}
∈
V_{j}
,
G_{i}
and
G_{j}
are neighboring
k
connected subgraphs, denoted by
NBR_{G}
(
G_{i}
,
G_{j}
,
k
).
Definition 4: Multihop kconnected subgraphs
.
G
_{1}
,
G
_{2}
,⋯,
G_{n}
be a partitioning of
G
. If ∃
G_{i}
subject to
NBR_{G}
(
G_{i}
,
G_{j}
,
k
)∧
NBR_{G}
(
G_{l}
,
G_{j}
,
k
),
G_{i}
and
G_{j}
are multihop
k
connected subgraphs, denoted by
MCON_{G}
(
G_{i}
,
G_{j}
,
k
)
3. Algorithms for Topology Control
Recall from the introduction, the design aims of the ASTC algorithm in each AS are twofold: 1) to provide minmax delay optimal through a hierarchical AS approach, and 2) to achieve strong connectivity in the resulting network. The ASTC algorithm does not require the global topology of the AS network to be known by any entity. On the contrary, ASTC relies on subAS network where nodes autonomously form groups in AS, and select a core for each subAS network. It is a hybrid of centralized algorithm and distributed algorithm. A centralized topology control algorithm is applied to each subAS network to achieve the desired connectivity within the subAS, while the desired connectivity between adjacent subAS networks is achieved via localized information sharing between adjacent subAS cores. The following subsections detail the three phases of the ASTC algorithm.
 3.1 Phase 1: SubAS network Formation
The main function of
Phase
1 is to select a minimal number of nodes as cores that dominate the subAS networks by using only 1hop 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 subAS, or become a member of a subAS 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 ASTC algorithm in each AS are twofold: 1) to provide minmax 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
In (2),
f
(·) denotes the balance function,
v_{i}
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
In (3),
is the average of reciprocal delay with every neighboring node. We use reciprocal delay
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
be of the same order of magnitude. The relationship between
hight
(
u
) and
hight
(
v
) is given by
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 subAS 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.
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: IntrasubAS Topology Control
In this phase, we present a centralized algorithm for intrasubAS network. Each core will calculate the links for all of the members of its subAS such that the resulting topology of the subAS meets the given topology constraint (minmax delay and
k
connectivity). The intrasubAS topology control algorithm is described in
Algorithm 1
, where
G
represents the AS, and let
G
_{1}
,
G
_{2}
,⋯,
G_{n}
(subAS) be a partitioning of
G
.
For each subAS,
Algorithm 1
ensures that
G_{k}
preserve the
k
connectivity of
G_{s}
i.e.,
CON
(
G_{s}
,
k
)⇒
CON
(
G_{k}
,
k
) And the maximum end to end delay among all edges in the subAS network is minimized by
Algorithm 1
, i.e., let
D
_{max}
(
G_{k}
) be the maximum delay of all edges in the subAS minimized by
Algorithm 1
, and let
S_{k}
(
G_{s}
) be the set of all kinds of kconnected subgraphs of (
G_{s}
), then we have
D
_{max}
(
G_{k}
)=min{
D
_{max}
(
G_{i}
)
G_{i}
∈
S_{k}
(
G_{s}
)}. The strong connectivity of
Algorithm 1
is provided in section 4.
 3.3 Phase 3: IntersubAS Topology Control
In this phase, connectivity between adjacent subAS networks is considered. In order to allow adjacent subAS 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 subAS (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 intersubAS. This algorithm is described in
Algorithm 2
. Where
G
represents the AS, and let
G
_{1}
,
G
_{2}
,⋯,
G_{n}
(subAS) be a partitioning of
G
.
In this algorithm, the core of a subAS
A
checks whether there exist
k
disjoint links from this subAS to each adjacent subAS
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 subAS networks and the edges with one vertex in each subAS. If
k
does not exceed the size of maximum cardinality matching, the core of subAS
A
select
k
disjoint links that meet the minmax delay optimal. When there does not exist
k
disjoint links between
A
and
B
(only
k_{m}
disjoint links), the core preserve the
k_{m}
connectivity between these two subAS networks and minimize the maximum delay between them. Note that this connectivity preservation (
k_{m}
connectivity) cannot guarantee
k
connectivity between subAS
A
and
B
. However, global
k
connectivity can be guaranteed after
Phase
3 is completed when connectivity with other neighboring subAS networks is already established. This will be proved in section 4.
Parameter
D_{IA}
(
G
_{1}
,
G
_{2}
) in
Algorithm 2
is used to perform an optimization which removes unnecessary links between certain adjacent subAS networks, while preserving the connectivity of the resulting topology.
D_{IA}
(
G
_{1}
,
G
_{2}
) is the maximum delay of the selected
k
links. However, when the number
k_{m}
of disjoint links between two adjacent subAS networks is less than
k
,
D_{IA}
(
G
_{1}
,
G
_{2}
) is ∞ . Then, as shown in
Fig. 4
, subAS
A
will not connect to a neighboring subAS
B
directly if it observes that there exists another subAS
C
, where
C
is also a neighbor of
B
, and both
D_{IA}
(
G_{A}
,
G_{C}
) and
D_{IA}
(
G_{B}
,
G_{C}
) are less than
D_{IA}
(
G_{A}
,
G_{B}
).
IntersubAS links between A and B are not necessary if there exist an neighboring subAS C such that both D_{IA}(G_{A},G_{C}) and D_{IA}(G_{B},G_{C}) are less than D_{IA}(G_{A},G_{B}).
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 kconnectivity of subAS G_{s}, i.e., CON
(
G_{s},k
)⇒
CON
(
G_{s},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
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}
(
G_{s}
), i.e., ∀
p_{m}
,
p_{n}
∈
P
_{u,v}
(
G_{s}
),
p_{m}
∩
p_{n}
={
u
,
v
}. If edge
e
_{0}
(
u
,
v
), let
G_{s}

e
_{0}
be the resulting graph by removing the edge
e
_{0}
from
G_{s}
Lemma 1.
Let u and v be two vertices in the kconnected graph G_{s}, if u and v are still kconnected after the removal of edge
e
_{0}
, =(
u
,
v
)
then CON
(
G_{s}

e
_{0}
,
k
).
Proof of Lemma 1:
In order to prove
CON
(
G_{s}

e
_{0}
,
k
), we prove
G'_{s}
=
G_{s}

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
_{k1}
}, where
x_{i}
∈(
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
(
G_{s}
,
k
) we have 
P
_{u1,v1}
(
G_{s}
)≥
k
, where 
P
_{u1,v1}
(
G_{s}
) is the number of paths in the set
P
_{u1,v1}
(
G_{s}
). 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}
)(
x_{i}
∈
X
)∧(
x_{i}
∈
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
p_{j}
∈
P
_{u1,v1}
(
G_{s}
). Without loss of generality, let the order of vertices in the path
p_{j}
be
. Since the paths in
P
_{u1,v1}
(
G_{s}
) are disjoint, the removal of edge
e
_{0}
breaks at most one path, i.e., 
P
_{u1,v1}
(
G_{s}
){
p_{j}
}≥
k
1. So we have 
P
_{u1,v1}
(
G'_{s}
){
p_{j}
}=
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
p_{j}
∈
P
_{u1,v1}
(
G_{s}
) is disjoint with the paths in
P
_{u1,v1}
(
G'_{s}
), so we have
p_{j}
∩
X
=
φ
. Hence, no vertex in
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
G_{s}
and
Ĝ_{s}
be two graphs, where
CON
(
G_{s}
,
k
)
and
V
(
G_{s}
)=
V
(
Ĝ_{s}
).
If every edge subject to
(
u
,
v
)∈(
E
(
G_{s}
)
E
(
Ĝ_{s}
))
satisfies that u is still kconnected to v in graph
G_{s}
{(
u'
,
v'
)∈
E
(
G_{s}
)
w
(
u'
,
v'
)≥
w
(
u
,
v
)}
, then
CON
(
Ĝ_{s}
,
k
).
Proof of Lemma 2:
Without loss of generality, let {
e
_{1}
,
e
_{2}
,⋯,
e_{m}
}=
E
(
G_{s}
)
E
(
Ĝ_{s}
)={(
u
_{1}
,
v
_{1}
),(
u
_{2}
,
v
_{2}
),⋯,(
u_{m}
,
v_{m}
)} be a set of edges subject to
w
(
e
_{1}
)>
w
(
e
_{2}
)>⋯>
w
(
e_{m}
). We define a series of subgraphs of
G_{s}
:
G
^{0}
_{s}
=
G_{s}
, and
G^{i}_{s}
=

e_{i}
, where
i
=1,2,⋯,
m
. Then we have
G^{m}_{s}
=
G_{s}
{
e
_{1}
,
e
_{2}
,⋯,
e_{m}
}, and
E
(
G^{m}_{s}
)⊆
E
(
Ĝ_{s}
). Here we prove Lemma 2 by induction.
Base:
Obviously, we have
G
^{0}
_{s}
=
G_{s}
, and
CON
(
G
^{0}
_{s}
,
k
).
Induction:
If
CON
(
,
k
), we prove that
CON
(
G^{i}_{s}
), where
i
=1,2,⋯,
m
. Since
G_{s}
{(
u'
,
v'
)∈
E
(
G_{s}
)
w
(
u'
,
v'
)≥
w
(
u_{i}
,
v_{i}
)}⊆
(
u_{i}
,
v_{i}
), and from the assumption of Lemma 2 (
u_{i}
is
k
connected to
v_{i}
in graph
G_{s}
{(
u'
,
v'
)∈
E
(
G_{s}
)
w
(
u'
,
v'
)≥
w
(
u_{i}
,
v_{i}
)}), we obtain that
u_{i}
is
k
connected to
v_{i}
in graph
(
u_{i}
,
v_{i}
). Applying Lemma 1 to
, it is obvious
CON
(
(
u_{i}
,
v_{i}
),
k
). That is,
CON
(
G^{i}_{s}
,
k
).
By induction, we have
CON
(
G^{m}_{s}
,
k
). Since
E
(
G^{m}_{s}
)⊆
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
G_{s}
=(
V_{s}
,
E_{s}
) in ascending order of
weight
. Whether (
u
,
v
)∈
E_{s}
should be placed into
G_{k}
depending on the connection of
u
and
v
, and edges of smaller weights. ∀(
u
_{0}
,
v
_{0}
)∈
E
(
G_{s}
)
E
(
G_{k}
), the edge (
u
_{0}
,
v
_{0}
) is not placed
G_{k}
, but
u
_{0}
is kconnected to
v
_{0}
. Obviously, any edge (
u'
,
v'
) subject to ((
u'
,
v'
)∈
E
(
G_{s}
))∧(
w
(
u'
,
v'
)≥
w
(
u
_{0}
,
v
_{0}
)) is not needed to be placed into
G_{k}
for the current node
u
_{0}
and
v
_{0}
. Hence, for every edge (
u
,
v
)∈
E
(
G_{s}
)
E
(
G_{k}
), we have
u
is
k
connected to
v
in
G_{s}
{(
u'
,
v'
)∈
E
(
G_{s}
))∧(
w
(
u'
,
v'
)≥
w
(
u
,
v
)}. Applying Lemma 2 here, then we can prove that
CON
(
G_{s}
,
k
)⇒
CON
(
G_{k}
,
k
).
Recall that
D
_{max}
(
G_{k}
) is the maximum delay of all edges in the subAS minimized by
Algorithm 1
, and
S_{k}
(
G_{s}
) is the set of all kinds of
k
connected subgraphs of
G_{s}
. The maximum delay among all edges in the network is minimized by
Algorithm 1
can be described as
D
_{max}
(
G_{k}
)=min{
D
_{max}
(
G_{i}
)
G_{i}
∈
S_{k}
(
G_{s}
)}.
Let (
u_{m}
,
v_{m}
) be the last edge that is placed into
G_{k}
, i.e.,
w
(
u_{m}
,
v_{m}
)=max
_{(u,v)∈E(Gk)}
{
w
(
u
,
v
)}. Let
G'_{k}
=
G_{k}
(
u_{m}
,
v_{m}
), then we obtain that 
P
_{um,vm}
(
G'_{k}
)<
k
. Now, we assume that there is a graph
H_{s}
=(
V
(
H_{s}
),
E
(
H_{s}
)) , where
V
(
H_{s}
)=
V
(
G_{s}
) , and
E
(
H_{s}
)={(
u
,
v
)∈
E
(
G_{s}
)
w
(
u
,
v
)<
w
(
u_{m}
,
v_{m}
)}. If we can prove that
CON
(
H_{s}
,
k
) is not true, we will obtain that any
G_{i}
∈
S_{k}
(
G_{s}
) should have at least one edge equal to or heavier than (
u_{m}
,
v_{m}
). That is,
D
_{max}
(
G_{k}
)=min{
D
_{max}
(
G_{i}
)
G_{i}
∈
S_{k}
(
G_{s}
)}. We prove
CON
(
H_{s}
,
k
) is not true by contradiction in the following.
Assume that
CON
(
H_{s}
,
k
), hence, 
P
_{um,vm}
(
H_{s}
)≥
k
. We have
H_{s}

G'_{k}
≠φ. Since all edges are placed into
G'_{k}
the ascending order, ∀(
u
,
v
)∈
H_{s}

G'_{k}
should satisfy that
u
is
k
connected to
v
in
H_{s}
{(
u'
,
v'
)∈
E
(
H_{s}
)
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
G_{i}
=(
V_{i}
,
E_{i}
)
and
G_{j}
=(
V_{j}
,
E_{j}
)
be two subgraphs of graph G. If
NBR_{G}
(
G_{i}
,
G_{j}
,
k
)
, then
CON
(
G_{i}
∪
_{G}
G_{j}
,
k
).
Proof of Lemma 3:
In order to prove
CON
(
G_{i}
∪
_{G}
G_{j}
,
k
), we prove
G_{i}
∪
_{G}
G_{j}
is connected with the removal of any
k
1 vertices from it. Since
NBR_{G}
(
G_{i}
,
G_{j}
,
k
), we have
CON
(
G_{i}
,
k
) and
CON
(
G_{j}
,
k
), i.e., consider any
u
,
v
∈
G_{i}
or
u
,
v
∈
G_{j}
,
u
is
k
connected to
v
. Then we only need to consider the case (
u
∈
G_{i}
)∧(
v
∈
G_{j}
).
Since
NBR_{G}
(
G_{i}
,
G_{j}
,
k
), ∃
u
_{0}
∈
G_{i}
,
v
_{0}
∈
G_{j}
,
u
_{0}
is connected to
v
_{0}
with the removal of any
k
1 vertices from
V_{i}
∪
V_{j}
{
u
_{0}
,
v
_{0}
}. With
CON
(
G_{i}
,
k
) and
CON
(
G_{j}
,
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,
G_{i}
∪
_{G}
G_{j}
is connected with the removal of any
k
1 vertices from it.
Corollary 1.
Let subgraphs
G
_{1}
,
G
_{2}
,⋯,
G_{n}
be a partitioning of G. Let S_{m} be the maximal set of subgraphs subject to
∀
G_{i}
,
G_{j}
∈
S_{m}
,
∃
MCON_{G}
(
G_{i}
,
G_{j}
,
k
)
. Then,
∪
_{G}
{
G_{i}

G_{i}
S_{m}
}
is kconnected.
Lemma 4.
Let G_{s} be a subgraph of G, and let G'_{s} be edges reduction of G_{s}
.
Let G"
=(
V
,
E'
)=(
G

G_{s}
)∪
_{G}
G'_{s}
.
If CON
(
G_{s}
,
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
∈
V_{s}
: It is obvious true because of
CON
(
G'_{s}
,
k
)
2)
u
∈
V_{s}
and
v
∈
V

V_{s}
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

E_{s}
,
p
is also exist in
G"
,
u
is connected to
v
by removing those
k
1 vertices. Otherwise, ∃(
a
∈
p
)∧(
a
∈
V_{s}
) and
a
is connected to
v
in
G

G_{s}
. 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

V_{s}
: 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

E_{s}
,
u
is
k
connected to
v
in
G"
. Otherwise, ∃(
a
_{1}
,
a
_{2}
∈
p
)∧(
a
_{1}
,
a
_{2}
∈
V_{s}
),
u
is connected to
a
_{1}
and
a
_{2}
is connected to
v
in
G

G_{s}
. 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}
,⋯,
G_{n} be kconnected subgraphs of kconnected graph G. Let
G'
_{1}
,
G'
_{2}
,⋯,
G'_{n}
be edges reduction of
G
_{1}
,
G
_{2}
,⋯,
G_{n}
, and
G'
_{1}
,
G'
_{2}
,⋯,
G'_{n}
are kconnected. Then,
is kconnected.
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
G_{i}
=(
V_{i}
,
E_{i}
)
be the subAS networks resulting from Phase 1 in the topology control, where
i
=1,⋯,
n
. Let
G'_{i}
=(
V_{i}
,
E'_{i}
)
, where
E'_{i}
=
E_{i}
∩
E'
. Then,
∀
i
,
j subject to
1≤
i
≤
j
≤
n
, we have
MCON_{G}
(
G_{i}
,
G_{j}
,
k
)⇒
MCON_{G'}
(
G'_{i}
,
G'_{j}
,
k
).
Proof of Lemma 5:
Since nodes of any intrasubAS are
k
connected. We take subAS as a
node
here. Formally, we represent graph
G
as
, where
V_{s}
={
G
_{1}
,
G
_{2}
,⋯,
G_{n}
} and
E_{s}
={(
G_{i}
,
G_{j}
)
NBR_{G}
(
G_{i}
,
G_{j}
,
k
)}. Actually, edge (
G_{i}
,
G_{j}
) contains at least
k
disjoint paths between
G_{i}
and
G_{j}
. Let
be the subAS level representation of
G'
, where
E'_{s}
={(
G'_{i}
,
G'_{j}
)
NBR_{G'}
(
G'_{i}
,
G'_{j}
,
k
)}. We use
V_{s}
to represent the set of subAS networks in
, because we need not to consider the topology of intrasubAS (both
G_{i}
and
G'_{i}
are
k
connected). We take all of them as nodes, so we consider (
G_{i}
,
G_{j}
) and
G'_{i}
,
G'_{j}
as the same edge. Recall that in
Algorithm 2
, each edge (
G_{i}
,
G_{j}
)∈
E_{s}
has a weight
D_{IA}
(
G_{i}
,
G_{j}
).
In order to prove Lemma 5, it suffices to show that
is connected to
G_{j}
in
. We order all edges in
in the ascending sequence of weights, and then judge whether an edge should be place into
. Without loss of generality, let the ordering be (
e
_{1}
,
e
_{2}
,⋯,
e_{m}
), where
m
=
E_{s}
. Then we prove Lemma 5 by induction.
Base:
Obviously, the pair of subAS networks corresponding to edge
e
_{1}
should always be placed into
, i.e.,
e
_{1}
∈
E'_{s}
.
Induction:
∀
t
≤
m
, if for all
q
<
t
, the pair of subAS networks corresponding to
e_{q}
are connected in
(either directly or indirectly). And suppose
e_{t}
=(
G_{i}
,
G_{j}
). From
Algorithm 2
, the only reason why
e_{t}
∉
E'_{s}
(
G_{i}
is not directly connected to
G_{j}
in
) is that there exists another subAS
G_{i}
, where both
D_{IA}
(
G_{i}
,
G_{l}
) and
D_{IA}
(
G_{l}
,
G_{j}
) is less than
D_{IA}
(
G_{i}
,
G_{j}
). However, since edges (
G_{i}
,
G_{l}
) and (
G_{l}
,
G_{j}
) come before (
G_{i}
,
G_{j}
) in the ascending order. From path
,
G_{i}
is connected to
G_{j}
in
.
By induction, we prove that
G_{i}
is connected to
G_{j}
in
, and then
MCON_{G}
(
G_{i}
,
G_{j}
,
k
)⇒
MCON_{G'}
(
G'_{i}
,
G'_{j}
,
k
).
Finally, we prove the correctness of Theorem 2. In the proof,
G_{i}
and
G'_{i}
have the same definition in Lemma 5.
Proof of Theorem 1:
For every subAS
G_{i}
, we know that
CON
(
G_{i}
,
k
) is true after
Algorithm 1
. Then we partition those subAS networks into sets
A
_{1}
,⋯,
A_{s}
, where each set contains subAS networks are multihop
k
connected in
G
, i.e., ∀
r
=1,⋯,
s
, then, (
G_{i}
∈
A_{r}
)∧(
MCON_{G}
(
G_{i}
,
G_{j}
,
k
))⇒
G_{j}
∈
A_{r}
. Then we define sets
A'_{1}
,⋯,
A'_{s}
, where ∀
i
,
G_{i}
∈
A_{r}
)⇒
G'_{i}
∈
A'_{r}
. Applying Lemma 5 here, for every
∀1≤
i
≤
j
≤
m
, we have
Take
A'_{r}
as a subgraph of
G'
,
where
and
Since
A'_{r}
only contains multihop
k
connected subgraphs, applying Corollary 1 here, we have
A'_{r}
is
k
connected. Then, applying Corollary 2 here, we have
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 ASTC 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 subAS networks, and
N_{S}
be the average number of nodes per subAS, i.e.,
N_{S}
=
N
/
S
. Let
R_{B}
be the average probability of nodes that are border nodes in a subAS, where 0<
R_{B}
<1. Let
S_{N}
be the average number of neighboring subAS networks for each subAS, i.e., 0<
S_{N}
<
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 subAS. We partition each phase into major steps. Hence, from
Table 1
, the total number of control messages required in the AS is
S
((2+
λ
+
R_{B}
)
N_{S}
+2
S_{N}
+2). It can be simplified as (2+
λ
+
R_{B}
)
N
+2
S_{N}S
+2
S
, which is
O
(
N
)+
O
(
S_{N}S
) in the worst case.
Average message complexity in each phase of a subAS
Average message complexity in each phase of a subAS
6. Simulation Results and Discussions
In this section, we present several sets of simulation results to evaluate the effectiveness of the proposed ASTC 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 minmax 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 obstaclefree, 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 subAS 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 ASTC, centralized algorithm FGSS
_{k}
and distributed algorithm FGSS
_{k}
;
3) 1000 Monte Carlo simulations.
Relative to ASTC, recall that in
Phase
1 of subAS 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 subAS networks where the average number of nodes per subAS 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 ASTC 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 subAS networks, where the average number of nodes per subAS is 6.58.
3)
Fig. 5
(c) is the topology resulting from the intrasubAS topology control algorithm of
Phase
2, when
k
=2.
4)
Fig. 5
(d) shows the topology after applying intersubAS Topology control algorithm of
Phase
3, when
k
=2. The intersubAS links are represented by black color.
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 ASTC, 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 ASTC 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)), ASTC 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, ASTC 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.
Results from three topology control algorithms (ASTC, FGSS_{k} and FLSS_{k}) 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 ASTC, FGSS
_{2}
and FLSS
_{2}
are all higher than when
k
=1. That is expected because 2connected is a stronger property than 1connected. 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 subAS networks and one more additional disjoint path from each node to other nodes within all subAS networks. The maximum delay of ASTC 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 ASTC 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 ASTC 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 ASTC 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 ASTC falls in between FGSS
_{k}
and FLSS
_{k}
. This is expected because ASTC 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 ASTC is constrained among neighboring subAS networks, and the delay performance is better than distributed algorithm in the simulation result. Thus, the proposed ASTC algorithm is better than centralized algorithm and distributed algorithm for SIN.
Fig. 6
(d) shows the average node degree of the topologies derived under ASTC, 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 ASTC does not depend on the size or density of the network. What’s more, when with the same
k
, the average degree under ASTC falls in between FGSS
_{k}
and FLSS
_{k}
. This is because ASTC 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 ASTC, 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 ASTC algorithm is
O
(
N
)+
O
(
S_{N}S
). For each node, the average number of messages required is (
O
(
N
)+
O
(
S_{N}S
)/
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 ASTC does not increase. This shows the ASTC 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.
Number of messages exchanges per node derived under ASTC, FGSS_{k}, FGSS_{k} 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 subAS networks, and make the topology control of the SIN easier to carry out. Then we proposed the ASTC 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, ASTC utilizes a hybrid method. In this way, not only the control message exchange is constrained among local neighboring subAS networks, but also the strong connectivity of the network is preserved. Our simulation results validated the theoretic analysis and effectiveness of the ASTC 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 ASTC algorithm so as to improve its practicality in real applications. Furthermore, we will also consider the topology control of AS1 (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.
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 Meshbased 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/ietifs.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/IAC14/B2/3/23563/
1 
7
Guo B.Y.
,
Guan Q.S.
,
Yu F. R.
,
Jiang S.M.
,
Leung V. C. M.
2014
“EnergyEfficient Topology Control with Selective Diversity in Cooperative Wireless Ad Hoc Networks: A GameTheoretic 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 TimeEvolving and Predictable DelayTolerant 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.
,
AlFuqaha 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.
,
RosalesHain 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 AdHoc 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 FaultTolerant 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 Clusterbased Faulttolerant Topology Control for Space Information Networks,”
in Proc. of IEEE CyberEnabled 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