A local reconfiguration algorithm (INP) for reliable routing in wireless sensor networks that consist of many static (fixed) energy-constrained nodes is introduced in the dissertation. For routing around crash fault nodes, a communication tree structure connecting sensor nodes to the base station (sink or root) is dynamically reconfigured during information dissemination. Unlike other location based routing approaches, INP does not take any support from a high costing system that gives position information such as GPS. For reconfigurations, INP uses only local relational information in the tree structure among nearby nodes by collaboration between the nodes that does not need global maintenance, so that INP is energy efficient and it scales to large sensor networks. The performance of the algorithm is compared to the single path with repair routing scheme (SWR) that uses a global metric and the modified GRAdient broadcast scheme (GRAB-F) that uses interleaving multiple paths by computation and by simulations. The comparisons demonstrate that using local relative information is mostly enough for reconfigurations, and it consumes less energy and mostly better delivery rates than other algorithms especially in dense environments. For the control observer to know the network health status, two new diagnosis algorithms (Repre and Local) that deal with crash faults for wireless sensor networks are also introduced in the dissertation. The control observer knows not only the static faults found by periodic testing but also the dynamic faults found by a path reconfiguration algorithm like INP that is invoked from evidence during information dissemination. With based on this information, the control observer properly treats the network without lateness. Local algorithm is introduced for providing scalability to reduce communication energy consumption when the network size grows. The performance of these algorithms is computationally compared with other crash faults identification algorithm (WSNDiag). The comparisons demonstrate that maintaining the communication tree with local reconfigurations in Repre and Local needs less energy than making a tree per each diagnosis procedure in WSNDiag. They also demonstrate that providing scalability in Local needs less energy than other approaches.

A local reconfiguration algorithm (INP) for reliable routing in wireless sensor networks that consist of many static (fixed) energy-constrained nodes is introduced in the dissertation. For routing around crash fault nodes, a communication tree structure connecting sensor nodes to the base station (sink or root) is dynamically reconfigured during information dissemination. Unlike other location based routing approaches, INP does not take any support from a high costing system that gives position information such as GPS. For reconfigurations, INP uses only local relational information in the tree structure among nearby nodes by collaboration between the nodes that does not need global maintenance, so that INP is energy efficient and it scales to large sensor networks. The performance of the algorithm is compared to the single path with repair routing scheme (SWR) that uses a global metric and the modified GRAdient broadcast scheme (GRAB-F) that uses interleaving multiple paths by computation and by simulations. The comparisons demonstrate that using local relative information is mostly enough for reconfigurations, and it consumes less energy and mostly better delivery rates than other algorithms especially in dense environments. For the control observer to know the network health status, two new diagnosis algorithms (Repre and Local) that deal with crash faults for wireless sensor networks are also introduced in the dissertation. The control observer knows not only the static faults found by periodic testing but also the dynamic faults found by a path reconfiguration algorithm like INP that is invoked from evidence during information dissemination. With based on this information, the control observer properly treats the network without lateness. Local algorithm is introduced for providing scalability to reduce communication energy consumption when the network size grows. The performance of these algorithms is computationally compared with other crash faults identification algorithm (WSNDiag). The comparisons demonstrate that maintaining the communication tree with local reconfigurations in Repre and Local needs less energy than making a tree per each diagnosis procedure in WSNDiag. They also demonstrate that providing scalability in Local needs less energy than other approaches.

Pulse synchronization is the evolution of spontaneous firing action across a network of sensor nodes. In the pulse synchronization model all nodes across a network produce a pulse, or "fire", at regular intervals even without access to a shared global time. Previous researchers have proposed the Reachback Firefly algorithm for pulse synchronization, in which nodes react to the firings of other nodes by changing their period. We propose an extension to this algorithm for tolerating arbitrary or Byzantine faults of nodes. Our algorithm queues up all the firings heard in the current cycle and discards outliers at the end of the cycle. An adjustment is computed with the remaining values and used as a starting point of the next cycle. Through simulation we validate the performance of our algorithm and study the overhead in terms of convergence time and periodicity. The simulation considers two specific kinds of Byzantine faults, the No Jump model where faulty nodes follow their own firing cycle without reacting to firings heard from other nodes and the Random Jump model where faulty nodes fire at any random time in their cycle.

