首页> 中国专利> 基于移动社交网络节点社会特性的机会路由行为建模方法

基于移动社交网络节点社会特性的机会路由行为建模方法

摘要

本发明公开了一种基于移动社交网络节点社会关系特性的机会路由行为建模方法,特征是利用相应的随机生成算法构造并挖掘任意网络节点对之间的社会关系网跳数距离和社团归属关系,基于所获取的上述社会特性,结合若干可根据需要调节的模型参数,为节点对间的相互接触频率与协作概率依照它们社会关系的亲疏程度有差别地建模。采用本发明方法建立机会路由行为模型,相比于现有的建模方法,能通过充分挖掘节点间的宏观和微观社会关系特性为社会性网络节点间的机会路由行为特性提供更完备的模型定义,为移动社交网络中设备间路由传输技术的开发与革新及其机会投递行为相关科学问题的研究提供更为合理而便捷的仿真基础。

著录项

  • 公开/公告号CN103595623A

    专利类型发明专利

  • 公开/公告日2014-02-19

    原文格式PDF

  • 申请/专利权人 中国科学技术大学;

    申请/专利号CN201310626892.1

  • 发明设计人 张四海;钱岑;秦晓卫;周武旸;

    申请日2013-11-28

  • 分类号H04L12/58;H04L12/701;G06F17/30;

  • 代理机构安徽省合肥新安专利代理有限责任公司;

  • 代理人汪祥虬

  • 地址 230026 安徽省合肥市包河区金寨路96号

  • 入库时间 2024-02-19 22:27:24

法律信息

  • 法律状态公告日

    法律状态信息

    法律状态

  • 2017-01-25

    授权

    授权

  • 2014-03-19

    实质审查的生效 IPC(主分类):H04L12/58 申请日:20131128

    实质审查的生效

  • 2014-02-19

    公开

    公开

说明书

技术领域

本发明属于社会性移动自组织网络(socialized mobile ad-hoc network)中的机会路由 技术领域,特别涉及基于移动社交网络节点的社会关系进行行为建模的方法。

背景技术

近年来智能终端设备的应用日益广泛,这些设备具有自发组织形成非连续 (intermittent)、延迟容忍(delay-tolerant)的无线移动网络并进行数据交换的潜能,所涉及 的具体组网技术包括蓝牙(bluetooth)、设备到设备(device-to-device)等,这种特殊的自组 织网络又被称为移动社交网络(Mobile Social Network)。移动社交网络中的用户节点即 智能终端的持有者之间能随机发生移动,《美国计算机协会移动自组织网络会议》 (MobiHoc’09,May18-21,2009,New Orleans,USA)等学术文献多次提及:任意随机移动 的自组织/延迟容忍网络节点之间相互接触事件的发生过程可用泊松过程予以合适地描 述;《美国电气与电子工程师协会快报》(IEEE COMMUNICATIONS LETTERS,VOL.13, NO.12,DECEMBER2009)提到所有节点对之间关系完全等同化的随机行走节点相互接 触事件的泊松过程参数λ可表征为下式所示的随机同质节点接触频率模型:

λ=c·υ0·RA

式中A表示一个节点移动的正方形仿真区域,υ0表示节点间的平均相对速率,R表示 节点的通信半径,而c是表征同质化随机移动模型的常数。然而,移动社交网络相比于 传统的移动自组织网络具有另一个重要特征,即节点间的相互社会关系。节点对之间社 会关系的亲疏,深刻地影响着节点对之间的两大机会路由特性:社会关系亲近的节点接 触的频繁度也随之增加;自私性(selfishness)决定一个移动社交节点为其他节点的数据分 发提供协作的概率,其中社会自私性(social selfishness)特别地随节点间社会关系的亲疏 而增减,从而社会特性将显著影响移动社交网络的机会路由性能。此类社会特性使得在 开发与革新移动社交网络设备间的路由技术以及研究网络中的机会投递行为相关科学 问题时,必须将节点间的社会倾向性对路由行为的影响作为重要考量因素。然而,由大 量真实的移动社交节点构建具有社会特性的测试场景在实现上具有较大难度,因此亟需 有效的仿真平台用于建模移动社交网络节点间的社会关系及其对于节点间机会路由行 为的影响,从而为相应的技术研发和科学研究提供便捷、可靠的仿真基础。

