skip to main content
article

Optimal routing and data aggregation for maximizing lifetime of wireless sensor networks

Published: 01 August 2008 Publication History

Abstract

An optimal routing and data aggregation scheme for wireless sensor networks is proposed in this paper. The objective is to maximize the network lifetime by jointly optimizing data aggregation and routing. We adopt a model to integrate data aggregation with the underlying routing scheme and present a smoothing approximation function for the optimization problem. The necessary and sufficient conditions for achieving the optimality are derived and a distributed gradient algorithm is designed accordingly. We show that the proposed scheme can significantly reduce the data traffic and improve the network lifetime. The distributed algorithm can converge to the optimal value efficiently under all network configurations.

References

[1]
K. Sohrabi, J. Gao, V. Ailawadhi, and G. J. Pottie, "Protocols for self-organization of a wireless sensor network," IEEE Pers. Commun., vol. 7, no. 5, pp. 16-27, Oct. 2000.
[2]
Y. Xu, J. S. Heidemann, and D. Estrin, "Geography-informed energy conservation for ad hoc routing," in Proc. MobiCom, 2001, pp. 70-84.
[3]
B. Chen, K. Jamieson, H. Balakrishnan, and R. Morris, "Span: An energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks," in Proc. MobiCom, 2001, pp. 85-96.
[4]
L. Li, J. Y. Halpern, P. Bahl, Y.-M. Wang, and R. Wattenhofer, "Analysis of a cone-based distributed topology control algorithm for wireless multi-hop networks," in Proc. ACM Symp. Principles Distrib. Comput., 2001, pp. 264-273.
[5]
N. Li, J. C. Hou, and L. Sha, "Design and analysis of an MST-based topology control algorithm," in Proc. IEEE INFOCOM, 2003, pp. 1702-1712.
[6]
W. Heinzelman, A. Chandrakasan, and H. Balakrishnan, "Energy-efficient communication protocol for wireless microsensor networks," in Proc. Int. Conf. Syst. Sci., 2000.
[7]
S. Singh, M. Woo, and C. S. Raghavendra, "Power-aware routing in mobile ad hoc networks," in Proc. MobiCom, 1998, pp. 181-190.
[8]
T. H. Meng and V. Rodoplu, "Minimum energy mobile wireless networks," IEEE J. Sel. Areas Commun., vol. 16, no. 8, pp. 1333-1344, Aug. 1999.
[9]
J.-H. Chang and L. Tassiulas, "Energy conserving routing in wireless ad hoc networks," in Proc. IEEE INFOCOM, 2000, pp. 22-31.
[10]
A. Sankar and Z. Liu, "Maximum lifetime routing in wireless ad hoc networks," in Proc. IEEE INFOCOM, Mar. 2004, pp. 1089-1097.
[11]
R. Madan and S. Lall, "Distributed algorithms for maximum lifetime routing in wireless sensor networks," in Proc. IEEE GLOBECOM, Nov. 2004, vol. 2, pp. 748-753.
[12]
J. Pan, Y. T. Hou, L. Cai, Y. Shi, and S. X. Shen, "Topology control for wireless sensor networks," in Proc. MobiCom, 2003, pp. 286-299.
[13]
Y. Xue, Y. Cui, and K. Nahrstedt, "A utility-based distributed maximum lifetime routing algorithm for wireless networks," in Proc. 2nd Int. Conf. QoS Heterogeneous Wired/Wireless Networks, 2005, p. 18.
[14]
K. Kalpakis, K. Dasgupta, and P. Namjoshi, "Maximum lifetime data gathering and aggregation in wireless sensor networks," in Proc. ICN, Aug. 2002, pp. 685-696.
[15]
S. Pattem, B. Krishnamachari, and Ramesh, "The impact of spatial correlation on routing with compression in wireless sensor networks," in Proc. IPSN, Berkeley, CA, 2004, pp. 28-35.
[16]
R. Cristescu, B. Beferull-Lozano, and M. Vetterli, "On network correlated data gathering," in Proc. IEEE INFOCOM, Hong Kong, 2004, pp. 2571-2582.
[17]
P. von Rickenbach and R. Wattenhofer, "Gathering correlated data in sensor networks," in Proc. DIALM-POMC, New York, 2004, pp. 60-66.
[18]
M. Mauve, J. Widmer, and H. Hartenstein, "A survey on position-based routing in mobile ad hoc networks," IEEE Network, vol. 15, no. 6, pp. 30-39, Nov. 2001.
[19]
L. Doherty, L. El Ghaoui, and K. S. J. Pister, "Convex position estimation in wireless sensor networks," in Proc. IEEE INFOCOM, Apr. 2001, pp. 1655-1663.
[20]
Y. Shang, W. Ruml, Y. Zhang, and M. P. J. Fromherz, "Localization from mere connectivity," in Proc. MobiCom, Jun. 2003, pp. 201-212.
[21]
C. Q. Hua and T. S. Yum, "Optimal routing and data aggregation for maximizing lifetime of wireless sensor networks," Inf. Eng. Dept., Chinese Univ. of Hong Kong, Tech. Rep., 2005.
[22]
M. C. Vuran, O. B. Akan, and I. F. Akyildiz, "Spatio-temporal correlation: Theory and applications for wireless sensor networks," Comput. Netw., vol. 45, no. 3, p. 245, 2004.
[23]
M. C. Vuran and O. B. Akan, "Spatio-temporal characteristics of point and field sources in wireless sensor networks," in Proc. IEEE ICC, Istanbul, Turkey, Jun. 2006, pp. 234-239.
[24]
R. K. Ahuja, "Algorithms for the minimax transportation problem," Nav. Res. Logist., vol. 33, pp. 725-740, 1986.
[25]
A. Ben-Tal and M. Teboulle, "A smoothing technique for nondifferentiable optimization problems," in Proc. Int. Seminar Optimiz., New York, 1988, pp. 1-11.
[26]
X. Li, "An entropy-based aggregate method for minmax optimization," Eng. Optimiz., vol. 18, pp. 277-285, 1992.
[27]
C. Chen and O. L. Mangasarian, "Smoothing methods for convex inequalities and linear complementarity problems," Math. Program., vol. 71, no. 1, pp. 51-69, 1995.
[28]
S. I. Birbil, S.-C. Fang, J. B. G. Frenk, and S. Zhang, "Recursive approximation of the high dimensional max function," Oper. Res. Lett., vol. 33, pp. 450-458, 2005.
[29]
L. Qi and D. Sun, "Smoothing functions and a smoothing newton method for complementarity and variational inequality problems," J. Optimiz. Theory Appl., vol. 113, pp. 121-147, 2002.
[30]
D. P. Bertsekas and J. N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods. Belmont, MA: Athena Scientific, 1997.
[31]
R. G. Gallager, "A minimum delay routing algorithm using distributed computation," IEEE Trans. Commun., vol. COM-25, no. 1, pp. 73-85, Jan. 1977.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking
IEEE/ACM Transactions on Networking  Volume 16, Issue 4
August 2008
249 pages

