Download (direct link):
Although clustering protocols can be seen as a means of controlling the topology of the network by organizing its nodes into a multilevel hierarchy, a clustering algorithm does not fulfill our informal definition of topology control since typically the transmit power of the nodes is not modified. In other words, a clustering algorithm is concerned with hierarchically organizing the network units assuming the nodes’ transmitting range is fixed, while a topology control protocol is concerned with how to modify the nodes’ transmitting ranges in such a way that a communication graph with certain properties is generated.
3.3 A Taxonomy of Topology Control
As the informal definition of topology control introduced in the previous section outlines, many different techniques can be classified as topology control mechanisms. In this section, we try to organize these diverse approaches to the topology control problem in a coherent taxonomy. Our taxonomy of topology control techniques is depicted in Figure 3.4.
First, we distinguish between homogeneous CTR and nonhomogeneous topology control. In the former case, all the network nodes must use the same transmitting range r, and the topology control problem reduces to the simpler problem of determining the minimum value of r such that a certain networkwide property is satisfied. This value of r is known as the critical transmitting range (CTR), since using a range smaller than r would compromise the desired networkwide goal. In nonhomogeneous topology control, nodes are allowed to choose different transmitting ranges (subject to the condition that the chosen range does not exceed the maximum range).
The homogeneous case is by far the simplest formulation of the topology control problem. Nevertheless, it has attracted the interest of many researchers in the field, probably
Homogeneous (the CTR)
RA and Energy-efficient
Figure 3.4 A taxonomy of topology control techniques.
because, owing to its simplicity, deriving clean theoretical results in this context is a challenging but feasible task. Chapters 4, 5, and 6 will be devoted to homogeneous topology control.
Nonhomogeneous topology control is classified into three categories, depending on the type of information that is used to compute the topology.
In location-based approaches, it is assumed that the most accurate information about node positions (the exact node location) is known. This information is either used by a centralized authority to compute a set of transmitting range assignments that optimizes a certain measure (this is the case of the Range Assignment problem and its variants), or it is exchanged between nodes and used to compute an ‘almost optimal’ topology in a fully distributed manner (this is the case of protocols for building energy-efficient topologies for unicast or broadcast communication). Typically, location-based approaches assume that network nodes, or at least a significant fraction of them, are equipped with GPS receivers. Location-based topology control techniques are described in Chapters 7 and 8 (centralized approach) and in Chapter 10 (distributed approach).
In direction-based approaches, it is assumed that nodes do not know their position but they can estimate the relative direction of their neighbors. This approach to topology control is discussed in Chapter 11.
In neighbor-based techniques, nodes are assumed to have access to a minimal amount of information regarding their neighbors, such as their ID, and to be able to order them according to some criterion (e.g., distance, or link quality). Neighbor-based techniques are probably the most suitable for application in mobile ad hoc networks, and are discussed in details in Chapter 12.
A final distinction is between per-packet and periodical topology control. In the former approach, every node maintains a list of efficient2 neighbors and, for each such neighbor v, the transmit power to be used when sending packets to v. Thus, the choice of the transmit
2With efficient, we mean here either energy efficient, or capacity efficient, or both.
power to use is done on a per-packet basis: when the packet is destined to a certain neighbor v, the appropriate power P(v) is set, and the packet is transmitted.
Per-packet topology control usually relies on quite accurate information on node locations, and it is typically applied in combination with location-based or direction-based topology control. A shortcoming of this technique is that it is rather demanding from a technological point of view, since it requires that the transmit power is changed very frequently (for an in-depth discussion of this issue, see Chapter 14). For this reason, simpler periodical techniques have been proposed. In this approach to topology control, every node maintains a list of efficient neighbors; however, differing from per-packet techniques, a node uses a single transmit power (the so-called broadcast power) to communicate with all the neighbors. This power can be intended as the higher of the transmit powers needed to reach the neighbors in the list. Periodically, the broadcast power level setting used by the node is updated, in response to node mobility and/or neighbor failures. As discussed in Chapter 13, periodical topology control is very suitable for application in mobile ad hoc networks.