跳到主要內容

臺灣博碩士論文加值系統

(35.173.42.124) 您好!臺灣時間:2021/07/24 09:15
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:朱中華
研究生(外文):Chung-Hua Chu
論文名稱:行動資訊系統中之有效資料傳輸
論文名稱(外文):Effective Data Dissemination in Mobile Data Systems
指導教授:陳銘憲陳銘憲引用關係
學位類別:博士
校院名稱:國立臺灣大學
系所名稱:電信工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2008
畢業學年度:97
語文別:英文
論文頁數:118
中文關鍵詞:資料廣播網路編碼時變無線頻寬即時資料廣播廣播排程
外文關鍵詞:data broadcastnetwork codingtime-variant bandwidthon-demand
相關次數:
  • 被引用被引用:0
  • 點閱點閱:98
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:1
隨著快速發展之行動通訊科技,使用者可以在任意時間及任何地點以無線行動裝置,如:筆記型電腦,PDA及智慧型手機來存取資訊。資料廣播是一項先進的技術,此技術可在行動資訊環境中達到高延展性及有效使用頻寬。因此,有各式各樣的技術被設計來提供資料廣播環境中更好的服務。
在資料廣播環境中各個頻道的頻寬是會隨著時間改變的,但傳統資料排程技術未考慮到這個問題。因此,在排程資料時未考慮此問題將會大大降低系統之效能。在本論文中,我們將探討如何在隨時間變化之多頻道頻寬的廣播環境中排程資料的問題。鑑於多頻道時變頻寬的特性,我們提出了可適性時變頻寬演算法來排程資料並且降低平均等待時間。
此外在傳統資料廣播中,伺服器在每個時間點廣播一筆資料。因此,若有使用者在同一時間點想存取兩頻道的資料,上述限制將導致存取衝突使得使用者必須等待下一個廣播週期才能得到想要的資料。在本論文中,我們提出嶄新的動態資料廣播架構。在此架構,資訊系統不再是廣播單筆資料,而是廣播混合多筆資料的編碼資料。我們根據使用者已存的資料並採用網路編碼技術使得資訊系統可在每個時間點使資料系統能動態地將多個資料做編碼。使用者可使用已存的資料來解碼已得到之編碼資料,進而得到需求的資料。因此,我們提出了一套演算法來動態地產生並排程編碼資料來降低平均等待時間。
即時要求及回應模式之資料廣播具有高延展性,因此被廣泛應用於行動計算之環境。然而,之前在此系統之研究仍受限於每個時間點只能廣播一筆資料。此限制不但降低系統的延展性且導致較長的等待時間。在本論文中,我們探討如何應用網路編碼之技術來提升系統的延展性及降低平均等待時間。為了提供即時服務及達到高延展性,我們提出即時編碼系統。有別於傳統網路編碼,我們的方法只編碼部分資料而非所有資料。此外,編碼是根據使用者已存的資料及查詢的資料。因此,可快速產生編碼資料且減少不必要的編碼。
With the rapid advances in wireless mobile communication technologies, mobile users can access information anytime, anywhere, via wireless mobile devices such as notebooks, PDA, smart phones, and so on. Data broadcast is an advanced technique to realize the large scalability and bandwidth utilization in a mobile computing environment. Therefore, various techniques have been devised to provide preferable services in the data broadcast environment.
In this environment, the channel bandwidth of each channel is variant with time in real cases. However, traditional schemes do not consider the time-variant bandwidth of each channel to schedule data items. Therefore, the above drawback degrades the quality in generating the broadcast program. In this dissertation, we address the problem of generating a broadcast program to disseminate data via the multiple channels of the time-variant bandwidth. In view of the characteristics of the time-variant bandwidth, we propose an algorithm using adaptive allocation on time-variant bandwidth to generate the broadcast program to avoid the above drawback to minimize the average waiting time.
In addition, traditional data broadcasting assumes that mobile users can only retrieve one data item in each time slot. Therefore, the above constraint leads to access conflicts and requires the mobile users to wait until the next broadcast cycle to retrieve the requested information. In this dissertation, we propose a novel dynamic data broadcasting framework that adopts network coding with stored data items in users. Our approach enables a server to dynamically encode multiple data items in each time slot, while each mobile user is able to retrieve the data item by decoding the encoded data items by using the locally stored data items. We propose an algorithm to dynamically generate a broadcast program to minimize average access time in the dynamic environment.
On-demand data broadcast is widely deployed to achieve high scalability in a mobile computing environment. However, traditional on-demand data broadcasting assumes that each time slot includes only one data item. Therefore, the above constraint limits the number of users that can be served in each time slot and leads to long latency. In this dissertation, we propose a new on-demand data broadcast model with modified network coding. Our approach is different from the traditional network coding because each time slot encodes only a subset of data items, which are decided according to the identities of requested and stored data items of users.
1 Introduction 1
1.1 Motivation and Overview of the Dissertation . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Data Broadcasting . . . . . . . . . . . . . . . . . . . . . 1
1.1.2 Network Coding . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.3 Dependent Data Broadcast . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.4 On-demand Data Broadcast . . . . . . . . . . . . . . . . . . . . . . . 6
1.2 Organization of Dissertation . . . . . . . . . . . . . . . . . . . . . . 6
2 A General Framework of Time-variant Bandwidth Allocation in the Data Broadcasting
Environment. . . . . . . . . . . . . . . . . . . . . . . 8
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . 11
2.2.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.2 System Architecture . . . . . . . . . . . . . . . . . . . . . . 13
2.2.3 Notation and Definition . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.4 AnalyticalModel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.5 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3 Bandwidth-allocation BroadcastProgram . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.1 Design Intuition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.2 Static Bandwidth AllocationAlgorithm . . . . . . . . . . . . . . . . . . . . . 21
2.3.3 Dynamic Bandwidth Allocation . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3.4 Example for Execution ScenariounderABA . . . . . . . . . . . . . . . . . . 36
2.4 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.4.1 Scenario 1: Constant Data Size and Variant Bandwidth . . . . . . . . . . . . . 43
2.4.2 Scenario 2: Variant Data Size and Variant Bandwidth . . . . . . . . . . . . . . 47
2.4.3 Scenario3: Time-variantBandwidthAllocation . . . . . . . . . . . . . . . . . 50
2.4.4 Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3 A General Framework for Dependent Data Broadcasting Based on Network Coding in a
Mobile Environment 56
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.2.1 System Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
1
3.2.2 Derivation of Access Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.3 Generating A Broadcast Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.3.1 Design Intuition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.3.2 Encode-Based Channel AllocationAlgorithm . . . . . . . . . . . . . . . . . . 65
3.4 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
3.4.1 Simulation Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
3.4.2 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
3.4.3 EfficiencyAnalysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
3.4.4 Adaptiveness Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
3.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
4 Multi-data Delivery Based on Network Coding in On-demand Broadcast 93
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
4.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
4.2.1 System Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
4.2.2 Derivation of Access Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
4.2.3 Notation and Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
4.3 Generating A Broadcast Schedule . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
4.3.1 Design Intuition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
4.3.2 Encode-Based Scheduling Algorithm . . . . . . . . . . . . . . . . . . . . . . 99
4.4 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
4.4.1 Simulation Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
4.4.2 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
5 Conclusion . . . . . . . . .111
[1] Comm View. http://www.tamos.com/products/commwifi/.
[2] EB Propsim C8. http://www.elektrobit.com/index.php?207.
[3] The working group for IEEE 802.11 WLAN standards. http://www.ieee802.org/11/.
[4] Spatial Channel Model for Multiple-Input Multiple Output Simulations, 3GPP TR 25.996v1.0.0.
http://www.3gpp.org. 2003.
[5] ETSI standard EN 302 304. http://www.dvb-h.org/. 2004.
[6] Predictive Data Rate Control in Wireless Transmitters, US Patern 6707862. 2004.
[7] S. Acharya, R. Alonso, M. J. Franklin, and S. B. Zdonik. Broadcast disks: Data management
for asymmetric communications environments. In Proceedings of the 1995 ACM International
Conference on Management of Data, pages 199–210, May 1995.
[8] S. Acharya and S. Muthukrishnan. Scheduling on-demand broadcasts: New metrics and algorithms.
In Proceedings of the 4th ACM/IEEE International Conference on Mobile Computing and
Networking, pages 43–54, 1998.
[9] R. Ahlswede, N. Cai, and R. W. Yeung. Network information flow. In IEEE Transactions on
Information Theory, 2000.
[10] D. Aksoy and M. Franklin. Rxw: A scheduling approach for large-scale on-demand data broadcast.
IEEE/ACM Transactions on Networking, 7(6):846–860, 1999.
[11] D. Aksoy and M. J. Franklin. Scheduling for large-scale on-demand data broadcasting. In Proceedings
of IEEE INFOCOM, March 1998.
[12] P. Ayyagari, P. Mitra, and A. Hurson. Efficient object retrieval from parallel air channels in the
presence of replicated objects. In Proceedings of the 7th International Conference on Mobile
Data Management (MDM-06), 2006.
[13] D. Barbará. Mobile computing and database - a survey. IEEE Transactions on Knowledge and
Data Engineering, 11(1):108–117, 1999.
[14] Y. Birk and T. Kol. Coding on demand by an informed source (iscod) for efficient broadcast
of different supplemental data to caching clients. IEEE Transactions on Information Theory,
52(6):2825–2830, 2006.
[15] M.-S. Chen, P. S. Yu, and K.-L.Wu. Optimizing index allocation for sequential data broadcasting
in wireless mobile computing. IEEE Transactions on knowledge and Data Engineering, 15(1),
February 2003.
[16] H. H. Chi-Wai Lin and D.-L. Lee. Adaptive realtime bandwidth allocation for wireless data
delivery. In Wireless Network (WINET), volume 10, pages 103–120, 2004.
[17] C.-H. Chu, H.-P. Hung, and M.-S. Chen. Variant bandwidth channel allocation in the data broadcasting
environment. In IEEE International Conference onMobile Data Management (MDM-07),
2007.
[18] C.-H. Chu, D.-N. Yang, and M.-S. Chen. Using network coding for dependent data broadcasting
in a mobile environment. In IEEE GLOBECOM, 2007.
[19] Y. D. Chung and M. H. Kim. Qem: A scheduling method for wireless broadcast data. In Proceedings
of the International Conference on Database Systems for Avanced Applications (DSFAA’99),
pages 135–142, 1999.
[20] S. Deb,M.M. edard, and C. Choute. On random network coding based information dissemination.
IEEE International Symposium on Information Theory(ISIT 2005), 2005.
[21] C. Fragouli, J.-Y. L. Boudec, and J. Widmer. Network coding: An instant primer. In SIGCOMM,
2006.
[22] C. Gkantsidis and P. R. Rodriguez. Network coding for large scale content distribution. In Proceedings
of IEEE INFOCOM, 2005.
[23] D. E. Goldberg. Genetic algorithm in search, optimization and machine learning. Addison-Wesley
Publishing, 1989.
[24] Y.-N. P. Guanling Lee and A. L. Chen. Scheduling real-time data items in multiple chanels
and multiple receivers environments. In Proceedings of the IEEE International Conference on
Distributed Computing Systems(ICDCS-2002), 2002.
[25] S. Hameed and N. H. Vaidya. Log-time algorithms for scheduling single and multiple channel
data broadcast. In ACM International Conference on Mobile Computing and Networking(
MobiCom’97), 1997.
[26] S. Hameed and N. H. Vaidya. Efficient algorithms for scheduling data broadcast. ACM/Baltzer
Wireless Networks, 5(3):183–193, 1999.
[27] T. Ho, R. Koetter, M. Medard, D. R. Karger, and M. Effros. The benefits of coding over routing
in a randomized setting. In IEEE International Symposium on Information Theory (ISIT), 2003.
[28] C.-H. Hsu, G. Lee, and A. L. P. Chen. A near optimal algorithm for generating broadcast programs
on multiple channels. In Proceedings of the 10th ACM International Conference on Information
and Knowledge Management, pages 303–309, 2001.
[29] J.-L. Huang andM.-S. Chen. Broadcasting dependent data for ordered queries without replication
in amulti-channel mobile environment. In Proceedings of the 19th IEEE International Conference
on Data Engineering, March 2003.
[30] J.-L. Huang and M.-S. Chen. Dependent data broadcasting for unordered queries in a multiple
channel mobile environment. IEEE Trans. on Knowledge and Data Engineering, 16(6), Jun. 2004.
[31] J.-L. Huang, M.-S. Chen, and H.-P. Hung. A qos-aware transcoding proxy using on-demand data
broadcasting. In Proceedings of IEEE INFOCOM, March 2004.
[32] J.-L. Huang and W.-C. Peng. An effective broadcast program generation algorithm for dependent
data. In Proceedings of the 5th Emerging Information Technology Conference (EITC-05), 2005.
[33] H.-P. Hung and M.-S. Chen. A general model of hybrid data dissemination. In Proceedings of the
6th International Conference on Mobile Data Management (MDM-05), May 2005.
[34] H. P. Hung and M. S. Chen. On exploring channel allocation in the diverse data broadcasting
environment. In Proc. of the 25th IEEE International Conference on Distributed Computing
Systems (ICDCS-2005), 2005.
[35] H.-P. Hung and M.-S. Chen. Efficient data broadcasting by progressively merging and splitting
data broadcasting environment. In Proceedings of IEEE GLOBECOM, 2006.
[36] H.-P. Hung and M.-S. Chen. Muls:a general framework of providing multi-level service quality
in sequential data broadcasting. IEEE Transactions on Knowledge and Data Engineering,
19(10):1433–1447, 2007.
[37] H.-P. Hung, J.-W. Huang, J.-L. Huang, and M.-S. Chen. Scheduling dependent items in data
broadcasting environments. In Proceedings of ACM SAC’06, March 2006.
[38] A. R. Hurson, Y. C. Chehadeh, and J. Hannan. Object organization on parallel broadcast chennels
in a global information sharing environment. IEEE International Performance, Computing, and
communication Conference, pages 347–353, 2000.
[39] T. Imielinski, S. Viswanathan, and B. R. Badrinath. Energy efficient indexing on air. In Proceedings
of the 1994 ACM International Conference on Management of Data, pages 25–36, 1994.
[40] T. Imielinski, S. Viswanathan, and B. R. Badrinath. Data on air: Organization and access. IEEE
Transactions on Knowledge and Data Engineering, 9(3):353–372, May/June 1997.
[41] S. Jaggi, P. Sanders, P. A. Chou, M. Effros, S. Egner, K. Jain, and L. Tolhuizen. Polynomial time
algorithms for multicast network code construction. IEEE Trans. on Information Theory, 15(6),
2005.
[42] G. Lee, M. Yeh, S. Lo, and A. Chen. A strategy for efficient access ofmultiple data items in mobile
environments. In Proceedings of the 3rd International Conference on Mobile Data Management,
pages 71–78, 2002.
[43] W.-C. Lee, Q. Hu, and D. L. Lee. A study on channel allocation for data dissemination in mobile
computing environments. ACM/Baltzer Mobile Networks and Applications, Special Issue on
Resource Management in Wireless Systems, 4(2):117–129, 1999.
[44] S.-Y. R. Li, R. W. Yeung, and N. Cai. Linear network coding. IEEE Transactions on Information
Theory, 49:371–381, 2003.
[45] A. Nanopoulos, D. Katsaros, and Y. Manolopouslos. Effective prediction of web-user accesses:
A data mining approach. Proc. WEBKDD Workshop, 2001.
[46] W.-C. Peng and M.-S. Chen. Dynamic generation of data broadcasting programs for a broadcast
disk array in a mobile computing environment. In Proceedings of the 9th ACM International
Conference on Information and Knowledge Management, November 2000.
[47] W.-C. Peng, J.-L. Huang, and M. S. Chen. Dynamic leveling: Adaptive data broadcasting in a
mobile computing environment. Mobile Networks and Applications, 8(4):355–364, 2003.
[48] E. Pitoura and R. Chrusanthis. Scalable processing of read-only transactions in broadcast push.
In Proceedings of IEEE ICDCS’99, September 1999.
[49] N. Prabhu and V. Kumar. Data scheduling for multi-item and transactional requests in on-demand
broadcast. In Proceedings of IEEE International Conference on Mobile Data Management, May
2005.
[50] K. Stathatos, N. Roussopoulos, and J. S. Baras. Adaptive data broadcast in hybrid networks. In
Proceedings of the 23rd International Conference on Very Large Data Bases, August 1997.
[51] B. Sun, A. R. Hurson, and J. Hannan. Energy-efficientscheduling algorithms of object retrieval
on indexed paralled broadcast channels. Proceedings of the 2004 International Conference on
Parallel Processing (ICPP’04), 2004.
[52] J. W. Wong. Broadcast delivery. Proceedings of The IEEE, 76(12):1566–1577, December 1988.
[53] Y.Wu, P. . Chou, and K. Jain. A comparison of network codig and packing. In IEEE International
Symposium on Information Theory (ISIT), 2004.
[54] J. Xu, D. L. Lee, and B. Li. On bandwidth allocation for data dissemination in cellular mobile
networks. In ACM/Kluwer Journal of Wireless Networks (WINET), Special Issue on Advances in
Mobile and Wireless, volume 9 of 2, pages 103–116, 2003.
[55] J. Xu, X. Tang, andW.-C. Lee. Time-critical on-demand data broadcast: Algorithms, analysis, and
performance evaluation. IEEE Transactions on Parallel and Distributed Systems, 17(1), January
2006.
[56] W.-G. Yee, S. B. Navathe, E. Omiecinski, and C. Jermaine. Efficient data allocation over multiple
channels at broadcast servers. IEEE Transactions on Computers, 15(10):1231–1236, October
2002.
[57] B. Zheng, X. Wu, X. Jin, and D. L. Lee. Tosa: A near-optimal scheduling algorithm for multichannel
data broadcast. In Proceedings of the 6th International Conference on Mobile Data
Management (MDM-05), May 2005.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top