|
|
Current and Back Issues can be viewed at the
ACM Digital Portal
Forthcoming (and Selected Back) Issues are listed below with Abstracts
| 21:1 January 2011: Special Issue on Wireless Networks |
Steepest-Ascent Constrained Simultaneous Perturbation for Multi-Objective Optimization
|
Daniel W. MCcLary, Violet R. Syrotiuk, Murat Kulahci
The simultaneous optimization of multiple responses in a dynamic system is challenging. When a
response has a known gradient, it is often easily improved along the path of steepest ascent. On
the contrary, a stochastic approximation technique may be used when the gradient is unknown or
costly to obtain. We consider the problem of optimizing multiple responses in which the gradient is
known for only one response. We propose a hybrid approach for this problem called simultaneous
perturbation stochastic approximation steepest ascent, SPSA-SA or SP(SA)2 for short. SP(SA)2
is an SPSA technique that leverages information about the known gradient to constrain the
perturbations used to approximate the others. We apply SP(SA)2 to the cross-layer optimization
of throughput, packet loss, and end-to-end delay in a mobile ad hoc network (MANET), a self-
organizing wireless network. The results show that SP(SA)2 achieves higher throughput and lower
packet loss and end-to-end delay than the steepest ascent, SPSA, and the Nelder-Mead stochastic
approximation approaches. It also reduces the cost in the number of iterations to perform the
optimization.
|
|
Optimal Scheduling in High Speed Downlink Packet Access Networks
|
Hussein Al-Zubaidy, Ioannis Lambadaris and Jerome Talim
In this paper, we present an analytic model and a methodology to determine the optimal packet
scheduling policy in a High Speed Downlink Packet Access (HSDPA) system. The optimal policy
is the one that maximizes cell throughput while maintaining a level of fairness between the users
in the cell. A discrete stochastic dynamic programming model for the HSDPA downlink scheduler
is presented. Value iteration is then used to solve for optimal scheduling policy. We use a FSMC
(Finite State Markov Channel) to model the HSDPA downlink channel. A near optimal heuristic
scheduling policy is developed. Simulation is used to study the performance of the resulted
heuristic policy and compare it to the computed optimal policy. The results show that the
devised heuristic policy performs very close to the optimal policy. It has much less computational
complexity which makes it easy to deploy and with only slight reduction in performance compared
to the optimal policy.
|
|
Cross Layer Interactions in Multi-hop Wireless Sensor
|
Yang Song, Yuguang Fang
In this paper, we propose a constrained queueing model to investigate the performance of multi-hop
wireless sensor networks. Speci¯cally, the cross layer interactions of rate admission control, tra±c
engineering, dynamic routing and adaptive link scheduling are studied jointly with the proposed
queueing model. In addition, the stochastic network utility maximization problem in wireless
sensor networks is addressed within this framework. We propose an adaptive network resource
allocation scheme, a.k.a., ANRA algorithm, which provides a joint solution to the multiple layer
components of the stochastic network utility maximization problem. We show that the proposed
ANRA algorithm achieves a near-optimal solution, i.e., (1 ¡ ²) of the global optimum network
utility where ² can be arbitrarily small, with a tradeo® with the average delay experienced in the
network. The proposed ANRA algorithm enjoys the merit of self-adaptability through its online
nature and thus is of particular interest for time varying scenarios such as multi-hop wireless
sensor networks.
|
|
Joint Congestion Control and Distributed Scheduling for Throughput Guarantees in Wireless Networks
|
Gaurav Sharma, Ravi R. Mazumdar
We consider the problem of throughput-optimal cross-layer design of wireless networks. We propose
a joint congestion control and scheduling algorithm that achieves a fraction 1=dI (G) of the
capacity region, where dI (G) depends on certain structural properties of the underlying connectivity
graph G of the wireless network, and also on the type of interference constraints. For a wide
range of wireless networks, dI (G) can be upper bounded by a constant, independent of the number
of nodes in the network. The scheduling element of our algorithm is the maximal scheduling
policy. Although this scheduling policy has been considered in several previous works, the challenges
underlying its practical implementation in a fully distributed manner while accounting for
necessary message exchanges have not been addressed in the literature. In this paper, we propose
two algorithms for the distributed implementation of the maximal scheduling policy accounting
for message exchanges, and analytically show that they still can achieve the performance guarantee
under the 1-hop and 2-hop interference models. We also evaluate the performance of our
cross-layer solutions in more realistic network settings with imperfect synchronization under the
signal-to-interference-plus-noise ratio (SINR) interference model, and compare with the standard
layered approaches such as TCP over IEEE 802.11b DCF Networks.
|
|
Steepest-Ascent Constrained Simultaneous Perturbation for Multi-Objective Optimization
|
Dalei Wu
Cross-layer design has become one of the most e®ective and e±cient methods to provide quality
of service (QoS) over various communication networks, especially over wireless multimedia net-
works. However, current research on cross-layer design has been carried out in various piecemeal
approaches, and lacks a methodological foundation to gain in-depth understanding of complex
cross-layer behaviors such as multiscale temporal-spatial behavior, leading to a design paradox
and/or unmanageable design problems. In this paper, we propose a theoretical framework for
quantitative interaction measures, which is further extended to sensitivity analysis by quantifying
the contribution made by each design variable and by the interactions among them on the design
objective. Thus, the proposed framework can signi¯cantly enhance our capability for cross-layer
behavior characterization and provide design insights for future design. Furthermore, a case study
on cross-layer optimized wireless multimedia communications has been adopted to illustrate major
cross-layer design tradeo®s and validate the proposed framework. Both analytical and experimen-
tal results show the correctness and e®ectiveness of the proposed framework.
|
|
Modeling the Interactions Between MAC and Higher Layer
|
Shamim Begum, Ahmed Helmy, Sandeep Gupta
We propose a new framework for worst case performance evaluation of MAC protocols for wireless ad hoc networks.
Given a protocol, its performance metrics and a network topology, our framework first generates MAC scenarios
which achieve poor performance at MAC-level.
In order to evaluate the impact of these MAC scenarios on the end performance, we model the interactions between MAC interface
and the MAC layer using a state transition graph and generate high level scenarios using enumeration techniques.
These high level scenarios can be simulated and compared with heuristics developed by others
to identify high level scenarios that are expected to lead to the worst case end performance.
In order to demonstrate its usefulness, we use our framework to evaluate the worst case performance of IEEE 802.11
DCF protocol by generating a library of MAC and high level scenarios. We simulate the high level scenarios to demonstrate that
the scenarios we generate exhibit the worst performance among all the scenarios,
including those generated by using heuristics recently proposed by other researchers.
|
|
| 20:4 October 2010 |
Random Variate Generation by Numerical Inversion when only the Density Is Known
|
Gerhard Derflinger, Wolfgang Ormann, Josef Leydold
We present a numerical inversion method for generating random variates from continuous distributions
when only the density function is given. The algorithm is based on polynomial interpolation
of the inverse CDF and Gauss-Lobatto integration. The user can select the required precision
which may be close to machine precision for smooth, bounded densities; the necessary tables have
moderate size. Our computational experiments with the classical standard distributions (normal,
beta, gamma, t-distributions) and with the noncentral chi-square, hyperbolic, generalized hyperbolic
and stable distributions showed that our algorithm always reaches the required precision.
The setup time is moderate and the marginal execution time is very fast and nearly the same
for all distributions. Thus for the case that large samples with xed parameters are required
the proposed algorithm is the fastest inversion method known. Speed-up factors up to 1000 are
obtained when compared to inversion algorithms developed for the specic distributions. This
makes our algorithm especially attractive for the simulation of copulas and for quasi-Monte Carlo
applications.
|
|
The Impact of Service Demand Variability on Resource Allocation Strategies in a Grid System
|
Helen Karatza, Stelios Zikos
Scheduling and resource management play an important role in building complex distributed systems, such as
grids. In this paper we study the impact on performance of job service demand variability in a two-level grid
architecture, given that the grid and local schedulers are unaware of each job’s service demand. We examine
two scheduling policies at grid level, which utilize site load information and three policies at local level. A
simulation model is used to evaluate performance. Results show that service demand variability degrades
performance, and thus a suitable local resource allocation policy is needed to reduce its impact.
|
|
Crowd Modeling and Simulation Technologies
|
Suiping Zhou, Dan Chen, Wentong Cai, Linbo Luo, Malcolm Low, Feng Tian, Victor Tay, Darren Ong, Benjamin Hamilton
As a collective and highly dynamic social group, human crowd is a fascinating phenomenon which
has been constantly concerned by experts from various areas. Recently, computer-based modeling
and simulation technologies have emerged to support investigation of the dynamics of crowds,
such as a crowd's behaviors under normal and emergent situations. This paper assesses the major
existing technologies for crowd modeling and simulation. We ¯rst propose a two-dimensional
categorization mechanism to classify existing work depending on the size of crowds and the time-
scale of the crowd phenomena of interest. Four evaluation criteria have also been introduced
to evaluate existing crowd simulation systems from the point of view of both a modeler and an
end-user.
We have discussed some in°uential existing work in crowd modeling and simulation regarding
their major features, performance as well as the technologies used in these work. We have also
discussed some open problems in the area. This paper will provide the researchers with use-
ful information and insights on the state-of-the-art of the technologies in crowd modeling and
simulation as well as future research directions.
|
|
Generalized Lindley-Type Recursive Representations for Multi-Server Tandem Queues with Blocking
|
Victor Chan
Lindley’s recursion is an explicit recursive equation that describes the recursive relationship between
consecutive waiting times in a single-stage single-server queue. In this paper, we develop explicit recursive
representations for multi-server tandem queues with blocking. We demonstrate the application of these
recursive representations with simulations of large-scale tandem queueing networks. We compare the
computational efficiency of these representations with two other popular discrete-event simulation approaches,
namely, event scheduling and process interaction. Experimental results show that these representations are
seven (or more) times faster than their counterparts based on the event-scheduling and process-interaction
approaches.
|
|
A Mixed Reality Approach for Interactively Blending Dynamic Models with Corresponding...
|
John Quarles, Paul Fishwick, Samsun Lampotang, Ira Fischler, Benjamin Lok
The design, visualization, manipulation, and implementation of models for computer simulation are key parts of
the discipline. Models are constructed as a means to understand physical phenomena as state changes occur
over time. One issue that arises is the need to correlate models and their components with the phenomena being
modeled. For example, a part of an automotive engine needs to be placed into cognitive context with the
diagrammatic icon that represents that part's function. A typical solution to this problem is to display a dynamic
model of the engine in one window and the engine's CAD model in another. Users are expected to, on their
own, mentally blend the dynamic model and the physical phenomenon into the same context. However, this
contextualization is not trivial in many applications.
Our approach expands upon this form of user interaction by specifying two ways in which dynamic models
and the corresponding physical phenomena may be viewed, and experimented with, within the same human
interaction space. We present a methodology and implementation of contextualization for diagram-based
dynamic models using an anesthesia machine, and then follow up with a human study of its effects on spatial
cognition.
|
|
An Integrated Human Decision Making Model for Evacuation Scenarios under a BDI Framework
|
Seungho Lee, Young-Jun Son, Judy Jin
An integrated Belief-Desire-Intention (BDI) modeling framework is proposed for human decision making and
planning for evacuation scenarios, whose submodules are based on a Bayesian belief network (BBN), Decision-
Field-Theory (DFT), and a probabilistic depth first search (PDFS) technique. A key novelty of the proposed
model is its ability to represent both the human decision-making and decision-planning functions in a unified
framework. To mimic realistic human behaviors, attributes of the BDI framework are reverse-engineered from
human-in-the-loop experiments conducted in the Cave Automatic Virtual Environment (CAVE). The proposed
modeling framework is demonstrated for a human’s evacuation behaviors in response to a terrorist bomb attack.
The simulated environment and agents (models of humans) conforming to the proposed BDI framework are
implemented in AnyLogic® agent-based simulation software, where each agent calls external Netica BBN
software to perform its perceptual processing function and Soar software to perform its real-time planning and
decision-execution functions. The constructed simulation has been used to test the impact of several factors (e.g.,
demographics, number of police officers, information sharing via speakers) on evacuation performance (e.g.,
average evacuation time, percentage of casualities).
|
|
| 20:3 July 2010 |
A Stochastic Approximation Method with Max-Norm Projections and its Applications to the Q-Learning Algorithm
|
Sumit Kunnumkal, Huseyin Topaloglu
2008-0015
|
|
Finding Feasible Systems in the Presence of Constraints on Multiple Performance Measures
|
Demet Batur, Seong-Hee, Kim
2007-0008
|
|
A Survey of Customization Support in Agent-Based Business Process Simulation Tools
|
William Robinson and Yi Ding
2006-0042
|
|
State-dependent Importance Sampling for a Jackson Tandem Network
|
Denis Miretskiy, Werner Scheinhardt, Michel Mandjes
2008-0022
|
|
Probabilistic Analysis of Simulation-Based Games
|
Yevgeniy Vorobeychik
008-0040
|
|
Profile-Driven Regression for Modelling and Run-Time Optimization of Mobile Networks
|
Daniel W. McClary, Violet R. Syrotiuk, Murat Ku¨ Lahc
2008-0048
|
|
| 20:1 January 2010: Special Issue on |
Editor's Introduction
|
Steve Chick and Enver Yucesan
Introduction here
|
|
|
Simulation Modeling for Analysis
|
Industrial Strength COMPASS: A Comprehensive Algorithm and Software for Optimization via Simulation
|
Jie Xu, Barry L. Nelson, L. Jeff Hong
2007-0038
|
|
Asymptotic Robustness of Estimators in Rare-Event Simulation
|
Pierre L'Ecuyer, Glynn, Peter; Tuffin, Bruno; Blanchet, Jose
2007-0043
|
|
Gradient Estimation for Discrete Event Systems by Measure-Valued Differentiation
|
Bernd Heidergott
2007-0052
|
|
Simulation Optimization Using the Cross-Entropy Method with Optimal Computing Budget Allocation
|
Donghai He, Loo Hay Lee, Chun-Hung Chen, Michael Fu, Segev Wasserkrug
2007-0054
|
|
Previous Special Issues:
|
|
|