蓝牙Adhoc网络形成算法的性能评价

第25卷第5期

2005年5月

文章编号:1001-9081(2005)05-1173-04

计算机应用

ComputerApplications

Vo.l25No.5May2005

蓝牙Adhoc网络形成算法的性能评价

何 蓉,方旭明

(西南交通大学计算机与通信工程学院,四川成都,610031)

(rong.he@,xmfang2002@)

摘 要:评价一个蓝牙Adhoc网络形成算法的优劣可以用不同方法和性能指标来衡量。文中首先介绍了蓝牙Adhoc网络的拓扑结构,然后讨论了评价蓝牙Adhoc网络形成算法的主要手段和性能指标,对目前主要的蓝牙Adhoc网络形成协议的性能进行了总结和比较。此外,还对树型散射网形成(TreeScatternetFormation,TSF)协议的部分性能指标进行了仿真,给出了相应的性能仿真曲线。最后总结现有网络形成协议存在的问题,分析业界关注的重点及今后可能的研究方向。

关键词:蓝牙;Adhoc网络;散射网;网络形成;协议中图分类号:TP393 文献标识码:A

PerformanceevaluationofBluetoothAdhocnetworkformationalgorithms

HERong,FANGXu-ming

(SchoolofComputerandCommunicationsEngineering,SouthwestJiaotongUniversity,ChengduSichuan610031,China)

Abstract:TherearedifferentmethodsandcriteriatoevaluatetheperformanceofaprotocolforBluetoothAdhocnetworkformation.Inthispaper,topologystructureofBluetoothAdhocnetworkwaspresentedfirstly.Then,mainapproachesinsystemperformanceevaluationandkeyperformancecriteriaofthenetworkformationalgorithmswerediscussed,andtheperformanceofdominatingitsformationprotocolswassummarized.Furthermore,simulationofTreeScatternetFormation(TSF)protocolwasdoneandthecorrespondingsimulationresultsweregiven.Atlast,someissuesinexistingprotocolswerepointedout,whilethekeyaspectsofBluetoothAdhocnetworkformationalgorithmswhichpeoplecaredmostandsomepossibleresearchdirectionswerepresented.

Keywords:Bluetooth;Adhocnetwork;scatternet;networkformation;protocol

0 引言

Adhoc网络是一种不需要网络基础设施的多跳、自组织网络,可以应用于军事指挥与通信、抢险救灾、应急通信、传感器网络、移动会议等众多领域。与蜂窝通信网类似,Adhoc网络除了面临容量限制以外,还有自组织、无集中控制管理机制,以及能量受到限制等复杂的问题,有很多关键理论和技术问题尚未得到根本或很好的解决,这些都是目前研究的热点。蓝牙技术和IEEE802.11标准在全球快速推动了Adhoc网络的发展,其中蓝牙技术被认为是可以用于组建Adhoc网络,特别是传感器网络最便于实施的技术之一。然而,在组建网络时,由于蓝牙技术自身的一些特点,对网络的综合设计、管理策略及其容量的分配等提出了巨大的挑战。

蓝牙网络的基本结构是微微网(piconet),每个微微网包含一个主设备(master)和最多7个活动(active)从设备(slave),主-从设备之间的通信是单跳的。同一微微网内部采用相同的跳频序列,各个微微网由不同的跳频序列区分。如何将多个微微网互相连接起来,构成一个多跳的Adhoc网络,也称为蓝牙散射网(scatternet),是一个值得研究的关键问题。最新的蓝牙规范1.2尚未对蓝牙微微网之间的通信和基于蓝牙的Adhoc网络的形成等内容做出具体描述[6],这是一个开放的问题。目前已有一些学者提出了各种不同的蓝牙

Adhoc网络形成算法,如何对这些算法的性能进行评价是一个重要的问题。

本文主要讨论了目前蓝牙Adhoc网络形成协议的主要性能评价方法和性能指标,分析比较了现有几种典型协议的性能,并对树型散射网形成(TreeScatternetFormation,TSF)协议[4]的一些性能指标进行了仿真,给出了相应的性能仿真曲线。最后总结了现有蓝牙Adhoc网络形成协议存在的问题,并分析了业界所关注的重点及今后可能的研究方向。

1 蓝牙Adhoc网络的拓扑结构

图1 蓝牙Adhoc网络的拓扑结构

当几个微微网在空间上有重叠时,可以让某些蓝牙设备充当桥节点(bridge)或网关节点(Gateway),采取时分复用方式在不同微微网之间进行角色的切换,这也是多个微微网能

