GANESH: results obtained in the first year.
1. Ferry based MAC for Sensor Networks
Veeraruna Kavitha and Eitan Altman
We focus on a class of polling systems encountered while modelling the ferry based wireless local area network (FWLAN). A moving ferry, while walking in a predetermined cyclic path, communicates with the static nodes (or users) of the network via a wireless link. The ferry is assumed to stop and communicate with a node that has a packet to send or to receive, when it is closest to that node. The location distribution of the node to which or from which a packet arrives is assumed to have a support of positive Lebesgue measure. These features imply that polling models with finite number of queues cannot be used to model the system. We study in this paper the continuous polling systems with service disciplines that model the use of the FWLAN (and that are more complex than the classical exhaustive or gated services). Our approach is based on discretization of the continuous polling model. We propose a special way of discretizing the continuous system such that: (1) the known Pseudo conservation laws can be applied to obtain the stationary expected workload of the discrete systems; (2) the limit, of these ‘discretized’ expected workloads, equals the stationary expected workload of the continuous system.
2.
Controlled forwarding in delay-tolerant
networks:
C.Singh, E.Altman, A.Kumar, R.Sundaresan
We studied the trade-off between delivery delay and energy consumption in a
delay tolerant network in which a message (or a file) has to be delivered to
each of several destinations by epidemic relaying. In addition to the destinations,
there are several other nodes in the network that can assist in relaying the
message. We first assumed that, at every instant, all the nodes know the number
of relays carrying the packet and the number of destinations that have received
the packet. We formulated the problem as a controlled continuous time Markov
chain and derived the optimal closed loop control (i.e., forwarding policy).
However, in practice, the intermittent connectivity in the network implies that
the nodes may not have the required perfect knowledge of the system state. To
address this issue, we obtained an ODE (i.e., a deterministic fluid)
approximation for the optimally controlled Markov chain. This fluid
approximation also yields an asymptotically optimal open loop policy. Finally,
we evaluated the performance of the deterministic policy over finite networks.
Numerical results showed that this policy performs close to the optimal closed
loop policy. Our preliminary work was first presented at the WiOpt
2011 conference. We are now preparing a journal paper.
3.
Control of Sleep mode in WiMax terminals:
A. Prakash Azad, S. Alouf, E. Altman, V. Borkar and G. Paschos
This work uses Markov Decision Theory and filtering theory in order to
design efficient methods for trading off energy consideration versus
performance aspects in WiMax wireless terminals. Some standards already
exist and they already propose protcols that handle the "sleeping modes"
of terminals. We show in our work how by changing the parameters
of the existing protocols, the performance can be improved.
We further derive new protocols that provide globally optimal performance.
We illustrate our results using many numerical examples. This work
is a first step in a line of research that concerns green networking.
We plan to study in the future the control of switching on and off the whole
base station and not only the terminals so as to increase energy saving.
4.
A nonneutral network with side payments:
E.Altman, M.Hanawal, and R.Sundaresan
Representatives of several Internet access providers have expressed their wish
to see a substantial change in the pricing policies of the Internet. In
particular, they would like to see content providers pay for use of the
network, given the large amount of resources they use. This would be in clear
violation of the "network neutrality" principle that had
characterized the development of the wireline Internet. We proposed and studied
possible ways of implementing such payments and of regulating their amount. We
introduced a model that includes the internaut's behavior, the utilities of the
ISP and of the content providers, and the monetary flow that involves the
internauts, the ISP and content provider, and in particular, the content
provider's revenues from advertisements. We considered various game models and
studied the resulting equilibrium; they are all combinations of a
noncooperative game (in which the service and content providers determine how
much they will charge the internauts) with a cooperative one - the content
provider and the service provider bargain with each other over payments to one
another. We included in our model a possible asymmetric bargaining power which
is represented by a parameter (that varies between zero to one). We also
studied two dynamic game models and studied the convergence of prices to the
equilibrium values. This work appeared in 2012 as an invited paper in the
WPIN workshop.
5.
Opportunistic scheduling in the presence
of noncooperative users:
V.Kavitha, E.Altman, R.El-Azouzi, and R.Sundaresan
A central scheduling problem in wireless communications is that of allocating
resources to one of many mobile stations that have a common radio channel. Much
attention has been given to the design of efficient and fair scheduling schemes
that are centrally controlled by a base station (BS) whose decisions depend on
the channel conditions reported by each mobile. The BS is the only entity
taking decisions in this framework. The decisions are based on the reports of mobiles
on their radio channel conditions. We studied the scheduling problem from a
game-theoretic perspective in which some of the mobiles may be noncooperative
or strategic, and may not necessarily report their true channel conditions. We
modeled this situation as a signaling game and studied its equilibria. We
demonstrated that the only Perfect Bayesian Equilibria (PBE) of the signaling
game are of the babbling type: the noncooperative mobiles send signals
independent of their channel states, the BS simply ignores them, and allocates
channels based only on the prior information on the channel statistics. We then
proposed various approaches to enforce truthful signaling of the radio channel
conditions: a pricing approach, an approach based on some knowledge of the
mobiles’ policies, and an approach that replaces this knowledge by a stochastic
approximation approach that combines estimation and control. We further
identified other equilibria that involve non-truthful signaling.
This work is a substantial extension of a conference proceedings.
and has now appeared in the IEEE Transactions on Information Theory.
6.
Spatial SINR games of base stations placement and mobile association:
C. Singh, E. Altman, A. Kumar and R. Sundaresan,
We consider first the question of base station association: for a
given placement of base station, we search for a decision rule for each
one of a very large number of mobiles such that given the decisions of all
otehr mobiles, the decision of each mobile maximizes its own ratio between
his received signal to the received sum of noise and interference. We then
address the question of the optimal placement of the base-station.
We call a "cell" corresponding to a base station all the points that are
points in which mobiles connect to that base station. We obtain a paradoxical
behavior in which the cells are non-convex, and where some mobiles connect
to a base station where as others which are closer to that same base station
do not connect to it. This paper that is to appear in IEEE Transactions
on networking, extends our previous results (that appeared in a conference)
that restricted to points on the line, to the analysis of mobiles and base
stations on the plane. This work is the first one in several work that take
into account geometric aspects in designing wireless networks. Two other papers that use game theory in a context of stochastic geometry (the location of both mobiles and base station is given by independent planar Poisson processes)
have now appeared (Infocom 2012 and IEEE JSAC.
GANESH: Results expected for second year.
Our work is motivated by geographical forwarding of sporadic alarm packets to a base station in a wireless sensor network (WSN), where the nodes are sleep-wake cycling periodically and
asynchronously. We seek to develop local forwarding algorithms that can be tuned so as to trade-off the end-to-end delay against a total cost, such as the hop count or total energy. Our approach is to solve, at each forwarding node enroute to the sink, the local forwarding problem of
minimizing one-hop waiting delay subject to a lower bound constraint on a suitable reward offered by the next-hop relay; theconstraint serves to tune the trade-off. The reward metric used
for the local problem is based on the end-to-end total cost objective (for instance, when the total cost is hop count, we choose to use the progress towards sink made by a relay as the reward).
We have first studied the case where the number of relays is exactly known. Next we have considered the model where the number of relays is not known leading to a partially observable Markov decision model. For this case we have obtained inner and outer bounds for the optimal policy. Finally we have considered the case where the relays upon waking up reveal
only the probability distribution of their rewards. To know the exact reward value, the source has to send additional probe packets incurring additional cost. Our problem can be considered as a new variant of the asset selling problem studied in operations research literature.
The indian group has already obtained preliminary optimization result for the case of a single controller. This year we shall extend these with the INRIA group to the multi-agent framework by using game t heoretic approaches.
Markov decion processes with Risk sensitive criterion applied
to DTNs.
V. Kavitha, V. Borkar together with INRIA group.
In formulation of optimal stochastic control arising in delay tolerant
networks (DTNs), one is often faced with manimizing the probability
that some content is not delivered by some time $T$. One thus minimizes
costs that have the form of
$E ( \exp [-\lambda \int_0^T X_s ds ] ) $.
$X_s$ is the number of mobiles that have some packet at time $s$, and
$\lambda$ is the rate at which each packet meats the destination.
So far this problem has been treated by changing the order between
the expectation and the exponential. This is then a bound on the original
cost, and it is the bound that is minimized instead of the real cost.
With Prof Borkar and Prof Kavitha, we intend to
develop tools that allow us to directly
handle the original cost (by using the framework of risk sensitive
Markov Decision Theory) in order to get exact solutions rather than bounds.
GANESH: Changes in Participants.
GANESH: Requested Budget.