Sage Journals: Discover world-class research

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.

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 Section 2, 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 Figure 1. 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 every $u, v \in V$ , there is a bidirectional edge between u and v, if and only if $Eudist (u, v) \leq 1$ . Here, $Eudist (u, v) \leq 1$ is the Euclidean distance between u and v.

Definition 2 (dominating set (DS)).

Given graph $G = (V, E)$ , $V^{'} \subseteq V$ is a DS of $G = (V, E)$ , only if for every $(u, v) \in E$ , either $u \in V^{'}$ or $v \in V^{'}$ is true.

Definition 3 (connected dominating set (CDS)).

( $C \subseteq 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 node u, 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 of $ST (u)$

The current status of node $ST (u)$ is defined as (1), considering factors of energy, degree, and mobility of node u:

\begin{matrix} ST (u) = \{\begin{cases} \frac{E_{s}}{V_{s}} \cdot |degree (u)|, & if V_{s} > 0 \\ E_{s} \cdot |degree (u)|, & otherwise. \end{cases} \end{matrix}

(1)

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:

\begin{matrix} V_{s} = \frac{N^{t + 1} (u) ∖ N^{t} (u)}{N^{t + 1} (u) \cup N^{t} (u)}, \end{matrix}

(2)

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:

\begin{matrix} E_{s} = \frac{E_{rm} (u)}{E_{in} (u)} . \end{matrix}

(3)

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 nodes $n 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 \in 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 Algorithm 1. 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 graph $G (V, E)$

Output: a dominate set D

(1) $D = Ø; L e n = | V |$

(2) For each $v \in V$

(3) $c o l o r (v) = W H I T E$ ;

(4) End for

(5) For $i = 1,2, \dots, 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) For each $v \in 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 \cup 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 Algorithm 2. 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 graph $G (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, \dots, 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 via GRAY 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 of all the BLACK nodes

(13) For each $v \in V$

(14) If $c o l o r (v) = G R A Y$

(15) For each $u \in 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 \geq 2$

(21) Choose any $u \in 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 Algorithm 3. 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 node v;

a connected graph $G (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) \cup$ 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 from $5 * 5$ to $1000 * 1000$ m² 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 m²
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 Figure 2. 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 Figure 3. 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 Figure 4. 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 Figure 5. 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.

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgments

This work was supported by GRRC program of Gyeonggi Province [(GRRCSUWON2014-B1) Cooperative Recognition and Response System Based on Tension Sensing] and also supported by Shandong Provincial Natural Science Foundation (ZR2014FL022), China.

References

Jang

H.-C.

Lien

Y.-N.

Tsai

T.-C.

Rescue information system for earthquake disasters based on MANET emergency communication platform

Proceedings of the ACM International Wireless Communications and Mobile Computing Conference (IWCMC ′09)

June 2009

Leipzig, Germany

623 627

10.1145/1582379.1582514

2-s2.0-70450237755

Ephremides

Wieselthier

J. E.

Baker

D. J.

A design concept for reliable mobile radio networks with frequency hopping signaling

Proceedings of the IEEE 1987 75 1 56 73

10.1109/proc.1987.13705

2-s2.0-0023092944

Clark

B. N.

Colbourn

C. J.

Johnson

Unit disk graphs

Discrete Mathematics 1990 86 1–3 165 177

10.1016/0012-365x(90)90358-o

MR1088569

2-s2.0-0000839639

Zheng

Sun

S.-X.

Huang

T.-Y.

Constructing distributed connected dominating sets in wireless ad hoc and sensor networks

Journal of Software 2011 22 5 1053 1066

10.3724/sp.j.1001.2011.00586

MR2830104

2-s2.0-79959758235

Dai

An extended localized algorithm for connected dominating set formation in ad hoc wireless networks

IEEE Transactions on Parallel and Distributed Systems 2004 15 10 908 920

10.1109/TPDS.2004.48

2-s2.0-17244373061

Wan

P.-J.

Alzoubi

K. M.

Frieder

Distributed construction of connected dominating set in wireless Ad Hoc networks

Mobile Networks and Applications 2004 9 2 141 149

10.1023/b:mone.0000013625.87793.13

2-s2.0-1642408650

Thai

M. T.

Wang

C.-W.

Wan

P.-J.

D.-Z.

On greedy construction of connected dominating sets in wireless networks

Wireless Communications and Mobile Computing 2005 5 8 927 932

10.1002/wcm.356

2-s2.0-29144524581

Wang

Xiao

A survey of energy-efficient scheduling mechanisms in sensor networks

Mobile Networks and Applications 2006 11 5 723 740

10.1007/s11036-006-7798-5

2-s2.0-33745902546

Shukla

K. K.

Sah

Construction and maintenance of virtual backbone in wireless networks

Wireless Networks 2013 19 5 969 984

10.1007/s11276-012-0512-6

2-s2.0-84879800653

10.

Wang

Min

On the construction of stable virtual backbones in mobile ad-hoc networks

Proceedings of the 24th IEEE International Performance, Computing, and Communications Conference (IPCCC ′05)

April 2005

355 362

2-s2.0-28444435197

11.

Sheu

P.-R.

Tsai

H.-Y.

Lee

Y.-P.

Cheng

J.-Y.

On calculating stable connected dominating sets based on link stability for mobile ad hoc networks

Tamkang Journal of Science and Engineering 2009 12 4 417 428

2-s2.0-74349120681

12.

Dai

Gao

Stojmenovic

On calculating power-aware connected dominating sets for efficient routing in ad hoc wireless networks

Journal of Communications and Networks 2002 4 1 59 70

10.1109/JCN.2002.6596934

2-s2.0-0038735958

13.

Ramalakshmi

Radhakrishnan

Improving route discovery using stable connected dominating set in MANETS

International Journal on Applications of Graph Theory in Wireless Ad Hoc Networks and Sensor Networks 2012 4 1 15 25

10.5121/jgraphoc.2012.4102

14.

Ramrekha

T. A.

Talooki

V. N.

Rodriguez

Politis

Energy efficient and scalable routing protocol for extreme emergency ad hoc communications

Mobile Networks and Applications 2012 17 2 312 324

10.1007/s11036-011-0336-0

2-s2.0-84861805176

15.

Wang

Liu

Das

S. K.

Energy-efficient dominating tree construction in wireless ad hoc and sensor networks

Distributed Computing and Networking 2008

Berlin, Germany

Springer

558 569

16.

Papavassiliou

A mobility-based clustering approach to support mobility management and multicast routing in mobile ad-hoc wireless networks

International Journal of Network Management 2001 11 6 387 395

10.1002/nem.415

2-s2.0-0035507897

17.

Wang

Min

On the construction of stable virtual backbones in mobile ad-hoc networks

Proceedings for the 24th IEEE International Performance, Computing, and Communications Conference (IPCCC ′05)

April 2005

355 362

2-s2.0-28444435197

18.

Revathi

Rangaswamy

T. R.

Efficient flooding and local route repair using stable connected dominating set for mobile ad hoc networks

Asian Journal of Scientific Research 2014 7 1 102 109

10.3923/ajsr.2014.102.109

2-s2.0-84896840277

19.

Chang

Y.-L.

Hsu

C.-C.

Routing in wireless/mobile ad-hoc networks via dynamic group construction

Mobile Networks and Applications 2000 5 1 27 37

10.1023/a:1019175605040

2-s2.0-0033743014

Improved Route Discovery Based on Constructing Connected Dominating Set in MANET

Abstract

1. Introduction

2. Related Work

2.1. Network Model and Related Definition

Definition 1 (unit disk graph (UDG)).

Definition 2 (dominating set (DS)).

Definition 3 (connected dominating set (CDS)).

2.2. Related Works on Finding MCDS

3. Forming and Fast Repairing SoN-MCDS

3.1. The Definition of ST ( u )

Definition 4 (the mobility of a node).

Definition 5 (the energy metric of a node).

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

3.2.1. Phase One: Constructing SoN-DS

Rule 1.

Rule 2.

Rule 3.

Algorithm 1: Forming SoN-DS.

3.2.2. Phase Two: Constructing SoN-MCDS

Algorithm 2: Forming SoN-MCDS.

3.2.3. Phase Three: Repairing SoN-MCDS Locally

Algorithm 3: Repairing SoN-MCDS.

4. Route Discovery Using SoN-MCDS

5. Simulation and Analysis

5.1. Simulation Settings

5.2. Result Analysis

6. Conclusion

Footnotes

Conflict of Interests

Acknowledgments

References

3.1. The Definition of $ST (u)$