Open Access Open Access  Restricted Access Subscription or Fee Access

Rate Allocation and Network Lifetime Problems for Wireless Sensor Networks

K. Venkatesh Sharma, K. Hanumantha Rao, S. Rajendra Prasad

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. To calculate the LMM rate allocation vector, we develop a polynomial-time algorithm by exploiting the parametric analysis (PA) technique from linear program (LP), which we call serial LP with Parametric Analysis (SLP-PA). We show that the SLP-PA can be also employed to address the LMM node lifetime problem much more efficiently than a state-of-the-art algorithm 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 only one of the two problems. Important insights can be obtained by inferring duality results for the other problem

.


Keywords


Energy Constraint, Flow Routing, Lexicographic Max-Min, Linear Programming, Network Capacity, Node Lifetime, Parametric Analysis, Rate Allocation, Sensor Networks, Theory.

Full Text:

PDF

References


F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “Wireless sensor networks: A survey,” Comput. Netw. (Elsevier), vol. 38, no. 4, pp. 393–422, 2002.

M. S. Bazaraa, J. J. Jarvis, and H. D. Sherali, Linear Programming and Network Flows, 2nd ed. New York: Wiley, 1990, ch. 4, 6, and 8.

D. Bertsekas and R. Gallager, Data Networks. Englewood Cliffs, NJ: Prentice Hall, 1992, ch. 6.

M. Bhardwaj and A. P. Chandrakasan, “Bounding the lifetime of sensor networks via optimal role assignments,” in Proc. IEEE INFOCOM, New York, Jun. 23–27, 2002, pp. 1587–1596.

D. Blough and S. Paolo, “Investigating upper bounds on network lifetime extension for cell-based energy conservation techniques in stationary ad hoc networks,” in Proc. ACM MobiCom, Atlanta, GA, Sep. 23–28, 2002, pp. 183–192.

T. X. Brown, H. N. Gabow, and Q. Zhang, “Maximum flow-life curve for a wireless ad hoc network,” in Proc. ACM MobiHoc, Long Beach, CA, Oct. 4–5, 2001, pp. 128–136.

J.-H. Chang and L. Tassiulas, “Routing for maximum system lifetime in wireless ad hoc networks,” in Proc. 37th Annu. Allerton Conf. Communications, Control, and Computing, Monticello, IL, Sep. 1999, vol. 1, pp. 22–31.

J.-H. Chang and L. Tassiulas, “Energy conserving routing in wireless ad hoc networks,” in Proc. IEEE INFOCOM, Tel Aviv, Israel, Mar. 26–30, 2000, pp. 22–31.

W. Heinzelman, “Application-specific protocol architectures for wireless networks,” Ph.D. dissertation, Massachusetts Inst. Technol., Cambridge, MA, Jun. 2000.

Y. T. Hou, Y. Shi, and H. D. Sherali, “On node lifetime problem for energy-constrained wireless sensor networks,” ACM/Springer Mobile Netw. Applicat., vol. 10, no. 6, pp. 865–878, Dec. 2005.

Y. T. Hou, Y. Shi, J. H. Reed, and K. Sohraby, “Flow routing for variable bit rate source nodes in energy-constrained wireless sensor networks,” in Proc. IEEE Int. Conf. Communications, Seoul, Korea, May 16–20, 2005, pp. 3057–3062.

K. Kalpakis, K. Dasgupta, and P. Namjoshi, “Maximum lifetime data gathering and aggregation in wireless sensor networks,” in Proc. IEEE Int. Conf. Networking (ICN’02), Atlanta, GA, Aug. 26–29, 2002, pp.685–696.

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, San Francisco, CA, Mar. 30–Apr. 3 2003, pp. 673–681.

H. Luss and D. R. Smith, “Resource allocation among competing activities: A lexicographic minimax approach,” Oper.s Res. Lett., vol. 5, no. 5, pp. 227–231, Nov. 1986.

R. Ramanathan and R. Rosales-Hain, “Topology control of multihop wireless networks using transmit power adjustment,” in Proc. IEEE INFOCOM, Tel Aviv, Israel, Mar. 26–30, 2000, pp. 404–413.

T. S. Rappaport,Wireless Communications: Principles and Practice. Englewood Cliffs, NJ: Prentice Hall, 1996.

V. Rodoplu and T. H. Meng, “Minimum energy mobile wireless networks,” IEEE J. Sel. Areas Commun., vol. 17, no. 8, pp. 1333–1344, Aug. 1999.

K. Sohrabi, J. Gao, V. Ailawadhi, and G. Pottie, “Protocols for selforganizing of a wireless sensor network,” IEEE Pers. Commun. Mag., vol. 7, pp. 16–27, Oct. 2000.

V. Srinivasan, P. Nuggehalli, C. F. Chiasserini, and R. Rao, “Cooperation in wireless ad hoc networks,” in Proc. IEEE INFOCOM, San Francisco, CA, Mar. 30–Apr. 3 2003, pp. 808–817.

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, Anchorage, AK, Apr. 22–26, 2001, pp. 1388–1397.

G. Zussman and A. Segall, “Energy efficient routing in ad hoc disaster recovery networks,” in Proc. IEEE INFOCOM, San Francisco, CA, Mar. 30–Apr. 3 2003, pp. 405–421.


Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.