目前已有的对于移动社交网络节点的社会关系及其所决定的节点间机会路由行为 的建模方法主要包括从真实社会行为的跟踪记录中获取以及依据社会关系特性进行构 造性的行为建模。在真实社会节点行为跟踪搜集与建模方面,《美国电气与电子工程师 协会学报》(IEEE TRANSACTIONS ON MOBILE COMPUTING,VOL.10,NO.11, NOVEMBER2011)中提到了通过对若干携带移动设备的人之间相互移动与接触行为的 跟踪记录进行建模,从而获得了一些真实追踪数据集,如剑桥(Cambridge)数据集、国 际计算机通信会议06(Infocom06)数据集及香港(HK)数据集等。这类数据集的优势在于 源自真实人类社会,具有较强的典型性;其主要缺点在于仅记录某一特定场景下的节点 活动规律而不能通过参数调节模拟多种场景,且能搜集到的数据所描述的行为通常仅包 括节点间的移动接触行为,但至今还缺乏节点彼此的协作规律或其他信息。《美国电气 与电子工程师协会快报》(IEEE COMMUNICATIONS LETTERS,VOL.14,NO.11, NOVEMBER2010)中提及了针对社会性延迟容忍网络(Delay-tolerant Networks)节点带 有自私性的机会路由行为所建立的仿真模型,该模型考虑了节点可能所属的不同社团 (community)划分关系,并以此为依据将属于同社团/不同社团的节点对之间的接触频率 与协作转发概率分别定义。然而这种建模方式仅考虑了节点的宏观社团属性,而缺乏对 于网络中单一节点对之间的特定社会关系及其影响下的节点机会路由特性的描述。

发明内容

本发明的目的是提出一种基于移动社交网络节点社会特性的机会路由行为建模方 法,通过充分挖掘节点间的宏观和微观社会关系特性为社会性网络节点间机会投递中的 接触频繁度与协作转发概率参量给出更完备的模型定义,以弥补现有真实行为追踪建模 方法中所建模场景与行为单一的缺点和构造性建模方法中所考虑社会属性不全面的缺 点,为移动社交网络中设备间路由传输技术的开发与革新及其机会投递行为相关科学问 题的研究提供更加合理而便捷的仿真基础。

本发明基于移动社交网络节点社会特性的机会路由行为建模方法,设N个移动社交 网络节点散布于一个方形封闭区域内并在社会关系的影响下随机移动,每个节点都携带 全向天线式的移动设备,当任意两个节点进入彼此的通信半径(communication range)即 意味着一次接触的发生,发生接触的节点可进行数据交换;采用新增节点随机优先连接 系数m=2的巴拉巴西-艾伯特(Barabasi-Albert,简称BA)无标度网络模型随机生成节点 间反映它们社会连接亲疏的无向社会关系网络;进一步采用戈尔文-纽曼 (Girvan-Newman,简称GN)算法将该社会关系网划分为两个社团并为节点加上对应的 社团标签(label);采用泊松过程描述任意移动社交网络节点对之间的随机接触行为,并 将任意潜在发送节点a与潜在接收节点b之间的相互接触泊松过程参数记为λab;其特 征在于:针对移动社交网络节点的机会路由场景,按照如下步骤获取网络中任意潜在 发送节点a与潜在接收节点b之间的机会路由行为相关特性:

第一步:通过检验前述社团标签获得任意潜在发送节点a与潜在接收节点b是否属 于同一社团的信息,若二者属同社团节点,则记社团属性参量C(a,b)>0,反之令该参量 C(a,b)=0;基于前述生成的节点间社会关系网,利用广度优先搜索算法获取任意潜在发 送节点a与潜在接收节点b在社会关系网中的跳数距离D(a,b);

第二步:依照前述获取的特定节点对间的社会关系参数,基于真实社会中关系亲近 的移动社交节点接触更频繁的特征拓展下式所示随机同质节点接触频率模型:

λ=c·υ0·RA

其中A表示一个节点移动的正方形仿真区域,υ0表示节点间的平均相对速率,R表示 节点的通信半径,c是表征同质化随机移动模型的常数;将任意潜在发送节点a与潜在 接收节点b间相互接触事件泊松过程参数λab以如下社会性节点接触频率模型公式表 示:

