As the RNS algorithm is always run locally, in all tests described below there is a single distinguished node, called “central node”. In most of the tests, to simplify the code, the calculations and to ease understanding of the tests, the central node is placed in point (0,0). Some tests however place it in a different location to prove that the algorithm works fine regardless of the central node’s coordinates.

The central node has an ID 0 and it’s range is marked with a thick, black circle. Other nodes have their corredponding IDs placed in the centers and their ranges are marked with dotted line.

Nodes which are central node’s Relative Redundant Nodes (RRNs) are marked grey to make it easy to see how they cover the area of the central node.

There is a graph corresponding to every test to visualize nodes location.

The source code of all the tests can be found in:

```
src/rns/test
```

To run the tests you need to type the following commands::

```
./waf configure --enable-tests --enable-modules=rns --enable-examples
./test.py -s test-suite-name
```

Those test aim at testing the basic funcionality such as setting and changing data stored in objects, constructors, destructors and some auxiliary functions.

To run unit tests, type the following command::

`./test.py -s rns-unit-tests`

As the whole RNS class is a template class also the header had to be templated.
This implied certain difficulties with header registration in ns-3. To ensure
that everything works a test is conducted that creates, uses *Serialization*
and *Deserialization* functions.

The test proves that at the same time two instances of *RnsHeader* class can
be created with different template types.

In the neighbor test *Ipv4Address* is used as *IdType* argument of the
template. This is probably the most useful one, but other tests were conducted
with different identification types.

The tests checks if neighbors and neighbor tables are created and work properly.

The main point of this test suite is to prove and document correct operation of ns-3 RNS algorithm implementation.

This test-suite can be run using:

`./test.py -s rns-algorithm-tests`

First examples show the very basic behaviour of RNS algorithm and prove that it behaves as expected. The only situation which was not considered being worth to get a visualization is situation 0. In this situation there are no nodes around the central node.

*Situation 1* contains a single neighbor node which is not in
direct contact with the central node. Even though the situation is not possible
in routing protocols it could happen in some application. Obviously, the node
is not redundant.

Situation shown in Figure *Situation 2* is also a trivial one. The
node which has a single one-hop neighbor can never be redundant, unless both of
them have exactly the same coordinates, which is physically impossible or if
the neighbors range is much greater then central node’s (see
*Situation 4*).

Also if a second neighbor arrives, there is little possibility for two of them to completely cover the area covered by central node. It remains turned on and is not redundant.

However, if one of the neighbors has a very large coverage, it might totally
include the area of central node. Then, of course, central node is redundant, as
shown in *Situation 4*.

If node 1 had a smaller range it wouldn’t be able to totally cover the area of
node 0. However in *Situation 5* nodes 1 and 2 together make node
0 redundant. This situation force algorithm to use a special function which is
run only if two active neighbors are found. The function checks if they overlap
in a way that would allow to turn node 0 off.

With three neighbors it is easy to make the node redundant, but to check if
the algorithm does not get trapped in a situation very close to redundancy, the
nodes in Figure *Situation 6* were placed in a way that wouldn’t
allow this.

There is a small area uncovered by any of the neighbors, which makes the central node non-redundant.

Another simple situation shows a rather unique example of a redundant node, placed around three other nodes, which cover all the area in its range.

If the node is redundant due to the presence of a group of three nodes adding
another node would not change its status. This is shown in Figure
*Situation 8*.

Interestingly, in this case all four nodes will be considered RRNs even though
only three of them would suffice. The reason for this is that the next node is
searched as the next sorted neighbor from the current one. Node 4 is a next
node for node 3, and node 1 is a next node for node 4. A solution to this
problem would be a search from the opposite direction, meaning: from the last
node. If, however, the next node wouldn’t lie in the \(W N_0 Q_1\) area it
would take much effort to check every node one by one (see also *Neighbor Search Order*).

If the nodes from the previous situation move further away from the central node or change their ranges in such manner, that none of them will have central node as a one-hop neighbor, then central node will not be redundant.

Such situation is visualized in *Situation 8*. The algorithm is
not even run by the node. When sorting of neighbors takes place, there is no
node found for which central node is a direct neighbor. Therefore the sorted
neighbors table is empty. The algorithm will end immidiately.

All the above tests were repeated with nodes coordinates moved by a vector [1.5,1.5] to check if the special central node’s position [0,0] influenced the tests.

There are numerous situations when the central node is redundant. Those shown below were chosen to test every possible, error-prone configuration and every line of the RNS algorithm implementation.

In *Situation 1* there are four neighbors, but one of them lies
outside the direct range of central node. All other neighbors are equally
distant from central node. Node 1 was updated as the first so the algorithm
will start execution taking node 1 as the one to begin with.

As explained in *Algorithm*, RNS first searches for the nodes lying in the
segment of the circle limited by points \(W\) and \(Q_1\). Node 2 lies in
the abovementioned segment for node 1, but there is no such node lying in this
segment for node 2. Therefore it’s necessary to search for a node which would
lie outside this segment but which would fulfill other requirements to become a
next hop circle. This triggers a different part of the algorithm.

*Situation 2* shows that the algorithm works even if the node
added as the first one is not the nearest. The node elected as nearest in this
case is node 2. Additionally the algorithm has to search for next circle among
two-hop neighbors.

What happens if the area around central node becomes more ‘crowded’? Figure
*Situation 1* is a visualisation of a case where all parts of
the algorithm have to be used to determine whether central node is redundant or
not and which of his neighbors are RRNS.

The nearest node is node 5. There are no nodes in the segment \(W N_0 Q_1\), so the algorithm searches for an external node which fulfills the conditions (node 5 is current):

