移动数据库中数据广播技术的研究
|
摘要
随着计算机技术、移动通讯技术和互联网技术的迅速发展，移动数据库得到广泛的应用。公共信息发布的应用中，分布广泛的数据库系统通过广播向客户端发布数据，客户端监听广播信道，当数据到来时，客户端读取所需的数据。对于移动客户来说，获取最新的数据是非常重要的，访问过时的信息是毫无意义的，因此数据广播更有利于维护数据的新鲜性和有效性。同时在无线单元内，从服务器到移动客户的下行通信带宽一般要远大于从移动客户到服务器的上行通信带宽，而且移动客户从服务器接受数据的开销也远小于发送开销，因此即使是处于断接状态的移动客户也可以选择接收从服务器发送的下行广播数据。于是，可以利用这种网络的非对称性，由数据服务器把大量的客户感兴趣的数据组织起来，以周期性的广播形式提供给移动客户。
在数据广播中，数据记录被访问的概率各不相同，因此可以通过访问概率建立索引树。索引树的结构决定了平均访问索引节点的数目，但是即使对于相同的索引结构，如果采用不同的广播序列，则平均访问时间也不尽相同。要为给定的索引结构设计最优广播序列不仅需要考虑已经存在的索引结点，还需要考虑索引树的结构。采用索引广播的方式可以使移动设备选择性地侦听信道，通过建立基于数据访问概率的索引树，以降低平均访问代价。
本文根据数据广播中数据记录被访问的概率不同的特点，通过对数据广播中的索引广播技术的研究，包括已有的基于数据访问概率的索引树，同时分析研究了具有很低数据平均预期延迟时间数据广播算法—数据广播中高效通道分配树算法，最后提出基于可变数据项的通道分配算法(VDCA)，从而减少数据广播的数据平均预期延迟时间，同时降低了平均访问代价。
In pace with rapid development in the computer technology, the mobile communication technology and the Internet technology, the mobile database is extensively applied. In the public information issue application, the widespread database system issue data through the broadcast to the client side, the client side monitor the broadcast channel, the client side reading the required data when data arrival. It is very important to gain the most recent data to the mobile client, the visits of the obsolete information is insignificant, therefore the broadcast is more advantageous to service data fresh and the validity. Meanwhile in the wireless unit, the downstream communication always far more than the upstream communication, moreover the expenses of the mobile client accepts data from the server also far to be smaller than the transmission expenses, even if under the separation condition, the mobile client also to be possible to selective receive the broadcast data which transmits from the server. Therefore, may use this kind of the asymmetry of the network, the data server organize the data which the mobile client interested, and sent to the mobile client by the periodic broadcast.
In the data broadcast, the visits probability of the data record is various, therefore the index tree may be built through visit probability. The structure of the index tree decides the average index number to be visited, but even regarding the same index structure, the average visit time is different if the broadcast sequence is different. If we want to design the most superior broadcast sequence for the existed index structure, we should consider not only the existed index point, but also the structure of the index tree. The mobile client may selectively to intercept the channel by the index broadcast, the average cost can be reduced through the establishment base on the data accessing probability of the index tree.
This dissertation according to the character of the different visit probability of the record in the data broadcast, through the research on index broadcast technology of the data broadcast, including the existed index tree base on the data accessing probability, and introduce the data broadcast algorithm with very low data average
在数据广播中，数据记录被访问的概率各不相同，因此可以通过访问概率建立索引树。索引树的结构决定了平均访问索引节点的数目，但是即使对于相同的索引结构，如果采用不同的广播序列，则平均访问时间也不尽相同。要为给定的索引结构设计最优广播序列不仅需要考虑已经存在的索引结点，还需要考虑索引树的结构。采用索引广播的方式可以使移动设备选择性地侦听信道，通过建立基于数据访问概率的索引树，以降低平均访问代价。
本文根据数据广播中数据记录被访问的概率不同的特点，通过对数据广播中的索引广播技术的研究，包括已有的基于数据访问概率的索引树，同时分析研究了具有很低数据平均预期延迟时间数据广播算法—数据广播中高效通道分配树算法，最后提出基于可变数据项的通道分配算法(VDCA)，从而减少数据广播的数据平均预期延迟时间，同时降低了平均访问代价。
In pace with rapid development in the computer technology, the mobile communication technology and the Internet technology, the mobile database is extensively applied. In the public information issue application, the widespread database system issue data through the broadcast to the client side, the client side monitor the broadcast channel, the client side reading the required data when data arrival. It is very important to gain the most recent data to the mobile client, the visits of the obsolete information is insignificant, therefore the broadcast is more advantageous to service data fresh and the validity. Meanwhile in the wireless unit, the downstream communication always far more than the upstream communication, moreover the expenses of the mobile client accepts data from the server also far to be smaller than the transmission expenses, even if under the separation condition, the mobile client also to be possible to selective receive the broadcast data which transmits from the server. Therefore, may use this kind of the asymmetry of the network, the data server organize the data which the mobile client interested, and sent to the mobile client by the periodic broadcast.
In the data broadcast, the visits probability of the data record is various, therefore the index tree may be built through visit probability. The structure of the index tree decides the average index number to be visited, but even regarding the same index structure, the average visit time is different if the broadcast sequence is different. If we want to design the most superior broadcast sequence for the existed index structure, we should consider not only the existed index point, but also the structure of the index tree. The mobile client may selectively to intercept the channel by the index broadcast, the average cost can be reduced through the establishment base on the data accessing probability of the index tree.
This dissertation according to the character of the different visit probability of the record in the data broadcast, through the research on index broadcast technology of the data broadcast, including the existed index tree base on the data accessing probability, and introduce the data broadcast algorithm with very low data average
引文
[1] 宁家骏等．畅游数据的海洋．中国计算机用户．2000，4：23-26页
[2] 石岩，张建军．数据库：风云爆发．中国计算机用户．1999，1：24-26页
[3] 何新贵，唐常杰，李霖，刘云生．特种数据库技术．科学出版社．2000
[4] 王珊，丁治明，张孝．移动数据库及其应用．计算机应用．2000，9：1-8页
[5] 胡虚怀．嵌入式移动数据库中数据广播技术的研究．岳阳职业技术学院学报．2004，3：90-93页
[6] Martin Breunig, Wolfgang Baer. Database support for mobile ronte planning systems. Computers, Environment and Urban Systems. 28 (2004): 595-610P
[7] Huseyin Gokmen Gok, Ozgur Ulusoy. Transmission of continuous query results in mobile computing systems. Information Sciences. 125 (2000): 37-63P
[8] Ming-Syan Chen, Kun-Lung Wu, Philip S. Yu. Optimizing Index Allocation for Sequential Data Broadcasting in Wireless Mobile Computing. IEEE Transactions on Knowledge and Data Engineering. 2003, 15(1): 161-173P
[9] Yon Dohn Chung, Myoung Ho Kim. Effective Data Placement for Wireless Broadcast. Distributed and Parallel Databases. 9, 2001 : 133-150P
[10] Sanjay Kumar Madria, Mukesh Mohania, Sourav S, Bhowmick, Bharat Bhargava. Mobile data and transaction management. Information Sciences. 141 (2002): 279-309P
[11] 魏峻，冯玉琳．移动计算形式理论分析与研究．计算机研究与发展．2002，2：23-29页
[12] 马卫东，李幼平．数据广播传输体系结构研究．计算机工程与应用．2001，24：53-58页
[13] 古志民，秦军．移动计算技术．信息技术．2001，20：14-17页
[14] Ammar M H, Wong J W. On the optimality of cyclic transmissions in teletext system. IEEE transaction on Communications. 1987, 35(1): 68-73P[15] 李建中，石胜飞．移动计算环境中的数据管理．计算机世界．2002，5：32-36页
[16] 肖迎元，刘云生，廖国琼．移动实时数据库系统综述．计算机工程与应用．2004，35：61-66页
[17] 陈嘉莉，王泽兵，孙建伶．移动计算中的数据广播技术．计算机科学．2002，29：49-51页
[18] S.Acharya, M.Franklin, S.Zdonik, R.Alonso. Broadcast disks: data management for asymmetric communications environments, in Proceedings of the ACM SIGMOD International Conference on Management of Data, San Jose, May 1995: 199-210P
[19] 丁治明，孟小峰，王珊．复制的移动数据库系统事务级同步处理策略．软件学报．2002，13(02)：12-18页
[20] 胡虚怀，李运兰．移动数据库及其三级复制体系结构的研究．岳阳职业技术学院学报．2003，12：77-79页
[21] Wen-Chih Peng, Ming-Syan Chen. Efficient Channel Allocation Tree Generation for Data Broadcasting in a Mobile Computing Environment. Wireless Networks. 9, 2003:117-129P
[22] Subhash Bhalla. Evolving a model of transaction management with embedded concurrency control for mobile database systems. Information and Software Technology. 45 (2003): 587-596P
[23] Guanling Lee, Shou-Chih Lo. Broadcast Data Allocation for Efficient Access of Multiple Data Items in Mobile Environments. Mobile Networks and Applications. 8, 2003: 365-375P
[24] 王彤，王良．嵌入式移动数据库的综述及评价．计算机工程．2001，12：155-157页
[25] 徐进辉，徐明．移动数据库事务处理模型研究．计算机工程与科学．2004，26：62-65页
[26] Dang Depeng, Liu Yunsheng. Concurrency control in real-time broadcast environments. The Journal of Systems and Software. 68 (2003): 137-144P
[27] C.-J. Su, L. Tassiulas. Broadcast scheduling for information distribution, in:??Proceedings of the 6th IEEE International Conference onInformation and Communication. (April 1997): 109-117P
[28] Lyrme Hall, Adrian Gordon, Lyrme Newall, Russell James. Adevelopment environment for intelligent applications on mobile devices. Expert Systems with Applications. 27(2004): 481-492P
[29] Sweta Pittie, Hillol Kargupta, Byung-Hoon Park. Dependency detection in MobiMine: a systemsperspective. Information Sciences. 155 (2003): 227-243P
[30] Siwoo Byun, Songchun Moon. Resilient data management for replicated mobile database systems. Data & Knowledge Engineering. 29 (1999): 43-55P
[31] John W. Wong, Broadcast Delivery. Proceedings of the IEEE, Volume: 76, Issue: 12, Dec. 1988: 1566-1577P
[32] 李霖，周光铭．非对称网络环境中数据广播的启发式多盘调度算法．计算 机学报．1999，22(1)：45-50页
[33] 邵雄凯，卢炎生．移动数据库中支持断连操作的一种新策略．小型微型计算机系统．2003，10：1776-1778页
[34] Budiarto, Shojiro Nishio, Masahiko Tsukamoto. Data management issues in mobile and peer-to-peer environments. Data & Knowledge Engineering. 41 (2002): 183-204P
[35] 杨晓宇，岳丽华，柳建平．多重查询优化技术在移动数据库中的应用．小型微型计算机系统．2004，8：1538-1541页
[36] Kam-Yiu Lam, Tei-Wei Kuo, Wai-Hung Tsang, Gary C.K Law. Concurrency Control In Mobile Distributed Real-Time Database Systems. Informcztion Systems. Vol.2.5,No.4, 2000: 261-286P
[37] Ye-In Chang, Che-Nan Yang. A complementary approach to data broadcasting in mobile information systems. Data & Knowledge Engineering. 40 (2002): 181-194p
[38] 林怀忠，陈纯，吴震华．数据复制与一致性．计算机工程与应用．2001，27：16-19页
[39] Antonio Si, Hung Va Leong. Query optimization for broadcast database. Data??& Knowledge Engineering. 29 (1999): 351-380P
[40] Yucel Saygin, Ozgur Ulusoy, Adnan Yazici. Dealing with fuzziness in active mobile database systems. Information Sciences. 120 (1999): 23-44P
[41] 林怀忠，陈纯．移动环境下事务一致性的动态实现．计算机研究与发展．2002，39(1)：23-26页
[42] Oleg Shigiltchoff, Panos K. Chrysanthis, Evaggelia Pitoura. Adaptive multiversion data broadcast organizations. Information Systems 29 (2005): 509-528P
[43] Ming-Syan Chen, Kun-Lung Wu, Philip S. Yu. Optimizing Index Allocation for Sequential Data Broadcasting in Wireless Mobile Computing. IEEE Transactions on Knowledge and Data Engineering. 2003, 15(1): 161-173P
[2] 石岩，张建军．数据库：风云爆发．中国计算机用户．1999，1：24-26页
[3] 何新贵，唐常杰，李霖，刘云生．特种数据库技术．科学出版社．2000
[4] 王珊，丁治明，张孝．移动数据库及其应用．计算机应用．2000，9：1-8页
[5] 胡虚怀．嵌入式移动数据库中数据广播技术的研究．岳阳职业技术学院学报．2004，3：90-93页
[6] Martin Breunig, Wolfgang Baer. Database support for mobile ronte planning systems. Computers, Environment and Urban Systems. 28 (2004): 595-610P
[7] Huseyin Gokmen Gok, Ozgur Ulusoy. Transmission of continuous query results in mobile computing systems. Information Sciences. 125 (2000): 37-63P
[8] Ming-Syan Chen, Kun-Lung Wu, Philip S. Yu. Optimizing Index Allocation for Sequential Data Broadcasting in Wireless Mobile Computing. IEEE Transactions on Knowledge and Data Engineering. 2003, 15(1): 161-173P
[9] Yon Dohn Chung, Myoung Ho Kim. Effective Data Placement for Wireless Broadcast. Distributed and Parallel Databases. 9, 2001 : 133-150P
[10] Sanjay Kumar Madria, Mukesh Mohania, Sourav S, Bhowmick, Bharat Bhargava. Mobile data and transaction management. Information Sciences. 141 (2002): 279-309P
[11] 魏峻，冯玉琳．移动计算形式理论分析与研究．计算机研究与发展．2002，2：23-29页
[12] 马卫东，李幼平．数据广播传输体系结构研究．计算机工程与应用．2001，24：53-58页
[13] 古志民，秦军．移动计算技术．信息技术．2001，20：14-17页
[14] Ammar M H, Wong J W. On the optimality of cyclic transmissions in teletext system. IEEE transaction on Communications. 1987, 35(1): 68-73P[15] 李建中，石胜飞．移动计算环境中的数据管理．计算机世界．2002，5：32-36页
[16] 肖迎元，刘云生，廖国琼．移动实时数据库系统综述．计算机工程与应用．2004，35：61-66页
[17] 陈嘉莉，王泽兵，孙建伶．移动计算中的数据广播技术．计算机科学．2002，29：49-51页
[18] S.Acharya, M.Franklin, S.Zdonik, R.Alonso. Broadcast disks: data management for asymmetric communications environments, in Proceedings of the ACM SIGMOD International Conference on Management of Data, San Jose, May 1995: 199-210P
[19] 丁治明，孟小峰，王珊．复制的移动数据库系统事务级同步处理策略．软件学报．2002，13(02)：12-18页
[20] 胡虚怀，李运兰．移动数据库及其三级复制体系结构的研究．岳阳职业技术学院学报．2003，12：77-79页
[21] Wen-Chih Peng, Ming-Syan Chen. Efficient Channel Allocation Tree Generation for Data Broadcasting in a Mobile Computing Environment. Wireless Networks. 9, 2003:117-129P
[22] Subhash Bhalla. Evolving a model of transaction management with embedded concurrency control for mobile database systems. Information and Software Technology. 45 (2003): 587-596P
[23] Guanling Lee, Shou-Chih Lo. Broadcast Data Allocation for Efficient Access of Multiple Data Items in Mobile Environments. Mobile Networks and Applications. 8, 2003: 365-375P
[24] 王彤，王良．嵌入式移动数据库的综述及评价．计算机工程．2001，12：155-157页
[25] 徐进辉，徐明．移动数据库事务处理模型研究．计算机工程与科学．2004，26：62-65页
[26] Dang Depeng, Liu Yunsheng. Concurrency control in real-time broadcast environments. The Journal of Systems and Software. 68 (2003): 137-144P
[27] C.-J. Su, L. Tassiulas. Broadcast scheduling for information distribution, in:??Proceedings of the 6th IEEE International Conference onInformation and Communication. (April 1997): 109-117P
[28] Lyrme Hall, Adrian Gordon, Lyrme Newall, Russell James. Adevelopment environment for intelligent applications on mobile devices. Expert Systems with Applications. 27(2004): 481-492P
[29] Sweta Pittie, Hillol Kargupta, Byung-Hoon Park. Dependency detection in MobiMine: a systemsperspective. Information Sciences. 155 (2003): 227-243P
[30] Siwoo Byun, Songchun Moon. Resilient data management for replicated mobile database systems. Data & Knowledge Engineering. 29 (1999): 43-55P
[31] John W. Wong, Broadcast Delivery. Proceedings of the IEEE, Volume: 76, Issue: 12, Dec. 1988: 1566-1577P
[32] 李霖，周光铭．非对称网络环境中数据广播的启发式多盘调度算法．计算 机学报．1999，22(1)：45-50页
[33] 邵雄凯，卢炎生．移动数据库中支持断连操作的一种新策略．小型微型计算机系统．2003，10：1776-1778页
[34] Budiarto, Shojiro Nishio, Masahiko Tsukamoto. Data management issues in mobile and peer-to-peer environments. Data & Knowledge Engineering. 41 (2002): 183-204P
[35] 杨晓宇，岳丽华，柳建平．多重查询优化技术在移动数据库中的应用．小型微型计算机系统．2004，8：1538-1541页
[36] Kam-Yiu Lam, Tei-Wei Kuo, Wai-Hung Tsang, Gary C.K Law. Concurrency Control In Mobile Distributed Real-Time Database Systems. Informcztion Systems. Vol.2.5,No.4, 2000: 261-286P
[37] Ye-In Chang, Che-Nan Yang. A complementary approach to data broadcasting in mobile information systems. Data & Knowledge Engineering. 40 (2002): 181-194p
[38] 林怀忠，陈纯，吴震华．数据复制与一致性．计算机工程与应用．2001，27：16-19页
[39] Antonio Si, Hung Va Leong. Query optimization for broadcast database. Data??& Knowledge Engineering. 29 (1999): 351-380P
[40] Yucel Saygin, Ozgur Ulusoy, Adnan Yazici. Dealing with fuzziness in active mobile database systems. Information Sciences. 120 (1999): 23-44P
[41] 林怀忠，陈纯．移动环境下事务一致性的动态实现．计算机研究与发展．2002，39(1)：23-26页
[42] Oleg Shigiltchoff, Panos K. Chrysanthis, Evaggelia Pitoura. Adaptive multiversion data broadcast organizations. Information Systems 29 (2005): 509-528P
[43] Ming-Syan Chen, Kun-Lung Wu, Philip S. Yu. Optimizing Index Allocation for Sequential Data Broadcasting in Wireless Mobile Computing. IEEE Transactions on Knowledge and Data Engineering. 2003, 15(1): 161-173P