收稿日期:2004-11-03;修订日期:2005-03-30 基金项目:西南交通大学科研基金资助项目(X1201011030102)

作者简介:何蓉(1974-),女,江西丰城人,讲师,博士研究生,主要研究方向:移动自组织网络、无线网格网; 方旭明(1962-)男,浙江义

乌人,教授,博士生导师,博士,主要研究方向:移动Adhoc网络、移动IP、无线局域网、蜂窝移动通信系统资源管理、移动性管理与建模.

1174 计算机应用2005年

够互联为多跳Adhoc网络的关键。桥节点可以是主/从桥(M/SBridge)或从/从桥(S/Sbridge),同一时刻桥节点只能在一个微微网中处于活动状态。一个典型的散射网拓扑结构如图1所示。图1中的有向链路表示节点之间已经建立了主-从关系。一个有k个出度(k\1)的节点是一个微微网中的主节点,共有k个从节点。一个有m个入度(m\1)的节点是m个微微网中从节点,各个微微网通过桥节点相连。图1中的无向链路仅仅表示两个节点理物上处于彼此的通信范围内,但并没有主-从关系,不能直接通信。

同一组蓝牙设备采用不同的蓝牙Adhoc网络形成算法,所形成的网络拓扑结构可能各不相同,从图论上来说,n个蓝牙设备组网时,可以采用的拓扑结构共有O(2n(n-1)/2)种[7]。常见的拓扑结构包括树型(如Bluetree[10]、TSF[4]、SHAPER[8])、环型(如BlueRing[16])和网状型(BTCP[9]、BlueStars[13])等。不同的网络拓扑结构对应的调度算法、路由协议、吞吐量及可靠性等性能各不相同,很难给出一个统一的评价标准。例如,树型拓扑结构在路由和调度等方面比较简单,不存在路由环路问题,但任何一对节点之间只存在一条路径,鲁棒性较差。网状拓扑结构在一对节点间存在多条路径,系统健壮性很好,但相应的路由和调度算法比较复杂,需要维护的链路数目较多。

真得到,常用的仿真软件有Ns2、OPNet、Glomosim、OMNet++和Qualnet等。

不同的蓝牙Adhoc网络形成算法都有自己特定的应用场景和所关注的性能指标,例如更高的网络吞吐量、更低的时延、更小的能量消耗等。评价蓝牙Adhoc网络形成协议的主要性能指标包括:完全的网络连接性,即网络中任意两个节点之间至少可通过一条单跳或多跳路径彼此连接;散射网的形成时延;桥节点的度,即桥节点所连接的微微网数目。由于桥节点在不同微微网之间转换角色时,将产生很大开销,从而降低网络性能,因此,桥节点的度是评价蓝牙Adhoc网络形成协议中重要的一个性能指标。当散射网中任何一个微微网的从设备数目多于7个,则需要在节点间进行休眠(park)和唤醒(unpark)操作,这将可能会导致系统吞吐量下降,因此,每个微微网中平均从节点数目也是衡量蓝牙Adhoc网络性能的一个重要指标。多跳特性,即不要求所有的节点都在彼此相邻的范围内,相对于要求所有节点都位于彼此相邻的传输范围内的单跳特性,其通用性更好;由于蓝牙技术主要用于组建一个移动性的Adhoc网络,拓扑结构是动态变化的。网络自愈性是评价网络形成协议在动态环境下的有效性的重要指标,是指当节点由于移动、电能耗尽等原因导致出现多个分区时,是否能够自动适应动态的拓扑变化,实现分区自愈,保证网络的连接性。目前已有的大部分蓝牙Adhoc网络形成协议都没有考虑自愈性。此外,评价蓝牙Adhoc网络形成协议性能的指标还包括散射网中平均微微网数目、网络总的最大带宽、最小平均路径长度、系统吞吐量、最大平均节点可用性,以及网络寿命等。

一般而言,各个性能指标是相互矛盾的,很难同时满足,某些性能的提高可能需要牺牲其他性能,因此设计协议时需要折中考虑各种因素。现有的文献通过仿真得到了一些结论,例如:在微微网的密度较大情况,如50~100个微微网重叠时,微微网之间的干扰比较明显[5];采用S/S桥节点的蓝牙散射网比采用M/S桥节点的散射网具有更高的系统吞吐量和更低的平均访问时延[17],这主要是因为M/S桥节点作为从节点参与另一个微微网通信时,其作为主节点的那个微微网内部的通信就停止了。

