Energy-efficient cooperative data aggregation for wireless sensor networks. (English) Zbl 1233.68096
Summary: Recently, cooperative communication mechanism is shown to be a promising technology to improve the transmit diversity only by a single transceiver antenna. Using this communication paradigm, multiple source nodes are able to coordinate their transmissions so as to obtain energy savings. As data aggregation is one of the most important operations in wireless sensor networks, this paper studies the energy-efficient data aggregation problem through cooperative communication. We first define the cooperative data aggregation (CDA) problem, and formally prove that this problem is NP-hard. Due to the difficult nature of this problem, we propose a heuristic algorithm MCT for cooperative data aggregation. The theoretical analysis shows that this algorithm can reach the approximate performance ratio of 2. Moreover, the distributed implementation DMCT of the algorithm is also described. We prove that both centralized and distributed algorithms can construct the same topology for cooperative data aggregation. The experimental simulations show that the proposed algorithms will decrease the power consumption by about 12.5% and 66.3% compared with PEDAP and PEGASIS algorithms respectively.
MSC:
| 68M14 | Distributed systems |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68W15 | Distributed algorithms |
Keywords:
data aggregation; cooperative communications; energy efficiency; wireless sensor networks; lifetime; heuristic algorithmReferences:
| [1] | Bertsekas, D.; Gallager, R.: Data networks, (1991) · Zbl 0734.68006 |
| [2] | Cardei, M.; Wu, J.; Yang, S.: Topology control in ad hoc wireless networks using cooperative communication, IEEE transactions on mobile computing 5, No. 6 (2006) |
| [3] | M. Enachescu, A. Goel, R. Govindan, R. Motwani, Scale free aggregation in sensor networks, in: Proc. of the First International Workshop on Algorithmic Aspects of Wireless Sensor Networks, 2004. · Zbl 1104.68315 |
| [4] | D. Estrin, R. Govindan, J. Heidemann, S. Kumar, Next century challenges: scalable coordination in sensor networks, in: Proc. of MOBICOM, 1999. |
| [5] | Garey, M. R.; Johnson, D. S.: Computers and intractability; A guide to the theory of NP-completeness, (1979) · Zbl 0411.68039 |
| [6] | Gehrke, J.; Madden, S.: Query processing in sensor networks, Pervasive computing 3, No. 1, 46-55 (2004) |
| [7] | A. Goel, D. Estrin, Simultaneous optimization for concave costs: single sink aggregation or single source buy-at-bulk, in: Proc. of the ACM Symposium on Discrete Algorithms, SODA, 2003. · Zbl 1092.68626 |
| [8] | B. Hohlt, L. Doherty, E. Brewer, Flexible power scheduling for sensor networks, in: Proc. of IPSN, 2004. |
| [9] | Ibrahim, Ahmed S.; Han, Zhu; Liu, K. J. Ray: Distributed energy-efficient cooperative routing in wireless networks, Distributed energy-efficient cooperative routing in wireless networks 7, No. 10, 3930-3941 (2008) |
| [10] | C. Intanagonwiwat, R. Govindan, D. Estrin, Directed diffusion: a scalable and robust communication paradigm for sensor networks, in: Proc. of MOBICOM, 2000. |
| [11] | J. Kahn, R. Katz, K. Pister, Next century challenges: mobile networking for ”smart dust”, in: Proc. of MOBICOM, 1999. |
| [12] | K. Kalpakis, K. Dasgupta, P. Namjoshi, Maximum lifetime data gathering and aggregation in wireless sensor networks, in: Proc. of IEEE International Conference on Networking, 2002. · Zbl 1059.68523 |
| [13] | Khandani, A.; Aboundi, J.; Modiano, E.; Zheng, L.: Cooperative routing in static wireless networks, IEEE transactions on communications 55, No. 11, 2185-2192 (2007) |
| [14] | M. Khan, G. Pandurangan, A fast distributed approximation algorithm for minimum spanning trees, in: Proc. of International Symposium on Distributed Computing, 2006. · Zbl 1155.68562 |
| [15] | B. Krishnamachari, D. Estrin, S. Wicker, Modeling data-centric routing in wireless sensor networks, in: Proc. of IEEE INFOCOM, New York, June 2002. |
| [16] | Laneman, J. N.; Tse, D. N. C.; Wornell, G. W.: Cooperative diversity in wireless networks: efficient protocols and outage behavior, IEEE transactions on information theory 50, No. 12, 3062-3080 (2004) · Zbl 1316.94050 |
| [17] | Lindsey, S.; Raghavendra, C.; Sivalingam, K. M.: Data gathering algorithm in sensor networks using energy metrics, IEEE transaction on parallel and distributed systems 13, 924-932 (2002) |
| [18] | A. Mainwaring, J. Polastre, R. Szewczyk, D. Culler, J. Anderson, Wireless sensor networks for habitat monitoring, in: Proc. of WSNA, September 2002. |
| [19] | Y. Shi, S. Sharma, Y.T. Hou, S. Kompella, Optimal relay assignment for cooperative communications, in: Proc. of MohiHoc, 2008. |
| [20] | Tan, H.; Korpeoglu, I.: Power efficient data gathering and aggregation in wireless sensor networks, SIGMOD record 32, No. 4 (2003) |
| [21] | N. Thepvilojanapong, Y. Tobe, K. Sezaki, On the construction of efficient data gathering tree in wireless sensor networks, in: Proc. of ISCAS, 2005. |
| [22] | A. Woo, T. Tong, D. Culler, Taming the underlying challenges of reliable multihop routing in sensor networks, in: Proc. of SenSys, 2003. |
| [23] | N. Xu, S. Rangwala, K. Chintalapudi, D. Ganesan, A. Broad, R. Govindan, D. Estrin, A wireless sensor network for structural monitoring, in: Proc. of SenSys, 2004. |
| [24] | Zhang, Y.; Huang, Q.: A learning-based adaptive routing tree for wireless sensor networks, Journal of communications 1, No. 2 (2006) |
| [25] | Zhang, J.; Zhang, Q.: Cooperative routing in multi-source multi-destination multi-hop wireless networks, Ieee infocom, 2369-2377 (2008) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
