从社会性角度分析MANET节点移动轨迹特征

 

　　移动自组网（ MANET） 是由一组带有无线收发装置的移动终端组成的一个多跳的临时性自治系统，它的每个节点在网络中随机地移动，通过无线连接组成任意的网络拓扑结构。在移动自组网中进行拓扑发现，对提高移动自主且网路由策略。QoS和功率控制等性能具有重要意义。由于节点的移动性、无线通信等特点，网络拓扑处于动态变化中，这种拓扑动态变化的特点使得源节点和目的节点间的有效通信变得困难，也为设计可靠快速的拓扑发现策略提出了一系列的问题。

　　人控移动设备构建的自组网环境下，真实的移动模型应当体现节点的社会性[3].因为，现实场景中的移动设备通常由人携带或控制，而人作为一种社会存在物，其交往活动受个体的意识、需要、社会行为等影响，具有交往社会性[4,5].社会性是节点移动的一个重要特性[3,6].但目前自组网研究只是根据现实场景下移动设备轨迹获取的一些移动特征[3,6],缺乏表征节点社会性的参数。

　　因此，本文通过分析现实场景下节点的移动轨迹，得到移动轨迹的链路持续时间分布和熟悉度-频繁度的特征，并从社会学角度，对两种分布特征产生的原因进行了深入的分析，证明了两种分布特征可体现现实场景中节点移动的社会性和节点组织关系的社会性。这对社会网络环境下自组网的仿真研究和应用具有重要意义。

　　1 节点移动特征的实验分析

　　本文选用着名的Haggle项目所采集的3个不同现实场景下节点的移动轨迹，来分析节点的移动特征。

　　1.1 移动数据集

　　RAWDAD组织提供的Haggle项目的3个数据集，分别在Intel研究合作实验室、剑桥大学的计算机实验室、Grand Hyatt Miami的IEEE会议环境下采集人携带无线设备的移动数据。为方便起见，3个数据集分别简称为Intel、Cambridge和Infocom05.实验所用的无线设备分为iMote设备和外部设备两种，采集了携带iMote设备节点之间、携带iMote设备节点与携带外部设备节点之间在彼此通信覆盖范围内的链路持续时间，而没有采集携带外部设备节点之间的链路持续时间。为了提高实验分析结果的有效性和正确性，只考虑携带iMote设备节点之间的链路持续时间数据。

　　为分析现实场景与仿真模型的移动特征差异，选择目前广泛采用的随机路点模型RWP（Random Waypoint Model）[8]和参考点组移动模型RPGM（Reference Point Group Model）[9].RWP的参数设置同参考文献[3],100个节点在5 000 m×5 000 m的区域内运动，通信半径为250 m,仿真时间为24 h,节点运动速度和速度分别为1 m/s、6 m/s,暂停时间和暂停时间分别为1 s、10 s.在RPGM中，节点共分10组，其余参数设置同RWP.多组实验结果显示置信度达90%以上。

　　1.2 实验分析方法

　　从链路持续时间的互补累积分布CCDF（Complemen-tary Cumulative Distribution Function）和熟悉度-频繁度两方面来考察移动轨迹特征。

　　采用互补累积分布的优点在于它考虑到所有的原始数据，避免了用直方图绘图时落入同一直方内的数据值差异的缺陷，同时也控制了尾部噪音。

　　链路持续时间的互补累积分布p（T）用来反映数据集中两个节点间链路持续时间取值大于某个常数T的概率。

　　定义2 熟悉度-频繁度：以数据集中节点j与节点k直接通信的次数fj,k表示节点间的通信频度。节点j与节点k在fj,k次直接通信中链路持续时间的累加和表示两节点的亲密度，和值越大，亲密度越高，也表明两个节点的社会关系越紧密。为了研究节点间的组织关系特征，计算数据集中所有节点对的亲密度和通信频度，画散点图，用x轴表示亲密度，y轴表示通信频度，便得到节点间的熟悉度-频繁度，如图1所示。

