Search

Digital Education Games (DEGs) have been used to support children's learning in various domains. A number of existing studies on DEGs has focused on whether they could improve children's learning performance. However, only a few of them have attempted to address the critical question of how young children interact with DEGs. Bridging this gap is the main motivation for my research work that contributed to the applied body of knowledge in Human-Computer Interaction, Game-Based Learning, and Educational Technology. With the use of state-of-the-art eye-tracking technology, especially its applicability for mobile devices, a better understanding of young children's focused attention and interaction strategies when learning with DEGs can be obtained. Methodologically, my research work demonstrates how eye-tracking methods can be applied with young users. For the empirical studies of this research work, a dedicated DEG and its Cardboard version serving as control were designed with reference to the UK Early Years Foundation Stage Framework on numeracy. The DEG was developed based on the literature on game-based learning and young children's attention span. To validate the learning effect of both versions of the game, the between-subject experimental design was employed and a paper-based knowledge test was created. The research protocols and instruments were pilot tested and were improved, especially the eye-tracking calibration process. In analysing the eye-tracking data, fixation duration was used as proxy for focused attention, and gaze sequences were used to infer interaction strategies with a refined Gaze Sub-sequence Marking Scheme. Overall, the empirical findings provided valuable groundwork and implication for future work. Specifically, a more child-friendly eye-tracker hardware design is required to facilitate data collection with children playing DEGs. Practical game design for 5-year-olds needs to consider different factors, including game duration, game difficulty, voice-based instructions and interactive non-player-character.

Cloud computing is an emerging Internet-based computing paradigm that aims to provide many on-demand services, requested nowadays by almost all online users. Although it greatly utilises virtualised environments for applications to be executed efficiently in low-cost hosting, it has turned energy wasting and overconsumption issues into major concerns. Many studies have projected that the energy consumption of cloud data-centres would grow significantly to reach 35% of the total energy consumed worldwide, threatening to further boost the world's energy crisis. Moreover, cloud infrastructure is built on a great amount of server equipment, including high performance computing (HPC), and the servers are naturally prone to failures. In this thesis, we study practically as well as theoretically the feasibility of optimising energy consumption in multi-cloud systems. We explore a deadline-based scheduling problem of executing HPC-applications by a heterogeneous set of clouds that are geographically distributed worldwide. We assume that these clouds participate in a federated approach. The practical part of the thesis has focused on combining two energy dimensions while scheduling HPC-applications (i.e., energy consumed for execution and data transmission). It has considered simultaneously minimising application rejections and deadline violations, to support resource reliability, with energy optimisation. In the theoretical part, we have presented the first online algorithms for the non-pre-emptive scheduling of jobs with agreeable deadlines on heterogeneous parallel processors. Through our developed simulation and experimental analysis using real parallel workloads from large-scale systems, the results evidenced that it is possible to reduce a considerable amount of energy while carefully scheduling cloud applications over a multi-cloud system. We have shown that our practical approaches provide promising energy savings with acceptable level of resource reliability. We believe that our scheduling approaches have particular importance in relation with the main aim of green cloud computing for the necessity of increasing energy efficiency.

The success of e-commerce applications and services depends on the outcomes of interactions between the provider of the products or services and its requestors. The flexibility of these agents to negotiate features of the products or services traded is an important characteristic of face-to-face business interactions, but is often missing in the online world. Flexibility is needed to discuss preferences and constraints in order to determine a solution that benefits both parties. Game theory is a natural framework in which to pose such problems. This thesis is concerned with a proposal-based negotiation: through which a service provider and requestor interact by exchanging proposals. In particular, we propose negotiation games based on feature models to design the flexible business interactions. Feature models are used to represent service configurations in order to support the variability of negotiated services, which increases the flexibility of the negotiators’ interactions. We introduce graph transformation games to implement and analyse our negotiation games, modelling the negotiation of features by representing the state of the game by a graph and the moves of the players by graph transformation rules. We propose two analyses of our graph transformation games in order to explore different negotiation strategies. Firstly, we analyse our graph transformation games as extensive-form games, in which backward induction technique is used to solve the game and determine the optimal strategies for the negotiators at each state of the game. Secondly, we analyse our graph transformation games as two-player turn-based stochastic games using the PRISM-games model checker. We define single-objective and multi-objective properties in order to generate optimal strategies for the players. To evaluate our approach, we applied it to a selection of feature models in order to test the scalability of the graph transformation games’ generation and analysis time.

