Page 30 - ITU KALEIDOSCOPE, ATLANTA 2019

2019 ITU Kaleidoscope Academic Conference

and the results show the designs can guide network engineers The main goal of the backbone-based techniques is to find
to select the most relevant performance metrics during a a connected subset of nodes in a network that guarantee
network feasibility study aimed at guiding the implementation connectivity by allowing every other node in the network
process. to reach at least one node on the backbone in a direct way
The rest of the paper is structured as follows: section 2 [11]. A communication backbone can be created by selecting
introduces topology reduction and discusses the approaches nodes that form a connected dominating set (CDS). From
used to achieve it; section 3 discusses the proposed graph theory, a CDS of a graph is a connected subset in which
network optimization function that is used to introduce all other nodes that do not belong to that subset have at least
hierarchical backbone network topology from sparse network one adjacent neighbor inside the subset. Advantages of this
topology; section 4 discusses the proposed link-based CDS-based topology control are collisions control, protocol
topology reduction algorithm for reducing dense mesh overhead control and energy consumption reduction, efficient
network topology to sparse mesh network topology; section network organization and scalability improvement [10].
5 discusses the backbone network topology algorithm used
to introduce hierarchical backbone network topology from 3. NETWORK OPTIMIZATION FUNCTION
sparse network topology; section 6 is a performance
evaluation of the proposed designs; and section 7 concludes The network design consists of finding a network
the paper. configuration expressed by the graph G = (N,L), where N
is the set of nodes while L is the set of links connecting the
nodes with the objective of optimizing an objective function
2. TOPOLOGY REDUCTION AND APPROACHES representing a penalty to be minimized or a profit/reward
While algorithms discussed in this section are designed for to be gained. In this paper, the network engineering profit
function P(G) is considered. It combines reliability and
application in physical networks, the designs proposed in quality of service (QoS) features, which are based on three
this paper are for predesigning a network topology offline metric measures; node degree, link margin and Euclidean
before it is replicated in reality. In general, topology control distance.
can be achieved through three main mechanisms: power
control technique, power mode mechanism and hierarchical
formation technique. 3.1 Network engineering design
In power control technique the communication range of the The profit function P(G) is expressed as follows:
wireless nodes is controlled by modifying the transmission
power parameter of the nodes in the network. This way the P(G) = Õ P(i) (1)
network nodes are able to better manage their neighborhood i∈N
size, interference level, power consumption and connectivity P(i) = α ∗ nd i + β ∗ lm i + γ ∗ sp i (2)
[9]. In power mode mechanism, the node activity is controlled
by switching between active and sleep operation modes to where, α, β and γ are coefficients of proportionality used to
dispense with redundant nodes and still achieve the desired express the preference for a given metric measure. A high
connectivity [10]. The main idea of the algorithms using value of one of the coefficients reveals a preference for the
these first two mechanisms is to produce a connected topology corresponding metric measure. The profit P(i) expresses the
by connecting each node with the smallest necessary set of resultant preference of node i N to be part of the backbone.
neighbors and with the minimum transmission power possible The metric measures are explained below.
[11]. These first two techniques are the main options for 1. Node degree: Nodes with a higher node degree lead
flat networks, where all nodes have essentially the same role to reduced network topology for the backbone network,
[7, 13], i.e., in an homogeneous infrastructure. which is preferred to nodes with a lower node degree.
Controlling the transmission power of the nodes or their Therefore, preference is given to nodes with a higher
activities only reduces the network topology to help save node degree than nodes with a lower node degree. The
energy but the approach does not prevent the transmission of node degree nd(i) of node i in a network graph with N
redundant information when several nodes are close to each number of nodes is calculated as:
other and may not simplify the network topology enough
for scalability [11]. The hierarchical formation technique N Õ
addresses the scalability problem. In hierarchical formation nd(i) = x ij (3)
technique, a reduced subset of the nodes in the network j=1
is selected and given more responsibilities on behalf of a where x ij = 1 if there is a link between node i and node
simplified and reduced functionality for the majority of the j and x ij = 0 otherwise.
nodes [11]. This approach greatly simplifies the network
topology and saves additional energy by assigning useful 2. Link margin: Links with higher link margins are
functions, such as information aggregation and filtering and better for communication than links with lower link
routing and message forwarding to the reduced subset of margins. Furthermore, nodes whose corresponding
nodes [11]. A hierarchical topology can be constructed by links have smaller differences in link margins are better
using either a backbone network or a cluster-based network. for communication than nodes whose corresponding

– 10 –