%----------------------------------------------------------
%---- Preamble --------------------------------------------
%----------------------------------------------------------

% Document class: IEEEtran
\documentclass[
  11pt,                           % Text size
%	draftclsnofoot,
%	journal,
%	onecolumn,
%	peerreview
% journal,                        % Journal Mode
% letterpaper                     % Paper size	
%	conference,
	final
]{IEEEtran}

\usepackage[T1]{fontenc}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage{booktabs}

%----------------------------------------------------------
%---- Title -----------------------------------------------
%----------------------------------------------------------
\title{Telematik Projekt - Wireless Embedded Systems}



\author{%
	\IEEEauthorblockN{Adri\'{a}n Anto\~{n}ana G\'{o}mez, Carlos D\'{\i}az C\'{a}novas\\
    \IEEEauthorblockA{%
    Computer Systems and Telematics\\
    Institute of Computer Science\\
    Freie Universit\"at Berlin, Germany\\
    {antonana@zedat.fu-berlin.de, cdiazc@zedat.fu-berlin.de}
    }%
  }%
}%

\begin{document}
\maketitle

%----------------------------------------------------------
%---- Abstract --------------------------------------------
%----------------------------------------------------------

\begin{abstract}
This is the first technical report of the \textquotedblleft telematik projekt\textquotedblright \  lecture of the Freie University in Berlin for the winter semester 2008/2009. In this report will be discussed the main points concerning the project which lead to the implementation of a routing protocol in a wireless embedded system. In this document, an usual scheme will be found in which some routing protocols will be presented along with a deeper explanation of the one implemented. Also, the practical cases tested will be exposed to illustrate the procedure of creation and testing of the project.
\end{abstract}

%----------------------------------------------------------
%---- Main Matter -----------------------------------------
%----------------------------------------------------------

\section{Introduction / Motivation}
This said this project aims to the building of a complete network structure on wireless embedded systems: nodes with radio transmitters based on the MSP430 processor, by the end of the project, must have the ability to find a route to any other node in any topology, and then send a message over a transport protocol to the chosen node. This, of course, have to be done bouncing packets on intermediate nodes when the desired node is not on the emitter's range.
In the first part of the project, a routing algorithm would be implemented, this one will be the responsible for finding the path from a node to another one through the nodes in the topology and this will be tested by a simple mechanism of messages sent between nodes using the route found.

\subsection{Routing protocols overview}
To implement the routing process the path to follow was to implement an already existing algorithm rather than \textquotedblleft inventing\textquotedblright \  a new one, the decision to this was simply because an already developed and well-tested algorithm would be less problematic than a new one that could pose problems already considered and solved by other ones.
The range of routing algorithms is large, but between them a fewer are involved in wireless systems, or are able to handle correctly those kind of networks. Some algorithms have been studied: Destination-Sequenced Distance Vector routing (DSDV), Optimized Link State Routing Protocol (OLSR) and Dynamic Source Routing (DSR). DSDV in based on tables to store the paths (only the next-hop) to take and requires periodic updates, all the information is also updated when a new packet comes, Bellmand-Ford algorithm is used to decide which route to take once the information is gathered. On his side, OLSR is a proactive algorithm that uses the information on the topology obtained with control messages to compute the next hop to every single node in the network. Finally DSR, like OLSR uses control messages but for retrieving a full route to the destination every-time needed, to do so a network-flooding is done by every node so it could achieve any node in his range and then an answer is given back.
Those are part of the two most-widely known kinds of routing algorithms. Those types are proactive and reactive algorithms. Proactive algorithms tend to discover the routes before they are needed, looking-up in the network a first time and possibly regularly to have always a ready-to-use routing information. On the other hand, a reactive algorithm can also be described as a on-demand one. The nodes on a network do never store information about the routes or about other nodes. In this kind of approach, when a route is needed, for instance to send a message then the process of discovering a route is put in place delaying for a while the task. This means that proactive algorithms are better when a fast user iteration is required but reactive ones are more applicable when no messages are required for a long time.

