Design

Overview

The RNS (Redundant Node Selection) algorithm was described in [Zhong09]. It’s aim is to find the nodes of a network which can be turned off without influence on the network performance. The redundancy criteria bases on the coverage of a node. A node is considered redundant if after it is turned off the coverage of the whole network will not change. To allow maintaining connectivity of the network a special feature was added.

Algorithm

The description below is based on the original paper [Zhong09]. For a detailed explanation of the actual ns-3 RNS implementation, please refer to Implementation.

Local execution

All local operations situate the running node (referred to as central node) in point (0,0). Neighboring nodes are considered to be circles of a certain radius with a center in the node’s position.

Several assumptions were made in the original RNS algorithm. First of all, every node has the same range. This simplifies the algorithm a lot as it implies another assumption that all one- and two-hop neighbors intersect at exactly two points with the central node.

The RNS algorithm runs in iterations. The aim of each iteration is to find the ‘next circle’.

At the beggining, the algorithm finds any neighbor that lies in its direct communication range (and vice versa). Let \(N_1\) be the point where central node lies, \(N_2\) the point where the current neighbor lies. If both \(N_1\) and \(N_2\) lie on the same line, then \(W\) is the point of its intersection with circle \(N_1\), opposite to node \(N_2\). Points \(Q_1\) and \(Q_2\) are points of intersection of circles \(N_1\) and \(N_2\). It is important to notice, that point \(Q_2\) is the one lying on the right of a vector \(\overrightarrow{N_1 N_2}\) and that it is calculated only once, for the first node.

The algorithm ends if:

  • the next circle cannot be found (central node is NOT redundant),
  • the first circle (node \(N_2\) in our case) is the next circle (central node IS redundant),
  • the current circle is external and contains point \(Q_2\) (central node IS redundant).

There are three ways to find the next circle:

1. If there is a node \(N_3\) which lies in the area \(W Q_1 N_1\) and point \(Q_1\) lies within it’s range then node \(N_3\) can be the next circle. Restart the algorithm with node \(N_3\) instead of \(N_2\). This situation was shown in Figure 1.

_images/des_fig1.png

Figure 1

2. The circle lying in the area \(W Q_1 N_1\) might not contain point \(Q_1\). In this case, as shown in Figure 2 there is a small area \(A B Q_1\) which remains not covered. A search is performed among all neighbors to find a node \(N_E\) that would cover the area. If such node is found then the algorithm should restart substituting the current node for node \(N_E\). If no such node exists then the node is not redundant and algorithm ends.

_images/des_fig2.png

Figure 2

3. If there are no nodes within the segment \(W Q_1 N_1\) then any external node \(N_E\) is searched for, that would contain point \(Q_1\). Cirlces \(N_1\) and \(N_E\) intersect in points \(C_1\) and \(C_2\). The algorithm reruns point 3, substituting \(Q_1\) by \(C_1\) and \(N_2\) by \(N_E\) as long as there are nodes matching the conditions for new \(Q_1\) and \(N_2\). If no such node was found in point 3, then the node is not redundant. If point \(Q_2\) lies within next circle then central node is redundant and the algorithm ends.

_images/des_fig3.png

Figure 3

Global execution

Authors of the RNS algorithm notice that the decision which nodes should be turned off cannot be made locally. They define the so called Redundant Related Nodes (RRN). If there is a set of nodes in which all the nodes are redundant, but turning one of them off will change the status of all others to non-redundant, then those nodes are called RRNs.

This set can be divided into pairs of nodes. Each node in a pair is a Twin Redundant Related Node. Only one node from each pair can be turned off and the other has to remain turned on. According to [Zhong09] there should be only one node turned off at a time. Next, if there are any pairs of TRRNs another node can be switched off. This action is to be repeated until there are no pairs of TRRNs.

Summary

