Student project suggestions

  Contact to Eiko Yoneki (eiko.yoneki@cl.cam.ac.uk)


 Project 1: Add mobility simulation to Java Network Simulator

    Project Goal: Design and implement mobility support to Java based network simulator. Additionally implement a demo application to test mobility simulation.   
  Summary:

The Java Network Simulator is a Java implementation of the ns-2 simulator originally from Berkeley. It is not as complete as ns-2, but it is a lot more accessible to programmers not familiar with Object Tcl. JNS allows developers of networking protocols to simulate their protocols in a controlled environment. The simulator then produces a trace file (same format as NAM trace files) that can be viewed in a network animator such as Javis (Java Visulalizer). Javis is the Java implementation of Nam, the network animator which can show animations of Nam trace files. 


JNS is a project originating from University College London. The latest version is available from sourceforge, and this version adds multicasting, multithreading and dynamic scheduling, thus allowing dynamic scheduling of events. In addition, JNS now supports simulation of "real" Java network applications.


The task is adding mobility simultation to JNS. I worked on the preliminary idea that is adding a thread within the dynamic scheduler, with breaking and establishing links depending on configuration information. Pursue this idea further or go for the challenge of a new design. An important part of this project is understanding mobility patterns and design rich mobility simulation, so that the simulation result will be more valuable. The most popular and simplest mobility pattern to implement will be "Random Way Point" algorithm. You might extend the concept of mobility such as policy based node mobility to simulate real world environments.


A candidate of demo applications will be a simple group communication system over mobile ad-hoc network,  and existing multicast protocol implementations can be used.

    Remarks:

Interest in mobile ad-hoc networks. Some knowledge of Java networking programming, threading, RMI, and multicast.

 

Project 2: Dynamic Group Creation by K-means Clustering for Group Communication

    Project Goal: Design and implement an ad hoc group communication mechanism such as sharing the taxi ride to the same destination.   
  Summary:

K-means clustering generates a specific number of disjoint, flat (non-hierarchical) clusters, and the K-means algorithm is used for similarity-based grouping. The goal is to divide the objects into K clusters such that some metric relative to the centroids of the clusters is minimized. Various metrics to the centroids that can be minimized include:

  • maximum distance to its centroid for any object
  • sum of the average distance to the centroids over all clusters
  • sum of the variance over all clusters
  • total distance between all objects and their centroids

The metric to minimize and the choice of a distance measure will determine the shape of the optimium clusters.

The typical operation of K-means is:

  1. place K points into the space represented by the objects that are being clustered. These points represent initial group gravities.
  2. assign each object to the group that has the closest gravity.
  3. when all objects have been assigned, recalculate the positions of the K gravities.
  4. repeat Steps 2 and 3 until the gravities no longer move. This produces a separation of the objects into groups from which the metric to be minimized can be calculated.

The goal of the project is designing a simple group communication mechanism over mobile ad hoc network environments. The group should be created in temporal manner after exchanging interests among the devices. It requires a simple gossipping routing to exchange the intests among devices/nodes. The main challenge is to create optimal groups among various interests using K-means clustering algorithm.

    Remarks:

Interest in mobile ad-hoc networks, and clustering algorithms.

 

Project 3: Query Processing for Network (as the Database)

Project Goal: Design and implement query processing mechanism over the network.
Summary:

Recent advances in computing technology have led to introduce new devices: the wireless, battery powered, smart sensor. They are used for monitoring and data collection task. The sensor applications depend on the ability to extract data from the network. Often, this data consists of summaries (or aggregations) rather than raw sensor readings. This project aims to design an aggregation service for such sensor network environments. An obvious approach for doing this would be to apply traditional data-processing techniques and operators from the database community. See an example below which describes an query is distributed over the network, and an aggregated result is sent back to the quesry dispatcher. You might consider "data flow" programming approach, or embedded processor in each node. If you want to challenge, you might design a simple concurrent processor. For the programming languages, any of Java, ML, and Prolog will be possible depending on the design. 

Remarks: Good knowledge on query processing, concurrency control, and database. 

    
  Project 4: Reliability with probabilistic protocol in peer-to-peer networks

Project Goal: Design and implement reliability function with gossip algorithms in a messaging system over mobile ad-hoc networks.
Summary:

Reliable point-to-point communication is usually achieved by applying TCP. In messaging middleware with asynchronous publish/subscribe paradigm, messages may be sent without generating a reply, and they may be processed hours after having been sent. The communicating parties do not handle how messages are transmitted and when they are processed. Thus, the messaging system must provide guarantees. It is not sufficient to know that a message has reached the messaging system that sits between the message producers and consumers. It is necessary to guarantee that the messages will not be lost due to failure of that messaging system. Messaging systems need to provide various guarantees regarding reliability and fault tolerance ranging from best-effort to guaranteed and timely.

 

