An efficient algorithm for scheduling in bluetooth piconets and scatternets

Bluetooth is a short-range radio technology operating in the unlicensed industrial-scientific-medical (ISM) band at 2.45 GHz. A piconet is basically a collection of slaves controlled by a master. A scatternet, on the other hand, is established by linking several piconets together in an ad hoc fashion to yield a global wireless ad hoc network. This paper proposes a scheduling policy that aims to achieve increased system throughput and reduced packet delays while providing reasonably good fairness among all traffic flows in bluetooth piconets and scatternets. We propose a novel algorithm for scheduling slots to slaves for both piconets and scatternets using multi-layered parameterized policies. Our scheduling scheme works with real data and obtains an optimal feedback policy within prescribed parameterized classes of these by using an efficient two-timescale simultaneous perturbation stochastic approximation (SPSA) algorithm. We show the convergence of our algorithm to an optimal multi-layered policy. We also propose novel polling schemes for intra- and inter-piconet scheduling that are seen to perform well. We present an extensive set of simulation results and performance comparisons with existing scheduling algorithms. Our results indicate that our proposed scheduling algorithm performs better overall on a wide range of experiments over the existing algorithms for both piconets (Das et al. in INFOCOM, pp. 591–600, 2001; Lapeyrie and Turletti in INFOCOM conference proceedings, San Francisco, US, 2003; Shreedhar and Varghese in SIGCOMM, pp. 231–242, 1995) and scatternets (Har-Shai et al. in OPNETWORK, 2002; Saha and Matsumot in AICT/ICIW, 2006; Tan and Guttag in The 27th annual IEEE conference on local computer networks(LCN). Tampa, 2002). Our studies also confirm that our proposed scheme achieves a high throughput and low packet delays with reasonable fairness among all the connections.

Online association policies in IEEE 802.11 WLANs

In this paper, we study the performance of client-Access Point (AP) association policies in IEEE 802.11 based WLANs. In many scenarios, clients have a choice of APs with whom they can associate. We are interested in finding association policies which lead to optimal system performance. More specifically, we study the stability of different association policies as a function of the spatial distribution of arriving clients. We find for each policy the range of client arrival rates for which the system is stable. For small networks, we use Lyapunov function methods to formally establish the stability or instability of certain policies in specific scenarios. The RAT heuristic policy introduced in our prior work is shown to have very good stability properties when compared to several other natural policies. We also validate our analytical results by detailed simulation employing the IEEE 802.11 MAC.

Online client-AP association in WLANs

In many IEEE 802.11 WLAN deployments, wireless clients have a choice of access points (AP) to connect to. In current systems, clients associate with the access point with the strongest signal to noise ratio. However, such an association mechanism can lead to unequal load sharing, resulting in diminished system performance. In this paper, we first provide a numerical approach based on stochastic dynamic programming to find the optimal client-AP association algorithm for a small topology consisting of two access points. Using the value iteration algorithm, we determine the optimal association rule for the two-AP topology. Next, utilizing the insights obtained from the optimal association ride for the two-AP case, we propose a near-optimal heuristic that we call RAT. We test the efficacy of RAT by considering more realistic arrival patterns and a larger topology. Our results show that RAT performs very well in these scenarios as well. Moreover, RAT lends itself to a fairly simple implementation.

An Efficient and Optimized Bluetooth Scheduling Algorithm for Scatternets

Bluetooth is a short-range radio technology operating in the unlicensed industrial-scientific-medical (ISM) band at 2.45 GHz. A scatternet is established by linking several piconets together in ad hoc fashion to yield a global wireless ad hoc network. This paper proposes a polling policy that aims to achieve increased system throughput and reduced packet delays while providing reasonably good fairness among all traffic flows in a Bluetooth Scatternet. Experimental results from our proposed algorithm show performance improvements over a well known existing algorithm.

Optimal capacity relay node placement in a multi-hop network on a line

