Wireless sensor networks research in the past decade has seen substantial initiative,support and potential. The true adoption and deployment of such technology is highly dependent on the workforce available to implement such solutions. However, embedded systems programming for severely resource constrained devices, such as those used in typical wireless sensor networks (with tens of kilobytes of program space and around ten kilobytes of memory), is a daunting task which is usually left for experienced embedded developers. Recent initiative to support higher level programming abstractions for wireless sensor networks by utilizing a Java programming paradigm for resource constrained devices demonstrates the development benefits achieved. However, results have shown that an interpreter approach greatly suffers from execution overheads. Run-time compilation techniques are often used in traditional computing to make up for such execution overheads. However, the general consensus in the field is that run-time compilation techniques are either impractical, impossible, complex, or resource hungry for such resource limited devices. In this thesis, I propose techniques to enable run-time compilation for such severely resource constrained devices. More so, I show not only that run-time compilation is in fact both practical and possible by using simple techniques which do not require any more resources than that of interpreters, but also that run-time compilation substantially increases execution efficiency when compared to an interpreter.

Inspired by the network information theory, network coding was invented in 2000. Since then, the theory and application of network coding have received intensive research and various network coding schemes have been proposed and studied. It has been demonstrated that the packetlevel network coding has the potential to outperform the traditional routing strategies in packet networks. By taking the advantages of the information carried by the packets sent to different receivers (sinks) in a packet network, packet-level network coding is capable of reducing the number of packets transmitted over the network. Therefore, the packet-level network coding employs the potential for boosting the throughput of packet networks. By contrast, the symbollevel network coding, which is also referred to as the physical-layer network coding, is capable of exploiting interference instead of avoiding it for improving the channel capacity and/or enhancing the reliability of communications. In this thesis, our focus is on the packet-level network coding. Performance of communication systems with network coding has been widely investigated from different perspectives, mainly under the assumption that packets are reliably transmitted over networks without errors. However, in practical communication networks, transmission errors always occur and error-detection or error-correction techniques are required in order to ensure reliable communications. Therefore, in this report, we focus our attention mainly on studying the performance of the communication networks with packet-level network coding, where Automatic Retransmission reQuest (ARQ) schemes are employed for error protection. Three typical ARQ schemes are invoked in our research, which are the Stop-and-Wait ARQ (SW-ARQ), Go-Back-N ARQ (GBN-ARQ) and the Selective-Repeat ARQ (SR-ARQ). Our main concern is the impact of network coding on the throughput performance of network coding nodes or networks containing network coding nodes. Additionally, the impact of network coding on the delay performance of network coding nodes or coded networks is also addressed. In a little more detail, in Chapter 3 of the thesis, we investigate the performance of the netvi works employing packet-level network coding, when assuming that transmission from one node to another is not ideal and that a certain ARQ scheme is employed for error-control. Specifically, the delay characteristics of general network coding node are first analyzed. Our studies show that, when a coding node invokes more incoming links, the average delay for successfully forming coded packets increases. Then, the delay performance of the Butterfly networks is investigated, which shows that the delay generated by a Butterfly network is dominated by the communication path containing the network coding node. Finally, the performance of the Butterfly network is investigated by simulation approaches, when the Butterfly network employs SW-ARQ, GBN-ARQ, or SR-ARQ for error-control. The achievable throughput, the average delay as well as the standard deviation of the delay are considered. Our performance results show that, when given a packet error rate Packet Error Rate (PER), the SR-ARQ scheme is capable of attaining the highest throughput and resulting in the lowest delay among these three ARQ schemes. In Chapter 4, the steady-state throughput of general network coding nodes is investigated, when the SW-ARQ scheme is employed. We start with considering a Two-Input-Single-Output (2ISO) network coding node without queueing buffers. Expressions for computing the steady-state throughput is derived. Then, we extend our analysis to the general H-Input-Single-Output (HISO) network coding nodes without queueing buffers. Finally, our analytical approaches are further extended to the HISO network coding nodes with queueing buffers. A range of expressions for evaluating the steady-state throughput are obtained. The throughout performance of the HISO network coding nodes is investigated by both analytical and simulation approaches. Our studies in this chapter show that the throughput of a network coding node decreases, as the number of its incoming links increases. This property implies that, in a network coding system, the coding nodes may form the bottlenecks for information delivery. Furthermore, the studies show that adding buffers to the network coding node may improve the throughput performance of a network coding system. Then, in Chapters 5 and 6, we investigate the steady-state throughput performance of the general network coding nodes, when the GBN-ARQ in Chapter 5 or the SR-ARQ in Chapter 6 is employed. Again, analytical approaches for evaluating the steady-state throughput of the general network coding nodes are concerned and a range of analytical results are obtained. Furthermore, the throughput performance of the network coding nodes supported by the GBN-ARQ or SR-ARQ is investigated by both simulations and numerical approaches. Finally, in Chapter 7, the conclusions extracted from the research are summarized and the possible directions for future research are proposed.

