本論文的研究方向含蓋了兩個主題, 我們在第一主題裏討論了在sensor networks 中查詢處理及資料管理的議題. 而在第二個主題中, 我們則將焦點放在 mobile computing systems 上資料處理的議題上.
Sensor networks 在近年來成為非常熱門的研究焦點, 有許多的研究致力於 sensor network 上應用程式的發展, 這些應用程式包含了氣象偵測, 移動物體監控, 野生物追蹤, 地震感測, 及建築物結構完整性監控, 等等. 在這些應用中, 大量的 sensors 被佈置在所要監控的環境中, 這些 sensors 會收集所要監測環境的資料 (例如溫度, 濕度, 等等). 使用者可以透過某種方式將這些資料取回分析. 於是這引發了一個重要的議題, 那就是如何有效率地由 sensor network 中取得使用者想要的資料. 更精確地來說, 那就是使用者要如何由 sensor network 中 "查詢" 出他想要的資料. 在第一個主題中, 我們討論 sensor network 如何處理兩個十分重要, 也十分有用的查詢, 那就是 (1) multi-dimensional range queries 以及 (2) object tracking queries. 由於在 sensor network 中, 許多的事件都是由多個屬性所組成的, 因此很自然地使用者就會利用 multi-dimensional range queries 來取得他想要的資料. 我們提出了一個名為 Pool 的 framework, 其提供了處理 multi-dimensional range queries 的介面. Pool 可以有效率地將 multi-dimensional 的資料儲存在 sensor network 中, 並且在使用者下達查詢時, 也能快速地決定要去那些 sensor node 上取得符合 query 的資料. 而對於 object tracking query 而言, 在 sensor network 中追蹤移動地物體是一個很常見的應用. 然而, 目前存在的 solutions 多是基於物體的速度是固定的 (fixed velocity) 這樣的假設所設計的, 因此對於規則移動的物體 (例如野生動物), 這些方法便會面臨耗費大量 sensornet resource 的困境. 我們提出了 TbOT 方法來有效率地追蹤 moving object. TbOT 方法並不假設所有的物體為 fixed velocity 的. 在我們的實驗中証明了這個方法不但可以大量節省追蹤 object 的能源, 而且對於追蹤物體的準確度, 也能達到十分高的水準.

對於第二個研究主題, 我們將研究重心轉移到 mobile computing systems 上的資料處理的議題上. 在一個 mobile computing systems 中, 使用者可以利用其手持系統 (例如 notebook 或者是 PDA) 來取得他想要的資料. 例如使用者可能想要得到鄰近停車位的資訊, 天氣的狀況, 交通的流量, 股市的交易訊息, 等. 於是, "如何將使用者想要的資料快速且有效率地送達給使用者" 就成了一個 mobile computing systems 設計的重點. 在本論文中, 我們討論了 mobile computing systems 如何有效率地遞送俱備 "時間限制" 的資料給使用者的議題. 這個議題在過去 mobile computing systems 的研究中是十分少見的, 且並沒有完全地被解決. 在本論文的後半部, 我們提出了不同的資料排程演算法. 當 server 需要處理大量俱時間限制的 data requests 時, 這些演算法可以依照 request 的 deadline 來決定要遞送資料的先後順序. 這樣的排序方式可以讓 mobile computing system 儘可能地滿足絕大部分使用者的需求.

