Stochastic optimization for adaptive labor staffing in service systems

Service systems are labor intensive. Further, the workload tends to vary greatly with time. Adapting the staffing levels to the workloads in such systems is nontrivial due to a large number of parameters and operational variations, but crucial for business objectives such as minimal labor inventory. One of the central challenges is to optimize the staffing while maintaining system steady-state and compliance to aggregate SLA constraints. We formulate this problem as a parametrized constrained Markov process and propose a novel stochastic optimization algorithm for solving it. Our algorithm is a multi-timescale stochastic approximation scheme that incorporates a SPSA based algorithm for ‘primal descent' and couples it with a ‘dual ascent' scheme for the Lagrange multipliers. We validate this optimization scheme on five real-life service systems and compare it with a state-of-the-art optimization tool-kit OptQuest. Being two orders of magnitude faster than OptQuest, our scheme is particularly suitable for adaptive labor staffing. Also, we observe that it guarantees convergence and finds better solutions than OptQuest in many cases.

Low complexity adaptation for channel shortening equalizers

Since the days of Digital Subscriber Links(DSL), Time Domain Equalizers(TEQ's) have been used to combat time dispersive channels in Multicarrier Systems. In this paper, we propose computationally inexpensive techniques to recompute TEQ weights in the presence of changes in the channel, especially over fast fading channels. The techniques use no extra information except the perturbation itself, and provide excellent approximations to the new TEQ weights. The proposed adaptation techniques are shown to perform admirably well for small changes in channels for OFDM systems.

An adaptation framework for head-pose classification in dynamic multi-view scenarios

Multi-view head-pose estimation in low-resolution, dynamic scenes is difficult due to blurred facial appearance and perspective changes as targets move around freely in the environment. Under these conditions, acquiring sufficient training examples to learn the dynamic relationship between position, face appearance and head-pose can be very expensive. Instead, a transfer learning approach is proposed in this work. Upon learning a weighted-distance function from many examples where the target position is fixed, we adapt these weights to the scenario where target positions are varying. The adaptation framework incorporates reliability of the different face regions for pose estimation under positional variation, by transforming the target appearance to a canonical appearance corresponding to a reference scene location. Experimental results confirm effectiveness of the proposed approach, which outperforms state-of-the-art by 9.5% under relevant conditions. To aid further research on this topic, we also make DPOSE- a dynamic, multi-view head-pose dataset with ground-truth publicly available with this paper.

Joint evaluation of channel feedback schemes, rate adaptation, and scheduling in OFDMA downlinks with feedback delays

Orthogonal frequency-division multiple access (OFDMA) systems divide the available bandwidth into orthogonal subchannels and exploit multiuser diversity and frequency selectivity to achieve high spectral efficiencies. However, they require a significant amount of channel state feedback for scheduling and rate adaptation and are sensitive to feedback delays. We develop a comprehensive analysis for OFDMA system throughput in the presence of feedback delays as a function of the feedback scheme, frequency-domain scheduler, and rate adaptation rule. Also derived are expressions for the outage probability, which captures the inability of a subchannel to successfully carry data due to the feedback scheme or feedback delays. Our model encompasses the popular best-n and threshold-based feedback schemes and the greedy, proportional fair, and round-robin schedulers that cover a wide range of throughput versus fairness tradeoff. It helps quantify the different robustness of the schedulers to feedback overhead and delays. Even at low vehicular speeds, it shows that small feedback delays markedly degrade the throughput and increase the outage probability. Further, given the feedback delay, the throughput degradation depends primarily on the feedback overhead and not on the feedback scheme itself. We also show how to optimize the rate adaptation thresholds as a function of feedback delay.

Tradeoff of average service cost and average delay for the state dependent M/M/1 queue

The optimal tradeoff between average service cost rate and average delay, is addressed for a M/M/1 queueing model with queue-length dependent service rates, chosen from a finite set. We provide an asymptotic characterization of the minimum average delay, when the average service cost rate is a small positive quantity V more than the minimum average service cost rate required for stability. We show that depending on the value of the arrival rate, the assumed service cost rate function, and the possible values of the service rates, the minimum average delay either a) increases only to a finite value, b) increases without bound as log(1/V), or c) increases without bound as 1/V, when V down arrow 0. We apply the analysis to a flow-level resource allocation model for a wireless downlink. We also investigate the asymptotic tradeoff for a sequence of policies which are obtained from an approximate fluid model for the M/M/1 queue.

