In Wireless Sensor and Robot Networks (WSRNs), static sensors report event information to one of the robots. In the k nearest neighbour query processing problem in WSRNs, the robot receives event report needs to find exact k nearest robots (KNN) to react to the event, among those connected to it. We are interested in localized solutions, which avoid message flooding to the whole network. Several existing methods restrict the search within a predetermined boundary. Some network density-based estimation algorithms were proposed but they either result in large message transmission or require the density information of the whole network in advance which is complex to implement and lacks robustness. Algorithms with tree structures lead to the excessive energy consumption and large latency caused by structural construction. Itinerary based approaches generate large latency or unsatisfactory accuracy. In this thesis, we propose a new method to estimate a search boundary, which is a circle centred at the query point. Two algorithms are presented to disseminate the message to robots of interest and aggregate their data (e.g. the distance to query point). Multiple Auction Aggregation (MAA) is an algorithm based on auction protocol, with multiple copies of query message being disseminated into the network to get the best bidding from each robot. Partial Depth First Search (PDFS) attempts to traverse all the robots of interest with a query message to gather the data by depth first search. This thesis also optimizes a traditional itinerary-based KNN query processing method called IKNN and compares this algorithm with our proposed MAA and PDFS algorithms. The experimental results followed indicate that the overall performance of MAA and PDFS outweighs IKNN in WSRNs.

Wireless sensor networks have been used in different applications due to the advancement of sensor technology. These uses also have raised different 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 efficient in practice. / Thesis (Ph.D, Computing) -- Queen's University, 2012-11-25 13:37:36.854

The coverage and energy issues are the fundamental problems which prevent the development of wireless sensor networks. In order to accurately evaluate the monitoring quality (coverage), one needs to model the interactive of sensors, phenomenons and the environment. Furthermore, in collaborative with scheduling algorithm and computer optimization, protocols can improve the overall monitoring quality and prolong the lifetime of network. This thesis is an investigation of coverage problem and its relative applications in the wireless sensor networks. We first discuss the realistic of current boolean sensing model and propose an irregular sensing model used to determine the coverage in the area with obstacles. We then investigate a joint problem of maintaining the monitoring quality and extending the lifetime of network by using scheduling schemes. Since the scheduling problem is NP hard, genetic algorithm and Markov decision process are used to determine an achievable optimal result for the joint problem of coverage-preserving and lifetime-prolong. In order to avoid the cost of centralized or distributed scheduling algorithms, a localized coverage-preserving scheduling algorithm is proposed by exploring the construction process of Voronoi diagram. Besides exploring the coverage characteristic in a static wireless sensor network, we investigate the coverage problem when the mobile elements are introduced into network. We consider the single-hop mobile data gathering problem with the energy efficiency and data freshness concerns in a wireless sensor network where the connectivity cannot be maintained. We first investigate the upper/lower bound of the covering time for a single collector to cover the monitoring area. Through our investigation we show that for a bounded rectangle area a hexagon walk could explore the area more efficiently than a random walk when the edges of area are known. We then propose a virtual force mobile model (VFM) in which the energy consumption for data transmission is modeled as a virtual elastic force and used to guide of mobile collectors to move to optimal positions for energy saving.

Over the past decade, wireless sensor networks have gained more research attention for their potential applications in healthcare, defense, environmental monitoring, etc. Due to the strict energy limitation in the sensor node, techniques used for energy saving are necessary for this kind of network. MIMO technology is proven to be an effective method of increasing the channel capacity and supporting higher data rate under a fixed power budget and bit-error-rate requirement. So, wireless sensor networks and MIMO technology are combined and investigated in this thesis. The key contributions of this thesis are detailed below. Firstly, the extended total energy consumption equations for different transmission modes in cluster-based wireless sensor networks are derived. The transmitting energy consumption and the circuit energy consumption are taken into account in both intra-cluster and inter-cluster phases respectively. Secondly, a resource allocation framework is proposed for cluster-based cooperative MIMO on consideration of circuit energy. By introducing two adjusting parameters for the transmitting energy and the time slot allocation between intra-cluster and inter-cluster phases, this framework is designed to achieve the maximum data throughput of the whole system whilst maintaining the capacity and outage probability requirement in these two phases respectively. Thirdly, on comparison of various transmission modes in wireless sensor networks, a relatively energy-efficient mode switching framework is proposed for both single-hop and multi-hop transmissions. Based on the destination and the neighboring nodes’ path-loss, the source node can decide which transmission mode, SISO or cooperative MISO, single-hop or multi-hop, should be chosen. Conditions for each mode switching are investigated. The possible existing area of the cooperative nodes and the relaying nodes can be obtained from this framework.

