臺灣博碩士論文加值系統

由於行動隨意網路與點對點網路的普及化，因此在行動隨意網路上如何整合點對點系統，以提供更有效率的分散式應用，將是一項重要的議題。這兩種網路具有一些相同的特性，例如，不需要集中式的基礎設備，能夠自我組態，適用於常變動的網路拓樸架構等等。然而，隨著點對點系統的快速發展，目前已經提出了相當多的路由機制。Distributed Hash Table(DHT)是這些路由機制中，其中一種比較有效率的方法，但是這樣的系統卻不適合直接建置在行動隨意網路之中。這是因為DHT忽略了節點在實際的網路拓樸中的分布情況，而造成需要付出昂貴的路由overhead。
因此，在本篇論文中，我們提出了具備位置感知以及能夠在常數時間內完成尋找的路由協定-SLSR，此協定最主要的目標在於降低路由時的訊息傳輸overhead，同時在叢集式的行動隨意網路中，提供錯誤容忍與平衡節點工作量的設計策略。我們的方法是利用超級節點式的點對點網路與Random Landmarking(RLM)機制來建構出具備位置感知的叢集，目的就是為了要降低整個網路中的訊息傳輸overhead，以提供更有效率的路由機制。
最後，我們透過模擬工具，來比較我們所提出的方法以及MADPastry所提出的路由機制。MADPastry與我們的作法相似，均以RLM機制來建構出具備位置感知的叢集，但是卻會造成大量的overhead。而模擬結果最後也顯示，在每一次的routing中，我們的方法能夠降低的通訊所造成的overhead以及提供較少的hop個數以完成路由之目的。

As mobile ad hoc network (MANET) and peer-to-peer (P2P) network become more popular, it becomes more and more interesting to integrate these two networks, because they both share common characteristics, such as infrastructure-less, self-organization, highly dynamic network topology, etc. However, there are many of routing approaches have been proposed with the rapidly growing of P2P system. Distributed Hash Table (DHT) is one of efficient routing algorithms in the P2P system but it is ill-suited for direct deploying in MANET. DHT ignores the physical deployment of nodes in the network topology and causes expansive routing overhead.
Therefore, in this thesis, we present a locality-aware and constant-time lookup routing protocol – SLSR that concentrates on reducing routing overhead, providing fault-tolerance and load-balance strategy in the cluster-based MANET. Our approach utilizes the concept of super-peer P2P network and Random Landmarking (RLM) to construct locality-aware cluster in order to decreasing the overhead in the whole network to provide efficient routing approach.
We compare our approach performance with MADPastry agent by simulation. The MADPastry is similar as our approach both using RLM to construct locality-aware cluster and causes large overhead. The simulation results show that our approach has low communication overheads and hop counts for each routing.

誌 謝 I
摘 要 II
ABSTRACT III
CONTENTS IV
FIGURE CAPTIONS V
1. INTRODUCTION 1
2. RELATED WORKS 5
3. THE DETAIL OF SLSR 8
3.1. BASIC IDEA 8
3.2. CROSS-LAYER ARCHITECTURE 9
3.3. DETAIL OF OUR PROPOSAL METHOD 11
3.3.1. Network Initiation 11
3.3.2. Routing Tables 14
3.3.3. The Packet Design of SLSR 19
3.3.4. Example of Routing 21
3.3.5. Node Departure and Fault Tolerance 25
4. SIMULATION SETUP AND RESULTS 27
4.1. SIMULATION ENVIRONMENT 27
4.2. SIMULATION RESULTS 29
5. CONCLUSIONS 35
REFERENCES 36

