臺灣博碩士論文加值系統

行動隨意網路(MANET)是由一群不需要透過基地台做溝通的行動節點所組成。由於節點的高移動性，將會使得在行動隨意網路(MANET)上的網路拓撲(Network Topology)改變的非常快，因此要找到可以用來傳輸資料的路徑是更加的困難。節點移動的特性也使建立的路徑容易斷裂，造成整體的網路拓撲相當的不穩定。除此之外，行動節點都會受到電量的限制，如何有效的利用電量也是一個重要的議題。為使群播繞路協定能夠有較高的穩定度，在本篇論文提出一在行動隨意網路中具行動預測能力之電量感知服務品質群播之繞路協定。為了能找到可靠度與穩定度高的路徑，在路徑搜尋(Route Discovery)的過程中，當收到路經需求(RREQ)封包時會先利用電量感知的模式求出傳送資料封包時所需消耗的電量。若節點所剩餘的電量足夠做傳輸的動作，再利用全球定位系統(GPS)求出二節點間的鏈結結束時間(Link Expiration Time)，由目的節點(Destination Node)選擇出整條路徑中最小的鏈結結束時間(Link Expiration Time)當作傳輸路徑的路徑結束時間(Route Expiration Time)，目的節點會收集多條可用路徑，並由多條路徑中決定出擁有最長路徑唯持時間的作為與來源節點間的傳輸路徑。我們以來源節點(Source Node)作為群播樹(Multicast Tree)的根(Root)節點，所有的目的節點(Destination Node)作為葉(Leaf)節點，每個目的節點與來源節點間皆為單一路徑(Unicast)。接著我們整合來源節點到所有目的節點間的傳輸路徑來建立一個更穩定的群播樹(Multicast Tree)，之後將利用此群播樹(Multicast Tree)達到資料的傳輸。最後我們將透過模擬實驗來證實所提出的方法效能上確實可以改進之前的研究方法。

A mobile ad hoc network (MANET) is a dynamically reconfigurable wireless network with no fixed infrastructure. Due to the high mobility of nodes, the network topology of MANETs changes very fast, making it more difficult to find the routes that message packets use. Furthermore, the mobile nodes have limited battery power, it is very important to use energy efficiently. In this thesis, we propose a power aware QoS multicast routing protocol (PQMRP) with mobility prediction for MANETs. In order to select a subset of paths to provide increased stability and reliability of routes, in routing discovery, each node receives the RREQ packet and uses the power aware model to get the power consumption of data packets transmitting in advance. If the node has enough remain power to transmits data packets, and then use global positioning system (GPS) to get the location information (i.e. position, velocity and direction) of the mobile nodes and utilize this information to calculate the link expiration time (LET) between two connected mobile nodes. During route discovery, each destination node selects the routing path with the smallest link expiration time (LET) and uses this smallest link expiration time as the route expiration time (RET). The destination nodes collect several feasible routes and then select the path with the longest route expiration time (RET) as the primary routing path. Then the source node uses these routes between the source node and each destination node to create a multicast tree. In the multicast tree, the source node will be the root node and the destination nodes will be the leaf nodes. Simulation results show that the proposed PQMRP outperforms MAODV.

Contents
Chapter 1 Introduction 1
1.1 Wireless Networks 1
1.1.1 The Infrastructure networks 1
1.1.2 Mobile Ad Hoc Networks 2
1.2 Design Concept 3
1.3 Thesis Organization 4
Chapter 2 Related Works 5
2.1 Multicast routing in Wireless Networks 5
2.1.1 The Basic Components of Multicasting 5
2.1.2 The Multicasting Routing Protocols of Mobile Ad Hoc Networks (MANET) 6
2.2 The Power-Aware Routing Protocols 17
2.3 The QoS Issue in Mobile Ad Hoc Networks 20
Chapter 3 Preliminaries 21
3.1 Global Positioning System (GPS) 21
3.2 Mobility Prediction Mechanisms 21
3.3 Power Aware Model 22
3.4 Multicast Ad Hoc on Demand Distance Vector (MAODV) Routing Protocol 24
Chapter 4 The Power-Aware QoS Multicast Routing Protocol (PQMRP) with Mobility Prediction 26
4.1 Tables for Routing 26
4.2 Route Discovery Process 27
4.3 Route Maintenance Process 37
4.3.1 Multicast Join Operation 37
4.3.2 Node Pruning Operation 38
4.3.3 Link Broken Maintenance 39
Chapter 5 Experimental Results 47
5.1 The Simulation Environment 47
5.2 Performance Analysis 49
5.2.1 Packet Delivery Ratio 49
5.2.2 End-to-end delay 51
5.2.3 Control overhead 53
5.2.4 Route rediscovery frequency 55
References 59

