Evolving Random Geometric Graph Models for Mobile Wireless Networks

We consider evolving exponential RGGs in one dimension and characterize the time dependent behavior of some of their topological properties. We consider two evolution models and study one of them detail while providing a summary of the results for the other. In the first model, the inter-nodal gaps evolve according to an exponential AR(1) process that makes the stationary distribution of the node locations exponential. For this model we obtain the one-step conditional connectivity probabilities and extend it to the k-step case. Finite and asymptotic analysis are given. We then obtain the k-step connectivity probability conditioned on the network being disconnected. We also derive the pmf of the first passage time for a connected network to become disconnected. We then describe a random birth-death model where at each instant, the node locations evolve according to an AR(1) process. In addition, a random node is allowed to die while giving birth to a node at another location. We derive properties similar to those above.

Carnatic music analysis: Shadja, swara identification and rAga verification in AlApana using stochastic models

We analyze the AlApana of a Carnatic music piece without the prior knowledge of the singer or the rAga. AlApana is ameans to communicate to the audience, the flavor or the bhAva of the rAga through the permitted notes and its phrases. The input to our analysis is a recording of the vocal AlApana along with the accompanying instrument. The AdhAra shadja(base note) of the singer for that AlApana is estimated through a stochastic model of note frequencies. Based on the shadja, we identify the notes (swaras) used in the AlApana using a semi-continuous GMM. Using the probabilities of each note interval, we recognize swaras of the AlApana. For sampurNa rAgas, we can identify the possible rAga, based on the swaras. We have been able to achieve correct shadja identification, which is crucial to all further steps, in 88.8% of 55 AlApanas. Among them (48 AlApanas of 7 rAgas), we get 91.5% correct swara identification and 62.13% correct R (rAga) accuracy.

Hybrid Bayesian Classifier for Improved Classification Accuracy

The widely used Bayesian classifier is based on the assumption of equal prior probabilities for all the classes. However, inclusion of equal prior probabilities may not guarantee high classification accuracy for the individual classes. Here, we propose a novel technique-Hybrid Bayesian Classifier (HBC)-where the class prior probabilities are determined by unmixing a supplemental low spatial-high spectral resolution multispectral (MS) data that are assigned to every pixel in a high spatial-low spectral resolution MS data in Bayesian classification. This is demonstrated with two separate experiments-first, class abundances are estimated per pixel by unmixing Moderate Resolution Imaging Spectroradiometer data to be used as prior probabilities, while posterior probabilities are determined from the training data obtained from ground. These have been used for classifying the Indian Remote Sensing Satellite LISS-III MS data through Bayesian classifier. In the second experiment, abundances obtained by unmixing Landsat Enhanced Thematic Mapper Plus are used as priors, and posterior probabilities are determined from the ground data to classify IKONOS MS images through Bayesian classifier. The results indicated that HBC systematically exploited the information from two image sources, improving the overall accuracy of LISS-III MS classification by 6% and IKONOS MS classification by 9%. Inclusion of prior probabilities increased the average producer's and user's accuracies by 5.5% and 6.5% in case of LISS-III MS with six classes and 12.5% and 5.4% in IKONOS MS for five classes considered.

Theoretical analysis of photoinduced H-atom elimination in thiophenol

The photoinduced hydrogen elimination reaction in thiophenol via the conical intersections of the dissociative (1)pi sigma* excited state with the bound (1)pi pi* excited state and the electronic ground state has been investigated with ab initio electronic-structure calculations and time-dependent quantum wave-packet calculations. A screening of the coupling constants of the symmetry-allowed coupling modes at the (1)pi pi*-(1)pi sigma* and (1)pi sigma*-S-0 conical intersection shows that the SH torsional mode is by far the most important coupling mode at both conical intersections. A model including three intersecting potential-energy surfaces (S-0, (1)pi pi*, (1)pi sigma*) and two nuclear degrees of freedom (SH stretch and SH torsion) has been constructed on the basis of ab initio complete-active-space self-consistent field and multireference second-order perturbation theory calculations. The nonadiabatic quantum wave-packet dynamics initiated by optical excitation of the (1)pi pi* and (1)pi sigma* states has been explored for this three-state two-coordinate model. The photodissociation dynamics is characterized in terms of snapshots of time-dependent wave packets, time-dependent electronic population probabilities, and the branching ratio of the (2)sigma/(2)pi electronic states of the thiophenoxyl radical. The dependence of the timescale of the photodissociation process and the branching ratio on the initial excitation of the SH stretching and SH torsional vibrations has been analyzed. It is shown that the node structure, which is imposed on the nuclear wave packets by the initial vibrational preparation as well as by the transitions through the conical intersections, has a profound effect on the photodissociation dynamics. The effect of additional weak coupling modes of CC twist (nu(16a)) and ring-distortion (nu(16b)) character has been investigated with three-dimensional and four-dimensional time-dependent wave-packet calculations, and has been found to be minor. (C) 2012 American Institute of Physics. http://dx.doi.org/10.1063/1.4709608]

