Direction des Relations Internationales (DRI)
Programme INRIA
"Equipes Associées"
(Demande de prolongation)
I.
DEFINITION
|
EQUIPE ASSOCIEE |
|
|
|
Demande de prolongation
pour 2010 |
|
Equipe-Projet INRIA
: MAESTRO, MESCAL, TREC |
Organisme étranger
partenaire : |
|
|||
|
Centre de recherche
INRIA : Sophia-Antipolis (Grenoble, ENS
Paris) |
Pays : INDE |
|
|||
|
|
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 francais |
Autre
participant francais |
|
Nom, prénom |
PRABHU Balakrishna |
TOUATI Corinne |
|
Grade/statut |
CR2 |
CR2 |
|
Organisme d'appartenance |
LAAS Toulouse |
INRIA Grenoble (MESCAL) |
|
Adresse postale |
Laboratoire d'Anaylse et d'Architecture des Système, 7, avenue du
Colonel Roche, 31077 Toulouse Cedex 4 |
Laboratoire d'Informatique de
Grenoble |
|
URL |
||
|
Téléphone |
0 5 61 33 64 82 |
04 76 61 20 53 |
|
Télécopie |
|
|
|
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 |
- 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) |
|
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. |
II. BILAN
2009
|
|
Programme
de travail initialement prévu pour 2009
Et les résultats obtenus
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.
Contrôle d’accès au canal radio dans les réseaux sans fil en présence de mobiles non-coopératifs
« Un grand nombre de travaux de
recherche existent (sous forme d’articles ou des brevets) sur la manière
de décider à chaque instant quel mobile accédera à un canal radio commun. Des
approches basées sur l’équité proportionnelle ont été implémentées dans
des équipements (station de base) qui sont commercialisées. La base théorique
de ces travaux repose sur l’hypothèse que la station de base reçoit une information
fiable sur l’état du canal de chaque mobile. Nous proposons de mettre en
question cette hypothèse et de concevoir et d’étudier des protocoles qui
prennent en comptent le faite que les mobiles puissent fausser
l’information sur le canal radio qu’ils transmettent afin
d’obtenir un meilleur débit. »
Obtained Results
We have identified the appropriate mathematical context to
model the above problem as that of Signalling Games. This
is a branch of game theory that is based on the following structure. There is
some random parameter with a probability distribution known to two interacting
players. Only one of them, say player 1, knows the realisation of that
parameter. This one sends a signal to the other player, who then takes an
action. This action determines the payoff of both players. Our problem indeed
maps into this one as follows. Player 1 who knows the realization is any of the
mobiles. The signal it sends to the other player is the signal that the mobile
sends to the base station (BS). The latter then takes a scheduling decision and
informs all mobiles who will transmit next. We identified the unique
equilibrium that this problem has and showed how to learn to converge to it
using a stochastic approximation algorithm. Our results will
be published in December 2009 in [KAES09].
La gestion des ressource et le problème d’association dans les radios cognitifs
« Les radios cognitifs sont des
terminaux intelligents qui sont conscients des réseaux disponibles et des
conditions radio liées à chaque réseau, et qui sont capables de se connecter à
des réseaux de technologies différents. Un élément central dans des réseaux
conçus pour ce type de terminaux est la possibilité d’offrir des services
de qualités différentes en laissant le choix entre ces services à l’usager.
Nous allons modéliser ce problème comme un jeu hiérarchique dont les acteurs
sont les mobiles (niveau 1) qui décident des services (du niveau de priorité) à
adopter, les opérateurs (niveau 2) qui décident quelle part du spectre
allouer à chaque niveau de priorité et comment choisir les tarifs
correspondants, et puis le propriétaire du réseau (niveau 3) qui choisi les
coûts des ressources à offrir aux fournisseurs de service. »
Obtained Results
We study
in [AKSS09] the question of
determining locations of base stations (BSs) that may
belong to the same or to competing service providers, taking into account the
impact of these decisions on the behavior of
intelligent mobile terminals who can connect to the
base station that offers the best utility. We first study the SINR
association-game: we determine the cells corresponding to each base stations, i.e. the locations at which mobile terminals
prefer to connect to a given base station than to others. The Signal to
Interference and Noise Ratio (SINR) is used as the quantity that determines the
association. We make some surprising observations: (i)
displacing a base station a little in one direction may result in a
displacement of the boundary of the corresponding cell to the opposite
direction; (ii) A cell corresponding to a BS may be the union of disconnected
sub-cells. We then study the Stackelberg equilibrium
in the combined BS location and mobile association problem: we determine where
to locate the BSs so as to maximize the revenues
obtained at the induced SINR mobile association game. We consider the cases of
single frequency band and two frequency bands of operation. Finally, we also
consider Stackelberg equilibria
in two frequency systems with successive interference cancellation.
We consider in [KAS09a]
a scenario in which a regulator owns the spectrum in a certain region. A number
of service providers lease spectrum from the regulator. Each service provider
sets up a base station to serve mobile subscribers in the region. This
gives rise to a hierarchical
game with players at three levels: the mobile subscribers (level
1), the service providers (level 2) and
the regulator (level 3). In the game at level 3, the regulator chooses
the price at which to lease the
spectrum. In the game at level 2, each service provider chooses the quantity of
spectrum to lease from the regulator and the rate at which to charge the mobile subscribers. We consider
the situation in which
each service provider has two kinds of mobile subscribers:
primary users, who receive high-priority
service and secondary users who receive
low-priority service. In the game at level 1, each mobile subscriber chooses a service provider
to join and whether to become a primary
or secondary user.
We consider the
situation in which base stations of two service providers serve adjacent cells on a
straight line. We define two kinds of access by the mobile subscribers:
rate-fair and time-fair access. First,
we analyze the game at level 1 when each mobile subscriber's service provider is fixed and it
chooses whether to be a primary or
secondary user of its service provider. We show that a threshold-type Wardrop equilbrium exists for both rate-fair and time-fair
access. Next, we consider the case of
migration in which a mobile subscriber can choose the service provider it
wants to join. We show that a threshold-type
Wardrop equilbrium exists, first for the simple
case when there are no secondary users
and then for the general case with
primary as well as secondary users. Finally, we consider the case in which the service
provider chooses which of its mobile subscribers will be primary and secondary and determine
the optimal choices that maximize the
total throughput of all mobile subscribers
Optimisation et Contrôle dans les réseaux Ad Hoc
« Nous
allons travailler sur deux thèmes : les réseaux Ad-Hoc véhiculaire (VANETs) et les réseaux tolérant les délais (DTN –
Delay Tolerant Networks).
VANETs : Il s’agit de réseaux basés sur les
liens provisoires sans fil entre des voitures qui roulent sur des routes.
Imaginons une source immobile qui souhaite envoyer un fichier à une destination
hors de sa portée. Il peut découper le message en paquets et les transmettre
par d’autres voitures qui vont dans la direction de sa destination et qui
peuvent servir de relais. Nous supposons que la source peut connaitre la vitesse
des voitures qui passent et nous posons la questions à savoir si à un instant donné il faudrait tenter
d’envoyer un paquet ou bien il vaut mieux attendre qu’une voiture
qui roule plus rapidement passe. Nous formulerons ce problème dans le cadre
de processus de décision markoviens.
DTN Nous allons
travailler sur la modélisation des réseaux ad-hoc mobiles qui doivent diffuser
très rapidement un fichier (par exemple un vaccin contre un virus informatique etc). Nous proposerons des politiques de diffusions du
fichier qui tiennent en compte la consommation énergétique. Le contrôle
d’énergie peut se faire sous forme de décision de transmettre ou non
d’un paquet de données, ou sous forme de contrôle de puissance de
transmission qui détermine la portée de
la communication et donc la probabilité d’avoir un lien entre deux
nœuds à un instant donné. »
Résultats
obtenues
We
introduce in [KAS09b] a defence strategy that
quarantines the malware by reducing the communication range. This
countermeasure faces us to a trade-off: reducing the communication range
suppresses the spread of the malware, however, it also
negatively affects the performance of the network as the end-to-end
communication delay increases. We model the propagation of the malware as a
deterministic epidemic. Using an optimal control framework, we select the
optimal communication range that captures the above trade-off by minimizing a
global cost function. Using Pontryagin’s
Maximum Principle, we derive structural characteristics of the optimal communication
range as a function of time for two different cost functions.
Protocoles pour la gestion de l’énergie.
« Nous poursuivrons notre travail
sur l’optimisation des durées des périodes d’inactivité dans les
terminaux mobiles. Il s’agit des périodes durant lesquelles la
consommation d’énergie des mobiles est minime ce qui permet
d’épargner l’énergie de la batterie du mobile afin de
prolonger sa duré de vie. Cette période est déclenchée quand le mobile ne
reçoit ou n’envoie plus de trafic durant un certain temps. Les résultats
obtenus dans la première année ont été basées sur l’hypothèse d’un
trafic d’entrée avec une distribution de Poisson. Notre but dans la
deuxième année est d’étudier des processus d’arrivées généraux. Les
critères à optimiser seront d’une part la consommation d’énergie et
d’autre part l’espérance du temps d’attente due aux périodes
d’inactivité. »
Résultats obtenus
The work in [AAABP09] considers systems with inactivity periods that have an
unknown duration. We study the question of scheduling ``waking up'' instants in
which a server can check whether the inactivity period is over. There is a cost
proportional to the delay from the moment the inactivity period ends until the
server discovers it, a (small) running cost while the server is away and also a
cost for waking up. As an application to the problem, we consider the energy
management in WiMax where the mobiles who are inactive reduce their energy consumption by entering
a sleep mode. Various standards exist which impose specific scheduling policies
for waking-up in wireless devices. We check these and identify optimal policies
under various statistical assumptions or exponential inactivity periods. We
show that periodic fixed vacation durations are optimal and we derive the optimal
period. We show that this structure does not hold for other inactivity
distributions but we manage to obtain the policy that performs best among the
periodic ones. We finally obtain structural properties for optimal policies for
the case of arbitrary distribution of inactivity periods
Others
We
consider in [RAK09] a dense, ad hoc wireless network,
confined to a small region. The wireless network is operated as a single cell,
i.e., only one successful transmission is supported at a time. Data packets are
sent between source destination pairs by multihop
relaying. We assume that nodes self-organise into a multihop
network such that all hops are of length d meters, where d is a design
parameter. There is a contention based multiaccess
scheme, and it is assumed that every node always has data to send, either
originated from it or a transit packet (saturation assumption). In this
scenario, we seek to maximize a measure of the transport capacity of the
network (measured in bit-meters per second) over power controls (in a fading
environment) and over the hop distance d, subject to an average power
constraint. We first argue that for a dense collection of nodes confined to a
small region, single cell operation is efficient for single user decoding
transceivers. Then, operating the dense ad hoc wireless network (described
above) as a single cell, we study the hop length and power control that
maximizes the transport capacity for a given network power constraint.
We mention an additional fruit of
our collaboration, not directly related to the theme of Dawn. In [AKB09]. Routing games, as introduced in the pioneering work
of Orda, Rom and Shimkin
(1993), are very closely related to the traffic assignment problems as already
studied by Wardrop and to congestion games, as introduced by Rosenthal. But
they exhibit more complex behavior: often the
equilibrium is not unique, and computation of equilibria
is typically harder. They cannot be transformed in general into an equivalent
global optimization problem as is the case with congestion games and in the
traffic assignment problem which possess a potential under fairly general
conditions. In this paper we study convergence of various learning schemes to an equilibrium in the problem of routing games. We are able
to considerably extend previous published results that were restricted to
routing into two parallel links. We study evolutionary-based learning
algorithms and establish their convergence for general topologies.
References
[AAABP09] Amar Prakash Azad, Sara Alouf, Eitan
Altman, Vivek S Borkar and Georgios Stavrou Pascos, “Vacation Policy Optimization with
Application to IEEE 802.16e Power Saving Contro”, IEEE CDC 2009,
[AKB09] Eitan
Altman, Vijay Kamble and Vivek
Borkar,
"Learning algorithms in routing games", GameNets
International Conference on Game Theory for Networks, 13-15 May 2009, Bogazici University, Istanbul, Turkey.
[AKH09] Eitan
Altman, Anurag Kumar, and Yezekael
Hayel, “A Potential Game Approach for Uplink
Resource Allocation in a Multichannel Wireless Access Network,” Proc.
ACM/ICST International Workshop on Game Theory for Communication Networks
(GAMECOMM),
[AKSS09] Eitan Altman, Anurag Kumar, Chandramani K. Singh, Rajesh Sundaresan,"Spatial
SINR Games Combining Base Station Placement and Mobile Association", IEEE Infocom, Rio de Janeiro, Brazil, April 19-25, 2009Rapport
financier 2009
|
1. Dépenses EA (effectuées
sur les crédits de l'Equipe Associée) |
|
|
2. Dépenses externes (effectuées sur des financements hors EA) |
||
Bilan des échanges effectués en 2009
(1)
DR / CR / professeur
(2) colloque, thèse, stage, visite....
(3) précisez l'unité (mois, semaine..)
(1)
post-doc / doctorant / stagiaire
(2) colloque, thèse, stage,
visite....
(3) précisez l'unité (mois, semaine..)
Description
du programme scientifique de travail pour l'année 2010
III. PREVISIONS
2010
Programme de travail
o A Theoretical Framework for Hierarchical Routing
Games with Applications to Cognitive Radios
We shall pursue our work on
cognitive radio and study a hierarchical routing game model that arises when
groups of terminals have to decide in a non-cooperative way to which
access point or base station to connect,
or how to split their traffic between various access points. It is assumed that
there is a differentiation in terms of quality of service and in costs between
primary and secondary users. Thus the
congestion experienced by a pack et depends on its
priority level. Another differentiation
is made by compressing the packets in the low priority flow while leaving the
high priority flow intact. From the work of road traffic researchers on related
topics like studying class dependent equilibrium costs in routing games, we
have learnt that in most cases, computing an equilibrium
is very hard and moreover, one often looses the uniqueness of the equilibrium. We
shall search for conditions for the uniqueness of the equilibria
in these hierarchical games and study pricing issues that allow to differentiate between primary and secondary users
efficiently.
o Adversary control in Delay Tolerant Networks
We plan to pursue our work on
Delay Tolerant Networks. We shall consider in particular the following problems:
a.
Linear
quadratic differential games Consider a two hop routing system. When the source meets a mobile then it transmits to
it a packet with some probability, which can be considered as a control
decision. The number of mobiles is not
fixed. New mobiles arrive at some known rate. We consider in this paper some
malicious intruder that can propagate some virus that renders mobiles un-operational.
We formulate this problem as a zero sum dynamic game and derive the value of
the game as well as the optimal policies for both players. The main idea here
is to take advantage of the fact that the expected fraction of mobiles that
have the packet as well as the expected fraction of those that do not have the
packet, evolve in a linear way. By introducing a quadratic cost we shall be
able to cast the problem into the framework of linear quadratic zero sum games
for which solution techniques are well known.
b.
Predator-Pray
models. We also plan to use the
predator-pray formulation of Lotkera equation in
order to model propagation of e-viruses in a network
o Access control in the presence of non cooperative mobiles.
We shall pursue our work on that
issue. So far we have considered as objective to maximize the sum of
throughput. We shall next introduce the alpha-fairness concept .due to Mo and Walrand. We shall study the properties of the solutions as
a function o f alpha. We note that obtaining an alpha-fair solution is not any
more equivalent to a signalling hierarchical game.
o
Extending and finalizing on-going work
Much of our work in the two
first year has been published in conferences and we
plan to complete and extend this work and to have journal publications. In
particular, we plan to work on extending our models for spatial games to
dimension 2 (see models in [KAS09a] as well as [AKSS09]).
Programme
d'échanges avec budget prévisionnel
Décrivez les échanges prévus dans les
deux sens : invitations de chercheurs de votre partenaire et missions INRIA
vers votre partenaire ;|
1. ESTIMATION DES DÉPENSES EN MISSIONS INRIA VERS LE PARTENAIRE |
||
|
6600 dont
un financé par CEFIPRA. Missions pour travail en commun |
||
|
4000 Un
thésard ira à IISc pour 2 mois et un deuxième pour
un mois pour un travail
en commun. CEFIPRA financera 2000 Euros |
||
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, ...) ? CEFIPRA finance le postdoc pour deux ans
ainsi qu’un nombre petit de missions
Indiquez ces éléments et donnez les montants associés. Cefipra payera
environ 50 000 euros pour le postdoc sur deux
ans, y compris les frais de voyage. Ils payeront 4 missions en Inde et 4
missions de l’Inde durant tous les 3 ans à venir. Dans le projet avec
CEFIPRA particippe aussi l’université d’Avignon.
Le projet Maestro finance deux
thésards qui viennent de l’IISc sur des
ressources propres (leur salaire n’est pas inclus dans le tableau)
|
A. Coût global de la proposition (total des tableaux 1 et 2 : invitations, missions, ...) |
|
|
B. Cofinancements utilisés (financements autres que Equipe Associée) |
|
Balakrishna PRABHU, chercheur au LAAS (avait
fait ses études doctorales chez Maestro et ses études de MASTER au IISc avec Prof Chockalingam qui fait parti de l’EA) rejoint l’EA (voir tableau en haut)