# Improved Route Discovery Based on Constructing Connected Dominating Set in MANET

Authors: Zifen Yang; Deqian Fu; Lihua Han; Seong Tae Jhang
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## Abstract

A mobile ad hoc network (MANET) is widely applied in various urgent scenarios, benefiting from its feature that the hosts can communicate with each other without any physical infrastructure. An efficient routing function plays a critical role in MANET, and routing based on CDS is a promising approach. In this paper, a novel approach is proposed to obtain a stable routing path and prolong lifetime of MANET, by integrating three factors such as energy, mobility, and degree for the status of node minimum connected dominating set (SoN-MCDS). Extensive simulations show that the proposed protocol is superior to other classical ones in terms of lifetime and low energy consumption.


---

## Body

## 1. Introduction

Because it is hard to communicate effectively in infrastructured networks, many infrastructures were damaged in disasters such as earthquake and flooding. MANET provides an instant and distributed peer to peer ad hoc communication among equipment. An Ad hoc network is a collection of wireless mobile hosts (also called nodes) such as notebooks, mobile phones, or the other portable equipment that communicate with each other by wireless channels. Recently, MANET is often applied in disaster relief operations as an effective facility [1]. However, an issue is that two nodes in a MANET can communicate directly if and only if they are within same radio transmission ranges. Hence, an intuitive choice is to introduce a strategy of multihop routing in MANET [2].MANET routing protocols can be divided into two groups: flat and hierarchical routing protocols, according to the logic of the network structure. In a flat routing protocol, every node is set to equal status and discovers a route with a broadcasting scheme. In this case, every node has to repeat sending or receiving broadcast signals. Moreover, in a network with dynamic topology, routing tables have to be updated frequently. Unfortunately, the flooding of broadcast signals, especially for frequent broadcasting, consumes too much battery power and even may lead to congestion as well. In hierarchical routing protocol, backbone-based routing pattern can significantly reduce the energy consumption in an ad hoc network. When a node wants to send message to its destination, it only needs to send the message to backbone, unless the destination is one of its neighbors. Obviously, the number of update routing messages is significantly reduced, compared with the number in the network with a flat routing protocol, while for backbone-based strategy, a direct requirement is that all backbone nodes should be connected. The connected backbone is called a connected dominating set (CDS). For routing based on CDS, there are many advantages such as restrict search space. Thus, flooding storm can be avoided, routing overhead can be reduced, and less energy can be consumed so that the lifetime of MANET can be prolonged. Based on all of the above considerations we propose a novel approach to construct SoN-MCDS by integrating three factors: energy, mobility, and degree.The rest of the paper is organized as follows. In Section2, the system model and definitions are presented and the related works are discussed. In Section 3, the algorithm of forming and fast repairing SoN-MCDS is presented, and using SoN-MCDS to implement route discovery is described in Section 4. In Section 5, some simulation results are shown to prove the performance of the proposed algorithm. Finally, a conclusion is drawn in Section 6.


## 2. Related Work

Throughout this paper, some notations in our algorithm are denoted as follows:N
(
u
): neighbors set for node u,
E
rm
(
u
): remaining energy of node u,
E
in
(
u
): initial energy of node u,
ST
(
u
): the current state of node u,
n
L
i
s
t: a list of nodes in MANET,
DS: dominating set,
CDS: connected dominating set.


### 2.1. Network Model and Related Definition

Traditionally, Unit Disk Graph (UDG) is utilized to model MANET as illustrated in Figure1. As well, three related definitions are presented as follows.Figure 1
UDG model.Definition 1 (unit disk graph (UDG)).
UDG is a 2-dimentional plane graph that, for everyu
,
v
∈
V, there is a bidirectional edge between u and v, if and only if Eudist
(
u
,
v
)
≤
1. Here, Eudist
(
u
,
v
)
≤
1 is the Euclidean distance between u and v.Definition 2 (dominating set (DS)).
Given graphG
=
(
V
,
E
), V
′
⊆
V is a DS of G
=
(
V
,
E
), only if for every (
u
,
v
)
∈
E, either u
∈
V
′ or v
∈
V
′ is true.Definition 3 (connected dominating set (CDS)).
(C
⊆
V) is a CDS of G if (1) C is a DS and (2) a graph induced by C is connected.


### 2.2. Related Works on Finding MCDS

