Download (direct link):
The NDP protocol is used to generate events, which are dealt with by the CBTC reconfiguration protocol. Three types of events can be generated:
- join(v), indicating that a new neighbor v has been detected;
- leave(v), indicating that neighbor v is no longer in the nodeís transmitting range;
- aChange(v), indicating that vís relative angle with respect to the node is changed since last beacon.
The reconfiguration protocol, which is summarized in Figure 13.6, is very simple. When a join(v) or leave(v) event is detected, the node determines whether vís removal or insertion in the neighbor set modifies the cone coverage. In case of join(v), similar to the shrink back
(algorithm for node u)
NDP is the Neighbor Discovery Protocol, that generates join(), leave() and aChange() events
2. Reconfiguring the power level
repeat until termination execute NDP case of detectedEvent join(v): insert v in the neighbor list compute the cone coverage while cone coverage is guaranteed
try to remove neighbors, starting from the farthest leave(v): remove v from neighbor list
check condition on cone coverage if the condition is violated, execute basicCBTC aChange(v): modify the cone coverage information
if the condition on coverage is violated, execute basicCBTC
noEvent: skip set timer TCFreq() wait until timer is expired
Figure 13.6 The CBTC reconfiguration protocol.
DEALING WITH NODE MOBILITY
operation (see Section 11.1), the power needed to reach node v is recorded, and neighbor nodes are removed (starting from the farthest) as long as the required condition on cone coverage is satisfied. In case of leave (v), it is verified whether the condition on cone coverage is impaired by vís failure; if yes, then the basic CBTC protocol is reexecuted. In case an aChange(v) event happens, the node updates the information about the cone coverage, and if the cone coverage requirement is not satisfied, it reexecutes basicCBTC.
In (Li et al. 2001), Li et al. show that if the network topology ever stabilizes, then the reconfiguration algorithm eventually builds a graph that preserves the connectivity of the final network, as long as periodic beaconing is guaranteed. The authors also discuss the important topic of which transmit power to use for beaconing. They show that if the beacon is sent using the minimum power needed to reach all the nodes in the neighbor list (i.e. it is sent at the broadcast power), then the reconfiguration protocol works correctly in combination with the basicCBTC protocol even in case the asymmetric edge removal optimization is implemented.
Toward an Implementation of Topology Control
Level-based Topology Control
In Chapters 10-12, we have presented several solutions to the problem of designing protocols for distributed topology control TC in ad hoc networks. The proposed solutions have been analyzed mainly from a theoretical viewpoint: what are the properties of the generated topology, what is the message complexity of the protocol, and so on. While this type of analysis is important (it is, in a certain sense, an investigation of the best possible results you can obtain with distributed topology control), the probably more important issue of how the proposed techniques can be used in a practical setting has been almost completely ignored in the protocols presented in Chapters 10-12.
When you think of applying distributed TC in practical settings, you have to face several problems, mainly because of the fact that some (or many) of the assumptions on which the protocol design is based may not hold. One such striking example is the assumption that all the nodes have the same maximum transmit power level, which is fundamental for the correctness of all the protocols presented in Chapters 10-12: combined with the working hypothesis of symmetric wireless medium, this assumption ensures the correct determination of a nodeís neighbor set in the maxpower communication graph. Does this assumption hold in practice? The answer to this question depends on the application scenario. Suppose you are in an ad hoc network used, say, for ubiquitous Internet access. In this application, the network is composed of different types of devices (wireless access points, laptops, PDAs, cell phones, and so on) that are used to extend the coverage area of the various wireless access points by exploiting multihop communication. It is clear that in this scenario to assume that all the devices have the same maximum transmit power is unrealistic: wireless access points are likely to have a much higher maximum transmit range than, say, the maximum range of a PDA. Let us now consider a more favorable application scenario: a sensor network application that uses sensor nodes equipped with the same type of wireless transceiver. Even in this situation, although the nominal maximum transmit power is the same for all the nodes, it is likely that the actual maximum transmitting range varies considerably between different nodes. In fact, the actual transmitting range is influenced by environmental conditions (temperature, humidity, wind, and so on), as well as by the battery level, and so on. In other words, contrary to what is assumed in most of the TC approaches proposed so