基于增量探测的大规模传感网导向性诊断理论与技术研究

Network diagnosis is crucial in managing a wireless sensor network (WSN) since many network-related faults, such as node and link failures, can easily happen. Diagnosis tools usually consist of two key components, information collection and root-cause deduction, while in most cases information collection process is independent with root-cause deduction. This results in either redundant information which might pose high communication burden on WSNs, or incomplete information for root-cause inference that leads false judgments. To address the issue, we propose DID, a directional diagnosis approach,in which the diagnosis information acquirement is guided by the fault inference process. Through several rounds of incremental information probing and fault reasoning, root causes of the network abnormalities with high credibility are deduced. We employ a node tracing scheme to reconstruct the topical topology of faulty regions and build the inference model accordingly. Combining an incremental probing scheme and a dynamic probabilistic inference model, DID effectively localizes the root causes of various network abnormalities. Additionally, the diagnosis is confined to topical area covering the problematic network elements in high potential. With a low overhead, a high accurate real-time network diagnosis service is thus provided.

无线传感器的故障诊断技术是保证无线传感器网络高效稳定运行的关键技术之一。现有无线传感器网络诊断方法中的大多数都存在信息收集与推理过程分离这一现象，这样会导致整个信息收集过程是静态和预定义的，无法适应无线传感器网络的高动态性特征。预定义的信息收集过程可能会造成两个不好的结果，过多的信息收集给网络带来了额外的通讯开销或是过少的信息收集使得原因推断产生过多的错误判断。基于这个观察，本项目组初步研究发现如果可以将信息搜集过程与诊断推理过程有效结合起来，将大大提高网络故障的诊断准确率。因此，本项目组提出了一种导向的无线传感器网络的诊断技术。在这个方法中，信息收集的过程是在概率推理模型的指导下进行的，随着信息收集不断完善，推理模型也不断得到细化，从而提高推理的准确率。同时，该方法通过动态获取潜在问题区域的拓扑关系，将诊断的范围限制在局部，从而有效地降低了网络诊断的开销。

无线传感器的故障诊断技术是保证无线传感器网络高效稳定运行的关键技术之一。本项目针对无线传感器网络的诊断进行了较为全面的研究，主要研究成果有：1.课题组系统研究了大规模无线传感器网络中的导向诊断方法，首次提出基于贝叶斯推断反馈的动态网络诊断系统。 首先课题组设计了一种拓扑追踪方法，该方法可以在节点上进行流量信息的标记进行记录，标记的内容与网络的数据包的流向是紧密相关的。当网络异常发生时，启动标记收集算法将潜在问题区域的拓扑进行恢复。然后，在恢复的初始拓扑上，通过分析网络故障的类型与网络元素之间的逻辑关系，建立了多层次的复合贝叶斯概率推理模型。2. 课题组研究了大规模基于射频识别的传感网中的批量验证方法，首次提出了次线性的批量射频标签验证的解决方法，并能够对批量标签中的真假标签数目进行准确估计。射频标签的批量估计是大规模射频标签广泛应用后带来的迫切性问题，之前的批量标签估计仅能够对批量标签中的是否含有假冒标签进行判断，而这样的结果是非常粗粒度的，因为它无法分辨批量标签中仅仅只含有一个假冒标签还是大部分标签都是假冒标签，同时之前的方法的扩展性不够好，无法实现次线性的验证时间。为此，课题组充分研究了批量标签验证中的扩展性问题，设计了一种高效的紧凑验证数据结构。该数据结构由独立的哈希函数生成，占用空间小，仅仅需要次线性空间。3. 课题组深入研究了基于射频识别的传感网中的复合标签数目估计问题。传统的标签数目在往往只针对一个数据集合，而实际应用中，往往需要对复合标签集合的数目进行估计。我们是首个提出复合标签集合估计这个问题，并且证明该问题的理论低极限值（Lower bound）。进一步地，我们提出了一种基于MinHash的复合估计策略，并证明该策略是最优解的log近似值，最后通过实际实验以及大规模仿真验证了我们策略的有效性。