Waleed AlSalih, <waleed@cs.queensu.ca>
Ph.D. Thesis: Mobile data collectors in wireless sensor networks
Recent advances in wireless and sensing technologies have enabled the deployment of large scale Wireless Sensor Networks (WSNs) which have a wide range of scientific and commercial applications. However, due to the limited energy supply of sensor nodes, extending the network lifetime has become crucial for WSNs to deliver their promised benefits. Several proposals have aimed at this objective by designing energy efficient protocols at the physical, medium access, and network layers. While the proposed pro- tocols achieve significant energy savings for individual sensor nodes, they fail to solve topology-related problems. An example of such problems is the bottlenecks around the sink, which is a direct result of multi-hop relaying: sensor nodes around the sink relay data generated all over the network which makes them deplete their energy much faster than other nodes.
A natural solution to this problem is to have multiple mobile data collectors so that the load is distributed evenly among all nodes. We investigate this promising direction for balancing the load and, hence, prolonging the lifetime of the network. We design optimization schemes for routing and placement of mobile data collectors in WSNs. We show, by theoretical analysis and simulations, that our approach has the potential to prolong the lifetime of the network significantly.
Waleed AlSalih, <waleed@cs.queensu.ca>
M.Sc. Thesis: Energy-aware task scheduling
Since the emergence of mobile computing, reducing energy consumption of battery- operated computing devices has become a very active research area. The widespread popularity of mobile computing devices, such as laptops, handheld devices and cell phones, motivates this research area. Several hardware based techniques have been proposed; this has led to more energy-efficient systems. Nevertheless, it is presumed in the literature of energy-aware design that software based techniques have the potential to reduce energy demand and contribute to solve the problem.
This research introduces the generic wireless cooperative system, which involves a set of heterogeneous computing devices connected via a wireless medium; in this cooperative system, the computational tasks of a resource-limited device are offloaded to one or more nearby devices in such a way that conserves energy and improves performance. In such a distributed computing environment, the assignment of computational tasks to different devices and the order of their execution play the vital role in energy conservation and performance improvement, and this is the focus of this research.
In this research, we define new energy-aware task allocation and task scheduling problems that have never yet been addressed, formulate proper task and processor models that fit the new problems and propose heuristic-based algorithms for both problems. To the best of our knowledge, this research is a pioneering work in defining and treating new generation of scheduling problems.
The proposed novel algorithms schedule a set of computational tasks, which may have dependencies and communication, into a set of heterogeneous processors in such a way that minimizes both the total consumed energy and the makespan (i.e., the time required to have all tasks completed). Experiments show that significant improvements can be achieved by using the proposed algorithms.
Ian Bentley, <bentley@cs.queensu.ca>
M.Sc. Thesis: Track persistence in wireless sensor networks
In this thesis we directly consider an object tracking problem for wireless sensor networks (WSNs), called track persistence. Track persistence temporally extends the problem of object tracking by seeking to store and retrieve the entire history of an object. To provide an initial solution to track persistence, we develop two distinct algorithms. The first algorithm, update to sink, translates track persistence into a centralized problem. The second algorithm, a linked list-like algorithm, builds a dynamic data structure as the object traverses the network, and rebuilds the object history distributively upon demand. We conduct worst case analysis upon both of these algorithms. Finally, we implement a simulation environment and run a number of tests upon both algorithms. Track persistence is a very challenging problem, and this thesis contributes a pair of solutions which stand as a basis for future research.
Kevin Brewer, <brewer@cs.queensu.ca>
M.Sc. Thesis: Parallel computation: Finding a ``moving target''
The principle of parallel computing is simple; use many processors to perform a task (by splitting the task among them and having them operate simultaneously) in order to complete it faster. Traditionally, however, the benefit offered by a parallel system is limited because the speedup (that is, the ratio of the sequential to the parallel running time) is at most linear in the number of processors. When computations are performed in real-time, however, there are many examples where a parallel system can solve a problem, but a sequential system cannot. In a real-time system, data can arrive or change, or deadlines may be present, giving the parallel system a significant advantage.
Of particular interest to this thesis is when the problem's data changes. We propose to view a changing problem (and therefore the changing solution) as an evader moving through a space representing the range of possible solutions. Then, a series of processors can be seen as pursuers trying to find the moving solution in the solution space.
This thesis describes the above concept of pursuit and evasion in solving a changing problem. We also introduce notation and terminology for expressing such computations. Various aspects of pursuit and evasion are examined and a number of variations are explored. In particular, a specific computational problem that fits this model is studied, namely, the process of searching a sorted list when the key value is changing. Solution bounds are derived for different possible ways in which the problem can change. With this basic groundwork, it is hoped that future work will further explore this paradigm of parallel computation in real-time.
Stefan Dinu Bruda, <bruda@ubishops.ca>
Ph.D. Thesis: Parallel real-time complexity theory
We present a new complexity theoretic approach to real-time computations. We define timed omega-languages as a new formal model for such computations, that we believe to allow a unified treatment of all variants of real-time computations that are meaningful in practice. To our knowledge, such a practically meaningful formal definition does not exist at this time.
In order to support our claim that timed omega-languages capture all the real-time characteristics that are important in practice, we use this formalism to model the two most important features of real-time algorithms, namely the presence of deadlines and the real-time arrival of input data. We emphasize the expressive power of our model by using it to formalize aspects from the areas of real-time database systems and ad hoc networks.
We also offer a complexity theoretic characterization of parallel real-time computations. First, we define complexity classes that capture the intuitive notion of resource requirements for real-time computations in a parallel environment. Then, we show that real-time algorithms form an infinite hierarchy with respect to the number of processors used, and that all the problems solvable in nondeterministic logarithmic space (NLOGSPACE) can be solved in real time by a parallel machine, no matter how tight the real-time constraints are. As well, we show that, once real-time constraints are dropped, several other real-time problems are in effect in NLOGSPACE. Therefore, we conjecture that NLOGSPACE contains exactly all the computations that admit feasible (poly(n) processors) real-time parallel implementations.
In the context of these results, the issue of real-time optimization problems is investigated. We identify the class of such problems that are solvable in real time, and we show that, for a large class of optimization problems, a parallel algorithm can report in real time a solution that is arbitrarily better than the solution reported by a sequential algorithm.
We also address the problem of real-time approximation algorithms. We identify problems that do not admit good approximation solutions in real time. We also show that bin packing admits a good real-time approximation algorithm.
FabioCampioni, <fabio.campioni@queensu.ca>
M.Sc. Thesis: Recruitment algorithms for vehicular crowdsending networks
Vehicular crowdsensing aims to utilize the plethora of onboard sensors and resources on smart vehicles to gather sensing data in a large coverage area. Due to vehicles predictable mobility, roadside service providers can use vehicles announced trajectories to recruit vehicles to provide sensing data for a coverage area. Selecting an optimal subset of vehicles has been previously proven to be NP-hard as it can be reduced to the set cover optimization problem. Existing works have utilized optimization models to obtain optimal solutions. Heuristic recruitment algorithms aim to obtain an approximate solution which runs in polynomial time. In this thesis, we propose several heuristic recruitment algorithms for a variety of vehicular crowdsensing problem formulations. We first explore the temporal vehicle recruitment problem where we recruit vehicles all travelling in the same direction on one road over time. We propose a heuristic recruitment algorithm to compare to an existing optimal framework and heuristic, and achieve better coverage at lower recruitment costs than the existing heuristic. We also prove that the existing heuristic can be arbitrarily bad in the worse case. We then consider the spatiotemporal vehicular recruitment problem where we recruit from vehicles moving freely in a two dimensional space. We propose a new optimal framework for obtaining optimal solutions, as well as a heuristic which we compare to an existing heuristic. Our performance evaluations show that we outperform the existing heuristic in terms of recruiter utility as well as recruitment cost. We also propose a new variation of the vehicular recruitment problem that considers a two dimensional coverage area with certain subsets of area having increased priority. We propose both an optimal model as well as a heuristic for obtaining approximate solutions and show that the heuristic achieves nearly optimal solutions. Finally, we consider the heterogeneous or multi sensor vehicular recruitment problem, where vehicles have multiple sensor types and areas of coverage require a certain sensor type to be covered. We propose an optimal model and heuristic for this problem, and again show in performance evaluations that the heuristic returns solutions close to optimal.
Salimur Choudhoury, <salimur@cs.queensu.ca>
Ph.D. Thesis: Cellular automaton based algorithms for wireless sensor networks
Wireless sensor networks have been used in different applications due to the advancement of sensor technology. These uses also have raised dierent optimization issues. Most of the algorithms proposed as solutions to the various optimization problems are either centralized or distributed which are not ideal for these real life applications. Very few strictly local algorithms for wireless sensor networks exist in the literature. In this thesis, we consider some of these optimization problems of sensor networks, for example, sleep-wake scheduling, mobile dispersion, mobile object monitoring, and gathering problems. We also consider the depth adjustment problem of underwater sensor networks. We design cellular automaton based local algorithms for these problems. The cellular automaton is a bioinspired model used to model different physical systems including wireless sensor networks. One of the main advantages of using cellular automaton based algorithms is that they need very little local information to compute a solution. We perform different simulations and analysis and find that our algorithms are effcient in practice.
Catherine Maxcy Chow, <cchow@city.coquitlam.bc.ca>
M.Sc. Thesis: Broadcasting with selective reduction: an alternative implementation and new algorithms
Broadcasting with selective reduction (BSR) is a model of parallel computation. It is an extension of the Parallel Random Access Machine (PRAM) with an additional broadcasting instruction which allows all processors to gain access to all memory locations simultaneously. At each memory location a subset of incoming data are selected according to a given selection criterion, and reduced to a single value using an appropriate reduction operator.
A generalization of BSR in which several criteria can be applied in the selection process was proposed earlier. We compare the proposed implementation of $k$-criteria BSR using a distributed memory parallel architecture with another design using a shared memory parallel architecture. This thesis also gives a feasible implementation of the multiple criteria BSR, which is more expandable and gives a better memory access time than the existing designs.
A number of computational problems are investigated and constant time algorithms are proposed. These include the problem of finding non-intersecting straight line connections of grid points to the boundary, variations to the knapsack problem, the longest consecutively-identical subsequence problem, the all point-pair distance problem, and the all point-pair inscribing problem. All the algorithms given are more efficient than the best known PRAM algorithm for the same problem.
We also revisit the convex hull problem for a set of points in the plane, and present for the first time an algorithm which runs in constant time using a number of processors linear in the size of the given set. By applying the same technique used for solving the convex hull problem, we are also able to produce a constant-time linear-cost solution to the convex polygon intersection problem. Finally, an algorithm is suggested for computing the shortest distance between two convex polygons using the multiple-criteria BSR model.
Kenny Deng, <deng@cs.queensu.ca>
M.Sc. Thesis:Throughput analysis in vehicle-to-vehicle networks
In recent years, providing wireless high-speed data connection service to fast moving vehicles on highways has been the focus of research in wireless technology. One approach is to use vehicle-to-vehicle multihop communication for packet relay, known as Vehicular Ad-hoc Networks (VANET). In this thesis, we propose a framework that supports high data rate connection using vehicle-to-vehicle multihop communication. We propose a generic TDMA-based MAC layer protocol, with base stations acting as coordinating points. Multihop relaying is used to connect source and destination nodes when they are out of transmission range of each other. Base stations select intermediate relay nodes for each connection, and assign channels to these nodes.
One key parameter in VANET is the network throughput, in terms of number of flows being accepted by the base station. Wireless signal interference is incurred when an antenna receives signals from various sources in the same channel. Therefore, with the limited number of channels, relays should be chosen, and channels should be assigned such that interference is avoided, and maximum number of flow requests is accepted. We design and implement greedy algorithms for channel assignment for two types of problems, online scheduling and offline scheduling. We identify four network parameters that affect network throughput: number of channels, transmission range, node density and request intensity. We then evaluate this algorithm against a derived theoretical average under steady network state (free flow) using different values of the network parameters. Our results show that in steady network state, the network throughput under greedy algorithm is about 70 percent of the theoretical average throughput. Offline scheduling algorithm outperforms online scheduling algorithm in all steady state test cases. Simulation results on steady network state also demonstrate that when inter-node spacing is comparable to transmission range, change of node density has significant impact on network throughput.
We also tested the greedy channel assignment algorithm using common transient states in VANET. We find out that this algorithm is resistant to slight network disturbances such as stop-and-go waves, but is seriously affected by scenarios such as gaps in the traffic flow.
Fangpeng Dong, <dong@cs.queensu.ca>
Ph.D. Thesis: Workflow scheduling algorithms in the grid
The development of wide-area networks and the availability of powerful computers as lowcost commodity components are changing the face of computation. These progresses in technology make it possible to utilize geographically distributed resources in multiple owner domains to solve large-scale problems in science, engineering and commerce. Research on this topic has led to the emergence of Grid computing. To achieve the promising potentials of tremendous distributed resources in the Grid, effective and efficient scheduling algorithms are fundamentally important.
However, scheduling problems are well known for their intractability, and many of instances are in fact NP-Complete [52]. The situation becomes even more challenging in the Grid circumstances due to some unique characteristics of the Grid. Scheduling algorithms in traditional parallel and distributed systems, which usually run on homogeneous and dedicated resources, cannot work well in the new environments.
This work focuses on workflow scheduling algorithms in the Grid scenario. New challenges are discussed, previous research in this realm is surveyed, and novel heuristic algorithms addressing the challenges are proposed and tested.
The proposed algorithms contribute to the literature by taking the following factors into account when a schedule for a DAG-based workflow is produced: predictable performance fluctuation and non-deterministic performance model of Grid resources, the computation and data staging co-scheduling, the clustering characteristic of Grid resource distribution, and the ability to reschedule according to performance change after the initial schedule is made. The performance of proposed algorithms are tested and analysed by simulation under different workflow and resource configurations.
Lorrie Fava Lindon, <lorrie@ramsey.cs.laurentian.ca>
Ph.D. Thesis: Synergy in parallel computation
Speedup is perhaps the most important measure of the performance of a parallel algorithm. Unfortunately, the term 'speedup' has been used to refer to a number of related measures, resulting in some confusion. Sorting out these various measures, and how they relate to each other, is a preliminary goal of this work. In addition, we generalize the notion of speedup, and introduce a new measure called success ratio.
The speedup theorem and Brent's theorem are two statements on the limitations of parallel speedup, both indicating that 'superlinear speedup' cannot be achieved. We contend that the statements lead to more restrictive bounds on parallel speedup than is correct in general. We review the literature on superlinear speedup, noting that almost all results in this area can be attributed to a few well-known sources of superlinear speedup. In the central part of this work, we put forward several paradigms for problems achieving superlinear speedup, and several paradigms for problems achieving superlinear speedup in novel ways.
Having shown several conditions under which the speedup theorem and Brent's theorem do not apply, we restate the theorems in a more restrictive manner which clearly limits their applicability. We investigate the consequences of these results in the areas of models computation, algorithm design, and algorithm analysis.
Paraskevi Fragopoulou, <Paraskevi.Fragopoulou@prism.uvsq.fr>
Ph.D. Thesis: Communication and fault tolerance algorithms on a class of interconnection networks
The issue of interprocessor communication in interconnection networks is a very important one and has been studied in the past by several researchers. There is a plethora of problems that arise when processors are asked to exchange information on parallel computers on which processors are interconnected according to a specific topology. Since the complete network is a prohibitively expensive topology, other types of networks are used, and as a consequence, there is a need for point-to-point communication. In this thesis, we focus our attention on four communications problems, namely, the single-node and multinode broadcasting, and the single-node and multinode scattering. These are global communication problems, in the sense that all processors participate in the communication as sources or destinations. Furthermore, the multinode broadcasting and scattering problems are symmetric, meaning that the transmission of messages is symmetric with respect to the origin of the information. All communication problems are studied under the store-and-forward, all-port communication model.
In the main part of this thesis, we study the generalized hypercube, the multidimensional torus and the star, three interconnection networks that are currently receiving considerable attention. The star interconnection network was introduced in 1986 as an attractive alternative to the binary hypercube in terms of degree, diameter, fault tolerance, and in several other aspects. Since its introduction, several of its properties have been studied and a variety of algorithms have been developed on it. The torus network is becoming increasingly popular as an underlying topology for distributed memory machines. For fixed dimensionality, the torus has bounded degree and as a consequence it is easier to implement using VLSI technology. Finally, some of the generalized hypercube networks have been proven to be more desirable than the binary hypercube for large multiprocessors, if we consider layout and wiring complexity.
The method we use to develop communication algorithms on the above networks is the construction of spanning graphs with special properties to direct the flow of information, a technique previously used for these or other networks. The properties of the spanning graphs are highly dependent on the network characteristics, the specific communications problem under consideration and the current communication model. All of the spanning graphs are constructed so that the network resources are fully utilized.
Another important issue in distributed memory multiprocessors is the fault tolerant properties of the interconnection topology. Techniques that assist the network to operate even under the presence of faults are essential. One way to achieve fault tolerant communication is by exploiting the disjoint paths that exist between pairs of nodes. With this in mind we develop fault tolerant algorithms for the above communication problems on the star network. The development of these algorithms is guided by the construction of the maximum possible number of edge-disjoint spanning trees on the star network.
In the final main chapter of this thesis, we make an attempt to generalize the technique used on the above three networks, so that it becomes applicable to a wider class of interconnection networks. As a result, a generalized framework is developed on the networks that belong to the Cayley graph based networks. Representative networks that belong to this subclass are the ring, the binary hypercube, the star, the bubble sort, the bisectional, the complete, the multidimensional torus, two networks introduced as extensions to the binary hypercube, and the generalized hypercube, to name a few. The benefit of this method is that several networks, which belong to the same class of Cayley graphs, while exhibiting diversity in terms of their characteristics (such as number of nodes, degree, diameter, average diameter, fault tolerance, etc.), are treated uniformly in terms of some communication problems.
A literature review of the state-of-the-art in relation to the above problems is provided. We conclude with a summary of the results obtained, and a list of related open problems.
Md. Kamrul Islam, <islam@cs.queensu.ca>
M.Sc. Thesis: Bounds on some geometric transforms
A flip or edge-replacement can be considered as a transformation by which one edge e of a geometric figure is removed and an edge f, where f is not equal to e, is inserted such that the resulting figure belongs to the same class as the original figure. This thesis is concerned with transformation of two kinds of geometric objects, namely, planar trees and planar paths, through the application of flips.
A technique is presented for transforming a given planar tree into another one for a set of n points in general position in the plane. It is proved that the number of flips required for such a transformation is at most 2n-k-s-2, where k and s are greater than or equal to 1.
In the case of planar path transformation we show that any planar path can be transformed into another by at most 2n-5 flips for a set of n points in convex position in the plane. Besides, experimental results are presented that show transformability of any planar path into another considering n points in general position, where n is less than or equal to 13.
Later, we investigate the possibility of using flips, as an enumeration technique to generate the set P(S) of all planar paths of a set S of n points in convex position in the plane. First, it is shown that |P(S)|= n2^{n-3}. Then two algorithms are proposed that describe the ways flips can be used to generate all the planar paths uniquely. The first algorithm is based on a recursion technique and uses flips of size one. The second algorithm is non-recursive and uses flips of size one and flips of size two (two edges are removed and two are inserted simultaneously) to enumerate all such paths uniquely.
Md. Kamrul Islam, <islam@cs.queensu.ca>
Ph.D. Thesis: Energy aware techniques for certain problems in wireless sensor networks
Recent years have witnessed a tremendous amount of research in the field of wireless sensor networks (WSNs) due to their numerous real-world applications in environmental and habitat monitoring, fire detection, object tracking, traffic controlling, industrial and machine-health control and monitoring, enemy-intrusion in military battlefields, and so on. However, reducing energy consumption of individual sensors in such networks and obtaining the expected standard of quality in the solutions provided by them is a major challenge. In this thesis, we investigate several problems in WSNs, particularly in the areas of broadcasting, routing, target monitoring, self-protecting networks, and topology control with an emphasis on minimizing and balancing energy consumption among the sensors in such networks. Several interesting theoretical results and bounds have been obtained for these problems which are further corroborated by extensive simulations of most of the algorithms. These empirical results lead us to believe that the algorithms may be applied in real-world situations where we can achieve a guarantee in the quality of solutions with a certain degree of balanced energy consumption among the sensors.
Md. Tauhidul Islam, <tauhidul@cs.queensu.ca>
Ph.D. Thesis: Radio Resource Allocation for Device-to-Device Communications Underlaying Cellular Networks
Inexpensive connectivity and computing power have caused the number of communicating devices to explode in the last decade. New applications are emerging every day to take advantage of the proximity and abundance of these devices. Device-to-Device (D2D) communication as an underlay to cellular network to increase spectral efficiency is a technology component of Long Term Evolution - Advanced (LTE-A). In D2D communication underlaying cellular networks, devices communicate with each other using a direct link using cellular resources without going through the evolved Node B (eNB) but remaining under the control of it. D2D communication is expected to be one of the prominent features supported by future cellular networks because of reusing the cellular spectrum to increase the system performance of cellular networks. However, due to the limitations of a licensed spectrum when these devices share a cellular spectrum to communicate directly among themselves, the same resource may need to be shared among cellular and D2D communicating pairs. This resource sharing introduces a new interference scenario which needs to be coordinated through a new resource allocation scheme. We investigate this problem of interference coordination and explore three different perspectives from which this problem can be viewed, namely a) interference minimization; b) fair allocation while minimizing interference; c) Quality of Service (Qos) satisfaction while maximizing total system sum rate of the cellular network. We show that the proposed schemes are suitable for the short LTE scheduling period of 1 ms as they are computationally less expensive. Our schemes can allocate radio resources to D2D pairs underlaying a cellular network in a short time, ensuring fairness in allocation while minimizing interference, and increasing the total system sum rate of the network while maintaining a QoS target.
AnneKayem, <kayem@cs.queensu.ca>
Ph.D. Thesis: Adaptive Cryptographic Access Control for Dynamic Data Sharing Environments
Distributed systems, characterized by their ability to ensure the execution of multiple transactions across a myriad of applications, constitute a prime platform for building Web applications. However, Web application interactions raise issues pertaining to security and performance that make manual security management both time-consuming and challenging. This thesis is a testimony to the security and performance enhancements afforded by using the autonomic computing paradigm to design an adaptive cryptographic access control framework for dynamic data sharing environments. One of the methods of enforcing cryptographic access control in these environments is to classify users into one of several groups interconnected in the form of a partially ordered set. Each group is assigned a single cryptographic key that is used for encryption/decryption. Access to data is granted only if a user holds the ``correct'' key, or can derive the required key from the one in their possession. This approach to access control is a good example of one that provides good security but has the drawback of reacting to changes in group membership by replacing keys, and re-encrypting the associated data, throughout the entire hierarchy. Data re-encryption is time-consuming, so, rekeying creates delays that impede performance. In order to support our argument in favor of adaptive security, we begin by presenting two cryptographic key management (CKM) schemes in which key updates affect only the class concerned or those in its sub-poset. These extensions provide performance enhancements, but handling scenarios that require adaptability remain a challenge. Our framework addresses this issue by allowing the CKM scheme to monitor the rate at which key updates occur and to adjust resource (keys and encrypted replicas) allocations to handle future changes by anticipation rather than on demand, the CKM scheme acquires the property of adaptability and minimizes the long-term cost of key updates. Finally, since self-protecting CKM requires a lesser degree of physical intervention by a human security administrator, we consider the case of ``collusion attacks'' and propose two algorithms to detect as well as prevent such attacks. A complexity and security analysis show the theoretical improvements our schemes offer. Each algorithm presented is supported by a proof of concept implementation, and experimental results to show the performance improvements.
Chi Kit Lau
M.Sc. Thesis: A parallel algorithm for Toeplitz systems of linear equations
This thesis proposes a new parallel algorithm to solve general Toeplitz systems of linear equations. The Toeplitz matrix has an interesting property: the matrix entries are constant along each diagonal of the matrix. This work has been motivated by the multi-user detection in wireless basestations project, which is supported by the CITO (Communication and Information Technologies Ontario) center of excellence.
The algorithm is based on a linear processor array model. It is an extension of an algorithm due to Schur. It takes O(n) time, storage space, and processors. Performance of the parallel algorithm is improved by taking advantage of two levels of parallelism. On one hand, different stages of the algorithm are pipelined to different processors. On the other hand, multiple instructions are executed in parallel by multiple functional units within a processor. A regeneration technique is employed to restore the upper triangular matrix, which prevents the O(n^2) storage for the entire matrix. Since the parallel model has an extensible architecture and requires only localized communication, it is ideal for implementation in VLSI technology. The new algorithm is compared to other parallel Toeplitz solvers. It is shown that the new algorithm runs faster, saves more storage space, and can be applied to wider classes of Toeplitz systems.
Hong Li
M.Sc. Thesis: Guaussian elimination with partial pivoting on a distributed memory system
One of the main steps of multiuser detection in wireless cellular basestations is to solve a system of linear equations. This thesis describes a variant of the Gaussian elimination algorithm for solving such a system on a set of processors arranged in a star architecture. Rows are distributed onto the processors via a host processor. A new pivoting scheme is proposed for the algorithm. The scheme requires no global communication and avoids sequential computation for finding the pivot element. It also avoids communication costs usually required to ensure a balance of computational load among the processors. A numerical analysis method is used to estimate the performance of the algorithm. The algorithm achieves a speedup of O(p) if the number of peripheral processors is p. The stability of the algorithm is evaluated, demonstrating that the algorithm is as stable as Gaussian elimination with standard partial pivoting.
Xiaoshuang Lu, <lux@cs.queensu.ca>
M.Sc. Thesis: Energy-aware dynamic task allocation in mobile ad hoc networks
Dynamic task scheduling has been intensively studied over the last several years. However, since the emergence of mobile computing, there is a need to study dynamic scheduling in the environment of mobile ad hoc networks, which contain a group of heterogeneous mobile nodes powered by batteries. For such a time-energy sensitive system, performance evaluation using only a time metric is not enough. In this thesis, we propose a novel energy-aware dynamic task allocation (EADTA) algorithm with a goal of time-energy efficiency. When a task is to be allocated to a processing node, the algorithm examines each candidate node to determine its processing capability, job queue length, energy level, communication delay, and energy consumption for communication. The algorithm then assigns the task to that node that optimizes an objective function of time and energy. We develop a simulation model to evaluate the performance of the algorithm under different scenarios. Results demonstrate that EADTA is superior to traditional algorithms in both the time and energy metrics.
Elodie Lugez, <lugez@cs.queensu.ca>
Ph.D. Thesis: Electromagnetic tracking in ultrasound-guided high dose rate prostate brachytherapy
Electromagnetic (EM) tracking assistance for ultrasound-guided high-dose-rate (HDR) prostate brachytherapy has recently been introduced in order to enable prompt and uncomplicated reconstruction of catheter paths with respect to the prostate gland. However, EM tracking within a clinical setting is notorious for fluctuating measurement performance. In fact, measurements are prone to errors due to field distortions caused by magnetic and conductive objects and can compromise the outcome of the procedure. Enhancing these measurements is therefore paramount.
The objective of this thesis is to enable robust and accurate reconstructions of HDR catheter paths on the ultrasound images of the prostate gland using EM tracking. To achieve this objective, the measurement uncertainty of an electromagnetic system was first characterized in various environments; this characterization enabled us to identify optimum setup configurations and model the measurement uncertainty. Second, we designed and implemented a specialized filtering method for catheter path reconstructions, combining the nonholonomic motion constraints which apply to the EM sensor, with both the position and orientation measurements of the sensor. Finally, the ultrasound probe was robustly tracked with the help of a simultaneous localization and calibration algorithm; this method allows for dynamic tracking of the ultrasound probe while simultaneously mapping and compensating for the EM field distortions.
We experimentally validated the performance of our advanced filter for catheter path reconstructions in an HDR brachytherapy suite; the EM sensor was threaded within paths of various curvatures at several insertion speeds. The simultaneous ultrasound probe tracking and EM field distortion compensation approach was also assessed in the brachytherapy suite. The performances of our approaches were compared to conventional error minimization methods. The advanced methods effectively increased the EM tracking accuracy of catheter paths and ultrasound probes. With the help of our proposed approaches, EM tracking can provide effective assistance for a plurality of clinical applications.
Cameron McKay, <mckay@cs.queensu.ca>
M.Sc. Thesis: Molecular codebreaking and double encoding
DNA computing is an unconventional branch of computing that uses DNA molecules and molecular biology experiments to perform computations. This thesis evaluates the feasibility of implementing molecular codebreaking, a DNA computing technique that uses a known-plaintext attack to recover an encryption key, and double encoding, a proposed error resistance technique that is designed to reduce the number of false negatives that occur during DNA computation.
This thesis evaluates molecular biology experiments that make up a molecular codebreaker, a theoretical DNA computer that has never been attempted in the laboratory until now. Molecular techniques such as ligation, gel electrophoresis, polymerase chain reaction (PCR), graduated PCR, and bead separation were carried out, reported upon and found to be feasible with certain reservations.
An implementation of the error resistance technique of double encoding, where bits are encoded twice in a DNA strand, was designed and attempted. Although the implementation was unsuccessful, several issues associated with double encoding were identified, such as encoding adaptation problems, strand generation penalties, strand length increases, and the possibility that double encoding may not reduce the number of false negatives.
Arezou Mohammadi, <arzmoh@yahoo.com>
Ph.D. Thesis: Scheduling algorithms for real-time systems
Real-time systems are those whose correctness depends not only on logical results of computations, but also on the time at which the results are produced. This thesis provides a formal definition for real-time systems and includes the following original contributions on real-time scheduling algorithms.
The first topic studied in the thesis is minimizing the total penalty to be paid in scheduling a set of soft real-time tasks. The problem is NP-hard. We prove the properties of any optimal scheduling algorithm. We also derive a number of heuristic algorithms which satisfy the properties obtained. Moreover, we obtain a tight upper bound for the optimal solution to the problem. Numerical results that compare the upper bound with the optimal solution and the heuristic algorithms are provided.
In the second part of this thesis, we study the problem of minimizing the number of processors required for scheduling a set of periodic preemptive independent hard real-time tasks. We use a partitioning strategy with an EDF scheduling algorithm on each processor. The problem is NP-hard. We derive lower and upper bounds for the number of processors required to satisfy the constraints of the problem. We also compare a number of heuristic algorithms with each other and with the bounds derived in this research. Numerical results demonstrate that our lower bound is very tight.
In the third part of the thesis, we study the problem of uplink scheduling in telecommunication systems with two dimensional resources. Our goal is to maximize the total value of the packets sent in uplink subframe such that system constraints and requirements are satisfied. The packets have various QoS requirements and have either soft or hard deadlines. We take two approaches, namely 0-1 and fractional approaches, to model the problem. Considering the properties of the application, we derive globally optimal solutions in polynomial time for the models. We also present a method to fine-tune the models. Numerical results are provided to compare the performance of the various optimal algorithms each corresponding to a model.
Marius Nagy, <marius@cs.queensu.ca>
M.Sc. Thesis: Parallelism in real-time computation
Computational paradigms in which time plays a central role in defining the problem to be solved are generally called real-time paradigms. Real time is a generic term, encompassing the multitude of aspects encountered today in the systems area as well as in theoretical studies. An algorithm that solves a problem in real time must be able to handle a stream of input data, arriving during the computation. Usually, there is also a precise deadline that must be met when the solution is obtained. These are the main features characterizing the real-time paradigms investigated in this thesis.
Performance of parallel and sequential models of computation are compared in various real-time environments. Evidence is provided to demonstrate the importance of parallelism in the real-time area. The time constraints imposed by some problems allow only a parallel algorithm to successfully complete the computation. Consequently, the difference between parallel and sequential machines is often that separating success and failure. This is the case, for example, for the pattern classifier based on the nearest neighbor rule, where in the worst case, the sequential machine will incorrectly classify all the input samples provided, except for the first one. The pipeline computer, on the other hand, produces the correct class for every sample in the input stream.
Even if the sequential computer manages to output a solution before the deadline, the improvement in the quality of the solution observed when a parallel model is employed, could be dramatic. This improvement may grow arbitrarily large or it can be superlinear in the number of processors of the parallel computer. Specifically, we show that for a series-parallel graph of size n, the accuracy ratio achieved by a PRAM with n/log n processors when computing the cardinality of a minimum covering set is, in some cases, on the order of n. Similarly, when locating the center of a tree in real time, there are cases in which the accuracy ratio achieved by a parallel algorithm running on a PRAM with n/log n processors is bigger than p, the number of time intervals in the real-time computation. For p greater or equal with n/log n a synergistic behavior is revealed again.
The improvement in the quality of the solution, gained by using a parallel algorithm that locates the median of a tree network of size n with demand rates changing arbitrarily is shown, in some circumstances, to be on the order of n to the power of (x-1), where x is greater or equal to 1. For the same median problem, but in a growing tree network with equal demand rates, the error generated by the sequential algorithm can be arbitrarily large, even exponential in the number of nodes in the network.
Well-established paradigms like data-accumulation and correcting algorithms are addressed in this thesis. The study of novel paradigms, like those introduced by reactive real-time systems, is also initiated. The results obtained herein for all these paradigms, using different models of parallel computation, as well as the practical aspects of the problems investigated and the increasing importance of real-time requirements in today's computations should help parallelism earn its rightful place in computer science and motivate further research.
Marius Nagy, <marius@cs.queensu.ca>
Ph.D. Thesis: Using quantum mechanics to enhance information processing
The weird quantum mechanical effects governing the behavior of sub-atomic particles are about to revolutionize the way we perform computation and manipulate information. This thesis is a testimony to the indelible mark that quantum mechanics has already left on computer science. Specifically, we have investigated some of the consequences of manipulating information at the quantum level on data security, parallel processing, universality and computability. We have devised an efficient scheme for entanglement verification with direct applicability to key distribution protocols based on entanglement. We also showed how an approach exploiting the context of a qubit in the quantum Fourier transform can be successful in dealing with low levels of eavesdropping, by propagating the disruption through data dependency. The importance of parallelism for quantum information processing and its consequence on universality is demonstrated through a series of evolving computing paradigms for which only a parallel approach can guarantee a reliable solution. We also bring a necessary clarification to the much disputed problem regarding the comparison between the computational power of a quantum machine and that of a conventional computer.
Naya Nagy, <nagy@cs.queensu.ca>
M.Sc. Thesis: The maximum flow problem: A real time approach
Given the large variety of its applications, the maximum flow problem has been studied ever since its definition in 1974. The problem aims to find the maximum flow that can exist between a source and a sink in a graph. The graph is weighted with the capacities of the edges.
In this work, a dynamic version of the problem is defined and studied. The graph receives corrections to its structure or capacities and consequently the value of the maximum flow is modified. Corrections arrive in real time. The real-time paradigm imposes time constraints (deadlines) on the input and output of the computation. Parallel and sequential solutions are developed and a comparative analysis of these solutions is presented.
The generally accepted advantage of using parallel computers is to reduce the running time of computations. In real-time computation, a parallel solution can make the difference between success and failure of the computation. A parallel machine of an appropriate power is able to cope with the deadlines in due time, thus rendering the computation successful, while a sequential implementation is slower and fails to meet the deadlines. Details are given in the analysis of the algorithms designed for the sequential random access machine (RAM) and the parallel reconfigurable multiple bus model (RMBM).
The real-time maximum flow problem is applied to the solution of a real-time process scheduling. The scheduling is an extension of Stone's static two processor allocation problem. The initial static problem assigns processes to two processors to minimize an objective function. The real-time version described in this thesis is a natural extension given the changing characteristics of the processes in real time. The model proposed allows processes to be created and destroyed, to change the amount of communication between them, and so on. The two processor allocation problem is then solved taking in consideration these variations in real time. Parallel and sequential algorithms are designed and analyzed. The parallel algorithm is always able to compute the optimal schedule, while the solution obtained sequentially is only an approximation. The improvement provided by the parallel approach over the sequential one is polynomial in the number of processors used by the parallel computer.
Naya Nagy, <nagy@cs.queensu.ca>
Ph.D. Thesis: Applications of quantum cryptography
This thesis extends the applicability of quantum cryptography. First, we prove that quantum cryptography at least equals classical cryptography in an important area, namely authentication. The quantum key distribution protocols presented here show that, contrary to previous belief, authentication can be done with quantum methods only.
In addition, we have designed quantum security systems in unconventional settings. The security of sensor networks poses specific challenges, as the sensor nodes in particular can be physically picked up by the intruder. Our scheme protects both the integrity of the communication messages and it also protects the identity of the nodes, such that a reading intrusion of a node is detectable.
The problem of access control in a hierarchy refers to a large number of users, organized in a hierarchy, having selective access rights to a database. Our quantum solution introduces quantum keys to the effect that the cryptographic scheme is dynamically adaptable to changes in the user structure, and it exhibits increased security levels.
To the best of our knowledge, this thesis is the first to introduce quantum keys, that is secret keys defined by an array of qubits. We show that quantum keys make it possible for two parties to communicate with one-time pads without having to meet in advance. Also, opposite to previous cryptographic ``common sense", the security level of a quantum cryptosystem with quantum keys and quantum messages is maintained while being used.
Constantine N. K. Osiakwan, <osiakwan@bnr.ca>
Ph.D. Thesis: Parallel computation of weighted matchings in graphs
An important class of problems in theoretical computer science is that of combinatorial optimization problems. Such problems ask for the "best" configuration that satisfies some properties. The properties addressed in this thesis concern finding optimum weight matchings in graphs.
Given a graph with n vertices and a weight on each edge, a matching is a subset of edges such that no two edges in the matching have a common vertex. The weight of a matching is the sum of weights of the edges in the matching. An optimum weight matching is a matching that has either minimum or maximum weight, depending on the application.
Efficient methods for computing optimum weight matchings on a single processor computer exist in the literature. Developments in very large scale integrated circuits have made it possible to devise parallel computers. In this thesis, we develop efficient algorithms for computing optimum weight matchings on a parallel computer.
All the algorithms we describe assume the EREW PRAM model of parallel computation with p (<= n) processors. An O( n/p + log n ) time parallel algorithm for computing matching trees is proposed. The assignment problem is extended to a general assignment problem, where the edge weights could be negative, rather than only positive, and solved in O( n^3/p + n^2 log n ) time. Another parallel algorithm with the same complexity as the latter is designed for computing maximum weight perfect matchings for complete graphs. These techniques are then extended and used in the design of parallel algorithms for matchings on the plane. For the assignment problem on the plane, an O( n^3/p^2 + n^(2.5) log n) time parallel algorithm is given. Finally, we present an O( n^(2.5) log^4 n/p) time parallel algorithm for computing minimum weight perfect matchings on the plane. In the later two algorithms, it is assumed that p <= n^0.5.
Alexandros Palioudakis, <alex@cs.queensu.ca>
Ph.D. Thesis: State complexity of nondeterministic finite automata with limited nondeterminism
In this thesis we study limited nondeterminism in nondeterministic finite automata (NFA). Various approaches of quantifying nondeterminism are considered.
We consider nondeterministic finite automata having finite tree width (ftw-NFA) where the computation on any input string has a constant number of branches. We give effective characterizations of ftw-NFAs. We give a tight worst-case state size bound for determinizing an ftw-NFA A as a function of the tree width and the number of states of A. We introduce a lower bound technique for ftw-NFAs.
We study the interrelationships between various measures of nondeterminism for finite automata. We present a new approach of quantifying nondeterminism, we call this measure the trace. The trace of an NFA is defined in terms of the maximum product of the degrees of nondeterministic choices in any computation. We establish upper and lower bounds for the trace of an NFA in terms of its tree width. We also study the growth rate of trace and we show that the unbounded trace as a function of input length of an NFA has exponential growth.
It is known that an NFA with n states and branching k can be simulated by a deterministic finite automaton with multiple initial states (MDFA) having k times n states. We give a lower bound for the size blow-up of this conversion. We consider also upper and lower bounds for the number of states an MDFA needs to simulate a given NFA of finite tree width.
We consider unary finite automata employing limited nondeterminism. We show that for a unary regular language, a minimal ftw-NFA can always be found in Chrobak normal form. A similar property holds with respect to other measures of nondeterminism. The latter observation is used to establish, for a given unary regular language, relationships between the sizes of minimal NFAs where the nondeterminism is limited in various ways.
We study also the state complexity of language operations for unary NFAs with limited nondeterminism. We consider the operations of concatenation, Kleene star, and complement.We give upper bounds for the state complexity of these language operations and lower bounds that are fairly close to the upper bounds. Our constructions rely on the fact that minimal unary NFAs with limited nondeterminism can be found in Chrobak normal form. Finally, we show that the branching measure (J. Goldstine, C. Kintala, D. Wotschke, Inf. and Comput vol 86, 1990, 179-194) of a unary NFA is always either bounded by a constant or has an exponential growth rate.
Francisco de la Parra, <parra@cs.queensu.ca>
M.Sc. Thesis: A sensor network querying framework for target tracking
Successful tracking of a mobile target with a sensor network requires effective answers to the challenges of uncertainty in the measured data, small latency in acquiring and reporting the tracking information, and compliance with the stringent constraints imposed by the scarce resources available on each sensor node: limited available power, restricted availability of the inter-node communication links, relatively moderate computational power.
This thesis introduces the architecture of a hierarchical, self-organizing, two-tier, mission-specific sensor network, composed of sensors and routers, to track the trajectory and velocity of a single mobile target in a two-dimensional convex sensor field. A query-driven approach is proposed to input configuration parameters to the network, which allow sensors to self-configure into regions, and routers into tree-like structures, with the common goal of sensing and tracking the target in an energy-aware manner, and communicating this tracking data to a base station node incurring low-overhead responses, respectively.
The proposed algorithms to define and organize the sensor regions, establish the data routing scheme, and create the data stream representing the real-time location/velocity of a target, are heuristic, distributed, and represent localized node collaborations. Node behaviours have been modeled using state diagrams and inter-node collaborations have been designed using straightforward messaging schemes.
This work has attempted to establish that by using a query-driven approach to track a target, high-level knowledge can be injected to the sensor network self-organization processes and its following operation, which allows the implementation of an energy-efficient, low-overhead tracking scheme. The resulting system, although built upon simple components and interactions, is complex in extension, and not directly available for exact evaluation. However, it provides intuitively advantageous behaviours.
Sandy Pavel, <sandy.pavel@sympatico.ca>
Ph.D. Thesis: Computation and communication aspects of arrays with optical pipelined buses
In large-scale general-purpose parallel machines based on connection networks, efficient communication capabilities are essential in order to solve most of the problems of interest in a timely manner. Interprocessor communication networks are often the main bottlenecks in parallel machines. One important drawback of these networks concerns the exclusive access to a communication link which limits the communication throughput to a function of the end-to-end propagation time. Optical communications have been proposed as a solution to this problem. Unlike electronic buses, in which the signal propagation is bidirectional, optical channels are inherently directional and have a predictable delay per unit length. This allows a pipeline of signals to be created by the synchronized directional coupling of each signal at specific locations along the channel. The possibility in optics to pipeline the transmission of signals through a channel provides an alternative to exclusive channel access. Using this kind of spatial parallelism the end-to end propagation latency can be amortized over the number of parallel messages active at the same on the channel.
The model of computation proposed and investigated in this thesis consists of an array that uses reconfigurable optical buses for communication (AROB). It increases the capabilities of other arrays with optical pipelined communication studied in the literature, through the use of more powerful switches and different reconfiguration rules. Some of the results presented in this thesis extend the results previously obtained for the other types of arrays with optical buses, allowing a better understanding of the implications of using optical interconnections for massively parallel processing.
The AROB is shown to be extremely flexible, as demonstrated by its ability to efficiently simulate different variants of the Parallel Random Access Machine (PRAM), bounded degree networks and reconfigurable networks. A number of applications of the AROB are presented, and its power is analyzed. Our investigation reveals that this architecture is suitable for massively parallel applications in different areas such as low-level image processing (Hough Transform), sparse matrix operations (multiplications, transpose), and data communications (partial permutation routing, h-relations).
When using optics, techniques that are unique and suitable to optics must be developed. Our main objective is to identify the mechanisms specific to this type of architectures that allow us to build efficient algorithms. Finally, lower bounds in terms of area and time are obtained for the types of electro-optical systems that use pipelined communications.
Ke Qiu, <kqiu@dragon.acadiau.ca>
Ph.D. Thesis: The star and pancake interconnection networks: properties and algorithms
The star and pancake interconnection networks were proposed in 1986 as attractive alternatives to the popular hypercube topology for interconnecting a number of processors in a parallel computer. Both the star and pancake possess many properties that are desirable in an interconnection network, such as a small diameter and a small degree, and they compare favorably with the hypercube in many other aspects. They have received much attention lately as researchers continue to explore their properties. In this thesis, we investigate the two networks from two perspectives, namely, topologically and algorithmically.
The topological properties of the two networks are first studied. They include the path and cycle structures of the star and pancake models. These are very useful in that they are the basic units that are later exploited to develop efficient routing schemes and other application algorithms. We also study the problems of embedding stars and pancakes into each other, and embedding meshes and tori of certain dimensions into star graphs.
We then study the networks from the algorithms point of view. This study is divided into four parts.
Various routing schemes, the key to fast communication among the processors in an interconnection network, are first presented.
We then describe a number of data communication procedures, such as broadcasting and computing prefix sums, on the star and pancake interconnection networks. These are fundamental building blocks that can be used in the design of larger application algorithms whose performance will directly depend on the performance of the data communication procedures.
Another problem we study is that of load balancing. The problem of load balancing on the star and pancake networks is interesting in its own right. It is important in parallel computation in that is distributes tasks evenly to all the processors in a network, thus reducing congestion. We then use the load balancing algorithm to find an efficient selection algorithm for the two networks.
In the last part of this study, the routing and data communication algorithms are used to develop solutions to some of the most important problems in computational geometry and graph theory. These problems include determining the convex hull of a set of points in the plane, and building a minimum-weight spanning forest of a weighted graph.
A literature review of the state-of-the-art in relation to the star and pancake interconnection networks is also provided, as well as a list of open problems in this area.
Geoffrey Seaborn, <seaborn@cs.queensu.ca>
M.Sc. Thesis: Changes in autonomic tone resulting from circumferential pulmonary vein isolation
In patients with normal hearts, increased vagal tone can be associated with the onset of paroxysmal atrial fibrillation (AF). Vagal denervation of the atria renders AF less-easily inducible. Catheter ablation involving circumferential pulmonary vein ablation (CPVA) and isolation (CPVI) is effective for treating paroxysmal AF, and has been shown to impact heart rate variability (HRV) indices, in turn reflecting vagal denervation. I examined the impact of CPVI on HRV indices over time, and evaluated the relationship between vagal denervation and rate of recurrence of AF post-procedure.
High-resolution 10-minute ECG recordings were collected from 64 patients (49 male, 15 female, mean age 57.1±9.7) undergoing CPVI for paroxysmal (n=46) or persistent (n=18) AF. Recordings were made pre-procedure, and at intervals up to 12 months. Recordings from healthy volunteers were used as control data. Anti-arrhythmic medication was suspended 5 half-lives prior to the procedure, and was resumed post-procedure for 3 months. A successful procedure was defined as one with no subsequent recurrence of atrial arrhythmia (AA), such as atrial tachycardia (AT), atrial flutter (AFL), or AF. HRV analysis was performed for all recordings in accordance with guidelines for standardization.
After CPVI, 27 patients presented recurrence. In patients with a subsequent successful procedure (group A), pre-procedure HRV indices did not differ from control patients (group C). However, patients who exhibited recurrence (group B) demonstrated significantly-reduced pre-procedure HRV compared both group C, and with patients from group A (30.8±14.0 & 33.1±20.1 vs 21.9±11.1 in RMSSD, P=0.04). Following the CPVI procedure, HRV was reduced with respect to pre-procedure levels in patients with successful procedures (33.1±20.1 vs 23.7±19.4, P=0.04), and did not differ from patients with unsuccessful procedures over 12 months of follow-up recordings. The post-procedure HRV of both groups was reduced compared to control values. Additionally, there was no significant difference in HRV between patients who experienced recurring AF (n=9), and those who experienced AT or AFL (n=18). Our data suggests that patients experiencing recurrence after one procedure have reduced pre-procedure HRV that is not changed by CPVI; whereas patients with a successful single procedure experience a change in HRV indices that is sustained over a long period, but is no different, post-procedure, from patients experiencing recurrence. These data suggest that the denervation associated with the CPVI procedure may only benefit patients with normal vagal tone prior to the procedure, and that sustained denervation is not a critical factor in successful outcome. Further prospective studies appear warranted to target patients with normal vagal tone.
Geoffrey Seaborn, <seaborn@cs.queensu.ca>
Ph.D. Thesis: Clinical decision support algorithm for predicition of postoperative atrial fibrillation following coronary artery bypass grafting
Introduction: Postoperative atrial fibrillation (POAF) is exhibited by 20-40% of patients following coronary artery bypass grafting (CABG). POAF is associated with increased long-term morbidity and mortality, as well as additional healthcare costs. I aimed to find techniques for predicting which patients are likely to develop POAF, and therefore who may benefit from prophylactic measures.
Methods: Informed consent was obtained prospectively from patients attending for elective CABG. Patients were placed in the POAF group if atrial fibrillation (AF) was sustained for at least 30 seconds prior to discharge, and were placed in the `no AF' (NOAF) group otherwise. I evaluated the performance of classifiers including binary logistic regression (BLR), k-nearest neighbors (k-NN), support vector machine (SVM), artificial neural network (ANN), decision tree, and a committee of classifiers in leave-one-out cross validation. Accuracy was calculated in terms of sensitivity (Se), specificity (Sp), positive predictive value (PPV), negative predictive value (NPV), and C-statistic.
Results: Consent was obtained from 200 patients. I excluded 21 patients due to postoperative administration of amiodarone, 5 due to perioperative AF ablation, and 1 due to both. Exclusions were also made for 8 patients with a history of AF and 2 patients with cardiac implantable electronic devices (CIED). POAF was exhibited by 54 (34%) of patients. Factors significantly associated (P<0.05) with POAF were longer postoperative hospital stay, advanced age, larger left atrial (LA) volume, presence of valvular disease, and lower white blood cell count (WCC). Using BLR for dimensionality reduction, I created a feature vector consisting of age, presence of congestive heart failure (CHF) (P=0.06), valvular disease, WCC, and aortic valve replacement (AVR). I performed leave-one-out cross validation. In unlabeled testing data, I obtained Se=70%, Sp=56%, PPV=89%, NPV=26%, and C=58% using a committee (BLR, k-NN, and ANN).
Conclusion: My results suggest that prediction of patients likely to develop POAF is possible using established machine learning techniques, thus allowing targeting of appropriate contemporary preventative techniques in a population at risk for POAF. Studies appear warranted to discover new predictive indices that may be added to this algorithm during continued enrolment and validation.
Amber Simpson, <simpson@cs.queensu.ca>
M.Sc. Thesis: On solving systems of linear equations in real time
The purpose of this thesis is to investigate the feasibility of applying the real-time paradigm to the problem of solving a system of linear equations. Unlike the conventional paradigm, the real-time paradigm is an environment characterized by the constant arrival of data and the existence of deadlines. The problem is stated as follows: Given a solution x_0 of the system of equations A_0 x = b, with one or more of the entries of A_0 changing to produce the system A_1, is it possible to use x_0 to obtain a solution x_1 without recomputing x_1? We conjecture that this is not possible in general. This means that each time an update is received during the computation of the solution of a system of linear equations, the solution must be recomputed from scratch to accurately reflect the change (in the worst case). The only evidence to support this claim is an Omega(n) lower bound on such computations. A more convincing lower bound is required to prove our conjecture though one is not offered in this thesis. We demonstrate that while we believe it is impossible to use a previously computed solution to produce a new solution, it is possible to relax our real-time restrictions to produce a parallel solution that further improves upon the sequential solution by processing newly arriving data and producing more solutions in the same time frame.
Emese Somogyvari, <somogyva@cs.queensu.ca>
M.Sc. Thesis: Quantitative structure-activity relationship modeling to predict drug-drug interactions between acetaminophen and ingredients in energy drinks
The evaluation of drug-drug interactions (DDI) is a crucial step in pharmaceutical drug discovery and design. Unfortunately, if adverse eects are to occur between the co-administration of two or more drugs, they are often dicult to test for. Tradi- tional methods rely on in vitro studies as a basis for further in vivo assessment which can be a slow and costly process that may not detect all interactions. Here is pre- sented a quantitative structure-activity relationship (QSAR) modeling approach that may be used to screen drugs early in development and bring new, benecial drugs to market more quickly and at a lesser cost. A data set of 6532 drugs was obtained from DrugBank for which 292 QSAR descriptors were calculated. The multi-label support vector machines (SVM) method was used for classication and the K-means method was used to cluster the data. The model was validated in vitro by exposing Hepa1-6 cells to select compounds found in energy drinks and assessing cell death. Model accuracy was found to be 99%, predicting 50% of known interactions despite being biased to predicting non-interacting drug pairs. Cluster analysis revealed in- teresting information, although current progress shows that more data is needed to better analyse results, and tools that bring various drug information together would be benecial. Non-transfected Hepa1-6 cells exposed to acetaminophen, pyridoxine, creatine, L-carnitine, taurine and caeine did not reveal any signicant drug-drug interactions, nor were they predicted by the model.
Emese Somogyvari, <somogyva@cs.queensu.ca>
Ph.D. Thesis: Exploring epigenetic drug discovery using computational approaches
The misregulation of epigenetic mechanisms has been linked to disease. Current drugs that treat these dysfunctions have had some success, however many have variable potency, instability in vivo and lack target specicity. This may be due to the limited knowledge on epigenetic mechanisms, especially at the molecular level, and their association with gene expression and its link to disease. Computational approaches, specically in molecular modeling, have begun to address these issues by complementing phases of drug discovery and development, however more research is needed on the relationship between genetic mutation and epigenetics and their roles in disease. Gene regulatory network models have been used to better understand diseases, however inferring these networks poses several challenges. To address some of these issues, a multi-label classication technique to infer regulatory networks (MInR), supplemented by semi-supervised, learning is presented. MInR's performance was found to be comparable to other methods that infer regulatory networks when when evaluated on a benchmark E.coli dataset. In order to better understand the association of epigenetics with gene expression and its link with disease, MInR was used to infer a regulatory network from a Kidney Renal Clear Cell Carcinoma (KIRC) dataset and was supplemented with gene expression and methylation analysis. Gene expression and methylation analysis revealed a correlation between 5 dierentially methylated CpGs and their matched dierentially expressed transcripts. Incorporating this information into network analysis allowed for the identication of potential targets that may be used in the discovery of novel therapeutics.
Ian Stewart, <ian@cs.queensu.ca>
M.Sc. Thesis: A modified genetic algorithm and switch-based neural network model applied to misuse-based intrusion detection
As our reliance on the Internet continues to grow, the need for secure, reliable networks also increases. Using a modied genetic algorithm and a switch-based neural network model, this thesis outlines the creation of a powerful intrusion detection system (IDS) capable of detecting network attacks.
The new genetic algorithm is tested against traditional and other modied ge- netic algorithms using common benchmark functions, and is found to produce better results in less time, and with less human interaction. The IDS is tested using the standard benchmark data collection for intrusion detection: the DARPA 98 KDD99 set. Results are found to be comparable to those achieved using ant colony optimiza- tion, and superior to those obtained with support vector machines and other genetic algorithms.
Sylvia Siu-Kei Tai, <tai@cs.queensu.ca>
M.Sc. Thesis: Relaying traffic with energy-delay constraints in wireless sensor networks
Energy is often considered the primary resource constraint in a wireless sensor network. Compared to sensing and data processing, data communication typically incurs the highest energy consumption. In this thesis, we study the problem of finding an optimal strategy for relaying traffic in a heterogeneous wireless sensor network such that the total energy spent on communication is minimized. The sought relaying strategy disallows traffic splitting, so data must be sent on a single path from the source to the destination. We consider the problem with respect to two types of network traffic, one with delay constraints - the Constrained Unsplittable Flow Allocation Problem (CUFA), and one without - the Unconstrained Unsplittable Flow Allocation Problem (UUFA). We present an integer linear programming formulation of problems UUFA and CUFA, and an alternate formulation based on an integer optimization technique known as 'branch-and-price' that can be used to solve relatively larger-sized problem instances to optimality, although both problems are NP-complete. The models and algorithms for solving problems UUFA and CUFA provide optimal solutions that can be used to study the impact on network resources of the best possible relaying strategy. Previous work in the literature has shown that relaying schemes which allow traffic to be split and relayed on multiple paths from the source to the destination can have several advantages, such as better load balancing. On the other hand, relaying schemes which relay data on a single path also have their advantages, for example, being less complex in design and having less overhead traffic. Based on the proposed models, an empirical study is performed to quantify the comparative performance gains and losses of relaying splittable and unsplittable traffic in a wireless sensor network when i) traffic is delay constrained and ii) traffic is not delay constrained. The results can provide insights into the effects of splitting traffic on the energy consumption and delay performance of wireless sensor networks.
Peter Taillon, <taillon@turing.scs.carleton.ca>
M.Sc. Thesis: The hypermesh multiprocessor network: architectural properties and algorithms
This thesis examines a recently proposed multiprocessor architecture called the hypermesh. A hypermesh can be modeled as a hypergraph with N = d^n nodes arranged in n-dimensional space such that along each dimension i, 0 <= i < n, there are d interconnected nodes. The high processor connectivity surpasses that of any of the enhanced mesh networks and rivals that of the popular hypercube network. With advances in optical communication technology this new network is now of great practical interest.
The thesis proposes new algorithms for the hypermesh showing that the high-interprocessor connectivity leads to asymptotically better algorithms. The computational problems selected are characterized by non-local communication patterns: broadcasting, prefix and semigroup computations, multiple searching and ranking, array compaction, matrix transpose, and dense and sparse matrix multiplication. The algorithms developed for these problems have complexities that compare favorably with equivalent solutions for the EREW PRAM and hypercube network.
Many researchers have studied the problem of routing in an optical network while limiting the number of wavelengths available for interprocessor communication. A practical variation of the hypermesh model is introduced that allows for efficient computation under the constraint of limited wavelength availability. Given a 2-dimensional hypermesh with N nodes, we consider the scenario where the number of wavelengths to which a transmitter/receiver can tune is some fixed integer b, where b << N^1/2. An efficient semigroup algorithm is introduced for this enhanced hypermesh, whose complexity compares favorably with those developed for two recently proposed mesh models that use separable row and column buses.
Hung Tam, <tam@cs.queensu.ca>
Ph.D. Thesis: Resource Management in Multi-hop Cellular Networks
In recent years, aided with the advancements in cellular technology, mobile communications have become affordable and popular. High cellular capacity in terms of number of users and data-rates is still in need. As the available frequency spectrums for mobile communications are limited, the utilization of the radio resources to achieve high capacity without imposing high equipment cost is of utmost importance. Recently, multi-hop cellular networks (MCNs) were introduced. These networks have the potential of enhancing the cell capacity and extending the cell coverage at low extra cost. However, in a cellular network, the cell or system capacity is inversely related to the cell size (the communication range of the base station). In MCNs, the cell size, the network density and topology affect the coverage of source nodes and the total demands that can be served and, thus, the radio resource utilization and system throughput. Although the cell size is an important factor, it has not been exploited. Another major issue in MCNs is the increase in packet delay because multi-hopping is involved. High packet delay affects quality of service provisioning in these networks.
In this thesis, we propose the Optimal Cell Size (OCS) and the Optimal Channel Assignment (OCA) schemes to address the cell size and packet delay issues for a time division duplex (TDD) wideband code division multiple access (W-CDMA) MCN. OCS finds the optimal cell sizes to provide an optimal balance of cell capacity and coverage to maximize the system throughput, whereas OCA assigns channels optimally in order to minimize packet relaying delay. Like many optimized schemes, OCS and OCA are computationally expensive and may not be suitable for large real-time problems. Hence, we also propose heuristics for solving the cell size and channel assignment problems. For the cell size problem, we propose two heuristics: Smallest Cell Size First (SCSF) and Highest Throughput Cell Size First (HTCSF). For the channel assignment problem, we propose the Minimum Slot Waiting First (MSWF) heuristic. Simulation results show that OCS achieves high throughput compared to that of conventional (single-hop) cellular networks and OCA achieves low packet delay in MCNs. Results also show that the heuristics, SCSF, HTCSF and MSWF, provide good approximation solutions compared to the optimal ones provided by OCS and OCA, respectively.
Sami Torbey, <torbey@cs.queensu.ca>
M.Sc. Thesis: Towards a framework for intuitive programming of cellular automata
The ability to obtain complex global behaviour from simple local rules makes cellular automata an interesting platform for massively parallel computation. However, manually designing a cellular automaton to perform a given computation can be extremely tedious, and automated design techniques such as genetic programming have their limitations because of the absence of human intuition. In this thesis, we propose elements of a framework whose goal is to make the manual synthesis of cellular automata rules exhibiting desired global characteristics more programmer-friendly, while maintaining the simplicity of local processing elements. We also demonstrate the power of that framework by using it to provide intuitive yet effective solutions to the two-dimensional majority classification problem, the convex hull of disconnected points problem, and various problems pertaining to node placement in wireless sensor networks.
Sami Torbey, <torbey@cs.queensu.ca>
Ph.D. Thesis: Beneath the surface electrocardiogram: computer algorithms for the non-invasive assessment of cardiac electrophysiology
The surface electrocardiogram (ECG) is a periodic signal portraying the electrical activity of the heart from the torso. The past fty years have witnessed a proliferation of computer algorithms destined for ECG analysis. Signal averaging is a noise reduction technique believed to enable the surface ECG to act as a non-invasive surrogate for cardiac electrophysiology.
The P wave and the QRS complex of the ECG respectively depict atrial and ventricular depolarization. QRS detection is a pre-requisite to P wave and QRS averaging. A novel algorithm for robust QRS detection in mice achieves a fourfold reduction in false detections compared to leading commercial software, while its human version boasts an error rate of just 0.29% on a public database containing ECGs with varying morphologies and degrees of noise.
A fully automated P wave and QRS averaging and onset/oet detection algorithm is also proposed. This approach is shown to predict atrial brillation, a common cardiac arrhythmia which could cause stroke or heart failure, from normal asymptomatic ECGs, with 93% sensitivity and 100% specicity. Automated signal averaging also proves to be slightly more reproducible in consecutive recordings than manual signal averaging performed by expert users.
Several studies postulated that high-frequency energy content in the signalaveraged QRS may be a marker of sudden cardiac death. Traditional frequency spectrum analysis techniques have failed to consistently validate this hypothesis.
Layered Symbolic Decomposition (LSD), a novel algorithmic time-scale analysis approach requiring no basis function assumptions, is presented. LSD proves more reproducible than state-of-the-art algorithms, and capable of predicting sudden cardiac death in the general population from the surface ECG with 97% sensitivity and 96% specificity.
A link between atrial refractory period and high-frequency energy content of the signal-averaged P wave is also considered, but neither LSD nor other algorithms nd a meaningful correlation.
LSD is not ECG-specic and may be ective in countless other signals with no known single basis function, such as other bio-potentials, geophysical signals, and socio-economic trends.
Tanya Wolff, <twolff@ca.ibm.com>
M.Sc. Thesis: Cayley networks: group, graph theoretic and algorithmic properties
This thesis explores the Cayley class of the interconnection model of parallel machines. A description of the general properties of the Cayley class, and a brief description of each of several types of Cayley networks are given. The representation of a group as a network of directed segments, where the vertices correspond to elements and the segments to multiplication by group generators and their inverses, was invented by Arthur Cayley, a nineteenth century mathematician. Such a network or graph is often called a Cayley diagram. We survey algorithms for routing, broadcasting, cycle decomposition, and embedding. Then we categorize these networks by group, and state for which types of Cayley graphs Hamilton Cycles are known to exist. Where possible algorithms for Hamilton Cycles are given. Sorting algorithms for the star are closely analyzed and two new algorithms are presented. One has the same running time as the fastest known algorithm as yet (O(n^3 log n)), and is elegant in its simplicity. The other is an adaptation of an algorithm for the multidimensional mesh and has a running time of O(n^2).
Return to Parallel Computation Group Home Page