Improved Solution to Data Gathering with Mobile Mule
- PDF / 5,598,664 Bytes
- 40 Pages / 439.37 x 666.142 pts Page_size
- 25 Downloads / 189 Views
Improved Solution to Data Gathering with Mobile Mule Yoad Zur1 · Michael Segal1 Received: 17 September 2019 / Accepted: 22 April 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract In this work we study the problem of collecting protected data in ad-hoc sensor network using a mobile entity called MULE. The objective is to increase information survivability in the network. Sensors from all over the network, route their sensing data through a data gathering tree, towards a particular node, called the sink. In case of a failed sensor, all the aggregated data from the sensor and from its children is lost. In order to retrieve the lost data, the MULE is required to travel among all the children of the failed sensor and to re-collect the data. There is a cost to travel between two points in the plane. We aim to minimize the MULE traveling cost, given that any sensor can fail. In order to reduce the traveling cost, it is necessary to find the optimal data gathering tree and the MULE location. We are considering the problem for the unit disk graphs and Euclidean distance cost function. We propose a primal–dual algorithm that produces a (20 + 𝜀)-approximate solution for the problem, where( 𝜀 → 0 as)the sensor network spreads over a larger area. The algorithm requires O n3 ⋅ 𝛥(G) time to construct a gathering tree and to place the MULE, where 𝛥(G) is the maximum degree in the graph and n is the number of nodes. Keywords WSN · MULE · MWCDS · Primal–dual · UDG
1 Introduction Consider an Ad-Hoc sensor network randomly embedded in the plane. An example application is the use of sensors scattered in forests using aircraft, to give an indication when a fire starts. The main problem in WSN is long-term survivability. Because of the limited energy of a sensor, its lifetime depends on its energy consumption. A standard solution for efficient utilization of energy is to build a data * Michael Segal [email protected] Yoad Zur [email protected] 1
Communication Systems Engineering Department, School of Electrical and Computer Engineering, Ben-Gurion University of the Negev, Beersheba, Israel
13
Vol.:(0123456789)
Algorithmica
gathering tree in the network. In this method, the data is aggregated in order to reduce the number of messages each sensor transmits. The sensors create a logical construction of a tree in the network, and all the data routed to the sink according to that tree. The basic principle of the data aggregation is that each sensor waits to aggregate the data from all its children before it sends its own message to its father. Failure is defined as a sensor that runs out of energy. When a sensor failure occurs, all the aggregated data from the sensor and its children are lost. Also, if the sensor is not a leaf in the tree, its entire subtree is disconnected. It takes a long time to recognize the fault, and for the network to reconstruct a new gathering tree. Here comes the use of data MULE to retrieve the lost data. Data MULE is a mobile unit provided with extended computing and
Data Loading...
