臺灣博碩士論文加值系統

本論文提出了一個在隨意式無線網路(Ad Hoc Wireless Networks)中全新的繞送演算法，名為以全球定位系統為基礎的集合式繞送演算法(GPS-based Quorum Hybrid Routing Algorithm)，或簡稱GPS-QHRA。在這個演算法中，我們把網路分割成若干個六角形區域(zone)。在全球定位系統(GPS)的技術下，網路中的每一個節點都知道它自己在那一個區域中，對於節點的方位很容易掌握，因此特別適用於隨意式無線網路中的環境。我們在每個區域中挑選出一個特別的資料庫節點(Location Database Node)，用來模擬在蜂巢式系統中HLR的功能。每個資料庫節點負責收集它管區之內節點的繞送資訊。在GPS-QHRA中，數個資料庫組成一個有規則集合(Uniform Quorum System)。這些有規則集合兩兩相交且相異，當來源節點有封包需要傳送時，會先查詢它所屬的資料庫節點，之後該資料庫節點會選出一個有規則集合，再根據那個有規則集合中的資料庫節點來查詢。由於有規則集合兩兩相交，因此我們便能用局部(Local)資訊，來獲得整體(global)網路中各節點的相對位置資訊。本文所提出的演算法能夠改善一個同樣是利用GPS技術的區域式階層鍊結繞送(Zone Hierarchical Link State)演算法。在ZHLS演算法中，其區域是以正方形劃分，而我們所提的演算法則是以六角形劃分，因此區域跟區域之間可以從4個方向傳輸改為6個方向傳輸，從而在繞送時可減少封包的數量和縮短路徑的長度(number of hops)。同時，在ZHLS演算法中並沒有叢集標頭(Cluster Head)的觀念，故每個節點都要維護繞送資訊。在GPS-QHRA中，利用資料庫節點作中央管理，負責維護每個區域(Zone)之間的繞送資訊，因此可減少多餘封包的產生，從而減少網路負載。最後一點是: 當來源節點要傳送封包給在區域之外的目標節點時，在ZHLS演算法中，必須發出一個位置搜尋封包廣播給網路中所有其他的區域來找出目標節點的位置。而在本論文的演算法中，由於具備有規則集合的觀念，因此只需廣播給有規則集合中的資料庫節點即可。在本論文的模擬中將可看到，GPS-QHRA所產生的網路負載、平均路徑長度、較ZHLS為佳。

In this Paper, a new routing protocol for Ad Hoc wireless networks, called GPS-based Quorum Hybrid Routing Algorithm (GPS-QHRA) is proposed. In this protocol, we assumed that the ad hoc network is divided into non-overlapping hexagon zones. With the aids of GPS, each node can keep track its position as its zone number. In each zone, we choose a special node, called Location Database Node, to perform the function of HLR as in cellular networks. The purpose of the Location Datatbase Node is to collect the routing information within its zone. All the Location Database Nodes in all hexagon zones are formed as Quorum, every two of which intersect at a constant number of databases. Upon location update of call arrival, a mobile’s location information is written to or read from all the databases of a quorum. Compared to a hyrbird routing algorithm, which uses GPS named Zone Hierarchical Link State (ZHLS), our proposed algorithm is more efficient. Since in ZHLS, zones are divided by square in the network, but in our proposal, zones are divided by hexagon, some research has showed that, hexagon model has more efficient than sqare model. Moreover, in ZHLS, every node has to maintain routing information, but in GPS-QHRA, database nodes only need to maintain routing information, preventing duplicate packets generated in the network, which in turn has less overheads. The last comparison is, a probe packet is needed to broadcast to all other zones in the network for finding the location of destination’s node in ZHLS when a node want to initiate a call to nodes that are not within its zones. In GPS-QHRA, we only need to multi-cast to the quorum's databases. Simulation will showed that GPS-QHRA has more efficiently compared to ZHLS.

目錄索引
論文口試委員審定書I
授權書2
中文摘要3
英文摘要4
誌謝5
目錄索引6
1 緒論9
2 相關研究11
2-1 Table Driven繞送演算法11
2-2 Source-Initiated On-Demand繞送演算法12
2-3 Table-Driven VS On-Demand繞送演算法13
2-4 Hybrid繞送演算法14
2-4-1 ZHLS繞送演算法14
2-4-2 ZHLS節點的階層式結構14
2-4-3 節點連接狀態封包(node LSP)與區域連接狀態封包(zone LSP)的產生15
2-4-4 ZHLS繞送法則17
2-4-5 Hybrid VS On-Demand與Table-Driven18
2-5 有規則集合式系統(Uniform Quorum System)18
2-5-1 UQS的環境19
2-5-2 UQS繞送法則19
2-5-3 UQS資料庫維護機制20
2-5-4 有規則集合式系統的建構21
3 GPS-QHRA23
3-1 環境參數23
3-2 GPS-QHRA設計前的定義24
3-2-1 區域地圖(Zone Map)的設計24
3-2-2 有規則集合的定義25
3-3 GPS-QHRA協定25
3-3-1挑選方位資料庫25
3-3-2 GPS-QHRA繞送表格的產生27
3-3-3 GPS-QHRA繞送法則29
3-3-4 GPS-QHRA位置更新法則30
3-3-5 方位資料庫節點重新挑選法則30
3-3-6 GPS-QHRA容錯法則31
4 模擬評估33
4-1 模擬環境33
4-2 模擬參數35
4-2-1 平均路徑長度35
4-2-2 LSP封包產生的比較37
4-2-3 移動性的影響38
4-2-4 搜尋路徑的負載41
5 結論44
參考文獻45

