近年來IEEE 802.11 無線區域網路已成為寬頻無線存取的主要途徑。其使用者在享受各種新穎服務的同時，也期待可攜無線設備的使用時間能符合需求。為減少能量浪費，電源管理是透過適時調降無線設備電源狀態的節能技術。對於共享傳輸媒介且多使用者的無線網路而言，除了依訊務的就緒與否來調節電源狀態，如何滿足個別需求且錯開使用者的服務時間以避免耗費電能的無意聆聽(overhearing)，也是很重要的議題。因此我們聚焦於電源管理排程演算法，考慮變動位元率訊務與錯誤重傳，減少服務期間重疊情形以達節能之目的。

在本論文中，為了支援802.11e 標準中的節能機制―排程式自動節能遞送(Scheduled Automatic Power Save Delivery)，我們首先提出一個易實現的排程演算法。此排程準則為最大化新加入訊務與現存已排程事件的距離。利用服務排程間距之週期性，能避免相關研究提出
的暴力搜尋法(brute-force search)造成的冗餘檢查。此外，基於現實中的訊務種類有限的特點，我們提出事先計算並儲存不同類訊務間的相對關係的演算法，進一步降低實現複雜度。由於前述排程準則為基於系統原有排程找尋新訊務的合適安插位置，因而排程結果與訊務加入順序相關，所得亦為漸進式的最佳化結果。所以我們延伸提出重整系統現存訊務排程的整體最佳化問題，目標為最大化整體系統排程的最小距離。我們設計的重整演算法妥善利用平分排程的低複雜度且保持最小排程間距的上限，可達到良好的節能效果。

為了提高無線頻寬使用效率，多重輪詢(multi-polling)經常被用來降低通訊協定中的虛耗(overhead)。然而，為了維持排序競爭式多重輪詢之正常運作，需要無線站台耗費許多時間在無意聆聽上，導致電能浪費而降低電池可用時間。在本論文中，我們提出一個節能多重輪詢(Energy-Efficient Multi-Polling)機制，結合低虛耗通訊協定與電源管理技術。在此機制中，我們推出一個給定頻寬使用率下的最佳甦醒時間排程(wake-up time schedule)，相較於原先的排序式多重輪詢機制，分析與模擬結果均展示良好的節能表現。在給定損失5%的頻寬使用率且由20 個無線站台組成之環境下，可達到80%的節能改進。此顯著效果來自妥適的甦醒時間排程，大幅避免無意聆聽的情形。最後，我們亦探討無線網路中因錯誤回復(error recovery)造成
的節能問題。對於類分時多工的多重輪詢機制，提出有效的甦醒時間排程以及相應於重傳致使延遲的排程更新演算法，增加站台進入低電源狀態的機會。模擬結果顯示採用我們的演算法可顯著改進錯誤重傳發生時的節能效果。

In the past decade, IEEE 802.11 wireless LANs has gained large popularity in broadband wireless access. Users are demanding high performances while keeping respectable operation time for the mobile devices. Power management (PM) is an essential technique for energy saving by putting de-vices into low power state during appropriate interval. For a multi-user and shared medium wireless network, in addition to managing power state according to readiness of traffic, it is important to separate the usage time of different users to prevent energy-consuming overhearing. Hence, in this dissertation, considering variable-bit-rate traffic and unpredictable error recovery, we focus on the scheduling algorithms to reduce the chance of service period overlapping.

To support standardized power saving mechanism in IEEE 802.11e, we propose a feasible scheduling algorithm for the Scheduled Automatic Power Save Delivery. The goal is to maximize the minimum distance between the scheduled instants of new joining traffic stream (TS) and exist-ing scheduled events (SEs). By the proven periodicity of service schedules, the redundant check in the previous brute-force method can be avoided. Moreover, considering limited number of classes for TSs, we can pre-calculate and store necessary information to further reduce the implementation complexity. Extending the idea of finding the optimal service start time for new joining TS incre-mentally, we also study the rearrangement of existing SEs to further maximize the system minimum distance. We prove the upper bound of the system minimum distance and design efficient rearrang-ing algorithms to achieve satisfactory energy saving.

In order to achieve higher system bandwidth utilization (BU), multi-polling mechanisms are often employed to reduce protocol overhead. However, they may require wireless stations (STAs) to spend much time in overhearing. We propose an energy-efficient multi-polling mechanism which combines PM strategy with a low overhead Medium Access Control protocol. Given a desirable guarantee of BU, an energy optimized wake-up time schedule (WTS) is devised. Significant saving of energy can be obtained with only small loss of BU as trade-off. It is the consequence of alleviat-ing the overhearing problem by well scheduled WTSs for STAs. In the end, we also study the ener-gy saving issue induced from error recovery. A WTS and a renewal algorithm in correspondence with the delay caused by retransmissions are proposed for the TDMA-like multi-polling mechanism. Simulation results show that, compared with the original setting, significant improvement can be obtained by the proposed algorithms.