表1对目前主要的蓝牙散射网形成协议的部分性能指标进行了总结和比较。其中,MSM表示表示网状拓扑,桥节点为M/S桥;SSM表示网状拓扑,桥节点为S/S桥;MSR表示环状拓扑,桥节点为M/S桥。2.2 TSF协议及其性能仿真

MIT实验室的GodfreyTan等人提出的TSF协议[4]能够

2 蓝牙Adhoc网络形成协议的性能评价

2.1 蓝牙Adhoc网形成协议的性能评价方法与指标

目前,对Adhoc网络系统性能评价的方法主要有两种,一种是测试法(measurement),该方法主要用于真实的系统或系统原型中。例如瑞典Uppsala大学APE测试环境,可以同时进行多达30个以上节点的测试。由于该方法需要构建试验床(Testbed),价格昂贵,且局限于特定的场景和移动模型,而且由于协议的可扩展性、对用户移动模式和速度的敏感度等都很难在真实的测试环境中实现,所以该方法并没有获得广泛应用,只有少量文献涉及到实际Adhoc网络试验床的测试研究。测试方法最大的优点是可以发现采用仿真建模手段无法发现的一些问题,例如,通过Uppsala大学APE测试环境发现了Adhoc网络中存在/通信灰色地带(CommunicationGrayZone)0问题[3],而采用仿真方法无法发现该问题。另一种方法是通过理论或仿真模型来评价系统性能,可以通过改变系统参数和场景来研究系统性能。Adhoc网络理论模型的研究目前还处在初级阶段,对网络性能的评价通常还不够详细。仿真建模方法比较成熟和灵活,得到了广泛应用,目前对Adhoc网络系统性能指标的评价基本都是采用计算机仿

第5期何蓉等:蓝牙Adhoc网络形成算法的性能评价 1175

对由于节点的移动、离开等造成的网络分裂进行分区自愈。TSF协议生成的拓扑结构为树型,只适用于单跳拓扑,即要求所有的节点都必须位于彼此的传输范围内。TSF协议的基本思想是每个节点都不断运行各自的状态机算法,在以下三种状态中的任意两种之间转换:

1)Inquire:查询操作。2)Comm:传输数据或者空闲。

3)Comm/Scan:开始于Comm状态,然后周期性进入查询扫描状态。

TSF协议能够实现分区自愈的基本思想是将节点的发现与树的合并分开实现。每个根节点选择一个协调者(Coordinator),如果该根节点只有一个子节点,则它自己作为协调者,否则,根节点从其子节点中任意选择一个作为协调者,该过程一直持续到选出一个协调者或者到达叶节点而结束。由协调者来执行发现其他协调者的任务,不同树之间的合并,即分区自愈,只能由根节点(rootnode)来执行;网络的形成遵循以下几个规则:

1)孤立节点(Freenode)可以和其他孤立节点建立连接,也可以与树节点(treenode,即非根节点和协调者节点)建立连接;

2)一棵树的根节点可以和另一棵树的根节点建立连接,这样使两棵独立的树合并为一棵;

3)树节点(Treenode)只能接收孤立节点(Freenode)作为从节点,不能和其他任何节点合并。

本文基于NS2和Blueware1.0仿真环境中对TSF协议的一些性能指标进行了仿真,包括散射网的形成时延、系统平均吞吐量、所形成的散射网平均路径长度(以跳为单位),以及散射网形成过程中发现邻节点操作的时间所占散射网形成总时间的百分比。仿真结果如图2~5

所示。

协议是现有协议中少数几个考虑了一定动态环境的网络形成协议之一,比静态网络形成协议具有更好的适用性。但是它还存在诸多问题,例如只适用于单跳环境;只依靠单个协调者来发现邻节点,速度较慢,因而网络形成延时较大;系统吞吐量会随着节点数目的增加而显著下降等。

图4 散射网平均路径长度(hops)

图5 散射网形成中发现邻节点所占时间百分比

3 结语

蓝牙Adhoc网络形成算法与网络的综合设计、调度算法、路由算法等密切相关,直接影响到蓝牙Adhoc网络是否能真正应用到实际环境中。评价一个网络形成算法的优劣可以用不同方法和性能指标来衡量。本文主要讨论了蓝牙Adhoc网络形成协议的主要性能指标,对现有主要网形成协议的性能进行了总结和比较。此外,还采用计算机仿真这种被广泛采用的方法,对TSF协议的部分性能指标进行了仿真与分析。

