A Binary Search Algorithm to Determine the Minimum Transmission Range for Minimum Connected Dominating Set of a Threshold Size in Ad Hoc Networks

A Binary Search Algorithm to Determine the Minimum Transmission Range for Minimum Connected Dominating Set of a Threshold Size in Ad Hoc Networks

Natarajan Meghanathan (Jackson State University, USA)
DOI: 10.4018/IJWNBT.2020070101

Abstract

The set of nodes constituting a minimum connected dominating set (MCDS) in a wireless ad hoc network (WANET) could be considered as the minimum number of nodes that are required to forward a broadcast message so that the message reaches all the nodes in the network. With regards to MCDS construction, we notice that smaller the transmission range for the nodes, the larger the size of the MCDS and vice-versa. Hence, from an energy efficiency point of view, it is imperative to determine the minimum transmission range (we assume uniform transmission range for all the nodes) that would be needed to construct a MCDS of a certain threshold size in WANETs. In this pursuit, we propose a binary search algorithm of logarithmic time complexity to determine the minimum uniform transmission range that would be sufficient to obtain a connected network and construct a MCDS whose size is within a threshold.
Article Preview
Top

1. Introduction

A wireless ad hoc network (WANET) is a network of wireless devices (nodes) formed in an impromptu fashion without a preexisting infrastructure (no routers; Siva Ram Murthy and Manoj, 2004). Two nodes in a WANET could directly communicate if they are within the transmission range of each other. In this paper, we assume that all nodes in a WANET operate at the same/uniform transmission range. A message transmitted by a node reaches all the nodes within its transmission range. The energy spent to transmit a message is proportional to the distance (typically to the square or the fourth power of the distance, referred to as the path loss exponent) over which the message is transmitted (Xiao et al., 2014). Deng et al (2007) observed that the per-hop uniform transmission range for maximal energy efficiency decreases with increase in node density (rather than network coverage) for path loss exponent of two but remains almost constant for path loss exponent of four. Also, a smaller transmission range need not necessarily reduce energy consumption as it comes with the overhead of involving several relay nodes that unnecessarily lose energy to receive a packet (Chen et al., 2003).

A common operation performed in a WANET is the broadcast operation in which a message transmitted by a node reaches the rest of the nodes in the network (Siva Ram Murthy and Manoj, 2004). Since nodes operate with a limited transmission range, a WANET would need one or more nodes to forward a broadcast message in their respective neighborhoods (the neighborhood of a node is the set of nodes that are within its transmission range). A minimum connected dominating set (MCDS) is a data structure that is typically considered to represent the minimum number of nodes needed to forward a broadcast message (Guha & Khuller, 1998). A connected dominating set (CDS) is a set of nodes in the network such that every node in the network is either in the CDS or is a neighbor of at least one node in the CDS (Guha & Khuller, 1998). A CDS is thus considered to create a virtual backbone for routing in wireless networks (Ephremides et al., 1987). Note that lower the transmission range for the nodes, the larger the number of nodes that need to be part of the MCDS (referred to as the MCDS node size) and vice-versa.

Traditionally, the problems of assigning an optimal transmission range and identifying an efficient communication topology are considered separately. Some of the recent works in the literature (below, we list some sample works) are taking a paradigm shift from this traditional approach by considering both range assignment and communication topology selection as a joint optimization problem, and our approach in this paper is also in this direction. Khalily-Dermany (2019) developed a formulation to view range assignment and routing as a joint optimization problem and came up with a distributed algorithm. Tran et al. (2019) proposed the set of CDS nodes as the search space for identification of intermediate nodes for dynamic channel selection and routing in cognitive radio vehicular ad hoc networks. Overlay-based broadcast (Nikolov & Haas, 2015) has been proposed for controlled flooding in highly dense ad hoc networks of low node mobility. To the best of our knowledge, no work in the literature has focused on determining the minimum transmission range that would be sufficient to obtain a CDS of certain size (representing the nodes that could forward a broadcast message) in ad hoc networks.

Complete Article List

Search this Journal:
Reset
Open Access Articles
Volume 10: 2 Issues (2021): Forthcoming, Available for Pre-Order
Volume 9: 2 Issues (2020)
Volume 8: 2 Issues (2019)
Volume 7: 2 Issues (2018)
Volume 6: 2 Issues (2017)
Volume 5: 1 Issue (2016)
Volume 4: 3 Issues (2015)
Volume 3: 4 Issues (2014)
Volume 2: 4 Issues (2012)
Volume 1: 4 Issues (2011)
View Complete Journal Contents Listing