Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/6774
Title: Energy-efficient interference-free link scheduling in wireless sensor networks
Authors: Ma, Junchao
Keywords: Wireless sensor networks.
Computer networks -- Energy conservation.
Hong Kong Polytechnic University -- Dissertations
Issue Date: 2013
Publisher: The Hong Kong Polytechnic University
Abstract: Wireless sensor networks (WSNs) consist of thousands of tiny, inexpensive and low-power sensor nodes that perform collaborative tasks and organize themselves into multi-hop networks. These sensor nodes are deployed over a given area, including both the terrestrial and underwater environments. Consequently, WSNs can be divided into terrestrial wireless sensor networks (TWSNs) and underwater wireless sensor networks (UWSNs). In this thesis, we mainly focus on the design of energy-efficient interference-free link schedulings in WSNs. In a link scheduling, each transmission link is assigned a set of time slots such that it can transmit without interferences. In TWSNs, sensor nodes use radio waves to communicate, and the major source of energy wastage is the idle listening state in the radio modules. To reduce the energy consumption, sensors are generally scheduled to sleep when the radio is not in use. In a traditional sleep scheduling, however, sensors have to start up numerous times in a period, and thus consume extra energy due to the state transitions (e.g. from the sleep state to the listening state or transmitting state). We first identify a novel energy-efficient interference-free link scheduling problem called contiguous link scheduling, in which links incident to one node are scheduled together to obtain consecutive time slots so that the node needs to start up only once to monitor the channel in a period. We prove that the problem is NP-complete, and propose efficient centralized and distributed algorithms that use time slots at most a constant factor of the optimum in both homogeneous and heterogeneous networks. Our proposed distributed scheduling with efficient delay algorithm can also efficiently reduce the network delay. Extensive simulations are conducted to demonstrate the effectiveness of our proposed algorithms. To further reduce the frequency of state transitions in TWSNs, we address a novel energy-efficient interference-free link scheduling problem called compact wakeup scheduling. In the scheduling, a node needs to wake up only once to communicate bidirectionally with all its neighbors. However, not all communication graphs have valid compact wakeup schedulings, and it is NP-complete to decide whether a valid compact wakeup scheduling exists for an arbitrary graph. In particular, trees and grid graphs, which are commonly used in WSNs, have valid compact wakeup schedulings. Polynomial-time algorithms using the optimum number of time slots in a period are proposed for these topologies. The simulation results illustrate the efficiency of our proposed algorithms. In UWSNs, acoustic communication is commonly used unlike that in TWSNs. The long propagation delay of acoustic signals causes the spatio-temporal uncertainty, which makes the link scheduling in UWSNs a challenging problem. To describe the propagation delays of the transmission links and deal with the spatio-temporal uncertainty, we construct a so-called slotted spatio-temporal conflict graph. We propose centralized and distributed scheduling algorithms with performance guarantee to the optimum solutions under both unified and weighted traffic load scenarios. In the weighted traffic load scenario, we consider the scheduling with and without the consecutive constraint. Simulations validate our theoretical results, and show the efficiency of our proposed algorithms.
Description: xx, 179 p. : ill. ; 30 cm.
PolyU Library Call No.: [THS] LG51 .H577P COMP 2013 Ma
URI: http://hdl.handle.net/10397/6774
Rights: All rights reserved.
Appears in Collections:Thesis

Files in This Item:
File Description SizeFormat 
b26817780_link.htmFor PolyU Users 203 BHTMLView/Open
b26817780_ir.pdfFor All Users (Non-printable) 2.61 MBAdobe PDFView/Open
Show full item record

Page view(s)

363
Last Week
2
Last month
Checked on Jul 16, 2017

Download(s)

410
Checked on Jul 16, 2017

Google ScholarTM

Check



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.