List of Figures
Fig. 1.1. An example of infrastructure networks. 2
Fig. 1.2. An example of mobile ad hoc networks (MANET). 3
Fig. 2.1. Flow of data and packets duplication in multicasting. 6
Fig. 2.2. AMRoute virtual multicast tree. 8
Fig. 2.3. AMRIS packet forwarding. 9
Fig. 2.4. Dissemination of group hellos in an MANET. 10
Fig. 2.5. Tree formation in ROMANT. 11
Fig. 2.6. Mesh creation in ODMRP. (a) Join-Query packet propagation. (b) Multicast mesh. 14
Fig. 2.7. Route discovery in MTPR. 18
Fig. 3.1. Power first order radio model. 23
Fig. 3.2. Route discovery of the MAODV protocol. 25
Fig. 4.1. On-demand process for multicast group management. 27
Fig. 4.2. RREQ packet format. 28
Fig. 4.3. RREP packet format. 29
Fig. 4.4. Beacon packet format. 30
Fig. 4.5. Routing process. (a) The route discovery process. (b) The route relay process. (c) The reliable multicast tree. 36
Fig. 4.6. Multicast join operation. (a) Join request packet propagation. (b) Join reply sent back to source. (c) Multicast tree branch addition. 38
Fig. 4.7. Node pruning operation. (a) Quit request packet propagation. (b) Multicast tree after pruning. 39
Fig. 4.8. RREQ_R packet format. 41
Fig. 4.9. RREP_R packet format. 42
Fig. 4.10. Repair of a broken tree link. (a) Link break (b) Repaired multicast tree. 46
Fig. 5.1. Packet delivery ratio vs. mobility speed with 50 mobile nodes. 50
Fig. 5.2. Packet delivery ratio vs. mobile nodes with a mobility speed of 20m/sec. 50
Fig. 5.3. End-to-end delay vs. mobility speed with 50 mobile nodes. 52
Fig. 5.4. End-to-end delay vs. mobile nodes with a mobility speed of 20m/sec. 52
Fig. 5.5. Control overhead vs. mobility speed with 50 mobile nodes. 54
Fig. 5.6. Control overhead vs. mobile nodes with a mobility speed of 20m/sec. 54
Fig. 5.7. Route rediscovery frequency vs. mobility speed with 50 mobile nodes. 56
Fig. 5.8. Route rediscovery frequency vs. mobile nodes with a mobility speed of 20m/sec. 56

List of Tables
Table 2.1: The comparison of multicast routing protocols. 16
Table 2.2: The comparison among tree-based protocol, mesh-based protocol, and hybrid protocol. 17
Table 2.3: The comparison of power-aware routing protocols. 20
Table 4.1: Parameters used in the simulations. 48

