MANET节点移动轨迹特征的社会性分析

柳巧平，李晓鸿，王 东

（湖南大学 计算机与通信学院，湖南 长沙410082）

移动自组网MANET(Mobile Ad-hoc Network)可以广泛地应用于战场通信指挥与控制、警察与医疗部门的抢险救灾等领域，应用前景广阔[1，2]。 目前，对移动自组网的研究主要采用仿真的手段[2]。能够生成节点移动轨迹的移动模型是仿真的基础。在自组网MAC协议、路由协议、广播算法、组播算法等研究中，为了提高这些研究工作的意义，要求移动模型能准确、真实地反映现实场景下移动设备的移动特征，所以移动模型的真实性对自组网研究至关重要[3]。

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

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

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

本文选用著名的Haggle项目[7]所采集的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(Complementary Cumulative Distribution Function)和熟悉度-频繁度两方面来考察移动轨迹特征。

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

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

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

(1)希望学生通过实验理解常见分布的特点。比如通过更改参数λ的大小,可以发现,随着参数λ的增加,泊松分布的密度函数峰值向右偏移,而且泊松分布总是在参数λ附近取得较大概率值,而在距离λ较远处,概率值迅速向零衰减。又如对于正态分布,当参数μ固定时,改变σ的大小,分布的密度函数的陡峭程度发生改变,σ越小,分布越陡峭,而当参数σ固定时,改变μ的大小,分布的密度函数会左右平移,这样可以帮助学生理解μ为位置参数,而σ是形状参数。以正态分布N(0,1)为例,绘制密度函数和分布函数图在R中可以用命令

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

图1 链路持续时间的熟悉度-频繁度

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]。

表1 节点间链路持续时间取值所占百分比

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

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

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

社会学家发现，现实社会中，组织关系的社会性表现为人们之间处于不同的组织和社会关系，不同亲密程度的关系所占比例符合一定的规律，并且这种社会关系在一段很长的时间内保持稳定[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与实际数据集的熟悉度-频繁度差异很大，熟悉度-频繁度的时间无关性特征可有效地衡量实际场景与仿真模型中节点移动特征的差异。

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

[1]BAI F，SADAGOPAN N，HELMY A.Important：a framework to systematically analyze the impact of mobility on performance of routing protocols for ad hoc networks[C].The 22nd IEEE INFOCOM,2003：825-835.

[2]刘珩，安建平.MANET移动模型分析与仿真实验[J].计算机工程，2006，32(17)：38-40.

[3]MIRCO M，CECILIA M.Designing mobility models based on social network theory[J].ACM SIGMOBILE Mobile Computing and Communications Review，2007，11(3)：59-70.

[4]周宏.雅斯贝尔斯交往理论探析[J].现代哲学，2000，59(1)：85-91.

[5]龙柏林.个人交往主体性的本质结构[J].浙江社会科学，2004(5)：139-151.

[6]PAN Hui，JON C.Bubble Rap：forwarding in small world DTNs in ever decreasing circles[R].Cambridge：University of Cambridge Computer Laboratory，2007(684)：1-44.

[7]Haggle project.RAWDAD[DB/OL].[2006-09-15].http：//crawdad.cs.dartmouth.edu/meta.php?name=cambridge/haggle.

[8]JOHNSON D，MALTZ D.Dynamic source routing in ad hoc wireless networks[C].Mobile Computing，1996：153-181.

[9]HONG Xiao Yan，GERLA M.A group mobility model for Ad hoc wireless networks[C].Proceedings of the ACM/IEEE MSWiM′99，1999：53-60.

[10]汪小帆，李翔，陈关荣.复杂网络理论及其应用[M].北京：清华大学出版社，2006.

[11]肖鸿.试析当代社会网络研究的若干进展[J].社会学研究，1999(3)：1-11.

[12]莫露茜.浅析客户关系管理逻辑中的“二八定律”和“长尾理论”[J].工业技术经济，2009，28(6)：92-93.

[13]艾伯特-拉斯洛·巴拉巴西.链接网络新科学[M].徐彬，译.长沙：湖南科学技术出版社，2007：78-93.

[14]AUGUSTIN C，PAN Hui，JON C，et al.Pocket switched networks：real-world mobility and its consequences for opportunistic forwarding[R].Cambridge：University of Cambridge Computer Laboratory，2005(617)：1-26.

[15]邓肯.J.瓦茨.小小世界——有序与无序之间的网络动力学[M].陈禹，译.北京：中国人民大学出版社，2006：10-161.

[16]贺寨平.国外社会支持网研究综述[J].国外社会科学，2001(1)：76-82.

[17]方壮志.社会网研究的基本概念和方法[J].华中理工大学学报，1995，25(3)：111-115.