Title

Distributed Power Control in Wireless Networks

Translated Titles

無線網路上分散式傳輸電力控制之研究

DOI

10.6843/NTHU.2008.00599

Authors

陳俊嘉

Key Words

電力控制 ; 子集合選取 ; 服務品質 ; 連線允許控制 ; 資料聚集 ; 無線感應網路 ; Power Control ; subset selection ; quality of service ; connection admission control ; data aggregation ; wireless sensor networks

PublicationName

清華大學資訊工程學系所學位論文

Volume or Term/Year and Month of Publication

2008年

Academic Degree Category

博士

Advisor

李端興

Content Language

英文

Chinese Abstract

無線網路主要的特性就是稀有的無線資源和移動裝置或無線感應器的有限電池能量。並且,一個電力控制的無線網路頻寬會隨著使用者的移動、訊號的衰減和屏蔽效應等因素而改變。因此,無線網路中無法保證所有的使用者都可以維持他們的服務品質或是訊號品質。在這個研究中,我們提出一個二階段分散式的子集合的選擇方法,用來找出一子集合的無線使用者,使得他們的服務品質可以被保證。在第一個階段,我們的方法可以找出一個基本可行的集合,然後在第二階段,再將這個基本可行的集合擴大。針對預防無資源可用的使用者,我們討論在電力領域和時間領域的衝突解決方式。經過模擬,我們可以在平均可行的連線個數、平均執行的時間上和最大等待時間等方面來檢驗我們所提方法的效能。 在跨層設計這方面的研究,我們考慮無線感應式網路,因為無線感應網路能夠用來探測環境的現象,所以受到愈來愈多的重視。因為每一個無線感應裝置都有有限的電力,如何能有效的利用電力在設計無線感應網路相關協定上是相當重要的課題。在無線感應網路中,資料匯集是可以有效降低電力消耗的方法之一。在這個研究上,我們提出一個結合資料匯集跨層的方法,這個方法可以最小化電力消耗。最重要的是,我們提出來的方法是分散式的,因此很適合用於無線感應網路上。從數值分析上,我們得到一個結論,並不是所有的資料都在被送至目的地前都需要被匯集才可以達到最省電。除此之外,我們透過模擬,評估我們方法帶給網路使用期的長短。

English Abstract

The main characteristics of wireless networks are the scarce radio resource and the limited battery of mobile stations or wireless sensors. The capacity of a power controlled wireless network can be changing due to user's mobility, fading or shadowing effects. As a result, the quality of service (QOS) of all users may not be guaranteed in a wireless network. In this study, we propose a two-phase distributed subset selection algorithm to identify a subset of wireless users whose QOS is guaranteed. In the first phase, it finds a basic feasible set, and then it tries to expand the basic feasible set in the second phase. For starvation prevention, we discuss conflict resolution in the power domain and in the time domain. Through simulations we evaluate the performance of the proposed scheme in terms of the number of average feasible links, the average execution time and maximum of the cycle time. In the study of cross-layer design, we consider the wireless sensor networks since wireless sensor networks attract more and more attention due to being capable of monitoring the environment. Since wireless sensor nodes typically have limited energy and power, power efficiency is a main concern in designing protocols for wireless sensor networks. Data aggregation is one of the strategies that can reduce the power consumption in wireless sensor networks. In this study, we propose a distributed cross- layer algorithm with data aggregation to minimize the power consumption. Most importantly, our proposed algorithm is distributed and therefore, it is suitable for wireless sensor networks. From numerical results, we conclude that not all data packets should be aggregated before they arrive the destination nodes. In addition, we evaluate the performance of our proposed algorithm in the network lifetime.