We use information theoretic achievable rate formulas for the multi-relay channel to study the problem of optimal placement of relay nodes along the straight line joining a source node and a destination node. The achievable rate formulas that we utilize are for full-duplex radios at the relays and decode-and-forward relaying. For the single relay case, and individual power constraints at the source node and the relay node, we provide explicit formulas for the optimal relay location and the optimal power allocation to the source-relay channel, for the exponential and the power-law path-loss channel models. For the multiple relay case, we consider exponential path-loss and a total power constraint over the source and the relays, and derive an optimization problem, the solution of which provides the optimal relay locations. Numerical results suggest that at low attenuation the relays are mostly clustered close to the source in order to be able to cooperate among themselves, whereas at high attenuation they are uniformly placed and work as repeaters. We also prove that a constant rate independent of the attenuation in the network can be achieved by placing a large enough number of relay nodes uniformly between the source and the destination, under the exponential path-loss model with total power constraint.

Measurement Based Impromptu Deployment of a Multi-Hop Wireless Relay Network

We study the problem of optimal sequential (''as-you-go'') deployment of wireless relay nodes, as a person walks along a line of random length (with a known distribution). The objective is to create an impromptu multihop wireless network for connecting a packet source to be placed at the end of the line with a sink node located at the starting point, to operate in the light traffic regime. In walking from the sink towards the source, at every step, measurements yield the transmit powers required to establish links to one or more previously placed nodes. Based on these measurements, at every step, a decision is made to place a relay node, the overall system objective being to minimize a linear combination of the expected sum power (or the expected maximum power) required to deliver a packet from the source to the sink node and the expected number of relay nodes deployed. For each of these two objectives, two different relay selection strategies are considered: (i) each relay communicates with the sink via its immediate previous relay, (ii) the communication path can skip some of the deployed relays. With appropriate modeling assumptions, we formulate each of these problems as a Markov decision process (MDP). We provide the optimal policy structures for all these cases, and provide illustrations of the policies and their performance, via numerical results, for some typical parameters.

Fatigue Laws Via Functional Equations