This thesis is concerned with the analysis of best response dynamics in simultaneous and sequential network design games with fair-cost sharing, for both capacitated and uncapacitated networks. We address questions related to the evolution of stable states through selfish updates. First, we examine in general what effects such updates can have, from various perspectives, on the quality of the solutions to a game. From this, we move on to a more specific analysis of updates which begin from an optimal profile, providing insight to the price of stability measure of network efficiency, from the perspective of the user incurring the highest cost in the game. Finally, we investigate the process of updates beginning from an empty strategy profile, and make some observations about the quality of the resultant profile in such situations.

Wireless Mesh Networks (WMNs) are becoming common due to the features provided, especially the low cost and self-configuration ability. In WMNs, the data traffic is transmitted through intermediate nodes. With the nature of wireless networks, forwarding (routing) the data from the senders to the destinations and managing the network resources efficiently are challenging. There are various reasons that affect the network performance especially the throughput reduction such as signal interference, mobility and congestion. The focus of this research is to improve the throughput in the multi-channel wireless mesh networks from two perspectives. The first issue considered in this work is selecting a path with the maximum available bandwidth and low signal interference to transmit data from the source to the destination. Thus, we design two routing metrics, the Expected Transmission Time with Queueing (ETTQ) and the Delay and Interference Aware Metric (DIAM), that consider the intra-flow interference, inter-flow interference and delay. The simulation results of these routing metrics by the Network Simulator (NS2) demonstrate that the DIAM metric can estimate the intra-flow interference, inter-flow interference and delay of a link and then select the path efficiently. The second problem that has been addressed to improve the network throughput is controlling the network congestion. In this work, we address the issue of packet drops in the Interface Queue (IFQ) due to the node congestion. We solve this issue by reducing the number of dropped packets at IFQ by allocating the flow rate from the solution of a linear program (LP). The simulations using NS2 have shown that the LP-based flow rate improves the network throughput in chain networks. In addition, with the complex networks, traffic rate adjustments alone are not sufficient and we propose a simple forwarding delay scheme for the Ad Hoc On-Demand Distance Vector protocol with Forwarding delay (AODV-F) with DIAM routing metric that reduces node congestion and improves throughput. The forwarding delay scheme has also been evaluated using NS2. Moreover, the LP adjusted flow rate and the forwarding delay address the issue of maximising the flow fairness as the results have demonstrated.

Participatory Design (PD) is a common software development approach that actively includes end-users in the design process. This ensures tailored results and can lead to a strong feeling of ownership and overall empowers end-users. Commonly applied paper-based PD approaches have several shortcomings. A prototype presented on paper is not interactive for the end-user to experience it. Preparing PD ideas captured as physical artefacts (e.g. sketches on acetates) for further data analysis can be unduly time consuming. Using software tools to conduct PD activities instead of relying on paper-based methods can address these shortcomings. The author has been motivated to design, develop, and evaluate two such tools - PDotCapturer and PDotAnalyser. PDotCapturer is used by end-users participating in PD activities to create new designs from scratch or express (re-)design ideas. PDotAnalyser is used by designers to work with and further analyse the ideas captured. PDotCapturer is compared with similar paper-based approaches to evaluate the relative effectiveness of tool-based and paper-based PD activities in terms of quantity and quality of design ideas elicited. To perform this comparison, the coding scheme CAt+ (Categories plus Attributes) to rate the quality of PD ideas is developed. CAt+ can also be used to filter and aggregate PD ideas to support designers in making sense of as well as addressing such ideas for re-design. Results of the comparisons of paper-based and tool-based approaches show that paper is advantageous in some regards (e.g. number of ideas gathered), but the tool is comparable or in some regards outperforms paper (e.g. user preference). Given the additional advantages tool-usage can bring (e.g. automated analysis support), the context where paper-based or tool-based PD approaches suit better is discussed. For future work the use of PDotCapturer and PDotAnalyser in diverse and distributed settings will be explored.

