# Delay Minimization Topology Control in Planetary Surface Network: An Autonomous Systems Approach

Authors: Wei Zhang; Gengxin Zhang; Liang Gou; Bo Kong; Dongming Bian
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

This paper investigates the topology control problem in the planetary surface network (PSN) of Interplanetary Internet (IPN) using an autonomous system (AS) approach. We propose a delay minimization topology control (DMTC) algorithm to achieve low time delay and strong connectivity in the planetary surface network. Compared with the most existing approaches 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 AS networks. We prove that the proposed algorithm could achieve logicalk-connectivity on the condition that the original physical topology is k-connectivity. Simulation results validate the theoretic analysis and effectiveness of the DMTC algorithm.


---

## Body

## 1. Introduction

The Interplanetary Internet (IPN) was proposed to satisfy the demands of deep space communications early in this century. As proposed in [1, 2], the IPN includes a backbone network, external networks, and planetary networks (PNs). A PN is composed of an orbiter network (ON) and a planetary surface network (PSN). The former is composed of orbiters circling the planets and provides a relay service between the surface network and the backbone network [3, 4]. The latter is composed of landers, rovers, astronauts, and sensors from different countries or space missions [5, 6]. Nodes in the planetary surface network autonomously connect to each other in order to perform collaborative tasks. Unlike wireless sensor network (WSN) on the earth, the PSN has distinguishing characteristics [7]. The scale of the PSN is large. Communication abilities of nodes in the PSN are usually stronger. Nodes in the PSN have a wide and uneven distribution. Some links among them are short and some are extremely long. Excessive use of these long-distance links data not only brings additional delay but also reduces operation efficiency. What is more, long links usually mean more energy will be consumed. Consequently, how to make an efficient and reliable topology control is challenging.Existing works about network topology control mainly focus on maintaining a specified topology and 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, for example, [8–16]. 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 [17–19]. However, these algorithms are not suitable for large scale network such as PSN where excessive amounts of control messages need to be collected by one central entity. Control information in the PSN is costly for long distance and too many hops. On the other hand, in distributed algorithms, each node collects the information from its neighboring nodes and autonomously computes which link should be preserved [19–21]. Consider 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 PSN.Instead of using long links, nodes in the PSN should collaboratively determine which links will be used and define the network topology though forming proper neighbor relations. That is, topology control algorithms of the PSN actually remove unnecessary long links. As a result, the network topology is susceptible to unpredictable events such as hardware failures in such a harsh environment. Therefore, to design robust topology control algorithms,k-connectivity of the network is considered, where a k-connected network is k-1 fault-tolerant; that is, the failure of less than k-1 nodes will not disconnect the whole network.In this paper, we study the topology control problem in the PSN using an autonomous system (AS) approach. An AS network is a collection of nodes with similar properties, for example, nodes distributed in the same region. The reasons for using the AS approach are twofold. Firstly, the complex PSN is decoupled into a series of small AS networks, and centralized method can be used in each AS to ensure strong connectivity. Secondly, distributed method is used among AS networks; thus the topology control message exchange can be constrained among neighboring AS networks. We propose a delay minimization topology control (DMTC) algorithm using such a hybrid approach. DMTC preservesk-connectivity and ismin-max delay optimal. The min-max criterion tries to minimize the maximum end-to-end delay between any pair of nodes in the network [22]. Briefly, the DMTC algorithm consists of three phases: (i) nodes in the PSN autonomously form AS networks and elect AS cores; (ii) with the topology information gathered from the members of its AS network, each AS core minimizes the maximum link delay used by all the nodes and guarantees strong connectivity using a centralized method; (iii) each AS core selects a set of border nodes, shares topology information with neighboring AS cores, and computes low time delay links between neighboring AS networks using a distributed method. The main contributions of this paper are summarized as follows:(1)
An AS network model of PSN is proposed. The large scale and complex PSN is decoupled into small AS networks with similar nodes to achieve strong connectivity with low cost control messages.(2)
A delay minimization topology control (DMTC) algorithm is proposed to achieve low time delay. It is a hybrid algorithm within an AS network and among neighboring AS networks.(3)
The strong connectivity of DMTC algorithm proved that the algorithm could achieve logicalk-connectivity on the condition that the original physical topology is k-connectivity.The rest of this paper is organized as follows. In Section2, we define the network model and provide some definitions. In Section 3, we propose an AS based algorithm DMTC to achieve low time delay and strong connectivity. Then, the validity of DMTC 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, the PSN is a self-organizing system constituted by various nodes. For example, as demonstrated in Figure1, the Mars PSN is a part of the IPN. Nodes in the PSN have a wide and uneven distribution. They work in different areas with either mobile (e.g., rovers) or static (e.g., sensors) statuses. If we apply a unified strategy to manage the whole PSN, it will induce low efficiency and even cannot maintain the normal operation of the network with too much control information. So, as shown in Figure 2, we divide the PSN into a series of AS networks according to the property of the nodes. Each AS network can adopt independent topology control strategy to achieve strong connectivity. And the control message exchange is constrained among neighboring AS networks to reduce the cost of control.Figure 1
The PSN is a part of the IPN and is a self-organizing system constituted by various nodes.Figure 2
The whole PSN is divided into a series of AS networks according to the property of the nodes.Considering that the properties of nodes in the PSN are similar except few nodes, we assume that all the nodes are homogeneous. They have the same maximal transmission rangeRmax. Let the PSN network topology be represented by undirected simple graph G=V,E, where V=u1,u2,…,un is the set of nodes (or, equivalently, vertices) and E=ui,uj∣ui,uj∈V∧rui,uj≤Rmax is the set of links (edges). rui,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 thatG 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 by some means (e.g., celestial navigation [23], initial navigation [24], and vision navigation [25]). We then define several graphs related terms in the following, which will be used in both algorithms and proofs. For all definitions, we refer to graph G=V,E and subgraphs Gi=Vi,Ei and Gj=Vj,Ej.Definition 1 (weight function).
For edgee=u,v, the weight function is wu,v=du,v,minIDu,IDv,maxIDu,IDv, where du,v is the time delay between u and v when exchanging information. Given u1,v1,u2,v2∈E, the relationship between wu1,v1 and wu2,v2 is given as(1)wu1,v1>wu2,v2⟺du1,v1>du2,v2ordu1,v1=du2,v2∧minIDu1,IDv1>minIDu2,IDv2ordu1,v1=du2,v2∧minIDu1,IDv1=minIDu2,IDv2∧maxIDu1,IDv1>maxIDu2,IDv2.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 path p=ux1x2⋯xm-1xmv¯, where xi∈V and u,x1,xi,xj,xm,v∈E. And, for any u,v∈V, if there exist at least k disjoint paths between them. Graph G is k-connected and denoted by CONG,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 (neighboringk-connected subgraphs).
For two disjoint subgraphsGi and Gj of G, if ∃u∈Vi,v∈Vj, and ∃u,v∈E, Gi and Gj are neighboring subgraphs, denoted by NBRGGi,Gj. If CONGi,k∧CONGj,k and ∃u1,v1,…,uk,vk∈E, where u1,…,uk∈Vi and v1,…,vk∈Vj, Gi and Gj are neighboring k-connected subgraphs, denoted by NBRGGi,Gj,k.Definition 4 (multihopk-connected subgraphs).
LetG1,G2,…,Gn be partitioning of G. If ∃Gl subject to NBRGGi,Gl,k∧NBRGGl,Gj,k, Gi and Gj are multihop k-connected subgraphs, denoted by MCONGGi,Gj,k.