[1]Royer, E.M.; Chai-Keong Toh, “A Review of Current Routing Protocols For Wireless Ad Hoc Networks”, IEEE Personal Communications, Volume: 6 2, April 1999, pp.46 —55.
[2]D.Baker et al., “Flat Vs. Hierarchical Network Control Architecture” ARO/DARPA Wksp. Mobile Ad—Hoc Networking; Mar.
[3]1997.
[4]L.Kleinrock and F.Kamoun, “Hierarchical Routing for Large Networks: Performance Evalution and Optimization” Computer Networks, Vol.1, No.3, 1977, pp.155-174.
[5]C. E. Perkins and P.Bhagwat, “Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers” Comp. Commun.Rev. Oct.1994, pp.234-244.
[6]C-C, Chiang. “Routing in Clustered Multihop, Mobile Wireless Networks with Fading Channel”Proc.IEEE SICON ’97, APR.1997. Pp.197-211.
[7]C.E. Perkins and E.M. Royer, ”Ad-hoc On-Demand Distance Vector Routing” Proc. 2nd IEEE Wksp. Mobile Comp. Sys and Apps, Feb.1999, pp.90-100.
[8]V.D. park and M.S. Corson, “A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks” Proc. INFOCOM ’97, Apr 1997.
[9]Paul,K.; Bandyopadhyay,S.; Mukherjee; Saha,D.”Communication-aware mobile hosts in ad-hoc wireless network” Personal Wireless Communication, 1999 IEEE International Conference on, 1999,pp.83-87.
[10]Joa-Ng. M.; I-Tai Lu “A peer-to-peer zone-based two-level link state routing for mobile ad hoc networks” Selected Areas in Communications, IEEE Journal on Volume: 178,Aug. 1999, pp.1415 —1425.
[11] E.D. Kaplan (Editor), Understanding The GPS: Principles and Applications Artech House, Boston, MA, Feb 1996.
[12] Moore， T. “An introduction to the global positioning system and its applications, Developments in the Use of Global Positioning Systems, 1994, pp.1/1-1/6.
[13] Haas, Z.J.; Liang, B., “Ad Hoc Mobility Management with Uniform Quorum Systems”, Networking, IEEE/ACM Transactions on Volume: 7 2, April 1999, pp.228-240.
[14] A. Ephremides, J.E. Wieselthier, and D.J. Baker, “A design concept for reliable mobile radio networks with frequency hopping signaling” Proc.IEEE, vol.75, pp. 56-83. Jan 1987.
[15] B.Das and V.Bharghavan, “Routing in ad-hoc networks using minimum connected dominating sets” presented at IEEE Int. Conf. Communication, Montreal, Canada, June 1997.
[16] A.Dey, Theory of Block Designs, 1986.
[17] Chih-Yung Chang, Tzu-Ting Wu, Chia-Ho Ou and Yao-Wen Chang, “Celluar Based Management Model for Mobile Hosts in Ad Hoc Networks”, Tamsui Oxford Journal of Matematical Sciences 16 (1) March, 2000, pp.51-65.
[18] S.Singh, M.Woo, and C.S. Raghavendra, “Power-Aware Routing in Mobile Ad Hoc Networks” Proc ACM/IEEE MOBICOM ’98, Oct. 1998.
[19]Zheng-Ying Liu, Tein-Yew Chung, “Stabilization Strategy and Routing for Ad-Hoc Wireless Networks”, Institute of Electrical and Computer Engineering and Science Yuan-Ze University of Technology, 2000.
[20] Zhenyu Tang, Garcia-Luna-Aceves, J.J., “collision-avoidance transmission scheduling for ad-hoc networks” Communications, 2000. ICC 2000. 2000 IEEE International Conference on Volume: 3, 2000, PP. 1788 —1794, vol. 3.
[21]Chunhung Richard Lin; Jain-Shing Liu, “Bandwidth routing in ad hoc wireless networks” Global Telecommunications Conference, 1998. GLOBECOM 1998. The Bridge to Global Integration. IEEE Volume: 4, 1998, pp.2477-2482, vol. 4.