Relaxation and jump dynamics of water at the mica interface

The orientational relaxation dynamics of water confined between mica surfaces is investigated using molecular dynamics simulations. The study illustrates the wide heterogeneity that exists in the dynamics of water adjacent to a strongly hydrophilic surface such as mica. Analysis of the survival probabilities in different layers is carried out by normalizing the corresponding relaxation times with bulk water layers of similar thickness. A 10-fold increase in the survival times is observed for water directly in contact with the mica surface and a non-monotonic variation in the survival times is observed moving away from the mica surface to the bulk-like interior. The orientational relaxation time is highest for water in the contact layer, decreasing monotonically away from the surface. In all cases the ratio of the relaxation times of the 1st and 2nd rank Legendre polynomials of the HH bond vector is found to lie between 1.5 and 1.9 indicating that the reorientational relaxation in the different water layers is governed by jump dynamics. The orientational dynamics of water in the contact layer is particularly novel and is found to undergo distinct two-dimensional hydrogen bond jump reorientational dynamics with an average waiting time of 4.97 ps. The waiting time distribution is found to possess a long tail extending beyond 15 ps. Unlike previously observed jump dynamics in bulk water and other surfaces, jump events in the mica contact layer occur between hydrogen bonds formed by the water molecule and acceptor oxygens on the mica surface. Despite slowing down of the water orientational relaxation near the surface, life-times of water in the hydration shell of the K ion are comparable to that observed in bulk salt solutions. (C) 2012 American Institute of Physics. http://dx.doi.org/10.1063/1.4717710]

Computational investigations on covalent dimerization/oligomerization of polyacenes: Is it relevant to soot formation?

We have postulated a novel pathway that could assist in the nucleation of soot particles through covalent dimerization and oligomerizations of a variety of PAHs. DFT calculations were performed with the objective of obtaining the relative thermal stabilities and formation probabilities of oligomeric species that exploit the facile dimerization that is known to occur in linear oligoacenes. We propose that the presence of small stretches of linear oligoacence (tetracene or longer) in extended PAH, either embedded or tethered, would be adequate for enabling the formation of such dimeric and oligomeric adducts; these could then serve as nuclei for the growth of soot particles. Our studies also reveal the importance of p-stacking interactions between extended aromatic frameworks in governing the relative stabilities of the oligomeric species that are formed. (c) 2012 Wiley Periodicals, Inc.

Probabilistic Shared Cache Management (PriSM)

Effective sharing of the last level cache has a significant influence on the overall performance of a multicore system. We observe that existing solutions control cache occupancy at a coarser granularity, do not scale well to large core counts and in some cases lack the flexibility to support a variety of performance goals. In this paper, we propose Probabilistic Shared Cache Management (PriSM), a framework to manage the cache occupancy of different cores at cache block granularity by controlling their eviction probabilities. The proposed framework requires only simple hardware changes to implement, can scale to larger core count and is flexible enough to support a variety of performance goals. We demonstrate the flexibility of PriSM, by computing the eviction probabilities needed to achieve goals like hit-maximization, fairness and QOS. PriSM-HitMax improves performance by 18.7% over LRU and 11.8% over previously proposed schemes in a sixteen core machine. PriSM-Fairness improves fairness over existing solutions by 23.3% along with a performance improvement of 19.0%. PriSM-QOS successfully achieves the desired QOS targets.

Active Sequential Hypothesis Testing with Application to a Visual Search Problem