Network design problems traditionally are modelled by a graph where each edge (or node) has a fixed cost. We investigate optimization problems in a realistic model for wireless network design called activation network. The activation network setting can be defined as follows. We are given a directed or undirected graph G = (V, E) together with a family {fuv : (u, v) E E} of monotone non-decreasing activation functions from D² to {0, 1}, where D is a constant-size subset of the non-negative real numbers, such that the activation of an edge depends on the chosen values from the domain D at its endpoints. An edge (u, v) E E is activated for chosen values xᵤ and xᵥ if fᵤᵥ(xᵤ, xᵥ) = 1, and the activation function fᵤᵥ is called monotone non-decreasing if fᵤᵥ (xᵤ, xᵥ) = 1 implies fᵤᵥ (yᵤ, yᵥ) = 1 for any yᵤ ≥ xᵤ, yᵥ ≥ xᵥ. The objective of activation network problems is to find activation values xᵥ E E for all v E V such that the total activation cost ∑ᵥEᵥ xᵥ is minimized and the activated set of edges satisfies some connectivity requirements. We give a 1:5-approximation algorithm for the minimum activation cost of k node-disjoint st-paths (st-MANDP) when k = 2. We also show that a p-approximation algorithm for the st-MANDP problem implies a p-approximation algorithm for solving the minimum activation cost of k edge-disjoint st-paths (st-MAEDP) problem when k = 2. We propose polynomial time algorithms that optimally solve the st-MANDP, st-MAEDP, minimum activation Steiner tree and the problem of finding minimum activation cost node-disjoint paths between k disjoint terminal pairs for graphs with treewidth bounded by a constant. We also study the st-MANDP, st-MAEDP, minimum spanning activation tree and minimum activation arborescence problems for the special case where |D| = 2 and all edges have the same activation function.

In the under uncertainty setting we study problems with imprecise input data for which precise data can be obtained. There exists an underlying problem with a feasible solution, but is computable only if the input is precise enough. We are interested in measuring how much of the imprecise input data has to be updated in order to be precise enough. We look at the problem for both the online and the offline (verification) cases. In the verification under uncertainty setting an algorithm is given imprecise input data and also an assumed set of precise input data. The aim of the algorithm is to update the smallest number of input data such that if the updated input data is the same as the corresponding assumed input data (i.e. verified), a solution for the underlying problem can be calculated. In the online adaptive under uncertainty setting the task is similar except the assumed set of precise data is not given to the algorithm, and the performance of the algorithm is measured by comparing the number of input data that have been updated against the result obtained in the verification setting of the same problem. We have studied these settings for a few geometric and graph problems and found interesting results. Geometric problems include several variations of the maximal points problem where, in its classical form, given a set of points in the plane we want to compute the set of all points that are maximal. The uncertain element here is the actual location of each point. Graph problems include a few variations of the graph diameter problem where, in its classical form, given a graph we want to calculate a farthest pair of vertices. The uncertain element is the weight of each edge.