Finally, of those above presented, DSR has been chosen. Mainly for its simplicity to implement DSR presents the features of a simple algorithm: not many considerations have to be taken on DSR apart from avoiding an undiscriminated flood, the obvious test-field problems and the specifications control are in fact little. This chose has also problems, for instance, the network traffic is huge compared to others since almost every node has to rebound traffic to let another one find a route to any other.

\section{Contribution}
\subsection{DSR workout}
As testing any software involving wireless hardware is a difficult task the decision was made to elaborate a simulator on which DSR could be tested using a big range of topologies. The DSR implementation was the one explained on the next sections of this document. There, every single instance of it will be in itself a node and between instances the communication is made using sockets.
This simulator, UDP based, was build along a topologies generator so large routes could be easily designed. One of the main problems encountered with the simulator was that being single-threaded on a fast computer in a loopback network device, lots of messages got lost during the procedure since the UDP stack discards them once sent and the node supposed to receive it was busy with I/O. This was solved introducing a wait before any sending, this way all the nodes had the time to resettle and perform the I/O tasks before waiting for a new packet.
To test the full functionality of this simulator, it was choose to compare practical real-life results performed (see next sections) with the ones obtained in the simulator, reproducing the same topologies. The results were very different of course, since simulator is network based and environmental effects free, no matter how big a topology was the results were always optimal as no requests could be lost. Also various randomly-generated topologies were tested with from a few nodes (5, 10\dots) up to around 100, in any, case again, results were optimal and not comparable to real-life tests.

\begin{figure*}
\resizebox{18cm}{!}{%
\includegraphics{topo.pdf}}
\end {figure*}

\subsection{Final choose}
\subsection{Developed implementation}
The implementation made fully-covers the basic features of finding a route through a topology and avoiding the repetition of messages to eliminate the infinite-loop problem caused in some algorithms.
As said, DSR uses control messages to perform its task: finding a route. Those messages are called \textquotedblleft route request\textquotedblright \  and \textquotedblleft route reply\textquotedblright. When a route request is released from a node this means this node wants to find a path to another node indicated in the message and when a route reply is released, it means this path has been found and is being transmitted back.
Route request messages are always broadcast flooding the network and every node that receives a route request packet has to rebroadcast it unless it has already done it. This way, the message will find its way through all the nodes until he reaches the final destination gathering information of the path it has traveled and storing it into the message, this done a route reply message is sent.
Route reply messages are sent from the final destination node as specified in a route request packet; a route reply message can never be sent without a previous route request. Because the final node knows the path traveled by the request it can now send the reply back to the emitter not flooding the network but following the route until the initial source node, this saves traffic and is also a minor way to ensure that the gathered path is available for transporting messages. Of course every node that receives a route reply packet has to send it to the next node in the list.
Even though this could lead to problems like packets-loss, over flood\dots \ methods are stated to minimize those issues. A cache system can be implemented to avoid requests from being sent without need when a path is already known. Also acknowledgment systems are contemplated to ensure every reply packet is sent back and that every link is still "alive" when this reply is sent. Since we are in a possibly-mobile environment those checks could be necessary if a node is in movement while those tasks are performed and it is part of the process.

As for the simulator, the main problem encountered was the fact that too fast responses from the node made impossible the task of receiving by others which were still occupied with other tasks. Again to avoid this, between the sending of a message and the next a certain time was respected. A new problem also found during the implementation was that synchronization was needed between the functions that perform a task (being the task divided in various functions) thus, will then need to know each other and what were they doing, for instance, when a route request is released no messages can be sent or any other request processed. This should simplify the whole implementation on a \textquotedblleft single-task\textquotedblright \  way, and by the way save traffic, as seen in the further evaluation sections, many operations generating much traffic lead to messages getting lost in their way. Global variables in the modules are used on this purpose, since every function can control and modify them.

\section{Evaluation and results discussion}
\subsection{Testing procedures and results}
To perform efficient tests, first some topologies had been designed, and from that point a series of rules had been established to allow simplifying the comparison task between them. To do so, the benchmark will be messages sent between nodes in the topology using a previously obtained route using DSR. After this, different amounts of messages (without a new route request) will be sent with different payloads, everything, in order to obtain an accurate view of the influence of the payload size in the transmission quality as for the influence of the topology configuration. On every case the payload sizes will always be: 5, 20, 50 and 100 bytes (no more than 127 bytes packets are allowed by libscatterweb), and the number of messages will be, between any new route request: 20, 50, 100 and 500, and in some cases 1000. Also the tested topologies were those following.

