Download (direct link):
As compared to CBTC, KNeigh displays about 20% better performance in terms of energy cost, and slightly better performance in terms of average physical node degree. The reason for this performance gap in favor of KNeigh stems from the fact that some nodes in CBTC (especially nodes lying on the boundary of the deployment region) use relatively high transmit power to reach at least one neighbor ‘in every direction’: on one hand, this feature of CBTC ensures that the generated topology preserves worst-case connectivity; on the other hand, it produces a relatively less energy- and interference-efficient topology as compared to KNeigh.
12.3 The XTC Protocol
The XTC protocol presented in (Wattenhofer and Zollinger 2004) is a neighbor-based topology control algorithm that, contrary to KNeigh, preserves worst-case connectivity. This better performance in terms of connectivity with respect to KNeigh is counterbalanced by a worse performance in terms of physical node degree, which can be as high as n — 1 (see Theorem 9.3.3). We recall that KNeigh generates graphs with physical node degree upper bounded by k, where k e D(log n).
In a certain sense, XTC can be considered as a generalization of KNeigh: similar to KNeigh, nodes first establish an order on their neighbor nodes; then, they exchange
NEIGHBOR-BASED TOPOLOGY CONTROL
information about the neighbor orders; finally, they compute their local view of the final network topology. The main differences between XTC and KNeigh are the following:
1. The neighbor order is based on the concept of ‘link quality’, rather than distance as it was the case in KNeigh.
2. When exchanging neighbor lists and computing the final topology, nodes consider the entire neighbor set, and not the first ę elements in the order as was the case in KNeigh.
Let us comment more on issues (1) and (2). The use of distance in KNeigh was motivated by the need of upper bounding the physical node degree, which is defined as the number of nodes within a node’s transmitting range: by setting the transmit power to the minimum level needed to reach ę neighbors, we ensure that the physical degree of a node is ę. Is it necessary that these neighbors are the closest ones, in term of Euclidean distance? The answer is no if we consider the correctness of KNeigh, but it is yes if we want to have a probabilistic guarantee on the connectivity of the generated topology: the most natural way to prove that the topology computed by KNeigh is connected w.h.p. is by using the theory of ę-neighbors graph, which is based on the concept of Euclidean distance. In case of XTC, the focus is on ensuring worst-case connectivity, which, as we know, implies that the physical node degree cannot be bounded. As a consequence of this, the number of neighbors within a node’s transmitting range is not an issue, and the notion of Euclidean distance is no longer necessary since connectivity is guaranteed in the worst case. Thus, nodes can use a more general and practical notion such as link quality to order their neighbors. We remark that, under particular circumstances (e.g. flat and unobstructed environment), the order induced on neighbors by link quality might coincide with the order induced by distance. Finally, note that nodes in XTC must exchange their entire neighbor set (issue (2)) since otherwise worst-case connectivity cannot be ensured.
12.3.1 Protocol description
Before presenting the protocol, we need some notation. Let us consider a certain node u, and let N(u) be its neighbor set (i.e. the set of nodes within u’s transmitting range at maximum power). In the following, we denote the order relation on N(u) by <u; in particular, w <u v means that node w precedes node v in the ordering of node u. In terms of link quality, w <u v indicates that link (u, w) has relatively higher quality than link (u, v). As usual, we assume that all the nodes in the network have the same maximum transmit power Pmax and that the wireless medium is symmetric.
As anticipated above, the XTC protocol (which is summarized in Figure 12.6) is very simple: initially, every node in the network establishes an order -< on the neighbor set. The way this can be accomplished depends on the criterion used to establish link quality: it can be defined in terms of the received signal strength, or in terms of packet delivery ratio, and so on. To simplify the presentation of XTC, in the protocol specification reported in Figure 12.6, it is assumed that link quality is determined by the strength of the received signal. With this assumption, establishing the neighbors order is very simple: each node sends a beacon at maximum power; when a neighbor receives the beacon, it measures the received signal strength (this can be easily done since wireless cards are typically equipped
NEIGHBOR-BASED TOPOLOGY CONTROL
(algorithm for node u)
Pmax is the maximum node transmit power
N(u) is the neighbor set of node u
DN(u) is the set of discarded neighbors