The marked increase in advertisements over online social networks (OSNs) necessitates the study of content propagation. We analyse the viral markets with content providers competing for the propagation of similar posts over OSNs. Towards this, we required a new variant of the branching process (BP), which we named as “Branching process with attack”; the entities upon wake up attempt to attack and acquire the opposite population; furthermore, each entity produces its offsprings as is usually considered in BPs. In addition to providing expressions for the growth rates of individual posts, dichotomy etc., we explore the co-existence/co-virality of posts; can the competing content spread and explode (number of unread/live copies of both posts grow significantly with time) simultaneously over the network? We prove that either one or both populations/posts get extinct or the populations settle to a unique co-existence equilibrium and derive the corresponding asymptotic ratios of the two populations/posts. Our analysis applies to large population networks focusing on mass behaviour, rather than micro details. Our study provides insights into two crucial design aspects, the number of seed users and the quality of the post. We performed Monte-Carlo simulations on synthetic and ego-twitter dataset by SNAP to support our findings.

We consider a single server queueing system with two classes of jobs: eager jobs with small sizes that require service to begin almost immediately upon arrival, and tolerant jobs with larger sizes that can wait for service. While blocking probability is the relevant performance metric for the eager class, the tolerant class seeks to minimize its mean sojourn time. In this paper, we discuss the performance of each class under dynamic scheduling policies, where the scheduling of both classes depends on the instantaneous state of the system. This analysis is carried out under a certain fluid limit, where the arrival rate and service rate of the eager class are scaled to infinity, holding the offered load constant. Our performance characterizations reveal a (dynamic) pseudo-conservation law that ties the performance of both the classes to the standalone blocking probabilities of the eager class. Further, the performance is robust to other specifics of the scheduling policies. We also characterize the Pareto frontier of the achievable region of performance vectors under the same fluid limit, and identify a (two-parameter) class of Pareto-complete scheduling policies.

When the base station density is sparse, users are often out of the coverage area of the cellular networks. In such scenarios, the users can rely on fellow users (willing to relay) to deliver delay tolerant information to a base station. Further, the users (and relays) can observe independent environments, during their traverse, if they are moving at considerable speeds. This provides them an opportunity to (independent) search for relays and or base stations at regular intervals of time. However, the user should beacon (transmit short pulses and wait for response), when it desires to be detected by the available relays in its neighbourhood. We derive the performance of such a system, accounting for the power utilized for beaconing, and obtain the beaconing policies that maximize the success (user/any previously contacted relay comes in contact with one of the base stations) probability of message delivery. The base stations and relays (at any given instance of time) are randomly distributed according to a Poisson Point process. We formulate the problem as a Markov Decision Process (MDP) to derive optimal policies depending on the system state (closed-loop). We show that the value function satisfies certain monotonicity properties and the optimal policy exhibits a certain switch-off property. We obtain an approximate solution for the continuous control and an exact solution for the ON-OFF (two action) control. Our investigations show that the closed-loop ON-OFF policies perform (almost) as good as the closed-loop continuous policies for all practically viable test cases. We further investigate open-loop policies for ON-OFF control, the policies that can be used when the system state is not known.