In graph theory, finding the minimum CDS is NP-hard [3]. Many works [4–7] try to construct minimum CDS with two kinds of methods. The reduction-based methods [4, 5] construct a CDS from one node with maximum degree. Initially, a node is colored and its neighbors are colored with other color. Then, the size of CDS is reduced by some rules to delete some nodes. On the other hand, the increase-based methods [6, 7] compute a DS at first and then select some nodes to connect the nodes in DS.However, the two kinds of methods did not consider two problems: limited energy and the mobility of the node. In disaster relief operations, as we all known, there are few chances to recharge the battery powered device. Also, nodes in MANET may move freely and randomly. Many works [8–12] take energy issue into consideration. A survey [8] of energy efficient scheduling mechanisms in sensor networks is given by Wang and Xiao. An algorithm [12] on calculating power-aware connected dominating sets for efficient routing in ad hoc wireless network is proposed by Wu et al. The algorithm constructs a CDS according to two rules concerning energy and degree of nodes. Ramalakshmi and Radhakrishnan proposed an improving route discovery algorithm [13] using stable connected dominating set in MANETs, utilizing three phases to construct a CDS. Neighbor discovery is implemented at the first phases; then, the remaining two stages are constructing and pruning the constructed CDS. Ramrekha et al. proposed an energy efficient and scalable routing protocol [14] for extreme emergency ad hoc communications. The algorithm selects routing path depending on the length of route and the remaining energy. Yu et al. have proposed energy efficient algorithm [15] to construct a dominating tree in wireless ad hoc and sensor networks. The algorithm obtains theoretically an approximation factor up to 9 with an efficient computational cost of O
(
n
) for message complexity and O
(
n
) for time complexity, which results in consuming less energy in ad hoc network.Some recent results focus on the mobility of nodes in constructing CDS. A mobility based clustering approach [16] is proposed by An and Papavassiliou to support mobility management and multicast routing in mobile ad hoc wireless network. A localized virtual backbone construction scheme [17] is proposed by Wang et al. to connect maximal independent set with multiple initiators. The algorithm takes node stability into consideration and constructs the backbone quickly.Furthermore, no proper mechanism to handle and save critical node failure in existing ad hoc routing protocols, so that the network consumes more battery power, even leads to node failure. Revathi and Rangaswamy [18] proposed efficient flooding and repairing local route with stable CDS for mobile ad hoc networks. A node with minimum velocity and maximum signal strength is selected as a dominator. However, the degree and energy of node are not considered.Therefore, it is observed that the energy and movement of nodes make significant reflection of the construction of virtual backbone with minimum numbers of nodes. In this paper, we take into account three factors of energy, mobility and degree of nodes, to propose an energy efficient protocol aiming to get a stable path for routing and prolong lifetime of network.


## 2.1. Network Model and Related Definition

Traditionally, Unit Disk Graph (UDG) is utilized to model MANET as illustrated in Figure1. As well, three related definitions are presented as follows.Figure 1
UDG model.Definition 1 (unit disk graph (UDG)).
UDG is a 2-dimentional plane graph that, for everyu
,
v
∈
V, there is a bidirectional edge between u and v, if and only if Eudist
(
u
,
v
)
≤
1. Here, Eudist
(
u
,
v
)
≤
1 is the Euclidean distance between u and v.Definition 2 (dominating set (DS)).
Given graphG
=
(
V
,
E
), V
′
⊆
V is a DS of G
=
(
V
,
E
), only if for every (
u
,
v
)
∈
E, either u
∈
V
′ or v
∈
V
′ is true.Definition 3 (connected dominating set (CDS)).
(C
⊆
V) is a CDS of G if (1) C is a DS and (2) a graph induced by C is connected.


## 2.2. Related Works on Finding MCDS