\subsection{Topologies}
Chain: with only one connection between each node. With a chain-like topology the main factor to observe is the influence of the number of hops in the lose of messages, this could allow to design effective organizations in real-life implementations.

Fully-meshed: every node see all the other nodes. With fully-meshed topologies the main issue that should be observed is the possible influence of the nodes between them in their radio performance.

Arrow and similar: in this kind of topologies a group of nodes are in full-mesh organization, meanwhile one or various of those has contact with an isolated node, outside this group, this topology will allow to test how well a message can go through a group of nodes that would generate interferences.

\subsection{Results}
Some representative results are for instance the ones obtained in multi-hops topologies, for a 4 node / 3 hops configuration when packets were 5 bytes long, loses were around 34\% but when come to bigger packets, like 100 bytes ones, loses were up to 97\%. This effect was considerably reduced on 3 nodes / 2 hops topologies where loses started at 2\% for small packet and were up to 11\% for bigger ones. Despite this, an interesting result has to noticed, for 3 nodes chained topology when sending packets of around 50 bytes the loses were smaller than for smaller ones; even though the tests were repeated several times the effect reproduced keep appearing maybe for some environmental reasons because with this packet size hardware behaved differently with other topologies. Of course with 5 nodes chained topologies loses were much higher up to 100\% for packets below 50 bytes long. 

The results show some interesting points. Those are explained in reference to their topology relationship.
Fully-meshed: on every single fully-meshed topologies the results were perfect, no loss of packets despite their sizes, also the number of nodes didn't seem to influence this by the above commented interferences. So, those, should not be considered as a problem when configuring a fully-meshed network.

Chain: for the chain topologies the results were truly influenced by the two major factors previously presented. First the message size in almost every case influences by making the link quality worst the bigger it is, even though, this influence is observable it augments slowly. A big difference can be observed instead in relation to the number of hops, single hop networks perform perfectly, but the introduction of more could make it almost unreliable, this effect, by the way, adds up with the previously described, and as it can be seen networks with 3 or more hops, sending big messages lead to almost 100\% of packet loses.

Arrow and similar: even if the cases tested show a good performance it is clear that in some other cases of this same topology, the number of hops (when more should be introduced) will affect as for the chain networks. It has to be said that so few of those topologies were tested because of the practical difficulties to set them up.

\subsection{Results discussion}
A word about route requesting should be said apart from the explained tests. On every single topology in which nodes were too close the major problem resulted in obtaining a route. This looks to be due by the fact that a route request in DSR requires way much more traffic than a simple message sent because every single node will rebroadcast a request to every node in his range and so on.


The tested topologies resulted of a configuration and testing procedure that lead to some observations; setting up some type of topologies were impossible due to the \textquotedblleft environmental conditions\textquotedblright, these are some of the reasons observed for that. Between others, it has been observed that the proximity of nodes causes in them a decay of their transmitting and receiving capacities. When trying to build a topology of a certain form, introducing nodes on it always causes the existing ones to completely change their behavior. Also, has to be considered the interferences produced by the elements that compose the medium where the configuration is tested (halogen lamps, mobiles phones, wifi networks\dots), today, it can not be hoped to find a radiofrequencies-free zone, so the actions to take have to consider those issues too. Also, a problem found during the experimentation process was the impossibility to safely rely on power provided by batteries; commercial batteries usually provide a non-constant amount of power and lack of it fast, influencing again the transmission power. To illustrate this, the square-shaped topology was not tested because the variations of range observed in the nodes, most of the time a two hop topology was the result, but not even always on both directions, at some points the square appeared to work, but second after it stopped, so the benchmarking was then impossible. For this same reason a square-derived topology, the star was not tested neither, the introduction of a new node in the middle of the other four, influenced so-much the already precarious configuration that no topology was in fact in place but a fully-meshed one in were the nodes got out of range of others for moments and then came back.