λab=1+C(a,b)[D(a,b)]r·υ0RA

其中社会链路影响参数r>0是一个可变的、用于控制节点间社会关系跳数距离对节点行 为影响强度的指数;是一个被所有节点对共享的仿真背景常量,其单位为:接触 次数/虚拟仿真时隙;基于真实社会中移动社交节点更倾向为与之社会关系更近的节点 提供协助的特征,将任意潜在发送节点a与潜在接收节点b在相遇时任意一方发起协作 转发请求时另一方接受的概率Pab以如下协作概率模型公式表示为:

Pab=1+C(a,b)β·[D(a,b)]r

其中自私性强度参数β>0表征一个可控制节点间社会自私性总体强弱的变量;

第三步:所有节点对之间的接触和协作行为按上述规则建立后,启动仿真模型使之 开始运行;每经过网络中节点可完成基本协作转发操作的任意单位仿真时隙(t0,t0+1), 即更新节点间的接触信息,该单位时隙内任意潜在发送节点a与潜在接收节点b发生接 触的概率P(Xab(t0+1)-Xab(t0)>0)可以节点间的相互接触事件泊松过程模型公式表示如 下:

P(Xab(t0+1)-Xab(t0)>0)=Σk=1P(Xab(t0+1)-Xab(t0)=k)=Σk=1(λab)k·e-λabk!=-1-e-λab

如果任意节点对以概率地在单位仿真时隙(t0,t0+1)内发生了接触,且两个节点间任 一方需要对方为其自身转发数据,则另一方依照协作概率模型所定义的概率决定是否为 其进行协作转发。

由于本发明基于移动社交网络节点社会特性的机会路由行为建模方法立足于网络 节点的机会路由场景,挖掘和记录了任意移动社交节点对之间分别体现它们微观社会连 接亲疏关系与宏观社会特性的社会关系网跳数距离与社团归属关系作为参量,对与节点 间机会路由行为特性直接相关的接触频率与协作转发概率进行建模,与现有通过追踪真 实社会节点活动所获得的单纯节点接触行为数据集相比,本发明方法为节点的接触行为 与协作概率均提供了基于社会特性的建模,且模型参量如社会链路影响参数、自私性强 度参数等均可根据所需构造的不同仿真场景予以相应缩放;与现有的仅基于节点宏观社 团归属关系对节点接触频率与协作概率的建模相比,本发明方法更全面地考虑到了节点 对在其所处社交网络中的广度优先搜索距离作为它们社会关系建模的参量,使得反映宏 观社会属性的社团归属关系与反映微观节点对之间亲疏关系的社会关系网跳数距离均 以量化的形式体现在对机会路由行为的建模中,任意网络节点对之间的机会路由行为特 性均可基于它们特定的社会关系单独予以定义;本发明基于移动社交网络节点社会特性 的机会路由行为建模方法的提出,能为移动社交网络中设备间路由技术的开发与革新及 其机会投递行为相关科学问题的研究提供更为合理而又足够便捷的仿真基础。

附图说明

图1是采用基于移动社交网络节点社会特性的机会路由行为建模方法建立的仿真模 型运行500单位仿真时隙后各节点对累积接触次数的分布图。

图2是《美国电气与电子工程师协会学报》(IEEE TRANSACTIONS ON MOBILE  COMPUTING,VOL.10,NO.11,NOVEMBER2011)中所搜集的真实社会移动社交数据 集Infocom06中各节点对累积接触信息分布图。

图3是采用本发明方法所建立的仿真模型中采用不同强度的社会自私性及其平均自 私性对照组获得的投递时延曲线图;

图4是采用本发明方法所建立的仿真模型中采用不同强度的社会自私性及其平均自 私性对照组获得的投递成功率曲线图。

图5是采用本发明方法所建立的仿真模型中无条件协作场景下各节点为其它节点提 供协作次数的分布图;

图6是采用本发明方法所建立的仿真模型中引入自私性强度参数β=4的社会自私性 场景下各节点为其它节点提供协作次数的分布图;

图7是采用本发明方法所建立的仿真模型中引入自私性强度参数β=8的社会自私性 场景下各节点为其它节点提供协作次数的分布图。

