Allocation distribuée des requêtes dans le réseau de capteur sans fil
Institution:
Paris,Télécom ParisTechDisciplines:
Directors:
Abstract EN:
Wireless sensor network architecture can be greatly simplified by enabling the mobile users to access directly the sensor nodes. Under this case, both efficiency and fairness should be considered in order to keep the network in an optimal operational state and the fairness is especially important as long as the users are actually the clients that pay for the services provided by the network. We studied this fairness problem from a user's point view. We have identified and studied the following problems: 1. The problem to allocate the continuous query with max-min fairness in a WSN. We obtained explicit expression for the case where only two uses are in the network and we proposed a distributed heuristic algorithm to solve a more user case. 2. The problem to allocate the discrete queries with fairness. Under this case, we used lexicographic max-min fairness and we proposed new formulation and solution for the problem. 3. The feasibility to reformulate the fairness problem and implement the solution in a 802. 15. 4/ZigBee based WSN. 4. The MMKP used in the formulation of the fairness problem. We have studied this problem by simulation experiments. We proposed a systematic method to generate the MMKP instances and we tested several groups of instances with the BBLP algorithm and two optimization utilities, namely the GLPK and CPLEX.
Abstract FR:
L'accès direct des utilisateurs mobiles dans les nœuds de capteurs simplifie l'architecture du réseau. L'équité et l'efficacité doivent être simultanément pris en compte pour optimiser le fonctionnement de ces réseaux et l'équité des utilisateurs est particulièrement importante lorsque les utilisateurs sont des clients du service fourni par le réseau. Nous étudions des questions d'équité dans le réseau de capteurs sans fil du point de vue d'un utilisateur. Nous avons identifié et étudié les problèmes suvants. 1. Le problème d'allocation de requête à l'équité Max-Min dans un WSN. L'expression explicite de requête à l'équité max-min, pour le cas où seulement deux utilisateurs existent dans le réseau, est dérivée. Et le problème au cas où plusieurs utilisateurs sont dans le réseau est résolu avec un algorithme heuristique distribué. 2. L'allocation équitable des requêtes entre les utilisateurs avec un modèle discret. Dans ce cas, l'équité max-min lexicographique doit être exploitée. Nous proposons une formulation pour le problème. 3. La faisabilité de reformuler le problème et de mettre en œuvre nos solutions dans un WSN basé sur IEEE 802. 15. 4/ZigBee. 4. Le MMKP utilisé pour formuler le problème. Nous avons étudié ce problème par expériences. Une méthode systématique pour générer les instances MMKP est proposée et plusieurs groupes d'instances qui représentent une variété de types de correlation entre les paramètres du problème sont générés. Ces instances sont testées avec l'algorithme BBLP ainsi que deux outils d'optimisation, le GLPK et le CPLEX.