RNS algorithm, as described in [Zhong09] assume a global knowledge of all nodes location and status. In sensor networks, however, the algorithm has to be fully distributed and involve some communication methods to allow synchronization.

Additionally, rarely does it happen that nodes have a fixed communication range, equal for all the nodes in the network. Adaptive energy emmission allows longer network life spans and many techniques exist and are used to lower the communication power, and thus also nodes’ ranges. This also implies that nodes should have a way to learn their neighbors’ ranges.

Another issue that had to be addressed in a real implementation is search optimalization, that would shorten the time spent on searching the ‘next circle’.

Implementation

The description published in [Zhong09] did not contain any pseudo-code or particular guidelines on how to implement the RNS algorithm. Some issues were not explained in detail (e.g. the means of inter-node communication) allowing different interpretations. Some issues were not addressed at all (e.g. neighbors search order). Therefore the ns-3 implementation differs to much extent from the original RNS algorithm.

All the changes and their influence on algorihm behaviour were explained below. Please refer to Algorithm Tests to see some examples of the situations discussed.

Neighbor Search Order

The main action of the algorithm is to search the ‘next circle’. Obviously, checking every neighbor in a random order will eventually find the proper candidate, but this requires more computation effort than if the nodes were pre-sorted according to some key.

Looking at the way the algorithm works it is easy to notice that the highest probability to find the next circle in every step is by looking counterclockwise from the starting node. The starting node should be the one that is closest to the central node because then it covers the largest area of central node’s own coverage.

If there is no node that would be covering the central node’s exact location then this location has to be covered by central node and it will not be turned off. This means that there is a limitation for the nearest node:

\[\begin{split}\overline{N_0 N_{Nearest}} < R_{Nearest}\end{split}\]

Please refer to Situation 9 of Simple cases for an example where the nearest node does not exist.

If the nearest node can be constituted then it is assigned an angle of 0 and the search algorithm will refer to it as to the first node. All other nodes are assigned an angle that is created by rotating the ray which starts in node 0 and goes through the node in question, towards the first node. This means that the angular distance from the nearest node determines the value of the key assigned to each node. For example in Figure 3: \(A_4 < A_1 < A_2 < A_5\) and \(A_3 = 0^\circ\).

_images/des_angles.png

Figure 3

Only active (meaning turned on) sorted nodes are considered in the search. They are stored in a separate vector.

A question remains: should we search the next circle from the first (i.e. the nearest node) or the last (i.e. the one which has greatest angular distance from the nearest node)? Situation 3 and Situation 4 in Redundancy cases are a good example of the possible advantages and disadvantages of both approaches.

Searching nodes from the first to the last (counterclockwise) allows us to find the next circle faster, especially if there are many nodes to analyze around the central node. But it also considers more nodes to be RRNs than if the search was conducted from the last node.

In this implementation a compromise attitude was taken. In the first two steps of the algorithm the nodes are searched from the first to the last. Point \(Q_1\) limits the area near to current node and eliminates those nodes which lie very close. Step 3, on the other hand, doesn’t provide any mechanism protecting RNS from the situation where many nodes lie close to each other (like in Situation 3). Therefore in step 3 the nodes are checked starting from the last and moving clockwise.

Communication Protocol

As it was mentioned before, much information has to be exchanged by the nodes, including:

  • position,
  • status: active (powered on, nonredundant, fully-functional) or inactive (turned off),
  • redundancy status,
  • range.

RNS is not a communication protocol, it is a self-organisation module that requires other parts of the system to take care about communication.

In many cases the RNS algorithm can rely on the communication protocol, used by the node to submit information on position and update it, when necessary. It is up to the communication protocol to decide which nodes are neighbors that could be used by RNS module to calculate redundancy. Usually it would be simply all one- and two-hops neighbors. But sometimes the communication protocol might choose to rely on the geographic coordinates to differentiate between potential RRNs and nodes which cannot be used in RNS algorithm.