具体实施方式

下面结合附图通过实施例对本发明作进一步详细说明。

实施例1:

本实施例中考察采用本发明基于移动社交网络节点社会特性的机会路由行为建模 方法所提出的仿真模型所得的移动社交网络节点对累积接触次数分布模拟真实社交性 自组织网络中搜集的同类数据的相似程度。

需建模的真实移动社交网络由具有全向天线的智能手机式移动设备节点构成,相互 间以蓝牙4.0(Bluetooth4.0)技术标准进行数据交换,网络中节点总数N=200,位于场景 尺寸A=100m×100m的区域内;使用加强发射功率蓝牙4.0标准的智能移动设备间拥有 R=25m的通信半径,设备间基本数据交换时间间隔Ts=8s,节点间平均相对移动速率 υ0=5m/s=40m/Ts,将移动设备的上述特征输入到曙光A650-G图形处理器 (DAWNING A650-G GPU)高性能计算机中,对应于硬件设备的仿真背景常量为 在本实施例中结合基于移动社交网络节点社会特性的机会路由 行为建模方法,采用新增节点随机优先连接系数m=2的巴拉巴西-艾伯特(BA)无标度网 络模型随机生成节点间的无向社会关系网络,进一步采用戈尔文-纽曼(GN)算法将所生 成的社会关系网划分为两个社团并为节点加上对应的社团标签(label),该轮仿真随机生 成的移动社交网络节点社会关系网实际被GN算法的社团发现机制划分为节点数分别 为177与23的两个社团,按照如下步骤逐个获取网络中任意潜在发送节点a与潜在接 收节点b之间的机会路由行为相关特性:

第一步:通过检验前述社团标签获得任意潜在发送节点a与潜在接收节点b是否属 于同一社团的信息,若二者属同社团节点,则记社团属性参量C(a,b)=3,反之令该参量 C(a,b)=0;基于前述生成的节点间社会关系网,利用广度优先搜索算法获取任意潜在发 送节点a与潜在接收节点b在社会关系网中的跳数距离D(a,b);

第二步:根据上一步中获取的特定节点对间的社会关系参数,拓展随机同质节点接 触频率模型,将任意潜在发送节点a与潜在接收节点b间相互接触事件泊松过程参数λab以社会性节点接触频率模型公式表示:

λab=1+C(a,b)[D(a,b)]r·υ0RA

取社会链路影响参数r=1.4;将任意潜在发送节点a与潜在接收节点b在相遇时任意一 方发起协作转发请求时另一方接受的概率Pab以协作概率模型公式表示:

Pab=1+C(a,b)β·[D(a,b)]r

取自私性强度参数β=4;

第三步:获取所有节点对之间的接触与协作行为参量后,启动仿真模型使之开始运 行;每经过网络中节点可完成基本协作转发操作的任意单位仿真时隙(t0,t0+1),即更新 节点间的接触信息,该单位时隙内任意潜在发送节点a与潜在接收节点b发生接触的概 率P(Xab(t0+1)-Xab(t0)>0)可以节点间的相互接触事件泊松过程模型公式表示如下:

P(Xab(t0+1)-Xab(t0)>0)=Σk=1P(Xab(t0+1)-Xab(t0)=k)=Σk=1(λab)k·e-λabk!=-1-e-λab

如果任意节点对以概率地在单位仿真时隙(t0,t0+1)内发生了接触,且两个节点间任 一方需要对方为其自身转发数据,则另一方依照协作概率模型所定义的概率决定是否为 其进行协作转发。

令移动社交网络节点在本方法建立的仿真模型下运行500单位仿真时隙,记录下所 有网络节点对之间的历史累积接触次数并绘制其分布图,如图1中曲线s所示,其累积 相互接触次数的节点对占总节点对数量的百分比分布特征近似于幂律(power-law)分布。 曲线s被与图2中曲线t所示的《美国电气与电子工程师协会学报》(IEEE  TRANSACTIONS ON MOBILE COMPUTING,VOL.10,NO.11,NOVEMBER2011)所 采集的国际计算机通信会议06(Infocom06)数据集中的节点对接触次数分布图相比较, 其结果显示:本方法所提出的机会路由行为模型所得的节点对接触历史分布图线与国际 计算机通信会议06数据集中所得的结果在分布特性上极为相似,且均近似于具有幂律 分布特性的经验分布值。本实施例的实施过程及其仿真结果充分说明了本发明基于移动 社交网络节点社会特性的机会路由行为建模方法能有效模拟真实社会中移动社交节点 的相互接触行为特征,能为智能手机式移动设备以蓝牙4.0技术标准组网构成的移动社 交网络中设备间路由技术的开发与革新及其机会投递行为相关科学问题的研究提供合 理且接近真实移动社交网络场景的仿真基础。