Mobile robots have found numerous applications in recent years, in areas such as consumer robotics, environmental monitoring, security and transportation. For information dissemination, multi-robot cooperation or operator intervention, reliable communications are important. The combination of communication constraints with other requirements in robotics, such as navigation and obstacle avoidance is called communication-aware motion planning. To facilitate integration, communication-aware methods should fit into traditional layered architectures of motion planning. This thesis contains two main contributions, applicable to such an architecture. The first contribution is to develop strategies for exploiting multipath fading while following a reference trajectory. By deviating from the reference, a robot can stop and communicate at positions with high signal strength, trading tracking performance for link quality. We formulate this problem in three different ways: First we maximize the link quality, subject to deterministic bounds on the tracking error. We control the velocity based on the position and channel quality. Second, we consider probabilistic tracking error bounds and develop a cascaded control architecture that performs time-triggered stopping while regulating the tracking error. Third, we formulate a hybrid optimal control problem, switching between standing still to communicate and driving to improve tracking. The resulting channel quality is analyzed and we perform extensive experiments to validate the communication model and compare the proposed methods to the nominal case of driving at constant velocity. The results show good agreement with the model and improvements of over 100% in the throughput when the channel quality is low. The second contribution is to plan velocities for a group of N robots, moving along pre-determined paths through an obstacle field. Robots can only communicate if they have an unobstructed line of sight, and the problem is to maintain connectivity while traversing the paths. This is mapped to motion planning in an N-dimensional configuration space. We propose and investigate two solutions, using a rapidly exploring random tree (RRT) and an exact method inspired by cell decomposition. The RRT method scales better with the problem size than the exact method, which has a worst-case time complexity that is exponential in the number of obstacles. But the randomization in the RRT method makes it difficult to set a timeout for the solver, which runs forever if a problem instance is unsolvable. The exact method, on the other hand, detects unsolvable problem instances in finite time. The thesis demonstrates, both in theory and experiments, that mobile robots can improve communications by planning trajectories that maintain visual connectivity, or by exploiting multipath fading when there is no line of sight. The proposed methods are well suited for integration in a layered motion planning architecture. / QC 20120117

The main purpose of this thesis is to utilize landmarks with known coordinates and the distance between a target and landmarks to establish an objective function, and to optimize the objective function by using unconstrained direct search method to estimate the coordinate of target. A number of nodes in the sensor network serve as the landmarks according to landmark selection algorithm. Since the landmark selection algorithm is time-consuming, a simplified scheme that would improve the algorithm is to reuse the distance information that had been computed. Due to the limit of transmission range between nodes, utilizing the shortest-path distance estimation model can quickly estimate the distance between the target and non-adjacent landmarks. The main conception of the model is combining the manner of multi-hop with the shortest-path model. Due to the possible errors in distance estimation, the error per hop is considered for reducing the estimation errors. It will obviously reduce the localization errors of the target. The thesis utilizes unconstrained direct search method to optimize the objective functions such as the simplex evolutionary method (SEM), the cyclic coordinate method(CCM) and the Powell method (PM). CCM and PM will tackle the problem of finding the forward length along search direction. Hence, two schemes that combine CCM or PM with SEM are proposed to resolve the problem. Finally, simulations are conducted to generate random some nodes in an known area and to select landmarks from the nodes. Let the target be assigned in the area and do performance analysis of positioning algorithm. We discuss the performance of the positioning algorithm by considering the error per hop approach. We also discuss the effects on positioning by changing some variables such as the number of nodes, the number of landmarks and the transmission range of nodes. It is seen that the positioning errors will be reduced in examples where the number of landmark are four or the number of node are four hundred. The performance of positioning becomes accurate by reducing the distance estimation error.

Non-parametric belief propagation (NBP) is a well-known message passing method for cooperative localization in wireless networks. However, due to the over-counting problem in the networks with loops, NBP’s convergence is not guaranteed, and its estimates are typically less accurate. One solution for this problem is non-parametric generalized belief propagation based on junction tree. However, this method is intractable in large-scale networks due to the high-complexity of the junction tree formation, and the high-dimensionality of the particles. Therefore, in this article, we propose the non-parametric generalized belief propagation based on pseudo-junction tree (NGBP-PJT). The main difference comparing with the standard method is the formation of pseudo-junction tree, which represents the approximated junction tree based on thin graph. In addition, in order to decrease the number of high-dimensional particles, we use more informative importance density function, and reduce the dimensionality of the messages. As by-product, we also propose NBP based on thin graph (NBP-TG), a cheaper variant of NBP, which runs on the same graph as NGBP-PJT. According to our simulation and experimental results, NGBP-PJT method outperforms NBP and NBP-TG in terms of accuracy, computational, and communication cost in reasonably sized networks. / COOPLOC / FP7-ICT WHERE2

