6533b7d0fe1ef96bd125aeaa

RESEARCH PRODUCT

Maximum Lifetime of the Wireless Sensor Network and the Gossip Problem

subject

description

In the gossip problem each node of the graph G possesses a unique piece of information - the gossip message. A sequence of one-way or two-way communications between pair of nodes is made to spread the messages so that any node of the graph knows all the gossips. The question is, what is the minimum number of calls between pairs of nodes needed to exchange all gossip messages? The solution to the two-way communication gossip problem is that \(2N-4\) calls (\(N\ge 4\)) suffice if and only if the graph contains a four cycle subgraph. For one-way communication problem the classical results states that in a strongly connected graph \(2N-2\) calls (\(N\ge 4\)) suffice. In this paper we consider the gossip problem in the context of saving the energy consumed by the sensor network nodes. In the process of gossiping the network nodes consume their energy resources. The amount of consumed energy depends on the cost of transmission between pairs of nodes, a selected transmission route and the sizes of the gossip messages. For the fixed size of gossip messages and the fixed cost of transmission of one unit of data between pairs of nodes we search for the optimal transmission route of the gossip messages such that the most overloaded node consumes the minimum amount of energy. We define the network lifetime for the gossiping process as the time until the first node of the network runs out of its energy. By minimizing the energy of the most overloaded node we obtain the solution to the network lifetime gossiping problem. In the paper we solve the problem for the one-dimensional regular sensor network. We propose a load balancing algorithm for solving the problem in networks with evenly distributed sensors in a given area such that an equal energy solution of the problem exists. We also propose a data aggregation scheduling algorithm to calculate the minimum number of calls necessary to spread the gossip messages for a given solution of the network lifetime gossiping problem.