傳統上,在無線網路的環境中,資料配置的目的是為了降低mobile user (MU) 對cell server抓取資料的時間。
在本篇論文中,我們以service advertisement的觀點來探討資料的配置與播放。針對service provider所提供的location-based service (LBS), 像是加油站與汽車旅館業, service provider在特定cell (service cell)內提供此LBS。這些LBS也許不為MUs知道, service provider透過資料的配置與播放,將這些LBS資訊傳達給MUs,藉以吸引MUs去接受這些LBS。

由於LBS與MU的位置有關,我們分析MUs的移動行為,
找出為hot spot的cells作。
我們發展出一套evaluation model,藉由分析MUs的移動行為, 具體地描述MUs在收到LBS資訊之後去使用LBS的群體意願。透過evaluation model, service provider可以知道選擇哪些cells作為資料的配置與播放,
方能吸引最多的MUs去使用LBS。

限於無線頻寬或者service provider的成本考量,可供作為資料的配置與播放的cell數目是有限制的。
在眾多的cells之中挑選最佳的cells,組合情形隨著所限制挑選的cell數目呈現指數成長。
我們發展出branchAndBound演算法,從眾多的組合解中,在可接受的時間下,找出最佳的組合解。

In mobile environment, traditionally the purpose of data allocation is to decrease the data transfer cost from cell servers to MUs. In the paper, we discuss about data allocation and dissemination in view of service
advertisement. For any location-based service (LBS) provided by service providers, like gas station or motel, service providers provide such LBS in particular cell (service cell). The LBS may not be known beforehand by MUs, but service providers can convey the LBS information to MUs by
data allocation and dissemination, to attract these MUs to use the LBS.

Because LBSs are related with the locations of MUs, we analyze the moving behavior of MUs and try to find out the hot-spot cells for data
allocation and dissemination. We develop an evaluation model by analysis of moving behavior of MUs, which can concretely describe the MU
group will to use the LBSs after they have received the LBS information. According to the evaluation model, service providers know how to choose which cells for data allocation and dissemination to attract the most MUs
to use the LBSs.

Constrained by wireless bandwidth or the capital of service provider, the number of cells for data allocation and dissemination must be constrained.
The number of combinations grows exponentially with the constrained number of cells when trying to choose from many ones. To solve this problem, we develop a branchAndBound algorithm, which can ?ndthe optimal solution from so many combinations in accepted period of time.

Bibliography

[3GPP] http://www.3gpp.org/, 2002

[AAFZ95] Swarup Acharya, Rafael Alonso, Michael Franklin, and Stanley
Zdonik, “Broadcast Disks: Data Management for Asymmetric
Communication Environments,” in Proceedings of the ACM SIGMOD
Conference on Management of Data, San Jose, CA, May 1995, pp 199-210.

[AAJM02] Joanthan Agre, Adedji Akinyemi, Lusheng Ji, Ryusuke Masuoka
and Pankaj Thakkar, “A Layered Architecture for Locationbased
Services inWireless Ad Hoc Networks,” in Proceedings of IEEE
Aerospace Conference, 2002, Vol, 3, pp 3.1085-3.1097.

[AB96] Azer Bestavros, “AIDA-based real-time fault-tolerant broadcast
disks,” in Procedings of the 16th IEEE Real-Time Technology and
Applications Symposium, Boston, Massachusetts, May 1996.

[AFZ96] Swarup Acharya, Michael Franklin,and Stanley Zdonik,
“Prefetching from a Broadcast Disk,” in Proceedings of the 12th International
Conference on Data Engineering, New Orleans, LA, USA,
February 1996, pp 276-285.

[AFZ97b] Swarup Acharya, Michael Franklin, and Stanley Zdonik, “Disseminating
Updates on Broadcast Disks,” in Proceedings of the 22th
50International Conference on Very Large Data Bases, Bombay, India,
September 1997, pp 354-365

[AS94] Rakesh Agrawal and Ramakrishnan Srikant, “Fast Algorithms for
Mining Association Rules,” in Proceedings of the 20th International
Conference on Very Large Databases, Santiago, Chile, September 1994,
pp 487-499.

