摘要
蓝牙技术是一种无线数据与语音通信的开放性全球规范,它是以低成本的短距离无线通信为基础,为固定与移动设备的通信环境提供连接的通信技术。蓝牙散射网的拓扑是网络路由及调度的基础,对整个网络的路由及调度性能都会产生重大的影响。因此,研究和创建一个合理的便于路由的蓝牙散射网拓扑构建算法至关重要。
本文分析了蓝牙技术协议框架及其网络结构的特点,并对现有蓝牙散射网的拓扑构建算法进行了研究和性能比较分析。在此基础上提出了一种基于分布式自愈的蓝牙散射网拓扑构建算法。该算法提出了基于节点能量等级和信息处理能力等级的节点优先级选取原则,根据节点的优先级选择主中心控制节点,按照先组成微微网,再扩充成散射网的机制进行组网。最终将一组节点数目未知的、均匀随机分布的、彼此孤立的、并不处于相互的通信距离内的蓝牙节点相互连接起来,构成连通的蓝牙散射网。
本算法提高了网络的健壮能力。另外,提出了主从节点在动态网络环境下出现故障时的处理方案,即主节点通过优先级轮询调度从节点和桥节点的方法可以及时检测并进行处理,提高了网络的自愈能力。
在网络仿真平台NS2下利用蓝牙仿真模块BlueHoc对本文提出的蓝牙动态网络拓扑构建算法进行了软件模拟,在性能参数方面与现存的TSF算法进行了对比和分析。结果表明本算法具有网络创建时间较短,故障恢复时间较快以及平均微微网大小接近8个节点等特点,是一种实用的蓝牙散射网构建算法。
Bluetooth technology is an open global specification for wireless data and voice communication. Based on low-cost short-distance wireless communication, Bluetooth becomes a communication technology that provides special connections for landline and mobile devices. Because it has many intriguing characteristics, such as low cost, low power consumption, small size, and free spectrum.With the development and popularization of Bluetooth techlogy, there is increasing interest in wireless ad hoc networks. The Bluetooth personal area network, which is composed of multi-devices, is one of the typical Ad hoc networks. There are two kinds of network formations, piconet and scatternet. The Bluetooth personal area network can either work independently or connect to Internet and other wireless networks. The Bluetooth personal area network is designed for the application scenes of homes and small offices. It can be used for voice communication, data transmission, the connection and automatic information exchange of electrical devices and etc. But the certain constraints of Bluetooth bring new challenges in constructing and maintenancing a wireless ad hoc network with Bluetooth devices.
To construct a determinate Bluetooth network topology, Bluetooth devices inquire each other, construct point-to-point physical connection, synchronize frequency-hopping sequence, exchange essential address and clock information. Better topology algorithm can carry out these steps faster to make nodes within communication range to form steady networks. Once Bluetooth scatternet topology is constructed, it will considerably influence the whole network routing and scheduling. We analyze the Bluetooth protocol, the characteristics of frequency hopping and master-to-slave mode, so it is proposed that the keystone in Bluetooth network researching is the construction of topology.
The whole work is divided into three parts.
Firstly, The Bluetooth personal area network, which is composed of multi-devices, is one of the typical Ad Hoc. The Ad Hoc wireless mobile network based on Bluetooth is a self-construction, self-organization and self-management wireless mobile network without additional network devices or manual configuration. The Bluetooth specification has not had feasible introduction on scatternet topology formation, packet routing, channel or link scheduling and access point. There is no algorithm could achieve the best performance of Bluetooth network, so these questions are all current leading and important research issues of Bluetooth technology.
Secondly, this paper introduces and analyses several typical Bluetooth scatternet topologies and their formative processes in present articles, and gives simple contrast among these scatternets, that indicates that there are some deficiencies in present algorithms on network topologies self-healing. This paper also discusses familiar problems in dynamic networks such as slave nodes quit or malfunction, master nodes quit or malfunction, main bridge nodes quit or malfunction, subordinate bridge nodes quit or malfunction and so forth. Thereby we discuss improving topology algorithm, which can better adapt to dynamic condition, and we compare the performances of the network construction algorithms above. The standards to evaluate an algorithm is about: (1)the connectedness of the formed network, (2)average degree of the devices, (3)delay of the network, (4) the number of devices in each piconet, (5)the number roles assumed by each node, (6)self-healing of the network, (7)multi-hop characteristics, (8)the average number of the piconets, (9)routing robustness, (10)time complexity, (11)network diameter, (12)message complexity. Then the advantages and disadvantages of the various algorithms are pointed out. Finally, the demands of an algorithm are concluded and the important bridge node working mode is given.
Finally,this paper proposes a dynamic Bluetooth scatternet topology algorithm, which is distributed and self-healing. Nodes are independent from each other which are located at random without messages about neighbors. This algorithm doesn’t demand that the nodes are within communication range. The core of this algorithm is during the inquiry procedure. When a node in the inquiry scan state receives an ID packet, it responds with an Frequency
Hop Synchronization(FHS) packet if it wishes to be discovered. It is proposed that the five bits which is not used in an FHS packet for the inquiry response can be employed to convey some additional information. For example, 2 bits represent the node energy status, 2 bits represent the information processing capacity of the node, 1 bit represents the node connectivity status. According to the inquiry procedure, the node can acquire the information of adjacent nodes. The principle of nodes election is mainly based on the following points: (1)The level of the node energy status, the highest energy level node is the generally selected node. (2)Among the same energy level nodes, the best information processing capacity level node is preferred. (3)On the basis of the former two principles, we tend to select the shortest distance nodes. According to the priority, the main central control node is selected. Finally a set of Bluetooth nodes which are unknown quantitatively, distributed evenly at random, independent from each other and not located within the communication range will connect with each other and form connected Bluetooth scatternet. The algorithm in this paper improves the robustness of the network. Once the nodes in the scatternet join or leave, the self-healing algorithm in this paper could detect and deal with it in time. It is detected by the priority scheduling of the brige node and the slave node. So this network can adapt to dynamic topology changes. This algorithm can also improve the ability of self-healing in Bluetooth network.
In this paper, we adopt Bluehoc Bluetooth network simulation software platform based on NS2 in Linux operating system to simulate the Bluetooth dynamic topology algorithm and make the performance analysis compare with the TSF algorithm. The results show that this algorithm has the performance of both fast creating network and fast recovery time, the size of the piconet is between 7.5 and 8, which is almost in full state. It is a practical algorithm for constructing scatternet topology.
引文
[1]马建仓.蓝牙核心技术及应用[M].科学出版社,2003.1.
[2]金纯,许光辰,孙睿.蓝牙技术[M].电子工业出版社,2001.3.
[3]李纯.蓝牙技术起跳[M].电子工业出版社,2002.1.
[4]NATHEN JM.蓝牙揭密[M].人民邮电出版社,2001.8.
[5]钱志鸿,杨帆,周求湛.蓝牙技术原理、开发与应用[M].北京航天航空大学出版社,2006.3.
[6]The Bluetooth Special Interest Group(SIG).http: //www.bluetooth.org.
[7]张禄林,雷春娟,郎晓虹.蓝牙协议及其实现[M].人民邮电出版社,2001.
[8]宿大伟,须德.蓝牙协议一致性测试方案[J].电信科学,2001(5):57-58.
[9]Theodore S.Rappapor.无线通信原理与应用[M].电子工业出版社,1998.9.
[10]方士庭.蓝牙天线技术分析与应用介绍[J].台湾新通讯,2001(9):35-37.
[11]Haartsen JC.The Bluetooth radio system[C].IEEE Personal Communications,February 2000,7(1):28-36.
[12] Bluetooth Profile Specfication-Generic Access Profile v1.1.Bluetooth SIG,2001.
[13]李勇,于宏毅.蓝牙散射网的构成机制[J].通信技术,2003,137(5):79-81.
[14]IEEE 802.11.http://grouper.ieee.org/groups/802/11.
[15]Infrared Data Association.http://www.irda.org/.
[16]王权平,王莉.ZigBee技术及其应用[J].现代电信科技,2004:37-38.
[17]葛利嘉,朱林等.超宽带无线电基础[M].电子工业出版社,2005.1.
[18]游战清.无线射频识别技术(RFID)原理与应用[M].电子工业出版社,2004:170-203.
[19]郑少仁,王海涛,赵志峰等.Ad Hoc网络技术[M].人民邮电出版社,2005.1.
[20]申辉贤,方旭明.基于蓝牙的Ad Hoc网络形成协议[J].电讯技术,2003(4):5-6.
[21]林宏.蓝牙自组个人区域网络创建和调度算法的研究[D].中国科学院软件研究所,2002:13-16.
[22]Johansson P,Kapoor R,Gerla M.Personal area networks:Bluetooth or IEEE 802.11[C].In International Journal of Wireless Information Networks special issue on mobile ad hocnetworks(MANETs) Standards,Research,Applications,April 2002,9(2):50-51.
[23]Moore D,Scribner T.Bluetooth personal area networking profiles v0.9[M].Bluetooth SIG,2001.http://www.bluetooth.org.
[24]T Salonidis,P Bhagwat,L Tassiulas .Distributed topology construction of Bluetooth personal area networks[C].Proceedings of IEEE Information and Communication 2001,2001,3:1577-1586.
[25]G V Zaruba,S Basagni and I Chlamtac.Bluetrees-scatternet formation to enable Bluetooth-based ad hoc networks[C].In Proc of IEEE ICC’01.2001,6:273–277.
[26]C Petrioli,S Basagni and I Chlamtac,Configuring BlueStars:Multihop scatternet formation for Bluetooth networks[C].IEEE Transactions on Computers,Special Issue on Wireless Internet 2003,52(6):779–790.
[27]Z Wang,R J Thomas and Z Haas.BlueNet–A new scatternet formation scheme[C].In Proceedings of the 35th Hawaii International Conference on System Science (HICSS-35).Big Island, Hawaii.2002,1:7-10,779-787.
[28]Aggarwal A,Kapoor M,Ramachandran L,Sarkar A.Clustering algorithms for wireless ad hoc networks[C].In Proceedings of the 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications,MA USA,August 2000:54-63.
[29]G Tan,A Miu,J Guttag,H Balakrishnan.An Efficient Scatternet Formation Algorithm for Dynamic Environment[J] . Proceedings of the IASTED Communications and Computer Networks(CCN),Cambridge,MA ,November,2002:4-6,68-74.
[30] Liu Yong Lee Myung J,Saadawi Tarek N.A Bluetooth scatternet-route structure for multihop Ad Hoc networks [J].IEEE Journal on Selected Areas in Communication ,2003,21(2):229-239.
[31]杨帆,王珂,钱志鸿.链式结构的蓝牙分散网拓扑构成算法与性能仿真[J].通信学报,2006.1,27(1):29-30.
[32]杨帆.蓝牙个域网调度与网络构成算法的研究[D].吉林大学通信工程学院,2006.06:106-118.
[33]C Law,K Y Siu.A Bluetooth Scatternet Formation Algorithm[C].Proccedings of the IEEE symposium on ad hoc wireless networks.USA:San Antonio,2001:2864-2869.
[34]Foo Chun Choong , Chua Kee Chaing . BlueRings-Bluetooth Scatternets with Ring Structures[C].IASTED International Conference on Wireless and Optical 71Communication(WOC2002).Canada:Banff,2002:1563-1567.
[35]C Petrioli,S Basagni and I Chlamtac.BlueMesh:Degree-Constrained Multi-Hop Scatternet Formation for Bluetooth Networks[J].Moblie Networks and Applications,2004,15(4):351-361.
[36]C Yao . On constructing minimum spanning trees in k- dimensional spaces and related problems[J].SIAM Journal on Computing,1982,11(4):721-736.
[37]S Basagni,R Bruno and C Petrioli.Performance evaluation of a new scatternet formation protocol for multi-hop Bluetooth networks[C].Proceedings of the 5th International Symposium on Personal Wireless Multimedia Communications,WPMC 2002,Honolulu,Hawaii,2002,1(27-30):208-212.
[38]Apurva Kumar,Rajeev Gupta.Capacity Evaluation of Frequency Hopping Based Ad-hoc Systems[C].Proceedings of ACM SIGMETRICS,June,2001:133-142.
[39]Kounavis M,Campbell A T.Implementation and evaluation of programmable handoff in mobile networks[J].In ACM Joumal on Mobile Networks and Applications(MONET),Special Issue on Mobile Multimedia Communieations,2001,6:443-461.
[40]G Zussman and A Segall . Capacity Assignment in Bluetooth Scatternets- Analysis and Algorithms[C].In Proceedings of IFIP-TC6 Networking,2002,3:2345-2351.
[41]Zurbes S.Consideration on Link and System Throuhgput of Bluetooth Networks[C].11th IEEE International Symposium on Personal Communications 2000:1315-1319.
[42]M J,M VB.Bridge of Bluetooth county:Topologies,Scheduling and Performance[J].IEEE Journal of Selected Areas in Communications,2003:240-258.
[43]Barriere L,Fraigniaud P,Narayanan L,Opatrny J.Dynamic construction of Bluetooth scatternets of fixed degree and low diameter[C].Proc of the fourteenth ACM-SIAM Symposium On Discrete Algorithms(SODA),2003:781-790.
[44]S.Baatz,C.Bieschke,M.Frank,P.Martini,C Scholz and C Killhl.Building efficient Bluetooth scatternet topologies from 1-factors[C].Proceedings of WOC 2002,2002:2-3.
[45]S asagni,R Bruno,C Petrioli.Device Discovery in Bluetooth Networks:A Scatternet Perspective[C].Proceedings of the IFIP-TC6 Networking Conference,Networking 2002,Pisa,Italy,May,2002:1-2.
[46]Salonidis T,Bhagwat P,Tassiulas L.Proximity awareness and fast connection establishment in Bluetooth[J].In Proceedings of IEEE Mobile and Ad Hoc Networking and Computing,Aug 2000:141-142.
[47]徐雷鸣,庞博,赵耀.NS与网络模拟[M].人民邮电出版社,2003:5-6.
[48]The VINT Project.The ns Manual[M].http: //www.isi.edu/nsnam/ns/(2002).
[49] B N Clark,C J Colburn and D S Johnson.Discrete Mathematics[J].1990,86:165-167.
[50] IBM,BlueHoc Version1.0. http: //www.124.ibm.com/developerworks/projects/bluehoc,2001.
[51]许家瑞.蓝牙模拟环境的建构[D].国立台湾大学资讯研究所,1991:15-16.