臺灣博碩士論文加值系統

摘 要

無線網路提供使用者於有效傳輸範圍內自由活動的便利性，無線傳輸技術的進步，更實現了行動計算的可能性。無線隨意網路是一種沒有固定基地台的架構，在此架構中每一節點均可能成為一個路由器，負責路由的任務。由於隨意網路具有高移動性，傳統有線網路的路由協定並不適用隨意網路，因此必須重新設計合適的路由演算法。在無線網路中，能源是極受限制的資源，因此在設計路由演算法時，必須將其列為參考因素，以便延長整個網路系統的生命週期。
為了有效減少路由交通流量、碰撞、干擾，節省能源消耗，進而延長網路運作時間，在本論文中，提出幾種利用定位系統及分群技術來協助路由的路由演算法，經由大量的電腦模擬，實驗的結果顯示所提出的方法均有極佳的效能。

關鍵字：路由演算法、位置感知、隨意網路、感測網路

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 Networks

Table 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............................................107

Bibliography

[1]A. Spyropoulos and C. Raghavendra, “Energy efficient communications in ad hoc networks using directional antennas,” Proceedings of IEEE INFOCOM, New-York, USA, 2002.
[2]B. Karp and H. T. Kung, “GPSR: Greedy Perimeter Stateless Routing for Wireless Networks,” Proceedings of MOBICOM’00, pp. 243-254, Aug. 2000.
[3]C. C. Chiang, “Routing in Clustered Multihop, Mobile Wireless Networks with Fading Channel,” Proc. IEEE SICON ’97, pp. 197-211, Apr. 1997.
[4]C. C. Chiang, M. Gerla, and L. Zhang, “Forwarding Group Multicast Protocol (FGMP) for Multihop, Mobile Wireless Networks,” Baltzer Cluster Computing, Vol. 1, No. 2, pp. 187­196, 1998.
[5]C. C. Chiang, M. Gerla, and L. Zhang, “Adaptive Shared Tree Multicast in Mobile Wireless Networks,” Proceedings of IEEE GLOBECOM''98, Sydney, Australia, pp. 1817­1822, Nov. 1998.
[6]C. E. Perkins and P. Bhagwat, “Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers,” Comp. Commum. Rev., pp. 234-44, Oct. 1994.
[7]C. E. Perkins and E. M. Royer, “Ad-hoc On-Demand Distance Vector Routing,” Proceedings of 2nd IEEE Wksp. Mobile Comp. Sys. and Apps., pp. 90-100, Feb. 1999.
[8]C. K. Toh, “A Novel Distributed Routing Protocol to Support Ad-Hoc Mobile Computing,” Proceedings of 1996 IEEE 15th Annual int’l. Phoenix Conf. Comp. And Commun., pp. 480-86, Mar. 1996.
[9]C. W. Wu and Y. C. Tay, “AMRIS: A Multicast Protocol for Ad hoc Wireless Networks,” Proceedings of IEEE MILCOM''99, Atlantic City, NJ, Nov. 1999.
[10]E. Bommaiah, M. Liu, A. McAuley, and R. Talpade, “AMRoute: Adhoc Multicast Routing Protocol,” IETF Internet­Draft, draft­talpade­manet­ amroute­00.txt, Aug. 1998.
[11]E. Crawley et al., “A Framework for QoS-based Routing in the Internet,” RFC 2386, http://www.ietf.org/rfc/rfc2386.txt, Aug 1998.
[12]E. D. Kaplan. Understanding the GPS: Principles and Applications, Artech House, Boston, MA, Feb. 1996.
[13]E. M. Royer, C. K. Toh, “A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks,” IEEE Personal Communications, pp. 46-55, Apr. 1999.
[14]E. M. Royer and C. E. Perkins, “Multicast Ad­hoc On­Demand Distance Vector (MAODV) Routing,” IETF Internet Draft, draft­ietf­manet­maodv­00.txt, July 2000.
[15]E.Yoneki and J. Bacon, “Distributed multicast grouping for publish/subscribe over mobile ad hoc networks,” IEEE Wireless Communications and Networking Conference, Vol. 4, pp. 2293-2299, Mar. 2005.
[16]Fred Bauer and Anujan Member, “Distributed Algorithms for Multicast Path Setup in Data Networks,” IEEE ACM Transactions on networking, Vol. 4, No. 2, Apr. 1996.
[17]Guerin et. al., “Equivalent Capacity and Its Application to Bandwidth Allocation in High-Speed Networks,” IEEE JSAC, Vol. 9, No. 7, September 1991.
[18]G. Dommety and R. Jain, “Potential networking applications of global positioning systems (GPS),” Tech. Rep. TR-24, CS Dept., The Ohio State University, April 1996.
[19]G. N. Rouskas and I. Baldine, “Multicast routing with end-to-end delay variation constraints,” IEEE JSAC, Vol. 15, No. 3, pp. 346-356, Apr. 1997.
[20]Heppner, F. and U. Grenander, “A stochastic nonlinear model for coordinated bird flocks,” in S. Krasner, Ed., The Ubiquity of Chaos. AAAS Publications, Washington, DC, 1990.
[21]H. F. Salama, D. S. Reeves, and Y. Viniotis, “Evaluation of Multicast Routing Algorithms for Real-Time Communication on High-speed Networks,” IEEE JSAC, pp. 332-345, Apr. 1997.
[22]H. Takahashi and A. Matsuyama, “An Approximate Solution for the Steiner Problem in Graphs,” Mathematical Japonica, Vol. 24, No. 6, pp. 573-577, Feb. 1980.
[23]I. Stojmenovic, A. Nayak, and J. Kuruvila, “Design guidelines for routing protocols in ad hoc and sensor networks with a realistic physical layer,” IEEE Communications Magazine, Vol. 43, No. 3, pp. 101-106, Mar. 2005.
[24]I. Stojmenovic, “Position-Based Routing in Ad Hoc Networks,” IEEE Communication Magazine, Vol. 40, No. 7, pp.128-134, July 2002.
[25]J. Broch, D. B. Johnson and D. A. Maltz, “The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks,” IETF Internet draft, draft-ietf-manet- dsr-01.txt, Dec. 1998.
[26]J. C. Navas and T. Imelinski, “Geocast-geographic Addressing and Routing,” Proceedings of ACM/IEEE MOBICOM ’97, Vol. 3, pp. 66–76, 1997.
[27]J. Hightower and G. Borriello, “Location Systems for Ubiquitous Computing,” Computer, Vol. 34, No. 8, pp. 57–66, Aug. 2001.
[28]J. J. Garcia­Luna­Aceves and E. L. Madruga, “A Multicast Routing Protocol for Ad­Hoc Networks,” Proceedings of IEEE INFOCOM''99, New York, NY, pp. 784­792, Mar. 1999.
[29]J. Kennedy, and R. Eberhart, “Particle Swarm Optimization,” Proceedings of IEEE Int''l. Conf. on Neural Networks (ICNN), Perth, Australi, Vol. IV, pp.1942-48, 1995.
[30]J. Moy., “Multicast extension to ospf,” IETF Internet Draft, Sep. 1992.
[31]J. Tillett, R. Rao, and F. Sahin, “Cluster-head identification in ad hoc sensor networks using particle swarm optimization,” IEEE International Conference on Personal Wireless Communications, pp.201-205, Dec. 2002.
[32]K. L. Wu and M. S. Yang, “Alternative c-means clustering algorithms,” Pattern Recognition 35, pp. 2267-78, 2002.
[33]K. Pahlavan, X. Li and J. P. Makela, “Indoor Geolocation Science and Technology,” IEEE Communication Magazine, pp. 112-118, Feb. 2002.
[34]K. Viswanath, K.Obraczka, and G.; Tsudik, “Exploring mesh and tree-based multicast. Routing protocols for MANETs,” IEEE Transactions on Mobile Computing, Vol. 5, No. 1, pp.28–42, Jan. 2006
[35]L. A. Latiff, A. Ali, C. C. Ooi, and N. Fisal, “Location-based Geocasting and Forwarding (LGF) Routing Protocol in Mobile Ad Hoc Network,” Proc. of the Advanced Industrial Conference on Telecommunications/Service Assurance with Partial and Intermittent Resources Conference/E-Learning on Tele- communications Workshop, pp. 536–541, July 2005
[36]L. Bajaj, M. Takai, R. Ahuja, K. Tang, R. Bagrodia, and M. Gerla, “GlomoSim: A Scalable Network Simulation Environment”, UCLA CSD Technical Report, #990027, May 1999.
[37]L. Blazevic, S. Giordano and J. Boudec, “Self-Organizing Wide-Area Routing,” Proceedings of SCI 2000/ISAS 2000, July 2000.
[38]L. Ji and M. S. Corson, “A Lightweight Adaptive Multicast Algorithm,” Proceedings of IEEE GLOBECOM''98, Sydney, Australia, pp. 1036­1042, Nov. 1998.
[39]L. Kou, G. Markowsky, and L. Berman, “A Fast Algorithm for Steiner Trees,” Acta Informatica, Vol. 15, No. 2, pp. 141-145, 1981.
[40]Maglaris et. al., “Performance Models of Statistical Multiplexing in Packet Video Communications,” IEEE Trans. on Comm., Vol. 36, No. 7, July 1988.
[41]M. Joa-Ng and I. T. Lu., “A Peer-to-Peer Zone-Based Two-Level Link State Routing for Mobile Ad Hoc Networks,” IEEE JSAC, Vol.17, No. 8, pp.1415–1425, 1999.
[42]M. Rahman, M. Mambo, A. Inomata, and E. Okamoto, “An anonymous on-demand position-based routing in mobile ad hoc networks,” International Symposium on Applications and the Internet SAINT’06, Jan. 2006.
[43]M. Spreitzer and M. Theimer, “Providing location information in a ubiquitous computing environment,” Proceedings of Symposium on Operating System Principles, pp. 270-283, Dec. 1993.
[44]M. S. Corson and S. G. Batsell, “A Reservation­Based Multicast (RBM) Routing Protocol for Mobile Networks: Initial Route Construction Phase,” ACM/Baltzer Wireless Networks, Vol. 1, No. 4, pp. 427­450, Dec. 1995.
[45]P. Sinha, R. Sivakumar, and V. Bharghavan, “MCEDAR: Multicast Core­Extraction Distributed Ad hoc Routing,” Proceedings of IEEE WCNC''99, New Orleans, LA, pp. 1313­1317, Sep. 1999.
[46]P. Winter, “Steiner Problem in networks: A Survey,” Networks, Vol. 17, No. 2, pp. 129-167, 1987.
[47]Q. Zhu, M. Parsa, and J. J. Garcia-Luna-Aceves, “A source-based algorithm for delay-constrained minimum-cost multicasting,” Proceedings of IEEE INFOCOM 95, Boston, MA, Apr. 1995.
[48]R. Bagrodia, R. Meyer, M. Takai, Y. Chen, X. Zeng, J. Martin, B. Park, H. Song, "Parsec: A Parallel Simulation Environment for Complex Systems," Computer, Vol. 31, No. 10, pp. 77-85, October 1998.
[49]R. Dube et al., “Signal Stability based Adaptive Routing (SSA) for Ad-Hoc Mobile Networks,” IEEE Personal Communication, pp. 36-45, Feb. 1997.
[50]R. Jain, A. Puri and R. Sengupta, “Geographical Routing Using Partial Information for Wireless Ad Hoc Networks,” IEEE Personal Communications, Vol. 8, No. 1, pp. 48-57, Feb. 2001.
[51]R. M. Karp, “Reducibility among Combinatorial Problems,” in Complexity of Computer Computations (R. Miller and J. Thatcher, eds.), pp. 85-103, Plenum Press, 1972.
[52]R. Sivakumar, P. Sinha, and V. Bharghavan, “CEDAR: A Core Extraction Distributed Ad Hoc Routing Algorithm,” IEEE JSAC, Vol. 17, No. 8, pp. 1454-65, Aug. 1999.
[53]R. Widyono., “The design and evaluation of routing algorithms for real-time channels,” Technical Report, ICSI TR-94-024, University of California at Berkeley International Computer Science Institute, June 1994.
[54]S. Basagni et al., “A Distance Routing Effect Algorithm for Mobility (DREAM),” Proceedings of 4th Annual ACM/IEEE Int. Conf. Mobile Computing and Networking, MOBICOM ’98, Dallas, TX, USA, pp. 76–84, 1998.
[55]S. Capkun, M. Hamdi, and J. Hubaux, “Gps-free Positioning in Mobile Ad Hoc Networks,” Proceedings of 34th Int’l. Conf. System Sciences, Hawaii, Jan. 2001.
[56]Satyabrata Chakrabarti and Amitabh Mishra, “QoS Issues in Ad Hoc Wireless Networks,” IEEE Network Magazine, pp. 142-148, Feb. 2001.
[57]Shigang Chen and Klara Nahrstedt, “Routing by Distributed Recursive Computation and Information,” Proceedings of IEEE International Conference on Performance, Computing, and Communications (IPCCC''99), pp. 393-403, Phoenix, AZ, Feb. 1999.
[58]Shigang Chen, Klara Nahrstedt, and Yuval Shavitt, “A QoS-Aware Multicast Routing Protocol,” IEEE JSAC, Vol. 18, No. 12, pp. 2580-2592, Dec. 2000.
[59]Shigang Chen and Klara Nahrstedt, “Distributed QoS Routing,” Technical Report No. UIUCDCS-R-97-2017, Department of Computer Science, University of Illinois at Urbana-Champaign, July 1997
[60]Shigang Chen and Klara Nahrstedt, “Distributed Quality-of-Service Routing in High-Speed Networks Based on Selective Probing,” Proceedings of Annual Conference on Local Area Networks (LCN''98), Boston, MA, pp. 80-89, Oct. 1998.
[61]Shigang Chen and Klara Nahrstedt, “Distributed Quality-of-Service Routing in Ad Hoc Networks,” IEEE JSAC, Vol. 17, No. 8, pp. 1488-1505, Aug. 1999.
[62]S. J. Lee, W. Su, and M. Gerla, “On­Demand Multicast Routing Protocol (ODMRP) for Ad Hoc Networks,” IETF Internet Draft, draft­ietf­manet­odmrp­ 02.txt, January 2000.
[63]S. J. Lee, W. Su, and M. Gerla, “Ad Hoc Wireless Multicast with Mobility Prediction,” Proceedings of IEEE ICCCN’99, Boston, MA, pp. 4-9, Oct. 1999.
[64]S. K. S. Gupta and P. K. Srimani, “An Adaptive Protocol for Reliable Multicast in Mobile Multi­hop Radio Networks,” Proceedings of IEEE WMCSA''99, New Orleans, LA, pp. 111­122, Feb. 1998.
[65]S. Ramanathan, “An Algorithm for Multicast Tree Generation in networks with Asymmetric Links,” Proceedings of IEEE INFOCOM, pp. 337-344, 1996.
[66]T. Imielinski and J. C. Navas, “GPS-based addressing and routing,” Tech. Rep. LCSR-TR-262, CS Dept., Rutgers University, March (updated August) 1996.
[67]T. Ozaki, J. B. Kim, and T. Suda, “Bandwidth­Efficient Multicast Routing Protocol for Ad­Hoc Networks,” Proceedings of IEEE ICCCN''99, Boston, MA, pp. 10­17, Oct. 1999.
[68]T. S. Rappaport, “Wireless Communications: Principles and Practice,” 2nd Ed., Prentice-Hall, 2002.
[69]V. C. Giruka and M. Singhal, “Angular Routing Protocol for Mobile Ad Hoc Networks,” 25th IEEE International Conference on Distributed Computing Systems Workshops, pp. 551-557, Jun. 2005.
[70]V. Rayward-Smith, “The Computation of Nearly Minimal Steiner Trees in Graphs,” International Journal of mathematical Education in Science and Technology, Vol. 14, No. 1, pp. 15-23, Feb. 1983.
[71]W. Heinzelman, A. Chandrakasan, and H. Balakrishnan, “An Application- Specific Protocol Architecture for Wireless Microsensor Networks,” IEEE Transactions on Wireless Communications, Vol. 1, No. 4, pp.660-667, Oct 2002.
[72]W. H. Liao, Y. C. Tseng, and J. P. Sheu, "GRID: A Fully Location-Aware Routing Protocol for Mobile Ad Hoc Networks", Telecommunication Systems, Vol. 18, No. 1, pp. 37-60, 2001.
[73]Y. Ko and N. H. Vaidya, “Geocasting in Mobile Ad Hoc Networks: Location­Based Multicast Algorithms,” Proceedings of IEEE WMCSA''99, New Orleans, LA, pp. 101­110, Feb. 1999.
[74]Y. Ko and N. H. Vaidya, “Location-aided Routing (LAR) in Mobile Ad Hoc Networks,” Proceedings of MOBICOM ’98, pp. 66–75, Aug. 1998.
[75]“Educational Observatory Institute GPS page,” http://www.edu- observatory.org/gps/gps.html
[76]“Iowa State University GPS page,” http://www.cnde.iastate.edu/gps.html