Lightweight scheduling and information delivery in wireless networks
Abstract/Contents
- Abstract
- As inherently distributed computational systems, wireless sensor networks rely critically on coordination between nodes to effectively sense, interpret and deliver environmental data. Wireless nodes face significant battery and computational limitations, so a strategy of lightweight and low-communication task coordination is critical to maintaining the longevity and efficient operation of the network. The challenge is to solve network-wide coordination problems, such as scheduling, routing and aggregation, using simple, local operations, such as gossiping, local broadcasting and neighborhood leader election. While each node performs a simple local task, these actions can be carefully aggregated to achieve the desired global solution. In this thesis, we study two key decentralized coordination problems: scheduling and information delivery. In scheduling, where coordination among nodes occurs at the neighborhood level, the problem is for nodes to select timeslots for their actions that do not interfere with those chosen by other nodes in the neighborhood. We employ simple, randomized and rapidly converging iterative algorithms that seek to stagger node behavior while relying as little as possible on potentially expensive inter-node communication. In information delivery, the problem is to build and maintain a delivery infrastructure that enables information dissemination from sources to sinks in the network. Here, we think of the coordination as occurring over longer distances in the network, enabling the required infrastructure to be built in an efficient, decentralized fashion. We employ information delivery "backbones'', like connected dominating sets and hierarchical trees, and show how they can be quickly and easily built and maintained, even when users are mobile and link dynamics affect the network topology.
Description
Type of resource | text |
---|---|
Form | electronic; electronic resource; remote |
Extent | 1 online resource. |
Publication date | 2010 |
Issuance | monographic |
Language | English |
Creators/Contributors
Associated with | Motskin, Ariel |
---|---|
Associated with | Stanford University, Institute for Computational and Mathematical Engineering. |
Primary advisor | Guibas, Leonidas J |
Thesis advisor | Guibas, Leonidas J |
Thesis advisor | Plotkin, Serge A |
Thesis advisor | Roughgarden, Tim |
Advisor | Plotkin, Serge A |
Advisor | Roughgarden, Tim |
Subjects
Genre | Theses |
---|
Bibliographic information
Statement of responsibility | Ariel Motskin. |
---|---|
Note | Submitted to the Institute for Computational and Mathematical Engineering. |
Thesis | Thesis (Ph.D.)--Stanford University, 2010. |
Location | electronic resource |
Access conditions
- Copyright
- © 2010 by Ariel Motskin
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...