臺灣博碩士論文加值系統

無線隨意網路近來受到廣泛的注意，一般而言，我們將其視為一獨立之網路。在此論文中，我們提出二階異質無線隨意網路架構，使其具有連結網際網路之能力。這網路的低階部分包含了一群配備無線網路卡的行動主機；為了連結網際網路以及克服網路分割問題，網路的高階部份由部份具有連接電話網路或基礎網路能力的行動主機所構成，我們稱之為閘道器。而這些高階閘道器的網路介面可以是無線網路、PHS手機或GPRS手機等，各具有不同的頻寬特性。由於閘道器的頻寬較狹小，很容易就成為網路傳輸的瓶頸，我們在此提出了三類的方法來處理負載平衡繞徑之議題，分別是 boundary-moving、host-partitioning 以及 probabilistic 方式。同時，我們考量了一些實作上的問題。模擬的結果以及一個負載平衡繞徑原形之實作都將呈現在此論文中。

The mobile ad hoc network (MANET) has attracted a lot of interest recently. However, most of the existing works have assumed a stand-alone MANET. In this thesis, we propose a two-tier, heterogeneous MANET architecture which can support Internet access. The low tier of the network consists of a set of mobile hosts each equipped with an IEEE 802.11 wireless LAN card. In order to connect to the Internet and handle the network partitioning problem, we propose that the high tier is comprised of a subset of the mobile hosts, called gateways, which can access to cellular / infrastructure networks. The high tier is heterogeneous in the sense that the network interfaces in the gateway hosts could be IEEE 802.11 cards, PHS handsets, or GPRS handsets characterized by different bandwidths and latencies. Observing that the gateways could become the bottlenecks of the two-tier network, we propose a set of solutions, namely boundary-moving, host-partitioning, and probabilistic solutions, to solve the load-balance routing issue. Implementation issues/concerns of these schemes are discussed. Simulation results are presented to compare these load-balance routing schemes. Prototype implementation experiences of such a network architecture is also presented.

Abstract 2
1 Introduction 9
2 System Model 13
2.1 Problem Statement 14
3 Boundary-Moving Solutions 17
3.1 Shortest-Path (SP)Routing 17
3.2 Minimum Load-Index (MLI) Routing 19
4 Host-Partitioning Solutions 21
4.1 Centralized Assignment (CA) 21
4.2 Distributed Assignment (DA) 22
4.3 Implementation Concerns: Source Routing and IP-in-IP Encapsulation 23
5 Probabilistic Solutions 25
5.1 Fully Probabilistic (FP) Routing 25
5.2 Partially Probabilistic (PP) Routing 26
5.3 Implementation Concerns: Binding with Multiple FAs 27
6 Prototype Implementation and Scenario Demonstration 29
6.1 Prototype Implementation 29
6.2 Scenario Demonstration 32
7 Simulation Results 35
8 Conclusions 41

[1] F. Aurenhammer. Voronoi Diagrams: a Survey of a Fundamental Geometric Data Structure.
ACM Computing Surveys, 23(3):345—405, Sep. 1991.
[2] C. E. Perkins. Mobile IP Design Principles and Practices. Addison-Wesley, Boston, MA,
USA, 1997.
[3] C. E. Perkins. Ad Hoc Networking. Addison-Wesley, Boston, MA, USA, 2001.
[4] C. E. Perkins. Mobile IP. IEEE Communications Magazine, 40(5):66—82, May 2002.
[5] C. E. Perkins and E. M. Royer. Ad hoc On-Demand Distance Vector Routing. In Proc.
of the 2nd IEEE Workshop on Mobile Computing Systems and Applications, Feb. 1999.
[6] C. E. Perkins and P. Bhagwat. Highly Dynamic Destination-Sequenced Distance-Vector
Routing (DSDV) for Mobile Computers. In Proc. of the ACM SIGCOMM Conference
on Communications Architectures, Protocols and Applications, pages 234—244, 1994.
[7] E. M. Royer and C.-K. Toh. A Review of Current Routing Protocols for Ad Hoc Mobile
Wireless Networks . IEEE Personal Communications, pages 46—55, Apr. 1999.
[8] D. B. Johnson and D. A. Maltz. Dynamic Source Routing in Ad Hoc Wireless Networks.
Mobile Computing, 353, 1996.
[9] M. R. Garey and D. S. Johnson. Computers and Intractability. A guide to the Theory
of NP-Completeness. W.H. Freeman, New York, USA, 1999.
[10] J. P. Macker and M. S. Corson. Mobile Ad Hoc Networking and the IETF. Mobile
Computing and Communications Reviews, 4(4):12—13, Oct. 2000.
[11] A. K. Parekh and R. G. Gallager. A generalized processor sharing approach to flow
control in integrated services networks: The singlenode case. IEEE/ACM Trans. on
Networks, 1(3):344—357, June 1993.
[12] J. B. Postel (Ed.). Internet Protocol. Internet Request For Comments RFC 791. Sep.
1981.
[13] R. E. Miller and J. W. Thatcher (eds.). Complexity of Computer Computations. Plenum
Press, New York, USA, 1972.
[14] S. Lu, V. Bharghavan, and R. Srikant. Fair Scheduling in Wireless Packet Networks.
IEEE/ACM Trans. on Networks, 7(4):373—389, Aug. 1999.
[15] S. R. Das, C. E. Perkins, E. M. Royer and M. K. Marina. Performance Comparison of
Two On-demand Routing Protocols for Ad hoc Networks. IEEE Personal Communications
Magazine special issue on AD hoc Networking, Feb. 2001.
[16] D. Stiliadis and A. Varma. E±cient Fair Queueing Algorithms for Packet-Switched
Networks. IEEE/ACM Trans. on Networks, 6(2):175—185, Apr. 1998.
[17] T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. MIT
Press, Cambridge, England, 1994.
[18] S. A. Thomas. IPng and the TCP/IP Protocols, chapter 4, pages 113—117. John Wiley
& Sons, Inc, New York, USA, 1996.
[19] Y.-C. Tseng and C.-C. Shen. Mobile IP and Ad Hoc Networks: An Integration and
Implemementation Experience. Master’s thesis, National Chiao Tung University, Hsin-
Chu, Taiwan, June 2002.
[20] I.-W. Wu, W.-S. Chen, H.-E. Liao, and F.-F. Young. A seamless hando® approach
of Mobile IP protocol for mobile wireless data networks. IEEE Trans. on Consumer
Electronics, 48(2):335—344, May 2002.
[21] Y.-C. Tseng and T.-Y. Hsieh. Fully Power-aware and Location-aware Protocols for
Wireless Multi-Hop Ad Hoc Networks. In Proc. of the Int’l Conf. on Computer Communication
and Networks (ICCCN), 2002.