在無線網路環境下，頻寬和客戶資源受到限制，資料廣播可有效率的將資訊傳送給大量的行動客戶。近年來，有許多關於在多頻道上排程的研究，但大多都只考慮無序需求。在本篇論文中，我們研究多頻道上有序需求的排班配置問題，排程規劃須考慮每筆需求之資料順序。依據不同的應用環境，我們提出一個有效的排程演算法，可即時安排客戶需求。實驗結果顯示在需求機率分佈已知的情況下，可大幅加快排程時間並提供更好的排程結果，而在需求機率分佈未知時亦可縮短平均存取時間。

In wireless mobile environments, the bandwidth and client capability are limited. Data broadcasting is an efficient and scalable method to disseminate information to a large number of mobile clients. In recent years, many applications are closely related to scheduling dependent data on multiple broadcast channels. However, most of the prior researches only focus on unordered queries. In this thesis, we study the problem of data allocation for ordered queries on multiple broadcast channels. We propose an efficient algorithm based on a local search strategy. The experiment results show that our algorithm outperforms the other popular algorithms when the query distribution is known. Meanwhile, our algorithm reduces average access time when the query distribution is unknown.

[1] S. Acharya, R. Alonso, M. Franklin and S. Zdonik, “Broadcast disks: Data management for asymmetric communication environments,” Proceedings of the ACM SIGMOD Conference, 1995, pp. 199-210.
[2] S. Acharya, M. Franklin and S. Zdonik, “Disseminating updates on broadcast disks,” Proceedings of the 22th International Conference on Very Large Data Bases, 1996, pp. 354-365.
[3] S. Acharya, M. Franklin and S. Zdonik, “Balancing push and pull for data broadcast,” Proceedings of the 1997 ACM SIGMOD international conference on Management of data, vol. 26, no. 2, 1997, pp. 183-194.
[4] E. Ardizzoni, A.A. Bertossi, M.C. Pinotti, S. Ramaprasad, R. Rizzi and M.V.S. Shashanka, “Optimal skewed data allocation on multiple channels with flat broadcast per channel,” IEEE Transactions on Computers, vol. 54, no. 5, 2005, pp. 558-572.
[5] A. Bar-Noy, J. Naor and B. Schieber, “Pushing dependent data in clients-providers-servers systems,” Proceedings of the 6th annual international conference on Mobile computing and networking, 2000.
[6] A. Bar-Noy, J.S. Naor and B. Schieber, “Pushing dependent data in clients-providers-servers systems,” Wireless Networks, vol. 9, no. 5, 2003, pp. 421-430.
[7] Y.C. Chehadeh, A.R. Hurson and M. Kavehrad, “Object organization on a single broadcast channel in the mobile computing environment,” Multimedia Tools and Applications, vol. 9, no. 1, 1999, pp. 69-94.
[8] Y.D. Chung and M.H. Kim, “QEM: A scheduling method for wireless broadcast data,” Proceedings of the Sixth International Conference on Database Systems for Advanced Applications, 1999, pp. 135-142.
[9] Y.D. Chung and M.H. Kim, “Effective data placement for wireless broadcast,” Distributed and Parallel Databases, vol. 9, no. 2, 2001, pp. 133-150.
[10] S.M.S. Google, “ Google Short Message Service(SMS),” 2005; http://www.google.com/sms/.
[11] J.L. Huang and M.S. Chen, “Dependent data broadcasting for unordered queries in a multiple channel mobile environment,” IEEE Transactions on Knowledge and Data Engineering, vol. 16, no. 9, 2004, pp. 1143-1156.
[12] J.L. Huang, M.S. Chen and W.C. Peng, “Broadcasting dependent data for ordered queries without replication in a multi-channel mobile environment,” Proceedings - International Conference on Data Engineering, 2003, pp. 692-694.
[13] H.P. Hung and M.S. Chen, “MULS: A general framework of providing multilevel service quality in sequential data broadcasting,” IEEE Transactions on Knowledge and Data Engineering, vol. 19, no. 10, 2007, pp. 1433-1447.
[14] H.P. Hung, J.W. Huang, J.L. Huang and M.S. Chen, “Scheduling dependent items in data broadcasting environments,” Proceedings of the 2006 ACM symposium on Applied computing, 2006.
[15] T. Imielinski, S. Viswanathan and B.R. Badrinath, “Data on air: Organization and access,” IEEE Transactions on Knowledge and Data Engineering, vol. 9, no. 3, 1997, pp. 353-372.
[16] G. Lee and S.C. Lo, “Broadcast data allocation for efficient access of multiple data items in mobile environments,” Mobile Networks and Applications, vol. 8, no. 4, 2003, pp. 365-375.
[17] G. Lee, S.C. Lo and A.L.P. Chen, “Data allocation on wireless broadcast channels for efficient query processing,” IEEE Transactions on Computers, vol. 51, no. 10, 2002, pp. 1237-1252.
[18] K.C.K. Lee, W.C. Lee and S. Madria, “Pervasive data access in wireless and mobile computing environments,” Wireless Communications and Mobile Computing, vol. 8, no. 1, 2008, pp. 25-44.
[19] H.V. Leong and A. Si, “Data broadcasting strategies over multiple unreliable wireless channels,” International Conference on Information and Knowledge Management, Proceedings, 1995, pp. 96-104.
[20] K.F. Lin and C.M. Liu, “Broadcasting dependent data with minimized access latency in a multi-channel environment,” IWCMC 2006 - Proceedings of the 2006 International Wireless Communications and Mobile Computing Conference, pp. 809-814.
[21] K.F. Lin and C.M. Liu, “Schedules with minimized access latency for disseminating dependent information on multiple channels,” Proceedings -2006 IEEE International Conference on Sensor Networks, Ubiquitous, and Trustworthy Computing, pp. 344-351.
[22] C.M. Liu and K.F. Lin, “Efficient scheduling algorithms for disseminating dependent data in wireless mobile environments,” Proceedings - 2005 IEEE International Conference on Wireless Networks, Communications and Mobile Computing,, 2005.
[23] S.C. Lo and A.L.P. Chen, “Optimal index and data allocation in multiple broadcast channels,” Proc. 16th IEEE Int'l Conf. Data Eng., 2000, pp. 293-302.
[24] S.P.O.T. Microsoft, “Microsoft DirectBand Network,” 2006; http://www.msndirect.com/.
[25] V. Padmanabhan and L. Qiu, “The content and access dynamics of a busy web site: findings and implications,” Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, 2000.
[26] W.C. Peng and M.S. Chen, “Efficient channel allocation tree generation for data broadcasting in a mobile computing environment,” Wireless Networks, vol. 9, no. 2, 2003, pp. 117-129.
[27] K. Prabhakara, K.A. Hua and J. Oh, “Multi-level multi-channel air cache designs for broadcasting in a mobile environment,” Proceedings - International Conference on Data Engineering, 2000, pp. 167-176.
[28] A. Si and H. Va Leong, “Query optimization for broadcast database,” Data and Knowledge Engineering, vol. 29, no. 3, 1999, pp. 351-380.
[29] K. Stathatos, N. Roussopoulos and J.S. Baras, “Adaptive data broadcast in hybrid networks,” Proceedings of the 23rd International Conference on Very Large Data Bases, 1997, pp. 326-335.
[30] G.K. Zipf, Human Behavior and the Principle of Least Effort: An Introduction to Human ecology., Addison-Wesley Press, Cambridge, MA., 1949.
[31] 曾煜棋、潘孟鉉、林致宇, 無線區域及個人網路：隨意及感測器網路之技術與應用, 2007.