蓝牙跳频算法分析

1.概述

1.1.为什么需要跳频

WLAN和基于IEEE 802.11规范的无线设备与蓝牙一样，在无需许可的2.4 GHz ISM（工业，科学和医疗）无线电频段中运行。为了改善在该环境中的相同规范设备的通讯性能，SIG引入了自适应跳频的技术AFH（advance frequence hopping），以减少这种干扰的影响。该跳频技术可以通过各种方法实现，每种方法都有其固有的优点和缺点。

在AFH解决方案出现之前开发的蓝牙产品采用另一种形式的跳频，其跳频在设计上是随机的。 这些第一代蓝牙设备使用2.4 GHz频段中的83.5个可用频道中的79个，以随机方式跳过这些频道，速率为每秒1600次。 一旦将另一个无线设备引入环境中，这种类型的跳跃就会导致偶尔的冲突。 没有AFH蓝牙缺乏避免这些冲突的能力，从而适应其环境。 结果如下图所示，显示了蓝牙（BT）和无线LAN（WLAN）都在运行的环境。

与上述相反，自适应跳频AFH允许蓝牙通过识别固定的干扰源并将其从可用信道列表中排除来适应环境。 这种重新映射过程还涉及减少蓝牙使用的信道数量。 蓝牙规范要求至少20个信道的最小集合。 下图显示了与上图相同的环境，但现在使用了自适应跳频后的蓝牙通讯信道。

2.Classic 跳频

经典蓝牙跳频框架如下所示：有一个Channel map，即为跳频表，一个跳频阶跃；根据跳频表和跳频阶跃和当前通讯频点，即可计算出主从机下一次数据通讯的频点。

蓝牙跳频表算法各家的算法略有不同，但都需要解决两个问题

1. 信道评估：

SIG规范没有规定如何识别不良信道，目前有两种主要的方法用于执行具有自适应跳频的信道评估：RSSI（接收信号强度指示）和PER（分组错误率）。
RSSI和PER都是众所周知的用于确定哪些信道可能已被占用的技术。然而，当涉及监听当前信道状态时，这两种方法不同。 PER用于反复测试和重新评估不良信道的方法不如RSSI准确，并且可能导致临时挫折。然而，在使用RSSI时还存在许多其他问题，例如RSSI消耗的功率大于PER。当缺少可用的时隙时，RSSI还可以要求从其他功能获取带宽。

2. 同一信道数据通讯：

蓝牙AFH规定，主设备和从设备都通过同一频道进行通信。 这样做是为了避免主设备在“好”信道上发送而从设备响应“坏”信道（反之亦然）的情况，因为这将导致多次重传（其他协议AFH的数据收发是在不同信道，会产生发数据正常，接收信道干扰导致无法响应主产生的多次重传）。由于主设备和从设备在相同频率上发送接收数据，因此信道跳频率降低50％至每秒800次。 虽然这可以使蓝牙设备对来自其他蓝牙设备的干扰更敏感，但迄今为止所带来的好处超过了这个小缺点。 

3.AFH

3.1.AFH 的原理

AFH 技术是对原始蓝牙跳频序列的一种改进, 它允许蓝牙设备缩减跳频点的数量, 其基本原理是将信道分成unknown, bad or good三类, 从而避免使用bad 信道, 减少受干扰的程度。当蓝牙微微网进入AFH 状态后, 其跳频序列可使用的跳频点N 的数量是动态变化的, 但规定必须有一个最小值Nmin , 即Nmin≤N≤79。 Bluetooth 协议中将Nmin定义为20。 AFH 只用于连接状态, 而不会改变寻呼、查询等状态时的跳频序列。自适应跳频选择机制的实现是基于原79 跳系统的频率选择核心, 在其基础上增加了AFH_mode和AFH _channel _map 两个参数( 图2.12) 。 AFH_mode 指出当前选频核心是否可以使用自适应跳频序列; AFH_channel_map 中指明哪些信道是可用的, 哪些信道是不可用的。首先, 原选频核心生成一个信道, 如果这个信道是AFH_channel _map 中定义的可用信道, 则不作任何调整, 直接作为跳频序列的输出; 如果此信道包含在不可用信道中, 则通过重定位函数将其映射成一个可用的信道。这种映射关系是一一对应的 , 就是说, 如果给定了蓝牙地址、时钟以及AFH_channel_map, 一个不可用的射频信道将被唯一地转换为一可用信道, 这样保证了在同一微微网中使用AFH 机制的主从设备能够保持跳频序列的同步。


