Rate allocation in wireless sensor networks with network lifetime requirement

ABSTRACT

An important performance consideration for wireless sensor networks is the amount of information collected by all the nodes in the network over the course of network lifetime. Since the objective of maximizing the sum of rates of all the nodes in the network can lead to a severe bias in rate allocation among the nodes, we advocate the use of lexicographical max-min (LMM) rate allocation for the nodes. To calculate the LMM rate allocation vector, we develop a polynomial-time algorithm by exploiting the parametric analysis (PA) technique from linear programming (LP), which we call serial LP with Parametric Analysis (SLP-PA). We show that the SLP-PA can be also employed to address the so-called LMM node lifetime problem much more efficiently than an existing technique proposed in the literature. More important, we show that there exists an elegant duality relationship between the LMM rate allocation problem and the LMM node lifetime problem. Therefore, it is sufficient to solve any one of the two problems and important insights can be obtained by inferring duality results for the other problem.

REFERENCES

• 1: I. F. Akyildiz , W. Su , Y. Sankarasubramaniam , E. Cayirci, Wireless sensor networks: a survey, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.38 n.4, p.393-422, 15 March 2002 [doi>10.1016/S1389-1286(01)00302-4]
• 2: Mokhtar S. Bazaraa , John J. Jarvis , Hanif D. Sherali, Linear programming and network flows (2nd ed.), John Wiley & Sons, Inc., New York, NY, 1990
• 3: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 4: M. Bhardwaj and A.P. Chandrakasan, "Bounding the lifetime of sensor networks via optimal role assignments," in Proc. IEEE Infocom, pp. 1587--1596, June 23--27, 2002, New York, NY.
• 5: Douglas M. Blough , Paolo Santi, Investigating upper bounds on network lifetime extension for cell-based energy conservation techniques in stationary ad hoc networks, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570668]
• 6: Timthoy X. Brown , Harold N. Gabow , Qi Zhang, Maximum flow-life curve for a wireless ad hoc network, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501431.501434]
• 7: J.-H. Chang and L. Tassiulas, "Routing for maximum system lifetime in wireless ad-hoc networks," in Proc. 37th Annual Allerton Conference on Communications, Control, and Computing, Sept. 1999, Monticello, IL.
• 8: J.-H. Chang and L. Tassiulas, "Energy conserving routing in wireless ad-hoc networks," in Proc. IEEE Infocom, pp. 22--31, March 26--30, 2000, Tel Aviv, Israel.
• 9: J. Chou, D. Petrovis, and K. Ramchandran, "A distributed and adaptive signal processing approach to reducing energy consumption in sensor networks," in Proc. IEEE Infocom, pp. 1054--1062, April 1--3, 2003, San Francisco, CA.
• 10: Wendi Beth Heinzelman , Anantha P. Chandrakasan , Hari Balakrishnan, Application-specific protocol architectures for wireless networks, 2000
• 11: Y.T. Hou, Y. Shi, and H.D. Sherali, "On rate allocation problem for wireless sensor networks," Technical Report, The Bradley Department of Electrical and Computer Engineering, Virginia Tech, July 2003. Available at http://www.ece.vt.edu/ thou/Research.
• 12: K. Kar, M. Kodialam, T.V. Lakshman, and L. Tassiulas, "Routing for network capacity maximization in energy-constrained ad-hoc networks," in Proc. IEEE Infocom, pp. 673--681, April 1--3, 2003, San Francisco, CA.
• 13: K. Kalpakis, K. Dasgupta, and P. Namjoshi, "Maximum lifetime data gathering and aggregation in wireless sensor networks," in Proc. IEEE International Conference on Networking (ICN'02), pp. 685--696, Aug. 26--29, 2002, Atlanta, GA.
• 14: H. Luss and D.R. Smith, "Resource allocation among competing activities: a lexicographic minimax approach," Operations Research Letters, vol. 5, no. 5, pp. 227--231, Nov. 1986.
• 15: S.S. Pradhan, J. Kusuma, and K. Ramchandran, "Distributed compression in a dense sensor network," IEEE Signal Processing Magazine, vol. 19, no. 2, pp. 51--60, March 2002.
• 16: R. Ramanathan and R. Rosales-Hain, "Topology control of multihop wireless networks using transmit power adjustment," in Proc. IEEE Infocom, pp. 404--413, March 26--30, 2000, Tel Aviv, Israel.
• 17: K. Ramchandran, "Distributed sensor networks: opportunities and challenges in signal processing and communications," presentation at NSF Workshop on Distributed Communications and Signal Processing for Sensor Networks, Dec. 2002, Evanston, IL. Available at http://www.ece.northwestern.edu/ pappas/nsf_workshop/presentations/ramchandran_workshop_DDSP.ppt.
• 18: Theodore S. Rappaport, Wireless Communications: Principles and Practice, IEEE Press, Piscataway, NJ, 1996
• 19: V. Rodoplu and T.H. Meng, "Minimum energy mobile wireless networks," IEEE Journal on Selected Areas in Communications, vol. 17, no. 8, pp. 1333--1344, Aug. 1999.
• 20: V. Srinivasan, P. Nuggehalli, C.F. Chiasserini, and R. Rao, "Cooperation in wireless ad hoc networks," in Proc. IEEE Infocom, pp. 808--817, April 1--3, 2003, San Francisco, CA.
• 21: R. Wattenhofer, L. Li, P. Bahl, and Y.-M. Wang, "Distributed topology control for power efficient operation in multihop wireless ad hoc networks," in Proc. IEEE Infocom, pp. 1388--1397, April 22--26, 2001, Anchorage, AK.
• 22: G. Zussman and A. Segall, "Energy efficient routing in ad hoc disaster recovery networks," in Proc. IEEE Infocom, pp. 405--421, April 1--3, 2003, San Francisco, CA.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications

General Terms:
Algorithms, Performance, Theory

Keywords:
energy constraint, flow routing, lexicographic max-min, linear programming, network capacity, node lifetime, parametric analysis, rate allocation, wireless sensor networks