实施例2:

本实施例中在本发明所提出的接触-协作模型中利用参数调节构建具有不同强度社 会自私性的仿真环境,并为每组社会自私性设置具有平均自私性的对照仿真组,然后对 比和讨论其仿真结果。

需建模的真实移动社交网络由具有全向天线的智能手机式移动设备节点构成,相互 间以蓝牙4.0(Bluetooth4.0)技术标准进行数据交换,采用与实施例1相同的网络节点场 景参量。将移动设备的上述特征输入到曙光A650-G图形处理器(DAWNING A650-G GPU)高性能计算机中,对应于硬件设备的仿真背景常量为在本 实施例中结合基于移动社交网络节点社会特性的机会路由行为建模方法,按如下步骤重 复9次生成节点间的社会关系模型及其所决定的机会路由行为模型:

采用新增节点随机优先连接系数m=2的巴拉巴西-艾伯特(BA)无标度网络模型随机 生成节点间的无向社会关系网络,进一步采用戈尔文-纽曼(GN)算法将所生成的社会关 系网划分为两个社团并为节点加上对应的社团标签(label)。按照如下步骤逐个获取网络 中任意潜在发送节点a与潜在接收节点b之间的机会路由行为相关特性:

第一步:通过检验前述社团标签获得任意潜在发送节点a与潜在接收节点b是否属 于同一社团的信息,若二者属同社团节点,则记社团属性参量C(a,b)=3,反之令该参量 C(a,b)=0;基于前述生成的节点间社会关系网,利用广度优先搜索算法获取任意潜在发 送节点a与潜在接收节点b在社会关系网中的跳数距离D(a,b);

第二步:根据上一步中获取的特定节点对间的社会关系参数,以社会性节点接触频 率模型获取任意潜在发送节点a与潜在接收节点b之间的接触频率泊松过程参数λab, 取社会链路影响参数r=1.8;以协作概率模型获取任意潜在发送节点a与潜在接收节点 b在相遇时任意一方发起协作转发请求时另一方接受的概率Pab;图3是采用本发明方 法所建立的仿真模型中采用不同强度的社会自私性及其平均自私性对照组获得的投递 时延曲线图;图4是采用本发明方法所建立的仿真模型中采用不同强度的社会自私性及 其平均自私性对照组获得的投递成功率曲线图,其中曲线d与i、e与j的仿真组中分别 取自私性强度参数β=4和β=8;

第三步:所有节点对之间的接触和协作行为按上述规则建立后,启动仿真模型使之 开始运行;每经过网络中节点可完成基本协作转发操作的单位仿真时隙,即根据前述节 点间相互接触事件泊松过程模型更新节点对之间的接触信息,在该时隙内相遇的节点对 中任一方需要另一方为其转发数据,则对方根据协作概率模型决定是否为其协作转发。

每次节点间社会关系模型和机会路由行为模型生成后,记录下社团节点数比值 (community ratio),即划分出的一个社团节点数与全网络总节点数之比作为仿真自变量; 重复进行60000次机会投递仿真实验,每次投递时均在网络中随机选取一个投递源节点 和一个单播目的节点,每个生成的机会投递数据包生存时限设定为TTL=13单位仿真时 隙,网络中允许的最大包副本数为2,采用投递时延(以单位仿真时隙计)和投递成功 率两种指标来衡量各仿真组进行机会路由投递的性能。每次模型生成及其仿真结果构成 各仿真曲线上的一个点,多次随机生成的点即连接成各条仿真曲线。