\[\begin{split}\overline{N_{external} N_{central}} < R_{central} + R_{external}\end{split}\]\[\begin{split}\overline{N_{external} N_{current}} < R_{central} + R_{current}\end{split}\]\[\begin{split}\overline{N_{external} Q_1} < R_{external}\end{split}\]

Nodes are searched from the last (node 4) to the first (node 5). The first node found to match the conditions is node 8 and it becomes the next circle.

If the external node was searched in the other direction: starting from the next (node 6) and moving towards the last one (node 4) all three nodes: 6, 7, 8, would match the above conditions and they would all be considered RRNs.

As a result any change in the status or range of any of those nodes would
trigger *AmIRedundant* function and would cause recalculation of the central
node’s status. That would cause many unnecessary calculations, so the search
from the last towards the next node was used. The disadvantage is that each
time an external source is searched for, more nodes have to be checked.

It is possible that for some reason one of central node’s RRNs can be turned
off. Let’s assume that the battery of node 8 was running low and it’s energy
saving system decided to turn it off. An RNS message was broadcast to all one-
and two-hops neighbors, telling them about the status change. Central node also
received the message and run AmIRedundant function to check if it remains
redundant. It’s easy to see in Figure *Situation 4* that nodes
6 and 7 cover a big part of node’s 8 range. RNS algorithm finds node 7 to be a
good substitute of node 8. As a result central node remains redundant and it’s
RRNs are now nodes: 5,7,1 and 3.

Even though usually nodes in a sensor network maintain the same or at least similar transmission power level, it is possible that they need to use different energies, for example to reach other, remote nodes.

An extreme case was tested, as shown in Figure *Situation 5*.
The nodes are scattered and represent different power levels. This situation
requires using every possible situation of redundancy, and what is more,
switching between checking different conditions.

The outcome of checking the redundancy of node 0 in this situation is, of course, positive. Its whole range area is covered by its neighbors. All of them are node’s 0 Relative Redundant Nodes, exept node 5. This means that node’s 0 redundancy is prone to change whenever one of other nodes moves or turns off.

Some most obvious non-redundancy situations were shown in section
*Simple cases*. There are, however some situations that potentially could
cause algorithm error.
To prove that the algorithm works fine and is capable of correct recognition of
non-redundant status, another test case was added. It consists of two
situations.

First of them shows a possibility of a node being non-redundant because of a
small uncovered area. As you can see in *Situation 1* node 3
lies in the \(W N_0 Q_1\) segment for node 2. The area marked red remains
uncovered and the algorithm fails to find any other node that would contain
points: \(A\), \(B\) and \(Q_1\). The central node has to remain on.

Another difficult situation which requires some special behaviour of the
algorithm is shown in *Situation 2*. Here there is an
uncovered space left in the middle of central node’s coverage area. Node 5 does
not contain point \(C_1\) which makes it unsuitable as a next circle. No
other node contains this point either, so the central node in this case is not
redundant.

There are many more situations where the node is found non-redundant. They were not considered challenging for the algorithm and were not studied explicitly in the test suite. Many of them can be found in the subsequent tests.

In the *Algorithm Tests* the behavior of RNS algorithm was demonstrated in
some situations. It was not possible, however, to observe the ability of the
node to change its redundancy status with the flow of time, according to the
changes in its neighborhood.

In the tests below the focus is again put on the central node (given the number 0). The position of it neighbors will be changed to prove that it is able to adapt its status to the current situation.

Lets begin with *Situation 5* as it provides us with a very
interesting and challenging, but at the same time fragile example of redundancy
situation.

First some tests are conducted to prove that moving node 5 around (which is the only node, who is not an RRN of node 0) will not influence the status of the node 0. The reason is that once a node becomes redundant and changes it status it will only run the RNS algorithm if it receives an update concerning one of its RRNs. Other nodes, like node 5, will not be able to trigger the algorithm. This allows the node to stay in a sleep mode for a longer period of time if a small group of RRNs is chosen.

Moving node 5 alone will not let us check any other behaviour of RNS, so the
next test moves away node 8. This is one of central node’s RRNs so the
algorithm is triggerred and the status of the node changes to non-redundant
(see *Situation 1*).

There are a couple of ways to change node’s 0 status back to redundant. The
most obvious would be to move node 8 back to its previous position. Another one
would be to move one of existing RRNs to “patch” the “hole” left after removing
node 8. This is shown in *Situation 2*.

Alternatively an external node could move into the remaining gap.
*Situation 3* shows node 5 taking place near node 8 and making the
central node redundant again.

Not only the neighbors can influence central nodes redundancy. It can move
itself as well. If node 8 and central node from *Situation 3* moved
slightly it would not cause a change in central node’s redundancy status. This
is shown in *Situation 4*.

If central node keeps moving it will eventually float away from its RRNs and
will no longer be redundant, as shown in *Situation 5*.

The above situations prove that RNS is capable of properly reacting to certain mobile situations.

Testing RNS algorithm cooperation with routing protocols requires a full node configuration and is only visible when simulator is started. Therefore those tests are not typical test suites but were shown as examples.

To run the example execut the following command::

`./waf --run rns-dsdv-example`

The situation is as shown in Figure *DSDV Example*. It demonstrates a
very basic bahavior of the RNS algorithm. The data provided to the algorithm
comes both from the DSDV protocol and from RNS updates.

There are three control prints. One is at the beginning of the simulation to show that all the nodes are non-redundant at the beginnig. Another one is printed after five seconds when the nodes have discovered that one of them is redundant and another one after 10 seconds to show that the status is maintained.

The example proves that RNS works correctly using DSDV routing protocol.