In any case RNS needs access to the communication protocol to inform it about being redundant. This information might be used by the node to limit it’s participation in network’s traffic. Before turning off, the node has to broadcast a message informing all of its neighbors that they cannot use it when calculating their own redundancy.

RNS asks the communication protocol to broadcast its header if:

  • it is switching its status,
  • it is changing its range,
  • it is changing its position (unless the protocol already takes care of this part).

RNS prepares its own header and calls a function appropriate for the node’s communication protocol. It is also ready to receive an RNS header from other nodes via its communication protocol.

To sum up, the protocol needs to be changed in several ways to cooperate with RNS module:

  1. It has to recognize a status change and make use of its own redundancy to save energy.
  2. It has to share some of its communcation abilities with RNS module, to allow it to send an RNS header if necessary.
  3. It has to share the content of its routing table if it contains location information of neighboring nodes.
  4. It has to recognize incoming RNS headers and pass them to RNS module.

Please refer to User Documentation Development for further explanation on RNS cooperation with routing protocol and other ns-3 units.

Different Node Ranges

The original RNS algorithm makes an assumption that all circles have equal radius. Handling a situation where nodes can have different communication ranges complicates the calculations, but is an inevitable part of the algorithm, highly increasing its usefullness.

The changes made to the algorithm to work correctly for different circles radii are far-going.

First of all, wherever the algorithm checks for point contention within a circle a proper radius has to be taken into consideration. Also circles intersection depend on the radii of both circles. Finally, node’s range information has to be passed and kept up to date at all times to ensure proper algorithm execution.

Second, it is possible for central node to be completely covered within a single neighbor’s range (see Situation 4 in Simple cases). RNS can now handle this case along with a situation where two neighbors of large radii manage to cover the range of central node (Situation 5).

Next, in some cases circles’ intersection is not obvious anymore and has to be checked, not to cause an error.

Lastly, if an external node is being searched for in the third step of the algorithm, then not only must the next circle contain point \(Q_1\), but also newly calculated \(C_1\), to ensure that the whole area is covered. A good example of such case is shown in Situation 2 and in Situation 5 (pay close attention to nodes 1, 2 and 8).

Redundancy vs Connectivity

The original RNS algorithm uses node’s coverage as a sole criterion for its redundancy. This however might lead to a situation when a node considered redundant is at the same time necessary for the network’s connectivity. What’s more the range does not refer to the node’s radio range. Instead it reflects the area that the node is supposed to cover, for example with its sensor.

The ns-3 RNS implementation deals with this setback by allowing user to tell RNS to maintain network’s connectivity. This is achieved by always using halves of the actual nodes’ radio ranges in all redundancy calculations.

The rationale behind this has been shown in Figure 4. Two nodes are in range of each other when the distance between their centres is smaller than or equal to the sum of halves of their ranges.

_images/des_fig4.png

Figure 4

In case of unequal nodes’ ranges, as shown in Figure 5, it is possible for node 0 to be in range of node 1 without being able to communicate. It is not the job of RNS algorithm to adjust the power level of each node. If, for any reason, the relevant algorithms or routing protocols allowed the abovementioned situation then it means that the connectivity of the network is sufficient and nodes 0 and 1 should be considered connected. Again, taking halves of their ranges will allow proper detection of ‘being in range’.

_images/des_fig5.png

Figure 5

RNS algorithm also checks for points being in range of nodes. Points \(Q_1\) and \(Q_2\) are intersection points of two circles, which symbolize nodes’ ranges. If the RNS ranges used by the nodes don’t have anything in common with their radio ranges (for example the range refers to the sensor range), then the range should be used as provided to RNS module. On the other hand, if network is expected to remain connected after switching off redundant nodes, then the algorithm should use halves of real radio ranges in its calculations.

This is achieved by using a special radio estimation function that monitors current communication power level and sets half of the calculated radio range as node’s range visible for RNS algorithm. The function takes the propagation loss model used by the node into consideration.