图的连通度、强定向及无线传感器网络

论文摘要

图论是一门富有趣味性和应用极为广泛的学科,它在化学、生物学、计算科学以及通信网络等方面都有广泛的应用。本文主要研究图的强定向和最优强（K,d）定向以及图论在无线传感器网络中的应用等课题。无线传感器网络（WSN）是由部署在监测区域内大量的微型传感器节点通过无线电通信形成的一个网络系统.传感器节点由传感单元、处理单元、无线收发单元和电源单元等几部分组成。无线传感器网络的出现引起了全世界广泛关注,其应用已经由军事国防领域扩展到环境监测、交通管理、医疗健康、工商服务和反恐抗灾等诸多领域。在无线传感器网络中,传感器节点的能量通常是电池.由于网络成本及环境因素,这些电池能量耗尽后,就无法再充电或更换电池而继续使用.因此,在保证网络覆盖以及网络畅通的基础上,如何延长网络的工作时间,是目前无线传感器网络研究的一个重要方面。在本文中,我们提出了一种新型的无线传感器网络.在此网络中,假设已知所有监控的离散目标的具体位置,并在每个目标周围部署大量的传感器节点,而后将节点所监测到的信息传输给一个或多个信息中心.将所有的传感器节点分成最大数量的不相交的传感器节点的集合,其中每个集合所包含的传感器节点能完全覆盖所有目标,并且将监测到的信息有效地传输给信息中心.然后将这些集合所包含的传感器节点依次激活。使得在任何时刻,都恰好只有处于活跃状态的节点负责监控与信息传输,而其余节点能量耗尽或处于睡眠状态.这种方法是延长无线传感器网络工作时间的一种较有效的方式.因此,我们的目标就是找出最大数量的不相交的传感器节点集合.将无线传感器网络的每个节点看成图G的一个顶点,并且uv∈E（G）当且仅当u和v所对应的传感器节点在彼此的传感范围之内.通常称G为网络图.我们考虑此类型无线传感器网络的三种不同的模型.1.假设无线传感器网络的每个传感器节点恰好只监控一个目标.设t1,t2,…,tι分别为ι个需要监控的目标,A1,A2,…,Aι为图G的顶点子集,其中若顶点v所对应的传感器节点监控目标ti,则v∈Ai,从而Ai∩Aj=（?）,1≤i<j≤ι.在这个模型下,我们将无线传感器网络的覆盖与能量有效性问题归结为图的不交集合覆盖与连通问题（DSCC.problem）.定义1不交集合覆盖与连通问题（DSCC-problem）:设（A1,A2,…,Aι）为图G的顶点划分.是否存在最大的整数k,使得存在G的两两点不交的连通子图G1,G2,…,Gk满足,|V（Gi）∩Aj|≥1,其中1≤i≤k和1≤j≤ι?我们证明该问题是NP完全的,进而给出一个相关的近似算法.最后,我们给出该近似算法的理论分析及实验估计.2.有时两个需监测的目标之间或目标与信息中心之问的距离较远,为了保证网络的畅通,需要部署一些只负责信息传输的传感器节点.在此模型中,假设无线传感器网络的某些传感器节点同时负责监控与信息传输,其余的传感器节点只负责信息传输.在网络图G中,称信息中心节点所对应的顶点为中心顶点.假定无线传感器网络有ι个离散的监控目标,每个目标可同时处于k个传感器节点的监控范围之内.设Ai为G中对应于监控第i个目标的传感器节点所对应的顶点的集合,其中1≤i≤ι;设S为G的中心顶点集合,那么Ai∩S=（?）和Ai∩Aj=（?）,其中1≤i≠j≤ι.G的包含S的一个顶点以及每个Ai的一个顶点的连通子图,对应于无线传感器网络中监控所有目标,并且将监测到的信息传输给至少一个信息中心的节点的集合.因此,无线传感器网络的最大数量的不相交的传感器节点集合的数目,就是G中最大数量的这样的连通子图的数目.进一步地,包含多个信息中心节点的无线传感器网络的覆盖与能量有效性问题可归化为只包含一个信息中心节点的覆盖与能量有效性问题.因此,我们假设网络图G只有一个中心顶点s.我们找到图的一个参数-连通度来达到无线传感器网络的覆盖与能量有效性.定理1设A1,A2,…,Aι为图G的两两点不交的顶点子集,并且|Ai|=k,1≤i≤ι,s∈V（G）∪i=1ιAi.如果k=2和G是ι+max{1,ι-4}连通的,或者k≥3和G是ι（k-1）+1连通的,那么存在k个连通子图G1,…,Gk,使得（a） |V（Gi）∩Aj|=1,其中1≤i≤k和1≤j≤ι;（b） V（Gi）∩V（Gj）={s},1≤i<j≤k.由定理1,如果k=2,并且无线传感器网络所对应的网络图G是ι+max{1,ι-4}连通的,或者k≥3和G是ι（k-1）+1连通的,那么可以找到k个（最大数量）传感器节点的不相交的集合,其中每个集合所包含的传感器节点完全覆盖所有目标,并且将监测到的信息有效地传输给信息中心,也就是可使无线传感器网络的工作时间提高k倍.同时,我们还证明了连通度条件ι（k-1）+1连通是紧的,并且我们猜想当k=2时,ι+1连通是足够的。猜想1设A1,A2,…,Aι为图G的两两点不交的顶点子集,并且|Ai|=2,1≤i≤ι,s∈V（G）∪i=1ιAi如果G是ι+1连通的,那么存在连通子图G1,G2,使得（a） |V（Gi）∩Aj|=1,其中i=1,2和1≤J≤ι;（b） V（G1）∩V（G2）={s}.最后,我们也给出了相应的算法来找出这k个传感器节点的集合。3.通常情况下,同时负责信息传输与监控的传感器节点的能量消耗比只负责信息传输的传感器节点的能量消耗来得快些.在模型2的基础上,假设那些只负责信息传输的传感器节点的工作时间,是那些同时负责监控与信息传输的节点的工作时间的d倍.设同时负责信息传输与监控的传感器节点的工作时间为一单位时间。同模型1与2一样的考虑,我们将全部传感器节点划分为多个集合,使得每个节点的集合既能监控所有目标,又能保证将监测到的全部信息传输给信息中心.但是,某个只负责信息传输的传感器节点可能会同属于两个或多个不同的传感器节点的集合。而且由于环境因素及成本考虑,在每个传感器节点上安装开关是不太可能实现的.因此,我们假设每个传感器节点一旦被激活就不能被关闭,直到能量耗尽。从而,那些含有共同传感器节点的任意两个集合,它们所含的传感器节点被激活的时间间隔不能超过d个单位时间.特别的,如果一个节点已被激活,若它还属于另一个即将被激活的节点集合,则该传感器节点无需再次激活.我们的目标就是寻找最大数量的有序的节点的集合,使得每个集合所含的传感器节点的传感范围能完全覆盖所有目标,并保证将监测到的全部信息传输给信息中心,而且对于任两个含有共同传感器节点的集合,它们的序号之差不能超过d.对应于网络图G,我们的目标就是寻找最大数量的包含点s且包含每个Ai的顶点的有序连通子图G1,G2,…,Gp,使得任意两个子图Gi和Gj,如果它们包含除s外的共同顶点,那么|i-j|≤d-1.我们证明了,即使无线传感器网络所对应的网络图满足一定的连通度的条件,要找出无线传感器网络的最优工作时间仍是NP完全的.我们给出一个近似算法来提高无线传感器网络的工作时间,并且给出该算法的理论分析与实验估计.众所周知,在交通系统中应用单行道,不仅会减少交通事故,而且可以简化交通控制管理.单行道问题的图论模型最初是由Rabbins[51]引入的.单行道问题是一个关于图的定向的问题.目前已有很多结果[2,14,24,34,52,53,54,55]基于不同的指标来研究与单行道问题相关的图的定向.Chartrand等人[9]引入了强有向图和强定向图的强距离、强半（直）径的新概念,它们成为图的定向的新的重要指标.设u和v是强定向图D的两个顶点,D中包含u和v,的最小强有向子图的弧数称为u和v的强距离sdD（u,v）.D的任一顶点v的强离心率se（v）为v与D中其它所有顶点的强距离的最大值.D的强半径srad（D）（强直径sdiam（D））为D中所有顶点的强离心率的最小值（最大值）.对于无向图,Lai等人[36]给出了图的最小（大）强半径及最小（大）强直径的定义.设G是一个连通图.G的最小强半径srad（G）（最大强半径SRAD（G））为G的所有强定向图的强半径的最小值（最大值）.类似地,G的最小强直径sdiam（G）（最大强直径SDIAM（G））为G的所有强定向图的强直径的最小值（最大值）.对于图G的任一强定向图D,都有κ（D）≤[κ（G）/2]和sdiam（D）≥sdiam（G）成立,其中κ（D）（κ（G））为D的强连通度（G的连通度）.通常,并不是所有的强定向图能同时满足两个等号.我们将同时使两个等号成立的定向称为图G的一个最优强（κ,d）定向.本文基于强距离、强半（直）径、强连通度等指标,研究特殊图类的强定向问题,得到以下结果.1.设K（m1,m2,…,mk）为完全k部图,其中m1,m2,…,mk分别为其顶点集的k部划分的子集的基数.我们研究了完全k部图的强定向图的强半径与强直径的一些性质.引理2设k≥3为任一整数,1=m1=…=mr<mr+1≤…≤mk,且k≥r+1.那么存在一个完全k部图K（m1,m2,…,mk）的强定向图K,使得当m1+m2+…+mk-1>mk时,srad（K）=3和sdiam（K）=4;当m1+m2+…+mk-1≤mk时,srad（K）=3和sdiam（K）=5.引理3设k≥3为任一整数,2≤m1≤m2≤…≤mk.那么存在一个完全k部图K（m1,m2,…,mk）的强定向图K,使得当m1+m2+…+mk-1≥mk时,srad（K）=sdiam（K）=4;当m1+m2+…+mk-1<mk时,srad（K）=4和sdiarn（K）=5.我们证明了,存在定向完全k部图的强定向图K’,K’’,K’’’,使得sdiam（K’）-srad（K’）=δ,srad（K’’）=r和sdiam（K’’’）=d,其中δ,r,d为满足0≤δ≤[k/2]-1,3≤r≤[k/2]1与4≤d≤k的任意整数.定理2对任一整数k≥3,存在完全k部图的强定向图K,使得sdiam（K）-srad（K）=δ,其中δ为满足0≤δ≤[k/2]-1的任一整数.定理3对任一整数k≥4,存在完全k部图的强定向图K,使得srad（K）=r,其中r为满足3≤r≤[k/2]+1的任一整数,且当k=3时,r=3.定理4对任一整数k≥4,存在完全k部图的强定向图K,使得sdiam（K）=d其中d为满足4≤d≤k的任一整数,且当k=3时,d=4.2.我们研究了完全k部图的最小（大）强半径及最小（大）强直径.给出了完全k部图的最小强半径、最小强直径与最大强直径的值,并且给出最大强半径的两个上下界.同时,我们发现了文[36]中关于完全2部图最小强直径值的一个错误结论,并给出其正确形式.定理5设k≥3和1≤m1≤m2≤…≤mk.那么,定理7设k≥3和m1=m2=…=mk=1.那么,定理8设k≥3和1≤m1≤m2≤…≤mk,且mk≥2.令m=m1+m2+…+mk-1.那么,定理9设k≥3和1≤m1≤m2≤…≤mk,且令m=m1+m2+…+mk-1.那么定理10设k≥3,1≤m1≤m2≤…≤mk和m=m1+m2+…+mk-1.那么3.我们证明了任一完全k部图均存在最优强（κ,d）定向.定理11设k≥2,m1≤m2≤…≤mk,mk≥2,且令m=m1+m2+…+mk-1≥2.那么K（m1,m2,…,mk）存在一个最优强（κ,d）定向。

