(硕士论文)图的连通度、强定向及无线传感器网络.pdf

文档介绍：图的连通度、强定向及无线传感器网络中文摘要中又摘要图论是一门富有趣味性和应用极为广泛的学科,它在化学、生物学、(K,d)定向以及图论在无线传感器网络中的应用等课题。无线传感器网络(WSN)、处理单元、,其应用已经由军事国防领域扩展到环境监测、交通管理、医疗健康、,传感器节点的能量通常是电池。由于网络成本及环境因素,这些电池能量耗尽后,,在保证网络覆盖以及网络畅通的基础上,如何延长网络的工作时间,是目前无线传感器网络研究的一个重要方面。在本文中,,假设已知所有监控的离散目标的具体位置,并在每个目标周围部署大量的传感器节点,,其中每个集合所包含的传感器节点能完全覆盖所有目标,。使得在任何时刻,都恰好只有处于活跃状态的节点负责监控与信息传输,,,并且乱口∈E(G)≠l,≠2?.,赴分别为z个需要监控的目标,Al,A2?.,A为图G的顶点子集,其中若顶点可所对应的传感器节点监控目标￡i,则口∈A,从而AnAf=D,l≤i<歹≤,我们将无线传感器网络的覆盖与能量有效性问题归结为图的不交ChineseAbstract集合覆盖与连通问题(’problem).定义1不交集合覆盖与连通问题pSCDpm6fe叫:设(Al,A2?.,Az)为图G的顶点划分。是否存在最大的整数七,使得存在G的两两点不交的连通子图G1,G2,?,G七满足,|y(G{)nAJI≥1,其中1≤i≤七和1≤J≤z?我们证明该问题是NP完全的,,我们给出该近似算法的理论分析及实验估计。,为了保证网络的畅通,,假设无线传感器网络的某些传感器节点同时负责监控与信息传输,,!个离散的监控目标,每个目标可同时处于奄个传感器节点的监控范围之内。设4l为G中对应于监控第i个目标的传感器节点所对应的顶点的集合,其中1≤i≤Z;设S为G的中心顶点集合,那么AinS=仍和AtnAf=D,其中1≤i≠歹≤,对应于无线传感器网络中监控所有目标,并且将监测到的信息传输给至少一个信息中心的节点的集合。因此,无线传感器网络的最大数量的不相交的传感器节点集合的数目,就是G中最大数量的这样的连通子图的数目。进一步地,,,A2?.,Az为图G的两两点不交的顶点子集,并且IAiI=七,1≤i≤z,s∈y(G)\u≮1月{.如果后=2和G是H—maX(1,z一4)连通的,或者七23和G是Z(七一1)+1连通的,那么存在七个连通子图G1?.,G南,使得(o)fy(G)nAI=1,其中l≤i≤七和l≤歹≤z;(6)y(Gi)ny(Gj)=fs),1≤i<歹≤,如果忌=2,并且无线传感器网络所对应的网络图G是Z+ma)({l,Z一4}连通的,或者七芝3和G是Z(七一1)+l连通的,那么可以找到七个(最大数量)传感器节点的不相交的集合,其中每个集合所包含的传感器节点完全覆盖所有目标,并且将监测到的信息有效地传输给信息中心,也就足可使无线传感器网络的工作时间提高老倍。同时,我们还证明了连通度条件Z(奄一1)+1连通是紧的,并且我们猜想当后