Routing is the fundamental problem for Wireless Ad hoc networks, including Wireless Mobile Ad hoc networks (MANETs) and Wireless Sensor networks (WSNs). Although the problem has been extensively studied in the past decade, the existing solutions have deficiencies in one or more aspects including efficiency, scalability, robustness, complexity, etc.This dissertation proposes several new solutions for routing in WSNs and MANETs. Spiral is a data-centric routing algorithm for short-term communication in unstructured static WSNs. Spiral is a biased walk that visits nodes near the source before more distant nodes. This results in a spiral-like search path that is not only more likely to find a closer copy of the desired data than random walk, but is also able to compute a shorter route because the network around the source is more thoroughly explored. Compared with existing flooding and random walk approaches, Spiral has a lower search cost than flooding and returns better routes than random walk.Closest Neighbor First Search (CNFS) is a query processing algorithm for mobile wireless sensor networks. It is also walk-based and biased to visit nodes close to the source first. Different from Spiral, CNFS collects topology information as the search progresses. The topology information is used to compute the shortest return path for the query result and to tolerate the network topology changes caused by node mobility, which could otherwise cause the query to fail. CNFS requires fewer messages to process a query than flooding-based algorithms, while tolerating node mobility better than random walk-based algorithms.Address Aggregation-based Routing (AAR) is a novel routing protocol designed for MANETs. It reactively performs route discovery, but proactively maintains an index hierarchy called a Route Discovery DAG (RDD) to make route discovery efficient. The RDD contains aggregated node address information, requiring fewer packets for route discovery than the flooding used in existing protocols, while handling mobility better than pre-computing routes to all nodes. Compared with some existing popular protocols, AAR shows better performance in delivery rate, message overhead, latency and scalability.

The Internet of Things (IoT) represents a networking paradigm where entities are viewed as objects that are identifiable, traceable and connected. This view requires the integration and interoperability of numerous wireless standards. Radio Frequency Identification (RFID) systems and Wireless Sensor Networks (WSNs) are two dominant technologies that jointly constitute a class of hybrid/integrated IoT architectures known as RFID-Sensor Networks (RSNs). Data delivery across such integrated architectures faces challenges in terms of cost-efficiency, scalability and connectivity, among many others. Moreover, IoT-driven solutions are required to address constraints on node mobility, delay-tolerance and resource management, and may have to adhere to an economic model in order to establish incentive-based schemes. Most available RSN solutions are tailored for a single-application and fail to address the aforementioned IoT constraints. To the best of our knowledge, a detailed framework that comprehensively addresses such constraints does not exist. We investigate this promising research direction by proposing a novel framework that incorporates an RSN integrated architecture to improve delivery over heterogeneous topologies. Our framework provides data delivery solutions that adhere to delivery and connectivity considerations of integrated RSN architectures in IoT. Moreover, our data delivery solutions incorporate pricing policies for incentive public sensing applications over the proposed architecture. We show, by theoretical analysis and simulations, that our framework outperforms rival RSN integration approaches, as well as other wireless Ad-hoc data delivery schemes in realizing IoT performance requirements. / Thesis (Ph.D, Computing) -- Queen's University, 2013-05-01 15:09:52.668

As the primary military operating environment shifts from the traditional battlefields to a more diverse urban environment, the use of remote wireless sensors is increasing. Traditional development and procurement methods are not capable of meeting the changing requirements and time constraints of commanders. To minimize the time to develop and deploy new systems, commercial solutions must be examined. The focus of this thesis is on the integration of Commercial Off-the-Shelf (COTS) components into a wireless multimedia sensor network. Because components from multiple vendors were utilized, different operating systems and transmission protocols had to be integrated across the network. The network must be capable of providing a varying Quality of Service (QoS) level depending on the active sensors in the network. To ensure the QoS level is met, an adaptive QoS algorithm was implemented in the wireless IEEE 802.11 router which monitored and measured the outgoing transmission interface; from which, it determined the latency and transmission jitter. Based on the results, the program can adjust the bandwidth as necessary. Finally, a user interface is developed that allows end users to monitor the network. The performance of the network is based on the end-to-end throughput, latency and jitter exhibited by the network.