In graph theory, finding the minimum CDS is NP-hard [3]. Many works [4–7] try to construct minimum CDS with two kinds of methods. The reduction-based methods [4, 5] construct a CDS from one node with maximum degree. Initially, a node is colored and its neighbors are colored with other color. Then, the size of CDS is reduced by some rules to delete some nodes. On the other hand, the increase-based methods [6, 7] compute a DS at first and then select some nodes to connect the nodes in DS.However, the two kinds of methods did not consider two problems: limited energy and the mobility of the node. In disaster relief operations, as we all known, there are few chances to recharge the battery powered device. Also, nodes in MANET may move freely and randomly. Many works [8–12] take energy issue into consideration. A survey [8] of energy efficient scheduling mechanisms in sensor networks is given by Wang and Xiao. An algorithm [12] on calculating power-aware connected dominating sets for efficient routing in ad hoc wireless network is proposed by Wu et al. The algorithm constructs a CDS according to two rules concerning energy and degree of nodes. Ramalakshmi and Radhakrishnan proposed an improving route discovery algorithm [13] using stable connected dominating set in MANETs, utilizing three phases to construct a CDS. Neighbor discovery is implemented at the first phases; then, the remaining two stages are constructing and pruning the constructed CDS. Ramrekha et al. proposed an energy efficient and scalable routing protocol [14] for extreme emergency ad hoc communications. The algorithm selects routing path depending on the length of route and the remaining energy. Yu et al. have proposed energy efficient algorithm [15] to construct a dominating tree in wireless ad hoc and sensor networks. The algorithm obtains theoretically an approximation factor up to 9 with an efficient computational cost of O
(
n
) for message complexity and O
(
n
) for time complexity, which results in consuming less energy in ad hoc network.Some recent results focus on the mobility of nodes in constructing CDS. A mobility based clustering approach [16] is proposed by An and Papavassiliou to support mobility management and multicast routing in mobile ad hoc wireless network. A localized virtual backbone construction scheme [17] is proposed by Wang et al. to connect maximal independent set with multiple initiators. The algorithm takes node stability into consideration and constructs the backbone quickly.Furthermore, no proper mechanism to handle and save critical node failure in existing ad hoc routing protocols, so that the network consumes more battery power, even leads to node failure. Revathi and Rangaswamy [18] proposed efficient flooding and repairing local route with stable CDS for mobile ad hoc networks. A node with minimum velocity and maximum signal strength is selected as a dominator. However, the degree and energy of node are not considered.Therefore, it is observed that the energy and movement of nodes make significant reflection of the construction of virtual backbone with minimum numbers of nodes. In this paper, we take into account three factors of energy, mobility and degree of nodes, to propose an energy efficient protocol aiming to get a stable path for routing and prolong lifetime of network.


## 3. Forming and Fast Repairing SoN-MCDS

Based on the above considerations, we observed that energy and mobility provide a significant reflection of the stability and the lifetime of MANET. Hence, when one source node wants to send message to destination, the proposed algorithm takes into account three aspects such as the remaining energy of nodeu, the velocity of u, and the degree of u at current state. This protocol works in three stages. The first stage is SoN-DS formation, and the second stage is connecting and pruning SoN-MCDS. If one of the nodes or links is broken for some reasons, the third stage will be executed.


### 3.1. The Definition ofST
(
u
)

The current status of nodeST
(
u
) is defined as (1), considering factors of energy, degree, and mobility of node u: (1)
ST
(
u
)
=
E
s
V
s
·
degree
u
,
if
V
s
>
0
E
s
·
degree
u
,
otherwise.Definition 4 (the mobility of a node).
V
s considers its neighbor set, and its mobility factors can be valued as the percentage of neighbors which remains the same between t time and t
+
1 time. With the symmetric difference V
s, the algorithm can select more stable nodes as dominating node:(2)
V
s
=
N
t
+
1
u
∖
N
t
u
N
t
+
1
u
∪
N
t
u
,where the form of A
∖
B denotes the symmetric difference between two sets A and B.Definition 5 (the energy metric of a node).
E
s is defined as (3). The metrics E
s help algorithm to select energy-rich nodes: (3)
E
s
=
E
rm
u
E
in
u
.


### 3.2. A Three-Phase Algorithm for Constructing and Fast Repairing SoN-MCDS

In this section, we propose a three-phase algorithm to construct and repair SoN-MCDS.


#### 3.2.1. Phase One: Constructing SoN-DS

