MITACS/LRSP Workshop on Networks

Saturday October 22, 2005

Place: 4351HP, School of Mathematics and Statistics, Carleton University

Schedule

09:00         Coffee

09:30-10:30   Oliver Yang, SITE, Faculty of Engineering, University of Ottawa
10:30-11:30   Keivan Navaie, System and Computer Engineering, Carleton University
11:30-12:30   Delfin Montuno, Nortel Networks

12:30- 1:30   Lunch (will be provided)

1:30 - 2:15   Johan van Leeuwaarden, Eurandom, Eindhoven
2:15 - 3:00   Yonghua Mao, Mathematics, Beijing Normal University

3:00 - 3:30   Coffee

3:30 - 4:15   Bin Liu, Applied Mathematics, Chinese Academy of Sciences
4:15 - 5:00   Gaing Li, Mathematics and Statistics, Carleton University

Speaker: Oliver Yang
Title: Energy Efficient Broadcast and Multicast Algorithms in Wireless Ad-hoc Networks

Abstract: We systematically explore two fundamental classes of energy-efficient broadcast/multicast problems: the Power Minimization problem and the Lifetime Maximization problem. We present a general analytical MILP (Mixed Integer Linear Programming) model for small networks, and a group of polynomial-time algorithms to practically handle significantly large networks for which the MILP model may not be computationally efficient. These have been validated by performance evaluation in different scenarios involving fixed/adaptive antenna, both omni-directional and directional.

Speaker: Keivan Navaie
Title: Multi-user Diversity in Multi-hop Cellular Networks

Abstract: Abstract: In this presentation we study multi-user diversity in single-hop and multi-hop cellular networks. An upper-bound is derived for the average achieved throughput per-user based on the network fundamental limitations. To overcome these limitations a base-station coordinated relaying method is presented. In the proposed relaying scheme, multi-user diversity is induced and then exploited in a 2-hop forwarding scheme to improve per-user achieved throughput. An actual protocol for implementing this method is designed and performance evaluation results are presented.

Speaker: Delfin Montuno
Title: Challenges and Applications of Sensor Networks

Abstract: This talk will survey sensor networks from the technology point of view such as networking, security, power constraints, and data management, and from the applications point of view such as monitoring, tracking, and management of such networks. It will attempt to formulate some of challenges so that they may be addressed from a mathematical point of view.

Speaker: Johan van Leeuwaarden
Title: Tail asymptotics for a tandem queue with coupled processors: a comparison between methods

Abstract: We consider the two-stage tandem queue with coupled processors. It is assumed that jobs arrive at the first station according to a Poisson process and require service at both stations before leaving the system. The amount of work that a job requires at each of the stations is an independent, exponentially distributed random variable. When both stations are nonempty, the total service capacity is shared among the stations according to fixed proportions. When one of the stations becomes empty, the total service capacity is given to the nonempty station. We derive asymptotic expressions for the stationary queue length distribution. The biggest challenge in obtaining these expressions is the analytic continuation of P(x; y) defined as the joint pgf of the stationary queue length at both stations. We manage to obtain the analytic continuation by exploiting the specific properties of a functional equation that implicitly defines P(x; y). The analytic continuation of P(x; y) results in knowledge on the dominant singularity of P(x; y). By investigating the behavior of P(x; y) in the vicinity of the dominant singularity, we are able to derive asymptotic expressions. There are some competing methods for deriving asymptotic expressions. We discuss these methods and point out the similarities and differences with our analytic approach.

Speaker: Yonghua Mao
Title: Eigentime Identities for Markov Chains

Abstract: The eigentime identities are proved for continuous-time reversible or transient symmetrizable Markov chains with Markov generator L. This enable us to give a relationship between spectra of L in L^2 and in L^\infty. Explicit formulas are presented in case of birth-death processes.

Speaker: Bin Liu
Title: Waiting Time Tail Probabilities in a Two-Queue Served by a Single Server Alternately

Abstract: We deal with a queueing system with two types of customers arriving at two different queues and a single server serving two queues alternately. Once the server is serving one queue, he keeps serving this queue until it becomes empty, then he switches to serve the other queue if it is not empty. We are interested in the tail behavior of the waiting time distribution when the service time distributions have a heavy tail. Towards it, we first show that the waiting time for each type of customers has some specific form of stochastic decomposition. Based on this result, we obtain the asymptotic expressions of the stationary waiting time distributions.

Speaker: Gang Li
Title: Variance Reduction and Long-Range Dependence Preservation by Leaky Bucket

Abstract: Consider a leaky bucket L(mu,b) with stationary input process A and stationary output process D. We show that D is less variable than A in both time domain and count domain and the property of long range dependence of the input process, if any, is preserved by a leaky bucket.