论文目录

• 中文摘要
• Franch Abstract
• Abstract
• Chapter 1 Introduction
• 1.1 Basic Definitions and Notation
• 1.1.1 Graphs
• 1.1.2 Digraphs
• 1.2 Wireless Sensor Networks
• 1.2.1 Basic Definitions
• 1.2.2 Backgrounds and Related Work
• 1.2.3 Main Results
• 1.3 Strong Distance
• 1.3.1 Definitions and Basic Properties
• 1.3.2 Known Results
• 1.3.3 Main Results
• Chapter 2 Improving Wireless Sensor Network Lifetime Through Power Efficient Organization
• 2.1 Introduction
• 2.2 Problem Formulation
• 2.3 NP-completeness
• 2.4 Compute Optimal Maximum Sets
• 2.4.1 Algorithm
• 2.4.2 Implementation of f and h
• 2.5 Analysis and Performance
• 2.5.1 Theoretical Analysis
• 2.5.2 Simulated Annealing for DSCC
• 2.5.3 Evaluation
• 2.6 Conclusion
• Chapter 3 Energy Conservation in Wireless Sensor Networks and Connectivity of Graphs
• 3.1 Introduction
• 3.2 Related Work
• 3.3 Proof of Theorem 3.1.1
• 3.4 The Related Algorithms
• Chapter 4 Energy Efficient Point Coverage and Connectivity Maintenance in Wireless Sensor Networks
• 4.1 Introduction
• 4.2 NP-Complete Problem
• 4.3 Algorithm
• 4.4 Analysis and Performance
• 4.4.1 Theoretical analysis
• 4.4.2 Performance evaluation
• 4.5 Conclusions
• Chapter 5 Strong Distances in Strong Oriented Complete k-Partite Graphs
• 5.1 Introduction
• 5.2 Main Results
• Chapter 6 Lower and Upper Orientable Strong Radius and Strong Diameter of Complete k-Partite Graphs
• 6.1 Introduction
• 6.2 The Lower Orientable Strong Radius and Diameter of Complete k-Partite Graphs
• 6.3 The Upper Orientable Strong Radius and Diameter of Complete k-Partite Graphs
• Chapter 7 Optimal Strong （κ, d）-Orientation of Complete k-Partite Graphs
• 7.1 Introduction
• 7.2 Proof of Theorem 7.1.1
• Symbols
• Bibliography
• Published and Submitted Papers
• Acknowledgements