UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Energy-efficient algorithm design for wireless sensor networks Shah-Mansouri, Vahid


Wireless sensor networks (WSNs) are composed of inexpensive sensor devices called sensor nodes. Sensors have limited power supply, computational capabilities, and memory. Different types of sensors can measure either temperature, light, sound, or pressure from the environment. Because the sensors have short transmission range, the generated data are gathered via multihop transmissions at a central processor called a sink. In this thesis, we propose several power efficient algorithms for WSNs. First, we formulate the lexicographically optimal commodity lifetime routing problem. We propose the lexicographically optimal node lifetime algorithm, which is suitable for practical implementation. Simulation results show that our proposed algorithm can increase the network lifetime compared to other schemes in the literature. Second, we study the problem of supporting multicast traffic in WSNs with network coding. We formulate the maximum-lifetime minimum-resource coding subgraph problem to study the lifetime-resource tradeoff. Results show that the network lifetime can be substantially increased using our algorithm. Next, we consider the problem of designing feedback mechanisms for WSNs using random linear network coding (RLNC). For an intermediate node, we determine the time at which the node can stop transmission of a particular flow. We propose novel link-by-link and end-to-end feedback mechanisms for RLNC with buffer sharing. Simulation results show that link-by-link feedback is more power-efficient compared to end-to-end feedback. Then, we study the passive loss inference problem in WSNs using RLNC. By inspecting the contents of packets at the sink, the sink can estimate the path loss rates from the sources and intermediate nodes. We propose a passive loss inference with RLNC algorithm. Simulation results show that our algorithm can identify the status of a higher number of links compared to a Bayesian inference algorithm. Finally, we study the problem of cardinality estimation in radio frequency identification systems with several readers. We introduce exclusive estimators to estimate the number of tags located exclusively in the zone of a reader. Then, we propose cardinality estimation algorithms. Our simulation results show that the variance of our proposed estimation algorithms increases linearly with the number of readers while it increases exponentially for existing algorithms.

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International