美章网 资料文库 移动P2P网络拓扑构造策略范文

移动P2P网络拓扑构造策略范文

时间:2022-12-10 10:26:34

移动P2P网络拓扑构造策略

移动P2P网络已经成为近年来研究热点领域之一。作为一种新兴的移动数据共享方式,移动P2P网络为人们在无基础设施支持的环境下提供了一种数据传输的解决方案,在军事战场、抢险救灾以及用户信息共享等领域具有十分广阔的应用前景。但是,与传统P2P系统相比,移动P2P网络具有节点移动频繁、移动设备资源受限、无线连接的不可靠以及有限的通信带宽等特点,这些都给在移动环境中构建P2P系统带来了巨大挑战。在移动P2P网络中,由于节点移动频繁,覆盖层无法保持相对持久的稳定性,会导致覆盖层与底层物理网络出现拓扑不匹配的情况,即拓扑匹配问题,这不但会引起资源查找和数据传输效率低下,而且也会导致较高的网络维护开销,浪费宝贵的无线带宽资源,因此,如何解决拓扑匹配问题,建立高效的资源查找策略是移动P2P网络研究的核心内容之一。

1相关工作

目前,针对移动P2P网络覆盖层拓扑结构以及资源查找策略,许多研究人员对此展开了深入的研究。文献[3]提出了一个跨层设计的具有拓扑匹配的覆盖网,利用MAC层多播来定期广播维护消息,收到维护消息后每个节点比较该节点与邻居节点间的距离以及各邻居节点间的最大距离,根据结果删除距离较长的冗余连接。这一方法虽然解决了拓扑匹配问题,但却需要广播大量的维护消息来维护拓扑,因而浪费了宝贵的网络带宽资源。文献[4]建立了一个基于移动内容服务器的移动P2P网络,通过移动内容服务器管理节点位置信息和一部分共享内容信息。进行查询时,由移动内容服务器推荐可能的资源拥有者列表及相关的路由信息,从而使查询节点可以较快地获得资源信息。这种方法可以较好地避免洪泛所带来的网络开销过大的缺点,但是移动内容服务器存在单点失效的风险。文献[5]提出了一个基于超节点的移动P2P网络框架RobP2P,建立了一个双层结构,上层由稳定的可靠性高的超级节点组成,下层由普通节点组成。虽然该文献旨在建立一个健壮的、高效的移动P2P网络,但是,其资源查找仍然是采用洪泛方式,仍然存在网络开销过大、耗费节点电量的缺点。文献[6]构造了具有双层结构的覆盖网,通过引入锚节点,建立了基于地理位置信息的覆盖网并提出相应的资源查找算法,但该方法中如何选取合理的锚节点是一个关键问题。文献[7,8]构建了具有层次结构的Chord环,虽然充分利用了节点异构性强的特点,有利于网络负载平衡,但是由于覆盖网的构建通常没有考虑到移动节点的物理位置,会出现覆盖网上的邻居节点可能在物理网络中相距甚远,因而大大增加了资源查找时延。通过以上分析可以看出,覆盖网拓扑结构是整个移动P2P网络的基础,只有构建设计合理、健壮的移动P2P网络拓扑结构,才能提高资源查找的效率,减少因环境变化带来的性能衰减。因此本文从移动P2P体系结构入手,提出了一种具有拓扑匹配的覆盖网构造方法,并在此基础上,提出了相应的资源查找策略,主要目的是提高资源搜索效率,减少用户访问时延,降低网络开销,提高服务质量。

2基于网格坐标自治域的移动P2P覆盖网拓扑构造

2.1分层虚拟网格坐标自治域的建立定义1虚拟网格坐标自治域是一个逻辑的二维笛卡尔坐标空间,x轴和y轴将该平面划分成四个象限,以x轴的右半轴开始沿逆时针方向分别将四个象限命名为1、2、3和4象限。定义2分层虚拟网格坐标自治域是虚拟网格坐标自治域的扩展,将每个象限继续划分为四个子象限,以此类推,逐层划分,就形成了分层虚拟网格坐标自治域。网络中所有节点最终都要映射到虚拟网格坐标自治域中,为建立虚拟网格坐标自治域,将第一个进入该系统的节点n0确定为引导节点,以n0为原点建立虚拟网格坐标自治域,如图1所示。整个区域Z可以看做一个大正方形区域,作为第0级网格坐标自治域,将整个区域Z按笛卡尔坐标象限划分成四个象限,分别定义为Z1、Z2、Z3、Z4,作为第一级网格坐标自治域。按相同方法,可以将每级坐标自治域继续划分成更小的子区域,直到所划分的网格坐标自治域边长L小于D/槡2为止(这里D表示虚拟网格坐标自治域距离阈值,下文作详细介绍);将这些最小的正方形区域定义为单位网格坐标自治域,凡是位于同一个单位网格坐标自治域内的任意两个节点间都是可以相互通信的。如图1所示,以第一象限Z1为例,坐标自治域从第一级划分开始,直至第三级,这里,分别对每层自治域的第一象限命名为Z1、Z11、Z111。这里的网格区域用符号Zxxxx表示,其中xxxx从最左边开始分别表示每一级所属的第x象限(按笛卡尔坐标象限划分方法,其值为1、2、3、4)。

