Design of incentive compatible protocols for wireless networks: A game theoretic approach

In this thesis work, we design rigorous and efficient protocols/mechanisms for different types of wireless networks using a mechanism design [1] and game theoretic approach [2]. Our work can broadly be viewed in two parts. In the first part, we concentrate on ad hoc wireless networks [3] and [4]. In particular, we consider broadcast in these networks where each node is owned by independent and selfish users. Being selfish, these nodes do not forward the broadcast packets. All existing protocols for broadcast assume that nodes forward the transit packets. So, there is need for developing new broadcast protocols to overcome node selfishness. In our paper [5], we develop a strategy proof pricing mechanism which we call immediate predecessor node pricing mechanism (IPNPM) and an efficient new broadcast protocol based on IPNPM. We show the efficacy of our proposed broadcast protocol using simulation results.

An efficient pricing based protocol for broadcasting in wireless ad hoc networks

In many applications of wireless ad hoc networks, wireless nodes are owned by rational and intelligent users. In this paper, we call nodes selfish if they are owned by independent users and their only objective is to maximize their individual goals. In such situations, it may not be possible to use the existing protocols for wireless ad hoc networks as these protocols assume that nodes follow the prescribed protocol without deviation. Stimulating cooperation among these nodes is an interesting and challenging problem. Providing incentives and pricing the transactions are well known approaches to stimulate cooperation. In this paper, we present a game theoretic framework for truthful broadcast protocol and strategy proof pricing mechanism called Immediate Predecessor Node Pricing Mechanism (IPNPM). The phrase strategy proof here means that truth revelation of cost is a weakly dominant-strategy (in game theoretic terms) for each node. In order to steer our mechanism-design approach towards practical implementation, we compute the payments to nodes using a distributed algorithm. We also propose a new protocol for broadcast in wireless ad hoc network with selfish nodes based on IPNPM. The features of the proposed broadcast protocol are reliability and a significantly reduced number of packet forwards compared to the number of network nodes, which in turn leads to less system-wide power consumption to broadcast a single packet. Our simulation results show the efficacy of the proposed broadcast protocol.

Second order cone programming approaches for handling missing and uncertain data

We propose a novel second order cone programming formulation for designing robust classifiers which can handle uncertainty in observations. Similar formulations are also derived for designing regression functions which are robust to uncertainties in the regression setting. The proposed formulations are independent of the underlying distribution, requiring only the existence of second order moments. These formulations are then specialized to the case of missing values in observations for both classification and regression problems. Experiments show that the proposed formulations outperform imputation.

New computational approaches for wrinkled and slack membranes

The static response of thin, wrinkled membranes is studied using both a tension field approximation based on plane stress conditions and a 3D nonlinear elasticityformulation, discretized through 8-noded Cosserat point elements. While the tension field approach only obtains the wrinkled/slack regions and at best a measure of the extent of wrinkliness, the 3D elasticity solution provides, in principle, the deformed shape of a wrinkled/slack membrane. However, since membranes barely resist compression, the discretized and linearized system equations via both the approaches are ill-conditioned and solutions could thus be sensitive to discretizations errors as well as other sources of noises/imperfections. We propose a regularized, pseudo-dynamical recursion scheme that provides a sequence of updates, which are almost insensitive to theregularizing term as well as the time step size used for integrating the pseudo-dynamical form. This is borne out through several numerical examples wherein the relative performance of the proposed recursion scheme vis-a-vis a regularized Newton strategy is compared. The pseudo-time marching strategy, when implemented using 3D Cosserat point elements, also provides a computationally cheaper, numerically accurate and simpler alternative to that using geometrically exact shell theories for computing large deformations of membranes in the presence of wrinkles. (C) 2010 Elsevier Ltd. All rights reserved.

Chemical approaches to penicillin allergy—IV. Binding of carrier receptor protein with penicillin and its analogues

The availability of electrophoretically homogeneous rabbit penicillin carrier receptor protein (CRP) by affinity chromatography afforded an idealin vitro system to calculate the thermodynamic parameters of binding of penicillin and analogues with CRP as well as competitive binding of such analogues with CRP in presence of14C-penicillin G. The kinetics of association of CRP with 7-deoxy penicillin which does not bind covalently with CRP have been studied through equilibrium dialysis with14C-7-deoxybenzyl penicillin and found to be K=2·79×106M−1.−ΔG=8·106 k cal/mole as well as fluorescence quenching studies with exciter λ 280 K=3·573×106M−1,−ΔG=8·239 k cal/mole. The fluorescence quenching studies have been extended to CRP-benzyl penicillin and CRP-6-aminopenicillanic acid (6APA) systems also. The fluorescence data with benzyl penicillin indicate two conformational changes in CRP—a fast change corresponding to the non-covalent binding to CRP with 7-deoxy penicillin and a slower change due to covalent bond formation. With 6-APA the first change is not observed but the conformational change corresponding to covalent binding is only seen. Competitive binding studies indicate that the order of binding of CRP with the analogues of penicillin is as follows: methicillin > 6APA > carbenicillin >o-nitrobenzyl penicillin > cloxacillin ≈ benzyl penicillin ≈ 6-phenyl acetamido penicillanyl alcohol ≈ 7 phenyl acetamido desacetoxy cephalosporanic acid ≈p-amino benzyl penicillin ≈p-nitro benzyl penicillin > ticarcillin >o-amino benzyl penicillin > amoxycillin > 7-deoxy benzyl penicillin > ampicillin.From these data it has been possible to delineate partially the topology of the penicillin binding cleft of the CRP as well as some of the functional groups in the cleft responsible for the binding process.

