蓝牙散射网网间通信问题的研究[转帖]

freezebb

2003年11月推出的蓝牙1.2版本提到的个人局域网也仅限于微微网（piconet）内的通信，在一个微微网中，即只有一个蓝牙设备是主设备（Master），可以最多有7个从设备（Slave）。这样的网络结构显然无法满足建立移动的个人局域网的需求。因此建立一个范围更广的散射网（Scatternet）是今后蓝牙的发展趋势。

散射网网间通信的问题
散射网是由多个微微网在时间和空间上相互重叠而构成的更加复杂的网络拓扑结构。散射网中的蓝牙设备既可以是某个微微网的从设备，也可以是另一个微微网的主设备。每个微微网的跳频序列各自独立，互不相关，同一微微网的所有设备跳频序列同步，通过时分复用技术，一个蓝牙设备便可以同时与几个不同的微微网保持同步。由于散射网内的通信拓扑结构（通路和节点数的不同），微微网内（intra piconet）、网间(inter piconet)切换的顺序，有效的数据流分配（即轮询算法）等各种因素影响，蓝牙利益集团（SIG）还没有制定一个协议标准来规范散射网的建立和保证最小服务质量（Qos）的通信。

散射网通信问题的症结
散射网通信面临两个急待解决的问题：
1.在复杂的网络拓扑结构，如何使散射网内的两个蓝牙设备之间迅速建立通信路径。
2.如何建立一种最佳的网间节点通信算法，从而减少因网间切换延迟造成的数据流传输效率的降低。
通过对国内外相关最新文献的研究发现，在散射网网间通信问题的研究领域，这两方面的问题往往是独立研究的。也就是在散射网拓扑结构的研究中不能顾虑到网间节点快速通信及计算量的要求。而网间节点通信算法也提出了各种各样的算法，但它们也基本不考虑实际的网络拓扑结构。
为此本文提出了一种基于利用自定义路径的散射网的随机拓扑结构，并整合了网间自适应调度通信算法，从而提供了一种真正意义上的散射网内的无缝连接通信解决方案，为实现智能的个人局域网具有一定的借鉴意义。

自定义路径的散射网拓扑结构
由于蓝牙接入点在时间和放置地点不具有规律性，因此蓝牙设备在散射网内的通信非常复杂。架构什么样的散射网，以保证网间通信顺畅成了研究的方向。国外对散射网组网提出过不同的理论，但都存在不同诸多问题。困扰的主要问题是路径的选择。目前主要可为分两种路搜索模式，一种为地址表路径搜索模式，另一种为需求搜索模式。这两种方式要么需要通信节点具有庞大的记忆体，要么在网内发送广播信息，会造成路径确认延迟或网内泛滥的询问路径信息。为此，在这里提出一种基于蓝牙设备地址的组网模式。它根据设备地址大小的不同，确认每个节点的网内通信范围，当目的节点需要得到发送节点传送的信息时，发送节点会判定目的节点是否在自己的通信范围之内，如果没有，则上传信息给主节点，由主节点传给相应的分节点(此分节点的通信范围应涵盖目的节点的MAC地址)，直到找到目的节点，这种方法称为自定义路径，它基本不会增加节点记忆体开销，并且路径方式是唯一确定的，同时这种散射网网的架构可以允许新的微微网或节点设备的加入。通过研究发现该组网方式结构清晰，定义明确,搜索路径快捷。
网间自适应调度算法
在自定义路径的散射网拓扑结构的基础之上，为了提高网间通信的速率，需要建立网间切换的通信机制。研究发现，许多算法经常需要对蓝牙协议做较大的改进和扩充后才能实现。而利用蓝牙协议中的监听模式却可以为微微网间的调度算法提供了一种灵活的方式，并且无须更改协议，这种方法称为网间自适应调度算法，它是监控各个链路上的流量并获得流量变化的数据。
在分散网中,有些节点是多个微微网的成员,是不同微微网中的从节点或者主节点,这些节点称为PMP(participant in multiple piconets)节点。它们采用时分复用方式分别参与到每个所连接的微微网中,数据才能在微微网间传递。
蓝牙协议中的监听模式为微微网间调试算法提供了一个灵活的方式。如图所示,从节点每间隔Tsniff处于监听状态,这时主从节点间可以传输数据,无论从节点收到属于自己的数据包与否,监听状态都维持Tsniffattempt个时隙。如果在监听状态中收到传给自己的数据包时，从节点还要继续在下面的Tsnifftimeout个时隙和剩余的Tsniffattempt个时隙中较大的时隙里处于监听状态，其它时间从节点可以处于休眠状态，这时设备处于低能耗模式，设备间不能传输数据。Tsniff为监听周期，Tsniffattempt为监听时隙。







