Optimizing on-demand data broadcast scheduling in pervasive environments

ABSTRACT

Data dissemination in pervasive environments is often accomplished by on-demand broadcasting. The time critical nature of the data requests plays an important role in scheduling these broadcasts. Most research in on-demand broadcast scheduling has focused on the timely servicing of requests so as to minimize the number of missed deadlines. However, there exists many pervasive environments where the utility of the data is an equally important criterion as its timeliness. Missing the deadline reduces the utility of the data but does not make it zero. In this work, we address the problem of scheduling on-demand data broadcasts with soft deadlines. We investigate search based optimization techniques to develop broadcast schedulers that make explicit attempts to maximize the utility of data requests as well as service as many requests as possible within the acceptable time limit. Our analysis shows that heuristic driven methods for such problems can be improved by hybridizing them with local search algorithms. We further investigate the option of employing a dynamic optimization technique to facilitate utility gain, thereby surpassing the requirement of a heuristic in the process. An evolution strategy based stochastic hill climber is investigated in this context.

REFERENCES

• 1: Swarup Acharya , Rafael Alonso , Michael Franklin , Stanley Zdonik, Broadcast disks: data management for asymmetric communication environments, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.199-210, May 22-25, 1995, San Jose, California, United States
• 2: Swarup Acharya , S. Muthukrishnan, Scheduling on-demand broadcasts: new metrics and algorithms, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.43-54, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288248]
• 3: Demet Aksoy , Michael Franklin, R × W: a scheduling approach for large-scale on-demand data broadcast, IEEE/ACM Transactions on Networking (TON), v.7 n.6, p.846-860, Dec. 1999 [doi>10.1109/90.811450]
• 4: Beyer, H. An Alternative Explanation for the Manner in which Genetic Algorithms Opearate. BioSystems 41 (1997), 1--15.
• 5: Hans-Georg Beyer , Hans-Paul Schwefel, Evolution strategies –A comprehensive introduction, Natural Computing: an international journal, v.1 n.1, p.3-52, May 2002 [doi>10.1023/A:1015059928466]
• 6: Breslau, L., Cao, P., Fan, L., Phillips, G., and Shenker, S. Web Caching and Zipf-Like Distributions: Evidence and Implications. In Proceedings of the IEEE INFOCOM '99 (New York, NY, USA, 1999), pp. 126--134.
• 7: G. Buttazzo , M. Spuri , F. Sensini, Value vs. deadline scheduling in overload conditions, Proceedings of the 16th IEEE Real-Time Systems Symposium (RTSS '95), p.90, December 05-07, 1995
• 8: Cho, H., Wu, H., Ravindran, B., and Jensen, E. D. On Multiprocessor Utility Accrual Real-Time Scheduling With Statistical Timing Assurances. In Proceedings of the IFIP International Conference on Embedded and Real-Time Ubiquitous Computing (Seoul, Korea, 2006), pp. 274--286.
• 9: Adaptive dissemination of data in time-critical asymmetric communication environments, Mobile Networks and Applications, v.9 n.5, p.491-505, October 2004 [doi>10.1145/1027347.1027352]
• 10: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 11: Sohail Hameed , Nitin H. Vaidya, Efficient algorithms for scheduling data broadcast, Wireless Networks, v.5 n.3, p.183-193, May 1999 [doi>10.1023/A:1019194826654]
• 12: John H. Holland, Hidden order: how adaptation builds complexity, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1996
• 13: Jensen, E., Locke, C., and Tokuda, H. A Time Driven Scheduling Model for Real-Time Operating Systems. In Proceedings of the Sixth IEEE Real-Time Systems Symposium (San Diego, CA, USA, 1985), pp. 112--122.
• 14: Shu Jiang , Nitin H. Vaidya, Scheduling data broadcast to “impatient” users, Proceedings of the 1st ACM international workshop on Data engineering for wireless and mobile access, p.52-59, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313300.313385]
• 15: Jae-Hoon Kim , Kyung-Yong Chwa, Scheduling broadcasts with deadlines, Theoretical Computer Science, v.325 n.3, p.479-488, 6 October 2004 [doi>10.1016/j.tcs.2004.02.047]
• 16: Kam-Yiu Lam , Edward Chan , Joe Chun-Hung Yuen, Approaches for broadcasting temporal data in mobile computing systems, Journal of Systems and Software, v.51 n.3, p.175-189, May 2000 [doi>10.1016/S0164-1212(99)00122-3]
• 17: Ken C. K. Lee , Wang-Chien Lee , Sanjay Madria, Pervasive data access in wireless and mobile computing environments: Research Articles, Wireless Communications & Mobile Computing, v.8 n.1, p.25-44, January 2008 [doi>10.1002/wcm.v8:1]
• 18: Victor C. Lee , Xiao Wu , Joseph Kee-Yin Ng, Scheduling real-time requests in on-demand data broadcast environments, Real-Time Systems, v.34 n.2, p.83-99, October 2006 [doi>10.1007/s11241-006-7982-5]
• 19: Peng Li , Haisang Wu , Binoy Ravindran , E. Douglas Jensen, A Utility Accrual Scheduling Algorithm for Real-Time Activities with Mutual Exclusion Resource Constraints, IEEE Transactions on Computers, v.55 n.4, p.454-469, April 2006 [doi>10.1109/TC.2006.47]
• 20: Andrew J. Page , Thomas J. Naughton, Framework for Task Scheduling in Heterogeneous Distributed Computing Using Genetic Algorithms, Artificial Intelligence Review, v.24 n.3-4, p.415-429, November 2005 [doi>10.1007/s10462-005-9002-x]
• 21: Binoy Ravindran , E. Douglas Jensen , Peng Li, On Recent Advances in Time/Utility Function Real-Time Scheduling and Resource Management, Proceedings of the Eighth IEEE International Symposium on Object-Oriented Real-Time Distributed Computing, p.55-60, May 18-20, 2005 [doi>10.1109/ISORC.2005.39]
• 22: Rechenberg, I. Evolutionsstrategie: Optimierung technischer Systemenach Prinzipien der biologischen Evolution. PhD thesis, Technical University of Berlin, 1970.
• 23: Starkweather, T., McDaniel, S., Whitley, C., Mathias, K., and Whitley, D. A Comparison of Genetic Sequencing Operators. In Proceedings of the Fourth International Conference on Genetic Algorithms (San Diego, CA, USA, 1991), pp. 69--76.
• 24: Chi-Jiun Su , Leandros Tassiulas, Broadcast Scheduling for Information Distribution, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.109, April 09-11, 1997
• 25: Vengerov, D., Mastroleon, L., Murphy, D., and Bambos, N. Adaptive Data-Aware Utility-Based Scheduling in Resource-Constrained Systems. Tech. Rep. TR-2007-164, Sun Labs, 2007.
• 26: Wong, J. W. Broadcast Delivery. Proceedings of the IEEE 76, 12 (1988), 1566--1577.
• 27: Haisang Wu , Umut Balli , Binoy Ravindran , E. Douglas Jensen, Utility Accrual Real-Time Scheduling under Variable Cost Functions, Proceedings of the 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, p.213-219, August 17-19, 2005 [doi>10.1109/RTCSA.2005.102]
• 28: Xiao Wu , Victor C. S. Lee, Wireless real-time on-demand data broadcast scheduling with dual deadlines, Journal of Parallel and Distributed Computing, v.65 n.6, p.714-728, June 2005 [doi>10.1016/j.jpdc.2005.01.004]
• 29: Jianliang Xu , Xueyan Tang , Wang-Chien Lee, Time-Critical On-Demand Data Broadcast: Algorithms, Analysis, and Performance Evaluation, IEEE Transactions on Parallel and Distributed Systems, v.17 n.1, p.3-14, January 2006 [doi>10.1109/TPDS.2006.14]
• 30: Ping Xuan , Subhabrata Sen , Oscar Gonzalez , Jesus Fernandez , Krithi Ramamritham, Broadcast on Demand: Efficient and Timely Dissemination of Data in Mobile Environments, Proceedings of the 3rd IEEE Real-Time Technology and Applications Symposium (RTAS '97), p.38, June 09-11, 1997

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization