An Optimal CDS Construction Algorithm with Activity Scheduling in Ad Hoc Networks

Abstract

A new energy efficient optimal Connected Dominating Set (CDS) algorithm with activity scheduling for mobile ad hoc networks (MANETs) is proposed. This algorithm achieves energy efficiency by minimizing the Broadcast Storm Problem [BSP] and at the same time considering the node's remaining energy. The Connected Dominating Set is widely used as a virtual backbone or spine in mobile ad hoc networks [MANETs] or Wireless Sensor Networks [WSN]. The CDS of a graph representing a network has a significant impact on an efficient design of routing protocol in wireless networks. Here the CDS is a distributed algorithm with activity scheduling based on unit disk graph [UDG]. The node's mobility and residual energy (RE) are considered as parameters in the construction of stable optimal energy efficient CDS. The performance is evaluated at various node densities, various transmission ranges, and mobility rates. The theoretical analysis and simulation results of this algorithm are also presented which yield better results.

Academic Editor:Jaesoo Yoo

Department of Information Science & Technology, Anna University, Chennai 600025, India

Received 18 December 2014; Revised 5 April 2015; Accepted 15 April 2015; 27 May 2015

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

Mobile ad hoc networks appear in a wide variety of applications such as the military, disaster relief, surveillance, sensing, and monitoring. Mobile ad hoc network (MANET) is a special kind of wireless network environment. It is different from the traditional wireless networks. Ad hoc network is a collection of autonomous and arbitrarily located wireless nodes. It is an infrastructure less network with dynamic topology, limited link bandwidth, variation in links, node capabilities, and energy-constrained resources. The nodes need to be more intelligent as they have to act as sender, receiver, and intermediate forwarder. Because of dynamic topology they frequently advertise the control information using a simple flooding. Simple flooding leads to Broadcast Storm Problem [1]. Broadcast Storm refers to the problem of exhausting the limited resources of the network due to excessive transmission of packets in the network. Considering this environment, several routing protocols have been proposed in order to find out and maintain the multihop route with reliability.

Generally ad hoc routing protocols in MANETs are classified into two types, namely, reactive and proactive. In proactive (table driven) routing protocols like DSDV [2] and OLSR [3] routing information in the network to update the tables is periodically broadcast. In case of on-demand (reactive) ad hoc routing protocols such as DSR [4] and AODV [5] simple flooding is used in route discovery procedure by broadcasting route request (RREQ) packets to the network. Generally in MANETs flooding is also used for alarm signals, paging , and so forth. However reactive routing protocols do not involve flooding of data packets but flooding of control packets takes place. Simple flooding consumes energy of the nodes and bandwidth of the network and also leads to congestion in the network which is called Broadcast Storm Problem.

In simple flooding a host on receiving a broadcast message for the first time will rebroadcast the message into network. A straightforward approach of simple flooding in spite of the fact that size of control packets is small suffers from the Broadcast Storm Problem which leads to the following problems [1].

(1) Redundant Rebroadcasts. When a mobile host decides to rebroadcast a broadcast message to its neighbours, all its neighbours already have the message.

(2) Contention for Medium. After a mobile host broadcasts a message, if many of its neighbours decide to rebroadcast the message, then they contend with each other.

(3) Collision. Collisions are more likely to occur due to lack of efficient back-off mechanism.

The effect of the Broadcast Storm Problem can be reduced efficiently and effectively using Connected Dominating Set (CDS). A Connected Dominating Set is constructed assuming the MANET as a graph, generally unit disk graph [6] for better approximation. CDS is analogous to the backbone network of traditional wired networks. The activity of broadcasting is confined to the nodes of CDS. The smallest possible CDS is called Minimum Connected Dominating Set (MCDS) and the problem of constructing MCDS is an NP hard problem. Many standard methods exist in the literature to construct the Minimum Connected Dominating Set [7-23]. Each has its own merits and demerits. Activity scheduling can be used to prolong the lifetime of the network by rotating the role of various nodes [24]. In this paper we propose an energy efficient optimal CDS algorithm with activity scheduling. Scheduling between the similar neighbourhood backbone nodes (dominators) improves the energy efficiency at the same time. Here the activity scheduling is distributed and synchronous which suits much MANETs. It has also less message complexity because only the dominator nodes involve scheduling locally.

The rest of the paper is organized as follows: The definitions, mathematical calculations, and notations used in this paper are given in Section 2. The existing solutions are reviewed in Section 3. The proposed work is discussed in Section 4. The performance analysis and simulation results are shown in Section 5. The conclusion and future work are provided in Section 6.

2. Definitions, Mathematical Calculations, and Notations

Some important definitions, mathematical equations, and the notations used in this work are discussed here.

2.1. Definitions

[figure omitted; refer to PDF] is a unit disk graph [6] which represents ad hoc wireless network. " [figure omitted; refer to PDF] " is the set of mobile nodes in the network and " [figure omitted; refer to PDF] " represents all the links in the network. We assume that all the nodes are deployed in a 2-D plane and their maximum transmission range is the same initially.

Definition 1.

Any node in an UDG is adjacent to at most five independent nodes.

Definition 2.

A dominator is a node which rebroadcasts the messages in the network. Generally it is called a BLACK node.

Definition 3.

A Dominatee is node which listens to the broadcast message from dominator node. It will not rebroadcast the message. Usually it is called a GREY node.

Definition 4.

A dominating set (DS) of a graph [figure omitted; refer to PDF] is a subset of " [figure omitted; refer to PDF] " such that each node in " [figure omitted; refer to PDF] " is adjacent to at least one node in dominating set.

Definition 5.