Wireless Sensor Networks (WSNs) is an important field of study as more and more applications are enhancing daily life. The technology trend is to achieve small-sized, cheap, and power efficient sensor nodes, which will make the system reliable and efficient. The Crossbow Technologies MICAz mote is an example used in this thesis. Measurements for its propagation characteristics in a realistic environment will help the deployment and installation of these motes to form a WSN. The CST Microwave Studio is used to build a simulation for the MICAz. The Rhino software is used to build Spanagel Hall, which is the location of the simulation. All of these elements are integrated in Urbana. Urbana is a simulation tool used to simulate the propagation decay around the mote and investigate the irregularity of the electromagnetic field for the indoor environment of the motes. The results and comparisons between empirical and simulated data are intended for assisting in the design and future studies and deployment of WSNs in the real world. / Jordanian Army author.

Using multi-agent systems to execute a variety of missions such as environmental monitoring and target tracking has been made possible by the advances in control techniques and computational capabilities. Communication abilities between agents allow them to coact and execute several coordinated missions, among which there is optimal coverage. The optimal coverage problem has several applications in engineering theory and practice, as for example in environmental monitoring, which belongs to the broad class of resource allocation problems, in which a finite number of mobile agents have to be deployed in a given spatial region with the assignment of a sub-region to each agents with respect to a suitable coverage metric. The coverage metric encodes the sensing performance of individual agent with respect to points inside the domain of interest, and a distribution of risk density. Usually the risk density function measures the relative importance assigned to inner regions. The optimal coverage problem in which the risk density is time-invariant has been widely studied in previous research. The solution to this class of problems is centroidal Voronoi tessellation, in which each agent is located on the centroid of the related Voronoi cell. However, there are many scenarios that require to be modelled by time-varying risk density rather than time-invariant one, as for example in area coverage problems where the environment evolves independently of the evolution for the robotic agents deployed to cover the area. In this work, the changing environment is modeled by a time-varying density function which is governed by a convection-diffusion equation. Mixed boundary conditions are considered to model a scenario in which a diffusive substance (e.g., oil from a leaking event or radioactive material from a nuclear accident) enters the area with convective component from the boundary. A non-autonomous feed- back law is employed whose generated trajectories maximize the coverage metric. The asymptotic stability of the multi-agent system is proven by using Barbalat’s lemma, and then theoretical predictions are illustrated by several simulations that represent idealized scenarios.

The meteoric rise and prevalent usage of wireless networking technologies for mobile communication applications have captured the attention of media and imagination of public in the recent decade. One such proliferation is experienced in Wireless Sensor Networks (WSNs), where multimedia enabled elements are fused with integrated sensors to empower tightly coupled interaction with the physical world. As a promising alternative to antiquated wired systems and traditional WSNs in a multitude of novel application scenarios, the newly renovated WSNs have inspired a wide range of research among which investigation on data acquisition techniques is a fundamental one. In this dissertation, we address the problem of data acquisition in next generation WSNs. As wireless sensors are powered with limited energy resources while they are expected to work in an unattended manner for a long duration, energy conservation stands as the primal concern. Also, to enable in-situ sensing in different rate-constrained applications, routing decisions should care about the medium access feasibility of achievable end-to-end data rates. Driven by the fact, we first design cross-layer medium contention aware routing schemes for rate-constrained traffic in single-channel WSNs that maximize network lifetime. Three sufficient conditions on rate feasibility, referred to as rate-based, degree-based, and mixed constraints, are incorporated into the routing formulations to guarantee the practical viability of the routing solutions. Next, with the aim to mitigate interference and hence to enhance network capacity, we extend our work by proposing energy and cross-layer aware routing schemes for multichannel access WSNs that account for radio, MAC contention, and network constraints. In that context, we first derive three new sets of sufficient conditions that ensure feasibility of data rates in multichannel access WSNs. Then, utilizing these sets, we devise three different MAC-aware routing optimization schemes, each aiming to maximize the network lifetime while meeting data rate requirements of end-to-end flows. Finally, we perform extensive simulation studies to evaluate and compare the performance of the proposed routing approaches under various network conditions. So far works are done in milieu of WSNs with both fixed access node and sensor nodes. In the subsequent part of the dissertation, we present the continuation of our work focusing on reliable data acquisition in Mobile WSNs for a promising application namely free-ranging animal tracking/monitoring. To accomplish that goal, we concentrate on providing sufficient conditions on access-point density that limit the likelihood of buffer overflow. We first derive sufficient access-point density conditions that ensure that the data loss rates are statistically guaranteed to remain below a given threshold. Then, we evaluate and validate the derived theoretical results with both synthetic and real-world data. / Graduation date: 2012