[AS96] Rakesh Agrawal and Ramakrishnan Srikant, “Mining Quantitative
Association Rules in Large Relational Tables,” in Proceedings
of the ACM SIGMOD International Conference on Management of
Data, Montreal Canada, June 1996, pp 1-12.

[BB97a] Sanjoy Baruah, and Azer Bestavros, “Pinwheel Scheduling for
Fault-Tolerant Broadcast Disks in Real-Time Database Systems,” in
Proceedings of 13th IEEE International Conference on Data Engineering,
Birmingham, England, April 1997, pp 543-551.

[BG94] Daniel Barbara and Hector Garcia-Molina, “Replicated Data
Management in Mobile Environments: Anything New Under the
Sun?” in Proceedings of IFIP Conference on Applications in Parallel
and Distributed Computing, April 1994, Vol. A-44, pp 237-246.

[BI92] B.R.Badrinath and T. Imielinski, “Replication and Mobility,” in
Proceedings of the 2nd IEEE Workshop on the Management of Replicated
Data, Monterey, California, November 1992, pp 9-12.

[BI94] Daniel Barbara and Tomasz Imielinski, “Sleepers andWorkaholics:
Caching Strategies in Mobile Environments,” in Proceedings of ACM
SIGMOD International Conference on Management of Data, May 1994, pp 1-12.

[CRYL03] Ying Chen, Fangyan Rao, Xiulan Yu, and Dong Liu,
“CAMEL: A Moving Object Database Approach for Intelligent Location
Aware Services,” in Proceedings of the 4th IEEE International
Conference on Mobile Data Management, Melbourne, Australia, January 2003,
pp. 331-334

[CYW97] Ming-Syan Chen, Philip S. Yu, and Kun-Lung Wu, “Indexed
Sequential Data Broadcasting in Wireless Mobile Computing,” in
Proceedings of the 17th IEEE International Conference on Distributed
Computing Systems, May 1997, pp 124-131.

[DF83] LawrenceW. Dowdy and Derrell V. Foster, “ComparativeModels
of the File Assignment Problem,” ACM Computing Surveys, June
1982, Vol. 14, No. 2, pp 287-313.

[HB01] Je?rey Hightower and Gaetano Borriello, “Location Systems for
Ubiquitous Computing,” in IEEE Computer, August 2001, Vol.34,
No.8, pp 57-66.

[HLC97] Bernhard Hofmann-Wellenhof, Herbert Lichtenegger, and
James Collins, “Global Positioning System: Theory and Practice,”
fourth edition, SpringerVerlag Wien, New York, NY, 1997.

[HR95] Long-Rong Hu and Stephen S. Rappaport, “Personal Communication
Systems Using Multiple Hierarchical Cellular Overlays,” IEEE
Journal on Selected Areas in Communications, 1995, Vol. 13 No. 2, pp 406-415.

[HSW94] Yixiu Hang, Prasad Sistla, and Ouri Wolfson, “Data Replication
for Mobile Computer,” in Proceedings of ACM SIGMOD International Conference on Management of Data, Minneapolis, Minnesota, May 1994, pp 13-24.

[HW93] Yixiu Huang and Ouri Wolfson, “A Competitive Dynamic Data
Replication Algorithm,” in Proceedings of the 9th IEEE International
Conference on Data Engineering, Vienna, Austria, April 1993, pp
310-337.

[JFPP01] Christian S. Jensen, Anders Friis-Christensen, Torben B.
Pedersen, Dieter Pfoser, Simonas Saltenis, and Nectaria Tryfona,
“Location-Based Services : A Database Perspective,” in Proceedings
of the 8th Scandinavian Research Conference on Geographical Information
Science, June 2001, pp. 59-68.

[KHR01] Uwe Kubach, Mario Hegele and Kurl Rothermel, “A Simulation
Framework for Mobile, Location-Dependent Information Access,” in
Proceedings of the 6th IEEE Symposium on Computers and Communcations,
Hammamet, Tunesia, August 2001, pp. 506-511.

[LC] Chiang Lee and Chao-Chun Chen, “A Data Delivery Strategy in
Ubiquitous Computing Systems,”