2.2构建基于网格坐标自治域的覆盖网考虑到无基础设施支持的MANET网络中,移动节点通常没有固定的IP地址,无法使用基于IP地址前缀的方法来构建拓扑匹配的覆盖网,因此,本文将采用更为通用的通信时延作为距离的度量单位,构建具有物理位置感知的移动P2P覆盖网络,能够有效避免因拓扑不一致而产生的绕路现象,从而降低用户访问时延,提高网络工作效率。通常,在物理网络中,距离较近的节点之间的通信时延也较短。因此,为了构建具有拓扑匹配的移动P2P覆盖网,将物理网络中节点之间的时延按着比例映射成为虚拟网格坐标自治域中的距离。例如,物理网络中节点间通信的传播时延为1ms可以等价于覆盖逻辑空间中的1个距离单位,那么,两个节点ni和nj之间的时延也可以按相同比例映射成覆盖网上的距离d(ni,nj)。假设两个节点间的最大通信时延为F(即在该时延F范围内,两节点位于彼此的通信范围,可以直接通信),那么映射到覆盖逻辑空间中就有一个距离阈值。已知第一个加入到网络的节点n0为引导节点,其坐标为(0,0)。n1为第二个加入到P2P网络的节点,按着前文所述的映射规则,将n0与n1的通信时延映射成为覆盖网中的距离d(n0,n1),在虚拟网格坐标自治域中,n1可以选择在以引导节点n0为中心,以d为半径的圆周上任意位置,为计算方便,设n1的覆盖网坐标为(0,d)。第三个加入节点n2的坐标根据n0(0,0)与n1(0,d)的覆盖网坐标以及n2与n0、n1的通信时延映射成为覆盖网中的距离d(n2,n0)和d(n2,n1)来确定,有两个待选位置,分别为pv和pw,如图1所示。任选一个位置pv作为n2的坐标,这种方法是根据旋转原则,不会破坏节点在虚拟网格自治域中的相对位置。此时,系统初始化过程完成,取消引导节点。当前三个节点的坐标确定后,其他后续加入节点的虚拟坐标,可以根据已知节点的覆盖网距离和已知节点的坐标计算获得。例如,当节点n3要加入移动P2P网络,如图1所示,通过n3与之间的通信时延计算出其覆盖网距离,并且坐标为已知条件,则根据三角函数可以计算出n3的覆盖网坐标n3(x,y),根据坐标位置与单位网格坐标自治域的四个顶点坐标(逻辑坐标确定后,由于各个单位自治域边长为已知,则单位网格坐标自治域的四个顶点坐标就已经确定下来)进行对比,将其划分到相应的自治域内。图1中的节点n3位于第一级的第1象限,第二级的第3象限,第三级的第4象限,则n3的标志符表示为(Z134,n3(x,y)),其中Z134是节点n3所在的网格坐标自治域,n3(x,y)为节点n3的覆盖网坐标。这种映射机制能够保证物理网络中距离较近的节点在覆盖网中也距离较近,从而建立起具有拓扑匹配的移动P2P覆盖网。

2.3节点移动性处理为了减少节点移动所带来的扰动,当节点在单位网格坐标自治域内小范围移动时,对节点的相关信息可以不作修改;只有当节点移出所属的单位网格坐标自治域时,才更新节点信息,并分配其新的虚拟坐标,这样可以大幅度减少拓扑维护信息,降低网络开销,节省宝贵的无线带宽资源。更进一步,考虑到那些位于网格自治域边缘的节点,随着节点移动,会出现节点在不同网格自治域间来回切换的情况,如果频繁更新信息,会造成网络开销过大。为了解决这一问题,本文引入一个阈值区域,如图2中所示的灰色地带,假设位于Z112网格自治域的节点要离开Z112进入到阈值区域(a点),随着节点移动,即使节点已经移动到Z113网格自治域时(b点),但是并不对该节点进行信息更新,直到节点离开阈值区域(c点),再更新节点的位置信息。通过引入阈值区域,能够有效减少节点移动性扰动所带来的通信维护开销。2.4索引节点的选取在每个单位网格坐标自治域内选出一个索引节点(索引节点选取方法由文献[9]给出),然后在上一级网格坐标自治域内重新选出索引节点,直至第0级。当新节点加入网络时,要将其所共享的资源信息列表发送给其所在的网格自治域的索引节点,即单位网格自治域内的索引节点是需要存储其域内所有节点的资源索引信息、节点标志、区域标志等。考虑到更高一级的索引节点如果维护其域内全部资源和节点的信息,会导致索引节点维护信息量过大,因此本文规定,较高一级的节点只维护粗略的信息,这里引入一个布尔变量,标志该区域是否有该资源,这样可以大大降低高级的索引节点信息维护量。考虑到系统容错性和健壮性,同时选取一个备份索引节点。当索引节点失效时,可以利用备份索引节点进行资源搜索。

