Books
in black and white
Main menu
Share a book About us Home
Books
Biology Business Chemistry Computers Culture Economics Fiction Games Guide History Management Mathematical Medicine Mental Fitnes Physics Psychology Scince Sport Technics
Ads

Topologi control in wireles ad hoc and sensor network - Santi P.

Santi P. Topologi control in wireles ad hoc and sensor network - Wiley publishing , 2005. - 282 p.
ISBN-10 0-470-09453-2
Download (direct link): topologycontess2005.pdf
Previous << 1 .. 46 47 48 49 50 51 < 52 > 53 54 55 56 57 58 .. 122 >> Next

A final aspect to consider in the design of a topology control mechanism is the quality of information required by the protocol: since obtaining very accurate information such as node locations is, in general, quite expensive (in terms of additional hardware required on the nodes, or message overhead, or both), it is desirable that the protocol relies on ‘low-quality’ information. This issue is carefully discussed in Section 9.2.
Summarizing, a topology control protocol should
1. be fully distributed and asynchronous;
2. be localized;
3. generate a topology that preserves the original network connectivity and relies on bidirectional links only;
DISTRIBUTED TOPOLOGY CONTROL: DESIGN GUIDELINES
99
4. generate a topology with small physical node degree;
5. rely on ‘low-quality’ information.
9.2 The Quality of Information
An important aspect to be considered in the design of topology control protocols is the type of information used by the nodes to build the local view of the topology: nodes can use high-quality information (e.g. neighbor node locations), medium-quality information (e.g. directional information, or distance to neighbors), or low-quality information (number and identity of neighbor nodes). In general, there is a direct relationship between information quality and energy efficiency of the computed topology: the more accurate the information available to the nodes, the more energy savings can be achieved. However, information quality (and, thus, energy savings) must be carefully traded off with the cost incurred for making the information available to the nodes. The cost is due to either some additional hardware required on the nodes (e.g. low-power GPS receivers in case of location information) or the message overhead needed to produce/update high-quality information, or both.
We clarify this point with an example. Suppose protocol Pi is based on location information and protocol P2 is based on distance estimation. Clearly, the cost of implementing P2 in a real network is significantly lower than that required by P1, since estimating distance between nodes requires cheaper hardware and/or less message exchange than does estimating node positions. So, if the energy savings provided by protocol P1 are not considerably higher than those achieved by P2, a solution based on protocol P2 may be preferable in practice.
Another argument in favor of designing protocols based on low-quality information is that they can be used in a wider range of application scenarios. For instance, it is well known that location estimation techniques perform poorly in indoor environments because of the hardly predictable propagation of the radio signal. So, location-based topology control protocols such as those presented in Chapter 10 cannot be used in this case.
9.3 Logical and Physical Node Degrees
As discussed in Chapter 3, one of the motivations for topology control is its potential to reduce interference between concurrent transmissions. A typical measure used to quantify the expected interference is the node degree of the communication graph: if the transmitting node u has small degree, relatively few nodes will experience interference during u’s transmission. For this reason, it is desirable to generate topologies with small average node degree. However, a clarification about the term ‘node degree’ is in order.
Most of the current literature on topology control defines node degree as follows:
Definition 9.3.1 (Logical node degree) Let GP = (N, EP) be the communication graph generated by a certain topology control protocol P. For a given u e N, the (logical) node degree of u in GP is defined as
L Deg(u) = |{v e N : (u, v) e EP}|.
100
DISTRIBUTED TOPOLOGY CONTROL: DESIGN GUIDELINES
The definition above is the traditional definition of node degree used in graph theory (see Appendix A). Since in the distributed setting typical of ad hoc and sensor networks every node independently builds its local view of the communication graph, we can equivalently define the logical degree of a certain node u as the number of nodes in its neighbor list after the protocol execution.
Note that what is defined above is a logical node degree, since some of the nodes that are within u's transmitting range might not appear in u's neighbor list (typically, because their link to node u is not energy efficient). As a consequence, the logical node degree is not very effective in measuring the expected interference experienced by nodes: if a certain node v is within u’s transmitting range but is not listed in u’s neighbor list (i.e. edge (u, v) is not in EP), it will not contribute to u’ s logical degree, but it is definitely affected by node u s transmission.
To circumvent this problem, the authors of (Blough et al. 2003b) have introduced the notion of physical node degree, which is defined as follows:
Definition 9.3.2 (Physical node degree) Let GP = (N, EP) be the communication graph generated by a certain topology control protocol P. For a given u e N, the (physical) node degree of u in G P is the number of nodes within u ’s range when it transmits with the minimum power needed to reach its farthest neighbor in GP, that is, when u transmits at the broadcast power. Formally,
Previous << 1 .. 46 47 48 49 50 51 < 52 > 53 54 55 56 57 58 .. 122 >> Next