数据集Infocom06分析:求所有重叠区间(附源码)

数据集Infocom06记录了节点相遇情况,对其分析会发现节点i与节点j检测到对方的时间往往不一致,考虑到节点间通信需要同步,这样的话,求出节点间相遇的所有重叠区间,就可将有向图转化成无向图,便于后续分析(如社区检测)。本文先简单介绍数据集的格式,再结合源代码介绍求其重叠区间。

1. Infocom06格式

Haggle项目收集的数据集,格式很一致,通常包含若干文件。最有用的文件是contacts.Exp*.dat,描述设备间相遇情况,描述节点i从时间t1到时间t2遇到节点j,即前4列(node_i  node_j  start  end),后面两列是基于前面4列组成文件计算得到的。详情见博文《Bubble Rap数据集Infocom05, Hong-Kong, Cambrige, Infocom06, Reality》。取部分行如下:

13    2    7261    7499    1    0
2    13    7289    7516    1    0
13    2    7866    8598    2    367
2    13    7997    9223    2    481

细心的你会发现,节点13检测到节点2的时间(7261)与节点2检测到节点13的时间不一样(7287),考虑到节点间通信需要同步,即只有在重叠区间方可通信(这样理解对吗?)。接下来介绍如何求出节点间所有的重叠区间。

2. 求重叠区间

我的方法有些笨,用shell脚本和awk脚本。先用grep将节点对过滤出来,并用sort对开始时间(左区间)排序,最后用awk脚本求其重叠区间并输出。

2.1 过滤节点对并排序

用grep命令将节点对保存在一个临时文件并排序,作为参数传给awk脚本,主要源代码如下:

devices=$(cat $contact_file | cut -f 1 | sort -n | uniq | wc -l)
for ((i=1; i<=devices; i++))
do
    for ((j=i+1; j<=devices; j++))
    do
        #grep all the contact between node i and node j
        grep "^$i $j " $tmp_duration_filter_file >> $tmp_duration_file
        grep "^$j $i " $tmp_duration_filter_file >> $tmp_duration_file
        sort -k3,3n $tmp_duration_file >> $tmp_overlapping_interval_file

        #count overlapping interval between node i and node j
        if [ -s  $tmp_overlapping_interval_file ]
        then
            awk -f contact_duration.awk $tmp_overlapping_interval_file >> $sum_contact_duration_file
        fi
    done
done

注:本例grep的正则表达式是grep “^$i $j “,这是因为我将datasets处理过了,即将时间间隔为0的行过滤掉并用空格作为输出分隔符。原数据集是用TAB作为分隔符,先按ctrl+v,再按TAB在vim输入TAB分隔符。

2.2 求重叠区间

经过上述的步骤,节点对的开始时间按递增排序,这里无须在乎节点的顺序(如1 3还是3 1)。两区间的重叠情况有如下3种(第二个区间的左区间总比第一个左区间要大,因为排序过):没有重叠、部分重叠、被包含。

image

图1 重叠区间3种情况

awk脚本源代码如下,主要源代码已加粗:

function max(a, b)
{
    return a>b?a:b
}

function min(a, b)
{
    return a<b?a:b
}

BEGIN {
    node_i = 0
    node_j = 0

    pre_start = 0
    pre_end = 0
    cur_start = 0
    cur_end = 0
    overlapping_start = 0
    overlapping_end = 0

    duration = 0
    sum_contact = 0
    sum_duration = 0
}

{
    node_i = min($1, $2)
    node_j = max($1, $2)

    if (NR == 1) {
        pre_start = $3
        pre_end = $4
    }
    else 
    {
        cur_start = $3;
        cur_end = $4

        if (cur_start > pre_end) #no overlapping
        {
            pre_start = cur_start
            pre_end = cur_end
        }
        else if (cur_start <= pre_end) #overlapping
        {
            pre_start = max(pre_start, cur_start)
            pre_end = max(pre_end, cur_end)

            overlapping_start = max(pre_start, cur_start)
            overlapping_end = min(pre_end, cur_end)
            duration = overlapping_end - overlapping_start
            
            sum_duration += duration
            sum_contact++
        }
    }
}

END {
    if (sum_contact!=0 && sum_duration!=0)
    {
        print node_i, node_j, sum_contact, sum_duration
    }
}

3. 数据分析

上述中,还求出所有节点对总的相遇时间、总的相遇次数,有了这些,就可以对该数据集进一步分析,如Bubble Rap论文中的number of contacts、contacts duration分布图,社区检测(community detection)。我也做了同样的分析,但结果不是很理想,求交流:Jelline@126.com

发表评论

电子邮件地址不会被公开。 必填项已用*标注

2 thoughts on “数据集Infocom06分析:求所有重叠区间(附源码)

  • 2017年11月30日 星期四 at 10:18上午
    Permalink

    楼主,根据你所说的,节点对之间相遇的检测时间是不一致的,而实际one仿真时节点间通信又是同步的,所以都应该先对原始数据集进行重叠区间的处理,然后再转换成one标准格式导入one中,我想问的是既然节点间通信是同步的,那原始数据集中节点对相遇的检测时间为什么会不一致呢?原因是什么?会不会可能实际上应该取两个时间段的并集更合理呢?

    Reply
    • 2018年01月17日 星期三 at 10:16上午
      Permalink

      很抱歉,这么迟才回复。

      我是这么理解的,节点A发现节点B(节点B广播的数据包被A监测到了),但因为A和B在同一个时间只能有一个节点使用同一信道,此时节点B还不知道节点A就在它的通信范围内。或者说两个节点建立连接需要时间。当然,这也取决于实验者是怎么采集数据的,我没有找到他们采集数据的细节。

      我认为并集是不合理,因为时间轴最开头的部分,连接还未建立,最末端的部分,连接已经断开。所以,我觉得取交集更为合理。我将交集解释为两个节点连接已建立,这样他们就可以通信了。

      Reply