Author name cluster

Michael Segal

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

1 author row

EAAI Journal 2021 Journal Article

Collective multi agent deployment for wireless sensor network maintenance

Harel Yedidsion
Danny Hermelin
Michael Segal

In this paper, we study the problem of wireless sensor network (WSN) maintenance using a team of physical autonomous mobile agents. The agents are deployed in the area of the WSN in such a way that would minimize the time it takes them to reach a failed sensor and repair it. The team must constantly optimize its collective deployment to account for occupied agents. The objective is to define the optimal deployment and task allocation strategy, that minimize the solution cost. The solution cost is a linear combination of the weighted sensors’ downtime, the agents’ traveling distance, and penalties incurred due to unrepaired sensors within a certain time limit. Our proposed solution algorithms are inspired by research in the field of computational geometry and the design of our algorithms is based on state of the art approximation algorithms for the classical problem of facility location. We empirically compare and analyze the performance of several proposed algorithms. The sensitivity of the algorithms’ performance to the following parameters is analyzed: agents to sensors ratio, sensors’ sparsity, frequency and distribution of failures, repair duration, repair capacity, and communication limitations. Our results demonstrate that: (i) cooperation enhances the team’s performance by orders of magnitude, (ii) k -Median based deployment algorithm provides up to 30% improvement in downtime, (iii) k -Center based deployment incurs 10% fewest penalties, and (iv) k -Centroid based deployment is most efficient in terms of minimizing the overall costs, with up to 21% lower cost than the next best algorithm.

Details DOI

TCS Journal 2015 Journal Article

Message and time efficient multi-broadcast schemes

Liron Levin
Dariusz R. Kowalski
Michael Segal

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.

Details DOI

TCS Journal 2012 Journal Article

Improved approximation algorithms for maximum lifetime problems in wireless networks

Zeev Nutov
Michael Segal

A wireless ad-hoc network consists of a collection of transceivers positioned in the plane. Each transceiver is equipped with a limited battery charge. The battery charge is reduced after each transmission, depending on the transmission distance. One of the major problems in wireless network design is to route network traffic efficiently, so as to maximize the network lifetime, i. e. , the number of successful transmission rounds. In this paper, we consider Rooted Maximum Lifetime Broadcast/Convergecast problems in wireless settings. The instance consists of a directed graph G = ( V, E ) with edge-weight w ( e ) (the power needed to transmit a message along e ) for every e ∈ E, node capacity b ( v ) (the battery charge of v ) for every v ∈ V, and a root r. The goal is to find a maximum size collection { T 1, …, T k } of Broadcast/Convergecast trees rooted at r such that ∑ i = 1 k w ( δ T i ( v ) ) ≤ b ( v ), where δ T ( v ) is the set of edges leaving v in T. In the Single Topology version, the same tree is used to transmit all the messages, namely, all the Broadcast/Convergecast trees T i are identical. Using recent work on degree constrained network design problems (Nutov, 2008) [26], we give constant ratio approximation algorithms for various broadcast and convergecast problems, improving the previously best known approximation Ω ( ⌊ 1 / log n ⌋ ) by Elkin et al. (2011) [12]. Similar results are shown for the more general Rooted Maximum Lifetime Mixedcast problem, where in addition we are given an integer γ ≥ 0, and the goal is to find the maximum integer k so that k Broadcast and γ k Convergecast rounds can be performed. We also consider the model with partial level aggregation.

Details DOI

TCS Journal 2008 Journal Article

Computing closest and farthest points for a query segment

Michael Segal
Eli Zeitlin

In this paper we present an improved algorithm for finding k closest (farthest) points for a given arbitrary query segment. We show how to preprocess a planar set P of n given points in O ( n 2 log n ) expected time (or, alternatively, in O ( n 2 log 2 n ) deterministic time) and a subquadratic space, in order to report k closest points to an arbitrary given query line segment in O ( k + log 2 n log log n ) time. Here, for the first time, the data structure that provides polylogarithmic query time and uses subquadratic space is presented. We also show an algorithm for reporting the k farthest points from an arbitrary given query line segment.

Details DOI