在这种实现机制下, 非自适应的79 跳系统的跳频序列等于将全部信道设为可用的AFH 选频核心产生的频率序列, 这一属性使得可以方便地与原非AFH 设备保持兼容。 AFH 技术的另一点改变是: 在原跳频系统中, 主从设备分别采用不同的频率发送数据; 当处于AFH 状态时, 在一次主从对话期间, Slave使用与Master相同的射频信道向Master响应数据包, 这被称作AFH 的相同信道机制。使用相同信道机制主要是由于在网中存在干扰的情况下, 减少跳频可以防止Slave在发送响应分组时跳到可能发生冲突的信道上, 保证至少在一次主从对话的过程中数据不易受到干扰, 达到提高吞吐率的目的。

3.2.AFH状态的控制

由于一个微微网中的跳频序列完全是由主设备决定的, 因此, 主设备也负责控制微微网跳频序列自适应状态的启用和停止, 并需要定期地更新可用信道信息。当系统希望进入AFH 状态时, 主设备首先要进行设备识别和初始化操作, 该过程主要在LMP( 链路管理协议) 层进行。 主设备先向其所有从设备发送询问消息, 通过查看从设备的属性检查是否具有支持AFH 机制的能力。如果主从设备都支持AFH, 则主设备发送LMP_set _AFH 的PDU 数据分组, 此PDU中包括AFH_mode 和AFH_channel_map 等参数, 将可用和不可用的信道通告给从设备。主设备对AFH 状态的进入、退出和更新都使用此PDU 类型, 发送AFH 命令之后, 主设备将等待确认信息的返回。 如果在规定的某个时刻( AFH_instant) 之前收到确认信息,则整个微微网顺利改变AFH 状态;

如果是进行更新信道信息操作, 在AFH_instant 之前未收到确认信息的情况下, 主设备将恢复使用全部信道作为可用信道的跳频序列,并继续向从设备发送AFH 命令直到收到响应, 方可以使用更新后的自适应跳频序列。

3.3.可用信道的确定

AFH_channel_map 参数中的可用信道是由以下几点共同确定的:
(1) 主设备本身对于干扰的测量。其主要依据有分组包丢失率(PLR)、接收信号强度(RSSI)、循环冗余纠错(CRC)、混合纠错(HEC)、前向纠错(FEC)等。
(2) Host端可以通过HCI命令HCI_set_AFH_Channel_Classification向蓝牙设备声明信道状态信息。
(3) 从设备也可以把其掌握的信道信息通过LMP 层的PDU 报告给主设备。
主设备将对这些信息资源进行理的分析和推算并最终生成一个可信赖的AFH_channel_map, 但无论如何可用信道的数量一定要大于最小信道数Nmin (20) 。 假设推算得到可用的good信道数为NG, 若NG ≥Nmin , 则可以使用全部good信道; 若Nmin > NG, 则必须使用部分unknown/bad 信道。

4.CSA#1(BLE 4.x)

4.1.算法流程

CAS#1跳频算法用于数据连接中，数据信道共37个，跳频公式如下： unmappedChannel = (lastUnmappedChannel + hopIncrement) mod 37。
fn+1=(fn+hop) mod 37, hop是一个5~16的随机值，在每次链路建立之后固定。协议规定第一次连接事件中fn=0，fn+1=(0+hop) mod 37，也就是hop信道编号

4.2.举例

假设主机 ChanelMap = 00011110 00000000 11100000 00000110 00000000b，最右边为第 1 信道，最左边为第 40 信道。那么使用到的信道为 9, 10, 21, 22, 23, 33, 34, 35, 36。
usedChannel[] = {9,10,21,22,23,33,34,35,36}, 即numUsedChannel(N) = 9
Last Unmapped Channel 的初值值为 0(之后为每次计算出来的unmappedChannel)；
假设输入 hopIncrement = 7, 则
unmappedChannel = (0+7)mod37 = 7，而 7 信道不是一个可用的信道，那么就要重映射, N=9
remappingIndex = 7mod N = 7
又 usedChannel[7] = 35
所以 data channel index = 35.

4.3.usedChannel

