Sensor Network Topology Design and Analysis for Efficient Data Gathering by a Mobile Mule
- PDF / 2,255,950 Bytes
- 25 Pages / 439.37 x 666.142 pts Page_size
- 81 Downloads / 215 Views
Sensor Network Topology Design and Analysis for Efficient Data Gathering by a Mobile Mule Harel Yedidsion3 · Stav Ashur1 · Aritra Banik2 · Paz Carmi1 · Matthew J. Katz1 · Michael Segal1 Received: 7 September 2018 / Accepted: 26 March 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract In this paper, we study the problem of data gathering in ad-hoc sensor networks using a mobile entity called mule. The mule traverses the children of failed sensors, to prevent loss of data. Our objective is to define the optimal communication tree, and the mule’s placement such that the mule’s overall traveling distance is minimized. We explore this problem in several network topologies including: unit disc graph on a line (UDL), general unit disc graph (UDG), and a complete graph with failing probabilities on the nodes (CGFP). We provide an optimal solution for the UDL problem and three approximation algorithms for the UDG problem. For the CGFP problem we outline the two possible structures of an optimal solution and provide near optimal approximation algorithms.
1 Introduction A wireless ad-hoc sensor network consists of several sensors with communication capabilities. The network’s topology is determined by the locations and transmission ranges of the sensors. The ranges determine a directed communication graph, in which the nodes correspond to the sensors and the edges correspond to the communication links. A standard operation for such a network has the sensors monitor their surroundings, and deliver the information to a base station using multi-hop communication. A failure in one node may cause data loss from its neighbors in the graph. A mobile mule may prevent this lose by visiting and collecting data from neighboring nodes. In this paper we investigate the optimal design of the network and the
* Harel Yedidsion [email protected] 1
Ben-Gurion University of the Negev, Beer‑Sheva, Israel
2
National Institute of Science Education and Research, HBNI, Bhubaneswar, India
3
The University of Texas, Austin, USA
13
Vol.:(0123456789)
Algorithmica
placement of the data mule as to minimize its overall traveling distance under additional constraints. 1.1 Problem Definition Formally, the problem is defined as follows: Let G = (V, E) be a graph embedded in the Euclidean plane, where V is the set of wireless nodes, |V| = n , and E is the set of undirected edges between nodes. Let T be a directed data gathering tree rooted at root r, spanning the nodes in V, where data propagates from leaf nodes to r. Consider a mobile entity with wireless capabilities called mule, that visits a subset of nodes Vm ⊆ V and collects the information they sense. The mule can travel anywhere in the plane. Let cd be the mule’s cost of traversing distance d. This cost is proportional to the distance traveled. If a sensor v fails, it is undesirable to lose the data it collected from its children in T, 𝛿(v, T) . Thus, the mule must travel through 𝛿(v, T) and restore the lost information. The mule’s tour through the chi
Data Loading...
