跳到主要內容

臺灣博碩士論文加值系統

(52.203.18.65) 您好!臺灣時間:2022/01/19 15:52
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:王士嘉
研究生(外文):Shih-Chia Wang
論文名稱:多時間限制頻道的資料配置
論文名稱(外文):Data Allocation for Multiple Time-Constraint Channels
指導教授:李強李強引用關係
指導教授(外文):Chiang Lee
學位類別:碩士
校院名稱:國立成功大學
系所名稱:資訊工程學系碩博士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
論文頁數:153
中文關鍵詞:多頻道時間限制行動計算頻道排程
外文關鍵詞:multiple channelstime-constraintchannel schedulemobile computing
相關次數:
  • 被引用被引用:0
  • 點閱點閱:197
  • 評分評分:
  • 下載下載:26
  • 收藏至我的研究室書目清單書目收藏:0
在無線環境下, 針對具有 time constraint 的 query results,傳統的 broadcast 和 on-demand 方式並無法保證當 query results 播出後,mobile user 能在 time constraint 內存取完 query results.因此, 設計一種新 channel 的使用方式, 專門排程這些具有 time constraint 的query results, 這樣的 channel 稱為 time-constraint channels.我們設計出使用最少的 channel 數和能滿足所有 mobile user 的 time constraint 的排程,名為 TFT-Based Scheduling Algorithm.另外也針對三種常影響排程的因素(Duplication Data, Data Order,and Limited Channels), 設計了適合的排程.
在以最少 channel 數排程的觀念下,以排程使用數為評比標準的 experiments 和 results 也呈現在這Paper.
In wireless environment, if query results are scheduled with time constraint,traditional Broadcast and On-demand technologies can not guarantee that mobile can access query results within time constraint.Hence, we design new channel scheduling technology,specially for scheduling query results with time constraints,and we called time-constraint channels.We design scheduling algorithm called TFT-Based Schedulig Algorithm}which can use minimum channels and satisfy all time constraint when mobile useraccess query results.And then, we consider three factors which will affect schedule(Duplication data, Data Order,and Limited Channels),and design scheduling algorithm to minimize the number of used time-constraint channels.

  Within the consept of using minimal channels,experiments and results with this concept are also presented in this paper.
Abstract i
Acknowledgements iii
Table of Contents iv
Table of Figures v
Table of Tables vi
Table of Algorithms vii
1 Introduction .... 1
1.1 Wireless Comuunication Environments ..................... 1
1.2 Motivations ..................... 2
1.3 Related Work ..................... 6
1.4 Thesis Organization ..................... 8
2 System Model and Parameters ..................... 10
3 Scheduling Time-Constrained Query Results..................... 16
3.1 Preliminaries ..................... 16
3.1.1 要如何才能使用最少 channel 數..................... 16
3.1.2 如何滿足從任何 time slots 進來的使用者.....................17
3.2 Time Fragment Transformation (TFT)..................... 21
3.3 TFT-Based Schedule for Time-Constraint Query Results .. 39
3.4 Validity of TFT-Based Schedule .....................42
3.4.1 使用最少 channels 排程 query results .....................44
3.4.2 說明 Mobile user 在每個時間點進入都可以在 time constraint 內存取到 query results.....47
3.5 Discussion: Is the Schedule Order of Queries Important?...52
3.5.1 保證在最少的 channel 數下排程完所有的 query results ....52
3.5.2 降低 computing 的 overhead .....................55
3.6 Example - TFT-Based Scheduling Algorithm..................... 56
4 Reducing Duplication Pages in Time-Constraint Broadcast Schedule ...59
4.1 Preliminaries ..................... 59
4.2 Two Phases Algorithm: Shrinking Method .....................66
4.2.1 Supporting Data Structure for Shrinking Method ... 67
4.2.2 Shrinking Algorithm..................... 67
4.2.3 Example of Shrinking..................... 75
4.3 One Phase Algorithm: Growing Method ..................... 78
4.3.1 Supporting Data Structure for Growing Method .... 78
4.3.2 DuplicationDegree ..................... 79
4.3.3 Growing Algorithm ..................... 80
4.3.4 Insert A Scheduled Page ...................... 82
4.3.5 Insert A New Page..................... 84
4.3.6 Example of Growing..................... 85
5 Time-Constraint Broadcast Schedule Considering Ordering Access Property... 89
5.1 Preliminary..................... 89
5.2 Rules for Scheduling Ordering Accessing Query Results.... 90
5.2.1 Rules for Scheduling time constraint(q) >= 2*|q|....... 92
5.2.2 Rules for Scheduling time constraint(q) < 2*|q| ....... 93
5.2.3 Short Summaries for Scheduling Ordering Accessing Query Results ...978
5.3 Supporting Data Structure for Scheduling.....................97
5.4 Algorithm..................... 98
5.5 Example for Data Ordering ..................... 100
6 Time-Constraint Broadcast Schedule Considering Limited Channels.....106
6.1 Page Dropping Rules for Limited Channels .....................106
6.1.1 滿足最多的 page 數.....................107
6.1.2 滿足愈多緊迫的 query results..................... 108
6.1.3 滿足最多的 query results 數.....................109
6.2 Schedule ..................... 110
7 Performance.. 113
7.1 SimulationModel ..................... 113
7.1.1 ServerModel ....................... 113
7.1.2 ClientModel ..................... 114
7.1.3 Query Results Generator ..................... 114
7.1.4 Default Value ..................... 118
7.2 Experiments and Results .....................119
7.2.1 TFT-Based .....................119
7.2.2 DuplicationData ..................... 121
7.2.3 Data Order ..................... 122
7.2.4 Limited Channels ..................... 125
8 Integration....... 131
9 Conclusions and Future Work...... 134
9.1 Conclusions ..................... 134
9.2 FutureWork ..................... 134
Bibliography 136
A Complexity of the Brute Force Method to Schedule Time-Constraint Queries .....146
B Merge Channels which scheduling ordering query results is NP-Complete ........147
C Satisfying Most Pages in Decision Rule 1 is a Optimal-Decision Problem .......148
D How to simulate Zi ......150
E How to gain Optimal(minimum channels) when scheduling duplication data ........152
Biography...... 153
[AAFZ95]Swarup Acharya, Rafael Alonso, Michael Franklin, and Stanley Zdonik,
``Broadcast Disks: Data Management for Asymmetric Communication Environments,'
in Proceedings of ACM SIGMOD International Conference on Management of Data (SIGMOD),
San Jose, CA USA, May 22-25, 1995, pp 199-210.