A Connected Dominating Set (CDS) " [figure omitted; refer to PDF] " of [figure omitted; refer to PDF] is a dominating set of [figure omitted; refer to PDF] which induces a connected subgraph of [figure omitted; refer to PDF] .

Definition 6.

Minimum Connected Dominating Set (MCDS) is a CDS with minimum cardinality.

2.2. Mathematical Calculations for Energy

The energy calculations and equations used in this work are described here. All calculations are in joules. In the network, only the energy of dominator nodes is considered because they consume more energy when compared to the Dominatees. Here dominators consume more power than Dominatees because the set of dominators acts as the backbone. Moreover there are many power consuming roles performed by dominators. First a dominator has to rebroadcast the messages in its transmission range. Second it has to keep track of its connectors to the other dominators. Third it has to maintain a table for list of active neighbours. Fourth it has to perform local repairs. Finally it has to perform activity scheduling with its counterparts. All these indulge in high message exchange and in turn energy consumption.

Moreover the Dominatees are considered to be in promiscuous mode in the case of exchanging control packets alone where they consume very low power to receive the control messages. We considered only the transmission of control packets and not data packets. The Dominatees do not have much role in the construction of the CDS and hence throughout the construction phase Dominatees remain in promiscuous mode. The power consumption at various modes is shown in Table 3. Equations (4), (5), and (6) give a clear picture of how energy is consumed for each bit. When compared to the rate at which energy is depleted in the dominators, the rate at which energy is depleted in the Dominatees is negligible.

In order to increase the lifetime of the dominator as well as network we have performed the activity scheduling to balance the energy consumption. At the same time we can make the network fault tolerant to some extent.

The dominator node's energy " [figure omitted; refer to PDF] " is a function of the residual energy [figure omitted; refer to PDF] and dissipated energy [figure omitted; refer to PDF] as given in (1) and the energy dissipation rate [figure omitted; refer to PDF] given in (2): [figure omitted; refer to PDF] The dissipation rate at a random time [figure omitted; refer to PDF] where [figure omitted; refer to PDF] = energy of node [figure omitted; refer to PDF] at time [figure omitted; refer to PDF] and [figure omitted; refer to PDF] = energy of node [figure omitted; refer to PDF] at time [figure omitted; refer to PDF] .

Let the initial energy of the dominator be " [figure omitted; refer to PDF] ." Once the dominator starts functioning, the energy is consumed and the available energy is reduced. The energy available at a particular instant of time is called residual energy [figure omitted; refer to PDF] . Let " [figure omitted; refer to PDF] " be the initial duration for which the dominator has functioned. After the time duration " [figure omitted; refer to PDF] " the residual energy available at the dominator is computed as in [figure omitted; refer to PDF] where " [figure omitted; refer to PDF] " is the residual energy of the dominator and " [figure omitted; refer to PDF] " is the energy dissipated during duration [figure omitted; refer to PDF] .

The dissipated energy [figure omitted; refer to PDF] is calculated as follows.

Let " [figure omitted; refer to PDF] " be the energy required to transmit a bit and let " [figure omitted; refer to PDF] " be the energy required to receive a bit. Let " [figure omitted; refer to PDF] " be the energy consumed during the promiscuous mode of operation in one time unit. " [figure omitted; refer to PDF] " is nearly half of " [figure omitted; refer to PDF] " and " [figure omitted; refer to PDF] " is one-tenth of " [figure omitted; refer to PDF] ." Let " [figure omitted; refer to PDF] " be the number of bits transmitted during " [figure omitted; refer to PDF] " and let " [figure omitted; refer to PDF] " be the number of bits received during " [figure omitted; refer to PDF] ." The depleted energy during duration " [figure omitted; refer to PDF] " is computed as in [figure omitted; refer to PDF] For the subsequent time intervals of duration " [figure omitted; refer to PDF] " the available energy is computed as in [figure omitted; refer to PDF] where [figure omitted; refer to PDF] is the residual energy available at a particular instant in time.

The overall remaining energy of the backbone network is computed as in [figure omitted; refer to PDF] where [figure omitted; refer to PDF] The overall residual energy of the backbone network.

[figure omitted; refer to PDF] is calculated at regular intervals, if this ratio for the dominator becomes less than the threshold ( [figure omitted; refer to PDF] ) then it will choose another equivalent node and performs activity scheduling. Here in this algorithm we have put TH as 10% of [figure omitted; refer to PDF] because of energy requirement. We have simulated the network with various values of threshold TH (5%, 10%, 15%, and 20%) of [figure omitted; refer to PDF] and observed that when TH = 10% of [figure omitted; refer to PDF] maintains the tradeoff between network lifetime and message cost. When TH = 20% of [figure omitted; refer to PDF] then frequent disconnections occur which result in high message cost and low network lifetime. When TH = 5% of [figure omitted; refer to PDF] then network lifetime increases but the dominator node will become unavailable because the node's energy will completely drain out. The results are shown in Figure 15. Here the network is simulated with 200 nodes at various transmission ranges.

So threshold is kept as 10% of [figure omitted; refer to PDF] .

That is, [figure omitted; refer to PDF]

[figure omitted; refer to PDF] ratio is given by [figure omitted; refer to PDF] Generally, [figure omitted; refer to PDF] .

2.3. Notations

The notations used in this work are given in the Notations section:

[figure omitted; refer to PDF] : : the degree of the node that has highest number of neighbours in the graph,

: [figure omitted; refer to PDF] : harmonic function,

: [figure omitted; refer to PDF] : the Asymptotic upper bound of a function,

: [figure omitted; refer to PDF] : the Asymptotic lower bound of a function,

: [figure omitted; refer to PDF] : tight bound, that is, both upper and lower bounds are of the same order,