3资源查找策略(RSHIN)

下面,针对文中提出的网格坐标自治域结构,提出基于分层索引节点的资源查找策略RSHIN(resourcesearchingstrategybasedonhierarchicalindexnode)。具体查找过程如下:a)当节点S需要查找某一资源R时,S首先向其自身所在的单位网格坐标自治域索引节点I发出资源查寻请求。如果索引节点I保存有存储资源R的源节点D的信息,则索引节点I将节点D的标志信息发送给S,S与D建立连接;否则转b)。b)如果索引节点I没有关于资源R的相关索引信息,则将查询请求转发给上一级索引节点,若仍然没有则再往上一级索引节点进行查询,逐级往上直至查询到顶级索引节点为止。若某一级索引节点存有资源R的信息,则转c)。若均没有,则本次查找失败。c)如果某一级索引节点存有资源R(表示该资源的布尔值为l)的信息,则该索引节点向其子区域的索引节点发出查询,逐级往下直至找到拥有该资源的详细索引信息的单位自治域内的索引节点为止,然后按着逆向步骤,则该级索引节点将节点D的标志信息发送给S,S与D建立连接。最终完成移动P2P网络资源查找与共享。下面给出RSHIN算法的伪代码描述。设拓扑结构划分深度为depth,m=depth,B是自治域索引节点存储资源的布尔值(0不存在,1存在);F表示是否为单位自治域(0是,1否)。

4仿真实验与结果分析

为了验证本文所提出的资源查找策略RSHIN的有效性,本文采用NS-2作为仿真实验平台,进行了仿真实验。实验场景参数设置:节点随机分布在4000m×4000m的区域内,节点移动速度为0~10m/s,节点通信半径为200m。移动节点个数在120~600,节点移动模型符合随机路点模型[10],假设节点停留时间为10s。无线通信带宽为2Mbps,MAC层采用802.11协议。假设每个节点拥有10个共享资源,资源大小为512Byte,发送速率为300kbps,发送节点和接收节点随机产生,每秒产生10个节点。文献[11]提出的CAR资源查找策略采用了基于地理位置信息的哈希索引结构,为了评价本文提出的查找策略,将RSHIN与CAR策略进行仿真实验,并对结果作出分析。首先考察不同节点密度对资源查找平均路径长度的影响。资源查找路径长度可以用跳数来度量。移动节点个数为120~600,每隔60取一个值,仿真实验结果如图3所示。可以看出,随着节点数量的增加,RSHIN查找策略的平均查找路径长度明显小于CAR的查找策略,主要是由于RSHIN采用层级递进的查询策略,并根据节点的坐标与网格坐标自治域信息,可以快速定位到资源节点的位置,因此提高了资源查找效率。接下来考察不同节点密度对资源查找成功率的影响。如图4所示,随着节点数量不断增加,两种算法的查找成功率都有所提升,但本文所提出的RSHIN查找策略要优于CAR算法。本文通过采取后备索引节点,当含有资源的叶子节点对应的资源节点失效时,资源查询信息快速地通过其域内的后备索引节点找到目的节点,从而可以有效降低索引节点失效而导致的性能下降,并且大大提高了资源查找成功率。

5结束语

本文提出了一种具有拓扑匹配的网格坐标自治域结构,充分考虑了物理网络中节点之间的位置关系,将物理邻近的节点划分到相同或者相邻的单位网格坐标自治域内,即保证物理邻近的节点在覆盖网上也邻近,从而可以有效减少由于拓扑不匹配而产生的网络性能下降等问题。考虑到节点移动扰动,引入阈值区域,可以有效降低网络维护开销。针对该拓扑结构,提出基于索引节点的资源查找策略RSHIN。仿真实验结果表明,该资源查找策略可以有效提升网络查找效率,降低数据访问延迟,提高了网络可用性及可扩展性。下一步工作中将主要研究如何进一步减少信息的冗余与节点能量的消耗问题。

作者:周欣欣 高越 宋人杰 余镇危 单位:东北电力大学 信息工程学院 中国矿业大学( 北京) 机电与信息工程学院

被举报文档标题:移动P2P网络拓扑构造策略

被举报文档地址:

https://www.meizhang.comhttps://www.meizhang.com/txcb/wltplw/683629.html
我确定以上信息无误

举报类型:

非法(文档涉及政治、宗教、色情或其他违反国家法律法规的内容)

侵权

其他

验证码:

点击换图

举报理由:
   (必填)