TestingDocumentation

Overview

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

Description of the test suites

Unit Tests

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

Header 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.

Neighbors Test

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.

Algorithm Tests

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

Simple cases

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.

_images/alg_simple_sit1.png

Situation 1

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).

_images/alg_simple_sit2.png

Situation 2

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.

_images/alg_simple_sit3.png

Situation 3

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.

_images/alg_simple_sit4.png

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.

_images/alg_simple_sit5.png

Situation 5

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.

_images/alg_simple_sit6.png

Situation 6

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.

_images/alg_simple_sit7.png

Situation 7

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.

_images/alg_simple_sit8.png

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).

_images/alg_simple_sit9.png

Situation 9

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.

Redundancy cases

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.

_images/alg_redundant_sit1.png

Situation 1

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.

_images/alg_redundant_sit2.png

Situation 2

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.

_images/alg_redundant_sit3.png

Situation 3

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.

_images/alg_redundant_sit4.png

Situation 4

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.

_images/alg_redundant_sit5.png

Situation 5

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.

Non-redundancy cases

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.

_images/alg_nonredundant_sit1.png

Situation 1

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.

_images/alg_nonredundant_sit2.png

Situation 2

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.

Mobile scenario

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).

_images/alg_mobile_sit1.png

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.

_images/alg_mobile_sit2.png

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.

_images/alg_mobile_sit3.png

Situation 3

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.

_images/alg_mobile_sit4.png

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.

_images/alg_mobile_sit5.png

Situation 5

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

Protocol operation

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.

Dsdv

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.

_images/example_dsdv.png

DSDV Example

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.