Department of Computer Science, The University of York

Dr Leandro Soares Indrusiak  
Lecturer in Real-Time Embedded Systems  

Open Projects 2012

(to be taken in 2012-2013)

Leandro Soares Indrusiak



12.lsi.1 - Applying optimisation techniques to online auctions

This is an open-ended project that attempts to use optimisation techniques to decide, given a portfolio of available auctions and a fixed amount of money, which are the products and bids that would maximise the value of the purchases. A number of interesting research questions can be addressed:
  • How can the value of a particular purchase be estimated? A simple approach is to use price references for the products of interest, but alternative approches can try to infer value from other auctions of the same product (e.g. average winning bid).
  • Can the algorithms improve their effectiveness by learning from the history of similar auctions (e.g. average winning bid, or list of winning bids over a period, such as www.bdkr.com)?
  • Can algorithms improve their effectiveness by learning from the current bidding history of the target auction? And of similar ones?
  • Can the algorithm be effectively evaluated using a simulated environment (i.e. using simple behavioural models of other bidders)?
  • Can the algorithm be evaluated live through the automatic interaction with an online auction site (e.g. JBidwatcher Java library to interface with eBay)?
  • How effective can this problem be modelled and solved with linear programming? And multi-criteria optimisation heuristics?
A successful project will consider different ways to model the problem, will choose a particular optimisation algorithm and create a scenario to evaluate its effectiveness in maximising the value of purchases for a given auction scenario (either simulated or using actual data obtained from auction websites).

Requirements: creativity and self-motivation

Desired: good background in algorithms, good programming skills (specially if the interface with auction websites is to be built), solid background in quantitative analysis

Suitable for: CS, CS/Maths, MEng, MScNC, MScSWE, MScComp, MScIT

