A framework for recursive algorithms in low-energy broadcast networks. Issue 3 (4th May 2019)

• Record Type: Journal Article
• Authors: Lewis, Timothy B.; Stout, Quentin F.
• Is Part Of: International journal of parallel, emergent and distributed systems. Volume 34:Issue 3(2019)
• Page Start: 321
• Page End: 340
• Publication Date: 2019-05-04
• Subjects: Sensor network -- recursion -- low-energy -- sorting -- convex hull; Parallel computers -- Periodicals; Electronic data processing -- Distributed processing -- Periodicals; Computer algorithms -- Periodicals; 004.35
• DOI: 10.1080/17445760.2018.1448930
• Languages: English
• ISSNs: 1744-5760

Abstract

ABSTRACT: With recent research in sensor networks and IoT technologies, algorithms for broadcast networks should not only seek to minimise runtime but also energy utilisation. We consider the scenario where processors conserve energy by going into a sleep state for the vast majority of the time. Algorithms under these conditions face additional challenges. Specifically, hibernating processors will not know when tasks that have a random runtime complete. This problem is compounded in recursive algorithms where each task's runtime depends upon the runtime of the recursive calls. We provide a framework, breadth-first recursion, that supports recursive algorithms in this setting. As a simple example, we provide a quick-sort algorithm which is optimal for both time and energy utilisation. We then provide an energy-efficient convex hull algorithm with output sensitive runtime that is sublinear for many realistic distributions for processor placement. Further, we provide simulations that show that our algorithms are practical and significantly faster than previous results. The left side of the image represents our algorithmic technique of breadth first recursion. Inside each box is filled with code and represents the recursive calls of a recursive algorithm. They are arranged in a recursion tree and there is an arrow indicating the order that they are executed. On the right side is a representation of the basic components of our model. They represent low-energy broadcast devices in a single-hop network. Graphical Abstract: