Article Preview
Top1. 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.