　　根据格拉诺维特1973年在《美国社会学杂志》上发表的论文中对强弱关系的定义[11],将熟悉度-频繁度中节点间的组织关系分为四类：社团关系、熟悉的陌生人关系、陌生人关系、朋友关系（为简便起见，将四类关系依次记为I、II、III和IV）。社团关系的节点对亲密度高，通信频繁度多；陌生人关系的节点对亲密度低，通信频繁度少；熟悉的陌生人关系的节点对亲密度低，通信频繁度多；朋友关系的节点对亲密度高，通信频繁度少。陌生人关系称为弱关系，其他三类统称为强关系。

　　1.3 实验结果

　　计算各数据集的链路持续时间的CCDF,如图2（a）和图2（b）所示，实际数据集的链路持续时间分布曲线在双对数坐标下基本为直线形式，具有幂律特征，表明较长的链路持续时间比例极小，较短的链路持续时间比例很大。数据集中节点间链路持续时间取值所占百分比如表1所示。RWP服从指数分布，其分布曲线在半对数坐标下表现为一条直线。仿真模型RWP和RPGM与实际数据集的链路持续时间CCDF有显着不同。

　　由各数据集中节点的熟悉度-频繁度可以看出，实际数据集中属于弱关系的节点对分布密集，所占比例很大，分别为97.95%、98.72%、99.2%,而处于强关系的节点对比例很少，分别为2.05%、1.28%、0.8%,约占1%~3%,即实际场景中绝大多数节点为弱关系，极少数节点为强关系。两种仿真模型中属于强关系的节点对比例很大，分别为33.66%、79.41%.仿真模型RWP和RPGM与实际数据集的熟悉度-频繁度特征差异显着。

　　为分析节点组织关系特征与时间的关系，考察实际数据集中不同采样时间长度内的节点熟悉度-频繁度。由于3个实际数据集的熟悉度-频繁度具有相同特性，不妨以Infocom05数据集为例，取时间长度分别为100 000 s、150 000 s、200 000 s、250 000 s,得到节点的熟悉度-频繁度，如图3所示。可以看出，不同统计时间内四类关系节点的比例基本维持不变，弱关系节点分布密集，强关系节点比例很少。

　　作为对比，本文还分析了仿真模型RWP下不同采样时间长度内的节点熟悉度-频繁度。可以看出，RWP中四类关系节点的比例随时间变化。这说明仿真模型RWP与现实场景的熟悉度-频繁度有很大差异。

　　2 实验结果对社会性诠释

　　2.1 节点移动的社会性

　　着名经济学家帕累托（Pareto）发现了二八定律，指出20%的人口拥有社会上80%的财富。后来人们发现，二八定律所反应的现象普遍存在于自然界和人类社会生活的各个方面[12].

　　根据参考文献[12],在人类的交往活动中，20%的人占据了交往时间的80%,而80%的人只占据了交往时间的20%.着名复杂网络研究者艾伯特-拉斯洛·巴拉巴西指出，只要二八定律成立，就能说其中蕴含幂律，幂律是用数学公式表明了少数几个大事件承载了大多数的活动[13].可见，人的交往活动现象蕴含幂律，这种幂律特征对移动自组网中人控移动节点的移动行为的影响表现为少数节点长时间在彼此的通信覆盖范围内移动，大量节点很少移动到彼此的通信覆盖范围内。若用链路持续时间表示节点在彼此的通信覆盖范围内移动，那么正是这种满足二八定律的社会性，使得在分析采集的移动轨迹时，得到链路时间分布具有幂律分布特征。由此说明，链路持续时间的幂律分布特征体现了一定社会环境下节点移动的社会性。

