Configuring heterogeneous wireless sensor networks under quality-of-service constraints

ROBERT JOHAN HUBERT HOES

Publication

Configuring heterogeneous wireless sensor networks under quality-of-service constraints

ROBERT JOHAN HUBERT HOES

Abstract

Wireless sensor networks (WSNs) are useful for a diversity of applications, such as structural monitoring of buildings, farming, assistance in rescue operations, in-home entertainment systems or to monitor people's health. A WSN is a large collection of small sensor devices that provide a detailed view on all sides of the area or object one is interested in. This thesis deals with the configuration problem of a WSN, starting with a heterogeneous collection of nodes in an area of interest, models of the nodes and their interaction, and task-level requirements in terms of quality metrics. Examples of quality metrics are end-to-end latencies, the coverage of the area, or network lifetime. We support multiple quality metrics and optimise these under constraints. Targeted is the class of WSNs with a single data sink that use a routing tree for communication. We introduce two models of WSN tasks ¿ target tracking and spatial mapping ¿ for the experiments in this thesis. The configuration process is split in five phases. After an initialisation phase, the routing tree is formed. We explore the trade-off between two attributes of a tree ¿ the average path length and the maximum node degree ¿ which affect the quality metrics, but also the complexity of the remaining optimisation trajectory. We introduce new algorithms to efficiently construct a shortest-path spanning tree with a bounded node degree. The next phase determines the Pareto-optimal configurations given the routing tree. A configuration contains settings for the parameters (hardware or software settings) of all nodes in the network, plus the quality metrics they give rise to. The Pareto-optimal configurations, represent the best possible trade-offs between the quality metrics. Given the vastness of the configuration space ¿ exponential in the size of the network ¿ a brute-force is impossible. Still our method efficiently finds, under certain conditions, all Pareto points, by incrementally searching the configuration space, and discarding potential solutions immediately when they appear to be non- optimal. Experimental results show that the practical complexity of this algorithm is approximately linear in the number of nodes in the network, and thus scalable to very large networks. After computing the Pareto-optimal configurations, one that satisfies the constraints is selected, and the nodes are configured accordingly (the selection and loading phases). The configuration process can be executed in either a centralised or a distributed way. Simulations show run times in the order of seconds for the centralised configuration of WSNs of hundreds of TelosB sensor nodes. The distributed algorithms take in the order of minutes for the same networks, but have a lower communication overhead. We further study meta trade-off between the task's quality and the cost of the configuration process itself. A speed-up of the configuration process can be achieved in exchange for a reduction in the quality. We provide complexity-control functionality to fine-tune this trade-off. The final part of this thesis describes methods to adapt the configuration to dynamism at run time due to, for example, changing network conditions or a sink that moves around. We use localised algorithms to maintain the routing tree and reconfigure the node parameters, and we are able to control the quality/cost trade-off by adjusting the size of the locality in which the reconfiguration takes place.