In this thesis, we propose a series of cross-layer aided routing algorithms for ad hocnetworks by jointly exploiting the characteristics of the physical layer, of the data link layer and of the network layer, for the sake of improving the network's throughput, while reducing the normalized energy consumption. Since the node mobility in dynamic self organizing ad hoc networks may render the routing information gathered during the route discovery process invalid and hence may disrupt the current data transmission, a fuzzy logic aided technique is incorporated into the routing algorithm for mitigating the influence of imprecise routing information. Both the expected route life time and the number of hops are used as the input parameters of the Fuzzy Logic System (FLS), which outputs the `stability' of a route. Hence, the specific route having the highest route `stability' is finally selected for data transmission. The proposed fuzzy logic based routing outperforms the conventional Dynamic Source Routing (DSR) in terms of the attainable network throughput. Moreover, since near-capacity channel coding aided Multiple Input Multiple- Output (MIMO) schemes allow a single link to communicate using the lowest possible transmit power at a given Frame Error Rate (FER), multi antenna aided routing was proposed for reducing the system's total energy consumption, which relied on a three-stage concatenated transceiver constituted by an Irregular Convolutional Code, Unity-Rate Code and Space-Time Trellis Code (IrCC-URC-STTC) equipped with two antennas. It is demonstrated that in a high-node-density scenario the average energy consumption per information bit and per node becomes about a factor two lower than that in the equivalent Single-Antenna Relay Node (SA-RNs) aided networks. Finally, we further exploit the benefits of cross-layer information exchange, including the knowledge of the FER in the physical layer, the maximum number of retransmissions in the data link layer and the number of RNs in the network layer. Energy-consumption-based Objective Functions (OF) are invoked for calculating the end-to-end energy consumption of each potentially available route for both Traditional Routing (TR) and for Opportunistic Routing (OR), respectively. We also improve the TR and the OR with the aid of efficient Power Allocation (PA) for further reducing the energy consumption. Moreover, two energy-efficient routing algorithms are designed based on Dijkstra's algorithm. The algorithms based on the energy-consumption OF provide the theoretical bounds, which are shown to be close to the bound found by exhaustive search, despite the significantly reduced complexity of the former. Finally,the end-to-end throughput and the end-to-end delay of this system are analyzed theoretically. The simulation results show that our energy-efficient OR outperforms the TR and that their theoretical analysis accurately matches the simulation results.

Recent advances in information and communications technology have led to a surge in the popularity of artificial Collective Adaptive Systems (CAS). Such systems, comprised by many spatially distributed autonomous entities with decentralised control, can often achieve discernible characteristics at the global level; a phenomenon sometimes termed emergence. Examples include smart transport systems, smart electricity power grids, robot swarms, etc. The design and operational management of CAS are of vital importance because different configurations of CAS may exhibit very large variability in their performance and the quality of services they offer. However, due to their complexity caused by varying degrees of behaviour, large system scale and highly distributed nature, it is often very difficult to understand and predict the behaviour of CAS under different situations. Novel modelling and quantitative analysis methodologies are therefore required to address the challenges posed by the complexity of such systems. In this thesis, we develop a process algebraic modelling formalism that can be used to express complex dynamic behaviour of CAS and provide fast and scalable analysis techniques to investigate the dynamic behaviour and support the design and operational management of such systems. The major contributions of this thesis are: (i) development of a novel high-level formalism, PALOMA, the Process Algebra for Located Markovian Agents for the modelling of CAS. CAS specified in PALOMA can be automatically translated to their underlying mathematical models called Population Continuous-Time Markov Chains (PCTMCs). (ii) development of an automatic moment-closure approximation method which can provide rapid Ordinary Differential Equation-based analysis of PALOMA models. (iii) development of an automatic model reduction algorithm for the speed up of stochastic simulation of PALOMA/PCTMC models. (iv) presenting a case study, predicting bike availability in stations of Santander Cycles, the public bike-sharing system in London, to show that our techniques are well-suited for analysing real CAS.

Recently, the advances in Ubiquitous Computing networks and the increased computational power of network devices have led designers to create more flexible distributed network models using decentralised network management systems. Security, resilience and privacy issues within such distributed systems become more complicated while important tasks such as routing, service access and state management become increasingly challenging. Low-level protocols over ubiquitous decentralised systems, which provide autonomy to network nodes, have replaced the traditional client-server arrangements in centralised systems. Small World networks represent a model that addresses many existing challenges within Ubiquitous Computing networks. Therefore, it is imperative to study the properties of Small World networks to help understanding, modelling and improving the performance, usability and resiliency of Ubiquitous Computing networks. Using the network infrastructure and trusted relationships in the Small World networks, this work proposes a framework to enhance security, resilience and trust within scalable Peer-to-Peer (P2P) networks. The proposed framework consists of three major components namely network-aware topology construction, anonymous global communication using community trust, and efficient search and broadcasting based on granularity and pro-active membership management. We utilise the clustering co-efficient and conditional preferential attachment to propose a novel topology construction scheme that organises nodes into groups of trusted users to improve scalability. Network nodes communicate locally without advertising node identity at a global scale, which ensures user anonymity. The global communication is organised and facilitated by Service Centres to maintain security, privacy and integrity of member nodes. Service Centres are allocated using a novel leader election mechanism within unstructured scalable P2P networks. This allows providing fair and equitable access for existing and new nodes without having to make complex changes to the network topology. Moreover, the scale-free and clustering co-efficient characteristics of Small World networks help organising the network layout to maintain its balance in terms of the nodes distribution. Simulation results show that the proposed framework ensures better scalability and membership management in unstructured P2P networks, and improves the performance of the search and broadcasting in terms of the average shortest path and control overhead while maintaining user anonymity and system resiliency.

In today’s distributed applications, replica placement is essential since moving the data in the vicinity of an application will provide many benefits. The increasing requirements of data for scientific applications and collaborative access to these data make data placement even more important. Until now, replication is one of the main mechanisms used in distributed data whereby identical copies of data are generated and stored at various distributed sites to improve data access performance and data availability. Most work considers file’s popularity as one of the important parameters taken into consideration when designing replica placement strategies. However, this thesis argues that a combination of popularity and affinity files are the most important parameters which can be used in decision making whilst improving data access performance and data availability in distributed environments. A replica placement mechanism called Affinity Replica Placement Mechanism (ARPM) is proposed focusing on popular files and affinity files. The idea of ARPM is to improve data availability and accessibility in peer-to-peer (P2P) replica placement strategy. A P2P simulator, PeerSim, was used to evaluate the performance of this dynamic replica placement strategy. The simulation results demonstrated the effectiveness of ARPM hence provided a proof that ARPM has contributed towards a new dimension of replica placement strategy that incorporates the affinity and popularity of files replicas in P2P systems.

Quality of service in local area networks is becoming more and more important, since bandwidth intensive applications are increasing in modern households, but the infrastructure is often limited. State of the art research and standardisation knows of QoS technologies targeting QoS in consumer networks, but these often require deployment on all devices, are limited to certain access technology or lack autonomous configuration support. This thesis presents a novel approach to Quality of Service in unmanaged Local Area Networks, called the QoSiLAN framework. It does not rely on network infrastructure support, but on host cooperation. It identifies traffic with a QoS demand and predicts the required resources to enable per-link bandwidth reservations in an autonomous manner. In contrast to traditional approaches, the bandwidth reservation is not realised explicitly by infrastructure support, but implicitly by host cooperation. This works by involving cooperating hosts, which limit their bandwidth output to not over-provision links with active QoS reservations in the network, while a full device coverage is not required essentially. The resource management and admission control is coordinated by a dedicated QoSiLAN Manager host, which also maintains a detailed link layer network topology map to make sophisticated resource policing admissions on link basis. To enable the QoSiLAN framework, this Thesis contributes the framework as well as new knowledge to the enabler technologies for traffic identification, resource prediction, topology mapping, policing and admission control as well as a dedicated QoS signalling communication protocol.

Wireless networks are increasingly used within pervasive computing. The recent development of low-cost sensors coupled with the decline in prices of embedded hardware and improvements in low-power low-rate wireless networks has made them ubiquitous. The sensors are becoming smaller and smarter enabling them to be embedded inside tiny hardware. They are already being used in various areas such as health care, industrial automation and environment monitoring. Thus, the data to be communicated can include room temperature, heart beat, user’s activities or seismic events. Such networks have been deployed in wide range areas and various levels of scale. The deployment can include only a couple of sensors inside human body or hundreds of sensors monitoring the environment. The sensors are capable of generating a huge amount of information when data is sensed regularly. The information has to be communicated to a central node in the sensor network or to the Internet. The sensor may be connected directly to the central node but it may also be connected via other sensor nodes acting as intermediate routers/forwarders. The bandwidth of a typical wireless sensor network is already small and the use of forwarders to pass the data to the central node decreases the network capacity even further. Wireless networks consist of high packet loss ratio along with the low network bandwidth. The data transfer time from the sensor nodes to the central node increases with network size. Thus it becomes challenging to regularly communicate the sensed data especially when the network grows in size. Due to this problem, it is very difficult to create a scalable sensor network which can regularly communicate sensor data. The problem can be tackled either by improving the available network bandwidth or by reducing the amount of data communicated in the network. It is not possible to improve the network bandwidth as power limitation on the devices restricts the use of faster network standards. Also it is not acceptable to reduce the quality of the sensed data leading to loss of information before communication. However the data can be modified without losing any information using compression techniques and the processing power of embedded devices are improving to make it possible. In this research, the challenges and impacts of data compression on embedded devices is studied with an aim to improve the network performance and the scalability of sensor networks. In order to evaluate this, firstly messaging protocols which are suitable for embedded devices are studied and a messaging model to communicate sensor data is determined. Then data compression techniques which can be implemented on devices with limited resources and are suitable to compress typical sensor data are studied. Although compression can reduce the amount of data to be communicated over a wireless network, the time and energy costs of the process must be considered to justify the benefits. In other words, the combined compression and data transfer time must also be smaller than the uncompressed data transfer time. Also the compression and data transfer process must consume less energy than the uncompressed data transfer process. The network communication is known to be more expensive than the on-device computation in terms of energy consumption. A data sharing system is created to study the time and energy consumption trade-off of compression techniques. A mathematical model is also used to study the impact of compression on the overall network performance of various scale of sensor networks.

This thesis investigates the problem of scheduling and routing employees that are required to perform activities at clients’ locations. Clients request the activities to be performed during a time period. Employees are required to have the skills and qualifications necessary to perform their designated activities. The working time of employees must be respected. Activities could require more than one employee. Additionally, an activity might have time-dependent constraints with other activities. Time-dependent activities constraints include: synchronisation, when two activities need to start at the same time; overlap, if at any time two activities are being performed simultaneously; and with a time difference between the start of the two activities. Such time difference can be given as a minimum time difference, maximum time difference, or a combination of both (min-max). The applicability of such workforce scheduling and routing problem (WSRP) is found in many industries e.g. home health care provision, midwives visiting future mothers, technicians performing installations and repairs, estate agents showing residences for sale, security guards patrolling different locations, etc. Such diversity makes the WSRP an important combinatorial optimisation problem to study. Five data sets, obtained from the literature, were normalised and used to investigate the problem. A total of 375 instances were derived from these data sets. Two mathematical models, an integer and a mixed integer, are used. The integer model does not consider the case when the number of employees is not enough to perform all activities. The mixed integer model can leave activities unassigned. A mathematical solver is used to obtain feasible solutions for the instances. The solver provides optimal solutions for small instances, but it cannot provide feasible solutions for medium and large instances. This thesis presents the gradual development of a greedy heuristic that is designed to tackle medium and large instances. Five versions of the greedy heuristic are presented, each of them obtains better results than the previous one. All versions are compared to the results obtained by the mathematical solver when using the mixed integer model. The greedy heuristic exploits domain information to speed the search and discard infeasible solutions. It uses tailored functions to deal with each of the time-dependent activity constraints. These constraints make more difficult the solution process. Further improvements are obtained by using tabu search. It provides moves based on the tailored functions of the greedy heuristic. Overall, the greedy heuristic and the tabu search, maintain feasible solutions at all times. The main contributions of this thesis are: the definition of WSRP; the introduction of 375 instances based on five data sets; the adaptation of two mathematical models; the introduction of a greedy heuristic capable of obtaining better results than the solver; and, the implementation of a tabu search to further improve the results.

Vehicular networking has gained considerable interest within the research community and industry. This class of mobile ad hoc network expects to play a vital role in the design and deployment of intelligent transportation systems. The research community expects to launch several innovative applications over Vehicular Ad hoc Networks (VANETs). The automotive industry is supporting the notion of pervasive connectivity by agreeing to equip vehicles with devices required for vehicular ad hoc networking. Equipped with these devices, mobile nodes in VANETs are capable of hosting many types of applications as services for other nodes in the network. These applications or services are classified as safety-critical (failure or unavailability of which may lead to a life threat) and non-safety-critical (failure of which do not lead to a life threat). Safety-critical and non-safety-critical applications need to be supported concurrently within VANETs. This research covers non-safety-critical applications since the research community has overlooked this class of applications. More specifically, this research focuses on VANETs services that are location-dependent. Due to high speed mobility, VANETs are prone to intermittent network connectivity. It is therefore envisioned that location-dependence and intermittent network connectivity are the two major challenges for VANETs to host and operate non-safety-critical VANETs services. The challenges are further exacerbated when the area where the services are to be deployed is unplanned i.e. lacks communication infrastructure and planning. Unplanned areas show irregular vehicular traffic on the road. Either network traffic flows produced by irregular vehicular traffic may lead to VANETs communication channel congestion, or it may leave the communication channel under-utilized. In both cases, this leads to communication bottlenecks within VANETs. This dissertation investigates the shortcomings of location-dependence, intermittent network connectivity and irregular network traffic flows and addresses them by exploiting location-dependent service migration over an integrated network in an efficient and cost-effective manner.