The ONE使用笔记:实现Bubble Rap

我认真研读了Bubble Rap那篇文章,从数据集本身分析,到centrality、community计算,再到The ONE实现,遇到很多问题。本文分享我已做的工作,并列出自已遇到的困惑。

1. Bubble Rap实现

首先,先贴个仿真结果,结果不是很好,后面变了centrality计算方法,效果跟Bubble Rap很接近。

image

图1:Bubble Rap的仿真结果

我实现思路很简单:用Python处理数据集(如infocom06),建立静态图,求得每个节点对应的centrality和所属的社区。有了这些数据后,在The ONE实现Bubble Rap就简单了。但这有个问题,社区检测community detection不是动态的,很有局限性。

后来,无意中发现GitHub有一份源码(在这里),作者也实现了Bubble Rap,直接在The ONE仿真器实现,是动态的。我也下了这份代码,并且打算用于我后续的仿真,但使用过程中发现这份代码有bug,我已将问题反馈给作者(在这里),但至今没有回复。所以,在使用的时候,务必当心。

2. 存在的困惑

数据集相关

  • 我找不到Hongkong数据集,在CRAWDAD下载的数据集,我一直觉得有问题
  • Contact graph中,边的权重如何算,对于开始时间与结束时间相同的contact怎么处理
  • Community detection,用k-clique还是用其他的?
  • ……

实现相关

  • 实现,其实我觉得还比较简单,主要解决将centrality, community读入The ONE,新建路由BubbleRapRouter,在其update根据论文实现算法。
  • 如何动态预测节点相遇情况
  • 如何突破The ONE没有MAC层的局限(不能broadcast)
  • ……

期待与您深入交流:回复本博文或电邮sparkandshine@163.com

Series: DTN路由协议 (6/6)

Leave a Reply

Your email address will not be published. Required fields are marked *