Recent developments in robot technology have contributed to the advancement of autonomous behaviours in human-robot systems; for example, in following instructions received from an interacting human partner. Nevertheless, increasingly many systems are moving towards more seamless forms of interaction, where factors such as implicit trust and persuasion between humans and robots are brought to the fore. In this context, the problem of attaining, through suitable computational models and algorithms, more complex strategic behaviours that can influence human decisions and actions during an interaction, remains largely open. To address this issue, this thesis introduces the problem of decision shaping in strategic interactions between humans and robots, where a robot seeks to lead, without however forcing, an interacting human partner to a particular state. Our approach to this problem is based on a combination of statistical modeling and synthesis of demonstrated behaviours, which enables robots to efficiently adapt to novel interacting agents. We primarily focus on interactions between autonomous and teleoperated (i.e. human-controlled) NAO humanoid robots, using the adversarial soccer penalty shooting game as an illustrative example. We begin by describing the various challenges that a robot operating in such complex interactive environments is likely to face. Then, we introduce a procedure through which composable strategy templates can be learned from provided human demonstrations of interactive behaviours. We subsequently present our primary contribution to the shaping problem, a Bayesian learning framework that empirically models and predicts the responses of an interacting agent, and computes action strategies that are likely to influence that agent towards a desired goal. We then address the related issue of factors affecting human decisions in these interactive strategic environments, such as the availability of perceptual information for the human operator. Finally, we describe an information processing algorithm, based on the Orient motion capture platform, which serves to facilitate direct (as opposed to teleoperation-mediated) strategic interactions between humans and robots. Our experiments introduce and evaluate a wide range of novel autonomous behaviours, where robots are shown to (learn to) influence a variety of interacting agents, ranging from other simple autonomous agents, to robots controlled by experienced human subjects. These results demonstrate the benefits of strategic reasoning in human-robot interaction, and constitute an important step towards realistic, practical applications, where robots are expected to be not just passive agents, but active, influencing participants.

Wireless sensors can be worn on soldiers or installed on vehicles to form distributed sensor networks to locate the source of sniper fire. A two-step source localization process is proposed for this sniper detection task. The time difference of arrival (TDOA) for the acoustic signals received by the sensors is first estimated using the generalized cross correlation (GCC) method. The estimated TDOA values are then used by the hybrid spherical interpolation/maximum likelihood (SI/ML) estimation method to estimate the shooter location. A simulation model has been developed in MATLAB to study the performance of the hybrid SI/ML estimation method. A wireless sensor network is simulated in NS-2 to study the network throughput, delay and jitter. Simulation results indicate that the estimation accuracy can be increased by increasing the number of sensors or the inter-sensor spacing. The constraint of small inter-sensor spacing on wearable sensors is found to degrade the estimation accuracy, but vehicular configuration providing larger inter-sensor spacing can help improve the estimation accuracy. The sensor topology should be well represented in all three dimensions to obtain desired estimation accuracy. The estimation accuracy is not adversely affected by sensor node failures or location perturbations. The NS-2 simulation results indicate that the wireless sensor network has low delay and can support fast information exchange needed in counter-sniper applications.

The applications of wireless sensor networks (WSNs) have risen in recent years both in the civilian and military sectors. While a number of WSN-based systems have been proposed and developed, vast majority of them focus on capability demonstration rather than the issues of deployment. As a result, even though the systems can serve useful purposes, they are very hard to deploy. The objective of this thesis is to focus on the deployment issues of WSNs. In addition, this thesis assesses the optimal configurations and environment that enables the sensor networks to thrive in a C4ISR environment. This thesis presents a technology review of the ZigBee and the IEEE 802.15.4 standards which form the core technology in WSNs. The thesis also discusses the IEEE 802.15.4 Physical and Media Access Control Layers that comprise the bottom two layers of WSNs. This thesis also provides a brief introduction to the hardware and software that deal with WSN technology. Lastly, this thesis evaluates the military applications of WSNs. It is hoped that the military can employ wireless sensors to increase situational awareness, attain information superiority, and improve decision-making.

