(19)中华人民共和国国家知识产权局
(12)发明专利说明书 | ||
(10)申请公布号 CN 102098677 A (43)申请公布日 2011.06.15 | ||
(21)申请号 CN200910273158.5
(22)申请日 2009.12.11
(71)申请人 武汉大学
地址 430072 湖北省武汉市武昌珞珈山
(72)发明人 胡瑞敏 陈铙 向斯达 王亦民
(74)专利代理机构 武汉天力专利事务所
代理人 严彦
(51)Int.CI
H04W16/00
H04W80/00
权利要求说明书 说明书 幅图 |
(54)发明名称
一种基于gossip的快速覆盖网络构建方法 | |
(57)摘要
本发明公开了一种基于gossip的快速覆盖网络构建方法，这种方式考虑了每个节点所持有的邻居集合的差异性，提出了一种动态自适应的拓扑信息交换机制。这种机制可以使得覆盖网络构建阶段前期节点可以快速的进行拓扑信息交换来达到拓扑信息的相对稳定状态；而在节点达到相对拓扑稳定后的拓扑维持阶段使得节点进行较小的拓扑信息交换来避免额外的信息交换而浪费网络带宽资源。 | |
法律状态
法律状态公告日 | 法律状态信息 | 法律状态 |
权 利 要 求 说 明 书
1.一种基于gossip的快速覆盖网络构建方法，其特征在于：对覆盖网络中的所有节点，执行以下步骤：
步骤1，覆盖网络中的任意节点A维持一个定时器，时长为T，同时维持一个邻居节点集合N<sub>A</sub>，N<sub>A</sub>的大小为n；节点A从邻居节点集合N<sub>A</sub>所存节点中随机选取一个节点B；节点B也维持一个定时器，时长为T，同时维持一个邻居节点集合N<sub>B</sub>，N<sub>B</sub>的大小为n；
步骤2，节点A将邻居节点集合N<sub>A</sub>中的节点按延时由小到大排序，然后从中选择X<sub>A</sub>个延时最小的节点作为一个子集S<sub>A</sub>；
其中，构成子集S<sub>A</sub>的节点个数X<sub>A</sub>，根据节点A加入到覆盖网络到当前时间的时间长度t<sub>A</sub>决定，公式表达为
<maths><math><mrow><msub><mi>X</mi><mi>A</mi></msub><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow><mo>=</mo><mfrac><mn>30</mn><mrow><mn>1</mn><mo>+</mo><msup><mi>e</mi><mrow><mo>(</mo><msub><mi>t</mi><mi>A</mi></msub><mo>/</mo><mn>2</mn><mo>-</mo><mn>6</mn><mo>)</mo></mrow></msup></mrow></mfrac><mo>+</mo><mn>10</mn><mo>,</mo></mrow></math></maths>e为自然对数；
步骤3，节点A将子集S<sub>A</sub>发送给节点B；
步骤4，节点B收到节点A发送的子集S<sub>A</sub>后，将子集S<sub>A</sub>与邻居节点集合N<sub>B</sub>合并，得到新的邻居节点集合N<sub>B</sub>，合并方式为将子集S<sub>A</sub>所含节点与邻居节点集合N<sub>B</sub>所存节点一起按照延时大小由小到大排序，并去除重复的节点，保留延时最小的n个节点作为新的邻居节点集合N<sub>B</sub>所存内容；然后从新的邻居节点集合N<sub>B</sub>中选择X<sub>B</sub
>个延时最小的节点作为一个子集S<sub>B</sub>，并将子集S<sub>B</sub>发送给节点A；
其中，构成子集S<sub>B</sub>的节点个数X<sub>B</sub>，根据节点B加入到覆盖网络到当前时间的时间长度t<sub>B</sub>决定，公式表达为
<maths><math><mrow><msub><mi>X</mi><mi>B</mi></msub><mrow><mo>(</mo><mi>t</mi><mo>)</mo></mrow><mo>=</mo><mfrac><mn>30</mn><mrow><mn>1</mn><mo>+</mo><msup><mi>e</mi><mrow><mo>(</mo><msub><mi>t</mi><mi>B</mi></msub><mo>/</mo><mn>2</mn><mo>-</mo><mn>6</mn><mo>)</mo></mrow></msup></mrow></mfrac><mo>+</mo><mn>10</mn><mo>,</mo></mrow></math></maths>e为自然对数；
正则化网络步骤5，节点A将收到的子集S<sub>B</sub>与邻居节点集合N<sub>A</sub>合并，得到新的邻居节点集合N<sub>A</sub>；合并方式为，将子集S<sub>B</sub>所含节点与邻居节点集合N<sub>A</sub>所存节点一起按照延时大小由小到大排序，并去除重复的节点，保留延时最小的n个节点作为新的邻居节点集合N<sub>A</sub>所存内容；
步骤6，节点A和节点B等待各自定时器超时，定时器超时后，重复上述步骤1～5共五个步骤。
说 明 书
技术领域
本发明涉及信息领域，尤其涉及一种基于gossip的快速覆盖网络构建方法。
背景技术
基于gossip(闲话)协议的覆盖网络系统已经成为构建覆盖网络的主流方式，其协议简单：通过成对节点之间不停交换各自的邻居节点信息来实现拓扑的维持与进化。如果网络不存在剧烈的拓扑关系变化，随着节点加入覆盖网络的时间推移，整个覆盖网络最终将会达到一种相对稳定的状态(就是每个节点的邻居集合不会有剧烈变化)，称之为覆盖网络收敛。此协议易于实现和部署，使得很多基于点对点方式的覆盖网络应用都采用gossip方式作为底层的覆盖网络构建方式，其特点包括：
(1)覆盖网络中的任意节点A维持一个定时器(时长为T)，同时维持一个邻居节点集合N<sub>A</sub>，N<sub>A</sub>的大小为n，即邻居节点集合N<sub>A</sub>中存放节点A的n个邻居节点。节点A从自己的邻居节点集合N<sub>A</sub>中随机选取一个邻居节点B。由于覆盖网络中任意节点维持机制一样，节点B也维持定时器和长度为n的邻居节点集合，记为N<sub>B</sub>。
(2)节点A将自己的邻居节点集合N<sub>A</sub>中的所有n个节点延时由小到大排序，然后按序将这n个邻居节点的信息发送给节点B。
(3)节点B收到节点A发送的邻居节点集合N<sub>A</sub>中n个节点的信息后，将N<sub>A</sub>与与自己的邻居节点集合N<sub>B</sub>合并，合并时将N<sub>A</sub>与N<sub>B</sub>中所有节点按照延时大小由小到大排序，并去除可能存在的相同节点，保留延时最小的n个节点存放到邻居节点集合N<sub>B</sub>，即合并后新的邻居节点集合N<sub>B</sub>所含节点数目仍与原来一样。使用与(2)同样的方式将节点B新的邻居节点集合N<sub>B</sub>中n个节点的信息发送给节点A；
(4)节点A将收到的邻居节点集合N<sub>B</sub>与自己的邻居节点集合N<sub>A</sub>进行
合并，合并时将N<sub>A</sub>与N<sub>B</sub>中中所有节点按照延时大小由小到大排序，并去除可能存在的相同节点。保留延时最小的n个节点存放到邻居节点集合N<sub>A</sub>，即合并后新的邻居节点集合N<sub>A</sub>所含节点数目仍与原来一样。
(5)节点A、节点B等待各自定时器超时，定时器超时后，重复上述(1)～(4)四个步骤，并一直继续维持下去。
以上步骤应用于覆盖网络中的所有节点，可参见Jelasity M.，Montresor A.andBabaoglu O.，“Gossip-based aggregation in large dynamic networks”，ACM Trans.On Computer Systems，2005，23(3)：219252。
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论