In recent years, many strides have been achieved in the area of Wireless Sensor Networks (WSNs), which is leading to constant innovations in the types of applications that WSNs can support. Much advancement has also been achieved in the area of smart homes, enabling its occupants to manually and easily control their utility expenses. In this thesis, both areas of research will be colluded for a simple, yet critical application: efficient and economical comfort control in smart residential spaces. The goal is to design a central, modular energy consumption control system for residential spaces, which manages energy consumption in all aspects of a typical residence. This thesis is concerned with two facets of energy consumption in residences. The first facet is concerned with controlling when the heating, ventilating, and air conditioning unit (HVAC) operates for each room separately. This is in contrast to a typical HVAC system where comfort is provided across the floor as a whole. The second facet is concerned with controlling the lighting in each room so as to not exceed a certain input value. The communication network that supports the realization of these coveted goals is based on Zigbee interconnected sensor nodes which pour data unto a smart thermostat which does all the required calculations and activates the modules required for comfort control and energy management, if needed. A Java-based discrete event simulator is then written up to simulate a floor of a typical Canadian single-family dwelling. The simulation assumes error-less communication and proceeds to record certain room variables and the ongoing cost of operation periodically. These results from the simulator are compared to the results of the well known simulator, created by DesignBuilder, which describes typical home conditions. The conclusion from this analysis is that the Comfort Control and Energy Management Algorithms (CEMA) are feasible, and that their implementation incurs significant monetary savings.

Sensor network web services have recently emerged as promising tools to provide remote management, data collection and querying capabilities for sensor networks. They can be utilized in a large number of elds among which Demand-Side Energy Management (DSEM) is an important application area that has become possible with the smart electrical power grid. DSEM applications generally aim to reduce the cost and the amount of power consumption. In the traditional power grid, DSEM has not been implemented widely due to the large number of households and lack of ne-grained automation tools. However by employing intelligent devices and implementing communication infrastructure among these devices, the smart grid will renovate the existing power grid and it will enable a wide variety of DSEM applications. In this thesis, we analyze various DSEM scenarios that become available with sensor network web services. We assume a smart home with a Wireless Sensor Network (WSN) where the sensors are mounted on the appliances and they are able to run web services. The web server retrieves data from the appliances via the web services running on the sensor nodes. These data can be stored in a database after processing, where the database can be accessed by the utility, as well as the inhabitants of the smart home. We showthat our implementation is e cient in terms of running time. Moreover, the message sizes and the implementation code is quite small which makes it suitable for the memory-limited sensor nodes. Furthermore, we show the application scenarios introduced in the thesis provide energy saving for the smart home.

Wireless sensor networks suffer from limited power resources. Therefore, managing the energy constraints and exploring new ways to minimize the power consumption during the operation of the nodes are critical issues. Conventional MAC protocols deal with this problem without considering the internal properties of the sensor nodes’ batteries. However, recent studies about battery modeling and behaviour showed that the pulsed discharge mechanism and the charge recovery effect may have a significant impact on wireless communication in terms of power saving. In this thesis we propose two battery-aware MAC protocols that take benefit of these factors to save more energy and to prolong the lifetime of the nodes/network without affecting the throughput. In both protocols we measure the remaining battery capacity of the node and use that measurement in the back-off scheme. The first protocol gives the nodes with higher remaining battery capacity more priority to access the medium, while the other one provides more medium access priority to the nodes with lower remaining battery capacity. The objective is to investigate, through simulations, which protocol reduces the power consumption of the nodes, improve the lifetime of the network, and compare the results with the CSMA-CA protocol.

Wireless sensor networks (WSN) have generated tremendous interest among researchers these years because of their potential usage in a wide variety of applications.<p> Sensor nodes are inexpensive portable devices with limited processing power and energy resources. Sensor nodes can be used to collect information from the environment, locally process this data and transmit the sensed data back to the user.<p> This thesis proposes a new reliable data delivery protocol for general point-to-point data delivery (unicasting) in wireless sensor networks. The new protocol is designed that aims at providing 100% reliability when possible as well as minimizing overhead and network delay. The design of the new protocol includes three components. The new protocol adopts a NACK-based hop-by-hop loss detection and recovery scheme using end-to-end sequence numbers. In order to solve the single/last packet problem in the NACK-based approach, a hybrid ACK/NACK scheme is proposed where an ACK-based approach is used as a supplement to the NACK-based approach to solve the single/last packet problem. The proposed protocol also has a new queue management scheme that gives priority to new data. By introducing the idea of a Ready_Bit and newer packet first rule in the transmission queue, nodes can detect and recover lost packets in parallel with the normal data transmission process. The performance of the new protocol is tested in a Crossbow MicaZ testbed. Experimental results show that the new protocol performs well under various system and protocol parameter settings.