Theoretical Computer Science 569 (2015) 13–23

Contents lists available at ScienceDirect

M

L a C b D a

Ar

Re

Re

Ac

Av

Co

Ke

Ad

Br

Di 1. on m to br ti w a ho w tim nu op gu pr * ht 03Theoretical Computer Science www.elsevier.com/locate/tcs essage and time efficient multi-broadcast schemes iron Levin a, Dariusz R. Kowalski b, Michael Segal a,∗ ommunication Systems Engineering Department, Ben-Gurion University of the Negev, Israel epartment of Computer Science, University of Liverpool, UK r t i c l e i n f o a b s t r a c t ticle history: ceived 22 September 2013 ceived in revised form 31 July 2014 cepted 9 December 2014 ailable online 16 December 2014 mmunicated by G. Ausiello ywords: -hoc networks oadcast and multi-broadcast stributed algorithms

We consider message and time efficient broadcasting and multi-broadcasting in wireless ad-hoc networks, where a subset of nodes, each with a unique rumor, wish to broadcast their rumors to all destinations while minimizing the total number of transmissions and total time until all rumors arrive to their destination. Under centralized settings, we introduce a novel approximation algorithm that provides almost optimal results with respect to the number of transmissions and total time, separately. Later on, we show how to efficiently implement this algorithm under distributed settings, where the nodes have only local information about their surroundings. In addition, we show multiple approximation techniques based on the network collision detection capabilities and explain how to calibrate the algorithms’ parameters to produce optimal results for time and messages. © 2014 Elsevier B.V. All rights reserved.

Introduction

Data broadcasting, where a rumor from a single source has to be delivered to all other nodes in the graph, is considered e of the most studied problems in wireless ad-hoc networks [1]. In this paper, we study a generalized version called the ulti-broadcast problem [2], where instead of a single source, a subset of sources S ⊆ V , each with a different rumor, have deliver their rumors to all other nodes in the network. When S contains only a single node, the problem reduces to data oadcasting problem, and when S contains all the nodes, it reduces to data gossiping problem [3].

We use the partial aggregation model, also known as the combined message model [4,5], where a node can aggregate mulple messages to one by stripping message headers, using compression or correlating data from other nodes [6]. Formally, e use the compression factor c, which serves as an upper bound for the number of messages that can be compressed to single batch; note that a message can only be compressed once. In this paper, we develop generalized algorithms which ld for any subset S ⊆ V and positive integer c ∈ [1, k], and thus suitable for both broadcasting and gossiping with and ithout aggregation (i.e., c = 1).

In data dissemination, there are two important performance metrics that directly affect the quality of the algorithm: e efficiency, measured by the total time until all nodes receive all rumors, and message efficiency, assessed by the total mber of messages that are transmitted in the network. Most papers on data broadcasting and gathering concentrate on timizing the time metric [4,7,3,8] and only provide by-product analysis of the message metric without exact performance arantees. However, in ad-hoc networks, where the nodes have limited battery and the cost of sending a message is directly oportional to the lifetime of a node [9], minimizing the number of messages is a key aspect in the overall efficiency of

Corresponding author.

E-mail address: segal@bgu.ac.il (M. Segal). tp://dx.doi.org/10.1016/j.tcs.2014.12.006 04-3975/© 2014 Elsevier B.V. All rights reserved. 14 L. Levin et al. / Theoretical Computer Science 569 (2015) 13–23 th an of kn se ne

Ou un th th de w al

Ne bo

Th ad w br fo fo 2. an r pa re is is w no as fu no in

In

Ou k

M

Tie solution. In this work, we concentrate on finding both message and time efficient algorithms for broadcasting problem d for the more general multi-broadcasting problem, with and without aggregation. We separate our analysis to two types network settings: centralized and distributed. In the centralized network setting [7], we assume that each node has full owledge about the topology of the network, including size, distance, and the ids of all nodes. In the distributed network ttings [10–12], we assume that each node has only partial information about the network; for example, the number of ighbors it has or the total number of nodes. r results. For centralized network setting we show a direct relation between messages efficiency and the size of the derlying backbone topology, on which rumors propagate to their destination, and show how to build a backbone such at the number of message transmitted is small. To handle time efficiency, we show how to shorten the diameter of e obtained backbone, which decreases the total time of the scheduling algorithm and ensures all rumors arrive to their stination as soon as possible. Our construction has minor impact on the message efficiency. By producing a backbone ith relatively short diameter with respect to the optimal one, our results improve previous approximation ratio by Kim et . [13]. For the distributed network settings, we first show how to construct the backbone on which rumors will propagate. xt, we show a randomized message and time efficient technique for transmitting messages using the constructed backne structure. The technique enables calibrating the performance of the algorithm based on time or message requirements. e novelty of our approach is by comparing the quality of the proposed algorithms under each of the criteria, separately. In dition, as a by-product of our work, we present an algorithm for building a connected dominating set with short diameter ith respect to the optimal.

The rest of the paper is organized as follows: in Section 2 we present the model of the network and formulate the multioadcast optimization problem. Summary of related work is presented in Section 3. We provide approximation algorithms r efficient message and time broadcast and multi-broadcast under centralized setting in Section 4, and extend this work r distributed setting in Section 5. Our conclusions and future work are summarized in Section 6.