摘要
Ad Hoc网络自出现以来就备受关注,已成学术界和工业界在通信领域的重要研究对象。Ad Hoc网络既没固定结构也没中心节点,是一种动态自适应网络。由于无线传输范围有限,使Ad Hoc网络常以“多跳”方式路由,因此也被称为“多跳”网络。Ad Hoc网络具有组网快速便捷、设备便携灵活等特点,不管在军用还是民用领域都有着广阔的应用前景。
在Ad Hoc网络中,某些应用需要主机间通过相互协作共同完成一项任务,而组播技术恰好可以提供支持。但静态网络中的组播协议不能很好的适应AdHoc网络,原因在于网络连通性的变化会破坏分组转发结构,而协议不具有快速修复功能。此外,协议创建转发结构时还需要全网的链路状态或距离矢量信息。当在网络规模较大尤其带宽有限时,这些信息的收集极易导致网络拥塞。因此,Ad Hoc网络中的组播协议研究具有重要意义。
近年,学者研究发现将“跳数”作为路由标准,并不能很好的反应Ad Hoc网络特征。因为“跳数”忽略了无线链路的质量,如链路的信噪比,稳定性等。本文则提出了基于链路稳定性的组播路由协议。稳定的路径具有较高的分组投递率,从而降低了分组重复发送次数,并且链路维持时间长,减少了断路发生,降低了协议的维护开销。本文根据无线信号的传播特点,提出了基于信号接收功率预估链路稳定性的方法。通过对节点分组信号接收功率的实时监测,用概率统计的方法估测节点间距离变化,从而得到链路的稳定性评价。此方法虽然比采用GPS定位预测节点移动性的精确度低,但要优于仅仅通过邻居变化来预测的方法。由于组播树结构更易受不稳定链路的影响,因此基于此方法本文提出了组播路由协议。设计了组成员加入和离开机制,以及组播树的创建和维护方法。协议的机制简单,能够优先选择稳定路径,减少路由环路的发生,并且与稳定性评价机制相结合,对即将断开的链路具有一定的预测性。最后,通过仿真实验检验协议,并从多个侧面来分析协议的性能。
机会路由也是新近提出的路由方法,它与传统路由最大的区别是分组转发时的不确定性。在传统路由中分组是沿已建的路径进行转发,具有确定性的下一跳。而机会路由则利用了无线环境下通信所具有的广播特性,分组的下一跳不指定某一邻居,只要有可到达的邻居接收即可。这种方法减少了分组的重发次数,也提高了网络的投递率。国际上机会路由在组播条件下的研究较少,本文则探讨了组播条件下的机会路由方法,并设计了机会组播路由协议。本文提出的机会组播路由协议也是基于树结构,但分组的转发并不是沿组播树进行,而是将其作为一辅助结构。通过组播树来约束分组在网络中的转发,以保证每个成员节点都能接收到分组,并且避免分组被无休止的路由。本文也设计了组播条件下分组的机会转发机制。该机制通过协调邻居节点间的操作,避免分组碰撞,保证分组能路由到目的节点,并且还保持组播自身的优点。仿真实验的结果表明,机会组播路由比传统路由在分组投递率方面具有显著优势,并且协议有较高的效率。
本文选择的仿真工具为OPNET,对其架构、仿真机制和无线管道做了详细的介绍。其中无线管道是对无线信道的仿真,也是进行无线仿真的基础。
文章的最后,总结说明了本文的主要内容和下一步工作,以及对Ad Hoc网络组播相关研究内容的展望。
Since it is known, Ad Hoc network has received great concern, and become a communication research object of academia and industry. It is a dynamically reconfigurable wireless network with no fixed infrastructure or central administration. Due to the limited radio propagation range of wireless devices, its routes are often "multihop", so it is also called "multihop" network. Because it is configured quickly and its devices are portable and flexible, Ad Hoc network has broad application prospects whether in military or civilian areas.
In a typical ad hoc environment, network hosts work in groups to carry out a given task, and multicast can provide support for these applications. However, multicast protocols used in static networks do not perform well in ad hoc networks, because the dynamic of ad hoc networks may undermine the multicast structure, and the protocols don't have quick fixes ability. Furthermore, multicast trees usually require global information of link state or distance vector of the network, however collect these information may cause network congestion especially in large and limited bandwidth network. So, the research of multicast protocol in Ad hoc networks has a great value.
Recently, scholars found that use the "hop count" as the routing path selection-criteria doesn't well adapt to Ad Hoc Networks. Because using "hop count" ignores the quality of the wireless link, such as the signal to noise ratio and stability of the link. So in this paper, a multicast protocol is proposed based on link stability. The stability link has higher packet delivery ratio, thereby reducing the number of packet retransmission, and has a long maintenance time, thereby reducing the happenes of link breakdown and the maintenance overhead of the protocol. According to wireless signal transmission characteristic, an estimate link stability method based on signal received power is proposed in this paper. Through real-time monitor the received power, the mothod estimates the changes of the distance between two nodes, using probabilistic statistical method. Although this method is less accurate than using GPS, it is better than just by neighbor changes to predict node mobility. As multicast tree is more vulnerable to the impact of instability link, this paper also proposed a multicast protocol based on this method. It has designed the join and leave mechanism of group member, also inluding the multicast tree creation and maintance mothod. The protocol has simple mechanism, can choose stable path as route and reduce the occurance of routing loops, and to be with the stability evaluation mechanism, it can predit the link which will be broken in a moment. Finally, we test the protocol through simulation, and analyze its performance from more than one side.
The opportunistic routing is a newly proposed routing method, and the difference with the traditional routing is delivering a packet in an uncertaint path. In traditional routing, the packet's forward path is built before the transmission. However, the opportunistic routing takes the broadcast of wireless environment as an advantage, do not certain a specific next hop neighbor, but as long as a neighbor received the packet, the routing can continue. This approach reduces the number of packet retransmission, and improves the network packet delivery ratio. While the study of opportunistic routing on multicast is less, this paper will explore the menthod of opportunistic routing on multicast, and design an opportunistic multicast routing protocol. This protocol is based on tree structure, but the packet is not forwarded along this tree which is just as a support structure. The protocol restricts the packet forwording through the multicast tree, to ensure that each group member can receive the packet and avoid endless packets routing. We also design packets opportunistic forwording mechanism on multicast in this paper. The mechanism coordinates the operation of neighbor node to avoid packet collisions, ensure that the packet can be routed to the destination node, and also has the advatage of mulitcast. Simulation results show that the opportunistic multicast routing has a significant advantage in packet delivery ratio than traditional multicast routing, also has a higher efficiency.
This paper uses OPNET as a simulation tool, described the structure, simulation mechanisms and wireless channels of OPNET in detail. Wireless channel is a radio channel simulation, but it is the basis for wireless simulation.
In the end of this paper, there are some summarizes of my research, next steps of my work, and prospects of reasearch on ad Hoc network multicast.
引文
[1].D.A. Beyer. Accomplishments of the DARPA Survivable Adaptive Networks SURAN Program[C]. in Proceedings of the IEEE MILCOM Conference.1990.
[2].L. M. Barry, R. J. Robert, and R. Ambatipudisastry. Goals and challenges of the DARPA GloMo program[J]. IEEE Personal Communication,1996.3(6):pp.34-43.
[3].于宏毅.无线移动自组织网[M].2005,北京:人民邮电出版社.
[4].郑少仁,王海涛.Ad Hoc网络技术[M].2005,北京:人民邮电出版社.
[5].P. Ramachandran. Source Authentication for Multicast in Mobile Ad Hoc Networks[D].2003, University of Maryland.
[6].L. Bao and J. J. Garcia-Luna-Aceves. Transmission scheduling in Ad Hoc networks with directional antennas[C]. in Proc. ACM English Annual International Conference on Mobile Computing and Networking 2002.
[7].肖文红.无线传感网络的研究[D].2006,复旦大学:上海.
[8].S. Deering and D. Cheriton. Multicast Routing in Datagram Internetworks and Extended LANs[J]. ACM Transactions on Computer Systems,1990.8(2):pp.85-110. [9].T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms[M]. 1997:MIT.
[10].P. Winter. Steiner Problem in Network:a Survey. Networks[J].1987.17(2):pp. 129-167.
[11].F. K. H. Wang. Steiner Tree Problem[J]. Networks,1992.15(1):pp.55-89.
[12].M. Imase. Dynamic Steiner Tree Problem[J]. SIAM J Discrete Mathematics, 1991.4(3):pp.369-384.
[13].J.B. Kruskal. On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem[C]. in Proceedings of the American Mathematical Society.1956.
[14].R. Gallager, P. Humblet, and P. Spira. A Distributed Algorithm for Minimum-weight Spanning Trees[J]. ACM Transactions on Programming Languages and Systems,1983.5(1):pp.66-77.
[15].L. Kou, G Markowsky, and L. Berman. A Fast Algorithm for Steiner Trees[J]. Acta Informatica,1981.15(2):pp.141-145.
[16].S. Vob. Steiner's Problem in Graphs:Heuristic Methods[J]. Discrete Applied Mathematics,1992.40(1):pp.43-72.
[17].H. Takahashi and A. Matsuyama. An Approximate Solution for the Steiner Problem in Grphs. Math. Japonica[J].1980.24(6):pp.573-577.
[18].V.J. Rayward-Smith. On Finding Steiner Vertices[J]. Networks,1986(16):pp. 283-294.
[19].Q Zhu, M Parsa, and J Garcia-Luna-Aceves. A Source-based Algorithm for Delay-constrained Minimum-cost Multicasting[C]. in In Proceedings of IEEE INFOCOM'95.1995.
[20].V. P. Kompella, C. Pasquale, and G C. Polyzo. Multicast Routing for Multimedia Communication[J]. IEEE/ACM Transactions on Networking,1993.1(3):pp.286-292.
[21].B. K. Haberman and G Rouskas. Cost, Delay and Delay Variation Conscious Multicast Routing[R].1997:North Carolina State University.
[22].V. P. Kompella, J. C. Pasquale, and G C. Polyzo. Two Distributed Algorithms for Multicating Multimedia Information[C]. in In Proceeding of ICCCN'93.1993.
[23].X. Jia. A Distributed Algorithm of Delay-bounded Multicast Routing for Multimedia Applications in Wide Area Networks[J]. IEEE/ACM Transactions on Networking,1998.6(6):pp.828-837.
[24].X. Chen and J. Wu. Multicasting techniques in mobile ad-hoc networks[M], in The Handbook of Ad-hoc Wireless Networks.2003. p.25-40.
[25].A. Shaikh, J. Rexford, and K. G Shin. Evaluating the impact of stale link state on quality-of-service routing[J]. IEEE/ACM Trans. Networking,2001.9(2):pp. 162-176.
[26].J.-S. Chou, C.-H. Lin, and C.-H. Chiu. An identity-based scheme for ad-hoc network secure routing protocol from pairing[J]. WSEAS Trans. Computers,2006. 5(6):pp.1214-1221.
[27].C. Liu, Y. Shu, and Y. Zhou. A comparison of DSR, MSR and BSR in wireless ad-hoc networks[J]. SPIE,2005.6011:pp.601-610.
[28].M. K. Marina and S. R. Das. Ad-hoc on-demand multi-path distance vector routing[J]. Wireless Commun. Mobile Computing,2006.6(7):pp.969-988.
[29].C. W. Wu and Y C. Tay. AMRIS:A multicast protocol for ad-hoc wireless networks[C]. in in Proc. IEEE MILCOM.1999.
[30].E. M. Royer and C. E. Perkins. Multicast operation of the ad-hoc ondemand distance vector routing protocol[C]. in Proc. ACM MOBICOM.1999.
[31].K. Chen and K. Nahrstedt. Effective location-guided tree construction algorithms for small group multicast in MANET[C]. in Proc. IEEE INFOCOM.2002.
[32].M. Gerla, S. J. Lee, and W. Su. On-demand multicast routing protocol (ODMRP) for ad-hoc networks[S].2000.
[33].J. J. Garcia-Luna-Aceves and E. L. Madruga. Core-assisted mesh protocol[J]. IEEE J. Select. Areas Commun,1999.17(8):pp.1380-1394.
[34].J. Xie, R. Rajesh, and A. McAuley. AMRoute:Ad-hoc multicast routing protocol[J]. Mobile Networks and Applications, Multipoint Communication in Wireless Mobile Networks,2002.7(6):pp.429-439.
[35].L. Ji and M. S. Corson. Differential destination multicast-A MANET multicast routing protocol for small groups[C]. in Proc. IEEE INFOCOM.2001.
[36].L. Junhai, Y Danxia, X. Liu, et al. A Survey of Multicast Routing Protocols for MANET[J]. IEEE COMMUNICATIONS SURVEYS & TUTORIALS,2009.11(1): pp.78-91.
[37].C. M. Cordeiro, H. Gossain, and D. P. Agrawal. Multicast over wireless mobile ad hoc networks present and future directions[J]. IEEE Network,2003:pp.52-59.
[38].L. Canourgues, J. Lephay, and Soyer. STAMP:Shared-tree adhoc multicast protocol[J]. in in Proc. IEEE MILCOM.2006.
[39].B. Kaliaperumal, A. Ebenezer, and Jeyakumar. Adaptive core-based scalable multicasting networks[in in Proc. IEEE INDICON.2005.
[40].H. Dhillon and H. Q. Ngo. CQMP:A mesh-based multicast routing protocol with consolidated query packets[C]. in Proc. IEEE WCNC.2005.
[41].Y. O. Soon, J.-S. Park, and M. Gerla. E-ODMRP:Enhanced ODMRP with motion adaptive refresh[C]. in Proc. ISWCS.2005.
[42].E. R. Inn Inn and W. K. Seah. Distributed steiner-like multicast path setup for mesh-based multicast routing in ad-hoc networks[J]. IEEE TIME:pp.192-197.
[43].J. Biswas, M. Barai, and S. K. Nandy. Efficient hybrid multicast routing protocol for ad-hoc wireless networks[J]. IEEE LCN,2004:pp.180-187.
[44].L. Layuan and L. Chunlin. A QoS multicast routing protocol for clustering mobile ad-hoc networks[J]. Computer Communications.30(7):pp.1-13.
[45].L. Jiageng, D. Cordes, and J. Zhang. Power-aware routing protocols in ad-hoc wireless networks[J]. IEEE Wireless Commun,2005.12(6):pp.69-81.
[46].W. Cheng, C. Wen, and K. Feng. Power-controlled hybrid multicast routing protocol for mobile ad-hoc networks[C]. in Proc. IEEE VTC.2006.
[47].M. X. Cheng and J. Sun. Energy-efficient broadcast and multicast routing in multi-hop ad-hoc wireless networks[J]. Wireless Communications and Mobile Computing,2006.6(2):pp.213-223.
[48].A. Davidian. Network coding:An overview[J]. Institute for Communications Engineering (LNT),2005.13(7):pp.1-19.
[49].D. S. Lun and A. Ebad. Network coding for wireless applications[C]. in Proc. SPIE.2005.
[50].Y. C. Wu, A. Philip, and S.-Y Kung. Minimum-energy multicast in mobile ad-hoc networks using network coding[J]. IEEE Trans. Commun,2005.53(11):pp. 1906-1918.
[51].B. Sun and L. Li. Reliable adaptive multicast protocol in wireless adhoc networks[J]. J. Systems Engineering Electronics,2006.17(1):pp.187-192.
[52].N.-C. Wang and S.-W. Chang. A reliable on-demand routing protocol for mobile ad-hoc networks with mobility prediction[J]. Computer Communications,2005.29(1): pp.123-135.
[53].龙华.OPNET Modeler与计算机网络仿真[M].2006,西安:西安电子科技大学出版社.
[54].C-K. Toh. Associativity-Based Routing for Ad hoc Mobile Networks[J]. IEEE Personal Communications,1997.4(2):pp.103-139.
[55].R. Dube, C. D. Rais, K-Y. Wang, et al. Signal Stability based Adaptive Routing for Ad hoc Wireless Networks[J]. IEEE Personal Communications,1997.4(1):pp. 36-45.
[56].P. Basu, N. Khan, and T.D.C. Little. A mobility based metric for clustering in mobile ad hoc networks[C]. in In proceedings of IEEE 2001.2001.
[57].W. Su, S-J. Lee, and M. Gerla. Mobility Prediction and Routing in Ad Hoc Wireless Networks [J]. International Journal of Network Management,2001.11(1): pp.3-30.
[58].M.S. Corson and J. Macker. Mobile Ad hoc Networking (MANET):Routing Protocol Performance Issues and Evaluation Considerations[R].1999, Request For Comments 2501, Internet Engineering Task Force.
[59].S. Biswas and R. Morris. ExOR:Opportunistic multi-hop routing for wireless networks[C]. in In Proceedigs of ACM SIGCOMM.2005.
[60].S. Chachulski. Trading Structure for Randomness in Wireless Opportunistic Routing[C]. in Proc. ACM SIGCOMM.2007.
[61].M. S. Nassr. Scalable and Reliable Sensor Network Routing:Performance Study from Field Deployment[C]. in Proc. IEEE INFOCOM.2007.
[62].S. Jain and S. Das. Exploiting Path Diversity in the Link Layer in Wireless Ad Hoc Networks[C]. in Proc. IEEE Wo WMoM.2005.
[63].M. Zorzi and R. R. Rao. Geographic Random Forwarding (GeRaF) for Ad Hoc and Sensor Networks:Multihop Performance [J]. IEEE Trans. Mobile Comp,2003. 2(4):pp.337-348.
[64].B. Zhao, R. I. Seshadri, and M. C. Valenti. Geographic Random Forwarding with Hybrid-ARQ for Ad Hoc Networks with Rapid Sleep Cycles[C]. in Proc. IEEE GLOBECOM.2004.
[65].Y. Yan. Practical Coding-Aware Opportunistic Routing Mechanism for Wireless Mesh Networks[C]. in Proc. IEEE ICC 2008.2008.
[66].S.-Y. R. Li, R. W Yeung, and N. Cai. Linear network coding[J]. IEEE Trans, on Information Theory,2003.
[67].H. Liu and B. Zhang. Opportunistic Routing for Wireless Ad Hoc and Sensor Networks:Present and Future Directions [J]. IEEE Communications Magazine,2009: pp.103-109.
[68].D. Ganesan, B. Krishnamachari, A. Woo, et al. Complex behavior at scale:An experimental study of low-power wireless sensor networks[R].2002, UCLA CS Department.
[69].D. De Couto, D. Aguayo, J. Bicket, et al. A high-throughput path metric for multi-hop wireless routing[C]. in In Proc. ACM/IEEE MobiCom.2003.