|
- UID
- 1023166
- 性别
- 男
- 来自
- 燕山大学
|
2蓝牙散射网拓扑构建算法
蓝牙散射网拓扑构建算法就是将一组彼此分离的，对相邻节点信息一无所知的节点连接起来，确定每个节点在网络中的角色，从而形成一个连通的蓝牙散射网。本节提出的算法可以对微微网数目进行合理控制，并能有效减少微微网间的冗余通信链接，减轻桥设备的负载，从而提高蓝牙散列网的性能。
2.1主节点的选择
算法采用分布式机制，在组网空间内选出部分权值较高的设备为主节点。每个蓝牙节点都有变量WEIGHT、变量BACK和变量TIMEOUT，其中变量WEIGHT代表节点的权值（电力等级、剩余能量、数据处理能力等资源状况），这个值表示节点作为主设备的适合度，软件模拟时，每个节点的WEIGHT值由程序随即设为（1－255）之间的整数；变量BACK代表节点是否需要备份，初始值为0，当节点角色确定为主节点和桥节点时，变量BACK变为1，变量TIMEOUT为超时设定值。
每个组网蓝牙设备接通电源后周期性切换成Inquiry或Inquiry Scan状态，以发现其他设备或被发现。当两个处于相对模式的蓝牙节点互相发现后，便进行WEIGHT值的比较（相等时，蓝牙地址大的一方获胜），WEIGHT值较小的一方将已收集到的FHS封包传给WEIGHT值较大的一方，并进入Page scan状态，WEIGHT值较大的一方接收对方的FHS封包后，将其TIMEOUT值复位，继续随机进入Inquiry或Inquiry scan程序；如此一再重复，直到TIMEOUT时间内，都没有再发现任何节点为止（节点会相继进入Page scan，只有处于Inquiry或Inquiry scan状态的节点能相互发现），该节点就是选举出来的主节点，它将进入Page程序，它的变量BACK值变为1，整个程序将进入桥节点的选择阶段。
2.2.桥节点的选择
各个已选出的主节点根据选桥策略确定互连各微微网的桥节点，并且优先使用权值较高的设备作桥。
由于第一阶段选出的主节点具有所有节点的FHS封包，从而获得需要连接成网的总节点数N总。此时，除了主节点处于Page状态，其余节点均处于Page scan状态，主节点可以通过Page程序与附近节点沟通，主节点运行微微网构成程序（此时，程序first变量的值为0，表示是初始微微网），选择最多7个节点构成初始微微网，并根据总节点数目的多少和选择weight值较大的从节点为原则，选择其中的最多3个节点作为桥节点。确定为纯从节点角色的节点同主节点建立连接，进入连接状态，不会再被其它节点搜索到；确定为桥节点角色的节点，会被主节点告知，参与初始微微网后，会再次进入Page scan状态，等待次主节点与之沟通，主节点通过桥节点将次主节点需要的信息传递给次主节点。
因为算法需要为散射网形成以后的每个微微网中的主节点和桥节点提供一个备份节点，而每个微微网的节点总数为8，除去一个主节点和它的一个备份从节点，还剩6个节点数，为满足备份要求，所以每个微微网的桥节点数最多为3。选择的桥节点数≤2时，散射网的创建过程是横向展开的，速度较慢，呈线性增长。当桥节点数≥3时，创建过程是全方位展开，速度很快，呈指数增长。随着桥节点数目的增加，创建过程加快了，但所形成散射网中微微网数量也相应增加了，网间干扰也随之加大了，所以综合考虑，在需要连接的节点数大于22时，桥节点数量Nb定为3是较好的选择。从节点数Ns尽量为7，具体选择方案如下：
当N总≤8时，Nb＝0，Ns＝N总－1；
当9≤N总≤15时，Nb＝1，Ns＝7；
当16≤N总≤22时，Nb＝2，Ns＝7；
当N总》22时，Nb＝3，Ns＝7；
初始微微网构成后，并确定桥节点数后，整个程序进入第三阶段。
2.3组成散射网
每个主节点寻呼各自所发现的设备。通过互连各个微微网，形成蓝牙散列网。
次主节点收到主节点传来的数据后，搜索通信范围内的节点，运行相同的微微网构成程序（程序first变量的值为1，表示生成的为次微微网），因为次主节点已经与一个桥节点相连，所以此时选择最多6个节点作为从节点，并根据搜索到的节点数目N次总，综合从节点的weight值，选择其中的最多2个从节点作为桥节点。次微微网的从节点数目Ns′和桥节点数目Nb′的选择方案如下：
当N次总≥8时，选择从节点数目Ns′为6，其中桥节点数目Nb′为2，再选择2个节点为新的次主节点；
当7≤N次总《8时，选择从节点数目Ns′为6，其中桥节点数目Nb′为1，再选择1个节点为新的次主节点；
当N次总≤6时，选择从节点数目Ns′为N次总，其中桥节点数目Nb′为0。
程序结束后，新微微网形成，次主节点成为该微微网的主节点，新的主节点继续选择它的次主节点，新的次主节点同样运行微微网构成程序，微微网的构成过程逐步展开，最后生成一个将所有节点连接起来的散射网。
第二、三阶段程序流程图如图6所示：
图6逐级构建微微网从而构成散射网
散射网构建算法描述如下：其中主节点为N0，微微网构成程序为
Piconet（N0，first），M（u）为次主节点集合，C（v）为第n次产生的次主节点集合。
Scatternet（n，M（u））
if（n=0）{
N0=M（u）-{};
First=0;
Return Piconet（N0，first）;
else{
M（u）=Scatternet（n-1，M（u））;
C（v）={};
while（∣M（u）∣！=0）{
u=M（u）-{};
C（v）=C（v）+Piconet（u，first）;
M（u）=M（u）-{u};
}
return C（v）;
}
}
网络构建过程应尽量向外扩展，所以次主节点的选取应离当前主节点尽量远，可以利用蓝牙中的接收信号强度指示（RSSI）来判断节点之间的距离。RSSI越大表示距离越远。因此，主节点选择RSSI值较大的节点为它的次主节点。
3.对于算法的节点插入和移除的两个过程
对于一个被给定的蓝牙WPAN拓扑，讨论两种分布式过程来处理拓扑变化。第一个过程是允许在WPAN中插入一个新的节点;第二个过程是从网络中去除一个节点，这两个过程要达到的主要目标是满足蓝牙规范的限制条件，即全网络连通性，有高的吞吐流量，降低控制信息的开销等。当然，可以加入一个新节点到网络中去，也意味着可以同时加入几个节点。因此，根据这个，我们可以依靠最初给定的一系列蓝牙设备用来建立一个可增长的BT--WPAN或者形成一个网络拓扑。
（1）插入节点过程
一个节点想快速加入到WPAN中来，它必须首先发送一个普通的查询信息来恳求它附近的节点是否可以加入。相反，如果一个节点的目的是加入到一个网络中并有良好连接，即想加入到具有低流量的微微网中或者扮演一个特殊的角色，它就必须使用专用的查询。
下面部分，讨论承载查询回复的FHS包。注意到，一个数据包FHS它包含有设备类型的标记，加上5比特就能够用于传递未来的信息。这其中2位比特预留下来以备将来使用，AM-ADDR领域的3位在查询回应中不使用。我们定义这5位传送以下信息：
2位：电池的电量等级（如：低于25%，在25%和50%之间，在50%到75%之间，高于75%）；
2位：节点的流量的等级；
1位：这个节点是否属于孤立微微网。如果一个微微网没有于任何一个微微网连接或者它附近的微微网都只仅仅与它相连那我们就称之为孤立的微微网。如果该节点属于孤立的微微网，那么该位置1，否则置0。
设a是开始查询过程的节点，正如上所述，根据收到的邻近的节点的回应，a它将决定对哪个节点进行寻呼，回应的节点要么是属于孤立的徽微网要么不属于孤立的微微网。除此之外，它还具有以下可能：
具有少于7个从节点的主节点；
从节点；
即是从节点又是桥节点；
即是主节点又是桥节点；
已经具有7个节点的主节点；
像a一样也在等着加入到蓝牙WPAN中。
a根据以下的优先顺序来选择加入到哪个回应节点；
1）属于孤立的微微网主节点（或者既是主节点又是桥节点的网络节点）
如果a收到不止一个属于孤立微微网的主节点的回应，它将选择从节点少于7个和低流量的的主节点加入。如果不止一个主节点满足上述条件，那么它还根据该节点的电池电量的等级来考虑。注意到a节点根据相关的RSSI估计每个回应节点的距离。把被选择的主节点记为u，节点a寻呼u并创建一个新的微微网，此时“a是主节点，u是从节点，过一会儿，这两个节点的角色进行互换，这样，在微微网中，a就变成从节点，并且受主节点u的支配。
如果a收到一个不属于孤立微微网的节点的回应，它将按如下的方式选择：
1）如果回复的是从节点少于7个的主节点（或者既是主节点又是桥节点），则a加入此节点并且创建一个新的微微网。通过主从节点的角色互换，a变成孤立的微微网中的从节点（或者是桥节点）
2）如果回复的节点是从节点（或者既是从节点又是桥节点）或者是具有7个从节点的主节点（或者既是主节点又是桥节点），则“创建一个新的含有该节点的微微网。
2）属于孤立的微微网从节点（或者既是从节点又是桥节点的网络节点）
有两种不同的情况：
1）没有连接到散射网的其它节点回复了a的查询，在这种情况下，a将有以下的情形：
（1）a具有可以成为主节点的足够的处理能力和能t容盘，如果这样，则a通过寻呼一个或多个对它的查询做过响应的从节点来创建一个新的微微网。那么这些从节点就成了刚形成的微微网和以前微微网之间的桥节点。对于这些被寻呼的从节点，a可以根据其节点的流量、电池状态和空间的距离来选择。假设一个微微网被一短比特位的字符来标识，即小于5位的长度，并且在微徽网中的每一个节点都知道所在的微微网的标识。一个被a寻呼的从节点可以在承载寻呼响应的FHS包中利用这’5位来标示这个信息。这样，a随时有可能中断寻呼的过程，因为它连接的节点属于已经有微徽网间连接的节点。
（2）a想成为从节点。a.根据流t，电池等级和空间距离来选择可以加入的节点，它和被选择的节点形成一个新的微微网，然后，在该微微网中，这两个节点互换角色，这样，。就变成了从节点，而被选择的节点则变成了在新微微网和以前微微网之间的主节点和桥节点。
2）a收到一个不属于孤立微微网的的节点的回复。在这种情况下，a试图连接剩余部分散射网中的孤立节点，并且按照以下优先次序在散射网中选择要连接的节点：从节点、既是从节点又是桥节点的节点、主节点、既是主节点又是桥节点、具有7个从节点的主节点。如果有必要，将依照以下准则进一步进行选择：流量，电池等级，空间距离。然后，完成要选择的节点后，a创建一个新的微微网。
3、不属于孤立的微微网但是又少于7个从节点的主节点
在现有的可利用的主节点之中，。选择具有最小流量的一个节点，如果在流量相同的情况下，然后考虑电池等级，其次是考虑该节点离a的空间距离。为了避免微微网之间的重盈和减少微微网内部之间的干扰，离“较近的节点具有优先权。把被选择的主节点记为产，节点a加入声创建一个新的微微网，此处a是主节点，尸是从节点，过一会儿，这两个节点的角色互换，这样，在微微网中，a变成从节点，并且受主节点产的支配。
不属于孤立的微微网从节点
在2的1）中，介绍了它的两种可能的情况：
1）“具有可以成为主节点的足够的处理能力和能量，如果这样，则a通过寻呼一个或多个响应过它的查询的节点来创建一个新的微微网，同时在新的微微网和以前的微微网中的节点就成为了桥节点。
2）a想成为从节点。在现有的可以利用的节点中选择可以加入的节点，a和被选择的节点形成一个新的微微网，然后，在该微微网中，这两个节点互换角色，这样，a就变成了从节点，而被选择的节点变成了主节点和桥节点。
5、不属于孤立的微微网的既是从节点又是桥节点的网络节点
像前面所说的一样，它也有两种可能的情况：
l）。具有可以成为主节点的足够的处理能力和能量，a依照以下三条准则来选择要寻呼的节点（该节点既是从节点又是桥节点）：流量;电池等级;空间距离。这样一个新的微微网形成，此处。作为主节点而被选择的节点作为从节点。
2）a想成为从节点。在这个新的微微网中，a作为从节点，被选择的节点作为主节点而且还充当该微微网与它先前所在的微微网的桥节点。
6、不属于孤立的微微网的既是主节点又是桥节点的网络节点
在现有的可利用的节点（既是主节点又是桥节点）之中，a依照以下三条准则来选择要加入的节点：流量：电池等级：空间距离。在a创建一个新的微微网之后，它与被选择的节点互换一下角色，从而在微微网中a成为从节点并且被它所选择的节点（既是主节点又是桥节点）所支配。
7、不属于孤立的微微网并且已有7个从节点的主节点
在现有的可利用的节点之中，a选择具有最小流量的一个节点，如果在流量相同的情况下，然后考虑电池等级，其次是考虑该节点离“的空间距离。以a为主节点的一个新的微微网被创建了。此时有两种可能性：
1）在这个新的微微网中，a仍然是主节点，而被选择的节点既是从节点又是桥节点;
2）这两个节点互换角色，这样，被选择的主节点使得它的其中的一个从节点处于闲置状态，该闲置节点可以运行插入程序来寻找新的微微网以便加入。要不然，a则和在这个微微网中的其它节点轮流的处于闲置状态。
8、新节点
节点a寻呼到一个新节点，这样创建一个以a为主节点的微微网。然后，如果两个节点协商后，可以互换角色。在该微微网中，同样可以包含一些回应了节点查询的其它节点。然而，为了保持蓝牙WPAN拓扑的连接性，要么是a要么是它微微网中的其它一些节点必须寻呼现有蓝牙WPAN中节点。
移去节点的过程
节点离开网络引起的变化主要取决于该节点在蓝牙WPAN中作用，有下面四种情况：
。该节点是从节点：该情况最简单，那就是该节点仅仅是从网络中移去，而没有改变拓扑的任何结构。
。该节点是主节点：在该微微网中的从节点将在蓝牙WPAN中寻找一个新的节点来重新建立连接，因此，每一个从节点都要执行插入程序，而桥节点仍然作为桥节点保持与其它微微网的连接。
。该节点既是主节点又是桥节点：这种情况的处理方式与第二种情况的处理方式一样。
。该节点既是从节点又是桥节点：如果有其它节点可以取代该节点，那么它就可从网络中很简单的移去。否则的话，就必须寻找一个可以替代该节点的节点这样，在此微微网中主节点将执行查询程序，如果不能找到通向目标微微网的桥节点，它将命令它的从节点执行查询程序以寻找桥节点。如果在蓝牙WPAN范围中，在这些节点所能传输的的范围内没有找到这样的节点，那么该微微网就与蓝牙WPAN断开。
2.射网的重要性能分析
3蓝牙组网的仿真结果和分析
小结
本章介绍了蓝牙个人区域网络的基本知识，明确了蓝牙微微网和散射网的概念，分析了蓝牙散射网的网路特点，阐述了蓝牙散射网拓扑构建的重要性以及蓝牙散射网拓扑构建算法需要解决的关键问题和衡量蓝牙散射网拓扑构建算法的标准。蓝牙自组个人区域网络的主从特性、动态性、跳频特性虽然使蓝牙组网更加灵活，但这些特点以及蓝牙节点本身多为个人数字设备，节点运行的协议和应用程序必须考虑节点处理能力、内存和能耗等条件，都无疑增加了网络拓扑构建 算法、网络路由等算法的难度。
目前蓝牙规范中对微微网内的通信协议有了明确的规定，但对蓝牙散射网的研究，还处于探索阶段，是各国科学家感兴趣和重点研究的课题之一，越来越多的研究成果完善了蓝牙网络的应用，提高了蓝牙产品的普及率。中国是人口密集，商业经济活动集中、人均收入还比较低的国家和地区，低成本、组网简单灵活的蓝牙产品将会有更广阔的应用前景。它的应用将遍及很多领域，如移动通信、计算机及周边设备、个人随身信息和娱乐设备、网络接入设备、医疗保健、金融、军事等。它是面对个人的近距离无线技术，是人与机器之间交流的好助手。
本章从介绍蓝牙节点的工作状态和蓝牙物理链路的建立过程入手，提出一种备份式的蓝牙散射网拓扑构建算法。算法吸收了Bluestars算法中以节点的可用资源为标准的方法，来选取主节点，初始主节点建立第一个微微网后，主节点选取最多3个桥节点和3个次主节点，通过逐级展开的方法建立相互连接的微微网，最终形成连通的蓝牙散射网，散射网形成后通过节点备份的方法，提高网络的自愈能力。本章最后运用数学推导的方法证明了算法几项重要的性能指标为：时间复杂度为O（logN）、消息复杂度为O（N）、网络直径为O（logN）、具有较少的微微网个数和节点角色的平均数。 |
|