This thesis is principally concerned with effcient energy consumption in wireless sensor networks from two distinct aspects from a theoretical point of view. The thesis addresses the issue of reducing idle listening states in a restricted tree topology to minimise energy consumption by proposing an optimisation technique: the extra-bit technique. This thesis also focuses on showing lower bounds on the optimal schedule length, which are derived for some special cases of the tree, such as a single chain, balanced chains, imbalanced chains, three and four level k-ary trees and Rhizome trees. Then, we propose an algorithm which can exactly match the lower bound for a single chain, balanced chains and Rhizome trees individually and which is a few steps away from the optimal solution for imbalanced chains. Finally, we propose the use of two frequencies to further save energy and minimize latency. Recent research has shown that significant energy improvements can be achieved in WSNs by exploiting a mobile sink for data collection via single hop communications. A mobile sink approaches the transmission range of sensors to receive their data and deposit the data at the base station. The thesis, as a second problem, focuses on the design issues of an energy efficient restricted tour construction for sink mobility. We propose two different techniques. The first one is heuristic and uses a criterion based on maximum coverage and minimum energy consumption called the "max-ratio". Although its time complexity is polynomial, this heuristic algorithm cannot always produce a good solution. As a result, we propose the sec- ond algorithm. Despite the time complexity of the second algorithm being pseudo polynomial, the optimal solution can be found if one exists. For each algorithm men- tioned, two scenarios are taken into account with regard to the transmission. In the first scenario, one assumes that there is no upper bound on the transmission range while in the second setting the nodes can adjust their transmission range between 0 and the maximum range. The algorithms have been implemented and simulated in Matlab.

In this thesis we will address four problems concerned with algorithmic issues that arise from communication and sensor networks. The problem of scheduling wireless transmissions under SINR constraints has received much attention for unicast (one to one) transmissions. We consider the scheduling problem for multicast requests of one sender to many receivers, and present a logarithmic approximation algorithm and an online lower bound for arbitrary power assignments. We study the problem of maximising the lifetime of a sensor network for fault-tolerant target coverage in a setting with composite events, where a composite event is the simultaneous occurrence of one or more atomic events. We are the first to study this variation of the problem from a theoretical perspective, where each event must be covered twice and there are several event types, and we present a (6 + ɛ)-approximation algorithm for the problem. The online strongly connected dominating set problem concerns the construction of a dominating set that is strongly connected at all times, and for every vertex not in the dominating set, there exists an edge to some vertex in the dominating set, and an edge from a vertex in the dominating set. We present a lower bound for deterministic online algorithms and present an algorithm that achieves competitive ratio matching the lower bound. The monotone barrier resilience problem is to determine how many sensors must be removed from a sensor network, such that a monotone path can exist between two points that does not intersect any sensor. We present a polynomial time algorithm that can determine the monotone barrier resilience for sensor networks of convex pseudo-disks of equal width.

Broadcasting, coverage, duty cycling, and capacity improvement are some of the important areas of interest in Wireless Networks. We address different problems related with broadcasting, duty cycling, and capacity improvement by sensing different network conditions and dynamically adapting to them. We propose two cross layer broadcasting protocols called CASBA and CMAB which dynamically adapt to network conditions of congestion and mobility. We also propose a broadcasting protocol called DASBA which dynamically adapts to local node density. CASBA, CMAB, and DASBA improve the reachability while minimizing the broadcast cost. Duty cycling is an efficient mechanism to conserve energy in Wireless Sensor Networks (WSNs). Existing duty cycling techniques are unable to handle the contention under dynamic traffic loads. Our proposed protocol called SA-RI-MAC handles traffic contention much more efficiently than RI-MAC without sacrificing the energy efficiency. It improves the delivery ratio with a significant reduction in the latency and energy consumption. Due to limited battery life and fault tolerance issues posed by WSNs, efficient methods which ensure reliable coverage are highly desirable. One solution is to use disjoint set covers to cover the targets. We formulate a problem called MDC which addresses the maximum coverage by using disjoint set covers S1 and S2. We prove that MDC is NP-complete and propose a √n-approximation algorithm for the MDC problem to cover n targets. The use of multi-channel MAC protocols improves the capacity of wireless networks. Efficient multi-channel MAC protocols aim to utilize multiple channels effectively. Our proposed multi-channel MAC protocol called LCV-MMAC effectively utilizes the multiple channels by handling the control channel saturation. LCV-MMAC demonstrates significantly better throughput and fairness compared to DCA, MMAC, and AMCP in different network scenarios.