在上面的论述中，我们假设了ChanelMap,但在实际过程中如何得到。
1.系统在启动后会将所有数据信道(37)都设置为可用。
2.在随后的使用过程中会对信道状态进行评估，非常的类似于AFH机制的信道评估(可以看做简化版的AFH)。
3.评估的输入参数有两个，1)设备对自身的评估结果；2)来自host的评估结果。最终通过一系列算法确定除usedChannel map.
4.在链路建立时，initiating端会发送CONNECT_REQ,会将channel_map填充ChM字段,同时会置上一个timer(device_channel_map_update_timer)，用于之后定期更新该channel_map(使用LL_CHANNEL_MAP_IND)
5.其次当host通过hci cmd发送host的信道评估结果时，也需要更新channel_map;

本地如何对信道进行评估？？
其实与classic相似，其主要依据有分组包丢失率(PLR)、循环冗余纠错(CRC)。所以可以看做是简化版的AFH.

5.CSA#2(BLE 5.0)

CSA＃2是更复杂和更难跟踪用于获得下一个连接事件的信道索引的算法。特别是在高通量使用情况下，避免干扰和多路径衰落效应，使得蓝牙可以在超过10dBm的发射功率情况下获取全世界不同国家的无线电认证（单点发射功率过高肯定是难过欧美无线电认证，必须通过跳频方式使得产品平均低于当地政府要求，CSA #2的算法下，蓝牙产品在整个工作频段的平均功率较CSA #1要低）。

5.1.输入参数

1.ChannelIdentifier = (Access Address31-16) XOR (Access Address15-0)
2.The 16-bit input counter changes for each event.
For data connections it is the connection event counter connEventCounter defined in Section 4.5.1.
对于M && S，每一个次CE,connEventCounter+=1;
For periodic advertising it is the event counter paEventCounter defined in
Section 4.4.3.4. (The initial value of this counter is implementation specific. The counter shall be incremented by one for each AUX_SYNC_IND PDU; the paEventCounter shall wrap from 0xFFFF to 0x0000. AUX_SYNC_IND PDUs shall use the Channel Selection Algorithm #2 (see Section 4.5.8.3) with this event counter.)

5.2.随机数prn_e的生成过程

5.2.1.PERM

5.2.2.MAM

output = (17 x a + b) mod 216

5.3.重映射

5.4.举例

假设主机使用到的信道为 9,10,21,22,23,33,34,35,36。
usedChannel[]={9,10,21,22,23,33,34,35,36}
Access Address 假设为 0x364F10C1, Access Address[31~0] = {0011 0110 0100 1111 0001 0000 1100 0001}
第一步：
ChannelIdentifier = {0011 0110 0100 1111}XOR{0001 0000 1100 0001}= {0010 0110 1000 1110} (十进制 9870)
第二步：
A 点： ChannelIdentifier XOR counter, 初始时刻 counter=0；
A = {0010 0110 1000 1110} XOR {0000 0000 0000 0000}={0010 0110 1000 1110}
B 点 PERM ,交换比特位;
B = {0110 0100 0111 0001} (十进制 25713)
C 点 MAM， Multiply, Add, and Modulo;
C = (2571317+9870)MOD(2^16) = 53775 {1101 0010 0000 1111}
同理：
D = {0100 1011 1111 0000}(十进制 19440)
E = (1944017+9870)MOD (2^16) = 12670 {0011 0001 0111 1110}
F = {1000 1100 0111 1110} (35966)
G = (3596617+9870)MOD(2^16) = 31468{0111 1010 1110 1100}
prn_e = G XOR ChannelIdentifier = {0101 1100 0110 0010}(23650)
第三步：
unmappedChannel = prn_e MOD 37 = 7
第四步：
判断， 7 信道不是一个可用的信道，那么就要重映射, N=9
remappingIndex = floor(923650/2^16) = 3
又 usedChannel[3] = 22
所以 data channel index = 22.

5.5.小结

CSA #2和CSA #1一样的地方是都有一张约定的跳频表；不一样的是跳频阶跃的值，CSA #1的跳频阶跃值是固定的，CSA #2的跳频阶跃是通过算法计算出来的。
另外一个不一样的是CSA #2可以用在广播信道和连接信道，CSA #1只适用于连接信道。

6.总结

经典蓝牙跳频AFH算法最为复杂，需要实时监听坏信道，更新跳频表，对MCU资源要求较高，BLE 4.x是AFH的简化版，跳频表随机，跳频阶跃固定，蓝牙5的BLE部分使用新的CSA #2算法，跳频阶跃通过算法计算得到，避免干扰和多路径衰落效应。