In a centralized model of messaging system, the server persists the messages in a central database; since server manages the communication between all clients, it usually implements guaranteed message delivery. Such a central database is not readily available in a mobile ad-hoc network environments, as the availability of any one node at all times is not reliable. In mobile ad-hoc networks, there are several multicast protocols, and they are good candidates to support messaging systems. One approach to provide reliability to those messaging systems is using probabilistic protocol, "gossiping algorithm".  Probabilistic protocols are protocols that guarantee delivery with a certain probability. Although not as safe as guaranteed protocol, the probabilistic protocols typically have less restrictive assumptions and constraints associated and reduced overhead, thus making them in many cases the better choice for mobile ad-hoc networks.

 

You can implement a simple messaging system by using a multicast protocol in mobile ad-hoc networks before designing the gossip based reliability support. Alternatively, I will provide one, then you can build gossip algorithm on top of that. There is an effort to refine gossiping algorithm to reduce the noise and to improve reliability such as combining gossip-based and semantic-based reliable protocols. The followings are candidate gossip algorithms.

 

1.     Anonymous Gossip : Gossip is a technique where nodes share the data they process with other nearby nodes, such that all nodes share a consistent view of what has been communicated. A general gossip based reliable multicast involves two phases: an unreliable multicast mechanism is used to multicast the message, and then the gossip phase is initiated, in which gossip is used to recover any lost messages from other nodes that have received them. A gossip message is sent by nodes wanting to gossip after a multicast has finished. Each node randomly selects one of its neighbours and sends a gossip message to it. If the receiver node is a member of the multicast group of sending, the node will randomly decide whether to accept the message or to propagate it. In order to propagate a gossip message, a node will randomly select one of its neighbours and send the gossip message to it. The accepting node will unicast a gossip reply back to the sending node that contains enough information to allow the two nodes to exchange the messages they lack.

 

2.     Route Driven Gossip : It uses a pure gossip scheme, which gossips uniformly about messages, negative acknowledgements, and membership information without requiring an underlying multicast primitive. It takes into consideration parameters of the network. It does not require a multicast primitive at the network layer and can be deployed on any basic, virtually unmodified, on-demand routing protocol.

 

Remarks: Good knowledge or interest of networking, multicast, and mobile ad-hoc networks. Java network programming essential.

 Project 5: Event Aggregation and Correlation

Project Goal: Design and implement Event Aggregation engine.
Summary:

Many applications require the event system (publish/subscribe system) to buffer and/or count events then signal them as required. For example, in financial applications, a trader needs to know when the exchange rate of pound against US dollor reaches its peak; such an event may be expressed as "The rate increased 10 times over the last week and dropped 3 times by the end of this week". You can create a composite event language or use the one created in Opera group. The event composition language is capable to specify "A without B" or "A followed by B". The project aims to develop a composite event engine with aggregation and correlation functionalities including implementation in Java. A composite event language can be designed on XML base such as extending XPath or XQuery.

Remarks: Interest in query languages. 

 Project 6: Hierarchical Bloom Filters

Project Goal: Design and implement hieracrhical Bloom filters for encoding hierarchical data.
Summary:

Bloom filters are compact data structures for probabilistic representation of a set in order to support membership queries. Each filter provides a constant-space approximate representation of the contents of a set. Errors between the actual set and the Bloom filter representation are always of the form of false positives to inclusion tests. A Bloom filter is a bit vector, and items are inserted by setting the bits corresponding to a number of independent hash functions.

 


Bloom filters apply better to data classified and represented by scalars. This project aims to create Bloom filter representation for encoding hierarchical data. There are some efforts on Attenuated Bloom Filter, and  you can use it as base or create your own design.

Remarks: Good knowledge on data structure and algorithms. Implementation in Java is preferable. 

 Project 7: Mobile Device/Web based Remote Controller on Data Repository 

Project Goal: Design and implement a remote controlling function to the data repository in the back-end computer.
Summary:

This application resides in mobile devices such as PDA or mobile phones that allows to print, fax and e-mail data (documents, multimedia etc) remotely to the nearest printer or fax machine. The user can browse through large data repository by looking at only the name of files, summaries, or full documents. Once selected, data can be forwarded to any email address or fax machine for full viewing. The remote controller can be extended to add web access or email access.

You will design a gateway between different devices and data access components in back-end computers. Within the gateway, transforming data format is required, and utilizing XML schema is essential. You can add data transformation components as much as feasible within the given time. For example, you can implement voice based summary function, or short digest of multimedia data, if you can. For example, you can add location based service to decide, what Kinko's printer to use for printing. In addition, what devices and what communication protocols are depending on given time and resources. One would be minimum to show concept proof.

With this application, when you forget your powerpoint files for the presentation away from your office, you can use mobile phone to look through your file repository, then print to Kinko's printer nearby or email to the meeting organizer.

As an extension, you can add an authentication and access control component in the gateway.

Remarks: Good knowledge of XML, Java JSP and Servlet programming.