UCT CS Research Document Archive

Internet of Things: Least Interference Beaconing Algorithms

Tuyishimire, Emmanuel (2014) Internet of Things: Least Interference Beaconing Algorithms. MSc, Department of Computer Science, University of Cape Town.

Full text available as:
PDF - Requires Adobe Acrobat Reader or other PDF viewer.


The emerging sensor networking applications are predicting the deployment of sensor devices in thousands of computing elements into multi-technology and multi-protocol platforms. Access to information will be available not only anytime and anywhere, but also using anything in a first-mile of the Internet referred to as the internet-of-things (IoT).
The management of such a large-scale and heterogeneous network, would benefit from some of the traditional IP-based network management techniques such as load and energy balancing, which can be re-factored to achieve efficient routing of sensor network traffic.
Research has shown that minimizing the path interference on nodes was necessary to improve traffic engineering in connection oriented networks. The same principle has been applied in past research in the context of the IoT to reveal that the least interference beaconing protocol (LIBP); a protocol derived
from the least interference beaconing algorithm (LIBA) outperforms the Collection Tree Protocol (CTP) and Tiny OS Beaconing (ToB) protocol, in terms of energy efficiency and lifetime of the sensor network. However for the purpose of efficiency and accuracy, it is relevant, useful and critical to revisit or re-examine the LIBA algorithm in terms of correctness and investigate potential avenues for improvement.
The main contributions of this research work are threefold. Firstly, we build upon formal methods to verify the correctness of the main principles underlying the LIBA, in terms of energy efficiency and interference minimization. The interference is here defined at each node by the number of routing paths carrying the sensor readings from the motes to the sink of the network that traverse the node. Our findings reveal the limitations in LIBA. Secondly, building upon these limitations, we propose two improvements to the algorithm: an algorithm called LIBA+ that improves the algorithm performance by keeping track of the energy usage of the sensor nodes, and a multi-sink version of the algorithm called LIBAMN that extends the algorithm to account for multiple sinks or gateways. These enhancements present preventive mechanisms to include in IoT platforms in order to improve traffic engineering, the security of network protocols and network stability. Lastly, we present analytical results, which reveal that the LIBA algorithm can be improved by more than 84% in terms of energy balancing. These results reveal that formal methods remain essential in the evaluation and performance improvement of wireless sensor network algorithms and protocols.

EPrint Type:Electronic Thesis or Dissertation
Subjects:C Computer Systems Organization: C.2 COMPUTER-COMMUNICATION NETWORKS
ID Code:997
Deposited By:Suleman, Hussein
Deposited On:21 January 2015