　　如前所述，仿真模型RWP和RPGM与实际数据集的通信持续时间CCDF有显着不同。这是因为，在RWP中，节点独立、随机地选择运动方式和状态，一个节点与其他每个节点在彼此通信覆盖范围内的概率相同，节点的链路持续时间取值较集中，大多在某一均值附近波动，这不符合幂律分布特性；而在RPGM中，各组中心点的运动是随机独立的，整组的运动与RWP中单个节点的运动方式一样，因此RPGM中节点的链路持续时间也不符合幂律分布特性。可见，从链路持续时间来看，RWP和RPGM都没有很好地描述现实场景中节点的社会性特征。链路持续时间的分布特征可有效地衡量现实场景和仿真模型中节点移动特征的差异。

　　2.2 熟悉度-频繁度特征体现节点组织关系的社会性

　　2.2.1 四类关系节点的比例差异

　　社会学家发现，现实社会中，组织关系的社会性表现为人们之间处于不同的组织和社会关系，不同亲密程度的关系所占比例符合一定的规律，并且这种社会关系在一段很长的时间内保持稳定[14-16].这在现实场景中表现为，少数个体关系亲密，碰面次数较多，接触时间长，而大部分个体碰面次数少，接触时间短，甚至从不来往。换言之，现实场景中绝大多数节点为弱关系，极少数节点为强关系。所以，属于弱关系的节点对分布密集，所占比例很大，而处于强关系的节点对比例很少。这与实验所得结论一致。真实场景下4类关系节点比例与仿真模型RWP和RPGM有显着不同。这是因为，在RWP中，节点之间独立无关，与现实场景中节点分属不同的组织关系有较大差异；在RPGM中，每个节点预先分配归属为某个组，且组织关系在整个仿真时间不变，而处于一定社会关系中的人因自身兴趣或交流需要，在不同时期处于不同的组或群体中，即RPGM的节点组织关系比例与现实场景有很大不同。由此表明，熟悉度-频繁度中不同关系节点的比例差异能用来衡量移动模型中节点移动特征的差异。

　　2.2.2 节点组织关系的时间无关性

　　在社会学理论中，社会网成员之间的关系保持不变的性质就是社会网的持久性连接的持久性，个人社会网的连接关系很强， 相对而言网络成员间的关系较持久和稳定[17],即现实社会中人的组织关系在一段时期内相对稳定。也就是说，现实场景下，熟悉度-频繁度中节点四类关系的比例基本保持不变，这与实验（如图3所示）结论一致。

　　而RWP和RPGM没有此种特性。因为随机移动模型中，一个节点与其他每个节点在彼此通信覆盖范围内的概率相同，所以仿真时间越长，一个节点与其他每个节点直接通信的次数越多，节点间的总通信持续时间就会越长，所以RWP中节点熟悉度-频繁度会向上和向右偏移。随仿真时间延长，III类节点比例减少，I类、II类和IV类比例相应增加。RPGM的熟悉度-频繁度情况与RWP类似，RPGM中组内节点关系不变，整组的运动与RWP中单个节点的运动方式一样，都为完全随机移动。

　　现实场景中节点的熟悉度-频繁度的特征很好地体现了一定社会环境下人的组织关系特性，且这种特性在一段时间内相对稳定。而RWP、RPGM与实际数据集的熟悉度-频繁度差异很大，熟悉度-频繁度的时间无关性特征可有效地衡量实际场景与仿真模型中节点移动特征的差异。

　　现实场景中移动终端通常由人携带或控制，而人因自身兴趣或交流合作的需要移动并与其他个体关联。本文依据社会学知识，说明了现实移动场景的社会性体现在节点移动的社会性和节点间组织关系的社会性，提出真实场景下移动轨迹的链路持续时间的幂律分布特征和熟悉度-频繁度特征体现了一定社会环境下节点的社会性，并通过实验证明了两种分布特征可以衡量移动模型节点移动特征的差异。因此，研究基于人控移动设备构建的自组网设计移动模型时，可从链路持续时间分布和熟悉度-频繁度来考察移动模型的节点移动和组织关系的社会性。