On the Construction of Data Aggregation Tree with Minimum Energy Cost in Wireless Sensor Networks: NP-Completeness and Approximation Algorithms
In many applications, it is a basic operation for the sink to periodically collect reports from all sensors. Since the data gathering process usually proceeds for many rounds, it is important to collect these data efficiently, that is, to reduce the energy cost of data transmission. Under such applications, a tree is usually adopted as the routing structure to save the computation costs for maintaining the routing tables of sensors. In this paper, we work on the problem of constructing a data aggregation tree that minimizes the total energy cost of data transmission in a wireless sensor network. In addition, we also address such a problem in the wireless sensor network where relay nodes exist and consider the cases where the link quality is not perfect. We show that these problems are NP-complete and proposeOð1Þ-approximation algorithms for each of them. Simulations show that the proposed algorithms have good performance in terms of energy cost.
PROJECT OUTPUT VIDEO: (Click the below link to see the project output video):
In many data aggregation algorithms, a tree is used as the routing structure, especially for applications that have to monitor events continuously. The reason for this is that sensors, which usually have limited resources, can save relatively high computational costs for maintaining routing tables if the sensors route packets based on a tree. While several papers target the maximization of the network lifetime. The problem of minimizing the total energy cost is also well studied in the literature. Moreover, for some indoor applications, the sensors may have AC power plugs. For example, the sensor of the Octopus wireless sensor network. Under such circum-stances or energy conservation activity, energy saving then becomes the major issue.
DISADVANTAGES OF EXISTING SYSTEM:
- Problem of constructing a data aggregation tree with minimum energy cost.
- Decrease Network Lifetime
- We prove the problem of constructing a data aggregation tree with minimum energy cost, termed MECAT, is NP-complete and provide a 2-approximation algorithm.
- We study the variant of such a problem in which the relay nodes exist, termed MECATRN.
- We show that the MECAT RN problem is NP-complete and demonstrate a 7-approximation algorithm.
- We show that any-approximation algorithm of the capacitated network design (CND) problem can be used to obtain a2-approximation algorithm of the MECATRN problem.
- We extend the MECAT problem and the MECATRN problem to cope with cases where the link quality is not perfect and proposeOð1Þ-approxi-mation algorithms.
- We conduct several simulations to evaluate the performance of the proposed algorithms.
ADVANTAGES OF PROPOSED SYSTEM:
- Constructing a data aggregation tree with minimum energy cost.
- Increase Network Lifetime.
- The Network Model
- Approximation Algorithm
- Data Aggregation with Relay Nodes
- Coping With Imperfect Link Quality
- Performance Evaluation
The Network Model
We model a network as an undirected connected graph with weights and associated with each node, respectively, where V is the set of nodes, E is the set of edges, and r is the sink. Each node v has to send a report of sizes to sink r periodically in a multi-hop fashion along the unique path on a routing tree. A routing tree constructed for a network with sink r is a tree with root r. Let Tx and Rx be the energy needed to send and receive a packet, respectively. While routing, a hop-by-hop aggregation is performed according to the aggregation ratio, q, which is the size of the reports that can be aggregated into one packet. Because it would be meaningless if the aggregation ratio is set to a non-integer, the aggregation ratio is assumed to be an integer throughout this paper. It is note-worthy that we implicitly assume that the transmission energy and the receiving energy of a packet are constants.
As the MECAT problem is NP-complete, we provide an approximation algorithm. Observe that while sending a packet to the sink, the longer the routing path is, the greater the energy cost is. Naturally, we would route each packet via a shortest path to the sink. The resulting routing structure is then a shortest path tree. There are at least three benefits to route packets using a shortest path tree. First, a shortest path tree is easy to construct in a distributed manner, as described in the following two steps. The sink node first broadcasts a message such that each node can evaluate the hop distance from the sink. Then, each node sets its parent to the node with a smaller hop distance from the sink. Second, in many time-critical applications, it is necessary to route packets using a shortest path tree to achieve the minimum packet transmission delay. Third, we can construct the shortest path tree even in the case where the aggregation ratio or report sizes are not known or vary from time to time. Although a shortest path tree may not have the minimum energy cost (see Fig. 1 for an example), Theorem 2 shows that a shortest path tree algorithm has an approximation ratio of 2. That is, regardless of the values of the aggregation ratio and the report size, the energy cost of a shortest path tree is no greater than two times the energy cost of the optimum solution.
Data Aggregation with Relay Nodes
To improve the network connectivity or survivability, the relay node placement problem in a wireless sensor network has been extensively investigated in the literature .These relay nodes, which do not produce reports, are used to forward the packets received from other nodes. In this section, we study the problem of constructing a data aggregation tree with minimum energy cost in the presence of relay nodes.
Coping With Imperfect Link Quality
we have implicitly assumed that the link quality is perfect. That is, packet transmission always succeeds. In this section, we first define a new objective function, that is, a new way to calculate energy cost, for the MECAT problem and the MECATRN problem to take the effect of imperfect link quality into consideration. We then propose approximation algorithms for the modified problems.
We study the problem of constructing energy-efficient data aggregation trees.
- System : Pentium Dual Core.
- Hard Disk : 120 GB.
- Monitor : 15’’ LED
- Input Devices : Keyboard, Mouse
- Ram :1 GB
- Operating system : Windows XP/UBUNTU.
- Implementation : NS2
- NS2 Version : 2.28
- Front End : OTCL (Object Oriented Tool Command Language)
- Tool : Cygwin (To simulate in Windows OS)
Tung-Wei Kuo, Kate Ching-Ju Lin, Member, IEEE, and Ming-Jer Tsai, Member, IEEE, “On the Construction of Data Aggregation Tree with Minimum Energy Cost in Wireless Sensor Networks: NP-Completeness and Approximation Algorithm”, IEEE TRANSACTIONS ON COMPUTERS, VOL. 65, NO. 10, OCTOBER 2016