This thesis investigates the RF characteristics of Mica-Z wireless unattended sensor networks for military and commercial applications. Several experimental configurations were designed and experiments carried out to observe and analyze the behavior of the Mica-Z sensor network. The Mica-Z moteâ s propagation characteristics and network performance were measured under near free-space, indoor and outdoor environments to provide a comprehensive perspective of typical sensor network characteristics. Link-break and re-association distances with their corresponding RF power measurements were recorded to determine the Mica-Zâ s range characteristics under these different operating environments. Power loss exponents were also estimated to provide Mica-Z users a faster and more convenient way to estimate operating ranges in the different environments. A graphical numeric electromagnetic code (GNEC) simulation was also used to investigate some of the possible improvements that could be made to the existing Mica-Z antenna design to enhance the performance of the sensor network. This thesis substantiates the difficulties of operating such sensor networks in the most hostile environments. Although the measurements and analyses demonstrated that controlled deployment was possible to some extent, the effectiveness of deployment remains challenging especially for random ad-hoc deployment.

Wireless sensor networks have been a key driver of innovation and societal progressover the last three decades. They allow for simplicity because they eliminate ca-bling complexity while increasing the flexibility of extending or adjusting networksto changing demands. Wireless sensor networks are a powerful means of fillingthe technological gap for ever-larger industrial sites of growing interconnection andbroader integration. Nonetheless, the management of wireless networks is difficultin situations wherein communication requires application-specific, network-widequality of service guarantees. A minimum end-to-end reliability for packet arrivalclose to 100% in combination with latency bounds in the millisecond range must befulfilled in many mission-critical applications.The problem addressed in this thesis is the demand for algorithmic support forend-to-end quality of service guarantees in mission-critical wireless sensor networks.Wireless sensors have traditionally been used to collect non-critical periodic read-ings; however, the intriguing advantages of wireless technologies in terms of theirflexibility and cost effectiveness justify the exploration of their potential for controland mission-critical applications, subject to the requirements of ultra-reliable com-munication, in harsh and dynamically changing environments such as manufactur-ing factories, oil rigs, and power plants.This thesis provides three main contributions in the scope of wireless sensor net-works. First, it presents a scalable algorithm that guarantees end-to-end reliabilitythrough scheduling. Second, it presents a cross-layer optimization/configurationframework that can be customized to meet multiple end-to-end quality of servicecriteria simultaneously. Third, it proposes an extension of the framework used toenable service differentiation and priority handling. Adaptive, scalable, and fast al-gorithms are proposed. The cross-layer framework is based on a genetic algorithmthat assesses the quality of service of the network as a whole and integrates the phys-ical layer, medium access control layer, network layer, and transport layer.Algorithm performance and scalability are verified through numerous simula-tions on hundreds of convergecast topologies by comparing the proposed algorithmswith other recently proposed algorithms for ensuring reliable packet delivery. Theresults show that the proposed SchedEx scheduling algorithm is both significantlymore scalable and better performing than are the competing slot-based schedulingalgorithms. The integrated solving of routing and scheduling using a genetic al-vvigorithm further improves on the original results by more than 30% in terms of la-tency. The proposed framework provides live graphical feedback about potentialbottlenecks and may be used for analysis and debugging as well as the planning ofgreen-field networks.SchedEx is found to be an adaptive, scalable, and fast algorithm that is capa-ble of ensuring the end-to-end reliability of packet arrival throughout the network.SchedEx-GA successfully identifies network configurations, thus integrating the rout-ing and scheduling decisions for networks with diverse traffic priority levels. Fur-ther, directions for future research are presented, including the extension of simula-tions to experimental work and the consideration of alternative network topologies. / <p>Vid tidpunkten för disputationen var följande delarbeten opublicerade: delarbete 4 (manuskript inskickat för granskning), delarbete 5 (manuskript inskickat för granskning)</p><p>At the time of the doctoral defence the following papers were unpublished: paper 4 (manuscript under review), paper 5 (manuscript under review)</p>

