论文研究-基于转发节点集的连通支配集分布式算法 .pdf

所需积分/C币:5 2019-08-15 17:09:54 406KB .PDF
收藏 收藏
举报

基于转发节点集的连通支配集分布式算法,唐勇,张军,在无线传感器网络中,构造一个虚拟骨干网是优化网络性能的重要手段。虚拟骨干网的构造在数学上等同于求图的最小连通支配集,最小
国武技论文在线 证明:因为 而 于是, U∪,又因为=U,所以 。命题得证。 引理 是由位于区域 边界上的圆的圆心构成的集合。 证明:因为 ,若删去在区域 内的节点,如果区域 没有空 洞,则可以证明是由位于区域 边界上的圆的圆心构成的集合。 假设点是空洞中的一点,连接点与点,则必然存在圆′与线段或的延 长线交于点,因为线段的长度′≤,即点在圆内(上)又因为点 在′上,所以线段在圆′内,因此,上的任一点都在圆′内(上)。又因 为点在线段上,所以点也在′内,因此点不在空洞内,因此不存在这样的空洞, 这与假设矛盾,所以假设不成立,即朋去区域 内的节点,不会形成空洞,因此,原 命题得证。证毕。 本文基于以上所述的思路,把算法过程分为两个阶段,第一阶段在全网内的每个节点 ∈,求取的转发集第二阶段从中选取一部分节点做为骨干节点,放入 中,算法过程在每个节点实施后,既可以算出整个网终的,求得网终的虚拟骨干网 为了措述方便,算法分为主算法和次算法。主算法完成第一阶段的工作,次算法完成第 阶段的工作。主算法采用覆盖的思路,将节点的邻居节点集合的区域边界上的节点 放入集合,构成节点的转发集,主算法分布式的在每个节点独立运行。次算法使用颜色 标记法,从源节点廾始广播特殊的数据包,将收到薮据包和尚未收到数据包的节点标记为 灰色和白色,将被确定为骨十节点的节点标记为黑色,算法遂步的从节点的转发集中选择出 被标记为黑色的节点。经过主次算法,成功求得图的,实现虚拟骨T网的构造 算法描述 主算法 问题:节点∈,求节点的转发集 在图 中,对于任意节点∈,令 。根据引 理,算法采用覆盖的思想,初始时,令=⑧,从节点开始,首先从邻居节点集 中选取节点,比较的通信范围所形成的圆形区域与区域 的关系,若 在区域 上,则将节点放入集合中 。同理,从中选取节 比较 ≤≤是否在区域 内,若在 上,则将节点放入 当遍历完整个集合后,即可计算出节点的转发集 国武技论文在线 o节 节点发节点 O节点非转发令居节点 图包含个节点的区域覆盖过程 若令 则有 ,如图所示。首先从中取出节点,因为 图中阴影区域表示 ,因此,节点 加入集合中。同理,节点 也被加入集合中。对于节点,因为 ,所以节点不在集合中,经过选举,最终 ,于是得到节点的转发集。 从以上思路可以看出,若节点广播数据包,节点的转发集中的节点再转发此数 据包,那么节点的仁何两跳以内的邻居都能收到数据包,因此,不难看出,若节点 作为节点,中的节点作为骨干节点,此算法在上是最优解。这也是本文采用此 方法计算连通支配集的原因。 引理:节点∈ 且 ≠,若∈,则必然彐′∈ 的交点至少有一个位于区域 的边界上 证明:因为∈,因此在区域 上,若 ≠Q,则必然存在圆 的一段弧位于 的边界上。所以,必然彐′∈, 截取圆位于边界上的 段弧,因此,与′至少有一个交点位于 的边界上。证毕 引理:在引理的条件下,若′与相交于点,且中仅有以′和为圆 L,为通信半径的圆交于点,则′位于区域 证明:因为在区域的边界上,因此,若仪是′和的交点,则必然有圆 的一段弧在区域 的边界上,所以,′位于区域 上。证毕。 引理:在引理的条件下,若彐 圆 交」同一点,则仅能推出距离最远的节点≤≤在区域 上 证明:反证法。假设是距离最远的节点,存在节点≠,在区域 为点是 边界上弧的交点。因此,与点相连的弧仅有两段在 的边界上,又 因为圆的一段弧在 的边界上,因此,在节点 中,仅能确定存在一个 节点在区域 根据假设,因为在区域 上,所以不在区域 上,又因为与 交于点,所以,必然覆盖了的部分。因此,节点距离节点比节点距离 节点更远,这与假设矛盾,所以,假设不成立,原命题成立。证毕。 国武技论文在线 ●n2 1/ d3 图区域边界上圆弧的交点情况 引理:节点,′∈,若交点仪是圆与′的交点,且在区域 的边界上,则节点 ∈ 证明:根据引理,可证引理。证毕。 根据引理和引理,对于节点 ∈,如果能够判断与的两个 交点中至少有一个位于区域 的边界上,则可以判断出节点与是否需要加入集合 引理:L知点是以中节点为圆心的儿个圆的交点,∈,若 则交点 证明:因为 ≥因此集合中不存在节点,使得覆盖点,所以,点 是区域 边界上的点,即∈。证毕 根据以上引理 算法的主算法(转发集求取算法)如下。 主算法采用覆盖的思想,通过判断圆弧的交点是否在区域 的边界上,确定是否 将产生此交点的两个圆的圆心加入集合 主算法: 算法输入:,。 算法输出 算法步骤: 初始化Q 从 中选取节点。 令 ,若不等于,则将、加入集合中。 返回第步直至无法执行 结束 算法的第步求取与节点相交,且在区域上的节点,本过程由算法完成 图表示了算法区域边界上圆弧的交点情况,图表示父点仅是两个圆的父点,图 表示交点是多个圆的交点。算法的第步需要处理图中多个圆在边界上交于 一定的情况,本过程由算法 处理 算法如下 算法的如下 算法输入 国武技论文在线 算法输出:,返回值。 算法步骤: 若 ≠团,则从 中选取节点 则跳到第步 计算圆与的交点,。 对于∨∈ 若 若 返 回,否则,跳到第步 返回 结束。 算法 过程如下: 算法输入 算法输出 ,从中选择 令 ∈ ≤且不存在∈,点在圆 上:,对于∈,在的邻居节点集合的所有节点中,若距离最远 返回第步,直至不能执行。 结束。 15 112 l71 12 图 算法第步的选择 算法第步处理多圆交于一点的问题时,需要选择一个的邻居节点集合, 但这个不包括这样的节点:存在除外的另一个交点已经在 的边界上。图反 映了这个情况,图中的全部节点,除了一个交点外,另一个交点均在 的边界 上,所以 图中由于与 与的交点在边界上,因此不在 中,所以有 外,算法的第步由定理保证 定理:若点是 边界上弧的交点,则中距离最远的两个节点在区域 证明:反证法,令 ≤,其中∈ 若∈,且节点 与在区域 ,连接与节点,则角∠最人。 国武技论文在线 假设存在∠ ,则必然有区域 或 ,覆盖了边界上的交点 或,于是点和不在区域 的边界上,因此,节点与不在区域 的上 这与原命题矛盾,所以假设不成立,原命题成立。证毕。 次算法 在图 中,主算法分布式的在每个节点运行,每个节点计算出自凵的转发集。 当节点集中的所冇节点计算出转发集后,则需要实施次算法来完成的求取。次算法 采用染色的方案:初始将所有的节点染成白色,当一个节点收到特殊数据包时,将自己 标记为灰色,当一个节点确定自己为支配节点时,将自己标记为黑色。算法完成后,所有被 标记为黑色的节点即为支配节氐,所有灰色节点即为非支配节点。算法假定在源节点处开 始执行(∈,可任意选取)。 根摭以上描述,次算法如下 算法输入 ∈ 算法输出 网络中的所有节点标记自己为白色,标记自己为灰色。 节点广播数据包,的邻居中的节点收到,若中的节点为白色,则 标记自己为灰色 若灰色节点∈ 且’∈则’广播数据包 当灰色节点收到了带有自己标识的后,将自己标记为黑色。 灰色和黑色节点收到数据包后,不再广播数据包 中的节点作为,执行 步的操作。 结宋。 数据包的结构需满足如下条件: 带有特征位,用以标识而异于普通数据包。 带有二跳转发节点的标记。如广播数据包 收到,则′会收到打有 标记的,表明转发的是来自两跳内的节点的数据包。 Pa:-1.1 w. 3 id 2 Pa:-1,1 .3 2 id2 Pal.2 (2) 图数据包传输规则描述 图给出了在次算法中,数据包在网终中传输的小意图 表小为的节 点收到为的节点广播的数据包后,广播的。中节点广播数据包,节点和收 到数据包,中节点和收到数据包,然后广播带有标识的,由于黑色节点不再广 播数据包,因此节点和无法确定自己为支配节点,支配节点为。 国武技论文在线 算法的第步需要通过判断收到的数据包所附加的标志,来判断是否要标记本节点 为黑色节点。如上所述,只有当节点自己发送的数据包通过两跳后回到自己时,节点才会确 定自己为黑色,即确定为支配节点。图描述了这个过程。图中仅画出了转发节点,其中黑 色节点为支配节点,图源节点广播数据包,图的邻节点转发,确定为支 配节点,图 完成从个转发节点中选举出个支配节点。 次算法以广播扩散的方法完成了的求取,每个转发集中的节点作为灰色节点仅转 发一次 图次算法的执行过程 图 算法分析 算法的正确性证明 因为图 是 图,对于任意的节点∈,主算法让算所得到的 是的个导出子图,因为c,因此 是连通的,并且 是的支配节点集 根据次算法,对于∈ 因此 是连通的,并且是 的支配节点集。依次累推,可知道通 过主次算法所计算得到的是图的连通支配集 复杂度分析 本算法的执行分为两部分:主算法和次算法,因此,算法的分析也按两部分分别描述。 主算法分布式的在每个节点进行,且互不依赖,互不影响,因此,每个节点只有相同的 计算时间。主算法采用覆盖的策略,需要计算哪些节点在区域 的边界上。对于∨∈, 中的节点需要两两计算其交点,若令 其中Δ,于是,这一过程 的计算次数为 国武技论文在线 × + 公式 其中表示节点计算所需的时间。 公式是主算法中算法所需要的时间, 算法处理多个圆在边界交于一点的 情况,其最坏的情況是∧+个圆相交于一个点,此时算法执行所需的时间复杂度为 △+ 公式 其中′表示节点计算所需的时间。于是,主算法的时间复杂度为 △++△++—△ 再来看次算法,次算法采用广播扩散的方法,先要在网络的所有节点集中选择亠个节点 倣为源节点,然后按照次算法提供的染色方案,最终被标记为黑色的节点作为网络的骨干 节点。算法所需要的时间为网络的最大路径长度。因此,若令网络的平均节点度数为△=△ 则本算法的时间复杂度为△ 仿真与结果分析 为了测试 算法的性能,我们仿真实现了 算法与 算法, 算法,以及 算法在不同的网终环境下所得到的个数,额外消息数以及算法 的收敛时间。 网络拓扑随机产生在 的正方形区域上,节点的位置服从均匀分布,如 果产生的网络不是连通的,则重新产牛直到整个网终连通为止。网络中的每个节点带有相同 的通信半径 对于每个仿真实验,产生个不同的网终拓扑。网终的节点数从 到个,间隔为个。实验如下: 实验:仿真比较 算法与算法 算法以及算法的大小 ODC Number of Nodes 算法与算法、 算法以及算法关于大小的比较 图显示了实验的结果 算法比起其他个算法具有最小的尺寸, 国武技论文在线 算法在节点密度较小吋与 算法具有接近的个数,但当节点密度较大时,本算法 要优于 算法,算法在节点密度较大时曲线趋于水平,但个数仍然比 算法大。因此, 算法在个数上要优于和 算法,在节点密度较小 时接近 算法 实验:仿真比较 算法与算法 算法以及算法的额外消息 根据额外消息数的定义,节点之间的邻居发现通过层的 完成,因此不属 于额外消息。 算法的主算法除了通过节点的邻居发现获取邻居的坐标信息外,节点 独立的完成转发集的计算,不需要发送与接收额外消息,这一点和 算法相同。 的次算法与 的第二阶段类似,其额外消息是广播特殊数据包所产生,而广播 的节点为中的节点,且中的节点在计算过程中都有且仪有次对的广播,因 此, 算法的额外消息数为其中的节点数。图描述了这种情况 FWCDS OHC 450 Number of Nodes 图 算法与算法额外消息数的比较 12000 H FWCDS 9 ODC ×MISB 图 算法与 算法 算法以及算法关于额外消息数的比较 因为 算法有非常小的额外消息数,因此仿真结果单独放在图中。 图描述了这四种算法额外消息数的仿真结果, 算法只有最多的额外消息数 算法的额外消息数约为 和 算法的倍。 实验:仿貞比较 算法与算法 算法以及算法的收敛时间。

...展开详情
试读 11P 论文研究-基于转发节点集的连通支配集分布式算法 .pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    • 至尊王者

      成功上传501个资源即可获取
    关注 私信 TA的资源
    上传资源赚积分,得勋章
    最新推荐
    论文研究-基于转发节点集的连通支配集分布式算法 .pdf 5积分/C币 立即下载
    1/11
    论文研究-基于转发节点集的连通支配集分布式算法 .pdf第1页
    论文研究-基于转发节点集的连通支配集分布式算法 .pdf第2页
    论文研究-基于转发节点集的连通支配集分布式算法 .pdf第3页
    论文研究-基于转发节点集的连通支配集分布式算法 .pdf第4页

    试读已结束,剩余7页未读...

    5积分/C币 立即下载 >