Direction des Relations Internationales (DRI)

Programme INRIA "Equipes Associées"

 

I. DEFINITION

EQUIPE ASSOCIEE

DAWN (Distributed Algorithms for Wireless Networks)

sélection

2008

 

Equipe-Projet INRIA :  MAESTRO

Organisme étranger partenaire :  IISc Bangalore

Centre de recherche INRIA :  Sophia-Antipolis
Thème INRIA :   COM

Pays :   INDE

 

 

Coordinateur français

Coordinateur étranger

Nom, prénom

 ALTMAN Eitan

 KUMAR Anurag

Grade/statut

 DR2

Professor

Organisme d'appartenance
(précisez le département et/ou le laboratoire)

 INRIA Sophia Antipolis

 IISc

Adresse postale

 2004 Route des Lucioles

06902 Sophia Antipolis Cedex

 Dept. of Electrical Communication , Indian Institute of Science,

Bangalore, 560 012, India

URL

 www-sop.inria.fr/maestro/personnel/Eitan.Altman

 www.ece.iisc.ernet.in/~anurag/

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

 altman@sophia.inria.fr

 anurag@ece.iisc.ernet.in   

 

 

 

 

 

Autre participant étranger

Autre participant étranger

Nom, prénom

BORKAR Vivek

SARKAR Saswati

Grade/statut

 Professor

Professor

Organisme d'appartenance
(précisez le département et/ou le laboratoire)

Tata Institute of Fundamental Research

 Dept of Electrical and Systems Eng.

Univ of Pennsylvania

Adresse postale

 Homin Bhabha Road

Mumbai 400 005, INDIA

200 S. 33rd Street, Philadelphia,

19104, USA

URL

www.tcs.tifr.res.in/~borkar/PersonalPage.html

 www.seas.upenn.edu/~swati/

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

 borkar@tifr.res.in

  swati@ee.upenn.edu

 

NOTA : Si la proposition d'Equipe Associée comporte plusieurs partenaires, français et/ou étrangers, vous pouvez :
- soit ajouter une colonne,
- soit dupliquer le tableau ci-dessus autant de fois que nécessaire, en remplaçant "Coordinateur français ou étranger" par "Autre participant français ou étranger".


La proposition en bref

Titre de la thématique de collaboration (en français et en anglais) : Stratégies émergeantes pour les réseaux de communication sans fil (Emerging Strategies for Wireless Communication Networks)

 

Descriptif (environ 10 lignes) :

 

 

Tandis qu’un grand nombre des défis de base des réseaux sans fil ont été adressés avec succès, la demande croissante de trafic sur un spectre de fréquence radio limité a entrainé une reconsidération de la manière utilisée pour partager cette ressource.  Par conséquent, un domaine émergeant de recherche est celui du partage dynamique de la bande passante, domaine sur lequel nous travaillerons. L’autre thème que nous aborderons est celui des réseaux multi-saut sans fil (connus sous le nom de réseaux ad hoc). En particulier, nous nous intéresserons aux sujets émergeants tels que les communications coopératives, le codage réseau, ordonnancement dynamique distribué de paquets, ainsi que des modèles précis de réseaux maillés d’accès aléatoires maillés. Nous explorerons des techniques issues de la théorie des jeux coopératifs et non-coopératifs et des  jeux dynamiques évolutionnaires afin de modéliser le partage des ressources dans les réseaux sans fil. Finalement, nous proposons d’utiliser des modèles de continuum des routes pour étudier les limites des réseaux denses ad hoc.

 

 

 

Présentation de l'Équipe Associée

(environ 2 pages)

1. Présentation du coordinateur étranger
Rédigez, en quelques lignes, un bref CV du coordinateur de l'équipe étrangère.

 

Anurag Kumar obtained his B.Tech. degree in Electrical Engineering from the Indian Institute of Technology at Kanpur in 1977, and was awarded the President of India's Gold Medal. He then obtained the PhD degree from Cornell University (1981), where he worked under the guidance of Prof. T.L. Fine. He was a Member of Technical Staff at AT&T Bell Labs, Holmdel, N.J., for over 6 years. During this period he worked on the performance analysis of computer systems, communication networks, and manufacturing systems. Since 1988 he has been with the Indian Institute of Science (IISc), Bangalore, in the Dept. of Electrical Communication Engineering, where he is now a Professor, and is also currently the Chairman of the Electrical Sciences Division. From 1989 to 2003 he was also the Coordinator at IISc of the nationwide Education and Research Network (ERNET) Project, which established the first country-wide packet communication network in India.