Originally, a list of nodesn
L
i
s
t ordered by ST
(
u
) has to be prepared in advance. In MANET, every mobile node says hello to its neighbors with message ST
(
u
)
,
N
(
u
). Then, each node v
∈
V in n
L
i
s
t is sorted by comparing two nodes u
,
v with the following simple rules.Rule 1.
u is stored in n
L
i
s
t if ST
(
u
)
>
ST
(
v
).Rule 2.
u is stored in n
L
i
s
t if E
s
(
u
)
>
E
s
(
v
) when ST
(
u
)
=
ST
(
v
).Rule 3.
u is stored in n
L
i
s
t if degree
(
u
)
>
degree
(
v
) when ST
(
u
)
=
ST
(
v
), E
s
(
u
)
=
E
s
(
v
).The process of forming SoN-DS is described in Algorithm1. Initially, all nodes of MANET are marked in white color. The first node u in n
L
i
s
t is considered as a dominating node and marked in black color; then all the neighbors of node u are marked in gray. After that, the remaining nodes in n
L
i
s
t repeat the same operations until no white node is in the MANET. Finally, a ST-CDS is formed by all the black nodes.Algorithm 1:Forming SoN-DS.
Input: a connected graphG
(
V
,
E
)
Output: a dominate setD
(1)
D
=
Ø
;
L
e
n
=
|
V
|
(2)
For each v
∈
V
(3)
c
o
l
o
r
(
v
)
=
W
H
I
T
E;
(4)
End for
(5)
For  i
=
1,2
,
…
,
L
e
n do
(6)
u
=
n
L
i
s
t
[
i
];
(7)If  c
o
l
o
r
(
u
)
!
=
G
R
A
Y
(8)c
o
l
o
r
(
u
)
=
B
L
A
C
K;
(9)End if
(10)Foreach  v
∈
N
(
u
)
(11)If  c
o
l
o
r
(
v
)
=
=
W
H
I
T
E
(12)c
o
l
o
r
(
v
)
=
G
R
A
Y;
(13)End if
(14)End for
(15)D
=
D
∪
u;
(16)End for


#### 3.2.2. Phase Two: Constructing SoN-MCDS

In this stage, we will construct a CDS and minimize its size, which is described in Algorithm2. At first, the first node of n
L
i
s
t is considered as a leader. Then, for each node in D excluding the leader, does a path without cycle between the node and the leader exist? If no path exists, a path must be created via selecting gray nodes as the relay nodes. The number of relay nodes is as smaller as possible. The operations are repeated until all the black nodes are connected. Then, all selected gray nodes are marked black. As a result, SoN-MCDS is constructed by all the black nodes. Further, the size of the constructed SoN-MCDS can be reduced via deleting extra black nodes.Algorithm 2:Forming SoN-MCDS.
Input: A connected graphG
(
V
,
E
) and D
Output:SoN-MCDS
(1)
l
e
a
d
e
r
=
n
L
i
s
t
[
1
]; L
e
n
=
|
V
|; c
o
u
n
t
=
0; S
=
Ø;
(2)
For  i
=
1,2
,
…
,
L
e
n  do
(3)u
=
n
L
i
s
t
[
i
]
(4)If there is no path between u and leader then
(5)  Create the shortest path viaGRAY node;
(6)End if
(7)If the path is a cycle then
(8)  Select another short path;
(9) Mark the selected GRAY node with BLACK;
(10)End if
(11)End for
(12)S  consists ofall the BLACK nodes
(13)For each v
∈
V
(14)If  c
o
l
o
r
(
v
)
=
G
R
A
Y
(15) Foreach u
∈
N
(
v
)
(16) If  c
o
l
o
r
(
u
)
=
B
L
A
C
K
(17) c
o
u
n
t
+
+;
(18) End if
(19) End for
(20) If  c
o
u
n
t
≥
2
(21) Choose any u
∈
N
(
v
)
(22) S
=
S∖u
(23) End if
(24)End if
(25)End for


#### 3.2.3. Phase Three: Repairing SoN-MCDS Locally

In this phase, an algorithm is presented for repairing SoN-MCDS locally as described in Algorithm3. If some nodes are deactivated due to reasons such as limited energy, the topology of the MANET has to be rebuilt. Hence, a new SoN-MCDS must be reconstructed with expensive cost of time and energy. Fortunately, the deactivated nodes only affect the local nodes. Hence, Algorithm 3 focuses on repairing SoN-MCDS locally.Algorithm 3:Repairing SoN-MCDS.
Input:
the broken nodev;
a connected graphG
(
V
,
E
)
Output:Son-MCDS
(1) If c
o
l
o
r
(
v
)
=
G
R
A
Y
(2) Free (v);
(3)  End if
(4) If c
o
l
o
r
(
v
)
=
B
L
A
C
K
(5)  V
′
=
N
(
v
)
∪ All the neighboring nodes of N
(
v
) in SoN-MCDS;
(6) E
′
=
E
/
(
e
d
g
e
s
c
o
n
n
e
c
t
e
d
t
o
v
);
(7) End if
(8) D = Algorithm 1 (G
(
V
′
,
E
′
))
(9) SoN-MCDS = Algorithm 2 (G
(
V
,
E
)
,
D
)


