隨著網路的普及，改變了人們的日常生活習慣，而網路應用也與日俱增，像是Google、Bing 以及Yahoo!等搜尋引擎，FTP、P2P 分享檔案應用，MSN、Yahoo 即時通、Skype 和Face book 等廣受歡迎的社交工具以及多樣的線上遊戲和網路購物等等，換言之，我們的生活已經逐漸與網路密不可分。為了滿足人們對於網路便利性之需求，傳統的有線網路(不包含光纖網路)已經不敷使用，且慢慢被無線網路所取代，而無線網路技術也因此積極向前，因此現今無線網路的運用以及技術也被人們大大的重視；如今任意的一台筆記型電腦或是手機都能夠輕易的連上網際網路，在未來，可以預見的無線網路的影音串流運用以及點對點協定將會大行其道。然而，在這些行動裝置上仍然有些許先天上之缺點困擾著人們。這些限制就是行動裝置的電力以及記憶容量有限，這些問題使得行動電話無法承受大量的資料傳輸或造成較差的使用品質。因此，如何提供好的電力及快取記憶體管控
向來是一個重要的議題。
在這篇論文中，我們提供了一個新的叢集架構，此架構不只提供電力上的管控並且也有支援快取的資料置換策略；對於此叢集，我們採用了由下而上(agglomerative)的建構方式，並且藉由計算能力值的方式確立各成員在叢集中的位置與關係；在快取策略部分，我們提出了Conditioned‐LRU策略，此策略是依據H.264/SVC 特性所設計，適用於不同播放設備以及多變的網路環境所使用，其概念是將每一frame 視為一路徑上的節點，並依據資料取得成本和畫面品質計算出成本最小路徑再從此路徑中挑選適當的被刪除者。而另外一個部分是電力管控，我們結合了叢集架構的特性以及IEEE 802.11 PSM 來控制更精確的耗電量，叢集中的每一位成員都會根據自己在叢集中的位置來決定睡眠時間，通常處於管理者的成員，電力和其它外在條件都較好，因此建議可以醒久一點來為大家服務，而下面的員工則睡久一點以節省自身電量，根據此方法，我們可以獲得不錯的省電效果。

Accompanying the popularization of Internet is varying the daily life of human. The application of Internet is growing strongly day by day such as the search engine – Google, Bing and Yahoo!, the application of data sharing – FTP and P2P, the popular social tool – MSN, Yahoo message, Skype and Face book, varying on‐line game and e‐shopping…etc. In other words, we already cannot live without Internet gradually. In order to satisfy the convenience that people want, the traditional wire network (not includes fiber) is superseded by the wireless network gradually and forwarding the wireless technique positively. Hence, the application and technique of wireless network are respected by people nowadays. Now, a laptop or a mobile phone can connect to Internet easily and it is bringing huge amount of different and interested applications and technique. In the future, it is foreseeable that the video streaming and P2P application will be more and more popular. However, there are still some restrictions to torment users, that is the memory and power of mobile phone is limited. These problems cause the mobile phone cannot bear to transmit and store a considerable quantity of data and make a worse quality of usage. Therefore, it is an important issue to manage power consumption and cache well. In our paper, we address novel cluster architecture. The cluster architecture not only has
power management but also cache management to decide which data item has to replace. We adopt the mechanism of button‐up (agglomerative) to establish the cluster, and ensure
the relationship of each member of this cluster by the capability value that every member owns. In the cache management, we design a cache replacement strategy called
Conditioned‐LRU (C‐LRU). In C‐LRU, it is designed that bases on the property of H.264/SVC, suits different playbacks and varying network environments. The strategy considers the link cost and the images’ quality to replace data item. 
In our paper, C‐LRU uses the concept of minimal cost path to find a better candidate to replace. The other issue is the power management. We combine the cluster and IEEE 802.11 PSM to reduce more power consumptions. Each member has different sleeping time that is based on the virtual location of management. In other words, different height of management stands for different sleeping time. Usually, the manager has a better capability than employees. Hence, we suggest the manager can wake up longer to serve others and employees sleep longer to save the power itself. By this mechanism, we can obtain a not bad performance to save more power.

