Probabilistic topology control in wireless sensor networks

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis Defence


Title: "Probabilistic topology control in wireless sensor networks"

By

Mr. Yunhuai Liu


Abstract

For a wide spectrum of applications ranging from habitat monitoring to
battlefield surveillance, the wireless sensor network (WSN) technology has
exhibited revolutionary advantages when compared to traditional solutions.
Among all the energy-saving schemes, topology control has been well
recognized as an efficient one. By providing an appropriate support for
routing protocols, topology control enables more energy-efficient
transmissions and higher network capacity.

In traditional topology control, a wireless network is represented using
deterministic model that assumes a pair of nodes is either connected or
disconnected. In practice, however, most wireless links are intermittently
connected, called lossy links. %Rich empirical studies have shown that in
most practical environments lossy links account the dominating majority of
WSNs, while reliable wireless links are only a small portion of due to the
high density, hostile environments, and hardware constraints. It implies
that these reliable links can only provide very limited support for
routing. By successfully leveraging these lossy links, topologies of more
energy-efficiency and higher network capacities are available. By
traditional deterministic network model, however, WSN topologies can
hardly be well characterized. To seize the opportunity of lossy links, I
propose a new probabilistic network model. Using this model we are able to
quantify the quality of the network connectivity. The key problem in
probabilistic topology control is to seek an appropriate topology of
minimized energy cost, while the quality of network connectivity satisfied
certain constraints.

In this work, I prove that in general, probabilistic topology control is a
NP-hard problem. To serve different communication paradigms, I propose two
algorithms called CONREAP and BRASP. The former CONREAP is for
sink-to-sensor communications and BRASP is for general sensor-to-sensor
communications. I prove that CONREAP has guaranteed network reachability
for the derived topology. The worst running time is |E| and the space
requirement is |d|. Experimental results show that CONREAP can remarkably
reduce the energy cost. It is more appropriate for low requirement and
large transitional region environments.

To show how to efficiently transmit in a probabilistic wireless network
with lossy links involved in, I proposed a novel reliability-oriented
transmission protocol called proliferation routing. It leverages
randomized dispersion and reproductions. The distinctive feature of
proliferation routing is its great flexibility and high energy-efficiency.
Not only can it be applied with any Medium Access Control (MAC) protocol
and routing metric, but also a desired service quality can be effectively
derived by controlling the system parameters. I conduct comprehensive
theoretical analysis and confirm it implementation and simulation
experiments. In a specific experiment setup, proliferation routing can
increase the end-to-end transmission success rate up to 70% compared with
the well-known hop-based routing and flooding.


Date:			Thursday, 31 July 2008

Time:			2:00p.m.-4:00p.m.

Venue:			Room 3501
			Lifts 25-26

Chairman:		Prof. Hong-Kam Lo (CIVL)

Committee Members:	Prof. Lionel Ni (Supervisor)
			Prof. Jogesh Muppala
			Prof. Qian Zhang
			Prof. Lilong Cai (MECH)
			Prof. Jiannong Cao (Computing, PolyU)


**** ALL are Welcome ****