On location support and one-hop data collection in wireless sensor networks

UnrestrictedWe consider two fundamental building blocks for many applications in wireless sensor networks - location support and efficient medium access for one-hop data collection.; In the first part of the thesis we identify two important problems of location support - accurate localization and fast & fair localization - and propose novel solutions. We address the problem of accurate localization by proposing two novel, light-weight RF localization techniques called Ecolocation and Sequence-Based Localization. We define constructs called location constraints and location sequences based on distance ranks of reference nodes from the location of the unknown node and use them for localization. We compare and contrast the two localization techniques and show their robustness to RF channel non-idealities through examples. Through extensive systematic simulations and a representative set of real mote experiments, we show that our light-weight RF localization techniques provide comparable or better accuracy than other state-of-the-art radio signal strength-based localization techniques over a range of wireless channel and node deployment conditions.; In addition to being accurate, the location support service should also be fast and fair. The response times of the reference nodes to localization requests from the unknown node should be minimized and multiple unknown nodes, at different locations, should not have widely varying response times. We identify this as a fast/fair localization problem and formulate it as a min-max optimization problem, show that it is related to the well-known, NP-hard, maximum broadcast frame length problem, and investigate a heuristic scheduling based solution. We study the attributes that determine the response times of the reference nodes, called the localization delay, and derive closed-form expressions for it. We then investigate the heuristic solution's performance in terms of localization delay, fairness and average and minimum localizable speeds.; In the second part of the thesis, we address the problem of medium access for one-hop data collection, which occurs frequently in many wireless sensor network applications. We consider a wide spectrum of one-hop data collection applications with continuous data collection at one end and one-shot data collection at the other. While in the continuous data collection problem the contending wireless nodes always have a packet to transmit, in the one-shot data collection problem each contending node has a single packet to transmit. Medium access mechanisms for continuous data collection have been studied extensively in the past by numerous researchers, but such mechanisms for one-shot data collection have received much less attention. In this thesis we address the medium access problem for this spectrum of application scenarios through three different pieces of work.; We model and analyze the performance of slotted Aloha medium access techniques for the one-shot data collection problem. Owing to the transient nature of the network in this problem we use non-ergodic Markov chain analysis and derive flow equations that accurately capture the temporal dynamics of the network. Using these equations we evaluate the medium access techniques' performance in terms of delay and energy consumption.; We then present a novel location-aware medium access protocol for the one-shot data collection problem that uses the location information of contending nodes to reduce collisions and improve the overall performance. We evaluate the protocol in terms of delay and energy consumption and compare it with location-unaware medium access protocols using simulations. Results show that our protocol can take advantage of the location distribution of nodes to provide significantly lower delay and energy consumption compared to location-unaware protocols.; Finally, we model, analyze, and evaluate the performance of the IEEE 802.15.4 MAC protocol for both ends of the one-hop data collection application spectrum. We find that the IEEE 802.15.4 MAC protocol performs poorly for one-hop data collection in dense sensor networks, showing a steep deterioration in both throughput and energy consumption with increasing number of transmitters. We propose a channel feedback-based enhancement to the protocol that is significantly more scalable, showing a relatively flat, slow-changing total system throughput and energy consumption as the network size increases. A key feature of the enhancement is that the back-off windows are updated after successful transmissions instead of collisions. The window updates are based on an optimality criterion we derive from mathematical modeling of p-persistent CSMA