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.

We plan to further investigate topics 2 and 4 above. We plan in particular to prepare full journal versions of these. In addition, we shall start shall focus on some new items.

Geographical Forwarding in Sleep-Wake Cycling Wireless Sensor Networks
K.P. Naveen, Anurag Kumar, D. MANJUNATH and E. Altman

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.

Several students that participated in Ganesh, last year, and in the DOWN project, three years ago, have now graduated and have have received positions in IITs: Veeraruna Kavitha, Prasanna Chaporkar and Gaurav Kasbekar (IIT Mumbay) and Venkatesh Ramayan (IIT Madras). We thus included them in this year, as well as Joy Kury who is a young faculty member with whom we have also started collaboration. We further included D. Manjunath who already collaborated with us before, and Y. Narahari who specializes on game theory in social networks. We wish to collaborate with him on this topic in the future. Our group will also include a new postdoc (Parmod Kumar) who is financed by the joint laboratory in applied math (IFCAM).

GANESH: Requested Budget.

On 2012 our CEFIPRA project ends. This project has funded most travels and visits of both the French and the Indian partners. On the other hand we shall have funding from IFCAM (as mentioned in the previous paragraph for a postdoc and for an internship (that started this year). The postdoc was requested by IFCAM to have several travels to India so as to ensure strong collaboration with the Indian group, but we did not receive travel money for that, nor money for the material that both the postdoc as well as other indian invited persons would need. We therefore request the following:

Travels to India:
three trips for senior members, 2 weeks each: 4500 euros Travels to India:
two trips for the postdoc, 3 weeks each: 3600 euros.

Travels to France:
four trips for Indian members to France: 8000 euros.

Two Laptops for Indian postdoc and Indian visitting INRIA: 4200 euros.

Total request: 20 300 Euros