When agents compete for common resource and when the utilities derived by them, upon allocation, are independent across the agents and time slots, an opportunistic scheduler is used. The instantaneous utility of one agent can be low, however few among many would have `good' utility with high probability. Opportunistic schedulers utilize these opportunities, allocate resource at any time to a `good' agent. Efficient schedulers maximize the sum of accumulated utilities. Thus, every time `best' agent is allocated. This can result in negligible (unfair) accumulations for some agents, whose instantaneous utilities are `low' with high probability. Fair opportunistic schedulers are thus introduced (e.g., alpha-fair schedulers). We study their price of fairness (PoF). We group the agents into finite classes, each class having identical utilities and QoS requirements. We study the asymptotic PoF as agents increase, while maintaining class-wise proportions constant. Asymptotic PoF is less than one, depends only upon the differences in the largest utilities of individual classes and is less than the maximum such normalized differences. The PoF is zero initially and increases with increase in fairness requirements to an upper bound strictly less than one. We observe that the fair schedulers are essentially priority schedulers, which facilitated easy analysis of PoF.

Recently proposals are made to mount wireless trans-receivers on periodically moving vehicles. These vehicles were primarily meant to facilitate human transportation in places like large universities. The idea was to design economical networks using the already existing infrastructure, when delays can be tolerated. The salient feature of these networks is that the wireless server does not stop, rather provides the service to the users while on the move and as long as the contact is available. Thus the service of various users waiting on such networks is interlinked. One cannot model this system with existing continuous/discrete polling models, as the later assume the server to stop and serve before resuming with its journey. We obtain the conditions for stability and then the workload analysis. We also discuss optimal scheduling policies.

Delay Tolerant Networks (DTNs) have gained importance in the recent past, as cost-effective alternative, in scenarios where delays can be accommodated. They work well in discretely connected network, where there is no direct connectivity between some/all components of the system. But the mobility of nodes creates occasional contact opportunities. The randomly moving nodes cooperate to help a fixed source, in delivering message to a far away destination within the given time threshold. The objective is to optimize the delivery success probability, which turns out to be a risk sensitive cost. The success probability depends upon the contact rates, which in turn depend upon the power used by the nodes to remain visible. The more the power used by a node, the larger is the radius for which it is visible. However these nodes are power constrained. This leads to a constrained finite horizon, Risk sensitive Markov Decision Process (MDP). In this paper we propose a linear program (LP) based approach to solve the corresponding dynamic programming equations. This approach enables us in handling the constraints. We showed using numerical simulations that, given a hard power constraint, the solution of the constrained MDP performs significantly superior in comparison with a solution obtained by optimizing a joint cost.

We discuss the idea of differential fairness in polling systems. One such example scenario is: primary customers demand certain Quality of Service (QoS) and the idea is to utilize the surplus server capacity to serve a secondary class of customers. We use achievable region approach for this. Towards this, we consider a two queue polling system and study its `approximate achievable region' using a new class of delay priority kind of schedulers. We obtain this approximate region, via a limit polling system with fluid queues. The approximation is accurate in the limit when the arrival rates and the service rates converge towards infinity while maintaining the load factor and the ratio of arrival rates fixed. We show that the set of proposed schedulers and the exhaustive schedulers form a complete class: every point in the region is achieved by one of those schedulers. It is well known that exhaustive service policy optimizes system performances like unfinished work. In this paper, we show that it is also optimal from the perspective of individual queues. We further pose two constrained optimization problems: a) admission control, wherein the arrival rates of secondary customers is optimally designed; b) maximizing the revenue considering the losses when secondary arrival rate is fixed. We finally show that exhaustive service discipline at each queue turns out to be optimal.

The use of small cells has been proposed to increase system capacity by installation of base stations close to user location. Proximity of the base station with the user equipment also implies lesser power requirement for transmitting the same information. Thus one may expect improvement in energy efficiency. But installing a large number of base stations can also lead to an increase in the total energy consumption of the system. To combat this, mechanisms have been proposed to switch OFF these base stations at times of low load. In this paper, we consider the problem of finding the fraction of base stations that can be switched OFF while maintaining quality of service (measured in terms of the average waiting time of users), for given load conditions. We also obtain the optimal switch OFF pattern. We do this in two steps. First, we determine the optimal ON-OFF pattern of base stations and user-base station association policy for a fixed fraction of base stations to be switched OFF. Then, we find the maximum fraction of base stations that can be switched OFF for given load conditions.

We consider the problem of “fair” scheduling the resources to one of the many mobile stations by a centrally controlled base station (BS). The BS is the only entity taking decisions in this framework based on truthful information from the mobiles on their radio channel. We study the well-known family of parametric α-fair scheduling problems from a game-theoretic perspective in which some of the mobiles may be noncooperative. We first show that if the BS is unaware of the noncooperative behavior from the mobiles, the noncooperative mobiles become successful in snatching the resources from the other cooperative mobiles, resulting in unfair allocations. If the BS is aware of the noncooperative mobiles, a new game arises with BS as an additional player. It can then do better by neglecting the signals from the noncooperative mobiles. The BS, however, becomes successful in eliciting the truthful signals from the mobiles only when it uses additional information (signal statistics). This new policy along with the truthful signals from mobiles forms a Nash equilibrium (NE) that we call a Truth Revealing Equilibrium. Finally, we propose new iterative algorithms to implement fair scheduling policies that robustify the otherwise nonrobust (in presence of noncooperation) α-fair scheduling algorithms.

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. In this paper, we study 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 model this situation as a signaling game and study its equilibria. We demonstrate 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 propose 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 approximations approach that combines estimation and control. We further identify other equilibria that involve non-truthful signaling.

Epidemics dynamics can describe the dissemination of information in delay tolerant networks, in peer to peer networks and in content delivery networks. The control of such dynamics has thus gained a central role in all of these areas. However, a major difficulty in this context is that the objective functions to be optimized are often not additive in time but are rather multiplicative. The classical objective function in DTNs, i.e., the successful delivery probability of a message within a given deadline, falls precisely in this category, because it takes often the form of the expectation of the exponent of some integral cost. So far, models involving such costs have been solved by interchanging the order of expectation and the exponential function. While reducing the problem to a standard optimal control problem, this interchange is only tight in the mean field limit obtained as the population tends to infinity. In this paper we identify a general framework from optimal control in finance, known as risk sensitive control, which let us handle the original (multiplicative) cost and obtain solutions to several novel control problems in DTNs. In particular, we can derive the structure of state-dependent controls that optimize transmission power at the source node. Further, we can account for the propagation loss factor of the wireless medium while obtaining these controls, and, finally, we address power control at the destination node, resulting in a novel threshold optimal activation policy. Combined optimal power control at source and destination nodes is also obtained.