总的说来,有关蓝牙Adhoc网形成问题的研究还不是很多,现有的蓝牙散射网形成协议还存在着很多的问题,距离真正的实际应用还有差距。业界对蓝牙Adhoc网络形成问题的关注重点包括:协议的自重构能力(sel-freconfiguration)、算法的分布式特征、算法的鲁棒性和可扩充性(Scalable)等。另外,由于可以从不同的角度以不同的性能指标来衡量网络的性能,而各个性能指标之间往往是相互矛盾的,如何在各个性能指标之间折中,从而使整个网络的性能最优,这也是业界目前比较关注的问题,例如如何在微微网中的最大从节点数与整个散射网中微微网的数目之间折中。蓝牙Adhoc网形成问题的研究可以与路由、调度及容量分配等问题结合起来考虑。另外,还可以结合业务流特征、QoS等条件,以实现负载平衡或者使微微网之间的通信量最少。参考文献:

[1] KALIAM,GARGS,SHOREYR.ScatternetStructureandInter-P-i

conetCommunicationintheBluetoothSystem[A].

IEEENational

ConferenceonCommunications[C].NewDelh,i2000.

图2

散射网形成时延

图3 散射网平均系统吞吐量

[2] BASAGNIS,BRUNOR,PETRIOLIC.Aperformancecomparison

ofscatternetformationprotocolsfornetworksofBluetoothdevices[A].ProceedingsoftheFirstIEEEInternationalConferenceonPer-vasiveComputingandCommunications(PerComp03)[C],March2003.341-350.

从仿真结果可以看出,随着节点数的增加,Adhoc网络形成时延和平均路径长度在波动中呈上升趋势,系统平均吞

吐量和平均发现设备所用时间则在波动中呈下降趋势。TSF

1176 计算机应用2005年

[3] CHLAMTACI,LIUJ.Mobileadhocnetworking:imperativesand

challenges[J].AdHocNetworks,2003,1(1):13-64.

[4] TANG,MIUA,GUTTAGJ,etal.AnEfficientScatternetForma-tionAlgorithmforDynamicEnvironments[A].IASTEDCommunica-tionsandComputerNetworks(CCN)[C].Cambridge,MA,Novem-ber2002.

[5] ZURBESS.ConsiderationsonlinkandsystemthroughputofBlue-toothnetworks[A].11thIEEEInternationalSymposiumonPerson-a,lIndoorandMobileRadioCommunications(PIMRC2000)[C].

2000.1315-1319.[6]

SpecificationsofBluetoothSystem,volume1[EB/OL].,February2001.

[7] BHAGWATP,RAOSP.OnthecharacterizationofBluetoothsca-t

ternettopologies[R].Maryland,USA:departmentofCSUnivers-ity,http://www.cs.umd.edu/~pravin/.2001.

[8] CUOMOF,BACCOGD,MELODIAT.Shaper:asel-fhealingalgo-rithmproducingmult-ihopbluetoothscatternets[A].GlobalTele-communicationsConference(GLOBECOMp03)[C],2003.236-240.

[9] SALONIDIST,BHAGWATP,TASSIULASL,etal.Distributedto-pologyconstructionofBluetoothpersonalareanetworks[A].Twent-iethAnnualJointConferenceoftheIEEEComputerandCommunica-tionsSocieties.Proceedings[C],April2001.1577-1586.[10]ZARUBAGV,BASAGNIS,CHLAMTACI.Bluetrees-scatternet

formationtoenableBluetooth-basedAdhocnetworks[A].IEEEIn-ternationalConferenceonCommunication[C],277.

June2001.273-December

[11] LIXY,STOJMENOVICI,WANGY.Partialdelaunaytriangula-tionanddegreelimitedlocalizedbluetoothscatternetformation[J].IEEETransactionsonParallelandDistributedSystems,2004,15(4):350-361.

[12] WANGZF,THOMASRJ,HAASZ.Bluenet-aNewScatternet

FormationScheme[A].Proceedingsofthe35thAnnualHawaiiIn-ternationalConferenceonSystemSciences(HICSS-35.02)[C].BigIsland,Hawai,iJanuary2002.

[13] PETRIOLIC,BASAGNIS,CHLAMTACI.Configuringbluestars:

MultihopscatternetformationforBluetoothnetworks[J].TransactionsonComputers,2003,52(6):779-790.

[14] PETRIOLIC,BASAGNIS,CHLAMTACI.BlueMesh:Degree-ConstrainedMult-iHopScatternetFormationforBluetoothNetworks[J].MobileNetworksandApplications,2004,9(1):33-47.

[15] LIUY,LEEMJ,SAADAWITN.ABluetoothScatternet-Route

