基于群组移动模型的Ad Hoc网络路由算法研究
|
摘要
移动Ad Hoc网络(MANET)是一种自组织的多跳无线网络，网络中每个节点可以自由移动，通过共享的无线信道进行通信，而无须任何固定设施。各个节点互为中继节点，从而可以与超出自身通信距离以外的节点进行通信。它主要应用在军事通信、抢险救灾和传感器网络等领域，因此引起军事界和学术界的广泛关注。
Ad Hoc网络在战场指挥通信等领域有着广泛的应用前景，其中最为典型的例子就是战术互联网(Tactical Internet，TI)。但在目前战术互联网的研究中，无论是分簇还是路由协议等都没有突出战术环境背景和移动特点这些关键因素，把战术互联网等同于普通的Ad Hoc网络。本文在阐述Ad Hoc网络结构的基础上，着重就路由协议和分簇路由算法进行了研究，并在此基础上提出了一种适用于战术网络环境背景特点的分簇算法和改进ZM-AODV分簇路由协议。该算法充分考虑了战术网络群组移动性和节点性能差异等特点，采用分级结构把网络中不同区域的节点划分为不同的簇，选择通信能力强的节点担任簇首，簇内使用及时的HELLO信息担任主动路由，在簇间使用按需的AODV路由。
为了验证协议的性能，我们在OPNET仿真平台上对ZM-AODV和AODV协议进行了仿真对比。通过对在不同网络负载和不同节点速度情况下的仿真试验数据分析，ZM-AODV协议均表现出良好的性能。在端到端平均时延和归一化控制开销方面，均优于AODV协议。簇内的HELLO信息缩短了路由建立时间，分簇结构降低了拓扑的变化，减少了拓扑控制开销，这些措施使战术网络的性能得到提高。
Mobile Ad Hoc network (MANET) is a self-organizing and multi-hop network structure, in which nodes share common wireless channel and can move freely without the aid of a fixed networking infrastructure. Each routing terminal acts as a router that forwards data packets to all the other nodes in the network, thereby extending the range and the coverage of communications links among mobile nodes. So it can be applied to modern battle field, disaster rescue, sensor networks and other environments, therefore has drawn wide attention from the military and the academic.
Ad Hoc network is used widely for Command and Control in the battlefield, and the representative example of Ad Hoc network is Tactical Internet (TI). However, many research about TI, whatever clustering and routing protocols simulation, regard TI as a normal Ad Hoc network ignoring the effect of battlefield factors and the mode of move factors. The aim of our research is to present a new cluster routing protocol and simulation solution which is fit for the feature of TI. The proposed routing protocol, called ZM-AODV, takes network's mobility and node's diversity into account. Hiberarchy is adopted to divide the nodes in different regions into different clusters, the more powerful node is chosen to be the cluster. The nodes in cluster use timely HELLO message to establish route and the communication between clusters use AODV.
For the sake of evaluating the performance of protocol, we simulate the ZM-AODV and AODV protocol in different scenes under OPNET platform. Protocol is simulated in different network's load and node's speed. The results show that ZM-AODV has a better performance than AODV, especially in End-To-End delay and routing overhead aspects. Due to the HELLO message in cluster can reduce the time of route establishment and the cluster structure can decrease the change of topology, the performance of TI can be improved obviously.
Ad Hoc网络在战场指挥通信等领域有着广泛的应用前景，其中最为典型的例子就是战术互联网(Tactical Internet，TI)。但在目前战术互联网的研究中，无论是分簇还是路由协议等都没有突出战术环境背景和移动特点这些关键因素，把战术互联网等同于普通的Ad Hoc网络。本文在阐述Ad Hoc网络结构的基础上，着重就路由协议和分簇路由算法进行了研究，并在此基础上提出了一种适用于战术网络环境背景特点的分簇算法和改进ZM-AODV分簇路由协议。该算法充分考虑了战术网络群组移动性和节点性能差异等特点，采用分级结构把网络中不同区域的节点划分为不同的簇，选择通信能力强的节点担任簇首，簇内使用及时的HELLO信息担任主动路由，在簇间使用按需的AODV路由。
为了验证协议的性能，我们在OPNET仿真平台上对ZM-AODV和AODV协议进行了仿真对比。通过对在不同网络负载和不同节点速度情况下的仿真试验数据分析，ZM-AODV协议均表现出良好的性能。在端到端平均时延和归一化控制开销方面，均优于AODV协议。簇内的HELLO信息缩短了路由建立时间，分簇结构降低了拓扑的变化，减少了拓扑控制开销，这些措施使战术网络的性能得到提高。
Mobile Ad Hoc network (MANET) is a self-organizing and multi-hop network structure, in which nodes share common wireless channel and can move freely without the aid of a fixed networking infrastructure. Each routing terminal acts as a router that forwards data packets to all the other nodes in the network, thereby extending the range and the coverage of communications links among mobile nodes. So it can be applied to modern battle field, disaster rescue, sensor networks and other environments, therefore has drawn wide attention from the military and the academic.
Ad Hoc network is used widely for Command and Control in the battlefield, and the representative example of Ad Hoc network is Tactical Internet (TI). However, many research about TI, whatever clustering and routing protocols simulation, regard TI as a normal Ad Hoc network ignoring the effect of battlefield factors and the mode of move factors. The aim of our research is to present a new cluster routing protocol and simulation solution which is fit for the feature of TI. The proposed routing protocol, called ZM-AODV, takes network's mobility and node's diversity into account. Hiberarchy is adopted to divide the nodes in different regions into different clusters, the more powerful node is chosen to be the cluster. The nodes in cluster use timely HELLO message to establish route and the communication between clusters use AODV.
For the sake of evaluating the performance of protocol, we simulate the ZM-AODV and AODV protocol in different scenes under OPNET platform. Protocol is simulated in different network's load and node's speed. The results show that ZM-AODV has a better performance than AODV, especially in End-To-End delay and routing overhead aspects. Due to the HELLO message in cluster can reduce the time of route establishment and the cluster structure can decrease the change of topology, the performance of TI can be improved obviously.
引文
[1] Cox D C. Wireless Personal Communication: What is it?. IEEE Personal Communications, 1995, 2 (2):20-35.
[2] 王金龙，王呈贵，吴启晖等．Ad Hoc移动无线网络．北京：国防工业出版社，2004．
[3] Perkins C E. Ad hoc Networking. Boston: Addison-Wesley, 2000.
[4] Paul Sass. Communications networks for the Force ⅩⅪ Digitized Battlefield. Mobile Networks and Applications, 1999,4(3):139-155.
[5] 彭艺．军用分组无线网络中的关键技术研究：(博士学位论文)．成都：电子科技大学，2005．
[6] Jubin J, Tomow J. The DARPA Packet Radio Network Protocols. Proceedings of the IEEE, 1987, 75(1):21-32.
[7] Schacham N, Westcott J. Future directions in packet radio architectures and protocols. Proceedings of the IEEE, 1987,75(1):83-99.
[8] Freebersyser J, Leiner B. A DoD Perspective on Mobile Ad Hoc Networks, Ad Hoe Networking, Addison Wesley, DEUTSCHLAND, 2001:29-51.
[9] Ram Ramanathan, Jason Redi. A Brief Overview of Ad Hoc Networks: Challenges and Directions. IEEE Communications Magazine, 2002,40(5):20-22.
[10] John Robinson. U S Army Weapon Systems 2001 Handbook. Defense Daily Network, New York, 2001:137-138.
[11] Elizabeth M Royer, Woh Chai-Keong. A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks. IEEE Personal Communications Magazine, 1999, 6(2):46-55
[12] 李青，张天忠．移动自组织网及其关键技术研究．电信科学，2003，4：10-13．
[13] 杨盘龙，田畅．分层分布式Ad Hoc网络拓扑模型的研究．系统仿真学报，2005，06：1405-1407．
[14] Ricardo Sanchez, Joseph Evans, Gary Minden. Networking on the Battlefield: Challenges in Highly Dynamic Multi-hop Wireless Networks. IEEE Military Communications Conference, Atlantic City, NJ, 1999:751-755.
[15] Dao S, Zhang Yongguang, Shek E et al. High-speed Digital Wireless Battlefield Network. Proceedings of SPIE-Digitization of the Battlespace Ⅳ, Orlando, Florida, 1999:129-137.
[16] 孙利民，李建中，陈渝等．无线传感器网络．北京：清华大学出版社，2005．
[17] Akyildiz I F, Wang Xudong. A survey on wireless mesh networks. IEEE Communications Magazine, 2005,43(9):23-30.
[18] 郑相全．无线自组网技术实用教程．北京：清华大学出版社，2004．
[19] Perkins C E, Bhagwat P. Highly Dynamic Destination Sequenced Distance Vector Routing(DSDV) for Mobile Computers. ACM SIGCOMM'94 Conference on Communications Architectures, Protocols and Applications. New York, 1994:234-244.
[20] Jacquet P, Muhlethaler P, Clausen T. Optimized Link State Routing Protocol for Ad Hoc Networks. Proceedings of IEEE INMIC, Pakistan, 2001:62-68.
[21] Quayyum A, Viennot L, Laouiti A. Multipoint relaying: An efficient technique for flooding in mobile wireless networks. Technical report, INRIA, Sophia Antipolis, France, 2000:3898-3899.
[22] Broch J, Johnson D B, Maltz D A. The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks. Internet Draft, Draft-ietf-manet-dsr-07, 2002.
[23] Perkins C E, Royer E M. Ad Hoc on-demand distance vector routing. Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications, New Orleans, 1999:90-100.
[24] Park V D, Corson M S. A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks. Proceedings of IEEE INFOCOM'97, Kobe, Japan, 1997:1405-1413.
[25] Haas Z, Pearlman M, Samar P. The zone routing protocol (ZRP) for Ad Hoc networks. Internet Draft: draft-ietf-manet-zone-zrp- 04, txt, 2002.
[26] Das S R, Perkins C E, Royer E M. Performance comparison of two on-demand routing protocols for Ad hoc networks. Proceedings of the IEEE Conference on Computer Communications (INFOCOM), Tel Aviv, Israel, 2000:3-12.
[27] Ramachandran I, Kapoor M, Sarkar A. Clustering algorithms for wireless Ad Hoc networks. Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications,2000, 28(16):54-63.
[28] Chatterjee M, Das K, Turgut D. A weighted clustering algorithm for mobile Ad Hoc networks. Journal of Clustering Computing IEEE, 2002, 15(2):193-204.
[29] Baker D, Ephrem Ides A. The architectural organizat ion of a mobile radio network via a distributed algorithm . IEEE Trans Comm, 1981,29 (11):1694-1701.
[30] Lin C R, Gerla M. A distributed architecture for multimedia in dynamic wireless networks. Proceedings of IEEE Globecom, Los angeles:TCCC and George Washington University,1995:1468-1472.
[31] Ephremides A, Wieselthier J E, Baker D J. A design concept for reliable mobile radio networks with frequency hopping signaling . Proceedings of IEEE, 1987, 75(1):56-73.
[32] Gerla M, Tsai J. Multicluster mobile multimedia radio network. Wireless Network, 1995, 1(3):255-265.
[33] Parekh A K. Selecting routers in Ad-Hoc Wireless Networks. Proceedings of the SBT/IEEE International Telecommunications Symposium,1994:1(3)225-227.
[34] Basagni S. Distributed clustering for Ad Hoc networks. Proceedings of the 1999 International Symposium on Parallel Architectures, Algorithms and Networks, Washington, DC, USA, 1999:310-315.
[35] Amis A D, Prakash R. Load-balancing clusters in wireless Ad Hoc networks. In: Proceedings of ASSET 2000, Univ of Texas, 2000.
[36] Chatterjee M, Das S K ,Turgut D. WCA: A Weighted Clustering Algorithm for Mobile Ad Hoc Networks. Journal of Clustering Computing IEEE, 2002,5(2):193-204.
[37] J M Chatterjee, S K Das, D Turgut. An on-demand weighted clustering algorithm(WCA) for ad hoc networks. IEEE GLOBECOM Telecommunications Conference, 2000:1697-1701.
[38] Dhurandher S K, Singh G V. Weight Based Adaptive Clustering in Wireless Ad Hoc Networks. Peoceedings of the 2005 IEEE International Conference on Personal Wireless Communications, New Delhi, India, 2005:95-100.
[39] WANG Haitao, TIAN Chang, ZHENO Shaoren. A Novel Clustering Algorithm in Ad Hoc Network and Its Performance Simulations. Journal of System Simulation, 2003,15(2):185-189.
[40] Ramachandran L, Kapoor M, Sarkar A. Clustering algorithms for wireless Ad Hoc networks, In Proceedings of the 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, 2000:54-63.
[41] Chatterjee M, Das K, Turgut D.A weighted clustering algorithm for mobile Ad Hoc networks. Journal of Clustering Computing IEEE, 2002,5(2):193-204.
[42] 陈敏．OPNET 网络仿真．北京：清华大学出版社，2004.
[43] 王文博，张金文．OPNET Modeler与网络仿真．北京，人民邮电出版社，2003．
[2] 王金龙，王呈贵，吴启晖等．Ad Hoc移动无线网络．北京：国防工业出版社，2004．
[3] Perkins C E. Ad hoc Networking. Boston: Addison-Wesley, 2000.
[4] Paul Sass. Communications networks for the Force ⅩⅪ Digitized Battlefield. Mobile Networks and Applications, 1999,4(3):139-155.
[5] 彭艺．军用分组无线网络中的关键技术研究：(博士学位论文)．成都：电子科技大学，2005．
[6] Jubin J, Tomow J. The DARPA Packet Radio Network Protocols. Proceedings of the IEEE, 1987, 75(1):21-32.
[7] Schacham N, Westcott J. Future directions in packet radio architectures and protocols. Proceedings of the IEEE, 1987,75(1):83-99.
[8] Freebersyser J, Leiner B. A DoD Perspective on Mobile Ad Hoc Networks, Ad Hoe Networking, Addison Wesley, DEUTSCHLAND, 2001:29-51.
[9] Ram Ramanathan, Jason Redi. A Brief Overview of Ad Hoc Networks: Challenges and Directions. IEEE Communications Magazine, 2002,40(5):20-22.
[10] John Robinson. U S Army Weapon Systems 2001 Handbook. Defense Daily Network, New York, 2001:137-138.
[11] Elizabeth M Royer, Woh Chai-Keong. A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks. IEEE Personal Communications Magazine, 1999, 6(2):46-55
[12] 李青，张天忠．移动自组织网及其关键技术研究．电信科学，2003，4：10-13．
[13] 杨盘龙，田畅．分层分布式Ad Hoc网络拓扑模型的研究．系统仿真学报，2005，06：1405-1407．
[14] Ricardo Sanchez, Joseph Evans, Gary Minden. Networking on the Battlefield: Challenges in Highly Dynamic Multi-hop Wireless Networks. IEEE Military Communications Conference, Atlantic City, NJ, 1999:751-755.
[15] Dao S, Zhang Yongguang, Shek E et al. High-speed Digital Wireless Battlefield Network. Proceedings of SPIE-Digitization of the Battlespace Ⅳ, Orlando, Florida, 1999:129-137.
[16] 孙利民，李建中，陈渝等．无线传感器网络．北京：清华大学出版社，2005．
[17] Akyildiz I F, Wang Xudong. A survey on wireless mesh networks. IEEE Communications Magazine, 2005,43(9):23-30.
[18] 郑相全．无线自组网技术实用教程．北京：清华大学出版社，2004．
[19] Perkins C E, Bhagwat P. Highly Dynamic Destination Sequenced Distance Vector Routing(DSDV) for Mobile Computers. ACM SIGCOMM'94 Conference on Communications Architectures, Protocols and Applications. New York, 1994:234-244.
[20] Jacquet P, Muhlethaler P, Clausen T. Optimized Link State Routing Protocol for Ad Hoc Networks. Proceedings of IEEE INMIC, Pakistan, 2001:62-68.
[21] Quayyum A, Viennot L, Laouiti A. Multipoint relaying: An efficient technique for flooding in mobile wireless networks. Technical report, INRIA, Sophia Antipolis, France, 2000:3898-3899.
[22] Broch J, Johnson D B, Maltz D A. The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks. Internet Draft, Draft-ietf-manet-dsr-07, 2002.
[23] Perkins C E, Royer E M. Ad Hoc on-demand distance vector routing. Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications, New Orleans, 1999:90-100.
[24] Park V D, Corson M S. A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks. Proceedings of IEEE INFOCOM'97, Kobe, Japan, 1997:1405-1413.
[25] Haas Z, Pearlman M, Samar P. The zone routing protocol (ZRP) for Ad Hoc networks. Internet Draft: draft-ietf-manet-zone-zrp- 04, txt, 2002.
[26] Das S R, Perkins C E, Royer E M. Performance comparison of two on-demand routing protocols for Ad hoc networks. Proceedings of the IEEE Conference on Computer Communications (INFOCOM), Tel Aviv, Israel, 2000:3-12.
[27] Ramachandran I, Kapoor M, Sarkar A. Clustering algorithms for wireless Ad Hoc networks. Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications,2000, 28(16):54-63.
[28] Chatterjee M, Das K, Turgut D. A weighted clustering algorithm for mobile Ad Hoc networks. Journal of Clustering Computing IEEE, 2002, 15(2):193-204.
[29] Baker D, Ephrem Ides A. The architectural organizat ion of a mobile radio network via a distributed algorithm . IEEE Trans Comm, 1981,29 (11):1694-1701.
[30] Lin C R, Gerla M. A distributed architecture for multimedia in dynamic wireless networks. Proceedings of IEEE Globecom, Los angeles:TCCC and George Washington University,1995:1468-1472.
[31] Ephremides A, Wieselthier J E, Baker D J. A design concept for reliable mobile radio networks with frequency hopping signaling . Proceedings of IEEE, 1987, 75(1):56-73.
[32] Gerla M, Tsai J. Multicluster mobile multimedia radio network. Wireless Network, 1995, 1(3):255-265.
[33] Parekh A K. Selecting routers in Ad-Hoc Wireless Networks. Proceedings of the SBT/IEEE International Telecommunications Symposium,1994:1(3)225-227.
[34] Basagni S. Distributed clustering for Ad Hoc networks. Proceedings of the 1999 International Symposium on Parallel Architectures, Algorithms and Networks, Washington, DC, USA, 1999:310-315.
[35] Amis A D, Prakash R. Load-balancing clusters in wireless Ad Hoc networks. In: Proceedings of ASSET 2000, Univ of Texas, 2000.
[36] Chatterjee M, Das S K ,Turgut D. WCA: A Weighted Clustering Algorithm for Mobile Ad Hoc Networks. Journal of Clustering Computing IEEE, 2002,5(2):193-204.
[37] J M Chatterjee, S K Das, D Turgut. An on-demand weighted clustering algorithm(WCA) for ad hoc networks. IEEE GLOBECOM Telecommunications Conference, 2000:1697-1701.
[38] Dhurandher S K, Singh G V. Weight Based Adaptive Clustering in Wireless Ad Hoc Networks. Peoceedings of the 2005 IEEE International Conference on Personal Wireless Communications, New Delhi, India, 2005:95-100.
[39] WANG Haitao, TIAN Chang, ZHENO Shaoren. A Novel Clustering Algorithm in Ad Hoc Network and Its Performance Simulations. Journal of System Simulation, 2003,15(2):185-189.
[40] Ramachandran L, Kapoor M, Sarkar A. Clustering algorithms for wireless Ad Hoc networks, In Proceedings of the 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, 2000:54-63.
[41] Chatterjee M, Das K, Turgut D.A weighted clustering algorithm for mobile Ad Hoc networks. Journal of Clustering Computing IEEE, 2002,5(2):193-204.
[42] 陈敏．OPNET 网络仿真．北京：清华大学出版社，2004.
[43] 王文博，张金文．OPNET Modeler与网络仿真．北京，人民邮电出版社，2003．