More information:
  • E. B. Budish, L. N. Takeyama. Buy prices in online auctions: Irrationality on the Internet? Econom. Lett. 72 325–333.
  • A. Roth, A. Ockenfels. Last-minute bidding and the rules for ending second-price auctions: Evidence from eBay and Amazon on the Internet. Amer. Econom. Rev. 92(4) 1093–1103.
  • JBidwatcher

    12.lsi.2 - Scheduling topology reconfiguration in Networks-on-Chip

    This project assumes a network-on-chip architecture that can dynamically reconfigure its topology. Given a particular application, the goal of the project is to devise an algorithm that can schedule reconfigurations in such a way that it minimises the worst case behaviour of the application (i.e. by creating shortcuts, duplicating congested links). The trade-off to be explored has to take into account the following aspects:
    • the number of additional/spare reconfigurable links of the NoC should be kept at a minimum
    • reconfiguration takes time
    • latencies should be minimised so that all latencies are less than the message deadlines (plus a safety margin), but not more than that


    A successful project should produce a scheduling algorithm and an evaluation infrastructure (i.e. simulation models or static analysis) that can comparatively evaluate different schedules.

    Requirements: strong background in computer architectures, embedded systems

    Desired: networks-on-chip (EDI), response time analysis (RTS)

    Suitable for: CS, CS Emb, MEng

    More information:
  • A. Kolodny, "What is Network-on-Chip?," ACM/SIGDA Newsletter, Vol. 36, No. 8, 2006.
  • R. Marculescu et al, "Outstanding Research Problems in NoC Design," IEEE Trans CAD of Integrated Circuits, v. 28, n. 1, 2009.
  • L. Moller, P. Fischer, F. Moraes, L. S. Indrusiak, M. Glesner, Improving QoS of Multi-layer Networks-on-Chip with Partial and Dynamic Reconfiguration of Routers. In: Proc FPL 2010, p. 229-233.

    12.lsi.3 - Heuristics for dynamic mapping of tasks in multicore systems

    The goal of this work is to implement and compare dynamic mapping heuristics, so that application tasks can be assigned and/or migrated to different processors during runtime in a multicore system. Important points to be observed when implementing the mapping heuristics include:
    • when to re-map a particular task? (it could be receiving data or having data being sent to it over the network)
    • which sort of information about the multicore system does the mapping heuristic requires, and how much resources one needs to store and transmit such information?
    • how much processing overhead is due to the mapping heuristic itself?


    Requirements: good background in algorithms, concurrent programming

    Desired: scheduling algorithms (RTS / CRT)

    Suitable for: CS, CSEmb, MEng

    More information:
  • R. Marculescu et al, "Outstanding Research Problems in NoC Design," IEEE Trans CAD of Integrated Circuits, v. 28, n. 1, 2009.
  • E. Carvalho and F. Moraes, “Congestion-aware task mapping in heterogeneous MPSoCs,” System-on-Chip, 2008. SOC 2008. International Symposium on, 2008.
  • C. Chou and R. Marculescu, “Contention-aware Application Mapping for Network-on-Chip Communication Architectures,” Proc. Intl. Conf. on Computer Design (ICCD), 2008.

    12.lsi.4 - Abstract models for estimating energy consumption in multicores

    The goal of this work is to model energy consumption into a simulation framework for multicores. It should focus mainly on the energy dissipated by the on-chip interconnect structure (e.g. on-chip bus, network-on-chip), and should include both dynamic and static power consumption. The outcome of the project should be a graphical interface that will show the power dissipation in different parts of the chip as the simulation executes.

    Different modelling approaches can be used, and the best solution is probably a mixture of the following:
    • buffer occupation analysis (buffers storing data for long periods of time consume static power, buffers with high activity consume more dynamic power)
    • transition activity analysis in wires (wires transmitting data with more transitions consume more dynamic power)
    Project outcomes should be validated by estimating the power dissipated by different configurations of a multicore system (e.g. tasks densely packed and increased blocking vs. tasks sparsely packed, less blocking but higher hop count).

    Requirements: embedded systems design (EDI)

    Suitable for: CSEmb, MEng

    More information:
  • R. Marculescu et al, "Outstanding Research Problems in NoC Design," IEEE Trans CAD of Integrated Circuits, v. 28, n. 1, 2009.
  • L. Soares Indrusiak and O. M. dos Santos, "Fast and Accurate Transaction-Level Model of a Wormhole Network-on-Chip with Priority Preemptive Virtual Channel Arbitration," in Design Automation and Test in Europe (DATE), 2011.
  • L. Moller, L. Soares Indrusiak, M. Glesner, "NoCScope: A graphical interface to improve Networks-on-Chip monitoring and design space exploration," 4th Int Design and Test Workshop (IDT), 2009.

    12.lsi.5 - Benchmarks for multi- and manycore systems

    This project involves the identification, customisation and use of benchmarks for multi- and manycore systems. Benchmarks have always been used to compare how well different architectures perform under specific conditions. However, as systems get more complex a new class of benchmarks is needed, which are able to evaluate systems at a higher level of abstraction (i.e. higher than processor instruction level). In this project, the student will have to review existing uniprocessor and multiprocessor benchmarks such as SPEC and PARSEC and do literature survey to check how such benchmarks have been used to validate large multi- and manycores. The final part of the project is the investigation of a suitable approach to use such benchmarks to evaluate end-to-end latencies (computation and communication) using transaction-level simulation models of large multicores.

    A successful project should produce a good literature survey on benchmarks for multicores and adapt at least one of them so that it can be used to drive a transaction-level simulator of a large multicore.

    Requirements: strong background in computer architectures, embedded systems

    Desired: multiprocessors and networks-on-chip (EDI)

    Suitable for: CS, CS Emb, MEng

    More information:
  • C. Bienia, Benchmarking Modern Multiprocessors. Ph.D. Thesis. Princeton University, January 2011.
  • SPEC - Standard Performance Evaluation Corporation
  • C. Grecu et al, "An Initiative towards Open Network-on-Chip Benchmarks", OCPIP Whitepaper, 2007.
  • R. Marculescu et al, "Outstanding Research Problems in NoC Design," IEEE Trans CAD of Integrated Circuits, v. 28, n. 1, 2009.

    12.lsi.6 - Simulation of video processing algorithms using Ptolemy II

    This project will take a simple video processing algorithm and integrate it into Ptolemy II simulator, so that the performance of the algorithm can be evaluated under different levels of parallelism (i.e. single-core, dual-core with shared memory, multi-core with distributed memory). The simulation should actually include both functional and non-functional parts of the system (i.e. the actual processing of the video, as well as the timing overheads of each part of the algorithm).

    The initial choice of the algorithm is a Sobel filter for edge detection, but a different choice can be proposed by the student. Implementations of this algorithm is available within the Silhouette Project, and this could be used as a starting point.

    A successful project will allow the simulation of the processing of a video stream (from a file or camera) and the monitoring of timing metrics for different parallel architectures.

    Requirements: excellent Java programming skills

    Desirable: embedded systems design (EDI), image processing (VIGR)

    Suitable for: CS, CSEmb, MEng

    More information:
  • C. Brooks, E.A. Lee, X. Liu, S. Neuendorffer, Y. Zhao, H. Zheng (eds.), "Heterogeneous Concurrent Modeling and Design in Java (Volume 1: Introduction to Ptolemy II)"
  • M.. S. Kolich, Silhouette Project

    12.lsi.7 - Evaluation of the impact of cycling in urban areas

    This open-ended project aims to evaluate the impact of encouraging cycling in urban areas as a way to reduce society's carbon footprint. It should use simulation models to compare different scenarios where different proportions of the population uses bicycles or individual cars. The comparison metrics should include carbon emissions and time to reach the destination.

    The evaluation should consider an area of York and have an accurate description of the road network for that chosen area (e.g. obtained from OpenStreetMap.org). Interesting issues to be considered include:
    • in areas where cycle paths are unavailable, the evaluation should take into account the slowing down of cars as they have to wait for bicycles (and the additional carbon emissions due to the stop-and-go behaviour)
    • the system should support different behaviour for cyclists (faster, slower cyclists)
    • system should support different levels of traffic for each road segment (possibly obtained from online sources such as Google Maps or City of York website)


    A successful project will enable the analysis and simulation of different scenarios with different balance of cyclists/drivers, and provide metrics for carbon emissions and time to destination. Part of the project should also be a discussion of the relevance of the obtained results, and the ethical issues about using this kind of evaluation to guide and influence public policies.

    Requirements: good programming skills, creativity

    Suitable for: CS, MEng, MScSWE, MScComp, MScIT

    Related work:
  • A. Faghri, E. Egyhaziova, "Development of a Computer Simulation Model of Mixed Motor Vehicle and Bicycle Traffic on an Urban Road Network", Journal Transportation Research Record, v. 1674, 1999.
  • P.A.M. Ehlert, L.J.M. Rothkrantz, "Microscopic traffic simulation with reactive driving agents," Intelligent Transportation Systems, pp.860-865, 2001.



    12.lsi.8 - Evaluating the correlation of real-world and online social networks

    This open-ended project aims to evaluate social networks in the real world, and correlate them with their online counterparts. The evaluation system will be composed by three modules:
    • a mobile phone app that periodically broadcasts the unique identifier of its user (e.g. via Bluetooth or WiFi), so that it can be received by other phones in the same area, effectively detecting when users share a space and for how long
    • a backend server which receives all identifiers received by all users (e.g. on a daily basis) and stores it on a database
    • a desktop application which can correlate the unique identifiers of each user with their usernames in popular social networks (e.g. Facebook or Google+), so that it can evaluate to which extent the interactions captured in the real-world correlate with the interactions people have in the online world (e.g. what percentage of your online social network do you actually meet in the real world? what percentage of the people you meet on a daily basis is also part of your online social life?)


    A number of extensions can be considered, such as considering the time and place of interactions in the real world (e.g. to investigate differences between work-related and leisure-related social network).

    A successful project will have a prototype implementation of the three modules above and will perform a number of small scale experiments with 10-20 users.

    A similar project using MoteRunner is also available:
    12.lsi.9.

    Requirements: good programming skills, creativity

    Desired: experience with app programming (Android preferred)

    Suitable for: CS, MEng, MSc HCIT, MScSWE, MScComp, MScIT

    Related work:
  • Emiliano Miluzzo, Nicholas D. Lane, Kristóf Fodor, Ronald Peterson, Hong Lu, Mirco Musolesi, Shane B. Eisenman, Xiao Zheng, and Andrew T. Campbell. 2008. Sensing meets mobile social networks: the design, implementation and evaluation of the CenceMe application. In Proceedings of the 6th ACM conference on Embedded network sensor systems (SenSys '08). ACM, New York, NY, USA, 337-350.
  • Campbell, A.T.; Eisenman, S.B.; Lane, N.D.; Miluzzo, E.; Peterson, R.A.; Hong Lu; Xiao Zheng; Musolesi, M.; Fodor, K.; Gahng-Seop Ahn; , "The Rise of People-Centric Sensing," Internet Computing, IEEE , vol.12, no.4, pp.12-21, July-Aug. 2008

    Background information for Ambient Intelligence projects based on IRIS motes and MoteRunner: 12.lsi.9, 12.lsi.10 and 12.lsi.11

    The following three projects will be based on Mote Runner, which is both a programming environment and a runtime platform for wireless sensor network motes. It supports Java and C#, and is fully integrated to Eclipse, so applications can be developed, debugged and simulated within a high-level programming and simulation environment before they are uploaded to the actual motes.

    All projects are expected to develop prototypes based on the IRIS motes available at the department. A total of 30 motes and 10 interface boards will be made available.

    More information:
  • J. L. Hill, "System Architecture for Wireless Sensor Networks," PhD Thesis, UC Berkeley, 2003.
  • Mote Runner website and Youtube video
  • A. Caracas, T. Kramp, M. Baentsch, M. Oestreicher, T. Eirich, I. Romanov, "Mote Runner: A Multi-language Virtual Machine for Small Embedded Devices," in 3rd Int Conference on Sensor Technologies and Applications (SENSORCOMM), 2009.

    12.lsi.9 - Monitoring social networks with MoteRunner motes

    Check background information above, as well as a similar project: 12.lsi.8.

    This open-ended project aims to evaluate social networks in the real world, and will use WSN motes to do so. The evaluation system will be composed by three modules:
    • a MoteRunner application which will be loaded to multiple mobile motes. It will periodically broadcast the unique identifier of its user, will listen to the broadcasts of other motes (and store the received identifiers), and will upload the stored identifiers to sink nodes when they pass within their proximity
    • a MoteRunner application which will be loaded to multiple stationary sink nodes. It will periodically send out beacons, which will be detected by the mobile motes and used as a protocol initiator, allowing them to send packets containing the identifiers that have encountered previously.
    • a backend server, which will store all information received by all sink nodes and enable queries about the number and frequency of interactions between users.


    The goal of the system is to evaluate how often people are co-located, and to try to infer from that information whether they interact (e.g. by analysing how close they are, how long they are co-located, what are the characteristics of the place where they meet, etc.) A successful project will have a prototype implementation of the three modules above and will perform a number of small scale experiments with 10-20 users.

    Requirements: MoteRunner (EDI)

    Suitable for: CS, CSEmb, MEng

    Related work:
  • Emiliano Miluzzo, Nicholas D. Lane, Kristóf Fodor, Ronald Peterson, Hong Lu, Mirco Musolesi, Shane B. Eisenman, Xiao Zheng, and Andrew T. Campbell. 2008. Sensing meets mobile social networks: the design, implementation and evaluation of the CenceMe application. In Proceedings of the 6th ACM conference on Embedded network sensor systems (SenSys '08). ACM, New York, NY, USA, 337-350.
  • Campbell, A.T.; Eisenman, S.B.; Lane, N.D.; Miluzzo, E.; Peterson, R.A.; Hong Lu; Xiao Zheng; Musolesi, M.; Fodor, K.; Gahng-Seop Ahn; , "The Rise of People-Centric Sensing," Internet Computing, IEEE , vol.12, no.4, pp.12-21, July-Aug. 2008

    12.lsi.10 - Acoustic localisation using MoteRunner

    Check background information above.

    This project will investigate the possibility of localising a source of sound by comparing sensor readings in three different sensor nodes. It should use sound intensity and time difference of arrival to estimate the approximate position of the source of sound. Once detected, the position should be sent to a sink node connected to a PC, which then displays the estimated position of the source using a graphical user interface. The main tasks will be:
    • program the motes to accurately synchronise their timers so that each of them can record the time when a sound is sensed, and through the difference between the time stamps it can estimate the distance of the source to each of the nodes, and thus estimate its position
    • program the motes to estimate the position of the sound source by comparing the different sound intensities sensed by each node
    • comparatively evaluate both solutions above, as well as hybrid solutions that use both methods to increase estimation accuracy
    • program a base station mote which is connected over USB to a host, so that it can receive the estimation of the sensing motes and inform the sound source's position to a backend process running on the host;
    • program a desktop or web-based application (e.g. with PHP) which reads the position of the sound source and displays it graphically over a map of the environment;


    Requirements: MoteRunner (EDI)

    Suitable for: CS, CSEmb, MEng

    Related work:
  • Jingbin Zhang, Ting Yan, John A. Stankovi, and Sang H. Son. 2007. Thunder: towards practical, zero cost acoustic localization for outdoor wireless sensor networks. SIGMOBILE Mob. Comput. Commun. Rev. 11, 1 (January 2007), 15-28.
  • Julian, P.; Andreou, A.G.; Riddle, L.; Shamma, S.; Goldberg, D.H.; Cauwenberghs, G.; , "A comparative study of sound localization algorithms for energy aware sensor network nodes," Circuits and Systems I: Regular Papers, IEEE Transactions on , vol.51, no.4, pp. 640- 648, April 2004

    12.lsi.11 - Altruistic and egoistic behaviour in wireless sensor networks

    Check background information above.

    This project will investigate protocols that will enable altruistic and egoistic behaviours in MoteRunner motes. The idea is to allow motes to take up more workload (i.e. sensor readings, data processing and aggregation) when their energy levels are higher, but refuse and forward workload when they feel that their energy levels are too low or decreasing too rapidly. A successful project will show different ways of implementing such behaviours and evaluate the impact of having such behaviours in a deployment of 20-30 motes in terms of network lifetime and work turnaround. The actual transfer of assemblies from mote to mote and their dynamic reprogramming does not have to be part of this project, and the focus should be on the actual control of responsibilities (which should be done in a distributed way). The evaluation could be done by using dummy tasks that will (or will not) reduce the energy levels of nodes when they execute them.

    Requirements: very good programming and debugging skills (Java preferred), ability to understand and use a simulation environment, very good background in networks (NDS / NWC).

    Desired: embedded systems design (EDI)

    Suitable for: MEng, MSc NC

    Related work:
  • Y. E. M. Hamouda and C. Phillips, “Biological Task Mapping and Scheduling in Wireless Sensor Networks,” in Communications Technology and Applications, 2009. ICCTA ’09. IEEE International Conference on, 2009, pp. 914-919.
  • Yuan Tian; Ekici, E.; Ozguner, F.; , "Energy-constrained task mapping and scheduling in wireless sensor networks," Mobile Adhoc and Sensor Systems Conference, 2005. IEEE International Conference on , vol., no., pp.8 pp.-218, 7-7 Nov. 2005

    12.lsi.X - Student-defined project

    I will consider intelligent student-defined projects in the areas of concurrent and distributed embedded systems. I am interested in hardware, software or system-level approaches to the design and optimization of such systems. Send me an email with a few keywords and ideas and I'll send you some feedback.