In routine industrial design, fatigue life estimation is largely based on S-N curves and ad hoc cycle counting algorithms used with Miner's rule for predicting life under complex loading. However, there are well known deficiencies of the conventional approach. Of the many cumulative damage rules that have been proposed, Manson's Double Linear Damage Rule (DLDR) has been the most successful. Here we follow up, through comparisons with experimental data from many sources, on a new approach to empirical fatigue life estimation (A Constructive Empirical Theory for Metal Fatigue Under Block Cyclic Loading', Proceedings of the Royal Society A, in press). The basic modeling approach is first described: it depends on enforcing mathematical consistency between predictions of simple empirical models that include indeterminate functional forms, and published fatigue data from handbooks. This consistency is enforced through setting up and (with luck) solving a functional equation with three independent variables and six unknown functions. The model, after eliminating or identifying various parameters, retains three fitted parameters; for the experimental data available, one of these may be set to zero. On comparison against data from several different sources, with two fitted parameters, we find that our model works about as well as the DLDR and much better than Miner's rule. We finally discuss some ways in which the model might be used, beyond the scope of the DLDR.

Adsopption isotherms-A critique

The possibility or the impossibility of separating the particle and the electrode interactions is discussed in a wider context of the effects due to any two interaction potentials on the equation of state. The involved nature of the pressure dependence on two individually definable forces is illustrated through the Percus Yevick results for the adhesive hard spheres. An alternative form of the adsorption isotherm is given to bring home the intimate relationship between the actual equation of state and the free energy of adsorption. Thermodynamic consequences of congruence with respect to E (or q) as reflected through the linear plots of q (or E) vs. θ are well known. Mathematical consequences of simultaneous congruence have been pointed out recently. In this paper, the physical nature of congruence hypothesis is revealed. In passing "the pseudo-congruence" is also discussed. It is emphasised that the problem is no less ambiguous with regard to modelling the particle/particle interaction. The ad hoc nature of our dependence of the available equations of state is emphasised through a discussion on the HFL theory. Finally, a heuristic method for modelling ΔG mathematically-incorporating its behaviour at saturation coverages-is advanced. The more interesting aspects of this approach, which generalises almost all isotherms hitherto known, are sketched.

Average-Delay Optimal Policies for the Point-to-Point Channel

Average-delay optimal scheduflng of messages arriving to the transmitter of a point-to-point channel is considered in this paper. We consider a discrete time batch-arrival batch-service queueing model for the communication scheme, with service time that may be a function of batch size. The question of delay optimality is addressed within the semi-Markov decision-theoretic framework. Approximations to the average-delay optimal policy are obtained.

Hot gaseous coronae of early-type galaxies and their radio luminosity function

Recent X-ray observations have revealed that early-type galaxies (which usually produce extended double radio sources) generally have hot gaseous haloes extending up to approx102kpc1,2. Moreover, much of the cosmic X-ray background radiation is probably due to a hotter, but extremely tenuous, intergalactic medium (IGM)3. We have presented4–7 an analytical model for the propagation of relativistic beams from galactic nuclei, in which the beams' crossing of the pressure-matched interface between the IGM and the gaseous halo, plays an important role. The hotspots at the ends of the beams fade quickly when their advance becomes subsonic with respect to the IGM. This model has successfully predicted (for typical double radio sources) the observed8 current mean linear-size (approx2Dsime350 kpc)4,5, the observed8–11 decrease in linear-size with cosmological redshift4–6 and the slope of the linear-size versus radio luminosity10,12–14 relation6. We have also been able to predict the redshift-dependence of observed numbers and radio luminosities of giant radio galaxies7,15. Here, we extend this model to include the propagation of somewhat weaker beams. We show that the observed flattening of the local radio luminosity function (LRLF)16–20 for radio luminosity Papproximately 1024 W Hz-1 at 1 GHz can be explained without invoking ad hoc a corresponding break in the beam power function Phi(Lb), because the heads of the beams with Lb < 1025 W Hz-1 are decelerated to sonic velocity within the halo itself, which leads to a rapid decay of radio luminosity and a reduced contribution of these intrinsically weaker sources to the observed LRLF.

Can equipartition fields produce the tilts of bipolar magnetic regions?

The effect of turbulence on the nonaxisymmetric flux rings of equipartition field strength in bipolar magnetic regions is studied on the basis of the small-scale momentum exchange mechanism and the giant cell drag combined with the Kelvin-Helmholtz drag mechanism. It is shown that the giant cell drag and small-scale momentum exchange mechanism can make equipartition flux loops emerge at low latitudes, in addition to making them exhibit the observed tilts. However, the sizes of the flux tubes have to be restricted to a couple of hundred kilometers. An ad hoc constraint on the footpoints of the flux loops is introduced by not letting them move in the phi direction, and it is found that equipartition fields of any size can be made to emerge at sunspot latitudes with the observed tilts by suitably adjusting the footpoint separations.

On optimal timer-based distributed selection for rate-adaptive multi-user diversity systems

We develop an optimal, distributed, and low feedback timer-based selection scheme to enable next generation rate-adaptive wireless systems to exploit multi-user diversity. In our scheme, each user sets a timer depending on its signal to noise ratio (SNR) and transmits a small packet to identify itself when its timer expires. When the SNR-to-timer mapping is monotone non-decreasing, timers of users with better SNRs expire earlier. Thus, the base station (BS) simply selects the first user whose timer expiry it can detect, and transmits data to it at as high a rate as reliably possible. However, timers that expire too close to one another cannot be detected by the BS due to collisions. We characterize in detail the structure of the SNR-to-timer mapping that optimally handles these collisions to maximize the average data rate. We prove that the optimal timer values take only a discrete set of values, and that the rate adaptation policy strongly influences the optimal scheme's structure. The optimal average rate is very close to that of ideal selection in which the BS always selects highest rate user, and is much higher than that of the popular, but ad hoc, timer schemes considered in the literature.

Assessment of treatment capabilities of Varthur Lake, Bangalore, India

Manmade waterbodies have traditionally been used for domestic and irrigation purposes. Unplanned urbanization and ad-hoc approaches have led to these waterbodies receiving untreated sewage. This enriches and eutrophies the waterbody. A physicochemical and biological analysis of sewage-fed Varthur Lake in Bangalore was carried out and its treatment capabilities in terms of BOD removal, nutrient assimilation and self-remediation were assessed. Anaerobic conditions (0 mg/L) prevail at the inlet which improves towards the outlets due to algal aeration. This removed > 50% BOD in the monsoon season but was inhibited by floating macrophytes in all other seasons. Alkalinity, TDS, conductivity and hardness values were higher when compared to earlier studies. This study shows the lake behaves as an anaerobic~aerobic lagoon with a residence time of 4.8 d treating the wastewater to a considerable extent. Further research is required to optimise the system performance.