[LC02] Chang-Hung Lee and Ming-Syan Chen, “Processing Distributed
Mobile Queries with Interleaved Remote Mobile Joins,” in IEEE
Tractions on Computers, October 2002, Vol. 51, No. 10, pp. 1182-
1195.

[LLJ00] Kyungsook Y. Lee, Guoping Liu and Harry F. Jordan, “Hierarchical
Networks for Optical Communications,” DBLP Journal of
Parallel and Distributed Computing, 2000, Vol. 60, No. 1, pp 1-16,

[LXZ02] Dik Lun Lee, Jianliang Xu, and Baihua Zheng, “Data Management
in Location-Dependent Information Services,” in IEEE Pervasive
Computing, July-September 2002, Vol. 1, No. 3, pp 65-72.

[OW93] OuriWolfson, “Data Allocation in Mobile Computing: A Project
Description”, in Proceedings of IEEE Workshop on Advances in Parallel
and Distributed Systems, Princeton, NJ, October 1993, pp 89-94.

[PC00] Wen-Chih Peng and Ming-Syan Chen, “Mining User Moving Patterns
for Personal Data Allocation in a Mobile Computing System,”
in Proceedings of the 29th International Conference on Parallel Processing,
August 2000, pp 573-580.

[PC02] Wen-Chih Peng and Ming-Syan Chen, “Allocation of Shared Data
Based on Mobile User Movement,” in Proceedings of the 3rd IEEE
International Conference on Mobile Data Management, Singapore,
January 2002, pp 105-112.

[PC03] Wen-Chih Peng and Ming-Syan Chen, “Developing Data Allocation
Schemes by Incremental Mining of User Moving Patterns in
a Mobile Computing System,” in IEEE Transactions on Knowledge
and Data Engineering, January-February 2003, Vol. 15, No. 1, pp
70-85.

[PLYC00] Kaveh Pahlavan, Xinrong Li, Mika Ylianttila, Ranvir Chana
and Matti Latva-aho “An Overview of Wireless Indoor Geolocation
Techniques and Systems,” in Proceedings of IEEE Mobile Wireless
Communication Networks, Paris, May 2000, pp 1-13.

[SWH98] A. Prasad Sistla, Ouri Wolfson, and Y. Huang, “Minimization
of Communication Cost Through Caching in Mobile Environments,”IEEE Transactions on Parallel and Distributed Systems, April 1998,
Vol. 9, No. 4, pp 378-389.

[TH01] Takahiro Hara, “E?ective Replica Allocation in Ad Hoc Networks
for Improving Data Accessibility,” in Proceedings of IEEE INFOCOM
2001, Anchorage, Alaska, U.S.A., April 2001, Vol. 3, pp 1568-1576.

[WH98] Ouri Wolfson, Yixiu Huang, “Competitive Analysis of Caching
in Distributed Databases”, IEEE Transactions on Parallel and Distributed
Systems, April 1998, Vol. 9, No. 4, pp 391-409.

[WJ92a] Ouri Wolfson and Sushil Jajodia, “Distributed Algorithm for
Dynamic Replication of Data,” in Proceedings of the 11th ACM Principles
of Database Systems Symposium, San Diego, 1992, pp 149-163.

[WJ92b] Ouri Wolfson and Sushil Jajodia, “An Algorithm for Dynamic
Data Distribution,” in Proceedings of the 2nd IEEE Workshop on
the Management of Replicated Data, Monterey, November 1992, pp 62-65.

[WM91] Ouri Wolfson and A. Milo, “The Multicast Policy and Its Relationship
to Replicated Data Placement,” ACM Transactions on
Database Systems, March 1991, Vol. 16, No. 1, pp 181-205.

[XWCR02] B. Xu, Ouri Wolfson, S. Chamberlain, and N. Rishe, “Cost
Based Data Dissemination in Satellite Networks,” em ACM Mobile
Networks and Applications, January 2002, Vol. 7, No. 1, pp 40 66.

[YL97] Yi-Bing. Lin. “Modeling Techniques for Large-Scale PCS Networks,”
IEEE Communications Magazine, February 1997, pp 102-107.