目   錄
第一章	緒論	1
1.1	前言	1
1.2	動機與目的	2
1.3	論文章節架構	5
第二章	背景知識與相關工作	6
2.1	叢集的建立	6
2.2	快取管理策略	12
2.2.1	協調式快取策略簡介	15
2.2.2	影音資訊快取問題	18
2.2.3	路徑資訊快取問題	20
2.3	H.264/SVC簡介	21
2.4	IEEE 802.11電源管理機制	24
第三章	叢集建立方法	26
3.1	叢集建立流程概述	26
3.2	能力值的計算	32
3.3	叢集的架構	41
3.3.1	叢集的建立與新成員的加入	41
3.3.2	成員的離去	44
3.3.3	資料的存放	45
3.3.4	資料路徑的建立	46
第四章	多媒體快取置換策略	48
4.1	網路連接成本	48
4.2	畫面品質損失成本	55
4.3	C-LRU快取置換策略	58
第五章 叢集式電力管理機制 ............................................................ 62
5.1 同步化方法與時機................................................................ 63
5.2 調整睡眠時間方法與準則 .................................................... 66
第六章 模擬與分析 ........................................................................... 70
6.1 模擬環境架構與參數分析 .................................................... 70
6.2 快取置換策略模擬結果 ........................................................ 82
6.3 叢集式電源管理機制模擬結果 ............................................ 90
第七章 結論與未來展望 ................................................................... 94
參考文獻 ................................................................................................ 96

圖 目 錄
圖1.1:叢集系統示意圖	5
圖2.1:使用K-Mean方法形成階層式架構示意圖	7
圖2.2:基本叢集建立與檢測流程圖	11
圖2.3:使用PER快取策略示意圖	15
圖2.4: 使用CB快取策略示意圖	15
圖2.5:使用SOP快取策略示意圖	17
圖2.6:點對點隨選視訊運用示意圖	19
圖2.7:SVC架構示意圖	23
圖3.1: 新成員加入示意圖 (新成員A)	27
圖3.2: 回傳RREP訊號示意圖	27
圖3.3:管理權狀態配置示意圖	29
圖3.4:成員C之管理權交予成員A之一	29
圖3.5:成員C之管理權交予成員A之二	30
圖3.6:成員A與C無管理關係圖	30
圖3.7: 叢集樹狀管理架構示意圖 (分支度為二)	31
圖3.8:具有8個節點的網路	33
圖3.9:log函式圖	37
圖3.10:距離與封包遺失率關係圖 (來源:[6])	38
圖3.11: 訊號強度與封包成功接收率關係圖	39
圖3.12: Poisson的CDF圖	40
圖3.13:維度為M的向量表示成員表 示意圖	43
圖3.14: 叢集的建立與新成員的加入流程圖	44
圖3.15: 成員卸任流程圖	45
圖3.16: 資料的存放流程圖	46
圖3.17: 資料路徑的建立流程圖	47
圖4.1:伺服器傳送資料至無線手持裝置A示意圖	49
圖4.2:伺服器傳送資料經手持裝置A至手持裝置B	50
圖4.3:手持裝置A直接傳輸資料至手持裝置B示意圖	50
圖4.4:frame的播放路徑示意圖	59
圖4.5:路徑示意圖	60
圖5.1:IEEE 802.11 的電源管理機制	63
圖5.2:兩層式網路架構示意圖	64
圖5.3: Periodically-Fully-Awake-Interval電源管理機制(N=4)示意圖	65
圖5.4:高度與睡眠時間關係圖	67
圖5.5:樹狀高度為4的資料傳輸示意圖	68
圖6.1:無線隨意網路連線圖	71
圖6.2:理想環境示意圖	72
圖6.3:分支度與耗電量關係圖(H=3)	73
圖6.4:分支度與等待時間圖(H=3)	74
圖6.5:分支度與耗電量關係圖(H=4)	75
圖6.6:分支度與等待時間圖(H=4)	76
圖6.7:分支度與耗電量關係圖(H=5)	77
圖6.8:分支度與等待時間圖(H=5)	78
圖6.9:叢集數與分支度關係圖	79
圖6.10:使用不同快取策略擊中率與快取大小關係圖	85
圖6.11:使用不同快取策略之影像品質與快取大小關係圖	86
圖6.12: 回收影片1的frame之一	88
圖6.13:回收影片1的frame之二	89
圖6.14:回收影片2(一次移動2個frame)	90
圖6.15:回收影片2(一次移動5個frame)	90
圖6.16:叢集管理拓樸圖	91
圖6.17:存活點數與時間關係圖	92