: [figure omitted; refer to PDF] : unit disk graph,

: [figure omitted; refer to PDF] : number of vertices (nodes),

: [figure omitted; refer to PDF] : number of edges (links),

: [figure omitted; refer to PDF] : energy of a dominator,

: [figure omitted; refer to PDF] : transmission energy of dominator,

: [figure omitted; refer to PDF] : receiving energy of dominator,

: [figure omitted; refer to PDF] : energy required in promiscuous mode,

: [figure omitted; refer to PDF] : 1-hop neighbors,

: [figure omitted; refer to PDF] : 1-hop neighbor list of node [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] ,

: [figure omitted; refer to PDF] : random time interval,

: [figure omitted; refer to PDF] : small time interval used for activity scheduling,

: [figure omitted; refer to PDF] : null set (or) empty set,

: [figure omitted; refer to PDF] : number of nodes in the network,

: [figure omitted; refer to PDF] : time duration,

: [figure omitted; refer to PDF] : the residual energy of the dominator,

: [figure omitted; refer to PDF] : current residual energy,

: [figure omitted; refer to PDF] : the energy dissipated during duration " [figure omitted; refer to PDF] ,"

: [figure omitted; refer to PDF] : the optimal value,

: [figure omitted; refer to PDF] : size of MCDS.

3. Literature Survey

3.1. Existing Solutions

There are various solutions to alleviate this Broadcast Storm Problem [1]. Some important solutions are probability based scheme, area based scheme, counter based scheme, neighbor knowledge based scheme, and CDS based scheme [1, 7-23, 25-27]. However except CDS based scheme none of these schemes are able to form the virtual backbone network. Connected Dominating Set (CDS) [7-23] belongs to graph based method. It can be used as a virtual backbone or spine of wireless ad hoc networks. CDS provides efficiency not only in broadcasting but also in multicasting and power management. Most of the above CDS algorithms aimed at small size of CDS but not considered the lifetime of CDS. Our algorithm considers both the size of CDS and lifetime of CDS. Generally they are classified into global, quasi-global, local, quasi-local ones based on the type of information it gathers. Generally the CDS construction algorithms are classified into two types: centralized and distributed.

3.1.1. Centralized CDS Algorithms

Centralized algorithms require entire network topology (global) of the MANET. They produce small sized CDS and better performance ratio when compared to distributed CDS algorithms. But they are prone to the problems caused by the mobility of nodes. Guha and Khuller [10] propose two polynomial time algorithms to construct a CDS in a general graph [figure omitted; refer to PDF] . These algorithms are greedy and centralized. The first one has an approximation ratio of [figure omitted; refer to PDF] , where " [figure omitted; refer to PDF] " is a harmonic function and " [figure omitted; refer to PDF] " is the degree of the node that has the highest number of neighbours in [figure omitted; refer to PDF] . Here a spanning tree is developed with maximum degree node as root. The nonleaf nodes in the tree forms the CDS. The second algorithm constructs a Steiner tree that connects all dominator (BLACK) nodes to form CDS. The size of CDS is at most [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] is the size of an optimal MCDS. The message complexity is [figure omitted; refer to PDF] and time complexity is also [figure omitted; refer to PDF] . Alzoubi et al. [14] propose a one-step greedy approximation algorithm with performance ratio at most [figure omitted; refer to PDF] . Butenko et al. [16] propose a two-phase algorithm; in first phase Maximum Independent Set (MIS) is constructed and second phase forms the CDS based on Steiner tree with minimum number of Steiner nodes. It has a performance ratio of [figure omitted; refer to PDF] . Cheng et al. [11] proposed a three-phase algorithm (centralized) to construct MCDS in UDG. It has time complexity of [figure omitted; refer to PDF] and message complexity of [figure omitted; refer to PDF] . Stojmenovic et al. [17] proposed a pruning based CDS construction. It has time complexity of [figure omitted; refer to PDF] and message complexity of [figure omitted; refer to PDF] . In centralized solutions mobility is a concern. Due to mobility topology changes which reflect in the frequent update cost. In our work we follow a distributed approach for the construction of the CDS.

3.1.2. Distributed CDS Algorithms

CDS is constructed based on localized information. These algorithms are further classified into prune based and MIS based ones. Wan et al. [8] proposed a distributed algorithm based on MIS this algorithm has time complexity of [figure omitted; refer to PDF] and message complexity of [figure omitted; refer to PDF] . The resulting CDS has a size of at most [figure omitted; refer to PDF] . Wu and Li's algorithm [7] is very simple. The localized property makes the CDS maintenance easier. The algorithm has a linear performance ratio. This algorithm needs at least two-hop neighbourhood information. It is presented based on the general graph model and it has time complexity of [figure omitted; refer to PDF] and message complexity of [figure omitted; refer to PDF] . They analysed the movement of nodes with an on-model or off-model as leaving from one small management domain and entering another management domain. Das and Bharghavan [12] propose a three-staged algorithm; first stage identifies dominating set, second stage constructs spanning forest, and third stage constructs the spanning tree. It has a time complexity of [figure omitted; refer to PDF] , message complexity of [figure omitted; refer to PDF] , and cardinality is at most [figure omitted; refer to PDF] . Stojmenovic et al. [17] propose a cluster based CDS construction which is based on 2-hop neighbourhood knowledge. Here ranking is based on degree and location of the node. It has time complexity of [figure omitted; refer to PDF] where " [figure omitted; refer to PDF] " is number of edges and message complexity of [figure omitted; refer to PDF] . Khabbazian et al. [22] proposed a local broadcast algorithm based on positional information to construct CDS. It has not focused much on mobility and energy. Sakai et al. [21] proposed a timer based CDS algorithm: two versions, namely, the single initiator CDS algorithm and multi-initiator CDS algorithm. Single initiator algorithm requires less time to construct the small size CDS when compared to multi-initiator. The message complexity for the multi-initiator is very high, but it has not concentrated much on the energy. Li et al. [18] proposed an algorithm with two phases. At the first phase, a Maximal Independent Set (MIS) is formed. At the second phase, a Steiner tree algorithm is used to connect the MIS. Cheng et al. [11] proposed a distributed multileader algorithm. It selects the node with minimum ID in its 1-hop neighbourhood as a leader, builds a tree rooted at each leader, and connect two adjacent trees through one or two nodes. It has a message complexity of [figure omitted; refer to PDF] and time complexity of [figure omitted; refer to PDF] . Tang et al. [28] proposed an energy efficient MCDS algorithm which considered the energy before constructing the MCDS algorithm. It has not much concentrated on mobility and also it is based on reduced neighbour set. Here two stages are used one is CDS construction stage and the second is pruning the CDS to MCDS. It has not concentrated on mobility. Leu and Chang [20] proposed a distributed algorithm for Relaying Mobile Node (RMN) with neighbour table ( [figure omitted; refer to PDF] ) and finally formed a CDS. Most of the above distributed algorithms concentrated either on mobility or on energy but not on both. The complexities of some important basic algorithms are detailed in Table 1.