[VH96a]Nitin H. Vaidya, and Sohail Hameed,
``Data Broadcast in Asymmetric Wireless Environments,'
in First International Workshop on Satellite-based Information Services (WOSBIS),
Rye, NY, November, 1996.

[VH96b]Nitin H. Vaidya, and Sohail Hameed
``Data Broadcast Scheduling: On-line and Off-line Algorithms,'
Technical Report 96-017,
Computer Science, Texas A&M Univ., July, 1996.

[VH96c]Nitin H. Vaidya, and Sohail Hameed,
``Improved Algorithms for Scheduling Data Broadcast,'
Technical Report 96-029,
Computer Science, Texas A&M Univ., December, 1996.

[AFZ96]Swarup Acharya, Michael Franklin,and Stanley Zdonik,
``Prefetching from a Broadcast Disk,'
in Proceedings of the 12th International Conference on Data Engineering,
New Orleans, Louisiana, February 26-March 1, 1996, pp 276-285.

[AFZ97a]Swarup Acharya, Michael Franklin and Stanley Zdonik,
``Balancing push and pull for data broadcast,'
in Proceedings of the ACM SIGMOD international conference on Management of data,
Tucson, Arizona, United States, 1997, pp 183-194.

[XSGFR97]Ping Xuan, Subhabrata Sen, Oscar Gonzalez, Jesus Fernandez and Krithi Ramamritham
``Broadcast on Demand: Efficient and Timely Dissemination of Data in Mobile Environments,'
in Proceedings of the 3rd IEEE Real-Time Technology and Applications Symposium (RTAS '97),
Montreal, CANADA, June 9-11, 1997,

[AFZ97b]Swarup Acharya, Michael Franklin,and Stanley Zdonik,
``Disseminating Updates on broadcast disks,'
in Proceedings of 22nd VLDB Conference,
Mumbai (Bombay), India, September 3-6, 1997, pp 356-365.

[CSW97]Ming-Syan Chen, Yu, P.S,and Kun Lung Wu
``Indexed sequential data broadcasting in wireless mobile computing,'
in Proceedings of the 17th International Conference on Distributed Computing Systems,
May 27-30, 1997,pp 124-131.

[CSW97] Sohail Hameed, Nitin H. Vaidya
``Log-Time Algorithms for Scheduling Single and Multiple Channel Data Broadcast,'
in Proceedings of the Third Annual ACM/IEEE International Conference on Mobile Computing and Networking(MOBICOM97),
Budapest,September 26-30, 1997, pp 90-99.

[BB97] Sanjoy Baruah ,and Azer Bestavros,
``Pinwheel scheduling for fault-tolerant broadcast disks in real-time database systems,'
in Proceedings of 13th ICDE,
Birmingham, April 7-11, 1997, pp 543-551.

[FZ98] Michael Franklin, and Stanley Zdonik,
``Data In Your Face": Push Technology in Perspective,'
in Proceedings of ACM SIGMOD International Conference on Management of Data (SIGMOD 98),
Seattle, WA, June, 1998, pp 516-519.

[TY98] Kian-Lee Tan, and Jeffrey X. Yu,
``Generating Broadcast Programs that Support Range Queries,'
Transactions on Knowledge and Data Engineering, Vol 10, No 4,
January/February, 1998, pp 668-672.

[OUL98] O.Ulusoy,
``Real-Time Database Management for Mobile Computing,'
in Proceedings of International Workshop on Issues and Applications of Database Technology (IADT'98),
Berlin, Germany, July, 1998, pp 233-240.
[AF98] Demet Aksoy, and Michael Franklin,
``Scheduling for large-scale on-demand data broadcastung,'
in Proceedings of IEEE INFOCOM,
San Francisco, CA, March, 1998, pp 651-659.

[AM98] Swarup Acharya, and S. Muthukrishnan,
``Scheduling On-Demand Broadcasts: New Metrics and Algorithms,'
in Proceedings of the Fourth Annual ACM/IEEE International Conference on Mobile Computing and Networking(MobiCom '98),
Dallas,TX, October, 1998, pp 43-54.

[STT99]Chi-Jiun Su, Leandros Tassiulas and Vassilis J. Tsotras,
``Broadcast scheduling for information distribution,'
ACM Wireless Networks}, Vol 5, No 2,
March, 1999, pp 137-147.

[LCY99]Kam-yiu Lam, Edward Chan, and Chun-Hung Yuen,
``Data Broadcast for Time-Constrained Read-Only Transactions in Mobile Computing Systems,'
in Proceedings of the First International Workshop on Advance Issues of E-Commerce and Web-Based Information Systems,
Santa Clara, California, April 8-9, 1999, pp 11-19.

[HV99]Sohail Hameed, and Nitin H. Vaidya,
``Efficient algorithms for scheduling data broadcast,'
ACM Wireless Networks,Vol 5,
1999,pp 183-193.

[AF99] Demet Aksoy and Michael Franklin ,
``R$imes$W: a scheduling approach for large-scale on-demand data broadcast,'
in Proceedings of IEEE/ACM Transactions on Networking 7(6),
New York, USA, December, 1999, pp 846-860.

[JV99] Shu Jiang, and Nitin H. Vaidya,
``Scheduling data broadcast to "impatient" users,'
in Proceedings of the ACM international workshop on Data engineering for wireless and mobile access,
Seattle, WA USA ,August 20, 1999, pp 52-59.

[PC00]Wen Chih Peng, and Ming Syan Chen,
``Dynamic Generation of Data Broadcasting Programs for a Broadcast Disk Array in a Mobile Computing Environment,'
in Proceedings of the ACU 9th International Conference on Information and Knowledge Management (CIKM 2240),
McLean, VA USA, November 6-11, 2000, pp 38-45.

[PHO00] Kiran Prabhakara, Kien A. Hua, and JungHwan Oh,
``Multi-Level Multi-Channel Air Cache Designs For Broadcasting in a Mobile Environment,'
in Proceesings of 13th International Conference on Data Engineering (ICDE 2000),
San Diego, CA, USA, February 28-March 3, 2000, pp 167-176.

[LC00]Shou-Chih Lo and Arbee L.P. Chen,
``Optimal Index and Data Allocation in Multiple Broadcast Channels,'
in Proceednngs of 16th International Conference on Data Engineering (ICDE 2000),
San Diego, CA, USA, February 28-March 3, 2000, pp 293-302.

[KSY00] Claire Kenyon, Nicolas Schabanel, and Neal Young,
``Polynomial-Time Approxdmation Scheme for Data Broadcast,'
in Proceedings of the Thirty-second Annual Acm Symposium on Theory of Computing (STOC 0700),
Portland Oregon USA, May 21-23, 2000, pp 659-666.

[AJB00] Amotz Bar-Noy, Joseph Naor, and Baruch Schieber,
``Pushing Dependent Data in Clients-Providers-Servers Systems,'
in Proceedings of the Sixth Annual International Conference on Mobile Computing and Networking (MOBICOM2000),
Boston MA USA, August 6-11, 2000, pp 222-230.

[AFZ01] Demet Aksoy, Michael Franklin, and Stan Zdoni,
``Data Staging for On-Demand Broadcast,'
in Proceedings of VLDB Conference,
,Rome ,September 2001 , pp 571-580.

[HLC01] C.H. Hsu, G. Lee and A.L.P. Chen,
``A Near Optimal Algorithm for Generating Broadcast Programs on Multiple Channels,'
in ACM International Conference on Information and Knowledge Management(CIKM2001),
Atlanta, Georgia, November 2001, pp 303-309.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top