WSN中基于端到端的贪婪故障定位算法

摘要

为了维持无线传感器网络的正常运行，所有的故障链路需要被精确定位。将该问题转换为基于端到端的数据引导，以减少主动监测次数为目的的最优监测序列的问题。提出了通过拓扑拆分得到故障子图，并通过子图的概率集进一步计算节省主动探测次数的基于节点监测多条链路的启发式贪婪算法NTHG（node testing using heuristic greedy）。仿真结果表明仅需要监测小部分的节点，就可以定位网络中所有的故障链路。与该问题最新的解决算法LTHG（link testing using heristic greedy）相比，新算法需要更少的监测次数和平均CPU 耗时，从而很好地降低了网络能耗，缩短了故障定位耗时。%In order to sustain the health of the network,all of the fault links need to be localized.This paper formulated a problem of optimal sequential testing guided by end-to-end data,and proposed NTHG.It picked the node that provided the highest gain,which from knowing the status of the path probability in sub-graph topology was defined as the cost saving.Exten-sive simulation shows that NTHG only require test a very small set of network components to localize all faults in the network. Compared with the existing alorithms LTHG,the new alorithms palces fewer relays and active measurements than LTHG does.