A key barrier in the adoption of Wireless Sensor Networks (WSNs) is achieving long-lived and robust real-life deployments. Issues include: reducing the impact of transmission loss, node failure detection, accommodating multiple sensor modalities, and the energy requirement of the WSN network stack. In systems where radio transmissions are the largest energy consumer on a node, it follows that reducing the number of transmissions will, in turn, extend node lifetime. Research in this area has led to the development of the Dual Prediction Scheme (DPS). However, the design of specific DPS algorithms in the literature have not typically considered issues arising in real world deployments. Therefore, this thesis proposes solutions to enable DPSs to function in robust and long-lived real-world WSN deployments. To exemplify the proposed solutions, Cogent-House, an end-to-end open-source home environmental and energy monitoring system, is considered as a case study. Cogent-House was deployed in 37 homes generating 235 evaluation data traces, each spanning periods of two weeks to a year. DPSs presented within the literature are often lacking in the ability to handle several aspects of real world deployments. To address issues in real-life deployments this thesis proposes a novel generalised framework, named Generalised Dual Prediction Scheme (G-DPS). G-DPS provides: i) a multi-modal approach, ii) an acknowledgement scheme, iii) heartbeat messages, and iv) a method to calculate reconstructed data yield. G-DPS’s multi-modal approach allows multiple sensor’s readings to be combined into a single model, compared to single-modal which uses multiple instances of a DPS. Considering a node sensing temperature, humidity and CO2, the multi-modal approach transmissions are reduced by up to 27%, signal reconstruction accuracy is improved by up to 65%, and the energy requirement of nodes is reduced by 15% compared to single-modal DPS. In a lossy network use of acknowledgements improves signal reconstruction accuracy by up to 2x and increases the data yield of the system up to 7x, when compared to an acknowledgement-less scheme, with only up to a 1.13x increase in energy consumption. Heartbeat messages allow the detection of faulty nodes, and yet do not significantly impact the energy requirement of functioning nodes. Implementing DPS algorithms within the G-DPS framework enables robust deployments, as well as easier comparison of performance between differing approaches. DPSs focus on modelling sensed signals, allowing accurate reconstruction of the signal from fewer transmissions. Although transmission scan be reduced in this way, considerable savings are also possible at the application level. Given the information needs of a specific application, raw sensor measurement data is often highly compressible. This thesis proposes the Bare Necessities (BN) algorithm, which exploits on-node analytics by transforming data to information closer to the data source (the sensing device). This approach is evaluated in the context of a household monitoring application that reports the percentage of time a room of the home spends in various environmental conditions. BN can reduce the number of packets transmitted to the sink by 7000x compared to a sense-and-send approach. To support the implementation of the above solutions in achieving long lifetimes, this thesis explores the impact of the network stack on the energy consumption of low transmission sensor nodes. Considering a DPS achieving a 20x transmission reduction, the energy reduction of anode is only 1.3x when using the TinyOS network stack. This thesis proposes the Backbone Collection Tree Protocol (B-CTP), a networking approach utilising a persistent backbone network of powered nodes. B-CTP coupled with Linear Spanish Inquisition Protocol (L-SIP) decreases the energy requirement for sensing nodes by 13.4x compared to sense-and-send nodes using the TinyOS network stack. When B-CTP is coupled with BN an energy reduction of 14.1x is achieved. Finally, this thesis proposes a quadratic spline reconstruction method which improves signal reconstruction accuracy by 1.3x compared to commonly used linear interpolation or model prediction based reconstruction approaches. Incorporating sequence numbers into the quadratic spline method allows up to 5 hours of accurate signal imputation during transmission failure. In summary, the techniques presented in this thesis enable WSNs to be long-lived and robust in real-life deployments. Furthermore, the underlying approaches can be applied to existing techniques and implemented for a wide variety of applications.

Wireless sensor networks are widely applied to many fields such as animal habitat monitoring, air traffic control, and health monitoring. One of the current problems with wireless sensor networks is the ability to overcome communication failures due to hardware failure, distributing sensors in an uneven geographic area, or unexpected obstacles between sensors. One common solution to overcome this problem is to place a minimum number of relay nodes among sensors so that the communication among sensors is guaranteed. This is called Relay Node Placement Problem (RNP). This problem has been proved as NP-hard for a simple connected graph. Therefore, many algorithms have been developed based on Steiner graphs. Since RNP for a connected graph is NP-hard, the RNP for a survivable network has been conjectured as NP-hard and the algorithms for a survivable network have also been developed based on Steiner graphs. In this study, we show the new approximation bound for the survivable wireless sensor networks using the Steiner graphs based algorithm. We prove that the approximation bound is guaranteed in an environment where some obstacles are laid, and also propose the newly developed algorithm which places fewer relay nodes than the existing algorithms. Consequently, the main purpose of this study is to find the minimum number of relay nodes in order to meet the survivability requirements of wireless sensor networks.