He was co-chair of the International Teletraffic Congress (ITC) sponsored seminar on Teletraffic Analysis Methods, Bangalore, 1993; program chair of the Conference on Signal Processing, Communications, and Networking (SPCOM), Bangalore, 1997; program chair of the IEEE Bangalore Section sponsored International Conference on Communications, Control and Signal Processing (CCSP2000), Bangalore, 2000; General co-Chair for the IEEE Workshop on Information Theory, Bangalore, October 2002.

He is an Area Editor for IEEE Transactions on Networking, and for IEEE Communications Surveys and Tutorials.

He has been elected a Fellow of the IEEE, and a Fellow of the Indian National Science Academy (INSA), and has been a Fellow of the Indian National Academy of Engineering (INAE) since 1998

 

2. Historique de la collaboration

·               2.1. entre les équipes : description scientifique de la collaboration passée et des résultats déjà obtenus. Cette description contiendra notamment une liste des publications communes (i.e. celles cosignées par au moins un chercheur de chacun des partenaires).

 

Visites Longue Durée : Durant les cinq dernières années, nous avons eu une visite de deux mois  du coordinateur indien (Prof A. Kumar), une de quatre mois de Prof V. Sharma (de IISc) et une visite de cinq mois de S. Sarkar (Univ of Pennsylvania, actuellement en sabbatique à IISc).

 

Autres Visites :  Le coordinateur français a effectué deux visites de deux semaines à IISc durant les deux dernières années. MAESTRO a accueilli Prof. V. Borkar (Tata Institute) et Prof A. Chockalingam  (IISc) pour plusieurs visites de 2 semaines environs chacune. Nous avons eu deux visites de deux semaines de Prof. A. Kumar et une de son thésard (pour un mois)

 

Collaboration CEFIPRA  Nous avons été le premier projet dans le thème des sciences de l information à être sélectionné dans le cadre de CEFIPRA. Le projet nous a financé deux ans de postdoc de Dr Arzad Kherani qui avait fait sa thèse doctorale avec Prof A. Kumar.

 

Encadrement d’étudiants indiens:  Deux étudiants indiens ont fait leur thèse doctorale sous la direction de chercheurs de MAESTRO. Deux autres étudiants indiens sont inscrit en thèse chez Maestro. Trois parmi ces quatre thésards ont fait leurs études de MASTER à IISc (Dr Pariijat Dube sous la direction de Prof A. Kumar, Dr. Balakrishna Prabhu et Mr. Amar Azar sous la direction de Prof A. Chockalingam). .

 

Publications :  Nous avons plus de dix publications communes dans des actes de conférences internationales avec comité de lecture, et trois publications dans des revues internationales (dont deux dans IEEE/ACM Trans. on Networking, et une dans IEEE JSAC).

 

 

 

LIST OF JOINT PUBLICATIONS

 

 

 

Reviewed International Journals

 

Srinivas Shakkotai, Eitan Altman, Anurag Kumar, “The case for noncooperative multihousing of users to access points in IEEE 802.11 WLANs”, IEEE Journal on Selected Areas in Communications, Special Issue on Noncooperative Behaviour in Networking, Vol 25 No 6, 1207-1215, Aug 2007

 

Anurag Kumar, Eitan Altman, Daniele Miorandi and Munish Goyal,  ``New Insights from a Fixed Point Analysis of Single Cell IEEE  802.11 WLANs,'' IEEE/ACM Transactions on Networking In press, 2007

 

Venkatesh Ramaiyan, Anurag Kumar, and Eitan Altman, ``Fixed  Point Analysis of Single Cell IEEE 802.11e WLANs: Uniqueness and Multistability,'' IEEE Transactions on Networking, In press, 2007.

 

 

 

International Conferences:

 

A. Kumar, E. Altman, D. Miorandi, M. Goyal, "New Insights from a Fixed Point Analysis of Single Cell IEEE  802.11 WLANs", IEEE Infocom, Miami, March 13-17, 2005

 

R. Venkatesh, A. Kumar and E. Altman, "Fixed point analysis of single cell IEEE 802.11e WLANs: uniqueness, multistability and throughput differentiation", ACM Sigmetrics, June 6-10, 2005, Banff, Alberta, Canada.

 

E. Altman, A. Kumar, D. Kumar, R. Venkatesh, "Cooperative and Non-Cooperative Control in IEEE 802.11 WLANs", Proceedings of the 19th International Teletraffic Congress, Beijing, 29 August - 2 September, 2005.

 