In this dissertation, we present our work in data management and query processing in sensor networks and mobile computing systems. The context of this dissertation is categorized into two parts. In this first part, we describe the techniques for query processing and data management in sensor networks. In the second part, we focus on the problem of efficient management and disseminating time-constrained data in mobile computing systems. Research in sensor networks has been targeted at numerous scientific applications, including micro-climate, vehicle tracking, habitat monitoring, earthquake and building health monitoring and others. In such applications, a large amount of sensors are deployed in an area of interest. These sensors then self-organize into a network and continuously collect environmental data (e.g., temperature, humidity, etc.). This entails the need for novel techniques to collect and query data from these networks.
We address this problem by providing solutions for efficiently processing queries and acquiring data in sensor networks. We primarily focus on two important and widely used queries, they are (1) the multi-dimensional range queries and (2) the object tracking queries. In many sensor networks, events or data are composed of several attributes. Thus, a natural way to query for events of interest is to use multi-dimensional range queries. In the dissertation, we present the design of Pool, an efficient and scalable scheme for supporting multi-dimensional range queries. Pool provides a highly efficient mechanism for collecting distributed multi-dimensional events in the sensors. Processing a multi-dimensional range query can therefore receive great benefit from the elegant storage structure of Pool. As for object tracking queries, tracking moving targets is one of the most important sensornet applications. However, existing solutions are designed based on the assumption that the velocity of the detecting object is fixed (i.e., an object will move with fixed speed in a fixed direction for a period of time). This introduces significant energy consumption while tracking irregular moving objects (e.g., wild animals).
We propose a Trigger-based Object Tracking (TbOT) scheme to minimize the consumed energy for the habitat monitoring applications. For increasing the accuracy and reducing the energy consumption, we explore the conditions under which TbOT is most desired. Our performance result reveals that TbOT provides dramatically high accuracy and meanwhile saves significant energy under various conditions.

In the second part of this dissertation, we focus our attention on the query processing and data management in mobile computing systems. In a mobile computing system, users are able to use their hand-held devices (e.g., PDAs or notebooks) to access information from anywhere at any time. Those information may include available parking spaces, weather, highway conditions, traffic directions, news and stock quotes. Thus, how a base station can disseminate information to mobile clients efficiently becomes an important design factor while building a mobile computing system. In the later portion of this dissertation, we focus on the design of a data dissemination system that considers timing constraints in mobile computing systems. This issue is not fully explored in the past. We propose several efficient scheduling algorithms which are designed for timely delivery of data to mobile clients. Our solutions can construct a broadcast program to satisfy as many clients' requirements within the expected times as possible.

