INF421 PI 2022-2023: Routing in the Internet of Things

Subject: [pdf]

Internet of Things (IoT) is characterised by the deployment of a large amount of connected objects. These objects are autonomous devices that use sensors to monitor their environment and communicate through a wireless radio channel. When these sensors are not powerful, they cannot communicate over a long distance, so that additional intermediate relay nodes may be required to connect them together. Sensors can themselves route the messages from other sensors or relays. In this project, we derive the optimal routes between sensors by using the notion of Steiner tree in graph theory.

Numerical Application (zip archive with all test files in .txt, files provides variables k, n and the adjacency matrix of graph G): scenarios

INF421 PI 2021-2022: User Scheduling in 5G

Subject: [pdf]

In 5G, an antenna transmits data packets to smartphones (or users) through a wireless medium, which is divided into a set of frequency channels. Figure 1 is an example of simultaneous transmission towards three users using three channels.

Figure 1: Wireless packet scheduler transmitting data simultaneously to three users over three (frequency) channels.

The higher the power dedicated to a user, the higher the data rate it can experience. The exact dependence between power and data rate is however user and channel specific. With the same transmit power, a user close to the antenna will enjoy for example a higher data rate than a user far away. A wireless packet scheduler is thus responsible to allocated channels to users and to divide the total power budget of the antenna among the available channels. The goal of this project is to design optimal packet schedulers in this context.

Numerical Application (zip archive with all test files in .txt, files provides variables N, M, K, p, p_k,m,n for every n and r_k,m,n for every n): testfiles

INF421 PI 2020-2021: Matching Mechanisms for Kidney Exchange

Subject: [projectINF421-2020]

Transplantation is the preferred treatment for most serious kidney diseases. Tra- ditionally, kidneys are obtained from cadavers. The demand is however increasing more rapidly than the offer and more and more patients are waiting for a cadaver’s kidney. In France in 2017, about 500 patients in the waiting list died because they have not been transplanted on time1.

An alternative is to obtain kidneys from live donors. It is attractive because the probability of successful transplantation is higher. If a patient knows someone that is ready to donate him his kidney (a spouse, a parent, a friend) and if the transplant is feasible (donor and patient are immunologically compatible), the transplant is realized. If the donor is not compatible with his patient, the pair may enter a kidney exchange program. In most countries, there is a consensus to forbid organ selling, so that non-monetary incentive mechanisms should be designed for an efficient allocation of kidneys to patients. This is the subject of this project.

INF421 PI 2018-2019: Robust Barrier Coverage in the Internet of Things

Subject: [projectINF421]

The concept of “Internet of Things” refers to the massive deployment of sensors in our daily life as well as in various economic sectors such as autonomous vehicles, robotics, agriculture, etc. These sensors, unless powered by a renewable energy, are equipped with batteries with several years of lifetime. They can be transmit to or be controlled by a central unit through a wireless communication protocol.

In this project, we study an application of the Internet of Things, which consists in deploying sensors to detect the intrusion of an animal or a human through a strip (or rectangular) area. This type of deployment has applications in wildlife monitoring or security. Every sensor has a sensing range, within which the presence of moving object is detected. As the detection may fail, we may require a robust deployment by adding some redundancy. We say that a set of sensors provides a robust K-barrier coverage if any intrusion can be detected by at least K sensors (see Figure 1).

Figure 1: Sensor deployment over a strip area providing a K = 2 barrier coverage.

As the sensor lifetime of the sensors is not infinite, we would like also to activate or desactivate sensors in order to save energy. Our objective is thus to find for a given sensor deployment, a given set of remaining lifetimes and a given K, a schedule of the sensors so that the network provides a K-barrier coverage at every instant and so that the network lifetime is maximized.

Numerical Application (change extension .doc in .txt): sensornetwork0, sensornetwork1