Table 1: Complexities of various CDS algorithms.

CDS algorithm	Classification	Time complexity	Message complexity
Guha & Khuller	Centralized	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]
Cheng et al.	Centralized	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]
Butenko et al.	Centralized	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]
Alzoubi et al.	Distributed	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]
Wu & Li	Distributed	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]
Das et al.	Distributed	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]
Stojmenovic et al.	Distributed	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]
Dai et al.	Distributed	[figure omitted; refer to PDF]	[figure omitted; refer to PDF]

3.2. Activity Scheduling

The lifetime of a CDS can be significantly increased by allowing some of the neighbouring dominators to sleep intermittently. Activity scheduling must fulfill two requirements: connectivity and coverage and minimization of the energy utilization. There are several sleep scheduling algorithms existing in the literature [24, 29]. These scheduling algorithms are classified into centralized and distributed ones. Distributed scheduling suits mobile ad hoc networks since MANETs lack infrastructure and centralized authority. As in the literature these activity scheduling schemes are further classified into scheduled wakeups and on-demand wakeups [30]. Miller and Vaidya [31] proposed a MAC layer activity scheduling algorithm that uses idle time to sense the channel. Sumi et al. [32] proposed an rotation based activity scheduling for wireless routing protocols where the roles of active and sleep are rotated among the MIS (maximal independent sets) based on power level priority. Kumar et al. [33] proposed a self-scheduling randomized independent scheduling (RIS) which uses synchronized probabilistic method which takes QOS as the metric. Berman et al. [34] proposed scheduling algorithm based on maximization problem to achieve [figure omitted; refer to PDF] -coverage. In much of the above scheduling algorithms almost all nodes involve activity scheduling which result in high message complexity.

Here we have designed an activity scheduling that suits MANETs and also the scheduling happens between dominators only. At a time dominator node may be in active mode (WAKEUP) or promiscuous mode (SLEEP). The dominating node in promiscuous mode sniffs the channel for wakeup signal or sleep signal at regular intervals. Moreover, the proposed activity scheduling algorithm in this paper also considers energy of the dominators.

4. Proposed Work

The proposed energy efficient optimal CDS algorithm with activity scheduling is a distributed algorithm. All nodes are assumed to be of equal energy and equal transmission range initially. Our work considers both energy and mobility of the nodes in the construction of MCDS. In addition, we employ activity scheduling algorithm to spend the energy in a more economical way. The actual algorithm is divided into five phases. Phase 1 deals with dominator election. Phase 2 is about obtaining the connectors across the network and forming redundant CDS. Phases 3 and 4 deal with the construction of optimal CDS algorithm along with activity scheduling among dominators to increase the lifetime of dominators and in turn increase the lifetime of the network. Activity scheduling performs localized scheduling among different dominators with same set of [figure omitted; refer to PDF] list so that the energy of the dominators sustain. Phase 5 is about the maintenance of the CDS at frequent intervals. Generally the CDS is disturbed when a dominator moves away or a new node joins the network or the energy and transmission range of the existing dominator goes below the threshold (TH) value. Here the residual energy and the transmission range of a dominator is calculated at regular intervals because initially all nodes have equal energy. In later states the nodes energy reduces according to (1), (2), (3), and (4).

Algorithm Phase 1 . This phase is the initial phase, executed distributively over the network. Initially all nodes are in WHITE colour and have equal energy and transmission range. So, residual energy (RE) has no role in selecting the dominating set but in later stages of reconstruction/maintenance of CDS, RE plays an important role in selecting energy efficient CDS algorithm (see Algorithm 1).

Algorithm 1

( [figure omitted; refer to PDF] ) Every node exchanges its unique ID and Residual Energy RE value (in case of reconstruction) with in

its transmission range. Obtains 1-hop neighbor list, [figure omitted; refer to PDF] .

( [figure omitted; refer to PDF] ) Every node again exchanges the list [figure omitted; refer to PDF] to obtain the 2-hop neighbor list which also includes the RE energy values

( [figure omitted; refer to PDF] ) A node with highest number of neighbors and lowest ID is elected as dominator initially.

( [figure omitted; refer to PDF] ) Now the dominator changes its color to BLACK and all its neighbors turn to GREY and broadcast this information

( [figure omitted; refer to PDF] ) IF an uncovered WHITE node receives this information from a GREY neighbor