## 3.1. The Definition ofST
(
u
)

The current status of nodeST
(
u
) is defined as (1), considering factors of energy, degree, and mobility of node u: (1)
ST
(
u
)
=
E
s
V
s
·
degree
u
,
if
V
s
>
0
E
s
·
degree
u
,
otherwise.Definition 4 (the mobility of a node).
V
s considers its neighbor set, and its mobility factors can be valued as the percentage of neighbors which remains the same between t time and t
+
1 time. With the symmetric difference V
s, the algorithm can select more stable nodes as dominating node:(2)
V
s
=
N
t
+
1
u
∖
N
t
u
N
t
+
1
u
∪
N
t
u
,where the form of A
∖
B denotes the symmetric difference between two sets A and B.Definition 5 (the energy metric of a node).
E
s is defined as (3). The metrics E
s help algorithm to select energy-rich nodes: (3)
E
s
=
E
rm
u
E
in
u
.


## 3.2. A Three-Phase Algorithm for Constructing and Fast Repairing SoN-MCDS

In this section, we propose a three-phase algorithm to construct and repair SoN-MCDS.


### 3.2.1. Phase One: Constructing SoN-DS

Originally, a list of nodesn
L
i
s
t ordered by ST
(
u
) has to be prepared in advance. In MANET, every mobile node says hello to its neighbors with message ST
(
u
)
,
N
(
u
). Then, each node v
∈
V in n
L
i
s
t is sorted by comparing two nodes u
,
v with the following simple rules.Rule 1.
u is stored in n
L
i
s
t if ST
(
u
)
>
ST
(
v
).Rule 2.
u is stored in n
L
i
s
t if E
s
(
u
)
>
E
s
(
v
) when ST
(
u
)
=
ST
(
v
).Rule 3.
u is stored in n
L
i
s
t if degree
(
u
)
>
degree
(
v
) when ST
(
u
)
=
ST
(
v
), E
s
(
u
)
=
E
s
(
v
).The process of forming SoN-DS is described in Algorithm1. Initially, all nodes of MANET are marked in white color. The first node u in n
L
i
s
t is considered as a dominating node and marked in black color; then all the neighbors of node u are marked in gray. After that, the remaining nodes in n
L
i
s
t repeat the same operations until no white node is in the MANET. Finally, a ST-CDS is formed by all the black nodes.Algorithm 1:Forming SoN-DS.
Input: a connected graphG
(
V
,
E
)
Output: a dominate setD
(1)
D
=
Ø
;
L
e
n
=
|
V
|
(2)
For each v
∈
V
(3)
c
o
l
o
r
(
v
)
=
W
H
I
T
E;
(4)
End for
(5)
For  i
=
1,2
,
…
,
L
e
n do
(6)
u
=
n
L
i
s
t
[
i
];
(7)If  c
o
l
o
r
(
u
)
!
=
G
R
A
Y
(8)c
o
l
o
r
(
u
)
=
B
L
A
C
K;
(9)End if
(10)Foreach  v
∈
N
(
u
)
(11)If  c
o
l
o
r
(
v
)
=
=
W
H
I
T
E
(12)c
o
l
o
r
(
v
)
=
G
R
A
Y;
(13)End if
(14)End for
(15)D
=
D
∪
u;
(16)End for


### 3.2.2. Phase Two: Constructing SoN-MCDS

In this stage, we will construct a CDS and minimize its size, which is described in Algorithm2. At first, the first node of n
L
i
s
t is considered as a leader. Then, for each node in D excluding the leader, does a path without cycle between the node and the leader exist? If no path exists, a path must be created via selecting gray nodes as the relay nodes. The number of relay nodes is as smaller as possible. The operations are repeated until all the black nodes are connected. Then, all selected gray nodes are marked black. As a result, SoN-MCDS is constructed by all the black nodes. Further, the size of the constructed SoN-MCDS can be reduced via deleting extra black nodes.Algorithm 2:Forming SoN-MCDS.
Input: A connected graphG
(
V
,
E
) and D
Output:SoN-MCDS
(1)
l
e
a
d
e
r
=
n
L
i
s
t
[
1
]; L
e
n
=
|
V
|; c
o
u
n
t
=
0; S
=
Ø;
(2)
For  i
=
1,2
,
…
,
L
e
n  do
(3)u
=
n
L
i
s
t
[
i
]
(4)If there is no path between u and leader then
(5)  Create the shortest path viaGRAY node;
(6)End if
(7)If the path is a cycle then
(8)  Select another short path;
(9) Mark the selected GRAY node with BLACK;
(10)End if
(11)End for
(12)S  consists ofall the BLACK nodes
(13)For each v
∈
V
(14)If  c
o
l
o
r
(
v
)
=
G
R
A
Y
(15) Foreach u
∈
N
(
v
)
(16) If  c
o
l
o
r
(
u
)
=
B
L
A
C
K
(17) c
o
u
n
t
+
+;
(18) End if
(19) End for
(20) If  c
o
u
n
t
≥
2
(21) Choose any u
∈
N
(
v
)
(22) S
=
S∖u
(23) End if
(24)End if
(25)End for


