基于蓝牙Ad Hoc网络的BAODV路由算法的研究
摘要
为了提高蓝牙Ad Hoc的建网效率,填补蓝牙技术与传统无线移动Ad Hoc按需路由协议不兼容的空缺,首次提出了基于蓝牙技术的AODV路由协议算法(BAODV:Bluetooth AODV);把蓝牙底层协议所特有的跳频技术、查询及其扫描技术、寻呼及其扫描技术以及连接进程融入至Ad Hoc的传统路由协议AODV中,使蓝牙节点具有了按需路由的特点。
利用AODV的HELLO机制,在蓝牙节点空闲状态时启动查询机制搜寻邻居拓扑信息;有数据分组发送请求时,节点只对已发现邻居启动寻呼进程交换控制分组消息;通过HOP COUNT的奇偶特性在BRREP回送过程中确定路由链路的主从角色;从/从桥链路和主/从桥链路分别实现了路由路径中数据分组传送的角色分配以及在路由建立及维护过程中控制分组的传送;新邻居节点列表的引入解决了蓝牙协议1主7从的拓扑限制。
采用NS2下的蓝牙仿真模块UCBT对蓝牙BAODV的网络形成算法做出了仿真,理论与实验研究初步表明:节点用于维护网络连通性的时间明显减少,节点的可发现概率明显提高,并维持在一个较高的水平;随着节点数目的增加,BAODV网络形成算法使主节点用于查询的时间更低,查询效率更优,时间的延长并不会使节点的查询性能降低;BAODV的连接进程在较短的时延后趋于稳定。
该算法主要应用于移动性较弱的蓝牙Ad Hoc网络,如何加快蓝牙Ad Hoc网络的快速收敛,增加网络的自愈速度为本论文提出新的挑战,是本论文进一步的研究方向。
In order to improve the efficiency of Network construction, and to fulfill the vacancy of the incompatibility between the Bluetooth technology and the on-demand routing protocol of Ad Hoc, Bluetooth Ad hoc On-Demand Vector (BAODV) algorithm was firstly proposed. The special technology of frequency hopping, inquiry and inquiry scanning, page and page scanning and connection particularly in Bluetooth Baseband is inducted into the traditional protocol of AODV to make the Bluetooth nodes routing on-demanded.
With the HELLO mechanism of AODV according to the inquiry mechanism, Bluetooth node can search its neighbors' topological information in leisure time. When data packets need to be sent, Bluetooth node needs to page only its discovered neighbors to transfers control packets. By the parity of HOP COUNT, the roles of routing path can be confirmed in the backward process of BRREP. Bridge of slave/slave routing path and bridge of master/slave routing path complete the role distributing in data and control packets sending with route searching and route maintaining. The on-demand scatternet formation of Bluetooth Ad Hoc save the time of inquiry processing, and the list of new-neighbor-node solve the constrain with 1 master to 7 slaves in Bluetooth topology.
The Bluetooth simulation module (UCBT) based on NS2 was adopted to simulate the scatternet formation of BAODV. The theory and experiment research indicated: with BAODV, delay of nodes' connection maintaining time is cut down and the probability of discoverable neighbor node is increased, and with a high level. As simulation nodes increased, the inquiry-delay of master node with BAODV scatternet formation algorithm reduced with high inquiry efficiency. As the simulation time passed, the performance of nodes inquiry will not be reduced, and the mechanism of connection in BAODV goes stability after a short delay.
This thesis is only applied to the weak mobility Bluetooth Ad Hoc network. How to improve the convergence of Bluetooth Ad Hoc scatternet formation and to speedup the healing time is the future research.
利用AODV的HELLO机制,在蓝牙节点空闲状态时启动查询机制搜寻邻居拓扑信息;有数据分组发送请求时,节点只对已发现邻居启动寻呼进程交换控制分组消息;通过HOP COUNT的奇偶特性在BRREP回送过程中确定路由链路的主从角色;从/从桥链路和主/从桥链路分别实现了路由路径中数据分组传送的角色分配以及在路由建立及维护过程中控制分组的传送;新邻居节点列表的引入解决了蓝牙协议1主7从的拓扑限制。
采用NS2下的蓝牙仿真模块UCBT对蓝牙BAODV的网络形成算法做出了仿真,理论与实验研究初步表明:节点用于维护网络连通性的时间明显减少,节点的可发现概率明显提高,并维持在一个较高的水平;随着节点数目的增加,BAODV网络形成算法使主节点用于查询的时间更低,查询效率更优,时间的延长并不会使节点的查询性能降低;BAODV的连接进程在较短的时延后趋于稳定。
该算法主要应用于移动性较弱的蓝牙Ad Hoc网络,如何加快蓝牙Ad Hoc网络的快速收敛,增加网络的自愈速度为本论文提出新的挑战,是本论文进一步的研究方向。
In order to improve the efficiency of Network construction, and to fulfill the vacancy of the incompatibility between the Bluetooth technology and the on-demand routing protocol of Ad Hoc, Bluetooth Ad hoc On-Demand Vector (BAODV) algorithm was firstly proposed. The special technology of frequency hopping, inquiry and inquiry scanning, page and page scanning and connection particularly in Bluetooth Baseband is inducted into the traditional protocol of AODV to make the Bluetooth nodes routing on-demanded.
With the HELLO mechanism of AODV according to the inquiry mechanism, Bluetooth node can search its neighbors' topological information in leisure time. When data packets need to be sent, Bluetooth node needs to page only its discovered neighbors to transfers control packets. By the parity of HOP COUNT, the roles of routing path can be confirmed in the backward process of BRREP. Bridge of slave/slave routing path and bridge of master/slave routing path complete the role distributing in data and control packets sending with route searching and route maintaining. The on-demand scatternet formation of Bluetooth Ad Hoc save the time of inquiry processing, and the list of new-neighbor-node solve the constrain with 1 master to 7 slaves in Bluetooth topology.
The Bluetooth simulation module (UCBT) based on NS2 was adopted to simulate the scatternet formation of BAODV. The theory and experiment research indicated: with BAODV, delay of nodes' connection maintaining time is cut down and the probability of discoverable neighbor node is increased, and with a high level. As simulation nodes increased, the inquiry-delay of master node with BAODV scatternet formation algorithm reduced with high inquiry efficiency. As the simulation time passed, the performance of nodes inquiry will not be reduced, and the mechanism of connection in BAODV goes stability after a short delay.
This thesis is only applied to the weak mobility Bluetooth Ad Hoc network. How to improve the convergence of Bluetooth Ad Hoc scatternet formation and to speedup the healing time is the future research.
引文
[1] Tan G, Miu A, Guttag J, Balakrishnan H. An efficient Scatternet Formation Algorithm for Dynamic Environments[C]. Cambridge: IASTED Communications and Computer Networks, 2002.527-536.
[2] Godfrey Tan, Allen Miu, John Guttag, Hari Balakrishnan. Forming scatternets from Bluetooth personal area networks. MIT Tech. Rep., MIT-LCS-TR-826, Oct, 2001
[3] T. Salonidis, P. Bhagwat, L. Tassiulas, R.LaMaire. Distributed topology construction of Bluetooth personal area networks. IEEE INFOCOM2001, 2: 1577-1586
[4] G.V. Zaruba, S. Basagni, L. Chlamtac. Bluetrees-scatternet formation to enable Bluetooth-based Ad Hoc networks. IEEE International Conference on Communication, 2001,1: 273-277
[5] Min-Te Sun, Chung-Kuo chang, Ten-Hwang Lai. A Self-Routing Topology for Bluetooth Scatternets. International Symposium on Parallel Architectures, Algorithms and Networks(ISPAN'02),2002
[6] Zhifang Wang, Robert J. Thomas, Zygmunt Haas. Bluenet-a New Scatternet Formation Scheme. 35th Annual Hawaii International Conference onSystem Sciences (HICSS-35.02), 2002
[7] C. Pereioli, S. Basagni, I. Chlamtac. Configuring Bluestars:Multihop scatternet formation for Bluetooth networks. IEEE Transactions on Computers, special issue on Wireless Internet, 2002
[8] Chiara Petrioli, Stefano Basagni. Degree-Constrained Multihop Scatternet Formation for Bluetooth Networks. IEEE Globecom 2002, Taipei, Taiwan, November 17-21,2002
[9] X. Li, I. Stojmenovic. Partial Delaunay Triangulation and Degree Limited Localized Bluetooth Scatternet formation. AD_HOC Networks and Wireless (ADHOCNOW), Fields Institute,Toronto, Canada, September 20-21 2002
[10] Yong Liu, Myung J. Lee, Tarek N. Saadawi. A Bluetooth Scatternet-Route Structuer for Multihop Ad Hoc Networks. IEEE Journal on Selected Areas in Communications, Feb. 2003, 21(2): 229-239
[11] Foo Chun-Choong and Chua Kee-Chaing. BlueRings - Bluetooth Scatternets with Ring Structures. IASTED International Conference on Wireless and Optical Communication(WOC 2002), Banff, Canada, July 2002
[12]任岚,郭忠文.分布式动态蓝牙散列网形成算法[J].计算机应用研究,2006,22(03):248-250
[13]刘继顺,宋铁成,叶芝慧.基于轮换簇头的多跳对等蓝牙Ad Hoc网络形成协议[J].南京师范大学学报(工程技术版),2006,06(03):1 8-22
[14]杨帆,王珂,钱志鸿.链形结构的蓝牙分散网拓扑构成算法与性能仿真[J].通信学报,2006,27(01):28-35
[15]方旭明,何蓉等.短距离无线与移动通信网络[M].北京:人民邮电出版社,2004
[16]T.Clausen and P.Jacquet.Optimized Link State Routing Protocol(OLSR).RFC 3626,October 2003
[17]C.E.Perkins and E.M.Royer.Ad-Hoc On-Demand Distance Vector Routing.In Proceedings ofIEEE WMCSA'99,New Orleans,LA,Feb.1999,90-100
[18]C.-K.Toh.Associativity-Based Routing For Ad Hoc Mobile Networks.Wireless Personal Communications Journal,Special Issue on Mobile Networking and Computing Systems,Kluwer Academic Publishers,Mar.1997,4(2):103-139
[19]David B.Johnson,David A.Maltz and Yih-Chun Hu.The Dynamic Source Routing fo Mobile Ad Hoc Networks.http://www.ietf.org/Internet-drafts/draft-ietf-manet-dsr-10.txt,19 July 2004,IETF Internet Draft(work in progress)
[20]M.R.Pearlman and Z.J.Haas.Determining the Optimal Configuration of the Zone Routing Protocol.IEEE JSAC,special issue on Ad-Hoc Networks,August 1999,17(8)
[21]Marina,M.K.,Das,S.R..On-demand Multipath Distance Vector Routing in Ad Hoc Networks.Proceedings of the International Conference for Network Procotols(2001)
[22]Elizabeth M.Royer and Charles E.Perkins.Multicast Operation of the Ad Hoc On-Demand Distance Vector Routing Protocol.In Proceedings of the Fifth Annual ACM/IEE International Conference,WCNC '99.,pp.1313-1317,September 1999
[23]S.-J.Lee,Mario Gerla,and C.-C.Chiang.On-Demand Multicast Routing Protocol,In Proceedings of the IEEE Wireless Communications and Networking Conference,WCNC'99,September 1999,1298-1304
[24]Jorjeta G.Jetcheve.Yih-Chun Hu,David A.Maltz,and David B.Johnson.A Simple Protocol for Multicast and Broadcast in Mobile Ad Hoc Networks.Internet-Draft,draft-ietf-manet-simple-mbcast-01.txt,July 2001.Work in progress
[25]Bluetooth SIG,Specification of the Bluetooth System:Specification Volume 1-Core. Version 1.1[S].
[26]Bluetooth SIG,Specification of the Bluetooth System:Specification Volume 2-Profile.Version 1.1[S].
[27]金纯,许光辰,孙睿.蓝牙技术[M].北京:电子工业出版社,2001
[28]麦汉荣,廖劲光等.基于蓝牙技术的网络空调程控系统的设计与实现[J].电子技术应用,2008,33(01):85-89
[29]唐欣,陈雷,周正.干扰受限环境下蓝芽系统的性能及自适应跳频共存机制[J].电路与系统学报,2003,8(5):23-27
[30]夏巍,李恪,许劲杨.蓝牙与Wi-Fi共存问题在蓝芽系统端的解决方案[J].计算机应用研究,2004,1(7):214-219
[31]甘良才,邹学玉.短波跳频信道差错率的实时监测器[J].电波科学学报,1999,1(1):110-115.
[32]东南大学移动通信国家重点实验室.蓝牙技术与应用讲义[M].东南大学内部讲义,2002
[33]CSR.BlueCore Scatternet Support[M].http://www.csr.com,Aug 2005
[34]T.Salonidis,P.Bhagwat,L.Tassiulas and R.LaMaire,"Proximity awareness and ad hoc network establishment in Bluetooth",Technical Report,Institute of Systems Research(ISR)University of Maryland,http://www.isr.umd.edu/TechReports.
[35]B.Zhen,Y.Kim,"Location Management Support of IP over Bluetooth",3Gwireless'2002,San Francisco,May 2002.
[36]于宏毅等.无线移动自组织网[M].北京:人民邮电出版社,2005
[37]张禄林,雷春娟等.蓝牙协议及其实现[M].北京:人民邮电出版社,2001
[38]刘书生,赵海.蓝牙技术应用[M].沈阳:东北大学出版社,2001
[39]陈林星,曾曦等.移动Ad Hoc网络.自组织分组无线网络技术[M].北京:电子工业出版社,2006
[40]郑少仁,王海涛等.Ad Hoc网络技术[M].北京:人民邮电出版社,2005
[41]于斌,孙斌等.NS2与网络模拟[M].北京:人民邮电出版社,2007
[42]徐雷鸣,庞博等.NS与网络模拟[M].北京:人民邮电出版社,2003
[43]Fall K,Varadhan K.The NS manual[EB/OL].http://www.isi.edu/nsnam/ns/doc/index.html,2007
[44]NS by Example.http://nile.wpi.edu/NS/
[45]UCBT-Bluetooth extension for NS2 at the University of Cincinnati.http://www.ececs.uc.edu/～cdmc/ucbt/
[2] Godfrey Tan, Allen Miu, John Guttag, Hari Balakrishnan. Forming scatternets from Bluetooth personal area networks. MIT Tech. Rep., MIT-LCS-TR-826, Oct, 2001
[3] T. Salonidis, P. Bhagwat, L. Tassiulas, R.LaMaire. Distributed topology construction of Bluetooth personal area networks. IEEE INFOCOM2001, 2: 1577-1586
[4] G.V. Zaruba, S. Basagni, L. Chlamtac. Bluetrees-scatternet formation to enable Bluetooth-based Ad Hoc networks. IEEE International Conference on Communication, 2001,1: 273-277
[5] Min-Te Sun, Chung-Kuo chang, Ten-Hwang Lai. A Self-Routing Topology for Bluetooth Scatternets. International Symposium on Parallel Architectures, Algorithms and Networks(ISPAN'02),2002
[6] Zhifang Wang, Robert J. Thomas, Zygmunt Haas. Bluenet-a New Scatternet Formation Scheme. 35th Annual Hawaii International Conference onSystem Sciences (HICSS-35.02), 2002
[7] C. Pereioli, S. Basagni, I. Chlamtac. Configuring Bluestars:Multihop scatternet formation for Bluetooth networks. IEEE Transactions on Computers, special issue on Wireless Internet, 2002
[8] Chiara Petrioli, Stefano Basagni. Degree-Constrained Multihop Scatternet Formation for Bluetooth Networks. IEEE Globecom 2002, Taipei, Taiwan, November 17-21,2002
[9] X. Li, I. Stojmenovic. Partial Delaunay Triangulation and Degree Limited Localized Bluetooth Scatternet formation. AD_HOC Networks and Wireless (ADHOCNOW), Fields Institute,Toronto, Canada, September 20-21 2002
[10] Yong Liu, Myung J. Lee, Tarek N. Saadawi. A Bluetooth Scatternet-Route Structuer for Multihop Ad Hoc Networks. IEEE Journal on Selected Areas in Communications, Feb. 2003, 21(2): 229-239
[11] Foo Chun-Choong and Chua Kee-Chaing. BlueRings - Bluetooth Scatternets with Ring Structures. IASTED International Conference on Wireless and Optical Communication(WOC 2002), Banff, Canada, July 2002
[12]任岚,郭忠文.分布式动态蓝牙散列网形成算法[J].计算机应用研究,2006,22(03):248-250
[13]刘继顺,宋铁成,叶芝慧.基于轮换簇头的多跳对等蓝牙Ad Hoc网络形成协议[J].南京师范大学学报(工程技术版),2006,06(03):1 8-22
[14]杨帆,王珂,钱志鸿.链形结构的蓝牙分散网拓扑构成算法与性能仿真[J].通信学报,2006,27(01):28-35
[15]方旭明,何蓉等.短距离无线与移动通信网络[M].北京:人民邮电出版社,2004
[16]T.Clausen and P.Jacquet.Optimized Link State Routing Protocol(OLSR).RFC 3626,October 2003
[17]C.E.Perkins and E.M.Royer.Ad-Hoc On-Demand Distance Vector Routing.In Proceedings ofIEEE WMCSA'99,New Orleans,LA,Feb.1999,90-100
[18]C.-K.Toh.Associativity-Based Routing For Ad Hoc Mobile Networks.Wireless Personal Communications Journal,Special Issue on Mobile Networking and Computing Systems,Kluwer Academic Publishers,Mar.1997,4(2):103-139
[19]David B.Johnson,David A.Maltz and Yih-Chun Hu.The Dynamic Source Routing fo Mobile Ad Hoc Networks.http://www.ietf.org/Internet-drafts/draft-ietf-manet-dsr-10.txt,19 July 2004,IETF Internet Draft(work in progress)
[20]M.R.Pearlman and Z.J.Haas.Determining the Optimal Configuration of the Zone Routing Protocol.IEEE JSAC,special issue on Ad-Hoc Networks,August 1999,17(8)
[21]Marina,M.K.,Das,S.R..On-demand Multipath Distance Vector Routing in Ad Hoc Networks.Proceedings of the International Conference for Network Procotols(2001)
[22]Elizabeth M.Royer and Charles E.Perkins.Multicast Operation of the Ad Hoc On-Demand Distance Vector Routing Protocol.In Proceedings of the Fifth Annual ACM/IEE International Conference,WCNC '99.,pp.1313-1317,September 1999
[23]S.-J.Lee,Mario Gerla,and C.-C.Chiang.On-Demand Multicast Routing Protocol,In Proceedings of the IEEE Wireless Communications and Networking Conference,WCNC'99,September 1999,1298-1304
[24]Jorjeta G.Jetcheve.Yih-Chun Hu,David A.Maltz,and David B.Johnson.A Simple Protocol for Multicast and Broadcast in Mobile Ad Hoc Networks.Internet-Draft,draft-ietf-manet-simple-mbcast-01.txt,July 2001.Work in progress
[25]Bluetooth SIG,Specification of the Bluetooth System:Specification Volume 1-Core. Version 1.1[S].
[26]Bluetooth SIG,Specification of the Bluetooth System:Specification Volume 2-Profile.Version 1.1[S].
[27]金纯,许光辰,孙睿.蓝牙技术[M].北京:电子工业出版社,2001
[28]麦汉荣,廖劲光等.基于蓝牙技术的网络空调程控系统的设计与实现[J].电子技术应用,2008,33(01):85-89
[29]唐欣,陈雷,周正.干扰受限环境下蓝芽系统的性能及自适应跳频共存机制[J].电路与系统学报,2003,8(5):23-27
[30]夏巍,李恪,许劲杨.蓝牙与Wi-Fi共存问题在蓝芽系统端的解决方案[J].计算机应用研究,2004,1(7):214-219
[31]甘良才,邹学玉.短波跳频信道差错率的实时监测器[J].电波科学学报,1999,1(1):110-115.
[32]东南大学移动通信国家重点实验室.蓝牙技术与应用讲义[M].东南大学内部讲义,2002
[33]CSR.BlueCore Scatternet Support[M].http://www.csr.com,Aug 2005
[34]T.Salonidis,P.Bhagwat,L.Tassiulas and R.LaMaire,"Proximity awareness and ad hoc network establishment in Bluetooth",Technical Report,Institute of Systems Research(ISR)University of Maryland,http://www.isr.umd.edu/TechReports.
[35]B.Zhen,Y.Kim,"Location Management Support of IP over Bluetooth",3Gwireless'2002,San Francisco,May 2002.
[36]于宏毅等.无线移动自组织网[M].北京:人民邮电出版社,2005
[37]张禄林,雷春娟等.蓝牙协议及其实现[M].北京:人民邮电出版社,2001
[38]刘书生,赵海.蓝牙技术应用[M].沈阳:东北大学出版社,2001
[39]陈林星,曾曦等.移动Ad Hoc网络.自组织分组无线网络技术[M].北京:电子工业出版社,2006
[40]郑少仁,王海涛等.Ad Hoc网络技术[M].北京:人民邮电出版社,2005
[41]于斌,孙斌等.NS2与网络模拟[M].北京:人民邮电出版社,2007
[42]徐雷鸣,庞博等.NS与网络模拟[M].北京:人民邮电出版社,2003
[43]Fall K,Varadhan K.The NS manual[EB/OL].http://www.isi.edu/nsnam/ns/doc/index.html,2007
[44]NS by Example.http://nile.wpi.edu/NS/
[45]UCBT-Bluetooth extension for NS2 at the University of Cincinnati.http://www.ececs.uc.edu/～cdmc/ucbt/