中文摘要 i
Abstract ii
Acknowledgements iii
Contents iv
List of Tables viii
List of Figures ix
1 Introduction 1
1.1 Overview 1
1.2 Acronyms 4
1.3 Contributions and Dissertation Organization 5
2 Backgrounds 8
2.1 Medium Access Control of Wireless LANs 8
2.2 Power Management of Wireless LANs 11
3 Scheduling Algorithm for Scheduled Automatic Power Save Delivery 17
3.1 System Model 18
3.2 Low Complexity Scheduling Algorithm 19
3.2.1 Basic Idea 19
3.2.2 Generalization to K Existing Tra±c Streams 23
3.3 Class-Based Scheduling Algorithm 26
3.3.1 Suggested Implementation Method 27
3.4 Performance Evaluations 30
3.4.1 Comparison of Computational Complexity 30
3.4.2 Comparison of Power Consumptions 32
3.4.3 Comparison of A®ordable Transmissions 33
3.5 Summary 34
4 Rearrangement Algorithms for the IEEE 802.11e S-APSD 40
4.1 System Model 41
4.2 The Rearrangement of Scheduled Events 43
4.2.1 The Brute-Force Searching Method 44
4.2.2 The Naive Equal-Spacing Method 45
4.3 The Coprime-Avoiding Scheduling Algorithms 47
4.3.1 The Gmin-Maintaining Decomposition Greedy Scheduling 50
4.3.2 The Simply Sorted Greedy Method 52
4.3.3 Implementation Issues 52
4.4 Performance Evaluations 54
4.4.1 Comparison of Computational Complexity 54
v
4.4.2 Comparison of the System Minimum Distance 57
4.4.3 Comparison of Power Consumptions 58
4.5 Summary 60
5 Energy-E±cient Multi-Polling Mechanism 63
5.1 System Model 65
5.2 Energy-E±cient Multi-Polling Mechanism 65
5.2.1 Mechanism Design 65
5.3 Energy-E±cient Wake-up Time Schedule 69
5.3.1 An Energy-E±cient Scheduling Model 69
5.3.2 Analysis of Energy E±ciency 75
5.3.3 Impact of Estimation Discrepancy 77
5.4 Performance Evaluation 78
5.4.1 Example 5.1 78
5.4.2 Example 5.2 79
5.4.3 Example 5.3 82
5.5 Summary 83
6 Dealing with Energy-Saving Issue Induced from Error-Recovery 87
6.1 System Model 88
6.1.1 Error recovery 88
6.1.2 Two-Step Multi-Polling 88
6.2 The Proposed Power Saving Scheme for TSMP 89
6.2.1 Wake-up Time Schedule without Pre-Delay 90
vi
6.2.2 Wake-up Time Schedule with Pre-Delay 97
6.3 Performance Evaluation 98
6.3.1 Simulation Scenario 98
6.3.2 Simulation Results 99
6.4 Summary 102
7 Conclusions 103
Bibliography 105