( [figure omitted; refer to PDF] ) THEN it converts itself to GREY and its GREY neighbor to BLACK

( [figure omitted; refer to PDF] ) This procedure is repeated until no WHITE node exist

This phase is illustrated with sample MANET topology as shown in Figure 1. After the exchange of IDs and RE (initially not counted) as shown in Figure 2, the nodes with the highest number of neighbors and lowest IDs form as dominating set, DS (BLACK nodes) = [figure omitted; refer to PDF] as shown in Figure 3. After this algorithm, phase 2 is implemented.

Figure 1: Initial example MANET.

[figure omitted; refer to PDF]

Figure 2: Initial MANET with ID exchange.

[figure omitted; refer to PDF]

Figure 3: MANET after algorithm phase 1 with DS.

[figure omitted; refer to PDF]

Algorithm Phase 2 . This is the connection establishment phase. That is, connectors are selected to connect the DS and to form CDS (see Algorithm 2).

Algorithm 2

( [figure omitted; refer to PDF] ) Every GREY node checks its neighbor list [figure omitted; refer to PDF] for more than one BLACK node.

( [figure omitted; refer to PDF] ) IF (Number of BLACK nodes >1)

( [figure omitted; refer to PDF] ) THEN convert its color to BLACK (connector) and exchange this information

( [figure omitted; refer to PDF] ) ELSE

( [figure omitted; refer to PDF] ) Two nearest GREY nodes of different BLACK nodes turns themselves as

BLACK to establish the connection (these are connectors)

This phase is illustrated here in the example MANET; the GREY nodes with two different BLACK nodes are node 1, node 17, and node 30. Now nodes 1, 17, and 30 will turn to BLACK as shown in Figure 3 and connections are established. After this phase CDS is formed as shown in Figure 4. In the next phase equivalent counterparts are selected locally by these dominators for activity scheduling.

Figure 4: Connectors are selected after algorithm phase 2 and (ID, RE, and [figure omitted; refer to PDF] ) are exchanged to get equivalent node for performing activity scheduling.

[figure omitted; refer to PDF]

Algorithm Phases 3 and 4 . This phase plays a crucial role where it prunes the previous CDS to obtain optimal CDS and it performs activity scheduling (Phase 4) among different adjacent dominators (BLACK nodes) with at most the same [figure omitted; refer to PDF] list to conserve the dominator's energy. Activity scheduling shifts the role of dominators at intervals, [figure omitted; refer to PDF] and their residual energies [figure omitted; refer to PDF] are also calculated as shown in (3). That is, the equivalent adjacent dominators turn on (WAKEUP) and off (SLEEP) alternatively to conserve the energy and increase the lifetime without compromising the delivery ratio. Here a new regular interval based activity scheduling algorithm is designed to suit the mobility of nodes. Here we maintained a trade-off between optimal CDS and number of dominators to perform the activity scheduling (see Algorithms 3 and 4).

Algorithm 3

[figure omitted; refer to PDF] ) Every BLACK node exchanges its [figure omitted; refer to PDF] list in its transmission range

( [figure omitted; refer to PDF] ) All its neighbors exchange their [figure omitted; refer to PDF] list, where [figure omitted; refer to PDF]

( [figure omitted; refer to PDF] ) Every BLACK node performs intersection of [figure omitted; refer to PDF] list with its own [figure omitted; refer to PDF] . That is, ( [figure omitted; refer to PDF] )

( [figure omitted; refer to PDF] ) Nodes with at most similar [figure omitted; refer to PDF] , that is, ( [figure omitted; refer to PDF] ) and (RE > TH) are selected and turned BLACK

( [figure omitted; refer to PDF] ) Perform Activity scheduling (phase 4) between neighboring BLACK nodes at regular time interval [figure omitted; refer to PDF]

( [figure omitted; refer to PDF] ) Black nodes also calculate RE at regular intervals.

( [figure omitted; refer to PDF] ) IF (RE <= TH)

( [figure omitted; refer to PDF] ) THEN

( [figure omitted; refer to PDF] ) Repeat steps ( [figure omitted; refer to PDF] ), ( [figure omitted; refer to PDF] ), ( [figure omitted; refer to PDF] ), ( [figure omitted; refer to PDF] ) & ( [figure omitted; refer to PDF] )

( [figure omitted; refer to PDF] ) ELSE

( [figure omitted; refer to PDF] ) Continue

Algorithm 4

( [figure omitted; refer to PDF] ) Initially all the Adjacent dominators are in active mode

( [figure omitted; refer to PDF] ) Dominator 1 turns itself into WAKEUP, sends SLEEP message to the counterparts and starts the timer TI.

( [figure omitted; refer to PDF] ) After receiving the SLEEP message the adjacent dominators start their own timer with a higher value

and goes in to Promiscuous mode.

( [figure omitted; refer to PDF] ) In promiscuous mode dominators listen to the messages

( [figure omitted; refer to PDF] ) WHILE (RE ≥ TH)

( [figure omitted; refer to PDF] ) BEGIN

( [figure omitted; refer to PDF] ) IF (Message = WAKEUP or Timer = 0)

( [figure omitted; refer to PDF] ) THEN

( [figure omitted; refer to PDF] ) Turns itself to WAKEUP and sends SLEEP message to its counter parts

// this is to balance the energy among the nodes

( [figure omitted; refer to PDF] ) END

