Distributed topology control algorithm based on one- and two-hop neighbors’ information for ad hoc networks
Introduction
An ad hoc network is a group of wireless nodes that communicate over radio. These mobile nodes do not need any infrastructure. These kinds of networks are very flexible and suitable to use in applications such as natural disaster recovery or fast deployment of military units in unpopulated areas. Since the nodes in ad hoc networks are usually battery equipped, they have a limited amount of energy which must be used as efficiently as possible. A complete solution to energy efficiency involves many areas of research, such as hardware, operating systems, networking, and applications [7]. Our work focuses on a mechanism named topology control. The goal of topology control is reducing energy consumption by discarding inefficient links, while still satisfying connectivity. The power required to transmit messages between nodes increases as the exponent α ⩾ 2 [14] of the distance between them. Therefore, compared to direct transmission, a smaller amount of energy can be consumed by a node u if it passes on its messages via a series of intermediate nodes to a node v. The topology control problem can be formalized as follows.
Let the graph G = (V, E) denote the wireless ad hoc networks, where V is the set of ad hoc nodes and E is the set of communication links. Our aim is presenting an algorithm that supplies a connected subgraph Gtc = (V, Etc) of G, where Etc ⊆ E, with the following properties:
A.1 – Connectivity: The main property of subgraph Gtc is connectivity. Two nodes are connected if there is a path between them. If two nodes are connected in G, then they should be connected in Gtc. A.2 – Symmetry: Gtc should contain only bidirectional links, because most routing protocols for ad hoc networks implicitly assume that wireless links are bidirectional. In addition, because of the high overhead needed to handle unidirectional links [11], bidirectional links are preferred. A.3 – Spanner: Graph Gtc is a spanner if the ratio between the minimum power-cost path in Gtc and in G is of a constant order. To study this property, we use the power stretch factor of Gtc (which is defined precisely in Section 4). A.4 – Low degree: Since a node u may cause interference at nodes in its transmission range, a smaller node degree usually reduces the amount of interference. Hence, it is desirable if each node has a small constant bounded degree. If the degree of the nodes has a constant bound, then the number of Gtc’s edges is of the order of the number of its nodes, namely ∣Etc∣ = O(∣V∣). This kind of graph is called a sparse graph. The algorithm itself should have the following attributes: B.1 – Local and fully distributed: Since ad hoc networks have no centralized authority, any node u independently collects the information of its neighbors (at most two-hop neighbors) in G and then determines the edges of Gtc incident in it on the basis of the local information. B.2 – Low-quality information: Since obtaining very accurate information such as node locations is usually expensive, the topology control algorithm should rely on ‘low-quality’ information (e.g. number and identity of neighbor nodes or the distance between nodes).
Many topology control algorithms have been designed for ad hoc networks. The topology control algorithms may be classified as centralized and distributed. In the centralized algorithms (such as [1], [10]), a particular node is responsible for evaluating an optimum network topology based on global information. These algorithms cannot be used on distributed nodes and, therefore, we do not deal with them in this paper. The other class contains distributed algorithms. CBTC(α) [7] is a distributed algorithm in which each node finds the minimum power that ensures it can reach some nodes in every cone of degree α. It has been shown in [7] that if α ⩽ 5π/6 then connectivity is preserved. The basic idea of the COMPOW [12] and CLUSTERPOW [6] approaches is that each node uses the smallest common power required to maintain connectivity. The major disadvantage of COMPOW is its message overhead, since each node has to exchange link state information with other nodes. Several geometry structures such as Gabriel graph [3], relative neighbor graph [16], Yao graph [21], local minimum spanning tree (LMST) [8], and ESPT [18] have been proposed for topology control in wireless ad hoc networks which are produced in a distributed manner. In some structures such as Gabriel graph, relative neighbor graph, Yao graph, and ESPT, the stretch factor is bounded but the node degree is not bounded. On the other hand, in topologies produced by XTC [20] and LMST, the node degree is bounded but the power stretch factors are not bounded. Still in some others, such as OrdYaoGG and SYaoGG graphs [15], the node degree and the power stretch factor are bounded.
Now we introduce the topology control algorithms XTC and Gabriel graph (GG), and we will compare our contribution with them in the next sections.
Let G be a geometrical graph (i.e. the set of G’s nodes are placed on the plane). RNG-based algorithms construct a subgraph of G known as relative neighborhood graph (RNG) [16] by removing all edges (u, v) ∈ G if there exists a node w such that d(u, v) > d(u, w) and d(u, v) > d(v, w), where d(u, v) is the Euclidean distance between u and v. The GG [3] is a special case of RNG, where node w is restricted to the disk with diameter d(u, v).
In [20], the XTC topology control algorithm was introduced exhibiting properties A.1 – A.4 and B.1 and B.2. This algorithm operates on a graph G = (V, E) and produces the topology control graph GXTC = (V, EXTC). The algorithm consists of three steps: neighbor ordering, neighbor order exchange, and link selection. In the first step, each node u establishes a link meter, denoted by ∥uv∥, which indicates the quality of the communication link (u, v) between u and its neighbor v. Then u computes an order ≺u over all its one-hop neighbors in G. All u’s neighbors are sorted decreasingly in ≺u with respect to the link meter values, namely a node w appears before node v in ≺u if ∥uw∥ < ∥uv∥ (this is denoted by w ≺ uv). In the second step, node u exchanges its order with all its one-hop neighbors. In the third step, node u selects a node v as its neighbor in graph GXTC if there exists no node w with w ≺ uv and w ≺ vu.
Section snippets
Proposed algorithm for synchronized nodes
We propose our algorithm, denoted by OTTC algorithm to stand for one- and two-hop topology control algorithm, in this section. Based on this algorithm, as the majority of the existing algorithms, each node receives Hello messages from its one-hop neighbors and then updates its local view when all Hello messages are received. This scheme works correctly if all nodes start at the same time, so we assume that all nodes have synchronized clocks. The OTTC algorithm, similar to the XTC algorithm [20]
AOTTC for asynchronism and mobile nodes
In the previous section, we assumed that all nodes are synchronized and they execute the OTTC algorithm at the same time. Also we implicitly assumed that the nodes are stationary. In practice, the nodes may be asynchronous and there exists a difference among their clocks. Although there exist various solutions [19] to adjust the clocks, they are costly. Also the network topology may change because of mobility and leaving/joining of the nodes. To solve these problems, an extension of the XTC
Performance evaluation
In this section, we present several simulation results to demonstrate the effectiveness of OTTC and AOTTC. The simulation code was implemented within the global mobile simulation (GloMoSim) library [17]. Default radio propagation range for each node is 100 ms; Nodes’ channel bandwidth is set to 2 Mbit/s. Each simulation executed for 300 s of simulation time. All member nodes join at the start of the simulation and remain members throughout the duration of the simulation. We use 15
Conclusion
In this paper, we have presented the OTTC algorithm which features properties A.1 – A.4, B.1 and B.2. It also has several advantages: it is simple, it is based on low-quality information (e.g. distance between nodes), it is lightweight (only 2n messages are exchanged in the network). Compared to similar topology control algorithms, OTTC has a main feature: in addition to one-hop neighbors’ information, OTTC uses two-hop neighbors’ information which helps to reduce the transmission radius and
References (21)
- et al.
An SPT-based topology control algorithm for wireless ad hoc networks
Computer Communications
(2006) - M. Burkhart, P.V. Rickenbach, R. Wattenhofer, A. Zollinger, Does topology control reduce interference? in: Proc. of ACM...
- M. Dyer, J. Beutel, L. Thiele, S-XTC: a signal-strength based topology control algorithm for sensor networks, in: Proc....
- et al.
A new statistical approach to geographic variation analysis
Systematic Zoology
(1969) - et al.
Handbook of Discrete and Computational Geometry
(1997) - D.B. Johnson, D.A. Maltz, Y. Hu, J. Jetcheva, The dynamic source routing protocol for mobile ad hoc networks (DSR),...
- V. Kawadia, P. Kumar, Power control and clustering in ad hoc networks, in: Proc. of the IEEE Infocom, San Francisco,...
- L. Li, J.Y. Halpern, P. Bahl, Y.-M. Wang, R. Wattenhofer, Analysis of a cone-based distributed topology control...
- N. Li, J. Hou, L. Sha, Design and analysis of an mst-based topology control algorithm, in: Proc. of the IEEE Infocom...
- X. Li, P. Wan, Y. Wang, O. Frieder, Sparse power efficient topology for wireless networks, in: Proc. of the IEEE Hawaii...
Cited by (22)
Optimized power control and efficient energy conservation for topology management of MANET with an adaptive Gabriel graph
2018, Computers and Electrical EngineeringAutonomous Gateway Mobility Control for Heterogeneous Drone Swarms: Link Stabilizer and Path Optimizer
2022, IEICE Transactions on CommunicationsAn Adaptive Yao-based topology control algorithm for wireless ad-hoc networks
2020, 2020 10h International Conference on Computer and Knowledge Engineering, ICCKE 2020Applied fuzzy heuristics for automation of hygienic drinking water supply system using wireless sensor networks
2020, Journal of SupercomputingA New Mobility Control Approach for Improved Route Availability in Mobile Ad Hoc Networks
2019, Arabian Journal for Science and Engineering