曲线p与h显示节点间不考虑自私性的无条件协作仿真组,曲线d与i、e与j分别 显示在①具有自私性强度参数β=4的社会自私性;②具有自私性强度参数β=8社会自 私性的场景下移动社交网络节点的平均投递时延与投递率曲线f与k、g与l为自私性 强度参数β=4和β=8的社会自私性仿真组的对照实验,分别显示当所有移动社交网络 节点对之间被设置为具有相等的自私性且其值为与之所对应的社会自私性仿真组中所 有节点对间自私性的统计平均值时,网络的平均投递时延与平均投递成功率。这种平均 自私性事实上体现了《美国电气与电子工程师协会全球通信会议》(IEEE Globecom, Page(s)1-5,2011)中所提及的不受节点社会亲疏关系影响的个体自私性(individual  selfishness)。本实例中各仿真组采用《美国电气与电子工程师协会学报》(IEEE  TRANSACTIONS ON MOBILE COMPUTING,VOL.10,NO.11,NOVEMBER2011)中 所提出的BUBBLE RAP机会路由算法进行仿真投递。分别对比曲线p、d、e和h、i、 j可发现:网络节点间的投递性能随着自私性的引入及其程度的加深(随β值的增大) 而持续下降,具体表现为平均投递时延的增加和投递成功率的下降。自私性的增加降低 了移动社交中各节点为其它节点协作转发的平均概率,明显地阻碍了路由消息向更优中 继转发的过程,从而对机会路由投递性能产生了负面影响。而曲线d与f、e与g、i与 k及j与l的对比显示:具有自私性强度参数β=4和β=8的社会自私性的仿真组投递性 能均优于它们各自具有平均自私性的对照组。这是因为在BUBBLE RAP机会路由算法 中,具有较高中心度(centrality)的节点更易于被其他节点请求协作转发,它们自身丰富 的社会链路关系使得它们与其他节点的平均协作概率要显著高于网络平均水平。而在具 有平均自私性的对照组内,这种协作概率实际被降低了,这就使得被投递的消息更难在 移动社交网络中被逐渐转发到合适的中继节点上去,从而降低了整体投递性能。

本实施例选择上述生成的各曲线中社团节点数比值为0.835的仿真图点,在图5中 给出采用本发明方法所建立的仿真模型中无条件协作场景下各节点为其它节点提供协 作次数的分布图;在图6中给出采用本发明方法所建立的仿真模型中引入自私性强度参 数β=4的社会自私性场景下各节点为其它节点提供协作次数的分布图;在图7中给出 采用本发明方法所建立的仿真模型中引入自私性强度参数β=8的社会自私性场景下各 节点为其它节点提供协作次数的分布图。各节点为其它节点提供协作的频度均随自私程 度的加深而持续下降,然而网络中为他人提供中继协作次数最多的若干枢纽节点(hub node)的协作概率随自私性引入而下降的趋势明显缓于网络中的其它节点。对仿真数据 的统计显示:移动社交网络中的五大枢纽节点在自私性强度参数β=4的仿真组中,相 比于无条件协作的仿真组而言提供的平均中继总次数仅下降了6.74%,而其它节点的这 一平均值相应下降了42.20%;五大枢纽节点在自私性强度参数β=8的仿真组中,相比 于无条件协作的仿真组而言提供的平均中继总次数下降了38.64%,而其它节点的这一 平均值相应下降了57.27%,这说明引入社会自私性的场景下枢纽节点在网络中承担的 协作转发比例相比于无条件协作场景而言有所增加。产生该现象的原因在于:枢纽节点 处在社会关系网中的核心位置,它们与网络中其它节点在社会关系网中的平均跳数距离 明显较小。而在前述本发明技术方案的协作概率模型中,节点间的协作概率与它们在社 会关系网中的跳数距离呈负相关,这种特性使得当社会自私性被引入到仿真模型中时, 枢纽节点提供的平均协作概率受自私行为影响的程度明显轻于其他普通网络节点。

实施例2充分显示了本发明所提出的基于移动社交网络节点社会关系特性的机会路 由行为模型能通过参数调节实现节点具有不同程度和类型自私性的场景,能有效地为智 能手机式移动设备以蓝牙4.0技术标准组网构成的移动社交网络中设备间路由传输技术 的开发与革新及其机会投递行为相关科学问题的研究提供合理的仿真基础。

去获取专利,查看全文>

相似文献

  • 专利
  • 中文文献
  • 外文文献
获取专利

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号