Page 32 - ITU KALEIDOSCOPE, ATLANTA 2019

2019 ITU Kaleidoscope Academic Conference

into a sparse mesh network topology. The objective of the 5.1 Backbone network design algorithm

Algorithm 1: LTR algorithm The algorithm for creating a hierarchical backbone network
1 mark all links in dense mesh network as non-visited; topology is provided by Algorithm 2. It uses a graph coloring
2 for each non-visited link of the network do approach, where the nodes of the network are initially
3 select worst non-visited link of the network; // i.e., assigned a white color and thereafter, they are colored black or
link with lowest link margin. gray, depending on whether they have qualified for backbone
artificially delete the link;
4 or edge status. This algorithm returns a network configuration
run the K-shortest path to detect if the network is still
5
k-connected; // it is k-connected if you Algorithm 2: Backbone formation
can find k-disjoint shortest paths for 1. Initialisation.
each source-destination pair of the Assign a white colour and zero height to all nodes of the
reduced network. network,
6 if it is k-connected then Select a node n from White whose profit/reward is highest,
remove the link permanently;
7 Backbone ← {n},
8 else Grey ← all neighbours of n,
leave the link and mark it as visited;
White ← N \ ({n} ∪ Grey).
9
10 end
2. Select a node k from Grey whose profit/reward is highest and
algorithm is to improve i) quality of the links by retaining height is lower.
Include k into the Backbone,
the links of high margin and pruning those of low margin Assign a black colour to k and update its height,
and ii) maintain the reliability of the network at a predefined Remove k and its neighbours from White,
level. In order to design fault-tolerant networks, the algorithm Include the neighbours of k in Grey.
uses the K-Shortest Path (K-SP) algorithm in [14] to compute
3. Repeat Step 2 whenever White , ∅.
K-shortest paths between source-destination pairs where K >
1. Links that provide K-disjoint shortest paths from each
node to the network sink are considered and included in the where the backbone nodes are colored into black and the edge
sparse network. nodes are colored into gray.

5. HIERARCHICAL BACKBONE NETWORK 6. PERFORMANCE EVALUATION
TOPOLOGY DESIGN
We conducted different experiments to evaluate the
The backbone design consists of finding a network performance of our designs. The network engineering
configuration that maximizes the reward function subject to process in Figure 2 is proposed and was followed to evaluate
similar QoS constraints as in the sparse network design but our designs. Building upon the elevation maps of an area
with the objective of partitioning the network into two sets: a where the network is to be designed, network planning
dominating set, which form the backbone and a dominated set software tool such as Radio Mobile [15] or SPLAT [16] is
forming the edge of the network. Mathematically formulated, used to produce feasible links of the targeted mesh network.
the design process consists of finding a network configuration Using the network report generated from the network
C opt derived from the graph G = (N,L) such that N is planning tool, the proposed topology reduction process is
divided into a dominating set N and a dominated set N, and
ˇ
ˆ
the design objective is achieved and its constraints are met.
Õ
ˆ τ opt (C opt ) = max P(k) (7)
C n ∈G
k∈N[C n ]
subject to

((7).1) lm (x, y) > τ lm ∀ x, y ∈ C opt
((7).2) k sp (x, y) > τ sp ∀ x, y ∈ C opt
ˆ
ˆ
((7).3) ∀n ∈ C opt : n ∈ N ∨ ∃m ∈ N : (n,m) ∈ L
ˇ
ˆ
ˇ
ˆ
((7).4) N ∪ N = ∅ ∧ N ∩ N = N
where N(X) is the set of nodes in the configuration X. Note
that constraints (7).1 and (7).2 express the QoS in terms of link
margin and reliability respectively, while constraints (7).3
and (7).4 represent the topology control model in terms
of backbone connectivity based on the K-dominated set
model [17, 18, 19]. Figure 2 – Network engineering process

– 12 –