The ant colony optimization (ACO) metaheuristic is inspired by the foraging behaviour of real ant colonies. Similarly with other metaheuristics, ACO suffers from stagnation behaviour, where all ants construct the same solution from early stages. In result, the solution quality may be degraded because the population may get trapped on local optima. In this thesis, we propose a novel approach, called direct communication (DC) scheme, that helps ACO algorithms to escape from a local optimum if they get trapped. The experimental results on two routing problems showed that the DC scheme is effective. Usually, researchers are focused on problems in which they have static environment. In the last decade, there is a growing interest to apply nature-inspired metaheuristics in optimization problems with dynamic environments. Usually, dynamic optimization problems (DOPs) are addressed using evolutionary algorithms. In this thesis, we apply several novel ACO algorithms in two routing DOPs. The proposed ACO algorithms are integrated with immigrants schemes in which immigrant ants are generated, either randomly or with the use of knowledge from previous environment(s), and replace other ants in the current population. The experimental results showed that each proposed algorithm performs better in different dynamic cases, and that they have better performance than other peer ACO algorithms in general. The existing benchmark generators for DOPs are developed for binary-encoded combinatorial problems. Since routing problems are usually permutation-encoded combinatorial problems, the dynamic environments used in the experiments are generated using a novel benchmark generator that converts a static problem instance to a dynamic one. The specific dynamic benchmark generator changes the fitness landscape of the problem, which causes the optimum to change in every environmental change. Furthermore in this thesis, another benchmark generator is proposed which moves the population to another location in the fitness landscape, instead of modifying it. In this way, the optimum is known and one can see how close to the optimum an algorithm performs during the environmental changes.

Simulation tools are primary means for evaluating and analysing performance of Mobile Adhoc NETworks (MANETS). Different mobility and propagation models have been used in this context. However, simple propagation models have been used heavily in simulation based MANETS routing performance analysis. A range of propagation models (such as ITU-R P.1411-5, ITU-R P1238-6, GOA-LoS, modified TRG, C-Shadowing and WINNER) for various indoor/outdoor and LoS/NLoS scenarios have been added into ns-2 based simulation and results have been analysed with those readily available in the simulator for AODV, DSR and OLSR routing protocols. A variety of synthetic mobility models have been implemented under those pathloss conditions and their impact on routing performance has been observed. Heterogeneous mobility conditions have been introduced for performance analysis of AODV and DSR routing protocols under, TRG, ITU and GOA pathloss conditions. It has been found that the DSR protocol fails to perform where AODV prevails in specific mobility environment. RPGM model have been analysed with variations of mobility model adopted by group-heads and its impact on MANETS have been investigated. A very large adhoc network has been tested through ns-2 simulator with comparison of ITU and TRG channel loss conditions and its results have been compared with other scalable routing performance analysis studies. Impact of corner-loss effects due to typical street movement scenario such as under MG mobility have been experimented through ITU-R based recommendations in ns-2 simulation environment. A small testbed based AODV performance analysis has been compared with ns-2 based simulation results under ITU and Shadowing propagation models and significant difference have been recorded in real vs simulation based results for NRL and Mean. Delay analysis. In summary, MANET performance have been analysed under a range of operational conditions and applications and it has been demonstrated that various factors such as mobility and propagation environment could significantly challenge the deployment of such networks.

The Grid has enabled the scientific community to make faster progress. Scientific experiments and data analyses once spanning several years can now be completed in a matter of hours. With the advancement of technology, the execution of scientific experiments, often represented as workflows, has become more demanding. Thus, there is a vital need for improvements in the scheduling of scientific workflows. Efficient execution of scientific workflows can be achieved by the timely allocation of the resources. Advance reservation can ensure the future availability of heterogeneous resources and help a scheduler to produce better schedules. We propose a novel resource mapping technique for jobs of a Grid workflow in an advance reservation environment. Using a dynamic critical path based job selection method, our proposed technique considers the conditional mapping of parent and child jobs to the same resource, trying to minimise the communication duration between jobs and thus optimising the workflow completion time. The proposed method is analysed in both static and dynamic environments, and the simulation results show encouraging performance especially for workflows where the communication costs are higher than the computation costs. We also propose a hybrid of multiple scheduling heuristics for the aforementioned problem, which chooses the best among multiple schedules computed by different algorithms. Simulation results show a significant improvement over well known scheduling heuristics in terms of workflow completion time. Considering the advance reservation environment, a better schedule for the earliest completion of a workflow can be achieved if better paths can be found for the transfer of data files between jobs executed on different resources. We propose a K-shortest path based routing algorithm for finding good paths in the advance reservation environment. The results show that our proposed algorithm performs very well in terms of the earliest arrival time of the data. Finally, we also study a modified partner based scheduling heuristic for non-advance reservation environments. The results demonstrate that our proposed algorithm is a promising candidate for adoption in such Grid environments.