Chemical approaches of penicillin allergy—III Isolation of the penicillin-free carrier receptor protein (CRP) on a polymeric 7-deoxy penicillin analogue template and its role in penicillin immunogeneses in rabbit and man

Specific penicillin-carrier receptor proteins (CRP) have been isolated from the sera of penicillin allergic rabbits and human subjects in the unconjugated native state in electrophoretically homogeneous form by employing a synthetic polymeric affinity template containing the 7-deoxy analogue of penicillin G. The synthesis of the 7-deoxy analogue has been described. In this affinity system the antipenicillin-antibody is desorbed by 0·9M thiourea and the CRP in 8M urea. The CRP after incubation with penicillin is converted into the full-fledged antigen. Studies on the origin of CRP and the nature of antibody as well as comparative studies on the properties of the rabbit antibody and those of antibodies elicited by a BSA-BPO conjugate are reported.

Chemical approaches to penicillin allergy—V. Nature of reaction between rabbit antigen (CRP-penicillin conjugate) and rabbit antipenicillin antibody

The availability of an electrophoretically homogeneous rabbit penicillin carrier receptor protein (CRP) and rabbit antipenicillin antibody afforded an idealin vitro system to calculate the thermodynamic parameters of the binding of14C benzyl penicillin CRP conjugate (antigen) to the purified rabbit antipenicillin antibody. The thermodynamic parameters of this antigen-antibody reaction has been studied by radio-active assay method by using millipore filter. Equilibrium constant (K) of this reaction has been found to be 2·853×109M−2 and corresponding free energy (ΔG) at 4°C and 37°C has been calculated to be −12·02 and −13·5 kcal/mole, enthalpy (ΔH) and entropy (ΔS) has been found to be 361 kcal/mole and +30 eu/mole respectively. Competitive binding studies of CRP-analogue conjugates with the divalent rabbit antibody has been carried out in the presence of14C-penicilloyl CRP. It was found that 7-deoxy penicillin-CRP complex and 6-amino penicilloyl CRP conjugate binds to the antibody with energies stronger than that with the14C-penicilloyl CRP. All the other analogue conjugates are much weaker in interfering with the binding of the penicilloyl CRP with the antibody. The conjugate of methicillin,o-nitro benzyl penicillin and ticarcillin with CRP do not materially interfere in the process.

A Computationally Efficient PWM Algorithm for Multilevel Inverters

Centred space vector PWM (CSVPWM) technique is popularly used for three level voltage source inverters. The reference voltage vector is synthesized by time-averaging of the three nearest voltage vectors produced by the inverter. Identifying the three voltage vectors, and calculation of the dwelling time for each vector are both computationally intensive. This paper analyses the process of PWM generation in CSVPWM. This analysis breaks up a three-level inverter into six different conceptual two level inverters in different regions of the fundamental cycle. Control of 3-level inverter is viewed as the control of the appropriate 2-level inverter. The analysis leads to a systematic simplification of the computations involved, finally resulting in a computationally efficient PWM algorithm. This algorithm exploits the equivalence between triangle comparison and space vector approaches to PWM generation. This algorithm does not involve any 3-phase/2-phase or 2-phase/3-phase transformation. This also does not involve any transformation from rectangular to polar coordinates, and vice versa. Further no evaluation of trigonometric functions is necessary. This algorithm also provides for the mitigation of DC neutral point unbalance, and is well suited to digital implementation. Simulation and experimental results are presented.

Hydrologic drought prediction under climate change: Uncertainty modeling with Dempster-Shafer and Bayesian approaches