These phases are illustrated in Figures 4 and 5. According to the algorithm, all the dominators (BLACK) select the counterparts locally and perform activity scheduling. Here in the MANET node 5 selects node 2 as the counterpart and node 1 selects the union of node 8 and node 24 as counterparts, because their combined [figure omitted; refer to PDF] list is equivalent to the neighbour list of node 1. Similarly node 17 and node 30 are counterparts. Node 18 selects union of node 25 and node 23 as the counterparts. Node 13 has no equivalent node or union of nodes with similar [figure omitted; refer to PDF] list; in this case node 13 will not perform activity scheduling locally until an equivalent node/nodes join. When compared to other nodes node 13 drains out quickly. These cases are handled by maintenance phase. Activity scheduling is performed as shown in Figure 6. Nodes [figure omitted; refer to PDF] perform activity scheduling locally. BLACK slashed lines (active connection) and RED slashed lines (inactive connection) indicate the scheduling. When compared to other algorithms the dominators will not run out of energy and lifetime of the network increases as shown in Figure 5.

Figure 5: CDS with activity scheduling.

[figure omitted; refer to PDF]

Figure 6: The energy efficient optimal CDS maintenance phase after [figure omitted; refer to PDF] time with new nodes 29 and 31. Moved-out node 17, drained-out node 5.

[figure omitted; refer to PDF]

Algorithm Phase 5 . This phase is called maintenance/repair phase. Here the mobility of the node and the residual energy (RE) are considered for maintaining the optimal CDS. Here four cases are considered when a new node joins the network, existing node moves away, existing dominator moves away, and existing dominator runs out of energy. Every dominator executes this phase at frequent [figure omitted; refer to PDF] time intervals. A BLACK (dominator) node turns itself to RED when its energy becomes less than threshold TH; that is, it drains out (see Algorithm 5).

Algorithm 5

( [figure omitted; refer to PDF] ) IF a BLACK node (Dominator) moves away

( [figure omitted; refer to PDF] ) THEN

( [figure omitted; refer to PDF] ) Immediate GREY node with highest [figure omitted; refer to PDF] and RE value is turned BLACK

and execute algorithm phase 4 (activity scheduling)

( [figure omitted; refer to PDF] ) IF a GREY node (Dominatee) moves away

( [figure omitted; refer to PDF] ) THEN

( [figure omitted; refer to PDF] ) No change

( [figure omitted; refer to PDF] ) IF a BLACK node's RE <= TH

( [figure omitted; refer to PDF] ) THEN

( [figure omitted; refer to PDF] ) Turn BLACK node to RED and handover the Dominator status to equivalent counterpart

and execute algorithm phase 4 (activity scheduling)

( [figure omitted; refer to PDF] ) IF a new WHITE node joins the network

( [figure omitted; refer to PDF] ) THEN

( [figure omitted; refer to PDF] ) IF it has BLACK node (dominator) in its range then

( [figure omitted; refer to PDF] ) Convert itself to GREY (dominate)

( [figure omitted; refer to PDF] ) ELSE

( [figure omitted; refer to PDF] ) Convert itself to GREY and its GREY neighbor to BLACK (as connector)

and execute algorithm phase 4 (activity scheduling)

The above phase is illustrated in Figure 6. Here the dominator node 17 moved away so counterpart node 30 has become the BLACK node as shown in Figure 7. Node 5 has drained out and turned itself into RED and exchanged locally. So node 2 has become the dominator as shown in Figure 7. Two new nodes 29 and 31 have joined the network, where node 29 is nearer to the nodes 23 and 25. Node 31 joined network near nodes 11 and 12; now IDs are exchanged locally. Now node 12 will become the additional new dominator; as node 29 is already adjacent to two dominators, it turns itself into GREY as shown in Figure 7. The final optimal repaired CDS [figure omitted; refer to PDF] is shown in Figure 7. Here only the nodes [figure omitted; refer to PDF] perform the activity scheduling.

Figure 7: The final repaired CDS with minimal activity scheduling.

[figure omitted; refer to PDF]

5. Simulation Results

In this section, the simulation results of some energy efficient CDS algorithms are compared with our energy efficient optimal CDS algorithm with activity scheduling. We present simulations that illustrate the results of the algorithm and analyse the behaviour of our algorithm in various scenarios. We run simulations in ns-2 (version 2.34). The simulation parameters are listed in Table 2. Power considerations for the dominator node are given in Table 3. Here in promiscuous mode the dominator listens to its surroundings.

Table 2: Simulation parameters.

Simulator	Ns2 (version 2.34)
Simulation area	1000 × 1000 m
Propagation	Two-ray ground reflection
MAC protocol	IEEE 802.11
Bandwidth	2 Mbps
Traffic	CBR
Transmission range	25~100 meters
Number of nodes	100~450
Maximum speed	5~25 m/sec
Mobility model	Random walk
Broadcast sessions	35
Broadcast rate	0.5-5 pkts/s
Message size	128 bytes
Hello interval	2 sec
Simulation time	60~100 minutes
Number of trials	75

Table 3: Power consumption table.

Parameter (node)	Power consumption (Watts)
Transmission	1000 mW
Receiving	500 mW
Promiscuous mode	100 mW

