Jean-Claude BERMOND, Mascotte, join project I3S (CNRS and University of Nice Sophia-Antipolis) and INRIA

Title: Gathering algorithms in radio networks

We study the problem of gathering information from the nodes of a multi-hop radio network into a predefined destination node under reachability and interference constraints. This problem has been asked by France Telecom in the context of how to bring Internet in villages; it appears also in collecting data in sensor networks. In such a network, a node is able to send messages to other nodes within reception distance, but doing so it might create interference with other communications. Thus, a message can only be properly received if the receiver is reachable from the sender and there is no interference from another message being simultaneously transmitted. The network is modeled as a graph, where the vertices represent the nodes of the network and the edges, the possible communications. The interference constraint is modeled by a fixed integer d, which implies that nodes within distance d in the graph from one sender cannot receive messages from another node. We mainly consider the case where each node has one (or more) unit-length message to transmit and, furthermore, we suppose that it takes one unit of time (slot) to transmit a unit-length message and during such a slot we can have only calls which do not interfere (called compatible calls). A set of compatible calls is referred to as a round. We give protocols and lower bounds on the minimum number of rounds for the gathering problem for various networks and under various hypothesis (like the possibility or not to store messages in transit nodes). In a few cases (specific topologies and small d) we have exact polynomial algorithms; but in general we have approximation algorithms. We also consider the dynamic version of the problem where we want to give to each node some bandwidth.

Title: Robust Multi-Sensor Scheduling for Multi-Site Surveillance

Joint work with N. Boyko, T. Turko, D.E. Jeffcoat, S. Uryasev, P.M. Pardalos

We present mathematical programming techniques for solving a class of multi-sensor scheduling problems. Robust optimization problems are formulated for both deterministic and stochastic cases using linear 0-1 programming techniques. In addition, equivalent formulations are developed in terms of cardinality constraints. The formulations are further extended to incorporate network-based settings. The solution methods and computational results for the formualted problems are presented.

Title: 2-club clustering as a model of virtual backbone in ad hoc networks

The concept of a virtual backbone is widely used in designing routing protocols for wireless ad hoc networks. In particular, virtual backbones based on approximations of minimum connected dominating sets have become popular recently. In this talk, we will investigate virtual backbones based on 2-club clustering as an attractive alternative to connected dominating sets.

Title: Sensor Scheduling and Redeployment Algorithms in Wireless Sensor Networks

In this talk, I will address sensor scheduling and redeployment algorithms in wireless sensor networks for both atomic event and composite event detection. Sensors may be equipped with different numbers and types of sensing components. They can detect an atomic event independently or they can cooperate to detect a composite event. In this talk, I will discuss sensor scheduling mechanisms that select a set of active sensors to perform sensing and data relaying, while all other sensors go to sleep to save energy. Sensors in the active set change over time in order to prolong network lifetime. In addition, sensor redeployment mechanisms are presented which exploit sensor mobility to relocate sensors such that to achieve load balance, a reliable surveillance, or to prolong network lifetime.

Title: Facility Location in Weighted Regions and its Applications

A weighted subdivision is a decomposition of the plane into regions, each of which has associated a positive integer weight. The distance between two points within the same region is measured as the Euclidean distance times the weight of the region. The straight line distance between two points in different regions is the sum of the distances over the regions intersected by the line segment joining the points.

Given a weighted subdivision with n vertices and m point-like sites, we will discuss how to find a line segment s such that the length of s and the sum of the (orthogonal) distances from the sites to s is minimized.

Title: A Noval Multimedia Database System for Data Broadcasting

Topology control is a useful strategy to reduce network energy consuming, extend network lifetime and avoid interference. There are mainly two types of topology control strategies, one is selecting a virtual backbone for the given network, while another is to control transmission range and assign schedules for each link. This talk briefly introduces these two types of strategies, including different communication models and the corresponding approximation designs to solve the problems. It also covers analysis for approximation ratios.

Title: Complexity and Approximation Algorithms for Assessing the Network Vulnerability

In this talk, we will discuss about the reliability routing problem in probabilistic graphs which can model the mobile and dynamic networks such as MANET, DTN, ICMAN^Å Given a probabilistic graph $G=(V,E)$ with a delivery probability function $p: E \rightarrow [0, 1]$, a source node $s$ and a sink $t$, find a subgraph $H$ maximizing the delivery probability Conn-Prob_H(s,t) such that $|E(H)| \le k$. We will present the approximation algorithm following the #P-hardness of this problem.

Title: Barrier Coverage of Line-Based Deployed Wireless Sensor Networks

Barrier coverage of wireless sensor networks has been studied intensively in recent years under the assumption that sensors are deployed uniformly at random in a large area (Poisson point process model). However, when sensors are deployed along a line (e.g., sensors are dropped from an aircraft along a given path), they would be distributed along the line with random offsets due to wind and other environmental factors. It is important to study the barrier coverage of such line-based deployment strategy as it represents a more realistic sensor placement model than the Poisson point process model. This talk presents the first set of results in this direction. In particular, we establish a tight lower-bound for the existence of barrier coverage under line-based deployments. Our results show that the barrier coverage of the line-based deployments significantly outperforms that of the Poisson model when the random offsets are relatively small compared to the sensor's sensing range. We then study sensor deployments along multiple lines and show how barrier coverage is affected by the distance between adjacent lines and the random offsets of sensors. These results demonstrate that sensor deployment strategies have direct impact on the barrier coverage of wireless sensor networks. Different deployment strategies may yield significantly different barrier coverage. Therefore, in the planning and deployment of wireless sensor networks, the coverage goal and possible sensor deployment strategies must be carefully and jointly considered.