In recent years there has been an increasing awareness that the deployment as well as utilization of new information technology may have some negative ecological impact. This includes awareness to energy consumption which could have negative consequences on the environment. In recent years, it was suggested to increase energy saving by deactivating base stations during periods in which the traffic is expected to be low. In this paper we study the optimal deactivation policies, using recent tools from Multimodularity (which is the analog concept of convexity in optimization over integers). We consider two scenarios: In the first case, a central control derives the optimal open loop policies so as to maximize the expected throughput of the system given that at least a certain percentage of Base stations are deactivated (switched OFF). In the second case, we derive optimal open loop polices, which each base station can employ in a decentralized manner to minimize the average buffer occupancy cost when the fraction of time for which the BS station is deactivated (idle mode) is lower bounded. In both the cases, we show that the cost structure is Multimodular and characterize the structure of optimal policies.

Power allocation to satisfy user demands in the presence of large number of interferers in a multicellular network is a challenging task. Further, the power to be allocated depends upon the system architecture, for example upon components like coding, modulation, transmit precoder, rate allocation algorithms, available knowledge of the interfering channels, etc. This calls for an algorithm via which each base station in the network can simultaneously allocate power to their respective users so as to meet their demands (when they are within the achievable limits), using whatever information is available of the other users. The goal of our research is to propose one such algorithm which in fact is universal: the proposed algorithm works from a fully co-operative setting to almost no co-operation and or for any configuration of modulation, rate allocation, etc. schemes. The algorithm asymptotically satisfies the user demands, running simultaneously and independently within a given total power budget at each base station. Further, it requires minimal information to achieve this: every base station needs to know its own users demands, its total power constraint and the transmission rates allocated to its users in every time slot. We formulate the power allocation problem in a system specific game theoretic setting, define system specific capacity region and analyze the proposed algorithm using ordinary differential equation (ODE) framework. Simulations confirm the effectiveness of the proposed algorithm.

We propose an energy efficient distributed cooperative Change Detection scheme called DualCUSUM based on Page's CUSUM algorithm. In the algorithm, each sensor runs a CUSUM and transmits only when the CUSUM is above some threshold. The transmissions from the sensors are fused at the physical layer. The channel is modeled as a Multiple Access Channel (MAC) corrupted with noise. The fusion center performs another CUSUM to detect the change. The algorithm performs better than several existing schemes when energy is at a premium. We generalize the algorithm to also include nonparametric CUSUM and provide a unified analysis. Our results show that while the false alarm probability is smaller for observation distribution with a lighter tail, the detection delay is asymptotically the same for any distribution. Consequently, we provide a new viewpoint on why parametric CUSUM performs better than nonparametric CUSUM. In the process, we also develop new results on a reflected random walk which can be of independent interest.

We consider the problem of centrally controlled 'fair' scheduling of resources to one of the many mobile stations connected to a base station (BS). The BS is the only entity making decisions in this framework based on truthful information from the mobiles on their radio channel. We study the well-known family of parametric α-fair scheduling problems from a game-theoretic perspective in which some of the mobiles may be noncooperative. We first show that if the BS is unaware of the noncooperative behavior from the mobiles, the noncooperative mobiles become successful in snatching the resources from the other cooperative mobiles, resulting in unfair allocations. If the BS is aware of the noncooperative mobiles, a new game arises with BS as an additional player. It can then do better by neglecting the signals from the noncooperative mobiles. The BS, however, becomes successful in eliciting the truthful signals from the mobiles only when it uses additional information (signal statistics). This new policy along with the truthful signals from mobiles forms a Nash Equilibrium (NE) called a Truth Revealing Equilibrium. Finally, we propose new iterative algorithms to implement fair scheduling policies that robustify the otherwise non-robust (in presence of noncooperation) α-fair scheduling algorithms.

We propose a simple and energy efficient distributed change detection scheme for sensor networks based on Page's parametric CUSUM algorithm. The sensor observations are IID over time and across the sensors conditioned on the change variable. Each sensor runs CUSUM and transmits only when the CUSUM is above some threshold. The transmissions from the sensors are fused at the physical layer. The channel is modeled as a multiple access channel (MAC) corrupted with IID noise. The fusion center which is the global decision maker, performs another CUSUM to detect the change. We provide the analysis and simulation results for our scheme and compare the performance with an existing scheme which ensures energy efficiency via optimal power selection.

Semi blind/blind equalizers are believed to work unsatisfactorily in fading MIMO channels compared to training based methods, due to slow convergence or high computational complexity. We revisit this issue. Defining a 'composite' channel for each equalizer, we compare the three algorithms based on the capacity of this channel. We show that, in a Rician (with line of sight, LOS) environment, semi blind/blind algorithms outperform training equalizers, but in Rayleigh channels, it is better to use training based methods. We also find the optimum training size in training and semi blind methods.