Publisher

IEEE Press

Publication History

Published: 01 August 2008
Revised: 09 June 2006
Received: 25 July 2005
Published in TON Volume 16, Issue 4

Author Tags

  1. data aggregation
  2. maximum lifetime routing
  3. network lifetime
  4. smoothing methods
  5. wireless sensor networks

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)2
  • Downloads (Last 6 weeks)0
Reflects downloads up to 16 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2021)Topology control game algorithm based on Markov lifetime prediction model for wireless sensor networkAd Hoc Networks10.1016/j.adhoc.2018.05.00678:C(13-23)Online publication date: 23-Aug-2021
  • (2021)Agent Based Spider-Net Information Gathering in Wireless Sensor NetworksWireless Personal Communications: An International Journal10.1007/s11277-021-08172-1118:4(3145-3166)Online publication date: 1-Jun-2021
  • (2021)Q-learning based routing for in-network aggregation in wireless sensor networksWireless Networks10.1007/s11276-021-02564-827:3(2231-2250)Online publication date: 1-Apr-2021
  • (2019)Data censoring with network lifetime constraint in wireless sensor networksDigital Signal Processing10.1016/j.dsp.2019.05.00492:C(73-81)Online publication date: 1-Sep-2019
  • (2019)Energy provisioning in wireless rechargeable sensor networks with limited knowledgeWireless Networks10.1007/s11276-019-01948-125:6(3531-3544)Online publication date: 1-Aug-2019
  • (2018)Quality of service control in proactive wireless sensor networks via lifetime planningInternational Journal of Sensor Networks10.1504/IJSNET.2018.09048626:4(252-268)Online publication date: 1-Jan-2018
  • (2018)Research on Monitoring and Prewarning System of Accident in the Coal Mine Based on Big DataScientific Programming10.1155/2018/93087422018(8)Online publication date: 1-Mar-2018
  • (2018)Trust Based Intrusion Detection Technique to Detect Selfish Nodes in Mobile Ad Hoc NetworksWireless Personal Communications: An International Journal10.1007/s11277-018-5804-4101:4(2029-2052)Online publication date: 1-Aug-2018
  • (2017)Lossless In-Network Processing and Its Routing Design in Wireless Sensor NetworksIEEE Transactions on Wireless Communications10.1109/TWC.2017.272451616:10(6528-6542)Online publication date: 1-Oct-2017
  • (2017)A Survey of Network Lifetime Maximization Techniques in Wireless Sensor NetworksIEEE Communications Surveys & Tutorials10.1109/COMST.2017.265097919:2(828-854)Online publication date: 2-Jun-2017
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media