第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