\begin{figure*}
\resizebox{18cm}{!}{%
\includegraphics{lost.pdf}}
\end {figure*}

Some ideas were stated to try to improve the testing conditions. Surely, the best testing medium should be a Faraday cage but not very practical to implement. Otherwise, conducting material can strategically placed to improved or reduce the nodes capacities. Aluminum paper, or simple bottles of water can be used. To complete the failed square topology it can be foreseen an scenario where edged-shaped sheet of aluminum paper can be put behind each node directing the radio waves to the nodes supposed to communicate with it.
Directing the radio waves could be in fact a generic solution to the topologies problems, rising the range ensuring then that the link quality will be better. Of course this solution is not valid on networks on those which the nodes require mobility, in where the omni directional antenna are necessary.
Other solutions could be the high-reduction of the range of the nodes to make it easier to place them without conflicting with each other, the opposite is also valid, when the range is very big, it could be easier to place the nodes in precise topologies when a lot of room is available.
Finally also an idea was the ability of having constant-reliable power sources, which will make, in a controlled environment, the range of the nodes more static, and therefore, easier to test.

\subsection{Implemented features overview}
From all the functionalities explained the approach taken covers the basic functionalities, the process to discover a route: route requesting, route replying. Apart from that systems have been put in place to avoid the rebroadcast of request messages when those were already sent or systems to ensure that a route discover would be complete, as, for instance repeating the request to avoid packet loss due to interferences.
With the implemented features, the system is now able provide itself with a route to a node when desired; this route is built-up node by node gathering information about each one on every hop. For more details about the process, refer to the previous sections.

\subsection{Features not implemented, consequences}
On the other hand there is a lack of non-basic functionalities which lead to some problems on the route discovering. When a single request is made, this request expires from the precise moment in which it is used, it means, a request has to be made every single time a packet (message...) has to be sent. This all means there is no cache system at any point of the process and a large amount of traffic will be needed with its consequent battery power loss.
Also, the official DSR rfc document contemplates the possibility of an acknowledgment system in-between the nodes when a route is being sent back, this system, if created, would have ensured that the nodes can still communicate when they already have broadcast a route request message and they are now meant to support messages across them.
Finally, another system not implemented on this approach is the shortening of routes, since this problem only occurs on systems with cache it was not even contemplated. The idea is to identify, in a route in process or received that a node is not repeated provoking the route to be longer than necessary. On the implementation made, it is ensured that the route has no repeated nodes since an already broadcast route is then ignored if received from another direction.
With all this said, the major downside of those lacks is the bigger amount of traffic and the operations redundancy.

\section{Conclusion}
In this first technical report it has been shown how to build an implementation of a routing protocol in a wireless embedded system. Along with this work some interesting conclusions could be extracted regarding this project. It has to be noticed, even having a very simple implementation with not very difficult programming issues, how different the theory and the simulations are in comparison with a practical wireless system. On the performed tests results were very difficult to evaluate due to the, sometimes, impossibility to easily force some topologies and how little complicated topologies lead to very bad transmission results.
Those difficulties show how in fact any further technical complication would emerge from this environmental fact. New methods have to be created to ensure that communication between nodes is effective and reliable.
So, at the end, working with wireless hardware show how not only programming or theoretical skills could be needed, but electronics or telecommunications ones would be useful in this field to a point on which a lot of work has to be put to develop any wireless communication system from scratch.

%\input{text/1-Introduction}
%\input{text/2-Basics}
%\input{text/3-Specifics}
%\input{text/4-Comparison}
%\input{text/5-Conclusion}

%----------------------------------------------------------
%---- Bibliography ----------------------------------------
%----------------------------------------------------------

\begin{thebibliography}{}

\item
RFC number 4728, \emph{DSR protocol}\\
http://tools.ietf.org/html/rfc4728\\

\item
Andrew S. Tanenbaum, \emph{Computer Networks}, 3rd~ed.\hskip 1em plus
  0.5em minus 0.4em\relax \\
  Prentice Hall Editions

\end{thebibliography}

\end{document}
