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

《连通控制集问题及其在无线传感器网络中的应用课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、连通控制集问题及其在无线传感器网络中的应用本讲主要内容无线传感器网络中的虚拟骨干网；最小连通控制集问题（MinimumConnectedDominatingSet，MCDS）；单位圆盘图中MCDS的近似算法；传感器网络监测区域phenomenon用户1Sink互联网/卫星传感器网络用户2传感器网络传感器感知+计算+通讯尺寸小，造价低廉由电池驱动，能量有限军事领域环境监测交通监控医疗保健与有线网络不同，无线传感器网络没有固定的基础设施，信息的传播需要通过多个传感器经过多跳（multi-hop）方式来实现。研究表明，采用虚拟骨干网可以减少信息传输中的拥塞，提高网

2、络的效率和稳定性。互联网/卫星Sink用户虚拟骨干传感器传感器网络监测区域A连通控制集控制集连通控制集单位圆盘图单位圆盘图（UnitDiskGraph）单位球图两步算法控制集连通控制集Step1.计算一个控制集D.Stage2.添加一些点使D变得连通独立集给定图G=（V，E），V的子集M称为一个独立集如果M中任两点不相邻。M称为极大独立集，如果任添加一个点至M，则不是独立集。极大独立集可以在多项式时间找出u1u2u3u(l+1)vD2D1D3vv2v1v5v3v45!最小连通控制集的常数倍近似算法求最小连通控制集的ＭＩＳ算法：步骤１　计算一个ＭＩＳ；步骤２　

3、逐步添加点把ＭＩＳ中所有点连接起来MIS算法的进一步改进ＭＩＳ算法可从两个方面进行改进：２。改进ＭＩＳ｜与ｏｐｔ之间的关系：１。改进ＭＩＳ的选择方式；３。改进ＭＩＳ的连接方式。ＭＩＳ选择选择ＭＩＳ的涂色算法Step１。任找连通图Ｇ的一棵生成树Ｔ；Step２。任意选择Ｔ的一个顶点ｖ作为根，将Ｔ中顶点按照距离ｖ的远近分层；Step３。　将ｖ涂为黑色（选为ＭＩＳ中点），然后逐层选择ＭＩＳ中点，涂为黑色，涂色过程中保证新涂色的点不与任何已经涂色的点相邻。ＭＩＳ算法Ｖ注：利用涂色得到ＭＩＳ，然后再逐步加点将其连接起来，得到的连同控制集不超过10opt。性质：距离最近的

4、两个ＭＩＳ中点距离恰为２。两个圆心距离<1的单位圆盘内最多可有几个独立点?8!(Wuetal,2006)四个单位圆盘，每一个都包含其它三个的中心，那么，这四个圆盘内最多有多少个独立点?<15!(Yaoetal,2008)单位圆盘图中(Wuetal.2006)(Funkeetal.2006)(Yaoetal.2008)(Wanetal,2002)MCDS(opt)MIS？Stage2:把一个MISD中所有点连接起来.贪婪算法.用贪婪算法连接MIS定理证明：Thanks,End