基于二叉树冲突分解的物联网随机接入控制

2021-11-17杜银霞李红睿王春红

计算机仿真 2021年9期

杜银霞，李红睿，王春红

(1.河北工程技术学院，河北石家庄 050091;2.河北科技大学，河北石家庄 050000)

1 引言

物联网能够借助信息传感设备，将设备与Internet连接起来，按照统一制定的协议，进行通信和信息交换，实现不同设备之间的数据通信，而随着物联网设备的增加，支持通信网络的需求也随之增加，例如船舶飞机、跨省列车、卫星等，这些应用需求都需要物理层的接入技术，实现高频次的数据传输，因此，对物联网随机接入进行研究，具有重要意义[1]。

国外物联网随机接入研究较早，提出多种随机接入协议，定位发射端节点，在多个时隙上发送数据包，联合多用户连续干扰消除技术，使接收端对数据包进行译码，得到每个数据包信令中，包含的复本位置信息，再随机选择两个时隙，通过发射端发送同一数据包的两个复本，采用迭代干扰消除算法，使接收端解决数据包冲突问题，同时牺牲能量效率，对每个数据包发送不规则数目的复本，避免数据传输的吞吐量受限。国内物联网随机接入研究，同样取得较大发展，设置共享的随机接入信道，根据随机多址协议，建立通信终端接入物联网的场景，利用随机竞争方式，使节点在公平条件下，以竞争的方式连接信道，融合协议和二叉树冲突分解算法，避免连接节点与其它节点协商[2]。

在以上理论的基础上，提出基于二叉树冲突分解的物联网随机接入控制方法，在随机接入协议中，利用二叉树冲突分解算法，解决信道中信息分组的碰撞、拥塞冲突，确保节点间信息数据的高频次传输。

2 基于二叉树冲突分解的物联网随机接入控制方法设计

2.1 制定物联网随机接入路由协议

根据物联网的网络性能，制定物联网随机接入路由协议。使用多点传播技术，优化链路状态协议，对该协议进行扩展，使其满足物联网的网络需求，得到物联网随机接入的OLSR路由协议[3]。通过OLSR协议，将物联网划分为3个覆盖等级，具体如图1所示。

图1 物联网接入协议的终端分布

根据终端所在信道环境，确定物联网覆盖等级，当最大耦合损耗超过165dB，等级为2，在145～165dB之间，等级为1，低于145dB，等级为0。在物联网随机接入前，采用单音跳频的传输方式，结合符号组的概念，将5个符号和1个循环前缀，作为一个符号组，生成序列前导，并根据不同的覆盖等级，对随机接入信道参数进行配置[4]。具体跳频前导方案如图2所示。

图2 单音跳频前导方案

如上图所示，灰色物理资源块表示一个前导，通过全“1”序列，扩展生成前导序列包络，通过子载波间隔和随机接入信道带宽，确定前导个数。采用跳频的方式，定时估计基站端的到达时间，使前导仅包含时频资源块，从而保证不同覆盖等级下，生成序列的前导长度，在随机接入前，为节点基站累积足够的能量[5]。在OLSR协议下，每个节点第一次收到消息时，对消息进行重传，具体配置如表1所示。

表1 重发传输机制的信道配置

设置覆盖等级2的最大重发次数为125，资源配置的前导周期最长，随着等级的减小，降低重发次数并缩短前导周期，以此避免物联网接入信道的资源消耗。接入信道配置完毕后，最小化OLSR协议的控制分组，使所有节点通过OLSR协议的控制分组，对物联网拓扑信息进行收集，并将拓扑信息存储在不同信息域中，让节点得到整个物联网的拓扑结构，使物联网随机接入时，可以直接转发数据包的对应节点[6]。至此完成物联网随机接入路由协议的制定。

2.2 计算物联网最优路由接入链路

优化最短路径算法，选择节点转发的最优通信链路。将字节长度作为OLSR协议的分组长度，刷新一个OLSR分组传递，就增加一个新的分组序列号，使每个物联网随机接入接口，都匹配到单独的分组序列号[7]。识别分组信息的有效时间域V为

(1)

式中，a、b分别表示时间域的高四位整数、低四位整数，ζ为比例因子[8]。当时间域V内，没有识别出分组包含的信息数据，就将该分组进行丢弃，仅接受OLSR协议的有效分组。然后建立节点的重复集合，记录接收分组的相关内容，确保无重复的检查分组信息头部，去除已处理的信息、以及分组长度小于分组头部的信息，对剩余分组进行逐跳转发。转发过程中，首先检测节点接入链路的方向性，周期广播该节点的邻居节点、以及邻居节点链路状态，选择存在双向链路的邻居节点。设转发节点为j，邻居节点为i，则节点间链路信道的MAC层帧成功率ξ为

ξ=G(j)/N(i)

(2)

式中，G(j)为节点j发送MAC帧的总数量，N(i)为节点i成功接收的数量[9]。链路接口队列的占用率η计算公式为

η=L(i)/C(i)

(3)

式中，L(i)为邻居节点iMAC层接口队列中，现有排队的分组个数，C(i)为接口队列排队的最大可容纳分组个数[10]。通过MAC层帧成功率和接口队列占用率，更新转发节点的链路状态，其节点间链路状态良好程度S(i，j)计算公式为

(4)

式中，Ki、Kj分别为节点i和节点j的空闲度，表示节点能够接纳后续负载的能力，α和β为预设指数[11]。综合考虑两跳邻居集合的连通度、以及节点间链路状态良好程度，计算一跳邻居节点i的优先选择因子Q，公式为

Q=d(τ)/S(i，j)

(5)