SeaMo plus : a virtual real-time multimedia service framework on handhelds to enable remote real-time patient monitoring for mobile doctors

The key requirements for enabling real-time remote healthcare service on a mobile platform, in the present day heterogeneous wireless access network environment, are uninterrupted and continuous access to the online patient vital medical data, monitor the physical condition of the patient through video streaming, and so on. For an application, this continuity has to be sufficiently transparent both from a performance perspective as well as a Quality of Experience (QoE) perspective. While mobility protocols (MIPv6, HIP, SCTP, DSMIP, PMIP, and SIP) strive to provide both and do so, limited or non-availability (deployment) of these protocols on provider networks and server side infrastructure has impeded adoption of mobility on end user platforms. Add to this, the cumbersome OS configuration procedures required to enable mobility protocol support on end user devices and the user's enthusiasm to add this support is lost. Considering the lack of proper mobility implementations that meet the remote healthcare requirements above, we propose SeaMo+ that comprises a light-weight application layer framework, termed as the Virtual Real-time Multimedia Service (VRMS) for mobile devices to provide an uninterrupted real-time multimedia information access to the mobile user. VRMS is easy to configure, platform independent, and does not require additional network infrastructure unlike other existing schemes. We illustrate the working of SeaMo+ in two realistic remote patient monitoring application scenarios.

Interplay Between Optimal Selection Scheme, Selection Criterion, and Discrete Rate Adaptation in Opportunistic Wireless Systems

An opportunistic, rate-adaptive system exploits multi-user diversity by selecting the best node, which has the highest channel power gain, and adapting the data rate to selected node's channel gain. Since channel knowledge is local to a node, we propose using a distributed, low-feedback timer backoff scheme to select the best node. It uses a mapping that maps the channel gain, or, in general, a real-valued metric, to a timer value. The mapping is such that timers of nodes with higher metrics expire earlier. Our goal is to maximize the system throughput when rate adaptation is discrete, as is the case in practice. To improve throughput, we use a pragmatic selection policy, in which even a node other than the best node can be selected. We derive several novel, insightful results about the optimal mapping and develop an algorithm to compute it. These results bring out the inter-relationship between the discrete rate adaptation rule, optimal mapping, and selection policy. We also extensively benchmark the performance of the optimal mapping with several timer and opportunistic multiple access schemes considered in the literature, and demonstrate that the developed scheme is effective in many regimes of interest.

e-SURAKSHAK: A Cyber-Physical Healthcare System with Service Oriented Architecture

In this paper we present the design of ``e-SURAKSHAK,'' a novel cyber-physical health care management system of Wireless Embedded Internet Devices (WEIDs) that sense vital health parameters. The system is capable of sensing body temperature, heart rate, oxygen saturation level and also allows noninvasive blood pressure (NIBP) measurement. End to end internet connectivity is provided by using 6LoWPAN based wireless network that uses the 802.15.4 radio. A service oriented architecture (SOA) 1] is implemented to extract meaningful information and present it in an easy-to-understand form to the end-user instead of raw data made available by sensors. A central electronic database and health care management software are developed. Vital health parameters are measured and stored periodically in the database. Further, support for real-time measurement of health parameters is provided through a web based GUI. The system has been implemented completely and demonstrated with multiple users and multiple WEIDs.

Joint Evaluation of Reduced Feedback Scheme, Scheduling, and Rate Adaptation in OFDMA Systems with Feedback Delays

Orthogonal frequency division multiple access (OFDMA) systems exploit multiuser diversity and frequency-selectivity to achieve high spectral efficiencies. However, they require considerable feedback for scheduling and rate adaptation, and are sensitive to feedback delays. We develop a comprehensive analysis of the OFDMA system throughput as a function of the feedback scheme, frequency-domain scheduler, and discrete rate adaptation rule in the presence of feedback delays. We analyze the popular best-n and threshold-based feedback schemes. We show that for both the greedy and round-robin schedulers, the throughput degradation, given a feedback delay, depends primarily on the fraction of feedback reduced by the feedback scheme and not the feedback scheme itself. Even small feedback delays at low vehicular speeds are shown to significantly degrade the throughput. We also show that optimizing the link adaptation thresholds as a function of the feedback delay can effectively counteract the detrimental effect of delays.

Optimal Joint Antenna Selection and Power Adaptation in Underlay Cognitive Radios

