近年來，電腦設備和無線通訊技術 不斷地突飛猛進，進而也引發人們對於發展 行動隨意無線網路(ad hoc networks)的興趣。行動隨意無線網路的特點之一，就是它不需要預先存在任何有線或無線的網路基礎建設(如：基地台、路由器、交換器)且不需要集中式的管理，行動節點之間的資料傳輸 均藉由鄰近節點的轉傳來完成。 在行動隨意無線網路環境下，無線節點可以任意移動，整個網路拓樸隨時都將有不可預期的變化。所以，在行動隨意無線網路下，設計一個有效的繞路協定也成了一種挑戰。過去十年來，已有許多適用於行動隨意無線網路環境下的路由協定被提出來。

　　為解決行動隨意無線網路環境下的繞路問題，已有許多的路由協定陸續被提出，像是 DSDV、WRP、FSR 和 AODV…等路由協定。而這些路由協定對於行動隨意無線網路環境下的某些應用，像是行動主機間彼此直接交談的應用著實非常有用，例如：視訊會議。然而在行動隨意無線網路環境下，還有另一種應用是 行動節點會直接對存放在別的行動節點的資料作存取，例如：救災時，救難人員彼此收集的情資直接分享使用。後者這方面的應用，路由協定僅能增進原本就連通的節點之間的通訊效率，但是，一旦網路被分割，節點和“擁有所需的資料的行動節點”分屬兩個不連通的網路，此時採用再好的路由協定 也無法取得所需資料。

　　實際上，行動隨意無線網路環境下，因為各節點皆任意地移動，收訊不良而斷線的情況也時常發生，導致於網路拓樸被分割的情形 發生的非常頻繁。而網路拓樸被分割將會導致“資料存取的成功率”下降。如何來避免『因為網路拓樸被分割而導致資料存取的成功率下降』 這是一個很重要的議題。而這也正是我們這篇論文所要探討。一個可行的處理辦法就是在行動節點上存放原本不屬於它的資料 的資料複製品。

　　在這篇論文中，我們提出了三個有效率的資料複製品的配置方法，來減緩因網路分割所帶來 資料存取的成功率下降的負面影響。在這些方法中，主要考慮 行動節點對每筆資料的存取次數、行動節點的degree值及 網路相連的狀態。

　In recent years, the advances in computer and wireless communication technologies have led to a growing interest in wireless ad hoc networks which are constructed only from mobile hosts. In ad hoc networks, however, the unpredictable topology of the network structure changes frequently and depends on the movement of mobile hosts. Consequently, it becomes a challenge to design an efficient routing protocol for ad hoc networks. To provide multi-hop communication in ad hoc networks, many ad hoc routing protocols have been suggested in the past ten years.

　Some typical ad hoc routing protocols, such as Destination Sequenced Distance Vector (DSDV), Wireless Routing Protocol (WRP), Fisheye State Routing (FSR), and Ad hoc On-demand Distance Vector routing (AODV) have been proposed. Actually, these routing protocols are really useful for applications where users equipped with mobile hosts directly communicate with each other, e.g., video conference systems. However, in ad hoc network, there are also other applications where mobile hosts access data items held by other mobile hosts. In these applications, the routing protocols can only improve the connectivity among mobile hosts which are connected to each other, but can do nothing when the network is divided.

　In fact, in ad hoc networks, since mobile hosts move freely, disconnections occur very often, and this causes network division frequently. Network division frequently results in deterioration of data accessibility. Preventing deterioration of data accessibility at the point of network division is a very important issue. We want to reduce the deterioration of data accessibility at the point of network division. A possible solution is to replicate data items on mobile hosts which are not the owners of the original data.

　In this paper, we propose three replica allocation methods to improve data accessibility by replicating data items on mobile hosts. In these three methods, we take into account the access times from mobile hosts to each data item, the degree value of the mobile host, and the status of the network connection. We also show the results of simulation experiments regarding the performance evaluation of our proposed methods.