### 3.2.3. Phase Three: Repairing SoN-MCDS Locally

In this phase, an algorithm is presented for repairing SoN-MCDS locally as described in Algorithm3. If some nodes are deactivated due to reasons such as limited energy, the topology of the MANET has to be rebuilt. Hence, a new SoN-MCDS must be reconstructed with expensive cost of time and energy. Fortunately, the deactivated nodes only affect the local nodes. Hence, Algorithm 3 focuses on repairing SoN-MCDS locally.Algorithm 3:Repairing SoN-MCDS.
Input:
the broken nodev;
a connected graphG
(
V
,
E
)
Output:Son-MCDS
(1) If c
o
l
o
r
(
v
)
=
G
R
A
Y
(2) Free (v);
(3)  End if
(4) If c
o
l
o
r
(
v
)
=
B
L
A
C
K
(5)  V
′
=
N
(
v
)
∪ All the neighboring nodes of N
(
v
) in SoN-MCDS;
(6) E
′
=
E
/
(
e
d
g
e
s
c
o
n
n
e
c
t
e
d
t
o
v
);
(7) End if
(8) D = Algorithm 1 (G
(
V
′
,
E
′
))
(9) SoN-MCDS = Algorithm 2 (G
(
V
,
E
)
,
D
)


## 3.2.1. Phase One: Constructing SoN-DS

Originally, a list of nodesn
L
i
s
t ordered by ST
(
u
) has to be prepared in advance. In MANET, every mobile node says hello to its neighbors with message ST
(
u
)
,
N
(
u
). Then, each node v
∈
V in n
L
i
s
t is sorted by comparing two nodes u
,
v with the following simple rules.Rule 1.
u is stored in n
L
i
s
t if ST
(
u
)
>
ST
(
v
).Rule 2.
u is stored in n
L
i
s
t if E
s
(
u
)
>
E
s
(
v
) when ST
(
u
)
=
ST
(
v
).Rule 3.
u is stored in n
L
i
s
t if degree
(
u
)
>
degree
(
v
) when ST
(
u
)
=
ST
(
v
), E
s
(
u
)
=
E
s
(
v
).The process of forming SoN-DS is described in Algorithm1. Initially, all nodes of MANET are marked in white color. The first node u in n
L
i
s
t is considered as a dominating node and marked in black color; then all the neighbors of node u are marked in gray. After that, the remaining nodes in n
L
i
s
t repeat the same operations until no white node is in the MANET. Finally, a ST-CDS is formed by all the black nodes.Algorithm 1:Forming SoN-DS.
Input: a connected graphG
(
V
,
E
)
Output: a dominate setD
(1)
D
=
Ø
;
L
e
n
=
|
V
|
(2)
For each v
∈
V
(3)
c
o
l
o
r
(
v
)
=
W
H
I
T
E;
(4)
End for
(5)
For  i
=
1,2
,
…
,
L
e
n do
(6)
u
=
n
L
i
s
t
[
i
];
(7)If  c
o
l
o
r
(
u
)
!
=
G
R
A
Y
(8)c
o
l
o
r
(
u
)
=
B
L
A
C
K;
(9)End if
(10)Foreach  v
∈
N
(
u
)
(11)If  c
o
l
o
r
(
v
)
=
=
W
H
I
T
E
(12)c
o
l
o
r
(
v
)
=
G
R
A
Y;
(13)End if
(14)End for
(15)D
=
D
∪
u;
(16)End for


## 3.2.2. Phase Two: Constructing SoN-MCDS