A. Chockalingam, E. Altman, J. V. K. Murthy, and R. Kumar,  Cross-layer Design for Optimizing TCP Performance, Proc. IEEE ICC'2005, Seoul, May 2005

 

S. Shakkottai, E. Altman and A. Kumar, "The Case for Non-cooperative Multihoming of Users to Access Points in IEEE 802.11 WLANs", IEEE Infocom, 2006

 

D. Kumar, V. Ramaiyan, A. Kumar and E. Altman, "Capacity Optimizing Hop Distance in a Mobile Ad Hoc Network with Power Control", Proceedings of the {\it 4th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks} (WiOpt'06), Boston, Massachusetts, April 3 - 7, 2006.

 

V. Ramaiyan, A. Kumar and E. Altman, "Jointly Optimal Power Control and Routing for a Single Cell,

Dense, Ad hoc Wireless Network", Proceedings of WiOpt, Limasol, Cyprus, June 2007,

 

V. Sharma, Dharmendra, K. Prasad., E. Altman, "Opportunistic Scheduling of Wireless Links", 20th International Teletraffic Congress (ITC 20), Ottawa, Canada, 17-21 june, 2007.

 

Eitan Altman, Saswati Sarkar and Eilon Solan,  "Constrained Single-Controller Stochastic Games",  International Workshop on Tools for solving Structured Markov Chains (SMCtools) Nantes, France,  October 26, 2007.

 

 

 

Chapters in books:

 

E. Altman, V. S. Borkar, A. A. Kherani, P. Michiardi and R. Molva, "Some game-theoretic problems in wireless ad-hoc networks", C. Kostis and O. Spaniol (Eds.), Mobile and Wireless Systems, LNCS 3427, pp. 83-104, 2005.

·               2.2. entre l'INRIA et l'organisme partenaire : indiquez ici, le cas échéant, les liens de toute nature dont vous avez connaissance (coopération avec un autre projet INRIA, accord de coopération, laboratoire mixte, ...).
Il est recommandé d'insérer autant de liens possibles vers les sites de ces collaborations ou organismes.
Il vous est expressément demandé de placer ici un pointeur vers la page du pays concerné sur le site de la DRI de l'INRIA ("zones géographiques").

Lien avec l’Inde : http://www-direction.inria.fr/international/Page_Pays.php?pays=Inde

Lien avec l’USA : http://www-direction.inria.fr/international/Page_Pays.php?pays=USA

3. Impact : indiquez en quoi, à votre avis, cette association aurait un impact important :

·               3.1. sur la collaboration déjà existante avec votre partenaire

 

Le groupe de IISc contient le Dr. Rajesh Sundaresan avec qui nous n’avons pas  eu de collaborations passées. Il est un brillant jeune chercheur qui se spécialise dans la théorie de communication, de détection et surtout dans la théorie d’information. La théorie de l’information est très importantes dans les communications sans fil car elle permet de connaitre les limites des débits qu’on peut espérer en fonction du canal utilisé. Nous souhaitons acquérir des connaissances dans ce domaine en collaborant avec Dr Sundnaresan ainsi qu’avec le prof Vinod Sharma en profitant des bénéfices de la complémentarité dans nos expertises. Nous avons accueilli le prof Sharma une seule fois et nous souhaitons pouvoir collaborer régulièrement. Il enrichit la coopération en y ajoutant sa spécialisation dans la théorie de l’information. De même, la structure d’équipe associée nous permettra d’approfondir la coopération avec la prof Saswati Sarkar avec qui nous avons noué les premiers liens scientifiques cette année seulement. Sa présence nous enrichira par ses connaissances en ordonnancement, en complexité et en algorithmes distribués.  Nous avons entamé une étude sur les jeux coopératifs dans les réseaux et elle y a contribue son expérience riche dans le partage équitable de ressources.

 

La participation de prof. Vivek Borkar nous permettra de profiter de sa spécialisation en techniques d’apprentissage et de contrôle adaptatif. Ces outils sont des atouts pour l’étude et la conception de protocoles distribués dans les réseaux sans fil. Prof A. Chockalingam de l’équipe de IISc a des connaissances que nous n’avons pas sur la couche physique des réseaux sans fil, sur la coopération entre mobiles et plus généralement sur la théorie de communication (modulation, réception et détection etc.). Ces expertisent sont important pour le travail sur des approches inter-couches (« crosslayer design ») que nous souhaitons développer. Enfin, nous souhaitons profondément consolider la coopération avec le prof Anurag Kumar qui a des connaissances très riches des technologies émergeantes et avec qui nous espérons mener étudier ces technologies. C’est avec les professeurs Borkar, Chockalingam et Kumar que nous avons collaboré  dans le cadre du projet CEFIPRA et la structure d’équipe associée nous serait une opportunité précieuse de la poursuivre et de l’approfondir et de l’élargir.

 

Un autre impacte important serait de pouvoir continuer d’attirer des excellents étudiants en thèse et des postdoc. Les voyages prévus en Inde dans le cadre de l’équipe associée nous permettrons de nouer des contactes directes avec des candidats potentiels.

·               3.2. sur la collaboration avec d'autres projets INRIA

 

Il y a un intérêt mutuel de collaboration entre les collègues indiens et des membres des projets TREC et PLANETE.

·               3.3. sur la collaboration avec d'autres équipes de l'organisme étranger partenaire.

4. Divers : toute autre information que vous jugerez utile d'ajouter.



II. PREVISIONS 2008

Programme de travail

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 travaille 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).

 