Various aspects like size of the CDS at various mobility rates, lifetime of the CDS at various mobility rates, and message overhead are observed and compared with existing CDS algorithms. Performance is analysed at sparse as well as dense networks. A sparse network is created with 100 nodes with transmission range of 25 mts at two different speeds 5 mts/s and 10 mts/s. Similarly a dense network is created with 450 nodes with transmission range of 50 mts at two different speeds 5 mts/s and 10 mts/s. A Random walk mobility model is used. The terrain area is about 1000 m × 1000 m. Figure 8 shows the size of CDS versus number of nodes in sparse network with node's transmission range of 25 mts, at node speed of 5 mts/s. Figure 9 shows the size of CDS versus number of nodes in sparse network with node's transmission range of 25 mts, at a node mobility of 10 mts/s. In both cases our algorithm performed well irrespective of speed and obtained optimal CDS size in sparse network when compared to the existing CDS algorithms. Figure 10 shows the size of CDS versus number of nodes in dense network with node's transmission range of 50 mts, at a node mobility of 5 mts/s. Figure 11 shows the size of CDS versus number of nodes in dense network with node's transmission range of 50 mts, at node mobility rate of 10 mts/s. In these cases also our algorithm performed well when compared to other algorithms because of its distributed nature. Figure 12 shows the message overhead versus number of nodes with node's transmission range of 50 mts and speed 10 mts/s. Here our algorithm exchanged optimal number of messages when compared to the existing standard CDS algorithms, where the existing CDS algorithms have not performed activity scheduling, so the CDS repair phase message cost increased. Figure 13 shows the delivery ratio versus number of nodes with transmission range of 25 mts and speed of 10 mts/s. Here also our algorithm performed well when compared to other algorithms. The graph in Figure 14 shows the lifetime of the optimal CDS versus mobility of nodes with node's transmission range of 50 mts. The lifetime of our algorithm is observed at different speeds of nodes 5 mts/s, 10 mts/s, 15 mts/s, and 20 mts/s. The lifetime of our algorithm in case of mobility is also good when compared to the existing standard CDS algorithms because of activity scheduling among neighbouring dominators in phases 3 and 4. So our algorithm is robust, reliable, and fault tolerant. The graph in Figure 15 shows the lifetime of the optimal CDS at various energy threshold values. Here the network is simulated with 200 nodes at various transmission ranges of 50 mts, 25 mts, and 10 mts and at a speed of 5 mts/s with threshold values of 0.05, 0.1, 0.15, and 0.2. The value of threshold at 0.1 gives better results and maintains the tradeoff between network lifetime and message cost.

Figure 8: Number of nodes versus CDS size (transmission range = 25 mts and speed = 5 mts/s).

[figure omitted; refer to PDF]

Figure 9: Number of nodes versus CDS size (transmission range = 25 mts and speed = 10 mts/s).

[figure omitted; refer to PDF]

Figure 10: Number of nodes versus CDS size (transmission range = 50 mts and speed = 5 mts/s).

[figure omitted; refer to PDF]

Figure 11: Number of nodes versus CDS size (transmission range = 50 mts and speed = 10 mts/s).

[figure omitted; refer to PDF]

Figure 12: Number of nodes versus message overhead.

[figure omitted; refer to PDF]

Figure 13: Number of nodes versus delivery ratio (%).

[figure omitted; refer to PDF]

Figure 14: Mobility of nodes (mts/s) versus MCDS lifetime (min).

[figure omitted; refer to PDF]

Figure 15: Lifetime of CDS (min) versus energy threshold values.

[figure omitted; refer to PDF]

6. Conclusion and Future Work

The major advantage of using activity scheduling algorithm is fast convergence and longer life even if CDS nodes move out due to mobility or energy drain. Here the energy of the dominators will not drain out due to activity scheduling. Only the dominator nodes are involved in further communication to establish the backbone and in maintenance of optimal CDS. In future work we will extend this to directed graphs and nodes with directional antennas.

Acknowledgment

The authors express their sincere thanks to Anna University for providing the valuable resources to perform the experiments.

Conflict of Interests

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

References

[1] S. Ni, Y. Tseng, Y. Chen, J. Sheu, "The broadcast storm problem in a mobile ad hoc network," in Proceedings of the 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom '99), pp. 151-162, August 1999.

