臺灣博碩士論文加值系統

IEEE 802.15.3無線個人區域網路(Wireless Personal Area Network)具有短距離、高速、低耗能的特性，並提供等時性(isochronous)與非同步(asynchronous)服務以支援多媒體應用，本文主要研究IEEE 802.15.3無線個人區域網路中等時性服務頻寬分配的問題，由於無線隨身裝置電源有限，如何節省能源是其中一項重要的議題，本文提出一個最佳節省能源排程問題(Optimal Energy-Aware Scheduling Problem, OEASP)，並証明該問題為一NP-完全問題，給定一組已建立連結的等時性傳輸和若干等時性傳輸的需求，以最少的等時性頻寬與能源服務所有的需求，提出有效的同時性資源分配演算法PSRA以提供近似最佳解，模擬的結果顯示所提出之演算法可以提供近似最佳排程以減少不必要的狀態轉換次數與待機時間。

With the characteristics of short range, high-rate, and low-power, IEEE 802.15.3 WPAN enable the isochronous and asynchronous service to meet the requirements of multimedia applications. This paper investigates the isochronous resource allocation problem in IEEE 802.15.3 WPAN. Due to the limited resources of wireless portable device, saving power is one of the most important issues. In this paper, an optimal energy-aware scheduling problem is defined and proved to be NP-complete. Given a set of established isochronous connections and a set of isochronous connections requests, using a minimal number of isochronous bandwidth and minimal energy to service all the connections is attempted. An efficient isochronous resource-allocation algorithm, capable of providing a solution close to the lower bound, is also proposed. Simulation results indicate that the proposed algorithm provides near optimal scheduling to reduce unnecessary switching times and idle time.

中文摘要…………………………………………………………………………………i
英文摘要……………………………………...…………………………………………ii
誌謝……………………………………………..………………………………………iii
目錄…………………………………………….……………………………………….iv
表目錄…………………………………………………………………..........................vi
圖目錄………………………………………………………………………………….vii
1. 緒論……………………………………………….…………………………………1
2. 文獻探討………………………………………….…………………………………5
2.1 超級訊框內能源管理……………….....………….……….…………………5
2.2 非工作保守虛擬時間……………………………………..……………….....8
2.3 區塊排程法…………………………………………………………………...8
3. 無線個人區域網路……………………………….………………………………...10
3.1 藍芽無線個人區域網路...…………………………………………………...10
3.2 IEEE 802.15.3高速無線個人區域網路………………………….…………11
3.3 超寬頻………………………………….………………………….………….13
4. 節省能源之資源分配演算法……………………………………………………...15
4.1 最佳能源管理排程問題探討…...…………………………………………..15
4.2 最佳多重權重雙分圖配對問題之NP-完全探討……………..……………19
4.3 節省能源之資源分配演算法………..………………………….…………..20
5. 效能評量……………………………………………………...................................30
6. 結論………………………………………………………………………………..45
參考文獻……………………………………………………………………………….46

