Distributed Algorithm Design Final Summary by Vincent McHenry

Distributed Algorithm Design Final Summary by Vincent McHenry

1.      Introduction

The purpose of this project was to develop a network that has nodes that are able to coordinate themselves without the need of a centralized platform storing information.  Specifically, the research was geared towards forming a network capable of performing the Consensus Algorithm. Most networks require the aforementioned central controller in order to let them know when to advance or grant them access to the data of other points, however the possibility of having a self-aware network where each node monitors itself would be an extremely attractive commodity.

2.       Approach

a.       Agent Oriented Programming

To begin research for this theoretical network, several articles on different forms of programming were looked into. Most notably was one pertaining to the differences between the standard protocol of Object Oriented Programming as opposed to that of a lesser known method called Agent Oriented Programming. In this methodology, the programmer treats each individual object as an “agent.” Yoav Shahom, who first coined the term “agent oriented programming,” further explains that an agent is considered “an entity that functions continuously and autonomously in an environment in which other processes/agents exist or take place.” Therefore the main difference between the two trains of thought in programming is that object oriented programming creates reactionary networks, or networks that can utilize information after it has been reported from the central controller, while agent oriented programming can be used to create predictive networks, or networks that are able to understand the data stored within the network through the use of previous patterns and an understanding of each individual element in the network.

b.      JADE vs Mesh Network

Two forms of agent oriented programming that can be used to create a network fit for the scope of this project. The first one is a software framework known as JADE. JADE is a java based platform that runs entirely through asynchronous message passing paradigms, allowing for the creation of a peer to peer network.  JADE can be installed on many different platforms, or endpoints, and connects all of them through the use of a remote graphical interface. This interface serves as the focal point of the network. Users can interact with JADE through the use of HTML, the java portion of the framework is fixed as a protocol for communication and therefore cannot be edited. The fact that the network essentially comes pre-built is an extremely advantageous feature for the use of JADE, but in the end the unknowns and cons outweigh this pro. The use of a “centralized” interface makes JADE seem less ideal for the scope of this project, and while it is not fully known how much priority this interface is given, the fact it is up for question is a poor sign, especially once the mesh network was looked into more. Another, less important, disadvantage to the use of JADE is that it is only able to be installed on Java-oriented environments such as Android. While this may only be a minor issue, it is still something that is not present when talking about mesh networks.

The concept of a mesh network involves two entirely different implementation styles. The first of these is referred to as a star topology. In this setup, ever member of the network is treated as an “endpoint,” meaning that it can only relay the information at its specific site and nothing more. All communication is done through a “coordinator,” or the central controller of the entire network. Obviously this is in direct contrast with the goal of this project, so instead more focus was given to the second of the implementations, the P2P (short for peer to peer) network. In this implementation, as the name suggests, every point is able to communicate with all the others in some form or fashion. The only way the network can be disabled is if every single node within it is disabled, thus removing any fear of one system failure crashing the entire network. Mesh networks can be written in many different programming languages, and therefore can be created within multiple forms of operating systems. And, most importantly, there is no mention of an overarching central controller running the network, meaning that this style would perfectly encapsulate the goals laid out for this project.

In order to code the mesh network, it was decided that Python would be the best language. Due to the extremely easy nature of Python’s syntax, as well as the vast libraries of pre-existing functions available to the user, it made perfect sense to continue on in this way. Python already has libraries for serial communication and xbee interfacing, which will be further explained later in the paper.

3.      Equipment

a.       Beaglebone Black

The best way to begin applying the research done, several products were looked into. The beaglebone was determined to be the best fit due to its large storage capability as well as its ease of interaction. The ability to install any operating system on the board provides a level of flexibility that proves extremely useful for programming the board in whatever language needed. For this project, Linux was used as the operating system on the board. Linux comes with a preinstalled command prompt that is able to compile and execute python codes quickly and simply.

In order to interface with the board, the easiest method is to use a SSH terminal. Through the use of a USB cable, the user can SSH onto the board and gain root access in order to create files and folders within the board. The system can be interacted with through various Debian commands in the terminal of the board. Through this method it is simple and easy to upload files from one’s own computer to the Beaglebone, allowing for quick editing of codes.

b.      Xbees

The best way to code a wireless mesh network is to follow a series of protocols known as the “Zigbee protocols,” which is also part of IEEE standards. These protocols all serve to regulate the processes in which each node of the network behaves for itself and with each other. As it turns out, Xbees are actually created using the Zigbee protocols. Each of these devices can be fully configured and comes with wireless capabilities to ease communication between several nodes.

The creation of a mesh network requires the configuration of each individual Xbee. This can be done through the use of the program called XCTU. This allows for the designation of each device in order to determine its communication capabilities. Nodes can be set as coordinators, routers, and endpoints. Endpoints are unable to communicate between peers so they serve no purpose for this project. Coordinators can serve as central controllers or just slightly more advanced routers. Routers are able to communicate with all nodes. Therefore it would best serve the project to set up the Xbees all as routers in order to enable perfect peer to peer communication.

4.      Coding

For this project two separate codes needed to be created. The first of which was the serial communication code. This will enable each Xbee to be able to write and receive data from one another. The project scope allows for consecutive nodes to be able to see the data created and stored in the node preceding and succeeding each individual one. Through the use of the serial and xbee libraries available for use in Python this was made extremely simple. By using the MAC address of each Xbee, the code will be able to write and read to specific nodes, which allows for full customization of the network and which nodes can communicate with which.

The second code was the Consensus Algorithm which would be used to calculate the necessary matrix between all of the individual nodes of the network. By using the generic matrix as seen here. Each line represents the data stream that would go through each node. In order to best implement this algorithm and insure that each point is staying level with the others, which is to say no node can finish their line of data before any other node, a sleep command is used to delay every node after the multiplication of the input data with a point of the matrix is complete.

5.       Problems Faced

While trying to apply the knowledge learned through the research done for this project and integrating the hardware many different obstacles were encountered. The first such issue was attempting to image the boards. While loading the operating systems for each board, one board happened to keep deleting the image. After some time and research into the problem, it turned out to just be a simple error where the board needed to be restarted each time it was activated in order to reload the operating system onto it. In the end this was a minor setback and has little to no effect on the functionality of the board.

Another issue faced was trying to set up the WiFi that is built into each beaglebone. This problem was unexplainable, as every instruction was clearly followed, yet issues still persisted. However, this proved to be workable, as the Xbees themselves come with their own form of wireless communication rendering the native WiFi of the beaglebones irrelevant.

The final major issue that appeared during the project was the actual creation of the mesh network using XCTU. While it was successfully completed at first by configuring one node to be a coordinator and the rest as routers, an issue occurred while trying to create the network using all routers. After doing further research, this should be easily fixable by reconfiguring one of the nodes as a coordinator. The research suggests that in order for the network to exist at all at least one node must be designated as a coordinator otherwise issues will most likely occur. The coordinator label itself is just a name, as it offers the same functionality as a router, meaning that the integrity of the central controller free design would still hold up.

6.      Next Steps

Continuing on with this project, hopefully the issue involving XCTU can be quickly cleared up. Once that has been done, the two different codes can be uploaded onto each individual board and tested to prove their functionality. After that, all that is left is the continual debugging of the codes until the network is operational. Further research can also be done into the efficiency of the network. For instance, the use of Series 1 Xbees in place of the currently used Series 2 ones may prove to make the mesh network design simpler and streamline the communication process.