[1] D.J. Baker, J. Wieselthier and A. Ephremides, A distributed algorithm for scheduling the activation of links in a self-organizing, mobile, radio network, in: Proceedings of IEEE ICC’82 (1982) pp. 2F6.1–2F6.5.

[2]Elizabeth, Royer, Chai-Keong, Toh: A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks, April 1999, IEEE Personal Communications.

[3] Haas, Zygmunt J., Jing Deng, Ben, Liang, Panagiotis Papadimitrator, S., Sajama, Wireless Ad Hoc Networks, Ithaca, New York, 2001

[4]E. M. Royer and C. Toh, “A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks,” IEEE Personal Communications, April 1999.

[5]C. E. Perkins, and P. Bhagwat, “Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers,” Proceedings of ACM SIGCOMM’94, London, UK, Aug. 1994, pp. 234-244.

[6]S. Murthy and J.J. Garcia-Luna-Aceves, “An Efficient Routing Protocol for Wireless Networks,” ACM/Baltzer Mobile Networks and Applications, vol. 1, no. 2, Oct.1996, pp.183-197.

[7] G. Pei, M. Gerla, and T. W. Chen, “Fisheye State Routing: A Routing Scheme for Ad Hoc Wireless networks,” in Proceedings of ICC 2000, New Orleans, LA, Jun. 2000.

[8] C.E. Perkins and E.M. Royer, "Ad Hoc On-Demand Distance-Vector Routing", Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications, pages 90-100, February 1999.

[9] Johnson, D. B.,Maltz, D. A.: Dynamic Source Routing in Ad-Hoc Wireless Networking, Mobile Computing, T. Imielinski and H. Korth, Eds. Norwell, MA: Kluwer, 1996, pp. 153-181

[10] 7] Park, V. D., Corson, M. S.: A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks, April 1997, Proc. IEEE INFOCOM ’97, Kobe, Japan

[11] Johnson, D.B., and Maltz, D.A. , “Dynamic Source Routing in Ad-Hoc Wireless Networking,” in Mobile Computing, T. Imielinski and H. Korth, editors, Kluwer Academic Publishing, 1996.

[12]Park, V.D., and Corson, M.S. “A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks,” IEEE INFOCOM ’97, Kobe, Japan, 1997.

[13] Perkins, C.E. and Royer, E.M., “Ad Hoc On-Demand Distance Vector Routing,” IEEE WMCSA’99, New Orleans, LA, Feb. 1999.

[14] M.J. Carey and M. Livny, “Distributed concurrency control performance: Astudy of algorithm, distribution, and replication,” Proc. 14th VLDB Conference,pp.13-25, 1988.

[15] A.W. Fu and D.W.L Cheung, “A transaction replication scheme for a replicated database with node autonomy,” Proc. 20th VLDB Conference, pp.214-225, 1994.

[16] T. Hara, K. Harumoto, M. Tsukamoto, and S. Nishio, “Dynamic replica allocation using database migration in broadband networks,” Proc. IEEE ICDCS 2000, pp.376-384, 2000.

[17] N. Krishnakumar and A.J. Bernstein, “High performance escrow algorithms for replicated databases,” Proc. 18th VLDB Conference, pp.175- 186, 1992.

[18] M. Stonebraker, “Concurrency control and consistency in multiple copies of data in distributed INGRES,” IEEE Transactions on Software Engineering, Vol.3, No.3, pp.188-194, 1979.

[19] R.H. Thomas, “A majority consensus approach to concurrency control for multiple copy databases,” ACM Transaction on Database Systems, Vol.4, No.2, pp.180-209, 1979.

[20] O.Wolfson and A. Milo, “The multicast policy and its relationship to replicated data placement,” ACM Transaction on Database Systems, Vol.16, No.1, pp.181-205, 1991.

[21] O.Wolfson and S. Jajodia, “Distributed algorithms for dynamic replication of data,” Proc. ACM PODS’92, pp.149-163, 1992.

[22] A.V. Aho, J.E. Hopcroft, and J.D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.

[23] T. Hara, Effective replica allocation in ad hoc networks for improving data accessibility, in : proceedings of IEEE INFCOM 2001(2001) pp. 1568-1576.