Download (direct link):
á.2 The CTR for Connectivity with Bernoulli Nodes
The point graph model with Bernoulli nodes is an extension of the traditional point graph model. In this model, it is assumed that at any instant of time any node in the network is active with a certain constant probability p > 0. Since node activations are independent events, the node’s active/inactive status can be modeled by a Bernoulli random variable of parameter p (this explains the name of the model).
Assume n nodes are distributed in a certain region R, each with transmitting range r and probability of being active equal to p > 0. We denote by G(n, r) the communication graph
OTHER CHARACTERIZATIONS OF THE CTR
Figure 6.2 Example of G(n, r) graph (a) and of its A(n, r, p) (b) and I(n, r, p) (c) subgraphs. Active nodes are light gray, and inactive nodes are black.
generated as in the traditional point graph model, that is, the graph obtained by connecting any two nodes that are at distance of, at most, r, independent of their active/inactive status. We denote the subgraph of G(n, r) induced by the set of active nodes as A(n, r, p). We denote as I(n, r, p) the subgraph of G(n, r) obtained from G(n, r) by removing all links whose both endpoints are inactive nodes. An example of graph G(n, r), and of its subgraphs A(n, r, p) and I(n, r, p), is reported in Figure 6.2.
Recent papers have investigated asymptotic conditions under which A(n, r, p) and I(n, r, p) are connected with high probability. The motivation for analyzing the connectivity of these graphs stems from the fact that A(n, r, p) and I(n, r, p) can be used to model several network design problems, such as the following:
- Randomized virtual backbone construction: In many applications of WSNs, nodes alternately shut down their transceivers in order to reduce power consumption. (We recall that the power consumption of a sensor node can be considerably reduced by turning the radio off-see Section 2.3). However, a certain number of nodes must keep the radio on, in order to preserve network connectivity. Thus, active nodes must form a connected backbone. We refer to this property as ‘active connectivity’. Another desirable property is that any inactive node has at least one active node within its transmitting range. In fact, inactive nodes still sense the environment (it is only the radio apparatus that is turned off), and, in case an inactive node detects an anomalous event, we want that the information regarding this event propagates quickly through the network, eventually reaching the operator. This can be accomplished only if every inactive node is able to directly communicate with at least one active node (and if the set of active nodes forms a connected backbone). Since if this property holds the set of active nodes is a dominating set, we refer to this property as ‘active domination’. Examples of virtual backbones are reported in Figure 6.3.
A simple randomized strategy to build a virtual backbone of active nodes is as follows: any node in the network remains active for a fraction 0 < p < 1 of its operational time, where the activation periods are randomly chosen. Assume that n nodes are distributed in a certain region R, and each node has the same transmitting range r. It is seen immediately that the virtual backbone resulting from the randomized strategy above satisfies active connectivity if and only if graph A(n, r, p) is connected, and
OTHER CHARACTERIZATIONS OF THE CTR
Figure 6.3 Active connectivity and active domination of the virtual backbone. Active nodes are light gray, and inactive nodes are black. The backbone of active nodes in (a) satisfies active connectivity, but not active domination (node u has no direct connection to any active node). The backbone in (b) satisfies both active connectivity and active domination.
that it satisfies both active connectivity and active domination if and only if graph I(n, r, p) is connected.
- Randomized broadcast: Assume a certain network node u wants to broadcast a message m. Performing broadcast in ad hoc networks is a nontrivial task, because of the problem of spatial reuse: if many nodes try to relay m simultaneously, it is likely that they corrupt each other’s transmission, leading to an increase in the broadcasting latency and/or energy consumption. This problem is known in the literature as the broadcast storm problem (see Chapter 8 for a more detailed description of this phenomenon). An easy strategy to prevent the broadcast storm problem is to use randomization: when a node receives message m, it relays m with a certain probability 0 < p < 1, independent of every other node. It is easy to see that under the assumption that n nodes with transmitting range r are distributed in a certain region message m eventually reaches all the network nodes if and only if graph I(n, r, p) is connected.
The connectivity of graphs A(n, r, p) and I(n, r, p) can be characterized by combining Theorem 9 of (Yi et al. 2003) and Theorem 9 of (Yi and Wan 2005).