网间自适应调度算法是监控各个链路上的流量并获得流量变化数据。根据这些数据调整监听模式的关键参数，实时改变节点在各个链路上的监听时隙分配比例，反映链路上的流量变化，从而有效提高吞吐量，降低时间延迟。目前，蓝牙协议中监听模式对微微网间调度的支撑有些不方便和不明确的地方。处于监听模式后不能改变监听模式的参数。只有在退出监听模式后再进入监听模式才可能使新的参数生效。监听初始时隙由主节点决定，这使连接多个微微网的从节点上的多个链路的监听时隙可能严重相互重叠，使从节点不能很好地参与到其它的微微网中。因此对监听模式的操作方式需要作一些改进：进入监听模式以后，主节点或者从节点可以改变监听参数，不需要退出监听模式。主、从节点之间协商监听参数并在下一个时隙后开始使用新的监听参数。监听初始时隙由从节点决定，从节点根据所连接的微微网个数和监听参数使分配在各个链路上的监听时间最大限度地不发生重叠。
1. 数据流量变化的监控
根据物理链路的数据流量，定义物理链路的繁忙程度B，简称为忙因子，取值范围从0.0~1.0，值越大越繁忙。当PMP节点处于监听模式时，监听时隙和监听周期的比值应该接近于B值，因为能传输数据的监听时隙所占的比例应该与B成正比，B值越大，数据流量就越大，所需的监听时隙就应越长，反之亦然。则B与Tsniff和Tsniffattempt应该有关系：B∝Tsniffattempt/Tsniff 。已知B和Tsniff值，就可以计算出Tsniffattempt值。为了避免因为B值的变化而产生相应监听模式参数的不断变化，只有当B值发生较大变化时，监听时隙和监听周期的值才作适当的放大或者缩小。
2. 最佳监听时隙分配计算
为实现分配在各微微网上的监听时间最大限度地不重叠，需要进行一些额外的简单计算。假设某个节点连接N个微微网，它在每个微微网中都处于监听模式，监听模式的参数分别是Tisniffattempt和Tisniff，其中1≤i≤N。Tisniffattempt / Tisniff 为节点在第i个微微网中的监听时间比例，因此Tisniffattempt和Tisniff 参数必须满足∑Tisniffattempt / Tisniff ≤1(1≤i≤N )。这时，如果节点取一个统一的监听间隔Tsniff，再将各个微微网的监听时隙分配到这个监听间隔中，使它们不重叠，实现监听时隙最大限度地不重叠。为了减少节点计算量，在实际应用中，假定Tisniff 不是连续取值，而是2的指数关系，即 Tisniff =2j(j＞1)。这时Tsniff 的取值为{ Tisniff }中的最大值。而Tisniffattempt 只需乘以某个2的倍数即可，使计算量降低了。
3. 监听参数计算
Lirx为在上个监听时隙里接受的数据个数，Litx为在上个监听时隙里发送的数据个数，流量为Fi。Fi=(Lirx+ Litx) Tisniff/( TmassniffTisniffattempt)，则Bi= Fi/Fmax。
PMP从节点连接了N个微微网，并是微微网P1到PN的从节点作为连接这些微微网的网桥，这时应在SB连接的微微网中都置于监听模式状态。如果SB在微微网P1中，当主节点M1和SB之间的数据流量较小时，SB会被置于监听时隙较短的监听模式，若按照微微网中的主节点决定监听模式的参数，SB有充足的时间参与到其他的微微网中。但是当主节点与从节点SB之间的数据流量都较大时，SB会被主节点置于某种较忙的模式，这时监听模式参数之间就发生了冲突，因此需要SB决定和协调各个监听模式的参数。
假设SB计算出各个链路的忙因子Bi，1≤i≤N。Bi是各个链路的绝对值，若∑NBi ＞1，则首先需要对Bi作修整，得到相对值Binew，Binew=Bi /∑NBj。若∑NBi≤1，则Binew=Bi。根据Binew计算从节点监听模式参数Tisniffattempt和Tisniff，使它在不同微微网中的参与度与其忙因子成正比，并且参数满足∑N Tisniffattempt/Tisniff≤1。若Tisniff确定并且等于Tsniff，则Tisniffattempt为Tisniffattempt=BinewTsniff。
若PMP主节点MS是微微网PS的主节点和微微网P1到PN的从节点。这时MS就不能将所有时间花在微微网PS中，它必须在某些时间切换到其他的微微网中。但是，MS是PS的主节点。它需要更多的时间处理PS中的事务，这将减少MS参与到P1到PN中的时间。因此必须根据微微网内和连接其他微微网的各个链路上的忙因子统一协调监听时间，但它们的计算方法基本相同。
只有当Bi发生较大变化时，对应的监听参数才会改变，以反映目前链路上的流量变化。当某个链路上有突发数据或者连续数据时，节点能有更多的时间比例参与到在这个链路上。或者当某个链路开始处于比较空闲的时候，节点能从这个链路上释放出来参与到其他的链路上，使系统整体吞吐量较大，平均延迟较小。
假设δ为监听模式参数改变所需的阈值，Bihistory为Bi 的历史平均值。这时，如果∣(Bihistory-Bi)/max(Bi，Bihistory )∣＞δ，说明Bi 开始有较大的变化，已经达到了参数可改变的界限。这时，如果Bi ＞Bihistory ，说明链路上的流量有较大增长，这时Ti’sniffattempt应增大，节点需要更多的监听时隙，允许主、从节点之间传送更多的数据。相反，如果Bi ＜Bihistory，说明链路上的流量有较大减少，这时Ti’sniffattempt应减小，节点释放出监听时隙，允许其他链路上有更多数据传送。假设 Aisniff=∣(Bihistory-Bi)/max(Bi，Bihistory )∣，Ti’sniffattempt增大和减少的幅度与Aisniff有关，Aisniff越大，Ti’sniffattempt的增减幅度就越大。因此当Bi ＞Bihistory时，将Tisniffattempt更改为Tisniffattempt=(1+ Aisniff/2) Tisniffattempt。当Bi ＜Bihistory时，将Tisniffattempt更改为Tisniffattempt=(1- Aisniff/2) Tisniffattempt。
假设Tisniffattempt 和Tisniff都是有界定值的，即Tisniffattempt∈[Tminsniffattempt,Tmaxsniffattempt]，Tisniff∈[Tminsniff,Tmassniff]。因此，如果更改后的Tisniffattempt＜TminsniffattemptTisniff/ Tmassniff，则Tisniffattempt等于TminsniffattemptTisniff/ Tmassniff，但Tisniff应增大，即Tisniff=2Tisniff(2Tisniff＜Tmassniff)或者 (2Tisniff≥Tmassniff)。如果更改后的Tisniffattempt＞TmaxsniffattemptTisniff/ Tmassniff，则Tisniff应减小，即Tisniff=Tisniff/2(Tisniff/2＞Tminsniff)或者Tminsniff(Tisniff/2≤Tmassniff)。而Tisniffattempt=( Tmassniff+Tmaxsniffattempt) Tisniff/(2Tmassniff)。如果改变后Tisniffattempt/ Tisniff增大且造成∑NTisniffattempt/ Tisniff＞1，则Tisniffattempt和 Tisniff恢复原来的值。
假设节点连接的微微网个数为N，忙因子为Bi，历史忙因子为Bihistory，忙因子变化率为Aiisniff，忙因子历史值的权值为α，监听间隔为Tisniff，监听时隙为Tisniffattempt，可取的监听周期的最大值为Tmaxsniff，最小值为Tminsniff，可取的监听时隙的最大值为Tmaxsniffattempt，最小值为Tminsniffattempt，判断改变监听参数的阈值为δ。调整Bihistory：Bihistory=αBihistory+(1-α) Bi.。
通过以上整个流程对监听参数的控制，完成了网间自适应算法。

结论
本文分析了影响蓝牙散射网网间通信的主要问题，提出了基于自定义路径的随机拓扑结构下的网间通信模式，即网间自适应调度算法。它能够排除各种散射网复杂的通信结构的影响，监控各个链路上的流量，并获得流量变化数据，根据这些数据调整监听模式的关键参数，实时改变节点在各个链路上的监听时隙分配比例，实现最佳监听时隙分配的方案。值得注意的是，散射网自定义路径法与现有微微网的通信协议产生一定的冲突，因此建议在散射网通信模式下，加入对散射网规范协议的更改，如在散射网通信模式下取消主/从设备模式。另外对于网间通信，进入监听模式以后，主节点或者从节点可以改变监听参数，不需要退出监听模式，这也需要在散射网的通信协议中提出要求。综上所述，网间自适应调度算法与自定义路径拓扑结构的结合，为散射网内网间通信提供了一个理想的模型，值得深入研究。