The university course timetabling problem is a difficult optimisation problem due to its highly-constrained nature. Finding an optimal, or even a high quality, timetable is a challenging task, especially when resources (e.g., rooms and time slots) are limited. In the literature, many approaches have been studied to solve this problem. In this thesis, we investigate genetic algorithms to solve the problem because they have been successfully used for a wide range of real-world problems. However, for university course timetabling problems, traditional genetic algorithms are not usually considered as efficient solvers. In this thesis, we investigate genetic algorithms to acquire good solutions for university course timetabling problems. Several ideas are introduced to increase the general performance of genetic algorithms on these problems. Local search strategies are introduced into the traditional genetic algorithm to enhance its performance for the university course timetabling problem. This differs from many works in the literature because it works on time slots of the timetable rather than events directly. A guided search approach is also introduced into genetic algorithms to produce high quality individuals into the population. In the guided search technique, the best parts of selected individuals from the current population are stored in an extra memory (or data structure) and are re-used to guide the generation of new individuals for subsequent populations. In addition to solving university course timetabling problems as a single-objective optimisation problem, we also tackle the multi-objective university course timetabling problem. We integrate the above proposed approaches into multi-objective evolutionary algorithms and propose a framework of multi-objective evolutionary algorithms based on local search and guided search strategies for the multi-objective university course timetabling problem. This framework is then instantiated into a set of multi-objective evolutionary algorithms for the multi-objective university course timetabling problem based on a set of multi-objective evolutionary algorithms that are typically used for general multi-objective optimisation problems. Computational results based on a set of well-known university course timetabling benchmark instances, show the effectiveness of the proposed approaches for both single- and multi-objective university course timetabling problems.

We are motivated by the problem of computing multicast routing structures in wireless ad-hoc networks modelled by special classes of graphs including unit disk graphs, quasi-unit disk graphs and (λ + 1)-claw-free graphs. Multicast communication can be established by a tree known as Steiner tree. Wireless ad-hoc networks must operate using limited resources, therefore, the suitability of nodes for inclusion in a Steiner tree can vary widely between different nodes. We model this by assuming that each node of the network is assigned a weight that represents the cost of including it in the Steiner tree. Our goal is to compute a Steiner tree with minimum total node weight. However, in scenarios where nodes and links are not reliable, a tree has the drawback that it can be disconnected by the failure of even a single link or node in the network. Therefore, we also consider various fault-tolerant routing structures called 2-edge-connected Steiner subgraphs, k-edge-connected Steiner subgraphs, 2-vertex-connected Steiner subgraphs, and 2-edge-connected group Steiner subgraphs. The problems we consider are NP-hard, so we are interested in algorithms that compute provably good approximate solutions in polynomial time. We present a generalization of Steiner subgraph problems referred to as the node-weighted δ-Steiner subgraph problem, where δ represents connectivity requirements. We present an algorithm with approximation ratio 0.5dρ for the node-weighted δ-Steiner subgraph problem, where d is the bounded maximum degree of the solution subgraph, and ρ is the approximation ratio of the edge-weighted version of the δ-Steiner subgraph problem. We then shown how to construct solution subgraphs of bounded maximum degree d in several graph classes for our problem variants. As a result, we obtain algorithms for the problems we consider, on graph classes that admit subgraphs of small degree, whose approximation ratios are better than the best known ratios for the same problems on general graphs.