In this stage, we will construct a CDS and minimize its size, which is described in Algorithm2. At first, the first node of n
L
i
s
t is considered as a leader. Then, for each node in D excluding the leader, does a path without cycle between the node and the leader exist? If no path exists, a path must be created via selecting gray nodes as the relay nodes. The number of relay nodes is as smaller as possible. The operations are repeated until all the black nodes are connected. Then, all selected gray nodes are marked black. As a result, SoN-MCDS is constructed by all the black nodes. Further, the size of the constructed SoN-MCDS can be reduced via deleting extra black nodes.Algorithm 2:Forming SoN-MCDS.
Input: A connected graphG
(
V
,
E
) and D
Output:SoN-MCDS
(1)
l
e
a
d
e
r
=
n
L
i
s
t
[
1
]; L
e
n
=
|
V
|; c
o
u
n
t
=
0; S
=
Ø;
(2)
For  i
=
1,2
,
…
,
L
e
n  do
(3)u
=
n
L
i
s
t
[
i
]
(4)If there is no path between u and leader then
(5)  Create the shortest path viaGRAY node;
(6)End if
(7)If the path is a cycle then
(8)  Select another short path;
(9) Mark the selected GRAY node with BLACK;
(10)End if
(11)End for
(12)S  consists ofall the BLACK nodes
(13)For each v
∈
V
(14)If  c
o
l
o
r
(
v
)
=
G
R
A
Y
(15) Foreach u
∈
N
(
v
)
(16) If  c
o
l
o
r
(
u
)
=
B
L
A
C
K
(17) c
o
u
n
t
+
+;
(18) End if
(19) End for
(20) If  c
o
u
n
t
≥
2
(21) Choose any u
∈
N
(
v
)
(22) S
=
S∖u
(23) End if
(24)End if
(25)End for


## 3.2.3. Phase Three: Repairing SoN-MCDS Locally

In this phase, an algorithm is presented for repairing SoN-MCDS locally as described in Algorithm3. If some nodes are deactivated due to reasons such as limited energy, the topology of the MANET has to be rebuilt. Hence, a new SoN-MCDS must be reconstructed with expensive cost of time and energy. Fortunately, the deactivated nodes only affect the local nodes. Hence, Algorithm 3 focuses on repairing SoN-MCDS locally.Algorithm 3:Repairing SoN-MCDS.
Input:
the broken nodev;
a connected graphG
(
V
,
E
)
Output:Son-MCDS
(1) If c
o
l
o
r
(
v
)
=
G
R
A
Y
(2) Free (v);
(3)  End if
(4) If c
o
l
o
r
(
v
)
=
B
L
A
C
K
(5)  V
′
=
N
(
v
)
∪ All the neighboring nodes of N
(
v
) in SoN-MCDS;
(6) E
′
=
E
/
(
e
d
g
e
s
c
o
n
n
e
c
t
e
d
t
o
v
);
(7) End if
(8) D = Algorithm 1 (G
(
V
′
,
E
′
))
(9) SoN-MCDS = Algorithm 2 (G
(
V
,
E
)
,
D
)


## 4. Route Discovery Using SoN-MCDS

Generally, routing protocols in MANET are classified into table-driven, on-demanding, and hybrid routing. In table-driven routing protocol, each node maintains route table with all paths to every destination from the node. In on-demanding routing protocols like AODV and DSR [19], the source node will start the process of route discovery when it has no route to the destination. The source node broadcasts a route request packet (RREQ) to its neighbors at first. In turn, every receiving node broadcasts the RREQ packet until the packet reaches the destination. Finally, the destination node will send the route reply message (RREP) to the source after receiving the RREQ packet. However, this protocol leads to an issue of broadcast storm, especially in MANET with large scale. To solve the problem more efficiently, we implemented a route discovery process in AODV with the proposed SoN-MCDS. When SoN-MCDS node receives a RREQ packet, it broadcasts the packet. But the nodes out of SoN-MCDS only receive the packet. So, the number of RREQ packets is reduced and the network congestion may be avoided to a large extent.


## 5. Simulation and Analysis

### 5.1. Simulation Settings

In this section, we simulate the algorithm with Matlab program to prove the efficiency. The experiments are repeated for 50 trials with different network sizes and speeds of mobile nodes. The experimental configuration is listed as follows: a rectangular grid of ranging from5
∗
5 to 1000
∗
1000 m2 and 5–200 points are distributed randomly over the grid. The other parameters are listed as shown in Table 1.Table 1
Parameter
Value
Area size
1000∗ 1000 m2
Traffic type
Constant bit rate (CBR)
Packet size
512 bytes
MAC protocol
IEEE 802.11
Transmission range
250 m
Bandwidth
2 Mbps
Queue size
50 packets
Mobility model
Random waypoint model
Transmission power
0.667 W
Receiving power
0.365 W
Idle power
0.1 W
Maximum speed
5, 10, 15, 20, 25