Many applications of wireless sensor networks (WSNs) require the sensor nodes of a network to belong to different priority classes where the nodes of a higher priority class enjoy higher data rates than nodes of a lower priority class. Practical design of such networks, however, faces challenges in satisfying the following basic design requirements: a) the need to rely on the medium access control mechanisms provided by the IEEE 802.15.4 standard for low-rate wireless personal area networks, b) the need to solve certain types of class size optimization problems to ensure adequate sensing coverage, and c) the need to achieve good utilization of the available channels. Unfortunately, the current version of the IEEE 802.15.4 does not provide adequate support for rate differentiation. Hence, many proposed solutions to the problem in the literature consider adding extensions to the standard. In this thesis, we introduce some class size optimization problems as examples of coverage problems that may arise in designing a WSN. We then consider a method proposed in the literature for handling the rate differentiation problem. The method relies on modifying the CSMA-CA channel access mechanism of the IEEE standard. We use simulation to examine its performance and its applicability to solve some class size optimization problems. We next investigate the use of Time Division Multiple Access (TDMA) protocols in providing service differentiation among different classes of sensors. We show simple sufficient conditions for the existence of TDMA-based solutions to a class size feasibility problem. Lastly, we consider the use of Guaranteed Time Slots (GTS) of the IEEE 802.15.4 standard in constructing TDMA schedules. We present a new algorithm that uses the GTS service to construct such schedules. The desired algorithm contains some optimization features. The obtained simulation results show the performance gain achieved by the algorithm.

The coverage and energy issues are the fundamental problems which prevent the development of wireless sensor networks. In order to accurately evaluate the monitoring quality (coverage), one needs to model the interactive of sensors, phenomenons and the environment. Furthermore, in collaborative with scheduling algorithm and computer optimization, protocols can improve the overall monitoring quality and prolong the lifetime of network. This thesis is an investigation of coverage problem and its relative applications in the wireless sensor networks. We first discuss the realistic of current boolean sensing model and propose an irregular sensing model used to determine the coverage in the area with obstacles. We then investigate a joint problem of maintaining the monitoring quality and extending the lifetime of network by using scheduling schemes. Since the scheduling problem is NP hard, genetic algorithm and Markov decision process are used to determine an achievable optimal result for the joint problem of coverage-preserving and lifetime-prolong. In order to avoid the cost of centralized or distributed scheduling algorithms, a localized coverage-preserving scheduling algorithm is proposed by exploring the construction process of Voronoi diagram. Besides exploring the coverage characteristic in a static wireless sensor network, we investigate the coverage problem when the mobile elements are introduced into network. We consider the single-hop mobile data gathering problem with the energy efficiency and data freshness concerns in a wireless sensor network where the connectivity cannot be maintained. We first investigate the upper/lower bound of the covering time for a single collector to cover the monitoring area. Through our investigation we show that for a bounded rectangle area a hexagon walk could explore the area more efficiently than a random walk when the edges of area are known. We then propose a virtual force mobile model (VFM) in which the energy consumption for data transmission is modeled as a virtual elastic force and used to guide of mobile collectors to move to optimal positions for energy saving.

Recent years have seen a tremendous growth in the development of small sensing devices capable of data processing and wireless communication through their embed- ded processors and radios. Wireless Sensor Networks (WSNs) are ad hoc networks consisting of such devices gaining importance due to their emerging applications. For a meaningful processing of the information sensed by WSN nodes, the clocks of these individual nodes need to be matched through some well de¯ned procedures. This dissertation focuses on deriving e±cient estimators for the clock parameters of the network nodes for synchronization with the reference node and the estimators variance thresholds are obtained to lower bound the maximum achievable performance. For any general time synchronization protocol involving a two way message ex- change mechanism, the BLUE-OS and the MVUE of the clock o®set between them is derived assuming both symmetric and asymmetric exponential network delays. Next, with the inclusion of clock skew in the model, the joint MLE of clock o®set and skew under both the Gaussian and the exponential delay model and the corresponding al- gorithms for ¯nding these estimates are presented. Also, for applications where even clock skew correction cannot maintain long-term clock synchronization, a closed-form expression for the joint MLE for a quadratic model is obtained. Although the derived MLEs are not computationally very complex, two compu- tationally e±cient algorithms have been proposed to estimate the clock o®set and skew regardless of the distribution of the delays. Afterwards, extending the idea of having inactive nodes in a WSN overhear the two-way timing message communication between two active (master and slave) nodes, the MLE, the BLUE-OS, the MVUE and the MMSE estimators for the clock o®sets of the inactive nodes located within the communication range of the active nodes are derived, hence synchronizing with the reference node at a reduced cost. Finally, focusing on the the one-way timing exchange mechanism, the joint MLE for clock phase o®set and skew under exponential noise model and the Gibbs Sampler for a receiver-receiver protocol is formulated and found via a direct algorithm. Lower and upper bounds for the MSE of JMLE and Gibbs Sampler are introduced in terms of the MSEs of the MVUE and the conventional BLUE, respectively.