[1]B. Tang, Z. Zhou, K. A., and T.c. Chiueh. “An integrated approach for P2P file sharing on multi-hop wireless networks”, Wireless And Mobile Computing, Networking And Communications, 2005. (WiMob'2005), IEEE International Conference on, Aug. 2005. Page(s):268 - 274 Vol. 3.
[2]Yan, Lu. ”Performance Evaluation and Modeling of Peer-to-Peer Systems over Mobile Ad hoc Networks”, TUCS - Turku Centre for Computer Science Technique report, Mar. 2005.
[3]C. E. Perkins and P. Bhagwat. "Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers", In Proc. Of ACM SIGCOMM , Aug. 1994.
[4]D. B. Johnson and D. A. Maltz. "Dynamic Source Routing in Ad Hoc Wireless Networks", Kluwer Academic, 1996.
[5]C. Perkins, E. Belding-Royer, and S. Das. "Ad hoc On-Demand Distance Vector (AODV ) Routing", IETF RFC 3561, July 2003.
[6]J. Li and S. Vuong. "An Efficient Clustered Architecture for P2P Networks", Proceedings of the 18th IEEE International Conference on Advanced Information Networking and Applications, AINA2004, Fukuoka, Japan, Mar. 2004.
[7]Gnutella website. http://gnutella.wego.com/
[8]Napster website. http://www.napster.com/
[9]Kazaa website. http://www.kazaa.com/
[10]A. Rowstron and P. Druschel. "Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems", In Proc. of Middleware, Nov. 2001.
[11]B. Y. Zhao, J. D. Kubiatowicz, and A. D. Joseph. “Tapestry: An Infrastructure for Fault-Resilient Wide-area Location and Routing”, Technical Report UCB//CSD-01-1141, U. C. Berkeley, April 2001.
[12]Stoica. I., Morris. R., Liben-Nowell. D., Karger. D.R., Kaashoek. M.F., Dabek. F., and Balakrishnan. H. "Chord: a scalable peer-to-peer lookup protocol for Internet applications", Networking, IEEE/ACM Transactions on Volume 11, Issue 1, Feb. 2003, Page(s):17 – 32.
[13]S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Schenker. “A Scalable Content-Addressable Network”, In Proc. of ACM SIGCOMM, Aug. 2001.
[14]R. Winter, T. Zahn, and J. Schiller. "Random Landmarking in Mobile, Topology-Aware Peer-to-Peer Networks", In Proc. of FTDCS, May 2004.
[15]Rüdiger Schollmeier, Ingo Gruber, and Michael Finkenzeller “Routing in Mobile Ad Hoc and Peer-to-Peer Networks. A Comparison”, In Networking 2002, International Workshop on Peer-to-Peer Computing, Pisa, Italy, May 19-24, 2002.
[16]FastTrack website http://www.fasttrack.nu/
[17]A. Mizrak, Y. Cheng, V. Kumar, and S. Savage. “Structured superpeers: Leveraging heterogeneity to provide constant-time lookup”, In IEEE Workshop on Internet Applications, 2003.
[18]Pucha. H., Das. S.M., and Hu. Y.C. "Ekta: an efficient DHT substrate for distributed applications in mobile ad hoc networks", Mobile Computing Systems and Applications, 2004. WMCSA 2004. Sixth IEEE Workshop on 2-3 Dec. 2004. Page(s):163 – 173.
[19]Y. C. Hu, S. M. Das, and H. Pucha. “Exploiting the synergy between peer-to-peer and mobile ad hoc networks”, In Proc. of HotOS-IX, May 2003.
[20]T. Zahn and J. Schiller. "MADPastry: A DHT Substrate for Practicably Sized MANETs", In Proc. of ASWN, June 2005.
[21]R. Winter, T. Zahn, and J. Schiller. "Topology-Aware Overlay Construction in Dynamic Networks", In Proc. of 3rd International Conference on Networking, Guadaloupe, France, Mar. 2004.
[22]NCTUns-3.0 website. http://nsl10.csie.nctu.edu.tw/
[23]G. Ding and B. Bhargava. “Peer-to-peer file-sharing over mobile ad hoc networks”, In Proceedings of IEEE Annual Conference on Pervasive Computing and Communications Workshops, March 2004. Page(s):104– 109.