【《基于邻居信息的冗余抑制和碰撞避免设计分析》7200字】

基于邻居信息的冗余抑制和碰撞避免设计分析目录TOC\o"1-3"\h\u31593基于邻居信息的冗余抑制和碰撞避免设计分析 158941.1基础实现 2238481.2转发概率计算 3282301.3随机转发延迟 11图3-2冗余抑制和碰撞避免的整体设计冗余抑制和碰撞避免的整体设计如图3-2所示，整体的思想是设置一个随机转发延迟，在随机转发延迟到期前收集消息的副本，以及转发副本节点的邻居节点集信息，在转发前对该条信息所对应的邻居节点集进行更新，根据未覆盖的邻居节点集信息，使用设计的概率公式自适应的调节节点的转发概率。为了兼顾低密度网络和高密度网络，本设计中使用分段函数确定随机转发延迟。1.1基础实现为了防止蓝牙Mesh网络发生无限泛洪的情况，TTL机制和缓存机制是必须实现的基本功能。TTL通过限制数据包的最大中继次数来避免数据包无限传播。在本设计中的缓存机制存在两个作用。记录已接收数据包信息防止对同一条消息的重复转发。在随机转发延迟截止时间到来前缓存计划转发的数据包。本设计中对TTL机制的设计遵循标准规范，当TTL值为2时，停止对数据包的中继。为了保证数据包的可达性，所有数据包均选择TTL的最大值127。在缓存机制的设计上，根据本设计的特点，需要设计两个缓存区，第一个缓存区为已接收缓存区，用于存放已接收的NetworkPDU的部分字段，防止重复转发。第二个缓存区为发送缓存区，用于存放待发送的NetworkPDU以及该消息的未覆盖邻居节点集和当前节点的邻居节点集。发送缓存区存在的原因是加入随机转发延迟后，接收到的消息将不会被立即转发出去，而是在随机转发延迟到期后，判断是否需要转发，如果需要转发，再通过广播信道进行广播转发。考虑到蓝牙Mesh设备一般应用在嵌入式设备上，处理速度慢、内存资源有限，因此缓存区不能无限存储数据包信息，需要采用一定的置换算法淘汰缓存的数据包，维持一个合理的范围，防止发生内存溢出的现象。置换算法可以分为三大类，第一类是采用先进先出的FIFO(FirstInFirstOut)。FIFO按照时间顺序，采用一个先进先出的队列存储数据包，在队列长度小于预设的最大缓存数量时，数据包压入队列，在队列长度达到了预设最大缓存数量时，队尾元素出队列，队首压入最新的数据包。FIFO优点是算法实现简单，仅用一个队列的数据结构就可以实现，插入一条数据的时间复杂度为O(1)，缺点是查找的时间复杂度为O(n)。第二类是LRU(LeastRecentlyUsed，最近最少使用)算法，该算法按照数据的访问时间对数据进行排序，将最新出现的数据包放到头部，如果该数据包已在LRU缓存中，则将其提到头部，在LRU缓存达到设定最大值时，淘汰最老的数据。LRU的优点是查找和插入的时间复杂度均为O(1)，效率较高，缺点是LRU算法实现的数据结构较为复杂，一般采用双向链表和哈希表实现，占用的空间资源较大。第三类是最佳置换算法，但其仅存在理论中。考虑到LRU算法的空间占用较大，实现较为复杂，而采用FIFO的方式占用空间较小，实现简单，因此已接收缓存区和待发送缓存区都采用FIFO算法实现。图3-3NetworkPDU组成为了节省设备的内存空间，已接收缓存区和待发送缓存区将缓存NetwordPDU的不同字段。如图3-3所示，表示的是NetworkPDU的组成。IVI、NID、NetMIC、TTL均为校验性的数据，而SEQ、SRC、DST字段可以作为数据包唯一性的区分依据，但不同节点的DST字段有可能重复(即多个节点向同一个单播地址发送数据)，因此，对已接收缓存区，仅缓存SEQ和SRC字段，每条缓存消息所占的字节数为5Byte。对于待发送缓存区，需要在缓存前修改TTL字段，同时计算NetMIC的新值，之后将整个NetworkPDU缓存起来，其最大长度为29Byte。1.2转发概率计算本文章的直接目的是通过减少蓝牙Mesh网络中非必要的冗余数据来提高蓝牙Mesh网络的性能，减小平均转发百分比，同时保证数据包的投递率不低于采用管理泛洪的蓝牙Mesh网络。在本小节的推导过程中，假设蓝牙Mesh网络中所有节点具有相同的传输功率(代表相同的传输半径)，同时不考虑广播冲突问题。下面将推导蓝牙Mesh网络中的节点在转发时产生冗余数据的模型。1、节点的转发有效覆盖率与冗余广播的关系蓝牙Mesh网络在智能建筑这种节点密度较大的应用场景中，节点之间距离较短，往往会造成一部份区域的无线电信号出现重叠的情况。下面将分析两个转发节点在转发过程中的通信情况。图3-4有效广播区域如图3-4表示，白色节点T和黑色节点R分别代表一次蓝牙Mesh网络消息发布时参与转发的两个节点，两个节点的发射功率相同，且均处于对方的无线电覆盖范围之内。图3-4中各参数的含义如下。表3-1各参数含义项目说明T中继节点(将消息通过广播转发给T)R中继节点(接收T的广播消息)r蓝牙Mesh节点无线电半径d两个中继节点的距离S节点T的无线电覆盖区域S节点R的无线电覆盖区域S节点T和节点R的无线电重叠区域S节点S的重播有校区域S节点T的重播有效区域假设节点均匀的分布在节点T和节点R所处的网络中，在t0时刻，节点T将蓝牙Mesh网络中的消息m通过广播转发给节点R。在t0时刻，节点T的无线电覆盖区域ST内所有的节点同时接收到消息m，在t1时刻，节点S通过广播继续对消息m进行中继，在t1时刻，节点R的无线电覆盖区域SR内所有的节点也会同时接收到消息m'(中继一次后，TTL会发生变化，BLE包也会发生变化，因此用m'代替)。在这两次广播过程中，节点T和节点R的无线电重叠区域ST∩R内的所有节点会收到消息m'。由于在第一次广播中，在节点在网络中随机分布的情形下，其广播面积与广播覆盖的节点呈正相关性。因此可以用有效广播区域来度量节点再次转发的收益。从直观上讲，两节点的距离越近，第二次广播的有效广播区域就越小，第二次的有效广播区域可以进行精确计算，在图3-4所示的网络中，为节点R的无线电覆盖面积与节点T和节点R交集之差：SR−T∩R以节点T和节点R的中点为坐标原点，建立坐标轴，可计算重播的广播面积SRSR−T∩R=πr令t=rsinθ,则有SR−T∩R=πr=πr=πr=π=π=r在节点T和节点R保证在同一无线电范围的前提下，其最大距离dTRPmax=r≈60.9%(3-4)从公式3-4中可以得出，中继节点的最大有效覆盖范围仅为其无线电覆盖范围的60.9%左右，在邻居节点较多，节点密度较大时，采用管理泛洪算法将导致中继节点接收到较多的冗余数据包，每次接收到当两个节点距离足够小时，SR−T∩R图3-5三个邻居节点导致转发节点的转播收益为零如果能够准确的计算设备间的距离和角度将会获得最佳的转发策略。但由于室内环境的复杂性，利用RSSI定位是不可靠的，这点在前面做了讨论。为了避免这个问题，本研究主要利用节点接收的冗余信息以及邻居节点信息来计算转发概率。在随机分布的网络中，区域内节点的数量和区域面积呈正相关，因此中继节点转发后能新增覆盖的节点数量与其重播的有效覆盖面积也呈正相关关系。对于一次转发来讲，定义Pavg在图3-4所示的模型中，使两个节点能够进行正常通信的dTR的有效范围为[0,r]，假设节点随机分布以节点R为圆心，r为半径的无线电范围内。为了得到有效平均面积，本文在MATLAB中进行了如下仿真实验，以求得P表3-2仿真参数仿真参数仿真数值仿真区域1000×1000传输半径500节点数量10000个拓扑分布随机分布拓扑数量1000如表3-2所示，本次仿真在1000×1000的区域内随机生成了10000个节点，每个节点的传输半径为500，以坐标(500,500)为中心作为接收节点R，计算所有落入接收节点区域的节点Ti,i=1,2,3…与节点R之间的有效覆盖面积图3-6随机分布的节点图3-7落入节点R内节点的平均有效覆盖率通过1000次仿真实验得到，在节点随机分布的条件下，Pavg≈41.35%。也就是说，节点第一次收到某条消息后，再次转发平均覆盖面积为Pavg=Pavg图3-8冗余消息数量与有效覆盖率的关系表3-3冗余消息数量与有效覆盖率的关系冗余消息数量平均有效覆盖率最大有效覆盖率141.35%60.90%217.10%37.09%37.07%22.59%42.92%11.76%51.21%8.38%60.50%5.10%70.21%1.11%80.09%1.89%90.04%1.15%从表3-3中可以看出，在接收到7条冗余消息时，节点再次转发的平均有效覆盖率仅为0.21%。在接收到第八条冗余消息时，有效覆盖率下降到了0.09%，再次转发的意义已经很小。当所有节点恰好都随机的分布在距离为r的圆周上时，冗余消息的有效覆盖面积取最大值，在接收到第8条冗余数据后，其有效覆盖率也仅为1.89%。在节点随机分布的情况下，节点数量与面积呈正相关关系。冗余消息数量代表着周围的已覆盖邻居节点的数量的最小值。在本设计中，将已覆盖邻居节点数两的值作为预期的冗余消息数量最大值，并以此作为依据计算节点的转发概率。2、节点的转发概率设计图3-9自裁剪算法在前面已经推导得到有效覆盖率和冗余广播之间的基本关系，而预期的冗余广播数量与邻居节点数量一致。下面将定义转发概率与邻居节点集的关系。设Ti为某次广播中的消息传递中的一个中继节点，R为此消息下一跳的中继节点，pi为节点Ti广播的消息副本，NTi表示节点Ti的邻居节点集，NR表示节点R的邻居节点集，N则在一次广播中，未覆盖邻居节点集为NRu在节点决定转发前一刻，假如接收到了k条消息p的副本，定义NT=(NR未覆盖邻居节点集NRu越大，转发概率应该设置的越高。在节点的转发有效覆盖率与冗余广播的关系的推导过程中，将未覆盖面积与总面积的比值定义为有效覆盖率，而在节点随机分布的情况下，节点面积正比于节点数量，因此在本小节，定义有效转发系数CR本设计面向的是高密度部署的蓝Mesh网络的冗余抑制问题，但在实际部署的网络中，也有可能存在局部比较稀疏的场景，这时在计算转发概率时，需要考虑网络的连通性。在上一小节的推导中，得到了平均有效覆盖率与冗余节点的关系，可以看到，网络也需要存在一定的冗余性。综合上述考虑，本设计采用分段函数作为节点计算转发概率的公式，本设计给出的转发概率计算公式为：Prelay其中Nc表示转发前已覆盖邻居节点集的数量，NRu表示在随机转发延迟到期后，该条消息的未覆盖邻居节点集合。在Nc小于8，且NRu≠0时，节点比较稀疏，只要还存在未覆盖的邻居节点，就以概率1转发，用以保证在稀疏网络中的连通性，在Nc大于8时，用有效转发系数计算转发概率，1.3随机转发延迟随机转发延迟(RandomRelayDelay,RRD)是减少广播冲突的重要手段。如果没有随机转发延迟，即使节点密度较小，由于BLE广播信道资源有限，也会有较大的可能性发生数据包冲突，这点在2.4.2节做了介绍。下面分析随机转发延迟与广播冲突的关系以及对蓝牙Mesh网络整体延迟的影响，并给出本文所设计的随机转发延迟策略。1、随机转发延迟与二次转发广播冲突的关系分析为了规避转发时的广播冲突问题冲突，可以通过随机化中继节点的转发前的延时时间减少节点同时占用同一信道资源的可能性。在蓝牙Mesh标准规范中，建议在数据包转发前增加一段随机转发延迟，但标准规范中未给出随机转发延迟的范围，下面将给出随机转发延迟的计算方法。在计算前先对网络做以下假设：网络中所有节点对与同一个数据包的无线电发射耗时长度相等，均为1。只要在某时间段内，有且仅有一个设备在占用广播信道进行广播时，扫描设备总能成功接收。如果两个设备的在某时刻广播区间发生重叠，重叠区间内数据包状态为无效。重叠区间外不受影响。设备可选择开始的广播时间范围为0-n的闭区间图3-10广播时间轴基于以上假设，下面推导两个节点转发时发生广播冲突的概率。如图3-10所示，假设蓝牙Mesh网络中有两个设备在接收到同一条广播后，决定在某随机的时刻进行转发，其可选广播初始时间的区间为[0,n由于广播开始时间的分布是随机的，因此落入数轴上所有点的概率相等，数轴上点落入的区间的概率pinterval与区间长度lPconflictPconflict图3-11随机转发延迟与二次转发碰撞概率的关系图3-11展示了随机转发延迟和二次转发碰撞概率的反比关系曲线，随机转发延迟越大，两次广播区间重合的概率越小，转发碰撞的概率也就越小。以上推算所得的冲突发生概率仅是重叠区间内的概率，由于节点的无线电范围完全重合的可能性较小，实际的冲突概率将会小于以上推算的值。在n=70时，其重叠区间的转发冲突概率为Pconflict=12、随机转发延迟给网络带来的平均延迟分析下面将结合文献ADDINNE.Ref.{44EC992C-DF07-426E-B8C7-F8B734B0C561}[39]中对Nordic实现的蓝牙Mesh协议栈的实际测试的部分数据来对随机转发延迟对整体网络延迟带来的影响进行直观的分析。在蓝牙Mesh网络中，网络延迟主要由三部分组成，分别是随机转发延迟，无线电发射时间(从37、38、39信道的发射耗时)，协议栈处理时间(蓝牙Mesh协议栈对数据包的加密解密，拆包组包等)。随机转发延迟平均值计算：引入随机转发延迟会增加蓝牙Mesh网络的网络延迟，一般来讲，随机延迟越大，总体网络延迟越大。易知，若节点的随机转发延迟上限为RRDmax，节点在[0,RRDmax无线电发射时间计算：BLE设备的物理层有1Mbps和2Mbps两个发射速率，在采用1Mbps物理层的情况下，设蓝牙Mesh中一个普通未分段消息组装为广播信道载荷时所占字节数