Transmit antenna selection (AS) is a popular, low hardware complexity technique that improves the performance of an underlay cognitive radio system, in which a secondary transmitter can transmit when the primary is on but under tight constraints on the interference it causes to the primary. The underlay interference constraint fundamentally changes the criterion used to select the antenna because the channel gains to the secondary and primary receivers must be both taken into account. We develop a novel and optimal joint AS and transmit power adaptation policy that minimizes a Chernoff upper bound on the symbol error probability (SEP) at the secondary receiver subject to an average transmit power constraint and an average primary interference constraint. Explicit expressions for the optimal antenna and power are provided in terms of the channel gains to the primary and secondary receivers. The SEP of the optimal policy is at least an order of magnitude lower than that achieved by several ad hoc selection rules proposed in the literature and even the optimal antenna selection rule for the case where the transmit power is either zero or a fixed value.

Subchannel allocation and power control in femtocells to provide quality of service

Femtocells are a new concept which improves the coverage and capacity of a cellular system. We consider the problem of channel allocation and power control to different users within a Femtocell. Knowing the channels available, the channel states and the rate requirements of different users the Femtocell base station (FBS), allocates the channels to different users to satisfy their requirements. Also, the Femtocell should use minimal power so as to cause least interference to its neighboring Femtocells and outside users. We develop efficient, low complexity algorithms which can be used online by the Femtocell. The users may want to transmit data or voice. We compare our algorithms with the optimal solutions.

A context aware collaborative service provisioning system for mobile-commerce

In the process of service provisioning, providing required service to the user without user intervention, with reduction of the cognitive over loading is a real challenge. In this paper we propose a user centred context aware collaborative service provisioning system, which make use of context along with collaboration to provide the required service to the user dynamically. The system uses a novel approach of query expansion along with interactive and rating matrix based collaboration. Performance of the system is evaluated in Mobile-Commerce environment. The results show that the system is time efficient and perform with better precision and recall in comparison with context aware system.

Delay optimal scheduling of a discrete-time batch service queue for point-to-point channel code rate selection

We consider the problem of characterizing the minimum average delay, or equivalently the minimum average queue length, of message symbols randomly arriving to the transmitter queue of a point-to-point link which dynamically selects a (n, k) block code from a given collection. The system is modeled by a discrete time queue with an IID batch arrival process and batch service. We obtain a lower bound on the minimum average queue length, which is the optimal value for a linear program, using only the mean (λ) and variance (σ2) of the batch arrivals. For a finite collection of (n, k) codes the minimum achievable average queue length is shown to be Θ(1/ε) as ε ↓ 0 where ε is the difference between the maximum code rate and λ. We obtain a sufficient condition for code rate selection policies to achieve this optimal growth rate. A simple family of policies that use only one block code each as well as two other heuristic policies are shown to be weakly optimal in the sense of achieving the 1/ε growth rate. An appropriate selection from the family of policies that use only one block code each is also shown to achieve the optimal coefficient σ2/2 of the 1/ε growth rate. We compare the performance of the heuristic policies with the minimum achievable average queue length and the lower bound numerically. For a countable collection of (n, k) codes, the optimal average queue length is shown to be Ω(1/ε). We illustrate the selectivity among policies of the growth rate optimality criterion for both finite and countable collections of (n, k) block codes.

EESM-Based Link Adaptation in Point-to-Point and Multi-Cell OFDM Systems: Modeling and Analysis

In contemporary wideband orthogonal frequency division multiplexing (OFDM) systems, such as Long Term Evolution (LTE) and WiMAX, different subcarriers over which a codeword is transmitted may experience different signal-to-noise-ratios (SNRs). Thus, adaptive modulation and coding (AMC) in these systems is driven by a vector of subcarrier SNRs experienced by the codeword, and is more involved. Exponential effective SNR mapping (EESM) simplifies the problem by mapping this vector into a single equivalent fiat-fading SNR. Analysis of AMC using EESM is challenging owing to its non-linear nature and its dependence on the modulation and coding scheme. We first propose a novel statistical model for the EESM, which is based on the Beta distribution. It is motivated by the central limit approximation for random variables with a finite support. It is simpler and as accurate as the more involved ad hoc models proposed earlier. Using it, we develop novel expressions for the throughput of a point-to-point OFDM link with multi-antenna diversity that uses EESM for AMC. We then analyze a general, multi-cell OFDM deployment with co-channel interference for various frequency-domain schedulers. Extensive results based on LTE and WiMAX are presented to verify the model and analysis, and gain new insights.