StructureforMultihopAdHocNetworks[J].IEEEJournalonSe-lectedAreasinCommunications,2003,21(2):229-239.

[16] FOOC-C,CHUAK-C.BlueRings-BluetoothScatternetswith

RingStructures[A].IASTEDInternationalConferenceonWirelessandOpticalCommunication(WOC2002)[C].Banf,fCanada,Ju-ly2002.

[17] MISICJ,MISICVB.Bridgesofbluetoothcounty:Topologies,

schedulingandperformance[J].IEEEJournalofSelectedAreasinCommunications,SpecialissueonWirelessLANsandHomeNe-tworks.2003,21(2):240-258.

IEEE

(上接第1172页)

如果单跳误差独立同分布E~N(0,R2),经过n跳后的累积误差的均方差等于。目前的算法如RBS、TPSN、DMTS和FTSP都采用提高单跳同步精度、采用最短路径同步以减少跳数,降低多跳误差累积。却没有充分利用周围节点的时钟信息以降低误差随跳数累积的速度。

时钟精度实质是对时钟值不确定性的表征,根据信息论的观点,信息作为一种负熵,可以降低不确定度。节点可以利用的信息包括临近节点的时钟信息以及自身的时间记录,在实际应用中,结合极大似然估计、贝叶斯后验估计进行数据融

[13]

合可以有效降低多跳误差累积。

1493.

[5] PingS.Delaymeasurementtimesynchronizationforwirelesssensor

networks[R].IntelResearchCenter:IR-TR-2003-64,June,2003.[6] MAROTIM,KUSYB,SIMONG,etal.Thefloodingtimesynchro-nizationprotocol[A].Proceedingsofthe2ndinternationalconfer-enceonEmbeddednetworkedsensorsystems(Sensysp04)[C],2004.39-49.

[7] GANERIWALS,KUMARR,SRIVASTAVAMB.Timing-SyncPro-tocolforSensorNetwork[A].Proceedingsofthe1stinternationalconferenceonEmbeddednetworkedsensorsystems(IPSNp04)[C],2003.138-149.

[8] ELSONJ,ESTRINGL.Fine-GrainedNetworkTimeSynchroniza-tionusingReferenceBroadcasts[A].Proceedingsofthe5thsympo-siumonOperatingsystemsdesignandimplementation[C],2002.147-163.

[9] PALCHAUDHURIS,SAHAAK,

JOHNSONDB.AdaptiveClock

synchronizationinsensornetworks[A].Proceedingsofthethirdin-ternationalsymposiumonInformationprocessinginsensornetworks[C],2004.340-348.

[10] SICHITIUML,VEERARITTIPHANC.Simple,accuratetimesyn-chronizationforwirelesssensornetworks[A].ProceedingoftheIEEEWirelessCommunicationsandNetworkingConference(WCNC2003)[C],2003.16-20.

[11] VIGJR.IntroductiontoQuartzFrequencyStandards[R].Technical

ReportSLCET-TR-92-1,ArmyResearchLaboratory.

[12] CLEMENTIA,FERREIRAA,PENNAP,etal.Theminimum

rangeassignmentproblemonlinearradionetworks[J].TheoreticalComputerSciencearchive,2003,29(9):751-761.

[13] GAOQ,BLOWKJ,HOLDINGDJ.Simplealgorithmforimpro-vingtimesynchronizationinwirelesssensornetworks[J].Electron-icsLetters,2004,40(14):889-891.

4 结语

时钟同步是无线传感器网络的一项重要支撑技术,它对

网络的运行以及应用的开展意义重大。本文分析了时钟同步在传感器网络的应用及其对时钟同步算法的特殊需求,阐述了时钟同步的一般原理,分类综述了现有的三大类同步算法,最后给出了未来研究的几个领域。参考文献:

[1] AKYILDIZIF,SUW,SANKARASUBRAMANIAMY,etal.Wire-lesssensornetworks:puterNetworks[J].TheInter-nationalJournalofComputerandTelecommunicationsNetworking,2002,8(4):393-422.

[2] HILLJ,CULLERD.Mica:AWirelessPlatformforDeeplyEmbed-dedNetworks[J].IEEEMicro,2002,22(6):12-24.

[3] ELSONJ,ROMERK.WirelessSensorNetworks:ANewRegimefor

TimeSynchronization[J].ACMSIGCOMMComputerCommunica-tionReview,2003,33(1):149-154.[4] MILLSDL.Internettimesynchronization:

col[J].

theNetworkTimeProto-IEEETransonCommunications1991,39(10):1482-

本文来源：https://www.bwwdw.com/article/jd51.html