基于无线传感器网络的事件监测算法研究

发布时间：2020-07-13 17:11

【摘要】：由具有感知、计算和通信功能的造价低廉的传感器节点以无线通信方式形成的自组织地网络系统即为无线传感器网络(WSNs)。无线传感器网络通过协作地采集、感知、分析环境信息,达到监测用户感兴趣的事件的目的。首先,传感器节点通过感知元件对物理对象进行信息采集;其次,数据信息以无线通信方式与逻辑计算设备进行网络信息交换。无线传感器网络不仅实现了高效的信息采集,而且构建了物理世界与虚拟计算世界的有效连接。无线传感器网络的自组织性和协作性为其开辟了广阔的应用前景,无线传感器网络被广泛地应用于空间探索、电力监控、医疗护理、智能交通、绿色建筑、智能家居、灾难预警等诸多领域。在基于无线传感器网络的事件监测应用中,准确、实时的事件信息有助于用户做出正确的分析和决策,能够有效地避免生命安全和财产损失事故的发生。然而,无线传感器网络具有资源受限和设计约束的特点。资源受限是指传感器节点具有受限的无线通信范围、有限的电源供给、低带宽、有限的计算能力和存储能力等特点。设计约束是指无线传感器网络的设计取决于其应用目的和所监测的物理环境。针对上述挑战,开展基于无线传感器网络的有效的、轻量级、高能效性的分布式事件监测算法和实时数据传输策略的研究十分重要,是无线传感器网络技术研究中极具挑战性的前沿性研究领域。本文的主要研究成果概括如下:(1)本文研究了Top-k监测问题,提出了基于过滤器的Top-k监测算法。无线传感器网络中的Top-k监测返回k个最大(或最小)的感知值及相应的位置信息。感知数据的Top-k查询结果可以帮助用户检测异常事件并定位发生异常事件的位置,对于用户具有重要的实际意义。然而,已有的Top-k查询处理算法致力于返回精确或近似的查询结果,没有考虑算法的通信能量开销,降低了算法的能效性。旨在降低通信复杂度,延长网络寿命,本文以最小化网内通信能量的期望为优化目标,开展了基于过滤器的Top-k监测算法的研究。本文给出了通信能量开销模型并分析了其物理意义,首次提出了过滤器的健壮性,并给出了其严格的形式化定义。根据期望的均值内涵和感知数据的时空相关性,本文给出了过滤器失败概率的计算公式。以最小化通信能量的期望为优化目标,本文证明了健壮的过滤器的最优阈值,提出了基于过滤器的Top-k监测算法。通过理论分析和真实感知数据的模拟实验,本文验证了提出算法的正确性以及高能效性。(2)本文研究了基于双阈值的事件监测问题,提出了分布式的(α,τ)-监测算法。受到感知硬件误差和环境噪声的影响,不确定性和误差广泛地存在于传感器节点采集的感知数据中。当噪声扰动或仪器误差引起感知值的严重偏离时,基于单一阈值的监测方法将导致较高的警报误报率和警报漏报率。为了克服单阈值监测算法的不足,提高警报信息的准确率,本文开展了带有概率保证的监测算法的研究,提出了轻量级的分布式(α,τ)-监测算法。其主要思想为对于给定的监测阈值α和概率阈值τ,节点计算感知数据大于α的概率的上界,并考察其上界是否超出概率阈值τ。本文提出了关键点的(α,τ)-监测问题并给出了其形式化定义和概率语义,并证明了感知数据大于监测阈值α的概率的紧上界,提出了计算开销为O(1)的关键点的(α,τ)-监测算法。进一步地,本文开展了区域的(α,τ)-监测问题的研究。给出了计算聚集值大于监测阈值的概率上界的数学方法,并提出了计算开销为O(n)的区域的(α,τ)-监测算法。本文提出了近似的连续(α,τ)-监测问题,其语义为满足近似要求的警报概率大于阈值τ时,节点向用户发送警报信息。本文给出了根据ε、δ确定优化样本容量的数学方法,并提出了基于抽样的近似(α,τ)-监测算法。通过理论分析和模拟实验,本文验证了提出的监测算法的高效性。(3)本文研究了小概率事件监测问题,提出了优化的近似τ-分位数算法。准确地描述感知数据的尾概率分布是监测小概率事件的关键技术。对于给定的小数τ,τ-分位数能够有效地描述底层数据的尾概率分布,已有的研究工作忽略了传感网中高能效的近似τ-分位数计算算法的设计。在以计算近似分位数概要为主旨而收集的感知数据中,仅有少量数据有助于计算τ-分位数。本文提出了τ-分位数的(ε,δ)-近似估计,给出了根据精度要求ε、δ以及τ计算优化的样本容量的数学方法。基于上述数学方法,本文提出了优化的近似τ-分位数算法,使得近似τ-分位数结果以低通信开销的聚集方式在网内传播。进一步地,本文对抽样算法性能进行了理论分析,证明了对于给定的τ和ε,样本容量是全网感知数据集合的势的log级,理论地证明了提出算法的高能效性。通过真实感知数据的模拟实验,本文验证了提出的近似τ-分位数算法的正确性和有效性。(4)本文开展了为各节点设置优化的重传阈值的研究,提出了计算优化的重传阈值的精确算法和近似算法。数据传输的时延是无线传感器网络中实时监测的关键技术。节点的重传阈值对数据包在指定的截止期限前成功地到达目的节点的概率具有重要影响。然而,已有的研究工作忽略了传输路径上各中继节点的重传阈值的优化,没有综合地考虑各传输链路质量以及数据包的实时要求,降低了数据包在指定的截止期限前到达目的节点的概率。因此,本文给出了为传输路径上的各节点设置优化的重传阈值的问题定义,并形式化为一般的整数组合优化问题。为了求解最优重传阈值,本文提出了基于动态规划技术的分布式算法(DPDA),证明了算法的正确性,并分析了算法的计算复杂度及其空间复杂度分别为O(n?·max1≤i≤n{ui})和O(n?·max1≤i≤n{ui})。当?的阶高于n的多项式函数时,本文设计了基于线性规划技术的(1+pmin)-近似算法(LPAA)。进一步地,当重传阈值的取值范围较大时,本文提出了基于拉格朗日乘子法的分布式近似算法(LMDAA),并分析了算法的计算复杂度为O(1)。通过理论分析和模拟实验,本文验证了提出的算法在实时数据传输方面具有较好的性能。
【学位授予单位】：哈尔滨工业大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TP212.9;TN929.5

【相似文献】