Ad hoc网络中能量均衡和节点不相交多径路由协议的研究
|
摘要
Ad hoc网络中节点能量有限,如果某些节点由于能量耗尽而停止工作,很可能导致整个网络分裂。另外,Ad hoc网络拓扑结构动态变化,无线带宽有限,单径路由不但不能充分利用有限的带宽,而且在链路拥塞或断开时,重新寻路会造成网络的不稳定和较大时延。这就使得节能和多径路由成为Ad hoc网络路由协议研究的热点。
本文主要研究了Ad hoc网络的能量均衡和多径路由协议。深入分析了Ad hoc网络中典型的路由协议AODV(Ad hoc On-demand Distance Vector Routing),设计并实现了基于AODV的能量均衡路由协议—EB_AODV(Energy-Balancing Routing Based on AODV)和节点不相交多径路由协议—NDM_AODV(Node-Disjoint Multi-path Routing Based on AODV)。
首先,分析了现有的节能路由协议的优缺点,针对AODV协议没有考虑节能,本文对AODV协议进行了节能扩展,提出了一种旨在最大化网络生存时间的能量均衡路由算法(EB_AODV),该算法将节点剩余能量作为选路控制条件,通过避免低能量节点参与路由,实现了节点间的能耗均衡性；通过能量充足的节点延迟转发机制,实现了网络的能耗均衡性。
其次,分析了现有的多径路由协议的优缺点,针对AODV协议采用单径路由方式的不足,对AODV协议进行了多径扩展,设计了一种节点不相交多径路由算法NDM_AODV,该算法充分结合了DSR(Dinamic Source Routing)协议的源路由思想,通过记载路由请求分组的传递路径,来获得多条节点不相交路由；同时控制请求报文的转发数量,减小了路由开销。
最后,对EB_AODV和NDM AODV进行了仿真实验,仿真结果表明,EB AODV协议有效的延长了网络生存时间,增加了分组投递率；NDM_AODV协议有效的减少了路由开销和时延,增加了投递率,它充分利用了Ad hoc网络有限的带宽资源。
Because of limited energy of nodes in Ad hoc networks, it is likely to lead to split the entire network if some nodes'energy has been depleted. Besides, with dynamic topology structure and limited bandwidth, some routing protocols based on single-path not only could not make full use of the bandwidth, but also lead to instability and bigger delay. So energy saving and multi-path routing become focus in researching routing protocols of Ad hoc networks.
Energy-saving and multi-path routing protocols have been studied in this paper. AODV, which is a typical routing protocol in Ad hoc networks, has been analyzed embeddedly. Two protocols are proposed based on AODV, which are called as Energy-Balancing routing protocols based on AODV (EB_AODV) and Node-Disjoint multi-path routing protocols based on AODV (NDM_AODV).
First of all, This paper analyzes advantages and disadvantages of current energy-saving protocols. for not considering energy-saving in AODV, This paper makes energy expansion on AODV. An energy-balancing routing protocol has been proposed. By avoiding the low-energy nodes being involved in routing, energy-balancing between nodes has been realized; By delaying transmition mechanism of nodes with enough energy, energy-balancing of the whole network has been realized.
Secondly, This paper analyzes advantages and disadvantages of current multi-path routing protocols. For having disadvantages of AODV, which uses single-path. This paper makes multi-path expansion on AODV. An node-disjoint multi-path routing protocol has been proposed, this protocol has made full use of the idea of source routing of DSR(Dynamic Source Routing)protocol, it records the path of request message to find many node-disjoint paths, and records the number of request messages to reduce load simultaneously.
Finally, two protocols are simulated in NS2. The simulation results show that EB_AODV has extended the survival time of network efficiently, and NDM_AODV has made full use of bandwidth, and improve the performance of Ad hoc network efficiently.
本文主要研究了Ad hoc网络的能量均衡和多径路由协议。深入分析了Ad hoc网络中典型的路由协议AODV(Ad hoc On-demand Distance Vector Routing),设计并实现了基于AODV的能量均衡路由协议—EB_AODV(Energy-Balancing Routing Based on AODV)和节点不相交多径路由协议—NDM_AODV(Node-Disjoint Multi-path Routing Based on AODV)。
首先,分析了现有的节能路由协议的优缺点,针对AODV协议没有考虑节能,本文对AODV协议进行了节能扩展,提出了一种旨在最大化网络生存时间的能量均衡路由算法(EB_AODV),该算法将节点剩余能量作为选路控制条件,通过避免低能量节点参与路由,实现了节点间的能耗均衡性；通过能量充足的节点延迟转发机制,实现了网络的能耗均衡性。
其次,分析了现有的多径路由协议的优缺点,针对AODV协议采用单径路由方式的不足,对AODV协议进行了多径扩展,设计了一种节点不相交多径路由算法NDM_AODV,该算法充分结合了DSR(Dinamic Source Routing)协议的源路由思想,通过记载路由请求分组的传递路径,来获得多条节点不相交路由；同时控制请求报文的转发数量,减小了路由开销。
最后,对EB_AODV和NDM AODV进行了仿真实验,仿真结果表明,EB AODV协议有效的延长了网络生存时间,增加了分组投递率；NDM_AODV协议有效的减少了路由开销和时延,增加了投递率,它充分利用了Ad hoc网络有限的带宽资源。
Because of limited energy of nodes in Ad hoc networks, it is likely to lead to split the entire network if some nodes'energy has been depleted. Besides, with dynamic topology structure and limited bandwidth, some routing protocols based on single-path not only could not make full use of the bandwidth, but also lead to instability and bigger delay. So energy saving and multi-path routing become focus in researching routing protocols of Ad hoc networks.
Energy-saving and multi-path routing protocols have been studied in this paper. AODV, which is a typical routing protocol in Ad hoc networks, has been analyzed embeddedly. Two protocols are proposed based on AODV, which are called as Energy-Balancing routing protocols based on AODV (EB_AODV) and Node-Disjoint multi-path routing protocols based on AODV (NDM_AODV).
First of all, This paper analyzes advantages and disadvantages of current energy-saving protocols. for not considering energy-saving in AODV, This paper makes energy expansion on AODV. An energy-balancing routing protocol has been proposed. By avoiding the low-energy nodes being involved in routing, energy-balancing between nodes has been realized; By delaying transmition mechanism of nodes with enough energy, energy-balancing of the whole network has been realized.
Secondly, This paper analyzes advantages and disadvantages of current multi-path routing protocols. For having disadvantages of AODV, which uses single-path. This paper makes multi-path expansion on AODV. An node-disjoint multi-path routing protocol has been proposed, this protocol has made full use of the idea of source routing of DSR(Dynamic Source Routing)protocol, it records the path of request message to find many node-disjoint paths, and records the number of request messages to reduce load simultaneously.
Finally, two protocols are simulated in NS2. The simulation results show that EB_AODV has extended the survival time of network efficiently, and NDM_AODV has made full use of bandwidth, and improve the performance of Ad hoc network efficiently.
引文
1.陈林星,曾曦,曹毅.移动Ad hoc网络——自组织分组无线网络技术[M],北京：电子工业出版社,2006,1-22.
2. Souryal, MR and Vojcic, BR and Pickholtz, RL.. Information efficiency of multihop packet radio networks with channel-adaptive routing [J], IEEE Journal on Selected Areas in Communications,2005,23(1):40-50
3. Thrun, S. Montemerlo, M. and Dahlkamp, H. etc.. Stanley:The robot that won the DARPA Grand Challenge [J], Journal of Field Robotics,2006,23(9):661-692
4.于宏毅等.无线移动自组织网络技术[M],北京：人民邮电出版社,2005,30-46
5. Yan Lindsay Sun, Wei Yu, Zhu Han. Information theoretic framework of trust modeling and evaluation for ad hoc networks [J], IEEE Journal on Selected Areas in Communications,2006,24(2):305-317
6. Lam.R.Y.W., Leung.V.C.M., Chan.H.C.B.. Polling-based protocols for packet voice transport over IEEE 802.11 wireless local area networks [J], IEEE Personal Communications,2006,13(1):22-29
7.王菊芬,袁道华.一种具有认证和加密功能的Ad hoc网络路由协议[J],计算机应用,2005,25(9)：2070-2073
8.樊勇,张晓彤,万亚东等.实现能量均衡消耗的传感器网络节点摆放策略[J],计算机工程,2007,33(16)：11-16
9.朱金华,于宁宁.无线自组织网络AODV路由协议研究[J],微计算机信息,2007,23(6)：122-124
10. Lee, U. Midkiff, S.F. and Park, J.S.. A proactive routing protocol for multi-channel wireless ad-hoc networks(DSDV-MC) [A], Proc. IEEE International Conference on Information Technology:Coding and Computing (ITCC)(C),2005,710-715
11. Johnson, D.B. Maltz, D.A. Broch, J. and others. The dynamic source routing protocol for multi-hop wireless ad hoc networks[J], Ad hoc networking,2001,5(1):139-172
12.梅创社,夏东盛.移动Ad hoc网络中节能的路由协议研究[J],陕西工业职业技术学院学报,2007,2(2)：27-32
13. Gomez, J. and Campbell, A.T. and Naghshineh, M. and Bisdikian, C..PARO: Supporting Dynamic Power Controlled Routing in Wireless Ad Hoc Networks [J], Wireless Networks,2003,9 (5),443-460
14. TOHCK. Maximum battery life routing to support ubiquitous mobile computing in wireless Ad hoc networks [J], IEEE Press Piscataway, NJ, USA,2004,12(4):609-619
15.李鹏,刘宇,李庆华.一种基于剩余能量考虑的Ad Hoc网络路由协议[J],计算机应用,2008,28(2)：399-400
16. D. Kim, J. Gareia, K. Obraczka, Routing Mechanisms for Mobile Ad Hoc Networks based on the Energy Drain Rate [J]. IEEE Transactions on Mobile Computing,2003, 2(2):161-173
17. Safwat, A. and Hassanein, H. and Mouftah, H.. A MAC-based performance study of energy-aware routing schemes in wireless ad hoc networks [J], GLOBECOM-NEW YORK,2002,1(1):47-51
18.陈小乐,方路平.一种满足剩余能量约束的方向性Ad Hoc网络路由协议[J],计算机工程与科学,2008,30(20)：24-27
19. Lee S J, Gerla M. Split Multipath Routing with Maximally Disjoint Paths in Ad hoc Networks [A], IEEE International Conference on Communications [C],2001, 3201-3205
20. Lei Wang, Lianfang Zhang, Yantai Shu, Miao Dong. Multi-path Source Routing in Wireless Ad Hoc Networks [A], Electrical and Computer Engineering,2000 Canadian Conference on [C],2000,479-483
21. Roy Leung. MP-DSR:A QoS-aware Multi-path DSR Protocol for Wireless Ad Hoc Networks [A], conference on local computer networks[C],2001,132-141
22.张平Ad Hoc网络多径源路由[D],天津：天津大学电子信息工程学院,2001
23.郑辉,陈曙,刘丽云.基于DSR的多路径路由协议的分析和改进[J],山东大学学报,2007,37(1)：1-4
24.李萌Ad Hoc网络跨层优化多径能量均衡路由[D],北京：清华大学电子工程系,2004,25-36
25. M. K. Marina, S. R. Das. Ad hoc On-demand Multipath Distance Vector Routing [A], Proceeding of 9th IEEE International Conference on Network Protocols (ICNP) [C], 2001,14-23
26. Z. Ye, S. Krishnamurthy, S. Tripathi. A Framework for Reliable Routing in Mobile Ad Hoc networks [A], INFOCOM 2003, Twenty-Second Annual Joint Conference of the IEEE Computer and Communications Societies [C],2003,270-280
27. ns2, http://www.isi.edu/nsnam/ns/[EB/OL]
28.史美林,英春.自组网路由协议综述[J],通信学报,2001,11：93-103
29. Plese, T. and Adjih, C. and Minet, P. and Laouiti, A. and Plakoo, A. and Badel, M. and Muhlethaler, P. and Jacquet, P. and Lecomte, J.. OLSR performance measurement in a military mobile ad hoc network [J], Ad Hoc Networks,2005,3(5):575-588
30.肖书成,邱珊Ad Hoc网络及其路由性能研究[J],重庆邮电学院学报,2004,16(3)：102-107
31. Burg, T. and Dawson, D.. Additional notes on the TORA example:a filtering approach toeliminate velocity measurements [J], IEEE Transactions on Control SystemsTechnology,1997,5(5)：520-523
32.王卓琳,李浩君.移动Ad hoc网络中的ZRP[J],无线电通信技术,2005,31(3)：8-10
33.杨锦亚,郭虹,胡捍英.自组网路由协议性能比较[J],微计算机信息,2006,22(8-3)：196-198
34. Doshi, S. and Bhandare, S. and Brown, T. X.. An on-demand minimum energy routing protocol for a wireless ad hoc network [J], ACM New York, NY, USA,2002,6(3): 50-66
35. Kim, K.R. and Min, S. G and Yu, N.K.. Maximizing the lifetime of wireless ad hoc networks using minimizing the Maximum used Power Routing [A]. Wireless Pervasive Computing,2008.3rd International Symposium on [C],2008,557-561
36.黄伟.基于能量控制的Ad Hoc网络路由协议的研究及仿真[D],武汉理工大学,2006
37. Wook, YuC, Youn H Y. Non-blocking, localized routing algorithm for balanced energy consumption in mobile Ad Hoc networks [J]. Proceedings of International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunica-tion Systems (MASCOTS 2001), Cincinnati,2001:117-124
38. Nasipuri A, Castaneda R, Das S. Performance of Multipath Routing for On-demand Protocols in Mobile Ad Hoc Networks [J], ACM/Kluwer Mobile Networks and Applications,2001,6(4):339-349
39. Wang Lei, Shu Yanta, Dong Miao. Adaptive Multi-path Source Routing in Ad hoc Networks [A], IEEE International Conference on Communications [C],2001: 867-871
40. Pham P, Perreau S. Performance Analysis of Reactive Shortest Path and Multi-path Routing Mechanism with Load Balance [J], Journal of Telecommunications and Information Technology,2003(2):251-259
41.于斌,孙斌,温暖等.NS2与网络模拟[M],北京：人民邮电出版社,2007
42.刘俊,徐昌彪,隆克平.基于NS的网络仿真探讨[J],计算机应用研究,2002,19(9)：54-57
43.朱西平,方旭明,饶伟栋.基于不同发送速率下移动自组网AODV路由协议的性能比较分析[J],计算机工程,2007,30(7)：86-87
44.胡鹏.无线自组网路由关键技术的研究[D],博士学位论文,中国科学技术大学,2006
45. Feeny L, Nilsson M. Investigating the energy consumption of a wireless network interface in an Ad hoc networking environment [A]. Proc.20th IEEE INFOCOM, Anchorage, Ak [C],2001:1548-1557
2. Souryal, MR and Vojcic, BR and Pickholtz, RL.. Information efficiency of multihop packet radio networks with channel-adaptive routing [J], IEEE Journal on Selected Areas in Communications,2005,23(1):40-50
3. Thrun, S. Montemerlo, M. and Dahlkamp, H. etc.. Stanley:The robot that won the DARPA Grand Challenge [J], Journal of Field Robotics,2006,23(9):661-692
4.于宏毅等.无线移动自组织网络技术[M],北京：人民邮电出版社,2005,30-46
5. Yan Lindsay Sun, Wei Yu, Zhu Han. Information theoretic framework of trust modeling and evaluation for ad hoc networks [J], IEEE Journal on Selected Areas in Communications,2006,24(2):305-317
6. Lam.R.Y.W., Leung.V.C.M., Chan.H.C.B.. Polling-based protocols for packet voice transport over IEEE 802.11 wireless local area networks [J], IEEE Personal Communications,2006,13(1):22-29
7.王菊芬,袁道华.一种具有认证和加密功能的Ad hoc网络路由协议[J],计算机应用,2005,25(9)：2070-2073
8.樊勇,张晓彤,万亚东等.实现能量均衡消耗的传感器网络节点摆放策略[J],计算机工程,2007,33(16)：11-16
9.朱金华,于宁宁.无线自组织网络AODV路由协议研究[J],微计算机信息,2007,23(6)：122-124
10. Lee, U. Midkiff, S.F. and Park, J.S.. A proactive routing protocol for multi-channel wireless ad-hoc networks(DSDV-MC) [A], Proc. IEEE International Conference on Information Technology:Coding and Computing (ITCC)(C),2005,710-715
11. Johnson, D.B. Maltz, D.A. Broch, J. and others. The dynamic source routing protocol for multi-hop wireless ad hoc networks[J], Ad hoc networking,2001,5(1):139-172
12.梅创社,夏东盛.移动Ad hoc网络中节能的路由协议研究[J],陕西工业职业技术学院学报,2007,2(2)：27-32
13. Gomez, J. and Campbell, A.T. and Naghshineh, M. and Bisdikian, C..PARO: Supporting Dynamic Power Controlled Routing in Wireless Ad Hoc Networks [J], Wireless Networks,2003,9 (5),443-460
14. TOHCK. Maximum battery life routing to support ubiquitous mobile computing in wireless Ad hoc networks [J], IEEE Press Piscataway, NJ, USA,2004,12(4):609-619
15.李鹏,刘宇,李庆华.一种基于剩余能量考虑的Ad Hoc网络路由协议[J],计算机应用,2008,28(2)：399-400
16. D. Kim, J. Gareia, K. Obraczka, Routing Mechanisms for Mobile Ad Hoc Networks based on the Energy Drain Rate [J]. IEEE Transactions on Mobile Computing,2003, 2(2):161-173
17. Safwat, A. and Hassanein, H. and Mouftah, H.. A MAC-based performance study of energy-aware routing schemes in wireless ad hoc networks [J], GLOBECOM-NEW YORK,2002,1(1):47-51
18.陈小乐,方路平.一种满足剩余能量约束的方向性Ad Hoc网络路由协议[J],计算机工程与科学,2008,30(20)：24-27
19. Lee S J, Gerla M. Split Multipath Routing with Maximally Disjoint Paths in Ad hoc Networks [A], IEEE International Conference on Communications [C],2001, 3201-3205
20. Lei Wang, Lianfang Zhang, Yantai Shu, Miao Dong. Multi-path Source Routing in Wireless Ad Hoc Networks [A], Electrical and Computer Engineering,2000 Canadian Conference on [C],2000,479-483
21. Roy Leung. MP-DSR:A QoS-aware Multi-path DSR Protocol for Wireless Ad Hoc Networks [A], conference on local computer networks[C],2001,132-141
22.张平Ad Hoc网络多径源路由[D],天津：天津大学电子信息工程学院,2001
23.郑辉,陈曙,刘丽云.基于DSR的多路径路由协议的分析和改进[J],山东大学学报,2007,37(1)：1-4
24.李萌Ad Hoc网络跨层优化多径能量均衡路由[D],北京：清华大学电子工程系,2004,25-36
25. M. K. Marina, S. R. Das. Ad hoc On-demand Multipath Distance Vector Routing [A], Proceeding of 9th IEEE International Conference on Network Protocols (ICNP) [C], 2001,14-23
26. Z. Ye, S. Krishnamurthy, S. Tripathi. A Framework for Reliable Routing in Mobile Ad Hoc networks [A], INFOCOM 2003, Twenty-Second Annual Joint Conference of the IEEE Computer and Communications Societies [C],2003,270-280
27. ns2, http://www.isi.edu/nsnam/ns/[EB/OL]
28.史美林,英春.自组网路由协议综述[J],通信学报,2001,11：93-103
29. Plese, T. and Adjih, C. and Minet, P. and Laouiti, A. and Plakoo, A. and Badel, M. and Muhlethaler, P. and Jacquet, P. and Lecomte, J.. OLSR performance measurement in a military mobile ad hoc network [J], Ad Hoc Networks,2005,3(5):575-588
30.肖书成,邱珊Ad Hoc网络及其路由性能研究[J],重庆邮电学院学报,2004,16(3)：102-107
31. Burg, T. and Dawson, D.. Additional notes on the TORA example:a filtering approach toeliminate velocity measurements [J], IEEE Transactions on Control SystemsTechnology,1997,5(5)：520-523
32.王卓琳,李浩君.移动Ad hoc网络中的ZRP[J],无线电通信技术,2005,31(3)：8-10
33.杨锦亚,郭虹,胡捍英.自组网路由协议性能比较[J],微计算机信息,2006,22(8-3)：196-198
34. Doshi, S. and Bhandare, S. and Brown, T. X.. An on-demand minimum energy routing protocol for a wireless ad hoc network [J], ACM New York, NY, USA,2002,6(3): 50-66
35. Kim, K.R. and Min, S. G and Yu, N.K.. Maximizing the lifetime of wireless ad hoc networks using minimizing the Maximum used Power Routing [A]. Wireless Pervasive Computing,2008.3rd International Symposium on [C],2008,557-561
36.黄伟.基于能量控制的Ad Hoc网络路由协议的研究及仿真[D],武汉理工大学,2006
37. Wook, YuC, Youn H Y. Non-blocking, localized routing algorithm for balanced energy consumption in mobile Ad Hoc networks [J]. Proceedings of International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunica-tion Systems (MASCOTS 2001), Cincinnati,2001:117-124
38. Nasipuri A, Castaneda R, Das S. Performance of Multipath Routing for On-demand Protocols in Mobile Ad Hoc Networks [J], ACM/Kluwer Mobile Networks and Applications,2001,6(4):339-349
39. Wang Lei, Shu Yanta, Dong Miao. Adaptive Multi-path Source Routing in Ad hoc Networks [A], IEEE International Conference on Communications [C],2001: 867-871
40. Pham P, Perreau S. Performance Analysis of Reactive Shortest Path and Multi-path Routing Mechanism with Load Balance [J], Journal of Telecommunications and Information Technology,2003(2):251-259
41.于斌,孙斌,温暖等.NS2与网络模拟[M],北京：人民邮电出版社,2007
42.刘俊,徐昌彪,隆克平.基于NS的网络仿真探讨[J],计算机应用研究,2002,19(9)：54-57
43.朱西平,方旭明,饶伟栋.基于不同发送速率下移动自组网AODV路由协议的性能比较分析[J],计算机工程,2007,30(7)：86-87
44.胡鹏.无线自组网路由关键技术的研究[D],博士学位论文,中国科学技术大学,2006
45. Feeny L, Nilsson M. Investigating the energy consumption of a wireless network interface in an Ad hoc networking environment [A]. Proc.20th IEEE INFOCOM, Anchorage, Ak [C],2001:1548-1557
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |