The impact of mobility on the time complexity for deterministic broadcasting in radio networks. (6th September 2011)

• Record Type: Journal Article
• Authors: Prakash, Ravi; Sasson, Yoav; Mohsin, Mansoor; Cavin, David; Schiper, Andre
• Is Part Of: International journal of ad hoc and ubiquitous computing. Volume 8:Number 3(2011)
• Page Start: 174
• Page End: 188
• Publication Date: 2011-09-06
• Subjects: MANETs -- mobile ad hoc networks -- deterministic broadcasting -- lower bound -- mobile networks -- mobility -- time complexity -- multi-hop radio networks; Ubiquitous computing -- Periodicals; Embedded computer systems -- Periodicals; Electronic data processing -- Distributed processing -- Periodicals; Wireless communication systems -- Periodicals; Computer architecture -- Periodicals; 004.2
• Languages: English
• ISSNs: 1743-8225

Abstract

We study the time complexity for deterministic broadcasting algorithms in mobile radio networks. The broadcast operation consists of a source node successfully communicating its message to every other node. In multi-hop radio networks such as MANETs, the message may traverse multiple other nodes. Nodes have no prior knowledge besides the number n of nodes in the network and its diameter D. The problem we address has been extensively studied for static networks. Our work quantifies the impact of mobility. We consider three families of graphs: undirected graphs of constant contention degree, undirected graphs of non-constant contention degree and directed graphs of non-constant contention degree. We prove the lower bounds of Ω(n log n) time slots for the first family, Ω(n²/D² log D + D) time slots for the second and Ω(n²/D² log D + n log D) for the third. At the time of writing, the corresponding tightest lower bounds derived in the static case are, respectively, Ω(D log n), Ω(n log/log n / D) and Ω(n log D).