## 3. Algorithms for Topology Control

Recall from Introduction that the design aims of the DMTC algorithm are twofold,(1) to provide min-max delay optimal through an AS approach and (2) to achieve strong connectivity in the resulting network. The DMTC algorithm does not require the global topology of the PSN network to be known by any entity. On the contrary, DMTC relies on AS networks where nodes autonomously form groups and select a core for each AS network. It is a hybrid of centralized algorithm and distributed algorithm. A centralized topology control algorithm is applied to each AS network to achieve the desired connectivity within the AS, while the desired connectivity between adjacent AS networks is achieved via localized information sharing between adjacent AS cores. The following subsections detail the three phases of the DMTC algorithm.


### 3.1. Phase 1: AS Network Formation

The main function ofPhase 1 is to select a minimal number of nodes as cores that dominate the 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 broadcastshello messages periodically in order to let them discover each other in the surrounding area. A hello message is of the form NodeID,Location,CoreID,Degree,Delay. The explanation of each field is as follows: (1)NodeID: 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 with 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 exchanging 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 to 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 an AS or become a member of an AS by checking for its local optimality. Each node computes its ownheight from its current states. The height metric should be chosen to suit the design goals of the PSN topology control algorithm. As a result, we use Delay,Degree,NodeID as the height metric. NodeID is included in the metric calculation to break ties. The height function is heightu=hu,IDu. In order to balance the factor of Delay and Degree, we formulate hu as(2)hu=fDegreeu,Delayu,vi,α,where f· denotes the balance function and α is the balance factor. The relationship between hightu and hightv is given by(3)hightu>hightv⟺hu>hvorhu=hv∧NodeIDu>NodeIDv.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.Step 3 (supplement of cores).
After Step2, each node checks if there are cores in the range Rmax. If cores exist, it will regard the core that has the least Delay between them as its parent. That is, this node will be the member of the 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. After that, nodes whose CoreID are zero without parent calculate their height functions. And the node that has the highest height among its neighbors without parent in the range Rmax should serve as a core.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 rangeRmax (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 PSN, 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 PSN. For instance, if a new node is added to the PSN, the process will take this node as a node without parent and turn to Step 3.


### 3.2. Phase 2: Intra-AS Topology Control

In this phase, we present a centralized algorithm for intra-AS network. Each core will calculate the links for all of the members of its AS such that the resulting topology of the AS meets the given topology constraint (min-max delay andk-connectivity). The intra-AS topology control algorithm is described in Algorithm 1, where G represents the PSN, and let G1,G2,…,Gn (AS) be partitioning of G.Algorithm 1:Intra-AS topology control.
Input: (at AS Gs=(Vs,Es))
k (required connectivity)
Output:
Gk=(Vk,Ek)
Begin:
Vk←Vs, Ek←∅
Sort all edges inEs in ascending order of weight (as defined in Definition 1)
for all edge (ui,vi) in the order do
if  ui is not k-connected to vi  then
Ek←Ek∪(ui,vi)
end if
end for
for all edge (uj,vj) of Ek in the descending order do
if  uj is still k-connected to vj with the disconnection of edge (uj,vj)  then
Ek←Ek-(uj,vj)
end if
end for
Return  GkFor each AS, Algorithm1 ensures that Gk preserve the k-connectivity of Gs; that is, CONGs,k⇒CONGk,k. And the maximum end-to-end delay among all edges in the AS network is minimized by Algorithm 1; that is, let DmaxGk be the maximum delay of all edges in the AS minimized by Algorithm 1, and let SkGs be the set of all kinds of k-connected subgraphs of Gs with the same vertices Vs; then we have DmaxGk=minDmaxGi∣Gi∈SkGs. The correctness of Algorithm 1 is provided in Section 4.


### 3.3. Phase 3: Inter-AS Topology Control

In this phase, connectivity between adjacent AS networks is considered. In order to allow adjacent AS networks to discover each other, every node continues broadcastinghello message NodeID,Location,CoreID,Degree,Delay as inPhase 1 periodically. When node u receives a hello message from node v that belongs to a different 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-AS. This algorithm is described in Algorithm 2, where G represents the PSN, and let G1,G2,…,Gn (AS) be partitioning of G.Algorithm 2:Inter-AS topology control.
Input: (at AS Gk=(Vk,Ek))
k (required connectivity)
Output:
Links for all nodes inGk's border list.
Begin:
Gki=(Vki,Eki), Vki←Vk, Eki←∅
for  all Gi subject to NBRG(Gk,Gi)  do
V′←{v∣(v∈Gi)∧(visadjacenttoGk)}
Vki←Vki∪V′
Eki←{(u,v)∣(u∈Vk)∧(v∈V′)∧(r(u,v)≤Rmax)}
M←∅
Ea ← sort all edges in Eki in ascending order of weight (as defined in Definition 1)
km←MaxMatching(Gki)
%MaxMatching(Gki) is the number of edges in MaxMatching(Gki)
if  km≥k  then
for  all edges et=(ut,vt)∈Ea in the order  do
Find the smallestt, subject to M≥k, where M←MaxMatching(Gt=(Vki,Ea(t))), and M is the number of
edges inM, Eat={e1,…,et}
end for
DIA(Gk,Gi)←et, where et is the weight of et
L(Gk,Gi)←M
else
for  all edges et=(ut,vt)∈Ea in the order  do
Find the smallestt, subject to M≥k2, and M←MaxMatching(Gt=(Vki,Ea(t)))
end for
DIA(Gk,Gi)←∞
L(Gk,Gi)←M
end if
SendDIA(Gk,Gi) to neighbor AS
end for
CollectDIA from neighboring AS
LIST←∅
for  all Gp subject to NBRG(Gk,Gp)  do
if  there does not exist Gq subject to
NBRG(Gk,Gq)∧NBRG(Gk,Gp)∧
(DIA(Gk,Gq)<DIA(Gk,Gp))∧  then
(DIA(Gp,Gq)<DIA(Gk,Gp))
LIST←LIST∪L(Gk,Gi)
end if
end for
Return  LISTIn this algorithm, the core of ASA checks whether there exist k disjoint links from this AS to each adjacent AS B. That is accomplished by applying an algorithm (MaxMatching) [26] that computes a matching of maximum cardinality in abipartite graph defined by the nodes in respective AS networks and the edges with one vertex in each AS. If k does not exceed the size of maximum cardinality matching, the core of AS A selects k disjoint links that meet the min-max delay optimal. When there do not exist k disjoint links between A and B (only km disjoint links), the core preserves the km-connectivity between these two AS networks and minimizes the maximum delay between them. Note that this connectivity preservation (km-connectivity) cannot guarantee k-connectivity between AS A and B. However, global k-connectivity can be guaranteed afterPhase 3 is completed when connectivity with other neighboring AS networks is already established. This will be proved in Section 4.ParameterDIAG1,G2 in Algorithm 2 is used to perform an optimization which removes unnecessary links between certain adjacent AS networks, while preserving the connectivity of the resulting topology. DIAG1,G2 is the maximum delay of the selected k links. However, when the number km of disjoint links between two adjacent AS networks is less than k, DIAG1,G2 is ∞. Then, AS A will not connect to neighboring AS B directly if it observes that there exists another AS C, where C is also a neighbor of B, and both DIAGA,GC and DIAGB,GC are less than DIAGA,GB.AfterPhase 3 is completed, each node is assigned a link list, and nodes connect to each other according to these lists. This topology will be maintained by every node withhello message periodically and always preserve the objective connectivity of the network.


## 3.1. Phase 1: AS Network Formation

The main function ofPhase 1 is to select a minimal number of nodes as cores that dominate the 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 broadcastshello messages periodically in order to let them discover each other in the surrounding area. A hello message is of the form NodeID,Location,CoreID,Degree,Delay. The explanation of each field is as follows: (1)NodeID: 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 with 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 exchanging 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 to 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 an AS or become a member of an AS by checking for its local optimality. Each node computes its ownheight from its current states. The height metric should be chosen to suit the design goals of the PSN topology control algorithm. As a result, we use Delay,Degree,NodeID as the height metric. NodeID is included in the metric calculation to break ties. The height function is heightu=hu,IDu. In order to balance the factor of Delay and Degree, we formulate hu as(2)hu=fDegreeu,Delayu,vi,α,where f· denotes the balance function and α is the balance factor. The relationship between hightu and hightv is given by(3)hightu>hightv⟺hu>hvorhu=hv∧NodeIDu>NodeIDv.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.Step 3 (supplement of cores).
After Step2, each node checks if there are cores in the range Rmax. If cores exist, it will regard the core that has the least Delay between them as its parent. That is, this node will be the member of the 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. After that, nodes whose CoreID are zero without parent calculate their height functions. And the node that has the highest height among its neighbors without parent in the range Rmax should serve as a core.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 rangeRmax (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 PSN, 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 PSN. For instance, if a new node is added to the PSN, the process will take this node as a node without parent and turn to Step 3.


## 3.2. Phase 2: Intra-AS Topology Control

In this phase, we present a centralized algorithm for intra-AS network. Each core will calculate the links for all of the members of its AS such that the resulting topology of the AS meets the given topology constraint (min-max delay andk-connectivity). The intra-AS topology control algorithm is described in Algorithm 1, where G represents the PSN, and let G1,G2,…,Gn (AS) be partitioning of G.Algorithm 1:Intra-AS topology control.
Input: (at AS Gs=(Vs,Es))
k (required connectivity)
Output:
Gk=(Vk,Ek)
Begin:
Vk←Vs, Ek←∅
Sort all edges inEs in ascending order of weight (as defined in Definition 1)
for all edge (ui,vi) in the order do
if  ui is not k-connected to vi  then
Ek←Ek∪(ui,vi)
end if
end for
for all edge (uj,vj) of Ek in the descending order do
if  uj is still k-connected to vj with the disconnection of edge (uj,vj)  then
Ek←Ek-(uj,vj)
end if
end for
Return  GkFor each AS, Algorithm1 ensures that Gk preserve the k-connectivity of Gs; that is, CONGs,k⇒CONGk,k. And the maximum end-to-end delay among all edges in the AS network is minimized by Algorithm 1; that is, let DmaxGk be the maximum delay of all edges in the AS minimized by Algorithm 1, and let SkGs be the set of all kinds of k-connected subgraphs of Gs with the same vertices Vs; then we have DmaxGk=minDmaxGi∣Gi∈SkGs. The correctness of Algorithm 1 is provided in Section 4.


## 3.3. Phase 3: Inter-AS Topology Control

In this phase, connectivity between adjacent AS networks is considered. In order to allow adjacent AS networks to discover each other, every node continues broadcastinghello message NodeID,Location,CoreID,Degree,Delay as inPhase 1 periodically. When node u receives a hello message from node v that belongs to a different 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-AS. This algorithm is described in Algorithm 2, where G represents the PSN, and let G1,G2,…,Gn (AS) be partitioning of G.Algorithm 2:Inter-AS topology control.
Input: (at AS Gk=(Vk,Ek))
k (required connectivity)
Output:
Links for all nodes inGk's border list.
Begin:
Gki=(Vki,Eki), Vki←Vk, Eki←∅
for  all Gi subject to NBRG(Gk,Gi)  do
V′←{v∣(v∈Gi)∧(visadjacenttoGk)}
Vki←Vki∪V′
Eki←{(u,v)∣(u∈Vk)∧(v∈V′)∧(r(u,v)≤Rmax)}
M←∅
Ea ← sort all edges in Eki in ascending order of weight (as defined in Definition 1)
km←MaxMatching(Gki)
%MaxMatching(Gki) is the number of edges in MaxMatching(Gki)
if  km≥k  then
for  all edges et=(ut,vt)∈Ea in the order  do
Find the smallestt, subject to M≥k, where M←MaxMatching(Gt=(Vki,Ea(t))), and M is the number of
edges inM, Eat={e1,…,et}
end for
DIA(Gk,Gi)←et, where et is the weight of et
L(Gk,Gi)←M
else
for  all edges et=(ut,vt)∈Ea in the order  do
Find the smallestt, subject to M≥k2, and M←MaxMatching(Gt=(Vki,Ea(t)))
end for
DIA(Gk,Gi)←∞
L(Gk,Gi)←M
end if
SendDIA(Gk,Gi) to neighbor AS
end for
CollectDIA from neighboring AS
LIST←∅
for  all Gp subject to NBRG(Gk,Gp)  do
if  there does not exist Gq subject to
NBRG(Gk,Gq)∧NBRG(Gk,Gp)∧
(DIA(Gk,Gq)<DIA(Gk,Gp))∧  then
(DIA(Gp,Gq)<DIA(Gk,Gp))
LIST←LIST∪L(Gk,Gi)
end if
end for
Return  LISTIn this algorithm, the core of ASA checks whether there exist k disjoint links from this AS to each adjacent AS B. That is accomplished by applying an algorithm (MaxMatching) [26] that computes a matching of maximum cardinality in abipartite graph defined by the nodes in respective AS networks and the edges with one vertex in each AS. If k does not exceed the size of maximum cardinality matching, the core of AS A selects k disjoint links that meet the min-max delay optimal. When there do not exist k disjoint links between A and B (only km disjoint links), the core preserves the km-connectivity between these two AS networks and minimizes the maximum delay between them. Note that this connectivity preservation (km-connectivity) cannot guarantee k-connectivity between AS A and B. However, global k-connectivity can be guaranteed afterPhase 3 is completed when connectivity with other neighboring AS networks is already established. This will be proved in Section 4.ParameterDIAG1,G2 in Algorithm 2 is used to perform an optimization which removes unnecessary links between certain adjacent AS networks, while preserving the connectivity of the resulting topology. DIAG1,G2 is the maximum delay of the selected k links. However, when the number km of disjoint links between two adjacent AS networks is less than k, DIAG1,G2 is ∞. Then, AS A will not connect to neighboring AS B directly if it observes that there exists another AS C, where C is also a neighbor of B, and both DIAGA,GC and DIAGB,GC are less than DIAGA,GB.AfterPhase 3 is completed, each node is assigned a link list, and nodes connect to each other according to these lists. This topology will be maintained by every node withhello message periodically and always preserve the objective connectivity of the network.


## 4. Proof of Strong Connectivity

In this section, we prove the strong connectivity of Algorithms1 and 2 [27]. The results are given as the following theorems.


### 4.1. Strong Connectivity of Algorithm1

Theorem 5.
Algorithm1 can preserve k-connectivity of AS Gs; that is, CONGs,k⇒CONGk,k. And the maximum delay among all nodes in the network is minimized by Algorithm 1.Before proving the correctness of Theorem5, two lemmas are first provided. Let p=ux1x2⋯xm-1xmv¯ 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 in graph Gs be represented by Pu,vGs; that is, ∀pm,pn∈Pu,vGs, pm∩pn=u,v. If edge e0=u,v, let Gs-e0 be the resulting graph by removing the edge e0 from Gs.Lemma 6.
Letu and v be two vertices in the k-connected graph Gs; if u and v are still k-connected after the removal of edge e0=u,v, then CONGs-e0,k.Proof of Lemma6.
In order to proveCONGs-e0,k, we prove that Gs′=Gs-e0 is connected with the removal of any k-1 vertices from Gs′. We already know that u and v are k-connected in Gs′. Thus, considering any two vertices u1,v1, we assume that u1,v1∩u,v=∅. We only need to prove that u1 is still connected to v1 after the removal of set k-1 vertices X=x1,…,xk-1, where xi∈VGs′-u1,v1. If u1,v1 is an edge in Gs′, that is obviously true. Hence, we only consider the case that there is no direct edge from u1 to v1.
SinceCONGs,k, we have Pu1,v1Gs≥k, where Pu1,v1Gs is the number of paths in the set Pu1,v1Gs. Let r1 be the number of paths in Pu1,v1Gs′ that are broken after the removal of vertices in the set of X; that is, r1=p∈Pu1,v1Gs′∣xi∈X∧xi∈p. We know that paths in Pu1,v1Gs′ are disjoint, so the removal of any one vertex in X can only break at most one path in Pu1,v1Gs′. Given X=k-1, we have r1≤k-1.
LetGs′′ be the resulting graph by removing X from Gs′. If Pu1,v1Gs′≥k, we have Pu1,v1Gs′′≥Pu1,v1Gs′-r1≥1; that is, u1 is still connected to v1 in Gs′′. Otherwise, Pu1,v1Gs′<k; it occurs only if the removal of edge e0=u,v breaks one path pj∈Pu1,v1Gs. Without loss of generality, let the order of vertices in the path pj be u1,…,u,v,…,v1¯. Since the paths in Pu1,v1Gs are disjoint, the removal of edge e0 breaks at most one path; that is, Pu1,v1Gs-pj≥k-1. So we have Pu1,v1Gs′=k-1.
Ifr1<k-1, it is obvious that Pu1,v1Gs′-r1≥1. Hence Pu1,v1Gs′′≥1. That is, u1 is still connected to v1 in Gs′′. Otherwise, if r1=k-1, every vertex in the set X belongs to the paths in Pu1,v1Gs′. We know that pj∈Pu1,v1Gs is disjoint with the paths in Pu1,v1Gs′, so we have pj∩X=∅. Hence, no vertex in u1,…,u,v,…,v1¯ is removed with the removal of X. So, with the removal of e0, u1 is still connected to u, and v is still connected to v1 in Gs′′. With the assumption that u and v are still k-connected after the removal of edge e0=u,v in Lemma 6. it is obvious that u is still connected to v in Gs′′. So u1 is still connected to v1 in Gs′′.
We have proved that, for any two verticesu1,v1∈Gs′, u1 is connected to v1 with the removal of any k-1 vertices from VGs′-u1,v1. Hence, CONGs′,k.Lemma 7.
LetGs and G^s be two graphs, where CONGs,k and VGs=VG^s. If every edge subject to u,v∈EGs-EG^s satisfies that u is still k-connected to v in graph Gs-u′,v′∈EGs∣wu′,v′≥wu,v, then CONG^s,k.Proof of Lemma7.
Without loss of generality, lete1,e2,…,em=EGs-EG^s=u1,v1,u2,v2,…,um,vm be a set of edges subject to we1>we2>⋯>wem. We define a series of subgraphs of Gs: Gs0=Gs, and Gsi=Gsi-1-ei, where i=1,2,…,m. Then EGsm⊆EG^s. Here we prove Lemma 7 by induction.
Base. Obviously, we have Gs0=Gs and CONGs0,k.
Induction. If CONGsi-1,k, we prove that CONGsi,k, where i=1,2,…,m. Since Gs-u′,v′∈EGs∣wu′,v′≥wui,vi⊆Gsi-1-ui,vi, and from the assumption of Lemma 7 (ui is k-connected to vi in graph Gs-u′,v′∈EGs∣wu′,v′≥wui,vi), we obtain that ui is k-connected to vi in graph Gsi-1-ui,vi. Applying Lemma 6 to Gsi-1, it is obvious that CONGsi-1-ui,vi,k. That is, CONGsi,k.
By induction, we haveCONGsm,k. Since EGsm⊆EG^s, hence CONG^s,k.Finally, we prove the correctness of Theorem5 as follows.Proof of Theorem5.
In Algorithm1, we place all edges into Gk in the ascending order. Whether u,v should be placed into Gk depends on the connection of u and v and edges of smaller weights. That is, every edge u,v∈EGs-EGk should satisfy that u is k-connected to v in Gs-u′,v′∈EGs∣wu′,v′≥wu,v. Applying Lemma 7 here, then we can prove that CONGs,k⇒CONGk,k.
Recall thatDmaxGk is the maximum delay of all edges in the AS minimized by Algorithm 1, and SkGs is the set of all kinds of k-connected subgraphs of Gs with the same vertices Vs. The maximum delay among all edges in the network is minimized by Algorithm 1 which can be described as DmaxGk=minDmaxGi∣Gi∈SkGs.
Letum,vm be the last edge that is placed into Gk. It is obvious that um,vm cannot be removed from EGk in the process of Algorithm 1; that is, wum,vm=maxu,v∈EGkwu,v. Let Gk′=Gk-um,vm; then we obtain that Pum,vmGk′<k. Now, we assume that there is graph Hs=VHs,EHs, where VHs=VGs and EHs=u,v∈EGs∣wu,v<wum,vm. If we can prove that CONHs,k is not true, we will obtain that any Gi∈SkGs should have at least one edge equal to or heavier than um,vm. That is, DmaxGk=minDmaxGi∣Gi∈SkGs. We prove that CONHs,k is not true by contradiction in the following.
Assume thatCONHs,k; hence, Pum,vmHs≥k. We have Hs-Gk′≠∅. Since all edges are placed into Gk′ in the ascending order, ∀u,v∈Hs-Gk′ should satisfy that u is k-connected to v in Hs-u′,v′∈EHs∣wu′,v′≥wu,v. Applying Lemma 7 here, we obtain that CONGk′,k. That is, Pum,vmGk′≥k, which is a contradiction.


### 4.2. Strong Connectivity of Algorithm2

Theorem 8.
LetG=V,E be the initial topology of the PSN. Let G′=V,E′ be the topology after Algorithm 2 is completed. Then we have CONG,k⇔CONG′,k.Before proving the correctness of Theorem8, several lemmas used in that proof are first provided.Lemma 9.
LetGi=Vi,Ei and Gj=Vj,Ej be two subgraphs of graph G. If NBRGGi,Gj,k, then CONGi∪GGj,k.Proof of Lemma9.
In order to proveCONGi∪GGj,k, we prove Gi∪GGj is connected with the removal of any k-1 vertices from it. Since NBRGGi,Gj,k, we have CONGi,k and CONGj,k; that is, 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.
SinceNBRGGi,Gj,k,∃u0∈Gi,v0∈Gj, u0 is connected to v0 with the removal of any k-1 vertices from Vi∪Vj-u0,v0. With CONGi,k and CONGj,k, we know that u is connected to u0, and v is connected to v0. Hence u is connected to v. That is, Gi∪GGj is connected with the removal of any k-1 vertices from it.Corollary 10.
Let subgraphsG1,G2,…,Gn be partitioning of G. Let Sm be the maximal set of subgraphs subject to the following: ∀Gi,Gj∈Sm, ∃MCONGGi,Gj,k. Then, ∪GGi∣Gi∈Sm is k-connected.Lemma 11.
LetGs be a subgraph of G, and let Gs′ be edges reduction of Gs. Let G′′=V,E′=G-Gs∪GGs′. If CONGs,k∧CONGs′,k∧CONG,k, then CONG′′,k.Proof of Lemma11.
In order to proveCONG′′,k, we prove that, ∀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 obviously true because of CONGs′,k.(2)
u∈Vs and v∈V-Vs: since CONG,k,u is connected to v in path p with the removal of any k-1 vertices in G. If p⊆E-Es, p also exists 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 CONGs′,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 CONG,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, ∃a1,a2∈p∧a1,a2∈Vs, u is connected to a1, and a2 is connected to v in G-Gs. Since CONGs′,k,a1 is connected to a2 by removing those k-1 vertices. Then u is connected to v with the removal of any k-1 vertices in G′′.Corollary 12.
LetG1,G2,…,Gn be k-connected subgraphs of k-connected graph G. Let G1′,G2′,…,Gn′ be edges reduction of G1,G2,…,Gn, and G1′,G2′,…,Gn′ are k-connected. Then,(4)G′′=G-⋃i=1nGiG∪G⋃i=1nGi′G is k-connected.Lemma 13.
LetG=V,E be the initial topology of the PSN. Let G′=V,E′ be the topology after Algorithm 2 is completed. Let Gi=Vi,Ei be the AS networks resulting from Phase 1 in the topology control, where i=1,…,n and Ei=u,v∈E∣u,v∈Vi. Let Gi′=Vi,Ei′, where Ei′=Ei∩E′. Then, ∀i,j subject to 1≤i≤j≤n, we have that MCONGGi,Gj,k⇒MCONG′Gi′,Gj′,k.Proof of Lemma13.
Since nodes of any intra-AS arek-connected, we take an AS as anode here. Formally, we represent graph G as G¯=VS,ES, where VS=G1,G2,…,Gn and ES=Gi,Gj∣NBRGGi,Gj,k. Actually, edge Gi,Gj contains at least k disjoint paths between Gi and Gj. Let G¯′=VS,ES′ be the AS level representation of G′, where ES′=Gi′,Gj′∣NBRG′Gi′,Gj′,k. We use VS to represent the set of AS networks in G¯′, because we do not need to consider the topology of intra-AS (both Gi and Gi′ are k-connected). We take all of them as nodes, so we consider Gi,Gj and Gi′,Gj′ as the same edge. Recall that, in Algorithm 2, each edge Gi,Gj∈ES has weight DIAGi,Gj.
In order to prove Lemma13, it suffices to show that, ∀Gi,Gj∈G¯, Gi is connected to Gj in G¯′. We order all edges in G¯ in the ascending sequence of weights and then judge whether an edge should be placed into G¯′. Without loss of generality, let the ordering be e1,e2,…,em, where m=ES. Then we prove Lemma 13 by induction.
Base. Obviously, the pair of AS networks corresponding to edge e1 should always be placed into G¯′; that is, e1∈ES′.
Induction. ∀t≤m, if for all q<t, the pair of AS networks corresponding to eq are connected in G¯′ (either directly or indirectly). And suppose et=Gi,Gj. From Algorithm 2, the only reason why et∉ES′ (Gi is not directly connected to Gj in G¯′) is that there exists another AS  Gl, where both DIAGi,Gl and DIAGl,Gj are less than DIAGi,Gj. However, edges Gi,Gl and Gl,Gj come before Gi,Gj in the ascending order. From path GiGlGj¯, Gi is connected to Gj in G¯′.
By induction, we prove thatGi is connected to Gj in G¯′, and then MCONGGi,Gj,k⇒MCONG′Gi′,Gj′,k.Finally, we prove the correctness of Theorem8. In the proof, Gi and Gi′ have the same definition in Lemma 13.Proof of Theorem8.
For every ASGi, we know that CONGi,k is true after Algorithm 1. Then we partition those AS networks into sets A1,…,As, where each set contains AS networks which are multihop k-connected in G; that is, ∀r=1,…,s, then Gi∈Ar∧MCONGGi,Gj,k⇒Gj∈Ar. Then we define sets A1′,…,As′, where, ∀i,Gi∈Ar⇒Gi′∈Ar′. Applying Lemma 13 here, for every Ar′=Gr1′,…,Grm′, ∀1≤i<j≤m, we have MCONG′Gri′,Grj′,k. Take Ar′ as a subgraph of G′; Ar′=VAr′,EAr′, where VAr′=v∣v∈Ar′ and EAr′=u,v∣u,v∈Ar′∧u,v∈E′. Since Ar′ only contains multihop k-connected subgraphs, applying Corollary 10 here, we have that Ar′ is k-connected. Then, applying Corollary 12 here, we have that(5)G′=G-⋃r=1sArG∪G⋃r=1sAr′G is k-connected. ThenCONG,k⇔CONG′,k.


## 4.1. Strong Connectivity of Algorithm1

Theorem 5.
Algorithm1 can preserve k-connectivity of AS Gs; that is, CONGs,k⇒CONGk,k. And the maximum delay among all nodes in the network is minimized by Algorithm 1.Before proving the correctness of Theorem5, two lemmas are first provided. Let p=ux1x2⋯xm-1xmv¯ 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 in graph Gs be represented by Pu,vGs; that is, ∀pm,pn∈Pu,vGs, pm∩pn=u,v. If edge e0=u,v, let Gs-e0 be the resulting graph by removing the edge e0 from Gs.Lemma 6.
Letu and v be two vertices in the k-connected graph Gs; if u and v are still k-connected after the removal of edge e0=u,v, then CONGs-e0,k.Proof of Lemma6.
In order to proveCONGs-e0,k, we prove that Gs′=Gs-e0 is connected with the removal of any k-1 vertices from Gs′. We already know that u and v are k-connected in Gs′. Thus, considering any two vertices u1,v1, we assume that u1,v1∩u,v=∅. We only need to prove that u1 is still connected to v1 after the removal of set k-1 vertices X=x1,…,xk-1, where xi∈VGs′-u1,v1. If u1,v1 is an edge in Gs′, that is obviously true. Hence, we only consider the case that there is no direct edge from u1 to v1.
SinceCONGs,k, we have Pu1,v1Gs≥k, where Pu1,v1Gs is the number of paths in the set Pu1,v1Gs. Let r1 be the number of paths in Pu1,v1Gs′ that are broken after the removal of vertices in the set of X; that is, r1=p∈Pu1,v1Gs′∣xi∈X∧xi∈p. We know that paths in Pu1,v1Gs′ are disjoint, so the removal of any one vertex in X can only break at most one path in Pu1,v1Gs′. Given X=k-1, we have r1≤k-1.
LetGs′′ be the resulting graph by removing X from Gs′. If Pu1,v1Gs′≥k, we have Pu1,v1Gs′′≥Pu1,v1Gs′-r1≥1; that is, u1 is still connected to v1 in Gs′′. Otherwise, Pu1,v1Gs′<k; it occurs only if the removal of edge e0=u,v breaks one path pj∈Pu1,v1Gs. Without loss of generality, let the order of vertices in the path pj be u1,…,u,v,…,v1¯. Since the paths in Pu1,v1Gs are disjoint, the removal of edge e0 breaks at most one path; that is, Pu1,v1Gs-pj≥k-1. So we have Pu1,v1Gs′=k-1.
Ifr1<k-1, it is obvious that Pu1,v1Gs′-r1≥1. Hence Pu1,v1Gs′′≥1. That is, u1 is still connected to v1 in Gs′′. Otherwise, if r1=k-1, every vertex in the set X belongs to the paths in Pu1,v1Gs′. We know that pj∈Pu1,v1Gs is disjoint with the paths in Pu1,v1Gs′, so we have pj∩X=∅. Hence, no vertex in u1,…,u,v,…,v1¯ is removed with the removal of X. So, with the removal of e0, u1 is still connected to u, and v is still connected to v1 in Gs′′. With the assumption that u and v are still k-connected after the removal of edge e0=u,v in Lemma 6. it is obvious that u is still connected to v in Gs′′. So u1 is still connected to v1 in Gs′′.
We have proved that, for any two verticesu1,v1∈Gs′, u1 is connected to v1 with the removal of any k-1 vertices from VGs′-u1,v1. Hence, CONGs′,k.Lemma 7.
LetGs and G^s be two graphs, where CONGs,k and VGs=VG^s. If every edge subject to u,v∈EGs-EG^s satisfies that u is still k-connected to v in graph Gs-u′,v′∈EGs∣wu′,v′≥wu,v, then CONG^s,k.Proof of Lemma7.
Without loss of generality, lete1,e2,…,em=EGs-EG^s=u1,v1,u2,v2,…,um,vm be a set of edges subject to we1>we2>⋯>wem. We define a series of subgraphs of Gs: Gs0=Gs, and Gsi=Gsi-1-ei, where i=1,2,…,m. Then EGsm⊆EG^s. Here we prove Lemma 7 by induction.
Base. Obviously, we have Gs0=Gs and CONGs0,k.
Induction. If CONGsi-1,k, we prove that CONGsi,k, where i=1,2,…,m. Since Gs-u′,v′∈EGs∣wu′,v′≥wui,vi⊆Gsi-1-ui,vi, and from the assumption of Lemma 7 (ui is k-connected to vi in graph Gs-u′,v′∈EGs∣wu′,v′≥wui,vi), we obtain that ui is k-connected to vi in graph Gsi-1-ui,vi. Applying Lemma 6 to Gsi-1, it is obvious that CONGsi-1-ui,vi,k. That is, CONGsi,k.
By induction, we haveCONGsm,k. Since EGsm⊆EG^s, hence CONG^s,k.Finally, we prove the correctness of Theorem5 as follows.Proof of Theorem5.
In Algorithm1, we place all edges into Gk in the ascending order. Whether u,v should be placed into Gk depends on the connection of u and v and edges of smaller weights. That is, every edge u,v∈EGs-EGk should satisfy that u is k-connected to v in Gs-u′,v′∈EGs∣wu′,v′≥wu,v. Applying Lemma 7 here, then we can prove that CONGs,k⇒CONGk,k.
Recall thatDmaxGk is the maximum delay of all edges in the AS minimized by Algorithm 1, and SkGs is the set of all kinds of k-connected subgraphs of Gs with the same vertices Vs. The maximum delay among all edges in the network is minimized by Algorithm 1 which can be described as DmaxGk=minDmaxGi∣Gi∈SkGs.
Letum,vm be the last edge that is placed into Gk. It is obvious that um,vm cannot be removed from EGk in the process of Algorithm 1; that is, wum,vm=maxu,v∈EGkwu,v. Let Gk′=Gk-um,vm; then we obtain that Pum,vmGk′<k. Now, we assume that there is graph Hs=VHs,EHs, where VHs=VGs and EHs=u,v∈EGs∣wu,v<wum,vm. If we can prove that CONHs,k is not true, we will obtain that any Gi∈SkGs should have at least one edge equal to or heavier than um,vm. That is, DmaxGk=minDmaxGi∣Gi∈SkGs. We prove that CONHs,k is not true by contradiction in the following.
Assume thatCONHs,k; hence, Pum,vmHs≥k. We have Hs-Gk′≠∅. Since all edges are placed into Gk′ in the ascending order, ∀u,v∈Hs-Gk′ should satisfy that u is k-connected to v in Hs-u′,v′∈EHs∣wu′,v′≥wu,v. Applying Lemma 7 here, we obtain that CONGk′,k. That is, Pum,vmGk′≥k, which is a contradiction.


## 4.2. Strong Connectivity of Algorithm2

Theorem 8.
LetG=V,E be the initial topology of the PSN. Let G′=V,E′ be the topology after Algorithm 2 is completed. Then we have CONG,k⇔CONG′,k.Before proving the correctness of Theorem8, several lemmas used in that proof are first provided.Lemma 9.
LetGi=Vi,Ei and Gj=Vj,Ej be two subgraphs of graph G. If NBRGGi,Gj,k, then CONGi∪GGj,k.Proof of Lemma9.
In order to proveCONGi∪GGj,k, we prove Gi∪GGj is connected with the removal of any k-1 vertices from it. Since NBRGGi,Gj,k, we have CONGi,k and CONGj,k; that is, 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.
SinceNBRGGi,Gj,k,∃u0∈Gi,v0∈Gj, u0 is connected to v0 with the removal of any k-1 vertices from Vi∪Vj-u0,v0. With CONGi,k and CONGj,k, we know that u is connected to u0, and v is connected to v0. Hence u is connected to v. That is, Gi∪GGj is connected with the removal of any k-1 vertices from it.Corollary 10.
Let subgraphsG1,G2,…,Gn be partitioning of G. Let Sm be the maximal set of subgraphs subject to the following: ∀Gi,Gj∈Sm, ∃MCONGGi,Gj,k. Then, ∪GGi∣Gi∈Sm is k-connected.Lemma 11.
LetGs be a subgraph of G, and let Gs′ be edges reduction of Gs. Let G′′=V,E′=G-Gs∪GGs′. If CONGs,k∧CONGs′,k∧CONG,k, then CONG′′,k.Proof of Lemma11.
In order to proveCONG′′,k, we prove that, ∀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 obviously true because of CONGs′,k.(2)
u∈Vs and v∈V-Vs: since CONG,k,u is connected to v in path p with the removal of any k-1 vertices in G. If p⊆E-Es, p also exists 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 CONGs′,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 CONG,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, ∃a1,a2∈p∧a1,a2∈Vs, u is connected to a1, and a2 is connected to v in G-Gs. Since CONGs′,k,a1 is connected to a2 by removing those k-1 vertices. Then u is connected to v with the removal of any k-1 vertices in G′′.Corollary 12.
LetG1,G2,…,Gn be k-connected subgraphs of k-connected graph G. Let G1′,G2′,…,Gn′ be edges reduction of G1,G2,…,Gn, and G1′,G2′,…,Gn′ are k-connected. Then,(4)G′′=G-⋃i=1nGiG∪G⋃i=1nGi′G is k-connected.Lemma 13.
LetG=V,E be the initial topology of the PSN. Let G′=V,E′ be the topology after Algorithm 2 is completed. Let Gi=Vi,Ei be the AS networks resulting from Phase 1 in the topology control, where i=1,…,n and Ei=u,v∈E∣u,v∈Vi. Let Gi′=Vi,Ei′, where Ei′=Ei∩E′. Then, ∀i,j subject to 1≤i≤j≤n, we have that MCONGGi,Gj,k⇒MCONG′Gi′,Gj′,k.Proof of Lemma13.
Since nodes of any intra-AS arek-connected, we take an AS as anode here. Formally, we represent graph G as G¯=VS,ES, where VS=G1,G2,…,Gn and ES=Gi,Gj∣NBRGGi,Gj,k. Actually, edge Gi,Gj contains at least k disjoint paths between Gi and Gj. Let G¯′=VS,ES′ be the AS level representation of G′, where ES′=Gi′,Gj′∣NBRG′Gi′,Gj′,k. We use VS to represent the set of AS networks in G¯′, because we do not need to consider the topology of intra-AS (both Gi and Gi′ are k-connected). We take all of them as nodes, so we consider Gi,Gj and Gi′,Gj′ as the same edge. Recall that, in Algorithm 2, each edge Gi,Gj∈ES has weight DIAGi,Gj.
In order to prove Lemma13, it suffices to show that, ∀Gi,Gj∈G¯, Gi is connected to Gj in G¯′. We order all edges in G¯ in the ascending sequence of weights and then judge whether an edge should be placed into G¯′. Without loss of generality, let the ordering be e1,e2,…,em, where m=ES. Then we prove Lemma 13 by induction.
Base. Obviously, the pair of AS networks corresponding to edge e1 should always be placed into G¯′; that is, e1∈ES′.
Induction. ∀t≤m, if for all q<t, the pair of AS networks corresponding to eq are connected in G¯′ (either directly or indirectly). And suppose et=Gi,Gj. From Algorithm 2, the only reason why et∉ES′ (Gi is not directly connected to Gj in G¯′) is that there exists another AS  Gl, where both DIAGi,Gl and DIAGl,Gj are less than DIAGi,Gj. However, edges Gi,Gl and Gl,Gj come before Gi,Gj in the ascending order. From path GiGlGj¯, Gi is connected to Gj in G¯′.
By induction, we prove thatGi is connected to Gj in G¯′, and then MCONGGi,Gj,k⇒MCONG′Gi′,Gj′,k.Finally, we prove the correctness of Theorem8. In the proof, Gi and Gi′ have the same definition in Lemma 13.Proof of Theorem8.
For every ASGi, we know that CONGi,k is true after Algorithm 1. Then we partition those AS networks into sets A1,…,As, where each set contains AS networks which are multihop k-connected in G; that is, ∀r=1,…,s, then Gi∈Ar∧MCONGGi,Gj,k⇒Gj∈Ar. Then we define sets A1′,…,As′, where, ∀i,Gi∈Ar⇒Gi′∈Ar′. Applying Lemma 13 here, for every Ar′=Gr1′,…,Grm′, ∀1≤i<j≤m, we have MCONG′Gri′,Grj′,k. Take Ar′ as a subgraph of G′; Ar′=VAr′,EAr′, where VAr′=v∣v∈Ar′ and EAr′=u,v∣u,v∈Ar′∧u,v∈E′. Since Ar′ only contains multihop k-connected subgraphs, applying Corollary 10 here, we have that Ar′ is k-connected. Then, applying Corollary 12 here, we have that(5)G′=G-⋃r=1sArG∪G⋃r=1sAr′G is k-connected. ThenCONG,k⇔CONG′,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 DMTC algorithm. The following terms are used in the complexity analysis.LetN be the total number of nodes in the PSN. Let S be the number of AS networks, and let NS be the average number of nodes per AS; that is, NS=N/S. Let RB be the average probability of nodes that are border nodes in an AS, where 0<RB<1. Let SN be the average number of neighboring AS networks for each AS; that is, 0<SN<S.Table1 shows the average control messages utilized in each phase to complete the topology algorithm for each AS. We partition each phase into major steps. Hence, from Table 1, the total number of control messages required in the PSN is S2+λ+RBNS+2SN+2. It can be simplified as 2+λ+RBN+2SNS+2S, which is oN+oSNS in the worst case.Table 1
Average message complexity in each phase of an AS.
Steps in each phase
Number of control messages
Phase 1:
Each node announces its existence
N
s
Core of the AS is selected withλ cycles
λ
N
s
Each node announces its current role
N
s
Phase 2:
Core node computes the intra-AS topology
0
Phase 3:
All border nodes report their border lists to the parent core
N
s
⋅
R
B
Core node distributesDIA vector to its border nodes
1
Border nodes sendDIA vector to border nodes of other AS networks
S
N
Border nodes of other AS networks reportDIA vector to their parent core
S
N
Core node sends the link list to the AS members
1


## 6. Simulation Results and Discussions

In this section, we present several sets of simulation results to evaluate the effectiveness of the proposed DMTC algorithm. Recall that the proposed algorithm is a hybrid of centralized algorithm and distributed algorithm. We compare it with typical centralized algorithmFGSSk [19] and distributed algorithm FLSSk [19]. 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 rangeRmax=450 km. Nodes are randomly distributed in a 2500×2500km2 region. In order to study the effect of AS size on the resulting topologies, we vary the number of nodes in the region among 125, 150, 175, 200, 225, and 250.For each network, we consider(1)
k-connectivity: k=1 and k=2;(2)
algorithms: the proposed hybrid algorithm DMTC, centralized algorithmFGSSk, and distributed algorithm FLSSk;(3)
1000 Monte Carlo simulations.Relative to DMTC, recall that, inPhase 1 of AS network formation, we configure that each node is at most one hop away from its parent core. In our simulations, algorithm inPhase 1 generates AS networks where the average number of nodes per AS is 6.39, 7.48, 8.51, 9.69, and 10.69 (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 DMTC algorithm. Four figures are given here:(1)
Figure3(a) shows the original physical topology without topology control. All nodes communicate with the maximal transmission range Rmax.(2)
Figure3(b) shows the topology after applying algorithm ofPhase 1. Nodes of the PSN are divided into 17 AS networks, where the average number of nodes per AS is 7.35.(3)
Figure3(c) is the topology resulting from the intra-AS topology control algorithm ofPhase 2, when k=2.(4)
Figure3(d) shows the topology after applying inter-AS topology control algorithm ofPhase 3, when k=2. The inter-AS links are represented by black color.Figure 3
Network topologies of 125 nodes with different topology control settings. (a) Without topology control. (b) After applying algorithm ofPhase 1. (c) k=2, after applying algorithm ofPhase 2. (d) k=2, after applying algorithm ofPhase 3.
(a)
(b)
(c)
(d)In Figure4, we show average and maximum delay between two nodes which are obtained from three topology control algorithms (the proposed hybrid algorithm DMTC, centralized algorithm FGSSk [19], and distributed algorithm FLSSk [19]). Note that we only consider link propagation delay in this simulation. It is evident from those results that DMTC is very effective in reducing the delay between nodes. Recall that the maximal transmission range Rmax of one node is 450 km. The corresponding delay is 1.501 ms. When k=1 (Figure 4(a)), DMTC reduces the maximum delay to 1.106 ms when there are 125 nodes in the PSN and as low as 0.703 ms when there are 225 nodes. The maximum delay is approximately 13.6% to 20.1% lower than FLSS1 distributed algorithm and 6.1% to 18.6% higher than FGSS1 centralized algorithm. For the average delay, DMTC reduces the delay to 0.656 ms when there are 125 nodes in the PSN and as low as 0.451 ms when there are 225 nodes, which is approximately 5.2% to 10.3% lower than FLSS1 distributed algorithm and 8.5% to 10.9% higher than FGSS1 centralized algorithm.Figure 4
Results from three topology control algorithms (DMTC,FGSSk, and FLSSk showing average and maximum link delay when (a) k=1 and (b) k=2 and (c) average node degree).
(a)
(b)
(c)Whenk=2 (Figure 4(b)), both the maximum and average delay resulting from DMTC, FGSS2, and FLSS2 are all higher than those when k=1. That is expected because 2-connected connectivity is a stronger property than 1-connected connectivity. What is 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 AS networks and one more additional disjoint path from each node to other nodes within all AS networks. The maximum delay is approximately 18.5% to 20.9% lower than FLSS2 distributed algorithm and 10.3% to 17.8% higher than FGSS2 centralized algorithm. The average delay is approximately 12.5% to 18.6% lower than FLSS2 distributed algorithm and 8.2% to 15.6% higher than FGSS2 centralized algorithm.The delay performance of the proposed algorithm DMTC falls in betweenFGSSk and FLSSk. This is expected because DMTC is a hybrid of centralized algorithm and distributed algorithm. Even though centralized algorithm has better delay performance (less than 20%), 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 DMTC is constrained among neighboring AS networks, and the delay performance is better than distributed algorithm in the simulation result. Thus, the proposed DMTC algorithm is better than centralized algorithm and distributed algorithm for PSN.Figure4(c) shows the average node degrees produced by DMTC versus a network without topology control. It is obvious that the node degree of a network with DMTC does not depend on the size or density of the network.Figure5 illustrates the number of messages exchanges required per node to complete DMTC in our simulation environment. Recall that the message complexity of the DMTC algorithm is oN+oSNS. For each node, the average number of messages required is oN+oSNS/N=o1. The result validates the analysis. When the number of nodes in the PSN increases from 125 to 225, the average number of messages required per node in DMTC does not increase. This shows that the DMTC algorithm has little extra overhead.Figure 5
Number of messages exchanges per node in DMTC when the number of nodes in the PSN increases.


## 7. Conclusion

We studied the topology control problem in the PSN using an AS approach. The motivation was that the AS network model decouples the complex PSN into simple AS networks. Then we proposed the DMTC algorithm to minimize time delay in the PSN. Compared with most existing approaches where either the purely centralized or the purely distributed control method is adopted, DMTC utilizes a hybrid method. In this way, not only is the control message exchange constrained among local neighboring AS networks, but also the strong connectivity of the network is preserved. Our simulation results validated the theoretic analysis and effectiveness of the DMTC algorithm.Although the assumptions stated in Sections2 and 6 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 the PSN are homogeneous, obstacle-free channel and equal Rmax) for DMTC algorithm so as to improve its practicality in real applications. In addition, we find that the proposed “hybrid approach” is a general method. It can be extended to solve the control problem of many other large scale networks, for example, machine-to-machine (M2M) network and space information network (SIN). Different topology control algorithms can be applied within AS network and between adjacent AS networks, depending on the optimization objective. And each AS network can be further separated into sub-AS networks. We will study these issues in the near future.



---

*Source: 726274-2015-10-18.xml*