基于同调理论的WSN覆盖空洞检测算法研究
发布时间：2020-03-18 19:50
【摘要】：本学位论文的研究课题来源于国家自然科学基金“基于同调理论的无线传感器网络k重覆盖若干算法研究”(批准号:61601122)。主要针对节点位置和节点间距离信息未知的场景,对无线传感器网络(WSN,Wireless Sensor Network)的覆盖空洞检测算法进行了深入研究。论文利用同调理论中的Rips复形对WSN的拓扑进行建模,在保证覆盖拓扑特性不变的前提下,休眠冗余节点,简化Rips复形,再根据简化后的Rips复形提出空洞检测算法。论文的主要贡献如下:(1)根据WSN的特点,提出了一种基于相对方位角(RDA,Relative Direction Angle)信息的覆盖空洞检测算法。首先,在节点位置和距离信息未知的情况下,根据同调理论,利用节点之间的连通信息构建网络拓扑的Rips复形。其次,计算节点的权重大小,利用节点之间的RDA信息,休眠部分节点,并且断开冗余节点之间的连接,从而达到简化Rips复形的目的。进而,提出了基于RDA信息的覆盖空洞检测算法,根据RDA信息找出所有的空洞边界(BE,Boundary Edge),以检测出所有的覆盖空洞。仿真分析表明,所提算法能够在保持原有WSN拓扑特性的同时,减少网络中部署节点的个数,整个算法的复杂度为O(nm2),覆盖空洞检测的正确率能达到99%,,n为节点的个数,m为节点的平均邻节点个数。(2)在RDA信息未知的情况下,通过在Rips复形中引入联合Laplacian算子(JLO,Joint Laplacian Operator),提出了一种基于 Laplacian 矩阵(LM,Laplacian Matrix)的覆盖空洞检测算法。算法首先通过计算节点的权重大小,选择合适的候选休眠节点。其次,构建休眠节点的邻节点形成的子单纯复形,计算其LM零空间矩阵的维数,根据维数对节点进行休眠控制。由此,判断所有的候选节点,直到不再存在可以被休眠的节点,以达到简化拓扑的目的。然后,基于简化的Rips复形,先根据拓扑特性找出形成覆盖空洞的边界,再将空洞边界顺次连接即可检测出WSN中存在的覆盖空洞。仿真结果表明,所提算法能有效减少网络资源,复杂度为O(n2m4),覆盖空洞检测的正确率为99%,n为节点的个数,m为平均邻节点的个数。
【图文】：
逡逑类似的对于定向２－单形ｓ２邋＝邋［ｖ0，１＾，２＾］，如图２．６邋（ｂ）所示，它可以表示一逡逑个由构成的三角形区域，假设预定知方向为，这个方向和Ｖｏｈｈ、逡逑１＾１；。！＾、的方向相反，但是方向是一样的，且它们之逡逑间存在如下的关系逡逑［ｖ０＞ｖｌ＞＾２ｌ邋￣邋［ｖｌｉｖ２＞Ｖ0ｌ邋￣邋［ｖ２＞ｖ０＞ｖｌｌ邋＝邋￣［ｖ０＞ｖ２＞ｖｌｌ邋＝逦（２邋８）逡逑－［Ｖｉ，Ｖ0，Ｖ２］邋＝邋－＾Ｖ＾Ｖｑ］逡逑Ｖ］逡逑Ｖ＼逡逑＾逡逑（ａ）定向１－单形逦（ｂ）定向２－单形逡逑图２．６定向１－，，邋２－单形逡逑定向１－单形［ｖ，ｗ］的边缘定义为逡逑ｄ［ｖ，ｗ］邋＝邋ｗ邋—邋ｖ逦（２．９）逡逑定向２－单形［ｗ，邋Ｖ，邋ｗ］的边缘定义为逡逑ｄ［ｕ
逡逑如图２．７邋（ｂ）的边界映射，如２－单形［２，３，４］可以映射为三个１－单形［２，３］，邋［３，４］，逡逑［４，２］之和。经过图２．７邋（ｃ）的映射之后，所有１－单形最终都将映射为０，整个过逡逑程很好地解释了（２．１３）体现的复形链过程。逡逑Ｖ２逡逑（ａ．）邋ｋ＝邋２逡逑ｖ｛逦Ｖｉ逡逑么邋一邋Ａ．二。逡逑（ｂ）逦ｈ＝邋１逡逑ｒ0？逦＾＾．邋0逡逑（ｃ）逦Ａ＝邋０逡逑图２．７不同维度的边界映射操作逡逑定义２．３邋（闭链群）单纯复形Ｘ的Ａ维闭链群为Ｚｆｃ（；0二ｋｅｒ４。逡逑定义２．４邋（边缘链群）单纯复形Ｚ的Ａ：维边缘链群为Ｓｆｃ（；0邋＝邋ｉｍ３ｋ＋１。逡逑由定义２．３和２．４可以推出：Ａ：维闭链群Ｚｆｃ（；0的元素均是不包含边界的ｈ链，逡逑左维边缘链群则是所有属于认＋邋１）－链群边界的ｋ链集合。而且从式逡逑３ｆｃ°３ｆｃ＋１邋＝邋０可以看出，一个边界不属于也不包含任何边界，因此Ｓｆｃ（；0邋Ｇ邋＆（；0。逡逑定义２．５邋（同调群）单纯复形Ｚ的维同调群定义为如下商空间逡逑Ｈｋ00＝Ｚｋ00／Ｂｋ00逦（２．１５）逡逑定义２．６邋（贝蒂数）同调群／４（；0的维度即为单纯复形Ｚ的＆阶贝蒂数，即逡逑—邋ｄｉｍＨｆｃ（＾）邋－邋ｄｉｍＺｋ（Ｘ）邋—邋ｄｉｍ５ｆｅ（Ｘ）逦（２．１６）逡逑定义２．５表明，＆维同调群／４（；0是一组ｙＨ隹闭链群的等价类集合，而且两个逡逑免维边缘链群的差值是一个０＋邋１）链群的边界。计算贝蒂数时需要通过边界映射逡逑的矩阵求得，一般地构建了单纯复形便能得到相应的矩阵，不需要利用增量逡逑计算的算法。在单纯复形中
【学位授予单位】：东南大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TN929.5;TP212.9
本文编号：2589114
【图文】：
逡逑类似的对于定向２－单形ｓ２邋＝邋［ｖ0，１＾，２＾］，如图２．６邋（ｂ）所示，它可以表示一逡逑个由构成的三角形区域，假设预定知方向为，这个方向和Ｖｏｈｈ、逡逑１＾１；。！＾、的方向相反，但是方向是一样的，且它们之逡逑间存在如下的关系逡逑［ｖ０＞ｖｌ＞＾２ｌ邋￣邋［ｖｌｉｖ２＞Ｖ0ｌ邋￣邋［ｖ２＞ｖ０＞ｖｌｌ邋＝邋￣［ｖ０＞ｖ２＞ｖｌｌ邋＝逦（２邋８）逡逑－［Ｖｉ，Ｖ0，Ｖ２］邋＝邋－＾Ｖ＾Ｖｑ］逡逑Ｖ］逡逑Ｖ＼逡逑＾逡逑（ａ）定向１－单形逦（ｂ）定向２－单形逡逑图２．６定向１－，，邋２－单形逡逑定向１－单形［ｖ，ｗ］的边缘定义为逡逑ｄ［ｖ，ｗ］邋＝邋ｗ邋—邋ｖ逦（２．９）逡逑定向２－单形［ｗ，邋Ｖ，邋ｗ］的边缘定义为逡逑ｄ［ｕ
逡逑如图２．７邋（ｂ）的边界映射，如２－单形［２，３，４］可以映射为三个１－单形［２，３］，邋［３，４］，逡逑［４，２］之和。经过图２．７邋（ｃ）的映射之后，所有１－单形最终都将映射为０，整个过逡逑程很好地解释了（２．１３）体现的复形链过程。逡逑Ｖ２逡逑（ａ．）邋ｋ＝邋２逡逑ｖ｛逦Ｖｉ逡逑么邋一邋Ａ．二。逡逑（ｂ）逦ｈ＝邋１逡逑ｒ0？逦＾＾．邋0逡逑（ｃ）逦Ａ＝邋０逡逑图２．７不同维度的边界映射操作逡逑定义２．３邋（闭链群）单纯复形Ｘ的Ａ维闭链群为Ｚｆｃ（；0二ｋｅｒ４。逡逑定义２．４邋（边缘链群）单纯复形Ｚ的Ａ：维边缘链群为Ｓｆｃ（；0邋＝邋ｉｍ３ｋ＋１。逡逑由定义２．３和２．４可以推出：Ａ：维闭链群Ｚｆｃ（；0的元素均是不包含边界的ｈ链，逡逑左维边缘链群则是所有属于认＋邋１）－链群边界的ｋ链集合。而且从式逡逑３ｆｃ°３ｆｃ＋１邋＝邋０可以看出，一个边界不属于也不包含任何边界，因此Ｓｆｃ（；0邋Ｇ邋＆（；0。逡逑定义２．５邋（同调群）单纯复形Ｚ的维同调群定义为如下商空间逡逑Ｈｋ00＝Ｚｋ00／Ｂｋ00逦（２．１５）逡逑定义２．６邋（贝蒂数）同调群／４（；0的维度即为单纯复形Ｚ的＆阶贝蒂数，即逡逑—邋ｄｉｍＨｆｃ（＾）邋－邋ｄｉｍＺｋ（Ｘ）邋—邋ｄｉｍ５ｆｅ（Ｘ）逦（２．１６）逡逑定义２．５表明，＆维同调群／４（；0是一组ｙＨ隹闭链群的等价类集合，而且两个逡逑免维边缘链群的差值是一个０＋邋１）链群的边界。计算贝蒂数时需要通过边界映射逡逑的矩阵求得，一般地构建了单纯复形便能得到相应的矩阵，不需要利用增量逡逑计算的算法。在单纯复形中
【学位授予单位】：东南大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TN929.5;TP212.9
【参考文献】
相关期刊论文 前6条
1 温涛;张冬青;郭权;宋晓莹;;无线传感器网络冗余节点休眠调度算法[J];通信学报;2014年10期
2 张希伟;戴海鹏;徐力杰;陈贵海;;无线传感器网络中移动协助的数据收集策略[J];软件学报;2013年02期
3 曾志文;陈志刚;刘安丰;;无线传感器网络中基于可调发射功率的能量空洞避免[J];计算机学报;2010年01期
4 任彦;张思东;张宏科;;无线传感器网络中覆盖控制理论与算法[J];软件学报;2006年03期
5 马祖长,孙怡宁,梅涛;无线传感器网络综述[J];通信学报;2004年04期
6 任丰原,黄海宁,林闯;无线传感器网络[J];软件学报;2003年07期
本文编号：2589114
本文链接：https://www.wllwen.com/kejilunwen/wltx/2589114.html