[1]B. An and S. Papavassiliou, "A Mobility-Based Hybrid Multicast Routing in Mobile Ad Hoc Wireless Network," Proceeding of IEEE Military Communication Conference (MILCOM 2001), pp. 316-320, October 28-31, 2001.
[2]A. Ballaradie, J. Crowcroft, and P. Francis, "Core Based Tree (CBT) – An Architecture for Scalable Inter-Domain Routing Protocol," Proceeding of the ACM Conference on the Special Interest Group on Data Communications (SIGCOMM), San Francisco, CA, USA, pp. 85-89, October 1993.
[3]E. Bommaiah, M. Liu, A. McAuley, and R. Talpade, "AMRoute: Ad Hoc Multicast Routing Protocol," Internet draft, draft-talpade-manet-amroute-00.txt, August 1998.
[4]K. L. Calvert and E. W. Zegura, "Core selection methods for multicast routing," Technical report, GIT-CC-95/15, 1995.
[5]C. C. Chiang, M. Gerla, and L. Zhang, "Forwarding Group Multicast Protocol (FGMP) for Multihop, Mobile Wireless Networks," ACMBaltzer Journal of Cluster Computing: Special Issue on Mobile Computing, Vol. 1, No. 2, pp. 187-196, December 1998.
[6]S. K. Das, B. S. Manoj, and C. S. R Murthy, "A Dynamic Core Based Multicast Routing Protocol for Ad hoc Wireless Network," Proceeding of the Third ACM International Symposium on Mobile Ad Hoc Networking and Computing, Lausanne, Switzerland, pp. 24-35, June 9-11, 2002.
[7]V. Devarapalli and D. Sidhu, "MZR: A Multicast Protocol for Mobile Ad Hoc Networks," IETF MANET Working Group Internet Draft, November 2000.
[8]G. Dommety and R. Jain, "Potential Networking Applications of Global Positioning System (GPS)," Technical Report TR-24, Computer Science Department, The Ohio State University, April 1996.
[9]J. J. Garcia-Luna-Aceves and E. L. Madruga, "The Core-Assisted Mesh Protocol," IEEE Journal on Selected Areas in Communications, pp. 1380-1394, August 1999.
[10]T. Gopalsamy, M. Singhal, D. Panda, and P. Sadayappan, "A Reliable Multicast Algorithm for Mobile Ad Hoc Networks," Proceedings of the 2002 IEEE International Conference on Distributed Computing Systems, pp. 563-570, July 2-5, 2002.
[11]C. Gui and P. Mohapatra, "Efficient Overlay Multicast for Mobile Ad Hoc Networks," Proceeding of the Conference on Wireless Communication and Networking, Vol. 2, pp. 1118-1123, March 16-20, 2003.
[12]W. R. Heinzelman, A. Chandrakasan and H. Baladrishnan, "Energy-efficient routing protocols for microsensor networks," Proceedings of the 33rd Hawaii International Conference on System Sciences, Vol. 8, pp. 1-10, January 2000.
[13]E. D. Kaplan. "Understanding GPS: Principles and Applications," Artech Hourse, Boston, MA, 1996.
[14]D. Kin, J. J. Garcia-Luna-Aceves, and K. Obraczka, "Power-Aware Routing Based on The Energy Drain Rate for Mobile Ad Hoc Networks." Proceedings of the IEEE International Conference on Computer Communications and Networks, pp. 565-569, October 14-16, 2002.
[15]S. J. Lee, M. Gerla, and C. C. Chiang, "On Demand Multicast Routing Protocol," Proceedings of the 1999 IEEE Conference on Wireless Communications and Networking, New Orleans, LA, USA, pp. 1298-1302, September 21-24, 1999.
[16]S. Lee and C. Kim, "Neighbor Supporting Ad Hoc Multicast Routing Protocol," Proceedings of the first ACM international symposium on Mobile and ad hoc networking computing, Boston, Massachusetts, USA, pp. 37-44, October 2000.
[17]J. P. Macker and M. S. Corson, "Mobile Ad Hoc Networking and the IETF," ACM SIGMOBILE Mobile Computing and Communications Reviews, Vol. 2, No. 2, pp. 9-14, January 1998.
[18]C. E. Perkins and E. Royer, "Ad-Hoc On-Demand Distance Vector Routing," Proceedings of the Second IEEE Workshop on Mobile Computing System and Application, New Orleans, LA, USA, pp. 90-100, February 1999.
[19]T. S. Rappaport, Wireless Communications: Principles and Practice, Prentice-Hall, Upper Saddle River, NJ, 1995.
[20]E. M. Royer and C. E. Perkins, “Multicast Operation of the Ad Hoc On-Demand Distance Vector Routing Protocol,” Proceedings of the 5th ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom), Seattle, WA, USA, pp. 207-218, August 15-20, 1999.
[21]K. Scott and N. Banmbos, "Routing and Channel Assignment for Low Power Transmission in PCS," Proceedings of the International Fifth Conference on Universal Personal communications, Cambridge, MA, England, Vol. 2, pp. 368-369, September 29-October 2, 1996.
[22]S. Singh, M. Woo, and C. S. Raghavendra, "Power-Aware with Routing in Mobile Ad Hoc Networks," Proceedings of the 4th Annual ACM/IEEE International Conference on Mobile Computing and Networking, Dallas, Texas, USA, pp. 181-190, October 25-30, 1998.
[23]R. Sivakumar, P. Sinha, and V. Bharghavan, "CEDAR: A Core Extraction Distributed Ad Hoc Routing Algorithm," Proceedings of the Eighteenth Annual Joint Conference on IEEE Computer and Communications Societies, New York, NY, USA, Vol. 1, pp. 202-209, March 21-25, 1999.
[24]P. Sinha, R. Sivakumar, and V. Bharghavan. "MCEDAR: Multicast Core Extraction Distributed Ad-Hoc Routing," Proceedings of the Wireless Communications and Networking Conference, New Orleans, LA, USA, pp. 1313-1317, September 21-24, 1999.
[25]C. K. Toh, "Maximum Battery Life Routing to Support Ubiquitous Mobile Computing in Wireless Ad Hoc Networks," IEEE Communications Magazine, Vol. 39, No. 6, pp. 138-147, June 2001.
[26]C. K. Toh, H. Cobb, and D. A. Scott, "Performance Evaluation of Battery-Life-Aware Routing Schemes for Wireless Ad Hoc Networks," Proceedings of IEEE International Conference on Communications, Helsinki, Finland, pp. 2824-2829, June 11-14, 2001.
[27]R. Vaishampayan and J. J. Garcia-Luna-Aceves, "Robust Tree-based Multicasting in Ad Hoc Networks" Proceedings of the 2004 IEEE International Conference on Performance, Computing, and Communications, pp. 647-652, 2004.
[28]C. W. Wu, Y. C. Tay, and C. K. Toh, "Ad Hoc Multicast Routing Protocol Utilizing Increasing ID-Numbers (AMRIS) Functional Specification," Internet draft IETF, November 1998.
[29]X. Zhang and Jacob. L, "Multicast Zone Routing Protocol in Mobile Ad Hoc Wireless Networks," Proceedings of 28th Annual IEEE International Conference on Local Computer Networks, pp. 150-159, October 20-24, 2003.