[1] IEEE 802.11 WG: IEEE Standard 802.11-1999, Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications, 1999.
[2] IEEE Std 802.11e-2005, Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications Amendment 8: Medium Access Control (MAC) Quality of Service Enhancements.
[3] Std 802.11n-2009, Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications Amendment 5: Enhancements for Higher Throughput.
[4] M. S. Gast, 802.11 Wireless Networks - The Definition Guide. O'Reilly, 2002.
[5] W. Ye, J. Heidemann and D. Estrin, "Medium Access Control With Coordinated Adaptive Sleeping for Wireless Sensor Networks," IEEE/ACM Trans. Networking, vol. 12,
no. 3, pp. 493- 506, June 2004.
[6] G. E. Moore, "Cramming more components onto integrated circuits," Electronics, vol. 38, no. 8, pp. 114V117, Apr. 1965.
[7] K. Lahiri, A. Raghunathan, S. Dey, and D. Panigrahi, "Battery-driven system design: A new frontier in low power design," in Proc. Intl. Conf. on VLSI Design, pp. 261-267,Jan. 2002.
[8] R. Mangharam, R. Rajkumar, S. Pollin, F. Catthoor, B. Bougard, L. Van der Perre,and I. Moeman, "Optimal fixed and scalable energy management for wireless networks,"
in Proc. IEEE INFOCOM, Vol. 1, pp. 114V125, Mar. 2005.
[9] S. H. Gunther, F. Binns, D. M. Carmean, and J. C. Hall, "Managing the Impact of Increasing Microprocessor Power Consumption," Intel Technology Jounal, First Quarter,
2001.
[10] Atheros White Paper, "Power Consumption and Energy Efficiency Comparisons of WLAN Products". 2003.
[11] Dell, "Dell TrueMobile 1400 WLAN Card." [Online].
Available: http://support.ap.dell.com/docs/network/p44970/en/specs.htm
[12] N.A. Pantazis and D.D. Vergados, "A survey on power control issues in wireless sensor networks," IEEE Communications Surveys & Tutorials, Vol. 9 , no. 4, pp. 86 - 107, 2007.
[13] D. Qiao, S. Choi,and K.G. Shin, "Interference Analysis and Transmit Power Control in IEEE 802.11a/h Wireless LANs," IEEE Trans. Networking, Vol. 15 , no. 5, pp. 1007 -
1020, 2007.
[14] Y. Xiao and J. Rosdahl, "Throughput and Delay Limits of IEEE 802.11," IEEE Commun. Lett., vol. 6, no.8, pp. 355- 357, Aug. 2002.
[15] S.-C. Lo, G. Lee, and W.-T. Chen, "An Efficient Multipolling Mechanism for IEEE 802.11 Wireless LANs," IEEE Trans. Comput., vol. 52, no. 6, pp. 764- 778, June 2003.
[16] S.-C. Lo and W.-T. Chen, "An Efficient Scheduling Mechanism for IEEE 802.11E MAC Enhancements," in Proc. IEEE WCNC, pp. 777- 782, vol. 2, March 2004.
[17] S. Kim, Y. Kim, S. Choi, K. Jang and J. Chang, "A High-Throughput MAC Strategy for Next-Generation WLANs," in Proc. IEEE WoWMoM, pp. 278- 285, June 2005.
[18] B.-S. Kim, S.W. Kim, Y. Fang, and T.F. Wong, "Two-Step Multipolling MAC Protocol for Wireless LANs," IEEE J. Select. Areas Commun., vol. 23, no. 6, pp. 1276-1286,
June 2005.
[19] Z.-T. Chou, C.-C. Hsu, and S.-N. Hsu, "UPCF: A New Point Coordination Function With QoS and Power Management for Multimedia Over Wireless LANs," IEEE/ACM Trans. Networking, vol. 14, no. 4, pp. 807-820, Aug. 2006.
[20] J. A. Stine and G. D.Veciana, "Improving Energy Efficiency of Centrally Controlled Wireless Data Networks," ACM/Kluwer Wireless Networks, vol.8, pp. 681-700, Nov. 2002.
[21] Y.-C. Tseng, C.-S. Hsu, and T.-Y. Hsieh, "Power-Saving Protocols for IEEE 802.11-Based Multi-Hop Ad Hoc Networks," in Proc. IEEE INFOCOM, Vol. 1, pp. 200-209, June 2002.
[22] E.-S. Jung and N. H. Vaidya, "An E±cient MAC Protocol for Wireless LANs," in Proc. IEEE INFOCOM, vol. 3, pp. 1756-1764, June 2002.
[23] S. Singh, and C. S. Raghavendra, "PAMAS - Power Aware Multi-Access protocol with Signalling for Ad Hoc Networks," in ACM SIGCOMM, Vol. 28 , no. 3, pp. 5 - 26, July
1998.
[24] H. Woesner, J. P. Ebert, M. Schlager, and A. Wolisz, "Power-Saving Mechanisms in Emerging Standards for Wireless LANs: The MAC Level Perspective," IEEE Persinal
Communications, pp. 40-48, June 1998.
[25] S. Jayashree, and C. Siva Ram Murthy, "A Taxonomy of Energy Management Protocols for Ad Hoc Wireless Networks," IEEE Commun. Magazine, Vol. 45 , no. 4, pp. 104 - 110, 2007.
[26] R. Krashinsky and H. Balakrishnan, "Minimizing Energy for Wireless Web Access with Bounded Slowdown," in Proc. ACM MOBICOM, Sep. 2002.
[27] D. Qiao and K. G. Shin, "Smart power-saving mode for IEEE 802.11 wireless LANs," in Proc. IEEE INFOCOM, Mar. 2005.
[28] X. P¶erez-Costa and D.Camps-Mur, "APSM: Bounding the Downlink Delay for 802.11 Power Save Mode," in Proc. IEEE ICC, May 2005.
[29] C. E. Jones, K. Sivalingam, P. Agrawal, and J.-C. Chen, "A Survey of Energy Efficient Network Protocols for Wireless Networks," ACM/Kluwer Wireless Networks, vol. 7, pp. 343-358, Nov. 2001.
[30] A. Kamerman and L. Monteban, "WaveLAN-II: A High-Performance Wireless LAN for the Unlicensed Band," Bell Labs Technical Journal, vol. 2, no. 3, 1997.
[31] Y. Jiao, A. R. Hurson, and B. A. Shirazi, "Online Adaptive Application-Driven WLAN Power Management," in Proc. IEEE Globecom, pp. 2663-2668, Nov. 2005.
[32] J.-R. Hsieh, T.-H. Lee, and Y.-W. Kuo, "Power Efficient Multipolling Mechanism for Next Generation Wireless LANs," in Proc. IEEE VTC2007-Spring, pp. 2971-2975, Apr. 2007.
[33] MATLAB and Simulink for Technical Computing, http://www.mathworks.com/
[34] B.W. Silverman, Density Estimation for Statistics and Data Analysis. Chapman and Hall, 1986.
[35] A. Grilo, M. Macedo, and M. Nunes, "A Scheduling Algorithm for QoS Support in IEEE 802.11e Networks," IEEE Wireless Commun. Mag., vol. 10, no. 3, pp.36-43, June 2003.
[36] Q. Zhao and D. H.K. Tsang, "An Equal-Spacing-Based Design for QoS Guarantee in IEEE 802.11e HCCA Wireless Networks," IEEE Trans. Mobile Computing, Vol. 7, no.
12, Dec. 2008.
[37] S. Mangold, S. Choi, G. R. Hiertz, O. Klein, B. Walke, "Analysis of IEEE 802.11e for QoS Support in Wireless LANs", IEEE Wireless Comm. Mag., Vol. 10, no. 6, Dec, 2003.
[38] X. P¶erez-Costa, D. Camps-Mur, J. Palau, D. Rebolleda and S. Akbarzadeh, "Overlapping Aware Scheduled Automatic Power Save Delivery Algorithm," in Proc. of European
Wireless Conference (EW), Paris, France, Apr. 2007.
[39] X. P¶erez-Costa, D. Camps-Mur and T. Sashihara. "Analysis of the Integration of IEEE
802.11e Capabilities in Battery Limited Mobile Devices," IEEE Wireless Comm. Mag.,special issue on Internetworking Wireless LAN and Cellular Networks, Vol. 12, no. 6,
December 2005.
[40] T. H. Cormen, C. R. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, Second ed., MIT Press and McGraw-Hill. ISBN 0262032937.
[41] F. Fitzek , A. Koepsel , A. Wolisz , M. Krishnam , and M. Reisslein, "Providing Application-Level QoS In 3G/4G Wireless Systems: A Comprehensive Framework Based On Multi-Rate CDMA," IEEE Wireless Comm. Mag., Vol. 9, no. 2, Apr., 2002.
[42] T. Simunic, H. Vikalo, P. Glynn, and G. D. Micheli, "Energy E±cient Design of Portable Wireless Systems," in Proc. of the International Symposium on Low Power Electronics and Design, pp. 49-54, 2000.
[43] J.-R. Hsieh and T.-H. Lee, "An Energy Saving Scheme with Error Recovery for Multi-Polling in Wireless LANs," in Proc. IEEE VTC2008-Spring, pp. 2121-2125, May 2008.
[44] T.-H. Lee and J.-R. Hsieh, "An E±cient Scheduling Algorithm for Scheduled Automatic Power Save Delivery for Wireless LANs," in Proc. IEEE VTC2010-Spring, May 2010.
[45] J.-R. Hsieh and T.-H. Lee, "Energy-E±cient Multi-polling Scheme for Wireless LANs," IEEE Trans. Wireless Commu., Vol. 8, No. 3, pp. 1532-1541, Mar. 2009.
[46] T.-H. Lee and J.-R. Hsieh, "Low Complexity Class-based Scheduling Algorithm for Scheduled Automatic Power-Save Delivery for Wireless LANs," submitted to IEEE
Trans. Mobile Computing. (under review)
[47] T.-H. Lee, J.-R. Hsieh, M.-C. Huang and Y.-W. Huang, "A Bandwidth Efficient Pairing Strategy for the MIMO-OFDM Based WLANs," in Proc. of IEEE VTC2009-Spring,
Apr. 2009.
[48] T.-H. Lee, J.-R. Hsieh, and H.-W. Chen, "A Rearranegement Algorithm for Scheduled Automatic Power Save Delivery of Wireless LANs," accepted and to appear in IEEE Tencon2010.
[49] F.H.P Fitzek and M.Reisslein, "MPEG-4 and H.263 Video Traces for Network Performance Evaluation," IEEE Network, Vol. 15, No.6, pp. 40-54, Dec. 2001.
http://www-tkn.ee.tu-berlin.de/research/trace/trace.html