Topic Category 基礎與應用科學 > 資訊科學
電機資訊學院 > 資訊工程學系所
Reference
  1. [2] A. K. Parekh and R. G. Gallager, ``A generalized processor sharing approach to flow control in integrated services networks: the single-node case," IEEE/ACM Trans. Networking, vol. 1, pp. 344 - 357, June 1993.
    連結:
  2. [3] A. K. Parekh and R. G. Gallager, ``A generalized processor sharing approach to flow control in integrated services networks: the multiple node case," IEEE/ACM Trans. Networking, vol. 2, pp. 137 - 150, April 1994.
    連結:
  3. [4] J. C. Bennett and H. Zhang, ``Wf2q: worst-case fair weighted fair queueing," in Proc. IEEE INFOCOM, pp. 120-128, 1996.
    連結:
  4. [5] S. J. Golestani, ``A self-clocked fair queueing scheme for broadband applications," in Proc. IEEE INFOCOM, pp. 636-646, 1994.
    連結:
  5. [6] M. Schwartz, Broadband Integrated Networks. Prentice Hall, 1996.
    連結:
  6. [7] J. Zander, ``Optimum global transmitter power control in cellular radio systems," pp. 24 - 27, September 1991.
    連結:
  7. [8] S. A. Grandhi, R. Vijayan, D. J. Goodman, and J. Zander, ``Centralized power control in cellular radio systems," IEEE Trans. Vehicular Technology, vol. 42, pp. 466-468, November 1993.
    連結:
  8. [9] J. Zander, ``Performance of optimum transmitter power control in cellular radio systems," IEEE Trans. Vehicular Technology, vol. 41, pp. 57-62, February 1992.
    連結:
  9. [10] J. Zander, ``Distributed cochannel interference control in cellular radio systems," IEEE Trans. Vehicular Technology, vol. 41, pp. 305-311, August 1992.
    連結:
  10. [12] S. A. Grandhi, R. Vijayan, and D. J. Goodman, ``Distributed power control in cellular radio systems," IEEE Trans. Commun., vol. 42, pp. 226-228, February/March/April 1994.
    連結:
  11. [13] G. J. Foschini and Z. Miljanic, ``A simple distributed autonomous power control algorithm and its convergence," IEEE Trans. Vehicular Technology, vol. 42,
    連結:
  12. pp. 641-646, November 1993.
    連結:
  13. [14] R. D. Yates, ``A framework of uplink power control in cellular radio systems," IEEE J. Selected Areas Commun., vol. 13, pp. 1341-1347, Sept. 1995.
    連結:
  14. [15] R. D. Yates and C.-Y. Huang, ``Integrated power control and base station assignment," IEEE Trans. Vehicular Technology, vol. 44, pp. 638-644, August 1995.
    連結:
  15. [16] S. V. Hanly, ``An algorithm for combined cell-site selection and power control to maximize cellular spread spectrum capacity," IEEE Journal Selected Areas in Communications, vol. 13, pp. 1332-1340, September 1995.
    連結:
  16. [17] N. D. Bambos, S. C. Chen, and G. J. Pottie, ``Radio link admission algorithm for wireless networks with power control and active link quality protection," in Proc. IEEE INFOCOM, (Boston, MA), pp. 97-104, April 1995.
    連結:
  17. [18] N. Bambos, S. C. Chen, and G. J. Pottie, ``Channel access algorithms with active link protection for wireless communication networks with power control," IEEE/ACM Trans. Networking, vol. 8, pp. 583-597, October 2000.
    連結:
  18. [19] M. Xiao, N. B. Shro□, and E. K. P. Chong, ``Distributed admisstion control for power-controlled cellular wireless systems," IEEE/ACM Trans. Networking, vol. 9, pp. 790 - 800, December 2001.
    連結:
  19. [20] T. ElBatt and A. Ephremides, ``Joint scheduling and power control for wireless ad hoc networks," IEEE Trans. Wireless Communications, vol. 3, pp. 74-85, January 2004.
    連結:
  20. [21] R. L. Cruz and A. V. Santhanam, ``Optimal link scheduling and power control in cdma multihop wireless networks," in Proc. IEEE Globecom, pp. 52-56, 2002.
    連結:
  21. [22] M. Andersin, Z. Rosberg, and J. Zander, ``Gradual removals in cellular pcs with constrained power control and noise," Wireless Networks, vol. 2, pp. 27-43, January 1996.
    連結:
  22. [24] N. Bambos, S. C. Chen, and D. Mitra, ``Channel probing for distributed access control in wireless communication networks," in Proc. IEEE Globecom, pp. 322-326, 1995.
    連結:
  23. [25] M. J. Neely, E. Modiano, and C. E. Rohrs, ``Power allocation and routing in multibeam satellites with time-varying channels," Networking, IEEE/ACM Transactions on, vol. 11, pp. 138-152, February 2003.
    連結:
  24. [26] F. P. Kelly, A. Maulloo, and D. Tan, ``Rate control in communication networks: Shadow price, proportional fairness and stability," Journal of the Operational Research Society, vol. 49, pp. 237-252, 1998.
    連結:
  25. [27] H. Yaiche, R. Mazumdar, and C. Rosenberg, ``A game theoretic framework for bandwidth allocation and pricing in broadband networks," Networking, IEEE/ACM Transactions on, vol. 8, pp. 667-678, Oct. 2000.
    連結:
  26. [28] S. H. Low and D. E. Lapsley, ``Optimization flow control-I: Basic algorithm and convergence," Networking, IEEE/ACM Transactions on, vol. 7, pp. 861-874, Dec. 1999.
    連結:
  27. [29] S. H. Low and R. Srikant, ``A mathematical framework for designing a low-loss low-delay internet," Network and Spatial Economics, vol. 4, pp. 75-102, March 2004.
    連結:
  28. [30] S. Kunniyur and R. Srikant, ``End-to-end congestion control scheme: Utility function, random losses and ecn marks," in IEEE INFOCOM, 2000.
    連結:
  29. [31] R. Srikant, The Mathematics of Internet Congestion Control. Birkhauser, 2004.
    連結:
  30. [32] X. Liu, K. P. Chong, and N. B. Shroff, ``Opportunistic transmission scheduling with resource-shared constraints in wireless networks," IEEE Journal on Selected Areas in Communications, vol. 19, October 2001.
    連結:
  31. [33] X. Liu, K. P. Chong, and N. B. Shroff, ``A framework for opportunistic scheduling in wireless networks," Computer Networks, vol. 41, pp. 451-474, March 2003.
    連結:
  32. [35] L. Chen, S. H. Low, and J. C. Doyle, ``Joint congestion control and media access control design for wireless ad hoc networks," in IEEE INFOCOM, 2005.
    連結:
  33. [36] X. Lin and N. B. Shroff, ``Joint rate control and scheduling in multihop wireless networks," in IEEE Conference on Decision and Control, 2004.
    連結:
  34. [37] A. Eryilmaz and R. Srikant, ``Joint congestion control, routing and mac for stability and fairness in wireless networks," in International Zurich Seminar on Communicatins, 2006.
    連結:
  35. [38] M. Johansson and L. Xiao, ``Scheduling, routing and power allocation for fairness in wireless networks," in IEEE VTC - Spring, 2004.
    連結:
  36. [39] M. J. Neely, E. Modiano, and C. E. Rohrs, ``Dynamic power allocation and routing for time varying wireless networks," in IEEE INFOCOM, 2003.
    連結:
  37. [40] R. L. Cruz and A. V. Santhanam, ``Optimal routing, link scheduling and power control in multi-hop wireless networks," in IEEE INFOCOM, 2003.
    連結:
  38. [41] L. Lin, X. Lin, and N. B. Shroff, ``Low-complexity and distributed energy minimization in multi-hop wireless network," in Proc. IEEE INFOCOM, 2007.
    連結:
  39. [43] C. Intanagonwiwat, R. Govindan, D. Estrin, J. Heidemann, and F. Silva, ``Directed diffusion for wireless sensor networking," IEEE/ACM Trans. Networking, vol. 11, pp. 2-16, February 2003.
    連結:
  40. [45] M. Ding, X. Cheng, and G. Xue, ``Aggregation tree construction in sensor networks," in Proc. of Vehicular Technology Conference (VTC), 2003.
    連結:
  41. [46] K. Dasgupta, K. Kalpakis, and P. Namjoshi, ``An effcient clustering-based heuristic for data gathering and aggregation in sensor networks," in Wireless Communications and Networking, WCNC, IEEE, vol. 3, 2003.
    連結:
  42. [47] H. □Ozg□ur Tan and I. K□orpeo•glu, ``Power effcient data gathering and aggregation in wireless sensor networks," in SIGMOD Rec., vol. 32, pp. 66-71, 2003.
    連結:
  43. [48] Y. Xue, Y. Cui, and K. Nahrstedt, ``Maximizing lifetime for data aggregation in wireless sensor networks," Mobile Networks and Applications, vol. 10, no. 6, pp. 853-864, 2005.
    連結:
  44. [49] K. Kalpakis, K. Dasgupta, and P. Namjoshi, ``Effcient algorithms for maximum lifetime data gathering and aggregation in wireless sensor networks," Computer Networks, vol. 42, pp. 697-716, Aug 2003.
    連結:
  45. [50] C. Zhu and M. S. Corson, ``A distributed channel probing scheme for wireless networks," in Proc. IEEE INFOCOM, pp. 403-411, 2001.
    連結:
  46. [53] A. Berman and R. J. Plemmons, Nonnegative Matrices in the Mathematical Sciences. New York: SIAM, 1994.
    連結:
  47. [1] J. F. Kurose and K. W. Ross, Computer Networking, A Top-Down Approach Featuring the Internet. Addison-Wesley, 2 ed., 2003.
  48. [11] D. Mitra, ``An asynchronous distributed algorithm for power control in cellular radio systems," in Proc. 4th Winlab Workshop Third Generation Wireless Information Network, (Rutgers Univ., New Brunswick, NJ), pp. 249-257, October 1993.
  49. [23] S. A. Grandhi, J. Zander, and R. Yates, ``Constrained power control," Wireless Personal Communications, vol. 1, no. 4, pp. 257-270, 1994.
  50. [34] X. Lin, N. B. Shroff, and R. Srikant, ``A tutorial on cross-layer optimization in wireless networks," Selected Areas in Communications, IEEE Journal on, vol. 24, pp. 1452-1463, Aug. 2006.
  51. [42] C. Intanagonwiwat, R. Govindan, and D. Estrin, ``Directed diffusion: a scalable and robust communication paradigm for sensor networks," in Mobile Computing and Networking, pp. 56-67, 2000.
  52. [44] B. Krishnamachari, D. Estrin, and S. Wicker, ``Impact of data aggregation in wireless sensor networks," in Proc. of International Workshop of Distributed Event Based Systems (DEBS), 2002.
  53. [51] P. Chaporkar, K. Kar, and S. Sarkar, ``Achieving queue length stability through maximal scheduling in wireless networks," in Proceedings of Information Theory and Applications Inaugural WorkShop, (University of California, San Diego), February 2006.
  54. [52] X. Wu, R. Srikant, and J. R. Perkins, ``Queue-length stability of maximal greedy schedules in wireless network," in Proceedings of Information Theory and Applications Inaugural WorkShop, (University of California, San Diego), February 2006.
  55. [54] R. B. Bapat and T. E. S. Raghavan, Nonnegative Matrices and Applications. Cambridge, United Kingdom: Cambridge University Press, 1997.