Direction des Relations Internationales (DRI)
Programme INRIA "Equipes Associées"
(Demande de prolongation)
EQUIPE ASSOCIEE |
|
sélection |
Demande de prolongation pour 2009 |
Equipe-Projet INRIA : MAESTRO, MESCAL, TREC |
Organisme étranger partenaire : IISc |
Centre de recherche INRIA : Sophia-Antipolis
(Grenoble, ENS Paris) |
Pays : INDE |
La proposition en
bref
Titre de la thématique de collaboration (en français et en anglais) : |
Descriptif (environ 10 lignes) : |
|
Coordinateur français |
Coordinateur étranger |
|
Nom, prénom |
ALTMAN Eitan |
KUMAR Anurag |
|
Grade/statut |
DR2 |
Professor |
|
Organisme d'appartenance |
INRIA Sophia Antipolis |
IISc |
|
Adresse postale |
2004 Route des Lucioles 06902 Sophia Antipolis Cedex |
Dept. of Electrical Communication , Indian
Institute of Science, |
|
URL |
|||
Téléphone |
04 92 38 77 86 |
+91 80 2360 0855 |
|
Télécopie |
04 92 38 77 65 |
+91 80 2341 5032 |
|
Courriel |
|||
|
|
|
|
|
Autre participant étranger |
Autre participant étranger |
Nom, prénom |
BORKAR Vivek |
SARKAR Saswati |
Grade/statut |
Professor |
Professor |
Organisme d'appartenance |
Tata Institute of Fundamental Research |
Dept of Electrical and Systems Univ of |
Adresse postale |
Homin Mumbai 400 005, |
19104, |
URL |
||
Téléphone |
+91 22 21 52971 ext 2293 |
+1 215 573 8071 |
Télécopie |
+91 22 21 52110 exr 2181 |
+1 215 573 2068 |
Courriel |
Changements majeurs survenus concernant l'Equipe Associée (modifications des objectifs scientifiques, des chercheurs impliqués) |
(joindre la page du programme de travail initialement prévu
fin 2007 pour l'année 2008
ou insérer un lien vers cette page)
Description scientifique de
ce programme de travail (détaillé pour l'année 2008 et en grandes lignes pour
le plus long terme)
Les thèmes sur lesquels nous travaillerons en commun sont tous liés aux nouvelles technologies dans les réseaux d’accès sans fil ainsi que dans les réseaux adhoc sans fil. Notre approche va s’appuyer sur la richesse en spécialisations des membres participants dans des domaines théoriques que nous utiliserons pour étudier les réseaux sans fil: Le contrôle stochastique, la théorie des jeux, la théorie d’information, le contrôle adaptatif, des techniques de traitement du signal et la théorie de l’optimisation..
Comme il y a parmi les participants indiens des personnes qui n’ont pas collaboré avant avec nous, une partie du travail de la première année sera consacrée à la définition de problèmes de recherche communs.
Nous allons travailler durant la
première année sur les problèmes de recherche suivants dans les réseaux sans
fil:
1. Le problème de l’association : il s’agit de proposer et analyser des protocoles pour qu’un mobile puisse décider à quel point d’accès se connecter quand il y a plusieurs points d’accès de la même technologie ou même quand il y en a plusieurs de technologies différentes. Les décisions peuvent être revues par les mobiles si les conditions de radio changent. Nous permettrons aussi les points d’accès d’avoir le pouvoir de prendre des décisions, et en particulier de refuser une nouvelle connexion (en fonction de la charge et des conditions radio). Le problème sera modélisé avec des outils de la théorie des jeux et du contrôle optimal. Nous étudierons non seulement le comportement d’équilibre dans les modèles des jeux mais aussi le comportement dynamique décrivant le comportement quand on n’est pas en équilibre. Dans la mesure ou les mobiles prennent les décisions d’association, nous identifierons des mécanismes d’administration et gestion du réseau qui favoriseront une convergence à des point d’équilibres qui sont efficaces. Les outils théoriques que nous utiliserons sont les jeux évolutionnaires, les « stochastic approximations » et les jeux stochastiques.
2.Choix de spectre de fréquences Nous allons étudier des problèmes d’optimisation dans les choix de porteuses dans des réseaux d’accès basés sur l’OFDMA. L’allocation des fréquences sera étudiée dans le cadre de la théorie des jeux dans le contexte ou ce sont les mobiles qui prennent ces décisions. En particulier, nous étudierons ce type de problèmes dans le contexte des « cognitive radios » ou les mobiles ont une capacité de trouver les meilleurs zone de fréquences (dans le sens ou l’interférence y est minimale). Nous utiliserons comme outils théoriques les jeux de potentiel et les jeux de congestion.
3. Contrôle de ressources en présence de nœuds malicieux L’équipe INRIA a travaillé depuis quelques années déjà sur des problèmes de gestion et administration du réseau en présence d’agents malicieux. Dans le passé notre recherche a porte sur le contrôle de puissance en présence de problèmes de brouillage radio des données par des agents malicieux. Cette année nous avons commence une étude avec Prof Sarkar sur l’identification et l’évaluation des problèmes de brouillage des canaux d’information. Nous souhaitons approfondir ce travail et y ajouter un volet d’expériences numériques qui serait effectuées par des stagiaires ou un thésard que nous encadrerons conjointement. L’outil théorique que nous utiliserons est celui des jeux Bayesiens à somme nul.
Une caractéristique d’un grand nombre des travaux communs que nous planifions est celui de l’utilisation des outils avancés de la théorie des jeux non-coopératifs
Travail théorique sur la
théorie des jeux
Nous avons identifié des sujets
de recherche théorique dans la théorie des jeux que nous aborderons déjà dans
la première année et dont nous aurons besoin des résultats pour notre travail
sur les réseaux sans fil. Des exemples de tels sujets sont
Les jeux
stochastiques à somme nul à information parfaite avec contraintes, dont
nous aurons besoin pour généraliser le sujet décrit au troisième point de la
page précédente au cas ou les condition radio ont une
corrélation temporelle
Les jeux stochastiques évolutionnaires: il s’agit d’un nouveau type de modèles ou les individus restent dans le système pendant un certain temps dont la durée dépend de leurs actions; ces actions déterminent non seulement l’utilité mais aussi la probabilité des transitions entre les états d’un individu. Un exemple est le contrôle de puissance ou les puissances disponibles aux mobiles dépendent du niveau de remplissage de leur batterie.
En parallèle nous allons apprendre la théorie des jeux coopératifs que nous estimons être le contexte adéquate pour un grand nombre de problèmes dans les réseaux ad-hoc et dans les réseaux paire à paire. Nous allons commencer à appliquer ces outils à partir de la deuxième année.
Plan pour la suite de la
coopération: Réseaux ad hoc
Pour la suite de notre travail, nous allons proposer des modèles multi-saut basées sur le CSMA. Récemment Garetto et al (IEEE/ACM Trans. Networking, 2006) ont utilisé un modèle CSMA qui avait été développé quelques années au par avant, parvenant à modéliser avec précision des phénomènes de manque de coordination et de « famine » (starvation) dans des réseaux multi-saut CSMA/CA. Nous proposons d’utiliser notre riche expérience commune (de notre collaboration passée) afin de développer des règles d’ingénierie pour l’utilisation de tels protocoles dans les réseaux d’entreprises. Nous allons étendre notre approche d’étudier l’équité dans le réseau local sans fil IEEE 802.11 au réseau multi-saut
Le routage dans les réseaux ad hoc denses: Dans les réseaux ad-hoc, les mobiles servent non seulement de sources et destination de trafic mais aussi de relai pour acheminer du trafic provenant d’autres sources vers d’autres destinations, Les protocoles de routages cherchent souvent des chemins les plus courts ou à moindre cout entre les sources et leur destination. La recherche s’effectue sur un graphe de connexion ou les nœuds représentent les mobiles et les arrêts représentent les liens radio entre les mobiles. Nous étudierons les problèmes de routage quand le réseau devient de plus en plus dense, tellement dense qu’on peut l’approximer par un continuum de chemins possibles sur le plan; On va donc chercher à caractériser une version continue de l’équilibre de Wardrop (un concept qui vient de la théorie du trafique routier).
En proposant des protocoles (de
routage ou de contrôle de flux) dans les réseaux sans fil, nous allons faire appel
à des approches « inter-couches » (cross-layer) qui visent à
prendre en compte les caractéristiques particuliers du canal radio et
d’intégrer des solutions aux problèmes du canal radio dans ces protocoles
(contrairement aux approches qui visent à traiter séparément les problèmes du
canal radio).
Description de l'activité scientifique de l'équipe associée et des résultats obtenus : publications, communications, organisation de colloques, formation, soutenances de thèse, valorisation économique, sociale, industrielle, enregistrement de logiciels, dépôt de brevets ... (1 à 2 pages)
Les membres de l’Equipe Associée ont eu des résultats prometteurs dans tous les domaines qui avaient été prévus. Cependant je préfère me focaliser sur les travaux de recherche qui ont été entrepris conjointement et qui ont abouti à des publications parues 2008 ou à des articles soumis en 2008. Le thème 2 du plan de travail est le seul qui n’a pas encore abouti à une soumission ou à une publication mais nous prévoyons d’avoir un rapport d’ici la fin de l’année.
Applications de la théorie des jeux dans
les réseaux sans fil
Contrôle de ressources en présence de nœuds malicieux Nous avons étudié dans [SAEH08] le problème de protection des réseaux sans fil contre des attaques en forme de brouillage. Contrairement aux problèmes où un adversaire brouille la transmission des données, nous nous sommes intéresses aux cas où l’adversaire brouille des signaux de transmission. Nous avons formulé et modélisé ce type de problèmes comme un jeu de signalisation (sous ensemble des jeux Bayesiens). Nous avons proposé des solutions à base de programmation linéaire pour identifier la pire des attaques possible et pour s’y protéger au mieux.
Le problème d’Association et du placement des stations de base Dans [AKSS09] nous utilisons un modèle fluide pour modéliser la planification des réseaux cellulaires dans plusieurs nivaux. Pour un placement donné de stations de base, nous étudions le problème d’association des mobiles : à quelle station de base se connecter. Nous cherchons un équilibre où chaque mobilbe est connecté à la station qui lui offre le meilleur rapport signal bruit. Dans le bruit nous prenons en compte l’interférence d’autres mobiles. Nous obtenons des résultats surprenants sur la structure des cellules. On y trouve des cellules découpées ce qui est le résultat du faite qu’un mobile peut trouveur un meilleur rapport signal bruit en se connectant à une station de base qui n’est pas la plus proche de lui. Puis nous étudions la question du placement optimal des stations de base dans deux cadres différents : le contexte coopératif où les stations de base appartiennent au même fournisseur de service, et le contexte compétitif où chaque station appartient à un autre fournisseur de service. Les outils utilisés théorique que nous développons dans ce travail sont liés aux jeux de positionnement (« location games ») qui font appelle à la géométrie et qui traitent des questions de placement géographique d’entreprises qui sont en compétition.
Le routage non-coopératif dans les réseaux sans fil Dans [AAE08] nous considérons plusieurs agents qui contrôlent chacun le routage de son propre trafic. Nous introduisons une famille d’utilités qui caractérisent des degrés de coopération variant entre la non-coopération et l’altruisme. Une coopération de degré A où A est un réel entre 0 et 1, est celle obtenue quand l’utilité de l’agent est la somme des performances propres de l’agent pondérées par le facteur A et celles des autres agents, pondérées par 1-A. Nous étudions l’impacte du degré de coopération sur les performances des agents. En particulier nous identifions les performances obtenues quand les degrés de coopération varient d’un agent a l’autre.
Le paradoxe de Braess dans les réseaux sans fil Le paradoxe de Braess est décrit un phénomène où en ajoutant des ressources à un réseau (en ajoutant de liens ou en augmentant la capacité des liens) les performances en équilibre s’empirent pour tous les agents qui utilisent ce réseau. Ce paradoxe vient du trafic routier et plusieurs cas réel l’ont confirmé. Dans [AKH08] nous avons identifié un paradoxe de la même famille qui survient quand plusieurs terminaux mobiles sont en compétition sur des ressources radio de deux stations de base. Nous avons étudié les divers équilibres obtenus et leur stabilité. La non-unicité de l’équilibre est liée à une structure qui ressemble à celle des jeux de coordination.
Protocoles de contrôle d’énergie
dans le WiMax
Dans les deux travaux [AAA08a,AAA08b] nous étudions des modèles de files d’attente avec des vacances non-homogènes pour étudier le comportement du mode dormant de WiMax. Il s’agit d’un protocole qui désactive le terminal mobile et puis le réveille après un certain temps. Si en se réveillant, le terminal ne trouve pas de paquets qui sont arrives durant cette période de inactivité, le terminal se désactive une deuxième fois et ainsi de suite. Une norme existante spécifie comment choisir les temps de désactivation en fonction de nombre de désactivations successives. Nous évaluons les performances de ce protocole et trouvons des nouveaux paramètres qui donnent des meilleures performances. Comme les performances dépendent des statistiques du trafic d’entrée, nous formulons un problème de type maxmin où les paramètres sont optimisés de façon à obtenir le meilleur comportement dans le pire des conditions.
Publications :
[AAA08a] Sara Alouf,
Eitan Altman and Amar Azad, "Analysis of an
M/G/1 queue with repeated inhomogeneous vacations -- Application to IEEE
802.16e power saving", Fifth International Conference on the Quantitative
Evaluation of Systems (QEST), St Malo, France,
14th-17th September 2008.
[AAA08b] Sara Alouf,
Eitan Altman, Amar Prakash
Azad, "M/G/1 Queue with Repeated Inhomogeneous Vacations Applied to IEEE
802.16e Power Saving", International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS), June 2-6, 2008,
[SAEH08] Saswati Sarkar, Eitan Altman, Rachid El-Azouzi and Yezekael Hayel, "Information Concealing games", Infocom symposium, April 2008.
[AKH08] E. Altman, V. Kamble
and H. Kameda, "A Braess type paradox in interference channels", Physicomnet workshop,
[AAE08] [Azad, Amar Prakash; Altman, Eitan; El-Azouzi, R., “From Altruism to
Non-Cooperation in Routing Games”, eprint
arXiv:0808.4079, 08/2008.
[AKSS09] Eitan Altman, Anurag
Kumar, Chandramani K. Singh and Rajesh Sundaresan Spatial SINR Games Combining Base Station
Placement and
1.
Dépenses EA (effectuées sur les crédits de l'Equipe Associée) |
Montant dépensé |
Stage et bourse thèse 3 mois |
12,061 (Azad et Kamble) |
Invitations des partenaires |
5.126 (Borkar+Sundaresan) |
Missions INRIA |
2.765 (Altman) |
Mission INRIA stagiaires |
3.025 |
PC portable |
1.400 |
Total |
24.307 |
Justifiez en quelques lignes l'utilisation des crédits et en particulier
une utilisation partielle du budget alloué.
Nous avons financé en plus des voyages des
chercheurs impliqués, 3 mois de thèse pour Amar Azad
qui vient de IISc où il a effectué son Master sous la
direction de Prof Chokalingam (participant dans
l’EA), 2 mois et demi de stage d’un étudiant indien, des missions
pour les stagiaires et thésards impliqués dans le projet et un PC pour le thésard de l’IISc (Amar Azad).
2.
Dépenses externes (effectuées sur des financements hors EA) |
Montant dépensé |
|
Nom de l'organisme 1 (*): CEFIPRA |
||
Invitations des partenaires |
2000 (Anurag Kumar) |
|
Missions INRIA vers le partenaire |
1500 (Eitan Altman) |
|
Total |
3.500 |
|
Nom de l'organisme 2 (*): |
||
Invitations des partenaires |
|
|
Missions INRIA vers le partenaire |
|
|
Total |
|
|
(*) Ajouter ou supprimer des lignes au tableau ci-dessus
de façon à faire figurer tous les organismes ayant contribué au financement de
l'équipe associée
Total des financements externes dépensés |
3.500 |
Total des financements EA et externes dépensés |
27,807 |
1. Chercheurs Seniors
Nom |
statut (1) |
provenance |
destination |
objet (2) |
durée (3) |
Coût (si financement EA) |
Coût (si financement externe) |
Anurag Kumar |
Full Professeur |
IISc |
INRIA (Maestro) |
Collaboratioon |
Dix jours |
0,00 |
2000,00 |
Rajesh Sundaresan |
Associate Professor |
IISc |
INRIA (Maestro) |
Collaboration |
Trois semaines |
2.680,00 |
|
Vivek Borkar |
Full Professor |
TIFR Bombey |
INRIA (Trec et Maestro) |
Collaboration et participation dans colloque |
Deux semaines |
2.446,00
|
|
Eitan Altman |
DR |
INRIA |
IISc |
Collaboration |
Dix jours |
0,00 |
1500,00 |
Eitan Altman |
DR |
INRIA |
Univ of Pennsylvania |
Collaboration |
Une semaine |
2.765,00 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Total des durées |
62 jours |
2. Juniors
Nom |
statut (1) |
provenance |
destination |
objet (2) |
durée (3) |
Coût (si financement EA) |
Coût (si financement externe) |
Azad Amar |
PhD |
Avignon, |
INRIA (Maestro) |
salaire |
3 mois |
8.317,00 |
Le reste du salaire est paye par un projet européen |
Kamble Vijay |
Stagiaire |
Bombey |
INRIA (Maestro) |
salaire Egide |
2,5 mois |
3.744,00 |
|
Azad Amar |
PhD |
Avignon |
Grenoble |
workshop |
5 jours |
166,00 |
|
Kamble Vijay |
Stagiaire |
Avignon |
Grenoble |
workshop |
5 jours |
166,00 |
|
Kumar Dinesh |
PhD |
New York |
Avignon |
collaboration |
2,5 semaines |
1.065,00 |
|
Kumar Dinesh |
PhD |
New York |
Avignon |
collaboration |
2 semaines |
946,00 |
|
Silva Alonso |
PhD |
Paris |
Inde |
collaboration |
frais voyage |
681.61 |
|
Total des durées |
7 mois |
Description du programme scientifique de travail pour l'année 2009
Nous poursuivrons notre travail sur la modélisation, l’optimisation et la conception de nouveaux protocoles dans les réseaux d’accès sans fil ainsi que dans les réseaux adhoc sans fil.
1. Echanges
Décrivez les échanges prévus dans les
deux sens : invitations de chercheurs de votre partenaire et missions INRIA
vers votre partenaire ;
Précisez s'il s'agit de chercheurs
confirmés ou de juniors (stagiaires, doctorants, post-doctorants) ;
Motivez, si possible, les raisons
scientifiques (travail commun, workshop,..) et
précisez la durée prévue ;
Indiquez les étudiants impliqués dans
la proposition. Donnez une estimation de leur nombre, pour chaque partenaire,
et précisez si des thèses en cotutelle sont prévues ;
Résumez
ensuite ces informations dans les tableaux 1 et 2
ci-dessous en faisant une estimation budgétaire :
1. ESTIMATION
DES DÉPENSES EN MISSIONS INRIA VERS LE PARTENAIRE |
Nombre de personnes |
Coût estimé |
Chercheurs confirmés |
4 |
7200 |
Post-doctorants |
|
|
Doctorants |
2 |
2400 |
Stagiaires |
|
|
Autre (précisez) : |
|
|
Total |
|
9600 |
2. ESTIMATION
DES DÉPENSES EN INVITATIONS DES PARTENAIRES |
Nombre de personnes |
Coût estimé |
Chercheurs confirmés |
4 |
7200 |
Post-doctorants |
|
|
Doctorants |
2 |
2400 |
Stagiaires (bourse et mission) |
1 |
4000 |
Autre (précisez) : |
|
|
Total |
|
13600 |
2. Cofinancement
Cette coopération bénéficie-t-elle déjà d'un soutien financier de la part de
l'INRIA, de l'organisme étranger partenaire ou d'un organisme tiers (projet
européen, NSF, ...) ?
Indiquez ces éléments et donnez les montants associés.
3. Demande budgétaire
Indiquez, dans le tableau ci-dessous, le coût global estimé de la proposition
et le budget demandé à la DRI dans le cadre de cette Equipe Associée.
(maximum 20 K€ pour une prolongation
en 2e année et 10 K€ pour une 3e année).
Commentaires |
Montant |
A. Coût global de la proposition (total des tableaux 1 et 2 : invitations, missions, ...) |
23.200 |
B. Cofinancements utilisés (financements autres que Equipe Associée) |
|
Financement "Équipe
Associée" demandé (A.-B.) |
23.200 |
Remarques ou observations :
© INRIA - mise à jour le 15/08/2008