### 5.2. Result Analysis

The average CDS size with varying network sizes is shown in Figure2. The average CDS size of SoN-MCDS is smaller than MaxS-CDS [18] thanks to integrating three factors of energy, mobility, and degree. But our result is larger than Wu-CDS [3]. The cause is that only the uncovered neighbors of the largest degree are selected as the virtual backbone with the algorithm of Wu-CDS.Figure 2
Average size of CDS.The average route length with increasing number of nodes is depicted in Figure3. As expected, the higher the CDS size, the shorter the route length.Figure 3
Average route length.The total energy consumed with different maximum speed with increasing number of nodes is shown in Figure4. With the increasing node speed, the existing path may be frequently damaged. So, another CDS must be constructed by consuming more energy. Therefore, our algorithm only considers the nodes moving slowly to be the backbone of network, so that the constructed CDS with our method is more stable and the risk of reconstructing operations is reduced.Figure 4
The total energy consumed with different maximum speed.Note that although the algorithm of WU-CDS gets a good result of minimum size CDS, it does not guarantee an optimal network performance. The total energy consumption of the protocols increases with the increasing node speed.The lifetime of network with increasing number of nodes is illustrated in Figure5. Obviously, our result shows that the nodes with more residual energy are selected as backbone nodes. As a consequence, the lifetime of the network can be prolonged significantly. That is, the survival time can be prolonged in emergency situations to provide more opportunities for the rescue.Figure 5
Average lifetime of network.


## 5.1. Simulation Settings

In this section, we simulate the algorithm with Matlab program to prove the efficiency. The experiments are repeated for 50 trials with different network sizes and speeds of mobile nodes. The experimental configuration is listed as follows: a rectangular grid of ranging from5
∗
5 to 1000
∗
1000 m2 and 5–200 points are distributed randomly over the grid. The other parameters are listed as shown in Table 1.Table 1
Parameter
Value
Area size
1000∗ 1000 m2
Traffic type
Constant bit rate (CBR)
Packet size
512 bytes
MAC protocol
IEEE 802.11
Transmission range
250 m
Bandwidth
2 Mbps
Queue size
50 packets
Mobility model
Random waypoint model
Transmission power
0.667 W
Receiving power
0.365 W
Idle power
0.1 W
Maximum speed
5, 10, 15, 20, 25


## 5.2. Result Analysis

The average CDS size with varying network sizes is shown in Figure2. The average CDS size of SoN-MCDS is smaller than MaxS-CDS [18] thanks to integrating three factors of energy, mobility, and degree. But our result is larger than Wu-CDS [3]. The cause is that only the uncovered neighbors of the largest degree are selected as the virtual backbone with the algorithm of Wu-CDS.Figure 2
Average size of CDS.The average route length with increasing number of nodes is depicted in Figure3. As expected, the higher the CDS size, the shorter the route length.Figure 3
Average route length.The total energy consumed with different maximum speed with increasing number of nodes is shown in Figure4. With the increasing node speed, the existing path may be frequently damaged. So, another CDS must be constructed by consuming more energy. Therefore, our algorithm only considers the nodes moving slowly to be the backbone of network, so that the constructed CDS with our method is more stable and the risk of reconstructing operations is reduced.Figure 4
The total energy consumed with different maximum speed.Note that although the algorithm of WU-CDS gets a good result of minimum size CDS, it does not guarantee an optimal network performance. The total energy consumption of the protocols increases with the increasing node speed.The lifetime of network with increasing number of nodes is illustrated in Figure5. Obviously, our result shows that the nodes with more residual energy are selected as backbone nodes. As a consequence, the lifetime of the network can be prolonged significantly. That is, the survival time can be prolonged in emergency situations to provide more opportunities for the rescue.Figure 5
Average lifetime of network.


## 6. Conclusion

In this paper, we propose an energy efficient protocol to use a stable path for routing and prolong lifetime of MANET. The proposed protocol forms SoN-MCDS to do the broadcast and data transmission, considering three factors of energy, movements, and degree of nodes. Simulation results show that our work is superior to other methods.



---

*Source: 612102-2015-08-18.xml*