Location-Aware Cluster-Based Routing Protocol Design for Wireless Networks

摘 要 無線網路提供使用者於有效傳輸範圍內自由活動的便利性，無線傳輸技術的進步，更實現了行動計算的可能性。無線隨意網路是一種沒有固定基地台的架構，在此架構中每一節點均可能成為一個路由器，負責路由的任務。由於隨意網路具有高移動性，傳統有線網路的路由協定並不適用隨意網路，因此必須重新設計合適的路由演算法。在無線網路中，能源是極受限制的資源，因此在設計路由演算法時，必須將其列為參考因素，以便延長整個網路系統的生命週期。 為了有效減少路由交通流量、碰撞、干擾，節省能源消耗，進而延長網路運作時間，在本論文中，提出幾種利用定位系統及分群技術來協助路由的路由演算法，經由大量的電腦模擬，實驗的結果顯示所提出的方法均有極佳的效能。 關鍵字：路由演算法、位置感知、隨意網路、感測網路Abstract Wireless networking offers freedom moving around the effective transmission area and the flexibility and easy to use function for Internet application. The advancement in wireless communication and portable computing devices has made mobile computing possible. A mobile ad hoc network (MANET) is an infrastructureless network with no fixed routers, hosts, or wireless base stations. Nodes of these networks function as routers, which discover and maintain routes to other nodes in the network. Routing protocols used in conventional wired networks are not suited to the mobile environment due to the considerable overhead produced by periodic route update messages and their slow convergence to topological changes. In ad hoc wireless networks, energy is a nonrenewable resource that a mobile node has a finite, monotonically decreasing energy store. These networks are power constrained because nodes operate with restricted battery power. Energy consumption at the network interface is an issue for all mobile computing devices. To minimize energy consumption in portable communication devices has been one of the major design goals for wireless networks. Minimum energy network design can allow longer battery life and mitigate interference. A network protocol that minimizes energy consumption is a key to low-power wireless networks. The limitation of bandwidth and energy are two challenges facing the design of wireless networks. Clustering enables bandwidth reuse and can, thus, increase system capacity. Cluster-based routing protocol enables better resource allocation and helps to improve power control and system lifetime. It will also enable the cluster heads to pre-process, aggregate and compress their data stream that further reducing energy dissipation. Recently, location-based routing protocol has obtained more attractive. Instead of searching route in the entire network blindly, location-based routing protocol using the location information of mobile nodes to confine the route searching space into a smaller estimated range. The smaller route searching space to be search, the less routing overhead and broadcast storm problem will be induce. In this dissertation, we propose some location-aided cluster-based routing protocols, which use geographical location information provided by positioning device in route discovery and route maintenance procedure. In our protocols, the whole network is partitioned into clusters. The path is constructed in a cluster-by-cluster basis. The performances of our algorithms were studied through extensive simulation. The simulation results reveal that our protocols have outstanding performance. Keywords: Routing Protocol, Location-Aware, Ad hoc Networks, Sensor NetworksTable of Contents Dedication................................................i Acknowledgements.........................................ii List of Tables..........................................vii List of Figures........................................viii Chapters 1.Introduction............................................1 2.Related Research and Simulation Tool....................8 2.1 Table-Driven Routing Protocols........................8 2.2 Demand-Driven Routing Protocols.......................9 2.3 Multicast Routing Protocols..........................10 2.4 Location-Based Routing Protocols.....................11 2.5 Cluster-Based Routing Protocols for Sensor Networks..14 2.6 Particle Swarm Optimization..........................14 2.7 Simulation Tool......................................15 3.Location-Aware Cluster-Based Multicast QoS Routing protocol (LACMQR)........................................16 3.1 The Operation of LACMQR..............................16 3.2 Simulation Results...................................25 4.Location-Aware Routing Protocol with Dynamic Adaptation of Request Zone for Mobile Ad Hoc Networks (LARDAR)......40 4.1 Motivation...........................................40 4.2 The LARDAR Routing Protocol..........................41 4.2.1 The definition of expected zone....................41 4.2.2 The definition of request zone.....................42 4.2.3 Determining the membership of forwarding node......44 4.2.4 The policy of Increase-Exclusive Search............45 4.2.5 Dynamic Adaptation of Request Zone.................47 4.2.6 The procedure of Route Discovery...................48 4.2.7 Route Recovery.....................................49 4.3 Simulation Results...................................49 5.Core Location-Aided Cluster Routing Protocol for Mobile Ad Hoc Networks (CLACR)..................................54 5.1 Motivation...........................................55 5.2 The CLACR Routing Protocol...........................57 5.2.1 Overview...........................................57 5.2.2 Network Partition..................................58 5.2.3 Cluster Head Election Protocol.....................59 5.2.4 Location Server Election Protocol..................61 5.2.5 Route Construction by Dijkstra Algorithm...........62 5.2.6 Route maintenance and Dynamic Route Optimization...65 5.2.7 Geocasting.........................................67 5.3 Simulation Results...................................67 6.Particle Swarm Optimization Algorithm for Energy-Efficient Cluster-Based Sensor Networks (PSO-SN).........77 6.1 Motivation...........................................78 6.2 The Proposed Protocol................................80 6.2.1 Overview...........................................80 6.2.2 The Optimum Number of Clusters Determination.......81 6.2.3 Cluster Formation by Particle Swarm Optimization Algorithm................................................81 6.2.4 Variations of Our Algorithm........................82 6.2.5 Cluster Heads Rotation Policy......................84 6.3 The Occasion of Cluster-Based and NonCluster-Based Protocol.................................................85 6.4 Simulation Results...................................87 7.Particle Swarm Optimization Algorithm for Energy-Efficient Cluster-Based Sensor Networks with Directional Antennas (PSO-SNDA)......................................92 7.1 Energy Model.........................................93 7.2 The Proposed Protocol................................94 7.2.1 Estimation of the Optimum Number of Clusters.......95 7.2.2 Cluster Construction by Particle Swarm Optimization Algorithm................................................97 7.3 The Time to Apply Cluster-Based Protocol.............99 7.4 Simulation Results..................................101 8.Conclusions and Future Works..........................105 8.1 Research Contributions..............................105 8.2 Future Works........................................106 Bibliography............................................10