[2] C. E. Perkins, P. Bhagwat, "Highly dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers," in Proceedings of the Conference on Communications Architectures, Protocols and Applications (SIGCOMM '94), pp. 234-244, 1994.

[3] P. Jacquet, T. Muhlethaler, T. Clausen, A. Laouiti, A. Qayyum, L. Viennot, "Optimized link state routing protocol for ad hoc networks," Hipercom Project , INRIA Roquencourt, Le Chesnay Cedex, France, 2003.

[4] D. B. Johnson, D. A. Maltz, "Dynamic source routing in ad hoc wireless networks," Mobile Computing , vol. 353, of The Kluwer International Series in Engineering and Computer Science, pp. 153-181, Kluwer Academic Publishers, 1996.

[5] C. E. Perkins, E. M. Royer, "Ad-hoc on-demand distance vector routing," in Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications (WMCSA '99), pp. 90-100, February 1999.

[6] B. N. Clark, C. J. Colbourn, D. S. Johnson, "Unit disk graphs," Discrete Mathematics , vol. 86, no. 1-3, pp. 165-177, 1990.

[7] J. Wu, H. Li, "On calculating connected dominating set for efficient routing in ad hoc wireless networks," in Proceedings of the 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, pp. 7-14, 1999.

[8] P.-J. Wan, K. M. Alzoubi, O. Frieder, "Distributed construction of connected dominating set in wireless ad hoc networks," in Proceedings of IEEE Conference on Computer Communications (INFOCOM '02), pp. 1597-1604, June 2002.

[9] F. Dai, J. Wu, "An extended localized algorithm for connected dominating set formation in ad hoc wireless networks," IEEE Transactions on Parallel and Distributed Systems , vol. 15, no. 10, pp. 908-920, 2004.

[10] S. Guha, S. Khuller, "Approximation algorithms for connected dominating sets," Algorithmica , vol. 20, no. 4, pp. 374-387, 1998.

[11] X. Cheng, M. Ding, D. Chen, "An approximation algorithm for connected dominating set in ad hoc networks," in Proceedings of the 1st International Workshop on Theoretical Aspects of Wireless Ad Hoc, Sensor, and Peer-to-Peer, Networks, 2004.

[12] B. Das, V. Bharghavan, "Routing in ad-hoc networks using minimum connected dominating sets," in Proceedings of the IEEE International Conference on Communications (ICC '97), pp. 376-380, Montreal, Canada, June 1997.

[13] L. Ruan, H. Du, X. Jia, W. Wu, Y. Li, K.-I. Ko, "A greedy approximation for minimum connected dominating sets," Theoretical Computer Science , vol. 329, no. 1-3, pp. 325-330, 2004.

[14] K. M. Alzoubi, P. J. Wan, O. Frieder, "Message-optimal connected dominating sets in mobile ad hoc networks," in Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC '02), pp. 157-164, EPFL, June 2002.

[15] M. Min, H. Du, X. Jia, C. X. Huang, S. C. Huang, W. Wu, "Improving construction for connected dominating set with Steiner tree in wireless sensor networks," Journal of Global Optimization , vol. 35, no. 1, pp. 111-119, 2006.

[16] S. Butenko, X. Cheng, C. Oliveira, P. M. Pardalos, "A new heuristic for the minimum connected dominating set problem on ad hoc wireless networks," Re-cent Developments in Cooperative Control and Optimization , pp. 61-73, Kluwer Academic Publishers, 2004.

[17] I. Stojmenovic, M. Seddigh, J. Zunic, "Dominating sets and neighbor elimination based on broadcasting algorithms in wireless networks," in Proceedings of the IEEE Hawaii International Conference on System Sciences (HICSS '01), IEEE, January 2001.

[18] Y. Li, M. T. Thai, F. Wang, C.-W. Yi, P.-J. Wan, D.-Z. Du, "On greedy construction of connected dominating sets in wireless networks," Wireless Communications and Mobile Computing , vol. 5, no. 8, pp. 927-932, 2005.

[19] J. Yu, N. Wang, G. Wang, D. Yu, "Connected dominating sets in wireless ad hoc and sensor networks-a comprehensive survey," Computer Communications , vol. 36, no. 2, pp. 121-134, 2013.

[20] S. Leu, R.-S. Chang, "Simple algorithm for solving broadcast storm in mobile ad hoc network," IET Communications , vol. 5, no. 16, pp. 2356-2363, 2011.

[21] K. Sakai, S. C.-H. Huang, W.-S. Ku, M.-T. Sun, X. Cheng, "Timer-based CDS construction in wireless ad hoc networks," IEEE Transactions on Mobile Computing , vol. 10, no. 10, pp. 1388-1402, 2011.

[22] M. Khabbazian, I. F. Blake, V. K. Bhargava, "Local broadcast algorithms in wireless ad hoc networks: reducing the number of transmissions," IEEE Transactions on Mobile Computing , vol. 11, no. 3, pp. 402-413, 2012.

[23] J. Blum, M. Ding, A. Thaeler, X. Cheng, D.-Z. Du, P. Pardalos, "Connected dominating set in sensor networks and MANETs," Handbook of Combinatorial Optimization , pp. 329-369, Springer, 2004.

[24] T. Yardibi, E. Karasan, "A distributed activity scheduling algorithm for wireless sensor networks with partial coverage," Wireless Networks , vol. 15, no. 6, pp. 213-225, 2009.

[25] B. Williams, T. Camp, "Comparison of broadcasting techniques for mobile ad-hoc networks," in Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking & Computing (MobiHoc '02), pp. 194-205, Lausanne, Switzerland, 2002.

[26] Q. Zhang, D. P. Agrawal, "Dynamic probabilistic broadcasting in MANETs," Journal of Parallel and Distributed Computing , vol. 65, no. 2, pp. 220-233, 2005.

[27] Y. Sasson, D. Cavin, A. Schiper, "Probabilistic broadcast for flooding in wireless mobile ad hoc networks,", no. IC/2002/54, Swiss Federal Institute of Technology, 2002.

[28] Q. Tang, K. Yang, P. Li, J. Zhang, Y. Luo, B. Xiong, "An energy efficient MCDS construction algorithm for wireless sensor networks," EURASIP Journal on Wireless Communications and Networking , vol. 2012, article 83, 2012.

[29] L. Wang, Y. Xiao, "A survey of energy-efficient scheduling mechanisms in sensor networks," Mobile Networks and Applications , vol. 11, no. 5, pp. 723-740, 2006.

[30] A. Keshavarzian, H. Lee, L. Venkatraman, K. Chitalapudi, D. Lal, B. Srinivasan, "Wakeup scheduling in wireless sensor networks," in Proceedings of the 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC '06), pp. 322-333, May 2006.

[31] M. J. Miller, N. H. Vaidya, "A MAC protocol to reduce sensor network energy consumption using a wakeup radio," IEEE Transactions on Mobile Computing , vol. 4, no. 3, pp. 228-242, 2005.

[32] M. R. A. Sumi, M. H. Imtiaz, S. M. M. Al Mamun, M. N. Hassan, "A new approach for designing and analysis of distributed routing algorithm and protocols of wireless ad hoc network," International Journal of Science and Advanced Technology , vol. 1, no. 6, 2011.

[33] S. Kumar, T. H. Lai, J. Balogh, "On k-coverage in a mostly sleeping sensor network," in Proceedings of the 10th Annual International Conference on Mobile Computing and Networking (MobiCom '04), pp. 144-158, Pennsylvania, Philadelphia, Pa, USA, October 2004.

[34] P. Berman, G. Calinescu, C. Shah, A. Zelikovsky, Y. Xiao, Y. Pan, "An efficient energy management in sensor networks," Ad Hoc and Sensor Networks , Nova Science, 2005.