Bing HAN, Telecom ParisTech, Telecom Bretagne

Location :

Amphi Grenat, Telecom ParisTech,  46, rue Barrault - 75013 Paris.

Abstract :

Distributed Query Allocation in Wireless Sensor Networks

Abstract
A Wireless Sensor Network (WSN) is a wireless network consisting of spatially distributed sensor 
nodes to gather information from the physical world. The promising idea of WSN is to build an 
information gathering, processing and representing system that connects human with the physical 
world. Lots of  efforts have been made in recent years on both the theoretical and applicative 
aspects of WSNs and we can expect that large scale WSN deployment will be possible in the near 
future. This thesis focuses on the large scale WSN which may serve potentially many users in an open 
architecture where each user has direct contact with the sensors. We will refer to this architecture 
as the mobile user WSN. Large scale mobile user WSN provides a promising solution to many 
applications. Multiple users in the network could act as data collectors working  together for a 
common task or they could also be end users which have no direct contact between each other. 
In either case, fairness among these users is an important issue in practice.


We  first investigate the fairness issues with a 
simple query model. In this model, multiple users query the sensors located within a circled area. 
The query circle is assumed to have a continuous variable diameter and centered at the querying 
user. Distributed optimization problem with congestion constraints is formulated and heuristic 
algorithm is developed to approximate the optimal solution. Next, a similar problem with a discrete 
query model is further investigated. In the discrete query model, the query range is measured by hop 
numbers. This variation makes the problem to be combinatorial and NP-hard. Multidimensional 
multiple choice knapsack problem is used to model the problem with both lexicographical max-min 
fairness and maximal query cover objectives. Distributed solutions are proposed and their 
performance are demonstrated by simulations. Since the ZigBee specification and IEEE 802.15.4 
standard are two de facto standards of the wireless sensor networks, we study our problems for a 
wireless sensor network based on such technologies. Special properties of the ZigBee 
cluster tree structure are exploited to keep the algorithm fully local thus only limited 
communications are involved in the proposed distributed algorithms. Efficiency of the algorithms 
are demonstrated by extensive simulations.


While all the subjects discussed so far are related with the fair capacity sharing problem found in 
wireless sensor networks with multiple users, the combinatorial problem behind the discrete version, 
namely the multidimensional multiple choice knapsack problem, is very interesting and 
deserves special research efforts. The inconsistency of the solution times of instances 
with similar parameters and the sharp contrast between hard small problems and easy large 
problems motivated our further investigation on the problem itself. By first proposing methods to 
generate problem instances with different properties, we try to solve several groups of 
instances with the current algorithm/solvers. Special properties that make the instances hard 
have been identified.

Host :