78 thoughts on “The ONE使用笔记:实现Bubble Rap

  • Friday June 24th, 2016 at 11:18 AM
    Permalink

    bubblerap那份源码,我compile后,只可以用default_setting来配置,用其他的setting或者自己新建一个都提示, Error parsing command args. Expected run index.Got,这是什么原因造成的呢?应该怎么处理?

    Reply
    • Thursday June 30th, 2016 at 07:44 PM
      Permalink

      Try to run your program like,

      ./one.sh -b 1:1 path/settings.txt

      Reply
  • Wednesday May 11th, 2016 at 03:41 PM
    Permalink

    你好,我在看源码是看到①CENTRALITY_WINDOW_SETTING;和②COMPUTATION_INTERVAL_SETTING这2哥周期时间,我想问 如果第②个是centrality的更新周期,那么第①个时间代表什么呢?是进行相遇过的节点在①时间内的节点统计?

    Reply
    • Thursday May 12th, 2016 at 12:21 AM
      Permalink

      CENTRALITY_WINDOW_SETTING is the duration of the time interval to consider.

      Reply
      • Thursday May 12th, 2016 at 10:36 AM
        Permalink

        你好,那是表示在①时间内一直在更新,那么②代表的是更新间隔吗? (英文不是特别好 0.0)

      • Thursday May 12th, 2016 at 10:47 AM
        Permalink

        请问,能发一份运行Bubble Rap代码的配置文件给我吗? 就是你发的源码链接里的源码。不知道怎么跑起来?

  • Wednesday April 6th, 2016 at 09:21 PM
    Permalink

    GitHub里面Bubble Rap的代码,但是运行出错有问题,请问你是如何解决的或是有正确的代码,能参考一下么?

    Reply
    • Wednesday April 6th, 2016 at 10:18 PM
      Permalink

      那份代码,我在博文也提了,的确有不少BUG,我半年前很认真调过,至少发现了两个,https://github.com/knightcode/the-one-pitt/issues/. 所以只是提供给你参考。

      你之前的几个问题集中在如何实现social-aware routing protocols,好歹你也看下源代码。。。

      Reply
  • Wednesday April 6th, 2016 at 09:12 PM
    Permalink

    能解释一下,其中社会性部分的程序么?怎么没有看到CommunityRouter算法,就是直接将社会性写为路由算法,这个不知道如何实现?

    Reply
  • Saturday November 7th, 2015 at 06:07 PM
    Permalink

    你好,看到你写的笔记,分析的很透彻,我也下载了那个GitHub里面Bubble Rap的代码,但是运行不了,不知道里面的Bug 是否已解决?另外,可否给我发一份你写的Bubble Rap源码?多谢!我邮箱:403604473@qq.com

    Reply
    • Wednesday November 11th, 2015 at 03:19 PM
      Permalink

      the-one-git里面包含了bubble rap源码,没错,这份源代码的确有bug,我至少发现了两个,在这里https://github.com/knightcode/the-one-pitt/issues

      Reply
      • Thursday December 8th, 2016 at 04:40 PM
        Permalink

        十分感谢您提供的资源,不过现在已经把你提到的两个问题都修改了,还是运行错误。不知能否发一份能运行的bubble rap代码给我。 我的邮箱:961536174@qq.com

      • Wednesday December 14th, 2016 at 08:57 PM
        Permalink

        是的,这份代码问题很多,只适用于参考他们是怎么实现的。我有时间,再整理一会源代码更新到社篇博文。

      • Thursday December 15th, 2016 at 03:31 PM
        Permalink

        博主真是棒棒哒! [赞]

  • Sunday October 11th, 2015 at 10:26 AM
    Permalink

    你好,我想要一份Bubble RAP的源码,不知道可以分享给我吗? 我的邮箱:381217445@qq.com

    Reply
    • Thursday October 15th, 2015 at 11:15 PM
      Permalink

      已给你邮件,请查收。这里有一份源码,比我实现的要好,https://github.com/knightcode/the-one-pitt

      Reply
    • Tuesday May 14th, 2019 at 06:09 AM
      Permalink

      您好,请问您还有当时的源码吗,作者用静态图实现的这一个,十分感谢,我的邮箱是970435269@qq.com

      Reply
  • Wednesday May 6th, 2015 at 11:03 AM
    Permalink

    在BUBBLR RAP那篇论文的第八节 作者画出了不同groups的centrality,并且还比较了reality数据集下 single group和all groups的几种路由性能(图16和图17) 那么如何在仿真中 single 和all groups 是如何体现的呢 ? 是不是Scenario.nrofHostGroups = 1就代表着 single group?

    Reply
    • Wednesday May 6th, 2015 at 04:27 PM
      Permalink

      论文的group是指community,仿真器的Scenario.nrofHostGroups=N, Group1, Group2, Group3, …,可以为每个组指定不同的参数(如router, waitTime, bufferSize)。你用Reality数据集,movementModel是StationaryMovement,只能是一个组。

      Reply
      • Thursday May 7th, 2015 at 09:14 AM
        Permalink

        那社区的group怎么看呢 仿真的时候我输出了CommunityDetectionReport 表示看不懂 reality数据集没有会议6的效果好

      • Thursday May 7th, 2015 at 09:15 AM
        Permalink

        举个栗子 CommunityDetectionReport 中输出为n0 4.2 n1 1.4 n2 4.2 n3 0.0 n4 0.6 n5 0.4 n6 0.0

      • Thursday May 7th, 2015 at 05:12 PM
        Permalink

        建议你看下CommunityDetectionReport源码,这样你就知道Report的格式了。

      • Thursday May 28th, 2015 at 04:35 PM
        Permalink

        我用的是Haggle4-Cam-Imote-dirconn.txt这个数据集,你可以看看我的输出报告。Message stats for scenario BubbleRap_TTL30240sim_time: 987529.0000created: 1000started: 9278relayed: 8385aborted: 893dropped: 0removed: 820delivered: 651delivery_prob: 0.6510deliverycost: 8.3850response_prob: 0.0000overhead_ratio: 11.8802latency_avg: 116310.4178

      • Friday May 29th, 2015 at 12:28 AM
        Permalink

        谢谢您的回复。我认真检查了下我的代码,还是没找出原因,可否将您的数据集Haggle4-Cam-Imote-dirconn.txt和设置文件_settings.txt,给我发一份?我想确认下是不是代码的问题。sparkandshine@163.com

      • Friday May 29th, 2015 at 12:55 PM
        Permalink

        已发

      • Tuesday June 2nd, 2015 at 12:17 AM
        Permalink

        Hello, 我用你的代码,跑了bubble-6.txt (在没有做任何改动的情况下),结果跟你差距比较大(尤其是started):Message stats for scenario BubbleRap_TTL30240sim_time: 987529.0000created: 1000started: 6106relayed: 5435aborted: 671dropped: 0removed: 567delivered: 640delivery_prob: 0.6400deliverycost: 5.4350response_prob: 0.0000overhead_ratio: 7.4922latency_avg: 121154.7031latency_med: 82251.0000hopcount_avg: 2.9922hopcount_med: 2buffertime_avg: 43995.6578buffertime_med: 14080.0000rtt_avg: NaNrtt_med: NaN

      • Tuesday June 2nd, 2015 at 06:06 AM
        Permalink

        你肯定没有看Bubble路由的副本数,很明显传给你的包里副本数是2,貌似我真的改过。。上面那个是4副本的情况所以有些不同。2副本的如下 ,和你的差不多Message stats for scenario BubbleRap_TTL30240sim_time: 987529.0000created: 1000started: 6044relayed: 5364aborted: 680dropped: 0removed: 558delivered: 640delivery_prob: 0.6400deliverycost: 5.3640response_prob: 0.0000overhead_ratio: 7.3813latency_avg: 125289.7078latency_med: 84011.0000hopcount_avg: 2.9891hopcount_med: 3buffertime_avg: 46253.6792buffertime_med: 14622.0000rtt_avg: NaNrtt_med: NaN

      • Tuesday June 2nd, 2015 at 06:08 AM
        Permalink

        每次仿真都有差别,然后改变Events2.prefix也会有一些结果变化,比较细微。

      • Friday June 26th, 2015 at 04:16 PM
        Permalink

        看到你俩在这里讨论,我有的问题啊,sim-time时间差不多11天多,是Cambridge的数据集采集时间,ttl有必要设置那么大吗?30240按分钟算就是3周,没意义吧?

      • Friday June 26th, 2015 at 06:05 PM
        Permalink

        那你打算怎么处理数据集?从中选择一个时间段来仿真?

      • Monday June 29th, 2015 at 09:25 AM
        Permalink

        我的意思是数据集本身的采集时长只有11天多,那么仿真时间也就是11天多,那么ttl如果比仿真时间还大是不是没有意义啊?我的处理办法是数据集采集时间有多长,仿真时长就设置为多长,然后在此时间内,选取几个时间截点作为ttl,然后分别仿真,作对比,不知道这样的方法是否可行?另外,抽取社会属性的时候,是否针对全部数据集来进行?或者选取一部分数据集进行呢?

      • Monday June 29th, 2015 at 11:28 PM
        Permalink

        (1)关于TTL这取决于你仿真结果要考查那个自变量,比如TTL,你那样选取是对的。另外,TTL设成11天+ (即无限,group.msgTtl=-1)是有意义的,比如考察bufferSize自变量时,要尽可能不让ttl也成为一个变量,也就是将其设成无穷大。(2)抽取社会属性个人认为,考虑全部数据集更加合理。与其将精力放在如何部分选取数据集,还不如何放在如何更准确找出社会属性(比如分布式)。

      • Tuesday June 30th, 2015 at 08:47 AM
        Permalink

        你说得对!

      • Tuesday June 30th, 2015 at 09:35 AM
        Permalink

        能否将这个配置文件发给我一份看看,每次运行结果总是很怪异,有时候随着ttl的增加,投递率怎么会有下降了呢,真奇怪!我的邮箱mhh@haust.edu.cn,谢谢

      • Tuesday June 30th, 2015 at 03:53 PM
        Permalink

        如果你的bufferSize是有限的话,那是正常的,因为丢包会变得越来越严重。settings文件我一会发给你。

      • Tuesday June 30th, 2015 at 05:18 PM
        Permalink

        谢谢。是这个原因吗?那总不能把buffersize 设置成无限吧,我在对infocom06数据集分析的时候,每次ttl为2d的成功投递率都会比ttl为1d的投递率低,我还纳闷呢,换了几个方法都是一样的结果,想看看你的setting是咋设置的,打算再换个数据集试一试。

      • Wednesday July 1st, 2015 at 03:46 PM
        Permalink

        关于bufferSize,你将其设成无限大,再跑一次仿真,得到结果与之前的对比,你就可以确认这一点。

      • Tuesday June 30th, 2015 at 05:29 PM
        Permalink

        谢谢,setting已收到,再次感谢。看到了一个问题,Events1.class = StandardEventsReader和ExternalEventsQueue差别在哪里?我采用的是StandardEventsReader,运行相当之慢,另外,buffersize你没有设置,就是采用的defaultsetting中的数值,我的设置相对于消息的size来说似乎是有点小了,我设置是buffersize=500M,而Events2.size = 500k,1M,这个应该如何来考察呢,如果我现在只考察ttl与成功投递率的关系,那么buffersize如何设置才能不受影响呢?

      • Wednesday July 1st, 2015 at 03:52 PM
        Permalink

        StandardEventsReader与ExternalEventsQueue的差别,没比较过。bufferSize不设,说明是无限大。从仿真角度来讲,你可以将bufferSize设成无限大,来消除buffer带来的影响,更确切的说,是丢包策略带来的影响。

      • Wednesday July 1st, 2015 at 03:55 PM
        Permalink

        我试试吧,之前一直用infocom06,昨天换了reality,还是一样的情况,今天再试试无限大吧,本来心理上觉得无论什么设备都不可能有无限大的size,所以就没考虑过无限大的情况,谢谢。

      • Monday July 6th, 2015 at 09:58 AM
        Permalink

        我看到你们所提的这个bubblerap的程序,用他readme.md中的配置,结果没有消息被成功投递

      • Monday July 6th, 2015 at 03:12 PM
        Permalink

        我只是今天才想起来试一下他的bubblerap程序,用的就是他自带的配置:Group.router = DecisionEngineRouterDecisionEngineRouter.decisionEngine = community.DistributedBubbleRapDecisionEngineRouter.communityDetectAlg = routing.community.KCliqueCommunityDetectionDecisionEngineRouter.K = 5DecisionEngineRouter.familiarThreshold = 700DecisionEngineRouter.centralityAlg = routing.community.CWindowCentrality,对reality进行分析,结果:Message stats for scenario (size=1k-2k)3w-Reality+DecisionEngineRouter+10080sim_time: 987529.0000created: 28625started: 0relayed: 0aborted: 0dropped: 0removed: 0delivered: 0delivery_prob: 0.0000response_prob: 0.0000overhead_ratio: NaNlatency_avg: NaNlatency_med: NaNhopcount_avg: NaNhopcount_med: 0buffertime_avg: NaNbuffertime_med: NaNrtt_avg: NaNrtt_med: NaN,所以很纳闷,问题我还没找出,正在看你所提的那两个bug

      • Thursday August 25th, 2016 at 12:24 PM
        Permalink

        您好,我也出现这样的问题,请问您是怎样解决的?

      • Friday October 28th, 2016 at 01:12 PM
        Permalink

        您好,请问这个问题解决了么?

    • Wednesday May 15th, 2019 at 04:47 AM
      Permalink

      请问您还有当时的setting文件吗,按照README中配置投递率等信息一直为0,十分感谢!

      Reply
  • Monday March 30th, 2015 at 03:37 PM
    Permalink

    最近开始看bubble,发现有很多问题看不明白,bubble的centrality用的无限洪泛的方法,然后计算节点落在源目的节点对上的最短路径上的次数,来作为计算centrality的度量,这里的无限洪泛是如何实现的?还有就是bubble的社区检测算法,没看明白,他说结合了k-clique和WNA,没明白是如何实现,能否帮忙解释一下?谢谢

    Reply
    • Monday March 30th, 2015 at 11:03 PM
      Permalink

      (1) Centrality无限洪泛是什么意思?Bubble Rap求centrality:从traces文件建立contact graph(权重表示节点对相遇时间的累加),在contact graph基础上,求betweenness centrality。(2) Community detection 坦率地说,我也不知道作者是怎么结合k-clique和WNA,最后我用Louvain方法求的community,Louvain更多信息,可以参考:https://sites.google.com/site/findcommunities/

      Reply
      • Tuesday March 31st, 2015 at 09:19 AM
        Permalink

        非常感谢你的及时回复!哦,我又仔细看了看,bubble中用无限洪泛法是为了求得时变网络联系图的,然后图的权重是根据相遇时长计算的来得,那意思是不是说相当于这个centrality的计算还是根据历史相遇时长来决定的了?历史相遇时长和相遇次数这两个指标如何衡量,有的节点对相遇时间非常短但是次数很多,有的则反之。另外,你用的Louvain算法进行社区划分,区分度如何?能实现重叠社区检测吗?

      • Tuesday March 31st, 2015 at 08:59 PM
        Permalink

        其实我也有点困惑,BubbleRap论文的确说权重可以根据相遇次数和相遇时间求得,但在实现部分也没明确说明是怎么求的。我是把相遇的累加时间作为权重。是的,论文先是根据整个数据集建立contact graph,在些基础上求centrality, community。当然,论文的后部分,也提出了如何动态或者分布式求centrality, community。以下是我用Louvain Method做的社区检测(社区不重叠,non-overlapping):realityNumber of Clusters: 6Modularity: 0.288028infocom06Number of Clusters: 4Modularity: 0.373748infocom05Number of Clusters: 5Modularity: 0.438567cambridgeNumber of Clusters: 7Modularity: 0.282373

  • Wednesday January 7th, 2015 at 11:09 PM
    Permalink

    恩 我个人感觉bubble的算法里 那个邻居阈值比较难处理。。你是用reality做的?要是infocom05 06的你觉得怎么处理比较好。

    Reply
    • Wednesday January 7th, 2015 at 11:49 PM
      Permalink

      Bubble Rap用到的community detection是:WMA + k-clique,具体是怎么求的,不得而之。我最开始用k-clique求,都没求出来,后来只用WMA求,modularity最高的情况下,社区数目都高达10几个,显然不合理。最近,我打算用Louvain方法做community detection. 关于数据集,我最开始只在infocom06上测试,现在我把范围扩大到4个数据集,看能不能有新发现。PS: 从datasets建立contact graph,你打算怎么指定间的权值?求duration,我碰到了不少问题。

      Reply
      • Thursday January 8th, 2015 at 12:12 AM
        Permalink

        WMA 我没仔细研究 因为作者另外一篇论文中 有对其分布式社区探测有对比 虽然复杂 但是效果一般但是 Simple 和 KClique 比较好理解 论文是Distributed Community Detection in Delay Tolerant Networks 。。。。现在问题是 不知道作者对数据集 各个节点之间边 都是怎么设定的 根据那篇论文 好像是通过设定不同时间 对社区划分效果进行对比 选取时间但是 感觉每个数据集 都这样做 很麻烦 主论文里 作者就对reality有一个比较定性的分析。。设定了 两个值

      • Thursday January 8th, 2015 at 01:02 AM
        Permalink

        边的权值,duration,怎么设定。最简单的方法是对整个数据集的节点对的duration进行累加,这样就得到一个静态的图。往前进一步,选择某个时间间隔(如5小时),5小时内的duration累计,每5小时更新一次。我认为Bubble Rap论文用的是前一种,论文后半部分有讲到如何分布式,动态求节点中心度,社区,但更像是discussion部分。

      • Thursday January 8th, 2015 at 02:12 AM
        Permalink

        嗯 对 主论文 可能使用的是集中式的划分 预处理 分析 然后 再根据label传输 但是作者论文的也描述了图的边形成是由交互时间产生 阈值没达到 就不认为两点间有边 reality数据集讨论 他会议那篇文章有说 期刊上的好像说的不清楚 bubble有两篇 有些地方略微不太一样 但是他那篇distributed community能看出来是认为两节点间通信时间累计超过某个阈值 认为其之间产生边 感觉bubble算法应该更倾向于用分布式社区划分来传输 而且分布式符合dtn环境不然实际运行时算法没法工作因为无法获得全局节点信息。。。

      • Thursday January 8th, 2015 at 05:33 AM
        Permalink

        找到之前跟Pan HUI的邮件,部分内容如下:(iii) the contact graphAs shown in your paper, datasets can be modeled as a contact graph where the weight of an edge represents durations between two nodes. Based on my understanding, the dynamic contact graph is converted into static one by assigning the weight of an edge as the sum of duration for each interval. Am I right?得到他的回复是:You are right about the point (iii)

      • Thursday January 8th, 2015 at 10:14 AM
        Permalink

        恩 边之间权值是用节点历史累计交互时间但是 我觉得有个边的阈值在里面 不然对于数据集形成的图是 是带权值的全连通图了每个节点在运行当中基本都和其他节点有过交互 这样集中式情况下KClique不好处理PS:其实可以和哪个人用中文交流他本身是中国人。。我记得很久以前 我还在知网上搜到过他和国内人发的论文

      • Thursday January 8th, 2015 at 04:47 PM
        Permalink

        我的建议是先找个算法把community求出来,把路由实现了,看看仿真结果,而后再想着让community detection更精确。以下是我用Louvain Method做的社区检测(社区不重叠,non-overlapping):reality Number of Clusters: 6 Modularity: 0.288028infocom06 Number of Clusters: 4 Modularity: 0.373748infocom05 Number of Clusters: 5 Modularity: 0.438567cambridge Number of Clusters: 7 Modularity: 0.282373

      • Thursday January 8th, 2015 at 04:47 PM
        Permalink

        我的建议是先找个算法把community求出来,把路由实现了,看看仿真结果,而后再想着让community detection更精确。以下是我用Louvain Method做的社区检测(社区不重叠,non-overlapping):reality Number of Clusters: 6 Modularity: 0.288028infocom06 Number of Clusters: 4 Modularity: 0.373748infocom05 Number of Clusters: 5 Modularity: 0.438567cambridge Number of Clusters: 7 Modularity: 0.282373

      • Thursday January 8th, 2015 at 02:14 AM
        Permalink

        还有你做图的处理是用的什么软件?复杂网络的?可以可视化吗?

      • Thursday January 8th, 2015 at 05:22 AM
        Permalink

        我用networkx(复杂网络的python包),matplotlib库作图。最近用louvain作社区检测,了解了Pajek,但生成图不直观。还有一个叫Gephi,可视化比较好。

      • Monday November 2nd, 2015 at 04:35 PM
        Permalink

        这上面显示的时间是今年的时间么,上面的讨论我都看了,貌似大神已经出国了,不知道还在研究机会网络么?
        好遗憾,才发现这么好的学习空间,上面的这个链接里放的是Bubble Rap修改版,虽然叫Bubble,但实际是一个叫LDC的路由协议。用过计算长、短相遇时间,组成效用函数进行信息转发。效果很好,在Infocom06数据集下可以达到将近90%的传输成功率,路由开销也很不错。

      • Friday November 6th, 2015 at 07:59 AM
        Permalink

        你好。我现在还在从事DTN网络编码的研究。LDC路由协议?

        你现在是用哪份源代码,我发现the-one-pitt这份源代码有不少bug。

  • Pingback: The ONE使用笔记:目录 | Spark & Shine