[1]J. Karaoguz, “High-rate wireless personal area networks,” IEEE Communications Magazine, vol.39, no.12, pp.96 - 102, Dec. 2001.
[2]Bluetooth, Specification of Bluetooth System, http://www.bluetooth.com
[3]G. R. Aiello and G. D. Rogerson, “Ultra-wideband wireless systems,” IEEE Microwave Magazine, vol.4, no.2, pp.36 - 47, Jun. 2003.
[4]P. Gandolfo, J. Allen, “802.15.3 Overview/Update,” WiMedia Alliance, Oct. 2002.
[5]“IEEE standard for information technology – telecommunications and informatione exchange between systems - local and metropolitan area networks - specific requirements part 15.3: wireless medium access control (MAC) and physical layer (PHY) specifications for high rate wireless personal area networks (WPANs) ,” IEEE Std 802.15.3-2003, 2003.
[6]Hao Zhu and Guohong Cao, “A power-aware and QoS-aware service model on wireless networks,” IEEE INFOCOM, vol.2, pp.1393 - 1403, Mar. 2004.
[7]J. Chen and K. Sivalingam, P. Agrawal, and S. Kishore, “A comparison of MAC protocol for wireless local networks based on battery power consumption,” IEEE INFOCOM, vol.1, pp.150 - 157, Apr. 1998.
[8]I. Howitt and Jing Wang, “Energy efficient power control policies for the low rate WPAN,” IEEE SECON, pp.527 - 536, Oct. 2004.
[9]Xiaolei Shi, G. Stromberg, Y. Gsottberger and T. Sturm, “Wake-up-frame scheme for ultra low power wireless transceivers,” IEEE GLOBECOM, vol.6, pp.3619 - 3623, Dec. 2004.
[10]D. Li, P. Chou, and N. Bagherzadeh, “Mode selection and mode-dependency modeling for power-aware embedded systems,” VLSID, pp.697 - 704, Jan. 2002.
[11]Zihua Guo, R. Yao, Zhu Wenwu, Xin Wang and Yong Ren, “Intra-superframe power management for IEEE 802.15.3 WPAN,” IEEE Communications Letters, vol.9, no.3, pp.228 - 230, Mar. 2005.
[12]億普媒體, 音樂美聲無線傳輸(一)藍芽立體聲耳機大剖析, http://www.eprice.com.tw/news/?news_id=3078
[13]B. Chen, K. Jamieson, H. Balakrishnan, and R. Morris, “An Energy-Efficient Coo- rdination Algorithm for Topology Maintaince in Ad Hoc Wireless Networks,” ACM Mobicom, 2001.
[14]Q. Li, J. Aslam and D. Rus, “Online Power-aware Routing in Wireless Ad-hoc Networks,” MobiCOM, Jul. 2001.
[15] M. Stemm and R. H. Katz, “Measuring and Reducing Energy Consumption of Network Interfaces in Handheld Devices,” IEICE Transactions on Communications, vol.E80-B, no.8, Aug. 1997.
[16]Y. Xu, J. Heidemann and D. Estrin, “Geography-informed Energy Conservation for Ad Hoc Routing,” Mobicom, Jul. 2001.
[17]H. Zhang, “Service Disciplines for Guaranteed Performance Service in Packet-Switching Networks,” IEEE Transactions on Networking, vol.83, no.10, Oct. 1995.
[18]Hao Zhu and Guohong Cao, “On Supporting power-efficient streaming applications in wireless environments,” IEEE Mobile Computing, vol.4, pp.391 - 403, Jul. - Aug. 2005.
[19]Intel, Ultra-Wideband (UWB) Technology: Enabling High-speed Wireless Personal Area Networks. http://www.intel.com/technology/ultrawideband/downloads/Ultra-Wideband.pdf
[20]Intel, Wireless USB: The First High-speed Personal Wireless Interconnect. http://www.intel.com/technology/ultrawideband/downloads/WirelessUSB.pdf
[21]IEEE802, IEEE 802.15WPAN High Rate Alternative PHY Task Group 3a (TG3a), http://www.ieee802.org/15/pub/TG3a.html
[22]G. R. Aiello and G. D. Rogerson, “Ultra-wideband wireless systems,” IEEE Microwave Magazine, vol.4, no.2, pp.36 - 47, Mar. 2003.
[23]Intel, Ultra-Wideband (UWB) Technology: Enabling High-speed Wireless Personal Area Networks, http://www.intel.com/technology/comms/uwb/download/wireless_pb.pdf
[24]C. L. Liu, Elements of Discrete Mathematics, 2/e, McGeaw-Hill, 1998.
[25]Ralph P. Grimaldi, “Discrete and Combinational Mathematics,” Addison-Wesley, 2003.
[26]K. H. Rosen, Discrete Mathematics and Its Applications, McGreaw-Hill, 2003.
[27]E. Horowitz, S. Sahni, and S. Anderson, Fundamentals of Data Structures in C, Computer Science, 1993.
[28]E. Horowitz, S. Sahni, and S. Anderson, Fundamentals of Data Structures in C++, Computer Science, 2000.
[29]T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to Algorithm, MIT, 2002.
[30]J. R. Hanly, E. B. Koffman and J. C. Horvath, Problem Solving and Problem Design in C, Addison Wesley, 2003.
[31]H. M. Deitel, P. J. Deitel, C How to Program, Pearson Education International, 2004.
[32]B. Harvey, S. Robinson, J. Templeman and K. Watson, C# Programming With the Public Beta, Wrox , 2000.
[33] S. Rhee, D. Seetharam and S. Liu, “Techniques for Minimizing Power Consumption in Low Data-Rate Wireless Sensor Networks,” WCNC, vol.3, pp. 527 - 536, Oct. 2004.
[34] Y. Wei, J. Heidemann and D. Estrin, “An Energy-Efficient MAC Protocol for Wireless Sensor Networks,” IEEE INFOCOM, vol.3, pp.1567 - 1576, Jun. 2002.
[35] Xin Wang, Yong Ren, Jun Zhao, Zihua Guo and Yao R., “Energy efficient transmission protocol for UWB WPAN,” VTC, vol.7, pp.5292 - 5296, Sep. 2004.
[36] T. Dam and K.Langendoen, “An adaptive energy-efficient MAC protocol for wireless sensor networks,” ACM Embedded networked sensor systems, pp.171 - 180, 2003.
[37]C. F. Chiasserini and R. R. Rao, “Energy efficient battery management,” IEEE JSAC, vol.19, pp.1235 - 1245, no.7, Jul. 2001.
[38]E. Hossain and V. K. Bhargava, “A centralized TDMA-based scheme for fair bandwidth allocation in wireless IP networks,” IEEE JSAC, vol.19, Nov. 2001.
[39]P. Nuggehalli, V. Srinivasan and R. Rao, “Delay constrained energy efficient transmission strategies for wireless devices,” IEEE INFOCOM, vol.3, pp.1765 - 1772, Jun. 2002.
[40]A. Gamal, C. Nair, B. Prabhakar, E. Uysal-Biyikoglu and S. Zahedi, “Energy-efficient scheduling of packet transmissions over wireless networks,” IEEE INFOCOM, vol.3, pp.1773 - 1782, Jun. 2002.
[41]L. Vajda, A. Torok , Youn Kyu-Jung and J. Sun-Do, “Hierarchical superframe formation in 802.15.3 networks,” IEEE Communication Society, vol.7, pp.4017 - 4022, Jun. 2004.
[42] S. H. Rhee,K. Chung,Y. Kim, W. Yoon and K. S. Chang, “An Application-Aware MAC Scheme for IEEE 802.15.3 High-Rate WPAN,” WCNC, vol.2, pp.1018 - 1023, Mar. 2004.
[43]WiMedia, View MBOA Presentation and White Paper Archives, http://www.wimedia.org/en/index.asp
[44]WiMedia, WiMedia MB-OFDM Overview, http://www.wimedia.org/en/resources- /technicallibrary.asp?id=res
[45] WiMedia, MultiBand OFDM Physical Layer Proposal for IEEE 802.15 Task
Group 3a, http://www.wimedia.org/en/index.asp