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

ISBN-10 0-470-09453-2

**Download**(direct link)

**:**

**43**> 44 45 46 47 48 49 .. 122 >> Next

Although implementing of unidirectional wireless links is technically feasible (see (Bao and Garcia-Luna-Aceves 2001; Kim et al. 2001; Pearlman et al. 2000a; Prakash 2001; Rama-subramanian et al. 2002) for unidirectional link support at different layers), the advantage of using unidirectional links is questionable. For instance, Marina and Das have recently observed that, in case of routing protocols, the high overhead needed to handle unidirectional links outweights the benefits that they can provide, and better performance can be achieved by simply avoiding them (Marina and Das 2002).

Indeed, most routing protocols for ad hoc networks (for instance, DSR (Johnson et al. 2002) and AODV (Perkins et al. 2002)) are based on the implicit assumption that wireless links can be ‘reversed’, that is, must be bidirectional. The same observation applies to the current implementation of the MAC layer in the IEEE 802.11 standard, which is based on a RequestToSend/ClearToSend message exchange: when node u wishes to send a message to a node v within its transmitting range, it sends a RTS to v and waits for the CTS message from v. If the CTS is not received within a certain period of time, the message transmission is aborted and it is tried again after a backoff interval. If the wireless link between nodes u and v is unidirectional, either one of the RTS or CTS message is not received, and communication is not possible. Supporting unidirectional links at the MAC layer would imply that intermediate nodes should relay the RTS/CTS messages on behalf of node u or v. Alternatively, a different channel access mechanism (for instance, based on collision detection instead of collision avoidance) should be used. Anyway, supporting unidirectional links would imply a considerable modification of the current implementation of the IEEE 802.11 MAC protocol.

The reasons above have motivated researchers to investigate restricted versions of the RA problem, where certain symmetry constraints are imposed on the communication graph. In particular, the following two problems have been defined and investigated (Blough et al. 2002; Calinescu et al. 2002):

Definition 7.4.1 (WSRA problem) Let N be a set of nodes in the d-dimensional space, with d = 1, 2, 3. Let RA be a range assignment for N and let G be the corresponding (directed) communication graph. The symmetric subgraph of G, denoted by GS, is the undirected graph obtained from G by removing unidirectional links. The WSRA problem is to determine a range assignment function RA such that Gs is connected, and c{RA) = JfuˆN (RA{u))a is minimum, where a is the distance-power gradient.

Definition 7.4.2 (SRA problem) Let N be a set of nodes in the d-dimensional space, with d = 1, 2, 3. A range assignment RA for N is said to be symmetric if it generates a

THE RANGE ASSIGNMENT PROBLEM

79

Figure 7.4 The different symmetry requirements in the WSRA and in the SRA problem. In WSRA, unidirectional links (dashed edges) are allowed, but they are not essential for connectivity. In SRA, all the links in the communication graph must be bidirectional: nodes u, v, and w must increase their transmitting range to meet this stronger symmetry requirement.

communication graph that contains only bidirectional links, that is, RA(u) > 8(ut, uj) & RA(uj) > 8(uj,uj). The Symmetric Range Assignment (SRA) problem is to determine a SRA function RA such that the corresponding communication graph is connected, and cm) = (RA(u))a is minimum, where a is the distance-power gradient.

Note the different symmetry requirements in the two versions of the problem: in the WSRA (Weakly Symmetric Range Assignment) problem, the communication graph may contain unidirectional links which, however, are not essential for connectivity. On the other hand, in the SRA problem, the communication graph must contain only bidirectional links. This is a much stronger requirement on the communication graph, as the example reported in Figure 7.4 shows. The motivation for studying WSRA stems from the observation that what is really important in the design of ad hoc and sensor networks is the existence of a connected backbone of symmetric edges. In other words, there could exist links for which symmetry is not guaranteed, but these links can be ignored without compromising network connectivity.

7.4.1 The SRA problem in one-dimensional networks

In case of colinear nodes, the optimal SRA for a set of nodes can be constructed as follows:

1. Order the nodes according to their spatial coordinate; let {ui,... ,un} be the resulting node ordering.

2. Assign to node u1 transmitting range 8(ui,u2), to node un transmitting range 8(un-1, un), and to every other node u transmitting range equal to max{5(ui-1, uf), 8(ut, ui+1)}.

80

THE RANGE ASSIGNMENT PROBLEM

3. Augment the transmitting range of some of the nodes in order to preserve symmetry: for any unidirectional edge (ui,uj) in the communication graph generated at the previous step, increase the transmitting range of node uj in such a way that it can reach node u. This process is repeated until all the edges in the graph are bidirectional.

**43**> 44 45 46 47 48 49 .. 122 >> Next