Budget prévisionnel 2008

1. Co-financement

- 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, ...) ?

Nous avons eu une collaboration financée par CEFIPRA (voir http://www.cefipra.org/cefipra/index.htm) qui s’est terminée en 2006. Suite à une excellente évaluation de la collaboration, un financement supplémentaire de deux missions nous a été accordé


- Dans le cas où votre proposition serait retenue, vous parait-il probable d'obtenir de l'organisme étranger partenaire un soutien financier symétrique ?

Non

ESTIMATION PROSPECTIVE DES CO-FINANCEMENTS

Organisme

Montant

 CEFIPRA (financera deux missions)

   4000 Euros

 

 

 

 

 

 

 

 

Total

  4000 Euros

2. Echanges

Description des échanges prévus dans les deux sens : accueil de chercheurs de votre partenaire et missions INRIA vers votre partenaire.
Motivez l'utilité et l'intérêt spécifique des échanges et la complémentarité des équipes.
Précisez s'il s'agit de chercheurs confirmés ou de juniors (stagiaires, doctorants, post-doctorants). Spécifiez si ces échanges ont lieu dans le cadre d'un travail scientifique, d'organisation d'événements conjoints, de séminaires, tutoriels ou écoles, de formation par la recherche : indiquez les étudiants impliqués dans la collaboration, donnez une estimation de leur nombre de chaque côté et précisez si des thèses -éventuellement en co-tutelle- sont prévues (pour chaque échange, précisez la durée et le calendrier prévisionnel).

 

Missions de l’équipe française : Nous prévoyons un voyage de 2 semaines de K. Avratchenkov du projet Maestro pour visiter le prof Vivek Borkar (Tata Institute, Mumbai), et une mission de E. Altman de deux semaines au IISc.. Amar Azad, thésard au projet Maestro, ira à IISc pour un mois.

 

Nous envisageons deux missions de chercheurs confirmés de l’Inde à l’INRIA et une  mission de Porf Sarkar de l’USA. Chaque mission sera pour une période de deux semaines.

Un thésard indien et un thésard de l’USA viendront pour une période de un mois chacun.

 

L’apport de chaque participant et la complémentarité ont été décrit dans la rubrique “L’impact sur la collaboration existante”

 

ESTIMATION DES DÉPENSES

Montant

 

Nombre

Accueil

Missions

Total

Chercheurs confirmés

 5

6000 Euros

4000 Euros

10000 Euros

Post-doctorants

 

 

 

 

Doctorants

3

3000 Euros

2400 Euros

5400 Euros

Stagiaires

 

 

 

 

Complement these

1

8600 Euros

 

8600 Euros

Ordinateur portable

1

2000 Euros

 

2000 Euros

Total

 

 

 

26000 Euros

 

 

- total des co-financements

 4000 Euros

 

 

Financement "Équipe Associée" demandé

22000 Euros

Remarques ou observations :

Le projet Maestro finance de ses propres fonds la thèse doctorale de Mr Azad Amar qui vient de l’IISc (il avait effectué sa thèse de Master sous la direction de prof Chockalingam). Le cout de sa thèse est de 33 K Euros et nous demandons une participation d’environ le quart de cette somme.

 

L’ordinateur portable est demandé pour l’IISc pour un thésard qui travaillera sur ce projet.

 

 

 

 

 

© INRIA - mise à jour le 28/08/2007