连通控制集问题及其在无线传感器网络中的应用.ppt

,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,连通控制集问题及其在无线传感器网络中的应用,本讲主要内容,无线传感器网络中的虚拟骨干网；,最小连通控制集问题（,Minimum,Connected,Dominating,Set,，,MCDS,）；,单位圆盘图中,MCDS,的近似算法；,传感器网络,监测区域,phenomenon,用户,1,Sink,互联网,/,卫星,传感器网络,用户,2,传感器网络,传感器,感知,+,计算,+,通讯,尺寸小，造价低廉,由电池驱动，能量有限,军事领域,环境监测,交通监控,医疗保健,与有线网络不同，无线传感器网络没有固定的基础设施，信息的传播需要通过多个传感器经过多跳（,multi-hop,）方式来实现。,研究表明，采用虚拟骨干网可以减少信息传输中的拥塞，提高网络的效率和稳定性。,互联网,/,卫星,Sink,用户,虚拟骨干,传感器,传感器网络,监测区域,A,连通控制集,控制集,连通控制集,单位圆盘图,单位圆盘图（,Unit,Disk,Graph,）,单位球图,两步算法,控制集,连通控制集,Step 1.,计算一个控制集,D,.,Stage 2,.,添加一些点使,D,变得连通,独立集,给定图,G=,（,V,，,E,），,V,的子集,M,称为一个独立集,如果,M,中任两点不相邻。,M,称为极大独立集，如果任添加一个点,至,M,，则 不是独立集。,极大独立集可以在多项式时间找出,u1,u2,u3,u(l+1),v,D2,D1,D3,v,v2,v1,v5,v3,v4,5!,最小连通控制集的常数倍近似算法,求最小连通控制集的算法：,步骤计算一个；,步骤逐步添加点把中所有点连接起来,MIS,算法的进一步改进,算法可从两个方面进行改进：,。改进与之间的关系：,。改进的选择方式；,。改进的连接方式。,选择,选择的涂色算法,Step,。任找连通图的一棵生成树；,Step,。任意选择的一个顶点作为根，,将中顶点按照距离的远近分层；,Step,。将涂为黑色（选为中点），,然后逐层选择中点，涂为黑色，,涂色过程中保证新涂色的点不与任何已经涂色的点相邻。,算法,注：利用涂色得到，然后再逐步加点,将其连接起来，得到的连同控制集,不超过,10 opt,。,性质：距离最近的两个中点距离恰为。,两个圆心距离,1,的单位圆盘,内最多可有几个独立点,?,8!,(Wu et al,2006),四个单位圆盘，每一个都包含其它三个的中心，,那么，这四个圆盘内最多有多少个独立点,?,15!,(Yao et al,2008),单位圆盘图中,(Wu et al.2006),(Funke et al.2006),(Yao et al.2008),(Wan et al,2002),MCDS(opt),MIS,？,Stage 2:,把一个,MIS,D,中所有点连接起来,.,贪婪算法,.,用贪婪算法连接,MIS,定理,证明：,Thanks,End,