AN APPROXIMATION ALGORITHM FOR THE MAXIMUM-LIFETIME DATA AGGREGATION TREE PROBLEM IN WIRELESS SENSOR NETWORKS
ABSTRACT
This paper studies the problem of constructing maximum-lifetime data aggregation trees in wireless sensor networks for collecting sensor readings. This problem is known to beNP-hard. Wireless sensor networks in which transmission power levels of sensors are adjustable and heterogeneous are considered.An approximation algorithm is developed to construct a data aggregation tree whose inverse lifetime is guaranteed to be within a bound from the optimal one. Adjustable transmission power levels of the sensors introduces an additional term in the bound compared with the bound for networks in which transmission power levels of all sensors are fixed. The additional term is proportionalto the difference between the maximum and minimumamounts of energy for a sensor to transmit a message using respectively its maximum and minimum transmission powerlevels. The proposed algorithm is further enhanced to obtain an improved version. Simulation results show that properlyadjusting transmission power levels of the sensors yields higherlifetime of the network than keeping their transmission powerlevels at the maximum level.
CONCLUSIONS
The problem of finding maximum-lifetime data aggregationtrees in sensor networks has been studied in this paper. Sensornetworks in which the transmission power levels of the sensorsare heterogeneous and adjustable have been considered. Lowerbounds on the inverse lifetime (or normalized load) of theoptimal data aggregation tree have been derived, which areequivalent to upper bounds on the lifetime of the optimaldata aggregation tree. An approximation algorithm has beendeveloped to construct a data aggregation tree whose inverselifetime (or normalized load) is guaranteed to be within abound from that of the optimal data aggregation tree. As aresult of adjustable transmission power levels of the sensors,the bound includes a term that is proportional to the differencebetween the maximum and minimum amounts of energy for asensor to transmit a message using respectively its maximumand minimum transmission power levels.The proposed algorithm consists of a novel method toclassify the nodes into heavily, medium, and lightly loadednodes, and an innovative technique for reducing the loads ofheavily loaded nodes. Additional techniques have been usedto enhance the proposed algorithm to become an improvedversion. Simulations have been carried out to show the advantageof adjustable transmission power levels over fixed thetransmission power levels of the sensors at their maximumlevels. The improved version of the proposed algorithm hasalso been shown to be able to further increase the lifetime ofthe network.
REFERENCES
[1] A. Mainwaring, J. Polastre, R. Szewczyk, D. Culler, and J. Anderson,“Wireless sensor networks for habitat monitoring,” Proc. 1st ACM Int.Workshop Wireless Sensor Networks and Appl. (WSNA), pp. 88-97, Sept.2002.
[2] N. Xu et al., “A wireless sensor network for structural monitoring,” Proc.ACM Conf. Embedded Networked Sensor Systems (SenSys), Nov. 2004,pp. 13-24.
[3] G. Tolle et al., “A macroscope in the redwoods,” Proc. ACM Conf. onEmbedded Networked Sensor Systems (SenSys), pp. 51-63, Nov. 2005,pp. 51-63.
[4] S. Madden, R. Szewczyk, M. J. Franklin, and D. Culler, “Supportingaggregate queries over ad-hoc wireless sensor networks,” Proc. 4th IEEEWorkshop on Mobile Computing and Syst. Appl., June 2002, pp. 49-58.
[5] H.¨O. Tan and˙I K¨orpeoˇglu, “Power efficient data gathering and aggre-gation in wireless sensor networks,” ACM SIGMOD Record, vol. 32, no.4, pp. 66-71, Dec. 2003.
[6] C. Buragohain, D. Agrawal, and S. Suri, “Power aware routing for sensordatabases,” Proc. 24th Annu. Joint Conf. IEEE Comput. and Commun.Soc. (INFOCOM), vol. 3, 2005, pp. 1747-1757.
[7] S. Hussain and O. Islam, “An energy efficient spanning tree based multihoprouting in wireless sensor networks,” Proc. IEEE Wireless Commun.and Networking Conf. (WCNC), 2007, pp. 4386-4391.
[8] W. Liang and Y. Liu, “Online data gathering for maximizing networklifetime in sensor networks,” IEEE Trans. Mobile Comput., vol. 6, no. 1,pp. 2-11, Jan. 2007.
[9] H. C. Lin, F. J. Li, and K. Y. Wang, “Constructing maximum-lifetime datagathering trees in sensor networks with data aggregation,” Proc. IEEE Int.Conf. Commun. (ICC), May 2010.
[10] Y. Wu, Z. Mao, S. Fahmy, and N. B. Shroff, “Constructing maximumlifetimedata-gathering forests in sensor networks,” IEEE/ACM Trans.Netw., vol. 18, no. 5, pp. 1571-1584, Oct. 2010.
[11] A. Behzadan, A. Anpalagan, and B. Ma, “Prolonging network lifetimevia nodal energy balancing in heterogeneous wireless sensor networks,”Proc. IEEE Int. Conf. Commun. (ICC), 2011, pp. 1-5.