表 目 錄
表2.1:耗電量表	19
表3.1:點與點之間的連線關係矩陣	33
表3.2:SORENSON相似度係數表	34
表4.1:連接成本等級表	52
表4.2:畫面等級表	56
表6.1:IEEE 802.11 2Mbps 傳送及接收耗電量(Lucent WaveLAN PC Card)	71
表6.2:不同高度的樹狀叢集建議參數表(H=3、4)	80
表6.3:快取策略模擬參數表	82

參考文獻
[1]	J.F. Lu, J.B. Tang, Z.M. Tang, J.Y. Yang, “Hierarchical initialization approach for K-Means clustering,” Pattern Recognition Letters 29 April 2008, Pages 787-795.
[2]	Chung-Horng Lung and Chenjuan Zhou , “Using hierarchical agglomerative clustering in wireless sensor networks: An energy-efficient and flexible approach,” Ad Hoc Networks 8, May 2010, Pages 328–344.
[3]	H. M. N. Dilum Bandara and Anura P. Jayasumana , “An Enhanced Top-Down Cluster and Cluster Tree Formation Algorithm for Wireless Sensor Networks,” Second International Conference on Industrial and Information Systems, ICIIS 2007, Sri Lanka, 8 – 11 August 2007, Page(s): 565 - 570.
[4]	Rui Xu, and Donald Wunsch II, “Survey of Clustering Algorithms,” IEEE TRANSACTIONS ON NEURAL NETWORKS, VOL. 16, NO. 3, MAY 2005.
[5]	Laura Marie Feeney and Martin Nilsson, “Investigating the Energy Consumption of a Wireless Network Interface in an Ad Hoc Networking Environment,” INFOCOM 2001. Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, 2001, Page(s): 1548 - 1557 vol.3
[6]	Philip Levis, Nelson Lee, Matt Welsh, and David Culler, “TOSSIM: Accurate and Scalable Simulation of Entire TinyOS Applications,” In SenSys '03: Proceedings of the 1st international conference on Embedded networked sensor systems, 2003, pp. 126-137.
[7]	Tal Rusak and Philip Levis, “Physically-based models of low-power wireless links using signal power simulation,” Computer Networks, Volume 54, Issue 4, 19 March 2010, Pages 658-673.
[8]	C. Perkins, E. Belding-Royer and S. Das, “Ad hoc On-Demand Distance Vector (AODV) Routing,” RFC3561, Year of Publication: July 2003. 
[9]	Ozden, B., Rastogi, R. and Silberschatz, A., “Buffer replacement algorithms for multimedia storage systems,” Multimedia Computing and Systems, 17-23 June 1996, Page(s): 172 – 180.
[10]	Qi Zhu, Ling Shao and Rong Yan ,“Buffer Replacement Algorithm for Merge-based Multicast Video-on-Demand System,”  Telecommunications, 23 Feb.-1 March 2003, Page(s): 1448 - 1451.
[11]	Hui Chen and Yang Xiao, “On-Bound Selection Cache Replacement Policy for Wireless Data Access,” Computers, IEEE Transactions on,  2007, Volume: 56 , Issue: 12, Page(s): 1597 - 1611.
[12]	Guohong Cao, Member, IEEE, “Proactive Power-Aware Cache Management for Mobile Computing Systems,” IEEE TRANSACTIONS ON COMPUTERS, VOL. 51, NO. 6, JUNE 2002, Page(s): 608 - 621.
[13]	Yi-Bing Lin, Wei-Ru Lai, and Jen-Jee Chen, “Effects of Cache Mechanism on Wireless Data Access,” IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS, VOL. 2, NO. 6, NOVEMBER 2003, Page(s): 1247 - 1258.
[14]	Takahiro Hara, “Cooperative Caching by Mobile Clients in Push-based Information Systems”, Parallel Architectures, Algorithms and Networks, 2004. Proceedings. 7th International Symposium on, 2004.
[15]	Francoise Sailhan and Valerie Issarny, “Cooperative Caching in Ad Hoc Networks”, In Proceedings of the 4th International Conference on Mobile Data Management, McLean, Virginia, USA , 2003, Pages: 13 - 28.
[16]	Liangzhong Yin and Guohong Cao, “Supporting Cooperative Caching in Ad Hoc Networks,” IEEE TRANSACTIONS ON MOBILE COMPUTING, 2006, VOL. 5, NO. 1, JANUARY, Page(s): 77 - 89.
[17]	Edward Chana, Wenzhong Li and Daoxu Chenb, “Energy saving strategies for cooperative cache replacement in mobile ad hoc networks,” Pervasive and Mobile Computing 5, February 2009 pp. 77~92.
[18]	Shudong Jin and Azer Bestavros, “Cache-and-Relay Streaming Media Delivery for Asynchronous Clients,” NGC, 2002. Computer Science Department Boston University, Boston USA, 2002.
[19]	Hui Guo and Kwok-Tung Lo, “Cooperative Media Data Streaming with Scalable Video Coding,” IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, September 2008, VOL. 20, NO. 9, SEPTEMBER, Page(s): 1273 - 1281.
[20]	Maozhi Hu, Ke Xu, Shu-tao Xia and Mingjiang Ye, “TOW: A Novel Time and Popularity Sensitive Cache Algorithm for P2P Live Media Streaming,” Communications and Networking in China 2008, ChinaCom 2008, 25-27 Aug. 2008,Page(s): 213 - 217.
[21]	Feng Jian, “A Novel Caching Mechanism for P2P Video-on-Demand Systems,” Second International Conference on Future Generation Communication and Networking, 13-15 Dec. 2008, Page(s): 140 - 143.
[22]	Ye Tian, Di Wu and Kam-Wing Ng, “A novel caching mechanism for peer-to-peer based media-on-demand streaming,” Journal of Systems Architecture 54 (2008) pp. 55–69
[23]	Heiko Schwarz and Mathias Wien, “The Scalable Video Coding Extension of the H.264/AVC Standard,” IEEE SIGNAL PROCESSING MAGAZINE, MARCH 2008.
[24]	Edouard Francois, Jerome Vieron, and Vincent Bottreau, “Interlaced Coding in SVC,” IEEE TRANSACTIONS ON CIRCUITS AND SYSTEM FOR VIDEO TECHNOLOGY VOL. 17, NO. 9, SEPTEMBER 2007, Page(s): 1136 - 1148.
[25]	黃柏昌、李維聰, “應用於H.264/SVC之適應性正向錯誤修正與交錯式順序機制於無線網路之研究,” 淡江大學電機工程學系碩士班 (積體電路與計算機系統組) 碩士論文 民98.
[26]	曾煜棋、潘孟鉉、林致宇, “無線區域及個人網路-隨意及感測器網路之技術與應用,” acore 知城圖書出版發行 民95.