Abstract
The SLIP course, Computer science, 4th year, Edinburgh University requires groups of 5 to design and build a full and working system comprising both software and hardware. The hardware this year took the form of ProSpeckZ mobile computing devices. Using these we were first to think of an then build a working system.
This report gives a rough outline of the project undertaken and provides details about the sections on which I worked. Details for other group members contributions, thus further detail on the system, may be found on their own pages.
Introduction
There were several initial ideas for the project to undertake including:
- Building Management System
- Miniature cooperating robots to map out an area
- Living environment automation
Selected Project
Building navigation system for the blind
This project was selected because it made strong use of the Speck platform in that there was a mobile element that required to use the radio for communications and needed to do do a modest amount of processing.
The system's aim is to allow a blind user to navigate an unknown building along a path created from their current location to their intended destination. This was to be achieved by having a network of stationary (wall mounted specks) at key navigational way points and the user wearing a mobile device that would inform the user about how to proceed at each way point.
System Design
This section will provide a basic overview of the system with details for the parts I worked on detailed below. More detail for the other sections can be found on the pages of the group member who worked on them.
Requirements
A set of requirements was created on the first meeting:
Functional Requirements
High Priority (Integration Stage 1)
- The system must store and provide map data to its users.
- The system must be able to calculate an optimal path between a fixed node on the map (reception) and any other node.
- The system must be able to guide the user along this optimal path.
- The system must detect deviances from this path, and correct the path if necessary.
Medium Priority (Integration Stage 2)
- The system should be able to re-map a path from any location within the influence of the system, to a new destination.
- The system should be able to determine the facing/orientation of the client in order to avoid path deviation.
- The system should provide a central display of the positions of its clients within its influence.
Low Priority (Integration if Time Available)
- The system may be able to provide environmental data about temperature, etc.
- The system may be able to gather statistics on traffic flow and feed this back into path finding.
Non-Functional Requirements
High Priority (Integration Stage 1)
- The system must be simple to use, to the degree that someone previously unexposed may effectively utilise it.
- The system must be robust, in that mobile devices should be able to withstand daily use.
- The system must be reliable.
- The system must be accessible to someone visually impaired.
Low Priority (Integration if Time Available)
- The system may provide an extended mobile interface to those able to use it.
Design
The full system has the following structure:
The mobile speck communicates with the wall specks using the network, which in tern uses the wall speck network to send messages to the server speck. The server speck uses it's UART to forward messages to the sever running the Java sever program. The sever program can have several client programs via the network of type Reception or Editor which can communicate back down to the wall and mobile specks.
When a user approaches a new wall speck the mobile speck tells the wall speck the next node on it's path, the wall speck then instructs the mobile speck to tell the user to take appropriate action. The user has a vibration motor positioned on each hip and an ear piece for verbal instruction. The wall speck may, for example, tell the mobile speck that the next node is to the left by 90 degrees, the mobile speck will vibrate the left-hand motor and use it's speech chip to say “turn left 90 degrees”.
Instructing the mobile speck about it's new path is done from the Reception GUI:
The user clicks on the start node then the end, the path is shown on the map, pressing the send button sends a request to the server for a packet to containing the path to the mobile speck over the speck network.
The Editor GUI is for installation and allows the topology graph to be edited and nodes positioned on an image of the building for easy manipulation, this editor can send an updated Graph to the server to update it.
The server can also be instructed to load and save a Graph object from/to a file.
Implementation
The overall structure of the project is as described above.
Due to the limited bandwidth and high latency of the wall speck network communication across it was kept to a minimum. There is an initialisation process which must be performed on each wall speck which informs it about all its adjacent nodes and the bearings to them, this means that the speck does not need to request this information from the server each time.
The sever/GUI communication is handled by RMI in a client/server mode as would be expected; there are no callback methods. More details for this area can be found below.
A third class of GUI that can connect to the server is the NetTest GUI, this small application allows injection of packets into the network for testing, packets can be either path, location or path request type, arbitrary type packets are also supported.
Final Implementation With respect to Requirements
Functional Requirements
High Priority (Integration Stage 1)
- The system must store and provide map data to its users:
The system must be able to calculate an optimal path between a fixed node on the map (reception) and any other node.
The Graph can provide an optimum path from any node to any other node, this requirement is a subset of that functionality.
Storage is achieved with the Graph object contained in the Server object which provides access to the necessary elements of the graph.
The system must be able to guide the user along this optimal path.
The network of wall specks and the mobile speck once initialised provide navigational information to the user as they pass each wall speck.
The system must detect deviances from this path, and correct the path if necessary.
Deviation from the path by a single wall speck will result in the user being instructed to go back to the path, further deviation will result in the path being regenerated to the destination from the current location to the destination along the new optimal route.
Medium Priority (Integration Stage 2)
The system should be able to re-map a path from any location within the influence of the system, to a new destination.
This has already been achieved.
The system should be able to determine the facing/orientation of the client in order to avoid path deviation.
The compass provides this functionality once calibrated.
The system should provide a central display of the positions of its clients within its influence.
This is achieved be the speck network informing the Server when each client moves between wall specks, this information is then available to the GUIs to display.
Low Priority (Integration if Time Available)
The system may be able to provide environmental data about temperature, etc.
Not Implemented
The system may be able to gather statistics on traffic flow and feed this back into path finding.
Not Implemented but could easily be added to the system as the information to recode such statistics is readily available.
Non-Functional Requirements
High Priority (Integration Stage 1)
The system must be simple to use, to the degree that someone previously unexposed may effectively utilise it.
The reception GUI allows easy destination selection, once that is sent to the mobile speck the user is instructed both verbally and by vibration as to the direction to turn and how to proceed.
The system must be robust, in that mobile devices should be able to withstand daily use.
Not Implemented, however all that must be done is to place all the components in suitable containers, and, in the case of the mobile speck, affix securely to a belt.
The system must be reliable.
There are small issues with reliably detecting the presence of a new way point, however, it just takes a little longer in some cases. Information about the locations of mobile specks is not sent using the reliable communication layer, this results in it sometimes being lost, as it was a low priority this is not an issue. The problem may also be fixed quickly by passing it through the reliable communication layer.
The system must be accessible to someone visually impaired.
The verbal and vibration communication should make the system easily accessible to a visually impaired individual, however the initial path set-up must be done by a sighted receptionist in the present implementation.
Low Priority (Integration if Time Available)
The system may provide an extended mobile interface to those able to use it.
Not Implemented
Project Management
Task assignment
Initially tasks were assigned to individuals but as the project progressed the division of work became more fluid and the group was divided into two parts, the Java side and the speck side.
The Java team, myself and Andrew were responsible for the Server, including the Graph and the GUIs. The division in our sub-group was that Andrew worked on the GUIs (excluding the NetTest GUI) while I worked on the Server and the Graph, there was a small amount of crossover in that I worked on the GUIs to a small extent and there are small parts of the Server that are Andrew's.
The other part of the team worked on the Specks almost exclusively, Richard worked on the Network, the UART and Java interface to the Speck network. The other hardware was handled by Tom and Mark as chronicled on their pages.
Communication
The Java sub-group had to decide on the Remote interface for the server to be accessible from the GUIs. The hardware team had to organise the interconnection of several hardware sections. There was little need for the two parts of the team to communicate apart form where information was passed between the two sides, this was nicely encapsulated in the single Server class through which all information in the system flows. This meant that I acted as the interface between the hardware and software sides of the group, arranging what and how data got form the physical speck network to the server's Graph representation and finally to the GUIs. Richard appearer to become another bridging point on the hardware side, bringing all the components together and writing the interaction logic.
My Sections:
Graph
Requirements
The graph is the object that stores the topological layout of the static wall nodes.
The graph has several functions:
Store the topology of the wall nodes positioned throughout the building by storing the links between adjacent nodes. Adjacent nodes being those that can be walked between, e.g. the ends of the same corridor, but have no nodes between them.
This implies the ability to create nodes and links.
Store the locations of the nodes, both floor and position on the floor.
Allow shortest path between two nodes to be found and returned as a list of nodes taken to get there.
Return a list of nodes adjacent to a given node.
Find the bearing between two nodes from a given node.
Find the distance between two nodes.
Design
The graph has the following structure:
Key:
This is a small object containing only the Id number for a node and a over-ridden hashCode() function. It is used as a key for the HashMaps in the nodes and in the graph itself.
Graph:
The Graph object itself contains a HashMap of nodes for fast access, accessor methods for the Node and Link data, methods to add and remove nodes and links. Finally there is a method for generating a path from one node to another. The Nodes and links themselves are private to the graph so that the graph remains consistent and encapsulated.
Node:
A node contains a HashMap of links to other nodes indexed by the key of the target node, this makes it easy to determine the adjacent nodes by getting the key set from the HashMap. All methods are protected to preserve encapsulation.
NodeData:
This class is contains all data unique to this node (except Id), it is public and is one of the two classes that can be extracted from the Graph and edited externally. This form fosters code reuse as the Graph itself can remain unchanged the only parts that must be changed are the Node and Link data classes.
Data contained in this class is: The nodes floor, the coordinates of this node and if it links to floors above or below.
Link:
This is the class that is created to represent the connection between two nodes. The link contains the key of the target node and a LinkData object.
LinkData:
Like the Node data the LinkData object is used to store information about the link not directly related to the topological layout of the graph.
The LinkData object in this implementation contains only a weight which can be used to represent the pass ability of this particular connection, for example a flight of steps will be harder to pass so a slightly longer path may be chosen over a path containing several sets of stairs.
Graph:
The graph object is the encapsulation of the topology of the network of nodes that makes up the system.
It was decided that for the internals of Graph should be protected from external modification, this is achieved by making all access to topological changes pass through the Graph object so that all changes occur in a well defined way. The kind of problem that is avoided is as follows: A node is removed, however the links to this node are not, this results in the node not being drawn by the GUIs or appearing in any node listing, however, because there are still links to it from other nodes it is still considered by the path finding algorithm. Paths may then be returned containing that contain non-existent nodes, or the system will fail trying to evaluate the length of such a path.
Another important function of the graph is to search for optimum paths between two nodes, this will be returned as a Path object.
Path:
A path is an ordered list of nodes that must be followed to get from one node to an intended another. For comparison with other paths the physical length of the path must be calculated, this may not be the real distance as weightings of links and a small penalty for each node passed.
Implementation
Implementation of the graph is as described in the design.
Node:
The node class contains a reference to the graph to perform checks on all references to nodes, if a reference is to a non-existent node an Exception is thrown, the reference to the graph is also used to dereference keys:
Node n = g.getNode(k);
The set of linked nodes is found from by getting the keyset from the HashMap:
protected Set getLinked() {
links.keySet();
}
Links to other nodes can be removed, this occurs only when a node is removed:
protected void removeLink(Key k){
links.remove(k);
}
Link:
The link class is very small and contains only the target and the target, both have accessor methods.
Graph:
Editing:
There are several methods used for the editing:
public void add(Key k, NodeData data) // add node to graph
public void link(Key from, Key to, LinkData data) // link 2 nodes both
directions
public void uniLink(Key from, Key to, LinkData data)// only in one derection
public void removeNode(Key k) // remove the given node and all links
Usage:
The methods for graph usage are:
public boolean contains(Key k) // Does graph contain this node?
public double getDistance(Key aK, Key bK) // Distance between nodes
public double getBearing(Key aK, Key bK) // Bering between nodes
public Set getNodeKeys() // Set of all nodes
public NodeData getNodeData(Key k) // Get data for this node
public Set getLinked(Key k) // All nodes linked to
public Path getPath(Key from, Key to) // Get path for these two
There are also methods to load and save Graph objects:
public static void save(Graph g, String file) public static Graph load(String file)
Path finding:
The path finding algorithm is a recursive depth first search of the entire graph from the start point storing all possible paths to the destination. Once all the possible paths have been found the weight of all of them is calculated and the path with the lowest weight is returned.
public Path getPath(Key from, Key to) throws NoPathFoundException,
NoSuchNodeException{
NodeData n = getNodeData(to); // Do this to check start and
n = getNodeData(from); // end both exist.
Path current = new Path(from); // Start at the begining
LinkedList paths = new LinkedList(); // list of paths found
getPathRec(current, paths, to); // call recursive function
if(paths.size() == 0){ // Catch no paths
throw new NoPathFoundException();
}
Path best = null;
double best_w = Double.MAX_VALUE;
Iterator i = paths.iterator();
while(i.hasNext()){ // Iterate through all paths found
Path p = (Path)i.next(); // and return the best
if(p.weight(this) < best_w){
best = p;
best_w = p.weight(this);
}
}
return best;
}
private void getPathRec(Path current,
LinkedList paths, Key to){
Path visited = (Path)current.clone(); // List of visited nodes
visited.remove(); // maintained to avoid loops
if(visited.contains((Key)current.getLast()) ){ // In a loop,return
// Been here.
current.remove();
return;
}else{
if(to.equals((Key)current.getLast())){ // Got to destination
//GOT THERE!
paths.add(current.clone()); // add this path to the list
current.remove();
return;
}else{
Set linked = null;
try{ // get list of where we can go
linked = getLinked((Key)current.getLast());
}catch(Exception e){
System.out.println(e);
}
Iterator i = linked.iterator();
while(i.hasNext()){ // Recurse allong each possibility
Key k = (Key)i.next();
current.add(k);
getPathRec(current, paths, to);
}
current.remove(); // after that backtrack
}
}
}
Testing
The graph was tested for each section at a time, first editing then usage.
Tests for editing were performed by creating a graph and printing out the number of nodes and the links present and the state of those links. Once the GUIs were completed the editing could be examined intuitively.
The second stage of testing as to have a graph set up and all the information form the previous set of tests and compare the results from the usage methods and the test outcomes.
The path finding had to be tested as a separate system due to its complexity and the subtlety of potential errors.
First the number of paths found had to be counted for simple (or as hard as I could work out) graphs and my results compared with the path finders.
Secondly the selection of the best path had to be checked, this was achieved by creating a specific maps with single paths, calculating their values by hand then comparing them with the results from the system.
The path finder still outputs the debug for this process.
Evaluation
The Graph provides a efficient method for storing the topology of the speck network and performs its function reliably and should scale well due to the use of HashMap for lookups.
The Path finder will work reliably and quickly even with large buildings as the algorithm shows worst performance with high levels of interconnection, buildings tend to have low interconnection and tend more toward a tree than a heavily cyclic graph.
The introspective nature of the Nodes (the nodes containing the graph that contains themselves) concerned several members of the group, this can be removed with little effort but this is not needed as it affects nothing.
Server
The Server was the centrer of the system from a software point of view. All information on the system passes through the server or is requested from the Server.
The flow of data through the Server is bi-directional, the speck network updates the positions of Mobile specks for the Reception to read and the Reception can send paths to the mobile specks.
Requirements
The Server has four functions:
Store and provide access to a Graph object which stores the locations and organisation of the Speck network from both the GUIs and the speck network connection.
Store, maintain and provide access to a list of “People”. This is the list of active mobile specks along with their locations with respect to the nodes in the network.
Accept send path instructions and forward them to the network.
Communicate directly with the Speck network to satisfy requests, send paths and initialise nodes. (Note that the communication code itself is written by Richard, however it calls methods from the rest of the server class.)
Design
The server has two “interfaces”, one to the speck network, the other to the DICE/Internet/other network from which the GUIs can connect. The speck connection will be written by Richard but will call methods in the server written by myself. The GUI side will be written using RMI due to the simplicity of implementation and ease of specification using an extension of the Remote interface.
Implementation
The Server implements the following interface:
public interface ServerRemote extends Remote {
public Graph getGraph() throws RemoteException;
public void updateGraph(Graph g) throws RemoteException;
public void saveGraph(Graph g) throws RemoteException;
public Graph loadGraph() throws RemoteException,
GraphIOException;
public void sendPath(Key k, Path p) throws ServerException,
RemoteException;
public People getPeople() throws RemoteException;
// Initialise the given index of wallnode with data from
// the map.
public void initWallnode( int key ) throws RemoteException;
// Same, for everything.
public void initAllWallnodes() throws RemoteException;
public void sendPacket(int sendTo, String packetData, byte type)
throws RemoteException;
public PacketList getOutgoingPackets() throws RemoteException;
public PacketList getIncomingPackets() throws RemoteException;
}
The Server functions:
Store and provide access to a Graph object which stores the locations and organisation of the Speck network from both the GUIs and the speck network connection.
The graph is made accessible using the getGraph method which returns the Graph object to the caller.
Store and maintain a list of “People”. This is the list of active mobile specks along with their locations with respect to the nodes in the network.
The people are stored as a People object that is updated by the speck network connection, this is made available using the getPeople remote method.
Accept send path instructions and forward them to the network.
The send path method allows the GUIs to send paths through the Server to the Speck network.
Communicate directly with the Speck network to satisfy requests, send paths and initialise nodes. (Note that the communication code itself is written by Richard, however it calls methods from the rest of the server class.)
Pass through methods for the graph allow access to all the required functionality so the speck network handling functions can perform as required.
The server, when started tries to load a Graph
from a file, If that fails it will fall back to an empty graph.
GUIs must obtain a working copy of the graph for them to work. This may lead to inconsistency across the GUIs if one of them is an Editor as the graph could be edited then updated back to the server. Before the map is updated on the server, if a reception GUI starts and obtains a copy of the old map, once the update occurs paths sent from the reception may be compatible. This should, however be dealt with by the exception system on the server. This system was kept because, although extending the remote interface to include the Pass through methods is no problem in itself, the network load and latency of making so many method calls would be very slow.
Exceptions:
There are a multitude of exceptions that can be thrown by the server and graph:
Server Exceptions: NodeNotSpeckException no node found for the given key. NullPathException path given by a GUI is null. ServerException General exception that is extended by other exceptions in the server package. Graph Exceptions: GraphException General exception that all other exceptions in the graph package extend. GraphIOException An IO exception has occurred while loading or saving. LinkException General link exception that all link type exceptions extend. LinkExistsException The link being added already exists. NoPathFoundException No path can be found for the given node pair of keys. NoSuchLinkException There is no link between the given nodes. NoSuchNodeException The given key cannot be dereferenced to a node. NodeAlreadyExistsException The given node Id already exists in this graph. NodeCollisionException The node being added is too close to an existing node. NodeException General node exception that all node exceptions extend. NodeOutOfBoundsException The node is outside the bounds of the graph.
Testing
Each function must be tested separately:
The graph returned by the getGraph method was determined to be the same as the one on the server.
A set of people were created and added to the graph, their position and multitude were observed on the GUI and debugged to the console to assure that there were the correct number in the correct locations. Position updates were then simulated from the Speck network and the changing positions were observed and scrutinised.
The send path function was tested by debugging to console at each stage and comparing the path list.
The Pass through functions could be assumed to work correctly as they simply call the functions in the graph.
Evaluation
The server performs its task well, there are several problems however:
The synchronisation problems with the graph mentioned earlier. This problem could be solved by adding a callback to the GUIs to inform them that the Graph on the server has changed and prompt them to update their copy.
The GUIs have to poll the People list, this, though functional is not very elegant, a similar callback system could be implemented here as above.
Network Test GUI
The Network Test GUI was written to inject packets into the network for testing.
Requirements
Three packet types must be available; path, location and path request.
There must also be an arbitrary type in which the type identifier byte can be set.
Low priority functionality:
Scrolling lists of incoming and outgoing packets.
Design
The injection of packets will be done by the server which will be instructed to do so by RMI calls, the argument to the calls will be a hex dump of the packet itself.
The GUI itself should have a list of packet types including the arbitrary type, this will select the value of the packet's type field, this will be editable in arbitrary mode. There should be a text box to enter the hex for the packet body.
Implementation
The packets are sent via the server using this method from the remote interface:
public void sendPacket(int sendTo, String packetData, byte type)
Once packet sending was finished the network had been set up and was functioning the need for the scrolling packet lists was reduced in importance even further and was abandoned to focus more effort on more important areas.
Testing
The packets were observed at the server and the hex was debugged to console as the packet was sent. Packets could also be targeted for the server speck and would thus be bounced back up the UART and debugged, this gives a round trip check.
Evaluation
The NetTest GUI became a extra feature within the Editor GUI which is where it should reside as a debugging tool.
The NetTest tool was never completed, the scrolling packet lists were never implemented, the server remote interface has the needed methods:
public PacketList getOutgoingPackets() throws RemoteException;
public PacketList getIncomingPackets() throws RemoteException;
So finishing it would be almost trivial.
Even though incomplete the NetTest GUI performed its purpose as a simple testing of the network and protocol design.
Other Contributions
Helped create the overall system design with central server architecture which is very reminiscent of the SDP system that I devised.
Mark and myself recorded the demonstration video for the presentation.
Played a large part in setting the hardware up for the final presentation and operated the mobile speck and demonstrated its functionality to several individuals.
Suggested the use of a hysteresis function to stop the mobile speck bouncing back and forth between two nearby wall specks.
Created the background image for the GUIs and created the graph used in the presentation.
Helped with testing the speck network reliability.
System Evaluation
As the demonstration showed, the system performed very well.
Limitations
There are currently several limitations to the implemented system:
The Graph synchronisation issues.
Due to the addressing scheme being used there can only be 32 wall mounted specks in the system. This should be easy to fix by increasing the address size.
Reliability of the mobile speck location update packets.
The packaging is currently not particularly robust (duct tape and blue tack), repackaging into system boxes would be a good start.
Finishing the NetTest GUI would make further development on the system easier.
Success
Overall I think we all feel that the system worked very well and achieved everything we could have reasonably have hoped to.
Evaluation
The team worked together very well, the work appears to have been divided well and communication was good.
Partitioning the group into two parts resulted in the smaller meetings which are much more productive as they are generally focused on particular issues and specific problems which all the members know about.