论文部分内容阅读
2016年，国务院安委会下发《金属非金属地下矿山采空区事故隐患治理工作方案》，明确指出地下矿山开采安全管理工作的重要性。通过物联网(IoT，Internet of Things)技术在矿山部署传感器，可以实现数据的识别、定位、监管等功能，因此，基于物联网技术进行矿山安全施工监测具有重要意义。鉴于矿井下应急救援的需求，在矿井塌陷的情况下，无法采用常规的供电方式，因此现有的技术方案大多数是基于IEEE802.15.4的低功耗MAC(Media Access Control)协议，例如ZigBee，通过CSMA/CA(Carrier Sense Multiple Access with Collision Avoid)算法在MAC层实现无线信道接入。不过，不同于露天开采，矿井下的特殊应用环境使得现有方法仍然面临挑战:首先在矿井下需要部署大量传感器，特别是人员定位传感器，其具有移动性的特点，在某个时间段可能会导致某些区域的无线设备聚集，增加无线数据碰撞的概率，而CSMA/CA算法无法在大数据量的情况下保证数据传输的可靠性;其次，CSMA/CA算法通过随机退避的方式竞争无线资源，当设备较多时，可能会造成较大的通信延迟;最后，矿井下物联网需要根据巷道走向来部署，因此需要针对其特殊的拓扑结构来进行算法设计。
基于以上背景，为了解决传输可靠性和通信延迟的问题，根据TDMA(Time Division Multiple Access)方法的特点，本文研究基于时隙调度的MAC协议关键技术，根据矿井下不同的巷道拓扑结构进行相关算法设计和分析。与此同时，由于时钟同步是时隙调度算法的必要条件，本文研究矿井下时钟同步方法。由于现有的同步方法侧重于两点之间同步精度和能耗的研究，且同步方法依赖于同步消息的收发，而在矿井下特殊条件下，无线干扰使得这些方法无法满足鲁棒性的需求，因此，本文研究符合矿井下时隙调度需求的同步方案。综上，本文的主要贡献如下:
(1)为了分析矿井下物联网的无线传输的基本需求，基于矿井下施工环境及物联网的部署方式，研究通用的矿井下多信道时隙调度问题。对该问题的计算复杂性进行理论分析，证明该问题是一个NP-Hard问题，然后提出一个通用的基于贪心思想的多信道时隙调度算法，理论化分析算法的有效性。与此同时，根据矿井下大量传感器数据的实际情况，在时隙调度问题基础上，提出一个多数据流的选择问题，并且提出对应的解决方案，最后进行必要的理论分析。
(2)为了解决矿井下不同巷道拓扑结构的多信道时隙调度问题，分别针对两种不同拓扑结构，进行相关算法的设计和分析。首先研究一种链式混合拓扑的矿井下物联网结构，分析多信道时隙调度问题的贪心算法在该拓扑结构下的最优性。其次，面向矿井下物联网的一种树状混合拓扑的特殊应用，研究一个更复杂的多信道时隙调度问题。理论化的分析其计算复杂性，同时分析在矿井下特殊树状混合拓扑结构下，提出的贪心算法在满足可调度的前提下能够得到最优化的调度结果。最后分别对两种拓扑结构下的贪心算法的丢包率和平均延迟进行了对比分析，实验结果表明提出的贪心算法具有较低的丢包率和平均延迟。
(3)为了解决矿井下传感器无线数据的多基站接入问题，研究特殊的基于延迟约束的多基站多信道时隙调度问题，通过计算复杂性分析，证明该问题是NP-Hard的。提出一个基于截止期优先的启发式算法来解决这个问题，包含预分配和动态调整两个部分:第一，通过最小截止期优先的预分配算法可以保证截止期较小的数据优先调度，降低延迟;第二，通过动态调整算法，可以使得更多的数据包接入信道。最后进行了对比实验分析，实验结果表明提出的算法具有较小的丢包率和较低的平均延迟。
(4)为了解决矿井下时隙调度算法面临的时钟偏移问题，研究并设计一个矿井下时钟同步方案，包括基站和传感器不同的时钟同步机制。采用动态超帧的设计思想，将超帧进行有效划分，在每个超帧的最后一段时隙进行时钟偏移量的估计，并且根据估计结果动态的调整下一个超帧的大小。最后分别从同步精度、能耗和鲁棒性三个方面对提出算法进行对比分析，实验结果表明提出的同步算法具有较好的性能。
本文研究了矿井下物联网无线MAC协议关键算法，设计的相关算法符合矿井下物联网无线数据实时、可靠传输的需求，并且从理论化的角度对问题进行复杂性和最优化的分析，具有一定的理论和工程参考价值。
基于以上背景，为了解决传输可靠性和通信延迟的问题，根据TDMA(Time Division Multiple Access)方法的特点，本文研究基于时隙调度的MAC协议关键技术，根据矿井下不同的巷道拓扑结构进行相关算法设计和分析。与此同时，由于时钟同步是时隙调度算法的必要条件，本文研究矿井下时钟同步方法。由于现有的同步方法侧重于两点之间同步精度和能耗的研究，且同步方法依赖于同步消息的收发，而在矿井下特殊条件下，无线干扰使得这些方法无法满足鲁棒性的需求，因此，本文研究符合矿井下时隙调度需求的同步方案。综上，本文的主要贡献如下:
(1)为了分析矿井下物联网的无线传输的基本需求，基于矿井下施工环境及物联网的部署方式，研究通用的矿井下多信道时隙调度问题。对该问题的计算复杂性进行理论分析，证明该问题是一个NP-Hard问题，然后提出一个通用的基于贪心思想的多信道时隙调度算法，理论化分析算法的有效性。与此同时，根据矿井下大量传感器数据的实际情况，在时隙调度问题基础上，提出一个多数据流的选择问题，并且提出对应的解决方案，最后进行必要的理论分析。
(2)为了解决矿井下不同巷道拓扑结构的多信道时隙调度问题，分别针对两种不同拓扑结构，进行相关算法的设计和分析。首先研究一种链式混合拓扑的矿井下物联网结构，分析多信道时隙调度问题的贪心算法在该拓扑结构下的最优性。其次，面向矿井下物联网的一种树状混合拓扑的特殊应用，研究一个更复杂的多信道时隙调度问题。理论化的分析其计算复杂性，同时分析在矿井下特殊树状混合拓扑结构下，提出的贪心算法在满足可调度的前提下能够得到最优化的调度结果。最后分别对两种拓扑结构下的贪心算法的丢包率和平均延迟进行了对比分析，实验结果表明提出的贪心算法具有较低的丢包率和平均延迟。
(3)为了解决矿井下传感器无线数据的多基站接入问题，研究特殊的基于延迟约束的多基站多信道时隙调度问题，通过计算复杂性分析，证明该问题是NP-Hard的。提出一个基于截止期优先的启发式算法来解决这个问题，包含预分配和动态调整两个部分:第一，通过最小截止期优先的预分配算法可以保证截止期较小的数据优先调度，降低延迟;第二，通过动态调整算法，可以使得更多的数据包接入信道。最后进行了对比实验分析，实验结果表明提出的算法具有较小的丢包率和较低的平均延迟。
(4)为了解决矿井下时隙调度算法面临的时钟偏移问题，研究并设计一个矿井下时钟同步方案，包括基站和传感器不同的时钟同步机制。采用动态超帧的设计思想，将超帧进行有效划分，在每个超帧的最后一段时隙进行时钟偏移量的估计，并且根据估计结果动态的调整下一个超帧的大小。最后分别从同步精度、能耗和鲁棒性三个方面对提出算法进行对比分析，实验结果表明提出的同步算法具有较好的性能。
本文研究了矿井下物联网无线MAC协议关键算法，设计的相关算法符合矿井下物联网无线数据实时、可靠传输的需求，并且从理论化的角度对问题进行复杂性和最优化的分析，具有一定的理论和工程参考价值。