Representation and quantification of uncertainty in climate change impact studies are a difficult task. Several sources of uncertainty arise in studies of hydrologic impacts of climate change, such as those due to choice of general circulation models (GCMs), scenarios and downscaling methods. Recently, much work has focused on uncertainty quantification and modeling in regional climate change impacts. In this paper, an uncertainty modeling framework is evaluated, which uses a generalized uncertainty measure to combine GCM, scenario and downscaling uncertainties. The Dempster-Shafer (D-S) evidence theory is used for representing and combining uncertainty from various sources. A significant advantage of the D-S framework over the traditional probabilistic approach is that it allows for the allocation of a probability mass to sets or intervals, and can hence handle both aleatory or stochastic uncertainty, and epistemic or subjective uncertainty. This paper shows how the D-S theory can be used to represent beliefs in some hypotheses such as hydrologic drought or wet conditions, describe uncertainty and ignorance in the system, and give a quantitative measurement of belief and plausibility in results. The D-S approach has been used in this work for information synthesis using various evidence combination rules having different conflict modeling approaches. A case study is presented for hydrologic drought prediction using downscaled streamflow in the Mahanadi River at Hirakud in Orissa, India. Projections of n most likely monsoon streamflow sequences are obtained from a conditional random field (CRF) downscaling model, using an ensemble of three GCMs for three scenarios, which are converted to monsoon standardized streamflow index (SSFI-4) series. This range is used to specify the basic probability assignment (bpa) for a Dempster-Shafer structure, which represents uncertainty associated with each of the SSFI-4 classifications. These uncertainties are then combined across GCMs and scenarios using various evidence combination rules given by the D-S theory. A Bayesian approach is also presented for this case study, which models the uncertainty in projected frequencies of SSFI-4 classifications by deriving a posterior distribution for the frequency of each classification, using an ensemble of GCMs and scenarios. Results from the D-S and Bayesian approaches are compared, and relative merits of each approach are discussed. Both approaches show an increasing probability of extreme, severe and moderate droughts and decreasing probability of normal and wet conditions in Orissa as a result of climate change. (C) 2010 Elsevier Ltd. All rights reserved.

Integrated modelling approaches to analysis of climate change impacts on forests and forest management

This paper reviews integrated economic and ecological models that address impacts and adaptation to climate change in the forest sector. Early economic model studies considered forests as one out of many possible impacts of climate change, while ecological model studies tended to limit the economic impacts to fixed price-assumptions. More recent studies include broader representations of both systems, but there are still few studies which can be regarded fully integrated. Full integration of ecological and economic models is needed to address forest management under climate change appropriately. The conclusion so far is that there are vast uncertainties about how climate change affects forests. This is partly due to the limited knowledge about the global implications of the social and economical adaptation to the effects of climate change on forests.

A non-cooperative game-theoretic approach to channel assignment in multi-channel multi-radio wireless networks

Channel assignment in multi-channel multi-radio wireless networks poses a significant challenge due to scarcity of number of channels available in the wireless spectrum. Further, additional care has to be taken to consider the interference characteristics of the nodes in the network especially when nodes are in different collision domains. This work views the problem of channel assignment in multi-channel multi-radio networks with multiple collision domains as a non-cooperative game where the objective of the players is to maximize their individual utility by minimizing its interference. Necessary and sufficient conditions are derived for the channel assignment to be a Nash Equilibrium (NE) and efficiency of the NE is analyzed by deriving the lower bound of the price of anarchy of this game. A new fairness measure in multiple collision domain context is proposed and necessary and sufficient conditions for NE outcomes to be fair are derived. The equilibrium conditions are then applied to solve the channel assignment problem by proposing three algorithms, based on perfect/imperfect information, which rely on explicit communication between the players for arriving at an NE. A no-regret learning algorithm known as Freund and Schapire Informed algorithm, which has an additional advantage of low overhead in terms of information exchange, is proposed and its convergence to the stabilizing outcomes is studied. New performance metrics are proposed and extensive simulations are done using Matlab to obtain a thorough understanding of the performance of these algorithms on various topologies with respect to these metrics. It was observed that the algorithms proposed were able to achieve good convergence to NE resulting in efficient channel assignment strategies.

Chemical Approaches to the Design of Oxide Materials.

Chemical methods of synthesis play a crucial role in designing and discovering new and novel materials and in providing less cumbersome methods for preparing known materials. Chemical methods also enable the synthesis of metastable materials which are otherwise difficult to prepare. In this presentation, the various innovative chemical methods of synthesising oxide materials will be briefly reviewed with emphasis on soft-chemical routes. Electrochemical synthesis, ion-exchange method, alkali-flux method and some of the interaction reactions will be highlighted, besides topochemical aspects of solid state synthesis. Cuprate superconductors as well as intergrowth structures will also be examined.

Some results and approaches for reconstruction conjectures

Tutte (1979) proved that the disconnected spanning subgraphs of a graph can be reconstructed from its vertex deck. This result is used to prove that if we can reconstruct a set of connected graphs from the shuffled edge deck (SED) then the vertex reconstruction conjecture is true. It is proved that a set of connected graphs can be reconstructed from the SED when all the graphs in the set are claw-free or all are P-4-free. Such a problem is also solved for a large subclass of the class of chordal graphs. This subclass contains maximal outerplanar graphs. Finally, two new conjectures, which imply the edge reconstruction conjecture, are presented. Conjecture 1 demands a construction of a stronger k-edge hypomorphism (to be defined later) from the edge hypomorphism. It is well known that the Nash-Williams' theorem applies to a variety of structures. To prove Conjecture 2, we need to incorporate more graph theoretic information in the Nash-Williams' theorem.

Synthetic approaches to homogynolides A and B

A four step, efficient and general methodology for the conversion of a cyclic ketone into the corresponding alpha-spiro-beta-methylene-gamma-butyrolactone, the key structural feature present in tricyclic sesquiterpenes bakkanes, has been developed employing a regiospecific 5-exo dig radical cyclisation reaction as the key step. The methodology has been extended to the total synthesis of bakkanes including homogynolide-B and chiral homogynolide-A.