We consider a visual search problem studied by Sripati and Olson where the objective is to identify an oddball image embedded among multiple distractor images as quickly as possible. We model this visual search task as an active sequential hypothesis testing problem (ASHT problem). Chernoff in 1959 proposed a policy in which the expected delay to decision is asymptotically optimal. The asymptotics is under vanishing error probabilities. We first prove a stronger property on the moments of the delay until a decision, under the same asymptotics. Applying the result to the visual search problem, we then propose a ``neuronal metric'' on the measured neuronal responses that captures the discriminability between images. From empirical study we obtain a remarkable correlation (r = 0.90) between the proposed neuronal metric and speed of discrimination between the images. Although this correlation is lower than with the L-1 metric used by Sripati and Olson, this metric has the advantage of being firmly grounded in formal decision theory.

Truthful multi-armed bandit mechanisms for multi-slot sponsored search auctions

In pay-per-click sponsored search auctions which are currently extensively used by search engines, the auction for a keyword involves a certain number of advertisers (say k) competing for available slots (say m) to display their advertisements (ads for short). A sponsored search auction for a keyword is typically conducted for a number of rounds (say T). There are click probabilities mu(ij) associated with each agent slot pair (agent i and slot j). The search engine would like to maximize the social welfare of the advertisers, that is, the sum of values of the advertisers for the keyword. However, the search engine does not know the true values advertisers have for a click to their respective advertisements and also does not know the click probabilities. A key problem for the search engine therefore is to learn these click probabilities during the initial rounds of the auction and also to ensure that the auction mechanism is truthful. Mechanisms for addressing such learning and incentives issues have recently been introduced. These mechanisms, due to their connection to the multi-armed bandit problem, are aptly referred to as multi-armed bandit (MAB) mechanisms. When m = 1, exact characterizations for truthful MAB mechanisms are available in the literature. Recent work has focused on the more realistic but non-trivial general case when m > 1 and a few promising results have started appearing. In this article, we consider this general case when m > 1 and prove several interesting results. Our contributions include: (1) When, mu(ij)s are unconstrained, we prove that any truthful mechanism must satisfy strong pointwise monotonicity and show that the regret will be Theta T7) for such mechanisms. (2) When the clicks on the ads follow a certain click precedence property, we show that weak pointwise monotonicity is necessary for MAB mechanisms to be truthful. (3) If the search engine has a certain coarse pre-estimate of mu(ij) values and wishes to update them during the course of the T rounds, we show that weak pointwise monotonicity and type-I separatedness are necessary while weak pointwise monotonicity and type-II separatedness are sufficient conditions for the MAB mechanisms to be truthful. (4) If the click probabilities are separable into agent-specific and slot-specific terms, we provide a characterization of MAB mechanisms that are truthful in expectation.

Incentive Compatible Influence Maximization in Social Networks with Application to Viral Marketing

Information diffusion and influence maximization are important and extensively studied problems in social networks. Various models and algorithms have been proposed in the literature in the context of the influence maximization problem. A crucial assumption in all these studies is that the influence probabilities are known to the social planner. This assumption is unrealistic since the influence probabilities are usually private information of the individual agents and strategic agents may not reveal them truthfully. Moreover, the influence probabilities could vary significantly with the type of the information flowing in the network and the time at which the information is propagating in the network. In this paper, we use a mechanism design approach to elicit influence probabilities truthfully from the agents. Our main contribution is to design a scoring rule based mechanism in the context of the influencer-influencee model. In particular, we show the incentive compatibility of the mechanisms and propose a reverse weighted scoring rule based mechanism as an appropriate mechanism to use.

Smoothed functional and Quasi-Newton algorithms for routing in multi-stage queueing network with constraints

We consider the problem of optimal routing in a multi-stage network of queues with constraints on queue lengths. We develop three algorithms for probabilistic routing for this problem using only the total end-to-end delays. These algorithms use the smoothed functional (SF) approach to optimize the routing probabilities. In our model all the queues are assumed to have constraints on the average queue length. We also propose a novel quasi-Newton based SF algorithm. Policies like Join Shortest Queue or Least Work Left work only for unconstrained routing. Besides assuming knowledge of the queue length at all the queues. If the only information available is the expected end-to-end delay as with our case such policies cannot be used. We also give simulation results showing the performance of the SF algorithms for this problem.