其中d(τ)为邻居集合τ的连通度，即τ为转发节点存在双向链接的节点个数[12]。通过公式(5)，选择节点间的最优链接路径，使物联网中每个节点都维持一个OLSR路由协议，使其能够找到下一跳的转发节点、目的节点地址，确定节点逐跳转发序列的源节点和目的节点，构成一条物联网随机接入的最优路径路由。至此完成物联网最优路由接入链路的计算。

2.3 基于二叉树冲突分解控制物联网接入链路冲突

利用二叉树冲突分解算法，控制接入链路信道的信息碰撞冲突。通过最优路由接入链路，发送包含节点信息的分组序列，利用二叉树冲突分解算法，针对同一时隙发生冲突的信息分组，将其编为一组，同时让与碰撞无关的信息分组暂时等待，当冲突解决完毕后，继续发送信息数据。信息碰撞的分解过程如图3所示，圆圈数字表示发生冲突的信息分组数目。

图3 二叉树冲突分解算法冲突分解过程

如图3所示，当同一时隙上等待传输的信息分组为0，将该时隙看作空时隙，不进行分组传输，当信息分组为1，则立刻发送分组，当信息分组为2个或2个以上，则对碰撞的信息分组进行分解。计算信道冲突的平均分解次数E，公式为

(6)

其中p为传输时，一个时隙分配到信息分组的成功率，φ为信道碰撞的信息分组数，k为分配不成功的概率。经过E次分解后，将碰撞的信息分组划分为多个子集，直至时隙空闲或时隙传输成功，退出冲突分解，确保物联网接入链路中，信息分组的成功传送，实现物联网接入链路冲突的控制。至此完成基于二叉树冲突分解算法，物联网随机接入控制方法的设计。

3 实验论证分析

将此次设计方法记为实验A组，两种传统物联网随机接入控制方法，分别为实验B组和实验C组，比较物联网随机接入后，节点传输信息数据的性能指标。共有 12 个 Lora 终端，采集温度与湿度。网关通过路由器与业务服务器连接，业务服务器即 PC 一台。Lora 网关将 Lora终端采集的信息上传至业务服务器，最核心的部分为 Lora 网关。

图4 随机接入控制方法验证平台模型实物图

3.1 实验准备

采用MATLAB仿真软件进行仿真，假设物联网的网络覆盖范围内，各节点均服从均匀分布，则实验的设置参数如下表所示：

所有具有物联网接入需求的终端，都在接入周期开始时刻发送接入请求，即周期内不存在新的接入请求。仿真环境考虑噪声和信道衰落的影响，使用ITU-R M.1225信道模型，设置多普勒频移为30kHz、莱斯因子为10dB，分别给出链路信道的小尺度衰落和大尺度衰落，并使其服从对数正态分布，标准差为3dB，均值为0dB，链路信道的带宽为2.5Mbps，捕获阈值为5dB，节点缓冲区可容纳55个信息分组。

3.2 实验结果

3.2.1 第一组实验结果

所有仿真节点都配置两块无线网卡，使用Waypoint运动模型，该模型运动范围为2000m×2000m，最大运动速度为30m/s，在缓冲区的停留时间为25s，网卡分别工作在两个互不干扰的信道上。选取三种不同长度的数据包，符号数目分别为60、40、20，信噪比范围分别为[6.5dB，10.8dB]、[10.8dB，20dB]、[20dB，∞]，数据包的比特数目都为1310，编号数据包分别为1、2、3，比较物联网随机接入后，不同归一化负载下传输数据包的吞吐量，实验结果如图5所示。

表2 仿真参数初始设置

图5 数据包1的吞吐量对比结果

由上图可知，当数据包符号数目为60时，实验A组的峰值吞吐量达到291kb/s，实验B组和C组的峰值吞吐量分别为249kb/s、239kb/s，相比实验B组和C组，A组数据吞吐量分别提高了42kb/s、52kb/s。第二种数据包的实验对比结果如图6所示。

图6 数据包2的吞吐量对比结果

由上图可知，当数据包符号数目为40时，实验A组的峰值吞吐量达到271kb/s，实验B组和C组的峰值吞吐量分别为233kb/s、191kb/s，相比实验B组和C组，A组数据吞吐量分别提高了38kb/s、80kb/s。第三种数据包对比结果如图7所示。

图7 数据包3的吞吐量对比结果

由7图可知，当数据包符号数目为20时，实验A组的峰值吞吐量达到238kb/s，实验B组和C组的峰值吞吐量分别为171kb/s、124kb/s，相比实验B组和C组，A组数据吞吐量分别提高了67kb/s、114kb/s。

3.2.2 第二组实验结果

选择符号数目分别为40的数据包，设置接入链路的信道比为20dB，调节数据流的发送速率，设置仿真时间为500s，比较数据包端到端的延迟时间，实验结果如表3所示。

表3 传输数据延迟时间对比结果

由表3可知，实验A组传输数据的平均延迟时间为0.23s，实验B组和实验C组的平均延迟时间分别为0.37s、0.41s，相比实验B组和C组，A组延迟时间分别缩短了0.14s、0.18s。

3.2.3 第三组实验结果

前两组实验接入周期开始时刻的接入请求数为300，请求数较少，物联网随机接入的成功率为100%，增加接入请求数量，比较三组实验的接入成功率，对比结果如表4所示。

表4 物联网接入成功率对比结果(%)

由表4可知，实验A组平均接入成功率为84.1%，实验B组和实验C组的平均成功率分别为79.6%、73.7%，相比实验B组和实验C组，A组成功率分别提高了4.5%、10.4%。综上所述，此次设计方法提高了物联网随机接入的成功率，能够处理大批量接入请求的节点设备，在此基础上，提高了数据吞吐量，使节点通信时不需要多次重发信息数据，降低了物联网接入的能量耗损，同时缩短了传输数据延迟时间，确保了物联网接入后的通信效率。