[1] S. Madden, R. Szewczyk, M. J. Franklin, and D. Culler, “Supporting aggregate queries over ad-hoc wireless sensor networks,” in Proceedings of 4th IEEE Workshop on Mobile Computing and Systems Applications (WMCSA’02), pp. 49–58,
Callicoon, New York, USA, June 2002.
[2] A. Cerpa, J. Elson, D. Estrin, L. Girod, M. Hamilton, and J. Zhao, “Habitat monitoring: application driver for wireless communications technology,” SIGCOMM Comput. Commun. Rev., vol. 31, no. 2 supplement, pp. 20–41, 2001.
[3] A. Mainwaring, J. Polastre, R. Szewczyk, D. Culler, and J. Anderson, “Wireless sensor networks for habitat monitoring,” in Proceedings of the 1st ACM International
Workshop on Wireless Sensor Networks and Applications (WSNA’02), pp. 88–97, Atlanta GA, September 28 2002.
[4] J. Xu, X. Tang, and W.-C. Lee, “Prediction-based strategies for energy saving in object tracking sensor networks,” in Proceedings of the International Conference on
Mobile Data Management, pp. 346–357, Berkeley, California, USA, Jan. 2004.
[5] J. Gao and P. Steenkiste, “An adaptive protocol for efficient support of range queries in dht-based systems,” in ICNP ’04: Proceedings of the Network Protocols, 12th IEEE International Conference on (ICNP’04), pp. 239–250. Washington, DC, USA: IEEE Computer Society, 2004.
[6] X. Li, Y. J. Kim, R. Govindan, and W. Hong, “Multi-dimensional range queries in sensor networks,” in Proceedings of the 1st international conference on Embedded networked sensor systems, pp. 63–75, Los Angels, CA, November 2003.
[7] J. Xu, X. Tang, and W.-C. Lee, “Ease: an Eenergy-efficient in-network storage scheme for object tracking in sensor networks,” in Second Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks, pp. 396– 405, Sept. 2005.
[8] G. Bernard, J. Ben-othman, L. Bouganim, G. Canals, S. Chabridon, B. Defude, J. Ferrié, S. Gançarski, R. Guerraoui, P. Molli, P. Pucheral, C. Roncancio, P. Serrano-Alvarado, and P. Valduriez, “Mobile databases: a selection of open issues and research directions,” SIGMOD Rec., vol. 33, no. 2, pp. 78–83, 2004.
[9] P. Xuan, S. Sen, O. Gonzalez, J. Fernandez, and K. 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), pp. 38–48, Montreal, Canada, June 9-11 1997.
[10] A. Deshpande, S. Nath, P. B. Gibbons, and S. Seshan, “Cache-and-query for wide area sensor databases,” in SIGMOD ’03: Proceedings of the 2003 ACM SIGMOD international conference on Management of data, pp. 503–514, San Diego, California, 2003.
[11] S. Acharya, R. Alonso, M. Franklin, and S. Zdonik, “Broadcast disks: data management for asymmetric communication environments,” in Proceedings of ACM SIGMOD
International Conference on Management of Data (SIGMOD), pp. 199–210, San Jose, CA USA, May 22-25 1995.
[12] Y.-C. Chung, C.-C. Chen, and C. Lee, “Time-constrained service on air,” in Proceedings of the 25th IEEE International Conference on Distributed Computing Systems
(ICDCS’05), pp. 739–748, Columbus, Ohio, USA, 2005.
[13] Y.-C. Chung, C.-C. Chen, and C. Lee, “Design and performance evaluation of broadcast algorithms for time-constrained data retrieval,” IEEE Transactions on
Knowledge and Data Engineering, vol. 18, no. 11, pp. 1526–1543, 2006.
[14] J. Fernandez-Conde and K. Ramamritham, “Adaptive dissemination of data in time-critical asymmetric communication environments,” in Proceedings of the 11th
Euromicro Conference on Real-Time Systems(ECRTS99), York, England, June 9-11 1999.
[15] G. Lee and S.-C. Lo, “Broadcast data allocation for efficient access of multiple data items in mobile environments,” Mob. Netw. Appl., vol. 8, no. 4, pp. 365–375, 2003.
[16] C.-L. Hu and M.-S. Chen, “Adaptive balanced hybrid data delivery for multichannel data broadcast,” in Proceedings of the IEEE International Conference on Communications, 2002, pp. 960– 964, 2002.
[17] S. Acharya, M. Franklin, and S. Zdonik, “Dissemination-based data delivery using broadcast disks,” IEEE Personal Communications, vol. 2, no. 6, pp. 50–60,
December 1995.
[18] S. Acharya, M. Franklin, and S. Zdonik, “Prefetching from a broadcast disk,” in Proceedings of the 12th International Conference on Data Engineering, pp. 276–285,
New Orleans, Louisiana, February 26-March 1 1996.
[19] C.-C. Chen, L.-F. Lin, and C. Lee, “Benefit-oriented data retrieval in data broadcast environment,” in Proceedings of 9th International Conference on Database Systems for Advances Applications (DASFAA04), pp. 916–921, Jeju Island, Korea, March 17-19 2004.
[20] A. Datta, D. Vandermeer, A. Celik, and V. Kumar, “Broadcast protocols to support efficient retrieval from database by mobile users,” ACM Transactions on Database
Systems, vol. 1, no. 24, pp. 1–79, March 1999.
[21] Q. Hu, W.-C. Lee, and D. L. Lee, “A hybrid index technique for power efficient data broadcast,” Distributed and Parallel Database, vol. 9, no. 2, pp. 151–177,
March 2001.
[22] J.-H. Hwang, S. Cho, and C.-S. Hwang, “Optimized scheduling on broadcast disks,” in Proceedings of the Second International Conference on Mobile Data Management
(MDM01), pp. 91–104, Hong Kong, Chian, January 8-10 2001.
[23] K. Prabhakara, K. A. Hua, and J. 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), pp. 167–176, San Diego, CA, USA, February 28-March 3 2000.
[24] A. Deligiannakis, Y. Kotidis, and N. Roussopoulos, “Hierarchical in-network data aggregation with quality guarantees,” in Proceedings of EDBT, pp. 658–675.
Springer, March 2004.
[25] C.-L. Hu and M.-S. Chen, “Dynamic data broadcasting with traffic awareness,” in Proceeding of the 22nd International Conference on Distributed Computing Systems
(ICDCS’02), pp. 112–119, Vienna, Austria, July 2-5 2002.
[26] S. Jiang and N. H. Vaidya, “Scheduling data broadcast to “impatien” users,” in Proceedings of the ACM international workshop on Data engineering for wireless
and mobile access, pp. 52–59, Seattle, WA USA, August 20 1999.
[27] S. Ratnasamy, B. Karp, S. Shenker, D. Estrin, R. Govindan, L. Yin, and F. Yu, “Data-centric storage in sensornets with ght, a geographic hash table,” Mobile
Networks and Applications, vol. 8, no. 4, pp. 427–442, August 2003.
[28] P. Bonnet, J. Gehrke, and P. Seshadri, “Towards sensor database systems,” in Proceedings of the second international conference on Mobile Data Management,
January 2001.
[29] H. Garcia-Molina, J. D. Ullman, and J. D. Widom, Database Systems: The Complete Book. Prentice Hall, 2001, ch. 13, p. 638.
[30] G. R. Hjaltason and H. Samet, “Index-driven similarity search in metric spaces,”ACM Trans. Database Syst., vol. 28, no. 4, pp. 517–580, 2003.
[31] G. S. Iwerks, H. Samet, and K. P. Smith, “Maintenance of k-nn and spatial join queries on continuously moving points,” ACM Trans. Database Syst., vol. 31, no. 2,
pp. 485–536, 2006.
[32] C. Intanagonwiwat, R. Govindan, and D. Estrin, “Directed diffusion: a scalable and robust communication paradigm for sensor networks,” in MobiCom ’00: Proceedings
of the 6th annual international conference on Mobile computing and networking, pp. 56–67. Boston, Massachusetts, United States: ACM Press, 2000.
[33] S. Madden, M. J. Franklin, J. M. Hellerstein, and W. Hong, “TAG: a Tiny AGgregation service for ad-hoc sensor networks,” SIGOPS Oper. Syst. Rev., vol. 36, no. SI, pp. 131–146, 2002.
[34] B. Greenstein, D. Estrin, R. Govindan, S. Ratnasamy, and S. Shenker, “DIFS: a distributed index for features in sensor networks,” in Proceedings of the First IEEE International Workshop on Sensor Network Protocols and Applications, pp. 163–173, May 11 2003.
[35] G. He, R. Zheng, I. Gupta, and L. Sha, “A framework for time indexing in sensor networks,” ACM Transactions on Sensor Networks, vol. 1, no. 1, pp. 101–133, 2005.
[36] A. Meka and A. Singh, “Dist: a distributed spatio-temporal index structure for sensor networks,” in CIKM ’05: Proceedings of the 14th ACM international conference on Information and knowledge management, pp. 139–146. Bremen, Germany: ACM Press, 2005.
[37] Crossbow, “Mep-sys datasheet,” Website, http://www.xbow.com/Products/
Product_pdf_files/Wireless_pdf/MEP-SYS_Datasheet.pdf.
[38] J. L. Bentley, “Multidimensional binary search trees used for associative searching,” Communication of the ACM, vol. 18, no. 9, pp. 509–517, 1975.
[39] N. Bulusu, J. Heidemann, and D. Estrin, “Gps-less low cost outdoor localization for very small devices,” IEEE Personal Communications Magazine, vol. 7, no. 5, pp. 28–34, Oct. 2000.
[40] L. Girod and D. Estrin, “Robust range estimation using acoustic and multi modal sensing,” in Proceedings of the 2001 IEEE/RSJ International Conference on Intelligent
Robots and Systems, pp. 1312–1320, Maui, Hawaii, October 2001.
[41] B. Karp and H. T. Kung, “Gpsr: Greedy perimeter stateless routing for wireless networks,” in Proceedings of the Sixth Annual ACM/IEEE International Conference
on Mobile Computing and Networking (Mobicom 2000), Boston, Massachusetts, August 2000.
[42] I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan, “Chord: A scalable peer-to-peer lookup service for internet applications,” in Proceedings of the
ACM SIGCOMM’ 01 Conference, San Diego, California, August 2001.
[43] A. Ghose, J. Grossklags, and J. Chuang, “Resilient data-centric storage in wireless ad-hoc sensor networks,” in Proceedings of the 4th International Conference on Mobile Data Management MDM 2003, pp. 45–62, 2003.
[44] lan F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “A survey on sensor networks,” IEEE Communications Magazine, vol. 40, no. 8, pp. 102–114, August 2002.
[45] J. M. Hellerstein, W. Hong, and S. R. Madden, “The sensor spectrum: Technology, trends, and requirements,” ACM SIGMOD Record, vol. 32, no. 4, pp. 22–27, December 2003.
[46] S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M. B. Srivastava, “Coverage problems in wireless ad-hoc sensor networks,” in Proceedings of The 20th Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom’02), pp. 1380–1387, Anchorage, Alaska, USA, April 22-26 2001.
[47] C.-F. Huang and Y.-C. Tseng, “The coverage problem in a wireless sensor network,”in Proceedings of the 2nd ACM International Workshop on Wireless Sensor Networks and Applications (WSNA’03), pp. 115–121, San Diego, California, USA, September 19 2003.
[48] K. Chakrabarty, S. S. Iyengar, H. Qi, and E. Cho, “Grid coverage for surveillance and target location in distributed sensor networks,” IEEE Transactions on Computers, vol. 51, no. 12, pp. 1448–1453, 2002.
[49] A. Howard, M. J. Mataric, and G. S. Sukhatme, “An incremental self-deployment algorithm for mobile sensor networks,” Autonomous Robots, Special Issue on Intelligent
Embedded Systems, vol. 13, no. 2, pp. 113–126, 2002.
[50] T. Clouqueur, V. Phipatanasuphorn, P. Ramanathan, and K. K. Saluja, “Sensor deployment strategy for detection of targets traversing a region,” Mobile Networks and Applications (MONET), vol. 8, no. 4, pp. 453–461, 2003.
[51] G. Wang, G. Cao, and T. L. Porta, “Movement-assisted sensor deployment,” in Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom’04), Hong Kong, China, March 7-11 2004.
[52] D. Ganesan, D. Estrin, and J. Heidemann, “Dimensions: Why do we need a new data handling architecture for sensor networks?” in Proceedings of the ACM Workshop on Hot Topics in Networks, pp. 143–148, Princeton, NJ, USA, October 2002.
[53] C. Intanagonwiwat, D. Estrin, R. Govindan, and J. Heidemann, “Impact of network density on data aggregation in wireless sensor networks,” in Proceedings of the 22nd
International Conference on Distributed Computing Systems, Vienna, Austria, July 2002.
[54] Y. Yao and J. Gehrke, “The cougar approach to in-network query processing in sensor networks,” ACM SIGMOD Record, vol. 31, no. 3, pp. 9–18, 2002.
[55] S. Madden, M. J. Franklin, J. M. Hellerstein, and W. Hong, “The design of an acquisitional query processor for sensor networks,” in Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, pp. 491–502. San Diego, California, USA: ACM Press, June 9-12 2003.
[56] S. R. Madden, “The design and evaluation of a query processing architecture for sensor networks,” Ph.D. dissertation, University of California, Berkeley, Fall 2003.
[57] A. Ailamaki, C. Faloutsos, P. S. Fischbeck, M. J. Small, and J. VanBriesen, “An environmental sensor network to determine drinking water quality and security,” ACM SIGMOD Record, vol. 32, no. 4, pp. 47–52, December 2003.
[58] L. Clare, G. Pottie, and J. Agre, “Self-organizing distributed sensor networks,” in The International Society for Optical Engineering, pp. 229–237, Orlando, Florida,
USA, April 1999.
[59] J. Hill, R. Szewczyk, A. Woo, S. Hollar, D. Culler, and K. Pister, “System architecture directions for network sensors,” ACM SIGOPS Operating Systems Review, vol. 34, pp. 93–104, 2000.
[60] K. Sohrabi and G. J. Pottie, “Performance of a novel self-organization protocol for wireless ad-hoc sensor netoworks,” in Proceedings of the IEEE Vehicular Technology
Conference (VTC’99), pp. 1222–1226, Amsterdam, the Netherlands, September 19-22 1999.
[61] H. Yang and B. Sikdar, “A protocol for tracking mobile targets using sensor networks,” in Proceedings of First IEEE International Workshop on Sensor Network Protocols and Applications (SNPA’03), pp. 71– 81, Anchorage, Alaska, USA, May 11 2003.
[62] Y. Xu, J. Winter, and W.-C. Lee, “Prediction-based strategies for energy saving in object tracking sensor networks,” in Proceedings of the International Conference
on Mobile Data Management (MDM’04), pp. 346–357, Berkeley, California, USA, January 2004.
[63] A. P. Sistla, O. Wolfson, S. Chamberlain, and S. Dao, “Modeling and querying moving objects,” in Proceedings of the Thirteenth International Conference on Data Engineering (ICDE’97), pp. 422–432, Birmingham U.K, April 7-11 1997.
[64] S. Madden and M. J. Franklin, “Fjording the stream: An architecture for queries over streaming sensor data,” in Proceedings of the 18th International Conference on Data Engineering (ICDE’02), pp. 555–566, San Jose, California, USA, 2002.
[65] J. Gehrke, F. Korn, and D. Srivastava, “On computing correlated aggregates over continual data streams,” in Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 13–24, Santa Barbara, California, USA, May 21-24 2001.
[66] M. R. Henzinger, P. Raghavan, and S. Rajagopalan, “Computing on data stream,” DEC System Research Center, Tech. Rep. 1998-011, May 1998.
[67] J. M. Hellerstein, W. Hong, S. Madden, and K. Stanek, “Beyond average: Towards sophisticated sensing with queries,” in Proceedings of the Second International Workshop on Information Processing in Sensor Networks (IPSN’03), F. Zhao and L. J. Guibas, Eds., pp. 63–79. Palo Alto, California, USA: Springer, April 22-23 2003.
[68] H. Samet, The Design and Analysis of Spatial Data Structures. Addison-Wesley, 1990.
[69] H. Samet, Application of Spatial Data Structurea. Addison-Wesley, 1990.
[70] A. Y. Seydim and M. H. Dunham, “A location dependent benchmark with mobility behavior,” in International Database Engineering and Applications Symposium (IDEAS’02), pp. 74–83, Edmonton, Canada, July 17-19 2002.
[71] G. T. Sibley, M. H. Rahimi, and G. S. Sukhatme, “Robomote: A tiny mobile robot platform for large-scale sensor networks,” in Proceedings of the IEEE International
Conference on Robotics and Automation (ICRA’02), pp. 143–1148, Crystal Gateway Marriott Hotel, Washington D.C., USA, May 11-15 2002.
[72] S. 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), pp. 43–54, Dallas,
Texas, USA, October 25-30 1998.
73] D. Aksoy and M. Franklin, “R×w: a scheduling approach for large-scale on-demand data broadcast,” pp. 846–860, December 1999.
[74] J. Cai and K.-L. Tan, “Tuning integrated dissemination-based information systems,”Data & Knowledge Engineering, vol. 3, no. 1, pp. 1–21, May 1999.
[75] T. Imielinski and S. Viswanathan, “Adaptive wireless information systems,” in Proceedings of the ACM Special Interest Group on DataBase Systems, pp. 19–41, 1994.
[76] W.-C. L. Quinlong Hu, Dik Lun Lee,“Dynamic data delivery in wireless communication environments,” in Proceedings of ER’98 Workshops on Mobile Data Access,
volume 1552 of Lecture Nodes in Computer Science, pp.218–229, 1998.
[77] 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, pp. 326–335, August 1997.
[78] S. Baruah and A. Bestavros, “Pinwheel scheduling for fault-tolerant broadcast disks in real-time database systems,” in Proceedings of 13th ICDE, pp. 543–551, Birmingham, U.K., April 7-11 1997.
[79] S. Baruah and A. Bestavros, “Real-time mutable broadcast disks,” in Proceedings of the Second International Workshop on Real-Time Databases(RTDB97), pp. 3–22, Burlington, VT, September 18-19 1997.
[80] A. Bar-Noy, J. Naor, and B. Schieber, “Pushing dependent data in clients-provide servers
systems,” in Proceedings of the Sixth Annual International Conference on Mobile Computing and Networking (MOBICOM2000), pp. 222–230, Boston MA USA, August 6-11 2000.
[81] E. Yajima, T. Hara, M. Tsukamoto, and S. Nishio, “Scheduling and caching strategies for broadcasting correlated data,” in Proceedings of the 2001 ACM symposium
on Applied computing, pp. 504–510, Las Vegas, Nevada, United States, March 11-14 2001.
[82] S. Hameed and N. H. Vaidya, “Efficient algorithms for scheduling data broadcast,” ACM Wireless Networks, vol. 5, pp. 183–193, 1999.
[83] S.-C. Lo and A. L. Chen, “Optimal index and data allocation in multiple broadcast channels,” in Proceedings of 16th International Conference on Data Engineering
(ICDE 2000), pp. 293–302, San Diego, CA, USA, February 28-March 3 2000.
[84] N. H. Vaidya and S. Hameed, “Data broadcast in asymmetric wireless environments,” in First International Workshop on Satellite-based Information Services
(WOSBIS), Rye, NY, November 1996.
[85] K. yiu Lam, E. Chan, and C.-H. 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, pp. 11–19, Santa Clara, California, April 8-9 1999.
[86] C.-L. Hu and M.-S. Chen, “Adaptive multichannel data dissemination: support of dynamic traffic awareness and push-pull time balance,” IEEE Transactions on
Vehicular Technology, vol. 54, no. 2, pp. 673 – 686, 2005.
[87] N. Vlajic, C. D. Charalambous, and D. Makrakis, “Performance aspects of data broadcast in wireless networks with user retrials,” IEEE/ACM Transactions on Networking, vol. 12, no. 4, pp. 620–633, August 2004.
[88] W. G. Yee, S. B. Navathe, E. Omiecinski, and C. Jermaine, “Efficient data allocation over multiple channels at broadcast servers,” IEEE Transactions on Computers,
vol. 51, no. 10, pp. 1231 – 1236, October 2002.
[89] T. Imielinski, S. Viswanathan, and B. Badrinath, “Data on air: Organization and access,” IEEE Transactions on Knowledge and Data Engineering, vol. 9, no. 3, pp.
353–372, May/June 1997.
[90] “Time-critical on-demand data broadcast: Algorithms, analysis, and performance evaluation,” IEEE Trans. Parallel Distrib. Syst., vol. 17, no. 1, pp. 3–14, 2006, jianliang Xu and Xueyan Tang and Wang-Chien Lee.
[91] M. Y. Chan and F. Y. L. Chin, “General schedulers for the pinwheel problem based on double-integer reduction,” IEEE Transactions on Computers, vol. 41, no. 6, pp.
755–768, June 1992.
[92] C. Kenyon and N. Schabanel, “The data broadcast problem with non-uniform transmission times,” in Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, pp. 547 – 556, Baltimore, Maryland, United States, 1999.
[93] B. Zheng, X.Wu, X. Jin, and D. L. Lee, “Tosa: a near-optimal scheduling algorithm for multi-channel data broadcast,” in MDM ’05: Proceedings of the 6th nternational
conference on Mobile data management, pp. 29–37. New York, NY, USA: ACM Press, 2005.
[94] E. Ardizzoni, A. A. Bertossi, S. Ramaprasad, R. Rizzi, and M. V. S. Shashanka, “Optimal skewed data allocation on multiple channels with flat broadcast per channel,”IEEE Trans. Comput., vol. 54, no. 5, pp. 558–572, 2005.
[95] W.-C. Lee, Q. Hu, and D. L. Lee, “A study on channel allocation for data dissemination in mobile computing environments,” Mobile Networks and Applications (MONET), vol. 4, no. 2, pp. 117–129, 1999.
[96] D. A. Tran, K. A. Hua, and N. Jiang, “A generalized air-cache design for efficiently broadcasting on multiple physical channels,” in SAC ’01: Proceedings of the 2001
ACM symposium on Applied computing, pp. 387–392. Las Vegas, Nevada, United States: ACM Press, 2001.
[97] N. H. Vaidya and S. Hameed, “Scheduling data broadcast in asymmetric communication environments,” Wirel. Netw., vol. 5, no. 3, pp. 171–182, 1999.
[98] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. New York, NY, USA: W. H. Freeman & Co., 1979.