Analytical model for congestion control and throughput with TCP CUBIC connections

We develop a Markov model for a TCP CUBIC connection. Next we use it to obtain approximate expressions for throughput when there may be queuing in the network. Finally we provide the throughputs different TCP CUBIC and TCP NewReno connections obtain while sharing a channel when they may have different round trip delays and packet loss probabilities.

Modeling the effect of transmission errors on TCP controlled transfers over infrastructure 802.11 wireless LANs

There have been several studies on the performance of TCP controlled transfers over an infrastructure IEEE 802.11 WLAN, assuming perfect channel conditions. In this paper, we develop an analytical model for the throughput of TCP controlled file transfers over the IEEE 802.11 DCF with different packet error probabilities for the stations, accounting for the effect of packet drops on the TCP window. Our analysis proceeds by combining two models: one is an extension of the usual TCP-over-DCF model for an infrastructure WLAN, where the throughput of a station depends on the probability that the head-of-the-line packet at the Access Point belongs to that station; the second is a model for the TCP window process for connections with different drop probabilities. Iterative calculations between these models yields the head-of-the-line probabilities, and then, performance measures such as the throughputs and packet failure probabilities can be derived. We find that, due to MAC layer retransmissions, packet losses are rare even with high channel error probabilities and the stations obtain fair throughputs even when some of them have packet error probabilities as high as 0.1 or 0.2. For some restricted settings we are also able to model tail-drop loss at the AP. Although involving many approximations, the model captures the system behavior quite accurately, as compared with simulations.

Performance analysis of adaptive physical layer network coding for wireless two-way relaying

The performance analysis of adaptive physical layer network-coded two-way relaying scenario is presented which employs two phases: Multiple access (MA) phase and Broadcast (BC) phase. The deep channel fade conditions which occur at the relay referred as the singular fade states fall in the following two classes: (i) removable and (ii) non-removable singular fade states. With every singular fade state, we associate an error probability that the relay transmits a wrong network-coded symbol during the BC phase. It is shown that adaptive network coding provides a coding gain over fixed network coding, by making the error probabilities associated with the removable singular fade states contributing to the average Symbol Error Rate (SER) fall as SNR-2 instead of SNR-1. A high SNR upper-bound on the average end-to-end SER for the adaptive network coding scheme is derived, for a Rician fading scenario, which is found to be tight through simulations. Specifically, it is shown that for the adaptive network coding scheme, the probability that the relay node transmits a wrong network-coded symbol is upper-bounded by twice the average SER of a point-to-point fading channel, at high SNR. Also, it is shown that in a Rician fading scenario, it suffices to remove the effect of only those singular fade states which contribute dominantly to the average SER.

The evolution of complexity in social organization-A model using dominance-subordinate behavior in two social wasp species

Dominance and subordinate behaviors are important ingredients in the social organizations of group living animals. Behavioral observations on the two eusocial species Ropalidia marginata and Ropalidia cyathiformis suggest varying complexities in their social systems. The queen of R. cyathiformis is an aggressive individual who usually holds the top position in the dominance hierarchy although she does not necessarily show the maximum number of acts of dominance, while the R. marginata queen rarely shows aggression and usually does not hold the top position in the dominance hierarchy of her colony. In R. marginata, more workers are involved in dominance-subordinate interactions as compared to R. cyathiformis. These differences are reflected in the distribution of dominance-subordinate interactions among the hierarchically ranked individuals in both the species. The percentage of dominance interactions decreases gradually with hierarchical ranks in R. marginata while in R. cyathiformis it first increases and then decreases. We use an agent-based model to investigate the underlying mechanism that could give rise to the observed patterns for both the species. The model assumes, besides some non-interacting individuals, the interaction probabilities of the agents depend on their pre-differentiated winning abilities. Our simulations show that if the queen takes up a strategy of being involved in a moderate number of dominance interactions, one could get the pattern similar to R. cyathiformis, while taking up the strategy of very low interactions by the queen could lead to the pattern of R. marginata. We infer that both the species follow a common interaction pattern, while the differences in their social organization are due to the slight changes in queen as well as worker strategies. These changes in strategies are expected to accompany the evolution of more complex societies from simpler ones.