Year

2013

Degree Name

Doctor of Philosophy

Department

School of Electrical, Computer and Telecommunications Engineering

Abstract

Broadcast is a fundamental operation in Wireless Sensor Networks (WSNs). Given a source node with a packet to broadcast, the aim is to propagate the packet to all nodes in an interference-free manner whilst incurring minimum latency. This problem, called Minimum Latency Broadcast Scheduling (MLBS), has been studied extensively in wireless ad-hoc networks, whereby nodes remain on all the time, and has been shown to be NP-hard. However, only a few studies have addressed this problem in the context of duty-cycled WSNs. In these WSNs, nodes do not wake-up simultaneously, and hence, not all neighbors of a transmitting node will receive a broadcast message at the same time. Unfortunately, this Minimum Latency Broadcast Scheduling problem in Duty-Cycled WSNs (MLBSDC) remains NP-hard and multiple transmissions may be necessary due to different wake-up times. Moreover, existing studies addressed the MLBSDC problem only over the idealistic interference model, i.e., the RTS/CTS interference model, in which, if two or more nodes transmit simultaneously to a single node, collision occurs and thereby, corrupting the message. However, this idealistic interference model does not take into account the interference from transmissions outside a receiver’s transmission range.

This thesis, therefore, investigates the MLBSDC problem under different interference models, i.e., the RTS/CTS, protocol, and physical interference model. Different from the RTS/CTS interference model, the other two models reflect the fact that the successful reception of a message is subject to interference from transmissions outside the receiver’s transmission range. This thesis proposes a series of approximation algorithms. Specifically, the main contributions of this thesis are as follows.

This thesis contributes two approximation algorithms, called BS-1 and BS-2, for the MLBSDC problem under the RTS/CTS interference model. In particular, BS-2 produces the best constant approximation ratio of 13T in terms of broadcast latency, as compared to other proposed algorithms. Here, T denotes the number of time slots in a scheduling period.

Apart from that, this thesis outlines one centralized greedy heuristic algorithm and its distributed implementation, called CEN and DIS respectively, for the MLBSDC problem under the RTS/CTS interference model. The centralised version, i.e., CEN, produces a ratio of (Δ-1)T in terms of broadcast latency, where Δ is the maximum degree of nodes. Extensive experimental results show that the broadcast latency of CEN and DIS is near optimal. In particular, compared to OTAB, the best broadcast scheduling algorithm to date, the broadcast latency and number of transmissions achieved by CEN are about ⅕ and ½ that of OTAB, respectively.

This thesis also contains two constant approximation algorithms for the MLBSDC problem under the protocol interference model. In particular, this thesis contains the first studies on the MLBSDC problem under the protocol interference model. The proposed algorithms, called IABBS and IAEBS produce a O(p2)- approximate solution with respect to broadcast latency, where p is the ratio between the interference and transmission range.

Finally, this thesis outlines the first distributed algorithm, called HBA, for the MLBSDC problem under the physical interference model. Furthermore, HBA gives a constant ratio in terms of the broadcast latency and number of transmissions. The performance of HBA is evaluated under different network configurations and the results show that the latencies achieved by HBA are much lower than existing schemes. In particular, the broadcast latency achieved by HBA is only ½ that of the tree-based algorithm.

Download

Share

COinS
 

Unless otherwise indicated, the views expressed in this thesis are those of the author and do not necessarily represent the views of the University of Wollongong.